面向WSNs节点数据采集的无人机Voronoi图路径规划

王正才, 彭 红

(贵州轻工职业技术学院, 贵阳 550025)

0 引言

利用移动数据收集设备可提高无线传感网络 (Wireless Sensor Networks，WSNs)[1-2]的能效及数据传输效率。通过移动，收集设备靠近每个节点，提高数据收集效率，再将所收集的数据传输至控制中心。通过收集设备的移动，避免了节点与控制中心通信，节省了因传输数据所消耗的能量。

最近，基于无人机(Unmanned Aerial Vehicle, UAV)的飞行数据收集器受到广泛关注[3-5]。相比于地面数据收集器(例如，移动机器人)，UAV移动更方便。地面上的数据收集器移动容易受到障碍物影响。此外，利用UAV通信，增加了信号传输的可靠性[6]。

然而，由于UAV的车载能量有限，它的移动总体距离受限[7-8]。因此，UAV应当在收集所有节点数据后，能够有能量返程，这就涉及到UAV路由设计问题。因此，如何设计低能耗的UAV路由成为UAV领域的研究热点。

除了能耗，设计UAV路由还需考虑UAV的类型。按飞行平台构型，可将UAV分为固定翼和多旋翼无人机。相比于固定翼，多旋翼UAV可以在任意方向上移动，并且能在特定位置上盘旋。此外，通过优化UAV盘旋的位置，可以控制传感节点传输数据时的能耗和UAV遍历的距离。

研究人员针对UAV盘旋位置进行了深入研究[9-11]。文献[9]提出了“节点视觉”方法，让UAV遍布每个传感节点，使UAV与节点间的通信距离最小，但是该方法增长了UAV所遍历的路程。

为了缩短移动路程，文献[10-11]选用了部分节点作为簇头，UAV只遍历簇头。但是该方法增加了簇头节点的能耗。此外，该方法要求节点能够向簇头传输数据，若节点间不能直接通信的话，该方法就无法使用。

文献[12-17]利用传感节点的通信范围决策UAV盘旋位置。先优化UAV的盘旋位置，致使在每个盘旋的位置，UAV能够与多个邻居节点通信。为了避免通信冲突，节点间采用基于时分多址接入(Time-Division Multiple Access, TDMA)策略。然而，由于所有UAV盘旋的位置并非是完全独立，决策UAV的盘旋位置是一项挑战的工作。

文献[12]利用Welzl的算法[18]构建能够共享一个盘旋位置的节点集。而文献[13-15]利用Voronoi图产生UAV盘旋位置。而文献[19-20]分别利用遗传算法、k-最短路径搜索最优的UAV盘旋位置。然而，这些方法产生的UAV盘旋位置并不是最优的。

为此，提出基于Voronoi图的无人机路径规划算法VDO-UAV。VDO-UAV算法依据Voronoi图产生参考路径，再在参考路径的基础上优化UAV盘旋的各位位置，最终由这些位置点构成UAV遍历路径。仿真结果表明，提出的VDO-UAV算法在不增加复杂度的前提下，缩短了遍历路径。

1 系统模型

引用多旋翼UAV机，其在高空H处收集节点数据。节点间不能直接通信。假定在区域Ω内有N个节点。用xi表示节点si的位置，i=1,2,…,N。

令PLπ={0,1,…,K,0}表示UAV的移动位置点。K表示UAV的第k次盘旋的位置 。由于K≤N,UAV在单个盘旋位置上能够收集多个邻居节点的数据。

令DLπ表示UAV所遍历的路程，其定义如式(1)所示：

(1)

式中，d表示i与i+1间的距离；Lπ={1,2,…,K}。

假定节点si向位于π(i)的UAV机传输数据，且π(i)∈{1,…,K}。表1给出一个示例，其中N=6、K=3。UAV移动位置点PLπ={0,1,2,3,0}。例如，π(2)=1表示节点2向位于1的UAV传输数据。类似地，π(5)=2表示节点5向位于2的UAV传输数据。

表1 节点与UAV盘旋位置示例

1.1 信道模型

将UAV与节点间链路视为视线链路(Line-of-Sight, LoS)。当节点si向位于π(i)位置点的UAV传输数据时，在UAV处所获取的信号功率：

(2)

图1 通信距离与水平距离示意图

1.2 传输能耗

采用文献[21]的能耗模型。节点si通过控制它的传输功率Gi，保证UAV接收信号的功率达到预设的值。因此，节点si向UAV传输bi比特数据所消耗的能量：

(3)

2 问题描述

(4)

因此，可利用式(5)表述VDO-UAV算法需解决的问题：

(5)

约束条件：

(6)

(7)

(8)

π(i)∈{1,2…,K},si∈S

(9)

3 VDO-UAV算法

3.1 Voronoi图的修正

{p|dp,xi=dp,xm,m∈A(i),i∈A(m),m∈S,p∈Ω}

(10)

式中：dp,xm表示点p离节点si的距离；A(i)表示节点si的邻居节点集；Ω表示监测区域。

(a) 修正前 (b) 修正后图2 构建示例

3.2 最短路由决策

通过最小化UAV盘旋位置数，缩短UAV遍历的距离。换而言之，每个UAV盘旋位置应尽可能覆盖多个节点，进而收集更多节点数据。据此，每条Voronoi边或中心均存在两个或两上以上的邻居Voronoi中心(节点)。因此，可用L(h)搜索最短路由，其中h=1,2,…,hmax。然而，如果直接搜索，计算量较大。

为了降低计算量，采用基于参考路径。所谓参考路径是指由各Voronoi中心连线组成的路径，如图3所示。参考路径是基于旅行商问题(Traveling Salesman Problem,TSP)[9]求解的路径。

而浙江省气象台此前使用的省级海洋业务平台因为开发应用多年,且主要功能以多种产品显示为主,不具有GIS缩放、格点订正等功能,无法很好展示近年来发展的海洋气象客观预报产品的精细化程度,已不能满足现代化海洋预报业务的需求。为此,省气象台及时组织力量开发新一代省级海洋预报业务平台。新一代海洋预报业务平台是立足于为全省气象预报员服务,基于海洋业务扁平化的理念,提供集数据采集、精细分析、格点订正、预报制作、快速发布、产品展示、工作记录等功能于一体,基于Silverlight和SQL数据库技术进行开发的专业业务平台,并将在使用中不断发展来更好满足台风和海洋气象预报业务需求。

算法1 The shortest route determination on mVDdmaxn Input:Reference path,a starting point,route direction,Lhmax,Lhmax-1,…,L(1).Output:The set of UAV hovering locations L.Initialize:ʌ≜1,…,N ,L=⌀.Step 1:Assign numbers to mVDdmaxn 1:Assign numbers to Voronoi regions in an ascending order along the reference path an the route direction,from the starting point.Step 2:Determine UAV hovering location,sequentially2:h←hmax3:if h≥4 then4:if L(h)≠⌀ then5:L←L∪l(h)|∀l(h)L(h) .For all l(h)L(h),numbers as-signed to Voronoi regions adjacent to l(h)are removed from the set Λ.6:end if7:h←h-1 and go to line 3.8:end if9:Let l(3)L(3)be the Voronoi vertex surrounded by three Voronoi regions with consecutive numbers.10:if l(3)exists for numbers i,i+1,i+2 Λ then11:L←L∪l(3) ,Λ←Λi,i+1,i+2 ,Go to line 9.12:end if13:For two adjacent Voronoi regions with consecutive numbers,let l(2)L(2)be the intersection of Voronoi edge and the reference path.14:if l(2)exists for numbers i,i+1 Λ then15:L←L∪l(2) ,Λ←Λi,i+1 ,Go to line 13.16:end if17:Let l(1)L(1)be the Voronoi center with number i Λ.L←L∪l(1)|∀i Λ Step 3:Find the shortest UAV route18:All lL are connected along the order of the reference path to make a closed route.19:For each l(1)L,replace l(1)with the intersection of the closed route and the MHCR of the corresponding sensor.

决策UAV路由的过程如算法1所示。具体步骤如下：

(1)首先沿参考路径，从始点对Voronoi区进行编号，如图3所示，沿着参考路径，对15个Voronoi区进行编号。

(2) 利用L(hmax)，L(hmax-1)，…，L(1)决策UAV盘旋的位置。具体而言，当h≥4时，所有区中心位置(h)∈L(h)都作为UAV盘旋的位置；当h≤3时，就寻找3个Voronoi区所包围的Voronoi顶点，并将这些顶点作为UAV盘旋的位置，如图3所示的红色圆点。第5、6、7个Voronoi区包围一个顶点，如算法1的9～12行所示。

(3)除了由3个Voronoi区能够包围的顶点外，即剩余的就是2个Voronoi区相邻或者孤立的一个Voronoi区。对于2个Voronoi区相邻情况(h=2)，就取Voronoi边与参考路径的交点作为盘旋位置，如图3所示，Voronoi区2与Voronoi区3。图中黑色的正方形就是参考路径与边的交点，将其作为UAV盘旋位置，如算法1的13～16行。

(4)只剩余孤立的Voronoi区(h=1)，在这种情况下，就将该孤立的Voronoi区的中心位置作为UAV盘旋位置，如图3所示的Voronoi区 4。如算法1的17行所示。

最后，为了形成闭合的路由，将所有UAV盘旋位置沿着参考路径连接成闭合线路，进而形成闭合路径，如图3所示。

图3 路由决策示例

4 性能仿真

4.1 仿真环境

选择UAV遍历距离和平均目标值作为性能指标。在满足UAV遍历距离限制下，若不能找到UAV的可行路径，目标值就为零。

同时，选择TSP算法[9]、文献[12]提出的跳跃-替换的融合算法(Combine-Skip-Substitute, CSS)、基于Voronoi边的算法(Voronoi Edge based Method, VEM)[13]和穷搜索法作为参照，并与VDO-UAV算法进行性能对比。

选择TSP算法、CSS算法、VEM算法和穷搜索法作为参照的原因分别如下：①本文提出VDO-UAV算法求解的UAV路径是以基于TSP求解的参考路径为基础，并对其进行修改的；选择TSP算法作为参照，能够反映VDO-UAV算法对参考路径修改后的所得到路径的性能；②文献[12]提出的CSS算法也是将路径规划问题看成TSP问题，并采用CSS求解该TSP问题的解，其与TSP算法和VDO-UAV算法在TSP问题上存在共性；③VEM算法立足于多无人机路径规划问题，并采用遗传算法求解最优的路径。这与VDO-UAV算法的目的一致；④穷搜索法是简单粗暴的搜索法。VDO-UAV算法目的是搜索最优的路径。因此，选择穷搜索法作为基准参照。

4.2 UAV遍历距离

图4 UAV的遍历距离

相比于TSP和VEM算法，提出的VDO-UAV算法在UAV遍历距离上的性能得到提高。VDO-UAV算法中UAV遍历距离与CSS算法相似。CSS算法是通过传感节点的通信距离决策UAV路由。 穷搜索法使UAU遍历距离最小。但是其算法复杂度最高。

4.3 算法复杂度

表2给出TSP、VEM、CSS和VDO-UAV算法的时间复杂度。其中N表示节点数。从表2可知，穷搜索法的复杂度最高，其随N呈指数增长。尽管CSS算法控制了UAV遍历距离，但是它的复杂度高于VDO-UAV算法。

表2 算法复杂度

5 总结

针对WSNs的数据收集问题，提出基于Voronoi图的无人机路径规划VDO-UAV算法。VDO-UAV算法充分利用了无人机收集数据的灵活性。为了缩短UAV遍历路径，VDO-UAV算法利用先依据TSP的参考路径对Voronoi区进行编号，再优先将多个Voronoi区相交的顶点作为UAV盘旋的位置。仿真结果表明，提出的VDO-UAV算法缩短了遍历路径。