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

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

關(guān)鍵詞： 無線傳感器網(wǎng)絡(luò)； 節(jié)點(diǎn)定位； 果蠅優(yōu)化算法； DV?distance

中圖分類號(hào)： TN911?34； TP393 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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é)點(diǎn)位置定位作為WSNs關(guān)鍵技術(shù)之一[2]，具有十分重要的研究意義。常見的定位方法可以分為基于測(cè)距（range?based）的定位技術(shù)和無須測(cè)距（range?free）的定位技術(shù)兩大類[3]。RSSI（Received Signal Strength Indication）是典型的基于測(cè)距定位算法[4]，由于具有硬件成本低、容易獲取等特點(diǎn)，得到了廣泛應(yīng)用，但是定位精度低、能耗相對(duì)較大。而無須測(cè)距定位算法應(yīng)用較為廣泛的是DV?Hop算法[5]，其屬于自組織定位系統(tǒng)（Ad Hoc Positioning System，APS）范疇，具有算法簡(jiǎn)單，易于實(shí)現(xiàn)等特點(diǎn)，但是對(duì)節(jié)點(diǎn)性能要求相對(duì)較高，精度受網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)影響較大[6]。

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

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

1 DV?distance算法描述

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

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

Step1： 獲取未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)之間的跳段距離。

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

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

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

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

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

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

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

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

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

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

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

式中為隨機(jī)數(shù)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

式中為信標(biāo)節(jié)點(diǎn)的位置坐標(biāo)。

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

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

4 實(shí)驗(yàn)仿真

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

式中：為仿真實(shí)驗(yàn)次數(shù)；為節(jié)點(diǎn)通信半徑（?。?；為可定位節(jié)點(diǎn)數(shù)；，分別為位置節(jié)點(diǎn)真實(shí)坐標(biāo)和算法求解所得坐標(biāo)。

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

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

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

4.2 信標(biāo)節(jié)點(diǎn)個(gè)數(shù)、網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)對(duì)算法定位精度的影響

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

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

5 結(jié) 語(yǔ)

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

參考文獻(xiàn)

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

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

[3] 高鵬，石為人.基于測(cè)距定向的WSNs分步求精定位算法[J].儀器儀表學(xué)報(bào)，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é)報(bào)（自然科學(xué)版），2014，24（1）：66?70.

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

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