›› 2012, Vol. ›› Issue (2): 328-340.doi: 10.1007/s11390-012-1226-z

Special Issue: Computer Networks and Distributed Computing

• Computer Network • Previous Articles     Next Articles

Delay and Capacity Trade-offs in Mobile Wireless Networks with Infrastructure Support

Zhuo Li1 (李卓), Wen-Zhong Li1 (李文中), Member, CCF, ACM, IEEE, Song Guo2 (郭嵩), Senior Member, IEEE, Member, ACM, Sang-Lu Lu1,* (陆桑璐), Senior Member, CCF, Member, ACM, IEEE, and Dao-Xu Chen1 (陈道蓄), Senior Member, CCF, Member, ACM, IEEE   

  1. 1. State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210046, China;
    2. School of Computer Science and Engineering, The University of Aizu, Aizu-Wakamatsu, 965-8580, Japan
  • Received:2011-09-20 Revised:2012-01-14 Online:2012-03-05 Published:2012-03-05
  • Supported by:

    This work is supported by the National Natural Science Foundation of China under Grant Nos. 61073028, 61021062, 60803111, the National Basic Research 973 Program of China under Grant No. 2009CB320705, the Key Project of the Research Program of Jiangsu Province of China under Grant No. BE2010179, and the Natural Science Foundation of Jiangsu Province of China under Grant No. BK2009100.

In this paper, we investigate the trade-offs between delay and capacity in mobile wireless networks with infrastructure support. We consider three different mobility models, independent and identically distributed (i.i.d) mobility model, random walk mobility model with constant speed and Lévy flight mobility model. For i.i.d mobility model and random walk mobility model with the speed Θ((1/√n)), we get the theoretical results of the average packet delay when capacity is Θ(1), Θ((1/√n)) individually, where n is the number of nodes. We find that the optimal average packet delay is achieved when capacity  where K is the number of gateways. It is proved that average packet delay D(n) divided by capacity λ(n) is bounded below by (n/K·W) . When ω(√n) ≤ K < n, the critical average delay for capacity compared with static hybrid wireless networks is Θ((K2/n) ). Lévy flight mobility model is based on human mobility and is more sophisticated. For the model with parameter α, it is found that (D(n)/λ(n)) > O(n((1-η)·(α+1)/2) ln n) when K = O(nη) (0 ≤ η < 1). We also prove that when ω(√n) ≤ K < n, the critical average delay is Θ(n(α-1/2)·K).

[1] Liu C, Wu J. Scalable routing in cyclic mobile networks.IEEE Transactions on Parallel and Distributed Systems,2009, 20(9): 1325-1338.

[2] Chen X, Shen J, Groves T, Wu J. Probability delegation for-warding in delay tolerant networks. In Proc. the 18th IC-CCN, San Francisco, USA, Aug. 3-6, 2009, pp.1-6.

[3] Zhu J Q, Liu M, Cao J N, Chen G H, Gong H G, XuF L. CED: A community-based event delivery protocol inpublish/subscribe systems for delay tolerant sensor network(DTSN). In Proc. ICPP, Vienna, Austria, Sept. 22-25, 2009,pp.58-65.

[4] Han B, Hui P, Kumar V S A, Marathe M V, Pei G H, Srini-vasan A. Cellular traffic o?oading through opportunistic com-munications: A case study. In Proc. the 5th CHANTS,Chicago, USA, Sept. 24, 2010, pp.31-38.

[5] Lee K, Rhee I, Lee J, Yi Y, Chong S. Mobile data o?oading:How much can WiFi deliver? In Proc. CoNEXT, Philadel-phia, USA, Nov. 30-Dec. 3, 2010, pp.425-426.

[6] Huang W T, Wang X B, Zhang Q. Capacity scaling in mobilewireless ad hoc network with infrastructure support. In Proc.the 30th ICDCS, Genoa, Italy, June 21-25, 2010, pp.848-857.

[7] Sharma G, Mazumdar R, Shroff N. Delay and capacitytrade-offs in mobile ad hoc networks: A global perspective.IEEE/ACM Trans. Networking, 2007, 15(5): 981-992.

[8] Rhee I, Shin M, Hong S, Lee K, Chong S. On the levy-walknature of human mobility. IEEE/ACM Transactions on Net-working, 2011, 19(3): 630-643.

[9] Guptu P, Kumar P R. The capacity of wireless networks.IEEE Trans. Information Theory, 2000, 46(2): 388-404.

[10] Grossglauser M, Tse D N C. Mobility increases the capacityof ad hoc wireless networks. IEEE/ACM Transactions onNetworking, 2002, 10(4): 477-486.

[11] Bansal N, Liu Z. Capacity, delay and mobility in wireless ad-hoc networks. In Proc. INFOCOM, San Francisco, USA,Mar. 30-April 4, 2003, pp.1553-1563.

[12] Neely M J, Modiano E. Capacity and delay tradeoffs for adhoc mobile networks. IEEE Transactions on InformationTheory, 2005, 51(6): 1917-1937.

[13] Toumpis S, Goldsmith A J. Large wireless networks underfading, mobility, and delay constraints. In Proc. INFOCOM,Hong Kong, China, Mar. 7-11, 2004, pp.609-619.

[14] Lin X J, Shrott N. Towards achieving the maximum capacityin large mobile wireless networks under delay constraints. J.Commun. and Networks, 2004, 6(4): 352-361.

[15] Liu J J, Jiang X H, Nishiyama H, Kato N. Delay and ca-pacity in ad hoc mobile networks with f-cast relay algo-rithms. IEEE Transactions on Wireless Communications,2011, 10(8): 2738-2751.

[16] Gamal A, Mammen J, Probhakar B, Shah D. Throughput-delay trade-off in wireless networks. In Proc. INFOCOM,Hong Kong, China, Mar. 7-11, 2004, pp.464-475.

[17] Lin X J, Sharma G, Mazumdar R R, Shroff N B. Degeneratedelay-capacity tradeoffs in ad-hoc networks with Brownianmobility. IEEE Transactions on Information Theory, 2006,52(6): 2777-2784.

[18] El Gamal A, Mammen J, Prabhakar B, Shah D. Optimalthroughput-delay scaling in wireless networks { part I: Thefluid model. IEEE Transactions on Information Theory,2006, 52(6): 2568-2592.

[19] El Gamal A, Mammen J, Prabhakar B, Shah D. Opti-mal throughput-delay scaling in wireless networks { part II:Constant-size packets. IEEE Transactions on InformationTheory, 2006, 52(11): 5111-5116.

[20] Mammen J, Shah D. Throughput and delay in random wire-less networks with restricted mobility. IEEE Transactions onInformation Theory, 2007, 53(3): 1108-1116.

[21] Ying L, Yang S C, Srikant R. Optimal delay { throughputtrade-offs in mobile ad hoc networks. IEEE Transactions onInformation Theory, 2008, 54(9): 4119-4143.

[22] Garetto M, Giaccone P, Leonardi E. Capacity scaling in adhoc networks with heterogeneous mobile nodes: The super-critical regime. IEEE/ACM Transactions on Networking,2009, 17(5): 1522-1535.

[23] Garetto M, Giaccone P, Leonardi E. Capacity scaling in adhoc networks with heterogeneous mobile nodes: The subcri-tical regime. IEEE/ACM Transactions on Networking, 2009,17(6): 1888-1901.

[24] Garetto M, Leonardi E. Restricted mobility improves delay-throughput trade-offs in mobile ad hoc networks. IEEE Tran-sactions on Information Theory, 2010, 56(10): 5016-5029.

[25] Tournoux P U, Leguay J, Benbadis F, Conan V, de AmorimMD, Whitbeck J. The accordion phenomenon: Analysis, charac-terization, and impact on DTN routing. In Proc. INFOCOM,Rio de Janeiro, Brazil, April 19-25, 2009, pp.1116-1124.

[26] Ciullo D, Martina V, Garetto M, Leonardi E. Impact of cor-related mobility on delay-throughput performance in mobilead-hoc networks. In Proc. INFOCOM, San Diego, USA,Mar. 15-19, 2010, pp.1-9.

[27] Wang C, Li X Y, Tang S J, Jiang C J, Liu Y H. Capacityand delay in mobile ad hoc networks under Gaussian channelmodel. ACM SIGMOBILE Mob. Comput. Commun. Rev.,2010, 14(3): 22{24.

[28] Lee Y, Kim Y, Chong S, Rhee I, Yi Y. Delay-capacity trade-offs for mobile networks with l?evy walks and l?evy flights.In Proc. INFOCOM, Shanghai, China, April 10-15, 2011,pp.3128-3136.

[29] Li X Y. Multicast capacity of wireless ad hoc networks.IEEE/ACM Trans. Networking, 2009, 17(3): 950-961.

[30] Keshavarz-Haddad A, Ribeiro V, Riedi R. Broadcast capacityin multihop wireless networks. In Proc. the 12th MobiCom,Los Angeles, USA, Sept. 24-29, 2006, pp.239-250.

[31] Tavli B. Broadcast capacity of wireless networks. IEEE Com-munications Letters, 2006, 10(2): 68-69.

[32] Li X Y, Liu Y H, Li S, Tang S J. Multicast capacity of wirelessad hoc networks under Gaussian channel model. IEEE/ACMTransactions on Networking, 2010, 18(4): 1145-1157.

[33] Wang X B, HuangWT,Wang S X, Zhang J B, Hu C H. Delayand capacity tradeoff analysis for MotionCast. IEEE/ACMTransactions on Networking, 2011, 19(5): 1354-1367.

[34] Wang Y, Chu X Y, Wang X B, Cheng Y. Optimal multicastcapacity and delay tradeoffs in MANETs: A global perspec-tive. In Proc. INFOCOM, Shanghai, China, April 10-15,2011, pp.640-648.

[35] Wang Q S,Wang X B, Lin X J. Mobility increases the connec-tivity of K-hop clustered wireless networks. In Proc. the 15thMobiCom, Beijing, China, Sept. 20-25, 2009, pp.121-132.

[36] Lee K, Hong S, Kim S J, Rhee I, Chong S. Slaw: A new mo-bility model for human walks. In Proc. INFOCOM, Rio deJaneiro, Brazil, April 19-25, 2009, pp.855-863.

[37] Zemlianov A, Gustavo de V. Capacity of ad hoc wireless net-works with infrastructure support. IEEE Journal on SelectedAreas in Communications, 2005, 23(3): 657-667.
No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Wang Xuan; Lü Zhimin; Tang Yuhai; Xiang Yang;. A High Resolution Chinese Character Generator[J]. , 1986, 1(2): 1 -14 .
[3] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[4] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[5] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[6] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[7] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[8] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[9] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[10] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved