面向物联网的深度Q网络无人机路径规划

张建行 康 凯 钱 骅 杨 淼③

①(中国科学院上海高等研究院 上海 201210)

②(中国科学院大学 北京 100049)

③(上海科技大学信息科学与技术学院 上海 201210)

物联网(Internet of Things, IoT)技术旨在构建万物互联的世界，现已在多个领域有了广泛的应用。大量的网络连接设备(可穿戴设备、智能设备、嵌入式传感器等)部署在健康、交通、能源、工业等各个领域，实现数据采集、检测、测量等用途。例如：将传感器安装在农场中用以火灾预警；
将传感器安装在灾难多发地或国家边境，用以搜寻、营救以及边境监控等[1]。然而，在一些特殊的应用场景中，如因地形地貌不适宜部署通信基础设施的偏远地区，物联网终端设备(即地面节点)只能通过无线多跳的方式将数据传回中心节点。这样势必会造成中心节点设备的能量消耗远高于边缘节点，从而减少整个网络的寿命[2]。同时这种传输方式的时延也无法得到保证。近几年来，无人机技术快速发展。凭借无人机的高机动性、低成本等优点，利用无人机收集地面物联网设备的信息并传回中心节点，是应对上述特殊环境中物联网通信问题的有效方法[3–5]。

使用无人机辅助物联网通信引入了新的挑战。由于无人机为能量受限的设备，如何规划无人机的飞行路径成为保障无人机辅助物联网通信服务质量(Quality of Service, QoS)的关键[3–5]。目前，许多工作聚焦于如何提升能量效率、最大化网络覆盖率、吞吐量等[6–11]。然而，在环境监测、灾难救援等场景中，QoS主要受限于无人机从地面节点收集的信息的时效性。基于优化吞吐量或延迟等指标设计的路径不能保证信息的时效性。比如，当传输延迟小时，如果吞吐量也比较小，说明数据很少能传输到中心节点，数据可能不具有时效性；
如果吞吐量较大，数据可能经历了长时间排队，也有可能不具有时效性[12]。

信息年龄(Age of Information, AoI)定义为目前接收到的、生成时间最晚的数据包的生成时间与当前时刻的时间差[13]。与传统的衡量指标相比，如吞吐量、延迟，AoI能更精确描述信息的时效性，因此AoI已在物联网中广泛地应用[14]。AoI的变化与地面节点的采样模式，即产生信息的间隔有关，为了降低AoI，无人机应在同样时间内更多访问信息产生间隔较小的节点。因此，传统方法如将问题建模成旅行商问题(the Travelling Salesman Problem,TSP)，设计一条最短路径并沿该路径依次访问所有设备的方法已不再适用[15–19]。Kaul等人[20]基于一个简单的排队论模型证明了最小化平均AoI的源节点采样速率与最大化吞吐量或最大化上行速率的最佳采样速率不同，这进一步证明文献[6–11]中提出的基于吞吐量等指标的路径规划算法不再适用于优化AoI的场景。同时，地面节点采样模式是不确定甚至未知的，比如温度传感器用于温度监测时会按照固定的采样频率采集温度信息，而用于火灾报警时，只有在温度高于设定的阈值时才会采集信息[21]。因此，无人机的路径规划应具备在线自动规划，以适应不同采样模式的能力。强化学习作为一种与环境交互并根据当前状态选择最优动作的方法，在解决此类问题上有天然的优越性。Zhou等人[21]在地面节点采样模式未知的情况下，使用深度强化学习提出了基于AoI的路径规划算法(AoI-based Trajectory Planning, ATP)最小化无人机收集信息的平均AoI。ATP算法将无人机飞行过程划分为多个相同长度的时隙，根据当前状态动态地决策下个时隙的飞行速度和方向。然而，其时隙设置约为1 s，即无人机需每隔1 s进行一次转向，这从能量消耗的角度来看是不合适的[6,22]。同时，其只考虑了位置对称的4个地面节点，在地面节点数增加且位置随机分布时的性能可能得不到保证。

本文针对现有无人机辅助物联网中路径规划存在的不足，研究无人机信息采集场景中的路径规划问题。由于物联网中地面节点的采样模式未知，传统路径规划方法不再适用。因此，本文首先通过把无人机信息收集过程建模成马尔可夫过程(Markov Decision Processes, MDP)，将路径规划问题转化为序列决策问题，即无人机根据当前状态决策下一个前往采集信息的节点。这样建模的好处为：无人机仅需从一个节点沿直线前往另一个节点后，才需一次转向前往下一个节点，可减少无人机的能量消耗。其次，本文提出基于深度Q网络(Deep Q-Network, DQN)框架[23]的路径规划算法。该算法将平均AoI和最大AoI的降低作为奖励项，无人机通过优化决策来降低平均AoI和最大AoI，同时保障收集信息的时效性和服务各节点的公平性。与传统方法相比，DQN更关注长期收益(奖励累加和)最大化，即如何使无人机整个飞行期间内收集的信息平均AoI最低。本文通过仿真验证本算法无人机收集信息的平均AoI，并与随机算法、基于最大AoI的贪心法、最短路径算法以及ATP算法进行了性能对比。

本文的结构如下：第1节介绍了无人机辅助物联网通信中，路径规划的研究现状与当前存在的问题；
第2节提出了本文应用场景的系统模型与无人机路径规划的问题构造；
第3节详细介绍了基于深度Q网络的飞行路径规划的算法；
第4节，通过仿真，对比和展示了本算法的性能提升；
最后，第5节对全文进行了总结。

2.1 系统模型

本文的研究面向偏远山区、农场、军事战场、灾害救援等场景。在一个大小为L×L的区域中，存在M个用来收集信息或监控的地面节点，这些节点由于基础通信设施匮乏或已损坏无法与中心控制节点进行通信。本文派遣一架无人机以固定高度在该区域内飞行，当无人机经过地面节点上空，会与地面节点之间存在高质量的直视径信道，建立连接、收集地面节点发送的数据包并传回中心控制节点。当无人机接收到一个地面节点发送的数据包时，立刻根据包内的时间戳更新AoI状态信息，并前往下一节点。

其中，//·//2为L2范数，v为无人机匀速飞行速度。在时刻T0=0，无人机由第1个地面节点的位置d1飞入该区域，并根据当前状态决策下个要前往采集信息的节点。K={1, 2, ···, K}用来表示无人机在最大飞行时间Tmax内做的决策集合，即访问物联网中节点的次数。Ik∈M为无人机第k次决策所选择的前往采集信息的节点编号，其中k∈K。Tk和lk=[lk,x,lk,y]分别用来表示无人机执行第k次决策后的时刻和位置。矩阵A ∈RK×M为记录AoI变化的矩阵，Ak,m为无人机执行第k次决策后，第m个节点上传的信息的AoI。无人机执行第k次决策前往Ik节点采集信息，并如式(2)更新AoI状态信息。

2.2 问题构造

本文希望降低无人机单次航行过程中收集信息的平均AoI，因此，无人机飞行路径规划目标为

其中，M为节点个数、K为无人机在Tmax时间内所作决策的次数。由于物联网中地面节点的信息采样模式，即tm未知，传统的优化方法将不再适用。因此本文将该问题重新建模为MDP，使用DQN在环境中学习得到一个可用于无人机路径规划的策略，即根据当前状态选择下个前往收集信息节点的策略。相比与传统方法，如贪心算法，即前往当前AoI最大的节点，DQN更关注长期收益(奖励累加和)最大化，即如何使无人机在整个飞行期间内收集信息的平均AoI最低。

本节展示了将问题转换为马尔可夫过程的流程和本文提出的无人机路径规划算法。

3.1 MDP构造

MDP为序列决策的经典形式化表达，是一种通过交互式学习实现目标的理论框架。本小节通过把无人机路径规划构造为MDP，并将问题式(3)转换为决策问题。MDP由一个4元组来表示，即M= (S,A,P,R)。

其中S为表示整个过程中所有状态s的集合；
A为 所有动作a的集合；
P为状态转移模型，即无人机在状态s下，执行一次动作a后，转移至下一个状态s′的 模型；
R为执行动作可获得奖励的集合。无人机的状态空间、动作空间和奖励定义如下：

(1) 状态设置：无人机在做第k次决策前，观察到的状态定义为

其中，Ak-1,:为矩阵A的第k–1行。该状态是对当前无人机的悬停位置，所有节点上传信息AoI的联合观察。

(2) 动作设置：无人机根据状态sk选择ak=Ik，其中Ik为选择的下个将要访问的地面节点的标号，ak∈A。执行该动作后，无人机位置更新为

一个地区的环境容量决定了在相应的旅游资源中能够承受的游客量，超过了环境容量的旅游发展，则会导致各种突发状况的发生，造成环境的严重破坏，降低地区的旅游资源价值，对此，需要旅游业在发展的过程中，能够把握好旅游资源的环境容量问题，防止因为过度旅游造成的环境破坏和损失。

(3) 奖励设置：无人机执行第k次决策后，会如式(2)更新AoI状态信息，奖励为

是此时所有接收到信息的AoI的最大值和平均值之和的反函数，其中λ为辅助DQN收敛的超参数。强化学习对奖励的大小十分敏感，奖励设置不合理会使DQN无法收敛或陷入局部最优，因此引入超参λ辅助算法收敛。在DQN学习的过程中，智能体(无人机)会选择未来的奖励加权和的期望值最大的动作，即每次执行完决策的动作后，地面节点上传信息的AoI的平均值和最大值越大，所得到的奖励也就越小。因此无人机会通过不断优化决策ak来降低平均AoI。将AoI最大值引入奖励项可以使无人机在降低平均AoI的同时，防止来自某一个地面节点的信息AoI过高，以保证服务各地面节点的公平性。

3.2 算法介绍

本文针对无人机辅助物联网的应用场景，提出一种基于深度Q网络框架的无人机路径规划算法，来保证无人机收集数据的时效性。本算法中，无人机通过DQN来找出最优的策略，即对于每一个状态sk，找出使未来奖励加权期望值R最大的动作，奖励加权期望值R表达式为

其中，γ为奖励打折率。本文使用π(a|s)=Pr(a=ak|s=sk)表示无人机选择动作的策略。状态价值函数Vπ(s)为从当前状态s开始，无人机按照策略π选取动作所获得的加权奖励的期望值，用来衡量策略π的好坏，如

其中，s′表示下一个状态，P r(s′,r|s,a)为状态转移模型。由状态价值函数Vπ(s)可写出动作-状态价值函数Qπ(s,a)，如

为无人机在当前状态s下，执行动作a，然后按照策略π前进所获得的回报的概率期望值。根据当前状态选择最优的动作a∗=arg maxaQπ(s,a)得出。在按上述方法求解最优动作时，需用的状态转移模型P，然而，在本场景中，状态转移模型P未知，需按照迭代的方式进行Qπ(s,a)的估计，迭代公式为

其中，α为学习速率。同时，由于本文场景的状态空间和动作空间巨大，传统的建立Q表记录每个状态对应动作的Q值的方法不再适用，因此本文依据DQN框架，使用神经网络拟合状态价值函数Qπ(s,a)。神经网络的输入为状态信息s和 动作a，输出为该动作的Q值。在神经网络训练完成以后，只需存储神经网络的参数即可，根据神经网络的输出选择Q值最大的动作，可节约大量存储空间。

本文提出的基于DQN的路径规划算法框图如图1所示。算法具体描述为：首先创建两个结构相同的神经网络，现实网络Qr和目标网络Qt。两个网络结构相同，均包含1个输入层，两个分别含有M+ 2和32个神经元的全连接层，以及1个输出层。其中，每个全连接层后加入ReLU激活函数层。首先，随机初始化Qr的参数θr，并令Qt的参数θr=θt。无人机根据当前观察到的状态s， 以ε的概率随机选取动作(ε会随着递减因子µ经过一定步长以后递减至0)，否则选取由Qr计算出的Q值最大的动作。无人机执行动作以后，观察下一个状态s′和奖励r，并将整个决策过程(s,a,r,s′)存储在经验池D中，当无人机达到终止状态则开始下一个回合。当经验池存储满以后，无人机每做一次决策，会从经验池中随机抽取|B|个 样本组成训练集B用于更新网络的参数。更新方式为最小化贝尔曼误差函数，

其中，y为目标网络Qt对现实网络Qr的估计。本文使用随机梯度下降的方式，即以θ ←θ −α∇θL(θ)形式进行参数更新，其中α为学习速率，每隔固定步长w后 ，令θr=θt。图1展示了本文提出的基于DQN的无人机路径规划算法完整流程。表1为基于DQN的无人机路径规划算法。

表1 基于DQN的无人机路径规划算法

图1 DQN算法框图

本节通过仿真验证了基于DQN的无人机路径规划算法的性能，并与其他算法进行了对比。本文共设置两种仿真场景：第1种为所有传感器均以相同采样间隔进行采样，如温度传感器用于温度监测时，会以固定的采样频率采集温度信息；
第2种为所有传感器以不同的采样间隔进行采样，如温度传感器用于火灾预警时，只有在温度高于设定的阈值时才会采集信息[21,24]。每个仿真场景均经过100次蒙特卡罗模拟验证DQN算法的鲁棒性。物联网网络参数设置为：地面节点个数为M=15，区域长度为L=200 m，无人机飞行速度为v=30 m/s，最大航行时间为Tmax=3600 s。在仿真场景1中：每次蒙特卡罗模拟时，所有地面节点均会随机赋予一个新的地理位置坐标dm=[xm, ym]，其中，0≤xm, ym≤L，采样间隔均设置为10 s。在仿真场景2中：每次蒙特卡罗模拟时，所有地面节点会随机赋予一个新的地理位置坐标和新的采样间隔tm，其中0≤tm≤15，每个传感器采样间隔均不相同。算法参数选择DQN原论文中推荐的参数，具体设置如表2所示[23]。

表2 DQN算法参数

本文选取无人机一个飞行周期内的所有地面节点的平均AoI作为衡量不同算法性能的指标。在仿真实验中，本文将DQN算法与另外4种算法在两种仿真场景下进行了对比。第1种为随机算法，即随机选取动作，随机算法被广泛用于作为基准算法，用来评估目标算法性能是否有提升。第2种为基于最大AoI的贪心法，即无人机前往当前时刻AoI最大的地面节点采集信息，贪心法复杂度较低，但在大多数情况下仅略优于随机算法。第3种为基于最短路径的算法，即无人机沿着一条包含所有节点的最短闭合路径飞行，循环往复，直到最大飞行时间(因该算法为确定性算法，其AoI不随训练回合变化)，本文与该算法对比以证明基于最短路径的算法在本文场景中已不适用。最后一种对比算法为文献[21]中提出的ATP算法。

图2(a)和图2(b)分别展示了DQN算法与另外4种算法在两种仿真场景中的对比结果，其中横轴表示训练回合(无人机的一个飞行周期)，纵轴表示该训练回合内的地面节点平均AoI。可以看到，经过训练，DQN算法中地面节点每个回合内的平均AoI中远低于随机算法、贪心算法和最短路径算法，说明基于深度强化学习的、启发式无人机路径规划算法在本文仿真场景中更加适用。同时，DQN算法的性能略优于ATP算法，这种优势来源于：ATP算法为基于价值函数的深度强化学习算法，但其在对无人机航行过程进行建模时设计的动作空间为连续空间，这使得其算法复杂度异常之高。具体解释可观察本文算法的第(5)步，

图2 不同算法在两种仿真场景下的性能对比

其中，Qr(s,a;θr)为对应的深度网络，ATP算法设计的无人机动作空间为连续空间，即动作a的取值为一个连续空间，这使得求解式(12)的复杂度过高，同时在训练过程中无人机每走一步需求解一次式(12)，使得整个算法的复杂度异常之高，进而难以进行超参数的调优。本文把无人机的动作空间设计为离散空间，如上文MDP构造中动作设置所示，可选动作的个数为节点的个数，大大降低了求解式(12)的复杂度，进而降低了整个算法的复杂度。

表3列举了无人机在飞行过程中地面节点的平均AoI。本文选取DQN算法训练稳定后所有回合的平均AoI的均值评价DQN算法的性能。经过训练，DQN算法中地面节点在两个仿真场景下的平均AoI分别可降到7.7 s和8.8 s，说明本文提出的基于DQN的路径规划算法在地面节点采样模式未知的情况下可以有效降低地面节点的平均AoI。同时，因仿真场景2中的随机性更大，DQN算法在仿真场景中1中性能略优于仿真场景2。与随机算法、贪心算法、最短路径算法和ATP算法相比，在仿真场景1中，DQN算法把平均AoI分别降低了81.9%,67.2%, 56.7%和39.2%；
在仿真场景2中，DQN算法把平均AoI分别降低了80.5%, 68.1%, 54.4%和38.9%。

表3 不同算法的AoI性能对比(s)

图3(a)和图3(b)展示了地面各个节点在两种仿真场景中不同算法下的平均AoI。可以看出，本文提出的基于DQN的路径规划算法不仅性能提升显著，并且不同节点之间的平均AoI差异较小。因为该算法在设计奖励项时将当前时刻的地面节点中的最大AoI也考虑进去，作为惩罚项，因此本文算法可有效保证无人机服务各节点之间的公平性。

图3 不同地面节点的平均AoI对比

同时，因仿真环境2更具有一般性，本文实验研究了在仿真环境2中不同参数对基于DQN的无人机路径规划算法性能的影响。图4(a)展示了无人机速度为30 m/s时，地面节点个数对DQN算法的影响。同时，本文选取了DQN算法在节点个数分别为5, 10, 15, 20时的训练曲线展示在图4(b)中，其对应的地面节点的平均AoI分别为3.7 s, 5.9 s, 8.8 s,15.3 s。可以看到，随着节点个数的增加，地面节点的平均AoI也在增加，且增加的越来越多。当节点数过多时，由于可选择动作的增加，算法的稳定性也随之降低，如图4(b)所示，节点个数为20的训练曲线波动明显大于节点个数为5的训练曲线。

图4 节点个数对DQN算法性能的影响

图5(a)展示了无人机飞行速度对地面节点平均AoI的影响。图5(b)展示了DQN算法在M=15时，无人机飞行速度分别为30 m/s, 25 m/s, 20 m/s,15 m/s时的训练曲线，其对应的地面节点的AoI分别为8.8 s, 11.9 s, 14.1 s, 17.7 s。可以看到，随着无人机飞行速度的增加，地面节点的平均AoI也在降低，并且两者近似呈线性关系，例如当无人机飞行速度降低一半时(如从30 m/s降到15 m/s)，地面节点的AoI升高了约1倍(从8.8 s升至17.7 s)。

图5 无人机飞行速度对DQN算法性能的影响

本节展示了DQN算法在无人机辅助物联网收集数据中保障数据实时性的性能，并分别与随机算法、贪心算法、最短路径算法和ATP算法在无人机单次航行周期内收集数据的平均AoI的对比，结果显示，本文提出的DQN算法不仅能有效降低收集数据的AoI，并能有效保证无人机服务各地面节点的公平性。

随着无人机技术的快速发展，将无人机应用到物联网中辅助收集数据扩展了物联网的应用范围，实现了在通信基础设施匮乏或损坏场景中的通信。本文针对现有路径规划算法无法保证收集数据的实时性这一问题，提出一种基于DQN的无人机路径规划算法来收集地面节点产生的信息。该算法符合无人机的飞行模式，可以实现最小化无人机收集信息的平均AoI，并将最大AoI的降低引入DQN算法中的奖励项，可有效保证无人机服务地面节点的公平性。仿真结果表明，经与随机算法、贪心算法、最短路径算法和ATP算法对比，DQN算法把平均AoI分别降低了约81%, 67%, 56%和39%，性能提升显著，有效保证了无人机数据搜集的时效性。

猜你喜欢 状态节点规划 我们的规划与设计，正从新出发！房地产导刊(2021年6期)2021-07-22概念格的一种并行构造算法河南科技学院学报(自然科学版)(2020年2期)2020-05-22结合概率路由的机会网络自私节点检测算法小型微型计算机系统(2020年5期)2020-05-14采用贪婪启发式的异构WSNs 部分覆盖算法*火力与指挥控制(2020年1期)2020-03-27状态联想小学生作文(低年级适用)(2019年5期)2019-07-26Crosstalk between gut microbiota and antidiabetic drug actionWorld Journal of Diabetes(2019年3期)2019-04-16规划·样本领导决策信息(2018年16期)2018-09-27生命的另一种状态读友·少年文学(清雅版)(2018年12期)2018-04-04规划引领把握未来领导决策信息(2018年50期)2018-02-22快递业十三五规划发布商周刊(2017年5期)2017-08-22

推荐访问:无人机 联网 路径