基于蚁群算法的无线传感器网络改进CTP路由协议

陈 昊，杨光友，，马志艳，，郑 拓，全 睿

（1湖北工业大学机械工程学院，湖北 武汉430068；2湖北工业大学农业机械工程研究设计院，湖北 武汉430068）

无线传感器网络（Wireless Sensor Network，WSN）节点具有体积小、能耗低等优点，但同时又有能量有限、计算能力有限、带宽有限和易受干扰等缺点［1－2］。因此，设计节能高效的路由协议是 WSN的主要研究内容之一［3］。路由算法的路径选择机制的优劣和执行效率的高低将直接决定传感器节点负载均衡程度、采集数据和收发数据的速率，从而影响整个网络的能耗和时延。网络拓扑中路由节点的负载过重会导致节点过度能耗而死亡，影响整个网络的性能和生命周期。同时，过载节点传输队列过长，影响数据的实时传输［4］。针对上述缺点，目前国内外已有学者对路由协议改进优化。基于均衡汇聚树的路由算法LB-CTP定义节点均衡度，引入规避繁忙节点接入机制，在路由更新中，相应节点以LB-CTP路由算法选择父节点接入网络，分担繁忙节点负担，有效均衡了网络负载［5］。文献［6］在TinyOS系统中实现了基于蚁群算法的路由协议，该协议采用多跳的通信方式，能够在降低丢包率和传输时延的同时平衡节点的能量消耗，延长了网络的存活时间。上述路由协议只是单一地优化节点负载，没有同时考虑网络时延和节点间链路质量，应用到实际中仍存在一些缺陷。

本文提出了一种结合蚁群算法和CTP路由协议的路由算法——蚁群汇聚树算法（Ant Colony Algorithm Collection Tree Protocol，ACA-CTP），并在TinyOS系统中运用NesC语言实现了该算法。算法在原有CTP路由协议的基础上，将蚁群算法的控制机制加入到CTP路由协议中，通过调整信息素浓度、节点间链路质量和数据包时间延迟三者之间的关系来指引路由包进行路径搜索，算法的自适应性好，全局搜索能力和快速收敛性两者之间较为均衡。最后通过TOSSIM仿真，比较了CTP路由协议、AODV路由协议和ACA-CTP路由协议的性能。

1 ACA-CTP路由协议中的蚁群算法控制机制

1.1 改进后的蚁群算法控制机制

本文以节点间链路质量qij和传输时延tij构建启发式因子ηij，作为QoS网络路由对路径优劣的评价参数［7－8］；同时考虑到传感器节点的计算能力有限，选择概率函数从乘幂公式改为乘法公式，提高算法的计算效率。改进后的蚁群算法概率选择公式:

其中，α、β和γ分别是信息素浓度τij、时间延迟tij和链路质量qij的可调权重。蚂蚁的路径选择倾向可以通过选择不同的α、β和γ值来调节，时延越短，链路质量越好，启发式因子越大，蚂蚁选择该路径的概率就越大。同时，这3个参数对蚁群算法的全局寻优性能和快速收敛性能的影响和作用是相互配合，密切相关的，只有正确选择三者之间的搭配关系，才能避免在搜索过程中出现过早停滞或陷入局部最优等情况的发生。因此，令α、β和γ三者之间的关系如下:

改进后的蚁群算法的信息素更新机制同基本蚁群算法相同。通过合理的设置信息素更新机制中的有关参数和α、β、γ3个参数，就可以实现算法收敛速度与全局寻优性能之间的平衡［9－10］，使网络负载达到平衡，延长网络生命周期。

1.2 改进后的蚁群算法仿真

为了验证改进蚁群算法的可行性和普通性，建立随机网络拓扑结构，运用Matlab仿真工具对其进行仿真研究。仿真环境是在100m×100m的区域中随机生成200个节点，用K均值聚类算法对这些节点进行聚类，最终得到20个中心点，这20个中心点即为所需传感器节点，节点通信半径为50m。随机网络中节点的时延、链路质量和信息素浓度随机产生，其中，链路质量qij取0～1的随机数，时间延迟tij取0～25的随机数，信息素浓度τij取0～10的随机数。

运行算法后生成的网络拓扑如图1所示。

图1 网络拓扑图

从图1中可以看出，改进蚁群算法得到的网络模型节点分布均匀，过远的传感器节点之间不会形成直接的传输路径，接近现实中的网络拓扑结构。将节点1设为数据采集节点，节点20设为目的节点，算法迭代次数为20次，每次出动蚂蚁个数为100只蚂蚁，信息素浓度重要参数α＝0.4，时间延迟重要参数β＝0.4，链路质量重要参数γ＝0.2，信息素蒸发系数ρ＝0.8，信息素增强系数w＝30。

运行算法后生成的最优路径如图2所示。

图2 最优路径图

如图2中所示，运行改进蚁群算法后得到的最优传输路径为1－9－15－16－20，并且图3中的信息素浓度、时间延迟和链路质量在算法迭代到15次时收敛，说明改进后的算法是合理可行的。

图3 QoS度量参数收敛图

通过仿真测试，证明ACA-CTP算法中的蚁群算法控制机制能根据信息素浓度、时间延迟和链路质量自动选择最优路径，自适应地选择和维护节点路由，为ACA-CTP路由协议的实现奠定了理论基础。

2 ACA-CTP路由协议

2.1 ACA-CTP路由协议的实现

ACA-CTP协议在CTP协议的基础之上，以链路质量、时间延迟和信息素浓度等3个QoS参数代替CTP协议中的单一链路质量参数作为新的路由选择度量，引入蚁群算法控制机制，利用蚁群算法的路径寻优和快速收敛特性选择数据传输的最优路径［11］。

ACA-CTP路由协议的改进如图4所示。

图4 ACA-CTP路由协议框架图

2.1.1 链路质量估计器的改进 如图4所示，链路质量估计器引入时间延迟这一新的度量作为评价网络状况的参数，同时为了获得节点间传输数据包的时间延迟估计，引入FTSP时间同步算法［12］。在TinyOS操作系统中，可以直接使用定时器组件TimeSyncC提供的接口来实现FTSP算法。

2.1.2 路由引擎的改进 新的路由表在原CTP协议的路由表的基础上增加了信息素浓度、数据传输时延和节点间链路质量等3个表项，随着链路质量估计器实时地计算传输时延和链路质量而周期性地更新路由表，路由引擎将路由表中的信息传输至转发引擎。ACA-CTP协议的路由信息包格式如图5所示。

图5 ACA-CTP路由信息包

ACA-CTP路由信息包中各个字段的作用如下:P为允许路由位，占1个位，P位允许节点从其他节点请求路由信息；C为拥塞标识位，占1个位，如果节点丢弃了一个路由帧，则必须将下一个传输路由帧的C位置位；Reserved为保留位，占6个位；Parent为父节点ID，占8个位；Current为当前节点ID，占8个位，

Quality为当前节点到源节点的链路质量，占8个位，

Timedelay为当前节点到源节点的数据传输时延，占8个位；

Pheromone为当前节点的初始信息素浓度，占8个位。

在ACA-CTP路由协议的实现中，路由引擎调用UpdateRouteTask函数来更新路由表中的信息素浓度、传输时延和链路质量等表项，转发引擎就能动态选择当前节点的下一跳节点，保证数据实时准确地传输至目的节点。

2.1.3 转发引擎的改进 转发引擎将更新后的路由表中的3个QoS参数代入公式（1）中，计算当前节点的各下一跳邻居节点的路径转移概率，选取最大转移概率邻居节点作为当前节点的父节点，将ACA-CTP协议的数据包沿着最优路径传输至目标节点。同时，为了避免因信息素累积而使节点负载过大和转发引擎陷入局部最优路径，信息素根据信息素更新机制进行挥发，经过N次迭代后，信息素浓度降低，确保转发引擎选取路径是最优路径。ACA-CTP路由算法流程图如图6所示。

图6 ACA-CTP路由协议流程图

3 ACA-CTP路由协议的仿真

在TinyOS操作系统中使用TOSSIM仿真器仿真ACA-CTP路由协议。不同于传统的仿真，TOSSIM仿真器通过对实际的TinyOS程序进行编译，建立更加真实的仿真环境，对ACA-CTP路由协议的性能做更加真实的分析。

3.1 仿真环境的搭建

本文选取某农科院农业大棚环境作为仿真环境，建立TOSSIM仿真模型。由于只有配置好网络的拓扑结构，TOSSIM仿真才能模拟网络行为，故仿真刚启动时，节点之间不能互相通信。提取农业大棚环境的网络参数，使用TOSSIM自带的Java工具根据对数正态阴影路径损耗模型产生网络拓扑，需要的配置文件中的网络参数如表1所示。

表1 网络拓扑参数配置表

配置文件中的节点坐标是根据农业大棚环境现场节点部署的实际位置测定的，13个节点的坐标分布如表2所示。

表2 实验现场节点坐标分布表

运行Java工具，生成两个文件“linkgain.out”和“topology.out”。其中，“linkgain.out”文件包含了网络中任意两个节点之间的链路增益和噪声；而“topology.out”文件包含了仿真环境中节点的坐标分布。

3.2 仿真结果分析

仿真环境配置完成后，在TinyOS协议栈的应用层编写ACA-CTP路由协议的应用程序，运行TOSSIM仿真器，仿真结果如图7所示。

图7 ACA-CTP路由协议仿真图

图7 中，〈8〉号节点的转发引擎（CtpForwardingEngineP）触发发送任务（sendTask）—转发（Trying to send a packet）发送队列（Queue）中的数据包，此时发送队列中只有一个数据包（Queue size is 1），节点不处于拥塞状态；但是没有发现合理的路由路径（no route，don′t send），再次发起路由请求（start retry timer）；发现路由路径，发送数据包，发送队列为空（Queue:size is 0）；然后收到一个数据包（head＜－［负载］＜－tail），数据包进入转发队列（Queue:size is 1），广 播 路 由 帧 （head＜ － ＜ －tail）；最后仿真完成（Completed simulation）。图7可以清楚地反映ACA-CTP路由协议下数据包的传输流程，但不能直观反映路由协议的性能。因此，本文收集仿真过程中各节点的仿真信息，绘制ACACTP路由协议网络拓扑图（图8）。

图8 ACA-CTP协议网络拓扑图

分别运行原始CTP路由协议和AODV路由协议，得到网络拓扑图分别如图9和图10所示。

图9 CTP协议网络拓扑图

图10 AODV协议网络拓扑图

其中，图10为在某农科院农业大棚现场测试农业大棚无线监测系统时，上位机监控软件直接绘出的网络拓扑图。在网络拓扑中，黑色节点为汇聚节点，白色节点为路由节点，灰节点为终端节点。

由上述拓扑图可知，3种路由协议生成的网络拓扑均为树形网络。比较3个不同的网络拓扑可以看出，ACA-CTP路由协议生成的网络拓扑中第1层节点均为路由节点，其子节点数目相同，每个路由节点都拥有2个直属子节点；第2层节点中的2个路由节点均有3个终端节点作为直属子节点，因此，9号节点和25号节点的负载均为3，24号节点的负载为8，而8号节点的负载为2。同理，CTP路由协议生成的网络拓扑中，24号节点的负载为11，8号节点的负载为7，9号节点的负载为2，25号节点的负载为5。AODV路由协议生成的网络拓扑中，24号节点的负载为11，8号节点的负载为9，9号节点的负载为6，25号节点的负载为3。3种路由协议下节点负载如表3所示。

表3 三种不同协议下节点负载表

为了比较3种路由协议平衡节点负载性能的优劣，引入网络负载均衡度（Network-Load Balance Degree，NLBD）作为衡量网络负载均衡性的标准。负载均衡度的值越小，说明该树形网络的节点负载越均衡，如果负载均衡度的值为零，说明该树形网络是一颗均衡汇聚树。负载均衡度

式中:VNLBD为树形网络的负载均衡度的值；Li为节点负载的值；L为节点负载的均值；n为树形网络中路由节点个数。

分别用式（3）计算3种路由协议生成网络拓扑的网络负载均衡度，得到的结果如表4所示。

表4 三种不同路由协议的网络负载均衡度表

由表4可知，ACA-CTP路由协议的网络负载均衡度最小，其均衡节点负载的能力最强；AODV路由协议的网络负载均衡度次之，其均衡节点负载的能力适中；CTP路由协议的网络负载均衡度最大，其均衡节点负载的能力最差。

ACA-CTP路由协议生成一颗4层汇聚树，CTP路由协议生成一颗5层汇聚树，而AODV路由协议生成一颗6层汇聚树，终端节点向汇聚节点传输数据时所经过的层数越多，其累计的传输时延也越大。三种路由算法的传输时延变化趋势如图11所示。

图11 三种路由协议传输时延的比较

图11 说明ACA-CTP路由协议相比其他两种协议有更好的实时性，这是由于引入了蚁群算法机制，ACA-CTP路由协议的收敛速度比其他两种协议更快，从而能在较短时间内搜索到满足QoS约束要求的最优路径。但是随着路由协议运行时间的推移，网络的拓扑结构逐渐稳定，其传输时延也趋于稳定，3种路由协议之间传输时延的差异逐渐缩小。

收包率是衡量节点间链路质量的重要指标，图12显示了3种路由协议生成网络中收包率的变化情况。

图12 三种路由协议网络收包率比较

图12 反映出随着协议运行时间的逐渐增加，网络拓扑结构趋于稳定，网络收包率也逐渐升高，ACA-CTP协议下网络的收包率略高于其他两种协议的收包率，但三者之间的差距不大。因此，链路质量这一QoS约束在信息素浓度、传输时延和链路质量这3个参量中所占权重较小，不应作为选择最优路径时的决定性因素。

4 结束语

本文提出了基于蚁群算法和CTP路由协议相结合的路由协议ACA-CTP，并在TinyOS系统的网络层和应用层实现了该路由协议，通过TinyOS系统自带的TOSSIM仿真器验证了ACA-CTP路由协议能够较好地均衡网络中节点的负载，减少数据包的传输时延和改善节点间链路质量，为提高农业大棚监测系统的多跳数据传输性能奠定了基础。但是，本文只对ACA-CTP路由协议进行了仿真，该协议在实际应用中的性能还有待验证。

［1］ 余小华，黄灿辉.一种基于蚁群优化的 WSN拥塞控制算法［J］.计算机应用研究，2012，29（04）:1 525-1 528.

［2］ 刘拥明，蒋新华，年晓红.无线传感器网络拥塞控制研究［J］.计算机应用研究，2008，25（02）:565-568.

［3］ Gnawali O，Fonseca R，Jamieson K.Collection tree protocol［C］//Proc.Of the 7th ACM Conference on Embedded Networked Sensor Systems.Berkeley，USA:ACM Press，2009.

［4］ 鲁天龙，卢俊岭，王小明，等.TinyOS2，x下基于蚁群算法的 WSNS路由协议设计［J］.计算机应用研究，2013，30（02）:541-543.

［5］ 赵晨旭，吴怡之，韩汉光.基于 WSN均衡汇聚树的CTP路由算法改进［J］.计算机工程，2012，38（14）:62-65.

［6］ 王 鑫，徐 攀，杨慧中.基于蚁群算法的路由协议在TinyOS中的实现［J］.传感器与微系统，2012，31（05）:40-43.

［7］ 林国辉，马正新，王勇前，等.基于蚂蚁算法的拥塞规避路由算法［J］.清华大学学报（自然科学版），2003，43（01）:1-4.

［8］ 杨新峰，刘克成.基于改进蚁群算法的 WSN路径优化［J］.计算机与现代化，2012（06）:102-105.

［9］ 刘瑞杰，胡小兵.基于动态调节信息素增量的蚁群算法［J］.计算机应用研究，2012，29（01）:135-137.

［10］陈凤超，李融林.基于路由代价的无线传感器网络蚁群路由算法［J］.华南理工大学学报（自然科学版），2011，39（05）:36-43.

［11］潘 浩，董齐芬，张贵军，等.无线传感器网络操作系统TinyOS［M］.北京:清华大学出版社，2011:279-282.

［12］黄森茂.无线传感器网络能量优化策略研究及时间同步算法实现［D］.武汉:湖北工业大学，2013.