張欣慧，徐晶晶，許必宵，趙學(xué)健，孫知信

(1.南京郵電大學(xué) 物聯(lián)網(wǎng)學(xué)院，江蘇 南京 210003;2.南京郵電大學(xué) 理學(xué)院，江蘇 南京 210003)

無線傳感器網(wǎng)絡(luò)三維定位算法研究

張欣慧1，徐晶晶1，許必宵2，趙學(xué)健1，孫知信1

(1.南京郵電大學(xué) 物聯(lián)網(wǎng)學(xué)院，江蘇 南京 210003;2.南京郵電大學(xué) 理學(xué)院，江蘇 南京 210003)

節(jié)點(diǎn)的位置信息是無線傳感器網(wǎng)絡(luò)應(yīng)用的基礎(chǔ)。節(jié)點(diǎn)定位技術(shù)作為無線傳感器網(wǎng)絡(luò)的關(guān)鍵技術(shù)之一，是無線傳感器網(wǎng)絡(luò)大多數(shù)應(yīng)用的基礎(chǔ)?，F(xiàn)有的大多數(shù)定位算法針對(duì)平面應(yīng)用設(shè)計(jì)，而在實(shí)際應(yīng)用中，由于地形限制或者環(huán)境限制，使得無線傳感器往往在空間上呈立體分布，而不是平面分布，所以需要把定位研究擴(kuò)展到三維空間中。針對(duì)無線傳感器網(wǎng)絡(luò)靜態(tài)節(jié)點(diǎn)定位算法的特點(diǎn)，介紹了二維定位算法的分類，在此基礎(chǔ)上系統(tǒng)地研究了近年來最新的三維定位理論和算法。主要根據(jù)基于測(cè)距的定位和無需測(cè)距的定位將三維定位算法分為兩大類，每類中再分為集中式定位和分布式定位，其中詳細(xì)研究了一些熱門的三維定位算法并總結(jié)了它們的優(yōu)缺點(diǎn)。在綜合分析當(dāng)前定位算法不足的基礎(chǔ)上，指出了未來三維定位算法的研究方向。

無線傳感器網(wǎng)絡(luò)；三維空間；定位算法；節(jié)點(diǎn)定位；測(cè)距

0 引 言

無線傳感器網(wǎng)絡(luò)(WSNs)如今已經(jīng)成為日常生活中的重要組成部分，它在軍用、民用、工商業(yè)等領(lǐng)域都有著廣泛的應(yīng)用前景。節(jié)點(diǎn)定位在這些應(yīng)用中是WSNs配置和運(yùn)行的關(guān)鍵問題，事件發(fā)生的位置和節(jié)點(diǎn)所包含的信息都建立在監(jiān)控消息的基礎(chǔ)上，毫無疑問，沒有位置信息的監(jiān)控消息是沒有意義的。

盡管現(xiàn)實(shí)中的無線傳感器網(wǎng)絡(luò)往往被布置在復(fù)雜的三維地形中，但是大多數(shù)定位技術(shù)都是假定在二維網(wǎng)絡(luò)部署的情況下提出的，而且一般這些適用于二維地形的定位技術(shù)并不能簡(jiǎn)單擴(kuò)展到三維環(huán)境中。傳統(tǒng)的二維定位算法往往分為集中式定位算法和分布式定位算法，或者分為基于測(cè)距的定位算法和無需測(cè)距的定位算法。此外，在基于測(cè)距的定位中常用的測(cè)距算法包括ToA、RSSI、AoA、TDoA。這些分類方式同樣可以擴(kuò)展到更符合真實(shí)情況的三維環(huán)境下的坐標(biāo)計(jì)算和定位算法中。

三維定位算法的研究目前有兩個(gè)大方向：一是將三維定位的問題降維到二維平面上來解決；二是通過對(duì)二維定位算法進(jìn)行改進(jìn)，將之?dāng)U展到三維定位上來，但這會(huì)提高原算法的時(shí)間和空間復(fù)雜度。大部分二維定位算法的研究文獻(xiàn)都是根據(jù)定位的實(shí)現(xiàn)方式來分類，例如劃分為集中式定位和分布式定位、基于測(cè)距的定位和無需測(cè)距的定位等。也有少部分文獻(xiàn)提出根據(jù)網(wǎng)絡(luò)架構(gòu)進(jìn)行分類，例如劃分為有錨節(jié)點(diǎn)的定位和無錨節(jié)點(diǎn)的定位等。

文中主要根據(jù)基于測(cè)距的定位和無需測(cè)距的定位將三維定位算法分為兩大類，每類中再分為集中式定位和分布式定位，其中詳細(xì)研究了一些熱門的三維定位算法并分析總結(jié)了它們的優(yōu)缺點(diǎn)。

1 基于測(cè)距的定位算法

基于測(cè)距的定位是指首先通過測(cè)距算法測(cè)量節(jié)點(diǎn)間的距離或者角度信息，之后利用所測(cè)信息通過數(shù)學(xué)計(jì)算得出未知節(jié)點(diǎn)坐標(biāo)的方式。下文將基于測(cè)距的三維定位算法按照節(jié)點(diǎn)處理信息的方式分為集中式定位和分布式定位分別進(jìn)行研究。

(1)集中式定位。

集中式定位是指將各個(gè)節(jié)點(diǎn)所收集到的信息傳送到服務(wù)器節(jié)點(diǎn)進(jìn)行處理，計(jì)算出未知節(jié)點(diǎn)坐標(biāo)位置的方式。

文獻(xiàn)[1-3]提出了一種被引用較多的Landscape-3D定位算法。如圖1所示，它需要借助移動(dòng)的定位輔助裝置LA在監(jiān)測(cè)區(qū)域上空周期性地廣播自身的位置信息，網(wǎng)絡(luò)中的未知節(jié)點(diǎn)通過接收到的位置信息，再利用RSSI計(jì)算其與LA之間的距離來確定自身位置。該算法主要依靠LA裝置的靈活性和健壯性，不需為節(jié)點(diǎn)配備GPS，但對(duì)LA的硬件裝備需求較高。

文獻(xiàn)[4]提出結(jié)合MDESM算法的微差分進(jìn)化算法，根據(jù)收集到的來自UAV的信息計(jì)算未知節(jié)點(diǎn)的位置坐標(biāo)。

文獻(xiàn)[5]以節(jié)點(diǎn)間的歐氏距離構(gòu)成的相似度矩陣為基礎(chǔ)，結(jié)合計(jì)算量過高的MDSMAP算法和LMDS算法并加入對(duì)測(cè)距信息的利用策略后，提出了FastMDSMAP算法，減少了定位時(shí)節(jié)點(diǎn)的能量消耗和計(jì)算時(shí)的時(shí)間復(fù)雜度。

圖1 Landscape-3D定位算法

文獻(xiàn)[6]提出一種給地震中的幸存者進(jìn)行3D定位的3DLM算法，以提高在地震后搜索和營(yíng)救幸存者的速度。該方案首先在塌陷區(qū)周圍設(shè)置移動(dòng)基站，使用RSSI估計(jì)幸存者和移動(dòng)基站之間的距離，通過三邊定位法確定幸存者的粗略位置；通過估計(jì)幸存者到三個(gè)移動(dòng)錨節(jié)點(diǎn)(被安置在形如等邊三角形的設(shè)備的三個(gè)角上)之間的距離來計(jì)算幸存者的精確位置。

文獻(xiàn)[7]基于Euclidean算法提出了一種三維定位算法，通過構(gòu)建立體模型將未知節(jié)點(diǎn)與錨節(jié)點(diǎn)之間距離的計(jì)算問題轉(zhuǎn)化為六面體模型頂點(diǎn)間距離的求解問題，再利用所提出的坐標(biāo)法求解節(jié)點(diǎn)的位置并通過循環(huán)迭代求精。

文獻(xiàn)[8]提出一種建立在RSSI值基礎(chǔ)上、復(fù)雜度有所減少的3D-三邊定位法COLA。該算法通過使用擁有兩個(gè)位置的超級(jí)錨節(jié)點(diǎn)(這兩個(gè)位置成對(duì)，只有z軸坐標(biāo)不同)來降低復(fù)雜度。

文獻(xiàn)[9]提出了一種在使用RSSI和三邊定位法計(jì)算未知節(jié)點(diǎn)坐標(biāo)之前預(yù)處理的方案：基于凹凸性劃分和分層的3D-CDD算法。該算法首先根據(jù)節(jié)點(diǎn)的高度將WSNs定位區(qū)域水平劃分為幾個(gè)適當(dāng)?shù)倪壿媽?，并在每層中根?jù)凹凸性的不同劃分為幾個(gè)分支區(qū)域，以減小由于網(wǎng)絡(luò)地形的凹凸程度不同造成的誤差。

基于測(cè)距的三維定位算法中需要測(cè)量大量的距離信息或角度信息，且與二維定位算法相比增加了一個(gè)維度的信息，這恰好迎合了集中式定位算法中服務(wù)器節(jié)點(diǎn)計(jì)算量和存儲(chǔ)量沒有限制的優(yōu)點(diǎn)。但同時(shí)集中式定位算法需要傳感器節(jié)點(diǎn)和服務(wù)器節(jié)點(diǎn)之間的大量通信，導(dǎo)致網(wǎng)絡(luò)通信量較大，且距離服務(wù)器節(jié)點(diǎn)距離較近的節(jié)點(diǎn)耗能大且易失效，故集中式定位算法不適用于資源受限型網(wǎng)絡(luò)。

(2)分布式定位。

分布式定位是指未知節(jié)點(diǎn)根據(jù)與通信范圍內(nèi)的鄰居節(jié)點(diǎn)交換的信息在后臺(tái)自行計(jì)算自己的坐標(biāo)位置的方式。

文獻(xiàn)[10]提出了基于傳統(tǒng)三角計(jì)算的Constrained-3D算法。該方案假定錨節(jié)點(diǎn)都部署在底部同一平面內(nèi)，以該平面為中心向上依靠測(cè)量與鄰居節(jié)點(diǎn)之間的距離來推算未知節(jié)點(diǎn)的位置。

文獻(xiàn)[11]提出的ILAH-3D算法將二維的經(jīng)典算法AHLos擴(kuò)展到三維，增加了普通節(jié)點(diǎn)升級(jí)為錨節(jié)點(diǎn)的驗(yàn)證條件，并采用加權(quán)最小二乘法來減少累積誤差。該算法還通過約束協(xié)作算法的執(zhí)行條件，借助節(jié)點(diǎn)間位置關(guān)系的同時(shí)再利用新升級(jí)的錨節(jié)點(diǎn)進(jìn)行重復(fù)定位運(yùn)算，以提高節(jié)點(diǎn)定位的精度。

文獻(xiàn)[12]提出了兩種適用于各向異性無線傳感器網(wǎng)絡(luò)的三維定位算法:混合粒子群算法(HPSO)和基于生物地理學(xué)的優(yōu)化算法(BBO)。HPSO改善了PSO不成熟收斂的問題，BBO在生物有機(jī)體在分配的地域集體學(xué)習(xí)的生物地理學(xué)的基礎(chǔ)上，應(yīng)用遷移算子在不同的棲息地之間選擇性地分享信息。該方案適用于在高噪聲環(huán)境下對(duì)目標(biāo)節(jié)點(diǎn)進(jìn)行高精度定位的情況，可以推廣應(yīng)用到救援工作當(dāng)中。

分布式定位算法中每個(gè)節(jié)點(diǎn)都根據(jù)從通信范圍內(nèi)的鄰居節(jié)點(diǎn)傳來的信息在后臺(tái)計(jì)算自己的位置，降低了網(wǎng)絡(luò)通信量且節(jié)省了網(wǎng)絡(luò)資源的消耗，可推廣至各種規(guī)模的無線傳感器網(wǎng)絡(luò)。但由于普通節(jié)點(diǎn)資源受限，計(jì)算能力和存儲(chǔ)能力相對(duì)于服務(wù)器來說較弱，難以實(shí)現(xiàn)復(fù)雜算法。

2 無需測(cè)距的定位算法

無需測(cè)距的定位是指依靠網(wǎng)絡(luò)連通性即可完成定位，無需測(cè)量絕對(duì)距離和角度的方式，它通過估計(jì)節(jié)點(diǎn)間的跳數(shù)或確定包含未知節(jié)點(diǎn)的可能區(qū)域從而求質(zhì)心的方法來確定未知節(jié)點(diǎn)的位置。下文將無需測(cè)距的三維定位算法按照節(jié)點(diǎn)處理信息的方式分為集中式定位和分布式定位分別進(jìn)行研究。

(1)集中式定位。

文獻(xiàn)[13]提出了一種無需測(cè)距的基于球殼交集的APIS算法。該方案將基于三角形的APIT算法擴(kuò)充到三維，劃分空間為球殼并取球殼交集來定位，其定位精度受錨節(jié)點(diǎn)密度和分布影響較大。

其他還有一些同APIS類似的，將APIT擴(kuò)展到三維空間來使用的算法，如：基于垂直平分線的PB-APIT算法[14]；可以為周圍鄰居錨節(jié)點(diǎn)少于三個(gè)的未知節(jié)點(diǎn)定位的RSSI-APIT算法[15]；在APIT中采用目標(biāo)搜索的算法[16]；適用于立方體空間，利用正中面的APIT-3D算法[17]；使用了蒙特卡洛法和RSSI濾波抽樣法的MC-APIT算法[18]。文獻(xiàn)[19]總結(jié)了上述算法的定位精度，提出了基于費(fèi)馬點(diǎn)分離的FM-APIT-3D算法。如圖2所示，利用費(fèi)馬點(diǎn)將三棱錐劃分為四塊，可以顯著改善定位精度和覆蓋率。以上與APIT有關(guān)的幾種方法均易受到錨節(jié)點(diǎn)密度及分布的影響。

圖2 費(fèi)馬點(diǎn)分離模型

文獻(xiàn)[20]研究了最簡(jiǎn)單的無需測(cè)距的3D-質(zhì)心定位算法。錨節(jié)點(diǎn)向周圍發(fā)送包含自己位置信息的信標(biāo)，未知節(jié)點(diǎn)收集到鄰居錨節(jié)點(diǎn)發(fā)來的信標(biāo)后通過計(jì)算多個(gè)錨節(jié)點(diǎn)坐標(biāo)的質(zhì)心來估計(jì)自己的位置。該算法雖成本、耗能較低，但同時(shí)定位誤差很大。

文獻(xiàn)[21-22]提出了3D-加權(quán)質(zhì)心定位算法，在計(jì)算質(zhì)心的過程中引入了錨節(jié)點(diǎn)與未知節(jié)點(diǎn)之間的邊權(quán)。文獻(xiàn)[23]提出的改進(jìn)的加權(quán)質(zhì)心定位算法使用一個(gè)優(yōu)化閾值來限制錨節(jié)點(diǎn)的數(shù)量，提高了定位精度。文獻(xiàn)[24]在3D-加權(quán)質(zhì)心定位算法中引入了Mamdani&Suggano模糊推理系統(tǒng)，結(jié)合RSSI解決了邊權(quán)如何尋找和計(jì)算的問題。

文獻(xiàn)[25]提出了一種基于球面坐標(biāo)的SBLS算法。未知節(jié)點(diǎn)通過與移動(dòng)錨節(jié)點(diǎn)之間交互的信息來構(gòu)建多元線性方程組，再利用克萊姆法則進(jìn)行求解并解決多解、無解問題，最終利用最小二乘法進(jìn)行優(yōu)化。

無需測(cè)距的三維定位算法經(jīng)常被用于以測(cè)控和控制為目的的應(yīng)用當(dāng)中，此類應(yīng)用中大量的數(shù)據(jù)需要匯總到數(shù)據(jù)中心進(jìn)行處理。此外，集中式定位算法定位精度較高，但同時(shí)也會(huì)因網(wǎng)絡(luò)資源緊缺而受到限制。

(2)分布式定位。

文獻(xiàn)[26]在結(jié)合了ROCRSSI算法中錨節(jié)點(diǎn)多次廣播信標(biāo)信息的方案和ALS算法中無線電信號(hào)強(qiáng)度隨傳輸距離的增加而衰減的特性的基礎(chǔ)上，提出了DBRF-3D算法。該算法屬于無需測(cè)距的定位算法，只需要錨節(jié)點(diǎn)廣播自身的信標(biāo)信息，在錨節(jié)點(diǎn)一跳通信范圍內(nèi)的未知節(jié)點(diǎn)通過監(jiān)聽到的信標(biāo)信息來估計(jì)自身位置。

文獻(xiàn)[27]將分布式定位算法Boundingbox擴(kuò)展到三維空間。未知節(jié)點(diǎn)的所有鄰居錨節(jié)點(diǎn)根據(jù)通信范圍作球，各在所作球中取一個(gè)三邊分別與x,y,z軸平行的內(nèi)接正方體，再取各內(nèi)接正方體的交集確定出包含有未知節(jié)點(diǎn)的限定立方體，之后用該立方體的質(zhì)心作為未知節(jié)點(diǎn)的估計(jì)位置。該算法的優(yōu)點(diǎn)是定位計(jì)算量很小，適用于運(yùn)算復(fù)雜的三維定位。

文獻(xiàn)[28]在結(jié)合DV-Hop和Boundingbox的基礎(chǔ)上提出DB算法。該算法克服了Boundingbox算法中因?yàn)殄^節(jié)點(diǎn)通信范圍有限而對(duì)錨節(jié)點(diǎn)數(shù)量要求較高的弊端。

文獻(xiàn)[29]對(duì)定位誤差較大的三維DV-Hop算法進(jìn)行了改進(jìn)，在充分利用地形特點(diǎn)的基礎(chǔ)上提出了基于近似投影校正的三維定位算法。該算法將三維DV-Hop算法所計(jì)算出的結(jié)果近似投影到靠近地形表面的位置，大幅提高了定位精度。

文獻(xiàn)[30]提出了改進(jìn)的蝙蝠算法(IBA)并將三維定位問題轉(zhuǎn)移到全局優(yōu)化上來，改善了BA早熟收斂和收斂速度慢的缺點(diǎn)。又利用慣性權(quán)因子和Levy飛行策略修改了速度和位置的方程，加快了收斂速度并實(shí)現(xiàn)了勘測(cè)開發(fā)能力的平衡。

分布式定位算法資源利用率較高。三維環(huán)境中的節(jié)點(diǎn)定位過程相對(duì)于二維環(huán)境來說資源消耗量較大，所以更傾向于采用分布式方法。但分布式定位算法由于節(jié)點(diǎn)資源的緊缺，難以追求高精確度。

3 綜合分析

(1)基于測(cè)距的定位算法。

基于測(cè)距的定位算法相對(duì)于無需測(cè)距的定位算法來說定位精度較高，但同時(shí)也對(duì)硬件設(shè)備要求高，計(jì)算量和通信量開銷較大，這會(huì)導(dǎo)致網(wǎng)絡(luò)耗能多、成本高、生命周期短。此外，基于測(cè)距的定位算法受錨節(jié)點(diǎn)的密度及分布影響較大，且在三維環(huán)境中可能會(huì)導(dǎo)致空間多解問題。

綜合考慮上述集中式定位算法和分布式定位算法的優(yōu)缺點(diǎn)，由于分布式定位算法對(duì)節(jié)點(diǎn)計(jì)算能力和存儲(chǔ)能力的要求更具平均性，三維環(huán)境中在使用基于測(cè)距的定位算法的同時(shí)更傾向于采用分布式方法。

(2)無需測(cè)距的定位算法。

考慮到三維環(huán)境中往往有較多的障礙物阻礙電磁波的傳播，無需測(cè)距的定位算法排除了測(cè)量絕對(duì)距離和角度時(shí)的測(cè)量誤差，所受環(huán)境干擾較小，成本和功耗較低，擴(kuò)展性好，更適用于數(shù)量級(jí)較高的三維環(huán)境。但同時(shí)無需測(cè)距的定位算法定位精度普遍較低，對(duì)網(wǎng)絡(luò)連通度和錨節(jié)點(diǎn)密度要求較高。

綜合考慮上述集中式定位算法和分布式定位算法的優(yōu)缺點(diǎn)，由于分布式定位算法資源利用率較高，三維環(huán)境中節(jié)點(diǎn)定位過程的資源消耗量較大，在使用無需測(cè)距的定位算法的同時(shí)更傾向于采用分布式方法。

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

文中對(duì)無線傳感器網(wǎng)絡(luò)中的三維定位算法進(jìn)行了研究。目前所研究的三維定位算法大部分是通過對(duì)二維定位算法進(jìn)行改進(jìn)得來的，一定程度上會(huì)提高原算法的時(shí)間和空間復(fù)雜度，同時(shí)它們?cè)谟?jì)算量、通信量和精度等方面存在較大的差別，適用范圍也有所不同。雖然說三維定位近年來已經(jīng)取得了長(zhǎng)足進(jìn)步，但還是有一些方面亟待完善：

(1)傳統(tǒng)的獲得錨節(jié)點(diǎn)位置的方法是通過最初為節(jié)點(diǎn)配備GPS來實(shí)現(xiàn)的，但因?yàn)镚PS的功耗大、體積大、成本高，并且在嚴(yán)重信號(hào)阻礙的環(huán)境中信號(hào)可能會(huì)十分微弱甚至接收不到。無錨節(jié)點(diǎn)的定位算法，可以替代多個(gè)不同位置的靜止錨節(jié)點(diǎn)的移動(dòng)錨節(jié)點(diǎn)算法將會(huì)解決無線傳感器網(wǎng)絡(luò)定位應(yīng)用中GPS的配置問題，是今后的一大研究熱點(diǎn)。

(2)基于測(cè)距的定位算法常借助電磁波信號(hào)測(cè)量距離，雖然能夠?qū)崿F(xiàn)精確定位，但對(duì)硬件設(shè)備要求高，計(jì)算量和通信量開銷較大，電磁波的傳播在三維環(huán)境中會(huì)受到較多障礙物的阻礙。同時(shí)無需測(cè)距的定位算法對(duì)網(wǎng)絡(luò)連通度和錨節(jié)點(diǎn)密度要求較高，定位精度普遍較低。未來的三維定位將把降低基于測(cè)距的定位算法的硬件代價(jià)，提高無需測(cè)距的定位算法的定位精度和魯棒性作為研究熱點(diǎn)。

(3)集中式定位算法中服務(wù)器節(jié)點(diǎn)的計(jì)算量和存儲(chǔ)量沒有限制，但由于需要傳感器節(jié)點(diǎn)和服務(wù)器節(jié)點(diǎn)之間的大量通信，網(wǎng)絡(luò)通信量較大，雖然定位精度較高，但不適用于資源受限型網(wǎng)絡(luò)。分布式定位算法資源利用率較高，但由于單個(gè)節(jié)點(diǎn)資源受限，難以實(shí)現(xiàn)復(fù)雜算法，定位精度較低。未來的研究方向除了降低集中式方法的通信資源消耗，提高集中式方法的定位精度以外，還可以綜合集中式定位和分布式定位的優(yōu)點(diǎn)形成混合式定位算法，以平衡資源利用率和定位精度之間的矛盾，但實(shí)施過程較為復(fù)雜。

總體來說，節(jié)點(diǎn)的位置信息是無線傳感器網(wǎng)絡(luò)應(yīng)用的基礎(chǔ)。未來三維定位算法的研究熱點(diǎn)是進(jìn)一步提高定位精度、定位覆蓋率，增強(qiáng)魯棒性，降低能耗，以便在無線傳感器網(wǎng)絡(luò)中進(jìn)行大規(guī)模的實(shí)際應(yīng)用。

[1]ZhangL,ZhouX,ChengQ.Landscape-3D:arobustlocalizationschemeforsensornetworksovercomplex3Dterrains[C]//Proceedingsof31stIEEEconferenceonlocalcomputernetworks.[s.l.]:IEEEComputerSociety,2006:239-246.

[2]VillasLA,GuidoniDL,UeyamaJ.3Dlocalizationinwirelesssensornetworksusingunmannedaerialvehicle[C]//12thIEEEinternationalsymposiumonnetworkcomputingandapplications.[s.l.]:IEEE,2013:135-142.

[3]CardosoCB,GuidoniDL,MaiaG,etal.Anenergyconsumptionawaresolutionforthe3DlocalizationandsynchronizationproblemsinWSNs[C]//Braziliansymposiumoncomputernetworksanddistributedsystems.[s.l.]:IEEE,2014:376-385.

[4]SalehinejadH,ZadehR,LiscanoR,etal.3Dlocalizationinlarge-scalewirelesssensornetworks:amicro-differentialevolutionapproach[C]//IEEE25thannualinternationalsymposiumonpersonal,indoor,andmobileradiocommunication.[s.l.]:IEEE,2014.

[5]ZhouZ,HuP,LiuQ,etal.MDS-basedfastlocalizationalgorithmforwirelesssensornetworks[J].ChineseJournalofSensorsandActuators,2007,20(10):2303-2307.

[6]WangJ,ChengZ,JingL,etal.Designofa3DlocalizationmethodforsearchingsurvivorsafteranearthquakebasedonWSN[C]//3rdinternationalconferenceonawarenessscienceandtechnology.[s.l.]:IEEE,2011:221-226.

[7] 唐良瑞,宮 月,羅藝婷,等.一種基于Euclidean的無線傳感器網(wǎng)絡(luò)三維定位算法[J].電子學(xué)報(bào),2012,40(4):821-825.

[8]ZhangA,YeX,HuH.Pointintriangletestingbasedtrilaterationlocalizationalgorithminwirelesssensornetworks[J].KsiiTransactionsonInternet&InformationSystems,2012,6(10):2567-2586.

[9]WangRJ,BaoHL,ChenDJ,etal.3D-CCD:anovel3Dlocalizationalgorithmbasedonconcave/convexdecompositionandlayeringschemeinWSNs[J].AdHoc&SensorWirelessNetworks,2014,23(3):235-254.

[10]LiangJ,ShaoJ,XuY,etal.Sensornetworklocalizationinconstrained3-Dspaces[C]//Proceedingsofthe2006IEEEinternationalconferenceonmechatronicsandautomation.[s.l.]:IEEE,2006:49-54.

[11]RongbinQI,SijinLI,TianyiMA,etal.Iteration-basedlocalizationalgorithmforwirelesssensornetworkinthree-dimensionalspace[J].ChineseJournalofSensors&Actuators,2012,25(5):644-650.

[12]KumarA,KhoslaA,SainiJS,etal.Stochasticalgorithmsfor3Dnodelocalizationinanisotropicwirelesssensornetworks[J].AdvancesinIntelligentSystems&Computing,2013,201:1-14.

[13] 呂良彬,曹 陽(yáng),高 洵,等.基于球殼交集的傳感器網(wǎng)絡(luò)三維定位算法[C]//2006年全國(guó)通信軟件學(xué)術(shù)會(huì)議.出版地不詳:出版者不詳,2006.

[14]YangJ,LiuF.AmodifiedlocalizationalgorithmofAPITbasedonperpendicularbisectorfeatureforwirelesssensornetwork[J].ChineseJournalofSensors&Actuators,2008,21(8):1453-1457.

[15]FengXF,QiHB.ImprovementandsimulationforalocalizationbasedonAPIT[C]//Internationalconferenceoncomputertechnologyanddevelopment.[s.l.]:IEEE,2009:68-72.

[16]LiX,GaoH,LvL.AnimprovedAPITalgorithmbasedondirectionsearching[C]//5thinternationalconferenceonwirelesscommunications,networkingandmobilecomputing.[s.l.]:IEEE,2009:1-4.

[17]LiuZQ,WangXF.WSNthree-dimensionallocalizationmethodbasedonmidperpendicularplanesegmentation[J].ComputerEngineering,2010,36(14):90-92.

[18]WangJ,FuJ.ResearchonAPITandMonteCarlomethodoflocalizationalgorithmforwirelesssensornetworks[M]//Lifesystemmodelingandintelligentcomputing.Berlin:Springer,2010:128-137.

[19]XiongX,YanC.Three-dimensionallocalizationalgorithmofAPITbasedonfermat-pointdividedforwirelesssensornetworks[C]//Seventhinternationalsymposiumoncomputationalintelligenceanddesign.[s.l.]:IEEE,2014:521-524.

[20]BulusuN,HeidemannJ,EstrinD.GPS-lesslowcostoutdoorlocalizationforverysmalldevices[J].RonalOmmnaon,2000,7(5):28-34.

[21]ShiQ,HuoH,FangT,etal.A3Dnodelocalizationschemeforwirelesssensornetworks[J].IEICEElectronicsExpress,2001,666(43):167-172.

[22]LiuL,ChongJS,WangXQ,etal.Adaptivesourcelocationestimationbasedoncompressedsensinginwirelesssensornetworks[J].InternationalJournalofDistributedSensorNetworks,2012,2012:141-149.

[23]XuL,WangK,JiangY,etal.Astudyon2Dand3Dweightedcentroidlocalizationalgorithminwirelesssensornetworks[C]//3rdinternationalconferenceonadvancedcomputercontrol.[s.l.]:IEEE,2011:155-159.

[24]NandaM,KumarA,KumarS.Localizationof3DWSNusingMamdaniSuganofuzzyweightedcentriodapproaches[C]//IEEEstudents’conferenceonelectrical,electronicsandcomputerscience.[s.l.]:IEEE,2012:1-5.

[25]DaiGuilan,ZhaoChongchong,QiuYan.Alocalizationschemebasedonsphereforwirelesssensornetworkin3D[J].ActaElectronicaSinica,2008,36(7):1297-1303.

[26]ZhuH.Anoveldistributedandrange-freelocalizationalgorithminthree-dimensionalwirelesssensornetworks[J].ChineseJournalofSensors&Actuators,2009,22(11):1655-1660.

[27]LiJuan,WangKe,LuChanggang.Boundingcube:alocalizationschemeforwirelesssensornetworksin3D[J].PeriodicalofOceanUniversityofChina,2009,39(6):1265-1268.

[28]YangS,ZhangB,WangK,etal.DB:adeveloped3DpositioningalgorithminWSNbasedonDV-Hopandboundingcube[C]//Internationalconferenceoncomputerandmanagement.[s.l.]:IEEE,2011:1-4.

[29] 胡中棟,謝金偉.基于近似投影校正的無線傳感器網(wǎng)絡(luò)三維定位機(jī)制[J].傳感技術(shù)學(xué)報(bào),2014,27(11):1573-1577.

[30]SharmaSPKM.Radiallyoptimizedzone-dividedenergy-awareWirelessSensorNetworks(WSN)protocolusingBA(BatAlgorithm)[J].IETEJournalofResearch,2015,61(2):170-179.

Survey of 3D-localization Algorithms in Wireless Sensor Networks

ZHANG Xin-hui1,XU Jing-jing1,XU Bi-xiao2,ZHAO Xue-jian1,SUN Zhi-xin1

(1.College of Internet of Things,Nanjing University of Posts and Telecommunications,Nanjing 210003,China;2.College of Science,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

The information of node localization is the base in applications of Wireless Sensor Networks (WSNs).Node localization,as a critical technology of WSN,has been the basis of most applications of WSN.At present,the research on sensor network localization commonly on two-dimensional,but in practical application,because of limit to terrain or environment,the wireless sensor sometimes distribute in three-dimensional,not on plane,so expanding the research to three-dimensional is need.According to the characteristics of static node localization algorithm for wireless sensor network,the classification of 2D-localization algorithms are introduced.On this basis,the state-of-the-art researches of 3D-localization theories and algorithms are systematically summarized.The 3D-localization algorithms are mainly divided into range-based and range-free.Each category is divided into centralized and distributed again.Then some popular 3D-localization algorithms are introduced in detail and summarized the advantages and disadvantages.Based on analysis of the disadvantages of existing localization algorithms,the future research directions of 3D-localization algorithms in WSNs are also pointed out.

Wireless Sensor Networks (WSNs)；Three-Dimensional (3D) space；localization algorithms；node-positioning；distance measurement

2016-02-25

2016-06-04

時(shí)間：2016-11-22

國(guó)家自然科學(xué)基金資助項(xiàng)目(60973140，61170276，61373135)；江蘇省產(chǎn)學(xué)研項(xiàng)目(BY2013011)；江蘇省科技型企業(yè)創(chuàng)新基金(BC2013027)；江蘇省高校自然科學(xué)研究重大項(xiàng)目(12KJA520003)

張欣慧(1994-)，女，研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)三維定位；趙學(xué)健，博士，副教授，碩士生導(dǎo)師，研究方向?yàn)闊o線網(wǎng)絡(luò)關(guān)鍵技術(shù)、大數(shù)據(jù)關(guān)鍵技術(shù)；孫知信，博士，教授，博士生導(dǎo)師，研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)與安全、多媒體通信、移動(dòng)互聯(lián)網(wǎng)。

http://www.cnki.net/kcms/detail/61.1450.tp.20161122.1227.008.html

TP393

A

1673-629X(2016)12-0195-05

10.3969/j.issn.1673-629X.2016.12.042