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

有效

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

本發(fā)明涉及一種基于啟發(fā)式算法的無線傳感器網(wǎng)絡(luò)任務(wù)分配方法，包括下列步驟：加載任務(wù)模型與無線傳感器網(wǎng)絡(luò)，獲取任務(wù)模型中的任務(wù)數(shù)量與無線傳感器網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)，用于之后的染色體編碼；種群初始化：種群中每一條染色體對應(yīng)著一種任務(wù)分配方案，染色體長度為任務(wù)模型中任務(wù)數(shù)量，節(jié)點(diǎn)存儲(chǔ)的元素為網(wǎng)絡(luò)模型中的傳感器節(jié)點(diǎn)，即染色體第i個(gè)節(jié)點(diǎn)存儲(chǔ)傳感器節(jié)點(diǎn)A，代表調(diào)度傳感器節(jié)點(diǎn)A執(zhí)行任務(wù)i；對種群中的個(gè)體進(jìn)行3?1交叉操作；進(jìn)行變異操作；計(jì)算種群中個(gè)體的適應(yīng)度值，進(jìn)行選擇操作；進(jìn)行信息素濃度更新；輸出最優(yōu)解。

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

本發(fā)明屬于物聯(lián)網(wǎng)領(lǐng)域，涉及一種基于啟發(fā)式算法的無線傳感器網(wǎng)絡(luò)任務(wù)分配方法。

背景技術(shù)

傳感器網(wǎng)絡(luò)由大量形體較小、能源受限且具備計(jì)算和無線通信能力的傳感器節(jié)點(diǎn)組成，這些傳感器節(jié)點(diǎn)可以感知來自環(huán)境的信息，處理感測到的數(shù)據(jù)并傳送到網(wǎng)絡(luò)中的其它裝置。傳感器網(wǎng)絡(luò)目前廣泛應(yīng)用于括環(huán)境監(jiān)測、對象跟蹤、森林防火、戰(zhàn)場態(tài)勢監(jiān)控等領(lǐng)域。因此，傳感器網(wǎng)絡(luò)得到了科學(xué)界和工業(yè)界的越來越多的研究和關(guān)注。部署無線傳感器網(wǎng)絡(luò)通常是為了完成一項(xiàng)復(fù)雜的任務(wù)，為了完成任務(wù)，無線傳感器網(wǎng)絡(luò)需要消耗大量能量來收集信息、處理數(shù)據(jù)和傳播數(shù)據(jù)。但是無線傳感器網(wǎng)絡(luò)的組成部分—傳感器節(jié)點(diǎn)是一個(gè)用電池供電的小型、低成本設(shè)備，單個(gè)傳感器節(jié)點(diǎn)資源有限，只能執(zhí)行相對簡單的操作。因此為了成功完成任務(wù)，網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)應(yīng)該協(xié)同工作，這就需要我們把復(fù)雜的任務(wù)分解成低資源需求的子任務(wù)，保證傳感器節(jié)點(diǎn)的資源足以完成子任務(wù)。傳感器節(jié)點(diǎn)有限的計(jì)算能力和能量儲(chǔ)備限制了其獨(dú)立完成任務(wù)的能力，因此合理的任務(wù)分配對提升網(wǎng)絡(luò)性能和延長網(wǎng)絡(luò)壽命有著至關(guān)重要的作用。

啟發(fā)式算法可以有效靈活的處理復(fù)雜問題，因此可以解決無線傳感器網(wǎng)絡(luò)任務(wù)分配問題，啟發(fā)式算法包括遺傳算法，蟻群算法，模擬退火法和粒子群算法。啟發(fā)式算法能保證小規(guī)模場景下根據(jù)給定的約束條件找到問題的最優(yōu)解，但是大規(guī)模場景下啟發(fā)式算法收斂較慢并且同樣容易出現(xiàn)提前收斂現(xiàn)象，不能保證所得解為全局最優(yōu)解，想要提升解的質(zhì)量就要擴(kuò)大算法的搜索空間，這使收斂速度更加緩慢，大大降低了算法效率。因此，優(yōu)化啟發(fā)式算法解決無線傳感器網(wǎng)絡(luò)任務(wù)分配問題是十分必要的。

融合算法是優(yōu)化啟發(fā)式算法的有效途徑之一，融合算法結(jié)合不同啟發(fā)式算法的特點(diǎn)，在不同階段以不同的方式取搜索解，在加快收斂速度的同時(shí)提高了找到最優(yōu)解的可能性。

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

本發(fā)明提出了一種使用融合啟發(fā)式算法進(jìn)行無線傳感器網(wǎng)絡(luò)任務(wù)分配方法，將遺傳算法和蟻群算法融合的融合算法來解決無線傳感器網(wǎng)絡(luò)任務(wù)分配問題。技術(shù)方案如下：

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

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

第二步，種群初始化：種群中每一條染色體對應(yīng)著一種任務(wù)分配方案，染色體長度為任務(wù)模型中任務(wù)數(shù)量，節(jié)點(diǎn)存儲(chǔ)的元素為網(wǎng)絡(luò)模型中的傳感器節(jié)點(diǎn)，即染色體第i個(gè)節(jié)點(diǎn)存儲(chǔ)傳感器節(jié)點(diǎn)A，代表調(diào)度傳感器節(jié)點(diǎn)A執(zhí)行任務(wù)i；

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

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