無線傳感器網絡節點自定位算法研究

摘要:節點位置信息是無線傳感器網絡應用的基礎，該文介紹了幾種典型的節點自定位算法，并對其進行了分析比較。其中ACT算法是分布式的算法，定位精度最高，但是最大的缺點就是計算發雜性高。該文對傳統的ACT算法進行了改進，降低了算法的復雜性，提高了定位的精度。仿真試驗表明:改進的ACT算法大幅降低了算法的運算復雜性，對于定位精度也有一定的提高。

關鍵詞:無線傳感器網絡;節點自定位;Trilateration算法;ACT算法

中圖分類號:TP3911文獻標識碼:A文章編號:1009-3044(2009)25-7110-03

Research on Self-Localization Algorithm for Wireless Sensor Network

ZHANG Jie， QIU Xiao-hui， LIU Xin

(College of Communication and Information Engineering of Nanjing University of Posts and Telecommunications， Nanjing 210003， China)

Abstract: The information of node localization is the base in application of wireless sensor networks (WSNs). In this paper several representative localization algorithm are discussed and compared. The ACT algorithm is distributed and is more precise than other algorithms， but it's too complex. So an improved ACT algorithm is presented. The extensive simulation shows that the improved ACT algorithm is simplified and can achieve high localization accuracy.

Key words: wireless sensor network; node self-localization; trilateration algorithm; alternating combination trilateration algorithm

無線傳感器網絡(wireless sensor network，簡稱WSN)就是由部署在監測區域內大量的廉價微型傳感器節點組成，通過無線通信方式形成的一個Adhoc網絡系統，其目的是協作地感知、采集和處理網絡覆蓋區域中感知對象的信息，并發給觀察者[1]。傳感器、感知對象、觀察者構成了傳感器網絡的三個要素。

無線傳感器網絡的節點自定位就是根據少數已知未知的節點，按照某些定位機制確定自身的位置。只有在傳感器節點自身定位之后，才能確定傳感器節點檢測到的事件發生的具體位置，這需要檢測到該事件的多個傳感器幾點之間互相協作，并利用它們自身的未知信息，使用特定的機制確定發生的位置。因此，在傳感器網絡中，傳感器節點自身的定位是提供監測事件未知信息的前提。

1 節點自定位算法分析

1.1 節點自定位算法的分類

根據定位機制可以將現有的無線傳感器網絡節點自定位算法分為兩類[2]:Range-Based 和Range-Free，前者需要通過測距或者角度信息;后者無需距離和角度信息，僅根據網絡連通性等信息實現節點的定位。

距離無關的定位機制(Range-Free)[3]無需實際測量節點間的絕對距離或方位就能夠計算未知節點的位置，因而降低了對節點硬件的要求，且定位性能受環境因素影響較小，適合應用于大規模的傳感器網絡，其中質心算法、DV-Hop算法[5]、Amorphous[6]算法和APIT算法是4種目前倍受關注的分布式的Range-Free定位機制。

基于距離的定位機制(Range-Based)需要根據節點間距離或角度的測量結果進行定位計算。常用的測距技術有Trilateration算法[4]和循環三邊組合測量法(ACT) [6]。

1.2 幾種節點自定位算法

該文主要研究基于距離的定位機制中的Trilateration算法和ACT算法，并且對ACT算法進行改進降低算法的復雜度，提高算法的定位精度。

1) Trilateration算法

Trilateration算法稱為三邊測量法，三個信標節點的坐標已知，分別為:(x1，y1)，(x2，y2)，(x3，y3)。三個信標節點到未知節點的距離分別為d1，d2，d3。按照如下關系式:

可計算出未知節點坐標為:

2) ACT算法

Trilateration算法三個信標節點的位置對于定位的誤差影響很大，比如當三個信標節點成等邊三角形分布時，定位的誤差最小，當三個信標節點共線時，定位誤差最大。

在這里我引入一個新的定義，角度權重函數:

W(a)min{Ad，Bd，Cd}

Ad，Bd，Cd分別為三角形ABC三個角的弧度值。

因為任意的三個信標節點可以確定一個頂點，所以N個信標節點根據排列組合可確定出CN3個權重多邊形。

所以根據上面的分析ACT算法的步驟如下:

第一步:確定權重多邊形的頂點坐標:每個信標節點廣播自身的ID以及位置信息(Xi，Yi)(i=1，…，N)，鄰居節點均能收到這些信息并利用TDOA[3]技術估計它到信標節點的距離ri(i=1，…，N)，根據信標節點中任意三個坐標值的組合及距離值計算權重多邊形的頂點坐標。例如:(Xa，Ya)(Xb，Yb)(Xc，Yc)，ra，rb，rc使用SSL算法計算權重多邊形的頂點坐標(IXj，IYj)(j=1，…，N):

[LXj，IYj]T=(MTM-1)MTL

其中:

第二步:確定權重多邊形頂點的權重值:

根據已知條件利用三角函數余弦定理計算出權重多邊形三個角的弧度值Ad，Bd，Cd，再利用權重函數計算權重。

第三步:重復步驟1和2計算權重多邊形其它的CN3-1個頂點坐標以及對應的權重值。

第四步:歸一化權重

第五步:確定未知節點的坐標:

第六步:重復步驟1到5計算其它未知節點的坐標值。

3) 改進的ACT算法

ACT算法有著良好的定位精度，但是缺點是顯而易見的就是算法的復雜度偏高，因此需要對ACT算法進行簡化，在之前我們分析過當三個節點成等邊三角形分布時定位誤差最小，共線時定位誤差最大，因此我們得到了如下的啟發:N個信標節點中我們沒有必要選取所有可能的組合來進行定位運算，因為由于誤差的累加定位誤差可能越累計越大，所以我們通過某種方法選取信標節點分布較好(接近于等邊三角形)的前m種組合，這樣但可以大大的簡化算法的復雜性同時也提高了定位的精度。從第3節的仿真結果中我們可以看到，總存在一個m使得定位的誤差最小，同時也大幅度的降低了計算的復雜性，節省了開銷。

對ACT算法改進如下:

第一步: 采用不同的權重函數。

第二步: 不對CN3種組合進行三邊測量，改為取前m個權重值最大的進行三邊測量。

改進的ACT算法實現步驟如下:

第一步:對于任意的三角形首先計算出三個頂點的正切值:

tanA=(K2-K3)/(1+K2K3)

tanB=(K1-K3)/(1+K1K3)

tanC=(K2-K1)/(1+K2K1)

其中K為三個頂點對應三條邊的斜率

權重函數為:

W(a)=min{tanA， tanB， tanC}

第二步:利用上面的方法計算每個三角形的權重值:

W(aj)=tanaj(j=1，…，CN3)

第三步:對于所有的三角形按照權重值進行排序，取權重值最大的前m個。

W(ak)=tanak(k=1，…，CN3)

第四步: 對于前m個權重值的進行歸一化處理:

第五步:根據三邊測量法計算m個頂點的坐標:

其中

第八步:確定未知節點的位置:

2 實驗仿真和結果分析

2.1 仿真環境

該文選用MATLAB版本為R2007a，運行硬件平臺為Inter(R) 1.73GHz CPU，1.00GB RAM，120GB 7200RPM Hard disk的PC機進行仿真。

2.2 仿真對象

1) 無線傳感器網絡節點自定位Trilateration算法。

2) 無線傳感器網絡節點自定位ACT算法。

3) 無線傳感器網絡節點自定位改進的ACT算法。

2.3 仿真結果

試驗中選取100m*100m的仿真環境，加入20%的高斯噪聲，通信半徑R=10m，信標節點和未知節點的比例為1:10，即10個信標節點，100個未知節點，均為隨機分布。如圖1所示，藍色星形為未知節點，黑色鉆石型為信標節點。

1) Trilateration算法仿真結果

圖2Trilateration算法進行定位后實際位置(星形)和估計位置(黑點)

2) ACT算法仿真結果

圖3為ACT算法進行定位后實際位置(星形)和估計位置(綠點)。

3) 改進的ACT算法仿真結果

圖4為改進ACT算法進行定位后實際位置(星形)和估計位置(紅點)。

2.4 仿真結果分析

1) 經驗值m的選取

經過100次仿真總存在一個m值使得定位精度最大，如圖5所示我們可以看出m取38時定位精度最高，因此我們可以根據經驗來選取m(不同的環境可能存在不同的m值)。

2) 三種方法的定位精度比較

如圖6所示，綠色為Trilateration算法定位精度，紅色為ACT算法的定位精度，藍色為改進的ACT算法的定位精度。在相同的條件下對三種方法進行100次循環運算，Trilateration算法的平均定位精度為35.67%，ACT算法的平均定位精度為25.11%，改進的ACT算法的平均定位精度為21.45%。通過實驗數據可以看出Trilateration算法的定位精度最差，改進的ACT算法的定位精度最好。

3) 算法復雜度比較

本實驗仿真N取100，m若取38則，ACT算法的乘除運算次數約為6720次，三角函數運算為360次，改進的ACT算法的乘除運算為2524次，沒有三角函數運算，因此從算法復雜度來說Trilateration算法最簡單，ACT算法最為復雜，改進的ACT算法大大簡化了ACT算法的復雜性。

3 結束語

該文針對目前無線傳感器網絡的節點自定位算法中基于測距的Trilateration算法，ACT算法進行詳細研究，可以看出兩種算法各有特點。主要對ACT算法進行改進，不但大幅度降低了ACT算法的運算復雜度，而且提高了ACT算法的定位精度。

參考文獻:

[1] S Tilak， N.B Abu-Ghazaleh， W Heinzelman， A taxonomy of wireless micro-sensor network models. Mobile Computing and Communications Review， 2002， 1-8.

[2] e T， Huang C， Blum B M. Range-free localization schemes for large scale sensor networks.In:Proc9th Annual Int'l Conf on Mobile Computing and Networking (MobiCom)，San Diego，CA.，2003:81-95.

[3] 孫利民，李建中，陳渝，等.無線傳感器網絡[M].北京:清華大學出版社，2005:3-5.

[4] K Langendoen，N Rejiers. Distributed localization in wireless sensor networks:Auqnatitative comparison [J].Computer Networks， 2003， 43(4):499-518.

[5] NiruPama Bulusu，John Heidemann，Deborah Estrin.CPS-less low cost outdoor localization for very small devices[J] IEEE Wireless Communications，2000，7(5):27-34

[6] 余義斌.傳感器網絡定位算法及相關技術研究[D].重慶:重慶大學博士學位論文，2006，10.