一种基于蚁群算法的容迟网络路由策略

ACR:An Ant-Colony-based Routing in Delay Tolerant Networks

延迟容忍网络(容迟网络)涵盖了星际网络、移动Ad Hoc网络以及偏远地区网络等许多除因特网以外的通信网络.网络的频繁断裂和间歇连接使容迟网络路由问题成为最具挑战的问题之一.蚁群优化算法作为一种在图中寻找优化路径的机率型技术,已广泛应用于许多领域,它具有正反馈、分布式计算和智能型优化等特点.为提高路由算法对网络拓扑变化的适应能力,研究基于蚁群算法的路由策略,并通过其智能自适应优化减少容迟网络传输延迟.首先模型化容迟网络的数据传输问题;其次设计基于蚁群算法的路由策略(ant-colony-based routing,ACR),包括转发和复制两种数据分配方式;最终基于容迟网络公共数据集Infocom Trace和RollerNet Trace进行仿真验证,并与MED,SimBet,Spray和Wait以及EBR等经典算法比较.仿真结果表明:基于转发方式的ACR算法比其他同类型算法至少缩短25.8%的传输延迟,基于复制方式的ACR算法至少降低22.5%的传输延迟.

Due to the frequent partitions and intermittent connections, routing becomes one of the most challenging problems in delay tolerant networks （DTNs）, which can be extensively applied in many domains, such as interplanetary networks, mobile ad hoc networks and networks in remote areas, etc. Ant colony optimization （ACO）, a probabilistic technique for finding an optimal path in a graph, is widely used in many other areas. The advantages of ACO can be concluded as positive feedback, distributed calculating, and intelligent optimization. To improve the adoption to dynamic topology, this paper investigates a routing algorithm based on ant colony to reduce the delivery delay by its intelligent and self-adapting optimization. In this paper, we first model message delivery in DTNs, and then propose our Ant-colony-based routing algorithm （ACR） which is used to guide message delivery, including forwarding-based and replication-based schemes. To show the performance of our algorithm, we finally evaluate ACR on public available data set Infocom Trace and RollerNet Trace against MED, SimBet, Spray ~ Wait and EBR. The simulation results show that forwarding-based ACR performs at least 25. 8% better than other forwarding-based algorithms in delivery delay, and replication-based ACR achieves at least 22.5% shorter delivery delay.