無線傳感器網絡中基于分簇的節點定位異常檢測

摘 要:在引入WSN分簇結構基礎上，提出一種分布式的節點定位異常檢測方法，利用聚類拓撲減少通信量，同時降低以往集中式檢測存在的單點風險。該方法不需要任何已知的部署知識或額外的硬件，每個簇的簇頭節點只需根據該簇節點報告的位置和鄰居表信息進行過濾計算，更新權值，即可確定和撤銷定位異常的節點。通過理論分析和仿真模擬驗證了這種基于分簇的節點定位異常檢測方法的正確性和有效性。

關鍵詞:無線傳感器網絡;節點定位;異常檢測;位置驗證;分簇

中圖分類號:TP393 文獻標志碼:A

文章編號:1001-3695(2010)03-1139-03

doi:10.3969/j.issn.1001-3695.2010.03.092

Node localization anomaly detection based onclustering in wireless sensor networks

ZHANG Yu-qin，QIN Zheng

(College of Software， Hunan University， Changsha 410082， China)

Abstract:On top of a clustering WSN architecture，this paper proposed a distributed scheme to detect localization anomaly.The clustering network could reduce the communication overhead between sensor nodes by utilizing clustered topology， and didn’t have the risk of single point of failure. This method didn’t need any deployment knowledge or hardware. According to compute the location and neighbor list from the sensor node，updated its weight by the cluster head，this scheme could filter the anomaly node.The simulation verifies the correctness and efficiency of this scheme.

Key words:wireless sensor networks(WSNs); node localization; anomaly detection; location verification; clustering

0 引言

在無線傳感器網絡(WSNs)中，節點的位置信息至關重要，它不僅是提供監測事件或目標位置信息的前提，也是實現傳感器網絡各項功能的基礎[1]。許多應用都是基于傳感器的位置信息，如環境監測、目標跟蹤、地理路由等。然而，由于傳感器未帶防竄改的硬件和傳感器網絡的開放性、無人看護性，使得節點定位過程極易受到來自惡意節點或被俘獲節點的攻擊，從而產生一些錯誤的位置信息[2]。此類信息如果不能被及時檢測，將會產生錯誤的位置報告，給基于位置的應用帶來嚴重的后果，可能導致基于位置的路由協議陷入混亂，或者惡意節點通過編造位置信息發動進一步的攻擊，包括Sinkhole攻擊、Wormhole攻擊等，對網絡造成更大的危害。因此，應用軟件在使用傳感器的位置信息之前，需要先對節點報告的位置信息進行判斷，檢測傳感器定位是否存在異常，這是傳感器網絡近年來的一個重要研究領域[3~5]。

目前，已提出的定位異常檢測方法有很多，但大部分都依賴于可用的已知部署信息或額外的硬件，不適用于一般的WSNs，而且很多方法都是通過基站來進行整個網絡的集中式檢測，存在通信量大、單點易失效等問題，一旦基站被損壞，整個檢測系統將失效。針對這種集中式檢測存在的問題，本文提出了一種基于分簇的節點定位異常檢測方法(BCLAD)。該方法引入了基于分簇的網絡拓撲結構，這種結構相當于一個分布式的信息聚合系統，一部分的SN被組織在一起，由簇頭控制，簇頭負責收集本簇內的數據進行整合處理，將結果上報給AP，AP負責處理簇頭上傳的數據，并與有線網絡進行通信。這種網絡結構可以有效降低網絡開銷，而且不存在單點失效問題。簇內的檢測采用MFWT(基于矩陣過濾的權重信任)算法，它不需要任何已知部署信息或額外硬件，只須根據傳感器報告的位置Li和鄰居表信息來計算差異矩陣。利用矩陣過濾出位置異常的節點，再根據過濾結果更新每個傳感器的權值，定位異常節點的權值將不斷減少，而正常節點的權值保持不變。通過一定次數的反復后，權值低于閾值的節點即為異常節點，會被簇頭檢測出來，繼而上報給基站。通過理論分析和模擬實驗證明，這種異常檢測方法可以有效降低通信量，并能保證較好的檢測率。

1 相關工作

定位異常檢測是指通過位置驗證方法來檢測一個節點是否確實在它所聲稱的位置，這是近年來的一個熱點安全問題。Sastry最先在文獻[6]中解決該問題，他采用計算超聲波和無線電的傳播時間差的方法驗證節點是否在特定的區域內(如一個房間)，但這種方法只能實現有限的判斷(在區域內/不在區域內)，而且超聲波傳播距離較短，容易受到干擾，不適合在野外大面積部署傳感器網絡。Capkun等人[7]提出了基于距離界定協議的VM(verifiable multilateration)機制。該機制借助一個授權節點和若干信標節點協作實現網絡中未知節點的安全定位和對定位結果的驗證，但該方法沒有考慮參考點被俘獲的情況，而且該方案依賴高速硬件測定無線電在空氣中傳播的時間，成本較高。Bahl等人[8]使用信號強度測試的方法估計移動節點在室內的位置，這種方法需要事先知道室內的信號強度分布地圖，這對于在野外大規模部署的傳感器網絡(特別是戰場監視等場合)是不可行的，而且，它是一種集中式的檢測方法，會給基站帶來很大的計算和存儲開銷。Du等人[9]提出了LAD算法，該方案借助在許多傳感器網絡應用中可以事先獲知的節點分布信息以及鄰居節點間的組關系，檢測節點的估計位置是否與它的觀測位置相一致。然而，LAD方案依賴于節點的分布信息，如果無法獲得精確的分布概率， LAD 的檢測結果將會受到極大影響。

2 基于分簇的節點定位異常檢測

2.1 網絡模型與假設

在這里引入一個基于分簇的網絡拓撲結構，在這種網絡中，整個傳感器網絡形成分層結構，傳感器節點通過由基站指定或者自組織的方法形成各個獨立的簇(cluster)，每個簇選出相應的簇頭(cluster head)，由簇頭負責簇內節點的控制，并對簇內所收集的數據進行整合、處理，隨后轉發給基站。這種分層式網絡結構既通過簇內控制減少了節點與基站遠距離的信令交互，降低了網絡建立時的復雜度，減少了網絡路由和數據處理的開銷，同時又可以通過數據融合降低網絡負載，減少了網絡的能量消耗。

本文采用的分簇式網絡拓撲結構如圖1所示，它包括三種類型節點:

a)傳感器節點(sensor node，SN)——網絡最底層，負責監測環境的數據收集;

b)簇頭節點(cluster head，CH)——負責將該簇中所有SN收集到的數據傳遞給上層;

c)接入點(access point，AP)——整個網絡的最高層，負責無線網絡與有線網絡之間數據的發送與接收。

這種基于分簇的網絡模型相當于一個分布式的信息聚合系統，每個傳感器有惟一的ID號。一部分的SN被組織在一起，由高層的簇頭CH控制，因此，每個SN只需要負責與它的簇頭CH通信，CH位于SN的上層，負責與它的上層AP和其他CH通信。AP負責處理簇頭上傳的數據，并與有線網絡進行通信。這種網絡結構相比傳統的網絡來說，只是增加了一些簇頭節點的數目，但是使得通信開銷大大減少，而且即使在一部分的節點受到損害后，整個網絡還是有足夠的健壯性。在這里假設簇頭CH和AP都是可信的。

2.2 基于分簇的節點定位異常檢測原理

在傳感器初始化部署后，整個網絡采用成簇協議選出簇頭并將網內節點分簇，在簇內，每個傳感器廣播它的ID號給鄰居，獲得它的鄰居ID表，然后向它的簇頭節點CH報告自己的位置Li和鄰居表信息。每個簇的簇頭節點CH收到該簇中所有節點上報的信息后，執行MFWT算法(見2.3節)對本簇所收到的位置信息進行檢測，把沒有通過檢測的傳感器ID號上報給AP，AP把該ID號廣播給整個傳感器網絡，通知將該傳感器從網絡中排除，不再使用其收集的信息。

2.3 基于矩陣過濾的權重信任算法(MFWT)

針對以前的定位異常檢測需要硬件或已知部署知識的問題，本文提出了基于矩陣過濾的權重信任算法MFWT，它只需要根據傳感器報告的位置Li和鄰居表信息來計算差異矩陣，利用矩陣過濾出來位置不一致的節點，根據過濾結果更新每個傳感器的權值，對于位置異常的節點其權值將不斷減少，通過一定次數的反復后，權值低于閾值的節點被檢測出來上報給AP。

a)計算差異矩陣Md

首先計算鄰居矩陣Mn。它由傳感器的鄰居表信息構成，傳感器的總數是n，矩陣Mn是一個n×n矩陣，里面的元素Mn(i，j)滿足下列情況:

Mn(i， j)=1 若j在i的鄰居表內

0若j不在i的鄰居表內(1)

接著是通信矩陣Mc。矩陣Mc是通過比較傳感器報告位置之間的距離與通信范圍構成的，里面的元素Mc(i，j)滿足下列情況:

Mc(i， j)=1 若dij≤R

0若dij>R(2)

其中:(xi，yi)和(xj，yj)是傳感器報告的位置;dij是i和j之間的歐式距離;R是傳感器之間的通信范圍。

在構建完Mn和Mc后，差異矩陣Md通過異或它們的元素組成:

Md=MnMc

(3)

在Md中，若元素為0，則代表鄰居的觀察值與所報告的位置一致，如Mn(i，j)=1，Mc(i，j)=1，異或后Md(i，j)=0，代表傳感器i可以觀察到j，i與j之間的距離也在通信范圍內，這是正常的。若元素非零，則代表鄰居的觀察值與所報告的位置存在矛盾。例如，Mn(i，j)=1，Mc(i，j)=0，異或后Md(i，j)=1，代表傳感器i可以觀察到j，但是根據它們的報告位置計算可知它們不是鄰居。只要這些矛盾存在，可以用矩陣Md來檢測異常位置。

b)利用Md過濾可疑異常節點

定義三個變量AD、PD和AS，利用這幾個變量來過濾可疑的節點。具體定義如下:

ADi=nk=0Md(i，k)(4)

它是差異矩陣Md中第i行的元素總和，量化了所得到的鄰居關系與i本身的觀察之間的不一致性。

PDi=nk=0Md(k，i)(5)

它是差異矩陣Md中第i列的元素總和，量化了所得到的鄰居關系與其他節點對i的觀察之間的不一致性。

ASi=nk=0|Md(i，k)-Md(k，i)|(6)

它量化了兩個傳感器之間通信的不對稱程度。

檢測開始，CH計算所有傳感器的矩陣Md和變量AD、PD和AS，然后比較它們與相應的閾值。如果有任何傳感器的變量值超過閾值，CH將它的ID號記錄下來(如節點k)，并設置矩陣Mn和Mc的第k行和第k列元素為0。在接下來每一輪中，CH重建Md，重新計算這些變量，并過濾掉當前輪中最不正常的傳感器，直到所有變量值低于閾值。被過濾出來的這些傳感器都是可疑的異常節點，剩下的都通過驗證，為正常節點。

c)更新權值并確定異常節點

在這里加入權重信任機制，是為了減輕由于定位所產生的誤差。傳感器在部署后，會給每個傳感器i設置一個權值初值wi，在經過矩陣過濾以后，每個節點的權值更新基于式(7):

Wi=wi-θ 若i為可疑節點

wi若i為正常節點(7)

其中:θ為權重處罰值，當一個節點被確定為可疑節點，它的權值就減少θ。權值更新以后，CH就可以根據權值是否低于門限值來確定位置異常的節點。CH把沒有通過檢測的傳感器ID號上報給AP，AP把ID號廣播給整個傳感器網絡，通知將該傳感器從網絡中排除，不再使用其收集的信息。

3 實驗與分析

下面采用OMNET++作為實驗平臺對本文提出的基于分簇的定位異常檢測方法進行仿真模擬。仿真分析的網絡模型的主要參數如下:

a)測試區域大小為一個 300×300 的平面區域，500個節點隨機分布在該區域范圍內，傳感器的通信距離為20 m;

b) 節點部署后，采用LEACH協議對網絡中節點分簇，簇個數為5%;每一個節點都有單獨的ID號，以區別于其他的節點;

c)模擬異常節點的行為如下:它們距離自己真實位置的距離為D=30 m，為了迷惑檢測者，它們不但報告錯誤位置，同時報告的鄰居表也與錯誤位置一致。

每個實驗結果根據超過100次的獨立模擬后的平均值計算得到。

定義以下指標評估檢測方法的性能:

響應時間(response time，RT)，正確檢測出異常節點的平均周期，代表一個異常節點如何被快速地檢測出來。

檢測率(detection rate)，DR= Ndf/Nf。其中:Ndf是被檢測出來的異常節點的數目;Nf是整個網絡中異常節點的總數目。

誤判率(1 positive rate)，FP=Ndt/Nt。其中:Ndt為正常節點但被錯判為異常節點的數目;Nt是整個網絡中正常節點的總數目。

3.1 網絡密度的影響

設置異常節點比率為10%，異常程度為30 m，當權重處罰值分別為0.01和0.05時，本文評估了節點數目變化時對本方法的影響，如圖2、3所示。

從圖2中可以看出，隨著節點數目增加，網絡密度和檢測率都提高了。當節點數目從20增加到1 000時，檢測率和誤判率都相對穩定，尤其在節點數目超過100后，檢測率保持在80%以上，誤判率低于5%。這意味著，該方法具有很好的擴展性，在各種不同的網絡狀態下運行良好，特別是在網絡規模較大時，可以保持很好的性能。圖2和3也顯示了權重處罰值設置的影響，當處罰值較大時，響應時間較小，檢測速度更快，但同時也導致誤判率FP較高，因此在實際中要根據具體的網絡需求來選擇合適的處罰值。圖4顯示了節點數目為500時，權重處罰值的設置對方法性能的影響。從圖中可以看出，當權重處罰值增加時，檢測率比較穩定，但誤判率FP有所提高。為了在檢測率和誤判率之間保持平衡，檢測權重處罰值取為0.01~0.1的值比較好，可以保證算法的性能。圖5是節點密度變化時本方法與文獻[5]提出的GFM算法進行的比較，兩種算法在節點密度較大時都能保持穩定的性能，本文的方法檢測率稍高一些。

3.2 異常程度的影響

設置節點總數目為500個，本文評估了異常程度對方法性能的影響，如圖6所示。

節點的異常程度包括兩個方面:a)異常節點占整個網絡節點數目的比例;b)某個節點的異常程度D(D為報告位置距其真實位置的距離)。圖6中，本文評估了在D分別為10 m，30 m，50 m，100 m時，異常節點比例從0.1增加到0.7的本方法的性能。從圖6可以看出，當異常比例增加時，檢測率有稍微的下降，這是因為更多異常節點的出現意味著聚合結果將會被更多的錯誤結果影響，但是總體看來，檢測率大都保持在80%以上，由此可見，該方法針對大規模的異常也能保持較好的檢測率，性能穩定。

圖7是本方法與文獻[5]提出的GFM算法在不同異常程度下的性能比較。文獻[5]的算法是一個集中式的檢測算法，從圖中可看出，當異常節點比率低于30%時，GFM算法還可保持較好的性能，隨著異常節點比率的增加，它的檢測率也快速下降，因此它只能適用于輕度異常的網絡，當網絡異常程度嚴重時，算法性能遠不如本文方法。

4 結束語

本文研究定位異常檢測，旨在發現由于錯誤的定位過程或惡意節點所造成的異常位置信息。針對傳統檢測方法存在的問題，本文引入了分簇式網絡結構，不再由基站進行集中式檢測，節點部署下去組合成簇后，由簇頭進行本簇內的檢測。這種分布式方法可以有效降低通信開銷，而且不存在單點失效的風險。簇頭只需根據傳感器報告的位置Li和鄰居表信息對簇內節點采用MFWT算法檢測定位是否存在異常，并確定異常節點上報給基站，不需要任何其他信息，實現簡單。仿真實驗表明，這種分布式的檢測方法在各種網絡環境中可以保證很好的性能，對研究傳感器如何安全地定位具有一定的意義。

參考文獻:

[1]

李建中，高宏.無線傳感器網絡的研究進展 [J].計算機研究與發展，2008，45(1):1-15.

[2]王福豹，史龍，任豐原.無線傳感器網絡中的自身定位系統和算法[J].軟件學報，2005，16(5):857-868.

[3]曹曉梅，俞波，陳貴海，等.傳感器網絡節點定位系統安全性分析[J].軟件學報，2008，19(4):879-887.

[4]LIU Dong-gang，NING Peng，DU Wen-liang.Detecting malicious beacon nodes for secure location discovery in wireless sensor networks [C]//Proc of the 25th Conference on Distributed Computing Systems.Washington DC:IEEE Computer Society，2005:609-691.

[5]WEI Ya-wen，YU Zhen，GUAN Yong.Location verification algorithms for wireless sensor networks[C]//Proc of the 27th International Conference on Distributed Computing Systems.2007:70-77.

[6]SASTRY N，SHANKAR U，WAGNER D.Secure verification of location claims[C]//Proc of the ACM Workshop on Wireless Security (WiSe).New York:ACM Press，2003:1-10.

[7]CAPKUN S，HUBAUX J P.Secure positioning of wireless devices with application to sensor networks[C]//Proc of the INFOCOM 2005. 2005:1917-1928.

[8]BAHL P，PADMANABHAN V N.RADAR:an in building RF-based user location and tracking system[C]//Proc oftheINFOCOM 2000.2000:775-784.

[9]DU Wei-liang，FANG Lei，NING Peng.LAD:localization anomaly detection for wireless sensor networks[C]//Proc of the 19th IPDPS.Orlando，FL:Academic Press，2006:874-886.