孫 弋， 許志杰

(西安科技大學(xué) 通信與信息工程學(xué)院， 陜西 西安 710054)

近年來伴隨著嵌入式系統(tǒng)性能的提升、傳感器技術(shù)的蓬勃發(fā)展[1]以及移動(dòng)數(shù)字網(wǎng)絡(luò)技術(shù)的快速迭代，全球范圍內(nèi)，應(yīng)用機(jī)器人市場規(guī)模增長明顯[2]。不同于執(zhí)行特定程序的物理設(shè)備，機(jī)器人具有高度的自主決策能力，對不同環(huán)境和場景適應(yīng)性強(qiáng)，且機(jī)器人群組之間的協(xié)作愈發(fā)成熟[3]。如何實(shí)現(xiàn)機(jī)器人集群的大規(guī)模應(yīng)用以及使機(jī)器人在有限功耗的限制下，具備強(qiáng)大的計(jì)算能力和低廉的部署成本成為亟需解決的熱點(diǎn)需求。基于網(wǎng)絡(luò)技術(shù)將機(jī)器人本體需完成的數(shù)據(jù)分析與處理、行為決策與規(guī)劃、機(jī)器人群組協(xié)同等復(fù)雜的計(jì)算任務(wù)卸載到云端執(zhí)行，通過數(shù)據(jù)共享，憑借云端專有的軟硬件資源代替機(jī)器人執(zhí)行更加復(fù)雜的計(jì)算任務(wù)、存儲(chǔ)更大規(guī)模數(shù)據(jù)、為機(jī)器人提供服務(wù)的系統(tǒng)稱為云機(jī)器人系統(tǒng)架構(gòu)。郭宇[1]利用連通支配集對云機(jī)器人底層網(wǎng)絡(luò)建模，并結(jié)合能耗敏感模型實(shí)現(xiàn)對整個(gè)機(jī)器人自組織網(wǎng)絡(luò)中的能量和時(shí)間延遲進(jìn)行分析，并在該模型下設(shè)計(jì)了基于遺傳算法的計(jì)算卸載策略。博弈論是研究分布式多智能體系統(tǒng)中決策者之間相互作用關(guān)系的數(shù)學(xué)工具，而云機(jī)器人系統(tǒng)作為典型的分布式系統(tǒng)，其服務(wù)的提供者與使用者，及使用者與使用者之間的博弈時(shí)刻存在，其中邊緣云擁有對計(jì)算資源的定價(jià)權(quán)，是博弈的領(lǐng)導(dǎo)者，而云機(jī)器人依據(jù)自身情況及所需資源價(jià)格做出卸載決策，是博弈的跟隨者。Xu等[4]對云機(jī)器人系統(tǒng)中的任務(wù)進(jìn)行分割與建模，基于多邊緣網(wǎng)絡(luò)中云機(jī)器人計(jì)算卸載問題設(shè)計(jì)了改進(jìn)的博弈論算法，提高機(jī)器人網(wǎng)絡(luò)服務(wù)質(zhì)量和用戶體驗(yàn)。尤斐然[5]應(yīng)用博弈論設(shè)計(jì)資源優(yōu)化分配的策略，分析一對多、多對對、多層聯(lián)合博弈的模型下的資源分配效率。上述文獻(xiàn)從博弈論的角度對資源分配與能耗進(jìn)行分析，但未討論博弈各方?jīng)Q策時(shí)的相互影響。針對上述不足，本文將多個(gè)機(jī)器人終端競爭同一邊緣云服務(wù)器中相同類型資源或服務(wù)的行為建模為Stackelberg博弈模型，基于逆向歸納法求解在多階段博弈過程中邊緣云與機(jī)器人終端的決策問題，求得云機(jī)器人系統(tǒng)博弈中雙方策略最優(yōu)的Nash均衡解，實(shí)現(xiàn)雙方效用函數(shù)的最大化。

1 相關(guān)研究

1.1 云機(jī)器人系統(tǒng)架構(gòu)

云機(jī)器人系統(tǒng)是在傳統(tǒng)的分布式網(wǎng)絡(luò)機(jī)器人系統(tǒng)之上，結(jié)合云計(jì)算[6]服務(wù)發(fā)展而來的一種新興發(fā)展方向。這一概念在2010年由Kuffner教授[7]首次提出，旨在利用互聯(lián)網(wǎng)大規(guī)模并行計(jì)算和近乎無限的分布式存儲(chǔ)能力為機(jī)器人設(shè)計(jì)統(tǒng)一的服務(wù)交互模型，擴(kuò)展其計(jì)算能力以及增強(qiáng)其服務(wù)能力。根據(jù)服務(wù)提供方式的不同，將該模型分為面向服務(wù)(SOA)的平臺(tái)架構(gòu)和提供機(jī)器人即服務(wù)(RaaS)的平臺(tái)架構(gòu)[8]。Arumugam等[9]基于平臺(tái)即服務(wù)的思想，設(shè)計(jì)DAvinCi的云機(jī)器人計(jì)算框架，并采用Map/Reduce的方式實(shí)現(xiàn)了機(jī)器人同步定位與地圖構(gòu)建算法的云服務(wù)平臺(tái)。Quintas等[10]提出了面向服務(wù)的機(jī)器人系統(tǒng)，其中機(jī)器人和智能空間共享知識。Du等[11]基于機(jī)器人即服務(wù)提出了機(jī)器人云中心(robot cloud center)的框架，其結(jié)合了SOA架構(gòu)和云計(jì)算模型，使任務(wù)以最大效率，耗費(fèi)最少資源完成。結(jié)合相關(guān)研究背景及云計(jì)算的特點(diǎn)，本文擬將機(jī)器人任務(wù)封裝為眾多獨(dú)立微服務(wù)，構(gòu)建RaaS的云機(jī)器人服務(wù)管理系統(tǒng)，機(jī)器人通過端到云的網(wǎng)絡(luò)向云端請求所需計(jì)算服務(wù)。計(jì)算卸載策略是云機(jī)器人進(jìn)行計(jì)算卸載的關(guān)鍵，其決定任務(wù)是否進(jìn)行卸載以及卸載數(shù)量。

1.2 計(jì)算卸載

計(jì)算卸載[12-13]是解決邊緣計(jì)算中用戶終端設(shè)備在計(jì)算和存儲(chǔ)資源等方面的不足，是云機(jī)器人架構(gòu)最重要的特點(diǎn)之一。用戶終端將對時(shí)間延遲不敏感的計(jì)算密集型任務(wù)遷移到專用服務(wù)器上運(yùn)算，待計(jì)算完成后接收計(jì)算結(jié)果的過程稱為計(jì)算卸載，其流程見圖1。

圖1 計(jì)算卸載流程圖Fig.1 Calculation offloading flow chart

計(jì)算卸載分二進(jìn)制卸載和部分卸載兩種方式。二進(jìn)制卸載方式指計(jì)算任務(wù)不可分割，其程序和數(shù)據(jù)作為統(tǒng)一整體卸載到邊緣云執(zhí)行，由此其對通信網(wǎng)絡(luò)的傳輸能力、網(wǎng)絡(luò)延遲提出了較高的要求，服務(wù)作為整體卸載到邊緣云端，降低了云端資源調(diào)度策略的設(shè)計(jì)難度，但使請求服務(wù)調(diào)度失效時(shí)的異常處理難度增加。Chen等[14]研究在任務(wù)執(zhí)行時(shí)延和能耗約束下，多參與者通過非合作博弈達(dá)到最優(yōu)計(jì)算策略的二進(jìn)制卸載問題。Ma等[15]研究無線網(wǎng)絡(luò)組網(wǎng)環(huán)境中多用戶終端的計(jì)算卸載問題，結(jié)合博弈論將所有用戶的計(jì)算任務(wù)，無線頻帶分配和計(jì)算資源進(jìn)行建模，獲得使任務(wù)執(zhí)行成本最小的最優(yōu)策略。Chen等[16]也是利用非合作博弈模型分析多用戶終端之間卸載策略的相互影響，基于降低任務(wù)執(zhí)行總代價(jià)和時(shí)間延遲，獲得最優(yōu)的計(jì)算卸載策略使通信與計(jì)算資源分配最優(yōu)。部分卸載方式指將計(jì)算任務(wù)分割為多個(gè)子任務(wù)，一部分在本地執(zhí)行，一部分在邊緣云執(zhí)行，既減少計(jì)算任務(wù)傳輸數(shù)據(jù)總量，又提高子任務(wù)執(zhí)行的并行性，充分發(fā)揮本地和邊緣側(cè)協(xié)同計(jì)算的優(yōu)勢，提高任務(wù)執(zhí)行的效率，同時(shí)需為到達(dá)邊緣側(cè)的子任務(wù)設(shè)計(jì)任務(wù)調(diào)度機(jī)制，滿足依賴關(guān)系的子任務(wù)串行執(zhí)行，相互獨(dú)立的子任務(wù)并行執(zhí)行。Dai等[17]基于多邊緣云服務(wù)器之間的負(fù)載均衡問題，在滿足任務(wù)執(zhí)行時(shí)間和能耗的條件下設(shè)計(jì)使系統(tǒng)整體耗能最小的最優(yōu)卸載策略。Jie等[18]將移動(dòng)邊緣計(jì)算環(huán)境中用戶之間的計(jì)算卸載策略抽象為符合主從關(guān)系的Stackelberg博弈，為優(yōu)化任務(wù)的響應(yīng)時(shí)間和資源利用率設(shè)計(jì)了一種任務(wù)調(diào)度算法。You等[19]研究在同一網(wǎng)絡(luò)中只有單一邊緣云服務(wù)器時(shí)，多終端設(shè)備將部分任務(wù)卸載到邊緣云中執(zhí)行時(shí)所需的信道資源分配問題，優(yōu)化任務(wù)執(zhí)行所需時(shí)間。上述文獻(xiàn)均假設(shè)邊緣云服務(wù)器擁有無限的計(jì)算資源，而云機(jī)器人系統(tǒng)在現(xiàn)實(shí)的計(jì)算平臺(tái)中運(yùn)行，其次對選擇部分卸載時(shí)結(jié)合能耗和時(shí)間延遲的計(jì)算卸載系統(tǒng)研究不足。

綜上，為降低通信設(shè)備壓力，提高云端服務(wù)調(diào)度靈活性，本文在云機(jī)器人系統(tǒng)中選擇部分卸載的計(jì)算卸載策略。本文重點(diǎn)研究在同一邊緣“網(wǎng)絡(luò)”只有單個(gè)邊緣云，且邊緣云的計(jì)算資源是有限時(shí)，實(shí)現(xiàn)機(jī)器人計(jì)算任務(wù)部分卸載的策略研究。

2 計(jì)算卸載系統(tǒng)模型

云機(jī)器人系統(tǒng)中的計(jì)算卸載是典型的邊緣計(jì)算(MEC)問題，根據(jù)上述對計(jì)算卸載的介紹，結(jié)合云機(jī)器人計(jì)算任務(wù)本身的特點(diǎn)可知：1)云機(jī)器人中的部分任務(wù)只能在本地執(zhí)行，且存在云端資源競爭不足等情況，故采用動(dòng)態(tài)部分卸載的策略；2)云機(jī)器人中的計(jì)算任務(wù)可被分割，部分在本地執(zhí)行，同時(shí)其他部分被卸載至邊緣服務(wù)器執(zhí)行，根據(jù)計(jì)算卸載的影響因素決定單節(jié)點(diǎn)卸載還是多節(jié)點(diǎn)卸載。本文的博弈論算法是研究多個(gè)機(jī)器人競爭同一邊緣云服務(wù)器資源，欲將計(jì)算任務(wù)卸載到邊緣服務(wù)器中執(zhí)行以減少自身設(shè)備的計(jì)算成本。任何一個(gè)機(jī)器人的卸載決策都會(huì)影響同一邊緣“網(wǎng)絡(luò)”中其他機(jī)器人終端的計(jì)算卸載決策。在云機(jī)器人系統(tǒng)的計(jì)算卸載模型中，處于同一邊緣“網(wǎng)絡(luò)”中的節(jié)點(diǎn)大多只有一個(gè)，符合多對一的模型。下面就基于Stackelberg博弈論的計(jì)算卸載策略方法進(jìn)行論述。

2.1 系統(tǒng)網(wǎng)絡(luò)模型

一個(gè)計(jì)算卸載網(wǎng)絡(luò)由一個(gè)具備計(jì)算加速服務(wù)的邊緣云和K個(gè)機(jī)器人終端集合N={1,2,…,K}組成，單個(gè)通信AP節(jié)點(diǎn)下管理至多K個(gè)移動(dòng)機(jī)器人終端，其網(wǎng)絡(luò)模型見圖2。

圖2 系統(tǒng)網(wǎng)絡(luò)模型Fig.2 System network model

計(jì)算卸載方式為動(dòng)態(tài)部分卸載，即機(jī)器人終端任務(wù)可按功能拆分為多個(gè)大小各異的簡單任務(wù)，一部分在本地執(zhí)行，另一部分在邊緣服務(wù)器上執(zhí)行。邊緣云計(jì)算平臺(tái)與通信AP節(jié)點(diǎn)之間采用有線網(wǎng)絡(luò)，不考慮在有線傳輸過程中所產(chǎn)生的通信損耗和時(shí)間延遲，通信AP節(jié)點(diǎn)通過無線網(wǎng)絡(luò)與機(jī)器人終端進(jìn)行連接，該無線網(wǎng)絡(luò)可分配的總帶寬為B。假設(shè)每個(gè)機(jī)器人終端與通信AP節(jié)點(diǎn)之間的信道相互獨(dú)立，互不干擾，每個(gè)機(jī)器人可均勻分得的最大帶寬為B/K，且通信能力不隨該節(jié)點(diǎn)管理機(jī)器人數(shù)量增加而下降。隨著機(jī)器人終端的移動(dòng)，其與通信AP節(jié)點(diǎn)之間的信道會(huì)隨著位置發(fā)生改變，假設(shè)單次任務(wù)卸載周期內(nèi)信道環(huán)境參數(shù)保持不變，但不同卸載周期信道環(huán)境參數(shù)可能改變。

2.2 任務(wù)執(zhí)行模型

基于上述的網(wǎng)絡(luò)模型，計(jì)算任務(wù)可在本地或邊緣側(cè)執(zhí)行，首先對計(jì)算任務(wù)進(jìn)行建模。云機(jī)器人系統(tǒng)中，功能各異的機(jī)器人終端選擇適當(dāng)?shù)腃PU計(jì)算能力，編號為k的機(jī)器人終端其計(jì)算能力用每秒CPU周期數(shù)Fk衡量，單位為cycles/s，執(zhí)行任務(wù)所需計(jì)算數(shù)據(jù)總量為Rk，單位為Byte，每執(zhí)行1bit數(shù)據(jù)所需的CPU周期數(shù)為Ck，單位為cycle。計(jì)算任務(wù)卸載到邊緣側(cè)執(zhí)行的比例為xk，0≤xk≤1，故執(zhí)行卸載的數(shù)據(jù)量為xkRk，本地執(zhí)行的數(shù)據(jù)量為(1-xk)Rk。時(shí)間延遲和能量消耗是評價(jià)計(jì)算卸載策略優(yōu)劣的重要指標(biāo)，下文對任務(wù)本地執(zhí)行和任務(wù)遠(yuǎn)端執(zhí)行中的時(shí)間延遲和能量消耗計(jì)算方法進(jìn)行建模。

1) 任務(wù)本地執(zhí)行模型

任務(wù)在本地執(zhí)行計(jì)算過程中所耗費(fèi)的時(shí)間和能量即時(shí)間延遲和能耗。計(jì)算能力為Fk的機(jī)器人終端執(zhí)行數(shù)據(jù)量大小為(1-xk)Rk的計(jì)算任務(wù)所消耗的時(shí)間和能量分別為：

(1)

(2)

式中：Vk表示每CPU周期消耗能量，單位J。

2) 任務(wù)遠(yuǎn)端執(zhí)行模型

(3)

(4)

機(jī)器人終端與通信AP節(jié)點(diǎn)之間的信道帶寬為B/K，單次計(jì)算卸載周期內(nèi)信道噪聲功率不變，為σ，其本地通信設(shè)備發(fā)送功率為Pk，機(jī)器人終端與通信AP節(jié)點(diǎn)之間的信號增益為Gk，根據(jù)Shannon公式可得：

(5)

因此機(jī)器人終端k上載任務(wù)數(shù)據(jù)到邊緣云上的傳輸時(shí)間為：

(6)

數(shù)據(jù)的上載和下載處于相同信道環(huán)境中，可得數(shù)據(jù)下載速率為：

(7)

式中：PBS為通信AP節(jié)點(diǎn)的通信設(shè)備發(fā)送功率。

計(jì)算結(jié)果的數(shù)據(jù)量相較于輸入數(shù)據(jù)量明顯減少，用α表示輸出數(shù)據(jù)量與輸入數(shù)據(jù)量的比值，則反饋到機(jī)器人終端的數(shù)據(jù)量為αxkRk，因此計(jì)算結(jié)果反饋時(shí)間為：

(8)

(9)

在此系統(tǒng)中任務(wù)可在本地和邊緣側(cè)同時(shí)進(jìn)行計(jì)算，因此機(jī)器人k執(zhí)行總數(shù)據(jù)量為Rk的任務(wù)需要的時(shí)間為：

(10)

(11)

式中：TPs,k表示機(jī)器人k通信設(shè)備的發(fā)送功率。

計(jì)算結(jié)果反饋過程中所消耗能量為：

(12)

上式中TPr,k表示機(jī)器人k通信設(shè)備的接收功率。則可得機(jī)器人終端執(zhí)行計(jì)算卸載所消耗的能量為：

(13)

為對計(jì)算卸載過程中需付出的代價(jià)進(jìn)行評估，設(shè)計(jì)了由多項(xiàng)式組成的評價(jià)代價(jià)函數(shù)公式：

(14)

能耗權(quán)重因子λe和時(shí)間延遲因子λt滿足約束條件，λe+λt=1。則計(jì)算卸載過程中總的代價(jià)函數(shù)表示為：

(15)

2.3 云機(jī)器人系統(tǒng)中的Stackelberg博弈模型

部署在云機(jī)器人系統(tǒng)環(huán)境中的邊緣云服務(wù)器計(jì)算資源通常是有限的，且同時(shí)服務(wù)的用戶數(shù)也存在上限，因此邊緣云與機(jī)器人終端之間，每個(gè)機(jī)器人終端之間都存在著明顯的博弈過程，即邊緣云通過對服務(wù)定價(jià)影響機(jī)器人終端的卸載決策，而每個(gè)機(jī)器人終端的卸載決策同時(shí)也會(huì)對其他機(jī)器人的決策產(chǎn)生影響。為激勵(lì)機(jī)器人終端將計(jì)算任務(wù)卸載到邊緣云上執(zhí)行，保證云機(jī)器人系統(tǒng)高效運(yùn)行的前提下，解決邊緣云定價(jià)策略與機(jī)器人終端卸載策略的平衡問題，給出當(dāng)前系統(tǒng)條件下的最優(yōu)價(jià)格和計(jì)算卸載策略集。

機(jī)器人終端的卸載策略集X={x1,x2,…,xK}代表每個(gè)機(jī)器人卸載數(shù)據(jù)到邊緣云中占總數(shù)據(jù)量的比例，0

1) 機(jī)器人效用函數(shù)

機(jī)器人終端執(zhí)行計(jì)算卸載過程中的代價(jià)包括計(jì)算等待時(shí)間延遲、傳輸能耗以及使用邊緣云服務(wù)支付的費(fèi)用，可將機(jī)器人終端k的成本表示為：

(16)

機(jī)器人終端k的效用函數(shù)由任務(wù)執(zhí)行所得收益與執(zhí)行總代價(jià)之差組成，所得收益可用對數(shù)函數(shù)表示為Yk(xk)，參數(shù)β與機(jī)器人終端任務(wù)相關(guān)，β>0。

(17)

則機(jī)器人終端k的效用函數(shù)表示為：

(18)

在給定的邊緣云價(jià)格策略集下，機(jī)器人終端確定計(jì)算卸載策略集，最小化自身成本函數(shù)P1:

(19)

同時(shí)期望獲得最大的自身效用P2:

(20)

式中：tk代表機(jī)器人k執(zhí)行卸載計(jì)算的總時(shí)延；ek代表機(jī)器人k執(zhí)行卸載計(jì)算的總能耗；Tmax代表任務(wù)的最大等待延遲；Emax代表最大剩余可用能量。在眾多參數(shù)的限制下需要最優(yōu)化機(jī)器人終端自身效用。

2) 邊緣云效用函數(shù)

機(jī)器人使用計(jì)算資源支付的費(fèi)用的總和即為邊緣云效用函數(shù)的表達(dá)式：

(21)

在滿足邊緣云最大計(jì)算資源的條件下，邊緣云調(diào)整其定價(jià)策略，激勵(lì)機(jī)器人終端卸載任務(wù)到邊緣云中，最大化自身收益P3:

(22)

式中：Fedg_all為邊緣云最大的計(jì)算資源數(shù)。

2.4 云機(jī)器人系統(tǒng)中Stackelberg博弈求解

逆向歸納法通過將多階段動(dòng)態(tài)博弈過程沿時(shí)間軸劃分為多次單人博弈，確定每個(gè)參與者在不同時(shí)間點(diǎn)的最優(yōu)選擇，是分析和求解Stackelberg博弈均衡策略的常用方法。P3問題中制定的價(jià)格會(huì)影響P1優(yōu)化問題中的卸載策略，而同樣P1問題的卸載策略會(huì)反作用于P3問題，問題P1和P3是耦合的。結(jié)合逆向歸納法，將機(jī)器人終端的卸載策略問題分解為給定邊緣云定價(jià)策略集下的子問題，通過求解P1問題得到最優(yōu)卸載策略集，而邊緣云服務(wù)器可在已得最優(yōu)卸載策略下解決P3問題中的最優(yōu)價(jià)格。經(jīng)過多次子問題的演化分析，得到全局最優(yōu)的卸載策略集和價(jià)格策略集。

(23)

(24)

將解xk代入機(jī)器人終端的成本函數(shù)后可得：

(25)

在給定價(jià)格策略集下，pk視做常數(shù)，則上方成本函數(shù)可表示為變量xk的分段函數(shù)：

(26)

可將上述公式簡化為：

(27)

分析可知，當(dāng)A1k<0

(28)

(29)

當(dāng)邊緣云計(jì)算資源定價(jià)小于ω1k時(shí)，機(jī)器人終端將把所有計(jì)算任務(wù)卸載到邊緣云中執(zhí)行，而此時(shí)由于邊緣云請求的計(jì)算服務(wù)量過大，導(dǎo)致其處理任務(wù)的效率變低，因此邊緣云定價(jià)應(yīng)避開設(shè)置在該范圍。當(dāng)邊緣云計(jì)算資源定價(jià)大于ω2k時(shí)，機(jī)器人終端在進(jìn)行計(jì)算卸載時(shí)的成本開銷過大，導(dǎo)致所有任務(wù)都在本地進(jìn)行，而邊緣云的收益為0，因此邊緣云定價(jià)應(yīng)避開此區(qū)間。當(dāng)ω1k≤pk≤ω2k時(shí)，機(jī)器人終端將部分任務(wù)卸載到邊緣側(cè)執(zhí)行，保證了邊緣云的收益和任務(wù)處理效率，減少機(jī)器人處理任務(wù)的能耗。

3 系統(tǒng)實(shí)現(xiàn)與測試

1) 二進(jìn)制字串的第一個(gè)位置若為1，則起始位置為(1，2)，否則起始位置為(2，1)。進(jìn)入子串的下一個(gè)位置。

2) 當(dāng)下一位置上的二進(jìn)制值為1時(shí)，則1被填充到水平方向上的表格中，若下一位置的二進(jìn)制值為0，則0被填充到垂直方向上的表格中。

例如，在一個(gè)機(jī)器人終端數(shù)為10的云機(jī)器人系統(tǒng)環(huán)境中，將動(dòng)態(tài)規(guī)劃填充表使用圖3中的一個(gè)二維10×10的表格表示。

圖3 算法示例Fig.3 Algorithm example

假設(shè)第一個(gè)隨機(jī)字串為 “1110011001”(見圖3(a)中黑色字串)或者 “0011011000”(見圖3(a)中紅色字串)。第二個(gè)隨機(jī)字串為 “1100011110”(見圖3(b)綠色字串)。因?yàn)榈诙€(gè)字串的第一位為1，所以起始位置為(1，2)?；谠摲椒ㄌ幚?，可有效減少公共子串的重復(fù)計(jì)算。

每生成一個(gè)隨機(jī)的二進(jìn)制字串，需要計(jì)算該字串總的執(zhí)行時(shí)間和能量消耗，同時(shí)還需要計(jì)算表格中每個(gè)方格的總能量消耗和執(zhí)行時(shí)間。但是如果生成的隨機(jī)字串與在表格中的字串有相同的部分，則在計(jì)算二進(jìn)制字串的時(shí)間和能耗時(shí)只計(jì)算到第一個(gè)相同數(shù)值的方格，然后將新計(jì)算的總能量和記錄在該方格內(nèi)的總能量相比較。如果新計(jì)算的總能量小于記錄在方格內(nèi)的能量，則使用新的子串代替舊的子串，并使用新計(jì)算的總能量、能量消耗以及執(zhí)行時(shí)間替換掉已記錄的值?；谠撘?guī)則更新剩下的所有子串的能量和執(zhí)行時(shí)間。否則，如果新計(jì)算的總能量大于記錄在方格中的總能量，則保留在該方格中已記錄的子串。當(dāng)算法中的字串Hamming距離大于給定閾值，便終止循環(huán)并返回計(jì)算結(jié)果。

機(jī)器人終端的CPU處理能力隨機(jī)分布于集合{0.1 GHz,0.2 GHz,…,1.0 GHz}之中，每執(zhí)行1字節(jié)數(shù)據(jù)需要消耗的CPU周期數(shù)在500～1 500 cycles/bit隨機(jī)分布，機(jī)器人終端k的輸入待處理數(shù)據(jù)總量Rk設(shè)置為100～300 KB的隨機(jī)值。機(jī)器人終端通信設(shè)備的發(fā)射功率為0.1 W，接收功率為0.06 W，通信AP節(jié)點(diǎn)的發(fā)射功率為1 W。邊緣云計(jì)算能力100 GHz。機(jī)器人數(shù)量最小為15，以15的倍數(shù)增長。時(shí)間權(quán)重因子λt隨機(jī)分布于區(qū)間[0,1]，能量權(quán)重因子λe=1-λt。

在將系統(tǒng)部分參數(shù)去除隨機(jī)性后，機(jī)器人終端成本開銷和效用隨計(jì)算卸載比例的變化曲線圖見圖4和圖5。

圖4 計(jì)算卸載成本均值隨卸載比例實(shí)驗(yàn)曲線Fig.4 Experiment curve of average offloading cost at offloading ratio

圖5 機(jī)器人終端效用均值隨卸載比例實(shí)驗(yàn)曲線Fig.5 Experiment curve of average utility of robot terminal at offloading ratio

隨著計(jì)算卸載比例增大，更多的計(jì)算任務(wù)卸載到邊緣測執(zhí)行，使機(jī)器人終端計(jì)算成本降低。但由于越來越多的機(jī)器人對任務(wù)執(zhí)行卸載，使邊緣云資源競爭愈發(fā)激烈，導(dǎo)致計(jì)算資源價(jià)格上升，使機(jī)器人終端的成本函數(shù)增大，因此機(jī)器人終端成本開銷的平均值會(huì)隨著卸載比例的增大先減小再增大。而用戶效用的平均值會(huì)隨著卸載比例增大，付出更多的成本，而執(zhí)行計(jì)算卸載的收益趨于平衡。此實(shí)驗(yàn)驗(yàn)證了系統(tǒng)模型的正確性。

圖6表示當(dāng)邊緣云網(wǎng)絡(luò)內(nèi)的機(jī)器人終端數(shù)量增加時(shí)，任務(wù)全部本地執(zhí)行和使用本文提出的Stackelberg博弈方法在機(jī)器人終端成本開銷上的對比結(jié)果。結(jié)合文中的分析可知，在使用Stackelberg博弈方法時(shí)，機(jī)器人終端成本開銷的平均值明顯低于本地執(zhí)行的開銷，因?yàn)殡m然本機(jī)計(jì)算無需向邊緣云支付計(jì)算資源費(fèi)用，但本地計(jì)算時(shí)間延遲較高，使成本開銷增大。

圖6 機(jī)器人終端本地及卸載計(jì)算成本隨用戶數(shù)實(shí)驗(yàn)曲線Fig.6 Experiment curve of tasks’ cost running in local and offloading follow the growing usrs

4 結(jié) 語

本文基于Stackelberg博弈思想設(shè)計(jì)了云機(jī)器人系統(tǒng)環(huán)境下機(jī)器人終端執(zhí)行計(jì)算任務(wù)卸載的優(yōu)化算法，解決在多機(jī)器人終端競爭同一邊緣云服務(wù)器計(jì)算資源場景下的邊緣云效用及機(jī)器人終端效用均衡問題。并就移動(dòng)終端的卸載決策問題提出了一種基于動(dòng)態(tài)規(guī)劃的優(yōu)化算法，該算法通過開辟存儲(chǔ)計(jì)算過程的數(shù)組，減少了對公共子串的重復(fù)計(jì)算。通過對不同計(jì)算能力和能量狀態(tài)的機(jī)器人終端設(shè)置不同的權(quán)重因子，以及對計(jì)算卸載決策博弈過程的分析，分別選擇對機(jī)器人終端和邊緣云最優(yōu)的卸載策略和定價(jià)策略。結(jié)合實(shí)驗(yàn)分析，該系統(tǒng)有效降低機(jī)器人終端計(jì)算能量消耗以及提高邊緣云自身效用，并驗(yàn)證了系統(tǒng)模型的正確性。