基于果蠅算法的物聯(lián)網(wǎng)節(jié)點定位技術(shù)研究

郭 悅,王紅軍,解夢奇

(國防科技大學(xué) 電子對抗學(xué)院,合肥 230037)

0 概述

近年來,隨著智慧城市、云計算、大數(shù)據(jù)等概念的相繼提出,物聯(lián)網(wǎng)產(chǎn)業(yè)進入到快速發(fā)展的階段。物聯(lián)網(wǎng)在當(dāng)前應(yīng)用比較廣泛的領(lǐng)域有智能路燈、物流和共享單車等方面,特別是在未來5G網(wǎng)絡(luò)架構(gòu)中,專門設(shè)計了mMTC大規(guī)模物聯(lián)網(wǎng)業(yè)務(wù)。基于位置的服務(wù)(Location-based Services,LBS)是物聯(lián)網(wǎng)范圍內(nèi)最具前景的應(yīng)用之一,基于物聯(lián)網(wǎng)的大多數(shù)公共服務(wù)和商業(yè)應(yīng)用均依賴于節(jié)點的位置信息,約70%的物聯(lián)網(wǎng)應(yīng)用開發(fā)直接依賴或受益于節(jié)點位置信息的獲取[1],精確的節(jié)點定位在物聯(lián)網(wǎng)位置服務(wù)應(yīng)用中占有越來越重要的地位。許多相關(guān)的數(shù)據(jù)只有在確定節(jié)點的確切位置信息時才有意義,否則毫無價值。物聯(lián)網(wǎng)中的位置信息不僅影響了人們生活的方方面面,而且已經(jīng)擴展和應(yīng)用到軍事領(lǐng)域。

物聯(lián)網(wǎng)中節(jié)點的定位[2-4],即通過已知節(jié)點的信息來對未知節(jié)點進行定位,是解決特定環(huán)境中實體定位問題(如環(huán)境監(jiān)測和入侵定位)的關(guān)鍵技術(shù)。已知節(jié)點即測量節(jié)點,是用來對未知節(jié)點進行定位的設(shè)備,可以通過測量節(jié)點配備的GPS系統(tǒng)獲得測量節(jié)點準(zhǔn)確的位置信息,未知節(jié)點即為需要定位的目標(biāo)節(jié)點。由于一定的環(huán)境因素或者其他條件的制約,無法通過GPS系統(tǒng)獲取目標(biāo)節(jié)點的位置信息,則需要一些其他的定位方法。傳統(tǒng)的定位方法包括基于測距的以及非測距的定位方法,基于測距的定位方法有極大似然估計法(Maximum Likelihood Estimation,MLE)、三邊測量法和最小二乘估計法(Least Squares Estimation,LSE)等;基于非測距的定位方法包括APIT(Approximate Point-in-triangulation Test)算法、邊界盒(Bounding-Box)算法和DV-Hop算法等。其中邊界盒算法[5]是一種分布式定位的經(jīng)典算法,該算法通過矩形區(qū)域?qū)y量節(jié)點的通信范圍進行約束,其具有計算簡單、操作容易的優(yōu)點,但定位誤差較大。為平衡算法的動態(tài)性能與定位準(zhǔn)確度,本文提出一種融合邊界盒算法與果蠅優(yōu)化算法(Fruit Fly Optimization Algorithm,FOA)的改進算法,該算法利用邊界盒算法來約束FOA算法的初始搜索范圍,同時通過增加權(quán)重系數(shù)重構(gòu)算法的味道濃度函數(shù),以改善算法的定位性能。

1 相關(guān)研究

近年來,隨著群智能算法的不斷發(fā)展,其在解決復(fù)雜問題方面為人們提供了有力的工具,同時對于定位問題的處理也具有良好的效果。粒子群優(yōu)化(Particle Swarm Optimization,PSO)算法被用來解決節(jié)點定位的問題,在粒子的搜索空間中,通過并行的方式進行迭代以實現(xiàn)優(yōu)化[6]。為獲得更高的定位精度,文獻[7]使用經(jīng)典的蟻群算法來優(yōu)化三邊測量算法的誤差函數(shù),然而,該算法具有計算速度較慢、易陷入局部最優(yōu)的缺陷,很大程度上影響了算法的定位精度。果蠅優(yōu)化算法[8-10]是一種較新的群智能優(yōu)化算法,相比于其他群智能算法,具有易于實現(xiàn)、結(jié)構(gòu)簡單、原理易懂等優(yōu)點。

由于果蠅優(yōu)化算法可用來處理優(yōu)化問題,在較短時間被成功地應(yīng)用于網(wǎng)絡(luò)能效優(yōu)化、物流[11]、規(guī)劃問題[12-13]、控制辨識問題[14-15]等方面。近年來,該算法被應(yīng)用于物聯(lián)網(wǎng)中節(jié)點的定位,且取得了較好的效果。文獻[16]基于果蠅優(yōu)化算法提出一種新型的節(jié)點定位算法,將m個測量節(jié)點對未知節(jié)點進行定位之后的平均誤差表達式作為算法的味道濃度函數(shù),通過迭代實現(xiàn)優(yōu)化,不斷縮小未知節(jié)點與測量節(jié)點之間的距離誤差,最終來確定未知節(jié)點的位置坐標(biāo)。該方法在一定程度上解決了一些傳統(tǒng)算法定位不精確的問題。但是在搜索過程中,每個粒子的軌跡取決于味道濃度最佳個體的位置,當(dāng)沒有更好的個體更新種群的最佳位置時,所有的粒子都會迅速聚集在當(dāng)前最佳位置的區(qū)域,導(dǎo)致早熟問題。同時在客觀上由于測距誤差的存在且誤差函數(shù)區(qū)分度小,使得定位誤差增大。文獻[17]提出一種改進的果蠅優(yōu)化算法DFOA(Dynamic Step Fruit Fly Optimization Algorithm),基于懲罰函數(shù)的思想,對算法的味道濃度函數(shù)進行優(yōu)化,并采用誤差修正系數(shù)μ濾除掉一些具有較大測距誤差的距離,使用懲罰系數(shù)M加大對非可行點的懲罰,并且在誤差修正參數(shù)μ的基礎(chǔ)上添加約束，以進一步減小未知節(jié)點的可行域范圍。但是懲罰系數(shù)M多憑經(jīng)驗選取,其選取不當(dāng)會對測量結(jié)果造成較大誤差。

通過分析不難發(fā)現(xiàn),在對果蠅優(yōu)化算法進行初始化時,需要在搜索空間中隨機初始化許多果蠅個體,當(dāng)果蠅種群在較大的空間進行搜索時,算法的收斂速度逐漸變慢,同時定位精度也會有一定程度的下降。

2 定位算法

2.1 邊界盒算法

邊界盒算法自從被提出以來,已廣泛應(yīng)用于物聯(lián)網(wǎng)中未知節(jié)點的定位,它是一種基于非測距的定位方法。該方法使用矩形區(qū)域來約束定位時未知節(jié)點所在的區(qū)域范圍,測量節(jié)點通信范圍如圖1所示。

圖1 節(jié)點通信范圍

如果未知節(jié)點與測量節(jié)點間的距離小于測量節(jié)點的通信半徑,則測量節(jié)點可以接收未知節(jié)點發(fā)射的信號;未知節(jié)點如果在測量節(jié)點通信半徑所覆蓋的通信圓區(qū)域內(nèi),那么它一定處于以測量節(jié)點為中心,以2倍通信半徑作為邊長的正方形區(qū)域內(nèi)。所以,矩形相互重疊的區(qū)域可以用作未知節(jié)點位置所在的估計區(qū)域。

如圖2所示,待定位的未知節(jié)點處于測量節(jié)點A的通信矩形A1A2A3A4內(nèi),同時也位于測量節(jié)點B的通信矩形B1B2B3B4范圍內(nèi),則未知節(jié)點一定處于2個矩形相交部分B1C1A3C2的范圍內(nèi)。因此,矩形相互重疊區(qū)域的中心可以用作對未知節(jié)點進行定位的結(jié)果。如果直接用通信圓的交集作為定位區(qū)域,則計算量太大,該算法將矩形區(qū)域交集的中心作為定位結(jié)果,復(fù)雜度和計算量小、操作簡單,但定位精度相對偏低。

圖2 邊界盒算法示意圖

2.2 果蠅優(yōu)化算法

果蠅優(yōu)化算法是一種新的全局搜索優(yōu)化方法,通過模擬生物學(xué)中果蠅獨特的覓食行為,基于果蠅個體優(yōu)越的嗅覺和視覺搜索機制,在搜索空間中進行迭代尋優(yōu)來達到優(yōu)化的目的。

本文將果蠅優(yōu)化算法應(yīng)用于物聯(lián)網(wǎng)中節(jié)點的定位,通過一步步地迭代實現(xiàn)優(yōu)化,最終得到未知節(jié)點的坐標(biāo)。經(jīng)過研究發(fā)現(xiàn),當(dāng)對果蠅個體進行初始化時,在搜索空間中需要隨機初始化許多的果蠅個體,文獻[16]在迭代次數(shù)、種群規(guī)模及飛行區(qū)間相同的條件下,分別在[0,30]及[0,5]范圍內(nèi)初始化果蠅位置。仿真結(jié)果表明,在其他條件相同的情況下,[0,5]范圍內(nèi)算法的收斂速度較快,且容易找出果蠅的最終聚集位置,定位精度較高。當(dāng)搜索空間較大時,算法的收斂速度較慢,定位精度也會有所降低。因此,可以優(yōu)化果蠅種群的初始搜索空間,以滿足定位要求。

為得到更好的定位性能,本文提出BFOA定位算法。該算法的主要思想是通過邊界盒算法將果蠅算法的初始搜索范圍約束在一定范圍內(nèi),再應(yīng)用FOA定位算法得到目標(biāo)節(jié)點的最優(yōu)估計位置。

在文獻[16]中,未知節(jié)點與m個已知節(jié)點的距離誤差函數(shù)被用作果蠅算法的味道濃度判定函數(shù),如式(1)所示。

(1)

其中,di為目標(biāo)距離。

通過迭代尋找味道濃度函數(shù)最小值作為果蠅的最優(yōu)位置,即待定位節(jié)點的位置,通過此方法在一定程度上提高了定位精度。然而,在測距過程中可能存在某些估計距離與實際距離有較大偏差,導(dǎo)致定位結(jié)果產(chǎn)生誤差。本文采用基于RSSI[18-19]模型的測距方法,根據(jù)在自由空間中無線電波的傳播規(guī)律可知,在距離測量的過程中,2個節(jié)點之間的距離越近,測得的距離誤差越小;距離越遠,誤差越大。因此,本文算法重新配置測距值集合中各測距值的權(quán)重,將由RSSI測距得到的距離值轉(zhuǎn)換成算法的權(quán)值,文中的權(quán)重系數(shù)wi用于對在味道濃度函數(shù)中測距值所占的比重進行約束。

(2)

誤差函數(shù)為:

(3)

改進后的味道濃度函數(shù)為:

(4)

BFOA算法流程如圖3所示。

圖3 BFOA算法流程

BFOA算法的具體步驟為:

步驟1使用邊界盒定位算法對果蠅優(yōu)化算法的初始搜索空間進行優(yōu)化。

步驟2對果蠅優(yōu)化算法的相關(guān)參數(shù)進行初始化,包括最大迭代次數(shù)(maxgen)和種群規(guī)模(sizePop)等。

步驟3測量節(jié)點通過 RSSI測距技術(shù)測量到目標(biāo)的距離di,在步驟1得到的區(qū)域內(nèi)隨機生成第一批果蠅個體。

步驟4選擇具有最佳味道濃度的個體作為果蠅優(yōu)化算法初始的種群位置,并保留最佳濃度值處的坐標(biāo)值。

步驟5根據(jù)視覺搜索機制產(chǎn)生果蠅個體,并通過式(4)來計算果蠅個體的味道濃度值用于迭代尋優(yōu)。

步驟6確定是否滿足收斂條件,如果滿足,則輸出最后一次迭代的坐標(biāo)作為估計位置;若不滿足,則繼續(xù)執(zhí)行步驟4～步驟5。

3 實驗與結(jié)果分析

為了更好地評估本文提出的BFOA算法的性能,利用Matlab R2016a進行仿真實驗,以一個節(jié)點定位的過程為例:場景為在100 m×100 m的二維矩形區(qū)域范圍內(nèi)設(shè)置一個未知節(jié)點,其坐標(biāo)為(40,50);粒子群算法的參數(shù)設(shè)置為:wstart=0.9,wend=0.4,w=wend×(wstart/wend)(i+1)/mmaxgen,其中wstart和wend分別為初始和結(jié)束時算法的慣性權(quán)重;參照文獻[18],DFOA算法的懲罰系數(shù)M設(shè)為8。

假設(shè)每次仿真時具有相同的網(wǎng)絡(luò)環(huán)境，實驗數(shù)據(jù)取運行1 000次的平均定位誤差值作為本次的實驗結(jié)果。為了衡量算法定位精度，選用式(5)的計算結(jié)果作為算法的評價標(biāo)準(zhǔn)。

(5)

其中,(x,y)表示最終算法的定位結(jié)果,(xreal,yreal)表示需要定位的節(jié)點的真實坐標(biāo)。可見,算法定位的平均誤差值越小,則定位精度越高。為了驗證算法的定位效果,分別比較粒子群算法、文獻[16]提出的基于果蠅優(yōu)化算法的節(jié)點定位方法、DFOA算法與本文提出的BFOA算法隨測量節(jié)點數(shù)量和種群規(guī)模變化時的定位精度,并且對4種算法的收斂速度、定位精度以及穩(wěn)定性進行分析。

3.1 測量節(jié)點數(shù)量對定位效果的影響

為了說明不同測量節(jié)點的數(shù)量對定位精度的影響,實驗時將種群規(guī)模設(shè)置為20,最大迭代次數(shù)設(shè)置為100。在測量節(jié)點數(shù)目不斷增加的情況下,比較粒子群算法、果蠅優(yōu)化算法、DFOA算法與本文提出的BFOA算法的定位精度。若4種算法的平均定位誤差比較接近,則說明測量節(jié)點數(shù)量的變化對定位結(jié)果影響不大;若平均定位誤差具有較大的差距,則說明定位效果差距較大,所得的仿真結(jié)果如圖4所示。

圖4 測量節(jié)點數(shù)量對定位效果的影響

Fig.4Effect of the number of measurment nodes on localization

從圖4可以看出,當(dāng)測量節(jié)點數(shù)由3個增加到11個時,實驗得到的粒子群算法、果蠅優(yōu)化算法、DFOA算法以及BFOA算法的平均定位誤差分別處于(3.312 6 m,3.481 5 m)、(3.886 5 m,4.023 8 m)、(2.864 2 m,3.261 4 m)和(2.265 3 m,2.419 5 m)的區(qū)間中,可以看出測量節(jié)點數(shù)量的增加對定位效果的影響不大。綜上所述,從節(jié)約能源以及硬件設(shè)備的復(fù)雜性等方面考慮,選取的測量節(jié)點越少越好,本文中采取3個測量節(jié)點進行定位。

3.2 種群規(guī)模對定位效果的影響

為驗證算法的動態(tài)性能,在仿真時考慮了種群規(guī)模這個指標(biāo)。通過交叉定位,將測量節(jié)點的數(shù)量設(shè)為3個,最大迭代次數(shù)設(shè)為100,并不斷改變種群規(guī)模。在種群規(guī)模增加的情況下,分別比較粒子群算法、FOA算法、DFOA算法以及本文提出的BFOA算法的定位效果,所得的仿真結(jié)果如圖5所示。

圖5 不同種群規(guī)模的定位效果

從圖5可以看出,當(dāng)果蠅種群規(guī)模增加時,4種算法的定位精度也隨之增加,同時當(dāng)具有較大的種群規(guī)模時,4種算法的定位效果均趨于穩(wěn)定。然而,當(dāng)種群大小增加時,算法的動態(tài)性能將會隨著計算量的增加而降低。當(dāng)種群規(guī)模達到20之后,4種算法的定位精度不會顯著增加,相比于FOA算法、PSO算法以及DFOA算法,BFOA算法的定位精度較高。所以,為了平衡算法的動態(tài)性能與定位的準(zhǔn)確性,定位時將種群規(guī)模設(shè)為20。

3.3 BFOA算法收斂性能和定位精度分析

由3.1節(jié)和3.2節(jié)內(nèi)容可知,將種群規(guī)模設(shè)為20,測量節(jié)點數(shù)量同樣設(shè)為3個,最大迭代次數(shù)設(shè)為100。在迭代次數(shù)不斷增加的情況下,比較粒子群算法、FOA算法、DFOA算法與本文提出的BFOA算法的收斂性能和定位精度,仿真結(jié)果如圖6所示。

圖6 迭代次數(shù)增加時4種算法定位效果對比

Fig.6 Comparison of localization effects of 4 algorithms with increasing iterations

從圖6可以看出,BFOA算法在迭代次數(shù)大于8次、DFOA算法在迭代次數(shù)大于15次、FOA算法在迭代次數(shù)大于18次、PSO算法在迭代次數(shù)大于45次后定位性能均趨于穩(wěn)定,但BFOA算法的收斂速度明顯較快。此外,隨著迭代次數(shù)的增加,4種算法定位精度均同步提高,從變化趨勢中可以看出,DFOA算法的定位精度明顯優(yōu)于FOA和PSO算法,在迭代30次之后PSO算法比FOA算法定位精度要高。但相比FOA、 PSO與DFOA算法,BFOA算法具有更低的定位誤差,即具有更高的定位精度。

綜合考慮算法的收斂速度和定位精度,BFOA算法的定位性能優(yōu)于DFOA、PSO和FOA算法。

3.4 BFOA算法穩(wěn)定性分析

在種群規(guī)模設(shè)為20,測量節(jié)點數(shù)量設(shè)為3個,最大迭代次數(shù)設(shè)為100的條件下,比較粒子群算法、FOA算法、DFOA算法與本文提出的BFOA算法的穩(wěn)定性。4種算法均進行了20組仿真對比實驗,每組仿真實驗中4種算法均運行1 000次,取與4種算法相對應(yīng)的1 000次實驗的平均定位誤差值作為本組的實驗結(jié)果,即通過比較4種算法多組實驗的平均誤差值波動情況來驗證算法的穩(wěn)定性,所得仿真結(jié)果如圖7所示。

圖7 4種算法在不同實驗組次下的定位效果

Fig.7 Localization effects of 4 algorithms in different experimental groups

從圖7可以看出,BFOA算法定位的平均誤差波動最小,算法的穩(wěn)定性相對最好,FOA算法定位的平均誤差波動較大,算法的穩(wěn)定性差，本文提出的算法具有很高的定位精度,同時具有更好的穩(wěn)定性。果蠅優(yōu)化算法迭代中的搜索效率與果蠅個體所處位置和迭代次數(shù)有關(guān),但并不與迭代次數(shù)呈嚴(yán)格的線性關(guān)系。本文采用邊界盒算法對初始搜索空間進行優(yōu)化使得搜索效率更高,穩(wěn)定性增強。因此,在算法的穩(wěn)定性方面,BFOA算法優(yōu)于DFOA、PSO和FOA算法。

4 結(jié)束語

本文提出一種基于果蠅優(yōu)化算法的物聯(lián)網(wǎng)節(jié)點定位方法,通過采用邊界盒定位算法優(yōu)化果蠅種群的初始搜索范圍,同時重構(gòu)算法的味道濃度函數(shù)以提高算法的定位性能,通過仿真實驗比較測量節(jié)點數(shù)量與種群規(guī)模大小對4種算法定位效果的影響，結(jié)果表明,與FOA、PSO和DFOA定位算法相比,本文算法在定位精度和收斂速度方面都有所提高,同時具有更高的穩(wěn)定性,且算法的復(fù)雜度較低。下一步將繼續(xù)對定位應(yīng)用進行研究,并在實際環(huán)境中驗證BFOA定位算法的有效性。