无线传感器网络中基于功率控制的蚁群路由算法*

何建强 滕志军 张 帆 刘 皎

（1.商洛学院电子信息与电气工程学院 商洛 726000）（2.东北电力大学信息工程学院 吉林 132012）

1 引言

无线传感器网络的功率控制技术主要指网络节点在无线通信过程中选择合适的功率发送分组以达到优化网络性能的目的［1]。控制节点的发射功率对提升无线传感器网络的性能具有较大意义，它既可以提升网络能量的有效性，又能增加网络并发吞吐量。目前，无线传感器网络路由节点能量的研究已取得一些成果。文献［2]中Camilo等提出了一种基于蚁群的能量有效性路由算法，即EEABR（Energy-efficient ant-based routing）路由算法，EEABR算法提升了收发蚂蚁包时的能量使用效率，即减小了发送蚂蚁包时的能量消耗，但没有考虑蚂蚁环路效应。文献［3]在EEABR算法的基础上提出一种EEABR改进算法，即EEIABR（Energy-efficient improved ant-based routing）路由算法。该算法通过在蚂蚁包中增加蚂蚁包序列号sq_num，有效削弱蚂蚁环路，同时修正信息素更新公式，将路由跳数修正为多跳消耗的能量值，并在信息素更新公式中引入节点能量与路径平均能量的偏离值，使全网节点的能量消耗更加平均，延长网络的生存周期。

本文在EEIABR路由算法的基础上，提出带有发射功率控制的PCABR算法。该算法通过提取接收hello分组的接收信号强度，并通过文献［4]中Friss公式推导出合适的发送功率级，并将该功率级存储在节点的邻居列表中。节点以概率公式选择下一跳路由发送前向蚂蚁分组时，会将综合考虑下一跳节点的剩余能量和自身的发送功率级，通过对节点发射功率级的控制，减小蚂蚁寻优过程和信息发送过程中的能量消耗，提升路径的优化程度，进一步增加网络生存周期。

2 EEIABR算法简介

EEIABR算法采用EEABR算法的蚂蚁包分类，分为Hello包和蚂蚁包两类［5]。节点通过广播Hello包来维护邻居列表，通过发送蚂蚁包来优化路径和传输信息。针对算法中容易形成环路和节点能量分布不均的缺点，在Hello包、蚂蚁包、节点邻居表中增添pkt_src（发送蚂蚁包的源地址）和sq_num（蚂蚁包序列号）的组合项，在发送蚂蚁包时，在蚂蚁包头中添加下一跳节点地址naddr以及＜pkt_src，sq_num＞。节点在广播Hello包时，除了要广播自己节点地址和能量，还应该广播路邻居列表中的＜pkt_src，sq_num＞，这样接收节点就会“知道”自己的邻居节点转发过的蚂蚁包，避免不必要的回传，改善蚂蚁的环路效应［6]。同时修正了后向蚂蚁包的信息素更新公式，并引入了能量差异因子，平衡了全网能量，提升能量分布均匀性。

3 PCABR算法的结构模型

3.1 Hello分组结构

PCABR采用与EEIABR算法相同的Hello分组结构，同样采用＜pkt_src，sq_num＞蚂蚁分组标识组合项，削弱环路效应。图1为PCABR算法的Hello分组结构图。

图1 PCABR Hello分组结构

其中，Type为分组类型，Hello_pkt_src为Hello分组的源地址，Energy为广播该Hello分组的节点的剩余能量，Phero为该条路径上的信息素浓度。

3.2 概率选择公式

PCABR算法在蚂蚁能见度函数中引入了节点发送功率作为前向蚂蚁概率选择下一跳节点的参考因子，因此其能见度函数E（s）需要重新定义，PCABR算法的概率选择式如（1）所示。能见度函数E（s）如式（2）所示。

式中T（r，s）、T（r，u）函数指蚂蚁转移路径的信息素浓度；α和β为参数，分别表征蚂蚁在概率选择过程中，信息素浓度和启发式信息的重要程度。

式中Prs为节点r向节点s的发送分组的发送功率。由已知参数可计算出节点所需要发送的最小功率值Prs。将该最小功率存储到如表1所示的邻居列表中。

表1 PCABR节点邻居列表

表 1 中，NeighbourAddr、NeighbourEng、Pheromone分别表示邻居节点地址、邻居节点能量以及该一跳路径上的信息素浓度。由于PCABR需要根据节点间距离而调节发射功率，因此，PCABR的邻居列表中需要加入＜NeighbourAddr，Pm＞的组合项，当前向蚂蚁分组从邻居列表中选取下一跳节点时，根据式（1）求出选择下一跳的概率值。

3.3 前向蚂蚁分组结构

PCABR采用与EEIABR相同的前向蚂蚁分组结构，如图2所示。

图2 前向蚂蚁包结构

其中Type为分组类型，这里标识为蚂蚁分组。Pkt_src为蚂蚁分组的源地址，Daddr为蚂蚁分组下一跳地址，由式（1）得出。Saddr为蚂蚁分组上一跳的节点地址。Energy_sum为前向蚂蚁分组到达当前节点时，所有访问过的节点的剩余能量总和。Energy_min为前向蚂蚁分组到达当前节点时，所有访问过的剩余能量最小节点的能量值。toSintNode为布尔型变量，表明蚂蚁分组方向。hops为蚂蚁经过的节点数。

3.4 信息素更新公式

当前向蚂蚁分组到达Sink节点时，需要转化成后向蚂蚁分组，沿原路径返回，再返回之前，需要由Sink节点根据前向蚂蚁分组携带的路径信息，即前向蚂蚁分组的中携带的信息计算该路径上的信息更新量。PCABR信息素更新公式如式（3）、（4）、（5）所示。

式（3）所示为节点r到节点s路径上的的信息素更新规则，其中ρ为信息素蒸发系数，防止信息素浓度的无限制累积。ΔTk为后向蚂蚁k携带的更新该条路径的信息素增量。由式（4）所示。

其中EAvgk为前向蚂蚁分组k访问过节点的平均剩余能量，如式（5）所示。

Energy_sum为前向路径上剩余能量的总和，Fdk为访问过的节点数，由图1中的hops得出。

从PCABR算法的信息素更新公式中可以得出，剩余能量较大，路由跳数较少，能量分布较为平均的路径信息素增加较多，后续蚂蚁分组选择该条路径的概率增大。

3.5 后向蚂蚁分组结构

PCABR后向蚂蚁分组负责更新前向路径上的信息素浓度，后向蚂蚁分组结构如图3所示。

图3 后向蚂蚁分组结构

其中Type为分组类型，Pkt_src为后向蚂蚁分组的最终目的地址，Daddr为后向蚂蚁分组下一跳地址，Saddr为后向蚂蚁上一跳的节点地址。Pheromone为信息素增量，toSinkNode为布尔型变量，与前向蚂蚁分组相对应，定义为false，Energy_avg为该条路径上的平均能量。

4 PCABR路由算法流程

4.1 Hello分组收发流程

如图4所示节点周期性的发送Hello分组与邻节点建立联系，节点在收到Hello分组后更新自己的邻居节点列表。与EEIABR算法不同之处在于，接收节点除了提取Hello信息中的邻节点地址，邻节点剩余能量和该一跳路径的信息素之外，还需要提取RSSI，得出发送给该跳节点的最优发射功率，存储在相应的邻居列表当中。

图4 PCABR Hello分组收发流程

4.2 PCABR蚂蚁分组收发流程图

如图5所示，节点每隔一段时间发送前向蚂蚁分组寻找通往Sink节点的路径。首先源节点查询邻居列表是否存在Sink节点，若存在则直接向Sink节点发送前向蚂蚁分组；若不存，则按式（1）概率选择下一跳分组转发节点。

当Sink节点收到前向蚂蚁分组之后，随即生成后向蚂蚁分组，按原路径返回至源节点并更新路径上信息素。首先，Sink节点查询邻居列表是否存在源节点，若存在则直接向源节点发送后向蚂蚁分组，若不存在则需要根据当前节点的路由表按原路径转发后向蚂蚁分组，并通过式（3）更新该跳路径上的信息素浓度。如此循环，直到源节点收到后向蚂蚁分组，该轮蚂蚁收发结束。

图5 PCABR蚂蚁分组收发流程

5 实验仿真及结果对比

为了验证PCABR、EEIABR和EEABR算法在多节点无线传感器网络中能量使用效率和能量均衡性上的优劣程度。通过Vmware9.0虚拟机下Ubuntu10.04+NS2.35平台对上述三种算法进行仿真。移动场景参数表如表2所示。CBR数据流参数表如表3所示。传感器节点参数如表4所示。

表2 移动场景参数表

表3 CBR数据流参数表

表4 传感器节点参数

除此之外，设定三种算法的节点的初始发送功率（txPower）为 0.6W，初始接收功率（rxPower）为0.3W，空闲能量消耗（idlePower）为0.06W，仿真时间为100s［7]。图6为节点平均剩余能量随节点数目变化，图7为节点最小剩余能量随节点数目变化。

图6 节点剩余能量随节点数目变化

如图6与图7所示，随着节点的不断增加，PCABR算法通过动态调整发射分组的功率，在节点平均剩余能量和节点最小剩余能量均优于EEABR和EEIABR算法［8]，表明PCABR算法在多节点的无线传感器网络对能量的使用效率的提升较为明显。

图7 节点最小剩余能量随节点数目变化

为了进一步验证PCABR算法在多节点时的能量均衡性，保持100*100m2不变，节点数目为65个，仿真时间为50s～100s［9]。图8为节点平均剩余能量随时间变化曲线，图9为节点最小剩余能量随时间变化曲线。

如图8与图9所示，在节点数目为65个时，随着时间的不断增加，PCABR算法在能量使用效率和能量均衡性方面相较于EEABR算法和EEIABR算法均有一定的提升。

图8 节点平均剩余能量随时间变化

图9 节点最小剩余能量随时间变化

6 结语

本文以EEIABR算法为基础，提出一种基于功率控制的蚁群路由算法PCABR。该算法通过提取邻节点Hello分组的接收信号强度，推导出对邻节点的最优功率级，达到对节点发送端功率控制的目的［10]。同时，PCABR对EEIABR算法的邻居节点列表，概率选择公式，信息素更新公式作进一步改进，使路径信息素更新更为准确，提高蚂蚁的搜索效率，仿真表明PCABR算法相较于EEIABR和EEABR算法在能量使用效率和网络节点均衡性方面均有一定的提升，更适用于节点数目较多的无线传感器网络。