郭 悅,王紅軍,解夢(mèng)奇

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

0 概述

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

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

1 相關(guān)研究

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

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

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

2 定位算法

2.1 邊界盒算法

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

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

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

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

圖2 邊界盒算法示意圖

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

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

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

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

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

(1)

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

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

(2)

誤差函數(shù)為:

(3)

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

(4)

BFOA算法流程如圖3所示。

圖3 BFOA算法流程

BFOA算法的具體步驟為:

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

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

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

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

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

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

3 實(shí)驗(yàn)與結(jié)果分析

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

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

(5)

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

3.1 測(cè)量節(jié)點(diǎn)數(shù)量對(duì)定位效果的影響

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

圖4 測(cè)量節(jié)點(diǎn)數(shù)量對(duì)定位效果的影響

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

從圖4可以看出,當(dāng)測(cè)量節(jié)點(diǎn)數(shù)由3個(gè)增加到11個(gè)時(shí),實(shí)驗(yàn)得到的粒子群算法、果蠅優(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ū)間中,可以看出測(cè)量節(jié)點(diǎn)數(shù)量的增加對(duì)定位效果的影響不大。綜上所述,從節(jié)約能源以及硬件設(shè)備的復(fù)雜性等方面考慮,選取的測(cè)量節(jié)點(diǎn)越少越好,本文中采取3個(gè)測(cè)量節(jié)點(diǎn)進(jìn)行定位。

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

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

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

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

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

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

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

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種算法定位精度均同步提高,從變化趨勢(shì)中可以看出,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,測(cè)量節(jié)點(diǎn)數(shù)量設(shè)為3個(gè),最大迭代次數(shù)設(shè)為100的條件下,比較粒子群算法、FOA算法、DFOA算法與本文提出的BFOA算法的穩(wěn)定性。4種算法均進(jìn)行了20組仿真對(duì)比實(shí)驗(yàn),每組仿真實(shí)驗(yàn)中4種算法均運(yùn)行1 000次,取與4種算法相對(duì)應(yīng)的1 000次實(shí)驗(yàn)的平均定位誤差值作為本組的實(shí)驗(yàn)結(jié)果,即通過比較4種算法多組實(shí)驗(yàn)的平均誤差值波動(dòng)情況來驗(yàn)證算法的穩(wěn)定性,所得仿真結(jié)果如圖7所示。

圖7 4種算法在不同實(shí)驗(yàn)組次下的定位效果

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

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

4 結(jié)束語

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