基于蟻群優(yōu)化算法的無線傳感器網(wǎng)絡路由研究

宋 杰，吳 勇，陳明明

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

基于蟻群優(yōu)化算法的無線傳感器網(wǎng)絡路由研究

宋 杰，吳 勇，陳明明

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

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

無線傳感器網(wǎng)絡；蟻群算法；能量均衡；路由協(xié)議

1 引言

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

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

2 無線傳感器網(wǎng)絡的耗能分析

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

圖2.1 能量消耗模型

具體的計算公式如下：

（1）節(jié)點發(fā)送數(shù)據(jù)的能量消耗公式為：

從2-1可以看出當節(jié)點節(jié)點間的距離大于閾值時，發(fā)送數(shù)據(jù)的耗能將大大的增加.

（2）節(jié)點接收數(shù)據(jù)的能量消耗計算公式為：

3 改進策略

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

當鄰居節(jié)點的轉移概率相近，或者轉移概率最大的節(jié)點遠離匯聚節(jié)點時，會增加傳輸路徑的長度，增加了耗能.將節(jié)點相對于匯聚節(jié)點的位置信息作為計算轉移概率的條件之一.轉移函數(shù)可變?yōu)椋?/p>

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

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

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

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

3.3 抑制信息素的增長

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

3.4 路徑信息素的更新

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

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

4 仿真分析

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

4.1 評價指標

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

4.1.1 節(jié)點的能量消耗

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

4.1.2 網(wǎng)絡的生命周期

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

4.1.3 路徑長度

由于無線傳感器網(wǎng)絡中節(jié)點能耗主要體現(xiàn)在節(jié)點間的通信方面.而發(fā)送數(shù)據(jù)的能量消耗和節(jié)點間的距離是呈現(xiàn)出指數(shù)型關系.因此，降低傳輸路徑長度降低網(wǎng)絡能量消耗的重要手段.

4.2 路徑長度

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

圖4.1 一次搜索路徑示意圖

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

4.3 能量消耗情況

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

圖4.2 能量消耗展示圖

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

4.4 網(wǎng)絡的生命周期

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

圖4.3

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

5 結束語

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

〔1〕孫利民，李建中，陳渝，等.無線傳感器網(wǎng)絡［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〕劉志.無線傳感器網(wǎng)絡中的能量高效覆蓋與路由算法研究［D］.北京：北京交通大學，2011.

〔4〕唐勇，周明天，張欣.無線傳感器網(wǎng)絡路由協(xié)議研究進展［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〕謝耀華.基于蟻群算法的無線傳感器網(wǎng)絡路由算法研究及實現(xiàn).西安電子科技大學，2013.3.

TP393

A

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