随机过程在机会网络中的应用讲解

随机过程在机会网络中的应用

摘要

机会网络是一种不需要在源节点和目的节点之间存在完整路径，利用节点移动带来

的相遇机会实现网络通信，机会网络利用节点的移动形成的通信机会逐跳传瑜消息，以

“存储一携带一转发”的路由模式实现节点间的逋信，节点的移动特性及规律影响到网

络性能，因此对节点移动规律的研究也变的至关重要，在经典的随机移动模型中节点的

运动方式类似布朗运动，节点间的期望相遇时间服从指数分布。在Epidemic的路由算

法经过two-hop,数据从源节点到目的节点的传输过程为马尔可夫链。因此随机过程被

用于分析节点的移动规律和传输机制。

关键词：移动模型、RLC编码、泊松过程、相遇概率

一、机会网络中的经典移动模型

随机移动模型由于算法简单，节点间随机运动各自独立，移动节点时自由的、不加

限制的，因此该模型常被应用于移动网络节点分析中，目前广泛用于描述MANET节点移

动规律的随机移动模型主要有3个独立同分布移动模型：RWP模型（RandomwayPoint

model随机路点模型）、RWM模型（RandomWalkMobilityModel,随机步行模型）和RDM

模型（RandomDirectionMobilitymodel,随机方向移动模型）。

RWP模型中，网络中节点随机分布在模拟区域中，并且呈现均与分布状态，节点在

区域中的目标位置、运动速度、达到目标位置后停顿时间都是随机选择的，也就是说.

在模拟运动空间Region内，节点随机选择一个目标位置D和一个运动速度V,从起点S

以速度V沿直线运动到目的D。RWM模型的运动方式与布朗运动相似，常常又被称为布

朗运动，在RWM模型中，移动节点从当前位置出发，其运动方向和速度都是随机选择的,

并且速度V和方向0e[0,2司服从均匀分布。

RDM模型中节点的移动方式主要为“聚集一分开一再聚集”这样循环的过程，移动

节点的速度V大小为一个定值，只有运动方向是随机选择，这个方向用一定的角度。表

示，，在［0,2乃］区间服从均匀分布。

BettstetterC等人的研究分别从不同的角度证明了上述3个移动模型的节点期望

相遇时间服从指数分布或其尾部服从严格的指数分布。

二、随机模型下的消息转发

在机会网络中，只有当两个移动节点在彼此的通信范围内时才能进行通信，在一个

简单的随机模型中，一股只有两个输入参数，网络中的节点数量和独立同分布的泊松过

程的强度。下面主要介绍两跳多副本和没有限制跳数的路由方法。

首先介绍一个随机网络模型，这个模型中拥有N+1个相同的节点，源节点向目的节

点发送一个消息，中间的节点可以作为中继节点帮助消息的转发，定义

0<r./l)<r..(2)<……为节点i和j的相遇时间，％(〃):=*5+1)-%(〃)为第n次相

遇的时间间隔。｛%(〃),〃21｝,1«i,/«N+1;iw./是相互独立的强度为4的泊松过程，

相应的随机变量亿是均匀独立的指数分布。

当网络中只有一种消息，且节点不能存储相同的信息，那么信息的传输过程为马儿

可夫链，在两跳多副本的情况下，马尔可夫链的状态为｛1,2,3,……N+1｝。当网络中

有i(l,2,3……)个消息时(包括初始消息)，马尔可夫链的状态为i,当消息到达目的

节点时,马尔可夫链的状态为N+1,状态1,2....N是传输状态N+1是一个吸收状态°

Figurel2跳多副本的马尔可夫链传输图

图1展示了2跳多副本的马尔可夫链的传输图，在两跳的协议下，源节点携带消息,

转发给碰到的下一个节点，如果下一个节点时目的节点则传输完成，如果不是，则由下

一个节点将接受消息并协助转发，而源节点则不再传给除目的节点外的其他节点，接受

到的消息的中继节点将做和源节点一样的工作，因此当网络中有i个副本时，一个新的

副本将以(N-i)人的泊松强度发给N-i个没有这个副本的节点，马尔可夫链的状态从i

变为i+1或者这i个副本中有一个以入i的强度转发给目的节点，马尔可夫链的状态从

i到N+lo马尔可夫链的状态由i到N+1的概率为方/((N-，)/1+方)=〃/7,从i到i+l

的概率为(N-i)4/((NT)2+万)=l-i/N,所以我们就能得到2跳多副本的传输方式中

两个节点间相遇时间间隔的分布。从状态i到状态i+l的时间间隔的分布函数为

尸(7；＜，)=1-6一(“)"，从状态i到N+1的时间间隔分布函数为=沟(根据

相遇时间间隔服从指数分布并目.泊松强度已知得到)。

Figure2不限跳多副本的马尔可夫链传输图

不限跳数的传输机制的传输图如图2所示，在消息转发机制为多跳副本不限的情况

下，节点将消息传给进入彼此通信范围内的节点，因此，当网络中有i个消息时，从状

态i到i+l的泊松强度为万(N-i),概率为——+=—+

从i到N+1的泊松强度为务,概率为&+=+,因此我们可以得

到从状态i到i+1的时间间隔的分布函数P(7；＜/)=1-1w,从状态i到N+1的时间

间隔的分布函数P((=疝。

三、RLC编码下的消息转发

RLC编码应用于机会网络的传输能够提高该消息的传输成功率。首先我们先介绍一

下RLC编码的机制，我们将每一个数据包看做是一个向量，向量里的元素来源于大小为

q的有限域与，假设数据包的大小为Sbits,那么代表这个数据包的编码向量包含

d=|S/bg打个元素。所谓编码就是将所有数据包的编码向量线性组合起来，假设有K

个数据包不i=l，2,3……，K。耳为一个向量，用来表示己。RLC编码就是将这K

个数据包线性的结合起来，那我们得到编码后的数据包为：

K

1=1

向量。=(q,……，即)，被称为编码向量，如果两个或者两个以上的编码数据包的

编码向量相互独立，那么我们称这几个编码的数据包相互独立。，在RLC的编码方案下,

网络节点存储编码数据包和编码向量，如果节点接收到r个线性无关的数据包，我们称

这个节点的秩为r。由这r个数据包的编码向量组成rXK的矩阵A。K个原始数据包组

r

成KXd的矩阵M=(mi,m2,……,mK),而受到的编码后的数据包组成rXd的矩阵

X=(xi,x2,……,xr)"因此我们可以通过求解方程AM=X来得到最初的K个原始的数据

包乂二4一一o

基于RLC的EpidemicRouting算法，他与前述两种传输机制有些差别，相当于有

多个初始信息，而且信息在传输过程中还会增加，因此这将不是一个马尔可夫链，但是

我们仍能够用泊松过程来解释他。

N-2N-l

Figure3RLC编码下的传输机制

因为在线性编码中，每一个节点中都可能含有你需要的消息，所以在这种机制下每

一个节点下一时刻与其他节点相遇的泊松强度为AU,而下一个节点中所包含有效信息

的概率为1-"夕，是与迦罗瓦域的大小有关。要想的到最初的K个原始数据包，目的节

点要收集到

K个线性无关的编码后的数据包，因为有效信息的概率为1-1/%所以至少要接触

K/(l-l//次，所以在一定的时间T内目的节点成功接收数据的概率为:

尸严1可)

在不使用编码的情况下，在EpidemicRouting算法下发送K个数据包，可以将它

看成是K个单独的不限跳多副本的马儿科夫链。当网络中只有一个数据包时，根据上面

的讨论我们可以知道每一个状态下目的节点收到消息的概率与跳数有关，在不限跳多副

本的情况下，网络中包含的副本个数的概率为。("=i)="N,i=1,2……,No当网络中

有i个副本时，目的节点在一定的时间内收到消息的概率为［所以平均的接

收概率为:

Pi=P(n=l)Pi(/=1)+=2)Pi(z=2).......P(n=N)Pi(i=N)

/=!

因为有K个数据包，所以最后的概率为:

N

Z=l

参数4在随机方向和随机路点模型中分别为：加力N空"，加亚=网嬖号。

卬BI.3683是随机路点模型中的一个特殊常数，E[V*]是两个节点的相对速度。如果

8rv8vvrv

V=Vmin=Vmax,我们有A/?D~-,ARW=

在我们所考虑的模型中，通过仿真看一下最终效果，在这个随机模型中我们设

N=100,K=10,q=128,在这里取v为5km/h,r=0.01km,L=l.5kmo那么在这种参数下

施=0.05659,/b?w=0.07743o那么通过RLC编码的接收成功率如图4所示，我们可以

看到，在一定的时间内见越大，节点最终收到消息的概率越大，同样，在同样大小的4

下，时间越长，节点收到消息的概率越大。图5展示了不通过线性编码节点传输成功率。

图6展示了相同几下，编码和不编码的传输成功率比较。

RWD模型下传输成功率

RWP模型下传输成功率

67

^6

§O6.5

-

14

。

0.3・

0.2••

0.1-

°00.511.522.533.544.55

仿真时间/h

FiguredRLC编码下不同4的传输成功率

协

日

货

统

e

功率

传输成

同，的

下不

编码

使用

re5不

Figu

神

R

曾

象

e

o

小

时间

仿真

成功率

的传输

非编码

编码和

同2下

re6相

Figu

总结

四、

和

松过程

其是泊

识，尤

程知

机过

量随

用大

中应

过程

机制

传输

消息

动和

的移

节点

研究

马尔可夫链，机会网络是利用节点移动带来的相遇机会来传输数据，如果能够对这一过

程进行数学建模对于实践应用有很好的指导意义。通过随机过程的学习，可以分析和优

化机会网络。

参考文献

[1]X.Zhang,G.Neglia,J.Kurose,andD.Towslcy,“Onthebenefitsof

randomlinearcodingforunicastapplicationsindisruptiontolerantnet­

works,vinProc.IEEEWiOPT,2006,pp.1-7.

[2]X.Zhang,G.Neglia,J.Kurose,andD.Towsley,^Performancemod­

elingofepidemicrouting,wComput.Netw.,vol.51/10,pp.2859-2891,

2007.

[3]X.Zhang,G.Neglia,J.Kurose,andD.Towsley,uBenefitsof

nctworkcodingindisruptiontolcrantnctworks,INRIA,Sophia

Antipolis,France,Tech.Rep.7277,2010[Online].Available:

http://hal.archives-ouvertes.fr/inria-OiMgd^B/en/

[4]Grossglauser,M.,andTse,D.Mobi1ityincreasesthecapacityofad-hoc

wirelessnetworks.ACM/1EEETransactionsinNetworking10,4(August2002),

477{486.

[5]Groenevelt,R.StochasticModelsforAdHocNetworks.PhDthesis,INRIA,

April2005.

[6]T.Ho,M.Mcdard,R.Koetter,andD.R.Karger,"Arandomlinear

networkcodingapproachtomulticast,“