基于DV-HOP的分布式無線傳感器網(wǎng)絡(luò)定位算法研究

劉國輝

(沈陽大學(xué) 教務(wù)處現(xiàn)代教育技術(shù)中心，沈陽 110044)

信息技術(shù)的快速發(fā)展使得電子技術(shù)、計(jì)算機(jī)技術(shù)以及無線通訊技術(shù)等得到了更快的進(jìn)步，低功耗多功能的無線傳感器憑借其體積小、可將信息采集、數(shù)據(jù)處理以及無線通訊等多種功能融為一體的優(yōu)勢，得到了更加廣泛的應(yīng)用[1]。

目前隨著該領(lǐng)域研究學(xué)者的不斷深入研究，徐巍超等[2]設(shè)計(jì)了一種通過無人機(jī)協(xié)助，利用極大似然估計(jì)法對未知的節(jié)點(diǎn)進(jìn)行初步定位的方法，以解決無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)在復(fù)雜的三維地形實(shí)際應(yīng)用的問題，該方法設(shè)計(jì)主要采用了平方根容積卡爾曼濾波算法進(jìn)行定位。實(shí)驗(yàn)表明，該算法對定位結(jié)果的精準(zhǔn)度較高，但對于節(jié)點(diǎn)的硬件及軟件的要求也較高，同時(shí)也增加了網(wǎng)絡(luò)部署的成本。錢開國等[3]提出了一種基于可靠信標(biāo)和節(jié)點(diǎn)度估計(jì)距離的無線傳感器網(wǎng)絡(luò)定位算法，以解決無線傳感器網(wǎng)絡(luò)定位算法傳感器節(jié)點(diǎn)分布不均勻應(yīng)用的情況。該算法與前者相比，不需要增加額外的硬件開銷，降低了成本，但精準(zhǔn)度得不到保障。

無線傳感器網(wǎng)絡(luò)中包含微電子技術(shù)、感知技術(shù)、分布式信息處理技術(shù)等多種先進(jìn)的技術(shù)，改變了人們與自然界信息傳統(tǒng)的交流方式，進(jìn)一步拓展了人們獲取各類信息的能力范圍。本文提出了一種基于DV-HOP的分布式無線傳感器網(wǎng)絡(luò)定位算法。

1 基于DV-HOP的分布式無線傳感器網(wǎng)絡(luò)定位算法設(shè)計(jì)

基于DV-HOP的分布式無線傳感器網(wǎng)絡(luò)定位算法流程可分為4個(gè)步驟：

第一步：選取分布式無線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)，根據(jù)轉(zhuǎn)化條件篩選，選出符合要求的定位節(jié)點(diǎn)；

第二步：以距離未知節(jié)點(diǎn)最近的定位節(jié)點(diǎn)作為參考，計(jì)算其它節(jié)點(diǎn)的可信度；

第三步：基于DV-HOP得出定位節(jié)點(diǎn)的泛洪信息，并計(jì)算各個(gè)未知節(jié)點(diǎn)得到與其相連接的定位節(jié)點(diǎn)數(shù)量和距離，再計(jì)算結(jié)果誤差，選擇符合條件的節(jié)點(diǎn)作為新的定位節(jié)點(diǎn)；

第四步：利用新的定位節(jié)點(diǎn)重新循環(huán)上述3個(gè)步驟，直到分布式無線傳感器網(wǎng)絡(luò)中找不出符合定位條件的未知節(jié)點(diǎn)，完成對分布是無線傳感器網(wǎng)絡(luò)的定位。

1.1 分布式無線傳感器網(wǎng)絡(luò)定位節(jié)點(diǎn)篩選

在分布式無線傳感器網(wǎng)絡(luò)中，其部分的拓?fù)浣Y(jié)構(gòu)如圖1所示。

圖1 分布式無線傳感器網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖

圖1中A1、A2、A3、A4表示為靠近未知點(diǎn)B1的4個(gè)定位節(jié)點(diǎn)，根據(jù)DV-HOP算法的最大似然估計(jì)原理，在二維平面中，B1至少需要3個(gè)定位節(jié)點(diǎn)估計(jì)其具體位置信息。選取圖1中的3個(gè)定位節(jié)點(diǎn)A1、A2、A3，其組成的三角形的內(nèi)角應(yīng)滿足下述公式：

(1)

公式(1)中，A1A2表示為定位節(jié)點(diǎn)A1、A2之間的距離；A1A3表示為定位節(jié)點(diǎn)A1、A3之間的距離；A2A3表示為定位節(jié)點(diǎn)A2、A3之間的距離。

假設(shè)3個(gè)定位節(jié)點(diǎn)的共線度為：

(2)

公式(2)中，αi表示為3個(gè)定位節(jié)點(diǎn)構(gòu)成的三角形內(nèi)角，因此3個(gè)定位節(jié)點(diǎn)的共線度取值范圍在π/3～π，當(dāng)共線度為π時(shí)，表示3個(gè)定位節(jié)點(diǎn)完全處于同一直線上。當(dāng)共線度為π/3時(shí)，通過定位節(jié)點(diǎn)得到的計(jì)算結(jié)果誤差最小。因此，在進(jìn)行定位計(jì)算前，首先要設(shè)定一個(gè)閾值D，根據(jù)文獻(xiàn)[2]的實(shí)驗(yàn)方法，結(jié)合本文內(nèi)容設(shè)定D的取值范圍為0～0.5，當(dāng)未知節(jié)點(diǎn)接收到多個(gè)定位節(jié)點(diǎn)的路由信息時(shí)，首先應(yīng)根據(jù)公式(1)計(jì)算出距離未知節(jié)點(diǎn)最近的3個(gè)定位定位節(jié)點(diǎn)的共線度，當(dāng)共線度DC的余弦函數(shù)的絕對值在0～D，則可進(jìn)行后續(xù)通過3次測量法求解出未知節(jié)點(diǎn)的位置信息；當(dāng)共線度DC的余弦函數(shù)的絕對值不在設(shè)定的范圍內(nèi)時(shí)，則由DV-HOP算法自動選擇距離B2第二近的另一個(gè)定位節(jié)點(diǎn)，即A4代替A3作為候選定位節(jié)點(diǎn)，直到3個(gè)定位節(jié)點(diǎn)的共線度滿足上述要求。

利用協(xié)作定位算法，將通過定位后得到準(zhǔn)確位置信息的節(jié)點(diǎn)有條件的轉(zhuǎn)換為定位節(jié)點(diǎn)，從而參與到對未知節(jié)點(diǎn)的定位[4]。當(dāng)定位結(jié)果足夠精準(zhǔn)的節(jié)點(diǎn)才能轉(zhuǎn)換為定位節(jié)點(diǎn)，否則其它估計(jì)得出的位置信息用于對其它未知節(jié)點(diǎn)的定位會增加誤差的累積。

1.2 節(jié)點(diǎn)可信度計(jì)算

當(dāng)未知節(jié)點(diǎn)B1與定位節(jié)點(diǎn)A1、A2、A3、A4相連接，且4個(gè)定位節(jié)點(diǎn)兩兩之間的距離值相近時(shí)，B1與A3和A4的連接較靠近直線，但與A2的連接較為曲折[5]。因此，為了滿足后續(xù)對未知節(jié)點(diǎn)平均跳距計(jì)算精度，同時(shí)保證計(jì)算過程中未知節(jié)點(diǎn)B2與定位節(jié)點(diǎn)A2之間的距離計(jì)算不受到影響，還需對選擇的定位節(jié)點(diǎn)進(jìn)行可信度計(jì)算。

設(shè)分布式無線傳感器網(wǎng)絡(luò)中共包含X個(gè)定位節(jié)點(diǎn)，當(dāng)定位節(jié)點(diǎn)i與其它X-1個(gè)定位節(jié)點(diǎn)的單條路徑的平均跳距為TKih，則平均跳距與定位節(jié)點(diǎn)i的總平均跳距之間的偏差程度經(jīng)過歸一化處理后可用于表示定位節(jié)點(diǎn)h相對于定位節(jié)點(diǎn)i的可信度，其計(jì)算公式可用公式(3)表示：

(3)

公式(3)中，Kih表示為定位節(jié)點(diǎn)的可信度。由公式(3)可以看出，當(dāng)TKi與TKih之間存在較大偏差時(shí)，可信度的取值越小，因此定位節(jié)點(diǎn)i與定位節(jié)點(diǎn)h的單路徑較為曲折，在后續(xù)未知節(jié)點(diǎn)平均跳距計(jì)算中會產(chǎn)生較大的誤差[6]。根據(jù)公式(3)計(jì)算出X個(gè)定位節(jié)點(diǎn)中計(jì)算誤差最小的定位節(jié)點(diǎn)，并將其帶入到公式(4)中進(jìn)行平均跳距計(jì)算。

1.3 基于DV-HOP的未知節(jié)點(diǎn)平均跳距計(jì)算

基于DV-HOP的算法，采用三邊測量的方法估計(jì)未知節(jié)點(diǎn)的具體位置信息，根據(jù)公式(3)可信度計(jì)算得出3個(gè)可信度最大且相同的定位節(jié)點(diǎn)。定位節(jié)點(diǎn)的分布不均勻可能會造成可信度之間存在差異，可信度較低的定位節(jié)點(diǎn)在進(jìn)行對未知節(jié)點(diǎn)的平均跳距計(jì)算時(shí)，可能會降低定位的精準(zhǔn)性[7]。因此，當(dāng)未知節(jié)點(diǎn)接收到多個(gè)定位節(jié)點(diǎn)時(shí)的平均跳距信息后，需要選取其中最近的定位節(jié)點(diǎn)的平均跳距作為參考數(shù)據(jù)，再根據(jù)其它定位節(jié)點(diǎn)對該定位節(jié)點(diǎn)的可信度進(jìn)行加權(quán)平均。基于DV-HOP的未知節(jié)點(diǎn)平均跳距計(jì)算公式為：

(4)

公式(4)中，TKB表示為B1的平均跳距；TK1、TK2、TK3、TK4表示為未知節(jié)點(diǎn)B1接收到來自4個(gè)定位節(jié)點(diǎn)的平均跳距，其中A1與未知節(jié)點(diǎn)B1的平均跳距最小；k21、k31、k41表示為定位節(jié)點(diǎn)A2、A3和A4相對于A1的可信度。

在獲取未知節(jié)點(diǎn)B1的平均跳距后，根據(jù)A1與各個(gè)定位節(jié)點(diǎn)之間的最小跳數(shù)，兩者相乘計(jì)算出A1和候選定位節(jié)點(diǎn)之間的距離[8]。再利用公式(5)，計(jì)算出A1的在分布式無線傳感器網(wǎng)絡(luò)中的具體位置信息：

(5)

公式(5)中，(xi，yi)表示為定位節(jié)點(diǎn)i的坐標(biāo)；(xh，yh)表示為定位節(jié)點(diǎn)h的坐標(biāo)，根據(jù)交換機(jī)上的流表信息，得到信任節(jié)點(diǎn)的沖激響應(yīng)特征，其表示為：

(6)

式中，a1表示多路徑轉(zhuǎn)發(fā)的跳數(shù)。采用多隊(duì)列的輪循調(diào)度方法，得到分散化網(wǎng)絡(luò)的節(jié)點(diǎn)的輸出占空比為：

(7)

計(jì)算網(wǎng)絡(luò)信任節(jié)點(diǎn)的協(xié)議號為，流量的優(yōu)先級為C(n),指定帶寬為ifj，得到網(wǎng)絡(luò)信任節(jié)點(diǎn)的感知半徑Ry可以表示為：

Ry=TKih+1,ifj?TKih.

(8)

完成對分布是無線傳感器網(wǎng)絡(luò)的定位。

2 驗(yàn)證分析

2.1實(shí)驗(yàn)準(zhǔn)備

首先，利用仿真實(shí)驗(yàn)軟件建立一個(gè)模擬的分布是無線傳感器網(wǎng)絡(luò)，并設(shè)定該網(wǎng)絡(luò)的區(qū)域?yàn)?0 m×50 m的正方形，在該區(qū)域內(nèi)隨機(jī)分布多個(gè)定位節(jié)點(diǎn)和未知節(jié)點(diǎn)，并將所有的節(jié)點(diǎn)通信半徑設(shè)置為相同的參數(shù)。分別利用徐魏超等[2]定位算法和本文提出的基于DV-HOP的分布式無線傳感器網(wǎng)絡(luò)定位算法對區(qū)域中未知節(jié)點(diǎn)定位，并設(shè)置本文算法為實(shí)驗(yàn)組，徐魏超等算法為對照組，比較兩組算法的平均定位誤差。

2.2 結(jié)果及分析

在100 s內(nèi)保持靜止，超寬帶定位系統(tǒng)每隔1 s進(jìn)行一次數(shù)據(jù)采集，假設(shè)TDOA距離差值誤差均值為10，方差為50，實(shí)驗(yàn)結(jié)果如圖2所示：

圖2 定位節(jié)點(diǎn)誤差

根據(jù)兩組算法計(jì)算結(jié)果與節(jié)點(diǎn)實(shí)際位置信息比對，得出兩組算法的平均定位誤差(見表1)。

表1 平均定位誤差實(shí)驗(yàn)結(jié)果對比表

由表1兩組數(shù)據(jù)結(jié)果可以看出，實(shí)驗(yàn)組的平均定位誤差在0.300～0.450 m，而對照組平均定位誤差在0.600～0.750 m，實(shí)驗(yàn)組平均定位誤差明顯小于對照組平均定位誤差。

表2 平均定位耗時(shí)實(shí)驗(yàn)結(jié)果對比表

由表2可以得知，實(shí)驗(yàn)組的平均定位耗時(shí)基本在3 s，最高耗時(shí)也僅達(dá)4 s，而對照組的耗時(shí)平均在7 s左右，最高耗時(shí)可達(dá)8 s，實(shí)驗(yàn)組的耗時(shí)明顯低于對照組。因此通過對比實(shí)驗(yàn)證明，本文基于DV-HOP的分布式無線傳感器網(wǎng)絡(luò)定位算法有效降低了定位算法結(jié)果的誤差，對分布式無線傳感器網(wǎng)路中的未知節(jié)點(diǎn)進(jìn)行更加精準(zhǔn)的定位且耗時(shí)更少。

3 結(jié)論

本文結(jié)合DV-HOP算法，提出一種全新的分布式無線傳感器網(wǎng)路定位的算法，通過對比實(shí)驗(yàn)證明了該算法與徐魏超等的算法相比計(jì)算誤差和定位耗時(shí)都得到了明顯的改善。在后續(xù)的研究中還將在分布式無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)精準(zhǔn)定位的基礎(chǔ)上，對信息融合算法選擇定位節(jié)點(diǎn)進(jìn)行更加深入的研究，從而得到更加滿足定位合理性的算法。