機(jī)會(huì)網(wǎng)絡(luò)下基于價(jià)值評判的馬爾科夫決策過程改進(jìn)Epidemic算法*

曹 偉

（廣東警官學(xué)院網(wǎng)絡(luò)信息中心，廣東 廣州510000）

引言

機(jī)會(huì)網(wǎng)絡(luò) （Opportunistic Networks）［1］［2］主要應(yīng)用于鄉(xiāng)村網(wǎng)絡(luò)、戰(zhàn)地網(wǎng)絡(luò)等不需要源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)間存在完整鏈路的場景。在實(shí)際的機(jī)會(huì)網(wǎng)絡(luò)當(dāng)中，諸多原因可能導(dǎo)致網(wǎng)絡(luò)不能連通。為應(yīng)對這種情況，機(jī)會(huì)網(wǎng)絡(luò)采取了“存儲(chǔ)-攜帶-轉(zhuǎn)發(fā)”的傳輸模式?，F(xiàn)階段的機(jī)會(huì)網(wǎng)絡(luò)研究方向包括有路由算法［3］、緩存管理、移動(dòng)模型等。Epidemic算法［4］是一種經(jīng)典算法，本文以Epidemic算法為參照算法。該算法基于泛洪機(jī)制的方式，不加以區(qū)分消息節(jié)點(diǎn)，將數(shù)據(jù)復(fù)制到所相遇的每一個(gè)節(jié)點(diǎn)，最終將消息遞交至目的節(jié)點(diǎn)。由于空間存儲(chǔ)、帶寬等資源是有限的，無限制的傳遞相同數(shù)據(jù)則會(huì)浪費(fèi)有限的資源，從而降低機(jī)會(huì)網(wǎng)絡(luò)的傳輸性能。同時(shí)在機(jī)會(huì)網(wǎng)絡(luò)內(nèi)可能存在惡意節(jié)點(diǎn)企圖去攻擊網(wǎng)絡(luò)、延遲傳輸或毀滅數(shù)據(jù)。

基于上述原因，本文提出了一種在Epidemic算法的基礎(chǔ)上，通過基于馬爾科夫決策過程來構(gòu)建機(jī)會(huì)路由的算法，為節(jié)點(diǎn)提供一種可靠的轉(zhuǎn)發(fā)方法，對Epidemic算法進(jìn)行泛洪控制，從而優(yōu)化機(jī)會(huì)網(wǎng)絡(luò)系統(tǒng)中的路由可用性和可靠性。

1 路由協(xié)議設(shè)計(jì)

1.1 算法總體設(shè)計(jì)框架

首先建立一個(gè)完全符合馬爾科夫決策過程的機(jī)會(huì)網(wǎng)絡(luò)模型。其中，建立的基于馬爾科夫決策過程的節(jié)點(diǎn)轉(zhuǎn)發(fā)策略：若當(dāng)前相遇的節(jié)點(diǎn)為消息目的節(jié)點(diǎn)，則直接遞交消息；否則在節(jié)點(diǎn)每次遇到一個(gè)節(jié)點(diǎn)后，對該節(jié)點(diǎn)進(jìn)行綜合價(jià)值計(jì)算和記錄，當(dāng)連續(xù)遇到前k個(gè)非目的節(jié)點(diǎn)后，將消息復(fù)制給之后遇到的第一個(gè)綜合價(jià)值高于前k個(gè)已相遇節(jié)點(diǎn)的節(jié)點(diǎn)。此后清空價(jià)值記錄表重復(fù)執(zhí)行該流程，直到消息遞交成功或消息生命周期結(jié)束。如圖1所示。

圖1 算法總體框架設(shè)計(jì)

1.2 場景描述

如圖2所示，在一片隨機(jī)區(qū)域中，定義源節(jié)點(diǎn)s，目的節(jié)點(diǎn)e，場景中存在不同優(yōu)先級梯度的節(jié)點(diǎn)n個(gè)。假定從節(jié)點(diǎn)s轉(zhuǎn)發(fā)消息到節(jié)點(diǎn)e，則在綜合價(jià)值梯度上s的價(jià)值最低，e最高。消息從節(jié)點(diǎn)s向節(jié)點(diǎn)e通過綜合價(jià)值評判方式，從低向高的方向傳輸，通過相遇節(jié)點(diǎn)的綜合價(jià)值，判斷是否要進(jìn)行消息轉(zhuǎn)發(fā)。由于所有的節(jié)點(diǎn)都攜帶各種消息，以規(guī)則的移動(dòng)模型進(jìn)行運(yùn)動(dòng)與其他節(jié)點(diǎn)的相遇是隨機(jī)的，因此符合離散時(shí)間有限階段馬爾科夫決策過程。

圖2 機(jī)會(huì)網(wǎng)絡(luò)傳遞過程場景

1.3 綜合價(jià)值計(jì)算

本文綜合價(jià)值通過節(jié)點(diǎn)之間的遞交預(yù)測值進(jìn)行分析。遞交預(yù)測值的計(jì)算公式如下：

（1）概率的更新：對于節(jié)點(diǎn)a：

Pinit是遞交預(yù)測值初始化常數(shù)，參考值為0.75；P(a,b)old為節(jié)點(diǎn)a,b在本次相遇之前的遞交預(yù)測值。

（2）概率的衰減：對于節(jié)點(diǎn)a：

其中γ是衰減常數(shù)，γ∈(0,1]參考值為0.98；k是從上次衰減開始計(jì)算所經(jīng)歷的時(shí)間單元個(gè)數(shù)。

（3）概率的傳遞：對于節(jié)點(diǎn)a針對于其他任何一個(gè)節(jié)點(diǎn)c（c不包含相遇節(jié)點(diǎn)b）：

其中β是傳遞系數(shù)，參考值為0.25，遞交預(yù)測值的傳遞，利用遞交預(yù)測值的傳遞性更新。

1.4 受控洪泛設(shè)計(jì)

任一節(jié)點(diǎn)以馬爾科夫方式移動(dòng)，通過基于馬爾科夫決策過程的消息轉(zhuǎn)發(fā)策略構(gòu)建模型。當(dāng)消息源節(jié)點(diǎn)與其他節(jié)點(diǎn)相遇時(shí)，要對該相遇節(jié)點(diǎn)的綜合價(jià)值進(jìn)行判斷，滿足條件才轉(zhuǎn)發(fā)消息至該節(jié)點(diǎn)上。定義馬爾科夫決策過程狀態(tài)集S，狀態(tài)集S包含兩個(gè)元素，分別為a和b，其中a表示當(dāng)前與本節(jié)點(diǎn)相遇的節(jié)點(diǎn)不是目的節(jié)點(diǎn)，b代表當(dāng)前與本節(jié)點(diǎn)相遇的節(jié)點(diǎn)是目的節(jié)點(diǎn)，因此S∈(a,b)。

定義狀態(tài)轉(zhuǎn)換集A(S)∈(x,y)，其中行動(dòng)x表示跳過當(dāng)前節(jié)點(diǎn)，并準(zhǔn)備相遇下一個(gè)節(jié)點(diǎn)；行動(dòng)y表示傳送消息給當(dāng)前節(jié)點(diǎn)。由馬爾科夫性質(zhì)可知，遞交不依賴當(dāng)前狀態(tài)Snow，且只要采取行動(dòng)x，該階段的過程就不斷持續(xù)。定義轉(zhuǎn)移概率，在時(shí)刻t+1，恰好在前n+1個(gè)節(jié)點(diǎn)中遇到目的節(jié)點(diǎn)的概率是：

根據(jù)式(5)，則未遇到目的節(jié)點(diǎn)的概率是：

設(shè)節(jié)點(diǎn)總數(shù)目為n，消息轉(zhuǎn)發(fā)策略為先觀察k個(gè)候選節(jié)點(diǎn)，通過比較綜合價(jià)值，記錄最優(yōu)節(jié)點(diǎn)Node(A)。在放棄前k個(gè)節(jié)點(diǎn)后，選擇第1個(gè)優(yōu)于Node(A)的節(jié)點(diǎn)Node(B)。k的求解過程如下：

對于某個(gè)固定的k，在總節(jié)點(diǎn)數(shù)目n確定下，如果最適合的節(jié)點(diǎn)出現(xiàn)在第i個(gè)位置k＜i≤n，且自k+1至i-1，各位置的節(jié)點(diǎn)綜合價(jià)值小于前k位置中的最優(yōu)節(jié)點(diǎn)，就要滿足在前k個(gè)節(jié)點(diǎn)里含有在前i-1個(gè)節(jié)點(diǎn)中的最佳節(jié)點(diǎn)，共有k(i-1)個(gè)可能?？紤]所有可能的i，在前k個(gè)節(jié)點(diǎn)之后能選中最佳節(jié)點(diǎn)的總概率P(k)：

用x來表示k/n的值，并且假設(shè)n充分大，則上述公式可以寫成：

對-x·lnx求導(dǎo)，并令這個(gè)導(dǎo)數(shù)為0，可以解出x的最優(yōu)值，x=1/e。

因x=k/n且k是自然數(shù)，對結(jié)果取整：本文中的路由算法轉(zhuǎn)發(fā)策略其核心思想是記錄與消息節(jié)點(diǎn)相遇的前k個(gè)節(jié)點(diǎn)，若所遇節(jié)點(diǎn)為消息目的節(jié)點(diǎn)則遞交消息；若在前k個(gè)節(jié)點(diǎn)中為消息目的節(jié)點(diǎn)，則記錄最佳節(jié)點(diǎn)并放棄前k個(gè)節(jié)點(diǎn)，對剩下的節(jié)點(diǎn)范圍內(nèi)首次出現(xiàn)的優(yōu)于被記錄節(jié)點(diǎn)的節(jié)點(diǎn)進(jìn)行消息傳遞。傳遞完成后，再次循環(huán)上述步驟直到消息傳遞完畢或生命周期結(jié)束為止。

2 性能評估

本實(shí)驗(yàn)通過在機(jī)會(huì)網(wǎng)絡(luò)仿真平臺ONE上實(shí)現(xiàn)，模擬區(qū)域范圍為4500m×3400m；每個(gè)節(jié)點(diǎn)以藍(lán)牙4.0協(xié)議傳輸，設(shè)定節(jié)點(diǎn)的傳輸半徑10m；節(jié)點(diǎn)共分兩組，由行人組1和行人組2組成，移動(dòng)模型采用ShortestPathMapBasedMovement算法；緩存空間為50Mb；消息大小為512Kb-1Mb。行人移動(dòng)速度為[0.5,1.5]km/h；消息產(chǎn)生間隔為25s至35s。并對仿真結(jié)果進(jìn)行了比較。其他參數(shù)因仿真場景而不同,這類參數(shù)在具體場景設(shè)定。

2.1 投遞成功率對比

通過對Epidemic和NewEpidemic兩個(gè)路由算法進(jìn)行仿真對比，設(shè)置節(jié)點(diǎn)總數(shù)分別為：100～200，每次遞增10個(gè)，則同時(shí)對比相遇節(jié)點(diǎn)按計(jì)算37%、20%和50%的比較，結(jié)果分別如圖3、圖4、圖5所示。

圖3 不同節(jié)點(diǎn)數(shù)量下的報(bào)文成功遞交率對比

如圖3所示，NewEpidemic算法在選取37%的觀察節(jié)點(diǎn)樣本時(shí)的性能最優(yōu)，而缺乏副本數(shù)量控制機(jī)制的傳染路由（Epidemic）整體性能最差。在NewEpidemic算法中，隨著節(jié)點(diǎn)數(shù)量的增加，報(bào)文成功遞交率有波動(dòng)但趨于穩(wěn)定。與NewEpidemic-20和NewEpidemic-50算法相比，在NewEpidemic-37中，充分利用了節(jié)點(diǎn)的歷史信息，使遞交預(yù)測值的計(jì)算更合理、有效，從而使報(bào)文能更快更多地遞交給目的節(jié)點(diǎn)，即提高報(bào)文成功遞交率。

2.2 擁塞對比

圖4 不同節(jié)點(diǎn)數(shù)量下的擁塞對比

如圖4所示的實(shí)驗(yàn)結(jié)果可以看出，在不同節(jié)點(diǎn)數(shù)量下容易發(fā)現(xiàn)NewEpidemic-37協(xié)議有一定的優(yōu)勢。隨著產(chǎn)生節(jié)點(diǎn)總數(shù)的提升，盡管擁塞率上升，但NewEpidemic-37網(wǎng)絡(luò)擁塞也保持較好的優(yōu)勢，能有效控制網(wǎng)絡(luò)開銷。

2.3 平均跳數(shù)對比

在計(jì)算平均跳數(shù)場景中，NewEpidemic-37協(xié)議具有較低的平均跳數(shù)，延遲較低。由實(shí)驗(yàn)結(jié)果可以看出，隨著節(jié)點(diǎn)密度的提高，平均跳數(shù)增大，NewEpidemic-37協(xié)議保證了高效率的消息投遞跳數(shù)。

綜上，通過對比發(fā)現(xiàn)，NewEpidemic路由算法在觀察37%的節(jié)點(diǎn)后，基于馬爾科夫決策過程得出評判價(jià)值來構(gòu)建機(jī)會(huì)路由的算法，為節(jié)點(diǎn)提供一種可靠的下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)方法，對機(jī)會(huì)網(wǎng)絡(luò)的性能具有保證，能夠適應(yīng)機(jī)會(huì)網(wǎng)絡(luò)的復(fù)雜工作環(huán)境等特點(diǎn)。

3 結(jié)束語

本文在分析機(jī)會(huì)網(wǎng)絡(luò)領(lǐng)域中現(xiàn)有的Epidemic路由算法特點(diǎn)和實(shí)際應(yīng)用中存在的各種問題的基礎(chǔ)上，針對Epidemic路由算法導(dǎo)致機(jī)會(huì)網(wǎng)絡(luò)產(chǎn)生大量冗余數(shù)據(jù)的實(shí)際問題，提出了New-Epidemic算法。該算法基于價(jià)值評判的馬爾科夫決策過程對洪泛進(jìn)行控制。實(shí)驗(yàn)結(jié)果表明，NewEpidemic算法在不同節(jié)點(diǎn)數(shù)量分布的情況下均有良好的機(jī)會(huì)路由傳輸性能，提高機(jī)會(huì)路由的魯棒性。