Steady and fair rate allocation for rechargeable sensors in perpetual sensor networks

ABSTRACT

Renewable energy enables sensor networks with the capability to recharge and provide perpetual data services. Due to low recharging rates and the dynamics of renewable energy such as solar and wind power, providing services without interruptions caused by battery runouts is non-trivial. Most environment monitoring applications require data collection from all nodes at a steady rate. The objective of this paper is to design a solution for fair and high throughput data extraction from all nodes in presence of renewable energy sources. Specifically, we seek to compute the lexicographically maximum data collection rate for each node, such that no node will ever run out of energy. We propose a centralized algorithm and an asynchronous distributed algorithm that can compute the optimal lexicographic rate assignment for all nodes. The centralized algorithm jointly computes the optimal data collection rate for all nodes along with the flows on each link, while the distributed algorithm computes the optimal rate when the routes are pre-determined. We prove the optimality for both the centralized and the distributed algorithms, and use a testbed with 155 sensor nodes to validate the distributed algorithm.

REFERENCES

• 1: M. Lukac, V. Naik, I. Stubailo, A. Husker, and D. Estrin, "In Vivo Characterization of a Wide area 802.11b Wireless Seismic Array," Center for Embedded Network Sensing. Papers. Paper 100., 2007. {Online}. Available: http://repositories.cdlib.org/cens/wps/100
• 2: Ning Xu , Sumit Rangwala , Krishna Kant Chintalapudi , Deepak Ganesan , Alan Broad , Ramesh Govindan , Deborah Estrin, A wireless sensor network For structural monitoring, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031498]
• 3: Sukun Kim , Shamim Pakzad , David Culler , James Demmel , Gregory Fenves , Steven Glaser , Martin Turon, Health monitoring of civil infrastructures using wireless sensor networks, Proceedings of the 6th international conference on Information processing in sensor networks, April 25-27, 2007, Cambridge, Massachusetts, USA [doi>10.1145/1236360.1236395]
• 4: T. E. O. Systems, "AMARSS and NIMS - Networked Minirhizotron and Arrayed Rhizosphere Sensing Systems." {Online}. Available: http://research.cens.ucla.edu/projects/2007/Terrestrial/AMARSS-NIMS/AMA%RSS
• 5: K. Martinez, R. Ong, and J. Hart, "Glacsweb: a Sensor Network for Hostile Environments," in Proc. of The First IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks, Santa Clara, CA, 2004.
• 6: J. Hsu, A. Kansal, J. Friedman, V. Raghunathan, and M. Srivastava, "Energy Harvesting Support for Sensor Network," in Proc. of IEEE IPSN Demo, 2005. {Online}. Available: http://www.ee.ucla.edu/ mbs/ipsn05/demo/18_JHsu.pdf
• 7: Vijay Raghunathan , Aman Kansal , Jason Hsu , Jonathan Friedman , Mani Srivastava, Design considerations for solar energy harvesting wireless embedded systems, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 8: C. Park and P. H. Chou, "AmbiMax: Autonomous Energy Harvesting Platform for Multi-Supply Wireless Sensor Nodes," in SECON, Sept. 2006, pp. 168--177.
• 9: Ingo Stark, Invited Talk: Thermal Energy Harvesting with Thermo Life, Proceedings of the International Workshop on Wearable and Implantable Body Sensor Networks, p.19-22, April 03-05, 2006 [doi>10.1109/BSN.2006.37]
• 10: M. P. Release, "MicroStrain Wins Navy Contract for Self Powered Wireless Sensor Networks," http://www.microstrain.com/news/article-29.aspx, 2003.
• 11: Scott Meninger , Rajeevan Amirtharajah , Anantha P. Chandrakasan , Jeffrey H. Lang , Jose Oscar Mur-Miranda, Vibration-to-electric energy conversion, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.9 n.1, p.64-77, Feb. 2001 [doi>10.1109/92.920820]
• 12: Crossbow, "Crossbow," http://www.xbow.com.
• 13: Shigang Chen , Yuguang Fang , Ye Xia, Lexicographic Maxmin Fairness for Data Collection in Wireless Sensor Networks, IEEE Transactions on Mobile Computing, v.6 n.7, p.762-776, July 2007 [doi>10.1109/TMC.2007.1039]
• 14: A. Charny, D. D. Clark, and R. Jain, "Congestion Control With Explicit Rate Indication," in IEEE International Conference on Communication, vol. 3, June 1995, pp. 1954--1963.
• 15: "MoteLab," http://motelab.eecs.harvard.edu/.
• 16: "National Climatic Data Center." {Online}. Available: http://www.ncdc.noaa.gov/oa/climate/uscrn
• 17: Jie Gao , Li Zhang, Load-Balanced Short-Path Routing in Wireless Networks, IEEE Transactions on Parallel and Distributed Systems, v.17 n.4, p.377-388, April 2006 [doi>10.1109/TPDS.2006.49]
• 18: Xiaofan Jiang , Joseph Polastre , David Culler, Perpetual environmentally powered sensor networks, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 19: Prabal Dutta , Jonathan Hui , Jaein Jeong , Sukun Kim , Cory Sharp , Jay Taneja , Gilman Tolle , Kamin Whitehouse , David Culler, Trio: enabling sustainable and scalable outdoor wireless sensor network deployments, Proceedings of the 5th international conference on Information processing in sensor networks, April 19-21, 2006, Nashville, Tennessee, USA [doi>10.1145/1127777.1127839]
• 20: L. Selavo , A. Wood , Q. Cao , T. Sookoor , H. Liu , A. Srinivasan , Y. Wu , W. Kang , J. Stankovic , D. Young , J. Porter, LUSTER: wireless sensor network for environmental research, Proceedings of the 5th international conference on Embedded networked sensor systems, November 06-09, 2007, Sydney, Australia [doi>10.1145/1322263.1322274]
• 21: Pei Zhang , Christopher M. Sadler , Stephen A. Lyon , Margaret Martonosi, Hardware design experiences in ZebraNet, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031522]
• 22: Thiemo Voigt , Hartmut Ritter , Jochen Schiller, Utilizing Solar Power in Wireless Sensor Networks, Proceedings of the 28th Annual IEEE International Conference on Local Computer Networks, p.416, October 20-24, 2003
• 23: M. Rahimi, H. Shah, G. S. Sukhatime, J. Heideman, and D. Estrin, "Studying the Feasibility of Energy Harvesting in a Mobile Sensor Network," in IEEE International Conference on Robotics and Automation, vol. 1, Sept. 2003, pp. 19--24.
• 24: Aman Kansal , Mani B. Srivastava, An environmental energy harvesting framework for sensor networks, Proceedings of the 2003 international symposium on Low power electronics and design, August 25-27, 2003, Seoul, Korea [doi>10.1145/871506.871624]
• 25: Aman Kansal , Dunny Potter , Mani B. Srivastava, Performance aware tasking for environmentally powered sensor networks, ACM SIGMETRICS Performance Evaluation Review, v.32 n.1, June 2004
• 26: Aman Kansal , Jason Hsu , Sadaf Zahedi , Mani B. Srivastava, Power management in energy harvesting sensor networks, ACM Transactions on Embedded Computing Systems (TECS), v.6 n.4, p.32-es, September 2007 [doi>10.1145/1274858.1274870]
• 27: K. Kar, A. Krishnamurthy, and N. Jaggi, "Dynamic Node Activation in Networks of Rechargeable Sensors," in INFOCOM, vol. 3, Mar. 2005, pp. 1997--2007.
• 28: C. M. Vigorito, D. Ganesan, and A. G. Barto, "Adaptive Control of Duty Cycling in Energy-Harvesting Wireless Sensor Networks," in The 4th Annual IEEE Communications Society Conference on Sensor, Mesh, and Ad Hoc Communications and Networks, June 2007, pp. 21--30.
• 29: Y. Thomas Hou , Shivendra S. Panwar , Henry H. -Y. Tzeng, On Generalized Max-Min Rate Allocation and Distributed Convergence Algorithm for Packet Networks, IEEE Transactions on Parallel and Distributed Systems, v.15 n.5, p.401-416, May 2004 [doi>10.1109/TPDS.2004.1278098]
• 30: Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 31: Sumit Rangwala , Ramakrishna Gummadi , Ramesh Govindan , Konstantinos Psounis, Interference-aware fair rate control in wireless sensor networks, ACM SIGCOMM Computer Communication Review, v.36 n.4, October 2006

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.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

General Terms:
Algorithms, Design

Keywords:
rate assignment, rechargeable sensor networks