一種基于迭代優化的安全定位算法*

滕 云,劉宏立(湖南大學電氣與信息工程學院,長沙 410082)

?

一種基于迭代優化的安全定位算法*

滕 云,劉宏立*
(湖南大學電氣與信息工程學院,長沙 410082)

由于無線傳感網絡節點往往部署在惡意環境中,節點不能獲得準確的位置信息,導致網絡運行的安全性受到破壞。針對無線傳感網絡在惡意環境中的安全定位問題,提出了一種新的基于牛頓迭代法的安全定位算法。首先建立了安全定位模型,然后對迭代過程中梯度矢量進行了分析,并且利用差分閥值法改進和優化了按百分比過濾的異常檢測過程,最后通過剩余錨節點信息和牛頓迭代法對未知節點實現高精度定位,進一步提高了節點定位精度。仿真結果證明,牛頓迭代法在定位應用上優于梯度下降法,并且優化后的安全定位算法具有更好的定位精度和魯棒性。

無線傳感器網絡;安全定位;牛頓迭代法;異常檢測;差分閥值法;

隨著網絡技術和無線通信技術的迅猛發展,無線傳感網絡[1]WSN(Wireless Sensor Network)成為了當今炙手可熱的信息獲取和處理技術。因為其具有功耗低,組網快捷的特點而被運用到很多的民用和軍事領域,它在定位方面更是具有價格低廉,定位精準,布置網絡方便,無需維護的特點,使其被廣泛的應用各個方面,如森林防火,海洋探測,軍事監測[2],環境監控[3]等。

目前的WSN節點定位算法主要分為兩類:距離無關(range-free)的定位算法[4]和基于距離(range-based)的定位算法[5]。range-based定位算法由于定位精度高,得到了研究人員的廣泛關注。到達時間(ToA)[6]、到達時間差(TDoA)[7]、到達角度(AoA)、和接收信號強度(RSSI)[8]是最常用的測距技術。基于RSSI的定位算法由于實現簡單、無需額外的硬件設施而被廣泛的應用。但是,由于WSN一般部署在無人值守的區域,傳輸信道的廣播特性,使其很容易受到攻擊者的各種惡意攻擊,使網絡中的節點不能夠準確的定位

對于在惡意環境下的無線傳感網絡安全定位問題,研究人員已經從不同的方面提出了一些傳感器節點定位的安全策略[9],如有的方法采用一系列的包括時間、空間和一致性的檢驗技術來抵御針對距離的欺騙攻擊[10]。文獻[11]針對WSN定位中遇到的獨立攻擊,結合最速下降法和牛頓迭代法提出了一種抗獨立攻擊的安全定位算法,通過惡意錨節點檢測技術和最速下降法選出最優錨節點數據,并利用牛頓迭代法實現了快速高精度的三維安全定位。文獻[12]提出了一種名為BRS的安全定位算法,使用信譽系統篩選錨節點,并利用加權泰勒展開式的最小二乘算法來獲得最終的定位位置,該算法有效的減輕了惡意錨節點對網絡節點定位的影響。但是利用信譽機制篩選錨節點會給網絡節點帶來很大的能量消耗,影響了網絡運行效率。文獻[13]根據統計方法提出了基于最小二乘法和最小中位數二乘法算法,通過基于中值距離的測量和計算方式,容忍WSN中對定位的惡意攻擊。

本文提出的安全定位算法是一種過濾算法,結合牛頓迭代和優化的異常檢測方式,根據梯度矢量的差分閥值過濾掉網絡中的惡意錨節點,對未知節點進行高精度迭代定位。本文對文獻[14]提出的異常檢測的過濾方式進行了改進,利用差分閥值取代了該文獻中的根據百分比過濾的方式,并且使用了定位性能更好的牛頓迭代法進行定位計算。由于過濾算法方式的改進和定位方法的不同使得在定位精度上有一定區別,仿真結果表明本文所提出的算法能得到更好的定位精度。

1 安全定位模型

假設一個部屬在二維空間R2的無線網絡,網絡中有n個錨節點和一個目標節點,錨節點位置已知,其坐標可以表示為(xi,yi);目標節點u位置未知,其坐標為(x,y)。假設目標節點能夠和所有的錨節點之間進行通信,每個錨節點都會發送一個包含自身位置信息和ID的信標報文給目標節點,目標節點接收到這些信息后,采用一定的定位算法計算出自己的位置信息。令這些錨節點分別為M1,…,Mn,在這n個錨節點中,部分錨節點可能是惡意錨節點,這些惡意錨節點會發送錯誤信標和位置信息給節點N,而誠實錨節點完全按照定位協議如實地發送自己的信息給節點N。令k表示惡意錨節點的數目,并且網絡無法預知k的大小。

(1)

(2)

(3)

那么,定義代價函數

(4)

可以證明λ(L)是一個凸函數,因此,定位問題就等價于尋找使代價函數λ(L)達到最小值的點L0。

2 基于迭代的安全定位算法

2.1 基于牛頓迭代安全定位算法

針對上述安全定位模型分析,λ(L)是一個凸函數,這個凸性使得其能夠使用牛頓迭代法對式(4)求取非線性最小值點。設第k次迭代以后得到的估計坐標為L(k),在L(k)處將代價函數λ(L)按二階泰勒級數展開

(5)

式中:右上角的H表示埃爾米特轉置。求解第k次的梯度向量

(6)

gi(k)是第i個錨節點對應的梯度矢量,對代價函數求解二階偏導,

(7)

得到的H(k)是L(k)處代價函數λ(L)的海森矩陣。式(5)對L求導并令導數為零,可求出下一個迭代結果為

L(k+1)=L(k)-H-1(k)g(k)

(8)

式中:H-1(k)是海森矩陣H(k)的逆矩陣。這個迭代方程就是最優化理論中牛頓法迭代公式。

根據牛頓迭代理論可以證明,經過少量的迭代以后,牛頓迭代計算估計值收斂于LS解。當網絡中存在一部分錨節點是惡意錨節點時,所得到的LS解就不準確。惡意錨節點的數目越多,所估計位置的誤差就越大。因此僅僅通過牛頓迭代運算不能在惡意環境下得到理想的節點估計值,需要利用異常檢測找出網絡中的惡意錨節點,并且將其濾除掉才能極大減小惡意攻擊對定位的影響。

2.2 異常檢測

異常檢測是為了減少惡意攻擊對定位精度的影響。圖1表示了一個包含3個錨節點的異常檢測過程,當梯度向量‖g(k)‖小于預先設定的門限閾值時,梯度矢量模值‖gi(k)‖大的錨節點會被認為是惡意錨節點而被濾除掉。設{‖g1(k)‖,…,‖gi(k)‖,‖gi+1(k)‖,…,‖gn(k)‖}是關于力矢量的從小到大的有序排列,若對于某一個i,有‖gi+1(k)‖-‖gi(k)‖>β,其中β為差分閾值,則去除{‖gi+1(k)‖,…,‖gn(k)‖}的所有力矢量,用剩余的力矢量計算梯度g(k),再根據式(8)進行下一步迭代。按照力矢量模值的相對大小以及差分閾值β的選擇來對惡意錨節點進行過濾。

圖1 異常檢測過程示意圖

3 性能分析

為了分析牛頓迭代算法在定位中的性能,針對3個參數對牛頓迭代法和梯度下降法進行比較。控制仿真參數的一致性,仿真條件參照文獻給出:30個錨節點隨機分布在大小為60 m×60 m的區域中,測量噪聲標準差η=2 m,梯度向量模值門限閾值為0.9,初始迭代點L‖0‖在區域中隨機選取,惡意錨節點數占總錨節點數的30%,即9個惡意錨節點。所有的仿真結果都通過1 500次運行取平均值得到,異常檢測階段去除50%的錨節點。

圖2 牛頓迭代法平均迭代次數曲線

收斂速度是迭代運算中至關重要的參數,因為它決定了運算效率,特別是應用在WSN中時,計算效率越高,整個網絡的工作效率就越高。于是仿真了牛頓迭代法在不同攻擊強度下的平均迭代次數。從圖2可以看到,該方法收斂時的迭代最大次數不超過18次。而文獻[15]仿真顯示梯度下降法需要200次迭代才能收斂,因此牛頓迭代法的收斂速度非常快,計算效率是梯度下降的10倍。

第2個參數是定位誤差。從圖3可以看到,不論攻擊強度多大,牛頓迭代法的定位誤差都小于梯度下降法。

圖3 攻擊強度與定位誤差關系圖

由于在迭代計算的過程中,有可能出現不收斂的情況,這種情況會使得最后的計算結果誤差相當大,因此穩定性也是影響定位的重要參數。最后仿真了在攻擊強度σattack=10 m的條件下,牛頓迭代法和梯度下降法1 500次的平均定位誤差。圖4可以看出,牛頓迭代法的收斂概率近似為1,而梯度下降法有時會出現很大的定位誤差。因此,梯度下降法的收斂性不能得到保證,其穩定度較差,而牛頓迭代法的穩定性更好。

圖4 定位誤差蒙特卡洛實驗曲線(σattack=10 m)

差分閾值β的大小選擇會直接影響定位誤差的大小,圖5顯示了差分閾值β的大小與定位誤差的關系。從圖中可以看到,差分閾值β與定位誤差曲線大致呈拋物線形,β=1.5時定位誤差最小。

圖6表示出了基于差分閾值異常檢測和固定百分比異常檢測的比較結果。從圖中可以明顯看到,不論從攻擊強度還是惡意錨節點數來看,基于差分閾值的異常檢測結果都明顯好于固定百分比異常檢測結果。

圖5 差分閾值與定位誤差關系圖

圖6 基于差分閾值和固定百分比異常檢測比較圖

4 結束語

本文提出了一種基于牛頓迭代法的無線傳感器網絡安全定位算法。該算法在定位精度、收斂次數和穩定性方面都要優于梯度下降法。同時,本文還對異常檢測階段作了分析及改進,針對異常檢測過濾固定百分比錨節點的不足,提出了可以自適應調整過濾錨節點數目的基于差分閥值的安全檢測法,從而進一步提高算法的定位精度。

[1] Kuriakose J,Joshi S,Raju R V,et al. A Review on Localization in Wireless Sensor Networks[M]//Advances in Signal Processing and Intelligent Recognition Systems. Springer International Publishing,2014:599-610.

[2] Demigha O,Hidouci W K,Ahmed T. On Energy Efficiency in Collaborative Target Tracking in Wireless Sensor Network:A Review[J]. Communications Surveys and Tutorials,IEEE,2013,15(3):1210-1222.

[3] 孫啟永,張文,李海波,等. 基于微電極陣列和無線傳感器網絡的水環境重金屬檢測系統研究[J]. 傳感技術學報,2013,26(7):907-911.

[4] Chen C C,Chang C Y,Li Y N. Range-Free Localization Scheme in Wireless Sensor Networks Based on Bilateration[J]. International Journal of Distributed Sensor Networks,2013,2013.

[5] Cheng L,Wu C,Zhang Y,et al. A Survey of Localization in Wireless Sensor Network[J]. International Journal of Distributed Sensor Networks,2012,2012.

[6] Vaghefi R M,Schloemann J,Buehrer R M. NLOS Mitigation in TOA-Based Localization Using Semidefinite Programming[C]//2013 10th Workshop on Positioning Navigation and Communication(WPNC). IEEE,2013:1-6.

[7] Lin L,So H C,Chan F K W,et al. A New Constrained Weighted Least Squares Algorithm for TDOA-Based Localization[J]. Signal Processing,2013,93(11):2872-2878.

[8] Livinsa Z M,Jayashri S. Performance Analysis of Diverse Environment Based on RSSI Localization Algorithms in WSNS[C]//2013 IEEE Conference on Information and Communication Technologies(ICT). IEEE,2013:572-576.

[9] 葉阿勇,許力,林暉. 基于RSSI的傳感器網絡節點安全定位機制[J]. 通信學報,2012,33(7):135-150.

[10] Chen H,Lou W,Wang Z. A Novel Secure Localization Approach in Wireless Sensor Networks[J]. EURASIP Journal on Wireless Communications and Networking,2010,2010:1-12.

[11] 陳宜,蔣朝惠,郭春. 一種抗獨立攻擊的WSN三維安全定位算法[J]. 傳感技術學報,2015,28(11):1702-1707.

[12] Yu N,Zhang L,Ren Y. BRS-Based Robust Secure Localization Algorithm for Wireless Sensor Networks[J]. International Journal of Distributed Sensor Networks,2013,2013.

[13] Li Z,Trappe W,Zhang Y,et al. Robust Statistical Methods for Securing Wireless Localization in Sensor Networks[C]//Proceedings of the 4th International Symposium on Information Processing in Sensor Networks. IEEE Press,2005:12.

[14] 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.

[15] Garg R,Varna A L,Wu M. Gradient Descent Approach for Secure Localization in Resource Constrained Wireless Sensor Networks[C]//2010 IEEE International Conference on Acoustics,Speech and Signal Processing. IEEE,2010:1854-1857.

滕 云(1992-),男,湖南常德人,湖南大學碩士研究生,研究方向為無線傳感網絡定位和安全,1090317073@qq.com;

劉宏立(1963-),男,湖南常德人,湖南大學教授,博士生導師,研究方向為無線傳感網絡、移動通信系統與軟件無線電、智能信息處理與傳輸技術,hongliliu@hnu.edu.cn。

A Secure Localization Algorithm Based on Iterative Optimization Method*

TENG Yun,LIU Hongli*
(College of Electrical and Information Engineering,Hunan University,Changsha 410082,China)

Because wireless sensor network nodes are often deployed in malicious environment,the node cannot get accurate location information,which leads to the destruction of network security. For the problem of secure location of wireless sensor networks in malicious environment,a new security localization algorithm based on Newton iteration method is proposed. Firstly,the security localization model is established,then the gradient vector is analyzed in the process of iteration,and the anomaly detection process is improved and optimized by using the differential threshold method. Finally,the unknown node is realized high-precision positioning result by residual information of anchor node and Newton iteration method,and further improving the node positioning accuracy. The simulation results show that Newton iterative method is better than gradient descent method in location application,and the optimized security location algorithm has better location accuracy and robustness.

wireless sensor network;secure localization;Newton iteration method;anomaly detection;differential threshold algorithm

項目來源:中央國有資本經營預算項目(財企[2013]470號);中央高校基本科研項目(2014-004);國家自然科學基金項目(61172089);湖南省科技計劃項目(2014WK3001);中國博士后科研基金項目(2014M562100);湖南省科技計劃重點項目(2015JC3053)

2016-07-04 修改日期:2016-12-16

TN212.9

A

1004-1699(2017)04-0570-05

C:7230

10.3969/j.issn.1004-1699.2017.04.015