一种QACO-LEACH无线传感器网络分簇路由算法

杨 佳,顾耀华,许 强

1(重庆理工大学 电气与电子工程学院,重庆 400054)2(重庆工商大学 计算机科学与信息工程学院,重庆 400067)

1 引 言

无线传感器网络(Wireless Sensor Networks,WSNs)是指在一定区域范围内,布撒大量具有信息采集和无线通信传输功能的微型智能传感器而组成的一种无线自组织网络[1].该网络可以对指定区域内的待监测量进行感知、处理和传输,最终将待监测量发送给观察者,从而可以实现远程检测的目的.无线传感器网络的这些特点决定了它在人们的日常生活和工农业生产中具有很大的实用价值.然而,无线传感器网络的节点能源大都来自于电池,随着电池能量的耗尽,很多环境下无法更换新的.并且当前技术无法对电池容量增大太多,能耗问题已经成为无线传感器网络发展的最大制约因素之一.因此,该问题成为了国内外学者研究的热点.其中,采用对无线传感器网络分簇路由进行优化来节约网络能耗是主要解决方式之一.

文献[2]所提出的LEACH是最早的分簇路由算法.该算法对所有传感器节点进行分簇,并在每个簇中选出一个簇头.这种方式与之前的方法相比,极大的节约了能耗.但是,该算法中所有簇头都是通过单跳的方式直接与Sink节点进行通信,这就会造成远离Sink节点的簇头能量消耗过快.此外,在选择簇头的时候,还存在无法保证簇头均匀分布的问题.近年来,群智能算法被引入到无线传感器网络中.其中,文献[3]在经典LEACH协议的基础上,引入蚁群优化(Ant Colony Optimization,ACO)算法,提出了一种基于蚁群的无线传感器网络分簇路由协议(ACO-LEACH),在一定程度上实现了节约能耗和延长网络生命周期的目的.但是,使用蚁群算法搜寻路径具有盲目性,容易造成局部最优解,并且最优路径的收敛速度比较慢.因此,本文在无线传感器网络的分簇阶段采用改进的LEACH协议对传感器进行分簇和簇头的选择;在簇间路由阶段,引入量子蚁群优化(Quantum Ant Colony Optimization,QACO)算法对无线传感器网络路由路径选择问题进行优化,找到全局最优解,加快了算法的收敛速度.提出了一种基于量子蚁群优化的无线传感器网络分簇路由算法(QACO-LEACH).该算法可以更好地节约节点的能耗,延长网络的生命周期.

2 量子蚁群算法

量子进化算法(Quantum Evolutionary Algorithm,QEA)是一种基于量子计算的一些理论和概念,并且模拟了量子态矢量表示和量子旋转门运算的概率进化算法[4].QEA在种群多样性、全局优化能力和收敛速度等方面表现出比传统遗传算法更好的性能.此外,该算法容易与其他算法融合的特点,也使得其在许多优化问题中得到广泛的应用.在研究量子进化算法的基础上,文献[5]和文献[6]详细阐述了进化计算和量子计算这两个概念,并且将这两个概念融合到蚁群算法中,提出了量子蚁群优化算法.在该算法中,量子比特可用于表示每只蚂蚁任意时刻的位置信息.在每只蚂蚁移动之前,根据选择概率来选择下一时刻的位置.这种选择概率可依据每条路径上的信息素强度和可见度大小判断得到.而蚂蚁位置的改变可以使用量子比特的更新来表示.因此,需要使用量子进化算法中的量子旋转门来更新代表每只蚂蚁此时位置信息的量子比特,从而实现蚂蚁的移动.在量子蚁群算法中,可以很好的解决蚁群算法中易于陷入局部最优的问题,主要是因为有效的增加了位置的多样性.所采取的措施之一就是每只蚂蚁的位置信息都使用量子比特的两个概率幅来表示.其次就是引入了量子非门,实现了蚂蚁位置的变异.在完成了蚂蚁位置变化之后,可根据蚂蚁位置信息的变化数据,更新路径的信息素强度和可见度大小.更新之后的信息素强度和可见度大小,又成为接下来其他蚂蚁选择概率的判断依据.与传统蚁群算法相比,同样数量的蚂蚁,量子蚁群算法的搜索空间更大,收敛速度更快,能更好的找到全局最优解.

3 基于量子蚁群算法的WSN分簇路由算法

传统的WSN分簇路由算法具有周期性,每个周期都包括两个阶段:簇形成阶段和簇间路由阶段[7].本文所提出的QACO-LEACH与此相同,在每一个周期中,我们将首先把所有节点划分成很多簇,然后才是等待数据的传输.

在簇形成阶段,每个簇中簇头的选择是需要解决的首要任务,该簇头节点将要承担比普通节点更多的额外任务,比如数据融合和收发消息等,这就必然会导致簇头节点比普通节点消耗更多的能量[8].因此,节点的剩余能量毋庸置疑是我们在选择簇头节点时必须要考虑的一个重要因素.此外,为了解决随机性选择簇头导致的簇头节点分布过于密集的情况,本文设定一个参数L,对于临近的两个待选簇头节点,首先判断两者之间的距离大小,若距离小于L,就比较两者各自的剩余能量大小.选择剩余能量大的节点作为簇头,另一个自然成为普通节点,从而确保形成的簇更加合理,避免了簇头“扎堆”现象.

其中,L的表达式为:

(1)

式中,S是检测区域的面积,N是传感器节点的数目,P是簇头节点占总节点数的比例.

在簇间路由阶段,主要进行的工作就是数据传输,而数据传输主要采用的方式就是在簇头节点与Sink节点之间进行多跳通信.本文在这种多跳通信中引入QACO算法,找出距离较远的簇头节点与Sink节点之间的最优路径.在该最优路径中进行数据传输,可以大大降低远离Sink节点的簇头节点的能耗,从而延长了整个网络的生命周期.本算法流程图如图1所示.

图1 QACO-LEACH算法流程图Fig.1 QACO-LEACH algorithm flow chart

4 算法的实现过程

4.1 簇形成阶段

簇头被选定之后,即以广播的形式向其周围节点发送当选簇头的消息.周围节点随后判断自身与簇头节点之间的距离大小,选择距离近的簇头节点并加入该簇.以此类推,各个节点自组织的加入各自的簇,直到所有节点分簇完成.实现步骤和一些伪代码如下:

Step 1.对所有参数值以及用得到的数据表进行初始化,同时在N×N的正方形区域内随机分布适量的节点,并将每个节点的坐标(x,y)记录下来.

Step 2.Q=Rand(0,1)//各个节点选择随机数

If (Q < T(n)) //T(n)的公式见式(2)

Position=Cluster Head //当选簇头

Broadcast //以广播形式向其他节点发送当选簇

头消息

If (Position=Cluster Head)

Listening

If (临近的两个簇头节点互相接收到对方发送的消息)

If (它们之间的距离

比较它们的剩余能量大小,大的即为簇头,小的自动成为

成员节点

End

(2)

其中,p表示簇头数量占总节点个数的百分比;Ecurrent是节点此时的能量;r表示此时的轮数;Emax是节点的初始能量值;G是在最后1/p轮中仍然没有当选簇头的节点集合.

簇头选择完成.

Step 3.剩余的所有未当选簇头的普通节点,判断自身与簇头节点之间的距离大小,选择距离近的簇头节点并加入该簇.以此类推,各个节点自组织的加入各自的簇,直到所有节点分簇完成.

4.2 簇间路由阶段

4.2.1 初始种群产生

在QACO中,蚂蚁种群初始化时,以随机的方式对代表每只蚂蚁当前位置的信息进行初始化编码.可以使用如下方案进行编码:

(3)

其中,θij=2π×rand;(i,j=1,2,…,m),m是种群规模,n是空间维数,rand是(0,1)之间的随机数.由该方案可知,两个量子态 |0>和|1>的概率幅各自代表了每只蚂蚁在空间中所占据的两个位置信息.因此,当蚂蚁的数量相同时,蚂蚁的搜索空间增大为原来的两倍,这一特点自然会使得收敛速度大大加快[8].

qi0=(cos(θi1),cos(θi2),…,cos(θin))

(4)

qi1=(sin(θi1),sin(θi2),…,sin(θin))

(5)

qi0为|0>态位置,qi1为|1>态位置.在选择路径时,分别使用一个染色体基因的因子代表每一个待选路径.当某条路径被选中时,其因子将被置1,若未被选中,则置0.在完成了这些工作之后,即可进行量子进化算法的操作.

4.2.2 蚂蚁位置更新与变异处理

在蚁群算法中,种群在搜索空间中多样性的丢失,容易导致陷入局部最优[9].因此,为了避免出现局部最优的情况,我们就需要提高种群多样性.本文采用的方式是将变异算子引入到进化算法中.在量子蚁群算法中,将传统ACO中蚂蚁经过之后路径信息素强度的增加量转变为量子旋转门旋转角的更新.该方式可以保证信息素向最优目标解的方向坍缩,信息素的更新以及量子旋转门的使用如式(6)(7).

(6)

(7)

其中:Δθ是旋转的角度大小,这里使用自适应的方式来调整量子旋转角Δθi的方向和大小,可以避免采用查询表的方式所带来的不便.调整方式如式(3)所示,容易得出对于旋转角的每一次调整,一定可以让信息素的更新趋势朝着目标最优解的方向调整.

Δθij=-sgn(A)×Δθ

(8)

(9)

其中:G是设置好的最大迭代次数,t是当前的迭代次数.最初执行算法时Δθ的值相对较大,这样可以保证搜索的范围更大,使算法的搜索空间更大,同时可以更好的跳出局部最优,防止过早陷入局部最优.随着迭代次数不断增加,Δθ的值会变得越来越小,因此可以确保算法在局部的更新能力.

然后,利用更新后的量子旋转门,对代表蚂蚁此时位置信息的量子比特进行更新,即完成了蚂蚁位置的移动.自此,只须改变每只蚂蚁的量子位概率幅,就可实现蚂蚁位置的变动.蚂蚁转移概率方程为:

(10)

(11)

式中dij为相邻两个簇头节点之间的距离,β(β≥0)为期望的启发式因子,μj为节点j的量子信息强度,其表达式为

(12)

式中|αj|2表示第j个量子位的量子态坍缩到|0>的概率,γ(γ≥0)为量子比特启发式因子.

4.2.3 路径信息素强度更新规则

在QACO中,信息素强度越高的地方,表明路径越好,因此需要及时更新信息素强度[10].在每个蚂蚁分别完成对各个路径的搜索选择之后,将所有单个蚂蚁的搜索结果映射到最优解空间中,从而完成蚂蚁当前位置信息素强度τij的局部更新.路径信息素强度的更新方程为:

(13)

4.2.4 具体实现步骤

1)times←0(times表示迭代次数或搜索次数);对每个τij和Δτij进行初始化;将每个蚂蚁各自放在待搜索区域的中心位置,待搜索区域的大小可根据蚂蚁的数量和所占空间大小来确定;

3)对每个蚂蚁下一步的前向目标函数Zk进行计算,并记录此时的最优解;

4)根据量子进化算法中表示量子行为的迭代方程,对蚂蚁所在区域周围路径进行区域搜索,并对目标函数进行优化;

5)针对蚂蚁周围的各个路径信息素浓度的改变,可使用更新方程对各个轨迹强度进行更新;

6)每只蚂蚁k的数据变化:Δτij← 0;times←times+1;

7)如果times< 预期的搜索次数而且没有退化行为(即搜索到的都是相同解),则转回步骤(2);

8)输出当前的最优解.

5 仿真实验与结果分析

为了验证本文提出的QACO-LEACH算法在无线传感器网络寻找最优路径和节约能耗中的优势,在Matlab2016a平台上分别对最优路径、分簇效果和能量消耗进行了仿真对比.

5.1 QACO-LEACH与ACO-LEACH搜寻最优路径效果对比

在100m×100m的正方形范围中,随机分布50个簇头节点.算法中参数分别设置为:α=0.9,β=1.8,ρ=0.8,γ=0.9.其中设置两个固定点:起始节点A(10,20),目的节点B(25,45).分别使用ACO算法和QACO算法选择从A点到B点的最优路径,仿真结果如图2所示.

图2 最优路径长度收敛曲线Fig.2 Optimal path length convergence curve

由图2明显看出,本文提出的QACO-LEACH最小路径长度始终小于ACO-LEACH,仿真结果表明,该算法在寻找最优路径方面具有更好的优势,达到了预期目标.

QACO的性能优于ACO是因为,对于基本蚁群算法来说,其在某一路径上不断增加的信息素含量,使得运行的结果更容易陷入局部最优.这种情况必定会导致无法更好的在整个网络中找寻到最优路径.相比之下,量子进化算法中,一个量子可以有三种状态:|0>态、|1>态以及|0>和|1>之间的任意叠加态.所以一个量子位所处的状态可以表述成|ψ>=α|0>+β|1>,α、β是实数,表示一个量子位所处状态的概率幅,同时此概率幅满足归一化的条件,即为|α|2+|β|2=1.因为量子比特可以处于|0>和|1>之间的任一连续状态中,因此量子优化算法可以表现出更多的状态和更多的多样性.所以QACO融合了量子进化算法和蚁群算法的优点,将信息素用量子编码来表示,可以解决搜寻最优路径时,信息素聚集过快的问题.通过使用量子旋转门,达到跳出局部最优进而使搜索继续进行下去的目的,最终搜寻到全局最优路径.

5.2 QACO-LEACH协议与其他协议分簇和节能效果对比

现分别在同一场景中对比LEACH协议、ACO-LEACH协议和QACO-LEACH协议在分簇和节能方面的表现效果.具体仿真环境与参数如表1所示.

表1 仿真环境与参数
Table 1 Simulation environment and parameters

5.2.1 QACO-LEACH与其它协议的分簇效果对比

在同样实验场景中,对LEACH协议、ACO-LEACH协议和QACO-LEACH协议在分簇阶段的效果进行对比.图3-图5分别为同一轮中三种协议的分簇结果.

图3 LEACH分簇结果仿真图Fig.3 LEACH clustering result simulation diagram

由以上各分簇仿真图看出,LEACH和ACO-LEACH分簇结果不太均匀, 很多簇头之间距离过近, 甚至出现两个临近簇头“重叠”现象.而QACO-LEACH的分簇结果相对更加均匀,未出现簇头“扎堆”现象,表明本文在LEACH基础上,加入的L参数有效的避免了簇头距离过近的现象,增加了簇头的整体分布合理性,达到了预期分簇效果.

图4 ACO-LEACH分簇结果仿真图Fig.4 ACO-LEACH clustering result simulation diagram

5.2.2 QACO-LEACH与其它协议的节能效果对比

在QACO-LEACH完成分簇之后,继续进行簇间路由,得到剩余存活节点个数仿真曲线,并与LEACH、ACO-LEACH和QACO-LEACH进行实验对比.仿真对比结果如图6所示.

图5 QACO-LEACH分簇结果仿真图Fig.5 QACO-LEACH clustering result simulation diagram

图6 剩余存活节点个数曲线图Fig.6 Curve of the number of remaining surviving nodes

由图6可以看出,在仿真时间为100轮附近,LEACH协议已有节点开始死亡;在190轮附近,ACO-LEACH协议有节点开始死亡;而在240轮附近,QACO-LEACH协议才有节点开始死亡.LEACH协议和ACO-LEACH协议的节点死亡一半的时间分别发生在180轮和390轮,而在QACO-LEACH协议中的节点在420轮死亡一半.当网络运行相同时间后,本文提出的QACO-LEACH比LEACH和ACO-LEACH剩余节点个数都多,表明通过本文算法的使用,有效的降低了簇头节点的能耗.

QACO-LEACH对无线传感器网络节点能耗的改善效果比LEACH和蚁群算法好,主要是因为LEACH协议中所有簇头都是通过单跳的方式直接与Sink节点进行通信,另一方面在选择簇头的时候,还存在无法保证簇头均匀分布的问题,容易造成簇头“扎堆”现象,这些缺陷会造成远离Sink节点的簇头能量消耗过快,导致网络寿命大大减少.而本文的QACO-LEACH,在分簇阶段引入一个参数L,从而解决了簇头分布不均匀的问题.ACO-LEACH在LEACH基础上引入了蚁群算法,一定程度上实现了节约能耗和延长网络生命周期的目的,但是使用蚁群算法搜寻路径具有盲目性,容易造成局部最优解,并且最优路径的收敛速度比较慢.针对这种现象,本文的QACO-LEACH利用量子蚁群算法的全局寻优能力好和收敛速度快的优点,很好的解决了簇间路由阶段出现的问题,找到了全局最优路径,从而降低网络能耗.

综上所述,本文算法分别在分簇阶段和簇间路由阶段解决了LEACH的分簇不均匀以及传统蚁群算法容易陷入局部最优和收敛速度慢的问题,并能更好地找到最佳路径.最终实现了预期结果,无线传感器网络生命周期延长效果明显,对以后的研究具有很好的参考价值.

6 结束语

量子蚁群算法综合了蚁群算法和量子进化算法的优势,克服了传统蚁群算法的缺点,简易的操作和相对成熟的理论研究,使算法更容易实现,从而可以在一些优化问题中达到更好的效果.本文在无线传感器网络中引入量子蚁群算法,对于蚂蚁位置的改变,选用了量子进化算法中的量子旋转门对代表蚂蚁当前位置的量子比特进行更新来实现.然后,依据位置的更新,实现蚁群信息素强度的更新.仿真结果表明,该方法提高了收敛速度,并增加了解的多样性,从而找寻到最优路由路径,节约了网络能耗,使网络生命周期得以延长.在无线传感器网络节能优化领域,提供了一个很好的解决方案.本文中算法在中小规模无线传感器网络中优化效果明显,在大规模乃至超大规模无线传感器网络中的效果有待实验验证.下一步将考虑在大规模无线传感器网络中进行优化实验,使其在大规模网络中达到相同优化效果.