Topology control for wireless sensor networks

ABSTRACT

We consider a two-tiered Wireless Sensor Network (WSN) consisting of sensor clusters deployed around strategic locations and base-stations (BSs) whose locations are relatively flexible. Within a sensor cluster, there are many small sensor nodes (SNs) that capture, encode and transmit relevant information from the designated area, and there is at least one application node (AN) that receives raw data from these SNs, creates a comprehensive local-view, and forwards the composite bit-stream toward a BS. In practice, both SN and AN are battery-powered and energy-constrained, and their node lifetimes directly affect the network lifetime of WSNs. In this paper, we focus on the topology control process for ANs and BSs, which constitute the upper tier of a two-tiered WSN. We propose approaches to maximize the topological network lifetime of the WSN, by arranging BS location and inter-AN relaying optimally. Based on an algorithm in Computational Geometry, we derive the optimal BS locations under three topological lifetime definitions according to mission criticality. In addition, by studying the intrinsic properties of WSNs, we establish the upper and lower bounds of their maximal topological lifetime. When inter-AN relaying becomes feasible and favorable, we continue to develop an optimal parallel relay allocation to further prolong the topological lifetime of the WSN. An equivalent serialized relay schedule is also obtained, so that each AN only needs to have one relay destination at any time throughout the mission. The experimental performance evaluation demonstrates the efficacy of topology control as a vital process to maximize the network lifetime of WSNs.

REFERENCES

• 1: C-F. Chiasserini and E Magli. Energy consumption and image quality in wireless video surveillance networks. Proc. 13th IEEE PIMRC, 2002.
• 2: W. Feng, J. Walpole, W. Feng, and C. Pu. Moving towards massively scalable video-based sensor networks. Proc. Workshop on New Visions for Large-Scale Networks: Research and Applications, 2001.
• 3: R. Collins, A. Lipton, H. Fujiyoshi, and T. Kanade. Algorithms for cooperative multisensor surveillance. Proceedings of IEEE, 89(10):1456--1477, 2001
• 4: Vijay Chandramohan , Ken Christensen, A First Look at Wired Sensor Networks for Video Surveillance Systems, Proceedings of the 27th Annual IEEE Conference on Local Computer Networks, p.728-729, November 06-08, 2002
• 5: R. Ramanathan and J. Redi. A brief overview of ad hoc networks: challenges and directions. IEEE Communications Magazine, 40(5):20--22, 2002.
• 6: Deborah Estrin , Ramesh Govindan , John Heidemann , Satish Kumar, Next century challenges: scalable coordination in sensor networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.263-270, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313556]
• 7: J. Chou, D. Petrovis, and K. Ramchandran. A distributed and adaptive signal processing approach to reducing energy consumption in sensor networks. IEEE Infocom'03, 2003.
• 8: Y. Hou, Y. Shi, J. Pan, A. Efrat, and S. Midkiff. Maximizing lifetime of wireless sensor networks through single-session flow routing. Technical Report, The Bradley Dept. of ECE, Virginia Tech, 2003.
• 9: T. Camp, J. Boleng, and V. Davies. A survey of mobility models for ad hoc network research. Wireless Communication & Mobile Computing, 2(5):483--502, 2002.
• 10: S. Ramanathan , Martha Steenstrup, A survey of routing techniques for mobile communications networks, Mobile Networks and Applications, v.1 n.2, p.89-104, Oct. 1996 [doi>10.1007/BF01193330]
• 11: E. Royer and C-K. Toh. A review of current routing protocols for ad hoc wireless networks. IEEE Personal Communications Magazine, 6(2):46--55, 1999.
• 12: Josh Broch , David A. Maltz , David B. Johnson , Yih-Chun Hu , Jorjeta Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.85-97, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288256]
• 13: Chris Barrett , Achla Marathe , Madhav V. Marathe , Martin Drozda, Characterizing the interaction between routing and MAC protocols in ad-hoc networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513812]
• 14: Sung-Ju Lee , William Su , Mario Gerla, Wireless ad hoc multicast routing with mobility prediction, Mobile Networks and Applications, v.6 n.4, p.351-360, Aug. 2001 [doi>10.1023/A:1011478628358]
• 15: Jinyang Li , John Jannotti , Douglas S. J. De Couto , David R. Karger , Robert Morris, A scalable location service for geographic ad hoc routing, Proceedings of the 6th annual international conference on Mobile computing and networking, p.120-130, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345931]
• 16: A. Amis, R. Prakash, T. Vuong, and D. Huynh. Max-min d-cluster formation in wireless ad hoc networks. Proc. IEEE Infocom'2000, pp. 32--41, 2000.
• 17: Z. Haas, et al., eds.. Special issue on wireless ad hoc networks. IEEE J. on Selected Areas in Communications, 17(8), 1999.
• 18: Christine E. Jones , Krishna M. Sivalingam , Prathima Agrawal , Jyh Cheng Chen, A Survey of Energy Efficient Network Protocols for Wireless Networks, Wireless Networks, v.7 n.4, p.343-358, 08/01/2001 [doi>10.1023/A:1016627727877]
• 19: Gavin Holland , Nitin Vaidya, Analysis of TCP performance over mobile ad hoc networks, Wireless Networks, v.8 n.2/3, p.275-288, March-May 2002 [doi>10.1023/A:1013798127590]
• 20: I. F. Akyildiz , W. Su , Y. Sankarasubramaniam , E. Cayirci, Wireless sensor networks: a survey, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.38 n.4, p.393-422, 15 March 2002 [doi>10.1016/S1389-1286(01)00302-4]
• 21: J. Chang and L. Tassiulas. Energy conserving routing in wireless ad hoc networks. Proc. IEEE Infocom'2000, pp. 22--31, 2000.
• 22: M. Bhardwaj, A. Chandrakasan, and T. Garnett. Upper bounds on the lifetime of sensor networks. Proc. IEEE ICC'01, pp. 785--790, 2001.
• 23: M. Bhardwaj and A. Chandrakasan. Bounding the lifetime of sensor networks via optimal role assignment. Proc. IEEE Infocom'02, pp. 1587--1596, 2002.
• 24: Douglas M. Blough , Paolo Santi, Investigating upper bounds on network lifetime extension for cell-based energy conservation techniques in stationary ad hoc networks, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570668]
• 25: Benjie Chen , Kyle Jamieson , Hari Balakrishnan , Robert Morris, Span: An energy-efficient coordination algorithm for topology maintenance in Ad Hoc wireless networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.85-96, July 2001, Rome, Italy [doi>10.1145/381677.381686]
• 26: Wendi Rabiner Heinzelman , Anantha Chandrakasan , Hari Balakrishnan, Energy-Efficient Communication Protocol for Wireless Microsensor Networks, Proceedings of the 33rd Hawaii International Conference on System Sciences-Volume 8, p.8020, January 04-07, 2000
• 27: R. Wattenhofer, L. Li, P. Bahl, and Y. Wang. Distributed topology control for wireless multihop ad hoc networks. Proc. IEEE Infocom'01, pp. 1388--1397, 2001.
• 28: Curt Schurgers , Vlasios Tsiatsis , Saurabh Ganeriwal , Mani Srivastava, Topology management for sensor networks: exploiting latency and density, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513817]
• 29: R. Ramanathan and R. Rosales-Hain. Topology control of multihop wireless networks using transmit power adjustment. Proc. IEEE Infocom'2000, pp. 404--413, 2000.
• 30: Ayad Salhieh , Jennifer Weinmann , Manish Kochhal , Loren Schwiebert, Power Efficient Topologies for Wireless Sensor Networks, Proceedings of the 2001 International Conference on Parallel Processing, p.156-166, September 03-07, 2001
• 31: Seapahn Meguerdichian , Farinaz Koushanfar , Gang Qu , Miodrag Potkonjak, Exposure in wireless Ad-Hoc sensor networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.139-150, July 2001, Rome, Italy [doi>10.1145/381677.381691]
• 32: Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin, Directed diffusion: a scalable and robust communication paradigm for sensor networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.56-67, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345920]
• 33: Wendi Beth Heinzelman , Anantha P. Chandrakasan , Hari Balakrishnan, Application-specific protocol architectures for wireless networks, 2000
• 34: Wendi Rabiner Heinzelman , Joanna Kulik , Hari Balakrishnan, Adaptive protocols for information dissemination in wireless sensor networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.174-185, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313529]
• 35: Eugene Shih , Seong-Hwan Cho , Nathan Ickes , Rex Min , Amit Sinha , Alice Wang , Anantha Chandrakasan, Physical layer driven protocol and algorithm design for energy-efficient wireless sensor networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.272-287, July 2001, Rome, Italy [doi>10.1145/381677.381703]
• 36: Alec Woo , David E. Culler, A transmission control scheme for media access in sensor networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.221-235, July 2001, Rome, Italy [doi>10.1145/381677.381699]
• 37: W. Ye, J. Heidemann, and D. Estrin. An energy-efficient MAC protocol for wireless sensor networks. Proc. IEEE Infocom'02, pp. 1567--1576, 2002.
• 38: E. Jung and N. Vaidya. An energy efficient MAC protocol for wireless LANs. Proc. IEEE Infocom'02, 2002.
• 39: Ya Xu , John Heidemann , Deborah Estrin, Geography-informed energy conservation for Ad Hoc routing, Proceedings of the 7th annual international conference on Mobile computing and networking, p.70-84, July 2001, Rome, Italy [doi>10.1145/381677.381685]
• 40: G. J. Pottie , W. J. Kaiser, Wireless integrated network sensors, Communications of the ACM, v.43 n.5, p.51-58, May 2000 [doi>10.1145/332833.332838]
• 41: K. Sohrabi, J. Gao, V. Ailawadhi, and G. Pottie. Protocols for self-organization of a wireless sensor network. IEEE Personal Communications, 7(5):16--27, 2000.
• 42: E. Welzl. Smallest enclosing disks (balls and ellipsoids). Lecture Notes in Computer Science, 555:359-370, 1991.
• 43: D. Niculescu and B. Nath. Ad Hoc Positioning System (APS) using AoA. Proc. IEEE Infocom'03, 2003.
• 44: Michele Zorzi , Ramesh R. Rao, Error Control and Energy Consumption in Communications for Nomadic Computing, IEEE Transactions on Computers, v.46 n.3, p.279-289, March 1997 [doi>10.1109/12.580424]
• 45: F. Ye, H. Luo, J. Cheng, S. Lu, and L. Zhang. A two-tier data dissemination model for large scale wireless sensor networks. Proc. ACM Mobicom'01, pp. 148--159, 2001.
• 46: E. Duarte-Melo and M. Liu. Analysis of energy consumption and lifetime of heterogeneous wireless sensor networks. Proc. IEEE Globecom'02, 2002.

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.1 Network Architecture and Design
          Subjects: Wireless communication

General Terms:
Algorithms, Design, Performance

Keywords:
network lifetime, topology control, wireless sensor networks