无线可充电传感器网络高效在线充电算法
2019-04-01邓玉莲史雯隽武继刚
陈 辉 邓玉莲 史雯隽 武继刚
1(广东工业大学 广东 广州 510006) 2(天津工业大学 天津 300387)
0 引 言
传感器网络是由大量传感器节点组成的自组织网络。传感器节点具有采集、发送数据的功能。传感器节点的电池容量是决定传感器网络生命周期的关键因素之一。近年来，随着电磁耦合共振无线传输技术的发展，使得充电设备能够通过无线的方式对传感器节点进行充电，从而延长传感器网络的生命周期。具有供电模块和无线充电模块的移动充电设备MC(Mobile Charger)能够周期性地为传感器节点充电[1-3]。这种包含了移动充电设备的新型传感器网络被称为无线可充电传感器网络。
文献[4]采用经典的STP算法证明了充电车按照最短哈密尔顿回路移动方式延长了传感器网络生命周期。文献[5]结合传感器剩余电量和充电车路径规划提出一种新的算法,该算法没有考虑传感器通信耗能以及充电转化率问题。文献[6]将充电策略和通信策略相结合，使得充电车能够为传感器充电并能收集传感器产生的数据。该方式降低了数据的传输耗能，并将耗能大的传感器节点作为待充电节点，但在动态充电请求的网络环境中并不适用。文献[7]将整个传感器网络划分为几个子网络，在每个子网络中选取固定位置定期为传感器提供能量补给，同时提出一种分布式算法用于调整链路调度和数据收发速率，以提高传感器网络的整体效用。为了提高网络充电效率，文献[8]提出点对多充电方式，即一个充电车可以为一定范围内的充电车同时充电，但其仅仅提高同一时间内传感器充电数量，并没有考虑到单个充电车无法满足大规模网络能量需求情况。文献[1]采用K-means聚类算法将传感器网络划分为若干子区域，对于每个区域分派一辆充电车为该区域节点充电，有效地满足了大规模传感器网络能量需求，但多个充电车同时工作对网络负载和容错率要求较高。文献[9]研究充电车速度对整体网络能量供给的影响，在已确定的充电路径和具体充电时间内，指派充电车选取适当速度以达到充电延迟和移动延迟的平衡，但是该充电策略无法对新发送充电请求的传感器节点提供电量补给。文献[10]采用多个充电车为传感器节点充电以维持传感器节点永久运行，多个充电车同时工作可以减少移动距离带来的额外能量损耗，但对于充电车的路径选取并没有实现最短路径规划。文献[11]根据传感器节点剩余电量将充电请求分为紧迫请求和一般请求。充电车先对紧迫请求传感器进行充电，一般请求的节点的剩余电量可以支持到下一轮充电。由此保障WRSNs有最大数量的节点正常运行。文献[12]对无线可充电传感器网络中的传感器节点划分聚类，采用基于旅行商问题的最小生成树算法求解WRSNs的最大充电吞吐量问题，该方案延长了传感器网络生命周期，但没有考虑充电车携带电量及充电车移动耗能对整体路径规划的影响。文献[13]在无线可充电传感器网络充电调度策略中考虑了充电车移动耗能及携带电量，但该网络的充电调度策略是基于静态网络环境，即充电车在当前充电过程中接收到新的充电请求将作为下一个充电周期的待充电传感器节点。文献[14]研究了基于动态请求的无线可充电传感器网络，即充电车在执行充电任务的过程中同时接收并处理新的请求充电，新请求的出现可能会改变充电车路径。
本文研究基于动态请求的无线可充电传感器网络中充电车的充电任务调度策略，同时考虑充电车移动耗能和充电周期总电量对充电车路径规划的影响。本文提出一个基于贪心策略和一个基于聚类思想的在线算法规划充电车充电路径，实现网络中充电传感器数量的最大化。
本文的贡献点如下：
(1) 针对动态请求的无线可充电传感器网络，在充电车移动耗能和充电周期总电量两个约束条件下的充电传感器数量最大化问题，建立非线性整型数学模型。
(2) 提出一个基于贪心策略的在线算法。该算法选择距离充电车最近的传感器作为下一个充电节点，因此能够快速地规划充电车的充电路径。
(3) 基于聚类思想，提出另一个在线算法。该算法采用基于旅行商问题的最小生成树算法使得充电车在每个类中的充电路径构成一条回路的同时，减少移动耗能。
1 模型与问题定义
1.1 WRSNs 网络模型
如图1所示，WRSNs由若干个同构传感器节点、一个基站BS(Base Station)和一个充电车组成。正方形块表示传感器节点，用集合V={v1,v2,…,vn}表示。黑色正方形块表示发出充电请求的节点。每个传感器节点都配有无线发射器，能够给基站和充电车发送数据和充电请求信号。基站负责汇总、处理传感器的监测数据，调整充电车充电策略以及为充电车补充电量。充电车是一个搭载有供电块和无线收发器模块的移动充电设备。在充电过程中充电车可以接收充电请求信号，调整自身移动路径。WRSNs中采用点对点方式对传感器节点进行充电，即充电车在同一时刻位于特定位置通过电磁耦合共振技术将电量传输给单个传感器节点。初始状态下充电车位于基站。
图1 WRSNs充电示例图
Bi表示传感器节点vi的电池容量，当节点vi的剩余电量低于预定阈值Mi=α·Bi(0<α<1)时会向基站和充电车发送充电请求信号，即ci=(vi,REi,ri)，REi表示节点vi剩余电量，ri表示节点剩余时间。待充电集合Vc用来存放请求充电服务的节点，当充电车收到来自传感器节点vi的充电请求后，将节点vi放入待充电集合Vc中。
充电车是依靠电量提供动力支持移动的充电设备。在执行充电任务过程中，充电车根据接收到的充电请求信号为传感器节点提供充电服务。WRSNs中周期性指派充电车为传感器节点充电，用T表示充电周期时间。基站在一个充电周期T内为充电车提供的总电量为E，称为充电周期总电量。基站和充电车接收到充电请求后，充电车携带满电量Em从基站出发给传感器节点充电，其中Em为充电车电池容量，Em≤E。在充电周期T内，充电车自身移动和为传感器节点充电都会消耗其电量，因此当充电车电量不能满足待充电传感器所需电量时，充电车返回基站蓄电，蓄满电后再从基站出发执行充电任务。充电车在每一个充电周期T内可能多次返回基站蓄电。本文采用点对点的充电方式，即WRSNs中只有一个充电车为传感器提供充电服务，为了保障WRSNs中下一个充电周期能够顺利进行，充电车在每个充电周期T内需要满足两个条件：充电车要在充电周期T内回到基站；充电车最终有足够电量回到基站。
1.2 最大充电传感器数
最大充电传感器数是指在一个充电周期T内，充电车能够充电的最大传感器数目。
传感器节点因电量耗尽停止工作会影响整体WRSNs运行，为了保证WRSNs中有最大数量的传感器正常运作，优先对低于预定阈值的传感器节点充电。本文的目标是在每一次充电周期T中最大化充电传感器数量，以达到延长无线传感器网络生命周期的目的。
1.3 问题定义
本节使用的主要符号及其定义如表1所示。
待充电节点向基站发送充电请求，基站派出带有满电量Em的充电车为传感器节点充电。每一个传感器节点所需电量为常数L。在执行充电任务的过程中充电车根据接收到的新充电请求信号改变充电路径，充电车移动和为传感器节点充电将会消耗自身电量。
表1 符号及其定义
最大充电传感器数：
(1)
xi,j∈(0,1)i,j=0,1,…,n
(2)
式中：xi,j=0时，充电车没有经过边xi,j，即充电车没有访问vj；xi,j=1时，充电车经过边xi,j，即充电车为节点vj充电。
为了确保充电车每次执行充电任务时必须基站出发，最后回到基站，有如下约束条件：
(3)
式中不等式取值大于等于1表示在一个充电周期T内，充电车多次往返基站。
为了确保在每次充电周期中，只能向待充电的传感器节点提供至多一次充电服务，有如下约束条件：
(4)
为了确保充电车充电消耗时间不超过充电周期T，有如下约束条件：
(5)
为了确保充电车充电消耗时间不超过充电周期T，有如下约束条件：
(6)
最大充电传感器数问题目标函数可表示为如下非线性0-1整型规划问题：
(7)
定理1无线可充电传感器网络求解最大充电传感器数量问题是NP-hard问题。
证明：文献[12]研究的是充电车的最大充电吞吐量，该问题是NP-hard问题。该问题描述如下：在一定规模的传感器网络中存在n个待充电的传感器节点，充电车服务时间T内从基站出发最后返回基站期间所能提供充电服务的节点数。因此，充电车的目标为，在服务时间内找到一条最佳的充电任务路径，使得充电车实现最大的充电服务吞吐量。本文增加了充电车移动耗能和充电周期总电量两个约束条件，复杂化了充电车充电传感器数量最大化问题。NP-hard问题描述如下，在欧几里得平面上存在n个节点，每个节点具有相应的值，节点与节点的边有权值。要求找到一条路径从1节点出发遍历平面上的n个节点使得节点值之和最大且所经过的边权值之和不能超过约束值。在约束值范围内平面内的所有节点不一定都能被访问，每个节点至多只能被访问一次。在静态的无线可充电传感器网络充电车充电任务调度问题中，待充电集合Vc中待充电传感节点相当于欧几里得平面上存在的n个节点；充电路径中访问的传感器节点等同于遍历1至n节点；传感器网络中充电车总路径消耗不能超过时间T和总电量E等同于定向问题中所经过的边权值之和不能超过约束值。综上所述，充电车实现最大充电传感器数目等同于求解定向运动问题。动态充电请求网络是静态无线可充电传感器网络的一种特殊情况。因此，动态充电请求网络下求解最大充电传感器数是NP-hard问题。
2 算 法
2.1 Online_Greedy算法
本文首先提出一个实时的Online_Greedy算法。Online_Greedy算法运用贪心思想规划充电车移动路线，总是寻找距离当前节点服务时间最短的节点加入充电路径。如图2所示，Online_Greedy算法是在一个充电周期T内，充电车从基站出发选择距离基站服务时间最短的节点为第一个充电节点，随后每一个纳入充电路径的节点都是距离当前充电节点服务时间最短的传感器节点。
图2 Online_Greedy算法充电策略示意图
在WRSNs网络中，假设充电车当前充电节点为vi，下一个充电节点为vj。我们用Qj表示节点vj的服务时间。节点vj的服务时间为单个传感器充电时间C、从节点vi移动到节点vj的时间tij、从当前vj节点返回基站时间tj0三者时间之和, 即Qj=C+tij+tj0。用Wj表示节点vj的服务耗电量，节点vj的服务耗电量为单个传感器充电的电量L、从节点vi移动到节点vj的耗电eij、从当前vj节点返回基站的移动耗电ej0三者时间之和，即Wj=L+eij+ej0。
图2中实线箭头区域表示充电车第一段充电路径。充电车为下一个节点提供充电服务前，会计算自身剩余电量是否能够为下一个节点充电以及支撑其返回基站。若电量充足，充电车继续为传感器节点充电，反之充电车就返回基站蓄电，然后进行下一轮的充电。图2虚线箭头部分表示充电车返回基站蓄电后再次出发的第二段充电路径。表2为算法描述中符号和函数定义。
表2 算法符号和函数定义
Online_Greedy算法描述如算法1所示。在充电时间T和总电量E内Online_Greedy算法求解无线传感器网络最大充电传感器数量的时间复杂度为O(n)。
算法1Online_Greedy算法
输入:一个等待充电的传感器集合Vc,充电周期T,充电周期总电量E输出:始点为v0的充电路径P1: cur=v0;2: t=0;3: path_cost=0;4: while t
2.2 Online_MST_Cluster算法
实际环境中，传感器节点的分布可能会按照不同的区域集中分布，针对这种情况，本文基于聚类思想并加入了充电车移动耗能和总电量的限制，提出了Online_MST_Cluster算法。
Online_MST_Cluster算法先对当前待充电的传感器节点划分聚类，再计算生成的子聚类中所有的传感器节点实现全部充电所消耗的时间和电量，当充电的时间和电量消耗满足限制条件时，充电车从基站出发为该聚类充电，充电完成后返回基站，在充电时间T内反复迭代上述过程。
Online_Greedy算法是对单个节点提供充电服务，而在Online_MST_Cluster算法中，充电车为聚类内包含的所有传感器节点提供充电服务。Online_MST_Cluster算法的充电模型如图3所示。
图3 Online_MST_Cluster算法充电策略示意图
综上，Online_MST_Cluster算法是采用聚类迭代循环的方式寻找满足充电条件的传感器聚类。首先，充电车从基站出发，在已经划分好的K个聚类中选择满足充电条件的聚类，若存在的聚类无法满足充电条件时，调整K值重新划分聚类数目，直至出现满足充电条件的聚类，在已经超出时间T的情况下程序迭代将不再进行，算法具体描述如算法2所示。
算法2Online_MST_Cluster算法
输入:一个等待充电的传感器集合Vc, 充电周期T, 充电周期总电量E, 常数K输出:始点为v0的充电路径P1: Kinit = 1;2: K=Kinit;3: t=0;4: path_cost=0;5: while t < T do6: clusters=K_means(Vc, K) ; /∗采用K-Means算法将Vc划分为K个聚类: V1,V2,…,VK ∗/7: paths=MST (clsuters);/∗ 采用解决旅行商算法问题的最小生成树算法求得基站v0和每一个聚类最短回路∗/8: sorted (clusters, paths) ;/∗按照聚类gain值从小到大进行排序∗/9: for each cluster in clusters10: if cost+cost (cluster) ≤ E andt+t(cluster)≤T11: P←cluster;12: cost+=cost(cluster);13: t+=t(cluster);14: ifno cluster found to charge, then adjust K setting K=min{2K,|Vc|};15: if K==|Vc| and no cluster found to charge16: break;17: update Vc;18: K←Kinit;19: end while ;20: return P.
定理2在给定充电时间T内，采用Online_MST_Cluster算法去解决最大充电传感器数问题，该算法的时间复杂度为O(|V|2·lg|V|·T)，|V|是总传感器数量。
证明：显然，Online_MST_Cluster算法能够求解无线传感器网络最大充电传感器数问题，接下来我们分析算法的时间复杂度。k-means算法的时间复杂度为O(|Vc|·n)，其中n是k-means算法中的迭代次数。计算每个聚类gain时间复杂度为O(|Vc|2) 。随着聚类数K值的调整，在满足充电条件聚类中计算最大的gain值的时间复杂度为O(|Vc|2·lg|Vc|)。所以很容易证明受到充电时间T影响的算法时间复杂度为O(|Vc|2·lg|Vc|·T)=O(|V|2·lg|V|·T)，其中|Vc|≤|V|。
3 实验结果与分析
这一节将通过5组模拟实验对比2个算法的性能，实验的参数设置如表3所示。
表3 实验参数设置
实验是在固定范围的监测区域内进行模拟对比实验，基站位于监测区域内。实验参数如表3所示，每一组实验数据对应一幅实验结果图。由于不同传感器作业任务不同，传感器节点电量低于预定阈值Mi=α·Bi就向基站和充电车发送充电请求信号。
本文以一个充电周期T内被充电的传感器数量的多少来衡量充电算法的性能。
3.1 离线精确算法与两个在线算法
Offline_Aglo是基于穷举策略的离线精确算法。我们对比离线精确算法Offline_Aglo与两个在线算法Online_Greedy、Online_MST_Cluster的执行效果。其中离线精确算法Offline_Aglo是基于静态充电请求网络，而两个在线算法是基于动态充电请求网络。静态充电请求网络是每一个充电周期的待充电传感器节点都事先给定，充电车在执行充电任务的过程中接收到的新充电请求将作为下一个充电周期的待充电节点。离线精确算法Offline_Aglo给出当前静态充电请求网络的最优解。实验设有传感器节点数量为10～50，充电周期T=60 s，总电量E=100 q。
我们对比Offline_Aglo算法与两个在线算法Online_Greedy、Online_MST_Cluster在小规模网络中实现的最大充电传感器数量。如图4所示，横坐标表示WRSNs中部署的传感器节点数，纵坐标表示充电时间内的最大充电传感器数。从图4中可明显看到Offline_Aglo算法的执行效果一直优于Online_Greedy和Online_MST_Cluster算法。值得注意的是当传感器节点超过20个时，Offline_Aglo算法与两个在线算法之间的差距越来越大，造成这一现象的原因是，Offline_Aglo采用穷举法且充电周期中待充电传感器节点都已知。在实现最大化充电传感器数量问题上，Online_Greedy、Online_MST_Cluster算法与精确算法Offline_Aglo算法相比分别差40%、48%。文献[13]中Online_SPT、Online_K_Cluster与精确算法Offline_Appro分别差59%、51%。在小规模网络中，基于所有待充电传感器节点都已知的情况下，Offline_Aglo算法是最好的选择。然而，Offline_Aglo算法代价大，运行时间长，不适用于大规模的无线可充电传感器网络。
T=60 s E=100 q图4 离线算法和两个在线算法执行效果图
3.2 无线可充电传感器网络规模
这一小节对比Online_Greedy算法和Online_MST_Cluster算法在不同的无线可充电传感网络规模下充电周期内的最大充电传感器数。充电周期T=2 500 s, 总电量E=1 500 q, 传感器节点数300～750。
实验结果如图5(a)所示，从图中可知Online_MST_Cluster算法充电周期内的充电传感器数量一直明显优于Online_SPT算法。当网络中的传感器节点数量在300到500时，Online_Greedy算法充电周期内所充电的传感器数量波动较大，这是因为Online_Greedy选取的第一个充电节点会对后面的实验结果产生较大的影响。Online_MST_Cluster算法执行效果增长稳定。随着网络中传感器数量逐渐增大，Online_Greedy算法、Online_MST_Cluster算法实现充电的传感器数量分别占总待充电传感器数量67%、76%。
(a) T=1 500 s E=2 500 q
(b) T=3 000 s E=3 000 q图5 网络规模与最大充电传感器数
为了对比Online_Greedy算法和Online_MST_Cluster算法在大规模网络节点下的执行效果，实验继续扩大无线传感器网络规模，充电周期T=3 000 s，总电量E=3 000 q，传感器节点数750～1 200。 实验结果如图5 (b)所示，当传感器节点数在800到900时,Online_Greedy算法充电周期内实现的最大充电传感器数要大于Online_MST_Cluster算法。随着网络规模逐渐增大，Online_Greedy算法效果多次呈现上升后下降而后又上升的趋势，这是由于采用贪心策略规划充电车的充电路径，造成实验效果波动较大。Online_MST_Cluster算法一直处于稳定上升的状态，这是因为Online_MST_Cluster是先聚类后充电，每一次迭代都计算所消耗的时间及电量，因此实验效果比较稳定。当传感器节点数超过1 050时 ，Online_MST_Cluster算法执行效果明显优于Online_Greedy算法。
3.3 总电量
这一小节将研究充电车携带电量E对充电周期内实现最大充电传感器数的影响。如图6(a)所示，充电时间T=1 500 s，传感器节点数为1 500，总电量值范围700～1 600。随着总电量不断增大，两个算法充电时间内实现的最大充电传感器数呈缓慢增长的趋势。当E值范围在700～1 400时，Online_Greedy算法执行效果优于Online_MST_Cluster算法，随着总电量继续增大，Online_Greedy算法的执行效果呈现不稳定状态，而Online_MST_Cluster算法一直处于稳定上升状态，最终在总电量E=1 400时超越Online_Greedy算法。
(a) T=1 500 s sensor_num=1 500
(b) T=3 000 s sensor_num=200图6 E与最大充电传感器数
同样地，我们继续增大总电量E值，观察电量大小对实验结果的影响，在图6(b)中，充电时间为T=3 000 s，传感器数量为2 000，总电量E值范围500～3 500。从图中可知Online_Greedy在充电周期内实现的最大充电传感器数波动较大，Online_MST_Cluster充电周期内实现的最大充电传感器数呈稳步增长趋势，当充电车携带电量较低时，Online_MST_Cluster算法效果不如Online_Greedy算法，但随着总电量的持续增大，Online_MST_Cluster算法的实验结果是优于Online_Greedy算法。 本文考虑了充电车移动耗能和总电量对充电周期内最大充电传感器数的影响，四组实验结果表明，Online_Greedy算法执行效果稳定性较差，波动较大。而Online_MST_Cluster算法执行效果稳定，随着网络规模和总电量增加，充电时间内的最大充电传感器数目也稳定增长，所以Online_MST_Cluster算法是求解闭合无线传感器网络最大充电传感器数问题的一种理想的解决方案。
4 结 语
本文研究动态请求的无线可充电传感器网络中最大充电传感器数问题，提出Online_Greedy和Online_MST_Cluster算法解决充电周期内如何实现最大化充电无线传感器数。考虑了充电车移动耗能和充电周期内总电量两个因素。其中，Online_Greedy算法时间复杂度低，运行效率高，Online_Greedy算法在大规模的无线传感器网络中执行效果稳定性较差，在小型的无线传感器网络中反而获得较高的效率。Online_MST_Cluster算法采用聚类划分的充电方式，不再单独处理单个传感器节点充电请求，而是对一个聚类中待充电传感器节点进行充电，大大减少了移动电量消耗。Online_MST_Cluster算法效果稳定，在大规模无线传感器网络中应用较好。在未来的工作中我们将重点研究充电车的充电路径调度策略，提高充电车携带电量，采用更新颖的聚类划分方式，来实现充电周期内最大充电传感器数量。
