Best and worst-case coverage problems for arbitrary paths in wireless sensor networks

The path-based coverage of a wireless sensor network is to analyze how well the network covers the sensor field in terms of paths. Known results prior to this research, however, considered only a single source–destination pair and thus do not provide a global outlook at the given network but a local feature for the given source–destination pair. In this paper, we propose a new coverage measure of sensor networks that considers arbitrary source–destination pairs. Our novel measure naturally extends the previous concept of the best and the worst-case path-based coverage to evaluate the coverage of a given network from a global point of view, taking arbitrary paths into account.In terms of the present coverage measure, we pose the evaluation and the deployment problems for give a network; the former is to evaluate the new coverage measure of a given sensor network, and the latter is to find an optimal placement of k additional sensor nodes to improve the coverage for a given positive integer k. We present several algorithms that are either centralized or localized that solve the problems with theoretical proofs and simulation results, thus showing that our algorithms are efficient and easy to implement in practice while the quality of their outputs is guaranteed by formal proofs. For the purpose, we show an interesting relation between the present coverage measure and a certain quantity of a point set, called the bottleneck, which has been relatively well studied in other disciplines such as computational geometry and operations research.     

An energy-efficient optimization deployment scheme for wireless sensor networks

Most of the current deployment schemes for Wireless Sensor Networks (WSNs) do not take the network coverage and connectivity features into account, as well as the energy consumption. This paper introduces topology control into the optimization deployment scheme, establishes the mathematical model with the minimum sum of the sensing radius of each sensors, and uses the genetic algorithm to solve the model to get the optimal coverage solution. In the optimal coverage deployment, the communication and channel allocation are further studied. Then the energy consumption model of the coverage scheme is built to analyze the performance of the scheme. Finally, the scheme is simulated through the network simulator NS-2. The results show the scheme can not only save 36% energy averagely, but also achieve 99.8% coverage rate under the condition of 45 sensors being deployed after 80 iterations. Besides, the scheme can reduce the five times interference among channels.     

Connected sensor cover for area information coverage in wireless sensor networks

Coverage is an important issue in wireless sensor networks (WSNs) and is often used to measure how well a sensor field is monitored by the deployed sensors. If the area covered by a sensor can also be covered by some other sensors, this sensor can go into an energy‐saving sleep state without sacrificing the coverage requirement. In this paper, we study the problem of how to select active sensors with the constraints that the selected active sensors can provide complete field coverage and are completely connected. We propose to use the notion of information coverage, which is based on estimation theory to exploit the collaborative nature of WSNs, instead of using the conventional definition of coverage. Owing to the use of information coverage, a point that is not within the sensing disk of any sensor can still be considered to be covered without loss of estimation reliability. We propose a heuristic to approximately solve our problem. The basic idea is to grow a connected sensor tree to maximize the profit from the covered points of the selected sensors in each step. Simulations are used to validate the effectiveness of the proposed algorithm and the results illustrate that the number of active sensors to provide area coverage can be greatly reduced by using the notion of information coverage compared with that by using the conventional definition of coverage. Copyright © 2008 John Wiley & Sons, Ltd.     

A lightweight intrusion detection framework for wireless sensor networks

In recent years, Wireless Sensor Networks (WSNs) have demonstrated successful applications for both civil and military tasks. However, sensor networks are susceptible to multiple types of attacks because they are randomly deployed in open and unprotected environments. It is necessary to utilize effective mechanisms to protect sensor networks against multiple types of attacks on routing protocols. In this paper, we propose a lightweight intrusion detection framework integrated for clustered sensor networks. Furthermore, we provide algorithms to minimize the triggered intrusion modules in clustered WSNs by using an over‐hearing mechanism to reduce the sending alert packets. Our scheme can prevent most routing attacks on sensor networks. In in‐depth simulation, the proposed scheme shows less energy consumption in intrusion detection than other schemes. Copyright © 2009 John Wiley & Sons, Ltd.     

QoS evaluation of energy-efficient ML-MAC protocol for wireless sensor networks

Power management is an important issue in wireless sensor networks (WSNs) because wireless sensor nodes are usually battery powered, and an efficient use of the available battery power becomes an important concern specially for those applications where the system is expected to operate for long durations. This necessity for energy efficient operation of a WSN has prompted the development of new protocols in all layers of the communication stack. If the radio transceiver is the most power consuming component of a typical sensor node, large gains can be achieved at the link layer where the medium access control (MAC) protocol controls the usage of the radio transceiver unit.     

基于PSO的无线多媒体传感器网络覆盖增强算法

在无线多媒体传感器网络(Wireless Multimedia Sensor Networks,WMSNs)中,由于节点部署的不合理,往往存在较多的监控盲区,影响了网络的服务质量。为了提高网络的覆盖率,在有向感知模型基础的基础上,提出了一种基于粒子群算法的WMSNs覆盖增强算法PSOCE。PSOCE算法以网络覆盖率为优化目标,以粒子群算法为计算工具,同时对节点的位置与主感知方向进行调整。仿真试验表明,PSOCE算法能够有效地改进WMSNs的覆盖质量,网络的覆盖率能提高6%～12%。     

Connectivity maintenance and coverage preservation in wireless sensor networks

In wireless sensor networks, one of the main design challenges is to save severely constrained energy resources and obtain long system lifetime. Low cost of sensors enables us to randomly deploy a large number of sensor nodes. Thus, a potential approach to solve lifetime problem arises. That is to let sensors work alternatively by identifying redundant nodes in high-density networks and assigning them an off-duty operation mode that has lower energy consumption than the normal on-duty mode. In a single wireless sensor network, sensors are performing two operations: sensing and communication. Therefore, there might exist two kinds of redundancy in the network. Most of the previous work addressed only one kind of redundancy: sensing or communication alone. Wang et al. [Intergrated Coverage and Connectivity Configuration in Wireless Sensor Networks, in: Proceedings of the First ACM Conference on Embedded Networked Sensor Systems (SenSys 2003), Los Angeles, November 2003] and Zhang and Hou [Maintaining Sensing Coverage and Connectivity in Large Sensor Networks. Technical report UIUCDCS-R-2003-2351, June 2003] first discussed how to combine consideration of coverage and connectivity maintenance in a single activity scheduling. They provided a sufficient condition for safe scheduling integration in those fully covered networks. However, random node deployment often makes initial sensing holes inside the deployed area inevitable even in an extremely high-density network. Therefore, in this paper, we enhance their work to support general wireless sensor networks by proving another conclusion: “the communication range is twice of the sensing range” is the sufficient condition and the tight lower bound to ensure that complete coverage preservation implies connectivity among active nodes if the original network topology (consisting of all the deployed nodes) is connected. Also, we extend the result to k-degree network connectivity and k-degree coverage preservation.     

Deterministic deployment based on information coverage in wireless sensor networks

In this study, a deterministic deployment problem in wireless sensor networks is examined. On the basis of information coverage, we study equilateral triangle and square deployment strategies, and we provide the maximum distance between sensors in order to reach the required detection probability for any point in the monitoring field. First, we provide a model of the signal attenuation. On the basis of the detected signal from the K sensors, the best linear and unbiased estimation is used to estimate the signal parameter with the corresponding error. For the equilateral triangle deployment, the maximum distance between sensors is computed and provided when the received signal data from two or three sensors is used. Similarly, we have computed and supplied the maximum distance between sensors in the square deployment. Simulations are performed to show the relationship between the number of sensors and the detection probability. The simulation results show that it is not a good choice to improve the detection probability with a larger number of sensors.Copyright © 2012 John Wiley & Sons, Ltd.     

QoS‐aware target coverage in wireless sensor networks

Wireless sensor networks have emerged recently as an effective way of monitoring remote or inhospitable physical targets, which usually have different quality of service (QoS) constraints, i.e., different targets may need different sensing quality in terms of the number of transducers, sampling rate, etc. In this paper, we address the problem of optimizing network lifetime while capturing those diversified QoS coverage constraints in such surveillance sensor networks. We show that this problem belongs to NP‐complete class. We define a subset of sensors meeting QoS requirements as a coverage pattern, and if the full set of coverage patterns is given, we can mathematically formulate the problem. Directly solving this formulation however is difficult since number of coverage patterns may be exponential to number of sensors and targets. Hence, a column generation (CG)‐based approach is proposed to decompose the original formulation into two subproblems and solve them iteratively. Here a column corresponds to a feasible coverage pattern, and the idea is to find a column with steepest ascent in lifetime, based on which we iteratively search for the maximum lifetime solution. An initial feasible set of patterns is generated through a novel random selection algorithm (RSA), in order to launch our approach. Experimental data demonstrate that the proposed CG‐based approach is an efficient solution, even in a harsh environment. Simulation results also reveal the impact of different network parameters on network lifetime, giving certain guidance on designing and maintaining such surveillance sensor networks. Copyright © 2009 John Wiley & Sons, Ltd.     

InRout - A QoS aware route selection algorithm for industrial wireless sensor networks

Wireless sensor networks are a key enabling technology for industrial monitoring applications where the use of wireless infrastructure allows high adaptivity and low cost in terms of installation and retrofitting. To facilitate the move from the current wired designs to wireless designs, concerns regarding reliability must be satisfied. Current standardization efforts for industrial wireless systems lack specification on efficient routing protocols that mitigate reliability concerns. Consequently, this work presents the InRout route selection algorithm, where local information is shared among neighbouring nodes to enable efficient, distributed route selection while satisfying industrial application requirements and considering sensor node resource limitations. Route selection is described as a multi-armed bandit task and uses Q-learning techniques to obtain the best available solution with low overhead. A performance comparison with existing approaches demonstrates the benefits of the InRout algorithm, which satisfies typical quality of service requirements for industrial monitoring applications while considering sensor node resources. Simulation results show that InRout can provide gains ranging from 4% to 60% in the number of successfully delivered packets when compared to current approaches with much lower control overhead.     

Location-unaware coverage in wireless sensor networks

In scenarios where sensors are placed randomly, redundant deployment is essential for ensuring adequate field coverage. This redundancy needs to be efficiently exploited by periodically selecting a subset of nodes (referred to as a “cover”) that actively monitor the field, and putting the remaining nodes to sleep. We consider networks in which sensors are not aware of their locations or the relative directions of their neighbors. We develop several geometric and density-based tests that enable a location-unaware sensor to intelligently determine whether it should turn itself off without degrading the quality of field coverage. These tests rely on distance measurements and exchanged two-hop neighborhood information. We design an algorithm (LUC) that exploits these tests for computing covers. Based on this algorithm, we propose two distributed protocols (LUC-I and LUC-P) that periodically select covers and switch between them so as to extend the network lifetime and tolerate unexpected failures. Our protocols are highly efficient in terms of message overhead and processing complexity. We implement LUC-I in TinyOS and evaluate it using the TOSSIM simulator. Experimental results indicate that our approach significantly prolongs the network lifetime and achieves comparable performance to location-aware protocols.     

Duty cycle learning algorithm (DCLA) for IEEE 802.15.4 beacon-enabled wireless sensor networks

The current specification of the IEEE 802.15.4 standard for beacon-enabled wireless sensor networks does not define how the fraction of the time that wireless nodes are active, known as the duty cycle, needs to be configured in order to achieve the optimal network performance in all traffic conditions. The work presented here proposes a duty cycle learning algorithm (DCLA) that adapts the duty cycle during run time without the need of human intervention in order to minimise power consumption while balancing probability of successful data delivery and delay constraints of the application. Running on coordinator devices, DCLA collects network statistics during each active duration to estimate the incoming traffic. Then, at each beacon interval uses the reinforcement learning (RL) framework as the method for learning the best duty cycle. Our approach eliminates the necessity for manually (re-)configuring the nodes duty cycle for the specific requirements of each network deployment. This presents the advantage of greatly reducing the time and cost of the wireless sensor network deployment, operation and management phases. DCLA has low memory and processing requirements making it suitable for typical wireless sensor platforms. Simulations show that DCLA achieves the best overall performance for either constant and event-based traffic when compared with existing IEEE 802.15.4 duty cycle adaptation schemes.     

Controlled sink mobility for prolonging wireless sensor networks lifetime

This paper demonstrates the advantages of using controlled mobility in wireless sensor networks (WSNs) for increasing their lifetime, i.e., the period of time the network is able to provide its intended functionalities. More specifically, for WSNs that comprise a large number of statically placed sensor nodes transmitting data to a collection point (the sink), we show that by controlling the sink movements we can obtain remarkable lifetime improvements. In order to determine sink movements, we first define a Mixed Integer Linear Programming (MILP) analytical model whose solution determines those sink routes that maximize network lifetime. Our contribution expands further by defining the first heuristics for controlled sink movements that are fully distributed and localized. Our Greedy Maximum Residual Energy (GMRE) heuristic moves the sink from its current location to a new site as if drawn toward the area where nodes have the highest residual energy. We also introduce a simple distributed mobility scheme (Random Movement or RM) according to which the sink moves uncontrolled and randomly throughout the network. The different mobility schemes are compared through extensive ns2-based simulations in networks with different nodes deployment, data routing protocols, and constraints on the sink movements. In all considered scenarios, we observe that moving the sink always increases network lifetime. In particular, our experiments show that controlling the mobility of the sink leads to remarkable improvements, which are as high as sixfold compared to having the sink statically (and optimally) placed, and as high as twofold compared to uncontrolled mobility. Stefano Basagni holds a Ph.D. in electrical engineering from the University of Texas at Dallas (December 2001) and a Ph.D. in computer science from the University of Milano, Italy (May 1998). He received his B.Sc. degree in computer science from the University of Pisa, Italy, in 1991. Since Winter 2002 he is on faculty at the Department of Electrical and Computer Engineering at Northeastern University, in Boston, MA. From August 2000 to January 2002 he was professor of computer science at the Department of Computer Science of the Erik Jonsson School of Engineering and Computer Science, The University of Texas at Dallas. Dr. Basagni’s current research interests concern research and implementation aspects of mobile networks and wireless communications systems, Bluetooth and sensor networking, definition and performance evaluation of network protocols and theoretical and practical aspects of distributed algorithms. Dr. Basagni has published over four dozens of referred technical papers and book chapters. He is also co-editor of two books. Dr. Basagni served as a guest editor of the special issue of the Journal on Special Topics in Mobile Networking and Applications (MONET) on Multipoint Communication in Wireless Mobile Networks, of the special issue on mobile ad hoc networks of the Wiley’s Interscience’s Wireless Communications & Mobile Networks journal, and of the Elsevier’s journal Algorithmica on algorithmic aspects of mobile computing and communications. Dr. Basagni serves as a member of the editorial board and of the technical program committee of ACM and IEEE journals and international conferences. He is a senior member of the ACM (including the ACM SIGMOBILE), senior member of the IEEE (Computer and Communication societies), and member of ASEE (American Society for Engineering Education). Alessio Carosi received the M.S. degree “summa cum laude” in Computer Science in 2004 from Rome University “La Sapienza.” He is currently a Ph.D. candidate in Computer Science at Rome University “La Sapienza.” His research interests include protocols for ad hoc and sensor networks, underwater systems and delay tolerant networking. Emanuel Melachrinoudis received the Ph.D. degree in industrial engineering and operations research from the University of Massachusetts, Amherst, MA. He is currently the Director of Industrial Engineering and Associate Chairman of the Department of Mechanical and Industrial Engineering at Northeastern University, Boston, MA. His research interests are in the areas of network optimization and multiple criteria optimization with applications to telecommunication networks, distribution networks, location and routing. He is a member of the Editorial Board of the International Journal of Operational Research. He has published in journals such as Management Science, Transportation Science, Networks, European Journal of Operational Research, Naval Research Logistics and IIE Transactions. Chiara Petrioli received the Laurea degree “summa cum laude” in computer science in 1993, and the Ph.D. degree in computer engineering in 1998, both from Rome University “La Sapienza,” Italy. She is currently Associate Professor with the Computer Science Department at Rome University “La Sapienza.” Her current work focuses on ad hoc and sensor networks, Delay Tolerant Networks, Personal Area Networks, Energy-conserving protocols, QoS in IP networks and Content Delivery Networks where she contributed around sixty papers published in prominent international journals and conferences. Prior to Rome University she was research associate at Politecnico di Milano and was working with the Italian Space agency (ASI) and Alenia Spazio. Dr. Petrioli was guest editor of the special issue on “Energy-conserving protocols in wireless Networks” of the ACM/Kluwer Journal on Special Topics in Mobile Networking and Applications (ACM MONET) and is associate editor of IEEE Transactions on Vehicular Technology, the ACM/Kluwer Wireless Networks journal, the Wiley InterScience Wireless Communications & Mobile Computing journal and the Elsevier Ad Hoc Networks journal. She has served in the organizing committee and technical program committee of several leading conferences in the area of networking and mobile computing including ACM Mobicom, ACM Mobihoc, IEEE ICC,IEEE Globecom. She is member of the steering committee of ACM Sensys and of the international conference on Mobile and Ubiquitous Systems: Networking and Services (Mobiquitous) and serves as member of the ACM SIGMOBILE executive committee. Dr. Petrioli was a Fulbright scholar. She is a senior member of IEEE and a member of ACM. Z. Maria Wang received her Bachelor degree in Electrical Engineering with the highest honor from Beijing Institute of Light Industry in China, her M.S. degree in Industrial Engineering/Operations Research from Dalhousie University, Canada and her Ph.D. in Industrial Engineering/Operations Research from Northeastern University, Boston. She served as a R&D Analyst for General Dynamics. Currently MS. Wang serves as an Optimization Analyst with Nomis Solutions, Inc.     

Leveraging data fusion to improve barrier coverage in wireless sensor networks

Intruder detection and border surveillance are amongst the most promising applications of wireless sensor networks. Barrier coverage formulates these problems as constructing barriers in a long-thin region to detect intruders that cross the region. Existing studies on this topic are not only based on simplistic binary sensing model but also neglect the collaboration employed in many systems. In this paper, we propose a solution which exploits the collaboration of sensors to improve the performance of barrier coverage under probabilistic sensing model. First, the network width requirement, the sensor density and the number of barriers are derived under data fusion model when sensors are randomly distributed. Then, we present an efficient algorithm to construct barriers with a small number of sensors. The theoretical comparison shows that our solution can greatly improve barrier coverage via collaboration of sensors. We also conduct extensive simulations to demonstrate the effectiveness of our solution.     

Optimal barrier coverage for critical area surveillance using wireless sensor networks

Intrusion detection using barrier coverage is one of many applications existed in wireless sensor networks. The main purpose of using barrier coverage is to monitor the borders of a specific area against the intruders that are trying to penetrate this critical area by ensuring the total coverage with a low cost and extending the lifetime of the network, many solutions have been proposed in the literature in order to solve the coverage problem in wireless sensor networks, which became a vital field of research. In this paper, we present a new technique based on geometric mathematical models, in order to guarantee the total coverage of our deployed barriers with a minimum possible number of sensors. The idea is to calculate the number of sensors adequate to cover a barrier before deployment. We then formulate the problem to minimize the number of sensors to be deployed to properly cover a barrier; the calculation makes it possible to solve this problem in polynomial using our own heuristic. Additionally, we propose a new mechanism for ensuring a fault‐tolerant network by detecting the faulty sensors and select other suited sensors to close the existing gaps inside the barriers and detecting the sensors whose energy is low before the failure. The obtained simulation results prove the effectiveness of the proposed algorithms.     

Polytype target coverage scheme for heterogeneous wireless sensor networks using linear programming

Sensing coverage is one of fundamental problems in wireless sensor networks. In this paper, we investigate the polytype target coverage problem in heterogeneous wireless sensor networks where each sensor is equipped with multiple sensing units and each type of sensing unit can sense an attribute of multiple targets. How to schedule multiple sensing units of a sensor to cover multiple targets becomes a new challenging problem. This problem is formulated as an integer linear programming problem for maximizing the network lifetime. We propose a novel energy‐efficient target coverage algorithm to solve this problem based on clustering architecture. Being aware of the coverage capability and residual energy of sensor nodes, the clusterhead node in each cluster schedules the appropriate sensing units of sensor nodes that are in the active status to cover multiple targets in an optimal way. Extensive simulations have been carried out to validate the effectiveness of the proposed scheme. Copyright © 2012 John Wiley & Sons, Ltd.     

CWSC: Connected k-coverage working sets construction algorithm in wireless sensor networks

One of the most important issues for wireless sensor networks is to get a long network lifetime without affecting either communication connectivity or sensing coverage. Many sensors that are deployed randomly in a dense sensor network in a redundant way waste a lot of energy. One effective way to save energy is to let only a subset of sensors work at any given time. In this paper, we mainly consider such a problem. Selecting the minimum number of connected sensor nodes that can provide k-coverage (k ≥ 1), i.e., selecting a subset S of working sensors, such that almost every point in the sensing region can be covered by at least k sensors and the sensors in S can form a connected communication subgraph. We propose a connected k-coverage working sets construction algorithm (CWSC) based on Euclidean distance to k-cover the sensing region while minimizing the number of working sensors. CWSC can produce different coverage degrees according to different applications, which can enhance the flexibility of the sensor network. Simulation results show that the proposed algorithm, which can conserve energy and prolong the lifetime of the sensor network, is better than the previous algorithms.     

A novel mathematical model for coverage in wireless sensor network

1 Introduction With the development of the sensor, wireless communication, and computer science, many researches have been focused on the development of a novel wireless network named wireless Ad-hoc sensor networks. This network can be defined as a network that can be self-organized in Ad-hoc fashion. This includes many sensor nodes and its objective is to sense, collect, and process the information collected by the individual sensor nodes via their cooperation [2]. Because of its high pract…     

Scheduling sensor activity for information coverage of discrete targets in sensor networks

In this paper, we study the problem of scheduling sensor activity to cover a set of targets with known locations such that all targets can be monitored all the time and the network can operate as long as possible. A solution to this scheduling problem is to partition all sensors into some sensor covers such that each cover can monitor all targets and the covers are activated sequentially. In this paper, we propose to provide information coverage instead of the conventional sensing disk coverage for target. The notion of information coverage is based on estimation theory to exploit the collaborative nature of geographically distributed sensors. Due to the use of information coverage, a target that is not within the sensing disk of any single sensor can still be considered to be monitored (information covered) by the cooperation of more than one sensor. This change of the problem settings complicates the solutions compared to that by using a disk coverage model. We first define the target information coverage (TIC) problem and prove its NP‐completeness. We then propose a heuristic to approximately solve our problem. Simulation results show that our heuristic is better than an existing algorithm and is close to the upper bound when only the sensing disk coverage model is used. Furthermore, simulation results also show that the network lifetime can be significantly improved by using the notion of information coverage compared with that by using the conventional definition of sensing disk coverage. Copyright © 2008 John Wiley & Sons, Ltd.