A Review of Coverage and Routing for Wireless Sensor Networks
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.
[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.
[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.
@article{"International Journal of Electrical, Electronic and Communication Sciences:54323", author = "Hamid Barati and Ali Movaghar and Ali Barati and Arash Azizi Mazreah", title = "A Review of Coverage and Routing for Wireless Sensor Networks", 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.", volume = "2", number = "1", pages = "70-7", }
