论文研究-Ad hoc网络中一种带预测的路由算法.pdf

所需积分/C币:11 2019-09-12 00:33:38 564KB .PDF

在自组网中,由于网络节点的移动性及拓扑结构的易变性,设计稳定的路由成为最受关注的问题。根据可靠性为多路径路由选择更多的可靠路径,以满足自组网中多路径传输在路径的数量和质量方面的需求,是多路径路由技术中的一个重要研究课题。为此,基于GRID模型和预测模型提出了一种带预测的稳定不相交备用路由算法,其利用有效限制路由查询包的泛洪区域,并结合预测策略和节点不相交路径算法来选择一条最稳定的不相交备用路由,从而进一步提高该路由算法的性能。模拟结果显示,与其他3个多路径路由相比较,该算法是一个有效的自组网路由算法。
92 2010,46(21) Computer Engineering and Applications计算机工程与应用 路由断开时,备用路由才被使用。详细算法如下所示。 if first RREQ from the received by the destination ↑2 lifetime=lifetime time consumed; // ,,4 if(lifer (a)RREQ的传输 store the path in the Route cache table at dest (b)形成的多路径 图2覆盖多路径 When wait timer expires 通过 host-by-host方式。因此,每个网格中只有恻格头需要维 path=Path Select(); i/selects disjoint backup paths 护路由表和负责网格中的路由发现过程。在路由发现阶段, backup path=max(RET) //selects the most stable route 该算法的主要目的是寻找尽可能多的且满足条件的稳定路 send rrep back to the source grid head; /send back Route 由。在此泛洪中,中间网格头并不随意丢掉RREQ包的副本 Reply msg along the path last node (如果像AODⅤ或DSR那样转发RREQ,那么将没有足够的 RREQ包到达目的节点,所以很难形成多条不相交路由),并5性能评价 且只有满足以下两个条件(C1和C2)时,中间网格头才将RREQ5.1模拟环境 包转发到与其相邻的网格中,同时将其H已的地址附加到 ns-2是一种支持多种有线和无线通信树(包括 Ad hoc RREQ包上 网络)的模拟软件,能够对不同网络层次、不同网络结构进 C1:节点不是RREQ包要到达的目的节点 行模拟。采用ns-2对该算法进行模拟,并与AODV-BR,SMR C2:ltl的值大于零。 和 Cluster-Multipath进行对比。模拟环境设置:50个节点在 基丁文献『3]策略设计了一种新的多路径转发策略,用以1000m×1000m区域。节点的传输距离为200m。数据包 搜寻多条满足条件的稳定备用路由,如图3所示。当网格头发送率为10pkt,数据包大小为512Bye。MAC层协议为 接收到一个RREQ包时,首先判断其 GridID是否在 Searched-E802.1DCF。无线信道带宽为2Mbs。整个实验模拟时 Area内,如果不在,则丢掉该RREQ包。否则,LET项和RET间为300s。采用传统的 Random Waypoint Model"作为节点 项将祓写入RREQ包中的相应域中,并更新该网格头的路由的移动模型。在移动特性的描述方面.采用了传统的停顿时 中表。然后检查m的值是否等于0,如果是,则丢掉该RBQ包间来定义模型的移动持性。节点到达指定位置后停滞时间4 并且终止该算法。如果不是并且接收该RREQ包的恻格头不越长,表示该情况下节点的移动特性越不明显。以此来观察 是目的节点,则继续广播RREQ包。最后,当目的网格节点接在各种移动情况下,各个协议的性能特点,并根据相关文献 收到RREQ包时,其判断目的节点是否为该网格头,如果目的[20所提出的几种不同的性能评价标准来进行评价。 节点不是该网格头,则负责唤醒日的节点并把缓存中的数据5.2模拟结果及分析 包发给目的节点。该策略可以有效地限制到达目的节点的备 图4显示了每个算法在不同移动性的情况下数据包的投 用路由的数量,并且降低备用路由的选择代价。 递率,本文提出算法的数据包投递率要高于其他3个路由算 法。原因是其恨据新的转发策略建立了稳定的不相交备用路 由集。路由根据网格头进行,且网格头是该GRID区域内稳定 性高的节点,即保证了路由的稳定性。另外稳定的备用路由 叮以及时继续保持通信的畅通,减少了丢包的叮能,并且高质 3 量的路由也保证了数据包的高投递率。 2}■氵·;·:·氵■氵■ 图5反映了端到端延时的情况,提出的算法使用新的转 1■:■;■;; 发策略建立了稳定的不相交备用路由集,而其余多路径路由 算法没有考虑稳定性。所以当路径岀错时,其余路由算法的 ( aired的传输 (b)形成的多路径 重新寻路会使得缓冲数据包等待时间加大,从而导致延时的 图3多路径新策路 提高。 4、3稳定不相交备用路由选择 从图6可以看出本文提出的算法的路由负载好于其余3 当目的网格头节点接收到第一个RREQ包时,它将等待个路由。原因是在一次的路由发现过程中,其可以找到稳定 段时间以接收更多的REQ包的副本,这样就可以建造的不相交备用路由集,这样可以减少由于路由失败而频繁进 备用路由集。为了使路由有更大的容错性,选择与主路由不行的路由发现过程。且提出的算法使用GRID结构和设计了 相交的最稳定路由作为胬用路由,这样,即使主路由断开,也 种新的转发策略,其都可有效地限制控制包的泛洪区域,所 不会影响备用路由。用类似于文献[门]的不相交路径选择算以也减少了路由鱼载 法,目的网格头节点会在备用路由集中选择RET最大的路由, 即最稳定的不相交路由作为备用路由。目的网格头节点根据6结论 最小延迟建立主路由。最后,通过结合使用主路由和备用路 自组网的路由算法往往采用传统的单路径路由方式,每 由米进行数据包的投递。主路由通常是第一选择,只有当主次路由发现泛洪都会伴有大量路由包的丢弃以及路由负载和 吴正字; ad hoc网络中一种带预测的路由算法 2010,46(21) 0.99 后0. 180 ≥0.95 2 6 6150 ≥0.93 0.91 A This paper s algorithm i- 8- This paper's algorithm 0.89E2 米 AODV-BR 米一 AODV-BR 90+SMR c2米 AODV-BR SMR e-Cluster- Multipath Cluster-Multipath 050100150200250300 050100150200250300 50100150200250300 Pause time/s Pause time/s Pause timeis 图4数据包投递率 图5端到端延迟 图6路山负载 路由延迟的増加,大大降低路由算法的性能。为解决这些问 2006), Patras, Greece,2006:106-110 题,提出了一种带预测的稳定不相交备用路由算法,其利用有10 Zhang Jie, Jeong C K. Lee g y,eta. Cluster-based multi-path 效限制路由查询包的泛洪区域,并结合预测策略和节点不相 routing algorithm for multi-hop wireless network [J]. Internation 交路径算法来选择一条最稳定的不相交备用路由,从而进 al Journal of Future Generation Communication and Network 步提高该路由算法的性能。模拟结果显示,与其他3个路由 ng,2008,1(1):67-74 相比较,该算法是一个有效的自组网路由算法。 [111 Wang Yong-wei, Giruka V C, Singhal M. Truthful multipath rout- ing for ad hoc networks with selfish nodes[]journal of paral lel and Distributed Computing, 2008, 68(6): 778-789 参考文献: [12] Rosenthal A Computing the reliability of complcx nctworks[JI [1] Lee s J, Gerla MAODV-BR: Backup routing in ad hoc net SIAM Journal of Applied Mathematics, 1977, 32: 384-393 works[C]/Proc of the IEEE WCNC 2000, Chicago, 2000: 1311-1316 [13 Provan J SThe complexity of reliability computations in pla [2] Marina M K, Das s R On-demand multipath distance vector ar and acyclic graphs[J]. sIAM Journal on Computing, 1986 routing for ad hoc networks[C]/Proc of the Int'l Conf for Net 15:694-702 work Procotols(ICNP), Riverside, 2001: 14-23 [14] Yao Zhong-bang, Cao Zhi-gang, Fan Ping-yi Hybrid multipath [3] Lcc S J, Gcrla M. Split multipath routing with maximally dis routing in mobile Ad hoc networks[J]Journal of Tsinghua Uni- joint paths in ad hoc networks[C]/Proc of the IEEE ICC 2001 versity( Sci Tech), 2004(7) Helsinki,2001:3201-3205 [15 Chao Chih-Min, Sheu Jang-Ping, Hu Cheng-Ta. Energy-conserv- [4] Guo Xiao-feng, Chen Yue-quan, Chen Gui-hai. An aggregated mul ing grid routing protocol in mobilc Ad hoc nctworks[C]//Inter- tipath routing scheme for Ad hoc networks[ J]Journal of Soft national Conference on Parallel Processing( ICPP'03), Taiwan. ware,2004,15(4) 2003:265-272 15] Pearlman M R. Haas Z J. Sholander P, et al. Alternate path rout- [16] Su W, Lee Sung-Ju, Gerla M Mobility prediction and routing ing in mobile Ad hoc networks[C]//Proceedings of IEEE MI in Ad hoc wireless networks[J]. International Journal of Net COM 2000, Los Angeles, CA, 2000, 1: 501-506 work Management, 2001,11(1): 3-30 [6] Wang L Multipath source routing in wireless Ad hoc networks[C]/ [17] Perkins C E, Royer E MAd hoc on-demand distance vector Canadian Conference on Electrical and Computer Engineering routing[C]pRoceedings of the 2nd IEee Workshop on Mo 2000,1:479-483 bile Computing Systems and Applications, New Orleans, LA [7 Leung R, Liu Ji-lei, Poon E, et al.MP-DSR: A Qos-aware multi 1999:90-100 pathdynamicsourceroutingprotocolforwirelessAd-hocnet-[18]ns-2manual[eb/ol].http://www.isi.edu/nsnam/ns/doc/index.html works[C]//Proceedings of LCN, USA, 2001 [19 Broch J, Maltz D A, Johnson D B, et al. a performance com [8] Kim S, Noh W, An S Multi-path Ad hoc routing considering re- parison of multi-hop wireless Ad hoc network routing proto dundancy [C]IEEE ISCC, Turkey, 2003: 45-50 cols[C]iProc of the 4th Annual ACM/IEEE International Con [9] Esmaeili E, Akhlaghi P, Dehghan M, et al. A new multi-path ference on Mobile Computing and Networking, Dallas, TX, 1998 routing algorithm with local recovery capability in mobile Ad 85-97. hoc networks[C]//5th International Symposium on Communic [20 Corson S, Macker J Mobile Ad hoc networking: Routing proto- tion Systems, Networks and Digital Signal Processing( CSNDSP col performance issues and evaluation considerations[S]. 1999 (上接50页 22(7) 的E/指标进行了优化。同时并将SA算法引入到DE调度算3] Trietsch D. Baker K r. Basic techniques for lot streaming[J].Op 法中来改进DE调度算法的性能。仿真试验表明了所得算法 erations Research, 1993. 41: 1065-1947 的可行性和有效性。 [4 Pan Q K, Tasgetiren M F, Liang Y CA discrete differential evo lution algorithm for the permutation flowshop scheduling prob 参考文献 lcm[]. Computers Industrial Enginccring, Doi: 10.1016 j. cic. 2008 [1] Storm R, Price K Diffcrcntial cvolution-A simple and cfficicn 03.003 adaptive scheme for global optimization over continuous spac [5] Tseng Chao-Tang, Liao Ching-Jong a discrete particle swarm op- es[r. Berkeley: University of California, 2006 timization for lot-streaming flowshop scheduling problem[J]. Eu [2]刘波,王凌,金以慧差分进化算法研究进展[J控制与决策,2007, ropean Journal of Operational Research, 2008. 191(2)

...展开详情
img
  • 至尊王者

    成功上传501个资源即可获取

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐