荊夏磊,喬學(xué)工

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

0 引言

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

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

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

1 算法模型

1.1 RSSI信號衰減模型

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

(1)

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

(2)

1.2 信標(biāo)節(jié)點移動目標(biāo)函數(shù)

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

(3)

(4)

(5)

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

2 多移動信標(biāo)節(jié)點定位算法

2.1 初步定位

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

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

2.1.1 RSSI定位

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

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

可得以下的方程組:

(6)

化簡為線性方程的形式:AX=b

(7)

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

X*=(ATA)-1ATb

(8)

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

2.1.2DVHop定位

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

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

(9)

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

2.2 精確定位

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

2.2.1 布谷鳥搜索算法

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

?L(λ) ，

(10)

(11)

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

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

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

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

AF-CS算法步驟如下:

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

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

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

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

2.3 定位算法步驟

具體的定位步驟如下:

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

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

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

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

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

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

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

3 仿真分析

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

3.1 信標(biāo)節(jié)點移動對定位覆蓋率的影響

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

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

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

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

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

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

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 改進算法對定位覆蓋率的影響

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

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

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

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

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

4 結(jié)論

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