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.