?

無(wú)線傳感器網(wǎng)絡(luò)靜態(tài)節(jié)點(diǎn)定位算法綜述

李建坡1,鐘鑫鑫1,徐 純2

(1.東北電力大學(xué)信息工程學(xué)院,吉林吉林132012;2.國(guó)家新聞出版廣電總局2021臺(tái),黑龍江齊齊哈爾161000)

摘 要:針對(duì)無(wú)線傳感器網(wǎng)絡(luò)靜態(tài)節(jié)點(diǎn)定位算法特點(diǎn),總結(jié)了無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位的基本原理、定位算法的最新進(jìn)展及其評(píng)價(jià)標(biāo)準(zhǔn)。從基于測(cè)距的靜態(tài)節(jié)點(diǎn)定位算法和無(wú)需測(cè)距的靜態(tài)節(jié)點(diǎn)定位算法兩個(gè)方面分類討論了典型的靜態(tài)節(jié)點(diǎn)定位算法,并對(duì)各算法的性能進(jìn)行歸納比較,說(shuō)明了目前算法存在的問(wèn)題,并提出未來(lái)發(fā)展趨勢(shì)。

關(guān)鍵詞:無(wú)線傳感器網(wǎng)絡(luò);靜態(tài)節(jié)點(diǎn)定位;綜述

無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks,WSN)是由部署在監(jiān)測(cè)區(qū)域內(nèi)大量的傳感器節(jié)點(diǎn)組成,通過(guò)無(wú)線通信方式形成的一個(gè)多跳的自組織網(wǎng)絡(luò)系統(tǒng),其目的是協(xié)作地感知、采集和處理網(wǎng)絡(luò)覆蓋區(qū)域中被感知對(duì)象的信息,并發(fā)送給觀察者。在WSN中,位置信息對(duì)傳感器網(wǎng)絡(luò)的監(jiān)測(cè)活動(dòng)至關(guān)重要,例如在軍事應(yīng)用、環(huán)境監(jiān)測(cè)、醫(yī)療保健、目標(biāo)監(jiān)測(cè)與跟蹤、智能交通、物流管理等許多應(yīng)用領(lǐng)域中,如何確定無(wú)線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)的位置信息(節(jié)點(diǎn)定位)成為必須解決的關(guān)鍵問(wèn)題之一[1-4]。從1992年AT&T Laboratories Cambridge開(kāi)發(fā)出室內(nèi)定位系統(tǒng)Active Badge至今[5],針對(duì)不同應(yīng)用領(lǐng)域,人們已經(jīng)設(shè)計(jì)了很多無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位系統(tǒng)和算法。但是,每種系統(tǒng)和算法都用來(lái)解決不同的問(wèn)題或支持不同的應(yīng)用,本文對(duì)WSN節(jié)點(diǎn)定位的基本原理和國(guó)內(nèi)外開(kāi)展的相關(guān)研究工作進(jìn)行了分析和總結(jié),本文著重分析了WSN節(jié)點(diǎn)定位的現(xiàn)狀和存在的問(wèn)題,明確今后的發(fā)展趨勢(shì),為WSN節(jié)點(diǎn)定位的廣大研究人員提供參考和借鑒。

1　WSN節(jié)點(diǎn)定位的分類

根據(jù)不同分類原則和網(wǎng)絡(luò)結(jié)構(gòu),常用的WSN節(jié)點(diǎn)定位算法可以進(jìn)行如下劃分:

(1)基于測(cè)距技術(shù)的定位和無(wú)需測(cè)距技術(shù)的定位

基于測(cè)距技術(shù)(Range-Based)的定位是通過(guò)獲得節(jié)點(diǎn)間的絕對(duì)距離或角度信息,使用三邊測(cè)量法[6]、三角測(cè)量法[7]、極大似然估計(jì)法[8]等算法計(jì)算節(jié)點(diǎn)位置。典型算法有基于RSS的定位算法[9]、基于TOA的定位算法[10,11]、基于TDOA的定位算法[10,11]、基于AOA的定位算法[10]、AHLos定位算法[12]、Cooperative ranging定位算法[13]、Two-Phase positioning定位算法[14]等。無(wú)需測(cè)距技術(shù)(Range-Free)的定位,不需要節(jié)點(diǎn)間的絕對(duì)距離或角度信息,僅根據(jù)網(wǎng)絡(luò)連通范圍、節(jié)點(diǎn)間的估計(jì)距離等信息實(shí)現(xiàn)定位。典型算法有DV-hop定位算法[15]、質(zhì)心算法[16]、APIT定位算法[17]、凸規(guī)劃定位算法[18]、MDS-MAP定位算法[19]、MCL定位算法[20]等。

(2)靜態(tài)節(jié)點(diǎn)定位和動(dòng)態(tài)節(jié)點(diǎn)定位

靜態(tài)節(jié)點(diǎn)定位指網(wǎng)絡(luò)中的所有節(jié)點(diǎn)位置均固定的定位方法。常用算法有AHLos定位算法[12]、DV-hop定位算法[15]、APIT定位算法[17]、凸規(guī)劃定位算法[18]、Amorphous定位算法[22]、SHARP定位算法[23]等。動(dòng)態(tài)節(jié)點(diǎn)定位指網(wǎng)絡(luò)中的部分或者全部節(jié)點(diǎn)處于移動(dòng)狀態(tài)的定位,包括錨節(jié)點(diǎn)移動(dòng)待定位節(jié)點(diǎn)靜止、錨節(jié)點(diǎn)靜止待定位節(jié)點(diǎn)移動(dòng)、錨節(jié)點(diǎn)和待定位節(jié)點(diǎn)均移動(dòng)。常用算法有DLS算法[24]、MBAL算法[25]、Constrained 3D算法[26]、MCL定位算法[20]、CDL算法[27]、3D-ADAL算法[28]等。

(3)集中式定位和分布式定位

集中式定位是指將需要的WSN節(jié)點(diǎn)信息傳送到某個(gè)中心節(jié)點(diǎn)進(jìn)行定位計(jì)算。典型的算法有Mapgrowing定位算法[29]、凸規(guī)劃定位算法[18]、SHARP定位算法[23]等。分布式定位是指依賴節(jié)點(diǎn)間的信息交換和協(xié)調(diào),由節(jié)點(diǎn)自行計(jì)算的定位方式。典型的算法有DV-Hop[15]、DV-distance定位算法[30]、APIT定位算法[17]、3D-ADAL算法[28]等。

(4)絕對(duì)定位和相對(duì)定位

絕對(duì)定位的定位結(jié)果是一個(gè)標(biāo)準(zhǔn)的坐標(biāo)位置,如經(jīng)緯度等。目前大部分WSN系統(tǒng)采用這種表示方式。相對(duì)定位通常以網(wǎng)絡(luò)中部分節(jié)點(diǎn)為參考,建立整個(gè)網(wǎng)絡(luò)的相對(duì)坐標(biāo)系統(tǒng)。典型的相對(duì)定位算法有Cooperative ranging定位算法[13]、SPA定位算法[31]、SHARP定位算法[23]等。有些算法,例如MDS-MAP算法[19],可以根據(jù)網(wǎng)絡(luò)配置情況實(shí)現(xiàn)絕對(duì)定位或相對(duì)定位。

(5)細(xì)粒度定位和粗粒度定位

根據(jù)接收信號(hào)強(qiáng)度、時(shí)間、方向和信號(hào)模式匹配等完成定位的稱為細(xì)粒度定位,可細(xì)分為基于距離的和基于方向性測(cè)量?jī)深?例如Active Badge[5]、AHLos定位算法[12]、Euclidean定位算法[15]等。根據(jù)節(jié)點(diǎn)接近度等完成的定位稱為粗粒度定位,例如DV-Hop定位算法[15]、SHARP定位算法[23]、Amorphous定位算法[22]等。

(6)一次計(jì)算定位和循環(huán)求精定位

一次計(jì)算定位是指根據(jù)接收的信息直接計(jì)算節(jié)點(diǎn)位置坐標(biāo),例如質(zhì)心算法[16]、APIT定位算法[17]、凸規(guī)劃定位算法[18]、Amorphous定位算法[22]等。循環(huán)求精定位算法是在起始階段得到節(jié)點(diǎn)位置的粗略估計(jì),在循環(huán)階段每個(gè)節(jié)點(diǎn)向其鄰居節(jié)點(diǎn)廣播它的位置估計(jì),并根據(jù)從鄰居節(jié)點(diǎn)接收的位置信息和節(jié)點(diǎn)間的測(cè)距結(jié)果重新計(jì)算自身位置,直至兩次計(jì)算得到的位置估值之差小于一定的域值。典型的算法有N-hop Multilateration Primitive定位算法[32]、Cooperative ranging定位算法[13]、Two-Phase positioning定位算法[14]等。

2　WSN靜態(tài)節(jié)點(diǎn)定位常用算法

本文將現(xiàn)有的WSN靜態(tài)節(jié)點(diǎn)定位算法按照節(jié)點(diǎn)分布特點(diǎn)分為基于測(cè)距的靜態(tài)節(jié)點(diǎn)定位算法和無(wú)需測(cè)距的靜態(tài)節(jié)點(diǎn)定位算法。

2.1 基于測(cè)距的靜態(tài)節(jié)點(diǎn)定位算法

2. 1. 1 基于RSS的定位算法

基于信號(hào)接收強(qiáng)度(Received Signal Strength,RSS)的節(jié)點(diǎn)定位[9]原理是將錨節(jié)點(diǎn)到未知節(jié)點(diǎn)間的信號(hào)強(qiáng)度衰減轉(zhuǎn)化為信號(hào)的傳播距離,然后利用經(jīng)驗(yàn)?zāi)Ｐ突蚶碚撃Ｐ蛯⑿盘?hào)的傳播損耗轉(zhuǎn)化為距離,從而計(jì)算出未知節(jié)點(diǎn)的位置。

該方法利用對(duì)接收無(wú)線信號(hào)強(qiáng)度的判斷即可比較準(zhǔn)確地估算出收發(fā)節(jié)點(diǎn)之間的距離,算法復(fù)雜度較低,對(duì)錨節(jié)點(diǎn)密度要求不高,是一種低功率、廉價(jià)的測(cè)距技術(shù),適用于大規(guī)模的無(wú)線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)定位。由于電磁波傳輸路徑中存在的多徑、繞射、障礙物干擾等因素的影響,都會(huì)對(duì)無(wú)線信號(hào)的傳輸模型產(chǎn)生不可避免的影響,一旦傳輸模型發(fā)生改變,那么按照模型計(jì)算無(wú)線信號(hào)的傳輸距離同信號(hào)強(qiáng)度衰減之間的關(guān)系將產(chǎn)生不可忽略的誤差,其測(cè)距誤差可達(dá)±50%[33]。

2. 1. 2 基于TOA的定位算法

基于到達(dá)時(shí)間(Time of Arrival,TOA)的定位算法[10,11]是指當(dāng)信號(hào)傳播的速度已知時(shí),根據(jù)其傳播時(shí)間來(lái)計(jì)算兩個(gè)節(jié)點(diǎn)間的距離,當(dāng)未知節(jié)點(diǎn)獲得與多個(gè)錨節(jié)點(diǎn)間的距離后,利用三邊測(cè)量法或其他方法計(jì)算未知節(jié)點(diǎn)的坐標(biāo)。

該方法需要節(jié)點(diǎn)間必須嚴(yán)格保證時(shí)間同步,而通常節(jié)點(diǎn)間距離較小,電信號(hào)又是以光速傳播,這都為節(jié)點(diǎn)間信號(hào)到達(dá)時(shí)間的精確測(cè)量增加了難度。

2. 1. 3 基于TDOA的定位算法

基于到達(dá)時(shí)間差(Time Difference of Arrival,TDOA)的定位算法[10,11]是指錨節(jié)點(diǎn)同時(shí)發(fā)射兩路速度不同的信號(hào),例如傳播速度為C1的無(wú)線電信號(hào)和傳播速度為C2的超聲波信號(hào),當(dāng)未知節(jié)點(diǎn)接收到兩路信號(hào)后,根據(jù)它們的到達(dá)時(shí)間差Δt,計(jì)算兩節(jié)點(diǎn)間的距離d,然后計(jì)算節(jié)點(diǎn)的位置坐標(biāo)。

由于該算法測(cè)量的是節(jié)點(diǎn)間的時(shí)間差,與TOA相比,不需要嚴(yán)格的時(shí)間同步,因而相對(duì)容易實(shí)現(xiàn),并且定位精度也更高。但是該算法受限于超聲波傳播距離有限(通常情況下WSN安裝的超聲波傳感器傳播距離均在10米以內(nèi),因而網(wǎng)絡(luò)需要密集部署)和非視距傳輸對(duì)超聲波信號(hào)傳播的影響,同時(shí)還要求傳感器節(jié)點(diǎn)具備感知兩種不同信號(hào)的能力。

2. 1. 4 基于AOA的定位算法

基于到達(dá)角度(Angle of Arrival,AOA)的定位算法[10]是利用接收節(jié)點(diǎn)上的陣列天線來(lái)感知發(fā)射信號(hào)的到達(dá)方向,計(jì)算錨節(jié)點(diǎn)與未知節(jié)點(diǎn)間的角度,然后利用交匯法計(jì)算節(jié)點(diǎn)的位置坐標(biāo)。該方法不需要嚴(yán)格的時(shí)間同步,且能額外提供節(jié)點(diǎn)的方位信息,但是易受環(huán)境影響,且節(jié)點(diǎn)需要配有陣列天線,硬件系統(tǒng)復(fù)雜,由于受到硬件尺寸及功耗的限制,不適用于大規(guī)模無(wú)線傳感器網(wǎng)絡(luò)。

另外,AOA信息還可以與TOA、TDOA信息一起使用成為混合定位法。采用混合定位法可以實(shí)現(xiàn)更高的精確度,減小誤差,或者可以降低對(duì)某一種測(cè)量參數(shù)數(shù)量的需求[34-36]。

2. 1. 5 AHLos定位算法

2001年,加州大學(xué)洛杉磯分校的Andreas Savvides等人提出了AHLos定位算法[12],該算法利用測(cè)距方法測(cè)量每個(gè)節(jié)點(diǎn)與其鄰居錨節(jié)點(diǎn)間的距離,根據(jù)鄰居錨節(jié)點(diǎn)的分布情況,利用相應(yīng)的原子多邊算法AM(Atomic Multilateration)、協(xié)作多邊算法CM(Collaborative Multilateration)和迭代多邊算法IM(Iterative Multilateration)計(jì)算未知節(jié)點(diǎn)的坐標(biāo),該算法的核心是迭代思想,將已定位的節(jié)點(diǎn)“升級(jí)”為錨節(jié)點(diǎn)投入新一輪的運(yùn)算,AHLos算法的迭代思想在獲得錨節(jié)點(diǎn)帶來(lái)的高計(jì)算精度的同時(shí),在一定程度上緩解了錨節(jié)點(diǎn)密度低時(shí)的節(jié)點(diǎn)定位問(wèn)題,但是將已定位的未知節(jié)點(diǎn)直接升級(jí)為錨節(jié)點(diǎn)可能會(huì)造成誤差累積,降低整體的定位精度。

文獻(xiàn)[37]將AHLos定位算法擴(kuò)展到三維空間,提出了ILAH-3D算法,通過(guò)采用加權(quán)最小二乘法和加入定位節(jié)點(diǎn)升級(jí)錨節(jié)點(diǎn)的驗(yàn)證條件來(lái)降低累積誤差,并根據(jù)三維空間中節(jié)點(diǎn)的各種位置關(guān)系,給出約束協(xié)作算法的執(zhí)行條件,然后結(jié)合升級(jí)的錨節(jié)點(diǎn)再進(jìn)行新一輪的定位算法。

2. 1. 6 N-hopMultilateration Primitive定位算法

2002年,Andreas Savvides等人在AHLos算法的基礎(chǔ)上提出了N-hop Multilateration Primitive定位算法[32],該算法對(duì)AHLos算法的協(xié)作多邊算法CM進(jìn)行了完善,給出了判定節(jié)點(diǎn)是否可參與協(xié)作多邊計(jì)算的充分條件,并使用卡爾曼濾波技術(shù)循環(huán)定位求精,減小了誤差積累。

首先根據(jù)判定條件,在網(wǎng)絡(luò)中生成多個(gè)由未知節(jié)點(diǎn)和信標(biāo)節(jié)點(diǎn)組成的超限制條件或限制條件完整的構(gòu)形,稱為協(xié)作子樹(shù)。每個(gè)協(xié)作子樹(shù)可相應(yīng)生成一組包括n個(gè)未知變量的至少n個(gè)非線性方程式,并且每個(gè)未知變量有唯一解,未被協(xié)作子樹(shù)包含的節(jié)點(diǎn)在整個(gè)算法的后階段處理;其次,根據(jù)信標(biāo)節(jié)點(diǎn)位置、節(jié)點(diǎn)間距離和網(wǎng)絡(luò)連通性信息對(duì)每個(gè)節(jié)點(diǎn)的位置進(jìn)行粗略估算,結(jié)果作為下一階段的輸入;最后,根據(jù)預(yù)設(shè)的定位精度,使用卡爾曼濾波技術(shù)在每個(gè)協(xié)作子樹(shù)范圍內(nèi)對(duì)上一階段的結(jié)果用分布式或集中式計(jì)算模式進(jìn)行循環(huán)求精。該方法突破了至少三個(gè)鄰居信標(biāo)節(jié)點(diǎn)才能定位的限制,提高了算法覆蓋度,缺點(diǎn)是循環(huán)求精的循環(huán)次數(shù)無(wú)法預(yù)知,錨節(jié)點(diǎn)必須部署在網(wǎng)絡(luò)邊緣。

2. 1. 7 DV-distance定位算法

文獻(xiàn)[15]和[30]提出了一種DV-distance定位算法,相鄰節(jié)點(diǎn)使用RSS測(cè)量節(jié)點(diǎn)間距離,然后利用相似于距離矢量路由方法傳播與錨節(jié)點(diǎn)的累計(jì)距離。當(dāng)未知節(jié)點(diǎn)獲得與三個(gè)或更多錨節(jié)點(diǎn)距離信息后使用三邊測(cè)量法進(jìn)行定位。該算法只適用于各向同性的密集網(wǎng)絡(luò)。實(shí)驗(yàn)表明,在網(wǎng)絡(luò)平均連通度為9,錨節(jié)點(diǎn)比例為10%,測(cè)距誤差小于10%的情況下,定位精度為20%,但是隨著測(cè)距誤差的增大,定位性能下降明顯。

2. 1. 8 Euclidean和DV-coordinate定位算法

Euclidean定位算法[15]和[30]給出了計(jì)算與錨節(jié)點(diǎn)相隔兩跳的未知節(jié)點(diǎn)位置的方法,該算法假設(shè)節(jié)點(diǎn)擁有使用RSS測(cè)量節(jié)點(diǎn)間距離的能力,錨節(jié)點(diǎn)首先廣播出一個(gè)包含自身ID和位置的信標(biāo)信號(hào),并將該信號(hào)的TTL域設(shè)置為2,即該信標(biāo)僅能傳送2跳。當(dāng)一個(gè)未知節(jié)點(diǎn)可從2個(gè)已知相互距離且與錨節(jié)點(diǎn)直接相鄰的節(jié)點(diǎn)處接收到該信號(hào),它就可以計(jì)算出自身與該錨節(jié)點(diǎn)的距離。當(dāng)未知節(jié)點(diǎn)獲得與3個(gè)或更多錨節(jié)點(diǎn)距離后再定位自身。該算法把用于定位的信標(biāo)節(jié)點(diǎn)由1跳擴(kuò)展到2跳,提高了算法的覆蓋度,降低了對(duì)錨節(jié)點(diǎn)密度要求,通信開(kāi)銷適當(dāng)。

在DV-coordinate定位算法[30]中,每個(gè)節(jié)點(diǎn)首先利用Euclidean定位算法計(jì)算兩跳鄰居節(jié)點(diǎn)的距離,以自身位置作為原點(diǎn)建立局部坐標(biāo)系統(tǒng)。然后相鄰節(jié)點(diǎn)交換信息,假如一個(gè)節(jié)點(diǎn)從鄰居節(jié)點(diǎn)那里接收到錨節(jié)點(diǎn)的信息并將其轉(zhuǎn)化為自身坐標(biāo)系統(tǒng)中的坐標(biāo)后,便可以估計(jì)自身的位置。

Euclidean和DV-coordinate定位算法雖然不受網(wǎng)絡(luò)各向異性的影響,但對(duì)測(cè)距精度、節(jié)點(diǎn)密度和錨節(jié)點(diǎn)密度非常敏感。實(shí)驗(yàn)表明,在網(wǎng)絡(luò)平均連通度為9,錨節(jié)點(diǎn)比例為20%,測(cè)距誤差小于10%的情況下,Euclidean和DV-coordinate的平均定位誤差分別為20%和80%。

2. 1. 9 DV-Bearing和DV-Radial定位算法

DV-Bearing和DV-Radial定位算法[30]提出了以逐跳方式跨越兩跳甚至三跳來(lái)計(jì)算與錨節(jié)點(diǎn)的相對(duì)角度,最后使用三角測(cè)量法定位。兩者的區(qū)別在于,DV-Bearing算法要求每個(gè)錨節(jié)點(diǎn)和未知節(jié)點(diǎn)都安裝有指南針,從而獲得絕對(duì)角度信息。實(shí)驗(yàn)表明,DV-Bearing和DV-Radial定位算法在網(wǎng)絡(luò)平均連通度為10. 5,錨節(jié)點(diǎn)比例為20%,AOA測(cè)量誤差小于5°的情況下,90%以上的節(jié)點(diǎn)可以實(shí)現(xiàn)定位,定位精度分別為40%和25%。

2. 1. 10 Cooperative ranging和Two-Phase定位算法

Cooperative ranging定位算法[13]和Two-Phase定位算法[14]都分為啟始和循環(huán)求精兩個(gè)階段。起始階段著重于獲得節(jié)點(diǎn)位置的粗略估算。而在循環(huán)求精階段,每一次循環(huán)開(kāi)始時(shí)每個(gè)節(jié)點(diǎn)向其鄰居節(jié)點(diǎn)廣播它的位置估算,并根據(jù)從鄰居節(jié)點(diǎn)接收的位置信息和節(jié)點(diǎn)間測(cè)距結(jié)果,重新執(zhí)行三邊測(cè)量,計(jì)算自身位置,直至位置更新的變化可接受時(shí)循環(huán)停止。

Cooperative ranging算法的起始階段又稱為TERRAIN (triangulation via extended range and redundant association of intermediate nodes)。首先在所有信標(biāo)節(jié)點(diǎn)上,根據(jù)節(jié)點(diǎn)間測(cè)距結(jié)果使用ABC算法(assumption based coordinates algorithm)建立局部坐標(biāo)系統(tǒng),然后將結(jié)果(以這個(gè)信標(biāo)節(jié)點(diǎn)為原點(diǎn)的局部網(wǎng)絡(luò)拓?fù)?傳播到整個(gè)網(wǎng)絡(luò)。未知節(jié)點(diǎn)根據(jù)它所獲得的網(wǎng)絡(luò)拓?fù)浯_定其與信標(biāo)節(jié)點(diǎn)的距離,使用三邊測(cè)量定位自身,然后進(jìn)入循環(huán)求精階段。

與Cooperative ranging算法不同,為了克服信標(biāo)節(jié)點(diǎn)稀疏問(wèn)題,Two-Phase定位算法在起始階段使用Hop-TERRAIN算法獲得節(jié)點(diǎn)位置的粗略估算。在循環(huán)求精階段,使用加權(quán)最小二乘法進(jìn)行三邊測(cè)量以計(jì)算新位置。

實(shí)驗(yàn)表明,Cooperative ranging算法定位精度可達(dá)到5%(測(cè)距誤差為5%,而單純使用TERRAIN算法得到的定位精度約為39%),而Two-Phase算法在錨節(jié)點(diǎn)比例為5%,測(cè)距誤差為5%,網(wǎng)絡(luò)連通度約為7的條件下,定位精度約為33%[13,14]。

2. 1. 11 Map-growing定位算法

文獻(xiàn)[29]提出了Map-growing算法,基本思想是通過(guò)遞歸算法,由三個(gè)相鄰的節(jié)點(diǎn)形成局部初始坐標(biāo)系并向外廣播坐標(biāo)信息,與此三節(jié)點(diǎn)相鄰且收集足夠信息的節(jié)點(diǎn)根據(jù)三邊測(cè)量法計(jì)算自身坐標(biāo);初始坐標(biāo)系以此方式擴(kuò)展,如此反復(fù)直至所有節(jié)點(diǎn)被定位。該算法實(shí)現(xiàn)簡(jiǎn)單,只需首先確定三個(gè)點(diǎn)建立相對(duì)坐標(biāo)系就可實(shí)現(xiàn)大部分節(jié)點(diǎn)的定位。由于不斷升級(jí)新的未知節(jié)點(diǎn)參與到定位中,該算法對(duì)拓?fù)浣Y(jié)構(gòu)適應(yīng)性很強(qiáng),節(jié)點(diǎn)覆蓋率高。但是該算法使用完成定位的節(jié)點(diǎn)協(xié)助定位會(huì)造成誤差累積,一旦測(cè)距誤差比較大時(shí),距離三個(gè)選取的參考點(diǎn)較遠(yuǎn)的邊緣區(qū)域節(jié)點(diǎn)計(jì)算得到的坐標(biāo)誤差就會(huì)很大。

2. 1. 12 COLA算法

Chia-Yen Shih等人提出一種基于RSS的三維無(wú)線傳感器網(wǎng)絡(luò)三邊測(cè)量定位方法COLA (Complexity-reached 3D trilateration localization approach)[38],該算法通過(guò)將三維三邊測(cè)量轉(zhuǎn)化為二維三邊測(cè)量來(lái)降低網(wǎng)絡(luò)復(fù)雜度,利用裝備有兩個(gè)收發(fā)器和兩個(gè)高度不同的天線超級(jí)錨節(jié)點(diǎn),探測(cè)兩個(gè)僅高度不同的位置信號(hào),該方法在低計(jì)算開(kāi)銷的條件下取得了較好的定位效果,但僅適用于室內(nèi)無(wú)線傳感器網(wǎng)絡(luò)。

2. 1. 13 SPA定位算法

Srdjan Capkun等學(xué)者針對(duì)無(wú)基礎(chǔ)設(shè)施的移動(dòng)無(wú)線網(wǎng)絡(luò),提出了一種SPA (Self - Positioning Algorithm)相對(duì)定位算法[31]。它選擇網(wǎng)絡(luò)中密度最大處的一組節(jié)點(diǎn)作為建立網(wǎng)絡(luò)全局坐標(biāo)系統(tǒng)的參考群(location reference group),并在其中選擇連通度最大的一個(gè)節(jié)點(diǎn)作為坐標(biāo)系統(tǒng)的原點(diǎn)。首先根據(jù)節(jié)點(diǎn)間的測(cè)距結(jié)果在各個(gè)節(jié)點(diǎn)建立局部坐標(biāo)系統(tǒng),通過(guò)節(jié)點(diǎn)間的信息交換與協(xié)調(diào),以參考節(jié)點(diǎn)為基準(zhǔn)通過(guò)坐標(biāo)變換建立全局坐標(biāo)系統(tǒng)。因?yàn)樗泄?jié)點(diǎn)都需要參與坐標(biāo)的建立和變化運(yùn)算,因此該方法的通信開(kāi)銷和計(jì)算量較大。

2. 1. 14 DGFSL-3D定位算法

馬永波等人提出了一種三維空間中基于動(dòng)態(tài)分組篩選的安全定位算法DGFSL-3D (Dynamic Group Filtering Security Localization Algorithm)[39],所有傳感器節(jié)點(diǎn)均裝備全向天線,具有相同的發(fā)射半徑,節(jié)點(diǎn)的物理坐標(biāo)不變,考慮到信標(biāo)節(jié)點(diǎn)可能失效或者信標(biāo)節(jié)點(diǎn)被捕獲后發(fā)布虛假定位信息等問(wèn)題,該算法對(duì)信標(biāo)節(jié)點(diǎn)進(jìn)行安全性檢測(cè),將部分節(jié)點(diǎn)判定為惡意定位節(jié)點(diǎn),從自己的信標(biāo)節(jié)點(diǎn)列表中剔除,最后進(jìn)行坐標(biāo)修正實(shí)現(xiàn)精確定位。該算法能夠有效地剔除定位干擾節(jié)點(diǎn),能夠顯著地降低惡意定位節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)定位過(guò)程的負(fù)面影響,算法具有較高的定位精度。

2.2 無(wú)需測(cè)距的靜態(tài)節(jié)點(diǎn)定位算法

2. 2. 1 Centroid算法

2000年,南加州大學(xué)的Nirupama Bulusu等學(xué)者提出了質(zhì)心算法(Centroid Algorithm)[16],該算法是一種僅基于網(wǎng)絡(luò)連通性的室外定位算法,以所有在其通信范圍內(nèi)的錨節(jié)點(diǎn)的幾何質(zhì)心作為未知節(jié)點(diǎn)的估計(jì)位置,不需要錨節(jié)點(diǎn)和未知節(jié)點(diǎn)之間精確的距離,算法實(shí)現(xiàn)比較簡(jiǎn)單,適用于定位精度要求不高的場(chǎng)合,多邊形的面積越小,估計(jì)誤差也就越小,因此該算法在較高的錨節(jié)點(diǎn)密度下方能實(shí)現(xiàn)較精確的定位,同時(shí),該算法在定位過(guò)程中并沒(méi)有體現(xiàn)出各連通錨節(jié)點(diǎn)對(duì)未知節(jié)點(diǎn)定位影響力的大小。

針對(duì)質(zhì)心法的不足,國(guó)內(nèi)外學(xué)者提出了多種改進(jìn)的質(zhì)心算法,例如基于錨節(jié)點(diǎn)功率調(diào)節(jié)的加權(quán)質(zhì)心定位算法[40],基于跳數(shù)的加權(quán)質(zhì)心定位算法[41],基于最小包圍多邊形定位(SEPL)算法[42],文獻(xiàn)[43]將質(zhì)心算法擴(kuò)展到三維場(chǎng)景,提出了3D-Centroid算法。

2. 2. 2 APIT定位算法

2003年弗吉尼亞大學(xué)的Tian He等人提出了APIT (Approximate Point-In-Triangulation Test)定位算法[17],該算法的理論基礎(chǔ)是Perfect Point-In-Triangulation Test Theory (PIT):假如存在一個(gè)方向,沿著這個(gè)方向p點(diǎn)會(huì)同時(shí)遠(yuǎn)離或接近A、B、C,那么p位于△ABC外;否則p就位于△ABC內(nèi)。APIT利用未知節(jié)點(diǎn)的臨近節(jié)點(diǎn)代替其移動(dòng)進(jìn)行計(jì)算,通過(guò)收集所有鄰居錨節(jié)點(diǎn)的信息,并測(cè)試未知節(jié)點(diǎn)是否位于不同的三個(gè)錨節(jié)點(diǎn)組成的三角形內(nèi),計(jì)算所有包含該未知節(jié)點(diǎn)的三角形的交集,即是節(jié)點(diǎn)所在的區(qū)域,取交集的質(zhì)心作為未知節(jié)點(diǎn)位置,與基本的質(zhì)心算法相比,有著更小的有效區(qū)域,因此在一定程度上提高了定位的精度。不過(guò)算法對(duì)網(wǎng)絡(luò)的連通性要求較高,且定位覆蓋率不高,如果要達(dá)到高的性能,就要求錨節(jié)點(diǎn)密度和通信范圍增大。實(shí)驗(yàn)表明,APIT測(cè)試錯(cuò)誤概率相對(duì)較小(當(dāng)相鄰節(jié)點(diǎn)為6個(gè)或者6個(gè)以上時(shí),誤判不超過(guò)14%);平均定位誤差小于節(jié)點(diǎn)無(wú)線電射程的40%。

文獻(xiàn)[44]基于APIT的思想,提出了環(huán)形區(qū)域疊加定位算法ROCRSSI (Ring Overlapping based on Comparison of Received Signal Strength Indicator)算法,該算法以APIT算法為基礎(chǔ),網(wǎng)絡(luò)中每個(gè)未知節(jié)點(diǎn)通過(guò)鄰居錨節(jié)點(diǎn)形成的一系列環(huán)形,然后將所得的環(huán)相互疊加,取疊加區(qū)域的質(zhì)心作為其估計(jì)位置,該算法在較低錨節(jié)點(diǎn)密度的情況下獲得較為精確的定位,但錨節(jié)點(diǎn)必須提前配置,預(yù)先知道自己的位置信息,且需要具有較大的傳播功率。

文獻(xiàn)[45]采用ROCRSSI算法的思想,將其拓展到三維空間定位,提出了基于球殼定位的APIS (Approximate Point-In-Sphere)算法,實(shí)現(xiàn)了立體空間中傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)定位。該算法基于劃分空間為球殼,未知節(jié)點(diǎn)尋找包含自己的最薄一層球殼,取球殼交集進(jìn)行定位。該算法的優(yōu)點(diǎn)是僅需錨節(jié)點(diǎn)廣播信標(biāo)信息,未知節(jié)點(diǎn)無(wú)需直接通信,減少了通信開(kāi)銷,同時(shí)無(wú)需測(cè)量節(jié)點(diǎn)間的實(shí)際距離;缺點(diǎn)是是由于采用球殼分割的方法,計(jì)算開(kāi)銷和通信開(kāi)銷大,節(jié)點(diǎn)成本高,并且定位覆蓋率受錨節(jié)點(diǎn)數(shù)量變化的影響較大。

2. 2. 3 Convex Optimization定位算法

2001年,加州大學(xué)伯克利分校的Doherty等學(xué)者提出了凸規(guī)劃(Convex Optimization)定位算法[18],該算法將整個(gè)網(wǎng)絡(luò)中點(diǎn)到點(diǎn)的通信模型轉(zhuǎn)化為節(jié)點(diǎn)位置的一組幾何約束,將整個(gè)網(wǎng)絡(luò)視為一個(gè)凸集,從而將節(jié)點(diǎn)定位問(wèn)題轉(zhuǎn)化為凸約束優(yōu)化問(wèn)題,利用未知節(jié)點(diǎn)與錨節(jié)點(diǎn)的連通性計(jì)算未知節(jié)點(diǎn)的可能區(qū)域,進(jìn)而估計(jì)節(jié)點(diǎn)位置,該算法是一種集中式定位算法,當(dāng)信標(biāo)節(jié)點(diǎn)比例為10%的時(shí)候,其定位誤差約等于節(jié)點(diǎn)的無(wú)線射程,誤差較大,且錨節(jié)點(diǎn)必須部署在網(wǎng)絡(luò)邊緣,否則,節(jié)點(diǎn)位置估算會(huì)向網(wǎng)絡(luò)中心偏移。

2. 2. 4 Amorphous定位算法

2003年,美國(guó)麻省理工的Radhika Nagpal等學(xué)者提出了Amorphous定位算法[22],該算法通過(guò)估算待測(cè)節(jié)點(diǎn)與錨節(jié)點(diǎn)之間的平均梯度值,根據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)的通信半徑,未知節(jié)點(diǎn)到每個(gè)錨節(jié)點(diǎn)的跳段距離,并使用三邊測(cè)量法或最大似然估計(jì)法估算自身位置,Amorphous算法對(duì)節(jié)點(diǎn)的運(yùn)算能力要求較小,但是需要預(yù)先設(shè)定網(wǎng)絡(luò)的密度,并且隨著未知節(jié)點(diǎn)與錨節(jié)點(diǎn)之間跳數(shù)的增加,估算距離與真實(shí)距離的誤差也隨之增大。

2. 2. 5 DV-Hop定位算法

2003年,美國(guó)路特葛斯大學(xué)的Dragos Niculescu等人利用距離矢量路由和GPS定位的原理提出了DV-Hop定位算法[15]。該算法首先使用典型的距離矢量路由協(xié)議使網(wǎng)絡(luò)中所有節(jié)點(diǎn)獲得到錨節(jié)點(diǎn)的跳數(shù),錨節(jié)點(diǎn)計(jì)算網(wǎng)絡(luò)平均每跳距離,并把此值廣播至整個(gè)網(wǎng)絡(luò),節(jié)點(diǎn)根據(jù)到錨節(jié)點(diǎn)的跳數(shù)和平均每跳距離計(jì)算到錨節(jié)點(diǎn)的距離,當(dāng)未知節(jié)點(diǎn)獲得與三個(gè)或更多錨節(jié)點(diǎn)距離時(shí),用三邊測(cè)量法進(jìn)行定位。DVHop算法屬于分布式算法,實(shí)現(xiàn)簡(jiǎn)單,通信開(kāi)銷小,但是隨著跳數(shù)的增加,估計(jì)距離誤差會(huì)增大,通信開(kāi)銷大。實(shí)驗(yàn)表明,DV-Hop算法在網(wǎng)絡(luò)平均連通度為10、錨節(jié)點(diǎn)比例為10%的各向同性網(wǎng)絡(luò)中定位精度約為33%。

文獻(xiàn)[46]通過(guò)考慮通信范圍和跳段距離的關(guān)系對(duì)DV-Hop算法進(jìn)行了限制和修正,提高了定位精度。

文獻(xiàn)[47]提出了基于自適應(yīng)慣性權(quán)重的優(yōu)化定位算法,在DV-Hop算法的基礎(chǔ)上,用改進(jìn)的粒子群算法做后期優(yōu)化,根據(jù)每次迭代后粒子位置與全局最優(yōu)位置的距離,對(duì)粒子的慣性權(quán)重進(jìn)行動(dòng)態(tài)調(diào)整,使其具有動(dòng)態(tài)自適應(yīng)性,并且利用進(jìn)化度作為搜索終止條件,加快算法的收斂速度,仿真表明該算法相對(duì)于DV-Hop算法,可以減低平均定位誤差,提高節(jié)點(diǎn)的定位精度。

李輝等人提出基于移動(dòng)代理的WSN三維MA3D-Hop定位算法[48],對(duì)DV-Hop算法進(jìn)行改進(jìn),并推廣到三維空間,建立了空間向量模型估計(jì)未知節(jié)點(diǎn)位置,并對(duì)初始估計(jì)位置進(jìn)行迭代求精,來(lái)減少定位誤差。

2. 2. 6 MDS-MAP定位算法

2003年,密蘇里哥倫比亞大學(xué)的Yi Shang等人將多維標(biāo)度(multidimensional scaling,MDS)的數(shù)據(jù)分析方法應(yīng)用于無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位,提出了MDS-MAP算法[19],該方法根據(jù)節(jié)點(diǎn)間的不同信息(例如與其它節(jié)點(diǎn)的距離)對(duì)節(jié)點(diǎn)進(jìn)行定位,然后對(duì)距離矩陣進(jìn)行奇異值分解得到節(jié)點(diǎn)初始坐標(biāo),再進(jìn)行優(yōu)化使這些坐標(biāo)滿足其間的距離關(guān)系。首先,從全局角度生成網(wǎng)絡(luò)拓?fù)溥B通圖,并為圖中每條邊賦予距離值,當(dāng)節(jié)點(diǎn)具有測(cè)距能力時(shí),該值就是測(cè)距結(jié)果。當(dāng)僅擁有連通性信息時(shí),所有邊賦值為1。然后使用最短路徑算法生成節(jié)點(diǎn)間距矩陣;然后,對(duì)節(jié)點(diǎn)間距矩陣應(yīng)用MDS技術(shù),生成整個(gè)網(wǎng)絡(luò)的二維或三維相對(duì)坐標(biāo)系統(tǒng);當(dāng)擁有足夠的錨節(jié)點(diǎn)時(shí)(二維最少3個(gè),三維最少4個(gè)),將相對(duì)坐標(biāo)系統(tǒng)轉(zhuǎn)化為絕對(duì)坐標(biāo)系統(tǒng)。該算法可在基于測(cè)距或非測(cè)距條件下運(yùn)行,并可根據(jù)情況實(shí)現(xiàn)相對(duì)定位和絕對(duì)定位。該算法采用集中式計(jì)算的模式,不需要錨節(jié)點(diǎn)或者僅需較少的幾個(gè)錨節(jié)點(diǎn),但是算法比較復(fù)雜,需要采用奇異值分解的方法進(jìn)行計(jì)算之間的平均梯度值。實(shí)驗(yàn)顯示,當(dāng)網(wǎng)絡(luò)的節(jié)點(diǎn)密度減小時(shí),定位誤差增大,并且無(wú)法定位的節(jié)點(diǎn)數(shù)量增加;而當(dāng)網(wǎng)絡(luò)連通度達(dá)到12. 2時(shí),幾乎全部節(jié)點(diǎn)都可實(shí)現(xiàn)定位;在擁有200個(gè)節(jié)點(diǎn)(其中4個(gè)信標(biāo)節(jié)點(diǎn)),平均連通度為12. 1的網(wǎng)絡(luò)中,在range-free條件下,定位誤差約為30%;而在range-based條件下,定位誤差為16%(測(cè)距誤差為5%)[19]。

針對(duì)MDS-MAP矩陣維數(shù)大,計(jì)算復(fù)雜的缺點(diǎn),文獻(xiàn)[49]提出了基于MDS的局部定位算法,設(shè)定跳數(shù)范圍,網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)在該跳數(shù)范圍內(nèi)進(jìn)行局部定位,然后融合局部定位圖得到全局定位圖。局部定位算法不需要估計(jì)相距較遠(yuǎn)節(jié)點(diǎn)的距離,從而提高了定位精度,而且適合于有大量節(jié)點(diǎn)的傳感器網(wǎng)絡(luò)。此外,在不同的節(jié)點(diǎn)上同時(shí)進(jìn)行局部定位實(shí)現(xiàn)分布式計(jì)算。

文獻(xiàn)[50]提出了基于多維定標(biāo)的無(wú)線傳感器網(wǎng)絡(luò)三維定位算法3D-MDS,將網(wǎng)絡(luò)在邏輯上劃分為許多簇,在每個(gè)簇內(nèi)計(jì)算局部坐標(biāo),然后將節(jié)點(diǎn)的位置信息回送,在后臺(tái)利用一種集中式的迭代優(yōu)化算法對(duì)初始坐標(biāo)求精,該算法降低定位誤差、計(jì)算復(fù)雜度和通信開(kāi)銷,適用于大規(guī)模無(wú)線傳感器網(wǎng)絡(luò)定位問(wèn)題。

文獻(xiàn)[51]在MDS-MAP定位算法的基礎(chǔ)上,提出了Isomap定位算法,利用測(cè)地線距離代替歐氏距離實(shí)現(xiàn)節(jié)點(diǎn)定位,提高了定位精度,但是鄰近參數(shù)K的選擇較為復(fù)雜。

2. 2. 7 SHARP定位算法

文獻(xiàn)[23]提出一種SHARP (Simple Hybrid Absolute Relative Positioning)定位方法。這種方法先在傳感器網(wǎng)絡(luò)節(jié)點(diǎn)中利用隨機(jī)法或者外圍結(jié)點(diǎn)法選擇一定數(shù)量的節(jié)點(diǎn),將這些節(jié)點(diǎn)作為參考節(jié)點(diǎn)但不要求知道其坐標(biāo)。利用相對(duì)定位方法MDS確定一個(gè)相對(duì)坐標(biāo)系,以及它們?cè)谶@個(gè)坐標(biāo)系中的坐標(biāo),最后網(wǎng)絡(luò)中的其它節(jié)點(diǎn)利用DV-distance定位方法確定自身在上述坐標(biāo)系中的坐標(biāo)。

SHARP結(jié)合了MDS和DV-distance算法的優(yōu)點(diǎn):用MDS確定參考節(jié)點(diǎn)相對(duì)坐標(biāo)精度較高,并且避免了計(jì)算所有節(jié)點(diǎn)組成的距離矩陣;DV-distance算法易于實(shí)現(xiàn)。經(jīng)實(shí)驗(yàn)驗(yàn)證,在節(jié)點(diǎn)密度高連通性好的傳感器網(wǎng)絡(luò)中,SHARP算法的定位精度要高于DV-distance和MDS。

2. 2. 8 HiRLoc安全定位算法

2006年,L. Lazos等學(xué)者提出HiRLoc安全定位算法[52],該算法基于區(qū)域覆蓋逼近,假設(shè)未知節(jié)點(diǎn)和錨節(jié)點(diǎn)配有最大發(fā)射功率的全方向天線,錨節(jié)點(diǎn)通過(guò)改變發(fā)射功率和定向天線的方向,重新廣播錨節(jié)點(diǎn)信息,減小多個(gè)覆蓋區(qū)域的重疊面積來(lái)確定節(jié)點(diǎn)位置,該算法主要側(cè)重于安全方面,可以抵御漏洞攻擊、Sybil攻擊等,對(duì)系統(tǒng)硬件需求較大。

2. 2. 9 3D-DRL算法

文獻(xiàn)[53]提出了一種基于網(wǎng)格劃分思想的非測(cè)距三維定位(3D-DRL)算法,錨節(jié)點(diǎn)廣播包括ID、位置、發(fā)射功率級(jí)別、傳播范圍等信標(biāo)信息,未知節(jié)點(diǎn)對(duì)接收到的信標(biāo)信息進(jìn)行存儲(chǔ),記錄能夠監(jiān)聽(tīng)到的錨節(jié)點(diǎn)數(shù)量,用以判斷是否有足夠的信標(biāo)信息進(jìn)行定位。然后以所有能監(jiān)聽(tīng)到的錨節(jié)點(diǎn)的質(zhì)心為中心將仿真區(qū)域劃分為立體網(wǎng)格,若一個(gè)錨節(jié)點(diǎn)判定某個(gè)小格子在其有效覆蓋范圍內(nèi),就會(huì)對(duì)該格子投一票,投票結(jié)束后,將得票值最高的網(wǎng)格作為未知節(jié)點(diǎn)的最大可能定位區(qū)域,選取該區(qū)域的質(zhì)心作為未知節(jié)點(diǎn)的估計(jì)位置。3D-DRL算法[54-55]無(wú)需未知節(jié)點(diǎn)間相互通信,具有較小的通信開(kāi)銷,不依賴于錨節(jié)點(diǎn)比例,且對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)具有魯棒性。定位區(qū)域網(wǎng)格化表示與投票機(jī)制減少了無(wú)線信號(hào)傳輸不規(guī)則性對(duì)算法定位精度的不利影響,但僅限于網(wǎng)絡(luò)中節(jié)點(diǎn)位置固定的情況。

2.3 WSN節(jié)點(diǎn)定位常用算法特點(diǎn)比較

對(duì)于上述代表性的WSN節(jié)點(diǎn)定位算法,其特點(diǎn)歸納如表1所示。

表1　常用靜態(tài)節(jié)點(diǎn)定位算法的特點(diǎn)比較

3　總 結(jié)

本文主要介紹了無(wú)線傳感器網(wǎng)絡(luò)靜態(tài)節(jié)點(diǎn)定位算法的基本原理和國(guó)內(nèi)外研究現(xiàn)狀,從基于測(cè)距的靜態(tài)節(jié)點(diǎn)定位算法和無(wú)需測(cè)距的靜態(tài)節(jié)點(diǎn)定位算法兩個(gè)方面分類討論了常用的節(jié)點(diǎn)定位及其改進(jìn)算法,通過(guò)上面的分析總結(jié)可以看出,目前研究的各類定位算法在網(wǎng)絡(luò)結(jié)構(gòu)、計(jì)算量、定位精度、應(yīng)用范圍等方面存在較大差別,也取得了豐碩的研究成果,但仍有一些問(wèn)題有待解決。

1)大部分定位算法均是在理想條件下進(jìn)行分析和驗(yàn)證,但是無(wú)線傳感器網(wǎng)絡(luò)往往部署在山地、叢林或者水下等復(fù)雜環(huán)境中,實(shí)際環(huán)境中的很多因素,例如無(wú)線電傳播路徑損耗、地形遮擋物、無(wú)線信號(hào)傳輸不規(guī)則性、大氣折射誤差等因素在算法中很少被考慮,算法缺少在實(shí)際應(yīng)用環(huán)境中的測(cè)試效果。

2)定位精度是目前大部分定位算法首先考慮的性能指標(biāo),算法復(fù)雜度、硬件成本、系統(tǒng)的能耗等參數(shù)考慮不多,這也在一定程度上限制了其應(yīng)用范圍。

3)無(wú)線傳感器網(wǎng)絡(luò)定位技術(shù)已經(jīng)逐步從二維空間向三維空間擴(kuò)展,從靜態(tài)節(jié)點(diǎn)定位向動(dòng)態(tài)節(jié)點(diǎn)定位擴(kuò)展,這方面的研究有待加強(qiáng)。

因此,研究低成本、高能效、易于系統(tǒng)化的節(jié)點(diǎn)定位技術(shù),研究能夠有效延長(zhǎng)網(wǎng)絡(luò)生命周期的低復(fù)雜度、低開(kāi)銷、低能耗的節(jié)點(diǎn)定位技術(shù),研究考慮到無(wú)線電傳播路徑損耗、地形遮擋物、無(wú)線信號(hào)傳輸不規(guī)則性、大氣折射誤差等因素的貼近現(xiàn)實(shí)場(chǎng)景的定位技術(shù),研究高精度的動(dòng)態(tài)節(jié)點(diǎn)定位及復(fù)雜三維空間中的節(jié)點(diǎn)定位技術(shù),將是未來(lái)研究的技術(shù)重點(diǎn)。

參 考 文 獻(xiàn)

[1] LOWELL J R. Military application of localization,tracking,and targeting[J]. IEEE Wireless Communications,2011,18(2):60-65.

[2] LIJianpo,ZHONG Xinxin,Lu I-Tai. Three-dimensional node localization algorithm for WSN based on differential RSS irregular transmission model[J]. Journal of Communications,2014,9(5):391-397.

[3] CHAO Long,Meng Shuai. Wireless sensor networks:traffic information providers for intelligent transportation system[C]. 18th International Conference on Geoinformatics,Beijing,2010,6:1-5.

[4] LIJianpo,JIANG Xue,LU I-Tai. Energy balance routing algorithm based on virtual MIMO scheme for wireless sensor networks[J]. Journal of Sensors,2014 (2014),1-7.

[5] HARTER A,HOPPER A. A distributed location system for the active office[J]. IEEE Network,1994,8(1):62-70.

[6] THOMAS F,ROS L. Revisitingtrilateration for robot localization[J]. IEEE Transactions on Robotics,2005,21(1):93-101.

[7] YORK G,PACK D. Comparative study on time-varying target localization methods using multiple unmanned aerial vehicles:Kalman estimation and triangulation techniques[C]. IEEE International Conference on Networking,Sensing and Control,Tucson,2005,3:305-310.

[8] HOWARD A,MATARIC M J,SUKHATME G S. Localization for mobile robot teams using maximum likelihood estimation[C]. IEEE/ RSJ International Conference on Intelligent Robots and Systems,Algarve,2002,10:434-439.

[9] ABID M A,CHERKAOUI S. 3D compressive sensing for nodes localization in WNs based on RSS [C]. IEEE International Conference on Communications,Beijing,2012,6:5195- 5199.

[10] KAUNE R. Accuracy studies for TDOA and TOA localization[C]. 15th International Conference on Information Fusion,Singapore,2012,7: 408-415.

[11] HARA S,ANZAI D,YABU T. A perturbation analysis on the performance of TOA and TDOA localization in mixed LOS/ NLOS environments [J]. IEEE Transaction on Communications,2013,61(2):679-689.

[12] SAVVIDES A,HAN C,STRIVASTAVA M B. Dynamic fine - grained localization in Ad - Hoc networks of sensors [ C]. 7th Annual International Conference on Mobile Computing and Networking,Rome,2001,7:166-179.

[13] SAVARESE C,RAVAEY J M,BEUTEL J. Location in distributed ad-hoc wireless sensor networks[C]. IEEE International Conference on A-coustics,Speech,and Signal Processing,Salt Lake City,2001,5:2037-2040.

[14] SAVARESE C,RAVAEY J M,LANGENDOEN K. Robust positioning algorithms for distributed ad-hoc wireless sensor network[C]. Proceedings of the USENIX Annual Technical Conference,California,2002,6:317-327.

[15] NICULESCU D,NATH B. Ad Hoc positioning system (APS)[C]. IEEE Global Telecommunications Conference,San Antonio,2001,11: 2926-2931.

[16] BULUSU N,HEIDEMANN J,ESTRIN D. GPS-less low-cost outdoor localization for very small devices[J]. IEEE Personal Communications, 2000,7(5):28-34.

[17] HETian,HUANG Chengdu,BLUM B M,et al. Range-free localization schemes for large scale sensor networks [C].9th Annual International Conference on Mobile Computing and Networking,San Diego,2003,9:81- 95.

[18] DOHERTY L,PISTER K S,GHAOUI L E. Convex position estimation in wireless sensor networks[C].20th Annual Joint Conference of the IEEE Computer and Communications Societies,Anchorage,2001,4:1655-1663.

[19] SHANG Yi,RUML W,ZHANG Ying,et al. Localization from mere connectivity[C]. 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing,New York,2003,6:201-212.

[20]李建坡,時(shí)明,謝巖,等.一種基于模糊理論的蒙特卡洛移動(dòng)節(jié)點(diǎn)定位算法[J].計(jì)算機(jī)應(yīng)用與軟件,2013,30(12):147-150.

[21]李建坡,時(shí)明,鐘鑫鑫.自適應(yīng)蒙特卡羅無(wú)線傳感器網(wǎng)絡(luò)移動(dòng)節(jié)點(diǎn)定位算法[J].吉林大學(xué)學(xué)報(bào)(工學(xué)版),2014,44(4):1191-1196.

[22] NAGOAL R,SHROBE H,BACHRACH J. Organizing a global coordinate system from local information an Ad hoc sensor network [C].2nd International Workshop on Information Processing in Sensor Networks,Palo Alto,2003,4:333-348.

[23] AHMED AA,SHI Hongchi,SHANG Yi. SHARP:a new approach to relative localization in wireless sensor networks[C]. 25th International Conference on Distributed Computing System Workshops,Columbus,2005,6:892-898.

[24] CHEN Xun,HAN Peng,HE Qiusheng. A viable localization scheme for dynamic wireless sensor networks[C]. First International Multi-Symposiums on Computer and Computational Science,Hangzhou,2006,6:587-593.

[25] KIM K,LEE W. MBAL:a mobile beacon-assisted localization scheme for wireless sensor networks[C]. 16th International Conference on Computer Communications and Networks,Honolulu,2007,8:57-62.

[26] LIANG Jianlin,SHAO Jun,XU Ying,et al. Sensor network localization in constrained 3-D spaces[C]. IEEE International Conference on Mechatronics and Automation,Zhengzhou,2006,6:49-54.

[27] CHANG T C,WANGKuochen,HSIEH Y L,et al. Color-theory-based dynamic localization in mobile wireless sensor networks[C].1st Workshop on Wireless Ad Hoc Sensor Networks,London,2005,5:73-78.

[28] GUERRERO E,ALVAREZ J,RIVERO L.3D-ADAL:A three-dimensional distributed range-free localization algorithm for wireless sensor networks based on unmanned aerial vehicles [C].5th International Conference on Digital Information Management,Thunder Bay,2010,7: 332-338.

[29] LI Xiaoli,SHI Hongchi,SHANG Yi. A map-growing localization algorithm for ad-hoc wireless sensor networks[C].10th International Conference on Parallel and Distributed System,California,2004,7:395-402.

[30] NICULESCU D,NATH B. DV based positioning in Ad Hoc networks[J]. Journal of Telecommunication Systems,2003,22(1):267-280.

[31] CAPKUN S,HAMDI M,HUBAUX J P. GPS-free positioning in mobile ad-hoc networks[C].34th Annual Hawaii International Conference on System Sciences,Maui,2001,1:1-10.

[32] SAVVIDES A,PARK H,STRIVASTAVA M. The bits and flops of the N-hopmultilateration primitive for node localization problems[C].1stACM International Workshop on Wireless Sensor Networks and Applications,New York,2002,112-121.

[33] YOKOO K,NISHIDOI T,URABE H. RSS-based localization considering topographical feature for pasturing [C].10th Workshop on Positioning Navigation and Communication,Dresden,2013,3:1-5.

[34] BEN-Shimol Y,BLAUNSTEIN N. Localization and positioning of any subscriber in indoor environments on the basis of analysis of joint AOA -TOA signal distribution[C]. IEEE-APS Topical Conference on Antennas and Propagation in Wireless Communications,Torino,2011,9: 1420-1423.

[35] LIU Chongfeng,YANG Jie,WANG Fengshuai,et al. Joint TDOA and AOA location algorithm[J]. Journal of Systems Engineering and Electronics,2013,24(2):183-188.

[36] MIKHALEV A,ORMONDROYD R. Passive emitter geolocation using agent-based data fusion of AOA,TDOA and FDOA measurements [C].10th International Conference on Information Fusion,Quebec,2007,7:1-6.

[37]祁榮賓,李思瑾,馬天義.基于迭代的無(wú)線傳感器網(wǎng)絡(luò)三維定位算法研究[J].傳感技術(shù)學(xué)報(bào),2012,25(5):644-650.

[38] SHIH C Y,MARRON P J. COLA:complexity reduced trilateration approach for 3D localization in wireless sensor networks[C].4th International Conference on Sensor Technologies and Applications,Venice,2010,7:24-32.

[39]馬永波.無(wú)線傳感器網(wǎng)絡(luò)精確動(dòng)態(tài)定位及其安全性問(wèn)題研究[D].吉林:吉林大學(xué),2010.

[40]吳磊,侯忠偉,許登元.無(wú)線傳感器網(wǎng)絡(luò)中基于錨節(jié)點(diǎn)功率調(diào)節(jié)的加權(quán)質(zhì)心定位算法[J].微電子學(xué)與計(jì)算機(jī),2012,29(10):177 -180.

[41]孟祥衷,宋保業(yè).無(wú)線傳感器網(wǎng)絡(luò)中的HWC定位算法[J].計(jì)算機(jī)工程,2009,35(7):104-106.

[42]張愛(ài)清,葉新榮,胡海峰.無(wú)線傳感器網(wǎng)絡(luò)質(zhì)心定位新算法及性能分析[J].計(jì)算機(jī)應(yīng)用,2012,32(9):2429-2431,2435.

[43]王丹.三維無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)自定位算法研究[D].成都:西南交通大學(xué),2007.

[44] LIU Chong,WUKui,HE Tian. Sensor localization with ring overlapping based on comparison of received signal strength indicator[C]. IEEE International Conference on Mobile Ad-hoc and Sensor Systems,Fort Lauderdale,2004,10:516-518.

[45]呂良彬,曹陽(yáng),高洵.基于球殼交集的傳感器網(wǎng)絡(luò)三維定位算法[J].北京郵電大學(xué)學(xué)報(bào),2006,29(S1):48-51.

[46] JIWeiwei,LIU Zhong. An Improvement of DV-Hop Algorithm in Wireless Sensor Networks[C]. International Conference on Wireless Communications,Networking and Mobile Computing,Wuhan,2006,9:1-4.

[47]季必曄,顧燕.無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)自適應(yīng)慣性權(quán)重定位算法[J].科學(xué)技術(shù)與工程,2012,12(27):6967-6973.

[48]李輝.無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位技術(shù)的研究[D].武漢:武漢理工大學(xué),2010.

[49] SHANG Yi,RUML W. Improved MDS-based localization[C].23rd Annual Joint Conference of the IEEE Computer and Communications Societies,Hong Kong,2004,3:2640-2651.

[50]張榮磊,劉琳嵐,舒堅(jiān).基于多維定標(biāo)的無(wú)線傳感器網(wǎng)絡(luò)三維定位算法[J].計(jì)算機(jī)應(yīng)用研究,2009,26(8):3100-3104.

[51] WANG Chenqiu,CHEN Jiming,SUN Youxian,et al. Wireless sensor networks localization with isomap[C]. IEEE International Conference on Communications,Dresden,2009,6:1-5.

[52] LAZOS L,POOVENDRAN R. HiRLoc:High-resolution robust localization for wireless sensor networks[J]. IEEE Journal on Selected Areas in Communications,2006,24(2):233-246.

[53]王德華.無(wú)線傳感器網(wǎng)絡(luò)非測(cè)距三維定位算法的研究[D].濟(jì)南:山東大學(xué),2010.

[54]陳杰香,張恒,趙麗萍.基于蒙特卡羅方法的邊界檢測(cè)不確定度估計(jì)[J].東北電力大學(xué)學(xué)報(bào),2013,32(3):75-78.

[55]李建坡,朱緒寧,隋吉生.基于ZigBee技術(shù)的無(wú)線指紋考勤系統(tǒng)[J].東北電力大學(xué)學(xué)報(bào):自然科學(xué)版,2009,29(6):33-37.

Review of Statical Node Localization Algorithm for Wireless Sensor Networks

LI Jian-po1,ZHONG Xin-xin1,XU Chun2

(1. School of Information Engineering,Northeast Dianli University,Jilin Jilin 132012;2. Station 2021,State Administration of Press,Publication,Radio,Film and Television,Qiqihaer Hei Longjiang 161000)

Abstract:The principle of node localization,the latest development of related algorithms and the evaluation standards of Wireless Sensor Network (WSN)were introduced in this paper. Furthermore,based on the detailed performance analysis and comparison of typical localization algorithms (range-based static node,rangefree static node),the problems of current researches and further directions were pointed out.

Key words:Wireless sensor networks;Statical node localization;Review

作者簡(jiǎn)介:李建坡(1980-),男,河北省定州市人,東北電力大學(xué)信息工程學(xué)院副教授,博士,主要研究方向:嵌入式系統(tǒng)、智能信息處理.

基金項(xiàng)目:國(guó)家留學(xué)基金項(xiàng)目([2012]3043);吉林省教育廳科學(xué)技術(shù)研究項(xiàng)目([2009]101);東北電力大學(xué)青年學(xué)術(shù)骨干科研促進(jìn)計(jì)劃項(xiàng)目

收稿日期:2014-10-15

文章編號(hào):1005-2992(2015)02-0073-10

文獻(xiàn)標(biāo)識(shí)碼:A

中圖分類號(hào):TP393