一種基于迭代優(yōu)化的安全定位算法*

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

?

一種基于迭代優(yōu)化的安全定位算法*

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

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

無線傳感器網(wǎng)絡(luò);安全定位;牛頓迭代法;異常檢測;差分閥值法;

隨著網(wǎng)絡(luò)技術(shù)和無線通信技術(shù)的迅猛發(fā)展,無線傳感網(wǎng)絡(luò)[1]WSN(Wireless Sensor Network)成為了當(dāng)今炙手可熱的信息獲取和處理技術(shù)。因?yàn)槠渚哂泄牡?組網(wǎng)快捷的特點(diǎn)而被運(yùn)用到很多的民用和軍事領(lǐng)域,它在定位方面更是具有價(jià)格低廉,定位精準(zhǔn),布置網(wǎng)絡(luò)方便,無需維護(hù)的特點(diǎn),使其被廣泛的應(yīng)用各個(gè)方面,如森林防火,海洋探測,軍事監(jiān)測[2],環(huán)境監(jiān)控[3]等。

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

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

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

1 安全定位模型

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

(1)

(2)

(3)

那么,定義代價(jià)函數(shù)

(4)

可以證明λ(L)是一個(gè)凸函數(shù),因此,定位問題就等價(jià)于尋找使代價(jià)函數(shù)λ(L)達(dá)到最小值的點(diǎn)L0。

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

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

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

(5)

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

(6)

gi(k)是第i個(gè)錨節(jié)點(diǎn)對(duì)應(yīng)的梯度矢量,對(duì)代價(jià)函數(shù)求解二階偏導(dǎo),

(7)

得到的H(k)是L(k)處代價(jià)函數(shù)λ(L)的海森矩陣。式(5)對(duì)L求導(dǎo)并令導(dǎo)數(shù)為零,可求出下一個(gè)迭代結(jié)果為

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

(8)

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

根據(jù)牛頓迭代理論可以證明,經(jīng)過少量的迭代以后,牛頓迭代計(jì)算估計(jì)值收斂于LS解。當(dāng)網(wǎng)絡(luò)中存在一部分錨節(jié)點(diǎn)是惡意錨節(jié)點(diǎn)時(shí),所得到的LS解就不準(zhǔn)確。惡意錨節(jié)點(diǎn)的數(shù)目越多,所估計(jì)位置的誤差就越大。因此僅僅通過牛頓迭代運(yùn)算不能在惡意環(huán)境下得到理想的節(jié)點(diǎn)估計(jì)值,需要利用異常檢測找出網(wǎng)絡(luò)中的惡意錨節(jié)點(diǎn),并且將其濾除掉才能極大減小惡意攻擊對(duì)定位的影響。

2.2 異常檢測

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

圖1 異常檢測過程示意圖

3 性能分析

為了分析牛頓迭代算法在定位中的性能,針對(duì)3個(gè)參數(shù)對(duì)牛頓迭代法和梯度下降法進(jìn)行比較?？刂品抡鎱?shù)的一致性,仿真條件參照文獻(xiàn)給出:30個(gè)錨節(jié)點(diǎn)隨機(jī)分布在大小為60 m×60 m的區(qū)域中,測量噪聲標(biāo)準(zhǔn)差η=2 m,梯度向量模值門限閾值為0.9,初始迭代點(diǎn)L‖0‖在區(qū)域中隨機(jī)選取,惡意錨節(jié)點(diǎn)數(shù)占總錨節(jié)點(diǎn)數(shù)的30%,即9個(gè)惡意錨節(jié)點(diǎn)。所有的仿真結(jié)果都通過1 500次運(yùn)行取平均值得到,異常檢測階段去除50%的錨節(jié)點(diǎn)。

圖2 牛頓迭代法平均迭代次數(shù)曲線

收斂速度是迭代運(yùn)算中至關(guān)重要的參數(shù),因?yàn)樗鼪Q定了運(yùn)算效率,特別是應(yīng)用在WSN中時(shí),計(jì)算效率越高,整個(gè)網(wǎng)絡(luò)的工作效率就越高。于是仿真了牛頓迭代法在不同攻擊強(qiáng)度下的平均迭代次數(shù)。從圖2可以看到,該方法收斂時(shí)的迭代最大次數(shù)不超過18次。而文獻(xiàn)[15]仿真顯示梯度下降法需要200次迭代才能收斂,因此牛頓迭代法的收斂速度非?？?計(jì)算效率是梯度下降的10倍。

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

圖3 攻擊強(qiáng)度與定位誤差關(guān)系圖

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

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

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

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

圖5 差分閾值與定位誤差關(guān)系圖

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

4 結(jié)束語

本文提出了一種基于牛頓迭代法的無線傳感器網(wǎng)絡(luò)安全定位算法。該算法在定位精度、收斂次數(shù)和穩(wěn)定性方面都要優(yōu)于梯度下降法。同時(shí),本文還對(duì)異常檢測階段作了分析及改進(jìn),針對(duì)異常檢測過濾固定百分比錨節(jié)點(diǎn)的不足,提出了可以自適應(yīng)調(diào)整過濾錨節(jié)點(diǎn)數(shù)目的基于差分閥值的安全檢測法,從而進(jìn)一步提高算法的定位精度。

[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] 孫啟永,張文,李海波,等. 基于微電極陣列和無線傳感器網(wǎng)絡(luò)的水環(huán)境重金屬檢測系統(tǒng)研究[J]. 傳感技術(shù)學(xué)報(bào),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的傳感器網(wǎng)絡(luò)節(jié)點(diǎn)安全定位機(jī)制[J]. 通信學(xué)報(bào),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] 陳宜,蔣朝惠,郭春. 一種抗獨(dú)立攻擊的WSN三維安全定位算法[J]. 傳感技術(shù)學(xué)報(bào),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-),男,湖南常德人,湖南大學(xué)碩士研究生,研究方向?yàn)闊o線傳感網(wǎng)絡(luò)定位和安全,1090317073@qq.com;

劉宏立(1963-),男,湖南常德人,湖南大學(xué)教授,博士生導(dǎo)師,研究方向?yàn)闊o線傳感網(wǎng)絡(luò)、移動(dòng)通信系統(tǒng)與軟件無線電、智能信息處理與傳輸技術(shù),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

項(xiàng)目來源:中央國有資本經(jīng)營預(yù)算項(xiàng)目(財(cái)企[2013]470號(hào));中央高?；究蒲许?xiàng)目(2014-004);國家自然科學(xué)基金項(xiàng)目(61172089);湖南省科技計(jì)劃項(xiàng)目(2014WK3001);中國博士后科研基金項(xiàng)目(2014M562100);湖南省科技計(jì)劃重點(diǎn)項(xiàng)目(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