楊海俊, 李魯群

(上海師范大學(xué) 信息與機(jī)電工程學(xué)院,上海 200234)

?

一種基于QoS的LEACH改進(jìn)算法

楊?？? 李魯群

(上海師范大學(xué) 信息與機(jī)電工程學(xué)院,上海 200234)

改進(jìn)了經(jīng)典分簇算法LEACH,提出了QBL(QoS-based LEACH)算法,以節(jié)約能耗為主要目標(biāo),旨在延長網(wǎng)絡(luò)壽命、減小時延、提高網(wǎng)絡(luò)可靠性.首先在簇頭競爭時采用了新的權(quán)重計(jì)算方法,其次采用了不均勻分簇的策略,此外簇內(nèi)只安排部分成員完成監(jiān)測任務(wù),并在簇間通信時采用基于權(quán)重的最短路徑方法.仿真實(shí)驗(yàn)證明:QBL算法在分簇情況、網(wǎng)絡(luò)壽命、時延、可靠性方面均有較為突出的表現(xiàn).

WSN; 拓?fù)淇刂? 分簇; QoS

0 引 言

無線傳感器網(wǎng)絡(luò)(WSN)集計(jì)算、通信、傳感等技術(shù)于一身,具有節(jié)點(diǎn)受限、自組織性、面向應(yīng)用、以數(shù)據(jù)為中心等特點(diǎn),廣泛地應(yīng)用于軍事、交通、醫(yī)療等多個領(lǐng)域.打破傳統(tǒng)網(wǎng)絡(luò)協(xié)議體系嚴(yán)格的分層機(jī)制,WSN研究中出現(xiàn)了層間互聯(lián)的跨層設(shè)計(jì),且WSN的QoS體系也有所不同.

在WSN中,拓?fù)淇刂剖俏挥贛AC層與網(wǎng)絡(luò)層之間的夾層,對MAC協(xié)議和路由協(xié)議、數(shù)據(jù)融合、目標(biāo)定位、同步機(jī)制等都有積極的影響.拓?fù)淇刂扑惴ǔ１环?種:控制節(jié)點(diǎn)功率的平面型,選擇骨干節(jié)點(diǎn)的層次型,及常與層次型結(jié)合使用的啟發(fā)機(jī)制.

本文作者對LEACH算法進(jìn)行了改進(jìn),提出了一種基于QoS的拓?fù)淇刂扑惴?QBL),以減小能量消耗為主要目的,并改善端到端的延遲,提高傳輸可靠性.

第1節(jié)闡述分簇拓?fù)淇刂扑惴ǖ南嚓P(guān)工作,第2節(jié)介紹網(wǎng)絡(luò)模型并提出問題,第3節(jié)描述QBL算法的設(shè)計(jì)和實(shí)現(xiàn),第4節(jié)對兩種算法進(jìn)行仿真對比,第5節(jié)進(jìn)行總結(jié)并指出以后的研究方向.

1 相關(guān)工作

層次型拓?fù)淇刂扑惴ㄓ址Q為分簇拓?fù)淇刂扑惴?把傳感器節(jié)點(diǎn)分為簇頭和成員節(jié)點(diǎn),成員節(jié)點(diǎn)收集的數(shù)據(jù)由簇頭進(jìn)行融合后發(fā)送至基站.簇頭與基站進(jìn)行通信時,成員節(jié)點(diǎn)關(guān)閉通信模塊以節(jié)約能量.該類算法擴(kuò)展性好、可減少碰撞、有利于延長網(wǎng)絡(luò)壽命、適用于大規(guī)模網(wǎng)絡(luò)等優(yōu)點(diǎn),因此出現(xiàn)了很多相關(guān)研究.

LEACH算法[1-2]是最具代表性的分簇算法之一,它引入“輪”的機(jī)制,每一輪分為簇建階段和穩(wěn)定階段.在建簇階段,各節(jié)點(diǎn)在區(qū)間[0,1]內(nèi)生成一個隨機(jī)數(shù),如果該隨機(jī)數(shù)小于公式(1)中的T(n)值,則此節(jié)點(diǎn)宣布成為簇頭.

(1)

其中p表示簇頭的百分比,r表示當(dāng)前輪數(shù),G是最近1/p輪中還未當(dāng)選過簇頭的節(jié)點(diǎn)集合.

HEED[3]在簇頭選舉時考慮了節(jié)點(diǎn)剩余能量,把節(jié)點(diǎn)通信能耗作為主要參考因素,將節(jié)點(diǎn)鄰居信息和節(jié)點(diǎn)密度作為次要參數(shù).DESC[4]根據(jù)簇頭節(jié)點(diǎn)剩余能量更新簇,主要參考了到鄰居節(jié)點(diǎn)距離、鄰居數(shù)目兩方面的因素.DWEHC[5]中簇頭的選舉主要依據(jù)到鄰居節(jié)點(diǎn)的距離和剩余能量,且簇內(nèi)通信采用了分級的多跳方式.MOCA[6]采用分布式的多跳分簇,保證了簇之間一定程度的重合.ARC[7]主要針對網(wǎng)絡(luò)連通性和覆蓋度,也采用“輪”的機(jī)制,在每輪中根據(jù)需要調(diào)節(jié)占空比和節(jié)點(diǎn)發(fā)射功率來更新拓?fù)浣Y(jié)構(gòu).CPCP[8]在選擇簇頭時更注重網(wǎng)絡(luò)覆蓋率,適用于監(jiān)測區(qū)域需要長時間完全覆蓋的應(yīng)用.

另外,還有LEACH-G(LEACH based on “game of life”)[9]、LEACH-T(LEACH based on Three factor)[10]、S-HEED(Stable-based HEED)[11]等算法.

2 網(wǎng)絡(luò)模型和問題描述

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

采用文獻(xiàn)[1-2]提供的能耗模型,若傳感器節(jié)點(diǎn)A與B之間的距離為d,記A發(fā)送kbit的數(shù)據(jù)給B時消耗能量為ETx(k,d),而B接收來自A的kbit數(shù)據(jù)消耗的能量為:

(2)

ERx(k,d)=ERx-elec(k)=k·Eelec.

(3)

其中,Eelec表示電路的能量消耗;εfs和εmp分別表示采用自由空間和多路徑衰減信道模型功率放大器需要的能耗;d0表示傳輸距離的閾值,當(dāng)d

假設(shè)監(jiān)測區(qū)域?yàn)镸×M的二維正方形,并假設(shè)WSN具有如下性質(zhì):1) 全網(wǎng)只有一個基站,位置固定;2) 節(jié)點(diǎn)一旦部署完成將保持靜止不動;3) 節(jié)點(diǎn)可依據(jù)與接收者的距離調(diào)整發(fā)射功率;4) 節(jié)點(diǎn)可根據(jù)接收信號的強(qiáng)度RSSI近似計(jì)算出與發(fā)送者之間的距離;5) 所有傳感器節(jié)點(diǎn)同構(gòu),不能補(bǔ)充能量,不具備定位功能,但能融合數(shù)據(jù),節(jié)點(diǎn)ID唯一;6) 基站具備較強(qiáng)的計(jì)算、存儲、通信能力,電量可持續(xù)使用,且所有節(jié)點(diǎn)都可以接收到基站的發(fā)射信號.

2.2 問題描述

LEACH存在很多優(yōu)點(diǎn):它對節(jié)點(diǎn)的硬件要求較低,節(jié)點(diǎn)不用存儲大量的信息;簇頭隨機(jī)選取,節(jié)點(diǎn)當(dāng)選簇頭的機(jī)會均等,一定程度上實(shí)現(xiàn)了能耗平衡;簇頭選舉不需要依賴全局信息或者上層控制,實(shí)現(xiàn)較為容易.但LEACH算法中也存在一些缺點(diǎn):

1) 選舉簇頭沒有考慮剩余能量.簇頭節(jié)點(diǎn)擔(dān)任工作較多,若能量少的節(jié)點(diǎn)當(dāng)選簇頭,容易耗盡能量而死亡,不利于延長網(wǎng)絡(luò)壽命.

2) 由于簇頭選取隨機(jī),容易導(dǎo)致成簇不均勻,且無規(guī)律可循,不利于網(wǎng)絡(luò)能耗的均衡.

3) 采用簇間多跳的方式與基站通信時,距基站較近的簇頭耗能更快(“熱區(qū)問題”),因?yàn)樗鼈兗纫诤媳敬氐臄?shù)據(jù)又要轉(zhuǎn)發(fā)其他簇的數(shù)據(jù).

3 QBL算法

針對LEACH存在的不足,提出了一種基于服務(wù)質(zhì)量的LEACH算法,記為QBL(QoS-Based LEACH).QBL算法以減小能量消耗為主要目的,旨在有效延長了網(wǎng)絡(luò)壽命,并致力于改善端到端的延遲、傳輸可靠性等指標(biāo).QBL依然使用了“輪”的概念,每一輪依然分為簇的形成階段Te和穩(wěn)定階段Ts.

(1)QBL算法選舉簇頭時依據(jù)的條件依次是:剩余能量較多,與鄰居通訊能耗較少,距離基站較近.

(2)針對“熱區(qū)問題”,QBL使距基站較近的簇頭成員數(shù)目較少,以節(jié)約能量供轉(zhuǎn)發(fā)數(shù)據(jù)使用,而距離基站較遠(yuǎn)的簇頭成員數(shù)目則較多.

(3)為了進(jìn)一步節(jié)約能量,QBL在每個簇內(nèi)只選擇部分成員完成檢測任務(wù),其余節(jié)點(diǎn)休眠.并在簇間通信階段采用基于權(quán)重的最短路徑算法,再次考慮了剩余能量和通信能耗兩個因素.

QBL算法中相關(guān)消息類型定義如下:Gather_Msg:初始化時基站廣播收集信息;Start_Msg:基站宣布開始競選簇頭;Reply_Msg:節(jié)點(diǎn)回復(fù)消息;Neighbor_Msg:節(jié)點(diǎn)收集鄰居信息;Head_Msg:節(jié)點(diǎn)宣布自己是簇頭;Join_Msg:節(jié)點(diǎn)請求加入某簇;Routing_Msg:建立簇間通信路徑時簇頭廣播Level值.

3.1 網(wǎng)絡(luò)初始化

在初始化階段,基站和節(jié)點(diǎn)相互通信獲得必要信息,為后續(xù)分簇提供基礎(chǔ).

1) 基站向所有節(jié)點(diǎn)廣播Gather_Msg,節(jié)點(diǎn)Vi據(jù)此計(jì)算到基站的距離dtoBS(i),存儲該值并回復(fù)Reply_Msg給基站.

(4)

式中N表示檢測區(qū)域的節(jié)點(diǎn)總數(shù),dtoBS(i)表示節(jié)點(diǎn)Vi到基站的距離.

LEACH算法最優(yōu)簇頭數(shù)目kopt的計(jì)算如公式(5)所示.

(5)

(6)

其中p表示簇頭節(jié)點(diǎn)所占百分比,帶入kopt,可進(jìn)一步演變?yōu)?

(7)

3) 基站節(jié)點(diǎn)廣播Start_Msg,將dtoBS和Dopt的值廣播給所有節(jié)點(diǎn),這樣所有節(jié)點(diǎn)知道的信息包括:dtoBS、Dopt和dtoBS(i).

3.2 簇的生成

在建簇階段,節(jié)點(diǎn)通過廣播獲得鄰居節(jié)點(diǎn)信息,根據(jù)權(quán)重建成簇.

1) 節(jié)點(diǎn)計(jì)算dopt(i),并相互通信獲得鄰居信息.首先,計(jì)算最佳發(fā)射半徑dopt(i),

(8)

其中

(9)

dopt(i)的計(jì)算以dtoBS為依據(jù),當(dāng)dtoBS(i)

然后,所有節(jié)點(diǎn)Vi以dopt(i)為發(fā)射半徑廣播Neighbor_Msg,廣播內(nèi)容包括ID、剩余能量Er(i).收到該廣播的節(jié)點(diǎn)Vj回復(fù)Reply_Msg,并存儲Vi到自己的距離ditoj,顯然有ditoj=djtoi.接著節(jié)點(diǎn)Vi計(jì)算鄰居節(jié)點(diǎn)剩余能量的平均值Eavg,

(10)

其中Nb(i)表示Vi的鄰居數(shù)目.

圖1 鄰居節(jié)點(diǎn)關(guān)系圖

對鄰居的定義如圖1所示,當(dāng)節(jié)點(diǎn)Vj在節(jié)點(diǎn)Vi最佳發(fā)射半徑dopt(i)范圍內(nèi),而節(jié)點(diǎn)Vi不在節(jié)點(diǎn)Vj最佳發(fā)射半徑dopt(j)范圍內(nèi)時,稱Vj為Vi的鄰居,也即Vi到Vj存在有向邊.當(dāng)節(jié)點(diǎn)Vj和Vk都在對方的最佳發(fā)射半徑之內(nèi)時,稱Vj和Vk互為鄰居.

2) 節(jié)點(diǎn)計(jì)算權(quán)重.節(jié)點(diǎn)求權(quán)重

(11)

權(quán)重wi包含we(i)、wnei(i)和wd(i) 3項(xiàng)因子,α、β和γ為3項(xiàng)因子的比重參數(shù),α+β+γ=1.

記

圖2 數(shù)據(jù)提交路徑

we(i)考慮了節(jié)點(diǎn)剩余能量Er(i),剩余能量多的節(jié)點(diǎn)適合成為簇頭.wnei(i)考慮了節(jié)點(diǎn)與鄰居的位置關(guān)系,節(jié)點(diǎn)Vi越靠近區(qū)域中心位置,簇內(nèi)通信能耗越少.wd(i)考慮了節(jié)點(diǎn)到基站的距離dtoBS(i),在如圖2所示的區(qū)域中,顯然D比C更適合當(dāng)選簇頭.當(dāng)C做簇頭時(圖2中實(shí)線標(biāo)注),A和B與基站通信,需要先將數(shù)據(jù)發(fā)送給C,然后再由C轉(zhuǎn)發(fā)給基站或上層簇頭,多走了很多“彎路”.

3) 依據(jù)權(quán)重競選簇頭.簇頭競選開始后,所有節(jié)點(diǎn)Vi等待時間T(i)之后,以dopt(i)為發(fā)射半徑廣播Head_Msg,宣布自己為簇頭.

(12)

與節(jié)點(diǎn)權(quán)重wi成反比,故權(quán)重較大的節(jié)點(diǎn)等待的時間較短.如果Vi在T(i)之前已經(jīng)收到Head_Msg消息則放棄競選并等待.T(i)之后,若沒有Vi收到廣播,說明自己權(quán)重較大,則發(fā)送廣播Head_Msg.因?yàn)楣?jié)點(diǎn)要在Te時間內(nèi)競選出簇頭并完成簇頭對簇成員的工作分配,所以T(i)的值不能大于1/2·Te.

4) 簇頭與簇成員相互選擇形成簇.競選失敗的節(jié)點(diǎn)Vi一直等待,直到時刻1/2·Te+ΔT之后,根據(jù)收到的Head_Msg選擇合適的簇頭發(fā)送Join_Msg,若節(jié)點(diǎn)同時收到2個或2個以上簇頭的消息,優(yōu)先選擇發(fā)射信號強(qiáng)度較強(qiáng)的簇頭申請加入.簇頭競選成功后,對申請加入的節(jié)點(diǎn)進(jìn)行安排.

3.3 簇內(nèi)節(jié)點(diǎn)管理

覆蓋率和最少活動節(jié)點(diǎn)數(shù)

(13)

其中ψ表示要求的覆蓋率,rs表示節(jié)點(diǎn)的監(jiān)測半徑,該結(jié)果也可應(yīng)用于對簇內(nèi)成員節(jié)點(diǎn)的管理[13-14].

在QBL算法中,簇頭收到Join_Msg消息后,首先計(jì)算k的值,顯然面積S就是以簇頭最佳發(fā)射半徑覆蓋的圓區(qū)域.然后,隨機(jī)選擇k-1個節(jié)點(diǎn)作為活動節(jié)點(diǎn)(簇頭自身為活動節(jié)點(diǎn)).最后,簇頭為每個活動節(jié)點(diǎn)建立TDMA方案,在回復(fù)允許成員加入時,告知活動節(jié)點(diǎn)被分配的時隙,告知其余節(jié)點(diǎn)在本輪中休眠.

3.4 簇間通信

簇頭競選成功后,建立到基站的多跳路徑,該過程與簇頭對成員節(jié)點(diǎn)的管理并發(fā)進(jìn)行.在規(guī)模較大的網(wǎng)絡(luò)中,簇頭與基站通信采用多跳的方式更有利于節(jié)約能量[12].采用最短路徑方法尋找簇頭到基站的最優(yōu)路徑,QBL為每個簇頭定義路由權(quán)值Level,

(14)

QBL算法中簇頭到基站的路由算法描述如下:

首先,簇頭Vi等待時間t(i)后以2·dopt(i)為發(fā)射半徑廣播Routing_Msg,廣播內(nèi)容包括ID、Level值,

t(i)=t·Level(i).

(15)

其中t隨著進(jìn)行輪數(shù)的增加逐漸減小,因?yàn)殡S著輪數(shù)的增加,節(jié)點(diǎn)剩余能量逐漸變小,而到基站的距離卻不變,t值逐漸變小不會造成網(wǎng)絡(luò)時延的增加.

簇頭Vi收到簇頭Vj廣播Routing_Msg后,比較Level(i)與Li to j+Level(j)的大小,如果Level(i)>Li to j+Level(j)則將Level(i)的值更新為Li to j+Level(j),且記為父節(jié)點(diǎn),記錄其ID;否則Level值保持不變.

(16)

Level較小的簇頭節(jié)點(diǎn)先進(jìn)行廣播,其他簇頭收到Routing_Msg后自動更新自身的Level值,當(dāng)所有簇頭廣播完后,每個簇頭可得知父節(jié)點(diǎn)的ID.簇頭Vi與基站通信時,先將數(shù)據(jù)提交給其父節(jié)點(diǎn)Vj,再由Vj提交給它的下一跳Vk,如此直至基站.

QBL算法流程如圖3所示.

圖3 QBL算法流程圖

4 算法仿真和性能分析

利用OMNET++工具對QBL和LEACH算法進(jìn)行仿真,來對比兩種算法在簇的分布、網(wǎng)絡(luò)壽命、節(jié)點(diǎn)耗能、時延、網(wǎng)絡(luò)可靠性方面的表現(xiàn).為了能夠顯示QBL算法不均勻分簇的效果,將基站設(shè)在監(jiān)測區(qū)域一角.仿真區(qū)域?yàn)?00 m×100 m,參數(shù)α、β、γ分別設(shè)為0.5、0.3和0.2;ψ的值設(shè)為1,節(jié)點(diǎn)初始能量Einit設(shè)為[0.45 J,0.5 J]之間的隨機(jī)數(shù),Eelec的值設(shè)為50 nJ/bit,εfs和εmp的值分別設(shè)為10 pJ/(bit·m2)和0.0013 pJ/(bit·m4),融合數(shù)據(jù)耗能設(shè)為5 nJ,數(shù)據(jù)包長度設(shè)為525 Bytes.

4.1 分簇仿真分析

當(dāng)對100個節(jié)點(diǎn)進(jìn)行仿真時(圖4),在LEACH算法(圖4a)中,簇頭分布隨機(jī),成簇規(guī)模沒有規(guī)律;而在QBL算法(圖4b)中,距離基站近的簇區(qū)較小,距離基站遠(yuǎn)的簇區(qū)較大.當(dāng)節(jié)點(diǎn)增加至200個時(圖5),LEACH(圖5a)和QBL(圖5b)分簇情況區(qū)別更大.通過100個節(jié)點(diǎn)和200個節(jié)點(diǎn)的對比發(fā)現(xiàn),在節(jié)點(diǎn)數(shù)目較多時,QBL分簇層次性更明顯.

之所以能實(shí)現(xiàn)這種不均勻分簇,是因?yàn)镼BL算法在簇頭選舉時給節(jié)點(diǎn)設(shè)置了不同的發(fā)射半徑,從而得到不均勻分簇的結(jié)果.在節(jié)點(diǎn)數(shù)目更多規(guī)模更大的網(wǎng)絡(luò)中,節(jié)點(diǎn)到基站的距離差異更大,不均勻成簇的層次性就會更加明顯.

圖4 100個節(jié)點(diǎn)時算法分簇情況

圖5 200個節(jié)點(diǎn)時算法分簇情況

4.2 網(wǎng)絡(luò)生存時間分析

從圖6中可以發(fā)現(xiàn),當(dāng)節(jié)點(diǎn)數(shù)目為100時,對于第一個節(jié)點(diǎn)死亡的時間,LEACH大約在110 s,而QBL大約在120 s,比LEACH推遲了將近10 s.而對于節(jié)點(diǎn)幾乎全部死亡的時間,LEACH是在150 s附近,QBL是在170 s之前,推遲了將近20 s,說明QBL算法有利于延長網(wǎng)絡(luò)壽命.這是因?yàn)镼BL充分考慮了節(jié)點(diǎn)能耗均衡性,在競選簇頭時考慮了節(jié)點(diǎn)剩余能量;且QBL采用不均勻分簇避免“熱區(qū)問題”,更好地實(shí)現(xiàn)了能耗平衡.

圖6 節(jié)點(diǎn)存活數(shù)量

4.3 網(wǎng)絡(luò)能量消耗分析

如圖7所示,隨著節(jié)點(diǎn)數(shù)目的增加,兩種算法平均每輪的能耗都在不斷增加.在節(jié)點(diǎn)較少時,QBL的能耗比LEACH稍大,但總體上QBL較LEACH而言能耗更小,且隨著網(wǎng)絡(luò)規(guī)模的增大,QBL的優(yōu)勢更明顯,說明QBL算法在規(guī)模較大的WSN中更具有優(yōu)勢.這是因?yàn)镼BL在競選簇頭時,考慮了簇內(nèi)通信能量消耗,并且在簇間通信時也將能耗考慮其中.但QBL算法在建簇階段需要節(jié)點(diǎn)間相互通信收集鄰居信息,需要額外消耗能量,故在規(guī)模較小的網(wǎng)絡(luò)中優(yōu)勢不明顯.

圖7 能量消耗

當(dāng)ψ值減小時,網(wǎng)絡(luò)能耗隨之減小,如圖8所示.這是因?yàn)镼BL采用了休眠機(jī)制,簇頭只選擇部分節(jié)點(diǎn)為活動節(jié)點(diǎn),其余節(jié)點(diǎn)在本輪中休眠,ψ值越小休眠的節(jié)點(diǎn)越多,也就越節(jié)約能量.隨著節(jié)點(diǎn)密度的增大,休眠的節(jié)點(diǎn)就會變多,節(jié)能效果就越明顯.

4.4 網(wǎng)絡(luò)時延分析

由圖9可知,兩種算法端到端的時延隨著時間都逐漸減小,最后都趨于平穩(wěn),但QBL端到端的時延較小.因?yàn)镼BL算法在競選簇頭時優(yōu)先選擇靠近簇區(qū)中心的節(jié)點(diǎn),減小了簇內(nèi)通信的時延;簇間通信時采用基于權(quán)重的最短路徑算法,也有利于減小端到端的時延.

4.5 網(wǎng)絡(luò)可靠性分析

本實(shí)驗(yàn)用丟包率衡量網(wǎng)絡(luò)的可靠性,如圖10所示.雖然在兩種算法都采用TDMA和CMDA機(jī)制,在一定程度上避免了數(shù)據(jù)碰撞,但通信量、信號強(qiáng)度、時延、成簇大小等因素對丟包率都存在影響,丟包率沒有一定的規(guī)律.但總的來說,QBL算法比LEACH算法丟包率更小.因?yàn)樵赒BL中簇間通訊路徑得到了優(yōu)化,簇內(nèi)節(jié)點(diǎn)管理合理,減少了網(wǎng)絡(luò)中路徑不通的概率.其次QBL算法中網(wǎng)絡(luò)壽命較長(見4.2),且時延較小(見4.4),這些因素使得它具有較小的丟包率.

圖9 端到端的時延

圖10 數(shù)據(jù)發(fā)送成功率

5 總結(jié)和展望

拓?fù)淇刂剖荳SN中的重要技術(shù),如何有效利用資源提供良好的服務(wù)質(zhì)量是該方向研究的重點(diǎn).QBL算法主要完成的工作有:

1) 采用基于權(quán)重的簇頭競爭機(jī)制,綜合了剩余能量、與鄰居的通信能耗、到基站的距離3個因素.

2) 采用不均勻分簇的策略,使距離基站遠(yuǎn)的簇區(qū)較大而距離基站近的簇區(qū)較小,更好地均衡節(jié)點(diǎn)能耗.

3) 簇頭只選擇部分成員完成檢測任務(wù),更加節(jié)能.并且簇間通信采用最短路徑算法,再次考慮了通信能耗和剩余能量2個因素.

4) 在簇頭分布、網(wǎng)絡(luò)壽命、時延、可靠性等方面對QBL算法與LEACH算法進(jìn)行仿真,證明QBL具有較好的性能.

在今后的研究工作中,需要合理地控制算法開銷,提高算法普適性.WSN技術(shù)的發(fā)展,節(jié)點(diǎn)的定位功能、精確度等日益提高,也將提供有力的硬件支持,能更好地滿足不同應(yīng)用QoS的要求.

[1] Heinzelman W B,Chandrakasan A P,Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks [J].Wireless Communications IEEE Transactions on,2002,1(4):660-670.

[2] Heinzelman W R,Chandrakasan A,Balakrishnan H.Energy-efficient communication protocol forwireless microsensor networks [C]//IEEE.System Sciences Proceedings of Annual Hawaii International Conference on.Hawaii:IEEE,2000.

[3] Younis O,Fahmy S.HEED:A Hybrid,Energy-Efficient,Distributed Clustering Approach for Ad Hoc Sensor Networks [J].Mobile Computing IEEE Transactions on,2004,3(4):366-379.

[4] Neamatollahi P,Taheri H,Naghibzadeh M,et al.DESC:distributed energy efficient scheme to cluster wireless sensor networks [J].Wired/Wireless Internet Communications,2011,6649:234-246.

[5] Ping Ding J H A A C.Distributed Energy-Efficient Hierarchical Clustering for Wireless Sensor Networks [J].Distributed Computing in Sensor Systems,2005,3560:322-339.

[6] Youssef A,Younis M,Youssef M,et al.WSN16-5:Distributed Formation of Overlapping Multi-hop Clusters in Wireless Sensor Networks [C]//IEEE.Global Telecommunications Conference 2006,San Francisco:IEEE,2006:1-6.

[7] Xu N,Huang A,Hou T,et al.Coverage and connectivity guaranteed topology control algorithm for cluster-based wireless sensor networks [J].Wireless Communications & Mobile Computing,2012,12(1):23-32.

[8] Soro S,Heinzelman W B.Cluster head election techniques for coverage preservation in wireless sensor networks [J].Ad Hoc Networks,2009,7(5):955-972.

[9] Yang Y J,Jia B,Wang J.An Improved Algorithm for LEACH Protocol in Wireless Sensor Network [J].Journal of Beijing University of Posts & Telecommunications,2013,36(1):105-109.

[10] Li Y,Sun L J,Wang R C,et al.Improvement of LEACH Algorithm in Wireless Sensor Network [J].Journal of Computer Research and Development,2011,48(Suppl):131-134.

[11] Yang M N,Yang D,Huang C.An improved HEED clustering algorithm for Wireless Sensor [J].Journal of Chongqing University,2012,35(8):101-106.

[12] Rosenberg V M A C.Design guidelines for wireless sensor networks:communication,clustering and aggregation [J].Ad Hoc Networks,2004,2(1):45-63.

[13] Choi W,Das S K.Trade-off between coverage and data reporting latency for energy-conserving data gathering in wireless sensor networks [C]//IEEE.Mobile Ad-hoc and Sensor Systems,2004 IEEE International Conference on,Fort Lauderdale:IEEE,2004.

[14] Liu M,Cao J N,Chen G H,et al.EADEEG:An Energy-Aware Data Gathering Protocol for Wireless Sensor Networks [J].Journal of Software,2007,18(5):1092-1109.

[15] 孫彥景.無線傳感器網(wǎng)絡(luò)分簇與虛擬骨干技術(shù) [M].徐州:中國礦業(yè)大學(xué)出版社,2010.

(責(zé)任編輯：包震宇)

An improved algorithm of LEACH based on QoS

YANG Haijun, LI Luqun

(College of Information,Mechanical and Electrical Engineering,Shanghai Normal University,Shanghai 200234,China)

Based upon clustering LEACH algorithm,a QBL(QoS-based LEACH)algorithm is proposed in this article aiming at improvement in energy saving,network delay,life time and reliability.The QBL algorithm,armed with new algorithm of weighting in selecting cluster head as well as uneven clustering strategy,has only part of members within the cluster to be assigned to fulfill monitoring tasks,and adopts shortest path of weighting methods in inter-cluster communication.Simulation results show that the QBL algorithm has turned out remarkable performance in improving network delay,lifetime and reliability in simulation experiments.

WSN; topology control; clustering; QoS

2015-04-22

李魯群,中國上海市徐匯區(qū)桂林路100號,上海師范大學(xué)信息與機(jī)電工程學(xué)院,郵編:200234,E-mail:liluqun@gmail.com

TP 393

A

1000-5137(2016)05-0527-09

10.3969/J.ISSN.1000-5137.2016.05.003