基于序貫概率比檢驗的自私路徑檢測方法

王騏，王青萍，王懷興，肖正安

（湖北第二師范學院，湖北 武漢 430205）

基于序貫概率比檢驗的自私路徑檢測方法

王騏，王青萍，王懷興，肖正安

（湖北第二師范學院，湖北 武漢 430205）

根據基于序貫概率比檢驗的無線傳感器網絡模型，對基于路由功能的自私路徑的檢測方法進行了研究。通過分析節點接收到的觀測樣本值，將計算得出的路徑評判值與已知閾值進行比較，從而判定是否為自私路徑。仿真結果表明，這種基于序貫概率比檢驗的序貫抽樣方案所需觀測值的數量大大減少，運行更快，且具有較高的檢測精度。相比于其他固定抽樣方案，這種方法無需事先確定檢驗統計假設所需的樣本觀測值數量，有利于對危害網絡安全的行為做出快速響應，從而限制受損網絡的范圍。

無線傳感器網絡；序貫概率比檢驗；網絡模型；自私行為檢測；評判；NS-2仿真

1 引言

無線傳感器網絡是由無人值守的節點形成的一種動態通信網絡。在網絡層的路由選擇中，這種自組織網絡需要節點間的相互協作，共同尋找到達目標節點的可行路徑，共同參與數據分組的轉發，否則將無法找到可行路徑完成端對端的數據分組傳送。根據網絡層的路由功能以及節點的行為，可將節點分為協作和自私兩種類型。“自私”是一種故意的消極行為，為了節省資源，自私節點可能不參與數據分組的轉發，丟棄部分或全部經由自身轉發的數據分組［1，2］。這些自私行為將會大大弱化網絡性能，甚至會導致全網通信癱瘓。因此，從網絡安全和性能的角度出發，需要找出網絡中的自私節點。

如何檢測出自私節點，一些國內外相關文獻提出了一些解決辦法。參考文獻［3］介紹了一種將檢測節點獲得的單位時間特征量值與閾值進行對比來判斷自私節點的方法；參考文獻 ［4］采用基于序貫概率比檢驗（sequential probability ratio test，SPRT）的方法，對節點不與周圍節點發生消息通信的時間進行閾值設定，從而檢測發起動態攻擊的節點；參考文獻［5］通過一種基于序貫概率比檢驗的檢測算法，檢測無線傳感器網絡中MAC層的非協作行為；參考文獻［6］闡述了MAC層的自私行為問題，并將此問題轉化為極小—極大頑健序列檢測問題；參考文獻［7］針對無線傳感網絡共享信道中自私節點（或惡意節點）對信道的不公平競爭行為，提出了一種基于網絡性能特征序列的聚類檢測方法。

以上這些檢測方法檢測的對象都是直接針對節點，觀測值或取樣樣本的數量較大，不僅影響運行效率，對能耗要求也較高，不利于對危害網絡安全的行為做出快速響應。與一般的檢測方法不同的是，基于序貫概率比檢驗的自私路徑檢測方法采用序貫抽樣方案，并不直接檢測自私節點，而是首先檢測自私路徑，再從自私路徑中檢測自私節點。這樣做的好處是縮小了檢測范圍，避免“大海撈針”，有利于降低能耗；另一方面，由于無需事先確定檢驗統計假設所需的樣本觀測值數量，因此所需觀測值的數量大大減少，能有效提高運行效率和檢測精度。

2 基于序貫概率比檢驗的網絡模型

序貫概率比檢驗是數理統計學的一個分支，它研究的對象是“序貫抽樣方案”及如何用這種抽樣方案得到的樣本進行統計推斷。序貫抽樣方案是指在抽樣時不事先規定總的抽樣個數（觀測或實驗次數），而是先抽少量樣本，根據其結果再決定停止抽樣或繼續抽樣、抽多少，直到決定停止抽樣為止。反之，事先確定抽樣個數的抽樣方案，稱為“固定抽樣方案”。

考慮以下的無線傳感器網絡模型：該網絡節點類型分為自私型和協作型，節點集記作 N=｛N1，N2，N3，…，Ni}，其中 i=1，2，3，…，n；自私節點集為 M=｛M1，M2，M3，…，Mi}，其中 i=1，2，3，…，n，且M?N。網絡內的節點數量記作|N|，自私節點的數量記作|M|，所以協作節點的數量為|N|-|M|。一般來說導致分組丟失的因素主要包括以下幾個方面。

· 自私節點。設任意自私節點i∈M的分組丟失概率為Pselfish。

· 網絡環境。比如網絡層的擁塞、數據鏈路層的爭用、

信道衰落引起的通信受損等。為了簡化起見，假定所有節點i∈N因網絡環境因素產生的分組丟失概率為Pdrop。

下一步考慮不同節點具有不同分組丟失概率的情況。

定義1 設網絡內起始節點為s=h0，目標節點為d，從起始節點s=h0到目標節點d之前的最后一個節點為hk，Rs?d=｛h0，…，hk}表示從起始節點 s=h0到 hk之間路徑上的有序節點集，那么從起始節點到目標節點，即h0→hk→d經歷的跳數為 k+1。

定義 3 Rs?d上的有序關系為：?x，y∈Rs?d，x＜y?hop（x，s?d）＜hop（y，s?d），其中，x、y 表示從起始節點 s到目標節點 d 之間路徑上的中間節點，節點 hop（x，s?d）、hop（y，s?d）分別表示從起始節點s到中間節點x、y之間所經歷的跳數。

定義 4 如果?hj∈，且 hj∈M，i＜j≤k，則路徑為自私路徑，即包含自私節點的路徑；否則為正常路徑，即不包含自私節點的路徑。

3 自私路徑的檢測

3.1 序貫概率比檢驗概述

假定存在兩種假設H1和H0，在這兩種假設中，要么H1正確，要么H0正確，不可能同時正確。相應地，兩種假設下的條件概率分別為 P［x|H1］和 P［x|H0］［3，4］。為了判斷兩種假設 H1和 H0哪個正確，進行一系列的觀測 x1，x2…，對于每個樣本觀測值 xn，n≥1，如果 P［x|H0］≠0，計算以及其中，n≥1，T0=1。然后以 Tn為依據，根據以下準則進行判斷。

判別式1 ①如果Tn較大，表明當前獲得的樣本觀測值 x1，…，xn更有可能是在假設 H1下獲取的，因此，H1正確；②如果Tn較小，則表明當前獲得的樣本觀測值x1，…，xn更有可能是在假設H0下獲取的，因此，H0正確；③如果Tn值的大小不足以判別當前的樣本觀測值x1，…，xn是在H1還是在H0下獲取的，那么就進行第n+1次觀測，獲取xn+1的值，計算Tn+1。如果根據Tn+1的值仍然無法確定H1和H0哪一個正確，再進行第n+2次觀測，獲取xn+2的值，計算Tn+2。以此類推，直到能根據①或②判別出H1和H0哪個正確為止。

在對H1和H0進行判別時，也有可能做出錯誤的判斷，即理論上H1是正確的，但實際上正確的是H0，這種情況稱為假肯定；相反地，如果理論上H0是正確的，但實際上正確的是H1，這種情況稱為假否定。根據網絡目標，假設預期的假肯定率和假否定率的上限值分別為α和β，為了將二者限制在α和β內，選取兩個閾值A和B，且B＜A。閾值A和B分別有界，且如果以A=作為閾值，將會獲得較高的檢測精度［6］。顯然，α和β的值越小，那么當判斷H1和H0哪個正確時，系統所需要的樣本觀測值就越多。在獲取一系列樣本觀測值x1，…，xn之后，由于選取了檢驗閾值 A和 B，那么判別式 1可表述如下。

判別式2 ①如果Tn≥A，則H1是正確的；②如果Tn≤B，那么H0是正確的；③如果B＜Tn＜A，那么就進行第n+1次觀測，獲取xn+1的值，計算Tn+1。如果根據Tn+1的值仍然無法確定H1和H0哪一個正確，再進行第n+2次觀測，獲取xn+2的值，計算Tn+2。以此類推，直到能根據①或②判別出H1和H0哪個正確為止。

3.2 基于序貫概率比檢驗的自私路徑檢測

根據第3.1節所述，現假定存在兩種假設H1和H0，其中H1表示自私路徑，H0表示正常路徑，現在需要鑒別哪種假設成立。如果網絡存在某種端對端數據分組傳送的反饋機制，且采用可靠的運輸層協議（比如TCP），那么運輸層就會以TCP確認的方式來進行反饋。假定以“數據分組的確認（acknowledgement，ACK）”作為數據分組發送成功的標志，將觀測值記為ACK，稱作ACK事件；以“數據分組的再發送（retransmission，RET）”作為數據分組發送失敗的標志，將觀測值記為RET，稱作RET事件。因此，當觀測值為ACK時，表明數據分組發送成功；當觀測值為RET時，表明數據分組發送失敗［4，5］。假定節點 hi∈Rs?d，路徑 Ris?d的評判 值表 示為 T（i，Ris?d）。根據 Ris?d上節 點 hi的 觀測 值 xn為ACK或RET，對路徑Ris?d是否為自私路徑進行評判，則：

3.3 T（i，Ris?d）的 計 算

· 對于任意節點hi∈Rs?d，如果獲得觀測值 xn=ACK，由于網絡運輸層采用了可靠的TCP，因此所有其他節點 hj（k≥j＞i）也將接收到相同的觀測值 ACK。同理，任意節點 hi∈Rs?d，如果獲得觀測值 xn=RET，那么所有其他節點hj（0≤j＜i）也將接收到相同的觀測值RET。

· 任 意節 點 hi∈Rs?d根據表達 式 T（i，Ris?d），能評判 的 路徑僅 是 Ris?d，而不 是完整路徑 Rs?d。因此，如果 節點hi的實際觀測值為ACK，卻收到觀測值為RET的數據分組，則表明ACK在路徑Ris?d上被丟棄，這種情況下，節點hi將把數據分組RET看成新的數據分組。

根據以上分析，有：

當節點 hi∈Rs?d時，P［x1］和 P［x2|x1］的大小受路徑 Ris?d上自私節點數量的影響。具體來說，路徑Ris?d上自私節點越多，P［x1］和 P［x2|x1］的值就越小。

令α表示路徑Ris?d上自私節點的實際數量，那么α=。如果路徑為正常路徑，那么 α=0；否則，1≤α≤min（k-i，|M|），其中，k-i為 hi→hk路徑上所經歷的節點數量（不包含起始節點hi）。假定路徑Ris?d上自私節點的實際數量為 α，分組丟失概率為 Pselfish，那么路徑 Ris?d上至少有一個自私節點發生分組丟失的概率為：

實際上 P∏（selfish）表示的是 α 個自私節點對自私路徑 Ris?d的總體影響，因此有：

根據式（4）、式（6）、式（7），有：

因 此 ，P［ACK|H0］、P［ACK|H1］、P［RET|H0］和 P［RET|H1］的值可以確定。

· 如果 Ris?d為 正常路徑，由式（5）有 P∏（selfish）=0，根據

式（8），有：

· 如果 Ris?d為自私路徑，根據式（8），有：

綜上所述，根據Ris?d上節點hi的觀測值xn，有如下結論。

· 如果 xn=ACK，根據式（1）、式（9）、式（11），有：

· 如果 xn=RET，根據式（1）、式（10）、式（12），有：

根據式（13）、式（14）及判別式 3，就可以判斷路徑 Ris?d是否為自私路徑。

4 模型的評估

運用NS-2工具對以上檢測方法的精度進行評估。根據以上網絡模型的定義，模型中 Pdrop和 P∏（selfish）的具體值以及路徑的具體跳數均不能具體指定，但可給出它們的預估參數值。

4.1 模型的實現

模型的預估參數如下。

·Pdrop：根據節點周圍網絡分組丟失和數據分組轉發的情況，得出Pdrop的預估值。

· P∏（selfish）：根據式（5），由于無法確定路徑上自私節點的確切數量（也就是模型中的 α 值），所以 P∏（selfish）的值也無法確定。實際上，P∏（selfish）是根據網絡目標而設定的網絡參數，是反映網絡對自私行為容忍度的參數 值 ，表 示 為，P∏（selfish）的 實 際 值 表 示 為。例如，如果的值被設定為0.4，那么網絡的目標就是檢測≥0.4的自私路徑。這也表明，網絡能夠容忍≥0.4的自私路徑。

· 路徑的跳數：節點根據自身的路由表，可以獲取通往路徑上某目標節點的跳數，但是反過來，從目標節點通往該節點的跳數無法確定。模型作了如下一階近似估計：路徑的總跳數=2×前向路徑跳數。

· T（i，Ris?d）的更新：節點 hi∈Rs?d保存每條活躍路徑 Ris?d

（即路由表項未過期的路徑）的評判記錄值 T（i，Ris?d）。每當 hi接收到Ris?d上的觀測值 xn時，都會對評判記 錄 T（i，Ris?d）進行更新。在節點 hi的路由表中 ，如果Ris?d被更新，那么 T（i，Ris?d）的值將會被重置為初始 值。因 此 ，每條路徑 T（i，Ris?d）的評判是獨立的。每個節 點都保留模型的閾值 A 和 B，T（i，Ris?d）記錄的初始化和更新以及自私路徑或正常路徑的判別見第2.2節。

4.2 評估

本節對模型進行評估，包括：根據模型的參數預估值，評估模型對自私路徑和正常路徑的檢測能力；對于給定的，當增大時，它如何影響檢測的精度。為此，采用兩種不同的設置，運用NS-2工具進行仿真。

· 第一種設置S1=0.4=0.75。

· 第二種設置S2：=0.4，=1。

網絡由100個節點組成，分布在一個10×10的網格中，在可通信的范圍內，每個節點有4個鄰居節點（邊緣節點和邊角節點分別只有3個和2個鄰居節點）。網絡負載由恒定比特率的流量生成器產生，每次流量大約產生200個數據分組，隨機選取數據分組的“源—目標對”。網絡運輸層采用可靠的TCP，介質訪問標準采用IEEE 802.11，路由協議采用AODV。以參考文獻［8，9］中定義的假肯定和假否定作為基礎，對模型進行評估。評估的依據是：①每個節點的判決結論（H1或H0）；②根據所有節點的判決結論得出的假肯定率和假否定率。兩種設置下的模型參數值為：α=5%，β=10%。根據第2.1節所述，閾值A=18，B=10.53。選取5種不同的TCP網絡負載，各運行30次，實際得到的假肯定率和假否定率如圖1所示。

圖1 模型的檢測精度

· 假肯定率分析：圖1（a）表明，兩種設置S1和 S2下的假肯定率的收斂值大約為3%，且幾乎一致。假肯定的發生，是由于重新發送數據分組時，將正常路徑錯誤地檢測為自私路徑。由于路徑實際上是正常，因此的，所以值的大小并不會影響數據分組的再發送。因此，對于給定的，盡管的值不一樣，但是假肯定率幾乎是一致的。

· 假否定率分析：圖1（b）表明，兩種設置S1和 S2下的假否定率的收斂值大約為8%，且隨的增大而減小。假否定的發生是由于路徑上發生ACK事件，將自私路徑錯誤地檢測為正常路徑。隨著的增大，在自私路徑上發生ACK事件的概率會隨之減小，因此，假否定率也會隨之減小。

· 評估結論：仿真結果表明，即使模型參數的估計值存在誤差，實際的假肯定率和假否定率仍然分別以α和β為界，說明這種基于序貫概率比檢驗的自私路徑檢測方法具有良好的檢測能力；如果給定，那么檢測精度隨著-差值的增大而增大。

5 結束語

本文介紹了一種基于序貫概率比檢驗的檢測自私路徑的方法，自私節點的檢測成效應通過3個指標參數來評價：檢測率（自私節點被檢測出來的成功率）、假肯定率（協作節點被鑒別為自私節點的錯誤率）、假否定率（自私節點被鑒別為協作節點的錯誤率）。一種好的檢測方式，應該具有較高的檢測率以及較低的假肯定率和假否定率。相比于其他檢測方法，SPRT運行更快，且不需要預先確定樣本觀測值的數量。采用仿真工具NS-2，驗證了這種方法的檢測精度。檢測自私路徑并不能完全消除自私行為帶來的影響。如果自私節點（模型參數表示為Pselfish）對網絡性能產生的不利影響遠大于網絡環境（模型參數表示為Pdrop）所產生的不利影響，那么檢測和隔離自私節點對網絡的生存就顯得至關重要，這方面的內容有待以后繼續研究。

［1］DJENOURI D，KHELLADI L，BADACHE N.A survey of security issues in mobile ad hoc and sensor networks ［J］.IEEE Communications Surveys&Tutorials，2005，7（4）：2-28.

［2］MICHIARDI P，MOLVA R.Core：a collaborative reputation mechanism to enforce node cooperation in mobile ad hoc networks［C］／／The IFIP TC6／TC11 6th Joint Working Conference on Communications and Multimedia Security，September 26-27，2002，Portoroz，Slovenia.New York ：SpringerUS，2002：107-121.

［3］張帥，張鳳斌.無線傳感器網絡中基于規范的入侵檢測算法研究［J］.計算機應用與研究，2012，29（9）：3464-3466.ZHANG S，ZHANG F B.Research on intrusion detection algorithm based on specification for WSN ［J］.Application Research of Computers，2012，29（9）：3464-3466.

［4］HO J W，WRIGHT M，DAS S K.Distributed detection of mobile malicious node attacks in wireless sensor networks［J］.Ad Hoc Networks，2011，10（3）：512-523.

［5］RONG Y，LEE S K，AND CHOI H A.Detecting stations cheating on backoff rules in 802.11 networks using sequential analysis ［C］／／IEEE INFOCOM ’06， April23-29， 2006，Barcelona，Catalunya，Spain.New Jersey：IEEE Press，2006：1-13.

［6］RADOSAVAC S， BARASJS， KOUTSOPOULOSI.A framework for MAC protocol misbehavior detection in wireless networks ［C］／／The 4th ACM Workshop on Wireless Security，September 2，2005，Philadelphia，PA，USA.New York：ACM Press，2005：33-42.

［7］陳波，毛劍琳，郭寧，等.基于K-means算法的無線傳感器網絡 節點自私 行 為檢測方 法 ［J］. 系統 仿 真 學 報，2014，（3）：580-585.CHEN B，MAO J L，GUO N，et al.Detection method for selfish behavior of wireless sensor networks nodes based on K-means algorithm［J］.Journal of System Simulation，2014（3）：580-585.

［8］王騏，蔡子元，范慧璞.一種檢測被捕獲節點的基于異常的算法研究［J］.壓電與聲光，2014，36（6）：1030-1034.WANG Q，CAI Z Y，FAN H P.Research on an anomaly-based intrusion detection algorithm for compromised nodes in wireless sensor networks［J］.Piezoelectrics&Acoustooptics，2014，36（6）：1030-1034.

［9］王騏，王殊，孟中樓.無線傳感器網絡中一種基于能效的入侵檢測算法 -3N 算法研究［J］.微電子學與計算機，2010，27（4）：153-157.WANG Q，WANG S，MENG Z L.Research on energy-efficiency intrusion detection algorithm （3Nalgorithm）in wireless sensor networks［J］.Microelectronics&Computer，2010，27（4）：153-157.

Detection method for selfish routes based on the sequential probability ratio test

WANG Qi，WANG Qingping，WANG Huaixing，XIAO Zheng’an
Hubei University of Education，Wuhan 430205，China

According to a network model based on the sequential probability ratio test （SPRT），one detection method of selfish routes with respect to the routing functionality in wireless sensor network was developed.Through the analysis of the observed sample values of the nodes，the calculated routes evaluation values were compared with the known threshold values so as to determine whether it was selfish route.Simulation results show that the sequential sampling scheme based on the sequential probability ratio test had high detection accuracy，and the number of the required observation was greatly reduced，so it could operate faster.A merit of SPRT is that the number of observations required to test statistical hypotheses need not be determined in advance when compared to other methods based on a fixed number of observations.This allows for making prompt decision on the behavior of damage to the network，thus it can limit the scope of the damaged networks.

wireless sensor network，sequential probability ratio test，network model，misbehavior detection，evaluation，NS-2 simulation

Hubei Provincial Department of Education Research Program （No.T201417）

TN918.91

A

10.11959／j.issn.1000-0801.2016059

2015-08-17；

2016-01-08

湖北省高等學校優秀中青年科技創新團隊基金資助項目（No.T201417）

王騏（1970-），男，博士，湖北第二師范學院副教授，主要研究方向為無線傳感器網絡安全、嵌入式系統應用。

王青萍（1980-），女，博士，湖北第二師范學院副教授，主要研究方向為光電功能材料與器件。

王懷興（1977-），男，博士，湖北第二師范學院講師，主要研究方向為虛擬儀器技術。

肖正安（1974-），男，湖北第二師范學院講師，主要研究方向為數字信號處理。