毛科技，趙小敏，邵 奔，陳慶章

(浙江工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，杭州 310023)

無線傳感網(wǎng)絡(luò)節(jié)點(diǎn)定位，簡單的說就是節(jié)點(diǎn)通過某種方法或者執(zhí)行某種算法獲得自己在網(wǎng)絡(luò)中的位置，通常以坐標(biāo)的形式表示，也可以用大致的位置(如房號)等表示［1］。由于全球定位系統(tǒng)(GPS)技術(shù)成熟，獲得節(jié)點(diǎn)的位置可以通過給節(jié)點(diǎn)安裝GPS接收器直接獲得，但受其價格、體積、功耗、信號屏蔽等諸多因素制約，所以通過GPS獲得所有節(jié)點(diǎn)的位置存在一定的困難。目前大多數(shù)的定位技術(shù)都是利用網(wǎng)絡(luò)中少量已知位置的節(jié)點(diǎn)通過定位算法獲得其它未知節(jié)點(diǎn)的位置，已知位置的節(jié)點(diǎn)稱為參考點(diǎn)，可以人為放置或者通過GPS獲得。未知節(jié)點(diǎn)的位置可以是相對于參考點(diǎn)建立的坐標(biāo)系，也可以是一個絕對位置(如參考點(diǎn)采用 GPS 定位)［2－3］。

由于無線傳感網(wǎng)絡(luò)節(jié)點(diǎn)分布的隨機(jī)性和節(jié)點(diǎn)感知信息的位置依賴性，節(jié)點(diǎn)準(zhǔn)確地進(jìn)行自身定位是無線傳感網(wǎng)絡(luò)應(yīng)用的重要條件。

1 研究背景

由于無線傳感網(wǎng)絡(luò)對節(jié)點(diǎn)的能耗、成本、體積等要求，所以定位算法必須在滿足上述要求的前提下才有實(shí)際的使用價值。目前，科研工作者已經(jīng)研究出了多種定位算法，如 SpotON［4］，APS［5］，MDS-MAP［6］等。另外，無線傳感網(wǎng)絡(luò)的定位算法分類方法眾多，較為典型有基于測距(Rang-based)和距離無關(guān)(Rangfree)的分類方法。其中基于測距的定位算法常用的測距技術(shù)有 RSSI，TOA，TDOA，AOA［7］等。大部分的測距算法都靠額外設(shè)備來提高定位精度，如使用RFID技術(shù)、超寬帶(UWB)技術(shù)、超聲波技術(shù)和使用天線陣列進(jìn)行基于角度的定位等［8－10］。距離無關(guān)的定位算法則是利用網(wǎng)絡(luò)的連通性或者跳數(shù)對未知節(jié)點(diǎn)的位置進(jìn)行估計。由于測距技術(shù)在功耗、成本等方面有較高的要求，所以在距離無關(guān)算法上的研究是非常具有意義的，目前眾多的距離無關(guān)算法中DV-Hop算法是最為典型并且備受關(guān)乎的。DV-Hop算法思想簡單，容易實(shí)現(xiàn)，但是由于其定位精度較低，受網(wǎng)絡(luò)拓?fù)溆绊戄^大，且跳數(shù)越多誤差越大，所以在實(shí)際的無線傳感網(wǎng)絡(luò)中應(yīng)用效果較差。

1.1 三維定位問題

到目前為止，很多學(xué)者已經(jīng)提出了比較典型的面向二維平面的定位算法，然而很少有涉及如何解決三維空間的定位問題。但是實(shí)際環(huán)境中傳感器節(jié)點(diǎn)是經(jīng)常被部署在三維空間中的，比如多樓層的建筑物里，地面起伏不定的山坡上以及水下空間等等。在三維環(huán)境下的定位問題相比于二維平面顯然會有一定區(qū)別，其主要難點(diǎn)如下:

(1)定位所需的參考點(diǎn)增加 在二維平面里，定位一個未知節(jié)點(diǎn)只需三個參考節(jié)點(diǎn)，而在三維空間里，最少需要四個參考節(jié)點(diǎn)才能定位一個未知節(jié)點(diǎn)。這帶來的不僅是對參考點(diǎn)密度的要求，而且增加了算法復(fù)雜度。

(2)地形障礙對傳輸信號的影響 室外二維環(huán)境下，節(jié)點(diǎn)的傳輸信號一般不受地形或者障礙影響，但是三維空間里地形因素帶來的非視距傳輸對信號的影響是不可忽視的，所以使用信號強(qiáng)度等計算節(jié)點(diǎn)之間距離的算法就會產(chǎn)生一定誤差，使用非測距算法的同時也要考慮節(jié)點(diǎn)最小通信半徑受影響帶來的連通性問題。若不考慮這些因素肯定會對定位精度產(chǎn)生很大影響。

(3)難以滿足特定應(yīng)用場合的需求 對于一些特定應(yīng)用場合的三維定位，如建筑物中，定位結(jié)果必須能夠反映出節(jié)點(diǎn)所處的樓層。由于樓層之間的距離有限，無法達(dá)到厘米級精度的定位算法基本難以確定節(jié)點(diǎn)處于哪一樓層，這是室內(nèi)三維定位目前急需解決的問題。

本研究將DV-Hop思想用于三維定位，其一是將三邊定位改為四邊定位;其二是解決網(wǎng)絡(luò)拓?fù)浜蛥⒖键c(diǎn)分布對定位算法造成的影響，提出一種定位算法的優(yōu)化方法以提高精度;其三是考慮建筑物中三維定位存在的問題，結(jié)合實(shí)際應(yīng)用，提出一種適用于建筑物內(nèi)的復(fù)雜度低的三維定位算法。

2 基于共面度的三維定位算法

在定位過程中，利用多邊定位法時至少能確定一個未知節(jié)點(diǎn)的參考點(diǎn)組合叫做一個定位單元。在二維平面中，當(dāng)計算出一個定位單元中每個參考點(diǎn)到未知節(jié)點(diǎn)的距離時，就可以利用三邊測量法去確定未知節(jié)點(diǎn)的位置。但是在計算機(jī)未知節(jié)點(diǎn)到參考點(diǎn)的距離時，往往存在一定的誤差，這使得原本三邊定位中的三個圓并不交于一點(diǎn)，所以要用估算的方法去確定未知節(jié)點(diǎn)的位置。但是當(dāng)定位單元中的三個參考點(diǎn)分布在近似于一條直線的情況下時，三個圓的交點(diǎn)有兩個，所以不能估計未知節(jié)點(diǎn)的位置［11］。同樣的問題在三維定位中也存在，在三維空間中，由于測距誤差使得定位單元中的四個球面未必存在交點(diǎn)，同樣當(dāng)四點(diǎn)近似共面時，四個球面的交點(diǎn)有兩個，從而難以估算未知節(jié)點(diǎn)的位置。目前二維定位已有學(xué)者提出了共線度的概念［11］，那么為了解決三維定位中的問題，本文引入了共面度的概念，并提出了基于共度面的三維定位算法。

2.1 共面度的定義

共面度即表示三維空間中四個點(diǎn)的共面程度，文獻(xiàn)［12］中提出了四面體形狀測量被用于評價有限元網(wǎng)格(Finite Element Meshes)中四面體的質(zhì)量，其中分析和比較了四面體形狀的三種不同測量方法:最小立體角(Minimum Solid Angle)，半徑比(Radius Ratio)和均值比(Mean Ratio)。下面主要介紹半徑比法。

在二維平面中，三角形的內(nèi)切圓半徑和外接圓半徑之比的兩倍可以表示三角形的半徑比，其取值范圍為［0，1］，圖1表示了二維平面下三角形的半徑比。那么擴(kuò)展到三維空間，四面體T的半徑比則定義為ρ=3rin/rcirc，其中rin和rcirc分別為四面體T的內(nèi)切球半徑和外接球半徑。

圖1 二維平面的三角形半徑比

文獻(xiàn)［13］中給出了計算四面內(nèi)切球和外接球半徑的公式:

其中v為四面體的體積，si是四面體四個面的面積，a，b，c分別為四面體三組對棱長度的乘積。

任意四面體的體積計算問題可以通過矩陣計算獲得。根據(jù)四面體半徑比的計算公式，結(jié)合式(1)和式(2)得到四面體半徑比ρ的計算公式為:

其比值范圍為(0，1］，當(dāng)接近0時四面體的四個頂點(diǎn)近似共面，為1時轉(zhuǎn)化為正四面體。

為了簡便起見，采用半徑比法的共面度如下式表示

其取值范圍為［0，1］。

2.2 多重閥值約束策略

在DV-Hop算法的第二階段，參考點(diǎn)獲得與鄰近參考點(diǎn)之間的距離和跳數(shù)信息后，計算平均每跳距離。由于該算法針對的是多跳網(wǎng)絡(luò)，在計算平均每跳距離時可能將很遠(yuǎn)的參考點(diǎn)也包含進(jìn)來，在對DV-Hop算法進(jìn)行仿真后發(fā)現(xiàn)，若參考點(diǎn)之間的跳數(shù)越多，即距離越遠(yuǎn)，參考點(diǎn)計算的平均每跳距離誤差也更大。另外在算法的第三階段，即定位未知節(jié)點(diǎn)的時候，未知節(jié)點(diǎn)和定位單元之間的距離越遠(yuǎn)，共面度約束帶來的定位影響越小，且定位誤差也越大。所以我們需要對算法引入兩個閾值進(jìn)行約束。

2.2.1 跳數(shù)閾值

在大規(guī)模無線傳感網(wǎng)絡(luò)中，節(jié)點(diǎn)數(shù)量多且分布廣，跳數(shù)閾值(thre_hop)確保了在定位過程中所有傳感器節(jié)點(diǎn)只與鄰近的幾個節(jié)點(diǎn)交換定位所需信息。采用跳數(shù)閾值對節(jié)點(diǎn)選擇進(jìn)行約束不但避免了因跳數(shù)過多帶來的定位誤差，而且對于某一未知節(jié)點(diǎn)，參與定位的定位單元減少，使得算法復(fù)雜度降低，延長了節(jié)點(diǎn)的使用壽命。

2.2.2 共面度閾值

共面度閾值(thre_hop)保證了對最佳定位單元的選擇，但是設(shè)置共面度閾值也存在其優(yōu)缺點(diǎn)，優(yōu)點(diǎn)是排除了參考點(diǎn)共面帶來的節(jié)點(diǎn)不可定位問題并且提高了定位精度，缺點(diǎn)則是造成了總體可定位節(jié)點(diǎn)的比例降低，其原因是共面度閾值造成了許多定位單元不能參與定位，對于某些與少數(shù)參考點(diǎn)連通的未知節(jié)點(diǎn)來說，設(shè)置這一約束條件很容易使得該點(diǎn)成為不可定位節(jié)點(diǎn)。

總之，多重閾值的約束策略對定位精度的提高和算法復(fù)雜度的降低是顯而易見的，但是閾值是一個靈活的數(shù)字，不能光評理論去討論閾值的最優(yōu)解，只有通過模擬和實(shí)際應(yīng)用才能找到權(quán)衡各個方面的最佳閾值。

3 算法仿真與分析

在MATLAB6.5下對本文提出的算法進(jìn)行了仿真，并且比較對象是在三維空間中利用四邊定位法的DV-Hop算法，主要的性能指標(biāo)有算法的定位誤差率(Localization Error Ratio，LER)，定義為未知節(jié)點(diǎn)定位誤差的平均值與節(jié)點(diǎn)通信半徑的比值;算法的可定位節(jié)點(diǎn)比例(Localized Node Proportion，LNP)，定義為定位算法運(yùn)行結(jié)束后能夠成功定位的未知節(jié)點(diǎn)總數(shù)占網(wǎng)絡(luò)中所有未知節(jié)點(diǎn)總數(shù)的比例，和不良節(jié)點(diǎn)比例(Bad Node Proportion，BNP)，定義為定位誤差大于節(jié)點(diǎn)通信半徑的不良節(jié)點(diǎn)數(shù)占所有可定位節(jié)點(diǎn)的比例。仿真實(shí)驗(yàn)還需要配置的一些參數(shù)包括節(jié)點(diǎn)的數(shù)量，節(jié)點(diǎn)的通信半徑，網(wǎng)絡(luò)密度(網(wǎng)絡(luò)平均連通度)，參考點(diǎn)比例等［14，15］。

在仿真實(shí)驗(yàn)中，首先需要給定網(wǎng)絡(luò)環(huán)境。本實(shí)驗(yàn)將節(jié)點(diǎn)所處的網(wǎng)絡(luò)環(huán)境設(shè)置在一個100 m×100 m×100 m的三維區(qū)域中，參考點(diǎn)和未知節(jié)點(diǎn)共100個，且坐標(biāo)是隨機(jī)產(chǎn)生的。在測試共面度閾值和跳數(shù)閾值變化對定位性能影響的實(shí)驗(yàn)中，得出的結(jié)論是共面度閾值和跳數(shù)閾值的設(shè)置對節(jié)點(diǎn)的LER和BNP有較為顯著的改善。但是在共面度閾值超過0.4以后不管對LER還是BNP的改善都趨于平穩(wěn)，而對LNP的降低卻比較明顯，所以將共面度閾值設(shè)置在0.4～0.6之間將既能滿足較好的定位精度也能實(shí)現(xiàn)較好的定位覆蓋率，在對原算法的比較實(shí)驗(yàn)中本文將共面度閾值設(shè)置在0.5。

節(jié)點(diǎn)通信半徑R根據(jù)不同的網(wǎng)絡(luò)密度設(shè)置，參考點(diǎn)比例分別為10%和20%，網(wǎng)絡(luò)密度從4到14的范圍內(nèi)變化。另外thre_dcp固定為0.5且thre_hop為4。最后的結(jié)果經(jīng)過多次測量取平均的方法來獲得。

觀察圖2(a)，在定位誤差率上，當(dāng)參考點(diǎn)比例相同時，DCP3D的誤差相比DV-Hop算法有10%以上的降低，并且當(dāng)網(wǎng)絡(luò)密度變化時，前者甚至在參考點(diǎn)比例為10%的情況下超過了后者在參考點(diǎn)比例20%時的定位精度，由此可見DCP3D算法相比DVHop算法在定位精度上有明顯的改善。

圖2 仿真實(shí)驗(yàn)結(jié)果對比

在可定位節(jié)點(diǎn)比例上，圖2(b)，DCP3D算法相比DV-Hop算法在網(wǎng)絡(luò)稀疏的時候降低較為明顯，但是當(dāng)網(wǎng)絡(luò)密度超過10的時候，DCP3D算法和DV-Hop算法都能夠達(dá)到90%以上的可定位節(jié)點(diǎn)比例。另外，DCP3D算法在參考點(diǎn)比例為20%的情況下，其可定位節(jié)點(diǎn)比例已經(jīng)基本與參考點(diǎn)比例10%情況下的DV-Hop算法持平。由此得出通過適當(dāng)增加網(wǎng)絡(luò)密度或者提高參考點(diǎn)比例可以使改進(jìn)算法在網(wǎng)絡(luò)覆蓋率上表現(xiàn)更好。

在不良節(jié)點(diǎn)比例上，圖2(c)，無論網(wǎng)絡(luò)密度與參考點(diǎn)比例多少，DCP3D算法都將其維持在20%以下，并且當(dāng)網(wǎng)絡(luò)密度僅僅提高至6的時候，不良節(jié)點(diǎn)比例已經(jīng)減少到10%以下，所以DCP3D算法在改善不良節(jié)點(diǎn)方面有卓越的表現(xiàn)。而DV-Hop算法在網(wǎng)絡(luò)密度和參考點(diǎn)比例低的時候，不良節(jié)點(diǎn)比例甚至超過了50%。由此可見，DCP3D算法針對節(jié)點(diǎn)密度的變化表現(xiàn)出了更好的穩(wěn)定性。

總結(jié)實(shí)驗(yàn)結(jié)果，不管在定位精度還是不良節(jié)點(diǎn)比例上，DCP3D算法都比DV-Hop算法表現(xiàn)出了更優(yōu)越的性能，但是唯一不足是可定位節(jié)點(diǎn)比例較DV-Hop算法有所降低，這可以通過增加網(wǎng)絡(luò)密度和參考點(diǎn)比例來改善。由于一般的無線傳感網(wǎng)絡(luò)節(jié)點(diǎn)的部署密度不會太低，所以改進(jìn)算法在實(shí)際應(yīng)用中的定位覆蓋率基本能夠達(dá)到要求。綜合各項性能指標(biāo)，DCP3D算法比DV-Hop算法更適用于無線傳感網(wǎng)絡(luò)三維定位。

4 總結(jié)

本文從無線傳感網(wǎng)絡(luò)定位技術(shù)存在的問題入手，分析了目前距離無關(guān)定位技術(shù)的研究現(xiàn)狀，針對三維定位技術(shù)的不成熟，在距離無關(guān)算法中典型的DV-Hop算法基礎(chǔ)上，通過引入共面度的概念消除了三維定位中定位單元近似共面對定位結(jié)果造成的影響，并且提出了多重閾值約束策略優(yōu)化算法，提高了定位精度，很大程度上減少了不良節(jié)點(diǎn)出現(xiàn)的可能性，具有較好的穩(wěn)定性。在設(shè)置合理的閾值條件下，該算法對可定位節(jié)點(diǎn)比例的影響可以忽略，證明了在總體的性能上比DV-Hop算法更為優(yōu)越。

［1］Ma Zuchang，Sun Yining，Mei Tao.Summary for Wireless Sensor Network［J］.Journal of China Institute of Communications，2004，25(4):114－124.

［2］Hady S A，Stephan O.A 3d-Localization and Terrain Modeling Technique for Wireless Sensor Networks［C］//Proc.of the 2nd ACM Int’l workshop on Foundations of wireless ad hoc and sensor networking and computing.2009，37－46.

［3］李曉維，徐勇軍，任豐原.無線傳感網(wǎng)絡(luò)技術(shù)［M］.北京理工大學(xué)出版社，2007.35.

［4］Hightower J，Boriello G，Want R.SpotON:An Indoor 3D Location Sensing Technology Based on RF Signal Strength［C］//Technical Report UW CSE 2000，Seattle:Department of Computer Science and Engineering.University of Washington，2000.452－463.

［5］Nicolescu D，Nath B.Ad-Hoc Positioning Systems(APS)［C］//Proc.of the 2001 IEEE Global Telecommunications Conf.Vol.5，San Antonio:IEEE Communications Society，2001.2926－2931.

［6］Shang Y，Ruml W，Zhang Y，et al.Localization from Mere Connectivity［C］//Proc.of the 4th ACM Int’l Symposium on Mobile Ad Hoc Networking ＆ Computing.Annapolis:ACM Press，2003.201－212.

［7］Shi Long，Wang Fubao，Duan Weijun.Self-Localization Mechanism and Algorithm for Wireless Sensor Networks［J］.Computer Engineering and Applications，2004，23:127－130.

［8］Oppermann I，Stoica L，Rabbachin A，et al.UWB Wireless Sensor Networks: UWEN—A Practical Example ［J］. IEEE Communications Magazine，2004，42(12):27－32.

［9］Lim H，Kung L，Hou J，et al.Zero-Configuration，Robust Indoor Localization:Theory and Experimentation［C］//Proc.of IEEE INFO-COM 2006.April 2006.30(8):15－19.

［10］Nasipuri A，Li K.A Directionality Based Location Discovery Scheme for Wireless Sensor Networks［C］//Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications.2002，105－111.

［11］Poggi C，Mazzini G.Collinearity for Sensor Network Localization［C］//Proceedings of 2003 IEEE 58th Vehicular Technology Conference.Piscataway，NJ，USA:IEEE，2004.3040－3044.

［12］LIU A，JOE B.Relationship Between Tetrahedron Shape Measures［J］.BIT Numerical Mathematics，Springer Netherlands，1994，34(2):268－287.

［13］Mitrinovic D，SPecaric J E，Volenec V.Recent Advances in Geometric Inequalities［J］.Kluwer Academic Publishers，Dordrecht，The Netherlands，1989.pp.463－555.

［14］王世香.精通MATLAB接口與編程［M］.北京:電子工業(yè)出版社，2007.

［15］于斌，孫斌，溫暖.NS2與網(wǎng)絡(luò)模擬［M］.北京:人民郵電出版社，2007.