杜艾芊，趙海濤，劉南杰

(1.南京郵電大學(xué) 通信與信息工程學(xué)院,江蘇 南京 210003；2.南京郵電大學(xué) 網(wǎng)絡(luò)基因工程研究所,江蘇 南京 210003)

車載通信中基于Q學(xué)習(xí)的信道接入技術(shù)研究

杜艾芊1,2，趙海濤1,2，劉南杰1,2

(1.南京郵電大學(xué) 通信與信息工程學(xué)院,江蘇 南京 210003；2.南京郵電大學(xué) 網(wǎng)絡(luò)基因工程研究所,江蘇 南京 210003)

針對(duì)基于IEEE 802.11p協(xié)議的車載網(wǎng)絡(luò)MAC層DCF(分布式協(xié)調(diào)功能)信道接入方法存在數(shù)據(jù)包接收率低、時(shí)延高、可擴(kuò)展性差等問題，提出一種基于Q學(xué)習(xí)的CW動(dòng)態(tài)調(diào)整算法-QL-CWmin算法。區(qū)別于現(xiàn)有的BEB算法，通過利用Q學(xué)習(xí)，網(wǎng)絡(luò)節(jié)點(diǎn)(Agent)能夠不斷地與周圍環(huán)境進(jìn)行交互學(xué)習(xí)，根據(jù)學(xué)習(xí)結(jié)果動(dòng)態(tài)地調(diào)整競(jìng)爭(zhēng)窗口(CW)，使節(jié)點(diǎn)總能以最佳的CW(從周圍環(huán)境中獲得獎(jiǎng)賞值最大時(shí)所選的CW大小)接入信道，以減少數(shù)據(jù)幀碰撞、降低端到端傳輸時(shí)延。仿真結(jié)果表明，采用QL-CWmin算法的通信節(jié)點(diǎn)能快速適應(yīng)車聯(lián)網(wǎng)的未知環(huán)境，數(shù)據(jù)包接收率和數(shù)據(jù)包傳輸時(shí)延得到了有效改善，同時(shí)該算法能為節(jié)點(diǎn)接入信道提供更高的公平性，適用于各種不同負(fù)載程度的網(wǎng)絡(luò)環(huán)境。

車載網(wǎng)絡(luò)；BEB算法；競(jìng)爭(zhēng)窗口；Q學(xué)習(xí)算法；分布式協(xié)調(diào)功能

0 引 言

近年來，隨著交通運(yùn)輸行業(yè)的迅速發(fā)展，汽車數(shù)量急劇增加。汽車為人們?nèi)粘３鲂袔砹吮憷?，但也出現(xiàn)了安全和交通擁堵等各種問題。20世紀(jì)80年代，美國(guó)加利福尼亞大學(xué)首次提出了智能交通系統(tǒng)(ITS)的概念，用以提高交通運(yùn)輸效率、緩解交通擁塞、減少交通事故。在智能交通系統(tǒng)和無線通信技術(shù)高速發(fā)展的今天，車聯(lián)網(wǎng)應(yīng)運(yùn)而生，它是繼互聯(lián)網(wǎng)、物聯(lián)網(wǎng)之后的另一個(gè)未來智慧城市的標(biāo)志。車聯(lián)網(wǎng)中，道路車輛和路邊基礎(chǔ)設(shè)施都安裝有短程無線收發(fā)器，具有無線通信功能，所以可形成一個(gè)無線網(wǎng)絡(luò)，即車載自組織網(wǎng)(VANET)。VANET是移動(dòng)自組織網(wǎng)的子類，沒有固定的拓?fù)浣Y(jié)構(gòu)，車輛可通過V2V(車與車)通信或V2I(車與路邊基礎(chǔ)設(shè)施)通信獲取信息和服務(wù)。VANET通過車-車通信和車-路通信實(shí)現(xiàn)人-車-路的協(xié)同，有效改善了交通安全，提高了交通效率，為用戶提供娛樂和Internet接入服務(wù)等。

IEEE802.11p又稱WAVE(WirelessAccessintheVehicularEnvironment)，主要用于車載通信，是由IEEE802.11標(biāo)準(zhǔn)擴(kuò)充的通信協(xié)議。IEEE802.11p針對(duì)車載環(huán)境對(duì)IEEE802.11的物理層和MAC層的相關(guān)參數(shù)做了些許調(diào)整，因而能更適用于車載環(huán)境中的無線通信。IEEE802.11p是WAVE協(xié)議棧的底層協(xié)議，已廣泛應(yīng)用于V2V通信。在任一網(wǎng)絡(luò)環(huán)境中，通信協(xié)議棧的重要因素之一就是MAC層，而IEEE802.11pMAC層主要解決的是車輛對(duì)信道接入的競(jìng)爭(zhēng)問題，它決定了某一時(shí)刻允許哪一節(jié)點(diǎn)接入無線信道。由于節(jié)點(diǎn)的高速移動(dòng)性、通信環(huán)境的快速變化性及節(jié)點(diǎn)密度和節(jié)點(diǎn)分布的多變性等，對(duì)VANETs共享無線信道的接入控制提出了挑戰(zhàn)。因此，設(shè)計(jì)高可靠性的MAC協(xié)議對(duì)VANETs尤為重要。為VANET環(huán)境設(shè)計(jì)MAC協(xié)議所面臨的挑戰(zhàn)主要有：在車輛位置和信道特征不斷變化的VANET中，實(shí)現(xiàn)既高效又公平的信道接入；對(duì)不同密度的交通流具有可擴(kuò)展性；能滿足各種不同的應(yīng)用需求。

1 相關(guān)文獻(xiàn)

文獻(xiàn)[1]提出一種基于鄰居節(jié)點(diǎn)數(shù)估計(jì)的最小競(jìng)爭(zhēng)窗口調(diào)整算法-AdaptiveCWmin。算法改變了CW的調(diào)整規(guī)則，并根據(jù)網(wǎng)絡(luò)信道的使用情況動(dòng)態(tài)地調(diào)整CWmin。通過估計(jì)車載網(wǎng)中的競(jìng)爭(zhēng)節(jié)點(diǎn)數(shù)來動(dòng)態(tài)地選擇合適的CWmin，若數(shù)據(jù)傳輸成功，則根據(jù)競(jìng)爭(zhēng)節(jié)點(diǎn)數(shù)確定CWmin；若失敗，則通過估計(jì)車輛密度來控制競(jìng)爭(zhēng)窗口的增加。同時(shí)還推導(dǎo)出最大退避階數(shù)、信道由于碰撞被檢測(cè)為繁忙的平均時(shí)間和競(jìng)爭(zhēng)節(jié)點(diǎn)數(shù)這三個(gè)參數(shù)與最優(yōu)CWmin的函數(shù)關(guān)系，節(jié)點(diǎn)成功發(fā)送數(shù)據(jù)后，根據(jù)函數(shù)計(jì)算出適應(yīng)車載網(wǎng)絡(luò)狀況的最優(yōu)CWmin值。利用文中提出的算法在數(shù)據(jù)包重傳之后選擇合理的CW，縮短了競(jìng)爭(zhēng)節(jié)點(diǎn)等待重傳的時(shí)間，增加了網(wǎng)絡(luò)吞吐量。

文獻(xiàn)[2]提出了基于統(tǒng)計(jì)次數(shù)的退避算法-newBEB和基于相對(duì)距離的退避算法-RBA。newBEB算法中設(shè)定了一個(gè)門限值，即發(fā)送節(jié)點(diǎn)傳輸成功和傳輸失敗的最大次數(shù)。當(dāng)節(jié)點(diǎn)連續(xù)發(fā)送成功的次數(shù)超過傳輸成功的最大次數(shù)時(shí)，就增加競(jìng)爭(zhēng)窗口值，降低其競(jìng)爭(zhēng)信道的能力；而當(dāng)節(jié)點(diǎn)連續(xù)發(fā)送失敗的次數(shù)超過傳輸失敗的最大次數(shù)時(shí)，就減少競(jìng)爭(zhēng)窗口值，增強(qiáng)其競(jìng)爭(zhēng)信道的能力。通過仿真對(duì)比分析，newBEB算法有效提高了節(jié)點(diǎn)接入信道的公平性。RBA算法中，每個(gè)節(jié)點(diǎn)根據(jù)自己與鄰居節(jié)點(diǎn)距離的平均值動(dòng)態(tài)地調(diào)整競(jìng)爭(zhēng)窗口的大小，仿真結(jié)果表明RBA算法提高了節(jié)點(diǎn)接入信道的公平性，降低了丟包率，在一定程度上提高了網(wǎng)絡(luò)吞吐量。

文獻(xiàn)[3]提出一種CW的控制方法-DBM-ACW方法(基于密度調(diào)整CW的方法)。根據(jù)信道擁塞的嚴(yán)重程度，選擇不同的CW值倍乘系數(shù)，或重設(shè)為CWmin。信道十分擁塞時(shí)，CW值的倍乘系數(shù)選擇上限值，可減少節(jié)點(diǎn)選擇相同退避數(shù)的概率；當(dāng)信道密度降低時(shí)，CW值的倍乘系數(shù)選擇下限值或重設(shè)為CWmin，避免節(jié)點(diǎn)在信道占用率較低時(shí)等待較長(zhǎng)的時(shí)間接入信道。經(jīng)仿真對(duì)比分析，文中提出方法在網(wǎng)絡(luò)密度較大時(shí)，性能優(yōu)勢(shì)尤為突出。

文獻(xiàn)[4]提出一種基于距離動(dòng)態(tài)調(diào)整CW值的方法，適用于在網(wǎng)絡(luò)負(fù)載較重的車載自組織網(wǎng)中廣播實(shí)時(shí)性緊急消息。文中推導(dǎo)出某節(jié)點(diǎn)和前一節(jié)點(diǎn)之間的距離d和動(dòng)態(tài)競(jìng)爭(zhēng)窗口CWd之間的關(guān)系，利用這一關(guān)系為不斷移動(dòng)的車輛節(jié)點(diǎn)動(dòng)態(tài)地分配不同的CW值，可減少由于碰撞需要重傳數(shù)據(jù)包的次數(shù)。此外，還能降低數(shù)據(jù)包碰撞概率、端到端時(shí)延及網(wǎng)絡(luò)負(fù)載等，最終使帶寬得到有效利用。仿真結(jié)果表明，此方法在高速公路交通流中就吞吐量、端到端時(shí)延和網(wǎng)絡(luò)負(fù)載而言，網(wǎng)絡(luò)性能得到有效改善。

傳統(tǒng)的退避算法雖然解決了信道競(jìng)爭(zhēng)的問題，但同時(shí)也存在一定的缺陷。節(jié)點(diǎn)每成功發(fā)送一次數(shù)據(jù)，就把當(dāng)前的CW降到最小值，使節(jié)點(diǎn)誤以為一次發(fā)送成功就表示當(dāng)前信道競(jìng)爭(zhēng)情況不激烈，同樣，一次發(fā)送失敗就認(rèn)為當(dāng)前信道競(jìng)爭(zhēng)激烈，碰撞增加，相應(yīng)的競(jìng)爭(zhēng)窗口成倍增加[5]。這種方式并沒有真正反映信道上的競(jìng)爭(zhēng)情況。尤其是節(jié)點(diǎn)個(gè)數(shù)較多網(wǎng)絡(luò)負(fù)載變嚴(yán)重時(shí)，成功發(fā)送完數(shù)據(jù)的節(jié)點(diǎn)把CW調(diào)為最小值，多個(gè)節(jié)點(diǎn)又有相同的CW值(CWmin)，會(huì)引起更多的碰撞。且碰撞和退避會(huì)浪費(fèi)時(shí)間，嚴(yán)重影響網(wǎng)絡(luò)的整體吞吐量。另外，數(shù)據(jù)發(fā)送成功的節(jié)點(diǎn)立刻將CW值置為最小，而數(shù)據(jù)發(fā)送失敗的節(jié)點(diǎn)的CW值成倍增加。之后的一段時(shí)間內(nèi)，CW值小的節(jié)點(diǎn)再次成功接入信道的概率增加，而CW值大的節(jié)點(diǎn)CW值會(huì)繼續(xù)增加，若CW值小的節(jié)點(diǎn)連續(xù)發(fā)送數(shù)據(jù)的話，就會(huì)一直占用信道，而其他節(jié)點(diǎn)的數(shù)據(jù)就無法發(fā)送出去，最終造成嚴(yán)重的信道接入不公平現(xiàn)象。除了接入信道不公平的問題，在時(shí)延方面也存在一定的缺陷。IEEE802.11p在MAC層中規(guī)定，初始競(jìng)爭(zhēng)窗口值為15(aCWmin)[6]。但是，數(shù)據(jù)流量負(fù)載過高(網(wǎng)絡(luò)密度較高)時(shí)，成功發(fā)送數(shù)據(jù)幀后恢復(fù)為初始競(jìng)爭(zhēng)窗口會(huì)使碰撞率增加，若節(jié)點(diǎn)在預(yù)定義時(shí)間段內(nèi)無法成功發(fā)送數(shù)據(jù)幀對(duì)應(yīng)的ACK消息，發(fā)送節(jié)點(diǎn)就會(huì)增加競(jìng)爭(zhēng)窗口，重傳數(shù)據(jù)幀，這樣會(huì)使時(shí)延增加。即使在初次嘗試發(fā)送數(shù)據(jù)時(shí)設(shè)定最佳的競(jìng)爭(zhēng)窗口可避免增加時(shí)延，但節(jié)點(diǎn)成功發(fā)送數(shù)據(jù)后，競(jìng)爭(zhēng)窗口又恢復(fù)為15，尤其是在網(wǎng)絡(luò)負(fù)載過高時(shí)，極其不宜采用這種方法。

2 基于Q學(xué)習(xí)的CW動(dòng)態(tài)調(diào)整算法

針對(duì)上述問題，文中在傳統(tǒng)信道接入機(jī)制的基礎(chǔ)上，引入強(qiáng)化學(xué)習(xí)，基于強(qiáng)化學(xué)習(xí)中的Q-Learning算法提出了新的信道接入方法-QL-CWmin方法。

2.1Q學(xué)習(xí)的基本原理

強(qiáng)化學(xué)習(xí)是機(jī)器學(xué)習(xí)中尤為重要的一種，它是智能系統(tǒng)從環(huán)境狀態(tài)到行為映射的學(xué)習(xí)過程，是解決智能系統(tǒng)尋優(yōu)問題的有效工具。能夠感知環(huán)境的Agent不斷在環(huán)境中學(xué)習(xí)，根據(jù)環(huán)境給予的反饋信號(hào)，總選擇執(zhí)行能達(dá)到目標(biāo)的最優(yōu)動(dòng)作。在強(qiáng)化學(xué)習(xí)中，Agent在環(huán)境中的學(xué)習(xí)過程是一種試探評(píng)價(jià)過程，它的基本原理是[7]：Agent在環(huán)境中學(xué)習(xí)時(shí)，選擇一個(gè)動(dòng)作作用于環(huán)境，環(huán)境狀態(tài)受該動(dòng)作影響而發(fā)生變化，同時(shí)會(huì)產(chǎn)生一個(gè)強(qiáng)化信號(hào)(獎(jiǎng)或懲)，并將此信號(hào)反饋給Agent，Agent會(huì)根據(jù)強(qiáng)化信號(hào)和環(huán)境的當(dāng)前狀態(tài)再選擇執(zhí)行下一個(gè)動(dòng)作，如果Agent的某一動(dòng)作策略會(huì)使Agent從環(huán)境中獲得正的獎(jiǎng)賞(強(qiáng)化信號(hào))，那么Agent此后選擇執(zhí)行這個(gè)動(dòng)作策略的趨勢(shì)就會(huì)加強(qiáng)，它的最終目的是Agent總選擇執(zhí)行能從環(huán)境中得到最大累積獎(jiǎng)賞值的動(dòng)作。

Q-Learning算法是強(qiáng)化學(xué)習(xí)算法中最典型的一種，也是目前應(yīng)用最為廣泛的一種。Q-Learning算法在環(huán)境條件未知的情況下最為有效，對(duì)環(huán)境的先驗(yàn)知識(shí)要求不高，它使Agent在馬爾可夫決策過程中具備利用經(jīng)歷過的動(dòng)作序列總選擇最優(yōu)動(dòng)作的能力。它不需要環(huán)境模型，Agent在動(dòng)態(tài)環(huán)境中通過交互試錯(cuò)不斷調(diào)整行為。Agent不斷探索環(huán)境，在每一環(huán)境狀態(tài)和可能的動(dòng)作之間建立一個(gè)Q值列表(Q表)，它學(xué)習(xí)的是每個(gè)狀態(tài)-動(dòng)作對(duì)的評(píng)價(jià)值-Q值(Q(st,at))，Q(st,at)是Agent在狀態(tài)st下根據(jù)策略選擇執(zhí)行動(dòng)作at,并循環(huán)執(zhí)行所得到的累積獎(jiǎng)賞值。Q-Learning算法的最優(yōu)策略是使Q(st,at)的累積獎(jiǎng)賞值最大化，所以Q學(xué)習(xí)的最優(yōu)策略表達(dá)式為[8]：

(1)

即Agent只需考慮當(dāng)前狀態(tài)和當(dāng)前可選的動(dòng)作，按照策略選擇執(zhí)行使Q(st,at)最大化的動(dòng)作。

文中所提出的信道接入方法-QL-CWmin，通過動(dòng)態(tài)調(diào)整競(jìng)爭(zhēng)窗口來解決碰撞率和時(shí)延的問題，利用Q-Learning算法學(xué)習(xí)最佳的競(jìng)爭(zhēng)窗口。由于鄰近節(jié)點(diǎn)之間互換信標(biāo)消息可獲得鄰居節(jié)點(diǎn)的位置信息，所以假設(shè)每個(gè)節(jié)點(diǎn)已知其一跳鄰居節(jié)點(diǎn)的位置信息，在節(jié)點(diǎn)成功發(fā)送數(shù)據(jù)幀后，環(huán)境給予節(jié)點(diǎn)一個(gè)正的獎(jiǎng)賞，若發(fā)送失敗，則給予負(fù)的獎(jiǎng)賞。在網(wǎng)絡(luò)負(fù)載較低時(shí)，使節(jié)點(diǎn)利用學(xué)習(xí)所得的最佳CW選擇以較小的CW接入信道避免增加時(shí)延；網(wǎng)絡(luò)負(fù)載較高時(shí)，則利用較大的CW接入信道防止碰撞。QL-CWmin算法可動(dòng)態(tài)地調(diào)整競(jìng)爭(zhēng)窗口，能以較低的時(shí)延發(fā)送數(shù)據(jù)，提高了數(shù)據(jù)包接收率和競(jìng)爭(zhēng)效率，減少了信道接入時(shí)延。

2.2 QL-CWmin算法的狀態(tài)-動(dòng)作對(duì)映射

整個(gè)車載自組織網(wǎng)絡(luò)即Agent學(xué)習(xí)的環(huán)境，網(wǎng)絡(luò)中的每個(gè)車輛節(jié)點(diǎn)即Agent，車輛節(jié)點(diǎn)在網(wǎng)絡(luò)中接入信道時(shí)所采用的競(jìng)爭(zhēng)窗口即Agent學(xué)習(xí)環(huán)境的環(huán)境狀態(tài)，由此車輛節(jié)點(diǎn)可能采用的所有競(jìng)爭(zhēng)窗口集即Agent學(xué)習(xí)環(huán)境的狀態(tài)空間。由于節(jié)點(diǎn)在網(wǎng)絡(luò)中接入信道的競(jìng)爭(zhēng)窗口通常為2的指數(shù)冪減1，因此競(jìng)爭(zhēng)窗口集為{15,31,63,127,255,511,1 023}，競(jìng)爭(zhēng)窗口初始值CWmin為15，最大值CWmax為1 023[9]。每一Agent可執(zhí)行的動(dòng)作有：增加(I)、保持(K)、減少(R)?！霸黾印奔丛龃蟾?jìng)爭(zhēng)窗口，“保持”和“減少”則分別是保持競(jìng)爭(zhēng)窗口大小不變和減小競(jìng)爭(zhēng)窗口。節(jié)點(diǎn)每執(zhí)行一個(gè)動(dòng)作后，環(huán)境狀態(tài)就發(fā)生狀態(tài)轉(zhuǎn)移。在網(wǎng)絡(luò)環(huán)境中不斷探索學(xué)習(xí)的過程中，每一節(jié)點(diǎn)在狀態(tài)-動(dòng)作對(duì)之間都維護(hù)一個(gè)Q表，Q表中包含Q值Q(st,at)，Q值的變化范圍為-1到1。其中，st為當(dāng)前競(jìng)爭(zhēng)窗口的大小，at為節(jié)點(diǎn)可能執(zhí)行的動(dòng)作。每發(fā)送完一個(gè)MAC幀后，節(jié)點(diǎn)根據(jù)發(fā)送狀態(tài)從網(wǎng)絡(luò)環(huán)境中獲得一個(gè)獎(jiǎng)賞值。若發(fā)送成功，節(jié)點(diǎn)得到一個(gè)正的獎(jiǎng)賞，若發(fā)送失敗(本協(xié)議中定義MAC層重傳次數(shù)不超過4，即數(shù)據(jù)重傳4次后，發(fā)送節(jié)點(diǎn)還是接收不到數(shù)據(jù)幀對(duì)應(yīng)的ACK消息，則定義此次發(fā)送失敗)，節(jié)點(diǎn)則得到一個(gè)負(fù)的獎(jiǎng)賞。丟包主要是由于其他數(shù)據(jù)包發(fā)生碰撞造成的，通過對(duì)獎(jiǎng)賞值進(jìn)行評(píng)估，節(jié)點(diǎn)自適應(yīng)地調(diào)整其競(jìng)爭(zhēng)窗口大小，總選擇執(zhí)行能使累積獎(jiǎng)賞值Q值最大化的最優(yōu)動(dòng)作。

2.3 QL-CWmin算法Q值函數(shù)更新

在Agent與環(huán)境不斷交互學(xué)習(xí)的過程中，節(jié)點(diǎn)接入信道可能執(zhí)行的動(dòng)作有：增加(I)、保持(K)、減少(R)。狀態(tài)空間為{15,31,63,127,255,511,1 023}。當(dāng)競(jìng)爭(zhēng)窗口為最小值時(shí)，競(jìng)爭(zhēng)窗口無法繼續(xù)減少；同樣地，當(dāng)競(jìng)爭(zhēng)窗口為最大值時(shí)，競(jìng)爭(zhēng)窗口無法繼續(xù)增加[10]。圖1為節(jié)點(diǎn)在網(wǎng)絡(luò)環(huán)境中學(xué)習(xí)的狀態(tài)轉(zhuǎn)移圖。

VANETs中，節(jié)點(diǎn)采用QL-CWmin算法發(fā)送MAC數(shù)據(jù)幀的過程中，利用狀態(tài)-動(dòng)作對(duì)的值函數(shù)Q(st,at)進(jìn)行迭代，并利用獎(jiǎng)賞作為估計(jì)函數(shù)來選擇下一動(dòng)作，對(duì)Q函數(shù)進(jìn)行優(yōu)化，通過多步迭代學(xué)習(xí)逼近最優(yōu)值函數(shù)。節(jié)點(diǎn)每發(fā)送一次數(shù)據(jù)幀，就更新一次Q表，更新Q值的表達(dá)式即Q學(xué)習(xí)的迭代公式為：

圖1 狀態(tài)轉(zhuǎn)移圖

α)×Q(st,at)

(2)

其中，α為學(xué)習(xí)率，是Agent在環(huán)境中的學(xué)習(xí)步長(zhǎng)，用于控制學(xué)習(xí)速度。α值越大，Q值收斂越快。由于MAC數(shù)據(jù)幀發(fā)送較為頻繁，0.6足以反映網(wǎng)絡(luò)拓?fù)涞淖兓潭?，所以文中取α?.6。γ為折扣因子，γ∈[0,1]，體現(xiàn)了Agent對(duì)以后環(huán)境所給予獎(jiǎng)勵(lì)的重視程度，取值越大表示越重視以后的獎(jiǎng)勵(lì)，反之，則只在乎眼前的獎(jiǎng)勵(lì)。文中取γ為0.9。

車輛節(jié)點(diǎn)在VANETs中初次接入信道發(fā)送數(shù)據(jù)時(shí)，會(huì)首先初始化Q(st,at)的值，然后根據(jù)探索策略在狀態(tài)st時(shí)選擇執(zhí)行動(dòng)作at，得到下一狀態(tài)st+1及其獎(jiǎng)賞值R，之后根據(jù)獎(jiǎng)賞值通過式(2)更新Q值，一直循環(huán)執(zhí)行直到實(shí)現(xiàn)目標(biāo)狀態(tài)或達(dá)到限制的迭代次數(shù)。其中獎(jiǎng)賞值R計(jì)算如下：

(3)

其中，RCW表示選擇當(dāng)前的CW值接入信道成功發(fā)送數(shù)據(jù)所獲得的正獎(jiǎng)賞。發(fā)送失敗，獎(jiǎng)賞值為-1，若當(dāng)前狀態(tài)正在發(fā)送數(shù)據(jù)，獎(jiǎng)賞值為0。

表1中定義了選擇各不同大小的CW值成功發(fā)送數(shù)據(jù)所獲得的不同獎(jiǎng)賞值。成功發(fā)送數(shù)據(jù)所選的CW值越小，得到的獎(jiǎng)賞值就越大，而網(wǎng)絡(luò)負(fù)載過高時(shí)，節(jié)點(diǎn)從環(huán)境中獲得負(fù)的獎(jiǎng)賞從而增加競(jìng)爭(zhēng)窗口，這樣能使節(jié)點(diǎn)充分利用信道資源。

表1 不同CW對(duì)應(yīng)的獎(jiǎng)賞值

圖2 基本流程圖

2.4 QL-CWmin算法的收斂性

強(qiáng)化學(xué)習(xí)中，“探索”是指Agent要盡可能地經(jīng)歷所有的狀態(tài)-動(dòng)作對(duì)，從而獲得全面充分的經(jīng)驗(yàn)知識(shí)，保證學(xué)習(xí)過程能收斂到最優(yōu)的Q值函數(shù)，但是過度“探索”會(huì)引入冗余信息，浪費(fèi)存儲(chǔ)資源和計(jì)算資源，最終影響學(xué)習(xí)速度。“利用”則是Agent為了從環(huán)境中獲得較高的獎(jiǎng)賞值，總是根據(jù)當(dāng)前的Q表選擇執(zhí)行可以獲得高獎(jiǎng)賞值的動(dòng)作，而不愿冒險(xiǎn)去嘗試可能會(huì)產(chǎn)生更高獎(jiǎng)賞值但也可能產(chǎn)生低獎(jiǎng)賞值的動(dòng)作[12]。所以尋求“探索”和“利用”間的平衡對(duì)保證學(xué)習(xí)過程能快速收斂到最優(yōu)Q值函數(shù)非常重要，Agent需要不斷“探索”次優(yōu)動(dòng)作從而使“利用”趨向全局最優(yōu)。

QL-CWmin算法中，節(jié)點(diǎn)在網(wǎng)絡(luò)環(huán)境中學(xué)習(xí)所用的探索策略為強(qiáng)化學(xué)習(xí)算法中應(yīng)用較為廣泛ε-greedy動(dòng)作選取機(jī)制，每個(gè)Agent節(jié)點(diǎn)要執(zhí)行的第一個(gè)動(dòng)作是將其CW值初始化為15，當(dāng)Agent對(duì)自己所處的網(wǎng)絡(luò)環(huán)境一無所知時(shí)，采用最小的CW值是最佳選擇。此后節(jié)點(diǎn)以概率ε進(jìn)行探索，尋求新的可能會(huì)產(chǎn)生更高獎(jiǎng)賞值但也可能產(chǎn)生低獎(jiǎng)賞值的動(dòng)作，以概率1-ε選擇當(dāng)前Q值最高的動(dòng)作(利用)。由于節(jié)點(diǎn)接入信道并成功發(fā)送數(shù)據(jù)所選用的CW越小，Agent得到的獎(jiǎng)賞就越多，只要當(dāng)前所選的CW能成功發(fā)送數(shù)據(jù)，節(jié)點(diǎn)就絕不會(huì)再增加CW。當(dāng)CW大于15，而網(wǎng)絡(luò)負(fù)載降低時(shí)，QL-CWmin算法也會(huì)通過探索將CW重設(shè)為15，即QL-CWmin算法總能使節(jié)點(diǎn)在網(wǎng)絡(luò)環(huán)境中通過“探索”和“利用”將CW調(diào)整為最佳值。

收斂問題也是強(qiáng)化學(xué)習(xí)算法所研究的一個(gè)重要問題[13]，Watkins與Dayan利用隨機(jī)過程和不動(dòng)點(diǎn)理論給出：

(1)學(xué)習(xí)過程具有Markov性；

(2)所有的狀態(tài)-動(dòng)作對(duì)能被無限次訪問；

(3)Q表中能存儲(chǔ)所有狀態(tài)-動(dòng)作對(duì)的Q值函數(shù)，每個(gè)元素分別對(duì)應(yīng)于一個(gè)狀態(tài)-動(dòng)作對(duì)；

以上四個(gè)條件都滿足時(shí)，Q學(xué)習(xí)過程可收斂到最優(yōu)狀態(tài)-動(dòng)作對(duì)值函數(shù)Q*。由此可見，QL-CWmin滿足收斂的所有條件。

3 仿真結(jié)果

文中對(duì)高速公路場(chǎng)景進(jìn)行仿真，仿真環(huán)境如表2所示。

表2 仿真參數(shù)

文中通過仿真從VANET的廣播幀接收率、端到端傳輸時(shí)延和數(shù)據(jù)幀碰撞率等方面對(duì)CWmin-15算法、CWmin-31算法、AdaptiveCWmin算法和提出的QL-CWmin算法進(jìn)行了對(duì)比分析。

圖3分別為VANET中采用四種退避算法的廣播幀接收率隨車輛密度的變化趨勢(shì)。

從圖中可以看出，車輛密度較小時(shí)，由于車輛節(jié)點(diǎn)總會(huì)以最小的競(jìng)爭(zhēng)窗口接入信道，且數(shù)據(jù)幀發(fā)生碰撞的概率很小，所以廣播幀接收率都較接近1。但隨著車輛密度的增加，廣播幀接收率都呈下降趨勢(shì)，而采用文中所提出的QL-CWmin算法的廣播幀接收率不僅優(yōu)于其他算法，且下降趨勢(shì)較為平穩(wěn)。因?yàn)檐囕v節(jié)點(diǎn)在VANET環(huán)境中不斷交互試錯(cuò)，總選擇Q值最高的競(jìng)爭(zhēng)窗口即最佳窗口接入信道，所以其廣播幀接收率不會(huì)隨著車輛密度的增加而呈急劇下降的趨勢(shì)。

圖3 廣播幀接收率與車輛密度的關(guān)系曲線

圖4和圖5分別是采用四種退避算法后VANET中的端到端傳輸時(shí)延和數(shù)據(jù)幀碰撞率隨車輛密度的變化趨勢(shì)。

圖4 端到端時(shí)延與車輛密度的關(guān)系曲線

圖5 數(shù)據(jù)幀碰撞率與車輛密度的關(guān)系曲線

從圖中可見，文中提出的QL-CWmin算法與其他三種退避算法相比，端到端傳輸時(shí)延和數(shù)據(jù)幀碰撞率都較小，因此采用QL-CWmin算法能為節(jié)點(diǎn)接入信道提供更高的公平性，從而能適用于各種不同負(fù)載程度的車載網(wǎng)絡(luò)。

總的來說，在節(jié)點(diǎn)接入信道發(fā)送數(shù)據(jù)發(fā)生碰撞需要進(jìn)行退避的過程中，車輛節(jié)點(diǎn)利用Q學(xué)習(xí)算法與周圍環(huán)境不斷交互，根據(jù)網(wǎng)絡(luò)環(huán)境反饋的獎(jiǎng)賞信號(hào)，動(dòng)態(tài)地調(diào)整競(jìng)爭(zhēng)窗口，使節(jié)點(diǎn)下次發(fā)送數(shù)據(jù)時(shí)總能以最佳的CW值接入信道，提高了數(shù)據(jù)成功發(fā)送的概率，減少了退避次數(shù)。就數(shù)據(jù)包接收率及端到端傳輸時(shí)延，QL-CWmin算法性能與其他傳統(tǒng)的退避算法相比都得到有效改善，尤其是QL-CWmin算法完全不同于以往傳統(tǒng)的退避算法[14]在節(jié)點(diǎn)成功發(fā)送完數(shù)據(jù)后就將CW值恢復(fù)為15，從不考慮網(wǎng)絡(luò)負(fù)載情況，而是使節(jié)點(diǎn)能經(jīng)歷所有的狀態(tài)-動(dòng)作對(duì)，根據(jù)獎(jiǎng)賞值總以較大的概率選擇能成功發(fā)送數(shù)據(jù)且能獲得較高獎(jiǎng)賞值的CW。因此，QL-CWmin算法顯著提高了節(jié)點(diǎn)接入信道的公平性，且還能適用于不同負(fù)載程度的網(wǎng)絡(luò)環(huán)境。

4 結(jié)束語(yǔ)

文中將強(qiáng)化學(xué)習(xí)中的Q學(xué)習(xí)算法引入到VANETsMAC層中，詳細(xì)設(shè)計(jì)了車輛節(jié)點(diǎn)與車載網(wǎng)絡(luò)環(huán)境交互學(xué)習(xí)時(shí)所處的狀態(tài)和可執(zhí)行的動(dòng)作，以及狀態(tài)-動(dòng)作對(duì)的映射關(guān)系和動(dòng)作策略，提出了QL-CWmin退避算法，并通過仿真對(duì)該算法和現(xiàn)有的其他退避算法進(jìn)行了對(duì)比分析。QL-CWmin算法就廣播幀接收率、端到端時(shí)延、數(shù)據(jù)幀碰撞率、節(jié)點(diǎn)公平性及可擴(kuò)展性而言，性能得到顯著改善。在ε-greedy動(dòng)作選取機(jī)制中ε值固定的情況下，節(jié)點(diǎn)在環(huán)境中探索新動(dòng)作時(shí)，選擇執(zhí)行各個(gè)動(dòng)作的概率一樣，這樣選擇最壞動(dòng)作的概率也很大。后續(xù)研究中，為了有效地平衡“探索”和“利用”，將會(huì)嘗試動(dòng)態(tài)調(diào)整ε值，當(dāng)前Q值最高的動(dòng)作賦予最高的概率，而探索的新動(dòng)作要根據(jù)其獎(jiǎng)賞值大小賦予不同的概率，從而使研究結(jié)果更精確，考慮因素更全面。另外，已提出的基于Q學(xué)習(xí)的信道接入退避方法是針對(duì)單智能體的學(xué)習(xí)過程的，單智能體的學(xué)習(xí)方法存在一些問題。例如，智能體對(duì)環(huán)境僅部分感知、學(xué)習(xí)搜索空間太大、學(xué)習(xí)效率低等。因此，針對(duì)這些問題，將進(jìn)一步研究基于多智能體Q學(xué)習(xí)的接入信道退避方法，有效改善節(jié)點(diǎn)接入信道的各方面性能。

[1]ReindersR,EenennaamM,KaragiannisG,etal.ContentionwindowanalysisforbeaconinginVANETs[C]//2011 7thinternationalwirelesscommunicationsandmobilecomputingconference.[s.l.]:[s.n.],2011:1481-1487.

[2]AlasmaryW,ZhuangW.MobilityimpactinIEEE802.11pinfrastructurelessvehicularnetworks[J].AdHocNetworks,2012,10(2):222-230.

[3]BaladorA,CalafateCT,CanoJC,etal.Reducingchannelcontentioninvehicularenvironmentsthroughanadaptivecontentionwindowsolution[J].WirelessDays,2013,30(12):1-4.

[4]LeeGil-Won,AhnSeung-Pyo,KimDong-Seong.ContentionwindowallocationschemeforV2V[C]//2013internationalconferenceonadvancedtechnologiesforcommunications.[s.l.]:[s.n.],2013:501-505.

[5]BooysenMJ,ZeadallyS,vanRooyenGJ.Surveyofmediaaccesscontrolprotocolsforvehicularadhocnetworks[J].IETCommunications,2011,5(11):1619-1631.

[6]ShiC,DaiX,LiangP,etal.Adaptiveaccessmechanismwithoptimalcontentionwindowbasedonnodenumberestimationusingmultiplethresholds[J].IEEETransactionsonWirelessCommunications,2012,11(11):2046-2055.

[7]LamptonA,ValasekJ.Multiresolutionstate-spacediscretizationmethodforQ-Learning[C]//Americancontrolconference.[s.l.]:[s.n.],2009:10-12.

[8] 趙 昀,陳慶偉,胡維禮.一種基于信息熵的強(qiáng)化學(xué)習(xí)算法[J].系統(tǒng)工程與電子技術(shù),2010,32(5):1043-1046.

[9]WangQ,LengS,FuH,etal.AnIEEE802.11p-basedmultichannelMACschemewithchannelcoordinationforvehicularadhocnetworks[J].IEEETransactionsonIntelligentTransportationSystem,2012,13(2):449-458.

[10] 魏李琦,肖曉強(qiáng),陳穎文,等.基于相對(duì)速度的802.11p車載網(wǎng)絡(luò)自適應(yīng)退避算法[J].計(jì)算機(jī)應(yīng)用研究,2011,28(10):3878-3880.

[11] 杜春俠,高 云,張 文.多智能體系統(tǒng)中具有先驗(yàn)知識(shí)的Q學(xué)習(xí)算法[J].清華大學(xué)學(xué)報(bào):自然科學(xué)版,2005,45(7):981-984.

[12] 陳學(xué)松,楊宜民.強(qiáng)化學(xué)習(xí)研究綜述[J].計(jì)算機(jī)應(yīng)用研究,2010,27(8):2834-2838.

[13] 黃玉清,王英倫.支持服務(wù)區(qū)分的多智能體Q學(xué)習(xí)MAC算法[J].計(jì)算機(jī)工程,2013,39(8):112-116.

[14]vanEenennaamM,RemkeA,HeijenkG.AnanalyticalmodelforbeaconinginVANETs[C]//Vehicularnetworkingconference.[s.l.]:IEEE,2012:9-16.

Research on Technology of Channel Access Based onQ-Learning Algorithm for Vehicular Communication

DU Ai-qian1,2,ZHAO Hai-tao1,2,LIU Nan-jie1,2

(1.College of Communication and Information Engineering,Nanjing University of Posts and Telecommunications,Nanjing 210003,China;2.Institute of Network DNA Engineering,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

AQ-Learningbasedback-offalgorithmisproposedbecausethetraditionalDCFapproachusedforIEEE802.11pMACprotocoltoaccessthechannelhassomeproblemsofthelowpacketdeliveryrate,highdelayandthepoorscalabilityinVANETs.Theproposedalgorithm,whichisquitedifferentfromthetraditionalBEBalgorithm,isadoptedbythenodes(Agents)tointeractwithsurroundingscontinuouslyandlearnfromeachother.ThevehiclenodesadjustthesizeofCW(ContentionWindow)dynamicallyaccordingtotheresultslearnedfromthesurroundingssothatthenodescanaccessthechannelwiththeoptimalCWeventuallyminimizingthepacketcollisionsandend-to-enddelay.Thesimulationresultsshowthatthecommunicationnodesusingtheproposedalgorithmcanadapttotheunknownvehicularenvironmentrapidly,andsimultaneouslythehighpacketdeliveryratio,lowend-to-enddelayandhighfairnesscanbeachievedforvehicularnetworkwithvariouslevelload.

vehicular network;BEB algorithm;contention window;Q-Learningalgorithm;DCF

2016-03-29

2016-08-02

時(shí)間：2017-01-10

國(guó)家“973”重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃項(xiàng)目(2013CB329005);國(guó)家自然科學(xué)基金資助項(xiàng)目(61302100,61101105,61201162)；江蘇省基礎(chǔ)研究計(jì)劃-重點(diǎn)研究專項(xiàng)基金(BK2011027,BK2012434)；江蘇省高校自然科學(xué)研究基金(12KJB510022,12KJB510020)

杜艾芊(1991-)，女，碩士研究生，研究方向?yàn)橐苿?dòng)通信與無線技術(shù)、車聯(lián)網(wǎng)車載通信;趙海濤，博士，副教授，研究方向?yàn)闊o線多媒體通信;劉南杰，博士，教授，研究方向?yàn)榉涸谕ㄐ?、車?lián)網(wǎng)、智能交通。

http://www.cnki.net/kcms/detail/61.1450.TP.20170110.1019.044.html

TP

A

1673-629X(2017)03-0085-06

10.3969/j.issn.1673-629X.2017.03.018