云機器人系統的計算卸載策略研究

孫 弋， 許志杰

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

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

1 相關研究

1.1 云機器人系統架構

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

1.2 計算卸載

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

圖1 計算卸載流程圖Fig.1 Calculation offloading flow chart

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

綜上，為降低通信設備壓力，提高云端服務調度靈活性，本文在云機器人系統中選擇部分卸載的計算卸載策略。本文重點研究在同一邊緣“網絡”只有單個邊緣云，且邊緣云的計算資源是有限時，實現機器人計算任務部分卸載的策略研究。

2 計算卸載系統模型

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

2.1 系統網絡模型

一個計算卸載網絡由一個具備計算加速服務的邊緣云和K個機器人終端集合N={1,2,…,K}組成，單個通信AP節點下管理至多K個移動機器人終端，其網絡模型見圖2。

圖2 系統網絡模型Fig.2 System network model

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

2.2 任務執行模型

基于上述的網絡模型，計算任務可在本地或邊緣側執行，首先對計算任務進行建模。云機器人系統中，功能各異的機器人終端選擇適當的CPU計算能力，編號為k的機器人終端其計算能力用每秒CPU周期數Fk衡量，單位為cycles/s，執行任務所需計算數據總量為Rk，單位為Byte，每執行1bit數據所需的CPU周期數為Ck，單位為cycle。計算任務卸載到邊緣側執行的比例為xk，0≤xk≤1，故執行卸載的數據量為xkRk，本地執行的數據量為(1-xk)Rk。時間延遲和能量消耗是評價計算卸載策略優劣的重要指標，下文對任務本地執行和任務遠端執行中的時間延遲和能量消耗計算方法進行建模。

1) 任務本地執行模型

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

(1)

(2)

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

2) 任務遠端執行模型

(3)

(4)

機器人終端與通信AP節點之間的信道帶寬為B/K，單次計算卸載周期內信道噪聲功率不變，為σ，其本地通信設備發送功率為Pk，機器人終端與通信AP節點之間的信號增益為Gk，根據Shannon公式可得：

(5)

因此機器人終端k上載任務數據到邊緣云上的傳輸時間為：

(6)

數據的上載和下載處于相同信道環境中，可得數據下載速率為：

(7)

式中：PBS為通信AP節點的通信設備發送功率。

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

(8)

(9)

在此系統中任務可在本地和邊緣側同時進行計算，因此機器人k執行總數據量為Rk的任務需要的時間為：

(10)

(11)

式中：TPs,k表示機器人k通信設備的發送功率。

計算結果反饋過程中所消耗能量為：

(12)

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

(13)

為對計算卸載過程中需付出的代價進行評估，設計了由多項式組成的評價代價函數公式：

(14)

能耗權重因子λe和時間延遲因子λt滿足約束條件，λe+λt=1。則計算卸載過程中總的代價函數表示為：

(15)

2.3 云機器人系統中的Stackelberg博弈模型

部署在云機器人系統環境中的邊緣云服務器計算資源通常是有限的，且同時服務的用戶數也存在上限，因此邊緣云與機器人終端之間，每個機器人終端之間都存在著明顯的博弈過程，即邊緣云通過對服務定價影響機器人終端的卸載決策，而每個機器人終端的卸載決策同時也會對其他機器人的決策產生影響。為激勵機器人終端將計算任務卸載到邊緣云上執行，保證云機器人系統高效運行的前提下，解決邊緣云定價策略與機器人終端卸載策略的平衡問題，給出當前系統條件下的最優價格和計算卸載策略集。

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

1) 機器人效用函數

機器人終端執行計算卸載過程中的代價包括計算等待時間延遲、傳輸能耗以及使用邊緣云服務支付的費用，可將機器人終端k的成本表示為：

(16)

機器人終端k的效用函數由任務執行所得收益與執行總代價之差組成，所得收益可用對數函數表示為Yk(xk)，參數β與機器人終端任務相關，β>0。

(17)

則機器人終端k的效用函數表示為：

(18)

在給定的邊緣云價格策略集下，機器人終端確定計算卸載策略集，最小化自身成本函數P1:

(19)

同時期望獲得最大的自身效用P2:

(20)

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

2) 邊緣云效用函數

機器人使用計算資源支付的費用的總和即為邊緣云效用函數的表達式：

(21)

在滿足邊緣云最大計算資源的條件下，邊緣云調整其定價策略，激勵機器人終端卸載任務到邊緣云中，最大化自身收益P3:

(22)

式中：Fedg_all為邊緣云最大的計算資源數。

2.4 云機器人系統中Stackelberg博弈求解

逆向歸納法通過將多階段動態博弈過程沿時間軸劃分為多次單人博弈，確定每個參與者在不同時間點的最優選擇，是分析和求解Stackelberg博弈均衡策略的常用方法。P3問題中制定的價格會影響P1優化問題中的卸載策略，而同樣P1問題的卸載策略會反作用于P3問題，問題P1和P3是耦合的。結合逆向歸納法，將機器人終端的卸載策略問題分解為給定邊緣云定價策略集下的子問題，通過求解P1問題得到最優卸載策略集，而邊緣云服務器可在已得最優卸載策略下解決P3問題中的最優價格。經過多次子問題的演化分析，得到全局最優的卸載策略集和價格策略集。

(23)

(24)

將解xk代入機器人終端的成本函數后可得：

(25)

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

(26)

可將上述公式簡化為：

(27)

分析可知，當A1k<0

(28)

(29)

當邊緣云計算資源定價小于ω1k時，機器人終端將把所有計算任務卸載到邊緣云中執行，而此時由于邊緣云請求的計算服務量過大，導致其處理任務的效率變低，因此邊緣云定價應避開設置在該范圍。當邊緣云計算資源定價大于ω2k時，機器人終端在進行計算卸載時的成本開銷過大，導致所有任務都在本地進行，而邊緣云的收益為0，因此邊緣云定價應避開此區間。當ω1k≤pk≤ω2k時，機器人終端將部分任務卸載到邊緣側執行，保證了邊緣云的收益和任務處理效率，減少機器人處理任務的能耗。

3 系統實現與測試

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

2) 當下一位置上的二進制值為1時，則1被填充到水平方向上的表格中，若下一位置的二進制值為0，則0被填充到垂直方向上的表格中。

例如，在一個機器人終端數為10的云機器人系統環境中，將動態規劃填充表使用圖3中的一個二維10×10的表格表示。

圖3 算法示例Fig.3 Algorithm example

假設第一個隨機字串為 “1110011001”(見圖3(a)中黑色字串)或者 “0011011000”(見圖3(a)中紅色字串)。第二個隨機字串為 “1100011110”(見圖3(b)綠色字串)。因為第二個字串的第一位為1，所以起始位置為(1，2)。基于該方法處理，可有效減少公共子串的重復計算。

每生成一個隨機的二進制字串，需要計算該字串總的執行時間和能量消耗，同時還需要計算表格中每個方格的總能量消耗和執行時間。但是如果生成的隨機字串與在表格中的字串有相同的部分，則在計算二進制字串的時間和能耗時只計算到第一個相同數值的方格，然后將新計算的總能量和記錄在該方格內的總能量相比較。如果新計算的總能量小于記錄在方格內的能量，則使用新的子串代替舊的子串，并使用新計算的總能量、能量消耗以及執行時間替換掉已記錄的值。基于該規則更新剩下的所有子串的能量和執行時間。否則，如果新計算的總能量大于記錄在方格中的總能量，則保留在該方格中已記錄的子串。當算法中的字串Hamming距離大于給定閾值，便終止循環并返回計算結果。

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

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

圖4 計算卸載成本均值隨卸載比例實驗曲線Fig.4 Experiment curve of average offloading cost at offloading ratio

圖5 機器人終端效用均值隨卸載比例實驗曲線Fig.5 Experiment curve of average utility of robot terminal at offloading ratio

隨著計算卸載比例增大，更多的計算任務卸載到邊緣測執行，使機器人終端計算成本降低。但由于越來越多的機器人對任務執行卸載，使邊緣云資源競爭愈發激烈，導致計算資源價格上升，使機器人終端的成本函數增大，因此機器人終端成本開銷的平均值會隨著卸載比例的增大先減小再增大。而用戶效用的平均值會隨著卸載比例增大，付出更多的成本，而執行計算卸載的收益趨于平衡。此實驗驗證了系統模型的正確性。

圖6表示當邊緣云網絡內的機器人終端數量增加時，任務全部本地執行和使用本文提出的Stackelberg博弈方法在機器人終端成本開銷上的對比結果。結合文中的分析可知，在使用Stackelberg博弈方法時，機器人終端成本開銷的平均值明顯低于本地執行的開銷，因為雖然本機計算無需向邊緣云支付計算資源費用，但本地計算時間延遲較高，使成本開銷增大。

圖6 機器人終端本地及卸載計算成本隨用戶數實驗曲線Fig.6 Experiment curve of tasks’ cost running in local and offloading follow the growing usrs

4 結 語

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