一种移动边缘云计算网络中的MEC服务器部署方法转让专利
申请号 : CN202110688768.2
文献号 : CN113347267B
文献日 : 2022-03-18
发明人 : 张永敏 , 黄金戈 , 任炬 , 吕丰 , 张尧学
申请人 : 中南大学
摘要 :
权利要求 :
1.一种移动边缘云计算网络中的MEC服务器部署方法，其特征在于包括以下步骤：第一步，对影响部署效率的各种因素进行建模和分析，得到部署效率的计算公式；具体是：
步骤1.1定义部署决策；令B＝{1，2，...，I}表示为所有可以用来部署MEC服务器的基站的集合，其中I表示基站的总数，i表示第i个基站；将部署决策用(Si，Ni)表示，其中Si∈{0，
1}，表示是否在第i个基站处部署MEC服务器，Si＝0表示不在第i个基站处部署MEC服务器，Si＝1表示在第i个基站处部署MEC服务器；Ni为小于等于 的自然数，表示在第i个基站处部署的计算资源量的数量，其中一个计算资源量代表一个内存容量为1TB的CPU； 表示由于第i个基站的空间限制，第i个基站处的Ni的值的上限， 为正整数；
步骤1.2定义时隙；用T表示整个时间段内的时隙总数，用t表示第t个时隙，其中t＝{1，
2，...，T}；在时隙t期间，到达第i个基站的计算任务遵循参数λi，t的泊松分布，并且每个计算任务的计算需求遵循期望值为Ri的指数分布；每个基站按照先来先服务策略处理它收到的计算任务；
步骤1.3计算批发计算资源对部署效率带来的正面影响；令a2，t表示将单位计算资源量批发到云端对部署效率带来的正面影响， 表示第i个基站在时隙t内最优的批发的计算资源量的数量；令 表示在时隙t期间将计算资源从第i个基站上批发到云端对部署效率带来的正面影响； 具体为：
其中，W为英文wholesale的首字母，代表批发；e为英文edge的首字母，代表计算资源量由边缘端批发；
步骤1.4计算用户覆盖率对部署效率带来的正面影响；令 表示在时隙t期间第i个基站处的用户覆盖率，其中A为英文accept的首字母，代表用户被边缘端接受后接入边缘端；
a1，t表示在时隙t内单位用户覆盖率对部署效率带来的正面影响；令 表示在时隙t期间在第i个基站处用户覆盖率对部署效率带来的正面影响， 具体为：其中C为英文coverage的首字母，代表覆盖； 为时隙t期间第i个基站处的用户覆盖率；
步骤1.5计算延迟对部署效率带来的负面影响；令第i个基站处的计算延迟对部署效率带来的负面影响为 是平均处理延迟 的递增凸函数； 设置为：其中L为英文latency的首字母，代表延迟；σi，t是保证 是平均处理延迟 的递增函数的参数，τi，t是保证 是平均处理延迟 的凸函数的参数；
根据M/M/c排队定理， 具体为：其中，μ是每个用户的平均服务时间，这里指单位时间单位计算资源量能够处理的计算任务量， 表示平均队列长度， 具体为：其中，c是服务台的个数，这里指计算资源量的个数，ρ是相同时间内用户的到达的平均数和单个计算资源量被服务的平均用户数的比值，ρs是相同时间内用户的到达的平均数和c个计算资源量被服务的平均用户数的比值，P0是系统空闲的概率；
步骤1.6计算MEC服务器的建设和运营造成的浪费；令αi，t表示时隙t期间的第i个基站的平均浪费量，令βi，t表示单位计算资源量的平均浪费量；令 表示在时隙t期间在基站i处MEC服务器的建设和运营造成的浪费， 具体为：其中，B为英文building的首字母，代表建设和运营；
步骤1.7构建部署效率的计算公式；整个时间段内所有部署MEC服务器的基站的总部署效率U具体为：
步骤1.8构建部署效率的最优化模型，该模型如公式(11)所示：其中，U表示总部署效率， 表示选择在哪些基站上部署MEC服务器和在每个基站上部署多少的计算资源量，才能使得MEC服务器的部署效率最大化，即在降低MEC服务器的部署造成的浪费的同时，尽可能的保证MEC服务器对移动用户的覆盖率，降低MEC服务器处理用户计算任务时的延迟和增加能够批发给云端的计算资源量； 表示Si只能从0和1之间取值； 表示Ni为小于等于 的自然数；
表示平均处理延迟不能超过其上限
第二步，利用符合要求的真实数据集，将数据集中的数据视为在边缘端处理计算任务的一个移动用户，得到计算部署效率所需要的各个参数的值；具体是：步骤2.1选取符合要求的数据集；
步骤2.2确定T和I的值；
步骤2.3初始化i＝1；t＝1；
步骤2.4根据数据集中的数据，计算时隙t期间移动用户对于第i个基站的期望数量λi，t，方法是将每个λi，t划分为可以连接到附近的基站j处的λi，j，t和时隙t内不处于任何其他基站覆盖范围内的用户数量θ0，t，i≠j；λi，j，t表示时隙t期间接近并被第j个基站覆盖且在第i个基站被移除后会选择连接到第j个基站的移动用户的预期数量，λi，i，t表示在时隙t内仅被第i个基站覆盖且在第i个基站被移除后不处于任何基站覆盖范围内的移动用户的预期数量；分别计算λi，t，λi，j，t，λi，i，t和θ0，t的值，得到λi，t，λi，j，t，λi，i，t和θ0，t的值；
第三步，根据部署效率计算公式和各参数的值，使用三层优化方法优化出最优的部署决策，该方法包含以下步骤：
步骤3.1使用三分法，在给定Ni时，计算最佳 即利用三分法来计算对于给定的Ni，最佳批发计算单位量 的含义为当Ni给定时，对于不同t的 的值的集合；
步骤3.2使用穷举搜索方法，当给定Si时找到最佳Ni，即在给定部署MEC服务器的基站时，计算最优的计算资源量；
步骤3.3使用排除法计算是否要在第i个基站部署MEC服务器，即计算Si，即使用一种排除方法尝试逐一移除不盈利的基站，以逐步提高总部署效率U；具体为：步骤3.3.1初始化S1，...，Si，...，SI均为1，且假设I个基站都部署了具有最佳Ni和 的MEC服务器，获取步骤3.2中得到的最佳Ni；
步骤3.3.2令i＝1；令U′＝0；U′用于存储U的最大值；
步骤3.3.3令Si＝0，即假设移除第i个基站中的MEC服务器，并储存此时λi，t，λi，j，t，λi，it，θ0，t和U′的值；
步骤3.3.4令t＝1；j＝1；
步骤3.3.5对于时隙t和第i个基站以外的基站j，根据步骤2.4所述的计算时隙t期间移动用户的期望数量的方法，计算λi，t，λi，j，t，λi，i，t和θ0，t的值；基于更新的λi，t，λi，j，t，λi，i，t和θ0，t的值，采用步骤3.1和步骤3.2所述的方法，重新计算最优的 和相应的总部署效率U，这里 的含义为对于不同的j和t，Nj和 的值的集合；如果总部署效率U大于移除第i个基站之前的总部署效率U′，则令Si＝0，即移除第i个基站并令U′＝U；否则，令Si＝1，即选择不移除第i个基站，并将参数λi，t，λi，j，t，λi，i，t，θ0，t和U′恢复为步骤3.3.3中储存的值；
步骤3.3.6若J＜I‑1，令j＝j+1，转至步骤3.3.3；否则令j＝1，转至步骤3.3.7；
步骤3.3.7若t＜T，令t＝t+1，转至步骤3.3.5；否则令t＝1，转至步骤3.3.8；
步骤3.3.8若i＜I，令i＝i+1，转至步骤3.3.5；否则转至步骤3.3.9；
步骤3.3.9得到最终最优部署决策第四步，根据最优部署决策 决定在城市中的哪些基站部署MEC服务器，并在每个基站上部署多少的计算资源量，并据此在城市中的基站上部署MEC服务器和计算资源量，方法为：
步骤4.1令i＝1；
步骤4.2根据最优部署决策中的Si，决定是否在第i个基站部署MEC服务器；若Si＝1，转至步骤4.3；否则，转至步骤4.5；
步骤4.3根据最优部署决策中的Ni，在第i个基站上部署Ni个计算资源量；
步骤4.4根据最优部署决策中的 决定第i个基站在时隙t内向云端批发 个计算资源量；
步骤4.5若i＜I，令i＝i+1，转至步骤4.2；否则转至步骤4.6；
步骤4.6完成全部基站和计算资源量的部署。
2.如权利要求1所述的一种移动边缘云计算网络中的MEC服务器部署方法，其特征在于第一步所述第i个基站处部署的计算资源量上限 的取值为[10，20]之间的任意整数；
所述a2，t的取值为[6，9]正面影响/计算资源量；a1，t取值为[8000，9500]正面影响/用户覆盖
4 4
率；σi，t和τi，t的取值均为[1×10 ，10×10]；αi，t的取值为[1，10]负面影响/(小时×基站)，βi，t的取值为[2，3]元/(负面影响×计算资源量)。
3.如权利要求1所述的一种移动边缘云计算网络中的MEC服务器部署方法，其特征在于步骤1.4所述 采用排队论方法计算，具体为：步骤1.4.1定义平均处理延迟的上限；对于计算任务，平均处理延迟 上存在一个上限，用 表示；如果 该用户的计算任务将不会被卸载到第i个基站；如果该用户的计算任务会被卸载到第i个基站上处理；
步骤1.4.2建立排队论模型；根据排队论理论，将时隙t期间第i个基站的计算任务处理建模为M/M/c排队模型，M/M/c排队模型指顾客的到达间隔服从参数为λ的负指数分布，到达的人数服从泊松分布，每位顾客的服务时间服从参数为μ的负指数分布，且顾客的到达和服务时间相互独立，系统有c个服务台的排队模型；其中c＝Ni， ρ＝λi，t/μ，ρs＝λi，t/(cμ)，并且 c，μ，ρ，ρs和 是排队论定理计算过程中所需要使用的参数，c是计算资源量的个数，μ是单位时间单位计算资源量能够处理的计算任务量，ρ是相同时间内用户的到达的平均数和单个计算资源量被服务的平均用户数的比值，ρs是相同时间内用户的到达的平均数和c个计算资源量被服务的平均用户数的比值， 是最大队列长度，E是单位计算资源量处理计算任务的能力；根据排队论定理，排队系统的稳态分布具体为：
其中
Pn指系统中有n个用户的概率，P0指系统空闲的概率；
步骤1.4.3计算用户被拒绝率；如果一个用户的计算任务的平均处理延迟那么该用户的计算任务将不会被卸载到第i个基站，即该用户会被第i个基站所拒绝；根据排队论定理，时隙t期间第i个基站处用户的被拒绝率 为：其中R为英文refuse的首字母，代表用户被边缘端拒绝后接入云端；
步骤1.4.4计算用户覆盖率；在时隙t期间第i个基站处的用户覆盖率 具体为：
4.如权利要求3所述的一种移动边缘云计算网络中的MEC服务器部署方法，其特征在于所述 的取值为[1，10]毫秒；μ的取值为[500，1000]任务/(小时×计算资源量)， 的取值为[1，10]计算任务。
5.如权利要求1所述的一种移动边缘云计算网络中的MEC服务器部署方法，其特征在于步骤2.1所述符合要求的数据集具有如下特征：
1).数据集中的信息为移动设备用户的信息或者可以被当做移动设备用户的信息；数据集中的一条数据对应一个用户；
2).数据集中的每一条数据需要包括用户ID即用户名，时间，用户所在经度，用户所在纬度的信息；
3).数据集中的数据总条数M超过一亿条；
4).数据集中的时间总跨度超过10天。
6.如权利要求1所述的一种移动边缘云计算网络中的MEC服务器部署方法，其特征在于步骤2.2所述T和I的值满足T≥240，I≥50。
7.如权利要求1所述的一种移动边缘云计算网络中的MEC服务器部署方法，其特征在于步骤2.4所述计算λi，t，λi，j，t，λi，i，t和θ0，t的值的方法是：步骤2.4.1从数据集中获得时隙t内每个用户所在的经纬度位置，还有每个基站的经纬度位置和覆盖范围；
步骤2.4.2计算λi，t的值，方法是：步骤2.4.2.1初始化λi，t＝0，令数据变量m＝1；
步骤2.4.2.2根据数据集中的第m条数据对应的用户所在的经纬度位置和第i个基站的经纬度位置和覆盖范围，判断该用户是否在第i个基站的覆盖范围内，若用户与第i个基站的距离小于第i个基站的覆盖范围，即该用户在第i个基站的覆盖范围内，且该用户与第i个基站的距离小于与其他任何基站的距离，令λi，t＝λi，t+1，转2.4.2.3；否则说明该用户不在第i个基站的覆盖范围内，λi，t保持不变，直接转2.4.2.3；
步骤2.4.2.3令m＝m+1，若m≤M，M为数据集中的数据总条数，转2.4.2.2；若m＞M，说明得到了λi，t，转至步骤2.4.3；
步骤2.4.3若第i个基站被移除，则在时隙t内，原来接入该基站的用户会分为两部分：一部分是选择接入其他基站的用户，预期数量为λi，j，t和当第i个基站被移除后不存在于任何一个基站覆盖范围内的用户，预期数量为λi，i，t；将λi，t划分为可以连接到附近的基站j处的λi，j，t和时隙t内不存在于任何一个基站覆盖范围内的λi，i，t，方法是：步骤2.4.3.1令j＝1；
步骤2.4.3.2初始化λi，j，t＝0，令数据变量m＝1；
步骤2.4.3.3根据λi，t中的第m条数据对应的用户所在的经纬度位置和第j个基站的经纬度位置和覆盖范围，判断该用户是否在第j个基站的覆盖范围内，若用户与第i个基站的距离小于第j个基站的覆盖范围，即该用户在第j个基站的覆盖范围内，且该用户与第j个基站的距离小于与其他任何基站的距离，令λi，j，t＝λi，j，t+1，转2.4.3.4；否则说明该用户不在第i个基站的覆盖范围内，λi，j，t保持不变，直接转2.4.3.4；
步骤2.4.3.4令m＝m+1，若m≤λi，t，转2.4.3.3；若m＞λi，t，说明得到了λi，j，t，转至步骤
2.4.3.5；
步骤2.4.3.5更新λj，t的值，令λj，t＝λj，t+λi，j，t；
步骤2.4.3.6令j＝j+1，j≤I‑1，转2.4.3.2；若J＞I‑1，说明得到了λi，j，t转至步骤
2.4.4；
步骤2.4.4计算λi，i，t的值，令λi，i，t＝λi，t‑∑jλi，j，t；
步骤2.4.5更新θ0，t的值，令θ0，t＝θ0，t+λi，i，t；
步骤2.5若t＜T，令t＝t+1，转至步骤2.4；否则令t＝1，转至步骤2.4；
步骤2.6若i＜I，令i＝i+1，转至步骤2.4；否则转至步骤2.7；
步骤2.7得到最终的λi，t，λi，j，t，λi，i，t和θ0，t的值。
8.如权利要求1所述的一种移动边缘云计算网络中的MEC服务器部署方法，其特征在于步骤3.1所述计算最佳 的方法是：步骤3.1.1初始化i＝1，初始化αi，t，βi，t，σi，t，τi，t，a1，t，a2，t，μ， 和Ni的值；
步骤3.1.2令t＝1；
步骤3.1.3令a＝0，b＝Ni；a代表三分法计算过程中最优值的上边界，b代表下边界；
步骤3.1.4令误差参数ε＝0.00001，若b‑a＞ε，转至步骤3.1.5；否则，转至步骤3.1.6；
步骤3.1.5令第一三分点x1＝a+(b‑a)/3，令第二三分点x2＝x1+(b‑a)/3；根据公式(10)计算U(x1)和U(x2)；这里U(x)表示当 的取值为x时，总部署效率U的值；若U(x1)＞U(x2)，则令b＝x2，转至步骤3.1.4；否则，令a＝x1；转至步骤3.1.4；
步骤3.1.6根据公式(10)计算U(a)，U(b)和U((a+b)/2)，将 的值设为a，b，(a+b)/2中能够使得U最大的值；
步骤3.1.7若t＜T，令t＝t+1，转至步骤3.1.3；否则令t＝1，转至步骤3.1.8；
步骤3.1.8若i＜I，令i＝i+1，转至步骤3.1.3；否则转至步骤3.1.9；
步骤3.1.9得到
9.如权利要求1所述的一种移动边缘云计算网络中的MEC服务器部署方法，其特征在于步骤3.2所述计算最优的计算资源量的方法是：步骤3.2.1初始化αi，t，βi，t，σi，t，τi，t，a1，t，a2，t，μ， 和Si的值；
步骤3.2.2令i＝1；
步骤3.2.3令U的最大值U′＝0；U′用于存储U的最大值；
步骤3.2.4令j＝1；
步骤3.2.5令Ni＝j；
步骤3.2.6利用步骤3.1获取的 根据公式(10)计算U；若U＞U′，则令U′＝U，令最优的Ni的值N′i＝Ni；
步骤3.2.7若 令j＝j+1，转至步骤3.2.5；否则令j＝1，转至步骤3.2.8；
步骤3.2.8若i＜I，令i＝i+1，转至步骤3.2.3；否则转至步骤3.2.9；
步骤3.2.9得到最优的Ni，即此时的N′i。
说明书 :
一种移动边缘云计算网络中的MEC服务器部署方法
技术领域
背景技术
的提高，由于无法预测的网络延迟和相对有限的Internet带宽，传统的移动云计算
(MobileCloud Computing，MCC)已经逐渐无法满足应用程序对延迟的严格要求。为了解决
这个问题，人们通过将服务器部署在靠近移动用户(例如，与蜂窝基站(BS)共置)的位置，提
出了移动边缘计算(Mobile Edge Computing，MEC)的概念。这样，用户可以在附近的MEC服
务器上处理计算任务，可以减轻网络带宽的压力并削弱不可预测的网络延迟的不利影响。
凭借其优势和移动设备的普及，MEC的发展得到了极大的推动。
务有效地卸载到MEC服务器，从而提高MEC服务器的QoS和效率。另一方面，由于相对有限的
计算资源(与云相比)和移动应用程序的不可预测行为，有必要设计高效的计算资源分配方
案以确保移动用户的QoS并提高MEC服务器的资源利用率。现有的计算资源分配方案主要分
为两类。一种是MEC服务器将其本地计算资源分配给用户或应用程序，另一种是MEC操作员
将资源分配给每个MEC服务器。这些工作大大提高了MEC系统的性能。
源分配方案，针对处理延迟，能耗，用户体验，系统成本等目标制定了优化问题。但是，它们
中的大多数都忽略了MEC服务器本身在部署时的性能和效率。只有在MEC服务器被高效率地
部署的前提下，以上的研究工作才是有意义的。值得注意的是，由于每个基站的网络覆盖范
围是有限的，每个基站和MEC服务器的部署成本是因地理位置而异的，移动用户的计算需求
量是随时间变化的等等不确定因素，高效的MEC服务器部署方法对于低MEC服务器的部署造
成的浪费，减少成本以提高MEC运营商的盈利能力、减少处理延迟以改善移动用户的体验而
言至关重要。研究MEC服务器的部署问题可以为MEC中的其他工作打下坚实的基础，具有重
要的意义。
因素，包括部署的位置，部署的计算资源量，建筑和运营成本，潜在的计算需求，处理延迟
等。如何降低MEC服务器的部署造成的浪费的同时，尽可能的保证MEC服务器对移动用户的
覆盖率和降低MEC服务器处理用户计算任务时的延迟是技术难点。
发明内容
MEC服务器对移动用户的覆盖率，降低MEC服务器处理用户计算任务时的延迟和增加能够批
发给云端的计算资源量。
设成本和限制，MEC运营商需要确定选择哪个基站来部署MEC服务器和相应数量的计算资源
量。接着，将MEC服务器的部署方法公式化为部署效率最大化问题，然后设计一个三层优化
算法以逐渐使MEC服务器的部署效率最大化。
(QoS)。然而，大多数现有工作都集中在假设MEC服务器已经部署的前提下，如何在MEC服务
器上进行计算卸载和资源分配。但是，如果不适当的部署MEC服务器，则整个MEC系统的效率
和性能会受到严重限制，从而阻碍了MEC的快速推广。
最大化。令B＝{1，2，...，I}表示为所有可以用来部署MEC服务器的基站的集合，其中I表示
基站的总数，i表示第i个基站。将部署决策用(Si，Ni)表示，其中Si∈{0，1}，表示是否在第i
个基站处部署MEC服务器，Si＝0表示不在第i个基站处部署MEC服务器，Si＝1表示在第i个基
站处部署MEC服务器；Ni为小于等于 的自然数，表示在第i个基站处部署的计算资源量
的数量，其中一个计算资源量代表一个内存容量为1TB的CPU； 表示由于第i个基站的
空间限制，第i个基站处的Ni的值的上限， 的取值由实际情况决定，为正整数， 的
优选取值为[10，20]，表示第i个基站处部署的上限计算资源量为[10，20]之间的任意整数；
2，...，T}。在这里，一个时隙可以是数十分钟或几小时，而整个时间段可以是数月或数年。
在不失一般性的前提下，假定在时隙t期间，到达第i个基站的计算任务遵循参数λi，t的泊松
分布，并且每个计算任务的计算需求遵循期望值为Ri的指数分布。λi，t的值根据实际情况计
算得出，计算过程将在第二步中给出。每个基站将按照先来先服务(FCFS)策略处理它收到
的计算任务。本发明的目标是最大化整个时间段内所有部署MEC服务器的基站的总部署效
率；
量批发到云端，则MEC服务器的部署效率越高。令a2，t表示将单位计算资源量批发到云端对
部署效率带来的正面影响， 表示第i个基站在时隙t内最优的批发的计算资源量的数量。
a2，t的取值由实际情况决定，a2，t的取值优选为[6，9]正面影响/计算资源量， 的值根据实
际情况计算得出，计算方法将在第三步中给出。令 表示在时隙t期间将计算资源从第i个
基站上批发到云端对部署效率带来的正面影响。 具体为：
率越高，MEC服务器的部署效率就越高。令 表示在时隙t期间第i个基站处的用户覆盖率，
其中A为英文accept的首字母，代表用户被边缘端接受后接入边缘端。a1，t表示在时隙t内单
位用户覆盖率对部署效率带来的正面影响。a1，t的取值由实际情况决定，a1，t的取值优选为
[8000，9500]正面影响/用户覆盖率。令 表示在时隙t期间在第i个基站处用户覆盖率对
部署效率带来的正面影响， 具体为：
上存在一个上限，用 表示。 的取值由实际情况决定， 的取值优选为[1，
10]毫秒。如果 那么该用户的计算任务将不会被卸载到第i个基站；如果
那么该用户的计算任务会被卸载到第i个基站上处理；
分布，到达的人数服从泊松分布，每位顾客的服务时间服从参数为μ的负指数分布，且顾客
的到达和服务时间相互独立，系统有c个服务台的排队模型。其中c＝Ni，
ρ＝λi，t/μ，ρs＝λi，t/(cμ)，并且 在此c，μ，ρ，ρs和 是排
队论定理计算过程中所需要使用的参数，c是服务台的个数，这里指计算资源量的个数，μ是
每个用户的平均服务时间，这里指单位时间单位计算资源量能够处理的计算任务量，ρ是相
同时间内用户的到达的平均数和单个计算资源量被服务的平均用户数的比值，ρs是相同时
间内用户的到达的平均数和c个计算资源量被服务的平均用户数的比值， 是最大队列长
度，E是单位计算资源量处理计算任务的能力。μ和 的取值由实际情况决定，μ的取值优选
为[500，1000]任务/(小时×计算资源量)， 的取值优选为[1，10]计算任务和的取值分别
为。根据排队论定理，排队系统的稳态分布具体为：
所拒绝；根据排队论定理，时隙t期间第i个基站处用户的被拒绝率 为：
也就意味着MEC服务器的部署效率降低。令第i个基站处的计算延迟对部署效率带来的负面
影响为 通常， 是平均处理延迟 的递增凸函数。这是因为移动用户对处理延迟很
敏感。在本发明中，将 设置为：
4 4
情况决定，σi，t和τi，t的取值均为[1×10，10×10]。
低。通常，建设和运营造成的浪费量主要来自两个方面：一方面是在基站上部署MEC服务器
的建设和日常维护会造成一定的浪费量。另一方面是MEC服务器上计算资源的每日运营造
成的浪费量。令αi，t表示时隙t期间的第i个基站的平均浪费量，令βi，t表示单位计算资源量
的平均浪费量。gi，t和βi，t的取值由实际情况决定，αi，t的取值为[1，10]负面影响/(小时×基
站)，βi，t的取值为[2，3]元/(负面影响×计算资源量)。令 表示在时隙t期间在基站i处
MEC服务器的建设和运营造成的浪费， 具体为：
的部署造成的浪费的同时，尽可能的保证MEC服务器对移动用户的覆盖率，降低MEC服务器
处理用户计算任务时的延迟和增加能够批发给云端的计算资源量；Si∈{0，1}， 表示Si只
能从0和1之间取值，Si＝0表示不在第i个基站处部署MEC服务器，Si＝1表示在第i个基站处
部署MEC服务器； 表示Ni为小于等于 的自然数；
表示平均处理延迟不能超过其上限
盖范围内的用户数、每个时隙内每个基站处理计算任务的延迟等)的值。具体是：
j)处的λi，j，t和时隙t内不处于任何其他基站覆盖范围内的用户数量θ0，t。在这里，λi，j，t表示
时隙t期间接近并被第j个基站覆盖且在第i个基站被移除后会选择连接到第j个基站的移
动用户的预期数量，而λi，i，t表示在时隙t内仅被第i个基站覆盖且在第i个基站被移除后不
处于任何基站覆盖范围内的移动用户的预期数量。λi，t，λi，j，t，λi，i，t和θ0，t的值均需要计算。
方法是：
基站的距离小于第i个基站的覆盖范围，即该用户在第i个基站的覆盖范围内，且该用户与
第i个基站的距离小于与其他任何基站的距离，令λi，t＝λi，t+1，转2.4.2.3；否则说明该用户
不在第i个基站的覆盖范围内，λi，t保持不变，直接转2.4.2.3；
任何一个基站覆盖范围内的用户，预期数量为λi，i，t。因此需将λi，t划分为可以连接到附近的
基站j(i≠j)处的λi，j，t和时隙t内不存在于任何一个基站覆盖范围内的λi，i，t，方法是：
站的距离小于第j个基站的覆盖范围，即该用户在第j个基站的覆盖范围内，且该用户与第j
个基站的距离小于与其他任何基站的距离，令λi，j，t＝λi，j，t+1，转2.4.3.4；否则说明该用户
不在第i个基站的覆盖范围内，λi，j，t保持不变，直接转2.4.3.4；
第j个基站的用户数量，因此λj，t＝λj，t+λi，j，t；
∑jλi，j，t；
当第i个基站被移除后不存在于任何一个基站覆盖范围内的用户数量，因此θ0，t＝θ0，t+
λi，i，t；
的集合。具体是：
(x2)，则令b＝x2，转至步骤3.1.4；否则，令a＝x1；转至步骤3.1.4；
函数，很难设计一种有效的方法来找到最优的Si。因此，使用一种排除方法尝试逐一移除不
盈利的基站，以逐步提高总部署效率U。具体为：
和θ0，t的值，采用步骤3.1和步骤3.2所述的方法，重新计算最优的 和相应的总
部署效率U，这里 的含义为对于不同的j和t，Nj和 的值的集合；如果总部署
效率U大于移除第i个基站之前的总部署效率U′(步骤3.2中得到)，则令Si＝0，即移除第i个
基站并令U′＝U；否则，令Si＝1，即选择不移除第i个基站，并将参数λi，t，λi，j，t，λi，i，t，θ0，t和
U′恢复为步骤3.3.3中储存的值；
计算资源量，。方法为：
附图说明
具体实施方式
最大化。令B＝{1，2，...，I}表示为所有可以用来部署MEC服务器的基站的集合，其中I表示
基站的总数，i表示第i个基站。将部署决策用(Si，Ni)表示，其中Si∈{0，1}，表示是否在第i
个基站处部署MEC服务器，Si＝0表示不在第i个基站处部署MEC服务器，Si＝1表示在第i个基
站处部署MEC服务器；Ni为小于等于 的自然数，表示在第i个基站处部署的计算资源量
的数量，其中一个计算资源量代表一个内存容量为1TB的CPU； 表示由于第i个基站的
空间限制，第i个基站处的Ni的值的上限， 的取值由实际情况决定，在本发明的数值实
验中， 的取值为[10，20]，表示第i个基站处部署的上限计算资源量为[10，20]之间的
任意整数；
2，...，T}。在这里，一个时隙可以是数十分钟或几小时，而整个时间段可以是数月或数年。
在不失一般性的前提下，假定在时隙t期间，到达第i个基站的计算任务遵循参数λi，t的泊松
分布，并且每个计算任务的计算需求遵循期望值为Ri的指数分布。λi，t的值根据实际情况计
算得出，计算过程将在第二步中给出。每个基站将按照先来先服务(FCFS)策略处理它收到
的计算任务。本发明的目标是最大化整个时间段内所有部署MEC服务器的基站的总部署效
率；
量批发到云端，则MEC服务器的部署效率越高。令a2，t表示将单位计算资源量批发到云端对
部署效率带来的正面影响， 表示第i个基站在时隙t内最优的批发的计算资源量的数量。
a2，t的取值由实际情况决定，在本发明的数值实验中，a2，t的取值为[6，9]正面影响/计算资
源量， 的值根据实际情况计算得出，计算方法将在第三步中给出。令 表示在时隙t期
间将计算资源从第i个基站上批发到云端对部署效率带来的正面影响。 具体为：
率越高，MEC服务器的部署效率就越高。令 表示在时隙t期间第i个基站处的用户覆盖率，
其中A为英文accept的首字母，代表用户被边缘端接受后接入边缘端。a1，t表示在时隙t内单
位用户覆盖率对部署效率带来的正面影响。a1，t的取值由实际情况决定，在本发明的数值实
验中，a1，t的取值为[8000，9500]正面影响/用户覆盖率。令 表示在时隙t期间在第i个基
站处用户覆盖率对部署效率带来的正面影响， 具体为：
上存在一个上限，用 表示。 的取值由实际情况决定，在本发明的数值实验中，
的取值为[1，10]毫秒。如果 那么该用户的计算任务将不会被卸载到第i
个基站；如果 那么该用户的计算任务会被卸载到第i个基站上处理；
分布，到达的人数服从泊松分布，每位顾客的服务时间服从参数为μ的负指数分布，且顾客
的到达和服务时间相互独立，系统有c个服务台的排队模型。其中c＝Ni，
ρ＝λi，t/μ，ρs＝λi，t/(cμ)，并且 在此c，μ，ρ，ρs和 是排
队论定理计算过程中所需要使用的参数，c是服务台的个数，这里指计算资源量的个数，μ是
每个用户的平均服务时间，这里指单位时间单位计算资源量能够处理的计算任务量，ρ是相
同时间内用户的到达的平均数和单个计算资源量被服务的平均用户数的比值，ρs是相同时
间内用户的到达的平均数和c个计算资源量被服务的平均用户数的比值， 是最大队列长
度，E是单位计算资源量处理计算任务的能力。μ和 的取值由实际情况决定，在本发明的
数值实验中，μ的取值为[500，1000]任务/(小时×计算资源量)， 的取值为[1，10]计算任
务和的取值分别为。根据排队论定理，排队系统的稳态分布具体为：
所拒绝；根据排队论定理，时隙t期间第i个基站处用户的被拒绝率 为：
也就意味着MEC服务器的部署效率降低。令第i个基站处的计算延迟对部署效率带来的负面
影响为 通常， 是平均处理延迟 的递增凸函数。这是因为移动用户对处理延迟很
敏感。在本发明中，将 设置为：
4 4
情况决定，在本发明的数值实验中，σi，t和τi，t的取值均为[1×10，10×10]。
低。通常，建设和运营造成的浪费量主要来自两个方面：一方面是在基站上部署MEC服务器
的建设和日常维护会造成一定的浪费量。另一方面是MEC服务器上计算资源的每日运营造
成的浪费量。令αi，t表示时隙t期间的第i个基站的平均浪费量，令βi，t表示单位计算资源量
的平均浪费量。αi，t和βi，t的取值由实际情况决定，在本发明的数值实验中，αi，t和的取值为
[1，10]负面影响/(小时×基站)，βi，t的取值为[2，3]元/(负面影响×计算资源量)。令 表
示在时隙t期间在基站i处MEC服务器的建设和运营造成的浪费， 具体为：
的部署造成的浪费的同时，尽可能的保证MEC服务器对移动用户的覆盖率，降低MEC服务器
处理用户计算任务时的延迟和增加能够批发给云端的计算资源量；Si∈{0，1}， 表示Si只
能从0和1之间取值，Si＝0表示不在第i个基站处部署MEC服务器，Si＝1表示在第i个基站处
部署MEC服务器； 表示Ni为小于等于 的自然数；
表示平均处理延迟不能超过其上限
盖范围内的用户数、每个时隙内每个基站处理计算任务的延迟等)的值。具体是：
(https：//outreach.didichuxing.com/appEn‑vue)/dataList)上发布。将每一个使用“滴
滴出行”APP的用户看作是将计算任务上传到MEC系统中的移动用户，以模拟移动用户。该数
据集的时间范围是2016年10月1日至31日。从该数据集中，可以获得每个移动用户的实时经
度和纬度信息。然后，从Opencellid(https：//opencellid.org)获得每个基站经度和纬度
信息以及该区域中每个基站的覆盖范围；
即T＝744；取I为数据集中出现的基站的总数，即I＝184；
j)处的λi，j，t和时隙t内不处于任何其他基站覆盖范围内的用户数量θ0，t。在这里，λi，j，t表示
时隙t期间接近并被第j个基站覆盖且在第i个基站被移除后会选择连接到第j个基站的移
动用户的预期数量，而λi，i，t表示在时隙t内仅被第i个基站覆盖且在第i个基站被移除后不
处于任何基站覆盖范围内的移动用户的预期数量。λi，t，λi，j，t，λi，i，t和θ0，t的值均需要计算。
方法是：
基站的距离小于第i个基站的覆盖范围，即该用户在第i个基站的覆盖范围内，且该用户与
第i个基站的距离小于与其他任何基站的距离，令λi，t＝λi，t+1，转2.4.2.3；否则说明该用户
不在第i个基站的覆盖范围内，λi，t保持不变，直接转2.4.2.3；
任何一个基站覆盖范围内的用户，预期数量为λi，i，t。因此需将λi，t划分为可以连接到附近的
基站j(i≠j)处的λi，j，t和时隙t内不存在于任何一个基站覆盖范围内的λi，i，t，方法是：
站的距离小于第j个基站的覆盖范围，即该用户在第j个基站的覆盖范围内，且该用户与第j
个基站的距离小于与其他任何基站的距离，令λi，j，t＝λi，j，t+1，转2.4.3.4；否则说明该用户
不在第i个基站的覆盖范围内，λi，j，t保持不变，直接转2.4.3.4；
第j个基站的用户数量，因此λj，t＝λj，t+λi，j，t；
∑jλi，j，t；
当第i个基站被移除后不存在于任何一个基站覆盖范围内的用户数量，因此θ0，t＝θ0，t+
λi，i，t；
的集合。具体是：
(x2)，则令b＝x2，转至步骤3.1.4；否则，令a＝x1；转至步骤3.1.4；
函数，很难设计一种有效的方法来找到最优的Si。因此，使用一种排除方法尝试逐一移除不
盈利的基站，以逐步提高总部署效率U。具体为：
和θ0，t的值，采用步骤3.1和步骤3.2所述的方法，重新计算最优的 和相应的总
部署效率U，这里 的含义为对于不同的j和t，Nj和 的值的集合；如果总部署
效率U大于移除第i个基站之前的总部署效率U′(步骤3.2中得到)，则令Si＝0，即移除第i个
基站并令U′＝U；否则，令Si＝1，即选择不移除第i个基站，并将参数λi，t，λi，j，t，λi，i，t，θ0，t和
U′恢复为步骤3.3.3中储存的值；
计算资源量，。方法为：
MEC服务器的基站，其中圆点表示部署MEC服务器的基站，方点表示不部署MEC服务器的基
站，；
批发的计算资源量。其中圆点、方点、上三角形点、下三角形点分别表示编号为95，100，118，
167的基站在10月10日的24个小时内向云端批发的计算资源量；
的MEC部署方法在效率提高方面具有明显优势。具体为：
总部署效率进行对比的结果图。其中横坐标表示用以比较的四种方法：TOA、K‑means、K‑top
和Random，纵坐标表示每种方法所对应的总部署效率；
发明可以在降低MEC服务器的部署造成的浪费的同时，尽可能的保证MEC服务器对移动用户
的覆盖率和降低MEC服务器处理用户计算任务时的延迟以及提高边缘与云共享计算资源产
生的潜在收益，在效率提高方面具有明显优势。