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服務質量。