唐弢，郭慶，李含青

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

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

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

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

1 網(wǎng)絡模型和基本假設

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

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

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

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

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

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

2 MANWS算法

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

2.1 錨節(jié)點檢測

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

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

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

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

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

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

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

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

式中:M為nj可通信節(jié)點個數(shù)，N為網(wǎng)絡中錨節(jié)點個數(shù).

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

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

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

2.2 定位算法

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

2.2.1 尋找錨節(jié)點

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

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

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

2.2.2 確定權值

圖4 未知節(jié)點區(qū)域Am×n網(wǎng)格劃分Fig.4 The grid of unknown node area Am×n

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

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

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

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

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

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

2.2.3 未知節(jié)點定位

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

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

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

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

3 MANWS算法仿真與分析

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

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

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

3.1 不存在攻擊或多徑

本文主要對影響定位精度的參數(shù):錨節(jié)點數(shù)量、通信半徑和小網(wǎng)格邊長進行仿真.

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

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

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

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

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

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

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

3.2 存在攻擊或多徑

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

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

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

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

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

4 結束語

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

［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校驗的無線傳感器網(wǎng)絡節(jié)點定位算法［J］.小型微型計算機系統(tǒng)，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，F(xiàn)ANG 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.