【作者】 魏叶华；

【导师】 李仁发；

【作者基本信息】 湖南大学 ， 计算机应用技术， 2009， 博士

【摘要】 作为一种新兴的无线网络技术,无线传感器网络在工业、农业、环境监控、军事和抢险救灾等领域有着广泛的应用前景。在许多应用中,节点位置至关重要,离开位置信息,监测事件或者感知数据也失去了实际应用价值。而每个传感器节点均配置GPS收发器,成本和能耗较高,不符合无线传感器网络各方面的约束,必须研究适合无线传感器特点的自定位算法。本文围绕无线传感器网络中的定位问题,针对现有研究的不足,结合无线传感器网络的特点,分别对静止网络、信标节点移动网络和移动网络下的定位相关问题进行了相应研究。本文首先对静态网络定位进行了研究。在增量或多跳测距定位中定位误差或测距误差容易造成累积,对后继节点的定位精度影响较大。现有一些非测距集中式算法仅使用网络连通信息,也能够获取较高的定位精度,并无需考虑测距误差问题。然而通常需收集网络全局信息,通信开销较大。针对以上缺点,本文提出了一种基于支持向量回归的半集中式定位算法。首先收集各信标节点间的连通信息到中心节点作为训练样本,然后使用支持向量回归技术得到连通信息到节点位置之间的回归函数,分发此函数到网内各节点,普通节点即可使用此函数完成自身位置估计。并且为了增加训练样本,对邻居信标节点大于等于三个的,使用基于RSSI测距的最小二乘法进行定位,升级为新的信标节点。实际上是一个测距和非测距的混合算法,但避免了全局网络信息的收集,缓解了测距误差的累积。集中式定位通信开销大、扩展性差,对于资源受限的、自组织无线传感器网络来说,具有一定的局限性。通过把定位问题转化为无约束优化问题,本文提出了一种基于混合禁忌搜索的分布式定位算法。为减轻测距误差的影响和获取较好的邻域解生成区间,设计了一个选择算子,选择合适的信标节点参与定位。接着,使用信标节点信息获取初始解。最后,使用禁忌搜索和模拟退火相结合的混合策略进行位置优化,进一步提高了定位精度,本质上也是一种二阶段求精定位算法。仿真表明本文算法在不同噪音因子和信标节点下能够获取较高定位精度。与大多数静态网络定位算法中假定部署一定比例的信标节点不同,在移动信标辅助定位中,使用一个或几个移动信标节点在部署区域内移动来协助普通节点进行位置估计,有效节约了网络成本。而信标节点的移动路径对定位性能具有很大的影响,但目前关注比较少,提出了几种基于某种曲线的静态路径规划方法,未考虑定位过程中的实时信息,对不规则网络拓扑不太适用。本文针对静态路径规划方法的不足,提出了一个更具灵活性的动态启发式路径规划方法。首次提出了使用定向天线技术来解决路径规划问题,通过配置了定向天线阵列的移动信标与邻居节点的通信,可收集邻近普通节点的分布和信标信息接收情况,以此在线决策信标节点的移动。为减少信息收集带来的通信开销,提出了一次决策两次移动的信标移动方法。仿真表明本文的动态方法能够有效避免非节点部署区域的遍历,避免了不必要的信息发送,减少了移动距离,并保持了较高的定位覆盖率。在移动无线传感器网络中,普通节点和信标节点均可按某种方式移动,导致网络拓扑和节点间的连通性不断发生变化,给定位带来了一定的难度和新的要求。为提高定位算法的收敛速度,增强定位结果的时效性和精度,本文提出了一种基于动态网格划分的蒙特卡罗定位算法。首先提出了最远距离选择模型,在保证一定定位精度的情况下减少参与的信标节点数,节约能耗。接着根据信标节点构建采样区域,限定采样范围,并引入了概率方法来计算最大采样次数。最后,进行采样、过滤和位置估计,并且改变了常用蒙特卡罗的过滤方法,使用误差补偿的运动模型进行样本过滤,避免了过滤阶段大量的循环计算开销。仿真表明本文算法在保证一定定位精度的情况下,节约了采样次数和能耗,减少了处理时间。最后,为了更好的研究无线传感器网络的各方面特性,分析算法在实际系统中的性能,设计并实现了一个无线传感器网络原型系统。系统使用自己设计的硬件节点,运行ZigBee通信协议,开发了终端软件来管理和监控节点信息。并且,使用基于RSSI的测距方法,对提出的定位算法进行了验证、分析。更多还原

【Abstract】 As a new type of wireless ad hoc network, wireless sensor networks have wide applications including industry, agriculture, environmental observation, military, and collecting information in disaster prone areas. Knowledge of nodes location is an essential requirement for many applications. Without location information of sensor nodes, the sensed data or the detection of events is nonsense. However, because each sensor with a GPS device is expensive in terms of cost and energy consumption, it is infeasible due to various resource constraints such as miniature size, low-complexity, limited battery power. Therefore, self-localization for wireless sensor networks has been presented and studied. Based on the key characters of wireless sensor networks and the limitations of current research, this thesis focuses on localization issues and related problems from stationary, beacon nodes moving and mobile wireless sensor networks.This thesis firstly studies the localization problems in static wireless sensor networks. In incremental or multi-hop range-based localization algorithms, the ranging error or localization error can be easily accumulated, and this will affect the localization accuracy of successor nodes. Some range-free centralized localization algorithms can obtain high localization accuracy only using network connectivity information and do not need to consider the ranging error. However, centralized localization needs to collect the information of the entire network to base station, thus the communication cost is high and it consumes too much energy. Aiming at these drawbacks, we present a semi-centralized localization algorithm based on support vector regression. The base node collects all connectivity information between beacon nodes and applies these collected information as training samples to run the training procedure by using support vector regression method. As a result, a regression function can be derived and be distributed to all sensors in the network. Then, normal nodes can perform the estimation of locations using the function based on the connectivity to all beacon nodes. In order to increase the number of training samples, the normal nodes having minimum three anchor nodes as neighbors are upgraded to anchor nodes. Least-square method with RSSI-based ditance measurements are applied to those normal nodes so that they can locate their positions. Our algorithm is composed of range-based method and range-free method. But it can avoid collecting global network information and so reduce the accumulation of the ranging errors.For resource-limited and self-organized wireless sensor networks, centralized localization methods are impractical because of the high communication overhead and bad scalability. We turn the localization problem into an unconstrained optimization problem and propose a distributed localization algorithm based on hybrid taboo search. In order to alleviate the effect of ranging error and get a good interval to generate neighboring solutions, a selection operator is presented to select several suitable anchor nodes to take part in the localization procedure. Subsequently, information of anchor nodes is used to obtain initial estimate of location of nodes. Finally, an optimization procedure is performed by using a hybrid method composed of taboo search and simulated annealing. This improves the accuracy of the estimation of the initial location. The simulation shows that the proposed algorithm has a good accuracy on localization when noise factors and the number of anchor nodes are different. Instead of having some anchor nodes in the most of existing current localization methods, mobile anchor node-assisted localization algorithm only needs one or several anchor nodes which traverse the deployment area to help normal nodes locate. Such architecture significantly reduces the cost of networks. However, the path of mobile anchor node has a direct impact on the performance of these approaches. And not too much research work has been done on this. Several static path planning methods for mobile anchor node have been presented based on a certain curve. Such static methods cannot make use of the real-time information in localization process, and are unsuitable for irregular network topology. To improve the static methods, we propose a novel heuristic dynamic path planning method with a better flexibility. It is the first time that directional antenna technology is used to solve the path planning problem. By communicating with neighborhood normal nodes, mobile anchor node configured with directional antenna array can detect the number of distributed normal nodes and the number of beacon which each normal node has received from it. Based on the knowledge, the mobile anchor node can make on-line decision for its moving. In order to reduce the communication overhead, the mobile anchor node make one decision and move twice. The simulation results show that our dynamic planning method can effectively avoid covering the areas where no sensor nodes are deployed. This reduces the distance of the moving path and the amount of messages transmitted by mobile anchor. The simulations also indicate that our method provides good localization coverage.In mobile wireless sensor networks, the network topology and the connectivity between all the nodes continually change because of the mobility of normal nodes and anchor nodes. Therefore, this brings more complicated and difficult problems in localization. In order to enhance the convergence speed of localization algorithm and improve the localization accuracy and timeliness, we present a Monte-Carlo localization algorithm based on dynamic grid division. Firstly, we construct a farthest distance selection model. The model can save the system energy by reducing reduce the number of anchors taking part in localization, and keep a good localization accuracy. Then, these selected anchor nodes are used to create the region to draw samples from. In addition, a probabilistic approach is introduced to calculate the maximum sampling number. Finally, sampling, filtering and location estimation are executed. Unlike the existing Monte-Carlo algorithms, a mobility model with error compensation is applied to filter the samples. This model can reduce the computing overhead for a large number of loop computing. The simulation demonstrates that our algorithm reduces the sampling numbers, energy consumption and the processing time and still has a good localization accuracy.Finally, for better research the characters of wirelss sensor networks and analysis the performance of the proposed algorithms in real system, we implemented a prototype system for wireless sensor networks. The nodes of the system are designed by ourselves with ZigBee protocal to communicate among the nodes. In our system, we write a program to manage and supervise the information from nodes. Furthermore, one proposed localization algorithm is evaluated on the prototype system based on RSSI ranging technology.更多还原