孫中皋 鄭紫微 許少娟

(1.大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院，遼寧大連116026;2.遼寧師范大學(xué)物理與電子技術(shù)學(xué)院，遼寧大連116029;3.寧波大學(xué)信息科學(xué)與工程學(xué)院，浙江寧波315211;4.大連理工大學(xué)城市學(xué)院，遼寧大連116600)

在無(wú)線傳感器網(wǎng)絡(luò)中，傳感器節(jié)點(diǎn)部署比較密集，鄰近節(jié)點(diǎn)采集到的數(shù)據(jù)具有較大的相關(guān)性，節(jié)點(diǎn)可以通過(guò)收集鄰近節(jié)點(diǎn)的數(shù)據(jù)并進(jìn)行融合［1］來(lái)減少冗余數(shù)據(jù)，從而降低數(shù)據(jù)采集的能耗.利用這一特性，人們提出了大量的分簇算法以提高網(wǎng)絡(luò)的能量效率.分簇的基本思想是將網(wǎng)絡(luò)中的節(jié)點(diǎn)劃分為簇頭節(jié)點(diǎn)和簇成員節(jié)點(diǎn)，簇頭節(jié)點(diǎn)負(fù)責(zé)收集簇內(nèi)成員節(jié)點(diǎn)的數(shù)據(jù)并進(jìn)行融合處理后發(fā)送至遠(yuǎn)方的基站.分簇算法的有效性很大程度上取決于簇頭節(jié)點(diǎn)的選取策略:(1)因簇頭節(jié)點(diǎn)的能耗遠(yuǎn)大于簇成員節(jié)點(diǎn)的能耗，若簇頭節(jié)點(diǎn)選取不當(dāng)，則容易導(dǎo)致其電池能量過(guò)早耗盡而使網(wǎng)絡(luò)失效，故選取簇頭節(jié)點(diǎn)時(shí)要考慮節(jié)點(diǎn)的能量和能耗;(2)傳感器節(jié)點(diǎn)的無(wú)線通信能耗遠(yuǎn)大于傳感和數(shù)據(jù)處理時(shí)消耗的能量［2］，所以簇頭節(jié)點(diǎn)的選取過(guò)程要減少消息通信的數(shù)量.

LEACH算法［3］是具有代表性的分簇算法，其簇頭節(jié)點(diǎn)的選取方法具有隨機(jī)性且沒(méi)有考慮節(jié)點(diǎn)的剩余能量.在其它眾多分簇算法中［4-11］，簇頭節(jié)點(diǎn)的選取方法不僅考慮了節(jié)點(diǎn)的剩余能量，還將網(wǎng)絡(luò)局部范圍內(nèi)節(jié)點(diǎn)的其它屬性信息作為簇頭節(jié)點(diǎn)選舉的依據(jù)，如節(jié)點(diǎn)度［4，6］、節(jié)點(diǎn)聚合度［5］、通信代價(jià)［6］和兩跳范圍內(nèi)節(jié)點(diǎn)的拓?fù)湫畔ⅲ?］等.文獻(xiàn)［6］中提出的HEED算法，在選舉簇頭節(jié)點(diǎn)時(shí)首先以節(jié)點(diǎn)剩余能量作為主參數(shù)選取出候選簇頭節(jié)點(diǎn)，然后以簇內(nèi)通信代價(jià)或度作為次參數(shù)，通過(guò)多次迭代來(lái)選取簇頭節(jié)點(diǎn).文獻(xiàn)［8］中提出的基于投票機(jī)制的分簇算法(VCA)，節(jié)點(diǎn)依據(jù)剩余能量信息給鄰居節(jié)點(diǎn)及自身投票，通過(guò)迭代選取票數(shù)高的節(jié)點(diǎn)為簇頭節(jié)點(diǎn).HEED算法和VCA在迭代過(guò)程中節(jié)點(diǎn)與鄰居節(jié)點(diǎn)的消息交換消耗了額外的能量.基于定時(shí)驅(qū)動(dòng)機(jī)制的分簇算法［9-11］則避免了迭代過(guò)程，減少了消息開(kāi)銷(xiāo).文獻(xiàn)［10］中提出的基于定時(shí)驅(qū)動(dòng)的分簇算法，節(jié)點(diǎn)按照負(fù)指數(shù)分布生成一個(gè)定時(shí)長(zhǎng)度用于競(jìng)爭(zhēng)簇頭節(jié)點(diǎn)，剩余能量較多的節(jié)點(diǎn)成為簇頭節(jié)點(diǎn)的機(jī)會(huì)更大.文獻(xiàn)［11］中提出的SWEET算法在簇頭節(jié)點(diǎn)選舉的兩個(gè)階段都采用了定時(shí)的方式.

結(jié)合投票機(jī)制考慮鄰居節(jié)點(diǎn)信息的思想和定時(shí)驅(qū)動(dòng)機(jī)制消息開(kāi)銷(xiāo)小的特點(diǎn)，文中提出了一種基于雙重選舉機(jī)制的分簇算法(DSMCA).投票選舉機(jī)制中考慮了節(jié)點(diǎn)的剩余能量、節(jié)點(diǎn)間及節(jié)點(diǎn)與基站間的通信代價(jià)3個(gè)屬性，節(jié)點(diǎn)所投票數(shù)取決于這3個(gè)屬性的綜合評(píng)價(jià)值，各屬性的權(quán)重系數(shù)采用信息熵的方法求得.投票結(jié)束后，節(jié)點(diǎn)依據(jù)所得的總票數(shù)生成一個(gè)定時(shí)長(zhǎng)度參與簇頭節(jié)點(diǎn)的選舉.

1 VCA

VCA認(rèn)為在簇頭節(jié)點(diǎn)選舉中，節(jié)點(diǎn)除考慮自身的能量狀態(tài)外還應(yīng)考慮鄰居節(jié)點(diǎn)的能量信息.節(jié)點(diǎn)si投給節(jié)點(diǎn)sj的票數(shù)為［8］

式中，ej為節(jié)點(diǎn)sj的剩余能量，dij為節(jié)點(diǎn)si到節(jié)點(diǎn)sj的距離，R為節(jié)點(diǎn)的通信半徑.

VCA以節(jié)點(diǎn)的剩余能量為參數(shù)，而忽略了節(jié)點(diǎn)的相對(duì)位置信息，在選取高能量節(jié)點(diǎn)的同時(shí)可能會(huì)付出高的能耗代價(jià).如圖1所示，sj和sk為si的兩個(gè)鄰居節(jié)點(diǎn)，采用VCA投票，當(dāng)sj和sk的剩余能量相等或較為接近時(shí)，si投給這兩個(gè)節(jié)點(diǎn)的票數(shù)相當(dāng).因sk與si之間的距離以及sk與基站之間的距離都比sj近，si選取sk當(dāng)選簇頭節(jié)點(diǎn)的通信代價(jià)更小，故sk應(yīng)比sj得到更多的票數(shù).

圖1 節(jié)點(diǎn)投票示例Fig.1 An example of node voting

2 DSMCA的雙重選舉機(jī)制

2.1 DSMCA的投票機(jī)制

DSMCA除考慮節(jié)點(diǎn)的剩余能量屬性外，還引入了節(jié)點(diǎn)間的通信代價(jià)以及節(jié)點(diǎn)與基站間的通信代價(jià)兩個(gè)屬性，節(jié)點(diǎn)按照以下規(guī)則投票:(1)節(jié)點(diǎn)只給比自己剩余能量大的鄰居節(jié)點(diǎn)投票;(2)節(jié)點(diǎn)所投出的總票數(shù)為1，投給某個(gè)節(jié)點(diǎn)的票數(shù)與該節(jié)點(diǎn)的綜合屬性評(píng)價(jià)值有關(guān).

由規(guī)則(1)可知，節(jié)點(diǎn)的剩余能量越大，得到的票數(shù)越多而投出的票數(shù)越少;相反，節(jié)點(diǎn)的剩余能量越小，投出的票數(shù)越多而得到的票數(shù)越少.規(guī)則(1)減少了剩余能量小的節(jié)點(diǎn)當(dāng)選簇頭節(jié)點(diǎn)的機(jī)會(huì)，讓剩余能量大的節(jié)點(diǎn)處于被選舉狀態(tài)而少投票，與VCA中節(jié)點(diǎn)給每個(gè)鄰居節(jié)點(diǎn)投票相比，減少了消息開(kāi)銷(xiāo).由規(guī)則(2)可知，一個(gè)具有較高剩余能量的節(jié)點(diǎn)，其鄰居節(jié)點(diǎn)數(shù)越多，得到的票數(shù)越多，并且票數(shù)均衡了節(jié)點(diǎn)的能量和能耗因素.

基于投票規(guī)則，DSMCA的多屬性投票模型為

式中，zj為節(jié)點(diǎn)sj的綜合屬性評(píng)價(jià)值，

m為屬性個(gè)數(shù)，rjk為節(jié)點(diǎn)sj的第k個(gè)屬性的規(guī)范化值，ωk為第k個(gè)屬性的權(quán)重，滿足

由式(2)、(3)可知，要計(jì)算票數(shù)，需先確定屬性的規(guī)范化值，并為每個(gè)屬性選擇合適的權(quán)重.

2.1.1 屬性規(guī)范化

設(shè)節(jié)點(diǎn)si擁有比自己剩余能量高的鄰居節(jié)點(diǎn)集為S={s1，s2，…，sn}，每個(gè)節(jié)點(diǎn)的屬性集為U={u1，u2，…，um}，用xk'l(1≤k'≤n，1≤l≤m)表示節(jié)點(diǎn)sk'關(guān)于屬性u(píng)l的評(píng)價(jià)值，則節(jié)點(diǎn)si可建立集合S的多屬性矩陣X:

由于不同屬性的物理量綱互不相同，為了使各屬性之間具有可比性，需要對(duì)屬性矩陣進(jìn)行規(guī)范化處理［12］.DSMCA采用比例轉(zhuǎn)換法對(duì)各屬性進(jìn)行轉(zhuǎn)換.對(duì)于效益型屬性(如剩余能量)，采用式(6)進(jìn)行規(guī)范化:

規(guī)范化后的屬性矩陣R為

將R中的屬性評(píng)價(jià)值代入式(3)，求得節(jié)點(diǎn)的綜合屬性評(píng)價(jià)值，就消除了屬性量綱的差異性.

2.1.2 屬性權(quán)重

熵在信息論中是不確定性和信息量的一個(gè)量度，其定義為［13］

式中，h為正常數(shù)，pi為一個(gè)離散的概率分布.熵值具有極值性，當(dāng)所有的pi都相等，即等概率pi=1/n時(shí)，熵值E取得最大值.

多屬性矩陣表述了節(jié)點(diǎn)的不同屬性值，可以看作是信息的載體.而熵法是評(píng)價(jià)屬性相對(duì)重要程度的一種有力工具［13］，其基本原理為:所有方案在某屬性上的取值差異越大，則該屬性向量提供的信息越多，該屬性被賦予的權(quán)重也越大;與之相反，所有方案在某一屬性上的取值越接近，則該屬性對(duì)各方案所起的作用越小，所賦予的權(quán)重也越小.

DSMCA采用熵法求解權(quán)重，節(jié)點(diǎn)在投票時(shí)通過(guò)所有可投票節(jié)點(diǎn)的多屬性矩陣衡量各屬性的重要程度，從而決定各屬性的權(quán)重.確定權(quán)重的步驟如下:

1)對(duì)于規(guī)范化后的屬性矩陣R，計(jì)算屬性u(píng)l的幾何影射pk'l為

2)計(jì)算屬性u(píng)l的熵El為

當(dāng)pk'l=0時(shí)，令pk'llnpk'l=0.

3)計(jì)算屬性u(píng)l的權(quán)重為

式(12)通過(guò)歸一化處理，使權(quán)重滿足式(4)的條件.

2.2 DSMCA的定時(shí)驅(qū)動(dòng)機(jī)制

設(shè)節(jié)點(diǎn)完成投票后統(tǒng)計(jì)所得票數(shù)為vtotal，首先將票數(shù)轉(zhuǎn)換為參與簇頭節(jié)點(diǎn)競(jìng)爭(zhēng)的初始定時(shí)長(zhǎng)度:

式中:ε為一足夠小的常數(shù)，當(dāng)vtotal=0時(shí)，節(jié)點(diǎn)依據(jù)ε生成定時(shí)長(zhǎng)度;x為在［0，1］上均勻分布的隨機(jī)變量;vmax為一常數(shù)，表示節(jié)點(diǎn)可能得到的最大票數(shù)，若節(jié)點(diǎn)收到每個(gè)鄰居節(jié)點(diǎn)的票數(shù)都為最大值1，則vmax等于節(jié)點(diǎn)所擁有的最大鄰居節(jié)點(diǎn)數(shù)，vmax由節(jié)點(diǎn)的通信半徑及網(wǎng)絡(luò)中節(jié)點(diǎn)的分布密度決定.

接著節(jié)點(diǎn)設(shè)置定時(shí)器時(shí)間為

式(13)中，當(dāng)vtotal≠0 時(shí)，令v=vtotal/vmax，則0 ＜v＜1，保證了tinitial＞0且tinitial關(guān)于v的一階偏導(dǎo)數(shù)?tinitial/?v=-v-1＜ 0，即隨著v的增大，tinitial單調(diào)遞減，也就是說(shuō)，節(jié)點(diǎn)所得的選票數(shù)越多，其生成的定時(shí)長(zhǎng)度越短.

另外，由式(13)可知，節(jié)點(diǎn)的初始定時(shí)長(zhǎng)度取決于節(jié)點(diǎn)得到的票數(shù)vtotal和隨機(jī)變量x的取值，其中vtotal取決于鄰居節(jié)點(diǎn)對(duì)節(jié)點(diǎn)多個(gè)屬性的綜合評(píng)價(jià)值，這使得在節(jié)點(diǎn)通信半徑內(nèi)存在與該節(jié)點(diǎn)具有相同票數(shù)的其它節(jié)點(diǎn)的概率很小，而且隨機(jī)變量x進(jìn)一步降低了相鄰節(jié)點(diǎn)生成相同定時(shí)長(zhǎng)度的可能性.所以，DSMCA降低了節(jié)點(diǎn)在競(jìng)爭(zhēng)簇頭節(jié)點(diǎn)時(shí)發(fā)生沖突的概率，在簇頭節(jié)點(diǎn)的通信半徑內(nèi)只存在一個(gè)簇頭節(jié)點(diǎn)，即簇頭節(jié)點(diǎn)在網(wǎng)絡(luò)中的分布相對(duì)均勻.

3DSMCA描述

3.1 網(wǎng)絡(luò)初始化

網(wǎng)絡(luò)初始化的主要任務(wù)是節(jié)點(diǎn)根據(jù)信號(hào)接收強(qiáng)度估算與發(fā)送方的距離，以便獲取通信代價(jià)屬性值及在數(shù)據(jù)傳輸時(shí)選取合適的發(fā)射功率.其中節(jié)點(diǎn)的通信代價(jià)屬性定義為節(jié)點(diǎn)向接收方發(fā)送一個(gè)數(shù)據(jù)包所需要的能量.

為此，在網(wǎng)絡(luò)部署完成后，首先由基站以一定功率向全網(wǎng)廣播一個(gè)消息，每個(gè)節(jié)點(diǎn)根據(jù)該消息估算至基站的距離并計(jì)算自身至基站的通信代價(jià).然后每個(gè)節(jié)點(diǎn)以一定的功率發(fā)送一個(gè)鄰居發(fā)現(xiàn)消息與鄰居節(jié)點(diǎn)進(jìn)行消息交換，在這個(gè)過(guò)程中，節(jié)點(diǎn)計(jì)算與每個(gè)鄰居節(jié)點(diǎn)間的通信代價(jià)，并獲得鄰居節(jié)點(diǎn)的剩余能量和至基站的通信代價(jià)屬性值.網(wǎng)絡(luò)初始化完成后，節(jié)點(diǎn)建立鄰居節(jié)點(diǎn)信息表，保存各節(jié)點(diǎn)的屬性值.

3.2 網(wǎng)絡(luò)運(yùn)行

在網(wǎng)絡(luò)初始化之后，同大多數(shù)分簇算法一樣，DSMCA采用輪方式運(yùn)行的方案，每輪包括簇頭節(jié)點(diǎn)選舉、簇形成和數(shù)據(jù)傳輸3個(gè)階段.

3.2.1 簇頭節(jié)點(diǎn)選舉階段

簇頭節(jié)點(diǎn)選舉開(kāi)始后，節(jié)點(diǎn)執(zhí)行如下步驟:

1)查看鄰居節(jié)點(diǎn)信息表，查找比自己剩余能量高的節(jié)點(diǎn)組成集合S，并建立多屬性矩陣X.如果S=?，說(shuō)明該節(jié)點(diǎn)在所有鄰居節(jié)點(diǎn)中剩余能量最大，節(jié)點(diǎn)直接進(jìn)入接收投票的狀態(tài)，并在投票過(guò)程結(jié)束后轉(zhuǎn)步驟6).

2)由式(6)和(7)對(duì)X進(jìn)行規(guī)范化處理，得到規(guī)范化屬性矩陣R.

3)由式(12)計(jì)算各屬性的權(quán)重系數(shù).

4)由式(3)計(jì)算S中每個(gè)節(jié)點(diǎn)的綜合屬性評(píng)價(jià)值.

5)由式(2)計(jì)算S中每個(gè)節(jié)點(diǎn)的票數(shù)，然后節(jié)點(diǎn)隨機(jī)生成一個(gè)退避時(shí)間，到時(shí)后首先競(jìng)爭(zhēng)信道，若成功則發(fā)送一個(gè)投票消息完成給其它節(jié)點(diǎn)的投票，在此過(guò)程中接收其它節(jié)點(diǎn)給自己的投票.

6)節(jié)點(diǎn)統(tǒng)計(jì)最終所得票數(shù)，由式(13)生成初始定時(shí)長(zhǎng)度，由式(14)設(shè)置定時(shí)器時(shí)間.

7)如果在ttimer時(shí)刻到達(dá)之前，節(jié)點(diǎn)沒(méi)有收到任何鄰居節(jié)點(diǎn)發(fā)出的簇頭節(jié)點(diǎn)當(dāng)選消息，則節(jié)點(diǎn)向所有鄰居節(jié)點(diǎn)廣播簇頭節(jié)點(diǎn)當(dāng)選消息，聲明自己當(dāng)選為簇頭節(jié)點(diǎn).所有收到當(dāng)選消息的節(jié)點(diǎn)停止計(jì)時(shí)成為普通節(jié)點(diǎn)并記錄相應(yīng)簇頭節(jié)點(diǎn)的ID.

3.2.2 簇形成階段

簇頭節(jié)點(diǎn)選舉結(jié)束后，網(wǎng)絡(luò)進(jìn)入簇形成階段.在該階段，每個(gè)普通節(jié)點(diǎn)向簇頭節(jié)點(diǎn)發(fā)送加入消息成為簇成員.普通節(jié)點(diǎn)在簇頭節(jié)點(diǎn)選舉階段可能會(huì)收到多個(gè)簇頭節(jié)點(diǎn)發(fā)送的當(dāng)選消息，此時(shí)，節(jié)點(diǎn)比較自己給每個(gè)簇頭節(jié)點(diǎn)所投的票數(shù)，向票數(shù)最高的簇頭節(jié)點(diǎn)發(fā)送加入消息.綜合屬性值大的簇頭節(jié)點(diǎn)形成的簇規(guī)模大于綜合屬性值小的簇頭節(jié)點(diǎn)，從而降低綜合屬性值小的簇頭節(jié)點(diǎn)的負(fù)擔(dān)，避免其過(guò)早失效.

在成簇過(guò)程中，如果一個(gè)簇頭節(jié)點(diǎn)存在鄰居節(jié)點(diǎn)，但其所有鄰居節(jié)點(diǎn)都選擇加入了其它簇，則該簇沒(méi)有簇成員加入，形成單節(jié)點(diǎn)簇，文獻(xiàn)［10］中將其稱為被動(dòng)型簇頭節(jié)點(diǎn).VCA和文獻(xiàn)［10］中的算法讓被動(dòng)型簇頭節(jié)點(diǎn)直接向基站發(fā)送自身數(shù)據(jù)，顯然浪費(fèi)了節(jié)點(diǎn)的能量.DSMCA采取多跳中繼方式，當(dāng)節(jié)點(diǎn)成為被動(dòng)型簇頭節(jié)點(diǎn)后，在鄰居節(jié)點(diǎn)中選取剩余能量最大的節(jié)點(diǎn)作為中繼節(jié)點(diǎn)并發(fā)送中繼消息通知被選節(jié)點(diǎn).

3.2.3 數(shù)據(jù)傳輸階段

由于網(wǎng)絡(luò)中可能存在被動(dòng)型簇頭節(jié)點(diǎn)，所以在數(shù)據(jù)傳輸階段，首先由被動(dòng)型簇頭節(jié)點(diǎn)將數(shù)據(jù)發(fā)送給中繼節(jié)點(diǎn)，然后各成員節(jié)點(diǎn)在簇頭節(jié)點(diǎn)分配的時(shí)分多址(TDMA)時(shí)隙內(nèi)將數(shù)據(jù)發(fā)送給簇頭節(jié)點(diǎn)，簇頭節(jié)點(diǎn)執(zhí)行數(shù)據(jù)融合后向基站發(fā)送一個(gè)數(shù)據(jù)包，即網(wǎng)絡(luò)完成一個(gè)數(shù)據(jù)采集周期.為避免頻繁的簇重組帶來(lái)的能量開(kāi)銷(xiāo)，網(wǎng)絡(luò)在多個(gè)數(shù)據(jù)采集周期后進(jìn)行重新分簇［14］.

3.3 屬性更新

節(jié)點(diǎn)在投票時(shí)需要鄰居節(jié)點(diǎn)的剩余能量、節(jié)點(diǎn)與鄰居節(jié)點(diǎn)間的通信代價(jià)以及鄰居節(jié)點(diǎn)與基站間的通信代價(jià)3個(gè)屬性值.在網(wǎng)絡(luò)初始化階段，節(jié)點(diǎn)通過(guò)信息交換建立了鄰居節(jié)點(diǎn)屬性信息表.假設(shè)網(wǎng)絡(luò)部署后，節(jié)點(diǎn)和基站的位置不再發(fā)生改變，故通信代價(jià)屬性在網(wǎng)絡(luò)運(yùn)行過(guò)程中不發(fā)生變化，無(wú)需進(jìn)行更新.但隨著時(shí)間的推移，節(jié)點(diǎn)的剩余能量會(huì)發(fā)生改變，這時(shí)需要節(jié)點(diǎn)之間定期交換剩余能量信息.DSMCA采取和VCA相同的方法:節(jié)點(diǎn)在每次簇重組開(kāi)始前向鄰居節(jié)點(diǎn)廣播心跳信號(hào)，在確認(rèn)鄰居節(jié)點(diǎn)存活狀態(tài)的同時(shí)，更新剩余能量屬性信息［8］.

4 仿真實(shí)驗(yàn)和結(jié)果分析

文中通過(guò)仿真實(shí)驗(yàn)來(lái)評(píng)價(jià)DSMCA的性能，采用網(wǎng)絡(luò)生命期(第一個(gè)節(jié)點(diǎn)失效的時(shí)間［15-16］)和數(shù)據(jù)傳輸效率來(lái)比較DSMCA、LEACH、HEED及VCA的性能，以驗(yàn)證DSMCA的有效性.實(shí)驗(yàn)中所用的參數(shù)設(shè)置如表1所示，采用和文獻(xiàn)［3］中相同的無(wú)線通信能耗模型及參數(shù).所有仿真均重復(fù)100次，取平均值作為最終結(jié)果.

表1 實(shí)驗(yàn)參數(shù)值Table 1 Values of simulation parameters

圖2為采用4種算法的網(wǎng)絡(luò)中存活節(jié)點(diǎn)數(shù)隨時(shí)間變化的情況.從圖2中可以看出，DSMCA的網(wǎng)絡(luò)生命期比LEACH、HEED、VCA分別提高了260%、50%和37%.其原因主要有:(1)DSMCA的投票機(jī)制采用了鄰居節(jié)點(diǎn)的多屬性信息，均衡考慮了能量和能耗因素，節(jié)點(diǎn)綜合屬性評(píng)價(jià)值越大，所得票數(shù)越多，越有機(jī)會(huì)當(dāng)選為簇頭節(jié)點(diǎn)，而LEACH沒(méi)有考慮節(jié)點(diǎn)的剩余能量信息，VCA只以節(jié)點(diǎn)的剩余能量信息為主參數(shù);(2)DSMCA簇頭節(jié)點(diǎn)選舉采用了定時(shí)驅(qū)動(dòng)方式，且節(jié)點(diǎn)只給剩余能量比自己大的節(jié)點(diǎn)投票，比采用迭代方式的HEED和VCA節(jié)省了大量消息開(kāi)銷(xiāo);(3)DSMCA中的被動(dòng)型簇頭節(jié)點(diǎn)采取多跳的方式向基站傳輸數(shù)據(jù)，減少了節(jié)點(diǎn)能耗.由圖2還可以看出，DSMCA從第一個(gè)節(jié)點(diǎn)失效到最后一個(gè)節(jié)點(diǎn)失效的時(shí)間跨度比其它3種算法更短，而時(shí)間跨度可反映出網(wǎng)絡(luò)中節(jié)點(diǎn)的能量均衡情況［5］，所以DSMCA的能量使用效率最高，更好地均衡了網(wǎng)絡(luò)中節(jié)點(diǎn)的能耗.

圖2 存活節(jié)點(diǎn)數(shù)隨時(shí)間的變化Fig.2 Changes of number of surviving nodes with time

圖3給出了基站收到的數(shù)據(jù)包數(shù)和存活節(jié)點(diǎn)數(shù)的關(guān)系.從圖3可見(jiàn)，與其它3種算法相比，DSMCA能夠使基站接收到更多的數(shù)據(jù)信息.這是因?yàn)镈SMCA的節(jié)點(diǎn)失效更為緩慢，能夠采集并傳送更多的數(shù)據(jù).

圖3 基站收到的數(shù)據(jù)包數(shù)與存活節(jié)點(diǎn)數(shù)的關(guān)系Fig.3 Relationship between number of data packets received at base station and number of surviving nodes

圖4給出了基站收到的數(shù)據(jù)包數(shù)與網(wǎng)絡(luò)能耗的關(guān)系.從圖4可以看出，在能耗相同的情況下，采用DSMCA的基站可以收到更多的數(shù)據(jù)包，整個(gè)網(wǎng)絡(luò)的能量使用效率更高.

圖4 基站收到的數(shù)據(jù)包數(shù)與網(wǎng)絡(luò)能耗的關(guān)系Fig.4 Relationship between number of data packets received at base station and energy consumption of network

5 結(jié)語(yǔ)

為了高效地利用無(wú)線傳感器網(wǎng)絡(luò)的能量，文中提出了一種基于雙重選舉機(jī)制的無(wú)線傳感器網(wǎng)絡(luò)分簇算法，該算法結(jié)合了投票選舉和定時(shí)驅(qū)動(dòng)兩種分簇機(jī)制.票數(shù)的計(jì)算均衡考慮了能量和能耗因素，借鑒了多屬性決策中求解多屬性綜合值的方法，采用熵法來(lái)計(jì)算屬性的權(quán)重系數(shù).節(jié)點(diǎn)將所得票數(shù)轉(zhuǎn)換為一個(gè)定時(shí)長(zhǎng)度參與簇頭節(jié)點(diǎn)競(jìng)爭(zhēng)，減少了消息開(kāi)銷(xiāo).在數(shù)據(jù)傳輸階段，被動(dòng)型簇頭節(jié)點(diǎn)采取多跳轉(zhuǎn)發(fā)數(shù)據(jù)的方式，節(jié)省了節(jié)點(diǎn)的能量.實(shí)驗(yàn)表明，和已有的幾種分簇算法相比，文中算法能更好地均衡節(jié)點(diǎn)能耗，延長(zhǎng)了網(wǎng)絡(luò)生存時(shí)間.今后將改進(jìn)簇形成階段的算法，使得簇頭節(jié)點(diǎn)之間的負(fù)載更加均衡，進(jìn)一步提高文中算法的性能.

［1］Fasolo E，Rossi M，Widmer J，et al.In-network aggregation techniques for wireless sensor networks:a survey［J］.IEEE Wireless Communications，2007，14(2):70-87.

［2］Akyildiz I F，Su W，Sankarasubramaniam Y，et al.A survey on sensor networks［J］.IEEE Communications Magazine，2002，40(8):102-114.

［3］Heinzelman W B，Chandrakasan A，Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks［J］.IEEE Transactions on Wireless Communications，2002，1(4):660-670.

［4］Chamam A，Pierre S.A distributed energy-efficient clustering protocol for wireless sensor networks［J］.Computers ＆Electrical Engineering，2010，36(2):303-312.

［5］孫亭，楊永田，蘆東昕，等.一種基于聚合度的動(dòng)態(tài)分層路由協(xié)議［J］.電子學(xué)報(bào)，2008，36(4):794-799.Sun Ting，Yang Yong-tian，Lu Dong-xin，et al.Convergence degree-based dynamic hierarchical routing protocol［J］.Acta Electronica Sinica，2008，36(4):794-799.

［6］Younis O，F(xiàn)ahmy 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.

［7］Dimokas N，Katsaros D，Manolopoulos Y.Energy-efficient distributed clustering in wireless sensor networks［J］.Journal of Parallel and Distributed Computing，2010，70(4):371-383.

［8］Qin M，Zimmermann R.An energy-efficient voting-based clustering algorithm for sensor networks［C］∥Proceedings of the Sixth International Conference on Software Engineering，Artificial Intelligence，Networking and Parallel/Distributed Computing and the First ACIS International Workshop on Self-Assembling Wireless Networks.Towson MD:IEEE，2005:444-451.

［9］Wen C Y，Sethares W A.Automatic decentralized clustering for wireless sensor networks ［J］.EURASIP Journal on Wireless Communications and Networking，2005，2005(5):686-697.

［10］曹涌濤，何晨，蔣鈴鴿.無(wú)線傳感器網(wǎng)絡(luò)中基于自適應(yīng)定時(shí)器策略的分簇算法［J］.電子學(xué)報(bào)，2007，35(9):1719-1723.Cao Yong-tao，He Chen，Jiang Ling-ge.A distributed timer-based clustering algorithm for wireless sensor networks［J］.Acta Electronica Sinica，2007，35(9):1719-1723.

［11］Fang S，Berber S M，Swain A K.An overhead-free clustering algorithm for wireless sensor networks［C］∥Proceedings of IEEE Global Telecommunications Conference.Washington DC:IEEE，2007:1144-1148.

［12］黃河，石為人，許磊，等.一種基于自適應(yīng)加權(quán)的無(wú)線傳感器網(wǎng)絡(luò)室內(nèi)能量均衡路由［J］.電子學(xué)報(bào)，2010，38(11):2493-2498.Huang He，Shi Wei-ren，Xu Lei，et al.Weight coefficient adaptive based indoor energy load-balance wireless sensor networks routing［J］.Acta Electronica Sinica，2010，38(11):2493-2498.

［13］徐玖平，吳巍.多屬性決策的理論與方法［M］.北京:清華大學(xué)出版社，2006:12-52.

［14］Heinzelman W B.Application-specific protocols architectures for wireless networks［D］.Cambridge:Department of Eleetrical Engineering and Computer Science，Massachusetts Institute of Technology，2000.

［15］岳林，易本順，肖進(jìn)勝，等.優(yōu)化生存時(shí)間的傳感器網(wǎng)絡(luò)地理機(jī)會(huì)路由［J］.華南理工大學(xué)學(xué)報(bào):自然科學(xué)版，2010，38(12):67-72.Yue Lin，Yi Ben-shun，Xiao Jin-sheng，et al.Geographic opportunistic routing with optimized lifetime for sensor networks［J］.Journal of South China University of Technology:Natural Science Edition，2010，38(12):67-72.

［16］Wu Y，Mao Z，F(xiàn)ahmy S，et al.Constructing maximumlifetime data-gathering forests in sensor networks［J］.IEEE/ACM Transactions on Networking，2010，18(5):1571-1584.