微信服务号

微信订阅号

2025年4月3日 16:03 星期四
首页 > 过刊浏览>2010年第21卷第zk期 >318-329
PDF HTML阅读 XML下载 导出引用 引用提醒
三维AD-HOC 网络地理信息路由算法
作者:
基金项目:

Supported by the National Natural Science Foundation of China under Grant No.60973122 (国家自然科学基金); the Aeronautics Foundation of China under Grant No.20091969022 (航空基金)


A Geographic Surface Routing Algorithm in 3D Ad Hoc Networks
Author:
  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [16]
    • |
  • 相似文献 [20]
    • | | |
  • 文章评论
    摘要:

    在二维AD-HOC 网络中,可以充分利用节点的地理信息进行路由,即AD-HOC 中节点根据邻居节点的距离目标节点的距离,选择下一跳节点进行路由转发.由于AD-HOC 中节点部署通常不满足均匀分布,造成网络中出现路由空洞,贪婪转发算法在遭遇空洞的情况下将无法正确执行.在二维AD-HOC 网络环境中,往往采用贪婪(Greedy)算法结合表面路由(Face Routing)的方法跳出路由空洞.但是在三维条件下,目前没有很好跳出路由空洞的算法能够实现有效的路由.提出了一种在三维AD-HOC 网络中的地理信息路由算法GSG,该算法使用3D RDT 图和3D RRNG 图的方法实现三维网络空间的划分.采用3D 表面路由的方法进行信息传递,在遭遇局部最小点时,可有效跳出路由空洞.仿真实验结果表明,GSG 算法可提升三维AD-HOC 网络条件下地理信息路由的效率,具有良好的可扩展性.

    Abstract:

    For geographic routing in 2D ad hoc networks, greedy algorithm is efficient. The next hop node is selected according to the distance to the destination. However, greedy forwarding fails when a message reaches a local-minimum. Face routing is used to solve these problems. Unfortunately, these results cannot be applied to 3D networks directly. We propose an algorithm GSG (Greedy Surface routing Greedy) for geographic routing in 3D environments. We partition whole network with 3D Restricted Delaunay Triangulation. Triangles and isolated edges are defined as 3D components on Surface. By means of identifying intersecting triangles and edges, efficient routes are constructed on surfaces by bypassing local-minimums. Simulation results show that GSG achieves good routing performance and scalability.

    参考文献
    [1] Bruck J,Gao J, Jiang AA. Localization and routing in sensor networks by local angle information. ACM MobiHoc, 2005. 181-192.
    [2] He T, Huang C, Blum BM et al. Range-Free localization schemes for large scale sensor networks. ACM MobiCom, 2003. 81-95.
    [3] Bose P, Morin P, Stojmenovic I, et al. Routing with guaranteed delivery in Ad Hoc wireless networks. Wireless Netoworks, 2001, 7(6):609-616.
    [4] Karpand B, Kung HT. GPSR: Greedy perimeter stateless routing for wireless networks. ACM MobiCom, 2000. 243-254.
    [5] Frey H, Stojmenovic I. On delivery guarantees of face and combined greedy-face routing in Ad Hoc and sensor networks. ACM MobiCom, 2006. 390-401.
    [6] Kuhn F, Wattenhofer R, Zhang Y, et al. Geometric Ad-Hoc routing of theory and practice. ACM PODC, 2003. 63-72.
    [7] Roland F, Roger W. Randomized 3D geographic routing. IEEE Infocom, 2008. 834-842.
    [8] Liu C, Wu J. Efficient geometric routing in three dimensional AD hoc networks. IEEE Infocom, 2009. 2751-2755.
    [9] Joe B. Construction of three dimensional delaunay triangulation using local transformations. Computer aided Geometric Design, 1991,8(2):129-142.
    [10] Stephane D, David K, Lata N. On routing with guaranteed delivery in three-dimensional ad hoc wireless networks. In: ICDCN. 2008. 546-557.
    [11] Godfried T. The relative neighbourhood graph of a finite planar set pattern recognition, 1980,12:261-268.
    [12] Kranakis E, Singh H, Urrutia J. Compass routing on geometric networks. In: Proc. of the 11th Canadian Conf. on Computational Geometry (CCCG 1999). 1999. 51-54.
    [13] Fang Q, Gao J, Guibas L. Locating and bypassing routing holes in sensor networks. IEEE Infocom, 2004. 2458-2468.
    [14] Liu S, Fevens T, Abdallah A. Hybrid position based routing algorithm for 3D mobile ad hoc networks. In: Proc. of the 4th Int’l Conf. on Mobile Adhoc and Sensor Networks. 2008. 177-186.
    [15] Tao S, Ananda A, Chan M. Spherical coordinate routing for 3D wireless ad-hoc and sensor network. In: IEEE Conf. on Local Computer Networks. 2008. 144-151.
    [16] Frey H, Stojmenovic I. On delivery guarantees of face and combined greedy-face routing in ad hoc and sensor networks. ACM Mobicom. 2006. 390-401.
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

汪芸,苏瀚,房鼎益.三维AD-HOC 网络地理信息路由算法.软件学报,2010,21(zk):318-329

复制
分享
文章指标
  • 点击次数:4681
  • 下载次数: 6004
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 收稿日期:2010-07-01
  • 最后修改日期:2010-12-10
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第19781420位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号