廖福保，張文梅

(1.廣東農(nóng)工商職業(yè)技術(shù)學(xué)院 計算機系，廣州 510507; 2.廣東農(nóng)工商職業(yè)技術(shù)學(xué)院 機電系，廣州 510507)

改進(jìn)的基于蟻群算法的非均勻分簇路由協(xié)議

廖福保1，張文梅2

(1.廣東農(nóng)工商職業(yè)技術(shù)學(xué)院 計算機系，廣州 510507; 2.廣東農(nóng)工商職業(yè)技術(shù)學(xué)院 機電系，廣州 510507)

針對無線傳感器網(wǎng)絡(luò)中傳感器節(jié)點隨機分布造成能耗不均和“熱區(qū)”等問題，提出了一種改進(jìn)的基于蟻群算法的非均勻分簇路由協(xié)議；該協(xié)議也采用“輪”方式運行，每輪簇首選舉開始階段，根據(jù)節(jié)點剩余能量、節(jié)點密度，結(jié)合節(jié)點到Sink節(jié)點的距離來構(gòu)造不均勻的競選半徑，每個節(jié)點根據(jù)競選半徑范圍內(nèi)鄰居節(jié)點計算剩余能量比及距離偏差平均值，從而計算出其簇首競爭等待時間，采用時間等候簇首競選機制來選舉出簇首，平衡簇內(nèi)的通信能耗；數(shù)據(jù)傳輸階段，考慮剩余能量、通信能耗、鏈路質(zhì)量、傳輸時延等因素，采用改進(jìn)的蟻群算法構(gòu)造最優(yōu)傳輸路徑，數(shù)據(jù)傳輸?shù)耐瑫r更新信息素，從而達(dá)到自適應(yīng)、動態(tài)優(yōu)化地建立和維護(hù)傳輸路徑；仿真結(jié)果表明，該路由協(xié)議能有效節(jié)約能量和均衡能耗，延長網(wǎng)絡(luò)生命周期，改善鏈路質(zhì)量，減少傳輸時延。

無線傳感器網(wǎng)絡(luò)；非均勻分簇；蟻群算法；路由協(xié)議

0 引言

無線傳感器網(wǎng)絡(luò)是由部署在監(jiān)測區(qū)域內(nèi)的大量微型傳感器節(jié)點以自組織方式組成，通常包含大量的傳感器節(jié)點和一個Sink節(jié)點，這些傳感器節(jié)點用于采集監(jiān)控區(qū)域內(nèi)的數(shù)據(jù)，并以無線通信的方式將數(shù)據(jù)上傳給Sink節(jié)點，無線傳感器網(wǎng)絡(luò)已被廣泛用于軍事、環(huán)境、醫(yī)療健康等領(lǐng)域[1-3]。

傳感器節(jié)點通常采用人工布置、飛機布撒等方式大量部署于監(jiān)控區(qū)域，且這些傳感器節(jié)點大多采用電池供電。由于監(jiān)控區(qū)域的復(fù)雜和任意，節(jié)點的電池難以補充和更換，因此設(shè)計節(jié)省能量消耗、延長生命周期的路由算法是目前無線傳感器網(wǎng)絡(luò)的研究熱點之一[4]。

目前，學(xué)者們提出了多種路由算法和協(xié)議，包括平面路由協(xié)議和分簇路由協(xié)議[5]，其中分簇路由協(xié)議比平面路由具有更好的可擴展性和能量均衡性，因此更適合無線傳感器網(wǎng)絡(luò)[6]。

在分簇路由協(xié)議中，無線傳感器網(wǎng)絡(luò)被劃分為多個不同的簇，每個簇由一個簇首和眾多的簇內(nèi)節(jié)點組成，簇內(nèi)節(jié)點負(fù)責(zé)采集監(jiān)控區(qū)域中的數(shù)據(jù)；簇首節(jié)點負(fù)責(zé)管理簇內(nèi)節(jié)點、接收簇內(nèi)節(jié)點采集的數(shù)據(jù)并將其融合后轉(zhuǎn)發(fā)至Sink節(jié)點[7]。分簇路由協(xié)議能將整個網(wǎng)絡(luò)的能量負(fù)載平均分配到每個節(jié)點，從而降低網(wǎng)絡(luò)能量的消耗，但在均勻分簇的無線傳感器網(wǎng)絡(luò)中，簇頭與Sink節(jié)點的通信無論采用單跳或多跳方式，都會存在“熱區(qū)”問題。

針對分簇路由協(xié)議中可能出現(xiàn)的“熱區(qū)”問題，本文在LEACH協(xié)議[8]、EEUC協(xié)議[9]等路由協(xié)議的基礎(chǔ)上提出了改進(jìn)的基于蟻群算法的非均勻分簇路由協(xié)議。

1 相關(guān)工作

1.1 相關(guān)算法

LEACH協(xié)議是最有典型的分簇路由協(xié)議，采用“輪”的概念周期性選擇簇首。每一“輪”每個節(jié)點都生成一個0-1之間的隨機數(shù)，當(dāng)該隨機數(shù)大于閾值T(n)，則該節(jié)點選為簇首。閾值T(n)采用公式(1)計算。

(1)

圖1 LEACH分簇拓?fù)涫疽?/p>

分簇完成后，簇首以單跳的方式將數(shù)據(jù)傳輸?shù)絊ink節(jié)點。

LEACH協(xié)議主要考慮的是簇內(nèi)成員節(jié)點的能耗，而沒有考慮簇首間的能耗問題。已有研究[9]表明簇首與Sink節(jié)點間采用多跳方式通信更有利于節(jié)約能量，但由于越靠近Sink節(jié)點的簇首需要轉(zhuǎn)發(fā)越多的數(shù)據(jù)，這樣越靠近Sink節(jié)點的簇首會越早耗盡能量而失效，形成“熱區(qū)”。

文獻(xiàn)[10-11]提出了EEUC、DEBUC算法，將整個網(wǎng)絡(luò)分為非均勻的簇，靠近Sink節(jié)點的簇小，可節(jié)省簇內(nèi)通信消耗，節(jié)省能量用于簇間數(shù)據(jù)轉(zhuǎn)發(fā)。

EEUC算法在簇的形成過程，利用公式(2)計算候選簇首的競選半徑，靠近Sink節(jié)點的競選半徑小，使得靠近Sink節(jié)點的簇的成員數(shù)量較少，從而為轉(zhuǎn)發(fā)數(shù)據(jù)節(jié)省能量，達(dá)到均衡能量的目的。

(2)

簇首競選完成后，簇首廣播競選獲勝消息，普通節(jié)點根據(jù)接收到的信號強度加入到簇中成為該簇的成員節(jié)點。分簇完成后，簇首以多跳的方式將數(shù)據(jù)傳輸?shù)絊ink節(jié)點。

1.2 存在的問題分析

在LEACH、EEUC協(xié)議及其眾多分簇路由協(xié)議中，成員節(jié)點都不直接與Sink節(jié)點通信，而必須通過簇首與Sink節(jié)點通信，沒有考慮有些成員節(jié)點直接與Sink節(jié)點通信的能耗小于通過成員節(jié)點與簇首通信的能耗。如圖1所示，成員節(jié)點A、B離Sink節(jié)點近，離簇首節(jié)點遠(yuǎn)，造成成員節(jié)點A、B通過簇首與Sink節(jié)點通信比A、B與Sink節(jié)點直接通信所耗能量更多。

另外，由于節(jié)點在監(jiān)控區(qū)域的隨機性，會造成某些區(qū)域簇首過多或過少，或者某些簇中的成員節(jié)點過多或過少，這些都會造成某些簇首過早耗盡能量而死亡。文獻(xiàn)[12]提出EBUCA算法利用節(jié)點剩余能量和節(jié)點密度來進(jìn)行簇首選舉，達(dá)到均衡節(jié)點能耗的目的,但沒有給出鄰居節(jié)點數(shù)量的獲取方式。文獻(xiàn)[13]根據(jù)節(jié)點到Sink節(jié)點的距離計算簇首競爭時間，但在多跳路由中簇首的下一跳并不一定是Sink節(jié)點，并不利于能量均衡。

文獻(xiàn)[14]在非均勻分簇的基礎(chǔ)上，簇間通信采用蟻群算法進(jìn)行優(yōu)化(ACOUC)，引入鏈路可靠性和實時性參數(shù)，但并沒有考慮通信能耗。文獻(xiàn)[15-16]在簇間路由選舉中，采用優(yōu)化的對蟻群算法進(jìn)行路徑搜索，均沒有考慮鏈路質(zhì)量等問題。文獻(xiàn)[9]說明了鏈路質(zhì)量好的路由能有效減少節(jié)點能耗，提高網(wǎng)絡(luò)能量利用率。目前無線傳感網(wǎng)絡(luò)的路由協(xié)議極少考慮到鏈路質(zhì)量的問題，并不能很好地投入到實踐應(yīng)用中。

本文綜合以上問題，提出了一種改進(jìn)的基于蟻群算法的非均勻分簇協(xié)議，在成簇階段，節(jié)點根據(jù)區(qū)域節(jié)點密度、節(jié)點剩余能量和節(jié)點到Sink節(jié)點的距離來決定簇半徑的大小，在節(jié)點密度大的區(qū)域及剩余能量小的節(jié)點減少競爭半徑，達(dá)到能量均衡的目的。節(jié)點競選簇首時根據(jù)節(jié)點剩余能量、鄰居節(jié)點分布均勻度計算簇首競爭等待時間，采用時間等候機制增大剩余能量高、鄰居節(jié)點分布均勻的節(jié)點成為簇首的機會，減少簇內(nèi)數(shù)據(jù)傳輸?shù)哪芎?。在簇間數(shù)據(jù)傳輸階段，采用蟻群算法多跳方式建立簇首到Sink節(jié)點的最優(yōu)路徑，考慮剩余能量、傳輸延時、鏈路質(zhì)量等因素，能減少簇首能量消耗，延長網(wǎng)絡(luò)生命周期。

2 相關(guān)模型

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

本文算法對無線傳感器的網(wǎng)絡(luò)模型作如下假設(shè)：1)節(jié)點隨機部署于M×M的正方形區(qū)域內(nèi)，Sink節(jié)點位于中央且位置固定，能量不受限；2)除Sink節(jié)點外的其它所有節(jié)點的初始能量相等且有限，節(jié)點可感知自身的剩余能量；3)每個節(jié)點部署后位置固定，節(jié)點間能相互通信，且都具有唯一的ID號；4)節(jié)點可以根據(jù)需要自由調(diào)整發(fā)射功率；5)節(jié)點能根據(jù)接收到的信號強度RSSI來計算發(fā)出者到自身的近似距離。

2.2 通信模型

已有研究[17]表明，無線傳感器網(wǎng)絡(luò)中節(jié)點間數(shù)據(jù)傳輸所耗的能量遠(yuǎn)大于其它能耗。本文采用與文獻(xiàn)[8]一樣的無線通信模型，節(jié)點發(fā)送k比特數(shù)據(jù)所消耗的能量如下：

(3)

節(jié)點接收k比特數(shù)據(jù)所消耗的能量如下：

ERx(k)=k×Eelec

(4)

3 改進(jìn)的基于蟻群算法的非均勻分簇路由協(xié)議

本算法類似于LEACH協(xié)議,采用“輪”方式運行。每“輪”利用簇首競爭等待時間機制進(jìn)行簇首選舉，簇內(nèi)數(shù)據(jù)利用TDMA方式傳輸，簇首采用改進(jìn)的蟻群算法多跳方式將數(shù)據(jù)傳輸?shù)絊ink節(jié)點。

3.1 概念描述

為便于描述，對本文所涉及的概念說明如下：

1)競選半徑。節(jié)點競選簇頭時的半徑，本文根據(jù)公式(5)計算競選半徑。

(5)

(6)

(7)

其中:Qi為節(jié)點si節(jié)點密度、Pi為可工作剩余能量比，Neighbor(i)為節(jié)點si的鄰居節(jié)點個數(shù)，N為網(wǎng)絡(luò)中所有節(jié)點個數(shù)，einit為節(jié)點初始能量，ei為節(jié)點當(dāng)前能量，emin為節(jié)點最低工作能量，c、α、β為0～1之間的值且c+α+β=1，用于控制取值范圍的參數(shù)。

由式(5)可知，當(dāng)節(jié)點密度相同、可工作剩余能量比相同時，簇首到Sink節(jié)點的距離越近，競選半徑越小，簇首可節(jié)省能量用于簇間轉(zhuǎn)發(fā)數(shù)據(jù)；當(dāng)簇首到Sink節(jié)點的距離相同、可工作剩余能量比相同時，節(jié)點密度越大，競選半徑越小，該區(qū)域的簇首數(shù)目相應(yīng)增多；當(dāng)簇首到Sink節(jié)點的距離相同、節(jié)點密度相同時，剩余能量越大，競選半徑越大，其它簇中成員節(jié)點越小，可節(jié)省其它簇首的能量，從而達(dá)到各簇的能耗均衡。

2)鄰居節(jié)點。節(jié)點sj為si的鄰居節(jié)點需同時滿足式(8)和式(9)兩個條件。

d(sj,si)

(8)

d(sj,si)

(9)

式中,d(sj,si)節(jié)點sj和節(jié)點si之間的距離。從式(9)可以看出，當(dāng)節(jié)點sj與si的距離大于與Sink節(jié)點的距離時，節(jié)點sj也不是節(jié)點si的鄰居節(jié)點，sj將不屬于任何簇，而直接將數(shù)據(jù)傳輸至Sink節(jié)點。

3)節(jié)點度dui。節(jié)點si的鄰居節(jié)點總數(shù)目。

4)鄰居表。每個節(jié)點保存一個鄰居節(jié)點表以存儲鄰居節(jié)點的相關(guān)信息，如表1所示。

表1 節(jié)點的鄰居表內(nèi)容

5)剩余能量比PEi。PEi表示節(jié)點si的所有鄰居節(jié)點剩余能量的平均值與節(jié)點si的剩余能量的比值，如公式(10)所示，PEi的值越小，則節(jié)點si相對于其鄰居節(jié)點的剩余能量越大。

(10)

6)距離偏差平均值ddi。如公式(11)、(12)所示，dij為節(jié)點sj到節(jié)點si的距離，dai為si各鄰居節(jié)點到si的平均距離，ddi表示si各鄰居節(jié)點到si的距離與dai之間偏差的平均值，平均值越小，代表節(jié)點si與鄰居節(jié)點的距離分布越均勻，就越能均衡簇內(nèi)的能量消耗。

(11)

(12)

7)簇首競爭等待時間ti。從節(jié)點收到Sink節(jié)點通知簇首競爭到本節(jié)點發(fā)出簇首競爭消息的等待時間，如公式(13)所示。

(13)

式中：α為[0.9,1]之間的隨機數(shù)，T為規(guī)定的簇首競爭持續(xù)時間，β為鄰居節(jié)點分布均勻度調(diào)節(jié)因子。從式中可以看出，簇首競爭等待時間tcomp_i由節(jié)點剩余能量比、鄰居節(jié)點分布的均勻度分布決定，剩余能量越高、鄰居節(jié)點分布越平均，tcomp_i的取值就越小，簇首競爭等待時間越短，節(jié)點競選成為簇首的機會越大。

3.2 簇首選舉及簇建立

在無線傳感器網(wǎng)絡(luò)分簇協(xié)議中，簇首對整個網(wǎng)絡(luò)能耗的均衡占用重要的位置；采用簇間多跳路由時，簇首除了要管理本簇的數(shù)據(jù)收發(fā)外，還需要中繼轉(zhuǎn)發(fā)其他簇的數(shù)據(jù)，任務(wù)較重；靠近Sink節(jié)點的由于需要轉(zhuǎn)發(fā)的數(shù)據(jù)量更大，任務(wù)更重。多個文獻(xiàn)[10-13]均證明了非均勻分簇能有效均衡能耗，能緩解能量空洞。本文在對無線傳感器網(wǎng)絡(luò)進(jìn)行非均勻分簇的基礎(chǔ)上，建立了本文的簇首選舉算法，見算法1。每“輪”開始時網(wǎng)絡(luò)中所有節(jié)點都參與簇首競爭，采用時序的方式選擇簇首。

算法1:簇首選擇算法步驟

2)Sink節(jié)點向全網(wǎng)發(fā)出Par_CLU分簇信號，各個節(jié)點根據(jù)接收到的信號強度RSSIi計算其到Sink節(jié)點的距離d(si,DS)，并根據(jù)公式(5)確定其競選半徑Ri。節(jié)點清空鄰居節(jié)點表，為下一步做準(zhǔn)備。

3)每個節(jié)點在其競選半徑Ri范圍內(nèi)廣播競選消息Sel_CLU,該消息包括節(jié)點的ID、當(dāng)前剩余能量ei。

5)各節(jié)點根據(jù)鄰居節(jié)點表中的信息，計算節(jié)點度dui，再按照公式(10)計算出剩余能量比PEi，根據(jù)公式(11)(12)計算出距離偏差平均值ddi。

6)各節(jié)點再根據(jù)公式(13)計算出自身的簇頭競爭時間tcomp_i。

7)Sink節(jié)點發(fā)出同步信號Tim_MSG，以同步各節(jié)點的時間。

8)節(jié)點si收到Tim_MSG信息后，si開始計時ti，同時監(jiān)聽其他節(jié)點的信息。

9)對于節(jié)點si有：

10)if(ti

11)if收到節(jié)點sj的簇首失敗消息Fai_CLU

12)ifsj為si的鄰居節(jié)點

13)更新鄰居表

14)endif

15)endif

16)if收到節(jié)點sj的簇首成功消息Suc_CLU

17)ifsj為si的鄰居節(jié)點

18)si廣播競選失敗的信息Fai_CLU

19)更新鄰居表

20)endif

21)else

22)繼續(xù)監(jiān)聽并計時

23)endif

24)endif

25)if(ti==tcomp_i)

26)發(fā)出本節(jié)點的簇首競選成功的消息Suc_CLU

27)清空鄰居表

28)endif

29)選舉結(jié)束后，簇首競選失敗的節(jié)點選擇加入到鄰居表中與其距離最近的簇首所在的簇中。如果鄰居節(jié)點中不存在簇首，則加入到最近的鄰居節(jié)點所在的簇，成為該簇成員節(jié)點。

30)分簇結(jié)束后，各個簇首向全網(wǎng)廣播競選成功的消息CLU_MSG,其它簇首節(jié)點收到該信息，如果沒有處理過且距離Sink節(jié)點更近，轉(zhuǎn)發(fā)CLU_MSG，Sink節(jié)點CLU_MSG信息后記錄簇首的id。最后Sink節(jié)點將記錄下所有的簇首id。

下面對算法1進(jìn)行具體的解釋。

第1行，各節(jié)點廣播Nei_MSG消息，從而計算出節(jié)點密度和可工作剩余能量比。第2行，各節(jié)點接收Sink節(jié)點發(fā)出的Par_CLU分簇信號，并根據(jù)RSSIi值、節(jié)點密度和可工作剩余能量比計算出競選半徑。第3-5行，各節(jié)點廣播Sel_CLU消息，計算出節(jié)點間距離dj、節(jié)點度dui，再計算出距離偏差平均值ddi和剩余能量比PEi。第6行，各節(jié)點根據(jù)距離偏差平均值ddi和剩余能量比PEi計算其競爭等待時間tcomp_i，鄰居節(jié)點分布越均衡、剩余能量越大，其競爭等待時間越短，競爭獲得簇首的機會越大。第10-24行為節(jié)點si的競爭等待時間沒有到達(dá)時的處理情況；第11-15行為在此期間si收到其它鄰居節(jié)點的Fai_CLU消息，則更新鄰居表；第16-23行為在此期間si如果收到其它鄰居節(jié)點的Suc_CLU消息，si發(fā)出失敗的信息并更新鄰居表，否則si繼續(xù)計時并監(jiān)聽網(wǎng)絡(luò)中的信息。第25-28行為節(jié)點si沒有收到其它鄰居節(jié)點的競選成功的Suc_CLU消息，且本節(jié)點的競爭等待時間已經(jīng)到達(dá)時，則發(fā)出簇首競選成功的消息Suc_CLU。第29行為簇首競選失敗的節(jié)點選擇加入到鄰居表中與其距離最近的簇首所在的簇中；如果鄰居節(jié)點中不存在簇首，則加入到最近的鄰居節(jié)點所在的簇，成為該簇成員節(jié)點；離簇首越近，可以節(jié)省簇內(nèi)通信的能量。第30行為各個簇首向全網(wǎng)廣播競選成功的消息CLU_MSG,同時收集其它簇首廣播的消息，為后續(xù)路由做準(zhǔn)備。CLU_MSG信息包括簇首ID、剩余能量、到Sink節(jié)點的距離d(si,DS)。

算法中將整個網(wǎng)絡(luò)劃分為大小不等的簇，靠近Sink節(jié)點的簇半徑小，同時簇首競爭等待時間考慮了剩余能量、節(jié)點分布均勻性等因素，能夠保證選舉的簇首綜合性能最優(yōu)，有利于均衡能耗。

3.3 路徑搜索

成簇完成后，從Sink節(jié)點釋放螞蟻開始搜索，每個簇首都維護(hù)一個簇首節(jié)點的路由表(見表2)。

表2 簇首節(jié)點路由表

算法2:路徑搜索算法步驟

2)whilesjID!=soID

3)ifsj的螞蟻Ao到達(dá)簇首si

4)ifd(si,so)d(sj,DS)

5)ifd(si,DS)

6)增加si路由表記錄

7)更新螞蟻Ao攜帶的信息

8)轉(zhuǎn)發(fā)Ao

9)endif

10)endif

11)endif

12)endwhile

13)螞蟻都釋放完畢后，各簇首si根據(jù)路由表計算其到鄰居簇首sj(sj∈Ci，Ci為si路由表中的簇首集)的初始信息素濃度(見公式14)。

(14)

14)再根據(jù)公式(15)計算si將sj作為下一跳的概率pij

(15)

(16)

下面對算法2進(jìn)行具體的解釋。

3.4 數(shù)據(jù)傳輸

數(shù)據(jù)傳輸分為簇內(nèi)傳輸和簇間傳輸, 簇內(nèi)傳輸由簇內(nèi)成員按時分多路復(fù)用(TDMA)方式把數(shù)據(jù)傳送給簇首, 簇首經(jīng)過數(shù)據(jù)處理后再通過簇間多跳路由將數(shù)據(jù)傳輸?shù)絊ink節(jié)點。

在簇間傳輸中, 簇首si依照概率pij最大的簇首sj作為下一跳。在數(shù)據(jù)傳輸過程中, 統(tǒng)計發(fā)送和接收數(shù)據(jù)包數(shù)量、轉(zhuǎn)發(fā)延時等信息。傳輸成功后, 按公式(17)對對應(yīng)路由的信息素進(jìn)行更新。為了節(jié)省能耗, 只在鏈路每成功發(fā)送一定數(shù)量的數(shù)據(jù)包后才對信息素進(jìn)行更新。

τij=(1-ρ)·τij+ρ·Δτij

(17)

(18)

式(17～18)中，ρ為信息素?fù)]發(fā)參數(shù)，ω為調(diào)節(jié)因子，均為0～1之間的值。ni為節(jié)點si在t時間內(nèi)發(fā)送的數(shù)據(jù)包數(shù)量，mj為節(jié)點sj在t時間內(nèi)接收到的數(shù)據(jù)包數(shù)量(mj≤ni),mj/ni即為鏈路質(zhì)量[19]。tij為從節(jié)點si傳輸數(shù)據(jù)到節(jié)點sj的時延，tmax為單跳最大時延。從公式(17)～(18)中可以看出，當(dāng)相鄰簇首間鏈路質(zhì)量越高、時延越短，在該路徑上的信息素濃度就越大，被選中作為下一跳的概率越大。

4 仿真實驗

本文采用OPNET仿真軟件對本文算法與EEUC、ACOUC算法進(jìn)行比較實驗。

4.1 仿真環(huán)境與參數(shù)設(shè)置

本文無線傳感網(wǎng)絡(luò)的仿真區(qū)域為100m×100m，100個節(jié)點在該區(qū)域中隨機部署，Sink節(jié)點位于區(qū)域中心。實驗中，數(shù)據(jù)傳輸模型采用一階無線電能量模型，實驗仿真參數(shù)如表3所示。

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

4.2 仿真結(jié)果分析

簇首選擇完成后，網(wǎng)絡(luò)節(jié)點分布如圖2所示。由于本文算法根據(jù)鄰居節(jié)點密度、鄰居節(jié)點分布均勻度等因素選擇簇首，從圖中可以看出，在節(jié)點密度大的區(qū)域簇首多，節(jié)點密度小的區(qū)域簇首少，簇首根據(jù)周圍節(jié)點的密度分布于無線傳感器網(wǎng)絡(luò)中。

圖2 節(jié)點分布圖

由圖3所示，比較3種算法的生命周期，EEUC和ACOUC算法未考慮節(jié)點密度、節(jié)點分布均勻度、鏈路質(zhì)量對網(wǎng)絡(luò)的影響，生命周期較短。而本文算法簇首選舉考慮了節(jié)點密度、節(jié)點分布均勻度等的影響，在簇間路由中選擇鏈路質(zhì)量較好、延時短、能耗低的路徑進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)，因此從首節(jié)點失效到最后一個節(jié)點失效的時間都比EEUC和ACOUC算法滯后，能更好的均衡網(wǎng)絡(luò)能耗，延長網(wǎng)絡(luò)生命周期。

圖4對比了3種算法在每輪網(wǎng)絡(luò)剩余總能量的變化情況，可以看出本文算法的能量消耗較EEUC、ACOUC算法更為緩慢，生存時間更長。表明本文算法簇間路由采用改進(jìn)的蟻群算法，考慮簇首剩余能量、傳輸時延、鏈路質(zhì)量等因素更能有效地節(jié)約能量。

圖4 剩余總能量對比

圖5對比了3種算法在每輪網(wǎng)絡(luò)數(shù)據(jù)傳輸時平均時延的變化情況，本文算法采用蟻群算法，收斂速度快，傳輸路徑更為優(yōu)化，在選擇下一跳時考慮了時延的影響，因此本文算法的平均時延較EEUC、ACOUC算法更短，數(shù)據(jù)傳輸更為及時。

圖5 平均時延對比

實驗中以丟包率來衡量通信可靠性，圖6對比了3種算法前100輪每輪中的丟包率變化情況。本文算法采用改進(jìn)的蟻群算法，螞蟻信息素更新時考慮鏈路質(zhì)量而動態(tài)調(diào)整，簇首數(shù)據(jù)轉(zhuǎn)發(fā)時選擇鏈路質(zhì)量更高的路徑。結(jié)果表明，本文算法比EEUC、ACOUC算法的可靠性更高。

圖6 丟包率對比

5 結(jié)語

本文借鑒非均勻分簇的思想，根據(jù)節(jié)點剩余能量、鄰居節(jié)點分布均勻度計算簇首競爭等待時間，使節(jié)點的簇首競爭等待時間不同，通過時序方式選擇簇首，剩余能量高、鄰居節(jié)點分布均勻的節(jié)點成為簇首的機會更大。在簇間路由階段，采用改進(jìn)的蟻群算法多跳方式傳輸數(shù)據(jù)到Sink節(jié)點，考慮剩余能量、傳輸延時、鏈路質(zhì)量等因素，選擇一條最優(yōu)的傳輸路徑。通過對本文算法、EEUC和ACOUC算法進(jìn)行比較實驗，結(jié)果表明本文算法更能有效均衡網(wǎng)絡(luò)能耗，時延更短，丟包率更低，有效延長網(wǎng)絡(luò)生命周期。

另外，本文算法中的各個參數(shù)會影響效率和性能，且各個參數(shù)存在關(guān)聯(lián)性，如何確定各參數(shù)值及其最佳組合需要進(jìn)一步的實驗和研究。

[1]YickJ,MukherjeeB,GhosalD.Wirelesssensornetworksurvey[J] .ComputerNetworks, 2008,52(12):2292-2330.

[2] 蘇金樹，郭文忠，余朝龍，等.負(fù)載均衡感知的無線傳感器網(wǎng)絡(luò)容錯分簇算法[J].計算機學(xué)報，2014，37(2)：445-456.

[3] 董 穎，蘇真真，周占穎，等.一種基于節(jié)點剩余能量和位置的LEACH改進(jìn)算法[J].四川大學(xué)學(xué)報(工程科學(xué)版)，2015，47(2)：136-141.

[4]BhattacharyaI,GhoshS,KunduS.MaximizinglifetimeofWirelessSensorNetworkthroughextendedLEACHAlgorithm[M].AdvancesinComputerScienceandInformationTechnology.ComputerScienceandInformationTechnology.BerlinHeidelberg:Springer,2012:377-386.

[5]LiuY,ChenX,LongC,etal.Improvementofhierarchicalroutingalgorithmforheterogeneouswirelesssensornetworks[J].JournalofComputationalInformationSystems, 2012,8(10):4143-4150.

[6] 任非原，黃海寧，林 闖.無線傳感器網(wǎng)絡(luò)[J].軟件學(xué)報，2003，14(7)：1282-1291.

[7] 劉 群，白全煒，曾憲華，等.能量感知的WSN節(jié)點分類控制路由算法[J].傳感技術(shù)學(xué)報，2011，24(7)：1053-1059.

[8]HeinzelmanW.ChandrakasanA.BalakrishnamH.Energy-efficientcommunicationprotocolforwirelessmicrosensornetworks[A].Procofthe33rdConfonSystemSciences[C].Piscataway.NJ:IEEE. 2000:3005-3014.

[9]MhatreV,RosenbergC.Designguidelinesforwirelesssensornetworks:Communication,clusteringandaggregation[J].AdHocNetworks, 2004, 2(1): 45-63.

[10] 李成法，陳貴海，葉 懋,等.一種基于非均勻分簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議[J].計算機學(xué)報，2007，30(1)：27-36.

[11] 蔣暢江，石為人，唐賢倫,等.能量均衡的無線傳感器網(wǎng)絡(luò)非均勻分簇路由協(xié)議[J].軟件學(xué)報,2012,23(5)：1222-1232.

[12] 盧先順，王瑩瑩，王洪斌,等.無線傳感器網(wǎng)絡(luò)能量均衡的非均勻分簇算法[J].計算機科學(xué),2013,40(5)：78-81.

[13] 皇蘇斌，王忠群，汪千松. 能量均衡的無線傳感器網(wǎng)絡(luò)節(jié)點非均勻分布路由協(xié)議[J].計算機應(yīng)用,2011, 31(11)：2887-2890.

[14] 張榮博,曹建福.利用蟻群優(yōu)化的非均勻分簇?zé)o線傳感器網(wǎng)絡(luò)路由算法[J].西安交通大學(xué)學(xué)報,2010,44(6)：33-38.

[15] 侯彥軍,譚國真.一種WSN分簇路由協(xié)議研究和實現(xiàn)[J].計算機科學(xué),2015,42(5)：160-187.

[16] 王開通，熊慶宇 等.無線傳感器網(wǎng)絡(luò)LEACH路由協(xié)議研究與改進(jìn)[J].計算機工程與應(yīng)用,2015,51(10)：103-107.

[17]CaoQ,HeT,andFangL,etal.Efficiencycentriccommunicationmodelforwirelesssensornetworks[A].Proc.oftheIEEEINFOCOM[C].Barcelona:IEEEComputerSocietyPress,2006: 1-12.

[18]EstrinD.WirelesssensornetworkstutorialpartIV:Sensornetworkprotocols[A].ProcoftheACMMobilComputingandNetworking[C].NewYork:ACM, 2002. 1-5.

[19] 郭書城，盧 昱，許定根. 基于分簇?zé)o線傳感器網(wǎng)絡(luò)的路由算法研究[J].通信學(xué)報,2010,31(8A)：63-69.

[20] 毛鶯池，王久龍 等.基于鏈路質(zhì)量的層次型路由協(xié)議研究[J].計算機科學(xué),2015,42(3)：74-80.

UnevenClusteringRoutingProtocolforWirelessSensorNetworksBasedonImprovedAntColonyAlgorithm

Liao Fubao1，Zhang Wenmei2

(1.Department of Computer, Guangdong AIB Polytechnic College, Guangzhou 510507, China；2.Department of Mechanics and Electronics, Guangdong AIB Polytechnic College, Guangzhou 510507, China)

Aiming at the energy consumption unbalance and “hotspot” energy hole for sensor nodes random distribution in Wireless Sensor Networks(WSNs), an uneven clustering routing protocol for WSNs based on improved ant colony algorithm is proposed. The protocol adopts round operation mode, in the beginning phase of each round cluster-head selection, it forms the uneven competition radius of nodes by the density of the nodes, residual energy and the distance to sink. The rate of residual energy and the average of distance deviation of nodes are calculated by the competition radius, and then the nodes’ wait times of cluster-head selection are calculated. In the cluster-head selection phase, the protocol adopts wait time of cluster-head selection to select the cluster head and balances the energy consumption in the cluster. In the data transmission phase, concerning the residual energy, energy consumption, link quality and transmission delay, the protocol adopts improved ant colony algorithm to construct optimal transmission path. The pheromones are updated at the time of data transmission, and the transmission path are established and maintained more self-adaptive and dynamic. The simulation shows that the routing protocol can efficiently reduce and balance the energy consumption, prolong the wireless sensor network survival period, improve the link quality and reduce transmission delay.

wireless sensor networks; unequal clustering; ant colony algorithm; routing protocol

2016-10-07；

2016-11-22。

科技部國家星火計劃項目(2013GA780003)。

廖福保(1976-)，男，江西寧都人，碩士，副教授，主要從事計算機應(yīng)用、無線傳感器網(wǎng)絡(luò)與路由方向的研究

1671-4598(2017)04-0147-06DOI：10.16526/j.cnki.11-4762/tp

TP

A