遗传算法在智能路由中应用研究

　　摘要遗传算法之所以在路由算法中被迅速应用，关键在于它不同于传统路由算法，遗传算法是基于全局链路传播状况产生的，它的着眼点是全局的传播速度。因此，基于遗传算法路由器在实际数据传输时速度更快，网络更健康。
　　【关键词】遗传算法 延迟回答 渠道变异
　　1 引言
　　互联网的迅速发展使得有适应能力的网络路由的算法更加重要。通常通过常规矢量路由算法基于跃点计数矩阵，是早期的互联网常用的算法。这类算法把路由中的通信等待时间确被忽视了。具有适应能力的路由算法是由Munetomo，TaKao和Sato提出的。该算法以网络通信等待时间最小化为前提，在路由表中保存了常用到的通信等待时间最小的可选传播渠道，并通过路由表分配发给需要转发的数据包，以此方法来减轻网络负载。路由表是一串字符串，每个字符串代表一个单独的传播渠道。
　　2 算法介绍
　　GAR（genetic-based adaptiAe routing）算法的主要过程是：路由在加电后，开始初始化路由表。通过37pso算法中的“While终止条件不满足do”循环语句，输出那些符合设定条件的路由表条目。然后开始等待接受或输人来自用户的包。
　　首先是：如果接受到的包类型是数据包，则进行下一步判断。如果包目的地是本节点，则接受。如果是其它目的节点的则将包转发到下一路由。
　　此时如果目的路由表是空的，则采用Dijkstra算法创建缺省路由表，标号都设为“暂时”。待完善路由表后，频率记录重新设置一条缺省路由。随着网络的传输，路由表由缺省值（暂时标记），慢慢由包路由值（永久标记）替代。在路由的条目数大于设定的极限值时需要进行删除目的地使用最少的路由条目。
　　或者采用轮盘赌方式，选择从缺省路由表中选择一路由。通过在设定时间段内比较选中路由与包路由使用的渠道是否相同，来确定正式的路由条目。
　　其次是：如果接收到一个延迟请求类型的包。则记录包延迟，将包送回源点。
　　最后是：如果收到的是答复延迟类型的包，包的创建时间记录和数据包的延迟记录合成一个数据包延迟记录。基于包延迟记录的路由条目在下面状态下就需要做出相应的调整。如果随机数小于变异概率Pm，路由表中的对应某染色体就产生相应的变异操作。新产生的串会充实到路由表中。此时，如果路由表的条目数高于限值的话，权重最小的串将被删除；如果随机数小于交叉概率Pc值，路由表中的对应某染色体就产生相应的杂交操作。新产生的串会充实到路由表中。同样，如果路由表的条目数高于限值的话，权重最小的串将被删除。
　　接收到传播渠道延迟包后，遗传算法会比较同一目的地的传播渠道的权重值。路由表中的可选传播渠道就会按照遗传算法计算权值后重新形成。如果路由表的大小超过了系统设定，则进行有目的的选择操作，以减少它的大小。
　　有两类选择操作：
　　（1）局部选择：删除同一目的地的传播渠道中权重值最小的传播渠道。
　　（2）全局选择：删除在路由表中使用频率最小的目的地传播渠道。
　　3 基于遗传算法的智能路由算法
　　遗传算法路由表是在路由表中可选传播渠道经过遗传传播渠道算法产生的。基于源传播渠道的思路，GAR算法有效地利用路由表中传播渠道之间的相似之处，为源节点上的包确定了一条完整的传播渠道。数据包本身携带了传播渠道上所有节点的信息。互联网协议拥有说明源渠道是否使用源传播渠道的选择权。包通常不使用这种权利，它只要知道下一跳使用最短传播渠道即可。GAR算法产生的路由表，可以清楚地显示下一跳的传播渠道。
　　GAR（genetic-based adaptiAe routing）算法的主要特点是:
　　（1）GAR算法是源传播渠道算法，包经过的所有节点都会记录到相应的字符串中。
　　（2）包途经过一个目的节点时，都有一组可选传播渠道。
　　（3）每条备选传播渠道都有权重值。权重值的大小与被选中的概率成正比。
　　（4）基于发送延迟得到的通信等待时间，来计算传播渠道的权重值。
　　（5）初始传播渠道是使用基于跳计数准则的Dijkstra最短传播渠道算法产生的默认传播渠道。
　　（6）通过变异、杂交之类的遗传运算，路由表中产生新的可选传播渠道，而传播渠道权重值在计算后将重新安排被调用的概率。
　　（7）在路由表中，通过选择操作，相同目的地的传播渠道中权重最小的将被删除。这样就能防止路由表过大而溢出。只要路由表中有权重最小的字符串存在，于此相关的其它传播渠道都将被删除。
　　4 结论
　　基于遗传算法路由算法主要是以数据包传播延时最小化为出发点的。在网络传输时，每当一节点收到数据包后，依据路由表中相关的条目向前传递。网络节点自己产生的数据包则由该节点路由指明传播渠道。每当遇到传播渠道不明时，基于Dijkstra最短传播渠道算法产生一个临时默认的传播渠道将被启用。在路由的初始状态，路由表是空的。GAR算法仅产生那些使用频繁的传播渠道。延迟请求在指定的间隔中，发送测试包。在测试包到后，延迟回答包被回送。当测试端收到延迟回答包时，计算测试包来回的平均时间，渠道的通信等待时间就会产生了。
　　
　　参考文献
　　[1]玄光男.遗传算法与工程优化[M].北京:清华大学出版社,2004.
　　[2]刘昊旸.遗传算法研究及遗传算法工具箱开发[D].天津大学,2005.
　　[3]叶梦雄.群智能在网络路由中的研究及存在问题[J].数字技术与应用,2012.
　　
　　作者简介
　　王强(1962-)，男，河南许昌人。讲师，本科学士，主要研究方向为计算机网络、通讯。
　　孔小婧(1983-),女，本科学士，讲师，主要研究方向为计算机网络。
　　
　　作者单位
　　许昌职业技术学院河南省许昌市461000