多可利用節點加權網格掃描安全定位算法

唐弢，郭慶，李含青

(哈爾濱工業大學通信技術研究所，黑龍江哈爾濱150001)

無線傳感網絡(WSN)是由部署在監測區域內的大量微型、低成本、低耗能的傳感器節點組成的多跳無線網絡、實現監測區域內敏感數據采集、處理和傳輸［1］.在WSN中，位置信息在WSN的監測活動中具有至關重要的作用，事件發生位置或獲取信息節點位置是傳感器節點監測消息中所必須包含的重要信息，沒有位置信息的監測消息往往毫無意義.因此，確定事件發生的位置或確定獲取消息的節點位置是WSN最基本的功能之一，對WSN應用的有效性起著關鍵作用［2］.

無線傳感器網絡中的定位問題可以描述為:在一個存在多個已知自身位置節點的多跳網絡中，通過定位系統、利用可用的信息找到未知節點的位置.定位算法主要分基于測距定位算法和非測距定位2種:前者是利用接受信號強度(RSSI)、到達時間(TOA)、到達時間差(TDOA)、到達角度(AOA)等測距信息定位，具體算法如環形RSSI(ROCRSSI)定位算法等;后者是利用網絡的連通度定位，如質心算法等［3］.

在無線傳感器網絡的某些應用網絡中，存在著因對網絡攻擊而導致定位不準確或無法定位的情況，例如戰場環境中的定位.戰場環境下網絡中的安全問題可以分為內部攻擊和外部攻擊兩類:內部攻擊是指網絡中的某一節點發送錯誤的測量信息;外部攻擊是指惡意節點偽裝成其他節點發送錯誤位置或測量信息.因而無論是內部還是外部攻擊，其最終的形式都是使節點的實際位置與聲明位置不符，或給出錯誤的測量信息(如強度、時間等)［4-5］.另外，在網絡中存在著多徑的情況.多徑問題是由建筑物反射等引起的，可以使未知節點在定位時誤認為有多個錨節點存在，并且其中一個發送的是錯誤的信息.因而，多徑也可以視為影響安全問題的一種因素.本文針對網絡中的攻擊和多徑問題，提出一種新的安全定位算法“多可利用節點加權網格掃描安全定位算法(MANWS)”，解決了在有遮蔽戰場環境下的定位問題.

1 網絡模型和基本假設

本文假設存在一個多跳分布式無線傳感網絡.該網絡主要針對于有遮擋的戰場環境，如森林中的戰場跟蹤與監測等，因而存在著安全和多徑問題.

在定位系統中通常有2種類型的節點:未知節點(unknown node)和錨節點(anchor).未知節點是指在網絡中節點位置未知并且本身沒有特殊的硬件設備可以獲得自身信息的節點;錨節點是指節點可以通過GPS等外部設備或確知的實際布置因不需要定位系統計算就能直接得到自身的物理位置.其中，錨節點是整個定位系統的基礎［6］.在網絡中，各節點(包括未知節點和錨節點)的信息傳播范圍均為一個以自身實際位置為中心、R為半徑的圓，即節點的通信半徑為R.實際中，通信范圍并不是一個規則的正圓而是一個不規則圖形［7］，這并不對本算法的定位精度等指標產生影響，因而為方便表達選用簡化的傳播模型.同時，每個節點可以發現與自己距離1跳和2跳的節點.其中，1跳是指距節點距離在［0，R］內的節點;同理，2跳是指距節點距離在(R，2R］內的節點.另外，在節點上應安裝RSSI測距設備和天線，以測量兩節點之間的距離和角度.

式中:β是pass loss指數，通常由場地測量得來，表1給出了β的一些典型值，障礙物越多其數值越大，因此隨著距離的增加接收到的平均能量下降的速度會越來越快(本文β=3).由式(1)可得:

式中:pt為傳送信號的強度，Gt、Gr分別是發送者和接收者的天線增益，L(L≥1)為系統損失，λ為波長.通常情況下，Gt=Gr=1、L=l［8］.

表1 pass loss指數β的幾種典型值Table 1 Typical value of the pass loss parameter β

pass loss通常由dB作為計量單位，因此根據式(1)可得

2 MANWS算法

MANWS算法主要分為錨節點檢測和未知節點定位2個部分，具體流程如圖1所示.下面將對算法做出詳細的闡述.

2.1 錨節點檢測

選擇二維坐標系網絡中任意2個錨節點ni和nj，且兩節點之間的距離小于R，如圖2所示.假設ni和nj相互間的到達角度分別為aij和aji.

圖1 算法總體流程Fig.1 The process of algorithm

圖2 錨節點ni和nj幾何關系模型Fig.2 The geometry between ni＆nj

這里對nj的安全性進行判定，假設兩錨節點之間的距離為dij，則有

式中:距離d和角度a分別由節點裝載的RSSI裝置和天線得到.如圖2所示，如果不存在測量誤差和攻擊，顯然可得

然而，在實際中測量會存在一定的誤差，導致節點非惡意時相加的結果不為0，此時需要引入門限值來指導攻擊節點的判斷結果.設門限值為λ，則nj安全判定條件為

對于內部攻擊，測量距離和角度都是錯誤的，所以可以由式(6)直接判定;而對于外部攻擊，其測量距離是正確的，只是聲明位置與實際位置不符，因而nj是否為攻擊節點可以由式(7)進行判定.

式中:(xi，yi)、(xj，yj)分別是ni、nj的坐標.由于以上在進行判定時使用的錨節點ni可能是惡意節點，所以需應用輪盤法對nj通信范圍內的每個錨節點進行計算，最后得到nj的可信度:

式中:M為nj可通信節點個數，N為網絡中錨節點個數.

以上討論了內部和外部攻擊的情況，下面介紹網絡中存在多徑時此算法的應用.兩錨節點間多徑情況如圖3所示，從ni獲得的信息可以看出，nj有2個位置:原本位置和反射點，即(xij，yij)和(xij'和yij');同樣的，有(xji，yji)和(xji'和yji').因而對nj的判斷條件為

圖3 多徑情況下節點幾何模型Fig.3 The geometry of network in multi-path

使用輪盤法遍歷所有nj的可通信節點，只要有一個符合式(9)，則可以說明nj為可信任節點.由于多徑情況的特殊性，此步驟可以在判定內部與外部攻擊之前進行，從而去除衍生的反射點.

2.2 定位算法

假設網絡中有N個錨節點和K個未知節點，且N?K.定位算法可分為以下3個步驟:尋找錨節點、確定權值和對未知節點定位.

2.2.1 尋找錨節點

未知節點收集它所監聽到的所有錨節點信息.若坐標為(xS，yS)的未知節點S可監聽到的所有錨節點集合為LHS，相應錨節點坐標分別為(xi，yi)，則這些錨節點在以(xS，yS)為圓心、以R為半徑的圓內，將之稱為1跳錨節點，其集合為

收集LHS1中所有1跳錨節點的鄰居錨節點作為2跳錨節點，相應錨節點坐標分別為(xj，yj).2跳錨節點在以(xS，yS)為圓心、以R和2R為內外半徑的環形中，其集合為

因而，對于未知節點S，1跳錨節點有L1個，其集合為LHS1;2跳錨節點有L2個，其集合為LHS2.

2.2.2 確定權值

圖4 未知節點區域Am×n網格劃分Fig.4 The grid of unknown node area Am×n

權值的確定是多可利用節點加權網格掃描安全定位算法中最重要的部分之一.算法中，利用RSSI值對距離進行估計，并將距離的倒數作為權值.以下將對1跳錨節點和2跳錨節點兩方面進行討論.

1)當被估計距離范圍為［0，R］時，未知節點S能直接接收到LHS1集合中錨節點發出的信號.則未知節點S接收到固定錨節點L1i的信號強度平均值pi為

式中:RSSIi表示未知節點S接收到固定錨節點L1i信號的RSSI平均值.同理可得固定錨節點L1i接收到固定錨節點L1j信號強度平均值pij.令dij表示固定錨節點L1i到固定錨節點L1j之間的距離，則由式(1)可得到未知節點S到固定錨節點L1i的距離di為

因此，可以假設LHS1集合中固定錨節點L1i的權值為 ωi=1/di.

2)當被估計距離范圍為(R，2R］時，未知節點S能直接接收到LHS2集合中錨節點發出的信號.與1)相同，由于LHS2集合中錨節點為LHS1集合中錨節點的鄰居，又因為任意2個錨節點中的距離已知，所以任意LHS2集合中錨節點L2k的權值為

式中:dik為L2k與其在LHS1中鄰居節點之間的距離，di為未知節點S到L2k在 LHS1中鄰居節點L1i的距離.值得注意的是，當網絡中存在LHS2集合中錨節點的鄰居節點多個存在于LHS1集合中，這時需計算所有ωk中最大值作為L2k的權值.

2.2.3 未知節點定位

權值計算完畢后，開始定位過程，多可利用節點加權網格掃描安全算法的定位過程如圖5所示.

在未知節點區域Am×n中，將每個網格的計分牌數值初始化，即Q=0.遍歷LHS1集合中所有錨節點，若網格在其通信范圍內，則計分牌加上該錨節點的權值.然后，遍歷LHS2集合中錨節點，若網格距錨節點在(R，2R］內，則計分牌加上此錨節點的權值.最后，得到網格的計分牌數值為

選擇記分牌上最大的數值區域作為未知節點存在區域，并將此區域的質心作為未知節點S的估計位置.

圖5 多可利用節點加權網格掃描算法定位過程Fig.5 The progress of weighted grid scan location algorithm with multi available nodes

3 MANWS算法仿真與分析

為了檢驗算法的性能，本文對所提出的定位算法進行了一系列仿真比較.仿真中，初始網絡設置為一個(100×100)m2的正方形網絡，并隨機產生均勻分布的網絡拓撲節點，節點數量為200個，其中有50個錨節點.節點通信半徑R為20 m，每一小網格為(2×2)m2的正方形.這里假定pass loss指數β值為3.

定位精度是衡量定位算法精確性的主要標準，其表達方法為

式中:Errormin是定位的平均誤差，(xe，i，ye，i)和(xr，i，yr，i)分別是未知節點的估計位置和實際位置.

3.1 不存在攻擊或多徑

本文主要對影響定位精度的參數:錨節點數量、通信半徑和小網格邊長進行仿真.

在對錨節點數量仿真時，假設其他條件不變，錨節點數量由20個增加到100個，將MANWS算法定位誤差與 DLE(distributed location estimation)算法［9］進行比較，得到的仿真結果如圖6所示.

在對通信半徑仿真時，假設其他條件不變，通信半徑由10 m增加到70 m，并將MANWS算法定位誤差與DLE算法比較，得到的仿真結果如圖7所示.

在對小網格邊長仿真時，假設其他條件不變，小網格邊長由1 m增加到3.3 m，得到的仿真結果如圖8所示.

由圖6～8可以看出多可利用節點加權網格掃描算法的定位精度明顯好于DLE算法，并受通信距離、錨節點比例和小網格邊長影響.

圖6 錨節點比例對定位誤差的影響Fig.6 Localization error vs.anchors number

圖7 通信距離對定位誤差的影響Fig.7 Localization error vs.communication range

圖8 小網格邊長對定位誤差的影響Fig.8 Localization error vs.grid scale

3.2 存在攻擊或多徑

假設在一個(100×100)m2的正方形網絡中存在節點數量為200個，其中錨節點由20個增加到100個，其通信半徑均為R=20 m，pass loss指數β值為 3，并且網絡受到女巫［10］、蟲孔、泛洪［7，11］等幾種常見形式的聯合攻擊，如圖9所示.具體地說，網絡中存在以下情況:1)單一惡意節點宣稱一個遠離它實際位置θ m的錯誤位置信息或修改它與待定位節點間的距離來影響位置評估精度;2)多個非共謀的惡意錨點，并且它們相互獨立地宣稱一個遠離它實際位置θ m的錯誤位置信息或修改它與待定位節點間的距離來影響位置評估精度;3)考慮多個惡意節點是共謀的情況;4)多徑反射形成的虛擬節點.另外，假設網絡中存在各種類型惡意節點總數為10個，占總節點數的5%.

在此環境下，對多可利用節點加權網格掃描安全定位算法的進行仿真驗證其安全性，并與DEL算法做出對比，如圖10所示.

從圖10可以看出，多可利用節點加權網格掃描安全定位算法可以抵御各種攻擊，并能應用于多徑問題存在的復雜環境中，與DLE算法相比，多可利用節點加權網格掃描安全定位算法具有更好的安全性.

圖9 攻擊模型示意Fig.9 Attack model

圖10MANWS算法安全性能仿真Fig.10 Secure simulation of MANWS algorithm

4 結束語

提出了一種多可利用節點加權網格掃描安全定位算法，適用于丘陵、山脈等有遮蔽的復雜戰場環境中，并且能夠在精確定位的同時保證定位的安全性，從而抵御戰場環境中的各種攻擊.在下一步的研究工作中，將進一步研究此算法的移動性，另外一個目標是將該算法應用于三維環境中.

［1］AKYILDIZ I F，SU W，SANKARASUBRAMANIAM Y，CAYIRCI E.Wireless sensor networks:a survey［J］.Computer Networks，2002，38(4):393-422.

［2］RAHMAN M Z，KLEEMAN L.Paired measurement localization:a robust approach for wireless localization［J］.IEEE Transactions on Mobile Computing，2009，8(8):1087-1102.

［3］汪煬，黃劉生，徐宏力，肖明軍.基于RSSI校驗的無線傳感器網絡節點定位算法［J］.小型微型計算機系統，2009，30(1):59-62.

WANG Yang， HUANG Liusheng， XUHongli， XIAO Mingjun.Localization algorithm for wireless sensor network based on RSSI-verify［J］.Journal of Chinese Computer System，2009，30(1):59-62.

［4］BOUKERCHE A，OLIVEIR H A B，NAKAMURA E F，LOUREIRO A A F.Secure localization algorithms for wireless sensor networks［J］.IEEE Communications Magazine，2008，46(4):96-101.

［5］BAGGIO A，LANGENDOEN K.Monte Carlo localization for mobile wireless sensor networks［J］.Ad Hoc Networks，2008，6(5):718-733.

［6］HU F ，TILLET J，ZIOBRO J，SHARMA N K.Secure wireless sensor networks:problems and solutions［J］.Journal on Systemics，Cybernetics and Informatics，2004，11(9):419-439.

［7］LAZOS L，POOVENDRAN R.HiRLoc:high-resolution robust localization for wireless sensor networks［J］.IEEE Journal on Selected Areas in Communications，2006，24(2):233-246.

［8］RAGHAVENDRA C S，SIVALINGAM K M，ZNATI T.Wireless sensor networks［J］.International Journal of Distributed Sensor Networks，2007，3(4):371-371.

［9］SHEU J P，LI J M，HSU C S.A distributed location estimating algorithm for wireless sensor networks［C］//2006 IEEE International Conference on Sensor Networks，Ubiquitous and Trustworthy Computing.Washington DC，USA，2006:218-225.

［10］DOUCEUR J R.The sybil attack［C］//The First International workshop on Peer-to-peer systems(IPTPS'02).Cambridge，UK，2002:251-260.

［11］ZHANG Y，LIU W，FANG Y，WU D.Secure localization and authentication in ultra-wideband sensor networks［J］.IEEE Journal on Selected Areas in Communications，2006，24(4):8-29.