一种移动边缘运算的负载平衡和调度方法

摘要

一种移动边缘运算的负载平衡和调度方法，属于流量控制技术领域，包括以下步骤：步骤S1，使用K‑means算法，对用户设备进行分群，得到用户设备的初步团簇部署信息；步骤S2，云端验证用户设备的初步团簇部署信息是否满足负载均衡；步骤S3，单个用户设备位移时，触发负载调度机制。本方案使用K‑means算法，对用户设备进行分群，然后将用户设备的服务副本部署到最接近分群中心的边缘服务器上，以降低用户设备与边缘节点的距离，从而降低服务的响应时间。

说明书

技术领域

本发明属于流量控制技术领域，特别涉及一种移动边缘运算的负载平衡和调度方法。

背景技术

移动边缘运算（Mobileedgecomputing，MEC），是一个网络架构的概念，在移动网络的边缘提供云端运算的能力，以及IT服务的环境。相比于传统的网络架构和模式，MEC具有很多明显的优势，能改善传统网络架构和模式下时延高、效率低等诸多问题，也正是这些优势，使得MEC成为5G的关键技术。

MEC将计算和存储能力“下沉”到网络边缘，由于距离用户更近，用户请求不再需要经过漫长的传输网络到达遥远的核心网被处理，而是由部署在本地的MEC服务器将一部分流量进行卸载，直接处理并响应用户，因此通信时延将会大大降低。以视频传输为例，在不使用MEC的传统方式下，每个用户终端在发起视频内容调用请求时，首先需要经过基站接入，然后通过核心网连接目标内容，再逐层进行回传，最终完成终端和该目标内容间的交互，这样的连接和逐层获取的方式是非常耗时的。引入MEC解决方案后，在靠近使用者的基站侧部署MEC服务器，利用MEC提供的存储资源将内容缓存在MEC服务器上，用户可以直接从MEC服务器获取内容，不再需要通过漫长的回程链路从相对遥远的核心网获取内容数据。这样可以极大地节省用户发出请求到被响应之间的等待时间，从而提升用户服务质量体验。

然而，MEC服务器的计算资源有限，若过多使用者向同一台边缘服务器要求服务，将造成频宽下降。另外，若服务部署不均衡，会使得某些边缘服务器长时间闲置，从而造成资源的浪费。

公开号为CN112601256A的中国专利公开了一种超密集网络中基于MEC-SBS簇化的负载调度方法，如图1所示，该方案通过使用分区算法，将系统中MEC-SBS划分到多个非重叠的计算协作簇中，从而实现将大规模MEC-SBS计算协作问题转化成计算协作簇中的小规模MEC-SBS计算协作问题。但是，其具有以下不足：

1，该方案采用k-means分簇算法构建初始协作簇，但是未考虑边缘服务器的状态以及服务人数。如果服务人数过多，会导致频宽下降，网络通信质量变差。

2，移动用户设备是动态的，初始的分簇不一定适合后续移动后的用户设备，因此，移动用户设备需要转换与其连接的边缘服务器。针对该转换方式，CN112601256A的中国专利公开了步骤二，卸载计算任务；移动用户设备选择与之信道增益最好的MEC-SBS进行关联，然后向与之关联的MEC-SBS卸载其产生的计算任务。但是，该步骤中，仅仅是针对初始化后的调整，并非是针对单个用户设备的因为位置移动的调整，缺少单个用户设备的转换机制。

发明内容

鉴于上述现有技术的不足之处，本发明的目的在于提供一种移动边缘运算的负载平衡和调度方法。

为了达到上述目的，本发明采取了以下的技术方案。

一种移动边缘运算的负载平衡和调度方法，包括以下步骤：

步骤S1，使用K-means算法，对用户设备进行分群，得到用户设备的初步团簇部署信息；

步骤S1a，用户设备选择一个边缘节点为主节点，其余的所有边缘节点为从节点，并将上述选择信息发送给主节点；

步骤S1b，主节点将所有边缘节点的经纬度坐标设定为团簇的初始中心点；主节点告知其余边缘节点为从节点，并收集所有边缘节点的经纬度坐标信息；

步骤S1c，从节点计算与其通信连接的用户设备到与该用户设备最近的

团簇的初始中心点的距离，将距离同一团簇的初始中心点最近的用户设备归属于一个团簇，然后将距离信息和团簇信息回传至主节点；

步骤S1d，主节点接收到所有从节点回传的距离信息和团簇信息后，重新计算各团簇的新中心点；选定团簇的簇数为边缘节点的个数k，然后判断是否达到收敛条件；

若未达到收敛条件，则返回到步骤S1b重新设置团簇中心点：根据每个团簇中的用户设备，计算这些用户设备的中心点，当做该团簇的新的中心点；重复步骤S1b至步骤S1d继续迭代运算直到计算结果，达到收敛条件为止；

若达到收敛条件，主节点将最后的团簇中心点对应到离它最近的实际边缘节点上；

步骤S1e，输出团簇集，得到用户设备的初步团簇部署信息，并将上述信息发送至云端；每个用户设备都只唯一归属于一个团簇；

步骤S2，云端验证用户设备的初步团簇部署信息是否满足负载均衡；

步骤S3，单个用户设备位移时，触发负载调度机制。

进一步，步骤S1d中，收敛条件设定为所有团簇中心点移动皆小于阈值，即聚准则函数

3.根据权利要求2所述的一种移动边缘运算的负载平衡和调度方法，其特征在于，步骤S2包括以下步骤：

步骤S2a，针对边缘节点的集合E中的每个边缘节点，依次检查是否有超过负荷的情形发生；其中，边缘节点的集合E={E

若I

否则，转入步骤S3；

步骤S2b，将超负载的边缘节点E

步骤S2c，根据用户设备的初步团簇部署信息和边缘节点的部署信息，将未超过负载的边缘节点根据其与E

步骤S2d，将E

步骤S2e，若O

若O

步骤S2f，依序继续检查E集合中每个边缘节点，并重复步骤S2b至步骤S2e，直到所有边缘节点都没有超过负载；

步骤S2g，云端发送信息告知边缘节点进行服务转移的流程，边缘节点发送信息告知与其连接的用户设备改变连线，将属于同一团簇的用户设备移动到与该团簇中心点所对应的边缘服务器上。

进一步，步骤S3，包括以下步骤：

步骤S3a，用户设备定期向与其通信连接的边缘节点传送心跳信息，心跳信息包括：用户装置的识别号、纬度、经度、当前连线的基站名称和局域网地址、心跳发送时间；

步骤S3b，边缘节点主动侦测用户设备是否位移；边缘节点根据用户设备连线基站的局域网地址位置来判断用户设备是否移动：当用户设备移动时会转换连线基站，连线的基站局域网地址就会改变，就表示用户设备已经位移，且通过基站局域网转换即可得知用户设备的移动方向；当用户设备转换位移时，就表述有更适合的边缘节点能为其提供服务，转入步骤S3c；

步骤S3c，将用户设备转换连线的基站所对应的边缘节点作为目标边缘节点，并将目标边缘节点的信息发送给该待调度的用户设备；

步骤S3d，用户设备接收到目标边缘节点的信息后，会先转移系统通道向目标边缘节点连线，接着再纪录服务相关信息并转换服务通道；转换完毕后，该用户设备转移至目标边缘节点继续使用服务，负载调度机制执行完毕。

本发明所能够达到的技术效果：

1.本方案使用K-means算法，对用户设备进行分群，然后将用户设备的服务副本部署到最接近分群中心的边缘服务器上，以降低用户设备与边缘节点的距离，从而降低服务的响应时间。

2.本方案采用负载平衡机制，弥补了K-means算法未考虑边缘服务器负载平衡的缺陷。本方案将计算的部署结果回传到云端，云端验证是否有任一边缘节点负载过重：若有，则启动负载平衡机制，根据边缘节点的负荷能力调整部署结果，迭代运算寻找下一个边缘节点，直到负载平衡机制执行完毕。本方案避免过多使用者向同一台边缘服务器要求服务导致频宽下降进而增加网络响应时间，根据边缘服务器状态、能力、服务部署位置等信息，调整边缘服务器服务人数。

3.本方案采用负载调度机制和心跳机制，监控用户设备的移动位置，实时掌握用户设备状态，当用户设备位移时，适时调整其连线的边缘服务器，让用户设备在移动的过程中也能够保持一定的服务质量。

4.当移动用户设备移动到未部署边缘服务器的网域时，原边缘服务器仍会根据移动用户设备的位置要求一台适合的边缘服务器为其提供连线。虽然移动用户设备与边缘服务器不在同一个网域内，但相对于遥远的云端中心，该种连接方式仍然拥有较低的网络延迟时间的优势。

实验结果显示，本方案能够有效率的决定合适的边缘节点的部署位置，有效地降低5~22%用户设备要求服务的响应时间。

附图说明

图1是公开号为CN101478826A的中国专利申请的无线传感器网络结构示例图；

图2是传统的k-means团簇算法的流程图；

图3是本发明的步骤S1和步骤S2的流程图；

图4是本发明的步骤S3的流程图；

图5是本发明的网络结构示例图。

具体实施方式

下面结合附图，对本发明作进一步详细说明。

移动边缘运算（Mobileedgecomputing，MEC）作为云计算的演进，将应用程序托管从集中式数据中心下沉到网络边缘，更接近消费者和应用程序生成的数据，在靠近移动用户的网络边缘提供IT和云计算的能力，并利用网络能力开放获得高带宽、低延迟、近端部署优势，从而产生新的业务和收入的机会，创造出新的商业模式。

MEC是实现5G低延迟和提升带宽速率等的关键技术之一，同时MEC为应用程序和服务打开了网络边缘，包括来自第三方的应用程序和服务，使得通信网络可以转变成为其它行业和特定客户群的多功能服务平台。

MEC基本采用三层式架构，由近至远，分别为移动用户设备、边缘节点、云端。

云端用以处理较大的任务以及持续性的服务。

边缘节点部署于基站附近，负责协助云端部署服务、收集资料，并掌握移动用户设备的状态。

k-means团簇算法，其基本思路为，对于给定的样本集，按照样本之间的距离大小，将样本集划分为k个簇，让簇内的点尽量紧密的连在一起，而让簇间的距离尽量的大。其基本的步骤为：

step1：选定要团簇的簇数k，选择k个中心点。

step2：针对每个样本点，找到距离其最近的中心点（寻找组织），距离同一中心点最近的点为一个类，这样完成了一次团簇。

step3：判断团簇前后的样本点的类别情况是否相同，如果相同，则算法终止，否则进入step4。

step4：针对每个类别中的样本点，计算这些样本点的中心点，当做该类的新的中心点，继续step2。

如图2所示，K-Means算法流程如下：

1)输入是样本集D={

2）计算各样本点至各中心点之距离并选择离资料点最近的团簇作为所属团簇；依据各样本点选择的结果重新计算各团簇之中心点；然后判断是否达到收敛条件：

a)将簇划分C初始化为C

b)对于i=1,2...m,计算样本

c)对于j=1,2,...,k,对C

e)收敛条件为中心点移动的幅度或是设定迭代回合数；中心点移动的幅度小于设定值，则团簇准则函数

聚准则函数J中，k为中心点个数，

3）输出团簇集C={C

K-means算法一般采用聚准则函数J为目标函数，其目标就是找到团簇准则函数的最小值。通过K-means算法可以将样本点分为k个团簇。采用K-means算法的优点是，可以将用户设备部署于最接近的边缘服务器附近，从而有效地降低整个网络的响应时间。

但是，K-means算法并没有考虑到边缘服务器的负载，当样本点（用户设备）过于集中时，密集样本点处的中心点（边缘服务器）将超负荷运作，因此，有必要在K-means算法的基础上，引入负载平衡机制。

同时，K-means算法初始化了用户设备的布局，但是，未考虑到移动用户设备是动态的，初始的分簇不一定适合后续移动后的用户设备。因此，有必要在K-means算法的基础上，引入负载调度机制，可以根据当前的用户设备的状态，实时调整部署。

一种移动边缘运算的负载平衡和调度方法，如图3、图4和图5所示，包括以下步骤：

步骤S1，使用K-means算法，对用户设备进行分群，得到用户设备的初步团簇部署信息。

步骤S1a，用户设备选择一个边缘节点为主节点，其余的所有边缘节点为从节点，并将上述选择信息发送给主节点；

步骤S1b，主节点将所有边缘节点的经纬度坐标设定为团簇的初始中心点；主节点告知其余边缘节点为从节点，并收集所有边缘节点的经纬度坐标信息。

步骤S1c，从节点计算与其通信连接的用户设备到与该用户设备最近的团簇的初始中心点的距离，将距离同一团簇的初始中心点最近的用户设备归属于一个团簇，然后将距离信息和团簇信息回传至主节点。

步骤S1d，主节点接收到所有从节点回传的距离信息和团簇信息后，重新计算各团簇的新中心点；选定团簇的簇数为边缘节点的个数k，然后判断是否达到收敛条件。

收敛条件设定为所有团簇中心点移动皆小于阈值，例如小于一米，即聚准则函数

若未达到收敛条件，则返回到步骤S1b重新设置团簇中心点：根据每个团簇中的用户设备，计算这些用户设备的中心点，当做该团簇的新的中心点；重复步骤S1b至步骤S1d继续迭代运算直到计算结果（聚准则函数J）达到收敛条件为止。

若达到收敛条件，主节点将最后的团簇中心点对应到离它最近的实际边缘节点上。

步骤S1e，输出团簇集，得到用户设备的初步团簇部署信息，并将上述信息发送至云端。每个用户设备都只唯一归属于一个团簇。

由于团簇的中心点不见得刚好有实体的边缘节点，因此将团簇中心点对应到离它最近的边缘节点上，有可能多个用户设备会对应到同一个边缘节点上，而导致边缘节点负载不平衡。

步骤S2，云端验证用户设备的初步团簇部署信息是否满足负载均衡。

步骤S2a，针对边缘节点的集合E中的每个边缘节点，依次检查是否有超过负荷的情形发生；其中，边缘节点的集合E={E

若I

否则，转入步骤S3。

步骤S2b，将超负载的边缘节点E

步骤S2c，根据用户设备的初步团簇部署信息和边缘节点的部署信息，将未超过负载的边缘节点根据其与E

步骤S2d，将E

步骤S2e，若O

若O

步骤S2f，依序继续检查E集合中每个边缘节点，并重复步骤S2b至步骤S2e，直到所有边缘节点都没有超过负载。

步骤S2g，云端发送信息告知边缘节点进行服务转移的流程，边缘节点发送信息告知与其连接的用户设备改变连线，将属于同一团簇的用户设备移动到与该团簇中心点所对应的边缘服务器上。

本方案在K-means计算完毕后会针对计算结果进行边缘节点的负载评估，由于云端能够掌握所有边缘节点的负荷能力，因此采用云端的集中式负载机制，当云端确认所有服务的部署皆在边缘节点可承受之范围内，则发送服务用户设备转移消息，将用户设备部署在适当的位置。

步骤S3，单个用户设备位移时，触发负载调度机制。

步骤S3a，用户设备定期向与其通信连接的边缘节点传送心跳信息，心跳信息包括：用户装置的识别号、纬度、经度、当前连线的基站名称和局域网地址、心跳发送时间。

步骤S3b，边缘节点主动侦测用户设备是否位移。边缘节点根据用户设备连线基站的局域网地址位置来判断用户设备是否移动：当用户设备移动时会转换连线基站，连线的基站局域网地址就会改变，就表示用户设备已经位移，且通过基站局域网转换即可得知用户设备的移动方向；当用户设备转换位移时，就表述有更适合的边缘节点能为其提供服务，转入步骤S3c。

步骤S3c，将用户设备转换连线的基站所对应的边缘节点作为目标边缘节点，并将目标边缘节点的信息发送给该待调度的用户设备。

步骤S3d，用户设备接收到目标边缘节点的信息后，会先转移系统通道向目标边缘节点连线，接着再纪录服务相关信息并转换服务通道；转换完毕后，该用户设备转移至目标边缘节点继续使用服务，负载调度机制执行完毕。

本方案采用心跳传送机制，使得边缘节点能够掌握用户设备信息及动向，因此用户设备需定期传送心跳信息。边缘节点收到心跳信息后记录并分析，如果用户设备位移，则给予用户设备对应的信息，以执行负载调度流程。相对于本方案，如果位移的移动设备，向云端要求服务响应并转换服务通道，响应的时间多出3~4倍。

本方案，将移动用户设备的信息，传送至边缘服务器，由边缘服务器来掌握移动用户设备的动向以及调整服务部署等。相对于将用户设备的信息传送至云端的集中式管理的模式，本方案降低了网络延迟。相对于当有需要时才将用户设备的信息传送至边缘服务器或云端的自主式管理的模式，本方案能系统的掌握移动用户设备的动向并实时调整用户的需求。另外，本方案将移动用户设备的信息传送至边缘服务器后，边缘服务器又将所有移动用户设备的信息传送至云端，使得云端能够掌握所有用户设备的信息，有利于云端提供各项系统服务。

值得指出的是，公开号为CN112601256A的中国专利公开了一种超密集网络中基于MEC-SBS簇化的负载调度方法，其是将各个团簇进行组合形成计算协作簇（见其图1），k-means分簇算法中样本点为MEC-SBS（移动边缘计算服务器）。而在本方案中，是将用户设备进行分簇，使其连接到最合适的边缘服务器，k-means分簇算法中样本点为用户设备。因此，两者的计算对象并不相同。

可以理解的是，对本领域普通技术人员来说，可以根据本发明的技术方案及其发明构思加以等同替换或改变，而所有这些改变或替换都应属于本发明所附的权利要求的保护范围。