群組機(jī)器人系統(tǒng)資源分配策略研究

孫 弋，宋冬冬

(1.西安科技大學(xué) 通信與信息工程學(xué)院，陜西 西安 710054;2.西安市網(wǎng)絡(luò)融合通信重點實驗室，陜西 西安 710054)

0 引 言

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

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

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

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

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

1 系統(tǒng)模型

1.1 網(wǎng)絡(luò)模型

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

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

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

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

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

1.2 資源流行度

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

(1)

式中α為微服務(wù)資源的流行程度。當(dāng)α越大，則微服務(wù)資源越受歡迎；當(dāng)α越小，則微服務(wù)資源越不受歡迎。

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

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

(2)

將資源流行度和基于資源消費(fèi)機(jī)器人偏好的流行度進(jìn)行加權(quán)構(gòu)建成模型中資源消費(fèi)機(jī)器人m對微服務(wù)資源的購買概率，見式(3)

Q=k1Qc+K2Qu

(3)

式中k1和k2分別為資源流行度和資源消費(fèi)機(jī)器人偏好的微服務(wù)資源流行度的系數(shù)。如果k1>k2，則說明資源提供機(jī)器人對流行的微服務(wù)資源更感興趣；否則，則說明資源消費(fèi)機(jī)器人購買微服務(wù)資源時追求自己的興趣。因此，Q可以表示在模型中資源消費(fèi)機(jī)器人對流行的微服務(wù)資源的潛在購買興趣，這使得模型更符合現(xiàn)實邏輯。

2 問題構(gòu)建

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

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

2.1 博弈構(gòu)成

利用Stackelberg博弈建模群組機(jī)器人系統(tǒng)的微服務(wù)資源分配問題，其基本構(gòu)成如下

跟隨者：

跟隨者是M個資源消費(fèi)機(jī)器人(1,2,…,M)。資源消費(fèi)機(jī)器人根據(jù)資源提供機(jī)器人的微服務(wù)資源定價和自身需求，調(diào)整微服務(wù)資源購買策略，最大化收益。

1)跟隨者的策略集。資源消費(fèi)機(jī)器人的策略是其在資源提供機(jī)器人處購買的微服務(wù)資源的數(shù)量xn,m，多個資源提供機(jī)器人可共同滿足其需求。

2)跟隨者的收益函數(shù)。資源消費(fèi)機(jī)器人的收益函數(shù)用Um表示。

資源消費(fèi)機(jī)器人的收益Um表示為獲得微服務(wù)資源的收益與購買微服務(wù)資源的支出之差。

對于資源消費(fèi)機(jī)器人m，m∈(1,2,…,M)，式(1)表示與微服務(wù)資源xn,m相關(guān)的收益。

(4)

式中β是與收益相關(guān)的常數(shù)。

微服務(wù)資源的價格應(yīng)該符合市場波動，即資源消費(fèi)機(jī)器人的訪問數(shù)目越多，微服務(wù)資源的價格應(yīng)該越高，這個關(guān)系用mn/Mn表示，為資源提供機(jī)器人中當(dāng)前存在的資源消費(fèi)機(jī)器人除以其最大服務(wù)能力。資源消費(fèi)機(jī)器人購買微服務(wù)資源的成本見式(5)，資源消費(fèi)機(jī)器人的純收入見式(6)

(5)

(6)

領(lǐng)導(dǎo)者：

領(lǐng)導(dǎo)者是N個資源提供機(jī)器人(1，2，…，N)。在應(yīng)急場景中，資源提供機(jī)器人可以生產(chǎn)一定量的微服務(wù)資源，且處于領(lǐng)導(dǎo)地位，可以決定微服務(wù)資源的定價并影響跟隨者的決策。

1)領(lǐng)導(dǎo)者的策略集。資源提供機(jī)器人的策略是制定微服務(wù)資源的價格P=(P1，P2，…，Pn)。

2)領(lǐng)導(dǎo)者的收益函數(shù)。資源提供機(jī)器人的收益函數(shù)用Un表示。

資源提供機(jī)器人的收益是定價Pn計算帶來的收益與計算的成本Cn之差。這里將成本Cn看作CPU生成微服務(wù)資源所需時間與能耗的函數(shù)。假定Tn是CPU生成單位數(shù)據(jù)所需的周期數(shù)，F(xiàn)n是單位時間CPU周期數(shù)，即計算能力，Hn是單位CPU運(yùn)算周期所消耗的熱量，即Cn的表達(dá)式見式(7)

(7)

式中λT和λH分別為時間、熱量系數(shù)，則資源提供機(jī)器人的收益函數(shù)為

(8)

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

在本模型的微服務(wù)資源分配系統(tǒng)中，資源消費(fèi)機(jī)器人根據(jù)自身需求從資源提供機(jī)器人處購買微服務(wù)資源，在支付微服務(wù)資源價格后獲得所需微服務(wù)資源。同時，資源消機(jī)器人通過微服務(wù)資源的價格來獲得收益，兩方參與者都試圖最大化自身收益。

對于資源提供機(jī)器人，其微服務(wù)資源分配問題可對應(yīng)為其收益的最大值，即

maxUn(P,x)

(9)

式中 微服務(wù)資源定價P為非負(fù)值；x為資源消費(fèi)機(jī)器人購買微服務(wù)資源的數(shù)量。

對于資源消費(fèi)機(jī)器人，其購買微服務(wù)資源問題可對應(yīng)為收益的最大值，將式(4)與式(5)帶入式(6)，得到資源消費(fèi)機(jī)器人的凈收益解析式為

(10)

則對應(yīng)的收益最大值問題為

maxUm(P,x)

(11)

從上述模型可得，資源提供機(jī)器人的最終目的是求解其在式(9)中的最大值。同時，資源消費(fèi)機(jī)器人作為跟隨者，其最終目的是求解式(11)中的最大值，并在資源提供機(jī)器人做出決策后再做出自己的決策。

2.3 Stackelberg純策略納什均衡

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

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

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

假定資源提供機(jī)器人已做公布微服務(wù)資源定價P，在該定價下資源消費(fèi)機(jī)器人之間是非合作博弈關(guān)系，收益函數(shù)為Um(P,xn,m,x-n,m)，其中m∈(1,2,…,M)，則資源消費(fèi)機(jī)器人的微服務(wù)資源的購買策略間存在納什均衡點。

由勞威爾不動點定理可知：博弈的參與方是有限個；每個博弈參與方其策略空間在歐幾里得空間上是有解閉集，同時，收益函數(shù)在x上是連續(xù)的。接下來證明資源消費(fèi)機(jī)器人收益函數(shù)x在其策略空間Um上是凹函數(shù)。

對資源消費(fèi)機(jī)器人收益函數(shù)求一階偏導(dǎo)數(shù)得

(12)

由公式(12)可知，資源消費(fèi)機(jī)器人的一階導(dǎo)數(shù)是關(guān)于微服務(wù)資源xn,m和定價Pn的二元函數(shù)。

二階偏導(dǎo)數(shù)得

(13)

由式可知(13)，二階偏導(dǎo)數(shù)為負(fù)，收益函數(shù)在整個策略空間上為凹函數(shù)。這里ηn是趨于0的正數(shù)，可忽略該項，即一階導(dǎo)存在，且為正，即該博弈下存在Nash均衡點[22]。

3 博弈求解

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

3.1 資源消費(fèi)機(jī)器人最優(yōu)資源需求

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

(14)

采用拉格朗日乘數(shù)法來求解表達(dá)式(14)。構(gòu)造拉格朗日函數(shù)

Lm(x,α,ε,γ)=Um+αxn,m+ε(1-xn,m)

(15)

式中α，ε，γ是拉格朗日乘子。

通過KKT(karush-kuhn-tucher)[23]條件來得到資源消費(fèi)機(jī)器人的最優(yōu)購買策略。條件如下

(16)

求解式(16)，得到資源消費(fèi)機(jī)器人的最優(yōu)購買需求，見式(17)

(17)

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

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

1)輸入x及其它初始化參數(shù)。

2)初始化P=(P1,P2,…,Pn)，令P1=P2=…=Pn=0。

3)求解式(8)關(guān)于的偏導(dǎo)數(shù)

(18)

4)式(18)不是解析解，令(18)等于0，反解出P，見式(19)。

(19)

5)由博弈論可知，資源提供機(jī)器人之間的定價會相互影響，即其他資源提供機(jī)器人會在某個資源提供機(jī)器人改變其資源定價后變更自己的服務(wù)定價。所以，需要用迭代方式來求解資源提供機(jī)器人的服務(wù)定價。迭代公式如下

(20)

4 仿真與分析

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

圖2 2個資源提供機(jī)器人定價關(guān)系Fig.2 Robot pricing relationship provided by two resources

當(dāng)修改初始定價P1=P2=5后，再次觀察資源提供機(jī)器人1和資源提供機(jī)器人2的定價關(guān)系圖，從圖3可以看出，2個資源提供機(jī)器人的定價也都在(3.1，3.5)擺動，驗證了所提算法的正確性。

圖3 初始值P=5時2個資源提供機(jī)器人定價關(guān)系Fig.3 Robot pricing relationship provided by two resources as P=5

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

圖4 資源消費(fèi)機(jī)器人的收益隨迭代次數(shù)變化Fig.4 Variation of revenue of resource consumption robots with the number of iterations

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

圖5 資源提供機(jī)器人的收益隨迭代次數(shù)變化Fig.5 Variation of revenue of the resource providing robot with the number of iterations

5 結(jié) 論

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

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