傳感網(wǎng)中對抗惡意節(jié)點的博弈論分析

袁智榮， 吳一坤， 王軍強， 蔣衛(wèi)東

(1.西北工業(yè)大學 無人機研究所，陜西 西安 710065；2.西北工業(yè)大學 電子信息學院，陜西 西安 710072)

研究與探討

傳感網(wǎng)中對抗惡意節(jié)點的博弈論分析

袁智榮1， 吳一坤2， 王軍強1， 蔣衛(wèi)東2

(1.西北工業(yè)大學 無人機研究所，陜西 西安 710065；2.西北工業(yè)大學 電子信息學院，陜西 西安 710072)

無線傳感網(wǎng)作為應用廣泛的多跳自組織網(wǎng)絡，由成百上千資源有限的傳感器節(jié)點組成。當網(wǎng)絡數(shù)據(jù)傳輸時，若節(jié)點的通信負載超過其可用帶寬，則會發(fā)生擁塞，使得傳輸不可靠，尤其在無線傳感網(wǎng)特殊的工作環(huán)境中，當有惡意節(jié)點存在時會更嚴重。為此，引入博弈論，對有惡意節(jié)點存在的傳感網(wǎng)進行研究，分析節(jié)點行為，建立博弈模型，給出實現(xiàn)步驟和驗證方案，綜合理論分析和仿真結(jié)果，獲得節(jié)點最佳策略，達到網(wǎng)絡擁塞避免的既定目標。

無線傳感網(wǎng)； 博弈論； 惡意節(jié)點； 擁塞避免

0 引 言

無線傳感網(wǎng)(WSNs)集合了傳感器技術、分布式信息處理、無線通信等方面研究的最新成果,成為目前國內(nèi)外學術領域中的熱點研究對象。為了增強人們對客觀世界的測控能力，它的功能被不斷加強，使之在空間探索、環(huán)境監(jiān)測、軍事偵察、遠程控制等領域都具有巨大實用價值和廣闊應用前景[1,2]。如何有效管理這些應用所帶來的數(shù)據(jù)傳輸問題，以保證網(wǎng)絡服務質(zhì)量優(yōu)良,成為當前需要面對的重要問題。

目前,針對無線傳感網(wǎng)擁塞避免的研究工作已經(jīng)取得了一定成果[3]。其中，博弈論作為一種理論工具，顯示了其獨特的優(yōu)勢和作用。從博弈角度考慮，認為參與者通常情況下是理性的，它們的策略都試圖將自身收益最大化，然而，這種理性并非絕對，自然環(huán)境的干擾會使參與者變成非正常狀態(tài)，嚴重影響網(wǎng)絡性能。本文以擁塞避免為目的，以對抗惡意節(jié)點為側(cè)重，推導出參與博弈的傳感網(wǎng)節(jié)點應該采取的最佳決策。

1 無線傳感網(wǎng)節(jié)點行為

1.1 節(jié)點自私行為

無線傳感網(wǎng)節(jié)點間通過互相協(xié)作來提供正常的網(wǎng)絡服務，但部分節(jié)點會優(yōu)先考慮自身有限資源而自私地選擇不合作行為，這樣必定會嚴重影響網(wǎng)絡性能。為了促進網(wǎng)絡自私節(jié)點進行協(xié)作，已提出基于信譽以及博弈論等方法的激勵機制，前者通過引入信譽值來迫使節(jié)點協(xié)作，后者則是通過分析節(jié)點收益來驅(qū)動合作[4]。

1.2 節(jié)點惡意行為

無線傳感網(wǎng)通常是被部署在一個相對開放的環(huán)境中，節(jié)點容易被外界攻擊者俘獲而成為惡意節(jié)點，進而對網(wǎng)絡發(fā)動攻擊。這些惡意攻擊不僅會造成網(wǎng)絡擁塞甚至癱瘓，而且具有很強的隨機性，難以防范，傳統(tǒng)的密鑰機制也會失效[5,6]。如何有效防范惡意節(jié)點的行為，對于保證傳感網(wǎng)正常數(shù)據(jù)傳輸具有十分重要的意義。

2 博弈論

2.1 構(gòu)成要素

博弈論主要研究了博弈參與者間的相互作用，是運用在競爭現(xiàn)象的數(shù)學理論和方法，其基本構(gòu)成要素如下：

1)參與者：博弈的決策主體，可以是人，也可以是參與競爭的其他主體。

2)策略：博弈中所有參與者采取行動時的組合，不止一組。

3)收益：參與者通過執(zhí)行策略所得的利潤。

4)均衡：所有參與者選擇的最優(yōu)策略集合。

2.2 納什均衡

博弈過程中，存在一策略組合，所有參與者都穩(wěn)定在該組合上采取行動，且沒有任何一個參與者愿意打破這種穩(wěn)定，而去采取其他行動。因為一旦穩(wěn)定被打破，參與者自身的收益將會降低。此策略組合被稱為納什均衡點。它的意義在于：為博弈提供了一種重要的分析手段，使研究可以在通俗的博弈結(jié)構(gòu)中尋找想要的結(jié)果。

3 模型設計

3.1 建模構(gòu)想

相對于以往將博弈論應用在無線傳感網(wǎng)中的研究，本文建立的博弈模型改進并突出了以下三點：

1)以往采取鏈路層定價帶寬，單個節(jié)點進行博弈。本文著眼網(wǎng)絡整體，將節(jié)點分類博弈，突出惡意節(jié)點行為，制定分類節(jié)點的相應策略。

2)以往忽略網(wǎng)絡外部干擾，將所有節(jié)點默認為理性狀態(tài)。本文考慮傳感網(wǎng)節(jié)點易受攻擊，將在傳統(tǒng)轉(zhuǎn)發(fā)或不轉(zhuǎn)發(fā)的策略范疇上加入攻擊行為，將它對網(wǎng)絡性能的影響考慮在內(nèi)。

3)以往采取靜態(tài)博弈類型。本文將利用動態(tài)演化博弈理論，根據(jù)收益矩陣，列出演化方程，仿真節(jié)點實時狀態(tài)，快速確定博弈策略優(yōu)劣。

3.2 模型建立

1)參與者:傳感網(wǎng)正常節(jié)點，傳感網(wǎng)惡意節(jié)點。

2) 策略:對于正常節(jié)點，具有轉(zhuǎn)發(fā)和不轉(zhuǎn)發(fā)兩種策略，記為S1=(T，NT)；對于惡意節(jié)點，具有轉(zhuǎn)發(fā)、攻擊和不轉(zhuǎn)發(fā)三種策略，記為S2=(T，A，NT)。其中，惡意節(jié)點的攻擊策略定義為：蟲洞攻擊、Sybil攻擊和刪除攻擊[7,8]相結(jié)合的行為，其目的是為了占用更多鏈路帶寬，使正常節(jié)點的數(shù)據(jù)無法有效傳輸，造成網(wǎng)絡擁塞。當采取攻擊策略時，惡意節(jié)點發(fā)送“偽數(shù)據(jù)包”，此包的真假用戶無法辨認。

3)收益：設定CR為節(jié)點轉(zhuǎn)發(fā)一個數(shù)據(jù)包消耗的資源，R為節(jié)點成功轉(zhuǎn)發(fā)一個數(shù)據(jù)包獲得的收益，CA為惡意節(jié)點發(fā)動攻擊消耗的資源，M為惡意節(jié)點發(fā)動攻擊獲得的收益，C為無線通信鏈路初始帶寬，C>R>M>CA>CR。當正常節(jié)點轉(zhuǎn)發(fā)時，惡意節(jié)點發(fā)動攻擊，它不僅獲得攻擊收益帶寬M，還會竊取正常節(jié)點應得轉(zhuǎn)發(fā)收益帶寬R；當正常節(jié)點不轉(zhuǎn)發(fā)時，惡意節(jié)點發(fā)動攻擊，只獲得攻擊收益帶寬M。

3.3 模型分析

1)收益矩陣分析

收益矩陣如表1所示，存在唯一的納什均衡，即(不轉(zhuǎn)發(fā)，攻擊)策略組合。意味著經(jīng)有限次博弈，正常節(jié)點會選擇不轉(zhuǎn)發(fā)行為，而惡意節(jié)點則不斷對網(wǎng)絡進行攻擊。

表1 節(jié)點博弈收益矩陣Tab 1 Node game profit matrix

隨著攻擊次數(shù)不斷增加，鏈路剩余可用帶寬單調(diào)遞減。存在時刻T，T時刻后惡意節(jié)點發(fā)送的“偽包”也不斷被丟棄。用戶看來，網(wǎng)絡發(fā)生了擁塞，無法正確傳輸數(shù)據(jù)。

2)行為策略改進

由于惡意節(jié)點的攻擊導致了網(wǎng)絡擁塞的發(fā)生。為了解決問題，受攻擊策略的啟發(fā)，給正常節(jié)點加入防御策略，正常節(jié)點的策略空間將變化為S1=(T，NT,D)。設定正常節(jié)點防御性轉(zhuǎn)發(fā)一個數(shù)據(jù)包消耗資源CD。其中，M>CD>CA。改進策略后的收益矩陣如表2所示。

表2 節(jié)點博弈收益矩陣Tab 2 Node game profit matrix

此矩陣不存在明顯的納什均衡。為了找到保證網(wǎng)絡性能的最優(yōu)策略，利用軟件工具進行更精確的仿真分析。

4 模型仿真

4.1 仿真對象

設定無線傳感網(wǎng)正常節(jié)點分別采取轉(zhuǎn)發(fā)、不轉(zhuǎn)發(fā)和防御策略的比例為X1,X2,X3；惡意節(jié)點分別采取轉(zhuǎn)發(fā)、攻擊和不轉(zhuǎn)發(fā)策略的比例為Y1,Y2,Y3，則有X1+X2+X3=1,Y1+Y2+Y3=1。

根據(jù)動態(tài)博弈中的演化博弈理論，可以得到不同類型節(jié)點采取不同策略時的復制動態(tài)方程。此方程的意義為：利用具體某類型節(jié)點全部采取某一具體策略時的均收益與具體某類型節(jié)點按比例采取具體策略時的均收益作比較，再結(jié)合微分方程的函數(shù)變化率，便可判斷出下一時刻節(jié)點的走勢取向?？偣擦N策略，所對應的六個復制動態(tài)方程如下：

(1)

d(X2)/dt=-[X1·Y1·X2+X2·X3·(Y1+Y2)]·R+X1·X2·CR-X2·X3·CD

(2)

(3)

(4)

(5)

d(Y3)/dt=-[(X1+X3)·Y1·Y3+Y2·X1·Y3]·R+Y1·Y3·CR+Y3·Y2·CA-Y2·Y3·M

(6)

式中 資源的消耗和收益是常量，在滿足基本條件C>R>M>CD>CA>CR的情況下，給出固定仿真值帶入：R=1，M=0.7，CD=0.5，CA=0.4，CR=0.2。

4.2 仿真工具與代碼

利用MATLAB對上述六個常微分方程進行仿真，核心代碼如下：

%%

t_span=[0:0.5:50];%自變量t

y=[0.5,0.5,0,1/3,1/3,1/3];%×1

到y(tǒng)3在t等于0時候的初始值，可變

[t,Y]=ode15s(@dif_Eq,t_span,y);

%調(diào)用龍格—庫塔函數(shù)求解微分方程，dif_Eq函數(shù)在另一個M文件中以子函數(shù)形式存在

figure1=figure(1); %創(chuàng)建圖

dif_Eq子函數(shù)代碼：

function dydt = dif_Eq(t,y)

%%

4.3 仿真數(shù)據(jù)分析

現(xiàn)對X1,X2,X3,Y1,Y2,Y3賦予多組初值，進行仿真分析。

1)令(X,Y)=(0.5，0.5，0，1/3，1/3，1/3),正常節(jié)點均分兩類，采取轉(zhuǎn)發(fā)或不轉(zhuǎn)發(fā)策略，無防御性策略節(jié)點；惡意節(jié)點隨機均分為三類，分別采取轉(zhuǎn)發(fā)、攻擊和不轉(zhuǎn)發(fā)策略。仿真結(jié)果如圖1所示。

分析：經(jīng)過博弈，正常節(jié)點全部采取不轉(zhuǎn)發(fā)策略，惡意節(jié)點全部采取攻擊策略，這和最初分析的未加入防御性策略時的節(jié)點收益矩陣結(jié)果吻合，網(wǎng)絡會走向擁塞甚至癱瘓的糟糕狀況。

2)令(X,Y)=(1/3，1/3，1/3，1/3，1/3，1/3),正常節(jié)點加入防御性策略，隨機均分為三類，分別采取轉(zhuǎn)發(fā)、不轉(zhuǎn)發(fā)和防御策略；惡意節(jié)點隨機均分為三類，分別采取轉(zhuǎn)發(fā)、攻擊和不轉(zhuǎn)發(fā)策略。仿真結(jié)果如圖2所示。

圖1 節(jié)點走勢圖Fig 1 Node trend image

圖2 節(jié)點走勢圖Fig 2 Node trend image

分析：經(jīng)過博弈，網(wǎng)絡節(jié)點無法達到穩(wěn)定狀態(tài)。當有部分正常節(jié)點采取防御性策略時，惡意節(jié)點將放棄攻擊策略變?yōu)檗D(zhuǎn)發(fā)策略(R-CR>M-CA)；當惡意節(jié)點變?yōu)檗D(zhuǎn)發(fā)策略后，正常節(jié)點將放棄防御策略變?yōu)檗D(zhuǎn)發(fā)策(R-CR>R-CD)；當正常節(jié)點變?yōu)檗D(zhuǎn)發(fā)策略后，惡意節(jié)點將放棄轉(zhuǎn)發(fā)策略變?yōu)楣舨呗?M+R-CA>R-CR)；當惡意節(jié)點變?yōu)楣舨呗院?，正常?jié)點將放棄轉(zhuǎn)發(fā)策略變?yōu)榉烙呗?R-CD>-CR)。因此，節(jié)點將陷入反復循環(huán)博弈的過程，網(wǎng)絡無法穩(wěn)定，該策略也不是能夠避免擁塞的選擇。

3)令(X,Y)=(0.2，0.1，0.7，0.4，0.2，0.4),更隨機地對節(jié)點比例變量賦予初值，驗證前兩組結(jié)論分析的可靠性。仿真結(jié)果如圖3所示。

圖3 節(jié)點走勢圖Fig 3 Node trend image

分析：經(jīng)過博弈，兩類節(jié)點依舊無法達到穩(wěn)定狀態(tài)。節(jié)點走勢與圖2類似，其原因與上組數(shù)據(jù)結(jié)論一致，說明只要加入防御策略后，仍有部分正常節(jié)點初始處于轉(zhuǎn)發(fā)及不轉(zhuǎn)發(fā)策略，網(wǎng)絡最終都會達到不穩(wěn)定的狀態(tài)，此結(jié)果與初始賦值的大小無關。

4)令(X,Y)=(0，0，1，1/3，1/3，1/3)，正常節(jié)點全部采取防御性策略轉(zhuǎn)發(fā)數(shù)據(jù)；惡意節(jié)點隨機均分三類，分別采取轉(zhuǎn)發(fā)、攻擊和不轉(zhuǎn)發(fā)的策略。仿真結(jié)果如圖4所示。

圖4 節(jié)點走勢圖Fig 4 Node trend image

圖4分析：經(jīng)過博弈，正常節(jié)點全部采取防御性策略；惡意節(jié)點為了最大化自身收益而全部采取轉(zhuǎn)發(fā)策略(R-CR>M-CA>0)。網(wǎng)絡會進入良好的協(xié)作狀態(tài)，避免擁塞發(fā)生，并一直穩(wěn)定地持續(xù)下去。但這樣的策略組合是否最優(yōu)有待進一步分析。

5)令(X,Y)=(0，0，1，0.1，0.6，0.3)，初值設定與第4組相比，更改了惡意節(jié)點的初始策略比例，使數(shù)據(jù)更隨機，增加結(jié)論可靠性。仿真結(jié)果如圖5所示。

圖5 節(jié)點走勢圖Fig 5 Node trend image

分析：經(jīng)過博弈，仿真結(jié)果與圖4類似，網(wǎng)絡達到了擁塞避免的狀態(tài)，而唯一區(qū)別在于圖5需要達到穩(wěn)定的時間更多，該組的策略劣于上組。但本質(zhì)來說，這種比較是無意義的，因為正是惡意節(jié)點比例的變化造成了耗時的增加，而實際中無法預測或管理惡意節(jié)點的變化。因此，若不僅只滿足擁塞避免，更期待尋找到最優(yōu)的實現(xiàn)策略(即達到擁塞避免的耗時最少)，就需要設定在惡意節(jié)點初始比例不變的情況下嘗試。

6)令(X,Y)=(0，0.7，0.3，1/3，1/3，1/3)，初值保持了與第4組相同的惡意節(jié)點初始策略比例，正常節(jié)點隨機分配，采取不轉(zhuǎn)發(fā)和防御兩種策略。仿真結(jié)果如圖6所示。

分析：經(jīng)過博弈，仿真結(jié)果與圖3和圖4類似，網(wǎng)絡中正常節(jié)點全部采取了防御策略；惡意節(jié)點全部采取了轉(zhuǎn)發(fā)策略。網(wǎng)絡達到擁塞避免的目的，但從最優(yōu)角度講，該組策略的耗時比第4組更多，處于劣勢。

圖6 節(jié)點走勢圖Fig 6 Node trend image

4.4 仿真數(shù)據(jù)總結(jié)

六組仿真結(jié)果更直觀確切地反映了此博弈模型，分析比較可得，對于無線傳感網(wǎng)，加入防御性轉(zhuǎn)發(fā)策略是至關重要的。為了對抗惡意節(jié)點，保證網(wǎng)絡性能，在初始部署節(jié)點時，將其全部設定為防御性轉(zhuǎn)發(fā)策略。

5 結(jié) 論

本文針對無線傳感網(wǎng)進行了研究，突出惡意節(jié)點對網(wǎng)絡性能的危害，提出問題，建模分析,最終得到解決方案。利用博弈理論建立網(wǎng)絡模型，以節(jié)點具體收益為基礎，分析節(jié)點行為選擇，嘗試性加入新策略，不斷改變網(wǎng)絡節(jié)點的決策部署，利用軟件實時擬合仿真，多組結(jié)果橫向?qū)Ρ?，從中選出最佳策略組合，達到既定目的，進而得到具有實際意義的適用性結(jié)論。本文可為無線傳感網(wǎng)對抗惡意節(jié)點，實現(xiàn)擁塞避免工作提供實質(zhì)性指導。

[1] 周新蓮.基于分簇技術的移動無線傳感器網(wǎng)絡數(shù)據(jù)收集協(xié)議研究[D].長沙：中南大學,2010.

[2] 劉擁民,蔣新華,年曉紅.無線傳感網(wǎng)擁塞控制研究[J].計算機應用研究,2008,25(2):565-571.

[3] 邱麗娟,姜 宇,胡成全.無線傳感器網(wǎng)絡可靠性研究進展[J].傳感器與微系統(tǒng),2011,30(10):1-3.

[4] 黃 莉.基于博弈論的無線網(wǎng)絡節(jié)點行為研究[D].北京：北京交通大學,2011.

[5] 戚玉娥.基于網(wǎng)絡流的流量異常檢測研究[D].濟南：山東師范大學,2009.

[6] Yim S,Choi Y.Neighbor-based malicious node detection in wireless sensor networks[J].Wireless Sensor Networks,2012,4(9):219-225.

[7] 陳 英,舒 堅,陳宇斌,等.無線傳感器網(wǎng)絡技術研究[J].傳感器與微系統(tǒng),2007,26(10):1-4，8.

[8] 盛 燕.無線傳感網(wǎng)惡意節(jié)點識別技術研究[D].哈爾濱:哈爾濱工程大學,2008.

Game theory analysis of against malicious nodes in sensor networks

YUAN Zhi-rong1, WU Yi-kun2, WANG Jun-qiang1, JIANG Wei-dong2

(1.Institute of UAV,Northwestern Polytechnical University,Xi’an 710065,China；2.College of Electronics and Information,Northwestern Polytechnical University,Xi’an 710072,China)

Wireless sensor networks(WSNs)is a widely applied multi-hop Ad Hoc networks,it is composed of hundreds of resources limited sensor nodes.When data is transmitting,if traffic load of node exceeds its available bandwidth,congestion will occur,so that transmission is unreliable.This is especially true in special work environment in WSNs,when there are malicious nodes,will be more serious.Introduce game theory,research on WSNs with presence of malicious node research,analyze behavior of nodes,establish game model,implementation steps and verification scheme are given,synthesize theoretical analysis and simulation results,get the optimal strategy of node,achieve goal of network congestion avoidance.

wireless sensor networks(WSNs); game theory; malicious node; congestion avoidance

10.13873/J.1000—9787(2016)07—0009—04

2016—04—26

TN 919

A

1000—9787(2016)07—0009—04

袁智榮(1965-)，男，陜西寶雞人，研究員級高級工程師，主要從事傳感器應用與控制的研究。