2011 International Conference on Network-Based Information Systems
Application of GA and Multi-Objective Optimization for QoS Routing in Ad-hoc Networks
Admir Barolli? , Evjol
a Spaho? , Fatos Xhafa? , Leonard Barolli§ and Makoto Takizawa? Department of Computers and Information Science Seikei University 3-3-1 Kichijoji-Kitamachi, Musashino-Shi, Tokyo 180-8633, Japan E-mail: firstname.lastname@example.org, email@example.com Graduate School of Engineering Fukuoka Institute of Technology (FIT) 3-30-1 Wajiro-Higashi, Higashi-Ku, Fukuoka 811-0295, Japan E-mail: firstname.lastname@example.org University of Catalonia Department of Languages and Informatics Systems C/Jordi Girona 1-3, 08034 Barcelona, Spain E-mail: email@example.com Department of Information and Communication Engineering Fukuoka Institute of Technology (FIT) 3-30-1 Wajiro-Higashi, Higashi-Ku, Fukuoka 811-0295, Japan E-mail: barolli@?t.ac.jp
§ ? Technical ? ?
Abstract—Much work has been done on routing in Adhoc networks, but the proposed routing solutions only deal with the best effort data traf?c. Connections with Quality of Service (QoS) requirements, such as voice channels with delay and bandwidth constraints, are not supported. The QoS routing has been receiving increasingly intensive attention, but searching for the shortest path with many metrics is an NP-complete problem. For this reason, approximated solutions and heuristic algorithms should be developed for multi-path constraints QoS routing. Also, the routing methods should be adaptive, ?exible, and intelligent. In this paper, we use Genetic Algorithms (GAs) and Multi-objective Optimization for QoS routing in Ad-hoc Networks. In order to reduce the search space of GA, we implemented a Search Space Reduction Algorithm (SSRA). After the reduction of search space the GAMAN search time improves. Our proposed method has the best performance for crossover rate 70% and mutation rate 8%. Keywords-Ad-hoc Networks, Intelligent Algorithms, Routing Algorithms, QoS Routing, Genetic Algorithms, MultiObjective Optimization.
I. I NTRODUCTION The wireless mobile networks and devices are becoming increasingly popular and they provide users access to information and communication any-time and anywhere. The conventional wireless networks are often connected to a wired network (e.g. ATM or Internet). This kind of wireless network requires a ?xed wire-line backbone infrastructure. All mobile hosts in a communication cell can reach a base station on the wire-line networks in onehop radio transmission. In contrast, the class of Ad-hoc networks do not use any ?xed infrastructure. The nodes
978-0-7695-4458-8/11 $26.00 ? 2011 IEEE DOI 10.1109/NBiS.2011.18 50
of Ad-hoc networks intercommunicate through single-hop and multi-hop paths in a peer-to-peer fashion. Intermediate nodes between two pairs of communication nodes act as routers. Thus the nodes operate both as hosts and routers. The nodes are mobile, so the creation of routing paths is affected by the addition and deletion of nodes. The topology of the network may change rapidly and unexpectedly. Much work has been done on routing in Adhoc networks , . Many protocols and algorithms such as Destination-Sequenced Distance-Vector (DSDV) protocol, cluster-based routing algorithms, Dynamic Source Routing (DSR) protocol, Ad-hoc On-demand DistanceVector (AODV) protocol, Zone Routing Protocol (ZRP), Temporally Ordered Routing Algorithm (TORA), and Associative Bit Routing (ABR) have been proposed. The emphasis has been on providing the shortest path and achieving a high degree of availability in a dynamic environment where the network topology changes fast. However, all the above routing solutions only deal with the best effort data traf?c. The QoS routing has been receiving increasingly intensive attention in the wire-line network domain , . The routing strategies can be classi?ed into three classes: source, distributed and hierarchical routing. However, these QoS routing algorithms can not be applied directly to Ad-hoc networks, because of the bandwidth constraints and dynamic network topology of Ad-hoc networks. Recently, because of the rising popularity of multimedia applications and potential commercial usages of Ad-hoc networks, QoS support in Ad-hoc networks has become an
unavoidable task. To support QoS, the link state information such as delay, bandwidth, cost, loss rate, and error rate in the network should be available and manageable. But, getting and managing the link state information in Ad-hoc networks is very dif?cult because the quality of wireless link may change with the surrounding circumstances. Furthermore, the resource limitation and the mobility of hosts make things more complicated. The challenge we face is to implement complex QoS functionality with limited available resources in a dynamic environment. In the literature, the research on QoS support in Adhoc networks includes QoS models , , QoS resource reservation signaling , QoS Medium Access Control (MAC) , and QoS routing , , . In this paper, we will survey only QoS routing problem in Adhoc networks. The QoS routing searches for a path with enough resources for QoS requirements. The QoS metrics could be additive, concave or productive. It is proved that if QoS contains at least two additive metrics, then the QoS routing is a NP complete problem . Therefore, searching for the shortest path with minimal cost and ?nding delay constrained least-cost paths are NP-complete problems. For this reason, approximated solutions and heuristic algorithms should be developed for multi-path constraints QoS routing. Also, to cope with changing of Ad-hoc networks topology, routing methods should be adaptive, ?exible, and intelligent. Use of intelligent algorithms based on Fuzzy Logic (FL), Neural Networks (NNs) and GAs can prove to be ef?cient for traf?c control in telecommunication networks . In difference from non-linear programming methods, GA, FL and NNs are heuristic methods which use explicit rules to ?nd feasible routes. The GA uses the genetic operators for optimization. By ?nding good values of crossover probability, mutation probability, and population size, the response time of the GA can be improved. However, there is a trade-off between the selected route and the response time. The GA tries to ?nd a route with a good ?tness value, but based on genetic operators probability this may be not the global optimum. In the case of mobile Ad-hoc networks, it is better to ?nd a route very fast in order to have a good response time to the speed of topology change, than to search for the best route but without meaning, because the network topology is changed and this route does not exist any-more. In this paper, we use Genetic Algorithms (GAs) and Multi-objective Optimization for QoS routing in Ad-hoc Networks. In order to reduce the search space of GA, we implement a Search Space Reduction Algorithm (SSRA). After the reduction of search space the GAMAN search time improves. The paper is organized as follows. In Section II, we discuss the issues and dif?culties for QoS support in Adhoc networks. In Section III, we introduce QoS routing metrics In Section IV, we deal with related work on QoS routing. In Section V, we present GA-based QoS routing. Our proposed multi-objective optimization method is pre-
sented in Section VI. The simulation results are presented in Section VII. Finally, conclusions are given in Section VIII. II. Q O S S UPPORT IN A D - HOC NETWORKS : I SSUES AND D IFFICULTIES The QoS is usually de?ned as a set of services requirements that needs to be met by the network while transporting a packet stream from a source to a destination. The network needs are governed by the service requirements speci?ed by the end user applications. The network is expected to guarantee a set of measurable prespeci?ed service attributes to the users in terms of end-toend performance metrics, such as delay, bandwidth, transmission success ratio, packet loss, and jitter. The power consumption and service coverage area are two other QoS metrics that are more speci?c to Ad-hoc networks. The Ad-hoc networks differ from traditional wire-line networks. The difference introduce unique issues and dif?culties for supporting QoS in Ad-hoc networks environment, which are summarized in following.
Unpredictable Link Properties Wireless media is very unpredictable. Packet collision is intrinsic to wireless network. Signal propagation faces dif?culties such as signal fading, interference, and multi-path cancellation. All these properties make the measure of bandwidth and delay of a wireless link unpredictable. Hidden-Exposed Terminal Problem Multi-hop packet relaying introduces the hiddenexposed terminal problem. This problem happens when signals of two nodes which are out of transmission range of each other collide at the common receiver. Because of the local nature of transmissions, hidden and exposed stations abound in Ad-hoc networks. A hidden station is a host that is within the range of the receiver but not the transmitter, while an exposed station is within the range of the transmitter but not the receiver. Node Mobility Mobility of the nodes create a dynamic network topology. Links will be dynamically formed when two nodes come into transmission range of each other and be torn down when they move out of the range. Route Maintenance The dynamic nature of the network topology and the changing behaviour of the communication medium make the precise maintenance of network information very dif?cult. Thus, the routing algorithms in Adhoc networks have to operate with inherently imprecise information. Furthermore, in Ad-hoc networks environments, node can join and leave any-time. The established routing paths may be broken even during the process of data transfer. Thus arises the need for maintenance and reconstruction of routing paths with minimal overhead and delay. Limited Battery Life
Mobile devices generally are dependent on ?nite battery sources. The resource allocation for QoS provisioning must consider the residual battery power and the rate of battery consumption corresponding to the resource utilization. Thus, all the techniques for QoS provisioning should be power-aware and poweref?cient. Security Security can be considered as a QoS attribute. Without adequate security, unauthorized access and usages may violate the QoS negotiations. The nature of broadcasts in wireless networks potentially results in more security exposures. The physical medium of communications is inherently insecure. So, we need to design security-aware routing algorithms for Adhoc networks. III. Q O S ROUTING M ETRICS
An Ad-hoc network.
5 5 5
6 5 3
1 4 4
In , the authors present the following metrics for QoS route discovery and selection.
QoS satisfying path
Minimum Required Throughput or Capacity (bps) This is the desired application data throughput. Maximum Tolerable Delay (s) Usually de?ned as the maximum tolerable end-to-end (source to destination) delay for data packets. Maximum Tolerable Delay Jitter One widely accepted de?nition of this metric is the difference between the upper bound on end-to-end delay and the absolute minimum delay. The former incorporates the queuing delay at each node and the latter is determined by the propagation delay and the transmission time of a packet. This metric can also be expressed as delay variance. Maximum Tolerable Packet Loss Ratio (PLR) The acceptable percentage of total packets sent, which are not received by the transport or higher layer agent at the packet’s ?nal destination node.
An example of QoS in Ad-hoc networks.
The primary goal of the QoS routing protocol is to determine a path from a SN to a DN that satis?es the needs of the desired QoS. The QoS path is determined within the constraints of minimal search, distance and traf?c conditions. We discuss some QoS routing algorithms in following . A. Ticket-based Probing Algorithm A ticket-based probing algorithm with imprecise model was proposed by Chen and Nahrstedt . While discovering a QoS-aware routing path, this algorithm tries to limit the amount of ?ooding (routing) messages by issuing a certain amount of logical tickets. Each probing message must contain at last on ticket. When a probing message arrives at a node, it may be split into multiple probes and forwarded to different next-hops. Each child probe will contain a subset of tickets from their parent. Obviously, a probe with a single ticket cannot be split any more. When one or more probe(s) arrive(s) at the destination, the hopby-hop path is known and delay/bandwidth information can be used to perform resource reservation for the QoSsatisfying path. In wire-line networks, a probability distribution can be calculated for a path based on the delay and bandwidth information. In a mobile Ad-hoc network, however, building such a probability distribution is not suitable, because wireless links are subject to breakage and state information is imprecise in nature. Hence a simple imprecise model was proposed for ticket-based probing algorithm. It uses history and current (estimated) delay variations and a smoothing formula to calculate the current delay, which is represented as a range of [delay - δ , delay + δ ]. To adapt to the dynamic topology of mobile Ad-hoc networks, this algorithm allows different level of route redundancy. It also uses re-routing and path-repairing techniques for route maintenance. When a node detects a broken path,
An application may typically request a particular quality of service by specifying its requirements in terms of one or more of the above metrics. IV. R ELATED W ORK ON Q O S ROUTING In this section, we will review the routing schemes that can support QoS in Ad-hoc networks. In Fig. 1 is shown an Ad-hoc network. The wireless topology derived from Fig. 1 is shown in Fig. 2. The mobile nodes are labelled as A, B, C, ..., K. The numbers beside each edge represent the available bandwidths of the wireless links. Suppose we want to ?nd a route from Source Node (SN) A to a Destination Node (DN) G. For conventional routing using shortest path (in terms of the number of hops) as metric, the route ”A-B-H-G” will be chosen. It is quite different in QoS route selection. Suppose we consider bandwidth as QoS metric and desire to ?nd a route from A to G with a minimum bandwidth of 4. Now, the feasible route will be ”A-B-C-D-E-F-G”. The shortest path route ”A-B-H-G” will not be adequate for providing the required bandwidth.
it will notify the SN, which will reroute the connection to a new feasible path, and notify the intermediate nodes along the old path to release the corresponding resources. Unlike the re-routing technique, path-repairing technique does not ?nd a completely new path. Instead, it tries to repair the path using local reconstructions. B. CEDAR CEDAR, a Core Extraction Distributed Ad-hoc Routing is proposed as a QoS routing scheme for small and medium scale mobile Ad-hoc networks . It dynamically establishes the core of the network, and then incrementally propagates the link states of stable highbandwidth links to the core nodes. The route computation is on-demand basis, and is performed by the core nodes using only local state. CEDAR has three key components has follows. Core Extraction: A set of nodes elected to form the core that maintains the local topology of the nodes in its domain, and also perform route computation. The core nodes are elected by approximating a minimum dominating set of the mobile Ad-hoc Networks. Link State Propagation: QoS routing in CEDAR is achieved by propagating the bandwidth availability information of stable links to all core nodes. The basic idea is that the information about stable high-bandwidth links can be made known to nodes far away in the network, while information about the dynamic or low bandwidth links remains within the local area. Route Computation: Route computation ?rst establishes a core path from domain of the SN to the domain of DN. Using the directional information provided by core path, CEDAR iteratively tries to ?nd a partial route from the source to the domain of the furthest possible node in the core path satisfying the requested bandwidth. This node then becomes the source of the next iteration. In CEDAR approach, the core provides an ef?cient and lowoverhead infrastructure to perform routing, while the state propagation mechanism ensures the availability of the linkstate information at the core nodes without incurring high overheads. C. Interference-aware QoS Routing In , the authors consider throughput-constrained QoS routing based on knowledge of the interference between links. So-called clique graphs are established, which re?ect which links interfere with each other, thereby preventing simultaneous transmission. The proposed solution operates by ?rst recording the channel usage (bps) of each existing data session on each link. It is noted that the total channel usage of the sessions occupying the links within the same clique must not exceed the channel capacity. A link’s residual capacity is then calculated by subtracting the channel usage of all sessions on links in the same clique from the link’s nominal capacity. This link capacity information may then be used in any known distributed Ad-hoc routing protocol to solve the throughput-constrained routing problem.
D. Cross-Layer Multi-Constraint QoS Routing In , the author focuses on performing multiconstraint QoS routing with three metrics: delay, link reliability and throughput. The author reiterates the fact that the multi-constraint QoS routing problem is NP-complete when a combination of additive and multiplicative metrics is considered. Among the above metrics, delay is additive, link reliability is multiplicative and achievable throughput is concave. However, methods have been proposed for reducing this NP-complete problem to one that can be solved in polynomial time. In one such method, all QoS metrics, except one, take bounded integer values. Then, the task of ?nding a path to satisfy all constraints can be performed by a modi?ed Dijkstra’s algorithm. In , the multiplicative metric is reduced to an additive one by taking the logarithm of the reliability percentage of a link. Also, the delay metric is reduced such that each link is represented by the percentage of the allowable total delay it introduces. The resulting problem in the new metric space can be solved in polynomial time. Then, a modi?ed Bellman-Ford or Dijkstra’s algorithm with the new reliability metric for link weights can be used to ?nd an approximation to the optimal path. An obvious advantage of this approach is the concurrent consideration of several important QoS metrics in path selection. However, the QoS state for all paths must be discovered and kept fresh. This incurs extra overhead and the details of this mechanism are not discussed in the paper. V. GA- BASED Q O S ROUTING A. GA Cycle The GA cycle is shown in Fig. 3. At the beginning, an initial population of potential solutions is created as a starting point for the search. In the next stage, the performance (?tness) of each individual is evaluated with respect to the constraints imposed by the problem. Based on each individual’s ?tness, a selection mechanism chooses ”parents” for the crossover and mutation operators. The crossover operator takes two chromosomes and swaps part of their genetic information to produce new chromosomes. The mutation operator introduces new genetic structures in the population by randomly modifying some of genes, helping the search algorithm to escape from local optimum. The offspring produced by the genetic manipulation process are the next population to be evaluated. GA can replace either a whole population or just its less ?t members. The creation-evaluation-selection-manipulation cycle repeats until a satisfactory solution to the problem is found, or some other termination criteria are met . B. GAMAN QoS Routing Algorithm In , we proposed a GA-based QoS routing algorithm for mobile Ad-hoc networks. We will explain in following GAMAN algorithm.
1) Network Model Assumptions: We assume that all the hosts communicate on the same shared wireless channel. Each node has a unique identi?er and has at least one transmitter and one receiver. Assume that the effective transmission distance of every node is equal. Two nodes are neighbours and have a link between them if they are in the transmission range of each other. We assume that there exists a neighbour discovering protocol. Each node periodically transmits a BEACON packet identifying itself, so that every node knows the set of neighbour nodes. We assume the existence of a MAC protocol, which resolves the media contention, supports resource reservation and ensures that among the neighbours in the local broadcast range only the intended receiver keeps the message and the other neighbours discard the message. We assume small to medium networks. For larger networks some cluster based algorithms or distributed algorithms can be used. We assume that the change in network topology is frequent, but not frequent enough to render any sort of route computation useless. Speci?cally, we assume that topology changes are typically followed by at least a short period of stability. Note that we only care about the relative mobility of hosts not the absolute mobility of the hosts. In particular, even if a platoon of solders or cars is moving, the mobile Ad-hoc Networks would be considered to be stable as long as the neighbourhood of each solder or car does not change. The links between the stationary or slow moving nodes are likely to exist continuously. Such links are considered as stationary links. The links between fast moving nodes are likely to exist only for a short period of time. Such links are considered as transient links. A routing path should use the stationary links whenever possible in order to reduce the probability of the path breaking when the network topology changes. 2) GAMAN Goals: We consider a type of mobile Adhoc network whose topologies are not changing that fast to make the QoS routing meaningless. We want to emphasize that GAMAN supports soft QoS without hard guarantees. The soft QoS means that there may exist transient time periods when the required QoS is not guaranteed due path breaking or network partition. However, the required QoS should be ensured when the established paths remain unbroken. Many multimedia applications accept soft QoS and use adaptation techniques to reduce the level of QoS disruption. In CEDAR, the bandwidth is used as the only QoS pa-
rameter for routing. Also, in ticked-based routing method the delay and bandwidth are used for QoS routing but not together. They are implemented as different algorithms. In this version, the GAMAN algorithm uses two parameters: delay and transmission success rate to decide the QoS path. The routing in mobile Ad-hoc networks has the following goals: a) the routing computation for small networks should be made at the SN in order to avoid the computation at intermediate nodes; b) as few nodes as possible must be involved in route computation; c) each node must only care about the routes corresponding to its destination, and must not be involved in frequent topology updates for parts of the network to which it has no traf?c; d) broadcast must be avoided as far as possible; e) it is desirable to have a backup route when the primary route has become stale and is being recomputed; f) messages should be not cycled around loops. Our GAMAN algorithm can satisfy these requirements: a) the GAMAN is a source-based routing algorithm; b) by using a SSRA and small population size few nodes are involved in route computation; c) by taking a subpopulation, the nodes in this sub-population care only about the routes in this sub-population; d) the broadcast is avoided because the information is transmitted only for the nodes in a population; e) the GA search different routes and they are sorted by ranking them. So the ?rst one is the best route, but other ranked routes can be used as backup routes; f) by using a tree based GA method, the loops can be avoided. In summary, our goal is to compute good routes quickly, and react to the dynamics of the network very fast. As a results, we sacri?ce optimality of routes. Robustness, rather than optimality is the key requirement. 3) SSRA: By SSRA a network with many nodes will be reduced in a network with a small number of nodes. Thus, GAMAN is able to cope with increase of number of nodes in Ad-hoc networks. 4) Gene Coding: To explain this procedure, we use a small mobile Ad-hoc network with 8 nodes as shown in Fig. 4. Let consider node A as a SN and node H as a DN. All routes are expressed by the network tree model shown in Fig. 5. The shaded areas show the same routes from node C to H. In order to decrease the chromosome gene number, the network tree model of Fig. 5 is reduced as shown in Fig. 6. In the reduced network tree model, each tree junction is considered as a gene and the path is represented by the chromosome. The most important factor to achieve ef?cient genetic operations is gene coding, because it has in?uence on the ef?ciency of genetic operations. In , a Genetic Load Balancing Routing (GLBR) method which use GA has been proposed. The adaptive routing mechanism has a load balancing system among alternative paths. In the GLBR method, the genes are put in a chromosome in the same order the nodes form a route. Therefore, the chromosomes have different sizes. If genetic operations are chosen randomly, the new off-
B A E C
4 H D E 5 E H
H C8 G H F G H D H
Figure 4. A mobile Ad-hoc network with 8 nodes.
H D H B D H
H D E H G H C F G H E H D H G H H C F G H D H B D H C G H F G H G H F G H H E D H B D H
Network tree model.
G H F G H 6 H E D H B D H
Reduced network tree model.
2 3 4 5 6 7 8
HD B EC D E GFE H E HDC HDB H C G F BC
GAMAN gene coding.
Figure 7. Chromosome examples for the route ”A-B-D-E-C-F-G-H”.
A TSR = 90% 90% (a) A TSR = 100% 100% (b) 60% 100% B 90% 90% B
springs of a population may be unsuitable individual populations. Also, because the individuals of a population have different sizes, the crossover operations are complicated. In order to simplify the genetic operations of GLBR method, in GAMAN, the network is changed in a tree, then the tree network is reduced by grouping together the same routes. After, the tree reduction, the tree junctions are expressed by genes as shown in Fig. 7. In Fig. 7 is shown a chromosome example for the route ”A-B-D-E-CF-G-H” of network example. Each chromosome expresses only one route. The genes contain the information of the adjacent nodes. As is shown in Fig. 7, the chromosomes have the same length. Therefore, the crossover operation becomes very easy. The genes in a chromosome have two states ”active” and ”inactive”. A gene is called active if the junction is in the route, otherwise the gene is in ”inactive” state. In GLBR method, the interaction between the adjacent genes in a chromosome is necessary. While, in GAMAN this interaction is not necessary. So, the mutation operation also becomes easy. Furthermore, the GAMAN has a good gene coding method, which is able to create various individuals, which result in a fast evolution. In GAMAN, the selection operation uses both the ranking and elitist models. As the crossover method is used the single point crossover. In the mutation operation, the genes are chosen randomly in the range from zero up to mutation probability p mutation ≤ 1 , where l is the chromosome length. 5) QoS Routing Parameters: The GAMAN algorithm can use many parameters for QoS routing. In following we consider the case for two QoS parameters: Delay Time (DT) and Transmission Success Rate (TSR). The DT means the time it takes a packet to go from one
An example of TSR calculation.
node to another one. The TSR shows the rate of correctly transmitted packets (without loss). Let consider a wireless network with wireless nodes and links as shown in Fig. 8. The node A is the source node and node B is the destination node. Let node A sends to node B 10 packets. The total TSR value for Fig. 8(a) and Fig. 8(b) is calculated by Eq.(1) and Eq.(2), respectively. 10 × 0.9 × 0.9 × 0.9 × 0.9 = 6.561 10 × 1.0 × 1.0 × 0.6 × 1.0 = 6.000 (1) (2)
The best route in this case is that of Fig. 8(a), because the total TSR is higher compared with that of Fig. 8(b). Let consider another example, when the values of DT and TSR are considered as shown in Fig. 9. The value of T parameter is decided as follows: T =
n i=1 DTi n i=1 T SRi
where n is the number of wireless links in a path. When node A wants to communicate with node D, there are two possible routes: “A-B-D” and “A-C-D”. The T value for these routes is calculated by Eq.(4) and Eq.(5), respectively. T A? B ? D = T A? C ? D 650 350 + 300 = = 0.1733 75 × 50 3750 800 400 + 400 = = 0.0468 = 90 × 95 8550 (4) (5)
Purpose Function : F1
Purpose Function : F4
Processing System F4
Processing System F1
Processing System F2
Processing System F3
Purpose Function : F2
Purpose Function : F3
Figure 9. A network example for mobile Ad-hoc network QoS routing.
The delay time of ”A-B-D” route is lower than ”A-CD” route, but the T value of ”A-C-D” route is lower than ”A-B-D”, so ”A-C-D” route is the better one. This shows that other good candidate routes can be found when two QoS parameters are used for routing in mobile Ad-hoc networks. 6) GAMAN Operation: The GAMAN is a source-based routing mechanism and uses two QoS parameters for routing. When a node of mobile Ad-hoc network wants to transmit information to a DN, this node becomes the SN. The network ?rst is transformed in a tree network with the SN as the root of tree. After that, the tree network is reduced in the parts where are the same routes. By reducing the tree network, the chromosome length is shorten so the genetic operations become simple. After the reduction of the tree network, the tree junctions are coded as genes. The genes in a chromosome have the information of the adjacent nodes. Because, the individual and chromosome are the same, the route is represented by the chromosome and the population is a collection of wireless links. After the gene coding, GAMAN starts the genetic operations. First, an initial population is selected. In the selected population, the ranking selection model is used to select individuals in order to carry out the genetic operations. The ranking model ranks each individual by their ?tness. The rank is decided based on the ?tness and the probability is decided based on the rank. The individual ?tness is based on T value. When T value is small, the individual ?tness is high. The genetic operations are the crossover and mutation. The GAMAN algorithm uses the single point crossover, because simple operations are needed to get a fast response. In the mutation operation, the genes are chosen randomly in the range from zero up to mutation probability p mutation ≤ 1 , where l is the chromosome length. After the crossover and mutation, the elitist model is used. Based on the elitist model the individual which has the highest ?tness value in a population is left intact in the next generation. Therefore, the best value is always kept and the routing algorithm can converge fast. The offsprings produced by the genetic operations are the next population to be evaluated. The genetic operations are repeated until the initialized generation size is achieved or a route with a minimum T value is found. The route selection in GAMAN is based on T value, which is the ratio of DT with TSR. T is used as a ?tness
Pareto solution for DT and CC.
function to evaluate the selected individuals (routes). By minimizing the T value, the DT value is minimized and the TSR value is maximized. This means that a packet from node SN to node DN is transmitted with a small delay and a high transmission success rate. VI. P ROPOSED M ULTI - OBJECTIVE O PTIMIZATION M ETHOD In this section, we propose a new method for Ad-hoc networks considering GA and multiobjective optimization. The proposed method uses the multi-division group model for multi-objective optimization. When a function can be divided in different objective functions, the global domain can be divided in different domains and each individual can evolve in its domain. The procedure is shown in Fig. 10, where four different objective functions are independent from each other and each process is operating independently in each domain. In Fig. 11 is shown an example of Delay Time (DT) and Communication Cost (CC). The vertical axis shows the DT and horizontal axis the CC. The DT and CC have tradeoff relations. The points in the ?gure show the individuals (routes). The individuals which are in the left-upper part of the ?gure have the lowest CC. On the other hand, the individuals which are in the right-lower part of the ?gure have the lowest DT values. The individuals which are in the shaded area have good values for both DT and CC. The shaded area is called “pareto solution”. The individuals near pareto solution can be found by exchange the solutions of different domains. A. QoS Routing Search Engine The structure of QoS Routing Search Engine (QRSE) is shown in Fig. 12. It includes Cache Search Engine (CSE) and GAMAN. CSE and GAMAN operate independently, but they cooperate together to update the route information. When the QRSE receives a request for QoS routing from a client, it forwards the request in parallel to
TSR50, CC125, DT50 100 90
80 70 60 50 40 30 0 Node 30 Node 45 Node 60 Node 75 Node 90 20 40 60 80 100 120 140
Processing time [ms]
Algorithm success rate versus processing time.
CSE and GAMAN cooperation1.
Node 75 Node 60
Success rate [%]
60 50 40 30 20 DT50 DT75 DT25 DT100 10
CSE and GAMAN cooperation2.
10 0 10
Processing time [ms]
CSE and GAMAN. Then, the CSE and GAMAN search in parallel to ?nd a route satisfying the required QoS. The CSE searches for a route in the cache database (in the cache database, the destination and route information is saved as a database item). If the found route by CSE satis?es the required QoS, this route information is sent to QRSE, otherwise the route is put in the gene pool as new individual. If a QoS route can not be found by CSE, the route found by GAMAN is sent to QRSE. B. CSE-GAMAN Cooperation and Database Updating The database information should be updated because the network traf?c and the network state change dynamically. In order to update the database, the CSE and GAMAN cooperate together. When the GAMAN ?nds a good QoS routing, it puts this route information in the cache database as shown in Fig. 13. The route information which is used frequently is given high priority, thus this route can be searched very fast by CSE. In the case when the CSE ?nds a route in the database, but this route does not ful?ll the required QoS by client, this route information is put as a new individual in the genepool of GAMAN as shown in Fig. 14. VII. S IMULATION R ESULTS We show in Fig. 15 and Fig. 16 the simulation results for SSRA. By reducing the search space, the GAMAN can ?nd faster a new route. We use as QoS parameters:
Figure 16. DTs.
Algorithm success rate versus processing time for different
Transmission Success Rate (TSR), DT and CC. As the simulation environment was used desk-top computer (OS: Windows XP Pro; IDE: Visual C++6.0; CPU: Athlon64 +3500, Memory: 1024MB). The QoS parameters were set up in a random way. The DT for each link was set between 1 and 100, TSR was set between 1 and 100% and CC between 1 and 200 units. In Fig.15, we set the threshold parameters T SR(T h) = 50, CC (T h) = 125, DT (T h) = 50. Then, we changed the number of nodes from 30 to 45, 60, 75 and 90 and measured the algorithm success rate. As shown in these ?gures with the increase of the number of nodes the success rate to ?nd a feasible route increases. In Fig.16, we consider T SR(T h) = 50, CC (T h) = 150 and change DT (T h) from 25 to 100. As shown in the ?gure with the increase of the DT threshold the success rate is increased. However, when the threshold is very small the success rate is less than 20%. Therefore, there are tradeoffs for deciding the threshold parameters. In Table I, we show the simulation results of the proposed method for population size 10 and for different number of generations, crossover rates and mutation rates. We can see that with increase of mutation rate, the avarage number of generations and average processing time is decreased. But, with increase of crossover rate, the average number of generations and average procesing
Table I S IMULATION RESULTS FOR POPULATION SIZE 10.
Mutation Rate [%] 1 Crossover Rate [%] 70 80 90 100 70 80 90 100 70 80 90 100 70 80 90 100 Average No. of Generations 15.7 16.7 21.2 19.3 11.3 9.8 10.7 14.1 7.4 7.8 7.9 9.1 9.1 8.9 8.2 7.4 Average Processing Time [ms] 468.2 487.5 590.7 536.7 213.3 185.9 203.9 275.2 120.6 137.5 133.3 157.3 149.3 143.8 135.5 120.6
(a) Number of generations
Table II T IME NEEDED FOR ONE GENERATION ( MS ).
Number of Individuals 4 8 12 16 3 44.43 26.83 23.55 22.22 GN Exchange 5 7 50.45 46.19 28.01 40.26 26.49 26.04 22.23 23.25 10 55.59 31.17 26.71 24.04
(b) Processing time
time is increased. However, when the mutation rate is 8%, the performance of proposed method is better than 10%. Also for crossover rate 70% and mutation rate 8% we have the best performance. In Table II are shown the simulation results of GAMAN. If there are few individuals in the population, the Generation Number (GN) which shows the number of generations needed to ?nd a solution becomes large. On the other hand, when the number of individuals is high, the GN to ?nd a solution becomes small. However, when the number of individuals is 12 and 16, the difference is very small. This is because some individuals become the same in the genepool. Considering the exchange of individuals between domains, it can be seen that when the exchange interval is short the solution can be found very fast. This shows that by exchanging the individuals the algorithm can approach very quickly to the pareto solution. In Fig. 17 are shown the simulation results for number of generations and the processing time. In Fig. 17(a), we show the Generation Size (GS) versus the number of individuals. While, in Fig. 17(b) is shown the processing time versus the number of individuals. We consider 4 cases when the number of exchanging individuals is 3, 5, 7, and 10, respectively. If there are few individuals in the population, the GS which shows the number of generations needed to ?nd a solution becomes large. VIII. C ONCLUSIONS In this paper we propose a new routing method for Ad-hoc networks considering GA and multiobjective optimization. The proposed method uses the multi-division group model for multi-objective optimization. We evaluated SSRA and GAMAN by computer simulations. From the simulation results, we found the following results.
Figure 17. Relation between generation size and number of individuals.
The SSRA can reduce the search space of GAMAN, so GAMAN can ?nd faster a new route. With increase of mutation rate, the avarage number of generations and average processing time is decreased. But, with increase of crossover rate, the average number of generations and avarage procesing time is increased. However, when the mutation rate is 8%, the performance of proposed method is better than 10%. Our proposed method has the best performance for crossover rate 70% and mutation rate 8%. If there are few individuals in the population, the GS which shows the number of generations needed to ?nd a solution becomes large.
We would like to consider in the future a policybased routing using FL. We want to put the policies in the Fuzzy Rule Base (FRB) and use these policies for QoS-routing. We also want to investigate an integrated approach of GA-based routing and policy-based routing. We also want to consider the swarm intelligence approach combined with GA for QoS routing in Ad-hoc networks. Population of the agents (ants) can be adapted according to the problem size. In swarm intelligence the scalability can be promoted by ocal and distributed agent interactions. Swarm intelligent processes do not rely on a centralized control mechanism. Therefore the loss of a few agents does not result in catastrophic failure, but rather leads to graceful, scalable degradation. Agents can change, die or reproduce, according to system changes. R EFERENCES
 C. E. Perkins, Ad-hoc Networking, Addison-Wesley, 2001.
 E. M. Royer, and C. K. Toh, “A Review of Current Routing Protocols for Ad-hoc Mobile Wireless Networks”, IEEE Personal Communications, pp. 46-55, April 1999.  S. Chen, and K. Nahrstedt, “An Overview of Quality of Service Routing for Next-Generation High-Speed Networks: Problems and Solutions”, IEEE Network, Special Issue on Transmission and Distribution of Digital Video, Vol. 12, No. 6, pp. 64-79, 1998.  W. C. Lee, M. G. Hluchyj, and P. A. Humblet, “Routing Subject to Quality of Services Constraints in Integrated Communications Networks”, IEEE Network, Vol. 9. No. 4, pp. 46-55, 1995.  H. Xiao, W. K. G. Seah, A. Lo, and K. C. Chua, “A Flexible Quality of Service Model for Mobile Ad-hoc Networks”, Proc. of IEEE VTC-2000, Tokyo, May 2000.  G. S. Ahn, A. T. Campbell, A. Veres, and L. H. Sun, “Supporting Service Differentiation for Real-Time and Best-Effort Traf?c in Stateless Wireless Ad-hoc Networks (SWAN)”, IEEE Transactions on Mobile Computing, Vol. 1. No. 3, pp. 192-207, 2002.  S. B. Lee, “INSIGIA: for Mobile Distributed G. S. Ahn, X. Zhang, and A. T. Campbell, An IP-Based Quality of Service Framework Ad-hoc Networks”, Journal of Parallel and Computing, Vol. 60, pp. 374-406, 2000.
 D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, Addison–Wesley, 1989.  L. Barolli, A. Koyama, T. Suganuma and N. Shiratori, “GAMAN: A GA Based QoS Routing Method for Mobile Ad-hoc Networks”, Journal of Interconnection Networks (JOIN), Vol. 4, No.3, pp. 251-270, September 2003.  M. Munetomo, Y. Takai, Y. Sato, “An Adaptive Routing Algorithm with Load Balancing by a Genetic Algorithm”, Trans. of IPSJ, Vol. 39, No. 2, pp. 219-227, 1998.  J. Anno, L. Barolli, A. Durresi, F. Xhafa, A. Koyama, “Performance Evaluation of Two Fuzzy-based Cluster Head Selection Systems for Wireless Sensor Networks”, Mobile Information Systems, Vol. 4., No. 4, pp. 297-312, December 2008.  L. Barolli, M. Ikeda, G. De Marco, A. Durresi, A. Koyama, J. Iwashige, “A Search Space Reduction Algorithm for Improving the Performance of a GA-based Routing Method in Ad-hoc Network”, International Journal of Distributed Sensor Networks (IJDSN), Vol. 3, No. 1, pp. 41-57, January 2007.  S. Zhao, D. Raychaudhuri, “Policy-based Adaptive Routing in Mobile Ad-hoc Wireless Networks”, Proc. of IEEE Sarnoff-2006 Symposium, Available online at http://www.winlab.rutgers.edu/?sulizhao/szhao sarnoff 06.pdf, March 2006.  E. Bonabeau, M. Dorigo, and G. Theraulaz, Swarm Intelligence: from Natural to Arti?cial Systems, Oxford University Press, 1999.  M. Dorigo, V. Maniezzo, and A. Colorni, “The Ant System: Optimization by a Colony of Cooperating Agents”, IEEE Transactions on Systems, Man, and Cybernetics, Part B, Vol. 26, No. 1, pp. 29-41, 1996.  A. Koyama, L. Barolli, G. Capi, B. O. Apduhan, J. Arai, A.Durresi, “An Ef?cient Multi-Purpose Optimization Method for QoS Routing Using Genetic Algorithm”, Journal of Interconnection Networks (JOIN), Vol. 5, No.4, pp. 409-428, December 2004.  Y. C. Hu and D. B. Johnson, “Caching Strategies in On-demand Routing Protocols for Wireless Ad-hoc Networks”, Proc. of IEEE/ACM MobiCom-2000, pp. 231-242, August 2000.
 S. Chen, S.H. Shah, and K. Nahrstedt, “Cross-Layer Design for Data Accessibility in Mobile Ad-hoc Networks”, Journal of Wireless Personal Communications, Special Issue on Multimedia Network Protocols and Enabling Radio Technologies, Kluwer Academic Publishers, Vol. 21, pp. 49-75, 2001.  S. Chen, and K. Nahrstedt, “Distributed Quality-ofService Routing in Ad-hoc Networks”, IEEE Journal of Selected Areas in Communications, Vol. 17, No. 8, pp. 1-18, 1999.  R. Sivakumar, P. Sinha, and V. Bharghavan, “CEDAR: A Core-Extraction Distributed Ad-hoc Routing Algorithm”, IEEE Journal of Selected Areas in Communications, Vol. 17, No. 8, pp. 1454-1465, 1999.  K. Wu, and J. Harms, “QoS Support in Mobile Ad-hoc Networks”, Crossing Boundaries - An Interdisciplinary Journal, Vol. 1, No. 1, pp. 92-106, Fall 2001.  Special Issue on Computational Intelligence in Telecommunication Networks, Computer Communications, Vol. 25, No. 16, 2002.  L. Hanzo (II.) and R. Tafazolli, “A Survey of QoS Routing Solutions for Mobile Ad-hoc Networks”, IEEE Communications Surveys and Tutorials, Vol. 9, no. 2, pp. 50-70, 2nd Quarter 2007.  R. Gupta, Z. Jia, T. Tung, and J. Walrand, “Interferenceaware QoS Routing (IQRouting) for Ad-hoc Networks”, Proc. of Global Telecommunications Conference, Vol. 5, pp. 2599-2604, November 2005.  Z. Fan, “QoS Routing Using Lower Layer Information in Ad-hoc Networks”, Proc. of Personal, Indoor and Mobile Radio Communications Conference, pp. 135-139, September 2004.