Internet of Things and Cloud Computing
Volume 3, Issue 3, October 2015, Pages: 79-81

Apply R+ Tree to Make Hierarchical Cluster Routing with QOS Guarranteed by Multiple Paths and Multicast Routing

Nguyen Thanh Long1, Nguyen Duc Thuy2, Pham Huy Hoang3

1Software development division III, Informatics Center of Hanoi Telecommunications, Hoan Kiem, Hanoi, Vietnam

2Center for applied research and technology development, Research institute of Posts and telecommunications, Hanoi, VietNam

3Information technology institute, Ha Noi University of Science Technology, Hanoi, Vietnam

Email address:

(N. T. Long)
(N. D. Thuy)
(P. H. Hoang)

To cite this article:

Nguyen Thanh Long, Nguyen Duc Thuy, Pham Huy Hoang. Apply R+ Tree to Make Hierarchical Cluster Routing with QOS Guarranteed by Multiple Paths and Multicast Routing. Internet of Things and Cloud Computing. Vol. 3, No. 3, 2015, pp. 79-81. doi: 10.11648/j.iotcc.s.2015030601.20

Abstract: In the new era of communication and network technologies, a routing protocol not only operates on some lower levels of a network protocol. It also operates on the application layer the highest-level layer in network protocol stack. So we call this is upper layer routing protocol. But it must be based on lower layers to make routing decisions. But normal routing protocols are used for most static network or rather small wireless networks or not high mobility networks. In mobile ad-hoc networks, nodes move very often and fast, so bandwidth of connection between them can be reduced. Therefore the transmission delay may be increased. The paper aims at purpose to increate QOS routing by hierarchical clustering routing by using R+ tree in addition with some advanced techniques multicast routing, multiple paths, use GEN/ BEE/ ANT to optimize routes to transmit data.

Keywords: MANET, R+, Service, Routing, Multi-Paths, Bandwidth, Cluster, Tree, Multicast, QOS, Overhead

1. Basical Concepts

The routing protocol in MANET is very popular in recently communication and computer technologies. In particular, routing protocol for service based routing is emerging in some recent years. In this paper, we analyze the R+ to organize the network topology in hierarchical clustering model. The R+ tree is rather simple to use for programming and design. The R+ can be expressed by the formula:

R+ = R+(C_1) U R+(C_2) U … U R+(C_n).       (1)

Assume R+ tree has n children C_1, C_2, …, C_n. In turn, each C_i is a child that connects directly to the root of R+ tree. Each R+ child tree, that has some children as its parent. In R+ tree, each inner node has a number of children that is in a predefined range [m, M], in which m, M are two bounds of this range. In a network, the nodes usually connect to each other to establish a network topology. This topology may be RING, STAR, BUS, … But when the number of nodes is increased and the space that occupies very large. The normal topologies are not very comfortable, it must to innovate these traditional topologies that in the recent time the multicast topology is usually used, to the larger network we may use hierarchical clustering model to organize the network topology. In this paper, we apply R+ tree to organize the network in hierarchical clustering model. So the network is distributed by multiple levels from the root of the tree to the leaves of the tree. In the tree, the network nodes in a level and belonged to a local root that are called a cluster or group. In a cluster or small group, the nodes usually have some more common characteristics with a cluster head, this is main node of a cluster. The cluster head manages all important tasks in this cluster. The cluster head is usually has much energy and operational capacity, that can operate continuously to communicate with each node in its cluster and some another clusters heads. The network of some cluster head may establish the framework for the upper level of cluster.

NETWORK(U(CH_i)) = CH_1 U CH_2 U CH_3 U … U CH_n.                       (2)

This NETWORK(U(CH_i)) is established a next level of cluster, that also has a cluster head. In this way, up to the root we have the root of the tree is cluster head of the highest level of the whole network. Therefore, it is very easy to realize that in the first level there are some n basic cluster, n  [m, M], in which each cluster has some nodes that in fact are network nodes, that has this root of this cluster is cluster head. So these nodes communicate with this cluster head for control and data communication in this cluster and outside networks. In the next levels, the roots of lower level establish the upper level, and they vote one of these nodes is cluster head. Therefore, it is easy to realize that the root of an upper level manages all nodes of all branches that connect to this local root. Then it is also the cluster head of this upper level of some cluster heads of one level lower some clusters. The purpose of the paper is to organize the whole network into a daisy chain of some R+ tree that each R+ tree is one part of this network by using some strength processing power nodes to establish a simple network of some roots of these R+ trees. Then adding nodes to one of these parts of whole network by following algorithms.

2. R+ Tree Advantages for Hierarchical Cluster Routing

The algorithms are used to make R+ tree are introduced in our previous papers rather deeply. In this paper will introduce more details on using this tree to make hierarchical clustered routing. We define R+ tree by recursive formula:

R+(Root) = R+(Child_1) U R+(Child_2) U … U R+(child_n). (3)

In that, Root is root of the R+ tree, so it is the most important node of the whole network, is the cluster head of top level cluster. Root often transmits control messages to their children members to coordinate its one level lower clusters. In turn these children members also manage their clusters by sending controlling messages. So overhead on control messages is:

OverHead(Control) = n_1*n_2*…*n_m.         (4)

For every leaf node can be operate. In that n_1 is number of children nodes in level 1 of R+ tree, n_2 is average number of children nodes of each cluster in level 2… As mention above, n_i Î [m, M], with the level of this tree m usually not large. Especially controlling messages are sending simultaneously from a cluster head to all its children nodes. So its delay is guaranteed as QOS request. Normally controlling messages are flooding on network, so it very fast causes network congestion. Especially it reduces network or route bandwidth (B) very fast for data transmission because almost B is used for controlling network. The configuration of each cluster is operated in low level service of cluster head by Operating System. When a node is covered by a cluster head with satisfied bandwidth, it may join this cluster by invitation message of this cluster head. Then this network local change is transmitted to network by multicast tree of some clusters. At first, this control message (M) is transmitted to the cluster head (CH) of parent cluster (PC) of the cluster head of current cluster. The cluster head of PC transmits this M to all members of PC and to CH of its cluster. By this way, this change of network configuration is very fast to be updated on all CHs. All network leaf nodes don’t need to receive this information, so it reduces much of bandwidth. The number of leaf nodes is:

n_1*n_2*…*n_m=∏(n_i),i=1..m.        (5)

with m level of network. Because the tree always is balanced so this number is rather stable. So each cluster has to store two main kind of connections: i) one to the cluster head of cluster that it belonged; ii) one to all its cluster members. This number of connections is near to:

n_i+1.                         (6)

Hence it is very good for storage management in each cluster head. In each leaf node of tree that needs to store only one connection to its cluster head.

The algorithm to choose cluster head as introduced by our previous papers [1-2-6-7]. In fact, a node can be belonged to some clusters simultaneously because all connections to these clusters also satisfy bandwidth demand. At the time to join network with very high density of nodes. For instance, many upper levels of cluster may accept this node at closed time. If this node stores all connections to these cluster heads then the time to update network topology is reduced by multicast tree from this node to all these CHs. With this way the root of R+ can be connected to some another trees easily. It establishes a daisy chain R+ trees. Because this model of networks can avoid the constraint of [m, M] in each level of R+ .

3. The procedures to establish R+ tree

3.1. Accepting a Node to R+ Tree

When a node is invited to join R+ tree or the root of a R+ that can be a branch of the large R+ to receive the HELLO of this node. The node’s information is propagating back to the root of the R+ tree. The node’s information is processed to choose the child (branch) of the root node to accept this node. The function to assess a node to decide the child of a CH to accept a node is operated based on some parameters. These parameters are fuzzed to put to a fuzzy logic controller to get the fuzzed output result to make the decision. The process is propagate to the leaf node of the R+ tree to add to one basically cluster.

3.2. Voting Cluster Head for a Cluster

The procedure to vote cluster head depends on some metrics of nodes in each cluster. When a cluster is established, some neuron network or fuzzy logic controller chooses the cluster head or a range of some cluster heads. Then the network of cluster heads of R+ tree is optimized by GEN algorithm.

4. Find Optimized Route by Multiple Paths and Multicast Routing

The temporary backbone of network of R+ daisy chain can be established some multicast trees or meshes of cluster heads of some clusters of this network for data transmission. Hence it avoids R+ structure in some critical circumstances to directly transmitting data from a source node to many destinations. This concept is very comfortable to upper layer routing in advanced networks. The algorithms to establish multiple multicasts and multiple paths with optimized routes that are found by GEN/ BEE/ ACO are introduced in [3-4].

5. Conclusions and Future Research

All above analysis are introduced in our previous papers, so they have very good performance. In the future, we have to research some compression techniques and encode data. It may help to reduce requested bandwidth and increase network security for data transmission. We may develop hierarchical clustering routing by using GPS to detect position of nodes with some techniques to estimate this position based on orbit of moving and velocity of node with some weighting model to assess these metrics to get correct node position to cluster network.


  1. Nguyen Thanh Long, Nguyen Duc Thuy, Pham Huy Hoang, Research on Applying Hierachical Clustered Based Routing Technique Using Artificial Intelligence Algorithms for Quality of Service of Service Based Routing, Internet of Things and Cloud Computing. Special Issue:Quality of Service of Service Based Routing. Vol. 3, No. 6-1, 2015, pp. 1-8. doi: 10.11648/j.iotcc.s.2015030601.11.
  2. Nguyen Thanh Long, Nguyen Duc Thuy, Pham Huy Hoang, Research on Innovating and Applying Evolutionary Algorithms Based Hierarchical Clustering and Multiple Paths Routing for Guaranteed Quality of Service on Service Based Routing, Internet of Things and Cloud Computing. Special Issue:Quality of Service of Service Based Routing. Vol. 3, No. 6-1, 2015, pp. 9-15. doi: 10.11648/j.iotcc.s.2015030601.12.
  3. Kartheek Srungaram, Dr. MHM Krishna Prasad, Department of Information Technology, JNTUK-UCEV, Vizianagaram, A.P, India, "ENHANCED CLUSTER BASED ROUTING PROTOCOL FOR MANETS".
  4. Cândida Ferreira, Departamento de Ciências Agrárias, Universidade dos Açores, 9701-851 Terra-Chã, Angra do Heroísmo, Portugal, "Gene Expression Programming: A New Adaptive Algorithm for Solving Problems".
  5. Bibhash Roy, Tripura Institute of Technology, Narsingarh, Tripura, India, "Ant Colony based Routing for Mobile Ad-Hoc Networks towards Improved Quality of Services".
  6. Nguyen Thanh Long, Nguyen Duc Thuy, Pham Huy Hoang, "Innovating R Tree to Create Summary Filter for Message Forwarding Technique in Service-Based Routing", Springer, ISBN: 978-3-642-41773-3, LNICST 121, p. 178, 2013.
  7. Research on Innovating, Applying Multiple Paths Routing Technique Based on Fuzzy Logic and Genetic Algorithm for Routing Messages in Service - Oriented Routing: Long Thanh Nguyen, Tam Nguyen The, Chien Tran, Thuy Nguyen Duc. Journal: Scalable Information Systems EAI.
  8. A Particle Swarm Optimization with Adaptive Multi-Swarm Strategy for Capacitated Vehicle Routing Problem. Kui-Ting Chen, Ke Fan, Yijun Dai and Takaaki Baba, 1Research Center and Graduate School of Information, Production and Systems, Waseda University, 2-7 Hibikino, Kitakyushu, Fukuoka, Japan.

Article Tools
Follow on us
Science Publishing Group
NEW YORK, NY 10018
Tel: (001)347-688-8931