物联网三维空间智能定位与分布式边缘计算支援方法

摘要

本发明的物联网三维空间智能定位与分布式边缘计算支援方法，包括：获取各个锚节点能耗和与物联网设备的距离信息，为每个物联网设备构建可用锚节点集合；根据锚节点间的夹角关系，从可用锚节点集合中选取4个不共面的锚节点构建物联网设备的定位单元集合；利用定位单元集合中的锚节点信息，求出物联网设备的定位坐标，并利用多次定位的均值求解目标物联网设备的位置；获取所有物联网设备的位置和任务请求类型，利用搭载边缘服务器的无人机基站动态执行路径规划以处理多个物联网设备的请求，确定卸载决策；无人机按照最优的路径规划航行，靠近物联网设备，物联网设备进行边缘计算卸载。

权利要求

1.物联网三维空间智能定位与分布式边缘计算支援方法，其特征在于，包括：步骤1：获取各个锚节点能耗和与物联网设备的距离信息，为每个物联网设备构建可用锚节点集合；

步骤2：根据锚节点间的夹角关系，从可用锚节点集合中选取4个不共面的锚节点构建物联网设备的定位单元集合；

步骤3：利用定位单元集合中的锚节点信息，求出物联网设备的定位坐标，并利用多次定位的均值求解目标物联网设备的位置；

步骤4：利用搭载边缘服务器的无人机基站动态执行路径规划以处理多个物联网设备的请求，目标为最大化系统的总移动效益，根据边际效用递减定律定义系统效益卸载决策变量的打分函数来决定卸载决策，规划无人机的飞行轨迹，具体为：步骤4.1：定义无人机计算支援系统的总移动效益函数，进而以最大化总移动效益函数为目标进行路径规划；

步骤4.2：获取上一时刻无人机的位置坐标集合，以及这一时刻的所有物联网设备的准确位置坐标集合和任务请求集合；

步骤4.3：根据边际效用递减定律定义系统效益卸载决策变量的打分函数；

步骤4.4：每一个无人机都运行一个无人机代理，无人机代理根据该时刻各物联网设备的位置、卸载决策和维护的移动效益，构建最大移动效益的覆盖集；

步骤4.5：选择当前无人机的最大移动效益覆盖集所对应的最优卸载决策和路径方案，即最大移动效益的方案；

步骤4.6：对于无任务产生的物联网设备为中心的情况，则根据已得到的有任务物联网设备的卸载决策根据该时刻各物联网设备的位置、卸载决策和维护的移动效益，构建最大移动效益的覆盖集，得出当前最优的卸载决策和路径方案；

步骤4.7：物联网设备通过与邻居进行通信与一致性协议来维护和更新自身当前已知的最大效益覆盖集，当物联网设备和他们的邻居对于每一个无人机所维护的最大效益覆盖集一致时停止迭代，得到对应的卸载决策和路径方案；

步骤5：无人机按照规划的路径信息航行，同时处理物联网设备的任务需求，无人机处理卸载的计算任务，并更新无人机剩余计算资源。

2.如权利要求1所述的物联网三维空间智能定位与分布式边缘计算支援方法，其特征在于，步骤1具体为：步骤1.1：物联网设备向周围的锚节点发送定位请求广播，包括设备标识和请求时间；

步骤1.2：定位请求到达物联网设备通信范围内的锚节点后，锚节点根据发送的时间戳和到达的时间，利用距离偏差模型计算该锚节点与物联网设备的距离，得到相应物联网设备的任务请求和距离信息，并将自身的位置坐标、剩余能量、与该物联网设备的距离信息发送给定位计算中心；

步骤1.3：定位计算中心收集和统计各个锚节点位置信息、剩余能量、与物联网设备的距离信息，为每个设备构建备选锚节点集合；

步骤1.4定位计算中心判断备选锚节点集合的元素剩余能量是否小于能量阈值，距离信息是否在能保证计算精确的物联网设备有效通信范围内，将能量小于能量阈值和在有效通信范围外的锚节点信息剔除，构建可用锚节点集合。

3.如权利要求1所述的物联网三维空间智能定位与分布式边缘计算支援方法，其特征在于，步骤2具体为：步骤2.1：对于每一个物联网设备的可用锚节点集合中的任意锚节点，利用三角形余弦定理，求取该物联网设备与每两个锚节点之间的距离和夹角；

步骤2.2：对每个物联网设备，从对应的备选锚节点集合中选取4个不共面的锚节点，若可用于定位锚节点大于4，则任意选择两个与目标物联网设备的连线夹角趋近于109.4736°的锚节点来构建定位单元，为该物联网设备形成定位单元集合。

4.如权利要求1所述的物联网三维空间智能定位与分布式边缘计算支援方法，其特征在于，步骤3具体为：步骤3.1：针对每个物联网设备，利用其定位单元集合中的锚节点信息，求出每组定位单元所对应的该物联网设备的位置坐标；

步骤3.2：通过对每个物联网设备进行多次定位，分别以各自的定位均值对其位置坐标进行修正；

步骤3.3：当两次定位的均值误差小于定位阈值时，此时算法趋于收敛，退出定位循环过程，得到物联网设备的准确位置坐标。

5.如权利要求1所述的物联网三维空间智能定位与分布式边缘计算支援方法，其特征在于，所述总移动效益函数为：其中，xij(t)为t时隙物联网设备ui任务卸载决策变量，当物联网设备ui将任务卸载给无人机vj执行时，xij(t)＝1，否则当xij(t)＝0时，则任务将在本地执行；任务请求只能交给一架无人机执行，卸载决策变量范围即为xij(t)∈{0,1}， 是无人机vj为物联网设备ui执行任务 的系统效益， 为无人机从pj(t‑1)位置到物联网设备ui的位置上方的飞行能耗，为执行所卸载任务的能耗。

6.如权利要求1所述的物联网三维空间智能定位与分布式边缘计算支援方法，其特征在于，所述系统效益卸载决策变量的打分函数为：其中， 表示当前迭代的打分值，Πj是无人机vj的最大覆盖集，即该集合中的任务可以卸载到无人机vj执行， 的定义为：其中， 为上次迭代最后加入覆盖集中的用户的打分值， 表示当前迭代执行ui任务的实际CPU频率， 表示上次迭代最后加入最大覆盖集中用户u的执行任务的实际CPU频率。

7.如权利要求1所述的物联网三维空间智能定位与分布式边缘计算支援方法，其特征在于，步骤5具体为：步骤5.1：无人机按照规划的路径信息航行，同时处理物联网设备的任务需求；

步骤5.2：无人机处理卸载的计算任务，并更新无人机剩余计算资源。

说明书

物联网三维空间智能定位与分布式边缘计算支援方法

技术领域

[0001] 本发明属于物联网技术领域，涉及物联网三维空间智能定位与分布式边缘计算支援方法。

背景技术

[0002] 在物联网(Internet of Things)技术的驱动下，越来越多的智能设备接入网络，并被广泛应用于生产生活的各个领域，如执行环境监测、目标跟踪、风险预警等。在很多情况下，这些物联网设备被广泛部署在无人值守甚至具有挑战性的区域中，如森林、沙漠以及军事区域，并需要不断移动以执行既定的任务，如物体的跟踪与识别。然而，许多低成本的物联网节点无法负担全球卫星导航系统(GNSSs)接收器的高昂费用，无法有效使用全球导航定位系统如GPS，北斗导航系统等方式进行定位。物联网设备的移动性、机密性和广泛分布等特点以及所处环境的地形复杂性(多路径、多层效应、不在视线范围内以及移动物体的干扰等)都会为物联网设备定位带来很大的挑战性。为了降低物联网成本，保证物联网的私密性，并为物联网设备提供准确有效的计算支持，需要构建一种三维空间的物联网设备智能定位方案。

[0003] 另一方面，受体积大小和机动性的制约，物联网设备面临有限的存储能力、计算能力、电池寿命和执行任务的时延要求等挑战。首先，在复杂环境中执行任务的物联网设备，其使用寿命极大地受所携带电量的制约。如果扩大设备电池容量会带来高昂的硬件成本，而在执行任务的户外环境中也很难进行反复充电。并且，物联网设备在某个时间可能执行超出其目前硬件能力的复杂任务，需要大型计算处理能力的支援。在有挑战性的区域中地面通信基础结构分布稀疏，无法为节点提供可靠的通信，传统的基于云计算的解决方案无法为其提供有效的计算支持。因此，在当前的物联网研究中，急需寻找一种新的替代方案，如移动边缘计算(Mobile Edge Computing，MEC)技术等。

[0004] 中国专利“CN111726854A一种降低物联网计算卸载能耗的方法”设计了一种基于遗传算法的卸载计算优化方法。此专利利用下一代网络中SDN的概念和边缘计算技术搭建基于边缘云的物联网网络架构；采用排队理论计算系统中处理计算任务的平均时延以及IoT设备本地处理计算任务的平均时延；然后将面向物联网场景的基于时延约束的全局能耗最小化的问题建模为数学问题；设计一种基于遗传算法的卸载计算优化方法求解网络中每个设备的卸载决策以及边缘云服务器开启数量，优化资源配置，降低能耗。该专利的技术方案在无人值守且具有挑战性的区域，如森林、沙漠以及军事区域等场景中，如果产生任务请求的物联网设备数量较多且分布广泛，则此方案得到的结果是加大边缘服务器开启数量，这样无疑会加大边缘服务器的能耗成本；如果物联网区域足够大，则该方案在预部署时会部署多台边缘服务器，以使能覆盖整个物联网区域，但是也许某些服务器一直不会开启，这样会造成硬件成本的浪费。

[0005] 中国专利“CN109788069A物联网中基于移动边缘计算的计算卸载方法”涉及物联网、移动边缘计算、模式选择与节点匹配、动态优化等理论框架。此专利考虑本地卸载、直接云端卸载、设备端卸载、设备中继转发卸载四种计算卸载模式，并增加考虑设备间的社会关系对卸载服务水平的影响以及系统长期动态性能，构建时延和能耗相关的系统长期收益函数，通过模式选择和节点匹配得到物联网中基于边缘计算的计算卸载决策，在时延和能耗性能上达到更好的平衡。所述的技术方案在一些具有挑战性的区域场景中，地面通信基础结构可能分布稀疏，无法为物联网节点提供可靠的通信，所以此专利中的四种计算卸载模式之直接云端卸载不能达到计算卸载的要求。

发明内容

[0006] 为解决上述技术问题，本发明的目的是提供一种物联网三维空间智能定位与分布式边缘计算支援方法，在具有挑战性区域环境中，为物联网设备定位降低物联网成本，保证物联网的私密性，并为物联网设备提供准确有效的计算支持。

[0007] 本发明提供一种物联网三维空间智能定位与分布式边缘计算支援方法，包括：

[0008] 步骤1：获取各个锚节点能耗和与物联网设备的距离信息，为每个物联网设备构建可用锚节点集合；

[0009] 步骤2：根据锚节点间的夹角关系，从可用锚节点集合中选取4个不共面的锚节点构建物联网设备的定位单元集合；

[0010] 步骤3：利用定位单元集合中的锚节点信息，求出物联网设备的定位坐标，并利用多次定位的均值求解目标物联网设备的位置；

[0011] 步骤4：利用搭载边缘服务器的无人机基站动态执行路径规划以处理多个物联网设备的请求，目标为最大化系统的总移动效益，根据边际效用递减定律定义系统效益卸载决策变量的打分函数来决定卸载决策，规划无人机的飞行轨迹；

[0012] 步骤5：无人机按照规划的路径信息航行，同时处理物联网设备的任务需求，无人机处理卸载的计算任务，并更新无人机剩余计算资源。

[0013] 在本发明的物联网三维空间智能定位与分布式边缘计算支援方法中，步骤1具体为：

[0014] 步骤1.1：物联网设备向周围的锚节点发送定位请求广播，包括设备标识和请求时间；

[0015] 步骤1.2：定位请求到达物联网设备通信范围内的锚节点后，锚节点根据发送的时间戳和到达的时间，利用距离偏差模型计算该锚节点与物联网设备的距离，得到相应物联网设备的任务请求和距离信息，并将自身的位置坐标、剩余能量、与该物联网设备的距离信息发送给定位计算中心；

[0016] 步骤1.3：定位计算中心收集和统计各个锚节点位置信息、剩余能量、与物联网设备的距离信息，为每个设备构建备选锚节点集合；

[0017] 步骤1.4定位计算中心判断备选锚节点集合的元素剩余能量是否小于能量阈值，距离信息是否在能保证计算精确的物联网设备有效通信范围内，将能量小于能量阈值和在有效通信范围外的锚节点信息剔除，构建可用锚节点集合。

[0018] 在本发明的物联网三维空间智能定位与分布式边缘计算支援方法中，步骤2具体为：

[0019] 步骤2.1：对于每一个物联网设备的可用锚节点集合中的任意锚节点，利用三角形余弦定理，求取该物联网设备与每两个锚节点之间的距离和夹角；

[0020] 步骤2.2：对每个物联网设备，从对应的备选锚节点集合中选取4个不共面的锚节点，若可用于定位锚节点大于4，则任意选择两个与目标物联网设备的连线夹角趋近于109.4736°的锚节点来构建定位单元，为该物联网设备形成定位单元集合。

[0021] 在本发明的物联网三维空间智能定位与分布式边缘计算支援方法中，步骤3具体为：

[0022] 步骤3.1：针对每个物联网设备，利用其定位单元集合中的锚节点信息，求出每组定位单元所对应的该物联网设备的位置坐标；

[0023] 步骤3.2：通过对每个物联网设备进行多次定位，分别以各自的定位均值对其位置坐标进行修正；

[0024] 步骤3.3：当两次定位的均值误差小于定位阈值时，此时算法趋于收敛，退出定位循环过程，得到物联网设备的准确位置坐标。

[0025] 在本发明的物联网三维空间智能定位与分布式边缘计算支援方法中，步骤4具体为：

[0026] 步骤4.1：定义无人机计算支援系统的总移动效益函数，进而以最大化总移动效益函数为目标进行路径规划；

[0027] 步骤4.2：获取上一时刻无人机的位置坐标集合，以及这一时刻的所有物联网设备的准确位置坐标集合和任务请求集合；

[0028] 步骤4.3：根据边际效用递减定律定义系统效益卸载决策变量的打分函数；

[0029] 步骤4.4：每一个无人机都运行一个无人机代理，无人机代理根据该时刻各物联网设备的位置、卸载决策和维护的移动效益，构建最大移动效益的覆盖集；

[0030] 步骤4.5：选择当前无人机的最大移动效益覆盖集所对应的最优卸载决策和路径方案，即最大移动效益的方案；

[0031] 步骤4.6：对于无任务产生的物联网设备为中心的情况，则根据已得到的有任务物联网设备的卸载决策根据该时刻各物联网设备的位置、卸载决策和维护的移动效益，构建最大移动效益的覆盖集，得出当前最优的卸载决策和路径方案；

[0032] 步骤4.7：物联网设备通过与邻居进行通信与一致性协议来维护和更新自身当前已知的最大效益覆盖集，当物联网设备和他们的邻居对于每一个无人机所维护的最大效益覆盖集一致时停止迭代，得到对应的卸载决策和路径方案。

[0033] 在本发明的物联网三维空间智能定位与分布式边缘计算支援方法中，所述总移动效益函数为：

[0034]

[0035] 其中，xij(t)为t时隙物联网设备ui任务卸载决策变量，当物联网设备ui将任务卸载给无人机vj执行时，xij(t)＝1，否则当xij(t)＝0时，则任务将在本地执行；任务请求只能交给一架无人机执行，卸载决策变量范围即为xij(t)∈{0,1}， 是无人机vj为物联网设备ui执行任务 的系统效益， 为无人机从pj(t‑1)位置到物联网设备ui的位置上方的飞行能耗， 为执行所卸载任务的能耗。

[0036] 在本发明的物联网三维空间智能定位与分布式边缘计算支援方法中，所述系统效益卸载决策变量的打分函数为：

[0037]

[0038] 其中， 表示当前迭代的打分值，Πj是无人机vj的最大覆盖集，即该集合中的任务可以卸载到无人机vj执行， 的定义为：

[0039]

[0040] 其中， 为上次迭代最后加入覆盖集中的用户的打分值， 表示当前迭代执行ui任务的实际CPU频率， 表示上次迭代最后加入最大覆盖集中用户u的执行任务的实际CPU频率。

[0041] 在本发明的物联网三维空间智能定位与分布式边缘计算支援方法中，步骤5具体为：

[0042] 步骤5.1：无人机按照规划的路径信息航行，同时处理物联网设备的任务需求；

[0043] 步骤5.2：无人机处理卸载的计算任务，并更新无人机剩余计算资源。

[0044] 本发明的一种物联网三维空间智能定位与分布式边缘计算支援方法，利用无人机搭载的边缘服务器技术(Unmanned Aerial Vehicle‑enabled Edge Servers，UAV‑Ess)，主动靠近执行任务的物联网设备来满足其计算需求、提高UAV能效并增加系统运行寿命、提高系统机动性。克服了边缘服务器被动服务于物联网节点增加硬件成本和能耗成本、在挑战性环境中因地面通信结构不完善难以为物联网节点提供可靠通信的缺陷。

[0045] 本发明提出的三维空间智能定位和分布式边缘计算支援技术方案中的三维空间智能定位方法可实时获取较为精确的物联网设备位置信息，其分布式边缘计算支援方法提高了物联网设备计算数据卸载量、降低了无人机能耗，提高了服务的设备请求数量。本发明在实验中同时对效益、处理设备请求数、计算能耗、飞行能耗、无人机的资源利用率和移动效益等性能指标进行了评价，均达到了很好的效果，可大大提高系统的实用性。

附图说明

[0046] 图1系统架构图；

[0047] 图2三维空间智能定位示意图；

[0048] 图3三维空间智能定位流程图；

[0049] 图4三维空间智能定位与边缘计算支援流程图；

[0050] 图5为TSIP和iTOA定位误差对比图；

[0051] 图6a为在不同用户数量下系统效益图；

[0052] 图6b为在不同无人机最大计算能力下系统效益图；

[0053] 图7a为在不同物联网设备数量下系统所能处理的物联网设备数目变化图；

[0054] 图7b为在不同无人机最大计算能力下系统所能处理的物联网设备数目变化图；

[0055] 图8a为能耗在不同物联网设备数量下的影响示意图；

[0056] 图8b为能耗在不同无人机最大计算能力下的影响示意图；

[0057] 图9a为在不同物联网设备数量下移动效益的大小变化图；

[0058] 图9b为在不同无人机最大计算能力下移动效益的大小变化图；

[0059] 图10为三个无人机的资源利用率示意图。

具体实施方式

[0060] 本发明提供一种物联网三维空间智能定位与分布式边缘计算支援方法。

[0061] 首先，根据物联网设备的有效通信范围和锚节点的能量信息，构建可用锚节点集合。此外，根据锚节点与物联网设备间的夹角关系构建定位单元，并利用参考点选择定理对定位单元中的锚节点进行选择，利用三维空间定位算法对分散在环境中的移动物联网设备进行智能定位，并通过多次定位的均值对物联网设备的位置坐标进行修正，若满足均值误差小于阈值，则得到物联网设备的位置。

[0062] 然后，利用移动边缘计算技术和搭载边缘服务器的无人机基站动态执行路径规划和计算卸载，以处理多个物联网设备的请求并最大化系统的移动效益。系统以分布式的方式，维护用户效益和节点效益，并构建对于用户的最大移动效益覆盖集。

[0063] 最后，根据最大一致性协议，依次选取系统移动效益最优路径规划和计算卸载方案。若物联网设备的计算负载超过无人机计算能力，则超出的计算任务只能在本地进行处理。

[0064] 本发明的物联网三维空间智能定位与分布式边缘计算支援方法，可以为物联网提供强大的计算能力，提高系统的机动性，增加物联网设备的智能管理和移动性支持，提高系统运行寿命。

[0065] 本申请的网络模型可以分为地面层和边缘层两层。其中，地面层分布了多个执行目标的物联网设备，这些物联网设备可以进行探测危险地形、监测敌军行动和危险预警等。并且，物联网设备根据不同的任务需求(如目标跟踪等)，随机移动并产生任务请求。此外，地面层还部署了多个用于定位的锚节点。边缘层包含了多个不断移动的搭载了边缘服务器的无人机设备。在物联网系统中，设备需要执行大量计算密集型任务。然而，受限于物联网设备自身的计算能力和电池寿命，任务请求需要卸载到提供计算支持的无人机上执行，以满足任务计算需求。在本方案中，任务请求需要尽可能地卸载到无人机上执行，若其计算负载超过无人机计算能力时，任务请求则在本地执行。

[0066] 本发明方案主要包括物联网中三维空间智能定位和分布式边缘计算支援两大部分。其中，三维空间智能定位主要包括获取锚节点能耗和距离信息、构建定位单元、利用多次定位的均值求解目标位置等步骤。分布式计算支援包括动态规划无人机航迹确定计算卸载决策、边缘计算卸载等步骤。具体包括：

[0067] 步骤1：获取各个锚节点能耗和与物联网设备的距离信息，为每个物联网设备构建可用锚节点集合；步骤1具体为：

[0068] 步骤1.1：物联网设备ui向周围的锚节点发送定位请求广播(IDi,Lreqi(t))，其中IDi是物联网设备ui的设备标识，Lreq(t)表示t时刻物联网设备ui的定位请求；

[0069] 步骤1.2：定位请求到达物联网设备通信范围内的锚节点后，锚节点rk根据发送的时间戳和到达的时间，利用距离偏差模型计算该锚节点rk与物联网设备ui的距离 得到相应物联网设备的t时隙的任务请求和距离信息，并将锚节点rk自身的位置坐标pk(t)＝(rk,x,rk,y,rk,z)、剩余能量ek(t)与该物联网设备的距离 等综合信息发送给定位计算中心；

[0070] 步骤1.3：定位计算中心收集和统计各个锚节点位置信息、剩余能量、与物联网设备的距离等信息 为每个设备构建备选锚节点集合H；

[0071] 步骤1.4定位计算中心判断备选锚节点集合H的元素剩余能量是否小于能量阈值距离信息是否在能保证计算精确的物联网设备有效通信范围 内，将能量小于 和在有效通信范围 外的锚节点信息剔除，构建可用锚节点集合Ψi。

[0072] 步骤2：根据锚节点间的夹角关系，从可用锚节点集合中选取4个不共面的锚节点构建物联网设备的定位单元集合，步骤2具体为：

[0073] 步骤2.1：对于每一个物联网设备的可用锚节点集合中的任意锚节点利用三角形余弦定理，求取该未知物联网设备与每两个锚节
点rk，rl之间的距离 和夹角；

[0074]

[0075] 其中， 是锚节点rk和锚节点rl之间的距离。因此，夹角θk,l可以通过下式求出：

[0076]

[0077] 步骤2.2：对每个物联网设备，从对应的备选锚节点集合中选取4个不共面的锚节点，若可用于定位锚节点大于4，则任意选择两个与目标物联网设备的连线夹角趋近于109.4736°的锚节点来构建定位单元，为该物联网设备形成定位单元集合，即：

[0078]

[0079] 其中，为锚节点夹角误差阈值，rk,rl,rh,rg∈Ψi(即rk,rl,rh,rg属于可用锚节点集合，两两互不相等且不共面)，当满足条件时则将定位单元，即锚节点rk,rl,rh,rg的坐标信息记录成一组定位单元M＝{(rk,x,rk,y,rk,z),(rl,x,rl,y,rl,z),(rh,x,rh,y,rh,z),(rg,x,rg,y,rg,z)}，然后将该定位单元放入定位单元集合Θi中，此时的可用定位单元数num＝num+1，其中Θi＝{M1,M2,...,Mnum}。

[0080] 步骤3：利用定位单元集合中的锚节点信息，求出物联网设备的定位坐标，并利用多次定位的均值求解目标物联网设备的位置，步骤3具体为：

[0081] 步骤3.1：针对每个物联网设备，利用其定位单元集合Θi中的锚节点信息M，求出每组定位单元所对应的该物联网设备的位置坐标pi(n)＝(ui,x,ui,y,ui,z)；

[0082] 步骤3.2：通过对每个物联网设备进行多次定位，分别以各自的定位均值对其位置坐标进行修正；

[0083] 具体实施时，通过多次定位的均值 对物联网设备的位置坐标pi(n)进行修正。

[0084] 步骤3.3：当两次定位的均值误差小于定位阈值 时，即满足：时，说明此时算法趋于收敛，退出定位循环过程；得到物联网设备的准确位置坐标[0085] 至此，得出物联网设备ui的坐标pi(t)＝(ui,x,ui,y,ui,z)。最后，可以通过第三方数据库维护分配的IP数据、地标数据、地理热点信息数据、设备协议内容数据等进行辅助定位，对物联网设备坐标进行修正。接下来，将对位置已知的物联网设备的任务请求进行卸载并为其提供计算支持。

[0086] 步骤4：利用搭载边缘服务器的无人机基站动态执行路径规划以处理多个物联网设备的请求，目标为最大化系统的总移动效益，根据边际效用递减定律定义系统效益卸载决策变量的打分函数来决定卸载决策，规划无人机的飞行轨迹，步骤4具体为：

[0087] 步骤4.1：定义无人机计算支援系统的总移动效益函数，进而以最大化总移动效益函数为目标进行路径规划；

[0088] 本发明提出了分布式计算卸载和路径规划方案，优化目标为最大化无人机计算支援系统的总移动效益，即无人机处理物联网设备任务所带来的系统效益与能耗的比值：

[0089]

[0090] 其中，xij(t)为t时隙物联网设备ui任务卸载决策变量，当物联网设备ui将任务卸载给无人机vj执行时，xij(t)＝1，否则当xij(t)＝0时，则任务将在本地执行；任务请求只能交给一架无人机执行，卸载决策变量范围即为xij(t)∈{0,1}， 是无人机vj为物联网设备ui执行任务 的系统效益， 为无人机从pj(t‑1)位置到物联网设备ui的位置上方的飞行能耗， 为执行所卸载任务的能耗。

[0091] 步骤4.2：获取上一时刻t‑1无人机的位置坐标集合pJ(t‑1)，以及这一时刻t的所有物联网设备的准确位置坐标集合pi(t)＝(ui,x,ui,y,ui,z)∈pI(t)和t时刻任务请求集合S(t)；

[0092] 其中， 其中， 分别表示任务类型、任务大小、任务的计算强度，即需要CPU的频率(每个输入位需要的CPU周期数)。

[0093] 步骤4.3：根据动态路径规划算法，规划无人机运行航迹和计算卸载方案。根据边际效用递减定律定义系统效益 的打分函数 系统效益卸载决策变量的打分函数为：

[0094]

[0095] 其中， 表示当前迭代的打分值，Πj是无人机vj的最大覆盖集，即该集合中的任务可以卸载到无人机vj执行， 的定义为：

[0096]

[0097] 其中， 为上次迭代最后加入覆盖集中的用户的打分值， 表示当前迭代执行ui任务的实际CPU频率， 表示上次迭代最后加入最大覆盖集中用户u的执行任务的实际CPU频率。

[0098] 如果当前迭代得到的计算卸载决策发生变化，用户则将自己的卸载决策和对应的打分发送给自己的邻居集合，并接受从邻居传递过来的决策信息，最后通过一致性协议，得到计算卸载决策方案。

[0099] 步骤4.4：每一个无人机vj都运行一个无人机代理，无人机代理根据t时刻各物联网设备的位置pI(t)、卸载决策和维护的移动效益 构建无人机vj的最大移动效益的覆盖集Πj(t)；

[0100] 步骤4.5：选择当前无人机vj的最大移动效益覆盖集Πj(t)所对应的最优卸载决策和路径方案 即最大移动效益的方案；

[0101] 其中，无人机在t时隙的位置集合表示为pJ(t)＝{pj(t)|vj∈V}。时隙t无人机vj的位置为pj(t)＝(vj,x(t),vj,y(t),vj,h(t))。无人机速度为：

[0102]

[0103] 其中，vj(t)不能超过无人机最大速度 即 时隙t无人机加速度为：

[0104]

[0105] 其中，aj(t)不能超过无人机最大加速度 即

[0106] t时隙无人机vj与物联网设备ui之间的信道功率增益为：

[0107]

[0108] 其中，ρ0为vj与ui之间参考距离d0＝1m处接收的信道功率增益。因此，用户ui卸载任务到无人机vj的传输速率可以表示为：

[0109]

[0110] 其中W为带宽，P为传输功率，hij(t)为信道增益，σ2为噪声功率。因此，从ui卸载到vj的数据大小为： 如果任务的大小在当前时隙 内可以完全卸载，则取任务大小 否则计算可以卸载的任务数据量。

[0111] 此外，无人机航行会产生推进能耗，时隙t的推进能量消耗与无人机瞬时加速度和速度有关，计算公式如下：

[0112]

[0113] 其中g表示重力加速度。η1和η2是与飞机重量、机翼面积、空气密度等有关的固定参数。

[0114] 在时隙t中无人机vj计算来自用户ui的任务 计算任务产生的能耗为：

[0115]

[0116] 其中，κ是UAV边缘服务器的有效电容(与硬件相关的常数)， 为CPU实际执行的频率。 为时隙大小。无人机vj的能耗应满足总能耗约束，即
在满足速度、加速度和能耗约束的情况下，可以得出当前vj最优的
卸载决策和路径方案

[0117] 步骤4.6：对于无任务产生的物联网设备为中心的情况(即无人机飞到无任务用户的上方)，则根据已得到的有任务物联网设备的卸载决策根据该时刻t各物联网设备的位置pI(t)、卸载决策和维护的移动效益 构建vj最大移动效益的覆盖集Πj(t)，得出当前vj最优的卸载决策和路径方案

[0118] 步骤4.7：物联网设备通过与邻居进行通信与一致性协议来维护和更新自身当前已知的最大效益覆盖集，当物联网设备和他们的邻居对于每一个无人机所维护的最大效益* *覆盖集一致时停止迭代，得到对应的卸载决策和路径方案(xij(t),pj(t))。
* *

[0119] 此时，判断(xij (t),pj(t))是否满足计算任务时延要求，即 若满足则将系统最优方案的物联网设备ui加入到获胜集中 更新任务集合S(t)，* * * *
并将当前的方案加入最优策略集合(xIJ(t),pJ(t))←(xij(t),pj(t))。

[0120] 步骤5：无人机按照规划的路径信息航行，同时处理物联网设备的任务需求，无人机处理卸载的计算任务，并更新无人机剩余计算资源。步骤5具体为：

[0121] 步骤5.1：无人机按照规划的路径信息航行，同时处理物联网设备的任务需求；

[0122] 当物联网设备将计算任务卸载到搭载边缘服务器的无人机UAV上执行，搭载边缘服务器的无人机vj采用DFVS(Dynamic Frequency and Voltage Scaling，DFVS)技术，其CPU周期频率可以根据计算量的不同而递增或递减，并以最大CPU周期频率 执行任务，k此时需满足 其中， 为单个任务s的执行频率。

[0123] 步骤5.2：无人机处理卸载的计算任务，并更新无人机剩余计算资源fj(t)。UAV边缘服务器可以满足任务的要求并充分利用UAV边缘服务器资源。

[0124] 下面结合具体算法伪代码、实验平台和实验结果详细阐述本发明的技术方案。

[0125] 本发明的三维空间智能定位算法，即算法1的伪代码如下所示：

[0126]

[0127]

[0128]

[0129] 本发明使用分布式边缘技术方法来解决UAVs动态路径规划和计算卸载过程，算法3的伪代码如下所示：

[0130]

[0131]

[0132] 本发明仿真实现基于MTALAB平台，在仿真场景中，设置了3个搭载边缘服务器的无人机，以及1000个物联网设备随机分布，构建了一个1000×1000×50的三维空间，其中111个锚节点定期部署，1000个物联网节点随机下落并不断移动，3架无人机也在移动，为物联网节点提供计算支持。每台服UAV搭载边缘服务器配置多个CPU核，最大计算能力物联网服务大小 在[0.5，2.5]Mbit内均匀分布，所需计算强度在[500,1000]cycles/bit内均匀分布。另外，为了更好地模拟用户的移动，我们选择了两种移动模型，包括基于地图的移动模型和随机游走模型，其中40％的用户利用基于地图的移动模型，60％的用户基于随机游走模型，用户在移动过程中以0.5的概率随机产生服务请求，综合评价算法的性能。模拟了1000个时隙，并使用了常用的准静态网络场景，在一个时间段内，无人机和物联网节点的位置是固定的，但它们的位置可能在不同的时间段发生变化。

[0133] 参数列表如表1所示：

[0134] 表1参数设置

[0135]

[0136] 同时在本专利的仿真验证时设置了对比算法。为了评价效益、处理的用户请求数、计算能耗、飞行能耗、无人机的资源利用率和移动效益六种性能指标，分别对UGDA(基于贪心的效益最大化)、MUFA(最大效益优先)、NUFA(最近用户优先)、ROA(随机优化算法)、CFCA(圆形的固定周期运动)以及本专利提出的DCOP(分布式计算卸载和路径规划算法)在MATLAB平台上进行对比实验。

[0137] 图5显示了定位误差。三维空间智能定位算法(Three‑dimensional Space Intelligeht Positioning,TSIP)的定位误差低于对比算法到达时间迭代算法(iterative Time‑of‑arrival,iTOA)。因为TSIP在构建定位单元时，不仅考虑了锚节点的可用性，还考虑了锚节点和物联网设备之间的角度，提升了定位精度。

[0138] 图6a和图6b显示了在不同物联网设备数量(用户)、不同无人机最大计算能力下系统效益的变化。我们的系统效益逼近MUFA算法，高于其它对比算法，原因是DCOP算法考虑了用户卸载的数据量和资源的占比情况，并且执行最大效益覆盖集，提升了系统效益。

[0139] 图7a和图7b显示了在不同物联网设备数量、不同无人机最大计算能力下系统所能处理的物联网设备数目的变化。由图7(a)可以见得随着物联网设备数量的增多，处理的物联网设备数量逐渐增加并趋于稳定。由图7(b)可见无人机处理的物联网设备数量随着无人机最大计算能力的增加而逐渐增加。原因是DCOP算法通过构建最大效益覆盖集和一致性协议，合理的规划了无人机航迹，增加了接纳的物联网设备请求数。

[0140] 图8a和图8b显示了能耗在不同物联网设备数量、不同无人机最大计算能力下的影响，从图8(a)(b)中可得出，随着物联网设备数目的增多或无人机最大计算能力的增加，虽然物联网设备移动的随机性使得无人机能耗在不同实验条件下具有一定的波动性，DCOP算法能耗的均值低于对比算法。

[0141] 图9a和图9b显示了在不同物联网设备数量、不同无人机最大计算能力下移动效益的大小变化，显示了随着物联网设备数目和无人机最大计算能力的增加，DCOP算法的移动效益也随之增加并趋于稳定，明显高于其他对比算法。原因是DCOP在构建最大效益覆盖集的时候，不仅考虑了数据的卸载量还考虑了无人机的能耗，提升了系统的移动性效益。

[0142] 图10显示了不同算法的3个无人机计算资源的利用率。

[0143] 表2展示了对不同数量的物联网设备的两种方法定位误差。

[0144] 表2定位误差

[0145]

[0146] 考虑到物联网的移动性，我们首先提出了TSIP算法，该算法根据所提出的信标节点选择定理合理构造定位单元，并对物联网的位置进行修正。然后，针对多个物联网和无人机造成的系统复杂性，提出了DCOP算法。通过物联网之间的通信和共识协议，构建并维护无人机的最大效用覆盖集，提高系统的移动性效用。仿真结果表明，本专利提出方案可以实时地获取较为精确物联网设备位置信息，同时，提高了物联网设备计算数据卸载量、降低了无人机能耗，提升了服务的用户请求数量。本专利提出的方案大大提高了系统的实用性，有效降低了无人机的能耗，最大化无人机计算支援系统的总移动效益，实现了物联网设备高效、动态的计算支持。

[0147] 以上所述仅为本发明的较佳实施例，并不用以限制本发明的思想，凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。