結合節點分組和門限優化的改進EEUC機制

黃金國，劉 濤，周先春，嚴錫君

(1.江蘇開放大學 信息與機電工程學院，江蘇 南京 210017；2.南京信息工程大學 電子與信息工程學院，江蘇 南京 210017；3.河海大學 計算機與信息學院 江蘇 南京 210098)

0 引 言

無線傳感器網絡的一個重要研究課題是研究如何有效管理節點的能量，以盡可能延長網絡的生存時間[1-4]。為了提高傳感器的能量利用效率，常采用聚類機制，但是該協議沒有考慮多跳無線傳感器網絡中的熱區問題。當簇首節點彼此協作以將其數據轉發到基站時，更靠近基站的簇首節點負擔沉重的中繼業務，這些節點會過早消亡[5-9]。為了解決這個問題，文獻[10]提出了一種EEUC(energy-efficient unequal clustering)機制，用于無線傳感器網絡中的周期性數據采集。該機制將無線傳感器網絡中的節點劃分成大小不等的簇，靠近基站的簇的規模大于遠離基站的簇的規模。因此，更靠近基站的簇首可以為簇間數據轉發保留一些能量。該機制還提出了一種用于簇間通信的多跳路由協議，降低轉發路徑上的能量消耗。EEUC機制在無線傳感器網絡中得到廣泛應用，許多學者在該機制的基礎上研究改進機制，以期進一步提高能量利用效率。如文獻[11]對EEUC的簇間多跳路由通信協議進行改進，為各簇首節點選擇一個根節點，僅由根節點與基站進行通信，降低其它簇首節點作為中繼節點的能耗，一定程度上緩解距離基站近的區域的熱區問題。然而，根節點的能耗很大，也帶來了新的能耗不均衡問題。文獻[12]對EEUC的簇首選舉進行改進，在原有簇首選舉的基礎上，又為每一個簇選出一個副簇首，這樣每一個簇的兩個簇首分別執行數據傳輸和數據采、融合任務，降低簇首能耗。但是，EEUC的分簇是不均勻的，有些簇規模很小，這些簇選擇雙簇首進行數據管理有可能增加能耗。文獻[13]對EEUC機制的簇首選舉和簇間通信兩個部分進行改進，在選舉簇首時引入能量、節點鄰居數和距離等參量計算門限函數和競爭半徑，在選擇中繼節點時引入候選中繼節點己當選轉發節點的次數以及簇內成員個數兩個參量計算網絡能量代價開銷，一定程度上均衡了網絡能耗。但是，對于EEUC機制劃分的規模較大的簇，由于簇內成員過多導致簇首節點能耗過大，能耗分布仍不均衡。本文重點針對EEUC機制劃分的規模較大的簇的能耗均衡問題進行深入研究，對大規模簇提出一種節點分組策略，由分組中心節點分擔簇內節點的數據采集和融合任務，降低簇首節點能耗，進一步均衡網絡能耗，延長網絡生存時間。同時，也對EECU機制的簇首節點選舉部分的門限函數進行改進，通過引入能量項和距離項，促使候選簇首節點偏向選擇離基站更近和剩余能量更多的節點，這樣也有助于避免將剩余能量偏低或者擔任簇首節點后能耗偏大的節點作為候選簇首節點，從而避免這些節點過早消亡。

1 相關知識

1.1 網絡模型

假設傳感器網絡由N個傳感器節點組成，傳感器節點均勻地部署在一個區域，以持續監控該區域的環境。傳感器節點和底層網絡模型滿足以下假設：

(1)網絡中存在一個遠離監測區域的基站，傳感器和基站在部署后都是靜止的，基站能量是無限的。

(2)所有節點是均勻的，具有相同的能力。每個節點都被分配一個唯一的標識符(ID)。

(3)節點不需要配備GPS功能單元來獲取精確的位置信息。

(4)節點可以使用功率控制來調整自身發射功率。

(5)鏈路具有對稱性，也即如果給定發射功率，節點可以基于接收到的信號強度來計算發送節點與其近似距離。

(6)節點可以感知自身的剩余能量。

1.2 EEUC機制

EEUC機制采用非均勻分簇和多跳路由組織無線傳感器網絡，均衡網絡內節點的能耗。EEUC是一種分布式競爭機制，簇首節點通過局部競爭選舉，這與LEACH機制不同。節點的競爭半徑隨著距離基站的距離而減小。這樣帶來的結果是，靠近基站的分簇的規模較小，這樣降低簇內數據傳輸的能耗，為簇首節點作為中繼節點轉發其它簇的數據節約能量。EEUC機制的簇內數據傳輸方式與LEACH機制相同，而簇間數據傳輸采用多跳路由協議，簇首根據節點的剩余能量及其到基站的距離從其相鄰簇首中選擇一個最優的中繼節點，實現簇首節點到基站的數據傳輸任務。EEUC機制的最大優勢是可以均衡網絡能耗，顯著改善網絡壽命。因此，EEUC機制以及以該機制為基礎的改進機制在無線傳感器網絡領域得到了廣泛應用。

EEUC機制使用一種簡化的能耗模型，該模型依據發射機和接收機之間的距離d，選擇使用自由空間(d2功率損耗)和多徑衰減(d4功率損耗)兩種信道模型。在距離d上傳輸l位數據包的能耗可以表示為

(1)

對應的接收能耗可以表示為

ERx(l)=lEelec

(2)

其中，Eelec表示數據收發過程中的電路能耗，εfs和εmp分別表示自由空間和多徑衰減兩種信道模型的能耗，d0為距離閾值，可以表示為

(3)

傳感器節點在數據融合時也會消耗能量，記為EDA。EEUC機制還假設傳感器感知的信息是高度相關的，因此簇首節點可以將從其簇成員節點收集的數據融合成單個長度固定的數據包。

2 改進EEUC機制

EEUC采用非均勻分簇思想，距離基站越遠的簇，其簇的規模越大，這樣盡管可以降低通信能耗，但是簇首節點的數據接收及融合任務重，能耗較高。為了均衡大規模簇的節點能耗，本文采用節點分組的思想，由分組的中心節點分擔簇首節點的數據接收和融合任務，從而降低簇首節點的能耗。此外，改進簇首節點選舉的門限函數，通過引入能量項和距離項，促使候選簇首節點偏向選擇離基站更近和剩余能量更多的節點，避免將剩余能量偏低或者擔任簇首節點后能耗偏大的節點作為候選簇首節點而導致這些節點過早消亡。詳細描述如下。

2.1 簇首選舉

對于每一個候選簇首節點，計算節點的競選半徑，然后構建候選簇首節點的鄰居節點表，將候選簇首節點和其鄰居節點的剩余能量進行排序，選擇剩余能量最大的節點作為最終的簇首節點，同時競選半徑內的所有節點不再參與簇首選舉過程。

LEACH協議設計的門限函數為

(4)

在每一輪選舉時，各個節點隨機產生一個0～1之間的隨機數u，如果u

但是，LEACH協議設計的門限函數沒有考慮節點的剩余能量。由于簇首節點需要進行大量的數據處理與傳輸工作，耗費能量很大，因此，剩余能量較小的節點不易作為候選簇首節點。另外，簇首節點擔負著簇內節點與基站的通信任務，簇首節點離基站越近，網絡傳輸能耗越小。基于這一思路，本文對門限函數進行改進，引入能量項和距離項，可以表示為

(5)

(6)

得到候選簇首節點之后，需要為每一個候選簇首節點計算競選半徑，本文仍采用EEUC機制的競選半徑計算方法，候選簇首節點n的競選半徑可以表示為

(7)

其中，Rmax表示競選半徑的最大值，dmax和dmin分別表示網絡中節點到基站的最大和最小距離，c表示一個范圍在0～1之間的參數。在本文中取值為0.5。

這樣，每一個候選簇首節點n在其競選半徑內維護一個鄰居節點列表，列表中的任一節點i滿足以下兩個條件：

(1)節點i為候選簇首節點；

(2)節點i與節點n的距離小于各自競選半徑的最大值。

之后，將候選簇首節點和其鄰居節點列表中的節點剩余能量進行排序，選擇剩余能量最大的節點作為最終的簇首節點，同時競選半徑內的所有節點不再參與簇首選舉過程。

2.2 簇建立

在完成簇首節點的選舉任務之后，喚醒網絡中處于休眠狀態的節點(也即非候選簇首節點)。選出的每個簇首節點在網絡區域廣播邀請成員消息。網絡中的非簇首節點選擇距離最近且接收信號強度最大的簇首節點，并發送加入簇的消息給該簇首節點，直到網絡中的節點都加入簇首節點所在的簇內，完成簇的建立任務。

2.3 簇內節點分組

按照EEUC的建簇思想，建立的簇是不均勻的，越靠近基站的簇的規模越小，越遠離基站的簇的規模越大。這樣做的目標在于均衡網絡能耗，因為距離基站越近的簇首節點作為中繼節點的概率越大，需要執行的數據轉發任務越多，簇首節點的能耗也就越大。因此可以通過降低這些簇的規模來減少簇內數據接收和融合的能耗。而距離基站越遠的簇首節點作為中繼節點的概率越小，其主要能耗在于執行簇內的數據接收和融合，因此可以設計較大規模的簇。這樣，當簇的規模較大時，簇首節點接收大量簇成員節點數據并進行融合的能耗很大。為了均衡大規模簇的節點能耗，本文在規模較大的簇內進行節點分組。簇內的分組中心節點分擔了部分數據接收和融合任務，簇首節點的數據接收和融合任務得以大幅降低，能耗也隨之下降，簇內節點能耗更加均衡。而且，簇首節點只對簇內各分組的中心節點采用TDMA策略分配時隙，由于分組中心節點的數量遠小于原來的簇成員節點數量，而分組中的數據通信在一跳通信范圍內，整體的數據傳輸能耗也得以降低。

如上所述，本文只對規模較大的簇進行節點分組，因此在執行節點分組之前需要判斷簇的規模。由式(7)可知，簇首節點的競選半徑與簇首節點到基站的距離成反比，也即競選半徑越大，說明簇首節點離基站越遠。由EEUC的設計規則知，離基站越遠的簇的規模越大。這樣，競選半徑越大，簇的規模越大。因此，本文依據競選半徑來度量簇的規模。由式(7)可知，競選半徑的范圍為1-cRmax,Rmax，本文取黃金分割點處的半徑值作為閾值TR，即

TR=1-cRmax+0.618Rmax-1-cRmax=
1-0.382cRmax

(8)

在進行簇內節點分組之前，先判斷簇首節點的競選半徑是否大于閾值TR，是則啟動節點分組任務，否則不啟動節點分組任務。節點分組的偽代碼見表1。

表1 節點分組偽代碼

其中，Φ表示空集。

2.4 數據傳輸

數據傳輸包括兩個部分，一是簇內的數據傳輸，由簇首節點收集各傳感器節點采集的數據；二是簇間的數據傳輸，由簇首節點選擇中繼簇首節點，通過多跳通信將數據傳輸給基站。本文的簇間數據傳輸方式與EEUC機制相同，這里不再贅述。而簇內數據傳輸與EEUC機制有所差異。本文將簇內數據傳輸分為兩種模式：一種是沒有包含節點分組的簇的簇內數據傳輸模式，一種是包含節點分組的簇的簇內數據傳輸模式。前一種簇內數據傳輸模式和EEUC機制相同，而后一種簇內數據傳輸模式和EEUC機制是有差異的，具體表現在：EEUC機制中每一個簇成員節點在簇首節點分配的時隙內與簇首節點進行通信，將傳感器采集的數據轉發給簇首節點；而本文機制中每一個分組中心節點在簇首節點分配的時隙內與簇首節點進行通信，將分組內所有傳感器采集的數據融合后轉發給簇首節點。這樣可以均衡大規模簇內節點能耗。

3 仿真實驗

本文采用Matlab 2012版本的軟件平臺進行無線傳感器網絡仿真實驗，參數見表2。

表2 實驗參數

下面將本文聚類機制與傳統EEUC機制以及文獻[13]改進的EEUC機制進行對比分析，從簇首節點能耗、網絡剩余能量和網絡生命周期3個方面評測3種聚類機制的性能，詳細描述如下。

3.1 簇首節點能耗

對于聚類協議而言，無線傳感器網絡中每一個簇的簇首節點的能耗是最大的。因為這些節點要負責簇內其它節點的數據收集、融合和傳輸任務，而且部分簇首節點還要作為中繼節點負責遠離基站的簇首節點的中繼通信。因此，降低簇首節點的能耗對于延長網絡的生命周期具有重要作用。本小節對簇首節點的能耗進行對比分析，隨機抽取十輪的簇首節點總能耗結果，如圖1所示。可見，文獻[13]改進的EEUC機制的簇首節點總能耗總體上略低于EEUC機制，但在某些輪(如圖1中的第3輪、第5輪和第6輪)的簇首節點總能耗略高于EEUC機制。而本文改進的EEUC機制在每一輪的簇首節點總能耗都低于傳統EEUC機制和文獻[13]改進的EEUC機制。總體上，傳統EEUC機制、文獻[13]改進的EEUC機制以及本文改進的EEUC機制的簇首節點總能耗的十輪平均值分別為1.3340、1.3150和1.2320，可見，總體上本文改進的EEUC機制的簇首節點總能耗的十輪平均值相對傳統EEUC機制、文獻[13]改進的EEUC機制分別下降7.6%和6.3%。這主要歸功于本文的節點分組策略，將規模較大的簇的簇首節點的能耗分攤到簇內分組的中心節點身上，從而降低了簇首節點的能耗。

圖1 簇首節點能耗對比

3.2 網絡剩余能量

無線傳感器網絡的生命周期與網絡中節點的剩余能量相關，當網絡中所有節點的剩余能量為0時，無線傳感器網絡達到最長生命周期，也即網絡消亡。本小節對網絡的剩余能量進行對比分析，實驗結果如圖2所示。網絡初始狀態下所有節點的總能量為200 J。節點在數據采集、融合和傳輸過程中都會耗費能量，網絡的剩余能量隨著輪數的增加一直在下降。由圖2可見，傳統EEUC機制在第787輪耗盡網絡能量，文獻[13]改進的EEUC機制在第862輪耗盡網絡能量，而本文改進的EEUC機制在第1033輪耗盡網絡能量，這也說明了改進的EEUC機制的能耗更均衡，其原因主要是本文的節點分組策略均衡了簇內節點的能耗。

圖2 網絡剩余能量對比

3.3 網絡生命周期

網絡生命周期是評價無線傳感器網絡路由協議優劣的重要指標，當無線傳感器網絡中所有節點都消亡之后，網絡也隨之消亡，網絡的生命周期達到最大。因此，可以通過分析網絡中節點的消亡情況來分析網絡的生命周期。圖3展示了3種聚類機制下網絡節點數量隨測試輪數的變化曲線。初始狀態下，網絡中無線傳感器節點的總數為400。當節點的能量消耗完畢之后，節點隨之消亡。由圖3可見，傳統EEUC機制在第694輪開始出現傳感器節點消亡的現象，在第787輪網絡中的傳感器節點全部消亡；文獻[13]改進的EEUC機制在第773輪開始出現傳感器節點消亡的現象，在第862輪網絡中的傳感器節點全部消亡；而本文改進的EEUC機制在第989輪開始出現傳感器節點消亡的現象，在第1033輪網絡中的傳感器節點全部消亡。可見，本文改進的EEUC機制的網絡生命周期最長。而且，本文改進的EEUC機制的傳感器節點消亡曲線最陡峭，這也說明本文改進EEUC機制的節點能耗更均衡。另外，本文改進的EEUC機制的傳感器節點的最早消亡時間要晚于傳統EEUC機制和文獻[13]改進的EEUC機制，這除了是因為本文通過節點分組降低了簇首節點的能耗之外，還由于本文在簇首選舉階段改進了門限函數，通過引入能量項和距離項，促使候選簇首節點偏向選擇離基站更近和剩余能量更多的節點，這樣也有助于避免將剩余能量偏低或者擔任簇首節點后能耗偏大的節點作為候選簇首節點，從而避免這些節點過早消亡。

圖3 網絡生命周期對比

4 結束語

管理節點能量是無線傳感器網絡的重要研究課題之一。EEUC機制的非均勻分簇思想在高效利用傳感器節點能量方面取得了有益成果，是學者們研究的主要方向之一。本文針對EEUC機制所存在的大規模簇的能量不均衡問題，提出了兩種改進策略。一是在候選簇頭選擇的門限函數構建時引入能量項和距離項，保證剩余能量越大、距離基站越近、擔任簇首節點次數少的節點越有機會成為候選簇首節點；二是對大規模簇進行節點分組，由分組的中心節點分擔簇首節點對組內成員節點采集的數據的收集和融合任務，均衡簇內節點能耗。實驗結果表明，本文改進的EEUC機制降低了簇首節點能耗，延緩了網絡能量消耗，延長了網絡生命周期。