延迟容忍网络中一种基于节点介数的拥塞感知路由算法

A Node Betweenness Based Congestion Aware Routing Algorithm for DTNs

确定性延迟容忍网络中,节点间的接触往往表现出一定的重复性和规律性.现有的确定性路由算法通常根据网络全局或部分的先验知识构建网络演化图,将路由选择过程转换为利用经典路由算法求解最短路径的问题.然而,这类算法中消息的转发一般采用预先计算好的路径,缺乏对网络状态的自适应性.网络流量可能集中于部分的活跃节点,造成这部分节点过度的资源消耗,从而导致网络拥塞.提出一种基于节点介数的拥塞感知路由算法,该算法通过网络拓扑的时空演化图计算出节点间延时开销最小的多条备选路径,同时引入节点介数来指示节点的负载情况.在转发路径的选择过程中,结合路径的延迟开销和介数值以不同的概率从备选路径集合中选择实际转发路径.仿真结果表明该算法有效地减少了网络负载不均造成的局部拥塞现象,提高了网络消息的交付性能.

In deterministic delay tolerant networks, the contact between nodes often show some repetitiveness and regularity. The existing deterministic routing algorithms usually construct an evolving graph based on the whole or partial priori knowledge of network, and then the route selection can be converted into solving the classic shortest path problem. However, since messages are forwarded by using the precalculated path, such algorithms often lack the adaptability against the change of network state. The traffic may concentrate on partial active nodes, which hastens the drawdown of resources and finally results in network congestion. This paper proposes a node betweenness based congestion aware routing algorithm which calculates multiple disjoint alternative paths with least delay by using the evolving graph, and introduces the node betweenness to indicate the load on nodes. In the routing process, the forwarding path is probabilistically selected among the set of alternative paths according to the path delay and betweenness value. Simulation results show that our algorithm effectively reduces the local congestion caused by network load unbalance and improves the message delivery ratio.