基于馬爾可夫決策過程的機會網絡轉發策略*

張　楊，王小明+，林亞光，張　丹

1.現代教學技術教育部重點實驗室，西安710119

2.陜西師范大學計算機科學學院，西安710119

* The National Natural Science Foundation of China under Grant No. 61373083 (國家自然科學基金); the Fundamental Research Funds for the Central Universities of China under Grant No. GK201401002 (中央高校基本科研業務費專項資金); the Program of Science and Technology Innovation Team of Shaanxi Province under Grant No. 2014KTC-18 (陜西省重點科技創新團隊項目).

Received 2015-04,Accepted 2015-08.

CNKI網絡優先出版：2015-08-27, http://www.cnki.net/kcms/detail/11.5602.TP.20150827.1531.012.html

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10(01)-0082-11

?

基于馬爾可夫決策過程的機會網絡轉發策略*

張楊1,2，王小明1,2+，林亞光1,2，張丹1,2

1.現代教學技術教育部重點實驗室，西安710119

2.陜西師范大學計算機科學學院，西安710119

* The National Natural Science Foundation of China under Grant No. 61373083 (國家自然科學基金); the Fundamental Research Funds for the Central Universities of China under Grant No. GK201401002 (中央高校基本科研業務費專項資金); the Program of Science and Technology Innovation Team of Shaanxi Province under Grant No. 2014KTC-18 (陜西省重點科技創新團隊項目).

Received 2015-04,Accepted 2015-08.

CNKI網絡優先出版：2015-08-27, http://www.cnki.net/kcms/detail/11.5602.TP.20150827.1531.012.html

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10(01)-0082-11

E-mail: fcst@vip.163.com

http://www.ceaj.org

Tel: +86-10-89056056

摘要：在機會網絡節點隨機移動的場景中，提高路由算法性能評價中的投遞率，控制開銷率，降低平均遲延是持續的研究方向。由于目前機會網絡結構稀疏和拓撲多變，單副本路由轉發策略效率較低。通過結合花粉布朗運動與機會網絡節點的隨機運動的相似性，并分析節點隨機運動的規律，定義了一種基于馬爾可夫決策過程的節點轉發策略。該策略在平均延時適當增加的情況下，可以有效控制網絡開銷率，提高消息投遞率。最后通過仿真實驗驗證了理論模型的正確性。

關鍵詞：機會網絡；馬爾可夫決策；投遞率

1　引言

機會網絡[1-2]（opportunistic network）源于容忍延遲網絡[3]（delay tolerant networks，DTN）和移動自組網[4]（mobile ad-hoc networking，MANET），可以視為是兩者的子類。機會網絡是一種不需要在源節點和目的節點之間存在完整路徑，利用節點移動帶來的相遇機會實現網絡通信，時延和分裂可容忍的自組織網絡[5]。

在機會網絡路由節點轉發算法評價分析中，需要關心3個參數[6]：（1）遞交率，目的節點成功接收到的報文與所有目的節點接收的報文個數之間的比值；（2）平均遲延，被成功遞交的報文從源節點到達目的節點所耗費的時間總和與遞交報文個數之比；（3）開銷率，成功遞交的數據包被中繼的次數與被成功遞交的數據包個數之差再除以被成功遞交的數據包的個數。一個有效的節點轉發策略需要考慮3個參數之間的約束以達到最佳期望[4，7-8]。

單副本[9-11]的路由策略是同一時間內網絡中只保留消息的一個副本。現有幾種基于單副本的機會網絡節點轉發策略：（1）First Contact[12]，該算法源節點將數據分組轉發給它遇到的第一個節點；（2）Direct Delivery[13]，該算法源節點僅在遇到目標節點時才將數據分組轉發給下一節點；（3）隨機路由[14]以概率P將消息發送給其遇到的節點；（4）Seek and Focus[11]結合了隨機路由和基于效用路由的轉發策略；（5）Simbet[15]中節點只將數據分組轉發給具備一定相似度的節點。

在某些隨機網絡場景中，如地震、海嘯等災難后短期缺乏充電條件的情況下，幸存者之間用智能手機組成一個隨機網絡傳遞各種救援消息。考慮到網絡節點設備的電源有限，需要節省網絡中的開銷率，同時提高消息對目標節點的投遞率。結合隨機網絡中節點隨機運動，并且在單副本的情況下，在有效保持源節點對目的節點的投遞率的同時，控制一定的開銷率使平均延遲最小，即找出一種機會網絡節點的轉發策略，使該策略的評價參數以此方式達到最優平衡。

本文機會網絡中的節點在規定區域內的隨機移動類似于花粉的布朗運動[16]。對布朗運動的數學描述是維納過程[17]，而維納過程具有馬爾可夫性質[18]。馬爾可夫決策過程[19]（Markov decision processes，MDP）根據每個時刻觀察到的狀態，從可用的行動集合中選用一個行動作出決策，系統下一步的狀態是隨機的，并且其狀態轉移概率具有馬爾可夫性。本文利用機會網絡隨機過程的馬爾可夫性尋找符合課題要求的單副本節點轉發策略。

本文研究了機會網絡單副本情況下現有的兩種轉發策略：First Contact和Direct Delivery。在此基礎上，分析了另外兩種已有單副本路由Seek and Focus 和Simbet。針對機會網絡3種路由評價分析參數，進行了如下研究：

（1）找出了一種機會網絡中基于馬爾可夫決策過程的節點轉發狀態轉移規律，并且遵循規律推算出與此相關的參數平衡收益；

（2）根據上述規律提出了一種節點轉發策略，該策略可以在一定的平均時延下，用有限的開銷率使節點投遞率最大化；

（3）通過實驗對比了多組本文所提策略相關參數和經典單副本路由，用仿真實驗驗證了模型和理論的正確性。

2　相關工作

現有機會路由按選擇廣播節點的方式可分為兩類[20-22]：第一類算法根據鏈路統計信息為每個節點賦予一個全局度量值，又稱優先級或梯度，數據總是從低優先級的節點向高優先級的節點傳輸，而目的節點具有最高的優先級，從而保證傳輸方向正確；第二類算法為每個節點指定一組可能的下一跳節點集合，又稱轉發集合或候選集合，該類算法通過避免環路以保證傳輸方向正確。這兩類算法都借鑒了傳統無線路由的轉發機制，每個廣播節點將數據包成功轉發后不會再次參與廣播，下一跳節點從剛接收到數據包的節點中選擇。

First Contact路由[9-10，12]，在理論上不考慮丟包和延時的情況下，對目標節點的投遞概率為f1＝1/n，開銷率最大。但是在實際情況中，該算法通過節點多次相遇轉發完成投遞，因為最先遇到的節點是未知的，所以該策略具有一定的盲目性，在大范圍的隨機場景中投遞率不高。

Direct Delivery路由[9-10，13]，理論上對目標節點的投遞概率f2＝1，但是平均延時最大；實際情況中，每個消息只傳輸一次，從而總的傳輸次數最少，但是在間歇連接的網絡中，由于鏈路的可靠性不能保障，從而導致投遞率低，平均遲延高。

P路由[11，14]，對于任意非目的節點，會以一定概率P(P＞0)將本節點所持有的消息傳遞給對方，其投遞率與P有關。在沒有任何先驗知識的情況下，無法選擇一個符合網絡最優情況的概率P。

Seek and Focus路由[9-11]，這是一個混合策略，此路由存在一個二維策略函數F(P，S)，P為節點轉發概率，S為節點效用值的閥值。當遇到隨機節點n時，如果當前節點效用值低于閥值，則執行隨機概率轉發；如果當前節點效用值大于閥值，則執行基于效用的轉發。節點的效用值根據兩類路由基礎算法在不同的場景中存在不同的定義方法。SF路由實際上是P路由的改進版本。同樣在沒有任何先驗知識的情況下，無法選擇合適的轉發概率P和閥值S，應該在具體場景中以實驗來驗證。

Simbet路由[9，15]，該策略以社會網絡的思想確定相遇節點的相似度判斷是否轉發消息。而節點相似度的判斷標準是根據第一類路由算法為每個節點賦予一個全局度量值，即節點等級。節點的相似度有運動相似度和節點社會屬性相似度等。

文獻[19]提到馬氏決策過程的定義，系統地分析了其理論框架并給出了有效的算法。除此之外，該文獻定義了有現階段馬爾可夫決策過程的五重組：

{T，S，A(i)，P(?|i，α)，R(i，α)}

其中，T為離散時間決策階段；S為系統所有可能狀態，在每個決策時刻，對系統的描述就是狀態，S也稱為狀態空間。如果在任一個決策時刻，決策者觀察到的狀態是i∈S，他可以在狀態i的可用行動集A(i)中選取行動α，其中A(i)也稱為行動空間，并且假定S 和A(i)都不依賴于時刻T，除非特別聲明，總考慮S和A(i)都是離散的情況。任意一個決策時刻，在狀態i采取行動α∈A(i)后，有兩個結果：（1）決策獲得報酬R(i，α)；（2）下一個決策時刻系統所處的狀態由概率分布P(?|i，α)決定。R(i，α)是定義在i∈S和α∈A(i)上的實值函數。當R(i，α)為正值時，表示收入；當其為負值時，表示費用。從模型的角度來看，報酬R(i，α)是即時的。通常情況下報酬還依賴下一個決策時刻的狀態j，即R(i，α，j)，那么行動α的期望值報酬為：

非負函數P(j|i，α)是下一個決策時刻系統轉移到狀態j的概率。函數P(j|i，α)被稱為轉移概率函數。根據馬氏狀態轉移矩陣性質，通常假設：

文獻[11]分析了主流單副本機會網絡路由，并且提出了基于馬爾可夫鏈的節點概率轉發策略。文獻[23]分析了校園環境下學生所攜帶移動節點的運動特點，采用半馬爾可夫過程模擬節點運動并建立了相應的DTN節點移動模型，對模型進行了仿真和分析，將仿真結果與隨機路徑點（random way point，RWP[24]）模型及實際路徑信息進行對比，可以看出半馬爾可夫過程模型能夠更準確地描述實際網絡環境。文獻[25]中的算法具有學習功能，能夠解決復雜的容遲容斷網絡環境中的高延遲和頻繁割裂問題。文獻[26]提出了基于網絡拓撲圖的馬氏鏈模型，為多副本的節點轉發策略找到了基于馬氏鏈的預測投遞機制。

現有關于應用馬爾可夫決策過程的文獻很多都是研究多副本情況下的機會網絡轉發策略。因此本文結合機會節點移動的特點，利用馬爾可夫決策過程構建機會網絡節點轉發策略，研究和對比分析單副本情況下的投遞率、開銷率與平均時延之間的平衡關系。

3　機會網絡節點轉發策略

首先建立一個完全隨機的機會網絡模型，該隨機模型完全符合馬爾可夫決策過程。然后靜態定義網絡中節點的優先級，建立基于馬爾可夫決策過程的節點轉發策略模型。該策略的思想是，在節點遇到前[N/e]個節點中，如果遇到目的節點則直接遞交消息；如果沒有遇到目的節點，則遞交于下一個遇到的且當前優先級最高的節點。

3.1場景描述

如圖1所示，在一個地形隨機的區域中，存在不同優先級梯度的節點N個，按照第一類基礎路由算法定義源節點S，目的節點D，場景中有N個節點。假定從源節點轉發消息到目的節點，按照優先級梯度，S的優先級最小，D最大。從低優先級的節點向高優先級的節點傳輸，根據遇見節點的優先級梯度來判斷消息轉發與否。考慮到場景中源節點攜帶消息按照隨機方式運動，途中遇見的任意節點也是隨機的，符合離散時間有限階段馬爾可夫決策過程。

Fig.1 Stochastic model of opportunistic network圖1　機會網絡隨機場景

3.2轉發策略

本文不考慮計算節點的優先級，直接定義節點的優先級排序，把源節點S定義為Lv0，把目的節點D定義為Lv(N?1)：

Lv0＜Lv1＜Lv2＜…＜Lv(N?1)

該策略是找到源節點攜帶消息出發，遇見高優先級的節點然后轉發消息，重復路由策略直到目的節點收到消息過程結束。節點按照隨機方式移動，定義基于馬爾可夫決策過程的節點轉發策略模型。

當源節點隨機遇見某一個節點時，需要判斷高優先級節點后決定消息是否轉發，這里設定從階段1開始到階段N時結束，因此決策的階段數與節點數目相同，即有N個不同優先度的節點，就會有T個決策時刻。定義馬爾可夫決策過程狀態空間S′＝{0，1}。狀態空間S′有兩個元素0和1。其中1代表當前的節點是目的節點；0表示當前的節點不是目的節點。

對于每一個狀態定義行動集A(0)＝A(1)＝{X，Y}，行動Y表示傳送消息給當前節點，行動X表示跳過當前節點，并準備相遇下一個節點。根據機會路由投遞消息的要求，除了在全部過程停止時，所有其他時間階段的報酬都是0，也就是在選取行動X（放棄當前的節點）時的報酬總是0。反之，只有當采取行動Y的時刻系統具備有效報酬。有效報酬的概念表示選中的節點是目標節點的概率，它是這樣確定的：

P(D)＝P{目的節點在前n個相遇節點中}

定義報酬值：

另外，為了描述過程的結束情況，用?表示過程的停止狀態。根據馬爾可夫性質，轉移概率是不依賴于當前狀態i的，而且只要采取行動X，過程就會繼續下去。

定義轉移概率，在時刻t＋1，恰好在前n＋1個節點中遇到目的節點的概率是：

根據式（2），則未遇到目的節點的概率是：

圖2為路由模型的狀態轉移圖。對于i＝0，1，得出馬氏決策過程的五元組：

{T，S，A(i)，Pt(j|i，α)，Rt(i，α)}

決策時刻T＝{1，2，…，N}，N＜∞

可能的狀態S＝S′∪{?}＝{0，1，?}

Fig.2 State transition diagram圖2　狀態轉移圖

則轉移概率為：

這里就定義好了解決這個節點轉發策略的馬氏決策過程數學模型。下面給出求解過程。用Ut(1)表示從當前時段到過程結束源節點能夠遇到目標節點的最大概率；用Ut(0)表示在剩下時段中源節點能夠遇見目的節點的最大概率，而此時遇見的節點不是目標節點。那么，它們滿足下面的關系：

對于n＝1，2，…，N?1，有：

考慮到Ut＋1(?)＝Ut(?)＝0，Ut≥0，化簡：

從上式分析得出，最優策略具有這樣的結構：t時刻如果在狀態S(1)，有Ut(0)＜n/N，最優行動是停止并且傳遞消息；如果Ut(0)＞n/N，最優行動就是繼續尋找下一節點；如果Ut(0)＝n/N，兩者都是最優行動。在狀態S(0)，繼續下去是最優的選擇。

當節點數目N確定以后，此機會網絡節點轉發策略是先觀察K個候選節點，然后比較并記錄其中最好的節點Lv(a)，在放棄前K個節點后，選擇第一個優于Lv(a)的節點Lv(b)，其中b＞a。下面給出求解K的過程：

把1到N個節點按照優先級進行排列共有N！種可能。對于某個固定的K，如果目的節點出現在第M個位置(K＜M≤N)，且從K＋1到M?1位置的節點優先級小于前K位置中的最優節點，就必須得滿足前M?1個節點中的最優節點在前K個節點里，這有K/(M?1)的可能。得到計算目的節點被選中的概率公式P(K)：

用x來表示K/N的值，x＝K/N，K＝Nx，確定積分上界N?1，積分下界M＝K＝Nx，假設N充分大，N?1≈N，則上述公式可以改寫成：

為了求出K和P(K)的極值，對上式求導，并令這個導數為0。

因為x＝K/N且K是自然數，所以結果取整得到：

該機會網絡轉發策略的核心思想是記錄源節點遇見的前[N/e]個節點，如果遇見目的節點則直接遞交消息，如果前[N/e]個節點不是目的節點，記錄其中最高優先度節點的Lv(a)值并放棄前[N/e]個節點，之后選擇剩下的N?[N/e]中的任何一個優于Lv(a)的節點傳遞消息，并繼續尋找目的節點D，直到消息傳遞完畢為止。此轉發策略使源節點對目的節點的跳數最小值為1。

對于任意節點i的轉發策略代碼如下所示：

1. Begin

2. if (contact Node i)

3. //源節點相遇節點i

4. if (i=Message’s target)

5. transfer Message to Node i;

6. //如果節點i是目標節點，則轉發消息

7.else if ([N/e].length

8.add i to [N/e];

9. //判斷是否是前[N/e]的節點

10. else if (i>[N/e].Max)

11. transfer Message to Node i;

12. //選擇剩下的N?[N/e]中的任何一個優于Lv(a)的節點傳遞消息

13.else

14.return;

15.End if

16.End if

17. End if

18.End if

19.End

整個算法理論上源節點對目的節點的投遞率最大值為：

源節點相對于其他等級節點的投遞率按照遞推公式計算：

4　實驗評估

4.1數值實驗

算法數值實驗采用Matlab編程計算，設節點數N＝100，按節點等級區分，0號節點是源節點，99號節點是目的節點，根據遞推公式（12），可以計算出本文轉發策略下對應不同等級節點的投遞率，如圖3所示。

Fig.3 Statistical result of numerical experiment圖3　數值實驗統計結果

本文的轉發策略是K1＝[N/e]，取整后等于[0.37N]，即略過前37個節點后轉發給第一個比之前遇到所有節點等級都高的節點。

4.2仿真實驗

本文采用ONE仿真平臺[27]評估轉發策略。利用ONE仿真平臺可以有效地模擬真實情況下節點的活動與相遇情況。

仿真實驗中進行了隨機運動模式實驗，模擬場景大小為1 000 m×1 000 m，節點個數為100，平均移動速度為10 m/s，接口帶寬為250 Kb/s，接口范圍為10 m，仿真次數200次取平均值，消息大小為50 KB。采用3種不同的隨機移動模型：隨機路點RandomWaypoint，隨機方向RandomDirection，隨機漫步RandomWalk。

4.2.1投遞率

通過前面的數學計算，了解到在一個隨機場景中，源節點跳過先前遇到的37個節點會使對目的節點的投遞率最大化。第一組實驗是為了對比本文轉發策略其他閥值的效果，即可以選取跳過的節點數。這里取了另一組經驗參數K2＝[0.20N]，即跳過前20個節點。選取這個參數的依據來源于鄧巴定律[28]，文獻中提到無論你曾經認識多少人，或者通過一種社會性網絡服務與多少人建立了弱鏈接，那些強鏈接仍然在此次此刻符合“二八”法則[29]，即在機會網絡中隨機遇到的20%的節點里面包含著目標節點的可能性是80%。第三組參數采取隨機經驗參數K3＝[0.10N]。實驗仿真的數據來源于3種隨機運動模式下節點投遞率的平均值。

如圖4所示，通過統計節點投遞率，對比另外兩組經驗參數，本文轉發策略在提高對目的節點的投遞率方面有著非常明顯的效果，但是對其他相似的非目的節點并無明顯優勢。同時也驗證了理論計算出來的消息轉發概率規律。

Fig.4 Delivery rates parameter experiment results analysis of forwarding strategy圖4　轉發策略參數實驗投遞率結果分析

如圖5所示，第二組投遞率實驗在第一組內部參數的基礎上對比了3種隨機運動模式。由實驗統計發現，自由漫步這種隨機運動模式取得的投遞率最高，說明節點運動模式越隨機，則越符合本文提到的馬爾可夫決策過程的相關規律。圖中橫坐標“轉發策略跳過的節點數目”為本文所提策略的閥值。通過對比不同閥值觀察投遞率的變化。

Fig.5 Delivery rates of motion models on ONE simulation platform圖5　ONE仿真平臺上移動模型投遞率實驗

第三組投遞率實驗在隨機運動模式的情況下，引入另外兩種單副本路由策略作為比較。依據文獻[11]提到的路由策略算法，仿真了Seek and Focus（SF）和Simbet在本文實驗設計中的實際投遞率。從圖6和圖7中發現，SF路由在不同轉發概率和不同閥值的情況下，投遞率圍繞著一個數學期望呈現隨機分布的特性。在第三組實驗中SF路由取其投遞率均值作為對比。Simbet的仿真實驗用了節點相似度容差作為觀察參數，節點相似度容差越小則節點越相似，容差越大則說明節點相似度差異就越大。在仿真實驗中其路由投遞率隨著不同節點相似度容差的遞增而增加，在本組實驗中，取其最優值進行實驗對比。通過實驗觀察，本文策略在3種節點隨機移動模型中投遞率差異較小。

Fig.6 Simert delivery rates analysis圖6　Simbert投遞率分析

Fig.7 SF delivery rates analysis圖7　SF投遞率分析

圖8統計了本文路由策略和另外3組路由策略Direct Delivery（DD）、Seek and Focus（SF）、Simbet在不同隨機運動模型下的投遞率，通過200次實驗取其平均值，可以發現在隨機漫步的運動模型下，本文策略的投遞率略高于DD路由、SF路由和Simbet路由，說明越隨機的行為模式越符合馬爾可夫決策過程的規律。同時發現一個現象，就是在隨機路點模型下，Simbet路由的投遞率上升。這是因為隨機路點運動模型下，節點的運動規律趨于中心化，這符合節點運動的社會屬性的規律，從而基于節點相似度的單副本路由Simbet的優勢就體現出來。

Fig.8 Delivery rates of different routing strategies on ONE simulation platform圖8　ONE仿真平臺上不同路由策略投遞率實驗

4.2.2開銷率

第一組實驗對比了本文轉發策略3個參數在3種隨機運動模型下的開銷率：成功遞交的數據包被中繼的次數與被成功遞交的數據包個數之差再除以被成功遞交的數據包的個數。從表1中可以發現，自由漫步運動模式有著稍好的表現。說明節點運動模式越隨機，則越符合本文提到的馬爾可夫決策過程的相關規律，具體表現為網絡中的數據包成功遞交的次數越多，而被中繼的次數越少，網絡負載越低，效率越優秀。

第二組開銷率實驗統計了本文路由策略和另外3組路由策略Seek and Focus（在相同實驗場景設計中，取不同的轉發概率P和不同閥值S后的開銷率平均值）、Simbet（在相同實驗場景設計中，取不同的節點相似度容差后的開銷率平均值）以及有著最優開銷率的Direct Delivery在3種隨機運動模型下的開銷率。通過200次實驗取平均值，從表2中可以發現，在3種隨機運動模型下各種路由的開銷率差異不大，但是自由漫步模式總體最優。本文轉發策略和Direct Delivery因為每次節點傳遞消息中介次數只有一次，所以開銷率明顯低于Seek and Focus和Simbet路由，同時本文轉發策略因為規避一定數量的相遇節點，所以比盲目尋找目的節點的Direct Delivery路由的實際投遞率高。開銷率與遞交成功的數據包有直接關系，這也造成了本文路由的開銷率低于DD路由的實際結果。另外Simbet路由在隨機路點移動模型中發揮了其社會屬性的優勢，節省了開銷率。

4.2.3平均遲延

除此之外，需要研究實際情況中節點的延時情況，如圖9和圖10所示。

Table 1 Overhead rates of different motion models on ONE simulation platform表1　ONE仿真平臺上不同運動模型開銷率實驗

Table 2 Overhead rates of different routing strategies on ONE simulation platform表2　ONE仿真平臺上不同路由策略開銷率實驗

可以看出，本文轉發策略在延時方面是有不足的，但是處于可以接受的范圍內。圖10中的延時是在略過37個節點的情況下與其他算法比較的，此時差于Simbet算法，但是依然遠遠優于Seek and Focus算法和Direct Delivery算法。從圖9中可以看出，經驗參數0.20N的延時要比0.37N的延時短，而0.10N有著最小的延時，也就是說略過前37個節點這個轉發策略需要消耗一定的時間。因此本文的高投遞概率是以犧牲一定延時為代價的，略過的節點越多，延時更大，但是遞交率越高。

Fig.9 Statistical average delay of different motion models on ONE simulation platform圖9　ONE仿真平臺上不同運動模型平均延時統計

Fig.10 Statistical average delay of different routing strategies on ONE simulation platform圖10　ONE仿真平臺上不同路由策略平均延時統計

從圖5、圖9和表2中還可以發現，平均延時隨略過節點數目增加而增加的趨勢，略小于投遞率隨略過節點數目增加而增加的趨勢，而遠遠小于網絡負載隨略過節點數目增加而減少的趨勢。前兩種變化呈現正比例的關系，而后者呈現指數關系。這是因為馬氏決策過程在略過一部分節點后投遞次數更少，網絡負載更低，且遞交率更為準確。這也驗證了本文的理論，在略過一部分節點后，基于馬氏決策過程的路由選擇策略使得網絡綜合效率更高。因此，在對投遞率要求較高的場景中，通過馬氏決策過程適當略過一部分節點則對網絡性能有很大的提升，根據實驗結果認為37%為較好的選擇。而在一般場景中，可以適當選取較少的略過節點的數量參數，在遞交率和延時之間平衡折中，保證較高遞交率和較低網絡負載的同時也有著較短的消息延時，提高網絡的整體通信效率，根據實驗結果認為20%為較折中的選擇。

為了更好地研究本文策略，設橫軸為延時區間，縱軸為對目的節點投遞次數，對比3種節點運動模式，如圖11所示。

Fig.11 Statistical average delay on ONE simulation platform圖11　ONE仿真平臺上平均延時統計

可以發現RandomWalk在很快的時間內完成了絕大部分針對目的節點投遞次數，從節省時間的情況上看是最為理想的，間接地驗證了馬爾可夫決策過程規律時間方面與空間方面的相似性。

5　結束語

機會網絡是一種不需要源節點和目的節點之間存在完整鏈路，利用節點移動帶來的相遇機會實現通信的自組織網絡。

在隨機的機會網絡場景中，平衡3個機會網絡的評價參數是一直研究的方向。本文結合了花粉布朗運動的數學含義與機會網絡節點的隨機運動特性，分析了節點隨機運動的規律，定義了基于馬爾可夫決策過程的一種節點轉發策略，并研究了此策略下機會網絡的參數平衡關系。通過理論模型分析和實驗驗證，本文提出的機會網絡節點轉發策略可以有效控制源節點對目的節點的開銷率，并且保證其對目的節點的較高投遞率，而不足之處是會增加平均延時。可以根據實際情況，向下調整轉發策略參數，以求得更好的網絡性能。

References:

[1] Nguyen H A, Giordano S. Context information prediction for social-based routing in opportunistic networks[J]. Ad Hoc Networks, 2012, 10(8): 1557-1569.

[2] Lin Yaguang, Wang Xiaoming, Zhang Lichen, et al. The impact of node velocity diversity on mobile opportunistic network performance[J]. Journal of Network and Computer Applications, 2015, 55: 47-58.

[3] Casteigts A, Flocchini P, Mans B, et al. Measuring temporal lags in delay-tolerant networks[J]. IEEE Transactions on Computers, 2014, 63(2): 397-410.

[4] Jeong J, Lee K, Yi Y, et al. ExMin: a routing metric for novel opportunity gain in delay tolerant networks[J]. Computer Networks, 2014, 59: 184-196.

[5] Jiao Xianlong, Wang Xiaodong, Zhou Xingming. An efficient routing protocol in wireless ad hoc networks[J]. Journal of Frontiers of Computer Science and Technology, 2008, 2(5): 478-486.

[6] Soares V N G J, Rodrigues J J P C, Farahmand F. GeoSpray: a geographic routing protocol for vehicular delay-tolerant networks[J]. Information Fusion, 2014, 15: 102-113.

[7] Jang I, Choi W, Lim H. An opportunistic forwarding protocol with relay acknowledgment for vehicular ad hoc networks[J]. Wireless Communications and Mobile Computing, 2011, 11 (7): 939-953.

[8] Shin W Y, Chung S Y, Lee Y H. Parallel opportunistic routing in wireless networks[J]. IEEE Transactions on Information Theory, 2013, 59(10): 6290-6300.

[9] Conan V, Leguay J, Friedman T. Fixedpoint opportunistic routing in delay tolerant networks[J]. IEEE Journal on Selected Areas in Communications, 2008, 26(5): 773-782.

[10] Liu Haitao, Zhang Baoxian, Mouftah H, et al. Opportunistic routing for wireless ad hoc and sensor networks: present and future directions[J]. IEEE Communications Magazine, 2009, 47(12): 103-109.

[11] Spyropoulos T, Psounis K, Raghavendra C S. Efficient routing in intermittently connected mobile networks: the single-copy case[J]. IEEE/ACM Transactions on Networking, 2008, 16 (1): 63-76.

[12] Amantea G, Rivano H, Goldman A. A delay-tolerant network routing algorithm based on column generation[C]//Proceedings of the 12th IEEE International Symposium on Network Computing and Applications, Cambridge, USA, Aug 2013. Piscataway, USA: IEEE, 2013: 89-96.

[13] Lu Xiaofeng, Pan Hui, Lio P. High delivery performance opportunistic routing scheme for delay tolerant networks[J]. China Communications, 2012, 9(6): 145-153.

[14] Daraghmi YA, Yi C W, Stojmenovic I. Forwarding methods in data dissemination and routing protocols for vehicular ad hoc networks[J]. IEEE Network, 2013, 27(6): 74-79.

[15] Shin K, Lee D. Fame-based probabilistic routing for delaytolerant networks[J]. IEICE Transactions on Communications, 2010, E93-B(6): 1451-1458.

[16] Shen Guangjun, Yan Litan. An approximation of subfractional Brownian motion[J]. Communications in Statistics: Theory and Methods, 2014, 43(9): 1873-1886.

[17] Bahram A. Convergence of the increment of a wiener process[J]. Acta Mathematica Universitatis Comenianae, 2014, 83(1) : 113-118.

[18] Dombry C, Eyi-Minko F. Stationary max-stable processes with the Markov property[J]. Stochastic Processes and Their Applications, 2014, 124(6): 2266-2279.

[19] Niyato D, Wang Ping. Optimization of the mobile router and traffic sources in vehicular delay-tolerant network[J]. IEEE Transactions on Vehicular Technology, 2009, 58(9): 5095-5104.

[20] Singh M P, Deen A J, Shukla P K. A comprehensive survey of routing strategies for vehicular ad-hoc networks[J]. Wireless Communication, 2013, 5(8): 328-333.

[21] Spyropoulos T, Picu A. Opportunistic routing[M]//Mobile Ad Hoc Networking: the Cutting Edge Directions. 2nd ed. [S.l.]:Wiley-IEEE Press, 2013: 419-452.

[22] Xiao Mingjun, Wu Jie, Liu Cong, et al. TOUR: time-sensitive opportunistic utility-based routing in delay tolerant networks[C]//Proceedings of the 32nd IEEE International Conference on Computer Communications, Turin, Italy,Apr 14-19, 2013. Piscataway, USA: IEEE, 2013: 2085-2091.

[23] Guo Hang, Wang Xingwei, Huang Min, et al. Mobility modelof DTN nodes based on semi-Markov process[J]. Journal of Chinese Computer Systems, 2011, 32(7): 1273-1276.

[24] Rhee I, Shin M, Hong S, et al. On the Levy-walk nature of human mobility[J]. IEEE/ACM Transactions on Networking, 2011, 19(3): 630-643.

[25] Zhang Wenzhu, Sun Fayong, Wang Xuan. Study of the DTN routing algorithm based on the Markov decision[J]. Journal of Xidian University: Natural Science Edition, 2011, 38(2): 18-22.

[26] Zhu Hao, Zhang Yu, Bai Shiyu. Evaluation method for node importance in networks based on Markov chain[J]. Journal of Circuits and Systems, 2013, 18(2): 452-456.

[27] Pan Daru, Sun Jiajia, Liu Xiong, et al.Acampus based mobility model for opportunistic network[C]//Proceedings of the 2nd International Conference on Communications, Signal Processing, and Systems. [S.l.]：Springer International Publishing, 2014: 1039-1046.

[28] Gon?alves B, Perra N, Vespignani A. Modeling users’activity on twitter networks: validation of dunbar’s number[J]. PloS One, 2011, 6(8): e22656.

[29] Zhang Hangqing. Topological analysis of SNS social networks[D]. Shanghai: Donghua University, 2011.

附中文參考文獻：

[5]焦賢龍,王曉東,周興銘.無線自組網中一種高效的路由協議[J].計算機科學與探索, 2008, 2(5): 478-486.

[23]郭航,王興偉,黃敏,等.基于半馬爾可夫過程的DTN節點移動模型[J].小型微型計算機系統, 2011, 32(7): 1273-1276.

[25]張文柱,孫發勇,王炫.基于馬爾科夫決策的容遲網絡路由算法[J].西安電子科技大學學報:自然科學版, 2011, 38 (2): 18-22.

[26]朱浩,張玉,柏詩玉.基于馬氏鏈的網絡節點重要性評價方法[J].電路與系統學報, 2013, 18(2): 452-456.

[29]張瀚青.基于SNS社交網絡的模型及其拓撲分析[D].上海:東華大學, 2011.

ZHANG Yang was born in 1984. He is a Ph.D. candidate at School of Computer Science, Shaanxi Normal University. His research interests include opportunistic network and social network, etc.

張楊（1984—），男，安徽阜陽人，陜西師范大學計算機科學學院博士研究生，主要研究領域為機會網絡，社會網絡等。

WANG Xiaoming was born in 1964. He received the Ph.D. degree from Northwest University in 2005. Now he is a professor and Ph.D. supervisor at School of Computer Science, Shaanxi Normal University, and the senior member of CCF. His research interests include wireless sensor network, mobile ad hoc networks, pervasive computing and social computing, etc. He has published more than 80 papers in international journals and conferences.

王小明（1964—），男，甘肅天水人，2005年于西北大學獲得博士學位，現為陜西師范大學計算機科學學院教授、博士生導師，CCF高級會員，主要研究領域為無線傳感器網絡，移動自組織網絡，普適計算，社會計算等。發表學術論文80余篇，出版專著2部，主編并出版教材1部。

LIN Yaguang was born in 1990. He is an M.S. candidate at School of Computer Science, Shaanxi Normal University. His research interests include opportunistic network and social network, etc.

林亞光（1990—），男，陜西渭南人，陜西師范大學計算機科學學院碩士研究生，主要研究領域為機會網絡，社會網絡等。

ZHANG Dan was born in 1991. She is an M.S. candidate at School of Computer Science, Shaanxi Normal University. Her research interests include opportunistic network and social network, etc.

張丹（1991—），女，甘肅酒泉人，陜西師范大學計算機科學學院碩士研究生，主要研究領域為機會網絡，社會網絡等。

Message Forwarding Strategy Based on Markov Decision Process in Opportunistic Networks*

ZHANG Yang1,2, WANG Xiaoming1,2+, LIN Yaguang1,2, ZHANG Dan1,2
1. Key Laboratory of Modern Teaching Technology, Ministry of Education, Xi’an 710119, China
2. School of Computer Science, Shaanxi Normal University, Xi’an 710119, China
+ Corresponding author: E-mail: wangxm@snnu.edu.cn

ZHANG Yang, WANG Xiaoming, LIN Yaguang, et al. Message forwarding strategy based on Markov decision process in opportunistic networks. Journal of Frontiers of Computer Science and Technology, 2016, 10(1)：82-92.

Abstract:To improve the delivery rates, control overhead rates and reduce the average delay is the ongoing research in the random opportunistic networks moving scenes. Due to the opportunistic network structure is sparse and the network topology is variable, the efficiency of single copy routing forwarding strategy is very low. This paper defines a forwarding strategy based on Markov decision by combining the similarity between Brownian motion of pollen and nodes random movement in opportunity networks and analyzing the law of the random motion of nodes. In the case of an appropriately growing average delay, the strategy can control the overhead rates and advance the delivery rates. Finally, this paper verifies the correctness of the theoretical models by simulation experiments.

Key words:opportunistic network; Markov decision; delivery rate

文獻標志碼：A

中圖分類號：TP393

doi:10.3778/j.issn.1673-9418.1504001