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

随机过程在机会网络中的应用摘要机会网络是一种不需要在源节点和目的节点之间存在完整路径，利用节点移动带来的相遇机会实现网络通信，机会网络利用节点的移动形成的通信机会逐跳传输消息，以“存储携带转发”的路由模式实现节点间的通信，节点的移动特性及规律影响到网络性能，因此对节点移动规律的研究也变的至关重要，在经典的随机移动模型中节点的运动方式类似布朗运动，节点间的期望相遇时间服从指数分布。在Epidemic的路由算法经过two-hop，数据从源节点到目的节点的传输过程为马尔可夫链。因此随机过程被用于分析节点的移动规律和传输机制。关键词：移动模型、RLC编码、泊松过程、相遇概率1、 机会网络中的经典移动模型随机移动模型由于算法简单，节点间随机运动各自独立，移动节点时自由的、不加限制的，因此该模型常被应用于移动网络节点分析中，目前广泛用于描述MANET节点移动规律的随机移动模型主要有3个独立同分布移动模型：RWP模型（Random way Point model随机路点模型）、RWM模型（Random Walk Mobility Model,随机步行模型）和RDM模型（Random Direction Mobility model,随机方向移动模型）。RWP模型中，网络中节点随机分布在模拟区域中，并且呈现均与分布状态，节点在区域中的目标位置、运动速度、达到目标位置后停顿时间都是随机选择的，也就是说，在模拟运动空间Region内，节点随机选择一个目标位置D和一个运动速度V，从起点S以速度V沿直线运动到目的D。RWM模型的运动方式与布朗运动相似，常常又被称为布朗运动，在RWM模型中，移动节点从当前位置出发，其运动方向和速度都是随机选择的，并且速度V和方向服从均匀分布。RDM模型中节点的移动方式主要为“聚集分开再聚集”这样循环的过程，移动节点的速度V大小为一个定值，只有运动方向是随机选择，这个方向用一定的角度表示，在区间服从均匀分布。Bettstetter C等人的研究分别从不同的角度证明了上述3个移动模型的节点期望相遇时间服从指数分布或其尾部服从严格的指数分布。2、 随机模型下的消息转发在机会网络中，只有当两个移动节点在彼此的通信范围内时才能进行通信，在一个简单的随机模型中，一般只有两个输入参数，网络中的节点数量和独立同分布的泊松过程的强度。下面主要介绍两跳多副本和没有限制跳数的路由方法。首先介绍一个随机网络模型，这个模型中拥有N+1个相同的节点，源节点向目的节点发送一个消息，中间的节点可以作为中继节点帮助消息的转发，定义为节点i和j的相遇时间，为第n次相遇的时间间隔。，是相互独立的强度为的泊松过程，相应的随机变量是均匀独立的指数分布。当网络中只有一种消息，且节点不能存储相同的信息，那么信息的传输过程为马儿可夫链，在两跳多副本的情况下，马尔可夫链的状态为1，2，3，N+1。当网络中有i(1,2,3)个消息时（包括初始消息），马尔可夫链的状态为i，当消息到达目的节点时，马尔可夫链的状态为N+1,状态1,2，N是传输状态N+1是一个吸收状态。Figure1 2跳多副本的马尔可夫链传输图图1展示了2跳多副本的马尔可夫链的传输图，在两跳的协议下，源节点携带消息，转发给碰到的下一个节点，如果下一个节点时目的节点则传输完成，如果不是，则由下一个节点将接受消息并协助转发，而源节点则不再传给除目的节点外的其他节点，接受到的消息的中继节点将做和源节点一样的工作，因此当网络中有i个副本时，一个新的副本将以(N-i)的泊松强度发给N-i个没有这个副本的节点，马尔可夫链的状态从i变为i+1或者这i个副本中有一个以i的强度转发给目的节点，马尔可夫链的状态从i到N+1。马尔可夫链的状态由i到N+1的概率为，从i到i+1的概率为，所以我们就能得到2跳多副本的传输方式中两个节点间相遇时间间隔的分布。从状态i到状态i+1的时间间隔的分布函数为，从状态i到N+1的时间间隔分布函数为（根据相遇时间间隔服从指数分布并且泊松强度已知得到）。Figure2 不限跳多副本的马尔可夫链传输图不限跳数的传输机制的传输图如图2所示，在消息转发机制为多跳副本不限的情况下，节点将消息传给进入彼此通信范围内的节点，因此，当网络中有i个消息时，从状态i到i+1的泊松强度为，概率为，从i到N+1的泊松强度为，概率为，因此我们可以得到从状态i到i+1的时间间隔的分布函数，从状态i到N+1的时间间隔的分布函数。3、 RLC编码下的消息转发RLC编码应用于机会网络的传输能够提高该消息的传输成功率。首先我们先介绍一下RLC编码的机制，我们将每一个数据包看做是一个向量，向量里的元素来源于大小为q的有限域，假设数据包的大小为S bits，那么代表这个数据包的编码向量包含个元素。所谓编码就是将所有数据包的编码向量线性组合起来，假设有K个数据包，i=1,2,3，K。为一个向量，用来表示。RLC编码就是将这K个数据包线性的结合起来，那我们得到编码后的数据包为： 向量，被称为编码向量，如果两个或者两个以上的编码数据包的编码向量相互独立，那么我们称这几个编码的数据包相互独立。，在RLC的编码方案下，网络节点存储编码数据包和编码向量，如果节点接收到r个线性无关的数据包，我们称这个节点的秩为r。由这r个数据包的编码向量组成rK的矩阵A。K个原始数据包组成Kd的矩阵，而受到的编码后的数据包组成rd的矩阵，因此我们可以通过求解方程来得到最初的K个原始的数据包 。基于RLC的Epidemic Routing算法，他与前述两种传输机制有些差别，相当于有多个初始信息，而且信息在传输过程中还会增加，因此这将不是一个马尔可夫链，但是我们仍能够用泊松过程来解释他。Figure3 RLC编码下的传输机制因为在线性编码中，每一个节点中都可能含有你需要的消息，所以在这种机制下每一个节点下一时刻与其他节点相遇的泊松强度为，而下一个节点中所包含有效信息的概率为，是与迦罗瓦域的大小有关。要想的到最初的K个原始数据包，目的节点要收集到K个线性无关的编码后的数据包，因为有效信息的概率为，所以至少要接触次，所以在一定的时间T内目的节点成功接收数据的概率为：。在不使用编码的情况下，在Epidemic Routing算法下发送K个数据包，可以将它看成是K个单独的不限跳多副本的马儿科夫链。当网络中只有一个数据包时，根据上面的讨论我们可以知道每一个状态下目的节点收到消息的概率与跳数有关，在不限跳多副本的情况下，网络中包含的副本个数的概率为，i=1,2,N。当网络中有i个副本时，目的节点在一定的时间内收到消息的概率为，所以平均的接收概率为：因为有K个数据包，所以最后的概率为：参数在随机方向和随机路点模型中分别为：，。是随机路点模型中的一个特殊常数，是两个节点的相对速度。如果，我们有，在我们所考虑的模型中，通过仿真看一下最终效果，在这个随机模型中我们设N=100，K=10，q=128，在这里取v为5km/h，r=0.01km,L=1.5km。那么在这种参数下，。那么通过RLC编码的接收成功率如图4所示，我们可以看到，在一定的时间内越大，节点最终收到消息的概率越大，同样，在同样大小的下，时间越长，节点收到消息的概率越大。图5展示了不通过线性编码节点传输成功率。图6展示了相同下，编码和不编码的传输成功率比较。 Figure4 RLC编码下不同的传输成功率Figure5不使用编码下不同的传输成功率 Figure6 相同下编码和非编码的传输成功率4、 总结研究节点的移动和消息传输机制过程中应用大量随机过程知识，尤其是泊松过程和马尔可夫链，机会网络是利用节点移动带来的相遇机会来传输数据，如果能够对这一过程进行数学建模对于实践应用有很好的指导意义。通过随机过程的学习，可以分析和优化机会网络。参考文献1 X. Zhang, G. Neglia, J. Kurose, and D. Towsley, “On the benets ofrandomlinear coding for unicast applications in disruption tolerant net-works,” in Proc. IEEE WiOPT, 2006, pp. 17.2X. Zhang, G. Neglia, J. Kurose, and D. Towsley, “Performance mod-eling of epidemic routing,” Comput. Netw., vol. 51/10, pp. 28592891,2007.3X. Zhang, G. Neglia, J. Kurose, and D. Towsley, “Benets ofnetworkcodingindisruptiontolerantnetworks,”INRIA,SophiaAntipolis, France, Tech. Rep. 7277, 2010 Online. Available:http:/hal.archives-ouvertes.fr/inria-00494473/en/4Grossglauser, M., and Tse, D. Mobility increases the capacity of ad-hocwireless networks. ACM/IEEE Transactions in Networking 10, 4 (August 2002),477486.5Groenevelt, R. Stochastic Models for Ad Hoc Networks. PhD thesis, INRIA,April 2005.6T. Ho, M. Medard, R. Koetter, and D. R. Karger, “A random linearnetwork coding approach to multicast,” IEEE Trans. Inf. Theory, vol.52, no. 10, pp. 44134430, Oct. 2006.7C. Gkantsidis and P. Rodriguez. Network coding for large scale contentdistribution. Infocom, 2005.8R. Groenevelt, P. Nain, and G. Koole. The message delay in mobile adhoc networks. In Performance, October 20059T. Small and Z. J. Haas. Resource and performance tradeoffs indelay-tolerant wireless networks. In ACM workshop on Delay TolerantNetworking, 2005.10T. Spyropoulos, K. Psounis, and C. S. Raghavendra. Spray and wait: anefcient routing scheme for intermittently connected mobile networks.In ACM workshop on Delay Tolerant Networking, 2005.当网络中只有一种消息，且节点不能存储相同的信息，那么信息的传输过程为马儿可夫链，在两跳多副本的情况下，马尔可夫链的状态为1，2，3，N+1。当网络中有i(1,2,3)个消息时（包括初始消息），马尔可夫链的状态为i，当消息到达目的节点时，马尔可夫链的状态为N+1,状态1,2，N是传输状态N+1是一个吸收状态。Figure1 2跳多副本的马尔可夫链传输图图1展示了2跳多副本的马尔可夫链的传输图，在两跳的协议下，源节点携带消息，转发给碰到的下一个节点，如果下一个节点时目的节点则传输完成，如果不是，则由下一个节点将接受消息并协助转发，而源节点则不再传给除目的节