孫 穎

（沈陽大學(xué) 信息工程學(xué)院，遼寧 沈陽 110044）

基于蟻群算法的能量均衡傳感網(wǎng)地理信息路由

孫 穎

（沈陽大學(xué) 信息工程學(xué)院，遼寧 沈陽 110044）

提出了一種基于蟻群算法的能量均衡傳感網(wǎng)地理信息路由算法，用來保證具有生存周期的無線傳感器網(wǎng)絡(luò)能夠在不損失其傳感能力的情況下，生存更長的時間.實驗證明，此算法能夠均衡網(wǎng)絡(luò)中的能量消耗，延長網(wǎng)絡(luò)生存時間，并能有效提高報文發(fā)送成功率，避免擁塞.

蟻群算法；地理信息路由；能量均衡路由；無線傳感器網(wǎng)絡(luò)

近年來，一種新型的分布式系統(tǒng)—— 嵌入式網(wǎng)絡(luò)系統(tǒng)顯示出了廣闊的應(yīng)用前景.其中，無線傳感器網(wǎng)絡(luò)成了監(jiān)控和分析物理環(huán)境最受歡迎的平臺.無線傳感器網(wǎng)絡(luò)是由大量無處不在的，密集布設(shè)在無人值守的監(jiān)控區(qū)域的具有通信與計算能力的微小傳感器節(jié)點，構(gòu)成的能夠根據(jù)環(huán)境自主完成指定任務(wù)的智能自治監(jiān)控網(wǎng)絡(luò)系統(tǒng).無線傳感器網(wǎng)絡(luò)是一種資源嚴格受限的分布式系統(tǒng)，采用多跳對等的通信方式，其網(wǎng)絡(luò)拓撲動態(tài)變化，具有自組織、自治、自適應(yīng)等智能屬性.

無線傳感器網(wǎng)絡(luò)出現(xiàn)之后，路由方面的研究就成為了該領(lǐng)域的研究熱點，目前關(guān)于路由的研究主要集中在幾個方面，一類是基于能量的路由；一類是基于服務(wù)質(zhì)量的路由；一類是基于最短路徑的路由.

本文結(jié)合了能量感知路由和地理信息路由，通過同蟻群算法的有機集成，提出了一種基于蟻群算法的能量均衡傳感網(wǎng)地理信息路由算法（Ant－colony－based Geographic and Energy Balance Routing，AGEBR）.該算法具有算法簡單并支持分布式的特點，很容易在資源受限的無線傳感器網(wǎng)絡(luò)節(jié)點上實現(xiàn).實驗證明，該算法具有能夠均衡網(wǎng)絡(luò)中的能量消耗，延長網(wǎng)絡(luò)生存時間，并能有效提高報文發(fā)送成功率，避免擁塞的特點.

1 相關(guān)工作

能量感知路由和基于地理位置的路由之前的相關(guān)工作，以及目前在無線傳感器網(wǎng)絡(luò)中利用環(huán)境能量資源的可行性啟發(fā)了我們在此方面的工作.

1.1 能量感知ad－h(huán)oc路由算法

在過去的幾年里，能量感知路由算法很受重視.Woo等人提出了5條能量感知定理［1］；Chang等人提出了一系列的流量遞增算法和一個流量變向算法［2］；Li等提出了一種“在線”能量感知路由算法和一種基于區(qū)域的路由算法［3］.所有的這些工作都是基于如下的假定，即節(jié)點具有有限的或定量的能量供應(yīng)，并且這些能量中不包括節(jié)點從環(huán)境獲取的額外能量.

1.2 基于地理位置的ad－h(huán)oc路由協(xié)議

基于地理位置的路由協(xié)議的可行性取決于區(qū)域的可變性，以及路由決策過程是可定位的.發(fā)送報文的節(jié)點只需要獲得自己、一跳節(jié)點和目的節(jié)點的位置.對于傳統(tǒng)的基于地理位置的路由算法，報文通過局部和貪婪的方式發(fā)送到能夠為其提供至目的節(jié)點的最優(yōu)方式的一跳鄰居.在貪婪模式下，笛卡兒路由算法［4］選擇到目的節(jié)點的最近的鄰居作為下一跳，而MFR（Most Forward within Radius）［5］更傾向于與目的節(jié)點具有最短工程距離（當前節(jié)點和目的節(jié)點之間的直線距離）的鄰居.

當前一些針對無線ad－h(huán)oc和傳感器網(wǎng)絡(luò)的實驗研究［6］表明無線鏈路可能出現(xiàn)較高的不可靠性，當評價更高層次的協(xié)議時，這種不可靠性需要被明確計算在內(nèi).文獻［7］表明了大型“傳統(tǒng)區(qū)域”的存在性，在其中的鏈路質(zhì)量存在高變動性，包括好的和不可靠的鏈路.這種鏈路的存在暴露了貪婪算法的重要缺陷，即距離目的節(jié)點最近的鄰居（有可能是距離轉(zhuǎn)發(fā)節(jié)點最遠的）可能與轉(zhuǎn)發(fā)節(jié)點之間的鏈路較差.脆弱的鏈路可能導(dǎo)致包丟失率升高和發(fā)送率的急劇下降，或者在添加重傳機制的情況下，增加能源消耗.基于地理位置的路由的當前工作認識到了這種信道條件下的現(xiàn)實問題.Seada等［8］提出了距離－跳數(shù)和能源權(quán)衡的基于地理位置的路由算法.他們總結(jié)出期望的報文傳輸，PRR（包接收率）×Adavancement，是一種可供選擇的度量，這種度量用于對利用ARQ（Automatic Repeat reQuest）機制的無線網(wǎng)絡(luò)丟失情況做出基于局部地理位置的路由算法決策.Zorzi和Armaroli也獨立地提出了同樣的鏈路度量［9］.上述工作的焦點在于報文收發(fā)情況，因此有關(guān)節(jié)點的能耗并未考慮.雖然GEAR（Geographic and Energy Aware Routing）［10］考慮了節(jié)點的剩余能量信息，但并沒有考慮到無線信道的實際環(huán)境.

2 算法適用的傳感器網(wǎng)絡(luò)模型

2.1 網(wǎng)絡(luò)模型

本文描述的網(wǎng)絡(luò)是一個隨機分布的無線傳感器網(wǎng)絡(luò)，含有1個sink節(jié)點，其余都是source節(jié)點.每個source節(jié)點i（i＝1，2，3，…）都周期性發(fā)送數(shù)據(jù)給sink節(jié)點.每個節(jié)點都有一個射頻最大通信半徑Rm，節(jié)點間的物理距離小于Rm，就能相互通信.以Pij表示節(jié)點i，j之間能否通信，則可生成通信矩陣

2.2 能量模型

Kansal等人［11］提出了一種能量的數(shù)學(xué)模型，當節(jié)點的功率滿足某種條件時，節(jié)點可以做到持續(xù)工作，而不會能量耗盡.

式中，ρ為能量獲取功率，σ1、σ2分別為能量閾值，當節(jié)點電池的初始能量大于σ1＋σ2時，則在T時間內(nèi)，節(jié)點能夠持續(xù)穩(wěn)定的工作.因此，在電池初始容量足夠的假設(shè)下，通過調(diào)節(jié)能量消耗功率E（t），就可以滿足節(jié)點持續(xù)穩(wěn)定工作的條件.

本文中假設(shè)能量獲取功率全網(wǎng)相同，但其較小或為零，因此總有傳感器節(jié)點不能滿足持續(xù)工作的條件，電能總有一天會耗盡.即T將小于某個常數(shù).本文的目標是使每個傳感器節(jié)點的T值盡可能相同，保證全網(wǎng)能量同時耗盡.這樣，也就保證了全網(wǎng)在傳感功能不受影響的情況下工作最長的時間.

在每一時刻，節(jié)點都能獲知剩余能量，以及未來T時間內(nèi)的能量獲取值ρT，如果沒有能量補充，則該值為0.因此，通過調(diào)節(jié)能量消耗功率來控制節(jié)點在這一時間內(nèi)持續(xù)穩(wěn)定工作.

從另一個角度考慮，在滿足這個條件的情況下，節(jié)點的剩余能量值與能量獲取值之和越高，所能支持的功耗E（t）頻率就越大.而節(jié)點的能耗大小可表示為

式中，Ec（t）為節(jié)點工作時的功耗，是由節(jié)點的任務(wù)循環(huán)（duty－cycle，DC）決定的，Es（t）是節(jié)點的靜態(tài)功耗，一般來說是個常量，即

因此，根據(jù)式（5）就能確定節(jié)點的最小DC，使能量消耗最大且不影響節(jié)點持續(xù)工作.

通過選路，控制更多的報文由DC最大的點發(fā)，就能充分利用網(wǎng)絡(luò)中的能量.而傳感網(wǎng)關(guān)心的另一個問題是網(wǎng)絡(luò)的性能，即最小化時延.盡管DC頻率高的點擁有更多的能量用于轉(zhuǎn)發(fā)數(shù)據(jù)，但也無法保證其所在的整條路徑上不存在擁塞.

2.3 任務(wù)模型

本文中所涉及的無線傳感器網(wǎng)絡(luò)中每個傳感器節(jié)點的任務(wù)包含兩個方面：數(shù)據(jù)采集和發(fā)送任務(wù)，這和傳感器的功能和工作周期有關(guān)；路由和轉(zhuǎn)發(fā)任務(wù)，其他節(jié)點的報文通過該節(jié)點轉(zhuǎn)發(fā)，最終到網(wǎng)關(guān)的報文.路由和轉(zhuǎn)發(fā)任務(wù)不是每個節(jié)點都有，節(jié)點具有該任務(wù)有兩個條件，一是在位置上不在邊緣，屬于中間節(jié)點，有被選為路由的可能，二是節(jié)點具有路由和轉(zhuǎn)發(fā)的功能.

3 算法描述

蟻群算法［12］又稱螞蟻算法，根據(jù)仿生學(xué)家的研究結(jié)果，螞蟻具有找到蟻穴與食物源之間最短路徑的能力.

Step 1 在算法初始化中，每個節(jié)點都被賦予一定的信息素，每個報文作為一個螞蟻.螞蟻k（k＝1，2，3，…）在運動過程中根據(jù)節(jié)點上信息素的濃度決定選擇哪個節(jié)點作為下一跳.螞蟻k可選的下一跳的集合為allowedk.allowedk中的元素要滿足地理位置上更靠近sink的節(jié)點才有資格作為下一跳，即

式中，d j，sink是鄰居j到sink節(jié)點的物理距離，d i，sink是k當前所在的節(jié)點到sink節(jié)點之間的物理距離.

Step 2 在搜索過程中，螞蟻k根據(jù)各條路徑上的殘留信息量和路徑的啟發(fā)信息計算狀態(tài)轉(zhuǎn)移概率.在t時刻螞蟻k由節(jié)點i轉(zhuǎn)移到節(jié)點j的概率（t）使用式（8）確定.

式中，τj（t）是節(jié)點j上殘留信息素數(shù)量；allowedk，表示螞蟻k下一步允許選擇的節(jié)點集合；α為信息素啟發(fā)因子；β為期望啟發(fā)式因子，α，β都是常數(shù)；ηij（t）為啟發(fā)信息，在本文中其表達式如下：

用來度量地理位置信息的重要性，距離網(wǎng)關(guān)越近的節(jié)點，成為下一跳的概率就越大.

Step 3 為了避免殘留信息素過多引起殘留信息淹沒啟發(fā)信息，在每只螞蟻走完一步后，要對殘留信息進行更新處理，根據(jù)節(jié)點不同其表達式有2個，發(fā)送節(jié)點為：

式中，Δτi（t）是每次調(diào)整的信息素，ρ（0＜ρ＜1）為節(jié)點的信息素更新?lián)]發(fā)系數(shù)，則1－ρ為信息殘留系數(shù).這樣成功發(fā)送時，收發(fā)雙方都會增加信息素，這樣會提高被選擇為下一跳的概率.而如果路徑上某一位置因為擁塞或其他原因?qū)е掳l(fā)送不成功，不成功的信息也會在路徑上擴散，并在有限個報文周期之內(nèi)擴散到整條路徑，進而會幫助在以后的選路過程中繞過出問題的鏈路.

4 實驗和分析

4.1 仿真場景

為了驗證本文提出的算法的有效性，進行了仿真實驗.仿真使用了MATLAB軟件，仿真場景如下，在一個半徑為100 m的圓內(nèi)隨機分布著30個傳感器節(jié)點（source節(jié)點），同時圓心處擁有一個sink節(jié)點，所有傳感器節(jié)點的數(shù)據(jù)收集和發(fā)送任務(wù)10 s生成一次，即發(fā)送一個報文，每個報文初始化成一個螞蟻.信息素啟發(fā)因子α為1；期望啟發(fā)式因子β為1.

4.2 結(jié)果分析

本文對僅根據(jù)剩余能量選路的Mint Route，和文中提出的考慮能量均衡的蟻群AGEBR進行了比較.以下所有仿真結(jié)果都為3次相同條件仿真的平均值，顯示距離網(wǎng)關(guān)不同距離上節(jié)點的生存時間和數(shù)據(jù)轉(zhuǎn)發(fā)能力.

圖1是網(wǎng)絡(luò)生存時間的仿真結(jié)果.仿真過程為每個節(jié)點設(shè)置了近似相同的初始能耗.從結(jié)果可見，在相同的初始能量設(shè)置下，使用蟻群算法的網(wǎng)絡(luò)能生存更長時間，這也證明了本文采用的選路策略比根據(jù)節(jié)點電池的剩余能量進行負載平衡的路由算法具有更好的節(jié)能效果.

圖1 節(jié)點生存時間比較Fig.1 Survival time of nodes

本節(jié)也針對網(wǎng)絡(luò)能量消耗進行了仿真.仿真中設(shè)定場景相比前一實驗有所變化，主要是設(shè)定了離網(wǎng)關(guān)最近的14個路由節(jié)點擁有最多初始能量，實驗?zāi)M100 d的工作過程.獲得以下實驗結(jié)果：

表1、表2分別是兩種路由情況下的能量消耗比，圖2是每個節(jié)點的能量消耗比之間的對比關(guān)系.由表和圖可以看出，AGEBR在平均能量消耗上略低于MintRoute，這是由于每次選路兼顧了路徑可靠性，能夠解決擁塞問題才會出現(xiàn)這樣的結(jié)果.同時，由于考慮了負載均衡和能量均衡，使得各節(jié)點的能量消耗比例較為平均，方差較小.

表1 MintRoute中路由節(jié)點的能量消耗比Table 1 Energy consumption ratio of routing nodes in MintRoute

表2 AGEBR中路由節(jié)點的能量消耗比Table 2 Energy consumption ratio of routing nodes in AGEBR

圖2 兩種路由情況下不同節(jié)點的能量消耗比Fig.2 Energy consumption ratio of different nodes in two routing situations

5 總 結(jié)

由于蟻群算法具有天然的分布式特性，因此，本文采用的算法也具備分布性的特征，非常適合在傳感網(wǎng)這種分布式網(wǎng)絡(luò)上使用.同時，由于蟻群算法的實現(xiàn)也比較簡單，沒有太多的資源需求，因此也適合在傳感網(wǎng)這種資源受限的網(wǎng)絡(luò)上使用.

［1］ Singh S，Woo M，Raghavendra C S.Power－aware routing in mobile ad hoc networks［C］∥ MobiCom'98 Proceedings of the 4th annual ACM／IEEE international conference on Mobile computing and networking.New York：ACM New York，1998：181－190.

［2］ Chang J H，Tassiulas L.Energy conserving routing in wireless ad－h(huán)oc networks［C］∥ INFOCOM 2000.Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Tel Aviv，Israel：IEEE，2000（1）：22－31.

［3］ Li Q，Aslam J A，Rus D.Online power－aware routing in wireless ad－h(huán)oc networks［C］∥ MobiCom'01 Proceedings of the 7th annual international conference on Mobile computing and networking.New York：ACM New York，2001：97－107.

［4］ Finn G G.Routing and addressing problems in large metropolitan－scale internetworks ［R］.ISI／RR87180，University of Southern California：Information Sciences Institute，1987.

［5］ Takagi H，Kleinrock L.Optimal transmission ranges for randomly distributed packet radio terminals［J］.IEEE Transactions on Communications，1984，32（3）：246－257.

［6］ Zhao J，Govindan R.Understanding packet delivery performance in dense wireless sensor networks［C］∥SenSys'03 Proceedings of the 1st international conference on Embedded networked sensor systems.New York：ACM New York，2003：1－13.

［7］ Zuniga M，Krishnamachari B.Analyzing the transitional region in low power wireless links［C］∥IEEE Secon 2004，2004：517－526.

［8］ Seada K，Zuniga M，Helmy A，et al.Energy efficient forwarding strategies for geographic routing in wireless sensor networks［C］∥ SenSys'04 Proceedings of the 2nd international conference on Embedded networked sensor systems.New York：ACM New York，2004：108－121.

［9］ Zorzi M，Armaroli A.Advancement optimization in multihop wireless networks［C］∥ 2003 IEEE 58th Vehicular Technology Conference，2003（5）：2891－2894.

［10］ Yu Y，Estrin D，Govindan R.Geographical and energyaware routing：A recursive data dissemination protocol for wireless sensor networks［R］.TR－01－0023， UCLA：Computer Science Department，2001.

［11］ Kansal A，Srivastava M B.An environmental energy harvesting framework for sensor networks［C］∥International symposium on Low power electronics and design，2003：481－486.

［12］ 朱程輝，葉福林，基于蟻群算法的無線傳感器網(wǎng)絡(luò)路由算法［J］.微型機與應(yīng)用，2010（15）：67－70.

Geographic Routing of Energy Balance Sensor Network based on Ant Colony Algorithm

SUNYing
（School of Information Engineering，Shenyang University，Shenyang 110044，China）

Ant－colony－based Geographic and Energy Balance Routing （AGEBR）were utilized to establish wireless sensor networks which had survival cycles.As a result，the sensor networks could last a longer period without losing their sensing ability.Experimental results demonstrated that the proposed approach can keep balance of the network energy consumption，prolong the network lifetime，and enhance the successful rate of sending packets without congestion.

ant colony algorithm；geographic routing；energy balance routing；wireless sensor network

TP 393.04

A

1008－9225（2012）02－0057－05

2011－11－18

遼寧省科學(xué)技術(shù)廳科技攻關(guān)項目（2011216004）.

孫 穎（1969－），女，遼寧沈陽人，沈陽大學(xué)副教授.

李 艷】