群组机器人系统资源分配策略研究

孙弋　宋冬冬

摘要：为解决应急场景下群组机器人系统稳定分配微服务资源，提升群组机器人的业务能力，采用Stackelberg博弈的模型。模型将资源提供机器人与资源消费机器人的供需关系抽象为多主多从的博弈问题，寻求在微服务资源分配时系统稳定的同时各方可获得的最大收益。在此基础构建了资源提供机器人和资源消费机器人的收益函数，并证明了在所提模型中给定一组资源提供机器人的微服务资源的定价时，资源消费机器人之间存在唯一的Nash均衡点。最后，利用了分布式迭代搜索算法，求解博弈的最终需求策略。结果表明：在应急场景下，本模型所构造的收益函数在满足系统稳定性的同时可使博弈双方获得最大收益，同时可得出资源提供机器人的均衡定价，实现微服务资源的有效分配。博弈模型构建过程符合现实逻辑、稳定性好，对未知场景中群组机器人资源分配具有一定参考价值。

关键词：群组机器人;系统稳定性;Stackelberg博弈;资源分配;纳什均衡

中图分类号：TP 242文献标志码：A

文章编号：1672-9315（2022）04-0818-08

DOI：10.13800/j.cnki.xakjdxxb.2022.0422

Research on  resource allocation strategy of group robot systemSUN Yi SONG Dongdong

（1.College of Communication and Information  Engineering，Xian University of Science and Technology，Xian 710054，China;

2.Xian Key Laboratory of Heterogeneous Network Convergence Communication，Xian 710054，China）Abstract：In order to solve the problem of stable allocation of microservice resources in the group robot system in emergency scenarios and improve the business capabilities of group robots，the stackelberg game model is adopted.The model determines the supply-demand relationship between resource-providing robots and resource-consuming robots as a multi-leader multi-follower game problem，seeking the maximum benefit that all parties can obtain while the system is stable when microservice resources are allocated.On this basis，the revenue function of resource-providing robots and resource-consuming robots are constructed，and it is proved that when the pricing of microservice resources of a set of resource-providing robots is given in the proposed model，there is a unique Nash equilibrium point between resource-consuming robots.Finally，a distributed iterative search algorithm is used to find out the final demand strategy of the game.The microservice results show that：in an emergency scenario，the revenue function constructed by this model can satisfy the system stability and  enable both parties to the game to obtain the maximum benefits，and at the same time，the equilibrium pricing of the resource-providing robots can be obtained，with the effective allocation of microservice resources  achieved.The game model construction process conforms to realistic logic and has a stronger stability，which provides a certain reference for resource allocation of group robots in unknown scenarios.

Key words：group robot;system stability;stackelberg game;resources allocation;Nash equilibrium

0引言

移动网络和物联网技术发展迅猛，大量终端设备被用于各个领域，智能终端设备迎来快速增[1]。机器人因其应用的广泛性 [2]、可以完成重复的、枯燥的、危险性高的工作而日渐成为社会发展应用的趋势 [3]。面对更加复杂的场景，单机器人的计算能力有限[4]，且不具备通信组网的能力，难以高效、高质量地完成特定情况下的任务。群组机器人主要研究如何设计大量简单的机器人通过局部交互协作，以群體的形式完成一些复杂的任务，或者模拟并实现一些预期的自组织行为[5]，而该类任务通常是单个机器人无法完成的。应急场景因实际情况的多样性、突发性以及环境的复杂性而十分棘手，因此，将群组机器人应用于应急场景是目前机器人研究的一个热点方向[6-7]。

综上，本课题提出在应急场景下采用群组机器人快速建立应急救援系统的模型，本模型主要针对应急情况发生后，现场环境信息不完整而难以施救的情况。利用群组机器人搭建一个应急救援支撑系统可为后续救援人员进入降低人身风险、提高救援保障能力和救援效率。应急场景下，系统与外界隔离，其主要计算能力和资源都集中到部分机器人上，并且有限，系统资源的合理分配可提高救援效率、降低灾害损失、提升救援服务质量。为了保障应救援系统的稳定性，群组机器人的组织形式采用中心式与分布式结合的网络结构，其中有多个中心节点和多个边缘节点，形成多云-多边体系。

云计算中的资源分配策略定义为保证物理或虚拟资源正确分配给云用户的机制[8]。在应急救援系统模型运行的初期，能够实现资源的分配是首先要考虑的，故本课题研究的重点是实现应急场景下群组机器人微服务资源的有效分配。博弈论是一个可以分析多个具有独立自主决策能力个体之间交互的工具，个体按照自己的利益做出决策，并设计了激励兼容的机制，这样个体就没有单方面偏离的动机[9]，被广泛用于解决资源分配和优化问题[10-12]。群组机器人中，每个机器人都具有自主决策能力，可根据自身需求执行相关策略。为了使自身利益最大化，群组机器人中各决策方均存在博弈。基于此，本课题提出在应急场景下，群组机器人通过博弈论分配微服务资源的模型。

文献[13]利用Stackelberg模型分析多个机器人终端竞争同一边缘云服务器中相同类型资源，利用一种结合汉明距离的动态规划算法求解，实验结果表明所提算法在缩短平均任务完成时间的同时，降低了云机器人系统的局部计算能耗，该模型仅讨论了机器人终端的效用，未讨论云端的效用。文献[14]提出了一种使用组合拍卖方法在云系统的资源分配中满足QoS标准的方法。考虑了有效资源分配的紧迫性，并确定了超过任务期限的概率及其期望值。强调了该方法具有较高的任务完成成功率，但未考虑用户的收益。文献[15]借助设备到设备（D2D）通信技术研究了多路访问边缘计算网络的最佳卸载机制，提出了一种基于 Stackelberg博弈的方法来实现价格和资源的均衡，并利用二分匹配的最优任务分配方法求解，仿真结果表明，所提方案可以获得更高的计算利润，但缺乏对用户收益的讨论。文献[16]研究了小型蜂窝网络中多设备多服务器系统的分布式计算卸载策略，目的是联合优化每个移动设备的能量消耗和延迟，并将开销最小化问题制定为策略博弈，证明了其纳什均衡的存在，仿真结果表明，所提算法可以有效的最小化每个移动设备的开销。文献[17]将移动边缘中卸载决策者和资源分配者之间的交互建模为Stackelberg博弈，构建了博弈对象和收益函数，并证明了博弈均衡的存在，设计了一种有效计算均衡的算法，仿真结果表明，所提算法在考虑联合管理计算卸载和资源分配的基础上，可以有效的最小化各方成本。但未具体讨论收益问题。

上述文献均在一定条件下讨论了博弈参与者的收益，但对博弈各方均衡收益问题讨论不足;其次，对资源分配时的重点聚焦时延与能耗上，适用于追求效率和节能的场景中。综上，为了考虑微服务资源有限场景中系统稳定性的同时，兼顾资源提供机器人和资源消费机器人各自最大收益，即均衡收益。①引入服务流行度和偏好内容流行度构建Stackelberg博弈模型，求解资源提供机器人和资源消费机器人追求各自目标时的纳什均衡策略;②通过分析所提的博弈模型，构造了参与者的收益函数。并证明了在资源提供机器人的微服务资源定价确定的情况下，资源消费机器人之间存在非合作博弈Nash均衡点;③通过拉格朗日乘子法求解出资源消费机器人的最优购买微服务资源量，再逆向地利用分布迭代求出资源提供机器人的最优定价，确保资源提供机器人和资源消费机器人的收益达到了均衡的最佳收益。

1系统模型

1.1网络模型

如圖1所示，应急场景下群组机器人系统包含N个资源提供机器人（1，2，…，N），M个资源消费机器人（1，2，…，M）。在本研究中，资源消费机器人从资源提供机器人处购买微服务资源，假定资源消费机器人的微服务资源需求量与资源提供机器人提供的微服务资源相对应，并且资源消费机器人的资源由自身和资源提供机器人共同提供。作为服务资源的提供方，资源提供机器人追求最大化收益，它们之间形成竞争。

系统模型如图1所示，具体过程为

1）资源提供机器人拥有一定量的微服务资源，为了合理的利用资源并提高业务效率，将微服务资源按一定价格出售给资源消费机器人。

2）资源消费机器人根据资源提供机器人的定价和自身需求购买微服务资源。

由于机器人电能和资源均有限，资源提供机器人会根据资源消费机器人的需求和自身的服务能力来动态的调整微服务资源的定价，而资源消费机器人会根据资源提供机器人的定价，调整购买微服务资源的数量，两者相互制约，寻求各自的最大化。

1.2资源流行度

在系统模型中，考虑实际情况，资源提供机器人的微服务资源往往有着不同的被购买频率，即它们有着不同的流行度，则资源消费机器人购买微服务资源的请求概率为Qc，其服从Zipf分布[18]

1.3偏好内容流行度

在实际情况中，不同的资源消费机器人购买微服务资源的请求存在一定的差异，且资源消费机器人的偏好不尽相同，因此，资源消费机器人请求购买微服务资源的概率也有差异，受文献[19]启示，本课题利用式（2）表示资源消费机器人的兴趣偏好

2问题构建

一个博弈模型通常由3个基本元素构成：一组参与者（a set of players）、每个参与者的动作（the action of each player）、一组效用函数（a set of utility functions）[20]。

博弈模型的决策是符合主从关系的Stackelberg博弈，参与者集合分为领导者和跟随者，其中领导者处于决策的领导地位，跟随者根据领导者的决策而做出自己的决策。每个决策个体都有自身的策略集合和对应的收益函数。Stackelberg博弈的过程表示为以下3个步骤：①领导者首先做出当前情况下的最优决策;②跟随者考虑领导者的策略，结合自身收益做出决策;③领导者再考虑跟随者的策略和自身收益函数调整其决策。整个博弈过程是动态的，当双方收益不再增加，没有决策参与者愿意改变策略时，博弈过程结束。

2.1博弈构成

2.2博弈群组构建

2.3Stackelberg纯策略纳什均衡

所提模型由N个资源提供机器人和M个资源消费机器人构成，在应急场景下，整个系统与外界隔离，系统的资源有限。当资源提供机器人设定微服务资源价格后，资源消费机器人为了使用微服务资源，它们之间形成非合作博弈。当资源提供机器人设定的微服务资源价格偏高时，资源消费机器人选择不购买资源;当资源提供机器人设定的微服务资源价格偏低时，自身无法获得利润，因此资源提供机器人和资源消费机器人之间形成主从博弈的Stackelberg博弈。博弈是为了求出Nash均衡点，进而得到资源提供机器人和资源消费机器人的最佳决策，最大化双方的收益。

Stackelberg博弈通常通过分析完全信息Nash均衡点来求解：在微服务资源分配和定价策略中，没有参与者有动机单方面改变策略，以获得更好效用，而不损害其他参与者的效用[21]。

在本模型中，资源提供机器人之间共享资源消费机器人的微服务资源请求，每个资源提供机器人决定微服务资源的定价以最大化自身收益。

3博弈求解

Stackelberg博弈通常使用逆向归纳法求解，上述章节已经证明了本课题所提模型存在Nash均衡点。基于此，先求解资源消费机器人获得的最优微服务资源数量，再利用求得的最优微服务资源计算出资源消费机器人的最优定价。

3.1资源消费机器人最优资源需求

应急场景中，系统与外界隔离，资源均有限，因此在实际求解中，需要考虑资源消费机器人的约束。资源消费机器人的最优购买数量x可表示为

3.2资源提供机器人的最优资源定价

求得资源消费机器人的最优购买需求后，利用分布式迭代法求解资源提供机器人的最优定价，算法如下。

4仿真与分析

图2给出资源提供机器人1与资源提供机器人2的微服务资源定价关系，2条曲线上的点分别表示当前资源提供机器人对另一资源提供机器人的最佳定价策略。由图可知，（3.1，3.5）是双方定价的平衡点，也是博弈均衡点，在该点处资源提供机器人1与资源提供机器人2都没有意愿改变定价策略使自己的收益降低，为双方收益最大化的最佳定价组合。

图4给出了在本课题的模型源消费机器人的收益随迭代次数的变化图。可以看出资源消费机器人的收益在纳什均衡点之前有波动，这是因为资源消费机器人1和资源消费机器人2的定价变化引起的，通资源消费机器1和资源消费机器2的定价达到纳什均衡后，两者的定价都趋于稳定，因此资源消费机器人的收益也趋于稳定。

图5给出了在本课题的模型下资源提供机器人的收益和迭代次数的关系。可以看出资源提供机器人的收益在纳什均衡点之前有波动，这是因为资源提供机器人1和通资源提供机器人2的定价变化引起的，当资源提供机器人1和资源提供机器人人2的定价达到纳什均衡后，两者的定价都趋于稳定，因此资源提供机器人的收益也趋于稳定。

5结论

1）针对急场景下的微服务资源分配问题，基于Stackelberg博弈多主多从的策略模型满足系统稳定性的同时实现计算资源的有效分配。首先，将资源提供机器人和资源消费机器人抽象为多主多从的博弈模型，构建双方的策略集和收益函数，证明了所提模型存在唯一的纳什均衡。

2）利用分布式迭代搜索迭代法求解资源提供机器人的最优资源定价以及资源消费机器人的最优购买策略。仿真结果验证了本课题的模型在满足系统稳定性的同时可以得到博弈双方均衡收益。下一步将考虑分布式框架下緩存的分配，以提高群组机器人的资源利用率并提升业务能力。

参考文献（References）：

[1]关向瑞.边缘计算中基于定价的协作计算卸载与资源分配方案研究[D].兰州：兰州理工大学，2021.GUAN Xiangrui.Research on pricing-based collaborative computing offloading and resource allocation scheme for edge computing[D].Lanzhou：Lanzhou University of Technology，2021.

[2]王天然.机器人技术的发展[J].机器人，2017，39（4）：385-386.WANG Tianran.Development of robot technology[J].Robot，2017，39（4）：385-386.

[3]孙弋，张笑笑.结合退火优化和遗传重采样的RBPF算法[J].西安科技大学学报，2020，40（2）：349-355.SUN Yi，ZHANG Xiaoxiao.RBPF algorithm based on annealing optimizationand genetic resampling[J].Journal of Xian University of Science and Technology，2020，40（2）：349-355.

[4]张松.基于云计算的服务机器人系统设计与实现[D].西安：西安科技大学，2020.ZHANG Song.Design and implementation of service robot system based on cloud computing[D].Xian：Xian University of Science and Technology.2020.

[5]FAN Y L，HUANG B，JIANG Z S.Overview on collaboration and control of swarm robotics[C]//Proceedings of the 2019 International Conference on Robotics.Shanghai，China，Sep.20-22，2019：488-492.

[6]吳正.多机器人救援系统研究[D].上海：上海应用技术大学，2020.WU Zheng.Research on multi-robot rescue system[D].Shanghai：Shanghai Institute of Technology，2020.

[7]林思梦.基于粒子群算法的灾后救援多机器人任务分配[D].徐州：中国矿业大学，2020.LIN Simeng.Multi-robot task allocation for rescue after disaster based on particle swarm optimization algorithm[D].Xuzhou：China University of Mining and Technology，2020.

[8]HAMDY N，ELSAYED A，ELHANGGAR N，et al.Resource allocation strategies in cloud computing：overview[J].International Journal of Computer Applications，2017，177（4）：18-22.

[9]CHEN X.Decentralized computation offloading game for mobile cloud computing[J].IEEE Transactions on Parallel and Distributed Systems：A Publication of the IEEE Computer Society，2015，26（4）：974-983.

[10]MOHAMMADY T H，HAJ S J H，SEYYED J H，et al.A new resource allocation method in fog computing via non-cooperative game theory[J].Journal of Intelligent & Fuzzy Systems，2021，41（2）：3921-3932.

[11]RIAHI S，RIAHI A.Application of game theory to optimize wireless system resource allocation[J].International Journal of Online and Biomedical Engineering（iJOE），2018，14（12）：4-25.

[12]田春生.蜂窝网络中D2D通信的资源分配关键技术研究[D].长春：吉林大学，2020.TIAN Chunsheng.Research on key technology of resource allocation for device-to-device communications underlaying cellular networks[D].Changchun：Jilin University.2020.

[13]孙弋，许志杰.云机器人系统的计算卸载策略研究[J].西安理工大学学报，2021，37（4）：562-569.SUN Yi，XU Zhijie.Research on computing offloading strategy of cloud robot system[J].Journal of Xian University of Technology，2021，37（4）：562-569.

[14]CHOI Y，LIM Y.Optimization approach for resource allocation on cloud computing for IoT[J].International Journal of Distributed Sensor Networks，2016，2016（3）：3479247（1-6）.

[15]SUN W J，ZHANG H X，WANG L Y，et al. Profit maximization task offloading mechanism with D2D collaboration in MEC networks[C]//2019 11th International Conference on Wireless Communications and Signal Processing（WCSP）.Xian，China，Oct.23-25，2019：1-6.

[16]YANG L C，ZHANG H L，LI X，et al.A distributed computation offloading strategy in small-cell networks integrated with mobile edge computing[J].IEEE/ACM Transactions on Networking，2018，26（6）：2762-2773.

[17]WANG T W，SUN Q B.Stackelberg game based computation offloading and resource allocation in mobile edge computing[C]//2020 International Conference on Space-Air-Ground Computing（SAGC）.Beijing，China，Dec.4-6，2020：1-6.

[18]YANG C C，YAO Y，CHEN Z Y，et al.Analysis on cache-enabled wireless heterogeneous networks[J].IEEE Transactions on Wireless Communicateons，2016，15（1）：131-145.

[19]鐘楠.基于局部内容流行度的边缘协作缓存策略研究[D].桂林：桂林电子科技大学，2021.ZHOU Nan.Research on edge cooperative cache strategy based on local content popularity[D].Guilin：Guilin University of Electronic Technology，2021.

[20]WANG Y，MENG S，CHEN Y C，et al.Multi-leader multi-follower stackelberg game based dynamic resource allocation for mobile cloud computing environment[J].Wireless Personal Communications，2017，93（2）：1-20.

[21]TRAN T D，LONG B L.Resource allocation for multi-tenant network slicing：a multi-leader multi-follower stackelberg game approach[J].IEEE Transactions on Vehicular Technology，2020，69（8）：8886-8899.

[22]梁子林.基于博弈论的非正交多址接入网络资源优化研究[D].北京：北京化工大学，2019.LIANG Zilin.Resource optimization of non-orthogonal multiple access network based on game theory[D].Beijing：Beijing University of Chemical Technology，2019.

[23]WANG K D，DING Z G，SO D K C，et al.Stackelberg game of energy consumption and latency in MEC systems with NOMA[J].IEEE Transactionson Communications，2021，69（4）：2191-2206.