无线可充电传感器网络充电路线规划摘要无线传感器网络中包括若干传感器以及一个数据中心，这些传感器的电池均需要能量来维持正常的工作，基于此一方面我们需要设计单个移动充电器从数据中心出发的合理网络充电路线，另一方面传感器工作时均会耗电，需要得到要保证各传感器正常工作的电池的最低容量，并由此拓展到多个移动充电器的问题。

针对问题一，要使得能耗最小化，就要保证移动充电器行走的路程最小，所以路线图可看成网络图，利用地球半径和各传感器的经纬度计算可以得出各个点之间的距离，问题转化为在给定的加权网络图中寻找从数据中心开始将网络图中所有顶点仅遍历一遍再回到数据中心使得路程最短的问题，即TSP问题，结合模拟退火算法和遗传算法，我们可以得到最优的路线方案见图二。

针对问题二，系统正常运行需要保证移动充电器跑完一圈的过程后各传感器一直不低于最低电池容量，可以将此作为约束条件，若要求得每一个满足题设条件传感器的电池容量最小值，可以等价为求传感器总电池容量的最小值，这样就将多目标问题转化为了单目标问题，经简化计算进一步转化为线性规划问题，合理设置充电速率r，移动速度v，电池容量最低值f,通过求解我们得到各传感器的最小电池容量见图四；在此基础上我们考虑到巡视间隔为1天，保证相邻两次巡视之间传感器的电池电量仍然满足要求，得到电池容量见图六。

针对问题三，规划同时派出4个移动充电器进行充电的路线可以联系多售货员的旅行商问题，以数据中心为原点，进行网络图分区，然后进一步分组求得最短巡视路径，通过引入均衡度分析不同划分方案的合理性，保证总路线最短与均衡度最好，因而转化为多目标优化问题，基于第一问的遗传算法我们得到最优的路线方案见图九，结合第二问进一步得到各电池最低容量见图十。

【关键词】模拟退火遗传算法 TSP 线性规划分区均衡度1.问题重述1.1问题背景随着物联网的快速发展，无线传感器网络WSN在生活中的应用也越来越广泛。

无线传感器网络中包括若干传感器以及一个数据中心。

传感器从环境中收集信息后每隔一段时间将收集到的信息发送到数据中心。

数据中心对数据进行分析并回传控制信息。

影响WSN生命周期最重要的一个因素是能量。

提供能量的方式之一是电池供电，利用移动充电器定期为传感器的电池补充能量，这种方式供电的网络也被称为无线可充电传感器网络WRSN。

1.2求解问题在WRSN系统中，传感器从环境中收集信息并将收集到的信息传递给数据中心。

当一个传感器的电量低于一个阈值时便无法进行正常的信息采集工作，为了让WRSN正常运转，移动充电器需要定期为传感器进行充电以避免其电量低于阈值。

为了减小移动充电器在路上的能量消耗，需要合理地规划移动充电器的充电路线。

请考虑以下问题：问题一：根据每个节点的经纬度，考虑当只派出一个移动充电器时，如何规划移动充电路线才能最小化移动充电器在路上的能量消耗。

问题二：知道每个节点的经纬度、能量消耗速率，假设传感器的电量只有在高于f(mA)时才能正常工作，移动充电器的移动速度为v(m/s)、移动充电器的充电速率为r（mA/s），在只派出一个移动充电器的情况下，若采用问题一规划出来的充电路线，每个传感器的电池的容量应至少是多大才能保证整个系统一直正常运行？问题三：知道每个节点的经纬度、能量消耗速率，假设传感器的电量只有在高于f(mA)时才能正常工作，移动充电器的移动速度为v(m/s)、移动充电器的充电速率为r（mA/s），但为了提高充电效率，同时派出4个移动充电器进行充电，在这种情况下应该如何规划移动充电器的充电路线以最小化所有移动充电器在路上的总的能量消耗？每个传感器的电池的容量应至少是多大才能保证整个系统一直正常运行？2、问题分析2.1 问题一分析：问题一属于典型的旅行商问题，该问题是在寻求一个充电器由起点出发，通过所有给定的传感器位置点之后，最后再回到原点的最小路径。

问题的求解有多种方式，我们在这里采用模拟退火算法和遗传算法来求解此问题。

附件一给出了29个传感器以及数据中心的经纬度，先将经纬度转换为弧度，再利用地球半径计算可以得出各个点之间的距离，从而可以求得这些点的距离矩阵，根据以上两种不同的求解方式会得出不同的最短路径（即最优路径），再对结果进行分析比较，得到最佳路线规划方案。

2.2 问题二分析：若将每一个传感器的电池容量都视作一个目标，则此问题属于多目标优化问题，在此题中，若要求得每一个满足题设条件传感器的电池容量最小值，可以等价为求传感器总电池容量的最小值，这样就将多目标问题转化为了单目标问题，根据题意，我们可以合理假设移动充电器的巡逻速率和频率，从而得到约束条件：在移动充电器巡逻一个周期（即绕所有点走一圈）内，每个传感器的电池容量最低不能低于f(mA),利用这一条件，我们可以建立不等式约束，从而进一步将问题转化为线性规划问题，利用线性规划的求解方式解得每一传感器满足题设条件的电池容量最小值。

2.3 问题三分析：问题三属于多个售货员的最佳旅行售货员问题，题目要求同时派出4个移动充电器进行充电，在这种情况下规划移动充电器的充电路线，使得移动充电器在路上总的能量消耗最小。

因此本文首先考虑以数据中心为原点，进行网络图分区，然后进一步分组利用遗传算法求得最短巡视路径，在第二问的解法基础上计算每个分区内传感器满足题设条件的电池容量最小值。

在分区时，我们引入均衡度的概念，它是最大路程和最小路程的差值与最大路程的比值，比值越小，表示分区路线均衡度越好（即路线长度差距较小）。

3、模型假设1.假设移动充电器匀速行进；2.假设题目所给数据真实可靠；3.假设地球是一个标准的球体，半径是6371km；4.假设移动充电器在传感器处的时间消耗仅用于充电；5.假设移动充电器的电池电量足够大，且不需要在数据中心进行充电；4、定义与符号说明5、模型的建立与求解数据分析基于对附录1所给数据的初步分析，可以做出数据中心与29个传感器的散点图，本文下一步将利用Matlab 求出数据中心到各点的最短距离，即网络图的最短路径树并作图。

(求解程序参见附录)图一 传感器分布情况5.1.1 问题一模型的建立转化为TSP 问题后，我们需要得到的是由数据中心（起点）经所有传感器的一条最短环路。

给数据中心编号为1，传感器依次编号为2,3...30，最后数据中心再重复编号为31。

在此基础上我们可以建立距离矩阵31*31ij ）（d D =，其中ij d 表示i ，j 两点间的距离。

则问题是由1出发，走过中间所有的点，到达31的一个最短路径。

我们的解空间是所有固定起点与终点的循环排列组合。

31}{2,3...30}...1|...{313021311===ππππππ的循环排列，）为，，，（），，（S 则我们可以建立如下数学模型：∑=+=31131211),...,,(min i i i d f πππππ （1）..t s 01≥+i i d ππ 30...,2,1=i （2） }31...,2,1{i ∈π 31...,2,1=i （3） 对于此类型的模型，我们通常可以使用模拟退火或者遗传算法来进行求解，多次退火（遗传）后得到最优的一组解。

5.1.2 问题一模型的求解模拟退火算法的求解1.模拟退火算法简介模拟退火算法得益于材料统计力学的研究成果。

统计力学表明材料中粒子的不同结构对应于粒子的不同能量水平。

在高温条件下，粒子的能量较高，可以自由移动和重新排列。

在低温条件下，粒子的能量较低。

如果从高温开始，非常缓慢的降温（退火过程），粒子就可以在每个温度下达到热平衡。

当系统完全冷却时，最终形成处于低能状态的晶体。

而将这种过程用数学方式来描述及展现，就是我们的模拟退火算法及其计算过程。

2.模拟退火算法求解过程（1）解空间。

在模型建立中我们已经说明了解空间S ，首先可以选取初始解为（1,2...31），再利用蒙特卡洛法求得一个较好的初始解。

（2）目标函数。

目标函数为走过所有的传感器的路径长度。

∑=+=31131211),...,,(min i i i d f πππππ （4） （3）新解的产生。

利用2变换法任选排列中两序号v u ,，交换其位置变为逆序，得到新路径。

（4）代价函数差。

)()(1111+-+-+-+=∆v v u u v u v u d d d d f ππππππππ （5）（5）接受准则。

⎩⎨⎧∆=,/-exp 1）（，T f P 00≥∆<∆f f （6） 如果0<∆f ，则接受新的路径，否则以概率)/(exp T f ∆-接受新的路径。

（6）降温。

利用选定的降温系数α进行降温，取新的温度T 为T α，本文选用999.0=α。

（7）结束条件。

用选定的终止温度3010-=e ，判断退火过程是否结束。

3.模拟退火算法求解结果图二 模拟退火计算结果由图像容易看出求得的最优移动充电器巡视路径为0-17-20-19-18-25-26-29-21-23-24-28-22-4-3-5-10-8-12-13-16-27-15-14-11-6-7-9-1-2-0，最短路径长度经计算为11.5064千米。

遗传算法求解：求解遗传算法的参数设定如下：交叉概率为1能保证种群的充分进化，一般而言，变异发生的可能性较小，本文取0.1。

1.遗传算法编码策略：用遗传算法解决TSP ，一个旅程很自然的表示为n 个传感器位置的排列，但基于二进制编码的交叉和变异操作不能适用，本文采用十进制编码，用随机数列3121w w w 作为染色体，其中10≤≤i w （30.,3,2 =i ），01=w ，131=w ；每一个随机序列都和种群中的一个个体相对应，例如，问题中的一个染色体为：[]78.0,69.0,56.0,11.0,87.0,74.0,45.0,82.0,23.0式中：编码位置i 为目标i ，位置i 的随机数表示目标i 在巡回中的顺序。

将这些随机数按升序排列得到如下巡回：5-2-9-4-8-7-3-1-62.遗传算法求解过程：（1）初始种群：利用经典的近似算法——改良圈算法求得一个较好的初始种群。

对于随机产生的初始圈：）（）（302,302,3111111≤<≤<<≤=+-+-v u v v v u u u v u C ππππππππππ ， 交换u 与v 之间的顺序，此时的新路径为：3111111ππππππππ ++--v u u v v u 。

记()()1111+-+-+-+=∆v v u u v u v u d d d d f ππππππππ，若0<∆f ，则以新路径修改旧路经，直到不能修改为止，就得到一个比较好的可行解。

直到产生M 个可行解，并把这M 个可行解转换成染色体编码。

（2）目标函数：目标函数为侦察所有目标的路径长度，适应度函数就取为目标函数。