盧建剛，樂紅兵

(江南大學物聯(lián)網(wǎng)工程學院，江蘇無錫214122)

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

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

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

1 問題描述

1．1LEACH算法

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

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

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

1．2 LEACH算法存在的問題

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

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

(3)在無線傳感器網(wǎng)絡中數(shù)據(jù)傳輸?shù)哪芰肯闹饕娐纺芰肯暮凸Ψ拍芰肯模⑶液笳呤侵饕?。依?jù)空間信道模型，功放能耗的大小取決于信號的傳輸距離，因此隨著傳輸距離的增加，傳輸所消耗的能量將急劇上升。在LEACH算法中，簇頭與基站之間的單跳數(shù)據(jù)傳輸方式會造成簇頭能量消耗過大。

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

2 改進算法及分析

2．1 系統(tǒng)描述

2．1．1 網(wǎng)絡模型

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

(1) 傳感器網(wǎng)絡建立后，節(jié)點在網(wǎng)絡中的位置將不會發(fā)生變化。

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

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

(4) 節(jié)點的無線發(fā)射功率可以依據(jù)接收者的距離進行調(diào)整。

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

2．1．2 能量模型

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

接收kbit的數(shù)據(jù)需要消耗的能量為:

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

2．2LEACH-D 算法

2．2．1 相關定義

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

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

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

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

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

2．2．2 簇頭的選擇

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

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

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

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

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

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

2．2．4 數(shù)據(jù)傳輸

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

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

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

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

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

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

圖1 簇樹路由的構(gòu)建

2．2．5 算法分析

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

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

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

3 仿真結(jié)果及分析

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

表1 仿真環(huán)境主要參數(shù)

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

圖2 不同V1取值下的第一個節(jié)點死亡發(fā)生的輪數(shù)

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

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

圖3 剩余節(jié)點曲線圖

圖4 總能耗曲線圖

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

圖5 不同方案下存活時間

4 總結(jié)

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

［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，F(xiàn)ahmy 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，F(xiàn)akhraie 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］ 張偉華，李臘元，張留敏，王選政．無線傳感器網(wǎng)絡LEACH協(xié)議能耗均衡改進［J］．傳感技術學報，2008，21(11):1918 －1922．

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

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

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

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

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

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