The capacity and energy efficiency of wireless ad hoc networks with multi-packet reception

ABSTRACT

We address the cost incurred in increasing the transport capacity of wireless ad hoc networks over what can be attained when sources and destinations communicate over multi-hop paths and nodes can transmit or receive at most one packet at a time. We define the energy efficiency ·(n) as the bit-meters of information transferred in the network for each unit energy. We compute the energy efficiency of many different techniques aimed at increasing the capacity of wireless networks and show that, in order to achieve higher transport capacity, a lower energy efficiency must be attained. Using the physical model, we compute the throughput capacity of random wireless ad hoc networks in which nodes are endowed with multi-packet reception (MPR) capabilities. We show that λ(n)= Θ (R(n))^(1-2/α) / n^1/α) bits per second constitutes a tight upper and lower bound for the throughput of random wireless ad hoc networks, where α>2 is the path loss parameter in the physical model, n is the total number of nodes in the network, and R(n) is the MPR receiver range. In doing so, we close the gap between the lower and upper bounds for the throughput capacity of wireless networks in the physical model. Compared to the original result derived for plain routing by Gupta and Kumar, MPR achieves a capacity gain of at least Θ((log n)α-2/2α) when RR(n)= Θ(√log n/n).

REFERENCES

• 1: de Moraes, R. M., Sadjadpour, H. R., and Garcia-Luna-Aceves, J. J. Many-to-many communication: A new approach for collaboration in manets. In Proc. of IEEE INFOCOM 2007 (Anchorage , Alaska , USA., May 6-12 2007).
• 2: Abbas El Gamal , James Mammen , Balaji Prabhakar , Devavrat Shah, Optimal throughput-delay scaling in wireless networks: part I: the fluid model, IEEE/ACM Transactions on Networking (TON), v.14 n.SI, p.2568-2592, June 2006 [doi>10.1109/TIT.2006.874379]
• 3: Franceschetti, M., Dousse, O., Tse, D., and Thiran, P. Closing the gap in the capacity of wireless networks via percolation theory. IEEE Transactions on Information Theory 53, 3 (2007), 1009--1018.
• 4: J. J. Garcia-Luna-Aceves , Hamid R. Sadjadpour , Zheng Wang, Challenges: towards truly scalable ad hoc networks, Proceedings of the 13th annual ACM international conference on Mobile computing and networking, September 09-14, 2007, Montréal, Québec, Canada [doi>10.1145/1287853.1287878]
• 5: Ghez, S., Verdu, S., and Schwartz, S. Stability properties of slotted aloha with multipacket reception capability. IEEE Transactions on Automatic Control 33, 7 (1988), 640--649.
• 6: Ghez, S., Verdu, S., and Schwartz, S. Optimal decentralized control in the random access multipacket channel. IEEE Transactions on Automatic Control 34, 11 (1989), 1153--1163.
• 7: Matthias Grossglauser , David N. C. Tse, Mobility increases the capacity of ad hoc wireless networks, IEEE/ACM Transactions on Networking (TON), v.10 n.4, p.477-486, August 2002 [doi>10.1109/TNET.2002.801403]
• 8: Gupta, P., and Kumar, P. R. The capacity of wireless networks. IEEE Transactions on Information Theory 46, 2 (2000), 388--404.
• 9: Sachin Katti , Shyamnath Gollakota , Dina Katabi, Embracing wireless interference: analog network coding, Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications, August 27-31, 2007, Kyoto, Japan
• 10: Pradeep Kyasanur , Nitin H. Vaidya, Capacity of multi-channel wireless networks: impact of number of channels and interfaces, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080835]
• 11: Liu, J., Goeckel, D., and Towsley, D. 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).
• 12: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 13: Negi, R., and Rajeswaran, A. Capacity of power constrained ad-hoc networks. In Proc. of IEEE INFOCOM 2004 (Hong Kong, March 7-11 2004).
• 14: Ozgur, A., Leveque, O., and Tse, D. Hierarchical cooperation achieves optimal capacity scaling in ad hoc networks. IEEE Transactions on Information Theory 53, 10 (2007), 2549--3572.
• 15: 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]
• 16: Rodoplu, V., and Meng, T. Bits-per-joule capacity of energy-limited wireless networks. IEEE Transactions on Wireless Communications 6, 3 (2007), 857--865.
• 17: Tong, L., Zhao, Q., and Mergen, G. Multipacket reception in random access wireless networks: from signal processing to optimal medium access control. IEEE Communications Magazine 39, 11 (2001), 108--112.
• 18: Toumpis, S., and Goldsmith, A. Capacity regions for wireless ad hoc networks. IEEE Transactions on Wireless Communications 2, 4 (2003), 736--748.
• 19: Verdu, S. On channel capacity per unit cost. IEEE Transactions on Information Theory 36, 5 (1990), 1019--1030.
• 20: Sergio Verdu, Multiuser Detection, Cambridge University Press, New York, NY, 1998
• 21: 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]
• 22: Zhang, H., and Hou, J. 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).
• 23: Shengli Zhang , Soung Chang Liew , Patrick P. Lam, Hot topic: physical-layer network coding, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161129]

INDEX TERMS

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

Additional 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:
capacity, energy efficiency, multi-packet reception, throughput, wireless ad hoc networks