Innovating R Treeand Multicast Routing to Make QOS Multiple Paths for Service Based Routing
Nguyen Thanh Long^{1}, Nguyen Duc Thuy^{2}, Pham Huy Hoang^{3}
^{1}Software development division III, Informatics Center of Hanoi Telecommunications, Hoan Kiem, Hanoi, Vietnam
^{2}Center for applied research and technology development, Research institute of Posts and telecommunications, Hanoi, VietNam
^{3}Information technology institute, Ha Noi University of Science Technology, Hanoi, Vietnam
Email address:
To cite this article:
Nguyen Thanh Long, Nguyen Duc Thuy, Pham Huy Hoang. Innovating R Tree and Multicast Routing to Make QOS Multiple Paths for Service Based Routing. Internet of Things and Cloud Computing. Vol. 3, No. 3, 2015, pp. 66-78. doi: 10.11648/j.iotcc.s.2015030601.19
Abstract: In the advanced routing of new networks communication and network technologies, it not only operates on some lower levels of a network protocol. But it also operates on some upper layers such as the application layer the highest-level layer in network protocol stack of OSI model. The routing process can be known by a more abstract concept. It can process on many layers on network’s stack of OSI model. So this kind of routing may be called the upper layer routing protocol. As the content based routing, in the service based routing protocol, the information can be classified by categories or service classes. Subscribers and publishers can communicate with each other but they don’t know other’s address. So it is more dynamical in processing and more comfortable for ad-hoc network. However the upper routing 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 may be reduced. Therefore the transmission delay may be increased. The paper aims at purpose to increate QOS of 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. In R^{+} tree model, the network’s nodes are managed by Bottom-Up model from leaf nodes to root of the tree. All the leaf nodes, inner nodes and root of this tree are used for two roles: i) Manage a cluster that consists all nodes that have direct connections with this node; ii) Operate as a normal node. The paper mentions: (i) Setup hierarchical clustering network by using R tree structure. (ii) Making multicast tree from some cluster heads for fast routing. (iii) Making optimized route by Ant Colony Optimization.
Keywords: MANET, R^{+}, Service, Routing, Multi-Paths, Bandwidth, Cluster, Tree, Multicast, QOS, Overhead, Ant, ACO
1. Basical Concepts
R tree is also the same as another tree, such as it has root, branches, and leaves. However it always keeps balance in its structure that is after each insert, update, delete operations it has to regulate its structure to remain each node has number of its children in the predefined range.
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)
We 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. The lower bound m is belonged to the range [0, ëM/2û]. 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 multiple levels from the root of the tree to its leaves distribute the network. 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 other cluster heads. The network of some cluster heads may establish the framework for the upper level of cluster.
NETWORK(U(CHi)) = CH1 U CH2 U CH3 U … U CHn (2)
This NETWORK(U(CHi)) is established that called 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 clusters, 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. The cluster head is a leaf node of the main R tree. So these nodes communicate with this cluster head for controlling 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.
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 some more details on using this tree to make hierarchical clustered routing. R tree can be expressed by a four items tuple:
R = {m, M, root, {F}} (3)
{F} is the set of functions to insert, update, delete and regulate the tree.
We define R^{+} tree by recursive formula:
R+(Root) = R+(Child1) U R+(Child2) U … U R+(childn) (4)
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} (5)
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 (6)
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 kinds 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. (7)
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. 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].
4. The Procedures to Accept a Node
As any normal protocol, when a node wants to join a network, it has to make HELLO message to broadcast it over network. When a cluster head receives this message, it checks some conditions. If these conditions such as node’s energy, strength of signal, CH will make a join request to send to this node. This node will send this CH its authentication information to join this cluster. As introduced in [6], this node information is processed and it will be propagate to a basically cluster from this cluster. When the properly cluster accepts this node, all changes needed will be operated from this cluster to the root of R^{+} tree. So it may happen the new node can be cluster head based on its capability and the procedures to vote new cluster for this cluster is processed. Hence at first it will be cluster of current cluster. The some cluster heads with the same level with this cluster head will vote new cluster head for the next level of clusters. The new node may be root of R^{+} tree, if it satisfies the conditions.
4.1. Accepting Node Procedure
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.
4.2. Voting Cluster Head Procedure
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.
5. Using Ant Colony Optimization to Find Stable Multiple Path QOS Route
QOS route is satisfied for communication demands of many kinds of applications, it utilizes network resources very efficiently. QoS consists of some metrics: end-to-end delay, available bandwidth, cost, loss probability. ACO [14] supports some QoS features: i) Multiple paths routing, ii) Traffic adaptive routing, iii) Do not decide based on local estimates, iv) Find optimal paths based on many criteria to load balancing.
The paper introduces an algorithm to find QOS routes based on ACO which consists of two phases: i) route discovery; ii) route maintenance. In the discovery phase, it uses two kinds of packets like route request and route reply of DSR protocol which are Ant_Route_Request and Ant_Route_Reply. Some QOS demands are stored in Ant_Route_Request in combination with visited node’s list field, this field stores nodes that are visited by this packet. So this packet contains: source address, destination address, hop count, bandwidth, visited node list initialized with source node.
5.1. Basic Concepts
Pheromone evaporation is some condition to choose the route. On the route to find food, an ant uses some pheromone evaporations to mask good routes. So other ants easy to find and go to the food source.
Establish to assess preference probability to choose a route based on: bandwidth of each link on the route, valid time remaining of links of route, total delay of all links, the hop count of this route by the formula:
Denote G = (V, E) that represents the graph of the network, V is the set of vertices, E is the set of edges. Assume R is route found that consists of n links: R ={(, ), (, ), …, (, )}. Hence, bandwidth of R is calculated by:
(8)
The valid time is remained of R that is defined by:
T(R) = (9)
Total delay of R is:
D(R) = (10)
The hop count of R is:
H(R) = n-1 (11)
Each parameter has a weight factor: , , and for , T(R), D(R), H(R) respectively.
Hence the route’s quality is the same on each link of the route which is calculated by the formula:
QOS(R) = (12)
The quality of each link is defined as the visibility of the ant by the formula:
(13)
5.2. Discovery Phase
Ant_Route_Request is broadcasted to 1-hop neighbors of the source node like a HELLO packet of OLSR. In each neighbor node: i) node has to maintain its link quality table {} of 1-hop distance nodes based on the accessing pheromone evaporation, it calculates the preference probability () of each link based on information of routing table on this node. If is more than predefined threshold preference probability, then this link is chosen for forwarding Ant_Route_Request next into the network; ii) Choose a 1-hop distance node among 1-hop distance nodes that is MPR, that has connections to almost 2-hop distance nodes of this node. So in choosing MPR is the next hop for the route to the destination. Now MPR functions as source node, it carries the same functions: broadcast Ant_Route_Request to its 1-hop distance nodes. When packet to find a route arrives at the destination node. Destination immediately creates Ant_Route_Reply to transfer back to the source node. In Ant_Route_Reply stores route has been detected, it is transferred by the unicast protocol to the source.
5.3. Maintenance Phase
Some routes can be detected in one discovery phase, but choose the optimal route by Genetic algorithm to transfer data. The remaining routes will be cached in the buffer of the source for multiple path routing, backup route in the case of main route hasn't existed by topology changes. But these routes are periodically checked for existence state.
6. Simulations
6.1. Establish R+ Tree for Hierarchical Network Clustering
The algorithms for establishing, updating R^{+} to hierarchically cluster network as the algorithms in [6] for building R^{+} to manage service based routing table.
Some modifications: i) A leaf node stores n components (, , …, ), each component stores a pointer P to an indexed item and a summary filter FS of its child node. Each indexed item stores a pair of two elements node identifier and its filter. Leaf node stores a summary filter of its components and cluster head’s ID of its group. So each leaf node give information about one basic group of the network; ii) Similarly, each inner or root node stores information about an upper group of the network. That is a cluster head’s ID of its group, some components that have pointers to its child nodes and their summary filters; iii) Condition for inserting a node N to a child group GC of a current group G is: check each components of G, calculate the formula: FT = , is FS of GC, F is the filter of the inserted node. Put N to GC that gives FT is minimum or maximum result based on real condition. Starting this algorithm at root node of R to a leaf node, at the leaf node actually insert N to this basic group and regulate the R tree to the root node for satisfying condition: number of elements of each group in the range [m, M].
6.2. Simulate These Algorithms of Applying R+ Tree to Cluster Network
Execute the process to insert node to the network until there are 1000 nodes. Perform this process by the regulation: when adding enough 10 nodes, then remove 1 node. Measure time in ms needed to add or remove a node, then collect the results to make a below graph:
As the graph shows that the time required to execute does not increase when the number of nodes increases. It is approximate one milli second. Sometimes this time increases for regulating R^{+} tree, but it is lower than one second. The time is rather high in the whole tree building process.
7. Assessment 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.
References