古 欣，禹繼國，王光輝

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

0 引言

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

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

1 分簇的目標和優(yōu)勢

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

對于大規(guī)模 WSNs而言，分簇網(wǎng)絡拓撲在拓撲管理、可擴展性和能量效率等方面都具有明顯優(yōu)勢。

1）分簇可將網(wǎng)絡分為多個小規(guī)模的網(wǎng)絡，從而可降低拓撲管理的難度。

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

3）簇內(nèi)引入節(jié)點睡眠機制，簇頭保持喚醒狀態(tài)，成員按調(diào)度向簇頭發(fā)送信息，既不影響網(wǎng)絡連通性又能節(jié)省能量。

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

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

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

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

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

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

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

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

3）根據(jù)簇頭輪轉(zhuǎn)特點可分為時間驅(qū)動型分簇算法和能量驅(qū)動型分簇算法。前者指簇頭按照一定時間周期在全網(wǎng)內(nèi)輪轉(zhuǎn)。后者指當簇頭能量低于預設能量閾值時在局部輪轉(zhuǎn)。

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

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

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

5）根據(jù)簇的大小規(guī)?？煞譃榫鶆蚍执厮惴ê头蔷鶆蚍执厮惴?。均勻分簇算法中簇的大小是均勻的。非均勻分簇算法則通過控制簇的大小來均衡簇頭間能耗。

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

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

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

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

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

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

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

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

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

4 結(jié)語

通過對現(xiàn)有的大量研究成果進行分類總結(jié)。歸納了今后對WSNs研究需關(guān)注的幾方面問題。

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

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

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

6）通過對分簇技術(shù)的應用分析可知分簇的安全性問題、網(wǎng)絡延遲和跨層優(yōu)化[19-20]等方面也是今后研究工作的關(guān)注點。

[1]周新蓮,吳敏,徐建波.無線傳感器中一種能量感知的分布式分簇算法[J].計算機研究與發(fā)展,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]郭強,孫強,李雪,等.無線傳感器網(wǎng)絡LEACH協(xié)議的研究[J].通信技術(shù),2008,41(12): 155-157.

[5]肖劉軍,鄧平.一種基于位置和能量的WSN改進分簇協(xié)議[J].通信技術(shù),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]黃河清,沈杰,姚道遠,等.無線傳感網(wǎng)自適應能量驅(qū)動簇頭輪換算法研究[J].電子與信息學報,2009,5(31):1040-1044.

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

[9]李成法,陳貴海,葉懋,等.一種基于非均勻分簇的無線傳感器網(wǎng)絡路由協(xié)議[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分簇協(xié)議[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]馮家麟,陳永生,楊萍.一種基于簇的分布式路由協(xié)議[J].計算機工程,2010,36(03):89-91.

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

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

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

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

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

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