一种基于WSNs分簇与UAV飞行轨迹优化的UAV-WSNs数据收集方案

马行坡, 黄苗苗

(信阳师范大学 计算机与信息技术学院/河南省教育大数据分析与应用重点实验室, 河南 信阳 464000)

0 引言

在无人机(Unmanned Aerial Vehicle,UAV)协助的无线传感器网络(UAV-assisted Wireless Sensor Networks,UAV-WSNs)中,利用UAV协助进行数据收集能够有效减少感知数据在传感器节点之间的传输跳数,进而有利于降低传感器节点的通信开销。然而,由于UAV和WSNs节点的能量都是有限的,如果UAV在未完成数据收集任务前(在飞行或悬停过程中)能量耗尽,那么将会导致UAV坠毁事故的发生;同时,在能量被耗尽的情况下,传感器节点也会直接停止工作。因此,如何在完成数据收集任务的前提条件下,最大限度降低UAV和传感器节点的能量消耗成为一个亟待解决的问题。

针对上述问题,相关领域的学者进行了广泛的研究。为了提高UAV-WSNs的数据传输效率,文献[1]提出了一种基于空地协同的在线规划数据收集方案,该方案使用分布式联盟形成算法对WSNs进行分簇;为了避免传感器节点在上传数据的过程中发生冲突,文献[1]还提出了一种新的数据上传协议。在文献[1]所提方案中,WSNs分簇完全由传感器节点自身完成,需要增加额外的计算和通信开销,这些开销对于计算能力较弱且通信半径较短的传感器节点而言不容忽视。为了提高无线传感器网络的能量效率,文献[2]提出了一种基于模糊C均值的聚类算法,该算法以最小化簇内节点总能耗为目标选择簇头节点。然而,文献[2]所提出的聚类方案依赖于节点的分簇个数,若分簇个数选取不佳,将影响WSNs的分簇效果,且该算法易陷入局部最优解。文献[3]提出了一种Affinity Propagation聚类方案,并结合动态规划和遗传算法优化无人机的飞行轨迹,以实现最小化节点的最大信息年龄和平均信息年龄的目标。文献[4]研究了WSNs和UAV之间的能量平衡问题,并提出了两种WSNs聚类方法:面向WSNs的聚类方法和面向UAV的聚类方法。在面向WSNs的聚类方法中,簇成员节点产生的感知数据通过簇头节点向UAV转发,UAV通过访问所有簇头节点来完成数据收集任务;而在面向UAV的聚类方法中,簇成员节点产生的感知数据首先由簇头节转发至汇聚节点,UAV只需访问汇聚节点便能完成数据收集任务。然而,汇聚节点距离各个簇头节点较远,易造成簇头节点过早失效,影响网络寿命。

文献[5]对传感器节点的唤醒时间表和UAV的轨迹进行了联合优化,并使用逐次凸优化方法求解该优化问题。文献[6]以最大化传感器节点的最小剩余能量为目标,提出了一种基于Voronoi图的UAV路径规划算法,该算法在开始时将每个Voronoi图的顶点设置为UAV的悬停位置;然后,根据每个传感器节点的剩余能量对UAV的悬停位置进行调整。调整的原则是,剩余能量越低的节点其正上方某位置被确定为UAV的悬停位置的概率越大。最后,根据Voronoi图的边分布和UAV的悬停位置分布来确定UAV的飞行轨迹。然而,给定任何两个悬停位置,与直接将它们连接起来的线段相比,在Voronoi图上通过组合多条连接上述两个给定悬停位置的边而形成的路径很可能更长,因此,根据Voronoi图所确定的UAV飞行轨迹很可能不是最优轨迹。文献[7]将非正交多址技术集成到UAV-WSNs系统中,并通过联合优化UAV的飞行轨迹和传感器节点的发射功率来实现降低传感器节点总能耗的目标。文献[7]所提方案要求每个传感器节点都能够与UAV进行直接通信,这无疑会大大增加UAV的飞行距离,进而大幅增加UAV的飞行能耗。为了最小化UAV完成数据收集任务的总时间开销,文献[8]联合优化了UAV的飞行轨迹和数据收集轨迹,并首次提出了V形数据收集轨迹。然而,文献[8]提出的数据收集方案需要UAV依次采集每个传感器节点的数据,当网络规模较大时,UAV悬停和飞行的时间与能耗将会显著增加。

文献[9]以最小化UAV-WSNs的系统总能耗为目标,提出了一种基于指针网络和A*算法的数据收集方案,即Ptr-A*方案。在该方案中,指针网络被用于优化UAV的飞行轨迹,A*算法则被用于确定各个簇的簇头节点位置。然而,文献[9]并未给出具体的WSNs分簇方案,也未给出UAV的最优悬停位置。

虽然目前相关学者已提出了一些UAV-WSNs数据收集方案,但这些方案仍有较大的改进空间。为此,提出了一种新的UAV-WSNs数据收集方案,概而言之,本文的主要贡献如下:

(1)基于WSNs分簇优化与UAV飞行轨迹优化,提出了一种新的UAV-WSNs数据收集方案;

(2)通过有机融合密度峰值聚类方法和K-Means聚类方法来优化WSNs分簇;

(3)将指针网络和内点法相结合,通过先优化WSNs各分簇的UAV访问次序、再优化UAV在WSNs各分簇上空的悬停位置,来优化UAV的飞行轨迹;

(4)搭建了UAV-WSNs数据收集仿真实验环境,在真实数据集上进行了大量仿真实验,验证了本文所提方案的高效性。

1 系统模型

图1 UAV-WSNs系统架构模型Fig. 1 Architecture model of the UAV-WSNs system

1.1 通信模型

UAV-WSNs系统的通信方式有两类:一是传感器节点之间的通信;二是传感器节点与UAV之间的通信。传感器节点之间的通信采用IEEE 802.15.4标准的通信模型;UAV和传感器节点是空对地信道模型,信道的平均路径损耗表示为[10]:

(1)

(2)

式(1)中:μLos和μNLos分别表示视距链路和非视距链路中过度路径损耗的平均值。式(2)中:β为路径损耗指数,fc和c分别为载波频率和光速。PLos和PNLos分别为视距概率和非视距概率,表示为:

(3)

(4)

(5)

式中:B表示可用带宽,N0是噪声功率谱密度,PT是传感器节点的发射功率。

1.2 UAV的能耗模型

在每一轮数据收集过程中,UAV从基站出发,按照设定轨迹匀速飞到各个悬停点,并在各个悬停位置以悬停状态收集传感器节点产生的感知数据,最后将收集到的数据运回基站。离开地面后,UAV支持的状态模式有:飞行模式和悬停模式,其在每一轮数据收集过程中的能量消耗(Euav)包括:飞行能耗、悬停能耗和通信能耗,即:

Euav=Eflight+Ecom_hover,

(6)

式中:Eflight为UAV完成一轮数据采集任务所产生的飞行能耗,Ecom_hover为UAV完成一轮数据采集任务过程中所产生的通信能耗与悬停能耗之和。

Eflight又可进一步表示为:

Eflight=tflight(Pmove+Phover),

(7)

式中:tflight为UAV在一轮数据收集过程中的总飞行时间,Pmove和Phover分别为UAV飞行和悬停时的功率。Pmove和Phover具体表示如下[11]:

(8)

(9)

式(8)中:Pfull和Pidle分别为UAV全速移动和空闲状态时的功率,vuav为UAV的飞行速度,vmax为UAV的最大飞行速度;式(9)中:muav为UAV的质量,ruav和nuav分别为UAV螺旋桨的半径和数量,g和ρ分别为地球重力和空气密度。

式(6)中的Ecom_hover可具体表示为:

(10)

1.3 传感器节点的能耗模型

(11)

(12)

(13)

(14)

令Esn表示在一轮数据收集过程中WSNs中所有传感器节点产生的总通信开销,则Esn可分为以下三部分:传感器节点之间发送数据的能耗、传感器节点接收数据的能耗和簇头节点将数据转发到UAV的能耗,因此,Esn可表示为:

(15)

式中:

1.4 问题描述

所研究的问题可描述为:在上文所述模型下,如何最小化单轮数据收集过程中UAV和WSNs节点的总能耗。其中,“单轮数据收集过程”是指,UAV从基站出发,在WSNs上空收集完所有传感器节点在给定周期内产生的感知数据后,返回基站的过程。

由于UAV在数据收集时其信号覆盖范围有限,且无线传感器节点的通信半径也较短,因此,为了提高大规模UAV-WSNs的数据收集效率,需要对WSNs进行分簇,并对UAV在各簇之间的飞行轨迹进行优化。因此,将上述问题拆分为“WSNs分簇优化”和“UAV飞行轨迹优化”两个子问题,并针对这两个子问题提出了一种名为DPKM-PN(“Density Peak K-Means” combined with “Pointer Networks”)的数据收集方案,下文给出该方案的详细介绍。

2 DPKM-PN方案

DPKM-PN方案的主要思想是:首先,基于密度峰值聚类方法和K-Means聚类方法对WSNs进行分簇;然后,利用指针网络技术优化各个分簇的UAV访问次序;最后,利用Matlab中的fmincon函数对UAV在WSNs各分簇上空的悬停位置进行优化。各个分簇的访问次序也是各个悬停位置的访问次序,确定了UAV的悬停位置及其访问次序,也就确定了UAV的飞行轨迹。此后,UAV便可沿这一飞行轨迹进行数据收集。

2.1 WSNs分簇

步骤1:基于密度峰值聚类方法确定初始簇中心位置集合Cinit和分簇个数K。确定初始簇中心Cinit和分簇个数K时,需计算每个传感器节点的密度和最小高密度距离[13]。对于传感器节点Si(1≤i≤N),可根据式(16)和(17)计算其密度值ρi和最小高密度距离δi[13]:

(16)

(17)

式(16)中,

dSi_Sj为节点Si到节点Sj的距离,ε为距离阈值。

(18)

最后,对Ctemp进行筛选,筛选原则为Cinit内任意两点之间的距离应大于二倍的阈值ε,过滤掉部分不满足距离要求的节点后,剩下的节点组成的集合即为初始簇中心点集合Cinit。

步骤2:基于K-Means聚类算法对WSNs进行分簇。令

表示WSNs所有簇中心位置组成的集合。初始时,Ccenter为Cinit内所有传感器节点的对应位置所组成的集合。在分簇过程中,各传感器节点寻找并加入距离自身最近的簇中心位置所对应的簇,分簇的目标是使各成员节点与其对应簇中心点之间的距离平方和E最小化:

(19)

(20)

(21)

式(20)和(21)中:|Clusterj|为第j类分簇中传感器节点的个数,LocS.x为簇Clusterj中传感器节点S的横坐标,LocS.y为簇Clusterj中传感器节点S的纵坐标。

步骤3:根据簇中心位置集合Ccenter确定WSNs的簇头节点的集合CHead。具体方法是,将各分簇中距离簇中心位置最近的节点作为对应簇的簇头节点。K(1≤K≤N)个簇头节点组成的集合表示为

(22)

2.2 UAV飞行轨迹优化

(23)

s. t.

(24)

τ={τ0,τ1,…,τK} ,

(25)

(26)

上述问题为有约束优化问题,DPKM-PN方案采用Matlab中的fmincon函数来求解这一问题。fmincon使用内点法对有约束优化问题进行求解,具体函数定义为[15]:

[X,fval]=fmincon(L,x0,A,b,Aeq,beq,lb,ub,nonl),

式中:X是优化之后UAV悬停点的地面映射位置;fval为UAV的总飞行距离;L是目标函数;x0是1个2K维向量,向量值为UAV的初始悬停位置;A和b是线性不等式约束;Aeq和beq是线性等式约束;lb和ub为2个2K维向量,其向量值分别为UAV悬停位置坐标的下界和上界;nonl是非线性约束。在对UAV的悬停位置进行优化时,将式(23)设置为目标函数,约束条件式(24)为非线性约束,并将线性约束条件设置为空。其优化目标是,在UAV悬停顺序已经确定的情况下,在各个簇头节点的通信范围内,寻找最小化UAV单轮数据收集的总飞行距离的悬停点。

3 仿真实验

本节通过仿真实验对DPKM-PN方案与已有方案进行对比与分析。为了验证DPKM-PN方案的高效性和先进性,选择最近提出的Ptr-A*[9]方案作为对比对象。

3.1 参数设置

实验采用MATLAB R2018b作为仿真平台。实验场景设置为:WSNs部署区域大小为4 km×4 km;N个传感器节点在该区域内随机部署;传感器节点每隔1 h产生一次感知数据,每个感知数据的大小为64 bit;UAV每隔1个月进行一次数据收集。仿真实验的其他参数设置如表1所示。

表1 实验参数设置Tab. 1 Experimental parameter settings

3.2 实验结果分析

首先,测试了利用fmincon函数对UAV的悬停位置进行优化的收敛效果,其结果如图2所示。在图2中,纵坐标为UAV在单轮数据收集过程中的总飞行距离,横坐标为迭代次数。从图2可以看出,经过多次迭代后得到的曲线是收敛的。

图2 多次迭代过程中UAV飞行距离的变化Fig. 2 Changes of the UAV flight distance over multiple iterations

接着,通过仿真实验给出了DPKM-PN方案和Ptr-A*方案在WSNs分簇、UAV悬停位置和飞行轨迹等方面的对比情况。图3(a)和图3(b)分别展示了DPKM-PN方案和Ptr-A*方案下的WSNs分簇、UAV悬停位置和飞行轨迹。可以看出,DPKM-PN方案中各个分簇的簇头节点总体更靠近各个分簇的中心位置,这有利于节约WSNs各分簇内传感器节点向其对应簇头节点传输数据的通信开销。

图3 2种方案对应的WSNs分簇结果与UAV的飞行轨迹Fig. 3 WSNs clusters and UAV flight trajectories corresponding to the two schemes

最后,对DPKM-PN方案和Ptr-A*方案在数据收集的能效性方面进行了对比。图4和图5分别显示了经过若干次数据采集之后UAV-WSNs的单轮数据收集平均总能耗以及WSNs的平均总能耗。

图4 UAV-WSNs的单轮平均能耗Fig. 4 Average energy consumption of UAV-WSNs in a round

图5 WSNs的单轮平均能耗Fig. 5 Average energy consumption of WSNs in a round

图4和图5显示:在UAV-WSNs系统的单轮数据收集平均总能耗方面,DPKM-PN方案比Ptr-A*方案减少了6.3%;在WSNs的平均总能耗方面,DPKM-PN方案比Ptr-A*方案减少了7.9%。这说明,相对于Ptr-A*方案,DPKM-PN方案具有更好的能效性。

4 结论

在UAV-WSNs系统中,如何提高系统的数据收集效率是近年来人们的研究热点之一。为了解决该问题,本文提出了一种基于WSNs分簇与UAV飞行轨迹优化的数据收集方案DPKM-PN。该方案首先基于密度峰值聚类方法确定WSNs的初始簇中心位置,然后将初始簇中心位置作为算法输入,采用K-Means聚类方法通过多次迭代确定最终的簇中心位置集合并完成WSNs分簇;接着,DPKM-PN基于指针网络理论确定WSNs各分簇的UAV访问次序;最后,基于内点法利用Matlab的fmincon函数对UAV在各分簇上空的UAV悬停位置进行优化,进而完成对UAV飞行轨迹的优化。实验结果表明,与最近提出的Ptr-A*方案相比,DPKM-PN方案在WSNs的总平均能耗方面降低了7.9%,在UAV-WSNs系统的平均总能耗方面降低了6.3%,进一步提高了UAV-WSNs的数据收集效率。