能量均衡的無線傳感器網(wǎng)絡多跳非均勻分簇算法

馬威風，陳桂芬

(長春理工大學 電子信息工程學院，吉林 長春 130022)

0　引言

無線傳感器網(wǎng)絡(Wireless Sensor Networks, WSNs)是由部署在監(jiān)測區(qū)域內大量廉價的微型傳感器節(jié)點組成，通過無線通信方式形成的一個多跳的自組織的網(wǎng)絡系統(tǒng)[1]。隨著傳感器、嵌入式計算、通信和計算機網(wǎng)絡等技術的日趨成熟，無線自組織網(wǎng)絡的各種應用逐漸成為可能，成為21世紀信息產(chǎn)業(yè)的重要支柱[2]。WSNs節(jié)點作為微小器件只能配備有限電源，而且多數(shù)部署在危險地帶或人難以到達的環(huán)境中，后期維護難以實現(xiàn)，使節(jié)點壽命很大程度上依賴電池壽命，因此，如何減少節(jié)點的能量消耗對于傳感器網(wǎng)絡而言至關重要[3]，同時也是設計協(xié)議時面臨的重要問題之一。

WSNs中節(jié)點布設密度大，節(jié)點感知到的數(shù)據(jù)存在大量的冗余信息[4]，而通信耗能為總能耗的主要部分。因此，必須嚴格控制數(shù)據(jù)包傳輸量來減少不必要的開銷。以LEACH[5]為典型代表的分簇算法將節(jié)點分為簇頭和簇內節(jié)點，簇內節(jié)點負責采集數(shù)據(jù)，而簇頭負責管理簇內節(jié)點，并進行簇內節(jié)點信息的采集、融合及轉發(fā)[6]。LEACH算法在一定程度上實現(xiàn)了能耗均衡，但存在簇頭分布位置的隨機性、選取簇頭未考慮節(jié)點剩余能量以及與基站直接進行數(shù)據(jù)傳輸導致能耗過大的問題[7]。

EEUC[8]算法采用非均勻分簇和簇間多跳的方式。網(wǎng)絡被劃分為大小不等的簇，遠離基站的簇內節(jié)點較多，避免過快消耗能量，而且簇間多跳路由方式可以進一步均衡簇頭能量消耗[9]，較好地解決了“熱區(qū)”問題[10]。

DEEUC[11]算法在EEUC基礎上優(yōu)化了簇頭選舉和路由選擇，算法中候選簇頭由上一輪簇頭根據(jù)簇內剩余能量選出，再通過能量因素選出最終簇頭。下一跳路由簇頭選擇正向單位能量消耗最小的鄰簇首，有效地提高簇頭間傳輸數(shù)據(jù)的效率。

本文基于非均勻分簇算法提出一種能量均衡多跳非均勻分簇算法(Energy Balance Multi-hops Uneven Clustering, EBMUC)，算法首先比較節(jié)點剩余能量與鄰節(jié)點平均剩余能量選出候選簇頭，再考慮距離、能量和鄰節(jié)點數(shù)因素選出最終簇頭；簇構造在節(jié)點入簇公式[12]中加入簇頭剩余能量；簇間選擇中繼節(jié)點協(xié)助傳輸數(shù)據(jù)，數(shù)據(jù)通過中繼節(jié)點和鄰簇頭多跳傳輸?shù)交?BS)，進一步延長網(wǎng)絡生存時間。

1　相關理論

1.1　網(wǎng)絡模型

正方形監(jiān)測區(qū)域內隨機分布N個周期性收集數(shù)據(jù)的WSNs節(jié)點，假設：(1)BS位于監(jiān)測區(qū)域邊緣，BS和節(jié)點部署后位置不再變動；(2)節(jié)點具有全網(wǎng)絡唯一的標識ID號，節(jié)點同構且具備一定的存儲能力，可以由信號強度估算距離；(3)BS能夠與全網(wǎng)絡的節(jié)點通信，通信方式為半雙工；(4)無線信道對稱，數(shù)據(jù)傳輸過程中融合數(shù)據(jù)減少數(shù)據(jù)量，融合單位數(shù)據(jù)耗能相同；(5)忽略外界影響，節(jié)點周期性采集數(shù)據(jù)并始終有數(shù)據(jù)傳輸?shù)紹S。

1.2　能量模型

本文采用文獻[13]中的無線通信能耗模型，kbit的數(shù)據(jù)包發(fā)送到距離d的一個節(jié)點，能耗主要由無線信號收發(fā)和功率放大產(chǎn)生，功放器件的耗能與環(huán)境和距離密切相關，可分為自由空間模型和多徑衰落模型。發(fā)送模塊能耗計算如式(1)所示：

(1)

ERx(k)=kEelec

(2)

1.3　最優(yōu)簇數(shù)目和最優(yōu)簇通信半徑

采用文獻[13]中的方法計算最優(yōu)簇數(shù)目(mopt)，假定在一個M×M的區(qū)域內均勻部署N個節(jié)點，產(chǎn)生m個簇，m個簇的總能耗如式(3)所示：

(3)

對式(3)中m求導并令式等于0, 求出mopt，由mopt計算均勻分簇情況下最優(yōu)簇通信半徑ropt、最優(yōu)跳數(shù)τopt，如式(4)所示，式中為向上取整。

(4)

2　EBMUC協(xié)議算法設計

(1)簇頭選擇：BS首先廣播初始化消息(包括mopt、ropt和d0)。節(jié)點收到消息后由信號強度估算到BS的距離dtoBS(i)，然后節(jié)點以ropt為半徑向周圍鄰節(jié)點廣播消息(包括節(jié)點剩余能量和到BS距離)，節(jié)點收到鄰節(jié)點消息后建立鄰節(jié)點信息表并統(tǒng)計鄰節(jié)點個數(shù)，計算其鄰節(jié)點平均剩余能量。若節(jié)點剩余能量大于鄰節(jié)點平均剩余能量，則當選候選簇頭并廣播消息，反之節(jié)點進入休眠。候選簇頭收到鄰候選簇頭的消息后建立鄰候選簇頭信息表，然后計算并廣播適應值(如式(5)所示)，通過交換適應值選擇值最大的候選簇頭為最終簇頭并廣播當選消息，休眠中的節(jié)點收到最終簇頭的消息后喚醒。

f(i)=w1N+w2E+w3D

(5)

(2)簇結構形成：①簇內結構。節(jié)點收到最終簇頭當選消息后建立簇頭信息表并估算到各簇頭距離，對每個簇頭的飽和度進行判斷(即表達式P2)，由式(6)選擇值大于0的簇頭發(fā)送加入消息(包括剩余能量和基站距離)。

Add(i, CHj)=αP1+(1-α)P2

(6)

簇頭記錄節(jié)點發(fā)送的加入消息(若收到競選簇頭失敗的候選簇頭的消息則將其標記為副簇頭)，根據(jù)成員節(jié)點數(shù)分配發(fā)送數(shù)據(jù)幀間隔。成員數(shù)較少的簇對應幀時間間隔較大，反之，幀時間間隔較小，以此來保證單位時間內不同簇內數(shù)目不同的節(jié)點傳輸?shù)臄?shù)據(jù)次數(shù)相同。最后，簇頭采用TDMA方式向簇內成員廣播工作時隙。

②簇間結構。簇頭收到周圍其他最終簇頭當選消息后建立鄰簇頭信息表，計算并廣播簇間數(shù)據(jù)轉發(fā)代價值(如式(7)所示)，通過比較代價值來決定下一跳簇頭。

(7)

下一跳簇頭確定后，若簇頭間距離大于d0，則在傳輸數(shù)據(jù)的簇內選擇靠近下一跳簇頭的中繼節(jié)點輔助傳輸數(shù)據(jù)，反之則簇頭間傳輸數(shù)據(jù)。中繼節(jié)點由節(jié)點剩余能量與到兩簇頭間的距離兩因素確定(如式(8)所示)，其中Erel、drel to CHj分別為中繼節(jié)點剩余能量和到下一跳簇頭距離。

(8)

(3)數(shù)據(jù)傳輸：簇成員節(jié)點在分配的時隙段向距離自己最近的副簇頭傳輸數(shù)據(jù)(若無副簇頭，則通過鄰節(jié)點，若無鄰節(jié)點則增大功率與簇頭之間通信，將數(shù)據(jù)多跳傳輸至簇頭)，副簇頭收集并融合數(shù)據(jù)后向簇頭轉發(fā)，每次多跳傳輸過程中都有數(shù)據(jù)融合，數(shù)據(jù)傳輸后簇成員節(jié)點進入休眠狀態(tài)；對于簇間數(shù)據(jù)傳輸則根據(jù)簇頭間的距離情況選擇中繼節(jié)點輔助數(shù)據(jù)傳輸。同樣，到BS距離小于d0的節(jié)點以單跳形式向BS傳輸數(shù)據(jù)，大于則多跳傳輸?shù)紹S。此外，靠近BS的簇頭或普通節(jié)點并不是有數(shù)據(jù)就立即向BS傳輸，而是等待數(shù)據(jù)量匯聚到一定程度后再向BS傳輸，這樣階段地一次性向BS傳送數(shù)據(jù)，大大減少了數(shù)據(jù)包的發(fā)送次數(shù)，從而使得距離BS較遠的節(jié)點可以向基站附近匯聚更多信息量的數(shù)據(jù)。網(wǎng)絡整體示意圖如圖1所示。

圖1　EBMUC協(xié)議節(jié)點示意圖

3　仿真實驗與分析

3.1　仿真實驗

在1 000 m×1 000 m區(qū)域中仿真比較了LEACH、EEUC、DEEUC和EBMUC，節(jié)點數(shù)為1 000個，初始能量為0.5 J，BS坐標為(1 000,500)。成簇權值α=0.6，w1、w2與w3分別取0.3、0.4和0.3，距離常數(shù)d0為87 m。其他參數(shù)見表1。

表1　仿真相關參數(shù)

3.2　仿真實驗結果分析

通過仿真網(wǎng)絡的生存時間、BS接收數(shù)據(jù)量和網(wǎng)絡剩余能量來研究本文算法的性能。

3.2.1網(wǎng)絡生存時間

網(wǎng)絡生存時間是衡量網(wǎng)絡性能的重要指標之一[14]，表2統(tǒng)計了圖2中四種算法的第一個死亡節(jié)點(FND)和死亡一半節(jié)點(HND)的輪數(shù),若是以HND作為網(wǎng)絡生存時間評判標準，四種算法網(wǎng)絡生存時間分別為215、273、297和362，與LEACH比較，EEUC采用了非均勻分簇的方式，很好地解決了“熱區(qū)”問題，延遲了FND的出現(xiàn)；DEEUC在EEUC的基礎上優(yōu)化了簇頭選取以及最小正向單位路由選擇，能耗比EEUC算法得到進一步降低；而本文的EBMUC算法在由候選簇頭選取簇頭時，考慮了能量、距離以及鄰節(jié)點數(shù)等因素，比DEEUC由候選簇頭通過能量因素競爭選取出的簇頭更為合理，出現(xiàn)FND輪數(shù)也更遲。EEUC、DEEUC以及本文算法會在某個時間段出現(xiàn)節(jié)點迅速死亡，產(chǎn)生這種現(xiàn)象的原因是由于這三種算法覆蓋面積遠大于LEACH，網(wǎng)絡中節(jié)點能量得到均衡消耗，會在某一刻存活的節(jié)點少于LEACH中的節(jié)點數(shù)。EBMUC由于中繼節(jié)點的加入，數(shù)據(jù)多跳傳輸?shù)紹S，更好地均衡了簇間能量消耗，所以后期節(jié)點死亡速度略快于DEEUC。

圖2　存活節(jié)點數(shù)對比圖

算法名稱FND輪數(shù)HND輪數(shù)LEACH34215EEUC201273DEEUC236297EBMUC298362

3.2.2基站BS接收數(shù)據(jù)量

圖3為四種算法BS接收數(shù)據(jù)量對比圖，在FND之前，EBMUC中基站收到的數(shù)據(jù)包總量約是LEACH算法的1.5倍，約是EEUC與DEEUC的1.3、1.1倍。這是因為EBMUC改進的簇頭選擇與簇間通信方式，延長了網(wǎng)絡的生命周期，使數(shù)據(jù)量有所增加，在EBMUC的HND之前，LEACH、EEUC和DEEUC中的大部分節(jié)點已經(jīng)死亡，網(wǎng)絡存在覆蓋率低的區(qū)域，節(jié)點難以將數(shù)據(jù)傳輸?shù)紹S。

圖3　基站BS接收數(shù)據(jù)量對比圖

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

圖4比較了四種算法的網(wǎng)絡剩余能量隨運行輪數(shù)的變化情況。EEUC、DEEUC和EBMUC的多跳非均勻策略比單跳均勻的LEACH有明顯的節(jié)能優(yōu)勢。EBMUC網(wǎng)絡剩余能量在700輪之前大于其他三種算法，體現(xiàn)了本文算法的能量利用高效性。之后，由于EBMUC覆蓋面積較大，消耗了一定的網(wǎng)絡剩余能量，因此小于LEACH算法，同樣地，EEUC和DEEUC也出現(xiàn)了這種情況。EEUC、DEEUC和EBMUC相比，DEEUC中簇頭指定能量最高的節(jié)點為下輪的簇頭，均衡了節(jié)點間能耗同時也避免多個節(jié)點成為候選簇頭參與最終簇頭競爭，節(jié)省了網(wǎng)絡能量。而EBMUC是先選擇候選簇頭，再由候選簇頭綜合考慮能量、距離以及鄰節(jié)點數(shù)來競爭最終簇頭，得到的簇頭更為合理，同時在節(jié)點入簇時考慮了簇頭能量與簇規(guī)模，有效地減輕了簇頭負擔，降低了網(wǎng)絡能耗。

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

4　結論

本文在研究現(xiàn)有的非均勻分簇算法基礎上，設計了一種能量均衡的多跳非均勻分簇算法，算法考慮了節(jié)點的距離、能量以及鄰居數(shù)等因素來選取最終的簇頭節(jié)點。節(jié)點入簇階段考慮了簇頭的能量與距離，同時也考慮了簇頭的鄰節(jié)點數(shù)，避免形成的簇結構規(guī)模過大。為了防止簇頭間出現(xiàn)遠距離傳輸數(shù)據(jù)的情況，采取選擇待傳輸數(shù)據(jù)簇內最遠處的節(jié)點作為中繼節(jié)點來輔助數(shù)據(jù)傳輸，縮短數(shù)據(jù)傳輸路徑，最小化簇間數(shù)據(jù)通信開銷。與LEACH、EEUC和DEEUC算法相比，本文算法平衡了節(jié)點能耗，延緩了網(wǎng)絡中死亡節(jié)點的出現(xiàn)輪數(shù)，從而延長了網(wǎng)絡生存時間。

[1] 蘇兵,張鈺婧.基于非均勻分簇的無線傳感器網(wǎng)絡路由協(xié)議[J].計算機測量與控制,2016, 24(2):325-327.

[2] 劉半藤,周瑩,陳友榮,等.基于移動-能量代價函數(shù)的無線自組織網(wǎng)絡路由策略研究[J].傳感技術學報, 2017,30(2):302-305.

[3] 林德鈺,王泉,劉伎昭.無線傳感網(wǎng)的移動與靜態(tài)sink相結合的節(jié)能策略[J].哈爾濱工業(yè)大學學報, 2016,48(11):162-168.

[4] 張策,張霞,李鷗,等.基于CS的無線傳感器網(wǎng)絡動態(tài)分簇數(shù)據(jù)收集算法[J].計算機研究與發(fā)展,2016, 53(9):2000-2008.

[5] ZHANG X L, LI Q, FU Y, et al. An energy balancing LEACH algorithm for wireless sensor network[C]. International Conference on Electrical, Computer Engineering and Electronics, 2015:752-756.

[6] 張軍強,王汝傳,黃海平.基于分簇的無線多媒體傳感器網(wǎng)絡數(shù)據(jù)聚合方案研究[J].電子與信息學報, 2014,36(1):8-14.

[7] SALMABADI H, ADIBNIA F, SARRAM M A. An improvement on LEACH protocol (EZ-LEACH)[C]. International Conference on Knowledge-Based Engineering and Innovation(KBEI)，2015:956-970.

[8] LI C F, YE M, CHEN G H, et al. An energy-efficient unequal clustering mechanism for wireless sensor networks[C]. IEEE International Conference on Mobile Ad-hoc and Sensor Systems Conference， IEEE, 2005:597-604.

[9] 劉洲洲,王福豹,張克旺.基于混合蛙跳算法的非均勻分簇WSNs路由協(xié)議[J].計算機應用研究,2013,30(7):2173-2176.

[10] 岳麗穎, 戴月明, 吳定會. 一種能量優(yōu)化WSNs非均勻分簇路由協(xié)議[J]. 計算機工程與應用, 2015(15)： 80-85.

[11] 曾華圣, 熊慶宇, 杜敏,等. 一種分布式能量高效的WSNs非均勻分簇路由協(xié)議[J]. 傳感器與微系統(tǒng), 2014, 33(3):146-149.

[12] 江禹生, 李萍, 馬超. 一種能量高效的無線傳感器網(wǎng)絡拓撲控制算法[J]. 傳感器與微系統(tǒng), 2014, 33(2):146-149.

[13] HEINZELMAN W, CHANDRAKASAN A, BALAKRISHNAN H. An application-specific protocol architecture for wireless microsensor networks[J]. IEEE Transactions on Wireless Communications, 2002, 1(4): 660-670.

[14] 劉半藤, 周瑩, 陳友榮,等. 基于加權路由思想的無線自組織網(wǎng)絡生存時間優(yōu)化算法研究[J]. 傳感技術學報, 2017,30(3):463-466.