Low power coordination in wireless ad-hoc networks

ABSTRACT

Distributed wireless ad-hoc networks (DWANs) pose numerous technical challenges. Among them, two are widely considered as crucial: autonomous localized operation and minimization of energy consumption. We address the fundamental problem of how to maximize life-time of the network by using only local information while preserving network connectivity. We start by introducing the Care-Free Sleep (CS) Theorem that provides provably optimal necessary and sufficient conditions for a node to turn off its radio while ensuring that global connectivity is not affected.The CS theorem is the basis for an efficient localized algorithm that decides which node will turn its radio off, and for how long. The effectiveness of the approach is demonstrated using numerous simulations of the performance of the algorithm over a wide range of network parameters.

REFERENCES

• 1: A. Cerpa and D. Estrin. Ascent: Adaptive self-configuring sensor networks topologies. In IEEE Infocom 2002.
• 2: J.-H. Chang and L. Tassiulas. Energy conserving routing in wireless ad-hoc networking. In IEEE Infocom 2000.
• 3: Benjie Chen , Kyle Jamieson , Hari Balakrishnan , Robert Morris, Span: an energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks, Wireless Networks, v.8 n.5, p.481-494, September 2002 [doi>10.1023/A:1016542229220]
• 4: Bevan Das , Raghupathy Sivakumar , Vaduvur Bharghavan, Routing in Ad Hoc Networks Using a Spine, Proceedings of the 6th International Conference on Computer Communications and Networks, p.34, September 22-25, 1997
• 5: Edsger W. Dijkstra, The structure of the “THE”-multiprogramming system, Communications of the ACM, v.11 n.5, p.341-346, May 1968 [doi>10.1145/363095.363143]
• 6: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 7: O. Kasten. Measurements of energy consumption for digitan 2 mbps wireless lan module (ieee 802.11/2mbps). http://www.inf.ethz.ch/kasten/research, 2001.
• 8: 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]
• 9: J. Rabaey, J. Ammer, T. Karalar, S. Li, B. Otis, M.Sheets, and T. Tuan. Picoradios for wireless sensor networks: The next challenge in ultra-low-power design. In ISSCC 2002.
• 10: V. Raghunathan, C. Schurgers, S. Park, and M.B. Srivastava. Energy aware wireless microsensor networks. IEEE Signal Processing March 2002.
• 11: E. Royer and C. Toh. A review of current routing protocols for ad-hoc mobile wireless networks. In IEEE Personal Communications 1999.
• 12: 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]
• 13: Eugene Shih , Benton H. Calhoun , SeongHwan Cho , Anantha P. Chandrakasan, Energy-Efficient Link Layer for Wireless Microsensor Networks, Proceedings of the IEEE Computer Society Workshop on VLSI 2001, p.16, April 19-20, 2001
• 14: 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]
• 15: A. Silberschatz, P. Galvin, and G. Gagne. Operating system concepts: Windows xp update, 2003.
• 16: M. Stemm and R.H. Katz. Measuring and reducing energy consumption of network interfaces in hand-held devices. IEICE Trans. on Comm E80-B(8): 1125--31, 1997.
• 17: 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]
• 18: W. Ye, J. Heidemann, and D. Estrin. An energy-efficient mac protocol for wireless sensor networks. In IEEE Infocom 2002.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Reliability, availability, and serviceability

General Terms:
Algorithms, Design, Performance

Keywords:
coordination, low-power, wireless ad-hoc network