車載自組織網絡中節點合作行為的博弈研究①

曾熙凱,丁 箐

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

車載自組織網絡中節點合作行為的博弈研究①

曾熙凱,丁 箐

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

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

公共品分組博弈; 車載自組織網; 平均度; 節點合作

1 引言

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

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

2 博弈基礎

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

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

2.1 公共品博弈模型

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

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

2.2 策略選擇

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

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

3 分組博弈理論模型

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

3.1 節點策略的轉換

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

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

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

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

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

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

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

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

3.2 分組博弈模型

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

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

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

圖2 節點普通博弈和分組博弈的博弈拓撲

4 模擬實驗及分析

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

圖3 模擬實驗局部地圖

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

表1 模擬實驗參數

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

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

圖4 不同網絡狀態下的公共品博弈

4.2 車載自組織網絡中的分組博弈

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

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

4.3 分組個數對合作者比例的影響

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

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

4.4 節點平均度數對合作者比例的影響

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

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

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

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

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

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

5 結束

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

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

1劉伎昭,王泉.車載自組網中聯盟博弈的虛假數據檢測策略.西安交通大學學報,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

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

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