一种无人机辅助移动云感知的路径规划与任务分配方案转让专利
申请号 : CN201810799964.5
文献号 : CN110736478B
文献日 : 2021-05-11
发明人 : 刘朋矩 , 周振宇
申请人 : 华北电力大学
摘要 :
权利要求 :
1.一种无人机辅助的移动云感知下路径规划和任务分配方法，其特征在于，无人机感知环境包括一个目标传感区域，一个移动云感知载体，和几个配备各种传感器及通信设备的无人机；通过移动云感知过程和任务分配策略对传输过程进行合理安排以提高能效；定义子区域集合为 任何子区域 的拓扑结构都建立成一个图，并用 来表示子区域n中的节点集合，其元素即为目标节点；目标节点i和i′之间的路线段定义为 其长度定义为 当两个节点之间不存在路线段时，规定进一步包括：
1)移动云感知过程：首先移动云感知载体发出传感请求，并招募无人机通过基于互联网的传感平台执行传感任务；定义可用无人机集合为 并假设K＞N；每个无人机根据任务分配决策执行感知任务，假设子区域n被分配，那么无人机从目标节点i＝1开始，沿路线段飞行，穿过子区域的每个目标节点，并在完成传感任务后返回初始位置，通过互联网将采集到的数据上传至平台；
2)任务分配策略：移动云载体和无人机的任务分配决策分别被表示为一个N×K矩阵XN×K和K×N矩阵YK×N，其中第(n，k)个元素表示为二值变量xn，k，其中xn，k＝1表示移动云感知载体更喜欢无人机k来执行子区域n的传感任务，否则令xn，k＝0；同样，第(k，n)个元素表示为二值变量yk，n，当yk，n＝1时表示无人机k更喜欢在子区域n中执行传感任务；
所述移动云感知过程进一步包括：建立针对于移动云感知载体及无人机的效用方程，
1)移动云感知载体的效用方程：对于移动云感知载体来说，它的收入取决于传感任务完成的程度和速度，感知质量、数量和延迟，因此移动云感知载体通过分无人机k到子区域n来获得收益，这个收益计算为
其中价格系数αn将关键参数变成一个统一的单位；用Dn表示与目标节点数量In正相关的子区域n中需要收集的总数据量；δk表示关联于感知设备精确性的无人机k的数据采集量，并为简化起见将Dn和δk设定为常量值；tk，n是无人机为完成传感任务所需要的总时间，即感应延迟，其值依赖于子区域的拓扑结构和无人机的路径规划方案，这里的 仅表示收益和感应延迟成反比的数值关系；对于分配的任务，用βn表示类似于αn的价格系数，则移动云感知载体付给无人机的报酬表示为：pn，k＝βnDnδk
因此移动云感知载体的效用表示为取得的收益和付出的报酬的差值，即其中xn为矩阵XN×K第n行的元素，即xn＝{xn，1，...，xn，k，...，xn，K}；
2)无人机的效用方程：对于无人机k，从移动云感知载体中获得的奖励为上文定义的pn，k；对应的成本表示为总能耗的线性函数，包含推进消耗的能量、方向调整、数据采集和传输消耗的能量，由于一般来说推进和方向调整的能耗比通信高几个数量级，忽略通信损耗以降低计算复杂度；基于稳态直线飞行模型推导出推力的能量消耗，并做出以下两个假设：①任何无人机在没有水平加速度和突然转向的情况下，以恒定的速度朝着特定方向飞行；
②任何无人机飞行高度恒定，没有垂直加速度；
因此假设每个无人机的速度在某个路线段内保持不变且不同路线段内能够发生变化，用 表示无人机通过子区域n的路线段 时的速度，相应的推进功率为其中 为平衡由表面摩擦引起的摩擦阻力所需的功率， 为平衡空气摩擦引起的摩擦阻力所需的功率，这两者与无人机及环境参数有关，表达为：其中 和 分别代表了空气密度和沿路线段 的零升力阻力系数，ηk和Wk分别代表了无人机的机翼长宽比和重量；因此飞过路线段 的能量损耗为在目标节点i′处调整前进方向所消耗的能量表示为其中a(t)表示无人机调整前进方向时的加速度，Tk′表示调整花费的时间，g是重力加速度；经计算发现 的值远小于 的值，因此忽略；对无人机k来说，子区域n的路线段选择策略集定义为 其中， 表示无人机选择了路线段 速度控制策略的集合定义为 因此无人机在子区域n的总能耗表示为：
其中σn为价格系数，则无人机的效用表示为奖励和成本的差值，即其中yk是矩阵YK×N第k行的元素，并且有yk＝{yk，1，...，yk，n，...，yk，N}。
2.如权利要求1所述无人机辅助的移动云感知下路径规划和任务分配方法，其特征在于，考虑到移动云感知载体和无人机都是自私的并且有利益的冲突，他们必须就任务分配决定达成一致才能成功地执行任务；进一步表述为两个目标的联合优化问题，具体包括：
1)移动云感知载体的目标：在感知延迟的约束下最大化其效用，表达为其中C1表示感知任何子区域所需的时间应该小于指定的延迟阈值 C2和C3保证每个无人机最多只能感知一个子区域且每个子区域最多只能被一个无人机感知；
2)无人机的目标：在电池容量的约束下最大化其效用，其表达为其中C4是能耗约束，即用于推进的总能耗应小于电池容量；C5是感知节点数量的约束，以确保所有子区域的目标节点都被感知到；C6表示每个路线段的速度边界约束；C7和C8的作用类似于C2和C3。
3.如权利要求2所述无人机辅助的移动云感知下路径规划和任务分配方法，其特征在于，提出的能效的联合任务分配和路径规划算法，将原始的N‑P难问题转化为两阶段的双边匹配问题，继而将动态规划和凸优化相结合解决路径规划问题，再根据最优路径规划结果，应用基于Gale‑Shapley算法的稳定匹配算法解决任务分配问题；上述过程进一步包括：
1)问题转换：将原始的N‑P难问题转化为考虑到双方利益冲突的两阶段双边匹配问题；
变换后的匹配问题可用三维数组 来表示，其中 和 分别表示匹配参与者子区域和无人机的集合， 表示匹配偏好的集合，为实现子区域和无人机在其约束下效益最大化，定义匹配关系φ：对于匹配问题 匹配φ是一组在偏好 限制下从集合到其自身的一一对应关系，即
并有当且仅当φ(n)＝k时φ(k)＝n；
2)基于动态规划的路径规划：为获得最小的能量消耗，必须解决路径规划问题以获得无人机的偏好，即使无人机k在第n个字区域执行传感任务时的能耗最小化：s.t.C4，C5
值得注意的是，路径规划问题P3有两个独特的特点：①路径规划决策是在离散时间阶段动态形成；
②能耗是阶段性的，即总能耗是选定的每一段飞行所消耗的推进能量的总和；
因此，P3属于确定性有限状态旅行商问题的框架，这是一个典型的N‑P难问题，我们使用动态规划来解决这个问题，因为它可以为评估其他次优算法提供一个较高的性能基准；
动态的原则是系统状态按照离散阶段的决策而发展，系统状态演化表示为：rτ+1＝z(rτ，uτ)，τ＝0，1，2，...，ψ‑1其中ψ和τ分别代表了阶段的总数和阶段的标号，rτ表示系统处于阶段τ，uτ表示阶段τ时做出的决定，状态更新机制由z枚举产生；为了使动态规划公式与路径规划问题一致，我们将目标节点集合作为状态集，即若状态阶段τ的目标点是i，则 决定子区域n的路线段选择策略集合即为 当阶段τ挑选了路线段 时， 因此状态的更新表示为：
动态规划在阶段τ的成本函数表示为阶段τ的能耗其中 是无人机在路线段 的最优速度， 是无人机在子区域n中从目标节点i；到节点i′的最低的能耗；假设初始阶段为r0＝0(τ＝0，i＝1)，并且ψ是有限的，即当目标节点有限时，无人机k在感知子区域n时的能耗定义为：o
其中C (ψ)表示最后阶段的最小能耗，即终端成本；上述优化问题通过从ψ‑1到0的阶段后项选择来解决
o
Jψ(rψ)＝C(rψ)
然而各阶段的最小能耗是未知的，为了获得这个能耗，需要解决以下问题：s.t.C6
注意到P4是下凸的，因此用Karush‑Kuhn‑Tucker方法解决，其拉格朗日方程为其中μ和λ为拉格朗日乘子，通过求 的一阶导数获得最优的速度，即解决以下问题：
则最优的总感知延迟和感知成本分别表示为：
3)偏好列表的建立：为实现双向匹配，匹配的参与者需要按照偏好对另一方参与者进行排序以构建自己的偏好列表，为了实现效用最大化，我们以可实现的最大效用对偏好进行建模，即偏好列表定义为实现最大效益时的匹配φ(n)＝k，子区域n和无人机k的偏好分别建立为：
定义一个完备的、具有反身性和传递性的二元偏好关系来比较偏好，即n
分别将子区域n对所有无人机的偏好列表和无人机k对所有子区域的偏好列表定义为Fk
和F，
n k
F 是根据 的值按降序对K个无人机进行排序，F 是根据的值按降序对N个子区域进行排序；整体集合 被导出为
4)基于Gale‑Shapley算法的任务分配：当无人机和子区域获得偏好列表之后，应用Gale‑Shapley算法获得匹配结果，其核心规则如下：①请求规则：任意子区域向其偏好列表的最顶端无人机请求匹配；
②拒绝规则：对于任何从子区域收到匹配请求的无人机，当存在更好的匹配候选项时拒绝该子区域，否则以当前阶段未被拒绝的子区域作为匹配的候选项保留；
因此匹配过程按照下列迭代步骤完成：n k
①初始化偏好列表：对所有的子区域和无人机计算F 和F ，初始化φ为空集，定义拒绝集合Φ为未参与匹配的子区域，初始化 ②匹配迭代：重复下述迭代过程：每个子区域根据请求规则向无人机发出请求，每个无人机根据拒绝规则选择最优的子区域，更新拒绝集合Φ并从被拒绝的子区域的偏好列表中移除拒绝其的无人机；直到每个子区域都被无人机接受了，或者被全部的无人机拒绝了；
③任务分配和路径规划过程：每个无人机根据②获得的匹配结果开始执行传感任务，假设φ(n)＝k，无人机k将根据最优的路线段选择和路径控制策略感知子区域n中的目标节点，当所有的子区域都被感知到并上传数据之后，移动云感知载体发出新的感知请求，并开始新的任务分配和路径规划过程。
说明书 :
一种无人机辅助移动云感知的路径规划与任务分配方案
技术领域
最佳任务分配策略的方法与系统。
背景技术
行采集。移动云感知系统一般由三部分构成：（1）一个基于互联网的传感平台，在该平台上
收集传感数据并部署各种服务；（2）设备持有者提供传感数据并上传至平台；（3）在平台上
发布传感任务的移动云感知载体。与需要大量传感器节点的传统传感技术相比，移动云感
知为大规模传感任务提供了一种低成本的解决方案。
人机的发展，其在移动云感知中发挥着重要作用。由于无人机有着快速部署和机动性可控
的特点，可以在任何地方自动进行云感知。无人机可以被派往传感器的上方进行周期性数
据收集，或者配备了丰富传感器的无人机本身充当数据提供者，以感知地面车辆难以到达
的区域，例如洪水危险区或核污染区。
电池容量仅为5200 mAh。因此，能效是无人机辅助的移动云感系统的一个关键要求。每一架
无人机的飞行路线都需要进行良好的设计和优化，以满足能量预算的限制。另一个关键的
挑战是如何分配传感任务以使得每个移动云感知载体的个人效用最大化。由于移动云感知
载体和无人机为不同的实体，它们极有可能拥有完全不同的利益并相互冲突，因此当且仅
当双方就任务分配达成一致时才可以实现传感任务。
发明内容
量和延迟的限制下，如何在不同子区域同时完成无人机的传感任务。我们发现任务分配问
题与路径规划问题同时存在，因为移动云感知载体和无人机的最优任务分配策略都依赖于
感知延迟和感知成本（无人机的能耗），这首先要通过解决路径规划问题来确定。因此，基于
无人机的移动云感知的成功实现需要从能效的角度对任务分配和路径规划进行联合优化，
包括任务分配和路径选择中的二元优化变量，以及速度控制中的连续优化变量。为了提供
一个易于处理的解决方案，我们将原始的问题转化为基于问题结构和决策时间顺序的双边
匹配问题。这个问题包括两个阶段：第一阶段通过动态规划和凸优化相结合的方法，求解由
路线段选择和速度控制组成的路径规划问题，计算出最小的感知成本和延迟，然后每个匹
配的参与者按照偏好对另一方对参与者进行排序，构建自己的偏好列表，并将其建模为匹
配下能够实现的最大利润；第二阶段通过对Gale‑Shapley 算法的研究来进行任务分配，通
过迭代获得一个稳定的匹配。
域的面积一般都超过单个无人机的最大飞行距离；其次，不同子区域的传感任务可以由多
架无人机同时执行，以减少整体的传感延迟。定义子区域集合为 ,
任何子区域 的拓扑结构都可以建立成一个图，并用 来表示
子区域n中的节点集合，其元素即为目标节点。并按照以下过程执行任务：
任务，假设子区域n被分配，那么无人机从目标节点 开始，沿路段飞行，穿过子区域的
每个目标节点，并在完成传感任务后返回初始位置，通过互联网将采集到的数据上传至平
台；
量和延迟，因此将其表述为
反比，其存在其他表现形式。同时，移动云感知载体需要付给无人机的报酬，这个报酬表示
为：
整的能耗是比通信高几个数量级，因此可以忽略通信损耗以降低计算复杂度。假设无人机
的飞行模型为稳态直线飞行(SSLF)模型，并做出以下两个假设:
应的推进功率为
了路线段 ），速度控制策略的集合定义为 ，因此无
人机在子区域 的总能耗表示为:
目标是在感知延迟的约束下最大化其效用，表达为
表示匹配参与者（子区域和无人机）的集合， 表示表示匹配偏好的集合。为实现子区域和
无人机在其约束下效益最大化，定义匹配关系 :对于匹配问题 ,匹配 是一组在
偏好 限制下从集合 到其自身的一一对应关系，即
,并有当且仅当 时
。
性能基准。动态的原则是系统状态按照离散阶段的决策而发展，系统状态演化表示为：
致，我们将目标节点集合作为状态集，即若状态阶段 是目标点是 ，则 ；决
定的集合即为 ，当阶段 挑选了路线段 时， ,因此状态的更新表示为：
法求取最优值。匹配过程按照下列迭代步骤完成： ①初始化偏好列表：对所有的子区域和
无人机计算 和 ，初始化 为空集，定义集合 为未参与匹配的子区域，初始化 。
②匹配迭代：重复下述迭代过程：每个子区域根据请求规则向无人机发出请求，每个无人机
根据拒绝规则选择最优的子区域，更新拒绝集合 并从被拒绝的子区域的偏好列表中移除
拒绝其的无人机；直到每个子区域都被无人机接受了，或者被全部的无人机拒绝了。③任务
分配和路径规划过程：每个无人机根据②获得的匹配结果开始执行传感任务，假设
,无人机 将根据最优的路线段选择和路径控制策略感知子区域 中的目标节点，
当所有的子区域都被感知到并上传数据之后，移动云感知载体可以发出新的感知请求，并
开始新的任务分配和路径规划过程。
附图说明
具体实施方式
仅代表可能的变化。除非明确要求，否则单独的组件和功能是可选的，并且操作的顺序可以
变化。一些实施方案的部分和特征可以被包括在或替换其他实施方案的部分和特征。本发
明的实施方案的范围包括权利要求书的整个范围，以及权利要求书的所有可获得的等同
物。在本文中，本发明的这些实施方案可以被单独地或总地用术语“发明”来表示，这仅仅是
为了方便，并且如果事实上公开了超过一个的发明，不是要自动地限制该应用的范围为任
何单个发明或发明构思。
的问题转化为两阶段双边匹配问题，建立偏好列表并进行求解。通过具体的仿真，用数值结
果对提出的联合任务分配和路径规划优化算法进行评估。
速度增量所节省的能量高于增加的能量消耗；当速度达到最优值后，随着速度的增加能耗
增加，这是由于速度增量开始主导能耗。图3显示了在不同的目标节点数量下无人机的能量
消耗。相比于对比算法，带有速度优化的基于动态规划的路径规划算法取得了更好的效果。
可以看出，所有算法的能耗都随着目标节点数量的增加而增加，这是因为感知更大的地理
区域需要耗费更多的能量。然而该算法通过对路段的选择和速度的控制从能效角度实现了
优化。图4显示了感知延迟约束对移动云感知载体效用的影响。假设每个子区域的感知延迟
约束相同，将所提出的路径规划算法与贪婪路径规划和随机路径规划进行了比较，当传感
延迟约束处于较低的状态时，移动云感知载体的效用受到限制，因为只有很少的无人机能
够满足严格的延迟要求，并且有资格参与传感活动。这使得许多子区域都是不进行匹配的，
相应的效用为零。随着感知延迟约束的增加，允许更多的无人机执行感知任务，所有算法的
性能都开始增加，这是因为与效用更高的候选人匹配的可能性显著增加。特别地，所有算法
最终都达到了最佳的性能，这是因为在相同的最优速度策略下，基于动态规划的路径规划
算法总是达到最小的飞行距离，对应最小的感知等待时间，从而使移动云感知载体达到最
大利润。图5显示了移动云感知载体的效益与子区域数量的关系。将所提出的联合任务分配
和路径规划算法与其他算法比较，发现路径规划优化在性能改进中起着重要作用。这是因
为基于动态规划的路径规划算法总是在相同的最优速度策略下达到最小飞行距离，从而获
得最小感知延迟，实现移动云感知载体的最大效用。图6为各子区域满意度累积分布函数与
满意度阈值的关系。子区域的匹配满意度以统计方式计算，使用蒙特卡洛方法获得这个统
计值。通过数值分析可看出所提出方法拥有较高的满意度。