無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)自定位算法的實(shí)際應(yīng)用研究*

劉 俞

（馬鞍山職業(yè)技術(shù)學(xué)院計(jì)算機(jī)系，安徽 馬鞍山243031）

引言

無線傳感器網(wǎng)絡(luò)［1］是將大量的具有無線通信能力的傳感器節(jié)點(diǎn)部署在監(jiān)測區(qū)域中，這些節(jié)點(diǎn)在部署完成后的短時(shí)間內(nèi)通過無線通信方式自組織形成一個(gè)多跳的網(wǎng)絡(luò)系統(tǒng)，然后立即進(jìn)入運(yùn)行狀態(tài)，所有節(jié)點(diǎn)協(xié)同工作實(shí)施監(jiān)測任務(wù).由于無線傳感器網(wǎng)絡(luò)與傳統(tǒng)監(jiān)測技術(shù)相比具有部署速度快、所需基礎(chǔ)設(shè)施少、精度高和生存周期長等優(yōu)勢，近年來，無線傳感器網(wǎng)絡(luò)在各種大規(guī)模環(huán)境監(jiān)測、安全監(jiān)測等系統(tǒng)中得到了廣泛的應(yīng)用，如森林防火監(jiān)測、空氣污染監(jiān)測、地震監(jiān)測預(yù)警、車輛定位跟蹤、緊急救災(zāi)搶險(xiǎn)等.

其中，節(jié)點(diǎn)定位技術(shù)是無線傳感器網(wǎng)絡(luò)中的關(guān)鍵支撐技術(shù).首先，它是無線傳感器網(wǎng)絡(luò)其它關(guān)鍵技術(shù)的基礎(chǔ)，如路由技術(shù)中路由路徑的建立與優(yōu)化就必須建立在節(jié)點(diǎn)已完成定位的基礎(chǔ)上;另外，位置信息是構(gòu)成監(jiān)測數(shù)據(jù)的重要部分，傳感器節(jié)點(diǎn)所獲取的數(shù)據(jù)的有效性和可靠性需要建立在定位準(zhǔn)確性的基礎(chǔ)上.根據(jù)定位機(jī)制的不同，現(xiàn)有的無線傳感器網(wǎng)絡(luò)自身定位算法有range－based和range－free 兩類［2］:前者是基于測距的定位算法，需要利用測距技術(shù)測量節(jié)點(diǎn)間的距離或角度，典型的測距技術(shù)有RSSI，TOA，TDOA和AOA，算法對硬件的要求高，定位精度較高;后者則與距離無關(guān)，是利用網(wǎng)絡(luò)的連通性進(jìn)行定位，有質(zhì)心、DV－Hop、APIT、LMAP 等典型算法，算法對硬件的要求低，定位精度相對較低.

1 山區(qū)景點(diǎn)環(huán)境監(jiān)測與游客安全監(jiān)測系統(tǒng)的提出

我國地域遼闊，有眾多的山區(qū)旅游景觀，如:安徽黃山、四川九寨溝、黑龍江大小興安嶺等.這些景點(diǎn)的旅游價(jià)值體現(xiàn)在其環(huán)境的原始性.因此，其生態(tài)環(huán)境、動(dòng)植物資源的保護(hù)就顯得尤為重要.其中，環(huán)境監(jiān)測是實(shí)現(xiàn)環(huán)境保護(hù)的重要手段.目前，無線傳感器網(wǎng)絡(luò)技術(shù)被越來越多地運(yùn)用在環(huán)境監(jiān)測中，其主要原因是利用無線傳感器網(wǎng)絡(luò)來完成環(huán)境監(jiān)測有以下幾方面的優(yōu)勢:1）網(wǎng)絡(luò)的部署速度快，傳感器節(jié)點(diǎn)的體積與功耗很小，因此它對被監(jiān)測區(qū)域的環(huán)境和人員的影響很小;2）傳感器節(jié)點(diǎn)具有分布區(qū)域廣、密度高、精度高以及較為穩(wěn)定的特點(diǎn)，不同區(qū)域的節(jié)點(diǎn)可以將自身采集到的監(jiān)測數(shù)據(jù)篩選融合后，通過優(yōu)化后的路由路徑傳送到監(jiān)控基站，使得監(jiān)控者能實(shí)時(shí)了解整個(gè)被監(jiān)測區(qū)域的情況.另外，監(jiān)控者也可以根據(jù)需要向網(wǎng)絡(luò)節(jié)點(diǎn)發(fā)布控制指令，接收到指令的節(jié)點(diǎn)會(huì)做出及時(shí)響應(yīng)，因此，無線傳感器網(wǎng)絡(luò)的監(jiān)測范圍廣、探測精度高、效率高;3）傳感器節(jié)點(diǎn)本身具有一定的計(jì)算能力和存儲(chǔ)能力，相鄰的節(jié)點(diǎn)可以通過無線通信相互聯(lián)系相互配合來實(shí)現(xiàn)監(jiān)測，因此無線傳感器網(wǎng)絡(luò)的監(jiān)測具有較高的穩(wěn)定性.正是因?yàn)闊o線傳感器網(wǎng)絡(luò)具備以上的優(yōu)勢，從而使其成為當(dāng)今環(huán)境監(jiān)測應(yīng)用的首選.

另外，山區(qū)景點(diǎn)通常地勢險(xiǎn)要，地理情況復(fù)雜，每年都有許多旅游者在山區(qū)遇險(xiǎn)失蹤，由于地域廣闊，地勢復(fù)雜，因此，很難對遇險(xiǎn)者的位置進(jìn)行定位，造成了無法開展救援的情況，從而導(dǎo)致了人員的傷亡.利用無線傳感器網(wǎng)絡(luò)則可以對進(jìn)入山區(qū)景點(diǎn)的游客進(jìn)行實(shí)時(shí)定位，使得監(jiān)控者能隨時(shí)了解每名游客每一時(shí)刻所處的位置，當(dāng)發(fā)生意外情況時(shí)，救援者能在第一時(shí)間趕到遇險(xiǎn)游客的位置實(shí)施救援，所以利用無線傳感器網(wǎng)絡(luò)進(jìn)行游客安全監(jiān)測成了保證游客人身安全的重要措施.

2 監(jiān)測系統(tǒng)中的節(jié)點(diǎn)定位算法

2.1 對監(jiān)測系統(tǒng)中節(jié)點(diǎn)定位算法選擇的分析

根據(jù)定位機(jī)制的不同［2］，現(xiàn)有的無線傳感器網(wǎng)絡(luò)自身定位算法有range－based和range－free 兩類，前者需要通過對信號的物理測量來計(jì)算未知節(jié)點(diǎn)與錨節(jié)點(diǎn)之間的角度或距離，因此這種算法對節(jié)點(diǎn)的硬件要求很高.例如，在TOA 方法和TDOA 方法中，節(jié)點(diǎn)需要配備射頻信號與超聲波信號收發(fā)的硬件裝置;在AOA 方法中，節(jié)點(diǎn)需要測量接收到的由其它節(jié)點(diǎn)發(fā)射的無線信號的到達(dá)角度，因此節(jié)點(diǎn)需要配備具有角度測量能力的天線裝置;在RSSI 方法中，節(jié)點(diǎn)需要配備收發(fā)射頻信號及測量其能量衰減的硬件裝置.由上可見，采用range－based 類型的定位算法，所需的節(jié)點(diǎn)硬件成本很高，從而導(dǎo)致了整個(gè)無線傳感器網(wǎng)絡(luò)的成本過高，可行性不強(qiáng).同時(shí)，在山區(qū)環(huán)境中，巖石、樹木、植被等物體會(huì)對信號產(chǎn)生遮蓋、衰減和散射，這些情況會(huì)直接引起信號的接收端產(chǎn)生嚴(yán)重的測量誤差，從而導(dǎo)致節(jié)點(diǎn)的定位誤差增大.另外，天氣情況包括雨、雪、霧、濕度、溫度等因素也會(huì)影響信號的傳輸，不同天氣情況會(huì)造成不同的測距誤差.因此，由于這些外界因素的干擾，使range－based 定位方法失去了定位精度高的優(yōu)越性.綜合以上的情況分析可以發(fā)現(xiàn)，range－based 定位方法并不適合在山區(qū)景點(diǎn)環(huán)境監(jiān)測與游客安全監(jiān)測系統(tǒng)中使用.

DV－h(huán)op 定位算法和質(zhì)心定位算法是兩種典型的range－free 定位方法，在這種類型的定位方法中，節(jié)點(diǎn)是通過網(wǎng)絡(luò)的連通性，來估算與其它節(jié)點(diǎn)間的距離，當(dāng)一個(gè)節(jié)點(diǎn)獲取到與足夠多的鄰近已定位節(jié)點(diǎn)的距離信息后，再根據(jù)具體算法進(jìn)行自身的位置計(jì)算，從而實(shí)現(xiàn)定位.因此，節(jié)點(diǎn)在定位過程中不再需要通過對信號的物理測量來計(jì)算節(jié)點(diǎn)間的角度或距離信息，這使得傳感器節(jié)點(diǎn)不需要信號的收發(fā)和角度測量天線等附加硬件模塊的支持，在減少了成本的同時(shí)也降低了能耗.其次，range－free 定位方法受外部環(huán)境影響較小，算法復(fù)雜度低，容易實(shí)現(xiàn)，從而能夠有效地延長整個(gè)網(wǎng)絡(luò)的生存期并且降低網(wǎng)絡(luò)的成本.另外，雖然DV－h(huán)op 定位算法和質(zhì)心定位算法沒有range－based 定位方法的定位精度高，但是它在定位過程中受外部環(huán)境影響很小，在各種不同的環(huán)境中都很適用，穩(wěn)定性高，并且山區(qū)景點(diǎn)環(huán)境監(jiān)測與游客安全監(jiān)測對于節(jié)點(diǎn)的定位精度要求并不是很高，比如定位誤差在10m 范圍內(nèi)都可以接受.因此，利用DV－h(huán)op 定位算法和質(zhì)心定位算法作為山區(qū)景點(diǎn)環(huán)境監(jiān)測與游客安全監(jiān)測系統(tǒng)的定位支持算法較為合理可行.

2.2 DV－h(huán)op 定位算法與質(zhì)心定位算法

DV－Hop 定位算法［3］是目前較為常用的一種定位算法，其基本思想是利用節(jié)點(diǎn)與節(jié)點(diǎn)間的多跳機(jī)制，通過無線通信與節(jié)點(diǎn)的協(xié)同工作，測算出網(wǎng)絡(luò)平均每跳距離，每個(gè)未知節(jié)點(diǎn)在與其它節(jié)點(diǎn)的通信過程中，記錄下自身與周圍鄰近錨節(jié)點(diǎn)相隔的最小跳數(shù)值，然后用此最小跳數(shù)值與網(wǎng)絡(luò)平均每跳距離相乘得出它與相應(yīng)的錨節(jié)點(diǎn)的相隔距離，當(dāng)未知節(jié)點(diǎn)計(jì)算得出與3 個(gè)或3 個(gè)以上的錨節(jié)點(diǎn)的相隔距離后，再利用三邊測量法或最大似然估計(jì)法計(jì)算出未知節(jié)點(diǎn)的位置坐標(biāo)［4］.此定位算法使用網(wǎng)絡(luò)平均每跳距離代替節(jié)點(diǎn)間的實(shí)際距離，對節(jié)點(diǎn)的硬件要求低，實(shí)現(xiàn)簡單.

DV－Hop 算法的定位過程:所有節(jié)點(diǎn)（包括錨節(jié)點(diǎn)和未知節(jié)點(diǎn)）利用已有的距離矢量路由協(xié)議進(jìn)行通信，所有未知節(jié)點(diǎn)獲得與錨節(jié)點(diǎn)的相隔跳數(shù)，所有錨節(jié)點(diǎn)獲得其它錨節(jié)點(diǎn)的位置坐標(biāo)及與其的相隔跳數(shù)，每個(gè)錨節(jié)點(diǎn)通過自身的位置坐標(biāo)值和獲取到的其它錨節(jié)點(diǎn)的位置坐標(biāo)值，計(jì)算出自己與其它每個(gè)錨節(jié)點(diǎn)間的距離值，然后分別用每個(gè)距離值除以對應(yīng)的最小跳數(shù)值，將得到的所有的結(jié)果取平均值即作為網(wǎng)絡(luò)平均每跳距離值，隨后每個(gè)錨節(jié)點(diǎn)將其計(jì)算得出的網(wǎng)絡(luò)平均每跳距離值向網(wǎng)絡(luò)廣播.每個(gè)未知節(jié)點(diǎn)只保存第一個(gè)達(dá)到的數(shù)據(jù)值，再將此值與所記錄的每個(gè)跳數(shù)值相乘，從而分別估算出自身與每個(gè)鄰近錨節(jié)點(diǎn)的距離.當(dāng)未知節(jié)點(diǎn)獲得與足夠多的錨節(jié)點(diǎn)的距離值后，再執(zhí)行三邊測量或最大似然估計(jì)法進(jìn)行計(jì)算，從而完成自身定位.

質(zhì)心定位算法［5］是一種基于網(wǎng)絡(luò)連通性的定位算法，其基本思想是利用平面幾何中對多邊形質(zhì)心的定義，即對于一個(gè)密度均勻的多邊形，它的幾何中心即為質(zhì)心，此多邊形各個(gè)頂點(diǎn)坐標(biāo)的平均值就是質(zhì)心的坐標(biāo).質(zhì)心定位算法就是將此定義應(yīng)用于無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的定位，即若某個(gè)未知節(jié)點(diǎn)能獲取到3 個(gè)或3 個(gè)以上錨節(jié)點(diǎn)的信號，則認(rèn)為自身處于這些錨節(jié)點(diǎn)所構(gòu)成的多邊形的中心位置，接下來計(jì)算出這些錨節(jié)點(diǎn)坐標(biāo)的平均值作為自己的估計(jì)位置坐標(biāo)［6］.此定位算法的計(jì)算量小，不需要節(jié)點(diǎn)間進(jìn)行大量的通信，硬件簡單，功耗低，容易實(shí)現(xiàn).

質(zhì)心算法的定位過程:每個(gè)錨節(jié)點(diǎn)都周期性地向網(wǎng)絡(luò)廣播一個(gè)數(shù)據(jù)包，其格式為（id，x，y），其中id是自身在網(wǎng)絡(luò)中的標(biāo)識號，x和y 是其位置坐標(biāo)值.當(dāng)一個(gè)未知節(jié)點(diǎn)在預(yù)設(shè)的時(shí)間內(nèi)接收到來自某個(gè)錨節(jié)點(diǎn)的數(shù)據(jù)包的個(gè)數(shù)達(dá)到事先已設(shè)定的閾值后，則該未知節(jié)點(diǎn)確認(rèn)與此錨節(jié)點(diǎn)相連通，若此未知節(jié)點(diǎn)獲得與自身相連通的錨節(jié)點(diǎn)個(gè)數(shù)達(dá)到3 個(gè)或3 個(gè)以上，則執(zhí)行質(zhì)心定位算法，計(jì)算出這些錨節(jié)點(diǎn)的質(zhì)心坐標(biāo)作為自身的位置坐標(biāo).

2.3 DV－h(huán)op 定位算法在山區(qū)景點(diǎn)環(huán)境監(jiān)測系統(tǒng)中的應(yīng)用分析

首先，通過飛行器或人工方式在整個(gè)景區(qū)范圍內(nèi)播撒大量的用于環(huán)境監(jiān)測的節(jié)點(diǎn)，這里稱之為基礎(chǔ)節(jié)點(diǎn)，在節(jié)點(diǎn)部署過程中對于環(huán)境監(jiān)測的重點(diǎn)監(jiān)測區(qū)域和事故易發(fā)的危險(xiǎn)區(qū)域，可通過人工方式加大節(jié)點(diǎn)的播撒密度，其中包括小部分?jǐn)y帶有GPS 定位設(shè)備可自身精確定位的錨節(jié)點(diǎn)，以及大部分的未定位的普通節(jié)點(diǎn).節(jié)點(diǎn)部署完成后，錨節(jié)點(diǎn)通過自身的定位裝置進(jìn)行精確定位，然后未定位的普通節(jié)點(diǎn)以鄰近的錨節(jié)點(diǎn)為參考點(diǎn)，通過節(jié)點(diǎn)間協(xié)同工作，執(zhí)行DV－h(huán)op 算法對自身進(jìn)行定位.未定位的普通節(jié)點(diǎn)A 的定位過程，如圖1 所示.

圖1 山區(qū)景點(diǎn)環(huán)境監(jiān)測區(qū)域中的節(jié)點(diǎn)定位示意圖

環(huán)境監(jiān)測系統(tǒng)為了實(shí)現(xiàn)實(shí)時(shí)監(jiān)測的目的，利用傳感器節(jié)點(diǎn)周期性地對監(jiān)測區(qū)域環(huán)境的數(shù)據(jù)進(jìn)行采樣，采樣的周期和數(shù)據(jù)的種類可根據(jù)具體需要調(diào)整.系統(tǒng)可以設(shè)置兩種工作模式:根據(jù)某特定情況下的具體需要，由監(jiān)控中心向網(wǎng)絡(luò)廣播特定的指令，節(jié)點(diǎn)獲取指令后進(jìn)行分析執(zhí)行，從而作出及時(shí)的響應(yīng)，這種工作模式為被動(dòng)工作模式;另外，當(dāng)監(jiān)測區(qū)域中的某個(gè)傳感器節(jié)點(diǎn)獲取的數(shù)據(jù)超過預(yù)設(shè)的警界值時(shí)，例如在圖2 中，A 節(jié)點(diǎn)采集到的溫度數(shù)據(jù)為60 ℃（假設(shè)預(yù)設(shè)的溫度警界值為50 ℃）時(shí)，該節(jié)點(diǎn)將主動(dòng)把采集到的數(shù)據(jù)和自身位置信息通過已形成的路由路徑發(fā)送到監(jiān)控中心，這種工作模式為主動(dòng)工作模式，如圖2 所示.

圖2 山區(qū)景點(diǎn)環(huán)境監(jiān)測網(wǎng)絡(luò)工作示意圖

通過這兩種工作模式，系統(tǒng)既能完成常規(guī)監(jiān)測的數(shù)據(jù)采樣和數(shù)據(jù)收集，也能實(shí)時(shí)獲取突發(fā)事件的信息，對產(chǎn)生異常數(shù)據(jù)的地區(qū)進(jìn)行定位，從而能及時(shí)采取措施應(yīng)對突發(fā)事件.

2.4 質(zhì)心定位算法在游客安全監(jiān)測系統(tǒng)中的應(yīng)用分析

對于進(jìn)入景區(qū)的每個(gè)游客，事先佩帶無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)設(shè)備，稱為游客節(jié)點(diǎn)，在整個(gè)游覽過程中，游客節(jié)點(diǎn)周期性地工作，此時(shí)用于山區(qū)景點(diǎn)環(huán)境監(jiān)測的所有基礎(chǔ)節(jié)點(diǎn)都已完成了自身的定位，游客節(jié)點(diǎn)便可利用周圍的基礎(chǔ)節(jié)點(diǎn)作為參考節(jié)點(diǎn)進(jìn)行自身定位，隨后游客節(jié)點(diǎn)將計(jì)算得到的位置信息發(fā)送至監(jiān)控中心，使得監(jiān)控中心能實(shí)時(shí)了解每個(gè)游客每一時(shí)刻所處的位置.

在對游客節(jié)點(diǎn)進(jìn)行定位時(shí)采用質(zhì)心定位算法，因?yàn)橛慰褪遣粩嘁苿?dòng)的，所以對于游客節(jié)點(diǎn)需要進(jìn)行周期性的定位，例如，游客節(jié)點(diǎn)每隔5 min 發(fā)送一個(gè)請求定位信息，當(dāng)周圍節(jié)點(diǎn)收到此信息后，便將自身的位置坐標(biāo)發(fā)送給此游客節(jié)點(diǎn)，當(dāng)游客節(jié)點(diǎn)接收到的鄰居節(jié)點(diǎn)的位置信息的個(gè)數(shù)達(dá)到設(shè)定的閾值后，便執(zhí)行質(zhì)心定位算法，估算出自身的位置坐標(biāo)，并將位置信息通過路由路徑發(fā)送到監(jiān)控中心，如圖3 所示.

圖3 游客節(jié)點(diǎn)定位及游客安全監(jiān)測系統(tǒng)工作示意圖

另外，當(dāng)監(jiān)控中心通過游客節(jié)點(diǎn)發(fā)來的位置信息發(fā)現(xiàn)游客已進(jìn)入危險(xiǎn)區(qū)域后，則可以通過網(wǎng)絡(luò)向此游客節(jié)點(diǎn)發(fā)送一個(gè)危險(xiǎn)警報(bào)信號，使游客獲知危險(xiǎn)，及時(shí)改變游覽路線，回到安全區(qū)域.

3 小結(jié)

本文以無線傳感器網(wǎng)絡(luò)在實(shí)際監(jiān)測系統(tǒng)中的應(yīng)用為背景，探討了DV－Hop 定位算法與質(zhì)心定位算法在實(shí)際環(huán)境中應(yīng)用的可行性.通過分析發(fā)現(xiàn)range－based定位方法并不適用于山區(qū)環(huán)境中的定位，而range－free 定位方法則比較適用.在山區(qū)景點(diǎn)環(huán)境監(jiān)測系統(tǒng)中采用DV－h(huán)op 定位算法進(jìn)行節(jié)點(diǎn)定位，在游客安全監(jiān)測系統(tǒng)中采用質(zhì)心定位算法進(jìn)行節(jié)點(diǎn)定位.經(jīng)分析，這種方案有較高的可行性，在今后的研究中，將繼續(xù)完善系統(tǒng)的設(shè)計(jì)，提升系統(tǒng)的性能.

［1］孫利民，李建中，陳渝，等.無線傳感器網(wǎng)絡(luò)［M］.北京:清華大學(xué)出版社，2005.

［2］王福豹，史龍，任豐原.無線傳感器網(wǎng)絡(luò)的自身定位系統(tǒng)和算法［J］.軟件學(xué)報(bào)，2005，16（5）:857－868.

［3］Nicolescu D，Nath B.DV Based Positioning in Ad Hoc Networks［J］.Journal of Telecommunication Systems，2003，22（1）:267－280.

［4］劉俞.無線傳感器網(wǎng)絡(luò)中基于傳輸時(shí)間比的定位算法及改進(jìn)［J］.重慶科技學(xué)院學(xué)報(bào):自然科學(xué)版，2012，14（2）:142－145.

［5］Bulusu N，John H.GPS－less Low Cost Out－Door Localization for very small devices［J］.IEEE Personal Communications，2000，7（5）:28－34.

［6］劉俞.無線傳感器網(wǎng)絡(luò)中基于復(fù)合權(quán)值的質(zhì)心定位改進(jìn)算法［J］.遼東學(xué)院學(xué)報(bào):自然科學(xué)版，2012，19（1）:31－35.