基于超模博弈的移動邊緣計算邊緣服務定價研究

楊桂松， 程 浩， 李 俊， 何杏宇

（1 上海理工大學 光電信息與計算機工程學院， 上海 200093； 2 國家工業信息安全發展研究中心， 北京 100040；3 上海理工大學 出版印刷與藝術設計學院， 上海 200093）

0 引言

隨著物聯網和移動設備的發展，移動邊緣計算［1－2］成為一種流行的計算范式。 在此范式中，計算和存儲資源被下放到網絡邊緣，為移動用戶提供高性能、低延遲的邊緣服務。 現有關于移動邊緣計算的研究主要集中在計算卸載和資源分配方面，很少有研究關注移動邊緣計算中交易方面的問題，目前還不存在一個通用的邊緣服務定價方法。

在移動邊緣計算中，邊緣服務提供商向移動用戶出售邊緣服務以支持其完成計算密集型任務［3－5］（如自動駕駛、大型交互式游戲等）。 這是因為移動用戶受自身移動設備限制，計算和存儲能力有限，不能獨立完成這些任務。 邊緣服務提供商將邊緣服務（包括計算服務、存儲服務等）封裝到一起出售給移動用戶來賺取收益。 而移動用戶購買邊緣服務來滿足自己相應的需求。

合適的邊緣服務定價方法不僅能提高邊緣服務提供商的收益水平［6］，也能改善移動用戶的體驗，這對促進移動邊緣計算范式的發展和應用有重大意義。 定價問題在移動邊緣計算相關領域已經有許多相關研究工作出現，包括網絡服務定價、動態定價和車聯網服務定價等。 文獻［7］根據網絡條件不斷調整網絡服務價格，將定價問題表述為成本最小化問題。 文獻［8］通過放寬多個約束條件，將具有挑戰性的定價問題轉化為線性規劃問題，提出一種動態定價策略。 文獻［9］提出了一種新的多用戶車輛輔助移動邊緣計算網絡動態定價策略。 也有一些研究工作考慮在不同價格和質量的網絡服務中進行選擇。 為了解決這一問題，文獻［10］和文獻［11］提出了一種拍賣機制，通過這種機制，網站服務代理可以自動選擇邊緣計算方案來支持其最終用戶。 在文獻［12］中，提出了一個利用邊緣服務的資源分配拍賣模型，允許代理根據其能量貢獻參與拍賣過程。

現有關于定價的研究沒有針對邊緣服務的特性設計一個適合邊緣服務的定價方法。 在移動邊緣計算中，如何根據移動用戶需求變化和邊緣服務提供商同行價格競爭制定最優邊緣服務價格是一個關鍵挑戰。 一方面，移動用戶需求與邊緣服務單價密切相關，邊緣服務提供商的邊緣服務市場需求受自身邊緣服務單價影響。 對于一個邊緣服務提供商而言，其他邊緣服務提供商定價一定時，其定價越高，邊緣服務市場需求越低；自身定價一定時，其他邊緣服務提供商定價越高，自身邊緣服務市場需求越高［13］。 除此之外，還需要考慮移動用戶的主觀因素，即部分移動用戶考慮其他因素而不改變原來的需求。 例如由于邊緣服務提供商的距離或信譽等因素，移動用戶不會因為價格變化而改變自身需求。另一方面， 邊緣服務提供商之間的同行價格競爭直接影響邊緣服務定價。 對手的邊緣服務定價越高，對自身越有利。 因此，每個邊緣服務提供商要充分考慮同行的報價來制定自身邊緣服務價格。 對于邊緣服務定價問題，邊緣服務具有可替代性和相異性，因此邊緣服務提供商之間存在價格競爭關系。 博弈論可以很好解決競爭關系下的定價問題［14－18］。

基于上述討論，為解決移動邊緣計算中的邊緣服務定價問題，提出一種基于超模博弈［19－20］的邊緣服務定價方法。 該方法主要從邊緣服務提供商的角度出發，在滿足移動用戶需求的前提下最大化邊緣服務提供商的收益。 首先，將邊緣服務定價過程建模成一個博弈模型，博弈的參與者是邊緣服務交易市場中的所有邊緣服務提供商。 參與者可以根據對手的邊緣服務定價策略制定對自己最有利的定價策略［21］。 然后，通過理論分析，證明了該博弈是超模博弈，從而論證納什均衡的存在性。 超模博弈表現為戰略互補性，這意味著當一個參與者采取更好的行動時，其他參與者也會效仿其行動。 超模博弈以格點理論和比較靜力學的數學理論為基礎，具有快速收斂的性質。 最后，為求解超模博弈的納什均衡，通過迭代近似的方法不斷逼近納什均衡，得到最優邊緣服務定價。 本文的主要貢獻總結如下：

（1）研究并提出移動邊緣計算中的邊緣服務定價問題，為邊緣服務交易市場繁榮提供支持。

（2）將邊緣服務提供商之間的邊緣服務定價過程建模成博弈模型，準確描述了邊緣服務提供商同行價格競爭關系和移動用戶需求對邊緣服務定價的影響。

（3）設計一種梯度迭代算法，求解超模博弈的納什均衡，解決了邊緣服務定價問題，在滿足移動用戶需求的前提下提高了邊緣服務提供商的收益。

1 系統描述

在移動邊緣計算中，邊緣服務交易過程是：邊緣服務提供商將邊緣服務打包出售給移動用戶，支持其完成計算密集型任務，以此賺取收益、即移動用戶支付的報酬，如圖1 所示。

圖1 邊緣服務交易過程Fig. 1 The process of edge services transaction

假定邊緣服務交易市場中有n家邊緣服務提供商，用E ＝｛e1，e2，...，en｝ 表示，其中，ei表示第i家邊緣服務提供商。 在邊緣服務交易中，邊緣服務提供商代表賣家，移動用戶代表買家。 邊緣服務以固定份額進行出售，其屬性包含單位成本和單位價格。 由于地理位置、計算和存儲能力大小等因素，不同賣家提供的邊緣服務單位價格和單位成本是不同的，用pi表示第i家邊緣服務提供商ei的邊緣服務單位價格，ci表示其邊緣服務單位成本，qi表示邊緣服務交易市場中所有移動用戶對ei的邊緣服務需求。 假定邊緣服務單價對市場需求的影響是線性的，即：

其中，αi為邊緣服務提供商ei能滿足邊緣服務交易市場的最大邊緣服務需求量；θi為ei自身需求價格系數，表示邊緣服務提供商ei的市場需求受自身邊緣服務單價影響程度；σij為邊緣服務提供商ei關于另一家邊緣服務提供商ej的需求價格系數，表示邊緣服務提供商ej的邊緣服務單價對邊緣服務提供商ei市場需求的影響。 明顯可知，αi，θi，σij＞0，i，j ＝1，2，…，n。 因此，邊緣服務提供商ei的收益yi可以計算為：

2 邊緣服務定價

2.1 博弈模型

在邊緣服務定價過程中，每家邊緣服務提供商在制定邊緣服務單價時不知道其他邊緣服務提供商的邊緣服務單價，只能在一次出價完成后，才能根據其他邊緣服務提供商的邊緣服務單價調整自身邊緣服務單價。 假定所有邊緣服務提供商不存在惡意競爭情況，也沒有部分邊緣提供商聯合出價以謀取更多收益的情況，每家邊緣服務提供商都處于公平競價地位。

根據上述特征，該邊緣服務定價過程可以被描述為非合作靜態博弈，即每個博弈參與者都是自主進行決策，與這個策略環境中其他參與者無關。 在博弈定價過程中每個邊緣服務提供商首先給出初始邊緣服務定價，然后根據對手定價調整自身定價，相互博弈直到定價達到納什均衡，得到最優邊緣服務定價。 此博弈過程充分考慮了邊緣服務提供商同行價格競爭和移動用戶需求，具體過程如圖2 所示。

圖2 博弈定價Fig. 2 Game pricing

一個通用的博弈模型包含3 個重要元素：參與者、策略和效用函數。 其中，參與者是指邊緣服務交易市場中的所有邊緣服務提供商ei（i∈n），策略指的是每個參與者的邊緣服務定價pi（i∈n）。 考慮到邊緣服務交易市場規律和移動用戶承受能力，所有邊緣服務提供商的邊緣服務定價只能在一定范圍內調整，即?i，i∈n，pi∈［pmin，pmax］。 效用函數指的是邊緣服務提供商的期望收益函數，可表示為Ui（P） （見后文公式（5）），P ＝｛p1，p2，…，pn｝，即參與者ei的效用Ui（P） 等同于參與者ei在所有參與者出價為P時的期望收益。 每個參與者調整自己的邊緣服務定價，使得自身效用最大化，最終得到最優定價，即定價的納什均衡，用P?＝｛，…，｝表示，其中pi?表示參與者ei的最優定價。

在邊緣服務交易市場中，大部分移動用戶主要考慮價格因素會隨著邊緣服務提供商調整價格而改變之前所選擇購買的邊緣服務提供商，同時其余移動用戶不會隨著邊緣服務提供商調整價格而改變之前所選擇的購買對象。 為了計算方便，假定前者占比為α（0＜α ＜1），后者占比為1－α。 因此，邊緣服務提供商ei的邊緣服務市場需求受市場上所有邊緣服務提供商的價格向量P和α的共同影響，可表示為：

公式（3）表達的含義是邊緣服務提供商ei的市場需求是由自身需求價格函數和剩余所有邊緣服務提供商的需求價格函數共同決定。α越大表示邊緣服務交易市場中受價格因素影響的移動用戶越多，邊緣服務提供商的市場需求受自身需求價格函數的影響越大，受其他邊緣服務提供商的需求價格函數影響越小。

此外，邊緣服務市場是動態且復雜的，存在一些突發狀況，比如某些社會事件（一款火熱的大型交互式游戲出現），使得移動用戶的邊緣服務需求增加或減少。 考慮市場需求的不確定性和不穩定性，對邊緣服務提供商的需求加上一個隨機擾動，可表示為：

其中，ξ為隨機擾動因子。 每家邊緣服務提供商會根據競爭對手當前定價策略，調整邊緣服務定價，以實現自身收益最大化。 將邊緣服務提供商ei的期望收益看作其效用，根據式（1）～式（4）可得：

2.2 博弈模型的超模性分析

為分析上述非合作靜態博弈的性質，對邊緣服務提供商（參與者）的效用函數進行分析，發現參與者之間的定價策略具有互補性，即參與者的最優反應對應關于對手的定價策略遞增。 而超模博弈為具有互補策略的博弈提供了一個一般解決方法，下面給出超模博弈的定義。

定義1 超模博弈對于一個集合S， 若其中任意2 個元素a和b的上確界都在S中，其中上確界記為a∨b，下確界記為a∧b， 則稱S為格子。從格子S到實數R的函數F， 即F：S→R， 若對于?a，b∈S，都有F（a）＋F（b）≤F（a∨b）＋F（a∧b），則稱F（a） 為S上的超模函數。

根據定義1 可知，超模博弈具有2 個明顯的特征：策略集S是R的子格，效用函數F關于自身和競爭對手的策略均是遞增差分的，即效用函數是策略集上的超模函數。 由2.1 節內容可知，每家邊緣服務提供商的定價范圍在實數范圍內是閉集，即pi∈［pmin，pmax］， 這表明其策略集是實數R的子格。 因此，只需證明其效用函數是策略集上的超模函數即可說明該博弈是超模博弈。 為了簡化邊緣服務提供商效用的表達形式，設計一個函數如下：

邊緣服務提供商ei的效用函數可簡化為如下：

對于邊緣服務提供商ei定價集合中的任意2 個定價pi和有：

由式（8）和式（9）可得：

此效用函數滿足定義1 的條件，因此該博弈為超模博弈，可表示為G ＝｛E，{pi}i∈n，{Ui}i∈n｝。 根據超模博弈的性質［13］可知，該博弈模型一定存在納什均衡，且納什均衡點唯一，也就是每個邊緣服務提供商都有唯一的最優定價。 求解最優定價可表示如下：

根據公式（11）可以求得每個邊緣服務提供商的最優定價，即定價的納什均衡P?。 由于每家邊緣服務提供商的定價彼此相互影響，很難根據聯立的n個方程（類似于式（11）的形式）直接求解納什均衡。 因此，本文考慮使用梯度迭代更新的方法，不斷迭代更新來逼近所有邊緣服務提供商定價的納什均衡。 具體求解過程見2.3 節。

2.3 梯度迭代更新算法設計

根據超模博弈的性質可知，超模博弈可以從任意初始值收斂到納什均衡。 由于邊緣服務提供商擁有的邊緣服務數量、提供邊緣服務的效率等均各不相同，每家邊緣服務提供商的初始定價也是不同的。所有邊緣服務提供商同時出價，不分先后。 為了實現定價快速收斂和充分考慮定價相互影響之間的均衡，每家邊緣提供商都按效用函數梯度的方向更新自身邊緣服務定價，可表示為：

其中，ε表示學習率，即調整定價的速率。 這里▽Ui（P） 可計算為：

根據邊緣服務定價的更新公式可以設計梯度迭代更新算法，所有邊緣服務提供商依次更新自身邊緣服務定價，直到邊緣服務定價達到穩定狀態，即定價的納什均衡。 由于本文的超模博弈考慮了移動用戶需求的影響，此博弈可能在某些特殊情況下（如邊緣服務交易市場中受邊緣服務價格因素影響的移動用戶占比過少）不能達到納什均衡。 這并不是違背超模博弈必定存在納什均衡的性質，因為在特殊情況下，邊緣服務提供商之間的定價過程可能不適用于建模成超模博弈，需要考慮更多的因素，建模成其它的博弈，如不完全信息博弈等。 梯度迭代更新算法的偽代碼如下。

算法1 梯度迭代更新算法

輸入初始定價向量P

輸出最優定價向量P?

1.參數初始化：最大邊緣服務滿足量ai，定價范圍pmin，pmax，自身需求價格系數θi，對手影響價格系數σij，邊緣服務單位成本ci，隨機擾動因子ξ，學習率ε等

2. while （change ofpi＞ 1e － 5 or iteration numbers ＜＝max）

／／價格變化幅度大于一個精度或迭代次數小于最大迭代次數

3.forifrom 1 ton／／所有邊緣服務提供商

4.根據式（13）計算梯度▽Ui（P）

5.ei根據式（12）調整自身邊緣服務單價

6.更新價格向量P

7.end for

8.end while

9.returnP?／／定價的納什均衡，即最優定價

3 實驗結果和分析

為評估所提邊緣服務定價方法的有效性，針對算法收斂性和邊緣服務提供商的收益等指標進行仿真。 仿真環境是Python 3.8。 在仿真實驗中，設置相關參數見表1。 參數設置的依據是邊緣交易市場的一般規律，比如邊緣服務提供商的市場需求受自身邊緣服務單價的影響比受其他邊緣服務提供商邊緣服務單價影響大，因此自身需求價格系數大于對手影響需求價格系數。

表1 仿真參數表Tab. 1 Simulation parameters

3.1 邊緣服務定價收斂性分析

首先分析僅受價格因素影響需求的移動用戶占邊緣服務交易市場不同比例時，所提算法是否能收斂，為每個邊緣服務提供商找到最優定價。 為了使仿真實驗具有一般性和普適性，本次仿真實驗采用控制變量法，通過一組對比實驗（6 次定價）來展示每家邊緣服務提供商的邊緣服務定價情況。 其中n ＝3，此仿真實驗中共有3 家邊緣服務提供商，所提供的邊緣服務是相互可替代的。

圖3 顯示不同受價格因素影響的移動用戶占比對梯度迭代算法收斂效果的影響。 其中，圖3（a）、圖3（b）和圖3（c）分別顯示α ＝0.9，α ＝0.7，α ＝0.5對算法收斂效果的影響。 可以看出當僅受價格因素影響的移動用戶占比大于等于市場一半時，該算法有很好的收斂效果，能找到定價的納什均衡點。 通過這3 張圖的對比可以發現，當α ＝0.9 時，3 家邊緣服務提供商的邊緣服務定價收斂是最快的，曲線也是最平滑的。 這表明所提算法在僅受價格因素影響的移動用戶占邊緣服務交易市場主體時有很好的收斂效果，可以實現快速定價。

而圖3（d）、圖3（e）和圖3（f）分別顯示α ＝0.4，α ＝0.3，α ＝0.2 對算法收斂效果的影響。 可以看出僅受價格因素影響的移動用戶占比小于市場一半時，算法越來越難收斂，最后呈現發散趨勢。 這表明本文設計的算法主要是針對邊緣服務單價對移動用戶需求和邊緣服務提供商的收益的影響，當價格不是影響移動用戶購買邊緣服務的主要因素時，不再適用。 通過這3 張圖的對比可以發現，圖3（d）和圖3（e）可以收斂，而圖3（f）直接呈發散趨勢，迭代次數到達限制的最大迭代次數。 這表明所提算法的普適性有限，不能針對受價格以外的因素來解決邊緣服務定價問題。 但這也從另一角度證明，當價格是影響移動用戶是否購買邊緣服務的主要因素時，所提算法可以很好解決邊緣服務定價問題。

圖3 算法收斂效果Fig. 3 Simulation of algorithm convergence effect

為直觀表示算法收斂情況，算法迭代次數見表2。 由表2 可以看出，當受價格因素影響的移動用戶占比越來越小，算法的迭代次數在增加，最后達到算法所設定的最大迭代次數。 這表明所提算法針對邊緣服務定價問題的有效性，當移動用戶主要根據價格而選擇是否購買邊緣服務時，所有邊緣服務提供商的邊緣服務定價均能達到穩定狀態。

表2 迭代次數表Tab. 2 Number of iterations

3.2 邊緣服務定價影響因素分析

為進一步研究影響邊緣服務提供商定價高低的因素，在α ＝0.8 的邊緣服務交易市場仿真環境中做了一組對比實驗。 在此邊緣服務交易仿真中，受價格因素影響的移動用戶占比為大多數。 由第1 節系統模型部分的分析可知，邊緣服務提供商受自身需求價格系數影響較大，因此考慮其最終的邊緣服務定價高低是受自身需求價格系數影響。 為了驗證這個猜想，在其他條件相同的情況下（除自身需求價格系數外使用表1 的參數），采用2 組不同的自身需求價格系數進行仿真實驗，結果如圖4 所示。

圖4（a）顯示3 家邊緣服務提供商的自身需求價格影響系數分別為θ1＝0.6，θ2＝0.5，θ3＝0.8 的邊緣服務定價情況。 可以發現邊緣服務提供商e2的自身需求價格影響系數最小，其最終邊緣服務定價最高，而邊緣服務提供商e3的自身需求價格影響系數最大，其最終邊緣服務定價最低。 圖4（b）顯示3家邊緣服務提供商的自身需求價格影響系數分別為θ1＝0.8，θ2＝0.6，θ3＝0.5 的邊緣服務定價情況。 可以發現與圖3（a）相似的結果，即邊緣服務提供商e3的自身需求價格影響系數最小，其最終邊緣服務定價最高，而邊緣服務提供商e1的自身需求價格影響系數最大，其最終邊緣服務定價最低。

通過圖4（a）和圖4（b）的對比可以得出以下結論，在相同的邊緣服務交易市場環境中，邊緣服務提供商自身需求價格影響系數越低，其最終邊緣服務單價越高，即邊緣服務定價高低與自身需求價格影響系數負相關。 在實際交易中，如果邊緣服務提供商所能出售的邊緣服務量受其自身價格影響較小，說明其邊緣服務相較于其他邊緣服務提供商的邊緣服務有優勢，比如邊緣服務質量高。 因此該邊緣服務提供商在博弈定價過程中具有優勢地位，其邊緣服務定價也就最高。 另一結論是邊緣服務提供商最終定價高低與其初始定價高低無關。 因為在圖4（b）中邊緣服務提供商e3的初始定價最低，最終定價卻最高，而邊緣服務提供商e2的初始定價最高，其最終定價卻不是最高。 這表明在實際定價過程中，邊緣服務提供商的初始定價方案是不合理的，僅根據自身情況給出初始定價，沒有考慮移動用戶的需求變化和同行的價格競爭。

圖4 自身需求價格影響系數圖Fig. 4 Self－demand price influence coefficient

3.3 邊緣服務提供商的收益分析

從邊緣服務提供商的角度分析所提出的定價方案對邊緣服務提供商的收益的影響，即在每家邊緣服務提供商調整邊緣服務單價時，其收益是如何變化的。 在3.1 節實驗的基礎上，本節實驗在α ＝0.8，θ1＝0.6，θ2＝0.5，θ3＝0.8 的邊緣服務交易市場仿真環境中觀察各家邊緣服務提供商的收益和所有邊緣服務提供商的總收益。

圖5 顯示3 家邊緣服務提供商的效用U1、U2和U3變化情況，即期望收益隨著邊緣服務定價的不斷調整而增加，最終趨于穩定。 這表明在博弈定價過程中，邊緣服務提供商之間在綜合考慮移動用戶需求和同行價格競爭影響，可以給出“最優反應”，最終制定出使自身收益最大化的邊緣服務單價。 值得注意的是，盡管每家邊緣服務提供商的定價都是呈上升趨勢，但這并不意味著其收益百分百呈上升趨勢，因為當邊緣服務提供商定價過高時，移動用戶可能會選擇購買其他邊緣服務提供商的邊緣服務。 每家邊緣服務提供商的收益隨著邊緣服務定價的調整都得到了一定程度的提升，這證明所提定價方法的有效性。

圖5 邊緣服務提供商收益Fig. 5 Profits of edge services providers

為進一步分析所提定價算法的優越性，將所提梯度迭代更新算法與隨機算法和貪婪算法相對比。隨機算法指的是各邊緣服務提供商根據各自邊緣服務的情況進行隨機定價，而不是通過博弈來進行定價。 貪婪算法指的是邊緣服務提供商在定價過程中沒有考慮移動用戶的需求，貪婪地選擇跟隨所有邊緣服務提供商中的最高價格作為自己的邊緣服務單價。 邊緣服務提供商收益對比如圖6 所示。 圖6 顯示，在3 家邊緣服務提供商e1、e2、e3的單獨收益方面，所提算法的收益更高；在3 家邊緣服務提供商的總收益方面，所提算法明顯高于另外2 種算法，這體現了所提算法的優越性。

圖6 邊緣服務提供商收益對比Fig. 6 The comparison of the profits of edge services providers

4 結束語

本文研究了移動邊緣計算中的邊緣服務定價問題，提出一種基于超模博弈的邊緣服務定價方法。該方法首先考慮邊緣服務提供商之間的定價影響、不同移動用戶對價格的敏感程度和邊緣服務交易市場中的不確定因素，設計合適的效用函數，計算邊緣服務提供商的效用。 然后，通過證明效用函數的超模性，論證該博弈定價納什均衡的存在性。 最后，設計一種梯度迭代更新算法，求解超模博弈的納什均衡找到最優邊緣服務定價。 結果表明所提算法在收斂速度和提升邊緣服務提供商收益的有效性。 在未來工作中，將考慮更復雜、更繁瑣的邊緣服務交易場景，探索更多針對不同類型邊緣服務的定價方法。