1.   引言

近年来，物联网(Internet Of Things, IOT)的发展如火如荼，作为其核心的无线传感器网络(Wireless Sensor Networks, WSNs)已广泛应用于环境监测、目标跟踪、医学和科学探索等领域^[1]。但是传统的电池供电方式导致了WSNs寿命受限。

为了解决这一问题，研究人员提出了如下3类解决方案。一是设法提高WSNs的资源利用率，进而减少传感器节点的能量消耗。例如引入优化路由协议^[2]、睡眠调度机制^[3]、数据融合处理^[4]、网络分簇聚类^[5]等策略。这类工作虽能减少网络整体能量消耗并延长其寿命，但是难以从根本上解决WSNs的能量受限问题。二是通过能量收集技术收集传感器周围环境中的能量实现能量的补给。例如收集太阳能、风能和热能等^[6-8]。但是这种方法具有一定的天然不稳定性。三是通过磁耦合共振的无线能量传输技术远距离对传感器进行无线充电。如Tong等人^[9]通过实验验证了无线充电技术在WSNs中应用的可行性。但是在WSNs中如何合理地调度移动充电器进行无线充电成为一个亟待解决的现实问题。

理论上，无线可充电传感器网络(Wireless Recharging Sensors Networks, WRSNs)可以永久保持工作状态。但是，因为充电系统充电能力的局限性，例如：充电器总能量受限^[10]，充电周期受限^[11]，充电距离的影响^[12]等因素，需要结合具体的充电任务进行调度规划。

根据充电模型划分，现有研究成果主要分为一对一^[13-15]和一对多两类充电模型^[16-18]。前者往往假设移动充电器从基站出发，为沿途的传感器节点提供一对一充电服务，最后返回基站的充电场景。在之前的工作^[13]中，本文主要考虑了一对一充电模式下，从移动充电器调度、传感器充电时间分配、节点速率控制协同优化来提高网络性能。而Huong等人^[14]则以最小化饿死节点数量为目标，提出了一种基于遗传算法的充电调度方案。Zhao等人^[15]以充电效率最大化为目标，建立了充电调度和充电时间分配的混合整数优化模型。并设计了兼顾充电任务和分配充电时间目标优化的离线算法。一对一充电方式的缺点主要是充电效率较低，并且在实施时受限于具体环境。

为了进一步提高移动充电器的充电效率，一对多充电调度方案应运而生。Liu等人^[16]提出了一种多节点的时空域局部充电算法(Multi-node Temporal Spatial Partial Charging, MTSPC)。本算法首先构建一个尽可能满足充电请求的充电方案，然后采用生成的充电方案来提高能源使用效率。而Zhang等人^[17]提出了一种多节点可充电算法(Multi-node Rechargeable Algorithm, MRA)。该算法使用移动充电器定期访问WRSNs中的每个对接站点并对覆盖范围内的节点充电。通过减少停靠点的数量并优化移动充电器的行驶路径，从而提高充电效率。此外吕增威等人^[18]则提出了一种基于多目标优化的WRSNs移动充电和数据收集联合优化方案。上述方案仅仅假设移动充电器的充电模型为全向覆盖，并没有考虑有向天线情形。本文主要在现有研究工作的基础上提出了一种基于充电效用最大化的有向充电方案。

2.   系统模型和问题描述

2.1   网络系统模型

2维平面中的无线可充电传感器网络可以表示为$G = (V',E)$，其中$V' = (V \cup S)$。$V$是平面内随机分布的传感器节点，每个传感器均配有容量为$B$的可充电电池，$S$代表网络中的Sink节点。本文主要考虑通过一个移动有向充电器为WRSNs中传感器进行周期性巡游充电的场景。网络中心处放置一个基站$v_0$，为巡游后的移动充电器补充能量以保证在下一个周期$T$内能够完成充电任务。网络系统模型如图1。

图 1  网络系统模型

下载: 全尺寸图片 幻灯片

2.2   充电模型

充电模型中的有向充电器采用一个5元组来描述：${{C}}_j{\rm{ = \{ }}(X_j,Y_j,A,\theta_j,D){\rm{| }}j \in {{M\} }}$。其中$X_j,Y_j$为有向充电器在2维平面中的锚点位置，$\theta_j$为有向充电器朝向角度，$A$是有向充电器最大覆盖角度，$D$为有向充电器最大充电半径，M为有向充电器停车锚点集合。同时，采用二进制数$Q_{c_{j,v_i}}$表示网络中传感器节点$v_i$是否被$C_j$覆盖到，如式(1)

其中，$\theta (C_j,v_i)$为有向充电器与传感器$v_i$的夹角，$d(C_j,v_i)$为有向充电器与传感器$v_i$的距离。有向充电模型如图2。

图 2  有向充电模型

下载: 全尺寸图片 幻灯片

若节点$v_i$在有向充电器$C_j$覆盖范围，采用Friis自由空间模型对$v_i$充电，充电功率近似为式(2)

其中，$a = \dfrac{{G_{\rm{s}}G_{\rm{r}}h{P_0}}}{{L_p}}{\left( {\dfrac{l}{{4p}}} \right)^2}$, $G_{\rm{s}}$为源天线增益，$G_{\rm{r}}$为接收天线增益，$L_p$为极化损失^[19]。

联合式(1)、式(2)，得到式(3)

2.3   问题描述

本文试图解决的问题是如何通过一个移动的有向充电器为WRSNs中多个传感器节点同时充电。移动充电器从基站$v_{\rm{0}}$出发，沿着一条闭环的巡游路径行驶，最终回到$v_{\rm{0}}$。在巡游过程中可能存在多个停车锚点使移动充电器停止移动，进行无线充电。假设这样的锚点集合是$M$，并且据此规划移动充电器的行驶路线。然后根据每个有向覆盖集合内节点能量、位置等变量为每个锚点的覆盖集合分配充电时间$\tau (t_j)\{ j \in M\}$，目标是使移动充电器充电效用最大化。

3.   MUC调度方案

在MUC调度方案中，充电效用最大化问题被分解为3个阶段优化：覆盖集合的提取、覆盖子集的筛选、充电时间的分配。

3.1   覆盖集合的提取

理想状态下有向充电器的停车锚点和朝向是任意的。为了简便操作，假设有向充电器只能停留在和网络中传感器节点相同位置处。用${C_j}(v) = \{ u|d(j,v)$$\le D, \left| {{\theta _{u,v}}} \right| \le \dfrac{A}{2},j \in M,v \in V\}$表示该锚点下有向覆盖集合。其中充电器朝向的变化会使有向覆盖集合也在不断地变化。为了解决这个问题，提出了在定点情况下有向覆盖集合提取算法。为方便描述，首先给出定义1。

定义1　在相同位置的情况下，不同朝向得到的覆盖集合$C_1(v)$和$C_2(v)$。如果$C_1(v) \in C_2(v)$，则称$C_2(v)$集合支配集合$C_1(v)$。

算法1　有向覆盖集合提取算法

步骤 1　以有向充电器$C_j$为原点建立2维平面坐标系，计算每个传感器节点与$C_j$的距离$d_i$、夹角$\theta_i$；

步骤 2　筛选出可充电范围内的传感器集合$V' = \{ v_1,v_2, ··· ,v_i\}$，按照逆时针方向将集合内的传感器节点按照角度从小到大进行升序排列，集合为${{q}} = {\rm{\{ }}\theta_1,\theta_2, ··· ,\theta_i{\rm{\} }}$；

步骤 3　以${{q}}$中的$\theta_i$为有向覆盖范围的临界边，逆时针方向扩展$A$角度，取出所有覆盖子集${C'_{{k}}}$,并记录相应的朝向角度$\theta_k = \theta_i + A/2$，直到遍历${{q}}$中的每一个传感器夹角；

步骤 4　去除被支配的覆盖子集，得到最终覆盖集合$C(v) = \{ {C'_1}(v),{C'_{\rm{2}}}(v), ··· ,{C'_k}(v)\}$。

图3为覆盖集合提取示例图。从图3(a)开始，以逆时针方向角度最小的$v_{\rm{1}}$节点作为覆盖范围的临界边，扩展覆盖角度$A$，取出第1次覆盖集合$C'_1 =$$\{ v_{\rm{1}},v_{\rm{2}},v_{\rm{3}}\}$；将临界边逆时针旋转${{q}}$集合中的第2个节点处，取出第2次覆盖集合$C'_2 = \{ v_{\rm{2}},v_{\rm{3}}\}$，如图3(b)所示；依次进行直到覆盖${{q}}$中所有元素。图3(c)—图3(e)分别得到其覆盖集合$C_3' = \{ v_{\rm{3}}\}$, $C_4' = \{ v_{\rm{4}}\}$, $C_5' =$$\{ v_{\rm{5}},v_{\rm{1}}\}$。去除被支配集合$C_2'$情况后，得到在定点处C的所有覆盖集合$C_1' = \{ v_{\rm{1}},v_{\rm{2}},v_{\rm{3}}\}$, $C_3' = \{ v_3\}$, $C_4' =$$\{ v_4\}$, $C_5' = \{ v_5,v_1\}$。

图 3  覆盖集合提取示例图

下载: 全尺寸图片 幻灯片

3.2   覆盖子集的筛选

在WRSNs中让能量较少的节点优先充电或分配较多的充电时间会使充电收益增加。采用$\rho (t) =$$\dfrac{1}{p}(B-{{\rm{ER}}_v}){{\rm{e}}^{\frac{{-t}}{p}}}$来模拟电池能量的补充过程，其中$t$表示充电时间，$p$是与充电速率有关的时间常数^[20,21]。通过对充电时间积分可以得到随时间变化的电池获能式(4)

为了更直观看出电池获能过程，图4模拟了剩余能量不同的两个传感器节点随时间充电的获能情况。

图 4  电池充电获能图

下载: 全尺寸图片 幻灯片

图4分别为电池容量$B = 10000$ J，初始节点能量${\rm{ER}} = 0$时，即节点能量从0开始充电的函数图像；$B = 10000$ J, ${\rm{ER}} = 2000$ J时，即节点能量从$2000\;{\rm{J}}$开始充电的函数图像。不难发现在相同充电时间下，剩余能量较少的节点充电获能较多。

在覆盖子集筛选上，将网络中充电增益最大的覆盖集合依次筛选出来直到全覆盖。式(5)表示单个传感器在覆盖范围内的充电增益

$P_{\rm{c}}$为传感器节点接收到的实际充电功率，$P_{\rm{e}}$为传感器节点额定充电功率。如果用$g({C'})$表示覆盖集合的增益，则

根据式(6)可以求出每个覆盖集合的增益，具体步骤如算法2所示。

算法2　最优覆盖子集筛选算法

步骤 1　初始化移动充电器锚点集合$S$，覆盖集合增益$G(S) = 0$，筛选节点集合$U = V$；

步骤 2　 按照式(6)计算覆盖集合中增益最大的子集并加入到集合$S = \{ G({C'_i})\}$中，其中$G({C'_i}) =$$\arg \max \left(\mathop {\lim }\limits_{\tau ({t_j}) \to 0} \displaystyle\sum\nolimits_{j = 1} {{f_j}(\tau ({t_j}))} \right)$；

步骤 3　去掉传感器集合$U$中筛选出来的节点集合$U = U-{\rm{sub}}(C_i')$；

步骤 4　重复步骤2，步骤3，直到集合$U$为空，此时可以得到最终的覆盖子集：$S = \{ G({C'_1}),$$G({C'_2}), ··· ,G({C'_i})\}$。

3.3   充电时间的分配

当确定了有向覆盖子集后，需要采用智能算法确定一条最短巡游路径。假定移动充电器能量有限，且在固定周期$T$内需要回到基站进行能量补给。因此需要对移动充电器的充电时间进行合理分配。事实上，传感器充电时间分配问题可以通过式(7)描述

引入拉格朗日乘子$\alpha ,\,\beta ,\,t$对式(7)求解，则式(7)转化为式(8)

对$\alpha ,\beta ,t$求偏导，得到式(9)—式(11)

迭代优化充电时间${t_j}(k + 1)$，则

其中，$\kappa (k)$是一个微小的迭代步长。经迭代计算，可以求出每个覆盖集合的分配时间$t_j\{ j \in M\}$。

4.   实验及结果分析

本节通过实验验证和分析MUC调度方案的性能。

4.1   参数设置

实验参数如表1所示。

表 1  参数设置

参数	值
移动充电器能量EI	80000 J
传感器能量B	1000 J
移动充电器移动速度v	2 m/s
移动充电器移动能耗Cv	5 J/s
移动充电器充电能耗C	2 J/s
充电周期T	60 min
充电参数p	200
最大充电距离D	35 m
有向覆盖角A	π/3

下载: 导出CSV 

| 显示表格

4.2   基线算法

(1) 本文采用以下两种不同充电时间优化算法用于性能比较：

(a) 固定能量充电(Fixed Energy Charging, FEC)算法：将有向覆盖范围内的所有节点能量充到某个阈值(60%)，随后移动充电器巡游至下一锚点充电。

(b) 平均能量充电(Average Energy Charging, AEC)算法：在能够巡游覆盖所有节点的前提下，将可用的充电时间平均分配给每个覆盖集合。

(2) 本文采用以下两种不同覆盖子集筛选算法用于性能比较：

(a) 最多节点覆盖(Maximum Node Coverage, MNC)算法：筛选出网络中有向覆盖节点最多的集合，直到覆盖到每个节点。

(b) 最大平均增益覆盖(Maximum Average Gain Coverage, MAGC)算法筛选出网络中有向覆盖平均节点增益最大的集合，直到覆盖到每个节点。

4.3   实验结果及分析

传感器节点随机分布在150 m×150 m范围内，初始能量随机分配在0～B之间。

图5是在不同节点规模下充电算法的充电效用对比图。MUC算法比AEC算法提高13.7%，比FEC算法提高32.7%。在一定范围内，MUC算法的充电效用随节点规模的增加而提高，这是因为节点规模的增加会提高增益覆盖子集筛选的多样性。图6是在不同节点规模下充电算法饿死节点数对比图。MUC算法在不同节点规模下饿死节点数都明显少于其他两种算法。

图 5  不同规模下算法充电效用对比图

下载: 全尺寸图片 幻灯片

图 6  不同节点规模下充电算法饿死节点数对比图

下载: 全尺寸图片 幻灯片

图7为参数$p$对充电算法的影响。$p$是与电池充电相关的参数。在$p$较大时电池充电效率较高；较小时充电效率较低。从图7可以看出，在$p$变化范围内，MUC算法充电效用优于FEC算法和AEC算法。这是因为MUC算法可以将移动充电器可用充电时间合理分配给传感器节点。

图 7  参数$p$对不同充电算法的影响

下载: 全尺寸图片 幻灯片

图8反映的是不同节点分布对充电算法的影响。在3种节点分布中，密集分布的充电效果最优。这是因为在密集分布的网络中，巡游的移动充电器停车锚点数较少，移动能耗较低，传感器可以分配到更多的可用充电能量。

图 8  不同节点分布对充电算法的影响

下载: 全尺寸图片 幻灯片

图9为不同覆盖算法下的覆盖子集筛选图。图9(a)MNC算法试图寻找网络中覆盖节点最多的覆盖集合，并依次将集合加入覆盖子集中，直到覆盖所有节点。因此该算法的停车锚点数最少，路径能量消耗最低；图9(b)MUC算法试图寻找网络中覆盖节点充电增益最大的覆盖集合，直到覆盖所有的节点。与MNC算法相比，停车锚点数目和移动充电器路径能量消耗均增加，但是该算法可以更加合理地分配移动充电器的能量；图9(c)MAGC算法试图寻找网络中覆盖集合内平均节点增益最大的覆盖集合。该算法在寻找覆盖集合上趋向于单个节点或几个节点充电以保证其覆盖集合内平均节点增益最大。

图 9  不同覆盖算法下覆盖子集筛选图

下载: 全尺寸图片 幻灯片

图10为不同节点分布下覆盖子集筛选图。50个传感器节点分别采用图10(a)随机分布、图10(b)均匀分布、图10(c)密集分布进行MUC覆盖子集筛选。图10表明，随机与均匀分布不仅导致移动充电器移动轨迹较长且停车锚点数较多：分别为14个和19个。而密集分布方式下，不仅移动轨迹较短，而且停车锚点数较少：为11个，同时移动路径的能耗也较低。

图 10  不同节点分布下覆盖子集筛选图

下载: 全尺寸图片 幻灯片

图11为不同节点规模下子集筛选算法充电效用对比图。MUC算法相比于MAGC算法提高了35.9%；相比于MNC算法在50节点，80节点时充电效用略低。这是由于在移动充电器行驶与充电过程中，根据真实采样比例单位时间内行驶能量消耗远大于单位时间内充电能量消耗。同时MNC算法的停车锚点数也少于其他两种算法的。如图9所示，MUC算法是24个停车锚点，MNC算法是22个停车锚点，而MAGC算法是85个停车锚点。所以在网络规模较小时MNC充电效用最高。当节点规模达到110, 140, 170时，本文MUC算法充电效用也高于MNC。这是因为网络中覆盖子集的多样性使移动充电器的充电能量最大化，而弥补路径能量消耗较大的不足，MUC算法平均充电效用比MNC算法提高4.4%。

图 11  不同节点规模下子集筛选算法充电效用对比图

下载: 全尺寸图片 幻灯片

图12是3种算法下网络饿死节点数的对比情况。图12表明，相比于其他两种算法，MUC覆盖算法饿死节点数明显较少。

图 12  不同节点规模下子集筛选算法饿死节点数对比图

下载: 全尺寸图片 幻灯片

5.   结束语

本文提出了一种基于充电效用最大化的无线可充电传感网络有向充电调度方案。该方案首先根据网络中传感器节点能量和位置信息进行有向覆盖子集筛选，然后将覆盖区域的传感器作为整体，优化其分配的充电时间以使充电效用最大化。本文算法主要适用于中小规模无线可充电传感网络。

在大规模无线可充电传感网络中，由于存在多节点同时发出能量请求的情形，此时单移动充电器的部署模式难以满足现实需求。未来的工作中，将考虑大规模无线可充电传感器网络中多充电小车的有向充电调度问题。