基于IFOA優(yōu)化DV—distance算法的無線傳感器網(wǎng)絡(luò)定位研究

龐先偉+左仁淑+王婷婷+李學(xué)軍

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

關(guān)鍵詞： 無線傳感器網(wǎng)絡(luò)； 節(jié)點定位； 果蠅優(yōu)化算法； 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 引 言

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

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

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

1 DV?distance算法描述

設(shè)定存在如圖1所示的無線傳感器網(wǎng)絡(luò)，其中，由個信標節(jié)點組成的集合為；個未知節(jié)點組成的集合為。

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

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

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

Step2： 未知節(jié)點位置確定。

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

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

（1） 由于相鄰節(jié)點間的距離是通過RSSI測得，而RSSI測距技術(shù)受距離和環(huán)境影響較大，因此導(dǎo)致節(jié)點間距離測量精度存在較大誤差。

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

2 改進果蠅優(yōu)化算法（IFOA）描述

2.1 基本果蠅優(yōu)化算法（FOA）

果蠅優(yōu)化算法基于模擬果蠅覓食生物學(xué)現(xiàn)象，通過動態(tài)調(diào)整嗅覺和視覺信息，實現(xiàn)向食物聚攏。FOA基本原理可以描述為：

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

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

式中為隨機數(shù)。

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

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

式中為目標函數(shù)。

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

Step6： 終止條件判斷。重復(fù)執(zhí)行Step2～Step5，直到滿足終止條件。

2.2 多子族群改進果蠅優(yōu)化算法

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

3 基于IFOA優(yōu)化DV?distance算法實現(xiàn)

3.1 動態(tài)誤差修正策略

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

式中：為修正后累計跳段距離；為動態(tài)加權(quán)修正因子；表示未知節(jié)點到信標節(jié)點的跳數(shù)；表示未知節(jié)點到信標節(jié)點的總跳數(shù)；分別表示信標節(jié)點之間的歐式距離和累計跳段距離。

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

3.2 基于IFOA優(yōu)化DV?distance算法實現(xiàn)流程

目標函數(shù)：定義IFOA適應(yīng)度函數(shù)為：

式中為信標節(jié)點的位置坐標。

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

基于IFOA優(yōu)化DV?distance算法節(jié)點定位過程如圖2所示。

4 實驗仿真

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

式中：為仿真實驗次數(shù)；為節(jié)點通信半徑（?。粸榭啥ㄎ还?jié)點數(shù)；，分別為位置節(jié)點真實坐標和算法求解所得坐標。

4.1 平均定位誤差與算法迭代次數(shù)的關(guān)系

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

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

4.2 信標節(jié)點個數(shù)、網(wǎng)絡(luò)節(jié)點個數(shù)對算法定位精度的影響

為進一步分析算法定位精度與信標節(jié)點個數(shù)和網(wǎng)絡(luò)節(jié)點個數(shù)之間的關(guān)系，分別采取FOADV?distance算法，IFOADV?distance算法和HABC算法進行試驗，網(wǎng)絡(luò)節(jié)點總數(shù)為200個。圖4給出了信標節(jié)點個數(shù)與之間的關(guān)系，圖5給出了節(jié)點個數(shù)與之間的關(guān)系。

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

5 結(jié) 語

本文在改進基本果蠅優(yōu)化算法的基礎(chǔ)上，針對傳統(tǒng)DV?distance算法定位精度低、噪聲影響大，受限于網(wǎng)絡(luò)拓撲結(jié)構(gòu)等問題，將改進的果蠅優(yōu)化算法引入到DV?distance設(shè)計中，提出一種基于IFOA優(yōu)化DV?distance算法的WSNs定位方法。為進一步提高算法定位精度，引入動態(tài)加權(quán)修正因子概念，并給出了動態(tài)誤差修正策略，最后對WSNs節(jié)點定位問題進行實驗仿真。仿真結(jié)果表明，基于IFOA優(yōu)化DV?distance定位算法有效提高了節(jié)點定位精度。

參考文獻

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

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

[3] 高鵬，石為人.基于測距定向的WSNs分步求精定位算法[J].儀器儀表學(xué)報，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的無線傳感器網(wǎng)絡(luò)定位算法研究[J].吉林師范大學(xué)學(xué)報（自然科學(xué)版），2014，24（1）：66?70.

[7] 石欣，冉啟可，范敏，等.無線傳感器網(wǎng)絡(luò)動態(tài)加權(quán)DV?Distance算法[J].儀器儀表學(xué)報，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].計算機科學(xué)，2013，40（1）：33?36.

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