基于博弈论的容迟网络中布雷斯路由悖论研究
|
摘要
容忍网络中的布雷斯(Braess)路由悖论现象对于其网络拓扑设计的高效性和合理性的提升具有重要的意义。对容迟网络常用的路由算法进行了分析,得出链路状态路由算法克服了距离矢量路由算法收敛慢、容易成环的缺点;但此算法采用的是迪杰斯特拉(Dijkstra)算法,每次寻找的是最短路径,可能会在一定情况下出现悖论现象。因此通过博弈理论的基本原理分析了Braess悖论及其对偶形式的存在性,对应于上述算法中,在其他条件不变的前提下,增加网络负载权值,提高了选择过程的效率。最后,在仿真实验中随机建立容迟网络的路由节点,规定路由节点间的距离、传输速度等权值,并收集多组基于不同网络特征参数的数据样本,编程来模拟路由算法并进行数据分析,进一步验证了Braess悖论在容迟网络路由算法中的存在。
The Braess' s routing paradox in the tolerance network is of great significance to the efficiency and rationality of their network topology design. In this paper,we analyze the routing algorithms commonly used in networks, and it's concluded that the link-state routing algorithm overcomes the shortcoming of slow convergence and easy loop formation of the distance vector routing algorithm. However,this algorithm adopts the Dijkstra algorithm,which looks for the shortest path each time, and may encounter paradoxes under certain circumstances. Therefore, the existence of the Braess' s paradox and its dual form is analyzed through the basic principle of the game theory,which corresponds to the above algorithm. Under other conditions unchanged, the weight of network load is increased to improve the efficiency of the selection process. Finally, in the simulation experiment,we randomly set up the routing node of the delay tolerant network,specify the distance between routing nodes, transmission speed and other weights, collect multiple sets of data samples based on the characteristics of different network parameters, and simulate the routing algorithm by programming and conduct the data analysis,which further validates the existence of Braess' s paradox in the delay tolerant network routing algorithm.
The Braess' s routing paradox in the tolerance network is of great significance to the efficiency and rationality of their network topology design. In this paper,we analyze the routing algorithms commonly used in networks, and it's concluded that the link-state routing algorithm overcomes the shortcoming of slow convergence and easy loop formation of the distance vector routing algorithm. However,this algorithm adopts the Dijkstra algorithm,which looks for the shortest path each time, and may encounter paradoxes under certain circumstances. Therefore, the existence of the Braess' s paradox and its dual form is analyzed through the basic principle of the game theory,which corresponds to the above algorithm. Under other conditions unchanged, the weight of network load is increased to improve the efficiency of the selection process. Finally, in the simulation experiment,we randomly set up the routing node of the delay tolerant network,specify the distance between routing nodes, transmission speed and other weights, collect multiple sets of data samples based on the characteristics of different network parameters, and simulate the routing algorithm by programming and conduct the data analysis,which further validates the existence of Braess' s paradox in the delay tolerant network routing algorithm.
引文
[1] HUI Pan,CROWCROFT J,YONEKI E.BUBBLE rap:social-based forw arding in delay-tolerant netw orks[C]//Proceedings of the 9th ACM international symposium on mobile ad hoc netw orking and computing.Hong Kong,China:ACM,2008:241-250.
[2] KAWECKI M,SCHOENEICH R O.Mobility-based routing algorithm in delay tolerant netw orks[J]. EURASIP Journal on Wireless Communications&Netw orking,2016(1):1-9.
[3] CHOUDHARY N,SINGH V. Performance enhancement of routing protocol for longer life time of WSN[J].International Journal of Computer Applications,2015,109(11):16-19.
[4] ZENG Deze,GUO Song,HU Jiankun. Reliable bulk-data dissemination in delay tolerant netw orks[J]. IEEE Transactions on Parallel&Distributed Systems,2014,25(8):2180-2189.
[5] CAO Wei,CAO Guohong,PORTA T L,et al.On exploiting transient social contact patterns for data forw arding in delaytolerant netw orks[J]. IEEE Transactions on M obile Computing,2013,12(1):151-165.
[6] MENG Tong,WU Fan,YANG Zheng,et al. Spatial reusability-aw are routing in multi-hop w ireless netw orks[J].IEEE Transactions on Computers,2016,65(1):244-255.
[7] WANG Ruhai,WEI Zhiguo,ZHANG Qinyu,et al.LTP aggregation of DTN bundles in space communications[J].IEEE Transactions on Aerospace&Electronic Systems,2013,49(3):1677-1691.
[8] MING Zhongxing,XU Mingwei,WANG Dan.Age-based cooperative caching in information-centric netw orking[C]//International conference on computer communication and netw orks.Shanghai,China:IEEE,2012:1-8.
[9] CHANG M,PENG S,LIAW J.Deferred-query:an efficient approach for some problems on interval graphs[J]. Netw orks,2015,34:1-10.
[10] WITTHAUT D,TIMME M. Nonlocal failures in complex supply netw orks by single link additions[J].European Physical Journal B,2013,86:377.
[11] TAGUCHI A.Braess'paradox in a two-terminal transportation netw ork[J]. Journal of the Operations Research Society of Japan,2017,25(4):376-389.
[12] XU Meng,WANG Guangmin,GRANT-MULLER S,et al.Joint road toll pricing and capacity development in discrete transport netw ork design problem[J]. Transportation,2017,44(4):731-752.
[13]刘巍,曾庆山.基于复杂网络的Braess悖论现象[J].计算机工程与设计,2015,36(4):1098-1102.
[14]董顺珍.蜈蚣博弈悖论理性人的认知分析[J].长江丛刊,2017(18):148.
[15]余孝军,黄海军.交通网络效率的度量和元件重要性的计算方法[J].系统工程理论与实践,2012,32(7):1546-1552.
[16]傅白白,刘法胜.管理中的Nash平衡与Braess悖论现象[J].运筹与管理,2004,13(1):150-155.
[2] KAWECKI M,SCHOENEICH R O.Mobility-based routing algorithm in delay tolerant netw orks[J]. EURASIP Journal on Wireless Communications&Netw orking,2016(1):1-9.
[3] CHOUDHARY N,SINGH V. Performance enhancement of routing protocol for longer life time of WSN[J].International Journal of Computer Applications,2015,109(11):16-19.
[4] ZENG Deze,GUO Song,HU Jiankun. Reliable bulk-data dissemination in delay tolerant netw orks[J]. IEEE Transactions on Parallel&Distributed Systems,2014,25(8):2180-2189.
[5] CAO Wei,CAO Guohong,PORTA T L,et al.On exploiting transient social contact patterns for data forw arding in delaytolerant netw orks[J]. IEEE Transactions on M obile Computing,2013,12(1):151-165.
[6] MENG Tong,WU Fan,YANG Zheng,et al. Spatial reusability-aw are routing in multi-hop w ireless netw orks[J].IEEE Transactions on Computers,2016,65(1):244-255.
[7] WANG Ruhai,WEI Zhiguo,ZHANG Qinyu,et al.LTP aggregation of DTN bundles in space communications[J].IEEE Transactions on Aerospace&Electronic Systems,2013,49(3):1677-1691.
[8] MING Zhongxing,XU Mingwei,WANG Dan.Age-based cooperative caching in information-centric netw orking[C]//International conference on computer communication and netw orks.Shanghai,China:IEEE,2012:1-8.
[9] CHANG M,PENG S,LIAW J.Deferred-query:an efficient approach for some problems on interval graphs[J]. Netw orks,2015,34:1-10.
[10] WITTHAUT D,TIMME M. Nonlocal failures in complex supply netw orks by single link additions[J].European Physical Journal B,2013,86:377.
[11] TAGUCHI A.Braess'paradox in a two-terminal transportation netw ork[J]. Journal of the Operations Research Society of Japan,2017,25(4):376-389.
[12] XU Meng,WANG Guangmin,GRANT-MULLER S,et al.Joint road toll pricing and capacity development in discrete transport netw ork design problem[J]. Transportation,2017,44(4):731-752.
[13]刘巍,曾庆山.基于复杂网络的Braess悖论现象[J].计算机工程与设计,2015,36(4):1098-1102.
[14]董顺珍.蜈蚣博弈悖论理性人的认知分析[J].长江丛刊,2017(18):148.
[15]余孝军,黄海军.交通网络效率的度量和元件重要性的计算方法[J].系统工程理论与实践,2012,32(7):1546-1552.
[16]傅白白,刘法胜.管理中的Nash平衡与Braess悖论现象[J].运筹与管理,2004,13(1):150-155.