一種基于虛擬錨節點策略改進的Bounding Box定位算法*

周 瑩

(重慶電子工程職業學院應用電子學院，重慶401331)

一種基于虛擬錨節點策略改進的Bounding Box定位算法*

周 瑩*

(重慶電子工程職業學院應用電子學院，重慶401331)

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

無線傳感器網絡;定位;Bounding Box算法;離散網絡;虛擬錨節點

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

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

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

1 Bounding Box算法描述

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

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

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

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

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

2 算法改進

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

2.1 雙半徑網絡節點模型

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

圖2 雙半徑網絡節點模型示意圖

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

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

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

2.2 虛擬錨節點策略

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

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

2.3 改進算法流程

根據上述分析本文改進算法的基本流程如圖3所示。

圖3 改進算法流程圖

3 算法仿真與性能分析

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

設節點個數為N，錨節點個數為M，則相對定位誤差為:

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

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

3.1 算法定位精度分析

圖4 定位精度比較

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

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

3.2 算法復雜度分析

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

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

圖5 定位消耗時間比較

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

圖6 兩種算法對網絡所有節點的定位誤差

由圖6可知，本文改進算法平均定位誤差為38.893%，而文獻［7］提出的算法定位誤差平均為53.036%，且本文算法在72個未知節點中可定位的節點有71個，而TB-Box算法僅有55個節點能夠實現定位。

4 結束語

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

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

［2］ 海丹，鄭志強，張輝.無線傳感器網絡環境下基于錨節點定位的節點定位誤差分析［J］.計算機應用研究，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，Faloutsos 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］ 向滿天，史浩山，李立宏，等.高精度與高覆蓋率的傳感器網絡定位算法［J］.通信學報，2008，29(11):19-23.

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

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

［10］Edgar H C.Wireless Sensor Networks:Architectures and Protocols［M］.Boca Raton，Florida:CRC Press LLC，2004.

［11］程偉，史浩山，王慶文.基于差分修正的傳感器網絡加權質心定位算法［J］.系統仿真學報，2012，24(2):389-393.

周 瑩(1983- )，女，漢族，重慶人，重慶電子工程職業學院電子系，講師，主要研究方向為電路系統設計與分析、傳感器技術，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

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

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

EEACC:6150P