无线传感器网络环境下小车充电路径规划问题的改进模拟退火算法研究

冯思尧，张程潇，柳 毅

（杭州电子科技大学 管理学院，浙江 杭州 310018）

0 引言

伴随着物联网的快速发展，无线传感器网络WSN（Wireless Sensor Network）在生活中的应用也越来越广泛[1]。无线传感器网络包含着若干传感器（Sensors）以及一个数据中心（Data Center），信息通过传感器传送到数据中心。在传感器无法利用自然条件（太阳能）获取能量的情况下，则需要安排移动充电设备给传感器电池供电，这时网络称为无线可充电传感器网络 （Wireless Rechargeable Sensor Network，WRSN）。因此，为维持WRSN正常工作，合理规划移动充电设备的路径为传感器提供能量成为重要的研究问题。

梁晓辉等（2020）对常见的路径规划求解算法进行综述并从不同方面比较各种算法的优劣[2]。姚明海等（2013）将模拟退火算法和遗传算法融合求解TSP（Traveling Salesman Problem）问题，利用遗传算法的全局搜索能力弥补了模拟退火算法容易陷入局部最优的问题[3]。谢艳丽等（2014）根据交叉算子和变异算子的特点，针对交叉算子引入拉普拉斯算子进行改进，并结合黄金分割法针对变异算子进行优化，提高收敛速度，同时避免过早陷入局部最优解[4]。于莹莹等（2014）在传统遗传算法中引入贪婪算法进行种群初始化，采用精英个体保留的选择方法调节个体适应，使其在种群较小的时候具有较强的寻优能力[5]。孙文彬等（2016）改进遗传算法初始解的构造方法，引入并行交叉和局部优化策略，明显提升了大规模TSP问题的求解效率[6]。徐练淞等（2017）在蚁群算法的基础上针对TSP问题提出了一种新型的改进蚁群算法，即变参数选择城市策略，并且在交叉策略中选择PMX（Partially Matched Crossover）交叉策略，实验结果表明与基本蚁群算法和遗传算法相比，该方法能够较快找到最优解，求解质量也较好[7]。何庆等（2018）根据旧种群和新种群每个对应个体的进化程度提出一种改进自适应的Metropolis准则，使IGSAA（Improved Genetic Simulated Annealing Algorithm）算法能够有效地避免陷入局部最优，但其对参数的设置具有较大的依赖[8]。包强（2021）引入并行计算思想，先用遗传算法获得较优的初始解，再通过模拟退火算法进行求解，提高了计算速度以及稳定性[9]。许焕等（2021）针对小车充电路径规划问题，使用变步长优化算法和模拟退火算法组合求解，并由此推广到了n个小车及其对应的电池容量[10]。

本文在研究无线可充电传感器网络中充电小车的路径规划问题时，将其视为一个旅行商路径优化问题（Traveling Salesman Problem，TSP）进行求解，从图论的角度建立旅行商问题的0-1规划数学模型，针对旅行商优化问题中模拟退火算法（Simulated Annealing，SA）收敛速度慢的问题提出一种基于动态概率的改进模拟退火算法，使模拟退火算法部分的温度控制变得更具有自适应性，利于该算法实现通过充电站寻找到从源节点到目标节点的最优路线。

1 单车充电的路径规划数学模型

以2020年“深圳杯”数学建模挑战赛C题为例，从图论的角度考虑，将充电网络模型描述为由n个节点构成的一个无向带权图，记做G=（V，E），V表示移动充电器以及传感器的点集，V={0，1，2，…，29}，其中0表示数据中心。E={（i，j）|i，j∈v，i≠j}是n（n-1）/2条边构成的集合，移动充电器从数据中心0出发，依次经过29个传感器进行充电，完成后再次返回数据中心。此问题即求在图G中找到由起点出发的一条经过所有点再回到起点的最短路径，建立以最短路径长度为目标函数的0-1规划模型：

其中，xij表示连接节点i和j边，当取值为1时，此条边在最短路径上；当取值为0时，表示不在最短路径上。dij为边xij的权重大小，即是节点i和节点j根据经纬度求解两点球面距离半正矢公式（Haversine公式）计算得到的两点间欧氏直线距离。约束式表示任意一个节点都只有一个出边和入边，并保证没有任何子回路解产生，即所产生的路径是包括所有节点的单一哈密顿回路。

2 求解单车充电路径规划的改进模拟退火算法

2.1 标准的模拟退火算法

传统的模拟退火算法（SA）通过给当前算法提供一个初始值作为当前解，这个解包含的部分元素通过变换产生大量新解，SA算法选择其中的最优解作为当前解。SA算法具体步骤[3]及流程如图1所示。

图1 模拟退火算法流程图Figure 1 Flowchart of the simulated annealing algorithm

步骤1：选择初始路径S1，确定初始温度T1，设置当前路径Si=S1，当前温度T=Tr，确定每个迭代次数对应的链长L；

步骤2：从Si的邻域中随机选择Sj，计算ΔS=Sj-Si，判断ΔS是否小于等于0，是则令Si=Sj，否则进行第3步；

步骤3：计算Sj的接受概率＞random（0，1），即判断接受概率是否大于（0，1）区间上的随机数，若大于则确定Sj为新的当前路径，否则保留原路径Si；

步骤4：如果满足在若干个Metropolis链中新解Sj都没有被接受时终止算法，或设定结束温度，否则按衰减函数衰减T后回到步骤2。

2.2 动态概率

当M0＞M1时，当前解M0与新解M1越接近，需要考虑接受新解的概率P，概率P越大，我们更加倾向于接受M1。因为P越大意味着在解空间搜索范围更广，为了使得搜索工作更加高效，前期搜索范围广，后期更加倾向于局部搜索。定义初始温度T0=1000，温度下降后Tt（t为迭代次数）为：

基于此，构造出概率关于温度和目标值差的关系表达式：

2.3 基于动态概率的改进模拟退火算法

本文在传统模拟退火算法的基础上提出基于动态概率的改进模拟退火算法。首先，通过蒙特卡洛模拟算法随机生成多个初始值，并选择其中的最优解作为当前解；其次，同时采用交换法、移位法、倒序法三种方法来产生新解（算法中每种方法采用的概率相同，均为1/3，如图2所示），根据每次产生的新解对应的目标函数M的值计算出动态概率P，并在此基础上判断对该解是否接受；最后，在迭代次数终止后，输出当前最优解作为结果。基于动态概率的改进模拟退火算法如表1所示。

表1 基于动态概率的改进模拟退火算法Table 1 An improved simulated annealing algorithm based on dynamic probability

图2 交换法、移位法、倒序法求解过程图Figure 2 Solution diagram of exchange method，shift method and reverse order method

3 仿真实验与数据分析

3.1 实验数据预处理

本文研究的问题引自2020年“深圳杯”数学建模挑战赛C题[11]，仿真实验中共给出30个节点（包含基站数据中心），并在给出每个节点经纬度且只派出一个移动充电器的前提下规划出最优充电路线。如图3所示为WSN的网络数据中心及传感器的经纬度位置信息图。在一个充电周期内，使得移动充电器在路程上的能量消耗最小，其本质为一个TSP问题，因此我们采用了TSP问题下的最短哈密顿回路，将一个充电周期内最少能量消耗问题转换为求解充电回路最短问题。基于此，建立以最短路径长度为目标函数的0-1规划模型，通过贪婪算法对模型进行求解，同时使用基于动态概率的改进模拟退火算法求解模型，并将得到的结果进行对比以验证算法的可行性。

图3 WSN网络的数据中心及传感器的经纬度位置信息图Figure 3 The latitude and longitude location information map of the data center and sensors in the WSN network

3.2 实验过程

利用贪婪算法求解移动充电器充电的最短路径，首先计算各个传感器与数据中心的距离，以当前移动充电器所在位置为基础做出路径最短的最优选择，选取每一次移动的局部最优解即每一次移动的最短路径，通过一系列局部最优解的选择，累加得到最终路径的规划路线。通过上述贪婪算法，得到的最优路径为：（V0表示数据中心）V0-V2-V1-V9-V7-V6-V11-V14-V15-V12-V8-V10-V5-V3-V4-V22-V23-V21-V17-V20-V19-V18-V25-V26-V29-V24-V28-V13-V16-V27-V0；对应的最短路径长度为：13.817km。如图4所示为基于路径最短原则的贪婪算法最优路径规划图。

图4 基于路径最短原则的贪婪算法的最优路径规划图Figure 4 The optimal path planning diagram of the greedy algorithm based on the path minimum principle

基于动态概率的改进模拟退火算法求解模型得到的最优路径为：（V0表示数据中心）V0-V2-V1-V9-V7-V6-V14-V11-V8-V12-V15-V27-V16-V13-V10-V5-V3-V4-V22-V28-V24-V23-V21-V29-V26-V25-V18-V19-V20-V17-V0；本实验用Python语言编程求解[12]，获得单充车充电路线总行程对应的最短路径长度为：11.485km。如图5所示为基于动态概率的改进模拟退火算法的近似最优规划路径。

图5 基于动态概率的改进模拟退火算法的近似最优规划路径Figure 5 Approximate optimal planning path of improved simulated annealing algorithm based on dynamic probability

3.3 实验结果分析

对于一个可移动充电器充电网络路径规划模型，采用基于最短路径的贪婪算法与改进的模拟退火算法进行求解，得到两种移动充电器的充电路径对比结果如表2所示。基于动态概率的改进模拟退火算法迭代过程如图6所示。

表2 贪婪算法与改进的模拟退火算法的充电路径优化结果对比Table 2 Comparison of charging path optimization results between greedy algorithm and improved simulated annealing algorithm

通过图6可以看出：基于动态概率的改进模拟退火算法在迭代50次之前，能够快速下降使得规划路径长度快速缩短；在迭代50次之后，路径长度曲线下降减缓并在300次之前达到收敛，因此该算法在大于50次的迭代次数下均能够获得较好的结果。对比文献[10]的优化结果，本文提出的改进算法获得的最优路径为11.485km，且在迭代300次后算法进入收敛趋势。对相同数据，两种算法所得的最优结果相似，但本算法的迭代次数与运行时间均得到了较大的优化。

4 结语

本文将无线传感器网络中单车充电路径规划问题抽象为NP-hard经典旅行商问题（TSP），建立数学模型，并提出基于动态概率的改进模拟退火算法。改进算法通过动态概率和交换法、移位法、倒序法调节模拟退火算法的参数来优化局部寻优能力和全局寻优能力。仿真实验结果表明，与路径最短的贪婪算法和传统模拟退火算法求解结果相比，本文的改进模拟退火算法在求解无线传感器网络中单车充电路径规划问题时具有收敛精度高、全局寻优能力强的优点。