一種容忍惡意錨節(jié)點(diǎn)獨(dú)立攻擊的安全定位算法*

羅 臻，劉宏立，徐 琨

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

隨著無線通信技術(shù)、計(jì)算機(jī)技術(shù)以及網(wǎng)絡(luò)技術(shù)的快速進(jìn)步，無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks)得到了穩(wěn)定的發(fā)展，并獲得廣泛應(yīng)用，例如水下監(jiān)視［1］、軍事偵察、交通監(jiān)控［2］、環(huán)境監(jiān)測(cè)［3］、森林火災(zāi)探測(cè)以及事故搜救［4］等。準(zhǔn)確地知道傳感器節(jié)點(diǎn)的位置是這些應(yīng)用得以實(shí)現(xiàn)的基礎(chǔ)，國(guó)內(nèi)外研究者就此提出了很多種定位方法［5］，大多數(shù)方法依賴于一組信標(biāo)或錨節(jié)點(diǎn)的已知位置信息來確定剩余節(jié)點(diǎn)的位置。在這些方法中，錨節(jié)點(diǎn)發(fā)送包含自己位置的信標(biāo)信號(hào)，當(dāng)其他節(jié)點(diǎn)接收到這一信號(hào)時(shí)就可以估計(jì)出它到錨節(jié)點(diǎn)的距離。常用的距離度量物理量有以下幾種:接收信號(hào)強(qiáng)度(RSS)、到達(dá)時(shí)間(TOA)、到達(dá)時(shí)間差(TDoA)、到達(dá)角(AOA)和跳計(jì)數(shù)［6］。一旦定位節(jié)點(diǎn)接收到足夠的信標(biāo)信號(hào)，它們就能通過三角測(cè)量法或三邊測(cè)量法來確定自己的位置。然而這些定位方法都是假設(shè)傳感器網(wǎng)絡(luò)部署在非攻擊的環(huán)境中，但實(shí)際上，無線傳感器網(wǎng)絡(luò)經(jīng)常會(huì)被部署在惡意危險(xiǎn)的環(huán)境中，那么傳感器節(jié)點(diǎn)的位置信息就會(huì)遭受到各種類型的攻擊。在惡意危險(xiǎn)的環(huán)境中，攻擊者可能會(huì)希望阻止節(jié)點(diǎn)的準(zhǔn)確定位，以此來阻礙整個(gè)網(wǎng)絡(luò)的正常運(yùn)行。所以，需要設(shè)計(jì)能夠精確定位并對(duì)攻擊具有魯棒性的安全定位算法。同時(shí)，由于定位節(jié)點(diǎn)本身有限的計(jì)算能力和能量，這樣的安全定位算法也應(yīng)該盡可能少的耗費(fèi)資源。

位置驗(yàn)證作為安全定位的一種策略已在相關(guān)的文獻(xiàn)中有所體現(xiàn)。S.Capkun等人提出的使用移動(dòng)基站的位置驗(yàn)證方法和其他一些距離邊界協(xié)議能夠有效地抵御攻擊［7－8］。在惡意危險(xiǎn)環(huán)境中的安全定位問題同樣引起了人們的注意。文獻(xiàn)［9］中提出了一種改進(jìn)的DV-Hop算法，通過利用設(shè)計(jì)好的非線性公式來處理蟲洞攻擊導(dǎo)致的不合理跳數(shù)，減輕了攻擊的影響。文獻(xiàn)［10］中提出了一種安全定位算法，其結(jié)果符合大多數(shù)錨節(jié)點(diǎn)發(fā)送的信息。文中還提出一種基于投票的算法，從信號(hào)處理的角度來看，該算法與用于對(duì)象檢測(cè)的Hough變換有些類似［11］。在本文中，我們提出了一種計(jì)算簡(jiǎn)單的基于梯度下降法和異常檢測(cè)技術(shù)的迭代安全定位算法，算法中迭代更新的矢量解釋以及異常檢測(cè)技術(shù)與文獻(xiàn)［12］提出的定位算法和文獻(xiàn)［13］提出的尋找數(shù)據(jù)最小截平方和(LTS)的方法有相似之處。

1 無線傳感器網(wǎng)絡(luò)安全定位分析及建模

我們考慮基于Range-Based的無線傳感器網(wǎng)絡(luò)安全定位問題。設(shè)網(wǎng)絡(luò)中有m個(gè)錨節(jié)點(diǎn)A1，A2，…，Am，有 n個(gè)未知節(jié)點(diǎn) S1，S2，…，Sn。每個(gè)錨節(jié)點(diǎn)的位置已知，其位置為［xi，yi］T，i=1，2，…，m。未知節(jié)點(diǎn)S1的真實(shí)位置為L(zhǎng)=［x，y］T，與之通信的錨節(jié)點(diǎn)個(gè)數(shù)為q個(gè)，接收到的錨節(jié)點(diǎn)的位置信息為 Ii=［xi，yi］T，i=1，2，…，q，未知節(jié)點(diǎn) S1和錨節(jié)點(diǎn)之間距離的估計(jì)值為di。這些距離的估計(jì)值通常會(huì)帶有噪聲，我們?cè)O(shè)此噪聲為均值為0，方差為σ2的加性高斯噪聲。給定一組帶噪聲的測(cè)量值{(Ii，di)}，i=1，2，…，q，未知節(jié)點(diǎn)S1位置的估計(jì)值 ^L=［^x，^y］T可以通過用最小二乘法(LS)解以下超定方程組獲得:

惡意錨節(jié)點(diǎn) Aj在發(fā)送其位置 Ij=［xj，yj］T的時(shí)候，可能故意發(fā)送錯(cuò)誤的位置信息。在這樣的情況下，LS估計(jì)值 ^L=［^x，^y］T可能和真實(shí)位置 L=［x，y］T相差很遠(yuǎn)。因此，我們需要能夠容忍這種攻擊的安全定位算法。

不失一般性，我們假設(shè)每個(gè)惡意錨節(jié)點(diǎn)只改變距離di值，因?yàn)楦淖內(nèi)魏纹渌麉?shù)都可以轉(zhuǎn)化為等效的改變di值。我們假設(shè)每個(gè)惡意錨節(jié)點(diǎn)添加一個(gè)獨(dú)立均勻分布的干擾給距離的估計(jì)值di，并發(fā)送這些錯(cuò)誤信息給定位節(jié)點(diǎn)。設(shè)是定位節(jié)點(diǎn)和錨節(jié)點(diǎn)之間的實(shí)際距離。定義

其中φi是均值為0，方差為σ2a的獨(dú)立均勻分布隨機(jī)變量，表示惡意錨節(jié)點(diǎn)造成的干擾;ωi是均值為0，方差為σ2的加性高斯噪聲。定位節(jié)點(diǎn)S1從q個(gè)錨節(jié)點(diǎn)接收到測(cè)量值{(Ii，di)}，i=1，2，…，q，并使用這些測(cè)量值來確定其位置。

2 安全定位算法

在本章中，我們將提出一種結(jié)合梯度下降法和異常檢測(cè)技術(shù)的迭代安全定位算法。當(dāng)不存在惡意錨節(jié)點(diǎn)，測(cè)量噪聲是加性高斯噪聲的情況下，測(cè)量得到定位節(jié)點(diǎn)真實(shí)位置的概率密度函數(shù)為

則定位節(jié)點(diǎn)位置的最大似然估計(jì)為:

其對(duì)數(shù)似然函數(shù)為:

不考慮后面的2個(gè)常數(shù)項(xiàng)，其最大似然估計(jì)就是最小化下面的非線性函數(shù)。

即

其中，f(x，y)對(duì)應(yīng)于式(2)中的指數(shù)部分。因此，最大似然估計(jì)值^L等同于式(1)的最小二乘解。

我們首先采用迭代梯度下降法搜索LS解。算法開始時(shí)，隨機(jī)給出估計(jì)值的初始值^L(0)。在第k步迭代中，根據(jù)當(dāng)前估計(jì)值 ^L(k－1)的值，計(jì)算f(x，y)的梯度，然后向梯度的負(fù)方向移動(dòng)一步以更新估計(jì)值。設(shè)λ(k)表示當(dāng)前位置估計(jì)值的代價(jià)函數(shù)梯度的負(fù)值

其中▽(·)表示關(guān)于位置L的導(dǎo)數(shù)。則

其中γ(k)是第k次迭代的步長(zhǎng)，(λ(k))/(|λ(k)|)是梯度負(fù)方向的單位向量。那么

每次迭代都會(huì)得出一個(gè)新的估計(jì)值，這個(gè)估計(jì)值將更接近定位節(jié)點(diǎn)的真實(shí)位置。如前所述，由于惡意錨節(jié)點(diǎn)的存在，LS估計(jì)有較大的誤差。因此，一旦梯度下降法收斂到LS解，我們就進(jìn)入到異常檢測(cè)階段。

異常檢測(cè)階段:在實(shí)際中，各惡意錨節(jié)點(diǎn)造成的獨(dú)立干擾趨于平均，使得LS解接近真實(shí)位置。因此，當(dāng)定位節(jié)點(diǎn)位置的估計(jì)值接近LS解時(shí)，惡意錨節(jié)點(diǎn)產(chǎn)生的向量λi(k)將大于正常錨節(jié)點(diǎn)產(chǎn)生的向量。我們?cè)谠刑荻鹊幕A(chǔ)上排除掉模值較大的向量，并使用剩余的向量來計(jì)算新的梯度。

在式(3)中，每個(gè)錨節(jié)點(diǎn)對(duì)應(yīng)一個(gè)λi(k)，由于LS解接近真實(shí)位置，那些正常錨節(jié)點(diǎn)對(duì)應(yīng)的|λi(k)|較小，而惡意錨節(jié)點(diǎn)對(duì)應(yīng)的|λi(k)|較大，我們對(duì)所有|λi(k)|進(jìn)行排序，那么從某一個(gè)|λi(k)|開始，其大小比它前一個(gè)|λi－1(k)|有明顯的增加，當(dāng)這個(gè)增加值大于我們?cè)O(shè)定的差分閾值β時(shí)，我們就認(rèn)為其后的所有λi(k)是由惡意錨節(jié)點(diǎn)產(chǎn)生的，其作用是將位置估計(jì)值 ^L(k－1)=［^x(k－1)，^y(k－1)］T向遠(yuǎn)離真實(shí)位置 L=［x，y］T的方向拉動(dòng)，于是我們舍棄這些λi(k)，保留前面模值較小的λi(k)重新求和，生成新的梯度向量λ(k)，然后用新的梯度向量λ(k)進(jìn)一步進(jìn)行迭代計(jì)算出最終的估計(jì)值。如圖1所示，I1、I2為正常錨節(jié)點(diǎn)，I3為惡意錨節(jié)點(diǎn)，L(k－1)為異常檢測(cè)之前得到的位置估計(jì)值，λ1(k)、λ2(k)、λ3(k)是關(guān)于 I1、I2、I3的向量，由于 I3是惡意錨節(jié)點(diǎn)，定位節(jié)點(diǎn)估計(jì)的距離d3和其實(shí)際的距離差別較大，由此產(chǎn)生的|λ3(k)|將大于由正常錨節(jié)點(diǎn) I1、I2產(chǎn)生的|λ1(k)|、|λ2(k)|，于是我們可以利用這個(gè)特性，濾除掉I3產(chǎn)生的攻擊。

圖1 異常檢測(cè)示意圖

由上可知，本算法利用梯度模的大小來濾除惡意錨節(jié)點(diǎn)產(chǎn)生的攻擊，但實(shí)際上梯度模的絕對(duì)大小并不能衡量錨節(jié)點(diǎn)是否是惡意的。由式(3)可知，梯度模的絕對(duì)大小和錨節(jié)點(diǎn)的位置，每一步迭代的結(jié)果以及所使用的測(cè)距方法有關(guān);迭代次數(shù)越多，迭代結(jié)果越精確，測(cè)量噪聲越小，那么梯度模的大小就越小。區(qū)分惡意錨節(jié)點(diǎn)的關(guān)鍵在于梯度模的相對(duì)大小，只有當(dāng)相對(duì)大小超過差分閾值β時(shí)，算法才會(huì)認(rèn)為存在惡意錨節(jié)點(diǎn)并濾除掉。

3 算法仿真及性能分析

我們通過仿真對(duì)本文提出的算法與LS算法、LMdS算法和投票算法進(jìn)行了比較。假設(shè)20個(gè)錨節(jié)點(diǎn)隨機(jī)部署在一個(gè)尺寸為100 m×100 m的區(qū)域中，加性高斯噪聲的標(biāo)準(zhǔn)差為σ=1 m。對(duì)于LMdS算法，子集個(gè)數(shù)和每個(gè)子集中的節(jié)點(diǎn)數(shù)分別為M1=20和n=4。對(duì)于基于投票的算法，每個(gè)小格的尺寸為1 m×1 m，所以n1=100。對(duì)于本文提出的算法，差分閾值β選擇不恰當(dāng)就可能導(dǎo)致算法不能濾除掉所有的惡意錨節(jié)點(diǎn)，或者在濾除掉的節(jié)點(diǎn)中包含有正常錨節(jié)點(diǎn)，在這里我們選取β=1，此值是通過在0.5到2之間多次實(shí)驗(yàn)所得出的最佳值，迭代次數(shù)M=100。進(jìn)入異常檢測(cè)階段的門限閾值為0.9。得到的結(jié)果均為500次仿真得出的平均值。我們采用以下線性遞減的步長(zhǎng)［14］:

同時(shí)，初始迭代位置的選擇也會(huì)影響算法的收斂情況。因?yàn)樵趯?shí)際中，很難知道定位節(jié)點(diǎn)位置的先驗(yàn)知識(shí)，所以初始位置通常選擇特殊點(diǎn)，在這里我們選擇(0，0)作為初始位置。當(dāng)選擇的初始位置接近真實(shí)位置時(shí)，算法就會(huì)收斂得較快，當(dāng)選擇的初始位置離真實(shí)位置較遠(yuǎn)時(shí)，算法就會(huì)收斂得較慢，迭代次數(shù)就會(huì)較多。

仿真結(jié)果如圖。其中，圖2(a)為當(dāng)惡意錨節(jié)點(diǎn)數(shù)占20%時(shí)，定位誤差與攻擊強(qiáng)度σa之間的函數(shù)關(guān)系;圖2(b)為當(dāng)惡意錨節(jié)點(diǎn)數(shù)占60%時(shí)，定位誤差與攻擊強(qiáng)度σa之間的函數(shù)關(guān)系。

圖2 攻擊條件下的定位算法比較

從圖2(a)中我們可以看到，當(dāng)惡意錨節(jié)點(diǎn)數(shù)小于50%時(shí)，隨著攻擊強(qiáng)度的增加，LS算法的定位誤差成線性增長(zhǎng)，其他3種算法的定位誤差基本不變，而本文提出的算法優(yōu)于其他兩種算法;當(dāng)惡意錨節(jié)點(diǎn)數(shù)達(dá)到60%時(shí)，LMdS算法和投票算法的定位誤差隨著攻擊強(qiáng)度的增加有所增大，而本文提出的算法仍然能保持一個(gè)較理想的定位精度。仿真表明，本文提出的算法對(duì)獨(dú)立的攻擊具有較好的魯棒性，其平均定位誤差受攻擊強(qiáng)度σ2a影響較小。

盡管平均定位誤差是衡量算法是否有用的一個(gè)指標(biāo)，但更重要的可能是算法是否能夠定位到節(jié)點(diǎn)的真實(shí)位置。為了從不同的角度衡量算法的準(zhǔn)確性，我們比較了其定位到真實(shí)位置的概率。由于噪聲、步長(zhǎng)等的影響，我們決定如果最終的估計(jì)距真實(shí)位置在σ2m以內(nèi)，就認(rèn)為該算法定位到了正確的位置。圖3給出了各算法定位到真實(shí)位置的概率與惡意錨節(jié)點(diǎn)數(shù)目的函數(shù)關(guān)系。我們可以看到，當(dāng)惡意錨節(jié)點(diǎn)數(shù)目小于50%時(shí)，LS算法的準(zhǔn)確率最低，但基本能保持在75%以上。當(dāng)惡意錨節(jié)點(diǎn)數(shù)目超過50%時(shí)，其他幾種算法的準(zhǔn)確率快速下降，而本文提出的算法比其他幾種定位算法的準(zhǔn)確率要高。

圖3 攻擊條件下不同算法收斂到正確估計(jì)的概率(σa=6 m)

與此同時(shí)，我們提出的算法的計(jì)算復(fù)雜度與惡意錨節(jié)點(diǎn)的數(shù)目沒有任何關(guān)系，它只隨迭代次數(shù)的增加成線性增長(zhǎng)，在每一步迭代中，只需要計(jì)算當(dāng)前估計(jì)值與各錨節(jié)點(diǎn)之間的距離。迭代步長(zhǎng)的選擇對(duì)算法的收斂速度有一定的影響，選擇合適的步長(zhǎng)能夠縮短算法的收斂時(shí)間。

4 結(jié)論

本文提出了一種用于無線傳感器網(wǎng)絡(luò)的安全定位算法。該算法結(jié)合梯度下降法和異常檢測(cè)技術(shù)，通過濾除掉不符合條件的測(cè)量數(shù)據(jù)來確定節(jié)點(diǎn)的位置。我們通過仿真證明了該算法的有效性。仿真結(jié)果表明，在惡意危險(xiǎn)的環(huán)境下，本文提出的方法比現(xiàn)有方法具有更高的定位精度，且效果較為明顯。

［1］ Cayirci E，Tezcan H，Dogan Y，et al.Wireless Sensor Networks for Underwater Surveillance Systems［J］.Ad Hoc Networks，2006，4(4):431－446.

［2］ Szewczyk R，Osterweil E，Polastre J，et al.Habitat Monitoring with Sensor Networks［J］.Communications of the ACM，2004，47(6):34－40.

［3］ 孫啟永，張文，李海波，等.基于微電極陣列和無線傳感器網(wǎng)絡(luò)的水環(huán)境重金屬檢測(cè)系統(tǒng)研究［J］.傳感技術(shù)學(xué)報(bào)，2013，26(7):907－911.

［4］ 段翠翠，王瑞榮，王建中，等.基于無線傳感器網(wǎng)絡(luò)的高危生產(chǎn)區(qū)人員定位系統(tǒng)［J］.傳感技術(shù)學(xué)報(bào)，2012，25(11):1599－1601.

［5］ 彭宇，王丹.無線傳感器網(wǎng)絡(luò)定位技術(shù)綜述［J］.電子測(cè)量與儀器學(xué)報(bào)，2011，25(5):389－399.

［6］ Niculescu D，Nath B.DV Based Positioning in Ad-Hoc Networks［J］.Telecommunication Systems，2003，22(1－4):267－280.

［7］ Capkun S，Rasmussen K，Cagalj M，et al.Secure Location Verification with Hidden and Mobile Base Stations［J］.IEEE Transactions on Mobile Computing，2008，7(4):470－483.

［8］ Capkun S，Hubaux J P.Secure Positioning in Wireless Networks［J］.IEEE Journal on Selected Areas in Communications，2006，24(2):221－232.

［9］ Liu D，Ning P，Liu A，et al.Attack-Resistant Location Estimation in Wireless Sensor Networks［J］.ACM Transactions on Information and System Security，2008，11(4):1－39.

［10］劉彩霞，黃廷磊.WSN中抵御蟲洞攻擊的改進(jìn)的DV-Hop算法研究［J］.傳感技術(shù)學(xué)報(bào)，2011，24(10):1473－1478.

［11］ Barinova O，Lempitsky V，Kholi P.On Detection of Multiple Object Instances Using Hough Transforms［J］.IEEE Transactions on Pattern A-nalysis and Machine Intelligence，2012，34(9):1773－1784.

［12］ Takizawa Y，Davis P，Kawai M，et al.Self-Organizing Location Estimation Method Using Received Signal Strength［J］.IEICE Transactions on Communications，2006，B89－B(10):2687－2695.

［13］ Rousseeuw P，Driessen K.Computing LTS Regression for Large Data Sets［J］.Data Mining and Knowledge Discovery，2006，12(1):29－45.

［14］ Chang D，Chu F.A New Variable Tap-Length and Step-Size FxLMS Algorithm［J］.IEEE Signal Processing Letters，2013，20(11):1122－1125.