無線網絡中DEEC協(xié)議的改進

黃曉峰，劉廣鐘

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

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

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

1 相關研究

1.1 Leach算法的分析

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

1.2 DEEC算法分析

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

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

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

1.3 網絡模型

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

(1)本網絡拓撲結構為靜態(tài)的，節(jié)點和基站節(jié)點的位置都不會隨時間改變。

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

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

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

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

1.5 能量消耗模型

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

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

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

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

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

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

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

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

3 仿真結果

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

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

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

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

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

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

參考文獻

[1]孫利民.無線傳感器網絡[M].北京：清華大學出版社，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網絡技術[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]劉玉華，趙永鋒，許凱華，等.無線傳感器網絡 LEACH協(xié)議的改進[J].計算機工程與應用，2010，46(17)：117-120.

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