2. 北京电子科技学院 密码科学与技术系, 北京 100070;
3. 吉林大学 通信工程学院, 吉林 长春 130012
无线传感器网络(wireless sensor network, WSN)是一系列具有通信、计算和感知的传感器节点所组成的无线网络, 可以在特定条件下为用户提供数据的收集、计算和传输。在实际的应用中, WSN中的节点在工作时, 主要依靠自身电池提供有限的能量, 不合理的网络开销会导致节点过早死亡。因此在选取节点之间通信最优路径的同时, 如何降低网络开销, 延长网络生命周期成为近年来研究WSN性能的重要内容。
蚁群算法是由Dorigo等[1]提出的仿生寻优算法, 该算法具有正反馈和较强的鲁棒性等特点, 在解决路径规划问题时效果较好。基于该算法的蚁群路由算法被提出后, 引发各方学者的广泛关注。
文献[2]利用模糊逻辑选择信道, 根据节点的剩余能量与到基站的距离将网络划分成不相等的簇, 预先粗略筛选下一跳节点, 从而在算法收敛速度上有一定优势, 但因为模糊逻辑的不确定性, 容易使算法陷入局部最优。文献[3]在选择簇头时, 利用EPO算法查找簇头到汇聚节点间的最优路径。文献[4]将部署节点的区域划分为不同层级, 根据博弈论模型选择簇头, 该算法有效提高网络生命周期, 但寻优效果不理想。文献[5]通过邻居节点提供到达目的节点需要的网络开销的预估值, 递增地计算出到达目的节点所需的所有路由成本, 最终筛选出最优解。文献[6]利用分段更新规则优化信息素更新公式, 但从全局的角度来看容易使网络陷入局部最优。
文献[7]将蚁群算法与鲸鱼算法相结合, 将具有最大适应度值的路径作为最优路径。文献[8]利用数据聚合来提高节点能量利用率, 通过评估节点剩余能量与汇聚节点的位置来确定最佳路由。文献[9]将蚁群划分为引导层蚂蚁和普通层蚂蚁, 在设计上加强引导层蚂蚁对汇聚节点的吸引力, 充分发挥了不同层蚂蚁在搜索过程中的协作优势, 避免陷入局部最优解。文献[10]将群集和多跳路由技术相结合, 同时利用动态选取法引入休眠节点，从而平衡网络中节点能量, 提高网络生命周期时间。文献[11]利用双子蚁群沿预定方向进行联合搜索, 提高算法搜索效率, 但网络生命周期较短。
综上所述, 现有蚁群路由算法及其优化算法在大型光伏发电系统状态监控中存在容易陷入局部最优、网络生命周期较短等问题。针对这些实际问题, 本文提出了一种基于自适应剩余能量阈值的WSN蚁群路由算法(an adaptive threshold of remaining energy based ant colony routing algorithm, ATRE-ARA)。通过优化自适应阈值、设置信息素上限和下限, 提高信息素的准确性, 平衡算法的局部和全局搜索能力。同时改进信息素启发函数, 引入搜索角和下一跳节点距离, 避免数据在节点间发生回旋, 提高算法寻优效率, 减少节点网络开销, 延长网络生命周期。
1 系统模型 1.1 数学模型本文将WSN描述为一个无向加权图G, 如(1)式所示。
|
(1) |
其中顶点V表示为网络中所有节点的集合, 如(2)式所示。
|
(2) |
E为节点间所有链路的集合, 如(3)式所示。
|
(3) |
假设d(r, s)表示节点r到节点s的距离, R为节点间有效通信距离, 且节点r和节点s之间的链路为ers, 分别由公式(4)和(5)表示。
|
(4) |
|
(5) |
C为WSN中所有可能存在链路的节点集合, 如(6)式所示。
|
(6) |
确定在网络中任意两节点之间是否存在有效链路, 可以用公式(7)表示。
|
(7) |
节点r和节点s存在有效链路时, 表示为1, 否则为0。假设网络中有且仅有1个汇聚节点z, z ∈V。W为网络中源节点的集合, 如公式(8)所示。
|
(8) |
在WSN中, 除汇聚节点外, 其余网络中各节点的初始能量为有限值。在节点发送和接收数据时都会损耗自身能量。本文采用的无线电能耗模型[12]如图 1所示。
|
| 图 1 无线电能耗模型 |
当节点发射数据包a时, 能量损耗发生在信号发射和信号放大2个阶段。信号发射阶段的能耗由数据包a的大小决定, 信号放大阶段的能耗主要由发射器和接收器之间的距离d(r, s)决定。
接收器在接收数据时的能量损耗由数据包a的大小决定。Etx(a)r为发射器发射能量消耗值, Erx(a)s为接收器接收能量消耗值, 具体能量损耗如公式(9)~(10)所示。
|
(9) |
|
(10) |
Eelec为每传输1 bit数据所消耗的能量, Eεfs和Eεamp分别代表数据包a在自由空间模型与多径衰减模型中发射1 bit数据功放所消耗的能量。d0为d(r, s)的距离阈值, 如(11)式所示。通过公式可知, 发射器发射能量消耗值Etx(a)r随距离d(r, s)变大而增加。计算(9)式中Etx(a)r的值时, 当d(r, s) < d0, 选择自由空间模型, 当d(r, s)≥d0, 选择多路径衰减模型。
|
(11) |
由于传统的蚁群路由算法存在局部节点能量开销较大和数据在节点间返复回旋等问题, 导致网络生命周期较短和算法容易陷入局部最优。针对以上问题, 本文在现有蚁群路由算法的基础上, 提出改进的蚁群路由算法, 通过改进信息素更新公式, 引入自适应阈值和搜索角, 设置信息素上限值和下限值, 可以有效降低数据在节点间的回旋, 提高全局寻优能力, 平衡全局网络能耗, 延长网络生命周期。
2.1 改进信息素更新策略算法每次迭代后, 路径上的信息素值都会更新, 传统的蚁群算法在更新信息素时没有对信息素值进行限制。在算法初期, 容易出现因局部路径信息素值过大或过小, 而导致陷入局部最优解。本文通过改进已有信息素公式, 设置信息素上限值Tmax和信息素下限值Tmin, 提高选择其他路径的概率。防止在算法迭代初期, 因局部路径信息素差值过大, 陷入局部最优, 增加了算法搜索全局最优的能力。改进的信息素公式如(12)式所示。
|
(12) |
|
(13) |
Ta(r, s)为蚂蚁a储存在节点r和节点s路径上的信息素浓度值或信息素值, 信息素浓度存储在邻居列表中。ΔTa(r, s)为蚂蚁a留在节点r和节点s之间的信息素增量, δ为自适应信息素蒸发系数, 如(13)式所示。n为节点路由数, ρ为基本蚁群算法中的信息素蒸发系数, ρ ∈ (0, 1)。路由数n的大小与自适应信息素蒸发系数δ正相关。
2.2 改进信息素增量公式基本蚁群算法在计算信息素增量ΔTa(r, s)时, 利用数据包a途径距离的长度作为衡量信息素增量的标准, 即
|
(14) |
式中：Ma为蚂蚁a经过所有节点的集合；La为数据包a途经路径长度, Q为常量。当La值越大时, ΔTa(r, s)值越小, 路径上的信息素Ta(r, s)越小, 从而影响数据包a选择下一跳节点s的概率。传统的蚁群算法在计算信息素增量时, 没有考量节点剩余能量, 容易造成局部节点网络开销过大, 导致节点过早死亡, 影响网络生命周期。
为进一步提高ΔTa(r, s)的准确性, 本文在基础蚁群算法的基础上, 引入下一跳节点剩余能量Es及其剩余能量的阈值E0, 并重新定义信息素增量公式, 如(15)式所示。
|
(15) |
式中：Eini是节点初始能量；Es为下一跳节点s的剩余能量；E0为Es的阈值。Efd是前向数据包a所途径的节点剩余能量之和, 即
|
(16) |
Eavg和Emin分别为节点平均剩余能量和最小能量, 如(17)~(18)式所示。
|
(17) |
|
(18) |
式中：Er为节点r剩余能量；Ha为前向数据包a当前跳数。
通过(15)式推导得出, 当Eavg>Emin时, Efd值越大, 所对应路径的ΔTa(r, s)值越大。在计算ΔTa(r, s)时, 引入Efd可以平衡全局网络节点剩余能量, 提高前向数据包a在计算下一跳概率公式时，选择剩余能量较多节点的概率。
在算法迭代过程中, 考虑到全局网络能量逐渐减小, 阈值E0需要随节点剩余能量降低而改变, 提出自适应函数, 如公式(19)所示。
|
(19) |
ω为常数, ω ∈ (1, 10)。N为算法迭代次数。由(19)式推导得出, E0随N增加而递减, 通过更新阈值E0大小, 可以有效提高ΔTa(r, s)的准确性。
2.3 信息素启发函数蚁群算法中的下一跳概率公式主要由2个关键部分组成: 备选路径上的信息素浓度T(r, s)和信息素启发函数η(r, s)。信息素浓度反映算法在不断迭代后评判路径优劣的标准, 而信息素启发函数反映网络中节点的局部情况。传统的蚁群算法只考虑下一跳节点剩余能量对信息素启发函数的影响。而在实际情况中, 剩余能量较多的节点往往远离汇聚节点, 单一利用节点剩余能量计算出的信息素启发函数可靠性不高, 最终影响下一跳概率公式的准确率。本文在传统蚁群算法的基础上, 综合考虑了下一跳节点剩余能量和节点r到下一跳节点s的距离, 改进信息素启发函数, 如(20)式所示。
|
(20) |
式中：Eini为节点初始能量；Es为节点s剩余能量。λ1和λ2分别代表(20)式中2项的权重值, 且λ1+λ2=1。参数μ是调整搜索角θ与d(r, s)的权重。θ是节点r到汇聚节点的连线和节点r到节点s的连线的夹角, 具体如图 2所示。
|
| 图 2 搜索角 |
d(r, s1), d(r, s2), d(r, s3)分别为节点r到节点s1, s2, s3的距离, θ1和θ2分别是s1和s2到节点r与汇聚节点的搜索角。当角度θ相等时, 距离d(r, s)越大, 该路径上的信息素启发函数值越小; 当距离d(r, s)相等时, 搜索角度越小, 该路径上的信息素启发函数值越大。
在算法初期, 由于网络中各节点剩余能量充沛, 能量因素对信息素启发函数影响较小, 改进后的算法通过引入搜索角θ和下一跳节点距离d(r, s)对搜寻路径进行限制, 有效减少数据在节点间返复传输, 降低能量损耗, 提高网络生命周期。
3 改进算法的流程在WSN中, 除汇聚节点外的节点定期向周围的邻居节点发送1个数据包, 本文将其定义为前向蚂蚁a。前向蚂蚁a从源节点出发, 通过计算下一跳概率公式选择下一跳节点并更新经过的路径和节点的信息素浓度, 同时前向蚂蚁a访问过的邻居节点都会以节点标识的形式存储在邻居列表中。当前向蚂蚁a到达汇聚节点时, 汇聚节点接收前向蚂蚁a的数据, 随即生成后向蚂蚁, 利用信息素公式并把计算后的信息素存储在后向蚂蚁中, 将数据沿原路径返回源节点。一次完整的数据收发过程, 标志着一次源节点到汇聚节点的信息素更新完毕, 随即算法进行新一轮数据收发过程, 算法步骤如下所示。
step 1 建立随机节点分布图并初始化各项参数, 其中初始迭代次数为0, 最大迭代次数为Nmax。
step 2 算法迭代次数加1。每一波次出动m只蚂蚁随机部署在M个节点上, 且每只蚂蚁将经过的节点信息存储在邻居列表中。
step 3 蚂蚁a在节点r, 利用下一跳概率公式, 选择下一跳节点, 如(21)式所示。
|
(21) |
式中：T(r, s)为节点r到节点s路径上的信息素浓度；η(r, s)是信息素启发函数。α和β分别代表信息素和启发函数的重要程度。
step 4 记录蚂蚁a经过的节点源地址和序列号, 并记录节点的剩余能量、平均能量和最小能量等信息。
step 5 判断当前节点是否为汇聚节点, 若未到达则继续执行step 2, 否则执行step 6。
step 6 当前向蚂蚁a到达汇聚节点后, 随即死亡并生成后向蚂蚁a′沿原路径返回。
step 7 后向蚂蚁a′利用(12)式和(15)式更新沿途信息素。
step 8 后向蚂蚁a′到达源节点后, 标志本次迭代结束, 随即重复step 2, 蚂蚁开始下次寻优, 直至迭代次数N=Nmax, 算法终止。
4 实验仿真与结果分析为验证改进算法的有效性, 本文对改进后的ATRE-ARA算法进行仿真实验, 并与现有的经典蚁群算法进行对比, 通过实验得出相应的数据和曲线, 以评价本文算法性能。
4.1 实验环境及相关参数本文实验环境采用Matlab R2016a搭建仿真平台, 仿真环境分别设置为100 m×100 m(环境1)和200 m×200 m(环境2)的正方形区域, 内部部署100个节点。图 3~4分别为节点在环境1和环境2中的分布情况, 其他仿真参数如表 1所示。
|
| 图 3 环境1中节点分布图 |
|
| 图 4 环境2中节点分布图 |
| 参数 | 数值 |
| 每轮发送蚂蚁数量 | 100 |
| 节点初始能量/J | 1 |
| 汇聚节点能量/J | 100 |
| 发送功率/W | 0.04 |
| 接收功率/W | 0.02 |
| 节点通信距离/m | 30 |
| ρ | 0.5 |
| λ1 | 0.4 |
| λ2 | 0.6 |
| α | 1.5 |
| β | 5 |
| Eelec/(nJ·bit-1) | 50 |
| Eεamp/(pJ·bit-1·m-4) | 0.001 3 |
| Eεfs/(pJ·bit-1·m-2) | 10 |
| Tmax | 0.86 |
| Tmin | 0.13 |
| 数据包大小/bit | 1 000 |
最优路径长度表明了各算法的寻优能力。在图 5~6中, ARA算法的最优路径长度与改进算法相同, 但路径收敛速度低于改进算法; EEABR算法的最优路径长度在2种实验环境下均高于改进算法, 收敛速度略快一些。这是因为ATRE-ARA算法在计算路径信息素值时, 引入了信息素上限值Tmax和信息素下限值Tmin, 防止在算法迭代初期, 因局部路径信息素差值过大, 陷入局部最优, 增加了算法搜索全局最优的能力, 但同时也降低了算法在寻优时的收敛速度。
|
| 图 5 环境1中路径收敛曲线 |
|
| 图 6 环境2中路径收敛曲线 |
表 2为3种算法的具体性能对比, 改进算法在不同环境中, 相比EEABR最优路径长度分别缩短了1.47%和1.59%。改进算法在2种环境下的迭代次数较EEABR算法多26次和4次, 较ARA算法少27次和14次。
| 环境 | 算法 | 最优路径长度/m | 最优曲线迭代次数 |
| 1 | ATRE-ARA | 171.51 | 197 |
| EEABR | 174.03 | 171 | |
| ARA | 171.51 | 224 | |
| 2 | ATRE-ARA | 312.19 | 218 |
| EEABR | 317.16 | 214 | |
| ARA | 312.19 | 232 |
为继续深入研究各算法在收敛后的节点能耗情况, 选取3种算法在不同环境下的各节点所消耗能量情况进行对比, 如图 7~8所示。由于本文提出的ATRE-ARA算法在计算信息素增量时, 引入下一跳节点剩余能量的阈值E0, 且阈值E0为自适应函数, 随算法不断迭代而改变, 通过更新阈值E0大小, 可以有效提高信息素增量的准确性。
|
| 图 7 3种算法在环境1下的节点耗能情况 |
|
| 图 8 3种算法在环境2下的节点耗能情况 |
从图 7可知, 在环境1中, 随着迭代次数的累积, 网络中的各节点能量开销逐渐增加, 2种对比算法的节点开销明显高于改进算法。其原因在于改进算法在迭代前期, 通过引入搜索角和下一跳节点距离对搜寻路径进行限制, 明显提高局部寻优能力, 在加速算法收敛的同时, 有效减少数据在节点间回旋, 降低能量损耗。随着全局网络中的节点剩余能量逐渐降低, 改进的信息素增量公式提高了选择剩余能量较多的节点作为下一跳节点的概率, 防止局部节点过早死亡, 达到平衡全局网络能量的目的。
由图 8可知, 由于环境2中节点间距离较远, 数据传输开销较大, 故节点能量消耗明显高于环境1中的节点。改进算法的网络开销均低于对比算法, 与环境1中得出的结论一致。
4.2.2 算法收敛后的节点平均能量分布情况为进一步验证本文ATRE-ARA算法的网络能耗性能, 通过仿真实验对比各算法在不同环境下的不同阶段的平均节点能耗情况。
从图 9~10可以看出, 随着迭代次数的增加, 各算法的节点平均能耗增加。本文提出的ATRE-ARA算法在2种环境下的不同阶段, 节点平均消耗能量均低于其余2种对比算法。且节点平均能耗在环境1和环境2中, 改进算法相比ARA算法分别降低了15.12 %和11.68 %。
|
| 图 9 环境1中平均能耗与迭代次数 |
|
| 图 10 环境2中平均能耗与迭代次数 |
本文在深入研究典型蚁群路由算法的基础上, 提出了一种ATRE-ARA路由算法来解决WSN中节点能量分布不均衡、网络生命周期较短和路由算法容易陷入局部最优等问题。通过优化信息素更新策略, 在设置信息素浓度上限与下限的同时引入节点路由数作为平衡路径信息素浓度的重要参考因素, 防止算法陷入局部最优, 增加了算法搜索全局最优的能力; 改进信息素启发函数和信息素增量公式, 引入搜索角和下一跳节点距离, 对搜寻方向和路径进行限制, 减少数据在节点间返复传输; 将下一跳节点剩余能量的阈值设置为自适应函数, 降低局部节点过早死亡的情况, 平衡网络中节点能量分布。通过仿真实验的对比与分析, 证明改进蚁群路由算法在兼顾全局搜索性能的同时有效延长了网络生命周期。后续将侧重研究三维空间中WSN的节点能量开销及算法寻优问题, 以提出适应更复杂环境下的路由算法。
| [1] | DORIGO M, BIRATTARI M, CARO G, et al. ANTS 2010 special issue[J]. Swarm Intelligence, 2011, 5(3/4): 143-147. |
| [2] | ARJUNAN S, SUJATHA P. Lifetime maximization of wireless sensor network using fuzzy based unequal clustering and ACO based routing hybrid protocol[J]. Applied Intelligence, 2018, 48(8): 2229-2246. DOI:10.1007/s10489-017-1077-y |
| [3] | MEHTA D, SAXENA S. Hierarchical WSN protocol with fuzzy multi-criteria clustering and bio-inspired energy-efficient routing(FMCB-ER)[J]. Multimedia Tools and Applications, 2020(16): 1-34. |
| [4] | DWIVEDI B, PATRO B, SRIVASTAVA V, et al. LBR-GWO: layered based routing approach using grey wolf optimization algorithm in wireless sensor networks[J]. Concurrency and Computation: Practice and Experience, 2021, 12(11): 12-21. |
| [5] |
廖伟志, 夏小云, 贾小军. 基于蚁群算法的多路径覆盖测试数据生成[J]. 电子学报, 2020, 48(7): 1330-1342.
LIAO Zhiwei, XIA Xiaoyun, JIA Xiaojun. Test data generation for multiple paths coverage based on ant colony algorithm[J]. Acta Electronica Sinica, 2020, 48(7): 1330-1342. (in Chinese) DOI:10.3969/j.issn.0372-2112.2020.07.011 |
| [6] |
王培良, 张婷, 肖英杰. 蚁群元胞优化算法在人群疏散路径规划中的应用[J]. 物理学报, 2020, 69(8): 240-248.
WANG Peiliang, ZHANG Ting, XIAO Yingjie. Application of ant colony cellular optimization algorithm in crowd evacuation path planning[J]. Acta Physica Sinica, 2020, 69(8): 240-248. (in Chinese) |
| [7] | SURESHKUMAR K, VIMALA P. Energy efficient routing protocol using exponentially-ant lion whale optimization algorithm in wireless sensor networks[J]. Computer Networks, 2021, 197(4): 1286-1389. |
| [8] | MOSTAFA E, ALAA A. Energy-aware intelligent hybrid routing protocol for wireless sensor networks[J]. Concurrency and Computation-Practice, 2021, 21(6): 112-134. |
| [9] | 张恒, 何丽, 袁亮, 等. 基于改进双层蚁群算法的移动机器人路径规划[J/OL]. (2020-05-22)[2021-05-13]. https://doi.org/10.13195/j.kzyjc |
| [10] | ANANDH S J, BABURAJ E. Energy efficient routing technique for wireless sensor networks using ant-colony optimization[J]. Wireless Personal Communications, 2020, 114(4): 3419-3433. DOI:10.1007/s11277-020-07539-0 |
| [11] | SHAO S, WU L, ZHANG Q, et al. Cooperative coverage-based lifetime prolongation for microgrid monitoring WSN in smart grid[J]. EURASIP Journal on Wireless Communications and Networking, 2020, 20(1): 14-29. |
| [12] |
滕志军, 庞宝贺, 孙铭阳, 等. 基于环境参数优化和时间信誉序列的恶意节点识别模型[J]. 西北工业大学学报, 2020, 38(3): 634-642.
TENG Zhijun, PANG Baohe, SUN Mingyang, et al. Malicious node recognition model based on environmental parameter optimization and time reputation series[J]. Journal of Northwestern Polytechnical University, 2020, 38(3): 634-642. (in Chinese) DOI:10.3969/j.issn.1000-2758.2020.03.023 |
2. Department of Cryptographic Science and Technology, Beijing Electronic Science and Technology Institute, Beijing 100070, China;
3. College of Communications Engineering, Jilin University, Changchun 130012, China
