WSN低功耗低時延路徑式協同計算方法

馬步云，馬新策，黃 松，任智源

(西安電子科技大學 綜合業務網理論及關鍵技術國家重點實驗室，陜西 西安 710071)

0 引言

無線傳感器網絡 (Wireless Sensor Network,WSN)[1]自提出以來得到快速發展，已被應用到包括醫療[2]、自然環境監測[3]等在內的多個領域。目前的WSN系統利用云平臺處理數據[4]，然而WSN采集的數據傳到云計算中心進行計算產生的通信開銷大、時延高，無法有效支撐時延敏感型業務。

針對云計算存在的高傳輸時延問題，出現了許多利用分布在網絡邊緣[5]的設備集群進行協同計算的方案。其中，基于步驟可分割的路徑式協同計算(路徑計算)方案[6-12]采用有向無環圖 (Directed Acyclic Graph,DAG) 表征業務，將DAG形式的業務映射到網絡邊緣設備上以降低任務處理時延，更適合處理復雜的新型信息業務。

但時延降低將導致能耗增加，WSN工作壽命減短，并且WSN通常位于野外，一旦能量耗盡，難以得到及時補充。因此，路徑計算如何進行任務映射，使得在能耗約束下業務處理時延最短，成為重要問題。為此，本文將能耗約束考慮進路徑計算中，提出了WSN低功耗低時延路徑式協同計算方法。

1 云霧網絡架構

為了能夠利用WSN支撐路徑計算的實現，本節基于一種WSN云霧網絡架構開展研究，如圖1所示。

圖1 云霧網絡架構Fig.1 Cloud fog network architecture

該架構自下而上為感知層、霧計算層和云計算層。感知層由集成一個或多個類型的無線傳感器組成，負責對所在區域進行監測。霧計算層由具備較強數據處理能力和通信能力的匯聚節點組成，一方面負責轉發和處理感知層產生的數據；另一方面負責將控制中心的命令傳達到傳感器節點，用戶可直接訪問匯聚節點獲取實時信息。云計算層由具備高性能的服務器集群構成，通過通信鏈路與匯聚節點相連，對WSN進行監控和管理。同時，當地面通信鏈路損壞或WSN部署區域缺少通信基礎設施時，可利用衛星網絡構成通信鏈路，實現云計算層和霧計算層的通信。

基于此架構，WSN產生的數據無需傳輸至云端進行處理，而是在云端提前制訂好將DAG形式的任務映射到網絡設備的任務調度方案，即任務映射策略，并將此策略下發到霧計算層，利用霧計算節點的計算能力逐步完成任務計算，顯著降低了任務處理時延。

2 能耗約束下的任務映射策略

基于云霧架構，路徑計算技術首先需要將DAG形式的業務圖映射至無向圖 (Undirected Graph,UG) 形式的霧網絡中，如圖2所示。

圖2 DAG至UG映射示例Fig.2 Example of DAG to UG mapping

2.1 DAG至UG映射規則模型

本節用有向無環圖G=(Ω，Γ)表示任務模型。定義Ω={ω1,ω2,…,ωs,ωs+1,…,ωl-1,ωl|s≥1,l>s+1}為G的節點集合，其中，ω1,ω2,…,ωs為s個任務起點，ωs+1,…,ωl-1為中間任務節點，ωl為任務終點。為簡化模型，本文僅考慮單任務情況。Γ為G的有向邊集合，定義Φ↑(ωi)={ωj|(ωj,ωi)∈Γ}為ωi的前向節點集合。

結合文獻[13]，圖G～圖U的映射規則如下：

定義1Ω～V的映射規則為ε:Ω→V，且ε需滿足：

(1)

ε將Ω的任務起點ω1,ω2,…,ωs映射為V的任務發起節點v1,v2,…,vs；將中間任務節點ωs+1,…,ωl-1映射為任意中繼節點vs+1,…,vt-1；將任務終點ωl映射為與用戶直連的節點vt。

定義2Γ～P的映射為Υ:Γ→P，且Υ需滿足：

Υ(ωi,ωj)=Pathε(ωi),ε(ωj)。

(2)

Υ將集合Γ中的有向邊映射為圖U中的節點ε(ωi)～ε(ωj)的最短路徑Pathε(ωi),ε(ωj)。

2.2 時延模型

上述映射規則可能會產生不同映射方案，導致不同的時延。為進一步降低時延，本小節基于2.1小節提出時延模型。

子任務ωi在某次映射關系中的時延可以表示為：

(3)

則圖G的任務處理時延為任務終點ωl的時延為：

T(G)=T(ωl)。

(4)

2.3 能耗模型

通過時延模型可計算出不同映射的任務處理時延，進而求出最短時延，但WSN能量有限，需要在能耗約束下完成任務計算，因此基于2.1和2.2小節提出能耗模型。

根據文獻[14]，WSN的能耗主要分為空閑能耗和活動能耗，忽略狀態轉換時的能耗，則網絡節點vi的能耗為：

(5)

2.3.1 空閑能耗

空閑能耗指節點處于空閑狀態時的能耗，根據文獻[15]所述，空閑能耗約占節點整體能耗的一半，因此必須考慮空閑能耗。

① 映射節點ε(ωi)的空閑能耗為：

(6)

(7)

2.3.2 活動能耗

① 映射節點ε(ωi)的活動能耗包括計算能耗和傳輸能耗，如式(8)所示：

(8)

(9)

由式(6)和式(8)可得，映射節點ε(ωi)的總能耗如式(10)：

(10)

(11)

整個霧網絡的總能耗為：

(12)

令整個霧網絡所含有的最大能量為Emax，則在某次任務G內，網絡所產生的能耗需小于等于最大能耗：

(13)

2.4 DAG至UG映射規則優化模型

僅根據2.1～2.3小節很難構建優化問題，為方便后續優化問題建立，基于上述小節給出DAG至UG映射規則的優化模型，并建立二值優化問題。

定義3子任務節點ωp和霧網絡節點vq的映射關系如下：當xωpvq=1時，ωp映射為vq；當xωpvq=0時，ωp不會映射為vq，則xωpvq滿足：

xωpvq∈{0,1}?ωp∈Ω,?vq∈V。

(14)

基于定義3，ωp～vq的映射可以構建為l×t的映射矩陣X，如式(15)：

(15)

則式(6)所表示的子任務ωi的時延可表示為式(16)：

(16)

任務G的時延可表示為X的函數，如式(17)：

T(G)=F(X)。

(17)

式(10)所示的映射節點ε(ωi)的總能耗可表示為：

(18)

(19)

則能耗約束下，圖G～圖U的最優映射關系建模如下：

X=argmin(F(X))

(20)

則求解圖G～圖U的最優映射關系可建模為求解式(20)的二值優化問題。

3 BPSO算法

(21)

(22)

第i個粒子在第n次迭代中，速度更新公式[19]為：

(23)

BPSO算法的位置更新公式如式(24)和式(25)：

(24)

(25)

本算法的適應度函數如式(26)：

f(X)=T(G)=F(X) 。

(26)

綜上所述，在求解上述時延優化模型時，BPSO算法的具體步驟如算法1所示。

算法1 BPSO算法1. fori=1:M do2. 初始化粒子的速度與位置3. 通過式(29)計算粒子適應度值4. 設置當前位置為粒子最佳位置pbest5. 通過比較得出全局最優位置gbest6. end for7. fork=1:Nmax do8. fori=1:M do9. 通過式(23)～式(25)更新粒子的速度和位置10.通過式(26)計算粒子適應度值11.If f(Xi+1) < f(pbest) then12. pbest = Xi+1;13. f(pbest) = f(Xi+1);14.end if15.If f(pbest) < f(gbest) then16. gbest = pbest;17. f(gbest) = f(pbest);18.end if19. end for20. end for21. Output:f(gbest)

4 仿真實驗及分析

圖3 仿真所用任務圖Fig.3 Task graph for simulation

考慮到WSN一般通過飛機等形式隨機投放到監測區域內，本次仿真利用Matlab隨機生成網絡拓樸圖，如圖4所示。

圖4 仿真所用網絡拓樸圖Fig.4 Network topology used in simulation

仿真平臺為Matlab，所用參數均參照文獻[16-17,20-24]設置，如表1所示。其中，fc為云服務器計算能力，Rc為云霧鏈路的數據傳輸速率，ffog為霧計算節點的計算能力，Rfog為霧鏈路數據傳輸速率，emax為單個節點的最大能量。

表1 系統參數

由表1可知，單個節點的最大能量為[0.5,2] J，結合圖4可知，霧網絡的最大能量Emax為[6,24] J。BPSO算法的基本參數為：種群規模M=500，最大迭代次數Nmax=1000，加速因子γ1=γ2=1，慣性權重ρ=1。

4.1 云計算與路徑計算時延性能對比

為驗證本文所提出的路徑計算方法的有效性，對比了3種不同業務的云計算和路徑計算的時延性能，并用Emax=6 J與Emax=24 J兩條線表示路徑計算的時延性能范圍。仿真結果如圖5所示。

(a) gzip ASCII壓縮任務

由圖5可知，路徑計算在處理不同類型任務時，開始均表現出Emax=6 J與Emax=24 J的時延無明顯差別，而當任務量大于某閾值時，Emax=6 J的時延高于Emax=24 J的現象。原因是：當任務量較小時，最佳映射產生的能耗低于Emax=6 J，因此二者無明顯差別；隨著任務量的增加，能耗也逐漸升高，當達到某閾值時，最佳映射產生的能耗高于Emax=6 J。為滿足能耗約束，不得不犧牲時延，將子任務映射至計算能力較差的節點上。

同時，隨著任務復雜度不斷增加，路徑計算的任務處理時延急劇增加，而云計算增長緩慢。原因是任務復雜度僅影響計算時延，而云計算的計算能力較強，因此任務復雜度的變化對云計算影響甚微；而匯聚節點計算能力較弱，因此當任務復雜度增加時，路徑計算的時延急劇增加，并且有逼近云計算的趨勢。據此可推測，當處理更復雜的任務時，云計算的時延性能將優于路徑計算。因此，路徑計算適合處理復雜度較低的任務，而云計算適合處理復雜度較高的任務。

4.2 BPSO算法與其他算法時延性能比較

為驗證BPSO算法在解決路徑計算方案的有效性，比較了處理多種任務時BPSO算法與加權輪轉法(WRR)、隨機動態算法(Pick-KX)以及貪婪負載均衡算法(Greedy-LB)的任務處理時延，如圖6和圖7所示。

圖6仿真了不同能耗約束下多種算法的時延性能，此時任務量取10 Mbit。由圖6可知，隨著Emax的增加，4種算法的任務處理時延均表現出先下降、后收斂于某一數值的趨勢，且BPSO算法的任務處理時延明顯低于其他3種算法，以x264 CBR編碼任務為例：當Emax=24 J時，BPSO、Greedy-LB、WRR以及Pick-KX的時延分別為4.609,6.733,7.754,7.936 s，BPSO算法相比于其他3種算法分別降低了31.55%,40.56%,41.92%。

圖7仿真了不同任務量約束下多種算法的時延性能，此時，能耗約束取24 J。由圖7可知，當數據量D<2 Mbit時，4種算法時延差別不明顯；但當任務量D>4 Mbit時，隨著任務量的增加， BPSO算法的時延明顯低于其他3種算法。以x264 CBR編碼任務為例：當任務量為10 Mbit時，BPSO、Greedy-LB、WRR以及Pick-KX的時延分別為3.91,6.608,6.87,7.122 s，BPSO算法相比于其他3種算法分別降低了40.83%,43.09%,45.10%。

這是因為Pick-KX算法隨機選取霧網絡節點進行映射，并未考慮節點的計算能力；WRR算法根據節點的計算能力大小關系進行映射，Greedy-LB算法通過選取當前負載最小的節點進行映射，但WRR和Greedy-LB均未考慮網絡邊的傳輸能力，仍不是最優；BPSO算法綜合考慮節點計算能力和網絡邊的傳輸能力，可達到有效降低任務處理時延的目標。

(a) gzip ASCII壓縮任務

(a) gzip ASCII壓縮任務

5 結論

針對WSN云計算模式處理任務時效性較差的問題，研究了一種云霧網絡架構，并將路徑計算技術引入WSN中，解決了將采集到的數據傳回云中心進行處理而引起的高傳輸時延問題。針對匯聚節點能耗增加導致壽命縮短的問題，提出了能耗約束下的路徑計算方法。仿真結果表明，在相同的能耗約束下，相比其他算法，基于BPSO算法得出的映射方案能有效降低業務處理時延。但本文所提出的映射方案僅限于靜態網絡，并未考慮DAG映射到動態網絡的情況，如何將DAG映射到動態網絡將是下一步的研究方向。