無線傳感器網絡中分簇算法綜述

何梟宇 姚彥鑫

摘要：在無線傳感器網絡領域中分簇算法是十分典型的算法，并在其中起著非常重要的作用。文章從能量消耗和網絡生命周期的角度出發，根據在成簇時是否隨機選擇簇頭，將分簇方法分為兩大類。隨后，文章列舉了當前常見的分簇算法，并以近年來出現DCEM（Delay-Constrained Energy-Efficient Cluster-based Multi-Hop Routing）算法為例，詳細描述了其分簇過程，該方法相對于其他方法降低了網絡能量損耗，同時延長了網絡生命周期。最后，結合現階段該領域的科研現狀，展望了這一研究方向在未來的發展趨勢。

關鍵詞： 無線傳感器網絡； 分簇算法； 能耗均衡； 網絡生命周期； 簇首選擇機制

中圖分類號：TN92 文獻標識碼：A

文章編號：1009-3044（2019）09-0028-03

Abstract：Clustering algorithms are very typical algorithms in the field of wireless sensor networks and play an important role in them. From the perspective of energy consumption and network life cycle， the paper divides the clustering method into two categories according to whether cluster heads are randomly selected at the time of clustering. Subsequently， the article lists the current common clustering algorithm， and takes the DCEM （Delay-Constrained Energy-Efficient Cluster-based Multi-Hop Routing） algorithm in recent years as an example to describe its clustering process in detail. Other methods reduce network energy consumption while extending the network life cycle. Finally， combined with the current research status in this field， the future development trend of this research direction is forecasted.

Key words：wireless sensor network； clustering algorithm； balanced energy consumption； network life cycle； cluster head selection mechanism

1 引言

無線傳感器網絡（Wireless Sensor Network，即WSN）是由很多廉價的并具有傳感、計算、數據處理和通信能力的微型傳感器節點組成的網絡。WSN無論在任何條件下都能夠通過節點間的通信，來完成對所需信息的采集和處理工作，逐漸廣泛應用于需要進行感知監測的各領域，如軍事領域、工業領域和環境領域等。

在WSN中如果每一個節點都單獨進行數據傳送，這樣就會導致網絡中數據過于龐大，而且還會發生信息碰撞，從而使能量無端地被浪費掉。為了避免這種情況的發生，節點被分為很多小的集合，稱為簇，這個把單個節點集合成群的過程稱為分簇。這種思想首次被提出是在分組無線網中，每個簇內需要選舉出一個簇頭（Cluster head），它是用來采集本簇中其他節點的信息的，匯總后發送到匯聚節點（sink）或基站（BS），簇內除了簇頭的其他節點被稱為成員節點（Cluster menber），如圖1所示。文章將WSN中的分簇算法按照選取簇頭時是否隨機選取分為兩大類，并對這兩類算法進行了總結，在此基礎上具體描述了近年來新出現的DCEM算法中的分簇方法。

2 典型的分簇算法

本章節按照在分簇過程中簇頭的選取是否隨機，將分簇算法歸結為兩大類，其中第一類隨機選取簇頭的分簇方法主要包括LEACH（Low-Energy Adaptive Clustering Hierarchy）[1-5]和TEEN（Threshold sensitive Energy Efficient sensor Network protocol）[6-8]算法，另一類根據節點信息選取簇頭的分簇方法主要包括HEED（Hybrid Energy Efficient Distributed Clustering） [9-10]、EEUC（Energy Efficient Unequal Clustering）[11-14]、UCFIA（Unequal Clustering Algorithm for WSN based on Fuzzy Logic and Improved ACO）[15] 和近年來提出的DCEM[16]算法。

2.1 隨機選取簇頭的分簇方法

WSN的分簇算法中，LEACH 和TEEN算法是較為傳統的分簇算法。兩種方法在選擇簇頭的過程中都是節點隨機生成0-1的隨機數，只要該值大于閾值就可以被選為簇頭，設定值是根據簇頭被選擇的幾率和網絡在此刻運行的輪數計算出來的。

LEACH中，在簇開始成立的階段，每個節點根據系統給節點分配的隨機數和閾值的大小關系來判斷自己是否能夠成為簇頭；接著，每個節點在收到簇頭信息的同時，依據這個信號的強度來判斷被選入到哪個簇，而且每經過一段時間網絡便會重復以上過程。在數據傳輸階段，簇內節點按照時分復用（TDMA）方式向簇頭發送信息。

TEEN與LEACH十分類似，兩者的不同之處在于數據傳送階段，TEEN中有硬、軟閾值，通過合理的調節這對值的大小可以降低系統能耗。

隨機選取簇頭方法的缺點為簇頭的選擇完全是不確定的，選取的簇頭不一定最為合適，因為沒有考慮到節點自身的信息，同時，所選數量也很有可能不適合這個網絡。相比這兩種經典的算法，下面我們將介紹的幾種在簇頭選擇時考慮節點的能量值和位置信息等因素的算法。

2.2 根據節點信息選取簇頭的分簇方法

HEED 算法分簇時，節點歸屬于哪個簇是根據它自身接收到的簇頭信息中攜帶的AMRP（Average Minimum Reachability Power）平均最小可達能量來進行判斷的，一個節點同時入選兩個或者多個簇的情況則可以避免。如果一個節點沒有接收到任何一個簇頭的信息，它便被判斷為“孤立節點”從而自成一簇，這種方法會導致網絡穩定性不好，原因是沒有把鄰居節點到簇頭節點的距離考慮進去，這樣形成的簇很不均勻，在出現大簇的同時還會出現一些孤立節點，使得的某些節點生命周期變短，從而導致網絡不穩定。HEED算法是依據節點的剩余能量，進行多次迭代來選擇簇頭，這就導致了在這個過程中能量消耗的代價過大。

EEUC算法分簇時，采用大小不同的競爭簇半徑，使得與Sink節點距離小的節點成簇半徑較小，這樣節點可節省一部分能量從而有更多的能量去幫助轉發數據。由于簇半徑有差異，網絡被分成多個不均勻的簇。數據傳輸過程中，該算法分為單跳和多跳情況，若簇頭到 Sink節點的距離小于預先設定的最大值，則以單跳的方式完成簇頭與Sink節點的信息交換；否則采用多跳方式，其中在挑選下一跳節點時，若有比自身到Sink距離更近的多個簇頭，挑選本輪次擁有能量相對多的作為下一跳。該算法的優點是距Sink節點較近的簇較小，反之較大，這種非均勻成簇的方式很大程度上緩解了一些節點過度使用的問題，但是由于數據傳輸階段，未將簇規模和其參與轉發次數考慮進來，還是沒有盡可能地到達網絡能耗的均衡。

UCFIA算法在分簇時利用包括節點剩余能量，與Sink節點的距離等信息，來判斷試探性簇頭成為簇頭的可能性及其成簇半徑，采用模糊邏輯模塊來處理選擇簇首和確定簇大小的不確定性。在傳輸數據的過程中，使用自適應最大—最小蟻群優化算法來找到從簇頭到Sink節點的最高效路徑，并且在這個過程中考慮了簇間流量的特征來平衡簇頭能耗。該算法中的許多參數，比如最大局部密度、最大競爭半徑等還可以進一步進行優化，以提高網絡的性能。

2016年提出的DCEM分簇多跳路由算法相比經典分簇路由算法，在能量損耗，生存節點等指標有所提高。下一章節將對DCEM算法中的分簇過程進行具體說明。

3 DCEM算法中的分簇方法

分析發現：按照上述過程會使得能量大的節點先發出信息，能量小的節點接收到能量大的節點信息后會自動變為其簇內節點。（4）變成備選的簇頭節點有兩種情況，一種是節點向外廣播了ADV信息，但并未收到其他節點的ADV信息，則該節點成為簇頭備選節點；另一種則是節點向外廣播了ADV信息，雖然收到其他節點的ADV信息，但是自身能量更高，該節點也成為簇頭備選節點。（5）有一種情況需要特別處理，即當兩個簇頭備選節點能量大小一樣，并且可以通信，那么每個備選簇頭節點需要經過等待時間后收到最終簇頭節點發送的信息，然后簇頭備選節點取消其計時器，成為當前輪的簇內節點。

DCEM算法在分簇的過程中，能量較大的簇頭節點形成相對較大的簇，反之形成較小的簇，充分發揮了節點的能量優勢，使得能量得到合理的利用。同時，相比其他算法由于考慮到了簇相交部分節點的歸屬問題，使得節點的歸屬更加明確，劃分更加合理。

4 結論

無線傳感器網絡在我們生活中起到了不可或缺的作用，逐漸廣泛應用于需要進行感知監測的各領域，如軍事領域、工業領域和環境領域等，給人們生活帶來方便的同時也給技術帶來了挑戰。其中的分簇算法引起了學術界的極大關注，文章通過總結WSN中的主要分簇算法，并對常見的相關算法進行了歸納和比較，為今后對分簇算法的研究打下了基礎。希望在不久的將來，可以提出更完善的分簇算法并應用到實際生活中。

參考文獻：

[1] Huynh T T， Dinh-Duc A V， Tran C H. Delay-constrained energy-efficient cluster-based multi-hop routing in wireless sensor networks[J]. Journal of Communications & Networks， 2016， 18（4）：580-588.

[2] Kaur J， Sahni V. Survey on Hierarchical Cluster Routing Protocols of WSN[J]. International Journal of Computer Applications， 2015， 130（17）：18-22.

[3] Yadav S， Yadav R S. A review on energy efficient protocols in wireless sensor networks[J]. Wireless Networks， 2015， 22（1）：1-16.

[4] 任智，姚玉坤，曹建玲.無線自組織網絡路由協議及應用[M].北京：電子工業出版社，2015：82-83.

[5] Yang L， Lu Y Z， Zhong Y C， et al. A hybrid， game theory based， and distributed clustering protocol for wireless sensor networks[J]. Wireless Networks， 2016， 22（3）：1007-1021.

[6] Rao P C S， Jana P K， Banka H. A particle swarm optimization based energy efficient cluster head selection algorithm for wireless sensor networks[J]. Wireless Networks， 2017， 23（7）：2005-2020.

[7] Manjeshwar A， Agrawal D P. TEEN： A Routing Protocol for Enhanced Efficiency in Wireless Sensor Networks[C]. Parallel and Distributed Processing Symposium. Proceedings， International. IEEE， 2002：189.

[8] Manjeshwar A， Agrawal D P. APTEEN： a hybrid protocol for efficient routing and comprehensive information retrieval in wireless[C]. Parallel and Distributed Processing Symposium. Proceedings International， IPDPS 2002， Abstracts and CD-ROM. IEEE， 2002：8 pp.

[9] 楊彩霞. 基于無線傳感器網絡的集中式分簇算法研究[D]. 蘭州交通大學， 2016.

[10] Younis O， Fahmy S. HEED： A Hybrid， Energy-Efficient， Distributed Clustering Approach for Ad Hoc Sensor Networks[J]. IEEE Transactions on Mobile Computing， 2004， 3（4）：366-379.

[11] Krishnamoorthy S. Enhanced Adaptive Clustering Mechanism for Effective Cluster Formation in WSN[J]. Social Science Electronic Publishing， 2017.

[12] Li C， Ye M， Chen G， et al. An energy-efficient unequal clustering mechanism for wireless sensor networks[C]. IEEE International Conference on Mobile Adhoc and Sensor Systems Conference. IEEE， 2005：8 pp.-604.

[13] Lv Y， Miao Z， Zhang D， et al. A Low Energy Uneven Clustering Topology Control Algorithm for Wireless Networks[C]. International Conference on Information Science and Control Engineering. IEEE， 2016：1203-1207.

[14] Jiang C， Ren Y， Zhou Y， et al. Low-Energy Consumption Uneven Clustering Routing Protocol for Wireless Sensor Networks[C]. International Conference on Intelligent Human-Machine Systems and Cybernetics. IEEE， 2016.

[15] 蔣暢江. 能量均衡的無線傳感器網絡非均勻分簇路由協議[J]. 軟件學報， 2012， 34（5）：1222-1232.

[16] Song M. Unequal clustering algorithm for WSN based on fuzzy logic and improved ACO[J]. The Journal of China Universities of Posts and Telecommunications， 2011， 18（6）：89-97.

【通聯編輯：代影】