本发明提供了一种边缘服务器选址部署模型及其求解方法，所述边缘服务器选址部署模型包括基站和边缘服务器，定义i表示所述边缘服务器，j表示所述基站，每个所述边缘服务器与一个或多个所述基站连接；建立所述边缘服务器选址部署模型，以使所述边缘服务器与所述基站之间的平均延时与费用支出之和最小。本发明不但可以有效减少移动边缘服务器放置成本，而且还可以通过移动边缘服务器所放置的地理位置，从而减少边缘服务器与用户之间通信的延迟，加快服务响应。该模型为np难问题，难以在常数时间内求解，而采用遗传算法可以在常数时间内求解出最优或接近最优的解。
1.一种边缘服务器选址部署方法，其特征在于：所述方法包括如下步骤：步骤1，将基站的位置坐标与边缘服务器的位置坐标通过计算公式：计算出基站与边缘服务器之间的距离；其中，cij表示所述边缘服务器与所述基站之间的距离，定义i表示所述边缘服务器，j表示所述基站，l(si)表示所述边缘服务器的位置坐标，l(bj)表示所述基站的位置坐标，bj∈B为所述基站的节点，B表示所述基站的节点的集合，si∈S为所述边缘服务器的备选点，S表示所述边缘服务器的备选点的集合，x为坐标修正系数；
步骤2，设置遗传算法参数；所述遗传算法参数包括初始化种群规模、每个个体的基因数、基因交叉概率、基因变异概率以及最大迭代次数；
步骤4，初始化种群，从边缘服务器备选点中选取k个作为其中一个个体的基因；
步骤7，计算适应度：取平均时延和费用成本的倒数；所述适应度为衡量个体优劣的尺度，根据所述适应度决定个体繁殖的数量、或者决定是否消亡；
步骤8，采用轮盘赌方式选择幸存个体，所述步骤8包括如下具体步骤：步骤8.1，计算适应度比例，即每个个体的选择概率 M为个体数量，f(xi)为个体xi的适应度，f(xj)为个体xj的适应度；
步骤8.2，计算每个个体的累积概率qi，相当于转盘上的跨度，跨度越大，越容易选到步骤8.3，随机生成随机值r∈[0,1]，若qi>r，则选择个体xi；
步骤8.4，由轮盘赌算法选择下来的个体为幸存个体，淘汰最差的T个个体，由最优的T个个体替代；
步骤9，随机交叉变异，所述步骤9包括如下具体步骤：
步骤9.1，将种群中个体随机分成两组，随机选择两个个体进行交叉操作；
步骤9.2，首先在[1，sz]的范围内，即在染色体长度内，随机产生两个交叉位min和max，将两个个体的[min，max]区域互换，其中sz为城市数数量，min
步骤9.3，处理染色体重复部分，随机变异重复的染色体；
步骤10，随机变异运算：随机选取变异个体，随机选择染色体变异；
步骤11，转向个体评价，开始新一轮循环：转向步骤6开始循环；
2.根据权利要求1所述的边缘服务器选址部署方法，其特征在于：在步骤2中，所述种群为个体的集合；所述个体为基因的集合；所述基因交叉概率为随机交换两个个体的部分编码；所述基因变异为随机改变某个体的某个或几个编码。
3.根据权利要求1所述的边缘服务器选址部署方法，其特征在于，步骤1和步骤2之间还设有步骤：对原始数据cij和costi进行归一化处理，使结果值映射到[0‑1]之间，其中costi表示每个所述边缘服务器布置费用；所述归一化处理的计算公式为：
4.根据权利要求1所述的边缘服务器选址部署方法，其特征在于：步骤3中所述编码的方式为十进制编码。
5.一种边缘服务器选址部署系统，其特征在于：所述边缘服务器选址部署系统应用权利要求1‑4中任一项所述的边缘服务器选址部署方法，所述边缘服务器选址部署系统包括所述基站和所述边缘服务器，每个所述边缘服务器与一个或多个所述基站连接；建立所述边缘服务器选址部署系统，以使所述边缘服务器与所述基站之间的平均延时与费用支出之和最小，所述边缘服务器选址部署系统如下：Minimize:∑i,j∈N(t*cij*xij+(1‑t)*costi) (1)Subject to ∑i∈Nxij＝1 for each j∈N， (2)xij≤yifor each i,j∈N， (3)∑i∈Nyi＝k， (4)
xij∈{0,1},for each i,j∈N， (5)yi∈{0,1}for each i,j∈N， (6)其中，yi表示所述边缘服务器备选地址是否被选中，xi,j表示所述边缘服务器与所述基站相连，其中，i,j∈N，N表示自然数，t表示权重系数；
约束条件(2)表示每个基站只能与一个边缘服务器相连；
约束条件(3)表示若边缘服务器i与基站j相连,则边缘服务器i已被选中；
约束条件(4)表示选中的边缘服务器的备选点数量为k；
约束条件(5)、(6)分别表示xij,yi为0或1变量。
6.根据权利要求5所述的边缘服务器选址部署系统，其特征在于：所述cij的计算公式：当l(si)+l(bj)为正数时，x＝1，当l(si)+l(bj)为负数时，x为虚数；所述边缘服务器的级别节点为无向图G＝(V，E)；其中，V表示所述边缘服务器的备选点和所述基站的节点的集合，E表示所述基站与边缘服务器之间的链路；所述V＝B∪S，其中，B表示所述基站的节点的集合，S表示所述边缘服务器的备选点的集合；bj为所述基站的节点，si为所述边缘服务器的备选点。
边缘服务器选址部署模型及其求解方法
技术领域
[0001] 本发明涉及一种边缘服务器选址部署模型及其求解方法，属于边缘计算通信领域。
背景技术
[0002] 随着5G时代的来临，移动网络服务的对象不再是单纯的手机，而是各种类型的设备，如VR、平板、汽车等。服务的场景也越来越多样化，比如移动宽带、大规模机器类型通信、工业互联网等。因此，在移动性、安全性、时延性和可靠性等多个方面，移动网络都必须满足更高的要求。
[0003] 为了满足移动网络高速发展所需的高带宽、低时延的要求，并减轻网络负荷，移动边缘计算(Mobile Edge Computing，MEC)应运而生。
[0004] 移动边缘计算相关的关键技术主要分为边缘云放置、计算卸载、服务迁移、群智协同四个技术。我们主要研究移动边缘计算环境下的边缘服务器放置问题。将计算任务从核心网迁移到网络边缘，减少核心网拥塞和数据传播延迟是移动边缘计算的主要目标。但是，边缘云即边缘服务器应该放置到哪些位置上并没有明确的规定，因此产生了边缘服务器放置问题。边缘服务器放置问题是在一定的地理位置范围内，考虑用户和资源等的约束限制，在满足用户需求和目标的前提下，按照一定的策略为边缘服务器选择合适的地理位置来达到资源利用率高、网络时延小的目的。
[0005] 在移动边缘计算环境中放置边缘服务器是一个挑战。边缘服务器的位置对移动用户的访问延迟和边缘服务器的资源利用率至关重要，特别是在智能城市，这些城市包括几百个或几千个基站，移动用户通过这些基站访问边缘服务器。由于这些网络规模庞大，边缘服务器的低效放置将导致边缘服务器之间的访问延迟过长和工作负载严重不平衡，一些边缘服务器将过载，而另一些边缘服务器则未被充分利用，甚至闲置。因此，边缘服务器的策略布局将显著提高各种移动应用的性能，如边缘服务器的访问延迟。
[0006] 有鉴于此，确有必要提出一种边缘服务器选址部署模型及其求解方法，以解决上述问题。
发明内容
[0007] 本发明的目的在于提供一种边缘服务器选址部署模型，以不但能够减少基站与边缘服务器之间的时延，而且还能减少部署边缘服务器的支出。
[0008] 为实现上述目的，本发明提供了一种边缘服务器选址部署模型，所述边缘服务器选址部署模型包括基站和边缘服务器，定义i表示所述边缘服务器，j表示所述基站，每个所述边缘服务器与一个或多个所述基站连接；建立所述边缘服务器选址部署模型，以使所述边缘服务器与所述基站之间的平均延时与费用支出之和最小，所述边缘服务器选址部署模型如下：
[0009] Minimize:∑i,j∈N(t*cij*xij+(1‑t)*costi) (1)
[0010] Subject to∑i∈Nxij＝1 for eachj∈N， (2)
[0011] xij≤yifor each i,j∈N， (3)
[0012] ∑i∈Nyi＝k， (4)
[0013] xij∈{0,1},for each i,j∈N， (5)
[0014] yi∈{0,1}for each i,j∈N， (6)
[0015] 其中，yi(i∈N)表示所述边缘服务器备选地址被选中，xi,j(i,j∈N)表示所述边缘服务器与所述基站相连，cij表示所述边缘服务器与所述基站之间的距离，costi表示每个所述边缘服务器布置费用，t表示权重系数；
[0016] 约束条件(2)表示每个基站只能与一个边缘服务器相连；
[0017] 约束条件(3)表示若边缘服务器i与基站j相连,则边缘服务器i已被选中；
[0018] 约束条件(4)表示选中的边缘服务器的备选点数量为k；
[0019] 约束条件(5)、(6)分别表示xij,yi为0‑1变量。
[0020] 作为本发明的进一步改进，所述cij的计算公式为：
[0021]
[0022] 其中，l(si)表示所述边缘服务器的位置坐标，l(bj)表示所述基站的位置坐标。
[0023] 作为本发明的进一步改进，所述边缘服务器的级别节点为无向图G＝(V，E)；其中，V表示所述边缘服务器的备选点和所述基站的节点的集合，E表示所述基站与边缘服务器之间的链路。
[0024] 作为本发明的进一步改进，所述V＝B∪S，其中，B表示所述基站的节点的集合，S表+ +示所述边缘服务器的备选点的集合；bj∈B(j∈N)为所述基站的节点，si∈S(i∈N)为所述边缘服务器的备选点。
[0025] 本发明的目的还在于提供一种边缘服务器选址部署的求解方法，其能够求解出最优解或接近最优解的边缘服务器选址位置。
[0026] 为实现上述目的，本发明提供了一种边缘服务器选址部署的求解方法，所述求解方法应用于上述边缘服务器选址部署模型，所述求解方法包括如下步骤：
[0027] 步骤1，将基站的位置坐标与边缘服务器的位置坐标通过计算公式：转化为基站与边缘服务器的备选点之间的距离；其中，l(si)表
示所述边缘服务器的位置坐标，l(bj)表示所述基站的位置坐标，bj∈B(j＝1,2,...,m)为所述基站的节点，si∈S(i＝1,2,...,n)为所述边缘服务器的备选点；
[0028] 步骤2，设置遗传算法参数；所述遗传算法参数包括初始化种群规模、每个个体的基因数、基因交叉概率、基因变异概率以及最大迭代次数；
[0029] 步骤3，对边缘服务器的备选点进行编码；
[0030] 步骤4，初始化种群，从边缘服务器备选点中选取k个作为其中一个个体的基因；
[0031] 步骤5，进行指定次数迭代进化；
[0032] 步骤6，计算每个个体的平均时延与费用成本；
[0033] 步骤7，计算适应度：取平均时延和费用成本的倒数；所述适应度为衡量个体优劣的尺度，根据所述适应度决定个体繁殖的数量、或者决定是否消亡；
[0034] 步骤8，采用轮盘赌方式选择幸存个体；
[0035] 步骤9，随机交叉变异；
[0036] 步骤10，随机变异运算：随机选取变异个体，随机选择染色体变异；
[0037] 步骤11，转向个体评价，开始新一轮循环：转向步骤6开始循环；
[0038] 步骤12，循环结束，选出最优个体作为解。
[0039] 作为本发明的进一步改进，在步骤2中，所述种群为个体的集合；所述个体为基因的集合；所述基因交叉概率为随机交换两个个体的部分编码；所述基因变异为随机改变某个体的某个或几个编码。
[0040] 作为本发明的进一步改进，步骤8包括如下具体步骤：
[0041] 步骤8.1，计算适应度比例，即每个个体的选择概率
[0042] 步骤8.2，计算每个个体的累积概率qi，相当于转盘上的“跨度”，“跨度”越大，越容易选到
[0043] 步骤8.3，随机生成r∈[0,1]，若qi>r，则选择个体xi；
[0044] 步骤8.4，由轮盘赌算法选择下来的个体为幸存个体，淘汰最差的T个个体，由最优的T个个体替代。
[0045] 作为本发明的进一步改进，步骤9包括如下具体步骤：
[0046] 步骤9.1，将种群中个体随机分成两组，随机选择两个个体进行交叉操作；
[0047] 步骤9.2，首先在[1，sz](sz为城市数数量)的范围内，即在染色体长度内，随机产生两个交叉位min和max(min
[0048] 步骤9.3，处理染色体重复部分，随机变异重复的染色体。
[0049] 作为本发明的进一步改进，步骤1和步骤2之间还设有步骤：对原始数据cij和costi进行归一化处理，使结果值映射到[0‑1]之间；所述归一化处理的计算公式为：
[0050]
[0051] 作为本发明的进一步改进，步骤3中所述编码的方式为十进制编码。
[0052] 本发明的有益效果是：本发明不但可以有效减少移动边缘服务器放置成本，而且还可以通过移动边缘服务器所放置的地理位置，从而减少边缘服务器与用户之间通信的延迟，加快服务响应。该模型为np难问题，难以在常数时间内求解，而采用遗传算法可以在常数时间内求解出最优或接近最优的解。
附图说明
[0053] 图1是本发明边缘服务器选址部署模型的结构示意图。
[0054] 图2是本发明中遗传算法的流程图。
[0055] 图3是本发明中轮盘赌算法的流程图。
[0056] 图4是本发明中遗传算法与其他算法在每个边缘服务器时延和成本的结果比较的示意图。
[0057] 图5是本发明中遗传算法与其他算法在基站与边缘服务器的平均时延与成本之和的示意图。
[0058] 图6是本发明比较遗传算法不同迭代次数所求解的结果示意图。
具体实施方式
[0059] 为了使本发明的目的、技术方案和优点更加清楚，下面结合附图和具体实施例对本发明进行详细描述。
[0060] 本发明揭示了一种边缘服务器选址部署模型，边缘服务器选址部署模型包括基站和边缘服务器。定义i表示边缘服务器，j表示基站，每个边缘服务器与一个或多个基站连接；建立边缘服务器选址部署模型，以使边缘服务器与基站之间的平均延时与费用支出之和最小，边缘服务器选址部署模型如下：
[0061] Minimize：∑i，j∈N(t*cij*xij+(1‑t)*costi) (1)
[0062] Subject to∑i∈Nxij＝1 for each j∈N， (2)
[0063] xij≤yifor each i，j∈N， (3)
[0064] ∑i∈Nyi＝k， (4)
[0065] xij∈{0，1}，for each i，j∈N， (5)
[0066] yi∈{0，1}for each i，j∈N， (6)
[0067] 其中，yi(i∈N)表示边缘服务器备选地址被选中，xi，j(i，j∈N)表示边缘服务器与基站相连，cij表示边缘服务器与基站之间的距离，costi表示每个边缘服务器布置费用，t表示权重系数。约束条件(2)表示每个基站只能与一个边缘服务器相连；约束条件(3)表示若边缘服务器i与基站j相连，则边缘服务器i已被选中；约束条件(4)表示选中的边缘服务器的备选点数量为k；约束条件(5)、(6)分别表示xij，yi为0‑1变量。
[0068] 上述边缘服务器与基站之间的距离计算公式为：
[0069]
[0070] 其中，l(si)表示边缘服务器的位置坐标，l(bj)表示基站的位置坐标。边缘服务器的级别节点可以看作一个无向图G＝(V，E)。其中，V＝B∪S表示边缘服务器的备选点和基站的节点的集合，其中，B表示基站的节点的集合，S表示边缘服务器的备选点的集合。定义bj+ +∈B(j∈N)为基站的节点，si∈S(i∈N)为边缘服务器的备选点。E表示基站与边缘服务器之间的链路。每一条链路不仅表示了基站与移动边缘服务器之间的物理连接，也描述了基站与移动边缘服务器之间的逻辑连接。
[0071] 首先定义一组概念：
[0072] 基因型：性状染色体的内部表现。
[0073] 进化：种群逐渐适应生存环境，品质不断得到改良。生物的进化是以种群的形式进行的。
[0074] 适应度：度量某个物种对于生存环境的适应程度。选择：以一定的概率从种群中选择若干个个体。一般，选择过程是一种基于适应度的优胜劣汰的过程。
[0075] 复制：细胞分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新细胞就继承了旧细胞的基因。
[0076] 交叉：两个染色体的某一相同位置处DNA被切断，前后两串分别交叉组合形成两个新的染色体。也称基因重组或杂交；基因交叉概率为随机交换两个个体的部分编码。
[0077] 变异：复制时可能(很小的概率)产生某些复制差错，变异产生新的染色体，表现出新的性状。基因变异为随机改变某个体的某个或几个编码。
[0078] 编码：DNA中遗传信息在一个长链上按一定的模式排列。遗传编码可看作从表现型到基因型的映射。
[0079] 个体：指染色体带有特征的实体，即为基因的集合。
[0080] 种群：个体的集合，该集合内个体数称为种群。
[0081] 下面将详细说明边缘服务器选址部署的求解方法。
[0082] 具体求解方法步骤包括：步骤1，将基站的位置坐标与边缘服务器的位置坐标通过计算公式： 转化为基站与边缘服务器的备选点之间的距离；其中，l(si)表示边缘服务器的位置坐标，l(bj)表示基站的位置坐标，bj∈B(j＝1,2,...,m)为基站的节点，si∈S(i＝1,2,...,n)为边缘服务器的备选点；
[0083] 步骤2，设置遗传算法参数；遗传算法参数包括初始化种群规模、每个个体的基因数、基因交叉概率、基因变异概率以及最大迭代次数；
[0084] 步骤3，对边缘服务器的备选点进行编码；
[0085] 步骤4，初始化种群，从边缘服务器备选点中选取k个作为其中一个个体的基因；
[0086] 步骤5，进行指定次数迭代进化；
[0087] 步骤6，计算每个个体的平均时延与费用成本；
[0088] 步骤7，计算适应度：取平均时延和费用成本的倒数；所述适应度为衡量个体优劣的尺度，根据所述适应度决定个体繁殖的数量、或者决定是否消亡；
[0089] 步骤8，采用轮盘赌方式选择幸存个体:
[0090] (8.1)计算适应度比例，即每个个体的选择概率
[0091] (8.2)计算每个个体的累积概率qi，相当于转盘上的“跨度”，“跨度”越大，越容易选到
[0092] (8.3)随机生成r∈[0,1]，若qi>r，则选择个体xi；
[0093] (8.4)由轮盘赌算法选择下来的个体为幸存个体，淘汰最差的T个个体，由最优的T个个体替代。
[0094] 步骤9，随机交叉变异：
[0095] (9.1)将种群中个体随机分成两组，随机选择两个个体进行交叉操作；(9.2)首先在[1，sz](sz为城市数数量)的范围内，即在染色体长度内，随机产生两个交叉位min和max(min
[0096] (9.3)处理染色体重复部分，随机变异重复的染色体。
[0097] 步骤10，随机变异运算：随机选取变异个体，随机选择染色体变异；
[0098] 步骤11，转向个体评价，开始新一轮循环：转向步骤6开始循环；
[0099] 步骤12，循环结束，选出最优个体作为解。
[0100] 具体来说，如图1所示，初始时，移动边缘服务器的备选点与基站网络的拓扑结构，该网络拓扑结构一共有7个基站，5个移动边缘服务器的部署备选点。先假设我们需要在5个移动边缘服务器的部署备选点选出3个点作为实际部署点。每个基站与移动边缘服务器备选点都有一个坐标(x，y)，每个移动边缘服务器备选点都有个部署成本costi。利用公式(7)计算出每个基站与每个移动边缘服务器之间的欧几里得距离cij。
[0101] 如果对数据有归一化需求，则对cij以及costi进行归一化处理。如图2所示，按照步骤2确定遗传算法参数。即确定最大迭代次数m、初始种群规模num，每个个体基因数k，基因交叉概率cross、基因突变概率mutate。如图6所示，最大迭代次数会影响求解结果。
[0102] 在步骤3中采用十进制为基因编码，例如[0,1,2]就代表该个体选择了0、1、2号边缘服务器备选点。步骤4中创建num*k个二维数组作为初始化种群数组。对每个个体基因进行随机初始化，从边缘服务器备选点随机选取k个点作为其中一个个体的基因。接下来，步骤5到步骤7，遍历每个基站到边缘服务器最短时延与成本之和，然后求得该个体的平均时延与成本之和。之后对个体按照平均时延与成本之和由大到小排序。
[0103] 如图3所示，之后由步骤8轮盘赌算法计算出幸存的个体。淘汰最差的n个个体，由最佳的n个个体代替。
[0104] 在步骤9中随机交换任意个体的基因，例如：[0,1,2]与[1,3,4]进行交换产生[0,2,3]与[1,1,4]。如果发生染色体重复，则变异该染色体，例如：[1,1,4]变异成[1,2,4]。步骤10进行随机个体的随机染色体变异。随机选择某个个体的某段基因，然后随机对其进行改变，例如：[1,2,4]变异为[1,2,3]。继续进行适应度计算，开始下一轮迭代，直到达到指定迭代次数。输出最佳个体。即边缘服务器部署方案。
[0105] 如图4和图5所示，通过实验对比不同算法，得出本发明不但可以在常数时间内求解出该np问题的最优解或接近最优的解，而且还可以在边缘服务器部署阶段减少边缘服务器与基站之间的平均时延和成本。同时，避免了该问题在时间复杂度方面难以常数时间求解的问题。
[0106] 综上所述，本发明通过设置一种边缘服务器选址部署模型及其求解方法，不但可以有效减少移动边缘服务器放置成本，而且还可以通过移动边缘服务器所放置的地理位置，从而减少边缘服务器与用户之间通信的延迟，加快服务响应。该模型为np难问题，难以在常数时间内求解，而采用遗传算法可以在常数时间内求解出最优或接近最优的解。
[0107] 以上实施例仅用以说明本发明的技术方案而非限制，尽管参照较佳实施例对本发明进行了详细说明，本领域的普通技术人员应当理解，可以对本发明的技术方案进行修改或者等同替换，而不脱离本发明技术方案的精神和范围。
