基于Floyd的無線傳感器網絡簇內能量優化

唐君超

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

?

基于Floyd的無線傳感器網絡簇內能量優化

唐君超

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

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

關鍵詞：移動匯聚節點；能量空洞； Floyd算法；能量優化

引用格式：唐君超. 基于Floyd的無線傳感器網絡簇內能量優化[J].微型機與應用，2016,35(13)：60-63.

0引言

無線傳感器網絡由大量的傳感器節點通過無線通信的方式自組織成一個分布式網絡系統，這些傳感器節點一起協同運行工作，檢測并采集傳感器感應范圍內的信息數據。一般情況下傳感器節點搜集信息數據后把數據傳輸給匯聚節點(Sink)或基站進行再次處理[1]。

在無線傳感器網絡系統中主要靠能量策略和路由協議來決定該系統的生存時間。能量策略中的節能技術[2]占更大的比重。無線傳感器網絡在應用中需要布置到無人值守的區域，所以一旦部署完成，節點的電池就無法更換，因此在運用節能技術的同時應盡可能延長網絡的生存時間。

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

1相關工作

在傳統的無線傳感器網絡的路由場景中，由于數據進行傳輸和轉發是基于多對一的多跳路由通信模型，所以網絡中會存在能量消耗不平衡的情況[3]?？拷o態基站的節點由于轉發任務過重，導致能量消耗相對過大，從而死亡，這種現象稱為無線傳感器網絡的能量空洞問題。

1.1網絡層次分簇

LEACH協議[4]的基本思想是以循環的方式隨機選擇簇頭(Cluster Head，CH)節點，將整個網絡的能量負載平均分配到每個傳感器節點上。其缺點是不確定的簇頭數量導致簇頭分布不均，從而使網絡能耗不均勻。而且其只適用于小規模的網絡系統。PEGASIS[5]是對LEACH的一種改進協議。它采用基于鏈式結構的協議，運行PEGASIS協議時每個節點首先利用信號強度來探測所有鄰居節點的遠近，調整信號強度僅使最近鄰居節點能夠接收信號，鏈中只選擇一個節點作為匯聚節點進行任務傳輸。優點是減少了LEACH在簇重構過程中產生的開銷，并且通過數據融合降低了收發任務的次數，從而降低能耗。缺點是由于傳感器節點需要知道鄰居的能量情況，協議需要動態調整拓撲結構，在利用率高的網絡中，拓撲的調整會帶來更大的開銷。

1.2移動Sink模式

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

2模型與假設

2.1能量模型

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

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

(1)

接收lbit數據所消耗的能量為：

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

(2)

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

2.2網絡模型假設

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

(1)節點SN的部署位置在監控區域G內服從均勻分布；

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

(3)根據通信距離的遠近，SN的發射功率可以調節；

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

圖1　網絡模型

圖2　MSN收集數據策略

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

(3)

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

2.3簇類劃分和簇頭選舉

本文引用參考文獻[9]中的分簇方法和簇頭選舉算法，但稍作修改來適應文本中實驗的要求。采用此方法的原因是其可以適用于各種類型的無線傳感器網絡。無需采用其他復雜的分簇算法和簇頭選舉算法，因為本文重點關注的是如何優化簇中的路由能量優化。

3RAEOC算法

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

圖3　簇內的拓撲網絡

(1)構建圖模型。如圖3，將簇內網絡構建成圖模型，CH和MSN也為其中成員節點。由于CH是被競選為能量最多的節點，所以計算拓撲等都由CH來計算。在競選簇頭時，各個節點都對其鄰居節點發送過廣播，所以各個節點的距離都已知，通過距離根據能量模型便可以求出發送數據所消耗的能量。

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

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

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

(4)

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

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

(5)其中,RE(Sb)為節點Sb的剩余能量系數，DV(Sa)為節點Sa所發送數據量的系數。對于RE和DV兩系數，有如下定義：

(6)

(7)

(3)使用Floyd算法[10]來求得所有節點到MSN的最短路徑。將圖的拓撲關系用矩陣M[i][j]n×n來表示，若Si一步到達Sj，則cij=M(0)[i][j]為最短距離；若Si和Sj無連接，則cij=∞；若Si二步到達Sj，則設Si經過一個中間點Sr到達Sj，則M(1)[i][j]為最短距離矩陣。

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

(8)

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

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

(9)

在此處，由于應用此算法很有可能出現多跳情況將數據傳輸給匯聚節點，所以中繼節點將會承受巨大壓力。結合實際情況，節點可以越過簇頭，直接將數據傳輸給匯聚節點，所以此處將會選擇能量消耗較小的路徑來傳輸數據。

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

E(Si,MSN)=

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

(10)

以下是整個網絡運作的過程：

(1)劃分網絡成幾個均勻的簇組；

(2)簇類中所有節點都遍歷發送廣播消息；

(3)選出簇頭并且計算出各鄰居節點之間的邊權值；

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

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

(6)CH獲得整個簇內拓撲模型并使用RAEOC算法對模型求解，尋找各節點到MSN的最短路徑；

(7)CH向各節點廣播計算的結果路徑和發送時間；

(8)各節點沿著最短路徑發送收集的信息給MSN。

4仿真實驗

4.1仿真環境

為了評價RAEOC算法的性能，利用MATLAB在相同的環境下對LEACH、PEGASIS和本文算法進行仿真，并進行比較。在實驗中模擬了不同算法對網絡整體能量消耗和監測區域大小變化對能量消耗的影響，仿真環境如表1所示。

表1　網絡環境參數

4.2實驗結果分析

首先對比了RAEOC、LEACH和PEGASIS三種協議模擬20輪后消耗能量的大小。將100個節點隨機平均分布在300 m×300 m的監測區域，從圖4中可以看出，經過20輪后，RAEOC所消耗的總能量遠比另外兩種算法少，相比LEACH總能量消耗可節省68%，相比PEGASIS總能量消耗可節省54%。這主要是因為RAEOC使用了分簇算法并進行數據融合，使數據在路徑上傳輸所消耗的能量降低了。LEACH由于單純地采用隨機數和閾值的策略產生簇頭，會使簇頭分布不均，導致網絡能耗不平衡。在圖4中，LEACH的曲線隨著輪數的增加，斜率起伏變化，說明每輪能量消耗都不同，更容易產生能量空洞。PEGASIS雖然改進了LEACH，減少了在簇重構過程中產生的開銷，但在動態調整網絡拓撲結構時效率會降低。

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

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

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

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

5結論

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

參考文獻

[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. 算法導論(第三版)[M]. 殷建平,徐云, 王剛,等，譯. 北京:機械工業出版社, 2013.

中圖分類號：TP393

文獻標識碼：A

DOI：10.19358/j.issn.1674- 7720.2016.13.020

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

作者簡介：

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

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