Design and optimization of distributed sensing coverage in wireless sensor networks

ABSTRACT

For many sensor network applications, such as military surveillance, it is necessary to provide full sensing coverage to a security-sensitive area while, at the same time, minimizing energy consumption and extending system lifetime by leveraging the redundant deployment of sensor nodes. In this paper, we propose a surveillance service for sensor networks based on a distributed energy-efficient sensing coverage protocol. In the protocol, each node is able to dynamically decide a schedule for itself to guarantee a certain degree-of-coverage (DOC) with average energy consumption inversely proportional to the node density. Several optimizations and extensions are proposed to enhance the basic design with a better load-balance feature and a longer network lifetime. We consider and address the impact of the target size and the unbalanced initial energy capacity of individual nodes to the network lifetime. Several practical issues such as the localization error, irregular sensing range, and unreliable communication links are addressed as well. Simulation shows that our protocol extends system lift-time significantly with low energy consumption. It outperforms other state-of-the-art schemes by as much as 50% reduction in energy consumption and as much as 130% increase in the half-life of the network.

REFERENCES

• 1: Ahn, G.-S., Campbell, A. T., Veres, A., and Sun, L.-H. 2002. SWAN: Service differentiation in stateless wireless ad hoc networks. In IEEE INFOCOM.
• 2: Alt, H., Hsu, D., and Snoeyink, J. 1995. Computing the largest inscribed isothetic rectangle. In Proceeding of 7th Canadian Conference on Computational Geometry 67--72.
• 3: Bhatnagar, S., Deb, B. R., and Nath, B. 2001. Service differentiation in sensor networks. In International Symposium on Wireless Personal Multimedia Communications.
• 4: Sagnik Bhattacharya , Hyung Kim , Shashi Prabh , Tarek Abdelzaher, Energy-conserving data placement and asynchronous multicast in wireless sensor networks, Proceedings of the 1st international conference on Mobile systems, applications and services, p.173-185, May 05-08, 2003, San Francisco, California [doi>10.1145/1066116.1066120]
• 5: Cao, Q., Yan, T., Stankovic, J. A., and Abdelzaher, T. F. 2005. Analysis of target detection performance for wireless sensor networks. In International Conference on Distributed Computing in Sensor Networks (DCOSS).
• 6: Cerpa, A. and Estrin, D. 2002. ASCENT: Adaptive self-configuring sensor networks topologies. In Proceedings of the IEEE Computer and Communications Societies (INFOCOM).
• 7: 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]
• 8: CrossBow Technology, Inc. CrossBow Technology, Inc. Available at http://www.xbow.com/Products/Product_pdf_files/wireless_pdf/6020-0042-0%1_A_MICA2.pdf.
• 9: Karen Daniels , Victor Milenkovic , Dan Roth, Finding the largest area axis-parallel rectangle in a polygon, Computational Geometry: Theory and Applications, v.7 n.1-2, p.125-148, Jan. 1997 [doi>10.1016/0925-7721(95)00041-0]
• 10: Jeremy Elson , Lewis Girod , Deborah Estrin, Fine-grained network time synchronization using reference broadcasts, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060304]
• 11: Radio-Triggered Wake-Up Capability for Sensor Networks, Proceedings of the 10th IEEE Real-Time and Embedded Technology and Applications Symposium, p.27, May 25-28, 2004
• 12: Chao Gui , Prasant Mohapatra, Power conservation and quality of surveillance in target tracking sensor networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023734]
• 13: Guo, C., Zhong, L. C., and Rabaey, J. M. 2001. Low power distributed MAC for ad hoc sensor radio networks. In IEEE GlobeCom.
• 14: Tian He , Brian M. Blum , John A. Stankovic , Tarek Abdelzaher, AIDA: Adaptive application-independent data aggregation in wireless sensor networks, ACM Transactions on Embedded Computing Systems (TECS), v.3 n.2, p.426-457, May 2004 [doi>10.1145/993396.993406]
• 15: Tian He , Chengdu Huang , Brian M. Blum , John A. Stankovic , Tarek Abdelzaher, Range-free localization schemes for large scale sensor networks, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938995]
• 16: Tian He , Sudha Krishnamurthy , John A. Stankovic , Tarek Abdelzaher , Liqian Luo , Radu Stoleru , Ting Yan , Lin Gu , Jonathan Hui , Bruce Krogh, Energy-efficient surveillance system using 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.990096]
• 17: Tian He , John A. Stankovic , Chenyang Lu , Tarek Abdelzaher, SPEED: A Stateless Protocol for Real-Time Communication in Sensor Networks, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.46, May 19-22, 2003
• 18: He, T., Vicaire, P., Yan, T., Cao, Q., Zhou, G., Gu, L., Luo, L., Stoleru, R., Stankovic, J. A., and Abdelzaher, T. 2006. Achieving long-term surveillance in VigilNet. In IEEE Infocom.
• 19: 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
• 20: Chih-fan Hsin , Mingyan Liu, Network coverage using low duty-cycled sensors: random & coordinated sleep algorithms, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984685]
• 21: H.Takagi and L.Kleinrock. 1984. Optimal transmission ranges for randomly distributed packet radio terminals. IEEE Trans. Commun. 32, 3.
• 22: Chalermek Intanagonwiwat , Deborah Estrin , Ramesh Govindan , John Heidemann, Impact of Network Density on Data Aggregation in Wireless Sensor Networks, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.457, July 02-05, 2002
• 23: Kirkpatrick, D. and Snoeyink, J. 1995. Tentative prune-and-search for computing fixed-points with applications to geometric computation. Fundamental Informatic. 353--370.
• 24: Krishnamachari, B., Estrin, D., and Wicker, S. 2002. Impact of data aggregation in wireless sensor networks. In Proceedings of the International Workshop on Distributed Event-Based Systems.
• 25: Chenyang Lu , Brian M. Blum , Tarek F. Abdelzaher , John A. Stankovic , Tian He, RAP: A Real-Time Communication Architecture for Large-Scale Wireless Sensor Networks, Proceedings of the Eighth IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS'02), p.55, September 25-27, 2002
• 26: Min, R., Bhardwaj, M., Cho, S.-H., Sinha, A., Shih, E., Wang, A., and Chandrakasan, A. 2000. An architecture for a power-aware distributed microsensor node. In IEEE Workshop on Signal Processing Systems.
• 27: Ramanathan, R. and Rosales-Hain, R. 2000. Topology control of multihop wireless networks using transmit power adjustment. In IEEE INFOCOM.
• 28: Shansi Ren , Qun Li , Haining Wang , Xin Chen , Xiaodong Zhang, A study on object tracking quality under probabilistic coverage in sensor networks, ACM SIGMOBILE Mobile Computing and Communications Review, v.9 n.1, January 2005 [doi>10.1145/1055959.1055971]
• 29: Robert Szewczyk , Alan Mainwaring , Joseph Polastre , John Anderson , David Culler, An analysis of a large scale habitat monitoring application, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031521]
• 30: Tian, D. and Georganas, N. 2003. A node scheduling scheme for energy conservation in large wireless sensor networks. Wireless Comm. Mobile Comput. J. 3, 2, 271--290.
• 31: Gilman Tolle , Joseph Polastre , Robert Szewczyk , David Culler , Neil Turner , Kevin Tu , Stephen Burgess , Todd Dawson , Phil Buonadonna , David Gay , Wei Hong, A macroscope in the redwoods, Proceedings of the 3rd international conference on Embedded networked sensor systems, November 02-04, 2005, San Diego, California, USA [doi>10.1145/1098918.1098925]
• 32: Williams, R. 1979. Geometrical foundation of natural structure: A source book of design. Dover, New York.
• 33: Guoliang Xing , Chenyang Lu , Robert Pless , Qingfeng Huang, Impact of Sensing Coverage on Greedy Geographic Routing Algorithms, IEEE Transactions on Parallel and Distributed Systems, v.17 n.4, p.348-360, April 2006 [doi>10.1109/TPDS.2006.48]
• 34: Guoliang Xing , Chenyang Lu , Robert Pless , Joseph A. O'Sullivan, Co-Grid: an efficient coverage maintenance protocol for distributed sensor networks, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984683]
• 35: Guoliang Xing , Xiaorui Wang , Yuanfang Zhang , Chenyang Lu , Robert Pless , Christopher Gill, Integrated coverage and connectivity configuration for energy conservation in sensor networks, ACM Transactions on Sensor Networks (TOSN), v.1 n.1, p.36-72, August 2005 [doi>10.1145/1077391.1077394]
• 36: 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]
• 37: 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]
• 38: Xue, Y. and Li, B. 2001. A location-aided power-aware routing protocol in mobile ad hoc networks. In IEEE GlobeCom.
• 39: Fan Ye , Gary Zhong , Jesse Cheng , Songwu Lu , Lixia Zhang, PEAS: A Robust Energy Conserving Protocol for Long-lived Sensor Networks, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.28, May 19-22, 2003
• 40: Ye, F., Zhong, G., Lu, S., and Zhang, L. 2002. Energy efficient robust sensing coverage in large sensor networks. Tech. Rept., UCLA.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General

General Terms:
Algorithms, Design, Performance

Keywords:
Sensor networks, energy conservation, sensing coverage