基于全向无线充电模型的动态调度优化方法

陈路 陈凛 马辉

摘  要： 如何延长网络寿命是无线传感网络中一个关键问题，为此提出了基于全向无线充电模型的动态调度优化方法，目标是最大化网络寿命。文章对充电小车的停止点选择进行了分析，根据全向无线充电模型的覆盖范围确定了充电小车的停止区域，再以最大化节点接收功率之和为优化目标确定每个区域内的最佳停止点。实验结果表明，所提出的方法能够延长网络寿命，与MRCR（Multi-node Renewable based on Charging Range）算法相比，可延长网络寿命约3%～113%。

关键词： 无线可充电传感网络; 全向无线充电模型; 移动调度; 停止点选择; 网络寿命

中图分类号：TP393          文献标志码：A     文章编号：1006-8228（2019）09-20-04

A dynamic scheduling method based on omnidirectional wireless charging model

Chen Lu， Chen Lin， Ma Hui

（Hangzhou Dianzi University， Hangzhou， Zhejiang 310018， China）

Abstract： How to extend network life is a key issue in wireless sensor networks. In order to solve this problem， a dynamic scheduling strategy based on the omnidirectional wireless charging model is proposed， with the goal of maximizing network lifetime. In this paper， the selection of stop point of charging car is analyzed， and according to the coverage of omnidirectional wireless charging model， the stop area of charging car is determined， and then the optimal stop point in each area is determined by maximizing the sum of receiving power of nodes. The experiment results show that the proposed method can prolong the network lifetime， which is about 3%～113% longer than MRCR （Multi-node Renewable Based on Charging Range） algorithm.

Key words： wireless rechargeable sensor network; omnidirectional wireless charging model; mobile scheduling; stop point selection; network life

0 引言

无线传感器网络通常由大量微传感器节点、汇聚节点和基站组成。节点通常配备监测模块、信息处理模块以及信息收发模块[1-2]。传统的节点使用电池供电，电池容量严重限制了节点寿命[3]。为了解决能量有限问题[4，6]，随着无线能量传输技术的出现与发展，可以利用该技术给节点提供稳定的能量。

据我们了解，Xie等人[7]是第一个把无线能量传输技术应用到无线传感网络中的。作者将全向无线充电模型抽象为正六边形，并且将二维传感网络划分为若干个相邻的正六边形，六边形的边长即为充电器的最大覆盖距离，充电小车只需要停止在六边形的中心即可对蜂窝内的所有节点进行充电。针对同样的问题，Wu等人[8]给出了更灵活的划分方法即首先将全向无线充电模型抽象为圆形，然后以各个圆形相交区域的顶点为候选停止点，最后以最短化小车的移动路径为优化目标从候选停止点中选出最终的停止点。

然而，从充电的角度研究该问题，我們会发现，更好的解决办法不仅要考虑节点是否在充电器的最大覆盖范围内，还应该考虑由充电器与节点之间的距离产生的能量衰减问题。所以，在我们的解决办法中，还会考虑最小化节点与充电器间的距离和，从而最大化节点接收到的总能量。

1 问题描述

全向无线充电模型，如图1所示，基于的无线充电原理是磁共振耦合，功率衰减模型如式⑴所示。

[Prd=Pout?（-0.0985?d2-0.0377?d+1）]   （1）

其中，[Prd]表示节点的接收功率值，[d]表示节点和充电小车间的距离，[Pout]表示充电小车的输出功率。假设[Pout=5W]，节点接收功率的最小阈值为[1W]，那么充电小车的能量最大传输距离[D]约为[2.7m]，只要节点与充电器的距离不大于[D]，充电器就可以同时对多个节点进行充电。

假设每一个节点的电池容量为[Bmax]，节点电池能量低于一个最小阈值[δ]即停止工作，有一个节点停止工作则整个网络寿命终止。为了公式化这个问题，以下将节点表示为[O={o1，o2，…oN}]，节点[oi]的位置表示为[（oxi，oyi）]。假设充电小车的停止点集合为[S=s1，s2，…sM，]，第[k]停止点[sk]的位置为[（sxk，syk）]，在这个位置可以充电的节点集合为[SN（sk）]，那么当[oi∈SN（sk）]时，假设节点[oi]和充电小车停止位置[sk]的距离为[dk，i]，可以根据式⑴得出相应的接收功率为[Pr（dk，i）]。进一步假设，节点[oi]在[t]时刻的能量为[ei（t）]，为了保证充电的有效性，每次给节点充电至少要使得节点的电量达到一个最小值[Bmin]。那么每个节点的充电时间[ti]要满足式⑵。

[max 0，Bmin-ei（t）Pr（dk，i）≤ti≤Bmax-ei（t）Pr（dk，i）] （2）

充电小车在停止点[sk]能够覆盖到的节点集合为[SN（sk）]，那么充电小车在这个停止点的停留时长要满足该集合内所有节点的能量需求。假设充电小车在停止点[sk]的停留时长为[?Tk]，那么[?Tk]要满足式⑶。

[ （3）]

直观地，充电小车在每个位置停留的时间越长，节点接收到的能量越多，也就能够最大限度的延长该区域内节点的寿命，但是可能会导致后面还没有充电的节点由于能量太低而停止工作，因此充电小车在每个位置的停留时间也不能太长。下面用[L]表示充电路径的长度，[v]表示充电小车移动的速度，[ωi]表示节点[oi]的能量消耗率。至此，本文给出最大化网络寿命的优化公式：

[maxk=1M?Tk+Lv]   （4）

[（5）]

[Prdk，i=（-0.0985dk，i2-0.0377dk，i+1）Pout]  （6）

[dk，i=（sxk-oxi）2+（syk-oyi）2]   （7）

[δ≤eit≤Bmax，oi∈SN（sk）]  （8）

式⑸计算充电小车在每个停止点停留时间的上限和下限，式⑹和式⑺计算每个节点的能量接收功率，式⑻确保每个节点的剩余能量值大于阈值。对于一个连续的二维无线传感网络，充电小车能够停止在任意位置，如果充电小车的停止位置不事先确定，式⑺的距离无法确定，相应的式⑹中的充电功率也就无法确定，最终导致无法得出式⑷的解。下面对停止的选择进行分析给出近似算法。

2 停止点选择分析

基于全向无线充电模型，只要节点和充电器间的距离不大于[D]，二者就能量进行能量传输。以节点为圆心，以[D]为半径作圆，充电小车只要停止在这些圆的相交区域内就可以同时对圆心处的节点进行充电。如图2所示，以节点[o1]、[o2]和[o3]为圆心，以[D]为半径作圆，那么图中可以对节点充电的区域有四个，分别为[a1]、[a2]、[a3]以及[a4]，充电小车只需要停在区域[a2]和[a4]即可实现对所有节点的充电。

当网络中有大量的节点时，这些圆的相交区域的数量可能也会很多，如果充电小车在每个相交区域都停止一次，那么不仅会导致充电小车的移动路线过长，造成能量浪费，还可能会导致后面的节点由于没有及时的得到能量补充而耗尽能量。为了尽量避免这样的问题出现，本文考虑以最少的停止次数覆盖到网络中的所有节点。下面给出最少化停止次数的非线性规划公式如式⑼。

[[mink=1numαk βk]

[fi，k=1，如果节点oi∈SN（ak）0，如果节点oi?SN（ak）]      ⑼ ]

公式⑼中，[ak]表示第[k]个停止区域，[SN（ak）]表示区域[ak]能覆盖到的节点集合;[fi，k]表示节点[oi]是否属于第[k]个停止区域的充电集合;[βk]表示是否选择第[k]个候选停止位区域，[βk=1]表示选择，相反则表示不选择;[num]表示总的候选区域个数。[num]个不等式确保每个节点至少属于一个被选择的停止区域。

假设停止次数确定为[M]个，停止区域集合确定为[Area=a1，a2，…，aM]，[ak]能覆盖到的节点集合为[SN（ak）]。但是在[ak]内充电小车的停止点仍然是无数个，需要在[ak]内确定一个最佳的停止点[sk]。在[ak]内的最佳停止点[sk]是指，最佳停止点定义为区域内所有节点的能量接收功率之和最大的点，这样能够最大化节点接收到的能量。[Area]中的每个停止区域都对应于一个最佳停止点，停止点集合记为[Stop={s1，s2，…，sM}]。由于节点接收功率是随着距离增加而衰减的，充电功率和最大也就是距离和最小，因此本文将问题转化为求距离和最小的点，公式化如式⑽。通过式⑽就能够确定在每个停止区域的停止点[sk]，以及覆盖到的节点集合[SN（sk）]。

[[minoi∈SN（ak）dk，i]

[s.t. dk，i=（sxk-oxi）2+（syk-oyi）2]      ⑽ ]

該问题的一个特例是最小覆盖问题，因为最小集合覆盖问题为一个NP难问题，那么该问题也是一个NP难问题。

3 停止点选择算法设计

由于停止点选择问题是一个NP难问题，本文提出一个近似算法，即“停止点选择”进行求解，算法步骤为：

步骤1 输入节点集合为[O={o1，o2，…oN}]、节点[oi]的位置[ （oxi，oyi）]以及充电小车最远覆盖距离[D];

步骤2 以每个节点为圆心，以[D]为半径画圆;

步骤3 确定每个圆的相交区域;

步骤4 确定每个相交区域覆盖到的节点集合;

步骤5 通过最小集合覆盖算法确定最少的停止区域，能够覆盖到所有的节点，最终的停止区域集合为[Area=a1，a2，…，aM];

步骤6 在每个停止区域内通过求解公式（10）确定最佳的停止点，输出停止点集合为[Stop={s1，s2，…，sM}]。

4 仿真实验

4.1 确定充电小车停止点

在25*25的网络中随机抛洒50个节点，得到的充电器停止位置如图3所示，从图中可以看出没有节点被遗漏，并且充电小车能够尽可能停止在距离节点较近的位置。

4.2 网络寿命

在25*25的网络中抛洒60～140个节点，分别使用本文提出的停止点选择算法和MRCR算法[15]确定充电小车停止点的坐标，计算并记录停止点选择算法相较于MRCR算法对网络寿命的延长提升的百分比，结果如图4所示。从图4中可以看出对于网络寿命的延长，使用停止点选择算法相较于使用MRCR算法，对于网络寿命延长提升了约3%～113%。

5 结束语

本文提出的基于全向无线充电模型的动态调度优化方法，目标是最大化网络寿命，实验结果表明本文所提出调度方法能够延长网络寿命，并且相对于MRCR算法网络寿命的延长效果有所提升。將该充电策略应用于无线可充电传感网络中能够最大限度的延长网络工作时长，未来我们将进一步研究基于全向无线充电模型的动态调度策略，目标是在确保网络无限运行的前提下最大化充电小车的能量利用率。

参考文献（References）：

[1] 黄锋，刘士兴，顾勤东.无线传感器网络节点概述[J]. 合肥工业大学学报，2008.31（8）：1208-1212

[2] 缪海星.无线传感器网络的移动数据收集及充电规划研究[D].华侨大学，2016.

[3] 丁煦.可充电无线传感器网络能耗模型及充电策略研究[D].合肥工业大学，2015.

[4] Erol-Kantarci M，Mouftah H T.Suresense： Sustainable wireless rechargeable sensor networks for the smart grid[J]. IEEE Wireless Communications，2012.19（3）：30-36

[5] He Shibo，Chen Jiming，Jiang Fachang，et al. Energy provisioning in wireless rechargeable sensor networks[C]. Shanghai： IEEE INFOCOM，2011.

[6] He Tengjiao，Chin K W，Soh S.On using wireless power transfer to increase the max flow of rechargeable wireless sensor networks[C].Singapore：IEEE Tenth International Conference on Intelligent Sensors，2015.

[7] Xie Liguang，Shi Yi，Hou Y T，et al.Multi-Node Wireless Energy Charging in Sensor Networks[J].IEEE/ACM Transactions On Networking，2015.23（2）：437-450

[8] Wu Guowei，Lin Chi，Li Ying， et al.A Multi-node Renewable Algorithm Based on Charging Range in Large-Scale Wireless Sensor Network[C].Blumenau： International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing， 2015.