Forwarding vs. Network Coding: Efficient Broadcasting in Multihop Wireless Networks

Suranjit Paul, Thomas Kunz, Li Li
DOI: 10.4236/ijcns.2011.44025                

Abstract

Broadcasting is used as a building block in many MANET (Mobile Ad hoc Network) routing protocols. In addition, broadcasting is a key primitive in ad hoc networks to support group-based applications. Efficiently supporting broadcasting in multihop wireless networks is therefore important. In this paper, we compare ef-ficient broadcasting protocols based on packet forwarding with those based on network coding. Using a number of network scenarios, we derive lower bounds for the required number of packet retransmissions at the MAC layer to support broadcast with and without applying network coding techniques. We compare these lower bounds with each other, as well as with protocols proposed for each approach. More specifically, we use SMF and PDP as sample forwarding-based broadcast protocols, and a simple XOR-based coding protocol over SMF and PDP as representative network coding solution. The results show that neither packet forwarding protocols nor network coding protocols achieve the theoretical lower bounds, in particular as the size of the network area (at constant density) increases. The comparison of the lower bounds also shows that network coding does have a potential performance advantage over packet forwarding solutions for broad-casting in multi-hop wireless networks, in particular for larger fixed density networks, justifying its inherent increased complexity.

Keywords

MANETs, Broadcasting, Multi-hop Networks, SMF, PDP, Network Coding

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	M. R. Garey and D. S. Johnson, “Computers and Intractability: A Guide to the Theory of NP-Completeness,” Freeman, San Francisco, 1978.
[2]	F. V. Fomin, F. Grandoni and D. Kratsch, “Solving Connected Dominating Set Faster than 2n,” Algorithmica, Vol. 52, No. 2, 2008, pp. 153-166. doi:10.1007/s00453-007-9145-z
[3]	S. Guha and S. Khuller, “Approximation Algorithms for Connected Dominating Sets,” Algorithmica, Vol. 20, No. 4, April 1998, pp. 374-387.
[4]	S. Butenko, X. Cheng and C. A. S. Oliveira, “A New Heuristic for the Minimum Connected Dominating Set Problem on Ad Hoc Wireless Networks,” in: S. Butenko, R. Murphey and P. Pardalos, Eds., Recent Developments in Cooperative Control and Optimization, Kluwer Academic Publishers, Norwell, 2004, pp. 61-73.
[5]	M. Min, H. Du, X. Jia, C. X. Huang, S. C. H. Huang and W. Wu, “Improving Construction for Connected Dominating Set with Steiner Tree in Wireless Sensor Networks,” Journal of Global Optimization, Vol. 35, No. 1, 2006, pp. 111-119. doi:10.1007/s10898-005-8466-1
[6]	Y. Li, M. T. Thai, F. Wang, C. W. Yi, P. J. Wan and D. Z. Du, “On Greedy Construction of Connected Dominating Sets in Wireless Networks,” Wireless Communications and Mobile Computing, Vol. 5, No. 8, December 2005, pp. 927-932. doi:10.1002/wcm.356
[7]	M. Rai, S. Verma and S. Tapaswi, “A Heuristic for Minimum Connected Dominating Set with Local Repair for Wireless Sensor Networks,” Proceedings of the 2009 8th International Conference on Networks, Guadeloupe, 1-6 March 2009, pp. 106-111.
[8]	J. P. Macker, J. Dean and W. Chao, “Simplified Multicast Forwarding in Mobile Ad Hoc Networks,” Proceedings of the Military Communications Conference, Monterey, 31 October-3 November 2004, pp. 744-750.
[9]	J. Macker, I. Downard, J. Dean and B. Adamson, “Evaluation of Distributed Cover Set Algorithms in Mobile Ad Hoc Network for Simplified Multicast Forwarding,” Mobile Computing and Communications Review, Vol. 11, No. 3, July 2007, pp. 1-11.
[10]	W. Lou and J. Wu, “On Reducing Broadcast Redundancy in Ad Hoc Wireless Networks,” IEEE Transactions on Mobile Computing, Vol. 1, No. 2, April-June 2002, pp. 111-123.
[11]	R. Ahlswede, N. Cai, S.-Y. R. Li and R. W. Yeung, “Network Information Flow,” IEEE Transactions on Information Theory, Vol. 46, No.4, 2000, pp. 1204-1216.
[12]	L. Li, R. Ramjee, M. Buddhikot and S. Miller, “Network Coding Broadcast in Mobile Ad Hoc Networks,” Proceedings of the 26th IEEE International Conference on Computer Communications, Anchorage, 6-12 May 2007, pp. 1739-1747.
[13]	S. Katti, H. Rahul, W. Hu, D. Katabi, M. Medard and J. Crowcroft, “XORs in the Air: Practical Wireless Network Coding,” Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, Vol. 36, No. 4, October 2006, pp. 243-254.
[14]	J. S. Park, D. S. Lun, Y. Yi, M. Gerla and M. Medard, “CodeCast: A Network-Coding Ad Hoc Multicast Protocol,” IEEE Wireless Communications, Vol. 13, No. 5, October 2006, pp. 76-81.
[15]	Y. Wu, K. Jain and S. Kung, “A Unification of Network Coding and Tree-Packing (Routing) Theorems,” IEEE/ACM Transactions on Networking, Vol. 52, No. 6, June 2006, pp. 2398-2409.
[16]	C. Campolo, C. Casetti, C. F. Chiasserini and S. Tarapiah, “Performance of Network Coding for Ad Hoc Networks in Realistic Simulation Scenarios,” Proceedings of the IEEE International Conference on Telecommunications, Marrakech, 25-27 May 2009, pp. 31-36.
[17]	D. E. Lucani, M. Medard and M. Stojanovic, “Broadcasting in Time-Division Duplexing: A Random Linear Network Coding Approach,” Proceedings of the Workshop on Network Coding, Theory, and Applications, Lausanne, 15-16 June 2009, pp.62-67.
[18]	R. Khalili, M. Ghaderi, J. Kurose and D. Towsley, “On the Performance of Random Linear Network Coding in Relay Networks,” Proceedings of the IEEE Military Communications Conference, San Diego, 16-19 November 2008, pp. 1-7.
[19]	C. Adjih and S. Y. Chon, “Wireless Broadcast with Network Coding: Energy Efficiency, Optimality and Coding Gain in Lossless Wireless Networks,” Research Report RR-7011, France, July 2009.
[20]	C. Fragouli, J. Widmer and J. Le Boudec, “Efficient Broadcasting Using Network Coding,” IEEE/ACM Transactions on Networking, Vol. 16, No. 2, April 2008, pp. 450-463.
[21]	T. Kunz, S. Paul and L. Li, “Efficient Broadcasting in Tactical Networks: Forwarding vs. Network Coding,” Proceedings of the Military Communication Conference, San Jose, 31 October-3 November 2010, pp. 1245-1250.