◆李 璐

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

安全模型、算法與編程

基于鏈路權重的無線傳感器網絡蟻群路由算法

◆李 璐

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

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

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

0 引言

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

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

1 鏈路權重分析

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

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

將無線傳感器網絡視為相互關聯(lián)的無向圖，設 G=(V,E)表示無線傳感器網絡，其中，V表示網絡節(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ù)（7）式和（8）式進行更新：

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

3 仿真分析

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

圖1帶寬瓶頸的比較

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

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

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

4 結語

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

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

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