基于正弦余弦算法的LEACH-C协议的改进

郭晓玲，李 玲，邹 昕，韩宇轩

(河北北方学院信息科学与工程学院，河北 张家口 075000)

无线传感器网络(wireless sensor networks，WSNs)是一种智能式和分布式的网络，它通常由大规模的低成本传感器节点通过无线的方式互联而成[1]。目前，WSNs已经被广泛应用到社会生活的诸多领域，是当前备受瞩目的热议话题之一。WSNs通常采用电池供电，能量受限，如果被用于监测环境恶劣的区域，后期更换维护电源的难度很大，因此，WSNs的首要任务就是提高携带的初始电源能量的利用率，尽可能延长整个网络的生命周期，避免出现监测盲区[2]。

WSNs大部分能量消耗集中在无线通信模块，设计WSNs的路由协议至关重要。LEACH-C(low energy adaptive clustering hierarchy,LEACH-Centralized)，一种集中式低功耗自适应分簇协议，它在分簇时使用模拟退火算法(simulated annealing，SA)寻找当前最优的簇头方案减少每轮的能量消耗[3]。模拟退火算法作为一种随机搜索算法，在较多的迭代次数后才能得到一个当前最优解，效率比较低。许多学者尝试对LEACH-C协议进行改进。文献[4]采用遗传算法代替模拟退火算法选取簇头方案，提出了一种染色体的表达方法，基于能量测度并根据问题特征确定合适的适应度函数，将提出的2个新的适应度函数应用于四种不同类型传感器网络，但是改进算法在节省能量和延长网络生命周期方面并不是很明显。文献[5]用模拟退火算法收敛后的局部最优解代替初始解进行后续的迭代工作，尝试提高搜索速度，而且在理论上证明了改进的可行性，但是算法的缺陷是算法执行的效果对初始解的依赖程度很大。在文献[6]中采用图像角点检测算子SUSAN算法代替模拟退火算法选取簇头方案，同时通过利用最小生成树原理，将所选出的簇头节点生成最小能耗树，试图减少网络能耗，但是该算法并未考虑簇头到基站距离的影响。本文采用近几年刚刚提出的群体寻优正弦余弦算法代替经典LEACH-C协议中的模拟退火算法进行集簇分层路由，实验结果表明，在相同的迭代次数情况下，用正弦余弦算法改进后，能提高监测区域网络中电源能量的利用率。

1 正弦余弦算法

正弦余弦算法(since cosine algorithm，SCA)，由S.Mirjalili在2016年提出，顾名思义，该算法利用正弦余弦数学函数来求解问题的最优解[7]。SCA不是模拟自然界某些现象而产生的算法，故其不要假设条件，易于实现。

假设种群规模为m，即包含m个个体，每个个体的维度为k，个体i在第j维的空间位置表示为Xij，i∈{1,2,…,m}，j∈{1,2,…,k}， 个体i第t+1次迭代后，在第j维的空间位置按公式(1)计算：

(1)

其中，Xij(t)为个体i在第t次迭代后第j维的位置分量，Xj*(t)为第t次迭代后所有种群当前最优个体在第j维的位置分量，r1、r2、r3和r44个参数中，最关键的是参数r1，r1，按公式(2)求得，r2∈[0,2π]、r3∈[0,2]和r4∈[0,1]为3个随机参数。

(2)

其中，t为当前的迭代次数，T为最大迭代次数，a一般取2，r1随着t的增加逐渐递减，从2递减到0。

SCA算法中，r2是0到2π之间的1个随机数，所以可知当r1>1时，正弦函数r1sin(r2)值或者余弦函数r1cos(r2)值才有可能大于1或者小于-1，此时算法可以在大范围空间内进行探索，搜索更多的解的可能；当r1≤1时，正弦函数r1sin(r2)值或者余弦函数r1cos(r2)值必定介于-1到1之间，算法在局部寻找最优解[8]，如图1所示。

图1 正弦余弦算法下一位置示意

在SCA算法中，在一个迭代周期T里，随着迭代次数的增加，正弦函数r1sin(r2)的值或者余弦函数r1cos(r2)的值也逐渐递减，如图2所示，可以看到正弦或余弦函数的振幅在逐渐递减。当振幅较大时，算法可以在一个大的空间中进行变化，寻找解的可能性；当振幅逐渐减小时，算法逐渐收敛，解也逐渐收敛[9]。

图2 正弦和余弦范围的递减模式

2 基于正弦余弦算法的LEACH-C协议的改进

在LEACH-C协议中，用正弦余弦算法SCA代替原来的模拟退火算法SA选举当前最优簇头方案，尽可能高效利用电源能量并延长网络生命周期。

2.1 网络模型

1)基站位于网络中心，一旦部署不再变动，而且假设基站的能量不受限[10]。

2)随机部署传感器节点，假设其在网络中是随机均匀部署的，一经部署位置固定。

3)假设传感器节点携带的原始能量相同，且后期不再补充。

4)假设网络中的传感器节点均能够与基站通信。

2.2 能量消耗模型

在改进协议中，发送端消耗的能量如公式(3)：

(3)

接收端消耗的能量如公式(4)：

ERx(l)=lEelec

(4)

簇头数据融合消耗的能量如公式(5)：

EFx(n,l)=nlEDA

(5)

其中，n为簇内节点总数，l代表簇内成员节点向簇头传输的数据量，EDA=5nJ/bit/signal，EDA为单位比特数据融合消耗的能量。

2.3 算法模型

采用集中式分簇路由，由基站进行每一轮的簇头选举和簇的划分。其中，簇头选举采用正弦余弦算法，使用簇内距离作为目标函数，成员节点选择距离最近的簇头成簇，选择目标函数最小的一个个体作为本轮的最终分簇方案。成员节点传输的数据在簇头节点进行本地融合后，再传输到基站，这样才完成本轮的数据传输。

1)初始种群生成

在每一轮中，首先基站计算所有传感器节点的平均能量，高于平均能量的节点构成这一轮的候选簇头集合。然后基站从候选簇头集合中随机选取这一轮的k个簇头组成一个个体，个体的维度等于k，每一个个体就是一种簇头方案，随机选取m次构成初始种群[13]。每一轮选择的簇头个数为k，按公式(6)计算：

k=round(Nalive·p)

(6)

网络中规定，如果网络中节点携带的原始能量消耗完时，节点被看作死亡。式(6)中Nalive为目前网络中存活的传感器节点个数，p是节点被选为簇头的概率，二者相乘按四舍五入取整。

2)目标函数

对于初始种群中的每一种簇头方案，基站计算普通成员节点与对应簇头的距离，选择距离最近的簇头成簇。从公式(3)可知，能量消耗与距离成指数关系，而且基站位于网络中心，所以以普通成员节点与对应簇头之间的簇内距离构建目标函数，按公式(7)和(8)计算，其中dtoCH代表普通成员节点与对应簇头节点之间的簇内距离。

(7)

(8)

3)位置更新

选择目标函数值最小的一种簇头方案保存下来，根据公式(1)进行群体位置的更新。更新后，对于位置越界的节点，选择迭代之前的对应最优值作为本次的更新值；对于更新后不在候选簇头集合中的节点，在候选簇头集合中选择距离其最近的一个节点作为本次的更新值；若更新后因重复导致簇头个数不足k个，则在候选簇头集合中随机选取不重复的节点补充到k个。

3 实验仿真与分析

实验在Intel core i7 CPU，16 G内存，3.6 GHz主频的计算机上，采用MATLAB R2010b对经典的LEACH-C协议和改进后的协议进行编程仿真。

3.1 仿真参数设置

为了便于改进协议和LEACH-C协议进行比较，将仿真参数设置如下：

①区域规模：200 m*200 m。

②传感器节点总数N：200个。

③区域节点携带的原始能量：0.5 J。

④基站x=100 m，y=100 m。

⑤数据量大小l：4000 bit。

⑥簇头当选概率p：0.05。

⑦SCA算法中，种群m=15，最大迭代次数T=20。

⑧SA算法中马尔科夫链长度Len=15，初始温度Temperature=100，温度每次下降控制Temperature*0.5，退出条件Temperature≤0.0001。

⑨其他常数：Eelec:50 nJ/bit;∈fs:10 pJ/bit/m2;∈mp:0.0013 pJ/bit/m4。

3.2 仿真结果与分析

图3和图4分别是两种协议出现30%死亡节点时的节点分布图。从图中可以看出，运行经典LEACH-C协议的网络，死亡节点相对比较集中，集中在某一侧；而图4中运行改进协议的网络中，死亡节点分布相对比较均匀。这是由于正弦余弦算法选举出的簇头方案在节约传感器节点能耗和均能传感器节点间能耗方面更优，使得死亡节点的分布相对比较均匀。

图3 LEACH-C协议有30%节点死亡的节点分布 图4 改进协议有30%节点死亡的节点分布

图5是运行两种协议的网络各轮生存节点对比图，可以看出，改进后的协议中第一个死亡节点时间比经典的LEACH-C协议推后了500多轮，延长了整个网络的生命周期。另外还可以发现，改进协议在第一个死亡节点出现以后，其他节点也相继快速死亡，呈直线下降趋势，说明节点间能量的消耗比较均衡。

图5 两种协议各轮生存节点对比

从表1可以看出，改进协议中第1个死亡节点出现的轮数比LEACH-C协议推后了542轮，20%死亡节点、50%死亡节点、80%的死亡节点出现的时间比LEACH-C协议都推后了；而且改进协议的网络，从出现第1个死亡节点，到80%的节点死亡仅仅用了19轮，说明改进协议比LEACH-C协议能更均衡和高效地利用网络中的电源能量。

表1 两种协议出现相同比例死亡节点时轮数对照表

图6显示了运行LEACH-C协议的网络出现死亡节点后，两种协议累计发送数据包的对比情况。可以看出，改进协议发送数据包的量明显高于LEACH-C，是因为LEACH-C协议中的死亡节点出现较早，节点死亡了便不再发送数据包，而改进协议的死亡节点出现较晚。出现死亡节点前，两种协议的所有节点均能发送数据，发送数据包的量相同。由于运行两种协议的网络初始总能量相同，改进协议比LEACH-C协议发送的总数据包要多，不难得出，改进协议发送单位数据包所消耗的能量要低于LEACH-C协议。所以，在能量的利用率方面改进协议表现更优。

图6 出现死亡节点后两种协议发送数据对比 图7 两种协议各轮累计消耗能量对比

图7是运行两种协议的网络各轮累计消耗能量对比图。图7中改进后的协议在整个网络生命周期内，能量消耗均低于LEACH-C，运行LEACH-C协议的网络节点全部死亡时间比改进协议要早。运行LEACH-C协议的网络能量消耗殆尽时，改进协议还在继续工作。

4 结 论

在传感器网络中，对网络生命周期的影响最重要的2个要素是能量和距离，在改进协议中优先考虑高能量节点构建候选簇头集合，对均衡传感器节点间的能量消耗起到了一定的作用；基站部署在网络中心，所以采用簇内距离构建目标函数，也是充分考虑到距离与能量消耗之间成指数关系。仿真实验结果表明，在相同迭代次数的情况下，正弦余弦算法比模拟退火算法表现更优，更能选举出合适的簇头方案，从而有效地均衡节点间的能量消耗，避免一些节点过早死亡，很好地延长了整个网络的生命周期。下一步工作将研究多跳SCA和链式SCA在更大规模网络分簇路由中的应用。