Forwarding vs. Network Coding: Efficient Broadcasting in Multihop Wireless Networks
- 1
- 2
- 3
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.
- M. R. Garey and D. S. Johnson, “Computers and Intractability: A Guide to the Theory of NP-Completeness,” Freeman, San Francisco, 1978.
- 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
- S. Guha and S. Khuller, “Approximation Algorithms for Connected Dominating Sets,” Algorithmica, Vol. 20, No. 4, April 1998, pp. 374-387.
- 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.
- 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
- 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
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.