[發明專利]無線傳感器低功耗低時延路徑式協同計算方法

有效

• 申請號: 202110038750.8
• 申請日: 2021-01-12
• 公開（公告）號: CN112996073B
• 公開（公告）日: 2022-10-28
• 發明（設計）人: 任智源;王一鳴;程文馳;胡梅霞;陳晨;張海林
• 申請（專利權）人: 西安電子科技大學
• 主分類號: H04W40/02
• 分類號: H04W40/02;H04W40/10;H04W4/38;H04W84/18;H04L45/121;H04L45/00;G06N3/00
• 代理公司: 北京世譽鑫誠專利代理有限公司 11368
• 代理人: 仲伯煊

1.無線傳感器低功耗低時延路徑式協同計算方法，其特征在于，包括以下步驟：

(1)、構建WSN云霧網絡架構；

(2)、制定能耗約束下的任務映射策略：

基于步驟(1)得到的WSN云霧網絡架構，將DAG形式的有向無環圖G映射至無向連通圖U的霧網絡中，并構建有向無環圖G至無向連通圖U的最優映射關系模型；

(3)、利用BPSO算法求解步驟(2)得到的最優映射關系模型，其中：

步驟(1)中的WSN云霧網絡架構自下而上包括感知層、霧計算層、云計算層，其中：

所述感知層由集成有一個或多個類型傳感器的無線傳感器組成，用于對所在部署區域進行監測；

所述霧計算層由多個具備數據處理能力和通信能力的匯聚節點組成，所述匯聚節點與無線傳感器通信互聯，所述霧計算層用于轉發和處理感知層產生的數據；

所述云計算層由多個服務器集群構成，服務器集群通過通信鏈路與匯聚節點通信互聯相連，用于對WSN云霧網絡架構進行監控和管理；

步驟(2)包括以下步驟：

(21)、構建DAG形式的有向無環圖G至無向連通圖U的映射規則模型：

在DAG形式的有向無環圖G至無向連通圖U的映射規則模型中，有向無環圖G＝(Ω，Γ)表示任務模型，定義Ω＝{ω₁,ω₂,…,ω_s,ω_s+1,…,ω_l-1,ω_l|s≥1,l＞s+1}為G的節點集合，其中：

ω₁,ω₂,…,ω_s是s個任務起點，ω_s+1,…,ω_l-1是中間任務節點，ω_l是任務終點；

Γ為G的有向邊集合，定義Φ_↑(ω_i)＝{ω_j|(ω_j,ω_i)∈Γ}為ω_i的前向節點集合；

此外，WSN拓撲圖用無向連通圖U＝(V,K)來表示，定義V＝{ν₁,ν₂,…,ν_s,ν_s+1,…,ν_t-1,ν_t|s≥1,t＞s+1}為U的節點集合，其中ν₁,ν₂,…,ν_s指業務發起節點，ν_s+1,…,ν_t-1為中繼節點，ν_t為與用戶直連的節點；

K為U的邊集合，每條邊均支持雙向數據傳輸，用來表示節點v_i到v_j的最短路徑；

定義為最短路徑集合；

為最短路徑中所經過的數據轉發節點集合；

為從節點v_i到v_j沿最短路徑傳輸單位數據量的時延；

將圖U的網絡邊傳輸速率和節點連接關系作為輸入，通過Floyed算法可求得

有向無環圖G至無向連通圖U的映射規則如下：

定義1.Ω至V的映射規則為ε:Ω→V，且ε需滿足式(1)條件：

ε將Ω的任務起點ω₁,ω₂,…,ω_s映射為V的任務發起節點ν₁,ν₂,…,ν_s；將中間任務節點ω_s+1,…,ω_l-1映射為任意中繼節點ν_s+1,…,ν_t-1；將任務終點ω_l映射為與用戶直連的節點ν_t；

定義2.Γ至P的映射為γ:?！鶳，且γ需滿足式(2)的條件：

γ將集合Γ中的有向邊映射為圖U中的節點ε(ω_i)至ε(ω_j)的最短路徑

(22)、基于步驟(21)得到的映射規則模型構建時延模型：

子任務ω_i在某次映射關系中的時延可以表示為式(3)：

其中：

為進行到子任務ω_i時的累積時延；

為ω_i計算時延；

為節點ε(ω_i)的計算能力；

α為任務計算復雜度系數；

則有向無環圖G的任務處理時延為任務終點ω_l的時延，如式(4)所示：

T(G)＝T(ω_l) (4)

(23)、基于步驟(21)得到的映射規則模型、步驟(22)得到的時延模型構建能耗模型，其中：

網絡節點v_i的能耗等于網絡節點v_i的空閑能耗與活動能耗之和；

(231)、空閑能耗

(2311)映射節點ε(ω_i)的空閑能耗如式(5)所示：

其中，指ε(ω_i)空閑狀態時的功率；

指ε(ω_i)在某次任務中處于空閑狀態的時間；

分別為計算時間、發送數據時間、接收數據時間，并且此三者無重合，其計算公式如式(6)-(8)所示：

由式(5)-(8)得ε(ω_i)的空閑能耗如式(9)：

(2312)轉發節點的空閑能耗如式(10)所示：

可利用式(11)-(12)計算：

由(10)-(12)得的空閑能耗如式(13)所示：

(232)、活動能耗：

活動能耗包括計算能耗和傳輸能耗：

(2321)、計算能耗：

計算能耗僅由映射節點ε(ω_i)產生，如式(14)：

其中k＞0和σ≥2都是正實數，σ和k分別被設置為3和10^-28；

(2322)、傳輸能耗：

映射節點ε(ω_i)的傳輸能耗如式(15)-(16)：

其中，P_T和P_R分別為節點的發送功率和接收功率，因此ε(ω_i)的活動能耗如式(17)：

轉發節點的活動能耗僅包括傳輸能耗，如式(18)：

由式(9)、(17)得，映射節點ε(ω_i)的總能耗如式(19)：

由式(13)、(18)得，轉發節點的總能耗如式(20)：

整個霧網絡的總能耗如式(21)所示：

令整個霧網絡所含有的最大能量為E^max，則在某次任務G內，網絡所產生的能耗需小于等于其最大能耗，如式(22)：

(24)、構建DAG形式的有向無環圖G至無向連通圖U映射規則優化模型——基于步驟(21)-步驟(23)給出DAG形式的有向無環圖G至無向連通圖U的映射規則，優化模型，建立二值優化問題：

定義3.子任務節點ω_p和霧網絡節點v_q的映射關系如下：當時，即為ω_p映射為v_q；當時，ω_p不會映射為v_q，則滿足式(23)：

基于定義3，ω_p至v_q的映射可以構建為l×t的映射矩陣X，如式(24)：

則式(5)所表示的子任務ω_i的時延可表示為式(25)：

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

T(G)＝F(X) (26)

式(19)所表示的映射節點ε(ω_i)的總能耗可表示為式(27)：

式(20)所表示的轉發節點的總能耗可表示為式(28)：

則能耗約束下有向無環圖G至無向連通圖U的最優映射關系建模如下：

X＝argmin(F(X))

步驟(3)中BPSO算法主要用于優化離散空間的約束問題，將粒子的位置限制為0或1，適用于式(29)所提出的二值優化問題：

采用BPSO算法時，粒子群在搜索空間I內移動尋找最好位置，中N_max為迭代次數最大值，M為粒子群規模，n∈{1,2,…,N_max}為迭代次數；

在第n次迭代中，第i個粒子的位置和速度可分別表示為：

式(30)中，Xⁿ(i)∈I，

式(31)中，Vⁿ(i)∈O，

第i個粒子在第n次迭代中，速度更新公式如式(32)：

式(32)中，和分別為粒子局部和全局最優位置，w為慣性權重，γ₁和γ₂為加速因子，β₁和β₂為在區間[0,1]內均勻分布的隨機數；

BPSO算法的位置更新公式如式(33)-(34)：

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

f(X)＝T(G)＝F(X) (35)。