• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

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

    2021-08-30 08:20:58姚銘明曹霑懋黃啟嵩單志龍
    關(guān)鍵詞:網(wǎng)狀網(wǎng)絡(luò)資源路由

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

    (華南師范大學(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方案的.

    猜你喜歡
    網(wǎng)狀網(wǎng)絡(luò)資源路由
    不同針灸療法治療尋常痤瘡的網(wǎng)狀Meta分析
    SWRH82B熱軋盤條心部異常網(wǎng)狀滲碳體組織分析及改善措施
    昆鋼科技(2022年1期)2022-04-19 11:36:16
    8種針灸療法治療原發(fā)性痛經(jīng)的網(wǎng)狀Meta分析
    探究路由與環(huán)路的問題
    網(wǎng)絡(luò)資源在高中班級(jí)管理中的運(yùn)用
    談網(wǎng)絡(luò)資源在大學(xué)計(jì)算機(jī)教學(xué)中的應(yīng)用
    PRIME和G3-PLC路由機(jī)制對(duì)比
    二維網(wǎng)狀配聚物[Co(btmb)2(SCN)2]n的合成、晶體結(jié)構(gòu)和Pb2+識(shí)別性能
    WSN中基于等高度路由的源位置隱私保護(hù)
    eNSP在路由交換課程教學(xué)改革中的應(yīng)用
    河南科技(2014年5期)2014-02-27 14:08:56
    新宁县| 比如县| 冕宁县| 昭觉县| 晋城| 青海省| 阿图什市| 元氏县| 雅江县| 太原市| 呈贡县| 亳州市| 甘孜县| 嘉义市| 精河县| 广东省| 江陵县| 依兰县| 朝阳区| 凉城县| 来安县| 韩城市| 秀山| 永善县| 禹城市| 阳东县| 屯门区| 黄石市| 卢湾区| 东港市| 美姑县| 岑溪市| 晋中市| 茂名市| 台中县| 天峻县| 德清县| 恩平市| 赤城县| 渭南市| 内乡县|