機會網(wǎng)絡中基于信譽度懲罰的重復博弈模型

趙宇紅 包鳳蓮,2 王靜宇

1(內(nèi)蒙古科技大學信息工程學院 內(nèi)蒙古 包頭 014010)2(包鋼集團第三職工醫(yī)院 內(nèi)蒙古 包頭 014010)

0 引 言

機會網(wǎng)絡[1]是一種在源與目的節(jié)點間不存在完整通信鏈路，通過節(jié)點間的機會相遇來完成通信的網(wǎng)絡。機會網(wǎng)絡采用“存儲—攜帶—轉(zhuǎn)發(fā)”的路由模式，實現(xiàn)節(jié)點間間歇性連接通信，這顯然需要節(jié)點間的相互協(xié)作。然而，節(jié)點受到自身資源、安全、隱私保護等方面的約束而表現(xiàn)出理性傾向，即節(jié)點追求收益的最大化。而某些節(jié)點一味追求保護與提升自身利益，拒絕或較少為其他節(jié)點提供服務，此時節(jié)點可稱為自私節(jié)點，自私節(jié)點的行為將嚴重影響網(wǎng)絡性能[2]。

目前，解決節(jié)點自私性問題的主要方法為激勵機制。國內(nèi)外常用的激勵機制分為基于虛擬貨幣、基于聲譽和基于博弈論這三類。然而，機會網(wǎng)絡的移動性、拓撲的動態(tài)變化、間歇性連接的特點給以上激勵機制帶來很大挑戰(zhàn)。在基于聲譽的激勵機制中，較難實現(xiàn)監(jiān)測下一跳節(jié)點的轉(zhuǎn)發(fā)行為。在基于虛擬貨幣的激勵機制中，無法保證實時地與第三方認證進行交互和結(jié)算。在基于博弈論的激勵機制中，現(xiàn)有的研究中給出很多策略來激勵雙方以促進節(jié)點間更好的合作，但是，其懲罰策略對節(jié)點并無區(qū)分性，激勵效果不好。

針對上述問題，本文設計了一種基于信譽度懲罰(TTFT)博弈模型，用于機會網(wǎng)絡的節(jié)點協(xié)作激勵。在所構(gòu)建的博弈模型中，博弈雙方根據(jù)網(wǎng)絡環(huán)境中節(jié)點的信譽度來動態(tài)調(diào)整懲罰周期來進行策略博弈，以期獲得模型的收益最大化。

1 相關(guān)工作

文獻[3]提出一種典型的基于聲譽的激勵機制。該模型通過Watchdog[4]監(jiān)測工具完成節(jié)點行為的監(jiān)測，通過聲譽值的比較來激勵節(jié)點協(xié)作。Watchdog用來監(jiān)測、記錄鄰居節(jié)點的行為數(shù)據(jù)，并計算節(jié)點間的聲譽值。通過將其與所設定的閾值比較來決定是否通信，該模型不但增加了硬件需求，同時也沒有考慮節(jié)點共謀攻擊的問題。文獻[5]利用博弈論分析移動自組織網(wǎng)絡中激勵節(jié)點間的協(xié)作，該首先在2個節(jié)點間建立數(shù)據(jù)轉(zhuǎn)發(fā)博弈，對模型提出精煉納什均衡，進一步求出最優(yōu)數(shù)據(jù)轉(zhuǎn)發(fā)策略，提出了依據(jù)信譽度的協(xié)作激勵策略。文獻[6]提出一種解決自私節(jié)點的策略，通過非合作理論來完成對鄰居節(jié)點的自私行為研究。在文獻[7]中，綜述了因節(jié)點的自私行為給無線網(wǎng)絡帶來的問題，特別是利用博弈論對節(jié)點的非合作行為進行了分析和研究。文獻[8]對節(jié)點的不協(xié)作行為設計懲罰機制，進而抵消了節(jié)點從不協(xié)作行為中獲取的收益，該模型對節(jié)點的行為主要采用本地監(jiān)測機制，但由于機會網(wǎng)絡的間歇移動特性導致該模型的激勵效果不好。文獻[9]提出一種基于懲罰機制的重復博弈模型，強調(diào)信任在P2P網(wǎng)絡中的重要性，通過信任值的大小來設置懲罰周期，但是該模型沒有對信任值的獲取給出說明。文獻[10]提出了一種基于懲罰策略的博弈模型，利用一個節(jié)點為網(wǎng)絡中其他節(jié)點提供轉(zhuǎn)發(fā)服務時獲取的收益大于節(jié)點采取不協(xié)作策略時的收益，求得激勵一致性條件。但該模型的懲罰策略沒有進一步對節(jié)點的不協(xié)作行為給予處理，即對節(jié)點的不協(xié)作行為沒有給予適度的懲罰。

2 基于信譽度懲罰策略的博弈模型

針對節(jié)點自私性的問題，目前所提出的基于懲罰策略的博弈論激勵機制沒有考慮到積累的歷史信息對節(jié)點將來行為的影響。本文在懲罰策略中引入節(jié)點的信譽度，通過節(jié)點間的信譽度來定義節(jié)點的懲罰周期，區(qū)分不同信譽累積節(jié)點的不同懲罰程度。本文首先給出博弈的假設條件：

(1) 理性節(jié)點：機會網(wǎng)絡中的節(jié)點以個體利益最大化為目標。

(2) 機會網(wǎng)絡G=(V,E)由理性節(jié)點構(gòu)成，G為連通圖，V={i,j,k,…}為節(jié)點集合，E為鏈路集合，節(jié)點間的通信鏈路為雙向。

(3) 本文討論的是節(jié)點消息轉(zhuǎn)發(fā)時自私性問題，消息丟失的主要原因為節(jié)點間的“不協(xié)作”行為。

(4) 機會網(wǎng)絡運行的時間由一系列離散的時隙t構(gòu)成，一個時隙為一個博弈階段。在任一時隙內(nèi)，單階段博弈可能隨時產(chǎn)生，并且單一時隙長度保證每個消息可傳送到目的節(jié)點。

(5) 每次博弈都遵循相同的規(guī)則和過程。

2.1 基于信譽度的懲罰策略

有效地選擇轉(zhuǎn)發(fā)節(jié)點對于保障機會網(wǎng)絡這樣具備移動性、間歇連接性的網(wǎng)絡的傳輸成功率及改善傳輸延遲是非常重要的，節(jié)點的連接能力、合作表現(xiàn)、所完成的連接量這些信息作為轉(zhuǎn)發(fā)節(jié)點的選擇依據(jù)是客觀且準確的，本節(jié)中定義節(jié)點的信譽度來量化節(jié)點的這些歷史行為，并提出基于信譽度的懲罰策略來解決節(jié)點的自私性問題。為解決在機會網(wǎng)絡中節(jié)點間存在的自私性問題，在本節(jié)中定義信譽度的相關(guān)概念和基于信譽度的懲罰策略。

2.1.1信譽度的相關(guān)概念

本文采用2-hop Ack[11]機制來監(jiān)控節(jié)點的轉(zhuǎn)發(fā)行為?；谝陨媳O(jiān)測到的行為數(shù)據(jù)，提出節(jié)點信譽度來度量節(jié)點的歷史行為，并進一步定義了交互的連通度和滿意度來量化這些行為，節(jié)點的信譽度通過綜合這兩個分量來獲得。

信譽度是描述節(jié)點歷史行為的信息積累。信譽度用C來表示，C∈[0,1]。

(1)

(2)

信譽度Ci,j表示節(jié)點i對j的信譽評價，其計算方法如下：

(3)

式中：α∈[0,1]。α是衡量連通度和滿意度的權(quán)重因子，其值的選取對信譽度的大小有很重要的影響，動態(tài)調(diào)節(jié)了連通能力與協(xié)作表現(xiàn)在信譽度中的比重，本文提出一種基于自適應濾波的方法[12]來確定α取值。其設計原則為：當前階段節(jié)點的信譽度應盡可能接近在最后的信譽度更新階段所得到的平均信譽度，與針對所有通信范圍內(nèi)的節(jié)點信譽值來實現(xiàn)，這是體現(xiàn)動態(tài)系統(tǒng)的最新演化效應，其計算方法如下：

(4)

(5)

當MSE′(α)=0時，可以得到α的解：

(6)

通過式(6)求得α的最佳值，從而可獲得節(jié)點信譽度。由于節(jié)點的信譽度源自對節(jié)點的歷史行為的量化，是對節(jié)點的過去行為的一種體現(xiàn)。因此，當節(jié)點采取“不協(xié)作”的方式時，根據(jù)以往信譽度的不同對其進行不同程度的懲罰，懲罰策略一方面可以激勵節(jié)點為取得未來收益而協(xié)作，也會因為歷史行為表現(xiàn)所引起的不同懲罰力度而激勵節(jié)點在未來為積累更高的信譽而采取更積極且高質(zhì)量的協(xié)作。

2.1.2懲罰策略

信譽度體現(xiàn)節(jié)點歷史行為，當節(jié)點采取“不協(xié)作”行為時，其鄰居節(jié)點會根據(jù)信譽度的不同采取不同程度“處罰”，該“處罰”是通過懲罰周期來體現(xiàn)的。 懲罰周期T的計算方法如下：

T=f(C)+1

(7)

基于信譽度的懲罰策略(TTFT)，其實施過程可描述如下：

(1) 在節(jié)點(i,j)可監(jiān)測條件下，節(jié)點在第一個博弈階段(t=1)選擇策略為(轉(zhuǎn)發(fā)，轉(zhuǎn)發(fā))。

(2) 在t>1博弈階段，如果節(jié)點j在t-1博弈階段選擇不轉(zhuǎn)發(fā)，此時節(jié)點i計算節(jié)點j的信譽度，基于懲罰度轉(zhuǎn)換函數(shù)計算節(jié)點懲罰周期T，在t階段后，j受到鄰居節(jié)點的懲罰。

(3) 在懲罰周期T內(nèi)，鄰居節(jié)點拒絕為j轉(zhuǎn)發(fā)消息，但是節(jié)點j必須無償為鄰居節(jié)點轉(zhuǎn)發(fā)消息，直至懲罰周期結(jié)束；在懲罰期內(nèi)，若節(jié)點j不接受懲罰并且繼續(xù)不轉(zhuǎn)發(fā)消息，則將其懲罰周期設置為無限。

(4) 在懲罰周期結(jié)束后，節(jié)點j與網(wǎng)絡中其他節(jié)點繼續(xù)正常轉(zhuǎn)發(fā)數(shù)據(jù)。

2.2 無限重復報文轉(zhuǎn)發(fā)博弈

單階段博弈過程可表示為一個三元組，Π={P,S,u}，其中博弈參與人集合為P={i,j}，i與j為相遇節(jié)點；節(jié)點的策略空間為S={Si,Sj}，其策略為(轉(zhuǎn)發(fā)(S)，不轉(zhuǎn)發(fā)(US))兩種；節(jié)點的效用函數(shù)為u={ui,uj}，并且節(jié)點的轉(zhuǎn)發(fā)收益大于損耗收益。

根據(jù)博弈論的畫線法[13]論證，該單階段博弈模型與“囚徒困境”相似，此博弈模型的納什均衡為(不轉(zhuǎn)發(fā)，不轉(zhuǎn)發(fā))，但這一穩(wěn)定狀態(tài)顯然無法支持機會網(wǎng)絡通信。由于機會網(wǎng)絡中節(jié)點間的通信是一種長期且動態(tài)變化的過程，單階段博弈顯然不符合節(jié)點的長期活躍需求。所以，基于網(wǎng)絡的時序演化可將單階段博弈擴展為重復博弈，為強化節(jié)點的未來收益，在重復博弈模型引入貼現(xiàn)因子δ，δ體現(xiàn)了節(jié)點對未來收益的期望。

具體博弈模型結(jié)構(gòu)如下。

無限重復博弈：設Π為單階段博弈，機會網(wǎng)絡中節(jié)點間長期報文轉(zhuǎn)發(fā)的交互過程是階段博弈Π的不斷重復，并且在每次階段博弈開始前，博弈參與人在Π(∞,δ)中的收益等于各階段收益現(xiàn)值之和Ui，其計算如下：

(8)

根據(jù)式(8)得到的收益矩陣如表1所示。

表1 無限重復博弈模型收益矩陣

下面，我們來計算并分析節(jié)點采取不同策略時的收益。為了便于分析節(jié)點收益的大小，假設節(jié)點在每個時隙t內(nèi)發(fā)送的消息數(shù)量相同。根據(jù)上述的定義可知，若節(jié)點i在當前博弈階段選擇了“不轉(zhuǎn)發(fā)”策略，那么其預期收益有如下兩種情況：

(9)

(10)

(11)

為激勵理性節(jié)點采取“合作”策略，需要確保其選擇“轉(zhuǎn)發(fā)”策略時所得收益要大于選擇“不轉(zhuǎn)發(fā)”策略時的收益，所以必須同時滿足：

(12)

當節(jié)點采用基于信譽度的懲罰策略時，式(12)可求得重復博弈的納什均衡為(轉(zhuǎn)發(fā),轉(zhuǎn)發(fā))。由于傳統(tǒng)重復博弈無法動態(tài)呈現(xiàn)其演化過程。因此，下一節(jié)將使用演化博弈理論來分析網(wǎng)絡中節(jié)點動態(tài)演化的過程，闡述節(jié)點由不轉(zhuǎn)發(fā)策略向轉(zhuǎn)發(fā)策略轉(zhuǎn)變的過程，并進一步分析該模型的穩(wěn)定性。

3 基于演化博弈論的節(jié)點協(xié)作分析

3.1 構(gòu)建并求解演化博弈模型

由于機會網(wǎng)絡中的節(jié)點同時發(fā)送和接收報文。假設整個網(wǎng)絡中節(jié)點分為兩類：轉(zhuǎn)發(fā)和不轉(zhuǎn)發(fā)節(jié)點。節(jié)點雙方的策略集合均為(轉(zhuǎn)發(fā)(TTFT)，不轉(zhuǎn)發(fā)(NS))。每個節(jié)點通過其他節(jié)點的選擇策略來調(diào)整自身策略以便獲取最大收益。在表示節(jié)點收益時，將TTFT和NS策略分別簡寫為TT和N，收益矩陣如表 2 所示。

表2 演化博弈模型的收益矩陣

根據(jù)收益的貼現(xiàn)計算方法計算收益為式(13)-式(15)。

(13)

(14)

(15)

假設網(wǎng)絡中轉(zhuǎn)發(fā)行為節(jié)點比例為ω，則不轉(zhuǎn)發(fā)行為節(jié)點比例為1-ω。期望收益矩陣可以計算：

(1) 轉(zhuǎn)發(fā)節(jié)點的期望收益為：

φs=ωU(TT,TT)+(1-ω)U(TT,N))

(2) 不轉(zhuǎn)發(fā)節(jié)點的期望收益為：

φN=ωU(N,TT)+(1-ω)U(TT,TT)

(3) 根據(jù)(1)和(2)節(jié)點的期望收益,可求得整體網(wǎng)絡的平均收益為：

ω(1-ω)U(TT,N)+ω(1-ω)U(N,TT)

(16)

根據(jù)式(16)可構(gòu)造協(xié)作節(jié)點的復制動態(tài)方程：

(17)

式(17)闡述演化博弈模型的動態(tài)過程，令F(ω)=0，當U(N,TT)≠0時方程的解為：ω1=0，ω2=1；當U(N,TT)=0時，對于任意ω∈[0,1]都為方程的解。

3.2 基于信譽度懲罰策略的穩(wěn)定性分析

雖然ω1=0、ω2=1都是F(ω)=0的解，但根據(jù)微分方程穩(wěn)定性原理可知：只有F′(ω)<0得到的解才具有穩(wěn)定性。下面分別對納什均衡解的穩(wěn)定性進行分析。

1) 在F(ω)=0時，任意ω∈[0,1]為其納什均衡的解，并且恒有F′(ω)=0。因此，ω∈[0,1]都是動態(tài)穩(wěn)定均衡解，此時復制動態(tài)方程的動態(tài)演化相位圖如圖1所示。

圖1 ω∈[0,1]時的動態(tài)演化相位圖

2) 在F(ω)=0，當U(N,TT)≠0時，ω1=0、ω2=1為納什均衡解，當F′(ω)=(1-2ω)U(N,TT)可求得：

圖2 ω1=0時動態(tài)演化相位圖

(2) 當U(N,TT)>0，可知F′(ω1=0)>0，F(xiàn)′(ω2=1)<0，因此，ω2=1為唯一的演化穩(wěn)定策略。

圖3 ω2=1時動態(tài)演化相位圖

綜上所述，在重復博弈過程中，節(jié)點的自私行為將逐漸轉(zhuǎn)化為協(xié)作行為。由演化博弈的穩(wěn)定性可知，即使網(wǎng)絡中自私節(jié)點比例較多，經(jīng)過TTFT懲罰策略的多次博弈后，其自私節(jié)點將演化成合作節(jié)點，促進節(jié)點間的協(xié)作，達到博弈模型的納什均衡，從而使網(wǎng)絡系統(tǒng)達到穩(wěn)定狀態(tài)。

4 仿真實驗

為驗證本文所提出的TTFT模型的有效性，采用ONE[14]模擬器來仿真實驗。模擬實驗的數(shù)據(jù)集為Infocom2006；節(jié)點間監(jiān)測通信范圍為10 m；移動速度為0.5～2.5 m/s；數(shù)據(jù)的大小為1 024 KB；節(jié)點緩存大小均為15 MB。實驗中為模擬無限博弈模型，在有限次博弈中未指定結(jié)束時間，為保障結(jié)果的可重現(xiàn)及穩(wěn)定性，實驗數(shù)據(jù)均進行了50組，取平均結(jié)果。

首先，利用2-hop Ack算法確定節(jié)點是否具有自私性以及自私節(jié)點所占比例。接下來，設定該實驗采用的路由協(xié)議Epidemic[15]，實驗分別分析了貼現(xiàn)因子δ和懲罰周期T對協(xié)作性的影響。最后，在常用路由協(xié)議中，將本文提出模型與現(xiàn)有常用博弈模型對比，并給出了仿真結(jié)果。

(1) 節(jié)點的貼現(xiàn)因子δ對協(xié)作行為的影響。合作收益及博弈雙方的貼現(xiàn)因子是影響協(xié)作機制演化的關(guān)鍵因素。圖4顯示了傳輸成功率和平均延遲隨貼現(xiàn)因子δ變化的情況。

(a) 傳輸成功率的對比

(b) 平均延遲的對比圖4 貼現(xiàn)因子對網(wǎng)絡性能的影響

(2) 懲罰周期T對協(xié)作行為的影響。圖5是在δ=1、不同比例自私節(jié)點情況下，節(jié)點間消息傳輸?shù)某晒β省Ｔ趹土P周期T=4時，節(jié)點間的傳輸成功率最高，激勵效果最好。即在一定的懲罰范圍內(nèi)，增加T將有利于提高網(wǎng)絡轉(zhuǎn)發(fā)率。但若懲罰周期T過長，即其周期長度超過實驗中節(jié)點間相遇次數(shù)的最大值，會導致網(wǎng)絡整體性能下降。因此，網(wǎng)絡傳輸中還需要根據(jù)自身信譽度來適應具體的T值。

圖5 不同懲罰周期T下網(wǎng)絡節(jié)點傳輸成功率對比

(3) 懲罰機制對協(xié)作行為的影響。機會網(wǎng)絡中，根據(jù)節(jié)點間不同的轉(zhuǎn)發(fā)策略，目前常用的路由算法可分為基于冗余的算法和基于效用的算法，其代表分別為Epidemic和Prophet[16]。Epidemic算法中每個節(jié)點將需傳送的消息保存在緩存中，當兩節(jié)點相遇的時候交換彼此的緩存內(nèi)容。Prophet算法通過節(jié)點間相遇的歷史信息來計算與目的節(jié)點相遇概率，選擇概率高的節(jié)點為下一跳轉(zhuǎn)發(fā)的節(jié)點。為驗證懲罰策略對協(xié)作激勵的影響以及在不同路由協(xié)議中的適用性，節(jié)點在無任何懲罰策略、冷酷策略[13](Grim Strategy，GS)、針鋒相對策略[17](Tit For Tat strategy，TFT)和本文的信譽度懲罰策略TTFT進行了傳輸仿真實驗。圖6顯示在不同自私節(jié)點比例和不同懲罰策略下節(jié)點傳輸成功率的對比。

(a) Epidemic路由協(xié)議與不同懲罰策略

(b) Prophet路由協(xié)議與不同懲罰策略圖6 傳輸成功率對比

Epidemic路由算法是將消息傳遞給與其相遇的所有節(jié)點，故該算法的成功傳輸率較高。但隨著自私節(jié)點比例的增多，節(jié)點中“不轉(zhuǎn)發(fā)”行為增加，所以其成功傳輸率也減少。Prophet算法是基于概率的轉(zhuǎn)發(fā)，由于自私節(jié)點的不合作行為，致其傳輸概率較低，因此隨著自私節(jié)點的增多，其傳輸成功率將減少。

當自私節(jié)點所占比例增大時，節(jié)點間的協(xié)作次數(shù)越來越少，表現(xiàn)為傳輸成功率在下降，但是不使用任何懲罰策略情況下，成功率最低。在網(wǎng)絡中使用GS策略后，節(jié)點首次選擇是合作的，故當自私節(jié)點數(shù)量較少時，傳輸成功率較高。但當網(wǎng)絡中的節(jié)點選擇不轉(zhuǎn)發(fā)策略時，則會導致以后永不轉(zhuǎn)發(fā)節(jié)點。故在自私節(jié)點比例增多時，傳輸成功率明顯下降。在使用TFT后由于該機制中引入懲罰機制，理性節(jié)點為增多節(jié)點未來的收益，會考慮其自私行為帶來的不利影響，故其傳輸成功率相較前者有所提高。在使用本文提出的TTFT懲罰機制后，隨著自私節(jié)點所占比例的增加，相對GS、TFI策略，TTFT提高傳輸成功率的效果更好。這是由于TTFT模型的懲罰周期是根據(jù)影響節(jié)點收益多少的信譽度來設置，具有區(qū)分性和動態(tài)性，所以其呈現(xiàn)的協(xié)作效果更好。

5 結(jié) 語

機會網(wǎng)絡中的節(jié)點因自身的處理能力低、存儲空間有限和電池容量小等原因，節(jié)點表現(xiàn)出自私性。因此，激勵自私節(jié)點轉(zhuǎn)發(fā)消息成為提高節(jié)點傳輸成功率和降低網(wǎng)絡延遲的關(guān)鍵問題。本文定義了信譽度對節(jié)點歷史行為進行度量，并提出基于信譽度的懲罰策略的重復博弈模型。一方面利用不同信譽度實施不同程度的懲罰，另一方面，利用節(jié)點對未來收益的期望，而激勵了節(jié)點積極參與協(xié)作轉(zhuǎn)發(fā)。通過演化博弈分析證明了基于信譽度懲罰策略TTFT的演化穩(wěn)定性，仿真表明，該模型可以激勵節(jié)點協(xié)作，提高網(wǎng)絡傳輸性能。