基于虛擬節(jié)點的BP無線傳感器網(wǎng)絡(luò)定位算法

孫 凱，劉潤杰，申金媛

(鄭州大學(xué)信息工程學(xué)院，河南鄭州450001)

0 引言

無線傳感器網(wǎng)絡(luò)節(jié)點的位置是網(wǎng)絡(luò)中必要的基礎(chǔ)信息，節(jié)點的準確定位是無線傳感器網(wǎng)絡(luò)關(guān)鍵問題之一。目前，根據(jù)網(wǎng)絡(luò)中是否需要測量節(jié)點之間的真實距離，定位算法可分為基于測距的方法(range-based)和距離無關(guān)的方法(range-free)［1］。前者測量利用節(jié)點之間的距離或者角度信息實現(xiàn)節(jié)點自身定位，典型的算法有TDoA，RSSI，ToA，AoA等?；跍y距的定位方法需要額外硬件的支持，并且會產(chǎn)生大量計算和通信開銷;距離無關(guān)的定位方法僅依靠網(wǎng)絡(luò)的連通度等信息實現(xiàn)節(jié)點自身定位，無需額外的硬件，但是定位精度卻不如前者，因此，如何提高距離無關(guān)定位方法的定位精度得到了學(xué)者們廣泛的研究。

在Range-Free方法中，比較典型的2種算法是由 Bulusu N提出的Centroid algorithm［2］和由Nicelescu D利用矢量路由和GPS定位原理提出的 DV-Hop［3］算法。而在國內(nèi)，李兆斌等人也提出增強的質(zhì)心定位算法(ACLA)［4］;于寧等人基于限制跳數(shù)思想提出LDV-Hop算法［5］。

現(xiàn)有定位算法都表明錨節(jié)點的比例越高，定位的精度越高［6，7］，但錨節(jié)點比例的增加會增加無線傳感器網(wǎng)絡(luò)的成本。本文首先將BP神經(jīng)網(wǎng)絡(luò)用于無線傳感器網(wǎng)絡(luò)的節(jié)點定位，為了進一步提高節(jié)點的定位精度，提出了基于次錨節(jié)點的BP定位估計方法。次錨節(jié)點的引入相當于虛擬地增加了錨節(jié)點的比例，這樣就減少了應(yīng)用成本。

仿真結(jié)果表明:BP神經(jīng)網(wǎng)絡(luò)具有較小的定位誤差，并且，次錨節(jié)點的引入也可進一步提高定位精度。

1 基于BP的定位算法

1.1 BP 結(jié)構(gòu)模型

本文首先采用兩層BP神經(jīng)網(wǎng)絡(luò)對未知節(jié)點進行定位。為了簡化定位估算系統(tǒng)的結(jié)構(gòu)和成本，采用距離無關(guān)的集中式定位算法。采用節(jié)點間的最小跳數(shù)信息，并發(fā)送給網(wǎng)絡(luò)中的中心節(jié)點(如一臺服務(wù)器)，由它運行定位算法，這樣可以保證運行算法的計算量和存儲量以及能耗。其中，節(jié)點間的最小跳數(shù)通過以下方法確定:錨節(jié)點向鄰居節(jié)點廣播自身位置信息的分組，其中包括跳數(shù)(初始化為0)和自身ID信息。接收節(jié)點記錄到錨節(jié)點的跳數(shù)。若收到來自同一錨節(jié)點的分組，且其中的跳數(shù)比原來收到的要大，則忽略該分組。然后將跳數(shù)加1，繼續(xù)向鄰居節(jié)點廣播該分組，這樣網(wǎng)絡(luò)中的節(jié)點能夠記錄下到每個錨節(jié)點的最小跳數(shù)。

假設(shè)共有N個隨機部署的節(jié)點，用n=1，2，…，N來表示，其中前M個為錨節(jié)點，其余為未知節(jié)點。Bi=(xi，yi)表示第i個節(jié)點的位置。令Si=［si1，si2，…sim…siM］表示各錨節(jié)點之間的最小跳數(shù)，其中，sim表示第i個錨節(jié)點到第m個錨節(jié)點的最小跳數(shù)，i=1，…，M，m=1，…，M，當 i=m時，sim=0。令 Sj=［sj1，sj2，…sjm…sjM］表示各未知節(jié)點到錨節(jié)點的最小跳數(shù)，其中sjm表示第j個未知節(jié)點到第m個錨節(jié)點的最小跳數(shù)，j=(M+1，M+2…N)，m=1…M。輸入層神經(jīng)元的個數(shù)M由錨節(jié)點數(shù)目決定，隱含層神經(jīng)元個數(shù)通過經(jīng)驗選取，輸出層的2個神經(jīng)元的對應(yīng)于節(jié)點位置的坐標(x，y)。

1.2 利用BP估算位置

基于BP的定位算法分為訓(xùn)練和估計2個階段。在訓(xùn)練階段，首先利用錨節(jié)點對網(wǎng)絡(luò)進行訓(xùn)練，訓(xùn)練的樣本選擇網(wǎng)絡(luò)中所有的錨節(jié)點，訓(xùn)練的輸入是錨節(jié)點之間的最小跳數(shù)，即 Si=［si1，si2，…sim…siM］，訓(xùn)練的輸出是對應(yīng)錨節(jié)點的位置 Bi=(xi，yi)，i=1…M，m=1…M。估計階段的輸入是每個未知節(jié)點到各錨節(jié)點之間的跳數(shù)，即Sj=［sj1，sj2，…sjm…sjM］，輸出是對應(yīng)的未知節(jié)點的位置，Bj=(xj，yj)，j=(M+1，M+2…N)，m=1…M。

2 基于虛擬節(jié)點的定位算法

2.1 次錨節(jié)點

研究表明:錨節(jié)點比例的增加可有效地提高未知節(jié)點的定位精度，但是增加錨節(jié)點比例同時也將增加無線傳感器網(wǎng)絡(luò)的應(yīng)用成本。為了節(jié)約成本并有效提高網(wǎng)絡(luò)的定位精度，本文提出了次錨節(jié)點的概念，將部分未知節(jié)點轉(zhuǎn)化為錨節(jié)點，從而進一步對未知節(jié)點進行定位。

2.2 次錨節(jié)點的選擇

引入次錨節(jié)點帶來的一個困難是如何從未知節(jié)點中選取合適的次錨節(jié)點，理論上應(yīng)該先對未知節(jié)點的位置進行估計，然后，選取定位比較準確的未知節(jié)點作為次錨節(jié)點，但是在實際中并不知道未知節(jié)點的位置，無法判斷未知節(jié)點的估計位置和實際位置的誤差。為了解決這個問題，引入了虛擬節(jié)點，并借助于虛擬節(jié)點在未知節(jié)點中選擇定位精度較高的未知節(jié)點作為次錨節(jié)點。

2.2.1 虛擬節(jié)點

虛擬節(jié)點即在現(xiàn)實中并不存在的點，它們不具備節(jié)點間通信和信息轉(zhuǎn)發(fā)的能力，但是可以假設(shè)在網(wǎng)絡(luò)中存在著隨機分布的這樣的一些節(jié)點，并且它們的位置是假設(shè)為已知的。假設(shè)網(wǎng)絡(luò)中有P個虛擬節(jié)點，位置是Ck=(xk，yk)，令Sk=［sk1，sk2，…skm…skM］表示虛擬節(jié)點到各錨節(jié)點的最小跳數(shù)，其中，skm表示第k個虛擬節(jié)點到第m個錨節(jié)點的最小跳數(shù)，k=1，2，…P，m=1…M。

2.2.2 跳數(shù)的轉(zhuǎn)化

虛擬節(jié)點的定位首先需要它們到各錨節(jié)點的最小跳數(shù)，由于虛擬節(jié)點不具備節(jié)點間通信和信息轉(zhuǎn)發(fā)的能力，因此，不能直接找虛擬節(jié)點和錨節(jié)點之間的最小跳數(shù)，為此可將虛擬節(jié)點和錨節(jié)點的距離轉(zhuǎn)化為跳數(shù)。本文首先計算虛擬節(jié)點和錨節(jié)點的距離，然后，將此距離和節(jié)點的無線射程作比較。如圖1，節(jié)點A為錨節(jié)點，節(jié)點B和C為虛擬節(jié)點，R是A的無線射程。虛擬節(jié)點C和錨節(jié)點A的距離DAC＜R，首先可以確定虛擬節(jié)點C和錨節(jié)點A之間是一跳;而虛擬節(jié)點B和錨節(jié)點A的距離DAB＞R，因此，它們之間的跳數(shù)大于一跳。在多跳的情況下，A和B的跳數(shù)不能直接根據(jù)它們的距離確定，而是綜合考慮B和鄰居節(jié)點的跳數(shù)信息而最終確定。

圖1 跳數(shù)轉(zhuǎn)化圖Fig 1 Transformation diagram of Hop number

2.2.3 虛擬節(jié)點的選擇

當知道了虛擬節(jié)點和錨節(jié)點的最小跳數(shù)后，可以用訓(xùn)練好的BP神經(jīng)網(wǎng)絡(luò)估計每個虛擬節(jié)點的位置，此時BP網(wǎng)絡(luò)的輸入是Sk=［sk1，sk2，…skm…skM］，網(wǎng)絡(luò)的輸出是對應(yīng)虛擬節(jié)點的估計位置 C'k=(xk，yk)，k=1，2，…P，m=1…M。

由于虛擬節(jié)點的位置是假設(shè)為已知的，這時就可以將虛擬節(jié)點的估計位置和精確位置比較，即C'k和Ck，從中選出Q個誤差小的虛擬節(jié)點，它們到各錨節(jié)點的最小跳數(shù)設(shè)為Sq=［sq1，sq2，…sqm…sqM］，q==1，2，…Q，m=1…M。為了進一步確定次錨節(jié)點，假設(shè)到所有錨節(jié)點的最小跳數(shù)都相同的節(jié)點的位置是接近的。基于這種思想，尋找Q個誤差小的虛擬節(jié)點到各錨節(jié)點的最小跳數(shù)Sq=［sq1，sq2，…sqm…sqM］和具有到各錨節(jié)點的最小跳數(shù) Sj=［sj1，sj2，…sjm…sjM］相同的未知節(jié)點，并將這些未知節(jié)點確定為次錨節(jié)點。

如圖2所示，假設(shè)網(wǎng)絡(luò)中有4個錨節(jié)點(節(jié)點1～4，實心圓)，9個未知節(jié)點(節(jié)點5-13，空心圓)，8個虛擬節(jié)點(節(jié)點14-21，三角)。假設(shè)經(jīng)過錨節(jié)點和未知節(jié)點的信息轉(zhuǎn)發(fā)以及虛擬節(jié)點將距離轉(zhuǎn)換為跳數(shù)后，可以得到所有節(jié)點之間的跳數(shù)。用BP神經(jīng)網(wǎng)絡(luò)首先預(yù)測8個虛擬節(jié)點的估計位置，然后和它們的準確位置相比較。假設(shè)找出誤差比較小的虛擬節(jié)點為16，17，19，21，然后尋找有沒有和虛擬節(jié)點16，17，19，21到各錨節(jié)點(1～4)跳數(shù)相同的未知節(jié)點。假設(shè)未知節(jié)點8和13分別和虛擬節(jié)點17和21到各錨節(jié)點的跳數(shù)相同，最后，據(jù)此確定未知節(jié)點8和13為次錨節(jié)點。

圖2 尋找次錨節(jié)點圖示Fig 2 Icon of searching for sub-anchor node

2.3 次錨節(jié)點的應(yīng)用

找到次錨節(jié)點后，重新構(gòu)建BP神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)，將錨節(jié)點和次錨節(jié)點共同作為網(wǎng)絡(luò)的錨節(jié)點，重新訓(xùn)練網(wǎng)絡(luò)。新BP網(wǎng)絡(luò)仍然采用兩層網(wǎng)絡(luò)結(jié)構(gòu)，訓(xùn)練完畢后，對所有的未知節(jié)點重新定位。

3 仿真與分析

為了檢驗所提方法的性能，對質(zhì)心(centroid)算法，DVHop算法，BP的定位算法，隨機選擇未知節(jié)點作為次錨節(jié)點的算法(RN-BP)以及利用虛擬節(jié)點選擇次錨節(jié)點的方法(VN-BP)分別在Matlab的平臺上進行了一系列仿真。仿真中所有節(jié)點都隨機分布在100 m×100 m的區(qū)域內(nèi)。由于BP神經(jīng)網(wǎng)絡(luò)的預(yù)測結(jié)果受到初始權(quán)重的影響，為了仿真結(jié)果能客觀地反映所提方法的優(yōu)劣性，每組不同條件均仿真運行100次，然后，取定位誤差的平均值進行分析比較。

為更好地分析所提算法的性能，本文在3種不同的情況下仿真分析:1)無線射程不同的仿真;2)錨節(jié)點比例不同的仿真;3)總節(jié)點數(shù)不同的仿真。

3.1 定位誤差和無線射程

對無線射程不同的情況進行仿真中共有200個節(jié)點，其中10個錨節(jié)點，各種算法定位誤差與無線射程關(guān)系如圖3所示。在相同的無線射程下，BP算法的定位誤差比Centroid算法小;在無線射程小于40 m時，DV-Hop算法的定位誤差比BP算法小，但是無線射程大于等于40 m時，DV-Hop算法的定位誤差卻比BP算法的高。引入次錨節(jié)點后，VN-BP算法的定位誤差比BP算法降低了平均7.37%，這說明次錨節(jié)點在不同的無線射程下對降低定位誤差是有效的;同時VN-BP的定位誤差也比RN-BP高降低了7.42%，這說明在各種不同的無線射程下，虛擬節(jié)點的引入對降低定位誤差均是有效的。

3.2 定位誤差和錨節(jié)點比例

對錨節(jié)點比例不同的情況進行仿真中共有200個節(jié)點，無線射程設(shè)為40 m，結(jié)果如圖4所示。仿真中5種算法的定位誤差都隨著錨節(jié)的比例增加呈下降趨勢。在相同的條件下，BP算法的定位誤差比DV-Hop算法和Centroid的誤差降低了平均14.806%和10.35%，尤其是當錨節(jié)點比例大于15%時，BP算法的定位誤差迅速下降。引入次錨節(jié)點后，VN-BP算法的定位精度又優(yōu)于BP算法，定位誤差降低了平均3.656%，這表明在不同的錨節(jié)點比例下次錨節(jié)點對降低定位誤差的有效性;同時VN-BP的定位誤差比RN-BP算法降低了平均2.346%，這也表明在不同的錨節(jié)點比例下虛擬節(jié)點的引入對降低定位誤差均是有效的。

圖3 無線射程和定位誤差Fig 3 Wireless range and positioning error

圖4 錨節(jié)點比例和定位誤差Fig 4 Anchor node proportion and positioning error

3.3 定位誤差和節(jié)點數(shù)

對總節(jié)點數(shù)不同的情況進行仿真中的錨節(jié)點比例為10%，無線射程設(shè)為40 m，結(jié)果如圖5所示。隨著節(jié)點數(shù)目的增加，5種算法的定位誤差大體上呈遞減趨勢。在相同的條件下，BP算法明顯優(yōu)于Centroid算法，定位誤差降低了平均13.5%;在節(jié)點數(shù)為100時，BP算法的定位誤差比DVHop算法大，但在當節(jié)點數(shù)目大于200后，定位誤差迅速降低，并小于DV-Hop算法的誤差。當引入次錨節(jié)點后，VN-BP算法的定位誤差比BP降低了5.866%，這說明次錨節(jié)點在不同的節(jié)點數(shù)下對定位精度的提高是有效的;同時VN-BP的定位誤差比RN-BP算法降低了4.036%，這說明虛擬節(jié)點的引入在不同的節(jié)點數(shù)下對定位精度的提高也是有效的。

圖5 節(jié)點數(shù)目和定位誤差Fig 5 Number of nodes and positioning error

4 結(jié)論

針對網(wǎng)絡(luò)中的錨節(jié)點比例因素，提出了應(yīng)用次錨節(jié)點以提高錨節(jié)點比例，降低定位誤差的算法。在定位誤差的比較中，無論在無線射程，錨節(jié)點比例和總節(jié)點個數(shù)變化時，引入次錨節(jié)點算法的都要優(yōu)于引進次錨節(jié)點前的算法和隨機從未知節(jié)點里選取次錨節(jié)點的算法，這說明通過虛擬節(jié)點選取次錨節(jié)點對降低定位誤差是有效的;其次，算法的定位誤差總體上比Centroid算法和DV-Hop算法的定位誤差小。因此，算法是一種適合無線傳感器網(wǎng)絡(luò)的定位算法。但并沒有考慮虛擬節(jié)點的分布對算法的影響，因此，虛擬節(jié)點的分布有一定的研究價值。

［1］王福豹，史 龍，任豐原.無線傳感器網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法［J］.軟件學(xué)報，2005，16(5):857－868.

［2］Bulusu N，Heidemann J，Estrin D.GPS-less low cost outdoor localization for very small devices［J］.IEEE Personal Communications Magazine，2000，7(5):28－34.

［3］Nicolescu D，Nath B.DV-based positioning in Ad Hoc networks［J］.Telecommunication Systems，2003，22(1－4):267－280.

［4］李兆斌，魏占禎，徐鳳麟.無線傳感器網(wǎng)絡(luò)增強的質(zhì)心定位算法及性能分析［J］.傳感技術(shù)學(xué)報，2009，22(4):563－566.

［5］于 寧，萬江文，吳銀峰.無線傳感器網(wǎng)絡(luò)定位算法研究［J］.傳感技術(shù)學(xué)報，2007，20(1):187－192.

［6］Yin M，Shu J，Liu L.The influence of beacon on DV-Hop in wireless sensor networks［C］∥GCCW＇06 5th International Conference on Grid and Cooperative Computing Workshops，2006:459－462.

［7］劉少飛，趙清華，王華奎.基于平均跳距估計和位置修正的DV-Hop定位算法［J］.傳感技術(shù)學(xué)報，2009，22(8):1154－1158.