車輛霧計算中基于反向拍賣的停車輔助方案

朱蘭婷,孫麗珺,閆 楊

(青島科技大學 信息科學技術學院,山東 青島 266061)

0 概述

隨著智能連接設備數量的增加,智慧城市、5G網絡、車聯網以及無線傳感器網絡中的數據呈現爆炸式增長[1-2]。霧計算將云計算的彈性資源從云數據中心擴展至網絡邊緣,緩解了網絡擁塞現象并縮短了服務響應時間[3-4]。車輛霧計算(Vehicle Fog Computing,VFC)作為霧計算的一種擴展模式,將霧計算與傳統的車載網絡相結合,設置車輛作為通信和計算的基礎設施,利用靠近用戶的邊緣設備提供實時響應服務,從而大幅提高了服務質量[5]。

傳統的車載網絡部署路側單元(Road Side Units,RSU)為移動終端提供服務。隨著服務請求的增加,RSU的數據處理壓力不斷提高[5]。此外,人口數量的增加和城市空間資源的限制,導致了嚴重的城市停車問題。許多城市的交通堵塞是由于車輛尋找停車位所造成,智能停車輔助可以節省用戶搜索車位的時間,如自動泊車系統可以為駕駛員提供實時停車導航服務[6-7],從而緩解交通擁堵現象。將VFC與智能停車輔助相結合,選擇一些具有霧計算能力的智能車輛作為基礎設施,與移動的車輛用戶進行信息交換和共享,可以改善交通狀況。

在VFC中,充當霧節點的智能車輛等設備具有資源有限性、分布性等特點,為VFC的發展帶來挑戰[8]。在一個地理區域內的各霧節點構成一個車輛霧網絡,各節點分布廣泛,實現霧計算資源的合理分配存在一定難度。如何利用霧節點為用戶提供服務,使節點資源得到充分利用,成為亟待解決的問題[9-10]。此外,雖然霧節點可以獨立地為用戶提供低延遲服務,但其與云數據中心相比能力有限[11]。VFC需要不同的霧節點提供服務,霧節點在貢獻資源的同時會花費一定的成本。因此,需要建立激勵機制,激勵霧節點持續穩定地貢獻資源,進一步提高服務質量[12-13]。

本文提出一種基于反向拍賣的VFC停車輔助分配策略RAFC,以幫助用戶獲取停車信息資源。由于反向拍賣可以使市場更具競爭力,有助于買方以最優惠的價格得到服務[14],因此在智能車輛霧計算能力相對有限的條件下,本文將VFC智能停車輔助與反向拍賣相結合,激勵霧節點貢獻資源,使更多的用戶以更低的價格獲得服務,從而緩解交通壓力。

1 相關工作

拍賣機制以投標方式來分配商品,建立相應的價格體系以實現資源的有效配置。傳統拍賣由賣方提供待售商品,買方進行競價,價高者得。而反向拍賣由買方提出購買需求,賣方進行報價,出價最低且滿足買方需求的賣方競標成功。在VFC停車輔助系統模型中,買方是欲獲得停車信息資源的車輛用戶,賣方是提供待售資源的智能車輛,拍賣代理是第三方平臺。由拍賣代理決定拍賣分配并宣布拍賣結果。

為充分調動參與者的積極性以實現資源合理分配,將經濟分析和定價模型與網絡資源分配相結合,可以更好地在社會效用、用戶滿意度、匹配成功率等方面發揮作用。因此,基于拍賣的分配策略得到越來越多的關注。文獻[15]提出一種基于反拍賣模型的激勵方法,針對反拍賣可解決用戶退出和預算平衡問題的優點,對模型中涉及的任務覆蓋、反拍賣選擇和獎勵實施等關鍵技術進行深入分析與研究。文獻[16]研究群智感知中單任務場景下的激勵機制,采用反向拍賣方式,提出一種基于區域覆蓋的群智感知激勵機制,以提高區域覆蓋率和用戶參與度。文獻[17]針對邊緣網絡的資源有限性問題,提出基于拍賣的資源分配方法。在霧計算的資源分配問題中,文獻[13]針對支持VFC的智慧城市,提出一種通過資源定價影響車輛路徑選擇的激勵方案,以減輕資源需求的地理不平衡性,但其沒有考慮提高用戶的匹配成功率。文獻[18]建立一種Stackelberg博弈模型,解決服務運營商的定價以及用戶的資源購買問題。文獻[19]將區塊鏈與云/霧計算服務相結合,建立基于拍賣的市場模型,以提高資源分配率和區塊鏈網絡的社會福利,但其未研究應用的時延性問題。

目前,部分研究人員將反向拍賣與網絡資源分配相結合,但未將反向拍賣與VFC停車輔助問題進行聯系,也未考慮用戶的時延和成本問題。本文提出一種RAFC策略,考慮車輛用戶的時延和成本需求,將提高用戶匹配成功率和降低用戶開銷成本作為優化目標,激勵用戶和霧節點積極參與分配。

2 VFC停車分配問題建模

2.1 問題描述

如圖1所示,在一個地理區域內,一個VFC停車輔助系統由需要獲得停車信息資源的車輛用戶U={u1,u2,…,um}、充當霧節點的智能車輛F={f1,f2,…,fn}以及第三方平臺物聯網提供商三部分組成[20]。其中,用戶作為買方,提交時延要求、資源需求,霧節點作為賣方,提供資源服務,第三方平臺擔任拍賣代理,負責接收信息和協調分配。本文假設各用戶相互獨立,一個用戶請求最多只能遷移至一個霧節點完成,但一個霧節點可以接收處理多個請求。

圖1 VFC停車輔助系統模型

在物聯網中,通常將一個較大區域劃分成若干獨立子區域,一個子區域內的霧節點構成一個霧網絡。本文考慮在一個車輛霧網絡內,由第三方平臺搜集信息,將霧節點資源提供給需求用戶。本文符號說明如表1所示。

表1 符號說明

2.2 問題建模

本文RAFC策略在滿足用戶時延要求的基礎上,最小化用戶的開銷成本并提高匹配成功率。用戶、霧節點和第三方平臺的三方交互關系如圖2所示。

圖2 三方交互關系示意圖

在圖2中,①表示用戶ui∈U將請求Qi=(qi,Di)提交給第三方平臺,霧節點fj∈F將資源量和資源單價信息Lj=(dj,Aj)提交給第三方平臺;②表示第三方平臺根據提交的信息確定分配方案,將結果通知雙方;③表示拍賣成功的用戶支付費用給霧節點和第三方平臺,霧節點支付代理費給第三方平臺。

RAFC策略的目標包括:

1)實現個人理性和預算平衡。

2)激勵三方積極參與分配。

3)滿足用戶的時延要求和資源需求。

4)提高用戶的匹配成功率。

5)降低用戶的開銷成本。

2.3 效用函數

2.3.1 用戶的效用函數

(1)

收益函數Ui(qi)表示ui的請求響應后可獲得的收益,qi表示ui的資源需求量,Ui(qi)可表示為:

Ui(qi)=alb(1+qi)

(2)

參數a計算如式(3)所示,a∈[1,2],其取值與用戶需求有關,a值越大,表示資源需求越緊急。

(3)

開銷成本函數Pi(qi)表示ui獲得資源后應支付的費用,包括ui向提供資源的霧節點支付的費用、轉發費用以及支付給第三方平臺的代理費。Pi(qi)表示為:

(4)

為激勵用戶積極參與分配并支付費用獲取服務,應滿足用戶可獲得的資源收益大于成本支出,即Ui(qi)>Pi(qi)。

2.3.2 霧節點的效用函數

(5)

2.3.3 第三方平臺的效用函數

(6)

3 RAFC策略

3.1 目標函數

RAFC策略將VFC停車輔助與反向拍賣相結合,制定分配方案,以最大化用戶匹配成功率同時最小化其開銷成本。RAFC策略的目標函數定義為:

(7)

(8)

s.t.

xij∈{0,1}

(9)

(10)

(11)

Ui(qi)>Pi(qi)

(12)

(13)

(14)

(15)

式(7)表示滿足用戶請求,實現匹配成功率最大化。式(8)表示最小化用戶開銷成本。約束條件式(9)的xij表示霧節點fj的資源分配給用戶ui是否成功,xij=0表示未分配成功,xij=1表示分配成功。約束條件式(10)表示ui成功分配的資源量小于或等于參與分配的fj提供的資源量。約束條件式(11)表示分配成功的ui數目小于或等于提出請求的ui數目,約束條件式(12)表示ui獲得收益大于支出成本。約束條件式(13)表示fj的轉發收益大于轉發成本。約束條件式(14)表示fj的資源服務收益大于資源成本與代理費之和。約束條件式(15)表示第三方平臺獲得的代理費大于支出成本。

上述目標函數屬于多目標優化問題,可以將多目標優化轉換為單目標優化問題來解決。最大化ui的匹配成功率可轉換為最小化ui的匹配失敗率。將目標函數式(7)、式(8)轉換為單目標函數,可表示如下:

(16)

3.2 RAFC策略設計

整數規劃可以將3.1節的目標函數問題簡化為0-1規劃問題,但0-1規劃問題已經被證明是一個NP問題。本文提出RAFC策略來近似求解NP問題,該策略分為節點篩選階段和資源匹配階段。

3.2.1 節點篩選階段

本文在Dijkstra算法[21]的基礎上進行改進,提出一種節點篩選算法,將最短路徑問題與用戶的時延和成本需求相結合,目的是找到滿足用戶時延要求和最低成本需求的候選霧節點集合Fc。首先,計算各霧節點之間的最短路徑,尋找滿足用戶時延要求的霧節點集合,不滿足條件的霧節點不再參與下一階段。然后,計算用戶的開銷成本,將成本最低的霧節點作為候選霧節點。節點篩選算法具體流程如算法1所示。

算法1節點篩選算法

輸入U,F,W

輸出Fc,Pi

1.Initialize: Fc←?;Pi←?;int i.j;

//Find the feasible shortest path that can meet the latency //requirement

2.for each ui∈U

3.for each fj∈F

6.Fc←Fc∪{fj};

7.end

8.end

9.for each ui∈U

10.calculate Pi(qi) for each fj∈Fcby formula(4) to find the lowest fj

11.Pi←Pi(qi)

12.end

13.return Fc, Pi

//Output the candidate fog node set,and minimum cost

3.2.2 資源匹配階段

算法1為用戶找出候選霧節點集合Fc,反之,每一個霧節點都存在候選用戶集合。本文在貪心算法[22]的基礎上進行改進,提出一種資源匹配算法。將候選用戶集合的資源需求按升序排列,每次完成分配后更新霧節點信息。若節點資源不能滿足剩余候選用戶的需求,停止分配該節點,再分配下一個節點,直到霧節點和用戶全都分配完成,得到成功分配的用戶集合Uw和霧節點集合Fw,算法結束。資源匹配算法具體流程如算法2所示。

算法2資源匹配算法

輸入Fc

輸出Uw,Fw

1.for each fj∈Fc

//User resource requirements are sorted in ascending order

2.sort qifor all ui∈U in the ascending order and the list is denoted Fc

3.if dj≥qi

4.Uw=[Uw,m]

//Update the set of users that have been assigned

5.dj=dj-qi;

//Update the amount of resources of the fog node fj

6.Else

7.break

//Processing the next fog node if the user resource //requirement is not met

8.End

9.return Uw, Fw

4 理論分析

本節首先從拍賣機制的經濟屬性角度進行分析,證明RAFC策略的算法是個人理性、預算平衡的,可以持續地激勵三方積極參與拍賣。然后,分析算法的時間復雜度,證明該算法具有可執行性并且可以在有限步驟內實現。

4.1 個人理性分析

定理1本文RAFC策略是個人理性的。

4.2 預算平衡分析

定理2本文RAFC策略是預算平衡的。

4.3 算法的時間復雜度分析

定理3RAFC策略的時間復雜度為多項式時間。

證明RAFC策略分為節點篩選階段和資源匹配階段兩部分。對于節點篩選階段,算法1中第2行～第8行的時間復雜度為O(mn),第9行～第11行的循環時間復雜度為O(m)。因此,算法1的時間復雜度為O(mn)+O(m),即算法1的時間復雜度為多項式時間。對于資源匹配階段,算法2中第1行～第8行的時間復雜度為O(|Fc|),第2行排序算法的時間復雜度為O(mlogam)。因此,算法2的時間復雜度為O(m|Fc|logam),即算法2的時間復雜度為多項式時間。綜上,本文RAFC策略的時間復雜度為多項式時間。

5 數值結果分析

5.1 參數設定

本文采用MATLAB仿真平臺驗證RAFC策略的可行性,將CRB數量定義為VFC網絡資源的單位。首先,定義所需的基本仿真參數。假設霧節點有5個～40個,用戶數目有10個～150個。用戶的資源需求量在2～12之間隨機選取,霧節點的資源量根據用戶資源需求量和用戶數目在10～200之間隨機選取。霧節點單位資源報價在1～10之間隨機選取,用戶的最大允許時延在0.1 s～0.3 s之間隨機選取。

實驗性能指標包括運行時間、匹配成功率、開銷成本、社會效用4個方面,通過50次實驗比較得到平均結果。同時,為驗證RAFC策略的性能,將該策略與隨機匹配法進行比較,隨機匹配法隨機分配用戶,若滿足用戶需求即完成匹配。

5.2 仿真結果分析

當霧節點數目和空閑資源一定時,用戶請求越多,方案的運行時間越長,開銷成本越高,匹配成功率越低。當請求數目一定時,霧節點的個數越多,匹配成功率越高。

圖3所示為霧節點數目等于10時2種方法的運行時間隨用戶數目的變化曲線。從圖3可以看出,隨著用戶數目的增加,2種方法的運行時間逐漸上升。當用戶數目相同時,由于RAFC策略需要對用戶的資源需求進行重新排序,更新霧節點信息,因此其運行時間高于隨機匹配法,但2種方法的運行時間相差不大,且RAFC策略的運行時間結果表明其可以快速實現。

圖3 2種方法的運行時間對比

圖4所示為用戶數目等于60時匹配成功率隨霧節點數目的變化曲線。從圖4可以看出,隨著霧節點數目的增加,匹配成功率逐漸升高。當霧節點數目少于15個時,RAFC策略的匹配成功率明顯高于隨機匹配法。但當霧節點個數多于15個時,隨著霧節點個數的增加,2種方法的匹配成功率相差不大,且都可以穩定在較高的值。當用戶數目恒定時,與隨機匹配法相比,RAFC策略可以提高匹配成功率。

圖4 匹配成功率1

圖5所示為霧節點數目等于10時匹配成功率隨用戶數目的變化曲線。從圖5可以看出,隨著用戶數目的增加,匹配成功率逐漸降低。當用戶數目相同時,RAFC策略的匹配成功率高于隨機匹配方法。當用戶數目少于70個時,2種方法的匹配成功率相差不大,但用戶數目大于70個時,匹配成功率出現較大變化,且當用戶數目為80個時,兩者差距最大,其后差距逐漸趨于穩定。由于RAFC策略的資源匹配階段采用了貪心策略,可以更快速地找到用戶匹配的局部最優解。當霧節點數目恒定時,與隨機匹配法相比,RAFC策略可以提高匹配成功率。

圖5 匹配成功率2

圖6所示為霧節點數目等于10時用戶的開銷成本隨用戶數目的變化曲線。從圖6可以看出,隨著用戶數目的增加,開銷成本逐漸增加。當用戶數目相同時,隨機匹配法產生的開銷成本高于RAFC策略,原因是RAFC策略考慮了用戶的最低成本需求且使用了貪心策略。當霧節點數目恒定時,與隨機匹配法相比,RAFC策略可以降低開銷成本。

圖6 2種方法的開銷成本對比

社會效用是指成功分配的用戶、霧節點及第三方平臺的三方收益總和。圖7所示為霧節點數目等于10時社會效用隨用戶數目的變化曲線。從圖7可以看出,隨著用戶數目的增加,社會效用逐漸增加。當用戶數目相同時,RAFC策略的社會效用高于隨機匹配法。RAFC策略結合了反向拍賣原理,激勵三方積極參與分配,且不損害三方的收益。當霧節點數目恒定時,與隨機匹配法相比,RAFC策略可以提高社會效用。

圖7 社會效用1

圖8所示為用戶數目等于60時社會效用隨霧節點數目的變化曲線。從圖8可以看出,隨著霧節點數目的增加,社會效用逐漸降低。當霧節點數目相同時,RAFC策略的社會效用高于隨機匹配法。當用戶數目恒定時,與隨機匹配法相比,RAFC策略可以提高社會效用。

圖8 社會效用2

6 結束語

本文研究VFC停車分配問題,提出一種基于反向拍賣的VFC停車輔助分配策略RAFC。該策略根據用戶需求和智能車輛的資源量來制定分配方案,激勵用戶、霧節點和第三方平臺積極參與拍賣。理論分析和實驗結果表明,RAFC策略在保證個人理性和預算平衡的基礎上,可以提高用戶匹配成功率,降低用戶開銷成本,提高社會效用。霧計算的網絡資源分配可廣泛應用于智能交通、智慧醫療、智能電網等新興領域,本文僅考慮車輛霧計算環境下的智能停車輔助問題,在實際應用中,需求具有多樣性,因此,下一步將研究當用戶有多種資源需求和時延要求時,如何利用車輛霧節點的計算、存儲等資源來制定更加高效的分配策略。