0 引言

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

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

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

    本文從博弈Game理論入手，提出一個(gè)基于Congestion game的接入Internet的數(shù)學(xué)模型。利用博弈Game理論解決路由選擇問題。在博弈Game理論中，當(dāng)實(shí)體的成功取決于系統(tǒng)中其他實(shí)體的決策時(shí)，博弈Game可作為一個(gè)最優(yōu)的分析工具。為此，利用博弈Game理論提出一個(gè)新的模型，尋找到最優(yōu)的路徑。

1 系統(tǒng)模型

    為了在VANET中應(yīng)用博弈理論(Game theory)，首先介紹Game theory相關(guān)的概念，并與VANET相對(duì)應(yīng)。用VANET 中的車輛扮演參與者(Player)，Player采取的策略與應(yīng)用函數(shù)相關(guān)。VANET網(wǎng)絡(luò)的服務(wù)質(zhì)量表示博弈理論中的效用函數(shù)(成本函數(shù))。

1.1 場(chǎng)景描述

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

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

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

    (3)RSU扮演網(wǎng)關(guān)(Gateway)，車輛通過網(wǎng)關(guān)接入Internet；

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

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

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

1.2 Congestion Game模型

    依據(jù)文獻(xiàn)[13]，在時(shí)隙t，博弈的模型如式(2)所示：

其中，N表示車輛(player)集，N_r=N∪N_g表示資源集，分別由車輛集N和網(wǎng)關(guān)集N_g構(gòu)成。C_i表示成本函數(shù)，A_i表示player i選擇另一個(gè)player j作為轉(zhuǎn)發(fā)節(jié)點(diǎn)的行為空間，如式(3)所示：

    此外，每個(gè)player i為了轉(zhuǎn)發(fā)數(shù)據(jù)包，而選擇另一個(gè)player j作為轉(zhuǎn)發(fā)節(jié)點(diǎn)所形成的成本由四個(gè)方面組成。

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

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

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

1.3 路由算法

    由于Player不知道網(wǎng)絡(luò)知識(shí)，無法計(jì)算Nash Equilibrium。為此，先提出一個(gè)基于BoltzmannGibbs^[14]學(xué)習(xí)算法，計(jì)算時(shí)隙t的Nash Equilibrium。

    在求得Nash Equilibrium等式后，再計(jì)算接入Internet的最優(yōu)路徑，最后，選擇最優(yōu)的路徑作為數(shù)據(jù)傳輸通道。

2 數(shù)值分析

2.1 仿真場(chǎng)景

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

其中，L為道路長(zhǎng)度，m為網(wǎng)關(guān)數(shù)，仿真參數(shù)如表1所示。

2.2 學(xué)習(xí)算法的評(píng)估參數(shù)

    為了有效地評(píng)估提出的學(xué)習(xí)算法，選擇比率η參數(shù)，如式(12)所示：

    通過仿真得出部分?jǐn)?shù)據(jù)如表2所示。當(dāng)η=0，表示學(xué)習(xí)算法的求解方案接近于Nash equilibrium。

2.3 仿真結(jié)果分析

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

    考慮兩類場(chǎng)景參數(shù)。第一類場(chǎng)景中，網(wǎng)關(guān)數(shù)為7、車輛數(shù)從60至90變化；第二類場(chǎng)景中，車輛數(shù)為30，網(wǎng)關(guān)數(shù)從2變化至14。

    (1)Route failures

    圖4繪制了Route failures隨車輛密度的變化曲線。從圖4可知，車輛密度對(duì)Route failures的影響不大，這主要是因?yàn)檐囕v密度增加，形成了更多的轉(zhuǎn)發(fā)節(jié)點(diǎn)，從而有更多的鏈路尋找網(wǎng)關(guān)，但這并不會(huì)加劇Route failures的變化。

    另外，Route failures隨著網(wǎng)關(guān)數(shù)的增加而下降，這與估計(jì)的相同。對(duì)于一個(gè)車輛而言，找到鄰近的網(wǎng)關(guān)會(huì)降低路由長(zhǎng)度，而短路徑的路由更有利于Route failures的下降。一旦網(wǎng)關(guān)數(shù)達(dá)到10，所有的車輛均與網(wǎng)關(guān)連接，Route failures接近于0。

    (2)Route Length(Number of hops)

    圖5為Route Length隨車輛密度的波動(dòng)情況。從圖5可知，Route Length的中間值較穩(wěn)定，約為1.184，這些數(shù)據(jù)表明車輛密度對(duì)Route Length的影響較小。圖6進(jìn)一步描繪了在不同車輛密度時(shí)Route Length的值。仿真數(shù)據(jù)進(jìn)一步證實(shí)，車輛密度對(duì)Route Length的影響較小。

    圖7反映了Route Length隨網(wǎng)關(guān)數(shù)的分布情況。Route Length隨網(wǎng)關(guān)數(shù)的增加而下降，當(dāng)網(wǎng)關(guān)數(shù)到達(dá)9以后，Route Length接近于1。從圖8可知，網(wǎng)關(guān)數(shù)對(duì)Route Length有極大的影響。

3 總結(jié)

    本文提出基于Congestion game車輛接入網(wǎng)關(guān)的數(shù)學(xué)模型。該模型利用成本函數(shù)選擇最優(yōu)的策略，從而尋找到接入網(wǎng)關(guān)的最優(yōu)路由。提出的該模型能夠?yàn)槊總€(gè)player尋找到最優(yōu)的策略，并計(jì)算Nash equilibrium，從而解決網(wǎng)絡(luò)擁塞問題，即找到最佳的接入Internet的路徑。仿真結(jié)果表明，提出的學(xué)習(xí)算法能夠獲取并接近于Nash equilibrium的解。此外，分析了車輛數(shù)和網(wǎng)關(guān)數(shù)對(duì)路由的性能影響。從仿真數(shù)據(jù)得知，車輛密度對(duì)Routes failure 和Routes length的影響不大，而網(wǎng)關(guān)對(duì)Routes failure 和Routes length有著極大的影響。

參考文獻(xiàn)

[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] 夏梓峻，劉春鳳，趙增華，等.基于鏈路預(yù)測(cè)的VANET路由算法[J].計(jì)算機(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] 常促宇，向勇，史美林.車載自組網(wǎng)的現(xiàn)狀與發(fā)展[J].通信學(xué)報(bào)，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.