基于距離的分布式無線傳感器網絡定位算法

摘 要：針對水下無線傳感器節點的定位問題進行研究，提出了一種可實現網絡規模升級的分布式無信標節點的自定位算法。該定位算法無須額外的硬件支持，僅采用節點間的距離信息建立相對坐標系，確定各節點的相對位置。詳細介紹了該算法的實現過程，通過仿真討論了求精過程、通信半徑等對定位誤差的影響，并驗證了該算法的合理性。為目標跟蹤、地理路由、網絡管理等系統功能提供了有力的技術支持。

關鍵詞：無線傳感器網絡； 節點定位； 基于距離； 分布式

中圖分類號：TP393.03 文獻標志碼：A 文章編號：1001-3695(2008)08-2528-04

Range-based and distributed node localization in wireless sensor networks

LIU Ai-ping， LIU Zhong， LIANG Yue， ZHOU Wei

( College of Electronics Engineering， Naval University of Engineering，Wuhan430033， China)

Abstract:This paper set out to explore node localization in underwater wireless sensor networks and proposed a scalable and distributed anchor-free algorithm of node localization. The algorithm had no use for additional hardware and only adopted the distances between the nodes to build a relative coordinate system on which to compute relative position of all nodes. It introduced the algorithm in detail and discussed the influence of refinement process and communication radius to the precision. Simulation results show that the proposed localization of node is reasonable. The algorithm of node localization is capable of supporting the further step of target-tracking， geography route and administration of networks efficiently and precisely.

Key words:wireless sensor network；node localization；range-based；distributed

無線傳感器網絡是由部署在監測區域內大量的微型傳感器節點組成，通過無線通信方式形成多跳、自組織的網絡系統。它可以通過臨時組網的方式在惡劣環境中支持節點之間的數據、語音、圖像和圖形等業務的無線傳輸，應用范圍可以覆蓋工業、商業、醫療、家庭、辦公環境、軍事等各種場合^[1]。尤其在未來戰場上，無須固定的基礎設施和分布式的網絡配置使無線傳感器網絡在軍事沖突中是可行的甚至是惟一可行的組網方式。無線傳感器網絡對于高技術武器裝備、集中指揮、協同作戰和提高作戰機動性等具有非常重要的意義。美國商業界周刊和MIT技術評論在預測未來技術發展的報告中，分別將無線傳感器網絡列為21世紀最有影響的21項技術和改變世界的10大技術之一。

無線傳感器節點通常隨機布放在不同的環境中執行各種監測、通信等任務，以自組織方式相互協調工作。例如，用飛機將傳感器節點布放到指定的區域中。隨機布放的傳感器節點無法事先知道自身位置，因此傳感器節點必須能夠在布放后進行定位。傳感器節點只有在自身正確定位后，才能確定傳感器節點檢測到的事件發生的具體位置。定位信息除可以報告事件發生的地點外，還可以用于：a）目標跟蹤，實時監視目標的行動路線，預測目標的前進軌跡；b）協助路由，直接利用節點位置信息進行數據傳遞的地理路由協議，避免信息在整個網絡中的擴散，并可以實現定向的信息查詢；c）進行網絡管理，利用傳感器節點傳回的位置信息構建網絡拓撲圖，并實時統計網絡覆蓋情況，對節點密度低的區域及時采取必要的措施^[1，2]，等等。因此，在傳感器網絡中，節點的精確定位對各種應用有著重要的意義。由于傳感器節點受到成本、能量和體積的限制，無線傳感器網絡的定位遇到了新的挑戰。GPS是一種獲得位置信息的方法，但是由于傳感器節點的數量非常巨大，達到數千甚至數萬，成本太高；另外，傳感器節點是采用電池供電，其電能不僅十分有限，而且不能補充，不適宜每個節點都裝備高能耗的GPS設備。在某些應用環境下，無法獲取GPS信號，如封閉的室內環境，針對本文海底布放的節點也無法使用GPS系統，致使該方法會受到一定的使用限制^[3]。

目前已經提出很多種節點定位的方法，并且都有很大的發展。根據定位的過程中是否使用信標節點，把定位算法分為基于信標節點的定位算法和無信標節點的定位算法。基于信標節點的定位中，以信標節點作為參考點，而且要求信標節點均勻分布于檢測區域且信標節點的數目達到所有節點數目的百分之十，甚至是百分之二十，才能達到較好的定位效果^[4]。而針對很多應用環境，無法達到這種要求，如在水下布放大量位置精確的信標節點，實現難度很大。因此本文采取了無信標節點的定位算法，提出了基于距離的分布式無信標的節點自定位機制。通過網絡內部節點之間的相互測距和信息交換，形成一套全網節點的坐標，是經濟可行的定位方案。

1 測距

從節點定位采用的手段來看，可以分為兩大類算法，即基于距離(range-based)和非基于距離的算法(range-free)。距離無關的定位技術無須測量節點間的絕對距離或方位，降低了對節點硬件的要求，但相對于基于距離的定位算法定位精度較差。尤其當累計距離誤差導致每一跳平均距離估計偏差，致使定位精度變差^[5]。針對本文應用的要求，選擇定位精度較高的基于距離的算法。基于距離的算法根據測量節點間距離或方位時所采用的方法，分為以下四種定位方法：

a）基于到達角度AOA的定位^[6]。接收節點通過天線陣列或多個超聲波接收機感知發射節點信號的到達方向，計算接收節點與發射節點之間的相對方位或角度，再通過三角測量法計算出節點的位置。AOA測距技術易受外界環境影響，且AOA需要額外硬件（如節點安裝方向傳感器，增加成本且節點的體積變大），在硬件尺寸和功耗上不適用于大規模的傳感器網絡。

b）基于RSSI定位^[7]。已知發射節點的發射信號強度，接收節點根據接收到的信號強度計算出信號的傳播損耗，利用理論和經驗模型將傳輸損耗轉換為距離，再利用已有的算法計算出節點的位置。雖然在實驗環境中RSSI表現出良好的特性，但是在現實環境中，溫度、障礙物、傳播模式等條件往往都是變化的，使得該技術在實際應用中仍然存在困難。

c）基于到達時間TOA的定位^[8]。已知信號的傳播速度，根據信號的傳播時間來計算節點間的距離，然后利用已有算法計算出節點的位置。基于TOA的定位精度高，但要求節點間保持精確的時間同步，因此對傳感器節點的硬件和功耗提出了較高的要求。

d）基于到達時間差TDOA的定位^[9，10]。發射節點同時發射兩種不同傳播速度的無線信號，接收節點根據兩種信號到達時間差以及已知這兩種信號的傳播速度，計算兩個節點之間的距離，再通過已有的定位算法計算出節點的位置。TDOA技術對硬件的要求高，成本和能耗使得該技術對低能耗的傳感器網絡提出了挑戰。但是TDOA技術測距誤差小，有較高的精度。

四種方法相比，TDOA與TOA實現簡單，無須額外的設備且性能良好；而TDOA與TOA相比在處理延時、non-LOS傳播有較好的性能^[10]。本文選擇了TDOA的測距方法，具體方法可以參考文獻[10]。

2 定位

無線傳感器節點的定位又可以分為集中式定位和分布式定位。集中式定位法是先將網絡中所有信息匯聚到一個中心節點，中心節點利用這些信息計算出每個節點的位置后，再把位置信息發送給相應的各個節點。這種方法的優點是定位精度較高，但是中心節點及其周圍的節點由于通信量過大，電能的消耗過快，當電能耗盡后會導致整個網絡與中心節點不能進行信息交互。另外，中心節點需要處理大量的數據，并且存在中心節點的選取和更換等問題。如果中心節點更換過于頻繁，勢必會引起網絡的不穩定甚至癱瘓。分布式定位法是利用網絡中節點之間的信息交互，由各個節點自行確定各自的位置。這種方法通過控制信息的泛洪把信息控制在一定范圍之內，減少了網絡通信量；信息的處理和計算分布到了網絡中的每個節點，避免了中心節點的選擇，這樣就大大提高了定位的效率。本文采取了無信標節點的分布式定位算法^[11]，定位過程主要分為以下四步：

a）網絡初始化。定位算法開始時，每個節點發出一個包括自己ID、跳數值為0的廣播信息，它們周圍所有跳數為1的鄰居收到該信息，將節點的距離信息、ID和跳數記錄下來，并將收到信息包的跳數加1，再向自己的鄰居廣播。每個節點廣播可以聽到所有節點的列表，這個過程一直持續下去，節點之間通過交互控制消息知道其鄰居節點的數目。該節點及其相鄰節點中具有最大連通度的節點被選為簇頭，當度數相同時則選擇ID小的作為簇頭節點，反復進行以上過程，直到所有的節點都加入某個簇。為了控制簇的大小范圍，可設定簇的節點跳數。為了防止廣播信息的無限循環，只有最新收到的信息才被重新廣播。信息不是最新的指該節點已經收到某個參考節點的廣播，而且最近收到的信息包中的跳數大于或等于存儲器中存儲的到該參考節點的跳數。

簇群形成后，網絡中的節點大致分為簇頭節點、普通節點及網關節點三種，如圖1所示。

b）局部坐標系的建立。當網絡初始化后，則要確定所有簇的局部相對坐標系，并在每一個簇內根據節點間的距離信息計算節點的相對位置坐標。首先，確定簇內坐標系的坐標原點和坐標軸，再根據每個簇內節點存儲的鄰居節點距離信息，計算簇內其他節點的相對位置坐標。具體步驟如下：

（a）選擇連通度最大的節點為簇頭節點N1，并設置簇頭節點的局部坐標為(0，0)，設置跳數。

（b）在簇頭節點通信半徑內，選擇距離其最遠的節點N2坐標為(0，d12)。這樣保證建立的簇可以覆蓋較大的區域。

（c）同時選擇在N1、N2通信半徑內，且它們距離之和最遠的節點N3，并且滿足N1、N2、N3不在一條直線上。根據三個點之間的距離d12、d13、d23，計算N3的坐標為(d13 cos α，d13 sin α)。其中，α=∠N3N1N2，cos α=(d212+d213-d223) / (2×d12×d13)。這種方法確定的N3節點可以避免形成的三角形過于扁平，會給其他節點的定位帶來較大誤差。使用N1、N2、N3建立的坐標系如圖2所示，并把N1、N2、N3標記為已經確定坐標系的點。

（d）三邊測量法^[12]建立其他未知節點在局部坐標系中的位置。如圖3所示，坐標系建立的情況下確定N4的坐標。距離信息為d12、d13、d23、d14、d24、d34，則xN4=d14 cos β，若γ=｜β-α｜時，yN4=d14 sin β；否則yN4=-d14 sin β。其中：β=∠N4N1N2，γ=∠N3N1N4，cos β=(d212+d214-d224) / (2×d12×d14)，cos γ=(d214+d213-d234) / (2×d13×d14)。此時把N4標記為已經確定坐標系的點。

（e）簇中的其他節點根據建立的坐標系及與已經建立坐標的點之間的距離信息，按照（d）的方法確定其相對位置坐標。

對所有簇中的節點按照上述方法確定相對局部坐標。

圖4的仿真實驗圖為10 km×10 km的區域隨機布放100個節點，通信半徑為1.5 km。圖中三角形代表按照步驟（a）選擇連通度最大的節點為簇頭節點，并按照步驟（b）（c）選擇其余兩個頂點構成三角形并采用它們進行局部坐標系的建立。紅色的圓代表三個頂點通信半徑能夠覆蓋的區域；淡灰色的線代表在通信半徑內能夠相互通信的節點。

c）迭代求精。在局部坐標建立以后，提供本簇內每個節點的初始位置估計。在求精階段，節點嘗試提高位置估計精度。節點通過測量到本簇內所有鄰居的距離并依此進行位置計算來更新自己的位置。該算法引入權值來提高求精階段的性能。設某個節點(xi，yi)，它到本簇內其他節點的距離為d1，d2，d3，…，dn。那么存在下面的公式：

(x1-xi)2+(y1-yi)2=d21



(xn-xi)2+(yn-yi)2=d2n（1）

從第一個方程開始分別減去最后一個方程，得

x21-x2n-2(x1-xn)xi+

y21-y2n-2(y1-yn)yi=d21-d2n



x2n-1-x2n-2(xn-1-xn)xi+y2n-1-y2n-

2(yn-1-yn)yi=d2n-1-d2n（2）

線性化后的方程表示為AX=b。其中：

A=2(x1-xn)2(y1-yn)



2（xn-1-xn）2(y1-yn)

b=x21-x2n+y21-y2n+d21-d2n



x2n-1-x2n+y2n-1-y2n+d2n-1-d2n，X=xi

yi

線性化后的方程組可以采用最小二乘（LS）算法求解出定位節點的估計位置X^=(ATA)-1 ATb。

上面討論的是在權值相等情況下的求精過程。本文根據每個測量值的可靠性，在最小二乘中采用不同的權值，用于提高定位精度。節點間距離越近權值越大，距離越遠或跳數越大權值越小，這是因為距離近的節點間測距誤差越小。殘差加權平方和函數為

f(X)=W 2(AX-b)2（3）

其中：W 2為加權矩陣。本文使用wij=1 /hop2ij，即當節點間距離為1－hop時，wij=1，節點間距離為2－hop時，wij=1 / 4等。

d）全局坐標系的建立。當網絡中各簇均建立局部相對坐標系后，再采用類似于局部坐標原點的選取方法，選擇相鄰簇最多、最穩定的子簇作為整體相對坐標參照系，并依此對其他各簇進行坐標變換，從而得到節點全局相對坐標。

簇間的坐標轉換要求利用兩個坐標系中相互重疊的節點坐標，即圖1所示的網關節點，且網關節點至少達到兩個以上。坐標變換方式包括平移、旋轉、鏡像。根據坐標點到兩個坐標軸的相對距離，計算出平移參數；根據坐標點相對于坐標軸的斜率，計算出其他坐標軸相對于參考坐標軸的旋轉角度。經過旋轉平移后，如果坐標軸的方向相反，則需要鏡像變換。算法類似(SPA)^[2，11]中的節點坐標變換的計算，如圖5所示。其中：（a）為參考坐標系；（b）為待變換的坐標系；（c）為以參考系為準，待變換坐標系的變換。

所有簇的坐標系都按照這種方式，使得所有坐標軸的方向都與參考坐標軸的方向一致，并且根據平移、旋轉、鏡像參數，對原局部坐標系中的點進行變化，計算它們在參考坐標系下的坐標。這樣就得到了全局坐標系。

圖6中(a)代表參考坐標系；(b)代表待轉換的某簇節點局部坐標系（兩圖中的三個三角形標記的節點為網關節點，用來計算坐標系的轉換參數，其余節點為普通節點）；(c)代表將某一簇的局部坐標系統一到參考坐標軸的方向，并且根據變換參數，對原局部坐標系中的點進行變化，星號標記的節點為變換后在參考坐標系下的坐標。

3 仿真結果及分析

為了檢驗算法的性能，本文使用MATLAB仿真工具對提出的定位方案進行了一系列仿真計算，并從求精過程對定位精度的影響和通信半徑對定位精度的影響兩個方面進行了仿真分析。

3.1 定位誤差分析

實驗1 為驗證求精算法對定位精度的提高，本文進行了仿真實驗。圖7中仿真分析的網絡模型的主要參數如下：網絡規模是200個節點，平均分布在10 km×10 km的矩形范圍內，并以節點間的距離作為節點實際距離，然后再在節點實際距離上加入隨機高斯噪聲（作為測量誤差）作為節點間的測量距離參數。圖7(a)為按照第2章a）的方法確立的某一簇的節點，包括簇頭節點以及距離它兩跳范圍內的節點；(b)把這一簇的節點提取出來；(c)為按照第2章b）的方法在這個簇當中確定局部坐標系（其中，虛線代表確定的橫坐標）；(d)為簇內所有節點局部坐標的建立；(e)為未使用求精過程的定位誤差（圓圈代表定位后的坐標；線段代表針對沒有加入噪聲精確定位的結果的偏離誤差）；(f)為使用求精過程定位的誤差。從(e)與(f)的對比可以看出，求精算法對定位精度有了明顯的提高。

為了更準確地說明求精過程對定位精度的影響，本文還進行了定量分析。網絡模型同上，進行100 次的仿真實驗，且進行平均定位誤差統計。平均定位誤差，設節點i的估計坐標與真實坐標在二維情況下的距離差值為Δdi，則N個未知位置節點的網絡平均定位誤差為

Δ=(1 / N) Ni=1Δdi（4）

實驗結果如圖8所示。從圖中可以看出，當測量誤差一定時，無迭代定位精度與節點數目無關，定位誤差較為穩定，且誤差較大。而采用迭代求精定位時，定位誤差隨著簇內節點數目的增加，明顯減小，定位精度有顯著的提高。由此可見，采用本文所用節點定位算法具有較高的定位精度。

實驗2 不同的通信半徑對定位精度的影響如圖9所示。網絡模型的主要參數如下：網絡規模是200個節點，平均分布在10 km×10 km的矩形范圍內，并以節點間的距離作為節點實際距離，然后再在節點實際距離上加入隨機高斯噪聲（作為測量誤差）作為節點間的測量距離參數。圖9（a）的通信半徑為1 km；（b）的通信半徑為1.2 km；（c）的通信半徑為1.5 km；（d）的通信半徑為2 km。從這幾幅圖的比較可以看到，通信半徑越大，網絡的連通度越大。

從圖10可以看到通信半徑越大定位精度越高，但是通信半徑的不斷增大，導致了能量消耗過大，而且對定位精度影響變小。在實際應用中可以考慮折中，通過上面的分析在本實驗選取了通信半徑為1.5 km。

3.2 結果分析

1）定位精度 位置估計的精度是設計定位算法始終追求的目標，它直接影響后續的網絡傳輸和監測性能。影響定位精度的因素主要包括測距誤差和定位計算帶來的誤差。由于測距誤差是由硬件設備決定，不同的測距技術具有不同的誤差特征。本文采用實際距離加上高斯噪聲作為測距參數。定位誤差方面，采用基于距離的無信標節點分布式定位算法。由上述分析結果可以看到，達到了較好的定位精度。

2）通信半徑 該半徑的提高導致網絡平均連接度的提高，而連通度的提高不僅會影響部署網絡范圍而且會帶來節點之間通信沖突。因此這也是一個評價指標。

針對不同的應用環境，還有各種各樣的條件需要考慮，如節點密度、功耗、輔助硬件、節點成本等，這些都是影響評價一個定位系統好壞的標準。

4 結束語

本文主要以水下應用為背景，提出了一種可實現網絡規模升級的分布式無信標網絡節點自定位機制。通過實驗仿真計算，驗證了該定位機制的合理性，同時對定位精度因素進行了分析。這種算法的特點是無須額外的硬件支持，是無線傳感器網絡節點定位的一種可選方案。位置信息是傳感器節點消息中不可缺少的部分，為水下事件位置報告、目標跟蹤、地理路由、網絡管理等系統功能提供了有力的技術支持。

參考文獻：

[1]LANGENDOEN K， REIJERS N.Distributed localization in wireless sensor networks: a quantitative comparison[J]. Computer Networks， ，2003，43(4):499-518.

[2]YOUSSEF A，AGRAWALA A.Accurate anchor-free node localization in wireless sensor networks[C]//Proc of the 24th I PCCC.2005:465-470.

[3]CHENG X， THAELER A， XUE G， et al .TPS: a time-based positioning scheme for outdoor sensor networks[C]//Proc of IEEE Confe-rence on Computer， Communications(INFOCOM).Hong Kong：[s.n.]，2004.

[4]ZHOU Zhong， CUI Jun-hong.Localization for large-scale underwater sensor networks，UbiNet-TR06-04[R].[S.l.]:UCONN CSE，2006:1-18.

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

[6]NICULESCU D， NATH B. Ad hoc positioning system (APS) using AoA[C]// Proc ofIEEE INFOCOM. San Francisco:IEEE Computer and Communications Societies， 2003：1734-1743.

[7]GIROD L， BYCHOVSKIY V， ELSON J， et al. Locating tiny sensors in time and space:a case study [C]//WERNER B.Proc of IEEE Int’l Conf on Computer Design: VLSI in Computers and Processors. Freiburg: IEEE Computer Society， 2002： 214-219.

[8]DENIS B， PIERROTJ-B.Joint distributed synchronization and positioning in UWB Ad hoc networks using TOA [J]. IEEE Trans on Microwave Theory and Techniques，2006，154(4):1896-1911.

[9]GIROD L， ESTRIN D. Robust range estimation using acoustic and multimodal sensing[C]// Proc ofIEEE/RSJ Int’l Conf on Intelligent Robots and Systems (IROS’01).Maui: IEEE Robotics and Automation Society， 2001：1312-1320.

[10]CHEN Hong-yang， DENG Ping. A robust location algorithm with biased extended Kalman filtering of TDOA data for wireless sensor networks[M].[S.l.]:IEEE， 2005:883-886.

[11]CAPKUN S， HAMDI M， HUBAUX JP.GPS-free positioning in mobile Ad hoc networks[C]//Proc of Hawaii International Conference on System Sciences.Maui:[s.n.]，2001:3481-3940.

[12]NICULESCU D， NATH B. DV based positioning in Ad hoc networks[J].Journal of Telecommunication Systems， 2003，22(1/4):267-280.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文