基于图论对无线充电传感器网络充电路线规划的研究

基于图论对无线充电传感器网络充电路线规划的研究

刘巧

华北电力大学（保定） 河北省保定市 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所示：

图1：模拟退火算法计算流程

模拟退火算法求解：我们查阅资料，选择了合适的退火方法和参数^[7]，我们设置 =1000， =500，温度衰减系数为0.95,每个温度下默认迭代200次，结果如图3所示：

图3：模拟退火算法所求最短路径

所经过路线为：数据中心-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所示：

图2：蚁群算法计算流程

蚁群算法：我们设置m=500， =1， =5， =0.2， =500，a=10，计算所得

结果如图4所示：

图4：蚁群算法所求最短路径

所经过路线为：数据中心-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个节点的消耗功率。

表1：消耗功率

2.2路程时间模型

根据我们设定的路段，第 段路途上需要耗费的时间为：

(3)

其中 ,表示两节点间距离。

那么对于第 个传感器而言，它等到移动充电器到达时刻之前，充电器在路段上的行进时间为：

(4)

由此可见，移动充电为所有传感器充一次电回到数据中心所需的总时间的为 。

2.3充电时间模型

移动充电车充电路径上共有30个节点，对第i个传感器来说，以充满电为要求，则可能造成时间上的浪费，我们只需保证下次循环到来前，此节点不会达到阈值f，所以我们并不是一定要充满电，我们只需充至我们29个传感器的最大电容量的最小值就可以，我们以Q来代替此值第 个传感器充满电所需的时间为：

(5)

其中 为最大电容量，并且由于第30个节点为数据中心，所以其值为0。所以前 个传感器充电所需的累计总充电时间为：

(6)

其中 。

2.4耗电时间模型

我们从移动充电器从数据中心出发开始计时，由于我们探讨的是动态平衡状态下的模型，所以在这次循环中，每个传感器不能以满电情况处理，要计算出发时第i个传感器剩下的电量，然后再进行消耗时间的运算

则根据我们的模型，每个节点的耗电时间应当满足：

(7)

其中 为第i个传感器电量消耗的速度,单位为mA/s， 为电量阈值。

2.5目标规划模型

对于第i个传感器能够持续工作的情况而言，充电器充电之前自身的电量不能被耗至阈值，即有如下要求：

（8）

于是我们建立了合理的线性约束，可以建立如下规划模型：

(9)

3.模型求解

3.1数据的模拟

我们在进行求解时，对一些未知量进行补充以检验模型的可靠性：

补充的数据如表3：

表3：补充数据

3.2对时间变量的求解

根据我们的速度可以得到相应的行进时间模型数据，结果如表2：

表2：距离时间

然而充电时间模型和消耗时间模型均与求解得电量有关，所以在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。

9