侯當(dāng)云，呂偉杰

（天津大學(xué)電氣與自動(dòng)化工程學(xué)院，天津300072）

基于偏差迭代的干擾源定位算法

侯當(dāng)云，呂偉杰*

（天津大學(xué)電氣與自動(dòng)化工程學(xué)院，天津300072）

針對(duì)無線傳感器網(wǎng)絡(luò)易受干擾攻擊而導(dǎo)致網(wǎng)絡(luò)通信受阻甚至癱瘓等問題，為確定干擾源位置進(jìn)而消除干擾、保障網(wǎng)絡(luò)正常通信，提出了偏差迭代定位算法。在確定初始估計(jì)位置后，通過參與定位的三個(gè)候選節(jié)點(diǎn)的位置信息即可求出干擾源估計(jì)位置與實(shí)際位置的大致偏差，對(duì)不滿足精度要求的初始估計(jì)位置進(jìn)行迭代直到偏差小于規(guī)定閾值為止。該算法不依賴網(wǎng)絡(luò)本身或者外部設(shè)備等復(fù)雜的硬件設(shè)施和技術(shù)支持，對(duì)現(xiàn)存方法中存在的定位誤差大、網(wǎng)絡(luò)耗能高等問題進(jìn)行了改善。仿真實(shí)驗(yàn)證明，該算法在不同網(wǎng)絡(luò)環(huán)境下定位效果均優(yōu)于現(xiàn)存算法。

無線傳感器網(wǎng)絡(luò)；定位；偏差迭代；閾值；仿真

EEACC：7230doi：10.3969/j.issn.1004-1699.2015.12.015

無線傳感器網(wǎng)絡(luò)WSNs（Wireless Senor Networks）是由部署在監(jiān)測區(qū)域內(nèi)大量的廉價(jià)微型傳感器，通過無線通信方式形成的一個(gè)多跳的自組織網(wǎng)絡(luò)［1］。其巨大的發(fā)展前景和應(yīng)用價(jià)值已經(jīng)引起軍事部門、工業(yè)界、學(xué)術(shù)界的廣泛關(guān)注，同時(shí)，由于無線媒介的開放性、廣播性等本質(zhì)特征導(dǎo)致網(wǎng)絡(luò)可以輕易的受到非法竊聽、篡改消息和拒絕服務(wù)等許多安全威脅［2］，因此保證網(wǎng)絡(luò)通信的安全性和可靠性變得日益重要。在無線傳感器網(wǎng)絡(luò)受到的各種威脅當(dāng)中，干擾攻擊（jamming）對(duì)網(wǎng)絡(luò)的危害最大，干擾攻擊的發(fā)起者稱之為干擾源（jammer）。干擾攻擊是一種通過占用網(wǎng)絡(luò)節(jié)點(diǎn)通信信道，使其不能進(jìn)行正常數(shù)據(jù)轉(zhuǎn)發(fā)的拒絕服務(wù)攻擊，敵人可利用無線網(wǎng)絡(luò)的開放性等本質(zhì)特征，輕易的在網(wǎng)絡(luò)中設(shè)置干擾。為應(yīng)對(duì)干擾攻擊，傳統(tǒng)方式通過采用直接序列擴(kuò)頻DSSS（Direct Sequence Spread Spectrum）和跳頻序列擴(kuò)頻FHSS（Frequency Hopping Spread Spectrum）［3］等方法來增強(qiáng)網(wǎng)絡(luò)防御能力從而抵抗干擾對(duì)網(wǎng)絡(luò)造成的不利影響。但考慮到基于802.11的無線局域網(wǎng)、自組織網(wǎng)絡(luò)以及基于802.15.4的無線分布式傳感器網(wǎng)絡(luò)在頻寬、能耗以及計(jì)算能力方面的受限性［4-6］，并且對(duì)物理層的設(shè)計(jì)不僅復(fù)雜而且需要很強(qiáng)的技術(shù)支持，使得這些傳統(tǒng)方法在實(shí)際應(yīng)用中并不常用。

為了保證無線網(wǎng)絡(luò)通信的可靠性，消除干擾帶來的不利影響，找到干擾源所在的位置變得尤為重要。干擾源位置一旦確定，就可以通過對(duì)其進(jìn)行徹底銷毀或者通過設(shè)計(jì)路由協(xié)議避開被干擾區(qū)域從而完全消除干擾攻擊對(duì)無線傳感器網(wǎng)絡(luò)的影響［7］。

1　相關(guān)工作

為了消除干擾對(duì)網(wǎng)絡(luò)的攻擊，我們首先需要了解各種網(wǎng)絡(luò)攻擊模型［8］。其次是網(wǎng)絡(luò)對(duì)攻擊的檢測問題。本文假設(shè)是在固定攻擊模型下，網(wǎng)絡(luò)可以準(zhǔn)確檢測到干擾激活后進(jìn)行的，因此不再考慮干擾的檢測階段。最后的關(guān)鍵問題是干擾源定位，定位問題是無線傳感器網(wǎng)絡(luò)中一個(gè)熱點(diǎn)問題。

WSNs定位方法一般分為：基于測距（rangebased）的定位和測距無關(guān)（range-free）的定位?；跍y距的定位算法主要是通過測量和傳輸節(jié)點(diǎn)俘獲的一些物理屬性，如信號(hào)強(qiáng)度［9］、到達(dá)時(shí)間差等信息進(jìn)行定位。其中具有代表性的是chen等人［10］提出的基于接收信號(hào)強(qiáng)度的定位算法，通過測量節(jié)點(diǎn)接收信號(hào)強(qiáng)度RSS（Received Signal Strength）值，利用RSS與距離之間的關(guān)系來估計(jì)干擾源位置。但是在Jamming攻擊環(huán)境下，被干擾區(qū)域的通信已被全部或者部分損壞，并且網(wǎng)絡(luò)中存在的多路徑衰退效應(yīng)使得測量和傳輸準(zhǔn)確的RSS值難度大大提高，因此基于測距的定位在實(shí)際環(huán)境中定位效果差不適宜于干擾定位。

測距無關(guān)定位算法則依靠盡可能少的信息，如已知的部分節(jié)點(diǎn)位置信息、節(jié)點(diǎn)轉(zhuǎn)發(fā)跳數(shù)等進(jìn)行定位，其中經(jīng)典算法包括純質(zhì)心定位算法CL（Centriole Localization）及考慮權(quán)重的質(zhì)心定位算法［11］WCL（Weight Centriole Localization），liu等人［12］提出的虛擬力迭代定位法。針對(duì)已有算法定位準(zhǔn)確性不足，孫言強(qiáng)等人［13］提出了基于幾何覆蓋的干擾攻擊定位算法GCL（Geometry Covering based Localization），找出一個(gè)最小包容圓使其能覆蓋所有的邊界節(jié)點(diǎn)，則圓心處作為估計(jì)干擾源位置。由于幾何算法不依賴網(wǎng)絡(luò)本身或其他設(shè)備等復(fù)雜的測距知識(shí)、算法簡單且定位精度高，因此開始成為研究定位問題的主要方向。

結(jié)合現(xiàn)有算法的不足之處，本文提出的算法無需任何測距上的先驗(yàn)知識(shí)和硬件設(shè)施，把定位中的優(yōu)化問題抽象成簡單的數(shù)學(xué)模型，只需參與定位的部分節(jié)點(diǎn)自身的位置信息即可求出干擾估計(jì)位置和實(shí)際位置的大致偏差，簡單可行，同時(shí)有效的減少網(wǎng)絡(luò)能量的消耗。

2　網(wǎng)絡(luò)模型

本節(jié)主要介紹參與干擾源定位的網(wǎng)絡(luò)模型和攻擊模型。

2.1網(wǎng)絡(luò)模型

無線傳感器網(wǎng)絡(luò)廣泛應(yīng)用于軍用、民用，等大規(guī)模、大范圍場合，為節(jié)約成本提高安放效率傳感器節(jié)點(diǎn)由飛機(jī)高空隨機(jī)撒播。在一定區(qū)域撒播下大量節(jié)點(diǎn)后，節(jié)點(diǎn)會(huì)通過自組織的方式相互連通構(gòu)成網(wǎng)絡(luò)。為了表征無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的狀態(tài)，對(duì)其進(jìn)行如下假設(shè)：①節(jié)點(diǎn)的固定性，網(wǎng)絡(luò)一旦形成，節(jié)點(diǎn)位置固定不變；②位置感知能力，網(wǎng)絡(luò)形成后，節(jié)點(diǎn)可以準(zhǔn)確感知自己所在的位置；③檢測性，可以準(zhǔn)確感知到干擾的存在，因此不再考慮干擾的檢測階段。

2.2攻擊模型

恒定干擾通過持續(xù)的發(fā)送無線電信號(hào)來擾亂正常網(wǎng)絡(luò)的通信信道，本文主要針對(duì)恒定干擾對(duì)網(wǎng)絡(luò)的影響進(jìn)行研究。對(duì)恒定干擾我們做如下假設(shè)：①位置固定，干擾一旦激活，位置固定不變；②傳播模型，以全方位球形輻射模式向網(wǎng)絡(luò)持續(xù)發(fā)送恒定功率的無線電信號(hào)，干擾半徑r的大小代表干擾功率的大小。

干擾一旦激活，如圖1所示，網(wǎng)絡(luò)節(jié)點(diǎn)狀態(tài)即被劃分為三種，處在干擾范圍內(nèi)的節(jié)點(diǎn)成為被干擾節(jié)點(diǎn)，失去全部通信能力成為網(wǎng)絡(luò)的通信“黑洞”；遠(yuǎn)離干擾范圍的節(jié)點(diǎn)為正常節(jié)點(diǎn)，不受干擾影響保持正常通信；其中處于干擾范圍邊緣的點(diǎn)成為邊界節(jié)點(diǎn)，這類節(jié)點(diǎn)通信并沒有被完全破壞，保持部分通信能力，可以向網(wǎng)絡(luò)外部傳輸其俘獲的各種信息，成為定位干擾源的關(guān)鍵節(jié)點(diǎn)。

3　本文算法分析

3.1問題分析

干擾激活后可利用網(wǎng)絡(luò)拓?fù)渥兓纬傻倪吔绻?jié)點(diǎn)來進(jìn)行干擾源的定位，這是因?yàn)檫吔绻?jié)點(diǎn)處于干擾范圍的邊緣使得邊界節(jié)點(diǎn)的通信能力并沒有被完全破壞，可向外部傳輸其準(zhǔn)確的位置信息。

我們利用質(zhì)心法求出干擾源初始估計(jì)位置，確定初始估計(jì)位置后，干擾源估計(jì)位置與實(shí)際位置之間可能存在偏差，因此利用偏差迭代定位算法確定干擾源的最終估計(jì)位置。我們?cè)O(shè)定偏差閾值為0.001，即橫縱坐標(biāo)的偏差均小于0.001，利用最小二乘法求出干擾源估計(jì)位置與實(shí)際位置的大致偏差，若精度不滿足要求，則將校正后的坐標(biāo)代替估計(jì)坐標(biāo)，進(jìn)行下一步的矯正，直到偏差小于規(guī)定閾值迭代結(jié)束。得到最終干擾源估計(jì)位置，此時(shí)偏差滿足閾值要求，最接近干擾源的真實(shí)位置。

3.2偏差迭代定位算法

設(shè)干擾源J的實(shí)際位置是（x0,y0），初始估計(jì)位置（x?0,y?0），邊界節(jié)點(diǎn)位置為（xi,yi）?？蓪⒏蓴_源初始估計(jì)位置與實(shí)際位置偏移表示為（Δx0,Δy0），J到邊界節(jié)點(diǎn)的距離為ri，為了計(jì)算J的位置，定義了一個(gè)最大似然估計(jì)函數(shù)f，并選擇這個(gè)函數(shù)的一個(gè)局部最小值，設(shè)f=ri-r?i。

式中：實(shí)際距離

估計(jì)距離

如上所述，J的真實(shí)位置可由近似分量和增量兩部分表示：

因此有：

按泰勒級(jí)數(shù)對(duì)式（4）右邊函數(shù)展開得：

為消除非線性，展開式（5）中消去了一階偏導(dǎo)數(shù)之后的各項(xiàng)，偏導(dǎo)數(shù)計(jì)算為：

把式（3）～（6）帶入式（2）中得：

為簡化公式（7），引入下述變量：

這樣式（7）可表示為：

在式（9）中等號(hào)左邊為已知量，右邊為未知量，設(shè)：

式（9）可表示為：

由此，得出：

因?yàn)樵谧畲笏迫还烙?jì)函數(shù)線性化過程中存在誤差，解得的偏移向量為干擾源估計(jì)位置與實(shí)際位置的大概偏差。參與最后求解的方程組中有三個(gè)未知量，因此至少需要三個(gè)方程組即三個(gè)邊界節(jié)點(diǎn)的位置信息，可在網(wǎng)絡(luò)拓?fù)渥兓蟮倪吔绻?jié)點(diǎn)中選擇。

4　算法性能分析

我們使用仿真工具搭建一個(gè)100 m×100 m仿真平臺(tái)，在該區(qū)域隨機(jī)撒播節(jié)點(diǎn)。節(jié)點(diǎn)通信半徑設(shè)定為20 m，每個(gè)節(jié)點(diǎn)裝有全向天線可以與自己通信范圍內(nèi)的所有鄰居節(jié)點(diǎn)進(jìn)行通信。將干擾放置在仿真平臺(tái)的中心。每次隨機(jī)撒播完節(jié)點(diǎn)在特定的干擾場景下調(diào)用這四種定位算法，把本文提出的算法和已有算法CL，WCL以及GCL進(jìn)行比較，在100次隨機(jī)試驗(yàn)中評(píng)估算法的定位效果。

4.1評(píng)價(jià)指標(biāo)

干擾源估計(jì)位置和真實(shí)位置之間的歐氏距離定義為單次定位誤差，如式（12）所示。把單次定位誤差相加求平均，即為平均定位誤差，如式（13）所示。

單次定位誤差由于采樣少而存在隨機(jī)性，平均定位誤差更能代表算法的優(yōu)劣。為了保證評(píng)估效果的準(zhǔn)確性，我們把平均定位誤差指標(biāo)作為評(píng)價(jià)的主要指標(biāo)。這也是在現(xiàn)存定位方法中首次提出采用平均定位誤差作為評(píng)價(jià)指標(biāo)。

4.2實(shí)驗(yàn)分析

4.2.1干擾源功率對(duì)定位精度的影響

節(jié)點(diǎn)密度相同，調(diào)整干擾功率：在100 m×100 m區(qū)域內(nèi)隨機(jī)撒播200個(gè)節(jié)點(diǎn)（100 m×100 m，N= 200），使干擾半徑r分別為20 m、30 m和40 m。每種算法隨機(jī)運(yùn)行100次，仿真結(jié)果如圖2所示。

圖2　R干擾功率對(duì)算法精度的影響（N=200）

在功率變化的三種情況下CL定位算法定位效果最差，本文提出的定位效果最好。當(dāng)干擾功率增大時(shí)，四種算法的平均定位誤差都有減小的趨勢(shì)，說明四種算法的定位精度都與干擾功率大小有關(guān)，這是因?yàn)楫?dāng)干擾功率增大時(shí)，被干擾節(jié)點(diǎn)和邊界節(jié)點(diǎn)的數(shù)目也相應(yīng)增加，參與定位的候選節(jié)點(diǎn)數(shù)增加，從而在一定程度上使定位誤差減小。通過仿真圖的曲線波動(dòng)情況可以看出，在不同的干擾功率情況下本文提出的算法曲線平穩(wěn)、波動(dòng)最小，因而定位精度最高且適應(yīng)性最強(qiáng)，這是傳統(tǒng)單次定位誤差所無法評(píng)估的。

4.2.2節(jié)點(diǎn)密度對(duì)定位精度的影響

干擾功率一定，調(diào)整節(jié)點(diǎn)的密度：在100×100區(qū)域隨機(jī)撒播100，150，200，250個(gè)節(jié)點(diǎn)，干擾激活后干擾半徑保持30 m不變。每種情況下四種算法隨機(jī)運(yùn)行100次，仿真結(jié)果如圖3和圖2中（2）所示。在不同的節(jié)點(diǎn)密度下，本文提出的算法定位精度仍然最好。并且隨著節(jié)點(diǎn)的密度增大，四種算法的定位誤差都有減小的趨勢(shì)，這是由于當(dāng)節(jié)點(diǎn)密度增大時(shí)，被干擾節(jié)點(diǎn)和邊界節(jié)點(diǎn)的數(shù)目增加并且參與定位的候選節(jié)點(diǎn)分布區(qū)域更趨近于圓，從而使四種算法的定位精度都有所提升。由此可以看出節(jié)點(diǎn)密度越大定位誤差越小，反之則定位誤差越大。從四種算法的平均定位誤差曲線圖可以看出本文算法曲線平穩(wěn)震蕩小，表明隨機(jī)定位效果好。

圖3　R節(jié)點(diǎn)密度對(duì)算法精度的影響（r=30 m）

4.3機(jī)理分析

在實(shí)際網(wǎng)絡(luò)環(huán)境中，當(dāng)干擾源位置處于網(wǎng)絡(luò)邊緣，或者節(jié)點(diǎn)隨機(jī)撒播以及傳播過程中功率損耗不同造成的各方向上邊界節(jié)點(diǎn)密度不均勻時(shí)，形成的邊界節(jié)點(diǎn)將不再包圍干擾源或者造成不同方向邊界節(jié)點(diǎn)分布密度差異很大，因而CL、WCL和GCL的定位誤差都將大大增加。但是本文提出的算法在幾何定位的基礎(chǔ)上進(jìn)行優(yōu)化，只要確定的邊界節(jié)點(diǎn)的絕對(duì)位置信息即可縮小定位誤差，而對(duì)整體的邊界節(jié)點(diǎn)相對(duì)位置信息無任何附加要求，因而即使干擾源位置邊緣化或邊界節(jié)點(diǎn)密度不均勻時(shí)，依然可以達(dá)到良好定位效果。

5　結(jié)語

由于無線傳感器網(wǎng)絡(luò)的本質(zhì)特征導(dǎo)致網(wǎng)絡(luò)易受干擾攻擊而導(dǎo)致通信失敗或網(wǎng)絡(luò)癱瘓，為消除干擾保證網(wǎng)絡(luò)正常通信，我們對(duì)干擾源定位問題進(jìn)行了進(jìn)一步的研究，在固定網(wǎng)絡(luò)模型和干擾模型的基礎(chǔ)上，把定位問題轉(zhuǎn)化成簡單的數(shù)學(xué)優(yōu)化問題。通過仿真驗(yàn)證，本文提出的算法比現(xiàn)存幾種算法定位精度顯著提高。但是對(duì)于無線傳感器網(wǎng)絡(luò)來說，其網(wǎng)絡(luò)模型和干擾攻擊模型是多種多樣的，在以后的研究中，我們可以對(duì)移動(dòng)的干擾模型和聯(lián)合干擾模型的定位問題進(jìn)行進(jìn)一步的探索。

［1］趙仕俊，唐懿芳.無線傳感器網(wǎng)絡(luò)［M］.北京：科學(xué)出版社，2013：1-3.

［2］畢俊蕾，李致遠(yuǎn).無線傳感器網(wǎng)絡(luò)安全路由協(xié)議研究［J］.計(jì)算機(jī)安全，2009（11）：35-38.

［3］Shiu Y S，Chang S Y，Wu H C，et al.Physical Layer Security in Wireless Networks：A Tutorial［J］.Wireless Communications，IEEE，2011，18（2）：66-74.

［4］Ian F Akyildiz，Su Weilian，Yogesh Sankarasubramaniam，et al.A Survey on Sensor Networks［J］.IEEE Communications Magazine，2002，40（8）：102-114.

［5］Zhou Yun，F(xiàn)ang Yuguang，Zhang Yanchao.Securing Wireless Sensor Networks：A Survey［J］.Communications Surveys and Tutorials，IEEE，2008，10（3）：6-28.

［6］Loay Abusalah，Ashfaq Khokhar，Mohsen Guizani.A Survey of Secure Mobile Ad Hoc Routing Protocols［J］.Communications Surveys and Tutorials，IEEE，2008，10（4）：78-93.

［7］聶云峰，王長勝，陳崇毅.一種空間查詢高效的無線傳感網(wǎng)絡(luò)路由協(xié)議［J］.傳感技術(shù)學(xué)報(bào)，2015，28（5）：744-751.

［8］Konstantinos Pelechrinis，Marios Iliofotou，Srikanth V Krishnamurthy.Denial of Service Attacks in Wireless Networks：The Case of Jammers［J］.Communications Surveys and Tutorials，IEEE，2011，13（2）：245-257.

［9］楊文鉑，邢鵬康，劉彥華.一種基于自適應(yīng)RSSI測距模型的無線傳感器網(wǎng)絡(luò)定位方法［J］.傳感技術(shù)學(xué)報(bào)，2015，28（1）：137-141.

［10］Chen Yingying，John-Austen Francisco，Wade Trappe.A Practical Approach To Landmark Deployment for Indoor Localization［C］//Sensor and Ad Hoc Communications and Networks，2006. SECON'06.2006 3rd Annual IEEE Communications Society on. IEEE，2006，1：365-373.

［11］Blumenthal J，Grossmann R，Golatowski F，et al.Weighted Centroid Localization in Zigbee-Based Sensor Networks［J］.Intelligent Signal Processing，2007.WISP 2007.IEEE International Symposium on.IEEE，2007：1-6.

［12］Liu Zhenhua，Xu Wenyuan，Chen Yingying，et al.Localizing Jammers in Wireless Networks［C］//Pervasive Computing and Communications，2009.PerCom 2009.IEEE International Conference on. IEEE，2009：1-6.

［13］孫言強(qiáng)，王曉東，周興銘.無線傳感器網(wǎng)絡(luò)中基于幾何覆蓋的Jamming攻擊定位算法［J］.通信學(xué)報(bào)，2010，31（11）：10-16.

Based on the Deviation of Iterative Algorithm in Jammer Localization

HOU Dangyun，Lü Weijie*
（School of Electrical Engineering and Automation，Tianjin University，Tianjin 3000072，China）

Wireless sensor networks communication is susceptible to jamming attacks，which would make the network communication blocked or even palsied.In order to localize the position of the jammer and then eliminate it to guarantee the normal communication，we develop a novel algorithm，deviation of iterative localization.After determining the initial estimate position，we calculate the deviation between the estimate position and the actual position through the position of three candidate nodes.If the deviation did not meet the accuracy requirement，iterated until it less than a specified threshold.The algorithm does not depend on the network complex hardware facilities or external device support.The problems of present methods about lager positioning error，higher energy consumption and the like have been improved.Simulation shows that our algorithm under the different network environments outperforms existing algorithms.

wireless senor networks；localization；deviation of iterative；threshold；simulation

侯當(dāng)云（1991-）河北省邯鄲市人，天津大學(xué)碩士研究生，主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)安全問題，hdy2013y@163.com；

呂偉杰（1975-）天津大學(xué)副教授，碩士生導(dǎo)師，主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)、圖像處理、現(xiàn)場總線等，weijielv@tju. edu.cn。

TN915.08

A

1004-1699（2015）12-1818-05

2015-06-30修改日期：2015-09-11