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

唐君超

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

?

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

唐君超

(上海海事大學(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)化

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

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]?？拷o態(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)生的開(kāi)銷，并且通過(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)更大的開(kā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ā)送lbit數(shù)據(jù)所消耗的能量為：

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

(1)

接收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ù)。

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

圖2　MSN收集數(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開(kāi)始移動(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ì)算方式如下：

(3)

當(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)建立模型。

圖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是被競(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ù)，有如下定義：

(6)

(7)

(3)使用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開(kāi)始移動(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所示。

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

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)生的開(kāi)銷，但在動(dòng)態(tài)調(diào)整網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)時(shí)效率會(huì)降低。

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

在多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　300 m×300 m區(qū)域下多MSN消耗的總能量

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

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)

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

中圖分類號(hào)：TP393

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

DOI：10.19358/j.issn.1674- 7720.2016.13.020

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

作者簡(jiǎn)介：

唐君超(1988-)，男，碩士研究生，主要研究方向：無(wú)線傳感器網(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