一種容忍惡意錨節點獨立攻擊的安全定位算法*

羅 臻，劉宏立，徐 琨

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

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

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

1 無線傳感器網絡安全定位分析及建模

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

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

不失一般性，我們假設每個惡意錨節點只改變距離di值，因為改變任何其他參數都可以轉化為等效的改變di值。我們假設每個惡意錨節點添加一個獨立均勻分布的干擾給距離的估計值di，并發送這些錯誤信息給定位節點。設是定位節點和錨節點之間的實際距離。定義

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

2 安全定位算法

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

則定位節點位置的最大似然估計為:

其對數似然函數為:

不考慮后面的2個常數項，其最大似然估計就是最小化下面的非線性函數。

即

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

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

其中▽(·)表示關于位置L的導數。則

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

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

異常檢測階段:在實際中，各惡意錨節點造成的獨立干擾趨于平均，使得LS解接近真實位置。因此，當定位節點位置的估計值接近LS解時，惡意錨節點產生的向量λi(k)將大于正常錨節點產生的向量。我們在原有梯度的基礎上排除掉模值較大的向量，并使用剩余的向量來計算新的梯度。

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

圖1 異常檢測示意圖

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

3 算法仿真及性能分析

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

同時，初始迭代位置的選擇也會影響算法的收斂情況。因為在實際中，很難知道定位節點位置的先驗知識，所以初始位置通常選擇特殊點，在這里我們選擇(0，0)作為初始位置。當選擇的初始位置接近真實位置時，算法就會收斂得較快，當選擇的初始位置離真實位置較遠時，算法就會收斂得較慢，迭代次數就會較多。

仿真結果如圖。其中，圖2(a)為當惡意錨節點數占20%時，定位誤差與攻擊強度σa之間的函數關系;圖2(b)為當惡意錨節點數占60%時，定位誤差與攻擊強度σa之間的函數關系。

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

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

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

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

與此同時，我們提出的算法的計算復雜度與惡意錨節點的數目沒有任何關系，它只隨迭代次數的增加成線性增長，在每一步迭代中，只需要計算當前估計值與各錨節點之間的距離。迭代步長的選擇對算法的收斂速度有一定的影響，選擇合適的步長能夠縮短算法的收斂時間。

4 結論

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

［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］ 孫啟永，張文，李海波，等.基于微電極陣列和無線傳感器網絡的水環境重金屬檢測系統研究［J］.傳感技術學報，2013，26(7):907－911.

［4］ 段翠翠，王瑞榮，王建中，等.基于無線傳感器網絡的高危生產區人員定位系統［J］.傳感技術學報，2012，25(11):1599－1601.

［5］ 彭宇，王丹.無線傳感器網絡定位技術綜述［J］.電子測量與儀器學報，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中抵御蟲洞攻擊的改進的DV-Hop算法研究［J］.傳感技術學報，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.