蔣寶慶，陳宏濱

（桂林電子科技大學(xué)信息與通信學(xué)院，廣西桂林 541004）

0 概述

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）是傳感器、計(jì)算機(jī)、無線通信及微系統(tǒng)等技術(shù)發(fā)展融合的產(chǎn)物［1］，是物聯(lián)網(wǎng)的基礎(chǔ)技術(shù)之一［2］，其由大量廉價(jià)微型傳感節(jié)點(diǎn)組成，通過使用相互連接的智能傳感器來感知和監(jiān)控環(huán)境。無線傳感器網(wǎng)絡(luò)應(yīng)用范圍廣泛，包括環(huán)境監(jiān)測、工業(yè)監(jiān)測、交通監(jiān)測等各個(gè)方面。由于傳感器的大數(shù)據(jù)環(huán)境和大規(guī)模無線傳感器網(wǎng)絡(luò)的出現(xiàn)，因此亟需新的節(jié)能數(shù)據(jù)采集技術(shù)。目前，無線傳感器網(wǎng)絡(luò)的數(shù)據(jù)采集方法主要集中在移動數(shù)據(jù)采集器和匯聚技術(shù)方面。隨著智能城市、智能家居等概念的提出，無線傳感器網(wǎng)絡(luò)被認(rèn)為是智能環(huán)境的核心技術(shù)。無線傳感器網(wǎng)絡(luò)能夠以智能通信的方式交互建立一個(gè)智能網(wǎng)絡(luò)，從而產(chǎn)生一個(gè)能夠處理用戶隨機(jī)需求的應(yīng)用系統(tǒng)。傳統(tǒng)的無線傳感器網(wǎng)絡(luò)結(jié)構(gòu)大多由靜態(tài)節(jié)點(diǎn)組成，這些節(jié)點(diǎn)密集地分布在傳感器區(qū)域內(nèi)。近年來，人們提出了多種基于移動收集器的無線傳感器網(wǎng)絡(luò)結(jié)構(gòu)，利用移動性來解決無線傳感器網(wǎng)絡(luò)中的數(shù)據(jù)收集問題，其中，無人機(jī)（Unmanned Aerial Vehicle，UAV）具有高機(jī)動性、靈活、可達(dá)視距點(diǎn)和成本低等特點(diǎn)。由于下一代無線通信領(lǐng)域?qū)⒕W(wǎng)絡(luò)部署從地面轉(zhuǎn)移到空中，因此無人機(jī)被廣泛用作匯聚節(jié)點(diǎn)與基站之間的通信樞紐［3］。

然而，無線傳感器網(wǎng)絡(luò)的移動性也帶來了靜態(tài)無線傳感器網(wǎng)絡(luò)中不存在的一些問題。文獻(xiàn)［4］指出其面臨的挑戰(zhàn)有感知偵查、喚醒-休眠機(jī)制、傳輸可靠性和移動控制，其中，移動控制指的是當(dāng)移動收集器的運(yùn)動可控制時(shí)，必須設(shè)計(jì)訪問網(wǎng)絡(luò)節(jié)點(diǎn)的策略，因此，必須定義移動節(jié)點(diǎn)的路徑和停留時(shí)間，使網(wǎng)絡(luò)性能達(dá)到最高。一般而言，軌跡規(guī)劃分為兩類：一類是靜態(tài)軌跡規(guī)劃，針對不隨時(shí)間變化的軌跡；另一類是動態(tài)軌跡規(guī)劃，指為滿足數(shù)據(jù)采集的某些特定條件（例如實(shí)時(shí)性），能夠隨時(shí)間變化而改變自己下一步軌跡的規(guī)劃。

本文根據(jù)無線傳感器網(wǎng)絡(luò)的移動性，提出非連續(xù)無人機(jī)軌跡規(guī)劃算法Q-TDUD?？紤]無人機(jī)輔助無線傳感器網(wǎng)絡(luò)數(shù)據(jù)采集的場景，通過相關(guān)工作的對比，針對數(shù)據(jù)采集中各節(jié)點(diǎn)數(shù)據(jù)率隨機(jī)的問題建立相應(yīng)的延時(shí)模型和能耗模型。在此基礎(chǔ)上，結(jié)合Q 學(xué)習(xí)算法設(shè)置合適的獎勵(lì)制度并對場景中的無人機(jī)進(jìn)行迭代訓(xùn)練，使其能夠智能地根據(jù)場景狀態(tài)的變化做出相應(yīng)的軌跡調(diào)整。

1 相關(guān)工作

多數(shù)從靜態(tài)軌跡規(guī)劃角度出發(fā)設(shè)計(jì)的無人機(jī)飛行策略未考慮無人機(jī)自身能耗與飛行軌跡之間的關(guān)系，因此，本文主要關(guān)注動態(tài)軌跡規(guī)劃方面的研究。文獻(xiàn)［5］證明了無論是速度最大化還是能耗最小化的軌跡規(guī)劃都不是最優(yōu)的方案，一般而言，軌跡規(guī)劃需要在這兩個(gè)目標(biāo)之間達(dá)到最佳的平衡。文獻(xiàn)［6］提出空對地?zé)o線通信的基本能量權(quán)衡問題，推導(dǎo)出無人機(jī)和地面終端的能量消耗表達(dá)式，得到了兩者之間權(quán)衡后的最優(yōu)地面終端發(fā)射功率和無人機(jī)軌跡。文獻(xiàn)［7］聯(lián)合優(yōu)化傳感器節(jié)點(diǎn)喚醒機(jī)制和無人機(jī)軌跡規(guī)劃機(jī)制，在最小化所有傳感器節(jié)點(diǎn)最大能耗的同時(shí)確保每個(gè)傳感器數(shù)據(jù)的可靠傳輸。文獻(xiàn)［8］研究無人機(jī)對傳感器進(jìn)行充電的軌跡規(guī)劃問題，討論總能量最大化引起的遠(yuǎn)近公平問題，進(jìn)而提出一種最優(yōu)航跡驅(qū)動的連續(xù)式盤旋航跡方法。文獻(xiàn)［9］研究無人機(jī)組播系統(tǒng)，提出一種基于虛擬基站布局的新概念和凸優(yōu)化的路徑設(shè)計(jì)方法。

上述工作均為連續(xù)式的無人機(jī)軌跡規(guī)劃研究，即在無人機(jī)執(zhí)行任務(wù)之前計(jì)算出飛行軌跡，按照該軌跡規(guī)劃結(jié)果連續(xù)式飛行直至任務(wù)結(jié)束。然而，連續(xù)式無人機(jī)的飛行軌跡規(guī)劃無法滿足實(shí)際應(yīng)用場景中數(shù)據(jù)收集的可靠性和有效性要求。只有當(dāng)無人機(jī)進(jìn)入?yún)R聚節(jié)點(diǎn)感知范圍且匯聚節(jié)點(diǎn)完成數(shù)據(jù)匯集時(shí)，無人機(jī)才對匯聚節(jié)點(diǎn)進(jìn)行感知，這會造成不必要的能量消耗及數(shù)據(jù)采集延遲。對此，一些研究者提出非連續(xù)無人機(jī)軌跡規(guī)劃。文獻(xiàn)［10］針對單無人機(jī)給多地面用戶進(jìn)行充電的問題，提出一種基于遺傳算法的非連續(xù)飛行方案，迭代搜索出最優(yōu)懸停點(diǎn)并優(yōu)化相應(yīng)的懸停時(shí)間。文獻(xiàn)［11］運(yùn)用機(jī)器學(xué)習(xí)領(lǐng)域的相關(guān)知識，利用認(rèn)知代理在無線傳感器網(wǎng)絡(luò)中建立基于學(xué)習(xí)、推理和信息共享的主動學(xué)習(xí)決策，使無人機(jī)能夠在多個(gè)約束中智能地選擇執(zhí)行懸?；蛘唢w行策略，得到非連續(xù)無人機(jī)飛行軌跡。文獻(xiàn)［12］提出一種改進(jìn)的多無人機(jī)Q 學(xué)習(xí)算法來解決分散的無人機(jī)軌跡規(guī)劃問題，同時(shí)計(jì)算使用嵌套馬爾科夫鏈得到的有效數(shù)據(jù)傳輸概率。文獻(xiàn)［13］研究用戶端信息（如位置、發(fā)射功率、信道參數(shù)等）無法訪問情況下的上行速率之和最大化問題，將該問題描述為一個(gè)馬爾科夫決策過程（Markov Decision Process，MDP），通過無模型強(qiáng)化學(xué)習(xí)來解決，同時(shí)由實(shí)驗(yàn)結(jié)果表明，無人機(jī)能在未知用戶側(cè)信息和信道參數(shù)的情況下，根據(jù)所學(xué)習(xí)的軌跡對地面用戶進(jìn)行智能跟蹤。

為優(yōu)化無人機(jī)的能耗及無線傳感器網(wǎng)絡(luò)的數(shù)據(jù)采集效率，上述工作主要從無人機(jī)的飛行能耗和懸停能耗以及數(shù)據(jù)傳輸?shù)男诺婪峙鋪磉M(jìn)行問題建模，但沒有考慮到負(fù)責(zé)接收和發(fā)送數(shù)據(jù)的匯聚節(jié)點(diǎn)存在匯聚完成時(shí)間不一致及數(shù)據(jù)量大小不一致的問題，忽略了實(shí)際應(yīng)用中節(jié)點(diǎn)數(shù)據(jù)產(chǎn)生速率隨機(jī)性的影響。在進(jìn)行無人機(jī)軌跡規(guī)劃時(shí)，懸停點(diǎn)順序及懸停時(shí)間應(yīng)得到進(jìn)一步優(yōu)化。由于強(qiáng)化學(xué)習(xí)中的Q 學(xué)習(xí)具有單步獎勵(lì)機(jī)制和離線學(xué)習(xí)等特點(diǎn)，其能將懸停動作加入無人機(jī)動作集中，通過一定次數(shù)的迭代得到最優(yōu)飛行策略，優(yōu)化懸停點(diǎn)順序和懸停時(shí)間，因此對于合理規(guī)劃無人機(jī)軌跡、保證有效數(shù)據(jù)率較高且提高能量效率的問題，可以結(jié)合強(qiáng)化學(xué)習(xí)理論進(jìn)行分析。

本文考慮節(jié)點(diǎn)數(shù)據(jù)產(chǎn)生速率的隨機(jī)性以及非連續(xù)無人機(jī)輔助數(shù)據(jù)采集的應(yīng)用場景，提出一種基于Q 學(xué)習(xí)的非連續(xù)無人機(jī)軌跡規(guī)劃算法Q-TDUD。在建立匯聚節(jié)點(diǎn)時(shí)，利用基于距離的K-means 算法對網(wǎng)絡(luò)中節(jié)點(diǎn)分簇并確定匯聚節(jié)點(diǎn)，根據(jù)傳感器網(wǎng)絡(luò)中單個(gè)節(jié)點(diǎn)在周期內(nèi)的數(shù)據(jù)速率改變概率以及單位數(shù)據(jù)量和單位距離轉(zhuǎn)發(fā)數(shù)據(jù)的延遲時(shí)間，構(gòu)建匯聚節(jié)點(diǎn)的延遲差異模型。在規(guī)劃非連續(xù)無人機(jī)軌跡時(shí)，將無人機(jī)軌跡設(shè)計(jì)整體細(xì)分為離散馬爾科夫過程［14］，并應(yīng)用強(qiáng)化學(xué)習(xí)［15］中的Q 學(xué)習(xí)算法來優(yōu)化無人機(jī)的飛行軌跡。在無線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集過程中，將無人機(jī)的位置和運(yùn)動方向作為強(qiáng)化學(xué)習(xí)中的狀態(tài)集和動作集。在每次執(zhí)行某個(gè)策略后，收到的匯聚節(jié)點(diǎn)的反饋將被用作更新Q 表的即時(shí)獎勵(lì)，通過獎勵(lì)對Q 表進(jìn)行更新，從而確定無人機(jī)在每個(gè)狀態(tài)的下一步策略。重復(fù)該過程直至找到最佳飛行軌跡。不同于現(xiàn)有多數(shù)無人機(jī)輔助數(shù)據(jù)采集的軌跡規(guī)劃研究，本文考慮各簇規(guī)模不一致導(dǎo)致相應(yīng)匯聚節(jié)點(diǎn)匯聚完成時(shí)間不一致的情況，設(shè)置延遲容忍時(shí)間來約束無人機(jī)數(shù)據(jù)采集任務(wù)的完成效率，提出非連續(xù)無人機(jī)軌跡規(guī)劃問題，并利用Q 學(xué)習(xí)中的獎勵(lì)機(jī)制設(shè)置兩種獎勵(lì)方式，使無人機(jī)能夠智能地選擇自己的懸停狀態(tài)或飛行狀態(tài)，將傳統(tǒng)的連續(xù)式無人機(jī)飛行軌跡規(guī)劃轉(zhuǎn)換為非連續(xù)的軌跡規(guī)劃。

2 系統(tǒng)模型

2.1 延時(shí)模型

無線傳感器網(wǎng)絡(luò)由大量傳感器節(jié)點(diǎn)和少量執(zhí)行器節(jié)點(diǎn)構(gòu)成，其應(yīng)用涵蓋廣泛，從工業(yè)過程的自動化到系統(tǒng)的通風(fēng)量和溫度控制等均有所涉及［16］。在無線傳感器網(wǎng)絡(luò)中，傳感器節(jié)點(diǎn)負(fù)責(zé)從物理世界收集信息，執(zhí)行器節(jié)點(diǎn)負(fù)責(zé)根據(jù)信息做出獨(dú)立的判斷，并執(zhí)行相應(yīng)的任務(wù)［17-19］，傳感器節(jié)點(diǎn)一旦部署完成，不再移動或者改變。

本文將n個(gè)靜態(tài)傳感器節(jié)點(diǎn)X={x1，x2，…，xn}隨機(jī)均勻地部署在大小為W的網(wǎng)絡(luò)范圍內(nèi)，初始化單個(gè)節(jié)點(diǎn)的數(shù)據(jù)生成速率為Va。無人機(jī)有能量損耗速度快、自身儲能小和工作時(shí)長短等缺點(diǎn)，若遍歷網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)進(jìn)行數(shù)據(jù)采集，則采集時(shí)間過長，會出現(xiàn)部分節(jié)點(diǎn)的緩存區(qū)數(shù)據(jù)溢出或無人機(jī)自身能耗不足導(dǎo)致任務(wù)終止等情況。因此，本文將節(jié)點(diǎn)組織成簇，在簇中選出匯聚節(jié)點(diǎn)負(fù)責(zé)接收簇內(nèi)各節(jié)點(diǎn)的數(shù)據(jù)并與無人機(jī)進(jìn)行數(shù)據(jù)交互，以提高網(wǎng)絡(luò)的擴(kuò)展性和節(jié)點(diǎn)能量的利用率。此處使用K-means 聚類算法［20］對隨機(jī)均勻分布的節(jié)點(diǎn)進(jìn)行分簇，得到包含k個(gè)簇的集合C={c1，c2，…，ck}，其中每個(gè)簇的簇成員個(gè)數(shù)為cn(k)，匯聚節(jié)點(diǎn)位置表示為，k∈{1，2，…，m}，匯聚節(jié)點(diǎn)的最大緩存數(shù)據(jù)量為Dmax。圖1 為傳感器網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量為30、分簇個(gè)數(shù)為4 時(shí)的節(jié)點(diǎn)分簇示意圖，將各簇分別用4 種不同的顏色表示（彩色效果見《計(jì)算機(jī)工程》官網(wǎng)HTML 版），其中，黑色點(diǎn)表示匯聚節(jié)點(diǎn)，是距離各簇質(zhì)心最近的節(jié)點(diǎn)。

圖1 K-means 分簇結(jié)果（k=4，n=30）Fig.1 K-means clustering result（k=4，n=30）

在簇成員向匯聚節(jié)點(diǎn)進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)的路由選擇上，本文考慮分級多跳路由的方式［21］。分級多跳路由的核心思想是劃分節(jié)點(diǎn)之間的優(yōu)先級，首先計(jì)算出簇成員節(jié)點(diǎn)到匯聚節(jié)點(diǎn)的距離，然后根據(jù)其距離將簇成員節(jié)點(diǎn)由近及遠(yuǎn)劃分為3 個(gè)等級。數(shù)據(jù)轉(zhuǎn)發(fā)規(guī)則為節(jié)點(diǎn)數(shù)據(jù)只能由較遠(yuǎn)的低級節(jié)點(diǎn)發(fā)送給較近的高級節(jié)點(diǎn)，不可跨級上傳。簇內(nèi)路由的系統(tǒng)模型如圖2 所示，圖中心的黑色點(diǎn)為該簇的匯聚節(jié)點(diǎn)，淺灰色點(diǎn)為一級轉(zhuǎn)發(fā)節(jié)點(diǎn)，深灰色點(diǎn)為二級中間節(jié)點(diǎn)，白色點(diǎn)為三級邊緣節(jié)點(diǎn)。當(dāng)開始數(shù)據(jù)匯集時(shí)，簇成員節(jié)點(diǎn)通過多跳的方式將數(shù)據(jù)轉(zhuǎn)發(fā)至匯聚節(jié)點(diǎn)進(jìn)行數(shù)據(jù)匯集。

圖2 簇內(nèi)路由Fig.2 Routing within the cluster

對于傳感器節(jié)點(diǎn)而言，需要考慮采集數(shù)據(jù)量和能量消耗之間的折中。處于網(wǎng)絡(luò)區(qū)域邊緣的節(jié)點(diǎn)只需要將收集的數(shù)據(jù)發(fā)送給移動采集器，能量消耗相對較少，而靠近匯聚中心的節(jié)點(diǎn)同時(shí)還需要為邊緣節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)，消耗的能量較多。因此，邊緣節(jié)點(diǎn)必須對采集到的數(shù)據(jù)進(jìn)行一定的壓縮和融合處理后再發(fā)送給下一跳節(jié)點(diǎn)。數(shù)據(jù)融合機(jī)制減少了需要傳輸?shù)臄?shù)據(jù)量，能夠減輕網(wǎng)絡(luò)的傳輸擁塞，降低數(shù)據(jù)的傳輸延遲，在一定程度上提高網(wǎng)絡(luò)收集數(shù)據(jù)的整體效率。用Dk表示匯聚周期Tv內(nèi)匯聚節(jié)點(diǎn)的數(shù)據(jù)量，用Pn表示節(jié)點(diǎn)的數(shù)據(jù)產(chǎn)生速率在一個(gè)匯聚周期Tv內(nèi)發(fā)生改變的概率，用Pc表示邊緣節(jié)點(diǎn)的數(shù)據(jù)融合率，則根據(jù)文獻(xiàn)［21］中對簇頭節(jié)點(diǎn)匯集數(shù)據(jù)量的計(jì)算方式，在匯聚周期Tv內(nèi)各簇的數(shù)據(jù)量為：

在實(shí)際應(yīng)用中，人們希望無人機(jī)的單次采集效率最大化?？紤]到無線傳感器節(jié)點(diǎn)監(jiān)測環(huán)境的不確定性以及無人機(jī)能耗特性的約束，需要設(shè)置匯聚節(jié)點(diǎn)的最小數(shù)據(jù)量大小，使得當(dāng)匯聚節(jié)點(diǎn)只有在匯聚數(shù)據(jù)量大小達(dá)到規(guī)定時(shí)，無人機(jī)才將此匯聚節(jié)點(diǎn)考慮至軌跡規(guī)劃內(nèi)，若匯聚節(jié)點(diǎn)在時(shí)隙t未達(dá)到最小數(shù)據(jù)量，則產(chǎn)生匯聚延時(shí)。本文通過設(shè)立延時(shí)機(jī)制來提高無人機(jī)的單次采集效率。用Ds表示匯聚節(jié)點(diǎn)最小數(shù)據(jù)量，若改變量為?Va，則Va+?Va∈[Vamin，Vamax]，其中，Vamin為節(jié)點(diǎn)最小數(shù)據(jù)產(chǎn)生速率，Vamax為節(jié)點(diǎn)最大數(shù)據(jù)產(chǎn)生速率。此時(shí)可以計(jì)算得到匯聚節(jié)點(diǎn)的延時(shí)為：

(k)為簇k的平均數(shù)據(jù)生成率，表示為：

2.2 能耗模型

考慮到在節(jié)點(diǎn)度、最大時(shí)間延遲等條件相同的情況下，移動采集器的軌跡長度與傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)的總跳數(shù)成反比［22］，若聯(lián)合考慮無人機(jī)與傳感器網(wǎng)絡(luò)的總能耗，當(dāng)改變網(wǎng)絡(luò)拓?fù)涫箓鞲衅骶W(wǎng)絡(luò)節(jié)點(diǎn)之間數(shù)據(jù)傳輸達(dá)到最小時(shí)，會一定程度忽略無人機(jī)的路徑復(fù)雜度，使無人機(jī)飛行能耗增加，從而系統(tǒng)中的能耗無法達(dá)到最優(yōu)。因此，本文主要考慮無人機(jī)的能耗。

如圖3 所示，無線傳感器網(wǎng)絡(luò)中的匯聚節(jié)點(diǎn)負(fù)責(zé)接收和處理從子節(jié)點(diǎn)多跳上傳來的數(shù)據(jù)，無人機(jī)在空中作為一個(gè)移動采集器對地面上k個(gè)匯聚節(jié)點(diǎn)進(jìn)行數(shù)據(jù)采集。

圖3 無人機(jī)采集無線傳感器網(wǎng)絡(luò)數(shù)據(jù)的場景Fig.3 A scene where UAVs collect data in WSN

將無人機(jī)采集數(shù)據(jù)的總過程分為T個(gè)時(shí)隙，以便于迭代推導(dǎo)。假設(shè)無人機(jī)以恒定速度VUAV飛行在固定高度H上空。每個(gè)時(shí)隙無人機(jī)的位置為U={U1，U2，…，UT}。其中，Ut=[xu(t) ，yu(t) ，H]。由于無人機(jī)的計(jì)算能耗與飛行能耗相比較小，因此可忽略不計(jì)。另一方面，本文將無人機(jī)完成收集所有匯聚節(jié)點(diǎn)數(shù)據(jù)的任務(wù)作為一輪。在每一輪開始時(shí)，各匯聚節(jié)點(diǎn)的匯聚延時(shí)會隨著各簇成員節(jié)點(diǎn)數(shù)據(jù)生成速率的更新而更新，因此，在每輪無人機(jī)開始采集數(shù)據(jù)到完成采集的過程中，各匯聚節(jié)點(diǎn)的數(shù)據(jù)量大小是固定的。又因?yàn)闊o人機(jī)只有進(jìn)入?yún)R聚節(jié)點(diǎn)的感知范圍r時(shí)才會與該節(jié)點(diǎn)進(jìn)行數(shù)據(jù)傳輸，保證了通信信道較大的穩(wěn)定性和較小的差異性，所以本文忽略無人機(jī)與各匯聚節(jié)點(diǎn)之間的數(shù)據(jù)傳輸能耗。因此，在保證無人機(jī)采集效率的同時(shí)提高無人機(jī)的能量效率，是優(yōu)化軌跡性能的關(guān)鍵。設(shè)ph為無人機(jī)的懸停功率，d（t）為一個(gè)時(shí)間間隙內(nèi)無人機(jī)飛行距離，則無人機(jī)懸停能耗Eh和飛行能耗Ef表示為：

由于無人機(jī)在飛行過程中加入了懸停策略，會出現(xiàn)某些匯聚節(jié)點(diǎn)數(shù)據(jù)匯集完成但是無人機(jī)尚未進(jìn)入其采集范圍的現(xiàn)象，這使得匯聚節(jié)點(diǎn)進(jìn)入等待時(shí)間易造成數(shù)據(jù)丟失及緩存溢出的情況，從而無人機(jī)后續(xù)的數(shù)據(jù)采集將變得毫無意義，因此有必要設(shè)置一個(gè)等待時(shí)間閾值來約束等待時(shí)間過長的情況。根據(jù)傳感器緩沖內(nèi)存限制及數(shù)據(jù)匯集的實(shí)時(shí)性要求，本文規(guī)定當(dāng)無人機(jī)在時(shí)隙t內(nèi)與匯聚節(jié)點(diǎn)k進(jìn)行數(shù)據(jù)采集時(shí)，若匯聚節(jié)點(diǎn)k的等待時(shí)間Tw(k)≤γ，則無人機(jī)采集的數(shù)據(jù)為有效數(shù)據(jù)，Tw(k)=Th(k) -t。若不在此等待閾值范圍內(nèi)，則將此數(shù)據(jù)稱為無效數(shù)據(jù)。等待閾值γ定義為：

其中，為平均延遲時(shí)間，η、ξ為常數(shù)參數(shù)。

3 Q-TDUD 算法描述

在無人機(jī)軌跡規(guī)劃中，無人機(jī)的能量消耗及通信質(zhì)量等問題始終是研究者的關(guān)注重點(diǎn)。上節(jié)已求解出無人機(jī)的飛行能耗和懸停能耗，下節(jié)將解決在保證無人機(jī)與傳感器之間上行鏈路傳輸穩(wěn)定的同時(shí)使無人機(jī)整體能耗最小的問題。本文考慮每架無人機(jī)的效用為其任務(wù)成功采集有效數(shù)據(jù)總量，因此，可以通過設(shè)計(jì)非連續(xù)無人機(jī)的軌跡來最大化有效數(shù)據(jù)總量。

本節(jié)將給出非連續(xù)無人機(jī)的軌跡規(guī)劃，最大化總傳輸速率和能量消耗的比值?？紤]速度的約束，將其建模為如下最優(yōu)化問題：

Ri表示CN（i）的傳輸速率，如式（8）所示：

其中，μ表示信道增益，β表示距離衰減，Ci表示匯聚節(jié)點(diǎn)所在位置，δ表示信道噪聲功率。

由于優(yōu)化問題是非凸的，全局最優(yōu)軌跡很難找到，并且在無人機(jī)未知匯聚節(jié)點(diǎn)位置信息的情況下，只有在多次執(zhí)行采集操作后才能觀察到能耗及有效數(shù)據(jù)的收集情況，因此本文基于強(qiáng)化學(xué)習(xí)確定無人機(jī)每個(gè)狀態(tài)的動作執(zhí)行策略來解決式（7）所示的問題。Q 學(xué)習(xí)算法是強(qiáng)化學(xué)習(xí)中基于值函數(shù)的算法，對任何有限的馬爾科夫決策過程，Q 學(xué)習(xí)都可以找到一種最優(yōu)策略。Q 學(xué)習(xí)涉及一個(gè)代理（agent）、一組狀態(tài)S以及一組動作A。通過在環(huán)境中執(zhí)行動作使得代理從一個(gè)狀態(tài)轉(zhuǎn)移到另一個(gè)狀態(tài)，在特定狀態(tài)下執(zhí)行動作會提供獎勵(lì)。簡單來說，Q(s，a) 為某一時(shí)刻s狀態(tài)下(s∈S)，采取動作a(a∈A) 能夠獲得的獎勵(lì)期望。環(huán)境會根據(jù)代理選擇的動作反饋相應(yīng)的獎勵(lì)r，因此，Q-TDUD 算法的主要設(shè)計(jì)思想是以狀態(tài)s與動作a構(gòu)建成一張Q 表來存儲Q值，最后根據(jù)Q值來選取能夠獲得最大獎勵(lì)的動作。在非連續(xù)無人機(jī)軌跡規(guī)劃中，將無人機(jī)在各時(shí)隙的位置信息設(shè)置為Q 學(xué)習(xí)中的狀態(tài)集，再將懸停態(tài)加入無人機(jī)的動作集之中，構(gòu)建一個(gè)關(guān)于無人機(jī)當(dāng)前位置狀態(tài)和動作的Q 表。在算法的迭代過程中，環(huán)境根據(jù)下一個(gè)狀態(tài)s，中選取的最大Q(s，，a，) 值乘以獎勵(lì)衰變系數(shù)，再加上真實(shí)獎勵(lì)值計(jì)算得到Q的現(xiàn)實(shí)值Q，(s，a)：

其中，γ為獎勵(lì)性衰變系數(shù)，γ越接近1 代表它越有遠(yuǎn)見會著重考慮后續(xù)狀態(tài)的價(jià)值。當(dāng)γ接近0 時(shí)會著重考慮當(dāng)前的利益影響，r為當(dāng)前行為獎勵(lì)，Q(s，，a，)為下一狀態(tài)中的最大Q值。

根據(jù)以上推導(dǎo)可以對Q值進(jìn)行計(jì)算，即對Q 表進(jìn)行更新。假設(shè)學(xué)習(xí)率為α，采用時(shí)間差分的方法進(jìn)行更新，則更新后的Q值為：

Q 學(xué)習(xí)的最大目標(biāo)是求出累計(jì)獎勵(lì)最大策略的期望。接下來需要明確學(xué)習(xí)環(huán)境、狀態(tài)集、動作集、獎勵(lì)設(shè)置以及Q 表的更新過程［23］。

1）環(huán)境。單架無人機(jī)從固定起點(diǎn)飛行，向通信半徑范圍內(nèi)的節(jié)點(diǎn)廣播數(shù)據(jù)包。在每個(gè)周期開始時(shí)，匯聚節(jié)點(diǎn)更新其數(shù)據(jù)量大小及數(shù)據(jù)匯集完成時(shí)間。無人機(jī)的位置為強(qiáng)化學(xué)習(xí)的狀態(tài)集，行為為動作集。在每輪采集開始時(shí)，無人機(jī)對地面匯聚節(jié)點(diǎn)的位置未知，但可通過接受各匯聚節(jié)點(diǎn)的反饋來獲取每個(gè)行為的好壞。

2）狀態(tài)集S={g1，g2，…，gx}。根據(jù)文獻(xiàn)［24］中的網(wǎng)格法使無人機(jī)的位置狀態(tài)離散化。將無人機(jī)需要采集的網(wǎng)絡(luò)區(qū)域劃分為x個(gè)網(wǎng)格{g1，g2，…，gx}。文獻(xiàn)［25］指出：網(wǎng)格粒度越小，節(jié)點(diǎn)位置及無人機(jī)狀態(tài)表示會越精確，但同時(shí)會占用大量的存儲空間，算法的搜索范圍將按指數(shù)增大；網(wǎng)格粒度太大，規(guī)劃的軌跡會很不精確。因此，此處的x與傳感區(qū)域大小及VUAV如式（11）所示：

其中，W為傳感區(qū)域大小，λ為常數(shù)參數(shù)。在每次無人機(jī)改變位置狀態(tài)后將對其位置進(jìn)行判定，劃分到所屬的狀態(tài)集，以便于Q 表的更新。

4）獎勵(lì)。獎勵(lì)機(jī)制分為懸停優(yōu)先和非懸停優(yōu)先兩種情況。第1 種是懸停優(yōu)先的情況，忽略無人機(jī)與匯聚節(jié)點(diǎn)進(jìn)行數(shù)據(jù)采集所耗費(fèi)的時(shí)間，若當(dāng)前位置狀態(tài)下無人機(jī)到延時(shí)最小的匯聚節(jié)點(diǎn)的飛行時(shí)間小于該節(jié)點(diǎn)的延遲時(shí)間時(shí)，即tf＜minTk，無人機(jī)動作獎勵(lì)為懸停優(yōu)先，其中，tf為無人機(jī)到最小延時(shí)節(jié)點(diǎn)的預(yù)估時(shí)間，當(dāng)δ=1 時(shí)懸停動作獎勵(lì)為r=rh，其他動作獎勵(lì)為0。第2 種是非懸停優(yōu)先的情況，若tf≥minTk，不滿足第1 種獎勵(lì)情況，則為非懸停優(yōu)先。兩種情況的獎勵(lì)設(shè)置為：

當(dāng)δ=0 時(shí)，使當(dāng)下無人機(jī)狀態(tài)的各匯聚節(jié)點(diǎn)完成時(shí)間序列{T1(t)，T2(t)，…，Tl(t)}，根據(jù)文獻(xiàn)［26］方法進(jìn)行歸一化處理得到{s1(t)，s2(t)，…，sl(t)}，便于獎勵(lì)的計(jì)算。筆者希望無人機(jī)朝著延時(shí)最小的節(jié)點(diǎn)且傳輸數(shù)據(jù)較大的方向飛行，因此：

當(dāng)選擇的動作a 使無人機(jī)與簇頭i的距離減小時(shí)，τ=1。

Q-TDUD 算法的偽代碼如算法1 所示。其中：第1 行初始化了無人機(jī)的位置、地面靜態(tài)節(jié)點(diǎn)的位置以及動作集和Q 表；第2 行～第3 行規(guī)定了無人機(jī)的總采集輪數(shù)，每輪開始前要更新無人機(jī)的位置坐標(biāo)和匯聚節(jié)點(diǎn)的延時(shí)；第4 行對無人機(jī)是否對所有的匯聚節(jié)點(diǎn)執(zhí)行完采集任務(wù)的判定，若還有節(jié)點(diǎn)尚未采集則程序仍然往下執(zhí)行，S是每次循環(huán)開始時(shí)程序根據(jù)無人機(jī)當(dāng)下位置坐標(biāo)判斷得到的狀態(tài)集中的狀態(tài)；第5 行進(jìn)行動作選擇。為使結(jié)果更具非偶然性，在確定選擇動作的策略時(shí)設(shè)置一個(gè)冒險(xiǎn)概率ξ，這樣代理有一定機(jī)會不遵從Q 表中當(dāng)前狀態(tài)的動作最大值來選擇動作，而是從剩余動作中隨機(jī)選擇一個(gè)動作執(zhí)行，有效避免了代理陷入某個(gè)動作并反復(fù)執(zhí)行所帶來的時(shí)間浪費(fèi)；第6 行～第12 行是對Q 表的更新。在獎勵(lì)計(jì)算方面，根據(jù)上述的兩種獎勵(lì)機(jī)制，首先計(jì)算出當(dāng)前tf與minTk的大小比較情況。若tf＜minTk，進(jìn)入第1 種懸停優(yōu)先獎勵(lì)模式，此時(shí)的無人機(jī)如果執(zhí)行的不是懸停動作，則獎勵(lì)為0；若tf≥minTk，則獎勵(lì)進(jìn)入非懸停優(yōu)先模式，如果此時(shí)無人機(jī)執(zhí)行的不是最佳動作則無法獲得最大獎勵(lì)。算法第12 行將當(dāng)前狀態(tài)的最大Q值動作的選擇策略設(shè)置為1，使下一輪代理在進(jìn)行動作選擇時(shí)在不冒險(xiǎn)的情況下得到最大Q值的動作選擇策略。

算法1Q-TDUD 算法

4 仿真與結(jié)果分析

本節(jié)將對比基于強(qiáng)化學(xué)習(xí)的無人機(jī)軌跡規(guī)劃的性能仿真結(jié)果，包括任務(wù)完成時(shí)間、有效數(shù)據(jù)率、有效數(shù)據(jù)收集以及有效數(shù)據(jù)和能耗之比。首先設(shè)置一個(gè)W=100 m×100 m 的正方形區(qū)域，在其中隨機(jī)均勻分布300 個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)的分布情況及分簇多跳結(jié)果如圖4 和圖5 所示（彩色效果見《計(jì)算機(jī)工程》官網(wǎng)HTML 版）。圖4 中的黑色點(diǎn)為各簇的簇頭節(jié)點(diǎn)，圖5 展示了簇內(nèi)節(jié)點(diǎn)的分級情況以及數(shù)據(jù)的多跳傳輸過程，圖中右下角圖案為六角星、右三角形、五角星的點(diǎn)分別為文獻(xiàn)［21］中簇內(nèi)分級算法計(jì)算所得的三級、二級、一級節(jié)點(diǎn)，黑色的線段表示不同級別節(jié)點(diǎn)之間的數(shù)據(jù)傳輸路徑。

圖4 K-means 分簇結(jié)果Fig.4 K-means clustering result

圖5 簇內(nèi)節(jié)點(diǎn)分簇多跳結(jié)果Fig.5 Grading and multiple hops result within a cluster

基于上述網(wǎng)絡(luò)結(jié)構(gòu)，設(shè)置節(jié)點(diǎn)初始數(shù)據(jù)產(chǎn)生速率Va=10bit/s，Vamin=5bit/s，Vamax=50bit/s。節(jié)點(diǎn)數(shù)據(jù)速率改變概率Pa=0.9，數(shù)據(jù)融合率Pc=0.8。Ds=5×104bit，Tv=3 s。無人機(jī)的初始位置為［50，50，H］，H=5 m，懸停功率ph=50 w，飛行功率pf=75 w，飛行速率VUAV=6 m/s。延時(shí)模型參數(shù)為η=0.01，ξ=3，=1。

針對上文無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署，將Q-TDUD算法參數(shù)設(shè)置為ξ=0.2，β=2，p(t)=5 w，λ=0.057，ρ=0.3，學(xué)習(xí)率α=0.01，獎勵(lì)衰減系數(shù)γ=0.9，并與連續(xù)式最小旅行商軌跡規(guī)劃算法（TSP-continues）［27-28］、非連續(xù)最小旅行商算法（TSP）、連續(xù)式下一跳最短路徑規(guī)劃算法（NJS-continues）以及非連續(xù)下一跳最短路徑規(guī)劃算法（NJS）進(jìn)行比較，Matlab 仿真結(jié)果如圖6～圖9 所示。TSP 方案的主要原理是先將網(wǎng)絡(luò)中的節(jié)點(diǎn)按照K-means 方法進(jìn)行分簇并找到簇頭，簇成員節(jié)點(diǎn)按照前文介紹的文獻(xiàn)［21］簇內(nèi)多跳方法將數(shù)據(jù)傳至簇頭，再用文獻(xiàn)［27］中蟻群求解TSP 問題的算法找出無人機(jī)經(jīng)過全部簇頭的最優(yōu)軌跡。NJS方案中的簇頭選取與簇內(nèi)節(jié)點(diǎn)數(shù)據(jù)的多跳傳輸部分與Q-TDUD 一致，在無人機(jī)軌跡規(guī)劃上，簇頭節(jié)點(diǎn)將根據(jù)已被采集和未被采集兩種狀態(tài)分為兩個(gè)集合，在每輪采集中無人機(jī)基于當(dāng)前的簇頭位置與未被采集集合的簇頭節(jié)點(diǎn)計(jì)算歐氏距離，距離最小的當(dāng)選為無人機(jī)執(zhí)行下一個(gè)采集任務(wù)的位置。TSP 與NJS方案又分為連續(xù)式和非連續(xù)式：連續(xù)式指的是無人機(jī)沒有懸停機(jī)制，若進(jìn)入?yún)R聚節(jié)點(diǎn)感知區(qū)域內(nèi)但匯聚節(jié)點(diǎn)并沒有達(dá)到匯聚完成狀態(tài)時(shí)，無人機(jī)會繼續(xù)按照計(jì)劃軌跡行駛，直至將所有數(shù)據(jù)采集完畢；非連續(xù)是指當(dāng)無人機(jī)按照計(jì)算出的軌跡行進(jìn)至某個(gè)匯聚節(jié)點(diǎn)感知區(qū)域內(nèi)時(shí)，若該節(jié)點(diǎn)尚未達(dá)到匯聚完成狀態(tài)，無人機(jī)會開啟懸停機(jī)制，懸停在感知區(qū)域內(nèi)直到采集完該節(jié)點(diǎn)數(shù)據(jù)才執(zhí)行下一個(gè)任務(wù)。

圖6 不同簇規(guī)模下的平均任務(wù)完成時(shí)間Fig.6 Average task completion times for different cluster sizes

圖7 不同等待時(shí)間閾值下有效數(shù)據(jù)率Fig.7 Effective data rates at different waiting time thresholds

圖8 1 000 輪內(nèi)有效數(shù)據(jù)收集情況Fig 8 Situation of the collection of valid data within 1 000 rounds

圖9 1 000 輪內(nèi)有效數(shù)據(jù)和能耗比值Fig 9 Effective data and energy consumption ratio within 1 000 rounds

由圖6 可以看出，在網(wǎng)絡(luò)中不同的簇規(guī)模下，Q-TDUD 算法完成任務(wù)的時(shí)間比其他4 種算法完成任務(wù)的時(shí)間要小，這是因?yàn)镼-TDUD 算法考慮到了各匯聚節(jié)點(diǎn)的隨機(jī)性，優(yōu)先對匯聚完成時(shí)間較小的節(jié)點(diǎn)執(zhí)行數(shù)據(jù)采集任務(wù)，顯著降低了無人機(jī)完成數(shù)據(jù)采集任務(wù)的時(shí)間，使網(wǎng)絡(luò)負(fù)載更均衡。

等待時(shí)間閾值增大情況下各算法對應(yīng)的有效數(shù)據(jù)率變化如圖7 所示。等待時(shí)間閾值根據(jù)式（4）計(jì)算得到，圖中的橫坐標(biāo)分別是ξ=5，η={0.01， 0.015，0.025，0.03，0.035，0.045} 時(shí)計(jì)算得到的等待時(shí)間閾值。由于傳感器小巧輕便的外形設(shè)計(jì)，其數(shù)據(jù)緩存區(qū)大小受到相應(yīng)限制，因此等待時(shí)間閾值的設(shè)置能夠揭示無人機(jī)是否能及時(shí)地執(zhí)行數(shù)據(jù)采集任務(wù)。從結(jié)果圖中可以得出，當(dāng)?shù)却龝r(shí)間閾值增大時(shí)，各算法的有效數(shù)據(jù)比例在增大，但當(dāng)?shù)却龝r(shí)間閾值較小時(shí)，Q-TDUD 算法的性能明顯優(yōu)于其他基準(zhǔn)算法，這說明Q-TDUD 算法能使無人機(jī)及時(shí)地飛行至已完成數(shù)據(jù)匯集的節(jié)點(diǎn)上方采集數(shù)據(jù)，提高傳感器網(wǎng)絡(luò)的數(shù)據(jù)采集實(shí)時(shí)性。

各算法能量效率的比較如圖8 和圖9 所示。圖8顯示在η=0.01，ξ=3 的等待時(shí)間閾值下，各算法的有效數(shù)據(jù)量隨著循環(huán)次數(shù)增大而增加，其中Q-TDUD算法略高于其他基準(zhǔn)算法，結(jié)合能耗情況來看，Q-TDUD 算法的能量效率明顯由于其他基準(zhǔn)算法。圖9 中歸一化處理后的有效數(shù)據(jù)和能耗的比值也顯示Q-TDUD 算法性能更好。

5 結(jié)束語

針對無線傳感器網(wǎng)絡(luò)中各節(jié)點(diǎn)數(shù)據(jù)產(chǎn)生速率隨機(jī)和匯聚節(jié)點(diǎn)狀態(tài)不一致的場景，本文提出一種基于強(qiáng)化學(xué)習(xí)的無人機(jī)飛行軌跡規(guī)劃算法Q-TDUD。該算法采用強(qiáng)化學(xué)習(xí)的思想，根據(jù)無人機(jī)的數(shù)據(jù)傳輸速率和匯聚節(jié)點(diǎn)的反饋信息更新Q值，據(jù)此得到無人機(jī)當(dāng)前狀態(tài)的下一步動作。無人機(jī)執(zhí)行動作后會收到匯聚節(jié)點(diǎn)的反饋信息并用于Q 表的更新，經(jīng)過迭代計(jì)算最終得到最佳無人機(jī)飛行軌跡。實(shí)驗(yàn)結(jié)果表明，與連續(xù)式無人機(jī)軌跡規(guī)劃方案相比，非連續(xù)無人機(jī)軌跡規(guī)劃方案在收集的有效數(shù)據(jù)總量上約增加了1 倍，并且隨采集輪數(shù)的增加呈繼續(xù)增多的趨勢，在平均任務(wù)完成時(shí)間上也比連續(xù)式方案縮短近50%，更貼近無人機(jī)軌跡規(guī)劃中實(shí)時(shí)性這一設(shè)計(jì)要求。本文提出的單無人機(jī)輔助無線傳感器網(wǎng)絡(luò)的數(shù)據(jù)收集軌跡規(guī)劃方法較難適用于大規(guī)模無線傳感器網(wǎng)絡(luò)，因此，下一步將研究多無人機(jī)輔助數(shù)據(jù)收集的聯(lián)合軌跡規(guī)劃問題并設(shè)計(jì)相應(yīng)求解算法。