無線傳感器網絡路由協議的研究

（武漢理工大學 計算機科學與技術學院， 武漢 430063）

摘 要：在分析層次LEACH協議的基礎上，提出了LEACH協議算法存在的問題，并相應地修改了成簇算法，增強了算法的健壯性。節點能量耗盡是導致無線傳感器網絡生命周期縮短的主要因素，因此在選擇簇首時根據剩余能量最大的節點優先成為簇首節點，同時避免了因過多簇重組帶來的巨大能量開銷，而這些操作的主要能量消耗是在能量不受限制的Sink節點來完成的，從而保證了整個網絡的負載平衡，使整個網絡的生命周期達到最大化。經仿真和分析，改進后的分簇路由協議不僅有較好的節能效果，還具有較長的網絡生命周期。

關鍵詞：無線傳感器網絡；分簇路由協議；Sink節點；剩余能量；鏈表

中圖分類號：TP393.04文獻標志碼：A

文章編號：1001-3695(2009)04-1453-03

Research on routing protocol for wireless sensor networks

WANG Xuan-zheng，LI La-yuan，ZHANG Wei-hua，ZHANG Liu-min

(Institute of Computer Science Technology， Wuhan University of Technology， Wuhan 430063， China）Abstract:On the basis of analyzing the LEACH protocol，this paper brought up problems of the LEACH protocol algorithm and revised it， which made the algorithmic robustness strengthened. The node which energy uses up was the main reason in WSN shorten life cycle， so node priority became cluster head node which had maximal surplus energy in the process of dividing cluster， at the same time， had avoided the enormous energy expense of re-organizing， the main energy consume of these handle came to sink node whose energy were free， therefore， keeping the loads of network balance， making the lifecycle of network maximization. By simulation and analysis， improved divide cluster routing protocol is not only has good performance in energy consumption， but also makes the lifecycle of network longer.

Key words:wireless sensor networks; divide cluster routing protocol; Sink node; surplus energy; chain list

無線傳感器網絡是當今國內外備受關注的，有多學科高度交叉的新興前沿研究領域。它綜合了傳感器技術、嵌入式計算機技術、現代網絡及無線通信技術、分布式信息處理技術等，能夠通過各類集成化的微型傳感器相互協作，實時監測、感知和采集各種環境或監測對象的信息，并通過嵌入式系統對信息進行處理，無線傳感器網絡可隨機自組織網絡且以多跳中繼方式將所感知信息傳送到用戶終端。無線傳感器網絡具有十分廣闊的應用前景，在軍事國防、工農業、城市管理、生物醫療、環境監測、搶險救災、防恐反恐、危險區域遠程控制等許多領域都有重要的理論價值和巨大的實用價值，它已經引起了世界許多國家軍事界、學術界和工業界的高度重視，并且被公認為是對21世紀產生具有最大影響的十項技術之一[1]。

1 分簇LEACH協議的分析

1.1 LEACH協議的介紹

LEACH協議算法每一輪循環可分為兩個階段，在簇建立階段，相鄰節點動態的形成簇，隨機產生簇首；在數據通信階段，簇內節點把數據發送給簇首，簇首再進行數據融合并將結果發給Sink節點。節點自組織成不同的簇，每個簇只有一個簇首。所有非簇首節點將自己的數據發給所屬的簇首節點，為減少冗余數據的傳輸，簇首節點在數據融合后將數據發送給遠方的Sink節點。這樣，每個非簇首節點都只需要知道自己所屬簇即可。在實際應用中，還可以根據需要建立更多的層次。在LEACH算法中，為了避免簇首能量消耗過快，每個節點需輪流擔任簇首。因此，LEACH算法的實現分成一個個回合，每個回合又可分成簇形成階段和簇穩定階段。為了減少分簇帶來的額外能耗，簇穩定階段遠遠長于形成階段（實際應用難以實現）。在簇形成階段，每個傳感器節點先生成0～1的隨機數，如果生成的隨機數小于閾值，那么該節點就被選為簇頭。閾值的大小T(n)由下面公式來確定:



T(n)=p/[1-p×(r mod 1/p)] n∈G

0nG

其中：P為網絡中簇首所占比例;R為目前進行的輪次；G為在最后1/p輪中未成為簇首的節點集合。

節點被選為簇首后，就向外發送廣播信息，其他節點根據收到的廣播信號的強弱決定要加入哪個簇，并向簇首發送加入簇的請求，此廣播的過程節點能耗較大。簇首收到請求后將節點加入自己的路由表并為每個節點設定一個TDMA時間表，再將該表發送給所有簇內節點。在此后的簇穩定階段，節點按照該路由表進行數據傳輸。每隔一定時間整個網絡重新進入簇重組階段開始新一輪的簇首選舉過程[2]。而重復的簇重組是急需改進的地方。

1.2 LEACH協議的優缺點

WSN分簇路由協議設計的首要目標是通過高效的分簇算法生成合適的網絡結構，主動地通過能量管理去避免網絡連通性下降，延長網絡的生命周期[3]。因此，能量消耗成了通信連接性能好壞、網絡運行周期長短的主要決定因素，WSN的整體性能高度依賴于各種高能效的分簇路由算法。LEACH協議雖然極大地降低了網絡的總體能耗，提高了網絡的擴展性，但其仍有不足之處，如每輪都要重新分簇和重新選擇簇首，而簇建立階段的協議能量開銷較大；其次，它要求傳感器節點之間以及傳感器節點與Sink點之間均可以直接通信，所以網絡的擴展性不是那么強，不適用于大型網絡。另外，LEACH算法選舉出的簇首分布不均勻、能量分布不均衡[4]。

2 改進后的LEACH-L路由算法的設計

2.1 初始化工作

無線傳感器網絡根據網絡的規模將整個網絡劃分為N個區域［5］，每個區域中有多個無線傳感器節點，被劃分的區域則被稱為簇，WSN中的Sink節點為每個初始狀態的簇建立鏈表，每個鏈表按能量從高到低的順序存放自己所屬簇的節點，每個節點的能量級別值為0～8，每個鏈表則認命該鏈表中第一個節點為其初始狀態的簇首節點，初始狀態各節點的能量級別值一般為8，不過也可以根據不同情況有所改變，FLAG的值為1。LEACH-L無線傳感器網絡結構圖如圖1所示；鏈表中每個節點域如圖2所示。

其中:指針域指向存放下一個節點的指針；ID表示該節點的身份標志；能量級別表示節點剩余能量級別為0～8；FLAG表示節點是否可以擔當簇頭。

2.2 算法語言描述

Sink節點在簇首認命及簇的維護可分為以下四種情況：

a)簇內節點和簇首節點在進行數據傳輸時檢查其節點的能量級別位是否發生變化。當簇內節點能量級別發生變化時，則修改其能量級別值，并將其以控制幀（包含ID和能量級別變化位）傳送到簇首節點，簇首將所有請求的控制幀經整理后將其發送到能量不受限的Sink節點。該節點將收到的控制幀進行分解處理，尋找每個節點所屬簇對應的鏈表，并在其簇所屬的鏈表中找到該節點，將其能量級別值減去1后，該節點重新按能量級別高低的順序插入到這個鏈表合適的位置，能量級別值之所以減去1，是因為節點能量消耗不可能在沒有通信的情況下消耗兩個能量級別。

b)當簇內節點能量級別位沒有發生變化時，簇內節點直接向簇首傳送數據包，簇首將所有簇內節點傳來的數據進行數據融合；當簇首的能量級別位發生變化且能量級別值大于0時，首先簇首節點先將自己的能量級別值減去1，并存儲自己新的能量級別值；然后將其他簇發來的控制幀（包含ID和能量級別變化位）進行整理；再將整理后以新控制幀的形式發送到Sink節點。該節點根據收到的數據進行分解處理，尋找每個節點所屬簇對應的鏈表，并在其簇所屬的鏈表中找到該節點，將其能量級別值減去1后，將節點重新按能量級別高低的順序插入到該鏈表合適的位置。

c)當簇首能量級別位沒有變化且級別值大于0時，只傳送數據包即可；當簇首節點能量級別值等于0且在數據傳輸時，則簇首節點以控制幀的形式向Sink節點報告，將其退出簇首信息以控制幀的形式傳送到Sink節點。該節點判斷該鏈表中的第一個節點的FLAG的值是否為1。如果為1，則Sink節點將認命鏈表中第一個節點為新的簇首節點，并要修改其對應鏈表中原簇首節點的FLAG值為0且將原簇頭節點的能量級別值作修改（鏈表中FLAG值為0的節點不能擔當新簇首），將原簇首節點按能量由高到低順序重新插入到鏈表中合適的位置，新認命的簇首節點被原簇首節點廣播給簇內節點，這時簇內節點就知道了該簇新的簇首節點，其他節點向新簇首發送加入簇的請求，簇首收到請求后將節點加入自己的路由表并為每個節點設定一個TDMA時間表，再將該表發送給所有簇內節點。否則，該簇退出工作（由于簇內所有節點能量已耗盡）。

d)Sink節點為各個簇首節點分配CDMA。在此后的簇穩定階段，節點按照該路由表進行數據傳輸[6]。如果簇內節點向簇首節點發送數據，首先發送控制幀（包含ID和能量級別變化位），簇首根據實際情況分配TDMA[7]，進行重新優化分配，給予發送數據量多的簇內節點，分配適當時隙長度，少量數據則分配較短的時隙長度，未傳輸數據的簇內節點不分配時隙。如果存在某些簇內節點能量級別為NULL時，則立即向簇首發送請求退出工作，簇首將此信息通過控制幀的形式傳送給Sink節點，該節點將其對應簇首的節點鏈表中節點刪除。如果鏈表的第一個節點的FLAG的值是0，則說明該簇已成為弱簇，該簇內的所有節點的能量馬上就要耗盡，此時，簇管理到此終止。

總之，簇首收到簇內節點的數據之后，進行數據融合，如果Sink節點附近有別的簇首節點也要向Sink節點發送數據，則其與離Sink節點附近的簇首節點重新進行數據融合，然后由離Sink節點較近的并且有數據將要發送的簇首節點傳送到Sink節點；如果Sink節點附近沒有其他的簇首節點要發送數據，則原來的簇首節點通過單跳或者多跳（盡量選擇在原簇首節點和Sink節點直線上的簇首節點作為多跳的中繼節點）的方式向Sink節點傳送數據。

2.3 算法可靠性維護

算法的可靠性維護主要涉及網絡節點的增加、減少及簇重組等所帶來的網絡拓撲結構變化[8]。

1)節點的加入 當有新的節點要加入到網絡中時，新的節點根據接收到周圍其他簇首節點信號的強度來決定加入哪個簇。如果節點發現E簇的信號強度最大，則說明新的節點離E簇最近，新的節點將向E簇簇首節點發出請求加入信號（附帶有該節點的能量級別值和ID），這時E簇簇首判斷該節點是否可以讓該節點加入該簇（主要依據能量是否充足）；如果簇首同意加入，則立即向新節點回復一個“yes”加入信息；同時簇首節點將新節點加入簇的信息與附近簇的信息進行數據整理后，通過附近其他的離Sink節點較近的簇首傳遞到Sink節點（或者直接通過單跳傳遞到Sink節點）。該節點找到E簇所對應的鏈表，將新的節點按能量級別從大到小的順序插入到該鏈表中合適的位置；如果不同意加入，其原因一般是新的節點的能量級別值沒有達到能夠擔任節點的水平，則簇首只新回復一個“no”拒絕信息，一旦節點收到該信息，則該節點將永久不能加入網絡中。

2）節點的退出 大部分節點由于工作而使其能量漸漸消耗殆盡，這樣會造成某些節點失去擔當網絡節點的能力。如果即將失效的是簇首節點，當簇首節點能量級別值等于0且在數據傳輸時，則簇首節點以控制幀的形式向Sink節點報告，將其退出簇首信息以控制幀的形式傳送到Sink節點。該節點判斷該鏈表中的第一個節點的FLAG值是否為1，若為1，則Sink節點將認命鏈表中第一個節點為新的簇首節點，并要修改原簇首對應鏈表中的FLAG值為0且將原簇首節點的能量級別值作修改（鏈表中FLAG值為0的節點不能擔當新簇首），將原簇首節點按能量由高到低順序重新插入到鏈表中合適的位置，否則該簇聲明退出工作；如果即將失效是簇內節點，節點的能量級別發生變化且能量級別值如果為NULL，則該節點會立刻向所屬的簇首發送請求退出工作控制幀，簇首會將附近其他簇的信息與此信息進行整理，單跳或通過多跳的方式傳遞到Sink節點。該節點會找到該節點所屬的簇對應的鏈表，將鏈表中的該節點刪除即可。如果簇內節點長時間沒有對簇首響應，則采用上面同樣的方法將沒有響應的節點從鏈表中刪除。

2.4 算法理論分析

理論分析可知，由于LEACH協議的簇內節點以廣播的形式相互競爭簇頭節點，不僅消耗了自己的節點的能量，還消耗了簇內其他節點的能量，而改進后真正的通信次數為1（1次廣播），另外與其他人改進的能量分簇算法相比，所傳輸的控制消息幀長度較短（能量級別變化位而不是能量級別值），其每個能量級別值至少3位，而筆者改進的能量變化位只需1位即可（其中1表示能量級別發生了變化，0表示能量級別值沒有發生變化）；簇首的選取是由能量不受限的Sink節點根據其鏈表來選擇的，只需要Sink節點向原簇首節點發送一個控制幀（只包括新簇首的ID）即可。因此可以大大地減少整個簇節點的能量消耗。

LEACH-L算法簇重組頻率有了較大的降低，節點的能量得到了最大化的利用，節點負載平衡性有很大的提高，成簇過程中，避免了LEACH算法簇內節點互相競爭簇首過多能量開銷，此外改進后算法簇重組及管理的主要能量消耗來自Sink節點，而恰恰該節點的能量不受限制。因此改進后的LEACH-L算法使網絡的能效性得到較大的提升，網絡生命周期有較好的延長。

3 仿真實驗

本文使用NS2離散事件模擬器來構建無線傳感器網絡的模擬環境。仿真實驗中的環境參數配置如下：環境區域為670 m×670 m，網絡節點初始數量20且以20遞增（其中網絡中只有一個Sink節點），網絡節點隨機分布，節點通信傳輸半徑為50 m，采用IEEE 802.15.4MAC層協議。設定節點初始能量為9 J，發送數據包能耗為0.009(J/packet)，接收數據包能耗為0.001 3(J/packet)，傳輸數據包大小為512 bit，發送一個控制幀的能耗為0.000 2(J/frame)，接收一個控制幀的能耗為0.000 08(J/frame)，控制幀大小為10 bit，實驗次數為10次，實驗結果取各項指標的平均值。網絡總的能量消耗情況如圖3所示。

從圖3可以看出，改進后的路由算法(LEACH-L)網絡總的能量消耗優于LEACH算法，剛開始能量消耗與LEACH算法沒有較大的差別，但隨著時間的增加，LEACH-L算法能耗優勢體現出來了，原因是剛開始由于Sink節點要占用時間來為每個簇建立鏈表同時初始狀態的簇首剩余能量還比較大，不會進行簇重組，但是在鏈表建成后和網絡時間的增長，LEACH-L優勢更加明顯，這是因為大部分簇的簇首能量即將耗盡，要進行新的簇首選擇，而本文設計的算法的簇首節點剩余的能量還相對較多，不會馬上進行簇重組，另外簇重組的能耗也小于LEACH算法，并且該算法會隨著時間的增長優越性會體現得更好。網絡的生命周期情況如圖4所示。

從圖4可以看出，當節點數較少時，該算法較優于LEACH算法，但是伴隨著節點數目的增加，當網絡節點數超過80以后，LEACH算法的生命周期急速下降，而LEACH-L受到較大的影響，這是因為過多的網絡節點會造成LEACH算法更大的分簇開銷和網絡通信的復雜度，從而導致網絡節點能量急劇消耗，縮短網絡的生命周期，這也充分驗證了筆者理論所分析的LEACH不適合于大型網絡這一點；而LEACH-L算法由于簇重組的主要開銷來自能量不受限的Sink節點，因此才不會出現以上情況，所以LEACH-L算法適合比較大的網絡。

4 結束語

本文通過能量不受限的Sink節點對WSN中各個簇的鏈表進行管理，選擇剩余能量最大的節點擔任新一輪簇重組的簇首，簇首節點選擇是基于節點最大能量的，而這些操作也都是由能量不受限的Sink節點來完成，所以此過程使簇的簇重組頻率大大減少，節約簇節點不必要的能量消耗，而LEACH算法有很多的能量開銷主要是來自過多的簇重組，改進后的LEACH-L算法，簇首選舉只需要Sink節點來認命，通過控制幀的方式傳遞到原簇首節點，由原簇首節點以廣播的形式告知簇內的各個節點，而這整個過程的能量開銷是相當小的，因此也就意味著整個簇的生命周期可以達到最大化，同時也是該算法比較適合大型網絡的主要原因。

參考文獻：

［1］

宋文，王兵，周應賓.無線傳感器網絡技術與應用[M].北京:電子工業出版社， 2007.

[2]彭靜，劉光祜，謝世歡.無線傳感器網絡路由協議研究現狀與趨勢[J].計算機應用研究，2007，24(2):4-9.

[3]孫勇，景博，張宗麟，等.無線傳感器網絡分簇路由的能量有效性研究[J].計算機工程，2007，33(17):51-52.

[4]任代蓉，雷霖，易勇.無線傳感器網絡的網絡協議與能量問題綜述[J].成都大學學報，2007，26(1):58-62.

［5］LI J，LAZAROU G.A bit map assisted energy efficient MAC scheme for wireless sensor networks[C]//Proc of the 3rd International Symposium on Information Processing in Sensor Networks.Berkeley，California:[s.n.]，2004.

[6]LIU Jun，HONG Xiao-yan.A traffic-aware energy efficient routing protocol for wireless sensor networks[C]//Proc of IEEE International Workshop on Computer Architecture for Machine Perception and Sen-sing.Montreal:[s.n.]，2006:18-20.

[7]CHO S，KANURI K，CHO J，et al.Dynamic energy efficient TDMA-based MAC protocol for wireless sensor networks[C]//Proc of Joint International Conference on Network and Services.2005.

[8]MANJESHWAR A，AGRAWAL D P.TEEN:a routing protocol for enhanced efficiency in wireless sensor networks[C]//Proc of the 15th Parallel and Distributed Processing Symposium.San Francisco: IEEE Computer Society，2001.