A Review of Coverage and Routing for Wireless Sensor Networks

Authors: Hamid Barati, Ali Movaghar, Ali Barati, Arash Azizi Mazreah

Abstract:

The special constraints of sensor networks impose a number of technical challenges for employing them. In this review, we study the issues and existing protocols in three areas: coverage and routing. We present two types of coverage problems: to determine the minimum number of sensor nodes that need to perform active sensing in order to monitor a certain area; and to decide the quality of service that can be provided by a given sensor network. While most routing protocols in sensor networks are data-centric, there are other types of routing protocols as well, such as hierarchical, location-based, and QoS-aware. We describe and compare several protocols in each group. We present several multipath routing protocols and single-path with local repair routing protocols, which are proposed for recovering from sensor node crashes. We also discuss some transport layer schemes for reliable data transmission in lossy wireless channels.

Keywords: Sensor networks, Coverage, Routing, Robustness.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1060655

References:

[1] Limin Wang," Survey on Sensor Networks", Department of Computer Science and Engineering Michigan State University.
[2] Kemal Akkaya and Mohamed Younis, "A Survey on Routing Protocols for Wireless Sensor Networks".Department of Computer Science and Electrical Engineering University of Maryland, Baltimore County.
[3] Crossbow Technology, Inc. Mote In-Network Programming User Reference Version 20030315, 2003.
[4] Stefan Dulman, Tim Nieberg, Paul Havinga, and Pieter Hartel. Multipath routing for data dissemination in energy e┬▒cient sensor networks. Technical Report TR-CTTT-02-20, Center of Telematics and Information Technology, University of Twente, The Netherlands, July 2002.
[5] A. Arora et. al. A Line in the sand: a wireless sensor network for target detection, classification, and tracking. Technical Report OSU-CISRC- 12/03-TR71, The Ohio State University, December 2003.
[6] Sally Floyd, Van Jacobson, Ching-Gung Liu, Steven McCanne, and Lixia Zhang. A reliable multicast framework for light-weight sessions and application level framing. IEEE/ACMTransactions on Networking, 5(6):784{803, December 1997.
[7] D. Ganesan, R. Govindan, S. Shenker, and D. Estrin. Highly-resilient, energy-efficient multipath routing in wireless sensor networks. Mobile Computing and Communications Review, 1(2), October 2002.
[8] Tian He, John A. Stankovic, Chenyang Lu, and Tarek F. Abdelzaher. SPEED: a real-time routing protocol for sensor networks. Technical Report CS-2002-09, University of Virginia, March 2002.
[9] Wendi Beth Heinzelman. Application-Specific Protocol Architectures for Wireless Networks. PhD thesis, Massachusetts Institute of Technology, June 2000.
[10] Wendi Rabiner Heinzelman, Anantha Chandrakasan, and Hari Balakrishnan. Energy-efficient communication protocol for wireless microsensor networks. In Proceedings of the 33rd HawaiiInternational Conference on System Sciences (HICSS), Maui, Hawaii, USA, January 2000.
[11] Wendi Rabiner Heinzelman, Joanna Kulik, and Hari Balakrishnan. Adaptive protocols for information dissemination in wireless sensor networks. In Proceedings of the Fifth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom), pages 174{185, Seattle, Washington, USA, August 1999.
[12] J. Hill and D. E. Culler. Mica: A wirleess platform for deeply embedded networks. IEEE, 2002.
[13] Jason Hill, Robert Szewczyk, Alec Woo, Seth Hollar, David Culler, and Kristofer Pister. System architecture directions for networked sensors. In Proceedings of The Ninth International Conference on Architectural Support for Programming Language and Operating Systems(ASPLOSIX), pages 93{104, November 2000.
[14] Chalermek Intanagonwiwat, Ramesh Govindan, and Deborah Estrin. Directed Diffusion: a scalable and robust communication paradigm for sensor networks. In Proceedings of the Sixth Annual International Conference on Mobile Computing and Networking, pages 56{67, Boston, Massachusetts, USA, August 2000.
[15] Chris Karlof, Yangping Li, and Joseph Polastre. ARRIVE: algorithm for robust routing in volatile environments. Technical Report UCB CSD-03- 1233, University of California, Berlekey, March 2003.
[16] Brad Karp and H. T. Kung. GPSR: greedy perimeter stateless routing for wireless networks. In Proceedings of International Conference on Mobile Computing and Networking (Mobicom), Boston, Massachusetts, USA, August 2000.
[17] Bhaskar Krishnamachari, Yasser Mourtada, and Stephen Wicher. The energy-robustness tradeoff for routing in wireless sensor networks. Technical Report Autonomous Networks Research Group (ANRG) Technical Report TR02-001, University of Southern California, September 2002.
[18] Sandeep S. Kulkarni and Karun N. Biyani. Correctness of componentbased adaptation.Proceedings of the 7th International Symposium on Component-Based Software Engineering(CBSE), 3054, 2004.
[19] Sandeep S. Kulkarni, Karun N. Biyani, and Umamaheswaran Arumugam. Composing distributed fault-tolerance components. Proceedings of the International Conference on Depend-able systems and Networks (DSN), Supplemental Volume, Workshop on Principles of Dependable Systems, pages W127{W136, June 2003.
[20] Sandeep S. Kulkarni and Limin Wang. Mnp: Multihop network reprogramming service for sensor networks. Technical Report MSUCSE- 04-19, Michigan State University, May 2004.
[21] Sung-Ju Lee, Elizabeth M. Belding-Royer, and Charles E. Perkins. Scalability study of the ad hoc on-demand distance vector routing protocol. International Journal of Network Management, 13:97{114, March/April 2003.
[22] Philip Levis, Neil Patel, Scott Shenker, and David Culler. Trickle: a selfregulating algorithm for code propagation and maintenance in wireless sensor networks. Technical report, University of California at Berkeley, 2003.
[23] Stephanie Lindsey and Cauligi S. Raghavendra. PEGASIS: powere┬▒ cient gathering in sensor information systems. In Proceedings of IEEE Aerospace Conference, March 2002.
[24] Ching-Gung Liu, Deborah Estrin, Scott Shenker, and Lixia Zhang. Timer adjustment in SRM. Technical Report USC 97-656, Univ. Southern California, July 1997.
[25] Haiyun Luo, Fan Ye, Jerry Cheng, Songwu Lu, and Lixia Zhang. TTDD: a two-tier data dissemination model for large-scale wireless sensor networks. In Proceedings of International Conference on Mobile Computing and Networking (MobiCom), Atlanta, Georgia, USA, September 2002.
[26] A. Manjeshwar and D. P. Agrawal. TEEN: a routing protocol for enhanced efficiency in wireless sensor networks. In Proceedings of the 1st International Workshop on Parallel and Distributed Computing Issues in Wireless Networks and Mobile Computing, in conjuntion with 2001 IPDPS, Hyatt Regency, San Francisco, USA, April 2001.
[27] Seapahn Meguerdichian, Farinaz Koushanfar, Miodrag Potkonjak, and Mina B. Srivastava. Coverage problems in wireless ad-hoc sensor networks. In Proceedings of INFOCOM, pages 1380{1387, Anchorage, Alaska, USA, April 2001.
[28] Christos Papadopoulos, Guru Parulkar, and George Varghese. An error control scheme for large-scale multicast applications. In Proceedings of INFOCOM, San Francisco, USA, March-April 1998.
[29] Charles E. Perkins and Elizabeth M. Royer. Ad hoc on-demand distance vector routing.In Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications (WMCSA), pages 90{100, New Orleans, Louisiana, USA, February 1999.
[30] Rahul C. Shah and Jan M. Rabaey. Energy aware routing for low energy ad hoc sensor networks. In Proceedings of IEEE Wireless Communications and Networking Conference (WCNC), Orlando, FL, USA, March 2002.
[31] Katayoun Sohrabi, Jay Gao, Vishal Ailawadhi, and Gregory J. Pottie. Protocols for self-organization of a wireless sensor network. IEEE Personal Communications, pages 16{27,October 2000.
[32] Fred Stann and John Heidemann. RMST: reliable data transport in sensor networks. In Proceedings of The First International Workshop on Sensor Net Protocols and Applications(SNPA'03), Anchorage, AK, USA, May 2003.
[33] Di Tian and Nicolas D. Georganas. A coverage-preserving node scheduling scheme for large wireless sensor networks. In Proceedings of the First ACM International Workshop on Wireless Sensor Networks and Applications (WSNA), Atlanta, Georgia, USA, September 2002.
[34] Di Tian and Nicolas D. Georganas. Low-cost, reliable data delivery in large wireless sensor networks. Technical report, University of Ottawa, 2003.
[35] Chieh-Yih Wan, Andrew T. Campbell, and Lakshman Krishnamurthy. PSFQ: a reliable trans-port protocol for wireless sensor networks. In Wireless Sensor Networks and Applications (WSNA), Atlanta, Georgia, USA, September 2002.
[36] Xiaorui Wang, Guoliang Xing, Yuanfang Zhang, Chenyang Lu, Robert Pless, and Christopher Gill. Integrated coverage and connectivity con¯guration in wireless sensor networks. In Proceedings of the First ACM Conference on Embedded Networked Sensor Systems (SENSYS),Los Angeles, CA, USA, November.