2. 东南大学 教育部计算机网络和信息集成重点实验室, 南京 210096
在移动自组织网络(MANETs)中常见路由算法的基础上, 如单副本路由和泛洪路由, 提出了一种基于轨迹相似度的单副本路由算法.针对单副本路由和泛洪路由中存在的问题, 如单副本路由中的大传输延迟、泛洪路由中的过量网络资源消耗及由此导致的数据丢失, 提出了基于历史轨迹记录相似度的多副本路由算法.通过仿真实验, 对所提算法在转发成功率、转发延时及转发次数等性能参数方面进行了评估.实验结果表明, 与现有的路由算法相比, 所提出的算法具有更好的性能表现, 达到了预期的设计目标.
2. Key Laboratory of CNII, Southeast University, Ministry of Education, Nanjing 210096, China
Based on the analysis of the common routing algorithms in mobile ad hoc networks (MANETs), e. g., single-copy and flooding, a routing algorithm, which uses single copy and the similarities of the trace, is proposed. To address the problems of single-copy and flooding routing, such as the high transmission delay in single-copy routing, the large amount of the network overhead and packet loss in the flooding, we K-copies routing algorithm based on the similarities of nodes trace records. Finally, the algorithms are evaluated in terms of several performance parameters, i. e., the packet delivery ratio, the average transmission delay and forwarding hops. The results of the simulations show that our algorithms have the better performance than other existing routing algorithms in MANETs.
MANETs是由一组可自由移动和相互通信的节点，通过自组织的方式构成的，其不需要依赖任何固定的基础网络设施.国内外的众多研究机构与学者已对MANETs的路由方法展开了许多卓有成效的研究，形成3种路由模型：① 单节点模型(摆渡节点模型[1])，由于网络中只有单个副本，因此该模型的网络开销较低，但无法避免投递机会低下所导致的传输中的高延迟问题；② 单副本模型[2]，该模型一般只能针对特定的网络，须充分利用节点移动的规律性，很难适应多数场景；③ 多副本模型，如泛洪路由[3]和多副本路由[4-5]，更多副本的存在提高了投递率，降低了传输延迟，然而过多的副本复制造成了网络资源的过度消耗和节点开销的增加.为此，笔者根据节点记录的相遇节点的历史信息，提出了一个基于历史相遇记录相似度的单副本网络模型，在提高节点转发成功率的同时，减少网络的负载开销；然后通过分析单副本路由(SCR, single-copy routing)算法和泛洪路由算法的性能瓶颈所在，设计实现了基于历史记录相似度的K副本路由算法；最后通过仿真实验，研究了节点随机移动模型下，各算法的性能表现，并分析了所提算法仿真结果的有效性.
1 运动轨迹驱动的SCR算法在单副本模型路由算法中，只生成一份送往目标节点的消息拷贝.每当带有该副本的节点a与节点b相遇时，如果b有更大的可能性将副本送达目标节点，那么a就将该副本转发给b.
如果2个节点的历史相遇记录中，共同遇到的节点所占的比例接近，说明这2个节点的活动范围和运动轨迹比较接近，遇到许多相同的节点，所以尽可能避免将消息转发给这样的节点，避免节点在小范围内频繁转发.根据节点之间访问的节点历史记录表可以计算出节点的相似程度：
|
(1) |
其中List(a)与List(b)为节点a与节点b的节点相遇历史记录表.由式(1) 可以看出，P(a, b)∈(0, 1)，相似度P的值越高，可以认为a与b的活动范围与运动轨迹相近，所以将副本转交给b的概率将随之降低，即节点a转发消息给节点b的概率为1-P(a, b).
2 运动轨迹驱动的多副本路由算法在多副本模型路由算法中，最简单并且最易实现的是泛洪路由算法.在泛洪路由算法中，每当有节点相遇时，便将各自携带的消息复制并转发给对方，这样能快速地在网络中扩散.泛洪路由算法是消耗网络资源最快的一种路由算法，在资源极其有限的无线传感器网络中，常常会因为缓存空间不足导致大量的数据拥塞以及数据丢失.所以要设计一些其他的方法来限制副本的数量，有效地利用有限的网络资源，并且有效率地将副本送达目标节点.
笔者考虑使用一个K值来控制消息在网络中的副本数量.在消息生成时赋予一个消息K份拷贝，当与新的节点相遇时，分割这K份拷贝，直到所携带的拷贝数为1时不再分割，而采用直接发送的方式将消息发送到目标节点.
K副本路由算法是SCR算法和泛洪路由算法的折衷算法.
2.1 二分K副本路由算法二分K副本方法采用每次二分K值的方法来分割这K个副本，具体方法：初始化令消息具有K个副本；任何一个携带有n(n>1) 个该消息副本的节点a(包括源节点和中继节点)，遇到另外一个节点b(没有该消息的拷贝)，将会移交
当节点移动符合独立同分布时，二分法的K副本分发策略是最优的数据分发策略.
2.2 基于相似度的K副本路由算法当节点随机移动，符合独立同分布时，二分法是最优的分发策略，但在实际的无线Ad hoc网络中，节点移动符合一定的群聚特征.从这一点出发，可以引入第1节中提出的相似度来进行K副本的分发.
初始化令消息具有K个副本；任何一个携带有n(n>1) 个该消息副本的节点a(包括源节点和中继节点)，遇到另外一个节点b(没有该消息的拷贝)，首先将会交互a与b的相遇历史记录信息，由式(1) 可以计算出相似度P(a, b)，根据相似度P移交
仿真实验使用已开发完成的时间片驱动的支持节点移动模型的仿真器.
3.1 副本数K值的确定为了讨论方便，假定在一个方形的场景(大小为200 m×200 m)中.每次实验开始时将生成100份待分发消息，这100份消息随机分配给随机分布的N个节点.节点采用随机移动模型(移动随机且独立同分布)，移动速度在5~10 m/s之间，平均速度为7.5 m/s，节点间的通信半径为20 m.基于相似度的K副本路由(PSAW, probability spray and wait)算法中相似度参数：历史相遇记录长度设置为10，存活期为20 s.
如图 1所示，副本数目的设置与网络中存在的总节点数是有关系的，当节点数量变大时，所需的副本数量也要随之增加，但是也不能持续增加，不然就会转变为泛洪路由算法而导致网络负载变大，从仿真结果分析来看，一般考虑在总节点数的1/5左右为最佳.
|
图 1 副本数K值的确定 |
该场景中设置网络的节点规模为50个.从图 2(a)中可以看出，由于节点的缓存容量有限，导致消息大量丢失.PSAW算法的性能介于二分K副本路由(BSAW, binary spray and wait)算法与泛洪路由算法之间.从图 2(b)中可以看出，网络负载对每个算法的消息平均投递延时影响不大，其中泛洪路由算法具有最小的消息平均投递延时，相反SCR算法具有很大的平均投递延时.从图 2(c)中可以看出，SCR算法的转发次数增长速度特别快，PSAW算法与BSAW算法的延时与转发次数基本一致，当K取值增加时，消息转发延时将减少，同时转发次数也有一定数量的增加.所以K副本路由算法在网络负载不同的网络中的表现介于SCR算法和泛洪路由算法之间.
|
图 2 初始生成消息数的影响 |
从图 3(a)中可以看出，SCR算法受节点密度的影响较小，K副本路由算法相比泛洪路由算法更能适应不同节点密度的网络环境.图 3(b)显示节点密度的增加将减少泛洪路由算法的消息转发延时，但是对K副本路由算法影响不大，介于SCR算法和泛洪路由算法之间.图 3(c)显示K副本路由算法能维持在一个比较稳定的状态.在不同节点密度的环境中，PSAW算法和BSAW算法能维持比较良好的表现.
|
图 3 节点密度的影响 |
笔者提出了一种基于相似度的SCR算法和基于相似度的K副本路由算法.通过仿真实验，测试算法的性能表现，并与现有的算法进行了对比分析，实验结果表明所提算法可以较好地提高消息的投递率，降低传输延迟.
| [1] | Lindgren A, Doria A, Schel'en O. Probabilistic routing in intermittently connected networks[J].SIGMOBILE Mobile Computting Communications Review, 2003, 7(3): 19–20. doi: 10.1145/961268 |
| [2] | Wu Jie, Wang Yunsheng. A non-replication multicasting scheme in delay tolerant networks [C]//IEEE. Mobile Ad hoc and Sensor Systems(MASS). San Francisco, CA: IEEE, 2010: 89-98. |
| [3] | Vahdat A, Becker D. Epidemic routing for partially connected ad hoc networks[J].Technical Report CS-200006, Duke University, 2000. |
| [4] | Spyropoulos T, Psounis K, Raghavendra C. Spray and wait: an efficient routing scheme for intermittently connected mobile networks [C]//ACM. SIGCOMM Workshop on Delaytolerant Networking. New York, USA: ACM, 2005: 252-259. |
| [5] | Spyropoulos T, Psounis K, Raghavendra C. Spray and focus: efficient mobility-assisted routing for heterogeneous and correlated mobility [C]//IEEE. Pervasive Computting and Communications Workshops. White Plains, NY: IEEE, 2007: 79-85. |