基于人工智能算法的能量高效分簇路由协议

王彦峰，陈 锟，王兴华

(广东电网公司 电网规划研究中心，广东 广州 510080)

0 引 言

作为无线传感器网络(wireless sensor networks，WSNs)中的核心技术，分簇路由协议通过将传感器节点分簇来提高网络能量效率，从而延长网络生存期[1]。其中，能量效率是指网络能量利用率。WSN中，通过提高能量使用的合理性，能够改善能量利用率，即提高能量效率。基于分簇的WSN中，选择高质量簇首，并规划合理的传输路径是提高网络能量效率、延长网络生存期的关键[2-4]。

针对WSN分簇路由协议存在的能耗问题，文献[5]提出经典的LEACH算法，采用随机的方式对传感器节点进行分簇，并通过周期性轮换簇首均衡节点的能量消耗。文献[6]采用人工蜂群算法优化网络分簇，并构建基于最小生成树的簇间路由以降低簇首负载。文献[7]采用粒子群优化算法选择最优簇首集合，并设计基于最小生成树的路由方案，有效延长了网络生存期。文献[8]运用粒子群优化模糊C均值进行聚类，以优化分簇效果。簇间路由阶段，引入猫群算法构建最优传输路径，以均衡簇首负载。文献[9]利用蝴蝶优化算法来解决最优网络分簇问题，并采用蚁群优化算法构建簇间路由。该协议缓解了路由协议中普遍存在的“热区”问题，提高了网络寿命。文献[10]采用全局交叉人工蜂群算法对传感器节点分簇，并采用改进蚁群算法作为簇首节点去寻找最佳传输路径，有效平衡了网络能耗，进而延长了网络生存期。

上述各项研究都试图通过使用不同的人工智能算法来改善网络性能，并取得了一定的成效。但上述协议仍然存在生存期短等缺陷。因此，本文提出了一种新的分簇路由协议FOFCA，该协议采用萤火虫优化算法(firefly algorithm，FA)对模糊C均值(fuzzy C-means，FCM)进行优化。在成簇阶段，使用FA选取FCM的初始聚类点，进而解决网络分簇问题；簇划分完成后，根据传感器节点的能量等级和地理位置，分布式选定簇首。数据传输阶段，簇首根据蚁群算法(ant colony optimization，ACO)构造的多跳传输路径与基站进行通信，簇内节点采用轮询控制机制向簇首发送数据。

1 系统模型

本节对包括网络模型和能耗模型在内的系统模型进行了描述。其中，网络模型指WSN中网络节点的特性及工作场景的特征。能耗模型指WSN在假设的网络模型中工作时消耗能量的依据。

1.1 网络模型

首先对本文算法所使用的网络模型做如下设定。

(1)具有全局唯一ID的传感器节点随机放置在监测区域内。

(2)所有节点同构，即初始能量相同，计算能力与通信能力相当。

(3)发送节点通过计算自身与接收节点之间的距离，实现了根据通信距离自主调节发射功率。

(4)不能对部署完成的WSN进行人为干预。

1.2 能耗模型

本文采用一阶无线电通信能耗模型，具体定义请参见文献[11]。

2 FOFCA算法

FOFCA算法引入了LEACH协议中“轮”的概念。网络初始化时期，基站执行由FA优化的FCM聚类算法为传感器节点分簇。首轮簇首由距离聚类中心最近的节点担任。此后每轮，成员节点根据当前状态计算自身权重值，并由权值最优的节点担任次轮簇头。所提出的簇头更换模式在提高簇首质量的同时将簇头更换次数维持在合理范围内，从而缓解簇首能耗，并延长网络生存期。

2.1 簇的构建

2.1.1 最优簇数

基于分簇的WSN通过将传感器节点划分为指定数量的簇来降低网络能耗。其中，分簇数量对网络性能有重要影响，因此本节考虑上述网络模型和能耗模型计算最优网络簇数。WSN工作一轮，所有网络节点的总能耗为[12]

(1)

式中：N为WSN中传感器节点的个数，dtoBS为节点与基站之间的欧氏距离。

Etotal对网络簇数k求偏导，得出最优网络簇数为

(2)

2.1.2 FCM聚类算法

FCM算法是一种基于柔性划分的模糊聚类算法，被广泛应用于图像处理、机器学习等领域[13]。应用FCM聚类算法解决WSN的最优聚类问题，网络节点被划分为k个紧致的均匀簇，从而最小化簇内通信距离。

FCM通过迭代优化目标函数，将传感器节点按位置相似度进行划分。目标函数按照下式进行计算

(3)

隶属度按照下式进行更新

(4)

聚类中心按照下式进行更新

(5)

当隶属度矩阵uij更新至最优值时，迭代结束，输出聚类中心。

2.1.3 FA优化FCM算法

FCM算法聚类机制灵活，收敛效果优越，然而，由于聚类性能容易受初始聚类中心的影响，导致算法易陷入局部最优[14]。为了解决这一问题，本文采用FA对FCM的初始聚类中心进行优化。

FA是一种受自然界中萤火虫发光特性启发而提出的新型启发式优化算法，具有设定参数少、协作能力强、鲁棒性强等特点，被广泛应用于人工神经网络训练、系统和工程设计等领域[15]。该算法模拟了萤火虫之间相互吸引和位置迭代更新的过程，将其应用于搜索和优化。使用萤火虫的亮度表示问题解的优劣，亮度最大的萤火虫即为最优解[16]。萤火虫荧光亮度的更新方式如式(6)所示

(6)

式中：I0为萤火虫的最大荧光亮度，即自身的无衰减的荧光亮度，γ为光吸收因子，反映光在传播过程中的衰减损耗，rij为萤火虫i与萤火虫j之间的距离，按照下式进行计算

(7)

式中：d表示待求解问题的维度，xi，k表示萤火虫i在第k维搜索空间的位置。

FA中，亮度较弱的萤火虫会受到亮度较强个体的吸引，并向其移动。个体j向i移动的数学模型如下

xi(t+1)=xi(t)+βFA×(xj(t)-xi(t))+αFA(rand-1/2)

(8)

式中：xi(t) 为t时刻萤火虫i的位置，αFA为步长因子，取值为[0，1]之间的常数，rand为[0，1]上服从均匀分布的随机数，βFA表示吸引度，代表萤火虫之间感受彼此亮度的能力，会随距离的增加而逐渐减小，计算方式如下

(9)

式中：β0表示r=0时的吸引度。

FA优化FCM算法的步骤如下：

步骤1 初始化FA，以随机的方式在搜索空间内生成初始种群。

步骤2 基于适应度函数1/Jm计算种群适应值，适应值越大，萤火虫个体的亮度越强。

步骤3 根据式(7)计算两个个体之间的距离。

步骤4 根据式(8)更新个体之间的吸引度。

步骤5 根据式(9)更新个体位置，其中最亮的萤火虫(适应度值最优个体)不受其它萤火虫吸引，并以随机方式更新自身位置。

步骤6 重复执行步骤2至步骤5，直到满足迭代结束的条件。

步骤7 将FA算法输出的最优解用作FCM算法的初始聚类中心，并执行FCM算法。

步骤8 输出聚类结果。

2.2 簇首选举

成簇阶段，基站采用由FA优化的FCM算法对网络节点分簇。第一轮，距离簇中心最近的传感器被指定为簇首。在后续轮次中，簇首根据节点的能量状态和位置信息计算簇内节点的适应值，并选择适应值最优的节点作为下一轮簇首。节点的适应值按照下式进行计算

fi=αf1+βf2

(10)

式中：fi表示节点i的适应值，f1为能量因子，f2为位置因子，α和β为权重系数，用于调整能量因子和位置因子的权重。

簇首节点相较于成员节点，需要执行更多的任务，因此其能耗也更大。因此，在计算节点适应值时充分考虑了节点的剩余能量，以使簇首有充足的能量执行各类任务。节点的能量因子f1设计为

(11)

式中：Eres(i) 和Eave(i) 分别表示节点i当前的能量值和该簇的平均能量值。由式(11)可知，节点i的能量值越高，对应的f1值也越大，当选簇首的概率越高。

成员节点感知到数据信息后，发送给对应簇首。簇首对数据进行融合，并发送给基站。簇首距离基站越近，则通信距离越短，通信能耗相应较低。因此，选择簇首时需要考虑节点的地理位置。基于上述分析，节点的距离因子设计为

(12)

式中：di表示节点i与基站之间的距离，dmax和dmin分别表示节点i所在的簇内中所有节点到基站距离的最大值和最小值。上式设计的优势在于同一个簇内的节点的位置相对集中，这使得其与基站之间的距离相近，采用余弦函数可以使同一簇内不同节点的距离因子有较大的区分度。节点距离基站较近，则对应的f2值越大，当选簇首的概率就越高。

权重系数的更新方式如下式所示

α=1/(1+Eres(i)/Eave(i))

(13)

β=1-α

(14)

权重系数更新方式的好处为：随网络的运行，节点能量不断耗损，在簇首选举时需要重点考虑节点的剩余能量因素。而α随节点能量的降低动态增加，很好满足了这一需求。

簇首更新时，节点之间需要交换大量控制包，从而产生能量损耗。为解决这一问题，本文降低了簇首更新的频率，在每轮最后，当前簇首根据下式决定次轮是否需要更换簇首

fCH≤λfmax(i)，λ∈(0，1]

(15)

式中：λ为网络系数，决定簇首更新频率。若簇首的适应值满足上式，则需要根据节点适应值来更新下一轮次的簇首。否则，下一轮次不需要更新簇首。这样就避免了因频繁更换簇首而产生的不必要能量开销。

2.3 簇间路由

基于上述网络模型与能耗模型，随通信距离增加，节点的通信能耗成指数型增长。簇首采集簇内节点感知到的数据后，对冗余数据进行压缩并将其发送到基站。如果簇首选择单跳方式向基站发送数据，会出现“热区”问题。针对这一问题，本文提出一种基于蚁群算法[17]的簇间路由方法，用于平衡网络节点的负载。

簇首节点选取下一跳的转移概率函数为

(16)

簇首i到j的启发值按照下式进行计算

(17)

式中：Ej-rem表示j的能量值，dij为i与j之间的欧式距离，Nj为下一跳簇首j所在簇的成员节点数，θ为簇首i到下一跳簇首j的连线与簇首i到基站的连线的夹角，ω1和ω2为权重系数。根据式(17)，可以得知，待选下一跳的节点能量越高、距离基站越近，则当前簇首到该下一跳簇首的启发值越大。此外，当前簇首到下一跳簇首的连线与当前簇首到基站连线所构成的夹角越小，其余弦值就越大，两簇首之间的启发值也越大，这代表更靠近当前簇首与基站连线的下一跳将得到支持，此时通信距离也较短。而远离当前簇首与基站的连线的下一跳将被拒绝。基于上述分析，角度因子能够避免簇首向下一跳节点发送数据时出现回旋式跳转问题。通过考虑多种因素，极大地提高了路径启发因子的功能性，使下一跳节点的选取更具针对性，从而提高路由效率。

信息素的更新方式在路径选择中起着至关重要的作用。本文提出一种新颖的信息素更新方式，包括全局信息素更新和局部信息素更新，分别记为阶段1和阶段2，以提高路由发现效率，其计算方式如下

τij(t+1)=(1-ρ)τij(t)+ρΔτij(t)

(18)

式中：ρ与Δτij(t) 分别表示信息素的挥发系数与增量。

阶段1：搜索代理由i移动至j，并根据下式完成局部信息素更新

(19)

式中：Qlocal为局部信息素浓度。由上式可知，局部信息素浓度更新时，综合考虑了到下一跳簇首的距离和下一跳簇首的剩余能量，在缩短通信距离的同时保证下一跳簇首有充足的能量完成数据转发任务。

阶段2：搜索代理到达终点后原路返回，同时按照下式完成全局信息素的更新

(20)

式中：Qglobal表示全局信息素浓度，为控制参数，Emin和L分别为路径中的最小能量值和路径长度。

根据局部信息素和全局信息素更新方式可知，长度短、能量均衡的路径在信息素更新时将会得到一个较大的值，这能够使路由发现阶段选择合适的路径来传输数据，提高路由效率。

2.4 改进簇内通信机制

一般的分簇路由协议在完成簇构建之后，簇内成员节点在自己的时隙内处于唤醒状态，并将过去一段时间内采集到的数据信息发送给簇首，其余时间进入休眠状态，以节省能量[18，19]。但TDMA机制不能鉴定节点是否需要被唤醒以履行数据发送任务，即不需要发送数据的节点在时隙到来时仍会被唤醒，执行与簇首通信的任务从而导致不必要的能量损耗。为了解决这一问题，本文引入了轮询控制机制，用来替代TDMA机制以完成簇内通信。在簇构建完成之后，簇首节点创建记录成员节点忙闲状态和访问顺序的轮询表，并将其分配给成员节点。其中，簇首根据忙闲状态判断节点是否有数据信息需要发送。簇首通过辨别当前轮次中需要访问的成员节点来针对性的唤醒部分节点，以降低节点能耗，同时避免了时隙的浪费。

3 仿真实验及结果分析

3.1 参数设置

为测试所提协议的有效性，使用Matlab R2016b软件对FOFCA、FIGWO[20]和GAFCMCR[21]协议在不同网络环境下进行仿真实验。监测区域的范围、基站位置和传感器节点的个数是影响协议性能的主要因素[22，23]，因此在不同网络环境下对协议进行仿真实验，WSN的场景参数见表1，仿真参数请参见文献[24]，萤火虫算法和蚁群算法用到的参数见表2[25，26]。

表1 网络场景参数

表2 FA与ACO算法参数

3.2 网络稳定期对比

网络稳定期的定义是网络中首个节点的死亡时间，是评估协议能耗均衡性的指标。在场景1中，网络中部署100个节点时，FOFCA、FIGWO和GAFCMCR的网络稳定期分别为221轮、56轮、89轮；网络中部署200个节点时，3种协议的网络稳定期分别为241轮、56轮、91轮；网络中部署300个节点时，3种协议的网络稳定期分别为229轮、73轮、129轮。在场景2中，3种协议的网络稳定期分别为32轮、7轮、8轮。为方便比较分析，将场景1和场景2中的网络稳定期分别绘制于图1和图2。图1为3种协议在场景1中的网络稳定期对比。场景1规模较小，节点之间的通信距离相应较短，网络节点能够正常工作较长的时间。从图1中可以明显看出，FOFCA相较于其它两种算法在网络稳定期指标上具有显著优势。这一优势得益于本文算法在分簇效果上的良好表现，成功缩短了簇类节点之间的通信距离从而降低通信损耗。此外，FOFCA在簇间通信阶段构造了高效的路由算法，簇首节点根据路由路径完成数据传输，有效降低了其能量消耗。基于上述原因，FOFCA能够有效均衡网络能耗，从而延长了网络稳定周期。图2为3种协议在场景2中的网络稳定期对比。场景2规模较大，簇首与基站之间的距离相对较远，远程通信给簇首带来了巨大的能量损耗，导致其过早死亡。但本文协议使用改进的蚁群算法为簇首节点规划最优传输路径，均衡了簇首负载，缓解了簇首的能量损耗。因此，在大规模场景下本文协议的网络稳定期比对比算法更长。

图1 3种协议在场景1中的网络稳定期对比

图2 3种协议在场景2中的网络稳定期对比

3.3 网络生存期对比

网络生存期用于评价协议的能量效率，其指的是75%的节点的死亡的时间。在场景1中，网络中部署100个节点时，FOFCA、FIGWO和GAFCMCR的网络生存期分别为983轮、457轮、579轮；网络中部署200个节点时，3种协议的网络生存期分别为991轮、538轮、827轮；网络中部署300个节点时，3种协议的网络生存期分别为1083轮、550轮、866轮。在场景2中，3种协议的网络生存期分别为615轮、257轮、396轮。为方便比较分析，将场景1和场景2中的网络生存期分别绘制于图3和图4。图3为3种协议在场景1中的网络生存期对比。由于场景1规模较小，所有节点短距离通信，能量耗损较小，3种协议均有较长的网络生存期。但本文协议分簇效果理想，并且簇首在簇间通信阶段采用了合理的多跳传输路径，降低了网络能耗，使本文所提出的协议在网络生存期指标上表现出显著的优势。图4显示了3种协议在大规模网络场景下的网络生存期对比。在这种大规模场景下，高效的路由算法对协议的性能有重要意义。若簇首节点单跳向基站发送数据，远距离通信会导致簇首节点产生大量的能耗，从而缩短网络生存期。本文提出的协议采用基于蚁群优化的簇间路由算法，有助于为簇首节点找到合适的传输路径，簇首通过多跳将数据发往基站，从而降低了网络能耗。因此，本文所提FOFCA协议在大规模场景下的网络生存期比对比协议更长。

图3 3种协议在场景1中的网络生存期对比

图4 3种协议在场景2中的网络生存期对比

3.4 网络吞吐量对比

部署WSN的目的是为了采集监测区域的数据，因此网络吞吐量是评价协议性能的一个关键性能指标。网络吞吐量越高，代表网络采集到的数据越多。图5为3种算法在场景1中的网络吞吐量的对比结果。根据图5，所提协议收集到的数据包个数远多于其它两种对比协议，这是因为FOFCA具有最长的网络生存期，延长了传感网的工作时间，故收集到了更多的数据包。此外，通过引入轮询调度改善了时隙的利用率，使基站接收到了更多的数据包。在大规模的应用场景中，FOFCA、FIGWO和GAFCMCR这3种协议的网络吞吐量进行了对比，如图6所示。在该场景中，本文所提出的协议具有最高的网络吞吐量，这是因为较长的网络生存期有助于基站接收更多的数据信息。此外，簇内使用轮询调度进一步改善了网络吞吐量。

图5 3种协议在场景1中的网络吞吐量对比

图6 3种协议在场景2中的网络吞吐量对比

4 结束语

为了均衡WSN负载，本文提出一种基于人工智能算法的分簇路由协议FOFCA。在网络分簇阶段，首先利用FA优化FCM聚类算法，克服了FCM受初始聚类中心的影响易陷入局部最优的缺点；其次使用改进的FCM为传感器节点聚类分簇，以最小化簇内节点之间的距离；最后，考虑节点的能量和到基站的距离因素，动态更新簇首以提高其质量。在簇间通信阶段，采用基于改进蚁群优化的簇间路由算法为簇首寻找传输路径，以降低簇首的能耗。同时，通过使用轮询调度完成簇内通信，改善能量利用率。仿真实验结果表明，FOFCA能够有效延长网络生存期，并提高网络吞吐量。