高效節能的能量異構傳感器網絡數據聚合協議

摘 要:介紹了一種有效地用于能量異構傳感網絡的數據采集協議EDGA。EDGA在能量最小化的網內通信和均衡能量負荷等性能上有很好的表現。它通過基于權重選擇概率選取的簇頭獲得了更好的處理能量異構環境的能力，并且利用一種簡單但有效的方法解決了簇內的面積覆蓋問題。仿真結果表明，該EDGA方法在能量異構無線傳感網絡的數據采集應用中比LEACH和HEED等方法有明顯的優勢。

關鍵詞:簇協議; 分層數據采集; 異構節點

中圖分類號:TP393文獻標志碼:A

文章編號:1001-3695(2010)06-2267-04

doi:10.3969/j.issn.10013695.2010.06.077

Effective data gathering scheme in heterogeneous energy WSN

LIU Zhen1， MAO Yingchi2， DONG Chen1

(1.School of Computer Science Information Technology， Zhejiang Wanli University， Ningbo Zhejiang 315100， China; 2.College of Computer Information Engineering， Hohai University， Nanjing 210098， China)

Abstract:This paper proposed an effective data gathering scheme for heterogeneous energy WSNs (EDGA). EDGA achieves a good performance in terms of lifetime by minimizing energy consumption for innetwork communications and balancing the energy load. EDGA is based on weighted election probabilities of each node to become a cluster head， which can better handle the heterogeneous energy capacities. Moreover， EDGA adopt a simple but efficient method to solve the area coverage problem in a cluster range， namely intracluster coverage. Finally， the simulation results demonstrate that the proposed EDGA significantly outperforms LEACH， HEED in terms of network lifetime and the amount of data gathered in the heterogeneous energy network.

Key words:clustered scheme; hierarchical data gathering; heterogeneous node

無線傳感網絡由微型、低成本、低功耗的微傳感器組成，這些傳感器可以通過通信來協同工作進行監測和數據處理。它們被協同起來，從目標區域采集信息進行檢測同時將信息傳送至基站[1]。層次化的機制對數據延遲進行優化可以增加網絡的可升級性，同時數據通過層次化的方式進行整合，可以降低數據冗余度和減少通信負荷，從而優化網絡壽命[2]。換句話說，在無線傳感網絡中植入異構節點是增加網絡壽命和可行性的有效方式。本文主要介紹一種名為EDGA的有效用于能量異構環境的層次化數據采集協議。該協議包括兩個周期，即簇頭信息周期和遍歷樹構建周期。在簇頭信息周期中，EDGA利用權重選擇概率來選擇簇頭，即通過節點的初始能量權重來進行判斷。這一方法比僅利用節點的殘余能量來選出簇頭更適用于能量異構環境。在簇頭信息周期之后，EDGA開始對簇頭集合構建遍歷樹，只有根節點可以通過單跳通信與下層節點進行通信。同時，EDGA引入了一個內部簇覆蓋機制，使得網絡壽命隨著分布節點樹的增加而線性延長。

1 相關工作

Heinzelman等人[3]給出了一種名為LEACH的簇選擇算法，為了節約功耗，LEACH僅選取所有傳感器節點的小部分p來當做簇頭，p是預先設定的參數值，剩下的傳感器節點根據連接到各簇頭的信號強弱來選擇合適的簇加入。為了分享能量負荷，將其工作劃分成環的形式來保證簇頭可以在每個環中循環。在文獻[4]中，為了處理能量異構環境，能量高的節點被認做簇頭的可能性更大，將每個節點相對于整個網絡所有節點的能量進行比較，從而計算其成為簇頭的可能性。因此，每個節點只有在全面了解其本地特征后才可能成為簇頭，大大影響了其可升級性。Lee等人在文獻[5]中推薦了一種新的簇算法:CODA來減輕因為各節點到信息匯入點的距離不同帶來的能量損耗失衡現象。CODA將整個網絡根據各節點到基站的距離和分布策略來劃分成數個組，每組均有各自的簇成員和節點成員，并將離基站遠的組分配更多的簇。這種方法相對于全網絡用同一概率選擇簇的方式來說，顯示出更好的性能、網絡壽命和功耗。但是，由于它依賴于全局的節點信息，使得系統同樣不易升級。Younis等人[6]提出了一種HEED簇化算法，周期性的根據節點殘余能量和節點地位來選取簇頭。它在整個網絡上得到一個均勻分布的簇頭集。Lee等人[7]考慮通過將節點分成類型1和0來進行事件驅動檢測異構網絡，類型1節點能量比類型0的高，其研究的關鍵點在于將電源節點構建進了網絡，以及其對網絡壽命的分析。近年來，介紹了一種用fuzz邏輯選出簇頭的方法來彌補LEACH的缺陷，認為fuzz邏輯的使用能有效延長異構網絡的壽命，但其異構網絡還是不同于能量異構環境。

2 系統模型

2.1 網絡模型

假設傳感器節點N隨機均勻分布在場地A中，其傳感網絡具有如下特征:

a)該網絡是一個靜態分布網絡，傳感器節點N均勻分布在一個二維空間中，同時這些節點是靜止不動的。

b)所有節點在秒級的精度上基本同步。

c)僅存在一個基站，其位置在區域A外且固定。

d)節點位置未知，如沒安裝GPS天線。

e)傳感器的無線傳輸功率可連續可調，可以達到不同的傳輸范圍。

f)所有節點具有不同的初始能量，一些節點具有比普通(normal)節點更高的能量，設m為總節點N的一部分，m0為具有normal節點β倍能量的節點比率，稱為super節點，數量為N×m×m0。剩余的N×m×(1-m0)節點具有normal節點能量的α倍，稱為advanced節點，其余的N×(1-m)為普通節點。

2.2 無線射頻模型

筆者用與文獻[4]中相同的無線傳播模型來進行研究，一個L位的信號傳播距離d后的信噪比如式(1)所示，當接收該信號時，射頻能量消散比如式(2):

ETx(L，d)=L×Eelec+L×εfs×d2 if d≤d0L×Eelec+L×εmp×d4if d>d0(1)

ERx=L×Eelec(2)

其中:Eelec為每位信號由發射電路到接收電路的能量消散比，εfs和εmp由放大器模型決定。

3 EDGA協議設計

接下來，將介紹異構EDGA協議，該協議用于增加網絡壽命和各異構節點的網絡穩定性。由于簇頭比簇成員在從成員節點處接收傳感器數據、進行信號處理、發射數據至其他節點和基站等任務中需要更多的功耗，應該讓各節點輪流充當簇頭的角色。EDGA的工作過程類似一個在選擇簇頭時作了進一步優化的循環LEACH流程。

3.1 簇頭選擇

EDGA對于簇頭的選擇過程類似于LEACH，出于對能量異構節點的考慮，EDGA基于節點的選擇概率來選擇簇頭，該概率依據相對于其節點的初始能量來分配權重。接下來，討論如何計算最佳概率的簇頭，及其選擇過程。

為了簡化，假定基站置于監測場地的正中央，其與所有節點的距離小于d0，因此可以給出簇頭節點的能耗為

Ech=(N/k-1)×L×Eelec+N/k×L×EDA+L×

Eelec+L×εfs×dBS2(3)

其中:k為簇的數目;L為傳輸的信號位數;EDA為傳遞一位信號給下級節點或基站時的損耗;dBS為簇頭與節點間的平均距離。非簇頭節點的能量消耗為:

Enon-ch=L×Eelec+L×εfs×d2CH(4)

其中:dCH為簇成員與簇頭間的平均距離。

假設所有節點均服從均勻分布，則可以表示為

d2CH=∫x=max0∫y=max0(x2+y2)×ρ(x，y)dxdy=M22πkd(5)

其中:ρ(x，y)為節點分布密度，M2為檢測場地面積。

網絡消耗的總功耗為

Etotal=L×(2×N×Eelec+N×EDA+(k×d2BS+N×d2CH))(6)

通過將式(6)對k微分后值為0，可以得到簇頭對于信息匯入點的最優數目為[3]

dBS2=∫A(x2+y2)×1A=0.765×M2(7)

如果重要節點相對于信息匯入點的距離大于d0，可以得到簇頭的最優數目為[9]

kopt=N2πεfsεmpMdBS2(8)

由式(7)(8)可以得出，EDGA協議中，節點成為簇頭的最優概率popt為

popt=koptN=10.7652πNεfsεmp(9)

節點成為簇頭的最優概率popt非常重要，在文獻[10]中，證明了如果簇的構建不是最優，即使簇的數量略大于甚至小于最優化的簇數目，總的功耗也會呈指數形式增長。

接下來討論如何計算權重概率。由于所有節點基于網絡模型隨機分布，新的異構結構不會影響網絡的空間密度，LEACH中的概率pleach亦不變。

假設E0為normal節點的初始能量，則super節點的能量為E0×(1+β)，advanced節點為E0×(1+α)，則新的異構網絡總能量為

Einit=N×(1-m)×E0+N×m×(1-m0)×(1+α)+N×m×m0×

E0×(1+β)=N×E0×(1+m×(α+m0×β))(10)

從式(10)可以看出系統總能量隨因子(1+m×(α+m0×β))增加而增加。比LEACH更優的一點是增加了傳感網正比于能量增加的時段。為了優化系統的穩定范圍，新的epoch必須與(1/popt)(1+m×(α+m0×β))相等，因為系統能量增大至m×(α+m0×β)倍。

如果對super、advanced和normal節點設置相同的閾值，則每個時段的(1/popt)(1+m×(α+m0×β))次循環中normal節點成為簇頭;每個時段的(1+β) (1/ popt)(1+m×(α+m0×β))次循環中super節點成為簇頭;每個時段的(1+α) (1/ popt )(1+m×(α+m0×β))次循環中advanced節點成為簇頭。因而無法保證每次循環中每時段的簇頭數為popt×N。因此，將簇頭數限制為popt ×N是不對的。推薦的方法是設定一個權重給最優概率popt，該權重為每個節點的初始能量除以normal節點的初始能量。設pn、pa和ps分別為normal、advanced和super節點的權重。

事實上，有(1+m×(α+m0×β)×N個節點能量等于normal節點的初始能量。為了保持每次循環的功耗最小，每次循環每個時段的簇頭平均數必須限制在popt×N內。在異構環境中每次循環每個時段的簇頭平均值為(1+m×(α+m0×β)×N×pn，normal、advanced和super節點的權重概率:

pn=popt1+m×(α+m0×β)pa=popt1+m×(α+m0×β)×(1+α)ps=popt1+m×(α+m0×β)(1+β)(11)

基于式(8)(9)(11)，可以通過權重概率解得LEACH中用來作為EDGA中選擇簇頭的閾值pLEACH，將normal、super和advanced節點閾值分別定義為T(sn)，T(ss)和T(sa):

T(sn)=pn1-pn×(r mod 1/pn)if s∈G′0ifsG′

T(sa)=pa1-pa×(r mod 1/pa)if s∈G″

0ifsG″

T(ss)=ps1-ps×(r mod 1/ps)if s∈G

0ifsG(12)

其中:r為當前循環，G′、G″和G分別為最后1/pn，1/pa和1/ps次循環of the epoch中未選做簇頭的normal、advanced和super節點。T(sn)作為N(1-m)個normal節點的閾值保證了每個normal節點在每(1/popt)(1+m×(α+m0×β))次循環每時段中會成為一次簇頭，其平均數量為N×(1-m)×pn。同樣，可以計算出advanced和super節點的閾值。

在EDGA協議中，當前循環中被選為簇頭的節點需向鄰近節點廣播簇頭信息，其他非簇頭節點在收到簇頭信息后根據信號強弱選擇要加入的簇。同時，向加入的簇頭發送加入信息。

3.2 簇內成員節點的選擇性激活

覆蓋率是近年來無線網研究中比較重要的一個話題。一般情況下，覆蓋率指的是面積覆蓋率，盡管假設所有傳感器都在工作，也很難保證目標區域的隨機覆蓋率為100%。小的監測漏洞在大部分的應用環境中影響很小并可以接受。一些應用中，常要求部分節點保持激活，覆蓋機制用來保證制定節點保持激活同時滿足覆蓋率預期。筆者將覆蓋機制應用到簇內，稱做簇內覆蓋，基于之前的工作[11]，最小簇頭數的隨機選擇計算如下:

Pcover=1-(1-area(N(x，y))/area(M))K(13)

設Pcover為某一應用中的覆蓋率預期，k為簇頭最小值，area(N(x，y))表示簇頭q(x，y)的信號采集范圍，area(M)為簇范圍，K為:

K=「ln(1-Pcover)/ln(1-R2s/Rcluster2)(14)

其中:Rs為節點采集半徑，Rcluster為簇半徑。

利用簇內覆蓋機制可以通過在每次循環中關閉冗余節點來延長壽命降低功耗。同樣，在簇頭廣播TDMA包時可以減少TDMA消耗，在節點密度很高，簇成員數量較大時，有大量的能量消耗在TDMA過程中。另外，簇內覆蓋機制并不消耗額外的能量。

3.3 構建遍歷樹

在網絡簇化后，簇內部組織方式由網絡應用來決定，例如，簇頭可以通過多跳方式與其他簇頭通信來抓取信息，或直接與基站通信。在多跳通信中，簇頭間的傳輸范圍可能發生變換，以保證一定的連接度以及處理沖突的能力。簇內通信時，連接度由簇內傳輸范圍R，簇間傳輸范圍r和節點密度決定。Kim等人[8]指出，如果R≥6r，簇頭組成的圖將被連接起來。而筆者認為，理論的連接值不一定適用于實際應用。考慮一個典型的傳感網設置，如文獻[6]所述(網絡大小從(0，0)~(100，100)，簇范圍為30 m，信息匯入點(sink)位于(50，175))。從上述連接方程得出簇內的通信輻射范圍為180 m，意味著簇頭基本上可以直接與基站進行通信。這里，將簇內傳輸范圍設為R=2.5r。

簇化之后，簇頭將自身權重與鄰近簇頭權重相對比，如果值小于其他簇頭，該簇將選擇最大權重簇頭作為其父節點，并發送CHILD MSG信號通知其父節點。一段時間后，一個遍歷樹將被構建出來，其根節點具有最大的權重。一旦遍歷樹建立成功，簇頭將廣播TDMA數據流來通知其成員節點開始數據采集過程。

本文定義節點i的權重為Wi=Ecurren×D(RSSi)/D(RSSmax)。其中:RSSi表示子節點i接收基站信號的強度;RSSmax為由基站位置決定的常量;函數D用來估計節點i到基站的距離。當布置好傳感器后，基站向所有傳感器廣播測試信號，傳感器根據接收信號強度來獲得RSS，RSS將一直保持不變直到基站或傳感器位置發生改變。很明顯，離基站近的節點擁有更多的能量，從而權重更大，成為根節點。

3.4 工作周期

數據采集在簇頭向保持激活的成員節點發送TDMA廣播后開始，激活的成員節點在TDMA過程中向各自簇頭發送采集到的數據，簇頭接收完所有數據后便將數據整合，以便降低信號中的噪聲。遍歷樹中的底層(即沒有子節點)節點則直接將數據發送給其父節點;其他節點則等待其子節點數據，然后將該數據整合后發往其父節點;最后由根節點將所有數據整合并發往基站;網絡隨后即開始下一次循環過程。為了減少簇化次數，每次循環都爭取進行更多的數據采集次數(定義所有節點采集的數據發往基站為一次)，在L次數據采集后，重新簇化開始新的循環。其中L為預先設定的參數值。

4 仿真結果

在仿真實驗中，筆者對比LEACH、HEED和EDGA在相同的異構環境下的網絡壽命、每次循環中的激活節點數和網絡消耗等指標。其中EDGA協議分為EDGA1(不含簇內覆蓋機制)和EDGA2(含簇內覆蓋機制，QoS設為95%)兩種。評估結果如表1所列(200次獨立實驗的平均值，每次節點分布為隨機產生的平均分布拓撲，射頻硬件模型均與文獻[4]中一致)。

表1 模擬中使用的參數列表

parametersvalue

network field(0，0)~(100，100)

node numbers100~500

cluster radius R30 m

sensing radius Rs10 m

sink position(50，50)

initial energy2 J

data packet size525 Byte

broadcast packet size25 Byte

Ethreshold0.01 J

Eelec50 nJ/bit

εfs10 nJ/bit/(m*m)

εmp0.001 3 pJ/bit/ m4

EDA5 nJ/bit/signal

threshold distance d075 m

data cycle L per round5

圖1和2描述的是節點數為200時不同異構參數設置下的激活節點和壽命的關系對比。圖1中的初始能量大于圖2，可以看出，在相同循環次數下，LEACH中關閉的節點比EDGA中的多，其normal節點很快關閉，使得監測區域很快閑置。另一方面，advanced和super節點關閉較慢，advanced和super節點越多，節點關閉則越慢，當節點關閉數量達到一定程度時，簇頭在每次循環per epoch中的平均值小于1，這就意味著在相當一部分循環中沒有簇頭，節點無法上報其數據。值得關注的是EDGA2中節點關閉很慢，這是由于簇內覆蓋機制選擇了一些保持激活的節點。

圖3說明的是展開節點數與網絡壽命間的關系。在LEACH、HEED和EDGA1中節點增加時，延長壽命失敗，而EDGA2可以保持壽命的延長隨著節點數線性增長。這是由于LEACH、HEED和EDGA1沒有用到簇內覆蓋機制，每個節點需向其父節點發送采集到的所有環境信息，哪怕是冗余信息。相反，EDGA2通過簇內覆蓋機制，僅一定數目的激活節點提供滿足預期覆蓋率的QoS，其冗余保持休眠狀態來節約能量并延長網絡壽命。圖4表明，各種協議的網絡消耗，包括廣播TDMA和簇化的能量消耗，對于EDGA2還包括構建遍歷樹的能量消耗。

在簇信息周期中，HEED由于簇頭的選擇需通過數次廣播產生而消耗更多的能量，而且，隨著節點密度的提高，其TDMA數據長度也隨之提高，從而在收發TDMA時會消耗更多的能量。另外，雖然EDGA2消耗一定能量用于建立遍歷樹，但由于只有簇內一定數目的激活節點收發TDMA數據包，消耗的能量較LEACH少，進一步來講，當節點密度提高時，其簇內激活節點數并不增多。

5 結束語

本文給出了一種有效應用于能量異構無線傳感網絡的帶簇內覆蓋機制的數據采集協議EDGA，它利用選擇概率簇化傳感器節點，更好地處理了能量異構環境，并通過構建遍歷樹實現了能耗的節約;同時，EDGA引入的簇內覆蓋機制減少了簇內激活節點數目。仿真結果表明，該EDGA方法較LEACH在能量異構網絡應用中的網絡壽命和數據采集量上有明顯的優勢。

參考文獻:

[1]TUBASISHAT M， MADRIA S. Sensor networks:an overview[J]. IEEE Potentials， 2003，22(2):20-23.

[2]POTTIE G J， KAISER W J. Wirless integrated network sensors[J]. ACM Communications， 2000，43(5):51-58.

[3]HEINZELMAN W R， CHANDRAKASAN A， BALAKRISHNAN H. Energyefficient communication protocol for wireless microsensor networks[C]//Proc of the 33rd Hawaii International Conference on System Sciences. Washington DC:IEEE Computer Society， 2000:55-60.

[4]HEINZELMAN W R， CHANDRAKASAN A， BALAKEISHNAN H. An applicationspecific protocol architecture for wireless microsensor networks[J]. IEEE Trans on Wireless Communications， 2002，1(4):660-670.

[5]LEE S H， YOO J J， CHUAN T C. Distancebased energy efficient clustering for wireless sensor networks[C]//Proc of the 29th IEEE International Conference on Local Computer Networks. Washington DC:IEEE Computer Society， 2004:567-568.

[6]YOUNIS O， FAHMY S. Distributed clustering in Ad hoc sensor networks: a hybrid， energyefficient approach[C]//Proc of IEEE INFOCOM. 2004:169-175.

[7]LEE H Y， SEAH K G， SUN P. Energy implications of clustering in heterogeneous wireless sensor networks:an analytical view[C]//Proc of the 17th IEEE Intertional Symp on Personal， Indoor and Mobile Radio Communications. 2006:77-83.

[8]KIM J M， PARK S H， HAN Y J， et al. CHEF:cluster head election mechansim using fuzzy logic in wirless sensor networks[J]. ICACT， 2008， 4:654-659.

[9]INTANAGONWIWAT C， GOVINDAN R， ESTRIN D. Directed diffusion: a scalable and roubust communication paradigm for sensor networks[C]//Porc of ACM MobiCom’00. Boston:ACM Press， 2000:56-67.

[10]WAN C Y，CAMPBELL A T， KRISHNAMURTHY L. PSFQ: a reliable transport protocol for wireless sensor networks[C]//Proc of the 1st ACM International workshop on Wireless Sensor Network and Applications.New York:ACM Press， 2002:1-11.

[11]MAO Y C， JUN L， CHEN D. Energy aware partial coverage protocol in wireless sensor networks[C]//Proc of the 3rd International Conference on Wireless Communications， Networking and Mobile Computing. [S.l.]:IEEE Press， 2007:2535-2538.