0 引言

    車聯網VANET(Vehicular Ad Hoc Network)被認為是應用于未來智能交通系統最有前景的技術，其提供了多類的應用服務，增加了車輛行駛安全、提高了交通效率^[1-3]。在VANET中，為了使用多類應用，從接入Internet到安全應用，車輛與車輛或與路邊基礎設施交互數據。如圖1所示，VANET構成了兩類通信：車間通信V2V(Vehicle to Vehicle)和車與基礎設施通信V2I(Vehicle to Infrastructure)^[4]。

    在VANET中，行駛者(車輛)接入Internet是較常見的應用之一。車輛通過網關接入Internet^[5-7]。這些網關是靜態的、固定于道路旁邊的設備。如圖2所示，為了能夠使VANET間的節點進行通信，路邊設施RSU(Roadside Units)扮演著網關的作用，并且RSU具備WLAN網絡能力。為了接入Internet，數據包需經過車間的多跳通信，直到接入Internet。

    然而，由于VANET中車輛的高速移動，很難設計一個有效的路由算法能夠以合理的成本接入Internet。而且移動自組織網MANET的路由不再適用于VANET，研究人員針對VANET提出眾多的路由協議^[8-12]。

    本文從博弈Game理論入手，提出一個基于Congestion game的接入Internet的數學模型。利用博弈Game理論解決路由選擇問題。在博弈Game理論中，當實體的成功取決于系統中其他實體的決策時，博弈Game可作為一個最優的分析工具。為此，利用博弈Game理論提出一個新的模型，尋找到最優的路徑。

1 系統模型

    為了在VANET中應用博弈理論(Game theory)，首先介紹Game theory相關的概念，并與VANET相對應。用VANET 中的車輛扮演參與者(Player)，Player采取的策略與應用函數相關。VANET網絡的服務質量表示博弈理論中的效用函數(成本函數)。

1.1 場景描述

    沿著道路有固定的RSUs作為Internet的接入點。車輛以隨機速度行駛，并通過RSUs接入Internet。每個車輛通過直接或多跳方式與RSU通信。假設條件如下：

    (1)所有車輛都具備GPS定位功能和無線局域網絡功能(WLAN capabilities)；

    (2)每個車輛利用GPS系統獲取自己的位置和速度；

    (3)RSU扮演網關(Gateway)，車輛通過網關接入Internet；

    (4)僅當車輛θ_i與θ_j的距離d_ij小于通信范圍R，車輛θ_i與θ_j的通信鏈路l_ij才被建立；

    (5)鏈路l_ij的剩余壽命τ_ij：

其中，S_i、S_j分別表示車輛θ_i、θ_j的速度。如果兩車輛以同樣的速度移動，鏈路l_ij的剩余壽命τ_ij無限大。

1.2 Congestion Game模型

    依據文獻[13]，在時隙t，博弈的模型如式(2)所示：

其中，N表示車輛(player)集，N_r=N∪N_g表示資源集，分別由車輛集N和網關集N_g構成。C_i表示成本函數，A_i表示player i選擇另一個player j作為轉發節點的行為空間，如式(3)所示：

    此外，每個player i為了轉發數據包，而選擇另一個player j作為轉發節點所形成的成本由四個方面組成。

    (1)取決由車輛θ_i、θ_j間鏈路的剩余壽命，如式(4)所示：

其中，α、β、γ以及δ均為正數，且表示相應四部分成本的權值因素。α+β+γ+δ=1，它們各自反映了四部分成本的影響性。因此，每個player在選擇策略時，應使得成本函數最小化。

    此外，依據文獻[13]，成本函數也稱為Potential function，如式(9)所示：

1.3 路由算法

    由于Player不知道網絡知識，無法計算Nash Equilibrium。為此，先提出一個基于BoltzmannGibbs^[14]學習算法，計算時隙t的Nash Equilibrium。

    在求得Nash Equilibrium等式后，再計算接入Internet的最優路徑，最后，選擇最優的路徑作為數據傳輸通道。

2 數值分析

2.1 仿真場景

    考慮長為L=4 000 m的三車道的高速場景，車輛行駛速度在(20 m/s，30 m/s)范圍內，如圖3所示。公路旁部署了網關，并且網關的間距D如式(11)所示：

其中，L為道路長度，m為網關數，仿真參數如表1所示。

2.2 學習算法的評估參數

    為了有效地評估提出的學習算法，選擇比率η參數，如式(12)所示：

    通過仿真得出部分數據如表2所示。當η=0，表示學習算法的求解方案接近于Nash equilibrium。

2.3 仿真結果分析

    本文主要采取以下兩個參數指標評估：(1)路由失敗(Route failures)：指在仿真過程中，路由斷裂的或未能建立的路由的平均數；(2)路由長度(Route length)：指路由的平均跳數。

    考慮兩類場景參數。第一類場景中，網關數為7、車輛數從60至90變化；第二類場景中，車輛數為30，網關數從2變化至14。

    (1)Route failures

    圖4繪制了Route failures隨車輛密度的變化曲線。從圖4可知，車輛密度對Route failures的影響不大，這主要是因為車輛密度增加，形成了更多的轉發節點，從而有更多的鏈路尋找網關，但這并不會加劇Route failures的變化。

    另外，Route failures隨著網關數的增加而下降，這與估計的相同。對于一個車輛而言，找到鄰近的網關會降低路由長度，而短路徑的路由更有利于Route failures的下降。一旦網關數達到10，所有的車輛均與網關連接，Route failures接近于0。

    (2)Route Length(Number of hops)

    圖5為Route Length隨車輛密度的波動情況。從圖5可知，Route Length的中間值較穩定，約為1.184，這些數據表明車輛密度對Route Length的影響較小。圖6進一步描繪了在不同車輛密度時Route Length的值。仿真數據進一步證實，車輛密度對Route Length的影響較小。

    圖7反映了Route Length隨網關數的分布情況。Route Length隨網關數的增加而下降，當網關數到達9以后，Route Length接近于1。從圖8可知，網關數對Route Length有極大的影響。

3 總結

    本文提出基于Congestion game車輛接入網關的數學模型。該模型利用成本函數選擇最優的策略，從而尋找到接入網關的最優路由。提出的該模型能夠為每個player尋找到最優的策略，并計算Nash equilibrium，從而解決網絡擁塞問題，即找到最佳的接入Internet的路徑。仿真結果表明，提出的學習算法能夠獲取并接近于Nash equilibrium的解。此外，分析了車輛數和網關數對路由的性能影響。從仿真數據得知，車輛密度對Routes failure 和Routes length的影響不大，而網關對Routes failure 和Routes length有著極大的影響。

參考文獻

[1] MISRA S，VENKATA K P，SARITHA V.Lacav：an energy-efficient channel assignment mechanism for vehicular ad hoc networks[J].The Journal of Supercomputer，2012，62(3)：1241-1262.

[2] 夏梓峻，劉春鳳，趙增華，等.基于鏈路預測的VANET路由算法[J].計算機工程，2012，38(4)：110-114.

[3] MISRA S，VENKATA K P，SARITHA V.Learning automata-based virtual backoff algorithm for efficient medium access in vehicular ad hoc networks[J].Journal of Systems Architecture，2013，59(10)：968-975.

[4] 常促宇，向勇，史美林.車載自組網的現狀與發展[J].通信學報，2007，11(5)：116-127.

[5] Hui Fu.A survey on the characterization of vehicular ad hoc networks routing solutions[J].ECS，2005，3(6)：1-15.

[6] ZANG Y，WEISS E.Opportunistic wireless internet access in vehicular environments using enhanced wave devices[J].International Journal of Hybrid Information Technology(IJHIT)，2008，1(2)：83-100.

[7] Wu Dong，Ling Yu，Zhu Hui.The rsu access problem based on evolutionary game theory for vanet[J].International Journal of Distributed Sensor Networks，2013，3(5)：21-27.

[8] SARITHA V，MADHU V.Approach for channel reservation and allocation to improve quality of service in vehicular communications[J].IET Networks，2013，3(2)：150-159.

[9] CHARILAS D E，PANAGOPOULOS A D.A survey on game theory applications in wireless networks[J].Computer Networks，2010，54(18)：3421-3430.

[10] BARBOSA A，BARROS P.An adaptive mechanism for access control in VANETs[J].Computer Networks and Security Laboratory，State University of Ceara(UECE)，2011，42(8)：123-132.

[11] Chen Tingting，Zhu liehuang，Wu Fan，et al.Stimulating cooperation in vehicular Ad hoc networks：a coalitional game theoretic approach[J].IEEE Transactions on Vehicular Technology，2011，60(2)：566-579.

[12] WU D，CAO J Y.Routing algorithm based on multicommunity evolutionary game for vanet[J].Journal of Networks，2012，7(7)：1106-1115.

[13] MONDERER D，SHAPLEY L S.Potential games[J].Games and Economic Behavior，1996，14(1)：124-143.

[14] TEMBINE H.Distributed strategic learning for wireless engineers[M].CRC Press，2012.