¹青岛理工大学管理工程学院，山东 青岛

²青岛理工大学信息与控制工程学院，山东 青岛

³青岛理工大学理学院，山东 青岛

收稿日期：2021年8月3日；录用日期：2021年8月25日；发布日期：2021年9月7日

摘要

充电路径的合理规划是保证无线可充电传感器网络稳定运行的关键。本文将该类问题抽象成MTSP问题，提出了一种多MCV工作的充电路径规划模型。通过预估可能解的数量，利用模拟退火算法对路径规划问题进行求解，经过313次迭代后得出充电路径规划的最优方案。

关键词

无线可充电传感器网络，MTSP，0-1整数规划模型，模拟退火算法

Optimization of Multi-MCV Charging Path in Wireless Rechargeable Sensor Networks

Ruiyan Zheng¹, He Zhou¹, Yuxuan Hou², Xingkui Fan^3*

¹College of Management Engineering, Qingdao University of Technology, Qingdao Shandong

²School of Information and Control Engineering, Qingdao University of Technology, Qingdao Shandong

³College of Science, Qingdao University of Technology, Qingdao Shandong

Received: Aug. 3^rd, 2021; accepted: Aug. 25^th, 2021; published: Sep. 7^th, 2021

ABSTRACT

The reasonable planning of charging path is the key to ensure the stability of wireless rechargeable sensor networks. In this paper, this kind of problem is abstracted as MTSP problem, and a charging path planning model with multi-MCV operation is proposed. By estimating the number of possible solutions, the simulated annealing algorithm is used to solve the path planning problem, and the optimal charging path planning scheme is obtained after 313 iterations.

Keywords:Wireless Rechargeable Sensor Network, MTSP, 0-1 Integer Programming Model, Simulated Annealing Algorithm

Copyright © 2021 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

无线传感器网络(WSN)由大量传感器节点和数据中心构成，具备数据收集、处理以及传输三个功能，在日常生活中得到广泛应用。但传感器节点与数据中心之间的距离越长，数据转发任务越多，节点的通信负荷也越高 [1]。因此，一些传感器节点会因为能量耗尽而提前停止工作。从这个角度出发，研究人员提出了不同的延长整个网络寿命的方法。

一般来说，要解决这个问题有三种方法。其中一种方法是节能，通过设计低功耗的路由协议来延长无线传感器网络的生命周期，但这会对网络性能产生不容忽视的影响，而且没有从实质上改变有限的生命周期对传感器稳定高效工作的影响。此外，一些学者致力于转换大自然的能量为无线传感器网络提供能量，例如太阳能 [2] 及热能 [3] 等。但所转换能量的稳定性和可控性成为制约无线传感器网络稳定工作的关键因素。第三种方法中，可移动充电车(Mobile Charging Vehicle, MCV)应用于无线传感器网络组成了无线可充电传感器网络(WRSN)，低成本的可移动充电车能够及时补充能量以满足传感器的需求，成为解决传感器能耗瓶颈问题的又一重要途径。

在无限可充电传感器网络中，按照充电车的工作时间可以将充电方式分为按需充电和周期充电两种。按需充电考虑了传感器网络中能量消耗的不平衡性，每轮只对最需要充电的几个传感器进行充电，一般应用在小规模的只包含单个充电车的传感器网络 [4]。周期性充电 [5] 是指充电车每次充电方案的总时间和充电顺序保持不变，每个节点定期进行能量补充，保证每个节点的能量变化也是周期性的，目前该充电方式应用较广泛。

在无线传感器网络中，每个节点的能量是有限的，并且节点的位置是固定的。为了保证网络的持续运行，需要一辆或几辆移动充电车为传感器节点补充能量。因此，我们将面临一个重要的研究问题：充电车将按照什么顺序工作，从而使充电车的充电效率更高。

2. 问题描述

本文以由 $n\left(n>1\right)$ 个移动充电车和m个传感器节点的无限可充电传感器网络为研究对象，并假定所有的移动充电车初始状态均位于数据中心。四个充电车路途总能耗最小的充电路线最优规划，可以使充电车的充电效率最高，使WRSN的实用性更强。

为方便研究，本文将整个网络的充电流程简化。在无线传感器网络中，传感器节点的能量是有限的，其主要工作是数据传输。在工作过程中，这些有限的能量E₀会逐渐消耗掉，每个节点都有不同的耗能率P_i。原则上，充电车本身的能量远大于节点的初始能量，因此充电车将为节点提供节点所需的能量。下面是一个简单的充电过程示例(如图1)。

图1. 多MCV充电路线规划示意图

3. 数学模型的建立

3.1. 优化目标的确定

可以将传感器网络看作是一个具有n个顶点的加权图G，网络中各边权重以各节点间的距离 $d_{ij}$ 表示。将四个移动充电器看作四个旅行商，传感器网络中的所有传感器以及数据中心看作城市，那么多MCV总充电路线规划即在加权图G中求顶点集V的划分 $V_1,V_2,V_3,V_4$，将G分成4个连通的子图 [6]，每个子图中寻找一条包含数据中心的回路，并达到四条回路的总边权值之和最小。

传感器节点间的距离矩阵 $D_{ij}={\left(d_{ij}\right)}_{n\times n}$ 已知条件下，为表示各段路程的累加，首先通过定义0-1变量来表示各MCV是否从某一传感器到另一传感器：

$x_{ij}^k=\{\begin{array}{l}1,移动充电器b_k从传感器a_i到达传感器a_j\\ 0,否则\end{array}$

$y_i^k=\{\begin{array}{l}1,移动充电器b_k经过传感器a_i\\ 0,否则\end{array}$

则第k个移动充电器经过传感器的路径之和 $z_k={\displaystyle {\sum }_{i=0}^n{\displaystyle {\sum }_{j=0}^n{d}_{ij}{x}_{ij}^k}},k=1,2,3,4$，充电路线规划的目标就是使这4个MCV充电的总路径最小：

$\min Z={\displaystyle \underset{i=1}{\overset{k}{\sum }}{z}_k}$ (1)

3.2. 约束条件分析

MCV从数据中心 $a_0$ 出发，除数据中心外其余传感器仅被某一个MCV访问一次，数据中心是四个MCV的起点和终点，由数据中心必须被访问4次来约束：

${\displaystyle \underset{k=1}{\overset{m}{\sum }}{y}_i^k}=\{\begin{array}{l}m,i=0\\ 1,i=1,2,\cdots ,n\end{array}$ (2)

为了保证每个MCV的充电路线都能形成一个圈，无向图中每个终点传感器只能有一个起点传感器和它相连；每个起点传感器只能有一个终点传感器和它相连：

$\begin{array}{l}{\displaystyle \underset{i=0}{\overset{n}{\sum }}{x}_{ij}^k}=y_j^k,\left(\forall j=0,1,\cdots ,n;k=1,2,\cdots ,m\right)\\ {\displaystyle \underset{j=0}{\overset{n}{\sum }}{x}_{ij}^k}=y_i^k,\left(\forall i=0,1,\cdots ,n;k=1,2,\cdots ,m\right)\end{array}$ (3)

规划过程中，因为三角形两边之和大于第三边，易得四个MCV中只派出一个MCV工作，而剩余MCV在数据中心闲置是充电总路线距离最短的情况(见图2)。为保证每个MCV均正常工作，即每个MCV都必须访问非数据中心外的至少一个节点，可以通过式(2)和式(3)条件相结合达成约束。

图2. 总距离上单MCV优于多MCV示意图

每个传感器集合的子集中都不能产生不与数据中心相连的支路，比如传感器集合 $R=\left\{a_1,a_2,a_3\right\}$ 产生闭路 $\left\{a_1-a_2-a_3-a_4\right\}$，其中并没有与数据中心 $a_0$ 相连，因此 $R=\left\{a_1,a_2,a_3\right\}$ 作为支路被消除 [7]。消除图中其他支路的条件可表示为：

$\begin{array}{l}S=\left\{\left(x_{ij}^k\right)|{\displaystyle \underset{i\in R}{\sum }{\displaystyle \underset{j\in R}{\sum }{x}_{ij}^k}}\le \left|R\right|-1,R\subseteq \left\{a_0,a_1,\cdots ,a_n\right\}\right\}\\ X=\left(x_{ij}^k\right)\in S\end{array}$ (4)

3.3. 多MCV移动充电路径优化模型

综合目标函数和约束条件的讨论，我们得到多MCV移动充电路径规划的0-1规划模型如下：

目标函数： $\min Z={\displaystyle {\sum }_{i=1}^k{z}_k}$

$\text{s}\text{.t}\text{.}\{\begin{array}{l}{z}_k={\displaystyle \underset{i=0}{\overset{n}{\sum }}{\displaystyle \underset{j=0}{\overset{n}{\sum }}{d}_{ij}{x}_{ij}^k}},k=1,2,3,4\\ {\displaystyle \underset{i=0}{\overset{n}{\sum }}{x}_{ij}^k}=y_j^k,\left(\forall j=0,1,\cdots ,n;k=1,2,\cdots ,m\right)\\ {\displaystyle \underset{j=0}{\overset{n}{\sum }}{x}_{ij}^k}=y_i^k,\left(\forall i=0,1,\cdots ,n;k=1,2,\cdots ,m\right)\\ {\displaystyle \underset{k=1}{\overset{m}{\sum }}{y}_i^k}=\{\begin{array}{l}m,i=0\\ 1,i=1,2,\cdots ,n\end{array}\\ S=\left\{\left(x_{ij}^k\right)|{\displaystyle \underset{i\in R}{\sum }{\displaystyle \underset{j\in R}{\sum }{x}_{ij}^k}}\le \left|R\right|-1,R\subseteq \left\{a_0,a_1,\cdots ,a_n\right\}\right\}\\ X=\left(x_{ij}^k\right)\in S\end{array}$ (5)

4. 算例分析

数据来源于2020年深圳杯B题附件一和附件二，其中，附件一给出了数据中心和传感器的经纬度坐标，附件二给出数据中心和传感器经纬度坐标外，还给出了每个传感器的能量消耗速率。为确定传感器网络的边权值，首先将数据中传感器网络节点的经纬度坐标转换成三维坐标，得到任意两个传感器节点及数据中心与各传感器之间的直线距离 [8]。

附件一中给出的各点经纬度坐标用有序数对(u,v)表示，u为经度，v为纬度。以地心O为坐标原点，赤道平面为xOy平面，0度经线圈所在的平面为xOz平面建立三维直角坐标系 [8]，则数据中心和各传感器的三维坐标为：

$\{\begin{array}{l}x=R\cos u\cos v\\ y=R\sin u\cos v\\ z=R\sin v\end{array}$ (6)

其中，地球半径R = 6370 km。

据解析几何相关知识，传感器网络中任意两节点 $A\left(u_A,v_B\right)$，$B\left(u_B,v_B\right)$ 间的实际距离为：

$d=R\arccos \left[\cos \left(u_A-u_B\right)\cos v_A\cos v_B+\sin v_A\sin v_B\right]$

充电路线的起点和终点都是数据中心，为了便于表示，不妨将数据中心看作0号传感器，将数据中心与所有的传感器记为一个节点集合 $A\left\{a_0,a_1,\cdots ,a_{n-1}\right\}$。 $d_{ij}$ 是两个传感器i与j之间的距离，据求得的节点间距离，得到数据中心与传感器之间、各个传感器之间的距离矩阵D：

$D={\left(d_{ij}\right)}_{n\times n}={\left[\begin{array}{cccc}10000& 4.883& \cdots & 63.341\\ 4.883& 10000& \cdots & \\ ⋮& ⋮& \ddots & ⋮\\ 63.341& & \cdots & 10000\end{array}\right]}_{30\times 30}$

在掌握实例数据后，根据前文建立的数学模型，考虑到多MCV充电路径方案数量大，一般算法收敛速度慢，因此通过MATLAB软件利用模拟退火算法求解多MCV的最短充电路径，算法流程图如图(如图3)。

由图4可知，经过313次迭代得到最大耗电量的稳定值，即得到最优解，计算出MCV最短的充电路线总路程为12.756 km，各MCV的传感器访问路径如下(如图5)。

图3. 模拟退火算法流程图

图4. 模拟退火算法迭代结果

图5. 多MCV充电路线规划结果

5. 结论

本文研究了无线可充电传感器网络中多充电车周期充电最优路径的优化问题，为使充电车路途能耗最低，建立了0-1整数规划模型，利用启发式算法中的模拟退火算法进行求解，经过313次迭代得到最优解。从实际应用角度来说，本文所提出模型对MRSN的充电问题具有重要的参考价值，对增强传感器网络实用性大有裨益，本文对实际问题向MTSP问题的转换为其他实际问题求解提供了思路。

基金项目

2020年山东省大学生创新训练项目(项目编号S202010429197)；2020年山东省本科教学改革研究重点课题(Z2020045)；2021年全国大学生创新训练项目(项目编号202110429213)资助。

文章引用

郑睿彦,周 何,侯宇轩,范兴奎. 无线可充电传感器网络中多MCV充电路径优化
Optimization of Multi-MCV Charging Path in Wireless Rechargeable Sensor Networks[J]. 应用数学进展, 2021, 10(09): 2960-2966. https://doi.org/10.12677/AAM.2021.109310

参考文献