[發明專利]面向邊緣計算的車輛任務卸載的集中式調度方法與系統

有效

• 申請號: 202110694312.7
• 申請日: 2021-06-22
• 公開（公告）號: CN113377516B
• 公開（公告）日: 2022-10-25
• 發明（設計）人: 唐潔;朱韋琳
• 申請（專利權）人: 華南理工大學
• 主分類號: G06F9/48
• 分類號: G06F9/48
• 代理公司: 廣州市華學知識產權代理有限公司 44245
• 代理人: 馮炳輝

1.面向邊緣計算的車輛任務卸載的集中式調度方法，其特征在于：該方法根據中心調度服務器實時收集車輛任務信息并實時更新邊緣服務器信息的特點，提出擴展婚姻匹配算法和基于現代投資組合理論的任務卸載評估模型，完成車輛任務和邊緣服務器的匹配，其包括以下步驟：

S1、車輛用戶向中心調度服務器發出任務卸載請求，并提供自身的移動性信息和車輛任務的要求；中心調度服務器實時更新所有邊緣服務器信息；

S2、中心調度服務器根據收集到的車輛用戶信息和邊緣服務器資源信息計算出兩種偏好列表，一種是與邊緣服務器收益相關的車輛任務偏好列表，另一種是與車輛任務服務質量相關的邊緣服務器偏好列表；兩種偏好列表分別是邊緣服務器對車輛任務的偏好列表和車輛任務對邊緣服務器的偏好列表，包括以下步驟：

S21、保證車輛用戶有充足時間卸載任務數據到邊緣服務器，計算滿足最低時延要求的邊緣服務器集合；

有的邊緣服務器距離車輛用戶遠，有的邊緣服務器不在車輛用戶的行駛方向上，有的邊緣服務器覆蓋范圍小，據此需要計算出每個車輛用戶的可卸載邊緣服務器集合；根據車輛用戶和邊緣服務器的位置和方向，計算車輛用戶在邊緣服務器覆蓋范圍內的停留時間，停留時間大于車輛用戶的任務數據上傳所需時間，任務才能夠卸載到這個邊緣服務器，該車輛用戶所有能夠卸載的邊緣服務器集合就是A_n；

S22、針對任務被接收處理的概率，提出關于任務緊迫程度的度量；

對于同一個邊緣服務器來說，不同車輛的任務需要被完成的緊迫程度不一樣；有的車輛任務最大時延寬松，或者車輛距離邊緣服務器近能夠立即卸載任務，這些車輛任務能夠有充足的時間執行任務；而有的車輛任務執行時間緊迫，或者車輛距離邊緣服務器有一段距離，使得該車輛的任務卸載到邊緣服務器時，邊緣服務器資源很可能被別的任務搶占，造成車輛任務無法在時延內完成；即車輛用戶的任務卸載請求傳到某一邊緣服務器，不一定被該邊緣服務器接收處理，因此車輛任務卸載到一個邊緣服務器被接收處理的概率影響著用戶服務體驗；針對任務被接收處理的概率，提出關于任務的緊迫程度的度量；根據任務最大時延為標準，以任務到達邊緣服務器立即執行后，距離最大時延的剩余時間占最大時延的比例來表示任務的緊迫程度K：

式中，Td是車輛任務允許的最大時延；T_ex是任務在邊緣服務器上的執行時間；其中w表示任務工作負載，f是邊緣服務器的CPU執行功率；

式中，T_c是任務到達邊緣服務器的時間，包括車輛行駛到邊緣服務器覆蓋的可卸載范圍的行駛時間T1和任務傳輸到邊緣服務器的上傳時間T2；其中行駛到邊緣服務器覆蓋的可卸載范圍內的路程信息d能夠通過GPS獲得并計算，v是車輛行駛的速度，則任務上傳中，傳輸速率為B是信道帶寬，p是上傳功率，h是信道增益，是白噪聲功率電平，da表示任務數據量大小，傳輸時間因此，T_c能夠表示為：

因此，任務在邊緣服務器上的緊迫程度為：

S.t.0≤K≤1

其中，0≤K≤1表示保證任務在最大時延內完成；

在車輛行駛的道路范圍上分布著邊緣服務器，其中滿足車輛用戶i任務的最低時延要求的邊緣服務器集合能夠計算出車輛用戶i的任務在邊緣服務器集合上的任一邊緣服務器j上的任務緊迫程度K_i,j；則車輛用戶i的任務在邊緣服務器集合上的任一邊緣服務器j上的任務緊迫程度等級表示為：

其中n表示集合中邊緣服務器的數量，K_i,g表示車輛用戶i的任務在邊緣服務器g上的任務緊迫程度；

將任務的緊迫程度引入到邊緣服務器任務調度上，任務在邊緣服務器上開始執行的緊迫度越大，則任務調度調整越靈活；在多個任務競爭邊緣服務器執行區間時，緊迫度越大的任務越容易被邊緣服務器接收安排；對于車輛用戶來說，在緊迫度小的邊緣服務器上，車輛任務很容易因為任務需要的邊緣服務器資源被別的任務搶占，而導致任務無法在時延內完成；因此車輛用戶會更傾向于在緊迫度大的邊緣服務器上優先申請執行任務卸載；

S23、車輛任務在邊緣服務器上執行耗費的服務器成本；

任務在邊緣服務器上占用的時間能夠表示任務對邊緣服務器資源的需求量，即邊緣服務器執行該任務的成本；一個邊緣服務器上會有多個車輛任務按順序執行，每個任務耗費服務器的成本是不一樣的；假設一個邊緣服務器j上有m個車輛任務按順序執行，則對于車輛用戶i任務，邊緣服務器j需要付出的成本C_i^j能夠表示為：

S.t.C1:

其中表示車輛用戶i任務在邊緣服務器j上執行的時間，H_j表示邊緣服務器j在該輪調度中能夠用的總計算資源；式子C1表示在該輪調度中，在邊緣服務器上執行的任務不會超過邊緣服務器最大負載；

車輛用戶i任務在一個邊緣服務器j上耗費的服務器成本為

S24、與邊緣服務器收益相關的車輛任務偏好列表；

邊緣服務器對車輛用戶進行打分，根據打分對車輛用戶進行排序以給定優先級，并按照優先級得出邊緣服務器對車輛的偏好；打分標準根據車輛任務定價、邊緣服務器成本及能夠執行邊緣服務器的數量；邊緣服務器j對于車輛用戶i的任務評分函數為：

其中，Prⁱ是車輛用戶i愿意支付的價格，表示車輛用戶i任務在邊緣服務器j上執行需要的邊緣服務器成本，是車輛用戶i的能夠執行邊緣服務器集合中所有服務器數量，η₁、η₂、η₃是三項評分指標的比重；

邊緣服務器希望收益最大，更偏愛出價高的車輛任務，即車輛任務定價越高優先級越高；邊緣服務器同樣考慮成本問題，任務在邊緣服務器上占用的時間就是邊緣服務器的成本；邊緣服務器在任務時延內完成的任務數量越多收益越大，因此對于一個車輛任務來說，滿足任務時延的邊緣服務器數量少的，應給予高的優先級；車輛得分越高，邊緣服務器給定的優先級越高，偏好越高；

S25、與車輛任務服務質量相關的邊緣服務器偏好列表；

車輛任務會更傾向處理能力強的邊緣服務器，導致處理能力強的邊緣服務器負擔過多任務，處理能力弱的邊緣服務器資源空閑的情況；為了整體邊緣服務器負載均衡，避免資源利用率低的情況，需要時刻考慮邊緣服務器資源均衡狀態B_state；某一階段邊緣服務器j的剩余可用計算資源表示為其資源均衡狀態表示為：

式中，表示所有的邊緣服務器剩余可用計算資源之和，表示任意一個邊緣服務器Φ的剩余可用計算資源，共有s個邊緣服務器，Φ＝1,2,3,...,s；

車輛對邊緣服務器的偏好集合是不斷更新的，在每一階段都需要計算新的偏好集合；提出了車輛用戶i對于邊緣服務器j的實時打分函數為：

其中，是車輛用戶i任務在邊緣服務器j上的任務緊迫程度的倒數；α≥0，是對邊緣服務器資源均衡狀態的重視程度，其中α＝0，表示不考慮服務器資源均衡狀態；

S3、中心調度服務器利用提出的擴展婚姻匹配算法，對車輛任務和邊緣服務器進行匹配；在每一輪匹配中，考慮到不同任務的權重以及計算資源利用率，提出一個任務篩選算法，對邊緣服務器上申請卸載的任務進行篩選和執行安排；

S4、對于邊緣服務器資源負載均衡的不同重視程度下的多個任務調度方案，中心調度服務器利用提出的一個基于現代投資組合理論的任務卸載評估模型，以平衡邊緣服務器收益和車輛任務時延風險，確定最終車輛任務調度方案；

S5、中心調度服務器確定最終車輛任務調度方案后，將方案發送給車輛用戶，車輛用戶根據中心調度服務器的方案將車輛任務卸載到相應的邊緣服務器執行，或者因為無法接受該調度方案下的任務時延而選擇提高自身任務出價參與下一輪邊緣服務器資源調度競爭。