賴 毅，唐 毓

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

0 引言

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network，WSN)是傳感器技術(shù)、無線通信技術(shù) 計算機技術(shù)、嵌入式計算技術(shù)結(jié)合的產(chǎn)物。利用分布在監(jiān)測區(qū)域中的多個傳感器節(jié)點，WSN能夠感知、監(jiān)測和采集相關(guān)環(huán)境或?qū)ο蟮男畔?。這些信息經(jīng)過融合之后以多跳中繼的方式傳遞到用戶終端，供用戶決策使用。WSN改變了人與自然界交互的方式，它在環(huán)境監(jiān)測、軍事國防、城市管理、搶險救災(zāi)等領(lǐng)域有很高的實用價值。無線傳感網(wǎng)絡(luò)的體系結(jié)構(gòu)如圖1所示[1]。

圖1 無線傳感網(wǎng)絡(luò)體系

1 ZigBee網(wǎng)絡(luò)體系結(jié)構(gòu)

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

2 ZigBee路由協(xié)議簡介

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

圖2 ZigBee路由選擇方式

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

圖3 典型的分簇拓撲結(jié)構(gòu)圖

3 算法設(shè)計

3.1 網(wǎng)絡(luò)模型

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

1）網(wǎng)絡(luò)中的所有節(jié)點被包含在一個圓形的區(qū)域內(nèi)，并且位置都不變，每個節(jié)點通過坐標節(jié)點都能計算出自己的位置；

2）節(jié)點的發(fā)射和接收功率足夠的大，可以直接單跳與網(wǎng)絡(luò)中的所有節(jié)點直接通信；

3）每個節(jié)點都要具備數(shù)據(jù)融合的能力；

4）網(wǎng)絡(luò)中每個節(jié)點的初始能量相同。

3.2 簇的具體劃分

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

則距離發(fā)射點的距離d的大小為：

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

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

我們定義在y軸上半?yún)^(qū)域與x軸正半軸夾角為θ的區(qū)域為簇1，然后依次劃分為簇2，簇3，…，簇n，網(wǎng)絡(luò)中得節(jié)點坐標假設(shè)為（x，y），則其與x軸的夾角θ'，則：

由式（4）可知：

具體簇的表示如圖4所示，根據(jù)此方法可以將整個網(wǎng)絡(luò)分成具有簇表示符的區(qū)域。

圖4 簇標識符示意圖

3.3 簇頭節(jié)點選取方法

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

1）節(jié)點的剩余能量；

2）各節(jié)點到協(xié)調(diào)器的距離。

在這里我們定義i表示某個節(jié)點，j表示網(wǎng)絡(luò)劃分的某個簇，r表示簇輪換的次數(shù)。

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

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

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

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

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

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

3.4 簇的輪轉(zhuǎn)

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

圖5 簇的轉(zhuǎn)示意圖

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

注意在簇的輪轉(zhuǎn)中，為了是簇盡量避免輪轉(zhuǎn)后的簇同以前的簇重回，我們設(shè)定的輪轉(zhuǎn)角度a不應(yīng)該與θ的值大小相同，應(yīng)根據(jù)整個網(wǎng)絡(luò)中布置的節(jié)點的數(shù)量來設(shè)置a的大小。當分簇輪轉(zhuǎn)完成以后，將重復(fù)上一節(jié)的簇頭選擇標準進行簇頭節(jié)點的選取。

4 算法仿真

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

表1 仿真環(huán)境的參數(shù)

考慮通信模塊的工作模式和收發(fā)能耗很關(guān)鍵。根據(jù)仿真參數(shù)設(shè)置，通過公式我們可以得到

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

4.1 仿真結(jié)果分析

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

4.2 輪轉(zhuǎn)時間T1的確定

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

圖6 輪轉(zhuǎn)周期值的確定

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

4.3 節(jié)點存活數(shù)情況

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

圖7 節(jié)點存活數(shù)仿真結(jié)果

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

4.4 網(wǎng)絡(luò)總能耗分析

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

圖8 網(wǎng)絡(luò)總能耗仿真結(jié)果

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

5 結(jié)束語

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

1）應(yīng)該根據(jù)不同的應(yīng)用環(huán)境設(shè)置不同的分簇算法，在大規(guī)模的網(wǎng)絡(luò)中，節(jié)點一跳到達協(xié)調(diào)器的幾率比較小，這就需要對整個網(wǎng)絡(luò)進行分層的設(shè)計，在每層選擇一個簇頭，簇頭之間組成MESH網(wǎng)絡(luò)進行通信。因此，在本算法中加入分層思想是下一步的主要研究方向；

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

[1]孫利民, 李建中.無線傳感器網(wǎng)絡(luò)[M].北京: 清華大學(xué)出版社, 2005: 156-161.

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

[3]王勝平, 胥布工, ZigBee網(wǎng)絡(luò)路由發(fā)現(xiàn)廣播策略[J], 計算機工程, 36(11).

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

[5]朱明輝, 張會清.基于RSSI 的室內(nèi)測距模型的研究[J],傳感器與微系統(tǒng), 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]李善倉, 張克旺.無線傳感器網(wǎng)絡(luò)原理與應(yīng)用[M], 北京,機械工業(yè)出版社, 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]黎天人, 羅娟, 李仁發(fā).基于通信范圍約束的傳感器網(wǎng)絡(luò)多層分簇算法[J], 計算機工程與應(yīng)用, 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.