刘可欣 陈东齐 曹林 邢妮
山东协和学院 山东济南 邮编 250200
摘要：本题要求解决一个移动充电器在充电道路上最小能量消耗问题，建立一个关于路程的数学规划模型，并给出合理规划路线。首先，通过分析可知移动充电器在路上的消耗和路程的长短、路况等有关。其中路程长短可以运用球面距离公式求出每个节点之间距离，运用Excel软件，画出相关节点位置得出移动充电器充电路线的合理选择，以求出一个最短的充电路径；路况情况则是需要实地分析。
关键词：数学规划模型 线性方程组 路径 能量消耗
引言：无线传感网络（WSN）是由多个传感器和一个数据中心通过无线通讯相互连接的一个网络系统，其中传感器负责信息的收集，数据中心负责对数据进行分析并向传感器回传控制信息。现在随着物联网的快速发展，人们对于无线传感器网络的性能要求越来越高，但能量问题是限制传感器发展的一个重要因素，为了解决传感器能量受限问题可采用移动充电器充电。本文研究的目的是探究移动充电器移动方式与传感器电池容量的联系。
一、问题重述
1.1问题背景
无线传感器网络随着物联网的快速展在生活中应用越来越广泛，无线传感器由一个数据中心和若干传感器组成。传感器从环境收集信息后，一段时间就要将收到信息发往数据中心，然后数据中心对数据进行分析并传控信息。
影响无线传感网络（WSN）的生命周期的因素是能量，为了使WSN不断运转，必须从为WSN持续提供能量。为WSN提供方式有两种，一种是能量收集，通过利用风能、太阳能等环境因素汲取能量维持WSN的运作，但这种方式因为外部环境的不确定因素，能量供应不稳定，一旦外部环境不利，WSN能量就无法汲取。另一种方式是电池供电，用移动电源为WSN补充能量，本文要求以电池供电方式求出传感器的充电路线与电池容量。
1.2问题描述
无线可充电传感器网络由三部分组成：一个数据中心DC，若干传感器，一个或多个移动充电器（MC）。数据中心和传感器分布在二维空间中，二维空间中传感器从环境中收集信息传递给数据中心。传感器电量低于一个固定值时便无法进行工作，为了保证系统的正常运转，传感器需要定期充电。移动充电器以固定速度从数据中心出发，移动从电器必须在所有传感器充电之后才能返回数据中心。移动充电器能量消耗主要有以下两方面原因，一是传感器在节点充电的正常能量损耗，二是移动充电器在充电道路上的能量消耗。为了低碳环保、节能，应合理规划充电路线。
1.3问题提出
根据给出每个节点经纬度，思考在只派出一个移动充电器，怎样合理规划移动充电器的充电路线才能使移动充电器在充电过程中能量消耗最小化。
二、问题分析
本题要求分析研究只派出一个移动充电器，寻找最短路线使移动充电器在路上消耗最小，建立路线数学规划模型，并给出合理的规划路线。针对该题，本文属于一个典型的旅行商问题，首先对每个节点经纬度进行分析，对充电器工作流程进行了解，其次本文求出每个传感器间距离，运用数学规划模型进行求解，最后得出相关路线。
三、符号说明
.png)
四、模型假设
1、假设地球是一个标准椭圆。
2、假设传感器充电时耗电量忽略不计。
3、忽略传感器充电前后浪费的时间。
4、移动充电器移动速度是固定的，忽略红绿灯等交通因素影响。
5、忽略传感器的使用寿命。
6、假设移动充电器有足够的电量为每一个传感器充电
7、忽略自然因素对传感器的影响。
五、模型的建立与求解
5.1 数据整理
根据每个节点的经纬度，本文做出关于数据中心与29个传感器的散点图，把数据中心和每个传感器以坐标轴的形式表示。
移动充电器主要能量消耗方式有两种，一种是移动充电器充电时的正常消耗，另一种是移动充电器在充电路上的能量消耗。题目要求规划出一个关于移动充电器在路上最小能量消耗的方案，已知移动充电器在路上能量消耗主要与路程有关，移动充电器充电的路程越长，消耗的能量就越大。要规划移动充电器在充电路线道路上能量消耗最小，即规划移动充电器充电的最短充电路程。
首先，先计算数据中心与传感器、传感器与传感器之间的距离。利用地球半径和各传感器的经纬度可以计算各个节点之间的距离。
每个节点的距离为球面距离，以地心为坐标原点O,建立赤道平面XOY，和0度经度圈平面XOZ,形成一个直角坐标系。则，AB两点的坐标为
.png)
5.2模型求解
本题要求解决移动充电器最短路径问题，并规定移动充电器遍历每个传感器的点，并且最终回到起始点“数据中心”。将数据中心、各传感器分别看作一个点，从数据中心点出发，找到距离数据中心点最近的传感器点，得到移动充电器第一次停留的位置，根据上一步找出的停留位置，可以将寻找最短充电路径问题转换为遍历所有传感器点停留问题。
本题是一个典型的旅行商问题即TSP问题，寻找遍历所有传感器充电的最短路程。TSP问题指的是从一个节点开始遍历其他所有节点并回到初始节点，构成一个哈密顿回路，节点与节点之间距离不同，目标是找到一条回路使得总路程最短，也即就是走最短的路遍历所有节点回到起点。[1]
.png)
根据计算的距离可知，移动充电器最短路程为11484.49米。根据程序和各点坐标，求解移动充电器的行驶路线。
根据程序和图像，得出在只派出一个移动充电器情况下，移动充电器最短消耗路线为起始点。
六、总结
本模型在解决单个移动充电器运行问题中，我们采用lingo软件对每个节点之间距离进行判断，找出最小路径，这个方法避免了像类似与模拟退火法等方法陷入局部最优解的问题。使得我们所求得的路径就是最小路径。在传感器最小容量问题上，考虑到了传感器规格问题，对于规格一致和不一致都进行了探究。
[参考文献]
[1]Mr_厚厚 在Matlab上实现遗传算法解决TSP旅行者问题 https://blog.csdn.net/cordova/article/details/64912680?locationNum=2&fps=1&utm_medium=distribute.pc_relevant_download.none-task-blog-baidujs-3.nonecase&depth_1-utm_source=distribute.pc_relevant_download.none-task-blog-baidujs-3.nonecase 2020.9.1
指导老师：邢妮 山东协和学院