面向多跳無線網絡的多干擾源定位算法

王棋萍，魏祥麟，范建華，王統祥，胡飛

(1.解放軍理工大學通信工程學院，江蘇 南京 210007；2.南京電訊技術研究所，江蘇 南京 210007)

面向多跳無線網絡的多干擾源定位算法

王棋萍1，魏祥麟2，范建華2，王統祥1，胡飛1

(1.解放軍理工大學通信工程學院，江蘇 南京 210007；2.南京電訊技術研究所，江蘇 南京 210007)

提出一種面向多跳無線網絡的多干擾源定位算法，主要包括3個步驟：基于梯度下降法的分組投遞率谷點推定、基于梯度上升法的接收干擾強度(RJSS,

jamming signal strength)峰點推定和聚類分析。首先，算法從多個初始節點出發，采用梯度下降法，沿著分組投遞率梯度下降最快的方向逼近干擾源，直至到達分組投遞率谷點；然后應用功率自適應動態調整技術，采用梯度上升法，沿著接收干擾強度上升最快的方向繼續逼近干擾源，直至接收干擾強度峰點（也稱為RJSS停止節點）；最后通過對無法與RJSS停止節點通信的鄰居節點進行聚類分析，確定干擾源的數量和位置。模擬實驗表明，與現有算法相比，所提算法可以有效降低多干擾源定位過程的定位誤差；并且，當干擾源間距符合限定條件時，算法定位結果更優。

多跳無線網絡；干擾攻擊；干擾源定位；聚類

1 引言

作為實現泛在網絡連接的一種可行方式，多跳無線網絡在近年來發展迅速且得到了一些實際部署。但無線信道的開放共享特性使多跳無線網絡容易受到多種干擾攻擊，進而造成網絡性能惡化和服務質量下降。干擾攻擊是一種通過占用網絡節點通信信道，使其不能進行正常數據轉發的拒絕服務攻擊[1]。為了有效應對干擾攻擊，國內外研究者從物理層通信模式、鏈路層調度策略、網絡層路由算法和應用層服務質量調整等角度提出了包括信道級、鏈路級和網絡級在內的干擾消除或規避方法[2～6]。這些方法多數需要利用干擾源精確位置或所在區域信息以采取對應抗干擾手段[7,8]。為此，如何高效、準確地定位干擾源成為近年來學術和工業界研究的熱點問題之一。

干擾源定位是指多跳無線網絡中的被干擾節點，利用主動測量和被動監聽得到的多個協議棧層次的觀察結果，利用無線信道傳播特性和干擾區域幾何知識，協作推斷干擾源的相對或絕對位置的過程。現有的干擾源定位算法大致可以分為2類，即測距類和非測距類方法[9]。測距類定位算法通過選擇合適位置節點的物理屬性，建立其關于干擾源位置的關系，最終定位干擾源位置。非測距算法則根據干擾區域附近內外節點的位置信息，利用幾何知識對干擾源位置進行估計。這2類算法大多針對單個干擾源提出，無法應用于多干擾源并存場景。

為了達到高效、大范圍的干擾，攻擊者可以選擇在網絡中的不同位置發起干擾攻擊。在多個干擾源的協同工作下，網絡干擾區域增大，節點受干擾強度增強。針對這種場景，Cheng等[10]提出了一種稱為X射線的干擾區域定位算法。X射線定位算法包括干擾區域映射、干擾區域骨架化和干擾源位置確定3個步驟。該算法通過干擾區域骨架化，利用分叉點的位置信息反映干擾源的物理位置，由于區域邊界受噪聲影響較大，因此，X射線干擾區域定位算法定位精度偏低。另外，網絡范圍內的信息收集使X射線定位算法的通信復雜度很高，時效性差。

為了提高定位精度且減小定位開銷，本文提出了一種新穎的多干擾源定位算法。該算法包括3個主要步驟：基于梯度下降法的分組投遞率谷點推定、基于梯度上升法的接收干擾強度峰點推定和聚類分析。首先，算法從多個初始節點出發，采用梯度下降法，沿著分組投遞率下降最快的方向逼近干擾源，直至到達分組投遞率谷點；然后應用功率自適應動態調整技術，采用梯度上升法，沿著接收干擾強度上升最快的方向繼續逼近干擾源，直至接收干擾強度峰點（也稱為RJSS停止節點）；最后對無法與RJSS停止節點通信的鄰居節點進行聚類分析，并將聚類中心作為干擾源的估計位置。本文的主要貢獻在于：1) 提出了基于聚類分析的干擾源定位方法，可以在無需估計干擾源數量的情況下實現多干擾源準確定位；2) 設計了接收干擾強度梯度峰點推定過程，使聚類分析的開始節點更加靠近干擾源實際位置；3) 給出了干擾源間的距離與多干擾源可定位性的關系；4) 通過大量實驗分析，驗證了所提出定位算法定位精度顯著優于現有定位算法。

2 相關工作

為了定位多跳無線網絡中的干擾源，近年來，國內外研究者提出了一系列方案解決單個干擾源定位問題。在不采用特定專有設備的條件下，Pelechrinis等[11]發現越靠近干擾節點，分組投遞率就越低，并基于這個觀察結果，采用梯度下降方法設計了基于PDR梯度下降的定位算法。基于該算法在高干擾功率場景下產生的較大誤差，Wang等[12]應用功率自適應調節技術提出了一種基于PDR梯度下降的改進算法。基于干擾攻擊導致的網絡拓撲狀態變化和節點狀態改變，Liu等[13]提出了一個稱為虛擬力迭代定位的干擾節點定位算法。虛擬力迭代定位算法首先估計干擾節點的傳輸范圍，然后產生一個估計的圓形干擾區域，之后迭代，改變估計的干擾區域的中心來覆蓋最多的被干擾節點。虛擬力迭代定位算法假設估計的干擾節點位置等于真實的位置時，估計的區域與實際干擾區域重合。通過估計干擾攻擊發生前后的監聽范圍，Liu等[14]提出利用節點的監聽范圍解決一個最小平方問題來定位干擾節點。這種方法有效的前提是監聽范圍和網絡及節點狀態的改變僅是由干擾導致的。Liu等[15]還將干擾節點定位問題建模為一個非線性最優化問題，并提出使用基因算法或者模擬退火算法最小化干擾節點定位誤差。

基于無線傳輸的廣播特性，一些基于幾何學知識的干擾節點定位方法被陸續提出，包括質心定位、權重質心定位、虛擬力迭代定位、凸殼定位、阿爾法殼定位等。在質心定位方法(CL,centroid localization)中，干擾節點的鄰居節點被稱為被干擾節點。CL收集所有被干擾節點的坐標值，并將其均值作為干擾節點的估計位置。考慮到不同被干擾節點距離干擾節點的距離不同，其感受到的干擾強度也不相同，研究者提出了權重質心定位，一定程度上提高了定位精度[16]。Sun等[17,18]提出了一種基于幾何覆蓋理論的干擾節點定位算法。GCL算法利用計算幾何中的凸殼理論，特別是最小包容圓方法，對攻擊者進行定位。Cheng等[19]基于凸殼理論，利用最小邊界圓和最大內切圓來定位干擾節點。Xiong等[20]將干擾節點定位問題建模為一個最小平方問題，并基于線性回歸方法提出了一種健壯的干擾節點定位算法。利用干擾節點引起的拓撲變化，Liu等[21]首先基于最大生成樹分割網絡拓撲，然后基于拓撲分割結果和適應性最小平方和算法定位多個干擾節點。Rau等[22]結合基于序列改變檢測技術的本地檢測和基于最小平方法的全局檢測方法提出了一種混合干擾節點定位方法。

Cheng等[10]基于網絡干擾區域提出了一種X射線多干擾源定位方法，用以定位多個干擾源。該算法是一種基于干擾區域骨架化，利用分叉點對干擾源進行近似估計的集中式定位算法。骨架用與原始形狀連通性和拓撲結構相一致的曲線表達物體形狀，它是所有最大圓盤的圓心的集合，最大圓盤即是完全包含在物體內部，并且至少與物體邊界相切于兩點的圓。因此，干擾區域骨架化保留了區域的輪廓和位置信息。X射線多干擾源定位算法主要包括3個步驟：區域映射、區域骨架化和干擾源估算。

3 問題分析與模型假設

3.1 問題提出

多個干擾源通過協同工作，可以增加干擾強度并擴大干擾范圍，進而增加對多跳無線網絡的危害。在多干擾源并存場景下，各個干擾源的干擾區域可能存在重合，使干擾區域往往不再符合某個簡單的幾何形狀。在這種場景下，如果無法判斷干擾源數量并分割各自干擾區域，而是僅根據單個干擾源的假定進行定位，那么得到的最終位置顯然是錯誤的。圖1(a)和圖1(b)分別表示2個干擾源各自的影響，圖1(c)表示兩者共同存在的場景。可以看出，多干擾源并存時，多個節點的受干擾情況都發生了變化，干擾區域的特征更加復雜。因此，在此場景下，直接應用單干擾源定位方法無疑會帶來較大的定位誤差。注意到，當干擾源間距較大，干擾區域不存在重疊時，可以應用單干擾源定位算法對各干擾源分別進行定位。為此，本文只研究干擾區域重疊場景下的多干擾源定位問題。

圖1 多干擾源共存的干擾區域示意

由上述分析可知，與單干擾源定位相比，多干擾源定位面臨更復雜的問題。如何在干擾源數量未知且干擾區域存在重疊的場景下，精確定位各個干擾源的位置是本文需要解決的主要問題。

3.2 模型假設

本節限定了本文使用的網絡模型、攻擊模型以及傳播模型。

3.2.1 網絡模型

本文對多跳無線網絡的基本設定如下。

1) 節點靜態性：一旦網絡部署完畢，每個傳感器節點的位置不再發生變化。

2) 位置感知：每個節點都能感知自己和鄰居節點的位置坐標。這可以通過位置服務以及多跳無線網絡中的協議交互實現。

3) 節點同構：網絡中的節點具有相同的計算、傳輸和存儲能力。傳感器節點的通信范圍相同。

4) 發射功率自適應：在限定的功率范圍內，節點可以適度增加發射功率，提高接收節點的接收信噪比。

3.2.2 攻擊模型

假定每個干擾源配置全向天線，發送相同功率的信號，且干擾源位置是固定不變的。假設網絡中有n個干擾源，干擾源間的距離Dij滿足

其中，Ri和Rj分別為干擾源i和j的干擾半徑，ω是一個變量，ω越小，干擾源間的距離越大。為了實現有效干擾，ω一般為0.5。當ω小于0.5時，干擾區域重疊區域過大，進而使總的干擾區域面積減小，這與多干擾源協作的目的相違背，因此，本文暫不考慮此場景。當干擾源間距離大于Ri+Rj時，會使干擾區域不重疊，此時只需采用單干擾源定位算法即可估計干擾源的位置。

3.2.3 傳播模型

本文采用式(2)所示的自由空間傳播模型。

其中，PRX為節點接收功率，PTX為射頻端發射功率，GTX、GRX分別為天線的發射增益和接收增益，d為發射節點和接收節點之間的距離，λ表示傳送的無線電波的波長。

4 面向多跳無線網絡的多干擾源定位

4.1 基本設想

多干擾源定位無法基于圓形干擾區域的假設，利用網絡節點的物理屬性和位置信息建立與干擾源的聯系。為了準確定位多個區域重疊的干擾源，首先需要確定多個干擾源所在的大致區域，然后根據聚類分析方法定位干擾源。本文提出的多干擾源定位算法包括3個步驟：基于梯度下降法的分組投遞率谷點推定、基于梯度上升法的接收干擾強度峰點推定和聚類分析。首先，從多個不同的起始節點發起定位過程，沿分組投遞率下降方向逼近干擾區域中心；然后，采用功率自適應方法，沿接收干擾強度上升方向進一步細化干擾區域；最后，通過對停止節點的損失鄰居進行聚類計算得到干擾源所在位置。

注意到，在多干擾源定位場景中，選擇較多的起始節點可以提高定位精度，但也會帶來更大的計算和通信耗費。為此，本文在網絡節點中隨機選取個節點作為初始節點，其中，N為網絡中節點的數量。

4.2 算法設計

4.2.1 基于梯度下降法的分組投遞率谷點推定

在無線通信中，分組投遞率(PDR,packet delivery ratio)被定義為被正確接收的分組數目與已發送的分組數目的比值[9]。分組投遞率能反映網絡中節點的通信質量，通信質量越好，分組投遞率越高。由于干擾信號的強度隨著距離的增大呈下降趨勢，所以距離干擾源越遠的節點受到干擾信號的影響越小，從而會滿足所需的信噪比要求，使節點的PDR值增大。

多跳無線網絡部署區域各個位置的PDR值構成了一個PDR標量場。這個標量場中的各個谷點(局部極小值)則代表了距離干擾源距離較近的那些難以正常通信的節點。為了推定這些谷點的位置，本文采用了梯度下降方法。

初始節點確定后，通過比較節點與其鄰居節點的PDR值，路徑沿PDR值下降最快的方向逼近干擾源，直至達到PDR谷點。在干擾源作用下，位于干擾源附近區域的節點喪失了通信能力，其PDR值近似下降為0，因此，PDR谷點推定的路徑無法到達距離干擾源最近節點的位置。圖2展示了PDR梯度下降的過程，圖2中的箭頭表示梯度下降的方向。由于干擾區域中心的部分節點受干擾程度較強，無法完成分組的傳輸，因此，PDR谷點推定路徑只能到達距離干擾源較遠的節點，如圖2中矩形框所示。為了描述方便，將PDR下降過程停止的節點稱為PDR停止節點。

圖2 PDR谷點推定過程

4.2.2 基于梯度上升法的接收干擾強度峰點推定

為了重構節點間的通信，Kim等[23]提出了功率自適應調節技術。在干擾場景中，通過不斷增加發射節點的功率，提高接收節點的接收信噪比，可以部分恢復節點間的通信。由于干擾源的干擾功率隨著距離的增大而減弱，距離干擾源越近，節點收到的干擾功率越大，所以節點的RJSS值能反映節點與干擾源的距離信息。其中，RJSS是指被干擾節點收到的干擾源信號強度，可以采用文獻[24]所提方法進行測量和估計。

類似于PDR標量場，本文可以定義RJSS標量場，最靠近干擾源的節點是RJSS標量場的峰點(局部極大值)。在RJSS標量場中，通過增大PDR停止節點的發射功率，重建這些節點與比它們更靠近干擾源的鄰居間的通信，進而可以進一步逼近干擾源所在位置，直至達到RJSS峰點。為了描述方便，后文也將RJSS峰點稱為RJSS停止節點。

假設在功率自適應調節技術中，節點所能到達的最大功率值為Pmax=Pnode+Pthreshold，其中，Pnode為節點初始功率，Pthreshold為節點所能增加的最大功率。在最大發射功率范圍內，PDR停止節點以步長逐漸增大發射功率，直到該節點能與其鄰居節點j通信，且其RJSS小于該鄰居節點j的RJSS，則節點j替代PDR停止節點，重復上述操作。因此，路徑沿著RJSS增加最快的方向逼近干擾源。在最大發射功率增量范圍內，當節點的RJSS值達到局部最大時，結束路徑搜索。圖3展示了一個RJSS梯度上升過程。其中，實線箭頭表示PDR谷點推定的路徑，虛線箭頭表示RJSS峰點推定的路徑。初始節點確定后，路徑先后沿著PDR減小最快和RJSS增加最快的方向靠近干擾源，直到到達RJSS停止節點，如圖3矩形框所示，RJSS停止節點圍繞在各個干擾源附近。

圖3 RJSS峰點推定過程

圖4為RJSS信息交互的協議示意。其中，T為發送節點，R為接收節點。發送節點T的初始功率為MIN_POW，并以增量step不斷增加發送功率，直到能與鄰居節點R進行通信。T向鄰居節點R發送包含id、接收干擾強度RJSS_T和節點發送功率power的數據幀RJSS_INFO，R成功接收分組信息后，從信息中讀取發送節點的RJSS值，若R的接收干擾強度大于T的接收干擾強度，則R向T發送包含自身id和RJSS值的數據幀RJSS_INFO_ACK，否則R不發送任何信息。

圖4 RJSS信息交互

4.2.3 聚類分析

由上文分析可知，RJSS停止節點位于干擾源附近，但仍與干擾源存在一定距離。因此，必須對RJSS停止節點進行進一步處理，提高定位精度。

如圖5所示，在未受干擾狀態下，RJSS停止節點的鄰居節點分布在以其位置為中心，以其傳播距離為半徑的圓形區域內。當網絡受到干擾攻擊，RJSS停止節點以最大發送功率傳輸信息時，部分鄰居節點的接收信噪比增大，滿足通信要求，可以重建與RJSS停止節點的通信，如白色圓點所示。其余鄰居節點在最大發射功率下的接收信噪比仍小于信噪比閾值，無法與RJSS停止節點傳遞信息，如灰色圓點所示。

圖5 RJSS停止節點鄰居節點分類

注意到，該類無法與RJSS停止節點通信的鄰居節點分布在各個干擾源周圍，可以較好地反映干擾源的位置。因此，通過收集所有RJSS停止節點在最大發送功率下仍無法通信的鄰居節點信息，按照其物理位置進行分類，聚類數目作為干擾源的估計數量，聚類中心作為干擾源的估計位置。

聚類分析是一種將研究對象分為相對同質的群組的統計分析技術。聚類的方法主要包括兩大類：層次聚類和非層次聚類。K-means是一種以確定的聚類數量K和選定的初始聚類中心為前提，使各樣本到其判屬類別中心距離之和最小的非層次聚類。該算法處理效率較高，特別是當樣本分布呈類內團聚狀時，可以達到很好的效果。然而，在本文研究的多干擾源定位場景中，由于干擾源數目未知，無法確定類數，因此，K-means聚類無法直接解決丟失鄰居節點的分類問題。文獻[25]基于樣本的幾何結構，設計了一種新的評估聚類有效性的指標，在此基礎上提出了一種確定樣本最佳聚類數的方法。因此，樣本最佳聚類數確定后，即可對樣本進行K-means聚類分析。為此，本文采用文獻[25]所提出的聚類方法。

4.3 算法描述

面向多跳無線網絡的多干擾源定位算法偽代碼如算法1所示。步驟1)是節點初始化；步驟4)到步驟13)比較節點i與其鄰居節點的PDR值，若鄰居節點的最小PDR值小于該點的PDR值，則用該鄰居節點代替節點i，重復上述步驟，直至達到PDR谷點；步驟15)到步驟31)以step的增量持續增加PDR停止節點發射功率，在節點重建與鄰居節點的通信的基礎上比較各自的RJSS值；在步驟32)到步驟37)中，若節點在最大發射功率范圍內不能搜尋到RJSS值更大的鄰居節點，則以該點作為RJSS谷點或RJSS停止節點，記錄該節點的丟失鄰居節點，否則用RJSS值更大的鄰居節點代替PDR停止節點，重復步驟15)到步驟31)；步驟38)對所有停止節點的丟失鄰居節點進行聚類分析，估計干擾源數量和位置。

算法1基于面向多跳無線網絡的多干擾源定位算法

輸入N：網絡中節點總數；σ=1，δ=1；σ、δ為循環條件，滿足該條件時進入循環，否則，退出循環

輸出O_ES：估計干擾源坐標

4.4 算法分析

4.4.1 復雜度分析

假設節點間平均距離為d，網絡半徑為R。對于每個初始節點，PDR谷點推定和RJSS峰點推定過程的平均跳數是。假定一跳的通信開銷為c，初始節點數量為M，其平均鄰居數量為ns，則算法總的通信開銷為。從存儲角度來說，假定每個節點用4 byte存儲每個鄰居的PDR值，用4 byte存儲每個鄰居的RJSS值，則每個節點的存儲開銷為8ns，總的存儲開銷上界為8Nns，其中，N是節點總數。聚類分析的時間復雜度為O(knt)，其中，k為最佳聚類數量，n為輸入樣本數量，t為迭代次數。

4.4.2 收斂分析

從某個初始節點開始的PDR谷點推定過程會停止于此節點的網絡范圍內的PDR谷點，且由于算法采用某個時刻的測量結果，因此不會出現震蕩情況。同樣地，從PDR停止節點開始的RJSS峰點推定過程也同樣停止于其網絡范圍內的RJSS峰點，也不會出現震蕩情況。而K-means算法則隨著迭代次數到達而停止。為了保證定位效果的準確性，5.3節討論了定位算法對干擾源間的距離的要求。總之，算法會在估計的時間開銷、通信開銷和存儲開銷之內收斂，并給出多個干擾源的估計位置。

5 算法驗證與結果分析

本節設計了一系列模擬實驗，用于驗證所提出的多干擾源定位算法的性能。首先，介紹了實驗設定；然后，在多干擾場景下，對本文提出的多路徑搜索定位算法以及現有的幾種定位算法分別進行仿真比較；最后，探討參數對算法性能的影響，并進行分析討論。

5.1 實驗設定

本文采用Matlab搭建了一個多跳無線網絡模型。假設網絡部署在L×L的區域內，N個網絡節點均勻分布在N個l×l的網絡柵格中，M個干擾源隨機部署在網絡中。仿真中使用的主要參數如表1所示。

表1 實驗仿真參數

對比基準。本文選擇X射線多干擾源定位算法和質心定位算法與本文提出的算法進行定位性能比較，分析算法的優劣。

對比測度。本文采用平均絕對誤差(MAE,mean absolute error)來衡量算法的定位性能，定義如式(3)所示。

5.2 實驗結果與分析

5.2.1 性能驗證

首先實驗驗證了所提出的多干擾源定位算法的性能，并在相同場景中與現有的X射線多干擾定位算法和質心定位算法進行了性能比較。圖6為算法的仿真結果，其中，實線折線、虛線折線分別為PDR谷點推定路徑和RJSS峰點推定路徑。初始節點沿著上述2段路徑逼近干擾源，RJSS停止節點如圖6矩形框所示，由于節點的發射功率增量有限，RJSS停止節點與附近干擾源仍存在一定距離。對停止節點丟失的鄰居節點進行聚類分析，聚類中心作為估計干擾源位置，如菱形所示。

圖6 本文算法多干擾源定位算法定位結果

圖7為X射線多干擾源定位仿真結果。圖7中折線圍成的區域為干擾區域，三角形節點為骨架的分叉點，矩形方框為聚類中心，即為估計干擾源的位置。

圖8展示了3種定位算法在100次實驗后的平均絕對誤差值(MAE)。由圖8可知本文提出的定位算法MAE為5.201 2，定位精度最高。X射線定位和質心定位的平均絕對誤差分別為27.480 9和 103.207。其中，質心算法是以估計干擾源與各個干擾源間距離的平均作為平均絕對誤差。在X射線定位中，環境噪聲會造成干擾邊界的波動，從而影響區域骨架的形狀，導致定位性能的降低。質心定位算法沒有對干擾源數量進行正確估計和對干擾區域進行合理的劃分，因此，簡單地對被干擾節點進行坐標平均無法定位干擾源的位置。

圖7 X射線多干擾源定位

圖8 多干擾場景中的定位算法精度比較

5.2.2 參數影響

本節主要討論了干擾源間距和干擾源發射功率和干擾源位置對算法性能的影響。

在干擾源間距分別為{100,80,60,40}的4個干擾場景中，本文算法的平均定位誤差如圖9所示。隨著干擾源間距的減小，定位誤差增大。這是因為當干擾源間距減小時，RJSS停止節點間距減小，導致丟失鄰居節點交織分布，通過聚類分析得到的聚類數可能不等于實際干擾源數量，因此，定位的誤差增大。

圖9 干擾源間距對MAE的影響

圖10所示的在不同干擾源發射功率下算法的平均絕對誤差。由圖10可知，隨著干擾源發射功率的增大，算法的定位精度降低。這是因為干擾源功率的增大導致路徑搜索無法深入干擾區域內部，RJSS停止節點和丟失鄰居節點與相應干擾源的距離增大，聚類中心偏離干擾源位置。此外，干擾源發射功率的增大導致干擾重疊區域擴大，丟失鄰居節點交織分布，因此聚類分析不準確，定位誤差增大。

圖10 干擾源發射功率對MAE的影響

為了評估干擾源分布位置對算法定位的影響，在不同的干擾源分布位置，對面向多跳無線網路的多干擾源定位算法進行了仿真。圖11是干擾源分別位于區域中心、區域邊界和區域角落時算法平均絕對誤差。從圖11中可以看出，當干擾源分布在區域中心時，算法的定位誤差最小。這是因為干擾源的邊緣化分布導致RJSS停止節點的邊緣化和丟失鄰居節點的減少，從而影響聚類中心的計算。

圖11 干擾源位置對MAE的影響

5.3 討論

由實驗分析可知，面向多跳無線網絡的多干擾源定位算法的定位性能與聚類效果有關。聚類效果越好，則定位越精確。

聚類計算是通過對RJSS停止節點在最大發送功率下失去的鄰居節點按照其位置屬性進行分類，聚類中心為干擾源估算位置。如圖12(a)所示，當干擾源相距較遠，逼近各個干擾源的RJSS停止節點距離較大，丟失的鄰居節點呈類內團聚狀分布時，通過聚類分析可以準確地將其分類，聚類中心為相應干擾源的估計位置。當干擾源距離較近，RJSS停止節點距離較小，其丟失的鄰居節點混合分布在一起，如圖12(b)所示，通過聚類分析無法將其正確劃分為2類，導致干擾源數量估計錯誤。可見，各個干擾源間的距離影響聚類的效果。

假設在最大發射功率下，RJSS停止節點與其丟失的鄰居節點間的平均距離為d0，干擾源距離丟失鄰居節點的平均距離為dj_neighbor，則d0和dj_neighbor應滿足

其中，PT是節點初始發送功率，IN_MAX是節點發射功率最大增量，PJ是干擾源發射功率，SNR_threshold為接收信噪比閾值。則丟失鄰居節點與干擾源的距離dj_neighbor滿足

圖12 丟失鄰居節點分布

停止節點與附近干擾源的平均距離dj_node為

根據式(5)和式(6)，可得停止節點與附近干擾源的最大距離dj_node_max滿足

因此若要通過聚類分析，正確劃分丟失鄰居節點，使聚類數等于干擾源數目，聚類中心能反映干擾源的近似位置，則干擾源間的距離D應滿足

其中，dnode_mean為節點間平均距離。由式(7)和式(8)可知，干擾源發射功率、節點發射功率最大增量影響算法的精確度。當干擾源間距不變時，干擾源發射功率的增大或者節點發射功率最大增量的減小均會使RJSS停止節點與干擾源的最大距離增大，從而使算法定位性能降低。

6 結束語

為了實現對多跳無線網絡中多干擾源的精確定位，本文提出了面向多跳無線網絡的多干擾源定位算法。該算法根據分組投遞率和接收干擾信號強度與干擾源位置的關系，應用功率自適應技術，從多個起始節點出發，先后進行分組投遞率谷點推定和接收干擾信號強度峰點推定，最后通過對RJSS停止節點損失鄰居進行聚類分析，從而確定干擾源的數量和位置。為了驗證算法性能，使用Matlab搭建了模擬實驗環境并設計了一系列模擬實驗，通過與現有定位算法的定位性能對比，該算法可以實現多干擾源的精確定位。此外，實驗還研究了其他參數對算法的性能影響，結果表明當干擾源間距符合限定條件時，面向多跳無線網路的多干擾定位算法具有良好的定位結果。下一步將建立多干擾源定位的理論模型，并對定位算法性能進行定量分析。

[1]XU W,TRAPPE W,ZHANG,et al.The feasibility of launching and detecting jamming attacks in wireless networks[C]//MobiHoc05:Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc networking and Computing.2005:46-57.

[2]PELECHRINIS K,KOUFOGIANNAKIS C,KRISHNAMURTHY S.On the efficacy of frequency hopping in coping with jamming attacks in 802.11 networks[J].IEEE Transactions on Wireless Communications,2010,9(10):3258-3271.

[3]NOUBIR G,LIN G.Low-power DoS attacks in data wireless lans and countermeasures[J].ACM SIGMOBILE Mobile Computing and Comm,2003,7(3):29-30.

[4]XU W,TRAPPE W,ZHANG Y.Channel surfing:defending wireless sensor networks from interference[C]//IPSN’07:Proc Sixth Int’l Conf.Information Processing in Sensor Networks.2007:499-508.

[5]MA K,ZHANG Y,TRAPPE,W.Mobile network management and robust spatial retreats via network dynamics[C]//First Int’l Workshop Resource Provisioning and Management in sensor Networks.2005:242.

[6]PELECHRINIS K,KOUFOGIANNAKIS C,KRISHNAMURTHY S.On the efficacy of frequency hopping in coping with jamming attacks in 802.11 networks[J].IEEE Transactions on Wireless Communications,2010,9(10):3258-3271.

[7]NIKA A,ZHANG Z,ZHOU X,et al.Towards commoditized real-time spectrum monitoring[C]//Hotwireless’14.2014.

[8]YANG Y,JIN M,WU H.3D surface localization with terrainmodel[C]//IEEE Infocom 2014.2014:46-54.

[9]孫言強,王曉東,周興銘.無線網絡中的干擾攻擊[J].軟件學報,2012,23(5):1207-1221.SUN Y Q,WANG X D,ZHOU X M.Jamming attacks in wireless network[J].Journal of Software,2012,23(5):1207-1221.

[10]CHENG T Z,LI P,ZHU S C,et al.M-cluster and X-ray:two methods for multi-jammer localization in wireless sensor networks[J].Integrated Computer-Aided Engineering,2014,21:19-34.

[11]PELECHRINIS K,KOUTSOPOULOS I,BROUSTIS I,et al.Lightweight jammer localization in wireless networks:system design and implementation[C]//IEEE Global Telecommunication Conference,2009.

[12]WANG Q P,WEI X L,FAN J H,et al.A step further of PDR-based jammer localization through dynamic power adaption[C]//WiCOM 2015,2015:651-654.

[13]LIU H B,XU W Y,CHEN Y Y,et al.Localizing jammers in wireless networks[C]//PERCOM 2009.Washington:IEEE Computer Society,2009:1-6.

[14]LIU Z H,LIU H B,XU W Y,et al.Exploiting jamming-caused neighbor changes for jammer localization[J].IEEE Trans Parallel Distrib Syst,2012,23(3):547-555.

[15]LIU Z H,LIU H B,XU W Y,et al.An error-minimizing framework for localizing jammers in wireless networks[J].IEEE Trans Parallel Distrib Syst,2014:25(2):508-517.

[16]BLUMENTHAL J,GROSSMANN R,GOLATOWSKI F,et al.Weighted centroid localization in Zigbee-based sensor networks[C]// IEEE Int’l Symp on Intelligent Signal Processing Alcala de Henares.2007:1-6.

[17]SUN Y Q,WANG X D,ZHOU X M.Geometry-covering based localization for jamming attack in wireless sensor networks[J].Journal on Communications,2010,31(11):10-16.

[18]孫言強,王曉東,周興銘.無線傳感器網絡中基于幾何覆蓋的Jamming攻擊定位算法[J].通信學報,2010,31(11):10-16.SUN Y Q,WANG X D,ZHOU X M.Geometry-covering based localization for jamming attack in wireless sensor networks[J].Journal on Communications,2010,31(11):10-16.

[19]CHENG T Z,LI P,ZHU S C.An algorithm for jammer localization in wireless sensor networks[C]//IEEE International Conference on Advanced Information Networking and Applications.2012:724-731.

[20]XIONG K Q,DAVID T.Locating jamming attacks in malicious wireless sensor networks[C]//Performance Computing and Communications Conference(IPCCC),2012 IEEE 31st international.Austin,TX,2012:400-407.

[21]LIU H,LIU Z,CHEN Y,et al.Localizing multiple jamming attackers in wireless networks[C]//2011 31 International Conference on Distributed Computing Systems.Minneapolis,MN,USA,2011:517-528.

[22]VIKRAMADITYA R A,RAGHUVARA R,SHASHIMOHAN V,et al.A novel method for jammer localization in large scale sensor networks[C]//Wireless And Optical Communications Networks (WOCN),2010 Seventh International Conference.2010:6-8.

[23]KIM Y,MOKAYA F,CHEN E,et al.All your jammers belong to us—localization of wireless sensors under jamming attack[C]//IEEE International Conference on Communications (ICC).2012:949-954.

[24]LIU Z H,LIU H B,XU W Y,et al.Error minimizing jammer localization through smart estimation of ambient noise[C]//MASS 2012.

[25]周世兵,徐振源,唐旭清.K-means算法最佳聚類數確定方法[J].計算機應用,2010,30(8):1995-1998.ZHOU S B,XU Z Y,TANG X Q.Method for determining optimal number of clusters in K-means clustering algorithm[J].Journal of Computer Applications,2010,30(8):1995-1998.

王棋萍（1990-），女，湖南湘鄉人，解放軍理工大學碩士生，主要研究方向為無線網絡安全。

魏祥麟（1985-），男，安徽碭山人，南京電訊技術研究所工程師，主要研究方向為數據中心網絡、無線網絡安全和網絡異常檢測。

范建華（1971-），男，安徽歙縣人，南京電訊技術研究所研究員，主要研究方向為無線網絡安全和認知無線電網絡。

王統祥（1990-），男，山東臨沂人，解放軍理工大學博士生，主要研究方向為無線網絡安全。

胡飛（1987-），男，江蘇淮安人，解放軍理工大學碩士生，主要研究方向為無線網絡安全。

Multi-hop wireless network oriented multiple jammers localization algorithm

WANG Qi-ping1,WEI Xiang-lin2,FAN Jian-hua2,WANG Tong-xiang1,HU Fei1
(1.College of Communications Engineering,PLA University of Science and Technology,Nanjing 210007,China;2.Nanjing Telecommunication Technology Research Institute,Nanjing 210007,China)

A multiple jammer localization algorithm in multi-hop wireless networks was proposed.The proposed algorithm contained three steps,packet delivery ratio (PDR) valley point determination based on gradient descent algorithm,received jamming signal strength (RJSS) peak point determination based on gradient ascent algorithm and cluster analysis.Firstly,the algorithm started from a few initial nodes and moved along the gradient descent direction ofPDRto approach the jammers until reaches thePDRvalley point.Then,the algorithm moved toward the jammers using power adaptation technique based onRJSSgradient ascent process until it reached theRJSSpeak point.Finally,through applying cluster analysis on the neighbour nodes which fail to communicate withRJSSpeak points,the number and positions of the jammers can be estimated.Experimental results have verified that the proposed algorithm can improve the accuracy of localization compared with existed localization algorithms.Furthermore,the performance of the proposed algorithm is prominent when the distance of jammers accords with constraint condition.

multi-hop wireless network,jamming attack,jammer localization,cluster

s:The National Key Basic Research and Development Program of China(973 Program) (No.2012CB315806),The National Natural Science Foundation of China(No.61402521,No.61070173),The Natural Science Foundation of Jiangsu Province(No.BK20140068,No.BK20140070,No.BK20150201)

TP393

A

10.11959/j.issn.1000-436x.2016284

2015-10-20；

2016-09-19

魏祥麟，weixianglin@163.con

國家重點基礎研究發展計劃(“973”計劃) 基金資助項目(No.2012CB315806)；國家自然科學基金資助項目(No.61402521,No.61070173)；江蘇省自然科學基金資助項目(No.BK20140068,No.BK20140070,No.BK20150201)