无线传感器网络作为物联网感知层由大量能量受限的低能耗、小体积传感器节点组成.广泛地应用于车联网、医疗健康、环境监测及智能家居等众多物联网领域中.能量受限是阻碍其发展的关键因素^[1].采用无线能量传输技术的无线可充电传感器网络(WRSNs，wireless rechargeable sensor networks)一出现便备受瞩目^[2]，研究并设计出合理的充电策略是保证WRSNs长久运行的关键问题.

WRSNs充电策略的研究一般分为单移动充电车(MC，mobile charger)充电方案和多MC充电方案.董颖等^[3]提出了一种基于预测的分簇低能量路径移动充电算法可及时对某些“饥饿”节点补充能量. Joseph等^[4]提出了一种联合优化节点功率控制、数据路由和充电策略的算法，可合理化利用网络资源. Han等^[5]提出了基于离线模型的充电方案，多MC周期性为节点补充能量和收集数据. Dai等^[6]讨论了在满足可维持大规模WRSNs正常运行的前提下需要最少的MC数量问题.

针对较大规模WRSNs提出一种多充电车充电策略K-PPER，K代表优化的K-means聚类算法(K-means improvement)，监测区域划分成K个簇并对节点以簇为单位进行管理，可使网络负载更加均衡；采用基于充电优先权的周期性能量补充方案(PPER，periodic energy replenishment based on charging priority)为节点补充能量，通过对节点剩余能量做出限定，可以使有能量需求的节点及时得到服务，能够保证节点不死亡.

1 网络模型 1.1 K-PPER可充电无线传感器网络结构

图 1为基于K-PPER算法的WRSNs示意图.

网络中有一个固定的位于网络监测区域中心的基站(BS，base station)，负责对节点产生的数据进行存储和处理，并管理MC的调度以及充电维护工作；在监测区域内，随机分布着大量负责采集和转发数据任务的可充电传感器节点，节点一旦部署之后位置不再发生改变；K个MC周期性地为网络内有能量需求的节点提供能量补充服务.假定BS和MC在工作状态下均能够准确地掌握网络中所有节点的位置信息.

1.2 K-PPER工作过程

采用优化K-means算法进行分簇，根据节点的地理位置将监测区域内的节点划分为K个簇.每个簇通过竞选方式产生簇头节点，其他节点只能作为成员节点，负责获取数据并转发至簇头节点；簇头节点对接收到的数据进行汇聚融合处理，并将融合后的数据转发至BS，最终由BS实现对数据的存储及处理.

在算法1中，1~2行表示利用优化的K-means聚类算法实现网络分簇；3~12行表示利用算法3进行充电调度，m代表充电调度次数；7~11行表示一次充电调度的执行过程.其中，t为MC的休整充电时间，当t>τ_station时MC的能量已充满；L_max为一轮充电序列的最大长度.当某节点的剩余能量满足充电阈值时，即主动向BS发送充电请求. BS以簇为单位将其加入归属簇所对应的充电序列中，并按充电优先级进行排序.当某充电序列中的节点满足一轮完整充电任务所能容纳的节点数时，BS即指定一个空闲的MC到达所对应的监测区域，MC即开展充电任务.完成充电任务后的MC返回BS，接受休整如补充电量并等待BS发出下一轮充电任务.

算法1  基于K-PPER算法的WRSNs充电策略

1  Initialization Network: set up the WRSNs with random distribution;

2  Use K-means and Algorithm 2 to cluster the network;

3  Sensor nodes communication and consume energy, transmit data to BS;

4  Node sends charging request to the BS:

5  for T=1 to m do

6          In each cluster charging list χ, use Algorithm3 to calculate the charging priority of nodes with charging request:

7          while t>τ_station&&length(χ)≡L_max do

8          BS sends the request and the charging list χ′ to one unoccupied MC:

9          MC receives the charging instruction with the list χ′ and arrives at the corresponding service area.and start charging task following its χ′:

10          Finish charging task and return to the BS.

11      end while

12  end for

2 网络初始化

网络采用优化的K-means算法完成分簇任务且只分簇1次.若整个监测区域被划分为K个簇，则节点属于某簇的信息不再改变.分簇后，BS广播成簇消息，节点接收到成簇消息后，参与簇头节点的竞选.第1轮簇头节点的竞选规则是选取距该簇中心位置最近的节点充当簇头节点.为均衡节点能耗，在其后的每一轮各簇均需依据簇内成员节点的剩余能量和位置来判断是否需更换簇头.若满足更换条件则在簇内执行簇头节点的轮换，反之则继续沿用上一轮的簇头节点.

2.1 初始聚类中心的选取

K-PPER中采用算法2优化网络初始聚类中心的选择.第1行表示计算网络中任意两点之间的距离；第2行表示将距离最远的2个节点作为初始聚类中心；3~4行表示在剩下的(N-2)个节点中选取到初始聚类中心距离乘积最大的节点作为第3个聚类中心，迭代上述步骤，当满足收敛条件时，算法终止.由K-means和算法2联合优化分簇过程，收敛速度更快且迭代次数更少，适用于分簇型的网络结构.

算法2  初始聚类中心选取算法

1  Stepl: Calculate the distance of N points g(  );

2  Step2: Find two points d₁, d₂ which is satisfed the inequality relationship as two initial cluster ceuters: {g(d₁, d₂)≥g(d_i, d_j)}(i, j=1, 2, …, N):

3  Step3:Calculate the distance of residual (N-2) sample points:

4  Step4: Find the point d₃ as the third initial cluster center $\prod\limits_{j = 1}^2 g \left({{d_j}, {d_3}} \right) \ge \prod\limits_{j = 1}^2 g \left({{d_j}, {d_i}} \right)$ (d_i is addition to d₁, d₂, d₃ ans sample point):

5  Step.....Repeat until find the k initial cluster center.

6  End

2.2 簇头竞选阶段

K-PPER策略在运行的第1轮选取与该簇聚类中心O_j相距最近的节点充当簇头节点，此时簇内的其他成员节点到达簇头节点的距离之和最小，实现了簇内能量的分布均衡.

网络每轮运行至数据传输阶段的最后一帧时，簇内所有成员节点向簇头节点汇报自己当前剩余能量E_i以及与簇中心O_j的距离d_i.式(1)计算节点i的更换因子值ε_i，成员节点的剩余能量越高，距离聚类中心越近，其更换因子ε_i就越大，即它竞选成为下一轮簇头节点的概率就越高.

${\varepsilon _i} = {E_i}{\left( {{d_i} + \mu } \right)^{ - 1}} $

(1)

其中μ为常数.

由于簇头轮换也需消耗一定的能量，为节约能量只有满足一定的簇头轮换条件(见式(2))，才会执行簇头轮换操作.

${\varepsilon _{{\rm{ head }}}} = {E_{{\rm{ head }}}}{\left( {{d_{{\rm{ head }}}} + \mu } \right)^{ - 1}}\alpha {\varepsilon _{{\rm{ max }}}}, \alpha \in (0, 1) $

(2)

其中：ε_head为本轮簇头节点的更换因子；E_head为当前簇头节点的剩余能量；d_head为簇头节点与簇中心的距离；ε_max为当前簇内ε_i的最大值；α为限制系数，它决定了簇内更新簇头节点的频率，α越小，簇头的更换频率越低，此时簇内一直担任簇头的节点会因能耗过大而死亡.为实现簇内节点能量的平均分配，经实验测试选取α=0.6.

当式(2)成立时，说明本簇在下一轮开始时需更换簇头节点，进入簇头轮换阶段.由节点n担任簇头节点，上一轮的簇头节点与节点n交换簇内成员信息和时隙，并在簇内广播更换簇头消息.不满足更换条件的簇，则在下一轮直接进入数据传输阶段，该簇在通信时继续沿用上一轮运行时的簇头节点.

2.3 数据传输阶段

在数据传输阶段，簇头节点采用时分多址接入(TDMA，time division multiple access)机制为簇内的成员节点划分时隙.成员节点在其所在的时隙内采集周围环境信息，经单跳或多跳转发数据至簇头，簇头节点接收数据并进行融合处理，最后经单跳路由发送至BS.因此，簇头节点i处的数据流应满足

${f_{i, B}} = \xi \left[ {{R_i} + \sum\limits_{j = 1}^n {{f_{j, i}}} } \right] $

(3)

其中：簇头节点i产生的数据速率为R_i；成员节点j向簇头节点i转发数据的速率为f_{j, i}；簇头i向BS发送数据的速率记为f_{i, B}；数据融合率ξ∈(0, 1]，表示簇头节点去除冗余数据的数据融合能力，ξ=1表示簇头对接收的数据没有进行融合处理.

簇头节点处汇集了簇内所有成员节点的数据，因此它相对于成员节点需要消耗更多的能量.为减轻簇头节点能耗，对簇内的通信方式做了优化改进.当簇内成员节点与BS之间的距离小于簇头节点到BS的距离时，该节点选择直接与BS通信；反之，不满足距离条件的成员节点仍然先发送数据至簇头节点，经过融合处理之后再发送至BS.

3 通信能耗模型 3.1 簇内成员节点能耗 3.1.1 发射能耗

采用一阶无线电模型描述节点的通信能耗，网络内节点每发送l bit数据需要消耗的能量为

$\begin{array}{l} {E_{{\rm{Tx}}}}(l, d) = {E_{{\rm{Tx}} - {\rm{elec}}}}(l) + {E_{{\rm{Tx}} - {\rm{amp}}}}(l, d) = \\ {\rm{\;\;\;\;\;\;\;\;\;\;\;\;\;\;}}\left\{ {\begin{array}{*{20}{l}} {l{E_e} + l{\varepsilon _{fs}}{d^2}, }&{d < {d_0}}\\ {l{E_e} + l{\varepsilon _{{\rm{amp}}}}{d^4}, }&{d \ge {d_0}} \end{array}} \right. \end{array} $

(4)

其中：E_TX-elec(l)为发射电路能耗；E_TX－amp(l, d)为发射功率放大器能耗；d为传输距离；发射电路每处理1 bit数据的能耗为E_e；ε_fs和ε_amp分别为自由空间信道和多径衰落信道发送功率放大器单位面积发射1 bit数据的能耗；d₀为距离阈值.文中取ε_fs=10 pJ/bit/m⁴，ε_amp=0.013 pJ/bit/m⁴，${d_0} = \sqrt {\frac{{{\varepsilon _{fs}}}}{{{\varepsilon _{{\rm{ amp }}}}}}} = 87.7{\rm{m}}$.

3.1.2 接收能耗

网络内的节点每接收l bit数据需消耗能量为

${E_{{\rm{RX}}}}(l, d) = l{E_{{\rm{RX}} - {\rm{elec}}}} = l{E_{\rm{e}}} $

(5)

其中：E_RX-elec为节点每接收1 bit数据需要的能耗，E_e表示接收电路每处理1 bit数据需要消耗的能量.

3.2 簇头节点能耗

簇头节点除发送能耗和接收能耗之外，还有融合能耗.设E_da表示簇头节点每融合1 bit数据需消耗的能量，其发送能耗和接收能耗的计算方法同3.1.设簇头节点i接收并将簇内节点的n bit数据融合为1 bit数据再发送给BS，簇头与BS间距离为d，簇头节点的能耗E_H如式(6)所示.

${E_{\rm{H}}} = {E_{{\rm{TX}}}}(1, d) + {E_{{\rm{RX}}}}(n, d) + n{E_{{\rm{da}}}} $

(6)

4 K-PPER能量补充方案

WRSNs中当节点的剩余能量满足充电条件时，节点主动向BS发送充电请求. BS接收来自各簇的充电请求信息，并向满足一轮充电请求的簇派出一个MC，令其到达相应的簇监测区域开展充电工作.笔者针对较大型WRSNs，提出一种基于充电优先权的周期性能量补充方案-K-PPER.

K-PPER联合考虑节点能耗、地理位置和邻居节点数量等关键因素，计算充电请求节点的充电权值，从而确定各簇内节点的充电顺序. MC依照该充电序列依次为有能量需求的节点提供能量.此外，为避免已发送充电请求的节点在等待MC到来的过程中耗尽能量，所以强迫当前剩余能量到达E_min的传感器节点进入到睡眠状态，以降低其工作能耗.

4.1 网络约束条件

采用K-PPER进行充电时需要对网络中的节点进行能量的控制与管理.若节点i当前的剩余能量e_i满足约束条件(7)，节点i立即向BS发送充电请求，请求信息中包括该节点当前的剩余能量、该节点与BS之间的距离以及它周围邻居节点的数量.

$\frac{{\phi (m, {\rm{BS}})}}{v}{p_i}l = {e_i} - {E_{\min }} $

(7)

$l \le {L_{\max }} $

(8)

其中：ϕ(m, BS)表示MC从BS出发到达距BS最远节点m的路径长度，v表示MC的移动速度，p_i表示节点i的能耗速率，l表示当前簇内充电序列χ的长度，L_max表示一轮充电序列可以实现的最大长度.

已发送充电请求的节点在等待MC到来的过程中，节点的剩余能量在某一时刻可能达到维持正常工作的阈值E_min.网络根据自组织介质访问控制协议(S-MAC，self-organized medium access control)迫使剩余能量达到阈值的节点转入睡眠状态以降低其能耗，同时利用请求发送/清除发送4次握手和随机回避机制避免碰撞.节点从侦听状态转入睡眠状态时会关闭天线，以降低大量空闲侦听带来的能耗.发送充电请求的节点在进入睡眠状态之前可等待的最长时间为

${t_0} = \frac{{e_i^\prime - {E_{\min }}}}{v} $

(9)

其中e′_i表示节点发送充电请求时的剩余能量.

BS收到来自各簇节点的充电请求，并且向满足一轮充电要求的簇派出MC开展充电任务，则MC提供服务的时长可以表示为

$\tau = {\tau _{{\rm{ station }}}} + \sum\limits_{m \in M} {{\tau _m}} + \left( {\frac{{{d_{B, 1}}}}{v} + \sum\limits_{m = 1}^{M - 1} {\frac{{{d_{m, m + 1}}}}{v}} + \frac{{{d_{M, B}}}}{v}} \right) $

(10)

其中：第2项代表MC停靠在充电节点处的时间，第3项代表MC在一次充电回路上的旅行时间.

4.2 充电序列确定

根据剩余能量、地理位置和网络连通性等3个方面确定其节点的充电优先级.节点的剩余能量越低，说明该节点越亟需充电，节点的能量因素是影响通信质量的关键因素；节点距离BS越近，MC到达该节点并为其充电时需经过的路径则越短，由此MC能够及时地到达能量请求节点处为其提供能量，故节点所在的地理位置也会影响到节点的充电优先级；此外，网络能够发挥作用是由于节点能够覆盖一定的区域且其所获得的数据能够通过多跳中继到BS，故还需保证节点之间的连通性，邻居节点越少的节点完成数据转发任务时需要的能耗越多，这也影响节点的充电优先级.因此，通过算法3获得节点的优先级.

算法3    节点充电优先级算法

Input: e_A, e_B, d_A, d_B, n_A, n_B, P_A, P_B

Output: Comparison of P_A and P_B

1    if σe_A+μd_A+φn_A < σe_B+μd_B+φn_B then

2        P_A>P_B

3    else if σe_A+μd_A+φn_A=σe_B+μd_B+φn_B then

4        if e_An_A < e_An_A then

5            P_A>P_B

6        else

7            P_A < P_B

8    end if

9  else

10    P_A < P_B

11  end if

在WRSNs中节点的充电请求是不断更新的，时刻会有新的节点加入到充电请求序列χ中.为及时有效地完成充电任务，K-PPER需要对已经加入充电序列χ中的节点计算它们的充电权值w_i，比较它们各自的充电优先级P_i.节点的充电权值可由式(11)和式(12)得到. w_i值越小，节点的充电优先级P_i越高，BS根据χ中节点的P_i值重新对充电节点排序.当充电序列的长度达到L_max时，满足一轮簇内充电要求，同时也得到该簇内一次完整的充电任务序列χ′. BS派出一个MC到达该簇，按χ′中的顺序依次对节点开展充电工作.

${w_i} = \sigma {e_i} + \mu {d_i} + \phi {n_i} $

(11)

$\sigma + \mu + \phi = 1, \sigma \ge 0, \mu \ge 0, \quad \phi \ge 0 $

(12)

其中：e_i表示节点i当前的剩余能量，d_i表示节点i与BS的距离，n_i表示节点i在其感知半径R_v范围内的邻居节点个数.文中对权值的分配情况如下：σ=0.4, μ=0.3, ϕ=0.3.

5 仿真实验与分析 5.1 参数设置

在200 m×200 m的仿真区域中，BS位于网络中心，坐标为(100, 100)；200个随机分布的具有相同初始能量E₀的可充电传感器节点；网络中设有4个MC，BS和节点的位置一旦确定之后将不再发生改变.

5.2 实验结果分析 5.2.1 网络效用

网络效用指网络内存活节点数占节点总数的比例. 图 2所示为采用优化K-means算法与传统K-means的网络效用对比.从图 2可见，在不为网络节点补充能量的前提下，优化网络的网络效用较K-means网络可提高约42%.

在传统K-means算法中，簇内选取距离簇质心位置最近的节点充当簇头节点，簇头节点需转发所有来自成员节点的数据，其能耗过快且易出现簇内能耗不均现象.在优化算法中，簇头节点的选取综合考虑了剩余能量和节点位置，簇内的能耗更均衡，有利于延长网络的平均寿命.此外，由于某些节点可直接与BS通信，这也减轻了簇头节点的数据转发压力，降低了其能耗速率.采用优化K-means算法的网络对应的网络效用值下降缓慢，说明其在节省能量方面的有效性.

5.2.2 网络能量消耗

图 3和图 4所示为在网络运行结束时(设定仿真时间为8 000轮)网络内节点剩余电量水平的抽样结果.

采用K-PPER策略网络内节点的平均剩余电量高达约85%，采用CLP策略时^[3]，网络节点平均剩余的电量约为67%. K-PPER使用K个MC，分别被派到对应的簇内开展周期性充电工作.达到充电条件的节点主动向BS发送请求，BS根据充电优先级的高低对已加入序列的节点进行排序，MC按次序为节点充电.这样不仅能够及时为低电量节点补充能量，而且减小了由于节点能量水平的降低而对网络覆盖性及连通性的影响.

5.2.3 能量效用

能量效用η指MC在一次充电任务中为节点补充的总能量与路径上消耗能量的比值. η值越大表示MC能量效用越高.

$\eta = \sum {{E_{{\rm{ sup ply }}}}} /{E_{{\rm{ route }} - {\rm{ consume }}}}\ $

(13)

其中：∑E_{sup ply}表示在一次充电任务中MC为网络中节点补充的总能量，E_{route-consume}表示MC在完成充电任务时自身消耗的能量.

图 5所示为在不同的网络规模下K-PPER、DC、DCLK^[7]3种多MC充电算法的能量效用对比.当网络规模从150个节点逐渐递增到400个节点时，K-PPER的MC平均能量效用为2.8，相比于DCLK算法的能量效用提高了约4%，较DC算法的能量效用提高了约18%.在采用K-PPER的网络中，MC能量效用波动很小且相对稳定，可以持续不断地为网络内节点提供能量补充，保障网络的持久运行.

6 结束语

提出了一种WRSNs中的多充电车充电策略K-PPER.首先为了避免网络中出现能耗不均衡的现象，采用优化K-means算法对监测区域聚类分簇，并完成了对簇头节点竞选和数据传输2个阶段的性能优化. K-PPER策略通过对网络进行约束，能够合理地为MC分配充电任务，对有能量需求的节点进行充电.仿真结果表明，优化的分簇网络具备更优的网络性能；K-PPER策略具有稳定且较优的能量效用，能够完成WRSNs的工作使命，维护网络的正常运行.