分布式场景下基于拍卖算法的边缘智能节点任务分配

2022-10-13 12:33李浩陈迪李林王莉
移动通信 2022年9期
关键词:竞标投标边缘

李浩,陈迪,李林,王莉

(63892部队,河南 洛阳 471003)

0 引言

随着当前计算机技术的迅猛发展,以及应用对计算能力要求的提升,智能边缘计算凭借其优秀的计算能力得到了越来越广泛的应用,是6G 移动通信网络非常重要的一个组成部分。智能边缘计算是由多个独立的计算系统通过移动通信网络形成逻辑集中以及物理上分布的计算系统[1]。智能边缘计算具有诸多优点,包括动态性、可靠性、实时性等[2]。为了减少网络通信时间,实现更快的处理响应,边缘计算将相关计算资源、存储能力下沉到边缘设备,使得大量的任务在边缘设备上进行处理。在分布式环境下,如何优化任务分配,使得智能边缘计算节点的资源获得更好的利用,这是智能边缘计算亟需解决的关键问题。随着用户任务的增加,智能边缘计算节点处理的复杂度也会随之增加。因此,任务分配方法的智能性显得至关重要,一个好的分配策略能够使任务获得更早的完成时间,提高任务的执行效率[3]。

分布式环境下的智能边缘计算系统可视为由多个智能边缘节点组成的集合,其主要目标是将大而复杂的系统转换成小的、彼此相互通信和协调的、易于管理的系统。分布式环境下的智能边缘计算系统具有自主性、分布性和协调性,并具有较好的自组织能力、自学习能力和推理能力[4]。在分布式网络环境下,系统中存在多个不同的边缘节点和多个不同的任务,如何将多个边缘节点合理映射到多个任务上,是任务分配的关键问题[5-6]。任务分配的目的是最大化整个系统执行任务的效益,同时最小化执行任务所需的代价。任务分配的好坏直接影响到整个系统协作的效率,并关系到各个边缘计算节点能否最大限度发挥自身能力。

在分布式场景下,多任务的高效分配方案需满足两点要求:首先,要在规定的时间内找到一个接近最优的任务分配方案,即最优性;其次,要保证任务分配方案在整个运行时间的效率,即动态性[7]。针对以上要求,本文提出了一种在分布式环境下基于拍卖算法的任务分配策略,解决6G 分布式场景下的边缘节点任务高效分配问题。在任务分配过程中,综合考虑完成任务的效益及各个边缘计算节点完成任务需付出的代价,采用拍卖的方式进行任务分配,从而得到一个任务分配方案,保证在最大化整个系统效益的同时最小化整个系统执行任务所需要的代价。

1 相关研究工作

1.1 分布式系统下的任务分配

在分布式系统中,任务分配是一个被研究多年的经典问题。任务分配的目标是把任务合理地分配到系统的每一个处理节点上,使程序的总体执行时间最短。任务分配算法的优劣影响了分布式环境下的系统性能。任务分配主要从时间和空间两个方面考虑,最终将需要分配的任务调度到相应处理机上,合理的任务分配策略能够提高处理机系统中资源的利用率、降低系统能耗以及提高任务调度的效率。影响任务分配的因素包括任务下发的价格、任务本身的执行代价、任务之间的通信开销以及任务之间的依赖关系等。

根据任务之间的关系,可以把任务分配分为两种类型:一种是任务之间没有依赖关系的独立任务的任务分配,另一种是任务之间有依赖关系,是相互之间有通信和上下文依赖关系的任务分配。针对分布式环境下的任务分配问题,国内外学者做了大量研究工作。文献[8] 针对分布式环境中的静态任务调度问题开展研究,提出了一种基于最早完成时间策略改变调度顺序的表调度算法。算法针对现有表调度算法在调度前不能准确地确定调度顺序的问题,在此基础上添加了一个动态优先级调度策略,当节点的前驱任务都已经完成调度任务时,相应地改变当前节点的优先级。文献[9] 针对分布式环境下提出了一种基于任务复制以及任务插入的聚类和归并算法,算法分为初始分簇、任务复制、任务归并以及任务插入等几个步骤,算法还充分考虑了连锁链式反应,可以解决本轮无效的任务复制在下一轮变成有效的问题。文献[10]基于合理的任务复制和分簇,实现关键任务的尽早调度,使工作流的最早完成时间得以提前,对任务簇进行聚集,从而可以充分利用任务簇中任务间可能的空闲时间;另外,对已聚类的工作流任务集使用任务后向优先合并的方法,可以实现任务间空闲时间版的有效利用,从而可优化工作流的完成时间。

1.2 拍卖算法

拍卖算法由麻省理工学院学者Bertsekas 于1988 年提出[11],后来在任务分配问题上得到了广泛的应用。陶雪丽等运用拍卖算法对物资运输任务分配问题进行了求解,得到了较优的分配结果,验证了算法在该问题上的有效性[12]。柳鹏等提出设立虚拟火力点和目标的方法对拍卖算法进行改进,并解决防空火力打击目标分配问题,讨论了拍卖算法价格增量ε 取值对目标分配结果的影响[13]。许可等针对异构多无人机系统的任务分配问题,分别设了带共享存储中心分布式拍卖算法和移除共享存储中心完全分布式拍卖算法,验证了算法的收敛性和有效性[14]。高龙设计了分布式拍卖算法,并以保障单元个体目标收益最大为分配依据,构建了装备保障体系任务分配框架[15]。

2 系统模型

2.1 任务模型

无线网络旨在实现和支撑万物智联、万务互联,成为支撑各行业的智能基础设施平台。为了适应新时代下不同产业跨界升级和新商业模式变革等诉求,无线网络系统通过深度融合通、感、算、智、存等功能于一体的无线基础设施平台,并同时具备“通信”、“感知”、“计算”、“智能”和“存储”等方面更强大业务能力;对外能够提供更强、更高效地提供“通信”、“感知”、“计算”、“智能”和“存储”等方面服务应用[16],系统模型如图1 所示。

图1 系统模型

考虑在网络覆盖区域内有n个边缘计算节点组成的边缘计算节点集合U={u1,u2,…,un},包含t个任务集合T={t1,t2,…,tn}。将这些任务主要划分为四种类型[17]:感知任务、计算任务、通信任务和智能任务。每个任务只属于其中一种类型,每种类型的任务数量不相同。假设任务在分配之前是已知的,并且在执行过程中是不变的。

2.2 任务分配模型

任务分配的目的是对边缘节点资源的合理使用,使得整体边缘计算节点的任务收益最大化。如果任务被边缘计算节点执行,那么用户需要支付相应的费用。因此,边缘节点完成用户任务的处理能够得到相应的收益。考虑单个任务的收益,主要由两部组成:任务回报和任务成本。构造任务收益函数,如下所示:

其中,Pij表示边缘计算节点i完成任务j的收益,Rj表示边缘计算节点完成任务j的回报,Cij表示边缘节点完成任务j的成本。

将边缘计算节点与任务的映射关系定义为一个匹配矩阵A={aij},其中aij∈ {0,1}表示边缘计算节点i与任务j的匹配关系。当aij=1,表示边缘计算节点i赢得投标,执行任务j,否则,aij=0。

综上所述,考虑以系统总体收益最大化的任务分配模型,具体如下所示:

其中,约束条件1 表示每个任务必须分配给一个边缘计算节点,约束条件2 表示每个边缘计算节点至多执行一个任务,约束条件3 表示对任务与边缘节点的匹配策略约束。

3 基于拍卖算法的任务分配方法设计

本节将介绍一种基于拍卖算法的任务分配方法,通过利用拍卖算法实现任务的最优分配。

拍卖算法本质上是各个拍卖参与者根据自身利益,依次对商品进行报价,通过多个轮次的竞标,最终得到相对满意的商品。基于拍卖的算法机制,将任务分配过程定义为动态拍卖过程。通过用户任务与边缘节点的动态拍卖过程,实现用户任务的合理化分配。

在基于拍卖算法的任务分配方法中,需要3 种角色的参与:第三方拍卖商、购买者和出售者。第三方拍卖商主要负责拍卖过程,确定任务最终的分配;购买者主要负责向拍卖商递交投标,投标成功的边缘计算节点,被拍卖商授予任务;出售者主要负责向拍卖商提交任务,让拍卖商负责任务的分配。

在所建立的模型中,任务分配系统作为第三方拍卖商通过无线通信等方式发布每个任务的任务信息,给予完成任务的中标边缘计算节点一定的任务奖励,其目标是最小化自身的成本。边缘节点作为投标者收到系统公布的任务信息后,根据当前状态和资源能力计算效用值,以最大化效益为目的进行任务投标。通过对每个任务的优化分配,从而实现整个系统的任务分配。对任务分配系统而言,每轮选择哪些投标者作为中标者是任务分配策略。对于边缘计算节点ni而言,每轮选择哪个任务投标ti是其投标策略,其中i∈N。假设在拍卖过程中,边缘计算节点都是自私而理性的。本文建立边缘计算节点的基于拍卖的任务分配模型,主要包括三部分:投标策略、任务匹配和激励机制。

3.1 投标策略

在投标过程中,每个收到任务信息的边缘计算节点,根据任务信息计算每个任务的收益。在每轮拍卖过程中,边缘计算节点根据任务的收益选择竞标,选择收益最大的任务进行投标。

本文采用的最大效用投标策略相比于平行拍卖算法[18],通过计算任务效用,边缘计算节点选择竞标效用最大的任务。这样做的好处是能够保证边缘计算节点的效用。同时,在第三方拍卖商决定最后的中标者,无论是哪个边缘计算节点中标,对于中标的边缘计算节点而言,都是效用最大的。相较于平行拍卖算法的投标方式,由于按照出售方的最大化效用进行分配,可能出现出售方与购买方的利益不一致,这样会导致中标的边缘计算节点所被分匹配的任务不是自身效用最大的任务。

3.2 任务匹配

当所有参加拍卖的边缘计算节点确定竞拍对象,完成投标后,则启动任务匹配。任务最终的分配也是边缘计算节点的匹配问题,其目标是确定一个边缘计算节点执行相应的任务。

在竞标过程中,某个任务存在多个边缘计算节点参与竞标。换句话说,在边缘计算节点完成竞标后,拍卖商需要进一步选择边缘计算节点,确定最终任务的分配。此时,选择权发生变化,不再是买方选择卖方,而是卖方选择买方。在确定任务的最后分配中,定义了智能分配性价比Eij,具体如下:

其中,Qi表示边缘计算节点i的资源能力,w1和w2是相应的权重系数。从上式可以看出,拍卖方不仅考虑了边缘计算节点的成本,而且考虑边缘计算节点的能力。

从上述过程可以看出,在相同出价条件下,卖方更愿意选择边缘计算较高的边缘计算节点作为任务的执行者。未被选中的边缘计算节点进入竞标失败者集合,等待下一轮拍卖的开始。

当确定本轮任务的分配,本轮拍卖立刻结束并按照拍卖结果为边缘计算节点进行分配任务,然后进行下一轮拍卖,直到所有任务都被拍卖完成或者所有边缘计算节点退出拍卖。

3.3 激励机制

为了鼓励边缘计算节点在竞标过程中提交真实的竞标价格,需要设计相应的支付规则。支付规则的确定对拍卖有着至关重要的影响,一套合理的支付规则能够保证拍卖的合理性,保证拍卖的激励相容,起到正面促进的作用。考虑到边缘计算节点的出价策略,采用Vickrey拍卖[19]机制作为最终的定价。Vickrey 拍卖也称为次高价拍卖,其核心思想是拍卖商选择第二高的出价作为最终的支付价格。通过Vickrey 拍卖方法,边缘计算节点的竞标过程中能够提供真实的竞标出价。

3.4 算法流程

本文设计的任务分配方法主要基于在线拍卖的方法实现,具体流程如图2 所示。首先,第三方拍卖商会创建一个用户集合用来收集边缘计算节点的信息;然后,整体系统会将相关任务信息提交给第三方拍卖商,第三方拍卖商广播相关任务信息;其次,边缘计算节点收到相关任务信息开始竞标,向第三方拍卖商提交出价;最后,第三方根据边缘计算节点的竞标信息,进行任务分配。基于拍卖算法的任务分配方法伪代码如下所示:

图2 基于拍卖算法的任务分配流程图

3.5 算法分析

在设计基于拍卖算法的任务分配方法中,出售方先向第三方拍卖商递交任务,并广播任务信息;然后,边缘计算节点向第三方拍卖商提交任务竞标;最后,第三方拍卖商收到边缘计算节点的竞标信息,进行任务的分配。

本文基于拍卖算法设计的任务分配方法,符合有效的拍卖机制,具体如下。

(1)个人合理性:每个竞标成功的边缘计算节点获得的回报都大于其成本,这意味每个边缘计算节点的效用都非负的;

(2)效率性:基于拍卖算法的任务分配方法包括投标策略、任务分配和激励机制,能够完成任务的有效分配;

(3)激励相容:任何边缘计算节点都不能通过提交不同于其真实成本的报价来提高其利润。

4 仿真实验与结果分析

为了验证本文算法的可行性和有效性,进行了不同情况下的仿真实验。假设在网络区域内,边缘计算节点的数量为12~32。边缘计算节点的综合能力和成本取值相同,随机分布在数值范围为[10,20]。每个任务的回报取值范围在[20,30]。为了进一步分析算法的优劣性,选择第一价格拍卖、第二价格拍卖和不考虑节点资源能力的情况进行实验对比,具体实验结果如下所示。

通过分析图3 可知,在任务数量逐渐增加的情况下,本文提出拍卖算法和其他拍卖算法所产生的任务分配收益都稳步增加。在给定任务数量范围相同的情况下,本文提出的拍卖算法所获收益值要高于其他拍卖算法的任务分配方法,算法的性能表现更好。其中,基于第一价格拍卖算法的任务分配方法所获得的收益最小,这是因为第一价格拍卖算法的中标取决于最高价,所以获得的任务收益最少。

图3 不同任务数量下的任务分配收益

由图4 可知,随任务数量的增加,本文所提出的拍卖算法和其他分配方法的性能值都不断增加。在相同任务数量的情况下,本文所提出的算法完成任务分配后的所取得任务总性能值均高于基于其他拍卖算法的任务分配方法。这是因为在任务分配过程中不仅考虑了节点的竞价,而且考虑了节点的资源能力。

图4 不同任务数量下的任务总性能值

综合图3 和图4 来看,本文所提出的拍卖算法,在不同用户数量下的总体收益和总体性能值均优于其他拍卖算法的任务分配方法。通过对比,充分体现了本文所提出的拍卖算法性能优异、表现稳定等优势,能够高效完成分布式计算任务的有效分配,平衡各边缘计算节点间的竞争关系,保证每个边缘计算节点的效能,以获得总体上更好的性能。该算法能够适应多节点协同和分布式场景下的资源和任务分配需要,从而有效应对分布式网络环境和形势的动态发展变化。

5 结束语

本文针对6G 分布式网络环境下的任务分配问题展开研究,定义了多边缘计算节点任务分配问题,制定了任务分配模型,并提出了一种基于拍卖算法的任务分配方法。考虑边缘节点之间的相互竞争,通过应用拍卖的方式对任务进行合理分配。在任务分配过程中不仅考虑任务的成本,而且考虑边缘计算节点的资源能力,提高了任务分配任务的合理性。通过实验仿真,结果表明该方法的有效性,能够实现分布式环境下任务的有效分配。

猜你喜欢
竞标投标边缘
市场化条件下武器装备竞标策略分析
造价信息管理在海外投标中的应用探讨
武器装备项目竞标组织管理研究与应用
国务院明确取消投标报名
军工企业招标投标管理实践及探讨
一张图看懂边缘计算
岁末年初的竞标秀
网上竞标在采购中的应用日益广泛
在边缘寻找自我
走在边缘