[發明專利]一種無線傳感器任務分配方法

有效

• 申請號: 201711022404.0
• 申請日: 2017-10-27
• 公開（公告）號: CN107820276B
• 公開（公告）日: 2019-09-20
• 發明（設計）人: 張洪光;郭鳳;吳帆;范文浩;劉元安
• 申請（專利權）人: 北京郵電大學
• 主分類號: H04W28/02
• 分類號: H04W28/02;H04W72/04;H04W84/18
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種無線傳感器任務分配方法，其特征在于：

步驟(1)，初始化任務分配方案，選定初始種群規模pop、最大進化代數MaxIt、加強的Pareto進化算法參數以及初始化空的外部檔案A₀，將任務隨機映射到無線傳感器節點上，生成初始種群P₀，根據DAG圖之間的任務通信關系和節點狀態，調整初始的任務分配方案，將有多個后繼任務的當前任務插入路由廣播任務，選擇距離最近的節點作為路由廣播節點，形成種群P₀’，將剩余能量值小于某一設定的閾值e_th的節點標記，不再為其分配任務，并將其替換為其他代表傳感器節點編號的隨機實數；

步驟(2)，根據種群P₀’的實數序列中每個任務分配的節點，結合任務的負載和通信關系以及節點處理速度、故障概率建立動態多目標優化的效用函數，得到任務分配的多目標優化模型；

任務分配的動態多目標優化的效用函數包括的能耗目標函數、時間目標函數以及可靠性目標函數為：

其中，m表示任務個數,n表示傳感器節點個數,e_ij表示第i個任務在第j個節點上的完成的能耗,t_ij表示第i個任務在第j個節點上完成的時間,λ_j為初始化的第j個節點的異構故障概率，表示優化后的任務完成總能耗，表示優化后任務完成的總時間，表示優化后任務完成的總可靠性參數；

步驟(3)，根據傳感器節點數和所有任務完成期限設定動態多目標優化算法中決策變量的約束條件：

其中，N_i表示第i個任務分配到序號為N_i的傳感器節點上，并且N_i屬于正整數，n表示共有n個傳感器節點，為優化方案的任務總完成時間，deadline為系統要求的所有任務完成的最大期限；

步驟(4)，建立動態多目標優化方法的動態環境檢測模型：

具體的，實時獲取任務關系矩陣{r_ij}_m×m、通信負載數組{c_i}_1×m以及計算負載數組{p_i}_1×m，并與原數據進行對比，若發生變化，則檢測到環境發生改變，那么當前的任務分配方案不再是該任務的最佳分配方案，需要重新根據新的任務關系矩陣進行初始化任務分配方案；

其中，任務的關系矩陣的建立為：根據給定的DAG圖之間的優先級關系，轉化為任務的關系矩陣，矩陣大小為m×m的0-1矩陣{r_ij}_m×m，m表示任務數量，r_ij＝1表示任務i的后繼任務為任務j，任務j的前驅任務為任務i，意義為：任務i執行完成后才能執行任務j，有一定的優先級關系；

其中，DAG圖中任務的負載，包括通信負載C和計算負載P，分別用1×m的數組{c_i}_1×m、{p_i}_1×m表示，c_i、p_i分別表示任務i的通信負載和計算負載大小；

步驟(5)，利用動態多目標優化算法對任務分配方案進行更新，具體的步驟為：

步驟(5.1)：計算種群P_t’和外部檔案A_t中的個體的每個適應度值，進行非支配排序，并進行二元錦標賽選擇、交叉、變異，生成子代P_t+1’；

步驟(5.2)：將種群P_t’和外部檔案A_t非支配排序得到的非劣解個體放入A_t+1，A_t+1＝{xⁱ|xⁱ∈P_t∪A_t}，如果A_t+1的大小超過設定的檔案大小C，則修剪A_t+1；如果A_t+1的大小小于C，則將P_t’和A_t中受支配的解加入到A_t+1；

步驟(5.3)：檢測環境是否發生變化，若沒有則執行步驟(5.4)；否則，則將當前A_t+1中的非劣等級為1的解輸出到當前時刻τ的Pareto解集L(τ)中，并更新剩余能量值，然后根據新的任務重新初始化方案，跳轉到步驟(5.1)；

步驟(5.4)：判斷是否達到最大進化代數MaxIt，如果沒有，則令t＝t+1，并轉到步驟(5.1)；否則，將外部檔案A_t+1中非劣等級為1的所有個體輸出到Pareto最優解集，停止運行；

步驟(6)，通過計算任務分配的能耗均衡度，從Pareto最優解集L(τ)中選擇能耗最均衡的解作為最佳的任務分配方案l，并動態更新每個時刻的傳感器節點剩余能量值，最后得出一組隨時間變化的最優任務分配方案解集：

l表示在τ時刻的最優解，L(τ)是在τ時刻的可行解集合，T表示任務分配的總時間；

具體的，能耗均衡度的計算為：

其中，Deviation(X^*)表示每個節點上消耗的總能耗的方差，值越小表明能量消耗越均衡，即節點上的負載均衡，將此函數作為決策函數，n為被分配的節點的數量，E_j為在節點j上消耗的能量。