一種改進(jìn)的布谷鳥搜索移動(dòng)信標(biāo)節(jié)點(diǎn)定位方法

荊夏磊,喬學(xué)工

(太原理工大學(xué) 信息工程學(xué)院,山西 晉中 030600)

0 引言

無線傳感器網(wǎng)絡(luò)由成百上千傳感器節(jié)點(diǎn)組成,這些傳感器節(jié)點(diǎn)可以通過飛機(jī)播撒或炮彈射擊等方式進(jìn)行部署。研究傳感器節(jié)點(diǎn)定位問題具有重要意義,如在戰(zhàn)場(chǎng)實(shí)時(shí)監(jiān)測(cè)[1],林業(yè)數(shù)據(jù)采集[2]等應(yīng)用中,往往需要獲取相關(guān)物體的位置信息。

傳統(tǒng)靜態(tài)信標(biāo)節(jié)點(diǎn)定位方式容易受到節(jié)點(diǎn)布置數(shù)量、分布狀態(tài)等因素影響。一旦網(wǎng)絡(luò)中節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)發(fā)生變化,定位效果不佳。許多研究者提出利用移動(dòng)信標(biāo)節(jié)點(diǎn)輔助未知節(jié)點(diǎn)定位[3-5]。Srinath[6]提出讓信標(biāo)節(jié)點(diǎn)按照隨機(jī)移動(dòng)模型移動(dòng),采用分布式算法定位;陳娟[7]等提出單一信標(biāo)節(jié)點(diǎn)采用Gauss-Markov的方式盡量遍歷傳感器節(jié)點(diǎn)分布區(qū)域,再通過加權(quán)質(zhì)心與擴(kuò)展卡爾曼濾波算法計(jì)算未知節(jié)點(diǎn)坐標(biāo);文獻(xiàn)[8]用接收信號(hào)強(qiáng)度法(RSSI)測(cè)量距離,用Bayes推論估算未知節(jié)點(diǎn)位置,比較了兩種確定路徑下的移動(dòng)信標(biāo)節(jié)點(diǎn)定位性能;文獻(xiàn)[9]提出一種基于移動(dòng)信標(biāo)節(jié)點(diǎn)功率控制的智能定位方法。上述文獻(xiàn)研究了移動(dòng)信標(biāo)節(jié)點(diǎn)按照某種路徑移動(dòng)時(shí)的節(jié)點(diǎn)定位問題。當(dāng)移動(dòng)信標(biāo)節(jié)點(diǎn)在運(yùn)動(dòng)中距離未知節(jié)點(diǎn)較近時(shí),定位精度較高;距離較遠(yuǎn)時(shí)定位精度低,甚至不能定位。節(jié)點(diǎn)定位覆蓋率是指可定位未知節(jié)點(diǎn)數(shù)目與全部未知節(jié)點(diǎn)數(shù)目之比。在移動(dòng)信標(biāo)節(jié)點(diǎn)輔助定位的情況下,研究節(jié)點(diǎn)定位覆蓋率具有現(xiàn)實(shí)意義。

近年來,國(guó)內(nèi)外的專家學(xué)者受到仿生學(xué)啟發(fā)而提出許多智能算法,如粒子群算法,人工魚群算法,遺傳算法等。智能算法具有很強(qiáng)的收斂性,布谷鳥搜索算法(Cuckoo Search,CS)是其中之一,該算法在梯形水庫(kù)優(yōu)化調(diào)度[10]、結(jié)構(gòu)損傷無損檢測(cè)[11]等應(yīng)用中有良好的實(shí)效。本文將布谷鳥搜索算法用到移動(dòng)信標(biāo)節(jié)點(diǎn)定位問題中,針對(duì)算法在迭代后期陷入局部最優(yōu)問題提出一種基于改進(jìn)布谷鳥搜索算法(Artificial Fish-Cuckoo Search,AF-CS)的移動(dòng)信標(biāo)節(jié)點(diǎn)定位算法。該算法將移動(dòng)信標(biāo)節(jié)點(diǎn)定位問題轉(zhuǎn)化為求解目標(biāo)函數(shù)——定位覆蓋率最優(yōu)解問題,將人工魚群算法(Artificial Fish Swarm Algorithm,AFSA)覓食行為引入布谷鳥搜索算法以增強(qiáng)算法的全局收斂能力。仿真結(jié)果表明:該算法能夠在一定條件下達(dá)到對(duì)未知節(jié)點(diǎn)的較高定位覆蓋率,同時(shí)提高了算法的收斂速度。

1 算法模型

1.1 RSSI信號(hào)衰減模型

由于節(jié)點(diǎn)布置在現(xiàn)實(shí)空間中,信號(hào)會(huì)受到障礙物或其他環(huán)境因素的干擾而產(chǎn)生損耗。本文采用的無線信號(hào)傳輸模型為對(duì)數(shù)-常態(tài)分布模型(Log-Normal Distribution Model)。節(jié)點(diǎn)接收信號(hào)時(shí)的路徑損耗如下:

(1)

公式(1)中,d為未知節(jié)點(diǎn)到移動(dòng)信標(biāo)節(jié)點(diǎn)的距離,d0=1 m為參考距離;PL(d)、PL(d0)分別表示經(jīng)過d和d0的路徑損耗,單位為dBm。當(dāng)d0=1 m時(shí),PL(d0)=55 dBm;n是路徑損耗因子,取值范圍為[2,5],本文取4;Xσ是均值為0,標(biāo)準(zhǔn)差為σ的高斯隨機(jī)變量,表示環(huán)境因素對(duì)測(cè)距誤差的影響,本文σ設(shè)定為8?？梢酝ㄟ^公式(2)計(jì)算未知節(jié)點(diǎn)到移動(dòng)信標(biāo)節(jié)點(diǎn)的距離:

(2)

1.2 信標(biāo)節(jié)點(diǎn)移動(dòng)目標(biāo)函數(shù)

在一定區(qū)域中,多個(gè)移動(dòng)信標(biāo)節(jié)點(diǎn)選擇合適的位置對(duì)未知節(jié)點(diǎn)進(jìn)行定位。本文將移動(dòng)信標(biāo)節(jié)點(diǎn)運(yùn)動(dòng)中的停留點(diǎn)視為移動(dòng)信標(biāo)節(jié)點(diǎn)的目標(biāo)位置。信標(biāo)節(jié)點(diǎn)移動(dòng)至目標(biāo)位置向周圍廣播自身位置信息。一般情況下,當(dāng)未知節(jié)點(diǎn)收到3個(gè)或3個(gè)以上不同信標(biāo)節(jié)點(diǎn)位置信息時(shí),通過定位算法可對(duì)該未知節(jié)點(diǎn)定位。在上述過程中,將對(duì)未知節(jié)點(diǎn)的定位覆蓋率作為目標(biāo)函數(shù),具體設(shè)計(jì)如下:

(3)

(4)

(5)

公式(3)-(5)中,A(t)為第t次迭代中可定位未知節(jié)點(diǎn)的數(shù)量,B是區(qū)域內(nèi)未知節(jié)點(diǎn)總數(shù)。at(i)表示第t次迭代中第i個(gè)未知節(jié)點(diǎn),在每次迭代中遍歷區(qū)域內(nèi)所有未知節(jié)點(diǎn)并將可定位的未知節(jié)點(diǎn)數(shù)量求和。Sj表示未知節(jié)點(diǎn)通信半徑R內(nèi)信標(biāo)節(jié)點(diǎn)數(shù)量,當(dāng)未知節(jié)點(diǎn)接收信標(biāo)節(jié)點(diǎn)信息數(shù)量達(dá)到3個(gè)或3個(gè)以上時(shí),將該未知節(jié)點(diǎn)記為“1”,否則記為“0”。目標(biāo)函數(shù)f(t)即為對(duì)未知節(jié)點(diǎn)的定位覆蓋率。

2 多移動(dòng)信標(biāo)節(jié)點(diǎn)定位算法

2.1 初步定位

Fig.1 Method of maximum likelihood estimation圖1 極大似然估計(jì)法

采用RSSI信號(hào)衰減模型和DV-Hop算法,對(duì)未知節(jié)點(diǎn)進(jìn)行定位,用于確定信標(biāo)節(jié)點(diǎn)移動(dòng)的目標(biāo)位置,為精確定位做準(zhǔn)備。

2.1.1 RSSI定位

采用RSSI[12]測(cè)距方法,對(duì)能夠定位的未知節(jié)點(diǎn)(該未知節(jié)點(diǎn)通信半徑內(nèi)的信標(biāo)節(jié)點(diǎn)個(gè)數(shù)大于等于3)進(jìn)行定位,再利用極大似然估計(jì)法求解未知節(jié)點(diǎn)的坐標(biāo)估計(jì)值。

如圖1所示,已知信標(biāo)節(jié)點(diǎn)S1，S2，…，Sn的坐標(biāo)(xS1,yS1)，(xS2,yS2)，…，(xSn,ySn),及他們到未知節(jié)點(diǎn)P的距離分別為d1，d2，…，dn.

可得以下的方程組:

(6)

化簡(jiǎn)為線性方程的形式:AX=b

(7)

通過極大似然估計(jì)法得到P的坐標(biāo)估計(jì)值(xP,yP):

X*=(ATA)-1ATb

(8)

上述方法即利用極大似然估計(jì)法求解能夠定位的未知節(jié)點(diǎn)坐標(biāo)。

2.1.2DVHop定位

經(jīng)過第一步的定位后,將求解出的未知節(jié)點(diǎn)升級(jí)為臨時(shí)性信標(biāo)節(jié)點(diǎn),與原有的信標(biāo)節(jié)點(diǎn)組成新的信標(biāo)節(jié)點(diǎn)集合。采用DV-Hop算法對(duì)其余的未知節(jié)點(diǎn)進(jìn)行粗略定位。

DV-Hop算法[13]根據(jù)節(jié)點(diǎn)間的最小跳數(shù)、平均每跳距離來估算未知節(jié)點(diǎn)坐標(biāo)。節(jié)點(diǎn)間的最小跳數(shù)通過距離矢量路由協(xié)議確定,平均每跳距離可由公式(9)求得。

(9)

其中i、j為信標(biāo)節(jié)點(diǎn),(xi,yi)、(xj,yj)為這兩個(gè)節(jié)點(diǎn)的坐標(biāo),hij為這兩個(gè)節(jié)點(diǎn)間的跳段數(shù),hopsizei表示信標(biāo)節(jié)點(diǎn)i到其他信標(biāo)節(jié)點(diǎn)的平均每跳的距離。

2.2 精確定位

經(jīng)過第一步的初步定位,再利用改進(jìn)布谷鳥搜索算法求解信標(biāo)節(jié)點(diǎn)移動(dòng)的目標(biāo)位置,從而提高未知節(jié)點(diǎn)的定位覆蓋率。

2.2.1 布谷鳥搜索算法

布谷鳥的Levy Flight隨機(jī)搜索路徑和鳥巢的位置更新公式如下:

?L(λ) ，

(10)

(11)

2.2.2 基于魚群覓食因子的AF-CS算法

布谷鳥搜索算法采用Levy Flight隨機(jī)搜索方式和偏差隨機(jī)搜索方式生成新解,這使得算法在迭代過程中具有均衡的局部尋優(yōu)和全局尋優(yōu)能力[16]。布谷鳥搜索算法雖然有上述優(yōu)點(diǎn),但也同樣存在算法后期容易陷入局部最優(yōu),收斂速度慢的問題。人工魚群算法[17-18]是李曉磊博士受魚群行為啟發(fā)而提出的一種基于動(dòng)物行為的群體智能優(yōu)化算法。算法中覓食人工魚個(gè)體的狀態(tài)可表示為向量Xi=(x1,x2,…,xn),其中xi(i=1,2,…,n)為欲尋優(yōu)變量;人工魚個(gè)體當(dāng)前所在位置的濃度為Y=f(X),其中Y為目標(biāo)函數(shù)值;人工魚個(gè)體之間的距離表示為dij=‖Xi-Yi‖;Visual表示人工魚的感知距離;Step表示人工魚移動(dòng)的最大步長(zhǎng)。嘗試次數(shù)Try-number。

文中闡述了折臂式鐵鉆工底座回轉(zhuǎn)機(jī)構(gòu)工作原理為：電動(dòng)機(jī)通過驅(qū)動(dòng)輪帶動(dòng)行星輪將扭轉(zhuǎn)力傳遞到回轉(zhuǎn)軸承上進(jìn)而實(shí)現(xiàn)了鐵鉆工整體的旋轉(zhuǎn)運(yùn)動(dòng)，完成鉆井上卸鉆柱絲扣的工藝要求，并得出了以下結(jié)論：

魚群覓食因子可以在解的感知范圍內(nèi),通過當(dāng)前解與前一位置解的比較,在嘗試次數(shù)范圍內(nèi)篩選出最佳目標(biāo)函數(shù)值,避免算法后期迭代陷入局部最優(yōu);同時(shí),在保證感應(yīng)位置比當(dāng)前位置和前一位置優(yōu)秀的共同前提下進(jìn)行更新,減少了重復(fù)解或劣質(zhì)解的無效迭代,提高了算法的收斂速度。

AF-CS算法步驟如下:

步驟1:將隨機(jī)生成的初始目標(biāo)位置作為輸入種群的個(gè)體位置Xi(i=1,2,…,n),初始化參數(shù),發(fā)現(xiàn)概率pa,最大迭代次數(shù)T,嘗試次數(shù)Try-number,感知距離Visual。

步驟4:產(chǎn)生隨機(jī)數(shù)r,讓隨機(jī)數(shù)r與發(fā)現(xiàn)概率pa做比較,若r>pa,則丟棄當(dāng)前較差位置,利用公式(11)偏差隨機(jī)搜索產(chǎn)生新解,并比較更新前后的目標(biāo)函數(shù)值,保留目標(biāo)函數(shù)值較好的鳥巢位置;否則保留當(dāng)前最優(yōu)位置。

步驟6:對(duì)篩選后的鳥巢位置與當(dāng)前目標(biāo)函數(shù)值最優(yōu)的鳥巢位置進(jìn)行比較,保留目標(biāo)函數(shù)值最優(yōu)的鳥巢位置。

步驟7:執(zhí)行步驟3-步驟6,直到達(dá)到預(yù)先設(shè)定的迭代次數(shù)時(shí)終止,輸出目標(biāo)函數(shù)值最優(yōu)的鳥巢位置。

2.3 定位算法步驟

具體的定位步驟如下:

步驟1:在邊長(zhǎng)為L(zhǎng)米的正方形區(qū)域內(nèi)隨機(jī)部署n個(gè)未知節(jié)點(diǎn)與m個(gè)信標(biāo)節(jié)點(diǎn)。

步驟2:未知節(jié)點(diǎn)接收周圍信標(biāo)節(jié)點(diǎn)的信號(hào),統(tǒng)計(jì)接收到信號(hào)的數(shù)量,采用RSSI測(cè)距法對(duì)節(jié)點(diǎn)間的距離進(jìn)行測(cè)量。

步驟3:采用極大似然估計(jì)法對(duì)能夠定位的未知節(jié)點(diǎn)進(jìn)行定位,并將這些未知節(jié)點(diǎn)升級(jí)為臨時(shí)性信標(biāo)節(jié)點(diǎn)。

步驟4:采用DV-Hop算法對(duì)其余的未知節(jié)點(diǎn)進(jìn)行粗略定位,統(tǒng)計(jì)所有未知節(jié)點(diǎn)的坐標(biāo)估計(jì)值,分別表示為(xs1,ys1) ,…,(xsn,ysn).

步驟5:調(diào)用AF-CS算法求解所有信標(biāo)節(jié)點(diǎn)移動(dòng)的目標(biāo)位置。

步驟6:信標(biāo)節(jié)點(diǎn)根據(jù)步驟5的求解結(jié)果,信標(biāo)節(jié)點(diǎn)運(yùn)動(dòng)到目標(biāo)位置上,對(duì)未知節(jié)點(diǎn)進(jìn)行重定位。

步驟7:統(tǒng)計(jì)未知節(jié)點(diǎn)的定位結(jié)果,表示為(xz1,yz1),…,(xzn,yzn),算法結(jié)束。

3 仿真分析

為驗(yàn)證多移動(dòng)信標(biāo)節(jié)點(diǎn)定位算法的有效性,本文設(shè)計(jì)邊長(zhǎng)為100 m的正方形區(qū)域?qū)σ苿?dòng)前后的定位效果進(jìn)行仿真實(shí)驗(yàn),仿真軟件是Matlab2010b。未知節(jié)點(diǎn)總數(shù)UN=200,最大迭代次數(shù)為T=200,發(fā)現(xiàn)概率pa=0.25,魚群覓食因子嘗試次數(shù)Try-number=30,人工魚感知距離Visual=5 m。

3.1 信標(biāo)節(jié)點(diǎn)移動(dòng)對(duì)定位覆蓋率的影響

3.1.1 信標(biāo)節(jié)點(diǎn)數(shù)量與定位覆蓋率

當(dāng)未知節(jié)點(diǎn)通信半徑R=30 m時(shí),計(jì)算不同信標(biāo)節(jié)點(diǎn)數(shù)量情況下信標(biāo)節(jié)點(diǎn)移動(dòng)前后對(duì)未知節(jié)點(diǎn)的定位覆蓋率,對(duì)比見表1。

表1 信標(biāo)節(jié)點(diǎn)數(shù)量與定位覆蓋率

表1數(shù)據(jù)表明,信標(biāo)節(jié)點(diǎn)對(duì)未知節(jié)點(diǎn)的定位覆蓋率隨節(jié)點(diǎn)布置數(shù)量的增加而增大;移動(dòng)后信標(biāo)節(jié)點(diǎn)對(duì)未知節(jié)點(diǎn)的精確定位覆蓋率比移動(dòng)前粗略定位覆蓋率更高。

3.1.2 通信半徑與定位覆蓋率關(guān)系

當(dāng)信標(biāo)節(jié)點(diǎn)數(shù)量為25個(gè)時(shí),計(jì)算不同通信半徑情況下信標(biāo)節(jié)點(diǎn)移動(dòng)前后對(duì)未知節(jié)點(diǎn)的定位覆蓋率,對(duì)比如圖2。從圖中可以看出，信標(biāo)節(jié)點(diǎn)對(duì)未知節(jié)點(diǎn)的定位覆蓋率隨通信半徑R的增大而增大;如通信半徑R為25 m時(shí),移動(dòng)后信標(biāo)節(jié)點(diǎn)對(duì)未知節(jié)點(diǎn)定位覆蓋率為85.72%,比移動(dòng)前提高了11.17%。圖2表明,當(dāng)通信半徑相同時(shí),移動(dòng)后信標(biāo)節(jié)點(diǎn)對(duì)未知節(jié)點(diǎn)的定位覆蓋率比移動(dòng)前定位覆蓋率更高。

Fig.2 Relationship between communication radius and localization coverage圖2 通信半徑與定位覆蓋率關(guān)系

Fig.3 Relationship between localization coverage and number of iterations圖3 定位覆蓋率與迭代次數(shù)關(guān)系

3.2 改進(jìn)算法對(duì)定位覆蓋率的影響

在信標(biāo)節(jié)點(diǎn)數(shù)量為25個(gè),通信半徑為R=30 m時(shí),AFCS算法與基本CS算法對(duì)未知節(jié)點(diǎn)的定位覆蓋率對(duì)比如圖3。從圖中可以看出，在第190次迭代時(shí),基本CS算法收斂的定位覆蓋率為84.51%;而改進(jìn)布谷鳥算法(AFCS)在第81次迭代后收斂,定位覆蓋率為98.47%。改進(jìn)布谷鳥算法AFCS加快了算法的收斂速度,提高了定位覆蓋率。

3.3 信標(biāo)節(jié)點(diǎn)目標(biāo)位置分布

圖4表示為通信半徑R=15 m時(shí),18個(gè)信標(biāo)節(jié)點(diǎn)目標(biāo)位置分布圖。在此狀態(tài)移動(dòng)信標(biāo)節(jié)點(diǎn)的定位覆蓋率為31.22%;圖5表示為通信半徑R=25 m時(shí),18個(gè)信標(biāo)節(jié)點(diǎn)目標(biāo)位置分布圖,在此狀態(tài)移動(dòng)信標(biāo)節(jié)點(diǎn)的定位覆蓋率為80.57%。

Fig.4 Distribution of 18 target positions at R=15 m圖4 R=15 m時(shí)18個(gè)目標(biāo)位置分布

Fig.5 Distribution of 18 target positions at R=25 m圖5 R=25 m時(shí)18個(gè)目標(biāo)位置分布

4 結(jié)論

本文提出了一種基于改進(jìn)布谷鳥搜索算法(AFCS)的多移動(dòng)信標(biāo)節(jié)點(diǎn)定位算法。該算法以對(duì)未知節(jié)點(diǎn)的定位覆蓋率為目標(biāo)函數(shù),通過RSSI定位、DV-Hop算法和基于AFCS算法的移動(dòng)信標(biāo)節(jié)點(diǎn)兩階段定位過程,提高對(duì)未知節(jié)點(diǎn)的定位覆蓋率。本文引入魚群覓食因子改進(jìn)布谷鳥搜索算法,有效改善了迭代后期因算法變異能力下降而陷入局部最優(yōu)解的狀態(tài),繼而提高了對(duì)未知節(jié)點(diǎn)的定位覆蓋率,加快了算法的收斂速度。綜上所述,該算法在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)改變時(shí)可通過信標(biāo)節(jié)點(diǎn)的移動(dòng)性保持對(duì)未知節(jié)點(diǎn)較高的定位覆蓋率。