[發(fā)明專利]一種無線傳感器網(wǎng)絡(luò)及其節(jié)點任務(wù)遷移方法

在審

• 申請?zhí)枺?/td>: 201410725181.4
• 申請日: 2015-08-03
• 公開（公告）號: CN104506576A
• 公開（公告）日: 2015-07-29
• 發(fā)明（設(shè)計）人: 王峰;馬慶功;朱輪;田中燕;石林;李寧
• 申請（專利權(quán)）人: 常州大學
• 主分類號: H04L29/08
• 分類號: H04L29/08;H04W24/04;H04W84/18
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術(shù)領(lǐng)域

本發(fā)明屬于無線多媒體傳感器網(wǎng)絡(luò)技術(shù)領(lǐng)域，特別涉及一種基于遺傳算法和積分激勵機制的節(jié)點任務(wù)遷移方法。

背景技術(shù)

隨著無線傳感器網(wǎng)絡(luò)應(yīng)用實時性要求越來越高，節(jié)點上分配的任務(wù)在時間期限內(nèi)成功完成是保證整個應(yīng)用實時性的重要條件。但在無線傳感器網(wǎng)絡(luò)環(huán)境中，無線節(jié)點很容易因為能量耗竭或受到惡意節(jié)點的攻擊而失效，所以當一個正在執(zhí)行任務(wù)的節(jié)點即將失效時，或是已經(jīng)死亡時，如何找到一種能夠快速、低耗又成功率高的任務(wù)遷移方法，將失效節(jié)點上的任務(wù)遷移到其他節(jié)點上去是非常必要的，這可以在個別節(jié)點失效的情況下，保證任務(wù)的順利執(zhí)行。

發(fā)明內(nèi)容

與現(xiàn)有技術(shù)相比，本發(fā)明的網(wǎng)關(guān)節(jié)點基于遺傳算法對相互依賴的子任務(wù)進行分配，并將積分激勵機制引入到分配算法中，從而平衡了各節(jié)點負載，延長網(wǎng)絡(luò)生命周期；在節(jié)點失效的情況下，可將失效節(jié)點上未完成的任務(wù)遷移到其他合適的節(jié)點上，保證了任務(wù)在時間期限內(nèi)完成，提高了任務(wù)分配效率及完成質(zhì)量。同時，通過改進的遺傳算法，改善了算法的空間探索能力，加快了進化速度，能在較短時間內(nèi)獲得節(jié)點的分配方案，提高了無線傳感器網(wǎng)絡(luò)的反應(yīng)時間。

本發(fā)明提供了一種無線傳感器網(wǎng)絡(luò)，包括一個網(wǎng)關(guān)節(jié)點和多個普通節(jié)點，其特征在于：

所述網(wǎng)關(guān)節(jié)點和普通節(jié)點以無線多跳的方式鏈接而成，網(wǎng)關(guān)節(jié)點具有電力供應(yīng)，而普通節(jié)點沒有電力供應(yīng)，普通節(jié)點隨機布置，一旦布置好后，就不再移動。

本發(fā)明還涉及一種無線傳感器網(wǎng)絡(luò)中基于遺傳算法的任務(wù)分配方法，其特征在于：

步驟一、網(wǎng)關(guān)節(jié)點接收一個應(yīng)用指令，該指令中的應(yīng)用可以被分解成多個相互依賴的子任務(wù)，用DAG任務(wù)圖G＝(T,E)來描述，DAG任務(wù)圖的頂點用集合T＝{T₁,T₂,...,T_n}表示，代表需要執(zhí)行的子任務(wù)，其中n表示子任務(wù)的個數(shù)，每個子任務(wù)有一個時間限制deadline，子任務(wù)的執(zhí)行必須在指定的deadline之前完成，DAG任務(wù)圖的邊用E＝{E₁,E₂,...,E_g}表示，代表子任務(wù)之間的數(shù)據(jù)依賴或控制依賴，其中g(shù)表示DAG任務(wù)圖的邊的個數(shù)，如果從頂點T_i到頂點T_j存在一條有向邊E_ij，則說明子任務(wù)T_j的執(zhí)行需要子任務(wù)T_i的輸出數(shù)據(jù)；網(wǎng)關(guān)節(jié)點采用遺傳算法對DAG任務(wù)圖中的子任務(wù)進行管理和分配，具體方法如下：

(1)隨機生成分配方案即染色體，構(gòu)建染色體集合S

用S＝{C₁,C₂,…,C_x}表示所有的分配方案即染色體的集合，其中C是一候選方案，x是所有候選方案的數(shù)目；網(wǎng)關(guān)節(jié)點隨機生成x個分配方案，每個分配方案就是一個染色體，每個染色體用3×n矩陣C來表示，n表示DAG任務(wù)圖中的任務(wù)總數(shù)，矩陣C第一行中的(T₁,...T_i...T_n)為待分配的子任務(wù)，其從左到右的順序根據(jù)DAG任務(wù)圖中任務(wù)執(zhí)行順序決定，矩陣C第二行(V₁,...V_j...V_m)代表子任務(wù)映射的節(jié)點，矩陣C第三行(ω₁,...ω_i...ω_n)代表子任務(wù)的計算量，染色體矩陣C如下：