基于块坐标下降算法的空地无人平台轨迹联合优化

李志坚,赵文栋,刘存涛

(陆军工程大学,江苏 南京 210007)

1 引言

1.1 传感器网络数据采集

目前,物联网技术的不断发展促使无线传感器网络的部署逐步成为现实。其中,小型低功耗传感器设备通常由其自身携带的电池进行供电,可用能量有限。当其部署在室外环境中执行诸如环境监测、信息感知等任务时,一旦电量耗尽，很难得到及时有效的能源补充。在对传感器数据进行采集时,实现传感器设备的节能数据传输是延长传感器网络工作寿命的有效手段之一。

近年来,小型无人机凭借其成本低，机动性强及操作灵活等优点,在无线传感网络数据采集方面得到了广泛应用。 数据采集过程中,传感器可采用休眠-唤醒机制,由无人机按需移动至传感器附近将其唤醒。然后，利用良好的视距通信链路与传感器进行通信,使得传感器设备能够以较小的发射功率获得较高的通信速率,从而达到节能数据传输的目的。为此,无人机辅助数据采集时通常需要考虑无人机与传感器之间的唤醒调度问题。此外,考虑小型无人机通常由机载电池供电,可用能量也是受限的,对无人机轨迹进行优化以节省飞行能耗,进而提高无人机的能耗效率,也是无人机辅助数据采集时通常需要考虑的问题。

针对数据采集过程中的无人机-传感器唤醒调度及无人机轨迹优化问题,已有研究从不同的目标出发开展了相关研究。静态无人机辅助传感器数据采集将无人机作为空中准静态基站,从一定高度辅助给定区域内传感器的数据传输,主要研究无人机的部署/布局优化方法,没有考虑如何更好地发挥无人机的机动性优势。文献[9]对物联网常用的圆形轨迹下无人机数据采集系统的性能进行了分析,找出了两者之间实现不同Pareto最优的传感器节点发射功率。文献[10]对无人机能耗进行了精确建模和优化。文献[11]在满足每个传感器的通信吞吐量需求的条件下，使无人机总能耗最小化,但没有考虑任务时间的影响以及传感器的能耗约束。文献[12]以传感器网络吞吐量最大化为优化目标,对无人机-传感器的唤醒调度和无人机轨迹进行了联合优化。文献[13]以最小化传感器向无人机传输数据的能耗为优化目标,提出了无人机轨迹和无人机-传感器的唤醒调度的联合设计方案。其中,传感器的节能传输是通过让无人机在采集数据时尽可能靠近传感器飞行以充分利用视距信道来实现的。文献[14]以无人机作为数据采集器,设计了一种高效节能和快速数据采集(EFDC)方案,用于丘陵地区的无人机辅助传感器网络的数据采集。然后,应用改进的禁忌搜索算法优化无人机的位置,利用导出的数据采集位置开发了旅行商问题,并采用改进的遗传算法对其进行求解。文献[15]在一对多数据采集方案下,联合优化了无人机轨迹和通信资源分配,提高了传感器网络的数据采集效率。文献[16]研究了一种固定翼无人机在林火监测中的数据采集任务规划，将问题建模为一个带邻域的Dubins旅行商问题(DTSPN)。

1.2 轨迹优化算法

当前路径优化算法可分为以生物和自然规律为启发的智能算法和以(非)凸优化范畴为主的传统算法。

文献[17]中基于凸优化理论,提出了一种有人/无人机协作系统的轨迹优化算法，分别以系统能耗最小化和无人机到达预定位置的时间最短为优化目标,对优化模型进行了逼近和凸化,最后，利用凸优化算法对该问题进行求解。文献[18]研究了U2U(UAV-to-UAV)的通信系统,通过优化无人机路径使信息传输时间最小化，提出了一种基于精确惩罚法和逐次凸逼近的路径规划算法。文献[19]提出了用于无人机航迹规划的改进人工蜂群算法。该算法参数少,收敛速度快,能够使无人机避免实时环境下的动态威胁。文献[20]提出了改进的遗传算法(IGA)和基于蚁群优化算法的粒子群算法(PSO-ACO)来解决无人机TSP问题。文献[21]研究无人机辅助的蜂窝网络,由无人机充当飞行中继将信息在蜂窝之间进行传递,随后针对接入点选择子问题具有NP难的特点,提出了一种基于博弈论的分布式算法。同时为了实现最优信道状态,采用基于深度强化学习(DRL)的方法求解无人机路径优化子问题。

上述研究很少考虑偏僻节点的存在对无人机能耗效率以及传感器网络整体寿命的影响。其中,本文中的偏僻节点主要指具有以下特征的节点:一是距离传感器网络中心较远,处于相对孤立的边缘位置,与无人机起点和终点之间连线的距离较远,如图1中的偏僻节点Ⅰ;二是处于障碍物较多的环境中,与无人机之间的通信信道较差,无法完成数据采集,如图1中的偏僻节点Ⅱ。需要注意的是,当传感器距离传感器网络中心较远,但与无人机起点和终点之间连线的距离较近时,通常不认为是偏僻节点。在本文中考虑第一种情况的偏僻节点。相比于访问其他节点而言,无人机对偏僻节点进行抵近访问时需要飞行更多的路程,从而导致能耗效率的降低和任务完成时间的增加。此外,当无人机可用能量受限或数据采集任务的时间比较紧急时,可能出现无法对偏僻节点进行抵近访问的情况,此时偏僻节点需要以较大的发射功率发送数据，才能确保数据的有效传输,从而会消耗更多的能量，导致传感器网络的使用寿命降低。

图1 两类偏僻节点

为此,本文研究了考虑偏僻节点影响的高效数据采集问题,提出了地面移动基站与无人机协同的数据采集方法。其中,地面移动基站指的是可按需临时部署的小型基站。在考虑无人机可用能量、任务完成时间以及传感器可用能量等多种约束条件的基础上,以最小化传感器的最大能耗为优化目标,对无人机-传感器的唤醒调度、无人机的轨迹以及地面移动基站的部署位置进行了联合优化。为了解决该问题,提出了基于迭代优化的问题求解框架,用块坐标下降(BCD)技术以迭代的方式交替优化子问题。最后,仿真结果表明，与基准方案相比,本文算法所提出的方案实现了显著的性能提升。

2 系统模型及问题形式化

2.1 系统模型

如图2所示,本文考虑了一个基于可部署基站和无人机的协同数据采集场景。其中,一架无人机作为可移动数据收集设备负责在给定的任务执行时间内收集位于地面的传感器U={1,2,…,|U|}的数据。其中，偏僻节点M={1,2,…,|M|}通过可部署基站将数据间接发送给无人机。将数据直接传输给无人机的传感器集合表示为K={1,2,…,|K|},U=K∪M,K∪M=Ø。传感器的坐标表示为=[,]。可部署基站的坐标表示为=[,]。假设所有传感器位置信息以及需要上传的数据量都是已知的,并且无人机的飞行高度是固定的。

图2 空地协同数据采集

假设从传感器和可部署基站到UAV的信道是视距(LoS)信道。在任意时隙中，传感器和可部署基站到UAV的信道增益为：

(1)

(2)

其中,表示距离为1 m时的参考信道功率增益,≥2为路径损耗指数。传感器在其被唤醒的传输时隙中以恒定的功率向无人机传输数据,在未被唤醒传输时为了节能而保持静默状态。用[]表示在时隙时地面设备被无人机唤醒的二进制变量,如果[]=1,则表示传感器在第个时隙进行数据传输，否则保持静默。从而，可以得到无人机-传感器唤醒调度约束为:

(3)

[]∈{0,1},∀,∈K∪BS

(4)

在任意时隙n,如果传感器k被无人机唤醒,则传感器k对应的传输速率[](bps/Hz)为

(5)

其中，σ表示噪声功率。同理，可部署基站与无人机之间的传输速率为

(6)

偏僻节点与可部署基站之间的传输速率为

(7)

传感器节点的能耗为:

(8)

(9)

2.2 问题形式化

本文的目标是在完成数据采集任务的约束条件下联合优化无人机轨迹、无人机-传感器的唤醒调度和可部署基站的部署位置,最小化所有传感器的最大能耗。令={[],∀},=,={[],∀,∈K∪BS}。那么，优化问题可表示为：

(P1):min,,,

s.t≤, ∀∈K

(10)

E≤η, ∀m∈M

(10b)

(10)

(10d)

[]∈{0,1}, ∀∈K∪BS,n

(10)

‖[]-[-1]‖≤, ∀≥2

(10f)

[1]=

(10g)

[]=

(10h)

约束(10a)、(10b)确保每个传感器的能耗不超过,为松弛变量，表示所有传感器能耗中的最大能耗。约束(10c)确保可靠地收集到每个传感器的目标数据量。约束(10f)、(10g)、(10h)分别对应无人机的机动性约束和初始/最终位置约束。

3 算法设计

3.1 偏僻节点筛选算法

首先将对无人机飞行时间影响最大的传感器节点筛选出来作为偏僻节点处理。筛选步骤如算法1所示:首先,记传感器到无人机起点和终点所连直线的距离为0,=‖-‖,将满足0,≥threshold的节点筛选出来放入集合中;然后，通过比较算法,再次筛选出对整个任务执行时间的影响超过阈值的传感器节点。在该场景下，选择导致无人机飞行总时间波动较大的传感器节点。假设传感器的数据量相同,传输功率相同。无人机飞行至传感器附近悬停，然后进行数据采集。将无人机开始对传感器进行数据采集的时刻表示为,为了保证传感器能耗均衡可以得到约束:‖()-‖≤，给定无人机最大飞行速度,且无人机匀速飞行时,飞行时间最小化问题可以转化为无人机飞行距离最小化问题：

(11)

显然约束和目标函数关于都是凸的,因此该问题可以用标准的凸优化技术来解决。最后，将不考虑预筛选的偏僻节点而得到的最短飞行路径,与全部传感器的最短飞行路径进行对比,筛选出影响超出阈值的传感器,这些传感器即为偏僻节点。

算法1 偏僻节点筛选算法 1: 初始化系统参数,设置筛选阈值为threshold1;2: 求解TSP问题,得到访问顺序;3: 预筛选‖Q0-wu‖≥threshold1,u→G;4: G→g,-g→G;5: 代入集合G,求解(P);6: 比较无人机飞行距离,得到偏僻节点集合。

3.2 联合优化算法

在(P1)中,由于存在式(10a)(10c)中的非凸约束和(10e)中的整数约束,问题(P1)是一个混合整数非凸优化问题,一般情况下很难得到最优解。因此,首先将(P1)中的整数变量放松为连续变量。由于松弛问题相对于、、不是联合凸的,采用块坐标下降技术交替求解、、。

1)优化唤醒调度

首先,对于任意给定的轨迹和基站部署位置、,可以通过求解以下标准线性规划(LP)问题得到整数松弛无人机-传感器的唤醒调度的解。

(12)

目标函数和约束都为线性函数,(2)是标准凸优化问题。

2)优化无人机轨迹

另一方面,对于任何给定的基站部署位置和无人机-传感器的唤醒调度、,无人机轨迹优化原则是最大化所有传感器的通信吞吐量的加权最小值,其中，权重与成反比。此时,传感器的能耗是一定的,比值越大,表明能量利用率越高。反之,能量利用率越高,表明传感器可以利用更小的能耗完成数据传输,从而达到降低传感器能耗的目的。该问题可以表述为

(13)

由于式(13)中的非凸约束,(P3)是一个非凸优化问题。然而,基于凸逼近算法可以得到一个有效的近似解,并保证至少收敛到一个局部最优解。其主要思想是在每次迭代时，不断地最大化(P3)的下界。设={[]∀}表示给定的第次迭代的无人机飞行轨迹。通过应用一阶泰勒展开,得到式(5)中[]下界为

(14)

其中

(15)

(16)

然后，可以通过求解以下问题来优化无人机的轨迹:

(17)

3)优化可部署基站部署位置

给定无人机轨迹、无人机-传感器的唤醒调度、以及通过优化得到的传感器能耗,在保证偏僻节点的能耗小于等于其他传感器能耗的前提下,优化临时基站的部署位置,使无人机和基站之间的吞吐量最大化：

(18)

[][]≥,

(19)

同理对式(19)应用一阶泰勒展开得到传输速率的下界。因此(P5)也可以转化为一个凸优化问题。

4)块坐标下降算法

采用块坐标下降法(也称交替优化法)对(P1)进行求解。算法的详细内容在算法2中进行了总结。

算法2 求解(P1)的块坐标下降算法 1: 初始化系统参数,筛选偏僻节点,设置迭代精度为tol;2: 初始化W0,计算初始无人机轨迹Q0, r←0;3: 更新迭代次数r=r+1;4: 将Wr、Qr代入(P2)得到Ar+1;5: 将Ar+1、Qr和Wr代入式(P4),获得Qr+1;6: 将Ar+1、Qr+1和Wr代入式(P5),得到Wr+1;7: 直到满足收敛条件。

3.3 收敛性分析

值得指出的是,在经典的块坐标下降法中,为了保证收敛性,需要在每次迭代中精确地以最优的方式求解更新子问题。而在本例中,对于轨迹优化问题(P3)只最优地求解它的近似问题(P4)。因此,不能直接应用经典坐标下降法的收敛性分析,需要证明算法2的收敛性。

首先,在算法2的步骤4中,由给定的和得到(P2)的最优解,因此，得到下面的不等式：

(,,)≥(+1,,)

(20)

其中，(,,)在(P1)前定义。

然后给定+1,,经过算法2的步骤5处理得到以下结果:

(21)

其中，(a)成立,因为式(13)的一阶泰勒展开式在给定的局部点处是紧密的,这意味着(P4)在处与(P3)的目标值相同;(b)成立,因为在给定、+1的算法1的步骤5中,+1为(P4)的最优解;(c)成立,因为问题(P4)的目标值是原问题(P3)在+1的目标值的下界。由式(20)中的不等式可知,虽然只解决了一个近似优化问题(P4)来获得无人机轨迹,但(P3)的目标值在每次迭代后仍然不增加，并且(P1)的目标值为一个有限值的下界。

最后,对于给定的+1、+1代入算法2的步骤6中，得

(,,)≥(+1,+1,+1)≥

(22)

因此，关于,,的函数(,,)是收敛的。

4 仿真分析

在本节中,为了验证本文提出方案和算法的有效性,提供数值例子来证明所提算法的有效性。除非另有说明,表1中列出的参数将被用于后续的数值结果。其他相关参数将单独描述。假设所有传感器分布在1.6 km×1.6 km的矩形区域内,设置无人机出发点为=[-800,0],目的点为=[800,0],单位为m。初始轨迹设置为直线飞行轨迹。

表1 仿真参数

为验证本文所提出算法的性能,与以下四种算法进行对比：1)静态数据采集方案,其中，无人机部署在所有传感器和可部署基站的几何中心；2)最短飞行距离基准方案,该算法中无人机在最短的飞行路径匀速移动；3)最小悬停时间基准方案,该算法中无人机只有在悬停时进行数据采集,采集完当前传感器数据后，以最大速度向下一传感器或可部署基站移动；4)无基站辅助方案,该算法中只对无人机轨迹和唤醒调度进行联合优化,没有考虑基站辅助。

从图3可以看出,在没有基站辅助的情况下，无人机需要飞到距离比较近的位置去收集信息。此时，由于无人机的飞行时间有限,无人机与其他传感器的距离变大,因此，在传感器传输功率一定的情况下,需要花费更多的时间来传输数据,进而消耗更多的能量。而有可部署基站辅助时，无人机不需要飞行至距离很近的位置,此时，无人机与其他节点的距离就会变小,同理，此时传感器的能耗就会降低。因此，在时间受限的条件下,有可部署基站辅助时，无人机与传感器之间的平均距离比没有可部署基站辅助时要小,即传感器消耗的传输能耗小。

图3 T=40 s时无人机的飞行轨迹对比

图4显示了传感器在=40 s时的无人机-传感器唤醒调度时间表,在这里我们可以观察到，传感器在大部分时间都处于未唤醒(睡眠)状态,只有当无人机飞行至足够接近它们时，才会被唤醒(传输)，而且无人机对可部署基站的唤醒时间明显大于其他传感器,这是因为算法并没有考虑可部署基站的能耗,因此，无人机不需要飞行至距离可部署基站附近进行数据采集,由于传输距离远，所以传输相同数据量时花费的时间就多。

图4 T=40 s时的无人机-传感器(基站)的唤醒调度

图5给出了不同任务执行时间下，无人机的飞行轨迹以及基站的部署位置。从图中可以看出,任务执行时间越长，无人机就会飞到距离传感器更近的位置去收集数据。因为算法是使传感器的最大能耗最小化,所以，在无人机与其他传感器传输距离越近时,可部署基站的部署位置同样会距离偏僻节点越近。由于可部署基站不需要考虑能耗问题,无人机不需要飞行至可部署基站附近进行数据采集,因此节省了飞行时间，可飞往其他传感器节点。

图5 无人机飞行轨迹以及基站位置与T的关系

图6比较了在不同任务周期时,传感器节点的最大能耗。从图中可以看出,本文所提出的方案优于基准方案。采用可部署基站辅助无人机进行数据采集时,无人机不需要用较长的时间飞行到偏僻节点的周围进行数据采集。此时,无人机有更多的时间飞行至距离传感器节点更近的位置进行数据采集,从而以固定功率传输数据的传感器所需要的通信时间减少,因此，传感器的能耗降低。

图6 Dk=10 m,不同T时传感器节点最大能耗

图7比较了不同数据量时传感器的最小-最大能耗。可以观察到,本文提出的设计优于其他基准方案,并且随着增加,性能增益更加明显。这是因为通过本文提出的方案,无人机可以更接近甚至停留在传感器的上方,因此，SN 可以用更短的传输时间、更高的速率传输数据,从而节省能源消耗。

图7 不同上传数据量时的传感器能耗(T=50 s)

图8 不同T时无人机能量效率

5 结束语

本文研究了一个可部署基站辅助无人机对传感器进行数据采集的场景，以传感器能耗最小为目标,构造了混合整数非线性规划问题,该问题可解耦松弛为若干个凸优化子问题。仿真结果表明,借助可部署基站可以极大地提高无人机的能效,降低传感器的能耗。通过扩展本文的结果,在未来的工作中还有许多研究方向可以进行：1)空中和地面移动基站共存的网络设计;2)基于高度和水平位置优化的无人机三维轨迹设计;3)考虑多地面移动基站辅助,针对多无人机和多用户场景进行节能联合轨迹设计。