一種基于迭代投票的無線傳感器網絡安全定位算法*

張 品，毛文敏，徐 靜

(杭州電子科技大學 通信工程學院，浙江 杭州310018)

0 引 言

無線傳感器網絡的眾多應用，如，環境監測、目標追蹤、網絡路由等都是基于網絡傳感器節點的位置信息［1］。無線傳感器網絡常處于敵對環境中，無線傳感器的位置信息極易受到攻擊。因此，無線傳感器網絡的節點安全定位至關重要。

無線傳感器網絡安全定位技術近幾年來成為了研究熱點之一，并取得了大量的成果。文獻［2］概述了現有的主要無線傳感器網絡安全定位算法。傳感器網絡節點安全定位的研究大致分為四大類:1)基于頑健觀測的安全定位策略，如，VM 定位機制［3］，SeRLoc［4］，SLA［5］;2)基于頑健計算的安全定位策略，如，AR－MMSE［6］;3)基于惡意信標節點檢測/隔離的安全措施，如，Liu D 檢測算法［7］，DRBTS［8］;4)基于位置校驗的安全措施，如，GFM 和TI 校驗算法［6］。Srinivasan A 等人提出的DRBTS 中，每個檢查點(信標節點)通過監聽信道來監督鄰居信標節點的服務情況，并根據每次的觀察結果更新監督對象的聲譽值;在此基礎上，未知節點通過學習機制收集鄰居信標節點的聲譽信息，再根據這些信息采用信任分級和集體投票方法選出可信任的信標節點。

在DRBTS 中需進行位置信息傳遞，加大了節點坐標泄露的可能性，從而使惡意節點竊取、篡改節點位置坐標，造成未知節點錯誤的節點位置定位。針對節點的安全定位，本文提出了一種無需進行坐標信息傳遞的安全定位算法，此算法通過迭代投票的方式選出可信的信標節點，從而實現安全定位。

1 定位原理

假設無線傳感器網絡中有三種節點:信標節點，未知節點和惡意節點。未知節點nv為待定位的節點，N(v)為nv的鄰近信標節點和節點nv的集合，共有n 個元素，R 為未知節點nv的通信半徑，所有節點分布在二維平面內，每個節點ni都擁有唯一的身份標識IDi。本文提出的迭代投票算法主要基于以下原理進行安全定位:

1)若N(v)中的信標節點是可信的，則信標節點到未知節點nv的距離小于通信半徑R;任意兩信標節點的距離小于2R。

2)若信標節點nx，ny，nz是可信的，通過三邊定位法［9］計算出的其他任意兩個信標節點ni，nj的坐標pi，pj，必接近ni，nj的實際坐標。因此，當前信標節點的可信性可以通過以此節點為基準，計算出的其他信標節點坐標的準確性來加以判斷。由于不進行節點坐標交換，計算出的節點坐標準確性可以通過以下方法加以描述:通過pi，pj計算得到距離d'ij=|pi－pj|，兩節點間的實際距離為dij，兩者之間的誤差為|d'ij－dij|。若|d'ij－dij|小于ε(ε 為定位誤差閾值)，則認為計算出的節點坐標準確，當前節點nx，ny，nz可靠。如圖1 所示，信標節點A，B，C 是可信的，D，E 為另兩個信標節點，利用三邊定位法計算出D，E 的節點坐標D'，E'在其實際坐標附近，則|d'DE－dDE|＜ε。

圖1 原理2 示意圖Fig 1 Schematic diagram of principle 2

2 算法步驟

2.1 測距階段

在測距階段，N(v)中的每個節點ni測出到其他節點的距離，并剔除部分節點。具體步驟如下:

1)N(v)中的每個節點利用某一特定測距方法(如TDOA，TOA，RSSI)測出到其他節點的距離dij(i≠j)。所有的距離可以形成n×n 的距離矩陣Md

2)每個節點ni向待定位節點nv發送其到其他節點距離信息{IDi‖IDj‖dij}，其中，k 為合法節點共享的一組密鑰，{}k為利用密鑰k 對信息進行加密。

3)根據定位原理1，去除距離矩陣Md中相應的不可信信標節點。N'(v)表示剩余節點的集合，其元素個數為n'。

2.2 迭代投票階段

在這一階段，每個節點ni都有一個投票器votei來記錄其得票數，初始值為0。根據迭代算法計算出的定位距離誤差，對節點進行投票。具體步驟如下:

1)在N'(v)中任意選取三個信標節點nx，ny，nz;

2)利用nx，ny，nz的坐標px，py，pz和到其他所有信標節點ni(ni∈N'(v)，i≠x，y，z)的距離dxi，dxj，dxz，通過三邊定位法計算出節點ni的坐標pi;

3)根據步驟(2)中計算出的坐標，計算除被選中的三個節點nx，ny，nz外，其他任意兩個節點ni，nj之間的定位距離誤差|d'ij－dij|;

4)若|d'ij－dij|＜ε，則信標節點nx，ny，nz各得一票，其投票器加1;

5)重復步驟(1)～(4)，經過num 次迭代，每個信標節點ni(ni∈N'(v))共獲得的投票數為|votei|。

2.3 得票數表更新階段

每個未知節點nv經過num 次迭代，形成每個信標節點ni(ni∈N'(v))的得票數表TVv(table of votes)，如表1 所示。未知節點交換得票數表，進行TVv更新，具體步驟如下:

表1 得票數表Tab 1 Table of votes

1)每個未知節點向其他未知節點發送自己的得票數表{IDv‖TVv}k;

2.4 未知節點定位階段

未知節點nv根據TVN'v中信標節點的投票數進行定位。具體步驟如下:

1)未知節點選取獲得投票數最多的三個信標節點na，nb，nc;

2)利用na，nb，nc的坐標pa，pb，pc和距離dvi(i=a，b，c)，通過三邊定位法計算出nv的坐標p'v。

3 算法仿真

本文提出的迭代投票算法，迭代次數num 的大小將直接影響到定位誤差和算法復雜度。假設誤差閾值ε=10 m，如圖3所示，即使在惡意節點數為時，通過14 次迭代定位誤差≤0.1;15 次迭代誤差≤0.05;16 次迭代誤差≤0.01。

圖2 節點分布圖Fig 2 Deployment of nodes

圖3 惡意節點數與迭代次數關系圖Fig 3 Diagram of relationship between malicious nodes and iteration numbers

若迭代次數num=10，誤差閾值ε=10 m，比較本文提出的迭代投票算法與未使用迭代投票的定位誤差。如圖4所示，本文提出的迭代投票算法極大地提高了節點定位精度。

圖4 定位誤差比較圖Fig 4 Comparison of localization error

4 結 論

在安全定位算法中，進行節點間交換位置信息，增加了位置信息被竊聽、篡改的可能。本文提出的算法在無須節點間交換位置信息的條件下，通過迭代投票選出可信的信標節點，實現安全定位。通過實驗仿真，迭代投票安全定位算法能在較少的迭代次數下獲得很小的定位誤差，大大提高了定位精度。

［1］ Jiang Jinfang，Han Guangjie，Shu Lei，et al.A novel secure localizations scheme against collaborative collusion in wireless sensor networks［C］∥Proc of IEEE IWCMC，Istanbul，2011:308－313.

［2］ Zeng Yingpei，Cao Jiannong，Hong Jue，et al.Secure localization and localization verification in wireless sensor networks［C］∥Proc of the 2009 IEEE 6th International Conference on Mobile Ad－Hoc and Sensor Systems，Macau，2009:864－869.

［3］ Capkun S，Hubaux J P.Secure positioning in wireless networks［J］.IEEE Journal on Selected Areas in Communications，2006，24(2):221－232.

［4］ Lazos L，Poovendran R.SeRLoc:Secure range－independent localization for wireless sensor networks［C］∥Proc of the 2004 ACM Workshop on Wireless Security，Philadelphia:ACM，2004:21－30.

［5］ Anjum F，Pandey S，Agrawal P.Secure localization in sensor networks using transmission range variation［C］∥Proc of 2nd IEEE International Conference on Mobile Ad－Hoc and Sensor Systems，Washington:IEEE Computer Society，2005:195－203.

［6］ Liu D P，Ning W K Du.Attack－resistant location estimation in sensor networks［C］∥Proc of IPSN 2005，Los Angeles:IEEE Computer Society，2005:99－106.

［7］ Liu D，Ning P，Du W.Detecting malicious beacon nodes for secure location discovery in wireless sensor networks［C］∥Proc of International Conference on Distributed Computing Systems，Columbus:IEEE，2005:609－619.

［8］ Srinivasan A，Teitelbaum J，Wu J.DRBTS:Distributed reputationbased beacon trust system［C］∥Proc of the 2nd IEEE International Symposium on Dependable，Autonomic and Secure Computing，Indianapolis:IEEE，2006:277－283.

［9］ 戴 歡.無線傳感器網絡定位算法及其應用研究［D］.無錫:江南大學，2012.

［10］Zhong S，Jadliwala M，Upadhyaya S，et al.Towards a theory of robust localization against malicious beacon nodes［C］∥Proc of IEEE INFOCOM，Phoenix，2008:1391－1399.