劉 偉,李 卓,楊曉斐,楊麗燕

(1.桂林理工大學(xué)信息科學(xué)與工程學(xué)院,桂林 541006,;2.桂林理工大學(xué)廣西嵌入式技術(shù)與智能系統(tǒng)重點(diǎn)實(shí)驗(yàn)室,桂林 541006)

無(wú)線傳感器網(wǎng)絡(luò)是一種由大量結(jié)構(gòu)簡(jiǎn)單、廉價(jià)的傳感器集成無(wú)線通信接口所組成的網(wǎng)絡(luò),它在環(huán)境監(jiān)測(cè)、災(zāi)難救助、目標(biāo)跟蹤等領(lǐng)域都有廣泛的應(yīng)用前景。在這些應(yīng)用中,傳感器節(jié)點(diǎn)的自我定位非常重要,因?yàn)闆](méi)有和具體的坐標(biāo)聯(lián)系在一起的監(jiān)測(cè)信息通常是沒(méi)有意義的。同時(shí),如基于地理信息的路由等無(wú)線傳感器網(wǎng)絡(luò)協(xié)議也需要節(jié)點(diǎn)的位置信息作為支撐。因此節(jié)點(diǎn)定位問(wèn)題是無(wú)線傳感器網(wǎng)絡(luò)的重要研究?jī)?nèi)容之一[1-3]。

根據(jù)是否需要測(cè)量節(jié)點(diǎn)之間的距離,無(wú)線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)定位方法可以劃分為基于測(cè)距和基于非測(cè)距的兩種方法。其中基于測(cè)距的方法,由于定位精度高在無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位中被廣泛采用?；跍y(cè)距的定位方法首先要測(cè)量節(jié)點(diǎn)之間的距離或角度。常用的測(cè)量方法有接收信號(hào)強(qiáng)度指示RSSI(Received Signal Strength Indicator)[4-5]、到達(dá)時(shí)間TOA(Time of Arrival)[6-7]、到達(dá)時(shí)間不同TDOA(Time Difference of Arrival)[8-9]和到達(dá)角度AOA(Angle of Arrival)[10-11]。在獲得距離或角度信息以后,基于測(cè)距的方法即可以采用各種方法對(duì)未知節(jié)點(diǎn)進(jìn)行定位。

目前對(duì)無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位的研究主要集中在二維空間,而在實(shí)際應(yīng)用中,傳感器節(jié)點(diǎn)通常分布在三維空間內(nèi),需要節(jié)點(diǎn)的三維空間信息,如海洋、山地、森林及各種空間飛行器等。因此非常有必要研究無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的三維節(jié)點(diǎn)定位方法。

獲取節(jié)點(diǎn)之間的距離或角度信息后,基于測(cè)距的方法就可以采用一些定位方法對(duì)未知節(jié)點(diǎn)進(jìn)行定位,其中一類方法是把獲取的距離或角度信息看作約束條件,將其轉(zhuǎn)化為一個(gè)目標(biāo)函數(shù),然后用各種優(yōu)化算法尋找該目標(biāo)函數(shù)的最小值,從而對(duì)未知節(jié)點(diǎn)進(jìn)行定位。優(yōu)化方法可分為傳統(tǒng)的優(yōu)化方法和生物啟發(fā)式優(yōu)化方法。

傳統(tǒng)的優(yōu)化方法基于確定的搜索策略,在滿足一定的限制條件下,利用優(yōu)化問(wèn)題的導(dǎo)數(shù)、梯度等數(shù)學(xué)性質(zhì)進(jìn)行求解。該類方法的缺點(diǎn)是運(yùn)算復(fù)雜度較高,并且隨著問(wèn)題的維數(shù)的增大其復(fù)雜度以指數(shù)倍增加,生物啟發(fā)式優(yōu)化方法可以有效地避免這個(gè)問(wèn)題,使計(jì)算更加有效,對(duì)優(yōu)化問(wèn)題所對(duì)應(yīng)的函數(shù)形式不做任何假設(shè),而且不要求目標(biāo)函數(shù)的連續(xù)性或可導(dǎo)性的假設(shè),算法簡(jiǎn)單,易于實(shí)現(xiàn)。

常見(jiàn)的生物啟發(fā)式優(yōu)化算法包括:模擬退火算法SA(Simulated Annealing)[12-13]、蟻群算法ACO(Ant Colony Optimization)[14]、遺傳算法GA(Genetic Algorithm)[15-16]、人工蜂群算法ABC(Artificial Bee Colony)[17]、細(xì)菌覓食算法BFA(Bacterial Foraging Algorithm)[18]、粒子群算法PSO(Particle Swarm Optimization)[18-20]。與其他生物啟發(fā)式優(yōu)化算法相比,粒子群算法具有容易執(zhí)行,收斂速度比較快的優(yōu)點(diǎn)。尤其是求解的問(wèn)題維數(shù)越多,其優(yōu)勢(shì)越明顯[18]。因此,粒子群算法非常適用于無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的三維定位。但是,在運(yùn)行過(guò)程中,粒子群算法可能會(huì)陷入局部最優(yōu),出現(xiàn)早熟收斂現(xiàn)象。避免粒子群算法出現(xiàn)早熟收斂現(xiàn)象的措施之一是增加粒子的多樣性,而SCE-UA(Shuffling Complex Evolution-University of Arizona)算法中的洗牌策略可以很好地保持粒子的多樣性,因此,為了克服粒子群算法的這一缺點(diǎn),我們結(jié)合SCE-UA(Shuffling Complex Evolution-University of Arizona)算法,提出了兩種基于SCE-PSO的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)三維定位方法。

本文剩余部分安排如下:第一節(jié)簡(jiǎn)單介紹一下粒子群算法和SCE-UA算法;第二節(jié)詳細(xì)介紹我們提出的兩種基于SCE-PSO的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)三維定位方法;第三節(jié)為仿真分析;最后一節(jié)對(duì)本文作出總結(jié)。

1 粒子群算法和SCE-UA算法概述

1.1 粒子群算法

粒子群優(yōu)化算法是1995年由Kennedy和Eberhart共同提出的,其起源于人們對(duì)鳥群等群居性動(dòng)物覓食行為的研究[21]。粒子群優(yōu)化算法的基本思想是:將優(yōu)化問(wèn)題的每一個(gè)解看作一個(gè)微粒,每個(gè)微粒在多維搜索空間中以一定的速度飛行,通過(guò)目標(biāo)函數(shù)的適應(yīng)度值衡量微粒的優(yōu)劣,每個(gè)微粒能夠通過(guò)自己的飛行經(jīng)驗(yàn)以及其他微粒的飛行經(jīng)驗(yàn),動(dòng)態(tài)地調(diào)整自己的飛行速度,從而向群體中最好的微粒位置飛行,最終搜索到優(yōu)化問(wèn)題的最優(yōu)解。

xi(t+1)=xi(t)+vi(t+1)

(1)

vi(t+1)=w·vi(t)+c1r1[pi-xi(t)]+c2r2[g-xi(t)]

(2)

式中:pi是第i個(gè)粒子自己所找到的最優(yōu)解,g是整個(gè)總?cè)核业降淖顑?yōu)解,w是慣性權(quán)重,c1和c2是學(xué)習(xí)因子,一般選取c1=c2=2;r1和r2是在(0,1)區(qū)間上服從均勻分布的隨機(jī)數(shù)。

為了防止粒子遠(yuǎn)離搜索空間,粒子的飛行速度v都被限制在[-vmax,vmax]之間。vmax較大,可以保證粒子種群的全局搜索能力;vmax較小,則粒子種群的局部搜索能力加強(qiáng)。

1.2 SCE-UA算法

SCE-UA算法是由美國(guó)亞利桑那州大學(xué)的Qingyun Duan博士在1992年提出的,它是一種有效的解決非線性約束最優(yōu)化問(wèn)題的方法[22]。目前其主要運(yùn)用在流域水文模型的參數(shù)優(yōu)選。SCE-UA算法基本思路是將基于確定性的復(fù)合形搜索技術(shù)和自然界中生物競(jìng)爭(zhēng)進(jìn)化原理相結(jié)合,用來(lái)求解最小化問(wèn)題,融合了確定性方法、隨機(jī)性方法、競(jìng)爭(zhēng)進(jìn)化、復(fù)合形混合等概念,從而保證了SCE-UA算法搜索的靈活性、全局性、一致性和有效性等。SCE-UA算法的最要步驟如下:

①初始化。假定待優(yōu)化的問(wèn)題是n維問(wèn)題,選取參與進(jìn)化的復(fù)合形個(gè)數(shù)p(p≥1)和每個(gè)復(fù)合形所包含的頂點(diǎn)數(shù)目m(m≥n+1),并計(jì)算樣本點(diǎn)數(shù)目s=p×m。

②產(chǎn)生樣本點(diǎn)。在可行域內(nèi)隨機(jī)產(chǎn)生s個(gè)樣本點(diǎn)x1,x2,…,xs,分別計(jì)算每一個(gè)點(diǎn)xi的函數(shù)值fi=f(xi),i=1,2,…,s。

③樣本點(diǎn)排序。把s個(gè)樣本點(diǎn)(xi,fi)按照函數(shù)值的升序排列,排序后仍記為(xi,fi),i=1,2,…,s,也就是f1≤f2≤…≤fs,記D={(xi,fi),i=1,2,…,s}。

⑤復(fù)合形進(jìn)化。按照下山單純形算法分別進(jìn)化每一個(gè)復(fù)合形。

⑥復(fù)合形混合。把進(jìn)化后的每個(gè)復(fù)合形的所有頂點(diǎn)組合成新的點(diǎn)集,再次按函數(shù)值fi的升序排列,排序后仍記為D,對(duì)D按目標(biāo)函數(shù)的升序進(jìn)行排列。

⑦收斂性判斷。如果滿足收斂條件則停止迭代,否則回到第④步。

SCE-UA算法的參數(shù)雖然較多,但絕大部分取值都可以采用已有研究成果的默認(rèn)值,只有復(fù)合形個(gè)數(shù)p需要根據(jù)具體問(wèn)題確定。根據(jù)文獻(xiàn)[22]推薦m=2n+1,q=n+1,s=p×m,α=1,β=2n+1。其中n為參數(shù)的個(gè)數(shù),m為每個(gè)復(fù)合形頂點(diǎn)的個(gè)數(shù),q為每個(gè)子復(fù)合形的頂點(diǎn)數(shù),s為種群大小,α和β為下山單純形算法中父代產(chǎn)生的子代的個(gè)數(shù)及代數(shù)。

2 基于SCE-PSO的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)三維定位方法

2.1 無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的三維定位目標(biāo)函數(shù)

假設(shè)在三維空間中,無(wú)線傳感器網(wǎng)絡(luò)中的未知節(jié)點(diǎn)的坐標(biāo)是(x,y,z),錨節(jié)點(diǎn)的坐標(biāo)分別為(x1,y1,z1),(x2,y2,z2),…,(xn,yn,zn),未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離分別為d1,d2,…,dn。由此,我們可以得出如下的式(3)。

(3)

因此,無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)三維定位的目標(biāo)函數(shù)可以定義為:

(4)

2.2 基于SCE-PSO的優(yōu)化算法

粒子群優(yōu)化算法中的速度更新式(2)有三部分組成,第一部分是粒子先前的速度,說(shuō)明了粒子目前的狀態(tài),具有平衡全局和局部搜索的能力;第二部分是認(rèn)知部分,表示粒子本身的思考,使粒子具有足夠強(qiáng)的全局搜索能力,避免局部極小;第三部分為社會(huì)部分,體現(xiàn)了粒子間的信息共享,這使得PSO能夠迅速找到最優(yōu)解。

粒子群算法在運(yùn)行的過(guò)程中,如果某一個(gè)粒子發(fā)現(xiàn)一個(gè)當(dāng)前最優(yōu)位置,其他粒子將迅速向其靠近,如果該最優(yōu)位置只是一個(gè)局部最優(yōu)點(diǎn),粒子群在搜索的過(guò)程中可能無(wú)法跳出這個(gè)局部最優(yōu)點(diǎn),因此會(huì)陷入局部最優(yōu),出現(xiàn)早熟收斂現(xiàn)象。避免粒子群算法出現(xiàn)早熟收斂現(xiàn)象的措施之一是增加粒子的多樣性。在此我們借鑒SCE-UA算法,提出了兩個(gè)基于SCE-PSO的優(yōu)化方法SCE-PSO1和SCE-PSO2。

在傳統(tǒng)的SCE-UA算法中,采用的是下山單純形算法進(jìn)化每一個(gè)復(fù)合形。但是下山單純形算法是用多面體來(lái)逐步逼近問(wèn)題的最佳值。如果待優(yōu)化問(wèn)題的維數(shù)比較大,其進(jìn)化過(guò)程就顯得比較復(fù)雜,所求出的解得質(zhì)量也不高,而且收斂速度也相對(duì)緩慢。由于無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)三維定位的維數(shù)較大,因此不適合用該方法進(jìn)行定位。而粒子群算法沒(méi)有選擇、交叉、變異等操作,其收斂速度較快,而且收斂速度受優(yōu)化問(wèn)題維數(shù)的影響也比較小,因此比較適用于無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的三維定位。

鑒于上述思想,我們提出了SCE-PSO1算法。在該算法中,我們用粒子群算法代替下山單純形算法去進(jìn)化SCE-UA算法中每一個(gè)復(fù)合形。這樣可以克服傳統(tǒng)SCE-UA算法的缺點(diǎn),提高收斂速度,增加求解高維數(shù)問(wèn)題的解的質(zhì)量;同時(shí)也可以利用SCE-UA算法中的洗牌策略(復(fù)合形混合之后,再重新劃分)保持粒子的多樣性,從而克服粒子群算法的缺點(diǎn),減少其出現(xiàn)早熟收斂的概率。

在SCE-PSO1算法中,采用粒子群算法進(jìn)化每一個(gè)復(fù)合形。每一個(gè)復(fù)合形在進(jìn)化過(guò)程中,其粒子的速度用式(2)更新。在式(2)中,pi是第i個(gè)粒子自己所找到的最優(yōu)解,g是該復(fù)合形中的粒子所找到的最優(yōu)解。因此式(2)并沒(méi)有體現(xiàn)進(jìn)化過(guò)程中各個(gè)復(fù)合形之間信息的共享。為了加快收斂速度,提高解的質(zhì)量,我們提出了SCE-PSO2算法。在SCE-PSO2算法中,每一個(gè)復(fù)合形在進(jìn)化過(guò)程中,其粒子的速度不再使用式(2)更新,而是用下面的式(5)進(jìn)行更新。

vi(t+1)=w·vi(t)+c1·r1[pi-xi(t)]+
c2·r2[g-xi(t)]+c3·r3[e-xi(t)]

(5)

在式(5)中,pi是復(fù)合形中第i個(gè)粒子本身找到的最優(yōu)解,g是該復(fù)合形中的粒子找到的最優(yōu)解,e是所有復(fù)合形中的粒子找到的最優(yōu)解。w是慣性權(quán)重,c1、c2和c3是學(xué)習(xí)因子,r1、r2和r3是在(0,1)區(qū)間上服從均勻分布的隨機(jī)數(shù)。式(5)包含四個(gè)部分,其中前三個(gè)部分與式(2)相同,第四部分表示進(jìn)化過(guò)程中各個(gè)復(fù)合形之間信息的共享。

3 仿真分析

為了驗(yàn)證我們提出的SCE-PSO1和SCE-PSO2算法的性能,我們選取PSO和SCE-UA算法與其作對(duì)比,并使用MATLAB R2013a軟件進(jìn)行仿真。我們?cè)谶呴L(zhǎng)為100 m的立方體網(wǎng)絡(luò)區(qū)域中放置了125個(gè)節(jié)點(diǎn),節(jié)點(diǎn)的分布為均勻分布,節(jié)點(diǎn)間距離是20 m(存在0～2 m的隨機(jī)誤差)。

為了保證算法可比性,4種算法的群體規(guī)模均取為14,PSO、SCE-PSO1和SCE-PSO2算法中的慣性權(quán)重w采用自適應(yīng)調(diào)整策略:w=wmax-t(wmax-wmin)/T,其中t指當(dāng)前的迭代次數(shù),T指最大的迭代次數(shù),T=20;wmax=0.9;wmin=0.4。PSO和SCE-PSO1算法中粒子的最大飛行速度wmax=20.tif;SCE-PSO2算法中粒子的最大飛行速度wmax=50.tif;SCE-UA算法中復(fù)合形的個(gè)數(shù)p=2,其余參數(shù)按照文獻(xiàn)[22]的推薦選取,即問(wèn)題的維數(shù)n=3,每個(gè)復(fù)合形頂點(diǎn)的個(gè)數(shù)m=7;下山單純形算法中每個(gè)子復(fù)合形的頂點(diǎn)數(shù)q=4;父代產(chǎn)生的子代個(gè)數(shù)α=1;產(chǎn)生的子代的代數(shù)β=7。

我們仿真了不同錨節(jié)點(diǎn)數(shù)量、不同通信半徑和不同測(cè)距誤差下,上述4種方法的平均定位誤差。平均定位誤差采用下式計(jì)算:

(6)

3.1 不同錨節(jié)點(diǎn)數(shù)量的仿真對(duì)比

本次仿真節(jié)點(diǎn)的通信半徑為50 m,測(cè)距誤差為均值為0,標(biāo)準(zhǔn)差為4的高斯噪聲。仿真結(jié)果如圖1所示。

圖1 不同錨節(jié)點(diǎn)數(shù)量的仿真性能

從圖1中可以看出,隨著錨節(jié)點(diǎn)數(shù)量的增大,4種優(yōu)化算法的平均定位誤差逐漸降低。這是由于節(jié)點(diǎn)總數(shù)與通信半徑一定時(shí),錨節(jié)點(diǎn)越多,參與未知節(jié)點(diǎn)定位的錨節(jié)點(diǎn)越多,節(jié)點(diǎn)的定位信息越豐富。從圖1中還可以看出,SCE-PSO2算法的性能是最好的,其次是SCE-PSO1算法,而PSO算法的性能最差。

3.2 不同通信半徑的仿真對(duì)比

本次仿真錨節(jié)點(diǎn)的數(shù)量為15,測(cè)距誤差為均值為0,標(biāo)準(zhǔn)差為4的高斯噪聲。仿真結(jié)果如圖2所示。

從圖2中可以看出,隨著通信半徑的增大,4種優(yōu)化算法的平均定位誤差逐漸降低。這是由于節(jié)點(diǎn)總數(shù)與錨節(jié)點(diǎn)數(shù)量一定時(shí),通信半徑越大,參與未知節(jié)點(diǎn)定位的錨節(jié)點(diǎn)越多,節(jié)點(diǎn)的定位信息越豐富。從圖1中還可以看出,SCE-PSO2算法的性能是最好的,其次是SCE-PSO1算法,而PSO算法的性能最差。

圖2 不同通信半徑的仿真性能

3.3 不同測(cè)距誤差的仿真對(duì)比

本次仿真錨節(jié)點(diǎn)的數(shù)量為15,節(jié)點(diǎn)的通信半徑為50 m,測(cè)距誤差為均值為0的高斯噪聲。我們仿真了不同仿真噪聲標(biāo)準(zhǔn)差下,4種優(yōu)化算法的平均定位誤差,仿真結(jié)果如圖3所示。

從圖3中可以看出,隨著測(cè)距誤差的增大,4種優(yōu)化算法的平均定位誤差逐漸增加。這是由于測(cè)距誤差越大,測(cè)量距離與真實(shí)距離的偏差越大,因此節(jié)點(diǎn)的定位越不準(zhǔn)確。從圖3中還可以看出,SCE-PSO2算法的性能是最好的,其次是SCE-PSO1算法,而PSO算法的性能最差。

圖3 不同測(cè)距誤差的仿真性能

綜合上面的三個(gè)仿真結(jié)果,可以看出,我們提出的SCE-PSO1和SCE-PSO2算法的性能均優(yōu)于原始的PSO和SCE算法,而且SCE-PSO2算法的性能要優(yōu)于SCE-PSO1算法。這是因?yàn)榕c原始PSO算法相比,在SCE-PSO1和SCE-PSO2算法中,我們引入了洗牌策略,增加了粒子的多樣性,從而減少了PSO算法出現(xiàn)早熟收斂的概率;而與原始SCE算法相比,在SCE-PSO1和SCE-PSO2算法中,我們用PSO算法取代受維數(shù)影響較大的下山單純形算法去進(jìn)化每個(gè)復(fù)合形,從而提高了搜索速度和解的質(zhì)量。而與SCE-PSO1算法相比,在SCE-PSO2算法中,我們?cè)诹Ｗ拥母滤俣仁?5)中,引入了各個(gè)復(fù)合形之間信息的共享,從而進(jìn)一步提高了搜索速度和解的質(zhì)量。

4 結(jié)論

本文提出了SCE-PSO1和SCE-PSO2兩種無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)三維定位方法,其綜合了PSO和SCE兩種優(yōu)化方法的優(yōu)點(diǎn),減輕了PSO方法中粒子早熟收斂的現(xiàn)象,同時(shí)改善了SCE-UA方法受問(wèn)題維數(shù)影響較大的缺點(diǎn),因此,SCE-PSO1和SCE-PSO2方法非常適用于無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的三維定位。仿真結(jié)果證明,SCE-PSO1和SCE-PSO2兩種方法的性能均優(yōu)于原始的PSO和SCE兩種方法,而且由于在SCE-PSO2中增加了各個(gè)復(fù)合形之間信息的共享,其性能要優(yōu)于SCE-PSO1方法。