基于TSP的蚁群算法在路由协议中的应用.pptx

1、基于 TSP 蚁群算法的网络路由协议优化设计方法,张政 2017/4/25,1. 路由协议概述,路由协议是运行于网络层的信息转发策略，性能优越的路由协议能够使消息的传递过程更加顺畅，使通信客户端可以通过最优的路径将信息传递给其它客户端，有效提升了网络的整体性能。无线通信协议的路径选择示意如下图 所示 。,2. TSP 蚁群算法模型,定义类似 TSP ，设 是一个节点的集合 ， 是集合 C中元素两两连接的集合 ， 是 的距离 ，如式（） ， 其中 ， 、 、 、 分别表为元素节点的坐标 。 定义G （C ，L）表示某个有向图。 为模拟蚂蚁的实际行为，首先引进如下记号 ：设 表示 t时刻位于元素

2、i 的蚂蚁的数目；n表示 TSP 规模，m为蚁群中蚂蚁的数目，d为节点 i 、j 间的距离 ， 则有 ：,为蚂蚁 k 走过的路程 ， 用一张禁忌表 （k ， ， ，m）记录蚂蚁 k 当前所走过的节点元素 ，集合随着 的进化过程作动态调整 。 是t时刻集合 C 中元素两两连接 上残留信息素的集合； 为 t时刻路径 （i ，j）上残留信息素数量 ， 在初始时刻各条路径上信息素浓度相等 ， 并设 C （ C 为某个正常数）， 基本蚁群算法的寻优是通过有向图 g （C ，L ，） 实现的，主要集中表现为路径选择策略以及信息素调节策略。,3.路径选择机制,蚁群算法中放置的人工蚂蚁处于离散状态中，蚂蚁根据

3、不同节点信息素浓度选择下一个需要访问的节点。蚂蚁通过随机策略完成整个游程， 整个游程的过程意味着所求问题的某个可行答案。 将 m只蚂蚁随机放在 n个节点上，然后在每个节点上循环利用某个特定的状态转移规则。蚂蚁在节点 i 与另一个没有经过的节点 j 间的运动运行随机转移策略 ， 该策略以节点 i 、j 之间路径上存在的信息素含量 以及节点间的距离为依据 。 表示 t时刻蚂蚁 k 由节点 i 转移到节点 j 的状态转移概率 ：,4. 信息素调节机制,为了避免残留信息素过多引起残留信息淹没启发信息，在每只蚂蚁走完一步或者完成对所有 n 个节点的遍历，即一个循环结束后，要对残留信息进行更新处理。使用

4、AntCycle 模型，其利用的是系统全局信息 ， 此信息更新策略能够使较短路径上对应的信息素逐步增大 ， 保证了算法中整体范围下较短路径的生存能力 ， 提升了信息正反馈性能 ，加快了系统搜索路径的效率 。 Q为常数，表示蚂蚁寻找路径过程中所释放信息素总量 ， 它在一定程度上影响算法的收敛速度。 代表本次循环中第 k只蚂蚁在路径 （i ，j）,上释放的信息素量 。,5.路由协议设计与实现,针对求解 TSP 问题的蚁群算法模型，对此模型进行修改，同时结合无线自组织网络信息传输的特点，完成基于蚁群算法的路由协议设计。 Step ： 初始化各通信节点间的距离。此操作通过节点广播信息完成，每个节点被分

5、配不同的 ID，作为其在此过程中的唯一标识，广播的数据帧格式如图所示，包括节点 ID 属性，当前位置坐标 （x ，y）， 是否为源节点或目的节点，如果有数据发送需求，源节点属性值赋值为 1，同时将目的节点的 ID 进行赋值 ，并对发送序列进行编号，如果没有数据发送需求，则置为 。,Step ： 将若干蚂蚁放在不同的通信节点中，每个通信节点维护自身的信息素列表 ，表中描述了当前节点的信息素含量和此刻与其它节点间的距离。信息列表的具体信息如图 所示。当节点位置移动后，此表中的数据也进行更新 。,Step ： 每只蚂蚁根据各节点至目的节点的距离 d 和信息素平 ， 选择下一通信节点，同时修改禁忌表。 Step ： 所有蚂蚁完成周游后，更新信息列表中的信息素水平和节点位置信息 。 Step ： 返回 St