基于骨架提取的水下传感器网络刚性定位判别研究  

Study on Localizability Judgment in Underwater Sensor Networks Based on Skeleton Extraction and Rigidity Theory

作　　者：夏娜[1] 王诗良[1] 郑榕[2] 杜华争[1] 徐朝农[3] 

机构地区：[1]合肥工业大学计算机与信息学院,合肥230009 [2]麦克马斯特大学计算与软件学院 [3]中国石油大学计算机科学与技术系,北京102249

出　　处：《计算机学报》2015年第3期589-601,共13页Chinese Journal of Computers

基　　金：国家自然科学基金(61100211;61003307);教育部新世纪优秀人才支持计划(NCET-13-0768);安徽省杰出青年科学基金(1408085J05)资助~~

摘　　要：水下传感器网络可用于海洋资源勘测、污染监测和战术监视等领域,已成为无线传感器网络方向的研究热点.在水下三维空间中如何对位置未知的节点进行可定位性判别,并实施有效定位,从而为水下监测应用提供位置信息是一个基础的关键问题.该文引入刚性图理论,提出了一种基于骨架提取的水下传感器网络刚性定位判别方法.该方法首先将水下传感器网络构建为无向图,然后通过"伪节点剔除"和"割边剔除"等策略提取具有全局刚性的子图,即网络的骨架,从而完成网络及节点可定位性的判别,最后利用层次分析法对可定位节点进行"定位可信度"综合排序,为定位计算提供指导和依据.大量仿真实验结果表明该方法在不同网络规模、节点密度和网络连通性情况下均具有较高的判别成功率和有效性.Underwater sensor networks（UWSNs）can be applied in sea resources reconnaissance,pollution monitoring and tactical monitoring etc.,and it has become a hot field in wireless sensor networks.In the three dimensional underwater space,it is a key topic to judge the localizability of the unknown sensor node in all kinds of applications.In this paper,a localizability judgment method for UWSNs is proposed based on skeleton extraction and Rigidity Theory.Firstly,UWSNs is converted to an undirected graph.Secondly,by eliminating its pseudo node and cutting edge,the graph will shrink to the sub-graph with global rigidity,which is named ＂network skeleton＂,and then the localizable nodes are figured out.Lastly,Analytic Hierarchy Process is used to evaluate the localization credibility of the localizable nodes.The extensive simulations demonstrate that the proposed localizability judgment method can achieve excellent success ratio and efficiency in the networks with different sensor numbers,sensor density and connectivity.

关 键 词：水下传感器网络 可定位性 骨架提取 刚性图理论 层次分析法 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] TP393[自动化与计算机技术—控制科学与工程]