基于图刚性的无线传感器网络定位新算法

New node localization algorithm for wireless sensor networks based on graph rigidity

针对分布式MDS-MAP算法的不足,提出了一种基于图刚性理论的无线传感器定位新算法MDS-MAP（GR）。算法利用图的刚性理论,确定网络中的所有刚性子区域,然后利用合并定理将刚性子区域进行扩展,最后对合并得到的刚性区域利用MDS-MAP算法和锚节点实现网络中节点的大规模定位。算法尽可能对刚性区域进行合并,节省了执行MDS-MAP算法的次数,提高了执行效率。通过在不同拓扑结构的无线传感器网络中进行了仿真实验,说明了提出的算法能有效定位不同半径下网络中90%以上的节点,另外,新方法比现有方法在定位成功率上提高了4%~5%,并且定位精度提高了2%~3.5%左右。算法适用于大规模无线传感器网络中的快速定位。

In order to solve the shortage of distributed MDS-MAP localization algorithm,this paper presented a new localization algorithm for wireless sensor network based on graph rigidity. Firstly,the presented algorithm utilized graph rigidity theory to determine all rigid sub-regions in network. Secondly,it used a merging theory to merge these rigid sub-regions. Finally,it used the MDS-MAP algorithm and anchor node to localize network nodes during these merged regions with a large scale. Because the proposed algorithm merged all rigid sub-regions as soon as possible before running the MDS-MAP algorithm,it reduced the run times of MDS-MAP efficiently and enhanced the proposed algorithm＇s performance. Through the simulation experiments in wireless sensor network with different topology structure,the results show that the proposed algorithm can efficiently localize more than ninety percent nodes with different communication radius. In addition,compare with previous method,the success rate of localization presented algorithm is improved 4% ~ 5% and the accuracy is improved 2% ~ 3. 5%. The presented algorithm is compatible to localize nodes in large scale wireless sensor networks.