合作图博弈在车载网数据分发中的应用

费 翔，栾 西，依 那，李 俊，吴建军

（1.北京大学信息科学技术学院卫星与无线通信实验室，北京100871；2.总参信息化部驻杭州军代室，浙江杭州310000）

合作图博弈在车载网数据分发中的应用

费 翔1，栾 西1，依 那1，李 俊2，吴建军1

（1.北京大学信息科学技术学院卫星与无线通信实验室，北京100871；
2.总参信息化部驻杭州军代室，浙江杭州310000）

针对日益突显的车载自组织网络中的内容分发问题，对车载网中的流行内容分发进行了简要介绍，论述了现有方案的不足之处，并创新性地采用合作图博弈对该问题进行了建模，在该模型中，车载单元（the On－Board Units，OBUs）根据通过博弈建立的网络进行数据分发。对提出的基于图论的合作博弈方案在车载网数据分发中的性能进行了仿真分析，结果表明，与传统的非合作方法相比，该方法具有明显的优势。

车载自组织网络；流行内容分发；合作图博弈；成对稳定

0 引言

最近，一种叫做流行内容分发的应用受到了研究者的广泛关注［1］。在该应用中，行驶中的车辆通过车载单元与路边单元（the Roadside Units，RSUs）的通信来下载流行多媒体内容［2］。由于文件大、车速快，OBUs在通过RSUs覆盖区域时不能完成整个文件的下载。

受互联网点对点通信协议［3，4］的启发，一些研究者利用汽车对汽车（Vehicle－to－Vehicle，V2V）通信组成点对点网络来完成OBU间的内容分发。文献［5］介绍了一种基于网络编码的移动P2P文件共享系统，文献［6］首先将合作博弈应用到了V2V通信中。在文献［7］中，作者提出了一种名为SPAWN 的P2P文件下载协议，然而SPAWN的节点和内容选择机制并不适用于文件较大的场景。

本文将已经在通信场景中得到应用［8］的合作图博弈引入到车载自组织网络中，解决了车载网中的流行内容分发问题。在博弈中，OBUs通过分布式的动态博弈形成一个成对稳定的网络，并按照网络进行数据传输。与传统的非合作方法相比，该方案同时考虑了网络中的内容需求和信道容量，提升了网络的性能。

1 系统模型

在考虑的场景中，共有M个OBU（SU用户），它们通过K个PU信道完成流行内容的分发。将这个问题规划为一个联合图博弈，在该博弈中，OBUs试图建立一个有方向的成对稳定图。一旦完成网络的构建，OBUs将会采取合作的方法按照图进行数据分发。假设OBU之间的单跳通信限制在直视范围内（称作“邻居节点”）。整个流行内容被分为N个大小相等的片段，每个OBU都需要全部片段。用M、N、Mi和K分别表示OBUs组成的集合、数据片段集合、OBU i的“邻居节点”的集合以及PU信道的集合。由于OBUs处于高速移动状态，经过RSU覆盖区域的时间较短，因而只能接收到片段集合N的一部分，剩余的数据片段需要通过V2V通信获得。在V2V通信中，一个OBU每次只能接收一个OBU的数据，但是可以同时向多个OBU传输数据。用Ni表示OBU i已经拥有数据片段集合，假设Ni中的初始元素均匀分布于集合N中。

在本系统中，假设每个PU信道上数据包的到达服从泊松分布，每个时隙中数据包的到达率为λ。对于K中的某一个信道，没有主用户占用信道的概率为P0＝e－λ，所有的OBU都使用全向天线。由于车辆行驰在高速公路上，因而建模时可以不考虑信道的小尺度衰落。在第k个PU信道上，OBU i和OBU j之间的V2V信道容量为：

式中，Wk为第k个信道的带宽，n为路径损耗指数，di，j为OBU i和OBU j之间的距离，βi为发射端的信噪比。为了不失一般性，假设W1＝W2＝…＝Wk＝W，β1＝β2＝…＝βk＝β。

对于车辆的移动模型，参考文献［9］中提出的高速公路车辆移动模型（FMM）。一个简化的双车道单向高速公路模型如图1所示。车辆在初始时刻随机布在2个车道上。为了更真实地反应车辆的移动，在该模型中，允许车辆进行变道超车。OBU的初始速度为vi（0），且vi（0）随机分布在［vmin，vmax］之间。其中，vmin是OBU的最低速度，vmax是OBU的最大速度。同一个车道上2个相邻车辆之间的安全距离为dmin。对于任意一个OBU i，只有在与同车道前向相邻车辆之间的距离小于dmin，且与相邻车道上距离最近的前后两辆车的距离大于dmin时，才允许进行变道。如果同一个车道上2个车辆之间的距离大于最大距离dmax，则后车允许加速到最大速度。针对OBU不需要改变车速的情况，OBU的速度满足：

图1 系统模型

在传统的非合作方法中，集合M中的OBU在进行V2V通信时，不需要进行合作。OBUs节点将需求通过广播告知其“邻居节点”，并随机响应其他“邻居节点”的数据请求。每一个OBU节点，在响应其他节点的数据请求之前，需要独立地感知K个PU信道，然后通过载波监听多路访问/冲突检测（CSMA/CA）协议接入空闲信道。

2 联盟图博弈

在传统的非合作数据传输方法中，V2V链路是随机建立的，这可能会使得OBU之间的通信效率较低，甚至有些OBUs可能没有与“邻居节点”建立连接。这就导致整个网络的数据吞吐量较低。下面利用合作图博弈来对车载自组织网络中的流行内容分发问题进行建模。通过分布式的动态博弈，建立一个有向的图G（V，E）。其中，V表示OBUs集，E表示V2V链路集。对任意的i，j∈V，j∈E表示节点i 和j之间存在一条有向链路。用diin和doiut分别表示图G中OBU节点i的入度和出度，其中，0≤diin≤1。

2.1 效用函数

对于某一个PU信道k，只有在该信道空闲，且其他邻居节点也没有在该信道上传输数据时，2个OBU节点之间才能够成功传输数据。用Pi，j表示OBU i和OBU j之间数据包成功传输的概率。

假设信道k∈K被主用户占用，用H1表示，反之用H0表示。同理，用H'1表示OBU i的检测结果表示信道k被主用户占用这一假设，反之用H'0表示。漏检概率和虚警概率分别用Pm和Pf表示，则每个OBU节点正确的做出信道空闲判别的概率为［10］：

式中，P（H0）＝P0，P（H1）＝1－P0，P（|H1）＝Pm，P（|H0）＝1－Pf。

总的来说，一共有KP0个PU信道处于空闲状态，可以被OBUs利用。每一个OBU都可以接入这些空闲信道中的任何一个信道。OBU j的邻居节点子集{Mji}中的OBU s没有与OBU i占用同一个信道的概率为：

假设OBU s发送和接收数据片段都能给整个网络带来相应的收益。OBU i的效用函数用πi（G）表示。考虑到周边节点的需求，OBU i在广播数据之前需要通过计算确定待广播的数据片段的集合与顺序，以获得更高的效用。采用一种贪心算法来选择每个OBU节点广播的数据片段。集合Ni，j＝（N Nj）M∩Ni表示OBU i可以提供给OBU j的数据片段的集合。用Ωi＝{j|ij∈E}表示与OBU i相连接的OBU节点集合。节点OBU i可以提供给Ωi的数据片段集合可以由Ni，b＝∪Ni，j给出。假设Ni，b中的数

j∈Ωi据片段按权重因子从大到小排序。每个数据片段的权重因子即为集合Ωi中缺少该数据片段的OBU节点的数目。OBU节点在每个时隙按照顺序一次广播集合Ni，b中的数据片段。假设每个时隙的数据传输时间为T，则OBU j在一个时隙内从OBU i接收到的数据片段集为：

用γout和γin分别表示发送和接收数据的价格因子，则相应的发送和接收效益分别为：

考虑到在进行数据传输时占用了相应的信道，增加了信道中数据冲突的概率，提高了信道的负担，这需要通过费用函数中体现出来。对于任何一条从OBU i发出的链路，潜在的冲突限制在集合μiΩi内。对于任意一条从OBU j指向OBUi的链路，潜在的干扰限制在集合μiΩi内。用γcost＞0作为价格因子，则费用函数为：

将式（6）、式（7）和式（8）相结合可以得到节点OBU i（i∈Μ）的效用函数：

2.2 动态网络的形成

下面给出了一个包含3个阶段的分布式短视动态博弈网络形成算法。短视动态方法是指在每一轮博弈过程中，每个节点在选择策略时只考虑本轮的效益，而不考虑长远效益，这与考虑长远效益的策略刚好相反［11］。通过分布式的本地策略选择，节点在博弈过程中可以选出一个最优策略，逐步迭代直至形成一个稳定的有向图。

假设当前的数据传输网络为G（V，E），则任意节点OBU i可能的行为包括：

①当ij∉E时，建立一条新的链路ij；

③当ij∈E时，断开当前的连接ij；

④当ji∈E时，断开当前的连接ji；

⑤以上4种情况的组合。

在合作图博弈过程中，每轮博弈都会随机选出一个OBU选择出其想要建立连接的其他OBU节点。通常，在每一轮博弈过程中，OBU i需要选出节点fi∈Μ去接受连接，并选出一个节点集合Ti∈Μ建立指向他们的连接。用（fi，Ti）表示节点OBU i的策略，则OBU i的策略空间可以表示为：Si＝{（fi，Ti）|fi∈Μ，Ti∈Μ}。如果j∈Ti且i∈fj，则节点OBU i 和OBU j之间将会建立一条链路，所有的链路都是以这种形式建立的。

假设，当节点OBU i变化到新的策略，且周边节点进行了相应的处理时，网络结构相应的会由G（V，E）变为了V，E'）。对于任何一个处于状态（fi，Ti）的OBU i∈Μ，满足以下条件的策略si＝（，）∈Si将会被称作一个可行性策略：

随机选择一个节点OBU i∈Μ参加动态博弈，集合Pi∈Si表示节点OBU i的可行策略集，动态博弈网络形成算法的具体步骤如下：

步骤1：从Μi中的“邻居节点”获取必要的信息，并计算出可行性策略集。

步骤2：随机选择并执行一个可行性策略si＝（，）∈Pi：

①如果断开连接ik，k∈Ti可以提高自身效用，节点OBU i单边地选择断开连接。

步骤3：更新网络结构G（V，E）和OBUs节点的策略集。

进行多轮博弈直到最后形成一个双边稳定网络G*（V，E*）。

由于每2个节点之间通信链路的建立需要经过双方的同意（内在的双边性），因而在考虑网络的稳定性时本文考虑双边稳定性［12］。通常情况下，在双边稳定状态下，整个网络中的任何一个节点都不能通过改变自己的策略找到一个可行性策略，并且任何2个节点也不能通过改变策略而同时提升它们的效用。在本文的合作图博弈中，由于博弈规则的限制，没有OBU节点可以通过单方面地改变，或者双方改变而提升自身的效用，因为最终的网络结构G*（V，E*）是双边稳定的，仿真结果也验证了这一结论。

3 仿真结果

在不同条件下，对本文所提出的合作图博弈方法与传统的非合作方法在高速公路车载自组织网络中的流行内容分发性能进行对比与评估。仿真参数的设置如下：M＝4～12，K＝8，Pf＝Pm＝0.1，n＝4，λ＝0.1，vmax＝40m/s，vmin＝20m/s，α＝0.2m/s2，p＝0.1。

网络中所有OBU节点随着时间的推移获得总的数据片段的数量如图2所示。仿真条件为：M＝6，N＝80，在V2V通信开始时，OBUs已经拥有的数据包的比例为ρ0＝0.6。图2中纵轴是除以NM归一化之后的结果，可以看出，非合作的传统方法和本文提出的合作图博弈方法获得的数据片段总数量都随着时间的推移提高，但是本文提出的方法的性能更好。在非合作的数据分发方法中，OBUs节点向所有的邻居节点广播其数据需求，且随机地相应其他邻居节点的数据需求，这就对网络造成了负担，容易造成网络的拥塞。对于本文提出的合作图博弈方法，OBU节点根据数据广播和接收双方的需求选择性地向邻居节点传输数据，每一个时隙形成的网络结构在传输数据时都比较有效，因而提升了整个网络的性能。

2种方法下随着时间的推移，网络中广播节点的数量的变化如图3所示。仿真条件为：M＝6，N＝80。由图3可以看出，本文提出的合作图博弈方法下的广播节点的数量衰减速度要快于非合作方法，且最终合作博弈方法下的广播节点数量处于一个明显较低的水平。这主要是因为在非合作方法中，由于信道中数据的碰撞，数据片段传输成功率较低，造成潜在的有数据片段需求的节点的数量变化较慢。而在合作图博弈方法中，每个节点传输的数据片段都是网络中需求较高的，且只有效用较高的节点才会传输数据，降低了信道碰撞的概率，使得数据传输速率较高，可以快速降低网络中的需求节点的数量，从而使得广播节点的数量也降低。

图2 OBU节点随着时间的推移获得的数据片段总数

图3 网络中广播节点的数量随时间的变化

4 结束语

用一种合作图动态博弈方法解决了高速环境下车载自组织网络中的流行内容分发问题。在合作图博弈模型中，OBU节点之间相互合作，建立一个高效的P2P数据传输网络。在每次的数据传输过程中，每个OBU节点可以向多个节点发送数据，但只允许从单个节点接收数据。提出的合作图动态博弈方法最终会收敛到一个双边稳定网络。仿真结果显示提出的方法的性能明显好于传统的非合作方法。

［1］Hartenstein H，Laberteaux K P.A Tutorial Survey On Vehicular Ad Hoc Networks［J］.IEEE Communications Magazine，2008，46（6）：164－171.

［2］Fiore M，Barcelo－Ordinas J M.Cooperative Download in Urban Vehicular Networks［C］∥in IEEE 6th International Conference on Mobile Adhoc and Sensor Systems，Oct.2009：20－29.

［3］Bittorrent，2003［Online］.Available：http：∥bitconjurer.org/BitTorrent/.

［4］Spognardi A，Lucarelli A，Pietro R D.A Methodology for P2P File－Sharing Traffic Detection［C］∥Proc.Int’l Workshop Hot Topics in Peer－to－Peer Systems（HOTP2P’05），July 2005：52－61.

［5］Lee U，Park JS，Yeh J，et al.Code Torrent：Content Distribution using Network Coding in VANET［C］∥ACM1st International Workshop on Decentralized Resource Sharing in Mobile Computing and Networking（MobiShare），Los Angeles，CA，2006：120－126.

［6］Shrestha B，Niyato D，Han Z，et al.Wireless Access in Vehicular Environments Using Bit Torrent and Bargaining ［C］∥IEEE Global Communications Conference，New Orleans，LA，2008：110－118.

［7］Nandan A，Das S，Pau G M，et al.Co－operative Downloading in Vehicular Ad－hoc Wireless Networks.The Second Annual Conference on Wireless On demand Network Systems and Services（WONS），St.Moritz，Switzerland，2005：32－41.

［8］Saad W，Han Z，Debbah M，et al.Coalitional Game Theory for Communication Networks：A Tutorial［J］.IEEE Signal Processing Magazine，2009，26（5）：77－79.

［9］Mahajan A，Potnis N，Gopalan K，et al.Urban Mobility Models for Vanets［C］∥Proceedings of the 2nd IEEE International Workshop on Next Generation Wireless Networks，2006：105－110.

［10］WANG Tian－yu，Song ling－yang，Zhu han.Collaborative Data Dissem－ination in Cognitive VANETs with Sensing－Throughput Tradeoff［C］∥IEEE International Conference on Communications in China（ICCC），BeiJing，China，2012：88－93.

［11］Arcaute E，Johari R，Mannor S.Network Formation：Bilateral Contracting and Myopic Dynamics［J］.Lecture Notes Computer Science，2007，4858（12）：191－207.

［12］Jackson M O，Wolinsky A.A Strategic Model of Social and Economic Networks［J］.J.Econ.Theory，1996，71（1）：44－50.

图11 滤波器B的仿真和测试结果

3 结束语

综合研究了短路枝节加载双模滤波器，包括容性S－L coupling和感性S－L coupling 2种情况。根据传输零点理论推测了固有传输零点的产生原理和分布规律。根据该滤波器各通路解释了附加传输零点的产生原理和分布规律。通过改变谐振器结构和源与负载耦合极性，可使枝节加载双模滤波器产生不同的频率响应曲线以满足不同的需求。

参考文献

［1］Athukorala L，Budimir D.Design of Compact Dual－mode Microstrip Filters［J］.IEEE Trans Microw Theory Tech，2010，58（11）：2888－2895.

［2］Song K J，Quan X.Inductance－loaded Y－shaped Resonators and Their Applications to Filters［J］.IEEE Trans.Microw.Theory Tech.，2010，58（4）：978－984.

［3］吴景宇，位朝垒，李晶.全微带结构三阶横向滤波器设计［J］，无线电工程，2014，44（8）：48－51.

［4］Song K J，Quan X.Inductance－loaded Y－shaped Resonators and Their Applications to Filters［J］.IEEE Trans.Microw.Theory Tech.，2010，58（4）：978－984.

［5］Amari S，Rosenberg U.Synthesis and Design of Novel in line Filters with One or Two Real Transmission Zero［J］.IEEE Trans.Microw.Theory Tech.，2004，52（9）：1464－1478.

［6］Amari S.Direct Synthesis of Folded Symmetric Resonator Filters with Source－load Coupling［J］.IEEE Microwave and Wireless Components Letters，2001，11（6）：264－266.

［7］曲永志，李德志，马延爽.基于HFSS的微调谐腔体带通滤波器设计［J］.无线电通信技术，2012，38（3）：62－64.

［8］彭志华，邹小平.一种电调谐滤波器的设计改进方法［J］.无线电通信技术，2012，38（3）：78－80.

［9］张鲁红，杨雪霞，马哲旺.SIR实现的新型毫米波UWB滤波器［J］.无线电通信技术，2013，39（3）：53－56.

［10］贾建蕊，韩军.基于HFSS设计同轴腔调谐滤波器［J］.无线电工程，2011，41（1）：44－46，60.

［11］王琦.基于散射参数法的波导滤波器设计［J］.无线电工程，2011，41（6）：62－64.

［12］王清芬，殷素杰，马延爽.一种新型的腔体滤波器设计分析［J］.无线电工程，2012，42（6）：62－64.

Coalitional Graph Game for Content Distribution in Vehicular Networks

FEIXiang1，LUAN Xi1，YINa1，LIJun2，WU Jian－jun1
（1.School of Electronics Engineering and Computer Science，Peking University，Beijing 100871，China；
2.Military Representative Office of Information Technology Department of General Staff Headquarters Stationed in Hangzhou Region，Hangzhou Zhejiang 310000，China）

The popular content distribution（PCD）problem，which is becoming increasingly prominent in Vehicular Ad－hoc Networks（VANETs），is introduced in this paper.The disadvantages of the existingmethods are discussed，and this problem ismodeled as a coalitional graph gamein which the on－board units（OBUs）try to form a directed graphto complete the data dissemination efficiently.Simulation results show that the proposed approach performs better compared with the traditional non－cooperative case.

vehicular ad hoc networks；popular content distribution；coalitional graph game；pairwise stable

TN915.9

A

1003－3114（2015）04－91－5

10.3969/j.issn.1003－3114.2015.04.24

费 翔，栾 西，依 那，等.合作图博弈在车载网数据分发中的应用［J］.无线电通信技术，2015，41（4）：91－95.

2015－02－10

国家自然科学基金项目（61071083；61371073）；国家高技术研究发展计划（863计划）（2012AA01A506）

费翔（1990—），男，硕士研究生，通信与信息系统专业，主要研究方向：卫星与无线通信。吴建军（1968—），男，博士，教授，主要研究方向：卫星通信、无线通信和信号处理。