基于虛擬節點的BP無線傳感器網絡定位算法

孫 凱，劉潤杰，申金媛

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

0 引言

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

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

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

仿真結果表明:BP神經網絡具有較小的定位誤差，并且，次錨節點的引入也可進一步提高定位精度。

1 基于BP的定位算法

1.1 BP 結構模型

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

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

1.2 利用BP估算位置

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

2 基于虛擬節點的定位算法

2.1 次錨節點

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

2.2 次錨節點的選擇

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

2.2.1 虛擬節點

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

2.2.2 跳數的轉化

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

圖1 跳數轉化圖Fig 1 Transformation diagram of Hop number

2.2.3 虛擬節點的選擇

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

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

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

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

2.3 次錨節點的應用

找到次錨節點后，重新構建BP神經網絡結構，將錨節點和次錨節點共同作為網絡的錨節點，重新訓練網絡。新BP網絡仍然采用兩層網絡結構，訓練完畢后，對所有的未知節點重新定位。

3 仿真與分析

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

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

3.1 定位誤差和無線射程

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

3.2 定位誤差和錨節點比例

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

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

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

3.3 定位誤差和節點數

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

圖5 節點數目和定位誤差Fig 5 Number of nodes and positioning error

4 結論

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

［1］王福豹，史 龍，任豐原.無線傳感器網絡中的自身定位系統和算法［J］.軟件學報，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］李兆斌，魏占禎，徐鳳麟.無線傳感器網絡增強的質心定位算法及性能分析［J］.傳感技術學報，2009，22(4):563－566.

［5］于 寧，萬江文，吳銀峰.無線傳感器網絡定位算法研究［J］.傳感技術學報，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］.傳感技術學報，2009，22(8):1154－1158.