楊琦
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ò)通信路徑各邊增加信息素。