无人机辅助的无线可充电传感网充电路径规划方案

王 杨，单天乐，赵传信，陈 鹏，艾世成

1(安徽师范大学 计算机与信息学院，安徽 芜湖 241000) 2(安徽建筑大学 智能建筑与建筑节能安徽省重点实验室，合肥 230022) 3(东南大学 计算机科学与工程学院，南京 211189)

1 引 言

针对无线可充电传感网的节点能量补充问题，国内外学者进行了很多研究和实践，其中最常用的是利用移动充电小车[1-3](Mobile Charger，MC)对WRSNs进行能量补充.然而，充电小车在一些条件受限和环境恶劣的地区，比如自然灾区、战争地区等，难以发挥其作用.即便在常规环境，也可能因障碍物较多使其路径规划失败.

为了解决此问题，本文提出了无人机辅助的基于分簇的WRSNs充电路径规划.文中无人机指携带充电装置、可进行无线充电的飞行器.其优点包括：速度快、灵活性强、可以轻松越过一般障碍物以及定点悬停等[4].所以，本文所提出的借助UAV的基于分簇无线充电策略，可以弥补MC的不足之处.

现有无线充电技术主要基于3大原理：1)电磁感应技术[5]，生活中很多设备都利用这一技术实现无线充电，例如手机、电动汽车等，它具有技术成熟且简单、一对一式充电[6-8]、效率较低等特点；2)磁耦合谐振技术[9]，相比电磁感应充电技术，它支持更大的空间范围内的能量传输，具有可以一对多式充电[10-12]、距离较短(10米左右)等特点；3)无线电波技术[13]，它具有充电范围更广(几十公里)、要求较高、安全性不够高等特点.本文采用磁耦合谐振技术对网络进行充电，比较符合中小范围内无线充电的要求.

根据充电器锚点的选择进行划分，现有研究成果主要分为以传感器节点位置为锚点[14-16]和以传感器网络各区块的重心为锚点[17-19]两大类.前者通常假设MC从充电中心出发，遍历沿途的传感器节点为它们进行一对一式或者一对多式充电，锚点选择在传感器节点的位置上.如Dai[14]等人以效用最大化为目标，提出了一种一对多有向充电调度方案.Zhu[15]等人以尽可能降低节点饿死率为目标，提出了基于饥饿避免的在线充电策略，该策略始终选择使其他待充电节点饥饿数最少的传感器节点作为锚点以尽量避免节点陷入能量饥饿状态.Lin[16]等人通过达到某一项性能的最优制定对应的移动充电策略，对低能量的节点进行能量补充.以传感器节点位置为锚点的好处是不用另外寻求合适的位置作为锚点，其缺点主要是由于位置固定可能不是最佳充电位置，并且会增加锚点数量和充电时间.

为了减少充电时间与提高充电效率，Han[17]等人提出了采用非均匀分簇的多跳路由协议选择各簇区域的簇头节点并且只对簇头节点进行充电与收集簇内节点的能量信息的调度方案，大大减少了在每个簇区域停留充电的时间从而减少了能耗.Lyu[18]等人提出了改进型的K聚类算法MCH，用在网络中选取合适的簇头节点，使得簇头节点能够均匀的分布在网络中，此外还保证了选区的簇头节点更好地兼顾簇内外的平衡.更有Mo L[19]等提出了基于非均匀分簇的无线充电和数据收集算法.通过分析网络中节点能耗和充电车的移动特性，采用蚁群算法求解节点的最佳路由路径，在延长网络寿命的基础上均衡节点能耗，提高网络内能量利用率.

本文的总体思路是先对中小型WRSNs进行非均匀分簇并且以簇区域的圆心作为无人机悬停充电时所处的水平位置，同时以簇区域大小来设置UAV最佳悬停高度，最后依据簇优先级将区域内的各锚点进行巡游遍历并且找寻最短路径作为规划.此方案考虑的是在中小范围内、无人机能源有限的情况下，如何尽可能地节省路径消耗来提高充电消耗占总功耗的比值问题.比起其他方案，本方案利用网络分簇并借助UAV，既可以减少悬停充电的次数也可以避免与地面障碍物碰撞，大大提高了能量利用率.

2 问题描述和系统模型

2.1 问题与方案描述

传统的传感器节点一般为电池供电，有限的能量限制了无线传感网的整体寿命.通过无线能量传输技术可以解决这一问题.本文做法是通过分簇并借助UAV对目标WRSN进行高效充电.假设UAV从充电中心出发，沿簇优先级顺序直线飞行并在锚点处适时悬停给簇中各节点充能，完成充电任务后返回至充电中心.研究的是在UAV电量充足、传感器节点随机分布的中小型WRSN中单体UAV的充电路径优化.最后各种实验环境下(包括WRSN的规模、节点的个数和节点的分布情况等方面)进行与MUC、AEC方案对比实验，再从充电周期等方面与CRP、HCCA进行对比.

2.2 网络分簇模型

本文的网络分簇模型如图1所示.

图1 网络分簇模型Fig.1 Network clustering model

二维平面上的WRSNs可以通过改进的K-means算法进行自适应分簇，此算法首先以一定规则随机产生簇头节点并告知网络此结果，在簇的建立阶段，非簇头节点根据自身与簇头节点的距离来选择加入哪个簇，并告知该簇头.最后形成一个个簇区域，簇的多少与簇的大小成负相关.本文以簇最外围传感器节点为圆弧切点作一个包括整个簇区域的圆，并且以其圆心作为锚点利用UAV对每个簇区域内节点进行无线充电.

2.3 无人机充电空间模型

三维空间中的无人机充电网络可以表示为N=(U，S)，其中U=(x，y，z，v)，S=(B，P).U是无人机无线充电时悬停的位置，用坐标x、y、z表示，并称其为锚点.x、y确定地理位置，z为无人机悬停高度，v为其飞行速度，由此进行合理的能量传输.S表示传感器节点的信息，B为电池信息，表示其所剩电量的百分比，P为传感器所处的地理位置.

采用二进制数V(Cr,Si)表示网络中传感器节点Si能否被Cr覆盖到.如公式(1)所示：

(1)

其中Maxdis为最大充电距离，Cr为最大充电范围(这里为一个圆域)，r为充电半径.d(Cr,Si)为传感器距离圆心的距离，D为传感器距离无人机的空间距离，另外有向充电器的充电角度用表示θu取值为60度.无人机充电空间模型如图2所示.

图2 无人机充电空间模型Fig.2 UAV charging space model

2.4 无线充电功率

当传感器节点处在充电辐射范围内，无人机与地面节点的信道功率增益在时刻t可表示为[20]:

(2)

其中β0表示距离为1时的参考信道功率增益，主要与负载频率和天线增益有关.Dsr(i，t)表示t时刻无人机与地面设备的距离.网络中无线能量的传输功率如公式(3)所示：

(3)

式中，Pr为传感器节点接收到的充电功率；D为传感器节点与充电器之间的距离；η为传输效率；Ps是无人机能量发送功率.Maxdis表示UAV可实现充电的最远距离.

2.5 充电工作基本流程

图3为OCPS算法的充电流程图.在一次充电工作开始前，CC会将所有簇的簇头节点按优先级顺序进行规划路径.UAV从CC出发按照已规划好的充电路径遍历每个簇进行悬停充电，并收集簇内节点信息.然后判断整个簇的电量是否充满，确定充满后飞至下一处进行同样工作否则继续充电.最后结束前检查是否遍历所有的锚点，是的话充电结束，否的话继续遍历直至所有簇区电量充足.文中假设UAV在新的一轮充电开始时携带充足的量，可满足一次调度中的充电需求和自身消耗，并且UAV从充电中心出发前已获知待充电节点的位置信息和电量信息.

图3 充电流程图Fig.3 Charging flow chart

3 充电路径优化方案

在充电路径优化过程中，关键的3个问题分别为：簇的划分与优先级的描述、UAV飞行高度的确定、飞行路径的选取.

3.1 簇的划分与优先级的描述

在具有n个传感器节点中小型WRSN中，选取(表示可同时充电的最大节点数)个分布均匀的传感器节点作为簇头，将传感器按照与簇头节点的距离大小分类，同一类的形成一个区域称为簇并用C表示.因节点分布不均所以进行的是非均匀分簇，具体过程如算法1所示.

算法1.改进的K-Means聚类分簇算法(PKM)

输入：随机的组与其簇头节点集合{Cr}、初始的K值、传感器节点集合{Si}

输出：非均匀的簇区域集合{Ci}

1.Setk=n/α

2.Initiatek cores

3.ForSjin {Si}

4.while(Sj)do

5.Calculatethedistances between Sj and k cores

6.Ifdis(x)is the minimum

7.PutSj into the {Cx} cluster

8.DeleteSj from {Si}

9.Endif

10.Endwhile

11.Recalculatecores as {Ci}

12.Returnstep 3

13.ifpre cluster core is clustercore

14. break

15.elsereturn Step 11

16.endif

17.endfor

18.return{Ci}

步骤2中距离度量标准是欧几里得距离的平方[21]：

(4)

其中x和y表示不同的两个样本，h为UAV悬停高度，n表示样本维度(节点的数量).

图4为聚类分簇示意图，共有46个传感器节点，采用K-Means聚类算法进行分簇，这里k的取值为3，即把46个对象分成3组.圆心作为锚点，边缘传感器与锚点的距离作为覆盖半径，得到3个簇区域.簇1与3为最大簇，灰色的节点为噪声节点[22].其中簇区域优先级的描述如算法2所示.

图4 聚类分簇示意Fig.4 Clustering diagram

算法2.簇优先级描述(CPD)

输入：每个节点的初始能量ei、各簇Ci所含节点信息、簇优先级划分φi

输出：每个簇的优先级ψj

1.Set，φ2=2，φ3=1

2.foreiin Cj

3.while(ei>0)do

4.caseei≤20：ψj+=φ1

5.case20

6.case50

7.endcase

8.endwhile

9.outputΨj=Ψj/i

10.endfor

3.2 UAV飞行高度的确定

无人机进行充电时，其飞行高度的变化会改变覆盖范围的大小以及充电速率的快慢.由公式(2)可知，在覆盖范围内时UAV与传感器节点之间的距离越远，无线充电的效率大大降低，而距离越近时覆盖的节点越少，因此必然存在合理的高度范围.

假设无线充电装置的最大覆盖角度为60度，那么当无人机飞行高度H1=3m时，其在地面形成的覆盖半径OA=5.19m，此区域(称为S1)内所有节点与UAV的距离在3m～5.19m之间；当无人机飞行高度H2=5m时，其在地面形成的覆盖半径OB=8.66m，此区域(称为S2)内所有节点与UAV的距离在3m～8.66m之间，如图5所示.

图5 不同高度下充电覆盖范围Fig.5 Charging coverage at different heights

图中两个三角形为相似三角形，可以得到：

(5)

假定充电最大角度为60度，这是在硬件选择时确定的.根据三角函数可得：

r=H×sinθ

(6)

(7)

边缘节点的充电功率为：

(8)

式(8)中只有H为变量.可以依据每个簇区域充电时间长短作为判断悬停高度合适与否的标准并进行如下计算.

图6 UAV悬停高度与充电时间关系Fig.6 Relationship between height and charging time

3.3 飞行路径的选取

对每个簇优先级进行从高到低排序以此作为初始序列并开始充电，然后采取动态优先级判决算法DPD对初始序列进行更新直至找到最优路径.将本文所提改进的K-Means聚类分簇算法PKM和簇优先级描述算法CPD结合起来，能得到完整的最优充电路径规划(Optimal Charging Path Scheme，OCPS)，OCPS算法执行流程如算法3所示.

算法3.基于动态优先级的充电路径规划(OCPS)

输入：WRSN中所有传感器节点集合N(包括每个节点位置坐标与剩余能量信息)；

输出：最优充电路径δ

1.执行PKM聚类分簇算法，将节点集合N分类为分簇集合C={c1,c2,…,ck}，并求出锚点集合M={m1,m2,…,mk}

2.根据集合C与M得到UAV给簇区域充电的充电地点

3.由CPD算法得到充电顺序关系，先对优先级最高的簇进行充电

4.执行动态优先级判决算法得到动态的充电路径规划，最终得到最优充电路径δ

算法4.动态优先级判决算法DPD

输入：簇优先级ψj、锚点Mi位置信息GM、UAV位置信息GU、各簇区域Cj、簇内紧急节点个数ni

输出：下一个充电锚点位置GN

1.SetGUonC1of the maxΨj

2.Calculatethe distance betweenGUandGMthendenoted byDij

3.forDiinDij

4.While(Di!=0)

5.Ifni·ψj/dijis the max of {ψ1、ψ2…ψj}

6.ψi=ni·ψj/dij

7. Remove the max from {ψ1、ψ2…ψj}

8.Elseψi=ψi

9.endif

10.endwhile

11.endfor

12.outputGNof the maxΨj

当UAV给某一节点充电后自动记录，不会重复充电，且对于大面积下的飞行轨迹可以忽略飞行高度进行平面路径规划.路径选择阶段如图7所示.图7(a)中，锚点1因初始优先级最高被选作第一个悬停充电地点.充电结束前获取UAV与其它各节点之间的距离，以作为动态优先级进行比较，拥有最高优先级的作为下一个充电地点.计算得到锚点2的优先级最高为0.016，其余3个分别为0.011、0.0065、0.0054，UAV飞往进行充电并将剩余节点优先级恢复至初始值.

图7(b)中，UAV在锚点2处充电，结束前获取与剩余节点之间的距离并且计算各簇的动态优先级.计算结果为ψ3=0.0095、ψ4=0.0045、ψ5=0.005，于是选择锚点3作为下一处充电地点.

同样地，图7(c)中UAV在锚点3处充电并计算得到ψ4=0.0071、ψ5=0.0025.所以选择飞至锚点4进行充电，最后因只剩下锚点5还未进行充电，所以飞至锚点5完成对整个WRSN的充能.

整个充电过程如图7(d)所示，UAV飞行路径长度为900m，飞行时间为90s对于整个充电周期时长可以忽略不计，能耗为900J约为总能量的1%，此路径较优.簇中节点数相同时，值越大簇所需能量越多.

图7 充电路径选择Figure 7 Charging path selection

采用本方案所得到的充电路径，因分簇使得目标充电区域明确且数量较少，减少了UAV悬停次数与飞行路程.又因优先级划分使区域间可以有序地进行充电，同时采取动态变化的优先级能够增强方案的鲁棒性.

4 实验与结果分析

本节从饿死节点数、充电效率[23]以及充电时长方面测试了OCPS方案的性能表现并与其它相关方案进行了对比.其中饿死节点数表示一个充电周期节点因能量不足而失效的数量；充电效率表示在一次充电调度中UAV为网络内节点补充的总能量占其自身消耗总能量的百分比；充电时长是指UAV从基站出发，完成一轮充电后返回基站的时间.

4.1 参数设置

实验所需参数如表1所示.

表1 参数设置Table 1 Parameter settings

4.2 基线算法

1)本文使用以下两种传统的方案进行对比实验：

·AEC(Average energy charging)算法：在能够巡游覆盖所有节点的前提下，将可用的充电时间平均分配给每个覆盖集合.

·MUC(Maximum utility charging)算法：根据有向覆盖子集确定充电锚点，在满足充电周期约束条件下优化充电路径.

2)本文与两种距离优先的方案进行性能比较：

·HCCA算法：以启发式LK算法迭代优化，通过增加计算复杂度获得更好的距离性能.

·CRP算法：以物理距离为纬度的贪心算法，此策略在充电距离上有优势，但容易陷入局部最优.

4.3 实验结果及分析

实验场景为400×400m的WRSN，剩余能量不一的传感器节点随机分布其中.

4.3.1 与MUC、AEC的比较

图8为不同节点规模下各算法充电效率对比图.从中可以得到少数量节点情况下，三者充电效率相差不大，在超过70个节点后，因MUC与AEC采用MC在移动方面的能耗远超UAV飞行所消耗并且算法所得路径更长，使得它们效率低于OCPS.另外随节点规模增加MUC充电效率逐渐提高，AEC趋于平稳.平均充电效率OCPS比MUC提高19.5%，比AEC提高27.9%.

图8 不同节点规模下各算法充电效率对比Fig.8 Comparison of the charging efficiency

图9为不同节点规模下各算法失效节点数比较图.节点较少时，因OCPS分簇会产生噪声节点，其失效节点比另外两种算法多.节点较多时，因MUC与AEC移动速度有限且驻留充电节点增加使得失效节点数上升并超过OCPS失效节点数量.可以得到，一定节点数量范围内OCPS算法失效节点与传感网中总节点个数没有必然联系，只与其分簇算法有关.

图9 不同节点规模下各算法饿死节点数Fig.9 Number of nodes starved to death

图10为不同节点规模下各算法巡游充电总时间.充电总时间随着节点个数增加而增加，在不多于70个节点时，3个方案的充电时间保持在30～60min内.90个节点处出现拐点，MUC与AEC充电时间明显增加，因其巡游路径更长、充电停留时间越久.OCPS算法充电时间增加得相对平缓，这是因为其在路径上消耗的时间远小于MC且由于分簇使其停留次数减至最少.

图10 不同节点规模下各算法充电时长Fig.10 Charging time of each algorithm

4.3.2 与CRP、HCCA的比较

传感器节点为90个时，各算法分簇及优先级情况如表2～表4所示.

表3 90节点时锚点信息-CRPTable 3 Anchor information-CRP

表4 90节点时锚点信息-HCCATable 4 Anchor information-HCCA

由表可知，OCPS、CRP、HCCA 3种方案分别将WRSN分成7、10、8个簇区域，这是由于它们在分簇算法上的差异，其中CRP为均匀分簇，OCPS、HCCA为非均匀分簇.经计算可以得到3种方案的飞行路径长度分别为1440、2160、1820m.在节点分布不同情况下，每种算法表现出的性能也不一样，所以选择同一实验环境可以更客观的从某种角度评判不同方案的优良.

图11为各算法在每个周期结束时的饿死节点数直观图.从中可以看出在两个周期内都保持在5个以内，且HCCA的死亡节点数更少；在后面两个周期结束时，OCPS算法表现优于另外两种算法，因为其锚点较少且路径消耗时长更少使得性能更为稳定，饿死节点一般为噪声节点.

图11 不同周期结束时各算法死亡节点数Fig.11 Number of dead nodes in each algorithm

图12为不同网络规模下各算法一个周期需飞行的路径长度.从中可以看出各算法在200m×200m范围内表现差异不大，随着范围扩大OCPS表现出其良好的稳定性.由于动态优先级描述算法，使得它兼顾到簇区域平均电量和距离因素，具有一定鲁棒性.而CRP算法因分簇所得簇区域最多且优先级描述固定使得其飞行距离较另外两个算法更长.另外OCPS算法平均飞行长度比CRP、HCCA分别缩短21.3%、10.8%.

图12 各网络规模下飞行距离Fig.12 Flight distance under each network scale

图13为不同网络规模下各算法一个充电周期所需时间.从图中可得200m×200m范围内三者充电时间相近，此范围外可按充电时间由少到多排序为OCPS、HCCA、CRP.在充电方面，因OCPS为非均匀分簇且最适高度随充电半径而变化，比CRP的均匀分簇更加高效，比HCCA的固定高度更加灵活.平均充电周期OCPS比CRP、HCCA分别缩短4.25、1.17mins.

图13 不同网络规模下充电时长Fig.13 Charging time under each network scale

5 总 结

本文针对中小范围无线可充电传感网络中传感器节点能量受限问题，提出了基于分簇的WRSNs最优充电路径规划方案OCPS.方案中一系列创新的方法，包括非均匀分簇算法、动态优先级算法等，简化了复杂路径规划的问题，并结合本文对合适高度的选择设计出了合理的充电路径规划方案.与相关方案进行实验对比，OCPS在充电利用率、充电时长与饿死节点数目等方面均表现出一定的优越性.

鉴于本文考虑的仅是单体无人机在中小范围WRSN内的充电规划问题，而大范围WRSN与多移动充电器更为重要，未来研究中将在本方案的基础上考虑中大范围多无人机的充电调度问题.