WSN低功耗低時(shí)延路徑式協(xié)同計(jì)算方法

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

(西安電子科技大學(xué) 綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710071)

0 引言

無線傳感器網(wǎng)絡(luò) (Wireless Sensor Network,WSN)[1]自提出以來得到快速發(fā)展，已被應(yīng)用到包括醫(yī)療[2]、自然環(huán)境監(jiān)測(cè)[3]等在內(nèi)的多個(gè)領(lǐng)域。目前的WSN系統(tǒng)利用云平臺(tái)處理數(shù)據(jù)[4]，然而WSN采集的數(shù)據(jù)傳到云計(jì)算中心進(jìn)行計(jì)算產(chǎn)生的通信開銷大、時(shí)延高，無法有效支撐時(shí)延敏感型業(yè)務(wù)。

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

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

1 云霧網(wǎng)絡(luò)架構(gòu)

為了能夠利用WSN支撐路徑計(jì)算的實(shí)現(xiàn)，本節(jié)基于一種WSN云霧網(wǎng)絡(luò)架構(gòu)開展研究，如圖1所示。

圖1 云霧網(wǎng)絡(luò)架構(gòu)Fig.1 Cloud fog network architecture

該架構(gòu)自下而上為感知層、霧計(jì)算層和云計(jì)算層。感知層由集成一個(gè)或多個(gè)類型的無線傳感器組成，負(fù)責(zé)對(duì)所在區(qū)域進(jìn)行監(jiān)測(cè)。霧計(jì)算層由具備較強(qiáng)數(shù)據(jù)處理能力和通信能力的匯聚節(jié)點(diǎn)組成，一方面負(fù)責(zé)轉(zhuǎn)發(fā)和處理感知層產(chǎn)生的數(shù)據(jù)；另一方面負(fù)責(zé)將控制中心的命令傳達(dá)到傳感器節(jié)點(diǎn)，用戶可直接訪問匯聚節(jié)點(diǎn)獲取實(shí)時(shí)信息。云計(jì)算層由具備高性能的服務(wù)器集群構(gòu)成，通過通信鏈路與匯聚節(jié)點(diǎn)相連，對(duì)WSN進(jìn)行監(jiān)控和管理。同時(shí)，當(dāng)?shù)孛嫱ㄐ沛溌窊p壞或WSN部署區(qū)域缺少通信基礎(chǔ)設(shè)施時(shí)，可利用衛(wèi)星網(wǎng)絡(luò)構(gòu)成通信鏈路，實(shí)現(xiàn)云計(jì)算層和霧計(jì)算層的通信。

基于此架構(gòu)，WSN產(chǎn)生的數(shù)據(jù)無需傳輸至云端進(jìn)行處理，而是在云端提前制訂好將DAG形式的任務(wù)映射到網(wǎng)絡(luò)設(shè)備的任務(wù)調(diào)度方案，即任務(wù)映射策略，并將此策略下發(fā)到霧計(jì)算層，利用霧計(jì)算節(jié)點(diǎn)的計(jì)算能力逐步完成任務(wù)計(jì)算，顯著降低了任務(wù)處理時(shí)延。

2 能耗約束下的任務(wù)映射策略

基于云霧架構(gòu)，路徑計(jì)算技術(shù)首先需要將DAG形式的業(yè)務(wù)圖映射至無向圖 (Undirected Graph,UG) 形式的霧網(wǎng)絡(luò)中，如圖2所示。

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

2.1 DAG至UG映射規(guī)則模型

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

結(jié)合文獻(xiàn)[13]，圖G～圖U的映射規(guī)則如下：

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

(1)

ε將Ω的任務(wù)起點(diǎn)ω1,ω2,…,ωs映射為V的任務(wù)發(fā)起節(jié)點(diǎn)v1,v2,…,vs；將中間任務(wù)節(jié)點(diǎn)ωs+1,…,ωl-1映射為任意中繼節(jié)點(diǎn)vs+1,…,vt-1；將任務(wù)終點(diǎn)ωl映射為與用戶直連的節(jié)點(diǎn)vt。

定義2?！玃的映射為Υ:?！鶳，且Υ需滿足：

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

(2)

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

2.2 時(shí)延模型

上述映射規(guī)則可能會(huì)產(chǎn)生不同映射方案，導(dǎo)致不同的時(shí)延。為進(jìn)一步降低時(shí)延，本小節(jié)基于2.1小節(jié)提出時(shí)延模型。

子任務(wù)ωi在某次映射關(guān)系中的時(shí)延可以表示為：

(3)

則圖G的任務(wù)處理時(shí)延為任務(wù)終點(diǎn)ωl的時(shí)延為：

T(G)=T(ωl)。

(4)

2.3 能耗模型

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

根據(jù)文獻(xiàn)[14]，WSN的能耗主要分為空閑能耗和活動(dòng)能耗，忽略狀態(tài)轉(zhuǎn)換時(shí)的能耗，則網(wǎng)絡(luò)節(jié)點(diǎn)vi的能耗為：

(5)

2.3.1 空閑能耗

空閑能耗指節(jié)點(diǎn)處于空閑狀態(tài)時(shí)的能耗，根據(jù)文獻(xiàn)[15]所述，空閑能耗約占節(jié)點(diǎn)整體能耗的一半，因此必須考慮空閑能耗。

① 映射節(jié)點(diǎn)ε(ωi)的空閑能耗為：

(6)

(7)

2.3.2 活動(dòng)能耗

① 映射節(jié)點(diǎn)ε(ωi)的活動(dòng)能耗包括計(jì)算能耗和傳輸能耗，如式(8)所示：

(8)

(9)

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

(10)

(11)

整個(gè)霧網(wǎng)絡(luò)的總能耗為：

(12)

令整個(gè)霧網(wǎng)絡(luò)所含有的最大能量為Emax，則在某次任務(wù)G內(nèi)，網(wǎng)絡(luò)所產(chǎn)生的能耗需小于等于最大能耗：

(13)

2.4 DAG至UG映射規(guī)則優(yōu)化模型

僅根據(jù)2.1～2.3小節(jié)很難構(gòu)建優(yōu)化問題，為方便后續(xù)優(yōu)化問題建立，基于上述小節(jié)給出DAG至UG映射規(guī)則的優(yōu)化模型，并建立二值優(yōu)化問題。

定義3子任務(wù)節(jié)點(diǎn)ωp和霧網(wǎng)絡(luò)節(jié)點(diǎn)vq的映射關(guān)系如下：當(dāng)xωpvq=1時(shí)，ωp映射為vq；當(dāng)xωpvq=0時(shí)，ωp不會(huì)映射為vq，則xωpvq滿足：

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

(14)

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

(15)

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

(16)

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

T(G)=F(X)。

(17)

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

(18)

(19)

則能耗約束下，圖G～圖U的最優(yōu)映射關(guān)系建模如下：

X=argmin(F(X))

(20)

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

3 BPSO算法

(21)

(22)

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

(23)

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

(24)

(25)

本算法的適應(yīng)度函數(shù)如式(26)：

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

(26)

綜上所述，在求解上述時(shí)延優(yōu)化模型時(shí)，BPSO算法的具體步驟如算法1所示。

算法1 BPSO算法1. fori=1:M do2. 初始化粒子的速度與位置3. 通過式(29)計(jì)算粒子適應(yīng)度值4. 設(shè)置當(dāng)前位置為粒子最佳位置pbest5. 通過比較得出全局最優(yōu)位置gbest6. end for7. fork=1:Nmax do8. fori=1:M do9. 通過式(23)～式(25)更新粒子的速度和位置10.通過式(26)計(jì)算粒子適應(yīng)度值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 仿真實(shí)驗(yàn)及分析

圖3 仿真所用任務(wù)圖Fig.3 Task graph for simulation

考慮到WSN一般通過飛機(jī)等形式隨機(jī)投放到監(jiān)測(cè)區(qū)域內(nèi)，本次仿真利用Matlab隨機(jī)生成網(wǎng)絡(luò)拓樸圖，如圖4所示。

圖4 仿真所用網(wǎng)絡(luò)拓樸圖Fig.4 Network topology used in simulation

仿真平臺(tái)為Matlab，所用參數(shù)均參照文獻(xiàn)[16-17,20-24]設(shè)置，如表1所示。其中，fc為云服務(wù)器計(jì)算能力，Rc為云霧鏈路的數(shù)據(jù)傳輸速率，ffog為霧計(jì)算節(jié)點(diǎn)的計(jì)算能力，Rfog為霧鏈路數(shù)據(jù)傳輸速率，emax為單個(gè)節(jié)點(diǎn)的最大能量。

表1 系統(tǒng)參數(shù)

由表1可知，單個(gè)節(jié)點(diǎn)的最大能量為[0.5,2] J，結(jié)合圖4可知，霧網(wǎng)絡(luò)的最大能量Emax為[6,24] J。BPSO算法的基本參數(shù)為：種群規(guī)模M=500，最大迭代次數(shù)Nmax=1000，加速因子γ1=γ2=1，慣性權(quán)重ρ=1。

4.1 云計(jì)算與路徑計(jì)算時(shí)延性能對(duì)比

為驗(yàn)證本文所提出的路徑計(jì)算方法的有效性，對(duì)比了3種不同業(yè)務(wù)的云計(jì)算和路徑計(jì)算的時(shí)延性能，并用Emax=6 J與Emax=24 J兩條線表示路徑計(jì)算的時(shí)延性能范圍。仿真結(jié)果如圖5所示。

(a) gzip ASCII壓縮任務(wù)

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

同時(shí)，隨著任務(wù)復(fù)雜度不斷增加，路徑計(jì)算的任務(wù)處理時(shí)延急劇增加，而云計(jì)算增長(zhǎng)緩慢。原因是任務(wù)復(fù)雜度僅影響計(jì)算時(shí)延，而云計(jì)算的計(jì)算能力較強(qiáng)，因此任務(wù)復(fù)雜度的變化對(duì)云計(jì)算影響甚微；而匯聚節(jié)點(diǎn)計(jì)算能力較弱，因此當(dāng)任務(wù)復(fù)雜度增加時(shí)，路徑計(jì)算的時(shí)延急劇增加，并且有逼近云計(jì)算的趨勢(shì)。據(jù)此可推測(cè)，當(dāng)處理更復(fù)雜的任務(wù)時(shí)，云計(jì)算的時(shí)延性能將優(yōu)于路徑計(jì)算。因此，路徑計(jì)算適合處理復(fù)雜度較低的任務(wù)，而云計(jì)算適合處理復(fù)雜度較高的任務(wù)。

4.2 BPSO算法與其他算法時(shí)延性能比較

為驗(yàn)證BPSO算法在解決路徑計(jì)算方案的有效性，比較了處理多種任務(wù)時(shí)BPSO算法與加權(quán)輪轉(zhuǎn)法(WRR)、隨機(jī)動(dòng)態(tài)算法(Pick-KX)以及貪婪負(fù)載均衡算法(Greedy-LB)的任務(wù)處理時(shí)延，如圖6和圖7所示。

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

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

這是因?yàn)镻ick-KX算法隨機(jī)選取霧網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行映射，并未考慮節(jié)點(diǎn)的計(jì)算能力；WRR算法根據(jù)節(jié)點(diǎn)的計(jì)算能力大小關(guān)系進(jìn)行映射，Greedy-LB算法通過選取當(dāng)前負(fù)載最小的節(jié)點(diǎn)進(jìn)行映射，但WRR和Greedy-LB均未考慮網(wǎng)絡(luò)邊的傳輸能力，仍不是最優(yōu)；BPSO算法綜合考慮節(jié)點(diǎn)計(jì)算能力和網(wǎng)絡(luò)邊的傳輸能力，可達(dá)到有效降低任務(wù)處理時(shí)延的目標(biāo)。

(a) gzip ASCII壓縮任務(wù)

(a) gzip ASCII壓縮任務(wù)

5 結(jié)論

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