基于網格的無線傳感器網絡非均勻分簇算法

韓鵬瑋，王慶生，張 博

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

責任編輯:李 薇

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

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

1 典型路由協議分析

無線傳感器網絡的路由協議所包含的內容很多，但其核心思想是簇首選擇與分簇以及如何在簇間傳輸數據［3－4］。分簇方法有很多，簇內可以應用不同的數據交換方法。同時，由于選擇簇首采用的方法不同，算法也不相同［5－6］。

1.1 LEACH協議

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

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

1.2 EEUC協議

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

2 能量模型及網絡模型

2.1 能量模型

無線傳感器網絡節點能耗的主要來源是數據的采集、計算與傳輸，由于傳輸的能耗遠遠多于計算與采集的能耗，所以本文主要考慮網絡的傳輸，暫不考慮采集與計算的能量損失。本文采用和文獻［7］相同的傳輸模型。傳輸模型在發送數據和接收數據時，所消耗的能量為

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

2.2 網絡模型

在以S為邊長的正方形區域內隨機分布N個相同的節點。基站位于方形區域外。本文假設下述條件成立:

1)所有節點都具有相同的結構，具有一樣的數據處理能力以及無線通信能力，并且初始能量相同。

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

3)檢測的范圍遠大于無線傳感器網絡的邊界區域。

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

3 算法設計與實現

3.1 劃分網格

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

3.2 非均勻分簇

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

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

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

簇首節點在每一輪中的能耗為

簇內節點在每一輪中的能耗為

整個網絡在每一輪中的能耗為

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

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

從式(6)可以得出，最佳簇首個數與網絡的節點個數n、正方形區域邊長A和基站與正方形區域中心的距離LBS有關。

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

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

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

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

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

4 UECG仿真與性能分析

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

表1 網絡環境與參數配置

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

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

圖3 節點非均勻分簇示意圖

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

圖4 存活節點與網絡運行關系示意圖

圖5是基站接收到的數據總量，從圖5可以清楚地看出，UECG協議比LEACH協議和EEUC協議傳輸的基站接收到的數據總量多，這意味著無線傳感器網絡通信有更高的利用率。

5 結論

圖5 基站接收到數據量

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

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

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

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

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

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

［6］王春雷，柴喬林，王華，等.基于分簇的無線傳感器網絡節能路由算法［J］.計算機應用，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］李成法，陳貴海，葉懋，等.一種基于非均勻分簇的無線傳感器網絡路由協議［J］.計算機學報，2007，30(1):27－36.

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