結(jié)合節(jié)點分組和門限優(yōu)化的改進EEUC機制

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

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

0 引 言

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

1 相關(guān)知識

1.1 網(wǎng)絡模型

假設傳感器網(wǎng)絡由N個傳感器節(jié)點組成，傳感器節(jié)點均勻地部署在一個區(qū)域，以持續(xù)監(jiān)控該區(qū)域的環(huán)境。傳感器節(jié)點和底層網(wǎng)絡模型滿足以下假設：

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

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

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

(4)節(jié)點可以使用功率控制來調(diào)整自身發(fā)射功率。

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

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

1.2 EEUC機制

EEUC機制采用非均勻分簇和多跳路由組織無線傳感器網(wǎng)絡，均衡網(wǎng)絡內(nèi)節(jié)點的能耗。EEUC是一種分布式競爭機制，簇首節(jié)點通過局部競爭選舉，這與LEACH機制不同。節(jié)點的競爭半徑隨著距離基站的距離而減小。這樣帶來的結(jié)果是，靠近基站的分簇的規(guī)模較小，這樣降低簇內(nèi)數(shù)據(jù)傳輸?shù)哪芎模瑸榇厥坠?jié)點作為中繼節(jié)點轉(zhuǎn)發(fā)其它簇的數(shù)據(jù)節(jié)約能量。EEUC機制的簇內(nèi)數(shù)據(jù)傳輸方式與LEACH機制相同，而簇間數(shù)據(jù)傳輸采用多跳路由協(xié)議，簇首根據(jù)節(jié)點的剩余能量及其到基站的距離從其相鄰簇首中選擇一個最優(yōu)的中繼節(jié)點，實現(xiàn)簇首節(jié)點到基站的數(shù)據(jù)傳輸任務。EEUC機制的最大優(yōu)勢是可以均衡網(wǎng)絡能耗，顯著改善網(wǎng)絡壽命。因此，EEUC機制以及以該機制為基礎(chǔ)的改進機制在無線傳感器網(wǎng)絡領(lǐng)域得到了廣泛應用。

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

(1)

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

ERx(l)=lEelec

(2)

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

(3)

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

2 改進EEUC機制

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

2.1 簇首選舉

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

LEACH協(xié)議設計的門限函數(shù)為

(4)

在每一輪選舉時，各個節(jié)點隨機產(chǎn)生一個0～1之間的隨機數(shù)u，如果u

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

(5)

(6)

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

(7)

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

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

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

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

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

2.2 簇建立

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

2.3 簇內(nèi)節(jié)點分組

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

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

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

(8)

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

表1 節(jié)點分組偽代碼

其中，Φ表示空集。

2.4 數(shù)據(jù)傳輸

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

3 仿真實驗

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

表2 實驗參數(shù)

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

3.1 簇首節(jié)點能耗

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

圖1 簇首節(jié)點能耗對比

3.2 網(wǎng)絡剩余能量

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

圖2 網(wǎng)絡剩余能量對比

3.3 網(wǎng)絡生命周期

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

圖3 網(wǎng)絡生命周期對比

4 結(jié)束語

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