物联网数据收集中无人机路径智能规划
2021年2月Journal on Communications February 2021 第42卷第2期通信学报V ol.42No.2物联网数据收集中无人机路径智能规划
付澍1,2，杨祥月1，张海君3，陈晨1，喻鹏4，简鑫1，刘敏1
（1. 重庆大学微电子与通信工程学院，重庆 400030；2. 重庆大学信息物理社会可信服务计算教育部重点实验室，重庆 400030；
3. 北京科技大学计算机与通信工程学院，北京 100083；
4. 北京邮电大学网络与交换技术国家重点实验室，北京 100876）
摘  要：为解决无人机在数据收集过程中的路径规划问题，将其分为全局路径规划和局部路径规划。针对全局路径规划，将其建模为一个定向问题，定向问题是背包问题和旅行商问题2种经典优化问题的组合。采用指针网络深度学习对该模型进行求解，并在无人机能量约束下得到其服务节点集合及服务顺序。针对局部路径规划，基于无人机接收到节点的参考信号强度，通过深度Q网络学习对无人机局部飞行路径进行规划，使无人机逼近节点位置并服务各节点。仿真结果表明，所提方案能够在无人机能量约束下有效提升其数据收集的收益。
关键词：无人机；数据收集；路径规划；指针网络；深度Q网络
中图分类号：TN92
文献标识码：A
DOI: 10.11959/j.issn.1000−436x.2021036
UAV path intelligent planning in IoT data collection
FU Shu1,2, YANG Xiangyue1, ZHANG Haijun3, CHEN Chen1, YU Peng4, JIAN Xin1, LIU Min1
1. School of Microelectronics and Communication Engineering, Chongqing University, Chongqing 400030, China
2. Key Laboratory of Dependable Service Computing in Cyber Physical Society of Ministry of Education, Chongqing University, Chongqing 400030, China
3. School of Computer & Communication Engineering, University of Science and Technology Beijing, Beijing 100083, China
4. State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China
Abstract: To solve the problem of path planning of UA V data collection, it was generally be divided into global path planning and local path planning. For global path planning, it was modeled as an orientation problem, which was a com-bination of two classical optimization problems, the knapsack problem and the traveling salesman problem. The pointer network of deep learning was used to solve the model to obtain the service node set and service order under the energy constraint of the UA V. In terms of the local path planning, the reference signal strength (RSS) of the sensor node received by UA V was employed to learn the local flight path of UA V by deep Q network, which enabled the UA V to approach and serve the nodes. Simulation results show that the proposed scheme can effectively improve the revenue of UA V data col-lection under the energy constraint of UA V.
Keywords: unmanned aerial vehicle, data collection, path planning, pointer network, deep Q network
1引言大主宰 起点
近年来，物联网产业的飞速发展，极大地推动了无线传感器网络（WSN, wireless sensor network）技术的应用，其承载的业务数据量呈几何式增长。WSN中存在大量的数据需要被收集，根据收集方式的不同，可将其分为2种类型，静态数据收集和移动数据收集。静态数据收集是指传感器网络中的
收稿日期：2020−08−26；修回日期：2020−11−20
通信作者：刘敏，**************
lol火男出装基金项目：国家自然科学基金资助项目（No.61701054）；中央高校基本科研业务费专项资金资助项目（No.2020CDJQY-A001, No.2020CDJGFWDZ014）
Foundation Items: The National Natural Science Foundation of China (No.61701054), The Fundamental Research Funds for the Central Universities (No.2020CDJQY-A001, No.2020CDJGFWDZ014)
第2期付澍等：物联网数据收集中无人机路径智能规划·125·
节点通过自组网，将自身采集的传感器数据经过多跳上传到数据中心[1]；移动数据收集是指在被监测环境中设置一个可移动的数据收集器进行数据收集。针对部署在地表交通困难的大规模无线传感器网络，无人机提供了一种有效的方式来对传感器设备移动式地进行数据辅助收集[2]。
无人机是我国人工智能产业体系的重点培育产品。与静态数据收集方法相比，基于无人机的移动数据收集可以显著降低数据传输的能耗，减少多跳间数据路由中存在的隐藏终端及其发送冲突问题带来的射频干扰，并有效延长网络的使用寿命。
无人机数据收集克服了地面数据采集的局限性，但仍然有一些关键的问题需要解决。具体而言，无人机数据收集包括网络节点部署、节点定位、锚点搜索、无人机路径规划、网络数据采集5个部分[3]。无人机最致命的缺点是续航时间短[4-6]，因此其能耗问题是系统稳定性的关键。近几年，关于无人机在数据收集的能耗研究中，无人机路径规划是一个开放性的研究课题，引起学术界的广泛关注。无人机路径规划是一个复杂的网络优化问题[7]，一般可分为全局路径规划和局部路径规划。
一般而言，无人机将在可用能量限制下，根据任务环境信息事先规划一条全局最优或次优路径，得到访问节点的访问顺序，再通过局部路径规划进行实时单个节点的搜索与逼近。近年来，无人机路径规划已经得到了广泛的研究。文献[3]把无人机路径规划问题建模成经典的旅行商问题，并执行快速路径规划（FPPWR, fast path planning with rule）。文献[8]利用马尔可夫链对单个无人机从远处传感器收集数据的移动过程进行建模，并模拟无人机运行过程中的不规则运动。文献[9]利用部分可观察的马尔可夫决策过程（POMDP, partially observable Markov decision process）对无人机路径进行规划。文献[10]基于Q学习算法对无人机的路径和避障等问题进行学习，并采用自适应随机探测的方法实现无人机的导航和避障。文献[11-14]基于深度强化学习（DRL, deep reinforcement learning）实现无模型的无人机路径规划。除了利用机器学习方法外，研究者还提出了很多启发式算法[15-17]来解决无人机路径规划问题。
定向问题[18]为节点选择和确定所选节点之间最短哈密顿路径的组合，可以看作背包问题和旅行商问
题2种经典问题的组合。本文将无人机数据收集过程的全局路径规划问题建模为定向问题。本文考虑的全局路径规划是指综合考虑无人机自身的能量约束、节点收益等，在指针网络深度学习架构下进行的路径规划。其中，背包问题的目标是在可用资源限制下，选择一部分节点并使之获得的收益最大化；旅行商问题的目标是试图使无人机服务所选节点的旅行时间或距离最小化。
文献[19]对定向问题最近的变化、解决方案及应用等进行了综述。近几年，关于求解定向问题的启发式方法很多，例如遗传算法[20]、动态规划法[21]、迭代局部搜索法[22]等。
2015年，Vinyals等[23]在人工智能顶级会议NIPS上提出了一个用于解决变长序列到序列的神经网络模型——指针网络，还验证了该模型可以单独使用训练示例来学习3个几何问题的近似解，即寻平面散点集的凸包、Delaunay三角剖分算法和平面旅行商问题。指针网络深度学习被提出后，近几年被研究者多次引用，文献[24]将指针网络深度学习结合强化学习解决旅行商问题，并提出该模型也可用于解决背包问题。文献[25]使用指针网络模型结合强化学习技术来优化3D装箱序列以最大化其收益。受这些模型的启发，本文首先将无人机全局路径规划建模为定向问题，接着采用指针网络深度学习对其进行求解。
在局部路径规划方面，无人机将根据节点广播参考信号强度（RSS, received signal strength）的特征[26]对其局部路径进行规划。文献[27]采用Q学习利用无人机对非法无线电台进行定位和寻。然而，
传统Q学习很难解决具有大量状态空间的模型，这导致其很难适用于大规模节点网络中的无人机路径规划。本文通过深度Q网络（DQN, deep-Q network）学习机制对大规模的Q表进行模拟与近似，从而极大地降低了Q学习的计算复杂度。
综上，本文首先将无人机的全局路径规划建模为定向问题并通过指针网络深度学习求解；然后在局部路径规划方面，利用DQN使无人机逼近目标节点。仿真结果表明，在无人机能耗限制下，所提方案能极大地提升物联网中的数据收集收益。
2系统模型及问题建立
2.1全局路径规划
本文综合考虑无人机在数据采集过程中面临
·126· 通  信  学  报 第42卷
的能量约束问题和路径规划问题。无人机能量消耗不仅与航行时间、航行速度有关，还与所处环境中的风速、障碍物等有关[28]。文献[29]将无人机的路由算法分类为恒定速度无人机、自适应速度无人机、悬停最大服务时间（HMS, hover with maximum service time ）等。本文采用HMS 的路由方法，即无人机悬停在相应节点上方，并以最大悬停时间max t 对用户进行数据传输，且假设无人机以恒定
的速度v 飞行。
在图1所示的系统模型中，无人机的起点和终点均为无人机服务站depot D 。depot D 可对无人机收集到的数据进行处理，并对无人机充电，需要收集数据的传感器节点随机分布在地图上，可通过聚类算法对随机分布的传感器节点进行分簇，并得到簇的中心坐标（图1中黑点）[30]。关于无人机以什么样的顺序访问这些簇才能在有限的能量约束下取得最大收益的问题，可以被建模为一个定向问题，即选取点和确定最短路径2种问题的结合。由于无人机数据收集存在无人机能量限制，因此不是所有的簇都会被服务。令{}1,2,,S k ∈"表示簇的集合，其中k 表示簇的数目。第i 个簇的奖励值为i p ，簇i 到j 的距离为,dist i j ，,1i j l =表示i 与j 之间有路径，那么无人机全局路径规划问题可以表示为
,,,,,max min ,dist i j i i j i j N N i j N
i j N
l p l ∈∈∑∑ (1) s.t.,01N k δδ=≤≤ (2)
depot,,depot 111k
k
j
i j i l
l ====∑∑ (3)
1,,1
1
12,,1k k
i s
s j i j l
l s k −===∀∈−∑∑"≤，
(4)
图1  系统模型
目标方程(1)表示最大化数据收集的奖励值，并且最小化无人机的飞行路径；约束(2)表示无人机可服务簇的份额；约束(3)表示起点和终点均为
无人机服务站depot D ；
约束(4)表示每个簇最多被服务一次。
在优化目标式(1)中，关于每个簇奖励值的设定，如果简单设定为簇内所有节点存储数据的总和，则可能对稍远的节点不公平，所以可将每个节点的奖励值设置为
0,10,dist max dist i i i
N j j
p I == (5)
其中，i I 表示簇i 内所有节点数据量总和的值（无量纲）。因此，奖励值的设定不仅与节点到服务站的
距离有关，还与数据的存储量有关，且p i 无量纲[31]。
2.2  局部路径规划
假设无人机对目标传感器的位置是未知的，无人机以固定的高度飞行，只考虑二维平面的运动，目标传感器节点的位置坐标为(,)x y ，无人机当前状态的坐标为(,)i i x y ，无人机与目标节点之间的距离可以表示为
d =
(6)
无人机通过配备天线来测量目标节点的RSS ，无人机可移动方向被相等地划分为8个方向，具体
如图2所示。
图2  无人机移动方向
RSS 值R P 可以通过以下计算式求得，它与距离
m d （单位为）有关，具体为
R T PL()P P d f =−− (7)
()PL 128.137.6lg 1000d d ⎛⎞
=+⎜⎟⎝⎠
(8)
第2期 付澍等：物联网数据收集中无人机路径智能规划 ·127·
其中，T P 为目标节点发射功率；()PL d 为距离d 处的路径损耗，此处的路径损耗模型[32]采用3GPP TR 38.814，本文主要参考天线接收信号强度值，为简化系统模型，只考虑了地对地大尺度信道衰落，后期研究无人机数据传输过程中将进一步同时考虑视距和非视距对传输性能的影响[33-35]；f 为捕获信道衰落变量。
深度Q 学习[36]融合了神经网络和Q 学习的方法，属于强化学习的一种，当然也应该具有强化学习的基本组成部分，即智能体、环境、动作、奖励、策略、值函数等。强化学习智能体与环境的交互过程如图3所示。智能体通过与环境进行交互，循环迭代产生新的状态并结合环境给出奖励值。
图3  强化学习智能体与环境的交互过程
Q 值函数更新式为
()()()()(),,,x ,,[ma s a s a s a Q Q r Q s s Q a a αγ=++−′′  (9)
其中，[]0,1α∈是学习率，[]0,1γ∈是折扣因子。 无人机的状态s 取决于各个方向测量的平均RSS 值中最大的RSS 值，动作空间对应图2中的8个方向，即{}12345678,,,,,,,a a a a a a a a a ∈。奖励值
r (s ,a )的设定为：如果当前位置各个方向测量的平均RSS 值中的最大值减去上一位置的各个方向测量的平均RSS 值中的最大值为正，则给一个正的奖励值，该奖励值设为固定值；如果为负，则给一个负的奖励值。如果无人机达到终止条件，则给其较大奖励值，本文中奖励值设定为
()2,RSS  2,RSS 100,,s a r ⎧⎪
=−⎨⎪⎩增加减小
达到终止条件 目标方程为
()()()traget max ,,Q r Q s a Q s a γ=+−′′ (10)
无人机的终止条件为当距离d <7.0时，目标节点定位成功。深度Q 学习的原理框架如图4所示。
3  算法建立
3.1  指针网络深度学习建立
指针网络深度学习的结构如图5所示，它是由序列到序列模型[37]和注意力机制[38]
结合改进得到
中国近代史人物
图4  深度Q 学习的原理框架
·128· 通  信  学  报 第42卷
的，由Encoder 和Decoder 这2个阶段组成。在Encoder 阶段，只考虑输入j x 对输出i y 的影响；在Decoder 阶段，解码输出注意力概率矩阵，并通过softmax 得到序列的输出概率分布。由于长短期记
忆网络（LSTM, long short-term memory ）[39]能够成功学习具有远距离时间依赖性数据的特征，其被用作网络单元构建指针网络深度学习模型。Encoder 部分使用LSTM 多层神经网络（记为LSTM-e ），Decoder 部分使用LSTM 多层神经网络（记为LSTM-d ）。
图5  指针网络深度学习的结构
第2节对无人机路径规划问题进行了建模，分别确定指针网络（PN, pointer network ）深度学习模型的输入输出如下所示。
1) 输入
coords 0011(,),(,),,{}(,)k k D x y x y x y ="为无人机服务站depot D 和每个簇中心坐标loc D 的并集。假设
depot D 处的奖励值00p =，prize 01,,{},k P p p p ="为0p 和i p 的并集，inputs 000111(,,)=,{,(,),,D x y p x y p "
感谢生活作文
,}(,)k k k x y p 。
2) 输出
输出序列roads 01{,,,}n D P P P ="表示无人机数据收集过程中簇的收集顺序，n P 对应inputs D 值的索引。指针网络深度学习的编解码过程为：输入序列inputs D 经过k +1步依次输入Encoder 模块，然后通过
Decoder 模块依次输出roads D 中的元素。
因此指针网络的原理可以表示如下[40]。
编码过程。将输入序列inputs D 经过k +1步依次
输送给LSTM-e ，
得到每一步输入所对应的LSTM-e 网络状态0,1,,()j e j k ="，如式(11)所示。当inputs D 输入完毕后，将得到的隐藏层状态1,,Enc ),,=(i n e e e ""进行编码后输入解码模块。
解码过程。由式(12)计算出LSTM-d 网络的隐藏层状态1,,Dec=(),,i n d d d ""；由LSTM-e 网络的隐藏
层状态1(),,,,i n e e e ""和LSTM-d 网络的隐藏层状态1,,Dec=(),,i n d d d ""分别计算出每个输入对当前输出带来的影响，如式(13)所示。将其softmax 归一化后得到注意力矩阵i a ，如式(14)～式(16)所示。然后选择矩阵中权重占比最大的指针作为输出，如式(17)所示。
()()1
,,,j j
j
j
j e f
x y p e −= (11)
()11 ,i i i d f P d −−= (12)
()T 12tanh ij j i u W e W d =+v  (13)  ()01inputs |,,,i i i p P P P D −=a " (14)  {}12,,,i i i in a a a =a " (15)
()
()
1
社保卡怎样查余额exp exp ij ij n
ij
j u a u ==
∑ (16)
01inputs  (|,arg m ,x ,)a i i i P p P P P D −=" (17)
其中，f 为非线性激活函数；v 、1W 和2W 为输出模型的可学习参数；ij a 由ij u 经过softmax 后得到，其作用是将ij u 标准化为输入字典上的输出分布[23]。 在解码过程中，还要考虑到定向问题模型中的
约束问题。首先，对于约束(2)，预设一个服务份额值δ。对于约束(3)，无人机的起点和终点均为无人机服务站depot D ，因此，第一步和最后一步将0P 和n P 设置为0。对于约束(4)，根据禁忌搜索的思想，在每一步添加roads D 元素时，将其作为禁忌元素添加到
号怎么注销
action D 表中，每一步输出将根据action D 表，在注意力矩阵中选择非action D 表中权值最大的作为输出。 3.2  指针网络+主动搜索策略
根据文献[25]提出的主动搜索（AS, active
search ）策略，将inputs D 中的元素（除索引0的位置）随机排列组合生成B 个批次的输入序列，通过梯度下降法优化目标函数，最后输出路径。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。