孫 凱，劉潤(rùn)杰，申金媛

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

0 引言

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

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

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

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

1 基于BP的定位算法

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

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

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

1.2 利用BP估算位置

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

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

2.1 次錨節(jié)點(diǎn)

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

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

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

2.2.1 虛擬節(jié)點(diǎn)

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

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

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

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

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

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

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

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

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

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

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

3 仿真與分析

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

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

3.1 定位誤差和無(wú)線射程

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

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

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

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

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

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

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

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

4 結(jié)論

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

［1］王福豹，史 龍，任豐原.無(wú)線傳感器網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法［J］.軟件學(xué)報(bào)，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ú)線傳感器網(wǎng)絡(luò)增強(qiáng)的質(zhì)心定位算法及性能分析［J］.傳感技術(shù)學(xué)報(bào)，2009，22(4):563－566.

［5］于 寧，萬(wàn)江文，吳銀峰.無(wú)線傳感器網(wǎng)絡(luò)定位算法研究［J］.傳感技術(shù)學(xué)報(bào)，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］劉少飛，趙清華，王華奎.基于平均跳距估計(jì)和位置修正的DV-Hop定位算法［J］.傳感技術(shù)學(xué)報(bào)，2009，22(8):1154－1158.