无线传感器网络连通忌覆盖问题及其解决方案综述

覆盖控制是无线传感器网络的一个基本问题,通过对网络空间资源的优化分配,来更好地完成环境感知和有效传输等任务。作为覆盖控制理论的研究热点之一,连通k覆盖问题研究如何从随机部署的大量传感器节点中选择一部分节点激活,使得任意监测目标都被至少k个不同的活跃节点同时覆盖,而且所有活跃节点都是通信连通的。本文分析了无线传感器网络中连通k覆盖问题的系统模型和算法评价指标,介绍了一些典型的近似算法并对其进行了分析和比较,最后进行了总结和展望。     

A novel gossip-based sensing coverage algorithm for dense wireless sensor networks

Wireless sensor networks (WSNs) have been widely studied and usefully employed in many applications such as monitoring environments and embedded systems. WSNs consist of many nodes spread randomly over a wide area; therefore, the sensing regions of different nodes may overlap partially. This is called the “sensing coverage problem”. In this paper, we define a maximum sensing coverage region (MSCR) problem and present a novel gossip-based sensing-coverage-aware algorithm to solve the problem. In the algorithm, sensor nodes gossip with their neighbors about their sensing coverage region. In this way, nodes decide locally to forward packets (as an active node) or to disregard packets (as a sleeping or redundant node). Being sensing-coverage-aware, the redundant node can cut back on its activities whenever its sensing region is k-covered by enough neighbors. With the distributed and low-overhead traffic benefits of gossip, we spread energy consumption to different sensor nodes, achieve maximum sensing coverage with minimal energy consumption in each individual sensor node, and prolong the whole network lifetime. We apply our algorithm to improve LEACH, a clustering routing protocol for WSNs, and develop a simulation to evaluate the performance of the algorithm.     

Distributed Deployment Schemes for Mobile Wireless Sensor Networks to Ensure Multilevel Coverage

One of the research issues in wireless sensor networks (WSNs) is how to efficiently deploy sensors to cover an area. In this paper, we solve the k-coverage sensor deployment problem to achieve multi-level coverage of an area I. We consider two sub-problems: k-coverage placement and distributed dispatch problems. The placement problem asks how to determine the minimum number of sensors required and their locations in I to guarantee that I is k-covered and the network is connected; the dispatch problem asks how to schedule mobile sensors to move to the designated locations according to the result computed by the placement strategy such that the energy consumption due to movement is minimized. Our solutions to the placement problem consider both the binary and probabilistic sensing models, and allow an arbitrary relationship between the communication distance and sensing distance of sensors. For the dispatch problem, we propose a competition-based and a pattern-based schemes. The former allows mobile sensors to bid for their closest locations, while the latter allows sensors to derive the target locations on their own. Our proposed schemes are efficient in terms of the number of sensors required and are distributed in nature. Simulation results are presented to verify their effectiveness.     

Minimizing mobile sensor movements to form a line K-coverage

In wireless sensor networks and social networks, distributed nodes usually form a network with coverage ability for a lot of applications, such as the intrusion detection. In this paper, a new kind of coverage problem with mobile sensors is addressed, named Line K-Coverage. It guarantees that any intruder trajectory line cutting across a region of interest will be detected by at least K sensors. For energy efficiency, we aim to schedule an efficient sensor movement to satisfy the line K-coverage while minimizing the total sensor movements, which is named as LK-MinMovs problem. We firstly construct two time-efficient heuristics named LK-KM and LK-KM+ based on the famous Hungarian algorithm. By sacrificing optimality a little bit, these two algorithms have better time efficiency. Then we propose a pioneering layer-based algorithm LLK-MinMovs to solve LK-MinMovs in polynomial time. Here, we assume that all sensors are initially located in a closed region. We validate its correctness by theoretical analysis. Later, the more general situation are considered that all sensors are allowed to locate outside of the region. We improve LLK-MinMovs algorithm to the general version: GenLLK-MinMovs. More importantly, our GenLLK-MinMovs fixes a critical flaw for MinSum algorithm which was proposed by previous literature to solve line 1-coverage problem. We show the flaw using a counter example. Finally, we validate the efficiency of all our designs by numerical experiments and compare them under different experiment settings.     

Distributed autonomy and trade-offs in online multiobject k-coverage

In this article, we explore the online multiobject k-coverage problem in visual sensor networks. This problem combines k-coverage and the cooperative multirobot observation of multiple moving targets problem, and thereby captures key features of rapidly deployed camera networks, including redundancy and team-based tracking of evasive or unpredictable targets. The benefits of using mobile cameras are demonstrated and we explore the balance of autonomy between cameras generating new subgoals, and those responders able to fulfill them. We show that higher performance against global goals is achieved when decisions are delegated to potential responders who treat subgoals as optional, rather than as obligations that override existing goals without question. This is because responders have up-to-date knowledge of their own state and progress toward goals where they are situated, which is typically old or incomplete at locations remote from them. Examining the extent to which approaches overprovision or underprovision coverage, we find that being well suited for achieving 1-coverage does not imply good performance at k-coverage. Depending on the structure of the environment, the problems of 1-coverage and k-coverage are not necessarily aligned and that there is often a trade-off to be made between standard coverage maximization and achieving k-coverage.     

Participant selection for <Emphasis Type="Italic">t</Emphasis>-sweep <Emphasis Type="Italic">k</Emphasis>-coverage crowd sensing tasks

With the popularization of wireless networks and mobile intelligent terminals, mobile crowd sensing is becoming a promising sensing paradigm. Tasks are assigned to users with mobile devices, which then collect and submit ambient information to the server. The composition of participants greatly determines the quality and cost of the collected information. This paper aims to select fewest participants to achieve the quality required by a sensing task. The requirement namely “t-sweep k-coverage” means for a target location, every t time interval should at least k participants sense. The participant selection problem for “t-sweep k-coverage” crowd sensing tasks is NP-hard. Through delicate matrix stacking, linear programming can be adopted to solve the problem when it is in small size. We further propose a participant selection method based on greedy strategy. The two methods are evaluated through simulated experiments using users’ call detail records. The results show that for small problems, both the two methods can find a participant set meeting the requirement. The number of participants picked by the greedy based method is roughly twice of the linear programming based method. However, when problems become larger, the linear programming based method performs unstably, while the greedy based method can still output a reasonable solution.     

Pareto-based evolutionary computational approach for wireless sensor placement

Wireless sensor networks (WSNs) have become increasingly appealing in recent years for the purpose of data acquisition, surveillance, event monitoring, etc. Optimal positioning of wireless sensor nodes is an important issue for small networks of relatively expensive sensing devices. For such networks, the placement problem requires that multiple objectives be met. These objectives are usually conflicting, e.g. achieving maximum coverage and maximum connectivity while minimizing the network energy cost. A flexible algorithm for sensor placement (FLEX) is presented that uses an evolutionary computational approach to solve this multiobjective sensor placement optimization problem when the number of sensor nodes is not fixed and the maximum number of nodes is not known a priori. FLEX starts with an initial population of simple WSNs and complexifies their topologies over generations. It keeps track of new genes through historical markings, which are used in later generations to assess two networks’ compatibility and also to align genes during crossover. It uses Pareto-dominance to approach Pareto-optimal layouts with respect to the objectives. Speciation is employed to aid the survival of gene innovations and facilitate networks to compete with similar networks. Elitism ensures that the best solutions are carried over to the next generation. The flexibility of the algorithm is illustrated by solving the device/node placement problem for different applications like facility surveillance, coverage with and without obstacles, preferential surveillance, and forming a clustering hierarchy.     

Sleep–wake up scheduling with probabilistic coverage model in sensor networks1

Energy optimisation is one of the important issues in the research of wireless sensor networks (WSNs). In the application of monitoring, a large number of sensors are scattered uniformly to cover a collection of points of interest (PoIs) distributed randomly in the monitored area. Since the energy of battery-powered sensor is limited in WSNs, sensors are scheduled to wake up in a large-scale sensor network application. In this paper, we consider how to reduce the energy consumption and prolong the lifetime of WSNs through wake-up scheduling with probabilistic sensing model in the large-scale application of monitoring. To extend the lifetime of sensor network, we need to balance the energy consumption of sensors so that there will not be too much redundant energy in some sensors before the WSN terminates. The detection probability and false alarm probability are taken into consideration to achieve a better performance and reveal the real sensing process which is characterised in the probabilistic sensing model. Data fusion is also introduced to utilise information of sensors so that a PoI in the monitored area may be covered by multiple sensors collaboratively, which will decrease the number of sensors that cover the monitored region. Based on the probabilistic model and data fusion, minimum weight probabilistic coverage problem is formulated in this paper. We also propose a greedy method and modified genetic algorithm based on the greedy method to address the problem. Simulation experiments are conducted to demonstrate the advantages of our proposed algorithms over existing work.     

Instrumenting Wireless Sensor Networks — A survey on the metrics that matter

Wireless Sensor Networks (WSN) are part of the technical fundament enabling the ‘Internet of Things’ (IoT), where sensing and actuator nodes instantaneously interact with the environment at large. As such they become part of everyday life and drive applications as diverse as medical monitoring, smart homes, smart environment, and smart factories, to name but a few. To acquire data, individual sensors interact with the physical environment by sensing physical phenomena in proximity. The wireless network connectivity is leveraged to collect the raw data or pre-processed events, and to disseminate code, queries or commands. Actuating capabilities facilitate instant interactions with the environment or application processes. Experience on how to operate large scale heterogeneous WSNs in (critical) real-world applications is still scarce, and operational considerations are often an afterthought to WSN deployment. A principled look into the metrics, i.e., a standard or best practice of measurement of the ‘vital’ parameters in WSNs is still missing. In this article, we contribute a survey on the most important metrics to characterize the performance of WSNs. We define an abstract system model for WSNs, take a look on what the WSN community considers ‘metrics that matter’, and categorize the metrics into scopes of relevance. We discuss the properties of the metrics as well as practical aspects on how to obtain and process them. Our survey can serve as a ‘manual’ for implementors and operators of WSNs in the IoT.     

覆盖率均衡区域覆盖算法

为了进一步实现无线传感器网络生命周期的最大化,针对网络中能量均匀且均衡覆盖问题展开研究,提出覆盖率均衡区域覆盖算法BRACA( Balanced Rate Area Coverage Algorithm)。该算法引入覆盖率均衡思想,将各传感器节点对目标区域覆盖率的均衡性与节点剩余能量的均衡性作为筛选因子,且通过调节传感器节点的剩余能量与其平均覆盖率的比例关系,筛选出最大不相关且代价最小的网络覆盖子集,以尽可能少的节点实现对区域的覆盖。经对比实验验证,算法BRACA具有更高的计算效率,所生成的ε-覆盖子集,以更少且更均衡的能量消耗,保证了网络覆盖率≥90%,有效地延长了网络生命周期。     

Primal and dual-based algorithms for sensing range adjustment in WSNs

Coverage and tracking of multiple targets, are viewed as important challenges in WSNs, mainly aimed for future ubiquitous and pervasive applications. Target coverage in WSNs with large numbers of sensor nodes and targets, and with a predefined placement of sensors, may be conducted through adjusting the sensing range and considering the energy consumption related to this operation. In this paper, we encounter the problem of multiple target coverage in WSNs by determining the sensing range of each sensor node to maximize the total utility of the network. We solve this Network Utility Maximization (NUM) problem via two approaches, primal and dual decompositions, which result in iterative distributed price-based algorithms. Convergence of sensing ranges to optimal values is proved by means of stability analysis and simulation experiments. Simulation results show convergence to optimal values in few iterations, with near optimal values for the total objective function and energy consumption of nodes. These results show scalability of our algorithm, in terms of the number of iterations needed for convergence when compared with the other two methods. Furthermore, the distributed algorithm based on dual decomposition is used to cover efficiently moving targets in consecutive time intervals.     

Distributed algorithms for barrier coverage using relocatable sensors

We study the barrier coverage problem using relocatable sensor nodes. We assume each sensor can sense an intruder or event inside its sensing range. Sensors are initially located at arbitrary positions on the barrier and can move along the barrier. The goal is to find final positions for sensors so that the entire barrier is covered. In recent years, the problem has been studied extensively in the centralized setting. In this paper, we study a barrier coverage problem in the distributed and discrete setting. We assume that we have n identical sensors located at grid positions on the barrier, and that each sensor repeatedly executes a Look-Compute-Move cycle: based on what it sees in its vicinity, it makes a decision on where to move, and moves to its next position. We make two strong but realistic restrictions on the capabilities of sensors: they have a constant visibility range and can move only a constant distance in every cycle. In this model, we give the first two distributed algorithms that achieve barrier coverage for a line segment barrier when there are enough nodes in the network to cover the entire barrier. Our algorithms are synchronous, and local in the sense that sensors make their decisions independently based only on what they see within their constant visibility range. One of our algorithms is oblivious whereas the other uses two bits of memory at each sensor to store the type of move made in the previous step. We show that our oblivious algorithm terminates within \(\varTheta (n^2)\) steps with the barrier fully covered, while the constant-memory algorithm is shown to take \(\varTheta (n)\) steps to terminate in the worst case. Since any algorithm in which a sensor can only move a constant distance in one step requires \(\varOmega (n)\) steps on some inputs, our second algorithm is asymptotically optimal.     

Lifetime extension for surveillance wireless sensor networks with intelligent redeployment

For wireless sensor networks (WSNs), uneven energy consumption is a major problem. A direct consequence of this is the energy hole problem, formation of sensing voids within the network field due to battery depleted sensors in the corresponding region. Hole formations are inherent in the network topology, yet it is possible to develop strategies to delay the hole formations to later stages of the network operation and essentially extend the network lifetime without sensing quality loss. In this work, we initially propose and analyze an approach that can be used to mitigate the hole problem. The approach is presented in detail and the effects on the sustained surveillance quality are presented. The results are based on simulations with different network configurations with realistic sensor models, MAC and routing protocols. By using the proposed approach, sustaining a sensing quality above a given threshold and more than doubling the network lifetime are possible. The results clearly indicate the suitability of the approach for especially demanding WSNs such as the ones used for border surveillance tasks.     

Energy-efficient communication in wireless cable sensor networks

In this paper, we introduce a new type of sensor: cable sensor. Unlike traditional point sensors, this type of sensor has a rectangular sensing region with a processor installed on it to do processing and communication. The wireless network formed by this kind of sensor is called wireless cable sensor network (WCSN). We study energy-efficient communication algorithms in WCSNs. We address it in two ways: one is through reducing the total transmission power of processors while maintaining the connectivity of the network and the other is through scheduling cable sensors to let them take turns to go to sleep without affecting the coverage and connectivity of the network. In the first approach, we initially develop a distributed algorithm called DTRNG based on the relative neighbourhood graph. Later we enhance it to Algorithm determine the transmission power by removing the largest edge in CYCles (DTCYC). Mathematical proofs show that Algorithm DTCYC provides an optimal solution that can not only minimise the total processor transmission power but maintain the connectivity of the network as well. In the second approach, we propose a cable mode transition algorithm which determines the minimum number of active sensors to maintain K-coverage as well as K-connectivity required by the application. We discuss the relationship between coverage and connectivity and prove the theorems that lay the foundation for our algorithm. Simulation results demonstrate that our algorithm is efficient in saving energy.     

Top-k query evaluation in sensor networks under query response time constraint

Top-k query in a wireless sensor network is to find the k sensor nodes with the highest sensing values. To evaluate the top-k query in such an energy-constrained network poses great challenges, due to the unique characteristics imposed on its sensors. Existing solutions for top-k query in the literature mainly focused on energy efficiency but little attention has been paid to the query response time and its effect on the network lifetime. In this paper we address the query response time and its effect on the network lifetime through the study of the top-k query problem in sensor networks with the response time constraint. We aim at finding an energy-efficient routing tree and evaluating top-k queries on the tree such that the network lifetime is significantly prolonged, provided that the query response time constraint is met too. To do so, we first present a cost model of energy consumption for answering top-k queries and introduce the query response time definition. We then propose a novel joint query optimization framework, which consists of finding a routing tree in the network and devising a filter-based evaluation algorithm for top-k query evaluation on the tree. We finally conduct extensive experiments by simulation to evaluate the performance of the proposed algorithms, in terms of the total energy consumption, the maximum energy consumption among nodes, the query response time, and the network lifetime. The experimental results showed that there is a non-trivial tradeoff between the query response time and the network lifetime, and the joint query optimization framework can prolong the network lifetime significantly under a specified query response time constraint.     

Coverage and connectivity-aware clustering within k hops in wireless sensor and actuator networks

Wireless sensor and actuator networks(WSANs)are a new kind of heterogeneous wireless sensor networks.Because actuators should provide maximal coverage for the sensed data,sensor-actuator connectivity is very important.However,no research considered both the maximal coverage and connectivity of sensoractuator.Once the sensors are out of coverage or the connectivity fails,the actuators cannot perform the correct actions for the area of interest.If a sensor cannot build a routing path from itself to any actuator,it becomes an orphan sensor.We therefore propose a coverage and connectivity aware clustering within k-hops(CCAC-k).In CCAC-k,sensors pick a cluster head before the actuators have been placed.All sensors are covered by at least one actuator and there are no orphan sensors in the monitored area,even when deployed randomly.Simulation results demonstrate that the coverage and connectivity of CCAC-k is higher than that of existing WSAN clustering solutions.CCAC-k also deploys fewer actuators than existing clustering solutions In addition,the coverage and connectivity in CCAC-k remains at 100%even under changes in the ratio of the transmission radius of the actuator to that of the sensor or the number of sensors.Finally,the number of actuators deployed in CCAC-k can be decreased if this or the number of sensors increased.     

Energy Efficient Monitoring in Sensor Networks

We study a set of problems related to efficient battery energy utilization for monitoring applications in a wireless sensor network with the goal to increase the sensor network lifetime. We study several generalizations of a basic problem called Set k-Cover. The problem can be described as follows: we are given a set of sensors, and a set of targets to be monitored. Each target can be monitored by a subset of the sensors. To increase the lifetime of the sensor network, we would like to partition the sensors into k sets (or time-slots), and activate each set of sensors in a different time-slot, thus extending the battery life of the sensors by a factor of k. The goal is to find a partitioning that maximizes the total coverage of the targets for a given k. This problem is known to be NP-hard. We develop an improved approximation algorithm for this problem using a reduction to Max k-Cut. Moreover, we are able to demonstrate that this algorithm is efficient, and yields almost optimal solutions in practice.     

New Algorithms for Facility Location Problems on the Real Line

In this paper, we study the facility location problems on the real line. Given a set of n customers on the real line, each customer having a cost for setting up a facility at its position, and an integer k, we seek to find at most k of the customers to set up facilities for serving all n customers such that the total cost for facility set-up and service transportation is minimized. We consider several problem variations including the k-median, the k-coverage, and the linear model. The previously best algorithms for these problems all take O(nk) time. Our new algorithms break the O(nk) time bottleneck and solve these problems in sub-quadratic time. Our algorithms are based on a new problem modeling and interesting algorithmic techniques, which may find other applications as well.     

Optimized query routing trees for wireless sensor networks

In order to process continuous queries over Wireless Sensor Networks (WSNs), sensors are typically organized in a Query Routing Tree (denoted as T) that provides each sensor with a path over which query results can be transmitted to the querying node. We found that current methods deployed in predominant data acquisition systems construct T in a sub-optimal manner which leads to significant waste of energy. In particular, since T is constructed in an ad hoc manner there is no guarantee that a given query workload will be distributed equally among all sensors. That leads to data collisions which represent a major source of energy waste. Additionally, current methods only provide a topological-based method, rather than a query-based method, to define the interval during which a sensing device should enable its transceiver in order to collect the query results from its children. We found that this imposes an order of magnitude increase in energy consumption.