冯晓东， 梁红硕

(1.中国人民解放军总参谋部信息化部 驻石家庄地区军事代表室， 河北 石家庄 050081；2.石家庄职业技术学院 信息工程系，河北 石家庄 050081)



路由算法的设计与优化

冯晓东1， 梁红硕2

(1.中国人民解放军总参谋部信息化部 驻石家庄地区军事代表室， 河北 石家庄 050081；2.石家庄职业技术学院 信息工程系，河北 石家庄 050081)

应用迪杰斯特拉算法和弗洛伊德算法进行路由链路设计时，可以找到最短路径，但可能引起网络负载的不均衡.在考虑网络综合性能的基础上，对这两种算法增加链路或在生成链路时加入节点度的限制，可实现路由算法的优化，减少网络负载不均衡情况的发生.

路由算法；迪杰斯特拉算法；弗洛伊德算法

对路由算法的设计，起源于图论中最短路径的求解.在图论中，考虑的基本元素是节点和各节点之间线路的权值.求解最短路径的过程类似于交通系统中的道路查询，即从某地经由哪条路线到达某地的路线最短，最短路径亦由此得名.应用迪杰斯特拉算法和弗洛伊德算法可实现路由链路设计，找到最短路径，但其均可能引起网络负载的不均衡，因此，本文对这两种算法进行了改进，在考虑网络综合性能的基础上增加约束条件，以达到优化算法的目的.

1 应用迪杰斯特拉(Dijkstra)算法实现链路设计

求解最短路径的算法最先是从求解某一个节点到达其他所有节点的最短路径开始的，这就是迪杰斯特拉算法.它考虑按照路径长度递增的次序产生最短路径.首先，构造一个已求得最短路径的节点的集合S，开始时S中只有一个初始节点；其次，找到从S中的节点到其他所有节点路径最短的节点，并加入到S中，再对所有节点进行循环.当所有节点都加入到集合S中时，就认为找到了从初始节点到其他所有节点的最短路径.

假设图G中有n个节点，分别是V0到Vn，数组D存放图中从初始节点V0到Vw的距离，arc存放图中Vi到Vj的距离，动态数组LinkS用于按序存放每一个加入到集合S中的节点的下标.初始时，这些距离都是两个节点间的直接距离.经过迪杰斯特拉算法后，数组D存放初始节点V0到图中其他n-1个节点间的最短距离，而从初始节点V0出发所找到的最短路径则存放在LinkS数组中.

迪杰斯特拉算法包含内外两重循环.内层第一个循环用于找到从集合S中的某个节点到其他所有节点的最短路径，并将找到的节点加入集合S中；内层第二个循环用于找到某个节点，并加入集合S后修改节点间的最短距离，存入数组D.外层循环则表示要经过n次才能将所有节点都加入到集合S中.对于有n个节点的图，此算法的时间复杂度为O(n2).但此算法并不能直接应用于网络拓扑结构的生成，通过对此算法再加一层循环，即对所有的节点执行此算法，才能得到网络中任一节点到其他节点的最短路径.应用这个算法，要对原算法中的几项变量进行调整，如数组D要改为二维数组，存放任意两节点间的最短距离；动态数组LinkS也要改为二维数组，其中，第一维用于表示选择哪个节点作为初始节点，第二维则仍是动态数组，用于存放从初始节点出发找到的最短路径.此算法是在原算法外增加一层循环，因此时间复杂度为O(n3).

此算法所找到的最短路径集合存放在LinkS数组中.实际程序中通常要模拟画出拓扑结构.此时，只要对此LinkS数组进行一个循环，取出任意两个相连的节点分别作为一条链路的起始节点和终止节点，并添加到链路数组中，同时注意不要出现链路重复，即可用此链路数组画出拓扑图.

2 应用弗洛伊德(Floyd)算法实现链路设计

求解任意两个节点之间的最短路径问题，可以通过修改迪杰斯特拉算法实现，而弗洛伊德算法则专门用于解决这一问题.弗洛伊德算法用于直接求解图中任意两个节点间的最短路径.此算法形式上比迪杰斯特拉算法简单，但是算法的时间复杂度相同.其基本思想是：对于任意两个节点Vi和Vj之间的距离D，在其余的n-2个节点中选取一个节点Vw，比较D和D+D的大小，若Vi通过Vw到达Vj的距离更短，则令最短路径数组P得到w，同时更新D的值，然后再分别对(Vi，Vw)和(Vw，Vj)进行相同的操作.这样，就能够找到任意两个节点间的最短距离，并存放于二维数组D中，同时，将最短路径存放于二维数组P中.

在实际绘制拓扑图时，此算法还需进一步处理，即由数组P得到所有的链路数组.这是一个递归求解的过程，链路数组为节点的动态数组，存放于Link中.其算法流程如图1所示.其中，Link.Insert(a,i,j)表示将a插入Link数组的i，j之间.

图1 弗洛伊德(Floyd)算法链路

3 路由算法的优化

在网络规划系统中，路由算法的求解不能单纯以生成链路的速度作为评价指标，因为在实际的网络中，各种性能参数的存在会对网络拓扑的性能造成很大的影响.如果简单地以路径生成算法的速度作为拓扑生成的主要依据，实际得到的链路性能反而可能下降.因此，要对算法进行一定的改进，在考虑网络综合性能的基础上对算法加上约束条件.如，在一个拥有80个节点的网络中，假设节点A正好处于网络的中央，那么根据常规的路由算法，生成的链路很可能都要经过节点A，如果节点C经过节点A到达节点B，同时节点D通过节点A到达节点E.在这种情况下，如果用户在节点C与B，D与E之间都配送大量的业务数据，则这些业务数据都要流经节点A.如果除节点A外的79个节点间的业务数据都要流经节点A，对节点A会是非常大的负担.同时，网络中的边缘节点相关的业务链路可能只有一两条，那么在这些边缘节点上，资源就会造成很大的浪费.所以单纯地追求网络节点间的最短路径是不可取的.

解决这一问题，有两种思路.第一种是增加链路.例如，让节点C和节点B直接连通，当经过节点A的业务量过大时，在配送节点C与B之间的业务时，直接在节点C与B之间增设链路.而这是以增加硬件设施为基础的.从软件设计的角度看，相关的处理代码要放到业务层.第二种思路是在生成链路时加入节点度的限制，即对任意一个节点，要对它所关联的链路数量设置约束条件.对于迪杰斯特拉算法，节点度的限制应该加在获取链路的代码中，即在数组Link中加入一个节点对(i，j)之前先对数组Link进行搜索.假如节点度限制最大为5，如果在Link中已经存在的节点对中的i或j已经出现了5次，则此节点对不加入链路中.对于弗洛伊德算法，加入约束条件的方式和迪杰斯特拉算法相似，但是判断条件简单.在向Link数组中加入某个节点s时，首先对Link数组进行搜索，看s出现的次数是否达到了5次，如果出现5次就不再添加.算法如图2所示.

节点度的增加会带来算法时间复杂度的消耗，尤其会使网络拓扑中任意两个节点间的路径不一定最短.但是，这一代价所换来的好处是可以确保网络负载均衡，提高网络的整体性能.

图2 在弗洛伊德算法中增加约束条件的算法链路

[1]万健.NoC路由算法设计与实现.南京：南京大学，2011.

[2]杜加琴.片上网络的拓扑结构设计和路由算法研究.合肥：安徽大学，2012.

责任编辑：金 欣

Design and optimization of routing algorithm

FENG Xiao-dong1， LIANG Hong-shuo2

(1.Information Department，General Staff Headquarters PLA，Shijiazhuang，Hebei 050081，China;2.Department of Information Technology，Shijiazhuang Vocational Technology Institute，Shijiazhuang，Hebei 050081,China)

The routing links by Dijkstra and Floyd algorithm may facilitate the designing，but may also cause uneven loads on the network.Considering the comprehensive performance and reduction of imbalance of the network，we add nodes to the two algorithm links.

routing algorithm; Dijkstra; Floyd algorithm

2015-10-19

冯晓东(1976-)，男，河北石家庄人，中国人民解放军总参谋部信息化部工程师.

1009-4873(2015)06-0043-03

TP393.027

A