基于鏈路權(quán)重的無線傳感器網(wǎng)絡(luò)蟻群路由算法

◆李 璐

(大連海洋學(xué)校實(shí)驗(yàn)中心 遼寧 116023)

安全模型、算法與編程

基于鏈路權(quán)重的無線傳感器網(wǎng)絡(luò)蟻群路由算法

◆李 璐

(大連海洋學(xué)校實(shí)驗(yàn)中心 遼寧 116023)

本文針對無線傳感器網(wǎng)絡(luò)存在網(wǎng)絡(luò)擁塞進(jìn)而造成網(wǎng)絡(luò)服務(wù)質(zhì)量急劇下降的問題，提出了一種基于鏈路權(quán)重的無線傳感器網(wǎng)絡(luò)蟻群路由改進(jìn)算法。該算法通過分析可用帶寬、傳輸時延兩個影響鏈路狀態(tài)的因素來計算鏈路的權(quán)重，根據(jù)鏈路權(quán)重來調(diào)整信息素的大小，直接反映了網(wǎng)絡(luò)中節(jié)點(diǎn)的當(dāng)前狀況，避免了網(wǎng)絡(luò)的局部擁塞，均衡了網(wǎng)絡(luò)流量；通過自適應(yīng)地調(diào)整鏈路權(quán)值的揮發(fā)系數(shù)，提高了算法的全局搜索能力。仿真結(jié)果表明，該算法有效控制了網(wǎng)絡(luò)擁塞，均衡了網(wǎng)絡(luò)負(fù)載分布。

無線傳感器網(wǎng)絡(luò)；路由協(xié)議；蟻群算法；鏈路權(quán)重

0 引言

隨著計算機(jī)網(wǎng)絡(luò)技術(shù)和傳感器技術(shù)的快速發(fā)展，無線傳感器網(wǎng)絡(luò)技術(shù)（WSNs）已被廣泛應(yīng)用于各個領(lǐng)域，包括環(huán)境監(jiān)測、軍事安全和醫(yī)療監(jiān)護(hù)等方面。這些領(lǐng)域的應(yīng)用對傳感器信息傳輸?shù)姆?wù)質(zhì)量（QoS）提出了更高的要求，而路由算法是無線傳感器網(wǎng)絡(luò)提高QoS的關(guān)鍵因素之一。因此，設(shè)計有效的無線傳感器網(wǎng)絡(luò)路由協(xié)議是提高QoS的重要手段。

本文從已有的無線傳感器網(wǎng)絡(luò)蟻群路由算法出發(fā)，提出了一種基于鏈路權(quán)重的無線傳感器網(wǎng)絡(luò)蟻群路由改進(jìn)算法，依據(jù)每兩個節(jié)點(diǎn)之間鏈路的可用帶寬、時延等因素來綜合計算鏈路權(quán)重，根據(jù)當(dāng)前鏈路權(quán)重大小來改變信息素的值，從而避開擁塞鏈路，達(dá)到負(fù)載均衡的目的。

1 鏈路權(quán)重分析

傳統(tǒng)的路由算法以路徑長度作為路由評價標(biāo)準(zhǔn)，而沒有考慮鏈路的狀態(tài)，導(dǎo)致最短的路徑未必最優(yōu)。因此，在原有算法的基礎(chǔ)上，引入每一跳的代價（權(quán)重），選擇權(quán)重最小的路徑，可以優(yōu)化路由選擇，提高無線傳感器網(wǎng)絡(luò)的QoS。而帶寬和時延是影響鏈路狀態(tài)的主要性能參數(shù)，本文利用這兩個參數(shù)來計算鏈路權(quán)重。

兩個節(jié)點(diǎn)之間鏈路的可用帶寬、時延都不相同，節(jié)點(diǎn)與鏈路的負(fù)載越大，緩沖隊列越接近飽和，其與鄰居節(jié)點(diǎn)間的鏈路將越繁忙，可用帶寬越少，傳輸時延越長，因而通信傳輸代價也就越高。

將無線傳感器網(wǎng)絡(luò)視為相互關(guān)聯(lián)的無向圖，設(shè) G=(V,E)表示無線傳感器網(wǎng)絡(luò)，其中，V表示網(wǎng)絡(luò)節(jié)點(diǎn)，E表示由節(jié)點(diǎn)集合組成的雙向連接的鏈路。任意鏈路e E∈ 與QoS相關(guān)的主要指標(biāo)為帶寬B()e和時延D()e。從節(jié)點(diǎn)i到任意節(jié)點(diǎn)j的帶寬和時延計算公式分別為：

其中， ()Be表示鏈路e E∈ 的帶寬，D()e和D(n)分別表示鏈路e E∈ 時延和節(jié)點(diǎn)n V∈ 時延。

節(jié)點(diǎn)i到鄰居節(jié)點(diǎn) j之間鏈路的權(quán)重ijw 計算如下：

路由建立以后，路由層采用周期發(fā)送HELLO包的機(jī)制來維護(hù)路由。周期發(fā)送HELLO包可及時更新鄰居節(jié)點(diǎn)表和對應(yīng)的信息素分布，并更新與其鄰居節(jié)點(diǎn)間的鏈路權(quán)重。

2 基于鏈路權(quán)重的蟻群路由改進(jìn)算法

為了提高蟻群算法搜索全局最優(yōu)解的能力，并有效避開擁塞鏈路，依據(jù)鏈路權(quán)重的變化來更新信息素的大小。在進(jìn)行路徑選擇過程中，根據(jù)當(dāng)前鏈路權(quán)重與設(shè)定的閾值的比值大小來更新路徑的信息素，即：當(dāng)鏈路權(quán)重小于閾值時，信息素強(qiáng)度Q就加上該鏈路的權(quán)重，否則就減去此鏈路權(quán)重。這樣權(quán)重較小的鏈路增加的信息素就較大，增加了被選中的可能性。第k只螞蟻在本次循環(huán)中留在路徑(i,j)上的信息素的更新規(guī)則由式（6）表示。

其中， wij表示鏈路(i,j)的權(quán)重；w表示鏈路權(quán)重的閾值，初始值為 w0；Q表示信息素的增強(qiáng)系數(shù)；表示第k只螞蟻?zhàn)哌^路徑(i,j)的長度。

所有螞蟻經(jīng)過鏈路后，各路徑的信息素根據(jù)（7）式和（8）式進(jìn)行更新：

式中，ρ表示信息素?fù)]發(fā)系數(shù)，則1 - ρ表示信息素殘留因子；表示本次循環(huán)中路徑(i,j)上的信息素增量，初始時刻

3 仿真分析

采用典型無線傳感器網(wǎng)絡(luò)結(jié)構(gòu)對該算法的有效性進(jìn)行仿真驗(yàn)證，每個頂點(diǎn)用n〈d〉表示，其中n表示節(jié)點(diǎn)標(biāo)號，d表示節(jié)點(diǎn)時延，節(jié)點(diǎn)時延假定為 1；每條鏈路用〈bw，dl〉表示，其中 bw表示鏈路的帶寬，dl表示鏈路的時延。假定源節(jié)點(diǎn)為11，目的節(jié)點(diǎn)為20，開始時每條相連鏈路的初始信息素濃度相同，螞蟻隨機(jī)地選擇路徑，每次選擇一個節(jié)點(diǎn)之后，對兩個節(jié)點(diǎn)間鏈路依據(jù)路徑的時延、帶寬情況進(jìn)行信息素更新，此后的螞蟻選擇路徑會受前代螞蟻的影響，經(jīng)過n代更迭進(jìn)而找到最優(yōu)路徑。

圖1帶寬瓶頸的比較

圖1 是對每次迭代過程中螞蟻所經(jīng)過路徑的帶寬瓶頸比較，傳統(tǒng)蟻群路由算法最終選擇的鏈路帶寬瓶頸值是17。本改進(jìn)算法選擇的帶寬瓶頸值為23，表明了隨著迭代次數(shù)的增加，本算法使得螞蟻逐漸傾向于帶寬較寬的鏈路。

網(wǎng)絡(luò)端到端的時延仿真結(jié)果中，傳統(tǒng)蟻群路由算法中最終選擇鏈路的端到端時延為60，本改進(jìn)算法將鏈路權(quán)重應(yīng)用到信息素更新中后，時延減小到35。因此，在路徑選擇過程中，螞蟻傾向于時延較小的鏈路。

通過帶寬瓶頸、時延的比較，表明基于鏈路權(quán)重的無線傳感器網(wǎng)絡(luò)蟻群路由算法比傳統(tǒng)蟻群路由算法具有明顯的優(yōu)勢，當(dāng)可用帶寬較少，傳輸時延較長（即鏈路擁塞）時，信息素更新策略降低了螞蟻選擇該路徑的可能，避開了網(wǎng)絡(luò)中的擁塞路徑，并且均衡了網(wǎng)絡(luò)負(fù)載。

4 結(jié)語

本文引入鏈路權(quán)重的思想，提出了基于鏈路權(quán)重的無線傳感器網(wǎng)絡(luò)蟻群路由改進(jìn)算法，利用鏈路權(quán)重來更新路徑上的信息素強(qiáng)度，并可自適應(yīng)地調(diào)整權(quán)值的閾值和揮發(fā)系數(shù)，從而避開擁塞鏈路，增大網(wǎng)絡(luò)全局搜索能力。仿真結(jié)果表明，改進(jìn)算法均衡了網(wǎng)絡(luò)負(fù)載，提高了網(wǎng)絡(luò)QoS，達(dá)到了路由算法自適應(yīng)性和網(wǎng)絡(luò)負(fù)載均衡化的效果。

[1]夏亞梅，程渤，陳俊亮．基于改進(jìn)蟻群算法的服務(wù)組合優(yōu)化[J]．計算機(jī)學(xué)報， 2012．

[2]童孟軍，俞立，鄭立靜．基于蟻群算法的無線傳感器網(wǎng)絡(luò)能量有效路由算法研究[J]．傳感技術(shù)學(xué)報，2011．