无线可充电传感器网络充电调度算法研究

郑 翔，孙 霞，许彤彤

(1.安徽理工大学，安徽 淮南 232001；2.阜阳师范大学，安徽 阜阳 236037)

0 引言

随着物联网技术的不断发展，为了保证无线传感器网络的工作性能,人们加大了对节点供电的研究力度［1］。文献［2-4］从无线传感器网络自身入手，探究了无线传感器网络节点最佳部署方式和最优能量供应方式，但没有对充电过程做出进一步阐释。文献［5］研究了无线可充电传感器网络中节点能量消耗问题，提出了不同的避免节点发生故障的充电方案。但从其结果上来看，并没有将节点故障率降至最低。因为在普通的TSP 模型中，无线充电能力没有得到充分利用。文献［6-7］重点探究了无线传感器网络中的移动充电设备路径规划问题，从而降低移动充电器的移动时延。但其仅仅探究了移动充电设备的行驶路径，并没有对其他调度细节做出规划和设计。当一个无线传感器网络节点数较多时，若只部署一个移动充电设备很难完成系统的充电要求。文献［8-9］研究了多个移动充电设备协同为无线传感器网络充电的合理调度问题，但其并没有平衡移动充电设备数与无线传感器网络规模的关系。

本文深入研究了移动充电设备数与节点数之间的关系，并且通过实验方式实证研究了发送充电请求的能量阈值大小，在python 软件上验证该算法。不难看出，此充电系统具有较高的稳定性和较长的网络生存周期，对于当前无线传感器网络的充电方式具有借鉴意义和应用价值。

1 网络模型

本文提出一种多移动充电设备（Multi-mobile charging device）通过无线充电技术为无线传感器网络补充能量的网络模型。在网络中心处安置一个维护站，作为MCD完成一次充电调度后的停留地与能量补充点。在一次充电调度中，每个MCD都会为一部分传感器节点充电，当MCD完成一次充电调度返回维护站时即开始准备下一轮充电调度，这时能量达到警戒阈值的传感器节点就会向基站发送充电请求，基站发送指令给MCD、MCD 遍历这些传感器节点为其充电。假设一次充电调度为Πmpl,i，m为充电调度的轮数，l为MCD 的序号，i为被遍历的传感器节点序号。MCD 给一个传感器节点充电完成后，在其驶向下一个传感器节点的过程中可以选择其他没有发送充电请求但是能量不是很充足的传感器节点进行充电。图1为网络模型图。

图1 网络模型图

1.1 无线充电模型

MCD 在给传感器节点充电的过程中遵循（1）式所示模型［10］。

图2 电气连接图

1.2 充电调度

MCD 在一定时间内从维护站出发完成一轮充电调度回到维护站的过程称为一个充电调度周期。在此期间，MCD 和节点的剩余能量都不得低于某一特定的值。一次充电调度完成到下一次充电调度开始的时间间隔称为调度间隔［12］。

1.3 传感器节点与MCD的能量限制

为了保证无线传感器网络稳定，必须使传感器节点是有能量的。若传感器节点的能量低于阈值Emin，节点即将死亡，因此必须保证传感器节点能量时刻不低于Emin。（2）式为传感器节点的能量约束式。MCD 完成一次充电调度需携带的能量如（3）式所示，其储存的能量主要用于MCD在传感器节点间的行驶和给传感器节点充电。Em(i)为第m次充电调度开始时传感器节点i剩余能量，pi为传感器节点的能量消耗功率，pw为MCD 的移动功率，L为哈密顿环的长度，N为在一次充电调度中遍历的传感器节点数，τm(i)为在第m次充电调度中移动充电设备给第i个传感器节点充电的时间。

2 MMCD优化调度算法

2.1 为无线传感器网络分配MCD

在一个较大的无线传感器网络中，若只用单个MCD，很难满足系统的充电需求，并且在此唯一的MCD 发生故障时，无线传感器网络得不到及时的能量补充，系统就会崩溃。因此考虑采用MMCD 优化调度算法为无线传感器网络充电。但并不意味着MCD 越多越好，设备数过多时会增加不必要的成本，设备数不够时又不能满足充电需求。本算法旨在找出满足系统稳定性的前提下最少的MCD 数。现以一个较大规模无线可充电传感器网络为例，假定在一次充电调度中所有节点都需要充电，这时为其调配p个MCD。大的无线传感器网络被分成了p个小网，给前p-1 个MCD 分配相同数量的节点，并将剩余节点分配给最后一个MCD，这是为了保证每个MCD 的充电负荷大致相同。因为前p-1 个网具有相同节点数，这里首先确定访问点顺序，然后建立哈密顿环需要强调的是，当MCD运动到哈密顿环中的最后一个节点时，节点剩余能量必须不低于Emin。以此得出关系式（9），该算法涉及到的参数及其含义如表1所示。

表1 算法中涉及的参数及其含义

在第m 次充电调度中，任意一个传感器节点将剩余能量用至最低所需要的时间，如（4）式所示。

只需知道MCD到达一个传感器节点的时间，给其充电的时间和向下一个传感器节点行驶的时间，就可以推算出到达下一个传感器节点的时间，如（5）式所示。

某一个MCD在其充电调度中，到达哈密顿环中最后一个传感器节点的时间不得大于最后一个节点能量用尽的时间，如（6）式所示。

以哈密顿环中第一个传感器节点为例，MCD 从基站行驶到第一个传感器节点的时间即为到达该传感器节点的时间，如（7）式所示。

MCD 在哈密顿环中第一个传感器节点停留的时间即为为其充电的时间，如（8）式所示。

在哈密顿环中，传感器节点数需与MCD数满足如（9）式所示的不等关系。

2.2 无线传感器网络中充电节点分类

在无线传感器网络中存在三种类型的节点：第一类是能量达到预先设定阈值的节点，其剩余能量已经不足以支撑一个完整的充电调度周期，必须为其充电；第二类是能量不够充足，最好适当给其补充一部分能量；第三类是能量很充足的节点，在当次充电调度中不必为其充电。我们首先要确定将传感器电池还剩多少能量定为向基站发送充电请求的阈值能量。每一个节点都必须满足：当节点能量达到阈值预警时，MCD 必须已经到达该节点，并对该节点进行充电。即满足（10）关系式，此时的警戒阈值称为第一警戒阈值。

除此之外，还有一种节点也是必须充电的节点，虽然在当次充电调度中这些节点的能量足以支撑到此次充电调度结束，但是在下一次充电调度中，MCD 到来之前，这些节点能量已经耗尽，所以此类节点在当次充电调度中也是必须充电的节点。此类节点满足的关系式如（11）式所示。这些节点满足的警戒阈值为第二警戒阈值。式（12）为一个充电调度周期总时间的计算式。

3 仿真实验与结果分析

3.1 仿真环境与参数设置

实验采用软件python3.6 进行仿真和调试，计算机 配 置 为Intel（R）Core（TM）i3 - 4130 CPU@3.40GHz，4.00 GB RAM。100 个节点随机分布在100m×100m 被监测区域内，基站和维护站均位于（50，50）处。网络模型如图3所示。

图3 网络模型

实验参数设置如下：节点电池容量Es=50J，节点能量最低阈值Emin=5J，MCD 运行速度v=0.5m/s，MCD 移动功率pw=6J/m，无线充电线圈发射功率pr=8J/s，节点最小能量消耗功率pimin=0.005J/s。节点最大能量消耗功率pimax=0.015J/s，充电效率η=0.5。

3.2 节点数与充电能量阈值的关系

无线传感器网络的节点数与充电能量阈值之间存在一定的关系。当一个MCD 负责充电的节点数变化时，第一警戒阈值和第二警戒阈值会随之发生变化。

图4 能量阈值q和q’的变化情况

从仿真结果可以看出，无线传感器网络的节点数和充电能量阈值关系如图4所示。图中的上面一条线代表第二充电阈值q’随着网络规模大小变化时的变化情况，而下面的线代表第一充电阈值q随着网络规模大小变化时的变化情况。可以看出随着无线传感器网络规模的增大q’是稳定在q的上方的，这和预期的结果是相同的，可以根据此结果确定发出充电请求的能量阈值。

3.3 网络规模与充电设备数量的关系

网络规模和最优移动充电设备数之间的关系，仿真结果如图5所示。

图5 网络规模和最优移动充电设备数之间的关系

根据算法得出网络规模和最优MCD 数之间的关系，不难发现，从本实验采用的100个节点的网络规模来看，最优的MCD数是3个。

图6 网络性能测试图

图6 是网络性能测试图，通过将本文中的MMCD 算法与已有的EDF 算法作对比，不难看出，随着系统运行时间的增加，无线传感器网络中节点存活率更高，存活率高则说明算法更优。从仿真结果可以看出，本文算法和已有算法相比，在提高网络寿命方面明显更优。

4 结论

针对当前大规模无线可充电传感器网络能量供应方式的不足，综合考虑了MCD数量和最低充电能量阈值的影响，研究如何调度最少的MCD来给具有生命周期的传感器节点高效充电的问题。本文提出一种新的近似算法，通过仿真实验得出结论，不仅证明了该算法具有较好的性能，而且对算法涉及到的核心参数进行了研究。与现有算法相比，本算法具有较长的网络寿命。