基于Q學(xué)習(xí)算法的Ad Hoc網(wǎng)絡(luò)自適應(yīng)DSR協(xié)議研究

遲 凱

（中國(guó)電子科技集團(tuán)公司第20研究所，西安 710068）

0 引 言

Ad Hoc網(wǎng)絡(luò)區(qū)別于傳統(tǒng)的有中心的網(wǎng)絡(luò)，采用臨時(shí)快速自組織建立網(wǎng)絡(luò)的形式。由于其去中心化、抗打擊，自愈性和魯棒性強(qiáng)，在軍事上得到了廣泛應(yīng)用。通過(guò)Ad Hoc網(wǎng)絡(luò)能夠把作戰(zhàn)節(jié)點(diǎn)（如指揮所、艦船、戰(zhàn)機(jī)等）有機(jī)地結(jié)合起來(lái)，協(xié)調(diào)指揮，形成統(tǒng)一的戰(zhàn)力；還能夠通過(guò)消息轉(zhuǎn)發(fā)，形成戰(zhàn)場(chǎng)共享信息態(tài)勢(shì)，有效避免了電子戰(zhàn)中單個(gè)節(jié)點(diǎn)受到針對(duì)性干擾喪失監(jiān)測(cè)能力的發(fā)生。由于網(wǎng)絡(luò)中的節(jié)點(diǎn)因?yàn)槟芰渴芟藁蛘吖β士刂频仍?，通信范圍一般受限，需要通過(guò)多跳路由的方式實(shí)現(xiàn)范圍外的通信，則Ad Hoc網(wǎng)絡(luò)路由協(xié)議對(duì)網(wǎng)絡(luò)質(zhì)量起到關(guān)鍵作用。Ad Hoc網(wǎng)絡(luò)中無(wú)線信道干擾、衰落、節(jié)點(diǎn)移動(dòng)等造成拓?fù)渥兓焖佟⒙酚少|(zhì)量不穩(wěn)定等多種問(wèn)題，對(duì)路由算法提出了很大挑戰(zhàn)。

路由算法可分為確定性路由算法和自適應(yīng)路由算法。確定性路由算法是源節(jié)點(diǎn)在發(fā)送分組之前，預(yù)先尋找或者維護(hù)一條確定的發(fā)送路徑，通過(guò)中繼節(jié)點(diǎn)逐次送達(dá)至目的節(jié)點(diǎn)。自適應(yīng)路由算法則在建立維護(hù)路由過(guò)程以及發(fā)送分組的過(guò)程中監(jiān)測(cè)網(wǎng)絡(luò)狀態(tài)，根據(jù)中繼節(jié)點(diǎn)或者鄰居節(jié)點(diǎn)反饋的信息改變路由選擇或者采用其他能夠提升分組送達(dá)率、降低擁塞的策略來(lái)提升服務(wù)質(zhì)量。確定性路由算法雖然簡(jiǎn)單、有效、容易實(shí)現(xiàn)，卻極易受到網(wǎng)絡(luò)擁塞節(jié)點(diǎn)或鏈路的影響，出現(xiàn)短板效應(yīng)。因?yàn)樽赃m應(yīng)路由能夠?qū)ν負(fù)渥兓杆?、鏈路狀態(tài)突變等情況及時(shí)作出反應(yīng)，調(diào)整本地節(jié)點(diǎn)業(yè)務(wù)發(fā)送，適應(yīng)網(wǎng)絡(luò)當(dāng)前變化，提高網(wǎng)絡(luò)性能，其在Ad Hoc網(wǎng)絡(luò)研究領(lǐng)域具有重要的價(jià)值。

傳統(tǒng)的Ad Hoc網(wǎng)絡(luò)路由協(xié)議可分為表驅(qū)動(dòng)（先應(yīng)式）路由協(xié)議、按需（反應(yīng)式）路由協(xié)議和混合路由協(xié)議。主要區(qū)別在于路由建立的方式不同。表驅(qū)動(dòng)協(xié)議通過(guò)定期交換路由信息分組，每個(gè)節(jié)點(diǎn)維護(hù)1張或者多張路由表，記錄到其他節(jié)點(diǎn)的路由信息。因此，采用表驅(qū)動(dòng)路由協(xié)議的節(jié)點(diǎn)在產(chǎn)生業(yè)務(wù)之前就預(yù)先準(zhǔn)備好了一條發(fā)送路徑，并定期進(jìn)行維護(hù)，及時(shí)對(duì)路由情況的變化進(jìn)行更新，雖然增加了額外的路由維護(hù)開銷，但業(yè)務(wù)類消息一旦到達(dá)可直接查詢路由表發(fā)送，時(shí)延較小。圖1為現(xiàn)有部分表驅(qū)動(dòng)協(xié)議［1］。

圖1 現(xiàn)有部分表驅(qū)動(dòng)路由協(xié)議

這些表驅(qū)動(dòng)協(xié)議的區(qū)別主要為每個(gè)節(jié)點(diǎn)維護(hù)路由表的大小和個(gè)數(shù)不同，并且維護(hù)路由表的過(guò)程中，更新信息在網(wǎng)絡(luò)中傳播的方式不同。

不同于表驅(qū)動(dòng)式協(xié)議，按需路由協(xié)議是根據(jù)發(fā)送數(shù)據(jù)分組的需要按需進(jìn)行路由發(fā)現(xiàn)的過(guò)程，即在有業(yè)務(wù)需要發(fā)送之前，并不維護(hù)路由，也沒(méi)有任何開銷。當(dāng)業(yè)務(wù)分組需要發(fā)送而節(jié)點(diǎn)沒(méi)有相應(yīng)路由信息時(shí)，節(jié)點(diǎn)發(fā)起1個(gè)路由發(fā)現(xiàn)過(guò)程，通過(guò)鄰居節(jié)點(diǎn)不斷中繼尋找到目的節(jié)點(diǎn)的可能路徑，建立路由后也只進(jìn)行簡(jiǎn)單的維護(hù)，并且到達(dá)一定生命期就刪除路由。按需協(xié)議開銷極小，只有在有業(yè)務(wù)需要發(fā)送時(shí)才帶來(lái)一定開銷，沒(méi)有產(chǎn)生業(yè)務(wù)的時(shí)間段基本處于靜默狀態(tài)，不容易被發(fā)現(xiàn)和定位，在戰(zhàn)場(chǎng)環(huán)境下有較高的隱蔽性。圖2是現(xiàn)有的部分按需路由協(xié)議［1］。

圖2 現(xiàn)有按需路由協(xié)議

按需路由協(xié)議之間的主要區(qū)別在于選路的標(biāo)準(zhǔn)不同，比如動(dòng)態(tài)源路由（DSR）協(xié)議，無(wú)線自組網(wǎng)按需距離矢量（AODV）協(xié)議以最短路徑為選擇路由的標(biāo)準(zhǔn)，基于穩(wěn)定性的路由（ABR）協(xié)議以有效時(shí)間為選擇標(biāo)準(zhǔn)。另外存儲(chǔ)路由信息的方式也有所不同，DSR協(xié)議完整記錄整條路徑信息，AODV則只記錄逐跳信息。

在Ad Hoc網(wǎng)絡(luò)中，表驅(qū)動(dòng)路由協(xié)議主要應(yīng)用于業(yè)務(wù)較均衡、拓?fù)渥兓^慢的網(wǎng)絡(luò)狀況下，而按需路由協(xié)議則適用于突發(fā)業(yè)務(wù)多、拓?fù)渥兓杆?、同時(shí)對(duì)功率控制、節(jié)點(diǎn)能量有特殊要求的網(wǎng)路狀況下。

1 DSR協(xié)議的研究

DSR協(xié)議是一種簡(jiǎn)單高效的適用于移動(dòng)Ad Hoc網(wǎng)絡(luò)（MANET）的按需路由協(xié)議，屬于卡耐基-梅隆大學(xué)Monarch項(xiàng)目的一部分［2］，經(jīng)過(guò)多次修訂和訂正，已日趨完善。其主要特點(diǎn)是使用源路由機(jī)制進(jìn)行分組轉(zhuǎn)發(fā)，即在有業(yè)務(wù)分組需要發(fā)送的時(shí)候，源節(jié)點(diǎn)發(fā)起路由發(fā)現(xiàn)過(guò)程，建立路由之后在每個(gè)數(shù)據(jù)分組的包頭中都包含了這一分組將要通過(guò)的完整的路由節(jié)點(diǎn)地址列表。轉(zhuǎn)發(fā)分組的中繼節(jié)點(diǎn)也能夠完整地獲知該分組所經(jīng)路徑的完整信息，從而能夠消除路由環(huán)路，并且支持單向和非對(duì)稱路由，源節(jié)點(diǎn)還可以根據(jù)路由發(fā)現(xiàn)階段形成的完整路徑信息以某種策略選擇和控制當(dāng)前數(shù)據(jù)分組所需路由，有相當(dāng)?shù)撵`活性。然而DSR協(xié)議的缺點(diǎn)也很明顯，因?yàn)閿?shù)據(jù)分組攜帶了所經(jīng)過(guò)的完整的路由信息，增加了額外的開銷，相對(duì)于其他按需路由協(xié)議開銷過(guò)大，降低了帶寬利用率，擴(kuò)展性差。IETF MANET工作組建議該協(xié)議使用于不大于200個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)。

正因?yàn)镈SR采用基于源路由的實(shí)現(xiàn)方式，源節(jié)點(diǎn)在路由建立階段通過(guò)目的節(jié)點(diǎn)回溯的路由應(yīng)答消息獲知了整條路徑上的節(jié)點(diǎn)列表，從而有依據(jù)該列表信息采取進(jìn)一步策略的可能。目前DSR協(xié)議的改進(jìn)算法主要有：基于DSR的分層路由協(xié)議，如DOA（DSR over AODV）是一種結(jié) 合 DSR 和AODV特點(diǎn)實(shí)現(xiàn)的分層路由協(xié)議，在層次內(nèi)使用AODV協(xié)議，在各層次間使用DSR 協(xié)議［3］；基于DSR的服務(wù)質(zhì)量（Qos）路由協(xié)議［4］，在路由發(fā)現(xiàn)階段收集Qos參量用于選擇一系列不相重疊的路由，根據(jù)不同的Qos要求提供節(jié)點(diǎn)使用，并達(dá)到減小網(wǎng)絡(luò)擁塞、平衡負(fù)載的目的；基于鏈路穩(wěn)定性算法的DSR協(xié)議［5］，通過(guò)鏈路穩(wěn)定性算法選擇穩(wěn)定性高的路由，降低了路由斷開次數(shù)和丟包率，并且不需要增加額外的節(jié)點(diǎn)信息交換報(bào)文。

2 自適應(yīng)DSR協(xié)議

2.1 Q學(xué)習(xí)算法

2.1.1 Q學(xué)習(xí)算法概述

強(qiáng)化學(xué)習(xí)，又稱增強(qiáng)學(xué)習(xí)或再勵(lì)學(xué)習(xí)，是求解序貫優(yōu)化決策問(wèn)題的一種機(jī)器學(xué)習(xí)方法。在強(qiáng)化學(xué)習(xí)理論和算法研究中，通常將序貫優(yōu)化決策問(wèn)題建模為馬爾科夫決策過(guò)程［6］。強(qiáng)化學(xué)習(xí)算法并不要求已知馬爾科夫決策過(guò)程的狀態(tài)轉(zhuǎn)移模型，因此在不確定的優(yōu)化決策問(wèn)題中具有更廣泛的應(yīng)用前景。

強(qiáng)化學(xué)習(xí)是智能系統(tǒng)從環(huán)境到行為映射的學(xué)習(xí)，以使獎(jiǎng)勵(lì)信號(hào)函數(shù)值最大化。強(qiáng)化學(xué)習(xí)中由環(huán)境提供的強(qiáng)化信號(hào)是對(duì)產(chǎn)生動(dòng)作的好壞作一種評(píng)價(jià)，智能系統(tǒng)通過(guò)評(píng)價(jià)對(duì)行為的反饋進(jìn)行學(xué)習(xí)，不斷改進(jìn)行動(dòng)方案以適應(yīng)環(huán)境。強(qiáng)化學(xué)習(xí)算法能夠在無(wú)法獲得完整環(huán)境信息的情況下根據(jù)感知到的狀態(tài)對(duì)網(wǎng)絡(luò)的各參數(shù)進(jìn)行重配置，進(jìn)而適應(yīng)不斷變化的網(wǎng)絡(luò)環(huán)境，提高網(wǎng)絡(luò)的性能。增強(qiáng)學(xué)習(xí)在與環(huán)境相互作用的過(guò)程中，通過(guò)極大化或極小化累積回報(bào)來(lái)選擇策略，即學(xué)習(xí)的目標(biāo)函數(shù)是學(xué)習(xí)一個(gè)控制策略，以此建立從狀態(tài)s到動(dòng)作a的映射，如圖3所示。

圖3 Agent與環(huán)境交互

Q學(xué)習(xí)算法是由Watkins提出的一種無(wú)模型強(qiáng)化學(xué)習(xí)算法［7］，被認(rèn)為是強(qiáng)化學(xué)習(xí)領(lǐng)域的重要突破。Q-learning選擇的策略是選取當(dāng)前狀態(tài)s下具有最佳Q值的動(dòng)作，即選取具有最大反饋獎(jiǎng)賞的動(dòng)作來(lái)觸發(fā)下一次環(huán)境反饋。通過(guò)直接優(yōu)化1個(gè)可迭代計(jì)算的動(dòng)作值函數(shù)Q（s，a）找到一個(gè)策略使得期望獎(jiǎng)賞總和最大。每次的迭代中都需要考察行為帶來(lái)的影響，確保學(xué)習(xí)過(guò)程收斂。

Q-learning作為一種強(qiáng)化學(xué)習(xí)算法，同樣通過(guò)馬爾科夫決策過(guò)程來(lái)建模，由于轉(zhuǎn)移概率和所獲得的環(huán)境獎(jiǎng)賞未知，其采用迭代的方法，以環(huán)境-動(dòng)作獎(jiǎng)賞值Q＊（s，a） 作為動(dòng)作執(zhí)行效果的衡量標(biāo)準(zhǔn)。Q＊（s，a） 表示Agent在狀態(tài)s下采用的策略使得所獲得的累積獎(jiǎng)賞值最大。最優(yōu)的策略即在對(duì)應(yīng)給定的狀態(tài)，選擇某個(gè)行為使得累計(jì)的獎(jiǎng)賞值最大。Q值是指在環(huán)境狀態(tài)為x時(shí)選擇策略π并執(zhí)行動(dòng)作a所獲得的累計(jì)獎(jiǎng)賞值。

2.1.2 Q學(xué)習(xí)算法在路由協(xié)議中的應(yīng)用

目前，Q-learning在復(fù)雜的優(yōu)化控制問(wèn)題中有了成功的應(yīng)用，其通過(guò)環(huán)境反饋來(lái)積累策略選擇的思想也被一些研究人員應(yīng)用于網(wǎng)絡(luò)路由算法設(shè)計(jì)中。Minsoo Lee等人［8］提出了一種將 Q-learning運(yùn)用于減小無(wú)線網(wǎng)絡(luò)路由控制開銷的方法，如圖4所示。

該算法根據(jù)源節(jié)點(diǎn)在每次路由建立過(guò)程中的路由發(fā)現(xiàn)時(shí)延更新表征網(wǎng)絡(luò)狀況的Q值，根據(jù)Q值的變化情況判斷網(wǎng)絡(luò)發(fā)展趨勢(shì)，從而增加或減小路由生存期和hello周期。

圖4 Q-learning減小控制開銷算法思想

Boyan等人［9］提出了一種將Q-learning運(yùn)用于路徑選擇的路由方法，如圖5所示。該方法能夠根據(jù)周圍鄰居節(jié)點(diǎn)的負(fù)載情況來(lái)選擇路徑，在網(wǎng)絡(luò)高負(fù)載的情況下能夠獲得相對(duì)較小的時(shí)延。

圖5 Q-learning路徑選擇算法思想

Q-learning用于路徑選擇的算法能夠在預(yù)先不知道網(wǎng)絡(luò)的拓?fù)湫畔⒑蜆I(yè)務(wù)類型的情況下，在動(dòng)態(tài)變化的網(wǎng)絡(luò)中發(fā)現(xiàn)有效的分組傳輸策略。每個(gè)節(jié)點(diǎn)保存一個(gè)Q值表用于記錄通過(guò)它的鄰居節(jié)點(diǎn)到達(dá)其所有的目的節(jié)點(diǎn)的分組傳輸時(shí)延估計(jì)。Qx（d，y）表示分組P經(jīng)過(guò)節(jié)點(diǎn)x的鄰節(jié)點(diǎn)y到達(dá)目的節(jié)點(diǎn)d所需時(shí)間的估計(jì)，這包括了分組P在節(jié)點(diǎn)x的排隊(duì)時(shí)延。節(jié)點(diǎn)首先選擇Q值最小的鄰居節(jié)點(diǎn)作為下一跳節(jié)點(diǎn)發(fā)送業(yè)務(wù)分組，之后得到下一跳節(jié)點(diǎn)對(duì)路徑上剩余時(shí)間的估計(jì)，對(duì)Q值進(jìn)行修正，直到Q值不再變化，則找到最佳路由。

2.2 Q＿DSR協(xié)議

DSR協(xié)議采用源路由的實(shí)現(xiàn)方式，源節(jié)點(diǎn)可以獲得整條路徑的節(jié)點(diǎn)信息，當(dāng)有多條路徑同時(shí)存在時(shí)有較高的自主權(quán)，不依賴于中繼節(jié)點(diǎn)對(duì)路徑信息的獲知和存儲(chǔ)。然而開銷過(guò)大是DSR協(xié)議最主要的缺點(diǎn)，為了保證整條路徑信息的傳遞，DSR協(xié)議的路由請(qǐng)求和路由應(yīng)答分組開銷較大，在網(wǎng)絡(luò)拓?fù)渥兓杆?、路由信息失效率高、需要不斷地發(fā)起路由請(qǐng)求的情況下尤為嚴(yán)重。在DSR路由協(xié)議中引入Q學(xué)習(xí)算法，可以較為有效地降低開銷，從而提高網(wǎng)絡(luò)的吞吐量。

2.2.1 路由建立階段

DSR協(xié)議是基于按需驅(qū)動(dòng)的，即每當(dāng)有業(yè)務(wù)消息需要發(fā)送時(shí)查詢是否存在到達(dá)目的節(jié)點(diǎn)的路由信息，如果沒(méi)有則發(fā)起路由請(qǐng)求消息，路由請(qǐng)求消息通過(guò)中繼節(jié)點(diǎn)廣播方式擴(kuò)散到網(wǎng)絡(luò)中，目的節(jié)點(diǎn)收到后則回復(fù)路由應(yīng)答消息逐條回溯到源節(jié)點(diǎn)。如果建立的路徑不穩(wěn)定，路由很快失效，則源節(jié)點(diǎn)發(fā)現(xiàn)路由失效后就需要重新發(fā)起路由請(qǐng)求消息重新建立路由，這便會(huì)導(dǎo)致開銷增大。這里引入Q學(xué)習(xí)算法，在路由建立階段借鑒了 Minsoo Lee等［8］提出的方法，當(dāng)源節(jié)點(diǎn)在第1次接收路由應(yīng)答分組時(shí)，根據(jù)發(fā)送路由請(qǐng)求消息時(shí)記錄下的時(shí)間和接收路由應(yīng)答分組的時(shí)間差計(jì)算端到端時(shí)延估計(jì)Test。

由上述時(shí)延估計(jì)值Test通過(guò)如下公式計(jì)算歸一化路徑時(shí)延估計(jì)值γ：式中：Tetemax為網(wǎng)絡(luò)可允許的端到端時(shí)延的最大值。

根據(jù)歸一化路徑時(shí)延估計(jì)值γ，依據(jù)t-1時(shí)刻Q值對(duì)當(dāng)前時(shí)刻描述網(wǎng)絡(luò)穩(wěn)定性的Qs值和不穩(wěn)定性的Quns值分別進(jìn)行更新，得到更新后的網(wǎng)絡(luò)穩(wěn)定性表征值：

式中：Qs［t］ 為節(jié)點(diǎn)在t時(shí)刻網(wǎng)絡(luò)穩(wěn)定性的Qs值；Quns［t］ 為節(jié)點(diǎn)在t時(shí)刻網(wǎng)絡(luò)不穩(wěn)定性的Quns值；α為學(xué)習(xí)因子，取值范圍為0≤α＜1。

源節(jié)點(diǎn)根據(jù)更新結(jié)果執(zhí)行不同行為，當(dāng)Qs［t］＞Quns［t］ 時(shí)，判斷網(wǎng)絡(luò)狀態(tài)向不穩(wěn)定發(fā)展，減小本條路由的路由生命期；當(dāng)Qs［t］ ＜Quns［t］ 時(shí)，判斷網(wǎng)絡(luò)狀態(tài)向穩(wěn)定發(fā)展，增大本條路由的路由生命期。

該方法能夠在路由建立階段自主感知網(wǎng)絡(luò)的狀態(tài)，并根據(jù)所感知的網(wǎng)絡(luò)狀態(tài)自適應(yīng)配置對(duì)應(yīng)狀態(tài)下合適的路由生存期，增大穩(wěn)定路由的存在時(shí)間，減小不穩(wěn)定路由的存在時(shí)間，從而當(dāng)網(wǎng)絡(luò)狀況良好的時(shí)候減小路徑信息仍然有效，然而因?yàn)樯嫫诘竭_(dá)而被銷毀的路由數(shù)，從而減小發(fā)起路由請(qǐng)求消息的次數(shù)，即減小開銷；當(dāng)網(wǎng)絡(luò)狀況惡化的時(shí)候縮短路由生命期，在一定概率上當(dāng)路由信息沒(méi)有完全失效、發(fā)送的分組完全沒(méi)有回復(fù)之前就銷毀路由，開始新的發(fā)起路由請(qǐng)求的流程。雖然縮短路由生命期會(huì)增加一定的開銷，但是業(yè)務(wù)分組發(fā)出之后沒(méi)有回應(yīng)，源節(jié)點(diǎn)判斷路由已失效之后再重新發(fā)起路由請(qǐng)求會(huì)帶來(lái)額外的延時(shí)，導(dǎo)致業(yè)務(wù)消息端到端時(shí)延增加，而在網(wǎng)絡(luò)狀況較差的情況下，一條路由往往還沒(méi)有到達(dá)生命期時(shí)就已經(jīng)失效，所以在網(wǎng)絡(luò)狀況較差的情況下適當(dāng)?shù)販p小生命期不會(huì)帶來(lái)過(guò)多的開銷，同時(shí)有助于源節(jié)點(diǎn)的路由反應(yīng)速度。

2.2.2 路由維護(hù)階段

通過(guò)在路由建立階段引入Q學(xué)習(xí)算法動(dòng)態(tài)調(diào)整本次建立的路由生存期，可以在不同的網(wǎng)絡(luò)狀態(tài)下自適應(yīng)地符合當(dāng)前的需要。然而Ad Hoc網(wǎng)絡(luò)情況的變化往往是突發(fā)的，路由建立階段作出的對(duì)網(wǎng)絡(luò)狀況的評(píng)估有時(shí)效性，因此需要在路由建立后，發(fā)送業(yè)務(wù)消息階段（即路由信息的實(shí)際使用階段）對(duì)網(wǎng)絡(luò)狀況進(jìn)行評(píng)估并做出自適應(yīng)的調(diào)整。這里采用基于Q-learning的應(yīng)答（ACK）消息監(jiān)測(cè)方法，對(duì)業(yè)務(wù)消息的應(yīng)答ACK進(jìn)行監(jiān)控，記錄收到業(yè)務(wù)類消息ACK的時(shí)延并迭代計(jì)算。ACK在路由協(xié)議中一般作為發(fā)送成功的標(biāo)志，規(guī)定時(shí)間內(nèi)收不到ACK則進(jìn)行重發(fā)或認(rèn)為發(fā)送失敗。這里將源節(jié)點(diǎn)收到ACK的時(shí)刻與發(fā)出數(shù)據(jù)業(yè)務(wù)的時(shí)刻之間時(shí)延作為當(dāng)前路徑質(zhì)量的評(píng)估因素。節(jié)點(diǎn)開始發(fā)送業(yè)務(wù)類消息時(shí)，開始記錄每個(gè)應(yīng)答ACK的到達(dá)時(shí)刻，取最大的時(shí)延Tack作為Tmax，并代入計(jì)算當(dāng)前時(shí)刻網(wǎng)絡(luò)穩(wěn)定性。當(dāng)連續(xù)3次判斷網(wǎng)絡(luò)狀態(tài)在向不穩(wěn)定發(fā)展時(shí)，則嘗試路由切換。

路由切換的過(guò)程如下：源節(jié)點(diǎn)將到達(dá)的數(shù)據(jù)分組，依然采用已建立的路由Rfound發(fā)送，同時(shí)發(fā)起一個(gè)路由請(qǐng)求消息；收到路由應(yīng)答消息后保存至路由應(yīng)答消息鏈表中，并提取路由信息形成待切換路由Rswitch［i］，源節(jié)點(diǎn)將待切換路由與當(dāng)前正在使用的路由信息進(jìn)行比對(duì)，通過(guò)中繼節(jié)點(diǎn)相同程度賦予每個(gè)待切換路由新鮮度Rf，中繼節(jié)點(diǎn)與當(dāng)前路由完全不同Rf為100，完全相同則為0；源節(jié)點(diǎn)通過(guò)比對(duì)每個(gè)待切換路由Rswitch［i］的Rf值，選出中繼節(jié)點(diǎn)最不相同的一條作為最可能的切換路由，當(dāng)業(yè)務(wù)分組到達(dá)后則采用新的路由發(fā)送分組。因?yàn)榍袚Q路由是當(dāng)原有路由穩(wěn)定性不斷惡化的情況下在失效前建立的備份路由，則其選擇標(biāo)準(zhǔn)為與原有路由中繼節(jié)點(diǎn)差異最大，從而最大可能避免原有路由中鏈路狀態(tài)惡化的中繼節(jié)點(diǎn)影響。切換路由的生命期與原路由相同，并且只建立1次，視為原有路由的延續(xù)。

中繼節(jié)點(diǎn)轉(zhuǎn)發(fā)業(yè)務(wù)類消息的同時(shí)，也監(jiān)測(cè)本地轉(zhuǎn)發(fā)的回溯到源節(jié)點(diǎn)的ACK回復(fù)消息，同時(shí)代入Q學(xué)習(xí)算法迭代計(jì)算。當(dāng)連續(xù)3次判斷網(wǎng)絡(luò)狀態(tài)不穩(wěn)定后，認(rèn)為當(dāng)前路由在向不穩(wěn)定狀態(tài)發(fā)展，此時(shí)中繼節(jié)點(diǎn)在需要進(jìn)行轉(zhuǎn)發(fā)至源節(jié)點(diǎn)的ACK消息上設(shè)置一個(gè)告警標(biāo)志位。源節(jié)點(diǎn)收到ACK之后讀取標(biāo)志位，嘗試進(jìn)行路由切換。

當(dāng)源節(jié)點(diǎn)每連續(xù)3次判斷當(dāng)前網(wǎng)絡(luò)狀態(tài)趨于穩(wěn)定的時(shí)候，則增大當(dāng)前路由生命周期，繼續(xù)維持當(dāng)前較好的路由。直到路由生命結(jié)束或者連續(xù)3次判斷網(wǎng)絡(luò)狀態(tài)不穩(wěn)定后發(fā)起路由建立過(guò)程。通過(guò)對(duì)業(yè)務(wù)類消息ACK回復(fù)的監(jiān)測(cè)，可以在路由維護(hù)階段實(shí)時(shí)自適應(yīng)地對(duì)當(dāng)前路由狀態(tài)做1個(gè)預(yù)判，從而及時(shí)尋找替代路由。源節(jié)點(diǎn)不必當(dāng)路由失效發(fā)送失敗后才被動(dòng)地開始建立路由，在路由狀況開始惡化的時(shí)候便可以試圖建立新路由準(zhǔn)備進(jìn)行路由切換，通過(guò)這種策略使得源節(jié)點(diǎn)更加靈活，能夠自適應(yīng)地調(diào)整路由參數(shù)，以契合網(wǎng)絡(luò)當(dāng)前狀態(tài)。源節(jié)點(diǎn)處理業(yè)務(wù)類消息ACK的流程如圖6所示。

圖6 源節(jié)點(diǎn)收到業(yè)務(wù)消息ACK處理流程

3 仿真和分析

目前使用較為普遍的網(wǎng)絡(luò)仿真軟件有OPNET［10］和NS2。本文采用OPNET對(duì)協(xié)議進(jìn)行仿真分析。OPNET Modeler采用了3層建模機(jī)制，分別在進(jìn)程層、節(jié)點(diǎn)層和網(wǎng)絡(luò)層進(jìn)行建模。進(jìn)程描述通過(guò)狀態(tài)機(jī)的轉(zhuǎn)移體現(xiàn)邏輯狀態(tài)變化，具有邏輯清晰、維護(hù)方便的特點(diǎn)。仿真運(yùn)行的過(guò)程中，OPNET采用了離散事件驅(qū)動(dòng)的模擬機(jī)制［10］，即當(dāng)事件產(chǎn)生時(shí)，仿真核心觸發(fā)事件驅(qū)動(dòng)，推動(dòng)仿真時(shí)間推進(jìn)。

為比較基于Q-learning的自適應(yīng)DSR協(xié)議的性能，建立一個(gè)簡(jiǎn)單的Ad Hoc網(wǎng)絡(luò)。在600m×600m的范圍內(nèi)，隨機(jī)放置了100個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)移動(dòng)模型采用隨機(jī)路點(diǎn)移動(dòng)模型，節(jié)點(diǎn)最大通信范圍為200m，通信為雙向?qū)ΨQ鏈路。圖7～圖10為仿真結(jié)果。

圖7 路由請(qǐng)求分組數(shù)量

從圖7可以看出，加入Q學(xué)習(xí)算法后DSR協(xié)議在業(yè)務(wù)量較輕的情況下能明顯降低路由請(qǐng)求分組的數(shù)量。因?yàn)榫W(wǎng)絡(luò)狀況較好的時(shí)候Q-DSR能夠根據(jù)Q學(xué)習(xí)迭代計(jì)算結(jié)果動(dòng)態(tài)地增加路由生存期，使得鏈路質(zhì)量較好的路由能夠更長(zhǎng)時(shí)間地進(jìn)行服務(wù)，從而降低非必要的路由請(qǐng)求分組（RREQ）發(fā)送概率。而路由請(qǐng)求分組是以泛洪的方式在網(wǎng)絡(luò)中擴(kuò)散，對(duì)網(wǎng)絡(luò)的影響較大，降低路由請(qǐng)求分組數(shù)能夠有效降低開銷。

從圖8可看出，通過(guò)Q學(xué)習(xí)對(duì)業(yè)務(wù)類消息的ACK接收時(shí)延的計(jì)算，能夠判斷當(dāng)前路由質(zhì)量發(fā)生怎樣的變化，從而及時(shí)調(diào)整路由生存期或切換新路由；而傳統(tǒng)的DSR協(xié)議只有當(dāng)業(yè)務(wù)分組發(fā)送失敗才嘗試建立新路由，導(dǎo)致業(yè)務(wù)分組時(shí)延額外增加了等待路由建立時(shí)間，浪費(fèi)時(shí)間和開銷資源。因?yàn)槁酚煞磻?yīng)及時(shí)，在業(yè)務(wù)量增大的情況下，能夠保持高于傳統(tǒng)DSR協(xié)議的吞吐量。

由圖9可看出，因?yàn)槟軌蚣皶r(shí)判斷出路由質(zhì)量，故采取延長(zhǎng)生存期或者發(fā)起路由切換的策略，從而加快路由反應(yīng)。在一定概率上，當(dāng)路由質(zhì)量高時(shí)繼續(xù)維護(hù)本條路由，當(dāng)路由質(zhì)量下降時(shí)及時(shí)采取替補(bǔ)

圖8 吞吐量

策略，從而自適應(yīng)地在節(jié)點(diǎn)發(fā)送失敗之前做出調(diào)整。Q＿DSR協(xié)議能夠保持較低的端到端時(shí)延。

圖9 端到端時(shí)延

選取業(yè)務(wù)量為4packets／s，通過(guò)改變速度測(cè)試Q＿DSR與傳統(tǒng)DSR協(xié)議在拓?fù)渥兓闆r下的端到端性能，從圖10可以看出，隨著節(jié)點(diǎn)運(yùn)動(dòng)速度的增加，拓?fù)渥兓觿?，傳統(tǒng)DSR路由失效率增加；而當(dāng)業(yè)務(wù)消息發(fā)送失敗后才開始建立新路由，則帶來(lái)額外的等待時(shí)延。基于Q學(xué)習(xí)算法的DSR協(xié)議能夠判斷路由質(zhì)量，下降后及時(shí)切換新路由，在一定概率上節(jié)省了等待時(shí)間，保持較低的端到端時(shí)延。在網(wǎng)絡(luò)拓?fù)渥儞Q迅速、鏈路質(zhì)量不穩(wěn)定的網(wǎng)絡(luò)狀況下尤為明顯。

圖10 節(jié)點(diǎn)不同移動(dòng)速度的端到端時(shí)延

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

自適應(yīng)Q＿DSR協(xié)議的改進(jìn)是在路由發(fā)現(xiàn)階段能夠根據(jù)建立路由時(shí)刻的網(wǎng)絡(luò)狀態(tài)動(dòng)態(tài)調(diào)整路由生存期，使得狀態(tài)良好情況下的路由能夠服務(wù)更久從而降低開銷；同時(shí)在路由維護(hù)階段通過(guò)監(jiān)測(cè)ACK判斷業(yè)務(wù)消息發(fā)送時(shí)刻的網(wǎng)絡(luò)狀態(tài)主動(dòng)切換質(zhì)量開始惡化的路由，從而提高路由反應(yīng)，提升吞吐量性能，降低端到端時(shí)延。通過(guò)仿真可以看出自適應(yīng)Q＿DSR協(xié)議能夠在網(wǎng)路狀態(tài)良好的情況下減小開銷，而在狀態(tài)較差的情況下減少路由等待時(shí)間，加快路由反應(yīng)速度，從而提升端到端性能。不足的是，通過(guò)ACK監(jiān)測(cè)有時(shí)不能準(zhǔn)確反應(yīng)發(fā)送業(yè)務(wù)消息時(shí)刻的網(wǎng)絡(luò)狀態(tài)，存在誤判的可能，需要進(jìn)一步改進(jìn)來(lái)提高算法的準(zhǔn)確度。在網(wǎng)絡(luò)狀態(tài)變化較快、節(jié)點(diǎn)較多、形成路由的跳數(shù)較大的情況下，自適應(yīng)Q＿DSR協(xié)議是較簡(jiǎn)單和高效的路由協(xié)議。

［1］ 張祿林，李承恕.MANET路由選擇協(xié)議的比較分析研究［J］.電子學(xué)報(bào)，2000，28（11）：88-92.

［2］ Johnson David B，Maltz David A.Protocols for adaptive wireless and mobile networking［J］.IEEE Personal Communications，1996，3（1）：34-42.

［3］ Rendong Bai，Singhal M.DOA：DSR over AODV routing for mobile Ad Hoc networks［J］.IEEE Transactions Mobile Computing，2006，5（10）：1403-1416.

［4］ Hashim R，Nasir Q，Harous S.Adaptive Multi-path Qos aware dynamic source routing protocol for mobile Ad Hoc network［A］.Innovations in Information Technology［C］.Dubai，2006：1-5.

［5］ 孟利民，吳晚霞.基于鏈路穩(wěn)定性算法的DSR協(xié)議研究［J］.通信學(xué)報(bào)，2008，29（11）：46-50.

［6］ Kaelbling L P，Littman M L，Moore A W.Reinforcement learning：a survey［J］.Journal of Artificial Intelligence Research，1996，4：237-285.

［7］ Watkins C，Dayan P.Q-learning［J］.Machine Learning，1992（3-4）：279-292.

［8］ Minsoo Lee，Dan Marconett，Xiaohui Ye，et al.Cognitive network management with reinforcement learning for wireless mesh networks［A］.IPOM 2007LNCS 4786［C］，Berlin，2007：168-179.

［9］ Boyan J A，Littman M L.Packet routing in dynamically changing networks：a reinforcement learning approach［A］.Advances In Neural Information Processing Systems［C］，1994：671-678.

［10］陳敏.OPNET網(wǎng)絡(luò)仿真［M］.第1版.北京：清華大學(xué)出版社，2004.