基于移动充电设备的无线传感网络充电策略研究综述*

2022-03-07陈雅倩焦万果

电子技术应用 2022年2期

陈雅倩，焦万果，周磊

(南京林业大学信息科学技术学院，江苏南京 210037)

0 引言

无线传感器网络(Wireless Sensor Networks，WSNs)是由部署在监控区域内许多微小型传感器节点以自组织方式构成，通过无线数据传输方式形成的一个单跳或者多跳的无线网络。在传统的无线传感器网络中，受传感器尺寸和成本限制，导致无线传感器网络能量和处理能力受限，尤其是能量方面，传感器采用电池供电且更换困难，使得无线传感器网络无法持续获得能量供应，导致网络生存期受限，严重限制了传感器技术的发展和应用。

为了充分利用有限的能量延长网络生存期，很多工作通过设计高能效的多址接入、路由协议等，在保障网络基本功能的基础上，有效地改善了网络生存期。如文献[1]提出的最小总能量路由算法，通过选择沿总传输能量最小的路由来延长网络的寿命；文献[2]提出的流增强算法，通过归一化剩余能量来衡量一跳所消耗的能量，避免一些节点能量消耗过快。除了路由算法，拓扑控制也是延长网络生命周期的重要方法。文献[3-4]通过提出节点聚类算法，改善网络拓扑结构，降低无线传感器网络的平均能耗、延长网络寿命。然而，由于传感器节点能量有限，这些工作只能让传感器网络生存期得到有限的改善。

近十年来，随着能量收集技术和无线充电技术的发展，研究者们尝试让传感器节点利用周围环境能量来补充自身的能量，可吸收的能量包括风能[5]、太阳能[6]等。文献[6]设计了一个基于最大功率点跟踪控制的太阳能采集器系统，利用光伏电池将太阳能转化成电能为无线传感器节点供电。文献[7]提出了一种太阳能预测算法，显著提高了传感器节点对太阳能的收集效率，有效缓解了无线传感器网络中能量受限的问题。通过提高能量收集效率和改善能量利用率，基于能量收集的传感器网络生存期得到了延长。然而，由于基于能量收集的传感器所能收集的能量严重依赖于自然环境，且环境和气候的随机变化，使得所能收集到的能量不可预测且难以控制。采用无线充电技术为传感器补充能量可以弥补这一不足。

和能量收集技术相比，基于无线充电技术的传感器网络可以根据传感器节点需求进行有针对性的能量供应，尤其采用可移动充电设备时，网络能量供应更加稳定可控，因此基于可移动充电设备的无线充电传感器网络成为传感器网络研究的一个热点，得到了广泛的研究。移动可充电设备的引入，虽能为传感器网络进行有效的能量补充，但同时也给网络能量管理带来新的问题和挑战。首先，给哪些传感器节点充电及顺序如何，即，充电路径的规划问题。影响这个问题的因素众多，如节点剩余能量、节点能量消耗速率、充电信道质量、充电设备移动开销等。不合理的路径规划不仅导致能量的浪费，还会导致网络部分关键传感器节点因无法及时被充电而提前死亡，同时其他节点能量却很充足。其次，给传感器节点充多少电及一个充电设备一次给多少个传感器节点充电，即充电方式的选择问题。此外，由于单个充电设备所携带电量有限，无法满足所有传感器节点的能量请求，为了保证传感器节点能量的供应，传感器网络会采用多个可移动充电设备。现有研究从充电设备数量优化、充电路径规划、充电方式选择等方面展开研究，对网络充电效率、网络运营成本以及网络生存期等性能指标进行优化。

虽然目前针对可充电传感器网络的充电策略研究的工作很多，但缺乏对所取得的成果进行系统的总结和分析。为了弥补可充电传感器网络充电策略研究综述的空白，本文对现有研究工作从网络场景、充电方式、路径优化等方面展开讨论，重点分析基于移动充电小车(Mobile Charging Vehicle，MCV)和无人机(Unmanned Aerial Vehicle，UAV)的无线传感网络充电策略研究的成果，具体内容组织结构如图1 所示。

如图1 所示，本文将现有研究工作按照网络场景划分为基于移动充电车充电的二维场景和基于无人机充电的三维网络，分别在这两个场景下讨论移动充电设备的充电方式选择、路径优化、充电设备数量优化等问题的研究成果。

图1 采用移动充电设备为无线传感器网络充电研究的研究成果

1 二维情形下移动充电车给无线传感器网络充电

一个二维传感器网络通常包含若干传感器节点、一个或多个移动充电车、充电服务站和基站。其中，充电服务站用于给移动充电车补充能量，基站既是网络的数据采集器，也是移动充电车的调度器。在没有充电服务站的网络中，基站充当充电服务站的角色，为移动充电车进行能量补充[8]。对于大规模的无线传感器网络而言，由于移动充电车本身移动时也会消耗能量，服务站若设置较远，移动充电车将不能到达离服务站很远的传感器节点。为解决这个问题，有研究者提出在网络区域中部署多个服务站[9]，当移动充电车的能量即将耗尽时，它会移动到附近的服务站补充能量或者更换新电池。目前，大部分研究要么假设充电车的能量不受限，要么在路径规划时，保证充电车在能量耗尽之前，返回充电站。根据网络中充电设备的数量，把这些工作分为单移动充电车和多移动充电车，下面分别介绍和总结这两种充电车配置下，在充电方式、路径优化及充电设备数量优化等方面取得的研究成果。

1.1 单个移动充电车

在可充电传感器网络中，单个移动充电车的充电模式是最先且广泛被研究的充电方式，下面将从充电方式和路径优化两个方面对现有研究成果进行归纳和总结。

1.1.1 充电方式

单个移动充电车参与无线传感器网络的充电模型主要有两种：点对点充电模型、点对多点充电模型。如图2所示，充电车一次只能给一个充电传感器充电，是一种典型的点对点充电模型。

在点对点充电方式中，采用分簇模型，让充电车对簇头节点进行充电，如图2 所示，是一种重要和典型的提高能量效率，提高网络生存期的方式。在分簇网络中，簇的形成、簇首选择以及簇首充电顺序，是充电算法主要研究内容[10-11]。除此之外，还有一些算法在设计充电策略时，考虑传感器节点对网络整体性能的影响，如文献[12]考虑节点间的冗余覆盖，选择能达到覆盖效用最大的节点作为待充电节点。

图2 点对点充电(分簇模型)

上述这些算法都是离线充电算法，还有一些工作通过实时在线调度充电车，根据传感器节点剩余能量，及时为一些主要节点或紧急节点进行能量补充，如文献[8]、文献[13]和文献[14]。为了实现在线的充电方案，文献[8]开发了一个主要节点和过路节点调度算法，并利用一种局部搜素算法将移动充电车当前移动目标的邻近节点作为过路节点进行充电。文献[13]采用了一种新的避免重要节点故障的在线充电算法。为了尽可能多地防止传感器故障，该算法总是选择那些不会导致重要节点故障的节点作为下一个充电节点。文献[14]提出的时空实时充电调度算法能够在按需架构中找到条件最优的充电方案。点对点充电方式的传感器网络中，一个移动充电车在同一个时刻只能给一个传感器节点充电，是一种常用的充电方式。对上述算法所涉及到文献的总结如表1所示。

在点对点充电模型中，充电车依次为需要充电的传感器节点进行充电，整个充电过程时间较长，Fu 等人的研究表明充电时间反比于充电效率：传感器充电时间越短，充电效率越高[15]。为了解决点对点充电方式低效问题，研究人员设计了点对多点充电模型，即一个移动充电车一次能给多个传感器节点同时充电，可以有效缩短充电时间，让更多的传感器节点得到充电机会。

文献[15]根据传感器的功耗率对传感器进行了分组，每次充电车对同一组传感器进行充电，缩短传感器的充电时间和充电车移动距离，可以提高充电效率。文献[16]和文献[17]为进一步提高充电效用，使用蜂窝拓扑结构的网络模型，如图3 所示，将蜂窝中心作为移动充电车的停止点，当移动充电车处于蜂窝中心位置时，可以对蜂窝内所有传感器节点进行充电，结果表明这种蜂窝结构可以有效提高充电效率，被广泛使用在可充电传感器网络充电策略研究中。

图3 点对多点充电(蜂窝模型)

文献[18]在点对多点充电模型下将最大化传感器节点的寿命作为设计目标，分别对传感器节点在完全充电和部分充电两种情况下设计出了具有恒定近似比的近似算法，在完全充电时，充电周期内所消耗的能量不能超过移动充电车的电池容量。

在点对多点充电模型下，充电结束时间取决于能量最低的节点的充电时间，这就会造成能量和时间的浪费，因此，在一些工作中，将两种方式结合起来，如文献[19]的作者考虑根据传感器节点的重要程度对不同传感器节点采取不同的充电模型，即将点对点充电模型与点对多点充电模型相结合，能够达到良好的充电效果。

1.1.2 路径优化

在基于充电车的传感器网络中，规划充电车设备的充电路径，是一个非常重点的问题，不同的路径规划，会影响网络的各项性能指标，如生存期、能效、吞吐量等。最短充电行程是最常见的路径优化目标，著名的旅行商算法可以求出遍历所有待充电传感器节点位置的最短路径，但现有工作一般不直接进行旅行商问题(Traveling Salesman Problem，TSP)的求解，因为这样会忽略距离和能量对路径的影响，所以需要进行一系列的转化。例如，在文献[20]中，作者以传感器节点之间的距离和它们的剩余能量作为权值来计算最优路径，而后将其转化为TSP 问题。文献[21]针对最小化移动充电车的行程问题，提出了一种启发式算法。文献[22]首先考虑了一个假设旅行时间为零的理想化问题，设计一个可证明的接近最优解的算法，在理想问题近似最优解的基础上，将遍历路径设置为连接逻辑点和服务站的最短哈密顿循环，然后可得到原问题一个实际解。

除了最小化充电行程，文献[23]把最大限度提高充电效用作为路径优化的目标，并在路径优化中考虑充电车移动消耗的能量和充电车能量有限，提出通过寻找包含移动充电车站的封闭充电路线且最大化累计充电效用增益的问题，并设计一个具有常数近似比的一阶近似算法来解决该问题。文献[24]中，作者将最大化充电节点的数量作为路径优化的目标，提出了一种启发式粒子群优化算法来求解充电路径。

上述研究均采用点对点充电方式，在点对多点充电模型，路径优化还要对充电车停止位置和充电时间进行优化。当以减少移动充电车停止位置的数量为目标时，Khelladi 等人使用单位圆盘模型定义充电车的充电范围[25-26]。当以最小化充电时间为优化目标来规划充电停止位置时，由于传感器每单位时间接收的电量与其跟移动充电车的距离有关：距离越远，单位时间接收的功率越小。Suo 等人[27]提出了移动充电车充电时间最小化的问题，目标是使用最短的充电时间让每个传感器接收至少一个单位的电量。首先，对传感器分布区域进行离散化，并将离散点集作为充电停止位置的候选位置；在此基础上，建立整数线性规划模型，确定充电停止位置。在文献[28]中，作者把移动充电车在各充电停止位置的运动轨迹和充电时间作为优化变量，提出了一种无线移动充电车偏移优化算法。在无线移动充电车移动路径优化中，既考虑各充电区域节点的剩余能量，又考虑无线移动充电车的移动时间，从而提高了能源效率；为计算每个充电区域的充电时间，不仅考虑该当前充电区域节点的剩余能量，还考虑其他充电区域节点的剩余能量。文献[29]中，作者考虑到移动充电车可能在其路径上的多个位置均可对同一传感器充电，提出了一个整数线性规划模型，其目标是最小化停止充电位置数量，从而使网络的总充电时间最小化。Moraes 和Har[30]在预先确定候选位置的基础上，选择部分传感器位置作为充电目标，以这些传感器的位置为中心，作半径为r 的圆，中心传感器作为簇头节点，根据每个簇簇头的位置，充电车以充电路径所需充电时间最小为优化目标进行路径规划。

1.2 多个移动充电车

在大规模传感器网络中，当采用移动充电车辆为无线传感器网络充电时，单个移动充电车辆所携带的能量可能不足以为所有即将能量耗尽的传感器充电，需要引入多个移动充电车。下面将介绍采用多个移动充电车的充电方式、路径优化以及其数量优化。

1.2.1 充电方式

在单纯调度移动充电车的充电方式研究方面，文献[31]在给定一组具有不同剩余寿命的待充电传感器的情况下，设计了一种自适应算法来调度移动充电车，以便在传感器能量耗尽之前对其进行一定比例的充电，即部分充电。Lin 等人[32]提出的时空协同充电方案将充电请求的时间需求和空间特征两个关键度量结合到一个联合度量中，并利用这个度量值对充电序列进行决策。为了提高网络的整体性能，找到最优的充电方案，作者提出时空协同充电算法，将充电调度问题建模为一个多目标联合优化问题，其中多目标指的是最大化能量利用率和最大化传感器节点存活率。文献[33]中，作者提出的周期性充电算法，第一次联合考虑了移动充电车的充电旅行周期和传感器节点的工作寿命：对于大容量的移动充电车，限制每个移动充电车只能服务一次充电行程，但允许它在返回充电服务站前对传感器节点进行重复充电；对于小容量的移动充电车，允许它服务于多个充电行程，移动充电车在一次特定的旅行中为传感器节点充电后，它将返回充电并开始另一次旅行。只调度移动充电车进行充电的充电方式没有考虑到对传感器节点的控制，联合两者的充电方式效率更高。

与上述单独调度移动充电车来提高充电效率的充电方式不同，Wu 等人[34]研究了如何通过联合考虑定向传感器放置和移动充电车调度问题来提高充电效用。在文献[35]中，作者所提出的充电方案也是通过同时调度移动充电车和传感器节点来保持网络运行的。在充电方案中引入了节点休眠机制，综合考虑传感器节点的剩余生命期、网络连通性的重要性和网络的覆盖度，提出了一种有效的充电算法，通过调度能量有限的WCVs 对传感器节点进行充电，并调度适当的传感器节点进入休眠状态。

1.2.2 路径优化

能够在充电周期内尽量使移动充电车的移动路径最短一直是研究者们的重要优化目标之一。Xu 等人[36]在调度多个移动充电车对传感器进行协同充电时，其设计目标是最小化这些移动充电车的移动距离之和。为了解决这个问题，在固定最大充电周期情况下，设计了一种近似算法，在最大周期可变时设计了一种启发式算法。对于每次行程只能充电k 个传感器的最短路径规划问题，Zoe 等人[37]提出了一种近似系数可调的规划方法。Xu 等人[38]为了解决使移动充电车中最长充电行程的长度最小化问题，提出了常数近似算法。在文献[39]中，作者提出了基于遗传算法的带时间窗的充电调度算法，使移动充电设备的行驶距离最小化。文献[35]中，在不可忽略移动充电设备自身行驶能耗的基础上，提出了一种最小行程路径算法来求解移动充电设备的最短行驶路径，通过重新安排传感器节点的充电顺序，优化了传感器节点的行程距离，最大限度地延长了无线传感器网络的使用寿命。

多移动充电车情况下，目前研究中，大多数是为每一个充电小车分配充电线路，除了上述文献，还有文献[40-41]。其中文献[40]先是提出求解最优封闭行程的算法，而后再调度车辆给这些封闭行程。文献[41]中作者为给多个移动充电车中的每一个找到一个闭合的充电回路，设计出了一个近似比恒定的近似算法。

1.2.3 数量优化

当采用多个移动充电车为无线传感器网络补充能量时，最小化移动充电车的数量是很多研究者们的优化目标。

尽量减少部署移动充电车数量方面，文献[42]首先研究了最小旅行次数问题，即在给定网络中的一组节点、一个车辆段和一个距离界D 下，找到在车辆段覆盖所有节点的最小旅行次数，且每次旅行长度不超过距离界D。文献[43]利用文献[42]提出的近似算法，并假设所有传感器具有相同的能量消耗率，研究部署最小数量的充电车辆解决传感器充分充电的问题。而文献[33]则通过将网络划分为最小数量的充电线路来分配给移动充电车，从而最小化移动充电车的数量。文献[40]在考虑每个移动充电车辆的能量容量约束的情况下，研究最小化移动充电车辆数量问题。

最小化车辆部署问题可以通过下述方法解决：找到移动充电车辆的时间表，通过为每辆车设计一个封闭的行程来为传感器完全充电，这样部署移动车辆不仅数量可以最小化，且保证每个移动车辆的能量容量约束。最小车辆展开问题的近似算法基本思想：通过限制每次封闭旅行的总消耗，将最小车辆调配问题简化为p-封闭旅行问题。在文献[44]中，作者设计一个哈密顿圈作为移动充电车的最短充电路径，然后，根据移动充电车的能量限制，将充电路径划分为若干个子路径，每个子路径分配一个移动充电车。文献[45]中，作者用K-均值聚类算法将整个网络区域划分为若干个子区域，为每个子区域分配一个移动充电车来为区域内传感器节点充电。首先，介绍了一种具有可证明的逼近比的树分解算法来寻找q-封闭路径；然后，提出了一种近似算法，根据每次充电周期的总距离，使移动充电设备的使用个数最少。这个策略的一个缺点是复杂度随着待充电节点的数量呈指数增长。

2 三维情形下无人机给无线传感器网络充电

近年来，考虑到无人机不仅可作为无线传感器网络中的数据采集器，还可以用作无线电源，许多研究者将充电传感器网络的研究由二维平面转到了三维空间，尝试将无人机作为移动充电设备参与到无线传感器网络寿命延长的工作中[45-46]。三维可充电传感器网络一般由传感器节点和无人机组成，如图4 所示。

图4 无人机参与的网络模型

在这类研究中，一般假设无人机是在固定高度飞行且所携带的能量是固定的，其能量主要在移动、悬停和充电过程中消耗。目前这类研究工作还比较少，下面主要对其中两篇典型工作[46-47]进行介绍。两者均采用点对点的充电方式，即无人机的充电悬停位置和待充电传感器节点之间存在一对一的映射，一个无人机只能给一个传感器节点充电。如图4 所示，无人机的轨迹优化跟移动充电车的路径规划一样，都离不开对充电停止位置和充电时间的优化，只有将时间与空间两方面的优化相结合才能更好地提高充电效率，达到延长网络寿命的目的。

文献[46]将无人机最大化能量利用效率问题分解为整数规划和非凸优化问题，提出了一种多项式时间随机近似方案，用于寻找近似的无人机最小悬停位置数。对于大规模网络中的巡航轨迹优化问题，该文给出了两种情形下的不同算法：一种情形是充电站点固定下的求解算法，另一种情形是充电站点不固定的求解算法。前者能够使得最优轨迹所需的时间最少，后者能够使得最优轨迹的距离最短。文献[47]中，作者在同时考虑传感器能量消耗和能量收集的情况下，采用拉格朗日乘子法对固定悬停位置下的无人机充电时间进行优化；对于悬停位置的优化，采用了复杂度较低的基于几何的无人机悬停位置确定方案，然后通过寻找初始可行解并迭代更新得到近似最优轨迹解，研究表明该工作可以有效延长网络寿命。

3 挑战与未来研究方向

虽然现有工作对基于移动充电设备的无线传感器网络充电策略进行了广泛且深入的研究，但在实际应用和理论边界方面，移动充电设备仍然面临着许多挑战。

(1)理想假设与实际应用场景不符，导致很多研究成果无法应用到实际网络中或无法达到预期效果。如大部分研究都假设移动充电设备是匀速的，然而实际中，充电设备匀速移动很难实现，会导致对充电路径时间不正确，从而影响待充电传感器节点的充电时间，进而影响网络的生存期。此外，现有研究基本都是通过仿真来验证算法的性能，在实际应用时，可能出现各种意料之外的问题，如存在障碍物，因无线信道质量不理想，无法达到预期充电效率等。因此，在考虑更多真实环境中的影响因素基础上，设计实际可用的充电算法；模拟真实环境，搭建基于实物的验证平台，解决充电策略真实评估，是基于充电设备充电的传感器网络亟需解决的重要问题。

(2)利用无人机可部分解决移动充电车实际应用遇到的问题，但现有文献对基于无人机的充电策略研究较少，需要进一步研究无人机的路径规划，包括多无人机间的协作，无人机与充电车的联合调度，以及无人机悬停时，机翼运动对充电效率的影响等实际问题。

(3)网络协议设计和充电策略的联合优化。路由协议、拓扑控制、多址接入、休眠调度等协议均会影响节点能量消耗速率以及网络中节点能量分布，而这些因素是设计充电策略时需要重点考虑的；充电策略的设计，会改变网络中节点剩余能量分布，而这又是网络协议设时重点考虑的因素。因此，联合网络协议和充电策略设计，提高网络能效，保障业务服务质量，改善网络生存期和降低网络运行成本，是未来可充电传感器网络的重要研究方向。

(4)在充电理论方面的研究，目前缺乏从理论上刻画节点能量消耗或网络负载与充电设备之间的关系，如单充电设备的网络中，充电容量边界问题；多充电设备网络中，充电设备数量下界问题等。