Review
Coverage and connectivity issues in wireless sensor networks: A survey

https://doi.org/10.1016/j.pmcj.2008.02.001Get rights and content

Abstract

Sensing coverage and network connectivity are two of the most fundamental problems in wireless sensor networks. Finding an optimal node deployment strategy that would minimize cost, reduce computation and communication overhead, be resilient to node failures, and provide a high degree of coverage with network connectivity is extremely challenging. Coverage and connectivity together can be treated as a measure of quality of service in a sensor network; it tells us how well each point in the region is covered and how accurate is the information gathered by the nodes. Therefore, maximizing coverage as well as maintaining network connectivity using the resource constrained nodes is a non-trivial problem. In this survey article, we present and compare several state-of-the-art algorithms and techniques that aim to address this coverage–connectivity issue.

Introduction

Wireless sensor networks (WSN) [53], [52] have inspired tremendous research interest in recent years. Advances in wireless communication and Micro Electro Mechanical Systems (MEMS) have enabled the development of low-cost, low-power, multi-functional, tiny sensor nodes which can sense the environment, perform data processing and communicate with each other untethered over short distances. A typical large-scale WSN consists of thousands of sensor nodes deployed either randomly or according to some predefined statistical distribution over a geographical region of interest. A sensor node by itself has severe resource constraints, such as limited memory, battery power, signal processing, computation and communication capabilities; hence it can sense only a small portion of the environment. However, a group of sensors collaborating with each other can accomplish a much bigger task efficiently. They can sense and collect raw data from the environment, do local processing, possibly communicate with each other in an optimal fashion to perform aggregation [36], and then route the aggregated data to sinks or base stations that can make application specific decisions and link to the outside world via the Internet or satellites. One of the primary advantages of deploying a wireless sensor network is its low-deployment cost and freedom from having a messy wired communication backbone, which is often inconvenient and economically infeasible.

A wide range of potential applications have been envisioned using WSNs [1], such as temperature and environmental conditions monitoring, wildlife habitat monitoring, security surveillance in military and battle-fields, smart homes and offices, improved health care, industrial diagnosis, etc. For instance, a sensor network could be deployed in a remote island for monitoring wildlife habitat and animal behavior [42], or near the crater of a volcano to measure temperature, pressure, and seismic activities [3]. In many of these applications the environment could be hostile and manual placement might not be possible. In these situations nodes are expected to be deployed randomly or sprinkled from airplanes and will remain unattended for months or years without any battery replenishment.

One of the important criteria for being able to deploy an efficient sensor network is to find optimal node deployment strategies and efficient topology control techniques [55], [54]. Nodes can either be placed manually at predetermined locations or dropped from an aircraft. However, since the nodes are randomly scattered in most practical situations it is difficult to find a random deployment strategy that minimizes all the desirable metrics simultaneously, such as, sufficient coverage and connectivity, low-computation and communication overhead. The notion of area coverage can be considered as a measure of the quality of service (QoS) in a sensor network, for it means how well each point in the sensing field is covered by the sensors. Once the nodes are deployed in the monitoring region, they form a communication network that can dynamically change over time depending on node mobility, residual battery power, static and moving obstacles, presence of noise, etc. The network can be viewed as a graph, where sensor nodes act as vertices and a communication link, typically a radio frequency channel, between two nodes represents an edge.

In this survey article, we investigate the sensing coverage and network connectivity problem. In Section 2, we introduce the notion of coverage and connectivity, and discuss their importance with respect to several applications. We also do a broad classification of the existing approaches. Section 3 describes the different models related to sensing, communication, coverage, and network connectivity. In Section 4, we describe the coverage algorithms based on exposure paths. In particular, the concepts of minimal and maximal exposure paths; breach paths and support paths; and their significance in intrusion detection are described here. In Section 5, we discuss various deployment schemes that exploit node mobility to improve the quality of coverage. The notion of dynamic coverage is introduced, and algorithms related to potential field and virtual forces that relocate nodes from their initial random deployment locations to the locations of coverage holes are presented. Section 6 discusses various techniques that consider the coverage–connectivity problem under an integrated framework. Here, several sleep scheduling and pattern-based schemes are described that are applicable to both two-dimensional and three-dimensional networks. In Section 7, we summarize our contributions, and finally in Section 8 we discuss research challenges and open problems in this area.

Section snippets

Coverage and connectivity

Efficient resource management and providing reliable QoS are two of the most important requirements in sensor networks. However, due to severe resource constraints and hostile environmental conditions, it is non-trivial to design efficient node deployment strategies that would minimize cost, reduce computation and communication overhead, provide a high degree of coverage, and maintain a globally-connected-network simultaneously. Challenges also arise because of the fact that most often

Preliminaries

In order to understand a physical system in a scientific way we resort to models. A model is a description of the physical system that captures its important behaviors, while abstracting away the gory details that complicate analysis without providing additional insights. The fundamental principle behind modeling is that it should be as simple as possible, but no simpler that it becomes unrealistic. In this section, we define several models that are used in sensor networks, e.g., sensing

Coverage based on exposure

Approaches to solve the coverage problem using the notion of exposure is basically a combinatorial optimization problem formulation. Two kinds of viewpoints exist in formulating the coverage problem: (1) worst-case coverage, and (2) best-case coverage.

In the worst-case coverage, the problem is formulated with the goal to find a path through the sensing region such that, an object moving along that path has the least observability by the nodes, and thus, the probability of detecting the moving

Coverage exploiting mobility

The second category consists of coverage schemes that exploit mobility to relocate nodes to optimal locations to maximize coverage. In some situations where terrain knowledge is available a priori, nodes could be placed deterministically, while in others, due to the large scale of the network or inaccessibility of the terrain, resorting to random deployment is perhaps the only option. However, as it turns out, random deployment often does not guarantee full coverage, resulting in accumulation

Integrated coverage and connectivity

Our discussion so far has primarily dealt with algorithms that guarantee optimal coverage of a sensing field. However, for a sensor network to operate successfully the nodes must also form a connected-network so that the sensed data can be transmitted in multi-hop to other nodes and possibly to a base station where intelligent decisions can be made. Therefore, it is equally important for a coverage algorithm to ensure network connectivity.

One of the fundamental results concerning integrated

Discussions

We have seen that one of the fundamental issues that arises in wireless sensor networks is the coverage–connectivity problem. Due to the large variety of applications, the notion of coverage has been interpreted in many different ways. However, in general, coverage can be considered as a measure of quality of service of a sensor network, because better coverage of a region leads to better measurements of the underlying physical phenomenon. This service facilitated by a better coverage is

Three-dimensional networks

In Section 6.1.2, we discussed the coverage–connectivity problem in three-dimensional networks. With the growing research interest in underwater sensor networks, a variety of applications, such as oceanographic data collection, pollution monitoring, and offshore explorations pose many challenges to the coverage–connectivity problem. Since the density of nodes to completely cover a three-dimensional region is prohibitively higher than the corresponding two-dimensional case [50], sensors deployed

Acknowledgments

The authors would like to thank Professor Bhaskar Krishnamachari of the Autonomous Networks Research Group at USC for his valuable inputs. We also sincerely thank the reviewers for constructive comments, which helped us to significantly improve the technical quality and organization of the paper. The work described here is supported in part by NSF through grants IIS-0326505, CNS-0721951, CNS-0627028, CCF-0430061, and CNS-0325875. Any opinions, findings, and conclusions or recommendations

Amitabha Ghosh received his B.S. in Physics from the Indian Institute of Technology, Kharagpur in 1996, and his M.E. in Computer Science and Engineering from the Indian Institute of Science, Bangalore in 2000. Currently, he is a Ph.D. student in the Ming Hsieh Department of Electrical Engineering - Systems under Dr. Bhaskar Krishnamachari, and is a member of the Autonomous Networks Research Group. Earlier he has worked with Lucent Technologies (now Alcatel-Lucent) as a Senior Software Engineer

References (76)

  • I.F. Akyildiz et al.

    Wireless sensor networks: A survey

    Computer Networks

    (2002)
  • N. Alam, Z.J. Haas, Coverage and connectivity in three-dimensional networks, in: MobiCom ’06: Proceedings of the 12th...
  • G.W. Allen, K. Lorincz, J. Johnson, J. Lees, M. Welsh, Fidelity and yield in a volcano monitoring sensor network, in:...
  • H.M. Ammari, S.K. Das, Integrated coverage and connectivity in wireless sensor networks: A two-dimensional percolation...
  • D.L. Applegate et al.

    The Traveling Salesman Problem: A Computational Study

    (2006)
  • X. Bai, S. Kumar, D. Xuan, Z. Yun, T.H. Lai, Deploying wireless sensors to achieve both coverage and connectivity, in:...
  • N. Bisnik, A. Abouzeid, V. Isler, Stochastic event capture using mobile sensors subject to a quality metric, in:...
  • L. Booth et al.

    Covering algorithms, continuum percolation, and the geometry of wireless networks

    Annals of Applied Probability

    (2003)
  • T. Camp et al.

    A survey of mobility models for ad hoc network research

    Wireless Communications & Mobile Computing, WCMC

    Mobile Ad Hoc Networking, Research, Trends and Applications

    (2002)
  • Q. Cao, T. Abdelzaher, T. He, J. Stankovic, Towards optimal sleep scheduling in sensor networks for rare-event...
  • S. Chellappan et al.

    Deploying wireless sensor networks under limited mobility constraints

    IEEE Transactions on Mobile Computing

    (2007)
  • B. Chen, K. Jamieson, H. Balakrishnan, R. Morris, Span: An energy-efficient coordination algorithm for topology...
  • T.L. Chin, P. Ramanathan, K.K. Saluja, K.C. Wang, Exposure for collaborative detection using mobile sensor networks,...
  • W. Choi, S.K. Das, A novel framework for energy-conserving data gathering in wireless sensor networks, in: Proceedings...
  • T. Clouqueur, V. Phipatanasuphorn, P. Ramanathan, K.K. Saluja, Sensor deployment strategy for target detection, in:...
  • O. Dousse, C. Tavoularis, P. Thiran, Delay of intrusion detection in wireless sensor networks, in: Proceedings of the...
  • A. Elfes, Occupancy grids: A stochastic spatial representation for active robot perception, in: Proceedings of the 6th...
  • S. Funke et al.

    Improved approximation algorithms for connected sensor cover

    Wireless Networks

    (2007)
  • D.W. Gage, Command control for many-robot systems, in: Nineteenth Annual AUVS Technical Symposium, Reprinted in...
  • D. Ganesan, B. Krishnamachari, A. Woo, D. Culler, D. Estrin, S. Wicker, Complex behavior at scale: An experimental...
  • A. Ghosh, Estimating coverage holes and enhancing coverage in mixed sensor networks, in: Proceedings of the 29th Annual...
  • A. Ghosh, S.K. Das, Distributed connected sensor cover algorithms for lattice and random deployment of nodes in dense...
  • A. Ghosh, Y. Wang, B. Krishnamachari, Efficient distributed topology control in 3-dimensional wireless networks, in:...
  • H. Gupta et al.

    Connected sensor cover: Self-organization of sensor networks for efficient query execution

    IEEE/ACM Trans. Netw.

    (2006)
  • M. Hafeeda, M. Bagheri, Randomized k-coverage algorithms for dense sensor networks, in: Proceedings of IEEE Infocom,...
  • P. Hall

    Introduction to the Theory of Coverage Processes

    (1988)
  • N. Heo, P.K. Varshney, A distributed self-spreading algorithm for mobile wireless sensor networks, in: Proceedings of...
  • A. Howard, M. Mataric, Cover me! a self-deployment algorithm for mobile sensor networks, in: Proceedings of IEEE...
  • A. Howard et al.

    An incremental self-deployment algorithm for mobile sensor networks

    Autonomous Robots Special Issue on Intelligent Embedded Systems

    (2002)
  • A. Howard, M. Mataric, G. Sukhatme, Mobile sensor network deployment using potential fields: A distributed scalable...
  • C.F. Huang et al.

    The coverage problem in a wireless sensor network

  • C.F. Huang et al.

    The coverage problem in three-dimensional wireless sensor networks

  • C.F. Huang et al.

    Distributed protocols for ensuring both coverage and connectivity of a wireless sensor network

    ACM Transactions on Sensor Networks

    (2007)
  • R. Iyengar, K. Kar, S. Mukherjee, Low-coordination topologies for redundancy in sensor networks. in: Proceedings of the...
  • O. Khatib

    Real-time obstacle avoidance for manipulators and mobile robots

    International Journal of Robotics Research

    (1986)
  • M.M. Kokar, J.A. Tomasik, J. Weyman, Data vs. decision fusion in the category theory framework, in: Proceedings of the...
  • T. Leighton, P. Shor, Tight bounds for minimax grid matching, with applications to the average case analysis of...
  • L. Li, J.Y. Halpern, P. Bahl, Y.M. Wang, R. Wattenhofer, Analysis of a cone-based distributed topology control...
  • Cited by (437)

    View all citing articles on Scopus

    Amitabha Ghosh received his B.S. in Physics from the Indian Institute of Technology, Kharagpur in 1996, and his M.E. in Computer Science and Engineering from the Indian Institute of Science, Bangalore in 2000. Currently, he is a Ph.D. student in the Ming Hsieh Department of Electrical Engineering - Systems under Dr. Bhaskar Krishnamachari, and is a member of the Autonomous Networks Research Group. Earlier he has worked with Lucent Technologies (now Alcatel-Lucent) as a Senior Software Engineer in the area of Telecommunications (GSM, GPRS), and in Honeywell Technology Solutions Lab as a Principal Engineer in the area of wireless sensor networks and cryptography. His current research interest is on modeling, design, and analysis of algorithms for deployment, topology control, medium access control, and routing protocols in wireless sensor networks.

    Dr. Sajal K. Das is a University Distinguished Scholar Professor of Computer Science and Engineering and the Founding Director of the Center for Research in Wireless Mobility and Networking (CReWMaN) at the University of Texas at Arlington (UTA). He is also a Visiting Professor at the Indian Institute of Technology (IIT), Kanpur and IIT Guwahati; Honorary Professor of Fudan University in Shanghai and Advisory Professor of Beijing Jiaotong University, China; and Visiting Scientist at the Institute of Infocomm Research (I2R), Singapore. His current research interests include wireless sensor networks, design and modeling of smart environments, mobile and pervasive computing, resource and mobility management in wireless networks, security, mobile grid computing, biological networking, applied graph theory and game theory. He has published over 400 papers and over 35 invited book chapters in these areas. He holds five US patents in wireless networks and mobile Internet, and coauthored the books “Smart Environments: Technology, Protocols, and Applications” (Wiley, 2005) and “Mobile Agents in Distributed Computing and Networking” (Wiley, 2008). Dr. Das is a recipient of several Best Paper Awards in such conferences as EWSN’08, IEEE PerCom’06, and ACM MobiCom’99. He is also a recipient of IEEE Engineer of the Year Award (2007), UTA Academy of Distinguished Scholars Award (2006), University Award for Distinguished Record of Research (2005), College of Engineering Research Excellence Award (2003), and Outstanding Faculty Research Award in Computer Science (2001 and 2003). He is frequently invited as keynote speaker at international conferences and symposia. Dr. Das serves as the Founding Editor-in-Chief of Pervasive and Mobile Computing (PMC) journal, and Associate Editor of IEEE Transactions on Mobile Computing, ACM/Springer Wireless Networks, IEEE Transactions on Parallel and Distributed Systems, and Journal of Peer-to-Peer Networking. He is the founder of IEEE WoWMoM and co-founder of IEEE PerCom conference. He has served as General or Technical Program Chair as well as TPC member of numerous IEEE and ACM conferences. He serves on IEEE TCCC and TCPP Executive Committees.

    View full text