孫弋　宋冬冬

摘要：為解決應急場景下群組機器人系統(tǒng)穩(wěn)定分配微服務資源，提升群組機器人的業(yè)務能力，采用Stackelberg博弈的模型。模型將資源提供機器人與資源消費機器人的供需關系抽象為多主多從的博弈問題，尋求在微服務資源分配時系統(tǒng)穩(wěn)定的同時各方可獲得的最大收益。在此基礎構(gòu)建了資源提供機器人和資源消費機器人的收益函數(shù)，并證明了在所提模型中給定一組資源提供機器人的微服務資源的定價時，資源消費機器人之間存在唯一的Nash均衡點。最后，利用了分布式迭代搜索算法，求解博弈的最終需求策略。結(jié)果表明：在應急場景下，本模型所構(gòu)造的收益函數(shù)在滿足系統(tǒng)穩(wěn)定性的同時可使博弈雙方獲得最大收益，同時可得出資源提供機器人的均衡定價，實現(xiàn)微服務資源的有效分配。博弈模型構(gòu)建過程符合現(xiàn)實邏輯、穩(wěn)定性好，對未知場景中群組機器人資源分配具有一定參考價值。

關鍵詞：群組機器人;系統(tǒng)穩(wěn)定性;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引言

移動網(wǎng)絡和物聯(lián)網(wǎng)技術(shù)發(fā)展迅猛，大量終端設備被用于各個領域，智能終端設備迎來快速增[1]。機器人因其應用的廣泛性 [2]、可以完成重復的、枯燥的、危險性高的工作而日漸成為社會發(fā)展應用的趨勢 [3]。面對更加復雜的場景，單機器人的計算能力有限[4]，且不具備通信組網(wǎng)的能力，難以高效、高質(zhì)量地完成特定情況下的任務。群組機器人主要研究如何設計大量簡單的機器人通過局部交互協(xié)作，以群體的形式完成一些復雜的任務，或者模擬并實現(xiàn)一些預期的自組織行為[5]，而該類任務通常是單個機器人無法完成的。應急場景因?qū)嶋H情況的多樣性、突發(fā)性以及環(huán)境的復雜性而十分棘手，因此，將群組機器人應用于應急場景是目前機器人研究的一個熱點方向[6-7]。

綜上，本課題提出在應急場景下采用群組機器人快速建立應急救援系統(tǒng)的模型，本模型主要針對應急情況發(fā)生后，現(xiàn)場環(huán)境信息不完整而難以施救的情況。利用群組機器人搭建一個應急救援支撐系統(tǒng)可為后續(xù)救援人員進入降低人身風險、提高救援保障能力和救援效率。應急場景下，系統(tǒng)與外界隔離，其主要計算能力和資源都集中到部分機器人上，并且有限，系統(tǒng)資源的合理分配可提高救援效率、降低災害損失、提升救援服務質(zhì)量。為了保障應救援系統(tǒng)的穩(wěn)定性，群組機器人的組織形式采用中心式與分布式結(jié)合的網(wǎng)絡結(jié)構(gòu)，其中有多個中心節(jié)點和多個邊緣節(jié)點，形成多云-多邊體系。

云計算中的資源分配策略定義為保證物理或虛擬資源正確分配給云用戶的機制[8]。在應急救援系統(tǒng)模型運行的初期，能夠?qū)崿F(xiàn)資源的分配是首先要考慮的，故本課題研究的重點是實現(xiàn)應急場景下群組機器人微服務資源的有效分配。博弈論是一個可以分析多個具有獨立自主決策能力個體之間交互的工具，個體按照自己的利益做出決策，并設計了激勵兼容的機制，這樣個體就沒有單方面偏離的動機[9]，被廣泛用于解決資源分配和優(yōu)化問題[10-12]。群組機器人中，每個機器人都具有自主決策能力，可根據(jù)自身需求執(zhí)行相關策略。為了使自身利益最大化，群組機器人中各決策方均存在博弈?；诖耍菊n題提出在應急場景下，群組機器人通過博弈論分配微服務資源的模型。

文獻[13]利用Stackelberg模型分析多個機器人終端競爭同一邊緣云服務器中相同類型資源，利用一種結(jié)合漢明距離的動態(tài)規(guī)劃算法求解，實驗結(jié)果表明所提算法在縮短平均任務完成時間的同時，降低了云機器人系統(tǒng)的局部計算能耗，該模型僅討論了機器人終端的效用，未討論云端的效用。文獻[14]提出了一種使用組合拍賣方法在云系統(tǒng)的資源分配中滿足QoS標準的方法。考慮了有效資源分配的緊迫性，并確定了超過任務期限的概率及其期望值。強調(diào)了該方法具有較高的任務完成成功率，但未考慮用戶的收益。文獻[15]借助設備到設備（D2D）通信技術(shù)研究了多路訪問邊緣計算網(wǎng)絡的最佳卸載機制，提出了一種基于 Stackelberg博弈的方法來實現(xiàn)價格和資源的均衡，并利用二分匹配的最優(yōu)任務分配方法求解，仿真結(jié)果表明，所提方案可以獲得更高的計算利潤，但缺乏對用戶收益的討論。文獻[16]研究了小型蜂窩網(wǎng)絡中多設備多服務器系統(tǒng)的分布式計算卸載策略，目的是聯(lián)合優(yōu)化每個移動設備的能量消耗和延遲，并將開銷最小化問題制定為策略博弈，證明了其納什均衡的存在，仿真結(jié)果表明，所提算法可以有效的最小化每個移動設備的開銷。文獻[17]將移動邊緣中卸載決策者和資源分配者之間的交互建模為Stackelberg博弈，構(gòu)建了博弈對象和收益函數(shù)，并證明了博弈均衡的存在，設計了一種有效計算均衡的算法，仿真結(jié)果表明，所提算法在考慮聯(lián)合管理計算卸載和資源分配的基礎上，可以有效的最小化各方成本。但未具體討論收益問題。

上述文獻均在一定條件下討論了博弈參與者的收益，但對博弈各方均衡收益問題討論不足;其次，對資源分配時的重點聚焦時延與能耗上，適用于追求效率和節(jié)能的場景中。綜上，為了考慮微服務資源有限場景中系統(tǒng)穩(wěn)定性的同時，兼顧資源提供機器人和資源消費機器人各自最大收益，即均衡收益。①引入服務流行度和偏好內(nèi)容流行度構(gòu)建Stackelberg博弈模型，求解資源提供機器人和資源消費機器人追求各自目標時的納什均衡策略;②通過分析所提的博弈模型，構(gòu)造了參與者的收益函數(shù)。并證明了在資源提供機器人的微服務資源定價確定的情況下，資源消費機器人之間存在非合作博弈Nash均衡點;③通過拉格朗日乘子法求解出資源消費機器人的最優(yōu)購買微服務資源量，再逆向地利用分布迭代求出資源提供機器人的最優(yōu)定價，確保資源提供機器人和資源消費機器人的收益達到了均衡的最佳收益。

1系統(tǒng)模型

1.1網(wǎng)絡模型

如圖1所示，應急場景下群組機器人系統(tǒng)包含N個資源提供機器人（1，2，…，N），M個資源消費機器人（1，2，…，M）。在本研究中，資源消費機器人從資源提供機器人處購買微服務資源，假定資源消費機器人的微服務資源需求量與資源提供機器人提供的微服務資源相對應，并且資源消費機器人的資源由自身和資源提供機器人共同提供。作為服務資源的提供方，資源提供機器人追求最大化收益，它們之間形成競爭。

系統(tǒng)模型如圖1所示，具體過程為

1）資源提供機器人擁有一定量的微服務資源，為了合理的利用資源并提高業(yè)務效率，將微服務資源按一定價格出售給資源消費機器人。

2）資源消費機器人根據(jù)資源提供機器人的定價和自身需求購買微服務資源。

由于機器人電能和資源均有限，資源提供機器人會根據(jù)資源消費機器人的需求和自身的服務能力來動態(tài)的調(diào)整微服務資源的定價，而資源消費機器人會根據(jù)資源提供機器人的定價，調(diào)整購買微服務資源的數(shù)量，兩者相互制約，尋求各自的最大化。

1.2資源流行度

在系統(tǒng)模型中，考慮實際情況，資源提供機器人的微服務資源往往有著不同的被購買頻率，即它們有著不同的流行度，則資源消費機器人購買微服務資源的請求概率為Qc，其服從Zipf分布[18]

1.3偏好內(nèi)容流行度

在實際情況中，不同的資源消費機器人購買微服務資源的請求存在一定的差異，且資源消費機器人的偏好不盡相同，因此，資源消費機器人請求購買微服務資源的概率也有差異，受文獻[19]啟示，本課題利用式（2）表示資源消費機器人的興趣偏好

2問題構(gòu)建

一個博弈模型通常由3個基本元素構(gòu)成：一組參與者（a set of players）、每個參與者的動作（the action of each player）、一組效用函數(shù)（a set of utility functions）[20]。

博弈模型的決策是符合主從關系的Stackelberg博弈，參與者集合分為領導者和跟隨者，其中領導者處于決策的領導地位，跟隨者根據(jù)領導者的決策而做出自己的決策。每個決策個體都有自身的策略集合和對應的收益函數(shù)。Stackelberg博弈的過程表示為以下3個步驟：①領導者首先做出當前情況下的最優(yōu)決策;②跟隨者考慮領導者的策略，結(jié)合自身收益做出決策;③領導者再考慮跟隨者的策略和自身收益函數(shù)調(diào)整其決策。整個博弈過程是動態(tài)的，當雙方收益不再增加，沒有決策參與者愿意改變策略時，博弈過程結(jié)束。

2.1博弈構(gòu)成

2.2博弈群組構(gòu)建

2.3Stackelberg純策略納什均衡

所提模型由N個資源提供機器人和M個資源消費機器人構(gòu)成，在應急場景下，整個系統(tǒng)與外界隔離，系統(tǒng)的資源有限。當資源提供機器人設定微服務資源價格后，資源消費機器人為了使用微服務資源，它們之間形成非合作博弈。當資源提供機器人設定的微服務資源價格偏高時，資源消費機器人選擇不購買資源;當資源提供機器人設定的微服務資源價格偏低時，自身無法獲得利潤，因此資源提供機器人和資源消費機器人之間形成主從博弈的Stackelberg博弈。博弈是為了求出Nash均衡點，進而得到資源提供機器人和資源消費機器人的最佳決策，最大化雙方的收益。

Stackelberg博弈通常通過分析完全信息Nash均衡點來求解：在微服務資源分配和定價策略中，沒有參與者有動機單方面改變策略，以獲得更好效用，而不損害其他參與者的效用[21]。

在本模型中，資源提供機器人之間共享資源消費機器人的微服務資源請求，每個資源提供機器人決定微服務資源的定價以最大化自身收益。

3博弈求解

Stackelberg博弈通常使用逆向歸納法求解，上述章節(jié)已經(jīng)證明了本課題所提模型存在Nash均衡點。基于此，先求解資源消費機器人獲得的最優(yōu)微服務資源數(shù)量，再利用求得的最優(yōu)微服務資源計算出資源消費機器人的最優(yōu)定價。

3.1資源消費機器人最優(yōu)資源需求

應急場景中，系統(tǒng)與外界隔離，資源均有限，因此在實際求解中，需要考慮資源消費機器人的約束。資源消費機器人的最優(yōu)購買數(shù)量x可表示為

3.2資源提供機器人的最優(yōu)資源定價

求得資源消費機器人的最優(yōu)購買需求后，利用分布式迭代法求解資源提供機器人的最優(yōu)定價，算法如下。

4仿真與分析

圖2給出資源提供機器人1與資源提供機器人2的微服務資源定價關系，2條曲線上的點分別表示當前資源提供機器人對另一資源提供機器人的最佳定價策略。由圖可知，（3.1，3.5）是雙方定價的平衡點，也是博弈均衡點，在該點處資源提供機器人1與資源提供機器人2都沒有意愿改變定價策略使自己的收益降低，為雙方收益最大化的最佳定價組合。

圖4給出了在本課題的模型源消費機器人的收益隨迭代次數(shù)的變化圖。可以看出資源消費機器人的收益在納什均衡點之前有波動，這是因為資源消費機器人1和資源消費機器人2的定價變化引起的，通資源消費機器1和資源消費機器2的定價達到納什均衡后，兩者的定價都趨于穩(wěn)定，因此資源消費機器人的收益也趨于穩(wěn)定。

圖5給出了在本課題的模型下資源提供機器人的收益和迭代次數(shù)的關系?？梢钥闯鲑Y源提供機器人的收益在納什均衡點之前有波動，這是因為資源提供機器人1和通資源提供機器人2的定價變化引起的，當資源提供機器人1和資源提供機器人人2的定價達到納什均衡后，兩者的定價都趨于穩(wěn)定，因此資源提供機器人的收益也趨于穩(wěn)定。

5結(jié)論

1）針對急場景下的微服務資源分配問題，基于Stackelberg博弈多主多從的策略模型滿足系統(tǒng)穩(wěn)定性的同時實現(xiàn)計算資源的有效分配。首先，將資源提供機器人和資源消費機器人抽象為多主多從的博弈模型，構(gòu)建雙方的策略集和收益函數(shù)，證明了所提模型存在唯一的納什均衡。

2）利用分布式迭代搜索迭代法求解資源提供機器人的最優(yōu)資源定價以及資源消費機器人的最優(yōu)購買策略。仿真結(jié)果驗證了本課題的模型在滿足系統(tǒng)穩(wěn)定性的同時可以得到博弈雙方均衡收益。下一步將考慮分布式框架下緩存的分配，以提高群組機器人的資源利用率并提升業(yè)務能力。

參考文獻（References）：

[1]關向瑞.邊緣計算中基于定價的協(xié)作計算卸載與資源分配方案研究[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]王天然.機器人技術(shù)的發(fā)展[J].機器人，2017，39（4）：385-386.WANG Tianran.Development of robot technology[J].Robot，2017，39（4）：385-386.

[3]孫弋，張笑笑.結(jié)合退火優(yōu)化和遺傳重采樣的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]張松.基于云計算的服務機器人系統(tǒng)設計與實現(xiàn)[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]吳正.多機器人救援系統(tǒng)研究[D].上海：上海應用技術(shù)大學，2020.WU Zheng.Research on multi-robot rescue system[D].Shanghai：Shanghai Institute of Technology，2020.

[7]林思夢.基于粒子群算法的災后救援多機器人任務分配[D].徐州：中國礦業(yè)大學，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]田春生.蜂窩網(wǎng)絡中D2D通信的資源分配關鍵技術(shù)研究[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]孫弋，許志杰.云機器人系統(tǒng)的計算卸載策略研究[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]鐘楠.基于局部內(nèi)容流行度的邊緣協(xié)作緩存策略研究[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]梁子林.基于博弈論的非正交多址接入網(wǎng)絡資源優(yōu)化研究[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.