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

在審

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

1.基于Q-learning的改進(jìn)動態(tài)生成樹移動路由算法，其特征在于：包括以下步驟：

S1：參數(shù)設(shè)置：

設(shè)定無線傳感器網(wǎng)絡(luò)監(jiān)測區(qū)S_N為L×L的正方形區(qū)域，移動匯聚節(jié)點(diǎn)在監(jiān)測區(qū)域內(nèi)按照具體運(yùn)動模型運(yùn)動；無線傳感器網(wǎng)絡(luò)在監(jiān)測區(qū)域中隨機(jī)部署N個傳感器節(jié)點(diǎn)，構(gòu)成傳感器節(jié)點(diǎn)集合并記為S＝{s₁,…,s_j,…,s_N}；j＝1,2,…,N；傳感器節(jié)點(diǎn)s_j一旦部署其位置將不再改變，且初始能量相同均為E₀；最大運(yùn)行輪數(shù)為r_max；簇頭選擇期望概率為p；最佳會合點(diǎn)個數(shù)為m；

S2：移動匯聚節(jié)點(diǎn)位置更新區(qū)域的設(shè)置：

根據(jù)步驟S1中最佳會合點(diǎn)個數(shù)為m、傳感器節(jié)點(diǎn)總數(shù)N和網(wǎng)絡(luò)監(jiān)測區(qū)域面積S_N，得到理想的移動匯聚節(jié)點(diǎn)位置更新的橢圓區(qū)域面積S_m；將移動匯聚節(jié)點(diǎn)當(dāng)前時刻的位置作為橢圓的后焦點(diǎn)F₁(C_x(t),C_y(t))，然后根據(jù)移動匯聚節(jié)點(diǎn)當(dāng)前位置的運(yùn)動狀態(tài)信息(位置和速度)，計算得到更新的橢圓區(qū)域的前焦點(diǎn)F₂(C'_x(t),C'_y(t))、半焦距c、半長軸a、半短軸b；

S3：根據(jù)步驟S2中得到的在t時刻橢圓的前后焦點(diǎn)坐標(biāo)分別為F₂(C'_x(t),C'_y(t))和F₁(C_x(t),C_y(t))，結(jié)合在t+Δt時刻移動匯聚節(jié)點(diǎn)的位置坐標(biāo)F₁′(C_x(t+Δt),C_y(t+Δt))，計算在t+Δt時刻橢圓更新閾值T_oval(t+Δt)；當(dāng)T_oval(t+Δt)＝1時，根據(jù)t+Δt時刻移動匯聚節(jié)點(diǎn)的運(yùn)動狀態(tài)構(gòu)建新的橢圓區(qū)域；否則，不重新構(gòu)建橢圓區(qū)域；

S4：將根據(jù)移動匯聚節(jié)點(diǎn)位置更新的橢圓區(qū)域內(nèi)的節(jié)點(diǎn)設(shè)置為會合點(diǎn)：

由步驟S2和S3得到根據(jù)移動匯聚節(jié)點(diǎn)位置更新的橢圓區(qū)域半長軸a，半短軸b，半焦距c，計算會合點(diǎn)選擇閾值T_h(s_j)，當(dāng)T_h(s_j)＝1，節(jié)點(diǎn)s_j加入會合點(diǎn)集合Η；否則，加入非會合點(diǎn)集合Η'；

S5：選擇簇頭：

根據(jù)步驟S4得到非會合點(diǎn)集合Η'，由經(jīng)典分簇算法LEACH，可以計算出節(jié)點(diǎn)s_j的簇頭選擇閾值T(s_j)，s_j∈Η'；每個節(jié)點(diǎn)s_j產(chǎn)生一個分布在[0,1]之間的隨機(jī)數(shù)T_r(s_j)；如果T_r(s_j)小于簇頭選擇閾值T(s_j)，則節(jié)點(diǎn)s_j在當(dāng)前輪當(dāng)選為簇頭，加入到簇頭集合C；否則，節(jié)點(diǎn)s_j為非簇頭節(jié)點(diǎn)，加入到非簇頭集合C′；

S6：簇的形成：

根據(jù)步驟S5得到簇頭集合C，每個簇頭在整個監(jiān)測區(qū)域廣播自己成為簇頭的消息，非簇頭節(jié)點(diǎn)接受到消息后，計算非簇頭節(jié)點(diǎn)s_t到每個簇頭節(jié)點(diǎn)c_k的距離集合將集合D_tk元素最小值對應(yīng)的k記為離非簇頭節(jié)點(diǎn)s_t最近的簇頭，并將它們之間的距離記為d_{tk_min}，則該非簇頭節(jié)點(diǎn)s_t加入離自身最近的簇頭節(jié)點(diǎn)c_k所在的簇，t∈C′；

S7：構(gòu)建會合點(diǎn)選擇的鄰接矩陣：

簇頭節(jié)點(diǎn)在把數(shù)據(jù)發(fā)送給移動匯聚節(jié)點(diǎn)過程中，可以通過無線傳感器網(wǎng)絡(luò)中其他簇頭節(jié)點(diǎn)轉(zhuǎn)發(fā)給會合點(diǎn)，會合點(diǎn)收集數(shù)據(jù)并處理后，發(fā)送給移動匯聚節(jié)點(diǎn)，通過構(gòu)建鄰接矩陣的方法，來更好的表示移動匯聚節(jié)點(diǎn)、會合點(diǎn)和簇頭節(jié)點(diǎn)之間的關(guān)系；

S8：基于Q-learning的動態(tài)生成樹的構(gòu)建：

S8.1：每個簇頭節(jié)點(diǎn)可以選擇的下一跳節(jié)點(diǎn)為其他簇頭節(jié)點(diǎn)或會合點(diǎn)，每個會合點(diǎn)可以選擇的下一跳節(jié)點(diǎn)為移動匯聚節(jié)點(diǎn)，據(jù)此構(gòu)建獎勵函數(shù)R；

S8.2：獎勵函數(shù)R構(gòu)建完成后，通過選擇不同的下一跳節(jié)點(diǎn)，得到不同的回報值；期望的控制策略是為每個節(jié)點(diǎn)選擇最恰當(dāng)?shù)南乱惶?jié)點(diǎn)，通過時間的積累，進(jìn)行循環(huán)迭代，從而構(gòu)建多跳傳輸策略矩陣Q_Table，在初始狀態(tài)時，多跳傳輸策略矩陣Q_Table為一個全0的矩陣，Q(s,a)表示每個節(jié)點(diǎn)選擇下一跳節(jié)點(diǎn)的效果，s為當(dāng)前狀態(tài)節(jié)點(diǎn)，a為下一跳可選擇的節(jié)點(diǎn)，Q(s,a)在迭代中更新；

S8.3：重復(fù)執(zhí)行步驟S8.1和步驟S8.2，進(jìn)行多次迭代，更新多跳傳輸策略矩陣Q_Table中的Q(s,a)，然后為每個節(jié)點(diǎn)選取最大的Q(s,a)所對應(yīng)的下一跳節(jié)點(diǎn)，即π^*＝argmax_aQ(s,a)，直到無線傳感器網(wǎng)絡(luò)的所有節(jié)點(diǎn)都連接到路徑樹上，則路徑樹構(gòu)建完成；

S9：根據(jù)S8構(gòu)建的路徑樹，每個簇的簇內(nèi)節(jié)點(diǎn)將自身監(jiān)測到的數(shù)據(jù)發(fā)送給所在簇的簇頭節(jié)點(diǎn)，簇頭節(jié)點(diǎn)接收多個簇成員節(jié)點(diǎn)傳輸?shù)臄?shù)據(jù)并對這些數(shù)據(jù)進(jìn)行融合處理；

S10：簇頭節(jié)點(diǎn)將自身融合處理后的數(shù)據(jù)發(fā)送給自己的下一跳節(jié)點(diǎn)；

S11：重復(fù)步驟S2至步驟S11，直到達(dá)到預(yù)先設(shè)定的運(yùn)行輪數(shù)r＝r_max或全部節(jié)點(diǎn)剩余能量為0焦耳。