Efficient and accurate sensor network localization

Wireless sensor networks (WSN) have great potential in ubiquitous computing. However, the severe resource constraints of WSN rule out the use of many existing networking protocols and require careful design of systems that prioritizes energy conservation over performance optimization. A key infrastructural problem in WSN is localization—the problem of determining the geographical locations of nodes. WSN typically have some nodes called seeds that know their locations using global positioning systems or other means. Non-seed nodes compute their locations by exchanging messages with nodes within their radio range. Several algorithms have been proposed for localization in different scenarios. Algorithms have been designed for networks in which each node has ranging capabilities, i.e., can estimate distances to its neighbours. Other algorithms have been proposed for networks in which no node has such capabilities. Some algorithms only work when nodes are static. Some other algorithms are designed specifically for networks in which all nodes are mobile. We propose a very general, fully distributed localization algorithm called range-based Monte Carlo boxed (RMCB) for WSN. RMCB allows nodes to be static or mobile and that can work with nodes that can perform ranging as well as with nodes that lack ranging capabilities. RMCB uses a small fraction of seeds. It makes use of the received signal strength measurements that are available from the sensor hardware. We use RMCB to investigate the question: “When does range-based localization work better than range-free localization?” We demonstrate using empirical signal strength data from sensor hardware (Texas Instruments EZ430-RF2500) and simulations that RMCB outperforms a very good range-free algorithm called weighted Monte Carlo localization (WMCL) in terms of localization error in a number of scenarios and has a similar computational complexity to WMCL. We also implement WMCL and RMCB on sensor hardware and demonstrate that it outperforms WMCL. The performance of RMCB depends critically on the quality of range estimation. We describe the limitations of our range estimation approach and provide guidelines on when range-based localization is preferable.     

Sensor selection for parameterized random field estimation in wireless sensor networks

We consider the random field estimation problem with parametric trend in wireless sensor networks where the field can be described by unknown parameters to be estimated. Due to the limited resources, the network selects only a subset of the sensors to perform the estimation task with a desired performance under the D-optimal criterion. We propose a greedy sampling scheme to select the sensor nodes according to the information gain of the sensors. A distributed algorithm is also developed by consensus-based ...     

A localization algorithm for large scale mobile wireless sensor networks: a learning approach

Localization is a crucial problem in wireless sensor networks and most of the localization algorithms given in the literature are non-adaptive and designed for fixed sensor networks. In this paper, we propose a learning based localization algorithm for mobile wireless sensor networks. By this technique, mobility in the network will be discovered by two crucial methods in the beacons: position and distance checks methods. These two methods help to have accurate localization and constrain communication just when it is necessary. The proposed method localizes the nodes based on connectivity information (hop count), which doesn’t need extra hardware and is cost efficient. The experimental results show that the proposed algorithm is scalable with a small set of beacons in large scale network with a high density of nodes. The given algorithm is fast and free from a pre-deployment requirement. The simulation results show the high performance of the proposed algorithm.     

基于苯环结构的WSNs单向链路故障检测算法

在无线传感器网络（ WSNs）中提出的许多路由算法因其真实应用场景下存在大量单向链路而使其性能大幅降低,甚至无法正常工作。对此如何在WSNs中实现准确、高效能单向链路故障检测成为一个重要的研究课题。针对这种情况提出了一种基于Hello报文的单向链路故障检测（ ALFD-H）算法,该算法充分利用WSNs组成的苯环网络模型,由苯环中心节点发起周期检测信号来完成单向链路故障检测。通过苯环中心节点处理故障单向链路来控制报文数量降低网络资源的消耗,并且提高了网络的连通性和可扩展性。通过NS2仿真实验结果表明：ALFD-H相较传统检测算法采用了苯环网络模型,减少了用于故障检测的能量消耗,从而大大延长了节点的工作时间和网络的生命周期。     

WSN节点的粒计算网格化定位算法

接收信号强度作为一种低功率廉价的测距方式而用于估计无线传感器网络的节点位置,但定位精度会受到时空传播介质的影响,构造快速算法是解决该问题的主要方法之一。对定位区域网格化,提出了基于粒计算的快速网格化定位算法。将定位问题转化为分类问题,利用粒计算分类算法,得到定位参数,估计未知节点的位置。实验结果表明与支持向量机定位相比粒计算网格化定位算法降低了定位误差和时间。     

灰洞检测：基于链路质量估计的看门狗算法

传感器网络中的数据传输依靠节点间的合作,但是节点被入侵者俘获而成为恶意节点后会发起灰洞攻击,从而大幅降低网络性能。现有的检测算法主要依靠统计节点的接收转发行为来检测灰洞。但是传感器网络的链路质量会导致节点的自然丢包,现有检测算法难以有效区分。针对此问题本文提出基于链路质量估计的看门狗算法以及最优阈值理论,利用链路质量来修正节点的统计结果,根据网络环境调整参数,最小化误报、漏报概率,提高算法正确率。仿真实验结果表明本文提出的算法能够有效地降低检测误报、漏报率。     

动态组簇的协同定位算法

提出一种动态组簇的协同定位方法,用于基于传感器网络的目标定位和跟踪.该方法包括数据融合算法和虚拟簇漂移(virtual cluster shift,VCS)机制两部分.数据融合算法部分采用均值漂移(mean shift)算法.虚拟簇漂移机制分布式地在组织目标周围的锚节点建立临时簇.簇首管理簇成员,收集感知数据,执行融合算法.当虚拟簇无法锁定目标时,簇首指定离目标最近的簇成员担任新簇首,簇的成员也进行更替,由此将虚拟簇移动(shift)到合适的位置.分析和仿真结果显示,采用动态组簇的协同定位方法跟踪目标可以大幅度降低通信开销,产生的通信量仅为以往集中式定位算法开销的1/3.     

Co-designed anchor-free localization and location-based routing algorithm for rapidly-deployed wireless sensor networks

We consider a wireless sensor network consisting of a single sink node at the center of a field of randomly distributed sensors. A simple anchor-free localization algorithm is proposed, in which the sink node imparts radial location information through the phased-array transmission of a series of beacons. Each individual sensor uses the knowledge of received beacons as well as information from neighbors to continue partitioning current sectors and identifying sub-sectors in which it resides until an accuracy requirement is satisfied. An energy-preserving routing algorithm is then proposed which uses the localization results as the basis for selecting relay nodes. We present the localization algorithm, analyze its partition errors as well as its impact on communication energy consumption, and then present the location-based routing algorithm. Simulation results indicate that the performance of our co-designed localization and routing algorithm in the presence of severe noise is as good as that provided by a shortest-path routing algorithm under ideal assumptions; therefore, our co-designing approach can achieve high performance with lightweight algorithms.     

Distributed Localization Using a Moving Beacon in Wireless Sensor Networks

The localization of sensor nodes is a fundamental problem in sensor networks and can be implemented using powerful and expensive beacons. Beacons, the fewer the better, can acquire their position knowledge either from GPS devices or by virtue of being manually placed. In this paper, we propose a distributed method to localization of sensor nodes using a single moving beacon, where sensor nodes compute their position estimate based on the range-free technique. Two parameters are critical to the location accuracy of sensor nodes: the radio transmission range of the beacon and how often the beacon broadcasts its position. Theoretical analysis shows that these two parameters determine the upper bound of the estimation error when the traverse route of the beacon is a straight line. We extend the position estimate when the traverse route of the beacon is randomly chosen in a real-world situation, where the radio irregularity might cause a node to miss some crucial coordinate information from the beacon. We further point out that the movement pattern of the beacon plays a pivotal role in the localization task for sensors. To minimize estimation errors, sensor nodes can carry out a variety of algorithms in accordance with the movement of the beacon. Simulation results compare variants of the distributed method in a variety of testing environments. Real experiments show that the proposed method is feasible and can estimate the location of sensor nodes accurately, given a single moving beacon.     

基于最大似然估计的加权质心定位算法

为解决无线传感器网络中节点自身定位问题,针对接收信号强度指示（received signal strength indication,RSSI）测距误差大和质心定位算法精度低的问题,提出一种基于最大似然估计的加权质心定位算法．首先通过计算将估计距离与实际距离之间的最大似然估计值作为权值,然后在权值模型中,引进一个参数k优化未知节点周围锚节点分布,最后计算出未知节点的位置并加以修正．仿真结果表明,基于最大似然估计的加权质心算法具有定位精度高和成本低的特点,优于基于距离倒数的质心加权和基于RSSI倒数的质心加权算法,适用于大面积的室内定位．     

On computing mobile agent routes for data fusion in distributed sensor networks

The problem of computing a route for a mobile agent that incrementally fuses the data as it visits the nodes in a distributed sensor network is considered. The order of nodes visited along the route has a significant impact on the quality and cost of fused data, which, in turn, impacts the main objective of the sensor network, such as target classification or tracking. We present a simplified analytical model for a distributed sensor network and formulate the route computation problem in terms of maximizing an objective function, which is directly proportional to the received signal strength and inversely proportional to the path loss and energy consumption. We show this problem to be NP-complete and propose a genetic algorithm to compute an approximate solution by suitably employing a two-level encoding scheme and genetic operators tailored to the objective function. We present simulation results for networks with different node sizes and sensor distributions, which demonstrate the superior performance of our algorithm over two existing heuristics, namely, local closest first and global closest first methods.     

A destination-based approach for cut detection in wireless sensor networks

Wireless sensor networks often suffer from disrupted connectivity caused by its numerous aspects such as limited battery power of a node and unattended operation vulnerable to hostile tampering. The disruption of connectivity, often referred to as network cut, leads to ill-informed routing decisions, data loss and waste of energy. A number of protocols have been proposed to efficiently detect network cuts; they focus solely on a cut that disconnects nodes from the base station. However, a cut detection scheme is truly useful when a cut is defined with respect to multiple destinations (i.e. target nodes), rather than a single base station. Thus, we extend the existing notion of cut detection, and propose an algorithm that enables sensor nodes to autonomously monitor the connectivity to multiple target nodes. We introduce a novel reactive cut detection solution, the point-to-point cut detection, where given any pair of source and destination, a source is able to locally determine whether the destination is reachable or not. Furthermore, we propose a lightweight proactive cut detection algorithm specifically designed for a network scenario with a small set of target destinations. We prove the effectiveness of the proposed algorithms through extensive simulations; specifically, in our network configurations, proposed cut detection algorithms achieve more than an order of magnitude improvement in energy consumption, when coupled with an underlying routing protocol.     

基于优化策略的混合定位算法

针对无线传感器网络(Wireless sensor network, WSN)的应用需求提出一种基于优化策略的混合节点定位算法. 选择1-hop节点最多的点作为初始点, 利用多维标度(Multi-dimensional scaling, MDS)方法计算初始节点及其1-hop节点的相对坐标, 并将这些节点的坐标发送给周围未定位节点; 未定位的节点根据接收到的坐标与节点间的距离, 利用极大似然法估算自身的坐标; 最后通过坐标变换计算所有节点的绝对坐标. 在此基础上, 进一步提出将本文节点定位算法与集中式和分布式优化策略相结合来优化网络节点的估计坐标, 以提高节点定位精度. 仿真结果表明本文提出的算法是有效的, 能够较好地完成无线传感器网络节点的定位.     

相似度优化的无线传感器网络移动节点定位

针对无线传感器网络中移动节点的定位特性,提出了一种利用序列相似度改进的蒙特卡洛定位算法.该算法先利用各信标节点的信号强度值对移动节点初定位,优化原算法的采样区域.同时将信号值存储为目标序列,通过比较信标节点和样本点间序列与目标序列的相似度过滤样本点,并以相似度值作为加权标准计算移动节点坐标.仿真结果表明,与其他算法相比,在不同的信标节点密度下,定位误差减少了1%~10%,在不同的节点最大移动速度的情况下,定位误差减少了30%~40%.     

无线传感器网络中基于虚拟力的分布式节点定位

节点定位是无线传感器网络应用中需要解决的一个基本问题。传统算法大都基于集中式方法估计节点位置,从而导致较大开销。因此,结合最小二乘法进行初步估计定位,并在此基础上,给出了基于虚拟力的传感器节点定位模型,提出了基于虚拟力的分布式定位算法,该算法通过邻居节点间信息的分布式交互,能够有效节省定位开销。进一步,在定位过程中引入未知节点升级机制,以提高收敛速度。一系列仿真实验表明,该算法能够通过分布式迭代定位,快速实现全网节点的精确定位。     

Distributed classification of acoustic targets in wireless audio-sensor networks

Target tracking is an important application for wireless sensor networks. One important aspect of tracking is target classification. Classification helps in selecting particular target(s) of interest. In this paper, we address the problem of classification of moving ground vehicles. The basis of classification are the audible signals produced by these vehicles. We present a distributed framework to classify vehicles based on features extracted from acoustic signals of vehicles. The main features used in our study are based on FFT (fast Fourier transform) and PSD (power spectral density). We propose three distributed algorithms for classification that are based on the k-nearest neighbor (k-NN) classification method. An experimental study has been conducted using real acoustic signals of different vehicles recorded in the city of Edmonton. We compare our proposed algorithms with a naive distributed implementation of the k-NN algorithm. Performance results reveal that our proposed algorithms are energy efficient, and thus suitable for sensor network deployment.     

网络中多节点故障定位的探测路径选择算法

针对现有故障定位技术不能满足多节点故障定位的要求,尤其当网络中存在大量故障节点时,提出了一种基于主动探测的探测路径选择算法。该算法主要包括用于故障检测的贪婪路径选择算法和用于故障定位的禁忌链路搜索算法。在故障检测阶段,使用贪婪路径选择算法迭代地选择具有最小权重的探测路径覆盖网络中的节点。在故障定位阶段,使用禁忌链路搜索算法多次生成候选路径集以选择最合适的探测路径来解决多节点故障定位问题。在随机网络拓扑和真实网络拓扑上的仿真结果表明,与现有的节点故障定位算法相比,探测路径选择算法具有更高的成功定位率和更低的探测成本。     

Self-organization of unattended wireless acoustic sensor networks for ground target tracking

A distributed, self-organization algorithm for ground target tracking using unattended acoustic sensor network is developed. Instead of using microphone arrays, each sensor node in the sensor network uses only a single microphone as its sensing device. This design can greatly reduce the size and cost of each sensor node and allow more flexible deployment of the sensor network. The self-organization algorithm presented in this paper can dynamically select proper sensor nodes to form the localization sensor groups that can work as a virtual microphone array to perform energy efficient target localization and tracking. To achieve this, we use a time-delay based bearing estimation plus triangulation for source localization in the sensor network. Major error sources of the localization method like time delay estimation, bearing calculation and triangulation are analyzed and sensor selection criteria are developed. Based on these criteria and neighborhood information of each sensor node, a distributed self-organization algorithm is developed. Simulation results show the effectiveness of the proposed algorithm.     

基于Amorphous的无线传感器网络定位算法研究

无线传感器网络广泛应用于各个领域,节点位置信息起着至关重要的作用。在所有的经典定位算法中,Amorphous定位算法属于非测距算法,通过获得未知节点与信标节点之间的跳数,估算节点间距离,进而计算节点坐标。分析Amorphous定位算法的缺点并提出了对节点间跳数的修正。引用质心算法加权,提出改进的算法模型,经仿真验证:该算法可获得较为精确的定位结果。     

A cellular learning automata-based deployment strategy for mobile wireless sensor networks

One important problem which may arise in designing a deployment strategy for a wireless sensor network is how to deploy a specific number of sensor nodes throughout an unknown network area so that the covered section of the area is maximized. In a mobile sensor network, this problem can be addressed by first deploying sensor nodes randomly in some initial positions within the area of the network, and then letting sensor nodes to move around and find their best positions according to the positions of their neighboring nodes. The problem becomes more complicated if sensor nodes have no information about their positions or even their relative distances to each other. In this paper, we propose a cellular learning automata-based deployment strategy which guides the movements of sensor nodes within the area of the network without any sensor to know its position or its relative distance to other sensors. In the proposed algorithm, the learning automaton in each node in cooperation with the learning automata in the neighboring nodes controls the movements of the node in order to attain high coverage. Experimental results have shown that in noise-free environments, the proposed algorithm can compete with the existing algorithms such as PF, DSSA, IDCA, and VEC in terms of network coverage. It has also been shown that in noisy environments, where utilized location estimation techniques such as GPS-based devices and localization algorithms experience inaccuracies in their measurements, or the movements of sensor nodes are not perfect and follow a probabilistic motion model, the proposed algorithm outperforms the existing algorithms in terms of network coverage.