無線傳感器網絡三維定位算法研究

張欣慧，徐晶晶，許必宵，趙學健，孫知信

(1.南京郵電大學 物聯網學院，江蘇 南京 210003;2.南京郵電大學 理學院，江蘇 南京 210003)

無線傳感器網絡三維定位算法研究

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

(1.南京郵電大學 物聯網學院，江蘇 南京 210003;2.南京郵電大學 理學院，江蘇 南京 210003)

節點的位置信息是無線傳感器網絡應用的基礎。節點定位技術作為無線傳感器網絡的關鍵技術之一，是無線傳感器網絡大多數應用的基礎?，F有的大多數定位算法針對平面應用設計，而在實際應用中，由于地形限制或者環境限制，使得無線傳感器往往在空間上呈立體分布，而不是平面分布，所以需要把定位研究擴展到三維空間中。針對無線傳感器網絡靜態節點定位算法的特點，介紹了二維定位算法的分類，在此基礎上系統地研究了近年來最新的三維定位理論和算法。主要根據基于測距的定位和無需測距的定位將三維定位算法分為兩大類，每類中再分為集中式定位和分布式定位，其中詳細研究了一些熱門的三維定位算法并總結了它們的優缺點。在綜合分析當前定位算法不足的基礎上，指出了未來三維定位算法的研究方向。

無線傳感器網絡；三維空間；定位算法；節點定位；測距

0 引 言

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

盡管現實中的無線傳感器網絡往往被布置在復雜的三維地形中，但是大多數定位技術都是假定在二維網絡部署的情況下提出的，而且一般這些適用于二維地形的定位技術并不能簡單擴展到三維環境中。傳統的二維定位算法往往分為集中式定位算法和分布式定位算法，或者分為基于測距的定位算法和無需測距的定位算法。此外，在基于測距的定位中常用的測距算法包括ToA、RSSI、AoA、TDoA。這些分類方式同樣可以擴展到更符合真實情況的三維環境下的坐標計算和定位算法中。

三維定位算法的研究目前有兩個大方向：一是將三維定位的問題降維到二維平面上來解決；二是通過對二維定位算法進行改進，將之擴展到三維定位上來，但這會提高原算法的時間和空間復雜度。大部分二維定位算法的研究文獻都是根據定位的實現方式來分類，例如劃分為集中式定位和分布式定位、基于測距的定位和無需測距的定位等。也有少部分文獻提出根據網絡架構進行分類，例如劃分為有錨節點的定位和無錨節點的定位等。

文中主要根據基于測距的定位和無需測距的定位將三維定位算法分為兩大類，每類中再分為集中式定位和分布式定位，其中詳細研究了一些熱門的三維定位算法并分析總結了它們的優缺點。

1 基于測距的定位算法

基于測距的定位是指首先通過測距算法測量節點間的距離或者角度信息，之后利用所測信息通過數學計算得出未知節點坐標的方式。下文將基于測距的三維定位算法按照節點處理信息的方式分為集中式定位和分布式定位分別進行研究。

(1)集中式定位。

集中式定位是指將各個節點所收集到的信息傳送到服務器節點進行處理，計算出未知節點坐標位置的方式。

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

文獻[4]提出結合MDESM算法的微差分進化算法，根據收集到的來自UAV的信息計算未知節點的位置坐標。

文獻[5]以節點間的歐氏距離構成的相似度矩陣為基礎，結合計算量過高的MDSMAP算法和LMDS算法并加入對測距信息的利用策略后，提出了FastMDSMAP算法，減少了定位時節點的能量消耗和計算時的時間復雜度。

圖1 Landscape-3D定位算法

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

文獻[7]基于Euclidean算法提出了一種三維定位算法，通過構建立體模型將未知節點與錨節點之間距離的計算問題轉化為六面體模型頂點間距離的求解問題，再利用所提出的坐標法求解節點的位置并通過循環迭代求精。

文獻[8]提出一種建立在RSSI值基礎上、復雜度有所減少的3D-三邊定位法COLA。該算法通過使用擁有兩個位置的超級錨節點(這兩個位置成對，只有z軸坐標不同)來降低復雜度。

文獻[9]提出了一種在使用RSSI和三邊定位法計算未知節點坐標之前預處理的方案：基于凹凸性劃分和分層的3D-CDD算法。該算法首先根據節點的高度將WSNs定位區域水平劃分為幾個適當的邏輯層，并在每層中根據凹凸性的不同劃分為幾個分支區域，以減小由于網絡地形的凹凸程度不同造成的誤差。

基于測距的三維定位算法中需要測量大量的距離信息或角度信息，且與二維定位算法相比增加了一個維度的信息，這恰好迎合了集中式定位算法中服務器節點計算量和存儲量沒有限制的優點。但同時集中式定位算法需要傳感器節點和服務器節點之間的大量通信，導致網絡通信量較大，且距離服務器節點距離較近的節點耗能大且易失效，故集中式定位算法不適用于資源受限型網絡。

(2)分布式定位。

分布式定位是指未知節點根據與通信范圍內的鄰居節點交換的信息在后臺自行計算自己的坐標位置的方式。

文獻[10]提出了基于傳統三角計算的Constrained-3D算法。該方案假定錨節點都部署在底部同一平面內，以該平面為中心向上依靠測量與鄰居節點之間的距離來推算未知節點的位置。

文獻[11]提出的ILAH-3D算法將二維的經典算法AHLos擴展到三維，增加了普通節點升級為錨節點的驗證條件，并采用加權最小二乘法來減少累積誤差。該算法還通過約束協作算法的執行條件，借助節點間位置關系的同時再利用新升級的錨節點進行重復定位運算，以提高節點定位的精度。

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

分布式定位算法中每個節點都根據從通信范圍內的鄰居節點傳來的信息在后臺計算自己的位置，降低了網絡通信量且節省了網絡資源的消耗，可推廣至各種規模的無線傳感器網絡。但由于普通節點資源受限，計算能力和存儲能力相對于服務器來說較弱，難以實現復雜算法。

2 無需測距的定位算法

無需測距的定位是指依靠網絡連通性即可完成定位，無需測量絕對距離和角度的方式，它通過估計節點間的跳數或確定包含未知節點的可能區域從而求質心的方法來確定未知節點的位置。下文將無需測距的三維定位算法按照節點處理信息的方式分為集中式定位和分布式定位分別進行研究。

(1)集中式定位。

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

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

圖2 費馬點分離模型

文獻[20]研究了最簡單的無需測距的3D-質心定位算法。錨節點向周圍發送包含自己位置信息的信標，未知節點收集到鄰居錨節點發來的信標后通過計算多個錨節點坐標的質心來估計自己的位置。該算法雖成本、耗能較低，但同時定位誤差很大。

文獻[21-22]提出了3D-加權質心定位算法，在計算質心的過程中引入了錨節點與未知節點之間的邊權。文獻[23]提出的改進的加權質心定位算法使用一個優化閾值來限制錨節點的數量，提高了定位精度。文獻[24]在3D-加權質心定位算法中引入了Mamdani&Suggano模糊推理系統，結合RSSI解決了邊權如何尋找和計算的問題。

文獻[25]提出了一種基于球面坐標的SBLS算法。未知節點通過與移動錨節點之間交互的信息來構建多元線性方程組，再利用克萊姆法則進行求解并解決多解、無解問題，最終利用最小二乘法進行優化。

無需測距的三維定位算法經常被用于以測控和控制為目的的應用當中，此類應用中大量的數據需要匯總到數據中心進行處理。此外，集中式定位算法定位精度較高，但同時也會因網絡資源緊缺而受到限制。

(2)分布式定位。

文獻[26]在結合了ROCRSSI算法中錨節點多次廣播信標信息的方案和ALS算法中無線電信號強度隨傳輸距離的增加而衰減的特性的基礎上，提出了DBRF-3D算法。該算法屬于無需測距的定位算法，只需要錨節點廣播自身的信標信息，在錨節點一跳通信范圍內的未知節點通過監聽到的信標信息來估計自身位置。

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

文獻[28]在結合DV-Hop和Boundingbox的基礎上提出DB算法。該算法克服了Boundingbox算法中因為錨節點通信范圍有限而對錨節點數量要求較高的弊端。

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

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

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

3 綜合分析

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

基于測距的定位算法相對于無需測距的定位算法來說定位精度較高，但同時也對硬件設備要求高，計算量和通信量開銷較大，這會導致網絡耗能多、成本高、生命周期短。此外，基于測距的定位算法受錨節點的密度及分布影響較大，且在三維環境中可能會導致空間多解問題。

綜合考慮上述集中式定位算法和分布式定位算法的優缺點，由于分布式定位算法對節點計算能力和存儲能力的要求更具平均性，三維環境中在使用基于測距的定位算法的同時更傾向于采用分布式方法。

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

考慮到三維環境中往往有較多的障礙物阻礙電磁波的傳播，無需測距的定位算法排除了測量絕對距離和角度時的測量誤差，所受環境干擾較小，成本和功耗較低，擴展性好，更適用于數量級較高的三維環境。但同時無需測距的定位算法定位精度普遍較低，對網絡連通度和錨節點密度要求較高。

綜合考慮上述集中式定位算法和分布式定位算法的優缺點，由于分布式定位算法資源利用率較高，三維環境中節點定位過程的資源消耗量較大，在使用無需測距的定位算法的同時更傾向于采用分布式方法。

4 結束語

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

(1)傳統的獲得錨節點位置的方法是通過最初為節點配備GPS來實現的，但因為GPS的功耗大、體積大、成本高，并且在嚴重信號阻礙的環境中信號可能會十分微弱甚至接收不到。無錨節點的定位算法，可以替代多個不同位置的靜止錨節點的移動錨節點算法將會解決無線傳感器網絡定位應用中GPS的配置問題，是今后的一大研究熱點。

(2)基于測距的定位算法常借助電磁波信號測量距離，雖然能夠實現精確定位，但對硬件設備要求高，計算量和通信量開銷較大，電磁波的傳播在三維環境中會受到較多障礙物的阻礙。同時無需測距的定位算法對網絡連通度和錨節點密度要求較高，定位精度普遍較低。未來的三維定位將把降低基于測距的定位算法的硬件代價，提高無需測距的定位算法的定位精度和魯棒性作為研究熱點。

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

總體來說，節點的位置信息是無線傳感器網絡應用的基礎。未來三維定位算法的研究熱點是進一步提高定位精度、定位覆蓋率，增強魯棒性，降低能耗，以便在無線傳感器網絡中進行大規模的實際應用。

[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的無線傳感器網絡三維定位算法[J].電子學報,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] 呂良彬,曹 陽,高 洵,等.基于球殼交集的傳感器網絡三維定位算法[C]//2006年全國通信軟件學術會議.出版地不詳:出版者不詳,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] 胡中棟,謝金偉.基于近似投影校正的無線傳感器網絡三維定位機制[J].傳感技術學報,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

時間：2016-11-22

國家自然科學基金資助項目(60973140，61170276，61373135)；江蘇省產學研項目(BY2013011)；江蘇省科技型企業創新基金(BC2013027)；江蘇省高校自然科學研究重大項目(12KJA520003)

張欣慧(1994-)，女，研究方向為無線傳感器網絡三維定位；趙學健，博士，副教授，碩士生導師，研究方向為無線網絡關鍵技術、大數據關鍵技術；孫知信，博士，教授，博士生導師，研究方向為計算機網絡與安全、多媒體通信、移動互聯網。

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