劉 云，王?；ǎ?嬋

(昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院，云南 昆明 650500)

能量在無(wú)線傳感網(wǎng)中是非常關(guān)鍵的因素，尤其是在給電池充電或者更換電池比較困難的環(huán)境中，因此高效節(jié)能是現(xiàn)在研究的熱點(diǎn)[1-2]。然而在許多應(yīng)用中比如火災(zāi)檢測(cè)，數(shù)據(jù)的實(shí)時(shí)有效性也變得同樣重要，因此必須權(quán)衡能耗和延時(shí)。

Younis O等人提出了HEED協(xié)議[3]，HEED協(xié)議是一種混合的高效節(jié)能分簇方法并且會(huì)定期更換簇頭。分簇方法是基于節(jié)點(diǎn)剩余能量和另一個(gè)參數(shù)，比如節(jié)點(diǎn)到相鄰節(jié)點(diǎn)的距離或節(jié)點(diǎn)的層級(jí)。HEED協(xié)議能均勻整個(gè)網(wǎng)絡(luò)的簇頭分布，從而均衡網(wǎng)絡(luò)能量消耗；但是其必須迭代多次達(dá)到定期更換簇頭的目的，因此會(huì)造成高昂的開(kāi)銷(xiāo)。

S Bai等人提出了DEAR協(xié)議[4]，該協(xié)議是一種多路徑延遲限制和能量限制自適應(yīng)路由協(xié)議。其考慮多種因素，比如可靠性、延遲和能量消耗，并且該協(xié)議允許數(shù)據(jù)包在網(wǎng)絡(luò)中連續(xù)傳輸，即使傳輸時(shí)發(fā)生沖突。它能在解決多目標(biāo)優(yōu)化問(wèn)題時(shí)，通過(guò)證明一個(gè)多項(xiàng)式時(shí)間算法來(lái)均衡延遲。然而由于算法的復(fù)雜度，節(jié)能和減小網(wǎng)絡(luò)延遲會(huì)受限。

為進(jìn)一步優(yōu)化能耗和延遲均衡的問(wèn)題，本文提出一種延遲能耗權(quán)衡多跳路由算法DETMR(Delay-Energy Trade-off in Multi-hop Routing)，該算法根據(jù)網(wǎng)絡(luò)和能量模型提出新的能量消耗函數(shù)和端到端延遲函數(shù)，根據(jù)這兩個(gè)函數(shù)選出滿(mǎn)足端到端延遲限制的能耗最少的最佳路由，并且能權(quán)衡能耗和延遲的關(guān)系，提高網(wǎng)絡(luò)整體性能。

1 模型分析

1.1 網(wǎng)絡(luò)模型

采用如圖1所示的網(wǎng)絡(luò)模型[5]，所有的節(jié)點(diǎn)分散在同一區(qū)域中，并做如下假設(shè)：(1)所有的節(jié)點(diǎn)靜止并且能量相同；(2)所有的節(jié)點(diǎn)都能感知自己的剩余能量并且根據(jù)傳輸?shù)木嚯x調(diào)節(jié)傳輸功率；(3)鏈路中的無(wú)線信號(hào)在所有方向上有相同的能量衰減；(4)如果通信的兩個(gè)傳感器沒(méi)有在彼此的通信范圍內(nèi)，則必須由其它的節(jié)點(diǎn)轉(zhuǎn)發(fā)；(5)所有的節(jié)點(diǎn)都能夠操作轉(zhuǎn)發(fā)模式和傳輸模式；(6)相鄰節(jié)點(diǎn)的數(shù)據(jù)是相關(guān)的，因此簇頭可以融合一部分?jǐn)?shù)據(jù)以減少總的數(shù)據(jù)傳輸。

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

如圖1所示的分簇網(wǎng)絡(luò)模型，傳感器節(jié)點(diǎn)分散在簇中，每個(gè)簇選出一個(gè)節(jié)點(diǎn)作為簇頭，剩下的節(jié)點(diǎn)是成員節(jié)點(diǎn)，成員節(jié)點(diǎn)把收集的數(shù)據(jù)發(fā)送給簇頭，簇頭接收并融合收集到的數(shù)據(jù)經(jīng)過(guò)多跳路由最后發(fā)送給匯聚節(jié)點(diǎn)。簇頭融合數(shù)據(jù)的同時(shí)也轉(zhuǎn)發(fā)數(shù)據(jù)[6]。傳感器節(jié)點(diǎn)(尤其是簇頭)能夠在發(fā)送數(shù)據(jù)給匯聚節(jié)點(diǎn)的過(guò)程中調(diào)節(jié)到相鄰節(jié)點(diǎn)的半徑。

1.2 能量模型

能量模型采用文獻(xiàn)[7]中的無(wú)線收發(fā)器能量耗散模型。接收l(shuí)bit數(shù)據(jù)時(shí)消耗的無(wú)線能量如下

ER(l)=Ee×l

(1)

其中，Ee是電子能量消耗參數(shù)。

假設(shè)相鄰節(jié)點(diǎn)傳輸?shù)臄?shù)據(jù)是相關(guān)的，則簇頭可以融合冗余的數(shù)據(jù)使之成為一個(gè)固定長(zhǎng)度的數(shù)據(jù)包。簇頭融合m個(gè)節(jié)點(diǎn)的lbit數(shù)據(jù)消耗的能量為

EF(l,m)=m×Ef×l

(2)

其中，Ef是數(shù)據(jù)融合參數(shù)。

當(dāng)距離是d時(shí)傳輸lbit數(shù)據(jù)消耗的能量如下

(3)

1.3 分簇過(guò)程

分簇過(guò)程以鄰居發(fā)現(xiàn)階段開(kāi)始，然后匯聚節(jié)點(diǎn)以一定的功率發(fā)送ADV消息給所有的節(jié)點(diǎn)并完成初始化[8]。每個(gè)節(jié)點(diǎn)根據(jù)接收到的信號(hào)強(qiáng)度計(jì)算到匯聚節(jié)點(diǎn)的距離。

每個(gè)節(jié)點(diǎn)在發(fā)送ADV(ID，E)消息給相鄰節(jié)點(diǎn)以及從相鄰節(jié)點(diǎn)接收數(shù)據(jù)前等待的時(shí)間為τ=1/E，ID是節(jié)點(diǎn)標(biāo)識(shí)符，E是節(jié)點(diǎn)的剩余能量。接收到ADV消息的節(jié)點(diǎn)之間比較能級(jí)，能級(jí)小的節(jié)點(diǎn)將會(huì)取消定時(shí)器從而成為成員節(jié)點(diǎn)。

候選簇頭是能級(jí)比較高的一系列節(jié)點(diǎn)，而通信范圍內(nèi)的兩個(gè)節(jié)點(diǎn)可能有相同的能級(jí)。為了解決這種情況，提出一種能量和延遲權(quán)衡(TED)方法來(lái)平衡能量消耗和端到端延遲。該方法通過(guò)調(diào)節(jié)參數(shù)α(α基于簇頭的能量消耗)和參數(shù)β(β基于簇頭到匯聚節(jié)點(diǎn)的距離)的值權(quán)衡能耗和延遲。如式(4)所示，TED表示選擇的候選簇頭。α和β是控制參數(shù)。α調(diào)節(jié)候選簇頭對(duì)剩余能量的依賴(lài)，β調(diào)節(jié)候選簇頭對(duì)距離的依賴(lài)。α和β值的范圍都是[0,1]，并且α+β≠0。

(4)

Ei是候選簇頭i的剩余能量，Et是其它候選簇頭接收ADV消息時(shí)積累的能量，d(i，s)是候選簇頭i到匯聚節(jié)點(diǎn)的距離。

若i是最終簇頭，則其發(fā)出通知之前等待的時(shí)間為ω=1/TEDi。其它候選簇頭收到最終簇頭的公告，取消它們的TED定時(shí)并且在當(dāng)前輪成為成員節(jié)點(diǎn)。分簇階段完成之后，所有的簇頭發(fā)送TDMA消息給成員節(jié)點(diǎn)并分配時(shí)隙[9]。

2 DETMR算法分析

DETMR算法是一個(gè)有連續(xù)回合的分布式方法，每一輪分為兩個(gè)階段[10]：分簇階段和數(shù)據(jù)傳輸階段。第一階段的任務(wù)主要是建立一個(gè)分簇的網(wǎng)絡(luò)拓?fù)洳⑶医⒍嗵酚?；第二階段的任務(wù)是通過(guò)簇頭傳輸從源節(jié)點(diǎn)到匯聚節(jié)點(diǎn)的數(shù)據(jù)。

2.1 計(jì)算端到端延遲

鏈路延遲D(i,j)測(cè)量從節(jié)點(diǎn)i到節(jié)點(diǎn)j的鏈路中數(shù)據(jù)包的延遲。定義鏈路延遲D(i,j)中節(jié)點(diǎn)的排隊(duì)延遲是dQ，傳輸延遲是dT以及傳播延遲是dP，用公式表示為

D(i,j)=(dQ+dT+dP)

(5)

其中，dT=l/φ,dP=d/γ；l是數(shù)據(jù)包長(zhǎng)度，Ψ是鏈路帶寬(bit/s)，d是簇頭i到簇頭j的物理鏈路長(zhǎng)度，γ是在媒介中的傳播速度(m/s)，dQ的值通過(guò)排隊(duì)理論[11]計(jì)算。節(jié)點(diǎn)隊(duì)列是M/M/1類(lèi)型的。在這種隊(duì)列中，輸入是泊松類(lèi)型，輸出是指數(shù)隨機(jī)變量，服務(wù)數(shù)是1。隊(duì)列中的排隊(duì)延遲可以用下式計(jì)算

(6)

μ是服務(wù)率，并且是一個(gè)指數(shù)隨機(jī)變量，λ是新數(shù)據(jù)包的進(jìn)入率，是泊松隨機(jī)變量。

Dete(x,s)表示端到端的延遲，是指數(shù)據(jù)從離開(kāi)源節(jié)點(diǎn)x到匯聚節(jié)點(diǎn)s接收經(jīng)過(guò)的時(shí)間。定義Dete(x,s)表示如下

(7)

假設(shè)μ，λ，Ψ和γ是對(duì)所有簇頭都相同的常數(shù)，U是從簇頭x到匯聚節(jié)點(diǎn)s之間的一系列中間節(jié)點(diǎn)。

2.2 計(jì)算路由成本

定義式(8)表示從簇頭i到j(luò)的鏈路消耗函數(shù)

(8)

其中,ER、EF、ET在式(1)～式(3)中已給出，ρ是節(jié)點(diǎn)剩余能量參數(shù)。

(9)

為了計(jì)算從簇頭x到匯聚節(jié)點(diǎn)s路由的消耗函數(shù)，定義

(10)

2.3 DETMR算法描述

DETMR算法是為了找到從簇頭x到匯聚節(jié)點(diǎn)s的最低消耗路由(最高效節(jié)能)。其中路由間端到端的延遲不存在延遲限制Δ。最小限制為

(11)

Rk是第k條路由，R′(x,s)是從簇頭x到匯聚節(jié)點(diǎn)s中端到端的延遲滿(mǎn)足Δ限制的一系列路由。Δ滿(mǎn)足

Dete(Rk)≤Δ

(12)

通過(guò)考慮以上優(yōu)化問(wèn)題，提出了算法1用來(lái)找到至少k個(gè)消耗路由符合端到端的延遲限制。算法1偽代碼如下：

1.SeR=?；SeR是從簇頭x到匯聚節(jié)點(diǎn)s傳輸數(shù)據(jù)時(shí)選擇的路由。

2.NoSa=?；NoSa是不滿(mǎn)足延遲限制Δ的一系列路由。

3.計(jì)算costij，?i,j∈C；C是一系列簇頭，j可以是匯聚節(jié)點(diǎn)。

4.計(jì)算K(x,s)；K(x,s)是從簇頭x到匯聚節(jié)點(diǎn)s可能的路由數(shù)。

5.找到至少k個(gè)消耗路由k-SR(x,s,k)；

6.while (k≠K(x,s)) do

7.Rk=k-SR(x,s,k)NoSa;

8.根據(jù)式(7)計(jì)算Dete(Rk);

9. if Dete(Rk)≤Δ then

10. SeR=Rk；

11. break；

12. else

13. NoSa=NoSa∪Rk；

14. k=k+1;

15. end if

16. end while

17. Return SeR；

算法根據(jù)式(8)中定義的消耗函數(shù)計(jì)算了從簇頭i到j(luò)的每一條鏈路的costij值，接著利用深度優(yōu)先搜索算法[13](DFS)計(jì)算從簇頭x到匯聚節(jié)點(diǎn)s可能的路由數(shù)。在第5行，算法根據(jù)公式(8)～式(10)利用最短是k的路徑找到至少k個(gè)路由。當(dāng)找到消耗最少的路由Rk(k的原始值是1)后，算法利用式(7)計(jì)算這條路由的端到端的延遲Dete(Rk)。再檢查端到端的延遲是不是滿(mǎn)足特定的閥值Δ。如果滿(mǎn)足，則選擇路由Rk；如果不滿(mǎn)足，把Rk移到NoSa。第7行將會(huì)移除不滿(mǎn)足延遲條件的最小消耗路由。

經(jīng)過(guò)證明[14]，算法總能在有限的時(shí)間內(nèi)完成，因此是收斂的。并且計(jì)算復(fù)雜度是一個(gè)多項(xiàng)式函數(shù)[15]，因此完全適合應(yīng)用在一個(gè)有有限個(gè)傳感器節(jié)點(diǎn)的分散式算法。

2.4 數(shù)據(jù)傳輸

一旦簇間多跳路由創(chuàng)建成功，就會(huì)開(kāi)始數(shù)據(jù)傳輸。每個(gè)節(jié)點(diǎn)分配傳輸時(shí)間之前會(huì)關(guān)閉無(wú)線電，然后在分配的時(shí)間內(nèi)發(fā)送數(shù)據(jù)給簇頭。簇頭從簇內(nèi)成員中接收數(shù)據(jù)。當(dāng)所有的數(shù)據(jù)被接收后，簇頭把接收的數(shù)據(jù)融合在單個(gè)的數(shù)據(jù)包來(lái)減少冗余和傳輸消耗的能量，然后把融合后的數(shù)據(jù)包發(fā)送給其它的簇頭，其它簇頭也按這種方式轉(zhuǎn)發(fā)數(shù)據(jù)直到到達(dá)匯聚節(jié)點(diǎn)。在一段確定的時(shí)間之后，開(kāi)始下一輪分簇過(guò)程。

由于成員節(jié)點(diǎn)只需要發(fā)送數(shù)據(jù)給簇頭，因此每個(gè)成員節(jié)點(diǎn)j消耗的能量為

Emem(j)=l×Ee+l×ε1×d2(j)

(13)

其中，d(j)是成員節(jié)點(diǎn)j到簇頭的距離。

而簇頭需要融合所有的簇間數(shù)據(jù)以及轉(zhuǎn)發(fā)數(shù)據(jù)給其他的簇頭，因此能量消耗為

ECH(i)=ER(i)+EF(i)+ES(i)

(14)

ER(i)=l×Ee×(sCH(i)+r)

(15)

EF(i)=sCH(i)×Ef×l

(16)

(17)

ER(i)是簇頭i接收所有的簇間數(shù)據(jù)消耗的能量，EF(i)是簇頭i融合所有的數(shù)據(jù)消耗的能量，ES(i)是簇頭i傳輸lbit的數(shù)據(jù)給其它簇頭或匯聚節(jié)點(diǎn)消耗的能量，sCH(i)表示屬于簇頭i的成員節(jié)點(diǎn)的數(shù)量，r是延遲時(shí)間，d是從簇頭i到下一跳的距離。

因此，每一輪總的能量消耗為

(18)

K是簇頭的數(shù)量，N是網(wǎng)絡(luò)中傳感器的數(shù)量。

3 仿真分析

仿真基于Matlab，并與HEED協(xié)議、DERA協(xié)議進(jìn)行對(duì)比，仿真參數(shù)如表1所示。

表1 仿真參數(shù)表

圖2 不同函數(shù)下能量消耗比較

圖3 能量消耗和端到端延遲權(quán)衡

圖3表示能量消耗和端到端延遲變化曲線，為了便于觀察，Dete和Etotal在同一個(gè)圖中，表示隨著轉(zhuǎn)發(fā)者的數(shù)量變化，能量消耗和端到端延遲的變化趨勢(shì)。通過(guò)分析兩種曲線，能獲得使能量消耗和端到端延遲獲得權(quán)衡的最佳跳數(shù)。在這里，選擇α=0.5，β=0.5,。從圖中可以看出，當(dāng)k=3(4跳)時(shí)，能使能量消耗和端到端延遲之間的權(quán)衡達(dá)到最佳，或k=2(3跳)也能達(dá)到目的。

圖4 3種算法網(wǎng)絡(luò)生命周期比較

圖4表示隨著通信次數(shù)的增加，3種算法活躍節(jié)點(diǎn)數(shù)的變化。仿真共進(jìn)行了50輪(每輪1 s)。在前15輪，3中算法節(jié)點(diǎn)數(shù)量并沒(méi)有明顯變化；15輪之后，活躍的節(jié)點(diǎn)數(shù)都有明顯的下降，并且HEED協(xié)議、DEAR協(xié)議與DETMR算法相比節(jié)點(diǎn)死亡更快，這是因?yàn)镈ETMR算法考慮到延遲控制問(wèn)題，均衡了網(wǎng)絡(luò)能量消耗，因此相比HEED協(xié)議、DEAR協(xié)議延長(zhǎng)了網(wǎng)絡(luò)生命周期。

圖5 不同延遲限制下總的能量消耗對(duì)比

圖5表示隨著延遲限制的增加HEED協(xié)議、DERA協(xié)議和DETMR算法總的能量消耗對(duì)比。從圖中可以看出，對(duì)于HEED協(xié)議、DERA協(xié)議隨著延遲限制的增加總的能量消耗是不變的(HEED協(xié)議是67 J，DERA協(xié)議是48 J)，而對(duì)于DETMR算法，隨著延遲限制的增加，總的能量消耗不斷減少。

4 結(jié)束語(yǔ)

無(wú)線傳感網(wǎng)中能量消耗和端到端的延遲是現(xiàn)在研究的熱點(diǎn)。本文提出了一種延遲能量權(quán)衡多跳路由算法—DETMR，算法根據(jù)網(wǎng)絡(luò)和能量模型提出一種新的能量消耗函數(shù)和端到端延遲函數(shù)。根據(jù)這兩個(gè)函數(shù)計(jì)算能量消耗和端到端延遲，選出滿(mǎn)足特定端到端延遲的最小能量消耗路由，從而確定數(shù)據(jù)傳輸?shù)淖罴崖窂?。仿真結(jié)果與HEED協(xié)議、DEAR協(xié)議相比，DETMR算法能均衡網(wǎng)絡(luò)能量消耗，延長(zhǎng)網(wǎng)絡(luò)生命周期。