周 瑩

(重慶電子工程職業(yè)學(xué)院應(yīng)用電子學(xué)院，重慶401331)

一種基于虛擬錨節(jié)點策略改進(jìn)的Bounding Box定位算法*

周 瑩*

(重慶電子工程職業(yè)學(xué)院應(yīng)用電子學(xué)院，重慶401331)

針對Bounding Box算法定位誤差大、覆蓋率低的缺點，提出了一種采用虛擬錨節(jié)點策略的改進(jìn)定位算法。首先未知節(jié)點利用其通信范圍內(nèi)的錨節(jié)點進(jìn)行定位;其次，已定位的節(jié)點根據(jù)升級策略有選擇性的升級為虛擬錨節(jié)點;最后，無法定位的節(jié)點利用虛擬錨節(jié)點實現(xiàn)定位。另外，在離散網(wǎng)絡(luò)模型的基礎(chǔ)上，通過建立雙半徑網(wǎng)絡(luò)節(jié)點模型從而進(jìn)一步約束了未知節(jié)點的位置。理論分析及仿真結(jié)果均表明，該算法在顯著提高定位覆蓋率的同時，有效地提高了定位精度。

無線傳感器網(wǎng)絡(luò);定位;Bounding Box算法;離散網(wǎng)絡(luò);虛擬錨節(jié)點

無線傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Network)的大多數(shù)應(yīng)用領(lǐng)域中，位置信息對其監(jiān)測功能的實現(xiàn)至關(guān)重要，沒有位置信息的監(jiān)測信息往往毫無意義［1］。定位的目標(biāo)就是根據(jù)網(wǎng)絡(luò)中部分位置已知的節(jié)點(錨節(jié)點)來估計其余節(jié)點(未知節(jié)點)的位置［2-3］。近年來所開發(fā)出來的各種無線傳感器網(wǎng)絡(luò)定位算法與機(jī)制［4-6］，采用的網(wǎng)絡(luò)場景通常分為連續(xù)和離散兩種模型。其中離散模型方法便于規(guī)范建模及統(tǒng)計分析，能夠有效地降低算法復(fù)雜度［7］。

文獻(xiàn)［4］的Bounding Box算法就是在離散網(wǎng)絡(luò)模型中對錨節(jié)點通信距離內(nèi)的未知節(jié)點進(jìn)行定位，能夠逼近節(jié)點的真實位置。但缺點是定位精度及算法覆蓋率不高，對錨節(jié)點的密度及分布有很嚴(yán)格的要求。文獻(xiàn)［7-9］針對上述問題分別做出了相應(yīng)的改進(jìn):文獻(xiàn)［7］提出了一種基于三跳通信環(huán)帶的方法提高了算法的定位精度;文獻(xiàn)［8］將多邊測距定位方法引入到Bounding Box算法中解決了該算法未知節(jié)點定位過分依賴錨節(jié)點的問題;文獻(xiàn)［9］利用錨節(jié)點與未知節(jié)點之間的關(guān)系通過約束待測節(jié)點的位置提高算法的覆蓋率。上述算法僅對Bounding Box算法的某一缺點進(jìn)行了改進(jìn)，并沒有對其定位精度和覆蓋率進(jìn)行整體改善。

針對這一問題，本文在文獻(xiàn)［7］的基礎(chǔ)上，提出了一種采用虛擬錨節(jié)點的Bounding Box改進(jìn)算法，通過將已定位的節(jié)點根據(jù)升級策略有選擇性的升級為虛擬錨節(jié)點提高了該算法的覆蓋率;另一方面提出了雙半徑網(wǎng)絡(luò)節(jié)點模型對未知進(jìn)行約束優(yōu)化從而提高了該算法的定位精度。

1 Bounding Box算法描述

Bounding-Box［4］算法由Simic SN等人提出。該算法的核心思想是:在二維區(qū)域內(nèi)，未知節(jié)點的通信范圍內(nèi)會有一些錨節(jié)點，通過這些錨節(jié)點的位置和傳感器節(jié)點的通信半徑，就能獲得未知節(jié)點所在的一個二維方形區(qū)域范圍。具體過程如下述。

假設(shè)在一個正方形區(qū)域Q=［-q/2，q/2］×［-q/2，q/2］中隨機(jī)分布了N個節(jié)點，其中有M個錨節(jié)點。首先錨節(jié)點廣播其位置信息至整個網(wǎng)絡(luò)，傳播半徑為R。考慮到干擾、偏移等不穩(wěn)定因素，假定所有節(jié)點的位置都是一個矩形范圍，即

如果將圓形通信范圍近似為其內(nèi)接正方形的約束盒(Bounding Box)［4］，將對該節(jié)點位置的2次約束簡化為線性約束，并考慮更多錨節(jié)點約束，就能縮小覆蓋區(qū)域的范圍，進(jìn)而降低節(jié)點位置區(qū)域的不確定性。為了便于進(jìn)一步的研究，Bounding Box算法將以上模型進(jìn)行離散化，如圖1所示。

圖1 Bounding Box算法定位原理(p=2)

在圖1中，實心點S1、S2、S3為錨節(jié)點，空心點S為未知節(jié)點，假定n為偶數(shù)，Q分解成(n+1)2個正方形單元格，S=［-n/2，n/2］×［-n/2，n/2］。節(jié)點所處單元格的坐標(biāo)為(i，j)，節(jié)點通信范圍是正方形

2 算法改進(jìn)

由上述對Bounding Box算法原理的分析可知，在進(jìn)行方盒重疊計算時，若未知節(jié)點接收到的錨節(jié)點信息越多，則用來重疊的方形區(qū)域就越多，因而誤差也就越小，同時，未知節(jié)點所接收到的錨節(jié)點信息數(shù)量的多少對算法的覆蓋率也有直接影響。但是，由于無線傳感器網(wǎng)絡(luò)受到成本的限制，過多的增加錨節(jié)點將大大增加網(wǎng)絡(luò)的開銷，是不切實際的［10］。為了解決這一問題，本文將具體作出以下改進(jìn)。

2.1 雙半徑網(wǎng)絡(luò)節(jié)點模型

在Bounding Box算法設(shè)定的離散網(wǎng)絡(luò)模型的基礎(chǔ)上，考慮到算法能量消耗的問題，對錨節(jié)點引入兩種通信半徑，分別為p和p/2，圖2給出了雙半徑網(wǎng)絡(luò)節(jié)點模型的示意圖。

圖2 雙半徑網(wǎng)絡(luò)節(jié)點模型示意圖

如圖2所示，S1、S2為錨節(jié)點，S為未知節(jié)點，其中錨節(jié)點的半徑為p和p/2，則正方形的邊長分別為2p+1和p+1，即錨節(jié)點的通信范圍為:

由圖2左圖可知，當(dāng)錨節(jié)點半徑取p時，未知節(jié)點接收到的兩個錨節(jié)點所重疊的區(qū)域為陰影區(qū)域A;而當(dāng)錨節(jié)點半徑取p/2時，未知節(jié)點接收到的兩個錨節(jié)點所重疊的區(qū)域為白色區(qū)域B，顯然，將區(qū)域B的質(zhì)心作為未知節(jié)點S的估計坐標(biāo)比將區(qū)域A的質(zhì)心作為估計坐標(biāo)所產(chǎn)生的誤差小的多，從而大大提高了算法的定位精度。

由于這一模型在錨節(jié)點向網(wǎng)絡(luò)廣播自身位置信息時首先采用半徑p，而在未知節(jié)點計算自身位置時采用p/2的通信半徑對方形區(qū)域進(jìn)行劃分并完成定位。但是可以發(fā)現(xiàn)，當(dāng)錨節(jié)點半徑取為p/2時，未知節(jié)點S有可能出現(xiàn)在錨節(jié)點S1、S2的通信范圍外，而無法定位，此時則采用通信半徑p實現(xiàn)定位，因而并未影響算法的覆蓋率。

2.2 虛擬錨節(jié)點策略

根據(jù)上述的分析可知，當(dāng)采用雙半徑網(wǎng)絡(luò)節(jié)點模型進(jìn)行定位時，雖然能夠較大程度的提高算法的定位精度，但未知節(jié)點需要依賴大量錨節(jié)點進(jìn)行定位的問題仍未解決。為此，本文在上述基礎(chǔ)上，提出了一種虛擬錨節(jié)點策略，以期提高算法的覆蓋率。該策略的基本思想如下述。

首先根據(jù)雙半徑網(wǎng)絡(luò)節(jié)點模型的思想，針對那些能夠與錨節(jié)點建立連通的未知節(jié)點，Bounding Box算法的定位過程，完成自身位置的估計，并自動升級為虛擬錨節(jié)點;而后，對于未能和錨節(jié)點建立連通的未知節(jié)點，則利用升級后的錨節(jié)點進(jìn)行定位。采用該策略，一方面能夠在錨節(jié)點數(shù)量有限的條件下明顯地提高算法的定位率;另一方面，由于在雙半徑網(wǎng)絡(luò)節(jié)點模型的基礎(chǔ)上實現(xiàn)的定位，能夠保證未知節(jié)點較高的定位精度，因此，在升級為虛擬錨節(jié)點后并被其他未知節(jié)點用來定位時所產(chǎn)生的誤差較小。另外，該策略中，只有那些沒有鄰錨節(jié)點的未知節(jié)點才虛擬錨節(jié)點進(jìn)行定位，而不是所有節(jié)點都利用這一策略，因而可以有效的避免由于累積誤差而導(dǎo)致誤差增大的問題。

2.3 改進(jìn)算法流程

根據(jù)上述分析本文改進(jìn)算法的基本流程如圖3所示。

圖3 改進(jìn)算法流程圖

3 算法仿真與性能分析

為了驗證本文改進(jìn)算法的性能，本文使用MATLAB仿真工具對算法進(jìn)行仿真實驗。仿真所用網(wǎng)絡(luò)區(qū)域為各向同性的邊長為100 m的方形監(jiān)測區(qū)域，其中令p=2。測試在不同的節(jié)點個數(shù)及錨節(jié)點個數(shù)下本文改進(jìn)算法(記為VB-Box)與文獻(xiàn)［7］提出的算法(記為TB-Box)和傳統(tǒng)算法(記為BBox)在定位精度及覆蓋率方面的性能。

設(shè)節(jié)點個數(shù)為N，錨節(jié)點個數(shù)為M，則相對定位誤差為:

其中(xest，yest)為未知節(jié)點的估計坐標(biāo)，(xtrue，ytrue)為未知節(jié)點的實際坐標(biāo)，p為節(jié)點的通信半徑。網(wǎng)絡(luò)中所有未知節(jié)點的歸一化的平均相對定位誤差［11］為:

其中k為仿真次數(shù)，在未加說明的情況下k=500次，nc為可定位的節(jié)點個數(shù)。歸一化的平均定位率通過下式計算:

3.1 算法定位精度分析

圖4 定位精度比較

定位精度是衡量算法準(zhǔn)確性的關(guān)鍵指標(biāo)。為了分析比較3種算法的定位精度，仿真了在兩種不同條件下定位精度的變化情況，圖4分別為3種算法的定位精度隨節(jié)點總數(shù)和錨節(jié)點個數(shù)變化的趨勢圖，其中，在圖4(a)中，設(shè)錨節(jié)點比例為10%，可以看出，隨著節(jié)點總數(shù)的增加，3種算法的定位精度均逐漸減小，文獻(xiàn)［7］提出的算法定位精度小于傳統(tǒng)算法，但本文改進(jìn)算法明顯由于傳統(tǒng)算法和TB-Box算法，且分別提高了9.64%和4.6%。

在圖4(b)中，設(shè)節(jié)點總數(shù)N=130，可以看出，在隨錨節(jié)點個數(shù)增加時，3種算法的定位精度均逐漸減小并趨于穩(wěn)定，說明了在錨節(jié)點增加到一定程度時，其對定位精度的影響逐漸減小。相比于BBox算法和TB-Box算法，本文改進(jìn)算法定位精度在該條件下平均提高了13.41%和7.4%。

3.2 算法復(fù)雜度分析

在無線傳感器網(wǎng)絡(luò)中，由于本身特點的限制，要求算法在計算過程中盡可能小的消耗能量以確保網(wǎng)絡(luò)節(jié)點的平均壽命。在本文中，用算法每次定位的平均時間等效算法的復(fù)雜度，來衡量比較3種算法的能量消耗情況。圖5給出了3種算法在不同條件下定位時間的變化曲線。其中，圖5(a)為錨節(jié)點比例為10%時3種算法定位時間隨節(jié)點總數(shù)的變化曲線，可以看出，隨著節(jié)點總數(shù)的增加，3種算法的定位時間均逐漸增多，傳統(tǒng)算法的定位時間最少，而文獻(xiàn)［7］所提出的算法每次定位用的時間較多，而本文改進(jìn)算法則適中，相比于B-Box算法，本文算法每次定位時間平均增加了0.018 1 s，而相比于TBBox算法，本文算法則減少了0.013 3 s。

圖5(b)給出了在節(jié)點總數(shù)為130時3種算法定位時間隨錨節(jié)點個數(shù)的變化曲線，可以看出，隨著錨節(jié)點數(shù)的增多，3種算法的定位時間基本保持不變，其中本文算法較傳統(tǒng)算法定位時間平均增加了0.017 1 s，而較TB-Box算法則降低了0.022 6 s。

圖5 定位消耗時間比較

通過上述仿真分析可知，本文改進(jìn)算法在節(jié)點個數(shù)較少且錨節(jié)點數(shù)較為稀疏時覆蓋率明顯優(yōu)于傳統(tǒng)算法和文獻(xiàn)［7］提出的算法，且算法的能量消耗適中，同時能夠保證良好的定位精度，圖6給出了在節(jié)點個數(shù)N=80，錨節(jié)點個數(shù)為7，p=2時本文改進(jìn)算法與TB-Box算法的每次定位誤差分布圖。

圖6 兩種算法對網(wǎng)絡(luò)所有節(jié)點的定位誤差

由圖6可知，本文改進(jìn)算法平均定位誤差為38.893%，而文獻(xiàn)［7］提出的算法定位誤差平均為53.036%，且本文算法在72個未知節(jié)點中可定位的節(jié)點有71個，而TB-Box算法僅有55個節(jié)點能夠?qū)崿F(xiàn)定位。

4 結(jié)束語

無線傳感網(wǎng)絡(luò)節(jié)點定位算法的覆蓋率和定位精度是衡量定位算法有效性與實用性的重要指標(biāo)。本文針對Bounding Box算法覆蓋率及定位精度較低的問題，在詳細(xì)分析離散網(wǎng)絡(luò)模型的基礎(chǔ)上，通過建立雙半徑網(wǎng)絡(luò)節(jié)點模型并將虛擬錨節(jié)點的思想引入到算法的定位過程中，在大大提高算法覆蓋率的同時減小了定位誤差。理論分析和仿真結(jié)果表明，在錨節(jié)點個數(shù)較少且網(wǎng)絡(luò)平均連通度較低時，相比于傳統(tǒng)算法及文獻(xiàn)［7］提出的改進(jìn)算法，本文改進(jìn)算法在略微增加算法復(fù)雜度的同時仍能保持較高的定位率;另外在確保網(wǎng)絡(luò)連通度的基礎(chǔ)上，本文算法有效的提高了定位精度，大大提升了算法的實用性。

［1］ 吳曉平，談士力.基于半定規(guī)則的無線傳感器網(wǎng)絡(luò)定位算法性能分析［J］.傳感技術(shù)學(xué)報，2012，25(12):1731-1736.

［2］ 海丹，鄭志強(qiáng)，張輝.無線傳感器網(wǎng)絡(luò)環(huán)境下基于錨節(jié)點定位的節(jié)點定位誤差分析［J］.計算機(jī)應(yīng)用研究，2011，28(4):1486-1489.

［3］ Stupp G，Sidi M.The Expected Uncertainty of Range Free Localization Protocols in Sensor Networks［C］//Algorithmic Aspects of Wireless Sensor Networks:First International Workshop，Algosensors.2004.85-97.

［4］ Simic S N，Sastry S.Distributed Localization in Wireless Ad Hoc Networks［R］.Technical Report UCB/ERL M02/26，UC Berkeley，2002.

［5］ Whitehouse C D.The Design of Calamari:an Ad-Hoc Localization System for Sensor Networks［D］.University of California at Berkeley，2002:1-73.

［6］ Leskovec J，Chakrabarti D，F(xiàn)aloutsos C.Information Survival Threshold in Sensor and p2p Networks［C］//Proceedings of 26th IEEE International Conference on Computer Communications.Anchorage，Alaska，USA，2007.1316-1324.

［7］ 向滿天，史浩山，李立宏，等.高精度與高覆蓋率的傳感器網(wǎng)絡(luò)定位算法［J］.通信學(xué)報，2008，29(11):19-23.

［8］ 許磊，石為人.一種無線傳感器網(wǎng)絡(luò)分布求精節(jié)點定位算法［J］.儀器儀表學(xué)報，2008，29(2):314-319.

［9］ 向滿天，史浩山，李立宏，等.基于單元格的無線傳感器網(wǎng)絡(luò)節(jié)點定位算法［J］.西北工業(yè)大學(xué)學(xué)報，2008，26(5):607-611.

［10］Edgar H C.Wireless Sensor Networks:Architectures and Protocols［M］.Boca Raton，F(xiàn)lorida:CRC Press LLC，2004.

［11］程偉，史浩山，王慶文.基于差分修正的傳感器網(wǎng)絡(luò)加權(quán)質(zhì)心定位算法［J］.系統(tǒng)仿真學(xué)報，2012，24(2):389-393.

周 瑩(1983- )，女，漢族，重慶人，重慶電子工程職業(yè)學(xué)院電子系，講師，主要研究方向為電路系統(tǒng)設(shè)計與分析、傳感器技術(shù)，zhouying1983cq@163.com。

An Improved Bounding Box Localization Algorithm Based on the Virtual Anchor Nodes*

ZHOU Ying*
(Department of Electronics，Chongqing College of Electronic Engineering，Chongqing 401331，China)

To overcome the disadvantages of localization accuracy and low coverage rate in current Bounding Box algorithm，an improved algorithm using the virtual anchor nodes was proposed.Firstly，the anchor nodes within the communication range of unknown nodes were used to calculate the coordinates of the unknown nodes.Secondly，the located unknown nodes were upgraded as the virtual anchor nodes according to the promotion strategy selectively. Finally，the nodes which were unable to locate themselves used the virtual anchor nodes to get their location.On the other hands，the network node model of double radius based on the discrete network model was introduced to restrict the location of the unknown nodes.The result of simulation and analysis shows that the proposed algorithm can improve the localization coverage rate as well as the estimation accuracy significantly.

wireless sensor network;localization;Bounding Box algorithm;discrete network;virtual anchor nodes

10.3969/j.issn.1005－9490.2014.02.035

TP393

A

1005－9490(2014)02－0332－05

項目來源:國家自然科學(xué)基金項目(61202490)

2013-05-27修改日期:2013-06-15

EEACC:6150P