楊琦

1.引言

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

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

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

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

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

（2）FCA算法描述

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

1）m個螞蟻獨立選擇一個起始傳感器結(jié)點（初始化）;

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

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

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

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

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

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

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

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

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

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

（3）算法的偽代碼表示

Begin：

初始化

Repeat for i ：=1 to m do

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

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

Unitl 結(jié)束條件

End

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

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

（1）

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

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

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

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

（2）

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

（6）變異FCA算法

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

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

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

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

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

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

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

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

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

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