1.一种边缘计算环境中服务迁移路径选择方法,其特征在于,包括以下步骤:
S1:根据实际需要确定移动用户从起点到终点的移动轨迹;
S2:以经纬度建立平面直角坐标系,经度为x轴,纬度为y轴;获取用户移动轨迹的经度最小值x1,经度最大值x2,纬度最小值y1,纬度最大值y2,从而确定用户移动区域的4个顶点:(x1,y1)、(x1,y2)、(x2,y2)、(x2,y1);用户移动区域分别向经度和纬度方向向外进行延伸,得到扩展用户移动区域,其4个顶点为(x1‑kx,y1‑ky)、(x1‑kx,y2+ky)、(x2+kx,y2+ky)、(x2+kx,y1‑ky),其中kx、ky分别表示经度方向、纬度方向的延伸长度,具体取值根据实际需要确定;然后将扩展用户移动区域划分为网格,得到大小为N×M的网格阵列;然后将扩展用户移动区域内的边缘服务器根据其经纬度坐标划分至对应的网格,记坐标为(i,j)的网格所包含的边缘服务器集合为φi,j,i=1,2,…,N,j=1,2,…,M;
S3:初始化分割点集合φ为空,记用户移动轨迹上除起点和终点外的定位点数量为D,第d个时刻的定位点Ld,d=1,2,…,D;对于每个定位点Ld,采用如下公式计算在该定位点的角度Angled:其中,dis()表示求取两个定位点之间的距离,L0表示用户移动轨迹的起点,LD+1表示用户移动轨迹的终点;
如果Angled<TA,TA表示预设的角度阈值,则将定位点Ld作为分割点加入分割点集合φ,否则不作为分割点;
根据分割点集合φ中分割点将用户移动轨迹分割为若干子轨迹,记子轨迹数量为Q;
S4:进行启发式的路径规划,得到服务迁移路径,包括以下步骤:
S4.1:记子轨迹序号q=1;
S4.2:对于子轨迹起点,将第q‑1条子轨迹所确定的终点的边缘服务器endq‑1作为第q条子轨迹起点的边缘服务器startq,start1即为在用户移动轨迹起点时所确定的边缘服务器;
对于子轨迹终点,当q<Q时,搜索得到距离第q条子轨迹终点最近的边缘服务器作为终点边缘服务器endq,当q=Q时,根据用户移动轨迹终点的实际情况确定第q条子轨迹的终点边缘服务器endQ;
S4.3:将第q条子轨迹起点的边缘服务器startq加入待定边缘服务器列表openlist,并设置其代价值为一个绝对大值,前驱节点为空;初始化备选边缘服务器列表closelist为空;
S4.4:判断是否待定边缘服务器列表openlist为空,如果是,进入步骤S4.5,否则进入步骤S4.6;
S4.5:第q条子轨迹不存在对应的服务迁移路径,服务迁移路径规则失败;
S4.6:从待定边缘服务器列表openlist中选择代价值最小的边缘服务器作为最优待定边缘服务器ESmin,并将其从待定边缘服务器列表openlist中删除;
S4.7:判断是否边缘服务器ESmin=endq,如果不是,进入步骤S4.8,否则进入步骤4.11;
S4.8:将边缘服务器ESmin加入备选边缘服务器列表closelist;
S4.9:根据步骤S2中的网格结果,确定边缘服务器ESmin所在网格G,将网格G所有邻居网格覆盖的边缘服务器构成邻居边缘服务器集合V;
S4.10:对于集合V中的每个邻居边缘服务器X,依次采用以下方法进行判断:如果邻居边缘服务器X既不属于待定边缘服务器列表openlist,也不属于备选边缘服务器列表closelist,则将邻居边缘服务器X加入备选边缘服务器列表closelist,计算得到邻居边缘服务器X的代价值f(ESmin,X),并令邻居边缘服务器X的前驱节点为边缘服务器ESmin;其中,代价值f(ESmin,X)的计算公式如下:f(ESmin,X)=λww+λbb(ESmin,X)+λddis′(ESmin,X)其中,w表示边缘服务器ESmin负载量的归一化值,b(ESmin,X)表示边缘服务器ESmin到邻居边缘服务器X带宽的归一化值,dis′(ESmin,X)表示边缘服务器ESmin到邻居边缘服务器X距离的归一化值,λw、λb、λd表示预设的权重,且λw+λb+λd=1;
如果邻居边缘服务器X属于待定边缘服务器列表openlist,则计算新的代价值f(ESmin,X),如果代价值f(ESmin,X)小于openlist中已经存储的该节点所对应的代价值,则将openlist中存储的该节点所对应的代价值更新为f(ESmin,X),并将其对应的前驱节点更新为边缘服务器ESmin,否则不作任何操作;
如果邻居边缘服务器X属于备选边缘服务器列表closelist,则计算新的代价值f(ESmin,X),如果代价值f(ESmin,X)小于closelist中已经存储的该节点所对应的代价值,则将closelist中存储的该节点所对应的代价值更新为f(ESmin,X),并将其对应的前驱节点更新为边缘服务器ESmin,否则不作任何操作;
返回步骤S4.4;
S4.11:根据各个边缘服务器的前驱节点,从第q条子轨迹的终点边缘服务器endq迭代回溯至起点边缘服务器startq,得到第q条子轨迹对应的路径;
S4.12:判断是否q<Q,如果是,进入步骤S4.13,否则进入步骤S4.14;
S4.13:令q=q+1,返回步骤S4.2;
S4.14:将Q条子轨迹对应的路径拼接起来,即得到从用户移动轨迹起点至终点的服务迁移路径。
2.根据权利要求1所述的边缘计算环境中服务迁移路径选择方法,其特征在于所述步骤S2扩展用户移动区域划分为网格的具体方法为:对于扩展用户移动区域,计算得到其长度L、宽度W以及对角线2个顶点(x1‑kx,y1‑ky)、(x2+kx,y2+ky)之间的距离S;记边缘服务器的信号覆盖半径为E,则令所划分子网格的长度和宽度都为 即得到的网格的对角线长度为E/2;则划分得到的网格阵列中行数N和列数M的计算公式如下:
其中, 表示向上取整;
根据以上方式将扩展用户移动区域划分为N行M列的网格阵列。
3.根据权利要求2所述的边缘计算环境中服务迁移路径选择方法,其特征在于所述长度L、宽度W和距离S为对应2个顶点在地球上的弧长。
4.根据权利要求1所述的边缘计算环境中服务迁移路径选择方法,其特征在于所述角度阈值TA的取值范围为[120°,140°]。
5.根据权利要求1所述的边缘计算环境中服务迁移路径选择方法,其特征在于所述轨迹分割前,对分割点集合φ中的分割点依次进行筛选,具体方法为:判断当前分割点与前一个分割点是否位于同一网格,如果是,则删除当前分割点,如果不是,则进一步判断当前分割点与前一个分割点的距离是否大于预设阈值T,如果是,则保留当前分割点,如果不是,则删除当前分割点。
6.根据权利要求5所述的边缘计算环境中服务迁移路径选择方法,其特征在于所述阈值T为网格对角线长度的1/3。