徐琨,劉宏立,詹杰,馬子驥
(1.湖南大學電氣與信息工程學院,湖南 長沙 410082;2.湖南科技大學物電學院,湖南 湘潭 411201)
容忍惡意攻擊的無線傳感網絡安全定位算法
徐琨1,劉宏立1,詹杰2,馬子驥1
(1.湖南大學電氣與信息工程學院,湖南 長沙 410082;2.湖南科技大學物電學院,湖南 湘潭 411201)
針對無線傳感網絡中惡意攻擊會篡改信標節點發射強度破壞節點準確定位的問題,提出了一種頑健的基于半定規劃松弛的安全定位算法(RSRSL)。該算法將發射功率作為一個未知的變量,分別基于單目標傳感網絡和多目標傳感網絡,建立了相應的安全定位概率模型。通過將非線性非凸的定位問題轉化為易于求解的半定規劃問題,實現對網絡中普通節點的安全定位,并分析了RSRSL算法的計算復雜度。通過仿真和實測實驗對RSRSL算法進行驗證,結果表明,在存在惡意攻擊的環境中,RSRSL算法要明顯優于已有的定位算法,具有較高的定位精度。
無線傳感網絡;安全定位;接收信號強度;發射功率;半定規劃
節點定位是無線傳感網絡(WSN,wireless sensor networks)的關鍵技術之一,是實現WSN其他功能的基礎,一個不知道自己位置信息的節點在網絡中沒有任何作用[1]。在WSN中,一部分節點的位置可以通過人工預設或裝備全球定位系統[2](GPS,global positioning system)提前獲得,一般稱為信標節點(BN,beacon node);但是大部分節點的位置是未知的,一般稱為普通節點(SN,sensor node)。普通節點需要在網絡部署之初或中途加入網絡時利用信標節點進行定位,常用的定位技術有基于到達時間[3](ToA,time of arrival)、到達時間差[4](TDoA,time difference of arrival)、到達角度[5](AoA,angle of arrival)和接收信號強度[6](RSSI,received signal strength indicator)等方法。其中,基于RSSI測量值的定位方法由于實現簡單、成本低廉以及不需要增加額外的硬件設備被廣泛地應用到WSN定位中[7]。
基于RSSI的定位方法主要依賴接收到的信號強度值實現定位,信號強度的不確定會對定位性能產生嚴重的影響。目前有很多基于RSSI的定位算法,如最大似然估計法[8](ML,maximum likelihood estimator)、線性最小二乘法[9](LLS,linear least squares)和凸優化[10](convex optimization)等方法。這些算法雖然能夠得到較好的定位性能,但都沒有考慮存在惡意攻擊的情況。WSN一般部署在無人值守的區域,網絡中無線信號的廣播特性使信號強度很容易受到攻擊者的各種惡意攻擊。攻擊者通過俘獲信標節點發起偽造插入[11]或重放[12]等惡意攻擊,虛增或虛減信標節點的發射功率值,或者采用阻擋、反射等物理攻擊手段對信號進行干擾,削弱或增強信號強度,破壞網絡中普通節點的正常定位,進而導致整個網絡功能失效。由于能耗和成本的限制,傳統網絡的安全技術不能直接移植到WSN中。文獻[13]提出了一種最小中值二乘算法(LMdS,least median square),通過將節點劃分為多個子集過濾惡意信標節點,并利用LLS實現對節點的安全定位,但該算法的計算復雜度高。文獻[14]將網絡劃分為網格,提出了一種過濾惡意信標節點的基于投票制(voting)的安全定位算法,通過采用迭代求精的方法實現對節點的定位,但這種方法需要將網絡劃分為網格,網格的大小和數量較多時,算法的計算量太大,計算復雜度高。文獻[15]提出了一種基于梯度下降的安全定位算法,通過測量一致性原理過濾惡意攻擊節點,實現對網絡節點的定位。文獻[16]提出了一種基于松弛標記方法的安全定位算法,通過檢測分組內節點的行為,過濾惡意攻擊節點,并證明了網絡中惡意節點比例和定位精度之間的關系,當惡意節點的總數小于等于時,采用有效的定位算法可以實現準確的定位。文獻[17]提出了一種分布式的基于RSSI的DPC安全定位算法,采用計算和測量一致性的原理對網絡中的惡意節點進行過濾,基于簇平面的思想實現安全定位。上述算法都將安全定位過程機械地分為過濾惡意信標節點和安全定位2個階段,增加了計算的時耗和復雜度。
針對惡意節點攻擊時會虛增或虛減發射功率大小導致定位失效的問題,分別基于單目標的無線傳感網絡和多目標的無線傳感網絡,本文提出了一種頑健的基于半定規劃松弛的安全定位算法(RSRSL,robust semidefinite relaxation secure localization algorithm)。該算法是一種基于頑健計算的安全定位算法,定位過程中無需過濾惡意信標節點。它不僅利用普通節點和信標節點之間的RSSI測量值,而且利用普通節點與其他普通節點之間的RSSI測量值進行位置估算。首先,建立了基于最大似然估計的定位模型;其次,針對該模型沒有考慮惡意攻擊會篡改發射功率的問題,提出了一種新的安全定位模型,該模型將發射功率表示成一個未知的變量,在定位過程中和位置信息一起估算,解決存在攻擊時所導致的定位失效問題;然后,針對提出模型是一個復雜的非線性非凸的全局優化問題而難以求解的特點,設計了一種新的半定規劃(SDP, semidefinite programming)算法,并分析了算法的復雜度;最后通過仿真和實測實驗,對提出的模型和算法進行驗證。
基于RSSI測量值的定位算法的主要原理是依靠信號強度的路徑衰減和物理距離之間的關系,求出節點之間的距離,從而實現對普通節點的定位。普通節點僅通過接收到的RSSI值實現對自身的定位,定位的精度嚴重依賴信標節點的發射功率。當攻擊者通過重放或其他物理手段惡意篡改信標節點的發射功率后,會導致嚴重的定位錯誤,破壞網絡中普通節點的定位。首先,對只有一個普通節點,m個信標節點的單目標網絡進行分析,建立對應的安全定位模型;然后擴展到普遍存在的n個普通節點和m個信標節點的多目標網絡,建立對應的安全定位模型。
2.1 單目標網絡安全模型
首先分析只有一個普通節點時的系統模型,在這種情況下,只需考慮信標節點發送的RSSI值。考慮一個分布在二維空間的傳感網絡,它由1個普通節點和m個信標節點組成,每個節點都有唯一的ID,普通節點與信標節點共享一個預設密鑰,實現節點間的安全通信。普通節點的位置未知,;信標節點的位置已知,。表示網絡中能夠與普通節點通信的信標節點集合,普通節點接收到的第j個信標節點的接收信號強度用對數正態分布模型表示為

其中,Pj表示距離為dj時的接收信號強度值,單位是dBm;P0表示參考距離為d0時的接收信號強度值,一般取d0為1 m;np表示路徑衰減因子;表示普通節點和第j個信標節點之間的歐氏距離;vj表示噪聲干擾,它是一個均值為0,方差為的高斯隨機變量。
在沒有攻擊的情況下,式(1)可以很好地描述網絡中RSSI和物理距離之間的函數關系,但是在存在惡意攻擊的環境中,攻擊者可以采用重放攻擊或阻擋、反射等物理攻擊手段虛增或虛減攻擊節點的發射功率值,這些攻擊都會導致接收節點接收到的RSSI不準確,導致嚴重的定位錯誤。為了緩解惡意信標節點篡改發射功率的影響,將式(1)中的發射功率看成一個未知的變量,在計算過程中,它需要和未知節點的坐標一起被估算。因此,式(1)中將有3個需要估算的未知變量,采用加權最大似然估計模型表示對應的安全概率模型。

2.2 多目標網絡安全模型
接下來考慮一個由n個普通節點和m個信標節點組成的網絡,普通節點不僅可以和信標節點進行通信,而且能和其他普通節點進行通信,所有節點共享一個預設密鑰,實現節點間的安全通信。為了提高定位性能,普通節點定位時同時利用從信標節點測量到的RSSI值和從其他普通節點測量到的RSSI值一起估算自身位置。普通節點的位置未知,。表示普通節點的集合,表示信標節點的集合。表示能和普通節點i通信的其他普通節點集合;表示能和普通節點i通信的信標節點集合。普通節點接收到的信號強度用對數正態分布模型表示為

其中,Pij表示普通節點在距離為dij時的接收信號強度;P0j表示普通節點在距離為1 m處的參考接收信號強度;dij表示普通節點i和信標節點j以及其他普通節點的歐氏距離,當j∈Bi時,;當j∈Ai時,;vij表示噪聲干擾,它是一個均值為0、方差為的高斯隨機變量。
同樣,當遇到惡意攻擊時,可以將發射功率看成未知變量,用最大似然估計模型表示出對應的安全概率模型

接下來分析如何求出安全模型式(2)和式(4)的全局最優解。針對式(2)和式(4)非線性、難于求解的問題,運用凸優化的半定規劃松弛理論分別設計了式(2)和式(4)的求解算法,將對應的最大似然估計問題轉化為半定規劃問題進行求解。半定規劃所具有的局部最優就是全局最優的特性,使其在求解過程中不會存在局部最優和鞍點的問題。下面,詳細描述半定規劃松弛的求解算法。
3.1 單目標網絡安全定位算法
式(1)中的距離dj和功率P0都是未知變量,為了便于求解,通過取對數和對等式兩邊移位等操作,可以將其表示為



式(7)表示的定位問題和式(2)描述的問題相比雖然得到了一定的平滑,但是仍然是一個非線性非凸的優化問題,求解過程復雜,計算復雜度高。定義,將式(7)進一步轉化為以下形式

式(8)仍然表示一個非線性的優化問題。接下來,利用凸優化的松弛技術,將式(8)轉化為標準的凸優化函數。將z=xTx松弛為線性矩陣不等式的形式,使讓其成為一個線性形式,使求式(8)的最小化問題轉化為求解半定規劃問題。

采用如內點法的優化算法可以較簡單地求出式(9)的最優解,而且,由于半定規劃的特性,可以確保式(9)能在全局最優解處收斂。
3.2 多目標網絡安全定位算法
對于存在n個普通節點的情況,可以通過和上述描述的類似方法進行求解,通過對其進行一階泰勒級數展開并移項重新整理后,得到一個如同式(8)平滑的最大似然估計概率模型,如式(10)所示。

其中,q=[q1,q2,…,qm]T,和求解只有一個普通節點的方法類似,可以將式(10)采用松弛技術將其轉化為求凸優化的目標函數問題。令表示普通節點坐標的矩陣,引入一個輔助矩陣變量Z=XTX,其中,表示矩陣Z的第(i,j)個元素。通過采用松弛技術,可以將式(10)轉化為標準的SDP形式

其中,ei表示一個m×1的向量,它的第i個元素為1,其他的元素都為0。當式(11)的目標函數取得最小值時,即存在X和Z,可以使Z=XTX成立,則式(11)和式(10)的解是一致的。式(9)和式(11)所描述的半定規劃問題可以通過很多已知的算法很容易地求出對應的最優解,如內點法。在Matlab仿真中,可以采用標準的SDP解析工具SeDuMi或SDPT3直接求解對應的SDP問題。
基于浮點數計算的總數或每秒浮點計算評估RSRSL算法的計算復雜度,并和ML、LLS、LMdS、投票法的計算復雜度進行對比。假設在實數域中,每個加減乘除操作以及平方根操作可以通過一次浮點計算完成。推導RSRSL算法在多目標網絡中的計算復雜度,單目標網絡是多目標網絡在n=1時的特殊情況。其中,n表示網絡中普通節點的總數;m表示信標節點的總數;表示網絡的連通數。當傳感網絡是全連通圖時,。對于一個標準的半定規劃問題,目標函數中包括一個向量和m+1個對稱矩陣。可以采用如內點法之類的迭代優化算法進行求解,對于每次迭代過程,最壞的情況下,求出半定規劃最優解的計算復雜度是。根據求解的精度要求,迭代的次數為,其中,?表示求解半定規劃優化解需要達到的精度。針對RSRSL算法,只考慮算法中占主導地位的計算元素,。RSRSL算法的計算復雜度為。當傳感網絡是全連通圖時,RSRSL算法和其他定位算法的計算復雜度如表1所示,其中,k表示迭代次數;m1表示網絡中需要劃分的子集數目;n1表示網絡部署區域劃分網格的數目。

表1 不同定位算法的計算復雜度(全連通網絡)
接下來對比RSRSL算法與ML、LLS、LMdS和投票法的計算復雜度。對于ML算法,采用牛頓迭代法進行求解時,它的精度主要依賴于初始值的選取和需要的精度。LMdS算法需要將網絡中的節點分成m1個子集,計算復雜度隨惡意節點的增多而急劇變大。投票法的定位精度依賴于網絡部署區域的網格大小,計算復雜度也與網絡中網格的數量有關。網絡部署區域越大,劃分的網格越小,網格數量越多,計算復雜度越高。而從上述對RSRSL算法的計算復雜度分析可以看出,RSRSL算法與網絡部署區域大小沒有關系,與惡意節點的數目也沒有關系。對于一個包含較多普通節點的密集網絡,RSRSL算法和ML算法在每次迭代的計算復雜度是類似的,但是要大于LLS的計算復雜度。但是對于一個網絡只包含較少普通節點的網絡,如只有10個普通節點的網絡,3種算法每次迭代的計算復雜度是近似相同的。
為了驗證RSRSL算法的定位性能,分別基于仿真實驗和實測實驗對RSRSL算法進行分析,并將其與已有的安全定位算法進行對比。采用均方根誤差來表示定位誤差:,其中,表示估算得出的普通節點坐標,表示普通節點的真實坐標。
5.1 仿真實驗
在一個60 m×60 m的矩形區域隨機部署30個信標節點和50個普通節點,每個節點的通信半徑為100 m。在一臺處理器為Intel Core i5-4590,主頻3.3 GHz,內存16 GB,1 600 MHz DDR3的臺式機上對所有算法進行仿真,對每一種算法進行1 000次仿真實驗。對于LMdS算法,設置子集的數量m1=20,每個子集中節點的個數n=4。對于投票法,設置網格的大小為1 m×1 m,即n1=60。利用CVX工具箱中的SeDuMi解析器對RSRSL算法進行求解。
圖1所示為不同攻擊強度下各種定位算法的定位性能。圖1(a)表示有20%的信標節點遭受惡意攻擊,發射信號強度被惡意篡改后,測量噪聲標準差和定位精度之間的關系。從圖中可以看出,當攻擊強度較低時,LLS的定位誤差最大,而且定位誤差隨著測量噪聲的增加急劇變大。RSRSL算法和LMdS算法、投票法的定位誤差較小,具有相似的定位性能,而且3種算法的定位誤差不會隨著測量噪聲的增加發生大的波動。圖1(b)表示有50%的信標節點遭受攻擊時,測量噪聲標準差和定位精度之間的關系。當網絡中的惡意攻擊節點增多時,LMdS算法會導致嚴重的定位誤差,但是RSRSL算法仍能表現出較好的定位性能,因為RSRSL算法將發射功率看成一個未知變量參與定位計算,可以有效地緩減惡意節點篡改發射功率對定位的影響。投票法也表現了很好的定位性能,由于網格點的不連續性,它的定位誤差要略微高于RSRSL算法,而且投票法的定位精度受到網格大小的影響,當將網格劃分的更小時,會帶來較低的定位誤差,但是會帶來巨大的計算復雜度,并需要很高的內存空間。

圖1 不同攻擊強度下各種算法的定位誤差
圖2所示為不同攻擊強度下,噪聲標準差σ=3dB時不同算法準確估算出正確位置的概率。由于存在測量噪聲和有限的網格大小,本文設定當估算位置在真實位置的αm范圍內時,即認為算法收斂到正確位置。當惡意信標節點的數量小于50%時,除了LLS算法,其他的安全定位算法都有較好的定位性能,有 90%的概率使估算的位置收斂于正確位置。當惡意信標節點的數量大于50%時,所有的定位算法的定位性能都降低,但RSRSL算法明顯優于其他算法。如當惡意信標節點的數量為60%或70%時,RSRSL算法收斂于正確位置的概率要比其他算法高10%左右。

圖2 不同攻擊強度下各種算法準確定位的概率
圖3所示為當有20%的信標節點遭受惡意攻擊時,普通節點的鄰居節點數目對定位誤差的影響。從圖中可以看出,當鄰居節點的數量慢慢變大時,即網絡的連通度增大時,所有算法的定位性能都得到了顯著的提高。當普通節點周圍的鄰居節點較少時,LLS和ML算法具有較高的定位誤差,其中,LLS的定位誤差最大,RSRSL算法的定位性要遠遠優于LLS和ML算法。雖然隨著鄰居節點的增加,LLS和ML的定位誤差有了顯著的降低,但是RSRSL算法仍然要明顯優于ML和LLS算法。

圖3 鄰居節點數對定位誤差的影響
5.2 實測實驗
在湖南大學電氣學院的實驗室對RSRSL算法進行驗證,實測環境是一個6.4 m×4.2 m的實驗室,室內有桌子、椅子和電腦等設施,在室內部署了12個信標節點、5個普通節點和1個中心節點,中心節點通過串口和上位機連接。每個節點都基于CC2430芯片,天線都是波長的全向天線,所有節點通過ZigBee協議組成一個傳感網絡,每個節點的有效通信半徑為10 m。通過調整信標節點的發射功率大小或設置障礙物來模擬惡意攻擊環境。在進行實驗之前,利用訓練測試數據提前計算出當前環境中的路徑衰減系數,設計了100組實驗來驗證RSRSL算法的定位精度。
圖4描述了在有20%的信標節點遭受惡意攻擊時,不同算法定位誤差隨測量噪聲標準差變化的情況。圖4(a)和圖4(b)分別表示網絡中有1個普通節點和5個普通節點時的定位性能。雖然網絡中部署的普通節點數目不同,但所有算法的定位性能都受測量噪聲標準差的影響,定位誤差隨著測量噪聲的增大而提高。其中,LLS算法受測量噪聲變化的影響是最大的,而且隨著測量噪聲的逐漸增大,定位誤差的變化越來越大。和仿真實驗相比,實測實驗中所有算法的定位性能要稍微弱于仿真的定位性能,這是因為在實測實驗中RSSI會受到多徑效應以及室內其他無線信號的影響。但是和仿真實驗的結果類似,RSRSL算法的定位性能在實測環境中也要明顯優于傳統的定位算法。

圖4 存在20%惡意信標節點下不同算法的定位誤差
在攻擊環境中,如何準確、安全地確定WSN節點的位置是目前的研究熱點。針對重放、偽造插入等外部攻擊會惡意篡改信標節點發射功率的問題,提出了一種新的無需過濾惡意信標節點的安全定位算法RSRSL。該算法考慮發射功率會被惡意篡改,不僅利用信標節點的RSSI測量值,而且利用普通節點的RSSI測量值建立了對應的安全定位模型。通過將非線性的定位問題轉化為半定規劃問題估算出普通節點的位置,并在數學上分析了RSRSL算法的計算復雜度。仿真和實測實驗表明,在存在攻擊的環境中,RSRSL算法能夠實現安全定位,定位性能要明顯優于已有的定位算法。
[1]CAN Z,DEMIRBAS M.A survey on in-network querying and tracking services for wireless sensor networks[J].Ad Hoc Networks,2013,11(1):596-610.
[2]ZHAO J,XI W,HE Y,et al.Localization of wireless sensor networks in the wild:pursuit of ranging quality[J].IEEE/ACM Transactions on Networking (TON),2013,21(1):311-323.
[3]HUANG J,XUE Y,YANG L.An efficient closed-form solution for joint synchronization and localization using TOA[J].Future Generation Computer Systems,2013,29(3):776-781.
[4]GHOLAMI M R,GEZICI S,STROM E G.TDOA based positioning in the presence of unknown clock skew[J].IEEE Transactions on Communications,2013,61(6):2522-2534.
[5]MALAJNER M,PLANINSIC P,GLEICH D.Angle of arrival estimation using RSSI and omnidirectional rotatable antennas[J].Sensors Journal,IEEE,2012,12(6):1950-1957.
[6]SAHU P K,WU E H K,SAHOO J.DuRT:dual RSSI trend based localization for wireless sensor networks[J].Sensors Journal,IEEE,2013,13(8):3115-3123.
[7]JIANG J A,ZHENG X Y,CHEN Y F,et al.A distributed RSS-based localization using a dynamic circle expanding mechanism[J].Sensors Journal,IEEE,2013,13(10):3754-3766.
[8]ZEYTINCI M B,SARI V,HARMANCI F K,et al.Location estimation using RSS measurements with unknown path loss exponents[J].EURASIP Journal on Wireless Communications and Networking,2013(1):1-14.
[9]SO H C,LIN L.Linear least squares approach for accurate received signal strength based source localization[J].IEEE Transactions on Signal Processing,2011,59(8):4035-4040.
[10]WANG C,QI F,SHI G,et al.A linear combination-based weighted least square approach for target localization with noisy range measurements[J].Signal Processing,2014,94:202-211.
[11]WEI Y,GUAN Y.Lightweight location verification algorithms for wireless sensor networks[J].IEEE Transactions on Parallel and Distributed Systems,2013,24(5):938-950.
[12]HE D,CUI L,HUANG H,et al.Design and verification of enhanced secure localization scheme in wireless sensor networks[J].IEEE Transactions on Parallel and Distributed Systems,2009,20(7):1050-1058.
[13]LI Z,TRAPPE W,ZHANG Y,et al.Robust statistical methods for securing wireless localization in sensor networks[C]//The 4th International Symposium on Information Processing in Sensor Networks.Los Angeles,USA,2005:91-98.
[14]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.
[15]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.
[16]ZHONG S,JADLIWALA M,UPADHYAYA S,et al.Towards a theory of robust localization against malicious beacon nodes[C]//The 27th Conference on Computer Communications.Phoenix,USA,2008:1391-1399.
[17]詹杰,劉宏立 ,劉大為,等.無線傳感器網絡中DPC安全定位算法研究[J].通信學報,2011,32(12):8-17.ZHAN J,LIU H L,LIU D W,et al.Research on secure DPC localization algorithm of WSN[J].Journal on Communications,2011,32(12):8-17.

徐琨(1979-),男,湖南常德人,湖南大學博士生,主要研究方向為無線傳感器網絡定位與追蹤、移動互聯等。

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

詹杰(1973-),男,湖南常德人,博士,湖南科技大學副教授,主要研究方向為無線傳感網絡定位、移動通信等。

馬子驥(1978-),男,湖南長沙人,博士,湖南大學講師,主要研究方向為下一代智能通信網絡、數字信號處理等。
Malicious attack-resistant secure localization algorithm for wireless sensor network
XU Kun1,LIU Hong-li1,ZHAN Jie2,MA Zi-ji1
(1.College of Electrical and Information Engineering,Hunan University,Changsha 410082,China;2.College of Physics and Electronic Science,Hunan University of Science and Technology,Xiangtan 411201,China)
In hostile environments,localization often suffers from malicious attacks that may distort transmit power and degrade positioning accuracy significantly for wireless sensor network.A robust semidefinite relaxation secure localization algorithm RSRSL was proposed to improve the location accuracy against malicious attacks.On the assumption of unknown transmit power,which is undoubtedly approximate to the fact of WSN,a novel secure location probability model was introduced for single-target and multi-target sensor networks,respectively.Taking the computational complexity of RSRSL into account,the nonlinear and non-convex optimization problem was simplified into a semidefinite programming problem.According to the results from both simulations and field experiments,it is clearly demonstrated that the proposed RSRSL has better performance on location accuracy,in contrast to the conventional localization algorithms.
wireless sensor network,security localization,
signal strength indicator,transmit power,semidefinite programming
s:The National Natural Science Foundation of China(No.61172089),The Central State-owned Capital Management and Budget Project of China (No.[2013]470),The National Doctoral Fund of China(2014M562100),The Science and Technology Program Foundation of Hunan Province(No.2014WK3001)
TP393
A
10.11959/j.issn.1000-436x.2016276
2016-07-29;
2016-11-21
國家自然科學面上基金資助項目(No.61172089);中央國有資本經營預算支出基金資助項目(No.[2013]470);博士后面上基金資助項目(No.2014M562100);湖南省科技廳基金資助項目(No.2014WK3001)