计算机应用 ›› 2010, Vol. 30 ›› Issue (06): 1439-1442.

• 网络与通信 • 上一篇    下一篇

基于虚拟坐标系统的无线网络地理路由算法

李玉军1,卢显良2,蒋海林3,李梁2,徐海湄4   

  1. 1. 电子科技大学
    2. 电子科技大学计算机学院
    3. 中科院成都信息技术有限公司
    4.
  • 收稿日期:2010-01-06 修回日期:2010-01-26 发布日期:2010-06-01 出版日期:2010-06-01
  • 通讯作者: 李玉军
  • 基金资助:
    电子科技大学青年基金资助项目

Geographic routing algorithm based on virtual coordinate system

  • Received:2010-01-06 Revised:2010-01-26 Online:2010-06-01 Published:2010-06-01

摘要: 针对地理路由算法中的路由空洞问题,通过引入虚拟坐标的方式,提出了一种新颖的无线网络地理路由算法——双重贪婪算法(DGA)。根据网络的拓扑结构信息,DGA为每个节点分配虚拟坐标,在基于真实地理位置的贪婪算法遇到路由空洞时,以基于虚拟坐标系统的贪婪算法作为恢复机制,从而保证路由算法的收敛性。DGA克服了GPSR等传统地理路由算法只能适用于理想的单位圆图(UDG)的缺点,能够适用于更加真实的无线网络模型。仿真实验验证了DGA高效的路由性能及良好的扩展性。

关键词: 无线网络, 路由算法, 地理路由, 贪婪算法, 虚拟坐标

Abstract: To address the holes problem in wireless sensor networks, a novel geographic routing algorithm, named Double Greedy Algorithm (DGA), was proposed based on virtual coordinate system. First, each node in the wireless network was allocated a set of virtual coordinates according to the topology of wireless network. Then, when the greedy algorithm based on the real geographic positions failed, the greedy algorithm based on the virtual coordinates helped it to recover from the dead end situation. Hence, the convergence of DGA was guaranteed. DGA was applicable for more accurate network models, such as the network model based on the log-normal shadowing model, which is substantially different to the GPSR algorithm. At last, the performance and scalability of DGA were verified by simulations.

Key words: wireless network, routing algorithm, geographic routing, greedy algorithm, virtual coordinate