牛瀟，王忠慶

（中北大學(xué)，山西省 太原 030051）

0 引言

傳感器網(wǎng)絡(luò)具有異于MANET的獨特性質(zhì)，而傳統(tǒng)MANET協(xié)議不適用于傳感器網(wǎng)絡(luò)，需要為傳感器網(wǎng)絡(luò)研究新的有效的路由算法。目前，在傳感器網(wǎng)絡(luò)的路由算法研究中，鑒于傳感器網(wǎng)絡(luò)中節(jié)點稠密分布、節(jié)點的能量、存儲及數(shù)據(jù)處理能力十分有限的特性，一般采用基于分簇的方法來進(jìn)行路由算法設(shè)計，以提高路由算法的性能。分簇算法作為路由協(xié)議的研究基礎(chǔ)，對路由算法性能的優(yōu)劣具有重要的影響。

1 LEACH算法及分析

LEACH算法是一種典型的層次路由算法。LEACH算法分別做了如下假設(shè)，主要設(shè)基站(BS)遠(yuǎn)離傳感器網(wǎng)絡(luò)節(jié)點并且是穩(wěn)定的；傳感器網(wǎng)絡(luò)中的所有節(jié)點是同構(gòu)的并且能量都受到限制；所有節(jié)點可以直接與基站通訊；節(jié)點都沒有位置信息；簇頭節(jié)點負(fù)責(zé)數(shù)據(jù)壓縮匯聚以及與基站進(jìn)行通訊；該算法主要通過隨機選擇簇首領(lǐng)，平均分擔(dān)中繼通信業(yè)務(wù)來實現(xiàn)節(jié)能。同時LEACH定義了“輪”(Round)的概念，針對每個節(jié)點n設(shè)定了一個閾值T(n)：

式(1)中p表示簇頭節(jié)點占網(wǎng)絡(luò)節(jié)點總數(shù)的百分比；r表示重新挑選簇頭節(jié)點的輪數(shù)；G表示網(wǎng)絡(luò)中最近1/p輪未當(dāng)選簇頭的節(jié)點的集合。并根據(jù)該閾值從侯選節(jié)點中挑選簇頭，具體的步驟：

（1） 若傳感器節(jié)點Ni∈G，則對于每個Ni獨立運算(2.1)式，獲得閾值T(n)。

（2） 若Ni不屬于G，則根據(jù)(1)式，T(n)為零。

（3） Ni產(chǎn)生一個0~1之間的隨機數(shù)RadomNum。

（4） 若T(n)＞RadomNum，則該節(jié)點當(dāng)選為簇頭，并廣播當(dāng)選消息。

（5） 其余節(jié)點選擇加入某簇頭所在的簇，形成穩(wěn)定的拓?fù)浣Y(jié)構(gòu)。

（6） 穩(wěn)定工作階段。

（7） 每隔時間t，進(jìn)行下一輪簇頭選取，轉(zhuǎn)Step1，重新選擇簇頭并成簇。

由以上步驟可知LEACH算法中的輪是指兩次簇頭選取之間的時間段，每一輪由初始化和穩(wěn)定工作兩個階段組成。在初始化階段，隨機選擇節(jié)點為簇首領(lǐng)，成為簇首領(lǐng)的節(jié)點向周圍廣播信息，其它節(jié)點根據(jù)接收到廣播信息的強度來選擇它所要加入的簇，并告知相應(yīng)的簇首領(lǐng)，由于信息的強度和節(jié)點之間的距離是成正比的，因此，實際上各非簇頭節(jié)點是選擇距離自己地理距離最短的簇頭所在的簇加入，并形成簇拓?fù)浣Y(jié)構(gòu)，如圖1所示。

圖1 成簇階段圖

無線傳感器網(wǎng)絡(luò)首先產(chǎn)生中心節(jié)點，其余節(jié)點加入距離自己最近的中心節(jié)點所在的簇，然后由中心節(jié)點直接和Sink節(jié)點進(jìn)行通訊。在穩(wěn)定工作階段，節(jié)點持續(xù)采集監(jiān)測數(shù)據(jù)，傳送到簇頭，由簇頭對數(shù)據(jù)進(jìn)行必要的融合處理之后，發(fā)送到終端節(jié)點。每輪工作周期結(jié)束后，重新選擇簇頭并重復(fù)前面的工作。

2 能量有效的分布式簇頭選取算法

目前提出的很多路由算法都沒有考慮傳感器節(jié)點的實際分布情況。在上述的LEACH算法描述中，LEACH存在著以下的諸多問題。

(1)由于位于簇邊緣位置的簇頭通訊能耗遠(yuǎn)大于位于簇中心位置的簇頭，因此將導(dǎo)致各簇頭能耗不均衡，使某些簇頭節(jié)點能量提前耗盡。

(2) LEACH沒有考慮到傳感器網(wǎng)絡(luò)在進(jìn)行部署的時候，節(jié)點分布密度對簇頭能耗的影響。由此導(dǎo)致在傳感器節(jié)點密集分布區(qū)域的簇頭能耗巨大，而在傳感器節(jié)點稀疏分布區(qū)域的簇頭能耗較小，網(wǎng)絡(luò)中各簇頭的能耗極不均衡。

(3) 動態(tài)分簇引起網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)頻繁變換和大量廣播通信，從而帶來了額外的能量開銷。

因此上述節(jié)點可能在某個局部分布非常的密集，而在其他的一些地方分布又非常稀疏。因此在這種情況下，簡單的采用LEACH算法中的簇頭選取機制，從而導(dǎo)致傳感器網(wǎng)絡(luò)生命周期的提前結(jié)束。首先提出了密度調(diào)節(jié)參數(shù)數(shù)學(xué)模型，然后將其與上一章提出的平均能耗調(diào)節(jié)參數(shù)結(jié)合起來，進(jìn)而提出了能量有效的分布式簇頭選取算法。

為了解決上面的問題，首先必須量化傳感器網(wǎng)絡(luò)的節(jié)點分布密度，為方便描述，做如下的假設(shè)：

(1) 傳感器的通信半徑R可以根據(jù)需求而改變，R0是基本通信半徑，R≥ R0；

(2) Ni表示傳感器網(wǎng)絡(luò)中的第i個節(jié)點；

(3) 任意節(jié)點Ni坐標(biāo)為（xNi, yNi）；

根據(jù)上面的假設(shè)，可知Dist(Ni，Nj)表示傳感器網(wǎng)絡(luò)中任意兩點之間的直線距離，但是由于在分布式路由算法中節(jié)點的位置信息都無法獲取，因此給出函數(shù)f(SignalIntension)，其中SignalIntension表示Ni節(jié)點接收到的，由Nj節(jié)點發(fā)出的信號的強度，這個值可以通過Ni節(jié)點的通訊模塊獲得，而f(SignalIntension)則表示接收信號的強度與收發(fā)信號的兩節(jié)點之間距離的映射關(guān)系。對于任意節(jié)點Ni，若Dist(Ni，Nj)

根據(jù)以上分析提出一種能量有效的分布式簇頭 選 取 算 法(EECHS，Energy Efficient Cluster Heads Selection)，該算法同時引入能量調(diào)節(jié)參數(shù)和密度調(diào)節(jié)參數(shù)，通過能量調(diào)節(jié)參數(shù)可以使得剩余能量越大且每輪平均工作能耗越小的節(jié)點有更多機會成為簇頭。通過密度調(diào)節(jié)參數(shù)可以使得分布密度越大區(qū)域的節(jié)點有更多機會成為簇頭。密度調(diào)節(jié)參數(shù)如下：

N(j)∈NeighborSet(i)。NeighborSet(i)是節(jié)點Ni的鄰居節(jié)點集合。即Nodedensity(i)的值表示節(jié)點Ni的鄰居節(jié)點的總數(shù)，也就是以N(i)為圓心，R0為半徑的圓形區(qū)域的節(jié)點的個數(shù)。當(dāng)Nodedensity(i)的值比較大時，意味著該節(jié)點所在區(qū)域節(jié)點分布的密度比較大。故，式(1)可修訂為式(2)：

在式(3)中，Ecur表示節(jié)點當(dāng)前的剩余能量，Eavg表示節(jié)點每輪的平均能耗。故，式(1)可修訂為：

其中，rs為節(jié)點連續(xù)未當(dāng)選為簇頭的輪數(shù)，一旦節(jié)點當(dāng)選簇頭，則rs重置為0。

得出能量調(diào)節(jié)參數(shù)如式(6)：

故LEACH算法的式(5)可以改進(jìn)為如式(7)所示：

顯然，a=0，b=1時，式(7)將簡化為式(9)：

即只在LEACH算法中進(jìn)一步考慮剩余能量與工作能耗對網(wǎng)絡(luò)生命周期的影響。

而當(dāng)a=1，b=0時，式(9)將簡化為式(10)：

即只在LEACH算法中進(jìn)一步考慮節(jié)點分布密度對網(wǎng)絡(luò)生命周期的影響。在穩(wěn)定工作階段，節(jié)點周期性的采集監(jiān)測數(shù)據(jù)，并傳送給簇首，進(jìn)行必要的數(shù)據(jù)聚集和融合之后，將處理后的數(shù)據(jù)發(fā)送到Sink節(jié)點，這是一種減小通信數(shù)據(jù)流的有效工作模式。持續(xù)一段時間以后，整個網(wǎng)絡(luò)進(jìn)入下一輪工作周期，重新選擇簇首。

LEACH可以在一定的程度上節(jié)省能量，與一般的協(xié)議相比，簇首的能量消耗非常高，各節(jié)點需要等概率地?fù)?dān)任簇首才能使網(wǎng)絡(luò)中所有節(jié)點比較均衡地消耗能量，有利于延長整個網(wǎng)絡(luò)的生命周期，至少延長15%；其特點是分層和數(shù)據(jù)融合，分層有利于網(wǎng)絡(luò)的擴展，數(shù)據(jù)融合能夠減少通信量。但是它必須在每個簇首都可以和節(jié)點直接通信的基礎(chǔ)上進(jìn)行，因而有一定的局限性。

3 算法仿真實驗

在輸入要進(jìn)行部署的傳感器節(jié)點個數(shù)，區(qū)域大小，初始能量和調(diào)節(jié)參數(shù)等相關(guān)數(shù)據(jù)后，可以根據(jù)這些數(shù)據(jù)產(chǎn)生指定個數(shù)的節(jié)點，并且為每個節(jié)點隨機分配一個坐標(biāo)。通過仿真實驗平臺將生成節(jié)點分布的模擬圖。因此采用EECHS算法在剛才模擬部署的傳感器節(jié)點中選擇簇頭并成簇，實驗平臺將以直觀的方式顯示簇頭選取的結(jié)果。最后實驗平臺還將記錄每輪分簇過程中產(chǎn)生的簇頭的坐標(biāo)，并以列表的方式顯示出來。具體的操作界面如圖2所示。

圖2 獲取初始參數(shù)界面圖

圖2為仿真系統(tǒng)中獲取部署節(jié)點參數(shù)數(shù)據(jù)的截圖，取得相應(yīng)的數(shù)據(jù)后即可對節(jié)點進(jìn)行部署，其中能量調(diào)節(jié)參數(shù)和密度調(diào)節(jié)參數(shù)的取值范圍為0~1之間。

圖3為模擬100個節(jié)點部署的截圖，其中每個小圈代表一個傳感器節(jié)點。

圖4為節(jié)點數(shù)為200個時，最后一輪分簇時選取的簇頭截圖，其中比較粗的小圈表示當(dāng)選為簇頭的節(jié)點，較細(xì)的圈表示普通節(jié)點?？赏ㄟ^選擇左側(cè)窗格中的分簇輪數(shù)來查看該輪產(chǎn)生的簇頭節(jié)點的個數(shù)及各簇頭的坐標(biāo)，同時還可以查看總的分簇輪數(shù)，從而與采用LEACH算法時傳感器網(wǎng)絡(luò)的生命周期進(jìn)行比較。

圖3 節(jié)點部署模擬圖

圖4 簇頭選取模擬圖

4 實驗結(jié)果

在實驗過程中隨機生成若干個點，代表隨機分布的傳感器，假定p=0.1，節(jié)點初始能量均為2000。當(dāng)傳感器節(jié)點個數(shù)固定為200，而部署區(qū)域大小分別取800×800，900×900，1000×1000，1100×1100，1200×1200時，得到的仿真實驗結(jié)果如圖5所示。

圖5 部署區(qū)域大小變化時EECHS與LEACH算法實驗對比圖

在圖5中，橫坐標(biāo)為正方形部署區(qū)域的邊長，縱坐標(biāo)為采用LEACH算法或EECHS算法時成簇的輪數(shù)(即網(wǎng)絡(luò)的生命周期)。由圖5可知，當(dāng)節(jié)點數(shù)量不變，隨部署區(qū)域面積的擴大，僅考慮節(jié)點的分布密度(a=0，b=1)、或僅考慮節(jié)點的剩余能量及其工作能耗(a=1，b=0)、或綜合考慮節(jié)點的分布密度以及節(jié)點的剩余能量及其工作能耗(a=0.5，b=0.5)時，采用EECHS算法，傳感器網(wǎng)絡(luò)的生命周期均比采用LEACH算法時更長。特別的，當(dāng)綜合考慮節(jié)點的分布密度、節(jié)點的剩余能量及其工作能耗(a=0.5，b=0.5)時，傳感器網(wǎng)絡(luò)的生命周期延長了近150%。

若隨機生成100，150，200……個點，而部署區(qū)域大小固定為1000×1000時，p=0.1，則仿真實驗結(jié)果如圖6所示。

圖6 節(jié)點個數(shù)變化時EECHS與LEACH算法實驗對比圖

在圖6中，橫坐標(biāo)為部署的節(jié)點個數(shù)，縱坐標(biāo)為采用LEACH算法或EECHS算法時成簇的輪數(shù)(即網(wǎng)絡(luò)的生命周期)。由圖6知，當(dāng)部署區(qū)域面積一定，隨部署的節(jié)點數(shù)增加，僅考慮節(jié)點的分布密度(a=0，b=1)、或僅考慮節(jié)點的剩余能量及其工作能耗(a=1，b=0)、或綜合考慮節(jié)點的分布密度以及節(jié)點的剩余能量及其工作能耗(a=0.5，b=0.5)時，采用EECHS算法，傳感器網(wǎng)絡(luò)的生命周期均比采用LEACH算法時更長。特別地，當(dāng)綜合考慮節(jié)點的分布密度、節(jié)點的剩余能量及其工作能耗(a=0.5，b=0.5)時，傳感器網(wǎng)絡(luò)的生命周期延長了近100%。

若隨機生成100個點，而部署區(qū)域大小固定為1000 1000，p=0.1時，節(jié)點的初始能量分別取1000，1500，2000，2500，3000則仿真實驗結(jié)果如圖7所示。

在圖7中，橫坐標(biāo)為節(jié)點的初始能量，縱坐標(biāo)為采用LEACH算法或EECHS算法時成簇的輪數(shù)(即網(wǎng)絡(luò)的生命周期)。由圖7知，當(dāng)部署區(qū)域面積及節(jié)點個數(shù)一定，隨節(jié)點初始能量的增加，當(dāng)僅考慮節(jié)點的分布密度(a=0，b=1)、或僅考慮節(jié)點的剩余能量及其工作能耗(a=1，b=0)、或綜合考慮節(jié)點的分布密度以及節(jié)點的剩余能量及其工作能耗(a=0.5，b=0.5)時，采用EECHS算法，傳感器網(wǎng)絡(luò)的生命周期均比采用LEACH算法時更長。特別地，當(dāng)綜合考慮節(jié)點的分布密度、節(jié)點的剩余能量及其工作能耗(a=0.5，b=0.5)時，傳感器網(wǎng)絡(luò)的生命周期比采用LEACH算法時延長了近90%。

圖7 初始能量變化時EECHS與LEACH算法實驗對比圖

[1] 史龍,王福豹,段渭軍，等.無線傳感器網(wǎng)絡(luò)Range-Free 自身定位機制與算法[J].計算機工程與應(yīng)用,2004,40（23）：127-130.

[2] B. Krishnamachari, D. Estrin, and S. Wicker. Modelling Data-Centric Routing in Wireless Sensor Networks[J]. In Proceedings of IEEE Infocom, 2002,102-111.

[3] 盧春枝.LU Chunzhi 無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議分析[J].武漢理工大學(xué)學(xué)報:信息與管理工程版, 2008,30(1).

[4] 朱彬.廖俊國.羅芽松.使用部署知識的異構(gòu)傳感器網(wǎng)絡(luò)有效成簇算法[J].計算機工程與應(yīng)用,2009,45(13).

[5] 張新秀.張淼.張振川.無線傳感器網(wǎng)絡(luò)分簇路由改進(jìn)算法及其性能[J].中國科技論文在線,2010,5(2).

[6] M. Chu, H. Haussecker,F. Zhao.Scalable informationdriven sensor querying and routing for ad hoc heterogeneous sensor networks[J].International Journal of High-Performance Computing Applications, 2002,16(3):348-356.

[7] 田艷霞,辛兵,吳克軍.無線傳感器網(wǎng)絡(luò)的節(jié)能研究[J].兵工自動化，2006,25(3).

[8] 沈 波,張世永,鐘亦平. 無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議[J]. 軟件學(xué)報, 2006,17(7): 1672-1681.