一种新的无线可充电传感器网络分簇算法

孙 伟，吴海青，高 萍

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

0 引言

在传统无线传感器网络(WSN)中，传感器节点通常由电池供电，但电池容量有限，且更换成本高。因此，能源供应不足严重限制了WSN的工作时间，是无线传感器网络中的一个重要问题[1]。为解决这个问题，在WSN中引入了无线充电技术，采用无线充电技术的传感器构成了无线可充电传感器网络(WRSN)[2]。相比较于利用环境能量供电，无线充电技术可以持续有效地提供能量，具有更大的潜能[3]。在WRSN中，移动充电小车可以移动，利用无线充电方式为大量传感器节点充电。当移动充电小车以随机方式运动时，当其运动至不需要充电传感器节点旁边时，此时若继续向该传感器节点供应能量，会导致传感器节点的能量冗余。与此同时，有一些传感器节点由于从移动充电车辆获得的能量较低或无移动充电小车对其供能，不能正常工作。因此，充电小车不合适的运动方式将导致能量浪费和能量的不足同时存在，即能效低下[4]。

由于传感器节点分布不均匀，节点传输功耗不是恒定的。此外，移动充电小车随机且冗长的行驶路径会导致充电效率降低[5]。这2个问题严重降低传感器网络的能量效率，从而降低了网络的生存期。为了提高WRSN的能量效率，许多工作采用了优化移动充电小车的充电路径或将传感器节点分簇的方法。

文献[6]中提出了移动充电小车的充电停留选择算法。在该算法中，将节点的平均接收功率定义为适应度函数，通过使用遗传算法最大化平均接收功率，找到优化的充电停留点集合。虽然该算法可以提高充电节点的利用率，但忽略了节点能量分布不均匀引起的问题。文献[7]中提出了基于低功耗自适应集簇分层协议(LEACH)来改进簇头节点选择。但是，该协议忽略了所选簇头的分布状态以及节点之间的不同通信距离，从而导致了节点能耗的不均衡。这种能耗不均衡的现象造成能量浪费，使得整个网络的寿命降低。文献[8]提出了Revised Earliest Deadline First(REDF)无线充电调度优化算法。该算法综合考虑充电期限和节点距离2个制约因素，从而延长无线传感器网络生命周期，建立一个稳定供应能量的无线传感器网络，但是该算法不适合大规模传感器网络。

为了克服当前算法的不足，在LEACH算计的基础上，提出了一种改进的分簇算法。在选择簇首期间，考虑节点的剩余能量和相邻簇首之间的距离，从而可以避免选择具有较少剩余能量的节点作为簇首，并且簇头可以均匀分布。该算法可以延长节点的生存时间，提高网络的能量效率。

1 LEACH协议

LEACH协议是无线传感器网络一个重要的分簇路由协议[9]，该协议采用LEACH算法，以循环方式随机选择簇头节点，并将整个网络的能量负载均匀分配到每个传感器节点，从而提高网络整体生存时间。与一般的平面多跳路由协议和静态分层算法相比，现有结果表明LEACH算法可以有效地延长网络生命周期。

运行LEACH协议的过程实际上是连续循环分簇的过程，每个集群重建可以称为一轮循环。一轮循环分为2个阶段：集群建立阶段和传输数据的稳定阶段。集群的建立又分为4个阶段：簇首节点的选择，簇首节点的广播，簇首节点的建立以及调度机制的生成。簇首节点选择的选择策略如下：传感器节点随机生成0到1之间的随机数，并将其与阈值T(n)进行比较。如果它小于阈值，则选择节点作为簇首。T(n)计算为:

(1)

式中，P代表成为簇首节点的概率，r为当前循环的轮数，G为在接近1/P轮中未当选簇首的节点的集合。

2 系统模型

本文考虑的是一个由n个传感器节点组成的无线传感器网络，如图1所示，网络由3部分组成：大量传感器节点、移动充电小车和基站。基站和移动充电小车位于检测区域外。检测区域内有大量的传感器节点，主要负责向基站收集、转发、存储和处理数据，传感器节点以单跳或多跳的方式将信息发送到基站。假设每个传感器节点具有有限且相同的初始能量，由于每个节点的业务负载和能量消耗速率不相同。基站和移动充电小车形成充电系统，主要负责传感器网络的能量供应。

图1 分簇式无线充电技术的系统模型

假设传感器节点服从高斯分布[10]，则每个簇里节点的分布可以用独立的高斯分布来描述，即簇首节点的概率密度函数为:

(2)

式中，m为该密度函数的特征矩阵，u为高斯分布的期望值，d为确定节点分布幅度的参数。期望u的计算公式为:

(3)

式中，Si为簇的区域面积，N为簇的数量。

3 传感器节点分簇算法

为了解决能量冗余，减少节点能量的不合理损失，提高网络服务质量，本文在LEACH算法的基础上，提出了一种适用于无线可充电传感器网络的改进分簇算法。该分簇算法选择簇首的基本原则是：考虑簇首选举中节点的剩余能量，尽量选择具有最大剩余能量的节点作为簇首节点；考虑簇首选举中相邻簇首之间的距离。算法的简单介绍如下。

首先，根据节点的剩余能量，利用LEACH算法选择剩余能量较多的节点作为簇首。其次，考虑相邻簇首之间的距离，如果簇首之间的距离小于由所提出的算法得到的距离阈值D，则簇首节点分布太密集，进而取消较低能量节点当选簇首的资格；否则，应适当增加簇首节点的数量，以确保簇首节点均匀分布在整个区域中。最后，簇首节点将在整个无线通信区域中广播，然后其他节点将通过就近原则加入簇首节点以形成簇，并通知相应的簇首完成簇建立过程。

簇形成之后，移动充电小车按顺序对各簇首进行充电。完成一轮充电后，充电小车返回基站，对自身进行充电。此时，簇内传感器节点将收集的数据发送给簇首节点。簇首节点对收集的数据进行数据融合，然后将信息发送到基站，基站进行数据处理，最后将处理后的数据发送给用户。工作一段时间或充电小车完成充电后，网络开始进行新一轮的分簇。

从上述描述中，可以发现所设计算法中的2个关键是：簇首的选择和距离阈值D的计算。

3.1 簇首选择算法

在LEACH算法中，阈值T(n)没有考虑节点的剩余能量，因此剩余能量较小的一些节点也会被选为簇头，由于簇头的能量消耗较快，从而会出现簇头因耗尽导致死亡，进而导致需要开始新一轮簇头选择，或由于节点死亡，网络无法正常工作。因此，在本文中，簇首的选择考虑节点的剩余能量。本文通过阈值的设置来直接滤除剩余能量过低的节点，阈值定义为:

(4)

式中，Enc为节点的当前能量，E为初始能量，rs为没有连续当选簇首的节点数量。一旦节点被选为簇首，则rs被设置为0，并且G是正常节点，不充当第一轮1/P中的簇首节点的集合。从式(4)可以看出，在其他参数不变的情况下，在r个循环后，当节点的剩余能量较大时，T(n)的值较大，节点被选为簇首节点的概率也更大；当节点的剩余能量越小时，T(n)的值越小，该节点被选为簇头首点的概率越小。

3.2 计算簇首之间的距离阈值D

距离阈值用于确定簇首的密度。如果D太小，则大量节点被选为簇首，这些簇首都需要充电小车来进行充电，可能会导致充电小车的能量不足，一些簇首可能无法及时被充电，从而没有足够的能量来为相应簇中的其他节点进行充电。相反，如果D具有较大的值，则表明相邻簇首之间的距离较大，即簇首的数量较少。这意味着每个簇内都有较多的传感器节点。由于传感器节点容量有限，在对每个簇首充电之后，移动充电小车可能仍然有一些能量，这些能量没有被充分使用。同时，由于簇内传感器节点太多，簇首没有足够的能量来为这些传感器节点充电。为了避免浪费和短缺，分2步来设置阈值D。

首先，通过考虑节点分布和感应区域，将簇首间的最优距离D定义为:

(5)

式中，Si和Sj为被测节点的簇区域，g(xj)和g(xi)为被测节点的概率密度函数。

利用式(5)计算出的D值，可以获得簇首的数量，由N1表示。根据移动充电小车的容量和传感器的电池尺寸，可以计算簇首数量N2：

(6)

式中，Cc为移动充电车的容量，Cs为传感器的电池尺寸，β为冗余因子，0.5<β<0.9。

如果N1

4 仿真结果

首先，比较了LEACH算法和本文所提出的分簇算法得到的簇首分布情况，如图2所示，其中黑色圆圈表示簇首节点，其他表示普通的传感器节点。比较图2(a)和图2(b)可以发现，与LEACH算法相比，本文设计的算法使簇首节点的分布更均匀。原因是所设计的分簇算法考虑了节点分布的密度和簇首之间的距离，可以避免由于簇首节点的损坏导致区域无法正常通信的问题，提高了网络的稳定性。

图2 节点分布

其次，比较了3种不同充电算法的网络剩余能量，结果如图3所示。在图3中，“ZC”是指移动充电小车直接对每个节点充电而没有运用任何分簇算法，“FCSF”是指使用LEACH算法来选择簇首节点，“N-FCSF”代表了本文提出的算法。结果表明，使用ZC充电技术的网络剩余能量和使用FCSF算法的网络剩余能量都比使用N-FCSF算法的剩余能量衰减得快。其中，ZC充电技术是网络剩余能量衰减时间最早的。因为ZC充电技术直接随机对整个网络中的每个节点充电，忽略了节点的剩余能量，并且由于无法及时充电，可能导致需要充电的节点过早死亡。另外，由于FCSF算法不对簇首节点进行筛选，剩余能量较少的节点当选簇首以后会加速死亡，大大降低了网络的能量效率。N-FCSF算法通过筛选簇首节点解决了网络节点分布不均匀的现象，有效降低了节点的能耗，延长了节点的生存时间，提高了网络的通信效率。

图3 剩余能量比较

图4比较了3种不同充电方法的节点存活数量。采用ZC充电方式的网络，节点从150 s开始死亡，所有节点在500 s后死亡。这是由于节点数量大，分布范围广，移动充电小车的自身耗能增加，可充电能量降低，充电周期延长，节点死亡次数增加。FCSF算法的节点从250 s死亡，所有节点在600 s后死亡。N-FCSF算法中，节点从500 s开始死亡，所有节点在650 s后死亡。这种结果表明N-FCSF算法延长了节点的生存时间，延长了网络的生命周期。原因是N-FCSF算法使簇首节点均匀分布，避免了每个节点与簇首之间距离引起的大量能量损失，并考虑了簇首节点选举时节点的剩余能量，避免了低剩余能量的节点作为簇首，提高了能量的效率。

图4 节点存活数量的比较

5 结束语

节点能量有限以及节点能耗的不平衡会导致“节点能量冗余”和“节点因能量耗尽而死亡”在网络中共存，为解决该问题，本文提出了一种适用于可充电传感器网络的分簇算法，该算法考虑了节点剩余能量和簇首之间的距离，充分地利用了移动充电小车的能量，改善了网络中能量的分布不平衡问题，提高了整个网络的能效，有效地延长了节点的生存时间和网络的生存期。