Priority-based target coverage in directional sensor networks using a genetic algorithm

Sensor networks have been applied in a wide variety of situations. Recently directional sensor networks consisting of directional sensors have gained attention. As for the traditional target coverage problem, the limited sensing angle of directional sensors makes it even more challenging. Moreover, individual targets may also be associated with differentiated priorities. Considering the distance between the directional sensors and targets influences sensing quality, this paper proposes the priority-based target coverage problem and strives to choose a minimum subset of directional sensors that can monitor all targets, satisfying their prescribed priorities. Due to the NP-Complete complexity, the minimum subset of directional sensors is approximated by using a genetic algorithm. Simulation results reveal the effects of multiple factors on the size of the resulting subset.     

一种连通性覆盖的无线传感器网络节点调度算法

研究传感器节点随机部署于监测区域内,无节点地理位置信息情况下,如何能量有效地保证网络的通信连通与感知覆盖;节点采用基于概率的联合感知模型。提出CDS-based SSCA算法,其为一种基于连通支配集构造树的节点调度机制,每个节点根据剩余能量和与父节点的距离来设置等待时间及成为候选节点优先级。模拟实验结果显示,本算法能够能量有效地满足感知覆盖和连通覆盖要求;与ASW算法相比较,工作节点个数较少,网络生命周期明显延长,降低了网络整体耗能。     

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.     

On the problem of k-coverage in mission-oriented mobile wireless sensor networks

The problem of sensor deployment to achieve k-coverage of a field, where every point is covered by at least k sensors, is very critical in the design of energy-efficient wireless sensor networks (WSNs). It becomes more challenging in mission-oriented WSNs, where sensors have to move in order to k-cover a region of interest in the field. In this type of network, there are multiple missions (or monitoring tasks) to be accomplished, each of which has different requirements, particularly, in terms of coverage. In this paper, we consider the problem of k-coverage in mission-oriented mobile WSNs which we divide into two sub-problems, namely sensor placement and sensor selection. The sensor placement problem is to identify a subset of sensors and their locations in a region of interest so it is k-covered with a small number of sensors. The sensor selection problem is to determine which sensors should move to the above-computed locations in the region while minimizing the total energy consumption due to sensor mobility and communication. Specifically, we propose centralized and distributed approaches to solve the k-coverage problem in mission-oriented mobile WSNs. Our solution to the sensor placement problem is based on Helly’s Theorem and the geometric analysis of the Reuleaux triangle. First, we consider a deterministic (or disk) sensing model, where the sensing range is modeled as a disk. Then, based on the above analysis, we address the k-coverage problem using a more realistic sensing model, known as probabilistic sensing model. The latter reflects the stochastic nature of the characteristics of the sensors, namely sensing and communication ranges. Our centralized and distributed protocols enable the sensors to move toward a region of interest and k-cover it with a small number of sensors. Our experiments show a good match between simulation and analytical results. In particular, simulation results show that our solution to the k-coverage problem in mission-oriented mobile WSNs outperforms an existing one in terms of the number of sensors needed to k-cover a region of interest in the field and their total energy consumption due to communication, sensing, and mobility for the correct operation of the protocol.     

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.     

On redundant coverage maximization in wireless visual sensor networks: Evolutionary algorithms for multi-objective optimization

Wireless visual sensor networks can provide valuable information for a variety of monitoring and control applications. Frequently, a set of targets must be covered by visual sensors, as such visual sensing redundancy is a desired condition specially when applications have availability requirements for multiple coverage perspectives. If visual sensors become rotatable, their sensing orientations can be adjusted to optimize coverage and redundancy, bringing different challenges as there may be different coverage optimization objectives. Actually, the specific issue of redundant coverage maximization is inherently a multi-objective problem, but usual approaches are not designed accordingly to compute visual sensing redundancy. This article proposes two different evolutionary algorithms that exploit the multi-objective nature of the redundant coverage maximization problem: a lexicographic ”a priori” algorithm and a NSGA-II ”a posteriori” algorithm. The performance of both algorithms are compared, using a previously proposed single-objective greedy-based algorithm as a reference. Numerical results outline the benefits of employing evolutionary algorithms for adjustments of sensors’ orientations, potentially benefiting deployment and management of wireless visual sensor networks for different monitoring scenarios.     

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.     

Multi-objective optimization for coverage control in wireless sensor network with adjustable sensing radius

In this paper, the problem of maintaining sensing coverage by keeping a small number of active sensor nodes and a small amount of energy consumption in a wireless sensor network is studied. As opposed to the uniform sensing model previously, we consider a large number of sensors with adjustable sensing radius that are randomly deployed to monitor a target area. A novel coverage control scheme based on elitist non-dominated sorting genetic algorithm (NSGA-II) is proposed in a heterogeneous sensor network. By devising a cluster-based architecture, the algorithm is applied in a distributed way. Furthermore, an ameliorated binary coding is addressed to represent both sensing radius adjustment and sensor selection. Numerical and simulation results validate that the procedure to find the optimal balance point among the maximum coverage rate, the least energy consumption, as well as the minimum number of active nodes is fast and effective.     

一种概率栅栏覆盖模型及其构建算法

K-栅栏覆盖是有向传感器网络的研究热点之一.概率感知模型要比0-1模型更贴近实际.而基于概率感知模型的栅栏覆盖还鲜有研究.根据感知概率阈值和感知距离要求,确定节点的虚拟半径.提出一种二元概率栅栏覆盖模型.在这个模型中,相邻2个节点的虚拟感知圆两两相切.在此基础上提出了最少节点的概率栅栏构建算法(construction of probabilistic barrier of minimum node, CPBMN).首先根据二元概率栅栏模型确定节点的目标位置,再通过匈牙利算法选用移动距离之和最少的移动节点移动到目标位置形成栅栏覆盖,缺少移动节点的子区域,选择附近区域的剩余移动节点修补形成1-栅栏覆盖.水平相邻的2个子区域之间构建竖直栅栏,这些子区域的概率1-栅栏合起来构成整个区域的概率K-栅栏覆盖.仿真结果证明：该方法能够有效形成概率栅栏,最多比其他栅栏构建算法节省70%能耗.     

Optimal energy allocation in heterogeneous wireless sensor networks for lifetime maximization

We consider the problem of optimal energy allocation and lifetime maximization in heterogeneous wireless sensor networks. We construct a probabilistic model for heterogeneous wireless sensor networks where sensors can have different sensing range, different transmission range, different energy consumption for data sensing, and different energy consumption for data transmission, and the stream of data sensed and transmitted from a sensor and the stream of data relayed by a sensor to a base station are all treated as Poisson streams. We derive the probability distribution and the expectation of the number of data transmissions during the lifetime of each sensor and the probability distribution and the expectation of the lifetime of each sensor. In all these analysis, energy consumption of data sensing and data transmission and data relay are all taken into consideration. We develop an algorithm to find an optimal initial energy allocation to the sensors such that the network lifetime in the sense of the identical expected sensor lifetime is maximized. We show how to deal with a large amount of energy budget that may cause excessive computational time by developing accurate closed form approximate expressions of sensor lifetime and network lifetime and optimal initial energy allocation. We derive the expected number of working sensors at any time. Based on such results, we can find the latest time such that the expected number of sensors that are still functioning up to that time is above certain threshold.     

A mobility constraint model to infer sensor behaviour in forest fire risk monitoring

Wireless sensor networks (WSNs) play an important role in forest fire risk monitoring. Various applications are in operation. However, the use of mobile sensors in forest risk monitoring remains largely unexplored. Our research contributes to fill this gap by designing a model which abstracts mobility constraints within different types of contexts for the inference of mobile sensor behaviour. This behaviour is focused on achieving a suitable spatial coverage of the WSN when monitoring forest fire risk. The proposed mobility constraint model makes use of a Bayesian network approach and consists of three components: (1) a context typology describing different contexts in which a WSN monitors a dynamic phenomenon; (2) a context graph encoding probabilistic dependencies among variables of interest; and (3) contextual rules encoding expert knowledge and application requirements needed for the inference of sensor behaviour. As an illustration, the model is used to simulate the behaviour of a mobile WSN to obtain a suitable spatial coverage in low and high fire risk scenarios. It is shown that the implemented Bayesian network within the mobility constraint model can successfully infer behaviour such as sleeping sensors, moving sensors, or deploying more sensors to enhance spatial coverage. Furthermore, the mobility constraint model contributes towards mobile sensing in which the mobile sensor behaviour is driven by constraints on the state of the phenomenon and the sensing system.     

A grid-based coverage approach for target tracking in hybrid sensor networks

Most existing work on the coverage problem of wireless sensor networks focuses on improving the coverage of the whole sensing field. In target tracking, the interested coverage area is the emerging region of a motorized target, not the whole sensing field. As the motorized target moves, the emerging region is also dynamically changed. In this paper, we propose a grid-based and distributed approach for providing large coverage for a motorized target in a hybrid sensor network. The large coverage is achieved by moving mobile sensor nodes in the network. To minimize total movement cost, the proposed approach needs to solve the following problems: the minimum number of mobile sensor nodes used for healing coverage holes and the best matching between mobile sensor nodes and coverage holes. In the proposed approach, the above two problems are first transformed into the modified circle covering and minimum cost flow problems, respectively. Then, two polynomial-time algorithms are presented to efficiently solve these two modified graph problems, respectively. Finally, we perform simulation experiments to show the effectiveness of proposed approach in providing the coverage for a motorized target in a hybrid sensor network.     

A sensor deployment approach using glowworm swarm optimization algorithm in wireless sensor networks

A wireless sensor network is composed of a large number of sensor nodes that are densely deployed in a sensing environment. The effectiveness of the wireless sensor networks depends to a large extent on the coverage provided by the sensor deployment scheme. In this paper, we present a sensor deployment scheme based on glowworm swarm optimization (GSO) to enhance the coverage after an initial random deployment of the sensors. Each sensor node is considered as individual glowworms emitting a luminant substance called luciferin and the intensity of the luciferin is dependent on the distance between the sensor node and its neighboring sensors. A sensor node is attracted towards its neighbors having lower intensity of luciferin and decides to move towards one of them. In this way, the coverage of the sensing field is maximized as the sensor nodes tend to move towards the region having lower sensor density. Simulation results show that our GSO-based sensor deployment approach can provide high coverage with limited movement of the sensor nodes.     

能量有效的无线传感器网络协同覆盖

在节点随机分布的无线传感器网络目标覆盖中,考虑到单个节点有时难以完成对目标的感知,利用节点的概率感知模型和漏检率的概念,提出了节点协同覆盖的思想,并建立了协同覆盖模型;详细分析并推导了协同覆盖感知概率、节点数目和节点参与协同覆盖的最低感知概率之间的关系;在协同覆盖模型的基础上,考虑节点能量消耗的因素,设计了优化网络使用寿命的协同覆盖算法ECTC;仿真结果表明,该算法在改善网络感知概率的同时,延长了网络的使用寿命。     

Cellular automaton-based algorithms for the dispersion of mobile wireless sensor networks

Due to the advent of sensor technology and its applications, mobile wireless sensor networks (MWSNs) have gained a significant amount of research interest. In a typical MWSN, sensors can move within the network. We develop a set of probabilistic and deterministic cellular automaton (CA)-based algorithms for motion planning problems in MWSNs. First, we consider a scenario where a group of sensors are deployed and they need to disperse in order to maximise the area covered by the network. In this variant of the problem we do not explicitly consider that the sensors should maintain the connectivity of the network while they move. Second, we consider a scenario where the sensors are initially randomly distributed and they need to disperse autonomously to both maximise the coverage of the network and maintain its connectivity. We carry out extensive simulations of both deterministic and randomised variants of the algorithms. For the first variant of the problem we compare our algorithms with one previous algorithm and find that our algorithm yields better network coverage than the earlier algorithm. We also find that probabilistic algorithms have better overall performance for the second variant. CA algorithms rely only on local information about the network and, hence, they can be used in practice for MWSN problems. On the other hand, locality of the algorithm implies that maintaining connectivity becomes a non-trivial problem.     

Coverage area enhancement in wireless sensor network

In the wireless sensor network, coverage area may be enhanced after an initial deployment of sensors. Though, some research works propose how to decrease the coverage hole by increasing sensing range or movement assisted sensor deployment, these are not suitable for energy constraint wireless sensor network, as longer mobility distance or higher power level consume more energy. In this paper, we address the increasing coverage area through smaller mobility of nodes. We find out the coverage hole in the monitoring region, which is not covering by any sensing disk of sensor. Then, we address the new position of mobility nodes to increase the coverage area. The simulation result shows the mobile nodes can recover the coverage hole perfectly. The coverage holes is recovered by mobility on the existing recovery area, which cannot be lost. Moreover, hole detection time in our proposed protocol is better than existing algorithm.

     

含障碍物区域的移动传感器网络部署算法*

针对感知区域内含障碍物的移动传感器网络(MSN)的优化问题,提出一种基于免疫算法与维诺图的移动传感器部署算法。共分为两个阶段：第一阶段,使用多目标免疫算法最大化网络覆盖率并最小化MSN移动与感知的能耗,使用维诺图调节传感器的感知范围;第二阶段：采用基于二值抗体的免疫算法调节传感器的状态,在保持高覆盖率的前提下,最小化节点感知与冗余覆盖引起的能耗。多组仿真实验结果显示,本算法对于有、无障碍的两种场景均获得了较好的覆盖率与能耗指标,并实现了较低的处理时间。     

Energy efficient coverage control in wireless sensor networks based on multi-objective genetic algorithm

Due to the constrained energy and computational resources available to sensor nodes, the number of nodes deployed to cover the whole monitored area completely is often higher than if a deterministic procedure were used. Activating only the necessary number of sensor nodes at any particular moment is an efficient way to save the overall energy of the system. A novel coverage control scheme based on multi-objective genetic algorithm is proposed in this paper. The minimum number of sensors is selected in a densely deployed environment while preserving full coverage. As opposed to the binary detection sensor model in the previous work, a more precise detection model is applied in combination with the coverage control scheme. Simulation results show that our algorithm can achieve balanced performance on different types of detection sensor models while maintaining high coverage rate. With the same number of deployed sensors, our scheme compares favorably with the existing schemes.     

基于遗传算法的无线传感器网络重新部署方法

研究了无线传感器网络在受限移动能力条件下的重新部署问题.针对节点的运动模型为跳跃式移动,提出一种基于遗传算法的重新部署算法.算法以节点的跳跃方向为遗传算法的基因,适用度函数同时考虑了最大化覆盖率和最小化移动总距离.仿真实验表明,在各向同性的感测模型中,此算法优于文献[8]提出的FBSD算法,能实现节点的最优运动规划,并且在有向感测模型中,此算法也能有效提高网络覆盖率.     

面向异构网络的基于 k-覆盖的休眠调度算法

异构无线传感网络WSNs(Wireless Sensor Networks)的多数监测应用要求兴趣区域FoI(Field of Interest)是k覆盖(k-cover),且k≥1.而冗余节点被安排为休眠,进而最小化能量消耗.为此,提出面向异构网络的基于k-覆盖的冗余节点休眠算法k-CRSS(k-cover based sleep Scheduling algorithm for redundant node).k-CRSS算法引用概率方法判断节点是否为冗余节点,并推导判断一个节点是否为冗余节点的概率表述式.然后,引用调度算法识别所有冗余节点,并让它们进行休眠,且在FoI内不出现覆盖空洞.k-CRSS算法属分布式算法,并无需任何地理信息,仅通过少量控制消息收集邻居节点信息.实验数据表明,k-CRSS算法通过调度算法减少了活动节点数,进而延长了网络寿命.