基于IFOA優化DV—distance算法的無線傳感器網絡定位研究

龐先偉+左仁淑+王婷婷+李學軍

摘 要： 對無線傳感器網絡節點定位問題進行研究，提出一種基于IFOA優化DV?distance算法的WSNs定位方法。針對DV?distance算法定位精度低、噪聲影響大，受限于網絡拓撲結構等問題，將改進的果蠅優化算法（IFOA）引入到DV?distance設計中，實現了節點位置的精確定位，為進一步提高算法定位的精度，引入動態加權修正因子，并給出動態誤差修正策略，最后對WSNs節點定位問題進行實驗仿真，仿真結果表明，基于IFOA優化的DV?distance定位算法較DV?distance和傳統定位算法在定位精度上有明顯改善。

關鍵詞： 無線傳感器網絡； 節點定位； 果蠅優化算法； DV?distance

中圖分類號： TN911?34； TP393 文獻標識碼： A 文章編號： 1004?373X（2017）13?0022?04

Abstract： The node localization problem for wireless sensor networks （WSNs） is studied. A DV?distance algorithm based on fruit fly optimization algorithm for WANs localization is proposed. Since the DV?distance localization algorithm has the defect of low localization precision， is influenced by noise easily， and restricted to the network topology structure， an improved fruit fly optimization algorithm （IFOA） is introduced into the DV?distance algorithm to realize the accurate localization of the node position. In order to improve the algorithm localization accuracy further， the dynamic weighted correction factor is introduced into the algorithm， and the dynamic error correction strategy is given. The simulation experiment was performed for WSNs node loca?lization. The simulation results show that the positioning accuracy of the improved DV?distance localization algorithm is significantly improved than that of the DV?distance and traditional localization algorithms.

Keywords： wireless sensor network； node localization； fruit fly optimization algorithm； DV?distance

0 引 言

隨著無線通信技術的不斷發展，無線傳感器網絡（WSNs）在火災、潮汐、環境監控、空間探索等領域得到了廣泛應用[1]。傳感器節點位置定位作為WSNs關鍵技術之一[2]，具有十分重要的研究意義。常見的定位方法可以分為基于測距（range?based）的定位技術和無須測距（range?free）的定位技術兩大類[3]。RSSI（Received Signal Strength Indication）是典型的基于測距定位算法[4]，由于具有硬件成本低、容易獲取等特點，得到了廣泛應用，但是定位精度低、能耗相對較大。而無須測距定位算法應用較為廣泛的是DV?Hop算法[5]，其屬于自組織定位系統（Ad Hoc Positioning System，APS）范疇，具有算法簡單，易于實現等特點，但是對節點性能要求相對較高，精度受網絡拓撲結構影響較大[6]。

Badri Nath等學者在DV?Hop算法基礎上提出了 DV?Distance節點定位算法，其通過計算未知節點與信標節點間最小跳數路段距離的最大似然估計來實現節點位置定位，具有良好的擴展性，但是該算法對距離誤差比較敏感[7]，因此提高算法魯棒性和抗干擾性是當前研究的熱點之一。果蠅優化算法（Fruit Fly Optimization Algorithm，FOA）是一種新的演化式算法[8]，具有計算簡單、參數少、易于理解等優點，得到了越來越多學者的關注，然而對FOA在WSNs節點定位方面的研究相對較少。

本文將改進的果蠅優化算法（IFOA）應用到DV?distance節點定位過程，并引入動態加權修正因子，給出動態誤差修正策略，最后對WSNs節點定位問題進行實驗仿真，以驗證基于IFOA優化DV?distance算法的有效性。

1 DV?distance算法描述

設定存在如圖1所示的無線傳感器網絡，其中，由個信標節點組成的集合為；個未知節點組成的集合為。

DV?Distance算法定位過程可以描述為：

Step1： 獲取未知節點到信標節點之間的跳段距離。

依據距離矢量交換協議[9]，信標節點向鄰居節點廣播包含跳段和累計跳段距離（初始化均為0）的自身位置信息分組，接收節點在比較同一信標節點跳數值后，保留具有最小跳數的分組，同時更新跳段和累計跳段距離信息，并轉發給其他鄰居節點。通過該方法，所有未知節點獲取了到每個信標節點的最小跳數和路徑信息。如圖1所示，未知節點到信標節點，，，的最小跳數分別為2，1，2，3；對應的累計跳段距離可以表示為：

Step2： 未知節點位置確定。

當未知節點獲取到所有信標節點間的累計跳段距離后，可以利用最大似然估計或三邊定位方法來確定未知節點的位置信息。

通過分析DV?Distance定位過程，可以看出其存在的缺點主要有：

（1） 由于相鄰節點間的距離是通過RSSI測得，而RSSI測距技術受距離和環境影響較大，因此導致節點間距離測量精度存在較大誤差。

（2） DV?Distance采用未知節點與信標節點間的累計跳段距離替代歐式距離，隨著跳段數的不斷增加，導致與存在較大差距，從而導致算法定位精度并不高。

2 改進果蠅優化算法（IFOA）描述

2.1 基本果蠅優化算法（FOA）

果蠅優化算法基于模擬果蠅覓食生物學現象，通過動態調整嗅覺和視覺信息，實現向食物聚攏。FOA基本原理可以描述為：

Step1： 參數初始化。隨機生成規模為的果蠅種群，設置種群初始位置，算法最大迭代次數以及算法終止條件。

Step2： 嗅覺搜尋。根據式（1）初始化果蠅搜尋食物的方向和距離，即得到果蠅個體位置：

式中為隨機數。

Step3： 味道濃度判定值計算。根據式（2）計算果蠅的味道濃度判定值：

Step4： 味道濃度計算。根據式（3）計算果蠅的味道濃度：

式中為目標函數。

Step5： 視覺搜尋。保留種群歷史最佳味道濃度值其他果蠅個體利用視覺向具有最佳味道濃度值的位置飛去，即。

Step6： 終止條件判斷。重復執行Step2～Step5，直到滿足終止條件。

2.2 多子族群改進果蠅優化算法

FOA在迭代進化過程中，只保留歷史最佳個體相關信息，導致算法容易陷入局部最優，出現“早熟”現象，其根本原因在于群體樣本多樣性較差。為提高種群多樣性，提出子族群概念，果蠅種群按照一定規則劃分成規模相同的子族群，果蠅個體先在子族群進行局部搜索，然后將子族群最優信息在種群范圍內進行信息交流，最后再次進行子族群劃分，如此往復，從而有效地增加了種群樣本多樣性，避免了算法陷入局部最優。子族群劃分規則可以描述為：果蠅個體按照味道濃度依次排列，將種群劃分為規模相同的個子族群，第1個果蠅個體分入第1個子族群，第2個果蠅個體分入第2個子族群，第個果蠅個體分入第個子族群，第個果蠅個體分入第1個子族群，依次類推，直至子族群劃分完畢。

3 基于IFOA優化DV?distance算法實現

3.1 動態誤差修正策略

用累計跳段距離替代歐式距離是DV?Distance定位算法定位精度不高的主要原因之一，為此，采用式（4）對累計跳段距離進行動態修正[7]。

式中：為修正后累計跳段距離；為動態加權修正因子；表示未知節點到信標節點的跳數；表示未知節點到信標節點的總跳數；分別表示信標節點之間的歐式距離和累計跳段距離。

式（4）充分考慮了未知節點到信標節點，以及所有信標節點之間累計跳段距離和歐式距離比值對定位精度的影響，并根據跳數大小動態調整誤差修正比值。顯然，未知節點到信標節點跳數越多，帶來的誤差也就越大，使得修正比例也就越大；未知節點到信標節點跳數占信標節點間總跳數比值越大時，累計跳段距離誤差也就越大，其分配的比例權重也就越小。

3.2 基于IFOA優化DV?distance算法實現流程

目標函數：定義IFOA適應度函數為：

式中為信標節點的位置坐標。

從式（5）可以看出，IFOA最優解為到所有信標節點誤差最小的點，即定位測距誤差越小，定位就越精確。

基于IFOA優化DV?distance算法節點定位過程如圖2所示。

4 實驗仿真

在Matlab仿真平臺進行實驗仿真，設節點隨機分布在200 m×200 m的網絡中，未知節點和信標節點位置信息隨機產生，每個節點具有相同的通信半徑。IFOA參數設置如下：。本文在文獻[10]的基礎上給出歸一化平均定位誤差評價指標：

式中：為仿真實驗次數；為節點通信半徑（取）；為可定位節點數；，分別為位置節點真實坐標和算法求解所得坐標。

4.1 平均定位誤差與算法迭代次數的關系

為驗證基于IFOA優化DV?distance算法（IFOADV?distance）的有效性，設網絡中共有100個節點，信標節點比例為10%，分別取FOADV?distance，IFOADV?distance和文獻[11]提出的HABC算法進行仿真，圖3給出了三種算法平均定位誤差與算法迭代次數的關系。

從圖3可以看出，隨著迭代次數的不斷增加，三種算法定位誤差都接近于0，但是IFOADV?distance收斂速度明顯優于其他兩種定位算法，表明該算法具有很強的穩定性，在迭代次數大于40次時，該算法的歸一化平均定位誤差基本保持不變，而且具有很高的定位精度。

4.2 信標節點個數、網絡節點個數對算法定位精度的影響

為進一步分析算法定位精度與信標節點個數和網絡節點個數之間的關系，分別采取FOADV?distance算法，IFOADV?distance算法和HABC算法進行試驗，網絡節點總數為200個。圖4給出了信標節點個數與之間的關系，圖5給出了節點個數與之間的關系。

從圖4可以看出，在網絡節點數保持不變的情況下，三種算法的定位誤差隨著信標節點比例不斷提高而減小，并逐漸趨于穩定，而且IFOADV?distance算法的定位誤差要明顯優于其他兩種算法。從圖5可以看出，在信標節點數保持不變的情況下，三種算法的定位誤差隨著網絡節點數量的不斷提高而減小，并逐漸趨于穩定。同樣，IFOADV?distance算法的定位誤差要明顯優于其他兩種算法。仿真實驗結果證明了基于IFOA優化DV?distance算法的有效性，并且該算法在定位精度和計算時間上要優于傳統定位算法。

5 結 語

本文在改進基本果蠅優化算法的基礎上，針對傳統DV?distance算法定位精度低、噪聲影響大，受限于網絡拓撲結構等問題，將改進的果蠅優化算法引入到DV?distance設計中，提出一種基于IFOA優化DV?distance算法的WSNs定位方法。為進一步提高算法定位精度，引入動態加權修正因子概念，并給出了動態誤差修正策略，最后對WSNs節點定位問題進行實驗仿真。仿真結果表明，基于IFOA優化DV?distance定位算法有效提高了節點定位精度。

參考文獻

[1] 劉志新，劉強，袁亞洲，等.基于貝葉斯估計與虛擬力導向混合遺傳算法的無線傳感網絡定位方案[J].控制與決策，2013，28（6）：899?903.

[2] 王換招，孟凡治，李增智.高效節能的無線傳感器網絡覆蓋保持協議[J].軟件學報，2010，21（12）：3124?3127.

[3] 高鵬，石為人.基于測距定向的WSNs分步求精定位算法[J].儀器儀表學報，2012，33（5）：976?984.

[4] AKSU H， AKSOY D， KORPEOGLU I. A study of localization metrics： evaluation of position errors in wireless sensor networks [J]. Computer networks， 2011， 55（15）： 3562?3577.

[5] NICULESCU D， NATH B. DV based positioning in Ad Hoc networks [J]. Telecommunication systems modeling， analysis， design and management， 2003， 22 （1）： 267?280.

[6] 馬慶功，劉冉冉.基于DV?Distance的無線傳感器網絡定位算法研究[J].吉林師范大學學報（自然科學版），2014，24（1）：66?70.

[7] 石欣，冉啟可，范敏，等.無線傳感器網絡動態加權DV?Distance算法[J].儀器儀表學報，2013，34（9）：1975?1981.

[8] PAN W T. A new fruit fly optimization algorithm： taking the financial distress model as an example [J]. Knowledge?based systems， 2012， 26（2）： 69?74.

[9] PAVAI K， SIBAGAMIA， SRIDHARAN D. Study of routing protocols in wireless sensor networks [C]// Proceedings of 2009 IEEE International Conference on Advances in Computing Control and Telecommunication Technologies. Trivandrum： IEEE， 2009： 522?525.

[10] 李牧東，熊偉，郭龍.基于人工蜂群算法的DV?Hop定位改進[J].計算機科學，2013，40（1）：33?36.

[11] 江濤.基于混合人工蜂群策略的改進DV?Hop定位算法[J].電子器件，2014，37（5）：912?916.