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

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 (中央高校基本科研業(yè)務費專項資金); the Program of Science and Technology Innovation Team of Shaanxi Province under Grant No. 2014KTC-18 (陜西省重點科技創(chuàng)新團隊項目).

Received 2015-04,Accepted 2015-08.

CNKI網絡優(yōu)先出版：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

?

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

張楊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 (中央高校基本科研業(yè)務費專項資金); the Program of Science and Technology Innovation Team of Shaanxi Province under Grant No. 2014KTC-18 (陜西省重點科技創(chuàng)新團隊項目).

Received 2015-04,Accepted 2015-08.

CNKI網絡優(yōu)先出版：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

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

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

1　引言

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

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

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

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

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

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

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

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

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

2　相關工作

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

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

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

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

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

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

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

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

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

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

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

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

3　機會網絡節(jié)點轉發(fā)策略

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

3.1場景描述

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

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

3.2轉發(fā)策略

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

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

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

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

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

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

定義報酬值：

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

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

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

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

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

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

可能的狀態(tài)S＝S′∪{?}＝{0，1，?}

Fig.2 State transition diagram圖2　狀態(tài)轉移圖

則轉移概率為：

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

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

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

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

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

把1到N個節(jié)點按照優(yōu)先級進行排列共有N！種可能。對于某個固定的K，如果目的節(jié)點出現在第M個位置(K＜M≤N)，且從K＋1到M?1位置的節(jié)點優(yōu)先級小于前K位置中的最優(yōu)節(jié)點，就必須得滿足前M?1個節(jié)點中的最優(yōu)節(jié)點在前K個節(jié)點里，這有K/(M?1)的可能。得到計算目的節(jié)點被選中的概率公式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是自然數，所以結果取整得到：

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

對于任意節(jié)點i的轉發(fā)策略代碼如下所示：

1. Begin

2. if (contact Node i)

3. //源節(jié)點相遇節(jié)點i

4. if (i=Message’s target)

5. transfer Message to Node i;

6. //如果節(jié)點i是目標節(jié)點，則轉發(fā)消息

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

8.add i to [N/e];

9. //判斷是否是前[N/e]的節(jié)點

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

11. transfer Message to Node i;

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

13.else

14.return;

15.End if

16.End if

17. End if

18.End if

19.End

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

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

4　實驗評估

4.1數值實驗

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

Fig.3 Statistical result of numerical experiment圖3　數值實驗統(tǒng)計結果

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

4.2仿真實驗

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

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

4.2.1投遞率

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

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

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

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

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

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

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

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

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

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

4.2.2開銷率

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

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

4.2.3平均遲延

除此之外，需要研究實際情況中節(jié)點的延時情況，如圖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仿真平臺上不同路由策略開銷率實驗

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

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

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

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

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

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

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

5　結束語

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

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

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

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

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

[26]朱浩,張玉,柏詩玉.基于馬氏鏈的網絡節(jié)點重要性評價方法[J].電路與系統(tǒng)學報, 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高級會員，主要研究領域為無線傳感器網絡，移動自組織網絡，普適計算，社會計算等。發(fā)表學術論文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