基于Double Deep Q-learning的無線通信節(jié)點(diǎn)覆蓋優(yōu)化

李忠濤

（中國電子科技集團(tuán)公司第五十四研究所 河北省石家莊市 050081）

1 引言

隨著通信與信息采集技術(shù)的發(fā)展，水面無線通信與水下目標(biāo)采集越來越受到各國的重視，但是由于水面無線通信節(jié)點(diǎn)受限于天線高度、海浪遮擋等因素影響，導(dǎo)致通信距離較短，信息采集范圍嚴(yán)重受限。因此，利用空中移動(dòng)無線通信節(jié)點(diǎn)遍歷水面無線通信節(jié)點(diǎn)進(jìn)行信息采集成為重要遠(yuǎn)程水面無線通信與信息采集手段。應(yīng)用場景示意圖見圖1。

無線通信節(jié)點(diǎn)通過無線進(jìn)行數(shù)據(jù)傳輸，具有一定的通信半徑。利用節(jié)點(diǎn)通信半徑的優(yōu)勢，以最小化移動(dòng)空中通信節(jié)點(diǎn)的移動(dòng)路徑為目標(biāo)，尋找監(jiān)測點(diǎn)和相應(yīng)的移動(dòng)路徑，便可以達(dá)到縮短覆蓋時(shí)間與節(jié)約能耗的目的。

本文中擬采用Double Deep Q-learning模型進(jìn)行算法設(shè)計(jì)，該算法是強(qiáng)化學(xué)習(xí)中的一種 values-based 算法，實(shí)現(xiàn)一種神經(jīng)網(wǎng)絡(luò)模型來代替表格 Q-Table，解決了系統(tǒng)狀態(tài)過多導(dǎo)致的Q-Table過大問題。在這個(gè)網(wǎng)絡(luò)模型中我們可以為空中通信節(jié)點(diǎn)的每個(gè)狀態(tài)找到一個(gè)好的動(dòng)作，以得到最優(yōu)路徑。通過不斷學(xué)習(xí)，可以得到優(yōu)化的DDQN模型，通過該模型引導(dǎo)空中無線通信節(jié)點(diǎn)移動(dòng)路徑，以最小代價(jià)實(shí)現(xiàn)水面通信節(jié)點(diǎn)覆蓋。

2 通信網(wǎng)絡(luò)的尋路算法

2.1 Double Deep Q-learning模型

Deep Q-learning（DQN）是基于Q-learning演變過來的。Q-learning使用Q-Table來儲存state與action之間的q值。如果在環(huán)境中，State很多，然后Agent的動(dòng)作也很多，那么毋庸置疑Q-table將會變得很大很大（比如說下圍棋），又或者說如果環(huán)境的狀態(tài)是連續(xù)值而不是離散值，盡管我們可以將連續(xù)值進(jìn)行離散化，但是又可能會導(dǎo)致Q-table變得龐大，因此在DQN中我們使用神經(jīng)網(wǎng)絡(luò)來代替Q-Table，如圖2所示。

DQN 算法的兩個(gè)最重要的特點(diǎn)是目標(biāo)網(wǎng)絡(luò) (target network) 和經(jīng)驗(yàn)回顧 (experience replay)。

（1）目標(biāo)網(wǎng)絡(luò)的作用其實(shí)是一種打亂相關(guān)性的機(jī)制，使用目標(biāo)網(wǎng)絡(luò)機(jī)制會使得DQN中出現(xiàn)兩個(gè)結(jié)構(gòu)完全相同但是參數(shù)卻不同的網(wǎng)絡(luò)，預(yù)測Q估計(jì)的網(wǎng)絡(luò)MainNet使用的是最新的參數(shù)，而預(yù)測Q現(xiàn)實(shí)的神經(jīng)網(wǎng)絡(luò)TargetNet參數(shù)使用的卻是很久之前的，TargetNet根據(jù)LossFunction更新MainNet的參數(shù)，每經(jīng)過一定次數(shù)的迭代，將MainNet的參數(shù)復(fù)制給TargetNet。引入TargetNet后，在一段時(shí)間里目標(biāo)Q值是保持不變的，一定程度降低了當(dāng)前Q值和目標(biāo)Q值的相關(guān)性，提高了算法穩(wěn)定性。

（2）DQN 算法中Q-learning與深度神經(jīng)網(wǎng)絡(luò)結(jié)合時(shí)帶來一個(gè)問題就是深度神經(jīng)網(wǎng)絡(luò)要求每個(gè)樣本之間互相獨(dú)立，而Q-learning的每一個(gè)樣本當(dāng)前狀態(tài)的狀態(tài)值是依賴后面的狀態(tài)返回值的。

經(jīng)驗(yàn)回顧就很好的解決這個(gè)問題，它把Q-learning產(chǎn)生的樣本存儲起來然后神經(jīng)網(wǎng)絡(luò)使用時(shí)隨機(jī)選取打亂樣本之間的相關(guān)性。

DQN 使用的目標(biāo)就是：

其中Rt+1表示成當(dāng)前s采取a后的即時(shí)r，加上折價(jià)γ后的最大reward max(Q(st+1,a)。

圖1：應(yīng)用場景示意圖

圖2：算法示意圖

圖3：較差路徑示意圖

DQN 中使用 max 操作選取同樣的值來進(jìn)行選擇和衡量一個(gè)行動(dòng)。這實(shí)際上更可能導(dǎo)致最后結(jié)果選擇過高的估計(jì)值，從而導(dǎo)致過于樂觀的估計(jì)。為了避免這種情況的出現(xiàn)，Double Deep Q-learning（DDQN）被提出。在Double Q-Learning算法里面，有兩個(gè)價(jià)值函數(shù)(value function)，一個(gè)用來選擇動(dòng)作（當(dāng)前狀態(tài)的策略），一個(gè)用來評估當(dāng)前狀態(tài)的價(jià)值。這兩個(gè)價(jià)值函數(shù)的參數(shù)分別記做θ和 θ′ 。算法的使用目標(biāo)如下：

本文中我們將運(yùn)用DDQN模型來尋找空中無線通信節(jié)點(diǎn)遍歷與水面無線通信節(jié)點(diǎn)進(jìn)行通信的最優(yōu)路徑。

2.2 整體模型結(jié)構(gòu)。

算法設(shè)計(jì)如下：

2.2.1 模型環(huán)境設(shè)計(jì)

在二維平面中隨機(jī)分布N個(gè)檢測圓。圓心為待通信的水面通信節(jié)點(diǎn)，檢測圓即為水面通信節(jié)點(diǎn)的通信范圍（當(dāng)空中通信節(jié)點(diǎn)與檢測圓相交時(shí)兩者通信完成），每個(gè)檢測圓我們設(shè)置均勻分布的四個(gè)監(jiān)測點(diǎn)（Ji_o；i為圓的編號，o為監(jiān)測點(diǎn)的編號）。

2.2.2 狀態(tài)空間

圖4：最優(yōu)路徑示意圖1

圖5：最優(yōu)路徑示意圖2

本文尋路問題為空中通信節(jié)點(diǎn)所找的路徑即為空中無線通信節(jié)點(diǎn)依次進(jìn)行遍歷的監(jiān)測點(diǎn)所形成的路徑。我們用一個(gè)數(shù)組來表示該路徑（依次選取與檢測圓個(gè)數(shù)相同的監(jiān)測點(diǎn)形成一個(gè)數(shù)組）也就是模型中的一個(gè)狀態(tài)。狀態(tài)的集合就是狀態(tài)空間。

2.2.3 動(dòng)作空間

我們?yōu)榭罩袩o線通信節(jié)點(diǎn)設(shè)置的動(dòng)作就是對路徑上某個(gè)節(jié)點(diǎn)更改為其他監(jiān)測點(diǎn)。因此一個(gè)動(dòng)作需要用一個(gè)二元組表示（分別為節(jié)點(diǎn)編號，監(jiān)測點(diǎn)編號）。動(dòng)作的集合就是該模型的動(dòng)作空間。

2.2.4 環(huán)境獎(jiǎng)勵(lì)

我們在環(huán)境中設(shè)置的獎(jiǎng)勵(lì)就是輸入環(huán)境中的狀態(tài)形成路徑的長度取負(fù)即為獎(jiǎng)勵(lì)。我們的目標(biāo)是為空中無線通信節(jié)點(diǎn)找到一個(gè)最優(yōu)的路徑遍歷所有的檢測圓，因此獎(jiǎng)勵(lì)即為長度的負(fù)數(shù)。

2.2.5 ε-貪心策略

由于動(dòng)作空間過大，為了避免DDQN中的ε-貪心策略陷入死循環(huán)中，我們在其策略中的貪心算法中每次選取3個(gè)最優(yōu)動(dòng)作，然后隨機(jī)取出一個(gè)作為貪心算法的最優(yōu)動(dòng)作。

2.2.6 空中無線通信節(jié)點(diǎn)移動(dòng)的結(jié)束狀態(tài)

本文問題中空中無線通信節(jié)點(diǎn)最終要找到的是遍歷所有的檢測圓的最短路徑，因此環(huán)境中需要判斷輸入的空中無線通信節(jié)點(diǎn)狀態(tài)是否滿足結(jié)束條件返回狀態(tài)標(biāo)志。結(jié)束狀態(tài)即為狀態(tài)數(shù)組中的路徑遍歷所有的檢測圓且路徑值收斂至最短。（遍歷一個(gè)檢測圓的情況可以有兩種，第一種是路徑通過該監(jiān)測圓上的監(jiān)測點(diǎn)，第二種就是路徑直接與該檢測圓相交）

算法實(shí)施步驟如下：

（1）初始化。我們需要生成環(huán)境以及對模型進(jìn)行初始化（包括經(jīng)驗(yàn)池的初始化）。這里我們規(guī)定空中無線通信節(jié)點(diǎn)從起始狀態(tài)到結(jié)束狀態(tài)為一幕，對模型的建立我們需要對幕進(jìn)行操作。

（2）空中無線通信節(jié)點(diǎn)隨機(jī)初始化一個(gè)狀態(tài)和動(dòng)作，然后輸入環(huán)境中得到獎(jiǎng)勵(lì)、下一個(gè)動(dòng)作以及是否達(dá)到結(jié)束狀態(tài)。

（3）我們把空中無線通信節(jié)點(diǎn)在環(huán)境中得到的信息輸入DDQN中進(jìn)行學(xué)習(xí)。

（4）重復(fù)以上步驟形成M次幕得到最后的DDQN模型。

3 實(shí)驗(yàn)

3.1 測試結(jié)果

在本文中，我們假設(shè)有10個(gè)水面無線通信節(jié)點(diǎn)（即N為10），每個(gè)通信節(jié)點(diǎn)用一個(gè)檢測圓表示。進(jìn)行1000次幕的學(xué)習(xí)（即M為1000），即可得到最終模型。表1為學(xué)習(xí)過程中部分路徑值。

表1：部分路徑值

檢測圓的直徑代表該節(jié)點(diǎn)的通信距離，又由于每個(gè)節(jié)點(diǎn)的遮擋、角度等通行環(huán)境完全相同，所以仿真時(shí)假設(shè)幾種通信距離（檢測圓半徑不同）。將最優(yōu)路徑和較差路徑的結(jié)果在二維圖中顯示如圖3-圖5。

從表1中可以看出，隨著學(xué)習(xí)次數(shù)的增長，空中通信節(jié)點(diǎn)完成對水面通信節(jié)點(diǎn)覆蓋過程的移動(dòng)路徑逐漸收斂至最小值，可以訓(xùn)練出實(shí)用的DDQN模型。從圖3-圖5的路徑結(jié)果對比可以看出，最優(yōu)移動(dòng)路徑與較差移動(dòng)路徑的路徑長度差異巨大，因此，通過該算法尋找最優(yōu)移動(dòng)路徑在實(shí)際應(yīng)用中具有較強(qiáng)需求，可以顯著縮短空中無線通信節(jié)點(diǎn)移動(dòng)時(shí)間、節(jié)約能耗。

4 結(jié)論

由實(shí)驗(yàn)結(jié)果可知，通過DDQN模型可以通過有限的量化和訓(xùn)練次數(shù)，訓(xùn)練出較好的神經(jīng)網(wǎng)絡(luò)，解決水面無線通信節(jié)點(diǎn)較多時(shí)，空中無線通信節(jié)點(diǎn)需要在最短時(shí)間內(nèi)遍歷所有水面節(jié)點(diǎn)建立無線通信和數(shù)據(jù)采集任務(wù)問題，可以顯著縮減空中無線通信節(jié)點(diǎn)移動(dòng)路徑，節(jié)約其運(yùn)動(dòng)能耗。