随着无线通信技术、传感技术和微电子技术的日趋成熟, 作为实现物联网必不可少的基础设施之一, 无线传感器网络(wireless sensor networks, 简称WSN)被广泛应用于环境监测^[1]、森林火灾报警^[2]、灾难自救^[3]和医疗护理^[4]等方面.然而传感器节点的电池能量严重受限, 成为影响传感器网络性能和发展的关键因素.

近期, 无线充电技术(wireless charging technique)^[5]和可充电锂离子电池技术^[6]的进步, 为WSN的能量问题提供了实际可行的解决方案.在这两种技术的支持下, 无线可充电传感器网络(wireless rechargeable sensor networks, 简称WRSN)^[7-10]兴起, 并且目前已有若干研究对WRSN充电策略和算法进行了探讨, 其中大部分研究关注于离线充电(offline recharging).离线充电假设各个传感器节点的能量消耗率始终固定不变, 移动充电器(mobile charger, 简称MC)根据网络中节点前一运行阶段的能量消耗提前规划充电路径, 充电过程中, MC沿着规划路径周期性运动, 为传感器节点补充能量.然而, 由于WSN通常部署在监测区域与周围环境紧密接触, 实际情况下, 传感器节点的能量消耗受周围环境影响表现出较高的动态性和多样性^[11], 因此, 节点的能量消耗率并不是固定不变的, 那么MC按照离线充电中预先规定的充电路径和策略进行充电, 就会造成传感器节点的能量饥饿(energy starvation)及充电算法性能的严重下降.可见, 离线充电策略在实际传感器网络环境下并不适用.针对离线充电的缺陷, 有研究者提出在线充电机制(online recharging).在线充电中, MC根据传感器节点的实际剩余能量状况实时动态地制定充电策略, 并及时响应节点的充电请求.相比于离线充电, 在线充电更好地适应实际节点的能量需求和变动.然而, 在线充电策略的设计存在如下挑战.

1) 由于节点的能量消耗率动态变化, 则不能提前获知各传感器节点的剩余能量, 以便预先规划MC的充电路线.在这种情况下, 如何根据节点的实际剩余能量状况实时动态地规划MC的充电路线, 及时为需要充电的节点补充能量, 且充电过程尽量降低饥饿节点比率具有挑战性;

2) 电响应具有公平性, 避免待充电节点由于长期得不到能量补充而失效;

3) 电过程要尽量降低MC移动引起的能量开销, 把MC携带的能量尽可能转化成为传感器充电的有效能量, 并达到饥饿节点比率和MC充电代价之间的平衡.

由于WSN中节点失效会产生数据丢失、链接失效甚至网络断开等问题^[12], 如何有效防止传感器节点陷入能量饥饿从而造成节点失效, 是WRSN无线充电(又称为移动充电)策略要解决的关键, 同时也是衡量充电算法性能的主要指标.然而, 现有在线充电相关工作存在没有充分考虑对节点的及时充电和MC对节点充电请求响应公平性的缺陷, 这同样造成了充电过程中节点能量饥饿^[13].当网络中需要监测的目标较多、请求充电的节点数量增多时, 节点能量饥饿问题尤为明显.为此, 本文提出能量饥饿避免的在线充电策略(energy starvation avoidance online charging scheme, 简称ESAOC):首先, 利用节点的剩余能量变化估计节点的当前能量消耗率, 据此计算每个待充电节点的最大充电容忍延迟及选择某一待充电节点作为下一充电节点时, 其他待充电节点的最短等待时间; 其次, 通过不断更新并比较传感器节点的最大充电容忍延迟和最短等待时间, 始终选择使待充电节点饥饿数量最少的节点作为充电候选节点, 以尽量避免大部分节点陷入能量饥饿.为提高充电效率, ESAOC在充电候选节点集中选择能够尽快完成充电的节点作为下一充电节点.相比于已有工作, 本文创新性如下.

1) 目前已有的WRSN充电策略多属于离线充电, 在线充电的相关研究相对较少.本文提出WRSN在线充电机制, 根据传感器节点的实际剩余能量情况, 实时动态地制定充电策略, 及时满足待充电节点的充电请求, 以尽量避免节点陷入能量饥饿;

2) 提出在线充电策略要以最小化网络饥饿节点比率的同时, 降低MC的充电代价和节点平均充电延迟为设计目标, 并应兼顾公平性, 避免节点长期得不到充电饥饿失效的思想;

3) 我们设计下一充电节点选择算法时考虑动态能量消耗率, 根据动态能量消耗率不断更新节点当前最大充电容忍延迟和某一节点被选为下一充电节点时其他待充电节点的最短充电等待时间, 通过比较这两个值, 始终选择使待充电节点陷入饥饿数量最少的节点作为充电候选节点来降低网络中的饥饿节点数量.相比离线充电, 本文考虑动态能量消耗率能更为准确地反映节点实际剩余能量状况, 从而使下一充电节点的选择更为合理;

4) 为提高MC能量利用率, 提出节点剩余能量低于门限值时再发送充电请求, 并对充电请求发送门限值进行了理论分析和推导;

5) 通过大量实验仿真对ESAOC的性能进行验证.仿真分析表明:与现有的几种在线充电策略相比, ESAOC不仅能有效解决节点的能量饥饿问题, 同时具有较低的充电延迟和充电代价.

1 相关工作

无线能量传输技术是近年来新兴的无线传感器网络能量问题解决方向, 相关研究可分为离线充电和在线充电两类.目前, 离线充电策略的相关研究相对较多, 如:

●  文献[14]同时考虑了MC充电过程的路径规划问题和数据收集问题, 提出的算法能够综合优化数据传输效率和MC的移动充电路径;

●   Peng等人^[15]和Li等人^[16]主要关注如何通过寻找一条最佳移动充电路线来最大化网络的生存时间;

●   Shi等人^[17]假设移动充电器携带的能量不受限制, 该文献主要探讨周期性地对传感器节点进行充电, 并在充电的每个周期尽量延长移动充电器的休息时间(即在服务站的时间); 同时, 文章还讨论了对多个传感器节点同时进行充电的场景;

●  文献[18]对在有限的数据延迟内同时优化移动充电的效率和数据采集的效率进行了研究, 并提出了相应的机制, 通过对网络中具有最少剩余能量的节点进行充电来最大化网络的使用效率;

●   Wu等人^[19]虽然对移动充电模型进行了讨论并给出了几种可行的无线充电解决方法, 但这些方法均是针对一维结构的传感器网络提出的(即传感器网络节点呈线性分布).而实际环境中, 传感器网络节点的分布大都是二维, 甚至是三维结构的, 因此, 该文献所述的无线充电方法在现实多维传感器网络中并不适用;

●  文献[20]的WerMDG策略中, 传感器节点能够根据自身剩余能量状况调整数据传输率和MC的充电路径, 并且MC同样能够调整对每个节点的充电时长来最大化网络的充电效率;

●   Fu等人^[21]讨论了基于RFID的无线可充电传感器节点充电问题, 提出了通过规划移动RFID读写器的最佳移动路线来最小化为网络中节点充电的延迟, 使充电后传感器节点的剩余能量高于给定阈值;

●   Lin等人^[22]关注于无线充电车辆之间的充电协作, 提出的GTCharge机制中, 充电过程被转化为无线充电车辆间的协作游戏来寻求每个充电车辆完成充电任务时的最大利润;

●  文献[23]提出了工业无线可充电传感器网络中基于网格的联合路由和充电算法:首先, 根据MC的充电特性设计路由协议; 其次, 根据路由过程引起的能量消耗, 为不同的充电地点分配不同的充电时间, 以实现能量平衡;

●  文献[24]把最小化充电延迟问题转化为速度变化的旅行商问题, 并提出利用线性规划来规划移动充电器的充电路径, 并设置移动充电器为每个传感器节点的充电时间长短.

在线充电中, MC根据传感器节点的能量剩余状况实时制定充电策略.He等人^[11]提出了抢占式最近工作优先充电策略(nearest-job-next with preemption, 简称NJNP), 尽管NJNP通过始终选择离移动充电器最近的待充电节点作为下一充电节点达到了较高的充电效率, 然而该策略没有考虑MC对充电请求响应的公平性, 容易造成某些传感器节点由于长期得不到充电服务而陷入能量饥饿; 文献[25]提出了基于剩余能量实时感知的充电算法, 然而该工作主要关注于活跃与不活跃的节点调度机制; 文献[26]提出, 在线充电过程应尽量避免节点陷入能量饥饿, 然而该策略中移动充电器能量无限大的假设不符合实际情况, 并且没有考虑节点能量消耗率的变化对实际节点剩余能量值的影响, 造成充电路径规划不合理从而导致节点能量饥饿.

Wang等人^[27]为消除充电过程缓慢造成数据失效, 采用一辆专用车辆来收集数据; 另外, 利用多辆车辆为传感器节点充电.为降低充电延迟和充电器移动造成的能量开销, 文中把传感器节点按地理位置分成多个簇, 每辆充电车辆仅为一个簇中的节点提供充电服务.文中把充电调度问题转化为具有能量约束和充电截止时间限制的最优化利润旅行商问题.利润被定义为充电器传输给传感器节点的能量总量减去MC运动到该节点需要的能量开销.之后, 作者分别提出两种算法来解决该问题, 并在得到充电路径后, 根据节点的剩余生存时间调整充电路径, 以使节点在电池能量耗尽前被充电.与此策略相比, ESAOC具有以下优势.

1) ESAOC仅需要一个移动充电器, 而此策略需要多台移动充电器;

2) 此策略需要对传感器节点进行分簇, 簇的维护产生能量开销, 此外, 簇的大小对充电策略性能影响较大; ESAOC无需分簇, 节省了簇维护的能量开销;

3) 此策略虽提出传感器节点能量消耗率动态变化, 但假设距离基站跳数相同的传感器节点能量消耗率均相同, 不符合实际情况; 而ESAOC对节点能量消耗率的估计同时考虑了能量消耗的实时性和节点能量消耗的历史统计, 更加合理.

2 系统模型和问题描述 2.1 系统模型

本文无线可充电传感器网络系统模型由网络模型和充电模型组成.假设N个传感器节点随机分布在半径为D的圆形区域内, 唯一的基站位于该圆形区域的中心.网络模型为(V, W, E, R, D), 其中, V={v₁, v₂, …, v_N}是网络中节点的集合, v_i代表第i个传感器节点.W={d_ij=(v_i, v_j)|v_i, v_j$\in $V}是权重的集合, 其中, d_ij表示节点v_i到v_j的欧几里得距离.通过集合V和集合W, 基站可以获知整个网络的分布情况.E为传感器节点的能量容量, R={r₁, r₂, …, r_n}为各传感器节点能量消耗率的集合, 每个节点的能量消耗率随着周围环境动态变化.此外, 假设基站的能量和通信能力足够大, 它能够直接传输数据给移动充电器MC.MC为带有高容量无线充电电源并具有一定计算和通信能力的移动设备, 如车辆或机器人.移动充电器在传感器网络部署区域中移动, 周期性地为传感器节点充电.当MC完成充电任务或能量不足时返回基站补充能量, 为下一次充电服务做准备.充电模型表示为(1, P, c, v, η), 1表示网络中只有一个MC, 每个MC的电池容量为P, 运动速度为v, 运动单位距离的能耗为c, 对传感器节点的充电效率为η.整个系统模型如图 1所示.

系统工作过程如下:每个传感器持续监测它所在区域, 并通过多跳通信的方式向基站发送感知消息.同时, 各传感器节点持续测量自己的剩余能量值, 一旦发现剩余能量值低于门限值E_thred, 就以类似发送感知消息的方式立即向基站发送充电请求.如, 节点i充电请求的格式为〈ID_i, RE_i, ts_i, urg=1〉 ,其中:ID_i为传感器节点的ID号; RE_i为该节点的剩余能量; ts_i是发送的时间戳; urg=1表明这是一个充电请求消息, 目的是为了和节点发送给基站的普通能量通告消息相区别.基站既能接收节点的感知消息, 又能接收节点的充电请求及能量通告, 并以长距离通信的方式把收到的充电请求直接发送给MC.初始时, MC位于基站所在位置, MC维持一个充电服务池, 用来存放节点的充电请求消息.当收到充电请求时, MC按照后文第3节描述的充电算法选择下一充电节点.MC具有4种状态, 分别为空闲、移动、充电和回归状态, 如图 2所示, 空闲状态表示MC没有任何充电请求; 移动状态说明MC已选好下一待充电节点并向该节点移动; 充电状态显示MC正在为节点充电; 回归状态为MC已完成充电任务或能量不足, 正在返回基站补充能量.

2.2 问题描述

传统的WRSN离线充电策略大都假设传感器节点的能量消耗率是固定不变的, 各时刻各个节点的剩余能量能够提前预知, 因此哪些节点在什么时刻将要发送充电请求都是可以提前预知的, 这样就能根据节点剩余能量状况提前规划MC的最优充电路径, MC沿着规划路径周期性地为传感器节点充电.然而实际情况下, 由于传感器节点与周围环境紧密接触, 节点的能量消耗因为不确定的周围环境变化及监测事件发生的不可预测性, 从而表现出高度的动态性.如果某些时间段监测事件较多, 能耗就大; 相反, 能耗可能就相对较低.此外, 节点在各个时刻传输数据量的差异也导致能量消耗动态变化.由于实际节点能量消耗动态变化, 节点在哪个时刻会发出充电请求也是不确定的.此外, 发出充电请求节点的剩余生存时间也会随着自身能量消耗率的变化动态改变.在上述前提下, 如果合理规划MC充电路径, 及时满足请求充电传感器节点的充电需求, 使节点在能量耗尽前被充电以尽量避免节点能量饥饿, 是我们要解决的问题关键.在最小化饥饿节点比率的同时, 动态移动充电过程还需考虑:(1)由于MC能量容量有限, 充电调度要保证MC有足够的能量返回BS补充能量; (2)充电调度算法尽量避免节点饥饿失效的同时, 降低MC在路径上移动引起的能量开消; (3)充电响应具有公平性, 避免请求充电节点长期得不到能量补充造成饥饿.

已有的在线充电策略在避免节点陷入能量饥饿方面并不十分有效, 如:抢占式最近工作优先充电策略NJNP^[25]没有考虑MC对节点充电请求响应的公平性, 如果最先请求充电的节点距离MC较远, 那么该节点很容易被后来到达的距离MC较近的节点抢占, 引起该节点由于长期得不到充电而失效.SAMER充电策略^[27]虽提出了节点能量饥饿避免的问题, 但没有考虑充电过程中各传感器节点的动态能耗变化, 造成充电路径规划不合理.如图 3所示, 假设待充电节点为节点E、节点F、节点B和节点D.SAMER策略在充电前首先依次检查选择任一节点为下一充电节点时其他待充电节点的剩余能量状况.根据SAMER, 此时选择B或者E为下一充电节点时, 节点D和F均不饿死, 则把节点B和节点E加入预充电节点集合; 而选择节点D或者节点F为一下充电节点时均出现其他节点饥饿的情况, 那么按照SAMER策略, MC的充电顺序为B→E→D→F.由于节点F的剩余能量较低, 如果MC选择首选对E充电后马上对F进行充电, 能保证F存活, 而此时, 由于首先对B进行充电, 对B充电完成后再对E进行充电, 那么由于此时F的等待时间较长, 很可能造成F在被充电前已经饿死了.也就是说, 按照上述充电顺序对B充电完成后选择E为下一充电节点, 并不能保证网络中所有其他请求充电的节点存活.另外, 如果按照上述充电顺序完成对E的充电后, 此时若有到E的距离比F到E的距离更近的节点不断到达, 那么这些节点就会在F之前被充电, 导致F由于等待充电时间过长而饿死.另外, SAMER在计算节点的剩余能量时, 没有根据各节点当前的能量消耗率来进行, 也导致充电路径规划的不合理性.

3 ESAOC策略设计实现 3.1 计算各节点的动态能量消耗率

由于受周围环境因素的影响, 传感器节点的能量消耗实际是动态变化的, 那么估计节点的当前能量消耗率, 成为ESAOC策略中计算每个待充电节点等待MC充电的最大充电容忍延迟和最短等待时间的关键.为估计节点的能量消耗率, 设初始网络部署的时间为零, 之后, 每个传感器节点每隔时间间隔Δ记录自己的当前剩余能量值和当前时间值, 并以消息的形式把记录的能量值和对应的时间值发送给基站.例如, 节点i发送给基站的能量通告消息形式为〈ID_i, RE_in, t_in, urg=0〉, n≥0, urg=0表示这是一个能量通告消息.传感器节点i能量消耗率的实时值r_in为

$ {r_{in}} = \frac{{R{E_{i(n - 1)}} - R{E_{in}}}}{\mathit{\Delta }},n \ge 1 $

(1)

令R_{i, n}表示接收n+1条剩余能量值通告后基站对节点i能量消耗率的估计, 利用加权平均法^[28], 有:

$ {R_{i, n}} = \frac{{{r_{i1}}{t_1} + {r_{i2}}{t_2} + ... + {r_{in}}{t_n}}}{{{t_1} + {t_2} + ... + {t_n}}} $

(2)

其中, t_n表示传感器节点i记录第n+1条剩余能量的时间, r_in为收到第n+1次能量通告后计算得到的能量消耗率实时值.将时间值作为计算能量消耗率的权重, 是因为时间值越大, 表示对应的能量消耗率的值就越新, 越接近实时值.这既保证了对节点能量消耗率估计的实时性, 又考虑到节点能量消耗率的历史统计.把公式(1)代入公式(2), 得:

$ {R_{i, n}} = \frac{{(R{E_{i0}} - R{E_{i1}})({t_0} + \mathit{\Delta } ) + (R{E_{i1}} - R{E_{i2}})({t_0} + 2\mathit{\Delta } ) + ... + (R{E_{i(n - 1)}} - R{E_{in}})({t_0} + n\mathit{\Delta } )}}{{n\mathit{\Delta } \left[{{t_0} + \frac{{(n + 1)\mathit{\Delta } }}{2}} \right]}} $

(3)

这样, 计算动态能量消耗率的方法需要基站保存所有的剩余能量记录, 代价会比较大.因此, 我们利用递推方法改进公式(2), 得:

$ \left\{ {\begin{array}{*{20}{l}} {{R_{i, n}} = \frac{{{R_{i, n - 1}} \times S{T_{n - 1}} + {r_{in}}{t_n}}}{{S{T_{n - 1}} + {t_n}}}, {\rm{ }}n \ge 2}\\ {{R_{i, 1}} = {r_{i1}} = \frac{{R{E_{i0}} - R{E_{i1}}}}{\mathit{\Delta } }} \end{array}} \right. $

(4)

其中, ST_n-1为前n个剩余能量值通告的时间值总和.节点每更新一次能量消耗率, 就要累加一次时间值总和ST_n:

$ S{T_n} = S{T_n}_{-1} + {t_n} $

(5)

这样, 根据公式(4)计算能量消耗率时, 基站只需保存R_{i, 1}、时间值总和以及最近一次估计的节点能量消耗率的值, 与公式(2)相比, 减小了基站的存储代价.此外, 在MC为节点充电期间, 节点不记录和发送自己的剩余能量.当充电完成后, 重新开始每隔时间间隔Δ记录一次自己的剩余能量值和当前时间, 并在充电完成后首次发送能量通告消息时, 同时发送充电完成的通告, 基站收到该通告后, 清除该节点之前的所有能量消耗率估计及时间统计, 并按上述方法重新计算该节点的能量消耗率.基站以长距离通信的方式把计算所得各个节点的能量消耗率通告给MC, 这样, MC就了解网络中各节点的能量消耗率及其变化.规定能量通告消息在一定的延迟范围内可以被传感器节点发送给基站的感知消息捎带, 这样, 发送能量通告给基站就不会花费节点太多能量, 降低了传感器节点的能耗开销.

3.2 门限值范围估计

传感器节点发现自己的剩余能量值低于门限值E_thred时, 就向基站发送充电请求.门限值的设定对充电策略性能影响非常大:若门限值E_thred非常小, 即充电请求发送的很晚, 此时留给MC运动到请求充电节点并为该节点充电的时间就非常有限, 导致很多节点因为得不到及时充电而失效, 因此, E_thred不能设置的非常小; 相反, E_thred设置得非常大时, 很可能MC运动到传感器节点准备充电时, 传感器节点的剩余能量仍非常大, 导致移动充电器MC能量利用率低下.设移动充电器MC收到充电请求就从BS出发开始为节点充电, 下面我们从几个方面来讨论E_thred的取值.

(1) 从单个节点的能量消耗方面分析

待充电节点的剩余能量应该满足:MC以最短的延迟到达节点并为该节点充电之前, 节点不能饿死, 否则, MC不可能满足节点的充电需求.若忽略充电请求传输所需要的时间, 则MC运动到节点i的最短延迟为

$ \frac{{distance(MC, i)}}{v} $

(6)

其中, distance(MC, i)表示MC的当前位置到节点i的欧几里得距离(此时即BS到i的距离).我们有:

$ \frac{{{E_{thred}}}}{{{R_i}}} > \frac{{distance(MC, i)}}{v} $

(7)

其中, R_i为节点i当前的能量消耗率, 根据公式(4)获得.公式(7)对网络中所有传感器节点成立, 因此,

$ {E_{thred}} > \max \left[{\frac{{distance(MC, i)}}{v} \times {R_i}} \right], 1 \le i \le N $

(8)

(2) 从网络中节点的整体能量状况分析

任一请求充电节点等待MC服务的时间由MC对所有先前节点的充电服务时间和MC从当前充电节点移动到该节点所需时间两部分组成.网络中, 任意两个传感器节点间的平均距离表示为

$ d = \frac{1}{{{N^2}}}\sum\limits_{i = 1}^N {\sum\limits_{j = 1}^N {{d_{_{ij}}}} } $

(9)

其中, d_ij为节点i到节点j的欧几里得距离.我们用d代替MC移动过程中每移动一个边的平均长度, 另外, 我们把节点需要补充的能量值表示为E-E_thred, ,那么网络中每个节点等待MC充电的平均等待时间为

$ $\begin{array}{l} {W_a} = \frac{{\left[{\frac{d}{v} + \frac{{2d}}{v} + ... + \frac{{Nd}}{v} + \frac{{E-{E_{thred}}}}{\eta } + \frac{{2(E-{E_{thred}})}}{\eta } + ... + \frac{{(N-1)(E - {E_{thred}})}}{\eta }} \right]}}{N}\\ {\rm{ }} = \frac{{(N + 1)\sum\limits_{i = 1}^N {\sum\limits_{j = 1}^N {{d_{ij}}} } }}{{2v{N^2}}} + \frac{{(E - {E_{thred}})(N - 1)}}{{2\eta }} \end{array}$ $

(10)

网络中, 节点能量消耗率的均值为

$ R = \left( {{R_1} + {R_2} + \ldots + {R_N}} \right)/N $

(11)

为使网络中不会有太多节点饥饿, 我们使:

$ {W_a} \times R < {E_{thred}} $

(12)

把公式(10)和公式(11)带入公式(12)并简化, 得:

$ {E_{thred}} > ({R_1} + {R_2} + ... + {R_N})/N \times \left[{\frac{{\frac{{\eta (N + 1)\sum\limits_{i = 1}^N {\sum\limits_{j = 1}^N {{d_{ij}}} } }}{{v{N^2}}} + E(N-1)}}{{2\eta + (N-1)({R_1} + {R_2} + ... + {R_N})/N}}} \right] $

(13)

(3) 从移动充电器携带的能量方面分析

移动充电器满能量出发一次服务的充电节点数量不能太少, 否则, MC的能量利用率低下.MC满能量出发一次能够服务的平均节点数量为

$ {N_{avg}} = \left\lfloor {\frac{{P - dc}}{{cd + E}}} \right\rfloor $

(14)

设充电请求的平均到达率为$\lambda = \frac{{\sum\limits_{i = 1}^N {{R_i}} }}{{E - {E_{thred}}}}$^[25], MC为节点充电的平均服务时间是:

$ T = \frac{{\frac{d}{c} + \frac{E}{\eta } + \frac{{2d}}{c} + \frac{{2E}}{\eta } + ... + \frac{{Nd}}{c} + \frac{{NE}}{\eta }}}{N} = \frac{{(N + 1)}}{2}\left( {\frac{d}{c} + \frac{E}{\eta }} \right) $

(15)

我们令:

$ lTN \ge {N_{avg}}a $

(16)

其中, α为期望的MC能量利用率, 且0 < α < 1.把公式(14)、公式(15)带入公式(16)得:

$ {E_{thred}} \ge \frac{{\alpha (N + 1)\left( {\frac{c}{d} + \frac{E}{\eta }} \right)\sum\limits_{i = 1}^N {{R_i}} }}{{2\left\lfloor {\frac{{P - dc}}{{cd + E}}} \right\rfloor }} $

(17)

根据以上分析, E_thred下限的取值应该为公式(8)、公式(13)和公式(17)取值的最大值.

3.3 下一充电节点选择算法

MC移动过程中到底选择哪个节点为下一充电节点, 关系到ESAOC策略性能的关键.ESAOC在选择下一充电节点时的基本思想是:如果充电服务池非空, 则对于任一待充电节点, MC根据当前时间和该节点当前能量消耗率计算该节点的当前最大充电容忍延迟和当某一其他节点(如节点i)被选为下一充电节点时, 该节点的当前最短等待充电时间.接着, 通过比较这两个时间值判断选择节点i为下一充电节点时, 该节点是否饥饿.通过把服务池中所有节点的这两个时间值进行比较, 在MC剩余能量充足的情况下, MC选择下一充电节点时, 始终选择使待充电节点陷入饥饿数量最少的节点作为充电候选节点, 以最小化网络中饥饿节点的数量.此外, 在具体选择下一充电节点时, ESAOC在充电候选节点集中选择最快完成充电的节点作为下一充电节点, 以尽量缩短其他请求充电节点的充电延迟.算法伪代码见算法1, 具体过程分5个步骤描述如下.

步骤1.

MC调度充电节点前, 首先计算充电服务池中每个待充电节点的当前最大充电容忍延迟, 例如, 待充电节点i的最大充电容忍延迟Delay_i(t)为

$ Dela{y_i}(t) = \frac{{RE(i)}}{{{R_i}}} + t{s_i} - t $

(18)

其中, RE_i为发送充电请求时该节点i的剩余能量, t为当前时间.如果节点的当前最大充电容忍延迟小于零等于零, 说明节点已经饿死, 则从队列中删除该节点.

步骤2.

对于充电服务池中未陷入饥饿的节点, MC依次计算若选择任一节点作为下一充电节点时, 所有其他待充电节点的最短等待时间, 如选择节点i作为下一待充电节点时, 节点j的最短等待时间W(i, j)计算如下:

$ \left. \begin{array}{l} W(i, j) = {t_{(MC, i)}} + \frac{{E - {E_i}(t + {t_{(MC, i)}})}}{\eta } + {t_{(i, j)}}\\ \;\;\;\;\;\;\;\;\;\;\;\;= {t_{(MC, i)}} + \frac{{E - ({E_i}(t) + {R_i} \times {t_{(MC, i)}})}}{\eta } + {t_{(i, j)}}\\ \;\;\;\;\;\;\;\;\;\;\;\;= {t_{(MC, i)}} + \frac{{E - R{E_i} - {R_i} \times (t - t{s_i} + {t_{(MC, i)}})}}{\eta } + {t_{(i, j)}} \end{array} \right\} $

(19)

其中, ${t_{(MC, i)}} = \frac{{distance(MC, i)}}{v}$表示MC从当前位置移动到节点i所在位置需要的时间, E_i(t)表示节点i的当前剩余能量值.若Delay_j(t)≥W(i, j), 说明选择节点i作为下一充电节点时, 节点j不会被饿死.若节点i满足对于j(j$\forall$i, j$\in $请求充电的节点), 有Delay_j(t)≥W(i, j), 说明选择节点i为下一充电节点时, 充电服务池中其他待充电节点均不会被饿死, 此时把节点i加入充电节点候选集Z.MC遍历充电服务池中所有节点, 找到所有满足上述条件的节点加入充电节点候选集.若集合Z为空, 则对于充电服务池中各节点, 如节点i, MC统计满足Delay_j(t) < W(i, j)的节点j的个数和对应的节点j的ID号.

步骤3.

1) 在选择下一充电节点时, 若集合Z不为空, 则MC为集合Z中的每个节点分别计算被选为下一充电节点时完成充电所需时间, 如下一充电节点选择节点i时, 充电所需时间为

$ {T_{charge}}(i) = {t_{(MC, i)}} + \frac{{E - E(t + {t_{(MC, i)}})}}{\eta } $

(20)

接着, MC根据公式(21)判断为Z中充电所需时间最短的节点充电时, 公式(21)是否成立:

$ R{E_{MC}}_{, i}-c \times distance\left( {MC, i} \right)-(E-{E_i}\left( {t + {t_{(MC, i)}}} \right)) \ge c \times distance\left( {i, BS} \right) $

(21)

其中, RE_{MC, t}表示MC的当前剩余能量值, distance(i, BS)是节点i到基站BS的距离.

若公式(21)成立, 则说明MC的剩余能量足够为该节点充电, 并使充电后MC能够回到基站补充能量.此时, 选择Z中完成充电所需时间最短的节点为下一充电节点, 因为选择该节点能够使其他待充电节点的等待时间最短.

2) 若Z为空, 则查看为满足Delay_j(t) < W(i, j)的节点j数量最少的节点i充电时, MC的剩余能量是否满足公式(21):若满足, 则选择使Delay_j(t) < W(i, j)数量最少的节点i作为下一充电节点.这是因为选择这样的节点作为下一充电节点时, 能够使充电服务池中陷入饥饿的传感器节点数量最少.

3) 若按上述条件1)或条件2)选择下一充电节点时, MC的剩余能量均不满足公式(21), 则查看选择距离MC最近的节点作为下一充电节点时, 公式(21)是否成立:若成立, 则选择距离MC最近的节点为下一充电节点.

4) 如果按照条件1)~条件3)均找不到满足条件的充电节点, 说明MC的剩余能量不足, 则MC立即返回基站补充能量.

步骤4.

如果步骤3已选中下一充电节点, 就为被选节点充电.在充电完成后, 从MC的充电服务池中删除已经被充电的节点, 并在清空集合Z后执行步骤5.如果步骤3没有选中任何节点, 则MC补充完能量后执行步骤5.

步骤5.

重复步骤1~步骤4, 直到MC的充电服务池为空时, MC返回基站.

算法1.下一充电节点选择算法.

1. While (size(S) > 0)do  //S为MC的充电服务池

2. {初始化:下一充电节点=Null; K=0; Z为空; true(i)=1; number(i)=0;min=FLT_MAX;

3.    For i=1; i≤size(S); i++

4.根据公式(18)计算Delay_i(t);

5.        if Delay_i(t)≤0 then

6. Delete (nodei);

7.        else K=K+1;

8.        end if

9.      end for

10.     for i=1; i≤K; i++

11.        for j=1; j≤K; j++

12. 计算W(i, j)和Delay_j(t);

13.if (W(i, j) > Delay_j(t))then

14.           true(i)=0;

15. number(i)=number(i)+1; //统计死亡节点的个数

16. end if

17.       end for

18.    if true(i) then

19.           add node(i) into Z;

20.        end for

21. if (not empty(Z)) then //选择下一充电节点

22.        for i=1; i≤size(Z); i++

23.计算T_charge(i);

24.    if (min > T_charge(i)) then

25. min=T_harge(i);

26.     x=i;

27.     end if

28. end for

29.     if (代入node(x)计算公式(21)成立)

30. Next-charge-node=node(x);

31.        end if

32.     else

33.     if(代入min(number(i))计算公式(21)成立) then

34.     Next-charge-node=the node with min(number(i))

35.   else

36.        if (代入当前离MC最近的节点计算公式(21)成立) then

37.     Next-charge-node=the node spatially nearest MC in S.

38.        else MC return to BS //MC返回BS补充能量

39.   end if

40.     end if

41.end if

42.}

整个过程举例如下:MC开始充电时, 充电服务池中的节点为节点1、节点3~节点6和节点8, MC发现:此时为节点1、节点3及节点8充电时, 充电服务池中其他节点不会被饿死, 因此, MC把这3个节点加入集合Z; 之后, MC发现:为节点1充电时, 其他节点的等待时间最短, 因此选择集合Z中的节点1为下一充电节点.MC完成节点1的充电后, 从充电服务池中删除节点1, 清空集合Z.接着, MC更新充电服务池中各节点的最大充电容忍延迟和选择任一节点作为下一充电节点时, 其他节点的最短等待时间后, 把节点3加入集合Z, 此时, 下一充电节点为节点3, 如图 4所示.后来, 节点7、节点2和节点9的充电请求先后到达, MC计算发现集合Z为空, 而为节点5充电时, 其他待充电节点饿死的数量最少(只有节点4饿死), 因此, 下一充电节点为节点5.同理, 完成节点5的充电后, 选择节点7为下一充电节点.在完成对节点7的充电后, MC计算发现集合Z为空, 而此时, 为使其他节点饥饿数量最少的节点充电时, MC的剩余能量不满足要求, 此时, MC选择距离MC当前位置最近的节点, 即节点9充电, 完成充电后立即返回基站补充能量, 并在补充能量后继续充电服务.

总之, ESAOC策略通过以下3个方面达到降低网络中能量饥饿节点数量的同时缩短充电等待延迟的目标:首先, ESAOC对充电请求发送门限值的范围进行理论分析, 为传感器节点设置合理的充电请求发送阈值; 其次, 合理估计节点的当前能量消耗率, 合理的能量消耗率为下一待充电节点选择策略提供了基础; 最后, 每次选择下一充电节点时, MC根据当前能量消耗率和当前时间计算各节点的当前最大充电容忍延迟和最短充电等待时间, 每次调度MC时, 均选择使网络中饥饿数量最少的节点加入充电节点候选集, 以最小化网络中由于饥饿死亡的节点数量.另外, 如果充电候选集中节点不唯一, 则选择其中最快完成充电的节点为下一充电节点, 以缩短其他等待充电节点的充电延迟.

4 性能分析

本节基于C++仿真平台对ESAOC策略进行性能分析, 并把ESAOC策略与NJNP策略^[11]、FCFS策略^[29]和SAMER^[26]策略进行性能对比.其中, NJNP和SAMER是近年提出的比较典型的动态充电策略, 而传统的FCFS充电调度策略的性能通常较低, 可以以FCFS作为参考来分析ESAOC的性能.我们通过以下3个指标对上述4种策略进行性能分析.

●  饥饿节点比率:定义为饥饿失效的待充电节点数量与请求充电的节点总数量之比.饥饿节点比率是评价充电策略性能的最重要指标之一, 饥饿节点比率越小, 说明充电策略效率越高、公平性越好;

●  充电延迟:定义为节点发送充电请求消息的时间与节点开始被MC充电的时间之间的时间间隔;

●  充电代价:由于MC需要在网络中不停移动为传感器节点充电, 而MC在移动过程中需要消耗能量, MC移动得越远, 相应消耗的能量也就越大, 因此, 充电代价定义为MC在充电过程中移动的总距离.

在仿真实验中, 设仿真区域为半径D=200m的圆形区域中随机分布了100个传感器节点, 假设每个传感器节点的数据产生过程遵循平均到达时间间隔为50s的泊松过程, 网络带宽为10Kbps.移动充电器MC在充电时以5m/s的速度在仿真区域中移动, 整个仿真持续时间为72 000s, 其他网络参数以及相应的缺省值见表 1.

4.1 充电效率对性能的影响

本组实验研究移动充电器的充电效率对策略性能的影响.令其他参数保持默认值, 充电效率从100mJ/s到300mJ/s逐渐变化, 各策略性能变化如图 5(a)~图 5(c)所示.

为无线可充电传感器网络进行无线充电的最主要目标是防止传感器节点陷入能量饥饿来延长网络的生存时间.图 5(a)显示:当移动充电器的充电效率提高时, 4种策略的饥饿节点比率均呈下降趋势.这是因为充电效率提高使得移动充电器单位时间内能够服务的待充电节点数量增加, 那么请求充电节点在它们的最大充电容忍延迟内被充电的概率增大引起的.随着充电效率变化, ESAOC的饥饿节点比率始终低于其他3种策略, 原因主要在于两个方面:首先, ESAOC对节点能量消耗率进行合理估计, 能量消耗率的估计过程既考虑了节点能量消耗的历史统计, 又保证了节点能量消耗具有实时性, 合理能量消耗率为下一步规划MC的移动路径提供了基础; 其次, ESAOC根据各节点当前能量消耗率计算节点的当前最大充电容忍延迟和最短充电等待时间, 通过比较这两个时间值, 统计选择任意节点为下一充电节点时, 网络中失效节点的总数量, 并始终选择使其他待充电节点饥饿数量最少的节点作为下一充电节点.下一充电节点选择算法以最小化饥饿节点数量为目标, 保证了ESAOC具有较低的饥饿节点比率.FCFS的饥饿节点比率最高, 因为该算法中移动充电器消耗大量时间在网络中不断来回往复移动, 使得节点等待充电的时间增长, 节点容易饥饿.图 5(b)中, NJNP, SAMER和ESAOC的平均充电延迟随着充电效率提高不断下降, 而FCFS却先增大后减小.FCFS的平均充电延迟开始时增大是因为充电效率提高使得MC能够服务的节点数量增多, MC来回往返的运动增多, 使得节点等待充电的时间增长.随着充电效率继续增大, MC为节点充电的速度更快, 使得充电延迟逐渐减小.ESAOC的平均充电延迟略低于SAMER和NJNP, 这是因为ESAOC在下一充电节点选择算法中最先选择完成充电所需时间最短的节点为下一充电节点, 这使得其他待充电节点等待充电的时间缩短的原因.随着充电效率继续提高, ESAOC在完成充电服务的节点数量增多后可能选择较远的节点作为下一充电节点, 以使其他待充电节点饿死的几率最小, 因此, 该策略的平均充电延迟在充电效率高时接近SAMER和NJNP算法.如图 5(c)所示, 4种策略的充电代价均会随着充电效率提高增大.因为充电效率越大为节点充电的速度就越快, 那么移动充电器移动的总距离就会越远来为完成更多的充电请求. ESAOC在充电效率较高时充电代价略高于NJNP和SAMER, 因为根据下一充电节点选择算法, 此时ESAOC可能选择的下一充电节点距离MC所在位置较远, 以使得网络中由于饥饿而失效的节点数量最小, 这会使移动充电器移动距离增大造成充电代价升高.

4.2 节点数量对性能的影响

本组实验讨论节点数量对各策略性能的影响, 我们把传感器节点数量由25个逐渐增长到200, 各策略的性能变化如图 6(a)~图 6(c)所示.

从图 6(a)可见:当传感器节点数量较少时, 由于此时网络中请求充电的节点数量较少, MC能够较快为数量不多的待充电节点补充能量, 因此, 4种策略的饥饿节点比率均不大.随着网络中节点数量继续增大, 这4种策略的饥饿节点比率均增大, 因为节点数量越多, MC的充电负担越重, 当请求服务的节点数量超过MC的服务能力时, 各策略的饥饿节点比率增长迅速.本文策略始终获得低于其他3种策略的饥饿节点比率, 这主要因为本策略在合理设置充电请求发送门限值的前提下, 合理估计各节点当前能量消耗率; 之后, 在每次选择下一充电节点时, 根据能量消耗率计算并比较待充电节点的当前最大充电容忍延迟和这些待充电节点得到充电服务的最短等待时间, 始终选择使其他待充电节点死亡数量最少的节点作为下一充电候选节点, 因此能够最大程度保证网络中失效的节点数量最少.SAMER的饥饿节点比率在节点数量大于150时高于NJNP, 主要是当节点数量较多时, SAMER很难在网络中找到符合条件的候选充电节点造成的.如图 6(b)所示:随着节点数量增大, NJNP, SAMER和ESAOC的平均充电延迟变化规律类似, 且ESAOC的平均充电延迟略低于NJNP和SAMER.这主要是因为ESAOC偏向于选择最快完成充电的节点为下一充电节点, 该下一充电节点选择策略能最小化网络中其他节点等待充电服务的时间.FCFS的平均充电延迟在节点数量高于75时增长迅速, 主要由于该策略中当节点数量增大时, 移动充电器MC在网络中来回移动显著增多, MC运动到节点的延迟增加了, 因此节点等待充电的时间延长了.图 6(c)中, NJNP, SAMER和ESAOC的充电代价先增大后减小.充电代价减小是因为当节点数量达到一定程度时, 充电请求数量也明显增加, 这样, MC在较近的距离内发现满足条件的待充电节点的概率增大, MC此时就来不及响应距离自己较远的充电请求, 一直在为自己周围的请求充电节点充电, 所以MC移动总距离小了.从图 6(a)可以看到, 此时饥饿节点比率也快速增加.从图 6(c)中还可以看到:网络中节点数量低于125时, ESAOC的性能优于其他策略; 之后, 随着节点数量继续增多.由于ESAOC可能选择距离MC较远的待充电节点以最小化网络中饥饿节点数量, 且ESAOC服务的节点数量最多, 而NJNP和SAMER公平性差, 偏向于选择距离MC较近的节点进行充电, 因此ESAOC的充电代价大于NJNP和SAMER.

4.3 MC移动速度对性能的影响

本组实验研究移动充电器的运动速度对策略性能的影响.图 7(a)显示, 4种策略的饥饿节点比率均随着移动充电器的速度增加呈下降趋势.因为MC速度增加后, 它能够以更快的效率为等待充电传感器节点充电, 降低了节点因等待其他节点的充电服务而饿死的几率.在MC运动速度变化过程中, FCFS的饥饿节点比率最大, 因为FCFS需要在网络中来回往复运动为节点充电, 使节点等待充电的时间增长.由于ESAOC在合理的充电请求门限值范围内发送充电请求, 并合理估计当前能量消耗率及通过高效的下一充电节点选择算法避免节点能量饥饿, ESAOC的饥饿节点比率始终小于其他3种策略, 显示了ESAOC的优越性能.图 7(b)中, MC的移动速度增加后, FCFS的平均充电延迟先略增大后减小.FCFS的平均充电延迟增大是因为MC移动速度增大使MC服务的传感器节点数量增加了, MC需要在网络中来回运动为传感器节点充电, 来回往返的运动延长了节点等待充电的时间.之后, 随着MC移动速度继续增长, 待充电节点完成充电服务的时间进一步缩短, 因此充电延迟减小.由于待充电节点等待服务的时间缩短, NJNP, SAMER和ESAOC的充电延迟均随着MC移动速度增长不断下降.如图 7(c)中, 由于MC移动速度越快移动充电器的服务能力越强, MC能够为更多的待充电节点完成充电, 因此MC的移动总距离增加, 导致充电代价也增加了.随着MC移动速度增加, SAMER的充电代价逐渐接近NJNP.因为随着服务的待充电节点数量增多, 两者均选择距离MC较近的节点为下一充电节点的缘故.为使陷入饥饿的节点数量最少, ESAOC可能选择的下一充电节点并不是距离MC最近的节点, 因此在MC移动速度较高时, ESAOC的充电代价高于NJNP和SAMER.

4.4 MC携带的能量对性能的影响

移动充电器的能量容量会影响策略的性能, 为此, 本组实验讨论MC的能量容量对各策略性能的影响.图 8(a)中, 4种策略的饥饿节点比率均随着MC能量容量变大而逐渐减小.这是因为能量容量大时MC能为更多的节点充电, 相应地, 由于MC能量不足导致节点不能及时充电从而引起节点饥饿的概率减小了, 因此节点饥饿比率降低.ESAOC策略的饥饿节点比率最低, 这主要由于ESAOC始终选择令其他节点饥饿数量最少的待充电节点为下一充电节点的原因.FCFS的饥饿节点比率在4种策略中最高, 因为首先FCFS在网络中来回往复运动浪费了MC的能量, 其次, FCFS的来回运动使节点等待充电的时间增长, 那么节点在有限的充电容忍延迟内失效的概率增大了.如图 8(b)所示:4种策略的平均充电延迟在MC能量容量低时较小, 随着MC能量容量不断增大, 原来由于MC能量不足失效的节点能够被充电了, 而这部分节点等待充电的延迟较长, 导致4种策略的充电延迟增大.ESAOC的充电延迟始终低于其他3种策略, 因为ESAOC偏向选择最快完成充电的节点为下一充电服务节点, 使其他节点等待服务的时间缩短.图 8(c)表明, MC能量容量增大使4种策略的充电代价提高.因为MC能够服务的节点数量增多了, 为此, MC移动的距离也就越远以便服务更多的节点.随着MC携带的能量增大, 因为ESAOC服务的节点数量最多且ESAOC可能下一跳选择的节点距离MC当前位置稍远, 因此当MC能量容量较大时, ESAOC的充电代价稍高于SAMER, 接近NJNP.

4.5 门限值对性能的影响

门限值的设置影响策略的性能, 为此, 本组实验讨论节点的充电门限值E_thred的设置对NJNP, SAMER和ESAOC性能的影响.实验中, 我们把节点的充电门限值分别设置为0.1E~0.6E, 得实验结果如图 9所示.

图 9显示, 3种策略的饥饿节点比率均随着E_thred变大不断减小.这是合理的, 因为门限值越大, 表明节点的充电请求发送越早, 节点发送充电请求时的剩余能量就越多, 那么留给MC运动到待充电节点并在节点能量全部消耗完之前为节点充电的时间就比较充足.相反, 充电门限值越小, 待充电节点的最大充电容忍延迟就会越短, 待充电节点就越容易在等到MC服务前死亡.此外, 无论E_thred值如何变化, ESAOC的饥饿节点比率始终低于SAMER和NJNP, 显示了本文策略在饥饿避免方面的优越性, 能够尽量避免节点陷入饿死, 从而延长了网络寿命.

此外, 为了验证门限值的理论分析是否合理, 我们在节点部署后确定节点的位置, 之后根据各节点位置计算得d; 此外, 根据节点的能量消耗情况计算能量消耗率, 并根据各节点能量消耗率统计平均能量消耗率R, 在已知R, d, N, E, c, η和各节点能量消耗率后, 通过公式(8)、公式(13)和公式(17)计算门限值E_thred, ,当设置α=0.9时, 最终得门限值下限约为0.37E.从图 9可以看出:当门限值大于0.37E时, NJNP, SAMER和ESAOC的饥饿节点比率均较低, 表明门限值下限的分析是合理的.

4.6 节点能量消耗率对性能的影响

节点的能量消耗率影响各策略的性能, 为了分析能量消耗率对性能产生的影响, 我们把传感器节点数据产生的平均到达时间间隔分别调整为30s, 40s, 60s, 70s和80s.随着数据的到达间隔不同, 网络中节点的能量消耗率会发生变化.我们得到4种策略的饥饿节点比率随数据产生的平均到达时间间隔变化如图 10所示.图中显示:平均数据到达间隔减小, 使4种策略的饥饿节点比率不断增大.引起这种现象的原因是:数据到达间隔越小, 则节点能量消耗率越大, 那么节点能量消耗就越快, 致使单位时间提出充电请求的节点数量增多.由于MC的服务能力有限, 当提出充电请求的节点数量不断增多时, 不能被及时充电而失效的节点数量也增多了, 造成饥饿节点比率增大.由于始终选择使网络中饥饿节点数量最少的节点作为下一充电节点, 在数据到达间隔变化使得节点能量消耗率变化过程中, ESAOC的饥饿节点比率始终低于另外3种策略, 表明ESAOC在避免节点失效方面非常有效.

5 结论

本文研究无线可充电传感器网络的在线动态充电问题, 并提出了能量饥饿避免的在线充电策略ESAOC. ESAOC不仅能够适应实际环境中传感器节点能量消耗的动态性和多样性, 还充分考虑了充电过程的公平性, 通过合理地选择MC服务的下一充电节点, 尽量避免请求充电节点陷入能量饥饿.仿真实验中, 我们通过分析饥饿节点比率、充电延迟和充电代价来评估所提策略的性能.实验结果表明:ESAOC能够有效降低饥饿节点比率, 并且能够及时有效地为网络中的待充电节点补充能量.