無線傳感器網絡基于多元簇首的分簇數據收集算法

胡升澤 包衛東 王 博 樂 俊 葛 斌

①(國防科學技術大學信息系統工程重點實驗室 長沙 410073)

②(北京信息技術研究所 北京 100094)

③(西南電子電信技術研究所 成都 610041)

1 引言

無線傳感器網絡(Wireless Sensor Networks,WSN)能夠獲取網絡分布區域內的各種環境或監測對象的信息并傳送給用戶，使人們獲得大量詳實而可靠的信息[1,2]。WSN 集成了傳感器、微機電系統和網絡三大技術，在軍事和民用領域都有著廣闊的應用前景[1-4]。數據收集是WSN應用的一項基本工作，分簇數據收集算法具有簡單、靈活、易擴展等特點，是 WSN數據收集算法研究的重點和熱點[5-8]。

在很多WSN應用中，節點容易因為自然條件、電磁環境等原因而失效[9]。在使用分簇數據收集算法收集數據時，如果某個簇首失效，相關簇成員的數據收集就可能受到影響，從而使數據收集的可靠性降低。另外，很多 WSN的節點通常只能配備能量有限的電源，網絡生命周期受限。因此，如何提高數據收集可靠性和延長網絡生命周期，就成為分簇數據收集算法亟待解決的兩個關鍵問題。

LEACH(Low-Energy Adaptive Clustering Hierarchy)[10,11]是一種經典的分簇數據收集算法，之后的很多分簇數據收集算法都是在其基礎上改進得到的[12]。該算法以輪為單位周期性運行，每輪包括設置和穩定兩個階段，前者執行選擇簇首和構建簇的任務，后者完成收集數據的工作。周期性運行機制能夠避免因為某個簇首失效而長時間數據收集。但是，在該算法和很多其它分簇數據收集算法中，每個簇成員只從屬于一個簇首，如果某個簇首失效，其所在簇中所有節點的數據都將無法收集。因此，為了提高數據收集可靠性，就必須降低簇成員對單個簇首的依賴程度。目前，已經有學者進行了相關研究，具有代表性的算法主要有 REED(Robust Energy Efficient Distributed clustering)[13,14],O-LEACH(Overlapping LEACH)[15]和 DED(Distributed, Energy-efficient and Dual-homed clustering)[16]。

REED將網絡虛擬成多層覆蓋網，每層覆蓋網都包括所有節點，每輪分別在各層覆蓋網中選擇簇首和構建簇，從而使每個簇成員都能夠同時從屬于多個簇首。O-LEACH是LEACH的改進版本，在每輪的設置階段，每個普通節點首先選擇接收信號強度最大的簇首作為主簇首，然后，再以主簇首接收信號強度的X%(0＜X≤100)為標準，選擇接受信號強度大于該標準的所有簇首，并加入主簇首和這些簇首所在的簇，從而使每個簇成員都能夠從屬于多個簇首。在收集數據的時候，REED和O-LEACH的各個簇成員都將數據同時發送至多個簇首。DED在分簇完成之后，由每個簇成員從除自己簇首之外的鄰近節點中選擇一個節點作為備份節點，在收集數據的時候，如果某個簇成員自己的簇首失效，則該簇成員可以將數據發送至備份節點。

上述算法都可以提高數據收集的可靠性，但也都存在一定的不足。REED在每層覆蓋網中都分簇，增加了能量開銷。O-LEACH中每個簇成員的簇首數目是不確定的，算法在提高數據收集可靠性方面也具有不確定性。此外，在REED和O-LEACH中，如果某個簇成員的簇首中有多個正常簇首，則這些正常簇首都會收集該簇成員的數據，出現重復收集數據的現象，增加了不必要的能量開銷。而在DED中，如果某個節點的備份節點也是簇成員，在收集的過程中，該節點的數據需要被轉發的次數就會增加，成功收集該節點數據的概率也會隨之降低，所以，該算法能夠提高的數據收集可靠性有限，文獻[16]中的對比實驗結果也表明，在數據收集可靠性方面，DED的性能比REED差。

本文提出基于多元簇首的分簇數據收集算法(Clustering data gathering algorithm based on Multiple Cluster Heads, CMCH)，期望既可以提高數據收集可靠性，又能夠延長網絡生命周期。

2 基礎模型

CMCH的網絡模型設定部署區域是一個邊長為M的正方形區域，基站位于部署區域之外的某個位置，N個節點隨機均勻分布在部署區域內，每個節點都有一個唯一的整型ID，此外，網絡還具有如下性質：(1)基站和節點的位置不變而且位置信息可知；(2)各節點以及基站之間時間同步；(3)節點之間同構；(4)節點的能量有限；(5)節點能夠根據通信距離調整發射功率。

CMCH采用同類算法常用的能耗模型，統計節點發送、接收和融合數據的能耗[11]。節點在發送數據時，如果發送距離小于閾值d0，采用自由空間模型，否則，采用多路徑衰減模型。節點發送和接收長度為lbit數據的能耗計算公式分別為式(1)和式(2)，其中，d是數據發送距離，Ee是無線收發電路發送或接收單位長度數據的電路能耗，εfs和εmp分別是自由空間模型和多路徑衰減模型的放大器能耗參數。

3 CMCH算法介紹

CMCH也按輪周期性運行，每輪包括設置階段和穩定階段，并在首輪之前設有初始化階段。為了避免混淆，首先界定以下幾類節點：存活節點指能量未耗盡的節點，死亡節點指能量已經耗盡的節點，失效節點指能量未耗盡但是無法正常工作的節點，正常節點指能量未耗盡而且可以正常工作的節點。

3.1 初始化階段

不失一般性，假設在2維坐標系中，部署區域的橫邊與橫坐標軸平行，基站位于部署區域沿縱坐標軸的上方，坐標為(BSx,BSy)。將部署區域的左下角頂點作為部署區域的起始點，設其坐標為(Ox,Oy)。

首先，根據節點失效概率確定每個柵格預期的簇首數目K。設節點失效概率為P，則每個柵格中正常簇首的期望數目為(1-P)K。一般情況下，柵格預期簇首數目越大，數據收集可靠性就越高，但是能量開銷也會越多。因此，可以選擇使柵格預期簇首數目不小于1的最小自然數作為K的值，即

根據預期能量消耗和K的值確定柵格劃分的標準，也就是確定柵格的數目G和柵格的邊長B。算法采用固定分簇的方法，所以，簇的數目和柵格的數目相等，也為G。算法采用與文獻[11]類似的方法確定G的最佳取值。假設簇首向基站發送數據時采用多路徑衰減模型，則簇首的能耗為

此外，還應當使每個柵格中預期分布的節點數目不小于柵格預期簇首數目。由于節點隨機均勻分布在部署區域中，每個柵格中預期分布的節點數目為N/G，因此，柵格數目應滿足條件：

在實際應用中，可以根據式(14)和式(15)確定適當的柵格數目。如果無法同時滿足，在側重能耗指標的應用中，應優先滿足式(14)，在側重數據收集可靠性的應用中，應優先滿足式(15)。

柵格的數目為G，則每一行或每一列的柵格的數目均為，可以得到柵格的邊長B為

另外，由于算法在簇成員和簇首之間采用單跳的方式連接，而簇首在柵格中的節點之間輪換，要求柵格中任意兩個節點都能夠實現單跳連接。設節點的最大通信距離為R，則柵格的邊長B還必須滿足：

然后，由基站向所有節點廣播BS_MSG((Ox,Oy), (BSx,BSy),M,K,G,B)消息。最后，各個節點從消息中獲取并保存相關信息，根據自己的位置坐標確定自己屬于哪個柵格。算法用二元組(Gx,Gy)作為柵格ID，其中，Gx是柵格橫標識，Gy是柵格縱標識，規定左下角柵格的ID為(1, 1)，右上角柵格的ID為ID為(Gx,Gy)的柵格的覆蓋范圍為

坐標為(x,y)的節點根據式(20)和式(21)計算所屬柵格的柵格橫標識和柵格縱標識。

3.2 設置階段

初始化階段完成之后，網絡便可以開始按輪運行，每輪首先進入設置階段。在設置階段，每個柵格根據節點的剩余能量分別選擇多個簇首，并由簇首基于時分復用的方式為柵格中的節點分配通信時隙。

首輪中，各個柵格的簇首分別由柵格內的節點協作選出。首先，每個節點通過組播的方式向所屬柵格的其它節點發送節點信息消息，消息中包括節點的ID，坐標，所屬柵格ID和剩余能量。所屬柵格ID為(Gx,Gy)，坐標為(x,y)的節點按照如表1所示的過程，計算與所屬柵格4個頂點距離的最大值dmax，并以此為標準確定消息的傳輸距離。

節點根據接收的其它節點的信息和節點自身的信息，按照剩余能量從大到小，對所有節點進行排序。在排序的過程中，如果出現多個節點剩余能量相同的情況，則按照節點ID從小到大確定它們的順序。然后，選擇排序靠前的K個節點作為柵格的簇首。接著，節點檢查自己是否包括在這些簇首之中，如果是，則節點將自己設置為簇首，否則，節點就將自己設置為簇成員。最后，每個簇首根據排序位置確定自己的優先級，排序越靠前則簇首的優先級越高。

表1 節點計算dmax的過程

簇首選擇完成后，各個簇首為本柵格所有節點分配通信時隙，并通過組播的方式向本柵格的其它節點發送通信時隙消息。通信時隙消息由柵格中的簇首按照優先級的順序發送，如果簇首已經收到本柵格優先級較高簇首發送的通信時隙消息，則該簇首放棄發送通信時隙消息，從而避免重復發送。

將首輪之后的任意一輪稱為非首輪。為了完成非首輪設置階段的工作，在每一輪穩定階段最后一次數據收集時，每個節點將自己的剩余能量等信息通過捎帶的方式附加在數據消息中發送給簇首，簇首也通過捎帶的方式將所收集的節點信息附加在數據消息中發送至基站。在非首輪的設置階段，首先由基站向所有節點廣播其在上一輪最后一次數據收集時所收集的各個柵格的節點信息。如果某些節點在上一輪中失效，則廣播消息中沒有這些節點的信息。因此，節點從廣播消息中獲取和保存本柵格的節點信息后，需要檢查該消息中是否有自己的信息，如果沒有，則節點采取與首輪設置階段相同的方法向所屬柵格的其它節點發送自己的節點信息。這樣，每個節點就能夠收集到所屬柵格其它節點的信息，然后再按照與首輪設置階段相同的方法選擇簇首、確定簇首的優先級、分配通信時隙和發送通信時隙消息。

3.3 穩定階段

穩定階段完成數據收集的工作。首先，包括簇首在內的每個節點在自己的通信時隙內，通過組播的方式向本柵格的簇首發送數據消息。然后，簇首將收集的數據和自己的數據進行融合處理。最后，由簇首向基站發送數據消息。為了避免柵格中多個簇首重復發送消息，各個柵格中的簇首按照優先級的順序向基站發送消息，如果優先級較高的簇首已經發送，則其它簇首不再發送。

如果當前是本輪最后一次數據收集，每個節點將自己的剩余能量等信息通過捎帶的方式附加在數據消息中發送至簇首，簇首也通過捎帶的方式將收集的節點信息附加在數據消息中發送至基站。

4 CMCH算法分析

在數據收集可靠性方面，CMCH使簇成員同時從屬于多個簇首，各個簇首也從屬于所屬柵格的其它簇首。只要柵格中還有正常簇首，則該簇首就可以收集柵格中所有正常節點的數據，從而完成該柵格的數據收集任務。因此，算法能夠有效降低簇成員對單個簇首的依賴，可以提高數據收集可靠性。

在網絡生命周期方面，CMCH采取了一系列降低能量開銷的措施，提高了能量使用效率，能夠延長網絡的生命周期。首先，算法采用固定分簇方法，每輪只需要重新選擇簇首，降低了分簇過程中的能耗。其次，算法采用捎帶的方式將選擇簇首所需的節點信息附加在數據消息中傳輸，并由基站廣播節點信息，降低了選擇簇首所需的能耗。再次，各個柵格中的簇首根據優先級向節點發送通信時隙消息和向基站發送數據消息，能夠避免重復發送，從而可以節約能量。最后，算法將消息的發送距離和接收節點限定在適當的范圍之內，也能夠降低能量開銷。

5 仿真實驗

本文在 MATLAB平臺上進行仿真實驗，并將CMCH與REED和O-LEACH進行對比。實驗中，節點總數為400，每個節點的初始能量都為0.5 J，控制消息和數據消息的長度分別為800 bit和1600 bit，其它實驗參數如表2所示。根據式(14)可以確定CMCH最佳柵格數目的范圍為1.93

表2 實驗參數

表3 P以及相應的K和N/K的值

在所有節點失效概率下都滿足式(14)和式(15)，而且可以作為柵格數目的選項有4, 9, 16, 25和36，各選項下的柵格邊長均滿足式(17)。本文將CMCH柵格數目設置為大小適中的16，將REED每層覆蓋網每輪預期選擇簇首數目以及O-LEACH每輪預期選擇簇首數目也都設置為16，另外，REED覆蓋網為K層，O-LEACH的參數X設置為50。

首先，通過仿真實驗對比各個算法的數據收集可靠性。將因為簇首失效而無法對其數據進行收集的有效節點稱為連帶失效節點。那么，在節點失效概率相等的情況下，算法的連帶失效節點越少，就表明算法具有更高的數據收集可靠性。統計仿真實驗中各個算法在出現死亡節點之前每輪連帶失效節點的平均數，如圖1所示?？梢钥闯?，CMCH的連帶失效節點平均數都少于 REED，表明 CMCH的數據收集可靠性高于 REED。在大多數情況下，CMCH的連帶失效節點平均數也都少于 OLEACH，因此，從總體上看，CMCH在數據收集可靠性方面的性能也優于O-LEACH。

接著，比較各個算法在網絡生命周期方面的性能。以網絡開始運行到出現第1個死亡節點前所經歷的輪數作為網絡生命周期，仿真實驗中，3種算法的網絡生命周期如圖 2所示。在相同條件下，CMCH的網絡生命周期都要遠遠長于O-LEACH和REED，證明CMCH能夠顯著延長網絡生命周期。

最后，通過仿真實驗考察柵格數目G對CMCH性能的影響。在G的取值分別為4, 9, 16, 25和36的情況下，CMCH的連帶失效節點平均數和網絡生命周期分別如圖3和圖4所示?？傮w上看，在數據收集可靠性方面，柵格數目越多，算法的性能越好，而在網絡生命周期方面，隨著柵格數目由少到多，算法的性能呈現先升后降的態勢。

圖1 各算法的連帶失效節點平均數

圖2 各算法的網絡生命周期

圖3 不同柵格數目的連帶失效節點平均數

圖4 不同柵格數目的網絡生命周期

6 結束語

提高數據收集可靠性和延長網絡生命周期是分簇數據收集算法亟待解決的兩個關鍵問題。為了解決上述問題，本文提出了CMCH算法。仿真實驗結果表明，與現有的REED和O-LEACH算法相比，該算法具有較高的數據收集可靠性，并顯著延長了網絡的生命周期。下一步工作將研究如何應對柵格中全部簇首節點都失效的情況，以及簇首采用多跳方式向基站發送數據的應用，并放寬算法的前提條件，以擴展算法的適用范圍，還將對算法的時延性能進行分析和考察。

[1] 李建中, 高宏. 無線傳感器網絡的研究進展[J]. 計算機研究與發展, 2008, 45(1): 1-15.Li Jian-zhong and Gao Hong. Survey on sensor network research[J].Journal of Computer Research and Development,2008, 45(1): 1-15.

[2] Liu W, Chen H, and Chen M. A survey of wireless sensor networks[C]. Proceedings of the World Automation Congress,Puerto Vallarta, Mexico, 2012: 305-307.

[3] 任豐原, 黃海寧, 林闖. 無線傳感器網絡[J]. 軟件學報, 2003,14(7): 1282-1291.Ren Feng-yuan, Huang Hai-ning, and Lin Chuang. Wireless sensor networks[J].Journal of Software, 2003, 14(7):1282-1291.

[4] Sakthidharan G R and Chitra S. A survey on wireless sensor network: an application perspective[C]. Proceedings of the International Conference on Computer Communication and Informatics, Coimbatore, India, 2012: 1-5.

[5] Abbasi A A and Younis M. A survey on clustering algorithms for wireless sensor networks[J].Computer Communications,2007, 30(14/15): 2826-2841.

[6] Boyinbode O, Le H, Mbogho A,et al.. A survey on clustering algorithms for wireless sensor networks[C]. Proceedings of the International Conference on Network-Based Information Systems, Gifu, Japan, 2010: 358-364.

[7] Kumar V, Jain S, and Tiwari S. Energy efficient clustering algorithms in wireless sensor networks: a survey[J].International Journal of Computer Science Issues, 2011, 8(5):259-268.

[8] Tuah N, Ismail M, and Jumari K. An energy-efficient node-clustering algorithm in heterogeneous wireless sensor networks: a survey[J].Journal of Applied Sciences, 2012,12(13): 1332-1344.

[9] Yick J, Mukherjee B, and Ghosal D. Wireless sensor network survey[J].Computer Networks, 2008, 52(12): 2292-2330.

[10] Heinzelman W, Chandrakasan A, and Balakrishnan H.Energy-efficient communication protocol for wireless microsensor networks[C]. Proceedings of the International Conference on System Sciences. Hawaii, USA, 2000:3005-3014.

[11] Heinzelman W, Chandrakasan A, and Balakrishnan H. An application-specific protocol architecture for wireless microsensor networks[J].IEEE Transactions on Wireless Communications, 2002, 1(4): 660-670.

[12] Aslam M, Javaid N, Rahim A,et al.. Survey of extended LEACH-based clustering routing protocols for wireless sensor networks[C]. Proceedings of the International Conference on High Performance Computing and Communications,Liverpool, United Kingdom, 2012: 1232-1238.

[13] Younis O, Fahmy S, and Santi P. Robust communications for sensor networks in hostile environments[C]. Proceedings of the International Workshop on Quality of Service, Montreal,Canada, 2004: 10-19.

[14] Younis O, Fahmy S, and Santi P. An architecture for robust sensor network communications[J].International Journal of Distributed Sensor Networks, 2005, 1(3-5): 305-327.

[15] Suharjono A, Wirawan, and Hendrantoro G. Dynamic overlapping clustering algorithm for wireless sensor networks[C]. Proceedings of the International Conference on Electrical Engineering and Informatics, Bandung, Indonesia,2011: 1-6.

[16] Mohammad M H and Jason P J. Survivable self-organization for prolonged lifetime in wireless sensor networks[J].International Journal of Distributed Sensor Networks, 2011,2011(1): 1-11.