唐君超

　　（上海海事大學 信息工程學院，上海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é)點路由機制中，使節(jié)點傳輸數(shù)據(jù)到匯聚節(jié)點的使用能量最優(yōu)化，并且平衡整個網(wǎng)絡(luò)的能量消耗。仿真結(jié)果表明，RAEOC算法比傳統(tǒng)的分簇算法如LEACH和PEGASIS可分別節(jié)省68%和54%的能量。

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

0引言

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

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

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

1相關(guān)工作

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

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

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

　　1.2移動Sink模式

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

2模型與假設(shè)

　　2.1能量模型

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

　　接收l bit數(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é)點組成，節(jié)點用SN表示，{S1，S2，...，SN}被隨機部署在一個半徑為R的圓形檢測區(qū)域G內(nèi)。移動匯聚節(jié)點(Mobile Sink Node，MSN)分布在監(jiān)控區(qū)域邊界。對網(wǎng)絡(luò)作如下假設(shè)：

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

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

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

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

　　網(wǎng)絡(luò)模型如圖1所示，其中，●為監(jiān)測節(jié)點，▼為MSN。此處MSN的移動軌跡和收集并匯聚數(shù)據(jù)的策略參考了文獻［9］中的方法。MSN通過均勻速度v沿著監(jiān)測區(qū)域G的邊界移動來收集數(shù)據(jù)，當MSN開始移動時，

　　它負責向整個區(qū)域廣播自己的位置P和速度v，此時普通節(jié)點和CH記錄MSN的數(shù)據(jù)P和v，然后通過計算得到何時需要發(fā)送數(shù)據(jù)給MSN，如圖2。計算方式如下：

　　當MSN從P0點出發(fā)，向區(qū)域廣播自身位置時，CH到P1點距離可以由CH點到圓心點距離計算得出，P1點即MSN收集數(shù)據(jù)停留點，根據(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簇類劃分和簇頭選舉

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

3RAEOC算法

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

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

　?。?）建立圖中邊和賦權(quán)。節(jié)點與其鄰居節(jié)點可以相互通信，便可以建立成邊。邊上賦權(quán)則根據(jù)能量公式計算而得。此處假設(shè)網(wǎng)絡(luò)環(huán)境不復雜，使用自由空間模型。例如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。在運行算法過程中由于各節(jié)點相對位置不變化，而計算邊權(quán)時主要依賴于節(jié)點之間的距離條件，所以隨著網(wǎng)絡(luò)運行的周期增加，節(jié)點之間邊權(quán)值不變，傳輸數(shù)據(jù)會一直選擇同一條路由，從而會過早出現(xiàn)能量空洞。本算法中加入兩個邊權(quán)權(quán)重系數(shù)，可使能量剩余不多的節(jié)點減少使用率。以下為節(jié)點Sa到Sb的邊權(quán)計算方式：

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

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

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

　　M(1)［i］［j］=Minfor(r→n){cir+crj}(8)

　　若Si經(jīng)過k步到達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é)點，所以中繼節(jié)點將會承受巨大壓力。結(jié)合實際情況，節(jié)點可以越過簇頭，直接將數(shù)據(jù)傳輸給匯聚節(jié)點，所以此處將會選擇能量消耗較小的路徑來傳輸數(shù)據(jù)。

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

　　E(Si,MSN)=

　　Min{E(Si,MSN,l,d),M(k)［i］［MSN］}(10)

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

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

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

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

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

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

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

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

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

4仿真實驗

　　4.1仿真環(huán)境

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

       4.2實驗結(jié)果分析

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

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

5結(jié)論

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

參考文獻

　?。?］ AKYILDIZ I F, SU W, SANKARASUBRAMANIAM Y, et al. A survey on sensor networks［J］. IEEE Communications Magazine, 2002, 40(8):102114.

　?。?］ 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.

　?。?］ 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.

　?。?］ LINDSEY S, RAGHAVENDRA C S. PEGASIS: powerefficient gathering in sensor information systems［J］. ASAIO Journal, 1996, 42(5):11251130.

　?。?］ 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.

　?。?］ 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.

　?。?］ 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.

　?。?0］ CORMEN T H, LEISERSON C E, RIVEST R L, et al. 算法導論（第三版）［M］. 殷建平,徐云, 王剛,等，譯. 北京:機械工業(yè)出版社, 2013.