© The Institution of Engineering and Technology
Among various network topologies, treelike 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 clusterpopulation 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)

R. Hekmat
.
(2006)
Adhoc networks: fundamental properties and network topologies.

2)

Y.S. Yen ,
R.S. Chang ,
H.C. Chao
.
Floodinglimited for multiconstrained qualityofservice routing protocol in mobile ad hoc networks.
IET Commun.
,
7 ,
972 
981

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)

J.M. McQuillan
.
(1974)
Adaptive routing algorithms for distributed computer networks.

5)

F. Kamoun ,
L. Kleinrock
.
Stochastic performance evaluation of hierarchical routing for large network.
Comput. Netw.
,
337 
353

6)

Lauer, G.S.: `Hierarchical routing design for suran', Proc. IEEE ICC, June 1986, p. 93–102.

7)

A.E. Baratz ,
J.M. Jaffe
.
Establishing virtual circuits in large computer networks.
Computer Networks and ISDN Systems
,
1 ,
27 
37

8)

Ramamoorthy, C.V., Tsai, W.T.: `An adaptive hierarchical routing algorithm', Proc. IEEE COMPSAC, November 1983, p. 93–104.

9)

E. Sakhaee ,
A. Jamalipour
.
Stable clustering and communications in pseudolinear highly mobile ad hoc networks.
IEEE Trans. Veh. Technol.
,
6 ,
3769 
3777

10)

Y.S. Yen ,
S. Hong ,
R.S. Chang ,
H.C. Chao
.
Controlled deployments for wireless sensor networks.
IET Commun.
,
5 ,
820 
829

11)

L. Kleinrock ,
F. Kamoun
.
Hierarchical routing for large networks: performance evaluation and optimization, computer networks.
Comput. Netw.

12)

Houstic, C.E., Leon, B.J.: `An adaptive routing algorithm for large storeandforward computer communication networks', Phase Report, October 1977.

13)

Murthy, S., GarciaLunaAceves, J.J.: `Loopfree internet routing using hierarchical routing trees', Proc. IEEE INFOCOM, April 1997, p. 7–11.

14)

J.J. GarciaLunaAceves ,
S. Murthy
.
A path finding algorithm for loopfree routing.
IEEE/ACM Trans. Netw.
,
1 ,
148 
160

15)

W.T. Tsai ,
C.V. Ramamoorthy ,
W.K. Tsai ,
O. Nishiguchi
.
An adaptive hierarchical routing protocol.
IEEE/ACM Trans. Comput.
,
8 ,
1059 
1075

16)

Behrens, J., GarciaLunaAceves, J.J.: `Hierarchical routing using link vectors', Proc. IEEE INFOCOM, April 1998, p. 702–710.

17)

S.P. Chung ,
M.T. Li
.
Performance evaluation of hierarchical cellular cdma networks with soft handoff queueing.
IEEE Trans. Veh. Technol.
,
2 ,
652 
672

18)

Susec, J., Marsic, I.: `Clustering overhead for hierarchical routing in mobile ad hoc networks', Proc. IEEE INFOCOM, April 2002, p. 1698–1706.

19)

D. Stoyan ,
W. Kendall ,
J. Mecke
.
(1995)
Stochastic geometry and its applications.

20)

J.L. Rougier ,
D. Kofman ,
A. Gravey
.
Optimization of hierarchical routing protocols.
Perform. Eval.
,
3 ,
227 
245

21)

M.G. Kendall ,
P.A.P. Moran
.
(1962)
Geometric probability.

22)

V.S. Alagar
.
The distribution of the distance between random points.
J. Appl. Probab.
,
3 ,
558 
566

23)

E.N. Gilbert
.
Random subdivisions of space into crystals.
Ann. Math. Stat.
,
3 ,
958 
972

24)

J. Moller
.
Random tessellation in .
Adv. Appl. Probab.
,
37 
73

25)

E. Ravasz ,
A. Baraba'si
.
Hierarchical organization in complex networks.
Phys. Rev. E
,
2 ,
026112 
026111

26)

J. Sucec ,
I. Marsic
.
Hierarchical routing overhead in mobile ad hoc networks.
IEEE Trans. Mob. Comput.
,
1 ,
46 
56

27)

S.G. Foss ,
S.A. Zuyev
.
On a certain segment process with Voronoi clustering.
INRIA, Rapport de Recherche
,
1 
17

28)

J.L. Meijering
.
Interface area, edge length, and number of vertices in crystal aggregates with random nucleation.
Philips Research Reprint
,
270 
290
http://iet.metastore.ingenta.com/content/journals/10.1049/ietcom.2011.0025
Related content
content/journals/10.1049/ietcom.2011.0025
pub_keyword,iet_inspecKeyword,pub_concept
6
6