宋 杰，吳 勇，陳明明

（安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 合肥 230601）

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

宋 杰，吳 勇，陳明明

（安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 合肥 230601）

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

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

1 引言

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

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

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

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

圖2.1 能量消耗模型

具體的計(jì)算公式如下：

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

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

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

3 改進(jìn)策略

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

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

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

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

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

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

3.3 抑制信息素的增長

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

3.4 路徑信息素的更新

每當(dāng)完成一輪路徑選擇后，對所有螞蟻?zhàn)哌^的路徑上的信息素按照以下規(guī)則進(jìn)行更新.

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

4 仿真分析

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

4.1 評價(jià)指標(biāo)

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

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

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

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

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

4.1.3 路徑長度

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

4.2 路徑長度

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

圖4.1 一次搜索路徑示意圖

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

4.3 能量消耗情況

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

圖4.2 能量消耗展示圖

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

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

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

圖4.3

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

5 結(jié)束語

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

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

〔4〕唐勇，周明天，張欣.無線傳感器網(wǎng)絡(luò)路由協(xié)議研究進(jìn)展［J］.軟件學(xué)報(bào)，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)絡(luò)路由算法研究及實(shí)現(xiàn).西安電子科技大學(xué)，2013.3.

TP393

A

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