D 算法及仿 D 算法的蚂蚁算法研究.doc

《D 算法及仿 D 算法的蚂蚁算法研究.doc》由会员分享，可在线阅读，更多相关《D 算法及仿 D 算法的蚂蚁算法研究.doc（4页珍藏版）》请在三一办公上搜索。

1、精品论文D 算法及仿 D 算法的蚂蚁算法研究许扬婧 北京邮电大学光通信与光电子学研究院，北京 (100876) E-mail：xyj1007摘要：本文首先介绍了经典的D算法，结合具体例子分析了如何寻找一点到其他点的最短 距离。其次，为了快捷可靠地寻找到满足多媒体QoS保证的路由，结合Dijkstra 算法和蚂蚁算法，从源节点开始，在所有满足QoS要求的邻接链路上泛滥寻路蚂蚁，在到达的所有寻路蚂蚁中选择其最优者复制并继续泛滥，直到最后到达目的节点为止。这样，通过约束条件下 的穷举搜索，最后一定可以找到源节点和目的节点间的满足QoS要求的路由。该算法具有思 路直观、运算量小、强收敛、能自适应网络变

2、动等优点。关键词：D 算法；蚂蚁算法；路由 中图分类号：TN911引言Dijstra 算法又叫 SPF 算法1，它是 Dijstra 提出的一个按长度递增的次序产生最短路径 的方法。从某个源节点到目地节点的最短路径就是所有到目的节点的路径中具有最小权值的 那条。Dijkstra 算法的基本思想是按照路径增加的顺序来寻找最短路径。这在传统的 best-effort 服务中是简单有效的，实际中也得到了最广泛应用。2基本的D算法D 算法可按下述步骤进行:初始化。首先，置定节点集 Vs=v1，其权值 D (v1)=0，此时，不在 Vs 中的其他每 个节点 v 皆未与 v1 相连，即 D(v1,，v)=

3、。其次，若有任一节点 v 欲与 v1 相连，但不一定是最短路径。设其未置定链路权值为d(vi,v)。若有置定节点 vs 经由中间节点 vi 连到未置定节点 vj，其 vs 到 vj 的链路权值则为: D(vs,vj)=D(vs,vi) +d(vi,vj)式中 D(vs,vj)为置定最小链路权值，d(vi,vj)为未置定链路权值。求节点集 V 中指定节点 v1 经 vi 到 vj 最小链路权值路由。要求满足下列关系式: D(v1,vj)=min D(v1,vj), (v1,vj)+d(vi,vj),vjV-VS式中 D(v1,vj)为含有节点 vi 的上次求得的最短径的最小链路权值; d(vi,

4、vj)为本次欲求节点 vi 和 vj 间链路权值; VS 为包含 v1 的置定子集;差集 V-VS 为未置定集。重复步骤 2 多次，直至 全部节点皆在 VS 中。按照最小权值要求，逐步缩小差集 V-VS,扩大置定子集 VS,直至 VSV， 算法结束。下面给出一段 Dijstra 算法的伪代码2。其中 C（i ,j）表示节点 i 到节点 j 的链接开销， 如果不是邻居节点，初始化的时候设置为无穷大；D（v）表示到节点 v 的当前路径的开销； N 表示最后确定的最小路径的节点的集合。下面就是算法的伪代码：Initialization：N=Afor all nodes vif v adjacent

5、to Athen D(v)=C(A,v)-4-else D(v)=inftyLoopfind w not in N such that D(w) is a minimum add w to Nupdate D(v) for all v adjacent to w and not in N; D(v)=min(D(v), D(w)+C(w,v)/*new cost to v is either old cost to v or knownShortest path cost to w plus cost from w to v*/ Until all nodes in NDijkstra算法的基

6、本思想是按照路径增加的顺序来寻找最短路径。这在传统的best-effort服务中是简单有效的，实际中也得到了最广泛应用。但Dijkstra算法存在以下不足3：（1）Dijkstra算法寻路时仅仅依据的是路径长短（常用网络跳数Hop表征），无法满足多 个QoS要求；（2）灵活性差，无法对网络的故障及拥塞做出反应。尽管如此，Dijkstra算法按照路径 增加的顺序来寻找最短路径的思想给我们提供了启发。虽然QoS路由参数不再只包括路径长 度一项，但QoS路由最终还是要把多个QoS参数映射为单一的评价度量，否则选择最优路由 根本无法做到。3改进蚂蚁算法原理借鉴于Dijkstra算法，我们注意到，从综合

7、的QoS评价指标来说，源节点到任何其他一个 节点的众多路径中，最优的路径肯定是唯一的。基于此原理，我们设计一种蚂蚁算法，从源 节点的相邻节点开始，通过蚂蚁泛滥，不断地计算并确定网络中每个节点到源节点的最优路 由，直到找到目的节点为止。3.1 蚂蚁泛滥要寻求网络中两点间的最优路径，可以对连接这两点间的所有路径进行比较，通过蚂蚁 泛滥，能很好地实现。源节点发送蚂蚁时，向它的所有满足QoS 要求的邻接点发送蚂蚁， 相邻节点把蚂蚁复制并向它的所有满足QoS 要求的相邻节点发送（刚才蚂蚁过来的那个节 点除外），为了防止蚂蚁无限制增长，每个应用对应的一批蚂蚁具有相同的ant-id，并做到： 蚂蚁要携带所有

8、经过路径的QoS 参数等必要信息，每当节点收到蚂蚁，都要跟先前到达的 相同ant-id 的蚂蚁比较，如果蚂蚁所经路径性能不比先前的好，就让该蚂蚁死亡，不再转发 蚂蚁。这样，保证了中间节点只把携带源节点到它的最优路径的蚂蚁得以转发出去，防止了 蚂蚁过度泛滥。如果网络中存在着符合要求的路径，寻路蚂蚁就一定能找到并原路返回通知 源节点。3.2 改进算法的具体实现3.2.1 人工蚂蚁设置ant（ant-id，source，aim，pssed -line，Line-fittness，QoSes，success），参数对应为4： 蚂蚁的应用标识号，源节点，目的节点，搜索路线，路线适应度，参数要求（QoSe

9、s表示参 数可能不止一个）,搜索成功标志位。3.2.2 源节点行为对应于每个应用，构造人工蚂蚁5，并在它所有满足QoSes 要求的邻接链路各放出一个， 然后开始等待找到路径的蚂蚁归来，且把不同路径回来的寻路成功的蚂蚁都保存好，然后择 最优一条使用。如图1所示，设源节点0有3个邻节点1，2，3，源节点0向邻接点1、2、3泛滥寻路蚂蚁， 然后节点1、2、3复制蚂蚁并向各自的邻接点进一步泛滥，其中节点5分别收到来自节点1、2 的两只蚂蚁，节点5择其中一个优良的进行复制泛滥。源节点0蚂蚁（01）1蚂蚁（03）蚂蚁（02）23蚂蚁（014）蚂蚁（025）蚂蚁（023）蚂蚁（015）蚂蚁（026）蚂蚁（0

10、27）4567图1 源节点寻QOS路由3.2.3 中间节点行为 首先判断是不是新应用的蚂蚁，如果是新应用，先判断本身是否就是目的节点，如果本身就是目的节点，就制作报信蚂蚁6，原路送回；若不符合QoSes要求，则让寻路蚂蚁死亡，不做任何处理；如果本身还不是目的节点，则对寻路蚂蚁加上本节点信息，然后向所有满足QoSes要求的节点继续泛滥蚂蚁。 如果不是新的应用，先判断此蚂蚁是否先前已经过本节点（防止回路）；再和以前保存的同一批次的蚂蚁做比较，性能如果没有原来的好，则让这个刚到达的蚂蚁死亡；如果新蚂 蚁性能更好，则意味着重新发现了一条新的源节点到本节点的更好路径，马上把蚂蚁做相应 改动（包括将本身节

11、点代号加入pssed-line，更新Line-fittness）并保存，然后往所有邻接链路送出新蚂蚁（除了刚才来时一条路径不送）。如图2所示。中间节点寻路蚂蚁 来到是新应用？ Y NY本身是 目的节点？N结合本路参数， 重新计算 QoS构造报信蚂蚁Y此路径满足NQoS 要求？满足 QoSN要求？返回 源节点蚂蚁死 亡路径性能更优良？YN最优存档，重新向邻 接点发送蚂蚁蚂蚁死亡Y蚂蚁泛滥存档，向邻接 点发送蚂蚁图2 中间节点处理寻路蚂蚁4总结本文受Dijkstra 算法的直观简单性启发，结合蚂蚁算法，不使用外激素，提出了一种QoS路由的新算法，经理论分析和例子证明，具有下列特点：算法思路直观。D

12、ijkstra 算法是一个很成熟的算法，文中提出，针对不同应用，我们只 要设置相对应的适应度函数，肯定可以找到源节点到目的节点的最优QoS 路由，就如同 Dijkstra 算法中找到最短路由一样。算法具有维护简单性。各个节点只需维护邻接链路信息，网络不必定期广播全局链路信 息，网络局部的故障不会影响全局。算法具有强收敛性。由于采用穷举遍历，只要存在最优路由，就肯定能找到。由于对蚂 蚁泛滥之前做了优劣比较，不会造成蚂蚁无限增长。参考文献1 刘洋基于改进D算法的动态拓扑结构全光网络路由算法D北京：20052 计会凤，徐爱功，隋达嵬Dijkstra算法的设计与实现J辽宁工程技术大学学报(自然科学版)

13、,2008,(S1)3 岳秋菊. 基于最短路径优化问题Dijkstra算法程序的设计和实现J甘肃高师学报, 2008，(02)4 丁建立,陈增强,袁著祉基于混合蚂蚁算法的网络资源均衡与优化A中国仪器仪表学会第五届青年 学术会议论文集C，20035 陈骏坚.基于新型蚂蚁算法的QoSR理论及技术研究D武汉理工大学：20066 Dorigo M，Gambardella L MAnt colony system: A cooperative learning approach to the traveling salesman problem，IEEE Trans. Evolutionary Comp

14、utation，1997，1(1):53-66Study of Dijkstra and Ant AlgorithmXu YangjingKey Laboratory of Optical Communication and Lightwave Technologies, Ministry of Education, Beijing University of Posts and Telecommunications, Beijing, PRC, (100876)AbstractThis article first introduces the classic D algorithm, com

15、bined with an analysis of specific examples ofhow to find the point to other points of the shortest distance. Secondly, in order to efficiently and effectively to meet the multi-media search to guarantee QoS routing, combined with Dijkstra algorithm and the ant algorithm, from the source node, to me

16、et all the QoS requirements of the adjacent link on the road look for the proliferation of ants, reaching all the ants look for in the road Select the best person to copy and continue to spread until the Node until the end and reach our destination. In this way, through the constraints of the exhaus

17、tive search, the final will be able to find the source and destination nodes between the node to meet the requirements of QoS routing. The algorithm is intuitive thinking, a small amount of computing, strong convergence, adaptive to changes in the network advantages.Keywords: dijkstra algorithm, ant algorithm, route