基于模糊理論的無線傳感器網絡簇首選舉算法

陶志勇，蔣守鳳

（遼寧工程技術大學a.電子與信息工程學院；b.研究生學院，遼寧葫蘆島125105）

·移動互聯與通信技術·

基于模糊理論的無線傳感器網絡簇首選舉算法

陶志勇a，蔣守鳳b

（遼寧工程技術大學a.電子與信息工程學院；b.研究生學院，遼寧葫蘆島125105）

無線傳感器網絡中分簇協議算法按輪工作，但多數分簇算法每輪都要進行簇首選舉，造成網絡節點能量消耗過多，而且占用大量時間。針對該問題，提出基于模糊理論的無線傳感器網絡簇首選舉算法。在網絡部署階段確定簇首競爭半徑，保證簇首均勻分布。在簇首選舉階段，通過與簇首競爭半徑內節點的通信，構造節點鄰域表，采用模糊理論綜合評判法生成簇首序列，節點依據序列次序輪流擔任簇首。簇建立完成后，簇首采用多跳方式與Sink通信，均衡遠近簇首的能耗。仿真結果表明，該算法可降低網絡節點的能量消耗，延長網絡生存時間。

無線傳感器網絡；分簇算法；模糊理論；競爭半徑；簇首序列；多跳路由

1 概述

無線傳感器網絡（Wireless Sensor Netw ork，WSN）作為新型的自治測控網絡，通過隨機部署各類微型傳感器來協同感知、采集和處理網絡監測區域內的感知數據［1］，最終以多跳方式通過無線自組網將感知到的信息傳輸至Sink節點。傳感器網絡執行具體任務時，完成的質量由網絡生存時間、網絡負載平衡性等網絡性能決定。

在無線傳感器網絡中，分簇路由算法相比平面路由算法具有更好的節能性［2］，基于簇的路由協議是研究的重點。大量的研究表明，分簇路由算法可較大限度地降低網絡中的數據通信量、節約節點的能量消耗，是延長網絡壽命的有效方法［3］。網絡建立時，通過分簇算法將網絡劃分為邏輯上的若干個簇，每個簇由一個簇首和若干成員節點組成，各成員節點負責采集、處理和向簇首傳遞數據，簇首負責管理簇內資源分配和簇間的通信［4］。是否合理的簇首選舉方法和簇間通信模式能夠決定網絡的總體性能是否可靠。

本文提出基于模糊理論的無線傳感器網絡簇首選舉算法（Cluster Head election algorithm in WSN Based on Fuzzy Theory，CHBFT）。在網絡部署階段，根據區域面積和網絡節點數等確定監測區域最佳簇首個數，再通過公式計算出簇首競爭半徑；在簇首選舉階段，構造節點鄰域表，利用模糊理論綜合評判法選取簇首，并廣播其作為簇首的信息；在簇建立階段，普通節點選擇相距最近的簇首加入簇，傳輸自身ID和評判結果值，由簇首建立一個簇首序列（簇首可選度），簇內節點按照該序列輪流作簇首；最后采用簇首間多跳路由的方法將數據傳輸至Sink節點，實現簇首與Sink節點的理想通信。

2 相關工作

簇結構在很大程度上影響著網絡的性能，因此，對無線傳感器網絡分簇算法的研究在幫助提高網絡整體性能方面有著重要的意義。分簇路由協議思想源于LEACH算法［5］，它的成簇方法貫穿于之后被提出的眾多層次路由協議中，很多文獻對簇組織問題進行了專門研究，如LEACH-E［6］，TEEN［7］和HEED［8］算法等，以上算法通過對簇首選舉的方式進行的改進，實現了簇首在監測區域內的合理、均勻分布。

而后被提出的各種分簇算法在選舉簇首時更是將節點剩余能量、節點聚合度及節點地理位置等因素作為參考條件。由于無線傳感器網絡的規模與拓撲結構的不斷變化，網絡中各類因素對網絡壽命的影響是無法確定的，具有一定的模糊性，那么在分簇過程中節點是否能夠勝任簇首這一要職也具有模糊性。事物的模糊性是指邊界不清楚，含義在表達時不能明確的區別是和非，在論域上無法劃分他的界限。這種模糊性與無線傳感器網絡分簇算法中多因素制約簇首選舉上十分契合［9］，針對于此，本文將模糊聚類的思想應用于WSN分簇算法的研究［10］。

3 CHBFT算法

CHBFT算法與LEACH分簇算法相同，共分為3個階段：簇首選舉，簇建立，簇間通信。而在簇首選舉階段哪些因素作為模糊理論綜合評判法的參數是考慮的重點：

（1）剩余能量。

網絡節點的剩余能量值是節點能否工作的先決條件，無論是傳輸數據還是廣播信息，都需要消耗節點的存儲能量，節點剩余能量多少直接影響著其工作時間的長短。

（2）到Sink節點距離及到鄰居節點的距離均值。

由能量消耗模型［11］看出，發送數據的能量消耗與通信節點間距離成反比。通信距離越短，能量消耗則越低，對發送數據的節點具有節省能量的作用；那么無論是到Sink節點的通信距離還是到鄰居節點的通信距離，其值越小越有利。

通過以上分析可知，利用模糊理論綜合評判法對簇首選舉的因素值為：節點剩余能量值，到Sink節點距離倒數值以及到鄰居節點距離均值倒數值。

3.1 簇首選舉

3.1.1 網絡最佳簇首個數及簇首競爭半徑

在網絡部署階段，Sink節點用一個特定的發送功率向監測區域廣播一個信號，網絡中的傳感器節點在接收到該信號后，根據接收信號的強度計算它到Sink節點的近似距離dχ-ch（χ為各節點ID編號）。此時可知網絡區域邊長M、網絡節點數目N及區域內節點到Sink節點的最大、最小距離。

根據文獻［12］可知，網最優簇首數mK值的計算公式為：

其中，εfs和εamp分別表示信號放大器在自由空間模型和多路衰減模型下將1 bit數據傳送單位距離時的能量消耗。通過式（1）可計算出網絡最優簇首數目的范圍；簇首競爭面積Sch近似為網絡總面積與簇首個數的比值，即：

3.1.2 節點信息獲取

之后監測區域中節點在簇首競爭半徑范圍內廣播其ID、位置信息、剩余能量及到Sink節點的距離，所有的競爭半徑內鄰居節點都會收到該信息，建立一個節點鄰域表。節點再計算到所有鄰居節點的距離及距離均值。節點鄰域表如表1所示。

表1 節點鄰域表

3.1.3 簇首選舉

在簇首選舉過程，CHBFT算法采用模糊理論的綜合評判法選舉簇首，首先要確定各因素的隸屬函數，建立隸屬度，再與參數權重集加權平均得出簇首可選度。

（1）隸屬函數與隸屬度

通過分析可知，節點的剩余能量越多、距離Sink節點越近，與鄰居節點距離均值越小，越是簇首的最佳選擇。本文采用如下隸屬函數的計算方式，將各參數歸為0～1的數值：

剩余能量的隸屬函數為：

其中，R_Ei為節點i的剩余能量；Einit為網絡節點的初始能量。

到Sink節點距離倒數的隸屬函數為：

其中，di-ch為節點i到Sink節點的距離；和為網絡中節點到Sink節點距離倒數的最大值和最小值。

到鄰居節點的距離均值的隸屬函數為：

其中，di-avg為節點i到所有鄰居節點距離的平均值；與為與鄰居節點相距均值倒數最小值及最大值。

節點通過以上3項參數隸屬函數得到節點的隸屬度Q：

（2）綜合評判

B=（bχ，…，by）為簇首選舉的綜合評判標準，也為簇首可選度；A=（a1，a2，a3）為3項參數的權重集，利用加權平均模型計算：

3.2 簇建立

成為簇首的節點向普通節點廣播自己成為簇首的信息，普通節點利用接收到的簇首廣播信息，計算出與自己距離最近的簇首，然后向該簇首發送請求加入簇的消息，待簇首再次返回一個確認成功加入的消息，則該節點加入簇成功。當網絡中所有節點均成功加入簇，簇建立階段完成。

同時各簇簇首更新其節點鄰域表中簇內成員的簇首可選度，生成一個簇首序列，以便下面“輪”時簇首選擇。

3.3 簇首間多跳路由

在簇首將數據傳輸到Sink節點這個階段，簇首對簇成員的數據進行融合處理，然后將數據以多跳通信的方式發送至Sink點。

由于網絡中各簇首距離Sink的距離不同，距離較近的簇首傳輸數據的能量消耗低，距離較遠的簇首傳輸數據時能量消耗較高［13］，因此本文采取簇間多跳路由的方式，讓距Sink節點較近的簇首協助距Sink節點較遠的簇首，以此平均各簇首傳遞數據時的能量差距。

引入閾值若簇首到Sink節點的距離小于d′，則它直接與Sink節點進行通信；否則該簇首以較大的功率向全網簇首廣播一條消息，包含其ID、當前剩余能量和它到匯聚點的距離，選擇一個簇首節點協助他進行簇間多跳傳輸。網絡中簇首j收到簇首i廣播的消息，則計算出它們之間的近似距離。假設簇首j是簇首i向Sink節點傳輸數據的中繼節點，則2個節點的能量消耗為：

直觀上看，若網絡中節點j位于節點i與Sink節點之間，這是鏈路能量消耗較小，則有利于節約能量。為了綜合考慮網絡節點的剩余，本文的簇間路由策略為：節點i在網絡中所有可以通信的簇首節點中，在小的2個節點中，選擇剩余能量最高的節點作為其路由的下一跳節點。

當數據傳輸完成，簇首通知在簇首可選度中值僅低于自身的節點為下一輪簇首，該簇首接到信息后，廣播自身為簇首的信息，首輪該簇成員則將數據傳遞給該簇首，再進行一輪數據的傳輸。

4 仿真結果與分析

為了驗證本文提出的路由算法的網絡性能，對LEACH算法、HEED算法和CHBFT算法進行比較。仿真中所用的參數如表2所示。

表2 仿真參數

網絡仿真環境如圖1所示，其中網絡中工作節點分布于100 m×100 m的區域內，Sink節點遠離網絡區域。

圖1 網絡仿真環境

4.1 網絡簇首數目

參考式（1），結合網絡仿真參數，可計算出：1≤mK≤6.2。另根據文獻［14］，對網絡環境進行仿真可見，當簇首數為5時，協議每一輪網絡平均消耗的能量相對最少；同時，此時網絡出現首個死亡節點以及全部節點死亡的輪數相對最多。由此可知，在本文設置的仿真環境下，簇首個數為5時，網絡各方面性能較為理想，可作理想簇首個數。再由式（2）計算出，簇首競爭半徑為R=25.3 m。

本文對LEACH算法、HEED算法和CHBFT算法200輪運行過程中簇首個數進行匯總，LEACH算法、HEED算法的簇首個數如圖2和圖3所示。

圖2 LEACH算法中簇首個數分布

圖3 HEED算法中簇首個數分布

CHBFT算法每輪簇首數目均與首輪數目相同，通過多次仿真，簇首數目集中于5或者6。

LEACH算法的不足之處就在于簇首隨機產生，簇首數目不穩定，且數目也不能保證接近最優簇首個數；HEED算法通過各節點間動態交換信息來控制了簇首個數，保證簇首數目多處于理想簇首數，但是在動態交換過程中造成大量能量消耗；CHBFT算法通過競爭半徑來控制簇首數目，而且首輪簇建立后，接下來“輪”的簇首數目將不會改變，因此，簇首數目更加穩定。

4.2 簇首能量消耗

簇首的能量消耗對網絡整體性能的影響非常大，它肩負收集、融合簇內成員數據，更需要將最終數據傳遞給Sink節點，無論是在數據量方面還是在傳輸距離方面都比普通節點更加耗能。為了驗證CHBFT算法在簇首耗能方面上的優越性，從仿真中隨機選取10輪中的簇首能耗，結果見圖4。

圖4 簇首消耗能量總和

對于簇首數目時常過多的LEACH算法，簇首能耗自然最大；HEED算法簇首數目與CHBFT算法簇首數目相差不大，但是CHBFT算法存在首“輪”產生簇首序列、以后“輪”無須廣播的優勢，無請求加入、確認加入簇的重復過程，在一定程度上節省了簇首及普通節點的能耗。

4.3 網絡生存壽命

網絡壽命定義為整個無線傳感器網絡里第一個傳感器節點的能量完全消耗完時的時間。表3為3種算法網絡壽命的比較。

表3 3種算法的網絡壽命比較

由于CHBFT算法減少了每輪廣播、重組簇的能耗及采用多跳簇間路由方式均衡簇首能耗，因此網絡節點的生存壽命更加長久。

5 結束語

在無線傳感器網絡分簇算法中，簇首的選取決定了整個網絡的性能。鑒于簇首選取過程中多因素的不確定性，本文提出基于模糊理論的無線傳感器網絡簇首選舉算法。該算法使各節點在競爭半徑內交換自身信息，構造節點鄰域表，計算出簇首可選度，生成簇首序列，然后選舉可選度最高的節點做簇首，形成無線網絡的層次結構。仿真結果表明，與LEACH算法以及HEED算法相比，CHBFT算法每輪產生的簇首數目集中于該網絡環境下的理想簇首數目，可保證網絡平均能量消耗少；同時簇首能量消耗更少，能有效延長無線傳感器網絡的生命周期。

［1］ Akyildiz IF，Su W，Sankarasubram aniam Y，et al.A Survey on Sensor Networks［J］.IEEE Communications Magazine，2002，40（8）：102-114.

［2］ 解志斌，于 謙，沈 斌，等.一種新的基于粒子群優化的雙簇頭分簇路由算法［J］.傳感技術學報，2013，26（8）：1135-1139.

［3］ 蘇金樹，郭文忠，余朝龍，等.負載均衡感知的無線傳感器網絡容錯分簇算法［J］.計算機學報，2014， 37（2）：445-456.

［4］ 劉 群，白全煒，曾憲華，等.能量感知的WSN節點分類控制路由算法［J］.傳感技術學報，2011，24（7）：1053-1059.

［5］ Heinzelman W，Chandrakasan A，Balakrishnan H.Energy Efficient Communication Protocol for Wireless Sensor Networks［C］//Proceedings of Hawaii International Conference on System Sciences.Hawaii，USA：IEEE Press，2000：1-10.

［6］ Heinzelman W，Chandraksan A，Balakrishnan H.An Application-specific Protocol Architechture for Wireless Micro-sensor Networks［J］.IEEE Transactions on Wireless Communications，2002，1（4）：660-670.

［7］ M anjeshwar A，Grawal D P.TEEN：A Protocol for Enhanced Efficiency in Wireless Sensor Networks［C］// Proceedings of the 15th Parallel and Distributed Processing Symposium.San Francisco，USA：IEEE Computer Society，2001：2009-2015.

［8］ Younis O，Fahm y S.HEED：A Hybrid Energy-efficient Distributed Clustering Approach for Ad Hoc Sensor Networks［J］.IEEE Transactions on Mobile Computing，2004，3（4）：660-669.

［9］ Degrauwe D，Roeck G D，Lombaert G.Uncertainty Quantification in the Dam age Assessment of a Cablestayed Bridge by Means of Fuzzy Numbers［J］. Computers&Structures，2009，87（17）：1077-1084.

［10］ 張海娟.基于蟻群算法的無線傳感器網絡分簇路由算法［D］.西安：西北大學，2010.

［11］ 田 勇，唐禎安，喻 言.能量均衡的室內無線傳感器網絡自適應分簇路由算法［J］.電子與信息學報，2013，35（12）：2992-2998.

［12］ 張 品，徐智福，孫 巖.一種新的基于簇頭優化的WSN路由協議［J］.傳感技術學報，2009，22（7）：1013-1017.

［13］ 孫 亭，楊永田，蘆東昕，等.一種基于聚合度的動態分層路由協議［J］.電子學報，2008，36（4）：794-799.

［14］ 蔣 陽，孫柳林，敖文鈞，等.WSN中LEACH路由協議簇頭數優化研［J］.計算機應用研究，2010，27（11）：4251-4253.

編輯金胡考

C luster Head Election Algorithm in Wireless Sensor Network Based on Fuzzy Theory

TAO Zhiyonga，JIANG Shoufengb
（a.School of Electronic and Information Engineering；b.Institute of Graduate，Liaoning Technical University，Huludao 125105，China）

Wireless Sensor Network（WSN）clustering algorithm works by‘round'.M any clustering algorithms carry out cluster head election in each round，causing excessive energy and time consumption.For this problem，this paper proposes Cluster Head election algorithm in WSN Based on Fuzzy Theory（CHBFT）.It determines the competition radius of cluster head in the network deployment phase to ensure the uniform distribution of cluster heads.In cluster head election phase，it communicates with the node in the com petition radius and structure node's neighborhood list，then uses fuzzy comprehensive evaluation method to generate a sequence of cluster heads，based on the sequence nodes become clusters in line.After the establishment of the clusters，the clusters use multi-hop to communicate with Sink to balance the energy consumption of cluster heads in different distance.Simulation results show that network energy consumption can be reduced and network survival time is extended by this algorithm.

Wireless Sensor Network（WSN）；clustering algorithm；fuzzy theory；com petition radius；sequence of cluster head；multi-hop routing

陶志勇，蔣守鳳.基于模糊理論的無線傳感器網絡簇首選舉算法［J］.計算機工程，2015，41（9）：115-119.

英文引用格式：Tao Zhiyong，Jiang Shoufeng.Cluster Head Election Algorithm in Wireless Sensor Network Based on Fuzzy Theory［J］.Computer Engineering，2015，41（9）：115-119.

1000-3428（2015）09-0115-05

A

TP393.02

10.3969/j.issn.1000-3428.2015.09.020

陶志勇（1978-），男，副教授、博士研究生，主研方向；多媒體通信；蔣守鳳，碩士研究生。

2014-09-29

2014-10-31 E-m ail：jsf_0116@163.com