Research on Innovating, Evaluating and Applying Multicast Routing Technique and Genetic Algorithm for Routing Messages in Service - Oriented 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, NghiaTan, Cau Giay, 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 Innovating, Evaluating and Applying Multicast Routing Technique and Genetic Algorithm for Routing Messages in Service - Oriented Routing. Internet of Things and Cloud Computing. Vol. 3, No. 3, 2015, pp. 42-47. doi: 10.11648/j.iotcc.s.2015030601.15
Abstract: MANET (short for Mobile Ad-Hoc Network) consists of a set of mobile network nodes, network configuration changes very fast. Each node will act as a router to maintain network operation. As some standard content based routing protocols, when a node publishes its content, it will broadcast data to network. The published content will be cached at all routers on the network. So when a node publish a request to get some content, it will prepare a subscription message then broadcast it. When any node on network received that subscription, it matches subscription’s content with published content that have been cached on it. If found then matched content will be transferred to requested node. Service Oriented Routing is inherited from the model of content based routing (CBR), combined with several advanced techniques such as Multicast, Genetic algorithm (GA) increase the data rate, and data encryption to ensure information security.
Keywords: MANET, QOS, Bandwidth, Time Slot, Service, GEN, GA
1. Introduction
Publish/Subscription Model is the interaction model is performed asynchronously in the content based routing [3].
Each network node must undertake the following roles: service provider, content receiver and router. In the article, we will make use of the advantages of these routing protocols and customize some important characteristics to construct novel routing protocol that is oriented service and guarantees quality of service.
Service oriented architecture allows flexible communication, the ability to provide location transparency for the transmission of information between applications.
Service-based network infrastructure is a new network interface in which the flow of messages is controlled by class of service that generated it.
2. Organization of Types of Messages
In order to perform service based routing, we have to organize data into messages, there are some message types:
1. Subcription / unsubcription message: to register/unregister node’s requested content. The message is structured with: the address of the subscriber and binding on the list of services and content requirements (constraints). The first constraint is service binding, followed by the content constraints. In particular, each constraint is a set of 3 components, has the form: (key,operator,value). In which key is a string, the operator is subject to value. i) If the value is the number then operators are: =, <, >, <=, >=, in; ii) If the value is a string then operators are: =, <, >, <=, >=, substring (sb), prefix (pf), postfix (ps).
2. Content message: to publish node’s content.
Content message structure: i) Source node address is the address of the node that generate message; ii) The next attribute_{1}, attribute_{2},. .., attribute_{n} are the attributes of the message. The first attribute_{1} is the service information, the remaining attributes define the content of the message. Each attribute is a pair of name and value.
3. Advertisement message: to advertise node’s content, to direct subscriptions from subscribers to matched publishers, avoid to flood subscriptions all over networks. This message has structure similar to content message structure.
4. Update request (UR) and reply sender (RS) message pair: to update routing table. UR includes 3 fields: sender address and request number determine the uniqueness of UR. Timeout is the longest time the sender wait for an answer. The RS has three fields, two fields from the sender request, the field no.3 contains its all content based addresses. The RS spreads back the sender.
5. Route request (RREQ) and route reply (RREP) message pair: to detect routes. RREQ consists of 1) Source Address and 2) Request Number determine the uniqueness of RREQ; 3) Type is 1; 4) Timeout is time the sender waits for a response; 5) TTL is the maximum number of HOP of the route that message is passed on; 6) Route field records addresses of nodes; 7) Free TimeSlots records free timeslots of the nodes of the route; 8) Destination List field saves address list of destination nodes. When RREQ is received by a destination, it creates RREP to transmit to the source node. The RREP contains all fields from RREQ, besides the type field is set to 2 and doesn’t have destination list field.
3. Some Channel Access Techniques
A. TDMA (Time Division Multiplex Access)
In TDMA, each subscriber is assigned some specific timeslots (TS) dynamically for sending data. After that it has to wait. A base station is responsible for coordinating the nodes. TDMA allows for low latency and guaranteed bandwidth.
B. CSMA / CA (Carrier Sense Multiple Access / Collision Avoidance)
After waiting for a data transfer session ends, the node waiting a period of a random integer number of time units is specified. Node has waited completely first that will have right to transfer.
4. Multicast Routing
A. Multicast model [9]
Assume a network is represented by a weighted graph G (T) = (V (T), L (T)), where V (T), L (T) denote the sets of nodes and links, respectively. Given a multicast tree T(s, M), where s is the source node of T: s V (T), M V (T) \ {s} is the set of destinations. Define functions:
Delay (l): L (T) à R^{+}, l is a link of this tree;
Cost (v): V (T) à R^{+}, v is a vertex of this tree;
Bandwidth (l): B (l) à R^{+};
Delay(R_{i}) = (1)
Cost(R_{i}) = (2)
Bandwidth (R_{i}) is defined in following section.
B. Bandwidth calculation
Using timeslot [6] parameter to calculate bandwidth in MANET network using TDMA.
Status of each time slot is denoted by a (i, j), x (i, j) to represent time slot assignment’s result of time slot j of link i.
a(i, j) = (3)
x(i, j) = (4)
Hence, in order for route has maximum bandwidth, have to assign maximum number of timeslots for each link. Several conditions that assignment has to satisfy:
(5)
1. The calculation starts from the link that is in a state of having at least time slots. If there are more than one link that have equal minimum number of time slots, use the following formular to select link to start the algorithm:
a) Define k constant numbers: W_{1}> W_{2}> …> W_{k}.
b) TS_{h} (h ), TS_{h }is the free timeslots at time h.
c) Check link independence by the formula:
INDEPENDENCE= (6)
d) Choose the link that has INDEPENDENCE is maximum.
2. Estimate bandwidth w of a route by formula:
w=min(t/3,g) (7)
in which: t is the total of time slots, g is total of free time slots of start link.
3. We call that link is L_{min} (A, B). Select w time slots from free time slots of this link which satisfies Eq. 7.
4. Choose w timeslots from T free timeslots of L_{min} by following algorithm:
5. L_{min} has at most four neighbor links: l_{i-2}, l_{i-1}, l_{i+1}, l_{i+2}. Calculate = , that is number of times the timeslot j is assigned for five links: l_{i-2}, l_{i-1}, l_{i}, l_{i+1}, l_{i+2}. Sort array T by ascending order, chose the first w timeslots.
6. Delete selected w timeslots from free timeslots of l_{i-2}, l_{i-1}, l_{i+1}, l_{i+2}.
7. If can’t choose w timeslots, reduce bandwidth estimation by 1, reassign bandwidth for this link.
8. Choose w timeslots for each link from B to destination node or A to source node:
9. For each link L(B_{i}, B_{i+1}), choose w timeslots from T_{i} free timeslots of this link by above algorithm in (4). If it cann’t be chosen then reduce the estimated route’s bandwidth by 1, reassign from the beginning. Remove this w timeslots for the next two links L(B_{i+1}, B_{i+2}) and L(B_{i+2}, B_{i+3}).
C. Estimate latency
Based on analysis of some factors that affect the latency of transmission on the route (S, N_{1}, N_{2}, …, N_{k}, D). Estimate latency on each link by the formula:
D(l) = * S + * B + * D + * M (8)
Where: S is the size of data, B is bandwidth of the link l, D is the distance of the link, M is mobility of two nodes of the link. , , , are the weight of the factors S, B, D, M respectively.
D. Algorithms for building minimum spanning tree
1. Build Shortest Path Tree based Multiple Paths (SPTM)
This method (A) builds multicast tree that has the shortest path by hop on the multipath route from the root node to the leaf nodes. Should include the concept of multipath routing, in every part of the route, find all possible paths. If there are multiple candidate paths to each path segment, they are sorted by shortest-path-first rule. The bandwidth of the route will equal to the total bandwidth of all possible paths:
=, R={P_{0},P_{2}, …,P_{n-1}} (9)
2. Build Least Cost Tree based Multiple Paths (LCTM)
This method (B) builds multicast tree that has the total cost of all paths is minimum which is calculated by summing the cost of the links which form quality of service multicast tree. This kind of Multicast Tree can be built by PRIM algorithm. Hence the cost of the tree is equal to total cost of the links that have made tree:
(10)
On each part of route, find all possible paths based on the route detected messages pair as shown above.
3. Build Multiple Least Cost Trees (MLCT)
This method (C) builds multiple tree by using method (B). The algorithm: i) Build a multicast tree (T) by (B), if T is found the go to (ii), return the result; ii) scan this tree T, find any route R that doesn’t satisfy QOS. If not found, add T to the result set. Otherwise, remove R from route set (S). Go to (i). Dividing block of large data into some smaller blocks to send on multiple trees to the destination nodes. In destination nodes, combine some small packets into original data.
5. Find Optimal Route by GA
Some concepts of genetic algorithm
a) Population: the set of routes (chromosome) detected by above algorithm in one time.
b) Chromosome: each chromosome is consisted of identifiers (ID) of the nodes are on the route.
c) Purpose: find the best route.
d) Genetic operators: reproduction, mutation, crossover.
e) Algorithm is specified in following steps:
1) Make initial population from the detected routes.
2) Next generations are generated by the evolution process: Evaluation by fitness function, Selection, Reproduction.
Until the number of generations reach a predefined threshold or the optimum solution is found.
A. Establish the fitness function
Fitness function is established on the basic of some QOS parameters {._{ }Define fitness of R_{i} by the function:
f_{i} = (11)
Hop between gene g_{k}, g_{k+1}.
B. Establish Genetic Algorithm to find routes
The GA finds optimal QOS routes between a source (S) and a destination (D) by the following algorithm:
1. Collect all possible routes between S and D.
2. Assign weights for all parameters of these chromosomes.
3. At each generation, choose the best chromosomes based on fitness function to get offsprings:
a. Select two fittest routes based on fitness function;
b. Execute crossover on R_{1} and R_{2 }to get a new route: R_{3}.
c. Execute mutation on R3 to prune the low energy nodes.
Get the optimal QOS route R.
C. Some techniques to execute crossover operations
1. Two chromosomes must have at least a common gene.
2. {R_{3}}_{ }= R_{1} R_{2}, is crossover operation. Check if R_{3} has route loops. If true: i) remove this route and choose the next common gene; ii) remove the loops.
3. If R_{3} is found, apply mutation for it. Finally add it to the next population.
D. Some techniques to execute mutation operations [16]
1. At first choose randomly the first sub-route of R_{3} = {s, N_{1}, N_{2}, …, N_{i}, …, d}, = { s, N_{1}, N_{2}, …, N_{i}}. Delete randomly set of nodes after i.
2. The remaining nodes:{N_{j}, N_{j+1}, …, d}, deg(j) is the set of neighbors of j;
3. N_{temp} = N_{j}; iloopcount = 0;
4. = {};
5. = { N_{temp} };
6. deg(N_{temp}) = {N_{1}, N_{2}, …, N_{k}}
7. if |deg(N_{temp})| = 1 && i) if N_{1} <> d: exit; ii) if N_{1} = d: return = { Nj, N1 };
8. if (|deg(N_{temp})| > 1) execute (9).
9. if(iloopcount == 0) execute (10) else execute (15)
10. For(i:=1; ik; i++){
11. If((|deg(N_{i})|==1)&&(deg(N_{i})=={d})){
12. = { { N_{i}, d_{ }}};}
13. Else{
a. If((i==1) && (iloopcount==0)){
i. N_{temp} = N_{i};
ii. iloopcount += iloopcount;
14. Execute (6) for N_{temp}}}
15. For(i:=k; i1; i--){
16. If((|deg(N_{i})|>1) && (i==1))
17. Return result;
18. If((|deg(N_{i})|==1)&&(deg(N_{i})=={d})){
19. = {{N_{i},d_{ }};}}
6. Build Optimal Multicast Tree by GA
A. Encoding multicast tree
Encode multicast trees into chromosomes. Use two arrays for each tree: (i) array S stores nodes’ ID in the pre-order of tree traversal depth first search algorithm; (ii) array T stores the parent’s ID of each node. This algorithm P is executed recursively:
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) Visit R by storing R in its order in the array S:
1. S[iCount] = R.ID;
2. If iCount>1 then
i. T[iCount] = R.parent.ID;
3. End if
4. Increase iCount by one: iCount += 1;
a) Foreach(Node child in R.children)
b) Execute Scan(child, ref iCount);
c) End;
B. 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.
C. Establish fitness function
F = , P is the set of chromosome’s parameters, , are parameter and its weight for calculating the fitness level of each chromosome by function . For example, F = (*. In each round, estimate each chromosome in the population by this fitness function to choose the two best chromosomes for applying genetic operators.
D. Genetic operators
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 until find two satisfied parent chromosomes (P) and get two child chromosomes or scan all common gene of P.
E. Mutation operator
To eliminate low residual energy nodes of chromosome.
F. Evaluation algorithm complexity
The algorithm has complexity O(n*(m+log(n))): m is the number of chromosomes and n is average number of genes of each chromosome.
7. Simulation and Evaluation
Simulate the SPTM:
Simulate with number of nodes from 50 to 1000 nodes, number of destination nodes is 10 and a fixed source node.
A. Process to find optimal route by GA algorithm
a) Population size: this is about 20 to 30 chromosomes;
b) Crossover probability 0.2 to 0.9, mutation probability 0.05 to 0.2.
c) Chromosome size: this is about 20;
GA Simulation in 1000 times to find the optimal route.
Time required to find the optimal route doesn’t increase when number of routes increase.
B. Simulate to find optimal multicast tree by GA
a) Population size: this is about 2 to 100 chromosomes;
b) Crossover probability 0.2 to 0.9, mutation probability is about from 0.05 to 0.2.
c) Chromosome size: about 20;
The number of simulation is 100 times:
The time required for algorithm execution is sometimes decreased when the number of multicast trees is increased. In general, this time is very stable.
8. Conclusion
We can improve the routing process in content based routing by using Multicast Tree. Use one of three strategies presented above to build trees with guaranteed bandwidth. The complexity of this algorithm is depended on length of the route L_{R} and estimated route’s bandwidth W, that is O(L_{R}* W). On the other hand, we can apply GA algorithms to find optimal route or multicast tree from the set of routes or multicast trees respectively. This process is carried out on the same time with the process to detect routes. So when the process to detect routes finishes, a little time later the GA process also finishes.
References