WSN中基于改进樽海鞘群算法的分簇路由协议

颜 清，刘 瑛，王国仕，张应斌

(1.海南电网有限责任公司 信息通信分公司，海口 570000；2.海南电网有限责任公司，海口 570000)

0 引言

随着智能化时代的到来，无线传感器网络(WSN，wireless sensor network)在越来越多的领域得到应用，例如无人驾驶、医疗领域、军事战场、智能仓储、环境监测等[1]。WSN包含成百上千个传感器节点，它们分布在指定区域中感知、评估和接受数据。这些传感器节点价格低廉，在感知、处理和传输数据信息方面具有较高的能力。传感器使用模拟数字转换器收集数据，并对数据进行处理，然后传输至基站。基站会对收集到的数据进行分析，为各种应用做出相应的决定。然而，WSN中传感器节点的能量有限且无法进行能量补充，因此提高能量利用率，延长网络生存期是WSN中亟待解决的问题[2-3]。在现有的路由协议中，基于分簇的层次路由被证明是平衡网络负载、延长网络生存期的有效技术[4-5]。层次路由通过将传感器节点分组，有效减少网络能量的消耗，提高网络的可扩展性，从而实现更长的网络寿命，提高WSN的性能。网络中的每个簇都有一个簇首，负责与网络中的其他簇通信。由于直接将传感数据传输到基站需要消耗较高的能量，因此在基于簇的WSN中使用路由协议来确定簇首与基站之间的最佳传输路线以减少能量消耗。路由协议的特点包括容错性、可靠性、信息积累、可扩展性等[6]。

经典的分簇路由协议LEACH[7]将网络节点进行分簇，并周期性轮换簇首，从而均衡网络能耗，延长网络生存期。但LEACH协议在选举簇首时没有考虑节点的剩余能量和位置信息，每个节点以相同的概率当选簇首。若剩余能量不足、地理位置不合理的节点当选簇首，将加速这部分节点的能量耗损，缩短网络生存期。此外，簇间通信阶段没有使用任何路由算法，降低了网络性能。为解决LEACH协议中存在的问题，研究人员采用群体智能算法解决最优簇首选举问题，并获得了理想的结果。文献[8]提出一种基于改进人工蜂群算法的分簇路由协议。首先对人工蜂群算法进行改进，提高了其全局搜索能力。然后使用改进的人工蜂群算法选择最优簇首，改善簇首质量。簇间通信阶段，构建了基于蚁群优化的路由算法，均衡了簇首节点的网络负载。文献[9]使用由遗传算法优化的K-Medoids聚类对网络节点分簇，并考虑节点的能量因素和地理位置选择最优簇首。仿真结果表明，所提协议有效延长了网络生存期。但该协议没有使用任何簇间路由，距离基站较远的簇首将产生大量的能耗而过早死亡。文献[10]首先使用粒子群算法优化模糊C均值聚类，以改善聚类效果。其次，使用改进的聚类算法对传感器网络分区，形成网络分簇。在每个簇内，考虑节点的剩余能量和位置因素动态更新簇首。数据传输阶段，提出一种基于猫群优化算法的路由技术，为簇首构建最优传输路径。对所提协议进行仿真，实验结果表明该协议优于LEACH协议和改进的LEACH协议。但所提协议在簇内通信阶段采用TDMA机制，容易导致时隙浪费，降低能量效率。文献[11]采用灰狼优化算法选择最优簇首集合，有效提高了网络了效率，延长了网络生存周期。但所提协议没有采用任何路由算法，簇首节点直接向基站发送数据将会产生大量的能量开销，使其过早死亡。文献[12]使用人工蜂群算法设计高效的分簇路由协议。在成簇阶段，首先考虑传感器节点当前剩余的能量、所处地理位置、成簇紧凑程度3种因素设计适应度函数，然后使用人工蜂群算法求解适应度函数，从而选出最优簇首集合。在稳定传输阶段，为降低节点的能量消耗，构建了基于转发代价的路由算法，确定节点到基站之间的传输路线，簇头按照规划好的路线以多跳方式将数据传送至基站。仿真实验证明，所提路由协议能够延长WSN的网络寿命，提高网络吞吐量。但基本人工蜂群算法易陷入局部最优，可能导致选出的簇首集合并非最优解，从而降低WSN性能。

针对上述协议数据传输过程中节点能量消耗大、对基站传输的总数据包数量小等问题，本文提出一种基于聚类的WSN节能路由协议。由于群体智能优化算法的搜索能力强、鲁棒性和较好的自适应性，本研究中主要使用群体智能优化算法解决最优聚类问题。首先对基本樽海鞘群算法进行改进，提出一种精英反向学习樽海鞘群算法，提高算法的全局搜索能力；其次根据节点的剩余能量和地理位置设计高效的适应度函数，并使用改进的樽海鞘群算法优化节点适应度函数，选出最优簇首集合。簇内通信阶段，设计一种基于最小生成树的路由算法，为簇首节点构建最优传输路径，在缓解簇首负载的同时最小化中继节点的能量消耗。最后，使用轮询控制机制为簇内成员节点构建数据传输调度，避免时隙浪费，进一步提高能量效率。

1 系统模型

1.1 网络模型

为方便后续工作的进行，本文考虑以下要素构建WSN模型[13]：

1)传感器节点具备全网唯一的ID号码，且随机分布在目标监测区域内。部署完成后节点的位置不再变动。

2)在WSN中，所有传感器节点同构。即所有传感器节点的初始能量和数据处理能力均相同。

3)传感器节点之间的距离根据欧氏距离公式进行计算。

4)基站接收关于传感器节点的剩余能量和距离信息。根据这些信息，通过使用既定的簇首选择算法为节点选择相应的簇首。路由算法则被用于规划簇首到基站之间的传输路径。

1.2 能耗模型

本文采用一阶无线电能耗模型来计算发射机和接受机的能量损耗[14]。WSN的能耗主要来自于传感器节点收发数据信息，节点发送kbit数据到距离自身为d的接收端所消耗的能量为：

(1)

ERx(m，d)=kEelec

(2)

ERx(k，d)=kEda

(3)

其中：Eda为节点融合每bit数据所需要的能量。

2 精英反向学习樽海鞘群算法

2.1 基本樽海鞘群算法

樽海鞘群算法(SSA，salp swarm algorithm)是Mirjalili等人受海洋生物樽海鞘的觅食和导航行为启发所提出的新型群体智能算法[15]。该算法具有控制参数少、易于实现、优化能力强等特点，已被成功应用于求解多个学科领域的优化问题[16]。

SSA中，位于樽海鞘链最前面的个体被定义为领导者，其余个体为跟随者。领导者的位置更新公式为：

(4)

其中：Fj为食物源在第j维搜索空间的位置；c2和c3为随机值，取值[0，1]之间；c1是控制领导者移动的重要参数，按照下式进行计算：

c1=2e-(4t/T)2

(5)

其中：t为当前迭代次数，T为最大迭代次数。

跟随者的位置更新方程为：

(6)

2.2 精英反向学习樽海鞘群算法

基本SSA算法具有较好的性能，能够有效解决全局优化问题。然而，基本SSA算法与其他群体智能算法类似，在搜索过程中存在全局勘探与局部开发不平衡、易收敛至局部最优的缺陷[17-18]。为解决基本SSA中存在的缺陷，本文提出一种精英反向学习的樽海鞘群算法(OSSA，opposition-based)。

2.2.1 反向学习

(7)

其中：aj和bj分别为搜索空间的上下限。

2.2.2 动态学习策略

基本SSA中，跟随者根据式(6)更新自身位置，该位置更新机制较为单一，缺少参数控制其移动方向和移动速度[16]。为解决这一问题，将领导者位置更新公式中的参数c1引入跟随者位置更新公式中，帮助控制跟随者的位置更新。改进的跟随者位置更新公式为：

(8)

根据式(8)可知，引入控制参数c1能够帮助跟随者实现有效跟随，帮助算法在全局搜索和局部勘探之间获得稳定的平衡，从而改进了基本SSA的整体性能。

2.3 OSSA算法步骤

所提OSSA算法步骤如下：

Step 1：设置算法参数：种群规模N、最大评估次数T、搜索空间上下限[ub，lb]；

Step 2：随机初始化种群，根据个体适应值将其分为领导者和跟随者；

Step 3：根据式(4)更新领导者位置，并执行OOBL，生成反向个体。根据适应值选择较优个体进入后续迭代。

复方阿胶浆生产原料包括红参、党参、熟地黄和山楂等，经过水提取后的药渣中除了含有较多的粗纤维外，还包括复杂多样的蛋白质、氨基酸、微量元素及残留的活性成分等多种物质。

Step 4：根据式(8)更新跟随者位置；

Step 5：评价种群适应值，将最优个体指定为当前食物源；

Step 6：判断是否达到最大评估次数，若达到，输出食物源位置，否则返回Step 3继续迭代。

3 基于OSSA的分簇路由协议

本节对所提出的基于OSSA的分簇路由协议进行详细介绍。网络运行初期，首先采用OSSA算法选择最优簇首集合，成员节点选择距离最近的簇首入簇，至此成簇阶段结束。数据传输阶段，构造最小生成树，为簇首节点寻找中继，簇首沿最优传输路径以多跳方式将数据分簇发往基站。簇内通信阶段，采用轮询控制机制帮助成员节点完成数据传输。

3.1 成簇阶段

成簇阶段，使用OSSA算法选择最优簇首集合，普通成员就近入簇，形成网络分簇。簇首选举时，OSSA中的每个个体代表一种聚类结果，个体适应值反映当前聚类效果，最终输出的食物源即为最优聚类。在进化过程中，OSSA迭代的准则为最优化适应度函数。因此，设计高效的适应度函数对于选择最优簇首具有重要意义。本文综合考虑节点的能量因素和地理位置，设计了新颖的适应度函数，用于评价OSSA生成的解的质量。

3.1.1 能量因子

在WSN中，簇首执行多项任务，包括收集普通节点的数据、与基站通信等。簇首需要较高的能量来完成这些任务，因此，需要选择剩余能量充足的节点担任簇首，以此延长网络生存期。本文将能量因子定义为当前簇首集合的总能量与网络总能量的比值，按照下式进行计算：

(9)

其中：k和n分别表示簇首数量和网络节点总数；Ech(i)和Ecm(j)分别表示簇首i和成员j的剩余能量。由能量因子表达式可以看出，当前簇首节点集合剩余总能量越多，f1越大，代表当前簇首集越优。

3.1.2 位置因子

选取簇首时，分散簇首在网络中的位置能够帮助网络分簇更加均匀，从而均衡簇间负载。本文将簇首的位置因子定义为基站到网络中心的距离与簇首到基站平均距离的比值，按照下式进行计算：

(10)

其中：d(center，BS)和d(CHi，BS)分别为基站到网络中心的距离和簇首到基站的平均距离。由位置因子表达式可以看出，簇首集合到基站的平均距离越短，簇首的通信距离也越短，此时f2较大，代表当前簇首集越优。

适应度函数值是评价当前簇首集合质量的基准，本文通过加权方式将能量因子和位置因子转换为OSSA算法的适应度函数。簇首集合的剩余能量越高，距离基站越近，适应度函数值越优。其计算方式如下：

fitness=αf1+(1-α)f2

(11)

其中：α为调节两个因子重要程度的权重系数。随网络运行，节点的剩余能量越来越少，选择簇首时节点能量因素的重要程度相应增加，因此，α应随网络运行动态变大。其计算方式如下：

(12)

其中：Econ和Etotal分别表示网络节点消耗的总能量和网络的初始总能量。根据上式可知，节点消耗的能量越多，则α越大，节点的能量因子的重要程度也就越大，最优适应度值所对应的簇首集剩余总能量越多。初始阶段，α取值1/2。

簇首选举完成之后，当前簇首广播自身成为簇首的消息，其余节点根据接收到的信号强度估算自身到每个簇首的距离，并加入最近的簇首形成分簇，完成簇的构建。

3.2 簇间路由

簇首选举完成后，网络进入稳定传输阶段。在该阶段，簇首将收集到的数据包发送给基站。根据能耗模型可知，节点的能耗与通信距离呈指数相关[20]。因此，缩短通信距离能够有效降低簇首节点的能量消耗。本文提出一种基于最小生成树的簇间路由算法，帮助簇首构建最优传输路径，以此降低簇首能耗，均衡网络节点的负载。

簇首收集簇内信息后，按照式(13)计算各邻居簇首的转发代价值，并选择具有最小转发代价的簇首作为下一跳。

(13)

3.3 基于轮询控制的簇内通信机制

现有的分簇路由协议中，在簇构建完成后，簇首节点构建TDMA调度，成员节点根据调度表中的信息，在自己的时隙内与簇首通信，其余时间则休眠，以降低能量耗损。这种机制有效降低了节点的能量损耗。然而，根据该机制，如果节点在自己的时隙到来时没有数据需要发送，该节点仍要被唤醒，这就给节点带来了不必要的能耗。为解决这一问题，本文引入轮询控制机制[21]。在选出簇首节点后，成员节点加入距离最近的簇首。簇首节点根据簇内成员节点的信息构建轮询调度。轮询表中记录了节点的工作次序和对应的节点ID。其中，没有数据需要发送的节点会被移出轮询表，仅保留在当前轮次需要与簇首进行通信的节点。通过这种方式，节点仅在有数据需要发送的轮询周期才会被唤醒，其余时间则处于休眠状态，从而有效地避免了节点被不必要的唤醒，进而降低了节点的能量损耗。

4 实验结果与分析

4.1 参数设置

为验证本文所提协议的有效性，使用Matlab R2014b软件对其进行仿真实验，并与灰狼优化算法[11]和遗传算法[14]两种基于群体智能算法的路由协议进行对比。为测试所提协议的可扩展性，本文考虑基站位置、网络规模和网络节点数设置了两种不同的场景对协议进行仿真。场景参数如表1所示，仿真参数如表2所示。OSSA算法的参数设置为：种群规模为30，最大迭代次数T为200[22]。

表1 网络场景参数

表2 实验参数

4.2 网络中首个节点的死亡时间对比

无线传感网是由多个传感器节点通过自组网的形式组成的网络，所有节点协同工作，负责收集监测区域内的数据信息。当所有网络节点均能正常工作时，监测区域内的信息会被完整的采集，一旦有节点死亡，就可能出现监测盲区，使监测到的数据不全面。因此，网络中首个节点的死亡时间是评价协议性能的重要指标。根据实验结果，在部署100个节点的小规模应用场景下，灰狼优化算法、遗传算法和本文协议的首个网络节点死亡时间分别为56轮、89轮、258轮；当WSN中部署200个节点时，灰狼优化算法、遗传算法和本文协议的首个网络节点死亡时间分别为56轮、89轮、231轮；当WSN中部署300个节点时，灰狼优化算法、遗传算法和本文协议的首个网络节点死亡时间分别为73轮、129轮、285轮。为直观反映3种协议在小规模监测区域内的首个网络节点死亡时间对比，将稳定期绘制于图1。从图中可以看出，相比于其他两种协议，本文协议能够有效延长首个节点的死亡时间。这是因为所提出的基于OSSA的簇首选取方法能够通过迭代优化选出最优簇首集合，从而优化聚类效果，将网络能耗均衡给更多的节点。场景2规模较大，节点的通信距离相对较远，通信产生的能耗也更大。在该场景中，3种协议的首个网络节点死亡时间如图2所示，分别为7轮、8轮、31轮。根据图2，3种协议首个节点的死亡时间都随着监测场景的扩展而变短。然而，与两种对比算法相比，本文协议能够有效延长首个网络节点的死亡时间，这是因为该协议在通信阶段使用了高效的路由算法，帮助簇首寻找合理的传输路径，避免了簇首直接与基站通信，从而缓解了其能量耗损。

图1 场景1网络稳定期对比

图2 场景2网络稳定期对比

4.3 网络生存周期对比

WSN的覆盖范围会随着节点的死亡不断降低，死亡节点过多会导致网络瘫痪，残余节点采集到的数据也不再有价值，此时认为网络失效。因此，本文将网络中有75%的节点死亡的时间定义为网络生存周期，用来评价协议的性能。在部署100个节点的小规模监测场景中，灰狼优化算法、遗传算法和本文协议的网络生存期分别为457轮、579轮、1 033轮；部署200个节点时，灰狼优化算法、遗传算法和本文协议的网络生存期分别为538轮、827轮、1 046轮；部署300节点时，灰狼优化算法、遗传算法和本文协议的网络生存期分别为550轮、866轮、1 133轮。为直观反映本文协议在网络生存周期指标上的优势，将3种协议的网络生存周期绘制于图3。从图中可以看出，本文所提协议的网络生存周期远长于对比协议，这得益于理想的分簇结果和高效的簇间路由。3种协议在大规模场景中的网络生存周期分别为257轮、396轮、698轮，如图4所示。从图4可以看出，随着网络规模的增大，3种协议的网络生存期均明显缩短。但本文协议的网络生存期仍远长于其他两种协议。这是因为在大规模场景中，簇首节点距离基站较远，路由算法在簇间通信阶段发挥着重要的作用。本文协议综合考虑邻居簇首的能量因素和地理位置构建了高效的簇间路由，簇首通过多跳方式将数据发往基站，有效降低了网络能耗，使网络能够工作更长的时间。

图3 场景1网络生存期对比

图4 场景2网络生存期对比

4.4 基站接收到的数据包总量对比

在监测区域内部署WSN的目的是采集数据信息，以了解目标区域的情况。当区域内出现危险信号，相关人员能够根据现场情况做出即时动作。因此，基站接收到的数据分组总数是评价协议性能的重要指标。本文将基站接收到的数据包总量定义为网络吞吐量。图5为3种协议在小规模场景下的网络吞吐量对比。从图中可以看出，本文协议在该指标上具有较大优势，这代表着基站接收到的数据包总数更多，对监测区域的了解也更加全面。图6为大规模场景下3种协议的网络吞吐量对比。根据图6，本文协议在该指标上有明显优于对比协议，这是因为较长的网络生存期使基站接收到了更多的数据分组。此外，簇内使用的轮询调度能够避免时隙浪费，进一步提高了本文协议的网络吞吐量。

图5 场景1网络吞吐量对比

图6 场景2网络吞吐量对比

5 结束语

为提高WSN的整体性能，，本文提出一种基于改进樽海鞘群算法的层次路由协议，该协议分别在成簇阶段和稳定传输阶段进行了优化。在成簇阶段，提出一种精英反向学习SSA算法，稳固基本SSA算法全局勘探与局部开发之间的平衡，增强算法的全局搜索能力，并将节点的剩余能量和地理位置引入精英反向学习SSA算法理论，使簇首剩余能量充足且分布均匀，均衡簇内负载的同时最小化通信距离。在稳定传输阶段，构建基于最小生成树的簇间路由，为簇首规划最优传输路径，均衡网络负载。簇内通信阶段，使用轮询调度构建簇内通信，避免节点被不必要的唤醒，进一步提高能量效率。最后，考虑节点数量、网络覆盖面积和基站的位置3种因素设置不同的应用场景对所提协议进行仿真测试，并与最新的基于群体智能算法的层次路由协议进行对比。实验结果表明，相比于对比协议，所提协议在网络稳定期、网络生存期和网络吞吐量指标上均有明显优势。