Multi-covered path in wireless sensor networks

The progress of development on sensor networks has inspired many new applications. Some of these applications require the target to be observed by more than one sensors simultaneously. Sensor coverage, which reflects how well a sensor network is monitored by sensors, is an important measure for the quality of service (QoS) that a sensor network can provide. In this paper, we addressed the coverage problem from two different view points and referred to them as the worst-case and best-case coverage problems. Most existing works on these two problems assumed that the coverage degree is one (i.e. the target area falls within the sensing range of at least one sensor). In this paper, we address the k-coverage problem, where the coverage degree is a user-defined parameter k. This is a generalization of the earlier work where only k=1 is assumed. By combining geometric and algorithmic techniques, we establish optimal algorithms to solve the two variants of the k-coverage problem in polynomial time. An important extension of our study on the k-coverage problem was also proposed: the distributed algorithm for the problem. This helps in applying the proposed algorithm under more practical scenarios.     

On Connected Multiple Point Coverage in Wireless Sensor Networks

We consider a wireless sensor network consisting of a set of sensors deployed randomly. A point in the monitored area is covered if it is within the sensing range of a sensor. In some applications, when the network is sufficiently dense, area coverage can be approximated by guaranteeing point coverage. In this case, all the points of wireless devices could be used to represent the whole area, and the working sensors are supposed to cover all the sensors. Many applications related to security and reliability require guaranteed k-coverage of the area at all times. In this paper, we formalize the k-(Connected) Coverage Set (k-CCS/k-CS) problems, develop a linear programming algorithm, and design two non-global solutions for them. Some theoretical analysis is also provided followed by simulation results.     

A Distributed Query Protocol in Wireless Sensor Networks

In wireless sensor networks, query execution over a specific geographical region is an essential function for collecting sensed data. However, sensor nodes deployed in sensor networks have limited battery power. Hence, the minimum number of connected sensor nodes that covers the queried region in a sensor network must be determined. This paper proposes an efficient distributed protocol to find a subset of connected sensor nodes to cover the queried region. Each node determines whether to be a sensing node to sense the queried region according to its priority. The proposed protocol can efficiently construct a subset of connected sensing nodes and respond the query request to the sink node. In addition, the proposed protocol is extended to solve the k-coverage request. Simulation results show that our protocol is more efficient and has a lower communication overhead than the existing protocol.     

Deployment of a mobile wireless sensor network with k-coverage constraint: a cellular learning automata approach

Deployment of a wireless sensor network is a challenging problem, especially when the environment of the network does not allow either of the random deployment or the exact placement of sensor nodes. If sensor nodes are mobile, then one approach to overcome this problem is to first deploy sensor nodes randomly in some initial region within the area of the network, and then let the sensor nodes to move around and cooperatively and gradually increase the covered section of the area. Recently, a cellular learning automata-based deployment strategy, called CLA-DS, is introduced in literature which follows this approach and is robust against inaccuracies which may occur in the measurements of sensor positions or in the movements of sensor nodes. Despite its advantages, this deployment strategy covers every point within the area of the network with only one sensor node, which is not enough for applications with k-coverage requirement. In this paper, we extend CLA-DS so that it can address the k-coverage requirement. This extension, referred to as CLA-EDS, is also able to address k-coverage requirement with different values of k in different regions of the network area. Experimental results have shown that the proposed deployment strategy, in addition to the advantages it inherits from CLA-DS, outperforms existing algorithms such as DSSA, IDCA, and DSLE in covering the network area, especially when required degree of coverage differs in different regions of the network.     

CASMOC: a novel complex alliance strategy with multi-objective optimization of coverage in wireless sensor networks

Coverage is a significant performance indicator of wireless sensor networks. Data redundancy in k-coverage raises a set of issues including network congestion, coverage reduction, energy inefficiency, among others. To address these issues, this paper proposes a novel algorithm called complex alliance strategy with multi-objective optimization of coverage (CASMOC) which could improve node coverage effectively. This paper also gives the proportional relationship of the energy conversion function between the working node and its neighbors, and applies this relationship in scheduling low energy mobile nodes, thus achieving energy balance of the whole network, and optimizing network resources. The extensive simulation results demonstrate that CASMOC could not only improve the quality of network coverage, but also mitigate rapid node energy consumption effectively, thereby extending the life cycle of the network significantly.     

一种无线传感器网络全连通群的休眠调度算法

该文针对无线传感器网络的覆盖性和连通性问题,在假设传感器节点地理位置信息已知的条件下,设计了一种包含全连通群的建立和维护以及群内节点休眠调度的全新算法。该算法采用保证群内节点彼此一跳可达的全连通群分群方法,以及分布式节能的休眠调度策略,最大程度上减少传感器网络的能量消耗,延长了网络寿命。仿真结果表明:该算法能较好地保证无线传感器网络的覆盖性和连通性,且能耗较低。     

On coverage issues in directional sensor networks: A survey

The coverage optimization problem has been examined thoroughly for omni-directional sensor networks in the past decades. However, the coverage problem in directional sensor networks (DSN) has newly taken attraction, especially with the increasing number of wireless multimedia sensor network (WMSN) applications. Directional sensor nodes equipped with ultrasound, infrared, and video sensors differ from traditional omni-directional sensor nodes with their unique characteristics, such as angle of view, working direction, and line of sight (LoS) properties. Therefore, DSN applications require specific solutions and techniques for coverage enhancement. In this survey article, we mainly aim at categorizing available coverage optimization solutions and survey their problem definitions, assumptions, contributions, complexities and performance results. We categorize available studies about coverage enhancement into four categories. Target-based coverage enhancement, area-based coverage enhancement, coverage enhancement with guaranteed connectivity, and network lifetime prolonging. We define sensing models, design issues and challenges for directional sensor networks and describe their (dis)similarities to omni-directional sensor networks. We also give some information on the physical capabilities of directional sensors available on the market. Moreover, we specify the (dis)advantages of motility and mobility in terms of the coverage and network lifetime of DSNs.     

Energy-efficient top-k query evaluation and maintenance in wireless sensor networks

Top-k query in a wireless sensor network is to identify k sensors with the highest sensor readings. Since sensors usually are powered by energy-limited batteries, a fundamental problem associated with top-k query evaluation in such a network is to maximize network lifetime, which poses great challenges due to the unique characteristics of sensor networks. In this paper, we first propose a novel filter-based algorithm for top-k query evaluation, which is able to filter out a fractional amount of data from network-wide transmission. We then develop an online algorithm for answering time-dependent top-k queries with different values of k through the dynamic maintenance of a materialized view that consists of historical top-k results. We finally conduct extensive experiments by simulations to evaluate the performance of the proposed algorithms using real sensing data sets. Experimental results show that the proposed algorithms outperform a well known existing algorithm significantly, and the network lifetime delivered by the proposed optimal quantile algorithm is at least 142 % times longer than that by an existing algorithm.     

Connectivity properties of large-scale sensor networks

In wireless sensor networks, both nodes and links are prone to failures. In this paper we study connectivity properties of large-scale wireless sensor networks and discuss their implicit effect on routing algorithms and network reliability. We assume a network model of n sensors which are distributed randomly over a field based on a given distribution function. The sensors may be unreliable with a probability distribution, which possibly depends on n and the location of sensors. Two active sensor nodes are connected with probability p _e (n) if they are within communication range of each other. We prove a general result relating unreliable sensor networks to reliable networks. We investigate different graph theoretic properties of sensor networks such as k-connectivity and the existence of the giant component. While connectivity (i.e. k = 1) insures that all nodes can communicate with each other, k-connectivity for k > 1 is required for multi-path routing. We analyze the average shortest path of the k paths from a node in the sensing field back to a base station. It is found that the lengths of these multiple paths in a k-connected network are all close to the shortest path. These results are shown through graph theoretical derivations and are also verified through simulations.     

WHOMoVeS: An optimized broadband sensor network for military vehicle tracking

With the advance of sensing technologies and their applications, advanced sensor networks are gaining increasing interest. For certain sensitive applications, heterogeneous sensors can be deployed in the monitored space to ensure scalability, high-speed communication, and long network lifetime. Hybrid sensor networks have capabilities to combine the use of both resource-rich and resource-impoverished sensor nodes. This paper proposes a heterogeneous broadband sensor network architecture for military vehicle tracking. Powerful sensor devices with good bandwidth and energy capabilities are used as a communication backbone while energy sensors are used to track moving targets. Copyright © 2007 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.     

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.     

Joint consideration of energy‐efficiency and coverage‐preservation in microsensor networks

This paper presents an energy‐efficient and coverage‐preserving communication protocol which distributes a uniform energy load to the sensors in a wireless microsensor network. This protocol, called Distance‐based Segmentation (DBS), is a cluster‐based protocol that divides the entire network into equal‐area segments and applies different clustering policies to each segment to (1) reduce total energy dissipation and (2) balance the energy load among the sensors. Therefore, it prolongs the lifetime of the network and improves the sensing coverage. Moreover, the proposed routing protocol does not need any centralized support from a certain node which is at odds with aiming to establish a scalable communication protocol. Results from extensive simulations on two different network configurations show that by lowering the number of wasteful transmissions in the network, the DBS can achieve as much as a 20% reduction in total dissipated energy as compared with current cluster‐based protocols. In addition, this protocol is able to distribute energy load more evenly among the sensors in the network. Hence, it yields up to a 66% increase in the useful network lifetime. According to the simulation results, the sensing coverage degradation of the DBS is considerably slower than that of the other cluster‐based protocols. Copyright © 2009 John Wiley & Sons, Ltd.     

Improved approximation algorithms for connected sensor cover

Wireless sensor networks have recently posed many new system building challenges. One of the main problems is energy conservation since most of the sensors are devices with limited battery life and it is infeasible to replenish energy via replacing batteries. An effective approach for energy conservation is scheduling sleep intervals for some sensors, while the remaining sensors stay active providing continuous service. In this paper we consider the problem of selecting a set of active sensors of minimum cardinality so that sensing coverage and network connectivity are maintained. We show that the greedy algorithm that provides complete coverage has an approximation factor no better than Ω(log n), where n is the number of sensor nodes. Then we present algorithms that provide approximate coverage while the number of nodes selected is a constant factor far from the optimal solution. Finally, we show how to connect a set of sensors that already provides coverage.     

Flow-balanced routing for multi-hop clustered wireless sensor networks

Power efficiency and coverage preservation are two important performance metrics for a wireless sensor network. However, there is scarcely any protocol to consider them at the same time. In this paper, we propose a flow-balanced routing (FBR) protocol for multi-hop clustered wireless sensor networks that attempts to achieve both power efficiency and coverage preservation. The proposed protocol consists of four algorithms, one each for network clustering, multi-hop backbone construction, flow-balanced transmission, and rerouting. The proposed clustering algorithm groups several sensors into one cluster on the basis of overlapping degrees of sensors. The backbone construction algorithm constructs a novel multi-level backbone, which is not necessarily a tree, using the cluster heads and the sink. Furthermore, the flow-balanced routing algorithm assigns the transferred data over multiple paths from the sensors to the sink in order to equalize the power consumption of sensors. Lastly, the rerouting algorithm reconstructs the network topology only in a place where a head drops out from the backbone due to the head running out of its energy. Two metrics called the network lifetime and the coverage lifetime are used to evaluate the performance of FBR protocol in comparison with previous ones. The simulation results show that FBR yields both much longer lifetime and better coverage preservation than previous protocols. For example, FBR yields more than twice network lifetime and better coverage preservation than a previous efficient protocol, called the coverage-preserving clustering protocol (CPCP) [18], when the first sensor dies and the network coverage is kept at 100%, respectively.     

Barrier coverage with wireless sensors

When a sensor network is deployed to detect objects penetrating a protected region, it is not necessary to have every point in the deployment region covered by a sensor. It is enough if the penetrating objects are detected at some point in their trajectory. If a sensor network guarantees that every penetrating object will be detected by at least k distinct sensors before it crosses the barrier of wireless sensors, we say the network provides k-barrier coverage. In this paper, we develop theoretical foundations for k-barrier coverage. We propose efficient algorithms using which one can quickly determine, after deploying the sensors, whether the deployment region is k-barrier covered. Next, we establish the optimal deployment pattern to achieve k-barrier coverage when deploying sensors deterministically. Finally, we consider barrier coverage with high probability when sensors are deployed randomly. The major challenge, when dealing with probabilistic barrier coverage, is to derive critical conditions using which one can compute the minimum number of sensors needed to ensure barrier coverage with high probability. Deriving critical conditions for k-barrier coverage is, however, still an open problem. We derive critical conditions for a weaker notion of barrier coverage, called weak k-barrier coverage.     

Efficient Sensor Deployment Control Schemes and Performance Evaluation for Obstacle and Unknown Environments

Deployment is a fundamental issue for wireless sensor networks (WSNs). A well-designed deployment control method not only directly influences the number of deployed sensors, but also influences on data accuracy and network topology. Three widely discussed deployment methods are random deployment, deterministic deployment and deployment by graphic theory. Most related works have focused on the maximal deployment area problem, but few studies have considered efficient methods to solve the k-coverage problem. Moreover, such methods have high time complexity, making them unsuitable for k-covered sensor deployment. To achieve scalable and efficient deployment, this study presents two new topology deployment methods, namely the slow-start method (SSM) and square-encircled method (SEM). The proposed deployment methods can yield k-covered scenarios with minimal overlapping areas, by three different coverage sensors. SSM and SEM are without needing to pre-analyze unknown or unsafe environments when deploying a k-coverage area. Deploying and satisfying each layer until k layers are obtained requires guaranteeing k coverage. The proposed methods have time complexities of O(n ²), making them suitable for WSNs. Moreover, this study first presents nine Construct Performance Evaluation (CPE) factors to evaluate the total costs of a WSN. Finally, this study evaluates the total deployment costs through CPE factors, and analyzes their performance. The simulation results clearly indicate the efficiency and effectiveness of the proposed deployment methods.

Expected k-coverage in wireless sensor networks

We are concerned with wireless sensor networks where n sensors are independently and uniformly distributed at random in a finite plane. Events that are within a fixed distance from some sensor are assumed to be detectable and the sensor is said to cover that point. In this paper, we have formulated an exact mathematical expression for the expected area that can be covered by at least k out of n sensors. Our results are important in predicting the degree of coverage a sensor network may provide and in determining related parameters (sensory range, number of sensors, etc.) for a desired level of coverage. We demonstrate the utility of our results by presenting a node scheduling scheme that conserves energy while retaining network coverage. Additional simulation results have confirmed the accuracy of our analysis.     

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.