無線傳感器網(wǎng)絡(luò)中分簇算法綜述

何梟宇 姚彥鑫

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

關(guān)鍵詞： 無線傳感器網(wǎng)絡(luò)； 分簇算法； 能耗均衡； 網(wǎng)絡(luò)生命周期； 簇首選擇機(jī)制

中圖分類號(hào)：TN92 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：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 引言

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，即WSN）是由很多廉價(jià)的并具有傳感、計(jì)算、數(shù)據(jù)處理和通信能力的微型傳感器節(jié)點(diǎn)組成的網(wǎng)絡(luò)。WSN無論在任何條件下都能夠通過節(jié)點(diǎn)間的通信，來完成對(duì)所需信息的采集和處理工作，逐漸廣泛應(yīng)用于需要進(jìn)行感知監(jiān)測(cè)的各領(lǐng)域，如軍事領(lǐng)域、工業(yè)領(lǐng)域和環(huán)境領(lǐng)域等。

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

2 典型的分簇算法

本章節(jié)按照在分簇過程中簇頭的選取是否隨機(jī)，將分簇算法歸結(jié)為兩大類，其中第一類隨機(jī)選取簇頭的分簇方法主要包括LEACH（Low-Energy Adaptive Clustering Hierarchy）[1-5]和TEEN（Threshold sensitive Energy Efficient sensor Network protocol）[6-8]算法，另一類根據(jù)節(jié)點(diǎn)信息選取簇頭的分簇方法主要包括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 隨機(jī)選取簇頭的分簇方法

WSN的分簇算法中，LEACH 和TEEN算法是較為傳統(tǒng)的分簇算法。兩種方法在選擇簇頭的過程中都是節(jié)點(diǎn)隨機(jī)生成0-1的隨機(jī)數(shù)，只要該值大于閾值就可以被選為簇頭，設(shè)定值是根據(jù)簇頭被選擇的幾率和網(wǎng)絡(luò)在此刻運(yùn)行的輪數(shù)計(jì)算出來的。

LEACH中，在簇開始成立的階段，每個(gè)節(jié)點(diǎn)根據(jù)系統(tǒng)給節(jié)點(diǎn)分配的隨機(jī)數(shù)和閾值的大小關(guān)系來判斷自己是否能夠成為簇頭；接著，每個(gè)節(jié)點(diǎn)在收到簇頭信息的同時(shí)，依據(jù)這個(gè)信號(hào)的強(qiáng)度來判斷被選入到哪個(gè)簇，而且每經(jīng)過一段時(shí)間網(wǎng)絡(luò)便會(huì)重復(fù)以上過程。在數(shù)據(jù)傳輸階段，簇內(nèi)節(jié)點(diǎn)按照時(shí)分復(fù)用（TDMA）方式向簇頭發(fā)送信息。

TEEN與LEACH十分類似，兩者的不同之處在于數(shù)據(jù)傳送階段，TEEN中有硬、軟閾值，通過合理的調(diào)節(jié)這對(duì)值的大小可以降低系統(tǒng)能耗。

隨機(jī)選取簇頭方法的缺點(diǎn)為簇頭的選擇完全是不確定的，選取的簇頭不一定最為合適，因?yàn)闆]有考慮到節(jié)點(diǎn)自身的信息，同時(shí)，所選數(shù)量也很有可能不適合這個(gè)網(wǎng)絡(luò)。相比這兩種經(jīng)典的算法，下面我們將介紹的幾種在簇頭選擇時(shí)考慮節(jié)點(diǎn)的能量值和位置信息等因素的算法。

2.2 根據(jù)節(jié)點(diǎn)信息選取簇頭的分簇方法

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

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

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

2016年提出的DCEM分簇多跳路由算法相比經(jīng)典分簇路由算法，在能量損耗，生存節(jié)點(diǎn)等指標(biāo)有所提高。下一章節(jié)將對(duì)DCEM算法中的分簇過程進(jìn)行具體說明。

3 DCEM算法中的分簇方法

分析發(fā)現(xiàn)：按照上述過程會(huì)使得能量大的節(jié)點(diǎn)先發(fā)出信息，能量小的節(jié)點(diǎn)接收到能量大的節(jié)點(diǎn)信息后會(huì)自動(dòng)變?yōu)槠浯貎?nèi)節(jié)點(diǎn)。（4）變成備選的簇頭節(jié)點(diǎn)有兩種情況，一種是節(jié)點(diǎn)向外廣播了ADV信息，但并未收到其他節(jié)點(diǎn)的ADV信息，則該節(jié)點(diǎn)成為簇頭備選節(jié)點(diǎn)；另一種則是節(jié)點(diǎn)向外廣播了ADV信息，雖然收到其他節(jié)點(diǎn)的ADV信息，但是自身能量更高，該節(jié)點(diǎn)也成為簇頭備選節(jié)點(diǎn)。（5）有一種情況需要特別處理，即當(dāng)兩個(gè)簇頭備選節(jié)點(diǎn)能量大小一樣，并且可以通信，那么每個(gè)備選簇頭節(jié)點(diǎn)需要經(jīng)過等待時(shí)間后收到最終簇頭節(jié)點(diǎn)發(fā)送的信息，然后簇頭備選節(jié)點(diǎn)取消其計(jì)時(shí)器，成為當(dāng)前輪的簇內(nèi)節(jié)點(diǎn)。

DCEM算法在分簇的過程中，能量較大的簇頭節(jié)點(diǎn)形成相對(duì)較大的簇，反之形成較小的簇，充分發(fā)揮了節(jié)點(diǎn)的能量?jī)?yōu)勢(shì)，使得能量得到合理的利用。同時(shí)，相比其他算法由于考慮到了簇相交部分節(jié)點(diǎn)的歸屬問題，使得節(jié)點(diǎn)的歸屬更加明確，劃分更加合理。

4 結(jié)論

無線傳感器網(wǎng)絡(luò)在我們生活中起到了不可或缺的作用，逐漸廣泛應(yīng)用于需要進(jìn)行感知監(jiān)測(cè)的各領(lǐng)域，如軍事領(lǐng)域、工業(yè)領(lǐng)域和環(huán)境領(lǐng)域等，給人們生活帶來方便的同時(shí)也給技術(shù)帶來了挑戰(zhàn)。其中的分簇算法引起了學(xué)術(shù)界的極大關(guān)注，文章通過總結(jié)WSN中的主要分簇算法，并對(duì)常見的相關(guān)算法進(jìn)行了歸納和比較，為今后對(duì)分簇算法的研究打下了基礎(chǔ)。希望在不久的將來，可以提出更完善的分簇算法并應(yīng)用到實(shí)際生活中。

參考文獻(xiàn)：

[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] 任智，姚玉坤，曹建玲.無線自組織網(wǎng)絡(luò)路由協(xié)議及應(yīng)用[M].北京：電子工業(yè)出版社，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] 楊彩霞. 基于無線傳感器網(wǎng)絡(luò)的集中式分簇算法研究[D]. 蘭州交通大學(xué)， 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] 蔣暢江. 能量均衡的無線傳感器網(wǎng)絡(luò)非均勻分簇路由協(xié)議[J]. 軟件學(xué)報(bào)， 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.

【通聯(lián)編輯：代影】