无线可充电传感器网络中的充电路径优化

王 茜，崔志华，王丽芳

(太原科技大学 计算机科学与技术学院，太原 030024)

1 引 言

目前，由传感器、微处理器和无线通信接口组成的传感器网络已经应用在医疗[1]、农业[2]和工业[3]等众多领域.由电池[4]供电的传感器通常分布在作战区这样的危险区域，传感器节点不仅承担着监测数据的任务，还需要接收、处理和发送数据等一系列工作.经过一定周期的工作后，传感器消耗了大量的能量，需要及时补充能量.所以，传感器的能量问题成为研究的热点.解决节点的能量问题分为3大类：低功耗路由协议[5，6]、能量收集[7]和无线充电[8].低功耗路由协议的设计，虽然可以降低节点的能耗，但随着时间的推移，节点会因为能量耗尽而停止工作，从而影响无线传感网络的正常工作.另外可以通过能量收集的方式补充能量，然而从环境中获取的能量是很难预测的，而且很不稳定.例如，在获取太阳能的过程中通常会受到天气的影响，这对于传感器的正常运行来说是低效的.无线充电则是第3种新颖的技术，就是将无线充电技术和移动充电设备引入到传感器网络中，形成无线可充电传感器网络(WRSNs)[9].由于传感器节点在网络区域内分布较为广泛，需要使用能够充电的设备移动到节点处进行能量的补充.在大多数场景中，通常利用携带大容量电池的移动充电车辆为传感器补充能量.在移动和充电的过程中，面临的充电问题和设计的充电方案随之产生.

根据不同的充电需求，充电场景的设计也是不同的.在小规模传感器网络中，对于为数不多的充电请求，设计一个充电小车即可满足需求.但对于大规模传感器网络来说，由于充电小车的自身能量有限，一个充电小车短时间内不足以响应大量的充电请求，此时需要设计多个充电小车的网络.为了及时为传感器节点补充能量，解决传感器网络的经典能量问题，研究人员设计了多样化的可充电传感器网络，并且关于充电小车的研究正在不断深入根据充电小车的个数，可分为单充电小车的充电设计和多充电小车的充电设计.为了有效利用无线充电技术来延长网络寿命，Peng等人[10]设计了基于一个充电小车的无线可充电传感器网络系统，通过一个能量站来实时监测传感器节点的能量状态，确定充电小车的充电顺序.并且，建立了该系统的概念原型，通过实验验证了实际系统的可行性，该系统的设计对于实际可充电传感器网络具有重要意义.除了对系统的设计和理论的验证，更多地是对充电设计的优化，即充电小车的路径优化求解、充电小车的部署等优化问题.Shi等人[11]研究了以充电小车休息时间最大化为目标的优化问题，同时证明了充电小车的最优路径是最短的哈密顿循环.同样是最大化充电小车的休息时间，Wang等人[12]侧重于充电路径规划的合理性做了进一步研究，根据已部署传感器网络的初始拓扑结构，将无线传感器网络划分为多个子网络.综合分析不同传感器节点的能量状态和位置，将整个网络的优化充电路径问题转化为子网络的局部优化问题，求解出每个子网络中动态网络拓扑下的最优充电路径，以此延长传感器网络的寿命.

与此同时，研究人员也考虑到了对多辆充电小车的充电设计.多辆充电小车单独负责小部分传感器节点的充电，共同维持整个网络的生命周期.在多充电小车的传感器网络中，面临的重要问题是充电成本，最小化充电小车数量和最大化充电效率是众多研究的优化目标.Wang等人[13]主要研究了多充电小车调度问题，在网络中心设置了一个中心调度器，当收到充电请求时，将立即分配充电小车进行充电.并且，规划了均匀和局部两种充电请求，对两种充电策略(分配最近充电小车去充电和分配距离较远充电小车去充电)进行了评估.为了尽可能地提高能量利用率，在不考虑移动充电小车自身能量的条件下，Zhang等人[14]提出了一种新型的协同移动充电模式，各个移动充电小车之间可以相互传输能量，以此来扩大充电范围.而Liu等人[15]首先最小化充电小车数量，在确定最小数量之后再对路径长度最小化，最后达到低能耗的目的.此外，Chen等人[16]提出对充电小车的速度参数进行优化，创造了移动过程中的充电机会，对以往先移动后充电的方法进行了创新，减少了最终的充电完成时间.

此外，充电优化问题的算法求解工作也有着一些突破，通过最短路径算法及一些不同的启发式算法来求解最优路径，可以使得移动充电小车的能量利用率提高，同时极大降低了充电成本和时间.俞立春等人[17]将精英策略引入到蛙跳算法[18]中，使用该算法求解出一条使小车能量利用率最大化的最优路径.陈花等人[19]考虑到小车自身能量有限，设计了周期性充电规划策略，在最大化充电周期的同时最小化充电小车能量消耗，以延长网络的生命周期，利用混沌粒子群算法[20]求解最优的充电路径和合理的充电时间.魏振春等人[21]则以最大化能量利用率和最小化数据传输时延为目标建立了联合充电和数据收集的多目标路径规划模型，通过多目标蚁群算法[22]求得了该多目标问题的Pareto最优解集.针对节点位置固定、能耗消耗快而导致的网络生命周期短的问题，夏静山等人[23]提出了一种考虑路径长度和能耗的双重目标下的充电路径优化方法，并使用遗传算法[24]来求解最优充电路径.但在实际充电问题中，如果充电小车仅在一个节点位置上耗费太多的充电时间，那么其他急需充电的节点将等待较长的时间，这样的充电过程对于延长网络生命周期是低效的.所以，不仅要考虑小车自身的能量消耗，还需对充电时间进行规划，当充电小车大于一辆时，充电小车的数量也不可忽视.

本文的主要工作有以下几点：首先建立了具有多辆多种充电小车的可充电传感器网络场景，综合考虑充电小车行驶总路径、充电总时间和小车分配成本作为成本目标；同时，对原本的鸽群算法作出了改进，提出基于自适应惯性权重的速度更新公式.然后将改进的鸽群算法和遗传算法进行混合，用新的混合算法对充电路径规划问题求解；最后利用Matlab仿真工具进行了实验验证，以此证明设计的算法解决实际问题的有效性.

2 多辆多种充电小车的模型与问题描述

2.1 网络模型

考虑一种多充电小车的可充电传感器网络作为本研究的网络模型，图1为设计的网络模型.传感器的工作主要是监测、处理和发送数据等，在监测区域内，随机部署了大量传感器节点和基站，节点之间通过多跳路由将监测的数据发送给基站.多个移动充电小车从基站出发，遍历每个待充电的节点集，依次为待充电节点进行无线充电，最后，所有的充电小车返回到基站休息来补充能量.在图1中，空心节点为急需充电的节点，三角形表示为基站，长方形表示为充电小车，黑色线段为充电小车充电路径，箭头指向下一个需要充电的节点.

图1 网络模型

2.2 问题描述

在传感器网络中，传感器的工作主要是对监测数据的处理.在数据传输过程中，节点会消耗自身的能量，能量消耗模型如下所示.当节点能量达到最低值时，需要及时进行能量补充.

接收K比特数据时消耗的能量为：

Er=ERX*CM

(1)

在这里，ERX表示为接收每比特信息消耗的能量，数值为50×10-13J/b，CM表示为接收数据中控制信息的大小，数值为32bit.

传输K比特数据时消耗的能量为：

(2)

在这里，ETX表示为传输每比特信息消耗的能量，数值为50×10-13J/b；DM表示为传输数据中数据信息的大小，数值为4000bit；Efs表示为节点自身耗散的能量，数值为10×10-13J/b；d表示每个节点到基站的距离；由于距离基站较远的节点，消耗的能量更多.所以用d0表示节点到基站之间的距离临界值，其值为30m.

在本文中，设置一定数目的两种不同电池容量的充电小车，以此来补充节点的能量消耗.在这个过程中，主要研究的问题是：成本最小化的多车充电路径规划.即，在成本最小化的目标下，合理分配出最小数量的充电小车，并且每个小车所能承受的充电能力没有超过自身的电池容量.将该问题形象描述为：

minF

(3)

约束条件如下：

max(N)≤N

(4)

er(Ci)≤ec0，1≤i≤N

(5)

(6)

ec(Vm)≤e0，1≤m≤M

(7)

rm≤tm≤dm

(8)

公式(4)表示充电小车的分配数量N不超过充电小车的总数，公式(5)表示第i个充电小车补充给传感器节点的能量er不超过小车自身能量，公式(6)表示需要补充能量的节点数量不超过整个节点序列V，公式(7)表示第m个节点消耗的能量不超过节点自身的能量(能量约束).公式(8)表示时间约束，充电小车给第m个节点充电的时间tm在申请充电请求时刻rm和最后维持时刻dm之间(时间约束).

(9)

(10)

f3=N1·cost1+N2·cost2，0≤N1+N2≤N

(11)

F：argmin{f1，f2，f3}

(12)

成本理论上由可变成本和固定成本两部分组成，在充电过程中，路径距离和充电总时间是一个可变成本，它们会因为待充电的节点不同而变化，而车辆自身包含固定成本，每个车型都有不同的成本系数，由表1可知，当分配车辆数目不确定

表1 参数设置

时，车辆成本也随之变化.关于成本最小化由公式(12)所示，综合考虑了路径距离、充电时间和车辆成本3个目标.公式(9)为路径距离，是每个充电小车为对应的节点序列进行充电的距离总和.公式(10)为充电时间，充电小车为节点充电的时间应该在公式(8)的约束范围内，当充电小车到达节点的时间大于维持能量的最后时间时，将产生节点等待的时间成本ncost；当充电小车提前到达节点时，将产生充电小车等待的时间成本ccost.公式(11)为充电小车的车辆成本，两种充电小车的电池容量不同，则两种车辆的成本系数cost也不同，并且分配车辆的数目N不超过充电小车总数.

3 改进的鸽群算法和遗传算法的混合UPIOGA

3.1 PIOGA混合算法的基本思想

鸽群算法是近年来才出现的一种群体智能优化算法，它是受自然界中鸽群自主归巢行为的启发而提出的.鸽群具有良好的导航和记忆能力，这对寻优过程非常有利.但在基本的鸽群算法中容易陷入局部极值，降低算法准确性，并且收敛速度不稳定.遗传算法则属于模拟演化规律的算法之一，通过设定初始的种群，然后以迭代的方式对种群进行选择、交叉、变异操作，最终得到适应性更强的种群，具有全局收敛性.本文通过将遗传算法与鸽群算法结合来解决路径规划问题，首先使用遗传算法大范围内搜索一组粗略解，然后以这组粗略解作为鸽群算法的初始种群，最后利用鸽群算法的指南针等特性进一步搜寻邻近区域可能的解.该混合算法既具有遗传算法全局寻优的特性，又具备鸽群算法的邻域寻优特性，从整体上提高了算法的执行效率.具体算法步骤：

1)初始化n个网络节点坐标，产生初始的遗传算法种群；

2)将每一条充电路径作为种群中的每个个体，计算每个个体的适应值，本文中的适应值函数f由公式(12)和(13)共同得出；

3)通过遗传算法中的选择、交叉和变异操作，以此更新种群；

4)达到预定的迭代次数后，输出初步优化后的种群；

5)由4)得到的种群作为鸽群算法的初始种群，进一步邻域寻优；

6)初始化鸽群算法中的参数，参数值如表1所示；

7)计算每只鸽子的适应值，同(2)；

8)地图和指南针算子更新，利用公式(15)和公式(16)更新个体的位置和速度，循环迭代要求的次数(在表1设定)后得到当前最好的位置；

9)将8)的个体位置移交给地标算子，继续按照要求的迭代次数循环更新，在每次循环中将鸽子的总数折半，对当前位置按照适应值函数排序，排在后半段的鸽子被认为远离目的地并且不熟悉地标，从而被舍弃；

10)迭代结束后，输出最终优化后的种群.完整的算法流程图如图2所示.

图2 算法流程图

3.2 混合算法PIOGA中的遗传操作

3.2.1 编码

对于充电车辆路径规划问题，本文采用自然数编码原则.假设m辆车为n个传感器节点进行充电服务，染色体编码为(0，i11i12，…，i1a，0，i21i22，…，i2b，0，…，0，im1，…，imn，0)，其中0代表传感器网络中的基站，即所有充电小车的起始位置，a，b，…，n指的是每个小车负责充电的节点个数，它们负责充电的节点个数是随机无序的，同时a，b，…，n这些数量不超过传感器节点数量n.1，2，…，m指的是m辆小车的编号，而两个0之间的序列表示每一个充电小车行走的子路径.通过算法优化，最终可以求解出最佳路径，并从路径中可以得出充电车辆的分配数量.

3.2.2 适应值函数和选择操作

多车辆的充电路线优化问题的优化目标就是要找到充电成本最小的车辆路线.因此，本文将3个目标f1，f2，f3线性整合为一个单目标F，F由公式(12)得到，1/F作为该算法的适应值函数f.

(13)

选择操作采用轮盘赌法，选择生命力强的个体繁殖后代产生新的种群.假设N为种群数目，fi为某个个体i的适应值，则该个体被选择的概率为：

(14)

3.2.3 交叉

交叉是进化算法中的重要过程，通过交叉，子代才能继承父代的优良性状.在本文中，采用如下交叉方式：

假设两条父代的染色体编码为p1和p2，其中：

1)随机初始化交叉点的位置和交叉长度.

2)分别找出p1和p2的交叉段，将p1的交叉段插入p2的交叉点中，将p2的交叉段插入p1的交叉点中，交叉成为s1和s2.

3)删除s1和s2中重复的编码，得到新的s1和s2.交叉实例图如图3所示.

图3 交叉实例图

3.2.4 变异

变异操作是为了增加种群的多样性，是指按照一定的概率将染色体中的某些基因转变成其他基因的过程.变异概率一般在5%以下.采用如下变异操作：

设染色体的编码长度为L.

1)随机生成两个不等的正整数r1和r2，且r1，r2均小于等于L.

2)交换染色体中的第r1位和第r2位基因.如图4所示.

图4 变异实例图

3.3 鸽群算法的改进

在复杂环境下采用鸽群算法进行路径规划时，存在容易陷入局部最优、收敛速度较慢和不稳定等问题，所以在本文中对鸽群算法进行了改进，引入自适应权重系数对种群中个体的速度、位置进行计算，由公式(15)、公式(16)所示，以提高鸽群算法的执行效率和满足最优路径规划.

(15)

(16)

(17)

其中，Vi和Xi表示第i个个体第t次迭代后的速度和位置，w为惯性权重，rand为随机数，Xg为当前迭代的全局最优值.在公式(17)中通过适应值函数f的比较来对惯性权重进行取值，f为公式(13)所提到的成本适应值函数，f与当前鸽群的平均成本值进行比较.

4 仿真实验及结果分析

4.1 场景和参数设置

为了验证算法和模型的有效性，设置了两种实验场景：传感器节点随机均匀分布在网络区域内和传感器节点呈圆环分布在网络区域内，如图5(a)、图5(b)所示.对于整个充电过程中涉及到的参数，取值如表1所示.本实验环境采用MatalbR2016a版本对UPIOGA算法进行仿真.采用对比法，与PIO算法、GA算法、基本的PIOGA混合算法和经典的HSGA混合算法分别在同一场景下进行比较.

4.2 实验结果

由图5(c)、图5(d)、图5(e)可以得出，两种节点分布相比较而言，均匀分布更适合本文的算法和模型，在圆环分布下的成本过高，节点位置固定，不具有随机性.通过大量的仿真实验，可以验证5种不同算法下的充电性能.表2列出了基于5种算法的充电成本和路线，并且对充电车辆分配情况做出了说明.从表2中可以得出，改进的PIOGA算法(UPIOGA)下的充电成本最小，充电路线更佳.与此同时，在图6基于5种算法的路线轨迹图中，UPIOGA算法的充电分布更均衡，提高了每个充电小车的能量利用率.

表2 充电成本和路线

图5 节点分布比较

图6 基于5种算法的对比结果

从表3测试问题的计算结果来看，UPIOGA算法的评价指标，即算法均值、最好值、均方差均好于算法GA、PIO的评价指标，虽然GA的最差值较好，但其均方差比UPIOGA算法较大.同时，从图6(f)的收敛曲线来看，UPIOGA算法既克服了单一算法过早收敛的不足，也获取了更好的解，能较好地保持算法的全局优化性能.

表3 5种算法对充电车辆问题的仿真实验结果

5 结 论

本文针对多充电小车路径规划问题，对基本的成本目标模型进行了改进：路径距离、充电时间和车辆成本综合考虑为一个充电成本目标.同时，对基本的鸽群算法进行了改进：在原有的个体速度公式基础上，增加关于实际充电成本的自适应惯性权重.最后将改进的鸽群算法与遗传算法混合为一个新的算法UPIOGA，基于UPIOGA算法求解充电路径问题.仿真实验证明了模型的合理性和算法的有效性.

在未来的工作中，可以将充电效率、能量消耗和充电车辆数量等因素综合考虑，使充电路径问题成为一个高维多目标优化问题.