基于博弈论的容迟网络中布雷斯路由悖论研究-《计算机技术与发展》

文章信息/Info

Title:: Research on Braess’s Routing Paradox in Delay Tolerant Networks Based on Game Theory

Author(s):: ZHAO Chen-xi; WANG Yang; XU Shan-shan; MENG Dan; ZHAO Chuan-xin; School of Mathematics &Computer Science,Anhui Normal University,Wuhu 241000,China

Keywords:: delay tolerant network; link state routing algorithm; Dijkstra algorithm; Braess’s paradox; game theory

摘要:: 容忍网络中的布雷斯(Braess)路由悖论现象对于其网络拓扑设计的高效性和合理性的提升具有重要的意义。对容迟网络常用的路由算法进行了分析,得出链路状态路由算法克服了距离矢量路由算法收敛慢、容易成环的缺点;但此算法采用的是迪杰斯特拉(Dijkstra)算法,每次寻找的是最短路径,可能会在一定情况下出现悖论现象。因此通过博弈理论的基本原理分析了 Braess 悖论及其对偶形式的存在性,对应于上述算法中,在其他条件不变的前提下,增加网络负载权值,提高了选择过程的效率。最后,在仿真实验中随机建立容迟网络的路由节点,规定路由节点间的距离、传输速度等权值,并收集多组基于不同网络特征参数的数据样本,编程来模拟路由算法并进行数据分析,进一步验证了 Braess 悖论在容迟网络路由算法中的存在。

Abstract:: 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.