韓鵬瑋，王慶生，張 博

(1.太原理工大學計算機科學與技術(shù)學院，山西 太原 030024;2.北京大學工學院，北京 100871)

責任編輯:李 薇

無線傳感器網(wǎng)絡(luò)由于在災(zāi)難管理、戰(zhàn)場監(jiān)控、醫(yī)學診斷和環(huán)境與棲息地檢測等方面的廣泛應(yīng)用，成為研究的熱點。然而無線傳感器網(wǎng)絡(luò)作為一個自組織網(wǎng)絡(luò)，在設(shè)計與實現(xiàn)上面臨了一些技術(shù)方面的挑戰(zhàn)［1］。大多數(shù)傳感器節(jié)點由于其電池的不可替換性，使得無線傳感器網(wǎng)絡(luò)通過網(wǎng)絡(luò)管理技術(shù)來進行能量控制機制成為一種挑戰(zhàn)。針對分布密度較高的無線傳感器網(wǎng)絡(luò)，目前一種比較有效的節(jié)能方法是在網(wǎng)絡(luò)內(nèi)對冗余數(shù)據(jù)進行處理，即在網(wǎng)絡(luò)層中讓路由協(xié)議結(jié)合數(shù)據(jù)融合機制，中間節(jié)點收到數(shù)據(jù)后，在轉(zhuǎn)發(fā)之前先要對數(shù)據(jù)進行融合處理，將所需的數(shù)據(jù)量壓縮到最小，平衡網(wǎng)絡(luò)中各個節(jié)點的能量消耗［2］。

對于節(jié)點分布密度較大的無線傳感器網(wǎng)絡(luò)，本文提出一種基于網(wǎng)格的無線傳感器網(wǎng)絡(luò)非均勻分簇算法UECG(Uneven Clustering Algorithm Based on Grid in WSN)，平衡了各個節(jié)點的能量損耗，進而減少網(wǎng)絡(luò)總能量的消耗。算法通過劃分虛擬網(wǎng)格，減少了各個網(wǎng)格中活躍節(jié)點的總數(shù)，休眠冗余節(jié)點，以降低冗余數(shù)據(jù)以及傳輸干擾，并減少不必要的信道偵聽，同時在各個網(wǎng)格選出激活節(jié)點后通過非均勻分簇算法來解決簇間能量消耗的不平衡問題，從而節(jié)省下更多的能量用于簇間數(shù)據(jù)傳送，平衡了網(wǎng)絡(luò)整體的功耗，最終達到延長網(wǎng)絡(luò)使用壽命的目的。

1 典型路由協(xié)議分析

無線傳感器網(wǎng)絡(luò)的路由協(xié)議所包含的內(nèi)容很多，但其核心思想是簇首選擇與分簇以及如何在簇間傳輸數(shù)據(jù)［3－4］。分簇方法有很多，簇內(nèi)可以應(yīng)用不同的數(shù)據(jù)交換方法。同時，由于選擇簇首采用的方法不同，算法也不相同［5－6］。

1.1 LEACH協(xié)議

LEACH(Low－Energy Adaptive Clustering Hierarchy)［7］協(xié)議是一種經(jīng)典的無線傳感器網(wǎng)絡(luò)分簇算法，具有周期性的特點，每個周期分為兩個階段:簇的形成階段與數(shù)據(jù)傳遞階段。在第一階段，無線傳感器網(wǎng)絡(luò)用自組織的方式來隨機生成簇首節(jié)點。在簇首節(jié)點被選出之后，簇首以廣播方式通知全網(wǎng)絡(luò)，其余節(jié)點則根據(jù)接收到的信號強弱來判斷加入哪個簇，并告知簇首，以此來形成完整的簇群。在第二階段，簇內(nèi)的節(jié)點在其相應(yīng)的通信時間內(nèi)將數(shù)據(jù)發(fā)送到簇首節(jié)點，簇首節(jié)點把收集到的數(shù)據(jù)經(jīng)過處理后直接發(fā)送給基站。在LEACH算法中，節(jié)點輪流成為簇首節(jié)點，這在一定程度上均衡了節(jié)點能耗，從而可以節(jié)約網(wǎng)絡(luò)能量，進而延長網(wǎng)絡(luò)壽命。

從上述分析中，不難看出LEACH協(xié)議的缺點是在不同的簇內(nèi)，簇首與非簇首的距離是不相同的，節(jié)點通信過程中簇首的能耗明顯多于普通節(jié)點。

1.2 EEUC協(xié)議

EEUC(Energy－Efficient Uneven Clustering)［8］針 對LEACH協(xié)議的缺點，提出了一種非均勻分簇的思想，它充分考慮到節(jié)點間的多跳通信模式。與基站距離較遠的簇首節(jié)點均通過距離基站較近的簇首節(jié)點來進行數(shù)據(jù)傳輸，這樣距離基站較近的簇首節(jié)點會耗費較多能量，因此會引起網(wǎng)絡(luò)能耗的不均衡。EEUC算法正是為解決這種問題而提出的，它采用非均勻的分簇方法，通過分布式機制來建立簇群。每個節(jié)點根據(jù)節(jié)點與基站的距離來計算競爭半徑，也就是成簇半徑。充分考慮到節(jié)點與基站之間的距離，減輕了距基站較近的簇首負載，避免了據(jù)基站較近的簇首節(jié)點的過早死亡，從而實現(xiàn)了均衡整個網(wǎng)絡(luò)的負載。但是EEUC算法的缺點是網(wǎng)絡(luò)中仍然有大量的冗余數(shù)據(jù)，并且考慮競爭半徑時，沒有考慮到簇首剩余能量的問題。

2 能量模型及網(wǎng)絡(luò)模型

2.1 能量模型

無線傳感器網(wǎng)絡(luò)節(jié)點能耗的主要來源是數(shù)據(jù)的采集、計算與傳輸，由于傳輸?shù)哪芎倪h遠多于計算與采集的能耗，所以本文主要考慮網(wǎng)絡(luò)的傳輸，暫不考慮采集與計算的能量損失。本文采用和文獻［7］相同的傳輸模型。傳輸模型在發(fā)送數(shù)據(jù)和接收數(shù)據(jù)時，所消耗的能量為

式中:k是數(shù)據(jù)長度;d是數(shù)據(jù)發(fā)送距離;ETx－elec(k)是收發(fā)電路發(fā)送長度為k的數(shù)據(jù)的電路能耗;ETx－amp(k，d)是長度為k的數(shù)據(jù)發(fā)送距離為d的放大器能耗;Eelec是發(fā)射(接收)電路發(fā)送(接收)1 bit信息的能耗;εfs和εamp分別是自由空間模型和多路徑衰減模型的放大器能耗;ERx－elec(k)是收發(fā)電路接收長度為k的數(shù)據(jù)的電路能耗。

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

在以S為邊長的正方形區(qū)域內(nèi)隨機分布N個相同的節(jié)點?；疚挥诜叫螀^(qū)域外。本文假設(shè)下述條件成立:

1)所有節(jié)點都具有相同的結(jié)構(gòu)，具有一樣的數(shù)據(jù)處理能力以及無線通信能力，并且初始能量相同。

2)所有節(jié)點的能量無法進行補充，并且都處于靜止狀態(tài)。

3)檢測的范圍遠大于無線傳感器網(wǎng)絡(luò)的邊界區(qū)域。

4)節(jié)點間相互通信能耗相同，即傳輸鏈路對稱。

3 算法設(shè)計與實現(xiàn)

3.1 劃分網(wǎng)格

首先將待監(jiān)控的區(qū)域劃分為N個等同大小的虛擬網(wǎng)格。傳感器節(jié)點被隨機分散部署在監(jiān)測區(qū)內(nèi)，每個網(wǎng)格區(qū)域里的節(jié)點為一組。每個網(wǎng)格由該網(wǎng)格的中心點坐標(x，y)來表示，用(x，y，i)來區(qū)分網(wǎng)格的狀態(tài)是否有效，其中，x與y是網(wǎng)格中心點的橫縱坐標，i代表網(wǎng)格當前的狀態(tài)，i=0和i=1分別表示該網(wǎng)格失效和有效。每個節(jié)點設(shè)定一個固定的ID值，用來表示該節(jié)點所處的網(wǎng)格。每次傳輸數(shù)據(jù)，都要激活有效網(wǎng)格內(nèi)能量最大的節(jié)點，休眠余下節(jié)點。網(wǎng)格內(nèi)的活躍節(jié)點用來采集相關(guān)信息并傳送數(shù)據(jù)，處于休眠中的節(jié)點則等待被激活。

3.2 非均勻分簇

非均勻分簇的主要思想是將激活節(jié)點分劃為規(guī)模不同的簇群，簇群的大小由各簇簇首到基站的距離來決定。由于離基站近的簇群轉(zhuǎn)移發(fā)送能耗高，故劃分較小的簇規(guī)模，從而有效減少簇群內(nèi)部傳輸?shù)南?，?jié)省能量填補簇群間的轉(zhuǎn)發(fā)能量損耗;給距離基站較遠的簇群劃分較大的區(qū)域，這樣可以增加簇群內(nèi)部各個節(jié)點間傳輸能量消耗，從而平衡了簇群在簇內(nèi)能耗和簇間能耗。

具體非均勻分簇的步驟如下:

1)分簇階段，首先需要考慮到的是簇首節(jié)點的個數(shù)。簇首節(jié)點的數(shù)量將對網(wǎng)絡(luò)的能耗產(chǎn)生影響，因此，如何求得最優(yōu)的簇首節(jié)點個數(shù)［9］是至關(guān)重要的。設(shè)網(wǎng)絡(luò)節(jié)點個數(shù)為n，K為簇的個數(shù)，dtoBS是簇首與基站之間的距離，dtoCH是簇內(nèi)節(jié)點到簇首的距離，EDF是單位數(shù)據(jù)融合所耗費的能量，I是數(shù)據(jù)包的大小(二進制位數(shù))。

簇首節(jié)點在每一輪中的能耗為

簇內(nèi)節(jié)點在每一輪中的能耗為

整個網(wǎng)絡(luò)在每一輪中的能耗為

式中:A為正方形區(qū)域的邊長;LBS是常量，表示基站與正方形區(qū)域中心的距離。

將Etotal對K求導，同時使其為0，得到K的最優(yōu)值使得Etotal的值最小。K的最優(yōu)值是

從式(6)可以得出，最佳簇首個數(shù)與網(wǎng)絡(luò)的節(jié)點個數(shù)n、正方形區(qū)域邊長A和基站與正方形區(qū)域中心的距離LBS有關(guān)。

2)算出最優(yōu)簇首個數(shù)后，根據(jù)各個激活節(jié)點的剩余能量，以P概率在激活節(jié)點中選出部分節(jié)點成為簇首，激活節(jié)點被選為簇首的概率為T(n)，T(n)是事先設(shè)置好的閾值。每個激活節(jié)點都會隨機產(chǎn)生一個數(shù)，將該數(shù)與閾值T(n)進行比較，若小于T(n)，該節(jié)點被選為簇首，否則作為普通節(jié)點?？紤]到LEACH協(xié)議中選取簇首時未將節(jié)點剩余能量考慮進去，本文在LEACH協(xié)議基礎(chǔ)上將閾值T(n)改進為

式中:G表示在最后1/p輪中沒有當選過簇首的節(jié)點集合;p表示簇首節(jié)點在所有節(jié)點中所占的百分比;r表示選取的輪數(shù);Eremain表示節(jié)點的剩余能量;表示第r輪網(wǎng)絡(luò)中激活節(jié)點平均剩余能量。

3)簇首被選出后，根據(jù)簇首到基站的距離設(shè)定簇的競爭半徑Rc?？紤]到離基站距離遠的節(jié)點能量缺失，成簇半徑越大導致節(jié)點能量損耗越大，因此本文在EEUC協(xié)議中競爭半徑公式的基礎(chǔ)上進行了改進，公式里考慮了能量因素，增加了節(jié)點的剩余能量。競爭半徑為

式中:dmax和dmin表示網(wǎng)絡(luò)中簇首到基站的最大距離和最小距離;R表示最大的競爭半徑值;pi和pn分別表示已激活節(jié)點的初始能量與余留能量;pd是節(jié)點失效的臨界能量值，即表示節(jié)點能量降低到pd時節(jié)點失效。節(jié)點si到基站的距離記為d(si，BS)，c∈(0，1)用來限制取值范圍。從式(8)可以看出，競爭半徑根據(jù)節(jié)點余留能量與據(jù)基站位置的改變而變化。

各個簇首在競爭半徑內(nèi)向其余節(jié)點廣播消息，其余普通激活節(jié)點加入并最終形成簇。簇群一旦建立成功便進入到信息采集與傳輸階段，利用節(jié)點間的多跳通信模式，距離基站較遠的簇首節(jié)點通過距離基站較近的簇首節(jié)點傳輸數(shù)據(jù)。

4 UECG仿真與性能分析

本文采用MATLAB仿真，仿真實驗均基于同一實驗場景，參數(shù)配置如表1所示。

表1 網(wǎng)絡(luò)環(huán)境與參數(shù)配置

首先將100 m×100 m的范圍均勻劃分為64個虛擬網(wǎng)格，在此基礎(chǔ)上的節(jié)點分布和覆蓋圖如圖1所示。從圖1中可以看到，多數(shù)區(qū)域被傳感器節(jié)點多次重復檢測，這樣會使大量冗余的信息被采集。在每個網(wǎng)格中激活一個能量最大的節(jié)點，休眠其余節(jié)點后，檢測區(qū)域的節(jié)點分布及覆蓋如圖2所示。比較圖1與圖2可以看出，本算法減少了區(qū)域的重復覆蓋度，從而大幅減少了冗余數(shù)據(jù)。同時從圖2可以看出通過網(wǎng)格選取出的64個激活節(jié)點能保證所監(jiān)控的覆蓋區(qū)域在95%以上。

節(jié)點分布優(yōu)化后，選出的64個激活節(jié)點通過非均勻成簇后的示意圖如圖3所示。從圖中可以看出，距離基站(50，－50)越近的簇范圍越小，而距離基站越遠的簇的范圍越大。

圖3 節(jié)點非均勻分簇示意圖

在部署400節(jié)點的條件下，本算法與LEACH協(xié)議和EEUC協(xié)議進行比較的結(jié)果如圖4所示，在實驗進行到1 403輪時，LEACH協(xié)議的全部節(jié)點死亡，EEUC協(xié)議在1 784輪時，最后一個節(jié)點死亡，而本文提出的算法，在2 201輪時，最后一個節(jié)點死亡。比LEACH協(xié)議的網(wǎng)絡(luò)壽命提高了56.88%，比EEUC協(xié)議的網(wǎng)絡(luò)壽命提高了23.37%。

圖4 存活節(jié)點與網(wǎng)絡(luò)運行關(guān)系示意圖

圖5是基站接收到的數(shù)據(jù)總量，從圖5可以清楚地看出，UECG協(xié)議比LEACH協(xié)議和EEUC協(xié)議傳輸?shù)幕窘邮盏降臄?shù)據(jù)總量多，這意味著無線傳感器網(wǎng)絡(luò)通信有更高的利用率。

5 結(jié)論

圖5 基站接收到數(shù)據(jù)量

本文研究了無線傳感器網(wǎng)絡(luò)中的LEACH協(xié)議和EEUC協(xié)議的優(yōu)缺點，綜合之后提出基于網(wǎng)格的無線傳感器網(wǎng)絡(luò)非均勻分簇算法。算法利用虛擬網(wǎng)格來降低數(shù)據(jù)冗余，并根據(jù)簇首與基站之間距離的遠近來設(shè)定簇群的范圍大小。距離基站較近的簇由于簇間轉(zhuǎn)發(fā)功耗較高而設(shè)定較小的簇規(guī)模，通過減少簇內(nèi)部的能量消耗，補充簇間轉(zhuǎn)發(fā)數(shù)據(jù)的能耗;而距基站較遠的簇群在簇間的轉(zhuǎn)發(fā)消耗較少，從而可以劃分較大的范圍來包含更多的節(jié)點，增加簇本身的能量消耗。平衡了簇群在簇內(nèi)與簇間的功耗，有效增加無線傳感器網(wǎng)絡(luò)的生存時間。本文接下來的研究重心將放在尋找異構(gòu)、非靜態(tài)網(wǎng)絡(luò)環(huán)境里的節(jié)能算法。

［1］王磊，施榮華.無線傳感器路由算法中的仿真研究［J］.計算機仿真，2011，28(3):170－173.

［2］李志宇，史浩山.基于最小Steiner樹的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)融合算法［J］.西北工業(yè)大學學報，2009，27(4):558－564.

［3］沈波，張世永，鐘亦平.無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議［J］.軟件學報，2006，17(7):1588－1600.

［4］周新蓮，吳敏，徐建波.BPEC:無線傳感器網(wǎng)絡(luò)中一種能量感知的分布式分簇算法［J］.計算機研究與發(fā)展，2009，46(5):723－730.

［5］陶曉玲，王桂鳳，王勇.基于Dijkstra的無線傳感器網(wǎng)絡(luò)分簇路由算法［J］.計算機工程與設(shè)計，2010，31(17):3807－3811.

［6］王春雷，柴喬林，王華，等.基于分簇的無線傳感器網(wǎng)絡(luò)節(jié)能路由算法［J］.計算機應(yīng)用，2007，27(2):342－345.

［7］HEINZELMAN W，CHANDRAKASAN A，BALAKRISHNAN H.Energyefficient communication protocol for wireless microsensor networks［C］//Proc.the 33rd Annual awaii Int’l Conf.on System Sciences.Maui:IEEE Computer Society，2000:3005－3014.

［8］李成法，陳貴海，葉懋，等.一種基于非均勻分簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議［J］.計算機學報，2007，30(1):27－36.

［9］何延杰，李臘元，邢明彥.WSN中一種能量均衡的分簇路由協(xié)議的設(shè)計［J］.傳感技術(shù)學報，2009，22(10):1510－1514.