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

(浙江工業(yè)大學計算機科學與技術學院，杭州 310023)

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

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

1 研究背景

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

1.1 三維定位問題

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

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

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

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

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

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

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

2.1 共面度的定義

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

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

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

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

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

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

其比值范圍為(0，1］，當接近0時四面體的四個頂點近似共面，為1時轉化為正四面體。

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

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

2.2 多重閥值約束策略

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

2.2.1 跳數(shù)閾值

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

2.2.2 共面度閾值

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

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

3 算法仿真與分析

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

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

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

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

圖2 仿真實驗結果對比

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

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

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

4 總結

本文從無線傳感網(wǎng)絡定位技術存在的問題入手，分析了目前距離無關定位技術的研究現(xiàn)狀，針對三維定位技術的不成熟，在距離無關算法中典型的DV-Hop算法基礎上，通過引入共面度的概念消除了三維定位中定位單元近似共面對定位結果造成的影響，并且提出了多重閾值約束策略優(yōu)化算法，提高了定位精度，很大程度上減少了不良節(jié)點出現(xiàn)的可能性，具有較好的穩(wěn)定性。在設置合理的閾值條件下，該算法對可定位節(jié)點比例的影響可以忽略，證明了在總體的性能上比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)絡技術［M］.北京理工大學出版社，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)絡模擬［M］.北京:人民郵電出版社，2007.