蔣青云

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

0 引言

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

1 簇首備份機制概述

1.1 簇首備份的基本概念

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

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

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

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

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

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

1.2 典型的簇首備份機制

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

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

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

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

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

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

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

圖3 節(jié)點確定鄰居關系的示意圖

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

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

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

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

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

2 基于綜合指標的簇首備份機制

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

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

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

圖4 簇首備份機制示意圖

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

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

表1 模擬實驗參數(shù)表

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

圖5 簇平均生存時間與節(jié)點密度關系示意圖

圖6 簇平均生存時間與節(jié)點通信距離關系圖

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

4 結(jié)束語

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

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

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

[3]唐勇，周明天，張欣.無線傳感器網(wǎng)絡路由協(xié)議研究進展[J].軟件學報，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)絡分簇路由協(xié)議[J].軟件學報，2006，17(7):1588-1600.

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

[7]朱光輝，張修如，劉衛(wèi)彪.無線傳感器網(wǎng)絡中能量有效的加權(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)絡中分簇算法能量有效性分析[J].電子與信息學報，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)仿真學報，2008，20(6):1523-1528.

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

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

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

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

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

[17]張源.一種基于LEACH協(xié)議的節(jié)能型分簇路由算法[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.