Minimum power configuration in wireless sensor networks

ABSTRACT

This paper proposes the minimum power configuration (MPC) approach to energy conservation in wireless sensor networks. In sharp contrast to earlier research that treats topology control, power-aware routing, and sleep management in isolation, MPC integrates them as a joint optimization problem in which the power configuration of a network consists of a set of active nodes and the transmission powers of the nodes. We show through analysis that the minimum power configuration of a network is inherently dependent on the data rates of sources. We propose several approximation algorithms with provable performance bounds compared to the optimal solution, and a practical Minimum Power Configuration Protocol (MPCP) that can dynamically (re)configure a network to minimize the energy consumption based on current data rates. Simulations based on realistic radio models of the Mica2 motes show that MPCP can conserve significantly more energy than existing minimum power routing and topology control protocols.

References

1. Volkan Rodoplu and Teresa H. Meng, "Minimum energy mobile wireless networks," IEEE J. Selected Areas in Communications, vol. 17(8), 1999.]]
2. Ram Ramanathan and Regina Hain, "Topology control of multihop wireless networks using transmit power adjustment," in INFOCOM, 2000.]]
3. Swetha Narayanaswamy, Vikas Kawadia, R. S. Sreenivas, and P. R. Kumar, "Power control in ad-hoc networks: Theory, architecture, algorithm and implementation of the compow protocol," in European Wireless Conference, 2002.]]
4. Vikas Kawadia and P. R. Kumar, "Power control and clustering in ad hoc networks," in INFOCOM, 2003.]]
5. Li Li, Joseph Y. Halpern, Paramvir Bahl, Yi-Min Wang, and Roger Wattenhofer, "Analysis of a cone-based distributed topology control algorithm for wireless multi-hop networks," in Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, 2001.]]
6. Khaled Alzoubi, Xiang-Yang Li, Yu~Wang, Peng-Jun Wan, and Ophir Frieder, "Geometric spanners for wireless ad hoc networks," IEEE Transactions On Parallel And Distributed System, vol. 14, May 2003.]]
7. Ning Li, Jennifer C. Hou, and Lui Sha, "Design and analysis of an mst-based topology control algorithm," in INFOCOM, 2003.]]
8. Suresh Singh, Mike Woo, and C. S. Raghavendra, "Power-aware routing in mobile ad hoc networks," in Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, 1998.]]
9. Sheetalkumar Doshi, Shweta Bhandare, and Timothy X Brown, "An on-demand minimum energy routing protocol for a wireless ad hoc network," SIGMOBILE Mob. Comput. Commun. Rev., vol. 6, no. 3, pp. 50--66, 2002.]]
10. Sheetalkumar Doshi and Timothy X Brown, "Minimum energy routing schemes for a wireless ad hoc network," in INFOCOM, 2002.]]
11. Jae-Hwan Chang and Leandros Tassiulas, "Energy conserving routing in wireless ad hoc networks," in INFOCOM, 2000.]]
12. Arvind Sankar and Zhen Liu, "Maximum lifetime routing in wireless ad-hoc networks," in INFOCOM, 2004.]]
13. Crossbow, "Mica2 wireless measurement system datasheet," 2003.]]
14. Benjie Chen, Kyle Jamieson, Hari Balakrishnan, and Robert Morris, "Span: An energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks," in MobiCom, 2001.]]
15. Alberto Cerpa and Deborah Estrin., "Ascent: Adaptive self-configuring sensor networks topologies," in INFOCOM, 2002.]]
16. Ya Xu, John Heidemann, and Deborah Estrin, "Adaptive energy-conserving routing for multihop ad hoc networks," Research Report 527, USC, October 2000.]]
17. Ya Xu, John Heidemann, and Deborah Estrin, "Geography-informed energy conservation for ad hoc routing," in MobiCom, 2001.]]
18. John A. Stankovic, Tarek Abdelzaher, Chenyang Lu, Lui Sha, and Jennifer Hou, "Real-time communication and coordination in embedded sensor networks," Proceedings of the IEEE, vol. 91, no. 7, 2003.]]
19. G. Calinescu, S. Kapoor, A. Olshevsky, and A. Zelikovsky, "Network lifetime and power assignment in ad-hoc wireless networks," in ESA, 2003.]]
20. Qun Li, Javed Aslam, and Daniela Rus, "Online power-aware routing in wireless ad-hoc networks," in MobiCom, 2001.]]
21. Xiaorui Wang, Guoliang Xing, Yuanfang Zhang, Chenyang Lu, Robert Pless, and Christopher D. Gill, "Integrated coverage and connectivity configuration in wireless sensor networks," in Sensys, 2003.]]
22. T. Moscibroda and R. Wattenhofer, "Maximizing the lifetime of dominating sets," in WMAN, 2005.]]
23. Michael R. Garey and David S. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., 1990.]]
24. Alec Woo, Terence Tong, and David Culler, "Taming the underlying challenges of reliable multihop routing in sensor networks," in SenSys, 2003.]]
25. Jerry Zhao and Ramesh Govindan, "Understanding packet delivery performance in dense wireless sensor networks," in Sensys), Los Angeles, CA, November 2003.]]
26. Marco Zuniga and Bhaskar Krishnamachari, "Analyzing the transitional region in low power wireless links," in First IEEE International Conference on Sensor and Ad hoc Communications and Networks (SECON), October 2004.]]
27. A. Meyerson, K. Munagala, and S. Plotkin, "Cost-distance: two metric network design," in FOCS '00: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000.]]
28. Mirjam Wattenhofer and Roger Wattenhofer, "Distributed weighted matching," in 18th Annual Conference on Distributed Computing (DISC), 2004.]]
29. H. Takahashi and A. Matsuyama, "An approximate solution for the steiner problem in graphs," Math. Japonica, vol. 24(6), 1980.]]
30. Gabriel Robins and Alexander Zelikovsky, "Improved steiner tree approximation in graphs," in SODA, 2000.]]
31. Falchi Alessio, "Sensor networks: performance measurements with motes technology," Tech. Rep., University of Pisa, Italy, 2004.]]
32. Wei Ye, John Heidemann, and Deborah Estrin, "An energy-efficient mac protocol for wireless sensor networks," in INFOCOM, 2002.]]
33. Charles E. Perkins and Pravin Bhagwat, "Highly dynamic destination-sequenced distance-vector routing (dsdv) for mobile computers," SIGCOMM Comput. Commun. Rev., vol. 24, no. 4, 1994.]]
34. David Kotz, Calvin Newport, Robert S. Gray, Jason Liu, Yougu Yuan, and Chip Elliott, "Experimental evaluation of wireless simulation assumptions," in MSWiM, October 2004.]]
35. G. Simon, "Probabilistic wireless network simulator," http://www.isis.vanderbilt.edu/projects/nest/prowler/.]]
36. Ying Zhang, "Routing modeling application simulation environment," http://www2.parc.com/spl/projects/era/nest/Rmase/.]]
37. Joseph Polastre, Jason Hill, and David Culler, "Versatile low power media access for wireless sensor networks," in SenSys, 2004.]]
38. Victor Shnayder, Mark Hempstead, Bor rong Chen, Geoff~Werner Allen, and Matt Welsh, "Simulating the power consumption of large-scale sensor network applications," in SenSys, 2004.]]
39. Tian He, Sudha Krishnamurthy, John~A. Stankovic, Tarek Abdelzaher, Liqian Luo, Radu Stoleru, Ting Yan, Lin Gu, Jonathan Hui, and Bruce Krogh, "Energy-efficient surveillance system using wireless sensor networks," in Mobisys, 2004.]]
40. Octav Chipara, Chenyang Lu, and Gruia-Catalin Roman, "Efficient power management based on application timing semantics for wireless sensor networks," in International Conference on Distributed Computing Systems (ICDCS), 2000.]]
41. Rong Zheng and Robin Kravets, "On-demand power management for ad hoc networks," in INFOCOM, 2003.]]
42. Tijs van Dam and Koen Langendoen, "An adaptive energy-efficient mac protocol for wireless sensor networks," in Sensys, 2003.]]

Index Terms

• Networks

  • Network types

    • Mobile networks

    • Wireless access networks

• Theory of computation

  • Design and analysis of algorithms

    • Approximation algorithms analysis

      • Routing and network design problems