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

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

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

* The National Natural Science Foundation of China under Grant No. 61373083 (國(guó)家自然科學(xué)基金); the Fundamental Research Funds for the Central Universities of China under Grant No. GK201401002 (中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金); the Program of Science and Technology Innovation Team of Shaanxi Province under Grant No. 2014KTC-18 (陜西省重點(diǎn)科技創(chuàng)新團(tuán)隊(duì)項(xià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

?

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

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

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

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

* The National Natural Science Foundation of China under Grant No. 61373083 (國(guó)家自然科學(xué)基金); the Fundamental Research Funds for the Central Universities of China under Grant No. GK201401002 (中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金); the Program of Science and Technology Innovation Team of Shaanxi Province under Grant No. 2014KTC-18 (陜西省重點(diǎn)科技創(chuàng)新團(tuán)隊(duì)項(xià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

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

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

1　引言

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

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

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

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

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

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

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

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

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

2　相關(guān)工作

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1場(chǎng)景描述

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

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

3.2轉(zhuǎn)發(fā)策略

本文不考慮計(jì)算節(jié)點(diǎn)的優(yōu)先級(jí)，直接定義節(jié)點(diǎn)的優(yōu)先級(jí)排序，把源節(jié)點(diǎn)S定義為L(zhǎng)v0，把目的節(jié)點(diǎn)D定義為L(zhǎng)v(N?1)：

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

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

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

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

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

定義報(bào)酬值：

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

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

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

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

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

決策時(shí)刻T＝{1，2，…，N}，N＜∞

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

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

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

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

對(duì)于n＝1，2，…，N?1，有：

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

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

當(dāng)節(jié)點(diǎn)數(shù)目N確定以后，此機(jī)會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)轉(zhuǎn)發(fā)策略是先觀察K個(gè)候選節(jié)點(diǎn)，然后比較并記錄其中最好的節(jié)點(diǎn)Lv(a)，在放棄前K個(gè)節(jié)點(diǎn)后，選擇第一個(gè)優(yōu)于Lv(a)的節(jié)點(diǎn)Lv(b)，其中b＞a。下面給出求解K的過(guò)程：

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

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

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

因?yàn)閤＝K/N且K是自然數(shù)，所以結(jié)果取整得到：

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

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

1. Begin

2. if (contact Node i)

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

4. if (i=Message’s target)

5. transfer Message to Node i;

6. //如果節(jié)點(diǎn)i是目標(biāo)節(jié)點(diǎn)，則轉(zhuǎn)發(fā)消息

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

8.add i to [N/e];

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

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

11. transfer Message to Node i;

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

13.else

14.return;

15.End if

16.End if

17. End if

18.End if

19.End

整個(gè)算法理論上源節(jié)點(diǎn)對(duì)目的節(jié)點(diǎn)的投遞率最大值為：

源節(jié)點(diǎn)相對(duì)于其他等級(jí)節(jié)點(diǎn)的投遞率按照遞推公式計(jì)算：

4　實(shí)驗(yàn)評(píng)估

4.1數(shù)值實(shí)驗(yàn)

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

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

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

4.2仿真實(shí)驗(yàn)

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

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

4.2.1投遞率

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

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

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

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

Fig.5 Delivery rates of motion models on ONE simulation platform圖5　ONE仿真平臺(tái)上移動(dòng)模型投遞率實(shí)驗(yàn)

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

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

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

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

Fig.8 Delivery rates of different routing strategies on ONE simulation platform圖8　ONE仿真平臺(tái)上不同路由策略投遞率實(shí)驗(yàn)

4.2.2開銷率

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

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

4.2.3平均遲延

除此之外，需要研究實(shí)際情況中節(jié)點(diǎn)的延時(shí)情況，如圖9和圖10所示。

Table 1 Overhead rates of different motion models on ONE simulation platform表1　ONE仿真平臺(tái)上不同運(yùn)動(dòng)模型開銷率實(shí)驗(yàn)

Table 2 Overhead rates of different routing strategies on ONE simulation platform表2　ONE仿真平臺(tái)上不同路由策略開銷率實(shí)驗(yàn)

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

Fig.9 Statistical average delay of different motion models on ONE simulation platform圖9　ONE仿真平臺(tái)上不同運(yùn)動(dòng)模型平均延時(shí)統(tǒng)計(jì)

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

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

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

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

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

5　結(jié)束語(yǔ)

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

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

附中文參考文獻(xiàn)：

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

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

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

[26]朱浩,張玉,柏詩(shī)玉.基于馬氏鏈的網(wǎng)絡(luò)節(jié)點(diǎn)重要性評(píng)價(jià)方法[J].電路與系統(tǒng)學(xué)報(bào), 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—），男，安徽阜陽(yáng)人，陜西師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院博士研究生，主要研究領(lǐng)域?yàn)闄C(jī)會(huì)網(wǎng)絡(luò)，社會(huì)網(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é)計(jì)算機(jī)科學(xué)學(xué)院教授、博士生導(dǎo)師，CCF高級(jí)會(huì)員，主要研究領(lǐng)域?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)，移動(dòng)自組織網(wǎng)絡(luò)，普適計(jì)算，社會(huì)計(jì)算等。發(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é)計(jì)算機(jī)科學(xué)學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)闄C(jī)會(huì)網(wǎng)絡(luò)，社會(huì)網(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é)計(jì)算機(jī)科學(xué)學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)闄C(jī)會(huì)網(wǎng)絡(luò)，社會(huì)網(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

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

中圖分類號(hào)：TP393

doi:10.3778/j.issn.1673-9418.1504001