VANET中基于TUU博弈的合作激勵機制

孫玉潔，李一洋，任 鈞，孟海賓，苗 成

（北方自動控制技術研究所，太原 030006）

0 引言

VANET具有無線自組網(wǎng)［1］的一般特征，但同時也存在很大的差異：1）車輛節(jié)點數(shù)目巨大、分布區(qū)域廣泛，具有豐富的外部輔助信息，例如車載定位/導航、激光雷達、視覺傳感裝置等；2）車輛只能沿著道路作高速、受限、約束運動；3）節(jié)點間的網(wǎng)絡拓撲變化頻繁，并且頻繁的拓撲變化又將導致頻繁的網(wǎng)絡分裂［2］；4）網(wǎng)絡極易受駕駛員自私行為以及周圍環(huán)境，包括是否存在障礙物等因素的影響［3］，由于VANET存在這些特點，將會導致相應的問題：VANET車輛節(jié)點數(shù)目巨大且分布區(qū)域廣泛，不同區(qū)域的拓撲結構和通信狀態(tài)都隨時間動態(tài)變化。通信狀態(tài)良好的區(qū)域通信鏈路完整，消息交付率高，而通信能力差的VANET區(qū)域里，車輛發(fā)出的消息不能夠成功地交付到目的車輛，或者消息傳送的延時增大，消息丟包率高，尤其是很多重要的用戶消息會因網(wǎng)絡通信能力不強而丟棄，這大大降低了網(wǎng)絡的Qos服務質(zhì)量。因此，良好的VANET通信狀態(tài)不僅能夠提高V2V通信的效率，還能夠為數(shù)據(jù)融合、實時同步和多媒體播放等車聯(lián)網(wǎng)應用提供支撐，而且也有利于延長網(wǎng)絡的生命周期。綜上，VANET通信能力的研究是VANET的一個基本問題，是保證網(wǎng)絡性能的關鍵所在。

由于車輛節(jié)點的自主性，部分節(jié)點可能為了節(jié)省帶寬和緩存等資源而拒絕轉發(fā)消息，這種拒絕轉發(fā)消息的自私行為會引起拓撲變化更加明顯。

1）VANET拓撲結構離散化，如圖1所示：圖1（a）表示所有車輛節(jié)點合作時的VANET拓撲，可以看出此時所有車輛之間的消息都能確?？煽總鬟f到網(wǎng)絡中的任意車輛上；圖1（b）表示網(wǎng)絡中存在自私節(jié)點Selfish Node時，網(wǎng)絡瞬間缺乏端到端的完整鏈路，圖中最左邊的車輛只能將消息轉發(fā)到至多兩個車輛節(jié)點。圖1說明自私行為嚴重影響了VANET的連通性，降低了VANET的服務性能。

圖1 VANET拓撲結構離散化圖

2）自私節(jié)點在一定程度上可以避免廣播風暴，如圖2所示：圖2（a）中，主干道上總共有20個車輛節(jié)點，車輛移動速度緩慢，VANET拓撲變化不明顯。如果所有節(jié)點都合作參與消息的轉發(fā)，源節(jié)點發(fā)出的消息會在整個網(wǎng)絡epidemic式傳播，所有車輛都將接受到的消息傳送給它的鄰居節(jié)點，因此，很顯然會導致網(wǎng)絡的廣播風暴；圖2（b）中，灰色節(jié)點為Selfish Nodes，因為VANET中部分節(jié)點的自私存在，從圖中可以看出，在自私節(jié)點主動獨立出VANET后，網(wǎng)絡擁塞現(xiàn)象得到緩解，拓撲結構清晰明朗，鏈路完整且不冗余，不僅可以保證源節(jié)點到目的節(jié)點的消息傳遞，而且能夠降低網(wǎng)絡吞吐量，降低傳遞延時。雖然少量的自私節(jié)點能夠在一定程度上提高VANET的服務性能，但是如果網(wǎng)絡中的自私節(jié)點數(shù)量過多，即使VANET中存在大量的車輛節(jié)點，也不能保證稠密VANET的連通性。因此，必須構建一種合適的激勵機制［4-5］，通過監(jiān)測網(wǎng)絡當前的通信狀態(tài)，動態(tài)地控制自私節(jié)點充當中間轉發(fā)節(jié)點的數(shù)量，從而有效地控制整個VANET的通信鏈路，保證網(wǎng)絡通信狀態(tài)良好。

圖2（a）稠密VANET 圖2（b）存在自私節(jié)點的VANET

然而，為了保證激勵機制的合理實施，必須準確評估當前VANET的通信狀態(tài)，D-S證據(jù)理論方法是目前態(tài)勢評估最常用的方法：對于VANET整個數(shù)據(jù)處理系統(tǒng)而言，多方面多角度地收集車輛節(jié)點的數(shù)據(jù)信息，最終是為了對網(wǎng)絡當前的通信狀態(tài)做出一個最終的決策，通過數(shù)據(jù)融合后的更準確更可靠的決策執(zhí)行后續(xù)的激勵機制。

1 VANET通信能力的評估

近年來，信息融合已經(jīng)成為信息處理領域研究的熱點問題，對于多信息源的分布式檢測以及數(shù)據(jù)融合的各種方法，人們已經(jīng)在理論上做了大量的研究，而在VANET的實際場景中，利用車輛信息的數(shù)據(jù)融合結果進行網(wǎng)絡決策或者預測的研究卻很少。如何利用VANET數(shù)據(jù)處理中心（NCC）獲得的網(wǎng)絡信息來動態(tài)、準確地判定VANET內(nèi)各個ZONE當前的通信狀態(tài)是實現(xiàn)該篇論文的關鍵問題，也是執(zhí)行TUU博弈模型的前提條件。

1.1 D-S證據(jù)理論

VANET由于自身的動態(tài)拓撲變化，每個ZONE在未來某個時刻的通信狀態(tài)充滿了未知性，不適合利用簡單的概率理論對VANET隨時間不確定變化的網(wǎng)絡通信狀態(tài)進行判定，而D-S證據(jù)理論針對這種未知引起的不確定性充分發(fā)揮了自身的優(yōu)勢，通過給定的證據(jù)、利用信度函數(shù)和似然函數(shù)兩個數(shù)值組成的區(qū)間來表示對命題的信任度，通過合成規(guī)則對不同證據(jù)產(chǎn)生的信息進行融合，因此，D-S數(shù)據(jù)融合方法能夠很好地適應于通信狀態(tài)多變的VANET，通過給定的網(wǎng)絡證據(jù)指標，每個NCC計算出的概率值表示對網(wǎng)絡通信狀態(tài)的信任度，通過簡單的合成規(guī)則就能得到準確、可靠的當前網(wǎng)絡通信狀態(tài)。

1.2 ZONE的網(wǎng)絡狀態(tài)的判定

根據(jù)第1部分討論的D-S證據(jù)理論及其組合規(guī)則，基于D-S證據(jù)理論的信息融合方法主要包括3個步驟：

1）融合問題的建模，即確定融合問題的識別框架。VANET的通信狀態(tài)結果組成了識別框架Θ=（通信能力強S，通信能力弱D），信息源分別給出二者在識別框架上的基礎概率分配。

2）信息的融合過程。

3）根據(jù)融合結果，采用一定的判別準則，確定獲得最大支持度的可能性，并做出相應的決策。具體流程圖如圖3所示。

圖3 基于D-S證據(jù)理論的信息融合過程

利用D-S證據(jù)理論進行信息融合：

焦元有兩個，分別為S，D。令S表示通信能力強，D表示通信能力弱，其識別框架為Θ={S，D}。證據(jù)數(shù)有 4個，m1=m度分布，m2=m網(wǎng)絡鏈路數(shù)，m3=m聚類系數(shù)，m4=m平均路徑長度。

預估方法不確定性的計算公式為：

其中，k∈（0，1）為歸一化因子。信度函數(shù)的物理含義為證據(jù)對S或D的支持程度，因此，得到下述判決準則：

數(shù)據(jù)處理中心能夠快速通過此方法，準確地判斷每個ZONE的網(wǎng)絡通信狀態(tài)，即通信能力強S或是通信能力弱D。

2 基于TUU博弈的激勵機制

2.1 基于TUU博弈的稀疏VANET激勵機制

在稀疏VANET中，發(fā)送、接收或者轉發(fā)數(shù)據(jù)包都是隨機過程。如果所有節(jié)點合作，即節(jié)點轉發(fā)接收到的數(shù)據(jù)包，那么所有節(jié)點將會受益，但是每個節(jié)點也將會耗費一些成本來轉發(fā)鄰居節(jié)點的數(shù)據(jù)包。在合作網(wǎng)絡中，一個自私節(jié)點受益會更多，因為它不用消耗自己的資源來轉發(fā)其他節(jié)點的數(shù)據(jù)包。然而，如果所有節(jié)點都自私，那么所有節(jié)點就會僅僅發(fā)送自身的數(shù)據(jù)包而不轉發(fā)鄰居節(jié)點的數(shù)據(jù)包，導致稀疏VANET中的數(shù)據(jù)包全部不能成功送達目的節(jié)點，從而引起網(wǎng)絡嚴重癱瘓。因此，利用博弈方法的激勵機制來解決稀疏VANET的連通性問題。

假設鄰居關系是對稱的，通信信道也是雙向的。從源節(jié)點到目的節(jié)點是通過中間節(jié)點轉發(fā)數(shù)據(jù)包的。假設每個節(jié)點有一個唯一的真實的身份，可轉移支付聯(lián)盟博弈（N，v）中，參與者集合N定義為VANET中一個區(qū)域ZONE內(nèi)的所有車輛，v是每個非空參與者集合的聯(lián)盟總收益。對于每個節(jié)點，其策略空間是［合作，叛變］，代表了中間節(jié)點i在接收到數(shù)據(jù)包后，是選擇轉發(fā)還是丟棄。使用博弈之前，區(qū)域ZONE中每個車輛都為一個單一聯(lián)盟。效用函數(shù)綜合考慮了平均連接率、延時、與目的節(jié)點之間的距離以及節(jié)點的信譽值。每個節(jié)點通過計算自身效用函數(shù)，得出：節(jié)點加入一個更大的聯(lián)盟比單獨行動獲得更大的收益，從而加入聯(lián)盟進行合作，最終，博弈的結果使得VANET區(qū)域中的所有節(jié)點形成一個大聯(lián)盟。制定節(jié)點i在k階段的平均收益如下：

對任意成員 i、j，πji是 i與 j合作（與其他成員合作）的收益，δji是i與j合作造成的損失，所以，πji-δji是 i與 j合作的凈獲益；同理，πji-δji是 j與 i合作的凈獲益；ai是i對聯(lián)盟所作貢獻的努力程度。因此，補償給i的總的凈收益或從i之處取出補償其他成員的總的凈收益（即Ti值可正也可負）就是i與其他合作成員全部凈收益之差的和，依據(jù)i對聯(lián)盟所作貢獻的努力程度再次分配。在雙方的合作中獲益較多的一方應給獲益較少的一方一定量的利益補償，同理，不合作中獲益較多的一方應從獲益較少的一方那里得到利益補償，只有這樣才能有望達成合作協(xié)議。同時，獲益一方在補償受損一方之后的福利應該仍然比參加合作前有所提高，即

表1 收益分配中各參數(shù)的含義

其中，cpi是節(jié)點 i的平均連接率。把 Ni（k）作為節(jié)點 i在k階段時的鄰居集，節(jié)點i保持每個鄰居節(jié)點j的動態(tài)數(shù)據(jù)：

通過這種轉發(fā)率的計算可以從單一節(jié)點得出此次交易過程中，一個節(jié)點是合作的還是自私的。最后，節(jié)點i評價節(jié)點j的平均連接率為：

2.2 基于TUU博弈的稠密VANET激勵機制

上一部分針對稀疏VANET，利用基于TUU博弈的激勵機制，合理激勵區(qū)域ZONE中所有節(jié)點積極合作，最終形成穩(wěn)定大聯(lián)盟，不但能夠增加網(wǎng)絡連接的機會，而且能夠使自私節(jié)點快速恢復到區(qū)域VANET中，從而增加消息傳遞的成功率和稀疏VANET的連通性。然而，在稠密VANET中，由于VANET節(jié)點密度過大，車輛的移動特征不明顯，如果采用稀疏VANET中的激勵機制促使節(jié)點合作，不但會出現(xiàn)消息在密集ZONE內(nèi)的頻頻交互，浪費大量的帶寬、緩存等資源的情況，還使得自私節(jié)點被迫參與消息的轉發(fā)收益甚小。因此，針對稠密VANET，本文提出一種新的機制——自私容忍激勵機制。這種激勵機制應用了可轉移效用博弈理論，提出選擇區(qū)域中具有高投遞率、高信譽值、低移動性的節(jié)點作為代理節(jié)點的概念［4］，選擇區(qū)域代理節(jié)點作為中間轉發(fā)節(jié)點，能夠很好地控制中間轉發(fā)節(jié)點過多導致出現(xiàn)消息頻頻交互的情況，適當容忍稠密VANET中自私節(jié)點拒絕轉發(fā)數(shù)據(jù)包的情況，減少了網(wǎng)絡中的冗余包，有效地降低了網(wǎng)絡負載，同時保證了網(wǎng)絡的連通性，提高了網(wǎng)絡性能。

假設每個節(jié)點的通信范圍是固定的，且節(jié)點一次轉發(fā)消息的所耗費成本cost都是相同的?？赊D移支付博弈（N，v）中，參與者集合N定義為ZONE中所有代理節(jié)點的集合，v是每個非空參與者集合的聯(lián)盟總收益。博弈開始前，由于每個節(jié)點對網(wǎng)絡信息的不確定性，任意選擇ZONE內(nèi)某一節(jié)點為代理節(jié)點。代理節(jié)點i的效用函數(shù)如下：

Pr是在此博弈階段節(jié)點i被選為區(qū)域ZONE內(nèi)的代理節(jié)點的概率。Wi是代理節(jié)點i轉發(fā)一個消息所得的報酬，cost是轉發(fā)一個消息耗費的成本，ui（k-1）是代理節(jié)點i在第k-1階段的效用值，ut是每個階段博弈的效用閾值。稠密VANET自私容忍激勵機制的博弈算法具體實現(xiàn)過程如下：

1）初始化階段。NCC選擇任意車輛節(jié)點為ZONE內(nèi)初始代理節(jié)點。設置計時器n=1，NCC存儲ZONE內(nèi)每個車輛節(jié)點的效用值，ut的初始閥值為初始代理節(jié)點的效用值utmin；

圖4 稠密VANET自私容忍激勵機制的博弈算法

2）在ZONE內(nèi)最初被NCC選擇的那個代理節(jié)點為一個單人聯(lián)盟。TUU博弈使得代理節(jié)點組成的聯(lián)盟不斷增大，即不斷有新的效用值高的節(jié)點加入聯(lián)盟。由于稠密VANET的網(wǎng)絡特點，不需要所有的節(jié)點都充當代理節(jié)點，因此，在每一階段博弈結尾，NCC都要將每個代理節(jié)點的效用值ui與效用閾值ut進行比較，如果出現(xiàn)ui大于ut，表示該節(jié)點可以加入聯(lián)盟成為代理節(jié)點，置計時器n累加1個單位；

3）如果計數(shù)器在某一博弈階段開始時，NCC檢測到n≥nmax=η*N，表示稠密VANET中已經(jīng)存在過多的代理節(jié)點，從而使得網(wǎng)絡消息投遞的成功率下降，消息頻頻交互，此時應當立即調(diào)整聯(lián)盟中代理節(jié)點的效用閾值ut，其中N表示網(wǎng)絡節(jié)點總數(shù)目，η表示網(wǎng)絡允許的代理節(jié)點占全網(wǎng)節(jié)點的最大比重；

4）然后不斷動態(tài)調(diào)整效用閾值ut，使整個網(wǎng)絡中代理節(jié)點組成的聯(lián)盟達到穩(wěn)定，從而使網(wǎng)絡性能得到改善。具體流程如圖4所示。

3 仿真

利用仿真平臺評估TUU-D激勵機制，并與DARWIN激勵機制和ICASRUS激勵機制進行仿真對比。

地圖：赫爾辛基市地圖（MovementModel.world-Size=4 500，3 400）；

移動模型：ShortestPathMapBasedMovement（合作節(jié)點100個，自私節(jié)點30個）；

路由協(xié)議：EpidemicRouter；

圖5 自私節(jié)點比例不同的網(wǎng)絡吞吐量

在圖5中，探討自私節(jié)點的比例對網(wǎng)絡節(jié)點轉發(fā)率的影響。值得注意的是，即使自私節(jié)點占全網(wǎng)節(jié)點的比例達到90%，在本文機制中，合作節(jié)點比自私節(jié)點能達到一個更的好轉發(fā)率。事實上，網(wǎng)絡轉發(fā)率指標的提高，很大程度上取決于網(wǎng)絡中自私節(jié)點的比例。

圖6 激勵機制對合作節(jié)點的轉發(fā)率

圖7 激勵機制對自私節(jié)點的轉發(fā)率

圖6、圖7分別描述了3種激勵機制對合作節(jié)點和自私節(jié)點的轉發(fā)率的影響。對于合作節(jié)點來說，本文機制相對于DARWIN機制和ICARUS機制在轉發(fā)率方面提高10%左右，尤其是對于仿真的前半階段（Time Slot＜500），在仿真的后半階段，這種差別逐漸削弱，但本文機制在相同的設置下能夠達到更高的轉發(fā)率（約為1%）。對于自私節(jié)點來說，情況發(fā)生顯著變化，自私節(jié)點轉發(fā)率的下降趨勢說明3中激勵機制都有效地控制了節(jié)點的自私行為，而本文機制懲罰力度最大，下降趨勢也最明顯，在整個仿真階段下降約30%。說明激勵機制更加有效。

圖8 激勵機制“恢復”自私節(jié)點的能力

圖8觀察了3種激勵機制“恢復”自私節(jié)點的能力。正如論文中提到，被NCC檢測到有自私行為的節(jié)點不能發(fā)送自身的數(shù)據(jù)包，因此，需要積極參與合作。圖8枚舉了3種激勵機制在仿真過程中節(jié)點表現(xiàn)出的自私性。從圖8中可以看出，DARWIN機制在約920個時隙時依然存在少量自私節(jié)點，I CARUS機制約在800個時隙時存在少量自私節(jié)點，本文機制在350個時隙已經(jīng)達到稀疏VANET中的理想控制指標，因此，本文機制能夠更快速地激勵自私節(jié)點的合作。

4 結論

本文提出了融合DARWIN機制和經(jīng)濟學中TUU博弈模型的新的激勵機制TUU-D機制，通過D-S證據(jù)理論提取影響網(wǎng)絡連通性的特征指標，通過證據(jù)融合動態(tài)判斷網(wǎng)絡狀態(tài)；引入TUU博弈方法，動態(tài)時變地激勵VANET中車輛節(jié)點的移動合作；將提出的激勵機制與經(jīng)典激勵機制作對比，仿真結果證明TUU-D激勵機制能夠在不同的城市場景下保證網(wǎng)絡的連通性，從而確保了網(wǎng)絡Qos服務質(zhì)量。