Challenges: towards truly scalable ad hoc networks

ABSTRACT

The protocols used in ad hoc networks today are based on the assumption that the best way to approach multiple access interference (MAI) is to avoid it. Unfortunately, as the seminal work by Gupta and Kumar has shown, this approach does not scale. Recently, Ahlswede, Ning, Li, and Yeung showed that network coding (NC) can attain the max-flow min-cut throughput for multicast applications in directed graphs with point-to-point links. Motivated by this result, many researchers have attempted to make ad hoc networks scale using NC. However, the work by Liu, Goeckel, and Towsley has shown that NC does not increase the order capacity of wireless ad hoc networks for multi-pair unicast applications. We demonstrate that protocol architectures that exploit multi-packet reception (MPR) do increase the order capacity of random wireless ad hoc networks by a factor Θ(log n) under the protocol model. We also show that MPR provides a better capacity improvement for ad hoc networks than NC when the network experiences a single-source multicast and multi-pair unicasts. Based on these results, we introduce design problems for channel access and routing based on MPR, such that nodes communicate with one another on a many-to-many basis, rather than one-to-one as it is done today, in order to make ad hoc networks truly scalable.

REFERENCES

• 1: P. Gupta and P. R. Kumar, "The capacity of wireless networks," IEEE Transactions on Information Theory, vol. 46, no. 2, pp. 388--404, 2000.
• 2: M. Grossglauser and D. Tse, "Mobility increases the capacity of ad hoc wireless networks," in Proc. of IEEE INFOCOM 2001, Anchorage, Alaska, USA., April 22--26 2001.
• 3: R. M. de Moraes, H. R. Sadjadpour, and J. J. Garcia-Luna-Aceves, "Throughput-delay analysis of mobile ad-hoc networks with a multicopy relaying strategy," in Proc. of IEEE SECON 2004, Santa Clara, CA, USA., October 4-7 2004.
• 4: R. Ahlswede, C. Ning, S. Y. R. Li, and R. W. Yeung, "Network information flow," IEEE Transactions on Information Theory, vol. 46, no. 4, pp. 1204--1216, 2000.
• 5: S. katti, D. Katabi, W. Hu, H. Rahul, and M. Medard, "The importance of being opportunistic: Practical network coding for wireless environments," in Proc. of Allerton 2005, Allerton House, UIUC, Illinois, USA., Sep. 2005.
• 6: J. Liu, D. Goeckel, and D. Towsley, "Bounds on the gain of network coding and broadcasting in wireless networks," in Proc. of IEEE INFOCOM 2007, Anchorage, Alaska, USA., May 6-12 2007.
• 7: Z. Li and B. Li, "Network coding in undirected networks," in Proc. of CISS 2004, Princeton, NJ, USA., March 17-19 2004.
• 8: S. Ghez, S. Verdu, and S. C. Schwartz, "Stability properties of slotted aloha with multipacket reception capability," IEEE Transaction on Automatic Control, vol. 33, no. 7, pp. 640--649, 1988.
• 9: -, "Optimal decentralized control in the random access multipacket channel," IEEE Transaction on Automatic Control, vol. 34, no. 11, pp. 1153--1163, 1989.
• 10: G. Mergen and L. Tong, "Stability and capacity of regular wireless networks," IEEE Transactions on Information Theory, vol. 51, no. 6, pp. 1938--1953, 2005.
• 11: Christina Peraki , Sergio D. Servetto, On the maximum stable throughput problem in random networks with directional antennas, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778426]
• 12: Su Yi , Yong Pei , Shivkumar Kalyanaraman, On the capacity improvement of ad hoc wireless networks using directional antennas, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778429]
• 13: S. Toumpis and A. J. Goldsmith, "Capacity regions for wireless ad hoc networks," IEEE Transactions on Wireless Communications, vol. 2, no. 4, pp. 736--748, 2003.
• 14: P. Gupta and P. R. Kumar, "Internets in the sky: The capacity of three dimensional wireless networks," Communications in Information and Systems, vol. 1, no. 1, pp. 39--49, 2001.
• 15: R. M. de Moraes, H. R. Sadjadpour, and J. J. Garcia-Luna-Aceves, "Many-to-many communication: A new approach for collaboration in manets," in Proc. of IEEE INFOCOM 2007, Anchorage, Alaska, USA., May 6-12 2007.
• 16: A. Ozgur, O. Leveque, and D. Tse, "Hierarchical cooperation achieves linear capacity scaling in ad hoc networks," in Proc. of IEEE INFOCOM 2007, Anchorage , Alaska , USA., May 6-12 2007.
• 17: M. Franceschetti, O. Dousse, D. N. Tse, and P. Thiran, "Closing the gap in the capacity of wireless networks via percolation theory," IEEE Transactions on Information Theory, vol. 53, no. 3, pp. 1009--1018, 2007.
• 18: R. Negi and A. Rajeswaran, "Capacity of power constrained ad-hoc networks," in Proc. of IEEE INFOCOM 2006, Barcelona, Spain, April 23--29 2006.
• 19: H. Zhang and J. Hou, "Capacity of wireless ad-hoc networks under ultra wide band with power constraint," in Proc. of IEEE INFOCOM 2005, Miami, FL, USA., March 13-17 2005.
• 20: R. S. Diggavi, M. Grossglauser, and D. Tse, "Even one-dimentional mobility increases ad hoc wireless capacity," in Proc. of IEEE ISIT 2001, Washington, D.C. USA., June 24-29 2002.
• 21: R. M. de Moraes, H. R. Sadjadpour, and J. J. Garcia-Luna-Aceves, "Mobility-capacity-delay trade-off in wireless ad hoc networks," Ad Hoc Networks, vol. 4, no. 5, 2006.
• 22: Philippe Jacquet , Georgios Rodolakis, Multicast Scaling Properties in Massively Dense Ad Hoc Networks, Proceedings of the 11th International Conference on Parallel and Distributed Systems - Workshops (ICPADS'05), p.93-99, July 20-22, 2005
• 23: Srinivas Shakkottai , Xin Liu , R. Srikant, The multicast capacity of large multihop wireless networks, Proceedings of the 8th ACM international symposium on Mobile ad hoc networking and computing, September 09-14, 2007, Montreal, Quebec, Canada [doi>10.1145/1288107.1288141]
• 24: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 25: Y. E. Sagduyu and A. Ephremides, "Joint scheduling and wireless network coding," in Proc. of NetCod 2005, Riva del Garda, Italy, Apr. 7 2005.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

General Terms:
Performance, Theory

Keywords:
ad hoc networks, multicast capacity, multihop wireless networks, multipacket reception, network coding, unicast capacity