基于骨架提取的水下传感器网络刚性定位判别研究-计算机学报.DOCVIP

PAGE 14 计 算 机 学 报 2014年 论文在线出版号No.26 夏娜等：基于骨架提取的UWSNs刚性定位判别研究 PAGE 15 第37卷 计 算 机 学 报 Vol. 372014论文在线出版号No.26 CHINESE JOURNAL OF COMPUTERS Online Publishing No.26 ——————————————— 本课题得到国家自然科学基金(No.、教育部新世纪优秀人才支持计划(No. NCET-13-0768)、安徽省杰出青年科学基金(No. 1408085J05)资助. 夏娜，男，1979年生，博士，教授，中国计算机学会(CCF)会员（E20-0008648M）, 主要研究领域为水下传感器网络、导航信息处理、计算智能与应用，E-mail: xiananawo@. 王诗良，男，1988年生，硕士研究生，主要研究领域为水下传感器网络，E-mail: wangshiliang888@. Rong Zheng，女，1975年生，博士，副教授，主要研究领域为网络监测和诊断、序列学习，E-mail: rzheng@mcmaster.ca. 杜华争，女，1986年生，博士研究生，主要研究领域为水下传感器网络、计算智能，E-mail: huazheng2616@163.com. 徐朝农，男，1977年生，博士，副教授，主要研究领域为自组织无线网络、嵌入式系统，E-mail: xu_chaonong@. 基于骨架提取的水下传感器网络刚性定位判别研究 夏娜1) 王诗良1) Rong Zheng2) 杜华争1) 徐朝农3) 1)(合肥工业大学计算机与信息学院, 合肥 中国 230009) 2) (麦克马斯特大学计算与软件学院, 汉密尔顿 加拿大 L8S4K1) 3)(中国石油大学计算机科学与技术系, 北京 中国 102249) 摘 要 水下传感器网络可用于海洋资源勘测、污染监测和战术监视等领域，已成为无线传感器网络方向的研究热点。在水下三维空间中如何对位置未知的节点进行可定位性判别，并实施有效定位，从而为水下监测应用提供位置信息是一个基础的关键问题。该文引入刚性图理论，提出了一种基于骨架提取的水下传感器网络刚性定位判别方法。该方法首先将水下传感器网络构建为无向图，然后通过“伪节点剔除”和“割边剔除”等策略提取具有全局刚性的子图，即网络的骨架，从而完成网络及节点可定位性的判别，最后利用层次分析法对可定位节点进行“定位可信度”综合排序，为定位计算提供指导和依据。大量仿真实验结果表明该方法在不同网络规模、节点密度和网络连通性情况下均具有较高的判别成功率和有效性。 关键词 水下传感器网络；可定位性；骨架提取；刚性图理论；层次分析法 中图法分类号 TP18, TP393 Study on Localizability Judgment in Underwater Sensor Networks Based on Skeleton Extraction and Rigidity Theory XIA Na1), WANG Shi-liang1), Rong Zheng2), DU Hua-zheng1), XU Chao-nong3) 1)( School of Computer and Information, Hefei University of Technology, Hefei 230009, China) 2) (Department of Computing and Software, McMaster University, Hamilton L8S4K1, Canada) 3)( \o Department of Computer Science and Technology Department of Computer Science and Technology, China University of Petroleum, Beijing 102249) Abstract 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 lo