孫毅，常少南，陳愷，崔強，沈維捷

(1. 華北電力大學 電氣與電子工程學院，北京 102206；2. 國網物資有限公司，北京 100120；3. 國網上海市電力公司，上海 200122)

0 引言

電工裝備建造質量是決定能源互聯網可靠安全運行的重要因素[1]。為了推動電工裝備高質量發(fā)展，國家電網有限公司全力打造電工裝備現代化“5 E一中心”供應鏈運作體系。截至2020年年底，電工裝 備 智 慧 物 聯 平 臺 (electrical equipment intelligent IoT platform，EIP)在上海開展試點且已接入53家供應商，覆蓋23類電網物資[2-3]。然而EIP供需信息實時共生共享的需求難以滿足，亟須技術保障EIP所需業(yè)務數據高效傳輸與處理。

隨著工業(yè)互聯網發(fā)展，要求各類傳感器、工業(yè)機器人的數據能夠就近完成計算，以提高智能工業(yè)設備運行效率[4-5]、故邊緣計算作為新興計算方案，在工業(yè)互聯網領域得到廣泛關注[6]。傳統(tǒng)工業(yè)互聯網的任務卸載研究關注異構設備之間執(zhí)行任務卸載的協調性與統(tǒng)一性[7-10]，并針對完成任務所需時延、能耗等目標進行優(yōu)化。如文獻[8]提出了一種時延依賴-優(yōu)先級感知的任務卸載策略，用于將從IoT設備生成的任務卸載到恰當的邊緣計算設備完成處理。文獻[9]分析了人工智能（artificial intelligence, AI）計算任務復雜性帶來的高能耗問題，并提出一種面向異構任務的綠色邊緣計算任務調度框架以降低AI計算能耗。EIP作為工業(yè)互聯網在能源領域的延伸與重要應用實踐之一[1]，工業(yè)邊緣計算架構的引入可有效解決EIP無法實現實時監(jiān)造與全息畫像等時延敏感型業(yè)務的低時延計算困境。

而現有研究中，工業(yè)互聯網的邊緣計算不但需關注協調性與統(tǒng)一性，還需關注網絡中不同主體之間的利益交互。如EIP信息設備主要由電網系統(tǒng)直接部署與管理，并通過智慧物聯網關完成供應商及電網內外網信息交互[11-12]，上述行為涵蓋電網、供應商與第三方服務商等多個主體，部分業(yè)務計算需依賴第三方提供相關服務，因此在執(zhí)行任務卸載時還需考慮供應商服務成本的優(yōu)化。文獻[13]為節(jié)約計算成本，提出一種基于最小成本最大流圖的任務卸載算法以提高邊緣節(jié)點的計算效用比。文獻[14-15]分別提出一種面向邊緣計算的多服務提供商算力共享平臺讓用戶可以選擇性地獲取最優(yōu)計算服務。

上述工作均默認邊緣節(jié)點緩存有全部服務功能，實際情況下邊緣節(jié)點的緩存空間有限，無法部署全部計算功能，需在邊緣設備中緩存重要應用服務及數據庫以滿足對應計算任務在邊緣側快速處理的需求。近年來，聯合服務緩存與任務卸載問題開始得到關注，對服務緩存容量有限情況下的任務卸載決策進行研究，以降低任務延遲和能耗。文獻[16]首次研究任務卸載和服務緩存聯合優(yōu)化問題。文獻[17]研究聯合任務緩存和任務調度問題，構建基于合作博弈的車聯網服務模型，降低了整體通信時延。文獻[18]研究了單服務器下的聯合服務緩存與任務卸載問題并提出了基于半定松弛的優(yōu)化算法，降低了求解復雜度。文獻[19]研究一種基于動態(tài)規(guī)劃的服務功能代碼庫緩存和計算卸載策略優(yōu)化算法，減少任務執(zhí)行延遲和用戶能耗的加權總和。文獻[20]在考慮用戶信息不確定性前提下基于貝葉斯博弈提出一種計算收益最大化的聯合服務緩存與任務卸載決策算法。文獻[21]提出通信、計算和服務緩存聯合優(yōu)化模型，利用異步分布式強化學習優(yōu)化卸載決策和資源管理方案。

上述工作僅研究了單服務器多用戶場景下的聯合服務緩存與任務卸載，未考慮多邊緣計算節(jié)點多用戶場景下的服務緩存問題；并且上述工作假設緩存服務全部由同一電信運營商提供，不會存在收益沖突。在現實場景中EIP涉及的服務功能與相關數據庫種類豐富且功能復雜，需要多個服務提供商提供算法庫或者軟件程序。針對上述問題，本文提出了面向電工裝備智慧物聯場景的聯合服務功能緩存與任務卸載策略，涉及的工作與創(chuàng)新點如下。

（1）針對現有工作僅研究單服務器-多用戶場景下的聯合服務緩存與任務卸載模型，本文提出了一種面向EIP場景的多邊緣節(jié)點-多供應商-服務提供商的聯合服務緩存與任務卸載模型，令邊緣物聯代理協同為供應商提供最優(yōu)計算服務功能部署策略以及低時延計算服務。

（2）針對現有工作未考慮電工裝備智慧物聯場景下供應商與第三方服務商服務收益與計算性價比相沖突的問題，本文提出一種基于主從博弈的聯合服務緩存與任務卸載策略解決沖突問題，并得到各方收益最優(yōu)時的緩存決策與卸載決策。

（3）針對傳統(tǒng)Benders分解方法求解主問題效率低下問題，進一步提出一種結合粒子群的廣義benders分解算法加速問題求解速度。

1 面向電工裝備智慧供應鏈的云邊協同網絡模型

考慮一個面向電網系統(tǒng)與電工裝備供應商（以下簡稱供應商）信息交互的網絡場景，如圖1所示，由一個電力中心云平臺與個邊緣物聯代理 (edge computing device, ECD)組 成，云中心編號為0。ECD之間的服務范圍互不重疊，為范圍內的電工裝備生產供應商提供計算服務，每個供應商配置一個通信終端，記供應商通信終端集合記為（以下簡稱為終端）。另外，ECD還可充當中繼節(jié)點將計算任務轉發(fā)到鄰近一跳內的其他ECD或更上層云平臺上完成計算。

圖1 面向電工裝備智慧供應鏈的云邊協同網絡模型Fig. 1 The cloud-edge collaborative network model for EIP

假設網絡計算服務提供商（以下簡稱服務商）在該網絡場景中為供應商提供種對應的計算服務，考慮到電網公司需要供應商提供相關生產信息用于開展產能分析、質量檢測等業(yè)務，因此設供應商終端的計算任務只能將任務上傳到ECD上完成處理。在本文中，供應商終端任務均不可繼續(xù)拆分為多個子數據塊來處理。設各供應商i有一個計算任務需要處理，計算任務屬性可以由所需服務功能類型、數據規(guī)模（單位bit）和計算任務所需CPU周期（單位MHz）3種屬性描述，分別表示為、和。

1.1 服務功能緩存模型

式（2）表示終端 i的任務只能歸屬到一種服務類型。當ECD緩存服務時能夠為需要該類型服務功能的計算任務提供服務，否則任務需卸載到緩存了服務的ECD或云中心完成計算。最后，ECD的緩存決策需滿足

1.2 任務卸載與數據傳輸模型

1.3 電力業(yè)務數據計算模型

ECD可用計算資源有限，需要為計算任務合理分配計算能力完成處理。設第個ECD的計算資源由CPU工作頻率表示， fi=fk·χik為分配給終端 i 的計算資源，其中計算資源分配系數χik∈[0,1]，應滿足

任務計算時間與ECD的CPU工作頻率有關，設終端i 的任務所需計算時間為

2 基于供應商-服務提供商的兩階段主從博弈模型

服務商和供應商的兩階段主從博弈模型如圖2所示，服務商是領導者，占主導地位，其目標為最大化邊緣計算設備的服務功能使用收益，供應商終端是追隨者。本文所提博弈第1階段令各服務商宣布計算服務價格和緩存決策，第2階段令各供應商選擇卸載決策，同時網絡根據卸載決策進行計算資源分配，如圖2所示。

圖2 服務商和供應商終端的兩階段主從博弈模型Fig. 2 The two-stage Stackelberg game model for service providers and suppliers

供應商終端的目標是做出最優(yōu)的卸載決策，一方面，為了保證電工裝備智慧供應鏈的正常運行，需要盡可能地降低任務計算時延；另一方面供應商需要借用服務商的服務資源，將帶來計算服務成本。供應商的目標為最小化計算資源的服務成本和任務計算總時延 R (x,b)，表示為

服務商部署到ECD的服務功能得到供應商使用時，將帶來計算服務收益，這促使服務商盡可能在邊緣網絡部署更多類型的服務令供應商訪問，服務商的目標為最大化邊緣計算設備的服務功能使用收益。一方面服務商需要保證服務收益；另一方面，為了滿足電工裝備智慧物聯供應鏈建設需求，在保證任務計算時延的同時其業(yè)務通信與計算時延需要盡可能在本地ECD完成處理，若服務商未恰當部署服務功能，造成較多的計算任務需要上傳電工裝備智慧物聯云平臺進行處理，將導致網絡帶寬以及業(yè)務服務質量造成惡化，進而給服務商帶來負收益，任務卸載到云中心造成的虧損為，為一個定值。

因此，以考慮服務收益最大化為目標的聯合緩存與卸載決策問題可表示為

式中：約束（3）為服務功能緩存容量約束；約束（4）表示終端只能將任務卸載到緩存有對應服務類型的ECD上；約束（9）與約束（10）分別為ECD計算資源分配限制以及分配系數與卸載變量的關系。

根據逆向歸納法原理[22-23]，本文提出的主從博弈模型的納什均衡點存在且唯一。由于變量為0?1變量，式（14）為MIP問題，求解難度為NP-HARD，求解時間復雜度隨用戶以及ECD的數目以及服務功能類型的增多而呈指數上升。因此，本文將提出一種聯合服務緩存和計算卸載優(yōu)化算法實現問題求解。

3 基于GBD的聯合服務緩存和計算卸載優(yōu)化算法

根據約束（16）～（18）得到約束矩陣Y(b,p)為

由于其他決策向量固定，式（15）只包含連續(xù)變量且為凹函數，故價格優(yōu)化子問題式（15）可以通過內點法獲取最優(yōu)的價格策略以及約束條件的最優(yōu)拉格朗日乘子。定義為次迭代中價格優(yōu)化子問題的最優(yōu)值，該值為服務商目標函數優(yōu)化問題上界。

在GBD方法中，主問題用于求解固定價格決策下的最優(yōu)緩存決策，因此服務緩存決策問題可表達為

同樣基于GBD方法的分離定理，供應商目標函數可以分解成一個卸載決策主問題和計算。引入一個十分小的正實數來擴展計算資源分配優(yōu)化子問題變量的取值范圍，避免出現取值為0導致求解錯誤，記擴展后的變量，取值范圍變成，設在第t次迭代中的緩存決策為，價格策略為，任務卸載決策為其中為當前循環(huán)迭代次數，計算資源分配子問題表示式為

由于卸載決策向量固定，同理計算資源分配優(yōu)化子問題式（22）可以通過內點法獲取最優(yōu)資源分配決策以及約束條件的最優(yōu)拉格朗日乘子。定義為在第次迭代中計算資源分配優(yōu)化子問題的最優(yōu)值，該值為供應商目標函數優(yōu)化問題的上界。由于卸載決策主問題用于求解固定資源分配決策下的最優(yōu)緩存卸載決策，可將主問題表示為

而在實際情況下，采用分支定界法求解式（21）和式(27)將產生高計算復雜度。因此，本文進一步提出采用二進制粒子群優(yōu)化算法(particle swarm optimization, PSO)解決主問題求解[24]，進而加速迭代過程。結合粒子群的GBD算法具體實現流程如圖3所示。

圖3 基于粒子群的GBD算法流程Fig. 3 Flow chart of PSO-based GBD algorithm

4 仿真分析

文章基于 MATLAB R2019 a，Intel(R) Core(TM)i7-10700 F CPU @2.90 GHz以及 32 GB內存環(huán)境進行。另外，本文采用CVX工具箱[25]內嵌的內點法[26]完成GBD方法中的涉及IP問題求解。本文考慮了一個如圖1所示的仿真網絡場景，其中存在 Kmax=6個ECD，在各ECD的覆蓋范圍中用戶數目服從為 λIk=20的泊松分布，每個ECD的覆蓋范圍互不重疊，各ECD通過光纖鏈路相連并構成如圖1所示的LAN通信網架，每個終端在很短的時間內僅生成一個業(yè)務計算需求，其中業(yè)務數據服從λs=0.5Mb的指數分布。涉及的電工物聯業(yè)務功能有類，包括智能監(jiān)造、智能量測、產能分析，區(qū)塊鏈訂單智能交易等功能，分別對應的電力APP服務功能數據規(guī)模服從 s′∈[0.5,2]Mbit的均勻分布。在本文仿真中，為簡化計算，假設所有ECD具有相同的緩存容量，記 C =15 Mbit，忍耐系數 τb= τx= τ=0.01，要注意的是，本文算法在ECD具有不同緩存容量的仿真場景一樣適用。最后，其他仿真參數如表1所示。

表1 仿真參數設定Table 1 Simulation parameters

在下述仿真分析中，將所提算法與固定定價的緩存與卸載算法、定制價格與熱門緩存與卸載算法[20]、定制價格與時延最優(yōu)卸載算法[27]在收益優(yōu)化、網絡時延以及緩存命中率3種性能指標上進行對比。

圖4為采用粒子群算法求解GBD分解后的整數規(guī)劃主問題的收斂性分析，可以看到，當算法達到600次迭代后算法收斂，粒子群找到了在固定資源分配決策下的任務卸載與緩存決策最優(yōu)解。

圖4 主問題求解收斂性分析Fig. 4 Convergence analysis of main problem solution

圖5展示了緩存容量變化對算法性能的影響。隨著緩存容量上升，供應商計算成本、服務商的服務收益均呈近線性上升，其中本文算法通過主從博弈模型，在服務商更新緩存策略后，供應商再根據服務商提供的信息更新任務卸載策略，令供應商與服務商收益競爭達到平衡點，因此博弈雙方收益相對均衡，其中供應商具有最低的服務成本并保證了服務商收益能夠維持在較高值，另外，相比于其他算法，由于考慮了供應商的計算時延需求，在保障低成本開銷同時具有與時延最優(yōu)算法相近的時延性能。

圖5 數據規(guī)模對算法收益影響分析Fig. 5 Impact analysis of the data size on algorithm revenue

4種緩存與計算模型的供應商與服務商收益變化受云計算懲罰成本影響的情況如圖6所示。固定定價的緩存與決策算法的定價模式由于不受到懲罰成本變化的影響，在任何情況下均固定定價，因此隨著懲罰成本上升令服務商具有更精確的緩存決策時，供應商用戶能夠獲取更多的服務并付出更低成本，但導致供應商在大部分情況下出現虧損；而隨著懲罰成本增加，本文算法能夠通過主從博弈模型，動態(tài)調整供應商與服務商的卸載與緩存決策，服務商為了獲得更高的計算收益，需在改變緩存決策時需要充分考慮供應商決策的變化，因此雙方在博弈中達到均衡時能夠實現雙方共贏，獲取最優(yōu)時延與服務收益。

圖6 ECD供應商通信終端數目變化對算法性能影響Fig. 6 Influence of the ECD supplier communication terminal number change on algorithm performance

在博弈過程中，聯合服務緩存與任務卸載模型的時延性能除了受到雙方博弈動作影響，還與ECD可用計算資源相關。如圖7所示，在可用計算資源較少的階段，3種模型均具有高的計算時延，這是由于不論具有多少緩存空間，計算資源不足導致了部分任務只能上傳云計算層完成計算；而隨著計算資源增多，服務緩存功能部署充足時，供應商能夠就近在邊緣獲取更多計算服務用于實現實時監(jiān)造與安全識別等時延敏感型業(yè)務，進而相比于另外兩種模型具有更優(yōu)的時延性能，而熱門度優(yōu)先算法僅考慮了歷史情況，無法根據實際用戶偏好變化決定當前時段的用戶緩存需求，而固定定價由于無法為服務商帶來明顯收益，而導致用戶卸載決策不具有可調度性，進而影響了計算性能。

圖7 ECD計算資源變化對算法性能影響Fig. 7 Impact of the ECD computing resource change on algorithm performance

圖8展示了3種算法的服務功能緩存命中率性能。明顯地，由于本文算法能考慮實時終端計算需求，具有較好的緩存命中率，而熱門度優(yōu)先緩存算法僅依靠歷史記錄決策，無法考慮現階段供應商終端計算任務類型的變化，而隨機緩存并未考慮任何因素，具有最差的性能。

圖8 緩存命中率分析Fig. 8 Analysis of cache hit ratio

5 結論

本文針對面向電工裝備智慧供應鏈的聯合服務緩存與任務卸載策略優(yōu)化問題提出了一種多邊緣節(jié)點-多供應商-服務提供商的聯合服務緩存與任務卸載模型，基于供應商-服務提供商兩階段主從博弈模型，求解得到服務緩存容量有限情況下最優(yōu)的任務卸載決策，實現了服務提供商收益和供應商終端任務成本以及時延加權的優(yōu)化。最后通過算例分析驗證了所提模型的有效性。主要得出以下結論。

（1）通過分析與推導證明了所提的基于供應商-服務提供商的兩階段主從博弈模型存在唯一均衡解，既能降低服務成本也能降低任務時延。

（2）通過提出結合粒子群的廣義benders分解算法，解決傳統(tǒng)benders分解方法求解主問題效率低下的問題。

（3）通過對比仿真網絡場景下，其他條件一定時，緩存容量變化、云計算懲罰成本變化、ECD可用計算資源變化3種情況時的服務成本和用戶不滿意度，分析得到所提優(yōu)化策略能實現服務商收益以及通信時延的優(yōu)化。

綜上，本文提出的基于主從博弈的聯合服務緩存與任務卸載優(yōu)化策略有助于解決服務緩存容量有限情況下的任務卸載決策問題，具有較好的適應性和經濟性。但是在本文研究中只選取服務成本和任務時延兩個指標對任務卸載的結果進行評價，之后的研究中可以針對更多評價指標展開研究。