Assigning the values of K and TB based on the communications types

Link layer feedback failure feedback approach

Link failure detection delay in Hello based approach is in the order of one second. Crosslayer approach has been proposed in order to decrease the above detection delay. To provide a frame transmission service in wireless networks as reliable as in wired Ethernet networks, a retransmission mechanism has been implemented in the IEEE 802.11 MAC layer (Lindhorst, Lukas & Nett, 2010). Each frame transmission must be acknowledged by the receiver to ensure successful frame transmissions. If a frame is not acknowledged, it is retransmitted several times until an Acknowledgment is received. After a certain number of retransmissions, the frame is considered as a lost frame. We can use the above mechanism as a link failure detection approach by making the MAC layer information regarding frame transmission available to the routing layer. Thus, the routing layer can decrease the failure detection delay by using the MAC layer information regarding the frame transmissions and retransmissions. Physical data rate influences the transmission errors. As we increase the transmission rate, the transmission errors also increase. That is why low data rates are used for the last frame transmission in order to increase the chance that this frame is successfully received.

The IEEE 802.11 standards use several modulation techniques, which results in different physical data rates. Thus, the transmission rates are not fixed in IEEE 802.11 standards. Transmission rate algorithm has to adapt with the link quality variations, especially in wireless communications. In (Lindhorst et al., 2010) two failure detection models based on the Crosslayer approach was proposed. The first model is independent of the data transmission rates, while the second model is dependent on data transmission rates. On the following paragraph, we explain these two models in detail. The first model is FrmLoss. This model only considers complete frame losses and does not care about the transmission rates. A counter (np) is used to count the number of complete frame losses. This counter is incremented by one every time a frame loss occurs, and it is rested to the initial value when the frame is successfully transmitted. A link failure is assumed when np ≥ n? ???, otherwise the frame losses are due to interference is assumed. The second model is TxError. This model considers the transmission rates, erroneous frame transmissions, in addition to complete frame losses. A counter (ne) count the number of consecutive erroneous frame transmissions at the basic data rates only. ne is rested to the initial value when a frame transmitted either successfully at basic data rate or any other rate.

A link failure is assumed when ne≥n? ???, otherwise the frame losses are caused by interference is assumed. How fast the data rates adaptation algorithm switch to the basic data rate determines the detection delay in this model. In summary, (Lindhorst et al., 2010) proposed two cross-layer models that emphasized the importance of distinguishing between transient and permanent transmission errors to ensure correct link failure detections. They took into account the impact of the physical data rate and the data rate adaptation algorithm. High data rates provide the highest throughput, but at the same time the highest transmission error probability (Lindhorst et al., 2010). The challenge in the above two approaches is how to choose the appropriate threshold values for n? Their results show that the delivery probability strongly depends on the used modulation modes, and hence the physical transmission rates. The detection delay decreased from the order of one second to some millisecond was experienced by a test-bed experiment (Lindhorst et al., 2010). (Pandey, Pack, Wang, Duan & Zappala, 2007) proposed a Mobility Detection Algorithm (MDA). MDA is a cross-layer approach that helps MANET routing protocols determine the real cause of frame losses, whether they are due to link failures (mobility) or congestion. The main objectives in MDA are to reduce the routing overhead and to increase throughput. Another approach that can distinguish between the frame losses that are due to congestion or link failures is signal strength measurements (Goff, Abu-Ghazaleh, Phatak & Kahvecioglu, 2002); (Klemm, Ye, S. V. Krishnamurthy &Tripathi, 2005). As it is known, when a mobile node starts moving away from a neighbor, the signal strength measured at that neighbor starts decreasing till it reaches a certain threshold, and at that time that neighbor declares that the link has broken. The drawback of using signal strength measurements to determine broken links is the complications of fading, multipath effects, and power conservation mechanisms that affect the accuracy of signal strength measurements (Pandey et al., 2007).

Hello based link failure detection approach

Neighbor discovery detects link failures in the routing layer as a part of the routing protocols. Most proactive and reactive routing protocols detect link failures by means of Hello beacons. In proactive routing protocols, like Optimized Link State Routing (OLSR), to discover the nodes neighborhood and establish links to neighbor nodes, each node periodically sends Hello beacons to neighbor nodes. After that, information obtained through Hello beacons is propagated through the network. In this way, all nodes are aware of the whole network topology. When one node detects a failed link, this node declares this failed links to all neighbors. On the other hand, in reactive routing protocols like AODV, a route is determined on demand. However, when this route is established, link failures are also detected by means of Hello beacons during the rout connection period (Gomez et al., 2005a). Hello based link failure detection approach is the most used approach to detect link failure, even though the cross-layer using link layer feedback is faster in detecting link failures. This is due to many reasons. On the one hand, link layer feedback frequently misinterprets transient transmission errors as permanent transmission errors. On the other hand, Hello based link failure detection scheme is easier to implement in MANET routing protocols and it is a link layer independent (Tschudin, Gunningberg, Lundgren & Nordstrom, 2005); (Gomez, Cuevas, & Paradells, 2006), and it requires less memory and power resources (Gomez et al., 2005a).

Link failure detection scheme with Hello beacons works by periodically sending Hello beacons to all neighbors. If a node receives a certain number of successive Hellos, it considers the link as active, while if a node does not receive a Hello beacon or any kind of frames for a certain period of time, a certain number of successive missing Hellos, it considers the link as inactive. Based on that, the failure detection delay is determined by the Hello interval (TB), and the number of missing Hellos (K). Hello based link failure detection scheme is used in many WMNs and MANETs routing protocols to detect links failures and to maintain route connectivity (Perkins, Belding-Royer & Das, 2003) and (Bellur & Ogier, 1999). Traditionally, the routing protocols use fixed values of K and TB. For example, in AODV TB is chosen to be 1 second and K is chosen to be 2 (Gomez et al., 2006). Later in this thesis, we will see that the use of fixed values of K and TB is not the best choice. Some authors were aware that the classical behaviour of choosing fixed values for both TB and K might not be the best choice, and that was why they proposed some approaches to adaptively choose the TB. To the best of our knowledge, the proposals available in literature just adapted the TB parameter and ignored the K parameter to enhance Hello based link failure detection approach performance.

This was due to the fact that the researchers focus was on maintaining the routing table’s accuracy and not in specific link failure detection. In this thesis, we will consider both TB and K to enhance Hello based link failure detection approach performance. In the following, we introduce to some proposals that adapt the TB parameter. (Gome et al., 2006) proposed a two-state adaptive mechanism for link connectivity maintenance in AODV, namely Adaptive Hello Rate mechanism (AHR) algorithm to dynamically choose the Hello interval based on two parameters, Time to Link Failure (TLF) and Time Without Change (TWC). TLF and TWC parameters determine the link lifetime duration, and the dynamicity of the communication links, respectively. AHR algorithm has two states, the first one is a low dynamic state that uses low Hello rate, and the second one is a highly dynamic state that uses high Hello rate. This mechanism switches between these two states based on two thresholds. AHR enters the highly dynamic state when the estimated TLF become smaller than the first threshold; while it enters the low dynamic state, when TWC becomes greater than the second threshold. The difficulty in this mechanism is how to choose these two thresholds.

Table des matières

INTRODUCTION
CHAPTER 1 LINK FAILURE DETECTION APPROACHES
1.1 Related work
1.1.1 Link layer feedback failure detection approach
1.1.2 Hello based link failure detection approach
1.2 Mathematical analysis of Hello based link failure detection approach
1.2.1 Network model and assumptions
1.2.2 Mathematical analysis
1.2.3 Analytical framework
1.2.4 Multi-path packet delivery ratio
1.3 Evaluation
1.3.1 The effect of TB and K on the packet delivery ratio
1.3.2 The effect of the sending rate on the pdr and the achieved gain
1.3.3 The effect of the link failure rate on the pdr and the achieved gain
1.4 Assigning the values of K and TB based on the communications types
1.4.1 Introduction
1.4.2 The one route case
1.4.3 The two routes case
1.5 A novel enhanced Hello based link failure detection approach
1.5.1 The proposed algorithm
1.5.2 Evaluation
1.6 Proposed solutions to network recovery
1.6.1 Initial resource allocation method
1.6.2 Greedy channel assignments method
1.6.3 Interference aware channel assignments
1.6.4 Autonomous reconfiguration system
1.6.5 Enhanced reconfiguration system
1.6.6 Fault tolerant routing protocols
CHAPTER 2 RELIABLE ROUTING
2.1 Introduction
2.2 Related work
2.3 Adaptive greedy forwarding strategy in MANETs based on node density
2.3.1 Mathematical model analysis
2.3.2 One-way connectivity
2.3.3 Two-ways connectivity
CHAPTER 3 NETWORK RELIABILITY AND CONNECTIVITY
3.1 Introduction
3.2 Literature review
3.3 Ensuring reliable communications in MANETs with uniform random distribution
3.3.1 Mathematical model analysis
3.3.2 Evaluation
3.4 The random waypoint mobility model
3.5 Ensuring two routes connectivity with random waypoint mobility model
3.5.1 The hop count
3.5.2 Mathematical analysis
3.5.3 Evaluation
CONCLUSION
RECOMMENDATIONS
LIST OF PUBLISHED PAPERS
LIST OF BIBLIOGRAPHICAL REFERENCES

Télécharger le rapport complet