無線網絡中DEEC協議的改進

黃曉峰，劉廣鐘

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

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

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

1 相關研究

1.1 Leach算法的分析

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

1.2 DEEC算法分析

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

其中，si為節點，i∈[1，n]。

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

1.3 網絡模型

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

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

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

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

1.4 IDEEC算法中的相關參數

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

1.5 能量消耗模型

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

2 改進的路由協議

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

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

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

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

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

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

3 仿真結果

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

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

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

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

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

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

參考文獻

[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協議的改進[J].計算機工程與應用，2010，46(17)：117-120.

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