ISSN 1000-1239 CN 11-1777/TP

• 论文 •

1. (北京大学计算机科学与技术系 北京 100871) (tmj@net.pku.edu.cn)
• 出版日期: 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

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.