基于雙機熱備機制的一種簇頭選舉算法

宋玉滔，張建明

（江蘇大學 計算機科學與通信工程學院 江蘇 鎮(zhèn)江 212013）

物聯(lián)網(wǎng)感知節(jié)點是由部署在監(jiān)測區(qū)域中大量的手持設(shè)備、車載設(shè)備等節(jié)點構(gòu)成，通過無線通信方式形成的一個多跳自組織網(wǎng)絡(luò)系統(tǒng)。首先，這些節(jié)點分布區(qū)域廣、本身能量受限，使感知節(jié)點的計算、通信、存儲能力非常有限，無法自主實現(xiàn)完善的安全防護，且節(jié)點群數(shù)目龐大不易管理控制，易有疏漏。第二，節(jié)點的移動性使網(wǎng)絡(luò)拓撲結(jié)構(gòu)頻繁變化，將面臨路徑破損、網(wǎng)絡(luò)生存時間縮短的問題，最終導致網(wǎng)絡(luò)簇頭節(jié)點容易出現(xiàn)無法有效處理數(shù)據(jù)或者死亡的現(xiàn)象，這將影響整個網(wǎng)絡(luò)的可靠性[1]。因此，設(shè)計一種基于可靠性的簇頭選舉機制來減少或者避免此類情況的發(fā)生成為影響整個網(wǎng)絡(luò)系統(tǒng)可靠性的核心問題。

為了降低通信能耗、提高網(wǎng)絡(luò)的可擴展性往往選舉一些具備高能量和計算能力的網(wǎng)絡(luò)節(jié)點為簇頭節(jié)點：Ghiasi 等人提出了一種能量有效的優(yōu)化成簇方法[2]，該方法使得每個簇中最多只有一個簇頭節(jié)點。林海等人提出一種利用能量預(yù)測的分簇算法[3]，每個節(jié)點根據(jù)能量預(yù)測模型預(yù)測下一周期自己的剩余能量，并得出閾值，根據(jù)該閾值決定是否當選為簇頭節(jié)點。為了使簇負載均衡且能量消耗小，Yu 等人提出了一種能量有效的動態(tài)分簇技術(shù)以最大化網(wǎng)絡(luò)生存周期[4]。每個節(jié)點根據(jù)鄰居節(jié)點信息計算自身成為簇頭節(jié)點的概率。Qin等人研究了簇頭選舉策略，提出一種基于投票的分簇算法[5]。這些研究以及應(yīng)用都是從如何選舉出高性能的簇頭為出發(fā)點，而未考慮簇頭的工作狀態(tài)問題。一旦簇頭節(jié)點出現(xiàn)無法有效處理數(shù)據(jù)或者死亡的現(xiàn)象，造成網(wǎng)絡(luò)通信中斷，將嚴重影響網(wǎng)絡(luò)的可靠性和穩(wěn)定性。為了解決這一問題本文提出一種基于簇頭熱備機制的簇頭算法（Election of Cluster Head Mechanism of Based on Hot Standby，EHS）。該算法在傳統(tǒng)簇頭選舉算法中引入熱備機制，在選舉出高性能的簇頭節(jié)點的基礎(chǔ)上，充分考慮節(jié)點的工作狀態(tài)，在保證網(wǎng)絡(luò)連通性的同時有效地提高了系統(tǒng)的可靠性。

1 雙機熱備機制

雙機熱備就是對于重要的服務(wù)，使用兩臺服務(wù)器（s1，s2）共同執(zhí)行同一操作。當一臺服務(wù)器出現(xiàn)故障時，可以由另一臺服務(wù)器承擔服務(wù)任務(wù)，從而在不需要人工干預(yù)的情況下，自動保證系統(tǒng)能持續(xù)提供服務(wù)[6]。根據(jù)兩臺服務(wù)器工作方式的不同可將雙機熱備分成三種不同的工作模式：主備模式、互備模式、雙工模式。

1）主備模式是中小系統(tǒng)最常用的模式[7]，是指一臺服務(wù)器A 處于某種業(yè)務(wù)的激活狀態(tài)（即Active 狀態(tài)），另一臺服務(wù)器B 處于該業(yè)務(wù)的備用狀態(tài)（即Standby 狀態(tài)）。當A 發(fā)生故障，B 會立即激活接管A 的業(yè)務(wù)。

2）互備模式是在雙機熱備的基礎(chǔ)上，兩個相對獨立的業(yè)務(wù)在兩臺機器上同時運行，但彼此設(shè)為備機，當某一臺服務(wù)器出現(xiàn)故障時，另一臺服務(wù)器可以在短時間內(nèi)將故障服務(wù)器的業(yè)務(wù)接管過來，從而保證了應(yīng)用的持續(xù)性。

3）雙工模式是兩臺服務(wù)器均為活動，同時接管相同的業(yè)務(wù)，保證整體的性能，也實現(xiàn)了負載均衡和互為備份。

熱備機制常被用于計算機服務(wù)器等一些大型系統(tǒng)中，有效的熱備機制可以有效防止了系統(tǒng)崩潰給企業(yè)帶來的巨大損失，提高系統(tǒng)的穩(wěn)定性、可靠性和容錯能力。但是熱備機制還沒有被用于簇頭選舉算法中，熱備機制在影響簇頭節(jié)點性能方面的研究是一個應(yīng)該被考慮的方向。

2 基于雙機熱備機制的簇頭選舉算法

由于網(wǎng)絡(luò)節(jié)點本身能量有限，如果采用互備模式和雙工模式，兩個簇頭節(jié)點同時處于運行狀態(tài)將會消耗簇頭過多的能量，當一個簇頭節(jié)點出現(xiàn)故障時，另一個簇頭節(jié)點無法確保有充足的能量保證業(yè)務(wù)的正常運行所以相對于其它模式而言，在提高網(wǎng)絡(luò)冗余度和提高網(wǎng)絡(luò)可靠性方面主備模式在進行適應(yīng)簇頭熱備時更具優(yōu)勢?；跓醾錂C制的簇頭選舉算法就是將常用于計算機服務(wù)器等一些大型系統(tǒng)中的熱備機制與傳統(tǒng)的簇頭選舉算法相結(jié)合，將傳統(tǒng)的單簇頭工作模式提升至雙簇頭主備工作模式。通過主備簇頭的合作和適時切換提高簇頭的可靠性進而提升整個網(wǎng)絡(luò)的可靠性和穩(wěn)定性。

2.1 網(wǎng)絡(luò)模型

在物聯(lián)網(wǎng)網(wǎng)絡(luò)中，感知層中的感知技術(shù)是物聯(lián)網(wǎng)的基礎(chǔ)，負責數(shù)據(jù)的采集和對外部世界的感知和識別。傳感技術(shù)主要是利用傳感器和由它們組成的網(wǎng)絡(luò)，通過各種節(jié)點采集被感知對象的信息，節(jié)點獲取的信息通過簇頭節(jié)點經(jīng)過一跳或者多跳路由傳送給sink 節(jié)點，然后由sink 節(jié)點通過傳輸層中的互聯(lián)網(wǎng)、衛(wèi)星或者無線通信網(wǎng)絡(luò)將數(shù)據(jù)發(fā)送給服務(wù)器，進行數(shù)據(jù)的應(yīng)用，如圖1 所示。

圖1 熱備模式數(shù)據(jù)傳輸模型Fig.1 Model of data transmission based-on hot standby

在物聯(lián)網(wǎng)感知層網(wǎng)絡(luò)中假設(shè)網(wǎng)絡(luò)有以下特征：

1）假定有一個可靠的鏈路層協(xié)議，為了防止單點故障，簇一旦形成，所有節(jié)點通過一個共享的雙向無線信道進行通信；

2）首選簇頭是自己推選出來的，允許在第一輪設(shè)置簇頭節(jié)點時采取自薦方式，并假設(shè)這個階段沒有低性能節(jié)點，簇頭節(jié)點的職能為數(shù)據(jù)融合向sink 節(jié)點傳送數(shù)據(jù)并且存儲各節(jié)點發(fā)向簇頭節(jié)點的信息和選舉信息；

3）服務(wù)簇頭節(jié)點存儲本簇內(nèi)成員的基本節(jié)點信息，并且可以運用選舉算法發(fā)起選舉行為和發(fā)送、接收狀態(tài)信息報文。

2.2 算法描述

參照LEACH 算法，本文算法將網(wǎng)絡(luò)的工作過程分成輪，每輪包括建立期和穩(wěn)定期，在建立期執(zhí)行分簇協(xié)議和主備簇頭的選舉；穩(wěn)定期分成若干幀，在每一幀，一是成員節(jié)點向群首服務(wù)簇頭發(fā)送數(shù)據(jù)，群首合并后經(jīng)過一跳或者多跳路由傳送給sink 節(jié)點，然后由sink 節(jié)點通過傳輸層中的互聯(lián)網(wǎng)、衛(wèi)星或者無線通信網(wǎng)絡(luò)將數(shù)據(jù)發(fā)送給服務(wù)器；二是服務(wù)簇頭與備用簇頭互相監(jiān)聽確定是否進行服務(wù)簇頭切換和備用簇頭重選舉。

如果備份簇頭的服務(wù)性能水平與服務(wù)簇頭的服務(wù)性能水平相差不大，這種接管不會給任何網(wǎng)絡(luò)數(shù)據(jù)處理帶來明顯上的影響。主從熱備份模式實現(xiàn)簡單，對簇頭信息機制限制較少。備用簇頭保持在線狀態(tài)運行可以使服務(wù)簇頭應(yīng)用切換過來后備用簇頭立即提供服務(wù)。從而縮短服務(wù)切換時間，提高了網(wǎng)絡(luò)的穩(wěn)定性。該模式穩(wěn)定期流程，如圖2 所示。

圖2 熱備模式工作流程Fig.2 Work flow based-on hot standby

偽碼描述：

2.3 算法實現(xiàn)

在網(wǎng)絡(luò)建立期根據(jù)LEACH 協(xié)議采用分布式的方式完成簇頭的選舉，根據(jù)網(wǎng)絡(luò)情況計算出一個最優(yōu)簇數(shù)，設(shè)最優(yōu)的簇數(shù)K，一般為網(wǎng)絡(luò)節(jié)點數(shù)的5%[8]。根據(jù)閾值T（n）的計算公式[9]：

其中，p 是期望的簇頭數(shù)在所有節(jié)點中所占的百分比；r*mod（1/p）為本周期內(nèi)當選為簇頭的節(jié)點個數(shù)；λ為加權(quán)因子，其值隨網(wǎng)絡(luò)規(guī)模和應(yīng)用場景的的不同而不同，0＜λ≤1，本文取0.01；Ep（n）為節(jié)點剩余能量率；ω為距離因子。Ep（n）的定義如下：

其中Er（n）為節(jié)點剩余能量；Eo代表簇內(nèi)的平均能量。ω的定義如下：

其中di為節(jié)點到sink 節(jié)點的近似距離；dmin為節(jié)點至sink 節(jié)點的最近距離；dmax為節(jié)點至sink 節(jié)點的最遠距離。每個傳感器節(jié)點選擇一個0～1 的隨機數(shù)，如果小于T（n）且距離Sink 節(jié)點距離較近的點為簇頭節(jié)點。在產(chǎn)生簇頭節(jié)點以后，普通節(jié)點選擇距離與之通信消耗能量最低的一個簇頭，申請加入其所在的群。簇頭根據(jù)收到的加入請求生成一個TDMA調(diào)度表，指定哪個節(jié)點在哪個時段發(fā)送數(shù)據(jù)，然后把調(diào)度表發(fā)給群內(nèi)節(jié)點。這樣針對整個網(wǎng)絡(luò)已分成K個簇群且已選舉出對應(yīng)的K個簇頭作為服務(wù)簇頭。

基于普通節(jié)點根據(jù)距離與之通信消耗能量最低的一個簇頭加入簇群，所以備用簇頭的選舉采用簇內(nèi)選舉機制[10]，根據(jù)簇內(nèi)節(jié)點的當前剩余能量的Er（i）值和一跳鄰居節(jié)點集合NVi 選舉出備用簇頭。其中服務(wù)簇頭節(jié)點提供數(shù)據(jù)處理服務(wù)并監(jiān)聽備用簇頭的工作狀態(tài)，備用簇頭用來監(jiān)視服務(wù)簇頭的工作狀態(tài)并且存儲與服務(wù)簇頭同樣的節(jié)點信息。

在系統(tǒng)正常情況下，服務(wù)簇頭和備用簇頭通過無線雙向信道進行通信。服務(wù)簇頭在對外提供服務(wù)的同時，按一定規(guī)則周期性的發(fā)送狀態(tài)信息報文給備用簇頭，設(shè)該周期為T，備用簇頭實時監(jiān)聽主機發(fā)送過來的狀態(tài)信息報文，并應(yīng)答ACK 確認幀。如果服務(wù)簇頭能夠正常收到ACK 確認幀，則說明備用簇頭處于正常工作狀態(tài)。如果簇頭不能夠正常收到ACK 確認幀，將備用簇頭故障標志變量faultNum 加1，當faultNum 大于設(shè)定的閾值maxFaultNum 的時候，則判定備用簇頭出現(xiàn)異常。簇頭節(jié)點在處理數(shù)據(jù)的同時會立即發(fā)起一次備用簇頭選舉行為，重新選舉出后備簇頭，確保下一次切換的可靠性。同時備用簇頭按一定規(guī)則周期性的發(fā)送狀態(tài)信息報文給服務(wù)簇頭，服務(wù)簇頭實時監(jiān)聽備用簇頭發(fā)過來的狀態(tài)信息報文，并應(yīng)答ACK 確認幀。如果簇頭不能夠正常收到ACK 確認幀，將服務(wù)簇頭故障標志變量faultNum 加1，當faultNum 大于設(shè)定的閾值maxFaultNum 的時候，則判定服務(wù)簇頭異常，備用簇頭首先提升為服務(wù)簇頭并接管本簇內(nèi)的數(shù)據(jù)處理任務(wù)，發(fā)布通告消息告知其它節(jié)點自己是新簇頭，普通節(jié)點根據(jù)自己與簇頭的距離選擇加入哪個簇并告知該簇頭。然后在簇內(nèi)發(fā)起簇頭選舉行為，選舉出一個新的簇頭作為后備簇頭。

3 仿真分析

3.1 仿真設(shè)置

使用NS2 作為基本的仿真平臺，通過與LEACH-ECHC算法相比較，評定本文基于雙簇頭熱備機制的簇頭選舉算法在保證網(wǎng)絡(luò)可靠性方面的性能。設(shè)置假設(shè)網(wǎng)絡(luò)中節(jié)點均勻分布，簇內(nèi)節(jié)點有60個，被安排在直徑為50 m 圓形區(qū)域內(nèi)，節(jié)點每秒鐘產(chǎn)生一個數(shù)據(jù)包并且節(jié)點僅僅在自己的時間表內(nèi)向簇頭傳輸信息。簇頭節(jié)點向sink 節(jié)點每5 秒鐘發(fā)送一個數(shù)據(jù)包，簇頭選舉行為每5 分鐘進行一次，備用簇頭選舉行為在服務(wù)簇頭產(chǎn)生之后由服務(wù)簇頭立即進行。

3.2 結(jié)果分析

使用NS2 仿真結(jié)果如圖3 所示。

圖3 sink 節(jié)點數(shù)據(jù)接收對比（100 小時）Fig.3 Data receiving comparison of sink nodes（100 hours）

在抽樣時間為100個小時期間內(nèi)，記錄利用EHS 算法和LEACH-ECHCCHE 算法進行簇頭選舉時，sink 節(jié)點所接收到的簇頭節(jié)點發(fā)送的數(shù)據(jù)包的總量。仿真環(huán)境中各個簇頭之間向sink 節(jié)點采用輪詢方式發(fā)送數(shù)據(jù)，以盡量避免擁塞對網(wǎng)絡(luò)的影響。從圖中可以看出，在100個小時的抽樣時間內(nèi)，簇頭節(jié)點共向sink 節(jié)點發(fā)送72 000個數(shù)據(jù)包，利用文中提出的基于熱備機制的簇頭選舉算法可以接收到67 210個數(shù)據(jù)包，而利用LEACH-ECHC 算法可以收到64 005個數(shù)據(jù)包，通過數(shù)據(jù)量可以計算出網(wǎng)絡(luò)在分別使用兩種算法時的平均無故障時間（Mean Time Between Failures，簡稱MTBF）?？傻茫?/p>

文中提出的EHS 算法由于引入了簇頭熱備機制，在服務(wù)簇頭出現(xiàn)異常時后備簇頭能夠及時地代替服務(wù)簇頭繼續(xù)提供服務(wù)，有效的保證了數(shù)據(jù)的接收、融合、轉(zhuǎn)發(fā)等任務(wù)，所以從一定程度上提高了簇頭節(jié)點的數(shù)據(jù)處理能力。由仿真可見，EHS 算法較LEACH-ECHC 算法在抽樣100個小時，發(fā)送數(shù)據(jù)量為72 000個數(shù)據(jù)包的情況下，EHS 算法少丟包3205個數(shù)據(jù)包，丟包率下降4.45%，在抽樣100 小時內(nèi)平均無故障時間提高了226 min，由此可知EHS 算法在網(wǎng)絡(luò)連通性和保證網(wǎng)絡(luò)的平均無故障時間方面都有一定的優(yōu)化，一定程度上增強了網(wǎng)絡(luò)的可靠性。

4 結(jié)束語

針對當前物聯(lián)網(wǎng)網(wǎng)絡(luò)中由于簇頭節(jié)點不穩(wěn)定，影響數(shù)據(jù)的傳輸和網(wǎng)絡(luò)的可靠性這一問題，提出一種基于熱備機制的簇頭選舉算法。文章從兩個方面取得了研究進展：1）引入雙簇頭熱備機制，有效降低了單點出錯對于整個網(wǎng)絡(luò)的影響，增強了簇頭服務(wù)能力；2）根據(jù)物聯(lián)網(wǎng)網(wǎng)絡(luò)感知層的特點，對比選取了主從熱備模式。通過仿真實驗，證明所提出的選舉算法是可行的，在一定程度上提高了網(wǎng)絡(luò)的容錯能力，保證了數(shù)據(jù)傳輸?shù)姆€(wěn)定性，在保證網(wǎng)絡(luò)的可靠性方面較CHE 算法效果顯著。在本算法應(yīng)用中，針對能量的消耗以及能量消耗問題需要進一步分析和測試，這正是下一步要研究的目標。

[1]王璨，駱堅，張大方，等.一種基于移動性的無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議[J].計算機工程與科學，2012，34（3）：6-12.WANG Can，LUO Jian，ZHANG Da-fang，et al.A mobilitybased cluster routing protocol for mobile wireless sensor networks[J].Computer Engineering and Science，2012，34（3）：6-12.

[2]Ghazis S，Srivastava A，Yang X，et al.Optimal energy awareclustering in sensor networks Sensors [C]//Florida Academic Press，2002：258-269.

[3]LIN Kai，ZHAO Hai，YIN Zhen-yu，et al.A clustering hierarchy arithmetic based on energy prediction for wireless sensor networks[J].Acta Electronica Sinica，2008，36（4）：824-828.

[4]Ming Yu，Leung K K，Malvankar A.A dynamic clustering and energy efficient routing technique for sensor networks[J].IEEE Trans on Wireless Communications，2007，6（8）：3069-3079.

[5]QIN Min，Zimmermann R.An energy-efficient voting-based clustering algorithm for sensor networks[C]//SNPD/SAWN，Maryland：Academic Press，2005：444-451.

[6]王秀娟.調(diào)度集中系統(tǒng)中雙機熱備機制的實現(xiàn)[J].北京交通大學學報，2009，33（2）：26-28.WANG Xiu-juan.Research and realization of hot standby for centralized traffic control system [J].Journal of Beijing Jiaotong University，2009，33（2）：26-28

[7]劉曉潔，黃永佳.基于Linux的雙機熱備系統(tǒng)的實現(xiàn)技術(shù)[J].計算機應(yīng)用領(lǐng)域，2007，24（4）：254-257.LIU Xiao-jie，HUANG Yong-jia.Implement of hot standby system based on linux[J].Computer Applications，2007，24（4）：254-257.

[8]Heinzelman W，Chandrakasan A，Balakrisham H.Energyefficient communication protocol for wreless microsensor networks [C]//Proceedings of the 33rd Annual Hawaii Int’l Conf.on System Sciences.IEEE Computer Society，2000：3005-3014.

[9]廖明華，張華，王東.基于LEACH 協(xié)議的簇頭選舉改進算法[J].計算機工程，2011，37（7）：112-114.LIAO Ming-hua，ZHANG Hua，WANG Dong.Improved Cluster-head election algorithm based on LEACH protocol[J].Computer Engineering，2011，37（7）：112-114.

[10]LIU H，ZHANG Y，Raychaudhuri D.Performance evaluation of the“cache-and-forward（CNF）”network for mobile content delivery service[C]//Dresden：International Conference on Communications Workshops，2009：l-5.