基于連通性的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法探究

何劍海

0 引言

無(wú)線傳感器網(wǎng)絡(luò)技術(shù)體現(xiàn)了無(wú)線通信技術(shù)的成熟以及嵌入式系統(tǒng)的快速發(fā)展。同時(shí)，該領(lǐng)域也顯示了計(jì)算機(jī)科學(xué)、電子工程技術(shù)、無(wú)線通信技術(shù)、環(huán)境科學(xué)以及智能交通等學(xué)科之間的相互協(xié)作和發(fā)展。其包含廣闊的創(chuàng)新發(fā)展空間，將信息數(shù)據(jù)的采集、傳輸以及處理融為一體，幫助人們?cè)诙虝r(shí)間內(nèi)迅速獲取周圍信息，最大程度地認(rèn)識(shí)、改造世界。該技術(shù)可應(yīng)用于眾多領(lǐng)域與社會(huì)生活的方方面面，具有廣闊的發(fā)展空間，因而一度成為熱門研究課題。

1 無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法的特點(diǎn)概述

1.1 無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法的研究意義

當(dāng)前，環(huán)境科學(xué)、農(nóng)業(yè)、醫(yī)療以及戰(zhàn)場(chǎng)等領(lǐng)域?qū)?jié)點(diǎn)定位的需求極其廣泛，故其成為無(wú)線傳感器網(wǎng)絡(luò)技術(shù)中的一個(gè)關(guān)鍵問題。

在環(huán)境科學(xué)中，長(zhǎng)期在戶外采集數(shù)據(jù)信息因?yàn)槔脽o(wú)線傳感網(wǎng)絡(luò)從而變得格外方便，特別是土壤成分的監(jiān)測(cè)、水源環(huán)境的監(jiān)測(cè)、對(duì)野生動(dòng)物的跟蹤以及植物生長(zhǎng)情況等方面的研究。這些場(chǎng)景對(duì)無(wú)線傳感器網(wǎng)絡(luò)技術(shù)的應(yīng)用，只有利用定位傳感節(jié)點(diǎn)的準(zhǔn)確性才能幫助人們?cè)谔厥獾沫h(huán)境中有效實(shí)現(xiàn)目的。在農(nóng)業(yè)中，為了達(dá)到監(jiān)測(cè)數(shù)據(jù)的準(zhǔn)確性，也需要系統(tǒng)利用節(jié)點(diǎn)定位技術(shù)來對(duì)數(shù)據(jù)信息進(jìn)行掌控。在醫(yī)療中，該技術(shù)體積小、攜帶方便，能夠?qū)崿F(xiàn)在每個(gè)患者身上配備一個(gè)無(wú)線傳感節(jié)點(diǎn)的目的。而通過節(jié)點(diǎn)定位技術(shù)，醫(yī)生能夠及時(shí)發(fā)現(xiàn)并第一時(shí)間解決問題。此外，還能利用節(jié)點(diǎn)傳感器統(tǒng)計(jì)的信息數(shù)據(jù)來判斷患者的病情。在戰(zhàn)場(chǎng)中，無(wú)線傳感器網(wǎng)絡(luò)技術(shù)備受重視，其隱蔽性與組織快速的優(yōu)點(diǎn)特別適于對(duì)戰(zhàn)場(chǎng)進(jìn)行監(jiān)控。一般部隊(duì)可以記住飛機(jī)在空中由上而下來散播傳感節(jié)點(diǎn)，以便在整個(gè)戰(zhàn)場(chǎng)區(qū)域中形成一個(gè)規(guī)模極大的無(wú)線傳感網(wǎng)絡(luò)。不過，這些節(jié)點(diǎn)的位置因?yàn)椴豢深A(yù)示只能利用定位技術(shù)來尋找獲得。

1.2 無(wú)線傳感器節(jié)點(diǎn)定位算法的基本定義

無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位基本的定義指通過已經(jīng)知道位置的錨節(jié)點(diǎn)來獲取未知節(jié)點(diǎn)的具體位置。節(jié)點(diǎn)定位的算法主要分為2個(gè)步驟：

（1）通過未知的節(jié)點(diǎn)和錨節(jié)點(diǎn)之間的某種形式的通信來測(cè)算出該未知節(jié)點(diǎn)與相近錨節(jié)點(diǎn)的距離，或者二者間的信號(hào)所形成的角度，或者二者之間連通性的信息。

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

1.3 當(dāng)前研究中所存在的問題

在無(wú)線傳感器網(wǎng)絡(luò)技術(shù)節(jié)點(diǎn)定位問題的研究中，較為常用的分類方式包括基于測(cè)距的算法和無(wú)需測(cè)距的算法。在實(shí)際應(yīng)用中，基于測(cè)距的定位方法為減小測(cè)距過程中的誤差，期間加入了過多復(fù)雜的處理機(jī)制，相應(yīng)就增加了計(jì)算與通信的開銷。因而可以說該法雖然在定位精度中具優(yōu)勢(shì)，但是對(duì)于一些功能簡(jiǎn)單而成本低的傳感節(jié)點(diǎn)來說并不適用。而無(wú)需測(cè)距的方法則是利用節(jié)點(diǎn)間的聯(lián)通的信息來進(jìn)行定位。基于連通性的節(jié)點(diǎn)定位算法的優(yōu)勢(shì)則正體現(xiàn)了計(jì)算量小、成本低廉的優(yōu)勢(shì)，對(duì)普通傳感節(jié)點(diǎn)有限的計(jì)算能力來說極為實(shí)用。

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

2 無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法的分類

基于連通性的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法包括以下幾類：

2.1 質(zhì)心算法

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

2.2 MDS-MAP定位算法

該節(jié)點(diǎn)定位算法是由密蘇里大學(xué)在MDS心理測(cè)量學(xué)與精神物理學(xué)的基礎(chǔ)上，通過對(duì)數(shù)據(jù)的分析而正式提出的集中式的算法。其在對(duì)節(jié)點(diǎn)定位中主要是利用節(jié)點(diǎn)之間信息的連通性。這種算法所具有的集中計(jì)算性質(zhì)使其在眾多應(yīng)用中受到限制。雖然已經(jīng)提出了改進(jìn)方案，但是仍然因?yàn)榫植砍霈F(xiàn)的誤差而造成整體誤差。不過對(duì)于一些不規(guī)則的網(wǎng)絡(luò)來說，其定位精度要遠(yuǎn)比其他的定位算法好。

2.3 APIT節(jié)點(diǎn)定位算法

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

2.4 APS系列定位算法

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

2.5 Amor phous定位算法

該節(jié)點(diǎn)定位算法由麻省理工大學(xué)提出，采用的是一種與DV-Hop獲得錨節(jié)點(diǎn)的條數(shù)極為類似的方法，該節(jié)點(diǎn)定位算法則是通過特殊的計(jì)算公式來獲得。其具有缺點(diǎn)，不僅需要提前預(yù)支網(wǎng)絡(luò)的平均連通度，還需要較高的節(jié)點(diǎn)密度來實(shí)現(xiàn)。

2.6 基于有序的MCL定位算法

該節(jié)點(diǎn)定位算法是由美國(guó)弗吉尼亞大學(xué)提出，其源于在機(jī)器人定位中應(yīng)用比較廣泛的SMC算法，通過移動(dòng)性來不斷提高定位的精度。該方法即使在錨節(jié)點(diǎn)的比例極低且網(wǎng)絡(luò)的傳輸極不穩(wěn)定的情況下依然能夠進(jìn)行準(zhǔn)確的定位。

2.7 基于節(jié)點(diǎn)部署信息的節(jié)點(diǎn)定位算法

該節(jié)點(diǎn)定位算法由美國(guó)雪城大學(xué)提出，雖然針對(duì)極大的計(jì)算量已經(jīng)提出了集中簡(jiǎn)化的方法，但當(dāng)前該法的最大問題還是因其過于嚴(yán)格的前提假設(shè)致使其在實(shí)踐中難以利用。

3 結(jié)語(yǔ)

總之，因?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)定位技術(shù)在各個(gè)領(lǐng)域中的廣泛運(yùn)用，人們?nèi)諠u重視對(duì)其進(jìn)行研究，不斷對(duì)節(jié)點(diǎn)定位算法進(jìn)行改進(jìn)，在提高定位精度的同時(shí)，減小其受環(huán)境的制約性。而定位技術(shù)的發(fā)展與改變也必然使得無(wú)線傳感器網(wǎng)絡(luò)技術(shù)對(duì)全球的發(fā)展產(chǎn)生積極影響。

［1］李善亮，黃劉生，吳俊敏，等.基于連通性的傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法［J］.計(jì)算機(jī)工程，2008（7）

［2］張強(qiáng).基于連通性的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位技術(shù)研究［D］.天津大學(xué)，2011

［3］朱軍.無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位研究［J］.電腦知識(shí)與技術(shù)，2011（17）

［4］王軍.無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法設(shè)計(jì)模式探討［A］.2011全國(guó)無(wú)線及移動(dòng)通信學(xué)術(shù)大會(huì)論文集［C］，2011

［5］李吉彪，劉丹.無(wú)線傳感器網(wǎng)絡(luò)中異常節(jié)點(diǎn)快速定位算法研究［J］.計(jì)算機(jī)仿真，2011（8）