刘巧
华北电力大学（保定） 河北省保定市 071000
摘要
本文研究为了使WRSN系统稳定工作，使移动充电器为题目给出的几个传感器充电的最小能耗，并计算出在此路径下为使系统正常运行而需要的最小电量。并以此为基础研究有两个移动充电器时的情况。
针对问题一规划出使移动充电器能耗最小的路径，通过分析我们得知，移动充电器的能耗取决于它所经过的路程于是问题一转化为规划最短路径问题，我们以此构建出最短路径规划模型，并通过启发式算法：模拟退火算法、蚁群算法求出最短路程，利用Matalb对两种启发式算法进行运算所得最短路径分别为模拟退火算法所算得9413.2m，蚁群算法所得为9605m。因为我们求移动充电车耗电最少，而移动充电车的耗电量取决于车子所经过路程所以所经过最短路程为9413.2m，路径为：数据中心-2-1-20-19-26-25-18-17-7-6-14-11-15-9-8-12-
27-16-10-13-5-4-3-22-28-24-23-21-29-17-数据中心。
对于问题二需要求出使WRSN系统正常运行的传感器的最低电量，我们通过分析得知只需移动充电器到达这个传感器时此传感器刚好达到阈值即可求出最小值。我们构建了一个使传感器电量最小的目标规划模型，并通过MATLAB求解得出最低电量为69.875mA。因为题目中未给出移动充电器的速度、充电速率、传感器电量阈值，所以我们为了使结果更有说服力，我们对移动充电器的速度、充电速率、传感器电量阈值进行了灵敏度分析，说明我们的结果的可信度。
一、模型的建立与求解
1.1对问题一的求解：
1.建模思路：
对问题的分析，我们发现消耗的能量取决于移动充电器所经过的路程，类似于TSP问题。经典的TSP可以描述为：一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要经过所有城市后，回到出发地。应如何选择行进路线，以使总的行程最短。从图论的角度来看，该问题实质是在一个带权完全无向图中，找一个权值最小的Hamilton回路。由于该问题的可行解是所有顶点的全排列，随着顶点数的增加，会产生组合爆炸，它是一个NP完全问题。由于其在交通运输、电路板线路设计以及物流配送等领域内有着广泛的应用，国内外学者对其进行了大量的研究。早期的研究者使用精确算法求解该问题，常用的方法包括：分枝定界法、线性规划法、动态规划法等。但是，随着问题规模的增大精确算法将变得无能为力，因此，在后来的研究中，国内外学者重点使用近似算法或启发式算法，主要有 遗传算法、模拟退火法、蚁群算法、禁忌搜索算法、贪婪算法和神经网络等算法。我们则先计算出各个传感器之间的欧式距离然后建立路程最短的目标规划模型最后运用模拟退火算法[1]和蚁群算法[2]分别进行求解。
2.模型建立：
计算出各个传感器之间的距离，我们在假设一中已经给出以平面距离进行计算，这里选择欧式距离进行计算，计算公式如下：
(1)
接着我们建立最短路程的目标规划模型：
(2)
3.求解算法：
3.1模拟退火算法
本题主要采用模拟退火算法(Simulated Annealing, SA)解决 TSP，SA是一种通用概率算法，它是基于 Monte-Carlo 迭代求解策略的一种随机寻优算法，结 合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解 能概率性地跳出并最终趋于全局最优[3]。
在模拟退火函数中，E代表状态能量温度T从状态i进入状态j时就遵循如下规律：
（1）如果,则接受该状态被转换
（2）如果，则状态转换以如下概率被接受：，为波尔茨曼常数
所以我们以指数函数作为我们新解更迭的概率的概率函数。
在本题中我们新解更迭频率随着温度由高到低，进行最优解的更替，并在我们设立的更迭次数限制下，寻找此温度退火下的最优值。
其计算步骤如图1所示：
.png)
所经过路线为：数据中心-2-1-20-19-26-25-18-17-7-6-14-11-15-9-8-12
-27-16-10-13-5-4-3-22-28-24-23-21-29-17-数据中心，这条最短路径为9413.2m。
3.2 蚁群算法：
蚁群算法是一种用来寻找优化路径的概率型算法，其基本思想来源于自然界蚂蚁觅食的最短路径原理。蚁群算法是由M.Dorigo等学者提出的分布式智能仿生算法[4]。该算法模拟了蚂蚁合作觅食行为的性质。它具有正反馈、高稳健性和并行性的优点，但是该算法存在搜索空间大、局部最优、搜索效率低、计算量大等问题[5,6]。
蚁群算法中信息素代表着新解更迭的依据，路径长的终点处信息素挥发后量较小，新解接受概率小，而信息素多的，迭代次数多的路径上的新解就更容易被接受。我们迭代的过程也要依靠合理的信息素挥发，并且新解的产生也要依靠启发函数。启发函数要根据信息启发函数和期望启发函数，两者决定新解的接纳程度。合理的设定信息素、挥发函数和启发函数，才能调整不同问题不同方式，避免局部最优解的问题。
其计算步骤如图2所示：
.png)
所经过路线为：数据中心-17-29-21-4-22-23-24-28-3-5-13-10-16-27-15
-12-8-9-7-6-11-14-18-25-26-19-20-1-2-数据中心。这条最短路径为9605m。
4.模型的分析与检验
利用Matalb对两种启发式算法进行运算所得最短路径分别为模拟退火算法所算得9413.2m，蚁群算法所得为9605m。因为我们求移动充电车耗电最少，而移动充电车的耗电量取决于车子所经过路程所以所经过最短路程为9413.2m，路径为：数据中心-2-1-20-19-26-25-18-17-7-6-14-11-15-9-8-12-27-16-10-13-5
-4-3-22-28-24-23-21-29-17-数据中心。由于模型对比中，模拟退火模型求解距离更短，我们认为模拟退火模型的拟合效果更好。
1.2对问题二的求解：
1.建模思路：
在问题二中需要使系统持续正常运行，因为移动充电器在移动需要时间，在此段时间内传感器在消耗电量并且每给一个传感器充电都会消耗一定时间，所以我们认为不论对于哪一个传感器而言，它前面的传感器充电总时间与移动充电器所走的路程总时间所消耗的时间和小于此传感器将能量消耗到阈值的时间小此系统一直正常运行，于是我们建立关于时间和耗电量的规划模型，求解出的最小值。
2.模型建立：
我们需要在第一问的基础上进行建模，我们先将路径上的传感器重新编号，我们为了方便计算，将终点设为数据中心，再将路径分为被每两个传感器之间的距离，这种情况下，我们可以得到30段以第一问路线为基础的路程，30个以数据中心为终点的节点。
首先求解最大电容量时，我们以时间约束为我们线性约束的条件。于是我们对充电器而言，将充电器时间路段分为在路程上行进时间和为传感器充电的充电时间，对于传感器而言，我们需要求解其耗电至阈值的时间。
其次，根据要求和假设，我们研究这个模型可持续情况下，系统是能够达到动态平衡的，所以我们以动态平衡其中的一次循环来进行研究分析。
2.1数据预处理
由于我们题目中速度单位是以米每秒为单位的，所以我们的消耗功率的单位应当转化为mA/s，所以我们在原数据处理上完成单位的转化，如表1所示，并且以V（i）为第i个节点的消耗功率。
.png)
然而充电时间模型和消耗时间模型均与求解得电量有关，所以在matlab的linprog函数中直接代入进行求解。
3.3求解结果
Matlab中求得Q的最小值为69.875mA，则在我们模拟数据后的模型中，当29个传感器的最小的满电容量至少是69.875mA时，才能保证整个系统能够不间断的工作。
二、模型的评价
1.模型的优点：
第一问中采取了两种较为先进的智能算法，具有搜索能力强的特点。在第一问中通过蚁群算法和模拟退火算法得出最优路径，并将两者比较，大大降低了误差。
第二问中运用线性规划模型求解，准确地建立在问题的基础之上，较为清晰地阐述了模型的建立，同时将时间分成充电器在路程上消耗的时间，给节点充电时间等部分，一定程度降低模型的复杂度，更容易理解。
2.模型的缺点：
第二问中对参数的设置有局限性，本模型只考虑到了充电速率远大于消耗速率的情况。
三、参考文献
[1]苗卉,杨韬. 旅行商问题(TSP)的改进模拟退火算法[J].微计算机信息,2007,23(11-3),241-243.
[2] 段海滨.蚁群算法原理及其应用[M].北京:科学出版社,2006:45-96.
[3]杨理云，用模拟退火算法求解旅行商问题[J]，微电子学与计算机, 24(5):193-196，2007。