無線傳感器網(wǎng)絡(luò)簇首備份機(jī)制研究

蔣青云

(湖南省婦幼保健院信息中心，湖南 長沙 410008)

0 引言

基于不同的應(yīng)用目的和應(yīng)用需求，諸多學(xué)者已經(jīng)研究出了多種分簇策略[1-2]，提出了多種有效的分簇算法[3]。然而，在分簇式無線傳感器網(wǎng)絡(luò)中，簇首節(jié)點(diǎn)[4]既需擔(dān)當(dāng)收集和轉(zhuǎn)發(fā)本簇內(nèi)各普通節(jié)點(diǎn)數(shù)據(jù)的任務(wù)，又需對其它離匯聚節(jié)點(diǎn)更遠(yuǎn)的簇首節(jié)點(diǎn)所收集的數(shù)據(jù)進(jìn)行轉(zhuǎn)發(fā)，這可能導(dǎo)致簇首節(jié)點(diǎn)因過快消耗能量而死亡。并且，簇首節(jié)點(diǎn)本身可能因硬件或軟件故障而影響當(dāng)前的通信狀態(tài)或行為，例如傳感器節(jié)點(diǎn)的內(nèi)存、收發(fā)器、寄存器、通信鏈路及控制程序等故障。無論是簇首節(jié)點(diǎn)因能量消耗過多死、過早死亡還是因突發(fā)性故障導(dǎo)致節(jié)點(diǎn)崩潰，都將導(dǎo)致該簇不能完成數(shù)據(jù)收集與傳輸任務(wù)[5]，影響了網(wǎng)絡(luò)的壽命。因此，有必要對簇首節(jié)點(diǎn)進(jìn)行維護(hù)，以延長網(wǎng)絡(luò)的生命周期。

1 簇首備份機(jī)制概述

1.1 簇首備份的基本概念

圖1 簇首備份與備份簇首轉(zhuǎn)為簇首的過程示意圖

扼要地說，簇首備份[6]就是指在分簇形成后，根據(jù)某種規(guī)則選取出除原簇首外的一個(gè)或多個(gè)備份簇首，以備原簇首在能量過快消耗或出現(xiàn)故障時(shí)能主動(dòng)承擔(dān)起該分簇的“領(lǐng)導(dǎo)者”任務(wù)。圖1給出了簇首備份與備份簇首轉(zhuǎn)為新的簇首的示意圖[7]，圖中BS表示基站(匯聚節(jié)點(diǎn))，序號(hào)為4、8、20的節(jié)點(diǎn)分別為簇C1、C2、C3 的簇首節(jié)點(diǎn)，序號(hào)為 22、19、1 的節(jié)點(diǎn)分別為簇C1、C2、C3的備份簇首節(jié)點(diǎn)(一個(gè)備份簇首節(jié)點(diǎn)的情形)，其余的為普通節(jié)點(diǎn)。圖1中的左圖表示簇首未出現(xiàn)故障時(shí)的情形，在簇C3中的簇首節(jié)點(diǎn)20出現(xiàn)故障后，該分簇內(nèi)的備份簇首節(jié)點(diǎn)1轉(zhuǎn)為新的簇首(如圖1中的右圖所示)，分簇內(nèi)各普通節(jié)點(diǎn)在新簇首的“領(lǐng)導(dǎo)”下繼續(xù)工作。

一般情形下，簇首節(jié)點(diǎn)承擔(dān)著相對普通節(jié)點(diǎn)更多的數(shù)據(jù)處理和傳輸任務(wù)[8]，其能量消耗相對較快，故障發(fā)生的可能性也相對更大。顯然易見，盡管簇首節(jié)點(diǎn)突發(fā)死亡，但簇內(nèi)其它普通節(jié)點(diǎn)仍能繼續(xù)進(jìn)行數(shù)據(jù)采集，簇的壽命并沒有真正結(jié)束。采用簇首備份機(jī)制可有效地解決因簇首過早死亡而出現(xiàn)的分簇或整個(gè)網(wǎng)絡(luò)的假死亡現(xiàn)象。簇首備份的優(yōu)勢[9]可概括為如下幾點(diǎn):

(1)可有效延長分簇的生命周期;

(2)可提高無線傳感器網(wǎng)絡(luò)的穩(wěn)定性和整體性能;

(3)能較大幅度地減少因簇首節(jié)點(diǎn)出現(xiàn)故障而產(chǎn)生的損失。

1.2 典型的簇首備份機(jī)制

簇首備份機(jī)制的關(guān)鍵是備份策略，即根據(jù)何種規(guī)則來選取合適的備份簇首，使網(wǎng)絡(luò)的整體性能達(dá)到最優(yōu)。根據(jù)不同的網(wǎng)絡(luò)狀況和用戶需求，典型的簇首備份[10]選取策略主要有考慮覆蓋面積[11]的選取法和基于節(jié)點(diǎn)度數(shù)[12]的選取法。

(1)考慮覆蓋面積的選取法。

這里所提到的覆蓋面積是指備份簇首的無線電信號(hào)所能覆蓋到原簇首的通信面積。如圖2所示，圖中實(shí)心節(jié)點(diǎn)和虛線圓周分別表示原簇首及其覆蓋范圍，空心節(jié)點(diǎn)和實(shí)線圓周表示備份簇首及其覆蓋范圍，原簇首覆蓋范圍與備份簇首覆蓋范圍的公共部分即為備份簇首的覆蓋面積，當(dāng)原簇首出現(xiàn)故障時(shí)，備份簇首可保證覆蓋面積對應(yīng)區(qū)域中的節(jié)點(diǎn)正常通信。

圖2 備份簇首的覆蓋面積示意圖

對于無線傳感器網(wǎng)絡(luò)，因其拓?fù)浣Y(jié)構(gòu)保持不變，成員節(jié)點(diǎn)與簇首之間的距離a也是確定的。這種考慮覆蓋面積的選取策略事實(shí)上是從通信距離的角度考慮了各成員節(jié)點(diǎn)競爭備份簇首的能力。這種考慮覆蓋面積的備份簇首選取策略的主要優(yōu)勢是:在整個(gè)選取過程中簇首只需根據(jù)節(jié)點(diǎn)信號(hào)的強(qiáng)弱估計(jì)對應(yīng)的節(jié)點(diǎn)間距，進(jìn)而估計(jì)出節(jié)點(diǎn)的覆蓋能力，無需額外的消息傳送開銷。但這種策略[12]只適合于節(jié)點(diǎn)密度較高、分布均勻的情況，當(dāng)假設(shè)不成立時(shí)，可能對整體的性能產(chǎn)生較大的影響。

(2)基于節(jié)點(diǎn)度數(shù)的選取法。

眾所周知，由于無線電傳輸無方向性，所以節(jié)點(diǎn)可以通過在自己的接收范圍內(nèi)監(jiān)聽周圍信號(hào)來確定鄰居節(jié)點(diǎn)數(shù)[13]。如圖3所示，當(dāng)節(jié)點(diǎn)A與節(jié)點(diǎn)B進(jìn)行數(shù)據(jù)通信時(shí)，在節(jié)點(diǎn)A的通信范圍內(nèi)的節(jié)點(diǎn)C、D均可通過監(jiān)聽信號(hào)的辦法來確定自己與A的鄰居關(guān)系，對網(wǎng)絡(luò)中的其它節(jié)點(diǎn)也是如此。

圖3 節(jié)點(diǎn)確定鄰居關(guān)系的示意圖

根據(jù)發(fā)現(xiàn)網(wǎng)絡(luò)中鄰居節(jié)點(diǎn)的思想，可設(shè)計(jì)如下的備份簇首選取策略:

Step1 簇內(nèi)各節(jié)點(diǎn)通過監(jiān)聽的方法得到自己的鄰居關(guān)系，設(shè)節(jié)點(diǎn)的度數(shù)為Dn;

Step2 簇內(nèi)各節(jié)點(diǎn)將自己鄰居數(shù)上報(bào)給本簇的簇首，得到最大簇婁TD;

Step3 簇首根據(jù)收到的各個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)度數(shù)，選取度數(shù)最大的節(jié)點(diǎn)，若Dn＜TD，則不進(jìn)行簇首備份，否則以該節(jié)點(diǎn)備份簇首進(jìn)行備份。

對于無線傳感器網(wǎng)絡(luò)，在大多情形下，節(jié)點(diǎn)部署后不再移動(dòng)，因此各節(jié)點(diǎn)的鄰居關(guān)系是在部署后就已經(jīng)確定了的。這種基于節(jié)點(diǎn)度數(shù)的選取法考察了節(jié)點(diǎn)的鄰居數(shù)目，從通信距離看，發(fā)現(xiàn)的鄰居節(jié)點(diǎn)數(shù)，從一定程度上反映出能與該節(jié)點(diǎn)進(jìn)行直接通信的成員節(jié)點(diǎn)數(shù)的多少。這種選取策略的主要技術(shù)優(yōu)勢是:對成員節(jié)點(diǎn)沒有特定的要求，且能適應(yīng)網(wǎng)絡(luò)的拓?fù)渥兓樾?，?shí)現(xiàn)起來非常簡單，但是，各個(gè)成員節(jié)點(diǎn)在發(fā)現(xiàn)鄰居與上報(bào)自身的節(jié)點(diǎn)度數(shù)時(shí)需要發(fā)送大量的控制消息，需要一定的額外開銷，且隨節(jié)點(diǎn)數(shù)目的增多而遞增，因此這種策略通常只適用于節(jié)點(diǎn)密度較低的場合。

2 基于綜合指標(biāo)的簇首備份機(jī)制

本文在研究上述兩種機(jī)制的基礎(chǔ)上，提出一種基于綜合指標(biāo)的無線傳感器網(wǎng)絡(luò)簇首備份機(jī)制。對于分簇式無線傳感器網(wǎng)絡(luò)，其數(shù)據(jù)收集任務(wù)[14]的完成與分簇的生命有著緊密的聯(lián)系。簇首備份是一種很好的延長分簇生命周期，提升網(wǎng)絡(luò)整體的性能的方法。

在無線傳感器網(wǎng)絡(luò)中，設(shè)分簇j內(nèi)第i個(gè)節(jié)點(diǎn)xi的節(jié)點(diǎn)度數(shù)為Degree(xi)(按上文提到的節(jié)點(diǎn)度數(shù)選取的方法確定)，其剩余能量為Eresidual(xi)，綜合指標(biāo)Syn_Indexj(xi)的計(jì)算公式[15]:

式中，φ1、φ2為權(quán)重因子，λ1、λ2、λ3為大于等于 0 的系數(shù)，其值根據(jù)具體場景和應(yīng)用來確定，分別用來衡量節(jié)點(diǎn)的剩余能量、度數(shù)及通信代價(jià)三者在實(shí)際場景和應(yīng)用中的權(quán)重。對簇j中的所有節(jié)點(diǎn)均按公式(1)計(jì)算出相應(yīng)的綜合指標(biāo)值Syn_Indexj(xi)(i=1，2，...，n，表示簇 j內(nèi)的節(jié)點(diǎn)數(shù))，再從大到小排列成Syn_Indexj(xi1)、Syn_Indexj(xi2)、Syn_Indexj(xi3)、…、Syn_Indexj(xin)。根據(jù)排隊(duì)后的綜合指標(biāo)值，即可實(shí)施備份簇首的選取機(jī)制。這種備份簇首選取策略，合理地結(jié)合了節(jié)點(diǎn)的剩余能量、節(jié)點(diǎn)度數(shù)與節(jié)點(diǎn)通信代價(jià)，能有效地克服無備份簇首情形下分簇提前死亡的問題，有效地延長了網(wǎng)絡(luò)生命，提升了網(wǎng)絡(luò)的整體性能。該簇首備份機(jī)制的詳細(xì)流程示意圖如圖4所示。

圖4 簇首備份機(jī)制示意圖

3 仿真與結(jié)果分析

為了便于比較分析，將本文提出的簇首備份機(jī)制引入到典型的基于K-均值聚類分簇算法KMC[16]中，并將此算法簡稱BH-KMC(Backup Cluster-Head for KMC)。筆者對分簇策略BH-KMC的分簇過程進(jìn)行了模擬仿真，并就其性能與經(jīng)典分簇策略LEACH[17]和KMC算法[18]進(jìn)行比較分析。為了消除網(wǎng)絡(luò)拓?fù)鋵Σ呗孕阅茉u價(jià)的影響，在不同的節(jié)點(diǎn)密度情形下，各進(jìn)行50次實(shí)驗(yàn)，取50次實(shí)驗(yàn)結(jié)果的平均值來比較分析。主要仿真實(shí)驗(yàn)參數(shù)如表1所示。

表1 模擬實(shí)驗(yàn)參數(shù)表

簇的平均生存時(shí)間是整個(gè)過程中各個(gè)簇生存時(shí)間的平均值，該指標(biāo)從整體的角度上反映了分簇的穩(wěn)定性。本文在節(jié)點(diǎn)密度和節(jié)點(diǎn)通信半徑不同的網(wǎng)絡(luò)環(huán)境下分別進(jìn)行了仿真，得到節(jié)點(diǎn)密度與簇平均生存時(shí)間關(guān)系和節(jié)點(diǎn)通信半徑與簇平均生存時(shí)間關(guān)系如圖5、圖6所示。

圖5 簇平均生存時(shí)間與節(jié)點(diǎn)密度關(guān)系示意圖

圖6 簇平均生存時(shí)間與節(jié)點(diǎn)通信距離關(guān)系圖

從圖5及圖6可以看出隨著節(jié)點(diǎn)密度和節(jié)點(diǎn)通信半徑的增加，BH-KMC和KMC算法的平均生存時(shí)間是遞增的，LEACH由于節(jié)點(diǎn)密度和通信半徑的增加的影響而略有下降?？梢园l(fā)現(xiàn)，在不同的環(huán)境下BH-KMC算法的簇平均生存時(shí)間始終高出其他兩種策略。實(shí)驗(yàn)表明BH-KMC算法在簇平均生存時(shí)間上都高于其他兩種算法一倍以上。

4 結(jié)束語

本文提出了一種基于綜合指標(biāo)的無線傳感器網(wǎng)絡(luò)簇首備份機(jī)制。在基于綜合指標(biāo)的簇首備份機(jī)制中，通過節(jié)點(diǎn)剩余能量、節(jié)點(diǎn)度數(shù)、通信代價(jià)三者構(gòu)建一種有效的綜合指標(biāo)，并根據(jù)此綜合指標(biāo)對簇內(nèi)成員節(jié)點(diǎn)進(jìn)行排序，選取具有優(yōu)秀的綜合指標(biāo)值的成員節(jié)點(diǎn)作為備份簇首節(jié)點(diǎn)，并保持簇首與備份簇首不斷輪換。實(shí)驗(yàn)表明BH-KMC算法在簇平均生存時(shí)間上都高于其他兩種算法一倍以上。這意味著整個(gè)分簇可以在更長的時(shí)間內(nèi)穩(wěn)定地工作，表明采用該機(jī)制的分簇?zé)o線傳感器網(wǎng)絡(luò)可有效地降低簇首故障所帶來的損失，加強(qiáng)了分簇的穩(wěn)定性，延長了網(wǎng)絡(luò)壽命，使得網(wǎng)絡(luò)整體性能得到優(yōu)化。

[1]李莉，董樹松，溫向明.無線傳感器網(wǎng)絡(luò)中的分簇算法[J].無線通信技術(shù)，2006，15(3):47-51，62.

[2]崔莉，鞠海玲，苗勇，等.無線傳感器網(wǎng)絡(luò)研究進(jìn)展[J].計(jì)算機(jī)研究與發(fā)展，2005，42(1):163-174.

[3]唐勇，周明天，張欣.無線傳感器網(wǎng)絡(luò)路由協(xié)議研究進(jìn)展[J].軟件學(xué)報(bào)，2006，17(3):410-421.

[4]Younis O，F(xiàn)ahmy S.Distributed clustering in Ad-hoc sensor networks:A hybrid，energy efficient approach[C]//Proc.IEEE INFOCOM 2004.Hong Kong，China，2004.

[5]沈波，張世永，鐘亦平.無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議[J].軟件學(xué)報(bào)，2006，17(7):1588-1600.

[6]徐建波.無線傳感器網(wǎng)絡(luò)分布式分簇和節(jié)能的數(shù)據(jù)收集協(xié)議研究[D].長沙:湖南大學(xué)，2008.

[7]朱光輝，張修如，劉衛(wèi)彪.無線傳感器網(wǎng)絡(luò)中能量有效的加權(quán)分簇算法[J].傳感器與微系統(tǒng)，2007，26(12):102-105.

[8]Lindsey S，Raghavendra C S.PEGASIS:Power-efficient gathering in sensor information systems[C]//Proc of the IEEE Aerospace Conf.Montana:IEEE Aerospace and E-lectronic Systems Society.2002:1125-1130.

[9]李莉，溫向明.無線傳感器網(wǎng)絡(luò)中分簇算法能量有效性分析[J].電子與信息學(xué)報(bào)，2008，30(4):966-969

[10]Gupta I，Riordan D，Sampalli S.Cluster-head election using fuzzy logic for wireless sensor networks[C]//Proc.of the 3rd Annual Communication Networks and Services Research Conf.Halifax:IEEE Computer Society，2005:255-260.

[11]陳嘉寧，謝高崗，張大方，等.BH-3hBAC:一種穩(wěn)定的MANET分簇策略[J].系統(tǒng)仿真學(xué)報(bào)，2008，20(6):1523-1528.

[12]陳嘉寧.基于備份的移動(dòng)自組織網(wǎng)絡(luò)分簇策略研究[D].長沙:湖南大學(xué)，2007.

[13]徐強(qiáng)，汪蕓.容錯(cuò)節(jié)能無線傳感器網(wǎng)絡(luò)中可靠覆蓋問題的解決方案[J].軟件學(xué)報(bào)，2006，17(s):184-191.

[14]夏心鋒，孫燕.基于聚類的無線傳感器網(wǎng)絡(luò)的分簇算法研究[J].南京師范大學(xué)學(xué)報(bào):工程技術(shù)版，2008，8(2):81-84.

[15]蔣青云.無線傳感器網(wǎng)絡(luò)分簇算法與簇首備份機(jī)制研究[D].長沙:中南大學(xué)，2009.

[16]陳潔潔，樊曉平，瞿志華，等.基于減法聚類的無線傳感器網(wǎng)絡(luò)分簇路由算法[J].信息與控制，2008，37(4):435-438，444.

[17]張?jiān)?一種基于LEACH協(xié)議的節(jié)能型分簇路由算法[J].計(jì)算機(jī)與現(xiàn)代化，2009(12):133-136.

[18]Ahmad A，Dey L.A k-mean clustering algorithm for mixed numeric and categorical data[J].Data ＆ Knowledge Engineering，2007，63(2):503-527.