基于不同预估模型的充电调度算法的性能比较

陈晶晶，陈虹微，林坤智，白奥烔

(龙岩学院 福建龙岩 364000)

无线传感器网络(Wireless Sensor Networks，WSN)涵盖的应用领域极其广泛，同时也是物联网不可替代的关键性技术。它包含自然灾害预警、品质监控、健康医疗、仓库管理、智能家居等应用[1]。网络中的传感器节点负责收集和处理监控区域内传感对象的信息，并将信息发送给基站[2]。

能量一直在WSN中扮演着非常重要的角色。由于传感器节点体积小，能装载的电池容量有限，通过更换电池来延长无线传感器网络的生命周期比较困难。已有的研究大多数通过平衡电源消耗负载[3]、移动的数据收集方式[4]等方式来减缓能量的消耗速度，但是这些方式还是会耗尽电池能量从而减短了网络的生存周期。

由于无线充电技术(WET)发展迅速且极具优势，许多学者考虑采用WET技术为WSN补充能量。无线可充电传感器网络(WRSN)就是指利用无线充电技术为WSN中的传感器节点充电的网络。据了解，近几年的研究热点就是WRSN中采用移动无线充电车(WCV)为节点充电。

关于无线充电车的研究主要分为确定性或非确定性方法。在确定性方法中，WCV按照固定的调度路线进行周期性移动给传感器节点充电。但是由于节点消耗能量的不确定性，该方法缺少灵活性。在非确定性方法中，一旦节点的能量水平低于预先设定的阈值时，节点自身就会向基站发送充电请求。基站接收到这些充电请求会按所设计方案依次对小车进行充电调度[5]。过去的相关方案具有局限性，只考虑节点的剩余时间及节点在区域的地理位置这两个因素。由于网络具有复杂性，且充电调度不但受到节点的剩余时间制约而且受到节点的位置制约。以前的调度方法在性能方面并不理想，能够服务的充电请求节点数量有限，当网络繁忙时，容易因为部分节点得不到及时充电而导致网络中止。以前的研究从未从全局角度出发来考虑WCV总的移动成本。因此，本文从全局出发，首先提出优先考虑WCV的剩余充电成本。通过全局计算剩余充电成本可以适当减少WCV的移动距离，得到优化的充电调度。

本文在过去研究的基础上[6-7]进一步设计了三种不同的剩余区域规划模型来计算全局预估剩余成本。并在该模型的基础上设计相应的充电调度算法。该算法不仅考虑时间和空间因素，还考虑剩余预估成本因素。最后，对这三种模型进行了大量的仿真，从而根据仿真结果分析和比较这三种模型的优缺点。

1.1 符号和说明

文中使用的相关符号及相关说明如表1所示。

表1 符号及其说明

1.2 网络模型

所采用的WRSN模型如图1所示。该模型组成包括，数个传感器节点其分布具有随机性，一部充电小车，以及安置在区域的左下角的一个基站。并且针对该网络模型，本文做出如下假设。

图1 WRSN网络模型

(1)每一个传感器节点的性能都相同，其位置都是随机分布在感测区域内。一旦节点其剩余能量低于预设阈值时，节点会直接向基站发送充电请求。

(2)无线充电小车在感测区域中可以无限制自由移动，但是只能单节点充电作业。每次执行新的充电任务时小车都必须从基站出发，当且仅当到达节点附近才能服务该节点作业，并且完成服务作业后需要返回基站进行电池的更换。

(3)基站知道每个节点的坐标，能够迅速为小车规划出相关充电调度。

1.3 全局充电成本预估模型

本小节提出一种全新的全局充电成本预估数学模型。利用该模型可以估算出小车的剩余充电移动成本CR。考虑利用给定的剩余面积[6-7]来预估充电移动成本。本节首先将回顾剩余面积的概念，然后设计三个不同的数学预估模型，具体如下所示。

(1)剩余面积计算公式

剩余面积的定义就是剩余的未被选中服务的节点所围成的区域。小车在小的区域范围内移动，所产生的成本较低，反之，较高。因此，剩余面积越小，所产生的剩余预估成本就越小。如图2所示，节点A被选为小车调度的第一个要执行的充电任务时(即，V={A})，图中虚线围起来的区域就是剩余面积W-V;如果节点B被选中(即，V={B})，红色实线围起来的区域就是剩余面积W-V。由图2可知，AR(W-{A})比AR(W-{B})小[6-7]，所以会优先考虑先给节点A充电。

图2 剩余面积的示意图

(2)预估模型一：区域用凸多边形面积近似，内部划分为圆形

该预估模型的计算过程如图3所示。除节点A以外的剩余充电需求节点连起来，形成一个凸多边形。那么就可以根据公式(1)中计算凸多边形面积的方法来计算AR(W-{A})的值。然后，根据剩余节点数N的值对此凸多边形进行区域划分，平均分为N个大小相同的圆形图形。

图3 区域用凸多边形面积近似，内部划分为圆形

接着，预估小车的剩余移动成本。具体计算过程如图4所示：两个相邻节点间的距离约是圆半径的两倍。从节点A的剩余面积的划分当中可以看出，充电小车在剩余面积中的移动路径就是从一个圆的圆心移动到相邻圆的圆心。剩余节点有N个，则充电小车在这些节点间移动需要N-1次，所以，在剩余的面积中充电小车的移动成本为圆的半径2(N-1)倍。则圆半径的计算方法如公式(2)所示。

图4 用圆覆盖节点A的剩余面积

(1)

其中(xi，yi)是W-{A}的凸包中的节点坐标。

(2)

A节点的预估充电移动成本CR(A)通过公式(3)来计算。

CR(A)=2(N-1)r+dAS+dNBS

(3)

(3)预估模型二：区域用方形面积近似，内部划分为圆形

如图5所示，首先将节点A剩余面积形成一个方形，则该预估模型的剩余面积计算步骤如下所示。

首先，首先找出横坐标最大的两个点B(x1,y1)，C(x2,y2)，计算出图5中方形的底边如下所示：

a=|x1-x2|

(4)

其次，再找出纵坐标最大的两个点D(x3,y3)，E(x4,y4)。计算出方形的高如下所示：

b=|y1-y2|

(5)

则所构成的剩余面积如公式(6)所示。

AR(W-{A})=ab

(6)

由于节点A的剩余面积的内部单元同模型一类似，也是采用N个以剩余节点为圆心，半径相等的圆来划分的，因此节点A的剩余预估成本采用公式(2)、(3)计算。

(4)预估模型三：区域用方形面积近似，内部划分为正方形

如图6所示，首先将节点A剩余面积形成一个方形。则该预估模型的剩余面积计算步骤按模型二中公式(4)、(5)、(6)进行计算。

图6 区域为方形，内部用方形划分的模型

然后，将方形区域均等划分成N个形状大小统一的单元。其中剩余的面积AR(W-{A})中的节点的数目用N表示。每个单元均是一个以节点作为中心点，且各边长相等的正方形图形。

如图6所示，节点A的剩余面积中，每两个节点间的平均距离约等于正方形的边长。从一个正方形的中心点移到相邻的正方形的中心点就是充电小车在剩余面积中的移动路径。所以，充电小车需要移动的次数为N-1次，充电小车在剩余的面积移动的成本相当于是正方形图形边长的N-1倍。该正方形图形边长的计算方法如公式(7)所示。

(7)

优先级和剩余的预估成本二者具有因果关系，较少的预估成本会产生较高的优先级。因此，剩余的预估成本可用公式(8)计算。

CR(A)=(N-1)a+dAS+dNBS

(8)

1.4 算法设计

算法1 小车调度算法

本小节在充电小车的调度算法设计上采用剩余预估成本的概念，全局地考虑充电小车的调度问题，其算法描述如下所示。

该算法的第一步，计算节点的时间以及空间的优先权，第二步计算节点集中每一个节点的CR(i)值，进而根据CR(i)值的大小从中选择CR值最小的节点将其从U中移出并且将其加入到V中。不断重复地执行上述过程，一直到U为空集停止，从而小车的充电调度路径也被计算出来。

本小节通过大量的仿真来评估这三种预估模型的性能。

2.1 仿真设定

仿真的设计内容如下所示，将100个静态可充电节点随机部署到600 m×600 m的方形区域内。将基站置于区域的左上角，坐标为(0，0)。其他仿真参数的设置如表2所示。

表2 仿真参数

仿真中用节点持续进行工作的时间值来表示节点能量的阈值。WRSN在繁忙时会导致节点产生更多的能量的消耗，基站会频繁接收到来自节点的充电请求。因此，根据节点的充电请求的频率，设置空闲、适度、繁忙这三种类型网络仿真环境。在仿真实验中，三种类型都随时产生了100个充电请求，并且设置了5个能量阈值的范围(单位：s)，即500±100，700±100，...和1300±100。为了让预估模型更准确，仿真数据均为100次仿真实验结果的平均值。

2.2 性能比较与分析

所谓的WRSN的生存周期就是死亡结点第一次出现的时间，这是评估调度算法性能的一项十分重要的指标。仿真结果如图7所示。从图7中可以看出，任何一种模型的生存周期在网络空闲的时候都比其他两种网络状态时间要长。当能量阀值设置在(500±100) s时，三种模型的生存周期会有细微区别，但是区别不大。因为当能量阈值设置在(700±100) s或者更高以上的范围时，因为三种类型模型的生存周期都能够达到一样。所以三种算法均能够满足节点所有的充电请求。

图7 网络的生存周期

本文将能够在固定的时间段内满足发送充电请求的节点数，用成功充电的节点数来表示。若小车的充电消耗要求越低，充电节点的数目就必须越多。仿真结果如图8所示。从图8可以看出，在网络繁忙状态下，三种模型的充电节点数可以达到九十几个。在适中和空闲状态，充电的节点数可以达到100个。

图8 成功充电节点数

本文将小车移动的总距离除以完成充电请求的节点数定义为小车的平均移动距离。如果平均移动距离越短，就代表算法自身的性能越好。仿真结果如图9所示。从图9可以看出，三种模型充电的平均距离基本一致，这三种模型都能较好地预估剩余移动成本。

图9 平均充电移动距离

三种预估模型的误差如图10所示。从图10可以看出，模型二的相对误差最小，这说明模型二的精度更高一些。

图10 相对误差图

本文在按需充电的架构的基础上提出三种不同的预估模型。首先提出剩余预估成本的概念，并在此基础上设计三种不同的预估模型，在这三种模型的基础上设计了相关的充电调度算法。最后通过大量的实验仿真分析和比较这三种模型的网络性能和相关预估误差值。从仿真结果可以看出，三种模型的性能一样，但是区域用方形面积近似，内部划分为圆形这一模型的相对误差最小。

尽管文中的模型提出了令人振奋的新观点，但是我们仍然需要做更多的研究工作。作为未来研究工作的一部分，将对模型进行进一步细化和证明。