機會網(wǎng)絡下基于價值評判的馬爾科夫決策過程改進Epidemic算法*

曹 偉

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

引言

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

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

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

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

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

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

1.2 場景描述

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

圖2 機會網(wǎng)絡傳遞過程場景

1.3 綜合價值計算

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

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

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

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

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

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

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

1.4 受控洪泛設(shè)計

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

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

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

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

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

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

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

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

2 性能評估

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

2.1 投遞成功率對比

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

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

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

2.2 擁塞對比

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

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

2.3 平均跳數(shù)對比

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

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

3 結(jié)束語

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