無線傳感網(wǎng)絡(luò)中基于共面度的三維定位算法研究與設(shè)計(jì)*

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

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

無線傳感網(wǎng)絡(luò)節(jié)點(diǎn)定位，簡單的說就是節(jié)點(diǎn)通過某種方法或者執(zhí)行某種算法獲得自己在網(wǎng)絡(luò)中的位置，通常以坐標(biāo)的形式表示，也可以用大致的位置(如房號(hào))等表示［1］。由于全球定位系統(tǒng)(GPS)技術(shù)成熟，獲得節(jié)點(diǎn)的位置可以通過給節(jié)點(diǎn)安裝GPS接收器直接獲得，但受其價(jià)格、體積、功耗、信號(hào)屏蔽等諸多因素制約，所以通過GPS獲得所有節(jié)點(diǎn)的位置存在一定的困難。目前大多數(shù)的定位技術(shù)都是利用網(wǎng)絡(luò)中少量已知位置的節(jié)點(diǎn)通過定位算法獲得其它未知節(jié)點(diǎn)的位置，已知位置的節(jié)點(diǎn)稱為參考點(diǎn)，可以人為放置或者通過GPS獲得。未知節(jié)點(diǎn)的位置可以是相對(duì)于參考點(diǎn)建立的坐標(biāo)系，也可以是一個(gè)絕對(duì)位置(如參考點(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ò)對(duì)節(jié)點(diǎn)的能耗、成本、體積等要求，所以定位算法必須在滿足上述要求的前提下才有實(shí)際的使用價(jià)值。目前，科研工作者已經(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ù)對(duì)未知節(jié)點(diǎn)的位置進(jìn)行估計(jì)。由于測距技術(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)境下的定位問題相比于二維平面顯然會(huì)有一定區(qū)別，其主要難點(diǎn)如下:

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

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

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

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

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

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

2.1 共面度的定義

共面度即表示三維空間中四個(gè)點(diǎn)的共面程度，文獻(xiàn)［12］中提出了四面體形狀測量被用于評(píng)價(jià)有限元網(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］中給出了計(jì)算四面內(nèi)切球和外接球半徑的公式:

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

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

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

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

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

2.2 多重閥值約束策略

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

2.2.1 跳數(shù)閾值

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

2.2.2 共面度閾值

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

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

3 算法仿真與分析

在MATLAB6.5下對(duì)本文提出的算法進(jìn)行了仿真，并且比較對(duì)象是在三維空間中利用四邊定位法的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è)置在一個(gè)100 m×100 m×100 m的三維區(qū)域中，參考點(diǎn)和未知節(jié)點(diǎn)共100個(gè)，且坐標(biāo)是隨機(jī)產(chǎn)生的。在測試共面度閾值和跳數(shù)閾值變化對(duì)定位性能影響的實(shí)驗(yàn)中，得出的結(jié)論是共面度閾值和跳數(shù)閾值的設(shè)置對(duì)節(jié)點(diǎn)的LER和BNP有較為顯著的改善。但是在共面度閾值超過0.4以后不管對(duì)LER還是BNP的改善都趨于平穩(wěn)，而對(duì)LNP的降低卻比較明顯，所以將共面度閾值設(shè)置在0.4～0.6之間將既能滿足較好的定位精度也能實(shí)現(xiàn)較好的定位覆蓋率，在對(duì)原算法的比較實(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)比例相同時(shí)，DCP3D的誤差相比DV-Hop算法有10%以上的降低，并且當(dāng)網(wǎng)絡(luò)密度變化時(shí)，前者甚至在參考點(diǎn)比例為10%的情況下超過了后者在參考點(diǎn)比例20%時(shí)的定位精度，由此可見DCP3D算法相比DVHop算法在定位精度上有明顯的改善。

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

在可定位節(jié)點(diǎn)比例上，圖2(b)，DCP3D算法相比DV-Hop算法在網(wǎng)絡(luò)稀疏的時(shí)候降低較為明顯，但是當(dāng)網(wǎng)絡(luò)密度超過10的時(shí)候，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的時(shí)候，不良節(jié)點(diǎn)比例已經(jīng)減少到10%以下，所以DCP3D算法在改善不良節(jié)點(diǎn)方面有卓越的表現(xiàn)。而DV-Hop算法在網(wǎng)絡(luò)密度和參考點(diǎn)比例低的時(shí)候，不良節(jié)點(diǎn)比例甚至超過了50%。由此可見，DCP3D算法針對(duì)節(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)的部署密度不會(huì)太低，所以改進(jìn)算法在實(shí)際應(yīng)用中的定位覆蓋率基本能夠達(dá)到要求。綜合各項(xiàng)性能指標(biāo)，DCP3D算法比DV-Hop算法更適用于無線傳感網(wǎng)絡(luò)三維定位。

4 總結(jié)

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