固定站点与无人机搭载边缘服务器的协同部署方法

1.本发明涉及车联网边缘计算领域，具体涉及一种固定站点与无人机搭载边缘服务器的协同部署方法。

背景技术：

2.边缘计算被公认为未来智慧车联网的核心使能技术之一。边缘计算使计算和存储能力下沉至车联网边缘，贴近车辆，从而提供低延迟、高吞吐、面向海量连接的计算服务。在未来的5g车联网时代，大量的边缘计算服务器将被部署于路边单元(rsu)、固定、路灯、甚至无人机(uav)上，贴近为车辆提供计算服务，终端车辆的计算请求也将在这样的本地边缘服务器上完成，降低反应时延。
3.边缘计算服务器部署是自动驾驶数字交通基础设施建设的重要组成部分，同时又是一个复杂的系统工程，需要综合考量部署载体、部署位置、覆盖范围、优化目标、车辆行为等多种要素。现今，该问题在国内外的研究和应用仍处于起步阶段，存在大量理论和应用上的挑战性问题。最简单直接的办法是将边缘服务器部署于现有的网络，成为固定位置的本地边缘服务器。凡进入覆盖范围的车辆产生的计算需求都交由本地边缘服务器处理。但是，车联网终端(节点/用户)是行驶的车辆，产生持续、实时和高强度的计算需求。车辆的高速移动会造成负载的时空动态变化；而上述固定站点部署方式中边缘服务器的位置、覆盖范围和计算能力一但确定很难更改，难以跟上动态的负载变化。例如在某一时刻，a地车流较大，b地较小时，a地的边缘计算服务器可能超载，而b地的边缘计算服务器能力较多空闲。经过一段时间后，车流负载发生变化，a地车流较小，b地较大时，情况会发生翻转，但是依然造成上述的服务器超载或利用率低等问题，即服务器的固定静态部署方式无法满足动态负载的要求。
4.移动单元搭载边缘服务器可以解决固定站点方式不能有效对车辆位置和负载的动态变化进行跟踪的问题，但如何选择合适的载体并规划适当的路径仍是领域内的开放问题。相比于单纯固定站点部署方式，无人机部署具有速度快、抵达负载热点迅速的特点。zhou设计了一种使用无人机对区域内分布的用户进行无线充电和计算卸载服务的方案。区域内的用户负载固定，单个无人机依次移动到用户附近进行服务。其轨迹规划问题被建模为一个非凸整数优化问题，最大化用户任务卸载速率，使用连续凸逼近(sca)方法求解，并对1台无人机和4个用户的小规模场景进行了验证。jeong研究了类似场景，使用了相同的方法，优化目标是能耗。加拿大皇家科学院、工程院院士、滑铁卢大学sherman shen教授提出了未来的“空天地一体化车联网体系架构”。路面车辆和相关基础设施构成地基网络，与在轨卫星构成的天基、平流层飞艇或无人机等空中飞行器构成的空基网络一起，融合成为一个空天地一体化立体空间信息网络。基于这一思想，cheng提出用无人机来辅助进行数据转发，主要从通信和数据传输的角度规划无人机移动路径，最大化数据传输率。其考虑3个单元的小规模场景，用户负载固定，建模和求解方法也类似。胡面向校园部署场景，提出一种基于arima－xgboost混合模型预测的无人机部署机制，根据负载预测值决定每个
时间段无人机的分派数量和位置，辅助进行计算卸载，解决网络负载不均的问题。cheng面向车联网场景，提出了空地一体化的边缘计算架构，前瞻性的指出无人机搭载边缘计算服务器具有快速跟踪动态负载的能力，但没有给出具体的问题模型和解决方案。wang研究使用无人机和地面协同处理北京欢乐谷游客的动态计算需求，最大化任务卸载成功率，并设计贪心法求解。
5.现有技术存在的问题是：
6.多数工作将固定站点和移动单元方案割裂处理，缺乏协同机制；已有工作仅针对少量无人机、小规模问题场景；已有工作基本针对静态负载，即地图上各区域的负载恒定，无人机规划路径对各区域依次进行服务。

技术实现要素：

7.本发明的目的是提供一种固定站点与无人机搭载边缘服务器的协同部署方法，主要用于解决固定站点部署方式不能跟随时空动态变化的负载这一问题。
8.为了实现上述任务，本发明采用以下技术方案：
9.一种固定站点与无人机搭载边缘服务器的协同部署方法，引入无人机搭载边缘计算服务器作为移动单元部署方式，与固定站点搭载边缘服务器构成的固定站点部署方式配合，进行移动单元部署策略的设计以及移动路径的规划，协同解决负载时空动态变化的问题；所述方法包括：
10.获取待部署区域的历史数据并加以精炼：将整个待部署区域的地图划分为若干栅格；划分栅格后，将时间离散化，划分为若干时隙，然后将历史数据中的所有的gps记录归纳到对应的栅格和时隙中去，即可得到任一栅格任一时隙内的gps记录数量总和；将所有栅格在某时隙内的负载用向量表示，则多个时隙对应的负载向量构成栅格化负载序列；
11.进行固定站点的部署：对负载非零的有效数据栅格进行分簇，栅格之间的距离定义为欧氏距离，各簇中心为固定站点边缘服务器的放置位置，各簇的栅格为所述固定站点边缘服务器的覆盖范围；以各个边缘服务器分配的计算能力为待求解未知量，以最大化固定站点可承担的负载总和为目标函数，构建约束条件并且求解目标函数，得到固定站点边缘服务器计算能力的分配结果，其中：
[0012][0013][0014][0015][0016][0017][0018]
上式中，wl
rsu
表示固定站点可承担的负载总和，设将栅格分为k簇，时间段分为t个时隙，时隙t＝1,
…
,t；簇k在t时隙的负载为簇k分配的计算能力为ck，定义μk(t)为一个0-1指示变量，表示第t时隙簇k的计算能力是否完全满足负载，其中μk(t)＝1表示完全
满足；对任一时隙，完全满足负载的簇应大于k
′
个；
[0019]
进行移动单元的部署，包括单时隙无人机悬停位置分派、时隙间无人机路径规划；其中：
[0020]
对于单时隙无人机悬停位置分派，首先对目标时隙t所有栅格的负载进行感知或预估；对于目标时隙t，用前一个时隙t-1，或者前一个时隙后20％～50％时间的数据对目标时隙t的负载进行预估；得到每个栅格的负载预估值后，将各簇固定站点的计算能力按栅格负载预估值比重分配至各栅格；各栅格的预估负载减去分配的计算能力，得到所有栅格i的剩余负载w
′i(t)；基于此剩余负载，以及无人机的覆盖半径r
uav
确定分派位置；
[0021]
对于时隙间无人机路径规划，当时隙t-1和下一时隙t的无人机悬停位置都确定后，以无人机的整体移动距离最短为原则，考虑到时隙t-1和下一时隙t无人机需求量的不同，进行时隙t-1的悬停位置移动到下一时隙t的路径的规划。
[0022]
进一步地，所述栅格的规格为1km*1km，也可以根据粒度需要进行灵活调整；
[0023]
对地图上的所有栅格进行检查，如栅格从来没有产生负载，说明此区域从来没有出现过车辆，没有分析的必要，将此栅格删去；所有剩下的栅格构成有效数据区域。
[0024]
进一步地，对于所述目标函数，引入一组新变量zk(t)来表示采用线性松弛+分支搜索的方法进行求解，考虑可用无人机的数量m，要想使得任意时隙所有的负载都得到服务，必须满足k
′
+m≥k，这样，当k-k
′
个簇发生计算短缺时，可以使用m≥k-k
′
个无人机加以补偿；根据可用无人机的数量和能力，确定k
′
的值，继而对目标函数进行求解，从而得到分配给各簇的固定站点边缘服务器分配的计算能力ck。
[0025]
进一步地，所述单时隙无人机悬停位置分派，具体包括单时隙单无人机位置分派；
[0026]
对于单时隙单无人机位置分派，问题的已知量为：t-1时隙无人机分派的栅格集合t时隙地图的剩余负载{w
′i(t)}，其中w
′
(t)表示栅格i的剩余负载，无人机的计算能力c
uav
，无人机的覆盖半径r
uan
，以及两两栅格之间的距离d
i,j
；需要输出的结果为：t时隙无人机的分派栅格g
x
，该无人机的承担负载wl，以及该无人机分派并承担负载后更新的地图上的剩余负载w
′
(t)；令(t)；令表示将无人机放在栅格gi上时，所有栅格的剩余负载，表示将无人机放在栅格gi上时，栅格j的剩余负载；
[0027]
(1)首先尝试上一个时隙的所有无人机的分派栅格把无人机放在中的每个栅格，若无人机的计算能力小于或等于其覆盖半径内的栅格剩余负载总和，即条件1，则直接选择此栅格为时段t的分派栅格g
x
，该无人机对应的承担负载wl＝c
uav
，以及更新后的剩余负载；
[0028]
(2)若所有的栅格都不满足上述条件1，则尝试地图上所有栅格并选择一个承担负载最大的作为分派栅格；
[0029]
(2-1)将无人机依次放在地图中的每个栅格gi并计算其对应的承担负载
[0030]
(2-1-1)初始化无人机剩余计算能力为c
cur
＝c
uav
，承担负载为地图的剩余负载
[0031]
(2-1-2)出无人机覆盖半径内所有栅格的集合
[0032]
(2-1-3)对按到栅格gi的距离升序排序；
[0033]
(2-1-4)依次对中的每个栅格gj：
[0034]
a)减去gj栅格的负载：wj′
(t)表示栅格j的剩余负载；
[0035]
b)更新无人机的承担负载：
[0036]
c)更新无人机的剩余计算能力：c
cur
＝c
cur-min(c
cur
,wj′
(t))；
[0037]
d)检查c
cur
是否为0？如是，则说明无人机已没有剩余计算能力，结束步骤；
[0038]
(2-2)返回步骤(2-1)中的的最大值对应的悬停位置即无人机分派栅格更新后的剩余负载，g
x
就是无人机分派栅格，得解；其中，表示将无人机放置于不同的栅格gi时对应的承担负载中的最大值；
[0039]
进一步地，若步骤(2-2)中的最大值不唯一，即有多个这样的g
x
，标记为集合{gy}，则选择到t-1时隙无人机位置集合距离最小的栅格；当t＝1时，即第一个时隙，略过此步；
[0040]
(3-1)定义gy到的距离为gy到所有栅格中距离最小的值所有栅格中距离最小的值其中，表示z是中任一栅格，表示从集合中寻z栅格到gy栅格距离最小的那个距离，d
y,z
为gy中的栅格与z栅格之间的距离；
[0041]
(3-2)在所有的gy中选择使得最小的gy作为无人机分派栅格；
[0042]
(3-3)返回上述g
x
作为无人机分派栅格，得解。
[0043]
进一步地，所述单时隙无人机悬停位置分派，具体还包括单时隙多无人机位置分派；
[0044]
对多个无人机的位置分派基于单无人机位置分派方法；设无人机数量为m，在时段t，依次执行单时隙单无人机位置分派方法，直到所有的m个无人机全部分派完毕，或者地图上所有的剩余负载都被承担为止。
[0045]
进一步地，所述时隙间无人机路径规划，包括：
[0046]
1)时隙t-1和时隙t所需无人机数量相等
[0047]
即地图上的整体负载基本不变，两个时段使用相同数量的无人机，将这一问题建模成带权二分图的最小匹配问题，二分图左侧节点是时隙t-1的栅格，右侧节点为时隙t的栅格；节点之间的边都是带权边，权值为相应栅格之间的欧氏距离；则路径规划问题转化为求该带权二分图的最小匹配，即最小化无人机移动距离之和，可以用匈牙利算法在多项式时间内求解；
[0048]
在此基础上，进一步考虑无人机的飞行距离限制，即无人机不可能在短时间内跨越较大距离，设定距离阈值，将不满足距离阈值的栅格从二分图中删去，然后对二分图求带权最小匹配，即可得到考虑无人机飞行距离限制的最小无人机移动路径；
[0049]
2)时隙t-1所需无人机数量大于时隙t
[0050]
此时仍可按1)中的方法构建二分图，所得的最小带权匹配仍然会使得右侧节点被全部覆盖，而左侧会有节点未被匹配覆盖；此时，认为未被覆盖的无人机不再需要，转为休眠状态，在原悬停栅格中选择一栋高楼楼顶降落该无人机，以节约能量；
[0051]
3)时隙t-1所需无人机数量小于时隙t
[0052]
此时，需要将原有休眠的无人机唤醒，唤醒位置即上一次休眠的位置，将节点补充进二分图的左侧；当系统追加新采购的无人机时，可以将无人机预先分配到指定位置休眠；构建二分图时，即以这些休眠位置为起点构造二分图左侧，构造完毕后，求二分图的最小带权匹配，得到无人机的移动路径。
[0053]
与现有技术相比，本发明具有以下技术特点：
[0054]
本发明针对城域车联网场景下的负载随时空动态变化的问题，利用数学方法对固定站点和移动单元进行协同部署，更具实用价值，且针对问题更实际、全面，可有效降低计算能力的总采购成本，解决固定站点部署方式不能跟随时空动态变化的负载这一问题，同时可降低无人机的能耗。
附图说明
[0055]
图1为固定站点与无人机搭载边缘服务器协同部署场景；
[0056]
图2为栅格化与数据精炼的示意图；
[0057]
图3为上海市有效数据栅格k-means聚类结果(分为30个簇)；
[0058]
图4为单时隙无人机悬停位置规划示意图；
[0059]
图5为时隙间无人机路径规划示意图，其中a)为问题描述，b)为转化为二分图问题，c)为考虑飞行距离限制的示意图；
[0060]
图6为时隙t-1所需无人机数量大于时隙t的示意图；
[0061]
图7为时隙t-1所需无人机数量小于时隙t的示意图。
具体实施方式
[0062]
本发明提供了一种使用无人机与固定站点部署边缘计算服务器的协同方法，根据部署载体是否移动，边缘服务器部署可分为固定站点和移动单元两种方式。边缘服务器可部署于固定位置，如5g、路边单元(rsu)等，即固定站点部署方式(本发明统称为rsu方式)。也可以部署于无人机或移动车辆上，称为移动单元部署方式。单纯固定站点部署方式由于不能移动，无法解决负载时空动态变化的问题。本发明考虑引入无人机这一移动载体搭载边缘计算服务器节点，规划合理的移动路径，让这部分边缘服务器移动起来，动态跟随车联网中的负载(即移动车辆)，同固定站点边缘服务器协同解决上述问题。
[0063]
本发明所应用的场景为一个车联网覆盖的地理区域，区域内已部署有移动网络，有大量移动的车联网节点，即车辆。这些车辆产生连续、大量的计算任务，但车辆本身的计算能力有限，需要将计算任务发送到附近的边缘服务器执行、取回计算结果，再根据计算结果决定下一步动作。本发明针对的问题就是如何部署这样的边缘服务器，确定部署的载体、位置或移动路径，使得车联网节点的计算需求能够尽可能得到就近服务。由于预算限制，可部署的固定站点边缘服务器数量k和总采购计算能力c
sum,rsu
有限，可分派的无人机数量m、每台无人机的计算能力c
uav
和覆盖半径r
uav
也有限。在这些限制之下，设计k个固定站点边缘
服务器和m台无人机搭载边缘服务器的协同部署方法，服务车联网产生的时空变化的计算负载。如图1所示，该示例中除k＝3套部署于固定站点的边缘服务器a、b、c外，又增加包含m＝2台无人机的无人机移动单元搭载边缘服务器d、e，对移动中的车辆进行动态跟踪服务。
[0064]
参见附图，本发明提供的一种固定站点与无人机搭载边缘服务器的协同部署方法，包括以下步骤：
[0065]
步骤1，栅格化与数据精炼
[0066]
首先，获取待部署区域的历史数据(如上海市区的车流交通数据集)并加以精炼。一个典型的交通数据集由大量车辆在不同时刻的gps位置记录组成，每条记录包括时刻，车辆的位置(用经纬度表示)等信息。数据精炼主要是地图和数据的栅格化。将整个待部署区域的地图划分为若干小方格，称为栅格，规格为1km*1km(此规格根据粒度需要可以灵活调整)。划分栅格后，将时间离散化，划分为若干时隙(time slot，又称时间片)，如每半小时为一个时隙，可将一天时间划分为48个时隙。然后将所有的gps记录归纳到对应的栅格和时隙中去，即可得到任一栅格任一时隙内的gps记录数量总和。此数据可用来衡量某栅格在某一时隙的车流密度，并估算对应的计算任务负载。
[0067]
例如，设每生成1条gps记录的时间，单个车联网节点产生c
g2c
的计算需求；若某栅格i在时隙t记录到ni(t)条gps记录，则其计算需求(即负载)为c
g2c
·
ni(t)(在实际系统中，可以使用实际产生的计算任务数历史数据来替代上述用gps记录估算的方式)。对地图上的所有栅格进行检查，如栅格从来没有产生负载，说明此区域从来没有出现过车辆(如水域)，没有分析的必要，在后续过程中将此栅格删去；所有剩下的栅格构成有效数据区域。如图2所示，完成栅格化和上述数据精炼后，将每个栅格在某时隙内的负载用向量表示，则多个时隙对应的负载向量构成栅格化负载序列，反映不同时段地图上不同栅格的负载变化。
[0068]
步骤2，固定站点部署策略
[0069]
基于上述栅格化负载序列，确定固定站点边缘服务器的部署。本发明对于固定站点的部署位置和覆盖范围不做特别要求，只要求将待部署区域的地图划分若干区域，每个区域即一套边缘服务器所覆盖的范围；地图划分在部署完毕后不再改变。举例采用一个简单而典型的做法：k-means分簇。在此基础上，考虑配合无人机的部署，优化分配各固定站点的计算能力。
[0070]
2.1k-means聚类
[0071]
采用k-means方法，对有效数据栅格(负载非0)进行分簇。栅格之间的距离定义为欧式距离，分簇数目为事先给定值，根据部署预算和规划征地情况制定。各簇中心为边缘计算服务器放置位置，各簇栅格为其覆盖范围。
[0072]
在图3的例子中，上海市地图被分为4800个栅格，其中有4318个有效栅格。对这4318个有效栅格进行k-means分簇，划分为30个簇，星号为边缘计算服务器放置位置，即簇的几何中心。此放置位置可以进一步优化为重心，即将负载作为各簇权重，计算簇的重心，此优化可保证边缘计算服务器偏向负载集中的区域。
[0073]
2.2固定站点边缘服务器计算能力分配
[0074]
设可采购的总计算能力为c
sum,rsu
，此值由投资方事先给定，即初始在计算能力上的投资上限。问题即在这一总计算能力限制下，将c
sum,rsu
分配给各簇的固定站点边缘服务
器，使得边缘服务器可以满足的负载最大化。另外，考虑与无人机的协同，必须保证在各时段，地图上多数簇的负载能够被固定站点边缘服务器计算能力满足，少量不能满足的簇交由无人机进行跟踪补偿。
[0075]
设将栅格分为k簇，时间段分为t个时隙，时隙t＝1,
…
,t。簇k在t时隙的负载为即簇内所有栅格的负载之和。簇k分配的计算能力为ck(待求解)，定义μk(t)为一个0-1指示变量，表示第t时隙簇k的计算能力是否完全满足负载，其中μk(t)＝1表示完全满足，即此时对任一时隙，完全满足负载的簇应大于k
′
个，即这k
′
个簇是不需要无人机辅助的。为保证任何时隙的负载都能得到服务，必须k-k
′
≤m，m为可用无人机数量。即在实际配置中，k
′
取一个不小于k-m的值。上述问题可以建模为混合0-1规划问题如下：
[0076][0077][0078][0079][0080][0081][0082]
问题的优化目标为wl
rsu
，最大化固定站点可承担的负载总和。约束1：所有簇分配的计算能力之和不大于总计算能力为c
sum,rsu
；约束2、3表明完全满足负载的簇数量应大于k
′
个；约束4表明各簇分配的计算能力非负；约束5表明μk(t)为0-1变量。为求解上述问题，引入一组新变量zk(t)，原问题可转化为：
[0083][0084][0085][0086][0087][0088][0089][0090][0091]
该问题是一个标准的整数线性规划问题，可用一般优化工具包求解，即线性松弛+分支搜索。
[0092]
该优化问题的使用方法是：
[0093]
考虑可用无人机的数量m，要想使得任意时隙所有的负载都得到服务，必须满足k
′
+m≥k，即固定站点计算充足的簇数与可用无人机数之和不小于簇总数。这样，当k-k
′
个簇发生计算短缺时，可以使用m≥k-k
′
个无人机加以补偿。若m《k-k
′
，则无论如何也不可能满足所有负载要求。因此，根据可用无人机的数量和能力，确定k
′
的值，继而对上述问题进行求解，从而得到分配给各簇的固定站点边缘服务器分配的计算能力ck。
[0094]
步骤3，移动单元(无人机搭载边缘服务器)部署策略
[0095]
无人机搭载边缘计算服务器部署由两部分构成：
[0096]
第一部分，对每个时隙规划无人机的分派位置，覆盖计算能力不足的栅格区域。
[0097]
第二部分，不同时隙之间，规划无人机的移动路径，降低移动开销。其中，可分派的无人机数量m、每台无人机的计算能力c
uav
和覆盖半径r
uav
均为事先给定值。
[0098]
3.1单时隙uav悬停位置分派
[0099]
问题如图4所示。整个待部署区域的地图在固定站点对负载进行服务以后，由于固定站点的计算能力有限，在某些时隙(目标时隙t)，可能存在超出固定站点能力外的剩余负载需要服务(负载热点地域)，如图4的所示，需要用无人机对这些热点栅格进行覆盖和服务。使用一定数量的无人机，分布在地图的不同位置，对这些负载热点进行覆盖，保证尽可能多的负载得到服务。
[0100]
算法主要思想如下：
[0101]
首先对目标时隙t所有栅格的负载进行感知或预估，例如对于目标时隙t，可以用前一个时隙t-1，或者前一个时隙后20％～50％时间的数据对目标时隙t的负载进行预估。得到每个栅格的负载预估值后，将各簇固定站点的计算能力按栅格负载预估值比重分配至各栅格。各栅格的预估负载减去分配的计算能力，得到所有栅格i的剩余负载w
′i(t)(当预估负载小于分配的计算能力时，剩余负载w
′i(t)为0)；基于此剩余负载，以及无人机的覆盖半径r
uav
确定分派位置；用w
′
(t)＝{w
′i(t)}表示t时隙所有的栅格(i＝1...n)的剩余负载。
[0102]
3.1.1单时隙单无人机位置分派
[0103]
首先考虑单个无人机的位置分派。问题的已知量为：t-1时隙无人机分派的栅格集合t时隙地图的剩余负载{w
′i(t)}，其中w
′i(t)表示栅格i的剩余负载，无人机的计算能力c
uav
，无人机的覆盖半径r
uav
，以及两两栅格之间的距离d
i,j
。需要输出的结果为：t时隙无人机的分派位置(栅格)g
x
，该无人机的承担负载wl，以及该无人机分派并承担负载后更新的地图上的剩余负载w
′
(t)＝{w
′i(t)}；令表示将无人机放在栅格gi上时，所有栅格的剩余负载，表示将无人机放在栅格gi上时，栅格j的剩余负载。
[0104]
算法的主要思想为：首先尝试上一个时隙的所有无人机的悬停栅格若负载变化不大，则尽量使无人机不移动，继续使用上一个时隙的悬停位置，节约移动能耗；否则，尝试地图上所有栅格作为悬停位置，选择一个承担负载最大的栅格。若有多个这样的栅格，则从中选一个到t-1时隙无人机悬停栅格最近的作为新的分派栅格。具体步骤如下：
[0105]
(1)首先尝试上一个时隙的所有无人机的分派栅格把无人机放在中的每个栅格，若无人机的计算能力小于或等于其覆盖半径内的栅格剩余负载总和(条件1)，则直接选择此栅格为时隙t的分派栅格g
x
，该无人机对应的承担负载wl＝c
uav
，以及更新后的
剩余负载此步骤的目的为尽最大可能避免无人机移动，节约能量；当t＝1时，即第一个时隙，略过此步；
[0106]
(2)若所有的栅格都不满足上述条件(条件1)，则尝试地图上所有栅格并选择一个承担负载最大的作为分派栅格。
[0107]
(2-1)将无人机依次放在地图中的每个栅格gi并计算其对应的承担负载
[0108]
(2-1-1)初始化无人机剩余计算能力为c
cur
＝c
uav
，承担负载为地图的剩余负载(对所有j，)；w
′j(t)表示栅格j的剩余负载，表示为将无人机放在栅格g
t
上时，栅格j的剩余负载。
[0109]
(2-1-2)出无人机覆盖半径内所有栅格的集合
[0110]
(2-1-3)对按到栅格gi的距离升序排序；
[0111]
(2-1-4)依次对中的每个栅格gj：
[0112]
a)减去gj栅格的负载：
[0113]
b)更新无人机的承担负载：
[0114]
c)更新无人机的剩余计算能力：c
cur
＝c
cur-min(c
cur
,wj′
(t))；
[0115]
d)检查c
cur
是否为0？如是，则说明无人机已没有剩余计算能力，结束步骤；
[0116]
(2-2)返回步骤(2-1)中的的最大值对应的悬停位置即无人机分派栅格更新后的剩余负载更新后的剩余负载得解；其中，表示将无人机放置于不同的栅格gi时对应的承担负载中的最大值。
[0117]
(3)特殊处理：若步骤(2-2)中的最大值不唯一，即有多个这样的g
x
，标记为集合{gy}，则选择到t-1时隙无人机位置集合距离最小的栅格；当t＝1时，即第一个时隙，略过此步。
[0118]
(3-1)定义gy到的距离为gy到所有栅格中距离最小的值所有栅格中距离最小的值其中，表示z是中任一栅格，表示从集合中寻z栅格到gy栅格距离最小的那个距离，d
y,z
为gy中的栅格与z栅格之间的距离。
[0119]
(3-2)在所有的gy中选择使得最小的gy作为无人机分派栅格；
[0120]
(3-3)返回上述g
x
作为无人机分派栅格，对应的承担负载以及更新后的剩余负载得解。
[0121]
3.1.2单时隙多无人机位置分派
[0122]
对多个无人机的位置分派基于单无人机位置分派方法。设无人机数量为m，在时段t，依次执行上述单无人机分派位置规划，直到所有的m个无人机全部分派完毕，或者地图上所有的剩余负载都被承担为止。
[0123]
另：每一天的第一个时隙t＝1开始前，需要确定无人机的初始分布位置。初始分
布有三种选择：1、随机分布；2、选择几个固定站点放置(站点建设充电器，同时完成充电)；3、根据历史负载信息通过执行步骤3.1.2计算放置位置。无人机位置确定以后，在凌晨由卡车将无人机运至指定栅格(或者由无人机自己飞行到指定位置)，为时隙t＝1的分派做好准备。当系统追加新采购的无人机时，按上述步骤在每一天的第一个时隙t＝1开始前同其他已有无人机一起部署。
[0124]
3.2时隙间uav路径规划
[0125]
当时隙t-1和下一时隙t的无人机悬停位置都确定后，需要规划从时隙t-1的悬停位置移动到下一时隙t的路径。为了节约无人机的能量，并且使得无人机快速移动到下一悬停位置，应使得无人机的整体移动距离最短。考虑三种情况：
[0126]
1)时隙t-1和时隙t所需无人机数量相等。
[0127]
即地图上的整体负载基本不变，两个时段使用相同数量的无人机。举例如图5a，需要将时隙t-1的3个无人机从相应位置移动到时段t的3个位置。将这一问题建模成带权二分图的最小匹配问题，如图5b。二分图左侧节点是时隙t-1的3个栅格，右侧节点为时隙t的3个栅格。节点之间的边都是带权边，权值为相应栅格之间的欧氏距离。则路径规划问题转化为求该带权二分图的最小匹配，即最小化无人机移动距离之和，可以用匈牙利算法在多项式时间内求解。在此基础上，进一步考虑无人机的飞行距离限制，即无人机不可能在短时间内跨越较大距离。设定该阈值为3，则g
10
到g
32
，g
19
到g
24
，g
23
到g2这3条边不满足这一限制，因此将其从二分图中删去，如图5c。对图5c中的二分图求带权最小匹配，即可得到考虑无人机飞行距离限制的最小无人机移动路径。
[0128]
2)时隙t-1所需无人机数量大于时隙t。
[0129]
即地图上的整体负载发生变化，原先需要较多的无人机，而现在由于整体负载下降，使用较少的无人机即可满足系统要求，举例如图6。此时仍可按情形1)中的方法构建二分图，所得的最小带权匹配仍然会使得右侧节点被全部覆盖，而左侧会有节点未被匹配覆盖。此时，认为未被覆盖的无人机不再需要，转为休眠状态，在原悬停栅格中选择一栋高楼楼顶降落该无人机，以节约能量。
[0130]
3)时隙t-1所需无人机数量小于时隙t。
[0131]
即地图上的整体负载发生变化，原先的无人机不够用，需要追加无人机以服务更高的负载，举例如图7。此时，需要将原有休眠的无人机唤醒，唤醒位置即上一次休眠的位置，将节点补充进二分图的左侧。构建二分图时，即以这些休眠位置为起点构造二分图左侧。构造完毕后，求二分图的最小带权匹配，得到无人机的移动路径。
[0132]
本方法可应用车联网场景，通过固定站点和移动单元协同部署来承担车联网节点产生的负载。首先基于历史信息，根据步骤2(固定站点部署策略)，在地图上部署k套边缘计算服务器。部署完毕后，当系统开始实际运行时，实时感知车流量变化，根据前一个时隙最后20％时间的流量强度预测下个时隙的流量(预测方法可以自选)；然后根据步骤3.1单时隙uav悬停位置分派，规划下一个时隙无人机的分派位置栅格，根据步骤3.2时隙间uav路径规划，确定从前个时隙到下个时隙的无人机移动路线。
[0133]
以上实施例仅用以说明本技术的技术方案，而非对其限制；尽管参照前述实施例对本技术进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者
替换，并不使相应技术方案的本质脱离本技术各实施例技术方案的精神和范围，均应包含在本技术的保护范围之内。

技术特征：

1.一种固定站点与无人机搭载边缘服务器的协同部署方法，其特征在于，引入无人机搭载边缘计算服务器作为移动单元部署方式，与固定站点搭载边缘服务器构成的固定站点部署方式配合，进行移动单元部署策略的设计以及移动路径的规划，协同解决负载时空动态变化的问题；所述方法包括：获取待部署区域的历史数据并加以精炼：将整个待部署区域的地图划分为若干栅格；划分栅格后，将时间离散化，划分为若干时隙，然后将历史数据中的所有的gps记录归纳到对应的栅格和时隙中去，即可得到任一栅格任一时隙内的gps记录数量总和；将所有栅格在某时隙内的负载用向量表示，则多个时隙对应的负载向量构成栅格化负载序列；进行固定站点的部署：对负载非零的有效数据栅格进行分簇，栅格之间的距离定义为欧氏距离，各簇中心为固定站点边缘服务器的放置位置，各簇的栅格为所述固定站点边缘服务器的覆盖范围；以各个边缘服务器分配的计算能力为待求解未知量，以最大化固定站点可承担的负载总和为目标函数，构建约束条件并且求解目标函数，得到固定站点边缘服务器计算能力的分配结果，其中：务器计算能力的分配结果，其中：务器计算能力的分配结果，其中：务器计算能力的分配结果，其中：务器计算能力的分配结果，其中：务器计算能力的分配结果，其中：上式中，wl
rsu
表示固定站点可承担的负载总和，设将栅格分为k簇。时间段分为t个时隙，时隙t＝1，...，t；簇k在t时隙的负载为簇k分配的计算能力为c
k
，定义μ
k
(t)为一个0-1指示变量，表示第t时隙簇k的计算能力是否完全满足负载，其中μ
k
(t)＝1表示完全满足；对任一时隙，完全满足负载的簇应大于k
′
个；进行移动单元的部署，包括单时隙无人机悬停位置分派、时隙间无人机路径规划；其中：对于单时隙无人机悬停位置分派，首先对目标时隙t所有栅格的负载进行感知或预估；对于目标时隙t，用前一个时隙t-1，或者前一个时隙后20％～50％时间的数据对目标时隙t的负载进行预估；得到每个栅格的负载预估值后，将各簇固定站点的计算能力按栅格负载预估值比重分配至各栅格；各栅格的预估负载减去分配的计算能力，得到所有栅格i的剩余负载w
′
i
(t)；基于此剩余负载，以及无人机的覆盖半径r
uav
确定分派位置；对于时隙间无人机路径规划，当时隙t-1和下一时隙t的无人机悬停位置都确定后，以无人机的整体移动距离最短为原则，考虑到时隙t-1和下一时隙t无人机需求量的不同，进行时隙t-1的悬停位置移动到下一时隙t的路径的规划。2.根据权利要求1所述的固定站点与无人机搭载边缘服务器的协同部署方法，其特征在于，所述栅格的规格为1km*1km，也可以根据粒度需要进行灵活调整；对地图上的所有栅格进行检查，如栅格从来没有产生负载，说明此区域从来没有出现
过车辆，没有分析的必要，将此栅格删去；所有剩下的栅格构成有效数据区域。3.根据权利要求1所述的固定站点与无人机搭载边缘服务器的协同部署方法，其特征在于，对于所述目标函数，引入一组新变量z
k
(t)来表示采用线性松弛+分支搜索的方法进行求解，考虑可用无人机的数量m，要想使得任意时隙所有的负载都得到服务，必须满足k
′
+m≥k，这样，当k-k
′
个簇发生计算短缺时，可以使用m≥k-k
′
个无人机加以补偿；根据可用无人机的数量和能力，确定k
′
的值，继而对目标函数进行求解，从而得到分配给各簇的固定站点边缘服务器分配的计算能力c
k
。4.根据权利要求1所述的固定站点与无人机搭载边缘服务器的协同部署方法，其特征在于，所述单时隙无人机悬停位置分派，具体包括单时隙单无人机位置分派；对于单时隙单无人机位置分派，问题的已知量为：t-1时隙无人机分派的栅格集合t时隙地图的剩余负载{w
′
i
(t)}，其中w
′
i
(t)表示栅格i的剩余负载，无人机的计算能力c
uav
，无人机的覆盖半径r
uav
，以及两两栅格之间的距离d
i，j
；需要输出的结果为：t时隙无人机的分派栅格g
x
，该无人机的承担负载wl，以及该无人机分派并承担负载后更新的地图上的剩余负载w
′
(t)；令(t)；令表示将无人机放在栅格g
i
上时，所有栅格的剩余负载，表示将无人机放在栅格g
i
上时，栅格j的剩余负载；(1)首先尝试上一个时隙的所有无人机的分派栅格把无人机放在中的每个栅格，若无人机的计算能力小于或等于其覆盖半径内的栅格剩余负载总和，即条件1，则直接选择此栅格为时段t的分派栅格g
x
，该无人机对应的承担负载wl＝c
uav
，以及更新后的剩余负载；(2)若所有的栅格都不满足上述条件1，则尝试地图上所有栅格并选择一个承担负载最大的作为分派栅格；(2-1)将无人机依次放在地图中的每个栅格g
i
并计算其对应的承担负载(2-1-1)初始化无人机剩余计算能力为c
cur
＝c
uav
，承担负载为地图的剩余负载(2-1-2)出无人机覆盖半径内所有栅格的集合(2-1-3)对按到栅格g
i
的距离升序排序；(2-1-4)依次对中的每个栅格g
j
：a)减去g
j
栅格的负载：w
j
′
(t)表示栅格j的剩余负载；b)更新无人机的承担负载：c)更新无人机的剩余计算能力：c
cur
＝c
cur-min(c
cur
，w
j
′
(t))；d)检查c
cur
是否为0？如是，则说明无人机已没有剩余计算能力，结束步骤；(2-2)返回步骤(2-1)中的的最大值对应的悬停位置即无人机分派栅格更新后的剩余负载，g
x
就是无人机分派栅格，得解；其中，
表示将无人机放置于不同的栅格g
i
时对应的承担负载中的最大值。5.根据权利要求4所述的固定站点与无人机搭载边缘服务器的协同部署方法，其特征在于，若步骤(2-2)中的最大值不唯一，即有多个这样的g
x
，标记为集合{g
y
}，则选择到t-1时隙无人机位置集合距离最小的栅格；当t＝1时，即第一个时隙，略过此步；(3-1)定义g
y
到的距离为g
y
到所有栅格中距离最小的值所有栅格中距离最小的值其中，表示z是中任一栅格，表示从集合中寻z栅格到g
y
栅格距离最小的那个距离，d
y，z
为g
y
中的栅格与z栅格之间的距离；(3-2)在所有的g
y
中选择使得最小的g
y
作为无人机分派栅格；(3-3)返回上述g
x
作为无人机分派栅格，得解。6.根据权利要求1所述的固定站点与无人机搭载边缘服务器的协同部署方法，其特征在于，所述单时隙无人机悬停位置分派，具体还包括单时隙多无人机位置分派；对多个无人机的位置分派基于单无人机位置分派方法；设无人机数量为m，在时段t，依次执行单时隙单无人机位置分派方法，直到所有的m个无人机全部分派完毕，或者地图上所有的剩余负载都被承担为止。7.根据权利要求1所述的固定站点与无人机搭载边缘服务器的协同部署方法，其特征在于，所述时隙间无人机路径规划，包括：1)时隙t-1和时隙t所需无人机数量相等即地图上的整体负载基本不变，两个时段使用相同数量的无人机，将这一问题建模成带权二分图的最小匹配问题，二分图左侧节点是时隙t-1的栅格，右侧节点为时隙t的栅格；节点之间的边都是带权边，权值为相应栅格之间的欧氏距离；则路径规划问题转化为求该带权二分图的最小匹配，即最小化无人机移动距离之和，可以用匈牙利算法在多项式时间内求解；在此基础上，进一步考虑无人机的飞行距离限制，即无人机不可能在短时间内跨越较大距离，设定距离阈值，将不满足距离阈值的栅格从二分图中删去，然后对二分图求带权最小匹配，即可得到考虑无人机飞行距离限制的最小无人机移动路径；2)时隙t-1所需无人机数量大于时隙t此时仍可按1)中的方法构建二分图，所得的最小带权匹配仍然会使得右侧节点被全部覆盖，而左侧会有节点未被匹配覆盖；此时，认为未被覆盖的无人机不再需要，转为休眠状态，在原悬停栅格中选择一栋高楼楼顶降落该无人机，以节约能量；3)时隙t-1所需无人机数量小于时隙t此时，需要将原有休眠的无人机唤醒，唤醒位置即上一次休眠的位置，将节点补充进二分图的左侧；当系统追加新采购的无人机时，可以将无人机预先分配到指定位置休眠；构建二分图时，即以这些休眠位置为起点构造二分图左侧，构造完毕后，求二分图的最小带权匹配，得到无人机的移动路径。

技术总结

本发明公开了一种固定站点与无人机搭载边缘服务器的协同部署方法，引入无人机搭载边缘服务器作为移动单元部署方式，与固定站点搭载边缘服务器构成的固定站点部署方式配合，进行移动单元部署策略的设计以及移动路径的规划，协同解决负载时空动态变化的问题。本发明针对城域车联网场景下负载随时空动态变化的问题，利用数学方法对固定站点和移动单元(无人机)搭载边缘服务器进行协同部署，更具实用价值，且针对问题更实际、全面，可有效降低计算能力的总采购成本，并解决固定站点部署方式不能跟随时空动态变化的负载这一问题，同时可降低无人机的能耗。低无人机的能耗。低无人机的能耗。