基于改進SSA的DV-Hop傳感器定位算法

劉瑞興,段中興

(西安建筑科技大學 信息與控制工程學院， 西安 710055)

1 引言

無線傳感器網絡(WSN)是當今物聯網領域的研究熱點，它由多個具有數據采集、分析和處理能力以及信息發送和接收能力的微型傳感器節點組成。由于WSN中傳感器節點的部署位置可以隨時改變，靈活的對某些特定區域進行實時監測，在實際中如森林火災預警、天然氣管道泄漏、國防安全保衛工作等諸多領域得到了廣泛應用。多數的WSN應用需要獲得節點的位置信息，不含位置信息的數據往往是無用的。因此，WSN技術中節點定位問題成為了重點研究內容。WSN中傳感器節點定位技術分為兩類：第一類基于測距，定位精度高，目前該類型的方法主要有TOA、TDOA、RSSI等；第二類非測距，不需要進行實際物理測量，主要方法有Centroid，Amorphous，DV-Hop等，缺點是定位精度較低。其中，DV-Hop算法作為目前應用較廣的定位算法之一，算法功耗小且適應性較強等特點可以滿足大部分實際應用的定位需求，得到更多的研究。

傳統的DV-Hop定位算法精度較低，研究學者對DV-Hop改進思路有2種：修正節點間的最小跳數和平均跳距；優化未知節點的位置。文獻[10]引入遺傳算法(GA)對跳數信標節點加權處理優化平均跳距，但是定位精度提升不足；文獻[11]引入多通道半徑細化節點間的最小跳數，提高定位精度，但是信標節點的多次廣播加劇了傳感器的能量消耗；文獻[12]采用多通信半徑方式和距離誤差和跳數歸一化優化最小跳數和平均跳距，并利用改進蝙蝠算法(BA)定位未知節點，提高了算法定位精度，但是增加了算法的復雜度，收斂速度變慢；文獻[13]將斯蒂芬森迭代模型與傳統的DV-Hop算法相融合，利用DV-Hop算法粗定位結果作為初值帶入史蒂芬森模型得到最優估計位置，提高了算法精度，加快收斂速度，但是該算法僅僅針對DV-Hop的第3階段進行改進，有很大的提升空間。針對上述研究存在的問題，提出一種基于改進SSA的DV-Hop傳感器定位算法來提高定位精度。

2 DV-Hop算法誤差分析與改進

2.1 傳統DV-Hop算法原理

DV-Hop算法由Niculescu等提出，具體過程可以分為3個階段：

第1階段：信標節點通過泛洪向WSN網絡中廣播自身信息如圖1所示，接收節點將收到的信息自建表格記錄并根據廣播不斷更新表格，泛洪結束得到所有節點到信標節點的最小跳數。

第2階段：利用式(1)計算出信標節點間的平均跳距。

(1)

式中: (,),(,)是信標節點的坐標；是信標節點,之間的跳數。未知節點將接收到第一個平均跳距信息作為自己的平均跳距，并通過式(2)計算其到信標節點的距離。

=×

(2)

第3階段：采用最小二乘法計算未知節點的位置坐標。

信標節點編碼信標節點坐標(x,y)跳數h

2.2 DV-Hop算法誤差來源

DV-Hop算法誤差主要來自以下3個方面：

1) 針對算法第1階段進行分析，發現跳數是通過節點間的通信來完成的，相鄰節點間相互感知到，即跳數為1，定義1跳的距離為通信半徑。如圖2(a)所示，跳數為1的實際距離明顯不是通信半徑，這樣選擇就會造成引入跳數誤差。圖中信標節點能與節點、、、進行通信，=1,=1,=1,=2，但是、、的距離相差較大，之間跳數記作2，對信標節點平均跳距影響較大，這種計算跳數的機制導致產生誤差。

2) 平均跳距的選擇不能通過單一的信標節點反應實際現象，這樣選擇忽略了其他信標節點的信息，在異構網絡中，未知節點的選擇不能反應真實的跳距。

3) 最小二乘法估計未知節點的位置會帶來累計誤差。

圖2 多通信半徑跳數計算示意圖Fig.2 Multi-communication radius hop calculation

2.3 最小跳數修正

誤差分析可以看出，節點之間的距離遠近不同，只有將通信半徑分級細化，才能更好地精確跳數。因此，提出了一種多通信半徑優化節點間的跳數值。

如圖2(b)所示建立模型，假設網絡中信標節點通信半徑為，將節點間劃分級，網絡中節點實際距離為，跳數記作,∈[1,]。

如式(3)所示，取=40,=4，如圖2(c)所示=14,=12,=34,=1,=+=54，鄰近信標節點跳數值是精確的小數，細化了跳數值提高跳數的準確性，減小定位誤差。

(3)

最小跳數修正算法流程如下：

輸入：設定,值，令=1；

輸出：信標節點、未知節點最小跳數。

Begin

初始化網絡；

For=1:

利用式(3)更新廣播半徑；

信標節點以()為半徑通過泛洪向WSN網絡中廣播自身信息，接收節點將收到的信息自建表格記錄，若沒有則接收，但不轉發；

=+1；

if>

break；

信標節點以為半徑通過泛洪向WSN網絡中廣播自身信息，接收節點將收到的信息自建表格記錄，最后將跳數值加1轉發到網絡中；

end

End

通過多次仿真實驗得出∈[2,5]之間比較合適。值過大導致泛洪廣播會極大消耗節點的能量，減少網絡壽命，值過小導致跳數誤差大，所以綜合考慮節點定位精度與壽命，仿真實驗將選用=4作為通信半徑用來分級廣播。

誤差分析可以看出，節點之間距離遠近不同，只有將通信半徑分級細化，才能更好的精確跳數。

2.4 平均跳距校正

DV-Hop算法的誤差主要是由于信標節點的平均跳距不準確造成的，提出采用加權平均值對信標節點平均跳距誤差進行校正。具體流程如下：

Step 1 初始化網絡中設定信標節點的數目；計算網絡中所有信標節點的平均跳距記作，計算方式如式(4)所示：

(4)

Step 2 誤差1通過第2階段信標節點平均跳距與步驟1中的計算，如式(5)所示：

1=(-)

(5)

(6)

Step 4 全面考慮信標節點的誤差來源，將Step 2、Step 3計算出的誤差系數利用式(7)計算作為其余信標節點的權值。

(7)

Step 5 再次計算信標節點的平均跳距，計算信標節點的平均跳距方案如下：

1) 信標節點,兩節點間的平均跳距為如式(8)所示。

(8)

2) 修正信標節點的平均跳距是信標節點與其余個信標節點的平均跳距加權，=1,2,…,-1，表示信標節點的權值，具體如式(9)所示。

(9)

2.5 建立目標函數

根據第1、2階段得到的估計距離，將定位問題轉化為求解坐標方程如式(10)所示：

(10)

式中:,,…,表示未知節點(,)與信標節點(,),(,),…,(,)之間的距離。第1、2階段的測距誤差為,,…,要求解未知節點(,)，只須使式(11)中的(,)最小，得到的誤差值將最小。(,)可以被看作非線性函數進行求解:

(11)

非線性優化問題中，首先需要建立一個目標函數來求解。本文中目標函數如式(12)所示:

(12)

式中：為麻雀個體的適應度值；(,)為未知節點位置；(,)為信標節點的位置；為兩者之間的距離。

3 改進麻雀搜索算法

3.1 麻雀搜索算法

麻雀搜索算法(SSA)是一種模擬麻雀種群覓食、逃避捕食者行為的啟發式算法，基本思想：初始化種群數量為存在于維搜索空間的麻雀種群，則=[1,2,…]，=1,2,…,=1,2,…，表示第只麻雀在維搜索空間中的位置。

麻雀群體中發現者起主導作用，引領種群不斷探索尋找食物，位置更新如式(13)所示：

(13)

跟隨者依托發現者尋找食物，并可能和發現者爭奪食物，提高自己捕食率，其位置更新如式(14)所示：

(14)

假設預警者約占麻雀種群的10～20，初始位置隨機，則位置更新如式(15)所示:

(15)

3.2 改進麻雀搜索算法

3.2.1 精英反向學習策略

反向學習是Tizhoosh等在2005年提出的，通過研究得到反向解有時比原始解更能得到種群的最優值。精英反向學習是針對反向學習策略生成的反向解不一定比原始解更容易搜索到全局最優解這一問題提出的。

(16)

(17)

使用精英反向解對麻雀種群進行初始化時，對于原始麻雀目標函數值小于反向解麻雀，若對其反向區域進行搜索，降低種群的收斂速度。因此，文中將精英反向學習策略引入到SSA對DV-Hop定位算法進行優化，將原始麻雀與反向解麻雀的適應度值相對比，保留種群較優的麻雀個體可以擴大種群的搜索范圍，避免盲目搜索也提高了算法的收斂速度。

3.2.2 發現者-跟隨者自適應調整

原始SSA算法中，發現者和跟隨者的數目比例是恒定的，這將導致在種群迭代前期，發現者的數目相對較少，缺乏引導種群全局探索的能力；后期，跟隨者數目較少，缺少精確局部搜索的能力。因此，文中提出發現者-跟隨者自適應調整策略，算法在開始階段，擁有較多的發現者，隨著迭代次數的增加，發現者的數目自適應減少，跟隨者的數目增多，逐步從全局搜索轉為局部精確搜索，從整體上提高算法的收斂精度。發現者和跟隨者數目調整如式(19)、式(20)所示。

(18)

=·

(19)

=(1-)·

(20)

其中：為發現者數目；為跟隨者數目；為比例系數，用于控制發現者和跟隨者之間的數目；為擾動偏離因子，對非線性遞減的值進行擾動；∈(0,1)的隨機數。

323 柯西變異擾動策略

柯西變異取自連續型概率的柯西分布，主要特點為零處峰值較小，峰值到零值下降緩慢，使變異范圍更均勻。變異如式(21)所示：

()=(1+tan(π(-05)))·

(21)

式中：為原來個體位置，()經過柯西變異后的個體位置，∈(0,1)隨機數。

3.3 ISSADV-Hop算法流程

ISSADV-Hop算法是針對傳統DV-Hop算法精度不高提出的，引入多通信半徑優化節點間的跳數值；同時使用誤差加權平均值，修正原始跳距；最后使用ISSA對未知節點進行定位。ISSADV-Hop具體算法實現流程：

1初始化網絡區域，節點總數、信標節點和未知節點數目，隨機初始化節點位置，通信半徑，初始跳數=0，循環次數；

2利用改進后DV-Hop算法得到最小跳數和平均跳距，然后按照式(2)計算出未知節點到信標節點之間的距離；

3麻雀種群初始化，確定種群數量，設置迭代次數，安全閾值，比例系數，擾動偏離因子，以及種群的搜索范圍和維數；

4引入精英反向學習策略初始化種群麻雀個體的位置，根據式(16)、式(17)按照要求對種群進行反向求解，進行適應度值的比較篩選出精英種群；

5根據式(19)、式(20)計算發現者和跟隨者數量；

6根據式(13)～式(15)更新發現者、跟隨者和警戒者位置；

7位置更新后，對種群加入柯西變異擾動，根據式(21)計算出擾動后麻雀的適應度值與前者比較，保留適應度值低的麻雀種群，然后記錄當前種群的最優個體的位置；

8循環步驟5、6、7直到達到，得到麻雀種群中全局最優位置，也就是未知節點的近似位置。

ISSADV-Hop算法流程如圖3所示。

圖3 ISSADV-Hop算法的流程框圖Fig.3 ISSADV-Hop algorithm flow

4 實驗與結果分析

4.1 實驗環境與參數設置

對ISSADV-Hop算法進行仿真和測試，實驗環境在MATLAB2018b上運行。應用文中算法與傳統DV-Hop算法相互之間進行比較，實驗使用系統Window10，CPU：i5-6300U @ 2.40 GHz，RAM：4 GB，實驗網絡環境參數和ISSA參數初始值的設置見表1和表2。

表1 實驗網絡環境參數Table 1 Network environment construction

表2 ISSA參數初始值Table 2 The initial values of the parameters of ISSA

如式(22)所示，實驗本身存在偶然性，為了減小誤差，文中將實驗重復200次計算平均值來得到最終結果。

(22)

式中：(,),(′,′)分別表示未知節點原始位置和實驗定位出來的位置，表示實驗使用的未知節點的數目，表示通信半徑。查閱能耗資料，設定通信半徑為30 m，節點數目設為100個，信標節點設為30個，與DV-Hop算法進行比較，進行200次仿真實驗結果對比，結果如圖4所示。

通過傳統DV-Hop算法與文中提出ISSADV-Hop算法在相同實驗條件下進行計算，圖4(a)為節點初始化分布圖；圖4(b)為DV-Hop算法誤差圖，可以看出偏差大；圖4(c)為本文中ISSADV-Hop算法定位出實際位置和估計未知的數據，可以清楚的看到改進后算法定位精度有大幅度提升；圖4(d)為循環200次的誤差，可以清楚的看到原始算法定位誤差在0.3019，改進后算法精度保持在0.105 5，相比于改進前歸一化定位誤差降低了19.64%，定位精度有顯著的提升。

為了進一步研究參數不同對定位精度的影響，將文中改進算法與DV-Hop、SSADV-Hop和IGWODV-Hop三種算法相對比進行仿真，通過改變通信半徑、節點數量和信標節點數分別進行實驗驗證。

圖4 節點初始化ISSADV-Hop、DV-Hop誤差與迭代200次誤差圖Fig.4 ISSADV-Hop and DV-Hop error comparison

4.2 通信半徑的影響

實驗中部署節點數量為100個，信標節點數為30個，通信半徑設置為20～50 m。實驗結果如圖5所示，隨著網絡中通信半徑的增大可以提高算法的定位精度，通信半徑的增加一定程度上可以為網絡中傳感器之間進行信息交流，改善網絡中傳感器的定位精度。與DV-Hop、IGWODV-Hop、SSADV-Hop算法相比，ISSADV-Hop算法歸一化定位誤差分別降低了7.54%、12.77%和5.48%。

圖5 變通信半徑對定位精度的影響曲線Fig.5 The influence of variable communication radius on positioning accuracy

4.3 節點數量的影響

實驗中保持節點通信半徑30 m不變，信標節點比例設為30%，節點數量設置在50～300個之間。從圖6可以看出，增加節點數量可以改善網絡的連通信，改善網絡中傳感器的定位精度。與DV-Hop、IGWODV-Hop、SSADV-Hop算法相比，ISSADV-Hop算法歸一化定位誤差分別降低了22.89%、14.46%和8.51%。

圖6 變節點數目對定位誤差的影響曲線Fig.6 The effect of changing the number of nodes on positioning error

4.4 信標節點的影響

實驗中保持節點通信半徑30 m不變，節點數量設置為100個之間信標節點數為10～40個。實驗結果如圖7所示，隨著信標節點數量的不斷增加提高了算法精度，這是由于信標節點數的增加精確了信標節點平均跳距。與DV-Hop、IGWODV-Hop、SSADV-Hop算法相比，ISSADV-Hop算法歸一化定位誤差分別降低了20.06%、12.95%和6.81%。

圖7 變信標節點對定位誤差的影響曲線Fig.7 The influence of variable beacon nodes on positioning error

4.5 定位耗時

實驗構建過程，先通過跳數值和平均跳距的優化。然后使用精英反向學習構建麻雀種群、自適應策略以及添加擾動優化麻雀搜索算法來定位未知節點?？梢园l現計算量的增加主要是由于無線傳感器網絡中節點數量確定。

選取100 m×100 m的網絡區域，通信半徑為30 m，信標節點的比例為30%，節點數量設置在50～200個之間，迭代100次。本文算法與DV-Hop、SSADV-Hop和IGWODV-Hop三種算法相對比進行仿真，仿真消耗時間如表3所示。

表3 不同節點數量中4種算法的平均定位時間Table 3 Average positioning time of 4 algorithms in different numbers of nodes

表3中數據可以看出，節點數量和運行時間基本成比例上升。在物聯網應用領域中，無線傳感器一般都有較強的壽命更換周期較長，剛安裝完畢也需要調試，所以文中提供的定位算法消耗的時間在可以承受范圍內。而且，雖然文中提出的算法運行時間較長，但ISSADV-Hop算法極大的提升定位精度，這在定位算法評價指標中起著決定性的作用。

5 結論

利用提出的多通信半徑方式優化節點間的跳數值，使跳數值更加精確；采用加權平均值校正平均跳距的誤差。使用改進后的麻雀搜索算法對未知節點的位置進行估計，并優化了DV-Hop算法的總體框架，減小位置偏差提升定位精度。采用具體的仿真實例，與傳統DV-Hop平均值比較精度有較大提高。

通過改變實驗參數中不同因素對實驗精度的影響，比傳統的DV-Hop、SSADV-Hop和IGWODV-Hop算法更有效提升了定位精度。對比上述4種算法的定位耗時，文中提出的改進算法增加了一定的運行定位時間，后期研究工作將重點關注降低算法計算量和復雜度。