Research on Applying Hierachical Clustered Based Routing Technique Using Artificial Intelligence Algorithms for Quality of Service of 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. 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. Vol. 3, No. 3, 2015, pp. 14-21. doi: 10.11648/j.iotcc.s.2015030601.11
Abstract: MANET (Mobile Ad-Hoc Network) is autonomous system, not based on existing infrastructure. Nodes usually change their position, network topology changes very fast. Service Based Routing is inherited from the model of Content Based Routing - CBR that manages and classifies many of network services. In order making nodes to communicate quickly and stablely, it requires applying some methodologies to reduce overhead and delay as well as power consumption. Therefore, this paper mentions a hierarchical clustered based routing using Tree. is a data structure with fast algorithms to establish, insert, update. It has been used in many fields effectively and efficiently such as Google Map, Forwarding technique, computer virtual memory. In combination with some artificial intelligence algorithms to make cluster, find optimized routes, multicast trees for effective communication. Fuzzy logic and genetic al. are proved to be very compatible with Manet. A genetic algorithm is used to choose optimized clusters, Fuzzy logic is applied to choose the cluster head and members of each cluster. Multiple paths routing is very importance for routing in MANET that making Quality of Service by Ant Colony Optimization Algorithm.
Keywords: MANET, QOS, Fuzzy Logic, Genetic, Cluster, Hierarchical, Ant, Optimization, Routing
1. Introduction
Service based routing performs on the model of subscribing requests, publishing contents, processing all of this information and replying results through network systems. When the number of nodes of a MANET is huge, control information communicated occupies an almost bandwidth of the MANET. So it needs a way to reduce MANET overhead. In this paper introduce a methodology by using the R^{+} tree to manage the network topology and hierarchical clusters its topology structure into several subnets. In each subnet, it chooses one or some cluster heads to manage their subnet. So control information mainly focuses on cluster heads. These cluster heads will establish a temporary stable network backbone. In each subnet, it will build one or more cluster heads based multicast tree for data transmission. It is easy to use fuzzy logic to choose cluster head and cluster members for each subnet. Use genetic al. to build an optimized multicast tree for its data transmission.
2. Fuzzy logic
2.1. Concept
The concept of fuzzy logic: To overcome the shortcomings of the traditional logic, Lotfi Zadeh has proposed one new theory of logic called fuzzy logic. Zadeh's theory represented the fuzzy or inaccuracy of logical clauses an inquantitative way by giving a set of membership functions, given function’s value in the range [0,1] . With S is a set, x is one element of the set, a fuzzy subset F of S is defined by one membership function μ_{F}(x) measuring the level that x belongs to F, with condition 0≤μ_{F}(x)≤1: i) with μ_{F}(x) = 0: x is completely not belong to F; ii) with μ_{F}(x)=1: x completely belongs F; iii) μ_{F}(x) = : F is called "brittle" set. The correctness of the logical expression are based on a set of rules gotten from experts or mathematical proof. Fuzzy logic is often used in decision support systems [5], used to approximate the function. Quality assessment of fuzzy expression depends on the quality of the laws.
2.2. Fuzzy Logic Controller
A fuzzy logic controller has some basic components:
1) Conversing functions: that fuzzifiers input values into fuzzy values, fuzzy values are in the range [0, 1], so these values are easy to process and calculate.
2) Use membership functions to assess fuzzy values. That classifies fuzzy values into groups. These groups can overlap each other. Each value has a membership value in a group.
3) Inference rules: use inference rules to make fuzzy outputs. Inference from two or more parameter values to get a fuzzy output.
4) Defuzzification: i) use the centroid method: get a value that is a center of result region that satisfies conditions; ii) use calculation: Output conversion functions convert membership functions’ results into a fuzzy output:
a) Circumstance 1: there is one parameter:
(1)
b) Circumstance 2: there is more than one parameter:
(2)
Where M is number of membership functions , x is fuzzy input, n is number of tests.
3. Hierarchical Clustering Using R+ Tree
3.1. R+ Tree Structure
R^{+} tree can be defined by recursive expression:
={, , …, }, all is an R subtree or a leaf node, High () = High() =… = High ().
R^{+} tree is like many other tree structures, it has a root, tree branches and leaves. For remaining balance on this tree, each branch of the tree has a number of child node is in [m, M]. In which, m, M are lower and upper bounds of the number of its children. So in each subnet, number of nodes will remain stable. Hence there are three kinds of nodes in this tree: i) Leaf node: this kind of nodes stores an array of cluster heads of a basically subnet at the lowest level. At one time it elects one is subnet’s cluster head. Each cluster head is chosen by fuzzy logic (FLC), each one is denoted by a component of two elements: node ID and a filter F which is composed of some predicates. F is logic predicate condition to choose a cluster head that is the result of FLC presented in the next section; ii) Inner/ Root node: each inner/ root node denotes an upper level subnet. The structure is similar to a leaf node, beside: its children are lower subnets. The algorithms to insert, update, delete a node in this tree are similar to which of R^{+} tree applied for forwarding technique [12]. Members of each subnet are also chosen by FLC. When a node takes part MANET, its information will be updated to R^{+} tree. It will join a basically subnet, these network topology will be replied back to the node.
3.2. Multiple Paths and Multicast Routing
One of ways to reduce overhead and build multiple path routing is to cluster network into some subnets. These subnets operate independently and communicate through cluster heads. This paper introduces clustering technique based on fuzzy logic. When many paths exist between a pair of source and destination nodes, use a genetic algorithm to find the optimal path. Build multicast tree [10] and optimize it by genetic al. to transmit data. In each branch of multicast tree use multiple paths to increase data rates. Detecting routes by broadcasting a pair of RREQ and RREP [10]. Use fuzzy logic to optimize this process as in [13]. Route discovery is optimized by using FLC to get a probability decision to rebroadcast RREQ at each node based on node location and its bandwidth.
Assume network is defined by a weighted graph G (T) = {V (T), L (T)}, V (T) and L (T) are vertex and edge sets. Divide network into n clusters: G = {, , …, }, in each cluster use an inner routing protocol to find the set of routes: RS = {, , …, }, is route set between cluster head CH and a node member i. So in order to find routes between two nodes (p, r) that belong to two clusters (, ), use the formula:
(3)
Where is the Descartes operator of two sets. So we have multiple paths between p and r.
Assume the number of routes in , , are , , respectively, the number of routes from up to r is:
(4)
In this paper, the Ant Colony Optimization (ACO) algorithm is used to detect multiple routes that satisfied quality of service (QOS) from a source node to a destination node. Otherwise, this algorithm can find QOS multiple paths route as introduced in section 5. ACO uses a pair of packets [10] RREQ and RREP to detect QOS routes on demand from a source S to a destination D. On the way between S and D, it collects some information about the link that RREQ has traversed and QOS metrics on the node. It assesses these metrics and decides route can transmit by this node or not. When it reaches D, it evaluates detected route globally and assign an availability P to this route. P is also the probabitity to choose this route to transmit data. If P is conformed QOS, it makes RREP to respond to S and updates routing table of immediate nodes.
3.3. Use fuzzy logic to Cluster Network
3.3.1. Elect Cluster Head
In the process to make a cluster, at first have to choose cluster head for a cluster based on some metrics, in this paper mentions two parameters:
i) Node bandwidth: B has three member functions: N, M, W, that are equal to three levels of bandwidth: Narrow, Medium, Wide. So node’s bandwidth is assessed based on these member functions.
ii) Node mobility: M, has three member functions: C, A, F, that are equal to three levels of mobility: Close, Adequate, Far.
Make inference rules in the table:
() | () | |||
N | M | W | ||
() | C | RM | L | VL |
A | S | M | L | |
F | VS | RM | M |
So get six levels for selecting CH: VS (very small), S (small), RM (rather medium), M (medium), L (large) and VL (very large).
3.3.2. Choose Cluster Members for A Cluster
To establish cluster, after a cluster head has been chosen, its members will be chosen based on some metrics. In this paper mentions two parameters:
i) Hop counts from node to CH: HC, there are three member functions: S, A, L, that are equal to three levels of hop count: Short, Average, Long.
ii) The bandwidth of the route from this node to CH: N, M, W, that are equal to three levels of bandwidth: Narrow, Medium, Wide.
() | () | |||
S | A | L | ||
() | N | RM | S | VS |
M | S | M | RM | |
W | VL | L | M |
So get six levels for selecting cluster members: VS (very small), S (small), RM (rather medium), M (medium), L (large) and VL (very large).
3.3.3. Choose A Route by Fuzzy Logic
In the process to detect routes, in each immediate node, for assessing route can pass over this node can based on two parameters:
i) Remaining energy in node: E, this parameter has five member function VL, L, M, H, VH;
ii) Energy consumption for transferring an amount of data through this node: J. This parameter also has five member function VL, L, M, H, VH;
The membership functions VL, L, M, H, VH are equal to five levels of energy: Very Low, Low, Medium, High, Very High. Assessing the membership value of each parameter by their member functions as in the diagram:
Build inference rules as in the following table:
S | J | |||||
VL | L | M | H | VH | ||
E | VL | HH | HM | HL | MH | MM |
L | HM | HL | MH | MM | ML | |
M | HL | MH | MM | ML | LH | |
H | MH | MM | ML | LH | LM | |
VH | MM | ML | LH | LM | LL |
So it has 25 fuzzy rules to get 9 member functions to choose route on each node. Assess the fuzzy results by output member functions as in the following diagram:
When the source receives enough routes in the route sets chosen by fuzzy logic, for getting optimal routes based on GA al. Because Genetic Al. has time required to calculate result very fast as mentioned in the next section. On the other way, it can build the optimal multicast tree in the case of transmitting data from one source node to some destination nodes simultaneously [10].
3.3.4. Find the Probability to Rebroadcast Control Messages
MANET with mobile nodes, information is transmitted through radio signal. When a node transmits data, nodes in its radio range will receive this data. When network density is dense, the radio signal is interference, so communication between nodes is usually lost and network throughput is reduced. In order to prevent this situation, it must reduce network overhead. One efficient method is to apply fuzzy logic to choose probability to decide to rebroadcast at each node.
() | () | ||||
I | N | B | E | ||
() | N | VL | RL | RM | L |
M | L | RM | M | RL | |
R | RL | M | H | RM | |
W | RM | H | VH | M |
So there are seven membership functions (MF) to estimate this probability: VL, L, RL, RM, M, H, VH that are corresponding to 7 membership values: very low, low, rather low, rather medium, medium, high, very high to choose probability to rebroadcast control messages.
The simulation to improve the better performance when using FLC to choose probabitity will be done in QualNet with some chosen parameters.
4. Build Optimal Multicast Tree by GA Algorithm
4.1. Build Optimal Multicast Tree by Route Finding GA
For each found multicast tree by executing one of the methods in [10], find the optimal route for it by the above algorithm in section 3.4. Assume L(T) is the list of found multicast trees. Following is an algorithm to find multiple trees and transmit data:
a) For each Multicast tree T_{i} in the list tree L(T).
b) For each route in this multicast tree T_{i}.
c) Find optimal R_{ik} in T_{i} by above genetic algorithm.
d) Execute (c) simultaneously for multiple routes to increase speed to get optimal T_{i} in L(T).
e) Divide a large block of data into several smaller blocks to transmit by multiple trees have found to multiple destinations.
4.2. Build Optimal Multicast Tree by GA
4.2.1. Encoding Multicast Tree
Before apply GA to find an optimal multicast tree, have to encode multicast trees into chromosomes. Use two arrays for each tree: (i) the first array S stores nodes’ ID in the order by executing pre-order algorithm P of tree traversal depth first search algorithm; (ii) the second array T stores the parent’s ID of each node. This algorithm P is executed recursively as described belows:
a) Assume R is root of the tree;
b) Function is named Scan with two parameters: i) a node A that will be visited; ii) a reference parameter iCount, init iCount by 1, that stores the sequence number of current node A. So Scan is:
c) Procedure Scan(byval R as Node, byref iCount as Integer)
d) Begin
e) Visit R by storing R in its order in the array S:
a. S[iCount] = R.ID;
b. If iCount>1 then
c. T[iCount] = R.parent.ID;
d. End if
e. Increase iCount by one: iCount += 1;
f) Foreach(Node child in R.children)
g) Execute Scan(child, ref iCount);
h) End;
Order | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
S | 20 | 21 | 12 | 11 | 13 | 112 | 23 | 28 | 29 | 26 | 125 | 212 | 132 | 2 | 102 | 142 | 312 | 192 |
T | 0 | 20 | 21 | 12 | 11 | 11 | 21 | 20 | 28 | 29 | 26 | 125 | 125 | 29 | 2 | 102 | 142 | 142 |
Decoding chromosomes into multicast tree:
The pair of chromosomes S and T after applying GA will be decoded into multicast tree T by the algorithm:
a) For k=2 to S.length Do
b) L(T) = L(T) (S(k), S(T(k)));
c) After the loop, get L(T) is the set of links of the tree T.
4.2.2. Establish the Fitness Function
Fitness function assesses each chromosome on the basic of delay, cost and residual energy of all links and nodes of the multicast tree:
F = (5)
Where: P is the set of chromosome’s parameters, , is parameter and its weight for calculating the fitness level of each chromosome by function . For example, F = (*, where , , are three constant values are chosen by user for easy estimating. In each round, estimate each chromosome in the population by this fitness function to choose the two best chromosomes for applying genetic operators consisting of crossover and mutation.
4.2.3. Genetic Operators
Similar to genetic operators for algorithm to find routes.
a) Crossover operator: {T_{new1}, T_{new2}} = T_{1} T_{2}, in which T_{1} = {T_{1first}, A, T_{1second}}, T_{2} = {T_{2first}, A, T_{2second}}, A is the common node of two chromosomes. So two result chromosomes can be:
b) T_{new1} = {T_{1first}, A, T_{2second}}, T_{new2} = {T_{2first}, A, T_{1second}},
c) Check T_{new1} and T_{new2} for eliminating any route cycle and having the same destination list.
d) If they don’t satisfy these conditions, then find the next common A of two chromosomes and execute (b).
e) Loop by finding two satisfied parent chromosomes (P) and get two child chromosomes or scan all common genes of P.
4.2.4. Mutation Operator
Use mutation operator to eliminate low residual energy nodes of chromosomes. Assume that each pair of nodes of tree T also has at least one connection.
4.2.5. Evaluation Algorithm Complexity
The fitness function has complexity O(m*n), where m is the number of chromosomes and n is the average number of genes on each chromosome. Crossover operator has complexity O(n*log(n)) and mutation operator has complexity O(n). Hence this algorithm has complexity O(n*(m+log(n))).
5. Using Ant Colony Optimization (ACO) to Find Multiple Stable Paths QOS Route
In order to find routes that are satisfied QOS constraints for communication on demands of many kinds of applications, as well as utilizing network resources very efficiently and effectively. Normally the QoS constraints consist of requirements on some metrics: end-to-end delay, reliability, bandwidth, cost, loss probability. ACO [14] supports some QoS features: i) Multiple paths routing; ii) Traffic adaptive routing; iii) ACO do not decide based on local estimates; iv) ACO finds optimal paths based on many criteria to load balancing. Actually ACO is only effective when network topology changes below a threshold level that can causes acceptable overhead when it makes process to detect routes. So any node has to decide to use ACO or not based on overhead that it can suffer. Usually, in small area of network or inner a cluster, it may use proactive routing protocol, for instance OLSR to update its routing table. In the overall of the network, network topology may be rather stable, so it could use reactive routing protocol in combination with some optimization protocols as ACO, GEN, BEE to discover routes for its transmission.
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 requirements 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 list, hop count, bandwidth of hops visited, visited node list initialized in source node. In every immediate node, ACO calculates bandwidth, delay of hop to decide to use this node in the route [10].
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:
(6)
The valid time is remained of R that is defined by:
T(R) = (7)
Total delay of R is:
D(R) = (8)
The hop count of R is:
H(R) = n-1 (9)
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) = (10)
The quality of each link is defined as the visibility of the ant by the formula:
(11)
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. Simulation and Evaluation
6.1. Simulate Applying Fuzzy Logic to Choose Probability to Rebroadcast Control Data
Use QualNet (main functions: modeling, simulating, and analysis) to simulate with some parameters [13]:
Parameter | Value |
Transmitter range | 250 |
Bandwidth | 2 Mbps |
Interface queue length | 50 messages |
Simulation time | 900 s |
Pause time | 0 s |
Packet size | 512 byte |
Topology size | (1 x 1) km |
Number of nodes | 25, 50, 75, 100 |
In which: DACBB: distance aware counter based broadcast and FPBB: the fuzzy logic based probabilistic AODV. This simulation uses these three protocols in the route discovery process. When a route discovery is initiated between a pair of a source and destination (S, D), the number of immediate nodes take part this process is increased when the number of connections (network flows) increases. The diagram shows that FPBB is the best performance protocol because it saves more rebroadcast of control messages especially with high offered load.
6.2. Simulate the Process to Find the Optimal Route by GA Algorithm
Some criterions to execute the GA algorithm:
a) Population size: this is about 20 to 30 chromosomes;
b) Crossover and mutation probabilities: Crossover probability is about from 0.2 to 0.9, mutation probability is about from 0.05 to 0.2.
c) Chromosome size: this is about 20;
Following is a diagram that represents the simulation result of GA to find the optimal route with a number of route varies from 4 to 20 routes, the route size varies from 3 to 20. The number of simulations is 1000 times:
From this diagram, it is very easy to realize that time required to find the optimal route doesn’t increase when amount of routes increase. In particular, with 1000 times of simulations, but in the diagram there are the number of points that is less than 1000, so the algorithm execution is very stable in time. The points are marked by red color.
6.3. Simulate the Process to Find Optimal Multicast Tree by GA Algorithm
Some criterions to execute the GA algorithm:
a) Population size: this is about 2 to 100 chromosomes;
b) Crossover and mutation probabilities: Crossover probability is about from 0.2 to 0.9, mutation probability is about from 0.05 to 0.2.
c) Chromosome size: this is about 20;
Following is a diagram that represents the simulation result of GA to find the optimal multicast tree with number of tree varies from 2 to 100 routes, the route size varies from 3 to 20. The number of simulations is 100 times:
From this diagram, it is very easy to realize that time required to find the optimal multicast tree doesn’t increase fast when the number of multicast trees increases. In particular, the time required for algorithm execution is sometimes decreased when the number of multicast trees is increased. In general, this time is very stable. The points are marked by red color.
6.4. Simulation of the Fuzzy Logic Controller to Choose Cluster Members
In this simulation, each node is assessed based on three metrics: bandwidth, hop count from this node to cluster node, energy remained. Simulation executes 2000 times with number of nodes from 20 to 50. These metrics of each node are randomly generated. The route from each member node to the cluster head consists of a number (from 1 to 10) of paths for increasing bandwidth and reducing latency. So the fuzzy logic controller assesses each node by using Eq. (12). The results of the simulation are represented in the Fig. 9.
From the Fig. 11, it is easy to realize that the time required to execute the algorithm converges.
7. Conclusions
In order to increase route bandwidth and availability with reducing control message overhead, the paper has mentioned fuzzy logic for clustering and genetic algorithm for finding optimal routes, multicast tree. Apply GA al. to find optimal route or multicast tree from the set of routes or multicast trees respectively. It requres the time to execute that is executable and this process is carried out on the same time with the process to detect routes. So when the precess to detect routes finishes, a little time later the GA process also finishes.
References