Abstract
A lot of work has been done on routing in MANETs. However, the proposed routing solutions deal only with the best effort data traffic. Connections with Quality of Service (QoS) requirements are not supported. The QoS routing has been receiving increasingly intensive attention in the wireline network domain. However, for MANETs only few QoS routing algorithms are proposed. For MANETs, approximated solutions and heuristic algorithms should be developed and QoS routing algorithms should be adaptive, flexible, and intelligent. In our previous work, we proposed a Genetic Algorithm (GA) based routing method for Mobile Ad-hoc Networks (GAMAN). In this paper, we enhance the proposed algorithm by adding an effective topology extraction algorithm to reduce the search space of GAMAN. We call this algorithm E-GAMAN. The E-GAMAN uses two QoS parameters for routing. The performance evaluation via simulations show that E-GAMAN has a good performance.
Introduction
A class of wireless mobile networks is Mobile Ad Hoc Networks (MANETs). The nodes of MANET 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.
The MANETs are useful in many application environments and do not need any infrastructure support. Collaborative computing and communications in smaller areas (building organizations, conferences, etc) can be set up using MANETs. Communications in battlefields and disaster recovery areas are other examples of application environments. Similarly, communications using a network of sensors or using floats over water are other potential applications of MANETs. The increased use of collaborative applications and wireless devices may further add to the needs and usage of MANETs.
Much work has been done on routing in MANETs [1, 2]. However, all these routing solutions deal only with the best effort data traffic. Connections with Quality of Service (QoS) requirements are not supported. The QoS routing has been receiving increasingly intensive attention in the wireline network domain [3, 4]. However, these QoS routing algorithms can not be applied directly to MANETs, because of the bandwidth constraints and dynamic network topology of MANETs.
Recently, because of the rising popularity of multimedia applications and potential commercial usages of MANETs, QoS support in MANETs has become an unavoidable task. Getting and managing the link state information in MANETs is very difficult because the quality of the 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 MANETs includes QoS models [5, 6], QoS resource reservation signaling [7], QoS Medium Access Control (MAC) [8], QoS scheduling [9], and QoS routing [10, 11, 12, 13, 14]. The QoS routing algorithms search 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 [12, 14]. For this reason, approximated solutions and heuristic algorithms should be developed for multi-path constraints QoS routing. Also, to cope with changing of MANET topology, routing methods should be adaptive, flexible, and intelligent.
Use of intelligent algorithms based on Fuzzy Logic (FL), Neural Networks (NNs), and Genetic Algorithm (GAs) can prove to be efficient for traffic control in telecommunication networks [15]. In our previous work [16], we proposed a GA based routing method for Mobile Ad-hoc Networks (GAMAN). In this paper, we enhance the proposed algorithm by adding an effective topology extraction algorithm to reduce the search space of GAMAN. We call this algorithm E-GAMAN. Robustness rather than optimality is the primary concern of E-GAMAN. In the case of MANETs, it is better to find a route very fast in order to have a good response time to the speed of topology change, than to search for the optimal route but without meaning, because the network topology is changed and this route does not exist anymore. The E-GAMAN uses two QoS parameters for routing. To evaluate the performance of the proposed method we carried out the simulations for different network topologies.
The paper is organized as follows. In Section 2, we introduce the related work. The proposed QoS routing algorithm is treated in Section 3. The simulation results are discussed in Section 4. Finally, conclusions are given in Section 5.
Related Work
In this section we will review the routing schemes that can support QoS in MANETs. In Fig. 1 a MANET is shown. The wireless topology derived from Fig. 1 is shown in Fig. 2. The mobile nodes are labeled as A, B, C, …, K. The numbers beside each edge represent the available bandwidths of the wireless links. Suppose we want to find a route from Source Node (SN) A to a Destination Node (DN) G. For conventional routing using the 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 the bandwidth as QoS metric and desire to find 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.
A MANET.
An example of QoS in MANET.
The primary goal of the QoS routing protocol is to determine a path from a SN to a DN that satisfies the needs of the desired QoS. The QoS path is determined within the constraints of minimal search, distance and traffic conditions. We will present in the following section some of QoS routing algorithms for MANETs [10, 11, 12, 13, 14].
A ticket-based probing algorithm with an imprecise model was proposed by Chen and Nahrstedt [10]. While discovering a QoS-aware routing path, this algorithm tries to limit the amount of flooding (routing) messages by issuing a certain amount of logical tickets. Each probing message must contain at least one 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 hop-by-hop path is known and delay/bandwidth information can be used to perform resource reservation for the QoS-satisfying path.
In wireline networks, a probability distribution can be calculated for a path based on the delay and bandwidth information. In a MANET, 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 the 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 MANETs, this algorithm allows a different level of route redundancy. It also uses re-routing and path-repairing techniques for route maintenance. When a node detects a broken path, 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, the path-repairing technique does not find a completely new path. Instead, it tries to repair the path using local reconstructions.
CEDAR
CEDAR, a Core Extraction Distributed Ad hoc Routing is proposed as a QoS routing scheme for small
and medium scale MANETs [11]. It
dynamically establishes the core of the network, and then incrementally propagates the link states
of stable high-bandwidth links to the core nodes. The route computation is on an on-demand basis,
and is performed by the core nodes using only local state. CEDAR has three key components. 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 MANET. 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 first establishes a core path from the domain of the SN to the domain of DN.
Using the directional information provided by the core path, CEDAR iteratively tries to find 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 the CEDAR approach, the core provides an efficient and low-overhead infrastructure to perform the routing, while the state propagation mechanism ensures the availability of the link-state information at the core nodes without incurring high overheads.
QoS-Aware Routing
A QoS-aware routing protocol is proposed in [14]. The authors introduce the bandwidth estimation by disseminating bandwidth information through “Hello” messages. The authors compare two different methods of estimating bandwidth. The “Hello” bandwidth estimation method performs better than the “Listen” bandwidth estimation method when releasing bandwidth is immediately important. The “Hello” and “Listen” methods work equally well in static topologies by using large weight factors to reduce the congestion and minimize the chance of lost “Hello” messages incorrectly signaling a broken route. In a mobile topology, “Hello” performs better in terms of end-to-end throughput, and “Listen” performs better in terms of the packet delivery ratio.
Proposed Algorithm
E-GAMAN has two algorithms: Search Space Reduction Algorithm (SSRA) and GAMAN.
SSRA
The flowchart of SSRA is shown in Fig. 3. The key element of SSRA is Effective Topology (ET) extraction. In order to extract the ET, the network connectivity information, wireless link and node metrics, and QoS requirement of the new connection are required. We use the “Threshold” to specify the QoS demand of a new request. If the Link Error Rate (LER) is more than the “Threshold” or the Node Available Bandwidth (NAB) is less than the “Threshold,” this means that the wireless path which passes via this wireless link or node cannot satisfy the requirements.
SSRA flowchart.
First, the SSRA based on the required “Threshold” checks all wireless links in the network whether their LER is less than the “Threshold” or not. If the LER is more than the “Threshold” then the wireless link is excluded from ET. Otherwise, the wireless link is included in the ET and the next wireless link is checked. The procedure is repeated until all links are finished. Next, the SSRA checks all nodes in the network, whether their available buffer satisfies the requirements or not. If the NAB is less than the “Threshold” then the node is excluded from the ET. Otherwise, the node is included in the ET and the next node is checked. The procedure is repeated until all nodes are finished. Finally, after all wireless links and nodes are checked, the network ET is constructed and the complete procedure is finished.
By using the SSRA, a network with many nodes and wireless links will be reduced in a network with a small number of nodes and wireless links.
GAMAN Network Model
We assume that all the hosts communicate on the same shared wireless channel. Each node has a unique identifier and has at least one transmitter and one receiver. Assume that the effective transmission distance of every node is equal. Two nodes are neighbors and have a link between them if they are in the transmission range of each other. We assume that there exists a neighbor discovering protocol. Each node periodically transmits a BEACON packet identifying itself, so that every node knows the set of neighbor nodes. We assume the existence of a MAC protocol, which resolves the media contention, supports resource reservation, and ensures that among the neighbors in the local broadcast range only the intended receiver keeps the message and the other neighbors 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. Specifically, 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 and not the absolute mobility of the hosts. In particular, even if a platoon of soldiers or cars is moving, the MANET would be considered to be stable as long as the neighborhood of each soldier 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.
GAMAN Algorithm
In this paper, we shall only consider a type of MANET 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 to 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 and QoS-Aware Routing, the bandwidth is used as the only QoS parameter for routing. Also, in a 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 proposed algorithm has the following features. It is is a source-based routing algorithm. By using a small population size few nodes are involved in route computation. By taking a subpopulation, the nodes in this subpopulation care only about the routes in this
subpopulation. The broadcast is avoided because the information is transmitted only for the nodes in a
population. The GA search different routes and they are sorted by ranking them. So the first one is the best
route, but other ranked routes can be used as backup routes. By using a tree based GA method, the loops can be avoided. By using SSRA, the algorithm extracts the effective topology of the MANET by avoiding transient
links and hidden terminal problems.
In summary, our goal is to compute good routes quickly, and react to the dynamics of the network very fast. As a results, we sacrifice optimality of routes. Robustness, rather than optimality is the key requirement.
GA Cycle
The GA cycle is shown in Fig. 4. At the beginning, an initial population of potential solutions is created as a starting point for the search. In the next stage, the performance (fitness) of each individual is evaluated with respect to the constraints imposed by the problem. Based on each individual's fitness, 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 the 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 fit members. The creation-evaluation-selection-manipulation cycle repeats until a satisfactory solution to the problem is found, or some other termination criteria are met [17].
GA cycle.
The most important factor to achieve efficient genetic operations is gene coding, because it has influence on the efficiency of genetic operations. In order to simplify the genetic operations, in the GAMAN algorithm, the network is expressed by a tree network and the genes are expressed by the tree junctions. By this coding method, the length of each chromosome is the same and the genetic operations are carried out in the tree junctions.
To explain this procedure, we use a small MANET with 8 nodes as shown in Fig. 5. Let us consider node A as a SN and node H as a DN. All routes are expressed by the network tree model shown in Fig. 6. 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. 6 is reduced as shown in Fig. 7. In the reduced network tree model, each tree junction is considered as a gene and the path is represented by the chromosome.
A MANET with 8 nodes.
Network tree model.
Reduced network tree model.
By using this gene coding method, the routing loops can be avoided. In Fig. 8 is shown the chromosome of route A-B-D-E-C-F-G-H. In GAMAN method, 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 an “inactive” state. The genetic operations are carried out in active genes.
GAMAN gene coding.
We have implemented two algorithms: one algorithm transforms the network in a tree network and another one reduces the tree network. But, for the sake of space, we will not introduce them in this paper.
The GAMAN algorithm uses the Delay Time (DT) and Transmission Success Rate (TSR) QoS parameters.
The DT means the time it takes a packet to go from one node to another one. The TSR shows the rate
of correctly transmitted packets (without loss). The value of T parameter is decided as follows.
where n is the number of wireless links in a path.
The GAMAN is a source-based routing mechanism and uses two QoS parameters for routing. When a node of MANET wants to transmit information to a DN, this node becomes the SN. The network is first transformed in a tree network with the SN as the root of a tree. After that, the tree network is reduced in the parts where the same routes are. By reducing the tree network, the chromosome length is shortened 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 the chromosome are the same, the route is represented by the chromosome and the population is a collection of wireless paths.
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 two individuals in order to carry out the genetic operations. The ranking model ranks each individual by their fitness. The rank is decided based on the fitness and the probability is decided based on the rank. The individual fitness is based on the T value. When the T value is small, the individual fitness is high.
The genetic operations are the crossover and the 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 1 up to mutation probability
After the crossover and mutation, the elitist model is used. Based on the elitist model the individual who has the highest fitness value in a population is left intact in the next generation. Therefore, the best value is always kept and the routing algorithm can converge very 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 fitness 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 SN to DN is transmitted with a small delay and a high transmission success rate.
We intent to use GAMAN for small scale MANETs. For large scale MANETs, a cluster based method or a distributed routing architecture can be used.
SSRA Simulation Results
In order to evaluate the performance of SSRA we used computer simulations. For simulations we used a SONY Note PC with the following specifications: CPU (Intel Pentium M1.3GHz), Memory (768 MB), OS (Microsoft Windows XP). The program was written in Microsoft Visual C + + 6.0 environment.
We used a different number of nodes for simulations (20, 30, 40, and 50 nodes). We considered that exist the wireless links in order to make the network topology. Then we put in a random way the values for each wireless link and remaining size of the buffer for each node. For each experiment, we carried out 300 simulations and then got the average values for the different number of nodes.
In Fig. 9 is shown the relation between the processing time and the number of wireless links for the different number of nodes. With the increase of the number of nodes, the processing time and the number of the wireless links increased. In Fig. 10 is shown the relation between the processing time and the search success rate. In this case we put strict threshold, so the success rate was between 20% to 60% for 20, 30, 40, and 50 nodes. In Fig. 11 and Fig. 12, we put higher threshold for the wireless link error rate and a small threshold for the buffer remaining capacity. It can be seen in Fig. 11 that the processing time is faster compared with the processing time in Fig. 9, while in Fig. 12, the wireless path searching success ratio is close to 100%.
Relation between processing time and number of wireless links (Case 1).
Relation between processing time and search success rate (Case 1).
Relation between processing time and number of wireless links (Case 2).
Relation between processing time and search success rate (Case 2).
By considering that the network topology was reduced by SSRA, we carried out many simulations to evaluate GAMAN for different number of nodes as shown in Table 1 and Table 2.
Time Needed for One Generation (ms)
Time Needed for One Generation (ms)
Performance for Different Parameters
Based on the DT and TSR values for each wireless link of MANET, the GAMAN calculate the value T, which is the ratio of DT with TSR. This value is used to measure the individual fitness. For simulations, we consider that a mobile node leaves the MANET, and we investigate the speed at which the GAMAN finds a new route. The genetic operations are repeated until a route with a small T value is found or the initialized generation size is achieved.
The performance behavior of GAMAN for a MANET with 20 nodes is shown in Fig. 13. This figure shows the rank versus the generation number. The rank is decided based on the value of fitness function T. When the rank is low the fitness value is low. This means that the selected route has a low delay and a high transmission rate.
Performance behavior of GAMAN algorithm.
In Table 1 are shown the simulation
results for the time needed for one generation and in Table 2 the performance of GAMAN for different parameters. In
Table 2, the Rank, Gen, and Ref have
the following meaning. Rank: the average rank to find a new route. Gen: the average number of generations to find a new route. Ref: the average number of individuals refereed in one simulation.
The GAMAN can get a new route for about 8 generations for a MANET with 20 nodes. The average time needed for one generation is about 4.8 ms. So, it needs about 40 ms. For a MANET with 10 nodes, it needs about 5 ms, for a MANET with 30 nodes, it needs about 270 ms, and for a MANET with 35 nodes about 300 ms. This shows that GAMAN can support QoS for MANET with 10, 20, 30, and 35 nodes when the network topology changing time is less than 5 ms, 40 ms, 270 ms, and 300 ms, respectively.
In this paper, we proposed an enhanced QoS routing algorithm for MANETs called E-GAMAN. The
proposed approach has two algorithms: SSRA and GAMAN. The SSRA reduce the search space for the GAMAN
so the GAMAN can find a feasible wireless path very fast. The GAMAN algorithm has the following
features. GAMAN is a source-based routing algorithm. By using a small population size few nodes are involved in the route computation. By taking a subpopulation, the nodes in this subpopulation care only about the routes in this
subpopulation. The broadcast is avoided because the information is transmitted only for the nodes in a
population. The GA search different routes and they are sorted by ranking them. So the first one is the best
route, but other ranked routes can be used as backup routes. By using a tree based GA method, the loops can be avoided.
The performance evaluation via simulations shows that the E-GAMAN algorithm has a good performance and is a promising algorithm for QoS routing in MANETs.
The proposed GAMAN algorithm can be applied for small and medium scale networks. In order to deal with large scale networks and also to find routes which satisfy more than two QoS parameters, we would like to extend our study by implementing the proposed method in a parallel GA.