一种基于非均匀分簇的实时充电算法∗

尹 玲谢志军陈科伟

(宁波大学信息科学与工程学院，浙江 宁波315211)

无线传感器网络(Wireless Sensor Networks，WSNs)作为当今世界获取信息的重要途径之一，由自主分布在空间内若干个固定位置的传感器节点组成。 随着数据量的提升，节点有限的电池容量已不足以支撑WSNs 的长久运行。 因此，各种能量补充技术应运而生，越来越多的学者加入了对无线可充电传感器网络( Wireless Rechargeable Sensor Networks，WRSNs)的研究。

有学者提出从环境中获取能量，如把风能、太阳能和热能等转化为节点可用的电能[1-3]，但此类能量的获取过程不受人为控制，难以保证能量收集的效率和时效性。 近几年兴起的无线充电技术以其充电效率高、充电过程可预测等优势，成为了研究的热点，其中移动充电方式更加适合本文的研究背景——具有实时性要求的WRSNs，此类网络由能量有限的移动充电器(Mobile Charger，MC)负责为节点补充能量，如若补充不及时节点便陷入休眠，从而影响WRSNs 的性能。 因此，合理规划MC 的充电路径，选择合适的充电顺序和充电时间，对于延长网络的生命周期至关重要。

考虑到充电成本，目前关于移动充电的研究大部分采用单MC 的方式，以较小的充电代价达到较大的网络效用。 文献[4]在给节点定期充电的基础上，设计了混合粒子群优化遗传算法来解决周期性充电的问题；文献[5]设计了一种能量平衡的联合路由和充电框架，分别针对路由树和充电路径提出相应的优化算法。 为提高充电效率，文献[6-7]采取了定向充电的方式，其中文献[6]研究了最小充电延迟问题，设计了一种充电功率离散化方法来实现定向充电并减小充电延迟；文献[7]则设计了一种近似算法来确定充电对接点及充电方向，同时最小化定向充电车对接点的数量并最大化充电覆盖范围。 以上研究的重点在于预先规划好一条最佳路径，以保证较高的节点存活率和充电效率，适用于静态路由。

对于复杂可变的WRSNs 来说，按需充电则更加合适。 文献[8]按需确定节点的最佳充电顺序，设计了针对MC 调度问题的线性规划模型，并提出基于引力搜索算法(Gravitational Search Algorithm，GSA)的解决方案；文献[9]提出一种基于模糊逻辑的按需充电调度方案:只给能耗高的节点充电，通过共同衡量剩余能量，到MC 的距离和关键节点密度等网络参数来决策MC 的充电路径；类似地，文献[10]根据节点到基站的距离和能耗率把WRSNs 中的节点分成两类并采用不同的充电策略，对于距离基站距离近且能耗高的节点采用一对一充电，相反距离基站距离远且能耗低的节点采用一对多充电，通过研究节点的充电时隙提出最小移动成本算法(minimum travel cost algorithm，MTC)。

大型WRSNs 还可以使用多个MC 协同充电，文献[11]首次针对最长延迟最小化问题，设计了一种具有恒定近似比的近似算法；文献[12]建立数学模型以量化节点的充电条件与具有不同电池容量的MC 的可达性条件之间的关系；考虑到MC 的造价昂贵和协调多个MC 工作的复杂性，文献[13]研究了最小化MC 数量的问题。

在现有关于WRSNs 充电规划的研究中，大多在于根据能量、距离和时延等网络因素预先规划MC的充电路径，在静态网络中表现良好。 但对于动态变化的WRSNs 来说，节点的能耗差异大，且实际网络中的不稳定因素多，动态的充电决策更有优势。本文为合理规划具有实时性要求的WRSNs 中MC的充电路径，提出一种基于非均匀分簇的实时充电算法(nUCRC)，首先将网络作非均匀分簇处理，根据节点的能量状态和截止充电时间决定簇头的选举与轮换，在每个充电周期内MC 依照最短移动路径原则依次访问各个簇中心，并根据簇内节点的时间和空间特征有序选择节点进行充电。 文章的主要创新点总结如下:①为提高基站的管理效率，将网络作非均匀分簇处理，并根据节点的剩余能量和截止充电时间共同决策簇头的选举和轮换；②使用动态规划算法(Dynamic Programming，DP)决策MC 的最短移动路径，并根据簇内节点的截止充电时间和到MC 距离的混合优先级决定簇内节点的充电顺序。

文章的其余部分安排如下:第1 节介绍了具有实时性要求的WRSNs 模型；第2 节详细描述了所提的基于非均匀分簇的实时充电算法(nUCRC)；第3节给出了仿真实验与结果分析；最后在第4 节总结了本文并指出未来研究方向。

1 网络模型

本节首先介绍了WRSNs 的模型，并给出问题描述与解决方案。

1.1 问题描述

图1 所示的WRSNs 中随机分布了若干个具有唯一ID 且位置固定的能量有限的无线可充电传感器节点，负责监测网络环境并收集数据，并将收集的数据交由该簇的簇头节点，簇头节点则以多跳的形式将从簇内普通节点汇聚的数据传送给基站，簇头节点承担汇集该簇内数据并转发至BS 的工作，能耗高且重要；一个MC 在每个周期内携带有限的能量从基站出发，负责为网络范围内的节点充电；一个能量不限且位置固定的基站(Base Station，BS)负责汇聚簇头节点收集的数据，并为MC 规划充电路径；MC 能够准确定位节点和BS，从而完成充电任务并返回BS 进行充电维护。 BS 需要按照一定的规则规划MC 的充电路径，既要优先为能耗大的节点充电，以保证最高的节点存活率，还要尽可能减少MC 的移动路径长度，保证尽可能低的充电时延。

图1 采用nUCRC 算法的WRSNs 模型

1.2 解决方案

为解决上述问题，本文设计的目标是在单个充电周期T内，MC 的移动路径最短、节点存活率δ最高:

式中:d(i，V)表示MC 移动总路径，Nlive是存活节点数，N为节点总数。

考虑到MC 携带的能量要大于为节点充电耗费的能量，并在一个充电周期T内完成为节点充电和返回BS 处进行充电维护，有如下能量约束和时间约束:

式中:T0是MC 自身充满电需要的时间，si是节点Si开始充电的时间，ti是节点Si结束充电的时间，Pr是MC 从BS 收集能量的速率，Pc是节点从MC 收集能量的速率，Em是MC 的移动耗能，eMC表示MC 的剩余能量，Tm则表示MC 的移动时间，T是MC 的充电周期。

为实现所提目标并满足约束条件，本文设计了一种基于非均匀分簇的实时充电算法(Real-time Charging algorithm based on non-Uniform Clustering，nUCRC):首先将网络做非均匀分簇处理，分簇完成后，通过衡量簇内节点的剩余能量以及截止充电时间选举簇头，在每个充电周期内，MC 按照最短移动路径依次访问各个簇中心，根据节点的时空特征选择要充电的节点以及充电顺序，并在靠近BS 的时候返回BS进行充电，然后继续按照原定路线访问剩下的簇，遍历完所有簇后返回BS 进行充电维护并结束当前充电周期，待充电维护结束开始下一充电周期。 以下的部分详细描述了所述的nUCRC 算法。

2 非均匀分簇的实时充电算法

nUCRC 算法分为两步实现以上目标:非均匀分簇和充电路径规划。

2.1 非均匀分簇

分簇有利于提升BS 的管理能力，使网络更加高效、有序地运行。 对于含有单个MC 的WRSNs 来说，假设共有N个节点需要分为K个簇，各节点距离BS 的距离、能耗率都不一样，由于MC 在一个充电周期内可能会多次返回BS 处进行充电维护，因此靠近BS 的节点被充电的机会更大，为均衡网络中节点被充电的机会，使靠近BS 的簇内节点数量更多，降低靠近BS 节点的被充电机会，提升远离BS的节点被充电的机会。 所以本文采用非均匀分簇的方法，使得距离BS 近的簇半径大、包含的节点数量多，而距离BS 远的簇半径小、包含的节点数量少。

2.1.1 簇半径的计算

网络运行初期，N个节点分别计算其到BS 的欧式距离di:

式中:xi(1≤i≤N)表示节点Si的位置，xBS表示BS的位置。 根据计算得到的di值决定该节点Si拟加入的簇半径大小Ri，并且Ri的值与di值成反相关关系。 BS 收到N个节点的di后，分别计算以这N个节点为中心的簇半径:

式中:ε表示预期的最小簇半径与最大簇半径的比值，当ε＝0 时表示此时网络采用均匀分簇，取ε＝0.5；dmax是节点距离BS 的最大值；dmin是节点距离BS 的最小值；R0表示候选簇头节点最小簇半径值。

2.1.2 簇头节点的选举

为减少传送到BS 的数据量，由簇头节点负责收集来自该簇内普通节点所产生的数据，进行数据融合后经过多跳的形式转发给BS(即距离BS 远的簇头节点汇集的数据将转发给距离BS 近的簇头节点，让其转交给BS)，其能耗要高于普通节点，因此簇头节点的选举对于WRSNs 的长久运行至关重要。开始时各节点竞选簇头的概率ρi＝ρ＝1/N，根据式(4)计算出的簇半径，当某个节点当选簇头后，处于其簇半径内的其他节点就退出簇头竞选，而成为该簇内的普通节点。 首先，各节点在网络范围内广播竞争消息，广播的消息包括:节点的唯一IDSi、与BS的距离di、簇半径Ri、当前剩余能量ei和能耗率qi，首轮选择K个节点当选簇头，原则如下:

①当前剩余能量ei最高；

②截止充电时间Di最大:

由于当前剩余能量最高的节点不一定是存活最久的节点，还需要考虑节点的能耗率，即计算节点的截止充电时间，当截止充电时间到期后节点还没充上电，该节点就陷入休眠，因此应当按照剩余能量和截止充电时间的混合优先级决定簇头的选举:

式中:α和β表示加权因子，用来衡量能量因素和时间因素影响簇头选举的程度，取α＝β＝0.5，表示由节点的剩余能量和截止充电时间公平选举簇头；ρi值越大表示节点Si当选簇头的概率越大，选举ρi最大的值当选簇头，当两个节点的ρi值相等且处于对方的簇半径内时，节点ID 小的当选簇头，而另外一个节点成为该簇内普通节点。

首轮K个簇头节点选举出后，每个簇头节点需要维护一个簇内节点的集合:

图2 非均匀分簇流程图

2.2 MC 充电路径规划

确定了非均匀的成簇方法以及簇头节点的选择，还需要确定MC 的簇间移动路径及簇内节点的充电顺序，确保最短的移动路径长度，使得每个充电周期内能量有限的MC 能将更多的能量用于给节点充电，并尽可能降低充电时延，保证充电的时效性。本文分别从最短路径规划和充电顺序选择来实现以上目标。

2.2.1 簇间移动路径规划

为确保最短的移动路径，使得单个充电周期内MC 从BS 出发，遍历所有簇，且每个簇只经过一次，充电周期结束再回到BS，整个回路总路径长度最小，这是典型的旅行商(TSP)问题。 对于本文单个MC 的情况，分簇个数不会太多，因此采用DP 算法来解决最短路径问题。

根据2.1 节中构建的簇，计算每个簇的簇中心

式中:｜Ck｜表示簇Ck内含有的节点数，dCsk-1，Csk表示任意两个簇中心的欧式距离，V表示簇中心的集合:

令d(i，V)表示从源点BS 出发，经过中各个顶点i一次且仅一次，最后回到BS 的路径长度:

上式表示当集合V为空时，di，BS表示直接返回BS，而当V不为空时，整体路径最短问题就转换为部分路径最短问题的最优求解。

MC 移动总耗能Em和移动时间Tm分别计算如下，其中，f是MC 以速度v移动d的距离所耗费的能量:

MC 在移动过程中靠近BS 时，会返回BS 进行充电维护，维护完毕会按既定路线继续完成充电任务，当遍历所有簇后返回BS 处，完成一次充电周期。

2.2.2 簇内节点充电顺序选择

当MC 移动到簇Ck的中心时，选取簇内能量低于电池容量50%的节点进行充电，避免了全充造成较大的充电时延。 无线能量传输采用改进的适用于WRSNs 的Friis 能量传输模型[14]:

式中:PC是簇中节点从MC 接收能量的功率，P0是MC 的发射功率；Gs和Gr分别是MC 的发射天线增益和节点的接收天线增益；η是整流器的效率；λ表示波长；d是MC 与被充电节点的充电距离；Lp表示极化损耗；γ是调整Frris 自由空间方程用于短距离传输的参数。

给单个节点Si的充电持续时间TC(Si)由节点当前剩余能量ei、节点电池总容量EN以及能量传输模型(12)共同决定:

MC 给节点Si充电耗费的能量则由充电时间和充电耗能共同决定:

对于选取的待充电节点，通过考虑该簇内节点的截止充电时间和距离MC 的距离共同决策充电顺序，由时间优先级和空间优先级共同定义混合优先级，按照混合优先级从高到低的次序依次为选取的节点充电。

定义簇头节点SCkH的截止充电时间为DCkH，最小的节点截止充电时间为，最大的节点截止充电时间为，得到时间优先级为:

同样定义dCkH是簇头节点到MC 的距离，距离MC 最近的节点的距离为，距离MC 最远的节点的距离为，得到空间优先级为:

将时间优先级和空间优先级结合得到混合优先级如下:

式中:α和β表示加权因子，与式(6)类似，此处的α和β是衡量时间和空间对于MC 充电顺序的权重，加入对数项是为了防止出现重复的混合优先级值。对于簇内所有ei≤EN×50%的节点，计算其混合优先级的值φ(m)(i)，值越小的节点具有更高的优先级，享有优先充电的权利。 当簇内所有符合条件的待充电节点完全充电后，该簇进行簇头轮换，重新计算簇内所有节点的ρi值，最大的当选新一任簇头。

图3 给出了待充电簇内有6 个符合充电条件节点的例子，由式(13)可知，由节点的开始充电时间si和充电完成时间ti可得到节点的充电持续时间，由于MC 同一时刻只能给一个节点充电，计算待充电节点的混合优先级并排序，按混合优先级从高到低依次给节点充电。 MC 在簇内的移动时间相对于充电时间可忽略不计。

图3 MC 根据优先级按序为簇内节点充电

非均匀分簇的实时充电算法(nUCRC)工作流程如图4 所示。

图4 nUCRC 算法工作流程图

3 实验仿真与结果分析

3.1 参数设置

本文在Pycharm 平台采用Python 语言仿真所提的nUCRC 算法，并将结果与当前最新的相关研究工作进行了比较。 在大小为100 m×100 m 的WRSNs 区域内，随机布置了100 个位置固定的无线可充电传感器节点，一个能量不限的BS 以及一个能量有限的MC，MC在每个充电周期内遍历所有簇，并为簇内需要充电的节点按序充电，实验参数的设置如表1 所示。

表1 实验参数设置

实验分别将本文所提nUCRC 算法与文献[8]所提的GSA 算法以及文献[10]提出的MTC 算法作性能对比，分别从节点存活率和平均充电时延方面进行了对比分析，同时还研究了网络规模对nUCRC算法性能的影响。

3.2 仿真结果分析

3.2.1 节点存活率对比

首先对比了几种算法的节点存活率，图5 描述了程序运行500 min 期间节点存活率的变化情况。可见在前200 min 采用三种算法的节点存活率都为100%，程序运行到250 min 时，采用GSA 算法的节点存活率明显下降；当程序运行到500 min 时，GSA算法的节点存活率已经下降到90%以下，MTC 算法的节点存活率下降较为缓慢，约为95%，而nUCRC算法由于事先采用了非均匀的分簇方法，且在选择节点进行充电的时候采用了时间和空间的混合优先级，因此有更好的存活率表现，相较于其他两种算法，节点存活率分别提高约4%和10%。

图5 节点存活率对比

3.2.2 平均充电时延对比

图6 分别描述了MC 不同的移动速度和电池容量对平均充电时延的影响。 由(a)图可见随MC 移动速度增加，采用nUCRC 算法和MTC 算法的平均充电时延缓慢下降，这是因为nUCRC 算法采用了最短移动路径思想，所以总体充电时延低于MTC 算法；而采用GSA 算法的平均充电时延则随移动速度的增加先增大后减小，先小幅度的增大是由于随速度增加，待处理的充电节点数量增加，MC 往返众多节点之间，但随MC 速度的进一步提升，充电时延也随之下降。 (b)图描述的是平均充电时延随MC 电池容量的变化情况，当MC 电池容量仅为5 000 J时，三种算法的平均充电时延都较小，这是因为很多节点都由于能量不足已陷入休眠，随着电池容量增大，有更多节点等待充电，时延也随之增大，而本文的nUCRC 算法由于采用了时空混合优先级选择节点充电，使急需充电的节点的等待时间变短，因而在平均充电时延方面也具有最佳的表现。

图6 平均充电时延对比

3.2.3 网络规模的影响

本文还研究了网络规模对nUCRC 算法性能的影响。 图7 给出了不同的网络规模对单个充电周期时间的影响。 随着网络规模增大、节点数增多，簇的数量也增多了，MC 充电任务加重，需要访问更多的簇、为更多的节点充电，完成一次充电周期所花费的时间就更长。 当网络规模为50 m×50 m，节点数N＝50 时，完成一次充电周期至多需要130 s，最少需要80 s；网络规模为100 m×100 m，N＝100 时，完成一次充电周期的时间最多为230 s，最少为180 s；而当网络规模为150 m×150 m，N＝150 时，完成一次充电周期的时间最少也需要600 s 左右，最多需要800 s 左右，说明此时单个MC 已经不能够满足此种网络规模下的实时充电需求了，需要多个MC 才能完成充电任务。

图7 网络规模对调度时间的影响

图8描述了网络规模对MC 移动路径长度的影响，网络规模为50 m×50 m，N＝50 时，MC 具有最短的移动路径，当网络规模增大时，节点数量增多导致MC 要往返于更多的簇之间为更多节点充电，因此当网络规模为150 m×150 m，N＝150 时，MC 每完成一个充电周期要移动8 000 m 左右的距离，显然单个MC 已经不能满足此种网络规模下的需求了。

图8 网络规模对移动路径长度的影响

4 结束语

在本文中，针对具有实时性要求的WRSNs 提出了一种基于非均匀分簇的实时充电算法(nUCRC)，创新之处在于采用非均匀分簇的方法，均衡了网络中不同位置节点的充电机会，并采用动态规划的方法找出MC 的最短移动路径；在选择簇内节点充电时，采取的是部分充的策略，有效减少了节点的充电等待时间；而在充电顺序的选择上，则采用了时空混合优先级的方法。 通过与最先进的两种按需充电算法的对比，本文所提算法的节点存活率提升约10%、平均充电时延提升约20%。 另外还对不同网络规模下nUCRC 算法的性能进行了分析，结果表明本文所提算法适用于小型WRSNs，下一步将对多个MC 协同工作展开研究。