基于流量模式的Q-學(xué)習(xí)路由及其連接調(diào)度

姚銘明, 曹霑懋, 黃啟嵩, 單志龍

(華南師范大學(xué)計(jì)算機(jī)學(xué)院, 廣州 510631)

無線網(wǎng)狀網(wǎng)[1](Wireless Mesh Networks,WMN)以網(wǎng)狀路由器(Mesh Router,MR)、網(wǎng)狀客戶端(Mesh Client,MC)為節(jié)點(diǎn)組成，節(jié)點(diǎn)具有中繼轉(zhuǎn)發(fā)數(shù)據(jù)包的功能. 其中，可以直接接入互聯(lián)網(wǎng)的MR被稱為網(wǎng)關(guān)(Gateway,GW)，GW是連接無線網(wǎng)狀網(wǎng)和互聯(lián)網(wǎng)之間的橋梁，MR和GW一起稱為無線骨干網(wǎng)絡(luò). 每個(gè)從MC發(fā)出的路由請(qǐng)求通過其關(guān)聯(lián)的MR傳輸?shù)焦歉删W(wǎng)絡(luò)中，路由請(qǐng)求在到達(dá)與互聯(lián)網(wǎng)相連的GW前需要通過多個(gè)MR.

由于無線網(wǎng)狀網(wǎng)的靈活性和安裝的簡單性,允許其網(wǎng)絡(luò)基礎(chǔ)設(shè)施的低成本部署. 同時(shí)，無線網(wǎng)狀網(wǎng)可用于擴(kuò)展有線網(wǎng)絡(luò)覆蓋范圍,可實(shí)現(xiàn)隨時(shí)隨地的連接，為無線網(wǎng)狀網(wǎng)的普及提供了良好的基礎(chǔ). 若無線網(wǎng)狀網(wǎng)只配置單個(gè)接口和信道，會(huì)存在一定的局限性，因?yàn)槠涔?jié)點(diǎn)不能同時(shí)發(fā)送和接收數(shù)據(jù)包. 為了提高無線網(wǎng)狀網(wǎng)的性能和容量，每個(gè)節(jié)點(diǎn)可以配備多個(gè)接口和多個(gè)信道. 然而，由于無線信道資源的稀缺性和無線接口所支持的信道數(shù)量有限，在傳輸數(shù)據(jù)時(shí)網(wǎng)絡(luò)性能會(huì)受到干擾和擁塞的嚴(yán)重影響，從而導(dǎo)致了一定的丟包和延遲[2]. 特別地，在無線網(wǎng)狀網(wǎng)中，多個(gè)用戶同時(shí)發(fā)出傳輸請(qǐng)求的情況時(shí)常出現(xiàn)[3]，多對(duì)傳輸請(qǐng)求同時(shí)發(fā)生而導(dǎo)致網(wǎng)絡(luò)波動(dòng)和產(chǎn)生干擾，這個(gè)共有現(xiàn)象稱為多并發(fā)流問題. 在多并發(fā)流下，不同數(shù)據(jù)流所選擇的路徑不可避免地存在節(jié)點(diǎn)交叉或者局部鏈路重疊的情形，易引起數(shù)據(jù)流間的資源競(jìng)爭，搶占節(jié)點(diǎn)資源，從而造成負(fù)載不均衡甚至擁塞現(xiàn)象. 另外，借助無線網(wǎng)絡(luò)的設(shè)備數(shù)量呈指數(shù)級(jí)增長. 電腦、智能手機(jī)和平板設(shè)備等各種智能設(shè)備都需要借助無線網(wǎng)狀網(wǎng)進(jìn)行互聯(lián)網(wǎng)接入[4]，在這些設(shè)備上運(yùn)行的應(yīng)用程序亦呈指數(shù)級(jí)增長，從而導(dǎo)致網(wǎng)絡(luò)中的數(shù)據(jù)量也呈指數(shù)級(jí)增長，加劇了多并發(fā)流問題的嚴(yán)重性.

傳統(tǒng)的路由方案總是基于固定的規(guī)則，只考慮單一的網(wǎng)絡(luò)度量，如吞吐量、丟包率和端到端延遲等，而沒有綜合考慮整個(gè)網(wǎng)絡(luò)環(huán)境情況. 在無線網(wǎng)狀網(wǎng)中，單獨(dú)使用這些指標(biāo)來選擇路由流量的路徑可能不是一個(gè)好的解決方案. 例如，路徑的跳數(shù)可能是最優(yōu)的，但是該路徑不一定是最優(yōu)的，可能具有更多的干擾. 因此，為了能在合理時(shí)間內(nèi)獲得聯(lián)合的最優(yōu)解，我們需要以幾個(gè)指標(biāo)為前提去優(yōu)化無線網(wǎng)狀網(wǎng)中的路徑.

在無線網(wǎng)狀網(wǎng)中，路徑尋找是針對(duì)一個(gè)流量請(qǐng)求，在源節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)之間確定一條可傳輸數(shù)據(jù)連通路徑，該路徑由有限個(gè)兩兩相連節(jié)點(diǎn)的鏈接構(gòu)成，即節(jié)點(diǎn)的序列；信道分配問題是為所確定路徑上的所有鏈接分配可用的信道；調(diào)度是將一個(gè)傳輸時(shí)隙分配給所找路徑上的每一個(gè)鏈接；路由策略是無線網(wǎng)狀網(wǎng)中從每一個(gè)路由請(qǐng)求的初始節(jié)點(diǎn)到目的節(jié)點(diǎn)的路由規(guī)劃. 對(duì)于多并發(fā)流的問題，單從路由、信道分配或者調(diào)度方面考慮都被證明是NP-難問題[5]. 為了解決這個(gè)問題，學(xué)者們從不同的角度提出了解決方案，如：提出了聯(lián)合信道分配和路由的方案來提高網(wǎng)絡(luò)性能[6]；為了保證吞吐量，從服務(wù)質(zhì)量(Quality of Service,QoS)的角度出發(fā)，基于OLSR路由協(xié)議[7]提出一種新的路由方案[8]；為改進(jìn)功率分配、干擾和擁塞，提出了一種貪婪式的算法[9]. 然而，無線網(wǎng)狀網(wǎng)以動(dòng)態(tài)信道和負(fù)載條件為特征，因此，通過靜態(tài)的計(jì)算路徑轉(zhuǎn)發(fā)的流量將無法保持高吞吐量. 而且，在高度動(dòng)態(tài)的環(huán)境下，使用跟隨瞬時(shí)網(wǎng)絡(luò)條件的短期路由策略不能幫助實(shí)現(xiàn)長期最優(yōu)性能，需要智能地根據(jù)這些網(wǎng)絡(luò)環(huán)境自適應(yīng)地選擇鏈路，以實(shí)現(xiàn)網(wǎng)絡(luò)資源的合理使用.

為了解決上述問題, 一個(gè)可行的方法是使用強(qiáng)化學(xué)習(xí)[10]算法. 強(qiáng)化學(xué)習(xí)已經(jīng)應(yīng)用于各種無線網(wǎng)絡(luò)，如無線自組網(wǎng)絡(luò)Ad Hoc[11]、無線傳感器網(wǎng)絡(luò)[12]和認(rèn)知無線網(wǎng)絡(luò)[13]. 除此之外，在無線網(wǎng)狀網(wǎng)路由問題上，有學(xué)者利用強(qiáng)化學(xué)習(xí)得到網(wǎng)絡(luò)性能表現(xiàn)上更優(yōu)的方案，該方案考慮了網(wǎng)關(guān)周圍的關(guān)鍵區(qū)域和多個(gè)網(wǎng)絡(luò)性能度量來尋找路徑[14]；還有從體驗(yàn)質(zhì)量(Quality of Experience,QoE)的角度出發(fā)，利用強(qiáng)化學(xué)習(xí)動(dòng)態(tài)調(diào)整每個(gè)節(jié)點(diǎn)發(fā)送數(shù)據(jù)包的策略[15]. 基于文獻(xiàn)[11-15]的啟發(fā)，在COSS方案[16]的基礎(chǔ)上，本文提出了基于流量模式的Q-學(xué)習(xí)路由與調(diào)度(Q-learning Routing and Scheduling Concerning Traffic Mode,QRST)方案：依托信道分層模型[17]來表示網(wǎng)絡(luò)拓?fù)?，利用?qiáng)化學(xué)習(xí)中的Q-learning算法尋找路徑來完成路由傳輸，再將路由、信道分配和調(diào)度組合起來；根據(jù)網(wǎng)絡(luò)資源的負(fù)載情況，自適應(yīng)地針對(duì)每一個(gè)路由請(qǐng)求學(xué)習(xí)最優(yōu)路由策略，然后進(jìn)行組合調(diào)度優(yōu)化. 最后，通過設(shè)置不同的網(wǎng)絡(luò)配置進(jìn)行虛擬計(jì)算實(shí)驗(yàn)，分析采用QRST、COSS、AODV方案的無線網(wǎng)狀網(wǎng)的網(wǎng)絡(luò)性能.

1 預(yù)備知識(shí)

1.1 強(qiáng)化學(xué)習(xí)的介紹

強(qiáng)化學(xué)習(xí)(Reinforcement Learning,RL)是一種計(jì)算學(xué)習(xí)方法，是智能體不斷與環(huán)境進(jìn)行交互，并根據(jù)經(jīng)驗(yàn)調(diào)整其策略來最大化其長遠(yuǎn)的所有獎(jiǎng)勵(lì)累積值的一個(gè)過程.

智能體是強(qiáng)化學(xué)習(xí)的執(zhí)行個(gè)體，我們可以預(yù)設(shè)參數(shù)讓智能體根據(jù)所處的環(huán)境自主做出決策. 如圖1所示：當(dāng)智能體在t時(shí)刻選擇一個(gè)合適的動(dòng)作at后，環(huán)境的狀態(tài)st變?yōu)闋顟B(tài)st+1，得到獎(jiǎng)勵(lì)rt+1；然后，智能體繼續(xù)選擇下一個(gè)合適的動(dòng)作，環(huán)境的狀態(tài)又會(huì)改變，從而得到新的獎(jiǎng)勵(lì)值，直到完成特定的目標(biāo)為止.

圖1 強(qiáng)化學(xué)習(xí)模型圖解

一個(gè)強(qiáng)化學(xué)習(xí)的系統(tǒng)可以由6個(gè)要素組成：(1)智能體的動(dòng)作a. 具體地，智能體在t時(shí)刻采取的動(dòng)作記為at. (2)環(huán)境的狀態(tài)s. 具體地，在t時(shí)刻的環(huán)境狀態(tài)記為st. (3)環(huán)境的獎(jiǎng)勵(lì)r. 智能體采取動(dòng)作at后得到的獎(jiǎng)勵(lì)記為rt+1，該獎(jiǎng)勵(lì)會(huì)在t+1時(shí)刻得到. (4)智能體的策略π. 策略是一個(gè)智能體的行為模型，是從狀態(tài)到行為的映射函數(shù)，即智能體會(huì)依據(jù)策略π來選擇動(dòng)作. (5)值函數(shù). 值函數(shù)是一個(gè)期望函數(shù)，表示的是智能體在當(dāng)前狀態(tài)s和策略π的累積折扣回報(bào)，一般有2種表示形式. 第1種表示形式為：

(1)

其中，γ為折扣因子，取值為0<γ<1，用來權(quán)重即時(shí)和未來的獎(jiǎng)勵(lì);第2種表示形式為：

(2)

表示的是智能體在當(dāng)前策略π下，給定狀態(tài)s和動(dòng)作a時(shí)的累積折扣回報(bào). (6)模型. 模型是用來預(yù)測(cè)環(huán)境下一步可能發(fā)生的變化的一套描述系統(tǒng)，環(huán)境狀態(tài)的轉(zhuǎn)化模型可以表示為一個(gè)概率模型，是在狀態(tài)s下采取動(dòng)作a后轉(zhuǎn)到下一個(gè)狀態(tài)s′的概率的一個(gè)集合.

一般來說，決策是由一個(gè)智能體在與環(huán)境交互的過程中，通過反復(fù)學(xué)習(xí)做出的. 最終目標(biāo)是讓智能體學(xué)習(xí)到一個(gè)最優(yōu)策略，使其在與環(huán)境交互過程中的累積獎(jiǎng)勵(lì)最大化. 智能體面臨的一個(gè)挑戰(zhàn)是利用與探索：智能體必須利用以前學(xué)習(xí)的知識(shí)，但又必須探索其環(huán)境中的新動(dòng)作和狀態(tài)，以便尋找更好的策略.

1.2 網(wǎng)絡(luò)模型的介紹

本文采用的是笛卡爾乘積(Cartesian Product of Graph,CPG)模型[18]，以便在無線網(wǎng)狀網(wǎng)中對(duì)多并發(fā)流的路徑進(jìn)行討論和研究. 多并發(fā)流下的無線網(wǎng)狀網(wǎng)結(jié)構(gòu)可用Γ={G,I,Ω,ξ,{(fi,di)}}來表示，其中：

(1)G=(V,E)為一個(gè)無線網(wǎng)絡(luò)的網(wǎng)狀拓?fù)浣Y(jié)構(gòu)圖，其中|V|代表節(jié)點(diǎn)數(shù)量，|E|代表邊的數(shù)量；

(2)I為G上節(jié)點(diǎn)之間的無線干擾關(guān)系；

(3)Ω={c1,c2,…,cq}為網(wǎng)絡(luò)拓?fù)鋱D上可用正交信道的集合，其中q為可用正交信道的數(shù)量；

(4)ξ為節(jié)點(diǎn)接口數(shù)量；

(5){(fi,di)}(i=1,2,…,ρ)為多個(gè)源節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)對(duì)的集合；

(6)Λ={λi}={(fi,di),zi}為列表{(fi,di)}相對(duì)應(yīng)的傳輸請(qǐng)求隊(duì)列，zi>0為數(shù)據(jù)的大小.

在該無線網(wǎng)狀網(wǎng)模型中，I的干擾判定條件為：

(1) 2個(gè)不同的發(fā)射節(jié)點(diǎn)sender_node間的距離不小于2跳；

(2) 2個(gè)不同的接收節(jié)點(diǎn)receiver_node間的距離不小于1跳；

(3) 發(fā)射節(jié)點(diǎn)sender_node與接收節(jié)點(diǎn)receiver_node間的距離大于1跳.

同一信道中的可共存條件為(1)∧(2)∧(3).

2 QRST方案的設(shè)計(jì)

本文在COSS方案的基礎(chǔ)上，針對(duì)多并發(fā)流問題提出了一個(gè)基于網(wǎng)絡(luò)負(fù)載的智能調(diào)度方案. 該方案由路由方案和調(diào)度方案組成.

2.1 路由方案的設(shè)計(jì)

首先，獲取正交信道的數(shù)量g，CPG網(wǎng)絡(luò)模型將網(wǎng)絡(luò)拓?fù)浞譃間個(gè)虛擬的網(wǎng)絡(luò)層，每層的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)相同，但各個(gè)節(jié)點(diǎn)之間所屬的正交信道不同. 每個(gè)節(jié)點(diǎn)上有多個(gè)信道和接口，節(jié)點(diǎn)的身份轉(zhuǎn)化為g個(gè)虛擬網(wǎng)絡(luò)層信道差異的節(jié)點(diǎn)，虛擬計(jì)算時(shí)仍把分層的節(jié)點(diǎn)看作同一個(gè)節(jié)點(diǎn). 然后，為每一條路徑分配可用信道時(shí)，需逐層檢查當(dāng)前網(wǎng)絡(luò)層下信道的可用性，若該路徑上的當(dāng)前鏈接在當(dāng)前網(wǎng)絡(luò)層下能滿足同一信道中鏈接可共存條件的干擾關(guān)系I，則將當(dāng)前網(wǎng)絡(luò)層所屬的信道分配給鏈接.

QRST方案中，在路徑發(fā)現(xiàn)的階段，對(duì)給定路由請(qǐng)求的節(jié)點(diǎn)對(duì)(fi,di)，采用強(qiáng)化學(xué)習(xí)中的Q-lear-ning算法來尋找路徑. Q-Learning算法是一種使用時(shí)序差分求解強(qiáng)化學(xué)習(xí)控制問題的方法，在Q-Learning算法中，將Q值Q(s,a)定義為在狀態(tài)s下選擇行為a并遵循最優(yōu)策略的估計(jì)值. 因此，Q-Learning算法的最終目標(biāo)是通過估計(jì)其Q值來尋找最優(yōu)策略. 在Q-Learning算法中，學(xué)習(xí)到Q值，然后使用即時(shí)獎(jiǎng)勵(lì)和折扣獎(jiǎng)勵(lì)進(jìn)行更新，并保存在一個(gè)大小為|s|*|a|的狀態(tài)價(jià)值函數(shù)表中，其中，|s|為狀態(tài)的數(shù)量，|a|為動(dòng)作的數(shù)量. 在狀態(tài)中選擇的動(dòng)作的Q值更新如下：

Q(st,at))，

(3)

其中，α(0<α<1)表示學(xué)習(xí)率，γ(0<γ<1)表示折扣系數(shù). 如果α=1，則智能體將會(huì)忘記其先前學(xué)習(xí)的Q值，并用最新估計(jì)的獎(jiǎng)勵(lì)替換該Q值.γ越接近于0，智能體越注重下一步的獎(jiǎng)勵(lì)；γ越接近于1，智能體越注重整體的獎(jiǎng)勵(lì)情況. 更新迭代在利用與探索之間的折衷采用ε-greedy策略，該策略通過設(shè)置一個(gè)較小的ε值，使用1-ε的概率貪婪地選擇目前認(rèn)為是最大行為價(jià)值的動(dòng)作，而用ε的概率隨機(jī)從所有m個(gè)可選動(dòng)作中選擇一個(gè). 用公式表示為：

(4)

ε-greedy策略的優(yōu)點(diǎn)是：當(dāng)時(shí)間趨于無窮大時(shí)，該策略可以保證每個(gè)動(dòng)作被無限次地采樣，這是Q-learning算法收斂的必要條件. 利用Q-learning算法尋找路徑流程如算法1所示.

算法1Q-learning尋找路徑算法

輸入：迭代次數(shù)T,狀態(tài)s,動(dòng)作a,學(xué)習(xí)率α,折扣系數(shù)γ,探索率ε

輸出：狀態(tài)價(jià)值函數(shù)表

初始化s和狀態(tài)價(jià)值函數(shù)表

forTdo

使用ε-greedy策略，在狀態(tài)s下選擇動(dòng)作a，從而確定下一跳節(jié)點(diǎn)，并獲得新狀態(tài)s′和獎(jiǎng)勵(lì)值r

更新Q(s,a):

s=s′

ifs′是目標(biāo)節(jié)點(diǎn)

結(jié)束當(dāng)前迭代

else

繼續(xù)尋找目標(biāo)節(jié)點(diǎn)

end if

end for

rt(st,at)=-Cm(sender_node,receiver_node)+

Ce(sender_node,receiver_node)，

(5)

其中，Cm(sender_node,receiver_node)代表發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)之間所有信道的數(shù)量，也是CGP模型的虛擬層層數(shù)，Ce(sender_node,receiver_node)代表發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)之間所有被占用的信道數(shù)量. 可用資源越多的節(jié)點(diǎn)的獎(jiǎng)勵(lì)值越大，反之亦然. 在QRST方案中，能根據(jù)網(wǎng)絡(luò)負(fù)載來尋找路徑，避免節(jié)點(diǎn)負(fù)載過重的區(qū)域，智能地選擇負(fù)載較輕的節(jié)點(diǎn)，從而避免資源競(jìng)爭的現(xiàn)象.

QRST方案的路由模型(圖2)尋找路徑的步驟如下：首先，根據(jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)建立強(qiáng)化學(xué)習(xí)智能體和初始化狀態(tài)價(jià)值函數(shù)表：將沒有相連的節(jié)點(diǎn)賦予一個(gè)非常大的負(fù)值，以確保智能體無法到達(dá)相連的節(jié)點(diǎn)，其他相連節(jié)點(diǎn)的Q值初始化為0. 然后，智能體將路由請(qǐng)求作為輸入，通過源節(jié)點(diǎn)和中繼節(jié)點(diǎn)嘗試尋找目的節(jié)點(diǎn)，每當(dāng)節(jié)點(diǎn)i向其鄰居節(jié)點(diǎn)j發(fā)送數(shù)據(jù)包時(shí)，節(jié)點(diǎn)j通過反饋信號(hào)做出響應(yīng)，該反饋信號(hào)表示其到達(dá)下一個(gè)鄰居節(jié)點(diǎn)的估計(jì)值. 在QRST方案中，反饋的Q值是節(jié)點(diǎn)i到節(jié)點(diǎn)j的網(wǎng)絡(luò)資源剩余量. 節(jié)點(diǎn)i收到反饋后，智能體利用式(3)來更新當(dāng)前位置對(duì)應(yīng)狀態(tài)價(jià)值函數(shù)表中的Q值，即Q(i,j)，隨后繼續(xù)為下一個(gè)節(jié)點(diǎn)尋找其鄰居節(jié)點(diǎn)，直到找到目的節(jié)點(diǎn). 再根據(jù)設(shè)定好的迭代次數(shù)，繼續(xù)重復(fù)為該路由請(qǐng)求尋找路徑，從而根據(jù)網(wǎng)絡(luò)資源迭代收斂狀態(tài)價(jià)值函數(shù)表，尋找到一條最優(yōu)路徑. 路徑上的每條鏈路都與網(wǎng)絡(luò)資源的剩余量相關(guān)聯(lián)，對(duì)于狀態(tài)價(jià)值函數(shù)表中每個(gè)狀態(tài)-動(dòng)作對(duì)，在經(jīng)過采樣之后，計(jì)算其Q值，并將此Q值用于估計(jì)沿著路由向目的節(jié)點(diǎn)發(fā)送數(shù)據(jù)包時(shí)的網(wǎng)絡(luò)資源量. 由于使用了Q值的查找，因此，QRST方案的收斂性得到了保證[18].

圖2 QRST方案的路由模型

2.2 調(diào)度方案的設(shè)計(jì)

在QRST方案中，首先，根據(jù)輸入的每一個(gè)路由請(qǐng)求λi，為其源節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)對(duì)(fi,di)找到合適的路徑，該路徑由一個(gè)或多個(gè)兩兩相連的節(jié)點(diǎn)對(duì)構(gòu)成；然后，為每個(gè)節(jié)點(diǎn)對(duì)分配信道和時(shí)隙來傳輸數(shù)據(jù)，在一個(gè)時(shí)隙下，激活更多的鏈接以傳輸更多的數(shù)據(jù)包和路由請(qǐng)求[19]，從而有效利用網(wǎng)絡(luò)資源.

為了能夠清晰地闡述該調(diào)度方案，需要提前定義若干符號(hào). 記Τ為網(wǎng)絡(luò)拓?fù)涞母轮芷?，Li為節(jié)點(diǎn)對(duì)(fi,di)的路徑長度，P為所有可兼容路徑的集合，F(xiàn)c(j)為判斷當(dāng)前節(jié)點(diǎn)j是否有可用信道的函數(shù). QRST方案的目標(biāo)是在Γ中實(shí)現(xiàn)網(wǎng)絡(luò)資源的最大化利用，即最大化多并發(fā)流鏈接的數(shù)量. 調(diào)度方案的具體流程如下：

(1)在調(diào)度開始前，先收集拓?fù)渚W(wǎng)絡(luò)的信息，包括節(jié)點(diǎn)狀態(tài)、傳輸請(qǐng)求和拓?fù)浣Y(jié)構(gòu)等；

(2)在調(diào)度時(shí)，將周期Τ分為多個(gè)時(shí)隙ti(ti=1,2,…,T). 在每個(gè)時(shí)隙中，方案先用Q-lear-ning算法為每一個(gè)路由請(qǐng)求尋找路徑，然后逐一遍歷未加入集合P的路徑是否為當(dāng)前時(shí)隙下的可兼容路徑. 若滿足同一信道中鏈接的干擾關(guān)系I，則將該路徑加入P；

(3)若當(dāng)前網(wǎng)絡(luò)資源已經(jīng)無法分配信道，則進(jìn)入下一個(gè)時(shí)隙，再逐一檢查未加入P的所有路徑，直到所有路徑都加入到P.

參考文獻(xiàn)[19],該調(diào)度方案(算法2)將網(wǎng)絡(luò)拓?fù)涞母轮芷诜譃槎鄠€(gè)時(shí)隙，通過逐一遍歷所有路徑，為符合可兼容條件的路徑分配信道和時(shí)隙，從而實(shí)現(xiàn)所有路徑的組合優(yōu)化調(diào)度，最大化同一時(shí)隙下可兼容路徑的數(shù)量，提高了網(wǎng)絡(luò)資源的利用. 通過這種方式組合正交信道上若干條無干擾鏈路構(gòu)成的路徑被稱為可兼容路徑. 該路徑上的所有鏈路都分配了合適的信道，避免了無線干擾I，使其不會(huì)與先前已分配好資源的路徑產(chǎn)生沖突，以實(shí)現(xiàn)多并發(fā)傳輸.

算法2基于網(wǎng)絡(luò)負(fù)載的調(diào)度方案

輸入：網(wǎng)絡(luò)結(jié)構(gòu)Γ

輸出：可兼容路徑集合P

初始化P

初始化信道和接口

forTdo

for 路由請(qǐng)求集合Λdo

Q-learning算法為給定路由請(qǐng)求的節(jié)點(diǎn)對(duì)(fi,di)尋找路徑;

for 路徑的鏈接Ldo

if 兩節(jié)點(diǎn)間存在可用信道

在時(shí)隙t下，為該鏈接分配信道

else

不分配信道，且將該鏈接放到下一個(gè)時(shí)隙t+1下

end if

end for

if 路由請(qǐng)求(fi，di)所有的鏈接都分配了信道

將該信道加入P中

end if

end for

end for

3 虛擬計(jì)算實(shí)驗(yàn)與結(jié)果分析

本節(jié)通過python程序虛擬計(jì)算，比較在不同網(wǎng)絡(luò)資源配置和路由請(qǐng)求下，分別采用QRST、AODV、COSS方案的無線網(wǎng)狀網(wǎng)的網(wǎng)絡(luò)性能變化.

實(shí)驗(yàn)場(chǎng)景是在1 000 m*1 000 m的區(qū)域范圍內(nèi)隨機(jī)生成36個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)間的傳輸距離為100 m，如圖3所示.

圖3 36個(gè)節(jié)點(diǎn)的隨機(jī)網(wǎng)絡(luò)拓?fù)鋱D

為保證實(shí)驗(yàn)的準(zhǔn)確性，每組實(shí)驗(yàn)都要進(jìn)行10次，每次實(shí)驗(yàn)條件中僅路由請(qǐng)求的節(jié)點(diǎn)對(duì)不同，最終取10次實(shí)驗(yàn)結(jié)果的平均值以避免隨機(jī)性. 在Python虛擬計(jì)算實(shí)驗(yàn)下，每一跳可以傳輸一個(gè)數(shù)據(jù)包，所需時(shí)間均為1個(gè)時(shí)隙(5 ms)，1個(gè)時(shí)間周期為0.5 s(100個(gè)時(shí)隙). 具體參數(shù)如下：可用接口數(shù)量R分別為4、8、12、16、20，可用信道數(shù)量分別為8、16、32，學(xué)習(xí)率α=0.01，探索率ε=0.1，折扣因子γ=0.9，數(shù)據(jù)包大小為1 MB，數(shù)據(jù)包個(gè)數(shù)為250個(gè)，鏈路容量為200 MB/s，傳輸距離為150 m.

在性能指標(biāo)上，采用能夠反映無線網(wǎng)狀網(wǎng)性能的指標(biāo)：無線網(wǎng)狀網(wǎng)的平均吞吐量、平均激活鏈路數(shù)量和路由請(qǐng)求傳輸完成時(shí)間. 這些指標(biāo)的具體定義如下：

(1)平均吞吐量：單位時(shí)間內(nèi)無線網(wǎng)狀網(wǎng)中所有目標(biāo)節(jié)點(diǎn)所接收到的數(shù)據(jù)總量. 該指標(biāo)可以有效衡量網(wǎng)絡(luò)的性能：平均吞吐量越高，則表示網(wǎng)絡(luò)性能越好.

(2)平均激活鏈路數(shù)量：單位時(shí)間內(nèi)無線網(wǎng)狀網(wǎng)中激活的鏈路數(shù)量. 該指標(biāo)為網(wǎng)絡(luò)中并發(fā)的鏈路數(shù)量，可以有效衡量網(wǎng)絡(luò)性能.

(3)路由請(qǐng)求傳輸完成時(shí)間：無線網(wǎng)狀網(wǎng)中所有路由請(qǐng)求從開始傳輸數(shù)據(jù)到全部數(shù)據(jù)被接收所需的時(shí)間. 該指標(biāo)可以有效地評(píng)估網(wǎng)絡(luò)的承載能力:傳輸所需時(shí)間越短，說明網(wǎng)絡(luò)在單位時(shí)間內(nèi)傳輸?shù)臄?shù)據(jù)量越多，單位時(shí)間內(nèi)能夠承載的數(shù)據(jù)流數(shù)量越多，網(wǎng)絡(luò)承載能力越強(qiáng).

3.1 不同流量模式下的網(wǎng)絡(luò)性能表現(xiàn)

在固定網(wǎng)絡(luò)資源配置下，通過改變隨機(jī)路由請(qǐng)求的數(shù)量，分析采用QRST、COSS和AODV方案的無線網(wǎng)狀網(wǎng)的性能表現(xiàn). 由在不同數(shù)量的路由請(qǐng)求下的平均吞吐量(圖4)可知：采用QRST方案的平均吞吐量明顯高于采用COSS、AODV方案的，這表明QRST方案充分利用了各個(gè)時(shí)隙下的網(wǎng)絡(luò)資源來傳輸數(shù)據(jù)包，同時(shí)能夠有效避免高負(fù)載現(xiàn)象的出現(xiàn)；隨著路由請(qǐng)求數(shù)量的增加，QRST方案的性能優(yōu)越性愈加明顯.

圖4 采用3種方案的無線網(wǎng)狀網(wǎng)在不同數(shù)量路由請(qǐng)求下的平均吞吐量(|R|=16∧|C|=32)

由相同的網(wǎng)絡(luò)配置下的平均激活鏈路數(shù)量(圖5)可知：(1)平均激活鏈路數(shù)量的曲線趨勢(shì)與平均吞吐量的大體一致；(2)采用QRST方案的平均激活鏈路數(shù)量高于采用COSS、AODV方案的，其原因是QRST方案充分利用了網(wǎng)絡(luò)資源，為每條鏈路選擇合適的分配信道，并發(fā)的鏈路之間不產(chǎn)生干擾，從而使每條鏈路都能高效率地傳輸數(shù)據(jù).

圖5 采用3種方案的無線網(wǎng)狀網(wǎng)在不同數(shù)量路由請(qǐng)求下的平均激活鏈路數(shù)量(|R|=16∧|C|=32)

由相同網(wǎng)絡(luò)配置下的傳輸時(shí)間(圖6)可知：采用QRST方案的傳輸時(shí)間比采用另外2種方案的略長一些，其原因可能是平均激活鏈路的數(shù)量多了，需略微犧牲傳輸時(shí)間來換取更高的吞吐量和激活的鏈路數(shù)量.

圖6 采用3種方案的無線網(wǎng)狀網(wǎng)在不同數(shù)量路由請(qǐng)求下的傳輸時(shí)間(|R|=16∧|C|=32)

為了探討QRST方案中Q-learning算法的迭代次數(shù)對(duì)網(wǎng)絡(luò)性能表現(xiàn)的影響，將迭代次數(shù)分別設(shè)置為300、400、500次. 由圖7可知：在足夠多的迭代次數(shù)下，采用QRST方案的無線網(wǎng)狀網(wǎng)在網(wǎng)絡(luò)性能表現(xiàn)上并沒有太大變化.

圖7 采用QRST方案的無線網(wǎng)狀網(wǎng)在不同迭代次數(shù)下的多組路由請(qǐng)求的平均吞吐量(|R|=16∧|C|=32)

在確定網(wǎng)絡(luò)配置和流量模式下，分析QRST方案中學(xué)習(xí)過程對(duì)網(wǎng)絡(luò)性能的影響. 由圖8可知：(1)前150次迭代過程的階段中，采用QRST方案的平均吞吐量會(huì)有一定的波動(dòng)，這是因?yàn)榇藭r(shí)Q還未完全收斂，所以會(huì)有不同的路徑，從而影響網(wǎng)絡(luò)性能的表現(xiàn)；(2)到了150次的學(xué)習(xí)次數(shù)后，平均吞吐量的表現(xiàn)逐漸穩(wěn)定在一個(gè)范圍內(nèi)波動(dòng).

圖8 30對(duì)路由請(qǐng)求的學(xué)習(xí)過程對(duì)平均吞吐量的影響(|R|=4∧|C|=8)

3.2 不同網(wǎng)絡(luò)資源配置下的網(wǎng)絡(luò)性能表現(xiàn)

在確定隨機(jī)路由請(qǐng)求數(shù)量為30對(duì)的情況下，將網(wǎng)絡(luò)資源配置設(shè)置為可控變量，分析采用QRST、COSS、AODV方案的無線網(wǎng)狀網(wǎng)在不同網(wǎng)絡(luò)資源配置下的平均吞吐量.

由圖9至圖11可知：

圖9 |C|=8且不同接口數(shù)時(shí)采用3種方案的無線網(wǎng)狀網(wǎng)的平均吞吐量

圖10 |C|=16且不同接口數(shù)時(shí)采用3種方案的無線網(wǎng)狀網(wǎng)的平均吞吐量

圖11 |C|=32且不同接口數(shù)時(shí)采用3種方案的無線網(wǎng)狀網(wǎng)的平均吞吐量

(1)當(dāng)|C|=8時(shí)，采用QRST方案的平均吞吐量始終低于采用COSS、AODV方案的. 其原因是QRST方案中Q-learning算法尋找路徑是采用信道數(shù)量作為獎(jiǎng)勵(lì)值，所以在信道資源匱乏的時(shí)候，采用QRST方案的平均吞吐量要低于采用COSS、AODV方案的.

(2)在|C|=16時(shí)，采用QRST方案的平均吞吐量與采用COSS方案的相差無幾，兩者均稍高于采用AODV方案的；隨著接口數(shù)量的增加，采用QRST方案的平均吞吐量高于采用COSS、AODV方案的.

(3)在|C|=32時(shí)，隨著接口數(shù)量的增加，QRST方案所帶來的性能提升要優(yōu)于另外2種方案：在|R|=12時(shí)，采用QRST方案的平均吞吐量已高于采用COSS、AODV方案的，而且是大幅度的提升，說明在|R|=12時(shí)，QRST方案已經(jīng)能充分利用網(wǎng)絡(luò)資源，而采用COSS、AODV方案的平均吞吐量要在|R|=16時(shí)才能有如此大幅的提升，但仍低于采用QRST方案的，說明QRST方案在網(wǎng)絡(luò)資源充足的前提下，能夠較好地應(yīng)對(duì)無線網(wǎng)狀網(wǎng)中多并發(fā)流的問題.

4 結(jié)論

為了解決無線網(wǎng)狀網(wǎng)中多并發(fā)流這一現(xiàn)象引發(fā)的路由和網(wǎng)絡(luò)資源配置緊張的問題，在COSS方案的基礎(chǔ)上，本文提出了基于流量的Q-學(xué)習(xí)路由與調(diào)度方案(QRST). 該方案首先獲取網(wǎng)絡(luò)的基本信息，包括拓?fù)浣Y(jié)構(gòu)和路由請(qǐng)求；然后使用強(qiáng)化學(xué)習(xí)中的Q-learning算法來尋找路徑；基于所得到的路徑，為路由分配無干擾的信道，形成可兼容路徑；最后組合調(diào)度所有可兼容路徑完成傳輸. 虛擬計(jì)算實(shí)驗(yàn)表明：QRST方案在不同流量模式下能取得較好的網(wǎng)絡(luò)性能，在一定的網(wǎng)絡(luò)配置下的網(wǎng)絡(luò)性能也優(yōu)于采用AODV、COSS方案的.