基于雙重選舉機制的無線傳感器網絡分簇算法*

孫中皋 鄭紫微 許少娟

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

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

LEACH算法［3］是具有代表性的分簇算法，其簇頭節點的選取方法具有隨機性且沒有考慮節點的剩余能量.在其它眾多分簇算法中［4-11］，簇頭節點的選取方法不僅考慮了節點的剩余能量，還將網絡局部范圍內節點的其它屬性信息作為簇頭節點選舉的依據，如節點度［4，6］、節點聚合度［5］、通信代價［6］和兩跳范圍內節點的拓撲信息［7］等.文獻［6］中提出的HEED算法，在選舉簇頭節點時首先以節點剩余能量作為主參數選取出候選簇頭節點，然后以簇內通信代價或度作為次參數，通過多次迭代來選取簇頭節點.文獻［8］中提出的基于投票機制的分簇算法(VCA)，節點依據剩余能量信息給鄰居節點及自身投票，通過迭代選取票數高的節點為簇頭節點.HEED算法和VCA在迭代過程中節點與鄰居節點的消息交換消耗了額外的能量.基于定時驅動機制的分簇算法［9-11］則避免了迭代過程，減少了消息開銷.文獻［10］中提出的基于定時驅動的分簇算法，節點按照負指數分布生成一個定時長度用于競爭簇頭節點，剩余能量較多的節點成為簇頭節點的機會更大.文獻［11］中提出的SWEET算法在簇頭節點選舉的兩個階段都采用了定時的方式.

結合投票機制考慮鄰居節點信息的思想和定時驅動機制消息開銷小的特點，文中提出了一種基于雙重選舉機制的分簇算法(DSMCA).投票選舉機制中考慮了節點的剩余能量、節點間及節點與基站間的通信代價3個屬性，節點所投票數取決于這3個屬性的綜合評價值，各屬性的權重系數采用信息熵的方法求得.投票結束后，節點依據所得的總票數生成一個定時長度參與簇頭節點的選舉.

1 VCA

VCA認為在簇頭節點選舉中，節點除考慮自身的能量狀態外還應考慮鄰居節點的能量信息.節點si投給節點sj的票數為［8］

式中，ej為節點sj的剩余能量，dij為節點si到節點sj的距離，R為節點的通信半徑.

VCA以節點的剩余能量為參數，而忽略了節點的相對位置信息，在選取高能量節點的同時可能會付出高的能耗代價.如圖1所示，sj和sk為si的兩個鄰居節點，采用VCA投票，當sj和sk的剩余能量相等或較為接近時，si投給這兩個節點的票數相當.因sk與si之間的距離以及sk與基站之間的距離都比sj近，si選取sk當選簇頭節點的通信代價更小，故sk應比sj得到更多的票數.

圖1 節點投票示例Fig.1 An example of node voting

2 DSMCA的雙重選舉機制

2.1 DSMCA的投票機制

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

由規則(1)可知，節點的剩余能量越大，得到的票數越多而投出的票數越少;相反，節點的剩余能量越小，投出的票數越多而得到的票數越少.規則(1)減少了剩余能量小的節點當選簇頭節點的機會，讓剩余能量大的節點處于被選舉狀態而少投票，與VCA中節點給每個鄰居節點投票相比，減少了消息開銷.由規則(2)可知，一個具有較高剩余能量的節點，其鄰居節點數越多，得到的票數越多，并且票數均衡了節點的能量和能耗因素.

基于投票規則，DSMCA的多屬性投票模型為

式中，zj為節點sj的綜合屬性評價值，

m為屬性個數，rjk為節點sj的第k個屬性的規范化值，ωk為第k個屬性的權重，滿足

由式(2)、(3)可知，要計算票數，需先確定屬性的規范化值，并為每個屬性選擇合適的權重.

2.1.1 屬性規范化

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

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

規范化后的屬性矩陣R為

將R中的屬性評價值代入式(3)，求得節點的綜合屬性評價值，就消除了屬性量綱的差異性.

2.1.2 屬性權重

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

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

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

DSMCA采用熵法求解權重，節點在投票時通過所有可投票節點的多屬性矩陣衡量各屬性的重要程度，從而決定各屬性的權重.確定權重的步驟如下:

1)對于規范化后的屬性矩陣R，計算屬性ul的幾何影射pk'l為

2)計算屬性ul的熵El為

當pk'l=0時，令pk'llnpk'l=0.

3)計算屬性ul的權重為

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

2.2 DSMCA的定時驅動機制

設節點完成投票后統計所得票數為vtotal，首先將票數轉換為參與簇頭節點競爭的初始定時長度:

式中:ε為一足夠小的常數，當vtotal=0時，節點依據ε生成定時長度;x為在［0，1］上均勻分布的隨機變量;vmax為一常數，表示節點可能得到的最大票數，若節點收到每個鄰居節點的票數都為最大值1，則vmax等于節點所擁有的最大鄰居節點數，vmax由節點的通信半徑及網絡中節點的分布密度決定.

接著節點設置定時器時間為

式(13)中，當vtotal≠0 時，令v=vtotal/vmax，則0 ＜v＜1，保證了tinitial＞0且tinitial關于v的一階偏導數?tinitial/?v=-v-1＜ 0，即隨著v的增大，tinitial單調遞減，也就是說，節點所得的選票數越多，其生成的定時長度越短.

另外，由式(13)可知，節點的初始定時長度取決于節點得到的票數vtotal和隨機變量x的取值，其中vtotal取決于鄰居節點對節點多個屬性的綜合評價值，這使得在節點通信半徑內存在與該節點具有相同票數的其它節點的概率很小，而且隨機變量x進一步降低了相鄰節點生成相同定時長度的可能性.所以，DSMCA降低了節點在競爭簇頭節點時發生沖突的概率，在簇頭節點的通信半徑內只存在一個簇頭節點，即簇頭節點在網絡中的分布相對均勻.

3DSMCA描述

3.1 網絡初始化

網絡初始化的主要任務是節點根據信號接收強度估算與發送方的距離，以便獲取通信代價屬性值及在數據傳輸時選取合適的發射功率.其中節點的通信代價屬性定義為節點向接收方發送一個數據包所需要的能量.

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

3.2 網絡運行

在網絡初始化之后，同大多數分簇算法一樣，DSMCA采用輪方式運行的方案，每輪包括簇頭節點選舉、簇形成和數據傳輸3個階段.

3.2.1 簇頭節點選舉階段

簇頭節點選舉開始后，節點執行如下步驟:

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

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

3)由式(12)計算各屬性的權重系數.

4)由式(3)計算S中每個節點的綜合屬性評價值.

5)由式(2)計算S中每個節點的票數，然后節點隨機生成一個退避時間，到時后首先競爭信道，若成功則發送一個投票消息完成給其它節點的投票，在此過程中接收其它節點給自己的投票.

6)節點統計最終所得票數，由式(13)生成初始定時長度，由式(14)設置定時器時間.

7)如果在ttimer時刻到達之前，節點沒有收到任何鄰居節點發出的簇頭節點當選消息，則節點向所有鄰居節點廣播簇頭節點當選消息，聲明自己當選為簇頭節點.所有收到當選消息的節點停止計時成為普通節點并記錄相應簇頭節點的ID.

3.2.2 簇形成階段

簇頭節點選舉結束后，網絡進入簇形成階段.在該階段，每個普通節點向簇頭節點發送加入消息成為簇成員.普通節點在簇頭節點選舉階段可能會收到多個簇頭節點發送的當選消息，此時，節點比較自己給每個簇頭節點所投的票數，向票數最高的簇頭節點發送加入消息.綜合屬性值大的簇頭節點形成的簇規模大于綜合屬性值小的簇頭節點，從而降低綜合屬性值小的簇頭節點的負擔，避免其過早失效.

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

3.2.3 數據傳輸階段

由于網絡中可能存在被動型簇頭節點，所以在數據傳輸階段，首先由被動型簇頭節點將數據發送給中繼節點，然后各成員節點在簇頭節點分配的時分多址(TDMA)時隙內將數據發送給簇頭節點，簇頭節點執行數據融合后向基站發送一個數據包，即網絡完成一個數據采集周期.為避免頻繁的簇重組帶來的能量開銷，網絡在多個數據采集周期后進行重新分簇［14］.

3.3 屬性更新

節點在投票時需要鄰居節點的剩余能量、節點與鄰居節點間的通信代價以及鄰居節點與基站間的通信代價3個屬性值.在網絡初始化階段，節點通過信息交換建立了鄰居節點屬性信息表.假設網絡部署后，節點和基站的位置不再發生改變，故通信代價屬性在網絡運行過程中不發生變化，無需進行更新.但隨著時間的推移，節點的剩余能量會發生改變，這時需要節點之間定期交換剩余能量信息.DSMCA采取和VCA相同的方法:節點在每次簇重組開始前向鄰居節點廣播心跳信號，在確認鄰居節點存活狀態的同時，更新剩余能量屬性信息［8］.

4 仿真實驗和結果分析

文中通過仿真實驗來評價DSMCA的性能，采用網絡生命期(第一個節點失效的時間［15-16］)和數據傳輸效率來比較DSMCA、LEACH、HEED及VCA的性能，以驗證DSMCA的有效性.實驗中所用的參數設置如表1所示，采用和文獻［3］中相同的無線通信能耗模型及參數.所有仿真均重復100次，取平均值作為最終結果.

表1 實驗參數值Table 1 Values of simulation parameters

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

圖2 存活節點數隨時間的變化Fig.2 Changes of number of surviving nodes with time

圖3給出了基站收到的數據包數和存活節點數的關系.從圖3可見，與其它3種算法相比，DSMCA能夠使基站接收到更多的數據信息.這是因為DSMCA的節點失效更為緩慢，能夠采集并傳送更多的數據.

圖3 基站收到的數據包數與存活節點數的關系Fig.3 Relationship between number of data packets received at base station and number of surviving nodes

圖4給出了基站收到的數據包數與網絡能耗的關系.從圖4可以看出，在能耗相同的情況下，采用DSMCA的基站可以收到更多的數據包，整個網絡的能量使用效率更高.

圖4 基站收到的數據包數與網絡能耗的關系Fig.4 Relationship between number of data packets received at base station and energy consumption of network

5 結語

為了高效地利用無線傳感器網絡的能量，文中提出了一種基于雙重選舉機制的無線傳感器網絡分簇算法，該算法結合了投票選舉和定時驅動兩種分簇機制.票數的計算均衡考慮了能量和能耗因素，借鑒了多屬性決策中求解多屬性綜合值的方法，采用熵法來計算屬性的權重系數.節點將所得票數轉換為一個定時長度參與簇頭節點競爭，減少了消息開銷.在數據傳輸階段，被動型簇頭節點采取多跳轉發數據的方式，節省了節點的能量.實驗表明，和已有的幾種分簇算法相比，文中算法能更好地均衡節點能耗，延長了網絡生存時間.今后將改進簇形成階段的算法，使得簇頭節點之間的負載更加均衡，進一步提高文中算法的性能.

［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］孫亭，楊永田，蘆東昕，等.一種基于聚合度的動態分層路由協議［J］.電子學報，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，Fahmy 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］曹涌濤，何晨，蔣鈴鴿.無線傳感器網絡中基于自適應定時器策略的分簇算法［J］.電子學報，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］黃河，石為人，許磊，等.一種基于自適應加權的無線傳感器網絡室內能量均衡路由［J］.電子學報，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］.北京:清華大學出版社，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］.華南理工大學學報:自然科學版，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，Fahmy S，et al.Constructing maximumlifetime data-gathering forests in sensor networks［J］.IEEE/ACM Transactions on Networking，2010，18(5):1571-1584.