An Efficient Routing Algorithm for Opportunistic Networks Based on Network Coding

Abstract:

To address the problems in Opportunistic Networks that nodes employing routing algorithms based on epidemic mechanism cant sense their neighboring nodes timely and many redundant data packets permeate through the network, an efficient routing algorithm based on XOR network coding was proposed (Xor Network Coding based Epidemic Routing, XNCER). When a node gets a Hello message, it broadcasts, instead of unicasting, a SV(Summary Vector) packet, in return, to all its neighboring nodes. Therefore, the data transmission can be initiated immediately, and the XOR network coding can also be leveraged so as to enhance the efficiency of data transmission. Moreover, the packets destined to the one hop neighboring nodes obtain the priority in transmission, and are determined whether to be deleted based on the ACK mechanism running in the MAC layer in order to cut down the memory overhead and restrain redundant packets from dissemination. Theoretical analysis and extensive simulation results show that the new algorithm obtains an overall improvement in terms of network overhead, average end-to-end delay as well as delivery rate. The novel algorithm can effectively solve the problems of sensing neighboring nodes and data redundancy.

• Periodical: Advanced Materials Research (Volumes 756-759)
• Pages: 2214-2219
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.756-759.2214
• Online since: September 2013
• Authors: Yu Kun Yao, Zhi Hu Liu, Zhi Ren, Ya Di Wen
• Keywords: Delay, Delivery Rate, Network Coding, Opportunistic Networks, Overhead, Routing Algorithm

References

[1] A. Vahdat, D. Becker, Epidemic Routing for Partially Connected Ad Hoc Networks. Technical Report CS-200006, Duke University, (2000).

[2] L. Pelusi, A. Passarella, and M. Conti, Opportunistic networking: data forwarding in disconnected mobile ad hoc networks, IEEE Communications Magazine, vol. 44, p.134–141, (2006).

DOI: 10.1109/mcom.2006.248176

[3] R. Ahlswede, N. Cai, and S.Y.R. Li, Network information flow, IEEE Trans Inform Theory, vol. 46, p.1204–1216, (2000).

DOI: 10.1109/18.850663

[4] H. Wen, F.Y. Ren, and J. Liu, A storage-friendly routing scheme in intermittently connected mobile network, IEEE Transactions on Vehicular Technology, vol. 60, p.1138–1149, (2011).

DOI: 10.1109/tvt.2011.2104378

[5] J. Z. Sun, Y.Y. Xiao, and H.Q. Chen, Wait and Epidemic Routing Algorithm. China Patent, CN201110130398. 7, (2011).

[6] M. Grossglauser, D.N.C. Tse, Mobility increases the capacity of ad hoc wireless networks, IEEE/ACM Trans. on Networking, Vol. 10, p.477–486, (2002).

DOI: 10.1109/tnet.2002.801403

[7] S. Katti, H. Rahul, and W. Hu, Xors in the air: practical wireless network coding, IEEE/ACM Transactions on Networking, Vol. 16, p.497–510, (2008).

DOI: 10.1109/tnet.2008.923722

[8] X.M. Wang, J.P. Wang, Y.L. Xu, Data dissemination in wireless sensor networks with network coding, EURASIP Journal on Wireless Communication and Networking, p.1–14, (2010).

DOI: 10.1155/2010/465915

[9] Y.F. Lin, B.C. Li, and B. Liang, Stochastic analysis of network coding in epidemic routing, IEEE Journal on Selected Areas in Communications, vol. 26, p.794–808, (2008).

DOI: 10.1109/jsac.2008.080606

[10] S.K. Yoon, Z.J. Haas, Application of linear network coding in delay tolerant networks, The Second International Conference on Ubiquitous and Future Networks (ICUFN 2010), IEEE Press, 2010, p.338–343.

DOI: 10.1109/icufn.2010.5547179

[11] B.K. Zhao, Z.M. Song, and J.S. Su, NTC: Towards efficient network coding in delay tolerant networks, 2011 Fifth International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing, IEEE Press, 2011, p.57–64.

DOI: 10.1109/imis.2011.105

[12] F. Mourad, H. Snoussi, and C. Richard, Interval-Based Localization using RSSI Comparison in MANETs, IEEE Transactions on Aerospace and Electronic System, vol. 47, p.2897–2910, (2011).

DOI: 10.1109/taes.2011.6034672