Robust topology control for indoor wireless sensor networks

ABSTRACT

Topology control can reduce power consumption and channel contention in wireless sensor networks by adjusting the transmission power. However, topology control for wireless sensor networks faces significant challenges, especially in indoor environments where wireless characteristics are extremely complex and dynamic. We first provide insights on the design of robust topology control schemes based on an empirical study in an office building. For example, our analysis shows that Received Signal Strength Indicator and Link Quality Indicator are not always robust indicators of Packet Reception Rate in indoor environments due to significant multi-path effects. We then present Adaptive and Robust Topology control (ART), a novel and practical topology control algorithm with several salient features: (1) ART is robust in indoor environments as it does not rely on simplifying assumptions about the wireless properties; (2) ART can adapt to variations in both link quality and contention; (3) ART introduces zero communication overhead for applications which already use acknowledgements. We have implemented ART as a topology layer in TinyOS 2.x. Our topology layer only adds 12 bytes of RAM per neighbor and 1.5 kilobytes of ROM, and requires minimal changes to upper-layer routing protocols. The advantages of ART have been demonstrated through empirical results on a 28-node indoor testbed.

REFERENCES

• 1: CC1000 Single Chip Very Low Power RF Transceiver, Texas Instruments.
• 2: 2.4 GHz IEEE 802.15.4 / ZigBee-ready RF Transceiver, Texas Instruments.
• 3: K. Srinivasan and P. Levis, "RSSI is under appreciated," in EmNets, 2006.
• 4: Shan Lin , Jingbin Zhang , Gang Zhou , Lin Gu , John A. Stankovic , Tian He, ATPC: adaptive transmission power control for wireless sensor networks, Proceedings of the 4th international conference on Embedded networked sensor systems, October 31-November 03, 2006, Boulder, Colorado, USA [doi>10.1145/1182807.1182830]
• 5: D. Son, B. Krishnamachari, and J. Heidemann, "Experimental study of the effects of transmission power control and blacklisting in wireless sensor networks," in IEEE SECON, 2004.
• 6: Alec Woo , Terence Tong , David Culler, Taming the underlying challenges of reliable multihop routing in sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958494]
• 7: N. Reijers, G. Halkes, and K. Langendoen, "Link layer measurements in sensor networks," in IEEE MASS, 2004.
• 8: Gang Zhou , Tian He , Sudha Krishnamurthy , John A. Stankovic, Impact of radio irregularity on wireless sensor networks, Proceedings of the 2nd international conference on Mobile systems, applications, and services, June 06-09, 2004, Boston, MA, USA [doi>10.1145/990064.990081]
• 9: D. Lal, A. Manjeshwar, F. Herrmann, E. Uysal-Biyikoglu, and A. Keshavarzian, "Measurement and characterization of link quality metrics in energy constrained wireless sensor networks," in IEEE GLOBECOM, 2003.
• 10: D. Ganesan, B. Krishnamachari, A. Woo, D. Culler, D. Estrin, and S. Wicker, "Complex behavior at scale: An experimental study of low-power wireless sensor networks," UCLA Computer Science Department, Tech. Rep., 2002.
• 11: Jerry Zhao , Ramesh Govindan, Understanding packet delivery performance in dense wireless sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958493]
• 12: Li Li , Joseph Y. Halpern , Paramvir Bahl , Yi-Min Wang , Roger Wattenhofer, Analysis of a cone-based distributed topology control algorithm for wireless multi-hop networks, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.264-273, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.384043]
• 13: N. Li, J. C. Hou, and L. Sha, "Design and analysis of an MST-based topology control algorithm," IEEE Transactions on Wireless Communications, vol. 4, no. 3, pp. 1195--1206, 2005.
• 14: Douglas M. Blough , Mauro Leoncini , Giovanni Resta , Paolo Santi, The k-Neighbors Approach to Interference Bounded and Symmetric Topology Control in Ad Hoc Networks, IEEE Transactions on Mobile Computing, v.5 n.9, p.1267-1282, September 2006 [doi>10.1109/TMC.2006.139]
• 15: Martin Burkhart , Pascal von Rickenbach , Roger Wattenhofer , Aaron Zollinger, Does topology control reduce interference?, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989462]
• 16: Douglas M. Blough , Mauro Leoncini , Giovanni Resta , Paolo Santi, Topology control with better radio models: Implications for energy and multi-hop interference, Performance Evaluation, v.64 n.5, p.379-398, June, 2007 [doi>10.1016/j.peva.2006.08.004]
• 17: Y. Gao, J. C. Hou, and H. Nguyen, "Topology control for maintaining network connectivity and maximizing network capacity under the physical model," in INFOCOM, 2008.
• 18: R. Fonseca, O. Gnawali, K. Jamieson, S. Kim, P. Levis, and A. Woo. The collection tree protocol (CTP). {Online}. Available: http://www.tinyos.net/tinyos-2.x/doc/html/tep123.html
• 19: Alberto Cerpa , Jennifer L. Wong , Miodrag Potkonjak , Deborah Estrin, Temporal properties of low power wireless links: modeling and implications on multi-hop routing, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA [doi>10.1145/1062689.1062741]
• 20: {Online}. Available: http://www.tinyos.net/
• 21: Kevin Klues , Gregory Hackmann , Octav Chipara , Chenyang Lu, A component-based architecture for power-efficient media access control in wireless sensor networks, Proceedings of the 5th international conference on Embedded networked sensor systems, November 06-09, 2007, Sydney, Australia [doi>10.1145/1322263.1322270]
• 22: {Online}. Available: http://www.cse.wustl.edu/wsn/index.php?title=MLA

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

General Terms:
Algorithms, Measurement, Performance

Keywords:
power management, topology control