基于節點相對密度的無線傳感器網絡成簇算法*

盧建剛，樂紅兵

(江南大學物聯網工程學院，江蘇無錫214122)

無線傳感器網絡的路由算法從網絡邏輯結構角度可以分為平面型和層次型兩種。由于平面路由算法中節點需要較多存儲空間來維持較大路由信息，同時在數據處理上不能進行有效數據融合，因此該路由算法不適用于大型的傳感器網絡。層次路由算法又稱分簇路由算法，這類算法在一定程度上克服了平面路由算法的不足，其中 LEACH［1］(Low Energy Adaptive Clustering Hierarchy)是最早提出的分簇路由算法，后來的許多分簇路由算法都是在它的基礎上發展起來的。

無線傳感器網絡中分簇路由算法的改進一般都是圍繞簇頭的選擇，成簇的方法以及數據傳輸的方式來考慮設計的。不少國內外研究人員針對LEACH算法的改進也主要從這三個方面進行。早期改進算法中比較經典的有Ossama Younis等人提出的HEED算法［2］，它在簇頭的選擇過程中考慮了節點的剩余能量，但因在簇頭選擇時約束條件過多，故而增加了算法的復雜度。Heinzelman W等人提出的LEACH-C算法［3］采用集中控制，它考慮節點能量和位置信息，但需要通過基站來控制節點如何成簇，這樣網絡不是完全自組織的，使用范圍受到限制。近年來國內外也有不少學者從事這方面的研究，提出一些比較好的改進方法。如文獻［4］采取在每個簇內增加副簇頭來保證數據傳輸的穩定性，有效地解決了簇頭在數據傳送過程中因為能量耗盡而中斷傳輸的問題。文獻［5］提出的模糊路由和數據融合算法整體改善了整個網絡的能量損耗，但該算法的可操作性比較差。國內的張偉華等人提出的LEACH-B算法［6］在選擇簇頭時將節點的當前能量和節點充當簇頭的次數綜合考慮了進來，然而當網絡運轉時間較長，整個算法優勢將會變得不明顯。李成岳等人提出的LEACH-T算法［7］采用了時間間隔來選取簇頭，保留了分布式產生簇頭的優點，避免了每輪產生簇頭個數的不確定性，但該算法對傳感器的要求較高，不便于廣泛的推廣應用。

本文在綜合研究LEACH及其相關改進算法的基礎上，針對LEACH算法存在簇頭分布不均和簇間負載不均衡的問題，提出了一種通過考慮節點相對密度來選擇簇頭和采取選擇合理中轉簇頭完成多跳通信的算法。通過Matlab的仿真表明，該算法有效改善了網絡生存時間和簇間負載均衡的問題。

1 問題描述

1．1LEACH算法

LEACH算法是MIT學者A．Chandrakasan等人為無線傳感器網絡設計的低功耗自適應聚類路由算法。LEACH算法提出了“輪”的概念，每輪分為簇的建立階段和穩定的數據通信階段，簇頭通過輪換來達到均衡節點能耗的目的。

初始化階段是簇頭的形成階段。在初始階段，每一個節點從0～1中選取一個隨機數，如果這個隨機數小于這一“輪”所設定的門閾值T(n)，那么這個節點就成為簇頭。T(n)的計算公式:

式中:p是網絡中簇頭所占比例;r為當前的輪數;G為在最后的1/p輪中還沒有成為過簇頭的節點集。節點在當選簇頭后，需要發布消息告知其它節點自己是簇頭。非簇頭的節點根據接受信號的強度來選擇它要加入的簇，并通知相應的簇頭。最后簇頭產生一個TDMA定時消息，并且通知簇內節點。當簇內節點收到TDMA同步消息后，它們將在各自的時間段內發送數據，在時段外是進入睡眠狀態。簇形成和TDMA時刻表確定后，就進入了本輪的數據傳輸階段。簇頭把來自簇內節點的數據進行數據融合和壓縮處理后，傳給遠處的基站。經過一個TDMA時刻表后，新的一輪又開始了，如此循環運行，直到大多數節點的能量耗盡為止。

1．2 LEACH算法存在的問題

(1)在LEACH算法中簇頭的選擇是通過采用閾值判定方法來選取的，具有極大的隨機性。這種隨機性可能造成簇頭在網絡中分布不均勻，導致有些節點密集區域簇頭過少甚至沒有，而有些節點稀少區域內簇頭過多，使得一部分節點無法加入任何簇或者促使其成員節點與較遠簇頭進行數據傳輸而消耗自身過多的能量。

(2)在LEACH算法中，由于簇頭選舉的隨機性使得網絡中簇頭需要負擔的節點數不同，在這種情況下可能加重了個別簇頭的負擔，導致簇間負載不均衡，使得整個網絡的負載平衡程度下降。

(3)在無線傳感器網絡中數據傳輸的能量消耗主要包括電路能量消耗和功放能量消耗，并且后者是主要的。依據空間信道模型，功放能耗的大小取決于信號的傳輸距離，因此隨著傳輸距離的增加，傳輸所消耗的能量將急劇上升。在LEACH算法中，簇頭與基站之間的單跳數據傳輸方式會造成簇頭能量消耗過大。

以上所提及LEACH算法所存在的問題，嚴重地影響了網絡的生存時間和簇間的負載平衡。為了有效地解決以上問題，本文提出了一種基于節點相對密度成簇算法—LEACH-D。

2 改進算法及分析

2．1 系統描述

2．1．1 網絡模型

所有的傳感器節點被隨機部署在一個N×N的正方形區域，周期性的采集該區域的信息。同時對建立的無線傳感器網絡作如下假設:

(1) 傳感器網絡建立后，節點在網絡中的位置將不會發生變化。

(2) 基站部署在該監測區域外的一個固定位置，且基站是唯一的。

(3) 網絡中所有傳感器節點初始能量相同，且能量是有限。

(4) 節點的無線發射功率可以依據接收者的距離進行調整。

(5) 節點之間連接對稱。若已知對方發射功率，則節點可以依據接收信號強度計算出發射者距自己的距離。

2．1．2 能量模型

無線能量模型根據通信節點之間的傳輸距離d的大小分為自由空間模型和多路徑衰減模型，式(3)為發送kbit數據消耗的能量，d0是決定哪種模型的閾值，它的大小由式(2)確定:

接收kbit的數據需要消耗的能量為:

其中，Eelec是收發電路所消耗的能量，εfs、εmp分別為兩種模型中功率放大所需的能量。

2．2LEACH-D 算法

2．2．1 相關定義

(1)鄰居節點 在網絡中每個傳感器節點都存在一個通信半徑，處于此通信半徑范圍之內的節點稱為其鄰居節點。

陽泉市位于山西省中部東側，全市總面積4 578 km2。地下水開采以娘子關泉域巖溶水為主，娘子關泉域巖溶地下水以水量集中穩定、水質良好成為陽泉市工農業生產及城市供水的重要供水水源。

(2)節點相對密度 在標準通信半徑R范圍內，節點所在實際網絡中的鄰居節點數與標準簇內鄰居節點數的比值。節點n的相對密度計算公式如下:

其中標準通信半徑R的大小為:

式中，Neighbor(n)_alive表示節點n在標準通信半徑范圍內的鄰居節點數;S表示節點所在區域的面積;N為網絡區域內的節點數;p表示簇頭占網絡節點總數的百分比;式(5)中，(1/p)－1是標準簇內的鄰居節點數。

2．2．2 簇頭的選擇

在以往針對LEACH算法的改進中很大一部分是通過對節點自身因素的考慮來決定簇頭的選擇，卻往往忽略了周圍其他節點的影響，這樣會由于節點分布狀況不明而造成簇頭在整個網絡中的分布不均勻。為了有效地反映每個節點所在區域內節點的分布狀況，本文在文獻［8］的基礎上提出相對節點密度的概念，并通過節點相對密度(如公式(5)所示)的大小來影響簇頭在整個網絡中的分布。

為了確保簇頭在整個網絡中合理分布，使得節點密集程度高的區域出現簇頭的個數多于節點密集程度低的區域，需采取的方法就是增大處于節點密集區的節點成為簇頭的概率;反之，則降低節點密集程度低所在區域的節點成為簇頭的概率。為此，本文在簇頭的選擇問題上將節點相對密度這個因素考慮進來，通過節點相對密度來影響簇頭的分布。從而得到改進后的簇頭選舉閾值T(n)為:

根據公式(7)計算簇頭選舉時的閾值T(n)可以看出，簇頭的選擇不再是單個節點的事情，而是要與周圍節點數聯系起來一起考慮，這樣就保證了每輪簇頭選舉中處于網絡密集區的節點有更大概率被選為簇頭節點的可能，同時為了避免簇頭集中出現在同一密集區造成覆蓋區域重疊的狀況，在當選簇頭的競爭區域內應盡量避免其它候選簇頭的出現。

本文在數據傳輸上采用多跳通信，但是這種通信方式使得靠近基站的簇頭除了進行自身簇內信息的收集，還要額外的擔負起其他簇頭的信息中轉，造成這一區域的簇頭能量消耗過大，導致產生了新的“熱區”問題［9－10］。為了克服這個問題，本文在簇的規模上進行了控制，使得越靠近基站區域節點成簇的規模越小，讓處于基站附近的簇頭有更多的能量用于其他簇頭的信息中轉，保持簇間負載均衡。

為了實現簇的規?？刂?，本文在文獻［11］的基礎上采取了一種改進的分簇規模約束機制，即在簇形成階段設置簇內非簇首節點數目的門限值以控制成簇的規模。其中，每個簇頭擁有的門限值的大小根據簇頭距離基站的遠近自動調整，即距離基站近的簇規模小，遠離基站遠的簇規模大。如果節點i成功當選簇頭，則其簇內節點數目N(i)應控制在M(i)的范圍內。當簇內節點數超過其控制的范圍，簇頭則拒絕接受其他節點入簇要求，并告知這些節點去選擇其他較近且簇內成員未滿的簇頭成簇。同時，如果出現節點到基站的距離小于或等于節點到簇頭的距離，則選擇節點直接與基站通信。其中M(i)的大小為:

其中:d(CHi，BS)是簇頭i到基站的距離;dCHmin是簇頭到基站的最近距離;dCHmax是簇頭到基站的最遠距離;e是修正節點數的加權因子，本文e取2/3。

2．2．4 數據傳輸

當簇生成后，就需建立簇頭與基站之間的通信。本文根據節點成簇的特點，在數據傳輸中采取了簇頭間多跳轉發機制。因此，如何合理選擇中轉簇頭成為多跳數據傳輸中的關鍵問題。

在構建路由表時，每個簇頭為了能找到更合理中轉簇頭，需要建立一張候選中轉簇頭集C(i)。為了將鄰近簇頭納入到自己的候選中轉簇頭集中，每個簇頭需以更大的通信半徑2·R廣播一條消息Head-Msg，其中包含簇頭的ID、剩余能量及其與基站的距離d。每個簇頭需通過以上獲取的信息來決定鄰近簇頭是否存在于自己的候選中轉簇頭集中。其中候選中轉簇頭集C(i)定義為:

假設簇頭i在C(i)中選取簇頭j作為中轉簇頭，簇頭j在C(j)中選取簇頭h作為中轉簇頭，且在通信過程中采用自由空間模型。計算傳輸kbit數據時消耗i和j兩個簇頭的能量為:

由上式可知，在數據傳輸中網絡能量的消耗取決于d(i，j)和d(j，h)的大小。然而只考慮中轉簇頭距離的遠近，而忽略其能量的大小，容易使單個中轉簇頭在轉發任務中能量過早耗盡，造成數據傳輸中斷。因此，本文綜合考慮了中轉簇頭的剩余能量和距離，并通過比較候選中轉簇頭集中簇頭T(CHi)的大小來建立更加合理網絡路由。

其中 ECHi－current是簇頭 i的剩余能量;ECHi－init是簇頭 i的初始能量;d(CHi，CHy)是簇頭 i到簇頭y的距離;dCHmax是簇頭到基站的最遠距離;v1是加權系數。

路由表的建立從離基站最遠的簇頭y開始，簇頭y通過查詢C(y)中簇頭T(CHi)的大小來選取擁有最大T(CHi)的簇頭作為其父節點。當出現簇頭T(CHi)相等的情況時，則根據ID的大小決定其父節點。該父節點繼續搜索，并選擇它的候選中轉簇頭中權重最大的作為根節點，依次搜索，直至所有簇頭加入到樹中，完成簇樹路由的構建，并由最后選取的根節點將數據傳遞給BS，如圖1所示。

圖1 簇樹路由的構建

2．2．5 算法分析

性質 整個算法的控制消息復雜度為O(N)

證明 本算法每輪產生的控制消息包括:(1)在每輪算法開始前，每個節點以半徑R廣播一條Hello-Msg，用來統計鄰居節點數。(2)在簇生成過程中，對于普通成員節點，只要發送一條請求入簇消息Join-Msg，用于加入所選的簇;簇頭需要發送一條當選簇頭消息CH-Msg，宣布當選簇頭。(3)在構建簇樹路由的過程中，每個簇頭以半徑2R廣播一條Head-Msg。設簇頭比率是P，從而網絡中總的控制消息開銷為:

因此整個算法的控制消息復雜度是O(N)

3 仿真結果及分析

在仿真實驗中，無線傳感器網絡由100個節點組成，隨機分布在100 m×100 m的區域內，基站位于平面坐標(50 m，175 m)，節點當選簇頭的概率p取0．05，節點的通信半徑 R根據式(6)取25．2 m。本文使用MATLAB對LEACH算法、EERP算法［12］和LEACH-D算法進行了仿真比較，參數的設置如表1所示。

表1 仿真環境主要參數

在數據傳輸過程中，計算簇頭權重的加權系數v1的大小直接影響整個算法的性能。圖2顯示了v1取不同值時，LEACH-D算法中第一個節點死亡發生的輪數。當v1的取值從0．1逐漸增加到0．2的過程中，中轉簇頭的選擇在考慮數據中轉能量消耗的同時，也增加對中轉簇頭當前能量的考慮，實現了均衡中轉簇頭能耗的目的，進而延緩第一個節點死亡發生的時間;當v1的取值大于0．2時，過分注重中轉簇頭當前能量，而逐漸忽略簇頭在數據中轉時的能量消耗，最終造成中轉簇頭能量消耗過大，從而加快了第一個節點死亡發生的時間。故從圖1可以看出，v1存在一個最優值0．2，此時第一個節點死亡發生的時間最晚。

圖2 不同V1取值下的第一個節點死亡發生的輪數

將這三種算法置于同等條件下，分別進行相關性能指標的測試。圖3顯示的是在三種不同算法作用下剩余節點數量的對照圖。從曲線的差別可以看出:(1)LEACH-D算法中第一個死亡節點出現時間滯后于LEACH算法和EERP算法;(2)隨著時間的推移，LEACH-D算法中節點減少的速度比在LEACH算法和EERP算法明顯放緩。通過比較三種算法作用下的曲線可以更加直觀說明改進后的算法更好地平衡了網絡負載，實現了延長網絡生命周期的目的。

能耗是衡量改進后算法性能的關鍵指標。從圖4節點剩余能量曲線的走勢可以看出:在整個網絡生命周期中，改進后的LEACH-D算法剩余能量曲線的下降速度要慢于其他兩種算法曲線。大約在r=400的時候，改進后的算法在能量消耗上比LEACH、EERP要少得多?？梢姡琇EACH-D算法通過均衡節點能耗，促使節點總能耗的降低。

圖3 剩余節點曲線圖

圖4 總能耗曲線圖

網絡生存時間能夠比較直觀的反映改進后算法的優劣性。本文分別采用網絡中1%、10%、50%、70%節點死亡發生輪數對三種算法進行了對比評價。仿真結果如圖5所示，EERP算法在LEACH算法的基礎上優化了數據的傳輸路徑，提高了整個網絡生存周期。其中，1%、10%、50%和70%的死亡節點發生的輪數分別較前者提高了3．7%、5．7%、5．9%和4．4%。而本文路由算法在均衡網絡能量消耗方面比EERP算法有了進一步的改善。其中，1%、10%、50%和70%的死亡節點發生的輪數分別比EERP算法提高了5%、3．6%、6%和4．4%。故就網絡的整體性能指標來看，本文的路由方案在均衡網絡能量消耗方面比以上兩種方案有了改進。

圖5 不同方案下存活時間

4 總結

針對實際網絡中可能出現傳感器節點分布不均勻以及LEACH算法的不足，本文提出了一種基于節點相對密度來選擇簇頭，并根據數據多跳傳輸的特點，采取構建簇樹路由的方法來解決網絡中簇間負載不均衡的問題。MATLAB仿真實驗表明，LEACH-D算法相對LEACH算法、EERP算法而言，能促進簇頭的均勻分布，有效均衡整個網絡的節點能耗，從而提高網絡的生命周期。

［1］ HeinzelmanW ，Chandrakasan A，Balakrishnan H．An Application-Specific Protocol Architecture for Wireless Microsensor Networks［C］//IEEE Transactions on Wirelesss Communications，2002，1(4):660－670．

［2］ Younis O，Fahmy S．A Hybrid，Energy Efficient，Distributed Clustering Approach for Ad-Hoc Sensor Networks［J］．IEEE Trans．on Mobile Computing，2004，3(4):660 －669．

［3］ Heinzelman W．Application-Specific Protocol Architectures for Wireless Networks［D］．Boston:Massachusetts Institute of Technology，2000．

［4］ Yassein M Bani，Al-zou’bi A，Khamayseh Y，et al．Improvement on LEACH Protocol of Wireless Sensor Network(VLEACH)［J］．Journal of Digital Content Technology and its Applications(JDCTA)，2009，3(2)．

［5］ Hamzeh M，Arab S，Fakhraie S M，et al．An Improvement on LEACH Algorithm with a Fuzzy Processor［C］//Proceedings of the 14th Asia-Pacific Conference on Communications(APCC)．IEEE Communications Society，2008:1 －5．

［6］ 張偉華，李臘元，張留敏，王選政．無線傳感器網絡LEACH協議能耗均衡改進［J］．傳感技術學報，2008，21(11):1918 －1922．

［7］ 李成岳，申鉉京，陳海鵬，孫恩巖．無線傳感器網絡中LEACH路由算法的研究與改進［J］．傳感技術學報，2010，23(8):1163－1167．

［8］ 喬俊峰，劉三陽，曹祥宇．無線傳感器網絡中基于節點密度的簇算法［J］．計算機科學，2009，36(12):46 －49．

［9］ 李成法，陳貴海，葉懋，吳杰．一種基于非均勻分簇的無線傳感器網絡路由協議［J］．計算機學報，2007，30(1):27 －36．

［10］ 劉明，黃小燕，劉銳．一種區域間能量均衡的無線傳感器網絡分簇算法［J］．傳感技術學報，2009，22(4):548 －551．

［11］ 張秋余，彭鐸，劉洪國．基于能量的無線傳感器網絡分簇路由算法［J］，計算機應用研究，2009，26(2):674 －676．

［12］ 王微，馮遠靜，俞立．一種高能效的無線傳感器網絡路由協議設計［J］．傳感技術學報，2008，21(12):2061 －2066．