WSN中多跳網絡能效和延遲控制優化研究

劉 云，王?；?，向 嬋

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

能量在無線傳感網中是非常關鍵的因素，尤其是在給電池充電或者更換電池比較困難的環境中，因此高效節能是現在研究的熱點[1-2]。然而在許多應用中比如火災檢測，數據的實時有效性也變得同樣重要，因此必須權衡能耗和延時。

Younis O等人提出了HEED協議[3]，HEED協議是一種混合的高效節能分簇方法并且會定期更換簇頭。分簇方法是基于節點剩余能量和另一個參數，比如節點到相鄰節點的距離或節點的層級。HEED協議能均勻整個網絡的簇頭分布，從而均衡網絡能量消耗；但是其必須迭代多次達到定期更換簇頭的目的，因此會造成高昂的開銷。

S Bai等人提出了DEAR協議[4]，該協議是一種多路徑延遲限制和能量限制自適應路由協議。其考慮多種因素，比如可靠性、延遲和能量消耗，并且該協議允許數據包在網絡中連續傳輸，即使傳輸時發生沖突。它能在解決多目標優化問題時，通過證明一個多項式時間算法來均衡延遲。然而由于算法的復雜度，節能和減小網絡延遲會受限。

為進一步優化能耗和延遲均衡的問題，本文提出一種延遲能耗權衡多跳路由算法DETMR(Delay-Energy Trade-off in Multi-hop Routing)，該算法根據網絡和能量模型提出新的能量消耗函數和端到端延遲函數，根據這兩個函數選出滿足端到端延遲限制的能耗最少的最佳路由，并且能權衡能耗和延遲的關系，提高網絡整體性能。

1 模型分析

1.1 網絡模型

采用如圖1所示的網絡模型[5]，所有的節點分散在同一區域中，并做如下假設：(1)所有的節點靜止并且能量相同；(2)所有的節點都能感知自己的剩余能量并且根據傳輸的距離調節傳輸功率；(3)鏈路中的無線信號在所有方向上有相同的能量衰減；(4)如果通信的兩個傳感器沒有在彼此的通信范圍內，則必須由其它的節點轉發；(5)所有的節點都能夠操作轉發模式和傳輸模式；(6)相鄰節點的數據是相關的，因此簇頭可以融合一部分數據以減少總的數據傳輸。

圖1 網絡模型

如圖1所示的分簇網絡模型，傳感器節點分散在簇中，每個簇選出一個節點作為簇頭，剩下的節點是成員節點，成員節點把收集的數據發送給簇頭，簇頭接收并融合收集到的數據經過多跳路由最后發送給匯聚節點。簇頭融合數據的同時也轉發數據[6]。傳感器節點(尤其是簇頭)能夠在發送數據給匯聚節點的過程中調節到相鄰節點的半徑。

1.2 能量模型

能量模型采用文獻[7]中的無線收發器能量耗散模型。接收lbit數據時消耗的無線能量如下

ER(l)=Ee×l

(1)

其中，Ee是電子能量消耗參數。

假設相鄰節點傳輸的數據是相關的，則簇頭可以融合冗余的數據使之成為一個固定長度的數據包。簇頭融合m個節點的lbit數據消耗的能量為

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

(2)

其中，Ef是數據融合參數。

當距離是d時傳輸lbit數據消耗的能量如下

(3)

1.3 分簇過程

分簇過程以鄰居發現階段開始，然后匯聚節點以一定的功率發送ADV消息給所有的節點并完成初始化[8]。每個節點根據接收到的信號強度計算到匯聚節點的距離。

每個節點在發送ADV(ID，E)消息給相鄰節點以及從相鄰節點接收數據前等待的時間為τ=1/E，ID是節點標識符，E是節點的剩余能量。接收到ADV消息的節點之間比較能級，能級小的節點將會取消定時器從而成為成員節點。

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

(4)

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

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

2 DETMR算法分析

DETMR算法是一個有連續回合的分布式方法，每一輪分為兩個階段[10]：分簇階段和數據傳輸階段。第一階段的任務主要是建立一個分簇的網絡拓撲并且建立多跳路由；第二階段的任務是通過簇頭傳輸從源節點到匯聚節點的數據。

2.1 計算端到端延遲

鏈路延遲D(i,j)測量從節點i到節點j的鏈路中數據包的延遲。定義鏈路延遲D(i,j)中節點的排隊延遲是dQ，傳輸延遲是dT以及傳播延遲是dP，用公式表示為

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

(5)

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

(6)

μ是服務率，并且是一個指數隨機變量，λ是新數據包的進入率，是泊松隨機變量。

Dete(x,s)表示端到端的延遲，是指數據從離開源節點x到匯聚節點s接收經過的時間。定義Dete(x,s)表示如下

(7)

假設μ，λ，Ψ和γ是對所有簇頭都相同的常數，U是從簇頭x到匯聚節點s之間的一系列中間節點。

2.2 計算路由成本

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

(8)

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

(9)

為了計算從簇頭x到匯聚節點s路由的消耗函數，定義

(10)

2.3 DETMR算法描述

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

(11)

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

Dete(Rk)≤Δ

(12)

通過考慮以上優化問題，提出了算法1用來找到至少k個消耗路由符合端到端的延遲限制。算法1偽代碼如下：

1.SeR=?；SeR是從簇頭x到匯聚節點s傳輸數據時選擇的路由。

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

3.計算costij，?i,j∈C；C是一系列簇頭，j可以是匯聚節點。

4.計算K(x,s)；K(x,s)是從簇頭x到匯聚節點s可能的路由數。

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

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

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

8.根據式(7)計算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；

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

經過證明[14]，算法總能在有限的時間內完成，因此是收斂的。并且計算復雜度是一個多項式函數[15]，因此完全適合應用在一個有有限個傳感器節點的分散式算法。

2.4 數據傳輸

一旦簇間多跳路由創建成功，就會開始數據傳輸。每個節點分配傳輸時間之前會關閉無線電，然后在分配的時間內發送數據給簇頭。簇頭從簇內成員中接收數據。當所有的數據被接收后，簇頭把接收的數據融合在單個的數據包來減少冗余和傳輸消耗的能量，然后把融合后的數據包發送給其它的簇頭，其它簇頭也按這種方式轉發數據直到到達匯聚節點。在一段確定的時間之后，開始下一輪分簇過程。

由于成員節點只需要發送數據給簇頭，因此每個成員節點j消耗的能量為

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

(13)

其中，d(j)是成員節點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接收所有的簇間數據消耗的能量，EF(i)是簇頭i融合所有的數據消耗的能量，ES(i)是簇頭i傳輸lbit的數據給其它簇頭或匯聚節點消耗的能量，sCH(i)表示屬于簇頭i的成員節點的數量，r是延遲時間，d是從簇頭i到下一跳的距離。

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

(18)

K是簇頭的數量，N是網絡中傳感器的數量。

3 仿真分析

仿真基于Matlab，并與HEED協議、DERA協議進行對比，仿真參數如表1所示。

表1 仿真參數表

圖2 不同函數下能量消耗比較

圖3 能量消耗和端到端延遲權衡

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

圖4 3種算法網絡生命周期比較

圖4表示隨著通信次數的增加，3種算法活躍節點數的變化。仿真共進行了50輪(每輪1 s)。在前15輪，3中算法節點數量并沒有明顯變化；15輪之后，活躍的節點數都有明顯的下降，并且HEED協議、DEAR協議與DETMR算法相比節點死亡更快，這是因為DETMR算法考慮到延遲控制問題，均衡了網絡能量消耗，因此相比HEED協議、DEAR協議延長了網絡生命周期。

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

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

4 結束語

無線傳感網中能量消耗和端到端的延遲是現在研究的熱點。本文提出了一種延遲能量權衡多跳路由算法—DETMR，算法根據網絡和能量模型提出一種新的能量消耗函數和端到端延遲函數。根據這兩個函數計算能量消耗和端到端延遲，選出滿足特定端到端延遲的最小能量消耗路由，從而確定數據傳輸的最佳路徑。仿真結果與HEED協議、DEAR協議相比，DETMR算法能均衡網絡能量消耗，延長網絡生命周期。