基于信息分組的TDOA安全定位算法

吳開興,張榮華

(河北工程大學(xué)信息與電氣工程學(xué)院,河北邯鄲056038)

無線傳感器網(wǎng)絡(luò)(wireless sensor network, WSN)是一種新型的低功耗、自組織、短距離的無線傳輸網(wǎng)絡(luò),可以實(shí)時(shí)監(jiān)測網(wǎng)絡(luò)分布區(qū)域內(nèi)各種監(jiān)測對象的狀態(tài)信息。在WSN的各種應(yīng)用中,大多數(shù)需要確定事件發(fā)生的位置,或者需要對目標(biāo)進(jìn)行跟蹤。隨著WSN應(yīng)用研究的不斷深入,對定位技術(shù)提出了更高需求。其中,安全定位已經(jīng)與定位精度和能耗一起成為WSN中評價(jià)定位算法性能的三個(gè)主要標(biāo)準(zhǔn)之一。安全定位技術(shù)是WSN節(jié)點(diǎn)定位的關(guān)鍵技術(shù),是定位過程有效性的重要保障[1]。

現(xiàn)有針對基于TDOA測距提出的安全定位算法,或者依賴于節(jié)點(diǎn)的密度[2],或者計(jì)算復(fù)雜性過高[3],或者只針對某種特定的攻擊[4],具有局限性。由于WSN受到的攻擊種類可能多種多樣,不可能對每種可能出現(xiàn)的特定攻擊行為采取一一防范的措施[5]。本文將針對基于TDOA測距的定位提出一種抵抗輕量級攻擊的定位算法AR-TDOA (Attack Resistant-Time Difference Of Arrival),采用信息分組方法隔離可疑數(shù)據(jù),目的是在存在攻擊的情況下,保證節(jié)點(diǎn)的可靠定位,屬于被動式的安全定位思想。

1 AR-TDOA算法

節(jié)點(diǎn)定位過程中,為了提供初始的定位參照,需要在初始化階段預(yù)先部署一定比例的錨節(jié)點(diǎn)(beacon node),錨節(jié)點(diǎn)可通過GPS或預(yù)設(shè)等方式實(shí)現(xiàn)定位,配有大功率無線發(fā)射設(shè)備,向未知節(jié)點(diǎn)發(fā)送包含位置信息的信標(biāo)報(bào)文。

1.1 TDOA測距原理

TDOA是一種適用性較強(qiáng)的定位算法,通過記錄信號的到達(dá)時(shí)間差來測量距離,降低了對時(shí)間同步的要求,測距精度可達(dá)到厘米級,被廣泛應(yīng)用于WSN定位系統(tǒng)。

TDOA測距原理如圖1所示,發(fā)射節(jié)點(diǎn)同時(shí)發(fā)射無線射頻信號和超聲波信號,接收節(jié)點(diǎn)記錄兩種信號到達(dá)的時(shí)間 T1、T2,己知無線射頻信號和超聲波的傳播速度分別為 c1、c2,那么兩點(diǎn)之間的距離為

1.2 坐標(biāo)計(jì)算

本文計(jì)算坐標(biāo)采用的是多邊測量法的極大似然估計(jì)法。此方法在測距存在一定誤差的情況下仍然能夠達(dá)到相當(dāng)高的定位精度。在進(jìn)行坐標(biāo)求解時(shí),采用多邊測量法(multilateration),它是三邊測量法的變形,如圖2所示。

即有n(n＞3)個(gè)參考節(jié)點(diǎn) P1(x1,y1),P2(x2,y2),…,Pn(xn,yn)到未知節(jié)點(diǎn)M的距離分別為d1,d2,…,dn,設(shè)M的坐標(biāo)為(x,y),則滿足

采用極大似然估計(jì)法(Maximum Likelihood Estimation,MLE)求解,從第一個(gè)方程開始分別減去最后一個(gè)方程,得

用線性方程組表示為

使用標(biāo)準(zhǔn)的最小均方差估計(jì)法可以得到節(jié)點(diǎn)M的坐標(biāo)為

1.3 抵抗攻擊的安全定位算法設(shè)計(jì)

提出的AR-TDOA算法主要針對安全敏感的無線傳感器網(wǎng)絡(luò)應(yīng)用。AR-TDOA算法是在TDOA測距技術(shù)基礎(chǔ)上增加安全機(jī)制,充分利用節(jié)點(diǎn)定位系統(tǒng)中大都存在冗余參照信息的特性,以方差的無偏估計(jì)是否符合誤差假設(shè)為安全性檢驗(yàn)依據(jù),對采集來的定位信息進(jìn)行數(shù)據(jù)分組過濾,目的是在存在攻擊的條件下仍能有效的計(jì)算正確的定位結(jié)果,降低攻擊對定位的影響。

本論文擬采用兩步對采集來的信息進(jìn)行過濾。

首先,對采集來的定位信息三元組進(jìn)行初步過濾,考慮基于TDOA測距技術(shù)定位的特點(diǎn),利用待定位節(jié)點(diǎn)與錨節(jié)點(diǎn)之間的距離d必定在節(jié)點(diǎn)的通信范圍之內(nèi)的特性,粗略濾掉 d＞R的定位數(shù)據(jù),為第二步信息分組做鋪墊。

其次,綜合分析、比較了多種信息分組方法的時(shí)間復(fù)雜度和定位誤差之后,選擇復(fù)雜度和定位精度達(dá)到平衡的4NP算法[6]作為AR-TDOA中使用的信息集分組算法,對其進(jìn)行改進(jìn),利用信息的一致性對定位信息進(jìn)行分組。

正常的定位信息集其定位誤差或均方差滿足一定規(guī)律,因此正常的定位信息集中的定位信息三元組(xi,yi,di)之間滿足某種關(guān)聯(lián)特征。存在攻擊的定位信息集中,惡意信標(biāo)發(fā)出的定位信息三元組(xi,yi,di)與正常定位信息之間不存在關(guān)聯(lián)特征,這些惡意三元組(xi,yi,di)在整個(gè)定位信息集中是奇異點(diǎn)。正常的定位信息可以根據(jù)數(shù)據(jù)之間的一致性進(jìn)行數(shù)據(jù)分類,從而很容易排除這些奇異點(diǎn)。

1.4 一致性檢驗(yàn)原則

由于存在測距誤差,定位系統(tǒng)大都采用最小二乘法(least square,LS)進(jìn)行估算。LS的回歸模型和估算函數(shù)分別為

LS算法簡單易行,但由于其代價(jià)函數(shù)采用求總和方式,LS算法對局外點(diǎn)非常敏感,單個(gè)干擾數(shù)據(jù)就足于導(dǎo)致參數(shù)估計(jì)嚴(yán)重偏差。針對LS算法的脆弱性,采用統(tǒng)計(jì)方法對定位結(jié)果進(jìn)一步分析。根據(jù)經(jīng)典回歸理論可知,如果測距誤差的分布是已知的,則通過分析殘差可以檢驗(yàn)所給參照數(shù)據(jù)是否服從誤差分布,利用這個(gè)規(guī)律可以檢驗(yàn)定位參照集是否滿足一致性檢驗(yàn)。

1.5 改進(jìn)后的4NP信息分組算法

改進(jìn)后的4NP信息分組算法步驟如下：

步驟1：生成安全定位信息集。利用蒙特卡方法從L中隨機(jī)抽取K(K≥3)個(gè)元素形成集合L1,對集合L1進(jìn)行一致性檢驗(yàn),直到集合L1通過一致性檢驗(yàn)為止。

步驟2：集合劃分。從剩余的L-L1中取出元素(xi,yi,di)放入L1中,對L1進(jìn)行一致性檢驗(yàn),若滿足則將元素(xi,yi,di)取出,放入L3;不滿足則將元素取出,放入L2。直至l中所有元素取完,將L3元素并入L1中,若L1不滿足一致性校驗(yàn)則繼續(xù)轉(zhuǎn)到步驟1。

步驟3：生成新簇L1,利用 L1中的元素采用極大似然估計(jì)法進(jìn)行定位求解。

2 仿真結(jié)果

本節(jié)通過仿真來驗(yàn)證以上理論結(jié)果的正確性及檢測算法的有效性,比較基于TDOA的定位算法,SeRLoc安全定位算法和AR-TDOA在受到攻擊時(shí)的定位性能。在100m×100m區(qū)域內(nèi)部署4個(gè)錨節(jié)點(diǎn),坐標(biāo)分別為(0,0),(0,100),(100,0) (100,100)。系統(tǒng)參數(shù)參照MIT開發(fā)的室內(nèi)定位系統(tǒng)Cricket[8]取典型值,節(jié)點(diǎn)平均偵聽到錨節(jié)點(diǎn)數(shù)為4,節(jié)點(diǎn)間通信距離為R,錨節(jié)點(diǎn)通信距離與R的比值為10,節(jié)點(diǎn)數(shù)N=500,未知節(jié)點(diǎn)隨機(jī)放置,測距誤差滿足ε～U(-e,e)。

實(shí)驗(yàn)考察了不同虛假錨節(jié)點(diǎn)數(shù)量情況下對定位的影響,仿真中錨節(jié)點(diǎn)通信半徑R=150m,模擬敵方虛假錨節(jié)點(diǎn),向定位場景中廣播錯誤的位置信息。整個(gè)實(shí)驗(yàn)重復(fù)1 000次,并取平均值。

圖3為3種定位算法在不同攻擊強(qiáng)度下的定位比較,其中 c為虛假錨節(jié)點(diǎn)數(shù)量,da為攻擊強(qiáng)度,即虛假錨節(jié)點(diǎn)聲稱的坐標(biāo)與真實(shí)坐標(biāo)的偏差距離,de為平均定位誤差,即定位結(jié)果偏離未知節(jié)點(diǎn)真正坐標(biāo)的平均距離。由圖3可以看出,攻擊強(qiáng)度da從0逐漸增大到100m的過程中,3種定位算法的定位誤差明顯不同。da增大,基于TDOA測距的定位算法的定位誤差明顯增大,SeRLoc安全定位算法因扇形區(qū)域面積而忽略攻擊強(qiáng)度小的定位坐標(biāo),但隨著攻擊強(qiáng)度的進(jìn)一步增大,定位誤差隨之大幅增大。AR-TDOA算法的定位誤差稍微增大到一個(gè)峰值后又回落到一個(gè)較小的穩(wěn)定值,這是因?yàn)檩^明顯的定位攻擊第一步就被濾掉。

從圖3中的曲線對比中可以看出,虛假錨節(jié)點(diǎn)數(shù)量c由1變?yōu)?時(shí),基于TDOA測距的定位算法和SeRLoc安全定位算法的定位誤差對應(yīng)增大,這是由于增加了的虛假定位信息影響了定位精度。AR-TDOA算法定位誤差變化相對緩和,因其采用了一致性檢驗(yàn)原則排除虛假數(shù)據(jù),利用符合條件的定位信息組進(jìn)行定位計(jì)算。

改進(jìn)前后的定位算法在計(jì)算開銷與穩(wěn)定性方面的比較見表1,可以看出改進(jìn)后的AR-TDOA算法相對于基于TDOA測距的定位算法和SeRLoc安全定位算法在計(jì)算開銷方面有少量增加,在穩(wěn)定性方面優(yōu)于前者。

表1 虛假錨節(jié)點(diǎn)攻擊條件下定位比較Tab.1 Positioning comparison with malicious beacon nodes

3 結(jié)論

1)攻擊強(qiáng)度增大,三種定位算法的平均定位誤差隨之增大,其定位誤差大小順序依次為TDOA＞SeRLoc＞AR-TDOA。

2)虛假錨節(jié)點(diǎn)數(shù)量越大,基于TDOA測距和SeRLoc的定位誤差越大,但AR-TDOA算法的定位誤差能保持在較小程度內(nèi)。

3)AR-TDOA算法在增加少量計(jì)算復(fù)雜度的情況下,能夠改善定位的穩(wěn)定性。

[1]曹曉梅,俞波,陳貴海,等.傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位系統(tǒng)安全性分析[J].軟件學(xué)報(bào),2008,19(4)：879-887.

[2]LAZOS L,POOVENDRAN R.SeRLoc：Secure range-independent localization for wireless sensor networks[C]// LAZOSL L,POOVENDR AN R.Proc.of the 2004 ACM Workshop on Wireless Security.New York：ACM Press, 2004：196-207.

[3]LIU D,NING P,DU W K.Attack-resistant location estimation in sensor networks[C]//ZHAO F,COZZENS J,ESTRIN D.Proc.of the Int'l Conf.on Information Processing in Sensor Networks.Washington：IEEE Computer Society Press,2005：178-185.

[4]任秀麗,楊威,薛建生.一種基于測距的無線傳感網(wǎng)Sybil攻擊檢測方法[J].計(jì)算機(jī)應(yīng)用,2009,29(6)：1628-1631.

[5]BOUKERCHE A,OLIVEIR A H A,NAKAMURA E F,et al.Secure localization algorithmsfor wireless sensor networks [J].IEEE Communication Magazine,2008(4)：96-101.

[6]張起元.無線傳感器網(wǎng)絡(luò)虛假數(shù)據(jù)檢測排除機(jī)制研究[D].合肥：中國科學(xué)技術(shù)大學(xué),2010.

[7]葉阿勇.無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)安全定位[D].西安：西安電子科技大學(xué),2009.

[8]PRIYANTHA N B,CHAKR ABORTY A,BALAKRISHNAN H.The cricket location-support system[C]//STEERE D C,BAPTISTA A,PU C,et al.Proc.of the 6th Annual Int' l Conf.onMobile Computing and Networking.Boston：ACM Press,2000：58-66.