CN107657374B - 一种基于能耗和距离动态变化的按需充电调度方法 - Google Patents

Abstract

本发明公开了一种基于能耗和距离动态变化的按需充电调度方法，首先建立节点能量消耗率预测模型；基于传感器节点的能量消耗率以及到移动充电器MC的距离选择充电节点；通过该充电节点建立一个往返服务站的虚拟封闭路径，利用基于节点剩余能量以及能耗率的充电路径可行性判断封闭路径的可行性，如果路径可行而且充电节点剩余能量可以维持到MC对其充电则执行，否则重新选择充电节点；建立节点自适应充电阈值模型，当充电电量达到最大阈值时，MC离开；当建立的虚拟封闭路径不可行或网络中没有节点需要充电时，MC返回服务站补充能量；实时的充电路径更能适应能耗动态发生变化的网络，故本发明在存活节点数和充电效率方面能够取得更好的调度性能。

Description

一种基于能耗和距离动态变化的按需充电调度方法

技术领域

本发明涉及无线传感器网络领域，具体地涉及一种基于能耗和距离动态变化的按需充电调度方法。

背景技术

无线传感器网络是一种由传感器节点构成的网络，能够实时监测，感知采集区域内监测对象的信息，而无线传感器网络所面临的最大问题是传感器节点能量不足，频繁更换电池高成本的问题。无线充电技术的兴起为节点补充能量提供了一种可供选择的新方式，而无线充电技术所面临最主要的问题就是对节点进行能量补充，以保证网络具有较长生命期。

为解决上述问题，目前研究人员做了很多工作，这些工作根据充电周期可以划分为两大类：周期充电和按需充电。定期充电是指网络中的移动充电器以预先设定的路径定期给传感器节点充电。对于预先路径设定这一问题，目前大多数研究是将其转换为TSP问题以找到最佳移动路径。由于节点直接与周围环境相互作用，因此节点的能量消耗表现出高度的动态性。在周期充电方式中，预先设定的运动轨迹往往不能很好地适应动态变化的能量消耗，所以提出了按需充电方式。按需充电是指当节点剩余能量达到最低阈值时即发出充电请求，然后移动充电器会根据收到的充电请求按需给需要充电的节点进行能量补充。在该充电方式中一般考虑的是移动充电器使用何种序列给需要充电的节点进行能量补充。Lin C等人的“TADP:Enabling temporal and distantial priority scheduling for on-demand charging architecture in wireless rechargeable sensor networks，Journalof Systems Architecture,70:26-38.2016”。一种时间和空间结合的方式被提出来给网络中需要充电的节点进行充电，从移动充电器到各个节点之间的距离和每个节点剩余能量共同决定充电调度方式。该方案首先通过节点离充电小车的距离和节点剩余能量能够维持工作时长确定出各节点的充电优先级，然后从所有发出充电请求的节点中选出优先级最高的一个节点进行充电。当移动充电器每次服务完一个节点后，再次通过剩余节点当前的状态值来重新确定各节点充电优先级，持续这一选择过程直到没有充电请求。在优先级选择时，当有两个节点优先级相同的情况下，通过空间密度来调度节点的充电顺序。

但是现存的采用按需充电方式的研究中，在决定节点的充电顺序时没有考虑到节点的能量消耗情况，导致能量消耗大的节点由于等待充电时间过长而导致节点死亡，从而网络整体生命期缩短。除此之外，一些按需充电的研究中都假定移动充电器的能量是无限的，因此没有考虑移动充电器移动所消耗的能量，这在实际应用中是不可取的。

发明内容

本发明旨在针对上述现有方法存在的问题，提出一种基于能耗和距离动态变化的按需充电调度算法。主要通过对节点能量消耗率进行建模得到不同节点的能量消耗率。基于能量消耗率和距离选择充电节点并建立充电节点返回服务站的虚拟封闭路径，然后利用基于节点剩余能量以及能量消耗率的充电路径可行性判断条件判断封闭路径的可行性，若路径可行且节点剩余能量足够维持到移动充电器Mobile Charger(MC)对其充电，则MC移动至节点对其充电直到达到自适应充电阈值。该算法有效减少了死亡节点数，在充电效率方面有较好的性能，延长了网络生命期。

本发明所采用的技术方案是，一种基于能耗和距离动态变化的按需充电调度方法，包括以下步骤：

步骤一、根据节点在一定时间内的能量消耗率信息，建立节点能量消耗率预测模型；

步骤二、根据步骤一得到的模型，得到节点能量消耗率，然后结合节点到移动充电器Mobile Charger即MC的距离，计算得到应进行充电的节点，即为充电节点；

步骤三、建立MC经过充电节点返回服务站的虚拟封闭路径，然后结合包括节点剩余能量、能量消耗率、MC移动速度、MC为节点充电的时间、MC在服务站补充自身能量所需时间在内的条件来对充电路径进行可行性判断；

步骤四、根据包括节点电池容量、节点能量消耗率在内的条件建立节点自适应充电阈值模型；

步骤五、综合步骤一到四，对整个网络中的节点进行计算，得到MC为各节点进行充电的路程规划方案，实现基于能耗和距离动态变化的按需充电调度方法。

所述的基于能耗和距离动态变化的按需充电调度方法，在所述步骤一中，节点能量消耗率预测模型如下所述：

表达式(1)中，R_i(t)是指节点在t时刻的能量消耗率，R_i(t+Δ)是指经过Δ时间节点的能量消耗率，E_i(t-Δ)是指节点在t-Δ时刻剩余能量，E_i(t)是指节点在t时刻剩余能量，α为控制因子，0＜α＜1。

所述的基于能耗和距离动态变化的按需充电调度方法，所述步骤二中包含以下步骤：

步骤1，根据发送充电请求的节点能量消耗率R_i(t)对节点进行降序排列，记为N_r，节点i所排序号记为N_r(i)；

步骤2，根据发送充电请求的节点和MC之间的距离D(i)对节点进行升序排列,记为N_d，节点i所排序号记为N_d(i)；

步骤3，通过表达式(2)得到基于距离与能量消耗率的每个节点的权重，选择P(i)值最小的节点作为充电节点，其中β为控制因子，0＜β＜1；

P(i)＝βN_d(i)+N_r(i) (2)

步骤4，如果得到的最小值P(i)唯一，则最小值P(i)对应的节点i为充电节点；如果最小值不唯一，即P(i)＝P(j)，则选择节点i和节点j中剩余能量较少的作为充电节点。

所述的基于能耗和距离动态变化的按需充电调度方法，所述步骤三中包含以下步骤：

步骤1)，建立充电节点返回服务站的虚拟封闭路径；

步骤2)，通过表达式(3)得到充电周期T，其中T_n为MC到达最后一个充电节点n所需时间，τ_n为MC在充电节点n的充电时长，v为MC的移动速度，D(n,0)为最后一个充电节点n返回服务站的时长，T_stay为MC在服务站补充自身能量所需时间；

步骤3)，通过表达式(4)得到MC到达第i个充电节点所需时长T_i，其中T_i-1为MC到达充电节点i-1所需时间，τ_i-1为MC在充电节点i-1的充电时长，D(i-1,i)为第i-1个充电节点到第i个充电节点的时长；

步骤4)，通过MC的移动时长与在每个充电节点的工作时长可以改写表达式(1),得到表达式(5),其中D是指整个封闭路径的长度，通过表达式(6)得到；

步骤5)，表达式(7)保证了每轮充电中节点能正常运行，其中E_th为节点警告能量阈值，R_i为充电节点i的能量消耗率；表达式(8)表明了节点在充电完成后剩余能量与所充能量的关系，其中Es为节点电池容量，η为节点的能量收集效率，c为MC给节点的充电效率；

E_th-R_i*T_i＞0 (7)

E_s＝E_th-R_i*(T_i+τ_i)+τ_i*η*c (8)

步骤6)，满足表达式(9)以保证MC充电路径中充过电的节点能量不会到能量警告阈值E_th；将表达式(8)与表达式(9)联立得到表达式(10)，保证了整个过程中节点i补充的能量比消耗的多，同时由单一节点满足表达式(10)推知整个网络中所有节点补充的能量比消耗的多，即得到表达式(11)，其中R_sum为所有节点的能量消耗率；

E_s-R_i*(T-T_i-τ_i)＞E_th (9)

τ_i*c*η＞R_i*T (10)

步骤7)，考虑MC的充电周期T中已经包含了节点的充电时间，即

为保证表达式(11)成立，因此得到表达式(12)；

c*η＞R_sum (12)

步骤8)，表达式(13)保证了MC的能量不少于路径中所有节点所需补充能量与MC在路径中移动所消耗能量的总和，其中MC的电池容量为E_w，其移动一米所消耗的能量为q_m；当且仅当路径中充电节点和MC分别满足表达式(12)，(13)时路径可行，否则路径不可行；

所述的基于能耗和距离动态变化的按需充电调度方法，所述步骤四中包含以下步骤：

步骤a，通过表达式(14)求出充电节点的自适应充电阈值E_ad，其中E_s为节点电池容量，通过表达式(8)求得，D_i表示充电节点i与MC之间的距离；

步骤b，节点在充电时，当其能量达到E_ad时就停止充电。

所述的基于能耗和距离动态变化的按需充电调度方法，所述步骤五中包含以下步骤：

步骤a)，网络中有n个发出充电请求的充电节点，N₀处为服务站所在位置，通过节点能量消耗率模型计算出各节点的能量消耗率；

步骤b)，根据步骤二选择充电节点i；

步骤c)，建立充电节点i返回服务站N₀的虚拟封闭路径(N₀,i,N₀)，每次将最新选择的充电节点加入之前的路径中，利用步骤三判断封闭路径的可行性，如果路径可行而且充电节点剩余能量可以维持到MC对其充电，将充电节点加入路径，MC移动至充电节点进行充电，否则重新选择充电节点；

步骤d)，根据节点自适应充电阈值模型，当充电电量达到自适应充电阈值E_ad时，MC离开；

步骤e)，重复步骤b)，c)，d)直到建立的虚拟封闭路径不可行或网络中没有节点需要充电，即n＝0时，MC返回服务站N₀进行能量补充。

下面结合附图和实施例对本发明作进一步描述。

附图说明

图1是本发明的流程图；

图2是本发明网络拓扑模型图；

图3和4是本发明虚拟路径构建实例图；

图5是本发明实施例提供的在充电吞吐量性能上的仿真对比实验；

图6是本发明实施例提供的在平均服务时间性能上的仿真对比实验；

图7是本发明实施例提供的在存活节点个数性能上的仿真对比实验；

图8是本发明实施例提供的在充电效率性能上的仿真对比实验。

具体实施方式

本实施例提供了一种基于能耗和距离动态变化的按需充电调度方法，参见附图1，包含以下步骤：

(1)建立节点能量消耗率预测模型:

构建区域面积为M×M平方米并且随机散布有m个传感器节点的无线传感器网络模型，有n个节点需要充电，一个移动充电器Mobile Charger(MC)从服务站出发对网络场景中需要充电的节点进行能量补充(参见附图2)。通过表达式(1)得到需要充电节点的能量消耗率，其中R_i(t)是指节点i在t时刻的能量消耗率，R_i(t+Δ)是指经过Δ时间节点i的能量消耗率，E_i(t-Δ)是指节点在t-Δ时刻剩余能量，E_i(t)是指节点在t时刻剩余能量，α为控制因子，0＜α＜1。

(2)建立基于节点能量消耗率以及到MC距离的充电节点选择算法：

根据发送充电请求的节点能量消耗率R_i(t)对节点进行降序排列，节点i所排序号记为N_r(i)。根据发送充电请求的节点和MC之间的距离D(i)对节点进行升序排列,节点i所排序号记为N_d(i)。通过表达式(2)得到基于距离与能量消耗率的每个节点的权重，其中β为控制因子，0＜β＜1；

P(i)＝βN_d(i)+N_r(i) (2)

基于节点能量消耗率以及到MC距离的充电节点选择算法详细描述如下：

(3)建立充电节点返回服务站的虚拟封闭路径以及基于节点剩余能量和能量消耗率的充电路径可行性判断条件：

步骤a，建立充电节点返回服务站的虚拟封闭路径；

为使构建充电节点返回服务站的虚拟封闭路径更易理解，本发明将举例说明如下：

1)第一个节点充电全过程(参见附图3)：

通过充电节点选择算法判断节点A为第一个充电节点，MC利用该节点建立一条返回服务站的虚拟封闭路径(虚线表示)，然后通过充电路径可行性判断条件判断该虚拟封闭路径可行，MC移动至节点A进行电量补充；

2)第二个节点充电全过程(参见附图4)：

待节点A充好电，通过充电节点选择算法判断节点E为第二个充电节点，MC利用该节点建立一条返回服务站的虚拟封闭路径(虚线表示)，然后通过充电路径可行性判断条件判断该虚拟封闭路径可行，MC移动至节点E进行电量补充。

步骤b，充电周期T的确定：通过表达式(3)，(4)，(5),(6)可以得到整个网络的充电周期T。表达式(3)中，T_n是指MC到达最后一个充电节点n所需时间，τ_n为MC在充电节点n的充电时长，v为MC的移动速度，D(n,0)是指最后一个充电节点n返回服务站的时长，T_stay为MC在服务站补充自身能量所需时间。表达式(4)中，T_i是指MC到达第i个充电节点所需时长，T_i-1为MC到达第i-1个充电节点所需时间，τ_i-1为MC在第i-1个充电节点的充电时长，D(i-1,i)是指第i-1个充电节点到第i个充电节点的时长。表达式(5)中，D是指整个封闭路径的长度，可以通过表达式(6)得到；

步骤c，每轮充电中节点正常运行的满足条件：通过表达式(7)可以判断节点是否能够维持正常工作直到MC为其充电，其中E_th为节点警告能量阈值，R_i为充电节点i的能量消耗率。表达式(8)表示节点在充电完成后剩余能量与所充能量的关系，其中Es为节点电池容量，η为节点的能量收集效率，c为MC给节点的充电效率；

E_th-R_i*T_i＞0 (7)

E_s＝E_th-R_i*(T_i+τ_i)+τ_i*η*c (8)

步骤d，补充过能量的节点不会再次达到能量警告阈值E_th的满足条件：通过表达式(9)可以保证已补充过能量的节点不会在一轮周期中不会再次达到能量警告阈值E_th。结合表达式(8)和表达式(9)可以得到表达式(10),该表达式表明在一轮充电周期中节点i补充的能量比消耗的多，以此过程推知表达式(11)，即对于全部请求充电节点而言，在一轮充电周期中所有节点补充的能量比消耗的多,R_sum为所有节点的能量消耗率。考虑到MC的充电周期T已经包含了节点的充电时长，因此

可以通过表达式(12)保证表达式(11)成立；

E_s-R_i*(T-T_i-τ_i)＞E_th (9)

τ_i*c*η＞R_i*T (10)

c*η＞R_sum (12)

步骤e，MC总能量水平：表达式(13)保证了MC总能量不少于路径中所有节点所需补充能量与MC在路径中所消耗能量的总和。其中MC的电池容量为E_w，其移动一米所消耗的能量为q_m。

步骤f，可行性判断条件：当且仅当路径中充电节点和MC分别满足表达式(12)，(13)时路径可行，否则路径不可行。

(4)建立节点自适应充电阈值模型：

MC移动至选定的节点为之充电直到充到自适应充电阈值E_ad后离开。通过表达式(14)得到自适应充电阈值E_ad，其中E_s为节点电池容量，可通过表达式(8)求得，D_i表示充电节点i与MC之间的距离。

(5)建立基于能耗和距离动态变化的按需充电调度算法：

MC从服务站位置通过充电节点选择算法选择第一个充电节点，找到第一个充电节点后利用该节点建立一个返回服务站的虚拟封闭路径，然后利用路径可行性判断条件判断虚拟封闭路径的可行性，如果路径可行且该节点的能量可以维持正常运作直到MC为之充电，则MC移动至该节点充电至自适应充电阈值后离开，如果路径不可行则再次利用充电节点选择算法选择下一个充电节点。重复这一“选择-判断”过程直到建立的路径不可行或者剩余待充电节点数目为0，此时MC返回服务站进行能量补充。具体地，基于能耗和距离动态变化的按需充电调度算法详细描述如下：

下面将对基于能耗和距离动态变化的按需充电调度算法进行充电吞吐量，平均服务时间，节点存活个数以及充电效率与Lin C等人“TADP TADP:Enabling temporal anddistantial priority scheduling for on-demand charging architecture inwireless rechargeable sensor networks，Journal of Systems Architecture,70:26-38.2016”中提出的TADP算法以及EDF算法，即最早死亡优先算法进行仿真对比实验。

1)充电吞吐量(参见附图5)：

具体地，充电吞吐量定义为，每个时间段成功充电的节点数。显然地，本发明提出的动态变化的按需充电调度算法的充电吞吐量随着时间推移在不断增大，并且相较于TADP算法和EDF算法，本发明中的算法能够明显提高每个时间段成功充电的节点数。

2)平均服务时间(参见附图6)：

具体地，平均服务时间定义为，节点发出充电请求与请求被完成，即MC移动至该节点对其完成能量补充过程所需的时长。平均服务时长越少意味着节点等待充电时间越短，同时网络中其它需要充电的节点由于能量耗尽而死亡的概率越小。相较于TADP算法和EDF算法，本发明中的算法能够明显减少平均服务时间。

3)存活节点个数(参见附图7)

显然地，本发明提出的算法在节点存活个数上相较于TADP算法和EDF算法有明显优势。这是由于本发明在MC充电过程中考虑了自适应充电阈值。每当正在补充能量的节点剩余能量达到自适应充电阈值，MC随即离开为下一个节点充电。这样就能够保证在MC为正在充电节点补充能量的过程中也兼顾了其它待充电节点由于能量耗尽而死亡的情况。

4)充电效益(参见附图8)

具体地，充电效益定义为，整个网络中所有节点所补充的能量与MC移动所消耗能量的比值。充电效益越大意味着整个网络性能越好。本发明在充电效益这一性能上要优于TADP算法和EDF算法。这说明本发明中提出的按需调度算法可以有效减少路由花费的能量，使更多的能量用于节点能量补充。

理论分析和仿真实验表明，本发明提出的基于能耗和距离动态变化的按需充电调度算法能够有效提高节点存活个数，减少平均服务时间，增大充电吞吐量和充电效益，从而延长网络的生命周期。

Claims (3)

1.一种基于能耗和距离动态变化的按需充电调度方法，其特征在于，包括以下步骤：

步骤一、根据节点在一定时间内的能量消耗率信息，建立节点能量消耗率预测模型；

步骤二、根据步骤一得到的模型，得到节点能量消耗率，然后结合节点到移动充电器Mobile Charger即MC的距离，计算得到应进行充电的节点，即为充电节点；

步骤三、建立MC经过充电节点返回服务站的虚拟封闭路径，然后结合包括节点剩余能量、能量消耗率、MC移动速度、MC为节点充电的时间、MC在服务站补充自身能量所需时间在内的条件来对充电路径进行可行性判断；

步骤四、根据包括节点电池容量、节点能量消耗率在内的条件建立节点自适应充电阈值模型；

步骤五、综合步骤一到四，对整个网络中的节点进行计算，得到MC为各节点进行充电的路程规划方案，实现基于能耗和距离动态变化的按需充电调度方法；

在所述步骤一中，节点能量消耗率预测模型如下所述：

表达式(1)中，R_i(t)是指节点在t时刻的能量消耗率，R_i(t+Δ)是指经过Δ时间节点的能量消耗率，E_i(t-Δ)是指节点在t-Δ时刻剩余能量，E_i(t)是指节点在t时刻剩余能量，α为控制因子，0＜α＜1；

所述步骤二中包含以下步骤：

步骤1，根据发送充电请求的节点能量消耗率R_i(t)对节点进行降序排列，记为N_r，节点i所排序号记为N_r(i)；

步骤2，根据发送充电请求的节点和MC之间的距离D(i)对节点进行升序排列,记为N_d，节点i所排序号记为N_d(i)；

步骤3，通过表达式(2)得到基于距离与能量消耗率的每个节点的权重，选择P(i)值最小的节点作为充电节点，其中β为控制因子，0＜β＜1；

P(i)＝βN_d(i)+N_r(i) (2)

步骤4，如果得到的最小值P(i)唯一，则最小值P(i)对应的节点i为充电节点；如果最小值不唯一，即P(i)＝P(j)，则选择节点i和节点j中剩余能量较少的作为充电节点；

所述步骤三中包含以下步骤：

步骤1)，建立充电节点返回服务站的虚拟封闭路径；

步骤2)，通过表达式(3)得到充电周期T，其中T_n为MC到达最后一个充电节点n所需时间，τ_n为MC在充电节点n的充电时长，v为MC的移动速度，D(n,0)为最后一个充电节点n返回服务站的时长，T_stay为MC在服务站补充自身能量所需时间；

步骤3)，通过表达式(4)得到MC到达第i个充电节点所需时长T_i，其中T_i-1为MC到达充电节点i-1所需时间，τ_i-1为MC在充电节点i-1的充电时长，D(i-1,i)为第i-1个充电节点到第i个充电节点的时长；

步骤4)，通过MC的移动时长与在每个充电节点的工作时长可以改写表达式(1),得到表达式(5),其中D是指整个封闭路径的长度，通过表达式(6)得到；

步骤5)，表达式(7)保证了每轮充电中节点能正常运行，其中E_th为节点警告能量阈值，R_i为充电节点i的能量消耗率；表达式(8)表明了节点在充电完成后剩余能量与所充能量的关系，其中Es为节点电池容量，η为节点的能量收集效率，c为MC给节点的充电效率；

E_th-R_i*T_i＞0 (7)

E_s＝E_th-R_i*(T_i+τ_i)+τ_i*η*c (8)

步骤6)，满足表达式(9)以保证MC充电路径中充过电的节点能量不会到能量警告阈值E_th；将表达式(8)与表达式(9)联立得到表达式(10)，保证了整个过程中节点i补充的能量比消耗的多，同时由单一节点满足表达式(10)推知整个网络中所有节点补充的能量比消耗的多，即得到表达式(11)，其中R_sum为所有节点的能量消耗率；

E_s-R_i*(T-T_i-τ_i)＞E_th (9)

τ_i*c*η＞R_i*T (10)

步骤7)，考虑MC的充电周期T中已经包含了节点的充电时间，即

为保证表达式(11)成立，因此得到表达式(12)；

c*η＞R_sum (12)

步骤8)，表达式(13)保证了MC的能量不少于路径中所有节点所需补充能量与MC在路径中移动所消耗能量的总和，其中MC的电池容量为E_w，其移动一米所消耗的能量为q_m；当且仅当路径中充电节点和MC分别满足表达式(12)，(13)时路径可行，否则路径不可行；

2.根据权利要求1所述的基于能耗和距离动态变化的按需充电调度方法，其特征在于，所述步骤四中包含以下步骤：

步骤a，通过表达式(14)求出充电节点的自适应充电阈值E_ad，其中E_s为节点电池容量，通过表达式(8)求得，D_i表示充电节点i与MC之间的距离；

步骤b，节点在充电时，当其能量达到E_ad时就停止充电。

3.根据权利要求2所述的基于能耗和距离动态变化的按需充电调度方法，其特征在于，所述步骤五中包含以下步骤：

步骤a)，网络中有n个发出充电请求的充电节点，N₀处为服务站所在位置，通过节点能量消耗率模型计算出各节点的能量消耗率；

步骤b)，根据步骤二选择充电节点i；

步骤c)，建立充电节点i返回服务站N₀的虚拟封闭路径(N₀,i,N₀)，每次将最新选择的充电节点加入之前的路径中，利用步骤三判断封闭路径的可行性，如果路径可行而且充电节点剩余能量可以维持到MC对其充电，将充电节点加入路径，MC移动至充电节点进行充电，否则重新选择充电节点；

步骤d)，根据节点自适应充电阈值模型，当充电电量达到自适应充电阈值E_ad时，MC离开；

步骤e)，重复步骤b)，c)，d)直到建立的虚拟封闭路径不可行或网络中没有节点需要充电，即n＝0时，MC返回服务站N₀进行能量补充。

Images