[發(fā)明專利]基于Q-learning的改進(jìn)動(dòng)態(tài)生成樹(shù)路由算法

在審

• 申請(qǐng)?zhí)枺?/td>: 202210867163.4
• 申請(qǐng)日: 2022-07-22
• 公開(kāi)（公告）號(hào): CN115022940A
• 公開(kāi)（公告）日: 2022-09-06
• 發(fā)明（設(shè)計(jì)）人: 魏倩;張夢(mèng);周林;白可
• 申請(qǐng)（專利權(quán)）人: 河南大學(xué)
• 主分類號(hào): H04W40/32
• 分類號(hào): H04W40/32;H04W40/10;H04W84/18
• 代理公司: 鄭州聯(lián)科專利事務(wù)所(普通合伙) 41104
• 代理人: 劉建芳

本發(fā)明提供了基于Q?learning的改進(jìn)動(dòng)態(tài)生成樹(shù)路由算法，包含以下步驟：采用Q?learning算法框架，首先，構(gòu)建移動(dòng)匯聚節(jié)點(diǎn)、會(huì)合點(diǎn)、簇頭之間互相連接關(guān)系的鄰接矩陣；其次，通過(guò)考慮節(jié)點(diǎn)間數(shù)據(jù)傳輸能耗和剩余能量，構(gòu)建獎(jiǎng)勵(lì)函數(shù)；最后，通過(guò)選擇不同的下一跳節(jié)點(diǎn)，得到不同的回報(bào)值，選擇回報(bào)值最大的下一跳節(jié)點(diǎn)，從而構(gòu)建簇頭、會(huì)合點(diǎn)、移動(dòng)匯聚節(jié)點(diǎn)之間的動(dòng)態(tài)多跳傳輸路徑樹(shù)，重復(fù)上述過(guò)程，直至全部節(jié)點(diǎn)死亡。本發(fā)明綜合考慮了移動(dòng)匯聚節(jié)點(diǎn)的移動(dòng)特性、節(jié)點(diǎn)的剩余能量、傳輸路徑能耗等因素，延長(zhǎng)了網(wǎng)絡(luò)壽命、提高了數(shù)據(jù)傳輸?shù)姆€(wěn)定性、節(jié)省了網(wǎng)絡(luò)資源、均衡了網(wǎng)絡(luò)負(fù)載。

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

本發(fā)明屬于無(wú)線傳感器網(wǎng)絡(luò)通信技術(shù)領(lǐng)域，具體基于Q-learning的改進(jìn)動(dòng)態(tài)生成樹(shù)路由算法。

背景技術(shù)

無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks，WSNs)主要是由成本低廉、數(shù)目龐大的微型傳感器節(jié)點(diǎn)采用協(xié)作互聯(lián)、自組織的方式構(gòu)成的通信網(wǎng)絡(luò)，具有部署簡(jiǎn)單、可靠性高等特點(diǎn)，這些節(jié)點(diǎn)通常以有限的能量大量且高密度的部署。在WSNs中，傳感器節(jié)點(diǎn)的能量是有限的，位置是隨機(jī)部署的，所以無(wú)法及時(shí)進(jìn)行補(bǔ)充能量或更換電池，一旦節(jié)點(diǎn)的能量耗盡，便不能再參與網(wǎng)絡(luò)數(shù)據(jù)的收集與傳輸，這將會(huì)導(dǎo)致網(wǎng)絡(luò)節(jié)點(diǎn)拓?fù)浣Y(jié)構(gòu)改變、監(jiān)測(cè)性能下降以及網(wǎng)絡(luò)生存周期降低。因此，減少網(wǎng)絡(luò)能耗一直是無(wú)線傳感器網(wǎng)絡(luò)路由算法研究的熱點(diǎn)。

無(wú)線傳感器網(wǎng)絡(luò)具有各種應(yīng)用，如偏遠(yuǎn)地區(qū)的洪水和火災(zāi)檢測(cè)、交通監(jiān)控、空中交通管制等。傳感器共同從周圍環(huán)境中收集環(huán)境條件信息，例如溫度、壓力和濕度，并將其轉(zhuǎn)發(fā)到靜態(tài)數(shù)據(jù)接收器。在許多情況下，由于節(jié)點(diǎn)部署在偏遠(yuǎn)和危險(xiǎn)的區(qū)域，收集傳感器節(jié)點(diǎn)監(jiān)測(cè)到的數(shù)據(jù)變得困難，而移動(dòng)匯聚節(jié)點(diǎn)(Mobile Sink)的引入有效地緩解了上述問(wèn)題。因此，引入移動(dòng)匯聚節(jié)點(diǎn)后如何節(jié)省網(wǎng)絡(luò)資源、延長(zhǎng)網(wǎng)絡(luò)壽命、降低網(wǎng)絡(luò)數(shù)據(jù)時(shí)延成為了一項(xiàng)重要的研究課題。WSN中傳感器節(jié)點(diǎn)數(shù)據(jù)往往通過(guò)多跳的方式發(fā)送至匯聚(Sink)節(jié)點(diǎn)，如果匯聚節(jié)點(diǎn)位置是固定的，與它距離較近的部分節(jié)點(diǎn)往往會(huì)承擔(dān)更多的轉(zhuǎn)發(fā)任務(wù)。隨著時(shí)間的推移，這些節(jié)點(diǎn)會(huì)因耗能較多將率先死亡，從而產(chǎn)生“能量空洞”的問(wèn)題。移動(dòng)匯聚節(jié)點(diǎn)可以用來(lái)解決“能量空洞”的問(wèn)題。

許多學(xué)者已經(jīng)針對(duì)WSN提出和開(kāi)發(fā)了許多節(jié)能路由協(xié)議，最經(jīng)典的分簇路由算法是Heinzelman等人提出的低功耗自適應(yīng)分簇路由協(xié)議(Low Energy Adaptive ClusteringHierarchy，LEACH)，該協(xié)議首次提出了執(zhí)行過(guò)程分“輪”和網(wǎng)絡(luò)節(jié)點(diǎn)分“簇”的思想。LEACH將整個(gè)過(guò)程劃分為若干輪，每輪包含兩個(gè)階段：設(shè)置階段和穩(wěn)態(tài)階段。在設(shè)置階段進(jìn)行簇頭的選擇和分簇，即簇的建立階段，其中簇頭的選擇根據(jù)閾值隨機(jī)選擇，分簇是先確定簇頭集合和非簇頭集合，然后簇頭節(jié)點(diǎn)廣播自己成為簇頭的消息，非簇頭節(jié)點(diǎn)選擇它接收到信號(hào)最強(qiáng)的那個(gè)簇頭，也即是非簇頭節(jié)點(diǎn)加入距離最近的簇頭，這樣建立一個(gè)個(gè)簇。在穩(wěn)態(tài)階段進(jìn)行數(shù)據(jù)的收集與傳輸，簇內(nèi)成員將自身監(jiān)測(cè)到的數(shù)據(jù)發(fā)送給相應(yīng)的簇頭，簇頭將接收到的數(shù)據(jù)進(jìn)行融合處理，然后將融合后的數(shù)據(jù)發(fā)送給匯聚節(jié)點(diǎn)。LEACH算法在一定程度上節(jié)約了網(wǎng)絡(luò)能耗、延長(zhǎng)了網(wǎng)絡(luò)壽命。

經(jīng)典的LEACH算法為分簇路由算法提供了基本的框架，為無(wú)線傳感器網(wǎng)絡(luò)能量?jī)?yōu)化提供了很好的思路。但是在現(xiàn)存的分簇路由算法中，仍存在以下問(wèn)題：

1，移動(dòng)匯聚節(jié)點(diǎn)需要頻繁地將新的位置信息告知傳感器節(jié)點(diǎn)，導(dǎo)致傳感器節(jié)點(diǎn)消耗過(guò)多能量；

2，移動(dòng)匯聚節(jié)點(diǎn)的移動(dòng)性導(dǎo)致網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)改變、傳感器節(jié)點(diǎn)能耗不均以及數(shù)據(jù)延遲；

3，簇頭節(jié)點(diǎn)通過(guò)單跳方式向移動(dòng)匯聚節(jié)點(diǎn)發(fā)送數(shù)據(jù)時(shí)，距離移動(dòng)匯聚節(jié)點(diǎn)較遠(yuǎn)的部分簇頭，容易出現(xiàn)過(guò)早死亡的情況。

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

本發(fā)明的目的是提供一種基于Q-learning的改進(jìn)動(dòng)態(tài)生成樹(shù)路由算法，能夠延長(zhǎng)網(wǎng)絡(luò)壽命、提高數(shù)據(jù)傳輸?shù)姆€(wěn)定性、節(jié)省網(wǎng)絡(luò)資源、均衡網(wǎng)絡(luò)負(fù)載。

本發(fā)明解決其技術(shù)問(wèn)題的技術(shù)方案為：基于Q-learning的改進(jìn)動(dòng)態(tài)生成樹(shù)路由算法，包括以下步驟：