1.   引言

近年来，无线传感器网络已广泛应用于农业、交通、环境监测等领域^[1]。为解决能量问题，一些学者提出采用移动设备(Mobile Equipment, ME)携带电能通过无线能量传输技术^[2]为传感器节点进行能量补充，采用这种方式的无传感器网络(Wireless Sensor Network, WSNs)称为无线可充电传感器网络(Wireless Recharging Sensors Networks, WRSNs)^[3]。同时，由于节点的能量有限，大量监测数据通过多跳传输将很快耗尽节点的能量，一些学者提出采用ME移动至节点处收集数据，大大减少了数据传输的能耗^[4]。

为更进一步解决能量问题，一些学者将上述方法进行结合，在网络中分别部署带无线充电功能的ME和带数据收集功能的ME。Wang等人^[5]提出数据收集和充电分别使用不同的ME，通过K-means算法进行网络划分来最小化数据收集时延。文献[6]针对大规模WSN提出锚点选择算法，并使用拉格朗日对偶方法进行问题求解。Wang等人^[7]提出了使用一个数据采集设备和多个充电设备的设备调度策略，降低了网络延迟。

由于无线充电和无线数据传输所使用的频段不同，所以可以同时进行充电和数据收集，即可以使ME既具备无线充电能力又兼备数据收集功能。Guo等人^[8,9]提出了一种联合无线充电及数据收集的分布式算法，在保证网络数据正常传输的前提下延长网络的寿命。Xie等人^[10]提出了一种近似算法将整个网络的能耗降到最低。Zhao等人^[11,12]提出了联合充电和收集数据框架，在保证数据正常传输的约束下，延长了网络的寿命。

然而，上述研究基本都是将充电规划和数据收集分开处理，对于分别部署无线充电设备和数据收集设备的研究来说，分别规划了两种设备的移动路径、充电策略和数据收集策略；对于移动设备兼备充电及数据收集功能的研究，一般是先根据传感器节点的充电需求来规划移动设备路径，再根据路径来进行数据收集。实际上，在规划ME的移动策略时应同时考虑传感器节点对电能的需求以及对数据传输的请求，这是一个多目标优化问题。

本文联合考虑充电及数据收集两个维度，建立多目标优化模型并设计算法进行问题求解。与前人研究相比，本文的创新之处在于：(1)在ME兼备无线充电及数据收集功能时，同时考虑最大化充电效率及最小化数据收集时延两个目标，建立了多目标优化模型；(2)在ME携带的能量有限且采用一对多方式进行无线充电和数据收集的前提下，设计了ME的移动策略和充电策略；(3)本文设计了基于虚拟节点的多目标蚁群优化充电规划(Virtual Node Multi-Objective Ant Colony, VN-MOAC)算法对该问题进行求解。

2.   问题描述及建模

在2维区域D内部署有无线可充电传感器网络，网络内有1个充电服务站CS、1个ME、$n$个无线传感器节点$S = \{ {s_1},{s_2}, ·\!·\!·, {s_n}\}$, $i \in \left[ {1,n} \right],i \in \mathbb{Z}$, ${s_i}$表示编号为$i$的传感器节点。各节点部署后不再移动，每个节点的地理位置坐标已知；传感器节点的电池容量为${E_{\max }}$，为了保证节点能够正常工作，节点的电量不能低于${E_{\min }}$，初始时所有节点的电量均为${E_{\max }}$。

移动设备ME的充电半径为$r$，数据收集半径为$R$，以一对多的方式为传感器节点充电，移动速度为$v$。ME携带的行驶能量和充电能量分别为${E_{\rm{M}}}$和${E_{\rm{C}}}$，在网络中游走会消耗行驶能量，为节点充电时会消耗充电能量。按照文献[13]的方式，假设网络由边长为$r$的全等正六边形组成的虚拟蜂窝网格覆盖，每个正六边形组成一个小区(cell), ME移动到每个小区的中心后停留在该位置给本小区内的节点充电并收集数据。本文的网络模型如图1所示。

图 1  网络模型

下载: 全尺寸图片 幻灯片

假设蜂窝网格中包含传感器节点的小区的集合为$H$，对这些小区进行重编号，第$k$个小区($k = 1,2,·\!·\!·, \left| H \right|$, $k \in \mathbb{Z}$)内包含的传感器节点的集合记为${H_k}$，显然有

当ME进入第$k$个小区后，会在小区中心停留并通过无线方式对该小区内的传感器节点进行充电，对于第$k$个小区内的传感器节点$h_i^k$($h_i^k \in {H_k}$)，节点到中心的距离为$d_i^k$，则有

其中，$U_i^k$为节点$h_i^k$的充电接收功率，$U\,$为ME的无线充电发射功率，充电效率函数$\eta (d_i^k)$是一个与距离有关的减函数^[14]。由于ME携带的能量有限，并不一定能保证到达每个小区都能够为小区内的节点都充满电，假设ME到达第$k$个小区的中心时的时刻为$t$, ME在小区内停留的时间为${\tau _k}$，小区$k$中节点$h_i^k$的当前电量为$e_i^k(t)$，由于ME在小区中心停留的时间长短影响小区内传感器节点的充电时长，并且当节点电量充满至${E_{{\rm{max}}}}$后电量将不再上升，因此可能会出现以下3种情况：(1)停留时间很短，小区内所有的节点均未充满；(2)停留时间很长，小区内所有的节点均已充满；(3)停留时间介于前两者之间，此时，有的节点被充满，有的节点还没有被充满，被充满的节点将保持电量${E_{{\rm{max}}}}$。从时刻$t$开始，节点从当前电量$e_i^k(t)$充满至${E_{{\rm{max}}}}$需要的时间$\tau$满足

其中，$p_i^k$为节点$h_i^k$的能量消耗率，对于小区$k$中的所有节点，均可根据式(3)求出各自的时间$\tau$，令${a_k} = {\rm{min}}\,\tau$, ${b_k} = {\rm{max}}\,\tau$，则有当停留时间${\tau _k}$满足${\tau _k} < {a_k}$时所有节点均未充满电，当${\tau _k} \ge {b_k}$时所有节点均已充满电，当${a_k} \le {\tau _k} < {b_k}$时有部分节点已经充满，有部分节点还未充满，其关系满足

对于传感器节点采集的数据，当ME到达小区中心时，同步收集传感器节点的数据。在实际应用中，ME不可能频繁为网络中的传感器节点充电和数据收集，大部分时间里ME停留在服务站休整并接收节点的数据请求^[15]。第$k$个小区内的传感器节点的数据请求时间记为$t_i^k$($1 \le i \le \left| {{H_k}} \right|$), ${t_k}$时刻ME到达该小区收集数据，数据收集的时间忽略不计，则该小区内传感器节点数据收集的时延为

从上述分析可以看出，传感器节点的充电需求取决于其自身的能量消耗情况，数据请求则取决于应用需求，并且每个小区内的传感器节点的充电需求和数据传输请求不同，此时ME的移动路径需同时考虑以上两个因素。为衡量ME的充电性能，希望ME携带的充电能量和行驶能量应尽量为传感器节点服务，然而由于ME携带能量有限，在从服务站出发后经一系列小区最后返回服务站时均可能剩余部分能量，因此应最大化ME的能量利用率$\phi$，其中$L$表示完成对所有小区的传感器节点充电任务时ME返回服务站的次数。

同时，为衡量ME的数据收集性能，应最小化网络中传感器节点的数据时延，本文采用网络中所有传感器节点的平均时延$\overline {\Delta \tau }$来刻画。

最大化ME的充电效率和最小化数据收集时延这两个目标均与ME的行驶路径和充电时间有关，ME在某一小区内停留时间长则该小区内的节点能量补充充分，节点的寿命将延长，但这会造成其他小区内节点的数据时延变大，这两个目标存在矛盾。因此本文的优化问题OPT-D为${\rm{Obj}}:\arg \mathop {{\rm{min}}}\limits_{Q,{\tau _i}} F =$$\{ {\phi ^{ - 1}},\overline {\Delta \tau } \}, \;\;{\rm{s}}{\rm{.t}}{\rm{.}}\ {式}\left( 1 \right) - {式}\left( 5 \right)$。其中，ME的行驶路径$Q$和每个传感器节点的充电时间${\tau _i}$为变量，${E_{{\rm{max}}}}$, ${E_{{\rm{min}}}}$, ${E_{\rm M}}$, ${E_{\rm{C}}}$, $p_i^k$, $U$, $t_i^k$, $v$等均为已知量。

3.   算法设计

本节将设计算法求解优化问题OPT-D。首先分析OPT-D的复杂性，可将其规约为经典的带距离约束的车辆路径问题(Vehicle Routing Problem, VRP)来证明该问题属于NP-Hard问题。将OPT-D问题转化为判定性描述后，对于任意给定的可行ME移动路径及在每个小区的停留时间，可以从服务站开始依次求得ME到达各个小区的时间，进而可以计算优化目标值$\phi$和$\overline {\Delta \tau }$，该验证过程的时间复杂度为$o(n)$，则OPT-D问题可在多项式时间复杂度验证。然后令${P_{\rm{M}}} = 1$, $\Delta \tau _i^k = 0$, $\eta (d_i^k) = 1$, $v = 1$，则可构建OPT-D问题与带距离约束的VRP的规约关系，规约过程的时间复杂度为$o(n)$。可以看出，带距离约束的VRP是OPT-D问题的特例，特例属于NP-Hard问题，因此OPT-D问题属于NP-Hard问题。

3.1   路径规划策略

由于ME的行驶能量有限，不能采用文献[13]中的方式，通过一条以服务站为起点和终点且经过所有小区的Hamilton回路来为节点充电，因此本文的路径规划允许当ME的行驶能量不足时多次返回服务站进行能量补充。如图2所示，路径规划由一系列连续的调度${C_r}$组成，每个调度满足网络中所有节点均被充电1次。每个调度包含1个驻站过程和若干连续的工作轮。根据文献[6]ME的驻站比(在服务站的驻站时间与调度总时间的比值)越大，ME的充电效果越好。假设ME的驻站时间是固定的且相对较长，数据收集时间可忽略不计。每个工作轮ME从服务站出发访问一部分小区并为其中的节点充电及收集数据，当行驶能量不足时返回服务站，各个工作轮所服务的小区不同。在调度中节点的能量均要满足大于${E_{{\rm{min}}}}$。

图 2  路径规划示意图

下载: 全尺寸图片 幻灯片

设ME在调度${C_r}$中的第$u$($1 \le u \le L$)个工作轮的路径为${Q_u} = \left( {{{{π}}_0},{{{π}}_1},{{{π}}_2}, ·\!·\!· ,{{{π}}_{{m_u}}},{{{π}}_0}} \right)$，则可以求得该调度的总行驶时间${\tau _{{\rm{tsp}}}}$满足式(9)，其中${{{π}}_0}$代表服务站CS, $\tau _{{\rm{tsp}}}^u$表示ME在第$u$个工作轮的行驶时间，${m_u}$(${m_u} \in \mathbb{Z}$)表示该工作轮中遍历的小区中心的数量。

进而可以得出该调度内ME消耗的行驶总能量和充电总能量分别满足式(10)和式(11)。

3.2   均衡化充电策略

对于充电时间，ME的充电能量也是有限的，为了将ME携带的充电能量补充到各个传感器节点，应尽量使各个节点寿命均衡，文献[16]提出了一对一充电的均衡化充电策略，本节在此基础上设计了一对多充电的均衡化充电策略，该策略通过最小化所有节点剩余生命的方差来确定在各个小区的充电时间。

在任意时刻$t$，小区$k$中的传感器节点$i$的剩余生命$l_i^k(t)$为

根据式(12)和式(4)，可以得出当${t_k}$时刻ME行驶到小区$k$的中心并在该小区停留时长为${\tau _k}$时，在(${t_k} + \tau _k^{}$)时刻小区内的节点的剩余生命$l_i^k({t_k} + {\tau _k})$及其他小区$h$($h = 1,2,·\!·\!·, \left| H \right|$, $h \in \mathbb{Z}$)内的节点$j$的剩余生命$l_j^h({t_k} + \tau _k^{})$。进而可以得出在(${t_k} + \tau _k^{}$)时刻，网络中所有节点的剩余生命的均值$\overline {l({t_k} + \tau _k^{})}$满足式(13)

则可以求得在(${t_k} + \tau _k^{}$)时刻网络中所有节点剩余生命的方差${s^2}({t_k} + \tau _k^{})$为

式(14)是关于$\tau _k^{}$的一元二次方程，通过方差最小化可以得出在每个小区中心的停留时间$\tau _k^{}$，但由于被充电小区内的节点的剩余生命是关于停留时间的分段函数，这会导致式(14)的求解很困难。因此本文将ME停留的小区中心点近似为一个虚拟节点来求解充电时间。

虚拟节点的消耗功率$p_k^{}$, ${t_k}$时刻的剩余能量$e_k^{}({t_k})$、最小电量$E '_{\!\!{\rm{min}}}$均与节点的接收功率函数相关，所以这里采用小区$k$中的节点的带权均值来虚拟为虚拟节点的$e_k^{}({t_k})$, $p_k^{}$及$E'_{\!\!{\rm{min}}}$，即

则可以得出虚拟节点${\psi _k}$的剩余生命及其他虚拟节点${\psi _h}$的剩余生命

代入式(13)、式(14)可得在(${t_k} + \tau _k^{}$)时刻，网络中所有节点的剩余生命的均值$\overline {l({t_k} + \tau _k^{})}$和方差${s^2}({t_k} + \tau _k^{})$。此时，最小化方差即可求出ME在每个小区的停留时间。通过最小化方差可以使节点之间的剩余生命尽量均衡，但方差仅反映波动情况，可能会出现方差很小但是网络中的能量整体下降的情况，如果这种情况一直持续，则会导致网络过早死亡，为此需引入约束式(18)，如果该约束导致无解，直接将节点充满电，此时即使将传感器节点充满电也无法使网络平均寿命大于充电前的平均寿命。

3.3   问题求解

本文设计了一种基于虚拟节点的多目标蚁群优化充电规划算法(VN-MOAC)对问题进行求解。VN-MOAC算法主要是对状态转移策略和信息素更新策略进行了改进。在状态转移策略的设计中，综合考虑了信息素浓度、节点之间的距离以及节点的剩余生命，避免了算法陷入局部最优。设蚂蚁的总数量为$m$，初始时刻蚂蚁$k(k = 1,2, ·\!·\!· ,m)$从服务站出发选择不同的小区进行路径选择，蚂蚁$k$访问完小区$i$后按式(19)选择下一小区$j$。

其中，${\rm{a}}{{\rm{d}}_k}$表示蚂蚁k没有访问过的小区集合，${\rm{rs(a}}{{\rm{d}}_k})$表示在${\rm{a}}{{\rm{d}}_k}$集合中随机选择一个小区；${\sigma _{ij}}(t)$是第$t$轮蚂蚁k从小区$i$到小区$j$的路径上的信息素浓度；${\mu _{ij}}(t) = 1/{d_{ij}}$, ${d_{ij}}$为小区$i$到小区$j$之间的欧式距离；${\omega _{ij}}(t) = 1/l_{{\rm{life}}}^{ij}(t)$, $l_{{\rm{life}}}^{ij}(t)$表示访问完小区$i$后到达小区$j$时小区$j$对应的虚拟节点的剩余生命时间。

在信息素更新策略中，本轮的信息素根据上一轮的残留信息素和精英蚂蚁在路径上留下的信息素进行更改，第$t + 1$轮的信息素浓度按照式(20)进行更新。

其中，$\rho$($\rho \in (0,1)$)为信息素的挥发系数，$\Delta \sigma _{ij}^k(t)$表示精英蚂蚁$k$在路径$(i,j)$上产生的信息素浓度，可由式(21)求得，${\rm{BP}}(t)$表示优化问题的Pareto解集，${U_{{\rm{BP}}(t)}}$为Pareto解集${\rm{BP}}(t)$对应的精英蚂蚁集合。

其中，$\xi$为调节因子，${\phi _k}$和$\overline {\Delta {\tau _k}}$分别表示精英蚂蚁$k$求得的总能量利用率和平均时延，${L_k}$和$D_Q^k$分别表示1次调度中返回服务站的次数和行驶路径长度。

3.4   算法复杂度分析

VN-MOAC算法的主要步骤是计算状态转移和信息素更新。计算状态转移主要是计算式(19)，该过程的时间复杂度为$O({\rm{|}}H{{\rm{|}}^2}m)$，其中，${\rm{|}}H{\rm{|}}$为小区数量，$m$为蚂蚁的个数；计算信息素更新主要是计算式(20)和式(21)，求得Pareto解集中的精英蚂蚁集合的时间复杂度为$O({m^2}B\lg {m^2}B)$，其中，$B$为目标函数的个数，在此基础上更新每只精英蚂蚁行驶路径上的信息素时间复杂度为$O({\rm{|}}H{{\rm{|}}^2}{m^2}B\lg {\rm{|}}H{{\rm{|}}^2}B)$。因此，算法的时间复杂度为$O({\rm{|}}H{{\rm{|}}^2}m + {\rm{|}}H{{\rm{|}}^2}{m^2}B$$\cdot\lg {m^2}B)$。

4.   仿真结果及分析

4.1   参数设置

在${\rm{1000}}\;{\rm m} \times {\rm{1000}}\;{{\rm{m}}}$的区域内布置50个传感器节点，服务站位于坐标${\rm{(0\;m,0\;m)}}$处。仿真工具是MATLAB R2016a。仿真时选取的参数为${E_{{\rm{max}}}}=$${\rm{ 10}}{\rm{.8\;kJ}}$, ${E_{{\rm{min}}}} = 540\;{\rm{J}}$^[10], ${E_{\rm{M}}}{\rm{ = 20\;kJ}}$, ${E_{\rm{C}}}{\rm{ = 20\;kJ}}$, $v = 8\;{\rm{m/s}}$, $U = {\rm{10\;W}}$, ${P_{\rm{M}}} = {\rm{100\;W}}$, ${p_i}{\rm{ = }}0.01 \sim$$1\;\rm W\,$，采用文献[14]中的充电效率函数。VN-MOAC算法相关参数为：最大迭代次数$M = 150$, $m = 20$, ${q_0} = 0.8$, $\rho = 0.4$。此外，根据文献[16]给定状态转移策略的权重系数$\alpha = 1$, $\beta = 5$, $\gamma = 4$。

为验证本文算法的有效性和性能，在3种场景下进行实验验证，L1场景为节点随机分布，L2场景为大部分节点集中于区域中心，L3场景为大部分节点集中在某一处，3种场景基本涵盖了无线传感器网络的一般情况。L1：随机布置50个节点； L2：按有界帕累托分布^[17]布置50个节点且热点位于${\rm{(0\;m,0\;m)}}$; L3：按有界帕累托分布布置50个节点，热点位于${\rm{(800\;m,800\;m)}}$。对比算法选用NSGA-II算法^[18]，每种场景独立运行50次实验。同时，为验证本文算法的收敛性能，选取随机布置的50个节点和100个节点进行收敛性对比分析，其中节点坐标及其所属小区的数据均来自文献[13]，统计50次实验的平均值进行分析。

本文所解决的是多目标优化问题，对比分析主要考虑以下几个指标：(1)目标值：ME的总能量利用率$\phi$越高以及数据传输的平均时延$\overline {\Delta \tau }$越低，算法性能越好；(2)Pareto解的个数${\rm{RN}}$: ${\rm{RN}}$越大，算法性能越好；(3)Pareto解集的均匀性${\rm{SP}}$：描述Pareto解集在目标空间中的分布范围，${\rm{SP}}$的值越小，解的分布越均匀，算法性能越好；(4)Pareto解集的分布范围$M^*_3$：衡量Pareto前沿的分布范围，$M^*_3$的值越大，算法性能越好。

4.2   实验结果分析

实验数据统计如表1和图3所示，表1展示了3种场景下各性能指标的最优值、最差值、平均值和中值。VN-MOAC算法的ME总能量利用率$\phi$最高值达到了95.85%，高于NSGA-II算法。3种场景下VN-MOAC算法得到的平均时延$\overline {\Delta \tau }$最优值要比NSGA-II算法分别缩短了8.19%, 34.58%, 11.29%。VN-MOAC算法中，Pareto解集的个数${\rm{RN}}$的平均值比NSGA-II算法分别增加了44.73%, 30.77%, 45.94%, Pareto最优解的均匀性${\rm{SP}}$的平均值优于NSGA-II算法23.74%, 5.96%, 7.81%。在Pareto最优解的分布范围$M_3^*$方面可以看出，VN-MOAC算法和NSGA-II算法搜索到的解的分布都比较均匀，而且解分布的范围也较广。实验结果表明本文提出的VN-MOAC算法在各个场景下的性能均优于NSGA-II算法。

表 1  VN-MOAC算法和NSGA-II算法计算结果比较

指标	网络场景	$\phi$ (%)			$\overline {\Delta \tau }$ (s)			${\rm{RN}}$			${\rm{SP}}$			$M_3^*$
		VN-MOAC	NSGA-II		VN-MOAC	NSGA-II		VN-MOAC	NSGA-II		VN-MOAC	NSGA-II		VN-MOAC	NSGA-II
最优值	L1	94.02	92.31		1663.82	1812.30		45	29		38.50	45.67		392.65	378.86
	L2	88.94	85.78		769.24	1176.02		35	25		161.93	180.14		391.60	342.24
	L3	95.85	93.36		1608.94	1813.72		49	27		85.69	105.50		373.73	294.36
最差值	L1	75.98	73.75		5184.72	5361.46		26	17		790.03	883.10		31.59	20.73
	L2	69.30	67.16		3784.31	3898.69		18	13		794.47	869.26		42.25	24.29
	L3	76.35	71.24		5197.55	5408.48		21	12		690.69	726.31		83.73	73.19
平均值	L1	85.01	83.47		3145.27	3359.45		38	21		389.43	510.69		192.43	167.94
	L2	80.17	75.44		2189.46	2411.95		26	18		391.85	416.68		220.62	202.72
	L3	85.98	82.76		3268.98	3333.71		37	20		363.16	393.92		187.60	166.90
中值	L1	84.86	82.84		3137.80	3145.03		38	22		410.53	527.60		125.62	95.47
	L2	82.34	74.66		2285.31	2329.71		27	19		352.32	406.76		204.86	171.06
	L3	87.81	82.48		3308.81	3365.68		38	21		347.66	384.47		182.56	172.99

下载: 导出CSV 

| 显示表格

图 3  3种场景下VN-MOAC算法和NSGA-II算法性能统计盒状图

下载: 全尺寸图片 幻灯片

3种场景下本文算法和NSGA-II算法的Pareto解的个数${\rm{RN}}$、Pareto解集的均匀性${\rm{SP}}$以及分布范围M₃^*的性能统计如图3所示，图3(a), 3(b), 3(c)为随机分布场景L1的各个性能指标对比图，图3(d), 3(e), 3(f)为偏中心分布场景L2的各个性能指标对比图，图3(g), 3(h), 3(i)为偏热点分布场景L3的各个性能指标对比图，可以看出本文算法在各个场景下的性能均优于NSGA- II算法。

图4展示了50个节点和100个节点下算法的收敛性对比分析情况，从图中可以看出，在120代之后50个节点和100个节点下算法均收敛，但100个节点的50组实验中最优Pareto解集中解的个数的平均值明显低于50个节点的实验，这是因为本文问题属于组合优化问题，当网络规模增大时其可行解空间变小，满足条件的Pareto解的数量将减少。同时，两组实验中每代的运行时间不同，100个节点的总运行时间长于50个节点，这是由于随着网络规模的增加计算量增大导致运行时间变长。

图 4  50个节点和100个节点下算法的收敛性对比

下载: 全尺寸图片 幻灯片

图5展示了VN-MOAC算法求解本问题在不同迭代次数下的Pareto前沿，算法在迭代120次之后得到的Pareto前沿的变化不大，前沿分布较为均匀，前沿部分出现的间断部分是由于本文研究的问题属于组合优化问题，可行解空间不连续造成的。

图 5  VN-MOAC算法在不同迭代次数下的Pareto前沿

下载: 全尺寸图片 幻灯片

5.   结束语

本文首次提出基于多目标优化的无线传感器网络移动充电和数据收集算法，在ME的行驶能量和充电能量分开且有限的非理想情况下，采用一对多的方式为节点充电和收集节点数据，设计了ME路径规划策略、均衡化充电策略，并设计了VN-MOAC算法对本文问题进行求解。仿真表明，本文算法在3种网络场景下的各项性能指标均优于NSGA-II算法。本文算法适用于中小规模网络，在大规模网络应用场景下，需要采用多个ME进行协作充电和数据收集，下一步将研究多ME充电和数据收集问题。