基于ISSA-GRNN的無線傳感器網(wǎng)絡定位優(yōu)化算法

王家威,薛亞輝,魏子堯

1.焦作大學 信息工程學院,河南 焦作 454000;2.中國石油大學(華東) 控制科學與工程學院,山東 青島 266580

隨著信息與網(wǎng)絡技術(shù)的不斷發(fā)展,無線傳感器網(wǎng)絡(Wireless Sensor Network,WSN)作為一項重要技術(shù)也已廣泛應用于追蹤、探測等領域[1-2]。節(jié)點定位問題作為其重點處理的問題之一,這些年來也在不斷改進和更新。經(jīng)典的無線傳感器網(wǎng)絡定位算法主要包括基于TOA、AOA、RSSI等距離相關算法[3]和基于Centroid、DV-Hop、APIT等距離無關這兩大類算法[4-6]。

近年來,智能優(yōu)化算法的不斷出現(xiàn)和深入融合促進了諸多技術(shù)與領域的協(xié)同發(fā)展,在定位問題上,也得到較多的應用。范時平等[7]DV-Hop算法的節(jié)點跳距進行改進,并與粒子群算法結(jié)合進行傳感器節(jié)點定位;方旺盛等[8]在改進粒子群算法優(yōu)化的基礎上,對節(jié)點跳數(shù)、跳距進行修正;印雷等[9]提出了改進的麻雀搜索算法,并對修正后的DV-Hop算法進行優(yōu)化;顏慧超等[10]提出了一種ISSA-DH算法,主要改進了節(jié)點跳數(shù)、跳距以及位置的計算方法;高棟等[11]利用RSSI修正Centroid算法的質(zhì)心,并結(jié)合灰狼優(yōu)化算法對相關節(jié)點進行定位。

針對DV-Hop和Centroid算法的定位精度問題,本文將這兩種算法和加權(quán)優(yōu)化方法進行融合。利用加權(quán)平均法,通過預估距離與實際距離之間的誤差量修正跳距,利用改進的加權(quán)因子并引入RSSI修正Centroid算法的質(zhì)心。通過采集不同節(jié)點間的關聯(lián)特征,將修正后的跳距特征、質(zhì)心特征和節(jié)點其他重要特征等進行特征融合,添加到廣義回歸神經(jīng)網(wǎng)絡(generalized regression neural network,GRNN)[12]中進行訓練。在結(jié)合GRNN的同時,需要考慮網(wǎng)絡中的調(diào)節(jié)參數(shù)對整體效果的影響,本文利用麻雀搜索算法(sparrow search algorithm,SSA)[13-14]的優(yōu)化思想改善GRNN網(wǎng)絡參數(shù),以解決參數(shù)隨機設置而導致預測不準確的問題。仿真實驗結(jié)果表明,結(jié)合后的優(yōu)化算法可以有效減少定位誤差,提高節(jié)點定位精度。

1 相關算法理論

1.1 WSN定位算法

1.1.1 DV-Hop定位算法

DV-Hop算法作為WSN中一種經(jīng)典的分布式定位方法,主要由以下幾個定位階段組成。首先,錨節(jié)點借助泛洪廣播向網(wǎng)絡中的其他節(jié)點發(fā)送自身節(jié)點的位置和跳數(shù)等信息,泛洪廣播完成后,每一個節(jié)點會獲取到與錨節(jié)點的最小跳數(shù)。當每個錨節(jié)點均接收到與所有其他錨節(jié)點間的距離和跳數(shù)信息時,需要計算錨節(jié)點間的平均跳距hopsize。未知節(jié)點k到錨節(jié)點i間的距離dk,i則根據(jù)錨節(jié)點的平均跳距hopsizek與最小跳數(shù)hk,i的乘積來計算,并使用最小二乘法來估計未知節(jié)點的坐標。

1.1.2 Centroid定位算法

Centroid定位算法主要通過求解多邊形的質(zhì)心來確定未知節(jié)點的位置,確定質(zhì)心的方法如下:假設某區(qū)域內(nèi)一共存在M個節(jié)點,其中錨節(jié)點有N個,未知節(jié)點有(M-N)個,M個節(jié)點的位置用坐標(xi,yi)表示,其中,i∈(0,1,…,M)。在通信半徑能夠輻射的范圍內(nèi),各錨節(jié)點周期性地向周圍其他節(jié)點廣播含自身位置的分組信息,當某節(jié)點接收到一定量信息后,計算由接收到的錨節(jié)點組成的多邊形的質(zhì)心,并用坐標表示,完成Centroid定位。

1.2 廣義回歸神經(jīng)網(wǎng)絡

廣義回歸神經(jīng)網(wǎng)絡(GRNN)屬于徑向基函數(shù)網(wǎng)絡的一種改進模型,在非線性回歸分析領域有很強的數(shù)據(jù)處理能力。它的結(jié)構(gòu)模型主要包括輸入層、模式層、求和層以及輸出層這四層。如圖1所示,輸入層向量X=[x1,x2,…,xm]Τ,輸出層向量Y=[y1,y2,…,yn]Τ,不同層的各個節(jié)點之間都有相應的網(wǎng)絡參數(shù)連接。GRNN具有和徑向基函數(shù)網(wǎng)絡相似的輸入層與模式層,模式層包含多個神經(jīng)元,其數(shù)量和學習樣本量相同。在求和層中含有兩類不同功能的神經(jīng)元,作用分別是對模式層中神經(jīng)元的輸出進行算術(shù)求和以及加權(quán)求和。GRNN復雜的神經(jīng)網(wǎng)狀結(jié)構(gòu)具有比徑向基函數(shù)網(wǎng)絡更好的運算速度和預測效果。

圖1 GRNN結(jié)構(gòu)模型

在GRNN模式層中,神經(jīng)元之間的傳輸函數(shù)Pi可以用式(1)表示:

其中,X表示輸入變量;Xi表示第i個神經(jīng)元指向的學習樣本;σ表示光滑因子;i=1,2,…,m。

經(jīng)過GRNN求和層中兩類求和方法求解后,在輸出層利用求和結(jié)果相除的方法輸出預估結(jié)果的第j個元素yj,具體見式(2):

其中,yij表示連接權(quán)值,對應于第i個輸出樣本Yi中第j個數(shù)值;j=1,2,…,n。

1.3 麻雀搜索算法

麻雀搜索算法(SSA)最早于2020年提出,是一種較新的智能優(yōu)化算法。該算法是從麻雀這種鳥類的覓食、反捕食活動中獲得的靈感,該算法中的種群,是由搜尋者和跟隨者組成,通過搜尋者不斷尋覓食物,逐漸指引跟隨者前進,算法的尋優(yōu)效果好,收斂速度快。

假設一個麻雀種群包含n只麻雀,覓食空間大小為d維,在搜尋者尋覓食物的過程中,其位置也在不斷更新,具體更新方法見式(3):

跟隨者的位置更新方法見式(4):

SSA需要選擇10%～20%的麻雀來勘察預警,以便隨時進行反捕食活動,從而保證麻雀種群的安全。預警者的位置更新方法見式(5):

2 本文優(yōu)化方法

本文的優(yōu)化方法主要從兩個方面展開,分別是對傳統(tǒng)定位方法的改進和使用優(yōu)化的神經(jīng)網(wǎng)絡預測節(jié)點的最終位置。將DV-Hop和Centroid這兩種算法和加權(quán)定位求解思想進行融合,修正DV-Hop算法的跳距和Centroid算法的質(zhì)心等信息,把節(jié)點融合特征引入GRNN中進行網(wǎng)絡訓練,并利用改進的SSA優(yōu)化GRNN進行定位,以更大程度地減少定位誤差。

2.1 平均跳距修正

在傳統(tǒng)的DV-Hop定位算法中,通常使用錨節(jié)點坐標間的歐氏距離與最小跳數(shù)的商計算平均跳距,使得最終預測的節(jié)點位置誤差較大。本文利用加權(quán)平均思想,結(jié)合文獻[9]和文獻[10]提出的方法修正跳距,以綜合考慮節(jié)點平均跳距對定位精度的影響。

假設錨節(jié)點個數(shù)為n,根據(jù)最小均方誤差原則,錨節(jié)點i的平均跳距hopsizei的計算方式如下:

其中,hopij表示錨節(jié)點間最小跳數(shù);dij表示錨節(jié)點間的距離。

跳距校正系數(shù)εi則根據(jù)錨節(jié)點間的估算距離和實際距離的差值與跳數(shù)進行相應計算得到,具體可按式(8)計算:

那么,經(jīng)修正后的錨節(jié)點平均跳距可表示為:

對于未知節(jié)點而言,在計算平均跳距時,通過添入加權(quán)因子來修正跳距權(quán)重:

其中,hopi和hopj表示單個錨節(jié)點i、全部錨節(jié)點(j=1,2,…,n)分別和未知節(jié)點間的跳數(shù)。

2.2 質(zhì)心修正

為了解決傳統(tǒng)Centroid定位方法存在的誤差,通過獲取節(jié)點接收的RSSI信號強度指示這一重要指標,進而對質(zhì)心進行修正。

RSSI具有操作方便、 通信損耗較少等優(yōu)點,信號發(fā)送方i和接收方j之間的RSSI值Pdij滿足關系式:

其中,dij表示信號發(fā)送方、接收方間的端距;d0表示信號參考距離;n表示路徑衰減指數(shù);Xσ表示隨機分布的高斯噪聲。

傳統(tǒng)的三角形Centroid定位方法原理如下:假設三個錨節(jié)點坐標分別為A1(x1,y1)、A2(x2,y2)、A3(x3,y3),未知節(jié)點坐標為O(x,y),以三個錨節(jié)點位置為圓心,對應距離為半徑,形成三個圓及其重疊部分。連接重疊部分的三個交點O1(xo1,yo1)、O2(xo2,yo2)、O3(xo3,yo3),形成一個三角形,計算該三角形的質(zhì)心坐標M1(xm1,ym1)即可,如式(12)所示。

文獻[11]提出的改進加權(quán)Centroid定位方法能夠有效提升定位精度。在定位之前,首先對節(jié)點收到的RSSI值預處理,本文采用高斯濾波平滑處理RSSI值,并作為新的RSSI值估測錨節(jié)點與未知節(jié)點的距離,相比于文獻[11]采用的中值濾波處理誤差更小。

未知節(jié)點在收到新的預處理RSSI值后,需要對RSSI值計算得到的距離進行升序排序,取排序前三的距離來選擇合適的錨節(jié)點,并引入差分修正因子α,如式(13)所示。

其中,N表示與未知節(jié)點同在通信范圍中的錨節(jié)點個數(shù);di表示錨節(jié)點和未知節(jié)點的間距;d1i表示錨節(jié)點和質(zhì)心的間距。

2.3 ISSA-GRNN算法

2.3.1 拉丁超立方體初始化種群

運行SSA算法時,對麻雀種群初始化是必不可少的。通常情況下,會采取隨機產(chǎn)生種群的方式初始化,這樣可能導致無法充分覆蓋解空間,從而影響種群個體分布均勻程度和收斂效果等。采用拉丁超立方體抽樣(latin hypercube sampling,LHS)[15]初始化SSA種群,在執(zhí)行LHS過程時,需要確定一個抽樣規(guī)模,將每一維的變量分割成多個同等小區(qū)間,將大超立方體變?yōu)樾〕⒎襟w。之后,產(chǎn)生一個全排列的矩陣,并最終進行采樣。通過整體空間覆蓋及抽樣非重疊,以提升SSA的種群多樣性和尋優(yōu)性能。

2.3.2 交叉驗證法處理網(wǎng)絡向量

在運行GRNN模型時,采用交叉驗證法(Cross Validation)[16]驗證網(wǎng)絡算法的性能,將GRNN的網(wǎng)絡向量值按組劃分,形成訓練集及其測試集以多次訓練和評估算法模型。在仿真實驗中,網(wǎng)絡向量值對應于傳感器中的不同節(jié)點信息,最終使預測模型更有效、更精確。交叉驗證過程圖2所示。

圖2 交叉驗證過程

2.3.3 ISSA-GRNN算法流程

為了盡可能消除GRNN初始網(wǎng)絡調(diào)節(jié)參數(shù)對定位實驗的影響,不斷提高定位精度,提出的基于ISSA和GRNN的節(jié)點特征融合定位優(yōu)化方法步驟如下:

(1)初始化WSN環(huán)境,確定網(wǎng)絡區(qū)域,布置網(wǎng)絡節(jié)點。利用加權(quán)定位思想修正DV-Hop算法中的跳距和Centroid算法中的質(zhì)心等特征。

(2)建立GRNN網(wǎng)絡模型,對GRNN中的網(wǎng)絡調(diào)節(jié)參數(shù)進行編碼,其編碼長度作為SSA種群大小。

(3)使用LHS初始化種群,對種群規(guī)模、迭代次數(shù)等參數(shù)進行設定,并生成適應度函數(shù)。

(4)將傳感器節(jié)點修正后的跳距、質(zhì)心等特征和節(jié)點其他重要特征相融合,作為GRNN的輸入向量進行訓練、測試,節(jié)點真實坐標作為訓練、測試的輸出值。

(5)對SSA的適應度值排序,得到當前最佳個體位置以及最差個體位置。

(6)迭代更新種群位置、適應度值,保存更新后的種群信息。

(7)判斷是否達到SSA的終止條件,若達到,則輸出最優(yōu)解,轉(zhuǎn)到(8),否則轉(zhuǎn)到(6)。

(8)解碼最優(yōu)解,并作為更新后GRNN中的網(wǎng)絡調(diào)節(jié)參數(shù)。

(9)重新訓練、測試GRNN,最終得到未知節(jié)點的預測坐標。

3 實驗仿真與分析

使用Matlab仿真軟件進行算法實驗,綜合比較了ISSA-GRNN算法與改進跳距的IDV-HOP算法、文獻[8]的RDV-HOP算法和文獻[9]的ISSADV-HOP算法。定位實驗模擬了一個100 m×100 m的區(qū)域,該區(qū)域隨機分布著若干個錨節(jié)點和未知節(jié)點,錨節(jié)點數(shù)量占比的設置范圍為10%～35%,總節(jié)點個數(shù)的設置范圍為50～300,通信半徑的設置范圍為20～45 m。SSA的麻雀種群個數(shù)為100,迭代次數(shù)為200。采用如下方法量化未知節(jié)點定位誤差:

3.1 通信半徑對節(jié)點定位的影響

圖3為不同定位算法在通信半徑的影響下其定位誤差的對比情況。設置總節(jié)點數(shù)為100、錨節(jié)點數(shù)為30,通信半徑不斷改變。伴隨通信半徑不斷增加,受到錨節(jié)點平均跳距產(chǎn)生的影響,使得各算法的整體定位誤差在逐漸減小并趨于平穩(wěn)。由表1可知,ISSA-GRNN算法的平均定位誤差相比于其他三種算法分別減少了70.2%、64.5%和26.4%。

圖3 通信半徑對節(jié)點定位的影響

表1 通信半徑影響下的平均定位誤差對比

3.2 錨節(jié)點數(shù)對節(jié)點定位的影響

圖4為不同定位算法在錨節(jié)點數(shù)的影響下其定位誤差的對比情況。設置總節(jié)點數(shù)為100、通信半徑為30 m,錨節(jié)點數(shù)量不斷按比例改變。隨著錨節(jié)點比例逐漸提高,各算法的整體定位誤差均在逐漸減小,這是因為在錨節(jié)點增多的同時,也使得節(jié)點跳距估計更加準確、最小跳數(shù)更加貼近WSN的真實程度。由表2可知,ISSA-GRNN算法的平均定位誤差相比于其他三種算法分別減少了68.8%、64.1%和27.7%,穩(wěn)定程度也更好。

圖4 錨節(jié)點數(shù)對節(jié)點定位的影響

表2 錨節(jié)點數(shù)影響下的平均定位誤差對比

3.3 總節(jié)點數(shù)對節(jié)點定位的影響

圖5為不同定位算法在總節(jié)點數(shù)的影響下其定位誤差的對比情況。設置錨節(jié)點比例為0.3、通信半徑為30 m,總節(jié)點數(shù)不斷改變。當總節(jié)點數(shù)逐漸增多時,WSN區(qū)域連通性也在不斷增強,因此保存了更多的節(jié)點定位信息,使得定位誤差不斷減少。由表3可知,ISSA-GRNN算法的平均定位誤差相比其他三種算法分別減少了73.0%、64.8%和21.4%。

圖5 總節(jié)點數(shù)對節(jié)點定位的影響

表3 總節(jié)點數(shù)影響下的平均定位誤差對比

總之,本文提出的ISSA-GRNN算法定位效果更穩(wěn)定、定位精度更高。

4 結(jié) 論

本文主要提出了一種ISSA和GRNN結(jié)合的優(yōu)化算法定位WSN未知節(jié)點的位置。首先利用LHS初始化SSA種群,然后優(yōu)化GRNN的網(wǎng)絡參數(shù),將加權(quán)修正后的節(jié)點跳距和質(zhì)心等重要特征相互融合作為GRNN的輸入向量訓練網(wǎng)絡,并使用交叉驗證法處理網(wǎng)絡向量值。與其他算法對比的仿真實驗結(jié)果表明,該優(yōu)化算法有著較好的定位效果,其定位誤差明顯小于其他定位算法,增加了節(jié)點定位的準確程度。在今后的研究中,可以考慮將此類優(yōu)化算法應用于三維空間或動態(tài)網(wǎng)絡中實現(xiàn)WSN節(jié)點定位,不斷拓展其綜合應用范圍。