Theoretical analysis for tree-like networks using random geometry

Author(s): S.Y. Chang ; H.-C. Wu ; Y. Wu ; H.-C. Chao
DOI: 10.1049/iet-com.2011.0025

For access to this article, please select a purchase option:

Buy article PDF

Buy Knowledge Pack

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership

Recommend Title Publication to library

IET Communications — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

Author(s): S.Y. Chang ¹ ; H.-C. Wu ² ; Y. Wu ³ ; H.-C. Chao ⁴
- Affiliations: 1: Department of Computer Science, National Tsing Hua University, Taiwan
  2: Department of Electrical and Computer Engineering, Louisiana State University, Baton Rouge, USA
  3: Department of Television Networks and Transmission, Communications Research Centre, Ottawa, Canada
  4: Department of Electrical Engineering, National Dong Hwa University, Hualien, Taiwan
Source: Volume 5, Issue 15, 14 October 2011, p. 2167 – 2176
DOI: 10.1049/iet-com.2011.0025 , Print ISSN 1751-8628, Online ISSN 1751-8636

Among various network topologies, tree-like networks, also known as hierarchical networks are proposed to decrease the overhead of the routing table especially for the situation involving many network nodes. Usually, the routing table size and the routing complexity are the two crucial concerns in designing a large network. Although there have been various algorithms to optimise the routing strategies for the hierarchical networks, hardly exists any work in studying and evaluating the routing table size and the routing complexity rigorously in the statistical sense. In this study, the authors generalise a new mathematical framework by applying the point process in random geometry. The new framework proposed by the authors leads to the explicit statistical measures of the routing table size and the routing complexity, which can be specified as the functions of the hierarchical network parameters including the number of the hierarchical levels and the cluster population for each hierarchical level. After the relationship between the network topology and these two network performance measures (routing complexity and routing table size) is established, a cluster-population optimisation method for hierarchical networks is presented. The simulation results are also provided to demonstrate the advantage of a hierarchical network over the associated conventional network without hierarchy.

References

1. 1)
  - A.E. Baratz , J.M. Jaffe . Establishing virtual circuits in large computer networks. Computer Networks and ISDN Systems , 1 , 27 - 37
2. 2)
  - J.M. McQuillan . (1974) Adaptive routing algorithms for distributed computer networks.
3. 3)
  - L. Li , Y. Zhu , Y. Yu . Link scheduling and data forwarding in wireless sensor networks of long chains tree topology. IET Commun. , 297 - 300
4. 4)
  - Y.-S. Yen , S. Hong , R.-S. Chang , H.-C. Chao . Controlled deployments for wireless sensor networks. IET Commun. , 5 , 820 - 829
5. 5)
  - L. Kleinrock , F. Kamoun . Hierarchical routing for large networks: performance evaluation and optimization, computer networks. Comput. Netw.
6. 6)
  - J.J. Garcia-Luna-Aceves , S. Murthy . A path finding algorithm for loop-free routing. IEEE/ACM Trans. Netw. , 1 , 148 - 160
7. 7)
  - E.N. Gilbert . Random subdivisions of space into crystals. Ann. Math. Stat. , 3 , 958 - 972
8. 8)
  - V.S. Alagar . The distribution of the distance between random points. J. Appl. Probab. , 3 , 558 - 566
9. 9)
  - Houstic, C.E., Leon, B.J.: `An adaptive routing algorithm for large store-and-forward computer communication networks', Phase Report, October 1977.
10. 10)
  - E. Sakhaee , A. Jamalipour . Stable clustering and communications in pseudolinear highly mobile ad hoc networks. IEEE Trans. Veh. Technol. , 6 , 3769 - 3777
11. 11)
  - R. Hekmat . (2006) Ad-hoc networks: fundamental properties and network topologies.
12. 12)
  - Lauer, G.S.: `Hierarchical routing design for suran', Proc. IEEE ICC, June 1986, p. 93–102.
13. 13)
  - Ramamoorthy, C.V., Tsai, W.T.: `An adaptive hierarchical routing algorithm', Proc. IEEE COMPSAC, November 1983, p. 93–104.
14. 14)
  - D. Stoyan , W. Kendall , J. Mecke . (1995) Stochastic geometry and its applications.
15. 15)
  - S.P. Chung , M.T. Li . Performance evaluation of hierarchical cellular cdma networks with soft handoff queueing. IEEE Trans. Veh. Technol. , 2 , 652 - 672
16. 16)
  - W.T. Tsai , C.V. Ramamoorthy , W.K. Tsai , O. Nishiguchi . An adaptive hierarchical routing protocol. IEEE/ACM Trans. Comput. , 8 , 1059 - 1075
17. 17)
  - J.L. Rougier , D. Kofman , A. Gravey . Optimization of hierarchical routing protocols. Perform. Eval. , 3 , 227 - 245
18. 18)
  - J. Sucec , I. Marsic . Hierarchical routing overhead in mobile ad hoc networks. IEEE Trans. Mob. Comput. , 1 , 46 - 56
19. 19)
  - F. Kamoun , L. Kleinrock . Stochastic performance evaluation of hierarchical routing for large network. Comput. Netw. , 337 - 353
20. 20)
  - J.L. Meijering . Interface area, edge length, and number of vertices in crystal aggregates with random nucleation. Philips Research Reprint , 270 - 290
21. 21)
  - Murthy, S., Garcia-Luna-Aceves, J.J.: `Loop-free internet routing using hierarchical routing trees', Proc. IEEE INFOCOM, April 1997, p. 7–11.
22. 22)
  - J. Moller . Random tessellation in . Adv. Appl. Probab. , 37 - 73
23. 23)
  - M.G. Kendall , P.A.P. Moran . (1962) Geometric probability.
24. 24)
  - S.G. Foss , S.A. Zuyev . On a certain segment process with Voronoi clustering. INRIA, Rapport de Recherche , 1 - 17
25. 25)
  - Susec, J., Marsic, I.: `Clustering overhead for hierarchical routing in mobile ad hoc networks', Proc. IEEE INFOCOM, April 2002, p. 1698–1706.
26. 26)
  - Y.S. Yen , R.S. Chang , H.C. Chao . Flooding-limited for multi-constrained quality-of-service routing protocol in mobile ad hoc networks. IET Commun. , 7 , 972 - 981
27. 27)
  - Behrens, J., Garcia-Luna-Aceves, J.J.: `Hierarchical routing using link vectors', Proc. IEEE INFOCOM, April 1998, p. 702–710.
28. 28)
  - E. Ravasz , A. Baraba'si . Hierarchical organization in complex networks. Phys. Rev. E , 2 , 026112 - 026111

Theoretical analysis for tree-like networks using random geometry

Theoretical analysis for tree-like networks using random geometry

Buy article PDF

Buy Knowledge Pack

Thank you

References

Related content