Ant colony optimization based sensor deployment protocol for wireless sensor networks

Sensor deployment is one of the most important issues in wireless sensor networks, because an efficient deployment scheme can reduce the deployment cost and enhance the detection capability of the wireless sensor networks. In addition, it can enhance the quality of monitoring in wireless sensor networks by increasing the coverage area. Ant colony optimization (ACO) algorithm provides a natural and intrinsic way of exploration of search space for multiple knapsack problem (MKP). In this work, we consider the problem of sensor deployment to achieve complete coverage of the service region and maximize the lifetime of the network. We model the deployment problem as the multiple knapsack problem. Based on ACO algorithm, we proposed a deployment scheme to prolong the network lifetime, while ensuring complete coverage of the service region. The simulations show that our algorithm can prolong the lifetime of the network.     

An analytical approach to the deployment quality of surveillance wireless sensor networks considering the effect of jammers and coverage holes

The requirements of surveillance wireless sensor networks, such as latency and reliability provisions, are directly related to the deployment quality, which is an indicator of the sensing capability of the network. The determination of the deployment quality is hindered by various factors that cause coverage holes, such as the existence of jammers and destruction of sensors. This paper presents an analytical deployment quality measure in terms of network parameters, including the sensor count, sensing coverage, coverage hole count, coverage hole area size and deployment area size. Assuming a random deployment model for both sensors and holes, our method determines the probability of detection of a target following a linear trajectory by a single sensor and generalizes it to derive the probability of detection in a network with coverage holes. The overall probability of detection is used as the network quality measure and is proposed as a suitable metric under sensor loss assumptions. The proposed deployment quality metric (DQM) is based on the shortest path strategy to provide a conservative estimation for the intruder detection performance. We show that it provides a good estimation of the actual deployment quality with given coverage hole and jamming area properties. Our metric is suitable for real life and simulation scenarios and is computationally inexpensive compared to both simulation based and distributed quality measurements.     

Surveillance with wireless sensor networks in obstruction: Breach paths as watershed contours

For surveillance applications of wireless sensor networks, analysis of sensing coverage and quality of sensing is crucial. For rough terrains where obstacles block the sensing capability, region-based approaches must be employed to determine the sensing quality. In this paper, we present a method to determine the breach paths and the deployment quality defined as the minimum of the maximum detection probabilities on the breach paths in the presence of obstacles. We propose the utilization of watershed segmentation on the iso-sensing map that reveals the equally-sensed regions of the field-of-interest in a surveillance application. Probabilistic sensor models are utilized to produce the iso-sensing map considering the sensing coverage degree and reliability level as the design criteria. The watershed segmentation algorithm is applied on the iso-sensing map to identify the possible breach paths. An algorithm is proposed to convert the watershed segmentation to an auxiliary graph which is then employed to determine the deployment quality measure (DQM). The effects of the sensor count and coverage degree on the DQM are analyzed.     

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.     

A Delaunay Triangulation based method for wireless sensor network deployment

To obtain a satisfied performance of wireless sensor network, an adaptable sensor deployment method for various applications is essential. In this paper, we propose a centralized and deterministic sensor deployment method, DT-Score (Delaunay Triangulation-Score), aims to maximize the coverage of a given sensing area with obstacles. The DT-Score consists of two phases. In the first phase, we use a contour-based deployment to eliminate the coverage holes near the boundary of sensing area and obstacles. In the second phase, a deployment method based on the Delaunay Triangulation is applied for the uncovered regions. Before deploying a sensor, each candidate position generated from the current sensor configuration is scored by a probabilistic sensor detection model. A new sensor is placed to the position with the most coverage gains. According to the simulation results, DT-Score can reach higher coverage than grid-based and random deployment methods with the increasing of deployable sensors.     

矩形截面矿井巷道三维WSN覆盖机理

无线传感器节点在矿井巷道内壁上多采用径向直线型和径向V字型部署。针对矩形截面矿井巷道的无线传感器节点如何在三维空间实现单重无缝覆盖的问题,通过分析巷道几何尺寸,推导出其节点在两种部署类型中的最小感知半径;进一步推导出其节点覆盖密度与节点感知半径、巷道高度、巷道宽度之间的函数关系,比较两种部署类型节点覆盖密度,为现实运用选择节点部署方式提供有力依据。仿真实验验证了推导结果的正确性。利用推导的结论结合矿井的几何尺寸,可直接计算出节点必须满足的最小感知半径、部署方法、部署位置和覆盖密度,从而提高节点覆盖的有效性,减少工程成本支出。     

无线传感器网络多重覆盖问题分析

传感器网络由大量能量有限的微型传感器节点组成.因此,如何保证在足够覆盖监测区域的同时延长网络的寿命,是一个需要解决的重要问题.为了达到这一目标,一种广泛采用的策略是选出部分能够足够覆盖监测区域的节点作为工作节点,同时关闭其他冗余节点.提出了一个数学模型,使得只要已知监测范围和节点感知半径的比值,就可以计算出达到服务质量期望所需要的节点数量.需要指出的是:与大部分研究覆盖的文献不同,该研究不基于节点的位置信息,因此可以极大地降低硬件成本,并且减少节点获得和维护位置信息的开销.模拟实验结果表明:在随机部署条件下,服务质量期望与实验所得到的实际覆盖度的误差不大于服务质量期望的2%;而对于相同的服务质量期望和实际覆盖度,计算所得的工作节点数量与实验所得的工作节点数量的误差小于计算数量的5%,这表明推导出的节点数量与服务质量期望之间的关系与模拟实验的结果相吻合.该结果可以广泛应用于传感器网络的节点部署、拓扑控制等领域中.     

无线传感器网络的节点智能部署方法研究

为满足应用系统对无线传感器网络性能,如覆盖连通质量等方面提出的特定需求,研究了概率感知和通信模型下,保障连通覆盖性能的节点部署问题,提出了基于带精英策略的非支配排序遗传算法的节点智能部署方法。仿真结果显示,在满足应用需求的前提下,提出的部署方法与随机部署和网格部署相比,其需要部署的节点数目明显较少;并且,该方法能得到一组反映目标间制约关系的非支配解,可供用户直观地在多个目标之间进行权衡,并折衷选择部署方案。     

一种基于数据融合的传感器网络部署策略

针对确定性部署问题,提出了一种基于数据融合的部署策略,采用Neyman-Pearson值融合感知模型,通过理论推导确定等边三角形部署和正方形部署网格的最小检测概率点位置,进而得出不同覆盖质量要求和环境参数时两种部署模式下的最大网格边长.基于退避机制的GFA(Grid Fusion Algorithm)融合算法将数据融合...     

A survey on coverage and connectivity issues in wireless sensor networks

A wireless sensor network (WSN) is composed of a group of small power-constrained nodes with functions of sensing and communication, which can be scattered over a vast region for the purpose of detecting or monitoring some special events. The first challenge encountered in WSNs is how to cover a monitoring region perfectly. Coverage and connectivity are two of the most fundamental issues in WSNs, which have a great impact on the performance of WSNs. Optimized deployment strategy, sleep scheduling mechanism, and coverage radius cannot only reduce cost, but also extend the network lifetime. In this paper, we classify the coverage problem from different angles, describe the evaluation metrics of coverage control algorithms, analyze the relationship between coverage and connectivity, compare typical simulation tools, and discuss research challenges and existing problems in this area.     

Design and Analysis of Sensing Scheduling Algorithms under Partial Coverage for Object Detection in Sensor Networks

Object detection quality and network lifetime are two conflicting aspects of a sensor network, but both are critical to many sensor applications such as military surveillance. Partial coverage, where a sensing field is partially sensed by active sensors at any time, is an appropriate approach to balancing the two conflicting design requirements of monitoring applications. Under partial coverage, we develop an analytical framework for object detection in sensor networks, and mathematically analyze average-case object detection quality in random and synchronized sensing scheduling protocols. Our analytical framework facilitates performance evaluation of a sensing schedule, network deployment, and sensing scheduling protocol design. Furthermore, we propose three wave sensing scheduling protocols to achieve bounded worst-case object detection quality. We justify the correctness of our analyses through rigorous proof, and validate the effectiveness of the proposed protocols through extensive simulation experiments     

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.     

Biologically inspired probabilistic coverage for mobile sensor networks

Coupling sensors in a sensor network with mobility mechanism can boost the performance of wireless sensor networks (WSNs). In this paper, we address the problem of self-deploying mobile sensors to reach high coverage. The problem is modeled as a multi-objective optimization that simultaneously minimizes two contradictory parameters; the total sensor moving distance and the total uncovered area. In order to resolve the aforementioned deployment problem, this study investigates the use of biologically inspired mechanisms, including evolutionary algorithms and swarm intelligence, with their state-of-the-art algorithms. Unlike most of the existing works, the coverage parameter is expressed as a probabilistic inference model due to uncertainty in sensor readings. To the best of our knowledge, probabilistic coverage of mobile sensor networks has not been addressed in the context of multi-objective bio-inspired algorithms. Performance evaluations on deployment quality and deployment cost are measured and analyzed through extensive simulations, showing the effectiveness of each algorithm under the developed objective functions. Simulations reveal that only one multi-objective evolutionary algorithm; the so-called multi-objective evolutionary algorithm with decomposition survives to effectively tackle the probabilistic coverage deployment problem. It gathers more than 78 % signals from all of the targets (and in some cases reaches 100 % certainty). On the other hand, non-dominated sorting genetic algorithm II, multi-objective particle swarm optimization, and non-dominated sorting particle swarm optimization show inferior performance down to 16–32 %, necessitating further modifications in their internal mechanisms.     

A Lagrangean relaxation based sensor deployment algorithm to optimize quality of service for target positioning

The target positioning service is one of useful applications for wireless sensor networks. So far, most papers considered traditional uniform quality of services (QoS) for target positioning in sensing fields. However, it is possible that all regions in a sensing field have different requirements for target positioning accuracy. We also concern the terrain of sensing fields might have some limitations for placing sensors. Therefore, this paper proposes a generic framework for the sensor deployment problem supporting differential quality of services (QoS) for target positioning to all regions in a sensing field. We define weighted error distance as metric of quality of positioning services. This problem is to optimize the QoS level for target positioning under the limitations of budget and discrimination priorities of regions, where locations and sensing radiuses of all sensors should be determined. We formulate the problem as a nonlinear integer programming problem where the objective function is to minimize of the maximum weighted error distance subject to the complete coverage, deployment budget, and discrimination priority constraints. A Lagrangean relaxation (LR) based heuristic is developed to solve the NP-hard problem. Experimental results reveal that the proposed framework can provide better quality of services for positioning than the previous researches, which only handles uniform QoS requirements. Moreover we evaluate the performance of proposed algorithm. As well as we adopt the previous algorithm, ID-CODE, as the benchmark to examine the proposed heuristic. The results show the proposed algorithm is very effective in terms of deployment cost.     

Optimal movement-assisted sensor deployment and its extensions in wireless sensor networks

In wireless sensor networks (WSNs), a good sensor deployment method is vital to the quality of service (QoS) provided by WSNs. This QoS depends on the coverage of the monitoring area. In WSNs with locomotion facilities, sensors can move around and self-deploy to ensure coverage and load balancing, where each unit of monitoring area is covered by the same number of sensors. The movement-assisted sensor deployment deals with moving sensors to meet coverage and load balancing requirements. In SMART [J. Wu, S. Yang, SMART: a scan-based movement-assisted sensor deployment method in wireless sensor networks, in: Proceedings of INFOCOM, 2005], various optimization problems are defined to minimize different parameters, including total moving distance, total number of moves, communication/computation cost, and convergence rate. In this paper, we focus on minimizing the total moving distance and propose an optimal, but centralized solution, based on the Hungarian method. This solution is illustrated in an application where the monitoring area is a 2-D grid-based mesh. We then propose several efficient, albeit non-optimal, distributed solutions based on the scan-based solution in Wu and Yang (2005). Extensive simulations have been done to verify the effectiveness of the proposed distributed solutions.     

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.

     

一种改进的无线传感器网络节点部署方案

现有的无线传感器网络节点部署方案需要额外探测和修复边界上的覆盖空洞,增加了网络部署的成本,且节点分布不均匀.为此,提出一种改进的节点部署方案.通过边界部署保证边界上的完全覆盖和连通,在感应区域内生成一个新的凸多边形区域,在新区域上递归调用边界部署算法,直到整个感应区域被完全覆盖.理论分析和仿真实验结果表明,该方案能够保证网络的1-连通性和完全覆盖,消除任务区域存在的边界效应,在部署节点个数和可扩展性方面均优于已有的部署方案.     

Efficient terrain coverage for deploying wireless sensor nodes on multi-robot system

Coverage and connectivity are the two main functionalities of wireless sensor network. Stochastic node deployment or random deployment almost always cause hole in sensing coverage and cause redundant nodes in area. In the other hand precise deployment of nodes in large area is very time consuming and even impossible in hazardous environment. One of solution for this problem is using mobile robots with concern on exploration algorithm for mobile robot. In this work an autonomous deployment method for wireless sensor nodes is proposed via multi-robot system which robots are considered as node carrier. Developing an exploration algorithm based on spanning tree is the main contribution and this exploration algorithm is performing fast localization of sensor nodes in energy efficient manner. Employing multi-robot system and path planning with spanning tree algorithm is a strategy for speeding up sensor nodes deployment. A novel improvement of this technique in deployment of nodes is having obstacle avoidance mechanism without concern on shape and size of obstacle. The results show using spanning tree exploration along with multi-robot system helps to have fast deployment behind efficiency in energy.     

Scan-Based Movement-Assisted Sensor Deployment Methods in Wireless Sensor Networks

The efficiency of sensor networks depends on the coverage of the monitoring area. Although, in general, a sufficient number of sensors are used to ensure a certain degree of redundancy in coverage, a good sensor deployment is still necessary to balance the workload of sensors. In a sensor network with locomotion facilities, sensors can move around to self-deploy. The movement-assisted sensor deployment deals with moving sensors from an initial unbalanced state to a balanced state. Therefore, various optimization problems can be defined to minimize different parameters, including total moving distance, total number of moves, communication/computation cost, and convergence rate. In this paper, we first propose a Hungarian-algorithm-based optimal solution, which is centralized. Then, a localized scan-based movement-assisted sensor deployment method (SMART) and several variations of it that use scan and dimension exchange to achieve a balanced state are proposed. An extended SMART is developed to address a unique problem called communication holes in sensor networks. Extensive simulations have been done to verify the effectiveness of the proposed scheme.     

改进QGA在WSNs节点部署中的应用

对含有障碍区域的无线传感器网络（WSNs）节点部署问题进行研究。建立节点探测模型和网络覆盖率评价方法,基于概率传感器模型提出一种部署方式,即对障碍区域进行随机布撒节点,确定区域采用量子遗传算法（QGA）寻找最优节点部署位置,实现对同构WSNs节点构成的目标区域的高效覆盖。仿真结果与GA,QGA相比：改进QGA有效提高了算法整体的搜索能力和收敛速度。