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

1.現(xiàn)代教學(xué)技術(shù)教育部重點實驗室，西安710119

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

* The National Natural Science Foundation of China under Grant No. 61373083 (國家自然科學(xué)基金); the Fundamental Research Funds for the Central Universities of China under Grant No. GK201401002 (中央高校基本科研業(yè)務(wù)費專項資金); 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網(wǎng)絡(luò)優(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

?

基于馬爾可夫決策過程的機會網(wǎng)絡(luò)轉(zhuǎn)發(fā)策略*

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

1.現(xiàn)代教學(xué)技術(shù)教育部重點實驗室，西安710119

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

* The National Natural Science Foundation of China under Grant No. 61373083 (國家自然科學(xué)基金); the Fundamental Research Funds for the Central Universities of China under Grant No. GK201401002 (中央高?；究蒲袠I(yè)務(wù)費專項資金); 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網(wǎng)絡(luò)優(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

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

關(guān)鍵詞：機會網(wǎng)絡(luò)；馬爾可夫決策；投遞率

1　引言

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

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

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

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

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

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

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

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

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

2　相關(guān)工作

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

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

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

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

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

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

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

{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)后，有兩個結(jié)果：（1）決策獲得報酬R(i，α)；（2）下一個決策時刻系統(tǒng)所處的狀態(tài)由概率分布P(?|i，α)決定。R(i，α)是定義在i∈S和α∈A(i)上的實值函數(shù)。當(dāng)R(i，α)為正值時，表示收入；當(dāng)其為負(fù)值時，表示費用。從模型的角度來看，報酬R(i，α)是即時的。通常情況下報酬還依賴下一個決策時刻的狀態(tài)j，即R(i，α，j)，那么行動α的期望值報酬為：

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

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

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

3　機會網(wǎng)絡(luò)節(jié)點轉(zhuǎn)發(fā)策略

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

3.1場景描述

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

Fig.1 Stochastic model of opportunistic network圖1　機會網(wǎng)絡(luò)隨機場景

3.2轉(zhuǎn)發(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é)點然后轉(zhuǎn)發(fā)消息，重復(fù)路由策略直到目的節(jié)點收到消息過程結(jié)束。節(jié)點按照隨機方式移動，定義基于馬爾可夫決策過程的節(jié)點轉(zhuǎn)發(fā)策略模型。

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

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

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

定義報酬值：

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

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

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

圖2為路由模型的狀態(tài)轉(zhuǎn)移圖。對于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)轉(zhuǎn)移圖

則轉(zhuǎn)移概率為：

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

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

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

從上式分析得出，最優(yōu)策略具有這樣的結(jié)構(gò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)的選擇。

當(dāng)節(jié)點數(shù)目N確定以后，此機會網(wǎng)絡(luò)節(jié)點轉(zhuǎn)發(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é)點出現(xiàn)在第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，假設(shè)N充分大，N?1≈N，則上述公式可以改寫成：

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

因為x＝K/N且K是自然數(shù)，所以結(jié)果取整得到：

該機會網(wǎng)絡(luò)轉(zhuǎn)發(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，直到消息傳遞完畢為止。此轉(zhuǎn)發(fā)策略使源節(jié)點對目的節(jié)點的跳數(shù)最小值為1。

對于任意節(jié)點i的轉(zhuǎn)發(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是目標(biāo)節(jié)點，則轉(zhuǎn)發(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數(shù)值實驗

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

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

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

4.2仿真實驗

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

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

4.2.1投遞率

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

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

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

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

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

第三組投遞率實驗在隨機運動模式的情況下，引入另外兩種單副本路由策略作為比較。依據(jù)文獻[11]提到的路由策略算法，仿真了Seek and Focus（SF）和Simbet在本文實驗設(shè)計中的實際投遞率。從圖6和圖7中發(fā)現(xiàn)，SF路由在不同轉(zhuǎn)發(fā)概率和不同閥值的情況下，投遞率圍繞著一個數(shù)學(xué)期望呈現(xiàn)隨機分布的特性。在第三組實驗中SF路由取其投遞率均值作為對比。Simbet的仿真實驗用了節(jié)點相似度容差作為觀察參數(shù)，節(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ā)現(xiàn)在隨機漫步的運動模型下，本文策略的投遞率略高于DD路由、SF路由和Simbet路由，說明越隨機的行為模式越符合馬爾可夫決策過程的規(guī)律。同時發(fā)現(xiàn)一個現(xiàn)象，就是在隨機路點模型下，Simbet路由的投遞率上升。這是因為隨機路點運動模型下，節(jié)點的運動規(guī)律趨于中心化，這符合節(jié)點運動的社會屬性的規(guī)律，從而基于節(jié)點相似度的單副本路由Simbet的優(yōu)勢就體現(xiàn)出來。

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

4.2.2開銷率

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

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

可以看出，本文轉(zhuǎn)發(fā)策略在延時方面是有不足的，但是處于可以接受的范圍內(nèi)。圖10中的延時是在略過37個節(jié)點的情況下與其他算法比較的，此時差于Simbet算法，但是依然遠遠優(yōu)于Seek and Focus算法和Direct Delivery算法。從圖9中可以看出，經(jīng)驗參數(shù)0.20N的延時要比0.37N的延時短，而0.10N有著最小的延時，也就是說略過前37個節(jié)點這個轉(zhuǎn)發(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ā)現(xiàn)，平均延時隨略過節(jié)點數(shù)目增加而增加的趨勢，略小于投遞率隨略過節(jié)點數(shù)目增加而增加的趨勢，而遠遠小于網(wǎng)絡(luò)負(fù)載隨略過節(jié)點數(shù)目增加而減少的趨勢。前兩種變化呈現(xiàn)正比例的關(guān)系，而后者呈現(xiàn)指數(shù)關(guān)系。這是因為馬氏決策過程在略過一部分節(jié)點后投遞次數(shù)更少，網(wǎng)絡(luò)負(fù)載更低，且遞交率更為準(zhǔn)確。這也驗證了本文的理論，在略過一部分節(jié)點后，基于馬氏決策過程的路由選擇策略使得網(wǎng)絡(luò)綜合效率更高。因此，在對投遞率要求較高的場景中，通過馬氏決策過程適當(dāng)略過一部分節(jié)點則對網(wǎng)絡(luò)性能有很大的提升，根據(jù)實驗結(jié)果認(rèn)為37%為較好的選擇。而在一般場景中，可以適當(dāng)選取較少的略過節(jié)點的數(shù)量參數(shù)，在遞交率和延時之間平衡折中，保證較高遞交率和較低網(wǎng)絡(luò)負(fù)載的同時也有著較短的消息延時，提高網(wǎng)絡(luò)的整體通信效率，根據(jù)實驗結(jié)果認(rèn)為20%為較折中的選擇。

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

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

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

5　結(jié)束語

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

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

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

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

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

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

[29]張瀚青.基于SNS社交網(wǎng)絡(luò)的模型及其拓?fù)浞治鯷D].上海:東華大學(xué), 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—），男，安徽阜陽人，陜西師范大學(xué)計算機科學(xué)學(xué)院博士研究生，主要研究領(lǐng)域為機會網(wǎng)絡(luò)，社會網(wǎng)絡(luò)等。

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年于西北大學(xué)獲得博士學(xué)位，現(xiàn)為陜西師范大學(xué)計算機科學(xué)學(xué)院教授、博士生導(dǎo)師，CCF高級會員，主要研究領(lǐng)域為無線傳感器網(wǎng)絡(luò)，移動自組織網(wǎng)絡(luò)，普適計算，社會計算等。發(fā)表學(xué)術(shù)論文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—），男，陜西渭南人，陜西師范大學(xué)計算機科學(xué)學(xué)院碩士研究生，主要研究領(lǐng)域為機會網(wǎng)絡(luò)，社會網(wǎng)絡(luò)等。

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—），女，甘肅酒泉人，陜西師范大學(xué)計算機科學(xué)學(xué)院碩士研究生，主要研究領(lǐng)域為機會網(wǎng)絡(luò)，社會網(wǎng)絡(luò)等。

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

文獻標(biāo)志碼：A

中圖分類號：TP393

doi:10.3778/j.issn.1673-9418.1504001