金永賢, 朱 虹

(浙江師范大學(xué) 數(shù)學(xué)與計算機科學(xué)學(xué)院,浙江 金華 321004)

無線傳感器網(wǎng)絡(luò)是一種便捷的新型自組織網(wǎng)絡(luò)，已經(jīng)廣泛應(yīng)用于工業(yè)、軍事、醫(yī)學(xué)等領(lǐng)域.它是一種由微型傳感器組合而成的網(wǎng)絡(luò)，由于傳感器節(jié)點的能量有限，易受外界干擾，網(wǎng)絡(luò)壽命和數(shù)據(jù)傳輸?shù)目煽啃砸泊蟠蠼档?因此，設(shè)計一種能量有效的路由協(xié)議是非常重要的.

按照路由特性進行分類，無線傳感器路由機制一般可以分為平面型和層次型，或者單徑和多徑路由.單徑路由算法簡單、擴展性好，但容錯性差，容易發(fā)生惡意攻擊.一旦路徑由于各種各樣的原因造成節(jié)點故障，就無法將數(shù)據(jù)包傳輸?shù)侥康墓?jié)點，尤其是在無線傳感器網(wǎng)絡(luò)這種資源很有限的網(wǎng)絡(luò)狀態(tài)下，數(shù)據(jù)傳輸?shù)目煽啃源蟠蠼档?多徑路由協(xié)議的本質(zhì)是在無線傳感器網(wǎng)絡(luò)中構(gòu)建多條備用路徑，避免最優(yōu)路徑發(fā)生故障造成數(shù)據(jù)無法成功傳輸?shù)侥康墓?jié)點.大量研究結(jié)果表明，層次型路由和多徑路由更加有助于提高網(wǎng)絡(luò)的能量有效性，均衡網(wǎng)絡(luò)負(fù)載.層次型路由中，分簇算法將網(wǎng)絡(luò)節(jié)點按層次進行劃分，由若干個相鄰節(jié)點構(gòu)成一個簇，每個簇選出一個簇首節(jié)點CH(cluster head)，簇內(nèi)節(jié)點通信由簇首負(fù)責(zé).簇的形成可以大大減少數(shù)據(jù)的傳輸量，節(jié)約節(jié)點能量.多徑路由中，蟻群算法已逐步成為研究熱點，它是一個分布式算法，最早用來解決TSP(travelling salesman problem)旅行商問題[1].螞蟻在覓食過程中為了給同伴留下食物的位置信號，自身會散發(fā)一種信息素，一條路徑中留下的信息素越多，證明經(jīng)過該路徑的螞蟻越多，那么找到食物的可能性也就越大.蟻群算法正是利用該原理,建立了傳輸數(shù)據(jù)的最優(yōu)路徑.

分簇路由中，早期比較經(jīng)典的路由協(xié)議是LEACH協(xié)議[2]，此協(xié)議以隨機的方式選取簇首，簇首以單跳的形式將簇內(nèi)數(shù)據(jù)融合并轉(zhuǎn)發(fā)至匯聚節(jié)點(sink節(jié)點).由于隨機選取簇首，所以不能保證每次都能選出最優(yōu)簇首進行數(shù)據(jù)傳輸，從而導(dǎo)致網(wǎng)絡(luò)的不穩(wěn)定性，并且每輪重新選取簇首也會大量耗能.文獻(xiàn)[3]提出的PEGASIS協(xié)議是在LEACH協(xié)議基礎(chǔ)上改進的，采用貪婪算法構(gòu)造鏈?zhǔn)浇Y(jié)構(gòu)進行通信，減少了節(jié)點間通信的平均距離及數(shù)據(jù)的發(fā)送量，其缺點是容易造成較長的通信時延.文獻(xiàn)[4]提出了WCA(weighted-clustering approach)協(xié)議，采用競爭方式選取簇首，將節(jié)點剩余能量作為權(quán)重因子系數(shù)，權(quán)重值最高的即成為簇首.文獻(xiàn)[5]提出的HRPNC(hierarchical routing protocol based on non-uniform clustering for wireless sensor network)協(xié)議，是一種非均勻分簇路由協(xié)議，與LEACH的分簇思想相結(jié)合，使用競爭機制競選簇首，有效解決了“熱區(qū)”內(nèi)負(fù)載不均衡的問題.

基于蟻群算法的路由中，文獻(xiàn)[6]提出了DAR協(xié)議，這個協(xié)議的特點是:只有在事件驅(qū)動時網(wǎng)絡(luò)才會運行，這樣可以節(jié)約節(jié)點能耗，所以是一種按需的蟻群多徑路由協(xié)議.該協(xié)議的缺點是在選擇下一跳節(jié)點時沒有考慮能量因素，只適用于小規(guī)模網(wǎng)絡(luò)，有一定的局限性.文獻(xiàn)[7]提出EEABR(energy efficient ant-based routing algorithm)協(xié)議，通過提高信息素增量以降低能耗，延長網(wǎng)絡(luò)壽命.文獻(xiàn)[8]提出ACSBMR協(xié)議，綜合考慮平均剩余能量和節(jié)點最小剩余能量，獲取節(jié)點距離信息作為啟發(fā)函數(shù)，能夠有效降低網(wǎng)絡(luò)時延，均衡節(jié)點能量.文獻(xiàn)[9]提出ACOMP (ant colony optimization multipath routing algorithm adopted angle factor)協(xié)議，通過添加節(jié)點間的角度因子進行路徑方向引導(dǎo)，建立可靠節(jié)能的路由，但是啟發(fā)函數(shù)未充分考慮節(jié)點能量等因素.

在分簇與蟻群相結(jié)合的路由協(xié)議中，MRP協(xié)議[10]在分簇階段通過延時轉(zhuǎn)發(fā)選出簇首，數(shù)據(jù)傳輸時根據(jù)概率選出能量損耗小且長度短的路徑，可以有效延長網(wǎng)絡(luò)壽命，其缺點是容易陷入局部最優(yōu)，引起部分節(jié)點過早死亡;CAEMP協(xié)議[11]采用事件驅(qū)動與查詢法相混合的數(shù)據(jù)采集法，采用“先發(fā)先勝”的原理選舉簇首，減少了開銷，但由于沒有考慮鏈路質(zhì)量等因素，選舉簇首的方法可以進一步改進.

基于上述情況，筆者提出了一個蟻群算法和分簇機制相結(jié)合的多徑路由協(xié)議.其主要特點是：當(dāng)無線傳感器網(wǎng)絡(luò)有事件發(fā)生時，各個有效節(jié)點通過權(quán)重值競選出簇首，通過成簇方式減少數(shù)據(jù)傳輸量.在數(shù)據(jù)傳輸時，使用蟻群算法建立多條路徑，在計算狀態(tài)轉(zhuǎn)移概率公式中，改進了信息素濃度因子和啟發(fā)函數(shù)因子.最后，通過計算選擇一條最優(yōu)路徑把數(shù)據(jù)發(fā)送至sink節(jié)點.

1 MRPCAC協(xié)議

1.1 系統(tǒng)模型

在一個M*M的方形區(qū)域內(nèi)，隨機散布著N個無線傳感器節(jié)點，節(jié)點具有以下特征：1)每個節(jié)點都有唯一ID號(Identification)；2)所有節(jié)點的位置都是固定不變的，且知道基站位置；3)根據(jù)實際情況,傳感器節(jié)點的發(fā)射功率可以獨自調(diào)節(jié)；4)傳感器節(jié)點初始量能及性能是一樣的;5)傳感器節(jié)點間的距離可以通過信號強度判斷.

節(jié)點發(fā)送和接收k比特數(shù)據(jù)所耗的量能公式為:

(1)

ERx(k)=k×Eelec.

(2)

N_IDEresdtoBSPheromone ValueState

圖1 節(jié)點信息表中數(shù)據(jù)的存儲結(jié)構(gòu)

1.2 分簇階段

1.2.1 競選簇首

為了競選出簇首，每個節(jié)點都必須保存一個節(jié)點信息表，用于記錄節(jié)點有關(guān)信息，節(jié)點信息表數(shù)據(jù)存儲結(jié)構(gòu)如圖1所示，節(jié)點信息表中含有的元素名稱和含義如表1所示.

在簇首節(jié)點競爭過程中，若某一個節(jié)點的Eres小于鄰居節(jié)點(所有可以與該節(jié)點直接通信的節(jié)點為鄰居節(jié)點)的平均能量Eavg(Eavg為所有鄰居節(jié)點的剩余能量之和除以鄰居節(jié)點數(shù)目總和)，則退出競選.候選節(jié)點是指所有有資格參與競選的節(jié)點，需要計算自己的權(quán)重值Posi(即位置方程)，每次競選簇首時總是把所有有資格參加競選的節(jié)點中(即一旦某個節(jié)點成為簇首，那么這個簇首和其簇內(nèi)成員節(jié)點在下一個簇首競選中就被排除在外)Posi值最大者當(dāng)選為簇首，直到選出所有簇首，簇首數(shù)量與節(jié)點總數(shù)、簇首允許的最大成員節(jié)點數(shù)及節(jié)點分布等有關(guān).文獻(xiàn)[12]提出的計算節(jié)點i的位置方程Posi如式(3)所示(λ1,λ2，λ3都是權(quán)重因子系數(shù)，表示各項的重要程度，三者之和為1).

(3)

將式(3)改進成

(4)

式(4)增加了Eres和dtoBS.從式(4)可知，Eres越大、dtoBS越小的節(jié)點更易成為簇首，這樣做有助于競選出更“優(yōu)”的簇首.

1.2.2 簇的形成

成功選擇簇首后，簇內(nèi)節(jié)點利用時分多址機制進行通信：簇首使用廣播方式通知其余普通節(jié)點，要求它們選擇加入距離最近的一個簇，并回復(fù)ACK(acknowledgement)消息，根據(jù)普通節(jié)點的回復(fù)情況，簇首為每個加入簇的普通節(jié)點分配時間片.某一時刻，若出現(xiàn)2個一樣的回答信號，則簇首將根據(jù)節(jié)點唯一的標(biāo)識號依次隨機分配不同的時間片.

1.3 多路徑的形成

由于傳感器網(wǎng)絡(luò)被劃分成多個簇，所以它們各自都需要形成自身到達(dá)sink節(jié)點的傳輸路徑.它們有2種發(fā)送路徑的方式：單跳與多跳.如果簇首與sink節(jié)點的距離較短，一般采用單跳方式，這種情況下簇首可以直接將數(shù)據(jù)傳輸至sink節(jié)點，無需通過其他節(jié)點間接轉(zhuǎn)發(fā)；相反，多跳路徑則需要通過其他節(jié)點轉(zhuǎn)發(fā)進行.本文提出的協(xié)議在簇間使用單跳與多跳結(jié)合的混合路由傳輸，簇內(nèi)則使用單跳傳輸方式(即普通節(jié)點直接把數(shù)據(jù)發(fā)送至簇首).

1.3.1 單跳路徑的建立

若dtoBS小于等于最優(yōu)單跳距離dsin，則簇首可以將有效數(shù)據(jù)信息直接傳輸至sink節(jié)點；否則，簇首間將使用蟻群算法建立多條多跳路徑.節(jié)點之點間的最優(yōu)單跳距離dsin為[13]

(5)

式(5)中：γ是信息發(fā)送過程中與距離相關(guān)的損耗系數(shù);Eamp表示功率放大的能量;Eelec表示發(fā)送過程中的電路損耗;Ecpu表示發(fā)送過程中處理數(shù)據(jù)的損耗.

1.3.2 多跳路徑的建立

當(dāng)dtoBS>dsin時，簇首需要通過其他節(jié)點轉(zhuǎn)發(fā)完成數(shù)據(jù)傳輸，即實行多跳傳輸.

當(dāng)簇首接收到成員節(jié)點傳輸來的數(shù)據(jù)后，檢查自身路由信息，若不存在到達(dá)sink節(jié)點的路徑，則緩存要傳輸?shù)臄?shù)據(jù)，同時向前向螞蟻發(fā)送建立路由信息，這類螞蟻的工作就是尋找一條到達(dá)sink節(jié)點的路徑.若已經(jīng)存在有效路徑，則按式(6)計算Pij(t)，并按其大小順序把數(shù)據(jù)發(fā)送轉(zhuǎn)發(fā)至下一個節(jié)點.

(6)

式(6)中:Pij(t)為t時刻某只螞蟻從節(jié)點i移動到節(jié)點j過程的狀態(tài)轉(zhuǎn)移概率;τij(t)為t時刻節(jié)點i至節(jié)點j路徑上的信息素濃度；ηij(t)為t時刻節(jié)點i至節(jié)點j的啟發(fā)函數(shù)值，它可以啟發(fā)螞蟻結(jié)合其他因素選擇較優(yōu)的下一跳節(jié)點；Tabu為禁忌表，它存放著同一類型螞蟻訪問過并留下標(biāo)記的那些節(jié)點，同一類型螞蟻是指從同一源地點出發(fā)的螞蟻；α,β分別代表信息素濃度值及啟發(fā)函數(shù)值的權(quán)重因子系數(shù).式(6)中節(jié)點j需要滿足以下2個條件：1)j是i的鄰節(jié)點，且j比i距離sink節(jié)點更近;2)j不屬于禁忌表.下面對式(6)中的2個因子項進行改進.

1)啟發(fā)函數(shù)因子ηij(t)的改進.啟發(fā)函數(shù)值ηij(t)的原計算公式為

(7)

式(7)只考慮了節(jié)點間的距離因素，因此,把公式改進成為

(8)

圖2 節(jié)點間的角度圖

式(8)中，

(9)

E為下一跳節(jié)點j的初始能量，那么E-Eres就是節(jié)點j的耗能；θ為節(jié)點i至sink節(jié)點連線與節(jié)點i至節(jié)點j連線間的夾角，如圖2所示；k1,k2為權(quán)重因子系數(shù)，本文實驗均設(shè)置為1；dij,dis,djs分別為i到j(luò),i到sink,j到sink的距離.

式(8)增加了能量、角度因素.根據(jù)式(9)和圖2的分析可知，θ值越小時，節(jié)點j與sink節(jié)點的距離djs也就越近，這是因為兩點之間直線距離最短.當(dāng)Eres越大，且θ和dij都比較小時，ηij(t)越大，則j成為下一跳轉(zhuǎn)移節(jié)點的可能性也就更大.

前向螞蟻到達(dá)sink節(jié)點后會自行消亡，并生成相應(yīng)的后向螞蟻原路返回路徑.

2)信息素濃度因子τij(t)的改進.信息素濃度原計算公式為

(10)

(11)

把式(10)改進為

(12)

式(12)中，

(13)

1.4 最優(yōu)路徑尋找與路由維護

當(dāng)建立若干個有效的傳輸路徑后，需從多條路徑中動態(tài)選擇一條最優(yōu)路由，將數(shù)據(jù)傳輸至sink節(jié)點.下面給出一個尋找最優(yōu)路徑的計算方法.

(14)

式(14)中:k為當(dāng)前已經(jīng)建立的有效路徑數(shù)目；Emin為第k條路徑上節(jié)點能量的最小值；Ek為第k條路徑上節(jié)點的總能耗值，即這條路徑上每個節(jié)點的能耗之和，每個節(jié)點能耗等于初始能量和剩余能量之差；Hopk為第k條路徑長度，即跳數(shù).從式(14)可知，長度越短或?qū)嶋H總能耗越少的路徑，fk值越大.其中，fk最大的路徑就成為最優(yōu)路徑.若某條路徑具有能量瓶頸，則不能成為最優(yōu)路由.

2 仿真實驗結(jié)果與分析

為驗證本文提出協(xié)議算法的有效性，在NS2網(wǎng)絡(luò)仿真環(huán)境下對LEACH協(xié)議[2]、EEABR協(xié)議[7]、CAEMP協(xié)議[11〗和MRPCAC協(xié)議進行實驗對比，模擬實驗環(huán)境所用的參數(shù)如表2所示.下面從能量有效性(每輪平均能耗和簇首節(jié)點能耗波動情況)和網(wǎng)絡(luò)生存時間(節(jié)點存活數(shù)目、節(jié)點死亡情況)進行實驗對比.

表2 仿真實驗參數(shù)

協(xié)議圖3 4種協(xié)議每輪平均能耗對比圖

2.1 能量有效性分析與比較

2.1.1 每輪平均能耗

每輪平均能耗是指每輪所有節(jié)點的能耗與節(jié)點總數(shù)之比.由圖3分析可以得出，每輪平均耗能：EACH協(xié)議約為0.057 J;EEABR協(xié)議約為0.036 J;CAEMP協(xié)議約為0.025 J;MRPCAC協(xié)議約為0.021 J.在這4種協(xié)議中，MRPCAC能耗平均值最低.下面分析一下其中原因：LEACH協(xié)議以隨機的方式選取簇首，簇首以單跳的形式將簇內(nèi)數(shù)據(jù)融合并轉(zhuǎn)發(fā)至sink節(jié)點.由于隨機選取簇首，所以不能

保證每次都能選出最優(yōu)簇首，從而導(dǎo)致網(wǎng)絡(luò)的不穩(wěn)定性，并且每輪重新選取簇首也會大量耗能.由于EEABR協(xié)議是通過蟻群算法建立多徑路由，通過提高信息素增量以降低能耗，延長網(wǎng)絡(luò)壽命，因而性能好于LEACH.CAEMP協(xié)議采用事件驅(qū)動與查詢法相混合的數(shù)據(jù)采集法，采用“先發(fā)先勝”的原理選取簇首，這樣可以減少開銷.MRPCAC協(xié)議為了降低數(shù)據(jù)發(fā)送量，用分簇技術(shù)將數(shù)據(jù)直接發(fā)送到sink節(jié)點；再加上通過對預(yù)先設(shè)定的閾值判斷來決定是否需要重新選舉簇首，從而避免每輪重新選舉簇首所帶來的能量消耗；另外，MRPCAC在簇首間使用多跳路由機制，能夠?qū)⒛芰控?fù)載均衡地分布在網(wǎng)絡(luò)中，避免局部產(chǎn)生耗能過大的現(xiàn)象，這樣做有利于均衡整個網(wǎng)絡(luò)能耗.

圖4 4種協(xié)議簇首能耗波動情況對比圖

2.1.2 簇首節(jié)點能耗波動

從圖4可以看出，LEACH算法采用每輪重新選取簇首，并且采取簇首輪換機制，簇首耗能較多且波動較大；EEABR協(xié)議在分簇方式上沒有考慮非均勻分簇，靠近sink節(jié)點的簇首能耗更大；在數(shù)據(jù)傳輸過程中，由于CAEMP協(xié)議使用信息素累加方法，在路由建立后，信息素越高的路徑承擔(dān)數(shù)據(jù)傳輸

的任務(wù)也越重，因而消耗的能量更大；MRPCAC協(xié)議只是在第1輪使用競選方法，之后只在簇內(nèi)進行競選，所以簇首分布較為穩(wěn)定，耗能較少.綜上所述，MRPCAC協(xié)議只在第1輪會消耗較大能量，因而，其消耗的總能量比其他3種協(xié)議更少，從而節(jié)能效果更好.

2.2 網(wǎng)絡(luò)生存時間分析與比較

從圖5和圖6可看出，LEACH協(xié)議從網(wǎng)絡(luò)系統(tǒng)運作的第500輪左右就出現(xiàn)死亡節(jié)點(FND表示出現(xiàn)第1個死亡節(jié)點、LND表示最后一個死亡節(jié)點出現(xiàn))，EEABR協(xié)議從900輪左右就開始出現(xiàn)死亡節(jié)點，CAEMP從1 100輪就開始出現(xiàn)死亡節(jié)點，而MRPCAC的死亡節(jié)點則是從1 500輪以后才出現(xiàn).LEACH協(xié)議大約在800輪已經(jīng)有一半的節(jié)點死亡，而另外3個協(xié)議還沒有出現(xiàn)死亡節(jié)點，在LEACH出現(xiàn)全部死亡節(jié)點時，CAEMP和MRPCAC的大部分節(jié)點還是存活的.CAEMP協(xié)議最后一個死亡節(jié)點大約出現(xiàn)在1 500輪，而MRPCAC協(xié)議大約出現(xiàn)在1 700輪，從而可知，MRPCAC協(xié)議的網(wǎng)絡(luò)壽命與CAEMP協(xié)議比，也是有所延長的.

圖5 網(wǎng)絡(luò)中節(jié)點存活數(shù)目對比 圖6 4種協(xié)議節(jié)點的FND和LND數(shù)目對比

3 結(jié) 語

本文研究和提出了MRPCAC協(xié)議.此協(xié)議在選擇簇首時考慮了能量和鄰居節(jié)點數(shù)量等.簇首間利用蟻群算法建立多條路徑，在計算狀態(tài)轉(zhuǎn)移概率公式中，改進了信息素濃度因子和啟發(fā)函數(shù)因子.協(xié)議給出了最優(yōu)路徑計算方法.最后實驗結(jié)果表明，和其他協(xié)議相比，MRPCAC具有能量有效性高、網(wǎng)絡(luò)負(fù)載均衡和網(wǎng)絡(luò)壽命長等優(yōu)點.