基于博弈論的無線Mesh網(wǎng)絡信任評估模型

宋佳佳,孫彥武

(嘉興學院,a.數(shù)理與信息工程學院;b.外國語學院,浙江嘉興314000)

基于博弈論的無線Mesh網(wǎng)絡信任評估模型

宋佳佳a,孫彥武b

(嘉興學院,a.數(shù)理與信息工程學院;b.外國語學院,浙江嘉興314000)

無線Mesh網(wǎng)絡中的節(jié)點具有動態(tài)性和異構性,為解決節(jié)點的自私性問題,引入了節(jié)點的能量屬性,提出了基于博弈論的無線Mesh網(wǎng)絡信任評估模型,節(jié)點的信任評估值由信任博弈分量與節(jié)點信任直接觀察分量結合的方式,使節(jié)點選擇理性策略以獲取最優(yōu)行為結果,達到網(wǎng)絡數(shù)據(jù)包轉發(fā)負載均衡,有效評價了節(jié)點的交互行為并抑制了自私節(jié)點.

無線Mesh;博弈論;節(jié)點能量;信任評價;激勵

隨著多網(wǎng)融合技術的不斷發(fā)展,無線Mesh網(wǎng)絡作為一種基于多跳路由(multi-hop)、對等網(wǎng)絡技術的新型網(wǎng)絡結構,即在有限的發(fā)射功率下,采用多跳技術實現(xiàn)流量融合,解決了無線接入“最后一公里”的瓶頸問題.[1]無線Mesh網(wǎng)絡結合了Ad Hoc網(wǎng)和傳統(tǒng)無線網(wǎng)絡的優(yōu)勢,有部署快速、組網(wǎng)靈活、網(wǎng)絡覆蓋率高、非視距傳輸(NLOS)強的優(yōu)點,尤其是在移動性、可靠性和自組織性等方面更靈活便捷,并可以用來提高無線網(wǎng)狀網(wǎng)的容量和信道的利用率.因此,無線Mesh網(wǎng)絡廣泛運用于政府、企業(yè)、社區(qū)、校園網(wǎng)建設和臨時應急指揮網(wǎng)絡等場所.如圖1所示,無線Mesh網(wǎng)絡提供了一種層次結構,其中網(wǎng)狀路由器節(jié)點組成了無線Mesh的骨干網(wǎng),它們一起為無線Mesh網(wǎng)和其他接入節(jié)點提供網(wǎng)絡的無線接入.

隨著手機等各類智能終端用戶的快速增加和無線Mesh網(wǎng)絡運用范圍的不斷擴大,[2]對無線Mesh網(wǎng)絡的穩(wěn)定性、適用性和安全性提出了更高的要求.但由于泛在結構和無線傳輸信道的開放性,無線Mesh網(wǎng)絡也面臨多種安全威脅,包括竊聽、截獲、偽裝及拒絕服務等.[3]網(wǎng)絡中許多服務和功能都必須依靠節(jié)點之間的相互協(xié)作來完成.但當實際的網(wǎng)絡節(jié)點分別屬于不同組織時,網(wǎng)絡節(jié)點會出于自身處理能力、帶寬資源、存儲空間等方面的考慮,有一定的自私性,即不愿意消耗自身的能量和計算資源去協(xié)助其他節(jié)點轉發(fā)數(shù)據(jù),這樣會影響無線網(wǎng)絡正常的路由和數(shù)據(jù)轉發(fā)功能.

圖1 無線Mesh網(wǎng)絡拓撲結構

如何激勵網(wǎng)絡中的自私節(jié)點進行合作以提高網(wǎng)絡整體性能是無線網(wǎng)絡研究領域面臨的重要挑戰(zhàn)之一.針對節(jié)點自私問題,目前主要采用兩類機制來處理:基于信任度的信任機制和基于非合作博弈的激勵機制.[4]前者通過對網(wǎng)絡節(jié)點交互行為的記錄和審計來綜合評定節(jié)點的合作行為,對不合作的節(jié)點進行懲罰.而后者是借鑒了經(jīng)濟學和博弈論的相關理論,對提供服務的合作節(jié)點進行相應的有償激勵.

文獻[5]提出了基于歷史效應和未來效應的信譽系統(tǒng),歷史行為會對節(jié)點當前交互行為產(chǎn)生影響,但信譽值的更新速度比較滯后.看門狗和選路人算法用來監(jiān)控和防止節(jié)點的異常行為,但這種算法的問題是沒有區(qū)分節(jié)點拒絕轉發(fā)數(shù)據(jù)是惡意還是物理原因,并對惡意節(jié)點沒有懲罰措施.[6]為了激勵節(jié)點轉發(fā)數(shù)據(jù)而增設的計數(shù)器機制,在一定程度上激勵了自私節(jié)點的轉發(fā)數(shù)據(jù)包,但增加了網(wǎng)絡開銷.[7]解決中間節(jié)點是否轉發(fā)數(shù)據(jù)包的Spirte機制,是通過對節(jié)點支付轉發(fā)開銷而使節(jié)點收益,雖然有效激勵了鏈路上的各節(jié)點轉發(fā)數(shù)據(jù)包,但沒有實現(xiàn)預算平衡.[8]

在通信節(jié)點信任評價的基礎上,利用博弈論對高信譽度節(jié)點即信任節(jié)點動態(tài)博弈,產(chǎn)生優(yōu)良節(jié)點的策略結合,達到節(jié)點間信道分配算法最優(yōu)和網(wǎng)絡資源的協(xié)同管理.而面對競爭環(huán)境中資源共享和分配問題,博弈論作為一種理想的基礎工具成為研究和分析動態(tài)頻譜共享技術的重要方法.還有人提出了基于議價(pricing)或仲裁(referee)博弈方法的信道資源分配方法,或使用了不完全信息貝葉斯博弈解決了無線網(wǎng)絡中普通節(jié)點和惡意節(jié)點的識別和共存問題.[9-10]而將博弈論運用到云終端客戶的行為中,用不完全信息動態(tài)博弈對云端客戶的類型、可信等級進行不同的訪問控制,根據(jù)博弈結果動態(tài)地調整用戶的信任等級,從而有效降低了惡意云端客戶的訪問請求,提高了云服務端的服務質量.[11]

在上述基礎上,可建立基于博弈論的無線Mesh網(wǎng)絡信任管理機制,如圖2所示,通過對節(jié)點不同行為策略的分析以獲取節(jié)點的最好行為結果,而節(jié)點的信任博弈分量和直接觀察分量直接決定了節(jié)點的信任評估值,信任度的高低與節(jié)點是否可以為鄰居轉發(fā)數(shù)據(jù)包相關聯(lián),無線Mesh網(wǎng)絡中節(jié)點的交易風險會有所控制并達到網(wǎng)絡的最佳效用.

圖2 基于博弈論的信任機制

1 信任管理機制模型

在基于博弈論的信任模型中,對參與網(wǎng)絡交互節(jié)點的屬性進行如下定義:

參與者:無線Mesh網(wǎng)絡中的節(jié)點類型θ,包括普通節(jié)點和自私節(jié)點;

行動集:參與者的行動依賴于它的類型,普通節(jié)點的行動集Ai＝{a1,a2}＝{提供服務,轉發(fā)數(shù)據(jù)包},自私節(jié)點的行動集合Ai＝{a3,a4}＝{享受服務,不轉發(fā)數(shù)據(jù)包};

支付:節(jié)點因可信提供服務轉發(fā)數(shù)據(jù)包的開銷,即能量消耗為Ei;節(jié)點因可信成功轉發(fā)數(shù)據(jù)包的收益為Ui;節(jié)點發(fā)出請求服務的開銷為Ci;節(jié)點拒絕服務不轉發(fā)數(shù)據(jù)包時所獲得的懲罰為Pi;

效用函數(shù):節(jié)點提供服務所獲取的收益λi(a,θ);節(jié)點在該策略下所需付出的成本為μi(a,θ);節(jié)點類型為θ的節(jié)點vi的效用函數(shù)為:

只有當a≠0,且μi(a,θ)≥0時,節(jié)點vi才有動機參與博弈.

在網(wǎng)絡中的每個節(jié)點在某t時刻的屬性集為Θ＝{θi(t),Ri(t),Hi(t),|Ni|(t)},其中θi(t)為節(jié)點能量利用率,Ri(t)為節(jié)點信譽度,Hi(t)為節(jié)點交互歷史記錄,|Ni|(t)為當前節(jié)點的鄰居節(jié)點數(shù).暫時不考慮時間因素的影響,節(jié)點vi的的屬性集合為ΘI＝{θi,Ri,Hi,|Ni|},即為節(jié)點vi的私人信息.Hij(t)＝{fji,Dij}為t時刻vi和vj的數(shù)據(jù)轉發(fā)記錄,其中fji為t時刻vj為vi轉發(fā)的數(shù)據(jù)包數(shù)量,Dij為vi要求vj轉發(fā)的數(shù)據(jù)包總數(shù).

2 基于博弈論的信任關系的建立

由于沒有歷史交易記錄,當有新節(jié)點加入無線Mesh網(wǎng)絡時,需要在網(wǎng)的節(jié)點對新加入節(jié)點進行信任評估.本模型利用新加入節(jié)點在一跳范圍內廣播發(fā)送Hello包來發(fā)現(xiàn)鄰居節(jié)點,再加入鄰居節(jié)點的鄰居表,通過節(jié)點之間的博弈形成對新節(jié)點的可信度評估,從而形成對新鄰居節(jié)點的初始信任值.

2.1 無線Mesh網(wǎng)絡節(jié)點間的相互交互產(chǎn)生信任度

定義無線Mesh網(wǎng)絡節(jié)點間的相互交互產(chǎn)生信任度如下:

其中α為權重因子,表示對節(jié)點的博弈分量和直接信任分量的偏好程度,若對新節(jié)點沒有歷史記錄,則α＝0;隨著節(jié)點交互行為次數(shù)的增多,α會逐漸增大.Tgij為節(jié)點交互的博弈分量,即節(jié)點vi根據(jù)當前網(wǎng)絡環(huán)境和節(jié)點屬性集對節(jié)點vj的信任評估值.Twij為節(jié)點的直接信任分量,即通過節(jié)點直接觀察得出的信任評估值.

2.2 節(jié)點的博弈分量

定義節(jié)點的博弈分量為:

對無線網(wǎng)絡中的所有節(jié)點來說,每個節(jié)點都有機會與其鄰居節(jié)點合作產(chǎn)生交互,節(jié)點之間相互策略的選擇產(chǎn)生交互信任收益,設節(jié)點vi在某一時刻與其鄰居節(jié)點進行的博弈收益為ui(Ni),μi(Ni| {vj}為節(jié)點vi和除去節(jié)點vj后的其他鄰居節(jié)點進行博弈產(chǎn)生的收益,故Δμij＝μi(Ni)-μi(Ni| {vj})表示節(jié)點vj對節(jié)點vi收益所起的作用,若Δμij}0,則表示節(jié)點vj的加入使得節(jié)點vi增加了收益,反之則表示收益降低,由此可視節(jié)點vj不可信任或信任度較低.

2.3 直接信任分量

定義直接信任分量為:節(jié)點的直接信任分量是節(jié)點直接交互而獲得的觀察值,第t次的信任評估值使用第t-1次節(jié)點交互行為的記錄值來計算.

其中,fji(t)和Dij(t)是第t-1次信任評估后節(jié)點vi和vj相互交易的累積記錄信息.η為懲罰因子,表示對節(jié)點自私行為的懲罰力度.

將節(jié)點vi和vj歷史上多次的交互結果的總數(shù)聚合為當前節(jié)點的最新信任評估值,假設觀察時間窗口值為κτ,其中κ≥1是觀察周期,則第m次的直接信任分量為:

式中κ作為信任評估的兩個節(jié)點的歷史交互次數(shù),當m＝κ時,可以把歷史上兩個節(jié)點的所有交互結果的聚合作為最終的信任評價.

2.4 新加入節(jié)點信任關系初始化步驟

Step1:加入新節(jié)點,更新鄰居集Ni

a)節(jié)點vi在當前網(wǎng)絡一跳范圍內廣播發(fā)送請求hello包,令TTL＝1;

b)收到hello包的節(jié)點vj發(fā)送回執(zhí)reply(j)給節(jié)點vi,并將vi加入自己的鄰居表里;

c)在一個生存周期內,節(jié)點vi根據(jù)收到的reply(j)構建自己的鄰居集;

Step2:更新信任值Tji

a)節(jié)點vi與節(jié)點vj進行博弈并計算和;

b)從鄰居表讀取節(jié)點vi的歷史記錄,并統(tǒng)計節(jié)點vi為vj實際轉發(fā)的分組數(shù)量fij和Dji;

c)根據(jù)公式計算Tji.

Step3:更新各節(jié)點的信息表和屬性表.

上述步驟能夠實時更新節(jié)點的信任評估并更新節(jié)點屬性表,根據(jù)節(jié)點對鄰居節(jié)點的信任度變化情況,反映出當前網(wǎng)絡拓撲變化及用戶行為的變化情況,使得網(wǎng)絡中個點之間保持最新的信任關系,在節(jié)點vi的鄰居范圍內,信任關系收斂的速度比較快.

3 實驗效果分析

具體的實驗環(huán)境如下:2.00 GHz Intel Pentium雙核處理器,2GB內存,320G硬盤,Windows 7操作系統(tǒng),實驗軟件為Matlab R2009a搭建的仿真平臺.Matlab是用于算法開發(fā)、數(shù)據(jù)可視化及數(shù)據(jù)分析、計算的功能強大的交互式程序設計及建模環(huán)境,在本實驗中,主要用于模擬環(huán)境中節(jié)點的仿真以及節(jié)點之間信任信息的計算分析.

通過設置不同的值來驗證博弈過程中的信任管理機制,假設規(guī)定每個節(jié)點轉發(fā)數(shù)據(jù)包所消耗的能量資源為0.005單位,在每一個評價周期τ內,節(jié)點vi向所有的鄰居節(jié)點總共發(fā)送50個數(shù)據(jù)包,每個鄰居節(jié)點獲得的分組數(shù)與其當前的信任評估值有關,信任評估值高的節(jié)點可以獲得更多轉發(fā)數(shù)據(jù)包的機會.當節(jié)點vi加入網(wǎng)絡先進入就近節(jié)點vj,vk的鄰居表進行信任評估,設定觀察時間窗口值為0,1τ,2τ,3τ,…,20τ,即m＝0,1,2,3,…20時的信任值Tij、Tik的變化情況.節(jié)點vi的屬性為Θ＝{0.8,0.5,0,|50|(t)},表示節(jié)點vi的能量利用率為0.8,初始信譽值為0.5,新進節(jié)點的交易歷史為0.

權重因子α反映了節(jié)點對信任分量的偏好程度,若沒有直接觀察分量,α＝0,節(jié)點的信任評估值由節(jié)點博弈分量決定;若節(jié)點只有一個鄰居,則α＝1,即完全依賴鄰居節(jié)點;隨著節(jié)點直接觀察分量的不斷獲取,信任評估值會由節(jié)點博弈分量和直接觀察分量共同決定,α不斷增大.η為懲罰因子反應對消極節(jié)點的懲罰情況,取值為1.

圖3反映了節(jié)點vi隨著時間窗口信任度的變化情況,在初始時由于vi是新加入節(jié)點沒有歷史交互記錄所以信任度比較低,隨著時間窗口的增加,節(jié)點vi的信任度呈現(xiàn)逐步增加的態(tài)勢,節(jié)點對鄰居節(jié)點的選擇偏向于丟包率小的節(jié)點,而直接交互記錄是節(jié)點信任評估最重要的依據(jù).

圖3 節(jié)點i的信任度變化

但隨著交互次數(shù)的不斷增多,Tij有所減小,而Tik有所增加,這是因為轉發(fā)數(shù)據(jù)包量的增加過多了消耗了節(jié)點vj的能量,而節(jié)點vk的能量優(yōu)勢在博弈分量中得以加強,如圖4所示.結果證明,過多的轉發(fā)數(shù)據(jù)包會消耗節(jié)點自身能量.

圖4 新加入節(jié)點博弈分量的變化

在實驗中,如圖5所示,假設節(jié)點vk在時間窗口m＝15時降低了自己的丟包率,可以看出Tik的值逐漸增大,同時Tij的值逐漸減小,這是由于節(jié)點vk分擔了節(jié)點vj的轉發(fā)數(shù)據(jù)包,減輕了vj的轉發(fā)負載,vk幫助vj轉發(fā)了更多的數(shù)據(jù)包,獲得了更多的信任,那么相應的博弈分量隨著vk轉發(fā)數(shù)據(jù)的增多而相應減少.

圖5 丟包率減少后節(jié)點信任度變化

4 結論

實驗結果表明,當有新節(jié)點加入網(wǎng)絡時,在線節(jié)點需要更新自己的鄰居并重新評估其鄰居的信任度.當鄰居節(jié)點的數(shù)量增加時,意味著對一個節(jié)點會有更多的鄰居節(jié)點為其轉發(fā)數(shù)據(jù)包,自私節(jié)點會更少的為節(jié)點服務,當鄰居數(shù)量減少時,節(jié)點對剩下鄰居的轉發(fā)依賴也會有所增加.節(jié)點的能量屬性會隨著時間窗口值的增大和節(jié)點與鄰居節(jié)點交互行為的變化而不斷發(fā)生變化,節(jié)點在選擇交互對象的時候會依據(jù)能量屬性和信任度來進行選擇,自私節(jié)點不能因為自身能量消耗少來獲得數(shù)據(jù)轉發(fā)權利,自身的信任度也不隨之增強.

基于博弈論的無線Mesh網(wǎng)絡信任管理機制利用節(jié)點的能量屬性進行博弈,在節(jié)點信任關系建立之后,就可以根據(jù)節(jié)點鄰居表中信譽評估值即信任的博弈分量和節(jié)點的直接觀察分量進行節(jié)點信任度的比較,從而獲得良好的策略結合以產(chǎn)生最優(yōu)的行為結果,使得網(wǎng)絡可以獲得最大的效用并降低節(jié)點間的交易風險.

[1]SGORA A,VERGADOS D,CHATZIMISIOS P.IEEE 802.11s Wireless Mesh Networks:Challenges and Perspectives[J]. MOBILIGHT,LNICST,2009,13(1):263-271.

[2]中國互聯(lián)網(wǎng)絡信息中心.第33次中國互聯(lián)網(wǎng)絡發(fā)展狀況統(tǒng)計報告[R].北京:中國互聯(lián)網(wǎng)絡信息中心,2014:5-80.

[3]仵國鋒.認知無線Mesh網(wǎng)絡若干關鍵技術研究[D].鄭州:解放軍信息工程大學,2011.12:20-75.

[4]JOSANG A,ISMAIL R,BOYD C.A survey of trust and reputation systems for online service provision[J].Decision Support Systems,2007,43(2):618-644

[5]郭彩麗,馮春燕,曾志民.認知無線電網(wǎng)絡技術及應用[M].北京:電子工業(yè)出版社,2010:12-91.

[6]MARTI S,GIULI T J,LAI K,et al.Mitigating routing misbehavior in mobile ad hoc networks[M]//Proc.of the ACM MobiCom 2000.New York:ACM Press,2000:255-265.

[7]BUTTYAN L,HUBAUX J.Stimulating cooperation in self-organizing mobile ad hoc networks[J].ACM/Kluwer Mobile Networks and Applications,2003,8(5):579-582.

[8]Zhong S,Chen J,Yang YR.Sprite:A simple cheat-proof credit-based system for mobile ad hoc network[M]//Proc.of the IEEE INFOCOM 2003,Vol3.Washington:IEEE Computer Society,2003,1987-1997.

[9]姬文江,馬建鋒,田有亮.無線Mesh網(wǎng)中一種基于博弈論的公平性路由協(xié)議[J].通訊學報,2012,33(11):17-23.

[10]Wenjing Wang,M.Chatterjee,K.Kwiat.Coexistence with malicious nodes:A game theoretic approach[M]//Proc.International Conference on Game Theory for Networks(GameNets’09).Istanbul:IEEE Press,2009:277-286.

[11]陳亞睿,田立勤,楊揚.云計算環(huán)境下基于動態(tài)博弈論的用戶行為模型與分析[J].電子學報,2011,39(8):1818 -1823.

(責任編輯 劉偉俠)

Trust Evaluation Model Based on Game Theory in Wireless Mesh Networks

Song Jiajia,Sun Yanwu
(a.College of Mathematics Physics and Information Engineering; b.College of Foreign Studies,Jiaxing University,Jiaxing,Zhejiang 314000)

Nodes in wireless Mesh network has dynamic and heterogeneous attributes,in order to solve the problem of selfishness,energy attribute of nodes and the game theory are introduced into the paper,it proposed the trust evaluation model based on game theory wireless Mesh network.The value of the node’s trust evaluation is divided into two parts,trust game component and direct observation component,so the nodes can choose the rational strategy to obtain the optimal behavior results,then achieve load balancing of the network in data packet forwarding.Finally,the model evaluated the convergence behavior of node and inhibited the selfish nodes effectively.

wireless Mesh;game theory;node energy;trust evaluation;incentive

TP393.08

A.

1671-3079(2014)03-0082-06

10.3969 /i.issn.1671-3079.2014.03.015

2014-03-12

宋佳佳(1986- ),女,嘉興學院數(shù)理與信息工程學院教師,碩士,主要研究方向為計算機網(wǎng)絡技術與網(wǎng)絡安全.

時間:2014-04-10 14:06 網(wǎng)絡出版地址:http://www.cnki.net/kcms/detail/33.1273.Z.20140519.1650.008.html