基于距離的分布式無(wú)線傳感器網(wǎng)絡(luò)定位算法

摘 要：針對(duì)水下無(wú)線傳感器節(jié)點(diǎn)的定位問題進(jìn)行研究，提出了一種可實(shí)現(xiàn)網(wǎng)絡(luò)規(guī)模升級(jí)的分布式無(wú)信標(biāo)節(jié)點(diǎn)的自定位算法。該定位算法無(wú)須額外的硬件支持，僅采用節(jié)點(diǎn)間的距離信息建立相對(duì)坐標(biāo)系，確定各節(jié)點(diǎn)的相對(duì)位置。詳細(xì)介紹了該算法的實(shí)現(xiàn)過程，通過仿真討論了求精過程、通信半徑等對(duì)定位誤差的影響，并驗(yàn)證了該算法的合理性。為目標(biāo)跟蹤、地理路由、網(wǎng)絡(luò)管理等系統(tǒng)功能提供了有力的技術(shù)支持。

關(guān)鍵詞：無(wú)線傳感器網(wǎng)絡(luò)； 節(jié)點(diǎn)定位； 基于距離； 分布式

中圖分類號(hào)：TP393.03 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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

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

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

目前已經(jīng)提出很多種節(jié)點(diǎn)定位的方法，并且都有很大的發(fā)展。根據(jù)定位的過程中是否使用信標(biāo)節(jié)點(diǎn)，把定位算法分為基于信標(biāo)節(jié)點(diǎn)的定位算法和無(wú)信標(biāo)節(jié)點(diǎn)的定位算法?；谛艠?biāo)節(jié)點(diǎn)的定位中，以信標(biāo)節(jié)點(diǎn)作為參考點(diǎn)，而且要求信標(biāo)節(jié)點(diǎn)均勻分布于檢測(cè)區(qū)域且信標(biāo)節(jié)點(diǎn)的數(shù)目達(dá)到所有節(jié)點(diǎn)數(shù)目的百分之十，甚至是百分之二十，才能達(dá)到較好的定位效果^[4]。而針對(duì)很多應(yīng)用環(huán)境，無(wú)法達(dá)到這種要求，如在水下布放大量位置精確的信標(biāo)節(jié)點(diǎn)，實(shí)現(xiàn)難度很大。因此本文采取了無(wú)信標(biāo)節(jié)點(diǎn)的定位算法，提出了基于距離的分布式無(wú)信標(biāo)的節(jié)點(diǎn)自定位機(jī)制。通過網(wǎng)絡(luò)內(nèi)部節(jié)點(diǎn)之間的相互測(cè)距和信息交換，形成一套全網(wǎng)節(jié)點(diǎn)的坐標(biāo)，是經(jīng)濟(jì)可行的定位方案。

1 測(cè)距

從節(jié)點(diǎn)定位采用的手段來看，可以分為兩大類算法，即基于距離(range-based)和非基于距離的算法(range-free)。距離無(wú)關(guān)的定位技術(shù)無(wú)須測(cè)量節(jié)點(diǎn)間的絕對(duì)距離或方位，降低了對(duì)節(jié)點(diǎn)硬件的要求，但相對(duì)于基于距離的定位算法定位精度較差。尤其當(dāng)累計(jì)距離誤差導(dǎo)致每一跳平均距離估計(jì)偏差，致使定位精度變差^[5]。針對(duì)本文應(yīng)用的要求，選擇定位精度較高的基于距離的算法?；诰嚯x的算法根據(jù)測(cè)量節(jié)點(diǎn)間距離或方位時(shí)所采用的方法，分為以下四種定位方法：

a）基于到達(dá)角度AOA的定位^[6]。接收節(jié)點(diǎn)通過天線陣列或多個(gè)超聲波接收機(jī)感知發(fā)射節(jié)點(diǎn)信號(hào)的到達(dá)方向，計(jì)算接收節(jié)點(diǎn)與發(fā)射節(jié)點(diǎn)之間的相對(duì)方位或角度，再通過三角測(cè)量法計(jì)算出節(jié)點(diǎn)的位置。AOA測(cè)距技術(shù)易受外界環(huán)境影響，且AOA需要額外硬件（如節(jié)點(diǎn)安裝方向傳感器，增加成本且節(jié)點(diǎn)的體積變大），在硬件尺寸和功耗上不適用于大規(guī)模的傳感器網(wǎng)絡(luò)。

b）基于RSSI定位^[7]。已知發(fā)射節(jié)點(diǎn)的發(fā)射信號(hào)強(qiáng)度，接收節(jié)點(diǎn)根據(jù)接收到的信號(hào)強(qiáng)度計(jì)算出信號(hào)的傳播損耗，利用理論和經(jīng)驗(yàn)?zāi)Ｐ蛯鬏敁p耗轉(zhuǎn)換為距離，再利用已有的算法計(jì)算出節(jié)點(diǎn)的位置。雖然在實(shí)驗(yàn)環(huán)境中RSSI表現(xiàn)出良好的特性，但是在現(xiàn)實(shí)環(huán)境中，溫度、障礙物、傳播模式等條件往往都是變化的，使得該技術(shù)在實(shí)際應(yīng)用中仍然存在困難。

c）基于到達(dá)時(shí)間TOA的定位^[8]。已知信號(hào)的傳播速度，根據(jù)信號(hào)的傳播時(shí)間來計(jì)算節(jié)點(diǎn)間的距離，然后利用已有算法計(jì)算出節(jié)點(diǎn)的位置?；赥OA的定位精度高，但要求節(jié)點(diǎn)間保持精確的時(shí)間同步，因此對(duì)傳感器節(jié)點(diǎn)的硬件和功耗提出了較高的要求。

d）基于到達(dá)時(shí)間差TDOA的定位^[9，10]。發(fā)射節(jié)點(diǎn)同時(shí)發(fā)射兩種不同傳播速度的無(wú)線信號(hào)，接收節(jié)點(diǎn)根據(jù)兩種信號(hào)到達(dá)時(shí)間差以及已知這兩種信號(hào)的傳播速度，計(jì)算兩個(gè)節(jié)點(diǎn)之間的距離，再通過已有的定位算法計(jì)算出節(jié)點(diǎn)的位置。TDOA技術(shù)對(duì)硬件的要求高，成本和能耗使得該技術(shù)對(duì)低能耗的傳感器網(wǎng)絡(luò)提出了挑戰(zhàn)。但是TDOA技術(shù)測(cè)距誤差小，有較高的精度。

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

2 定位

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

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

簇群形成后，網(wǎng)絡(luò)中的節(jié)點(diǎn)大致分為簇頭節(jié)點(diǎn)、普通節(jié)點(diǎn)及網(wǎng)關(guān)節(jié)點(diǎn)三種，如圖1所示。

b）局部坐標(biāo)系的建立。當(dāng)網(wǎng)絡(luò)初始化后，則要確定所有簇的局部相對(duì)坐標(biāo)系，并在每一個(gè)簇內(nèi)根據(jù)節(jié)點(diǎn)間的距離信息計(jì)算節(jié)點(diǎn)的相對(duì)位置坐標(biāo)。首先，確定簇內(nèi)坐標(biāo)系的坐標(biāo)原點(diǎn)和坐標(biāo)軸，再根據(jù)每個(gè)簇內(nèi)節(jié)點(diǎn)存儲(chǔ)的鄰居節(jié)點(diǎn)距離信息，計(jì)算簇內(nèi)其他節(jié)點(diǎn)的相對(duì)位置坐標(biāo)。具體步驟如下：

（a）選擇連通度最大的節(jié)點(diǎn)為簇頭節(jié)點(diǎn)N1，并設(shè)置簇頭節(jié)點(diǎn)的局部坐標(biāo)為(0，0)，設(shè)置跳數(shù)。

（b）在簇頭節(jié)點(diǎn)通信半徑內(nèi)，選擇距離其最遠(yuǎn)的節(jié)點(diǎn)N2坐標(biāo)為(0，d12)。這樣保證建立的簇可以覆蓋較大的區(qū)域。

（c）同時(shí)選擇在N1、N2通信半徑內(nèi)，且它們距離之和最遠(yuǎn)的節(jié)點(diǎn)N3，并且滿足N1、N2、N3不在一條直線上。根據(jù)三個(gè)點(diǎn)之間的距離d12、d13、d23，計(jì)算N3的坐標(biāo)為(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節(jié)點(diǎn)可以避免形成的三角形過于扁平，會(huì)給其他節(jié)點(diǎn)的定位帶來較大誤差。使用N1、N2、N3建立的坐標(biāo)系如圖2所示，并把N1、N2、N3標(biāo)記為已經(jīng)確定坐標(biāo)系的點(diǎn)。

（d）三邊測(cè)量法^[12]建立其他未知節(jié)點(diǎn)在局部坐標(biāo)系中的位置。如圖3所示，坐標(biāo)系建立的情況下確定N4的坐標(biāo)。距離信息為d12、d13、d23、d14、d24、d34，則xN4=d14 cos β，若γ=｜β-α｜時(shí)，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)。此時(shí)把N4標(biāo)記為已經(jīng)確定坐標(biāo)系的點(diǎn)。

（e）簇中的其他節(jié)點(diǎn)根據(jù)建立的坐標(biāo)系及與已經(jīng)建立坐標(biāo)的點(diǎn)之間的距離信息，按照（d）的方法確定其相對(duì)位置坐標(biāo)。

對(duì)所有簇中的節(jié)點(diǎn)按照上述方法確定相對(duì)局部坐標(biāo)。

圖4的仿真實(shí)驗(yàn)圖為10 km×10 km的區(qū)域隨機(jī)布放100個(gè)節(jié)點(diǎn)，通信半徑為1.5 km。圖中三角形代表按照步驟（a）選擇連通度最大的節(jié)點(diǎn)為簇頭節(jié)點(diǎn)，并按照步驟（b）（c）選擇其余兩個(gè)頂點(diǎn)構(gòu)成三角形并采用它們進(jìn)行局部坐標(biāo)系的建立。紅色的圓代表三個(gè)頂點(diǎn)通信半徑能夠覆蓋的區(qū)域；淡灰色的線代表在通信半徑內(nèi)能夠相互通信的節(jié)點(diǎn)。

c）迭代求精。在局部坐標(biāo)建立以后，提供本簇內(nèi)每個(gè)節(jié)點(diǎn)的初始位置估計(jì)。在求精階段，節(jié)點(diǎn)嘗試提高位置估計(jì)精度。節(jié)點(diǎn)通過測(cè)量到本簇內(nèi)所有鄰居的距離并依此進(jìn)行位置計(jì)算來更新自己的位置。該算法引入權(quán)值來提高求精階段的性能。設(shè)某個(gè)節(jié)點(diǎn)(xi，yi)，它到本簇內(nèi)其他節(jié)點(diǎn)的距離為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）

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

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）算法求解出定位節(jié)點(diǎn)的估計(jì)位置X^=(ATA)-1 ATb。

上面討論的是在權(quán)值相等情況下的求精過程。本文根據(jù)每個(gè)測(cè)量值的可靠性，在最小二乘中采用不同的權(quán)值，用于提高定位精度。節(jié)點(diǎn)間距離越近權(quán)值越大，距離越遠(yuǎn)或跳數(shù)越大權(quán)值越小，這是因?yàn)榫嚯x近的節(jié)點(diǎn)間測(cè)距誤差越小。殘差加權(quán)平方和函數(shù)為

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

其中：W 2為加權(quán)矩陣。本文使用wij=1 /hop2ij，即當(dāng)節(jié)點(diǎn)間距離為1－hop時(shí)，wij=1，節(jié)點(diǎn)間距離為2－hop時(shí)，wij=1 / 4等。

d）全局坐標(biāo)系的建立。當(dāng)網(wǎng)絡(luò)中各簇均建立局部相對(duì)坐標(biāo)系后，再采用類似于局部坐標(biāo)原點(diǎn)的選取方法，選擇相鄰簇最多、最穩(wěn)定的子簇作為整體相對(duì)坐標(biāo)參照系，并依此對(duì)其他各簇進(jìn)行坐標(biāo)變換，從而得到節(jié)點(diǎn)全局相對(duì)坐標(biāo)。

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

所有簇的坐標(biāo)系都按照這種方式，使得所有坐標(biāo)軸的方向都與參考坐標(biāo)軸的方向一致，并且根據(jù)平移、旋轉(zhuǎn)、鏡像參數(shù)，對(duì)原局部坐標(biāo)系中的點(diǎn)進(jìn)行變化，計(jì)算它們?cè)趨⒖甲鴺?biāo)系下的坐標(biāo)。這樣就得到了全局坐標(biāo)系。

圖6中(a)代表參考坐標(biāo)系；(b)代表待轉(zhuǎn)換的某簇節(jié)點(diǎn)局部坐標(biāo)系（兩圖中的三個(gè)三角形標(biāo)記的節(jié)點(diǎn)為網(wǎng)關(guān)節(jié)點(diǎn)，用來計(jì)算坐標(biāo)系的轉(zhuǎn)換參數(shù)，其余節(jié)點(diǎn)為普通節(jié)點(diǎn)）；(c)代表將某一簇的局部坐標(biāo)系統(tǒng)一到參考坐標(biāo)軸的方向，并且根據(jù)變換參數(shù)，對(duì)原局部坐標(biāo)系中的點(diǎn)進(jìn)行變化，星號(hào)標(biāo)記的節(jié)點(diǎn)為變換后在參考坐標(biāo)系下的坐標(biāo)。

3 仿真結(jié)果及分析

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

3.1 定位誤差分析

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

為了更準(zhǔn)確地說明求精過程對(duì)定位精度的影響，本文還進(jìn)行了定量分析。網(wǎng)絡(luò)模型同上，進(jìn)行100 次的仿真實(shí)驗(yàn)，且進(jìn)行平均定位誤差統(tǒng)計(jì)。平均定位誤差，設(shè)節(jié)點(diǎn)i的估計(jì)坐標(biāo)與真實(shí)坐標(biāo)在二維情況下的距離差值為Δdi，則N個(gè)未知位置節(jié)點(diǎn)的網(wǎng)絡(luò)平均定位誤差為

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

實(shí)驗(yàn)結(jié)果如圖8所示。從圖中可以看出，當(dāng)測(cè)量誤差一定時(shí)，無(wú)迭代定位精度與節(jié)點(diǎn)數(shù)目無(wú)關(guān)，定位誤差較為穩(wěn)定，且誤差較大。而采用迭代求精定位時(shí)，定位誤差隨著簇內(nèi)節(jié)點(diǎn)數(shù)目的增加，明顯減小，定位精度有顯著的提高。由此可見，采用本文所用節(jié)點(diǎn)定位算法具有較高的定位精度。

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

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

3.2 結(jié)果分析

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

2）通信半徑 該半徑的提高導(dǎo)致網(wǎng)絡(luò)平均連接度的提高，而連通度的提高不僅會(huì)影響部署網(wǎng)絡(luò)范圍而且會(huì)帶來節(jié)點(diǎn)之間通信沖突。因此這也是一個(gè)評(píng)價(jià)指標(biāo)。

針對(duì)不同的應(yīng)用環(huán)境，還有各種各樣的條件需要考慮，如節(jié)點(diǎn)密度、功耗、輔助硬件、節(jié)點(diǎn)成本等，這些都是影響評(píng)價(jià)一個(gè)定位系統(tǒng)好壞的標(biāo)準(zhǔn)。

4 結(jié)束語(yǔ)

本文主要以水下應(yīng)用為背景，提出了一種可實(shí)現(xiàn)網(wǎng)絡(luò)規(guī)模升級(jí)的分布式無(wú)信標(biāo)網(wǎng)絡(luò)節(jié)點(diǎn)自定位機(jī)制。通過實(shí)驗(yàn)仿真計(jì)算，驗(yàn)證了該定位機(jī)制的合理性，同時(shí)對(duì)定位精度因素進(jìn)行了分析。這種算法的特點(diǎn)是無(wú)須額外的硬件支持，是無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位的一種可選方案。位置信息是傳感器節(jié)點(diǎn)消息中不可缺少的部分，為水下事件位置報(bào)告、目標(biāo)跟蹤、地理路由、網(wǎng)絡(luò)管理等系統(tǒng)功能提供了有力的技術(shù)支持。

參考文獻(xiàn)：

[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]孫利民，李建中，陳渝，等.無(wú)線傳感器網(wǎng)絡(luò)[M].北京：清華大學(xué)出版社，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.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文