唐君超

　?。ㄉ虾：Ｊ麓髮W(xué) 信息工程學(xué)院，上海201306）

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

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

0引言

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

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

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

1相關(guān)工作

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

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

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

　　1.2移動(dòng)Sink模式

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

2模型與假設(shè)

　　2.1能量模型

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

　　接收l(shuí) bit數(shù)據(jù)所消耗的能量為：

　　ERx(l)=ERx－elec(l)=lEelec(2)

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

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

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

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

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

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

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

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

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

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

　　2.3簇類劃分和簇頭選舉

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

3RAEOC算法

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

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

　　（2）建立圖中邊和賦權(quán)。節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)可以相互通信，便可以建立成邊。邊上賦權(quán)則根據(jù)能量公式計(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)

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

　　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ù)。對(duì)于RE和DV兩系數(shù)，有如下定義：

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

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

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

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

　　E(Si,MSN)=

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

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

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

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

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

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

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

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

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

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

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

　　4.1仿真環(huán)境

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

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

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

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

5結(jié)論

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

參考文獻(xiàn)

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

　　［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.

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

　　［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.

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

　?。?］ 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. 算法導(dǎo)論（第三版）［M］. 殷建平,徐云, 王剛,等，譯. 北京:機(jī)械工業(yè)出版社, 2013.