一種基于麻雀算法的優化DV-Hop定位算法

陸 霞,張國華,葉 苗,孫國福

(南京師范大學 泰州學院 信息工程學院,江蘇 泰州 225300)

0 引言

無線傳感網(Wireless Sensor Network, WSN)是由大量傳感器節點構成的自組織無線通信網絡,在農業、軍事、醫療等領域廣泛應用[1]。目前,傳感器節點定位算法的研究主要集中在距離式定位和非距離式定位兩個方面[2],RSSI,AOA,TOA等屬于距離式定位算法[3];CL,APIT,DV-Hop等屬于非距離式算法。其中,DV-Hop算法簡單,運行開銷低,當節點獲取到3個及以上信標節點位置信息后就可以實現定位,使用較為普遍,但是對未知節點位置判斷存在定位誤差大、時間開銷大等問題。

近年來,種群智能優化算法成為許多領域的研究熱點,很多學者以此為契機針對DV-Hop算法提出了較多改進措施。林鳳德等[4]在算法中引入遺傳變異算子在種群中進行全局搜索,再使用蟻群算法進一步搜索,保留最優個體,算法提升了DV-Hop的定位精度,但仍有提升空間。石琴琴等[5]使用相似路徑搜索算法估算節點跳距,并使用灰狼算法進一步修正跳距值,提升了DV-Hop算法的定位精度,但收斂性還有待進一步提高。麻雀搜索算法(Sparrow Search Algrithm,SSA)是一種新型的種群智能優化技術,相比較其他群體智能優化算法具有結構簡單、速度快、易于擴充等優勢[6]。本文提出的基于麻雀算法的DV-Hop優化定位算法具備更強的搜索能力,更快的收斂速度,即使在節點分布不均的WSN中,也能優化DV-Hop算法中未知節點坐標,進而提升定位精度。

實驗結果對比分析,通過改變信標節點數量、通信半徑、種群數量和迭代次數等條件,本文提出的優化算法相較于經典DV-Hop算法,在定位精度和收斂性能上有了顯著提升。

1 DV-Hop算法分析

DV-Hop算法不使用直接測距的方法進行定位,而是借鑒了計算機網絡中基于距離向量的路由機制,具體原理如圖1所示。DV-Hop算法主要包含3個步驟。

圖1 DV-Hop算法原理

(1)信標節點將包含自身信息的分組(包含編號、位置、到其他節點的跳數等)向鄰居節點進行廣播。通過廣播所有節點不僅可以獲取信標節點的位置,還能確定和信標節點之間的最小跳數。

(2)估算未知節點和信標節點間的距離。信標節點利用第一階段中獲取到的最小跳數,結合其他信標節點的位置,估算自身每跳的距離Hopi,再將包含跳距的信息分組廣播轉發給鄰居節點,未知節點將收到信標節點的跳距乘以最小跳數,估算到各個信標節點之間的距離dij。

式中:(xi,yi)(xj,yj)是信標節點i和j的坐標,M是信標節點總數,hij是信標節點i與j(i≠j)之間的跳段數。

式中:Hopi是距離未知節點i最近的信標節點每跳的距離,hij是未知節點i與信標節點j之間的最小跳數。

(3)當未知節點獲取到3個以上信標節點的距離數據,使用式(3)三邊測量法估算未知節點的位置坐標[7]。

式中:(x,y)表示待估算的未知節點坐標,(xi,yi)表示信標節點坐標(i=1,2,…n),di表示未知節點和信標節點之間的距離。

通過上述對DV-Hop算法的描述發現,該算法實現容易、成本較低。但無線傳感網中,傳感器節點分布不均,且每個節點擁有的能量不等,DV-Hop算法也存在2個主要不足。

(1)算法實現過程中需要進行2次洪泛廣播,第1次是未知節點從信標節點獲取最小跳數和位置信息;第2次是信標節點告知估算得到的自身跳距。每次洪泛廣播中,絕大部分節點都將參與其中,容易造成節點能量的浪費,增加無線傳感網的能耗開銷。

(2)誤差的積累會造成未知傳感器節點定位精度的降低。誤差主要由2方面原因構成:①使用Hopi估算信標節點每跳的跳距,計算結果存在誤差,進而使得求解未知節點距離信標節點的距離dij也存在誤差。②在算法的第3個階段,未知節點至少收到3個信標節點才能使用估算算法計算坐標,若信標節點組合中存在3點共線或近似共線問題,或者1個信標節點距離未知節點遠,另外,2個信標節點距離未知節點近,未知節點定位精度會受到很大影響甚至會出錯[8]。

2 基于麻雀算法的DV-Hop優化定位算法

DV-Hop算法中,根據第2階段估算得到的距離,可以得到未知節點位置和距離之間的滿足:

式中:δi表示誤差值(i=1,2,…n)。建立優化算法的目標是將δi降低到最小,那么優化定位算法需要解決的問題可以歸納為:

即求F(xi,yi)的最小值。

2.1 優化定位算法數學模型

麻雀喜歡群居,圈養麻雀主要包含2種身份:發現者(Producer)和跟隨者(Scrounger)。其中,發現者負責尋找食物并為整個種群提供覓食的區域和方向,跟隨者則是利用發現者獲取食物[6]。麻雀覓食過程使用“發現者-跟隨者”模型,每只麻雀在種群中可以使用位置屬性進行描述。

麻雀算法通過合適的迭代次數不斷更新搜索范圍,更新收斂最佳位置。麻雀覓食數學模型可以分為種群初始化、擴大覓食搜索范圍和覓食位置定位3個過程。

2.1.1 種群初始化

種群中麻雀個體數量為n,指定位置較好的m只麻雀為發現者,剩余的(n-m)只麻雀為追隨者,發現者數量變化范圍[ul,ur],確定最大迭代次數T。種群初始化位置公式為:

使用式(4)作為每只麻雀的適應度函數。

2.1.2 擴大覓食搜索范圍

發現者可以為種群覓食提供更大的搜索范圍,便于種群覓得更多的食物。每次迭代過程中,發現者位置更新公式為:

式中:t表示當前迭代次數,α表示[0,1]之間的隨機數。的更新參照式(7)計算。

2.1.3 覓食位置定位

覓食搜索過程中,跟隨者時刻監視發現者動向,當它們察覺到發現者找到更好的食物,則立即前往食物所在位置,爭奪發現者的食物。跟隨者位置更新公式為:

式中:xworst表示第t次迭代時麻雀的最差位置,xp表示發現者目前最佳位置,表示發現者在t+1次迭代的最佳位置,A+表示每個元素隨機賦1或-1的1×d的矩陣。當k＞時,表示第i個跟隨者沒有獲得食物,覓食失敗;當k≤時,表示第k個跟隨者已經到達最優位置xp附近。的更新參照式(8)計算。

2.2 優化定位算法描述

基于麻雀算法的DV-Hop優化定位算法主要包含以下步驟:

步驟1:根據式(3)和式(4)使用經典DV-Hop算法估算未知節點和信標節點之間的跳距。

步驟2:初始化麻雀算法的基本參數(發現者數量及變化范圍、種群數量、初始位置等),將未知節點周圍已知的信標節點坐標作為初始麻雀的基本位置信息,根據式(6)將適應度取值低的麻雀作為發現者。

步驟3:在既定的最大迭代次數范圍內,根據式(7)和式(8)不斷更新發現者和跟隨者的位置信息。

步驟4:在迭代過程中,若跟隨者位置連續多次無更新,需進行種群個體變異,重新選擇新的發現者繼續進行位置更新,否則轉步驟5。

步驟5:如果已達到最大迭代次數,輸出最佳位置,最佳位置即為優化后的未知節點坐標,算法結束,否則重復步驟3和步驟4。

改進后的DV-Hop優化定位算法流程如圖2所示。

圖2 DV-Hop優化定位算法流程

3 實驗結果與分析

3.1 實驗環境

為了驗證改進算法的定位精度,使用如表1所示的實驗平臺提供運行環境支持。假設所有傳感器節點結構相同,且區域內任意2個節點均可通信,仿真網絡環境參數設置如表2所示。以上述實驗環境和參數設置為依據,分別變換信標節點數量、通信半徑、種群數量和迭代次數,將DV-Hop算法、基于麻雀算法的DVHop算法(下文簡稱SSA DV-Hop)進行性能比對。采用平均相對定位誤差作為評定指標,計算公式為:

表1 實驗平臺配置

表2 仿真網絡環境參數設置

式中:N表示節點總數,M表示信標節點個數,(x,y)表示未知節點估算坐標信息,(x′,y′)表示未知節點實際坐標信息,R表示節點通信半徑。

3.2 定位精度對比

3.2.1 信標節點數量對定位精度的影響

如圖3所示在通信半徑為15 m,迭代次數為30次,信標節點數量由5個變化到30個的情況下,2種算法定位精度的表現,結果表明:隨著信標節點數量的增加,DV-Hop算法定位精度可以提高約34%,SSA DVHop算法定位精度提高約24%,SSA DV-Hop算法定位精度較高。

圖3 信標節點數量變化對定位精度的影響

3.2.2 通信半徑變化對定位精度的影響

如圖4所示在信標節點數量為15個,迭代次數為30次,通信半徑由15 m變化到30 m的情況下,2種算法定位精度的表現,結果表明:隨著通信半徑的增加,DV-Hop算法定位精度可以提高約23%,SSA DV-Hop算法定位精度提高約25%,SSA DV-Hop算法定位精度較高。

圖4 通信半徑變化對定位精度的影響

3.2.3 種群數量對定位精度的影響

如圖5所示在信標節點數量為15個,迭代次數為30次,通信半徑為15 m,種群數量由30個變化到80個的情況下進行仿真實驗。結果表明:隨著種群數量的增加,SSA DV-Hop算法定位誤差不斷降低,當種群數量大約達到40個時,SSA DV-Hop算法定位精度無顯著變化。

圖5 種群數量對定位精度的影響

3.2.4 迭代次數對定位精度的影響

如圖6所示結果表明:隨著迭代次數的增加,SSA DV-Hop算法定位誤差逐漸減低,迭代次數大約達到70次左右定位誤差無顯著變化,收斂速度較快。

圖6 迭代次數對定位精度的影響

4 結語

針對DV-Hop算法定位精度較低的不足,在分析麻雀算法原理的基礎上,將改進后的優化麻雀算法應用到DV-Hop算法中,實現了信標節點跳距的優化。仿真結果表明,在不增加額外網絡開銷的情況下,基于麻雀算法的優化DV-Hop定位算法能有效提高節點的定位精度。