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.