ReviewCoverage and connectivity issues in wireless sensor networks: A survey
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)
- 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...
- 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:...
- et al.
Covering algorithms, continuum percolation, and the geometry of wireless networks
Annals of Applied Probability
(2003) - 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...
Deploying wireless sensor networks under limited mobility constraints
IEEE Transactions on Mobile Computing
Improved approximation algorithms for connected sensor cover
Wireless Networks
Connected sensor cover: Self-organization of sensor networks for efficient query execution
IEEE/ACM Trans. Netw.
Introduction to the Theory of Coverage Processes
An incremental self-deployment algorithm for mobile sensor networks
Autonomous Robots Special Issue on Intelligent Embedded Systems
The coverage problem in a wireless sensor network
The coverage problem in three-dimensional wireless sensor networks
Distributed protocols for ensuring both coverage and connectivity of a wireless sensor network
ACM Transactions on Sensor Networks
Real-time obstacle avoidance for manipulators and mobile robots
International Journal of Robotics Research
Cited by (437)
An efficient method for maximal area coverage in the context of a hierarchical controller for multiple unmanned aerial vehicles
2023, European Journal of ControlResource allocation for target tracking in multiple radar architectures over lossy networks
2023, Signal ProcessingA novel adaptive deployment method for the single-target tracking of mobile wireless sensor networks
2023, Reliability Engineering and System SafetyForecasting fine-grained sensing coverage in opportunistic vehicular sensing
2023, Computers, Environment and Urban SystemsA new and reliable intelligent model for deployment of sensor nodes for IoT applications
2022, Computers and Electrical Engineering
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.