[發(fā)明專利]一種基于啟發(fā)式算法的無線傳感器網(wǎng)絡(luò)任務(wù)分配方法

有效

• 申請?zhí)枺?/td>: 202011026884.X
• 申請日: 2020-09-25
• 公開（公告）號: CN112153594B
• 公開（公告）日: 2021-09-07
• 發(fā)明（設(shè)計）人: 楊嘉琛;倪天蕾;王天應(yīng)
• 申請（專利權(quán)）人: 天津大學
• 主分類號: H04W4/38
• 分類號: H04W4/38
• 代理公司: 天津市北洋有限責任專利代理事務(wù)所 12201
• 代理人: 程毓英

1.一種基于啟發(fā)式算法的無線傳感器網(wǎng)絡(luò)任務(wù)分配方法，包括下列步驟：

第一步，加載任務(wù)模型與無線傳感器網(wǎng)絡(luò)，獲取任務(wù)模型中的任務(wù)數(shù)量與無線傳感器網(wǎng)絡(luò)中的傳感器節(jié)點，用于之后的染色體編碼；

第二步，種群初始化：種群中每一條染色體對應(yīng)著一種任務(wù)分配方案，染色體長度為任務(wù)模型中任務(wù)數(shù)量，節(jié)點存儲的元素為網(wǎng)絡(luò)模型中的傳感器節(jié)點，即染色體第i個節(jié)點存儲傳感器節(jié)點A，代表調(diào)度傳感器節(jié)點A執(zhí)行任務(wù)i；初始化過程為：利用輪盤賭機制優(yōu)先選擇剩余能量多的集群中心作為某一任務(wù)的執(zhí)行傳感器，目的是平衡集群中心的能量負載，避免某一集群中心過早耗盡能量降低網(wǎng)絡(luò)壽命；然后，在傳感器節(jié)點滿足該任務(wù)需求資源的基礎(chǔ)上，用節(jié)點執(zhí)行該任務(wù)產(chǎn)生的能耗以及節(jié)點的剩余能量代表該節(jié)點被選擇的概率，能耗越小，剩余能量越多，節(jié)點被選中執(zhí)行此任務(wù)的概率越大；然后將能耗的倒數(shù)與負載倒數(shù)之和作為個體的適應(yīng)度值，能耗越低，負載越均衡，適應(yīng)度值越高；

第三步，對種群中的個體進行3-1交叉操作，根據(jù)交叉概率選取三條父染色體，產(chǎn)生一條子染色體，并檢查交叉后的子染色體中存不存在能量耗盡的傳感器節(jié)點，若存在則此次交叉無效，重新選取父染色體的交叉點進行交叉，三條父染色體的交叉過程為：選取三條父染色體中相同位置的兩個基因點作為交叉點，將三條父染色體分為九個染色體片段，選擇父染色體中相同片段對應(yīng)分配任務(wù)方案能耗較低的三個片段，組合產(chǎn)生一條新的子染色體；

第四步，進行變異操作：根據(jù)變異概率選擇染色體，從變異節(jié)點開始，重新進行任務(wù)分配，引入信息素濃度來決定傳感器節(jié)點被變異染色體選擇執(zhí)行某子任務(wù)的概率，其公式為：

式中τ(Task_m-Sensor_n)為任務(wù)m與傳感器節(jié)點n對下對應(yīng)的信息素濃度，η(Sensor_n-Task_m)為啟發(fā)因子，能耗越低，傳感器節(jié)點剩余能量越高，啟發(fā)因子越大，SNList為待選傳感器節(jié)點集合，α是信息素濃度權(quán)重，β是啟發(fā)因子權(quán)重；

第五步，計算種群中個體的適應(yīng)度值，進行選擇操作；

第六步，種群初始化以及每次選擇操作完成后，都需更新所有傳感器節(jié)點的信息素濃度，方法為：

上述公式中，τ(Task_m-Sensor_n)_G+1為第G+1代任務(wù)m與傳感器節(jié)點n對下對應(yīng)的信息素濃度，ρ為揮發(fā)系數(shù)，τ(Task_m-Sensor_n)_G為第G代任務(wù)m與傳感器節(jié)點n對下對應(yīng)的信息素濃度，K為種群個體數(shù)，Δτ_i(Task_m-Sensor_n)為第G代任務(wù)m與傳感器節(jié)點n對下對應(yīng)的信息素增量，其與個體適應(yīng)度值fitness成正比，常數(shù)Q為一個個體可以增加的信息素總量；

第七步，重復(fù)第三步到第六步，直至算法達到預(yù)設(shè)的最大進化代數(shù)，輸出最優(yōu)解。

2.根據(jù)權(quán)利要求1所述的方法，其特征在于，第五步具體為：完成交叉和變異之后，計算個體適應(yīng)度值，采用輪盤賭機制選擇被保留的個體，適應(yīng)度越高越容易被保留；另，選擇操作前進行精英保留，即挑選出種群中適應(yīng)度最高的個體直接加入到下一代種群中，保證最優(yōu)解一直存在。