一種基于殘差分析過濾的安全定位算法

滕 云，劉宏立，徐 琨

(湖南大學(xué) 電氣與信息工程學(xué)院，長沙 410082)

一種基于殘差分析過濾的安全定位算法

滕 云，劉宏立，徐 琨

(湖南大學(xué) 電氣與信息工程學(xué)院，長沙 410082)

在無線傳感網(wǎng)絡(luò)節(jié)點(diǎn)定位中，惡意錨節(jié)點(diǎn)的出現(xiàn)會降低網(wǎng)絡(luò)定位性能，為了解決這個問題，根據(jù)節(jié)點(diǎn)定位過程中的惡意錨節(jié)點(diǎn)攻擊特性和定位計算中的殘差問題，提出一種基于殘差分析和過濾的無線傳感網(wǎng)絡(luò)安全定位算法。建立了基于距離的安全定位模型，對網(wǎng)絡(luò)定位中的殘差問題進(jìn)行了分析，并且通過殘差特性過濾掉網(wǎng)絡(luò)中惡意錨節(jié)點(diǎn)，利用剩余錨節(jié)點(diǎn)信息和梯度下降法對未知節(jié)點(diǎn)實現(xiàn)高精度定位。仿真表明，此算法在多個性能指標(biāo)下都能取得相對較高的定位精度，并且在高強(qiáng)度的惡意攻擊下也能保持較高的定位性能。此算法不但能有效地抵御惡意攻擊對節(jié)點(diǎn)定位的破壞，還顯著地加強(qiáng)了網(wǎng)絡(luò)的定位安全性。

無線傳感網(wǎng)絡(luò)；安全定位；梯度下降法；殘差分析；過濾

0 引 言

無線傳感網(wǎng)絡(luò)(wireless sensor network，WSN)是由大量成本低廉，存儲空間、計算能量有限的傳感節(jié)點(diǎn)組成。他們能在短時間進(jìn)行數(shù)據(jù)通信，具有功耗低，組網(wǎng)快捷的特點(diǎn)而被廣泛運(yùn)用到民用和軍事領(lǐng)域，如森林防火、戰(zhàn)場監(jiān)控[1]、環(huán)境監(jiān)測[2]和洪水監(jiān)控等。傳感器節(jié)點(diǎn)的位置對于無線傳感網(wǎng)絡(luò)十分重要，因為節(jié)點(diǎn)定位對于大多數(shù)基于位置的路由協(xié)議和應(yīng)用都起著關(guān)鍵的作用，所以研究人員對定位技術(shù)已經(jīng)產(chǎn)生了廣泛的興趣并針對不同方向進(jìn)行了研究。如WSN的定位效率[3]和定位精度[4]等問題。

基于距離[5](range-based，RB)的定位算法中，定位節(jié)點(diǎn)使用不同鄰居節(jié)點(diǎn)的距離信息估計它們的位置，然后通過三邊測量法、三角測量法或者最大似然估計法[6]進(jìn)行定位。但是，由于WSN的特點(diǎn)原因，無線傳感網(wǎng)絡(luò)節(jié)點(diǎn)經(jīng)常部署在無人監(jiān)控的區(qū)域中，甚至是惡意危險的環(huán)境中，使其很容易受到攻擊者的各種惡意攻擊[7]，這些攻擊往往通過信號干擾或者捕獲網(wǎng)絡(luò)中的錨節(jié)點(diǎn)來對定位過程進(jìn)行破壞，使網(wǎng)絡(luò)中的節(jié)點(diǎn)不能夠準(zhǔn)確地定位，從而導(dǎo)致整個網(wǎng)絡(luò)無法正常工作。因此，安全定位對WSN有著重要作用。

針對在惡意環(huán)境下的無線傳感網(wǎng)絡(luò)安全定位問題，研究人員已經(jīng)提出了多種安全定位策略[8]。文獻(xiàn)[9]通過分析多徑效應(yīng)和外部干擾對接收信號強(qiáng)度指示(received signal strength indication, RSSI)的影響，提出采用頻率分割集來克服多徑效應(yīng)對RSSI的影響，通過改善RSSI的測距精度來提高定位的精度。文獻(xiàn)[10]提出了一種基于到達(dá)時間差(time difference of arrival, TDoA)的2步法安全定位算法，通過錨節(jié)點(diǎn)之間的檢測和信譽(yù)分級找出并過濾惡意錨節(jié)點(diǎn)，最終實現(xiàn)了高精度的定位結(jié)果。文獻(xiàn)[11]提出了一種名為Beta信譽(yù)系統(tǒng)(Beta reputation system)的安全定位算法，使用信譽(yù)系統(tǒng)篩選錨節(jié)點(diǎn)，并利用加權(quán)泰勒展開式的最小二乘算法來獲得最終的定位位置，該算法有效地減輕了惡意錨節(jié)點(diǎn)對網(wǎng)絡(luò)節(jié)點(diǎn)定位的影響。但是利用信譽(yù)機(jī)制篩選錨節(jié)點(diǎn)會給網(wǎng)絡(luò)節(jié)點(diǎn)帶來很大的能量消耗，影響了網(wǎng)絡(luò)運(yùn)行效率。文獻(xiàn)[12]針對WSN定位中遇到的獨(dú)立攻擊，利用最速下降法和惡意錨節(jié)點(diǎn)檢測技術(shù)選出最優(yōu)錨節(jié)點(diǎn)數(shù)據(jù)，并結(jié)合牛頓迭代法實現(xiàn)了快速高精度的三維安全定位。

本文提出的安全定位算法是一種過濾算法，結(jié)合梯度下降法和殘差分析過濾的方式，利用殘差特性過濾掉網(wǎng)絡(luò)中的惡意錨節(jié)點(diǎn)，對未知節(jié)點(diǎn)進(jìn)行高精度迭代定位。本文算法與文獻(xiàn)[13]提出的結(jié)合梯度下降法和異常檢測方式的算法有相似之處。但由于過濾算法方式的區(qū)別使得在定位精度上有一定區(qū)別，仿真結(jié)果表明本文所提出的算法能得到更好的定位精度。

1 安全定位模型

在基于測距的定位算法中，未知節(jié)點(diǎn)需要通過通信方式收集鄰居錨節(jié)點(diǎn)的距離和位置信息集{(x,y),d}，然后通過三角測量或者三邊測量來計算未知節(jié)點(diǎn)的位置。

d2(x,y)=(x-xi)2+(y-yi)2

(1)

當(dāng)n≥3時，根據(jù)公式(1)列出這n個方程，利用最小二乘法(least square, LS)就能得到未知節(jié)點(diǎn)M的準(zhǔn)確值。

(2)

(3)

(4)

可以推得

‖Li-L‖

那么，定義目標(biāo)函數(shù)

(5)

因此，定位問題就等價于尋找使目標(biāo)函數(shù)λ(L)達(dá)到最小值的點(diǎn)L0。

2 安全定位算法

2.1 梯度下降法

基于上述安全定位模型分析，目標(biāo)函數(shù)λ(L)是一個凸函數(shù)，因此可以用梯度下降法對(5)式求解非線性最小值點(diǎn)。首先，隨機(jī)給出估計值的初始值L(0)。在第k步的迭代計算中，根據(jù)當(dāng)前估計值L(k-1)的值，估計第k步的值。求解第k次的梯度向量

(6)

(6)式中：▽(·)表示位置值L的導(dǎo)數(shù)。于是可以得到第k步的刷新估計值

(7)

(7)式中：γ(k)是第k次迭代的步長；(g(k))/(|g(k)|)表示梯度負(fù)方向的單位向量，即梯度下降第k次迭代的搜索方向。那么根據(jù)目標(biāo)函數(shù)(5)求得的第k次搜索方向為

(8)

(8)式中：L為第(k-1)次迭代得到的估計坐標(biāo)值。每次迭代都會得出一個新的估計值，這個估計值都會更接近未知節(jié)點(diǎn)的真實坐標(biāo)值。

2.2 基于殘差分析的過濾算法

由于WSN中存在著一部分的惡意錨節(jié)點(diǎn)，使得未知節(jié)點(diǎn)得到的部分距離測量值不準(zhǔn)確，定位所需的信息集{(xi,yi),di}與(1)式不相容，所以使用梯度下降法無法得到精確解，最終估計值會出現(xiàn)很大的誤差，因此考慮使用一種過濾算法，在迭代計算的過程中，通過算法找到惡意錨節(jié)點(diǎn)，并且將其濾除，使用剩下的信息集對未知節(jié)點(diǎn)進(jìn)行定位運(yùn)算。

分析定位迭代計算中的殘差問題。根據(jù)安全定位模型，第i個錨節(jié)點(diǎn)對應(yīng)的定位殘差為

(9)

(9)式中，[xest,yest]T表示第k次迭代得到的估計位置值。那么可以求得所有錨節(jié)點(diǎn)的定位殘差總和為

(10)

于是在一次迭代運(yùn)算中，所有錨節(jié)點(diǎn)對應(yīng)的定位殘差平均值為

(11)

最終，可以得到每個錨節(jié)點(diǎn)的殘差偏差值，

(12)

殘差偏差的值代表了每個錨節(jié)點(diǎn)對應(yīng)的殘差以殘差平均值為中心的分散程度。殘差偏差越大，說明其對應(yīng)的錨節(jié)點(diǎn)貢獻(xiàn)的結(jié)果越偏離其他大多數(shù)錨節(jié)點(diǎn)。

在惡意攻擊存在的情況下，梯度下降法不能保證每一個錨節(jié)點(diǎn)對應(yīng)的定位殘差絕對值很小，總會存在一部分的錨節(jié)點(diǎn)對應(yīng)的定位殘差會大于其他的錨節(jié)點(diǎn)。根據(jù)安全定位模型，惡意錨節(jié)點(diǎn)的存在必將增加總定位殘差。因此，可以利用這個原則，在迭代計算收斂于LS解時，計算每個錨節(jié)點(diǎn)對應(yīng)的Δdi殘差大小或者ei，并對它們的大小按升序排列，剔除掉殘差較大或者殘差偏差很大的錨節(jié)點(diǎn)，利用剩余錨節(jié)點(diǎn)計算未知節(jié)點(diǎn)的坐標(biāo)，這樣能夠減小定位誤差。

為了選擇過濾的參考參數(shù)，對根據(jù)殘差大小和根據(jù)殘差偏差大小剔除錨節(jié)點(diǎn)2種方式進(jìn)行了仿真對比，仿真條件如下： 40個錨節(jié)點(diǎn)和一個未知節(jié)點(diǎn)隨機(jī)分布在大小為100 m×100 m的區(qū)域內(nèi)，測量噪聲標(biāo)準(zhǔn)差η=2 m，初始迭代點(diǎn)L(0)在區(qū)域中隨機(jī)選取，惡意錨節(jié)點(diǎn)數(shù)占總錨節(jié)點(diǎn)數(shù)的40%，所有的仿真結(jié)果都通過1 500次運(yùn)行取平均值得到。2個方法都濾除50%錨節(jié)點(diǎn)。

圖1顯示了2種過濾參數(shù)在不同的攻擊強(qiáng)度下的平均定位誤差。從圖1中可以看出，在所有攻擊強(qiáng)度下，根據(jù)殘差偏差大小過濾錨節(jié)點(diǎn)得到的定位誤差明顯小于根據(jù)殘差大小過濾的情況。

圖1 不同攻擊強(qiáng)度下的定位誤差對比圖Fig.1 Comparison chart of positioning errors at different attack intensities

然而在迭代計算結(jié)果收斂于LS解之前，惡意錨節(jié)點(diǎn)參與了未知節(jié)點(diǎn)坐標(biāo)計算，所以這個估計值得到的定位殘差Δdi或者殘差偏差ei都不能完全反映真實的情況，因此，需要對殘差和殘差偏差進(jìn)行綜合考慮，剔除掉殘差和殘差偏差都較大的錨節(jié)點(diǎn)。

為了證明此綜合過濾方法的有效性，對此算法與根據(jù)殘差偏差大小過濾的算法進(jìn)行了仿真比較。如圖2所示，在不同的攻擊強(qiáng)度下，此算法在定位精度上要明顯優(yōu)于殘差偏差大小過濾法。

圖2 綜合過濾與殘差偏差大小過濾的定位誤差比較Fig.2 Comparison of positioning errors between synthetic filtering and residual deviation

出現(xiàn)這種現(xiàn)象的原因是：在迭代運(yùn)算收斂于LS解時，由于有惡意錨節(jié)點(diǎn)提供的惡意信息集{(xm,ym),dm}，特別是惡意錨節(jié)點(diǎn)的攻擊強(qiáng)度過高或者惡意錨節(jié)點(diǎn)的數(shù)量過多時，導(dǎo)致整體的殘差平均值被拉高，這樣誠實錨節(jié)點(diǎn)對應(yīng)的殘差偏差值就會高于部分惡意錨節(jié)點(diǎn)，于是就會出現(xiàn)一種現(xiàn)象，即部分誠實錨節(jié)點(diǎn)對應(yīng)的殘差值很小，而殘差偏差值很大，那么如果只考慮殘差偏差值的大小，這部分誠實錨節(jié)點(diǎn)就有很大可能會被過濾掉，這樣必定會增大定位誤差。而對2個參數(shù)進(jìn)行綜合考慮的話，就可以避免這部分誠實錨節(jié)點(diǎn)被算法濾除掉。

3 仿真結(jié)果與分析

本節(jié)對本文所提出的算法進(jìn)行了仿真分析，并在相同的條件下與其他幾種算法進(jìn)行了比較。對比的3種算法分別是最小中位二乘法(least median square, LMS)、投票算法和梯度下降法。仿真條件為： 40個錨節(jié)點(diǎn)和一個未知節(jié)點(diǎn)隨機(jī)分布在大小為60 m×60 m的區(qū)域內(nèi)，測量噪聲標(biāo)準(zhǔn)差η=2 m，初始迭代點(diǎn)L(0)選擇點(diǎn)[0，0]T，所有的仿真結(jié)果都通過1 500次運(yùn)行取平均值得到。

首先仿真了攻擊強(qiáng)度與定位誤差之間的關(guān)系。設(shè)惡意錨節(jié)點(diǎn)數(shù)占總錨節(jié)點(diǎn)數(shù)目的40%，在攻擊強(qiáng)度為2～20 m的情況下，仿真結(jié)果如圖3所示，圖3中4個算法在攻擊強(qiáng)度增加的情況下，都能穩(wěn)定在理想的定位誤差范圍之中，而本文提出的算法在所有攻擊強(qiáng)度下的定位誤差都明顯小于其他3種算法。

然后對惡意錨節(jié)點(diǎn)所占百分比與定位誤差關(guān)系進(jìn)行了仿真。設(shè)攻擊強(qiáng)度為10 m，仿真結(jié)果如圖4所示。圖4中隨著惡意錨節(jié)點(diǎn)個數(shù)的增加，定位誤差都有所升高，并且當(dāng)惡意錨節(jié)點(diǎn)數(shù)占到50%以上時，曲線斜率增幅變大。本文提出的算法在不同惡意錨節(jié)點(diǎn)個數(shù)情況下的定位誤差比其他3種算法都要小，特別是當(dāng)惡意錨節(jié)點(diǎn)數(shù)目過多時，本文提出的算法依然能保持在理想的定位精度范圍內(nèi)，并且定位誤差遠(yuǎn)小于其他3種算法。

圖3 定位誤差與攻擊強(qiáng)度關(guān)系比較(惡意錨節(jié)點(diǎn)占40%)Fig.3 Comparison of relationship between positioning errors and attack intensities

圖4 惡意錨節(jié)點(diǎn)所占百分比與定位誤差關(guān)系比較(攻擊強(qiáng)度為10 m)Fig.4 Comparison of relationship between positioning errors and percentages of malicious anchor

最后為了檢驗算法定位的準(zhǔn)確性，對定位收斂到真實位置的概率進(jìn)行了仿真比較。設(shè)網(wǎng)絡(luò)中惡意錨節(jié)點(diǎn)數(shù)占總錨節(jié)點(diǎn)數(shù)目的60%時仿真結(jié)果如圖5所示。由于網(wǎng)絡(luò)中通信噪聲等因素的干擾，決定平均定位誤差在3 m范圍內(nèi)，就認(rèn)為它定位到了真實的位置。從圖5中可以看出，在攻擊強(qiáng)度小于6 m時，隨著攻擊強(qiáng)度的增加，所有算法定位到真實位置的概率下降較快，但是都能保持在70%以上。隨著攻擊強(qiáng)度的繼續(xù)增加，LMS和投票法的定位準(zhǔn)確概率持續(xù)下降，而本文所提出的算法和梯度下降法能夠穩(wěn)定在80%以上的范圍，但是本文算法定位準(zhǔn)確概率稍優(yōu)于梯度下降法。

圖5 攻擊強(qiáng)度下定位到真實位置的概率比較(惡意錨節(jié)點(diǎn)數(shù)占60%)Fig.5 Comparison of probabilities of locating to real locations under attack

綜合上述仿真和比較，本文提出的算法在以上參數(shù)情況下都要優(yōu)于LMS、投票法和梯度下降法3種算法，并且本文提出的算法在惡意攻擊強(qiáng)度和惡意錨節(jié)點(diǎn)數(shù)目很高的環(huán)境下都能保持十分理想的定位精度，而且定位誤差遠(yuǎn)小于LMS和投票法。

4 結(jié) 論

本文介紹了一種在惡意環(huán)境中適用于無線傳感網(wǎng)絡(luò)中的安全定位算法，算法結(jié)合了梯度下降法和基于殘差分析的過濾算法，通過仿真實驗證明了過濾算法的有效性，能有效地過濾掉網(wǎng)絡(luò)中的惡意錨節(jié)點(diǎn)，極大減少了惡意攻擊對網(wǎng)絡(luò)節(jié)點(diǎn)定位的干擾。通過仿真對比，表明本文提出的算法能在惡意環(huán)境下抵御惡意攻擊對網(wǎng)絡(luò)節(jié)點(diǎn)定位的攻擊，并且具有很強(qiáng)的魯棒性。

[1] DEMIGHA O, HIDOUCI W K, AHMED T. On energy efficiency in collaborative target tracking in wireless sensor network: a review[J]. Communications Surveys & Tutorials, IEEE, 2013, 15(3): 1210-1222.

[2] 孫啟永，張文，李海波，等． 基于微電極陣列和無線傳感器網(wǎng)絡(luò)的水環(huán)境重金屬檢測系統(tǒng)研究[J].傳感技術(shù)學(xué)報，2013，26(7): 907-911． SUN Qiyong, ZHANG Wen, LI Haibo, et al, In-Situ Heavy Metal Detection in Field Aquatic Environment Based on Wireless Sensor Network and Micro Electrode Array[J]. Chinese Journal of Sensors and Actuators, 2013，26(7): 907-911．

[3] YANG S K, SSU K F. An energy efficient protocol for target localization in wireless sensor network[J]. World Academy of Science, Engineering and Technology, 2009, 56(8): 398-407.

[4] 任楓軒. 高精度遞增式無線傳感網(wǎng)絡(luò)的定位算法[J]. 重慶郵電大學(xué)學(xué)報:自然科學(xué)版,2013,02:184-186，191. REN Fengxuan, High-precision incremental localization algorithm for wireless sensor network[J]. Journal of Chongqing University of Posts and Telecommunications:Natural Science Edition, 2013,02:184-186,191.

[5] 彭宇，王丹．無線傳感器網(wǎng)絡(luò)定位技術(shù)綜述[J].電子測量與儀器學(xué)報，2011，25(5): 389-399． PENG Yu，WANG Dan. A review: wireless sensor networks localization[J]. Journal of Electronic Measurement and Instrument, 2011, 25(5): 389-399．

[6] SALMAN N, GHOGHO M, KEMP A H. On the joint estimation of the RSS-based location and path-loss exponent[J]. Wireless Communications Letters, IEEE, 2012, 1(1): 34-37.

[7] BOUKERCHE A, OLIVEIRA H A B F, NAKAMURA E F, et al. Secure localization algorithms for wireless sensor networks[J]. Communications Magazine, IEEE, 2008, 46(4): 96-101.

[8] 葉阿勇，許力，林暉. 基于RSSI的傳感器網(wǎng)絡(luò)節(jié)點(diǎn)安全定位機(jī)制[J]. 通信學(xué)報, 2012, 33(7): 135-150. YE Ayong, XU Li, LIN Hui, Secure RSSI-based node positioning mechanism for wireless sensor networks[J]. Journal on Communications, 2012, 33(7): 135-150.

[9] MRAZ L, CERVENKA V, KOMOSNY D, et al. Comprehensive performance analysis of ZigBee technology based on real measurements[J]. Wireless personal communications, 2013, 71(4): 2783-2803.

[10] HAN G, JIANG J, SHU L, et al. A two-step secure localization for wireless sensor networks[J]. The Computer Journal, 2013, 56(10): 1154-1166.

[11] YU N, ZHANG L, REN Y. BRS-based robust secure localization algorithm for wireless sensor networks[J]. International Journal of Distributed Sensor Networks, 2013,(11):560-572

[12] 陳宜,蔣朝惠,郭春. 一種抗獨(dú)立攻擊的WSN三維安全定位算法[J]. 傳感技術(shù)學(xué)報,2015,28(11):1702-1707. CHEN Yi, JIANG Chaohui, GUO Chun. A 3D Secure Localization Algorithm Resistant to Non-Coordinated Attack in Wireless Sensor Network[J]. Chinese Journal of Sensors and Actuators, 2015,28(11):1702-1707.

[13] GARG R, VARNA A L, WU M. An efficient gradient descent approach to secure localization in resource constrained wireless sensor networks[J]. IEEE Transactions on Information Forensics and Security, 2012, 7(2): 717-730.

(編輯：張 誠)

s：The Central State-Owned Capital Operating Budget Project of China (2013-470)；The Central Universities Basic Research Project of China (2014-004)；The National Natural Science Foundation of China (61172089)；The Planned Science and Technology Project of Hunan Province of China (2014WK3001)；The Post-doctoral Science Foundation of China (2014M562100)；The Planned Science and Technology Key Project of Hunan Province of China (2015JC3053)

A secure localization algorithm based on residual analysis filtration

TENG Yun, LIU Hongli, XU Kun
(College of Electrical and Information Engineering, Hunan University, Changsha 410082,P.R. China)

During the process of localization in the wireless sensor network, the appearance of malicious anchor nodes will destroy the performance of network positioning. In order to solve this problem, a new wireless sensor network security algorithm is proposed，which based on the characteristics of malicious anchor nodes and the residual problem in location calculation. Firstly, a distance-based security location model is established. Then the residual problem in the network location is analyzed, and the malicious anchor nodes in the network are filtered out by the characteristic of residual. Finally, the unknown nodes are realized high-precision positioning result by the information of residual anchor node and gradient descent method. The simulation results show that the proposed algorithm can achieve relatively high positioning accuracy under a variety of performance indexes, and can maintain high positioning performance even under intensified malicious attacks. So this algorithm can not only effectively resist the malicious attack on the node location, but also significantly enhance the security of network localization.

wireless sensor networks; secure localization; gradient descent; residual analysis; filtering

2016-06-11

2017-04-25 通訊作者：劉宏立 honglilin@hnu.edu.cn

中央國有資本經(jīng)營預(yù)算項目(2013-470)；中央高?；究蒲许椖?2014-004)；國家自然科學(xué)基金(61172089)；湖南省科技計劃項目(2014WK3001)；中國博士后科研基金(2014M562100)；湖南省科技計劃重點(diǎn)項目(2015JC3053)

10.3979/j.issn.1673-825X.2017.03.004

TN212.9

A

1673-825X(2017)03-0307-06

滕 云(1992-)，男，湖南常德人，碩士研究生，研究方向為無線傳感網(wǎng)絡(luò)定位和安全。E-mail:1090317073@qq.com

劉宏立(1963-)，男，湖南常德人，教授，博士生導(dǎo)師，研究方向為無線傳感網(wǎng)絡(luò)、移動通信系統(tǒng)與軟件無線電、智能信息處理與傳輸技術(shù)。E-mail:hongliliu@hnu.edu.cn。

徐 琨(1979-)，男，湖南津市人，博士研究生，研究方向為無線傳感網(wǎng)絡(luò)定位和安全。E-mail:kunxuhnu@sina.com。