基于近邻算法的无人机采集森林数据航迹路线的规划
时间：2023-04-15 16:10:04 来源：柠檬阅读网 本文已影响 人 
王晓东，杨昆
(1.河南九域腾龙信息工程有限公司， 郑州 450000；
2.郑州科技学院 信息工程学院， 郑州 450064)
随着低功耗[1]、微型传感器的迅速发展，无线传感网络(Wireless Sensor Networks, WSNs)已在军事和民用等领域广泛应用[2]。在这些应用中，传感节点收集检测区域内的数据信息，再经数据样本采集、处理和传输，使控制中心能够掌握区域环境的实况。这类应用特别适宜于无人值守或者恶劣环境的监测[3]，如森林防火、煤矿检测。有效地收集数据是基于WSNs应用的关键，传统的收集数据方法是由WSNs内节点自行组网，并通过单跳或者多跳方式将数据传输至控制中心。由于多数传感节点是由干电池供电，节点的能量有限。传统的收集数据方法消耗了节点的大部分能量，易出现能量空洞[4]。据此，研究人员在WSNs中采用移动节点收集网络内节点数据，如移动机器人、小车和无人机(Unmanned Aerial Vehicles, UAV)。因机动性好，部署灵活，基于UAVs的WSN数据收集机制受到广泛关注[5-9]。例如，Chen等[5]研究基于UAV协助的数据收集算法。该算法采用非正交多址接入(Non-orthogonal multiple access, NOMA)策略，并将节点组建成NOMA群，并在UAV位置、功率控制约束条件下，最大化网络吞吐量。数据收集轨迹规划是基于UAV辅助WSN数据采集的关键。Zhan等[10]研究证实：最优的数据收集轨迹是由连通线段组成。先建立数据收集轨迹优化模型，再利用凸优化求解获取次优解。此外，Hu等[11]研究表明，UAV性能由UAV的数据收集和传输过程共同决定，而这2个过程又受到UAV路径影响。然而，上述研究工作只关注到UAV路径规划问题，没有考虑到传感节点的能量问题。Yang等[12]考虑了传感节点充电时间问题，并利用遗传算法UAV的最优锚点和停留时间。尽管上述研究工作充分利用了UAV在空中收集数据的速度快、无线信号覆盖范围大等优势，但是其没有考虑无线能量传输(Wireless Power Transfer, WPT)策略。由于传感节点是由干电池供电，并且即使电池能量消耗尽，也不便更换电池，节点的工作寿命有限。部署UAVs也只是降低节点能耗速度，并不能从根本上解决节点储能的有限问题。利用WPT策略，使无人机向节点传输电能，可有效地补充节点能量，延长节点的工作时间。UAVs的机动性好，其返航充电站充电。一方面，延长UAV的续航时间，另一方面，补充能量后可继续为监测区域内的节点补给能量。
本研究以检测森林异常数据为应用场景，通过UAV收集已部署森林区域内的节点数据, 研究单个UAV的航迹规划问题，即UAV的移动轨迹。UAV在收集节点数据时，需移动至节点上空，并以悬停方式收集节点数据。因此，如何规划UAV的航迹是提高数据收集效率的关键因素之一。
在规划UAV航迹时考虑2项约束条件：①每个节点都需被遍历，即在单条航迹路径中，UAV需遍历每个节点；
②确保UAV能够返航到充电站，一旦UAV的剩余能量小于阈值，就返充电站充电。其中阈值等于UAV返航到充电站所消耗的能量。规划UAV航迹的目标：基于上述2项约束条件，最小化UAV航迹路径，降低数据收集时间。为此，本研究提出基于近邻算法的无人机数据采集航迹规划算法(NNDC)。先基于节点被遍历、UAV有能量返航能量的约束条件下，建立路径最小化路径的模型，再利用近邻算法求解，获取最小化UAV航迹路径。性能分析表明，NNDC算法缩短了路径，降低了数据收集时间。
考虑森林异常数据检测场景。在森林区域内部署多个传感节点，这些传感节点收集区域数据，如温度数据、非法生物入侵等异常事件[13]，网络模型如图1所示。
图1 网络模型Fig.1 Network model
网络由N个传感节点和一个无人机构成。采用确定性方式在目标区域内(e×e)部署N个传感节点，其中e为边长。假定N个传感节点位置为已知信息。由集合N={s1,s2,…,sN}表示。i∈N表示节点索引号。传感节点以固定周期感知环境数据，再将数据传输至UAV。用G=(N,T,A)表示网络模型，其中N表示顶点，其对应网络中的节点数；
T=[Tij]为权重矩阵，其中Tij表示顶点i与顶点j连线的权重；
A={(i,j)|i,j∈N,i≠j}表示2顶点间的连线(边)集。
此外，在网络区域部署一个UAV的充电站。当UAV的电量不足，其将返到该充电站充电。为简化表述，用S0表示充电站。
NNDC算法旨在满足能量约束条件和UAV遍历所有节点的条件下，最小化UAV完成任务的时间。为此，先阐述节点和UAV的能耗模型。
2.1 UAV向节点的无线输电
(1)
式中，ti表示si需要从UAV采集能量的时间。
2.2 UAV的能耗
UAV的能耗主要由2部分组成[15]。
(2)
(3)
Ep的定义见公式(4)
(4)
(5)
因此，UAV的能耗(EUAV)可表述为
(6)
2.3 目标问题的构建
NNDC算法通过优化UAV的航迹路径，减少收集所有传感节点所需的时间。因此，可构建如公式(7)所示的目标问题
(7)
式中，dij表示节点si与节点sj间距离。
为了保证UAV在任意一条路径r∈R需遍历每个节点，且只遍历一次，构建公式(8)的约束条件
(8)
同时，确保UAV在每条r∈R中航迹中，只遍历一次从顶点i与顶点j连线，需构建公式(9) 的约束条件
(9)
最后，对UAV在每条路径所消耗的能量进行限制，使其不超过其可储存的最高能量Emax。
(10)
实质上，公式(7)的目标问题是规划UAV的航迹问题。为了消除子环路径，采用Miller-Tucker-Zemlin(MTZ)约束进行子环消除。作为有效的子环消除约束条件，MTZ被广泛应用于车辆路径规划问题。为此，对约束条件进行修改。
i≠j,∀r∈R。
(11)
(12)
此外，UAV的每条路径r∈R必须包含S0(充电站)。因此，先生成K个S0的复制点，并将其加入节点集，即形成新的节点集N′=N∪K,其中K表示K个S0的复制点所形成的集合，即K={N+1,…,N+K}。相应地，边集A也被扩展，即A′={(i,j)|i,j∈N′,i≠j}。
为了保证每条航迹路径均遍历一个S0点，形成公式(13)的约束条件
(13)
最后，形成见公式(14)的目标函数P1(包括公式(8)、公式(12)、公式(13)，下面不再列出)
(14)
P1问题是典型的行商问题(Travel Salesman Problem, TSP)。而TSP问题为NP-complete问题[16]。因此，P1问题也是NP-hard问题。为此，采用近邻算法，规划UAV的航迹。
(15)
对于任意一条路径r∈R，UAV从S0开始，先寻找离其最近的节点作为下一个遍历点。假定sk∈N是离S0最近的节点。因此，将sk∈N加入路径r，即Tr←{s0}∪{sk}，其中Tr表示路径r的节点集。UAV移动至节点sk后，就开始向其传输能量，随后，收集该节点数据。UAV再更新自己的能量
(16)
下面给出基于近邻算法的UAV轨迹规划过程的算法。
该算法的输入为：
(1)充电站S0离网络内所有节点的距离，即{d0i}i∈N。
(2)各节点间距离，即{dij}i∈A2。
初始阶段，令d←0;EUAV←Emax;r←1;Tr←{S0};Nr←φ;N′←N。
4.1 仿真环境
利用MATLAB软件建立仿真平台，分析NNDC算法的性能。在200 m×200 m区域内以确定性方式部署N个传感节点。充电站S0位于200 m×200 m区域中心。部分仿真参数见表1。
表1 仿真参数Tab.1 Simulation parameters
选择3个同类的算法作为参照。
(1)基于距离排序的UAV航迹规划(Distance-Sorting Trajectory Planning of UAV, DSTP)。在DSTP算法中，先依据节点离充电站距离的大小，从近至远排序。其中充电站就是监测区域的中心位置，且是UAV的初始位置。然后，UAV再依据各节点序值，依次遍历。
(2)随机服务(Radom Service, RS)算法。在RS算法中，UAV以随机方式收集节点的数据，即随机移动。
(3)利用分支定界法直接求解目标函数,记为BABS。该方法能够获取最优的航迹，但是该算法的复杂度很高。
4.2 性能分析
将UAV收集所有节点的数据称为一项任务。UAV完成单项任务的时间越短，表示路径越优。分析节点数随任务的执行时间变化。图2给出UAV执行50次任务时完成任务的平均时间，以下简称任务平均时间。由图2可知，任务平均时间随节点数的增加而呈线性增加。原因在于节点数越多，UAV在执行每次任务需要收集的节点数据越多。因此，执行任务时间就越多。此外，相比于RS算法和DSTP算法，提出的NNDC算法降低了执行任务时间。原因在于NNDC算法利用近邻算法，优化了UAV收集数据的路径。BABS算法执行任务时间最短。这主要因为BABS算法采用穷搜索法建立了遍历所有节点的最优路径。然而，由于复杂度高，BABS算法只能执行14个节点的任务。
图2 任务平均时间随节点数变化情况Fig.2 Average mission time varies with number of nodes
分析UAV可存储的最大能量Emax对任务平均时间的影响，如图3所示。其中节点数为14。由图3可知，任务平均时间随Emax的增加而下降。原因在于：Emax越大，UAV存储的能量越足，其返往充电站充电的次数越少，这利于缩短节点遍布节点路径。此外， BABS算法具有最低的任务平均时间，并且当Emax大于600 J，其保持常数。这意味着，当Emax足够大时，BABS算法只需一条路径就能遍布网络中所有节点，无须中途返回充电站充电。相比于RS算法和DSTP算法, NNDC算法的任务平均时间仍保持显明的优势。
图3 任务平均时间随Emax变化情况Fig.3 Average mission time varies with Emax
再分析NNDC算法在每轮节点数据收集所产生的路径数。路径数越少，说明UAV往返充电站的次数越少，能够以低能耗方式收集节点数据。图4给出节点数为14个时的路径数随Emax的变化情况。由图4可知，Emax越大，每轮收集节点数据所需的路径数越少。这意味着UAV在收集节点数据时，充电次数越少。当Emax达到650 J时，NNDC算法所需的路径数逼近于BABS算法所需路径数。
图4 路径数随Emax变化情况Fig.4 Average number of tours varies with Emax
最后，分析30轮数据收集中，UAV在每轮中所消耗的能量，如图5所示，Emax=600 J,N=20。一轮是指UAV收集遍历所有节点，并收集所有节点的数据。由图5可知，随着轮数增加，UAV的能耗在增加，原因在于最初节点可利用储能工作，但随着轮数增加，节点需要从UAV采集更多能量，换而言之，UAV需要向节点补给更多能量，这就增加了UAV的能耗。相比于RS和DSTP算法，NNDC算法降低了能耗。这归功于NNDC算法优化了收集数据的路径，减少飞行时间。
图5 UAV平均每轮所消耗的能量Fig.5 Average energy consumed of UAV in each round
针对无线传感网络的数据收集问题，提出基于近邻算法的无人机数据采集航迹规划算法(NNDC)。NNDC算法利用无人机的机动性、高空特性，收集节点数据。同时，考虑到节点能量有限问题，NNDC算法通过无人机向节点补给能量。本研究针对森林数据异常数据收集的应用前景，利用无人机收集节点数据;建立数据收集时间最小化的目标函数，再利用邻近算法规划UAV遍历节点数据的次序；
考虑到节点的能量有限问题，允许UAV利用WPT向节点传输能量。性能分析表明，相比于RS和DSTP算法，NNDC算法缩短了数据收集时间。
