Soutenance mémoire
Comparison of the MANET Routing Protocols
Introduction
To compare the performances of the routing strategies in various scenarios , multiple series of simulations were setup and executed with Network Simulator 2 (NS 2) (1995). The comparison of the protocols is based on the QoS parameters: (a) the routing total overhead, (b) PDR, (c) average path length, (d) average end to end delay, (e) throughput. The choices of the tested protocols were made in order to analyse strategies with different features. The main objective for these tests is to examine how the QoS performance factors are influenced when the experiment parameters are changed. It’s also important to mention that in order to mimic a realistic scenario, each Constant Bit Rate (CBR) application is launched at a random time rather than from the beginning of the simulation. Thus, avoiding unfairness when comparing reactive protocols with proactive ones. Because, the proactive method takes some time to establish connectivity. Accordingly, lunching the CBR application from the start will most likely result in massive packet losses for the proactive protocols.
Results and Discussion
hrough this section, it’s important to emphasise that the tests were conducted in various simulation conditions / scenarios to verify which protocol is the most suitable for each situation. And most importantly, to conclude on which protocol that is the most versatile in various situations.
The network growth
In the first experiment, the network was gradually expanded. To operate, all MANET routing protocols advertise routing messages in order to establish / preserve connectivity. Reasonably, the growth of the network implicates an increase of the routing information announced by the outing protocols Nevertheless, not all the protocols are influenced equally. Because the proactive algorithms construct / preserve a path to every attainable destination, this approach requires a frequent advertisement of the global topological view, in a form of routing messages. Accordingly, as the size of the topology and the routing messages expand, the overhead of the proactive protocols is raised extensively. Particularly, due to the repetitive broadcast of multiple routing messages (Topology Control, MPR Selector and HELLO Messages), OLSR (Francisco, 2004) generates a substantial overhead. Also, DREAM (Jeff and Wilcox, 2002) produces the highest overhead. In addition to its proactive approach, the overhead of this protocol depends on the nodes movement speed and the location of the destination is frequently forwarded to the source. Though this method strengthens the active path, it amplifies the overhead. DSDV on the other hand produces the lowest overhead by announcing the routing messages with the lowest broadcast frequency amongst the tested protocols. Although operating reactively, DSR generates a considerable overhead because of the insertion of the active path in all the routing / data messages. Similarly to DREAM, LAR announces supplementary geographical coordinates in order to accelerate path recovery. Therefore, the overhead of DSR and LAR is augmented. While AODV and AOMDV build a path when it’s necessary only, their recorded overhead is higher than the overhead produced by DSDV. This outcome is caused by the fact that the reactive method flood the entire network with RREQs to establish a path towards the destination. Consequently, to build / maintain only ten paths, the reactive protocols generate a large quantity of routing packets. Conversely, when AODV, LAR and DSR are operational, the routing messages are treated only by the members of the active paths. On the other hand, in order to update the routing table, all the received routing messages are treated by the proactive protocols. Hence, in Fig 11, the quantity of routing messages processed by the proactive protocols is significantly higher by comparison with the reactive protocols. It’s noticeable that even if LAR generates as much overhead as AODV, AODV treats a larger quantity of routing packets during this experiment. While LAR generates more routing messages to update the source location table, this protocol can estimate the zone in which the destination is positioned when a path failure occurs. Consequently, whereas AODV searches for the destination in the entire network, LAR avoids overflowing the network and thus, avoids processing a large quantity of RREQs. Likewise, DSR processes a low amount of routing packets because after the establishment of the path, only the nodes forming the transmission paths process the routing messages.For similar reasons, though DREAM generates the highest overhead, OLSR treats the largest amount of routing information during this experiment. This outcome is due to the fact that running OLSR requires a periodical processing of all the received control messages. Furthermore, when DREAM is applied, although the destination announces frequently its location and the intermediate nodes retransmit it to the source, only the nodes forming the transmission route process the corresponding routing messages. Thus, limiting the quantity of routing information processed. It’s also worthy to point out that in order to create a path to every reachable destination, the routing packets advertised by DSDV and the proactive protocols in general, contain a larger volume of routing information whereas the reactive protocols generate small routing packets . Also, the routing packets advertised by DSR and LAR are larger than the packets announced by AODV and AOMDV due to the inclusion of the entire path (DSR) and the geographical location (LAR). Unlike OLSR and DREAM, the overhead of AOMDV is small. By maintaining all the discovered disjoined paths leading to the destination, AOMDV is less affected by route failures. Though this method introduces supplementary processing, in case of a path breakdown, AOMDV relies on an alternative path instead of overflowing the network. Hence, during this test, DSDV and AOMDV produce the smallest overhead. In Fig 13 and 14, the PDR and throughput recorded during this experiment, are illustrated. Due to its high sensitivity to the changes influencing the active routes, AODV reacts faster to a path failure to construct a new path. Thus, attaining the largest PDR as shown in Fig 13. Moreover, OLSR, AOMDV, LAR and DREAM also accomplish considerable PDRs. Peculiarly, the PDR of AOMDV is lower by comparison with AODV. Although AOMDV maintains disjoined backup paths towards the source, the performance of this protocol declines in terms of PDR when the transmission attempt through the alternative path, fails. On the contrary, DSDV and DSR produce lower PDRs by comparison with the remaining protocols. Even if DSDV attempts to speed up the convergence by immediately advertising the vital topological alterations, the updates describing the remote destinations are not forwarded in a timely manner. Same, as DSR relies on the explicit routing directives, this protocol is slow to react to path failures especially those that transpire at a distant point of the path. Accordingly, the PDR accomplished by both protocols, is decreased.
From a throughput point of view (Fig 14), the network expansion renders the throughput produced by the protocols, unstable. This outcome is mainly due to the increase of the random topological events that can either make or break a transmission path. Obviously, the throughput value, which is the quantity of data successfully received by the destinations in a unit of time, is strongly related to the PDR. Consistently with the PDR values, DSDV produces the lowest throughput. Likewise, AODV achieves the highest throughput. In Table 7, we displayed two essential QoS flow parameters obtained from simulation in order to conduct a conclusive comparison: path length (which influence the jitter) and end to end delay. From a path length perspective (for successful deliveries only), due to its unawareness of the newly formed routes, DSR creates the longest paths during this experiment. Primarily, DSR uses the first obtainable path until it collapses. Then, in case of a path failure, the packets are salvaged by the intermediate nodes and re-routed towards the destination which increases the path length even further. LAR and DREAM also produce longer paths but for unrelated reasons. First, LAR applies a path recovery process based on the existing geographical description. Even if this approach facilitates the search for the destination, it does not produce necessarily the shortest path. Equally, the routing decisions in DREAM are based on the geographical coordinates and not hop count. Thus, both protocols achieve similar performances from an average path length point of view. Otherwise, DSDV, AOMDV and OLSR achieve the lowest average path lengths. Clearly, the performances of DSDV and OLSR are the outcomes of the proactive route updating approach. Then, while the results suggest that AOMDV built shorter paths by comparison with AODV, AODV achieves a much higher PDR than AOMDV. Meaning, that the low average path length of AOMDV during this experiment is partially caused by the failure to deliver packets to the remote nodes. From an average end to end delay point of view, DSR generates the lowest performance. Although the packet salvaging / recovery method applied by this protocol is intended to improve the PDR, re-routing the packets increases significantly the delay when this operation is successful. Besides, the surplus caused by the inclusion of the active path in the data messages increases as well the end to end delay. It’s also perceivable that the end to end delay of DREAM and LAR is slightly lower than the end to end delay of AODV. This performance is mainly due to the pathmaintenance / recovery based on the geographical information. Nevertheless, the end to end delay of DREAM and LAR is still a little elevated because of the slightly high average path length constructed by these two protocols. In addition to the obvious correlation between the end to end delay and path length, the delay depends also on the load of the nodes participating in the transmission. For instance, although LAR and DREAM usually achieve similar performances in terms of path length due to their related routing strategies, the end to end delay of the two protocols randomly diverge largely because of the arbitrariness of load balance in the constructed paths.
As opposed to the previous results, the average end to end delay of DSDV is the lowest. Although this protocol loses a lot of packets due to path failures, DSDV optimises eventually the paths based on the destination sequence number. As a result, this protocol delivers less packets, mostly to the closer nodes, with a lower delay. Also, AOMDV and OLSR achieve a relatively low average end to end delay. Naturally, the performance of OLSR is reasonable due to the periodical upgrading of all the possible routes. Nevertheless, when a transmission path is broken, the end to end delay is raised. Plus, as the overhead increases due the growth of the network, the additional routing packets queuing / processing time influences negatively the end to end delay of OLSR as well as the rest of the protocols. The end to end delay of AODV is affected by: (a) the path failures, (b) ignorance of the recently available paths. Unlike the rest of the protocols, in case of a path failure, AOMDV can rely on alternative routes to preserve the connectivity with the destination. Besides, because of its low complexity / overhead, the end to end delay of this protocol is less affected by routing packets queuing / processing time. Consequently, from an end to end delay perspective, this protocol achieves a superior performance (while producing a relatively good PDR performance as opposed to DSDV).
The increase of the network density
During this experiment, the transmission range was progressively increased in order to increase the network density. Primarily, the overhead of the protocols is affected in various ways as shown in Fig 15. Generally, the overhead of the proactive protocols is reasonably increased due to the increase of the number of connections between the nodes. On the other hand, the increase of the transmission range has the opposite effect on the reactive protocols in terms of overhead. Obviously, the increase of the transmission range boosts the strength of the routes, thus lowering the occurrences of link / path failures. Therefore, the overhead of the reactive protocols declines. In Fig 16 and 17, the increase of the PDR and throughput achieved by all the protocols, are the clear outcomes of the increase of the network density. Due to the improvement of the links / paths strengths, packet losses caused by routing errors, are less frequent. Hence, the PDRs of all the protocols are noticeably raised. Likewise, from an average path length and end to end delay perspective (Table 8), all the routing protocols achieve superior performances. Due to the low between the source and destination. Thus, increasing the throughput values as well. All performance metrics considered, the performance of DSR is remarkable. As the length of the paths decreases, the overhead of DSR decreases noticeably. In addition to achieving a noteworthy PDR when the transmission paths are shorter, knowing the integrity of the path provides a significant security option for this protocol.
Number of transmission connections
From an overhead perspective (Fig 18), the growth of the transmission demands affects the reactive protocols drastically. While the proactive algorithms construct the routes systematically, the reactive ones initiate a search for each connection demand independently. Added to the effect of path failures, the overhead of the reactive protocols is enlarged clearly when the numberconnection requests is raised. Distinctively, because of the backup routing method, AOMDV is less effected by path failures and consequently produces a lower overhead. In contrast to AOMDV, the overhead generated by DREAM and LAR is noticeably amplified. This result is due to the fact that LAR and DREAM frequently announce the position of the destination, for each connection, to update the location tables. Hence, the elevated overhead produced by these two protocols. On the other hand, the overhead of OLSR and DSDV remained stable. Basically, this result is due to the independence of the proactive path building process form the transmission demands.
Mainly, in addition to a reasonable expansion of the throughput (Fig 19), the PDR of all the protocols decreases as shown in Fig 20. While the number of connections is raised, the quantity of packets dropped due to route failures and collisions, is enlarged respectively. Based on the assembled results, AOMDV is fairly the best performing protocol during this experiment. Through maintaining alternative paths, AOMDV is more tolerant to path failures and, unlike the other protocols, can handle multiple transmissions more efficiently. Same, through the proactive path updating approach, the PDR of OLSR is relatively less influenced by path failures during this experiment. Most importantly, from an end to end delay perspective (Table 9), the performances of the protocols deteriorate considerably. While DREAM / LAR build paths based on the geographical information, and AOMDV promotes stable connectivity by creating multiple paths, the rest of the protocols are focused on building the shortest paths. As a result, the end to end delay increase due to the concentration of traffic on the nodes involved in multiple transmissions. On the other hand, DREAM and LAR don’t rely on hop count for path selection. Thus, the abovementioned protocols indirectly lighten the stress on the intermediate nodes positioned in the shortest path. Additionally, whereas path failures enlarge the delay for the other protocols, AOMDV maintains connectivity through alternative paths. As a result, lowering the occurrences of path recoveries and the delay introduced by them.
Node velocity
In order to verify the effect of the nodes speed of movement on the performance of the protocols, we made a series of simulations where the nodes velocity is augmented progressively. An understandable consequence of this alteration is a more frequent occurrence of path failures. According to the results in Fig 21, whereas the overhead of OLSR and AOMDV is stable, the overhead of DSR, DREAM, LAR, DSDV and AODV, is increased. This result is consistent with the theoretical descriptions of these protocolsDue to the frequent occurrences of path ruptures, DSR and AODV must launch a new path construction process which increases their overhead. Additionally, while applying DREAM and LAR, the nodes advertise their routing messages based on their speed of movement. Hence, the recurrent topological events (link / path failures and node movement) elevate the overhead of the aforementioned protocols. Additionally, the overhead of DSDV is slightly increased since this protocol is based on an event driven method to announce the important changes. On the other hand, the overhead of OLSR is not increased at all since this protocol is based on a periodical broadcast of the routing messages. Likewise, the overhead of AOMDV is less influenced because this protocol attempts to avoid path reconstruction by maintaining the connection to the destination through alternative paths. From a throughput and PDR point of view, the increase of the nodes speed of movement lowers the performances of most protocols as illustrated in Fig 22 and 23. Although AOMDV reduces the effect of path failures in terms of overhead, the high pace of the topological changes eventually renders the alternative paths unreliable. As a result, postponing path reconstruction while attempting to transmit the data through an alternative path, results into expanding packet losses (-29% PDR). Similarly, OLSR does not distribute the new information about the destination fast enough. Which results into routing errors and subsequently, less packets are delivered to the destination (-15% PDR). On the other hand, when path failures are frequent, AODV immediately starts the search for a new path towards the destination. As a result, although this method increases the overhead, this protocol achieves the highest PDR (-8% PDR). Furthermore, DREAM and LAR circumvent path failures by frequently advertising the location of the destinations that are moving fast. Subsequently, when a path failure is sensed, path recovery is usually less complicated. As a result, both protocols relatively reduce the effect of the nodes mobility on the ongoing transmissions (-10% PDR).
Correspondingly with the previous experiments, the results in Table 10 illustrate that the highest average path length and end to end delay are attained by DSR due to the packets salvaging / recovery attempts. Moreover, whereas AODV restarts path building once a path failure is sensed, searching in the entire network amplifies the delay gradually. The end to end delay of AOMDV is low due to the availability of alternative paths but then again, this protocol suffers a significant PDR drop (Fig 23). Conversely, LAR explores the recent geographical updates about the destination to accelerate path recovery. Which is why this protocol averages a relatively constant end to end delay while the nodes speed of movement is increased. Based on the obtained results, AODV, OLSR and LAR achieve the highest performances during this experiment.
Conclusion
In this chapter, we conducted three series of experiments in order to: (a) test the protocols in each particular scenario, (b) test the protocols overall adaptability. On the basis of originality, we selected three proactive protocols and four reactive protocols. In Fig 24, the average performances of the protocols are ranked from 0 to 10 respectively with the obtained results (10 being the best performance for the defined factor). It’s important to note that the overhead score in Fig 24 takes in consideration the sizes of the routing messages as well. Based on the recorded results, AOMDV is the most versatile protocol. The only inconvenience noticed while using this protocol, is the decline of its PDR especially during the nodes velocity experiment. This result is essentially due to the ability of AOMDV to postpone path reconstruction. While this approach is rewording from an overhead point of view, further improvement must be done in order to regulate / predict whether AOMDV must launch a path recovery or, rely on an alternative path. Moreover, though OLSR generates a massive overhead, this protocol averages a low path length with an impressive PDR. Thus in the next chapter, we first propose a simple mobility aware extension to improve AOMDV. Subsequently, a proactive protocol is implemented and tested to solve the complexity / overhead issue encountered with OLSR.
|
Table des matières
Chapter I: Routing In Dynamic Networks
I.I. Introduction
I.II. Proactive protocols
I.III. Reactive protocols
I.IV. Hybrid and hierarchical protocols
I.V. Recent advances
I.V.1. QoS Oriented Protocols
I.V.2. Energy Aware Protocols
I.V.3. Mobility Aware Protocols
I.V.4. Security Oriented Protocols
I.VI. Conclusion
Chapter II: Comparison of the MANET Routing Protocols
II.I. Introduction
II.II. Results and Discussion
II.II.1 The network growth
II.II.2 The increase of the network density
II.II.3 Number of transmission connections
II.II.4 Node velocity
II.III. Conclusion
Chapter III: Proposition for two Extended Protocols
III.I. Introduction
III.II. Mobility aware extension for the reactive protocols
III.III. Lowering the overhead and complexity of the proactive protocols
III.II.1 Routing messages treatment algorithm
III.II.2 Path update treatment
III.II.3 Deletion updates treatment
III.II.4 The routing information filter algorithm
III.II.5 Protocol testing
III.IV. Results and discussion
III.III.1 The network growth influence
III.III.2 The network density influence
III.III.3 Network members movement
III.V. Conclusion
Chapter IV: Proposal Of A Load Balancing Mechanism For Wireless Mesh Networks
IV.I. Introduction
IV.II. Routing in WMN: State of the Art
IV.III. Load balancing: State of the Art
IV.IV. A Load Balancing Algorithm For WMN Based On the Genetic Algorithm
IV.V. Overview on evolutionary computing
IV.V.I. Ant Colony Optimization
IV.V.II. Genetic Algorithm
IV.V.III. Chemical Reaction Optimization
IV.VI. Our Proposed Algorithm
IV.VII. Conclusion
Télécharger le rapport complet
