基于网络编码的机会网络高效路由算法

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

摘要/Abstract

摘要：

针对采用Epidemic机制的机会网络路由算法在数据分组传送阶段存在通信冗余的问题，提出了一种基于网络编码的高效路由算法——NCBER(network-coding-based epidemic routing）。NCBER在传送数据分组的过程中使用主动异或网络编码和多播，并取消了 Request（请求）控制分组，从而减少数据分组的转发次数和控制分组数量，降低网络开销，缩短分组传输时延。理论分析和仿真结果表明，NCBER 算法在网络开销和数据分组端到端时延性能方面优于经典的Epidemic路由算法及其改进算法MRRMR（message redundancy removal of multi-copy routing），并且使数据传送成功率保持在100%。

关键词: 机会网络, 路由算法, 网络编码, 多播, 网络开销

Abstract:

To address the problem in opportunistic network that t existing epidemic-mechanism-based routing algorithms incur redundant communication overhead during the transmission of data packets,an efficient routing algorithm based on network coding,called NCBER (network-coding-based epidemic routing),was proposed.During the transmission of data packets,NCBER adopts an active XOR coding operation and multicast,and cancels the transmission of the Request control packets,so as to reduce the time used to transmit data packets,as well as the number of control packets.As a result,NCBER cuts down the network overhead and ortens the end-to-end delay of data packets.Theoretical analysis and extensive simulation results show that NCBER outperforms the classical epidemic routing algorithm and its improvement called MRRMR (message redundancy removal of multi-copy routing) in terms of the network overhead and the end-to-end delay,while still keeping the delivery rate at 100%.

Key words: opportunistic network, routing algorithm, network coding, multicast, network overhead

任智,刘智虎,姚玉坤,陈前斌. 基于网络编码的机会网络高效路由算法[J]. 通信学报, 2013, 34(9): 16-23.

Zhi REN,Zhi-hu LIU,Yu-kun YAO,Qian-bin CHEN. Efficient routing algorithm for opportunistic networks based on network coding[J]. Journal on Communications, 2013, 34(9): 16-23.

图/表 8

图1

图2

图3

表1

图4

图5

图6

表2

参考文献 16

[1]	PELUSI L , PASSARELLA A , CONTI M ,et al. Opportunistic networking:data forwarding in disconnected mobile ad hoc networks[J]. IEEE Communications Magazine, 2006,44(11): 134-141.
[2]	VAHDAT A , BECKER D . Epidemic Routing for Partially Connected Ad Hoc Networks[R]. Duke University, 2000.
[3]	WEN H , REN F Y , LIU J ,et al. A storage-friendly routing scheme in intermittently connected mobile network[J]. IEEE Transactions on Vehicular Technology, 2011,60(3): 1138-1149.
[4]	AHLSWEDE R , CAI N , LI S Y R ,et al. Network information flow[J]. IEEE Trans Inform Theory, 2000,46(4): 1204-1216.
[5]	LI S Y R , YEUNG R W , CAI N . Linear network coding[J]. EEE Transactions on Information Theory, 2003,49(2): 371-381.
[6]	NGUYEN D , NGUYEN T , BOSE B . Wireless Broadcasting Using Network Coding[R]. Oregon State University, 2006.
[7]	KATTI S , RAHUL H , HU W ,et al. Xors in the air:practical wireless network coding[J]. IEEE/ACM Transactions on Networking, 2008,16(3): 497-510.
[8]	CHACHULSKI S , JENNINGS M , KATTI S ,et al. Trading structure for randomness in wireless opportunistic routing[A]. Proceedings of the 2007 conference on Applications,technologies,architectures,and protocols for computer communications(SIGCOMM'07)[C]. New York,USA, 2007. 169-180.
[9]	LU X F , HUI P . An energy-efficient n-epidemic routing protocol for delay tolerant networks[A]. 2010 the Fifth IEEE International Conference on Networking,Architecture,and Storage[C]. Macau,China, 2010. 341-347.
[10]	RESTA G , SANTI P . A Framework for Routing Performance Analysis in Delay Tolerant Networks with Application to Noncooperative Networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2012,23(1): 2-10.
[11]	ZHANG X L , NEGLIA G , KUROSE J ,et al. On the bene?ts of random linear coding for unicast applications in disruption tolerant networks[A]. The Second Workshop on Network Coding,Theory,and Applications[C]. Massachusetts,USA, 2006. 1-7.
[12]	LIN Y F , LI B C , LIANG B . Stochastic analysis of network coding in epidemic routing[J]. IEEE Journal on Selected Areas in Communications, 2008,26(5): 794-808.
[13]	ZHAO B K , SONG Z M , SU J S ,et al. NTC:towards efficient network coding in delay tolerant networks[A]. 2011 the Fifth International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing[C]. Seoul,Korea, 2011. 57-64.
[14]	YU H Z , MA J F , BIAN H . Message redundancy removal of multi-copy routing in delay tolerant MANET[J]. The Journal o China Universities of Posts and Telecommunications, 2011,18(1): 42-48.
[15]	ZHANG X , NEGLIA G , KUROSE J ,et al. Performance modeling of epidemic routing[J]. Computer Networks, 2007,51(10): 2867-2891.
[16]	VIANI F,LIZZI L , ROCCA P , et a l . Object tracking through RSSI measurements in wireless sensor networks[J]. Electronics Letters, 2008,44(10): 653-654.

参数	取值
节点数量	100
仿真范围	1 500×600
移动模型/(m·s^-1)	Random Waypoint
速率区间/s	1,19]
运动间歇时间/s	0
通信半径/m	10，25，50，75，100
仿真时间/s	3 000
最大数据速率/(Mbit·s^-1)	54
数据分组大小/KB	1
数据分组发送间隔/s	1
发分组起始时间/s	5
发分组结束时间/s	1 984
节点缓存大小/KB	2 000
Hello周期/s	3
相遇时间间隔阈值/s	21.65
随机种子	128，130，132，134