基于相遇节点跨层感知的机会网络高效低时延路由算法

doi:10.3969/j.issn.1000-436x.2013.10.001

摘要/Abstract

摘要：

针对基于epidemic机制的机会网络路由算法未能及时感知相遇节点以及在数据分组交换过程中存在冗余的问题，提出了一种采用跨层感知相遇节点思路的机会网络高效低时延路由算法——ERCES（epidemic routing based on cross-layer encountered-node sensing），通过在物理层、MAC层和网络层之间的跨层信息共享与协同，实现相遇节点及时感知，并且采用节点相遇后立即广播新数据分组、收到SV（summary vector）分组后优先发送目的节点为对方的数据分组、动态自适应发送HELLO分组、借助SV删除节点缓存中已到达目的节点的分组等新机制，减少控制和存储开销，降低分组时延。理论分析验证了ERCES算法的有效性，仿真结果表明：与经典的Epidemic Routing算法及其多个改进相比，ERCES算法的控制开销和存储开销分别减少8.2%和2.1%以上，数据分组平均端到端时延至少降低了11.3%。

关键词: 机会网络, 路由算法, 相遇节点, 感知, 跨层设计

Abstract:

An efficient low-delay routing algorithin,name epidemic routing based on cross-layer encountered-node sens-ing (ERCES)was proposed to address the issue that the epidemic-based routing algorithms have some extralatency in sensing encountered nodes and extra overhead in exchanging data packets.ERCES achieves to speed sensing encountered nodes through cross-layer design among the PHY,MAC,and network layers.Moreover,to reduce overhead and to de-crease data latency,it makes a node send novel data packet immediately after encountering other nodes,sends the packets close-by their destinations firstly after receiving summary vector(SV)packets,adaptively varies the period of HELLO packets and deletes the packets reaching their destinations from nodes' memory with the help of SVs.Theoretical anal-,ysis verifies the effectiveness of ERCES.And simulation results show that ERCES reduces by at least 11.3% the control overhead by at least 8.2%,2.1% memory overhead by more than 2.1%,and the average end-to-end delay by at least 11.3%.

Key words: opportunistic network, routing algorithm, encountered node, sensing, cross-layer design

任智,索建伟,陈红,徐中浩,陈前斌. 基于相遇节点跨层感知的机会网络高效低时延路由算法[J]. 通信学报, 2013, 34(10): 1-8.

Zhi REN,Jian-wei SUO,Hong CHEN,Zhong-hao XU,Qian-bin CHEN. Efficient low-delay routing algorithm for opportunistic networks based on cross-layer sensing of encountered nodes[J]. Journal on Communications, 2013, 34(10): 1-8.

图/表 10

图1

图2

图3

表1

图4

图5

图6

图7

图8

表2

参考文献 18

[1]	STAVROULAKI V , TSAGKARIS K , LOGOTHETIS M ,et al. Opportunistic networks[J]. IEEE Vehicular Technology Magazine, 2011,6(3): 52-59.
[2]	熊永平, 孙利民, 牛建伟 ,等. 机会网络[J]. 软件学报, 2009,20(1): 124-137. XIONG Y P , SUN L M , NIU J W ,et al. Opportunistic networks[J]. Journal of Software, 2009,20(1): 124-137.
[3]	叶晖, 陈志刚, 赵明 . ON-CRP:机会网络缓存替换策略研究[J]. 通信学报, 2010,31(5): 98-107. YE H , CHEN Z G , ZHAO M . ON-CRP:cache replacement policy for opportunistic networks[J]. Journa1 on Communications, 2010,31(5): 98-107.
[4]	刘乔寿, 周建二, 张普宁 . 机会网络中基于消息副本数量的自适应缓存管理策略[J]. 重庆邮电大学学报 (自然科学版), 2012,23(4): 394-399. LIU Q S , ZHOU J E , ZHANG P N . Adaptive cache management method for opportunistic network based on number of message copies[J]. Journal of Chongqing University of Posts and Telecommu ications (Natural Science Edition), 2012,23(4): 394-399.
[5]	BURGESS J , GALLAGHER B , JENSEN D ,et al. Maxprop:routing for vehicle-based disruption-tolerant networks[A]. The 25th IEEE International Conference on Computer Communications[C]. ashington DC,USA, 2006. 1-11.
[6]	BURNS B , BROCK O , LEVINE B N . Mv routing and capacity building in disruption tolerant networks[A]. The 24th Annual Joint Conference of Conference of the IEEE Computer and Communicat ns Societies[C]. Miami,USA, 2005. 398-408.
[7]	JATHAR R , GUPTA A . Probabilistic routing using contact sequencing in delay tolerant networks[A]. 2010 the Second International Conference on Communication Systems and Networks[C]. Bangalore,India, 2010. 1-10.
[8]	KO H , OH S , KIM C . Adaptive,asynchronous rendezvous protocol for opportunistic networks[J]. Journal of Electronic Letters, 2012,48(8): 462-464.
[9]	VAHDAT A , BECKER D . Epidemic Routing for Partially Connected Ad Hoc Networks[R]. 2000.
[10]	MATSUADA T , TAKINE T . (p,)-Epidemic routing for sparselyq populated mobile ad hoc networks[J]. IEEE Journal on Selected Areas in Communications, 2008,26(5): 783-793.
[11]	TOWER J P , LITTLE T D C . A proposed scheme for epidemic routing with active curing for opportunistic networks[A]. The 22nd International Conference on Advanced Information Networking and Applications Workshops[C]. Okinawa,Japan, 2008. 1696-1701.
[12]	WANG X , SHU Y T , JIN Z G ,et al. Adaptive randomized epidemic routing for disruption tolerant networks[A]. The 5th International Conference on Mobile Ad Hoc and Sensor Networks[C]. Wu Yi Mountain,China, 2009. 424-429.
[13]	任智, 黄勇, 陈前斌 . 基于分组索引增量交换的机会网路高效低时延路由算法[J]. 计算机学报, 2010,33(9): 1634-1642. REN Z , HUANG Y , CHEN Q B . An efficient low-delay routing algorithm for opportunistic networks based on exchange of increments in packet indexes[J]. Chinese Journal of Computers, 2010,33(9): 1634-1642.
[14]	DEMERS A , GREENE D , HAUSER C ,et al. Epidemic algorithms for replicated database maintenance[A]. The 6th Symposium on Principles of Distributed Computing[C]. British Columbia,Canada, 1987. 8-32.
[15]	任智, 陈前斌, 黄勇 . 机会网络中基于跨层触发的相遇节点快速感知方法[P]. 中国发明专利,201010042051.2 2010. REN Z , CHEN Q B , HUNAG Y . A Fast Approach for Sensing Encountered Nodes in Opportunistic Networks Based on Cross-Layer Triggering[P]. China Invention Patent,201010042051.2 2010.
[16]	CORSON M S , PAPADEMETRIOU S , PAPADEMETRIOU P , et al. An internet MANET encapsulation protocol (IMEP)specification[EB/OL]. .
[17]	GROSSGLAUSER M , TSE D N C . Mobility increases the capacity of ad hoc wireless networks[J]. IEEE/ACM Transactions on Network g, 2002,10(4): 477-486.
[18]	林闯, 田源, 姚敏 . 绿色网络和绿色评价:节能机制、模型和评价[J]. 计算机学报, 2011,34(4): 593-612. LIN C , TIAN Y , YAO M . Green network and green evaluation:mechanism,modeling and evaluation[J]. Chinese Journal of Computers, 2011,34(4): 593-612.

参数	数值
网络面积/m²	1 500×300
节点运动速度/(ms^-1)	1～19
传输速率/(Mbit·s^-1)	54
节点个数	50
分组产生间隔/s	1
节点通信范围/m	10,25,50,75,100
相遇时间阈值/s	1.23,3.07,6.15,9.22,12.3
仿真时间/s	4 000