無線網(wǎng)絡(luò)中DEEC協(xié)議的改進(jìn)

黃曉峰，劉廣鐘

(上海海事大學(xué) 信息工程學(xué)院，上海201306)

當(dāng)今社會，無線傳感器網(wǎng)絡(luò)已經(jīng)出現(xiàn)在社會的各種角落，智慧城市的提出更是為無線傳感器網(wǎng)絡(luò)提供了更大的發(fā)展空間。無線傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Network)是由大量的傳感器節(jié)點(diǎn)組成的一種網(wǎng)絡(luò)，無需固定基礎(chǔ)設(shè)施的支持，具有快速展開、抗毀性強(qiáng)、自組織、動態(tài)拓?fù)浜湍芰渴芟薜忍攸c(diǎn)[1]。由于節(jié)點(diǎn)能量有限并且對其充電非常困難，因此設(shè)計路由算法時應(yīng)該著重于延長網(wǎng)絡(luò)的生存周期、提高網(wǎng)絡(luò)的有效性，避免網(wǎng)絡(luò)斷裂，保證負(fù)載均衡。目前對于無線網(wǎng)絡(luò)路由算法的研究發(fā)現(xiàn)，基于分簇的層次路由有很強(qiáng)的擴(kuò)展性，多跳傳輸?shù)穆酚煞绞娇梢跃夤?jié)點(diǎn)的能量的負(fù)載[2-3]。

針對這些協(xié)議的不足，本文提出了一種負(fù)載均衡的無線傳感器網(wǎng)絡(luò)路由改進(jìn)算法IDEEC。通過在簇頭選擇階段，綜合考慮節(jié)點(diǎn)的剩余能量以及節(jié)點(diǎn)周圍的密度，保證簇的均勻分布。

1 相關(guān)研究

1.1 Leach算法的分析

Leach算法的基本思想是減少節(jié)點(diǎn)與基站的直接通信，并通過數(shù)據(jù)融合降低通信能量的損耗。Leach算法是周期性執(zhí)行的，分為分簇階段和穩(wěn)定階段。在分簇階段，節(jié)點(diǎn)會產(chǎn)生一個 0與 1之間的隨機(jī)數(shù)，并與 T(n)進(jìn)行比較，如果該隨機(jī)數(shù)小于T(n)，則廣播為簇頭。非簇頭節(jié)點(diǎn)收到廣播后，選擇最近的節(jié)點(diǎn)加入，當(dāng)簇頭節(jié)點(diǎn)收到加入數(shù)據(jù)包后，再將該表廣播發(fā)給簇內(nèi)成員節(jié)點(diǎn)。沒有加入任何簇的節(jié)點(diǎn)直接與基站通信。在穩(wěn)定階段，簇內(nèi)成員節(jié)點(diǎn)將采集的數(shù)據(jù)傳送給簇頭節(jié)點(diǎn)，簇頭節(jié)點(diǎn)進(jìn)行數(shù)據(jù)融合后發(fā)送給基站。當(dāng)穩(wěn)定階段完成了第一輪的數(shù)據(jù)傳輸后，重新進(jìn)入到分簇階段。Leach算法延長了整個網(wǎng)絡(luò)的生存周期。

1.2 DEEC算法分析

DEEC算法[4]是針對Leach算法的改進(jìn)，考慮了節(jié)點(diǎn)的初始和剩余能量，增加了網(wǎng)絡(luò)的生存周期。考慮到網(wǎng)絡(luò)的異構(gòu)性，數(shù)據(jù)傳輸節(jié)點(diǎn)的能量不可能都相同，因此每個節(jié)點(diǎn)成為簇頭的概率就不同。節(jié)點(diǎn)成為簇頭的概率pi與改進(jìn)的閾值 T（n）的關(guān)系如下：

其中，si為節(jié)點(diǎn)，i∈[1，n]。

[5]對DEEC分簇算法進(jìn)行改進(jìn)。由于在數(shù)據(jù)傳輸階段，簇頭節(jié)點(diǎn)間沒有考慮傳輸跳數(shù)，因此可能會造成大的傳輸延遲。但是跳數(shù)縮小時，多跳傳輸中選擇下一簇頭時沒有考慮到剩余能量，同時一旦能量的消耗過大，節(jié)點(diǎn)就不足以繼續(xù)多跳傳輸。

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

本路由算法中的無線傳感器網(wǎng)絡(luò)為n個節(jié)點(diǎn)隨機(jī)分布在M×M區(qū)域內(nèi)。節(jié)點(diǎn)集合表示為S={s1，…，sn}，同時網(wǎng)絡(luò)有以下特點(diǎn)：

(1)本網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)為靜態(tài)的，節(jié)點(diǎn)和基站節(jié)點(diǎn)的位置都不會隨時間改變。

(2)傳感器節(jié)點(diǎn)的初始能量相同，每個節(jié)點(diǎn)具有唯一的ID號。

(3)傳感器節(jié)點(diǎn)可以自己調(diào)節(jié)無線的發(fā)送功率。

1.4 IDEEC算法中的相關(guān)參數(shù)

在無線傳感器網(wǎng)絡(luò)中，主要根據(jù)網(wǎng)絡(luò)的生存時間和負(fù)載平衡程度來判定分簇路由算法的好壞。在分簇路由算法中，每輪中簇的覆蓋節(jié)點(diǎn)的平均程度會影響網(wǎng)絡(luò)的生存周期。

1.5 能量消耗模型

本文中統(tǒng)一采用與Leach算法相同的無線通信能量消耗模型，能量消耗公式是一階無線電模型[6]。節(jié)點(diǎn)發(fā)送l bit數(shù)據(jù)所消耗的能量由發(fā)射損耗和功率放大損耗兩部分組成：

2 改進(jìn)的路由協(xié)議

綜合以上協(xié)議的不足，提出了一種高效的分簇路由算法，通過引入能量閾值和簇頭的通信范圍，防止簇內(nèi)成員被選成簇頭節(jié)點(diǎn)。

本路由算法采用與Leach算法相同的機(jī)制，每個周期依然分為分簇階段和穩(wěn)定階段。在分簇階段，普通成員節(jié)點(diǎn)首先計算出成為簇頭的概率pi，然后隨機(jī)產(chǎn)生[0，1]之間的隨機(jī)數(shù)，并與門限閾值T(si)進(jìn)行比較，如果大于門限閾值則成為候選簇頭。計算節(jié)點(diǎn)的剩余能量并與能量閾值Ethr比較，其中能量閾值為：

式中Einitial為節(jié)點(diǎn)的初始能量。當(dāng)候選簇頭的剩余能量大于Ethr，才能成為簇頭。通過引入能量閾值，可以防止較低能量的節(jié)點(diǎn)成為簇頭，造成網(wǎng)絡(luò)中數(shù)據(jù)的丟失和重新選舉簇頭的開銷。為了使簇分布更加均勻，引入了覆蓋半徑Rc。Rc代表了整個網(wǎng)絡(luò)每個簇的覆蓋距離，計算公式為：

成為簇頭的節(jié)點(diǎn)廣播消息，當(dāng)節(jié)點(diǎn)收到該消息后計算與該簇頭的距離，如果小于通信半徑r，則改變節(jié)點(diǎn)的類型為簇的候選成員節(jié)點(diǎn)，以防止簇內(nèi)的節(jié)點(diǎn)進(jìn)行簇頭選舉，保證簇能夠盡量覆蓋所有的網(wǎng)絡(luò)。當(dāng)簇頭選擇完成后，進(jìn)行簇的形成，簇頭節(jié)點(diǎn)廣播數(shù)據(jù)包，該數(shù)據(jù)包包括簇頭的ID和簇頭的能量，非簇頭節(jié)點(diǎn)收到數(shù)據(jù)包后選擇就近的簇頭加入，沒有加入到簇的節(jié)點(diǎn)則直接與基站通信。

完成分簇后，進(jìn)入到數(shù)據(jù)信息傳輸階段，本算法中將采用兩種方法來進(jìn)行傳遞。當(dāng)簇頭節(jié)點(diǎn)的平均能量較大時，采用最小路由數(shù)傳遞數(shù)據(jù)，保證節(jié)點(diǎn)在最小時延下到達(dá)sink節(jié)點(diǎn)。但同時能量消耗的也較快，會導(dǎo)致網(wǎng)絡(luò)的生存周期較短，所以當(dāng)節(jié)點(diǎn)能量達(dá)到門限值后，將采用最短距離來進(jìn)行簇頭間的下一跳路由的選擇，這樣將能延長整個網(wǎng)絡(luò)的生存周期。

在最小路由[7]傳遞數(shù)據(jù)時，定義一個距離 β，其值與d0相同，簇頭節(jié)點(diǎn)按照同樣的功率傳遞廣播數(shù)據(jù)包，數(shù)據(jù)包中包含節(jié)點(diǎn)的ID號、剩余能量以及離基站的距離。其他簇頭節(jié)點(diǎn)收到數(shù)據(jù)包后，比較與自己之間的距離，當(dāng)節(jié)點(diǎn)離基站距離小于β時，則選作下一跳，這樣保證了節(jié)點(diǎn)能夠直接地傳輸數(shù)據(jù)到基站，減小了傳送時延，但這種方式也加快了節(jié)點(diǎn)能量的消耗，為了使負(fù)載平衡，引入能量門限值 E1，當(dāng)節(jié)點(diǎn)能量低于E1時，進(jìn)行最短路徑傳輸，節(jié)點(diǎn)通過選擇離自己最近的簇頭進(jìn)行數(shù)據(jù)傳輸。這樣既保證了傳輸時延短，同時也能使網(wǎng)絡(luò)的生存周期加長。其中E1為簇頭的平均能量大小。

3 仿真結(jié)果

對本文提出的協(xié)議進(jìn)行性能測試，同時選擇了Leach算法和DEEC算法進(jìn)行仿真結(jié)果的比較。假定無線傳感器網(wǎng)絡(luò)是隨機(jī)布置在一個二維的平面區(qū)域，節(jié)點(diǎn)的位置部署是隨機(jī)選擇的，基站位于節(jié)點(diǎn)正上方。三種算法的效率如圖1所示。

圖1中，整個網(wǎng)絡(luò)的生存周期明顯增長，第一個死亡節(jié)點(diǎn)出現(xiàn)的時間較晚。把第一死亡節(jié)點(diǎn)出現(xiàn)的時間作為網(wǎng)絡(luò)性能的檢驗(yàn)條件，生存周期的性能相對于Leach和DEEC協(xié)議分別提高了大約50%和30%，這是因?yàn)長each和DEEC算法中由于隨機(jī)選擇簇頭節(jié)點(diǎn)，節(jié)點(diǎn)的分布不均勻，造成第一個死亡節(jié)點(diǎn)先出現(xiàn)，其中雖然DEEC考慮到了剩余能量的選擇，但是對于簇的分布沒有進(jìn)行考慮。

比較圖1中的數(shù)據(jù)傳輸效率，可以看出IDEEC算法的數(shù)據(jù)傳輸效率大大高于另外兩種算法。

如果從整個網(wǎng)絡(luò)的死亡節(jié)點(diǎn)出現(xiàn)的時間分析，則生存周期的性能相對于Leach和DEEC路由算法分別提高了大約30%和25%，由此可見整個網(wǎng)絡(luò)的生存周期得到了很大的提升。同時從圖1(b)中的傳輸效率可以看出改進(jìn)的路由算法的數(shù)據(jù)傳輸量很大，很大程度上提高了網(wǎng)絡(luò)的傳輸效率。

圖2顯示了路由算法每輪形成的簇的數(shù)目，在前1 500輪時，形成的簇的數(shù)目較大，這是因?yàn)樵? 500輪已經(jīng)產(chǎn)生了第一死亡節(jié)點(diǎn)，網(wǎng)絡(luò)的簇的數(shù)目受到了影響，從圖中的趨勢可以看出，改進(jìn)的DEEC協(xié)議產(chǎn)生的簇的數(shù)目較以前穩(wěn)定，這是由于引入均勻分簇的原因，所以整個簇的數(shù)目較穩(wěn)定，不會受到巨大的波動。

在無線傳感器網(wǎng)絡(luò)的分簇協(xié)議中，簇的形成以及數(shù)據(jù)傳輸?shù)倪x擇方式直接影響著無線傳感器網(wǎng)絡(luò)的性能。正是基于以上問題，本文中的路由算法對現(xiàn)有的算法進(jìn)行了改進(jìn)，引入均勻分簇和傳輸負(fù)載均衡。根據(jù)仿真結(jié)果，本算法綜合考慮了網(wǎng)絡(luò)分布均勻及節(jié)點(diǎn)傳輸階段傳輸時延的問題，提高了網(wǎng)絡(luò)路由算法的生存周期。

參考文獻(xiàn)

[1]孫利民.無線傳感器網(wǎng)絡(luò)[M].北京：清華大學(xué)出版社，2005.

[2]AKKAYA K，YOUNIS M.A survey on routing protocols for wireless sensor networks[J].AdHoc Networks，2005，3(5)：325-349.

[3]鄭少仁，王海濤，趙志峰，等.Ad Hoc網(wǎng)絡(luò)技術(shù)[M].北京：人民郵電出版社，2005.

[4]QING L，ZHU Q X，WANG M W.Design of a distributed energy-efficient clustering algorithm for heterogeneous wireless sensor networks[J].Computer Communications，2006，17(3)：481-489.

[5]Liu Feng，Zhang Dengyi.Clustering routing protocol based on local optimization for wireless sensor networks consumer electronics[C].Dalian：2012 2nd International Conference，2012.

[6]劉玉華，趙永鋒，許凱華，等.無線傳感器網(wǎng)絡(luò) LEACH協(xié)議的改進(jìn)[J].計算機(jī)工程與應(yīng)用，2010，46(17)：117-120.

[7]楊云，李斌，高峰，等.無線傳感器網(wǎng)絡(luò)簇內(nèi)優(yōu)化的最小跳數(shù)路由算法[J].計算機(jī)應(yīng)用與軟件，2010，27(2)：31-33，46.