论文研究-基于交通引力场的复杂网络路由选择方法.pdf

所需积分/C币:10 2019-07-22 20:21:28 1.99MB .PDF

为提高网络吞吐量、缓解交通拥塞程度,结合复杂网络理论和引力场理论研究了在交通引力场下的动态路由选择过程,定义了传输路径对数据包的引力计算公式。基于路径的引力,顾及数据包的传输路径长度、节点畅通度及介数对传输过程的影响,提出了一种在介数约束下的引力场路由选择策略,并引入参数μ用于调节路由过程对节点介数的控制强度。为描述数据包传输过程的有效性,引入有序参数η,利用其由自由流到拥塞态的指标流量相变值度量网络的传输能力,并对网络节点拥塞分布情况进行了统计分析。仿真结果显示,与最短路由选择算法相比,该路由策略较大地提高了网络传输能力,有效地均衡了网络交通负载,大部分节点均得到了高效利用,路由算法稳定、可
196· 计算机应用研究 第34卷 R>R时,算法不能及时有敚地缓解局部的拥塞情况,导致拥导致这些节点严重拥塞,进而较大地降低了网络的传输能力。 塞开始蔓延至整个网络,节点的引力均变得很小.算法的避让 木文路由算法在文献[18中引力场路由策略的基础上, 机制逐渐失效,数据包将逐步沿着最短路径进行传递,平均顾及节点的介数对网络拥塞的影响,对节点的引力进行约束 传输路径长度开始减小。本文路由算法能够及时地控制网络主要是进一步限尙了介数较大节点对交通流的吸引力。为此 拥塞,如果某个节点开始聚集少量数据包,算法能及时发现并这里对本文路由算法和文献18]中引力场路由算法进行对比 评佔其拥塞程度,且该节点对其他数据包的引力将减小,致使实验分析,结果如图4所示。仿真结果表明,本文算法的路由 在一定时间范围内只冇极少甚至没冇数据包发送至该节点,即性能优于文献[18]中路由策略,将网络吞吐量提高了25%,说 算法有效地控制了该节点的接收能力。而随着节点缓存数据明约束介薮较大节点的引力有助于提升网络的传输性能。在 包个数的不断减少,其对网络上其他节点中数据包的引力也逐研究过程中发现,本文路由算法对于介数分布极不均衡的无标 渐増大,节点的接收能力增强。由此可见,本文蕗由选择策略度网络的路由传递很显著,但对于规则网终、随机网络等难以 能显著地提高网络的吞吐量及控制网络交通拥塞程度。 体现其对节点引力的约束,路由性能与文献[8]相当。 10000 本文路白算法 8中路由算法 0 15 0.5 6000 0.4 03 4000 01020304050 a)与R的关系 b)〈Im)与R的关系 图3网络乔吐量与的关系图4引力场路由算法对比实验结果 30r 3结束语 000 2.0 本文结合引力场理论和复杂网络理论,进一步研究了网络 上数据包的动态传输过程。在文献[18]的基础上,针对介数 010203040506C 0020304050d较大节点在传统最短路由策略中聚集能力过大而易引发拥塞 R 的问题,提出一种在节点介数约束下的引力场动态路由选择算 ()(7.)与R关系 (《L〉与R的关系 法,分别针对算法在不同参数取值下的路由情况进行了模拟仿 图1最短路由策略实验结果 真。理沦和实验结果表明,与最短距离路由策略相比,本文路 0.8 10000 由算法较大地提高了网络的传输能力,所有节点均得到了高效 0.6 8000}a=1-3 0.5 利用,节点的介中心分布较为均匀。由于算法对介数较大节点 k0.4 的引力约束更为显著,在一定程度上限制了此类节点的接收能 0.2 2000 力,进而有效地缓解了此类节点的拥塞程度,实现了网络负载 的均衡分配。同吋,路由算法的性能不受引力场模型中可调参 102030405060 01020 R 数的影响,说明算法具有较强的稳定性和可靠性。本文硏究进 a)n与R的关系 (b)〈〉与R的关系 6C00 步深化了对网络路由引力作用机理的理解,为寻找高效的动 态路由策略提供了理论参考。 4000 5300 参考文献 [1 Watts D J, Strogatz S H. Collective dynamics of'small-worldnet- 1000 works[J]. Nature,1998,393(6684):440-442 030405060 0102030405060 [2 Barabasi A L, Albert R. Emergence of sealing in random networks R [J]. ScIence,19),286(5439):509-512 ()〈r)与R的关系 ()〈L)与R的关系 图2最短路由策略实验结果 L 3 Newman M e J. The structure and function of complex networks [J] S| AM Review,2003,45(2):167-256 此外,本文统计了不同值下网络的吞吐量情况,结果如14 Doccaletti s, Latera'y, Moreno y,etal. Complex netwon:mr 图3所示。结果表明,当R<R时,R随μ值的增大而增大并 ure and dynamics[J]. Physics Reports, 2006, 424(4-5): 175- 在μ=-1处达到最大;当R>R时,R.随μ值的增大而减小 308 且当μ>0时,R急剧下降,且随μ的持续增大,R2的减小趋势5sgsH, Exploring complex networks[J. Nature,.01,410 逐渐趋于平稳。在最短路由算法中,度较大的节点具有较强的 (6825):268-276. 聚集能力且最易引发拥塞。在本文算法中,当<0时,路由过L6MmiM. Complex syste:ewk ck thinking J. Artificial Intelli- 程削弱了度较大节点的聚集能力,在一定程度上数据包将有意 gence,2006,170(18):1194-1212 识地將开这些节点,故拥塞不易引发且网终传输能力较强;如17 Carmi s,WuZ, Lopez E,em. Transport between multiple users in complex networks[ J]. European Physical Journal B, 2007, 57 果μ太小,算法将过度约束度较大节点的连通能力,造成这些 (2):165-174. 节点可能处于空闲状态,其在网络传输中的重要性没有得到休[8]郑海青,井元伟,刘晓平一类具有多种榻合时滞的复杂动态网络 现,进而降低了网络的吞吐量;当μ>0时,路由过程等同于增 的牵制同步「J].控制与决策,2010,25(11):1719-172 强了度较大节点的聚集能力,造成大部分薮据包都汇集于此, (下转第210页) 10 计算机应用研究 第34卷 大,采取本文所述基于终端属性分组转发方式和基于历史相遇 ference on Broadband Network Multimedia Technology. 2009: 854 预测方式,网络开销没有明显差异,这是因为此时矿下矿工属 性大致相同,由活跃终端携带数据可以在较小开销情况下以铰[3] Ren Zhi,, Zhang Jian, Li Jibi,eta. An effective hybird routing algo 低时延将数据转发至AP。 rithm for opportunistic networks[C//Proc of the 2nd International Confe nd intelligent sy O12:543-547 [4 Morelli A, Stefanelli C, Tortonesi M, et al. Mobility pattern predic- 历史相遇概率 9-其于终端属性 tion to support opportunistic networking in smart cities[C]// Proc of 接10 丁历史相遇概率 International Conference on Mobile Wireless Middle Ware, Operatin 将 基丁终端属性 Systems and Applications. 2013: 166-175 s3。6。 [5刘期烈,许猛,李云,等.基于历史效刑的机会网络路由算法 [J].计算机应用,2013,33(2):361-364 0246810121416I820 02468101214161820 终端个数 终端个数 [6 Karamshuk D, Boldrini C, Conti M, et al. Human mobility models 图8活跃终端个数 图9活跃终端个数增加时 for opportunist orks[J]. IEEE Communications Magazine 增加吋网络吋延 携带数据终个数 2011,49(12):l57-165 活跃终端个数较少时,本文提出的机会网络分组转发协议[7] Cheng Gang, Song Mei, Zhang Yong,enal. Routing protocol based 在时延和开销上均优于基于历史相遇概率的转发协议,且在开 on social characteristics for opportunistic networks[ J]. Journal of 销有明显优势的情况下获取与洪泛方式相差不大的时延。基 China universities of posts and telecommunications 2014 2 于终端属性的机会网络分组转发协议更适用于终端活动范围 (1):67-7 受限、终端活跃度差异较大的场景。 [8 Nin Jianwei, T iu MingZhu, Shu Lei, et al. Copy limited flooding over ortunistic networks[C//Proc of Wireless Communications and 4结束语 working Conference. 2013: 1785-1790 [9] Deng Yubo, Liu Wei, Zhang Lei, et al. Path prediction based on 本文针对井下信道环境复杂,无线网络连通性差的问题 second-order Markov chain for the opportunistic networks [C]/Proe 提出了一种基于矿下工种终端移动马尔可大模型的机会网络 ofl上 E computing mmunications and Ir Applicationg Confer- 分组转发算法。结合矿下终端属性建立马尔可夫移动模型,预 Prce.2014:116-120. 测终端相遇概率;计算终端网络酎延、终端与目的终端相選概「σ童超,牛建伟,龙翔,竽.移动模型硏究综述「J.计箅机科学 率炇其扩散范围;根据层次分析法确定数据转发策略。仿真结 2009,36(10):5-10 果显示,本文提出的分组转发协议在网络时延、路由开销等方111 Hui pan, Crowcroft J, Yoneki e. BUBBLE rap: social- based for 均有明显优势,既解决了矿下恶劣环境下的通信问题,又解决 warding in delay tolerant networks[C// Proc of the 9th ACM Inter- 了机会网络中洪泛方式带来的大的数据开销问题,更加适合矿 national Symposium on Mobile Ad hoc Networking and Computing 下恶劣环境下的机会网络。但网络中终端数量较多时仍会造 New york, ACM Press 2008. 241-250 成一定的资源浪费,如何根据终端白由缓存空间大小、数据优 [12 Rusli M E, Harris R, Punchihewa A. Markov chain-based analytical 先级等选择合适的数据丢弃策略,进一步改詟网络路由开销是 model of opportunistic routing prmlnxol for wireless sensor networks [C// Proc of IEEE TENCON. 2010: 257-262. 下一步研究重点。 [13 Chen Meng, Wang Haiquan. A multi-ohjeclive rouling decision ma 参考文献 ing model for opportunistic network Cl// Proc of IEEE International [IⅠˉ王赟.煤矿井下常用无线通信技术综述[J].科技情报开发与经 Conference on Cloud Computing and Intelligence Systems. 2011 济,2010(20);218-219 316-320. [2.丌houiπg, Ying jing, Wu minghui. Formal laxouormy researchωn[14]李千日,张宏,姜海涛,等·基于无线射频的机会网络路由方 opportunistic networks[ C|// Proc of the 2nd IEEE International Con 法:中国,CNl02045809A「P.2011-0504 (上接笫196页) I 15 1 Guimeri R, Diaz-Cuilera A, Vega-Redondo F, ct al. Optimal net [9 llolme P. Congestion and centrality in traffic flow on complex net work topologies for local search with congestion[ J. Physical Re works[ J. Advances in Complex Systems, 2003, 6(2): 163-176 ew letters,2002,89(24):248701 [10 Daniele DM, Luca DA, Ginestra B, el al. Congestion phenomena [16 Danila B, Yu Yong, Marsh J A, et al. Transport optimization on on complex networks [J]. Physical RevieW E, 2009, 79(2 complex networks[ J. Chaos, 2007, 17(2):026102 015101 [17]钱江海,韩定定.基于预期流优化的空间网络引力模型[J].物流 [11 Echenique P, Gomez-Gardenes J, Moreno Y. Dy of jamming 学报,2009,58(5):3028-3033 transitions in complex networks J. Europhysics Letters, 2005, 71 (2):325-331 [18]刘刚,李水树.基于引力场理论的复杂网络路由选择策略硏究 「J1.物理学报,2012,61(24):248901 12 Bosiljka t, Rodgers G J, Stefan T. Transport on complex networks flow, jamming and optimization [_. International Journal of Bifur- [19] Song Haiquan, Guo Jin. Improved routing strategy based on gravita- cation and Chaos,2007,17(7):2363-2385 tional field theory [J_. Chinese Physics B, 2015, 24(10): 651 L13 Perotti J I, BilloniO V. Smart random walkers: the cost of knowin 658 the path[ J]. Physical Review E, 2012, 86(1): 011120 L 2U Arenas A, Diaz-Guilera A, Guimera R. Communication in networks [14 Noh D, Rieger H. Random walks on complex networks[.]. Physi with hierarchical branching J. Physical Review Letters, 2001. 86 cal Review Letters, 2004, 92(11): 118701 (14):3196-3199

...展开详情
img

关注 私信 TA的资源

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