基于分區的能耗均衡路由協議*

翟春杰，徐建閩，劉永桂*（.華南理工大學自動化科學與工程學院，廣州5064；.華南理工大學土木與交通學院，廣州5064）

?

基于分區的能耗均衡路由協議*

翟春杰1，徐建閩2，劉永桂1*
（1.華南理工大學自動化科學與工程學院，廣州510641；2.華南理工大學土木與交通學院，廣州510641）

摘要：為了均衡無線傳感器網絡的節點能耗，增強網絡穩定性，設計并實現了一種基于分區的能耗均衡路由協議。該協議設計了一種優化的分區算法，將節點基于分區劃分而形成簇，解決了先前協議中簇的個數和分布的隨機性問題；在選舉簇首時，綜合考慮了節點剩余能量、簇內節點能耗均衡、簇內部總能耗三個方面，采用三級簇首選擇機制，選擇的簇首既能均衡節點能耗，又可以降低簇群總能量消耗；在數據轉發時，普通節點選擇距離最近的簇首，在不超過通信距離閥值時，簇首可以隔層選擇下一跳簇首，有利于緩解無線傳感器網絡的“熱區效應”。仿真結果表明：相比MEET和DREEM-ME路由協議，該協議能更好地均衡節點能耗、增強網絡穩定性、改善網絡服務質量。

關鍵詞：無線傳感器網絡；能耗均衡；分區算法；簇首選擇機制

無線傳感器網絡與應用高度相關，單一的路由協議不能滿足各種應用需求。針對不同應用的特點，人們研究了眾多的路由協議，這些路由協議主要分為兩類：平面型路由協議和層次型路由協議。

層次型路由協議將網絡劃分成許多簇，每個簇會選出一個簇首來執行不同的任務，而簇內其它節點則會成為簇成員，簇成員將感知到的數據傳送給簇首，由簇首執行數據匯聚、融合來減少數據的重復性以及所需傳送的數據量，最后通過多跳的路由方式傳送給基站［1］。

LEACH［2］為最早提出的層次型路由協議，它可以有效降低節點能耗和延長網絡壽命，但是由于節點等概率地隨機擔任簇首，能量較低的節點也有可能成為簇首，造成節點能耗不均，影響網絡壽命；數據轉發采用簇首到基站的單跳方式，這會導致距離基站遠的節點會消耗過多能量。

首先，在簇首選擇方面，文獻［3-4］為了避免能量較低的節點擔任簇首，采用設定固定的最小能量閾值的方法來篩去剩余能量較少的節點，然而采用固定的最小能量閾值缺乏應用靈活性，為了解決這個問題，文獻［5］采用了隨著網絡整體能量下降而動態變化的節點剩余能量閾值。

然后，在數據轉發方面，為了解決LEACH中數據以單跳方式傳輸造成距離基站遠的節點消耗過多能量的問題，文獻［6-8］在簇首和基站之間的通信采用多跳方式，這樣有利于節約簇首能量，延長網絡周期。

為了均衡節點能耗、延長網絡壽命，在選擇簇首時盡量避免剩余能量較低的節點［3-5］，在數據轉發時多采用多跳方式［6-8］，但是這仍然無法改變簇分布不均和網絡“熱區效應”的現象，針對這一問題，文獻［9-10］分別提出了MEET和DREEM-ME協議，為了使簇首分布均勻，在簇形成方面，它們將隨機分布的節點根據位置進行分區，同一個分區中的節點構成一個簇，選擇簇中剩余能量最大的節點作為簇首；在數據轉發方面，仍然采用多跳方式，普通節點可選擇距離最近的簇首，而不只是所屬簇的簇首，同時簇首選擇下一層級最近的簇首。所建立的簇，分布比較均勻，節點能耗更加均衡，但是分區不夠合理，簇首選擇標準單一，“熱區效應”尚未有效地緩解。

本文在研究LEACH、MEET、DDR［11］等協議的基礎上，提出了基于分區的能耗均衡路由協議。該協議吸取了MEET、DREEM-ME等協議的分區思想，提出了一種更加合理的、可擴展的分區算法，分區更加科學、均勻；在簇首選擇方面，綜合考慮節點剩余能量、簇內節點能耗均衡、分區總能量消耗三個方面，選擇的簇首更加優化；在數據轉發方面，普通節點不受所屬簇的限制，可選擇距離最近的簇首，同時所設計的下一跳簇首選擇算法可進一步均衡節點能耗，有效地緩解了“熱區效應”。

1　建立簇首競爭簇

根據概率選擇簇首，由于簇首的分布隨機性很大，簇群的分布不均勻，導致節點能耗不均衡，影響網絡的壽命，本協議的關鍵之一在于將節點基于位置劃分，建立若干分布均勻的簇，這里的簇成員只參與競爭簇首，稱為簇首競爭簇，每一個競爭簇只能選出一個簇首，這樣保證了簇首的分布達到較優的狀態，有效地延長了網絡的壽命。實現競爭簇的劃分，要經過兩個步驟，首先對區域分區，然后節點根據自身所處的位置確定所屬的分區，也就確定了所屬的競爭簇。

1.1區域劃分

區域劃分的基本思想：根據鄰層簇首間以及簇首和競爭簇內普通節點之間的最大距離約束，將一個區域以基站為中心劃分成若干個層，再將每個層均勻地劃分成若干個分區。如圖1所示，將一個區域劃分為4層，每層又均勻地劃分出6或12個分區，下面說明以基站為中心的各圓半徑之間的關系。

設以基站由內而外的圓的半徑分別為r1、r2、r3、r4，以基站由內而外的層分別為A層、B層、C層和D層；由于節點通信時，能耗會隨著節點間的距離而變化，設d0為節點間通信距離門限值，距離小于d0的節點通信，能耗則符合慢衰落模型，反之，大于或等于d0的節點通信，其能耗則符合快衰落模型[12]。為使節點通信降低能耗，區域劃分有三大原則：其一，B層簇首距離基站的最大距離為d0；其二，相鄰兩層最鄰近競爭簇的簇首間的最大距離為d0；其三，每層競爭簇的普通節點與該競爭簇簇首的最大距離小于d0。這樣在數據轉發時，就保證了普通節點與簇首、簇首與簇首、簇首與基站之間通信的距離均小于d0，通信能耗符合慢衰落模型。

如圖2所示，基于以上3個劃分原則，在ΔPOQ中，由三角形面積公式可得

圖2　參數分析示意圖

同時由海倫公式可得

由式（1）和式（2）可得

從而得出了r1，r3，d0，θ之間的關系式

在ΔMON中，同理由三角形面積公式可得

由海倫公式可得

由式（4）和式（5）可得

從而得到了r4，d0，θ之間的關系。

同時由于第一條劃分原則可得

綜上，基于3個劃分原則基礎上所得到的區域劃分為四層的約束方程為：

1.2建立簇首競爭簇

記S(i，j)為區域中第i層的第j個分區，i∈{A，B，C，D}，j∈{Ⅰ，Ⅱ，…，Ⅻ}，S(i，j).angle為該分區在以基站為圓心的角度區間，S(i，j).dista為該分區相對基站的軸向分布區間，其中

S(i，j).angle=(S(i，j).angle.orig，S(i，j).angle.end]

S(i，j).dista=(S(i，j).dista.orig，S(i，j).dista.end]

這里的S(i，j).angle.orig，S(i，j).angle.end，分別為該分區相對于基站的起始角度和終止角度，S(i，j).dista.orig，S(i，j).dista.end分別為該分區相對于基站軸向的起始距離和終止距離。

如圖3所示可以清楚地獲悉S(C，Ⅱ).angle.orig，S(C，Ⅱ).angle.end，S(C，Ⅱ).dista.orig，S(C，Ⅱ).dista.end的具體含義。

設有N個節點隨機分布在區域內，通過TSTOA[13]定位算法，可以得到每個節點相對于基站的方位，并進一步獲取節點相對于基站的角度和距離的信息，記s(k)為第k個節點，s(k).angle和s(k).dista分別為該節點相對于基站的距離和角度，s(k).layer 和s(k).sec為該節點所屬的層和在該層的分區，若節點的方位滿足

則s(k).layer=i，s(k).sec=j即確定了節點所屬的分區，該分區的所有節點就構成了簇首競爭簇，競爭簇形成算法如圖4所示。

圖3　距離、角度概念的示意圖

圖4　傳感節點劃分算法流程圖

2　簇首選擇

節點隨機分布在區域后，根據它們的方位信息就可以確定其所屬的分區，這樣分區中所有的節點組成一個簇，如何選擇簇首以便增強網絡的穩定性，提升網絡的服務質量是本協議的第2個關鍵。

2.1能耗模型

節點的能耗集中在節點工作期間，節點休眠時的能耗很小，在建立能耗模型時，主要考慮節點工作能耗，而工作能耗包括接收數據時的接收能耗和發送數據時的發送能耗；考慮發射端與接收端受距離影響的信號衰落，包括自由空間衰落和多徑效應，便得到如下發送和接收單位比特的節點能耗表達式［12］

其中Tenergy為節點發送單位比特數據的能耗，Renergy為節點接收單位比特數據的能耗，Eelec為發送電路和接收電路的能耗，d0為收發兩端距離的門限值，εfs，εamp為相應衰落的恒定參數。

在數據轉發時，普通節點根據距離最近的原則選擇加入某個簇首，這樣就建立了基于簇首的數據轉發簇，若數據轉發簇中至少存在一個普通節點，可以建立下面的數據轉發能耗模型，這里只是考慮數據轉發簇內的能耗模型。

若簇首為區域第j個簇首，其所在的數據轉發簇就記為j個數據轉發簇，則簇內普通節點s(i)向簇首發送li比特數據的能耗為

簇首接收節點s(i)發來的li比特數據的能耗為

則所有普通節點向簇首發送數據的能耗為

其中Noj為第j個數據轉發簇內普通節點的個數。簇首接收數據的能耗為

則該數據轉發簇總能耗為

一般情況下，普通節點向簇首發送的數據包相同，設定為l比特，那么簇首便收到Noj×l比特數據，普通節點的發送能耗

簇首的接收能耗

數據轉發簇總能耗

2.2簇首選擇機制

選擇簇首是在簇首競爭簇中進行的，也就是每個分區中所有節點參與競爭該分區的簇首，而分區節點數目固定，由能耗模型可知，普通節點的能耗取決于距離簇首的距離，簇首的能耗不變，競爭簇總能耗取決于普通節點到簇首的距離平方和。

本協議所解決的問題在于，一要選擇競爭簇中剩余能量較大的節點作為簇首，二要保證競爭簇中節點能耗均衡，三要保證競爭簇總能耗較小。能耗均衡與競爭簇總能耗較小與競爭簇的拓撲結構有關，當節點隨機分布后，其位置一般不會改變，不同的節點擔任簇首，就形成了不同的競爭簇的拓撲結構。

若要保證普通節點能耗均衡，就是要把普通節點到簇首的距離的方差限制在一定范圍內，而要保證競爭簇總能耗較小就要使普通節點到簇首的距離平方和較小。

在選擇簇首時，本文綜合考慮簇首的剩余能量，普通節點到簇首距離的方差和普通節點到簇首距離的平方和3個方面，采用下面的3級簇首選擇機制：

第1級：保證簇首的剩余能量較高。將競爭簇的節點按照剩余能量降序排列，設該競爭簇的存活節點數目為N1，若1≤N1≤2，則將排在第一的節點設置為簇首；若N1≥3，若取出排名前的節點作為候選簇首，n1∈[2，N1]；

第2級：保證普通節點的能耗均衡。第一級獲取的候選簇首，分別假設為簇首，求出每個候選簇首對應的能耗方差，把候選簇首按照方差進行升序排序，若N2=2，則將排在第一的候選簇首設置為簇首，若N2≥3，取出排名前的候選簇首作為待定簇首，n2∈[2，N2]；

第3級：保證競爭簇總能耗較小。分別計算第二級獲取的待定簇首為簇首時對應的總能耗，并將待定簇首按照總能耗進行升序排列，取出能耗最小的待定簇首作為該競爭簇的簇首。

所采用的3級簇首選擇機制，兼顧了簇首剩余能量、普通節點的能耗均衡、競爭簇總能耗3個方面，但這3個方面的優先程度不同，首先保證簇首剩余能量處于競爭簇的較高水平，其次保證待定簇首所對應的能耗方差較小，最后保證所選簇首對應的最小總能耗較小。

3級簇首選擇機制在選擇簇首方面十分靈活，它可以通過調整n1和n2的值，合理地分配給簇首剩余能量、簇內節點能耗均衡和競爭簇總能耗相應的權重，從而有利于滿足多種應用需求，本文后面的仿真中取n1=n2=2。

3　數據轉發

本文提出的路由協議具有可擴展性，這就意味著某一節點可能距離基站很遠，直接向基站傳輸數據會產生很大的能耗，因此本協議采用了3層通信架構，即普通節點到簇首、簇首到簇首和簇首到基站的數據轉發［10］。首先，普通節點將感知的數據轉發給距離最近的簇首，然后該簇首對接收的數據進行融合后選擇下一跳簇首轉發，最終數據會到達基站，因此在數據轉發時，如何選擇下一跳簇首則是本文協議的第3個關鍵，本文設計了下一跳簇首選擇算法，既均衡了節點能耗，又減少了網絡總能耗。

由于節點的隨機分布，網絡數據轉發時會出現熱區效應，即內層節點能量消耗要比外層節點要快，之所以出現這種現象，原因在于內層簇首不僅要處理簇內節點的數據，還要接收、融合、轉發外層簇首轉發來的數據。本文提出的下一跳簇首選擇算法，一方面，為了緩解“熱區效應”隔層選擇簇首，確保內層節點的能耗速度不要過快，另一方面，在隔層選擇下一跳簇首上加入d0條件約束，確保隔層節點的數據轉發能耗符合慢衰落能耗模型，減少了能量消耗。

下一跳簇首選擇算法

if S（i）. Energy>0 & S（i）.IsHeader==0//存活著的普通節點

S（i）. NextHop=min{dis.CHAI，...，dis.CHAVI，dis.CHBI，dis.CHBII，...，dis.CHBXII，...，dis.CHDXII}

//選擇距離最近的簇首作為數據轉發的下一跳節點

else if S（i）. IsHeader==1//簇首節點

if S（i）. Layer==D//該簇首節點位于D層

if min{dis.CHBI，dis.CHBII，...，dis.CHBXII}

//該簇首節點距B層簇首節點的最小距離小于等于d0

S

（i）. NextHop=min{dis.CHBI，dis.CHBII，...，dis.CHBXII}

//選擇距離該簇首最近的B層簇首作為數據轉發的下點

else

S（i）. NextHop=min{dis.CHCI，dis.CHCII，...，dis.CHCXII}

//選擇距離該簇首最近C層簇首作為數據轉發的下一跳節點

if S（i）. NextHop==0//C層傳感節點全部死亡

S（i）. NextHop=min{dis.CHBI，dis.CHBII，...，dis.CHBXII}

//選擇距離該簇首最近B層簇首作為數據轉發的下一跳節點

endif

if S（i）. NextHop==0//B層傳感節點全部死亡

S（i）. NextHop=min{dis.CHAI，dis.CHAII，...，dis.CHAVI}

//選擇距離該簇首最近B層簇首作為數據轉發的下一跳節點

endif

if S（i）. NextHop==0//A層傳感節點全部死亡

S

（i）. NextHop=BS//傳輸數據直接送基站

endif

endif

endif

if S（i）. Layer==C

if min{dis.CHAI，dis.CHAII，...，dis.CHAVI}

S（i）. NextHop=min{dis.CHAI，dis.CHAII，...，dis.CHAVI}

else

S（i）. NextHop=min{dis.CHBI，dis.CHBII，...，dis.CHBXII}

if S（i）. NextHop==0

S（i）. NextHop=min{dis.CHAI，dis.CHAII，...，dis.CHAVI}

endif

if S（i）. NextHop==0

S（i）. NextHop=BS

endif

endif

endif

if S（i）. Layer==A|| S（i）. Layer==B

S（i）. NextHop=BS

endif

endif

endif

4　算法仿真分析

本文采用MATLAB對MEET、DREEM-ME和本文協議進行仿真，在節點存活數目、簇首數據包接收數量、網絡剩余總能量三個方面進行比較，以此檢驗本文協議的性能。在仿真時，與MEET和DREEM-ME協議最初均勻分布節點不同，為更加貼近實際，本文在三種協議的仿真中，均使用相同隨機分布的節點，同時擴大了最初MEET和DREEMME協議的仿真規模。

4.1仿真參數設置

仿真是在相同的隨機節點分布、相同的數據包大小、相同的能耗模型等的基礎上，分別采用MEET、DREEM-ME和本文協議，創造路由協議仿真的唯一差異性，從而使仿真結果具有很強的說服力，具體仿真參數設置如表1所示。

表1　協議仿真相關參數設置

4.2仿真結果

4.2.1網絡存活節點數量

穩定期是以網絡第一個節點死亡的時間計算，如圖5所示，本文協議的第一個死亡節點是在第425個周期，而MEET和DREEM-ME協議第一個死亡節點則分別在第4個和第10個周期。顯而易見，在保持網絡的穩定性上，本文協議要遠比MEET 和DREEM-ME協議優越。

就所有節點死亡的時間看，MEET和DREEMME協議相同，比本文協議要長。在第1600個周期時，三種協議的存活節點數量相近，約有30個，約占總節點的6%，并且主要分布在基站附近，覆蓋面積極小，從某種程度上可以說，網絡有效壽命已盡，這說明了同MEET和DREEM-ME協議相比，本文協議基本上不改變網絡有效生存期。

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

4.2.2簇頭接收的數據包

如圖6所示，MEET和DREEM-ME協議分別在1096個周期、1105個周期后就只剩下直接與基站進行通信的節點，而本文協議在1871個周期后才只剩下直接與基站通信的節點，這都說明了在整個網絡的有效生存期內，本文協議簇頭接收的數據包數量要遠大于MEET和DREEM-ME協議，通常簇頭接收的數據包越多，越表明網絡的有效監測覆蓋率就越大，網絡的服務水平就越高。

圖6　簇頭接收的數據包對比

4.2.3網絡剩余能量

如圖7所示，在整個網絡有效生命期間內，本文協議的網絡剩余能量要大于MEET和DREEMME協議，說明了本文協議在節省網絡總能耗方面要優于MEET和DREEM-ME協議，這對于提高網絡的服務質量很有幫助。

圖7　網絡剩余能量對比

5　結論

為了能夠使網絡節點能耗均衡，增強網絡穩定性，提高網絡服務水平，本文提出了更加優化的分區算法、三級簇首選擇機制和下一跳簇首選擇算法。其中，分區算法解決了網絡中簇首分布隨機性的問題，使得簇首均勻分布在整個區域范圍內；三級簇首選擇機制，綜合考慮了節點剩余能量、簇內節點能耗均衡、簇內部總消耗三個方面，選出的簇首既有利于均衡網絡節點的能耗，同時在一定程度上可以減小總的網絡能耗；下一跳簇首選擇算法，則用來解決距離基站較遠的節點通過多跳的方式向基站傳輸數據，緩解了網絡的熱區效應。

對本文的路由協議進行了MATLAB仿真，評價其相關指標，并將其與MEET和DREEM-ME協議進行對比，仿真結果表明，在網絡存活節點、簇頭接收的數據包數量和網絡剩余能量等方面，基于分區的能耗均衡路由協議要明顯優于MEET和DREEM-ME協議。

參考文獻：

［1］許韻.無線傳感器網絡中層次型鏈式路由協議的研究［D］.安徽：安徽大學，2011.

［2］Heinzelman W R，Chandrakasan A，Balakrishnan H. Energy-Effi?cient Communication Protocol for Wireless Microsensor Networks ［C］//Proceedings of the 33rd Hawaii International Conference on System Sciences，2000. IEEE，2000：10.

［3］曹建玲，劉文朋，彭雙，等.一種基于能耗均衡的ZigBee網絡高效混合路由算法［J］.電訊技術，2013，53（10）：1352-1356.

［4］董亮，張靈，陳云華.基于限制廣播的ZigBee分布式動態能量均衡協議［J］.傳感技術學報，2014，27（8）：1120-1124.

［5］何杏宇，周亦敏，楊桂松，等.無線傳感器網絡能量感知增強樹型路由協議研究［J］.傳感技術學報，2015，28（4）：551-556.

［6］劉慶，王培康.無線傳感器網絡的安全分簇路由協議［J］.計算機仿真，2009，26（4）：167-171.

［7］張文祥，馬銀花，郭繼坤.無線傳感器網絡路由算法的研究［J］.計算機測量與控制，2009，17（3）：617-619.

［8］童夢軍，關華丞.基于蟻群算法的能量均衡多路徑路由算法的研究［J］.傳感技術學報，2013，26（3）：425-434.

［9］Saleem F，Javaid N，Moeen Y，et al. MEET：Multi-Hop Energy Ef?ficient Protocol for Energy Hole Avoidance using Variable Trans?mission Range in Wireless Sensor Networks［C］//9th International Conference on Broadband and Wireless Computing，Communica?tion and Applications. IEEE. 2014：478-484.

［10］Amjad N，Javaid N，Haider A，et al. DREEM-ME：Distributed Re?gional Energy Efficient Multi-Hop Routing Protocol based on Max?imum Energy in WSN［C］//8th International Conference on Broad?band and Wireless Computing，Communication and Applications. IEEE. 2013：43-48.

［11］Ahmad A，Latif K，Javaid N，et al. Density Controlled Divide-and-Rule Scheme for Energy Efficient Routing in wireless sensor net?works［C］// 26th IEEE Canadian Conference Of Electrical And Computer Engineering（CCECE）. IEEE. 2013：1-4.

［12］唐毅，梁曉曦，武俊.無線傳感器網絡最優簇首節點數量研究［J］.通信技術，2007（6）：30-32.

［13］盧翔，涂時亮，陳章龍.對無線傳感器網絡定位算法的比較和分析［J］.計算機應用與軟件，2009，26（12）：199-201，285.

翟春杰（1989-），男，安徽亳州，碩士研究生，主要研究領域為智能控制理論與應用，auchunjiezhai@mail.scut.edu.cn；

劉永桂（1978-），男，湖南邵陽，博士，副教授，主要研究領域為無線傳感器網絡，auygliu@scut.edu.cn。

徐建閩（1960-），男，山東招遠，博士，教授，博士生導師，主要研究領域為智能控制理論與應用、交通信息工程及控制、智能交通系統等，aujmxu@scut.edu.cn；

Minimum Transmit Power Based Distributed Relay Selection in Wireless Networks*

WU Hang1，QIAN Liping1*，CHEN Qingzhang1，LU Weidang2
（1.College of Computer Science and Technology，Zhejiang University of Technology，Hangzhou 310023，China；2.College of Information Engineering，Zhejiang University of Technology，Hangzhou 310023，China）

Abstract：Relay cooperation has been proposed as a promising solution to improve the energy efficiency and service quality of edge users. In this regard，this work proposes a distributed auction-based relay selection algorithm to mini?mize the total transmit power consumption for dual-hop decode-and-forward relay networks over Rayleigh fading channels. In particular，we first provide the optimal power consumption of any cooperative transmission in the closed-form expression. Then，we design a distributed relay selection algorithm that assigns every user to the appro?priate relay node based on the idea of auction. Simulation results show that every user node can find its best coopera?tive relay through limited message passing with relay nodes.

Key words：wireless network；relay selection；auction algorithm；multi-user multi-relay

doi：EEACC：6150P10.3969/j.issn.1004-1699.2016.01.016

收稿日期：2015-08-13修改日期：2015-10-12

中圖分類號：TN92

文獻標識碼：A

文章編號：1004-1699（2016）01-0080-08

項目來源：國家自然科學基金項目（61573153）；廣州市科技計劃項目（201510010132）