article

Scalability and performance evaluation of hierarchical hybrid wireless networks

Authors:

Dipankar RaychaudhuriAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 17, Issue 5

Pages 1536 - 1549

https://doi.org/10.1109/TNET.2008.2011987

Published: 01 October 2009 Publication History

Abstract

This paper considers the problem of scaling ad hoc wireless networks now being applied to urban mesh and sensor network scenarios. Previous results have shown that the inherent scaling problems of a multihop "flat" ad hoc wireless network can be improved by a "hybrid network" with an appropriate proportion of radio nodes with wired network connections. In this work, we generalize the system model to a hierarchical hybrid wireless network with three tiers of radio nodes: low-power end-user mobile nodes (MNs) at the lowest tier, higher power radio forwarding nodes (FNs) that support multihop routing at intermediate level, and wired access points (APs) at the highest level. Scalability properties of the proposed three-tier hierarchical hybrid wireless network are analyzed, leading to an identification of the proportion of FNs and APs as well as transmission range required for linear increase in end-user throughput. In particular, it is shown analytically that in a three-tier hierarchical network with n_A APs, n_F FNs, and n_M MNs, the low-tier capacity increases linearly with n_A, and the high-tier capacity increases linearly with n_A when n_A = Ω(√n_F) and n_A = O(n_F). This analytical result is validated via ns-2 simulations for an example dense network scenario, and the model is used to study scaling behavior and performance as a function of key parameters such as AP and FN node densities for different traffic patterns and bandwidth allocation at each tier of the network.

References

[1]

D. B. Johnson and D. A. Maltz, "Dynamic source routing in ad hoc wireless networks," in Mobile Computing, T. Imielinski and H. Korth, Eds. Norwell, MA: Kluwer, 1996, ch. 5, pp. 153-181.

[2]

C. E. Perkins and E. M. Royer, "Ad hoc on-demand distance vector routing," in Proc. 2nd IEEE WMCSA, Feb. 1999, pp. 90-100.

Digital Library

[3]

P. Gupta and P. R. Kumar, "The capacity of wireless networks," IEEE Trans. Inf. Theory, vol. 46, no. 2, pp. 388-404, Mar. 2000.

Digital Library

[4]

C. R. Lin and M. Gerla, "Adaptive clustering for mobile wireless networks," IEEE J. Sel. Areas Commun., vol. 15, no. 7, pp. 1265-1275, Sep. 1997.

Digital Library

[5]

A. Iwata, C.-C. Chiang, G. Pei, M. Gerla, and T.-W. Chen, "Scalable routing strategies for ad-hoc wireless networks," IEEE J. Sel. Areas Commun., vol. 17, no. 8, pp. 1369-1379, Aug. 1999.

Digital Library

[6]

E. M. Belding-Royer, "Hierarchical routing in ad hoc mobile networks," Wireless Commun. Mobile Comput., pp. 515-532, 2002.

[7]

B. Liu, Z. Liu, and D. Towsley, "On the capacity of hybrid wireless networks," in Proc. IEEE INFOCOM, Mar. 2003, vol. 2, pp. 1543-1552.

[8]

U. C. Kozat and L. Tassiulas, "Throughput capacity of random ad hoc networks with infrastructure support," in Proc. 9th ACM MobiCom, Sep. 2003, pp. 55-65.

Digital Library

[9]

S. Toumpis, "Capacity bounds for three classes of wireless networks: Asymmetric, cluster, and hybrid," in Proc. 5th ACM MobiHoc, May 2004, pp. 133-144.

Digital Library

[10]

A. Agarwal and P. R. Kumar, "Capacity bounds for ad hoc and hybrid wireless networks," Comput. Commun. Review, vol. 34, no. 3, pp. 71-81, Jul. 2004.

Digital Library

[11]

A. Zemlianov and G. de Veciana, "Capacity of ad hoc wireless networks with infrastructure support," IEEE J. Sel. Areas Commun., vol. 23, no. 3, pp. 657-667, Mar. 2005.

Digital Library

[12]

Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specification, IEEE Std. 802.11, 1999.

[13]

WCDMA for UMTS Radio Access for Third Generation Mobile Communications, H. Holma and A. Toskala, Eds. New York: Wiley, 2000.

[14]

Z. Wu and D. Raychaudhuri, "Integrated routing and MAC scheduling for single-channel wireless mesh networks," in Proc. 9th IEEE WoWMoM, Jun. 2008, pp. 1-8.

Digital Library

[15]

L. Raju, S. Ganu, B. Anepu, I. Seskar, and D. Raychaudhuri, "Beacon assisted discovery protocol (BEAD) for self-organizing hierarchical wireless ad-hoc networks," in Proc. IEEE GLOBECOM, Nov. 2004, pp. 1676-1680.

[16]

S. Zhao, Z. Wu, A. Acharya, and D. Raychaudhuri, "PARMA: A PHY/MAC aware routing metric for ad-hoc wireless networks with multi-rate radios," in Proc. 6th IEEE WoWMoM, Jun. 2005, pp. 286-292.

Digital Library

[17]

K. Fall and K. Varadhan, "The ns manual," The VINT Project, UC Berkeley, LBL, USC/ISI, and Xerox PARC, 2002 Online. Available: http://www.isi.edu/nsnam/ns/doc/ns_doc.pdf

[18]

Air Interface for Fixed Broadband Wireless Access Systems, IEEE Std. 802.16, 2001.

[19]

Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications for Low Rate Wireless Personal Area Networks (LRWPANs), IEEE Std. 802.15.4, 2003.

[20]

S. Ganu, L. Raju, B. Anepu, S. Zhao, I. Seskar, and D. Raychaudhuri, "Architecture and prototyping of an 802.11-based self-organizing hierarchical ad-hoc wireless network (SOHAN)," in Proc. PIMRC, Sep. 2004, pp. 880-884.

[21]

M. Franceschetti, O. Dousse, D. Tse, and P. Tiran, "Closing the gap in the capacity of random wireless networks," in Proc. IEEE ISIT, Jun./ Jul. 2004, p. 439.

[22]

M. Grossglauser and D. Tse, "Mobility increases the capacity of ad hoc wireless networks," IEEE/ACM Trans. Netw., vol. 10, no. 4, pp. 477-486, Aug. 2002.

Digital Library

[23]

A. Özgür, O. Lévêque, and D. Tse, "Hierarchical cooperation achieves linear capacity scaling in ad hoc networks," in Proc. IEEE INFOCOM, May 2007, pp. 382-390.

[24]

S. Zhao and D. Raychaudhuri, "Multi-tier ad hoc mesh networks with radio forwarding nodes," in Proc. IEEE GLOBECOM, Nov. 2007, pp. 1360-1364.

[25]

R. Diestel, Graph Theory, 3rd ed. Berlin, Germany: Springer, 2006.

[26]

C. E. Perkins and P. Bhagwat, "Highly dynamic destination-sequenced distance-vector routing (DSDV) for mobile computers," in Proc. ACM SIGCOMM, Aug. 1994, pp. 234-244.

Digital Library

[27]

L.-L. Xie and P. R. Kumar, "A network information theory for wireless communications: Scaling laws and optimal operation," IEEE Trans. Inf. Theory, vol. 50, no. 5, pp. 748-767, May 2004.

Digital Library

[28]

J. Li, C. Blake, D. S. J. De Couto, H. I. Lee, and R. Morris, "Capacity of ad hoc wireless networks," in Proc. ACM MobiCom, Jul. 2001, pp. 61-69.

Digital Library

[29]

T. M. Cover and J. A. Thomas, Elements of Information Theory. New York: Wiley-Interscience, 1991.

Digital Library

[30]

E. J. Duarte-Melo and M. Liu, "Data-gathering wireless sensor networks: Organization and capacity," Comput. Netw., pp. 519-537, Nov. 2003.

Digital Library

[31]

S. Zhao and D. Raychaudhuri, "On the scalability of hierarchical hybrid wireless networks," in Proc. 2006 IEEE CISS, Mar. 2006, pp. 711-716.

Cited By

Chen PReisslein M(2018)A simple analytical throughput---delay model for clustered FiWi networksPhotonic Network Communications10.1007/s11107-014-0471-129:1(78-95)Online publication date: 17-Dec-2018
https://dl.acm.org/doi/10.1007/s11107-014-0471-1
Yu YPeng YYu YRao T(2014)A new dynamic hierarchical reputation evaluation scheme for hybrid wireless mesh networksComputers and Electrical Engineering10.1016/j.compeleceng.2013.05.00540:2(663-672)Online publication date: 1-Feb-2014
https://dl.acm.org/doi/10.1016/j.compeleceng.2013.05.005
Chen DBabaei AAgrawal PNasipuri AHu YShakkottai S(2012)Reliable link lifetime-based cluster-head election in wireless ad hoc networksProceedings of the thirteenth ACM international symposium on Mobile Ad Hoc Networking and Computing10.1145/2248371.2248410(251-252)Online publication date: 11-Jun-2012
https://dl.acm.org/doi/10.1145/2248371.2248410

Index Terms

Scalability and performance evaluation of hierarchical hybrid wireless networks

Recommendations

Dynamic multi-hop clustering for mobile hybrid wireless networks
ICUIMC '08: Proceedings of the 2nd international conference on Ubiquitous information management and communication

In mobile wireless networks communication is often improved by sending messages along a stable backbone of more reliable communication paths. Building such a backbone requires efficient clustering algorithms which aggregate network nodes into logical ...
Landmark routing in ad hoc networks with mobile backbones
Special issue on Routing in mobile and wireless ad hoc networks

A mobile ad hoc network is usually assumed to be homogeneous, where each mobile node shares the same radio capacity. However, a homogeneous ad hoc network suffers from poor scalability. Recent research has demonstrated its performance bottleneck through ...
Comparison of reactive and proactive routing protocols for different mobility conditions in WSN
ICCCS '11: Proceedings of the 2011 International Conference on Communication, Computing & Security

Ad hoc networks prove to be challenging networks for communication due to its resource constrained nature and frequent changes in the network topology. Though a lot of research has been going on in the various parts of the world for optimization of ...

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 17, Issue 5

October 2009

339 pages

ISSN:1063-6692

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 October 2009

Revised: 17 December 2007

Received: 26 March 2007

Published in TON Volume 17, Issue 5

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
375
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Chen PReisslein M(2018)A simple analytical throughput---delay model for clustered FiWi networksPhotonic Network Communications10.1007/s11107-014-0471-129:1(78-95)Online publication date: 17-Dec-2018
https://dl.acm.org/doi/10.1007/s11107-014-0471-1
Yu YPeng YYu YRao T(2014)A new dynamic hierarchical reputation evaluation scheme for hybrid wireless mesh networksComputers and Electrical Engineering10.1016/j.compeleceng.2013.05.00540:2(663-672)Online publication date: 1-Feb-2014
https://dl.acm.org/doi/10.1016/j.compeleceng.2013.05.005
Chen DBabaei AAgrawal PNasipuri AHu YShakkottai S(2012)Reliable link lifetime-based cluster-head election in wireless ad hoc networksProceedings of the thirteenth ACM international symposium on Mobile Ad Hoc Networking and Computing10.1145/2248371.2248410(251-252)Online publication date: 11-Jun-2012
https://dl.acm.org/doi/10.1145/2248371.2248410

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents