Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Introduction Read chapter Read first chapter

2014 | OriginalPaper | Chapter

2. Capacity Scaling Laws of Wireless Networks

Authors : Ning Lu, Xuemin (Sherman) Shen

Published in: Capacity Analysis of Vehicular Communication Networks

Publisher: Springer New York

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The capacity scaling law of wireless networks has been considered as one of the most fundamental issues. In this chapter, we aim at providing a comprehensive overview of the development in the area of scaling laws for throughput capacity in wireless networks. We begin with background information on the notion of throughput capacity of random networks. Based on the benchmark random network model, we then elaborate the advanced strategies adopted to improve the throughput capacity, and other factors that affect the scaling laws. We also present the fundamental tradeoffs between throughput capacity, delay, and mobility. Finally, the capacity for hybrid wireless networks are surveyed, in which there are at least two types of nodes functioning differently, e.g., normal nodes and infrastructure nodes.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Introduction
next chapter Unicast Capacity of Vehicular Networks with Socialized Mobility
Footnotes
1
Since studies of throughput capacity focus on the scaling behavior instead of a specific value, the order notation is involved to describe how capacity scales with the number of nodes N. Specifically, the following Knuth’s notation is used throughout all the papers on scaling laws: given nonnegative functions f 1(n) and f 2(n), \(f_{1}(n) = O(f_{2}(n))\) means f 1(n) is asymptotically upper bounded by f 2(n); \(f_{1}(n) =\varOmega (f_{2}(n))\) means f 1(n) is asymptotically lower bounded by f 2(n); and \(f_{1}(n) =\varTheta (f_{2}(n))\) means f 1(n) is asymptotically tight bounded by f 2(n); \(f_{1}(n) = \omega (f_{2}(n))\) means f 1(n) is asymptotically dominant with respect to f 2(n); \(f_{1}(n) = o(f_{2}(n))\) means f 1(n) is asymptotically negligible with respect to f 2(n).
 
2
Redundancy of the packet means extra copies of the original packet, which are issued by the source node.
 
3
The throughput is achievable in static random ad hoc networks.
 
Literature
22.
23.
A. Goldsmith, M. Effros, R. Koetter, M. Médard, A. Ozdaglar, L. Zheng, Beyond shannon: the quest for fundamental performance limits of wireless ad hoc networks. IEEE Commun. Mag. 49(5), 195–205 (2011)CrossRef
31.
T. Cover, J. Thomas, J. Wiley et al., Elements of Information Theory, vol. 306 (Wiley Online Library, John Wiley & Sons, Inc., Hoboken, New Jersey 1991)
32.
M. Franceschetti, O. Dousse, D. Tse, P. Thiran, Closing the gap in the capacity of wireless networks via percolation theory. IEEE Trans. Inf. Theory 53(3), 1009–1018 (2007)MathSciNetCrossRef
33.
S. Yi, Y. Pei, S. Kalyanaraman, On the capacity improvement of ad hoc wireless networks using directional antennas, in Proceedings of ACM MobiHoc, Annapolis, 2003
34.
C. Peraki, S. Servetto, On the maximum stable throughput problem in random networks with directional antennas, in Proceedings of ACM MobiHoc, Annapolis, 2003
35.
H. Sadjadpour, Z. Wang, J. Garcia-Luna-Aceves, The capacity of wireless ad hoc networks with multi-packet reception. IEEE Trans. Commun. 58(2), 600–610 (2010)CrossRef
36.
J. Garcia-Luna-Aceves, H. Sadjadpour, Z. Wang, Challenges: towards truly scalable ad hoc networks, in Proceedings of ACM MobiCom, Montreal, 2007
38.
Z. Wang, H. Sadjadpour, J. Garcia-Luna-Aceves, Fundamental limits of information dissemination in wireless ad hoc networks–part II: multi-packet reception. IEEE Trans. Wirel. Commun. 10(3), 803–813 (2011)CrossRef
39.
S. Aeron, V. Saligrama, Wireless ad hoc networks: strategies and scaling laws for the fixed SNR regime. IEEE Trans. Inf. Theory 53(6), 2044–2059 (2007)MathSciNetCrossRef
40.
A. Ozgur, O. Lévêque, D. Tse, Hierarchical cooperation achieves optimal capacity scaling in ad hoc networks. IEEE Trans. Inf. Theory 53(10), 3549–3572 (2007)CrossRef
41.
J. Ghaderi, L. Xie, X. Shen, Hierarchical cooperation in ad hoc networks: optimal clustering and achievable throughput. IEEE Trans. Inf. Theory 55(8), 3425–3436 (2009)MathSciNetCrossRef
42.
U. Niesen, P. Gupta, D. Shah, On capacity scaling in arbitrary wireless networks. IEEE Trans. Inf. Theory 55(9), 3959–3982 (2009)MathSciNetCrossRef
43.
M. Franceschetti, M. Migliore, P. Minero, The capacity of wireless networks: information-theoretic and physical limits. IEEE Trans. Inf. Theory 55(8), 3413–3424 (2009)MathSciNetCrossRef
44.
S. Lee, S. Chung, Capacity scaling of wireless ad hoc networks: Shannon meets Maxwell. IEEE Trans. Inf. Theory 58(3), 1702–1715 (2012)MathSciNetCrossRef
45.
K. Lu, S. Fu, Y. Qian, H. Chen, On capacity of random wireless networks with physical-layer network coding. IEEE J. Sel. Areas Commun. 27(5), 763–772 (2009)CrossRef
46.
J. Liu, D. Goeckel, D. Towsley, The throughput order of ad hoc networks employing network coding and broadcasting, in IEEE Proceedings of MILCOM, Washington, DC, Oct 2006
49.
J. Liu, D. Goeckel, D. Towsley, Bounds on the throughput gain of network coding in unicast and multicast wireless networks. IEEE J. Sel. Areas Commun. 27(5), 582–592 (2009)CrossRef
50.
R. Negi, A. Rajeswaran, Capacity of power constrained ad-hoc networks, in IEEE Proceedings of INFOCOM, Hong Kong, Mar 2004
51.
X. Tang, Y. Hua, Capacity of ultra-wideband power-constrained ad hoc networks. IEEE Trans. Inf. Theory 54(2), 916–920 (2008)MathSciNetCrossRef
52.
H. Zhang, J. Hou, Capacity of wireless ad-hoc networks under ultra wide band with power constraint, in IEEE Proceedings of INFOCOM, Miami, Mar 2005
53.
M. Grossglauser, D. Tse, Mobility increases the capacity of ad hoc wireless networks. IEEE/ACM Trans. Netw. 10(4), 477–486 (2002)CrossRef
54.
S. Diggavi, M. Grossglauser, D. Tse, Even one-dimensional mobility increases the capacity of wireless networks. IEEE Trans. Inf. Theory 51(11), 3947–3954 (2005)MathSciNetCrossRef
55.
S. Jafar, Too much mobility limits the capacity of wireless ad hoc networks. IEEE Trans. Inf. Theory 51(11), 3954–3965 (2005)MathSciNetCrossRef
56.
P. Kyasanur, N. Vaidya, Capacity of multi-channel wireless networks: impact of number of channels and interfaces, in Proceedings of ACM MobiCom, Cologne, 2005
57.
P. Kyasanur, N. Vaidya, Capacity of multichannel wireless networks under the protocol model. IEEE/ACM Trans. Netw. 17(2), 515–527 (2009)CrossRef
58.
M. Kodialam, T. Nandagopal, Characterizing the capacity region in multi-radio multi-channel wireless mesh networks, in Proceedings of ACM MobiCom, Cologne, 2005
59.
S. Toumpis, A. Goldsmith, Large wireless networks under fading, mobility, and delay constraints, in Proceeding of IEEE INFOCOM, Hongkong, Mar 2004
60.
M. Ebrahimi, M. Maddah-Ali, A. Khandani, Throughput scaling laws for wireless networks with fading channels. IEEE Trans. Inf. Theory 53(11), 4250–4254 (2007)MathSciNetCrossRef
61.
R. Gowaikar, B. Hochwald, B. Hassibi, Communication over a wireless network with random connections. IEEE Trans. Inf. Theory 52(7), 2857–2871 (2006)MathSciNetCrossRef
62.
S. Cui, A. Haimovich, O. Somekh, H. Poor, S. Shamai, Throughput scaling of wireless networks with random connections. IEEE Trans. Inf. Theory 56(8), 3793–3806 (2010)MathSciNetCrossRef
63.
R. Gowaikar, B. Hassibi, Achievable throughput in two-scale wireless networks. IEEE J. Sel. Areas Commun. 27(7), 1169–1179 (2009)CrossRef
64.
R. Jaber, J. Andrews, A lower bound on the capacity of wireless erasure networks. IEEE Trans. Inf. Theory 57(10), 6502–6513 (2011)MathSciNetCrossRef
65.
C. Hu, X. Wang, Z. Yang, J. Zhang, Y. Xu, X. Gao, A geometry study on the capacity of wireless networks via percolation. IEEE Trans. Commun. 58(10), 2916–2925 (2010)CrossRef
66.
P. Li, M. Pan, Y. Fang, Capacity bounds of three-dimensional wireless ad hoc networks. IEEE/ACM Trans. Netw. 20(4), 1304–1315 (2012)CrossRef
67.
A. Keshavarz-Haddad, V. Ribeiro, R. Riedi, Broadcast capacity in multihop wireless networks, in Proceedings of ACM MobiCom, Los Angeles, 2006
69.
X. Li, J. Zhao, Y. Wu, S. Tang, X. Xu, X. Mao, Broadcast capacity for wireless ad hoc networks, in Proceedings of IEEE MASS, Atlanta, Sept 2008
70.
S. Li, Y. Liu, X. Li, Capacity of large scale wireless networks under gaussian channel model, in Proceedings of ACM MobiCom, San Francisco, 2008
76.
X. Wang, L. Fu, C. Hu, Multicast performance with hierarchical cooperation. IEEE/ACM Trans. Netw. 20(3), 917–930 (2012)CrossRef
77.
78.
Z. Wang, H. Sadjadpour, J. Garcia-Luna-Aceves, A unifying perspective on the capacity of wireless ad hoc networks, in Proceedings of IEEE INFOCOM, Phoenix, Apr 2008
79.
G. Sharma, R. Mazumdar, N. Shroff, Delay and capacity trade-offs in mobile ad hoc networks: a global perspective. IEEE/ACM Trans. Netw. 15(5), 981–992 (2007)CrossRef
80.
D. Ciullo, V. Martina, M. Garetto, E. Leonardi, Impact of correlated mobility on delay-throughput performance in mobile ad-hoc networks, in Proceedings of IEEE INFOCOM, San Diego, Mar 2010
81.
S. Ross, Introduction to Probability Models (Academic, Academic Press, Burlington, MA, USA 2009)
82.
K. Lee, Y. Kim, S. Chong, I. Rhee, Y. Yi, Delay-capacity tradeoffs for mobile networks with Lévy walks and Lévy flights, in Proceedings of IEEE INFOCOM, San Diego, Mar 2010
83.
I. Rhee, M. Shin, S. Hong, K. Lee, S. Kim, S. Chong, On the Levy-walk nature of human mobility. IEEE/ACM Trans. Netw. 19(3), 630–643 (2011)CrossRef
84.
M. Neely, E. Modiano, Capacity and delay tradeoffs for ad hoc mobile networks. IEEE Trans. Inf. Theory 51(6), 1917–1937 (2005)MathSciNetCrossRef
85.
L. Ying, S. Yang, R. Srikant, Optimal delay–throughput tradeoffs in mobile ad hoc networks. IEEE Trans. Inf. Theory 54(9), 4119–4143 (2008)MathSciNetCrossRef
86.
X. Lin, N. Shroff, The fundamental capacity-delay tradeoff in large mobile ad hoc networks, in Proceedings of 3rd Annual Mediterranean Ad Hoc Networking Workshop, Bodrum, June 2004
87.
A. El Gamal, J. Mammen, B. Prabhakar, D. Shah, Optimal throughput-delay scaling in wireless networks-part I: the fluid model. IEEE Trans. Inf. Theory 52(6), 2568–2592 (2006)CrossRef
88.
X. Lin, G. Sharma, R. Mazumdar, N. Shroff, Degenerate delay-capacity tradeoffs in ad-hoc networks with brownian mobility. IEEE Trans. Inf. Theory 52(6), 2777–2784 (2006)MathSciNetCrossRef
89.
G. Sharma, R. Mazumdar, Scaling laws for capacity and delay in wireless ad hoc networks with random mobility, in Proceedings of IEEE ICC, Paris, June 2004
90.
P. Li, Y. Fang, J. Li, Throughput, delay, and mobility in wireless ad hoc networks, in Proceedings of IEEE INFOCOM, San Diego, Mar 2010
91.
M. Garetto, P. Giaccone, E. Leonardi, On the capacity of ad hoc wireless networks under general node mobility, in Proceedings of IEEE INFOCOM, Anchorage, May 2007
93.
M. Garetto, P. Giaccone, E. Leonardi, Capacity scaling in ad hoc networks with heterogeneous mobile nodes: the super-critical regime. IEEE/ACM Trans. Netw. 17(5), 1522–1535 (2009)CrossRef
94.
M. Garetto, P. Giaccone, E. Leonardi, Capacity scaling in ad hoc networks with heterogeneous mobile nodes: the subcritical regime. IEEE/ACM Trans. Netw. 17(6), 1888–1901 (2009)CrossRef
95.
M. Garetto, E. Leonardi, Restricted mobility improves delay-throughput tradeoffs in mobile ad hoc networks. IEEE Trans. Inf. Theory 56(10), 5016–5029 (2010)MathSciNetCrossRef
96.
A. Ozgur, O. Lévêque, Throughput-delay tradeoff for hierarchical cooperation in ad hoc wireless networks. IEEE Trans. Inf. Theory 56(3), 1369–1377 (2010)CrossRef
97.
C. Comaniciu, H. Poor, On the capacity of mobile ad hoc networks with delay constraints. IEEE Trans. Wirel. Commun. 5(8), 2061–2071 (2006)CrossRef
98.
B. Liu, Z. Liu, D. Towsley, On the capacity of hybrid wireless networks, in Proceedings of IEEE INFOCOM, San Francisco, Mar 2003
99.
U. Kozat, L. Tassiulas, Throughput capacity of random ad hoc networks with infrastructure support, in Proceedings of ACM MobiCom, San Diego, 2003, pp. 55–65
100.
S. Toumpis, Capacity bounds for three classes of wireless networks: asymmetric, cluster, and hybrid, in Proceedings of ACM MobiHoc, Tokyo, 2004, pp. 133–144
101.
A. Zemlianov, G. De Veciana, Capacity of ad hoc wireless networks with infrastructure support. IEEE J. Sel. Areas Commun. 23(3), 657–667 (2005)CrossRef
102.
B. Liu, P. Thiran, D. Towsley, Capacity of a wireless ad hoc network with infrastructure, in Proceedings of the 8th ACM International Symposium on mobile Ad Hoc Networking and Computing, Montréal (ACM, 2007), pp. 239–246
103.
P. Li, Y. Fang, Impacts of topology and traffic pattern on capacity of hybrid wireless networks. IEEE Trans. Mobile Comput. 8(12), 1585–1595 (2009)CrossRef
104.
D. Shila, Y. Cheng, T. Anjali, Throughput and delay analysis of hybrid wireless networks with multi-hop uplinks, in Proceedings of IEEE INFOCOM, Shanghai, Apr 2011
105.
P. Li, C. Zhang, Y. Fang, Capacity and delay of hybrid wireless broadband access networks. IEEE J. Sel. Areas Commun. 27(2), 117–125 (2009)CrossRef
106.
G. Zhang, Y. Xu, X. Wang, M. Guizani, Capacity of hybrid wireless networks with directional antenna and delay constraint. IEEE Trans. Commun. 58(7), 2097–2106 (2010)CrossRef
107.
W. Shin, S. Jeon, N. Devroye, M. Vu, S. Chung, Y. Lee, V. Tarokh, Improved capacity scaling in wireless networks with infrastructure. IEEE Trans. Inf. Theory 57(8), 5088–5102 (2011)MathSciNetCrossRef
108.
W. Huang, X. Wang, Q. Zhang, Capacity scaling in mobile wireless ad hoc network with infrastructure support, in Proceedings of IEEE ICDCS, Genoa, June 2010
109.
P. Li, Y. Fang, The capacity of heterogeneous wireless networks, in Proceedings of IEEE INFOCOM, San Diego, Mar 2010
110.
P. Zhou, X. Wang, R. Rao, Asymptotic capacity of infrastructure wireless mesh networks. IEEE Trans. Mobile Comput. 7(8), 1011–1024 (2008)CrossRef
111.
L. Law, K. Pelechrinis, S. Krishnamurthy, M. Faloutsos, Downlink capacity of hybrid cellular ad hoc networks. IEEE/ACM Trans. Netw. 18(1), 243–256 (2010)CrossRef
112.
P. Li, X. Huang, Y. Fang, Capacity scaling of multihop cellular networks, in Proceedings of IEEE INFOCOM, Shanghai, Apr 2011
113.
N. Zhang, N. Lu, R. Lu, J.W. Mark, X. Shen, Energy-efficient and trust-aware cooperation in cognitive radio networks, in Proceedings of IEEE ICC, Ottawa, June 2012
114.
M. Vu, V. Tarokh, Scaling laws of single-hop cognitive networks. IEEE Trans. Wirel. Commun. 8(8), 4089–4097 (2009)CrossRef
115.
S. Jeon, N. Devroye, M. Vu, S. Chung, V. Tarokh, Cognitive networks achieve throughput scaling of a homogeneous network. IEEE Trans. Inf. Theory 57(8), 5103–5115 (2011)MathSciNetCrossRef
116.
C. Yin, L. Gao, S. Cui, Scaling laws for overlaid wireless networks: a cognitive radio network versus a primary network. IEEE/ACM Trans. Netw. 18(4), 1317–1329 (2010)CrossRef
117.
W. Huang, X. Wang, Capacity scaling of general cognitive networks. IEEE/ACM Trans. Netw. to appear
118.
Y. Li, X. Wang, X. Tian, X. Liu, Scaling laws for cognitive radio network with heterogeneous mobile secondary users, in Proceedings of IEEE INFOCOM, Orlando, Mar 2012
Metadata
Title
Capacity Scaling Laws of Wireless Networks
Authors
Ning Lu
Xuemin (Sherman) Shen
Copyright Year
2014
Publisher
Springer New York
Book
Capacity Analysis of Vehicular Communication Networks

Print ISBN: 978-1-4614-8396-0

Electronic ISBN: 978-1-4614-8397-7

Copyright Year: 2014

DOI
https://doi.org/10.1007/978-1-4614-8397-7_2

Premium Partner

    Image Credits