基于改进SSA优化WSN分簇协议

孙其昌，朱正礼，张福全

(南京林业大学 信息科学技术学院，江苏 南京 210037)

0 引言

无线传感器网络(Wireless Sensor Networks，WSN)是被广泛使用的Ad Hoc无线网络类型之一[1]，它主要由部署在分散目标区域中的大量微型且廉价的低功耗传感器节点组成。无线传感器网络的主要限制是传感器节点的电源受限。电池供电的传感器通常部署在恶劣、无人值守的环境中，在这些环境中几乎不可能更换电池，导致传感器节点可用的能量受到限制[2]。因此，最小化能耗以延长网络生命周期是无线传感器网络研究的重要课题。由于传感器节点的大部分能量消耗是由无线通信引起的，因此选择有效的路由算法可以显著降低通信能量[3]。LEACH是目前最流行也是最早的分层路由协议之一。在典型的分层路由算法中，许多后续路由协议中都引用LEACH中的分簇思想。分簇方法减少网络的能量消耗并改善网络的寿命。LEACH的核心概念是轮回制，基本思想是周期性地随机选择一个簇首节点，并在传感器节点之间平均分配网络能量负荷[4]。LEACH协议一直是研究的热点，事实证明LEACH与一般的平面多跳路由协议和静态分层算法相比，可以将网络生命周期延长15%。但是，LEACH协议未指定群集头节点如何均匀分布，并且由于成为簇首的每个节点消耗的能量大致相同，因此该协议不适用于节点能量不平衡的网络[5]。

在本文中，考虑节点的位置和剩余能量，以及集群中的成员节点数量，通过改善簇首选择机制并进行仿真验证。提出一种基于改进麻雀搜索算法(Improved Sparrow Search Algorithm,ISSA)的分簇路由协议，在考虑簇内邻居节点数量、能量和距离分布信息的前提下，优化簇首的选择。

1 问题描述

传统LEACH协议将网络中所有存活的传感器节点采用单层模式划分，把网络内非死亡传感器节点划分为成员节点和簇首节点。成员节点和簇首节点进行簇内通信，簇首节点和Sink节点进行簇间通信。LEACH协议按“轮”周而复始直至节点全部死亡或者达到预设的结束条件，每一轮包括两个阶段，即建立阶段和稳定阶段，对应簇首选举、簇的划分和数据传输阶段[6]。

LEACH协议将网络划分层次，可在一定程度上均分能耗，提高网络生存周期。同时，LEACH协议减少信息传输的时耗，且簇的划分也在一定程度上维系拓扑结构，使得网络更健壮[7]。随着对LEACH的深入研究，研究人员发现LEACH协议存在以下不足：

① LEACH协议在选举簇首时，节点等概率成簇，没有考虑到节点的剩余能量,使得能量小的节点可能被选为簇首，从而导致能量很快耗尽。

② LEACH协议在选举簇首时未考虑节点位置，使得选出的簇首可能分布在边缘或聚集在一起，加剧能耗。

③ LEACH协议每一轮中产生的簇首数是随机的，选出的簇首数可能超出网络正常运行的需求，从而降低网络内节点的生命周期。

为改进LEACH协议存在的不足，本文提出一种新的路由协议——LEACH-ISSA。LEACH-ISSA采用集中式控制策略，每轮各阶段与LEACH 协议相同，LEACH-ISSA 相较于LEACH协议的改进之处在于利用ISSA优化WSN分簇过程采用LEACH-ISSA协议在簇首选举过程中会根据节点的能量和位置以及簇内成员节点数等信息选择簇首。

2 麻雀搜索算法

麻雀搜索算法(Sparrow Search Algorithm,SSA)[8]是根据麻雀觅食并逃避捕食者的行为而提出的群智能优化算法。SSA主要模拟麻雀群觅食的过程。麻雀觅食过程也是发现者-跟随者模型的一种，同时还叠加侦查预警机制[9-10]。麻雀群中找到食物较好的个体作为发现者，其他个体作为跟随者，同时种群中选取一定比例的个体进行侦查预警，如果发现危险则放弃食物。

SSA中每个个体为麻雀，它们只有一个属性“位置”——代表它找到的食物的位置。每只麻雀有3种可能的行为：

① 作为发现者，持续搜索食物，不断更新位置，寻找最优位置；

② 作为跟随者，跟随发现者觅食；

③ 作为预警者，有危险则放弃食物。

在d维解空间内每只麻雀的位置为适应度值。这群麻雀中有n只麻雀，每代选取种群中位置最好的pn只麻雀作为发现者，剩余的n-pn只麻雀作为跟随者。麻雀的位置X可以用以下矩阵表示：

(1)

式中，n为麻雀的数量，d表示要优化的变量的维数。麻雀的个体适应度值可以用以下向量表示：

(2)

式中，n表示麻雀的数量，Fx中每行的值表示个体的适应度值。

2.1 发现者位置更新

在每次迭代过程中，发现者的位置更新如下：

(3)

当R2

2.2 跟随者位置更新

在每次迭代过程中，跟随者的位置更新如下：

(4)

式中，XP为发现者当前最佳位置，Xworst表示当前种族最差位置。另外，A表示1×d维矩阵，其中每个元素随机分配1或-1，并且A+=AT(AAT)-1。

当i>n/2时，其值为一个标准正态分布随机数与一个以自然对数为底数的指数函数的积，当种群收敛时其取值符合标准正态分布随机数。(其值会收敛于0)。

当i≤n/2时，其取值为当前最优的麻雀的位置加上该麻雀与最优位置每一维距离随机加减后，将总和均分到每一维上。可以描述为在当前最优位置附近随机找一个位置，且每一维距最优位置的方差将会变得更小，即不会出现在某一维上与最优位置相差较大，而其他位置相差较小(其值收敛于最优位置)。

2.3 预警者位置更新

种群觅食时，会选取部分麻雀负责警戒，当天敌靠近时，无论是发现者还是跟随者，都将会放弃当前的食物而飞到另一个位置。每代从种群中随机选取SD(一般取10%～20%)只麻雀负责预警行为。其位置更新公式为：

(5)

3 改进的SSA优化算法

3.1 SSA改进方向

SSA在求解最优解在原点附近的问题时，其性能非常好，而当待求解的最优解距原点较远时，其性能将会迅速下降，收敛速度较慢。

由于SSA的各麻雀收敛于当前最优解的方式是直接跳跃到当前最优解附近，不是像其他进化算法那样向最优解移动，这就导致SSA容易陷入局部最优，且全局搜索能力较弱。为避免SSA的局部收敛，改进其全局优化函数，在麻雀位置更新时引入自适应t分布的变异策略，借此来提高收敛速度并避免算法陷入局部最优。

3.2 自适应t分布策略

t分布又称学生分布(Student’s t-distribution)，含有参数自由度n，它的曲线形态与自由度n的大小有关，n值越小，其曲线越平坦，曲线中间越低，曲线双侧尾部翘得越高[11]。高斯分布(Gaussian)、柯西分布(Cauchy)与t分布的对比如图1所示。

图1 3种分布对比图Fig.1 Comparison of three distributions

对麻雀位置利用自适应t分布进行更新如式(6)所示：

(6)

(7)

算法流程如下：

步骤1：初始化参数，包括种群数量N、最大迭代次数、发现者比例PD、预警者比例SD、预警阈值R2；

步骤2：计算麻雀种群个体适应度值，找出当前最优适应度值和最差适应度值以及二者对应的位置；

步骤3：从适应度值较优的麻雀中，选取部分麻雀作为发现者，按照式(7)重新更新位置；

步骤4：步骤3余下的麻雀作为跟随者；

步骤5:从麻雀种群中随机选择部分麻雀作为预警者；

步骤6：再次计算麻雀个体适应度值并更新麻雀位置；

步骤7：是否满足停止条件，满足则退出，输出结果；否则，重复执行步骤2～6。

3.3 测试函数验证

本小节通过使用4个标准测试函数如表1所示，验证所提出的ISSA的可行性和有效性。

表1 测试函数及参数

如图2所示，SSA和ISSA应用在4个基准函数上的收敛曲线(y轴为当前最佳收敛值)。从图中可以看出，ISSA在收敛速度和收敛精度上均优于 SSA。

(a) F1

4 应用ISSA优化WSN分簇

基于ISSA优化的分簇路由协议(LEACH-ISSA),通过优化簇首的选择来避免部分节点能量过度损耗，从而降低死亡节点的出现概率。算法主要步骤如下：

步骤1：初步成簇

使用LEACH协议对目标网络进行簇的初步划分，形成的簇首集称为候选簇首集,设定能量阈值E0，排除低能量节点后，有M个节点被选为候选簇首组成新的候选簇首集[8]。E0为网络中所有存活节点能量的平均值：

(8)

式中，N为网络中节点的总数，Ei为节点i当前的剩余能量，D为死亡节点数，剩余能量大于阈值E0的节点才可作为候选簇首节点。此时只考虑节点剩余能量，并未考虑各节点的位置、邻居节点数、与基站的距离等因素，所以候选簇首只负责收集、发送节点信息，不进行数据传输。

步骤2：候选簇首信息收集

簇内节点将自身的位置、当前能量、邻居节点数等信息传递给候选簇首，候选簇首将各自包含的节点信息发送到基站。

步骤3：LEACH-ISSA算法优化并确定簇首

该阶段为LEACH-ISSA优化算法的核心阶段，由基站进行集中式控制[12]。每轮基站先接收当前候选簇首集，簇首集中每个候选簇首节点包含对应簇内节点的信息[13]。基站依据定义的适应值函数，使用LEACH-ISSA算法评价簇首集中每个候选簇首，并不断更新寻找最优适应值，对应找到食物的麻雀位置为该种群的最优位置，即该簇的最优簇首。优化后的最优簇首位置可能和实际节点信息有差别，取最近节点位置为实际最优簇首节点位置。最终得到M个最优簇首组成最佳簇首集。

为选取最优簇首建立对应的适应函数，本文主要设计如下几个决策因子：

(1) 簇首剩余能量因子f1

将各节点的剩余能量引入适应值函数，作为簇首剩余能量因子。簇首剩余能量因子表示网络内所有存活节点的能量与簇首能量的比值，公式为：

(9)

式中，ECHj表示簇首节点的能量。若簇首节点的剩余能量越高，则f1值越小，表示该函数倾向于选择剩余能量高的节点为簇首，从而均衡网络负载，延长网络寿命。

(2) 簇首间距因子f2

初始分簇时可能出现分簇不均匀的情况，使得簇首过于靠近，且簇首会处于簇内边缘位置。由于簇内采用单跳通信，加大了簇内节点到簇首的通信消耗。因此引入簇首之间距离因子，公式为：

(10)

式中，d(CHi,CHM)表示簇首i～M的距离，用于调整簇首间距。d(CHi,BS)表示簇首i到基站的距离，用于调整簇首到基站的距离。当每轮初始分簇得到对应M值时，为使f2越小，需减小簇首与基站的距离,同时增大簇首之间距离，使簇首在整个网络中分布更分散。

(3) 邻居节点数因子f3

引入邻居节点数因子，选簇时应该给予簇内邻居节点数多的节点更多成为簇首的机会，减少通信距离。当与整个网络平均邻居节点数相近时，簇首分布更均匀，公式为：

(11)

式中，|Ci_avg|表示第i个簇内所有节点的邻居节点数的平均邻居节点数，|Cavg|表示整个网络的N个节点的平均邻居节点数。二者值越接近，每个簇的簇内平均节点数越均匀，对应f3的值越小。综上所述，适应值函数如下所示：

fitness=αf1+βf2+λf3，

(12)

式中，α，β，λ为用户定义的常数，表示3组因子对适应值函数的影响程度。α+β+λ=1，依据需要可调整相应权重，对应权重取值越高表示相对应的影响因子在选取簇首时起到的作用越大。LEACH-ISSA算法流程如图3所示。

图3 LEACH-ISSA每轮算法流程图Fig.3 LEACH-ISSA algorithm flow chart for each round

5 仿真与结果分析

5.1 仿真环境

本文实验采用Matlab2018b作为实验平台，对LEACH算法和LEACH-ISSA算法进行仿真实验比较。实验的能量模型采用文献[14]使用的一阶无线通信模型。d0为固定值，公式如下：

(13)

式中，εfs表示自由空间损耗，εamp表示多径衰落损耗。节点在距离d上传输kbit时，若传输距离大于d0时,采用自由空间模型；小于等于d0时，采用多路径消耗模型。

在能耗计算上，以k表示一个数据分组的比特数,Eelec表示每传输1 bit数据的能耗，EDA表示每融合1 bit数据的能耗。距离为d的两节点间传输kbit数据的发送能耗ETX(k,d)和接收能耗ERX(k,d)，以及融合kbit数据的融合能耗EDA(k,d)计算方法分别为：

(14)

ERX(k,d)=kEelec，

(15)

EDA(k,d)=kEDA。

(16)

式(14)为自由空间模型或多路衰减模型。考虑距离的影响因素，采取设定传输距离阈值d0，将节点的发送能耗划分为自由空间能耗和多径衰减能耗两种模式。阈值公式如式(13)，如果传输距离小于d0，采用前者；如果传输距离大于d0，则采用后者。接收节点的能耗公式不变。

在仿真实验中，无线传感器网络由100个具有定位功能的节点组成，节点在指定大小区域内随机分布，基站BS位于坐标(x=150,y=150)，每个节点初始能量相同为0.1 J，实验参数如表2所示。

表2 实验参数表

5.2 仿真结果和分析

为评价LEACH-ISSA协议的效果，实验将从网络剩余能量、生存时间以及簇首能量消耗与LEACH、LEACH-SSA协议进行对比。为更符合实际，设定当死亡节点数在80%以上，仿真结束。

图4、图5为整个区域内存活节点数随着轮次增加的变化，图中显示LEACH协议第一个死亡节点在57轮，LEACH-SSA协议为469轮次， LEACH-ISSA协议在706轮。LEACH协议达到80%死亡节点在558轮，LEACH-SSA为875轮次，LEACH-ISSA为911轮次。由此说明，经LEACH改进的LEACH-ISSA算法可有效避免节点过早死亡，减少损耗，达到延长整个网络生存周期的目的。

图4 存活节点数对比图Fig.4 Comparison of the number of surviving nodes

图5 死亡节点数1%、10%、80%轮次对比图Fig.5 Comparison of 1%,10%,and 80% of the number of dead nodes

图6为整个网络剩余总能量的比较，从图中可以看出，相同初始能量下LEACH-ISSA协议中网络剩余总能量大于LEACH协议和LEACH-SSA协议，表明整个网络的能量消耗得到有效降低。

图6 剩余能量对比图Fig.6 Comparison of remaining energy

图7为网络中簇首每轮消耗能量的比较，因为在整个网络运行中，节点作为簇首时的能耗最大，所以对簇首选择的改进最有效。通过对比3种协议在每轮簇首节点消耗的能量，发现LEACH-ISSA协议每轮簇首消耗的总能量明显小于LEACH协议，表示LEACH-ISSA协议排除不必要的簇首节点，减少簇首数量。另外从图中可以看出LEACH-ISSA协议簇首整体消耗相比于LEACH协议更均衡。

图7 簇首能耗图Fig.7 Energy consumption diagram of cluster head

结果显示，在80%节点死亡仿真结束前提下， LEACH-ISSA算法生命曲线明显优于其他两种算法。与LEACH 算法相比，本文算法节点存活率提高63%左右，与使用LEACH-SSA相比，本文算法节点存活率提高4%左右，有效均衡网络中的能量。

6 结论

针对LEACH协议的不足，提出LEACH-ISSA协议。首先对SSA进行改进；然后利用ISSA，兼顾节点剩余能量、位置及相邻节点等因素，使LEACH协议的簇首选择分布更加合理，成簇效果得到优化。有效降低网络的整体能耗，延长网络的生命周期。下一步工作重点将考虑结合WSN路由路径规划进行优化。