VANET中基于TUU博弈的合作激励机制

孙玉洁，李一洋，任 钧，孟海宾，苗 成

（北方自动控制技术研究所，太原 030006）

0 引言

VANET具有无线自组网［1］的一般特征，但同时也存在很大的差异：1）车辆节点数目巨大、分布区域广泛，具有丰富的外部辅助信息，例如车载定位/导航、激光雷达、视觉传感装置等；2）车辆只能沿着道路作高速、受限、约束运动；3）节点间的网络拓扑变化频繁，并且频繁的拓扑变化又将导致频繁的网络分裂［2］；4）网络极易受驾驶员自私行为以及周围环境，包括是否存在障碍物等因素的影响［3］，由于VANET存在这些特点，将会导致相应的问题：VANET车辆节点数目巨大且分布区域广泛，不同区域的拓扑结构和通信状态都随时间动态变化。通信状态良好的区域通信链路完整，消息交付率高，而通信能力差的VANET区域里，车辆发出的消息不能够成功地交付到目的车辆，或者消息传送的延时增大，消息丢包率高，尤其是很多重要的用户消息会因网络通信能力不强而丢弃，这大大降低了网络的Qos服务质量。因此，良好的VANET通信状态不仅能够提高V2V通信的效率，还能够为数据融合、实时同步和多媒体播放等车联网应用提供支撑，而且也有利于延长网络的生命周期。综上，VANET通信能力的研究是VANET的一个基本问题，是保证网络性能的关键所在。

由于车辆节点的自主性，部分节点可能为了节省带宽和缓存等资源而拒绝转发消息，这种拒绝转发消息的自私行为会引起拓扑变化更加明显。

1）VANET拓扑结构离散化，如图1所示：图1（a）表示所有车辆节点合作时的VANET拓扑，可以看出此时所有车辆之间的消息都能确保可靠传递到网络中的任意车辆上；图1（b）表示网络中存在自私节点Selfish Node时，网络瞬间缺乏端到端的完整链路，图中最左边的车辆只能将消息转发到至多两个车辆节点。图1说明自私行为严重影响了VANET的连通性，降低了VANET的服务性能。

图1 VANET拓扑结构离散化图

2）自私节点在一定程度上可以避免广播风暴，如图2所示：图2（a）中，主干道上总共有20个车辆节点，车辆移动速度缓慢，VANET拓扑变化不明显。如果所有节点都合作参与消息的转发，源节点发出的消息会在整个网络epidemic式传播，所有车辆都将接受到的消息传送给它的邻居节点，因此，很显然会导致网络的广播风暴；图2（b）中，灰色节点为Selfish Nodes，因为VANET中部分节点的自私存在，从图中可以看出，在自私节点主动独立出VANET后，网络拥塞现象得到缓解，拓扑结构清晰明朗，链路完整且不冗余，不仅可以保证源节点到目的节点的消息传递，而且能够降低网络吞吐量，降低传递延时。虽然少量的自私节点能够在一定程度上提高VANET的服务性能，但是如果网络中的自私节点数量过多，即使VANET中存在大量的车辆节点，也不能保证稠密VANET的连通性。因此，必须构建一种合适的激励机制［4-5］，通过监测网络当前的通信状态，动态地控制自私节点充当中间转发节点的数量，从而有效地控制整个VANET的通信链路，保证网络通信状态良好。

图2（a）稠密VANET 图2（b）存在自私节点的VANET

然而，为了保证激励机制的合理实施，必须准确评估当前VANET的通信状态，D-S证据理论方法是目前态势评估最常用的方法：对于VANET整个数据处理系统而言，多方面多角度地收集车辆节点的数据信息，最终是为了对网络当前的通信状态做出一个最终的决策，通过数据融合后的更准确更可靠的决策执行后续的激励机制。

1 VANET通信能力的评估

近年来，信息融合已经成为信息处理领域研究的热点问题，对于多信息源的分布式检测以及数据融合的各种方法，人们已经在理论上做了大量的研究，而在VANET的实际场景中，利用车辆信息的数据融合结果进行网络决策或者预测的研究却很少。如何利用VANET数据处理中心（NCC）获得的网络信息来动态、准确地判定VANET内各个ZONE当前的通信状态是实现该篇论文的关键问题，也是执行TUU博弈模型的前提条件。

1.1 D-S证据理论

VANET由于自身的动态拓扑变化，每个ZONE在未来某个时刻的通信状态充满了未知性，不适合利用简单的概率理论对VANET随时间不确定变化的网络通信状态进行判定，而D-S证据理论针对这种未知引起的不确定性充分发挥了自身的优势，通过给定的证据、利用信度函数和似然函数两个数值组成的区间来表示对命题的信任度，通过合成规则对不同证据产生的信息进行融合，因此，D-S数据融合方法能够很好地适应于通信状态多变的VANET，通过给定的网络证据指标，每个NCC计算出的概率值表示对网络通信状态的信任度，通过简单的合成规则就能得到准确、可靠的当前网络通信状态。

1.2 ZONE的网络状态的判定

根据第1部分讨论的D-S证据理论及其组合规则，基于D-S证据理论的信息融合方法主要包括3个步骤：

1）融合问题的建模，即确定融合问题的识别框架。VANET的通信状态结果组成了识别框架Θ=（通信能力强S，通信能力弱D），信息源分别给出二者在识别框架上的基础概率分配。

2）信息的融合过程。

3）根据融合结果，采用一定的判别准则，确定获得最大支持度的可能性，并做出相应的决策。具体流程图如图3所示。

图3 基于D-S证据理论的信息融合过程

利用D-S证据理论进行信息融合：

焦元有两个，分别为S，D。令S表示通信能力强，D表示通信能力弱，其识别框架为Θ={S，D}。证据数有 4个，m1=m度分布，m2=m网络链路数，m3=m聚类系数，m4=m平均路径长度。

预估方法不确定性的计算公式为：

其中，k∈（0，1）为归一化因子。信度函数的物理含义为证据对S或D的支持程度，因此，得到下述判决准则：

数据处理中心能够快速通过此方法，准确地判断每个ZONE的网络通信状态，即通信能力强S或是通信能力弱D。

2 基于TUU博弈的激励机制

2.1 基于TUU博弈的稀疏VANET激励机制

在稀疏VANET中，发送、接收或者转发数据包都是随机过程。如果所有节点合作，即节点转发接收到的数据包，那么所有节点将会受益，但是每个节点也将会耗费一些成本来转发邻居节点的数据包。在合作网络中，一个自私节点受益会更多，因为它不用消耗自己的资源来转发其他节点的数据包。然而，如果所有节点都自私，那么所有节点就会仅仅发送自身的数据包而不转发邻居节点的数据包，导致稀疏VANET中的数据包全部不能成功送达目的节点，从而引起网络严重瘫痪。因此，利用博弈方法的激励机制来解决稀疏VANET的连通性问题。

假设邻居关系是对称的，通信信道也是双向的。从源节点到目的节点是通过中间节点转发数据包的。假设每个节点有一个唯一的真实的身份，可转移支付联盟博弈（N，v）中，参与者集合N定义为VANET中一个区域ZONE内的所有车辆，v是每个非空参与者集合的联盟总收益。对于每个节点，其策略空间是［合作，叛变］，代表了中间节点i在接收到数据包后，是选择转发还是丢弃。使用博弈之前，区域ZONE中每个车辆都为一个单一联盟。效用函数综合考虑了平均连接率、延时、与目的节点之间的距离以及节点的信誉值。每个节点通过计算自身效用函数，得出：节点加入一个更大的联盟比单独行动获得更大的收益，从而加入联盟进行合作，最终，博弈的结果使得VANET区域中的所有节点形成一个大联盟。制定节点i在k阶段的平均收益如下：

对任意成员 i、j，πji是 i与 j合作（与其他成员合作）的收益，δji是i与j合作造成的损失，所以，πji-δji是 i与 j合作的净获益；同理，πji-δji是 j与 i合作的净获益；ai是i对联盟所作贡献的努力程度。因此，补偿给i的总的净收益或从i之处取出补偿其他成员的总的净收益（即Ti值可正也可负）就是i与其他合作成员全部净收益之差的和，依据i对联盟所作贡献的努力程度再次分配。在双方的合作中获益较多的一方应给获益较少的一方一定量的利益补偿，同理，不合作中获益较多的一方应从获益较少的一方那里得到利益补偿，只有这样才能有望达成合作协议。同时，获益一方在补偿受损一方之后的福利应该仍然比参加合作前有所提高，即

表1 收益分配中各参数的含义

其中，cpi是节点 i的平均连接率。把 Ni（k）作为节点 i在k阶段时的邻居集，节点i保持每个邻居节点j的动态数据：

通过这种转发率的计算可以从单一节点得出此次交易过程中，一个节点是合作的还是自私的。最后，节点i评价节点j的平均连接率为：

2.2 基于TUU博弈的稠密VANET激励机制

上一部分针对稀疏VANET，利用基于TUU博弈的激励机制，合理激励区域ZONE中所有节点积极合作，最终形成稳定大联盟，不但能够增加网络连接的机会，而且能够使自私节点快速恢复到区域VANET中，从而增加消息传递的成功率和稀疏VANET的连通性。然而，在稠密VANET中，由于VANET节点密度过大，车辆的移动特征不明显，如果采用稀疏VANET中的激励机制促使节点合作，不但会出现消息在密集ZONE内的频频交互，浪费大量的带宽、缓存等资源的情况，还使得自私节点被迫参与消息的转发收益甚小。因此，针对稠密VANET，本文提出一种新的机制——自私容忍激励机制。这种激励机制应用了可转移效用博弈理论，提出选择区域中具有高投递率、高信誉值、低移动性的节点作为代理节点的概念［4］，选择区域代理节点作为中间转发节点，能够很好地控制中间转发节点过多导致出现消息频频交互的情况，适当容忍稠密VANET中自私节点拒绝转发数据包的情况，减少了网络中的冗余包，有效地降低了网络负载，同时保证了网络的连通性，提高了网络性能。

假设每个节点的通信范围是固定的，且节点一次转发消息的所耗费成本cost都是相同的。可转移支付博弈（N，v）中，参与者集合N定义为ZONE中所有代理节点的集合，v是每个非空参与者集合的联盟总收益。博弈开始前，由于每个节点对网络信息的不确定性，任意选择ZONE内某一节点为代理节点。代理节点i的效用函数如下：

Pr是在此博弈阶段节点i被选为区域ZONE内的代理节点的概率。Wi是代理节点i转发一个消息所得的报酬，cost是转发一个消息耗费的成本，ui（k-1）是代理节点i在第k-1阶段的效用值，ut是每个阶段博弈的效用阈值。稠密VANET自私容忍激励机制的博弈算法具体实现过程如下：

1）初始化阶段。NCC选择任意车辆节点为ZONE内初始代理节点。设置计时器n=1，NCC存储ZONE内每个车辆节点的效用值，ut的初始阀值为初始代理节点的效用值utmin；

图4 稠密VANET自私容忍激励机制的博弈算法

2）在ZONE内最初被NCC选择的那个代理节点为一个单人联盟。TUU博弈使得代理节点组成的联盟不断增大，即不断有新的效用值高的节点加入联盟。由于稠密VANET的网络特点，不需要所有的节点都充当代理节点，因此，在每一阶段博弈结尾，NCC都要将每个代理节点的效用值ui与效用阈值ut进行比较，如果出现ui大于ut，表示该节点可以加入联盟成为代理节点，置计时器n累加1个单位；

3）如果计数器在某一博弈阶段开始时，NCC检测到n≥nmax=η*N，表示稠密VANET中已经存在过多的代理节点，从而使得网络消息投递的成功率下降，消息频频交互，此时应当立即调整联盟中代理节点的效用阈值ut，其中N表示网络节点总数目，η表示网络允许的代理节点占全网节点的最大比重；

4）然后不断动态调整效用阈值ut，使整个网络中代理节点组成的联盟达到稳定，从而使网络性能得到改善。具体流程如图4所示。

3 仿真

利用仿真平台评估TUU-D激励机制，并与DARWIN激励机制和ICASRUS激励机制进行仿真对比。

地图：赫尔辛基市地图（MovementModel.world-Size=4 500，3 400）；

移动模型：ShortestPathMapBasedMovement（合作节点100个，自私节点30个）；

路由协议：EpidemicRouter；

图5 自私节点比例不同的网络吞吐量

在图5中，探讨自私节点的比例对网络节点转发率的影响。值得注意的是，即使自私节点占全网节点的比例达到90%，在本文机制中，合作节点比自私节点能达到一个更的好转发率。事实上，网络转发率指标的提高，很大程度上取决于网络中自私节点的比例。

图6 激励机制对合作节点的转发率

图7 激励机制对自私节点的转发率

图6、图7分别描述了3种激励机制对合作节点和自私节点的转发率的影响。对于合作节点来说，本文机制相对于DARWIN机制和ICARUS机制在转发率方面提高10%左右，尤其是对于仿真的前半阶段（Time Slot＜500），在仿真的后半阶段，这种差别逐渐削弱，但本文机制在相同的设置下能够达到更高的转发率（约为1%）。对于自私节点来说，情况发生显著变化，自私节点转发率的下降趋势说明3中激励机制都有效地控制了节点的自私行为，而本文机制惩罚力度最大，下降趋势也最明显，在整个仿真阶段下降约30%。说明激励机制更加有效。

图8 激励机制“恢复”自私节点的能力

图8观察了3种激励机制“恢复”自私节点的能力。正如论文中提到，被NCC检测到有自私行为的节点不能发送自身的数据包，因此，需要积极参与合作。图8枚举了3种激励机制在仿真过程中节点表现出的自私性。从图8中可以看出，DARWIN机制在约920个时隙时依然存在少量自私节点，I CARUS机制约在800个时隙时存在少量自私节点，本文机制在350个时隙已经达到稀疏VANET中的理想控制指标，因此，本文机制能够更快速地激励自私节点的合作。

4 结论

本文提出了融合DARWIN机制和经济学中TUU博弈模型的新的激励机制TUU-D机制，通过D-S证据理论提取影响网络连通性的特征指标，通过证据融合动态判断网络状态；引入TUU博弈方法，动态时变地激励VANET中车辆节点的移动合作；将提出的激励机制与经典激励机制作对比，仿真结果证明TUU-D激励机制能够在不同的城市场景下保证网络的连通性，从而确保了网络Qos服务质量。