螞蟻算法在無線傳感網絡通信中的研究

楊琦

1.引言

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

2.無線傳感網絡通信的修正仿真算法

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

（1）無線傳感網絡通信仿真的修正螞蟻算法的數學基礎

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

（2）FCA算法描述

FCA算法的設計是：

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

2）應用狀態轉移規則及局部修正規則尋出一個無線傳感網絡通信路選上的環;

3）進行全局信息素的修正。

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

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

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

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

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

5）在這N組中，依據選取綜合效應最佳（即代價函數值最小）的一組螞蟻所選擇的無線傳感網絡通信路徑結果，利用下面的全局調整準則對其進行信息度的全局調整;

6）重復（3）～（5），直到所有螞蟻的收斂至同一最優的無線傳感網絡通信路徑為止。

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

（3）算法的偽代碼表示

Begin：

初始化

Repeat for i ：=1 to m do

狀態轉移、局部修正、構造無線傳感網絡通信路徑（每個螞蟻都構造）

全局信息素修正（對最好的無線傳感網絡通信路徑）

Unitl 結束條件

End

（4）算法中的狀態轉移規則

在FCA中需要進行傳感器結點的狀態轉移，依據的是狀態轉移規則，也即螞蟻選擇下一傳感器結點的概率（公式1[7]）是由兩傳感器結點連接邊上的代價和信息素決定的。

（1）

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

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

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

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

（2）

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

（6）變異FCA算法

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

1）FCA的狀態轉移規則

一個螞蟻在傳感器結點r執行后將按照下面的式子確定轉移至的下一個傳感器結點s：

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

2）FCA的全局修正規則

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

與前一算法比較，FlowNAA的全局修正規則只是讓實現最好遍歷的螞蟻釋放信息素。它只是在已有的無線傳感網絡通信程內搜索出新的無線傳感網絡通信，這不僅適應實際的情況（無線傳感網絡通信仿真是在若干可以選擇的無線傳感網絡通信中選擇一條較優的，或者根據需要對原有的無線傳感網絡通信進行修改），從而提高求解的速度。

3）FCA的局部修正規則

若螞蟻從節點r向結點s轉移，則規定螞蟻在這條邊上存儲一定的信息素修正規則如下：

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