基于圓環分區的非均勻分簇路由協議

鄭文軍，陳輝

(安徽理工大學 計算機科學與工程學院，安徽 淮南 232001)

0 引言

隨著無線傳感器網絡(WSNs)應用領域的增多，其相關理論和技術的研究也得到越來越多的學者的重視，目前已成為物聯網應用研究的一個重要研究方面。傳統WSNs中傳感器節點大多以逐跳轉發方式將數據發送至基站(Sink節點)，距離基站較遠的節點會以靠近基站較近的節點為轉發節點，最終將數據發送至基站。這會加重基站附近轉發節點的負載，提前耗盡能量而死亡，并加速了該死亡節點附近區域節點的死亡速度，最終造成網絡分割，影響網絡生存周期[1]。該問題也被稱為“熱區”問題。如何有效解決“熱區”問題，充分利用網絡能量是無線傳感器網絡協議亟待解決的關鍵之一。

目前，大量高效的無線傳感器網絡的“熱區”問題解決方法被眾多學者所提出。LEACH[2]是WSNs中最早提出的層次型路由協議，它在節約能量方面相對于平面路由協議效果更好，但是在簇首選舉過程中會出現簇首分布不均和低能量節點擔任簇首的問題[3]。文獻[4-5]分別提出了基于區域劃分的分簇路由協議MEET和DREEM-ME，通過將隨機分布的節點進行區域劃分來達到簇首分布均勻的目的，同時處于同一區域的節點構成一個簇并根據剩余能量選舉簇首。該協議使得節點能耗更加均衡，但是分布不夠合理，簇首選擇標準單一，“熱區”問題未能有效解決。針對MEET和DREEM-ME的缺陷，文獻[6]提出了一種基于分區的能耗均衡路由協議，將節點基于位置劃分，建立若干分布均勻的簇，限制了簇首分布的隨機性。但是文獻[7]中模擬實驗表明，在節點能量均勻、單一靜態Sink節點的WSNs中，當網絡生命結束時，網絡中可能有高達90%的能量沒有得到利用，而采用節點能量不均勻策略，可以大大提高網絡能量的利用率。因此，對于分簇網絡，根據簇與Sink節點距離的遠近采用非均勻分簇方法可以使得簇與簇之間能量不均等，進而可以達到均衡網絡能耗的目的。

文獻[8]提出基于分環思想的非均勻分簇路由算法RBMC，將監測區域劃分為等間距同心圓環模型，計算最佳簇首個數來均衡網絡能耗，達到了延長網絡壽命的目的，但是文獻[8]仍然采用LEACH閾值公式選舉簇首，沒有考慮節點能量與節點位置等因素。針對RBMC的缺陷，文獻[9]提出了ERBMC算法，通過在LEACH閾值公式中增加能量因素，并采用多輪選擇確定最優簇首；文獻[10]提出了一種能量高效的非均勻分簇算法，在“熱區”內選取多個能量較高的節點直接轉發數據至基站，均衡節點負載，非“熱區”內根據距離基站距離形成大小異構的簇來提高節點能量利用率；但是文獻[9-10]的簇首選舉方式都是基于LEACH的基礎之上，導致簇首分布的隨機性較大。文獻[11]提出一種非均勻分簇路由協議UCRP，通過簇首能量以及節點與基站間的距離來控制簇的大小，減小基站周邊簇首的接收能耗，能夠有效延長局部節點的生存時間，但是基于競爭產生的簇頭仍然存在能量浪費問題，因為候選簇頭較多，需要競爭的次數也較多。

本文提出的路由協議RPRP借鑒了上述算法的優點。首先，在區域劃分方面，將圓形網絡劃分成若干環，根據最優簇首數再將每層環內劃分成若干個區間，使得同一環內簇大小同構，不同環內簇大小異構；然后，在簇首選舉方面，每個分區內通過考慮節點剩余能量和簇內能耗最小兩個因素來選舉最佳簇首；最后，在數據轉發方面，通過三重約束條件來保證傳輸路徑最短的同時緩解內環節點的負載。RPRP協議避免上述文獻中出現的簇首分布不均，考慮因素單一等問題，且能夠有效地均衡網絡能耗，緩解“熱區效應”。

1 網絡與能耗模型

1.1 網絡模型

假設監測區域被橫向劃分成若干個環形區域，縱向劃分成若干個扇形區域。若傳感器節點隨機分布在網絡中，可能會使得基站附近節點較少或部分區域因缺少節點而產生空白區域，容易造成能量空洞，故網絡模型具有以下性質:

1)節點隨機均勻地分布在監測區域中。

2)Sink位于圓環的幾何中心點即圓心位置，能量不受限且不可移動。3)所有節點都具有唯一標識，且能量有限。4)節點位置信息已知，且發射功率可調節。

1.2 能耗模型

如圖1所示為網絡能耗模型圖，能耗模型參考主要文獻[12]。傳感器節點發射器發送kbit數據給相距為d的節點的能量消耗公式如下:

節點接收其他節點發送的kbit數據所消耗的能量為:

式中:Eelec為節點發送或者接收1bit數據節點內部電路所消耗的能量，d為節點間距離，d0為節點通信閾值，d0為節點通信閾值當d＜d0時，節點發送能耗符合自由空間模型，否則，其能耗符合快衰落模型，εfs和εmp為相應衰落的能耗系數。由于簇頭節點的融合能耗遠遠小于簇頭間的傳輸能耗，故本文忽略數據融合能耗。

圖1 網絡能耗模型圖

2 RPRP方案設計

2.1 基本思想

本文提出的RPRP路由協議，將圓形監測區域劃分成多個環并以網絡能耗最小為依據計算出最優簇首數目，避免了選舉的簇首數量過多或過少，使得網絡分簇更加合理。根據計算出的簇首數量對網絡進行合理的區間劃分，在每個分區內選舉出一個簇首，解決了簇首分布的隨機性問題；由于網絡非均勻劃分，距離基站越近，分區面積越小，簇的面積也越小，簇首能夠提供充足的能量轉發上游簇首的數據，能夠有效緩解“熱區”問題，達到網絡能耗均衡的目的。然后綜合考慮節點剩余能量和簇內能耗均衡2個因素選舉簇首，提高了簇首選擇的合理性。在數據轉發階段通過三重條件約束選擇出路徑最短，能耗較小的下一跳中繼節點，能夠有效緩解內環壓力，提高網絡性能。

2.2 非均等分區

2.2.1 網絡分環

RPRP協議首先對圓形網絡進行分環操作。初始化建立一個圓環形監測網絡，如圖2所示，每層圓的半徑ri=r+(i-1)δ。假設該圓形監測區域的半徑為R，整個網絡中的節點數量為N，節點初始能量為E0，網絡被劃分成H環(從內向外依次為 1，2，3…H)，除首環(第 1 環)外，其余每層環被劃分成m個區間，每個區間內有一個簇首節點。每層環內的節點數目為Ni，則有

本文采用簇內單跳簇間多跳的通信方式，外環簇首節點通過內環簇首節點中轉，最終將數據發送到基站。靠近基站的節點既為源節點，又為中繼節點，故節點距離基站越近，負載越大，如何處理該問題是緩解“熱區”的一個關鍵。根據文獻[13]可知，當首環半徑r滿足:

首環內節點直接發送數據到基站更節約能量。

圖2RPRP的分環模型圖

2.2.2 最優簇首數計算

無線傳感器網絡總的能量消耗Etotal主要分為簇內傳輸總能耗Elocal和簇間傳輸總能耗Eexter。其中簇內傳輸總能耗主要包括以下3部分:

①首環內節點直接發送數據給基站的能耗；

②第i(2≤i≤H)環內的成員節點發送能耗；

③第i(2≤i≤H)環內的簇首節點接收能耗。

綜合上述3點可得出每一輪數據周期第i環的簇內傳輸能耗為:

其中:Ri表示第i(i≠1)環每個區間內簇的半徑大小，可近似為:

簇間傳輸能耗主要包括兩方面:外環簇首的發送能耗和內環簇首的接收能耗。整個網絡的簇間傳輸能耗主要包括以下4個部分:

①首環內成員節點接收外環簇首數據的接收能耗。

②第2環簇首節點與首環內成員節點的通信能耗以及接收外環簇首數據的接收能耗。

③第3環到第H-1環內，簇首發送數據給內環簇首的發送能耗和接收上游簇首數據的接收能耗。

④第H環簇首的發送能耗。因為第H環為最外環，不需要承擔外環簇首的數據中繼責任。

綜合上述4點可得出每一輪數據采集周期第i環的簇間傳輸能耗為:

其中:d1-2表示第2環分區內簇首節點到首環成員節點的距離。其距離平方的期望E[d21-2]，有

綜合公式(6)和(7)可得出無線傳感器網絡數據采集一周的通信總能耗為:

其中Etotal是一個關于m的函數，對其求極值可得最優簇首數mopt。

2.3 簇的形成

分區內成簇主要包含簇的劃分和簇頭的選舉。

2.3.1 簇的劃分

如圖3所示，圓形網絡被劃分成H環，每層環形區域被劃分為mopt個區間，每個區間即一個競爭簇。記S(i，j)為區域中第i層的第j個區間，i?{1，2，3，...H}，j?{1，2，3，...mopt}。每個節點可根據自身的位置信息，獲得相對于基站的角度和距離信息，記s(k)為第k個節點，s(k).angle和s(k).dista分別為該節點相對于基站的角度和距離。s(k).layer和s(k).sec為該節點所屬的層和在該層的分區，若節點的方位滿足:

則s(k).layer=i，s(k).sec=j即確定了節點所屬的分區，該分區內的節點就構成了一個簇區域。

圖3RPRP的分區模型圖

2.3.2 簇頭的選舉

本文在分區中選舉簇首時，綜合考慮了節點能量和簇內能耗兩個因素，合理選舉簇首。

剩余能量因子反映了節點能量剩余的多少。若Ei越大，則表示剩余能量越多且消耗量越少，更適合作簇首節點。

簇內能耗因素Di表示節點i與所在分區內其余節點的距離平方和，由能耗模型可知，Di越小，簇內總能耗越小，越適合作簇首節點。

定義節點權值公式如下:

網絡中所有節點根據公式(12)計算自己的value值并廣播給所在分區內的其余節點，每個分區內value值最大的節點成為簇首。簇首選舉結束之后，簇首廣播消息宣布成為簇首節點，所在分區內其余節點加入該簇首，實現分區內成簇。

2.4 數據轉發

在數據轉發階段，距離基站較遠的外環簇首需通過內環簇首中繼將數據發送至基站。如何選擇合適的中繼簇首是本文協議的一個關鍵。本文設計的中繼簇首選擇策略按照以下3個條件為約束，既能夠保證通信路徑最短，同時又能減少網絡總能耗。

約束條件:1)外環簇首只能以同一扇形區域的內環簇首為中繼節點；2)外環簇首與下一跳簇首間的距離應小于通信閾值d0；3)當外環簇首有多個符合條件的下一跳簇首時，以文獻[11]中的能量開銷Erelay為依據選擇合適的下一跳中繼節點。

能量開銷的計算依據為:

其中:d2(si,sj)表示節點i與節點j的距離平方，d2(sj,BS)表示節點j與基站的距離平方。

同一扇形區域內的下一跳簇首選擇流程如下:

步驟1:初始化節點。所有節點初始能量相同且隨機均勻分布在網絡中。

步驟2:節點分級。與基站距離小于d0的簇首節點為一級簇首，與一級簇首距離小于d0的外環簇首節點為二級簇首，以此類推確定所有簇首等級。

步驟3:二級簇首將一級簇首作為中繼節點，一級簇首則直接與基站通信。當二級簇首有不止一個一級簇首可以選擇時，選擇能量開銷Erelay最小的一級簇首作為中繼節點。

步驟4:按照步驟3，依次確定所有簇首的等級，直至鏈路建立完成。

以圖4為例，0表示基站，1-5分別為各分區內的簇首節點。圖4(a)表示各節點間的關系，其中1、2與基站直接通信為一級簇首，3、4以一級簇首為中繼節點為二級簇首，5為三級簇首。簇首3、5通過計算各自的能量開銷Erelay選擇合適的中繼節點，最終形成如圖4(b)所示的數據轉發路徑。

圖4 數據傳輸路徑圖

3 仿真及結果分析

本文使用 MATLAB對 LEACH、UCRP和RPRP進行仿真，由于本文提出的RPRP主要針對于延長網絡壽命，故在節點存活數目和存活節點平均剩余能量兩方面來衡量本文協議的性能。

LEACH、UCRP和RPRP三種協議節點隨機均勻分布在半徑為R=200 m的監測區域內。首環半徑r取值過大會增加距離基站較遠的節點的負載，不利于均衡“熱區”內節點能耗，本文首環半徑取r=40 m，其余仿真環境參數如表1所示。通過設置環間距來計算不同環間距下網絡劃分環數H以及最優分區數mopt，具體參數如表2所示。

當環間距過小時，網絡中的簇首數量會較多，當環間距過大時，相鄰兩層間的簇首距離過大。故本文以環間距為30 m、40 m、50 m和60 m時的10%節點死亡時間作為參考依據選擇出較優的環間距。當環間距為30 m時，簇首劃分數量較多，增加了網絡的通信能耗；當環間距為50 m和60 m時，相鄰環簇首間的距離可能會超過通信閾值d0，會增加更多的通信能耗；當環間距40 m時，網絡被均等劃分，各環之間的間距均相等，不會導致最外環的簇過小而影響網絡的生命周期。如圖5所示，不同環間距下網絡中10%節點死亡時間對比可知，當δ=40時，效果最佳。

表1 仿真環境參數

表2 環間距與分區數確定

圖5 環間距與生存周期關系

圖6是LEACH協議、UCRP協議以及RPRP協議3種協議的網絡存活節點平均剩余能量關系圖。從圖中可以看出，本文提出的RPRP協議較其他兩種協議相比存活節點平均剩余能量坡度更小，能量消耗更加均衡，在處理“熱區”問題方面效果更好，網絡生存時間也更加持久。

圖6 網絡節點平均剩余能量對比

圖7是LEACH、UCRP以及RPRP三種協議的存活節點個數關系圖。從圖中可以得出，應用本文提出的RPRP算法時，雖然首個節點死亡時間早于UCRP協議，但是從總體來看相較于LEACH和UCRP網絡中節點存活個數更多。同時可以看出，相較于均勻分簇協議，在均衡網絡能耗方面非均勻分簇協議效果更佳。

圖7 網絡存活節點數量對比

圖8是三種協議在以基站為中心的80m范圍內的節點死亡率對比圖，從圖中的對比情況我們可以得知，本文協議能夠使得距離基站較近的節點存活的更久，在解決無線傳感器網絡的“熱區”問題上效果更佳。

4 結束語

本文提出了一種圓環分區的非均勻分簇路由協議RPRP，RPRP能夠合理劃分網絡，保證網絡總能耗最小。同時，在每個分區內根據節點剩余能量及簇內能耗最小為依據選舉出簇首節點，保證簇首選擇的合理性。在數據轉發階段，通過三重條件約束，既保證了網絡傳輸能耗較小，又能使得數據轉發路徑最短，有效緩解了網絡內環節點的負載，延長網絡生命周期。

圖8 基站附近節點死亡對比