祝镱雯,程宗毛

(杭州电子科技大学理学院，浙江 杭州 310018)

0 引 言

无线可充电传感器网络(Wireless Rechargeable Sensor Networks，WRSNs)中的充电问题是一个热门研究问题，即无线充电车(Wireless Chargeable Vehicle，WCV)如何为节点供电[1]。前期的充电方案大多数将充电问题转化成旅行商问题，利用哈密顿回路的解来规划充电路径。文献[2-3]分别采用点对点的充电模型和点对多的充电模型，利用哈密顿回路的解来规划充电路径，确保传感器网络持续运行。保证了WCV行驶距离最短，但忽略了节点充电的紧急性。文献[4]提出一种新的充电规则，即WCV每次选择离它最近的节点充电，这种反复移动增加了移动距离，不仅浪费能量，而且忽略了节点充电的紧急性。文献[5]先通过哈密顿回路的解来制定主节点的充电路径，再在主节点周围选择可行的路过节点，将其插入到充电路径中。这种机制只在选取路过节点时考虑节点充电的紧急性，在主节点选取时仍忽略了节点充电的紧急性，造成急需充电节点的死亡。文献[6]将传感器节点的紧急优先级和距离优先级合并为混合优先级，根据混合优先级生成最小生成树，使用最少数量的WCV维持传感器网络运行，但是，基于最小生成树方法只能保证根节点到其他节点的路径是最短的，不能保证其他节点之间的路径最短，从而导致WCV在路上消耗更多的能量。受上述方法的启发，本文针对大规模WRSNs按需充电体系，研究多无线充电车充电调度优化问题。在已知充电节点数和节点剩余电量的前提下，提出一种无线充电车能量利用率最大化的综合权重调度算法，进而得到最小化网络死亡节点数的充电优化方案。

1 网络模型

在一个矩形区域内，基站位于几何区域中心，传感器节点随机部署在矩形区域内，节点固定不动。WCV配有GPS定位系统，基站负责收集传感器和WCV的相关数据，管理传感器网络，规划充电路径和调度WCV。当传感器节点剩余能量低至阈值时，传感器节点从有电节点变成充电节点，向基站发送充电请求，基站通过传感器节点的剩余能量和地理位置规划充电策略，派出WCV进行充电。为了把充电策略的重点放在充电调度和方案整体性能上，本文算法简化了充电模型，假设传感器在合理时间内将充电请求发送给基站，其中的短暂延迟不影响方案的整体性能。

在WRSNs中，基站表示为N0，充电节点表示为Ni(i=1,2,…,n)，节点Ni到节点Nj之间的距离为di,j，当i=0时，d0,j表示基站到充电节点Nj的距离。WRSNs中的充电问题主要有2个基本约束。

(1)节点的能量约束：节点的剩余电量在WCV到达之前大于0，否则节点死亡。

通过迭代法计算出WCV的到达时间ti和逗留时间τi分别为

(1)

(2)

式中，v表示WCV的行驶速度，Ec表示节点的总容量，Ei表示节点Ni的剩余电量，qc表示WCV为节点充电的速率。

节点的能量约束表示为：

Ei-piti>0,i=1,2,…,n

(3)

式中，pi表示节点Ni的消耗速率。

(2)WCV的能量约束：WCV完成一轮充电任务后要有足够的电量回到基站。

(4)

本文设计充电方案的目标是最小化网络节点死亡数，最大化WCV能量利用率。本文通过节点的死亡数Ndead和WCV的充电量Ea来衡量充电策略的性能。Ndead表示WCV到达充电节点时电量为0节点的数目，Ea表示WCV为所有充电节点充电的总电量。

(5)

(6)

式中，I(Ei-piti=0)表示示性函数，优化目标为minNdead，maxEa。

2 模型求解

在按需充电网络模型下，解决问题的关键是WCV的充电顺序。因此，本文提出一种无线充电车能量利用率最大化的综合权重调度算法，即用综合权重调度算法(Comprehensive Weight Scheduling Algorithm，CWSA)来提高网络的生存率。首先，利用节点的综合权重规划WCV充电主路径；然后，在WCV充电时，顺带为主路径周围充电节点充电。

2.1 主路径规划

在大规模的WRSNs中，有M辆WCV为充电节点进行充电。首先根据充电节点的坐标位置，利用K均值聚类算法将网络中的充电节点聚成M类，每辆WCV为一个类内的节点进行充电。在每一类内，基站通过节点的综合权值规划WCV的充电路径。

综合权重主要包括距离权重、急迫性权重以及节点度数权重。

(7)

式中，系数λ1，λ2，λ3表示距离权重、急迫性权重以及节点度数权重的重要程度，系数和为1，根据实际需求选择系数大小。

定义1(距离权重)：Pi(d)表示传感器节点Ni的距离权重，距离越远权重越小，由节点Ni到节点Nj的距离表示，即Pi(d)=-dij。

对于节点度数的计算，需确定距离阈值Di，本文Di选取是Ni周围充电节点与Ni距离的1/4中位数。节点度数保证了WCV尽可能多地将电量利用在节点充电上，减少了行驶电量的消耗。

通过式(7)计算得出所有充电节点的综合权值，在每一类内，将所有充电节点按权重由大到小排序，WCV按排序进行节点充电，当WCV的剩余电量不能维持WCV回到基站充电时停止充电并返回。每辆WCV按综合权重排序对充电节点充电的顺序即为每辆WCV的充电主路径。

2.2 选择插入节点

在充电主路径确定之后，进行插入节点的选取。插入节点的选择规则主要是如何选择出可行的插入节点，本文采用“绘制辅助圆”的方法[5]，以主路径上2个节点之间的距离为直径绘制圆，将圆内的节点选取为可行插入节点。

假设主路径中插入一个节点Ninsert，则WCV行驶距离将增加：

Δdinsert=di,insert+dinsert,i+1-di,i+1

(8)

WCV消耗电量将增加：

ΔEinsert=qmΔdinsert+qcτinsert

(9)

当节点Ninsert满足主路径节点不死亡，也不会导致WCV电量的耗尽以及Ninsert在WCV来到之前不死亡时，Ninsert就是插入节点。即：

为简化计算，每个圆内只选择一个插入节点。当圆内有多个节点符合要求时，通过计算每个节点的综合权值，选取权值最大的节点。在主路径中每2个充电节点都可插入满足条件的插入节点，由此形成新的充电路径。在新的充电路径上再按照插入规则选择插入节点，不断循环，直至WCV的剩余电量不能维持其回到基站充电时停止，最终得到最优充电路径。

3 仿真实验

本文的仿真实验设计参考文献[6]的设计，设置如下：(1)网络大小为100 m×100 m的正方形区域，需充电节点数为100～300个；(2)WCV能量为5 000 J，行驶速度为1 m/s，移动消耗能量为12 J/s，充电速度为8 J/s；(3)传感器节点能量为100 J，节点的消耗速率为0.01～0.03 J/s。

在不同充电节点数量N、不同阈值δ下，CWSA算法对网络节点死亡数的影响，结果如图1所示。在不同充电节点数量N、不同的WCV数量M下，CWSA算法对网络节点死亡数的影响如图2所示。从图1可以看出：在部署的节点数相同情况下，增加WCV数量能够明显降低节点死亡数量。从图2可看出：在部署的节点数相同情况下，随着阈值的增加，网络的节点死亡数量也得到降低。这是由于随着阈值的增加，节点剩余电量同时增加，节点死亡数量随之降低。从图1、图2还可以看出：节点死亡数都随着充电节点数的增加而降低。

图1 不同小车数量下死亡的节点数

图2 不同阈值下死亡的节点数

从网络节点死亡数和总充电量两方面对本文提出的CWSA算法和文献[6]提出的基于最小生成树的最优移动车辆数算法(Number of Mobile Vehicles，NMV)进行比较，结果如图3、图4所示。从图3可看出：在充电节点固定时，随着WCV数量的增加，运用2种算法的网络节点死亡数都不断减少，但在CWSA算法下网络的死亡节点数减少得多。同时，当WCV数量相同时，在CWSA算法下的死亡节点数明显少于NMV算法，甚至少于一半以上。由此说明，在相同的网络规模下，CWSA算法能更好地延长网络寿命。从图4可看出：随着WCV数量的增加，在2种算法下网络的总充电量不断增加，但运用CWSA算法的总充电量比NMV算法增加得更多。还可看出WCV数量相同时，运用CWSA算法时，网络的总充电量明显高于NMV算法，由此也可以说明在相同的网络规模下CWSA算法能更充分地利用WCV，延长网络寿命。

图3 无线充电车数目与节点死亡数关系

图4 无线充电车数目与充电量关系

4 结束语

在大规模的WRSNs按需充电体系下，本文研究传感器节点的多无线充电车调度优化问题，开发一种基于无线充电车能量利用率最大化的综合权重调度算法，得到最小化网络节点死亡数的充电优化方案。可将此方案运用到实际应用中，用更低的成本维持网络的运行。本文的研究针对充电节点数目确定且不变的情况，但在实际应用中，随着时间的变化，充电节点数不断增加，后续将对这种场景下的多无线充电车调度优化问题展开进一步研究。