無線傳感器網絡分簇路由協議綜述﹡

古 欣，禹繼國，王光輝

（①曲阜師范大學 計算機科學學院，山東 日照 276826；②山東大學 數學學院，山東 濟南 250100)

0 引言

在實際應用中無線傳感器網絡（WSN，Wireless Sensor Network）中的大量節點通常能量有限且往往不能再次補充。因此如何合理利用有限能量來延長網絡壽命是路由協議設計面臨的首要問題。分簇被證明是節省能耗和提高網絡壽命的一種基本機制。所謂分簇，就是將節點劃分成許多稱之為簇的組，每個簇都有一個簇頭和許多簇成員[1]。成員將收集到的數據發送給簇頭，簇頭對數據進行融合后直接或者通過其他簇頭發送到基站。

通過分析現有WSNs分簇協議，揭示了分簇算法的本質，并基于分簇算法本身和分簇技術的應用兩方面對這些協議進行了分類和介紹，最后引導了下一步的研究方向。

1 分簇的目標和優勢

分簇的目標往往根據具體的應用而設定，例如文獻[2]中將分簇目標總結為負載均衡、增加連通度、最小化簇數目以及最大化網絡壽命等。

對于大規模 WSNs而言，分簇網絡拓撲在拓撲管理、可擴展性和能量效率等方面都具有明顯優勢。

1）分簇可將網絡分為多個小規模的網絡，從而可降低拓撲管理的難度。

2）較好的可擴展性使分簇更適用于大規模WSN應用場景。

3）簇內引入節點睡眠機制，簇頭保持喚醒狀態，成員按調度向簇頭發送信息，既不影響網絡連通性又能節省能量。

4）簇頭對數據進行融合，降低了數據冗余，減少了數據通信量。

5）只有簇頭參與路由大大減少了路由表尺寸，降低了通信開銷和內存開銷。

2 基于分簇算法的分類及介紹

近年來分簇算法取得了大量優秀的研究成果。按不同方面可將現有分簇算法進行如下分類。

1）根據算法的執行方式可分為集中式分簇和分布式分簇。集中式分簇算法需要掌握網絡全局信息，因此可獲得好的簇頭分布但在大規模網絡中的應用有限。分布式分簇算法中節點根據局部信息獨立分簇，開銷小，更適合大型網絡。

LEACH[3]是最為經典的按輪執行的分布式分簇協議，每輪由簇的建立和數據傳輸兩階段組成。在前一階段,節點生成一個[0,1]之間的隨機數，若此數小于閾值 T(n)則成為簇頭。在后一階段，成員將數據發送給簇頭，簇頭對數據進行融合后直接發送至基站。簇頭角色全網內周期性輪轉。該協議結構簡單且不需要較大通信開銷，然而它在簇頭選舉時未考慮節點剩余能量。學者們針對其提出了一些改進協議，如在簇頭競選時文獻[4]同時考慮了節點剩余能量和距基站距離的。文獻[5]同時考慮了節點位置和剩余能量。

2）根據分簇的層數不同可分為單層分簇和多層分簇。單層分簇將網絡分為兩層，簇頭為高層，成員為低層，所有節點由一層簇頭和歸屬于這些簇頭的成員組成，算法實現簡單，開銷較小。多層分簇中低層簇頭通常作為高層簇頭的成員，因此可進一步降低節點能耗，但實施復雜且開銷較大。

文獻[6]采用自頂向下的方式構造多層分簇拓撲。在簇的建立階段節點以 p1(u)的概率成為第一層簇頭，其他節點成為第一層簇成員。第一層簇頭通知其成員進行第二層簇頭選舉，第一層成員以 p2(u)的概率成為第二層簇頭，剩余節點成為第二層簇成員，依次進行直到簇內節點數小于等于3時停止。數據傳輸階段，T層成員將數據發送到T層簇頭，T層簇頭對數據進行融合后發送至 T-1層簇頭，依此類推，最后由第一層簇頭將數據進行融合后發送給基站。

3）根據簇頭輪轉特點可分為時間驅動型分簇算法和能量驅動型分簇算法。前者指簇頭按照一定時間周期在全網內輪轉。后者指當簇頭能量低于預設能量閾值時在局部輪轉。

文獻[7]中簇頭依據節點剩余能量在簇內選擇備份簇頭，在簇頭能量達到閾值或簇頭意外失效的情況下，備份簇頭迅速代替原簇頭成為新簇頭，并接管大部分原簇成員，無法接入新簇頭的節點選擇加入鄰居簇，從而在局部完成拓撲重建工作。

4）根據簇頭選舉參數可分為以節點 ID、節點度、節點剩余能量和節點相對剩余能量等為簇頭競選參數的分簇算法。

文獻[8]以節點相對剩余能量為簇頭競爭參數。在簇的建立階段每個節點 vj廣播包含自身 ID和剩余能量的E_Msg消息，同時也收到所有鄰居的E_Msg消息。 vj基于此計算自己的相對剩余能量和發送簇頭消息的時刻t，若節點在t之前沒有收到鄰居的簇頭消息，則廣播簇頭消息成為簇頭，否則退出簇頭競爭。

5）根據簇的大小規模可分為均勻分簇算法和非均勻分簇算法。均勻分簇算法中簇的大小是均勻的。非均勻分簇算法則通過控制簇的大小來均衡簇頭間能耗。

文獻[9]中的算法是典型的分布式非均勻分簇算法，每輪開始節點 si以T的概率成為候選簇頭，每個候選簇頭 si根據自身到基站的距離計算它的競爭半徑 Rc。并以 Rc為半徑廣播一條包含自身ID和剩余能量的簇頭競選消息。同時 si根據收到的來自其鄰居的簇頭競選消息定期更新自己的簇頭鄰居集合 si. SCH。如果 si的剩余能量大于 si. SCH中所有節點的剩余能量就廣播一條簇頭消息宣布成為簇頭。

3 基于分簇技術應用的算法分類及簡述

近年來對基于分簇技術設計的算法也取得了不少研究成果?？紤]不同的應用對這類算法進行如下分類。

1）安全分簇。文獻[10]提出了基于秘密共享的CA證書方案和自組織證書方案。文獻[11]中則提出一種基于簇的平面Merkle哈希樹的Sybil攻擊防御機制。

2）覆蓋度。通常算法是先采用分簇的方式將覆蓋區域劃分成許多子區域，然后進行細粒度的網絡監測與覆蓋控制。文獻[12]中利用最大熵原理對整個網絡進行預分簇得到臨時簇頭，在保證網絡覆蓋度的前提下獲取各分簇內活躍節點的連通支配集。

3）連通度?；谶B通度約束的分簇算法可以保證簇頭等骨干節點之間的連通性。文獻[13]是利用分簇技術對網絡進行劃分后在保證網絡連通度的前提下，找出可以達到最大覆蓋度的最少活動節點數。

4）移動模型。針對網絡中由少數節點移動的情況，文獻[14]提出一種基于權值的分布式分簇算法，文獻[15]提出了一個適用于同時包含固定和移動傳感器節點的WSN的移動簇頭通信協議。

5）數據收集。分析對以分簇為基礎的收集融合算法可以減少網絡中的數據傳輸總量，文獻[16]算法提出了一種在分簇路由協議支持下的時間、空間多維度的數據壓縮算法。文獻[17]設計出一種基于分簇結構的混合型數據收集協議。

6）能量補給。已有的分簇路由協議大都是基于節點能量受限設計的，但現有的一些采能技術已經可以為節點提供適量的能量補給。文獻[18]中提出的具有能量補給的分簇路由算法綜合考慮了節點的能量起伏變化以及能量補給水平，修正了現有簇頭選擇機制和非簇頭歸屬機制。

4 結語

通過對現有的大量研究成果進行分類總結。歸納了今后對WSNs研究需關注的幾方面問題。

1）如何在網絡中出現死亡節點的情況下，仍能保持連通性，使全網能正常運行，是一個有待解決的問題。

4）目前對算法研究所采用的網絡模型和能量模型相對過于理想化，與真實網絡有一定的差距。

5）當前研究成果通常是基于二維的網絡模型，實現向三維空間的擴展也是所面臨的問題之一。

6）通過對分簇技術的應用分析可知分簇的安全性問題、網絡延遲和跨層優化[19-20]等方面也是今后研究工作的關注點。

[1]周新蓮,吳敏,徐建波.無線傳感器中一種能量感知的分布式分簇算法[J].計算機研究與發展,2009,46(05):723-730.

[2]ABBASI A A, YOUNIS M. A Survey on Clustering Algorithms for Wireless Sensor Networks[J].Computer Communications,2007:2826-2841.

[3]HEINZELMAN W R, CHANDRAKASAN A. Energy-efficient Communication Protocol for Wireless Microsensor Networks[C]//Proc. of the 33rd Annual Hawaii International Conference on System Sciences.Maui,HI,2000:1-10.

[4]郭強,孫強,李雪,等.無線傳感器網絡LEACH協議的研究[J].通信技術,2008,41(12): 155-157.

[5]肖劉軍,鄧平.一種基于位置和能量的WSN改進分簇協議[J].通信技術,2010,43(08): 43-45.

[6]JIN Y,WANG L,KIM Y,et.al. An Energy-efficient Multi-level Clustering Algorithm for Large-scale Wireless Sensor Networks[J]. Computer Networks,2008:542-562.

[7]黃河清,沈杰,姚道遠,等.無線傳感網自適應能量驅動簇頭輪換算法研究[J].電子與信息學報,2009,5(31):1040-1044.

[8]劉明,曹建農,陳貴海.能量感知的無線傳感器網絡數據收集協議[J].軟件學報,2007,18(05):1092-1109.

[9]李成法,陳貴海,葉懋,等.一種基于非均勻分簇的無線傳感器網絡路由協議[J].計算機學報,2007,30(01):27-36.

[10]CAPKUN S,BUTTYAN L,HUBAUX J P. Self-organized Public-key Management for Mobile ad hoc Network[J]. IEEE Trans. on Mobile Computing,2003,2(01):52-64.

[11]王曉東,孫言強,孟祥旭.WSN中基于簇的Sybil攻擊防御機制[J].計算機工程,2009,35(15):129-134.

[12]馬小飛,繆亮,范媛媛.基于連通覆蓋度的WSN分簇協議[J].計算機工程,2010,36(15):114-116.

[13]MISRA S,KUMAR P M,OBAIDAT S M.Connectivity Preserving Localized Coverage Algorithm for Area Monitoring Using Wireless Sensor Networks.

[14]馮家麟,陳永生,楊萍.一種基于簇的分布式路由協議[J].計算機工程,2010,36(03):89-91.

[15]柴亦飛,高麗強,涂時亮,等.無線傳感器網絡移動簇頭節點節能傳輸協議[J].計算機工程,2008,34(11):114-116.

[16]尹震宇,趙海,徐久強,等.WSN中基于分簇路由的多維度數據壓縮算法研究[J].電子學報,2009(05):1109-1114.

[17]徐建波,李仁發.無線傳感器網絡中一種新型的混合型數據收集協議[J].計算機研究與發展,2008,45(02):254-260.

[18]樊曉平,楊璽,劉少強,等.具有能量補給的無線傳感器網絡分簇路由算法[J].計算機工程,2008,34(11):120-128.

[19]虞莉莉,趙躍華.無線傳感器網絡跨層優化研究[J].通信技術,2008,41(12):.

[20]唐慧,胡向東.無線傳感器網絡數據融合研究綜述[J].信息安全與通信保密,2007(07):62-64,68.