唐君超

(上海海事大學(xué) 信息工程學(xué)院，上海201306)

?

基于Floyd的無線傳感器網(wǎng)絡(luò)簇內(nèi)能量優(yōu)化

唐君超

(上海海事大學(xué) 信息工程學(xué)院，上海201306)

摘要：無線傳感器網(wǎng)絡(luò)中的能量空洞是無法避免的，能量空洞問題會加速整個網(wǎng)絡(luò)生命的死亡。針對簇型網(wǎng)絡(luò)中容易出現(xiàn)能量空洞問題，提出一種新的基于能量效率的簇中路由算法(a Route Algorithm based Energy Optimization in Cluster，RAEOC)。網(wǎng)絡(luò)被劃分成多個等區(qū)域的簇類，RAEOC將Floyd算法應(yīng)用到簇內(nèi)節(jié)點(diǎn)路由機(jī)制中，使節(jié)點(diǎn)傳輸數(shù)據(jù)到匯聚節(jié)點(diǎn)的使用能量最優(yōu)化，并且平衡整個網(wǎng)絡(luò)的能量消耗。仿真結(jié)果表明，RAEOC算法比傳統(tǒng)的分簇算法如LEACH和PEGASIS可分別節(jié)省68%和54%的能量。

關(guān)鍵詞：移動匯聚節(jié)點(diǎn)；能量空洞； Floyd算法；能量優(yōu)化

引用格式：唐君超. 基于Floyd的無線傳感器網(wǎng)絡(luò)簇內(nèi)能量優(yōu)化[J].微型機(jī)與應(yīng)用，2016,35(13)：60-63.

0引言

無線傳感器網(wǎng)絡(luò)由大量的傳感器節(jié)點(diǎn)通過無線通信的方式自組織成一個分布式網(wǎng)絡(luò)系統(tǒng)，這些傳感器節(jié)點(diǎn)一起協(xié)同運(yùn)行工作，檢測并采集傳感器感應(yīng)范圍內(nèi)的信息數(shù)據(jù)。一般情況下傳感器節(jié)點(diǎn)搜集信息數(shù)據(jù)后把數(shù)據(jù)傳輸給匯聚節(jié)點(diǎn)(Sink)或基站進(jìn)行再次處理[1]。

在無線傳感器網(wǎng)絡(luò)系統(tǒng)中主要靠能量策略和路由協(xié)議來決定該系統(tǒng)的生存時間。能量策略中的節(jié)能技術(shù)[2]占更大的比重。無線傳感器網(wǎng)絡(luò)在應(yīng)用中需要布置到無人值守的區(qū)域，所以一旦部署完成，節(jié)點(diǎn)的電池就無法更換，因此在運(yùn)用節(jié)能技術(shù)的同時應(yīng)盡可能延長網(wǎng)絡(luò)的生存時間。

本文提出一種新的基于能量效率的簇中路由算法(a Route Algorithm based Energy Optimization in Cluster，RAEOC)，通過在使用移動Sink的無線傳感器網(wǎng)絡(luò)中進(jìn)行區(qū)域分簇，然后在簇中使用基于能量優(yōu)化的路由策略。RAEOC的最終目標(biāo)是利用能量優(yōu)化策略來達(dá)到整個網(wǎng)絡(luò)壽命的延長。

1相關(guān)工作

在傳統(tǒng)的無線傳感器網(wǎng)絡(luò)的路由場景中，由于數(shù)據(jù)進(jìn)行傳輸和轉(zhuǎn)發(fā)是基于多對一的多跳路由通信模型，所以網(wǎng)絡(luò)中會存在能量消耗不平衡的情況[3]?？拷o態(tài)基站的節(jié)點(diǎn)由于轉(zhuǎn)發(fā)任務(wù)過重，導(dǎo)致能量消耗相對過大，從而死亡，這種現(xiàn)象稱為無線傳感器網(wǎng)絡(luò)的能量空洞問題。

1.1網(wǎng)絡(luò)層次分簇

LEACH協(xié)議[4]的基本思想是以循環(huán)的方式隨機(jī)選擇簇頭(Cluster Head，CH)節(jié)點(diǎn)，將整個網(wǎng)絡(luò)的能量負(fù)載平均分配到每個傳感器節(jié)點(diǎn)上。其缺點(diǎn)是不確定的簇頭數(shù)量導(dǎo)致簇頭分布不均，從而使網(wǎng)絡(luò)能耗不均勻。而且其只適用于小規(guī)模的網(wǎng)絡(luò)系統(tǒng)。PEGASIS[5]是對LEACH的一種改進(jìn)協(xié)議。它采用基于鏈?zhǔn)浇Y(jié)構(gòu)的協(xié)議，運(yùn)行PEGASIS協(xié)議時每個節(jié)點(diǎn)首先利用信號強(qiáng)度來探測所有鄰居節(jié)點(diǎn)的遠(yuǎn)近，調(diào)整信號強(qiáng)度僅使最近鄰居節(jié)點(diǎn)能夠接收信號，鏈中只選擇一個節(jié)點(diǎn)作為匯聚節(jié)點(diǎn)進(jìn)行任務(wù)傳輸。優(yōu)點(diǎn)是減少了LEACH在簇重構(gòu)過程中產(chǎn)生的開銷，并且通過數(shù)據(jù)融合降低了收發(fā)任務(wù)的次數(shù)，從而降低能耗。缺點(diǎn)是由于傳感器節(jié)點(diǎn)需要知道鄰居的能量情況，協(xié)議需要動態(tài)調(diào)整拓?fù)浣Y(jié)構(gòu)，在利用率高的網(wǎng)絡(luò)中，拓?fù)涞恼{(diào)整會帶來更大的開銷。

1.2移動Sink模式

其原理為基于策略的移動Sink沿著預(yù)先設(shè)定的路徑收集數(shù)據(jù)。參考文獻(xiàn)[6]提出了三層體系結(jié)構(gòu)下移動Sink隨機(jī)地在節(jié)點(diǎn)區(qū)域移動，并收集移動路徑上感知范圍內(nèi)的節(jié)點(diǎn)數(shù)據(jù)。Sink會遍歷整個網(wǎng)絡(luò)，一旦到達(dá)原始出發(fā)點(diǎn)就結(jié)束了一輪收集。參考文獻(xiàn)[7]提出了一種基于能量效率的數(shù)據(jù)收集策略，原理是將一個名為SenCar的數(shù)據(jù)監(jiān)測器作為移動Sink，當(dāng)Sink的傳輸范圍不夠時，需要進(jìn)行網(wǎng)絡(luò)分簇并計算出其移動的轉(zhuǎn)折點(diǎn)(Turning Points)，這個策略在實(shí)驗(yàn)中可以延長整個網(wǎng)絡(luò)壽命，但缺點(diǎn)是延遲較高。

2模型與假設(shè)

2.1能量模型

本文采用參考文獻(xiàn)[8]中的能量模型。根據(jù)節(jié)點(diǎn)間距離的不同，可以分為兩種模型，分別是自由空間模型和多路徑衰減模型。距離為d的情況下發(fā)送lbit數(shù)據(jù)所消耗的能量為：

ETx(l,d)=ETx-elec(l)+ETx-amp(l,d)=

(1)

接收lbit數(shù)據(jù)所消耗的能量為：

ERx(l)=ERx-elec(l)=lEelec

(2)

其中，Eelec為發(fā)送或接收單位比特數(shù)據(jù)所消耗的能量；εfs和εamp代表放大器系數(shù)；d0是距離邊界值。

2.2網(wǎng)絡(luò)模型假設(shè)

假設(shè)整個無線傳感器網(wǎng)絡(luò)由N個傳感器節(jié)點(diǎn)組成，節(jié)點(diǎn)用SN表示，{S1，S2，...，SN}被隨機(jī)部署在一個半徑為R的圓形檢測區(qū)域G內(nèi)。移動匯聚節(jié)點(diǎn)(Mobile Sink Node，MSN)分布在監(jiān)控區(qū)域邊界。對網(wǎng)絡(luò)作如下假設(shè)：

(1)節(jié)點(diǎn)SN的部署位置在監(jiān)控區(qū)域G內(nèi)服從均勻分布；

(2)節(jié)點(diǎn)SN擁有唯一ID號并且初始能量相同；

(3)根據(jù)通信距離的遠(yuǎn)近，SN的發(fā)射功率可以調(diào)節(jié)；

(4)MSN沿著G的邊界進(jìn)行勻速移動來收集數(shù)據(jù)。

圖1　網(wǎng)絡(luò)模型

圖2　MSN收集數(shù)據(jù)策略

網(wǎng)絡(luò)模型如圖1所示，其中，●為監(jiān)測節(jié)點(diǎn)，▼為MSN。此處MSN的移動軌跡和收集并匯聚數(shù)據(jù)的策略參考了文獻(xiàn)[9]中的方法。MSN通過均勻速度v沿著監(jiān)測區(qū)域G的邊界移動來收集數(shù)據(jù)，當(dāng)MSN開始移動時，它負(fù)責(zé)向整個區(qū)域廣播自己的位置P和速度v，此時普通節(jié)點(diǎn)和CH記錄MSN的數(shù)據(jù)P和v，然后通過計算得到何時需要發(fā)送數(shù)據(jù)給MSN，如圖2。計算方式如下：

(3)

當(dāng)MSN從P0點(diǎn)出發(fā)，向區(qū)域廣播自身位置時，CH到P1點(diǎn)距離可以由CH點(diǎn)到圓心點(diǎn)距離計算得出，P1點(diǎn)即MSN收集數(shù)據(jù)停留點(diǎn)，根據(jù)式(3)計算出時間t，然后CH在接收到MSN廣播后經(jīng)過時間t后向MSN發(fā)送所收集到的數(shù)據(jù)，發(fā)送功率可以調(diào)節(jié)為CH到P1的距離。由此可以最優(yōu)化地利用能量。這里假設(shè)MSN在收集數(shù)據(jù)時會停留足夠長的時間來完成數(shù)據(jù)的收集，完成后繼續(xù)沿邊界移動并再次發(fā)出廣播。

2.3簇類劃分和簇頭選舉

本文引用參考文獻(xiàn)[9]中的分簇方法和簇頭選舉算法，但稍作修改來適應(yīng)文本中實(shí)驗(yàn)的要求。采用此方法的原因是其可以適用于各種類型的無線傳感器網(wǎng)絡(luò)。無需采用其他復(fù)雜的分簇算法和簇頭選舉算法，因?yàn)楸疚闹攸c(diǎn)關(guān)注的是如何優(yōu)化簇中的路由能量優(yōu)化。

3RAEOC算法

許多路由問題往往可以規(guī)約為一個圖的問題，本文將傳感器節(jié)點(diǎn)看作圖中的點(diǎn)，節(jié)點(diǎn)之間的通信作為邊，通信所需要的能量消耗當(dāng)作邊上的賦權(quán)，此時基于能量的路由研究問題即可當(dāng)作圖的極值問題來建立模型。

圖3　簇內(nèi)的拓?fù)渚W(wǎng)絡(luò)

(1)構(gòu)建圖模型。如圖3，將簇內(nèi)網(wǎng)絡(luò)構(gòu)建成圖模型，CH和MSN也為其中成員節(jié)點(diǎn)。由于CH是被競選為能量最多的節(jié)點(diǎn)，所以計算拓?fù)涞榷加蒀H來計算。在競選簇頭時，各個節(jié)點(diǎn)都對其鄰居節(jié)點(diǎn)發(fā)送過廣播，所以各個節(jié)點(diǎn)的距離都已知，通過距離根據(jù)能量模型便可以求出發(fā)送數(shù)據(jù)所消耗的能量。

(2)建立圖中邊和賦權(quán)。節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)可以相互通信，便可以建立成邊。邊上賦權(quán)則根據(jù)能量公式計算而得。此處假設(shè)網(wǎng)絡(luò)環(huán)境不復(fù)雜，使用自由空間模型。例如S5與S6之間的距離為a，則能量消耗為：

E(S5,S6,l,a)=ETx(l,d)+ERx(l)=

lEelec+lεfsa2+lEelec=l(2Eelec+εfsa2)

(4)

此處，算法中引入兩個權(quán)重系數(shù)：一個是剩余能量系數(shù)RE，另一個是數(shù)據(jù)量系數(shù)DV。在運(yùn)行算法過程中由于各節(jié)點(diǎn)相對位置不變化，而計算邊權(quán)時主要依賴于節(jié)點(diǎn)之間的距離條件，所以隨著網(wǎng)絡(luò)運(yùn)行的周期增加，節(jié)點(diǎn)之間邊權(quán)值不變，傳輸數(shù)據(jù)會一直選擇同一條路由，從而會過早出現(xiàn)能量空洞。本算法中加入兩個邊權(quán)權(quán)重系數(shù)，可使能量剩余不多的節(jié)點(diǎn)減少使用率。以下為節(jié)點(diǎn)Sa到Sb的邊權(quán)計算方式：

E(Sa,Sb)=E(Sa,Sb,l,b)×RE(Sb)×DV(Sa)

(5)其中,RE(Sb)為節(jié)點(diǎn)Sb的剩余能量系數(shù)，DV(Sa)為節(jié)點(diǎn)Sa所發(fā)送數(shù)據(jù)量的系數(shù)。對于RE和DV兩系數(shù)，有如下定義：

(6)

(7)

(3)使用Floyd算法[10]來求得所有節(jié)點(diǎn)到MSN的最短路徑。將圖的拓?fù)潢P(guān)系用矩陣M[i][j]n×n來表示，若Si一步到達(dá)Sj，則cij=M(0)[i][j]為最短距離；若Si和Sj無連接，則cij=∞；若Si二步到達(dá)Sj，則設(shè)Si經(jīng)過一個中間點(diǎn)Sr到達(dá)Sj，則M(1)[i][j]為最短距離矩陣。

M(1)[i][j]=Minfor(r→n){cir+crj}

(8)

若Si經(jīng)過k步到達(dá)Sj，則根據(jù)迭代，可得出最短距離矩陣M(k)[i][j]，迭代公式如下：

M(k)[i][j]=Minfor(r→n){M(k-1)ir+M(k-1)rj}

(9)

在此處，由于應(yīng)用此算法很有可能出現(xiàn)多跳情況將數(shù)據(jù)傳輸給匯聚節(jié)點(diǎn)，所以中繼節(jié)點(diǎn)將會承受巨大壓力。結(jié)合實(shí)際情況，節(jié)點(diǎn)可以越過簇頭，直接將數(shù)據(jù)傳輸給匯聚節(jié)點(diǎn)，所以此處將會選擇能量消耗較小的路徑來傳輸數(shù)據(jù)。

最終Si到MSN的能量消耗可以表示為：

E(Si,MSN)=

Min{E(Si,MSN,l,d),M(k)[i][MSN]}

(10)

以下是整個網(wǎng)絡(luò)運(yùn)作的過程：

(1)劃分網(wǎng)絡(luò)成幾個均勻的簇組；

(2)簇類中所有節(jié)點(diǎn)都遍歷發(fā)送廣播消息；

(3)選出簇頭并且計算出各鄰居節(jié)點(diǎn)之間的邊權(quán)值；

(4)MSN開始移動，并且廣播自身位置和速度；

(5)CH計算出距離MSN最近的時刻，并設(shè)置任務(wù)，在此時刻發(fā)送融合的數(shù)據(jù)；

(6)CH獲得整個簇內(nèi)拓?fù)淠Ｐ筒⑹褂肦AEOC算法對模型求解，尋找各節(jié)點(diǎn)到MSN的最短路徑；

(7)CH向各節(jié)點(diǎn)廣播計算的結(jié)果路徑和發(fā)送時間；

(8)各節(jié)點(diǎn)沿著最短路徑發(fā)送收集的信息給MSN。

4仿真實(shí)驗(yàn)

4.1仿真環(huán)境

為了評價RAEOC算法的性能，利用MATLAB在相同的環(huán)境下對LEACH、PEGASIS和本文算法進(jìn)行仿真，并進(jìn)行比較。在實(shí)驗(yàn)中模擬了不同算法對網(wǎng)絡(luò)整體能量消耗和監(jiān)測區(qū)域大小變化對能量消耗的影響，仿真環(huán)境如表1所示。

表1　網(wǎng)絡(luò)環(huán)境參數(shù)

4.2實(shí)驗(yàn)結(jié)果分析

首先對比了RAEOC、LEACH和PEGASIS三種協(xié)議模擬20輪后消耗能量的大小。將100個節(jié)點(diǎn)隨機(jī)平均分布在300 m×300 m的監(jiān)測區(qū)域，從圖4中可以看出，經(jīng)過20輪后，RAEOC所消耗的總能量遠(yuǎn)比另外兩種算法少，相比LEACH總能量消耗可節(jié)省68%，相比PEGASIS總能量消耗可節(jié)省54%。這主要是因?yàn)镽AEOC使用了分簇算法并進(jìn)行數(shù)據(jù)融合，使數(shù)據(jù)在路徑上傳輸所消耗的能量降低了。LEACH由于單純地采用隨機(jī)數(shù)和閾值的策略產(chǎn)生簇頭，會使簇頭分布不均，導(dǎo)致網(wǎng)絡(luò)能耗不平衡。在圖4中，LEACH的曲線隨著輪數(shù)的增加，斜率起伏變化，說明每輪能量消耗都不同，更容易產(chǎn)生能量空洞。PEGASIS雖然改進(jìn)了LEACH，減少了在簇重構(gòu)過程中產(chǎn)生的開銷，但在動態(tài)調(diào)整網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)時效率會降低。

圖4　LEACH，PEGASIS和RAEOC消耗的總能量

在多MSN的情況下，網(wǎng)絡(luò)能量消耗的情況，如圖5所示。在300 m×300 m的區(qū)域中，隨著MSN的數(shù)量增多，總能量消耗會降低。同樣如圖6，在500 m×500 m的區(qū)域中也是如此。當(dāng)MSN為3個時，總能量消耗降低明顯，但超過3個后，效果并不明顯，減少的余地很小。所以得出結(jié)論，部署3個MSN對于能量消耗減少效果相對較好。

圖5　300 m×300 m區(qū)域下多MSN消耗的總能量

圖6　500 m×500 m區(qū)域下多MSN消耗的總能量

5結(jié)論

基于在無線傳感器網(wǎng)絡(luò)中能量的消耗問題，提出了一種分簇并優(yōu)化簇內(nèi)路由的算法。該算法可以幫助網(wǎng)絡(luò)節(jié)省能量消耗，延長網(wǎng)絡(luò)壽命，并且通過簇內(nèi)算法平衡每個節(jié)點(diǎn)的能量消耗，可以減緩出現(xiàn)能量空洞的時間。仿真結(jié)果也表明，相比傳統(tǒng)的LEACH和PEGASIS，本文算法在整體網(wǎng)絡(luò)能量消耗上減少更多。在今后的研究中，可以考慮使用改進(jìn)型的Floyd算法或者其他多源最短路徑算法來替代Floyd算法。

參考文獻(xiàn)

[1] AKYILDIZ I F, SU W, SANKARASUBRAMANIAM Y, et al. A survey on sensor networks[J]. IEEE Communications Magazine, 2002, 40(8):102-114.

[2] PANTAZIS N A, VERGADOS D D. A survey on power control issues in wireless sensor networks[J]. Communications Surveys

& Tutorials, 2007, 9(4):86-107.

[3] CHEN G, LI C, YE M, et al. An unequal cluster-based routing protocol in wireless sensor networks[J]. Wireless Networks, 2007, 15(2):193-207.

[4] STOJMENOVIC I, LIN X. Loop-free hybrid single-path/flooding routing algorithms with guaranteed delivery for wireless networks[J]. Parallel and Distributed Systems, 2001, 12(10):1023-1032.

[5] LINDSEY S, RAGHAVENDRA C S. PEGASIS: power-efficient gathering in sensor information systems[J]. ASAIO Journal, 1996, 42(5):1125-1130.

[6] SHAH R C, ROY S, JAIN S, et al. Data MULEs: modeling and analysis of a three-tier architecture for sparse sensor networks[J]. Ad Hoc Networks, 2003, 1(2-3):215-233.

[7] MA M, YANG Y. SenCar: an energy efficient data gathering mechanism for large scale multihop sensor networks[J]. Parallel & Distributed Systems IEEE Transactions on, 2006, 18(10):1476-1488.

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

[9] Wang Jin, Yin Yue, KIM J U, et al. An mobile-sink based energy-efficient clustering algorithm for wireless sensor networks[C].Computer and Information Technology (CIT),2012 IEEE 12th International Conference on. IEEE, 2012:678-683.

[10] CORMEN T H, LEISERSON C E, RIVEST R L, et al. 算法導(dǎo)論(第三版)[M]. 殷建平,徐云, 王剛,等，譯. 北京:機(jī)械工業(yè)出版社, 2013.

中圖分類號：TP393

文獻(xiàn)標(biāo)識碼：A

DOI：10.19358/j.issn.1674- 7720.2016.13.020

(收稿日期：2016-03-14)

作者簡介：

唐君超(1988-)，男，碩士研究生，主要研究方向：無線傳感器網(wǎng)絡(luò)。

Wireless sensor network energy optimization in cluster based on Floyd

Tang Junchao

(School of Information Engineering, Shanghai Maritime University, Shanghai 201306, China)

Abstract:Suffering from energy hole problem is inevitable in the wireless sensor networks. Energy hole problem will hasten the death of the whole network. To solve this problem in the clustering network, we propose a route algorithm based energy optimization in cluster (RAEOC). The network is divided into some uniform clusters, and RAEOC applies the Floyd algorithm to intra-cluster routing. It optimizes the energy consume of data transmission from sensor nodes to sink, and balances the energy consume of the whole network. Simulation results indicate that RAEOC algorithm can save energy 68% and 54% than traditional clustering algorithms such as LEACH and PEGASIS.

Key words:mobile sink node; energy hole; Floyd algorithm; energy optimization