基于蟻群優化算法的無線傳感器網絡路由研究

宋 杰，吳 勇，陳明明

（安徽大學 計算機科學與技術學院，安徽 合肥 230601）

基于蟻群優化算法的無線傳感器網絡路由研究

宋 杰，吳 勇，陳明明

（安徽大學 計算機科學與技術學院，安徽 合肥 230601）

無線傳感器網絡是一種能量、資源受限的網路系統，實現網絡中節點能量使用均衡延長整個網絡的生命周期是無線傳感器網絡路由設計的重要目標.本文在基本蟻群算法在無線傳感器網絡應用的基礎之上提出了幾點改進策略.將節點現有的能量水平作為計算轉移概率的條件之一，使優秀路徑上的節點在網絡中存在的時間更長.將節點的位置信息作為計算轉移概率的條件，通過將位置信息寫入轉移概率中，使節點在搜索路徑時具有方向性.最后本文利用MATLAB工具對改進的策略進行了實驗仿真，并將結果和原始的ACO算法進行比較分析，仿真結果顯示改進策略在延長節點的生命周期，維持網絡能量均衡方面比其他倆種算法具有一定的提升.

無線傳感器網絡；蟻群算法；能量均衡；路由協議

1 引言

隨著傳感技術、無線通信技術和嵌入式技術的不斷發展成熟，無線傳感器網絡逐漸成為當今社會的研究熱點.它強大的感知能力、自組織能力、部署方式簡單方便的特點決定了在很多領域都有廣闊的應用前景［1，2］.由于無線傳感器網絡中節點的能量受限，將傳統的網絡協議應用到無線傳感器路中不太現實.近年來，許多學者對無線傳感器網絡路由做出了大量的研究［3］.

無線傳感網最初的雛形是起源于上個世紀70年代，當時的技術僅處于初始的研制階段，此時的網絡采用點對點的傳輸，而且傳感器節點只具有簡單的數據獲取能力.80年代左右，無線傳感網技術己經慢慢發展起來，該網絡采用串/并口方式與控制中心相連，并且傳感器節點具有了獲取各種不同信息的能力.到了20世紀的末期，由于其他學科技術的綜合發展，使得無線傳感網技術也有了更好的發展，該技術采用總線連接方式代替了串/并口方式，形成了真正意義上的無線局域網絡21世紀，無線傳感網作為多學科交叉的新興技術研究領域，被世界各個國家高度關注，給軍事方面、學術和工業界等帶來了巨大反響.然而由于傳感器一般由電池供應電能，而且分布的環境可能比較惡劣.經常更換電池不太現實，因此傳感器的能源供應成為制約無線傳感器網絡發展的一個重要的因素.由于傳感器能量主要消耗在數據的發送過程中，因此減少數據傳輸過程中發送次數、平衡整個網絡中傳感器的能量成為人們研究的熱點.研究無線傳感器網絡路由算法起于1990年以后，如今這一課題的科研很有活力，不論國內還是國外相關的科研工作人員付出了很多的努力.無線傳感器網絡拓撲結構易變，并且使用有限能量的電池供電.這些特征使得傳統的路由算法機制無法再用于無線傳感器網絡，所以要研究設計新的路由算法.目前越來越多的學者和科研機構投入到無線傳感器網絡路由算法的研究中來，使得這項研究成為當今的熱點領域.路由算法越來越復雜，其性能越來越高，能滿足更高層次的質量需求.同時越來越多的智能算法的引入使無線傳感器網絡路由算法更加高效、可靠，性能有了顯著的提高，使之成為目前研究的重點.其中蟻群算法在無線傳感器網絡路由算法中得到了廣泛的研究.

2 無線傳感器網絡的耗能分析

根據大量研究表明無線傳感器網絡中節點的能量消耗主要分為三個部分：數據采集（即感知環境）耗能、數據融合耗能、通信耗能［6］.由于通信耗能在三部分耗能中占據絕大部分，所以在試驗中只考慮了節點間通信耗能.本文采用的能量消耗模型為：

圖2.1 能量消耗模型

具體的計算公式如下：

（1）節點發送數據的能量消耗公式為：

從2-1可以看出當節點節點間的距離大于閾值時，發送數據的耗能將大大的增加.

（2）節點接收數據的能量消耗計算公式為：

3 改進策略

3.1 將節點的位置作為影響轉移概率的因素之一

當鄰居節點的轉移概率相近，或者轉移概率最大的節點遠離匯聚節點時，會增加傳輸路徑的長度，增加了耗能.將節點相對于匯聚節點的位置信息作為計算轉移概率的條件之一.轉移函數可變為：

其中τij（t）為t時刻節點i到節點j路徑上的信息素濃度；ηij（t）為t時刻節點i到幾點j之間路徑啟發信息；其中ηij=1/dij即啟發信息是倆節點之間距離的倒數；μj是節點位置對路徑的啟發信息，其中μj=1/dj，dj表示節點j到匯聚節點的距離.α、β、λ是調節因子，分別反映了信息素對螞蟻轉移概率的影響、節點間距離對螞蟻轉移概率的影響、節點到匯聚節點間的距離對螞蟻轉移概率的影響.可以看出當下一跳節點和匯聚節點的距離大時轉移概率函數p相對變小，螞蟻選擇該節點的概率變小.

3.2 將節點剩余能量作為影響轉移概率的因素之一

無線傳感器網絡是由多個傳感器節點自組織形成的，每個節點的在網絡的壽命，直接關系到整個網絡的生命周期.將節點的剩余能量作為影響轉移概率的因素顯得十分必要.可以將轉移概率函數設計為：

其中τij（t）為t時刻節點i到節點j路徑上的信息素濃度；ηij（t）為t時刻節點i到幾點j之間路徑啟發信息；其中ηij= 1/dij即啟發信息是倆節點之間距離的倒數；

3.3 抑制信息素的增長

螞蟻搜索出最優路徑后，由于螞蟻的正反饋機制該條路徑上的信息素含量將會進一步的提高.這樣全網中較優秀的路徑上的節點能量很容易耗盡，降低了整個網絡的生命周期.本文采用螞蟻攜帶抑制信息的方法來解決上述問題.即當螞蟻在節點i的候選節點集合中選擇j為最優路徑后，該路徑上的信息素適度的降低.

3.4 路徑信息素的更新

每當完成一輪路徑選擇后，對所有螞蟻走過的路徑上的信息素按照以下規則進行更新.

式中τij（t+n）表示t+n時刻節點i和節點j之間路徑上的信息素含量；ρ表示整個網絡路徑中信息素的衰減因素；Δτij（t）表示本輪計算中m個螞蟻對節點i和節點j之間路徑上的信息素含量的抑制.其中

4 仿真分析

本文的仿真環境為MATLAB.仿真系統模型為：在面積大小為200*200的空間內隨機的部署200個感知點，負責感知信息和接收、發送數據包.匯聚節點設置在感知區域的邊沿，坐標為（0，0）.采用TSP標準庫中的實例來布置場景，平面區域中的節點有的分布是均勻的有的分布是不均勻的.為了更好的進行試驗，做出以下假設：（1）傳感器節點的是不可以移動的.（2）所有的傳感器具有唯一的標志ID，并且可以感知自己的坐標.（3）除匯聚節點外傳感器節點的能量受限、初始能量相同，并且可以感知.

4.1 評價指標

本文提出的改進策略旨在實現無線傳感器網絡的能量均衡.仿真實驗主要考察節點的能量消耗、網絡的生命周期、路徑長度等方面考察了改進策略的有效性.

4.1.1 節點的能量消耗

無線傳感器網絡需要將檢測區域采集到的數據經過一定融合，傳送到匯聚節點.為了延長整個網絡的生命周期需要減少網絡中所有節點的能耗，并且保證所有節點的能量使用的均衡.如果一些節點的網絡任務過重，將會使這些節點過早的退出網絡.不利于網絡能源的均衡利用，可能降低網絡的生命周期.

4.1.2 網絡的生命周期

網絡生命周期的長短是衡量無線傳感器網絡路由協議的重要指標之一.

4.1.3 路徑長度

由于無線傳感器網絡中節點能耗主要體現在節點間的通信方面.而發送數據的能量消耗和節點間的距離是呈現出指數型關系.因此，降低傳輸路徑長度降低網絡能量消耗的重要手段.

4.2 路徑長度

從上文的無線通信能量模型中我們可以看出無線通信能耗主要體現在節點間的通信方面.而發送數據的能量消耗和節點間的距離是呈現出指數型關系.降低傳輸路徑長度降低網絡能量消耗的重要手段.在依次仿真試驗中選取某個節點作為源節點，通過蟻群算法和改進的算法搜索路徑.得到的數據如圖所示：

圖4.1 一次搜索路徑示意圖

從上圖4.1中可以看出原始的蟻群算法在搜索最優路徑過程中經歷了10跳，而改進的算法在搜索最優路徑的過程中經歷了8跳.倆種算法都經過了編號為89的節點，由于改進的算法引用了節點的位置信息，下一跳節點選擇為編號為60的節點，原始的蟻群算法從鄰居節點中選取轉移概率最大的編號為198的節點.明顯的增加了整體的路徑長度.因此，可以看出改進的算法在降低傳輸路徑長度方面有一定的提升.

4.3 能量消耗情況

改進策略的初衷是降低網絡整體的耗能、均衡網絡的消耗實現無線傳感器網絡生命周期的延長.本實驗迭代100次，倆算法下的網絡能耗如下所示：

圖4.2 能量消耗展示圖

從圖4.2中可以看出，倆種算法隨著網絡使用時間的增加網絡整體的能耗趨于平衡，改進的策略和原始蟻群算法相比較在能耗方面有一定的優勢.在網絡開始階段，由于網絡上各個路徑上的信息素相等，傳統蟻群算法在轉移概率相等時隨機的選擇鄰居節點集合中的一個節點作為下一跳，改進策略將節點的位置信息作為轉移概率計算的參數之一，使搜索路徑具有方向性.這樣改進策略在開始階段的路徑長度很可能小于原始的蟻群算法.在圖4.2中可以看出在開始階段改進策略的能耗明顯小于原始算法.隨著網絡使用時間的增加，每個節點的能量差開始體現出來，位置信息對搜索路徑的影響降低.因此，從圖中可以看出，在穩定階段二者的能耗差距不是非常的明顯.

4.4 網絡的生命周期

無線傳感器網絡的生命周期直觀的體現是網絡中存活節點的個數.無線傳感器網路中每個節點的傳輸能力有限，需要多個節點多跳的方式將數據傳送到匯聚節點.當網絡中存活節點的個數低于一定數量時，網絡趨于癱瘓，不能夠進行正常的采集傳輸工作.

圖4.3

從圖4.3中可以看出在開始階段，不考率人為的破壞的情況下傳感器節點的數量是不降低的，隨著使用時間的增加，當出現節點退出網絡時，網絡存活節點數量隨著時間的推移急速下降.由于將節點的能量水平作為計算轉移概率的因素之一，從圖4.3中可以看出改進策略對網絡中優秀路徑中的節點起到了很大的保護作用，改進策略出現死亡節點的時間明顯滯后于原始算法.

5 結束語

通過閱讀大量的文獻，本文在原有的蟻群算法基礎之上提出了幾點改進策略旨在實現網絡的能量均衡，延長網絡的生命周期.同過和原有的蟻群算法相比較可以看出本文提出的算法有效地降低了網路中的路徑長度，在提升網絡生命周期方面有一定的優勢.

〔1〕孫利民，李建中，陳渝，等.無線傳感器網絡［M］.北京：清華大學出版社，2005，3～23.

〔2〕Bonnet P，Gehrke J，Seshadri P. Querying the physical world ［J］. IEEE Personal Communication，2000，7（5）：10-15.

〔3〕劉志.無線傳感器網絡中的能量高效覆蓋與路由算法研究［D］.北京：北京交通大學，2011.

〔4〕唐勇，周明天，張欣.無線傳感器網絡路由協議研究進展［J］.軟件學報，2006，17（3）：410-421.

〔5〕Hedetniemi S.M.，HedetniemiS.T.， Liestman A.L.. A survey of gossiping and broadcasting in communication networks［J］.Networks，1988，18（4）：319-349.

〔6〕謝耀華.基于蟻群算法的無線傳感器網絡路由算法研究及實現.西安電子科技大學，2013.3.

TP393

A

1673-260X（2015）05-0013-03