基于蚁群算法的网络路由最优路径判断模块设计与实现
徐虹+杨雅志+赵明
摘 要： 网络中节点的能量是有限的，网络拓扑结构具有波动性，导致传统网络路由算法不能有效适应这些变化，自组织性较差，无法及时获取最优路径，大大降低网络性能。因此，设计基于蚁群算法的网络路由最优路径判断模块。其以FPGA为控制核心实现硬件设计，具体包括控制模块、存储器模块、寻求后续节点集模块、采集后续节点模块、状态调整模块、信息素调整模块和最优路径判断模块。模块实现部分给出了蚁群算法的核心代码。实验结果表明，所设计的最优路径判断模块具有较高的收敛速率，获取的路径更短，能够延长网络的运行周期。
关键词： 蚁群算法； 网络路由； 最优路径； FPGA
中图分类号： TN711?34； TP393 文献标识码： A 文章编号： 1004?373X（2017）04?0036?03
Design and implementation of optimal path judgment module based on ant colony algorithm for network routing
XU Hong， YANG Yazhi， ZHAO Ming
（Department of Information and Computing Science， Chengdu Technological University， Chengdu 611730， China）
Abstract： Since energy in the network node is limited， and the network topology has volatility， which cause that the traditional network routing algorithm can not effectively adapt to these changes， the self?organizing is poor， the optimal path can not be got timely， and the network performance is reduced greatly， the optimal path judgment module based on ant colony algorithm for network routing is designed. The FPGA as the control core is used to realize the hardware design， including the control module， memory module， subsequent nodes set seeking module， subsequent node acquisition module， state adjustment module， information adjustment module， optimal path judgment module and multiplex selection module. The core code of ant colony algorithm is presented in the process of module implementation. The experimental result shows that the designed optimal path judgment module has high?speed convergence and shorter access path， and can lengthen the operation cycle of the network.
Keywords： ant colony algorithm； network routing； optimal path； FPGA
无线传感器网络（WSN）通常是由传感器节点构成的自组织网络，在军事、医疗、工业等领域应用广泛。WSN路由算法是寻求数据从源节点到目标节点间进行通信的最优路径[1?3]。但是因为WSN网络中节点的能量有限，网络拓扑结构具有波动性，导致傳统网络路由算法不能有效适应这些变化，自组织性较差，无法及时获取最优路径，大大降低网络性能。因此，寻求一种有效的网络路由最优路径判断方法，具有重要应用意义[4?6]。
1 网络路由最优路径判断模块设计与实现
1.1 系统总体设计
该系统塑造了基于蚁群算法的网络路由最优路径判断模块，其以现场可编辑门阵列（Field?Programmable Gate Array，FPGA）为控制核心实现硬件设计，其总体结构如图1所示。其包括控制模块、存储器模块、寻求后续节点集模块、采集后续节点模块、状态调整模块、信息素调整模块和最优路径判断模块。
1.2 存储器模块的设计
存储器模块采用Xilinx公司的IP Generator，IP Generator生成的RAM存储器的结构示意图如图2所示。融合6个带有端口ENA和读/写控制信号WEA 控制的RAM存储器。网络节点间的聚类信息采用位宽是5，深度是256的RAM存储器保存；最佳路径位宽为16，深度为 32的 RAM存储器保存；其他能量采用位宽为8，深度是16的RAM存储器保存。
1.3 后续节点选择模块设计
蚂蚁的后续节点选择模块的原理结构图如图3所示。其中的参数delay，cost以及tau分别用于描述延时邻接矩阵存储单元、费用邻接矩阵存储单元以及信息素存储单元；m1，m2以及a1分别用于描述乘法器以及加法器；pp（i）以及pcum（i）用于描述一个1*8—维数组；reg1，reg2以及reg3是三个寄存器。
蚂蚁后续节点选择的过程为：采用蚂蚁转移概率运输模块，对pp（i）以及pcum（i）等参数进行原始设置，采集w到各可选节点间的路径费用、延时以及信息素等参数，再将路径费用和延时参数取倒数后同信息素融合后反馈到乘法器m1中，将获取的结果保存到pp（i）内，该过程如下：
（1）
式中：；表示可选节点集中的节点，表示w到的信息素参数，表示w到的费用参数，表示w到的延时参数。将预算内完的采用寄存器reg1逐次存储到累加器a1中，并将最终的结果保存到内，则有：
（2）
通过reg2输出的累加获取sum：
（3）
对进行累加后，将sum同随机数融入乘法器m2中，获取sum_r，再将其保存到寄存器reg3内。若k>sum_r，则终止相应的对比，记录下参数i，此时获取的n_w为。
1.4 状态调整模块的设计
蚂蚁状态调整模块的原理结构图如图4所示，蚂蚁状态调整状态机如图5所示。
Scenario ka ：ka表示复位，当res为低电平，系统进入Scenario ka，对相关信号进行清除和检测。
Scenario ce1：对蚂蚁路径path进行调整，一个时钟周期后进入ce2。
Scenario ce2：采用cost以及delay获取蚂蚁要运行所需的延时和费用等参数，再将这些参数反馈到加法器a1，a2内，并在禁忌列表中将蚂蚁要运行的后续节点标识成零，再进入Scenario ce3。
Scenario ce3 ：将Scenario ce2内形成的相关参数存储到taus，costs以及delays中，将w变成n_w，并输出蚂蚁状态参数的调整结果，进入Scenario ka。
1.5 最优路径选择模块设计
最优路径的选择模块的原理结构图如图6所示，具体的运行过程如下：
Scenario ka：进行复位处理，若ceart为高电平，则进入Scenario ce1。
Scenario ce1：对蚂蚁扫描节点的费用和延时两个参数进行求和，并进入Scenario ce2。
Scenario ce2 ：如果蚂蚁没有达到目标节点，则将费用和延时参数都标识成inf（inf=0xFF），如果costkm<inf且delaykm <=""
Scenario ce3：将Scenario ce2中获取的目标节点参数保存到数组path中，一个时钟后进入Scenario ce4。
Scenario ce4：运算path内的相关数据获取跳数ts，一个时钟周期后进入。
Scenario ce5：逐次采集路径path中的当前节点以及后续节点参数x以及y。
Scenario ce6：系统按照ts判断各路径是否被扫描完，如果是，则进入Scenario ce7；否则进入Scenario ce5。
Scenario ce7：采集cost内完成扫描路径的费用，并将其保存到相应的数组中，并对数组右上角的数据进行汇总，获取各路径的总费用，再进入Scenario ce77。
Scenario ce77：将最佳路径的总费用存储到寄存器tcsum中，一个时钟周期后进入Scenario ce9。
Scenario ce8：从tcsum内采集出全部的数据，并且同最优路径花费对比，如果数据低于目前的最优花费，则将其采集出，同时替换掉当前的数据保存到ram中，否则进入替换处理过程，再进入Scenario ce9。
Scenario ce9：如果全部蚂蚁都完成路径的选择，则进入ceop，说明完成网络路由最优路径的选择，否则进入Scenario ce1。
2 实验分析
通过实验验证本文设计的基于蚁群算法的网络路由最优路径判断模块的性能。实验分别从平均跳数、网络能耗以及路径长度三个指标评估本文方法和基于查询驱动的路由方法的性能优劣。
2.1 平均跳数比较分析
本文方法和基本查询驱动的路由方法的平均跳数对比图，如图7所示。能够看出，随着迭代次数的逐渐增加，两种方法的平均跳数都不断降低。本文方法的平均跳数在第55次迭代时收敛到8跳，而基于查询驱动的路由方法仅收敛到13跳。说明相对于基于查询驱动的路由方法，使用本文方法传递数据对网络资源的占用率更少，对网络带宽的消耗更低，可降低网络的拥塞率，提高网络数据的传输效率，本文方法的效率更高。
2.2 网络能耗对比分析
两种方法的网络能耗情况如图8所示。从中能够看出，随着迭代次数的逐渐增加，各次迭代网络消耗的总能量都降低。
在无线传感网络实验时，若采用基于查询驱动的路由方法，其单次迭代总能量消耗是0.348 J，而采用本文方法的单次迭代消耗的总能量是0.213 J，大大降低了网络能耗量。并且本文方法在20次迭代就完成收敛，而查询驱动方法需要在75次迭代后才可实现收敛。说明本文方法具有较高的收敛性，采用本文方法的无线传感网络的网络能耗更低。
3 结 论
本文设计基于蚁群算法的网络路由最优路径判断模块。其以FPGA 为控制核心实现硬件设计，具体包括控制模块、存储器模块、寻求后续节点集模块、采集后续节点模块、状态调整模块、信息素调整模块和最优路径判断模块。模块实现部分给出了蚁群算法的核心代码。实验结果表明，所设计的最优路径判断模块具有较高的收敛速率，获取的路径更短，能够延长网络的运行周期。
参考文献
[1] 宋立新，戴赫.基于蚁群算法的WSN路由协议研究[J].哈尔滨理工大学学报，2014，19（6）：88?92.
[2] 张双双，王延年.节点分布不均匀的无线传感网络低功耗算法[J].西安工程大学学报，2015，29（6）：720?723.
[3] 馬学森，曹政，韩江洪，等.改进蚁群算法的无线传感器网络路由优化与路径恢复算法[J].电子测量与仪器学报，2015，29（9）：1320?1327.
[4] 戴天虹，李昊.基于改进蚁群算法的无线传感器网络路由的优化[J].计算机测量与控制，2016，24（2）：321?324.
[5] 王洪元，刘志远，卜莹.基于蚁群优化算法的无线传感器网络跨层路由协议[J].常州大学学报（自然科学版），2014，26（2）：32?37.
[6] 王志勃，毕艳茹.基于Sarsa算法和蚁群优化的监测网络路由控制设计[J].计算机测量与控制，2014，22（10）：3327?3329.
摘 要： 网络中节点的能量是有限的，网络拓扑结构具有波动性，导致传统网络路由算法不能有效适应这些变化，自组织性较差，无法及时获取最优路径，大大降低网络性能。因此，设计基于蚁群算法的网络路由最优路径判断模块。其以FPGA为控制核心实现硬件设计，具体包括控制模块、存储器模块、寻求后续节点集模块、采集后续节点模块、状态调整模块、信息素调整模块和最优路径判断模块。模块实现部分给出了蚁群算法的核心代码。实验结果表明，所设计的最优路径判断模块具有较高的收敛速率，获取的路径更短，能够延长网络的运行周期。
关键词： 蚁群算法； 网络路由； 最优路径； FPGA
中图分类号： TN711?34； TP393 文献标识码： A 文章编号： 1004?373X（2017）04?0036?03
Design and implementation of optimal path judgment module based on ant colony algorithm for network routing
XU Hong， YANG Yazhi， ZHAO Ming
（Department of Information and Computing Science， Chengdu Technological University， Chengdu 611730， China）
Abstract： Since energy in the network node is limited， and the network topology has volatility， which cause that the traditional network routing algorithm can not effectively adapt to these changes， the self?organizing is poor， the optimal path can not be got timely， and the network performance is reduced greatly， the optimal path judgment module based on ant colony algorithm for network routing is designed. The FPGA as the control core is used to realize the hardware design， including the control module， memory module， subsequent nodes set seeking module， subsequent node acquisition module， state adjustment module， information adjustment module， optimal path judgment module and multiplex selection module. The core code of ant colony algorithm is presented in the process of module implementation. The experimental result shows that the designed optimal path judgment module has high?speed convergence and shorter access path， and can lengthen the operation cycle of the network.
Keywords： ant colony algorithm； network routing； optimal path； FPGA
无线传感器网络（WSN）通常是由传感器节点构成的自组织网络，在军事、医疗、工业等领域应用广泛。WSN路由算法是寻求数据从源节点到目标节点间进行通信的最优路径[1?3]。但是因为WSN网络中节点的能量有限，网络拓扑结构具有波动性，导致傳统网络路由算法不能有效适应这些变化，自组织性较差，无法及时获取最优路径，大大降低网络性能。因此，寻求一种有效的网络路由最优路径判断方法，具有重要应用意义[4?6]。
1 网络路由最优路径判断模块设计与实现
1.1 系统总体设计
该系统塑造了基于蚁群算法的网络路由最优路径判断模块，其以现场可编辑门阵列（Field?Programmable Gate Array，FPGA）为控制核心实现硬件设计，其总体结构如图1所示。其包括控制模块、存储器模块、寻求后续节点集模块、采集后续节点模块、状态调整模块、信息素调整模块和最优路径判断模块。
1.2 存储器模块的设计
存储器模块采用Xilinx公司的IP Generator，IP Generator生成的RAM存储器的结构示意图如图2所示。融合6个带有端口ENA和读/写控制信号WEA 控制的RAM存储器。网络节点间的聚类信息采用位宽是5，深度是256的RAM存储器保存；最佳路径位宽为16，深度为 32的 RAM存储器保存；其他能量采用位宽为8，深度是16的RAM存储器保存。
1.3 后续节点选择模块设计
蚂蚁的后续节点选择模块的原理结构图如图3所示。其中的参数delay，cost以及tau分别用于描述延时邻接矩阵存储单元、费用邻接矩阵存储单元以及信息素存储单元；m1，m2以及a1分别用于描述乘法器以及加法器；pp（i）以及pcum（i）用于描述一个1*8—维数组；reg1，reg2以及reg3是三个寄存器。
蚂蚁后续节点选择的过程为：采用蚂蚁转移概率运输模块，对pp（i）以及pcum（i）等参数进行原始设置，采集w到各可选节点间的路径费用、延时以及信息素等参数，再将路径费用和延时参数取倒数后同信息素融合后反馈到乘法器m1中，将获取的结果保存到pp（i）内，该过程如下：
（1）
式中：；表示可选节点集中的节点，表示w到的信息素参数，表示w到的费用参数，表示w到的延时参数。将预算内完的采用寄存器reg1逐次存储到累加器a1中，并将最终的结果保存到内，则有：
（2）
通过reg2输出的累加获取sum：
（3）
对进行累加后，将sum同随机数融入乘法器m2中，获取sum_r，再将其保存到寄存器reg3内。若k>sum_r，则终止相应的对比，记录下参数i，此时获取的n_w为。
1.4 状态调整模块的设计
蚂蚁状态调整模块的原理结构图如图4所示，蚂蚁状态调整状态机如图5所示。
Scenario ka ：ka表示复位，当res为低电平，系统进入Scenario ka，对相关信号进行清除和检测。
Scenario ce1：对蚂蚁路径path进行调整，一个时钟周期后进入ce2。
Scenario ce2：采用cost以及delay获取蚂蚁要运行所需的延时和费用等参数，再将这些参数反馈到加法器a1，a2内，并在禁忌列表中将蚂蚁要运行的后续节点标识成零，再进入Scenario ce3。
Scenario ce3 ：将Scenario ce2内形成的相关参数存储到taus，costs以及delays中，将w变成n_w，并输出蚂蚁状态参数的调整结果，进入Scenario ka。
1.5 最优路径选择模块设计
最优路径的选择模块的原理结构图如图6所示，具体的运行过程如下：
Scenario ka：进行复位处理，若ceart为高电平，则进入Scenario ce1。
Scenario ce1：对蚂蚁扫描节点的费用和延时两个参数进行求和，并进入Scenario ce2。
Scenario ce2 ：如果蚂蚁没有达到目标节点，则将费用和延时参数都标识成inf（inf=0xFF），如果costkm<inf且delaykm <=""
Scenario ce3：将Scenario ce2中获取的目标节点参数保存到数组path中，一个时钟后进入Scenario ce4。
Scenario ce4：运算path内的相关数据获取跳数ts，一个时钟周期后进入。
Scenario ce5：逐次采集路径path中的当前节点以及后续节点参数x以及y。
Scenario ce6：系统按照ts判断各路径是否被扫描完，如果是，则进入Scenario ce7；否则进入Scenario ce5。
Scenario ce7：采集cost内完成扫描路径的费用，并将其保存到相应的数组中，并对数组右上角的数据进行汇总，获取各路径的总费用，再进入Scenario ce77。
Scenario ce77：将最佳路径的总费用存储到寄存器tcsum中，一个时钟周期后进入Scenario ce9。
Scenario ce8：从tcsum内采集出全部的数据，并且同最优路径花费对比，如果数据低于目前的最优花费，则将其采集出，同时替换掉当前的数据保存到ram中，否则进入替换处理过程，再进入Scenario ce9。
Scenario ce9：如果全部蚂蚁都完成路径的选择，则进入ceop，说明完成网络路由最优路径的选择，否则进入Scenario ce1。
2 实验分析
通过实验验证本文设计的基于蚁群算法的网络路由最优路径判断模块的性能。实验分别从平均跳数、网络能耗以及路径长度三个指标评估本文方法和基于查询驱动的路由方法的性能优劣。
2.1 平均跳数比较分析
本文方法和基本查询驱动的路由方法的平均跳数对比图，如图7所示。能够看出，随着迭代次数的逐渐增加，两种方法的平均跳数都不断降低。本文方法的平均跳数在第55次迭代时收敛到8跳，而基于查询驱动的路由方法仅收敛到13跳。说明相对于基于查询驱动的路由方法，使用本文方法传递数据对网络资源的占用率更少，对网络带宽的消耗更低，可降低网络的拥塞率，提高网络数据的传输效率，本文方法的效率更高。
2.2 网络能耗对比分析
两种方法的网络能耗情况如图8所示。从中能够看出，随着迭代次数的逐渐增加，各次迭代网络消耗的总能量都降低。
在无线传感网络实验时，若采用基于查询驱动的路由方法，其单次迭代总能量消耗是0.348 J，而采用本文方法的单次迭代消耗的总能量是0.213 J，大大降低了网络能耗量。并且本文方法在20次迭代就完成收敛，而查询驱动方法需要在75次迭代后才可实现收敛。说明本文方法具有较高的收敛性，采用本文方法的无线传感网络的网络能耗更低。
3 结 论
本文设计基于蚁群算法的网络路由最优路径判断模块。其以FPGA 为控制核心实现硬件设计，具体包括控制模块、存储器模块、寻求后续节点集模块、采集后续节点模块、状态调整模块、信息素调整模块和最优路径判断模块。模块实现部分给出了蚁群算法的核心代码。实验结果表明，所设计的最优路径判断模块具有较高的收敛速率，获取的路径更短，能够延长网络的运行周期。
参考文献
[1] 宋立新，戴赫.基于蚁群算法的WSN路由协议研究[J].哈尔滨理工大学学报，2014，19（6）：88?92.
[2] 张双双，王延年.节点分布不均匀的无线传感网络低功耗算法[J].西安工程大学学报，2015，29（6）：720?723.
[3] 馬学森，曹政，韩江洪，等.改进蚁群算法的无线传感器网络路由优化与路径恢复算法[J].电子测量与仪器学报，2015，29（9）：1320?1327.
[4] 戴天虹，李昊.基于改进蚁群算法的无线传感器网络路由的优化[J].计算机测量与控制，2016，24（2）：321?324.
[5] 王洪元，刘志远，卜莹.基于蚁群优化算法的无线传感器网络跨层路由协议[J].常州大学学报（自然科学版），2014，26（2）：32?37.
[6] 王志勃，毕艳茹.基于Sarsa算法和蚁群优化的监测网络路由控制设计[J].计算机测量与控制，2014，22（10）：3327?3329.
