基于马尔可夫会议时间跨度预测模型的DTN路由算法资源-CSDN文库

Routing

Model

191 浏览量 2021-03-03 03:53:41 上传评论 1 收藏 1.62MB PDF 举报

资源推荐

资源详情

资源评论

Hindawi Publishing Corporation

International Journal of Distributed Sensor Networks

Volume , Article ID ,  pages

http://dx.doi.org/.//

Research Article

The DTN Routing Algorithm Based on Markov Meeting Time

Span Prediction Model

En Wang,

Yongjian Yang,

Bing Jia,

and Tingting Guo

Department of Computer Science and Technology, Jilin University, Changchun 130012, China

Department of Soware Engineering, Jilin University, Changchun 130012, China

Correspondence should be addressed to Yongjian Yang; yyj@jlu.edu.cn

Received  July ; Accepted  August 

Academic Editor: Yuan He

permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Putting forward an ecient routing algorithm in DTN (delay tolerant network) has become a focus of attention due to the existing

phenomena that the connections between nodes in the network change dramatically over time and the communications suer from

frequent disruptions. In this paper, the meeting time span between nodes is predicted using the Markov model, and the relay node

holding the shortest meeting time span with the destination node is determined as the most ecient node. In the two phases, spray

phase and wait phase, the message is routed according to the utility value. us, the routing algorithm based on Markov meeting

time span prediction model is provided. Simulation results suggest that this algorithm eciently improves the delivery rate and

reduces the average delay.

1. Introduction

DTN (delay tolerant network) []whichisputforwardby

Fall at the international committee SIGCOMM in  []

is a kind of challenged network characterized by changing

topology and lacking of stable links between terminates. End-

to-end transmission latency may be arbitrarily long due to

occasionally connected links [, ].

Examples of DTN are those operating in mobile or

extreme scenarios such as interplanetary networks [, ],

military networks [], rural area networks [], wildlife track-

ing sensor networks [, ], and pocket switched networks

(PSNs) [, ]. Developing ecient routing protocols in this

kind of network where topology changes dramatically has

been a hot issue.

Generally, present routing protocols in DTN can be

classied into two categories: copy-based routing []and

eciency-based routing []. Epidemic []isthebasiccopy-

based routing protocol that exchanges messages in a simple

way which seems like epidemic. Considering that the number

of copies during its execution is out of control, this method

will cost a lot of network resources: rubbish copies increase

with the growth of time and nally lead to congestion.

To control the number of message copies, there comes a

classical routing protocol based on quota: spray and wait [,

]. Several improvements have been made on it aerwards.

Multiperiod spraying [] extends the single spray phase into

several spray phases, expecting ecient usage of network

resources by infecting more nodes. Spray and focus []

improves the wait phase. e message is routed through

thenodeofthehighestutility.Sprayandforward[]

also improves the wait phase and calculates the meeting

probability using the Markov location model. However, all

the above methods only focus the improvements on one of

the two phases, and spray and forward only considers the

meeting possibility []ataspecicplacewithoutconsidering

the possible meeting on the way. To make up the above

drawbacks, we propose a new DTN routing algorithm based

on the Markov [] meeting time span prediction model: pre-

dict and forward (PAF). e meeting time span is predicted

using the Markov model, and the message is forwarded to

the node of the highest utility. Experiments show that this

 International Journal of Distributed Sensor Networks

method achieves higher delivery rate and lower average delay

compared with epidemic or spray and wait routing protocols.

2. The DTN Routing Algorithm Based on

Markov Meeting Time Span Prediction

Model (PAF)

e main idea of PAF is as follows. Each node stores locally

a multidimensional array which records the meeting time

spans between the node and every other node. en the

general range of the next meeting time span is predicted from

theprevioustimespanusingMarkovmodel,andthehighest

utility value is endowed to the node holding the shortest

meeting time span with the destination node. During both

spray phase and wait phase, the message is forwarded to the

node of the highest utility value.

2.1. e Meeting Time Span Prediction Model Based on

Markov. In some DTNs where interested nodes exist, the

meeting between nodes is not random. ere are some

regularities in the meeting time span. In our work, the

previous meeting time spans are used to predict the general

range of the next meeting time span by applying the Markov

model and search for the ecient node which may be the

earliest one to meet the destination node.

Set the meeting time span as a random variable .

e sequence 

𝑖

forms a time-dispersed and state-dispersed

Markov chain. For every two nodes in the network, record the

meeting time span sequence 

𝑖

,andmap

𝑖

into one of the 

states according to the following rules. When 0<

𝑖

≤100,

it is mapped to state . When 100<

𝑖

≤200,itismapped

to state . When 200<

𝑖

≤500,itismappedtostate

. When 500<

𝑖

≤1000,itismappedtostate.When

1000<

𝑖

, it is mapped to state . So the meeting time spans

of every two nodes can be described by a state sequence 

𝑖

which is consisted of states –. According to the property of

theMarkovchain,



𝑛

=

𝑛

|

𝑛−1

=

𝑛−1

,

𝑛−2

=

𝑛−2

⋅⋅⋅

=



=

𝑛

=

𝑛

|

𝑛−1

=

𝑛−1

,

()

where 

𝑖

denotes the value of every meeting time span and



𝑖

denotes the state from  to . 

𝑖

is collected by every node

and stored as 

𝑖

locally. When source node meets a random

node 

𝑖

, the meeting time span sequences of these two nodes

are updated, and then gets the history meeting time span

sequence between 

𝑖

and the destination node stored at .

Astate-transfermatrixis created based on the previous

sequence. Multiply the last state of the previous state sequence

by , and then the next meeting time span is predicted. e

state-transfer matrix is dened by

=

12345







, ()

where 

𝑖𝑗

in transfer matrix denotes the transfer probability

from state to state and



𝑖=1



𝑘𝑖

(

=1,2,3,4,5

)

. ()

For example, assuming that a sequence of the meeting

time spans between node and the destination node is , ,

, , , , , , , , , the state-transfer matrix is calculated as

follows:

=

12345



00100

1/301/31/3 0

01000

1/20 0 0 1/2

00010



. ()

Assuming that the current state is , denotes the state to

which the meeting time span is mapped and corresponds to

row of matrix .Searchforthecolumnwiththehighest

probability in row in the state-transfer matrix, and this

column number is the next state we predict. Take matrix ()

for example. Supposing that the current state is , the highest

probabilityinrowis,anditislocatedatcolumn.Soitis

predictedthatthenextstateis.

BasedonthepropertyoftheMarkovmodel,wecan

calculate the state 

𝑖

to which the next meeting time span

between node 

𝑖

and the destination node should be mapped.

e smaller 

𝑖

is, the earlier the node will meet the destination

node. However, there may be more than one node obtaining

the smallest state. So it is necessary to determine which node

the message will be forwarded to. To solve this problem,

we adopt a two-step method, that is, taking the predicted

state as an input and predicting again using the same state-

transfer matrix. If there are still two or more nodes obtaining

the smallest state, consider the last time the nodes meet

the destination node, and choose the node with the earliest

meeting time as the relay node. e sequence diagram

describing this method is shown in Figure .

2.2. PAF Routing Algorithm. ere exist some obvious dis-

advantages in the spray phase and wait phase of the classical

spray and wait protocol. In spray phase, choosing a node

randomly to spray may cause a problem: many messages will

be sent to nodes with low eciency. In the wait phase, waiting

for the destination node negatively may miss the nodes which

have higher meeting probabilities with the destination node.

PAF algorithm applies the Markov meeting time span

prediction model in both the spray phase and wait phase.

During the spray phase, this method tries to nd the nodes,

which may be the earliest one to meet the destination

node within the communication range and performs binary

spraying. Every node adopts the same spraying policy. When

only one copy of the message is le, the node enters into

the wait phase. During the wait phase, this method still tries

to nd the node which may be the earliest one to meet the

destination node instead of waiting negatively, as shown in

Figure . us, we provide the PAF routing method on the

basis of the Markov meeting span prediction model.

剩余7页未读，继续阅读

评论收藏

内容反馈

weixin_38746166

粉丝: 8
资源: 959

基于马尔可夫会议时间跨度预测模型的DTN路由算法

论文研究-基于DTN历史队列预测的单播路由算法.pdf

基于DTN历史队列预测的单播路由算法

基于神经网络与马尔可夫组合模型的视频流行度预测算法.docx

基于加权马尔可夫链修正的ARIMA 预测模型的研究.pdf

基于马尔可夫模型的手势识别算法

基于隐马尔可夫模型的热路径预测算法研究 (2010年)

网络游戏-基于节点位置预测的DTN网络异步路由算法.zip

论文研究-外商直接投资趋势研究——基于灰色马尔可夫预测模型与时间序列模型的对比.pdf

基于马尔可夫链的轨迹预测.pdf

基于隐马尔可夫模型回归HMMR模型的时间序列分割处理matlab仿真+代码仿真操作视频

粒子群优化算法优化灰色预测模型GM(1,1)+matlab源代码

论文研究-基于有序样品聚类的集对权马尔可夫链年降水量预测模型.pdf

基于马尔可夫链的彩票分析

论文研究 - 基于灰色马尔可夫预测模型的矿井瓦斯涌出量预测

基于粒子群算法的自回归加权马尔可夫链的负荷预测.pdf

Python基于SEIR传染病模型和MCMC马尔可夫链蒙特卡洛算法的疫苗接种场景模拟仿真源码

基于传统方法的单目深度估计-基于马尔可夫随机场的深度估计方法

模型算法模型课件讲义含代码预测方法马尔可夫预测

灰色最小二乘马尔可夫链预测算法

最新资源