樓國(guó)紅, 張劍平

(太原工業(yè)學(xué)院 電子工程系, 太原 030008)

無線傳感器網(wǎng)絡(luò)由自治無線節(jié)點(diǎn)構(gòu)成, 這些節(jié)點(diǎn)隨機(jī)部署在一個(gè)區(qū)域, 對(duì)控制對(duì)象的參數(shù)進(jìn)行收集, 如溫度、 聲音、 電壓等, 以幫助管理人員快速、 及時(shí)地收集對(duì)象數(shù)據(jù). 節(jié)點(diǎn)定位是無線傳感器網(wǎng)絡(luò)的應(yīng)用基礎(chǔ), 如果節(jié)點(diǎn)位置信息無效或錯(cuò)誤, 則無線傳感器網(wǎng)絡(luò)無法對(duì)目標(biāo)進(jìn)行準(zhǔn)確、 實(shí)時(shí)監(jiān)控, 因此節(jié)點(diǎn)定位方法的設(shè)計(jì)與研究是該領(lǐng)域關(guān)注的焦點(diǎn)[1-3].

目前, 節(jié)點(diǎn)定位常采用全球定位系統(tǒng)(global positioning system, GPS)對(duì)節(jié)點(diǎn)的位置進(jìn)行計(jì)算, 該方法受外界環(huán)境干擾小、 實(shí)時(shí)性好、 魯棒性高, 是目前定位精度最高的一種方法[4]. 無線傳感器網(wǎng)絡(luò)由大量的節(jié)點(diǎn)組成, 如果每個(gè)節(jié)點(diǎn)安裝一個(gè)GPS, 會(huì)導(dǎo)致無線傳感器網(wǎng)絡(luò)定位的成本高, 因此通常對(duì)少量的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)安裝GPS, 其位置已知, 這些節(jié)點(diǎn)稱為錨節(jié)點(diǎn)[5]. 先將錨節(jié)點(diǎn)的位置作為參考信息, 再對(duì)其他未知節(jié)點(diǎn)的位置進(jìn)行估計(jì)和定位, 當(dāng)前無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法根據(jù)是否需要硬件支撐情況劃分為兩類： 測(cè)距的無線傳感器網(wǎng)絡(luò)定位算法和無需測(cè)距的無線傳感器網(wǎng)絡(luò)定位算法[6]. 測(cè)距的無線傳感器網(wǎng)絡(luò)定位算法需要額外硬件支持, 根據(jù)信號(hào)強(qiáng)度或角度信息對(duì)無線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)位置進(jìn)行估計(jì), 如基于信號(hào)接收強(qiáng)度指示的無線傳感器網(wǎng)絡(luò)定位算法, 其傳感器節(jié)點(diǎn)定位精度高, 定位成本也相對(duì)更高. 而無需測(cè)距的無線傳感器網(wǎng)絡(luò)定位算法不需要額外硬件支持, 工作過程相對(duì)簡(jiǎn)單, 已成為當(dāng)前無線傳感器網(wǎng)絡(luò)的主要研究方向[7-9]. 無需測(cè)距的無線傳感器網(wǎng)絡(luò)定位算法主要有質(zhì)心定位算法和DV-Hop算法. 質(zhì)心定位算法根據(jù)無線傳感器網(wǎng)絡(luò)的連通性和未知節(jié)點(diǎn)不斷接收到的錨節(jié)點(diǎn)發(fā)送信息進(jìn)行定位, 但其定位誤差較大, 無法準(zhǔn)確確定未知節(jié)點(diǎn)的位置. 為了解決質(zhì)心定位算法的缺陷, 文獻(xiàn)[10-12]將測(cè)距中的到達(dá)時(shí)間差定位算法與其進(jìn)行組合, 對(duì)其定位結(jié)果進(jìn)行加權(quán), 一定程度上提高了節(jié)點(diǎn)的定位精度, 但權(quán)值如何進(jìn)行確定沒有統(tǒng)一的標(biāo)準(zhǔn)和理論指導(dǎo), 定位結(jié)果并非真正的最優(yōu). DV-Hop定位算法根據(jù)錨節(jié)點(diǎn)與未知節(jié)點(diǎn)之間的跳距實(shí)現(xiàn)節(jié)點(diǎn)定位, 因此節(jié)點(diǎn)距離的估計(jì)最關(guān)鍵, 標(biāo)準(zhǔn)DV-Hop定位算法采用平均距離作為節(jié)點(diǎn)距離, 當(dāng)無線傳感器節(jié)點(diǎn)的分布不均勻時(shí), 測(cè)距值估計(jì)的距離較大, 從而導(dǎo)致傳感器節(jié)點(diǎn)的定位誤差較大. 文獻(xiàn)[13]提出了采用遺傳算法對(duì)測(cè)距進(jìn)行優(yōu)化和修正, 減少平均測(cè)距誤差, 但遺傳算法存在收斂速度慢, 進(jìn)化后期易出現(xiàn)停滯現(xiàn)象, 難得到局部最優(yōu)解, 對(duì)測(cè)距優(yōu)化結(jié)果產(chǎn)生不利影響, 最終對(duì)無線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)定位結(jié)果進(jìn)行干擾.

針對(duì)節(jié)點(diǎn)定位存在的問題, 本文設(shè)計(jì)一種基于粒子群修正測(cè)距的無線傳感器節(jié)點(diǎn)定位算法. 首先對(duì)DV-Hop的工作原理進(jìn)行分析, 找到導(dǎo)致跳距估計(jì)誤差的因素, 然后采用粒子群算法對(duì)無線傳感器節(jié)點(diǎn)之間的測(cè)距估計(jì)結(jié)果進(jìn)行修正, 以減少節(jié)點(diǎn)間的測(cè)距估計(jì)誤差, 并對(duì)標(biāo)準(zhǔn)粒子群算法的不足進(jìn)行相應(yīng)的改進(jìn), 最后通過仿真實(shí)驗(yàn)與當(dāng)前經(jīng)典無線傳感器節(jié)點(diǎn)定位算法進(jìn)行對(duì)比測(cè)試. 測(cè)試結(jié)果表明, 在相同工作環(huán)境下, 本文方法提高了無線傳感器節(jié)點(diǎn)的定位精度, 且未增加額外硬件開銷, 比經(jīng)典無線傳感器節(jié)點(diǎn)的整體定位性能更優(yōu).

1 無線傳感器網(wǎng)絡(luò)結(jié)構(gòu)

圖1 無線傳感器網(wǎng)絡(luò)的基本結(jié)構(gòu)Fig.1 Basic structure of wireless sensor networks

無線傳感器網(wǎng)絡(luò)常包含大量的節(jié)點(diǎn), 節(jié)點(diǎn)采用隨機(jī)方式進(jìn)行部署, 分布極不均勻, 單個(gè)節(jié)點(diǎn)的數(shù)據(jù)處理和存儲(chǔ)能力有限, 因此節(jié)點(diǎn)之間信息冗余較高, 這些節(jié)點(diǎn)自動(dòng)構(gòu)成一個(gè)無線網(wǎng)絡(luò), 對(duì)監(jiān)測(cè)對(duì)象信息進(jìn)行采集, 通過與相鄰節(jié)點(diǎn)之間的信息轉(zhuǎn)發(fā)方式將信息發(fā)送到匯聚節(jié)點(diǎn), 匯聚節(jié)點(diǎn)主要負(fù)責(zé)數(shù)據(jù)的融合, 然后將數(shù)據(jù)發(fā)送到移動(dòng)通信網(wǎng)絡(luò), 移動(dòng)通信網(wǎng)絡(luò)將數(shù)據(jù)發(fā)送到需要的用戶. 在整個(gè)網(wǎng)絡(luò)中, 每個(gè)節(jié)點(diǎn)均有一個(gè)用于識(shí)別的號(hào)碼, 普通節(jié)點(diǎn)的能量通常有限, 且不能進(jìn)行補(bǔ)充, 而匯聚節(jié)點(diǎn)的能量是無限的, 不受限制, 而且節(jié)點(diǎn)的位置固定不能移動(dòng), 其基本結(jié)構(gòu)[14]如圖1所示.

2 DV-Hop算法和粒子群算法

2.1 DV-Hop算法

傳感器網(wǎng)絡(luò)有兩類節(jié)點(diǎn), 其中一類節(jié)點(diǎn)獲得自己所在位置坐標(biāo)的錨節(jié)點(diǎn), 另一類節(jié)點(diǎn)不知道自己位置的節(jié)點(diǎn), 只能通過錨節(jié)點(diǎn)估計(jì)其位置, 稱為未知節(jié)點(diǎn). DV-Hop算法是一種根據(jù)路由的跳數(shù)實(shí)現(xiàn)未知節(jié)點(diǎn)定位的經(jīng)典算法, 且節(jié)點(diǎn)定位的成本低, 自適應(yīng)能力強(qiáng), 步驟如下：

1) 傳感器節(jié)點(diǎn)之間的最小跳數(shù)計(jì)算. 每個(gè)錨節(jié)點(diǎn)在自己通信范圍內(nèi)不斷廣播自己的位置信息, 收到信息的節(jié)點(diǎn)保留最小跳數(shù), 同時(shí)對(duì)鄰居節(jié)點(diǎn)進(jìn)行廣播, 這樣全部節(jié)點(diǎn)都會(huì)記錄與所有錨節(jié)點(diǎn)之間的最小跳數(shù).

2) 計(jì)算無線傳感器網(wǎng)絡(luò)兩個(gè)錨節(jié)點(diǎn)之間的平均跳距. 根據(jù)錨節(jié)點(diǎn)的位置信息和最小跳數(shù)可得到任意兩個(gè)錨節(jié)點(diǎn)i和j之間的平均跳距, 計(jì)算公式為

(1)

式中:hi,j表示錨節(jié)點(diǎn)i和j之間的最小跳數(shù)； (xi,yi)和(xj,yj)分別表示錨節(jié)點(diǎn)i和j的位置坐標(biāo).

3) 未知節(jié)點(diǎn)位置的估計(jì). 根據(jù)未知節(jié)點(diǎn)u和錨節(jié)點(diǎn)i之間的最小跳數(shù)tu,s及平均跳距可得到未知節(jié)點(diǎn)u和錨節(jié)點(diǎn)i之間的距離為

du,s=HopSize×tu,s.

(2)

4) 當(dāng)未知節(jié)點(diǎn)得到附近3個(gè)錨節(jié)點(diǎn)的距離值時(shí), 可采用三邊定位算法得到未知節(jié)點(diǎn)的位置. 設(shè)D為待定位傳感器節(jié)點(diǎn),A,B,C為錨節(jié)點(diǎn), 其位置分別為(xA,yA),(xB,yB),(xC,yC), 則可建立如下關(guān)系式：

(3)

式中: (x,y)表示D的位置坐標(biāo);dA,dB和dC表示節(jié)點(diǎn)D與錨節(jié)點(diǎn)A,B,C之間的距離.

三邊定位算法只利用3個(gè)節(jié)點(diǎn)的位置信息, 提供的信息有限, 因此可引入極大似然估計(jì)法對(duì)未知節(jié)點(diǎn)的坐標(biāo)信息進(jìn)行估計(jì). 設(shè)共有n個(gè)錨節(jié)點(diǎn), 節(jié)點(diǎn)D與其距離分別為di(i=1,2,…,n), 則可建立如下方程：

(4)

對(duì)式(4)進(jìn)行變換和簡(jiǎn)化后, 可得:

(5)

設(shè)

可建立線性方程Ax=b, 從而得

x=(ATA)-1ATb.

(6)

采用最小二乘法, 根據(jù)式(6)可得到未知節(jié)點(diǎn)D的位置坐標(biāo).

對(duì)DV-Hop算法的實(shí)現(xiàn)過程進(jìn)行分析可知, 測(cè)距決定了無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的定位精度, 通常情況下, 根據(jù)信號(hào)強(qiáng)度對(duì)測(cè)距進(jìn)行估計(jì). 設(shè)節(jié)點(diǎn)發(fā)射功率為Pt, 發(fā)射節(jié)點(diǎn)和接收節(jié)點(diǎn)之間的距離為d,λ表示發(fā)射波長(zhǎng), 則接收節(jié)點(diǎn)收到的信號(hào)功率為

(7)

式中:Gt和Gr分別表示發(fā)射節(jié)點(diǎn)和接收節(jié)點(diǎn)的增益;L表示功率損耗常數(shù).

可將式(7)得到的信號(hào)功率轉(zhuǎn)換為傳感器節(jié)點(diǎn)之間的實(shí)際距離, 但在實(shí)際應(yīng)用中, 由于受空氣、 樹木及建筑物等外界因素的影響, 根據(jù)信號(hào)強(qiáng)度得到測(cè)距值與實(shí)際距離值之間存在一定的偏差, 從而導(dǎo)致節(jié)點(diǎn)定位誤差, 因此本文引入粒子群算法對(duì)測(cè)距進(jìn)行修正.

2.2 粒子群算法

設(shè)粒子i的位置向量和速度向量分別為Xi=(xi1,xi2,…,xiD)和Vi=(vi1,vi2,…,viD), 其當(dāng)前的最優(yōu)位置和粒子群的當(dāng)前最優(yōu)位置分別為Pi=(pi1,pi2,…,piD)和Pg=(pg1,pg2,…,pgD), 則第(k+1)時(shí)刻, 粒子i的速度和位置變化公式為

式中相關(guān)參數(shù)的意義見文獻(xiàn)[15]. 慣性權(quán)重ω的線性迭代表達(dá)式為

(10)

當(dāng)前的最優(yōu)位置及粒子群當(dāng)前最優(yōu)位置的更新公式分別為

(11)

f(Pg)=min{f(Pi)}.

(12)

標(biāo)準(zhǔn)粒子群算法也存在易出現(xiàn)局部最優(yōu)解的缺陷, 因此本文引入混沌機(jī)制對(duì)粒子的位置進(jìn)行擾動(dòng), 幫助其逃離局部最優(yōu)解. Logistic混沌系統(tǒng)為

zi+1=μzi(1-zi),zi∈[0,1],μ∈(2,4].

(13)

選擇遺傳算法作為對(duì)比算法, 其對(duì)式(14),(15)的求解目標(biāo)函數(shù)值變化曲線如圖2所示. 由圖2可見, 粒子群算法的收斂速度明顯快于遺傳算法, 目標(biāo)函數(shù)值更理想, 對(duì)比結(jié)果說明了粒子群算法的優(yōu)越性.

圖2 兩種算法對(duì)目標(biāo)函數(shù)的求解曲線Fig.2 Solving curves of objective function by two algorithms

3 算法設(shè)計(jì)

3.1 誤差修正系數(shù)

為了降低測(cè)距誤差, 引入距離誤差修正系數(shù)μ對(duì)未知節(jié)點(diǎn)潛在的區(qū)域進(jìn)行限制, 以提高無線傳感器網(wǎng)絡(luò)測(cè)距的準(zhǔn)確性. 距離誤差修正系數(shù)μ的求解步驟如下:

1) 采用信號(hào)強(qiáng)度技術(shù)估計(jì)未知節(jié)點(diǎn)D與m個(gè)錨節(jié)點(diǎn)之間的距離di(i=1,2,…,m);

2) 隨機(jī)選擇3個(gè)錨節(jié)點(diǎn)作為參考節(jié)點(diǎn), 得到D的位置約為(x′,y′)；

(16)

5) 將ei的平均值作為距離誤差修正系數(shù)：

(17)

6) 未知節(jié)點(diǎn)可行域范圍的約束條件為

(18)

3.2 節(jié)點(diǎn)定位數(shù)學(xué)模型

節(jié)點(diǎn)定位的數(shù)學(xué)模型可采用如下形式進(jìn)行描述：

(19)

無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位的目標(biāo)函數(shù)為

(20)

其中M表示距離誤差懲罰因子.

3.3 粒子群算法修正測(cè)距的無線傳感器節(jié)點(diǎn)定位步驟

1) 初始化粒子群算法的參數(shù), 如慣性權(quán)重、 最大迭代次數(shù);

2) 計(jì)算無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位的μ, 并確定目標(biāo)函數(shù);

3) 初始化粒子群的種群;

4) 根據(jù)目標(biāo)函數(shù)計(jì)算每個(gè)粒子的適應(yīng)度值, 并確定Pi和Pg;

5) 迭代次數(shù)增加, 更新慣性權(quán)重, 并更新每個(gè)粒子的位置和速度, 產(chǎn)生新一代的粒子群;

6) 計(jì)算新一代粒子群的適應(yīng)度值, 并對(duì)Pi和Pg進(jìn)行更新;

7) 如果當(dāng)前迭代次數(shù)超過最大迭代次數(shù), 則得到無線傳感器節(jié)點(diǎn)的位置.

粒子群算法修正測(cè)距的無線傳感器節(jié)點(diǎn)定位流程如圖3所示.

圖3 粒子群算法修正測(cè)距的無線傳感器節(jié)點(diǎn)定位流程Fig.3 Flow chart of ranging distance modified by particle swarm algorithm for wireless sensor nodes location

4 仿真測(cè)試

選擇DV-Hop算法、 遺傳算法修正測(cè)距的無線傳感器節(jié)點(diǎn)定位算法在相同實(shí)驗(yàn)環(huán)境下進(jìn)行仿真對(duì)比實(shí)驗(yàn). 采用VC++6.0進(jìn)行編程實(shí)現(xiàn)定位算法. 定位結(jié)果采用如下定位誤差進(jìn)行分析：

(21)

圖4 不同算法的傳感器節(jié)點(diǎn)定位誤差變化曲線Fig.4 Location error variation curves of sensor nodes for different algorithms

統(tǒng)計(jì)DV-Hop算法、 遺傳算法修正測(cè)距的無線傳感器節(jié)點(diǎn)定位算法和粒子群算法修正測(cè)距的無線傳感器節(jié)點(diǎn)定位算法的節(jié)點(diǎn)定位誤差(m), 結(jié)果如圖4所示. 由圖4可見, DV-Hop算法的節(jié)點(diǎn)定位誤差最大, 其次為遺傳算法, 而粒子群算法修正測(cè)距的無線傳感器節(jié)點(diǎn)定位效果最優(yōu).

為了分析不同算法的傳感器節(jié)點(diǎn)定位實(shí)際效果,圖5給出了DV-Hop算法(A)、 遺傳算法修正測(cè)距的無線傳感器節(jié)點(diǎn)定位算法(B)和粒子群算法修正測(cè)距的無線傳感器節(jié)點(diǎn)定位算法(C)的節(jié)點(diǎn)定位結(jié)果. 由圖5可見, 由于遺傳算法和粒子群算法對(duì)無線傳感器節(jié)點(diǎn)的測(cè)距誤差進(jìn)行了校正, 因此無線傳感器節(jié)點(diǎn)定位效果優(yōu)于傳統(tǒng)的DV-Hop算法, 同時(shí)粒子群算法定位效果優(yōu)于遺傳算法, 這主要是粒子群算法克服了遺傳算法收斂速度慢、 易陷入局部最優(yōu)的缺陷, 提高了無線傳感器節(jié)點(diǎn)定位精度.

圖5 不同算法的節(jié)點(diǎn)實(shí)際定位結(jié)果Fig.5 Actual location results of the nodes for different algorithms

綜上所述, 本文提出了一種粒子群修正跳距的傳感器節(jié)點(diǎn)定位算法, 仿真測(cè)試結(jié)果表明, 粒子群算法可解決當(dāng)前DV-Hop算法定位過程存在的問題, 在不增加額外硬件的情況下, 有效改善了傳感器節(jié)點(diǎn)定位的效果, 具有一定的優(yōu)越性.