CCN中一种非混合式蚁群路由优化策略
|
摘要
蚁群优化(ant colony optimization,ACO)近年来在信息中心网络(content centric networking,CCN)路由领域的应用逐渐增多,其中,将ACO与其他机制相混合以改善路由性能的策略得到较多研究,但基于蚁群优化的混合式算法通常存在可扩展性低下,动态性差,网络成本高等问题。为此提出一种高效的非混合式蚁群路由算法(irritant ant framework,IAF)。添加一个新维度—一种动态的、仿生物的信息素分层,将传统单级别信息素上升为多级别信息素,增强蚁群对于路径的探索程度,抑制算法过早收敛;并且考虑了节点状态的动态性,实时改变信息素等级以选择最佳转发路径;此外,首次考虑了节点缓存特性对信息素更新策略的影响,构造出全新的信息素更新公式,减小算法的收敛时间。实验结果表明,该算法能够有效地降低内容请求时延,提升缓存命中率,以较低的开销获得良好的CCN路由性能。
The application of ant colony optimization( ACO) in the field of content centric networking( CCN) routing has been increasing. The strategy which mixes ACO with other mechanisms to improve the routing performance has received more research. However,the hybrid algorithm based on ACO has been showing low scalability,poor dynamism and high investment cost. In this paper we present an efficient non-hybrid ant colony routing strategy( IAF,irritant ant framework) to address these problems. It adds a new dimension-a dynamic,biologically-inspired pheromone stratification,rising from the traditional single level pheromone to multiple level pheromones,which fully explores the path information and suppresses premature convergence of the algorithm; and it considers the dynamics of the node state and changes the pheromone level in real time to select the optimal forwarding path. In addition,it also considers for the first time the influence of characteristics of node cache on the pheromone update strategy and constructs a new pheromone updating formula to reduce the convergence time. The simulation results show that the scheme is able to decrease the request latency,increase the cache hit ratio,while improving the overall performance of content delivery with a low amount of additional overhead.
The application of ant colony optimization( ACO) in the field of content centric networking( CCN) routing has been increasing. The strategy which mixes ACO with other mechanisms to improve the routing performance has received more research. However,the hybrid algorithm based on ACO has been showing low scalability,poor dynamism and high investment cost. In this paper we present an efficient non-hybrid ant colony routing strategy( IAF,irritant ant framework) to address these problems. It adds a new dimension-a dynamic,biologically-inspired pheromone stratification,rising from the traditional single level pheromone to multiple level pheromones,which fully explores the path information and suppresses premature convergence of the algorithm; and it considers the dynamics of the node state and changes the pheromone level in real time to select the optimal forwarding path. In addition,it also considers for the first time the influence of characteristics of node cache on the pheromone update strategy and constructs a new pheromone updating formula to reduce the convergence time. The simulation results show that the scheme is able to decrease the request latency,increase the cache hit ratio,while improving the overall performance of content delivery with a low amount of additional overhead.
引文
[1]JACOBSON V,SMETTERS D K,THORNTON J D,et al.Networking named content[C]//Proceedings of the5th international conference on Emerging networking experiments and technologies.New York:ACM,2009:1-12.
[2]CHOI J,HAN J,CHO E,et al.A survey on content-oriented networking for efficient content delivery[J].IEEE Communications Magazine,2011,49(3):121-127.
[3]张岩.内容中心网络的路由转发机制研究[D].北京:北京邮电大学,2014.ZHANG Yan.Research on routing and forwarding schemes for content centric network[D].Beijing:Beijing University of Posts and Telecommunications,2014.
[4]DORIGO M,MANIEZZO V,COLORNI A.Ant system:optimization by a colony of cooperating agents[J].IEEE Transactions on Systems,Man and Cybernetics-Part B(Cybernetics),1996,26(1):29-41.
[5]SIM K M,SUN W H.Ant colony optimization for routing and load-balancing:survey and new directions[J].IEEE Transactions on Systems,Man and Cybernetics-Part A:Systems and Humans,2003,33(5):560-572.
[6]PING G,XIU C,YI C,et al.Adaptive ant colony optimization algorithm[C]//International Conference on Mechatronics and Control.New York:IEEE Press,2014:95-98.
[7]张国印,唐滨,孙建国,等.面向内容中心网络基于分布均匀度的蚁群路由策略[J].通信学报,2015,36(6):1-12.ZHANG Guoyin,TANG Bin,SUN Jianguo,et al.Ant colony routing strategy based on distribution uniformity degree for content centric network[J].Journal on Communications,2015,36(6):1-12.
[8]DORIGO M,GAMBARDELLA L M.Ant colony system:a cooperative learning approach to the traveling salesman problem[J].IEEE Transactions on evolutionary computation,1997,1(1):53-66.
[9]STTZLE T,HOOS H H.MAX-MIN ant system[J].Future generation computer systems,2000,16(8):889-914.
[10]STTZLE T,DORIGO M.A short convergence proof for a class of ant colony optimization algorithms[J].IEEE Trans.Evolutionary Computation,2002,6(4):358-365.
[11]BLIMAN P A,BHAYA A,KASZKUREWICZ E,et al.Convergence results for continuous-time dynamics arising in ant colony optimization[J].IFAC Proceedings Volumes,2014,47(3):7031-7036.
[12]GUTJAHR W J.ACO algorithms with guaranteed convergence to the optimal solution[J].Information processing letters,2002,82(3):145-153.
[13]STTZLE T,HOOS H.The max-min ant system and local search for combinatorial optimization problems[M]//Meta-heuristics.[S.l.]:Springer,1999:313-329.
[14]SHANBHAG S,SCHWAN N,RIMAC I,et al.So CCeR:Services over content-centric routing[C]//Proceedings of the ACM SIGCOMM workshop on Information-centric networking.New York:ACM,2011:62-67.
[15]CHEN S H,KAMBAYASHI Y,SATO H.Multi-Agent Applications with Evolutionary Computation and Biologically Inspired Technologies:Intelligent Techniques for Ubiquity and Optimization[J].Bmc Genomics,2009,10(4):334.
[16]MICHLMAYR E,PANY A,KAPPEL G.Using taxonomies for content-based routing with ants[J].Computer Networks,2007,51(16):4514-4528.
[17]SALAMA K M,ABDELBAR A M,FREITAS A A.Multiple pheromone types and other extensions to the Ant-Miner classification rule discovery algorithm[J].Swarm Intelligence,2011,5(3-4):149-182.
[18]SALAMA K M,ABDELBAR A M,OTERO F E B,et al.Utilizing multiple pheromones in an ant-based algorithm for continuous-attribute classification rule discovery[J].Applied Soft Computing,2013,13(1):667-675.
[19]HLLDOBLER B,WILSON E O.The ants[M].Ney:Harvard University Press,1990.
[20]刘涛,程东年,田铭.基于副本通告的内容中心网络快捷路由机制[J].计算机工程,2014,40(5):62-67.LIU Tao,CHENG Dongnian,TIAN Ming.Short-cut Routing Mechanism in Content Centric Network Based on Replicas Notification[J].Computer Engineering,2014,40(5):62-67.
[21]丰宁宁,王成华.一种基于分布式协作的WSN定位方法[J].计算机技术与发展,2012,22(5):60-63.FENG Ningning,WANG Chenghua.A Type of Localization Method Based on Distributed Collaboration for Wireless Sensor Networks[J].Computer Technology&Development,2012,22(5):60-63.
[2]CHOI J,HAN J,CHO E,et al.A survey on content-oriented networking for efficient content delivery[J].IEEE Communications Magazine,2011,49(3):121-127.
[3]张岩.内容中心网络的路由转发机制研究[D].北京:北京邮电大学,2014.ZHANG Yan.Research on routing and forwarding schemes for content centric network[D].Beijing:Beijing University of Posts and Telecommunications,2014.
[4]DORIGO M,MANIEZZO V,COLORNI A.Ant system:optimization by a colony of cooperating agents[J].IEEE Transactions on Systems,Man and Cybernetics-Part B(Cybernetics),1996,26(1):29-41.
[5]SIM K M,SUN W H.Ant colony optimization for routing and load-balancing:survey and new directions[J].IEEE Transactions on Systems,Man and Cybernetics-Part A:Systems and Humans,2003,33(5):560-572.
[6]PING G,XIU C,YI C,et al.Adaptive ant colony optimization algorithm[C]//International Conference on Mechatronics and Control.New York:IEEE Press,2014:95-98.
[7]张国印,唐滨,孙建国,等.面向内容中心网络基于分布均匀度的蚁群路由策略[J].通信学报,2015,36(6):1-12.ZHANG Guoyin,TANG Bin,SUN Jianguo,et al.Ant colony routing strategy based on distribution uniformity degree for content centric network[J].Journal on Communications,2015,36(6):1-12.
[8]DORIGO M,GAMBARDELLA L M.Ant colony system:a cooperative learning approach to the traveling salesman problem[J].IEEE Transactions on evolutionary computation,1997,1(1):53-66.
[9]STTZLE T,HOOS H H.MAX-MIN ant system[J].Future generation computer systems,2000,16(8):889-914.
[10]STTZLE T,DORIGO M.A short convergence proof for a class of ant colony optimization algorithms[J].IEEE Trans.Evolutionary Computation,2002,6(4):358-365.
[11]BLIMAN P A,BHAYA A,KASZKUREWICZ E,et al.Convergence results for continuous-time dynamics arising in ant colony optimization[J].IFAC Proceedings Volumes,2014,47(3):7031-7036.
[12]GUTJAHR W J.ACO algorithms with guaranteed convergence to the optimal solution[J].Information processing letters,2002,82(3):145-153.
[13]STTZLE T,HOOS H.The max-min ant system and local search for combinatorial optimization problems[M]//Meta-heuristics.[S.l.]:Springer,1999:313-329.
[14]SHANBHAG S,SCHWAN N,RIMAC I,et al.So CCeR:Services over content-centric routing[C]//Proceedings of the ACM SIGCOMM workshop on Information-centric networking.New York:ACM,2011:62-67.
[15]CHEN S H,KAMBAYASHI Y,SATO H.Multi-Agent Applications with Evolutionary Computation and Biologically Inspired Technologies:Intelligent Techniques for Ubiquity and Optimization[J].Bmc Genomics,2009,10(4):334.
[16]MICHLMAYR E,PANY A,KAPPEL G.Using taxonomies for content-based routing with ants[J].Computer Networks,2007,51(16):4514-4528.
[17]SALAMA K M,ABDELBAR A M,FREITAS A A.Multiple pheromone types and other extensions to the Ant-Miner classification rule discovery algorithm[J].Swarm Intelligence,2011,5(3-4):149-182.
[18]SALAMA K M,ABDELBAR A M,OTERO F E B,et al.Utilizing multiple pheromones in an ant-based algorithm for continuous-attribute classification rule discovery[J].Applied Soft Computing,2013,13(1):667-675.
[19]HLLDOBLER B,WILSON E O.The ants[M].Ney:Harvard University Press,1990.
[20]刘涛,程东年,田铭.基于副本通告的内容中心网络快捷路由机制[J].计算机工程,2014,40(5):62-67.LIU Tao,CHENG Dongnian,TIAN Ming.Short-cut Routing Mechanism in Content Centric Network Based on Replicas Notification[J].Computer Engineering,2014,40(5):62-67.
[21]丰宁宁,王成华.一种基于分布式协作的WSN定位方法[J].计算机技术与发展,2012,22(5):60-63.FENG Ningning,WANG Chenghua.A Type of Localization Method Based on Distributed Collaboration for Wireless Sensor Networks[J].Computer Technology&Development,2012,22(5):60-63.