螞蟻算法在無線傳感網(wǎng)絡(luò)通信中的研究

楊琦

1.引言

無線傳感網(wǎng)絡(luò)的廣泛應(yīng)用背景，更需要開展對(duì)其通信性能等理論研究工作，尤其在航空、軍事、生產(chǎn)控制等方面，不容有半點(diǎn)失誤，因此，如何保障傳感器網(wǎng)絡(luò)之間的性能安全可靠、穩(wěn)定，以及動(dòng)態(tài)自調(diào)整等是關(guān)鍵問題，但目前在無線傳感網(wǎng)絡(luò)領(lǐng)域尚缺仿真方面的理論研究。本文認(rèn)為能實(shí)現(xiàn)對(duì)無線傳感網(wǎng)絡(luò)的通信模擬，可以避免無線傳感網(wǎng)絡(luò)通信應(yīng)用后工作效率不高、預(yù)估各種問題、以及問題出現(xiàn)后的解決方案等。

2.無線傳感網(wǎng)絡(luò)通信的修正仿真算法

為了使用螞蟻算法進(jìn)行無線傳感網(wǎng)絡(luò)通信仿真，必須有效地進(jìn)行算法中的各個(gè)參數(shù)和無線傳感網(wǎng)絡(luò)通信描述的對(duì)應(yīng)。本文設(shè)置給定的n個(gè)傳感器結(jié)點(diǎn)的集合為圖中的節(jié)點(diǎn)，傳感器結(jié)點(diǎn)之間存在流轉(zhuǎn)，則設(shè)對(duì)應(yīng)的圖上有有向邊存在，邊上記錄權(quán)：是若干條件規(guī)則因素組合的代價(jià)Cij（1≤i≤n，1≤j≤n，i≠j），并以此為信息素，這些信息素是根據(jù)上述算法的得出的已運(yùn)行的無線傳感網(wǎng)絡(luò)通信或者根據(jù)用戶經(jīng)驗(yàn)實(shí)現(xiàn)賦值的，然后當(dāng)無線傳感網(wǎng)絡(luò)通信的結(jié)點(diǎn)有變化時(shí)變遷應(yīng)設(shè)計(jì)相應(yīng)的算法使得它能夠在原來的基礎(chǔ)上集成原來的知識(shí)而快速尋出各種新的可能的無線傳感網(wǎng)絡(luò)通信。

（1）無線傳感網(wǎng)絡(luò)通信仿真的修正螞蟻算法的數(shù)學(xué)基礎(chǔ)

若將每個(gè)傳感器結(jié)點(diǎn)看成是圖上的頂點(diǎn)，代價(jià)Cij為連接頂點(diǎn)Vi、Vj邊上的權(quán)，從第n個(gè)傳感器結(jié)點(diǎn)之間向第一個(gè)傳感器結(jié)點(diǎn)引一條有向邊，且邊上的權(quán)值為0信息素，則無線傳感網(wǎng)絡(luò)通信仿真系統(tǒng)最終希望得到的是在一個(gè)具有n個(gè)節(jié)點(diǎn)的完全圖上找到一條有效無線傳感網(wǎng)絡(luò)通信的回路，其中假若無線傳感網(wǎng)絡(luò)通信執(zhí)行中有任務(wù)反饋再執(zhí)行，也由于其前驅(qū)結(jié)點(diǎn)的不同而認(rèn)為是不同的結(jié)點(diǎn)。蟻群由m>n個(gè)螞蟻組成，它們獨(dú)立地按下面的步驟工作，所完成的算法就是無線傳感網(wǎng)絡(luò)通信仿真的修正螞蟻算法（Sensor Correct Ants：SCA）。

（2）FCA算法描述

FCA算法的設(shè)計(jì)是：

1）m個(gè)螞蟻獨(dú)立選擇一個(gè)起始傳感器結(jié)點(diǎn)（初始化）;

2）應(yīng)用狀態(tài)轉(zhuǎn)移規(guī)則及局部修正規(guī)則尋出一個(gè)無線傳感網(wǎng)絡(luò)通信路選上的環(huán);

3）進(jìn)行全局信息素的修正。

本文的螞蟻算法可歸納如下：

1）分別對(duì)其在圖G中各邊上的信息度進(jìn)行初始化;

2）取一組螞蟻（由M個(gè)不同種類的螞蟻組成），將其中每一個(gè)都隨機(jī)地放到設(shè)定為起始初始節(jié)點(diǎn)的傳感器結(jié)點(diǎn);

3）令每個(gè)螞蟻分別根據(jù)下面的轉(zhuǎn)移概率準(zhǔn)則尋找下一個(gè)新傳感器結(jié)點(diǎn)，在選路過程中，若一個(gè)螞蟻在未到達(dá)目的節(jié)點(diǎn)前發(fā)現(xiàn)此次路徑已行不通，則其退回上一節(jié)點(diǎn)（年齡減去所退回的路徑對(duì)應(yīng)的時(shí)延），重新選擇其他路徑;若某一個(gè)螞蟻未到達(dá)目的節(jié)點(diǎn)就已死亡，則應(yīng)在初始點(diǎn)重新發(fā)送一個(gè)同類的螞蟻。當(dāng)成功地完成了任務(wù)流轉(zhuǎn)，則利用下面的局部調(diào)整準(zhǔn)則修改這兩個(gè)節(jié)點(diǎn)間路徑上的信息素（稱為局部信息素修正）。重復(fù)該步驟直到流轉(zhuǎn)至第n個(gè)傳感器結(jié)點(diǎn)，最后回到初始狀態(tài)。

4）對(duì)所有邊上的信息素進(jìn)行修正（稱為全局信息素修正 ）。

5）在這N組中，依據(jù)選取綜合效應(yīng)最佳（即代價(jià)函數(shù)值最?。┑囊唤M螞蟻所選擇的無線傳感網(wǎng)絡(luò)通信路徑結(jié)果，利用下面的全局調(diào)整準(zhǔn)則對(duì)其進(jìn)行信息度的全局調(diào)整;

6）重復(fù)（3）～（5），直到所有螞蟻的收斂至同一最優(yōu)的無線傳感網(wǎng)絡(luò)通信路徑為止。

值得說明的是，上述螞蟻仿真無線傳感網(wǎng)絡(luò)通信路選算法在初始一段時(shí)間內(nèi)尋找有效無線傳感網(wǎng)絡(luò)通信路徑的速度相對(duì)要慢些，這是由于隨機(jī)選擇無線傳感網(wǎng)絡(luò)通信路選過程中會(huì)出現(xiàn)螞蟻死亡（傳感器尚失通信能力等）的情況。為了加快螞蟻的路徑選取速度，可以對(duì)上述算法加以適當(dāng)調(diào)整，即在初始時(shí)，對(duì)每個(gè)傳感器結(jié)點(diǎn)，構(gòu)造滿足其時(shí)延條件的路由表，并在上述螞蟻算法執(zhí)行過程中，限制螞蟻在規(guī)定的規(guī)則庫表中選取通信路徑中針對(duì)當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)，這樣就避免了螞蟻死亡所造成的時(shí)間浪費(fèi)，從而在很大程度上節(jié)省了各螞蟻成功地選取其所對(duì)應(yīng)的有效無線傳感網(wǎng)絡(luò)通信路徑所需的時(shí)間。

（3）算法的偽代碼表示

Begin：

初始化

Repeat for i ：=1 to m do

狀態(tài)轉(zhuǎn)移、局部修正、構(gòu)造無線傳感網(wǎng)絡(luò)通信路徑（每個(gè)螞蟻都構(gòu)造）

全局信息素修正（對(duì)最好的無線傳感網(wǎng)絡(luò)通信路徑）

Unitl 結(jié)束條件

End

（4）算法中的狀態(tài)轉(zhuǎn)移規(guī)則

在FCA中需要進(jìn)行傳感器結(jié)點(diǎn)的狀態(tài)轉(zhuǎn)移，依據(jù)的是狀態(tài)轉(zhuǎn)移規(guī)則，也即螞蟻選擇下一傳感器結(jié)點(diǎn)的概率（公式1[7]）是由兩傳感器結(jié)點(diǎn)連接邊上的代價(jià)和信息素決定的。

（1）

式中表示螞蟻 K從第r個(gè)傳感器結(jié)點(diǎn)流轉(zhuǎn)至第s個(gè)傳感器結(jié)點(diǎn)的概率;表示螞蟻儲(chǔ)在邊上的信息素;，表示邊對(duì)應(yīng)的代價(jià);表示螞蟻K在第r個(gè)傳感器結(jié)點(diǎn)時(shí)還沒有流轉(zhuǎn)至的傳感器結(jié)點(diǎn)集合;β>0為由信息素與代價(jià)的相對(duì)重要性來確定的參數(shù)。

式（1）表明螞蟻從狀態(tài)r轉(zhuǎn)移到狀態(tài)s所選傳感器結(jié)點(diǎn)的概率隨著信息素的增大而增大，隨著代價(jià)的增大而減少，即狀態(tài)轉(zhuǎn)移規(guī)則是螞蟻喜歡朝信息素大代價(jià)小的下一個(gè)傳感器結(jié)點(diǎn)轉(zhuǎn)移。

（5）算法中的全局信息素修正規(guī)則

為了分配更多的信息素到最佳的無線傳感網(wǎng)絡(luò)通信路徑所在邊上，必須修正信息素。另外一個(gè)目的就是模仿真實(shí)的螞蟻不僅存儲(chǔ)信息素還適當(dāng)蒸發(fā)它們。因此，一旦m個(gè)螞蟻按照公式（1）完成了一次圖的遍歷（即找到一個(gè)較佳的無線傳感網(wǎng)絡(luò)通信仿真結(jié)果）后，則必須用公式（2）修改各邊上的信息素量。

（2）

其中，0<α<1是用來蒸發(fā)儲(chǔ)在邊上的信息素的參數(shù)，LK是螞蟻K得到的無線傳感網(wǎng)絡(luò)通信所對(duì)應(yīng)的路徑上的代價(jià)和。全局修正規(guī)則不是由個(gè)別螞蟻來實(shí)現(xiàn)，而是通過圖的邊來存儲(chǔ)，起到了一個(gè)分布式長期記憶的效果。

（6）變異FCA算法

上述螞蟻算法對(duì)較小規(guī)模的傳感器結(jié)點(diǎn)（n個(gè)）情況下求解最佳仿真無線傳感網(wǎng)絡(luò)通信十分有效;但隨著n的增大，效果明顯下降。針對(duì)這一問題，本文又提出了變異FCA算法。該算法同前一算法描述一致，改進(jìn)之處就是在狀態(tài)轉(zhuǎn)移，修正規(guī)則中引進(jìn)了變異運(yùn)算，以避免原算法在大規(guī)模的傳感器結(jié)點(diǎn)情況出現(xiàn)局部最優(yōu)。

1）FCA的狀態(tài)轉(zhuǎn)移規(guī)則

一個(gè)螞蟻在傳感器結(jié)點(diǎn)r執(zhí)行后將按照下面的式子確定轉(zhuǎn)移至的下一個(gè)傳感器結(jié)點(diǎn)s：

S2隨機(jī)地從JK（r）中選取，q為[0，1]上的隨機(jī)數(shù)，q0為參數(shù)（0

2）FCA的全局修正規(guī)則

FCA的全局修正規(guī)則如下：α是信息素消散參數(shù)。0<α<1，Lab是m個(gè)螞蟻中最好遍歷代價(jià)之和。

與前一算法比較，F(xiàn)lowNAA的全局修正規(guī)則只是讓實(shí)現(xiàn)最好遍歷的螞蟻釋放信息素。它只是在已有的無線傳感網(wǎng)絡(luò)通信程內(nèi)搜索出新的無線傳感網(wǎng)絡(luò)通信，這不僅適應(yīng)實(shí)際的情況（無線傳感網(wǎng)絡(luò)通信仿真是在若干可以選擇的無線傳感網(wǎng)絡(luò)通信中選擇一條較優(yōu)的，或者根據(jù)需要對(duì)原有的無線傳感網(wǎng)絡(luò)通信進(jìn)行修改），從而提高求解的速度。

3）FCA的局部修正規(guī)則

若螞蟻從節(jié)點(diǎn)r向結(jié)點(diǎn)s轉(zhuǎn)移，則規(guī)定螞蟻在這條邊上存儲(chǔ)一定的信息素修正規(guī)則如下：

這個(gè)局部修正規(guī)則保證避免搜索陷入局部極小陷阱，同時(shí)又給最佳的無線傳感網(wǎng)絡(luò)通信路徑各邊增加信息素。