遺傳-禁忌搜索優(yōu)化的Amorphous定位算法

胡 偉,袁三男

(上海電力學院電子與信息工程學院,上海 200082)

隨著近距離、低功耗無線通信技術的發(fā)展,無線傳感器網(wǎng)絡WSN(Wireless Sensor Networks)技術在現(xiàn)代社會中扮演著越來越重要的作用[1]。定位技術不僅是無線傳感器網(wǎng)絡技術中重要組成部分,也被人們廣泛應用到生活中的各個領域[2]。在對未知節(jié)點定位的過程中,根據(jù)是否對已知節(jié)點進行實際測量,可以把定位算法分為測量距離定位算法和無距離測量定位算法[3-5]?；诰嚯x測量的定位算法通常有基于到達時間的ToA測距、基于到達時間差的TDoA測距、基于到達角度的AoA測距和基于接收信號強度的RSSI測距等;無需測距的常見算法有質(zhì)心算法、DV-Hop算法、APIT算法和Amorphous算法等。測量距離定位算法對硬件有更高的要求,需要投入更大的成本,所以研究無距離測量定位算法有著重要的意義。

本文主要針對Amorphous算法將通信半徑作為平均每跳距離存在較大誤差,導致定位誤差明顯的特點做了深入分析。為了提高Amorphous算法的定位精度,對算法中的各個參數(shù)包括錨節(jié)點的個數(shù)、節(jié)點通信半徑和總節(jié)點的數(shù)目等參數(shù)優(yōu)化[6]。該方法雖然可以減小誤差,但實用性較差;為減小Amorphous算法在不同通信模型下的定位誤差,可以在該算法離線計算網(wǎng)絡平均連通度的基礎上,建立了四種RSS閾值模型[7],該方法使定位誤差得到抑制,但實現(xiàn)過程較復雜;針對Amorphous算法估計跳數(shù)值誤差大的缺點提出設置跳數(shù)閥值,如果信標節(jié)點距未知節(jié)點跳數(shù)大于此閥值,則其不參與未知節(jié)點定位[8]。但是存在當未知節(jié)點到所有錨節(jié)點的距離都在閾值外時可能會產(chǎn)生無解的情況。

針對Amorphous算法定位誤差大,遺傳算法局部搜索能力較弱、單獨的遺傳算法比較費時的問題,本文提出基于遺傳-禁忌搜索算法對傳統(tǒng)的Amorphous定位算法進行優(yōu)化。首先將傳統(tǒng)Amorphous算法中對未知節(jié)點到錨節(jié)點的最小跳數(shù)的估計值進行修正,即利用接收器的信號強度與跳數(shù)進行一定比例的轉(zhuǎn)換;其次利用禁忌搜索算法的禁忌表策略加強了遺傳算法的局部搜索能力、避免了遺傳算法產(chǎn)生重復解;最后使用遺傳-禁忌搜索算法對優(yōu)化后的Amorphous算法產(chǎn)生的初始解進行優(yōu)化。本文提出的算法降低了Amorphous算法的定位誤差,提高了對未知節(jié)點的定位精度。

1 Amorphous算法

Amorphous是由Radhika Nagpal等提出的定位算法。該算法的實現(xiàn)無需測量距離,通過獲取未知節(jié)點與已知節(jié)點(錨節(jié)點)之間的最小跳數(shù),估計未知節(jié)點位置[9]。該算法分為3個階段:

①計算未知節(jié)點與每個錨節(jié)點之間的最小跳數(shù):錨節(jié)點將含有id、坐標和跳數(shù)(初始化為0)的數(shù)據(jù)包發(fā)送到整個無線傳感器網(wǎng)絡中的鄰居節(jié)點,鄰居節(jié)點收到數(shù)據(jù)包后將跳數(shù)加1,繼續(xù)轉(zhuǎn)發(fā)給相鄰的未知節(jié)點。如此往復,所有未知節(jié)點都將獲得到錨節(jié)點坐標和到錨節(jié)點的跳數(shù),為了使未知節(jié)點保存到錨節(jié)點的跳數(shù)最小,未知節(jié)點將只保留跳數(shù)最小的數(shù)據(jù)包丟棄其他數(shù)據(jù)包。然后利用式(1)計算局部跳數(shù)的平均值代替它與錨節(jié)點之間的最小跳數(shù)hop(i,k);

(1)

式中,h(j,k)和h(i,k)分別表示未知節(jié)點j和未知節(jié)點i到錨節(jié)點k的跳數(shù),|nbrs(i)|表示未知節(jié)點i的鄰居節(jié)點數(shù)目。

②計算未知節(jié)點到每個錨節(jié)點的跳段距離:采用式(2)計算網(wǎng)絡平均連通度,

nlocal=NπR2/S

(2)

式中,N為網(wǎng)絡總節(jié)點數(shù),S為網(wǎng)絡區(qū)域面積,R為網(wǎng)絡中節(jié)點的通信半徑。

無線信號的單跳覆蓋距離使用式(3)計算

(3)

根據(jù)平均每跳距離及距各信標節(jié)點的局部跳數(shù),由式(4)計算未知節(jié)點和各信標節(jié)點間的距離。

d(i,j)=HopSizei×hop(i,j)

(4)

式中,HopSizei表示未知節(jié)點i獲得的平均每跳距離。

③利用三邊測量法或極大似然估計算法,計算未知節(jié)點位置:現(xiàn)假設3個錨節(jié)點的坐標為(X1,Y1)、(X2,Y2)、(X3,Y3),他們與未知節(jié)點W(X、Y)的距離為d1、d2、d3。代入式(5),

(5)

寫成矩陣形式AX=b;三邊測量法估算W的坐標X=A-1b;極大似然估計法估算W的坐標X=(AT-A)-1AT-b。

2 遺傳-禁忌搜索算法

遺傳算法GA(Genetic Algorithm)1975年由美國Michigan大學的Holland教授與其同事首先提出[10],該算法是通過模擬自然進化過程搜索最優(yōu)解的方 法[11]。禁忌搜索算法TS(Tabusearch)最早是由Glover等提出[12],具有獨特的記憶功能,它具有搜索速度快局部搜索能力強等優(yōu)點。在全局搜索方面遺傳算法(GA)較禁忌搜索算法(TS)強,在局部搜索方面的表現(xiàn)則正好相反。基于此本文提出將兩種算法結(jié)合在一起處理定位問題。GA中的選擇過程與TS的移動過程是相似的,它們的目標都是進行單點尋優(yōu)操作以改善解的結(jié)構。在本文中,利用GA迭代特性可以保證全局收斂;利用TS迭代特性可以保證解的多樣性及局部收斂。

2.1 適應度函數(shù)的選取

根據(jù)最近的3個已知節(jié)點及其坐標可以構成未知節(jié)點的非線性方程組:

(6)

那么可以得到適應度函數(shù)為:

(7)

式中(xi,yi)表示的是未知節(jié)點的坐標,(aj,bj)表示的是第j個已知節(jié)點的的坐標,dj表示未知節(jié)點與第j個已知節(jié)點的估計距離。

2.2 選擇算子的選取

從一個群體中選擇優(yōu)良的個體并淘汰劣質(zhì)個體的過程被稱為選擇,而選擇算子是建立在適應度評估值基礎上的。即適應性強的個體,被選為下一代的概率就越大[13]。例如,設種群的個體數(shù)量為100,個體i的適應度用函數(shù)f(i)表示,Pi表示整個種群的適應度總和可用式(8)表示,

(8)

那么此個體被選中的概率用Pix可由式(9)表示

(9)

計算所有個體的適應度值,并對它們按照Pix從大到小的順序進行排序。采用基于適應度的賭輪選擇法,其基本思想是每個個體被選中的概率與其適應度大小成正比。

2.3 交叉率的選取

將種群中的兩個父代個體的部分基因進行替換重組的過程稱為交叉,通過這一操作可以在下一代中得到新型基因的個體。在遺傳算法中,交叉率Pc值的大小是影響遺傳算法性能的一個關鍵因素[14]。自適應遺傳算法中的Pc值可由計算式(10)獲得。

(10)

式中fmax表示群體中最大的適應值,favg表示群體的平均適應值,f表示要交叉的兩個個體中較大的適應值,k1、k2為某一常數(shù)。

Pc值設置過大時,新個體產(chǎn)生的速度快,但是遺傳算法穩(wěn)定性可能也越弱,即具有高適應度的個體結(jié)構可能會被破壞;Pc值設置過小時,遺傳算法的穩(wěn)定性會變強,但會使得到最優(yōu)解的過程變得緩慢。因此在實驗時需要不斷嘗試不同的Pc值對整體算法過程的影響,經(jīng)過多次實驗我們得到Pc=0.6時實驗效果較好,即在選出的下一代個體中以概率為0.6進行基因重組。此外,在交叉重組的過程中,為了避免出現(xiàn)“近親結(jié)合”,基因代碼差異較小的個體不能進行交叉操作。

2.4 禁忌對象和禁忌長度

禁忌對象和禁忌長度是禁忌表中兩個重要的指標。禁忌算法的主要功能是避免一些重復性的操作,即將在計算過程中重復出現(xiàn)的數(shù)值放入到禁忌表中以此禁止對禁忌表中的元素進行操作,我們將禁忌表中的元素稱為禁忌對象。禁忌長度指的是被禁忌對象不允許選取的迭代次數(shù)。

在實際操作中會給被禁對象X一個數(shù)t(禁忌長度),要求被禁對象X在t步迭代內(nèi)被禁。在禁忌表中采用tabu(X)=t記憶,每迭代一步,該項指標做運算tabu(X)=t-1,直到tabu(x)=0時解禁。通過上訴操作后,所有元素將會被分為被禁元素和自由元素。禁忌長度的取值很關鍵。禁忌長度過短,一旦陷入局部最優(yōu)點,出現(xiàn)循環(huán)無法跳出;禁忌長度過長,候選解全部被禁忌,造成計算時間較大,也可能造成計算無法繼續(xù)下去。本文中所用的方法是直接給禁忌長度t賦值為10。

3 遺傳-禁忌搜索優(yōu)化的Amorphous算法

3.1 Amorphous算法的改進

在經(jīng)典Amorphous定位算法中,用式(3)的數(shù)值作為每兩個節(jié)點間的距離的大小,這樣在計算未知節(jié)點實際位置時會產(chǎn)生較大的誤差。例如,當P、Q兩個節(jié)點都在O節(jié)點的通信半徑內(nèi)時且兩個節(jié)點距離O節(jié)點的距離不同時,那么|PO|與|QO|不相等。但是在計算的過程中會被當做一跳處理,即|PO|與|QO|的數(shù)值相等。在現(xiàn)實的無線網(wǎng)絡中這個問題也是普遍存在的。針對經(jīng)典算法中的這一問題本文提出改進方法,即在無線網(wǎng)絡通信中主要采取的是無線電或超聲波的方式傳播信號?？梢栽谛盘栔饕獜姸瓤臻g內(nèi)劃分若干區(qū)間,在接受端檢測出某個節(jié)點的信號強度并就此信號強度轉(zhuǎn)換成相應的跳數(shù)。例如,將信號強度在40 dBm～90 dBm劃分成若干區(qū)間,40 dBm～50 dBm可以將跳數(shù)設置為1,50 dBm～60 dBm跳數(shù)設置為0.8,以此類推。

3.2 遺傳-禁忌搜索優(yōu)化的Amorphous算法

遺傳-禁忌搜索優(yōu)化的Amorphous算法分大致為2個階段,第一階段通過改進后的Amorphous算法獲取未知節(jié)點的初始解;第二階段是將上一階段產(chǎn)生的初始解代入到人工智能算法中進行優(yōu)化。程序流程如圖1所示。

實現(xiàn)算法的具體步驟如下:

Step1根據(jù)錨節(jié)點的坐標使用改進后的Amorphous算法得到未知節(jié)點的坐標作為GATS算法的初始輸入;

Step2計算初始坐標的適應度,判斷是否滿足GA的終止條件,即是否達到最大迭代次數(shù)或者達到最小的誤差要求。滿足這一條件直接輸出結(jié)果;否則進行選擇、交叉操作后將結(jié)果代入到下一步;

Step3上一步產(chǎn)生的結(jié)果產(chǎn)生鄰域解和候選集,首先判斷是否滿足藐視準則,若滿足則直接更新禁忌表、用當前解更替最優(yōu)解;若不滿足,則判斷候選解屬性,將非禁忌對象對應的解作為當前解,更新禁忌表;完成上述步驟后判斷是否滿足TS終止條件,若滿足終止條件返回到上一步;若不滿足終止條件,將在這一步驟中循環(huán)直至達到滿足TS終止條件跳回Step 2。

圖1 遺傳-禁忌搜索優(yōu)化的Amorphous算法流程圖

4 仿真分析

4.1 仿真環(huán)境

為了驗證本文提出的算法在實際操作中的應用效果,在MATLAB平臺進行了IAmorphous-GATS定位算法的仿真實驗。迭代次數(shù)為100,交叉概率為0.6,禁忌表長度為10。為驗證本文提出優(yōu)化算法的優(yōu)化效果,使用Amorphous算法、IAmorphous算法和IAmorphous-GATS定位算法在一定條件下進行對比。

使用歸一化定位誤差比較不同算法的定位性能,

(11)

4.2 仿真實驗與分析

在做仿真實驗的過程中,主要是觀察通信半徑、錨節(jié)點比例及節(jié)點總數(shù)對定位算法的影響。因此,在實驗中采取控制變量法對這三個影響因素分別進行了觀察。為了得到更好的實驗對比效果,本次實驗包括傳統(tǒng)Amorphous定位算法、改進跳數(shù)的IAmorphous-TS(Improved Amorphous Tabu-Search Location)定位算法、IAmorphous-GA(Improved Amorphous Genetic-Algorithm Location)定位算法和IAmorphous-GATS(Improved Amorphous Genetic-Algorithm Tabu-Search Location)。

4.2.1 不同通信半徑

觀察通信半徑對實驗的算法的影響時,控制節(jié)點總數(shù)為100,錨節(jié)點比例為30%。仿真結(jié)果如圖2所示,對于三種定位算法整體來看,都是隨著通信半徑的增加定位的誤差在逐漸減小。最終在通信半徑大于30 m時誤差逐漸趨于平穩(wěn),主要是隨著通信半徑的增加未知節(jié)點到錨節(jié)點的跳數(shù)減小且最終將為某一固定值,計算的位置信息也將不再變動。從仿真結(jié)果可以看出,本文提出的IAmorphous-GATS算法對提高定位精度有較好的效果,雖然IAmorphous-GATS相對于傳統(tǒng)的Amorphous算法誤差有所減小,但是在通信半徑在小于25 m前沒有達到很好的優(yōu)化效果。從仿真數(shù)值上看,IAmorphous-GATS的優(yōu)化效果更加明顯,定位誤差分別比傳統(tǒng)Amorphous定位算法、IAmorphous-TS定位算法、IAmorphous-GA定位算法下降29.3%、24.7%、16.1%。

圖2 通信半徑與定位誤差關系圖

4.2.2 不同錨節(jié)點比例

觀察錨節(jié)點比例對實驗的算法的影響時,控制節(jié)點總數(shù)為100,通信半徑為30 m。從仿真圖中可以看出,如圖3所示,隨著錨節(jié)點比例的增加,定位精度在上升,定位誤差在減小,當錨節(jié)點比例達到20%時,定位誤差逐漸趨于平穩(wěn)。產(chǎn)生這一現(xiàn)象的主要原因是隨著錨節(jié)點比例的增加減小了錨節(jié)點到未知節(jié)點間的跳數(shù),從而減小了錨節(jié)點到未知節(jié)點的距離差值,使得整體的誤差也在減小。從仿真結(jié)果可以看出,本文提出的IAmorphous-GATS定位算法在錨節(jié)點比例在達到30%后定位誤差趨于平穩(wěn)。IAmorphous-GATS算法對修正未知節(jié)點信息有明顯的優(yōu)化效果,與傳統(tǒng)Amorphous定位算法相比有更小的定位誤差,更高的定位精度。從仿真數(shù)值上看,IAmorphous-GATS的優(yōu)化效果明顯,定位誤差分別比傳統(tǒng)Amorphous定位算法、IAmorphous-TS定位算法、IAmorphous-GA定位算法下降30.2%、20.6%、14.7%。

圖3 錨節(jié)點比例與定位誤差關系圖

4.2.3 不同節(jié)點總數(shù)

觀察節(jié)點總數(shù)對實驗的算法的影響時,控制通信半徑為30 m,錨節(jié)點比例為30%。仿真結(jié)果如圖4所示,從仿真結(jié)果中可以看出隨著節(jié)點總數(shù)的增加,整體平均定位誤差在減小。在節(jié)點總數(shù)達到250個時平均定位誤差逐漸趨于平穩(wěn)。從仿真結(jié)果可以看出,本文提出的IAmorphous-GATS定位算法對修正未知節(jié)點信息有更明顯的優(yōu)化效果,與傳統(tǒng)Amorphous定位算法相比有更小的定位誤差,更高的定位精度。從仿真數(shù)值上看,IAmorphous-GATS的優(yōu)化效果更加明顯,定位誤差分別比傳統(tǒng)Amorphous定位算法、IAmorphous-TS定位算法、IAmorphous-GA定位算法下降33.9%、23.3%、13.5%。

圖4 節(jié)點總數(shù)與定位誤差關系圖

4.2.4 算法復雜度

為了解本文提出算法的在實際執(zhí)行時占用時間資源的情況,設置節(jié)點總數(shù)為100、通信半徑為40 m、錨節(jié)點所占比例為30%時算法運行情況。這也說明了IAmorphous-GATS也以一定的算法復雜度換取了定位精度。

表1 算法的運行時間

5 結(jié)論

本文針對傳統(tǒng)的Amorphous定位算法進行了分析,在以Amorphous算法為基礎的條件下進行了未知節(jié)點定位信息的優(yōu)化。首先提出使用劃分區(qū)間的方法在跳數(shù)上增加比例設置,然后對輸出結(jié)果使用遺傳和禁忌搜索算法進行了優(yōu)化。通過仿真實驗結(jié)果可以看出本文提出的對傳統(tǒng)定位算法的優(yōu)化方案降低了定位誤差取得了很好的實驗效果。在保證更高的定位精度的情況下對算法中的各個參數(shù)如何進行調(diào)整以及對算法結(jié)構進行進一步的優(yōu)化是下一步的研究重點。