摘  要： 提出無(wú)線(xiàn)傳感器網(wǎng)絡(luò)路由算法IDEEC（Improvement Distribute Energy-Efficient Clustering Algorithm for Heterogeneous Wireless Sensor Networks），該算法具有能量消耗低的優(yōu)點(diǎn)，基于傳輸時(shí)延的考慮，采用多跳方式傳送數(shù)據(jù)。通過(guò)與Leach和DEEC的路由的協(xié)議的仿真結(jié)果比較，本路由算法的網(wǎng)絡(luò)生存周期分別提高了50%和30%。
關(guān)鍵詞： IDEEC；能量閾值；傳輸效率

    當(dāng)今社會(huì)，無(wú)線(xiàn)傳感器網(wǎng)絡(luò)已經(jīng)出現(xiàn)在社會(huì)的各種角落，智慧城市的提出更是為無(wú)線(xiàn)傳感器網(wǎng)絡(luò)提供了更大的發(fā)展空間。無(wú)線(xiàn)傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Network)是由大量的傳感器節(jié)點(diǎn)組成的一種網(wǎng)絡(luò)，無(wú)需固定基礎(chǔ)設(shè)施的支持，具有快速展開(kāi)、抗毀性強(qiáng)、自組織、動(dòng)態(tài)拓?fù)浜湍芰渴芟薜忍攸c(diǎn)[1]。由于節(jié)點(diǎn)能量有限并且對(duì)其充電非常困難，因此設(shè)計(jì)路由算法時(shí)應(yīng)該著重于延長(zhǎng)網(wǎng)絡(luò)的生存周期、提高網(wǎng)絡(luò)的有效性，避免網(wǎng)絡(luò)斷裂，保證負(fù)載均衡。目前對(duì)于無(wú)線(xiàn)網(wǎng)絡(luò)路由算法的研究發(fā)現(xiàn)，基于分簇的層次路由有很強(qiáng)的擴(kuò)展性，多跳傳輸?shù)穆酚煞绞娇梢跃夤?jié)點(diǎn)的能量的負(fù)載[2-3]。
    針對(duì)這些協(xié)議的不足，本文提出了一種負(fù)載均衡的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)路由改進(jìn)算法IDEEC。通過(guò)在簇頭選擇階段，綜合考慮節(jié)點(diǎn)的剩余能量以及節(jié)點(diǎn)周?chē)拿芏?，保證簇的均勻分布。
1 相關(guān)研究
1.1 Leach算法的分析
    Leach算法的基本思想是減少節(jié)點(diǎn)與基站的直接通信，并通過(guò)數(shù)據(jù)融合降低通信能量的損耗。Leach 算法是周期性執(zhí)行的，分為分簇階段和穩(wěn)定階段。在分簇階段，節(jié)點(diǎn)會(huì)產(chǎn)生一個(gè)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)。沒(méi)有加入任何簇的節(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算法延長(zhǎng)了整個(gè)網(wǎng)絡(luò)的生存周期。
1.2 DEEC算法分析
    DEEC算法[4]是針對(duì)Leach算法的改進(jìn)，考慮了節(jié)點(diǎn)的初始和剩余能量，增加了網(wǎng)絡(luò)的生存周期?？紤]到網(wǎng)絡(luò)的異構(gòu)性，數(shù)據(jù)傳輸節(jié)點(diǎn)的能量不可能都相同，因此每個(gè)節(jié)點(diǎn)成為簇頭的概率就不同。節(jié)點(diǎn)成為簇頭的概率pi與改進(jìn)的閾值T（n）的關(guān)系如下：
  
    參考文獻(xiàn)[5]對(duì)DEEC分簇算法進(jìn)行改進(jìn)。由于在數(shù)據(jù)傳輸階段，簇頭節(jié)點(diǎn)間沒(méi)有考慮傳輸跳數(shù)，因此可能會(huì)造成大的傳輸延遲。但是跳數(shù)縮小時(shí)，多跳傳輸中選擇下一簇頭時(shí)沒(méi)有考慮到剩余能量，同時(shí)一旦能量的消耗過(guò)大，節(jié)點(diǎn)就不足以繼續(xù)多跳傳輸。
1.3 網(wǎng)絡(luò)模型
    本路由算法中的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)為n個(gè)節(jié)點(diǎn)隨機(jī)分布在M×M區(qū)域內(nèi)。節(jié)點(diǎn)集合表示為S={s1，…，sn}，同時(shí)網(wǎng)絡(luò)有以下特點(diǎn)：
    (1)本網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)為靜態(tài)的，節(jié)點(diǎn)和基站節(jié)點(diǎn)的位置都不會(huì)隨時(shí)間改變。
    (2)傳感器節(jié)點(diǎn)的初始能量相同，每個(gè)節(jié)點(diǎn)具有唯一的ID號(hào)。
    (3)傳感器節(jié)點(diǎn)可以自己調(diào)節(jié)無(wú)線(xiàn)的發(fā)送功率。
1.4 IDEEC算法中的相關(guān)參數(shù)
    在無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中，主要根據(jù)網(wǎng)絡(luò)的生存時(shí)間和負(fù)載平衡程度來(lái)判定分簇路由算法的好壞。在分簇路由算法中，每輪中簇的覆蓋節(jié)點(diǎn)的平均程度會(huì)影響網(wǎng)絡(luò)的生存周期。
1.5 能量消耗模型
    本文中統(tǒng)一采用與Leach算法相同的無(wú)線(xiàn)通信能量消耗模型，能量消耗公式是一階無(wú)線(xiàn)電模型[6]。節(jié)點(diǎn)發(fā)送l bit數(shù)據(jù)所消耗的能量由發(fā)射損耗和功率放大損耗兩部分組成：

    式中Einitial為節(jié)點(diǎn)的初始能量。當(dāng)候選簇頭的剩余能量大于Ethr，才能成為簇頭。通過(guò)引入能量閾值，可以防止較低能量的節(jié)點(diǎn)成為簇頭，造成網(wǎng)絡(luò)中數(shù)據(jù)的丟失和重新選舉簇頭的開(kāi)銷(xiāo)。為了使簇分布更加均勻，引入了覆蓋半徑Rc。Rc代表了整個(gè)網(wǎng)絡(luò)每個(gè)簇的覆蓋距離，計(jì)算公式為：
    
    成為簇頭的節(jié)點(diǎn)廣播消息，當(dāng)節(jié)點(diǎn)收到該消息后計(jì)算與該簇頭的距離，如果小于通信半徑r，則改變節(jié)點(diǎn)的類(lèi)型為簇的候選成員節(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ù)包后選擇就近的簇頭加入，沒(méi)有加入到簇的節(jié)點(diǎn)則直接與基站通信。
    完成分簇后，進(jìn)入到數(shù)據(jù)信息傳輸階段，本算法中將采用兩種方法來(lái)進(jìn)行傳遞。當(dāng)簇頭節(jié)點(diǎn)的平均能量較大時(shí)，采用最小路由數(shù)傳遞數(shù)據(jù)，保證節(jié)點(diǎn)在最小時(shí)延下到達(dá)sink節(jié)點(diǎn)。但同時(shí)能量消耗的也較快，會(huì)導(dǎo)致網(wǎng)絡(luò)的生存周期較短，所以當(dāng)節(jié)點(diǎn)能量達(dá)到門(mén)限值后，將采用最短距離來(lái)進(jìn)行簇頭間的下一跳路由的選擇，這樣將能延長(zhǎng)整個(gè)網(wǎng)絡(luò)的生存周期。
    在最小路由[7]傳遞數(shù)據(jù)時(shí)，定義一個(gè)距離?茁，其值與d0相同，簇頭節(jié)點(diǎn)按照同樣的功率傳遞廣播數(shù)據(jù)包，數(shù)據(jù)包中包含節(jié)點(diǎn)的ID號(hào)、剩余能量以及離基站的距離。其他簇頭節(jié)點(diǎn)收到數(shù)據(jù)包后，比較與自己之間的距離，當(dāng)節(jié)點(diǎn)離基站距離小于?茁時(shí)，則選作下一跳，這樣保證了節(jié)點(diǎn)能夠直接地傳輸數(shù)據(jù)到基站，減小了傳送時(shí)延，但這種方式也加快了節(jié)點(diǎn)能量的消耗，為了使負(fù)載平衡，引入能量門(mén)限值E1，當(dāng)節(jié)點(diǎn)能量低于E1時(shí)，進(jìn)行最短路徑傳輸，節(jié)點(diǎn)通過(guò)選擇離自己最近的簇頭進(jìn)行數(shù)據(jù)傳輸。這樣既保證了傳輸時(shí)延短，同時(shí)也能使網(wǎng)絡(luò)的生存周期加長(zhǎng)。其中E1為簇頭的平均能量大小。
3 仿真結(jié)果
    對(duì)本文提出的協(xié)議進(jìn)行性能測(cè)試，同時(shí)選擇了Leach算法和DEEC算法進(jìn)行仿真結(jié)果的比較。假定無(wú)線(xiàn)傳感器網(wǎng)絡(luò)是隨機(jī)布置在一個(gè)二維的平面區(qū)域，節(jié)點(diǎn)的位置部署是隨機(jī)選擇的，基站位于節(jié)點(diǎn)正上方。三種算法的效率如圖1所示。

    圖1中，整個(gè)網(wǎng)絡(luò)的生存周期明顯增長(zhǎng)，第一個(gè)死亡節(jié)點(diǎn)出現(xiàn)的時(shí)間較晚。把第一死亡節(jié)點(diǎn)出現(xiàn)的時(shí)間作為網(wǎng)絡(luò)性能的檢驗(yàn)條件，生存周期的性能相對(duì)于Leach和DEEC協(xié)議分別提高了大約50%和30%，這是因?yàn)長(zhǎng)each和DEEC算法中由于隨機(jī)選擇簇頭節(jié)點(diǎn)，節(jié)點(diǎn)的分布不均勻，造成第一個(gè)死亡節(jié)點(diǎn)先出現(xiàn)，其中雖然DEEC考慮到了剩余能量的選擇，但是對(duì)于簇的分布沒(méi)有進(jìn)行考慮。
    比較圖1中的數(shù)據(jù)傳輸效率，可以看出IDEEC算法的數(shù)據(jù)傳輸效率大大高于另外兩種算法。
    如果從整個(gè)網(wǎng)絡(luò)的死亡節(jié)點(diǎn)出現(xiàn)的時(shí)間分析，則生存周期的性能相對(duì)于Leach和DEEC路由算法分別提高了大約30%和25%，由此可見(jiàn)整個(gè)網(wǎng)絡(luò)的生存周期得到了很大的提升。同時(shí)從圖1(b)中的傳輸效率可以看出改進(jìn)的路由算法的數(shù)據(jù)傳輸量很大，很大程度上提高了網(wǎng)絡(luò)的傳輸效率。
    圖2顯示了路由算法每輪形成的簇的數(shù)目，在前1 500輪時(shí)，形成的簇的數(shù)目較大，這是因?yàn)樵? 500輪已經(jīng)產(chǎn)生了第一死亡節(jié)點(diǎn)，網(wǎng)絡(luò)的簇的數(shù)目受到了影響，從圖中的趨勢(shì)可以看出，改進(jìn)的DEEC協(xié)議產(chǎn)生的簇的數(shù)目較以前穩(wěn)定，這是由于引入均勻分簇的原因，所以整個(gè)簇的數(shù)目較穩(wěn)定，不會(huì)受到巨大的波動(dòng)。

    在無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的分簇協(xié)議中，簇的形成以及數(shù)據(jù)傳輸?shù)倪x擇方式直接影響著無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的性能。正是基于以上問(wèn)題，本文中的路由算法對(duì)現(xiàn)有的算法進(jìn)行了改進(jìn)，引入均勻分簇和傳輸負(fù)載均衡。根據(jù)仿真結(jié)果，本算法綜合考慮了網(wǎng)絡(luò)分布均勻及節(jié)點(diǎn)傳輸階段傳輸時(shí)延的問(wèn)題，提高了網(wǎng)絡(luò)路由算法的生存周期。
參考文獻(xiàn)
[1] 孫利民.無(wú)線(xiàn)傳感器網(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ú)線(xiàn)傳感器網(wǎng)絡(luò)LEACH協(xié)議的改進(jìn)[J].計(jì)算機(jī)工程與應(yīng)用，2010，46(17)：117-120.
[7] 楊云，李斌，高峰，等.無(wú)線(xiàn)傳感器網(wǎng)絡(luò)簇內(nèi)優(yōu)化的最小跳數(shù)路由算法[J].計(jì)算機(jī)應(yīng)用與軟件，2010，27(2)：31-33，46.