合作圖博弈在車載網數據分發中的應用

費 翔，欒 西，依 那，李 俊，吳建軍

（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—），男，博士，教授，主要研究方向：衛星通信、無線通信和信號處理。