基于連通性的無線傳感器網絡節點定位算法探究

何劍海

0 引言

無線傳感器網絡技術體現了無線通信技術的成熟以及嵌入式系統的快速發展。同時，該領域也顯示了計算機科學、電子工程技術、無線通信技術、環境科學以及智能交通等學科之間的相互協作和發展。其包含廣闊的創新發展空間，將信息數據的采集、傳輸以及處理融為一體，幫助人們在短時間內迅速獲取周圍信息，最大程度地認識、改造世界。該技術可應用于眾多領域與社會生活的方方面面，具有廣闊的發展空間，因而一度成為熱門研究課題。

1 無線傳感器網絡節點定位算法的特點概述

1.1 無線傳感器網絡節點定位算法的研究意義

當前，環境科學、農業、醫療以及戰場等領域對節點定位的需求極其廣泛，故其成為無線傳感器網絡技術中的一個關鍵問題。

在環境科學中，長期在戶外采集數據信息因為利用無線傳感網絡從而變得格外方便，特別是土壤成分的監測、水源環境的監測、對野生動物的跟蹤以及植物生長情況等方面的研究。這些場景對無線傳感器網絡技術的應用，只有利用定位傳感節點的準確性才能幫助人們在特殊的環境中有效實現目的。在農業中，為了達到監測數據的準確性，也需要系統利用節點定位技術來對數據信息進行掌控。在醫療中，該技術體積小、攜帶方便，能夠實現在每個患者身上配備一個無線傳感節點的目的。而通過節點定位技術，醫生能夠及時發現并第一時間解決問題。此外，還能利用節點傳感器統計的信息數據來判斷患者的病情。在戰場中，無線傳感器網絡技術備受重視，其隱蔽性與組織快速的優點特別適于對戰場進行監控。一般部隊可以記住飛機在空中由上而下來散播傳感節點，以便在整個戰場區域中形成一個規模極大的無線傳感網絡。不過，這些節點的位置因為不可預示只能利用定位技術來尋找獲得。

1.2 無線傳感器節點定位算法的基本定義

無線傳感器網絡節點定位基本的定義指通過已經知道位置的錨節點來獲取未知節點的具體位置。節點定位的算法主要分為2個步驟：

（1）通過未知的節點和錨節點之間的某種形式的通信來測算出該未知節點與相近錨節點的距離，或者二者間的信號所形成的角度，或者二者之間連通性的信息。

（2）利用三邊測量方法、三角測量方法或者極大似然的估計方法來對某一未知節點的位置進行計算。這一方法的理論依據就是如若知道某一個節點與任意3個以上的參考點的距離，完全可以對該點的位置進行確定。三角測量法則指的是凡是知道任3個以上參考點與某一個節點的角度，就可以將該點的位置確定，這兩種方法極具相似性。

1.3 當前研究中所存在的問題

在無線傳感器網絡技術節點定位問題的研究中，較為常用的分類方式包括基于測距的算法和無需測距的算法。在實際應用中，基于測距的定位方法為減小測距過程中的誤差，期間加入了過多復雜的處理機制，相應就增加了計算與通信的開銷。因而可以說該法雖然在定位精度中具優勢，但是對于一些功能簡單而成本低的傳感節點來說并不適用。而無需測距的方法則是利用節點間的聯通的信息來進行定位?；谶B通性的節點定位算法的優勢則正體現了計算量小、成本低廉的優勢，對普通傳感節點有限的計算能力來說極為實用。

但目前基于連通性的定位算法大部分精度并不高，這也成為其亟待解決的問題。對此研究者們分別進行了復雜的計算與研究。

2 無線傳感器網絡節點定位算法的分類

基于連通性的無線傳感器網絡節點定位算法包括以下幾類：

2.1 質心算法

該節點定位算法是由美國的南加州大學提出的概念，其是基于連通性的無線傳感器網絡節點中最為簡單的一種定位算法。在該方法中，未知節點將錨節點發送傳遞的信息收集之后，來判斷自身能與具體的哪些錨節點互動信息。而后利用計算出的錨節點來對自己的位置進行判斷和定位。該方法只要將錨節點位置擺放恰當，就能使誤差減到最小，但隨即進行部署所取得的定位并不能取得理想的效果。

2.2 MDS-MAP定位算法

該節點定位算法是由密蘇里大學在MDS心理測量學與精神物理學的基礎上，通過對數據的分析而正式提出的集中式的算法。其在對節點定位中主要是利用節點之間信息的連通性。這種算法所具有的集中計算性質使其在眾多應用中受到限制。雖然已經提出了改進方案，但是仍然因為局部出現的誤差而造成整體誤差。不過對于一些不規則的網絡來說，其定位精度要遠比其他的定位算法好。

2.3 APIT節點定位算法

該節點定位算法由美國弗吉尼亞大學提出，其指的是若未知的節點存在于一個錨節點所組成的三角形中，那么這個三角形就包括了未知節點，那么在執行該定位算法時，每次未知節點每次都要選三個能通信的錨節點來測試，看該未知節點是否包含在由三個錨節點所圍成的三角形里。如此重復直到最后窮盡，對所有未知節點的三角形的相交區域確定，該區域的質心則是未知節點的位置。該定位算法一般在節點密度較高的情況下才會比較準。

2.4 APS系列定位算法

該節點定位算法由美國的路特葛斯大學提出，主要是利用了距離矢量路由與GPS定位原理相結合提出的算法。該算法又包括六種定位算法，其中DV-Hop是基于連通性的節點定位算法中最為經典的算法。

2.5 Amor phous定位算法

該節點定位算法由麻省理工大學提出，采用的是一種與DV-Hop獲得錨節點的條數極為類似的方法，該節點定位算法則是通過特殊的計算公式來獲得。其具有缺點，不僅需要提前預支網絡的平均連通度，還需要較高的節點密度來實現。

2.6 基于有序的MCL定位算法

該節點定位算法是由美國弗吉尼亞大學提出，其源于在機器人定位中應用比較廣泛的SMC算法，通過移動性來不斷提高定位的精度。該方法即使在錨節點的比例極低且網絡的傳輸極不穩定的情況下依然能夠進行準確的定位。

2.7 基于節點部署信息的節點定位算法

該節點定位算法由美國雪城大學提出，雖然針對極大的計算量已經提出了集中簡化的方法，但當前該法的最大問題還是因其過于嚴格的前提假設致使其在實踐中難以利用。

3 結語

總之，因為無線傳感器網絡定位技術在各個領域中的廣泛運用，人們日漸重視對其進行研究，不斷對節點定位算法進行改進，在提高定位精度的同時，減小其受環境的制約性。而定位技術的發展與改變也必然使得無線傳感器網絡技術對全球的發展產生積極影響。

［1］李善亮，黃劉生，吳俊敏，等.基于連通性的傳感器網絡節點定位算法［J］.計算機工程，2008（7）

［2］張強.基于連通性的無線傳感器網絡節點定位技術研究［D］.天津大學，2011

［3］朱軍.無線傳感器網絡節點定位研究［J］.電腦知識與技術，2011（17）

［4］王軍.無線傳感器網絡節點定位算法設計模式探討［A］.2011全國無線及移動通信學術大會論文集［C］，2011

［5］李吉彪，劉丹.無線傳感器網絡中異常節點快速定位算法研究［J］.計算機仿真，2011（8）