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.     

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.     

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

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

Lightweight Deployment-Aware Scheduling for Wireless Sensor Networks

Wireless sensor networks consist of a large number of tiny sensors that have only limited energy supply. One of the major challenges in constructing such networks is to maintain long network lifetime as well as sufficient sensing areas. To achieve this goal, a broadly-used method is to turn off redundant sensors. In this paper, the problem of estimating redundant sensing areas among neighbouring wireless sensors is analysed. We present simple methods to estimate the degree of redundancy without the knowledge of location or directional information. We also provide tight upper and lower bounds on the probability of complete redundancy and on the average partial redundancy. With random sensor deployment, our analysis shows that partial redundancy is more realistic for real applications, as complete redundancy is expensive, requiring up to 11 neighbouring sensors to provide a 90 percent chance of complete redundancy. Based on the analysis, we propose a scalable Lightweight Deployment-Aware Scheduling (LDAS) algorithm, which turns off redundant sensors without using accurate location information. Simulation study demonstrates that the LDAS algorithm can reduce network energy consumption and provide desired QoS requirement effectively. This research was partially supported by Natural Sciences and Engineering Research Council of Canada. Kui Wu received his Ph.D. in Computing Science from the University of Alberta, Canada, in 2002. He joined the Department of Computer Science at the University of Victoria, Canada in the same year and is currently an Assistant Professor there. His research interests include mobile and wireless networks, network performance evaluation, and network security. Yong Gao received his Master's degree and Ph.D. degree in computer science from University of Alberta, Canada, in 2000 and 2005 respectively. He is currently with the Irving K. Barber School of Arts and Sciences, UBC Okanagan, Canada. His research interests include search algorithms and AI, communication networks, and computational biology. Yang Xiao worked at Micro Linear as an MAC (Medium Access Control) architect involving the IEEE 802.11 standard enhancement work before he joined Department of Computer Science at The University of Memphis in 2002. Dr. Xiao is an IEEE Senior member. He was a voting member of IEEE 802.11 Working Group from 2001 to 2004. He currently serves as Editor-in-Chief for International Journal of Security and Networks (IJSN) and for International Journal of Sensor Networks (IJSNet). He serves as an associate editor or on editorial boards for the following refereed journals: (Wiley) International Journal of Communication Systems, (Wiley) Wireless Communications and Mobile Computing (WCMC), EURASIP Journal on Wireless Communications and Networking, and International Journal of Wireless and Mobile Computing. He serves as five lead/sole guest editor for five journal special issues. He serves as a referee/reviewer for many funding agencies, as well as a panelist for NSF. His research interests are Security/ Reliable Communications, Medium Access Control, Mobility/Location/Paging Managements, Cache Access and Replacement Policies, Quality of Service, Energy Efficiency, and Routing in wireless networks and mobile computing.     

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.     

无线传感网络部分覆盖技术研究展望

在无线传感网络(Wireless Sensor Networks,WSN)技术中,各传感节点覆盖区域的研究是这项技术应用的基础课题.文章对国外最近提出的部分覆盖技术进行了收集整理,对其技术特性做了分析和对比.从覆盖度、节点分布特性、节点类型以及网络拓扑结构4方面对这些技术进行比较.最后,对部分覆盖技术的未来可能的研究方...     

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…     

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.     

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.     

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.     

A pragmatic approach to area coverage in hybrid wireless sensor networks

Success of Wireless Sensor Networks (WSN) largely depends on whether the deployed network can provide desired area coverage with acceptable network lifetime. This paper seeks to address the problem of determining the current coverage achieved by the non‐deterministic deployment of static sensor nodes and subsequently enhancing the coverage using mobile sensors. We identify three key elements that are critical for ensuring effective area coverage in Hybrid WSN: (i) determining the boundary of the target region and evaluating the area coverage (ii) locating coverage holes and maneuvering mobile nodes to fill these voids, and (iii) maintaining the desired coverage over the entire operational lifetime of the network. We propose a comprehensive solution that addresses all of the aforementioned aspects of the area coverage, called MAPC (mobility assisted probabilistic coverage). MAPC is a distributed protocol that operates in three distinct phases. The first phase identifies the boundary nodes using the geometric right‐hand rule. Next, the static nodes calculate the area coverage and identify coverage holes using a novel probabilistic coverage algorithm (PCA). PCA incorporates realistic sensing coverage model for range‐based sensors. The second phase of MAPC is responsible for navigating the mobile nodes to plug the coverage holes. We propose a set of coverage and energy‐aware variants of the basic virtual force algorithm (VFA). Finally, the third phase addresses the problem of coverage loss due to faulty and energy depleted nodes. We formulate this problem as an Integer Linear Program (ILP) and propose practical heuristic solutions that achieve similar performance as that of the optimal ILP solution. A guiding principle in our design process has been to ensure that the MAPC can be readily implemented in real‐world applications. We implemented the boundary detection and PCA algorithm (i.e., Phase I) of the MAPC protocol on off‐the‐shelf sensor nodes and results show that the MAPC can successfully identify boundary nodes and accurately determine the area coverage in the presence of real radio irregularities observed during the experiments. Extensive simulations were carried out to evaluate the complete MAPC protocol and the results demonstrate that MAPC can enhance and maintain the area coverage, while reducing the total energy consumption by up to 70% as compared with the basic VFA. Copyright © 2010 John Wiley & Sons, Ltd.     

Minimal exposure path algorithms for directional sensor networks

As a fundamental problem of wireless sensor networks, the minimal exposure path problem corresponding to the sensor network's worst‐case coverage plays an important role in the applications for detecting intrusions. However, most existing works about minimal exposure path are based on omnidirectional sensors. In contrast, this paper studies the minimal exposure path problem for two different types of directional sensing models: the binary sector model and directional sensitivity model. For the binary sector model, we construct a special Voronoi diagram, called sector centroids‐based Voronoi diagram, to transform the minimal exposure path problem from a continuous geometric problem into a discrete geometric problem. By using the sector centroids‐based Voronoi diagram, we develop an approximate algorithm to find the minimal exposure path in the sensors deployment field. For the directional sensitive model, we formulate the minimal exposure path problem by using two sensing intensity functions: all‐sensor intensity function and maximum‐sensor intensity function and then generate two weighted grids to convert the minimal exposure path problem into two discrete geometric problems. On the basis of the aforementioned weighted grids, we also develop two approximation algorithms to find the minimal exposure path for the directional sensitive model. We conduct extensive experiment simulations to validate and evaluate our proposed models and algorithms. Copyright © 2012 John Wiley & Sons, Ltd.     

基于无线传感器网络汇聚传输实时性的分布式调度算法

在无线传感器网络多种应用中,各节点需要在短时间内将采集的数据传输至汇聚节点,从而形成多对一的汇聚传输。针对网络汇聚传输的实时性,提出了一种分布式的节点传输调度算法。各节点只需要根据一跳范围内的邻居信息进行传输调度。仿真和分析表明该算法可以有效避免数据碰撞,并使得完成一次全网数据收集所需要的时隙数基本在网络节点总数的1.6到1.8倍左右,比目前其他调度算法在实时性和复杂度方面更具有优势。     

信息扩散在无线传感器网络中的应用

首先假定在一个动态、实时的大型楼宇式停车场环境中,使用无线传感器网来支持信息查询和导航系统。基于扩散方程和泊松公式,提出一种新颖的信息查询和导航方法,该方法能够更便捷、有效地完成导航系统进程。从信息导航理论研究的角度来分析,一般假定研究工作的环境是理想状态,受到很少的限制,同时假定实际中一些错误的导航进程可以得到更正。为了达到导航系统的精确性,首次应用了信息传播、电势场以及偏微分方程（扩散方程）的相关知识,同时将梯度下降法应用于该算法。在研究过程中,采用了完整的数学推导。模拟实验表明,该方法准确方便,并且高效地克服了典型传感器网络配置信息导航系统最优解较难快速获得和存在竞争冲突的弱点。同时,扩散方程的结构也更具灵活性和适应性。导航性能也有较大提高,还可避免甚至消除竞争冲突。另外,热扩散方程的灵活使用克服了原有调和函数方法强约束的缺点,取得了模型降阶的效果。     

Providing and finding k‐road‐coverage efficiently in wireless sensor networks

In this paper, we study k‐road‐coverage problems in wireless sensor networks (WSNs). Assume there is a 2‐dimensional area Ω with a given road map = (V,E) where E contains all road segments and V consists of all intersection points on Ω. The first question we study is about ‘sensor deployment’, i.e., how to deploy a minimum number of sensor nodes on Ω such that each path (each road segment) on is k‐covered when all sensor nodes have the same sensing range. When sensors can only be deployed in a set of discrete locations, we propose an efficient method with the approximation ratio 6 + ϵ for the special case where k = 1 and O(k) generally. If sensors can be deployed in arbitrary locations, we propose an efficient method with the approximation ratio 24 + ϵ when k = 1 and O(k) generally. The second question we study is about ‘path query’, i.e., how to find the k‐covered path or k‐support path connecting any given source/destination pair of points on the road map . Basically, given any source/destination pair of points S and D, we present two algorithms which can efficiently find a k‐covered path connecting S and D and a k‐supported path connecting S and D, respectively. Copyright © 2010 John Wiley & Sons, Ltd.     

传感器网络中运动目标检测与定位

传感器网络综合了传感器、网络和无线通信等多种技术,成为近几年来网络技术和传感器技术发展的一个热门领域.对传感器网络中运动的车辆进行了检测和定位.首先利用恒虚警检测方法判断是否有目标被检测,在检测出目标的前提下,分别利用直接搜索法和卡尔曼滤波方法对目标定位,最后对仿真结果进行了比较.     

Secure coverage-preserving node scheduling scheme using energy prediction for wireless sensor networks

With the fast development of the micro-electro-mechanical systems(MEMS),wireless sensor networks(WSNs)have been extensively studied.Most of the studies focus on saving energy consumption because of restricted energy supply in WSNs.Cluster-based node scheduling scheme is commonly considered as one of the most energy-efficient approaches.However,it is not always so efficient especially when there exist hot spot and network attacks in WSNs.In this article,a secure coverage-preserved node scheduling scheme for WSNs based on energy prediction is proposed in an uneven deployment environment.The scheme is comprised of an uneven clustering algorithm based on arithmetic progression,a cover set partition algorithm based on trust and a node scheduling algorithm based on energy prediction.Simulation results show that network lifetime of the scheme is 350 rounds longer than that of other scheduling algorithms.Furthermore,the scheme can keep a high network coverage ratio during the network lifetime and achieve the designed objective which makes energy dissipation of most nodes in WSNs balanced.     

Localized algorithms for coverage boundary detection in wireless sensor networks

Connected coverage, which reflects how well a target field is monitored under the base station, is the most important performance metric used to measure the quality of surveillance that wireless sensor networks (WSNs) can provide. To facilitate the measurement of this metric, we propose two novel algorithms for individual sensor nodes to identify whether they are on the coverage boundary, i.e., the boundary of a coverage hole or network partition. Our algorithms are based on two novel computational geometric techniques called localized Voronoi and neighbor embracing polygons. Compared to previous work, our algorithms can be applied to WSNs of arbitrary topologies. The algorithms are fully distributed in the sense that only the minimal position information of one-hop neighbors and a limited number of simple local computations are needed, and thus are of high scalability and energy efficiency. We show the correctness and efficiency of our algorithms by theoretical proofs and extensive simulations. Chi Zhang received the B.E. and M.E. degrees in Electrical Engineering from Huazhong University of Science and Technology, Wuhan, China, in July 1999 and January 2002, respectively. Since September 2004, he has been working towards the Ph.D. degree in the Department of Electrical and Computer Engineering at the University of Florida, Gainesville, Florida, USA. His research interests are network and distributed system security, wireless networking, and mobile computing, with emphasis on mobile ad hoc networks, wireless sensor networks, wireless mesh networks, and heterogeneous wired/wireless networks. Yanchao Zhang received the B.E. degree in computer communications from Nanjing University of Posts and Telecommunications, Nanjing, China, in July 1999, the M.E. degree in computer applications from Beijing University of Posts and Telecommunications, Beijing, China, in April 2002, and the Ph.D. degree in electrical and computer engineering from the University of Florida, Gainesville, in August 2006. Since September 2006, he has been an Assistant Professor in the Department of Electrical and Computer Engineering, New Jersey Institute of Technology, Newark. His research interest include wireless and Internet security, wireless networking, and mobile computing. He is a member of the IEEE and ACM. Yuguang Fang received the BS and MS degrees in Mathematics from Qufu Normal University, Qufu, Shandong, China, in 1984 and 1987, respectively, a Ph.D. degree in Systems and Control Engineering from Department of Systems, Control and Industrial Engineering at Case Western Reserve University, Cleveland, Ohio, in January 1994, and a Ph.D. degree in Electrical Engineering from Department of Electrical and Computer Engineering at Boston University, Massachusetts, in May 1997. From 1987 to 1988, he held research and teaching position in both Department of Mathematics and the Institute of Automation at Qufu Normal University. From September 1989 to December 1993, he was a teaching/research assistant in Department of Systems, Control and Industrial Engineering at Case Western Reserve University, where he held a research associate position from January 1994 to May 1994. He held a post-doctoral position in Department of Electrical and Computer Engineering at Boston University from June 1994 to August 1995. From September 1995 to May 1997, he was a research assistant in Department of Electrical and Computer Engineering at Boston University. From June 1997 to July 1998, he was a Visiting Assistant Professor in Department of Electrical Engineering at the University of Texas at Dallas. From July 1998 to May 2000, he was an Assistant Professor in the Department of Electrical and Computer Engineering at New Jersey Institute of Technology, Newark, New Jersey. In May 2000, he joined the Department of Electrical and Computer Engineering at University of Florida, Gainesville, Florida, where he got early promotion to Associate Professor with tenure in August 2003, and to Full Professor in August 2005. His research interests span many areas including wireless networks, mobile computing, mobile communications, wireless security, automatic control, and neural networks. He has published over one hundred and fifty (150) papers in refereed professional journals and conferences. He received the National Science Foundation Faculty Early Career Award in 2001 and the Office of Naval Research Young Investigator Award in 2002. He also received the 2001 CAST Academic Award. He is listed in Marquis Who’s Who in Science and Engineering, Who’s Who in America and Who’s Who in World. Dr. Fang has actively engaged in many professional activities. He is a senior member of the IEEE and a member of the ACM. He is an Editor for IEEE Transactions on Communications, an Editor for IEEE Transactions on Wireless Communications, an Editor for IEEE Transactions on Mobile Computing, an Editor for ACM Wireless Networks, and an Editor for IEEE Wireless Communications. He was an Editor for IEEE Journal on Selected Areas in Communications:Wireless Communications Series, an Area Editor for ACM Mobile Computing and Communications Review, an Editor for Wiley International Journal on Wireless Communications and Mobile Computing, and Feature Editor for Scanning the Literature in IEEE Personal Communications. He has also actively involved with many professional conferences such as ACM MobiCom’02 (Committee Co-Chair for Student Travel Award), MobiCom’01, IEEE INFOCOM’06, INFOCOM’05 (Vice-Chair for Technical Program Committee), INFOCOM’04, INFOCOM’03, INFOCOM’00, INFOCOM’98, IEEE WCNC’04, WCNC’02, WCNC’00 Technical Program Vice-Chair), WCNC’99, IEEE Globecom’04 (Symposium Co-Chair), Globecom’02, and International Conference on Computer Communications and Networking (IC3N) (Technical Program Vice-Chair).     

无线多媒体传感器网络部署控制算法

已有的无线多媒体传感器网络（WMSNs）研究针对传感器放置在目标区域内的情况进行,且没有考虑节点通过云台的转动获得的整个可能感知区域对覆盖率的影响。本文首先针对节点放置点高于目标区域的应用进行研究,综合考虑节点感知区域和可能感知区域,建立了延时和无延时感知模型,并针对不同的感知模型提出了传感器网络部署控制算法（IVPDCA）,算法中改进了虚拟势场算法,定义了节点质量的概念来表示节点间覆盖重叠的大小,建立受力模型,使得节点在合力作用下进行重新部署,同时关闭冗余节点,既延长了网络寿命,又提高了区域覆盖率。仿真结果验证了算法的有效性。     

有向传感器网络覆盖控制策略

针对当前的有向传感器网络覆盖控制算法中主要存在的节点方向调节受限、优化程度有限、算法适用性单一等问题,提出了一种有向传感器网络覆盖控制策略(CCS,coverage control strategy),该策略经过严格的数学推导,形成一个分布式算法,能够广泛适用于不同网络下的不同节点感知模型。仿真实验表明,传感器节点运行CCS能够有效增强网络覆盖,并相比于现有的几种同类算法,具有一定的优越性。