ISSN 1000-1239 CN 11-1777/TP

• 论文 • 上一篇    下一篇

Ad Hoc网络中基于骨干网的相对定位算法研究

田明军 赵 丹 王靖轩 严 伟   

  1. (北京大学计算机科学与技术系 北京 100871) (
  • 出版日期: 2008-05-15

BackboneBased Relative Positioning in Ad Hoc Networks

Tian Mingjun, Zhao Dan, Wang Jingxuan, and Yan Wei   

  1. (Department of Computer Science and Technology, Peking University, Beijing 100871)
  • Online: 2008-05-15

摘要: 在无线自组网中,相对定位是一个相当重要的研究课题.SPA相对定位算法提出之后,人们针对SPA算法提出了一系列改进的方法.其中一种基于群的相对定位算法成功减少了SPA算法的通信开销,但因其坐标系合并结果存在二义性,往往造成很大的误差.因此提出了一个确定Ad Hoc网络中节点相对位置的新算法——BBA.该算法采用基于骨干网络的思想,由网络中少部分节点先组成骨干网络,然后在骨干网络上的节点建立局部坐标系,最终合成整个网络的相对坐标系.模拟实验的结果表明,与基于群的算法相比,该算法在减小通信开销的同时保证了算法的正确性,并且减少了参与定位运算的节点比例.

关键词: 无线自组网, 相对定位, 骨干网, 通信开销, 局部坐标系

Abstract: Relative positioning is a hot topic in ad hoc network. And self positioning algorithm is an essential work in this field. After SPA was proposed, people have done a lot of works in order to get better accuracy while reducing the communication cost. Most of these works retain the main architecture of SPA. One of them named cluster based approach decreases the communication cost of SPA successfully. But it has big problems in terms of accuracy. When merging two neighboring local coordinate systems, the results are ambitious. And it thus causes low accuracy in positioning especially when there is a large node number. Proposed in paper is a new relative positioning algorithm, BBA, which is backbonebased. The backbonebased algorithm contains mainly three steps: firstly, a part of nodes is selected to establish a backbone network, then every node on the backbone builds a local coordinate system, finally, all the local coordinate systems are merged to a global one. Simulation results show that compared with cluster based approach, the BBA algorithm not only decreases the communication cost but also is highly accurate. Additionally, the BBA algorithm reduces the ratio of the nodes that involve computing positions, which is also considered an important improvement.

Key words: ad hoc network, relative positioning, backbone network, communication cost, local coordinate system