[發明專利]一種邊緣計算中基于博弈論的服務部署及任務卸載方法有效

申請號：	202010027936.9	申請日：	2020-01-10
公開（公告）號：	CN111163178B	公開（公告）日：	2021-03-30
發明（設計）人：	王子通;龔迎莎	申請（專利權）人：	中國地質大學（武漢）
主分類號：	H04L29/08	分類號：	H04L29/08;G06N5/04
代理公司：	武漢知產時代知識產權代理有限公司 42238	代理人：	易濱
地址：	430000 湖***	國省代碼：	湖北;42
權利要求書：	查看更多	說明書：	查看更多
摘要：
搜索關鍵詞：	一種邊緣計算基于博弈論服務部署任務卸載方法
鉆瓜網技術展會專利詞庫專利權人專利榜在售專利公布日期熱門專利

【權利要求書】：

1.一種邊緣計算中基于博弈論的服務部署及任務卸載方法，其特征在于：具體包括以下步驟：

S101：采用排隊論表示邊緣節點e請求服務s到達率為邊緣節點e的服務率為

S102：根據所述到達率和所述服務率計算邊緣節點時間開銷

S103：計算云端時間開銷

S104：根據所述邊緣節點的時間開銷和所述云端時間開銷計算總體開銷C(d)；

S105：構建兩階段的斯塔克爾伯格博弈模型，并根據所述總體開銷C(d)構建約束條件，求解兩階段斯塔克爾伯格博弈模型的離散解；

S106：采用剪枝算法在所述離散解中，找到納什均衡解；

步驟S103中，云端時間開銷計算式如式(2)：

式(2)中，c表示云端，表示用戶向云端請求服務s的到達率；τ_c為云端處理服務的平均完成時間；

步驟S104中，系統總體開銷C(d)的計算式如式(3)：

式(3)中，C_i(d_i)表示第i個服務請求的時間開銷，i表示服務序號，其中，i＝1,2,…,m，m為服務請求總數；表示根據部署策略d部署服務s的邊緣節點的集合，e_j表示部署了服務s的邊緣節點集合中的第j個邊緣節點，j＝1,2,…,k，k為部署了服務s的邊緣節點的總個數；δ表示所有的服務請求集合；和分別表示用戶向邊緣節點e請求服務i的時間和用戶向云端請求服務i的時間；

步驟S105中構建兩階段的斯塔克爾伯格博弈模型調整服務部署策略，通過相應約束條件，求解兩階段斯塔克爾伯格博弈模型的離散解具體為：

S201：斯塔克爾伯格博弈模型中，領導者為云服務提供商，跟隨者為用戶；第一階段中，所述云服務提供商確定服務部署策略d；

S202：第二階段中，根據第一階段確定的服務部署策略d確定計算任務的約束條件，如式(4)：

式(4)中，δ_e表示邊緣節點e上的服務集合；μ_e表示邊緣節點e的服務總處理能力；λ^s表示對服務s的總請求率；表示用戶向云端請求服務s的到達率；δ_e(d)表示根據部署策略d部署了在邊緣節點e上的服務集合；d表示服務s的部署策略，表示是否在邊緣節點e上部署服務s；若在邊緣節點e上部署服務s，則為1，否則為0；

S203：根據所述約束條件，利用拉格朗日乘子法，構建約束條件方程；

S204：利用所述約束條件方程，通過KKT條件，得到反應方程；

S205：利用所述反應方程的反向歸納方法，得到云服務提供商的離散解

步驟S203中，所述約束條件方程具體如式(5)：

式(5)中，α_e、β_e和γ_e均為拉格朗日乘子，且均為預設值；

步驟S204中，所述反應方程具體如式(6)：

式(6)中，表示除了邊緣節點e，請求其他部署服務s的邊緣節點的請求率之和；

步驟S106中，利用剪枝算法在所述兩階段斯塔克爾伯格博弈模型的離散解中，找到納什均衡解，剪枝算法具體步驟如下：

S301：利用所述兩階段斯塔克爾伯格博弈模型的離散解構造多叉樹t；獲取雙向隊列Q；初始化到達葉子節點標志rank＝1、多叉樹每層的節點數level＝0、下一層的節點數next_level＝0、服務請求率的序數num＝0；

S302：將所述服務請求率λ^s按降序排隊；

S303：將單過程部署策略入隊；

S304：判斷所述隊列Q是否為空，若是，所述單過程部署策略出隊，并到步驟S305；否則，跳轉至步驟S310；