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

廖福保，張文梅

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

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

廖福保1，張文梅2

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

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

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

0 引言

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

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

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

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

針對(duì)分簇路由協(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é)議，采用“輪”的概念周期性選擇簇首。每一“輪”每個(gè)節(jié)點(diǎn)都生成一個(gè)0-1之間的隨機(jī)數(shù)，當(dāng)該隨機(jī)數(shù)大于閾值T(n)，則該節(jié)點(diǎn)選為簇首。閾值T(n)采用公式(1)計(jì)算。

(1)

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

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

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

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

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

(2)

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

1.2 存在的問題分析

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

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

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

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

2 相關(guān)模型

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

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

2.2 通信模型

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

(3)

節(jié)點(diǎn)接收k比特?cái)?shù)據(jù)所消耗的能量如下：

ERx(k)=k×Eelec

(4)

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

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

3.1 概念描述

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

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

(5)

(6)

(7)

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

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

2)鄰居節(jié)點(diǎn)。節(jié)點(diǎn)sj為si的鄰居節(jié)點(diǎn)需同時(shí)滿足式(8)和式(9)兩個(gè)條件。

d(sj,si)

(8)

d(sj,si)

(9)

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

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

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

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

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

(10)

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

(11)

(12)

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

(13)

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

3.2 簇首選舉及簇建立

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

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

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

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

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

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

7)Sink節(jié)點(diǎn)發(fā)出同步信號(hào)Tim_MSG，以同步各節(jié)點(diǎn)的時(shí)間。

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

9)對(duì)于節(jié)點(diǎn)si有：

10)if(ti

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

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

13)更新鄰居表

14)endif

15)endif

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

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

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

19)更新鄰居表

20)endif

21)else

22)繼續(xù)監(jiān)聽并計(jì)時(shí)

23)endif

24)endif

25)if(ti==tcomp_i)

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

27)清空鄰居表

28)endif

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

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

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

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

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

3.3 路徑搜索

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

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

算法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ù)路由表計(jì)算其到鄰居簇首sj(sj∈Ci，Ci為si路由表中的簇首集)的初始信息素濃度(見公式14)。

(14)

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

(15)

(16)

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

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

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

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

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

(17)

(18)

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

4 仿真實(shí)驗(yàn)

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

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

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

表3 實(shí)驗(yàn)仿真參數(shù)表

4.2 仿真結(jié)果分析

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

圖2 節(jié)點(diǎn)分布圖

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

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

圖4 剩余總能量對(duì)比

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

圖5 平均時(shí)延對(duì)比

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

圖6 丟包率對(duì)比

5 結(jié)語

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

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

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

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

[3] 董 穎，蘇真真，周占穎，等.一種基于節(jié)點(diǎn)剩余能量和位置的LEACH改進(jìn)算法[J].四川大學(xué)學(xué)報(bào)(工程科學(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é)報(bào)，2003，14(7)：1282-1291.

[7] 劉 群，白全煒，曾憲華，等.能量感知的WSN節(jié)點(diǎn)分類控制路由算法[J].傳感技術(shù)學(xué)報(bào)，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].計(jì)算機(jī)學(xué)報(bào)，2007，30(1)：27-36.

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

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

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

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

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

[16] 王開通，熊慶宇 等.無線傳感器網(wǎng)絡(luò)LEACH路由協(xié)議研究與改進(jìn)[J].計(jì)算機(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é)報(bào),2010,31(8A)：63-69.

[20] 毛鶯池，王久龍 等.基于鏈路質(zhì)量的層次型路由協(xié)議研究[J].計(jì)算機(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。

科技部國家星火計(jì)劃項(xiàng)目(2013GA780003)。

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

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

TP

A