基于通信節點的WSN自主聚類非均勻分簇路由協議

劉一玨, 王 軍, 田 鹍

(沈陽化工大學 計算機科學與技術學院，遼寧 沈陽 110142)

無線傳感器網絡(WSNs)是由大量的微型傳感器節點通過無線通信部署在監控區域中形成的自組織網絡系統.通過傳感器節點收集和聚集環境信息，最后將數據發送到基站進行進一步處理.許多領域，如軍事、航空、環境、醫療等都可以受益于無線傳感器網絡的應用[1-2].然而，無線傳感器網絡仍面臨許多挑戰.因為傳感器節點的能量非常有限，所以能量消耗是首要考慮的問題.研究表明，分簇路由可以更好地降低傳感器節點的能量消耗，平衡網絡能量分布，延長網絡壽命[3-4].LEACH[5]是基于分簇路由協議提出的，該協議利用簇頭的隨機選擇，在網絡中的傳感器之間均勻地分配能量負載，有效地從全局角度減少能量耗散并提高網絡壽命.但該協議仍有許多不足之處[6-7].近年來，基于簇的路由協議不斷完善，提出了LEACH-C、HMR等[8-10].然而，這些分簇路由協議仍存在一些問題，如簇頭開銷過大、多跳傳輸不合理等，導致靠近基站的節點重載流量等.

LEACH的缺點是簇頭分布的不均勻導致了一些網絡區域的能量消耗過大以及可用性差.隨后提出了許多改進意見.LEACH-C[11]是一種基于LEACH的改進版本，其使用基站來形成集群并減少節點在創建集群時的能量消耗；LEACH-CC[12]是一種基于功率的LEACH-C的改進，其通過改變簇頭節點的范圍來平衡網絡的能量分布；LEACH-H[13]采用遺傳算法(GA)獲得簇首選擇的閾值公式，GA優化了公式的3個因素，包括節點的剩余能量、鄰居的數量、節點和節點與基站之間的距離；基姆等[14]提出了一種利用新的概率函數確定每個回合中簇首數目的方案.上述協議改進了具有中心控制機制和剩余能量的簇首選舉算法，還引入了其他參數來保證簇頭的良好分布.但由于存在節點間距離相對較長的情況，所以數據傳輸會消耗大量的節點能量[15-17].

本文提出一種基于通信節點和多跳傳輸相結合的多因素自主聚類分簇路由MFACRP(mutile factors autonomous clutering routing protocol)協議.定義了2種主要節點：通信節點和簇頭節點.為減少簇首的負擔，采用通信節點進行中繼，實現多跳數據傳輸.當選擇簇頭時，仔細考慮節點剩余能量、節點位置和鄰居節點數等多個因素.新協議有效地減少節點的能量消耗，更好地平衡網絡的能量分布，并大大延長網絡的壽命.實驗評估表明采用多跳路由和雙功能節點相結合的方法可以延長網絡的使用壽命.

1 系統假設和能量消耗模型

1.1 系統假設

不同的無線傳感器網絡路由協議有不同的應用場景.MFACRP協議的應用場景具有以下特點：

(1)傳感器節點采用正態分布隨機部署在監控區域內，基站位于監控區域之外.

(2)傳感器節點和基站在部署后位置固定，傳感器節點的能量有限，基站的能量不受限制.

(3)傳感器節點通過接收信號強度與節點間距離之間的關系確定監測區域內節點的位置.

(4)傳感器節點周期性地收集檢測區域內的數據并將數據發送到基站.

(5)每個傳感器節點的無線電發射機功率是可控的.節點可以根據發射距離選擇無線電發射機的功率.

1.2 拓撲結構

根據所提MFACRP協議的應用場景的描述，假設傳感器網絡中有N個節點，并且基站位于監控區域之外.傳感器節點的位置隨機分布在監視區域中，且基站位置固定.將N個節點通過二維正態分布[18]將其部署在監視區域上.它被描述為

(1)

其中：(mi，ni)表示節點i的部署點；σm和σn分別是M維和N維的標準偏差；相對位置參數(m，n)作為該區域的中心點.如圖1所示，以基站為中心，將網絡區域劃分為內部區域和外部區域，以對應于單跳和多跳傳輸.內部和外部區域中的節點通過分層方法被組織成許多局部聚類.每個簇中有簇頭和一些標準節點(非簇頭節點).標準節點收集監測區域內的信息并將數據發送到相應的簇頭.簇頭收集并聚合數據，然后根據它們所在的區域通過單跳或多跳傳輸將數據轉發給基站.中間通信節點用來中繼數據傳輸，平衡通信節點兩端節點的能量消耗，減輕簇頭的負載，降低簇頭節點的能耗.

圖1 拓撲結構

1.3 能耗模型

網絡節點發送數據時其能耗模型[6]為

(2)

式中:Eelec為節點發送或接收單位數據所耗費的電路能量,其大小受信號的編碼方式、處理以及傳播方式所影響；l為要發送或接收的數據長度(比特)；d為數據發送所經過的有效距離(當d

Erx(l)=lEelec.

(3)

此種模型是無線通信過程中采用的標準模型，通信過程中融合數據所消耗的能量不做考慮.

1.4 協議中的符號

為平衡所有節點之間的能量消耗，需要獲得整個網絡中節點剩余能量的水平.引入下面的剩余能量估計方法來粗略估計網絡的每個操作回合消耗的能量.

假設E0是網絡中每個節點的初始能量，引入常數R來表示無線傳感器網絡的理論運行周期，每個回合中每個節點的平均能量消耗定義為

(4)

在第r輪中，每個節點的平均剩余能量定義為

(5)

其中：E(r)表示節點在每輪成功當選為簇首的能量閾值，僅當節點的剩余能量大于閾值時，節點才會有機會被選擇為簇頭.

協議中還定義了節點到基站的平均距離的計算方法，用常數davg來表示.由于節點隨機部署在監測區域，所以采用以中間為基準的方法，將監控區域中心到基站的距離作為平均距離.計算公式為

(6)

其中：(X,Y)表示基站的坐標；(x，y)表示監視區域中心的坐標.

Davg表示節點的相鄰節點的平均數目.計算公式為

(7)

其中：S表示所有的節點的集合；Ddgee(i)表示節點i的鄰居節點的數目.

2 MFACRP路由協議

MFACRP協議與現有的分簇路由協議類似，MFACRP協議也是采用一輪再一輪地不斷完善和修訂的簇頭和簇間數據傳輸路徑的過程.

無線傳感器網絡首先執行初始化過程，然后將監測區域劃分為單跳和多跳傳輸區域，接著進行一輪再一輪的簇頭選取和簇間數據傳輸路徑優化工作.每一輪MFACRP分為2個階段：聚類和穩定傳輸.聚類階段包括選舉通信節點和簇頭節點；穩定傳輸階段處理簇間多跳路由和數據傳輸.為了減少由聚類引起的額外能量消耗，穩定傳輸階段應遠長于聚類階段.MFACRP的工作過程如圖2所示.

圖2 工作時隙圖

2.1 協議初始化

在聚類階段，無線傳感器網絡通過執行初始化，根據節點到基站的距離，將網絡的監視區域劃分為內部區域和外部區域.劃分內外區域的目的是減少簇頭節點與基站數據傳輸的平均距離，平衡傳感器節點的能量消耗.

在初始化期間，每個傳感器節點需要通過接收信號強度指示(RSSI)來估計自己與基站的距離.首先，基站向網絡中的所有節點發送廣播消息，然后每個節點根據接收到的信號強度來估計自己與基站的距離.每個節點獨立地決定它屬于哪個區域.如果節點與基站之間的距離小于閾值，則節點屬于內部區域，否則節點位于外部區域.這里將網絡節點最大傳輸距離的一半作為劃分區域的閾值.

簇頭采用單跳或多跳傳輸，當簇頭節點與基站之間的距離小于閾值時，多跳傳輸的能量消耗大于單跳傳輸的能量消耗.因此根據它們所在的區域向基站轉發數據.在內部區域中，由簇頭聚合的數據將通過單跳傳輸直接發送到基站，而外部區域中的簇頭將通過多跳傳輸將聚合數據發送到基站.

2.2 協議工作過程

為減輕個別簇頭的通信量可能過大的問題，引入通信節點進行中繼和小區域的簇頭選擇.在簇頭選舉階段開始時，通過閾值確定通信節點，然后由通信節點選擇簇頭.根據節點的能量和節點位置，優化簇頭的選舉過程.通過改進的簇頭選舉算法，可以保證簇頭的合理分布.

2.2.1 成簇階段

在MFACR協議中，進行成簇時必須首先選擇通信節點.通信節點的選舉算法采用與LEACH簇首選舉算法類似的算法，這樣能夠確保所選通信節點可以在網絡中分布均勻，不會出現通信節點空白區.通信節點作為多跳傳輸的中繼節點，負責選擇簇頭.每個節點在0和1之間產生一個隨機數，以決定是否成為通信節點.只有當隨機數小于閾值T(n)時，它才成為通信節點.閾值T(n)計算公式為

(8)

其中：預定義參數p表示當選為通信節點的概率；參數r表示當前輪數；G是在上一輪中沒有被選擇為通信節點的節點集合,即當一個節點在此輪中作為通信節點，它就不能成為下一輪中的通信節點.

簇頭由通信節點選出，而不采用傳統的基站選擇簇頭的方法.這樣保證了簇頭節點與通信節點的距離最優且合理地分布在網絡中，同時還減少了在通信過程中與基站通信的能量消耗.

在選擇簇頭的過程中，每個通信節點向一定距離內的節點發送廣播消息，并從接收廣播消息的節點接收響應消息.一旦非通信節點在本回合中接收到廣播消息，它們將向通信節點發送它們的響應.響應消息為

Rep[i,E(i),dtoBS(i),Ddgee(i)].

(9)

其中：i表示節點i的ID；E(i)表示節點i的當前剩余能量；dtoBS(i)代表節點i與基站的距離，Ddgee(i)是節點i的鄰居節點數.

通信節點i分別計算出向其發送響應消息的節點的閾值Gi(n)，然后選擇具有最大閾值的節點作為簇頭.閾值計算公式為：

(10)

式中：w1、w2、w3分別為節點剩余能量、與基站的距離、鄰居節點的數量3個因子的權重值；E(r)表示節點在第r輪中成為簇頭的能量閾值；davg表示所有節點與基站的平均距離；Davg表示所有節點鄰居節點的平均數目.從公式(10)可以看出：剩余能量越大，與基站距離越近，鄰居節點越多，則節點當選簇首的概率就越大.

在選擇簇頭之后，每個簇頭向網絡中的所有節點廣播成簇消息.在接收到消息之后，每個非簇頭節點根據所接收信號的強度來決定它加入哪個簇.同時，每個非簇頭節點需要向自身選擇的簇頭發送連接請求消息.一旦形成簇，簇頭便會創建TDMA調度，指定分配給簇中每個成員節點固定的通信時隙，并將此TDMA調度計劃廣播回簇中的每個成員節點.

2.2.2 協議的二次聚類

圖3 二次聚類結構

由于簇頭都是由通信節點選出，所以選出距離通信節點最近的節點作為新簇頭進行數據傳輸.這樣很大程度減少簇頭因頻繁傳輸數據而造成能量損耗，從而增加網絡的生存時間.

2.2.3 穩定傳輸階段

在聚類階段之后，穩定的數據傳輸階段開始.非簇頭節點在簇頭給它們分配的通信時間段內將它們的數據傳輸到簇頭，數據將聚集在簇頭中，然后發送到基站.位于內部區域的簇頭將直接將聚合數據發送到基站.而位于外部區域的簇頭將通過多跳傳輸將數據轉發給基站.通信節點被用作多跳傳輸的中繼節點.

3 實驗結果分析

使用MATLAB驗證MFACRP協議的性能，從整個網絡的剩余能量、存活節點數和死節點數等方面來評估網絡壽命.實驗比較了LEACH、LEACH-H、HMR和MFACRP的性能.

假設300個節點在邊長300 m的正方形區域的無線傳感器網絡中隨機分布，為了簡單起見，假設基站位于該區域之外，位于(350,350)的位置.仿真中的其他參數列于表1中.

簇頭選舉閾值公式中各因子的權重依次為W1=0.6，W2=0.27，W3=0.13.

表1 仿真參數

節點的剩余能量能夠反映網絡總能耗的狀態，所以可以通過網絡中節點的剩余能量來衡量網絡壽命.在運行相同輪數的情況下，網絡中節點的剩余能量越多，網絡能量利用效率越高.

在仿真實驗中，規定網絡生存周期從開始到存活節點的數量小于總節點的10 %結束.因此穩定期即為從網絡運行開始直到死亡節點的數目超過總節點的90 %時.穩定期越長，協議的性能越好.

圖4顯示了在相同環境下，LEACH、LEACH-H、HMR和MFACRP在經歷了相同輪次后的存活節點數量變化趨勢.在協議運行過程中，協議的穩定周期分別達到230輪、531輪、866輪和1 274輪.4種協議的生命周期分別為966輪、1 262輪、1 252輪和1 581輪.與LEACH協議相比，兩個改進的協議LEACH-H和HMR可以有效地將網絡壽命延長近31 %.而MFACRP的壽命可延長64 %.在MFACRP協議中，穩定傳輸階段期間采用通信節點作為數據傳輸的中繼，這種改進降低了節點與基站通信的能量消耗，并解決了簇頭的通信過載問題.通信節點的引入有效地延長了穩定期.

圖4 節點數量對比

數據傳輸性能可通過基站接收的數據包數量來證明.圖5顯示了在相同環境中相同運行輪次下LEACH、LEACH-H、HMR和MFACRP協議的基站接收數據包數量變化趨勢.

圖5 接收數據包對比

從圖5可以看出：隨著操作輪次的增加，基站在MFACRP協議中接收的數據包數量遠遠大于相同輪次下其他協議接收的數據包數量.在MFACRP中發送到基站的數據包大約在第 1 500 輪時飽和，同時基站大約接收了20 800個數據包.基站在LEACH、LEACH-H和HMR中接收的數據包數量遠小于MFACRP.因此，MFACRP協議可以顯著提高數據傳輸能力和交互能力，表明在相同的運行環境中可以收集更多的數據并且提高網絡性能.

4 結 論

如何有效利用有限的節點能量來延長無線傳感器網絡的生存時間是無線傳感器網絡面臨的一個重要挑戰.本文提出的MFACRP協議以減少傳感器節點的能量消耗，同時使網絡節點能量負載均衡，以及優化簇頭的選擇.為了減少簇頭的能量開銷，引入通信節點作為多跳傳輸的中繼節點，通信節點同時負責選擇簇頭.為使簇頭選舉過程更加合理高效，在成簇完成后，對于重疊度較高的簇重新進行聚類.為了適應不同的傳輸方式，將監控區域劃分為不同的區域，簇頭將采用單跳或多跳傳輸，根據它們所在的區域將數據轉發給基站.同時MFACRP協議利用局部最優路徑構造算法來有效減少多跳路徑中節點的能量消耗.仿真結果表明，該協議能夠提高節點的能量利用效率，有效地平衡網絡的能量分布，從而延長網絡的使用壽命.