車載自組織網(wǎng)絡中節(jié)點合作行為的博弈研究①

曾熙凱,丁 箐

(中國科學技術大學 軟件學院,合肥 230051)

車載自組織網(wǎng)絡中節(jié)點合作行為的博弈研究①

曾熙凱,丁 箐

(中國科學技術大學 軟件學院,合肥 230051)

在車載自組織網(wǎng)絡中使用公共品博弈理論促進節(jié)點合作的研究表明車輛密集區(qū)域的節(jié)點會呈現(xiàn)不合作狀態(tài).本文通過模擬實驗得知當節(jié)點平均度數(shù)較低時,節(jié)點更容易產(chǎn)生合作行為.為了提高車輛密集區(qū)域中合作節(jié)點的比例,本文提出了博弈度數(shù)與博弈拓撲的概念,并在此基礎上構建了一種能夠更改網(wǎng)絡博弈拓撲,降低節(jié)點博弈度數(shù)的分組博弈理論模型.實驗結果表明,在車輛密集區(qū)域使用該博弈模型能夠顯著提高網(wǎng)絡中合作節(jié)點的比例.

公共品分組博弈; 車載自組織網(wǎng); 平均度; 節(jié)點合作

1 引言

車載自組織網(wǎng)絡中的數(shù)據(jù)傳輸對車輛節(jié)點的合作性有著很高的要求.然而,節(jié)點由于能耗和處理能力的限制容易出現(xiàn)拒絕轉(zhuǎn)發(fā)數(shù)據(jù)等目光短淺的自私行為.近年來在車載自組織網(wǎng)絡環(huán)境下采用博弈模型促進節(jié)點合作的論文呈增多趨勢[1-4],研究者應用博弈論的相關知識增強節(jié)點之間的合作轉(zhuǎn)發(fā).大多數(shù)研究都建立在網(wǎng)絡中存在中央控制器的基礎上,通過激勵或者懲罰策略促進節(jié)點合作,并不符合車載網(wǎng)絡具有分布式特點的實際情況.文獻[5,6]提出了一種基于消息轉(zhuǎn)發(fā)的公共品博弈模型,該模型采用了無中央控制的分布式機制,并運用了這種博弈模型探究車載自組織網(wǎng)的網(wǎng)絡特征對網(wǎng)絡中合作節(jié)點數(shù)量的影響.他們發(fā)現(xiàn)更高的聚類系數(shù)和更高的連通性會增加合作節(jié)點的比例.但是他們強調(diào)在車載自組織網(wǎng)絡中保持節(jié)點的合作性極其困難.其后部分作者致力于對公共品博弈模型進行優(yōu)化,文獻[7]構建了一種不均勻投資的公共品博弈模型.在該模型中,節(jié)點會對合作者比例更高的博弈團體投入更多的資金.張海峰等人提出理性的節(jié)點如果在某輪博弈時從以節(jié)點i為中心的博弈中得到更多的收益,那么在下一輪參加該博弈時就會投入更多的資金[8].文獻[9]則根據(jù)節(jié)點度數(shù)定義了節(jié)點之間的影響強度,更高度數(shù)的節(jié)點對更低度數(shù)節(jié)點的影響越大.節(jié)點參與博弈時,根據(jù)與博弈中心中心節(jié)點之間的影響強度決定投資金額與收益分配.實驗表明以上模型都能夠促進節(jié)點的合作行為.在文獻[10]中,節(jié)點根據(jù)自己度數(shù)的大小決定博弈時的投資金額.實驗表明,當高度數(shù)節(jié)點投資更少時能促進網(wǎng)絡中節(jié)點的合作行為.文獻[11]中,學者根據(jù)節(jié)點的度數(shù)決定公共池金額的分配.實驗顯示分配給高度數(shù)節(jié)點或者低度數(shù)節(jié)點更多的收益都會提升網(wǎng)絡中合作節(jié)點的比例.由于車載自組織網(wǎng)絡中節(jié)點不停移動、鄰居也相應不斷變化,因此節(jié)點不知道鄰居節(jié)點博弈的歷史信息,博弈前也不知道自己本輪的博弈度數(shù),這些針對無標度網(wǎng)的博弈優(yōu)化模型并不適合車載自組織網(wǎng)絡.

在本文的工作中,通過觀察使用公共品博弈模型促進節(jié)點合作時車輛密度與合作節(jié)點比例的關系,發(fā)現(xiàn)較小的節(jié)點平均度能夠促進網(wǎng)絡中節(jié)點的合作行為,提出了一種適合于車載自組織網(wǎng)絡的公共品分組博弈模型,并分析了節(jié)點平均度對于合作節(jié)點數(shù)量的影響.實驗表明合理的對節(jié)點進行分組從而降低節(jié)點平均度數(shù)能夠顯著地提升車載自組織網(wǎng)絡中合作節(jié)點的比例.

2 博弈基礎

本文采用公共品博弈作為博弈模型的基礎.在公共品博弈中,合作者選擇向公共品獎池中投入一定資金c,非合作者不投入資金.一段時間后,公共資源產(chǎn)生r倍增值,小組所有成員平均分配公共池資源.倍增系數(shù)r代表了團隊的協(xié)同效益,預示團隊協(xié)同的力量大于個人獨自行動.當倍增系數(shù)r越高時團隊的收益越高,更能激勵節(jié)點參與團隊協(xié)作.

在車載自組織網(wǎng)中將消耗自身資源轉(zhuǎn)發(fā)數(shù)據(jù)包的節(jié)點稱為合作者,由于自私性拒絕轉(zhuǎn)發(fā)數(shù)據(jù)包的節(jié)點稱為非合作者,認為兩種節(jié)點分別擁有合作和非合作策略.合作節(jié)點的轉(zhuǎn)發(fā)行為為整個網(wǎng)絡的消息傳播作出了貢獻,而非合作者僅僅坐享其成.節(jié)點進行公共品博弈后,合作者和非合作者節(jié)點均勻分配公共收益,并且根據(jù)自己與鄰居的收益判斷是否改變自己當前的策略.

2.1 公共品博弈模型

在每輪博弈開始時,節(jié)點向自己鄰居廣播博弈信息,其中包括自己上一輪博弈的收益和當前的策略.接收到鄰居的博弈消息后,節(jié)點會統(tǒng)計自己鄰居中合作者和非合作數(shù)量,以自己為中心進行公共品博弈.由于車載自組織網(wǎng)絡中車輛的不斷移動,鄰居的不斷變化,節(jié)點無法準確的給鄰居回饋博弈收益,本文只考慮單一的公共品博弈,每個節(jié)點只從以自己為中心的博弈中得到收益.

假設每輪博弈合作者的投資金額為1.在第t輪博弈時,節(jié)點i的博弈度數(shù)為ki(t),博弈的倍增系數(shù)為r,鄰居當中合作者的個數(shù)為nc(t).則節(jié)點i作為合作者和非合作者在該輪的博弈收益為

2.2 策略選擇

每個節(jié)點會根據(jù)自己與鄰居的收益決定是否更改自己當前的策略.眾所周知,具有理性和自私性的節(jié)點會更傾向于向成功的鄰居學習而使自己變得更好,本文認為高收益的鄰居更為成功.節(jié)點i會在它的所有鄰居當中隨機選擇一個鄰居與之比較收益,做出是否學習鄰居策略的選擇.本文假設在第t輪博弈時,如果節(jié)點i選擇它的鄰居j進行比較,則節(jié)點i選擇節(jié)點j策略的概率為

其中T為噪聲,代表節(jié)點選擇理性程度,T越小說明節(jié)點越理性.如果T=0,且節(jié)點j的收益比節(jié)點i的收益大,那么節(jié)點i肯定會選擇節(jié)點j的策略作為自己下一階段的策略.如果T=∞,那么節(jié)點i完全隨機的選擇是否更改自己的策略.如果T>0,節(jié)點i也有一定的概率不會選擇節(jié)點j的策略而是保留自己原有的策略.通過之前一系列的研究[9-11],設置T=0.1是最適合的選擇.

3 分組博弈理論模型

節(jié)點博弈時與之交換博弈信息的鄰居被稱為該節(jié)點的博弈鄰居.如果節(jié)點i和節(jié)點j具有相同的博弈鄰居,且兩個節(jié)點互為鄰居,則認為節(jié)點i和j處于同一個博弈團體.

3.1 節(jié)點策略的轉(zhuǎn)換

由公式(1)(2)(3)可以得知,同一個博弈團體中合作者的收益肯定會小于非合作者的收益.如果網(wǎng)絡中只存在一個博弈團體,節(jié)點會逐漸選擇不合作策略.但是當網(wǎng)絡中存在不同的博弈團體時,會出現(xiàn)合作者收益高于非合作者的情況.

圖1 不同博弈團體導致節(jié)點收益的差異性

如圖1所示,編號為C和D的節(jié)點分別代表合作者和非合作者.圖1(a)中所有節(jié)點處于一個博弈團體中,他們具有相同的博弈鄰居.其中合作者會逐漸更改自己的策略向非合作者轉(zhuǎn)變.圖1(b)在節(jié)點總數(shù)和合作者比例相同的情況下?lián)碛?個博弈團體.每個博弈團體由于合作者比例不同導致了節(jié)點收益的差異性.根據(jù)公式(1)(2)可知合作者比例越多的博弈團體中節(jié)點的收益越高,并且隨著倍增系數(shù)r的增大,合作者比例對博弈收益的影響越大.這時會存在合作者收益高于非合作者收益的情況.由于車輛的移動性以及連接各個博弈團體的中間節(jié)點的存在,非合作者在策略選擇時就有可能改變自己的策略.

假設低收益節(jié)點學習高收益節(jié)點策略的概率為1.網(wǎng)絡中有N個隨機移動的節(jié)點,節(jié)點每輪博弈的鄰居完全隨機.其中合作者數(shù)量為NC,非合作者數(shù)量為ND,所有節(jié)點構成一個博弈團體.則合作者與非合作者相互轉(zhuǎn)變的概率為:

如果將節(jié)點分為兩個博弈團體,分別具有NC1和NC2個合作節(jié)點,ND1和 ND2個非合作節(jié)點.假設兩個團體中合作者比例pC1>pC2,且第一個團體中合作者的收益高于第二個團體中非合作者的收益.則合作者與非合作者相互轉(zhuǎn)變的概率為:

針對這些特殊性，在將近一年的工作中，工作隊始終牢固樹立總目標意識，突出“維護穩(wěn)定、建強組織、脫貧攻堅、群眾工作、兵地融合”五項任務，按照“四句話”“4+2”工作要求，發(fā)揮工會自身優(yōu)勢，打好“工”字牌“農(nóng)”字牌，扎實推進“訪惠聚”工作深入開展，堅持用“愛心”“恒心”“耐心”，凝聚起職工群眾一心向黨的“民心”。

將收益高的那個博弈團體分為兩個更小的博弈團體,且pC11>pC12>pC2,則合作者與非合作者相互轉(zhuǎn)變的概率為:

由此可知,對具有相同節(jié)點總數(shù)和合作者比例的不同群體進行博弈時,如果群體中擁有更多合作者比例不同的博弈團體,該群體中的節(jié)點將更傾向于選擇合作策略.

3.2 分組博弈模型

由公式(1)(2)可知團體成員越少時,單個成員策略的改變對團體中合作者比例以及團體收益的影響越大.本文實驗4.1結果顯示車載自組網(wǎng)中節(jié)點平均度較小時合作者比例會更高.從文獻[6]中可以得知網(wǎng)絡中存在一些被大量低度數(shù)節(jié)點圍繞的高度數(shù)節(jié)點(hub節(jié)點)時更容易促進節(jié)點間的合作.在連通性越強的網(wǎng)絡中,hub節(jié)點能與更多普通節(jié)點的進行博弈,hub節(jié)點的高合作性能夠促進普通節(jié)點產(chǎn)生合作行為.結合相關研究和前文的分析,本文提出了一種基于分組的公共品博弈理論模型.

在分組博弈模型中,將博弈鄰居的個數(shù)稱為節(jié)點的博弈度數(shù),所有節(jié)點與它們的博弈鄰居組成的網(wǎng)絡拓撲稱為博弈拓撲.分組博弈模型把網(wǎng)絡中所有節(jié)點隨機分為n個小組.將第1組的節(jié)點作為博弈hub節(jié)點,它們與所有的鄰居交換博弈信息而具有較高的博弈度數(shù).其余普通節(jié)點只與鄰居中同組的節(jié)點進行博弈,從而降低了普通節(jié)點的博弈度數(shù).通過分組博弈將實際的網(wǎng)絡拓撲改變成一種少量高度數(shù)節(jié)點被大量低度數(shù)節(jié)點圍繞的博弈拓撲.

網(wǎng)絡中的節(jié)點在每個時間單位進行一輪博弈.在每輪博弈開始時,節(jié)點向自己的鄰居發(fā)送博弈信息.博弈信息中包含節(jié)點的博弈策略、博弈收益以及分組編號.hub節(jié)點接收所有收到的博弈信息,而普通節(jié)點只接收分組編號與自己相同以及hub節(jié)點發(fā)送的博弈信息.節(jié)點將收到信息的發(fā)送方作為本輪的博弈鄰居.

圖2 節(jié)點普通博弈和分組博弈的博弈拓撲

4 模擬實驗及分析

為了探討車載自組織網(wǎng)絡中分組博弈的性能及進行相關的優(yōu)化,本文利用SUMO仿真工具在自定義的650(m)×650(m)的地圖中產(chǎn)生由 N(50,100,300)個節(jié)點組成的網(wǎng)絡,模擬車輛密度大的城市交通中車輛的運行軌跡并使用NS2仿真工具實現(xiàn)節(jié)點博弈信息的交換.地圖中共有4x3條雙向道路以及交叉產(chǎn)生的12個十字路口,每兩條平行道路之間的距離超出了車輛的傳輸范圍,模擬地圖的部分區(qū)域如圖3所示.

圖3 模擬實驗局部地圖

模擬時將每個節(jié)點看成一個車輛,隨機設置每個車輛的初始位置和移動路徑.在初始的時候以50%的概率隨機設置每個節(jié)點的合作策略.每隔一個時間單位進行一輪博弈,當網(wǎng)絡中合作者比例達到平衡值時,統(tǒng)計博弈過后合作者所占的比例.本文對不同的網(wǎng)絡拓撲進行重復多次實驗,以保證實驗結果的一致性,實驗統(tǒng)計出的所有數(shù)值都是多次實驗后的平均值.為了保證模擬實驗更為真實有效,本文在道路路口設置了紅綠燈并且設置了道路最大速度以及車輛加速度來限制車輛的移動.車輛會在十字路口大量聚集產(chǎn)生高的車輛密度.各參數(shù)如表1所示.

表1 模擬實驗參數(shù)

4.1 車輛密度對合作者比例的影響

圖4顯示了使用公共品博弈在不同節(jié)點密度和消息傳播范圍下,合作者比例隨倍增系數(shù)r的變化規(guī)律.由圖中可知隨著倍增系數(shù)r的增大,網(wǎng)絡中合作節(jié)點比例會增多.較小的節(jié)點密度和傳輸范圍會造成較小的節(jié)點平均度.在車輛數(shù)量為100時,相對小的傳輸范圍能夠提升合作者比例.但是當節(jié)點數(shù)量為50且傳輸范圍較小時合作者比例反而較低.通過分析得知,低的節(jié)點平均度數(shù)能促進網(wǎng)絡中節(jié)點的合作行為,但是過低的節(jié)點平均度數(shù)可能造成網(wǎng)絡中孤立節(jié)點和孤立團體的存在,影響網(wǎng)絡拓撲的連通性.網(wǎng)絡中孤立的節(jié)點和團體由于缺乏與網(wǎng)絡中其他節(jié)點博弈信息的交換而導致不合作行為的發(fā)生,并且很難改變自己的策略.

圖4 不同網(wǎng)絡狀態(tài)下的公共品博弈

4.2 車載自組織網(wǎng)絡中的分組博弈

圖5 顯示了具有100個節(jié)點,傳輸范圍為250 m的網(wǎng)絡中,使用分組博弈在分組不同時合作者比例隨倍增系數(shù)r的變化趨勢.根據(jù)與實驗4.1的比較,可以明顯的觀察出在車載自組織網(wǎng)絡中使用分組博弈極大地促進了節(jié)點的合作行為,特別是當分組較多的時候.將100個節(jié)點分成10個組時,在r取值很小時網(wǎng)絡就達到了幾乎全合作的狀態(tài).

圖5 分組博弈中分組個數(shù)對合作者比例的影響

4.3 分組個數(shù)對合作者比例的影響

圖6 顯示了使用分組博弈在不同節(jié)點密度和通信范圍下,倍增系數(shù)r為4時,合作者比例隨著分組個數(shù)的變化趨勢.從圖中可知,隨著分組個數(shù)的增多,合作者比例會達到一個最優(yōu)值,并且上升過程變化較快.當節(jié)點密度越大時,維持最優(yōu)效果的分組選擇會越多.當合作者比例達到和維持最優(yōu)值以后會出現(xiàn)下降的趨勢.分析得出,過多的分組會造成網(wǎng)絡拓撲的不連通性.在節(jié)點個數(shù)等于50,傳輸范圍為100 m的網(wǎng)絡中,由于網(wǎng)絡拓撲的不連通性,節(jié)點很難呈現(xiàn)較好的合作行為.雖然車輛的移動性會對不連通性進行彌補,但還是應盡可能的避免這種情況的發(fā)生.

圖6 不同節(jié)點密度和通信范圍下的分組博弈

4.4 節(jié)點平均度數(shù)對合作者比例的影響

圖7 、8、9、10顯示了在分組博弈中不同節(jié)點密度和通信范圍下,r為4時,節(jié)點的平均度數(shù)和合作者比例隨分組個數(shù)的變化趨勢.其中只計算了普通節(jié)點的平均度數(shù),并不將hub節(jié)點的度數(shù)考慮在內(nèi).將節(jié)點平均度數(shù)與合作者比例進行對比分析可以發(fā)現(xiàn),當普通節(jié)點平均度在1.8-2.2左右的時候,合作者比例能夠達到最優(yōu).當節(jié)點平均度數(shù)高于這個范圍時,由于過高的節(jié)點平均度,合作者比例會快速的降低.當節(jié)點平均度低于這個范圍時,節(jié)點的不連通性會導致合作者比例緩緩的降低.

圖7 50個節(jié)點100傳輸范圍下的分組博弈

圖8 50個節(jié)點250傳輸范圍下的分組博弈

圖9 100 個節(jié)點 100 m 傳輸范圍下的分組博弈

圖10 100 個節(jié)點 250 m 傳輸范圍下的分組博弈

本文只在特定的高密度場景下進行了相關實驗.在無紅綠燈路口,高速公路,停車場等其他場景下以及使用不同車輛移動模型時,雖然車輛速度,移動行為,車輛密度均會有所不同,但是節(jié)點只需要獲取通信范圍內(nèi)的鄰居以及鄰居分組編號就能進行分組博弈,故在多種場景下都可以使用本文方法,降低節(jié)點的博弈度數(shù),促進節(jié)點進行合作.

5 結束

本文針對公共品博弈模型在高車輛密度區(qū)域中促進節(jié)點合作不理想的情況,通過實驗得知較小的節(jié)點博弈度數(shù)能促進網(wǎng)絡中節(jié)點的合作行為,基于此提出了一種分組博弈理論模型.該模型在博弈拓撲上可以降低節(jié)點博弈平均度數(shù).實驗結果表明,在車輛密度特別大的情形下,該模型有利于網(wǎng)絡中的個體選擇合作策略.通過合理的分組,將網(wǎng)絡中節(jié)點的平均博弈度控制在1.8-2.2時能很好的促進個體之間的合作.車輛密度越大的網(wǎng)絡對維持最優(yōu)值的分組選擇更多.

本文只限定于分組個數(shù)固定的分組博弈模型研究,網(wǎng)絡中的節(jié)點擁有相同的分組選擇,實驗表明在車輛密集區(qū)域能取得很好的博弈效果.事實上,車載自組織網(wǎng)絡的網(wǎng)絡拓撲具有更豐富的結構,從鄉(xiāng)村網(wǎng)絡拓撲到高速公路拓撲都具有各自的特性.在未來的工作中,本文希望能夠在多場景下進行模擬和優(yōu)化分組博弈模型,使得節(jié)點根據(jù)自身博弈度數(shù)的變化動態(tài)地調(diào)整適合于自己的分組個數(shù).

1劉伎昭,王泉.車載自組網(wǎng)中聯(lián)盟博弈的虛假數(shù)據(jù)檢測策略.西安交通大學學報,2015,49(2):69–73,134.[doi:10.7652/xjtuxb201502012]

2Chai R,Lv Y,Yang B,et al.Cooperative game based relay vehicle selection algorithm for VANETs.Proc.of the 14th International Symposium on Communications and Information Technologies.Incheon,South Korea.2014.30–34.

3Kapade N.TLC:Trust point load balancing method using coalitional game theory for message forwarding in VANET.Proc.of 2014 IEEE Global Conference on Wireless Computing and Networking.Lonavala,India.2014.160–164.

4Zhang L,Jia SC,Liu ZS,et al.Bus-Ads:Bus trajectorybased advertisement distribution in Vanets using coalition formation games.IEEE Systems Journal,2015,PP(99):1.

5Shivshankar S,Jamalipour A.Effect of altruism and punishment on selfish behavior for cooperation in vehicular networks.Proc.of the 1st IEEE International Conference on Communications in China.Beijing,China.2012.653–658.

6Shivshankar S,Jamalipour A.An evolutionary game theorybased approach to cooperation in VANETs under different network conditions.IEEE Trans.Vehicular Technology,2015,64(5):2015–2022.[doi:10.1109/TVT.2014.2334655]

7Gao J,Li Z,Wu T,et al.Diversity of contribution promotes cooperation in public goods games.Physica A:Statistical Mechanics and its Applications,2010,389(16):3166–3171.[doi:10.1016/j.physa.2010.04.018]

8Zhang HF,Shi DM,Liu RR,et al.Dynamic allocation of investments promotes cooperation in spatial public goods game.Physica A:Statistical Mechanics and its Applications,2012,391(8):2617–2622.[doi:10.1016/j.physa.2011.12.005]

9Lei C,Wu T,Jia JY,et al.Heterogeneity of allocation promotes cooperation in public goods games.Physica A:Statistical Mechanics and its Applications,2010,389(21):4708–4714.[doi:10.1016/j.physa.2010.06.002]

10Cao XB,Du WB,Rong ZH.The evolutionary public goods game on scale-free networks with heterogeneous investment.Physica A:Statistical Mechanics and its Applications,2010,389(6):1273–1280.[doi:10.1016/j.physa.2009.11.044]

11Zhang HF,Yang HX,Du WB,et al.Evolutionary public goods games on scale-free networks with unequal payoff allocation mechanism.Physica A:Statistical Mechanics and its Applications,2010,389(5):1099–1104.[doi:10.1016/j.physa.2009.11.029]

Research on Evolutionary Game Theory for Cooperative Behavior of Node in VANETs

ZENG Xi-Kai,DING Qing
(School of Software Engineering,University of Science and Technology of China,Heifei 230051,China)

Studies in vehicular ad hoc networks using public goods game theory to enhance the cooperation show that the performance of cooperation in those types of network would have been poor in the areas with high vehicle density.In this paper,the result of simulation shows that the certain range of degrees of vehicle will enhance the cooperation in network.Therefore,we propose a grouping game model with the concept of the game degree and game topology to enhance the cooperation in the areas with high vehicle density.This model can change the game topology and reduce the game degree of nodes.The experimental results show that using this model in any high density regions of vehicles can significantly enhance the performance of cooperation in the network.

grouping public goods game; vehicular ad hoc network; average degree; cooperation of node

曾熙凱,丁箐.車載自組織網(wǎng)絡中節(jié)點合作行為的博弈研究.計算機系統(tǒng)應用,2017,26(10):270–275.http://www.c-s-a.org.cn/1003-3254/6029.html

2017-02-05; 采用時間:2017-03-02