基于ZigBee技術的分簇算法研究

賴 毅，唐 毓

（1.四川省電力公司 簡陽電業局，簡陽 641400；2.四川省電力公司 成都電業局，成都 610031）

0 引言

無線傳感器網絡(Wireless Sensor Network，WSN)是傳感器技術、無線通信技術 計算機技術、嵌入式計算技術結合的產物。利用分布在監測區域中的多個傳感器節點，WSN能夠感知、監測和采集相關環境或對象的信息。這些信息經過融合之后以多跳中繼的方式傳遞到用戶終端，供用戶決策使用。WSN改變了人與自然界交互的方式，它在環境監測、軍事國防、城市管理、搶險救災等領域有很高的實用價值。無線傳感網絡的體系結構如圖1所示[1]。

圖1 無線傳感網絡體系

1 ZigBee網絡體系結構

ZigBee網絡是一種無線自組織的網絡，網絡中的節點之間通過單跳或者多跳的方式進行相互通信，在網絡構成上，靈活多變，整個網絡支持多種拓撲結構[2]，在組網方式上，常見的有三種不同類型的網絡，包括星狀網、樹狀網以及網狀網。

2 ZigBee路由協議簡介

現有的ZigBee協議主要采用的泛洪的模式[3]。協調器廣播一個消息給網內他所能到達的節點，如圖2所示，源節點S如果要向目的節點D發送消息，首先源節點S會想其相鄰的節點A、B廣播一個消息，當節點A、B收到消息再轉發給他們的鄰居節點C，由于C是A、B節點共用的鄰居節點，根據協議，C節點將拋棄后面所接收到的相同的消息，直到消息傳送到目的節點D，當D收到消息后，再按原路徑返回給源節點S，當源節點S收到消息后再按ZigBee協議中規定的路由方式選擇最好的路徑到目的節點D[4]。

圖2 ZigBee路由選擇方式

綜合上面的分析，發現ZigBee的泛洪方式雖然實現起來比較簡單，不需要去維護路由而消耗很大的能量，但是總體來說也存在一些問題，比如“熱點”問題，對數據的丟包率有很大的影響，為了讓ZigBee網絡發揮到更大的作用，我們就必須自己設計協議，對ZigBee的網絡按一定的方法進行分簇設計，解決上面提到的問題。一個典型的網絡分簇拓撲結構如圖3所示。

圖3 典型的分簇拓撲結構圖

3 算法設計

3.1 網絡模型

本協議規定所有節點都分布在一定規模的區域，然后我們通過一個圓將所有節點包圍在里面。該協議的運行前提是在以下四個條件下進行。

1）網絡中的所有節點被包含在一個圓形的區域內，并且位置都不變，每個節點通過坐標節點都能計算出自己的位置；

2）節點的發射和接收功率足夠的大，可以直接單跳與網絡中的所有節點直接通信；

3）每個節點都要具備數據融合的能力；

4）網絡中每個節點的初始能量相同。

3.2 簇的具體劃分

由于協調器節點的能量是無限的，本協議采用集中式方法對節點進行分簇以及簇頭的選取，當網絡初始化時，協調器節點集中式的對整個區域根據一定的規則進行簇的劃分。大體的劃分是規則是：以協調器為中心，建立一個二維坐標軸，并在坐標軸的兩端各布置一個參考節點，每個參考節點已知自己在坐標軸上的相對位置，在開始時我們可以對節點位置進行固化，根據監控區域的大小進行設置，圓形區域半徑為R，然后通過定位方法得到每個節點的坐標位置，在對節點定位有很多種方案，有直接定位和間接定位，直接定位中可以采用GPRS對節點進行定位，而間接定位主要分為基于距離關系定位、基于信標節點的定位，在本算法中我們采用了基于RSSI測距的三邊定位法，在距離的測量中，我們選用了如公式的模型[5]。

則距離發射點的距離d的大小為：

公式（2）中A為發射器發射給1m處的節點的信號強度的大小，其取值范圍在45-49之間，n為一個常數，代表信號傳輸與環境有一定的關系，其取值大小在3.25～4.5之間。通過公式（1）、（2）計算出節點到發射點節點之間的距離后，再根據三邊定位算法求出網絡中所有節點的坐標值。

在按根據項目的具體需要將網絡分為K等分，這樣做的目的是為了讓整個網絡的分簇更加均勻，避免了簇的重疊；使網絡拓撲更加均衡， 假設將整個網絡分成均勻的n等份，即n個簇，則每個簇的扇形角度θ的大小為：

我們定義在y軸上半區域與x軸正半軸夾角為θ的區域為簇1，然后依次劃分為簇2，簇3，…，簇n，網絡中得節點坐標假設為（x，y），則其與x軸的夾角θ'，則：

由式（4）可知：

具體簇的表示如圖4所示，根據此方法可以將整個網絡分成具有簇表示符的區域。

圖4 簇標識符示意圖

3.3 簇頭節點選取方法

簇頭節點是整個ZigBee網絡分簇中的關鍵部位，簇頭節點的選擇算法是整個算法的核心，選擇是否合理直接對整個網絡有很大的影響，在本算法中，我們采用了節點加權值來確定簇頭節點，主要關心以下兩個方面。

1）節點的剩余能量；

2）各節點到協調器的距離。

在這里我們定義i表示某個節點，j表示網絡劃分的某個簇，r表示簇輪換的次數。

關于剩余能量Ei(r)我們可以根據下面的公式（7）求得：

其中，ei(r)為節點i的剩余能量，_表示節點i所在的第j簇中所有節點的平均能量，的大小為：

Nj(i)表示第j簇中有i個節點。

由于本算法在一段時間后會進行簇的輪轉，能量不均對整個網絡的影響不是很大，所以，我們在確定代價函數cost(i,j)(r)的公式時，只有代價函數的值越大，當選簇頭節點的概率就越大，代價函數cost(i,j)(r)cost的公式如下：

在公式中，必須滿足α+β=1，當如果網絡中遇到同時有兩個節點cost(i,j)(r)值的大小相同時，這時我們再以節點的ID大小來選擇簇頭節點。節點ID小的當選為簇頭節點。

當網絡中得簇頭節點選擇完畢以后，簇頭節點將向簇內的每個節點廣播一個數據包，在這個數據包中包括了自己已經是簇頭節點的消息，其他節點將不在競爭簇頭節點。并允許簇中得其他節點加入本簇，并且夠建一個簇內節點的鄰居表，為了讓整個簇內的能耗更少，非簇頭節點可以選擇定時的休眠喚醒對數據進行采集和傳送，這就需要簇頭節點給簇內成員分配一個TDMA的序列，簇內的節點根據這個TDMA序列進行數據的傳輸，沒輪到自己傳輸數據的時候，節點將進行休眠，更加降低簇內節的能耗，讓整個簇的生命周期更長。同時為了保證數據傳輸的準確性，簇內每個節點收到簇頭消息的時候，將返回一個ACK對消息進行確認已經收到。

3.4 簇的輪轉

當網絡中的簇頭工作一定時間后其剩余能量較小，這是如果還繼續擔任簇頭節點，不但容易導致簇頭節點過快死亡，而且由于簇頭節點的能量迅速耗盡，將會對整個網絡的穩定性產生一定的影響，許多協議都采用了輪換簇頭的方式來解決這一問題[7]，但是這些輪換簇頭的方法都是在同一個簇內選取剩余節點能量較多的節點來當選簇頭節點，并且每個節點只能當選一次簇頭，但是由于網絡中每個節點都在進行數據的傳遞，能量都有所消耗，這樣一來必定導致每個簇的總體能量都會下降，直到最后每個節點能量都比較少時，不能選出簇頭節點，該區域將會成為一個死區，導致網絡的穩定性和生命周期，為了解決該問題，我們采取對簇頭節點的輪換思想，但唯一不同的時，對整個區域進行重新劃分，再對整個簇進行簇頭節點的選取。我們采用了根據坐標按相應的規則進行輪轉，這樣節點位置沒有發生變化，但是處于某個簇已經發生該變，具體示意如圖5所示。

圖5 簇的轉示意圖

整個分簇的重新輪轉是由協調器發送一個命令進行輪轉，這個輪轉的時間是隨機的，在這里我們設置為T1,輪轉時間的值取決于整個網絡的生命周期的長短，其值大小將在后面仿真進行取值，當分簇輪轉開始時，協調器將發送命令對整個簇進行重新的架構，首先它發送命令給網絡中的節點，讓網絡中的每個節點在現有的角度上加上a度，然后再根據公式（10）判斷現在自己屬于哪個簇。

注意在簇的輪轉中，為了是簇盡量避免輪轉后的簇同以前的簇重回，我們設定的輪轉角度a不應該與θ的值大小相同，應根據整個網絡中布置的節點的數量來設置a的大小。當分簇輪轉完成以后，將重復上一節的簇頭選擇標準進行簇頭節點的選取。

4 算法仿真

由于Matlab2007的Trutime工具箱中有完整的物理層以及MAC層的模塊，非常方便對于協議棧中的網絡層進行仿真，本算法基于MATLAB2007的平臺進行仿真，為了評估本算法的優越性，特采用了現有的ZigBee路由算法AODV以及現有的經典分簇路由算法LEACH與本算法進行仿真比較，由于仿真的模型采用了三種不同的協議，為了實現同等條件下進行比較，我們假定所有的參數都是固定不變的，這其中包括物理層、MAC以及其他的層，在仿真過程中，節點的能耗模型采用了一階能耗的模型[8]，仿真環境的參數如表1所示。

表1 仿真環境的參數

考慮通信模塊的工作模式和收發能耗很關鍵。根據仿真參數設置，通過公式我們可以得到

其中εfs代表無線電路的能量消耗，εamp代表放大器的參數，通過帶入表中的數值可以知道d0=87.8，也就是說當簇頭節點與協調器節點的距離小于87.8m時，節點的通信模式采用自用空間模型模型，節點的能耗損失最小。

4.1 仿真結果分析

由于評價ZigBee路由協議的指標相當的多，在這里我們主要從簇的建立時間、每種算法工作一段時間后網絡中存活的節點數以及算法在運行過程中整個網絡消耗的能量為主要指標來對比分析本算、LEACH算法以及現有的ZigBee路由協議。通過仿真分析，節點想有機會競選簇頭，至少要滿足開始設置的閾值，在本算法仿真中，我們設計節點每隔30ms發送一次數據大小為128bit的數據。在仿真時，我們先確定當α、β的大小，通過仿真分析，當α取0.6時，整個網絡的生命周期最長，因此，決定簇頭選擇標準的權值公式中α=0.6，β=0.4，此后的仿真都采用此數值。

4.2 輪轉時間T1的確定

在本算中，我們設計了整個簇不斷的輪轉來平衡整個網絡的能量消耗，但是輪轉時間T1的取值不能隨意設置，如果這個時間設置過長，有可能網絡中某個簇頭節點的能量已經消耗的相當多了，而其他簇的能量消耗較少，影響其他簇的節點能量平衡，而當時間設置過短時，有可能整個網絡的能量消耗速度加快，因為在本算中，整個網絡中簇的重新劃分消耗的能量是比較大的，所以在本算法設計中，應該盡可能選擇合適的輪轉時間周期，以使整個網絡的性能更加良好，達到延長網絡生命周期的目的。在這里我們選擇輪轉周期T1的值主要通過仿真來確定，通過設置不同的T1值來觀察整個網絡中第一個節點的死亡時間，仿真結果如圖6所示。

圖6 輪轉周期值的確定

通過圖中可知，在后面的仿真過程中，T1的取值為120s時，整個網絡的生命周期最長。

4.3 節點存活數情況

由于ZigBee網絡中節點的能量是有限的，因此我們在設計協議時應該以降低網絡的能耗以及延長整個網絡的生命周期為目標，而節點在工作狀態中存活數量的多少直接對整個網絡的生命周期有直接的影響，是評價一個路由協議的主要指標[11]如圖所示，該圖給出了三種算法中，根據網絡中節點運行的時間長短，來對整網絡中節點的存活數量進行對比，在仿真開始之處，我們設定了節點死亡的定義，如果節點的剩余能力為初始能量的10%時，即認為該節點已經死亡，不在進行數據的采集及傳輸，仿真結果的曲線如圖7所示。

圖7 節點存活數仿真結果

從圖中我們可以看見，本算法中節點存活的數量相對其他兩種算法，隨著時間的推移，當網絡運行20s的時候，AODV的路由協議最先出現節點的死亡，這是因為沒有對網絡分簇，有可能網絡中某種節點承擔著大量的數據轉發，使節點的能耗變大，造成節點的死亡，而本算法第一個節點的死亡時間產生的時間在40s左右而，而LEACH協議的第一個節點的死亡時間在25s左右，這是由于LEACH只在固定區域內對簇投節點的選擇進行輪轉，而本算采用簇整體輪換的思想，避免了因為某個簇的能量過低而造成節點的大面積死亡，延長了節點的工作時間，在提高了整個網絡的負載均衡性，每個節點的能量都得到充分的應用，并使整個網絡的生命周期變長，

4.4 網絡總能耗分析

在ZigBee網絡中，我們最關心整個網絡的總體能耗大小，只有減少了網絡整體能耗，才能對延長網絡的生命周期有決定性的影響，我們不但要盡可能的減少整個網絡的總體能耗，還要使網絡中每個節點的能耗均勻分別，仿真結果如圖8所示。

圖8 網絡總能耗仿真結果

從圖中我們可以發現，AODV協議的能耗是最高的，這是因為該算法沒有對數據進行融合，大量的冗余數據被轉發，導致整個網絡的能耗增高。而LEACH算法以及本算法都對數據進行了相關的融合，以致整個網絡的總體能耗比AODV要低，在網絡組建之初，使用AODV協議以及LEACH算法的能耗要低于本算法的能耗，但是隨著時間的推移，本算法中的能量消耗呈現緩慢遞增的情況，而LEACH算法和AODV協議的能耗都直線上升，這是因為本算法在組網開始階段，要對每個簇內的簇頭選擇消耗一定的能量，但是當選擇完畢后，網絡中的節點負載都比較均衡，能耗降到最低。

5 結束語

分簇算法的設計對網絡的性能以及穩定性的提高有很大的意義，如果整個網絡使用了分簇算法，不但有利于資源分配，降低數據傳輸時延，還能夠采用混合式的路由，這對網絡的擴展性有很大的好處，所有，分簇算法的設計有很廣泛的應用，但是分簇協議的設計會帶來更多的計算和維護通信的開銷，增大網絡的能量消耗，因此，為了盡可能的降低分簇算法所帶來的一些影響，我們 必須提高分簇算法的性能。在未來，分簇算法的研究和設計應該重點注意以下兩個方面。

1）應該根據不同的應用環境設置不同的分簇算法，在大規模的網絡中，節點一跳到達協調器的幾率比較小，這就需要對整個網絡進行分層的設計，在每層選擇一個簇頭，簇頭之間組成MESH網絡進行通信。因此，在本算法中加入分層思想是下一步的主要研究方向；

2）應充分考慮節點的移動性，節點靜止不動適用的范圍一般用于定位或者數據的采集方面，但是在某些場合，節點需要移動，這時在設計分簇算法時，應根據節點的移動速度來設計分簇算法。

[1]孫利民, 李建中.無線傳感器網絡[M].北京: 清華大學出版社, 2005: 156-161.

[2]戚劍超, 魏臻.ZigBee樹型路由算法的改進[J], 合肥工業大學學報(自然科學版) 第33卷第4期, 2010, 4.

[3]王勝平, 胥布工, ZigBee網絡路由發現廣播策略[J], 計算機工程, 36(11).

[4]周武斌, 羅大庸.ZigBee路由協議的研究[J], 計算機工程與科學, 2009, 31(6).

[5]朱明輝, 張會清.基于RSSI 的室內測距模型的研究[J],傳感器與微系統, 2010, 29(8).

[6]Heinzelman W, Chandrakasan A, Balakrishnan H.Energy efficient communication Protocol for wireless microsensor networks[J], In: Proceedings of the 33rd Hawaii International Conference on System Sciences Maui: IEEE Computer Society, 2000.3005-3014.

[7]Shu-bo QIU, Yuan XU, Xiu-wei YANG.A Novel Cluster Head Selection Method Using Energy for ZigBee Cluster-Tree Network[J], IEEE International Conference on Automation and Logistics Chongqing, China, August 2011.

[8]李善倉, 張克旺.無線傳感器網絡原理與應用[M], 北京,機械工業出版社, 2008: 12-20.

[9]Heinzelman W, Chandrakasan A, Balakrishnan H.Energy efficient communication Protocol for wireless microsensor networks[J], In: Proceedings of the 33rd Hawaii International Conference on System Sciences Maui: IEEE Computer Society, 2000.3005.

[10]黎天人, 羅娟, 李仁發.基于通信范圍約束的傳感器網絡多層分簇算法[J], 計算機工程與應用, 2009(4): 9.

[11]Handy M J; Haase M,Timmermann D.Low Energy Adaptive Clustering Hierarchy with Deterministic Clusterhead Selection[A].Germany: 2002.368-372.