周 瑩

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

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

周 瑩*

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

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

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

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

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

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

1 Bounding Box算法描述

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

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

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

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

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

2 算法改進(jìn)

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

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

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

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

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

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

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

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

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

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

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

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

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

3 算法仿真與性能分析

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

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

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

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

3.1 算法定位精度分析

圖4 定位精度比較

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

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

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

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

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

圖5 定位消耗時(shí)間比較

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

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

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

4 結(jié)束語(yǔ)

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

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

［2］ 海丹，鄭志強(qiáng)，張輝.無(wú)線傳感器網(wǎng)絡(luò)環(huán)境下基于錨節(jié)點(diǎn)定位的節(jié)點(diǎn)定位誤差分析［J］.計(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é)報(bào)，2008，29(11):19-23.

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

［9］ 向滿天，史浩山，李立宏，等.基于單元格的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法［J］.西北工業(yè)大學(xué)學(xué)報(bào)，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é)報(bào)，2012，24(2):389-393.

周 瑩(1983- )，女，漢族，重慶人，重慶電子工程職業(yè)學(xué)院電子系，講師，主要研究方向?yàn)殡娐废到y(tǒng)設(shè)計(jì)與分析、傳感器技術(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

項(xiàng)目來(lái)源:國(guó)家自然科學(xué)基金項(xiàng)目(61202490)

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

EEACC:6150P