基于煙花算法的無線傳感器網絡節(jié)點定位

朱曉麗，高鵬

(1.萬博科技職業(yè)學院計算機科學與技術系,安徽 合肥 230031； 2.安徽工業(yè)經濟職業(yè)技術學院計算機與藝術學院,安徽 合肥 230051)

0 引言

無線傳感器網絡(wireless sensor networks, WSN)通常是自組織網絡，它由大量低功耗的傳感器節(jié)點組成，這些傳感器節(jié)點分布在一些需要監(jiān)測的區(qū)域，監(jiān)控物理參數或環(huán)境狀況，并將收集到的信息轉移到匯聚節(jié)點。目前WSN已被應用于許多領域，如軍事、工業(yè)、醫(yī)學，用作目標跟蹤、環(huán)境監(jiān)測、事件檢測等。一般自組織網絡的路由問題主要是WSN定位問題。傳感器節(jié)點往往隨機分布，應用WSN的地方幾乎都需要知道傳感器的位置，因為采集的數據不含位置信息就沒有實用價值。如果每個傳感器節(jié)點都使用全球定位系統(tǒng)(global positioning system, GPS)獲取節(jié)點位置信息，成本昂貴，通常不可行。一種解決方法是選擇部分傳感器作為錨節(jié)點，由GPS或手動配置獲得錨節(jié)點定位信息，再結合不同技術估算其他傳感器節(jié)點位置。

目前估算傳感器節(jié)點位置的算法分為測距定位算法和無測距定位算法。無測距定位算法估計傳感器的位置，利用的是相鄰節(jié)點之間的連通性和拓撲信息[1]。測距定位算法估計傳感器的位置，依賴于節(jié)點之間的距離，通過估算無線電信號接收強度(received signal strength, RSS)、到達時間(time of arrival, TOA)、到達時間差(time difference of arrival, TDOA)、到達角(angle-of-arrival, AOA)等獲取節(jié)點之間的距離信息[2]。

WSN定位優(yōu)化問題十分復雜，但是隨機算法的產生及應用正逐漸解決這一問題。其中應用最廣泛的是群智能算法，這是一種模擬生物群體集體智慧的算法。群智能算法在解決局部最優(yōu)解和離散組合指數等復雜的優(yōu)化問題上較為成功，但其在處理大規(guī)模優(yōu)化問題上算法執(zhí)行效率很低。為此，Tan和Zhu[3]在2010年提出了一種新的群智能算法——煙花算法(FWA)。本文將FWA應用于WSN節(jié)點定位，測量結果顯示，和常見的幾種算法相比，FWA定位誤差較小，這為FWA在WSN節(jié)點定位上的應用提供了依據。

1 WSN節(jié)點定位的數學建模

在解決WSN定位問題上，測距定位算法準確性高,應用廣泛,其中基于RSS的定位算法具有很強的測試和分析性能，因此本文選擇RSS獲取節(jié)點之間距離信息。

接收機越靠近發(fā)射機，接收信號的強度就越大。基于發(fā)送功率和接收功率之間的關系，可以估算兩個節(jié)點之間的距離。由于不同節(jié)點使用的硬件不同或測量過程中環(huán)境噪聲發(fā)生變化，測距誤差會很大。此外，無線電反射引起的多徑傳播，會導致衰落現象，也會產生較大誤差。為了減少這些誤差，用對數正態(tài)陰影[4]描述無線信道衰落現象：

(1)

式中：Pt表示發(fā)射功率；PL(d0)表示路徑損耗；d0和α分別是參考距離和路徑損耗指數；Xσ在高斯分布N(0,σ2)中出現，表示無線電信號的噪聲。測距技術只是定位算法的第一部分。第二部分是確定傳感器節(jié)點的確切位置，使用錨節(jié)點的位置和通過RSS獲得的不精確的距離計算所有傳感器節(jié)點的位置。設錨節(jié)點坐標為(xj,yj)，若WSN包含N個未知傳感器節(jié)點，(xi,yi)表示未知節(jié)點i(i=1,2,…,N)的坐標，則未知節(jié)點與錨節(jié)點之間的距離為

(2)

RSS定位算法測得的距離Rij和由式(2)得出距離dij之間的距離誤差為

eij=(Rij-dij)2

(3)

假設節(jié)點i有M個相鄰錨節(jié)點，定位誤差公式變?yōu)?/p>

(4)

最終目的是最小化所有未知節(jié)點的誤差總和，因此目標函數為

(5)

對目標函數進行優(yōu)化是本文的研究重點，所選用的算法誤差總和越小，WSN節(jié)點定位越準確。本文應用新型群智能算法——FWA對此問題進行優(yōu)化。

2 煙花算法

將FWA這一迭代算法應用于WSN定位，通過迭代估算相鄰節(jié)點的位置。測距定位算法在估算距離時使用單邊或多邊定位。這種方法可以減少所需的錨節(jié)點數量，降低硬件成本，但如果沒有足夠的錨節(jié)點，一些節(jié)點的位置是無法估算的。迭代多邊算法還存在誤差積累問題，且要求錨節(jié)點必須位于網絡邊緣[5-6]。

FWA在特定地點隨機產生n個煙花。每個煙花xi產生的火花量為[7]

(6)

式中：參數m表示n個煙花產生的火花數量；ymax是最差煙花，ymax=max(f(xi))(i=1,2,…,n)；η代表用于避免除零錯誤分配的小常數。

制作的煙花爆炸振幅不同，建模如下：

(7)

(8)

(9)

爆炸隨機影響火花的尺寸z，定義為

z=round(d·x)

(10)

式中，d是維數優(yōu)化數量，x代表隨機數在0和1之間的均勻分布，所有選定的維度確定時，x也同時確定。文獻[8—9]對此提出改進建議，將火花映射到新的位置公式：

ΔXk=Ai·rand(-1,1)

(11)

火花保持最佳位置x*并轉移到下一處，根據其余的(N-1)個地點到其他地點的距離，選擇它們的位置。某一位置xi和其他位置之間的距離由下式計算：

(12)

式中，K是煙花當前所有位置的集合[10]?；诠?12)得到的距離，選擇位置xi的概率為

(13)

文獻[11]針對映射與變異算子提出了兩項改進。映射操作符改為

(14)

高斯變異算子為

(15)

式中，XB是目前煙花爆炸發(fā)現火花的最好位置，且e=N(0,1)。

3 FWA在節(jié)點定位的應用

傳感器節(jié)點被隨機分布在需要監(jiān)測的區(qū)域，其中一些被隨機選擇為錨節(jié)點。使用公式(1)建立無線信道模型，計算RSS以及節(jié)點之間的距離，用該煙花算法優(yōu)化目標函數。本文對目標函數進行調整[12]，定義新的目標函數：

(16)

估計完未知傳感器節(jié)點的位置后，更新錨節(jié)點位置，從而估計相鄰傳感器節(jié)點的位置。為了能夠本地化，一個節(jié)點必須至少有3個相鄰錨節(jié)點。在這種情況下，對于未知傳感器節(jié)點，FWA使用公式(16)最小化目標函數。

在未知傳感器節(jié)點有1個或2個相鄰錨節(jié)點的情況下，采用FWA估計節(jié)點位置[13]。所有更新的錨節(jié)點從原始錨節(jié)點那里獲取距離信息，如果未知傳感器節(jié)點有1個或2個錨節(jié)點，則可以從相鄰節(jié)點的位置數據發(fā)現它的位置，這極大地提高了節(jié)點定位精度。

4 實驗結果

為了驗證本文算法，利用MATLAB進行仿真實驗，對比本文提出的FWA與回聲定位算法、多點定位算法、DV-hop算法、粒子群優(yōu)化算法、神經網絡算法、改進的DV-hop算法的定位效果。對本文提出的FWA的實驗參數進行設置：煙花數為5，迭代次數為5 000次，爆炸振幅為40，火花最小、最大數量分別設置為2和40。為了進行比較，調整初始實驗條件，參數設置如下：

Pt=0 dBm,PL(d0)=55 dBm

當d0=1時，路徑損耗指數α=4。監(jiān)測區(qū)域設置為50 m×50 m，傳輸距離為25 m。每個實驗開始時，傳感器節(jié)點隨機分布在該地區(qū)，錨節(jié)點隨機選擇。用公式(17)計算未知節(jié)點和錨節(jié)點之間的距離，其結果為實際距離，把實際距離與估計距離的比值作為定位誤差，并考慮RSS的噪聲干擾，同時結合已有參數值，得出噪聲干擾因素下的距離值：

(17)

為了驗證本文算法性能，分別測試各算法隨RSS值、節(jié)點數、錨節(jié)點數和噪聲標準偏差變化時的定位誤差。圖1為不同RSS值時定位誤差的變化?？梢钥闯?，隨著RSS值的增加，各個算法的定位誤差逐漸減低，并趨于穩(wěn)定，這是由于定位誤差是根據所測試的估計距離的平均值得出。在此過程中，本文提出的FWA定位誤差較小，定位精度較高。

圖1 RSS值與定位誤差的關系

圖2是節(jié)點數與定位誤差之間的關系?？梢钥闯?，隨著傳感器節(jié)點數的增加，定位誤差逐漸減小，同時定位誤差趨于穩(wěn)定。與其他算法相比，FWA的定位精度較高，且在節(jié)點數量變化過程中FWA定位誤差值變化平穩(wěn)，定位穩(wěn)定性較好。

圖2 節(jié)點數量與定位誤差的關系

為了進一步驗證本文算法的優(yōu)越性，對不同錨節(jié)點數下的定位誤差進行測試。由圖3可知，選擇更多的錨節(jié)點時定位誤差較低。當62%以上的傳感器節(jié)點被用作錨節(jié)點時，本文FWA定位誤差最小，而錨節(jié)點比例小于50%時FWA相對于粒子群算法定位誤差偏大。但總體來說，在錨節(jié)點數量一定時，FWA定位誤差較小，定位較準確。

圖3 錨節(jié)點數量與定位誤差的關系

圖4比較了6種不同算法的噪聲水平和定位誤差之間的關系。由此可知，隨著噪聲標準偏差的增大，定位誤差變大，本文提出的FWA模型誤差平穩(wěn)增加，且誤差最小，說明FWA在WSN節(jié)點定位時性能穩(wěn)定、精度高。

圖4 噪聲標準偏差與定位誤差的關系

5 結語

為優(yōu)化WSN節(jié)點定位精度，使節(jié)點定位誤差更小，且整體性能更穩(wěn)定，本文將一種新的群智能算法——FWA應用于WSN節(jié)點定位系統(tǒng)。通過更新傳感器節(jié)點定位過程中的錨節(jié)點，使定位節(jié)點的數量增加。通過仿真實驗，使用不同的實驗參數，測試本文所提出的FWA在不同的網絡規(guī)模、不同信號強度等情況下的應用效果。最后，將各實驗因素綜合起來，通過橫向比較，證明了相比其他算法，FWA在進行無線網絡節(jié)點定位時定位精度更高，性能更穩(wěn)定。