分布式場景下基于拍賣算法的邊緣智能節點任務分配

李浩，陳迪，李林，王莉

（63892部隊，河南 洛陽 471003）

0 引言

隨著當前計算機技術的迅猛發展，以及應用對計算能力要求的提升，智能邊緣計算憑借其優秀的計算能力得到了越來越廣泛的應用，是6G 移動通信網絡非常重要的一個組成部分。智能邊緣計算是由多個獨立的計算系統通過移動通信網絡形成邏輯集中以及物理上分布的計算系統[1]。智能邊緣計算具有諸多優點，包括動態性、可靠性、實時性等[2]。為了減少網絡通信時間，實現更快的處理響應，邊緣計算將相關計算資源、存儲能力下沉到邊緣設備，使得大量的任務在邊緣設備上進行處理。在分布式環境下，如何優化任務分配，使得智能邊緣計算節點的資源獲得更好的利用，這是智能邊緣計算亟需解決的關鍵問題。隨著用戶任務的增加，智能邊緣計算節點處理的復雜度也會隨之增加。因此，任務分配方法的智能性顯得至關重要，一個好的分配策略能夠使任務獲得更早的完成時間，提高任務的執行效率[3]。

分布式環境下的智能邊緣計算系統可視為由多個智能邊緣節點組成的集合，其主要目標是將大而復雜的系統轉換成小的、彼此相互通信和協調的、易于管理的系統。分布式環境下的智能邊緣計算系統具有自主性、分布性和協調性，并具有較好的自組織能力、自學習能力和推理能力[4]。在分布式網絡環境下，系統中存在多個不同的邊緣節點和多個不同的任務，如何將多個邊緣節點合理映射到多個任務上，是任務分配的關鍵問題[5-6]。任務分配的目的是最大化整個系統執行任務的效益，同時最小化執行任務所需的代價。任務分配的好壞直接影響到整個系統協作的效率，并關系到各個邊緣計算節點能否最大限度發揮自身能力。

在分布式場景下，多任務的高效分配方案需滿足兩點要求：首先，要在規定的時間內找到一個接近最優的任務分配方案，即最優性；其次，要保證任務分配方案在整個運行時間的效率，即動態性[7]。針對以上要求，本文提出了一種在分布式環境下基于拍賣算法的任務分配策略，解決6G 分布式場景下的邊緣節點任務高效分配問題。在任務分配過程中，綜合考慮完成任務的效益及各個邊緣計算節點完成任務需付出的代價，采用拍賣的方式進行任務分配，從而得到一個任務分配方案，保證在最大化整個系統效益的同時最小化整個系統執行任務所需要的代價。

1 相關研究工作

1.1 分布式系統下的任務分配

在分布式系統中，任務分配是一個被研究多年的經典問題。任務分配的目標是把任務合理地分配到系統的每一個處理節點上，使程序的總體執行時間最短。任務分配算法的優劣影響了分布式環境下的系統性能。任務分配主要從時間和空間兩個方面考慮，最終將需要分配的任務調度到相應處理機上，合理的任務分配策略能夠提高處理機系統中資源的利用率、降低系統能耗以及提高任務調度的效率。影響任務分配的因素包括任務下發的價格、任務本身的執行代價、任務之間的通信開銷以及任務之間的依賴關系等。

根據任務之間的關系，可以把任務分配分為兩種類型：一種是任務之間沒有依賴關系的獨立任務的任務分配，另一種是任務之間有依賴關系，是相互之間有通信和上下文依賴關系的任務分配。針對分布式環境下的任務分配問題，國內外學者做了大量研究工作。文獻[8] 針對分布式環境中的靜態任務調度問題開展研究，提出了一種基于最早完成時間策略改變調度順序的表調度算法。算法針對現有表調度算法在調度前不能準確地確定調度順序的問題，在此基礎上添加了一個動態優先級調度策略，當節點的前驅任務都已經完成調度任務時，相應地改變當前節點的優先級。文獻[9] 針對分布式環境下提出了一種基于任務復制以及任務插入的聚類和歸并算法，算法分為初始分簇、任務復制、任務歸并以及任務插入等幾個步驟，算法還充分考慮了連鎖鏈式反應，可以解決本輪無效的任務復制在下一輪變成有效的問題。文獻[10]基于合理的任務復制和分簇，實現關鍵任務的盡早調度，使工作流的最早完成時間得以提前，對任務簇進行聚集，從而可以充分利用任務簇中任務間可能的空閑時間；另外，對已聚類的工作流任務集使用任務后向優先合并的方法，可以實現任務間空閑時間版的有效利用，從而可優化工作流的完成時間。

1.2 拍賣算法

拍賣算法由麻省理工學院學者Bertsekas 于1988 年提出[11]，后來在任務分配問題上得到了廣泛的應用。陶雪麗等運用拍賣算法對物資運輸任務分配問題進行了求解，得到了較優的分配結果，驗證了算法在該問題上的有效性[12]。柳鵬等提出設立虛擬火力點和目標的方法對拍賣算法進行改進，并解決防空火力打擊目標分配問題，討論了拍賣算法價格增量ε 取值對目標分配結果的影響[13]。許可等針對異構多無人機系統的任務分配問題，分別設了帶共享存儲中心分布式拍賣算法和移除共享存儲中心完全分布式拍賣算法，驗證了算法的收斂性和有效性[14]。高龍設計了分布式拍賣算法，并以保障單元個體目標收益最大為分配依據，構建了裝備保障體系任務分配框架[15]。

2 系統模型

2.1 任務模型

無線網絡旨在實現和支撐萬物智聯、萬務互聯，成為支撐各行業的智能基礎設施平臺。為了適應新時代下不同產業跨界升級和新商業模式變革等訴求，無線網絡系統通過深度融合通、感、算、智、存等功能于一體的無線基礎設施平臺，并同時具備“通信”、“感知”、“計算”、“智能”和“存儲”等方面更強大業務能力；對外能夠提供更強、更高效地提供“通信”、“感知”、“計算”、“智能”和“存儲”等方面服務應用[16]，系統模型如圖1 所示。

圖1 系統模型

考慮在網絡覆蓋區域內有n個邊緣計算節點組成的邊緣計算節點集合U={u1,u2,…,un}，包含t個任務集合T={t1,t2,…,tn}。將這些任務主要劃分為四種類型[17]：感知任務、計算任務、通信任務和智能任務。每個任務只屬于其中一種類型，每種類型的任務數量不相同。假設任務在分配之前是已知的，并且在執行過程中是不變的。

2.2 任務分配模型

任務分配的目的是對邊緣節點資源的合理使用，使得整體邊緣計算節點的任務收益最大化。如果任務被邊緣計算節點執行，那么用戶需要支付相應的費用。因此，邊緣節點完成用戶任務的處理能夠得到相應的收益。考慮單個任務的收益，主要由兩部組成：任務回報和任務成本。構造任務收益函數，如下所示：

其中，Pij表示邊緣計算節點i完成任務j的收益，Rj表示邊緣計算節點完成任務j的回報，Cij表示邊緣節點完成任務j的成本。

將邊緣計算節點與任務的映射關系定義為一個匹配矩陣A={aij}，其中aij∈ {0,1}表示邊緣計算節點i與任務j的匹配關系。當aij=1，表示邊緣計算節點i贏得投標，執行任務j，否則，aij=0。

綜上所述，考慮以系統總體收益最大化的任務分配模型，具體如下所示：

其中，約束條件1 表示每個任務必須分配給一個邊緣計算節點，約束條件2 表示每個邊緣計算節點至多執行一個任務，約束條件3 表示對任務與邊緣節點的匹配策略約束。

3 基于拍賣算法的任務分配方法設計

本節將介紹一種基于拍賣算法的任務分配方法，通過利用拍賣算法實現任務的最優分配。

拍賣算法本質上是各個拍賣參與者根據自身利益，依次對商品進行報價，通過多個輪次的競標，最終得到相對滿意的商品。基于拍賣的算法機制，將任務分配過程定義為動態拍賣過程。通過用戶任務與邊緣節點的動態拍賣過程，實現用戶任務的合理化分配。

在基于拍賣算法的任務分配方法中，需要3 種角色的參與：第三方拍賣商、購買者和出售者。第三方拍賣商主要負責拍賣過程，確定任務最終的分配；購買者主要負責向拍賣商遞交投標，投標成功的邊緣計算節點，被拍賣商授予任務；出售者主要負責向拍賣商提交任務，讓拍賣商負責任務的分配。

在所建立的模型中，任務分配系統作為第三方拍賣商通過無線通信等方式發布每個任務的任務信息，給予完成任務的中標邊緣計算節點一定的任務獎勵，其目標是最小化自身的成本。邊緣節點作為投標者收到系統公布的任務信息后，根據當前狀態和資源能力計算效用值，以最大化效益為目的進行任務投標。通過對每個任務的優化分配，從而實現整個系統的任務分配。對任務分配系統而言，每輪選擇哪些投標者作為中標者是任務分配策略。對于邊緣計算節點ni而言，每輪選擇哪個任務投標ti是其投標策略，其中i∈N。假設在拍賣過程中，邊緣計算節點都是自私而理性的。本文建立邊緣計算節點的基于拍賣的任務分配模型，主要包括三部分：投標策略、任務匹配和激勵機制。

3.1 投標策略

在投標過程中，每個收到任務信息的邊緣計算節點，根據任務信息計算每個任務的收益。在每輪拍賣過程中，邊緣計算節點根據任務的收益選擇競標，選擇收益最大的任務進行投標。

本文采用的最大效用投標策略相比于平行拍賣算法[18]，通過計算任務效用，邊緣計算節點選擇競標效用最大的任務。這樣做的好處是能夠保證邊緣計算節點的效用。同時，在第三方拍賣商決定最后的中標者，無論是哪個邊緣計算節點中標，對于中標的邊緣計算節點而言，都是效用最大的。相較于平行拍賣算法的投標方式，由于按照出售方的最大化效用進行分配，可能出現出售方與購買方的利益不一致，這樣會導致中標的邊緣計算節點所被分匹配的任務不是自身效用最大的任務。

3.2 任務匹配

當所有參加拍賣的邊緣計算節點確定競拍對象，完成投標后，則啟動任務匹配。任務最終的分配也是邊緣計算節點的匹配問題，其目標是確定一個邊緣計算節點執行相應的任務。

在競標過程中，某個任務存在多個邊緣計算節點參與競標。換句話說，在邊緣計算節點完成競標后，拍賣商需要進一步選擇邊緣計算節點，確定最終任務的分配。此時，選擇權發生變化，不再是買方選擇賣方，而是賣方選擇買方。在確定任務的最后分配中，定義了智能分配性價比Eij，具體如下：

其中，Qi表示邊緣計算節點i的資源能力，w1和w2是相應的權重系數。從上式可以看出，拍賣方不僅考慮了邊緣計算節點的成本，而且考慮邊緣計算節點的能力。

從上述過程可以看出，在相同出價條件下，賣方更愿意選擇邊緣計算較高的邊緣計算節點作為任務的執行者。未被選中的邊緣計算節點進入競標失敗者集合，等待下一輪拍賣的開始。

當確定本輪任務的分配，本輪拍賣立刻結束并按照拍賣結果為邊緣計算節點進行分配任務，然后進行下一輪拍賣，直到所有任務都被拍賣完成或者所有邊緣計算節點退出拍賣。

3.3 激勵機制

為了鼓勵邊緣計算節點在競標過程中提交真實的競標價格，需要設計相應的支付規則。支付規則的確定對拍賣有著至關重要的影響，一套合理的支付規則能夠保證拍賣的合理性，保證拍賣的激勵相容，起到正面促進的作用。考慮到邊緣計算節點的出價策略，采用Vickrey拍賣[19]機制作為最終的定價。Vickrey 拍賣也稱為次高價拍賣，其核心思想是拍賣商選擇第二高的出價作為最終的支付價格。通過Vickrey 拍賣方法，邊緣計算節點的競標過程中能夠提供真實的競標出價。

3.4 算法流程

本文設計的任務分配方法主要基于在線拍賣的方法實現，具體流程如圖2 所示。首先，第三方拍賣商會創建一個用戶集合用來收集邊緣計算節點的信息；然后，整體系統會將相關任務信息提交給第三方拍賣商，第三方拍賣商廣播相關任務信息；其次，邊緣計算節點收到相關任務信息開始競標，向第三方拍賣商提交出價；最后，第三方根據邊緣計算節點的競標信息，進行任務分配。基于拍賣算法的任務分配方法偽代碼如下所示：

圖2 基于拍賣算法的任務分配流程圖

3.5 算法分析

在設計基于拍賣算法的任務分配方法中，出售方先向第三方拍賣商遞交任務，并廣播任務信息；然后，邊緣計算節點向第三方拍賣商提交任務競標；最后，第三方拍賣商收到邊緣計算節點的競標信息，進行任務的分配。

本文基于拍賣算法設計的任務分配方法，符合有效的拍賣機制，具體如下。

（1）個人合理性：每個競標成功的邊緣計算節點獲得的回報都大于其成本，這意味每個邊緣計算節點的效用都非負的；

（2）效率性：基于拍賣算法的任務分配方法包括投標策略、任務分配和激勵機制，能夠完成任務的有效分配；

（3）激勵相容：任何邊緣計算節點都不能通過提交不同于其真實成本的報價來提高其利潤。

4 仿真實驗與結果分析

為了驗證本文算法的可行性和有效性，進行了不同情況下的仿真實驗。假設在網絡區域內，邊緣計算節點的數量為12～32。邊緣計算節點的綜合能力和成本取值相同，隨機分布在數值范圍為[10,20]。每個任務的回報取值范圍在[20,30]。為了進一步分析算法的優劣性，選擇第一價格拍賣、第二價格拍賣和不考慮節點資源能力的情況進行實驗對比，具體實驗結果如下所示。

通過分析圖3 可知，在任務數量逐漸增加的情況下，本文提出拍賣算法和其他拍賣算法所產生的任務分配收益都穩步增加。在給定任務數量范圍相同的情況下，本文提出的拍賣算法所獲收益值要高于其他拍賣算法的任務分配方法，算法的性能表現更好。其中，基于第一價格拍賣算法的任務分配方法所獲得的收益最小，這是因為第一價格拍賣算法的中標取決于最高價，所以獲得的任務收益最少。

圖3 不同任務數量下的任務分配收益

由圖4 可知，隨任務數量的增加，本文所提出的拍賣算法和其他分配方法的性能值都不斷增加。在相同任務數量的情況下，本文所提出的算法完成任務分配后的所取得任務總性能值均高于基于其他拍賣算法的任務分配方法。這是因為在任務分配過程中不僅考慮了節點的競價，而且考慮了節點的資源能力。

圖4 不同任務數量下的任務總性能值

綜合圖3 和圖4 來看，本文所提出的拍賣算法，在不同用戶數量下的總體收益和總體性能值均優于其他拍賣算法的任務分配方法。通過對比，充分體現了本文所提出的拍賣算法性能優異、表現穩定等優勢，能夠高效完成分布式計算任務的有效分配，平衡各邊緣計算節點間的競爭關系，保證每個邊緣計算節點的效能，以獲得總體上更好的性能。該算法能夠適應多節點協同和分布式場景下的資源和任務分配需要，從而有效應對分布式網絡環境和形勢的動態發展變化。

5 結束語

本文針對6G 分布式網絡環境下的任務分配問題展開研究，定義了多邊緣計算節點任務分配問題，制定了任務分配模型，并提出了一種基于拍賣算法的任務分配方法。考慮邊緣節點之間的相互競爭，通過應用拍賣的方式對任務進行合理分配。在任務分配過程中不僅考慮任務的成本，而且考慮邊緣計算節點的資源能力，提高了任務分配任務的合理性。通過實驗仿真，結果表明該方法的有效性，能夠實現分布式環境下任務的有效分配。