倪克松 丁宁 张哲

（青岛理工大学 山东省青岛市 266520）

1 前言

无线可充电传感器网络WRSN 在计算技术、无线通信和嵌入式技术领域中有广泛的应用场景。WRSN 包括三个部分：一个数据中心（DC）、若干传感器和单个或多个移动充电器（MC）。

实际工作过程为：

（1）MC 离开数据中心；

（2）寻找下一个传感器；

（3）为传感器充电；

（4）寻找下一个传感器。

移动充电器的能源一部分用在为29 个传感器进行充电，另一部分在路上消耗。为使移动充电器在移动过程中实现能量消耗最小化，需要对其进行移动路线规划。问题提出：分别在单个和多个MC 运作情况下求解最优路径，使得MC 能耗最小，并求解两种最优路径下系统正常工作的每个传感器最小电容量。

2 问题分析

（1）通过对单个MC 移动路径的调度和优化，使得其走过的路径长度尽量的短。把不同的传感器抽象成节点，已知每个节点的经纬度，可以得到每个节点到任意节点以及到数据中心之间的距离。由于MC 的移动路径必然是一个过每个点的闭合路径，即是一个Hamilton 圈，最优圈即为最优路径。

（2）当MC 的移动路径已经固定时，根据已有的节点能量消耗速率、传感器最低工作阈值f，MC 移动速率v 以及充电速率r，即可以唯一确定对于某一个节点所需要的最低电容量。

（3）在第二问的基础上，引入虚拟起始节点，将4 个MC 移动规划问题转换为单个MC 规划问题。在该最优路径下求解满足系统正常运行各个MC 路径上的传感器最低电容量，传感器节点被分为4 组，增加约束4 个MC 工作周期相同，求解模型与问题二相似。

3 模型假设

为了便于解决问题，提出如下假设：

（1）MC 可携带的能量足够大，可以完成一个周期的充电任务；

（2）MC 一旦移动到传感器节点，能立即对传感器进行充电；

（3）充电过程中前一MC 回到数据中心，后一MC 马上出发；

（4）该无线传感网络图为强连通图，即任意两个节点之间都存在路径。

4 模型的建立与求解

4.1 单个MC情景下的最优路径及最小电容量

首先，附件1 中的数据中心及传感器的位置通过地球上的经纬度坐标给出。将地球近似为标准球体，以零经度零纬度分别作为笛卡尔坐标系的x 轴与y 轴，在坐标系中寻找最优路径，后再转化为距离进行输出。

取地球半径R 为6371km，设第i 个节点(xi,yi)与第j 个节点(xj,yj)之间的距离为lij，转换公式为：

可通过两点间距离公式计算，各节点的直角坐标计算各点的平面距离。

移动充电器从数据中心x1出发，每节点恰通过一次，最终回到起始点x1，即不重复地行遍所有节点再回到出发点，其形成的闭环图形为一个典型的Hamilton 圈[1]。问题转化为典型的TSP 问题，利用改良圈算法来解决该问题。

已知传感器节点个数为29，rij=0 或1，其中：

则有目标函数Z 为：

约束条件为：

目标函数式（3）表示移动充电器所经过的路程之和的最小值。

式（5）是由C 中删去边xixi+1和xjxj+1，添加边xixj和xi+1xj+1而得到的。然后适当修改C 以得到具有较小权的另一个Hamilton 圈，这种方法为改良圈算法。若则以Cij代替C，Cij为C 的改良圈，以此不断进行改进直到无法进行，即得最优圈。

表1：单个MC 运作下每个传感器最低电容量单位：mA

表2：单个MC 运作下每个传感器最低电容量单位：mA

改良圈算法得到的结果几乎不是最优的，为得到更高的精确度，可以选择不同的初始圈C，重复进行几次，以得到更优结果[1]。采用蒙特卡洛模拟生成一个随机的初始圈，在大量Hamilton 圈中选择长度最小的圈即为最优圈，假设最优圈的长度为L(x)，L(x)满足下列目标函数为：

使用MATLAB 给出生成各种随机数的命令，运用蒙特卡洛模拟对随机数进行枚举给出初始圈，在多次随机生成的300000 个Hamilton圈中，得到的最优圈为1→18→21→20→19→26→27→3 0→22→24→25→29→23→5→4→6→11→14→17→28→16→13→9→12→15→7→8→10→3→2→1，长度为8.52km，最优Hamilton 圈有两个，它们路径长度相等，路径方向正好颠倒，其他的Hamilton 圈为次优圈。

由附件2 可知每个传感器节点的经纬度和能量消耗速率，移动充电器的移动速度为v(m/s)、充电速率为r(m/s)。

设当MC 移动到每个传感器时，该传感器的电量恰好为f(mA)，第i 个节点的能量消耗速率为pi，满足r>pi即MC 充电速率大于传感器能量消耗速率。

其中，Qi为第i 个节点的电池容量，l总为充电路线的总长，ki表示第i个节点的充电时间。不等式左边表示第i个节点的生存时间，不等式右边表示第i 个节点从充完电到下一次充电的时间。

其中，ki为：

k总为节点的充电时间总和，即

MC 的路程总长l总与移动速率v、充电速率以及每个传感器节点的能量消耗速率p、剩余电池容量f 已知。将（8）、（9）式代入（7）式即可得只含未知量Qi的不等式，则问题就转化为求解满足不等式的最小Qi，即

对于每一个，都有对应的一个上述形式的最优化问题。这些问题的限制条件构成了一个不等式组。为了便于表达，下面令Si为第i 个节点的可充电容量，ki第j 个节点的充电速率与能量消耗速率之差，即

则有

显然，对于任意一个i，当且仅当公式（15）中的不等式取等号时，Si取得最优解。于是对于得到的非齐次一维线性等式组，经过整理后可以用矩阵表示如下：

令上式的系数矩阵为A，未知数向量为S。上述等式的左右两边同时右乘系数矩阵的逆即可得到解集S，因为最低传感器工作电量f 为定值，故可求得每一个传感器的最低电容量Qi。

下面对实际情形进行了仿真，对于充电速率r=10000mA/h，总路长l=8.52km，f=2mA，MC 移动速度v=0.01km/s 的情况下，每一个传感器的最低存电量如表1所示。

4.2 多个MC情景下的最优路径及最小电容量

为达到MC 充电效率的最大化目的[2]，需要多个移动充电器之间相互配合或者独立负责一部分传感器节点的充电。

为了减少总行程长度，会有m-1 个MC，每个MC 总是只经过最接近起始节点的m-1 节点中的一个就回到了出发节点，剩余的n-m+1 个节点只由一个MC 遍历。由于这种方法不符合实际需要，所以规定每个MC 允许经过的节点不超过一个上限值。

引入m-1 个虚拟起始节点，其中m 为移动充电器的数量，并且设虚拟节点的坐标为数据中心的坐标[3]，分别为xn+1…,xn+m-1，即将MTSP 问题转化为TSP 问题。

变量定义如下：n 为给定的节点数，m 为MC 个数，N=n+m-1为总的节点数即实际节点与虚拟节点之和，i,j 为节点序号，lij为节点i 到节点j 的距离，其中虚拟节点之间和虚拟节点与数据中心之间的距离为无穷大；emax表示MC 允许经过的节点数量的上限，其中，为一条经过所有节点的环路。则MTSP 转化为TSP 后的最优圈长度L(x)模型为：

模型建立与单个MC 模型类似。

分别对4 个MC 的移动路线标号为①②③④，并求各自组内传感器模型类比于问题二，约束条件如下所示：

其中，k总为每一组路线的充电时间总和，l总为每一组路线下4个MC 的移动距离之和，ki表示第i 个节点的充电时间，各个变量的关系见问题二中模型的建立部分。

实际问题路径长度不同，充电节点数也不完全一致，每个MC的工作周期不同，为了保证4 个MC 的周期相同，建立模型：

通过标准差来限制MC 的充电节点数（工作能力），模型为

式（18）中zj为每条MC 路径中节点数，为4 条路径的平均节点数，标准差越小，MC 工作能力越接近。

由问题二得一个周期内主要工作时间在MC 移动过程中。求解满足不等式的每个传感器节点的最小电容量

（1）对MC 充电能力不加以限制时，只考虑MC 工作，不考虑工作能力和工作效率时，3 个MC 只对一个传感器节点进行充电后就回到了数据中心，剩下节点都由一个MC 来进行充电，但这种方式不切实际。

（2）对MC 能力进行限制时，使每个MC 工作能能力尽量相同，以每个MC 充电节点数的离差来衡量小车的工作能力，进行了多次仿真求解，每次在蒙特卡罗模拟给出的300000 个初始圈中寻找最优Hamilton 圈，路径总长越短越好，最常路径越短越好，这两个优化目标需同时满足。

最优路径为：①：1→5→22→24→25→29→23→4→1；②：1→3→9→12→15→7→8→10→2→1；③：1→21→19→26→27→30→20→18→1；④：1→6→11→14→17→28→16→13→1。

定义一个惩罚因子：

评价指标=路径长度+惩罚因子×4 个MC 路线经过的节点个数的离差，即评价指标越小，双目标优化效果越优。

该最优路径的路径总和为10.27km，最长路径为2.24km，评价指标为1.24，4 个MC 对应的节点个数分别为7、8、7、7 条，该路径的评价指标最小。

在该最优路径下，对每条路线上的最小电容量进行求解，结果为表2。

表2中各传感器节点的最低电容量比较小，原因：①传感器节点消耗功率非常小；②模型可以等价于MC 一直在工作，电容量较小时即可保证系统正常运行。

5 结论

本文将蒙特卡洛算法与改良圈算法相结合，多次搜索得到Pareto 最优解；单个MC 路径被分为4 条MC 路径，路径变短，工作周期变短，传感器等待下一次充电时间变短，每个传感器的最低电容量变小，有利于电池制作成本的降低，有较大的商业价值。接下来的研究方向：各个传感器节点的能量消耗功率不同，应从剩余能量最小的节点优先进行充电[2]，以此为优先约束条件，考虑这样运作的MC 的充电效率影响和能量损耗，达到将MC 能量更多地用于充电过程的目标。