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

◆李 璐

(大連海洋學校實驗中心 遼寧 116023)

安全模型、算法與編程

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

◆李 璐

(大連海洋學校實驗中心 遼寧 116023)

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

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

0 引言

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

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

1 鏈路權重分析

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

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

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

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

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

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

2 基于鏈路權重的蟻群路由改進算法

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

其中， wij表示鏈路(i,j)的權重；w表示鏈路權重的閾值，初始值為 w0；Q表示信息素的增強系數(shù)；表示第k只螞蟻走過路徑(i,j)的長度。

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

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

3 仿真分析

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

圖1帶寬瓶頸的比較

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

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

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

4 結語

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

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

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