基于分層的WSN非均勻模糊分簇路由

許 韻

（銅陵市公安局，安徽 銅陵 244000）

基于分層的WSN非均勻模糊分簇路由

許 韻

（銅陵市公安局，安徽 銅陵 244000）

基于分簇拓撲的無線傳感器網絡中常出現的“熱區”問題，文章提出一種非均勻分簇的無線傳感器網絡多跳路由協議，基本思路是將網絡劃分為寬度不等的層來構建非均勻的簇，路由算法按輪運行。結合剩余能量和密集度，利用Mamdani模糊推理進行層內的簇首選擇，構建層間路由樹讓簇首以多跳方式與基站進行通信。仿真結果表明該算法能夠有效緩解“熱區”問題，延長網絡存活時間。

無線傳感器網絡；非均勻分簇；能耗均衡；模糊分簇

無線傳感器網絡（Wireless Sensor Network，WSN）路由協議中，基于分簇的層次路由方法被認為是眾多方法中最有利于節能的方法之一。近來的研究表明在簇首和基站通信時采取多跳的方式更有助于節約能量[5]。但是采取多跳的方式轉發數據，使得越靠近基站的簇首節點，因轉發頻率過高而導致“熱區”(Hot Spot)問題，使得靠近基站的簇首節點能量迅速耗盡而影響網絡存活時間。鑒于此，有很多者提出以非均勻分簇(Unequal Clusters)的方式來解決此問題[1][2][5]。

文獻中首次提出采用非均勻分簇方法UCS[1]來平衡負載。在EECS[2]和EEUC[5]協議中，越靠近基站節點的簇規模越小，使得簇內能量的消耗減少，用于補償簇間轉發數據時的能量消耗；同時創造較多的簇個數，提供更多的轉發簇首選擇。因此可緩解“熱區”問題。本文在前人的基礎上，提出一個基于層次的非均勻分簇路由算法。算法通過將網絡先劃分為若干寬度不等的層次結構來建立大小不等的簇。在簇首的競爭中，參照文獻[4]的做法，利用模糊推理系統計算量低的特點，以剩余能量、鄰節點數作為系統輸入，以節點成為簇頭機會作為系統輸出。利用模糊推理規則，將簇首選擇轉化為模糊推理。以此來組織更適合大小的簇來節約能量。仿真結果表明，我們提出的算法，對于平均分散節點能耗與增加網絡壽命，具有明顯的改善。

1．網絡模型

無線傳感器網絡由N個隨機部署的傳感器節點組成，具有如下性質：

（1）在感測區域的外圍遠方設置一基站（BS），傳感器節點和基站在部署后均不再發生位置移動。

（2）所有傳感器節點具備數據融合的功能，每個節點都有一個唯一的標識(ID)。

（3）若已知發射功率，傳感器節點可以根據接收信號的強度計算出發送方距自己的近似距離。

（4）傳感器節點可以根據它與接收方的距離自由調整發射功率。

我們使用文獻[3]中提出的無線電通信模型。該模型中，節點在距離d上傳輸l比特數據時，發射能耗為：

其中，ETx(l,d)表示傳送l比特的數據到距離為d位置的節點所需消耗的能量；ERx(l)則表示節點接收l比特的數據所需的能量消耗；ETx-elec、ERx-elec、及 ETx-amp則分別表示傳送、接收與放大傳輸信號所需消耗的功率。此外，我們假設每個簇首將消耗EDA的能量來進行數據融合。

2.基于非均勻分簇的路由協議

2.1 層次的建立

在網絡部署階段，基站在覆蓋范圍內廣播hello消息將整個網絡劃分為n個不等寬度的層。如圖1所示。hello消息的格式如圖2所示。基站依式（3）計算每個層的上界UB和下界LB，R0為所設定最遠層的下界。

圖 2 “hello”消息格式

UBi為第i層的上界，LBi為第i層的下界。Ui為第i層的寬度，本文定義U0為網絡邊界與基站間的距離。網絡中各節點依接收到消息的信號強度計算出其到基站的近似距離并確定其層次。實現偽代碼如下。

2.2 非均勻分簇的路由算法

本文算法按輪運行，每輪分為成簇階段和穩定的數據傳輸階段，在成簇階段首先將每層的節點組織成簇，然后構造路由樹。在數據傳輸階段，節點在分配的時隙內把采集到的數據傳與簇首。簇首將接收簇內節點發送來的數據并對數據進行融合處理，然后送往基站。在持續一段時間以后，轉入下一輪，重新選擇簇首。

2.2.1 成簇算法

各層中簇首的選擇以節點的剩余能量和鄰居節點數為依據。首先，在網絡中預先設定一個[0,1]內閾值T,用來控制參加簇首競選的節點比例。每一輪，節點在[0,1]內選取一隨機值，如果該值小于T，則此節點成為簇首的候選節點，候選節點根據模糊推理規則計算自己的chance，然后以Rc(Rc=(UBk-LBk)/2)為通信半徑廣播一個Candidate_MSG，包括節點自身標識，節點的chance和層標識k。之后節點等待來自同層其他節點發送的Candidate_MSG，等待一段時間后，若沒有其他節點的chance大于自身的chance。則宣布簇首競選獲勝并廣播一個ClusterHead_MSG。相同層的非簇首節點在收到ClusterHead_MSG后選擇離自己最近的簇首并向該簇首發送Cluster_Join_MSG。成簇算法的偽碼如下:

2.2.2 模糊變量和模糊規則

剩余能量包含“Low、Medium、High”3 個模糊集；鄰節點數包含“Little、Medium、Many”3 個模糊集；節點成為簇頭機會 包 含 “Very Low、Low、Rather Low、Med Low、Med、Med High、Rather High、High、Very High”9 個模糊集。對于隸屬度函數的選擇，根據專家經驗“Medium”選擇三角形隸屬函數，其他則選擇Z形隸屬函數。節點剩余能量為初始能量與消耗能量的差值，消耗能量主要包括節點的通信和計算能量，通常認為通信能耗比計算能耗大3個數量級。因此，簇首主要根據接收到的節點數據包估計簇內節點剩余能量。鄰節點數為處于節點以Rc為通信半徑的通信范圍內且屬同層的節點數。模糊規則由專家經驗確定，通常剩余能量低、鄰節點數目多的節點成為簇頭的機會小；反之，當選簇頭機會大。每個輸入模糊變量包含3個模糊集，利用“if-then”語句構建模糊規則，用“and”連接前項條件，則該模糊系統共有32=9條規則。具體的模糊規則庫見表1。

表1模糊規則庫

在建立了輸入輸出變量及其隸屬度函數構造完模糊規則后，即可執行模糊推理。本文采用“極大-極小”合成為模糊推理規則，模糊推理算法為Mamdani算法，去模糊化方法為面積中心法。

2.2.3 路由樹的建立

簇建立后，每個層中的所有簇首在其通信半徑內廣播RELAY_MSG（CHid，k，Eres，Dist to BS）。每個簇首收到來自其他簇首的RELAY_MSG后，會比較k值，挑選來自上層簇首并根據其發送的消息強度計算自身與該簇首的距離，依式（4）計算每個中繼簇首的成本TCj。

選取TC成本最小的簇首為其到基站的中繼節點。簇首節點挑選中繼節點的相關算法的偽碼如下：

3．仿真結果

本文利用MATLAB對本文路由算法與LEACH和EEUC進行仿真分析比較。假設采用理想的MAC協議，忽略無線鏈路中可能發生的丟包，碰撞錯誤，仿真實驗參數如表2所示。所有仿真結果都是模擬10次的均值。

表2仿真參數

圖3顯示的是網絡中存活的節點數目隨時間變化的情況。圖4顯示的是3種協議所生成的簇首在一輪中所消耗的能量之和。從實驗中隨機選取10輪，統計各輪中所有簇首消耗的能量。

由圖3中可以看出，本文提出的協議，在第一個節點死亡時間上，較EEUC延遲約68.4~123.5%；而在半數節點死亡時間點，較EEUC改善約21.3~34.3%。且整體網絡壽命也有所延長。由圖4可以看出，本文算法和EEUC都采用多跳通信的方式，在簇首能耗上都大大低于LEACH。由于本文的方法在簇首的競爭上，綜合考慮了剩余能量及其鄰居節點數對簇首能耗的影響，在簇首挑選中繼簇首的過程中考慮了中繼簇首的剩余能量與傳輸距離，來避免同一簇首疲于替其它簇首進行數據轉發，有效地平衡了簇首的能耗。故其各方面性能優于EEUC協議。

4．結束語

本文提出了一個基于層的非均勻分簇路由協議。首先將網絡劃分成寬度不等的層，以此來構建非均勻簇。在簇形成階段，考慮剩余能量以及鄰居節點數，基于模糊推理規則來產生簇首，進而組織更適當的簇來均衡負載。接著讓簇首以多跳的方式與基站進行通信，進一步平衡熱區的能耗。仿真結果顯示，我們提出的方法相較于過去的一些相關研究，確實可改善網絡中熱區能耗不均的現象，延長網絡壽命。

［1］Soro S,Heinzelman W.Prolonging the lifetime of wireless sensor networks via unequal clustering[C].Proceedings of the 5th International Workshop on Algorithms for Wireless,Mobile,Ad Hoc and Sensor Networks,Denver,CO,2005.

［2］Ye M,Li C F,Chen G H,Wu J.An Energy-Efficient Clustering Scheme in Wireless Sensor Networks[C].Proceedings of IEEE Int’l Performance Computing and Communications Conference,2005:535-540.

［3］Heinzelman W,Chandrakasan A,Balakrishnan H．Energy-Efficient Communication Protocol for Wireless Microsensor Networks[C].Proceedingsofthe33rdHawaiiInternationalConference onSystemSciences,2000.

［4］GuptaI,RiordanD,SampalliS.Cluster–headElectionusingFuzzy Logic for Wireless Sensor Networks[C].Communication Networks and Services Rearch Conference,2005:255-260.

［5］李成法，陳貴海．一種基于非均勻分簇的無線傳感器網絡路由協議[J]．計算機學報，2007，30(1):88-91.

Unequal fuzzy Clustering Protocol for Wireless Sensor Networks Based on Level Model

Xu Yun
（Tongling Public Security Bureau,Tongling Anhui,244000,China）

In order to alleviate the"hot spot"problem for Wireless Sensor Network base on clustering.We proposed an unequal clustering routing protocol for wireless sensor network.We assume that network is divided in to n radial level with the BS at the center to build the unequal clusters.Algorithm is running by round.First,it takes the residual energy and intensity as the important index;use the fuzzy inference system to selection cluster head in every level.The cluster head to communicate with the base station by multi-hop way.Simulation results show that the algorithm can effectively alleviate the"hot spot"issues,and extend the network lifetime.

Wireless Sensor Network;uneven clustering;energy balance;fuzzy clustering

TP331

A

1672-0547（2011）05-0101-03

2011－08-15

許 韻（1978-），男，銅陵市公安局網監支隊一級警司。