Chiraz Houaidia
email: chiraz.houaidia@cristal.rnu.tn

Hanen Idoudi

Adrien Van Den Bossche

Thierry Val
email: 4val@irit.fr

Leila Azouz Saidane
email: 5leila.saidane@ensi.rnu.tn

Impact of IEEE 802.11 PHY/MAC Strategies on Routing Performance in Wireless Mesh Networks

Keywords: Wireless mesh network, PHY/MAC protocols, Routing protocols

Current routing mechanisms proposed for adhoc networks are still feasibly applied in Wireless Mesh Networks given their similarities. Many researchers have conducted numerous simulations for comparing the performances of these routing protocols under various conditions and constraints. Most made comparisons are not aware of PHY/MAC layers and their impact on routing performances. In this paper we study through simulations the impact of PHY/MAC protocols on higher layers. The considered protocols include three propagation models, ie., FreeSpace, TwoRayGround and Shadowing, three different PHY/MAC protocols specified IEEE 802.11 standards namely, 802.11b, 802.11s and 802.11n, and finally three routing protocols, ie., AODV, OLSR and HWMP. In a comparative way, we investigate the effectiveness of these protocols when they coexist on a wireless mesh network environment. Our results show that the routing strategy can significantly impact the network performance only if it is strongly linked to the characteristics of the lower layers.

I. INTRODUCTION

W IRELESS Mesh Networks are a promising technology to provide broadband wireless Internet to a large number of users spread across large geographical regions. Due to their features of dynamic self-configuration, easy maintenance and low cost, WMNs promise larger coverage, improved performance, more reliability and better flexibility than classical wireless LANs. In fact, in rural areas, where broadband infrastructure is not available, WMNs may be a potential solution to provide these regions with a reliable Internet access based on multihop connections. In this context, the French association tetaneutral.net [19] has launched its project to cover the region of Toulouse in France in a meshed manner. This association is acting as a provider of Internet access, web hosting and a nonprofit operator and is aiming to allow and encourage internet connection sharing between neighbors by any means (cable, wireless, etc.). It offers also a technical solution allowing a secure access share. WMNs have a two-tier architecture based on multi-hop transmission and composed of two types of nodes: Wireless Mesh Routers (WMR) and mesh clients [START_REF] Hiertz | Principles of IEEE 802.11s[END_REF]. WMRs form a wireless meshed backbone network offering inter-user connectivity. They generally have minimal or no mobility and are equipped with multiple radio interfaces. Mesh clients, consisting of end devices like laptops, PDAs or phones, gain network access by associating to a WMR. When a mesh client wants to communicate with another, it may do directly or through mesh routers that allow multiple route opportunities.

Mesh networks share some characteristics with ad-hoc networks in the way that both are based on multi-hop communication and both are used to provide broadband access to Internet.

Reason for what, current MAC and routing mechanisms can still feasibly applied in WMNs. However, MANETs, evolved from an academic environment, focus essentially on node mobility, power constraint and related ad-hoc capabilities. In contrast, mesh networks, emerging from an industrial background, are focusing more on optimal deployment, wireless capacity, QoS and related backbone capabilities. Indeed, existing MAC and routing protocols do not support enough scalability, throughput and link quality. For these different aspects WMNs are gaining significant attention from both academic and business communities. In fact, researchers and industrial standards groups are revisiting, from a mesh perspective, existing protocols for wireless networking mainly IEEE 802.11 standards and are actively working on new specifications [START_REF]IEEE Standard for Information technology-Telecommunications and information exchange between systems Local and metropolitan area networks-Specific requirements Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications[END_REF].

Routing, particularly, has undergone extensive study since it represents a challenging issue for wireless mesh networks [6][7][8] [START_REF] Boukerche | Routing protocols in ad hoc networks: A survey[END_REF]. In fact, in a multi-hop network, routing extends network connectivity to end-users. Thus, an efficient path selection must be done while optimizing network resources and satisfying users QoS requirements. However, with an unstable radio environment, a shared medium and a varying link capacities limited by interference, routing performance issues in a WMN are increasingly challenging. Packet losses, throughput degradation due to intra-flow and inter-flow interference, congestioned links, etc., are among several problems identified in WMNs and issued generally from lower layers. To guarantee then an efficient data routing in the network, one should, first, properly characterize the impact of environmental factors and PHY/MAC attributes on higher layers and second adapt the design of the routing metric to better control influenced parameters.

In this paper, we try to check the efficiency of conventional routing strategies under lower layers and whether the choice of PHY/MAC/Routing protocols all together affects the relative performance of the network. The considered protocols include three propagation models [START_REF] Rhattoy | The impact of propagation environment and traffic load on the performance of routing protocols in Adhoc networks[END_REF], ie., FreeSpace, TwoRayGround and Shadowing, three different PHY/MAC protocols specified IEEE 802.11 standards namely, 802.11b [START_REF]IEEE Standard for Information technology-Telecommunications and information exchange between systems Local and metropolitan area networks-Specific requirements Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications[END_REF], 802.11s [START_REF] Hiertz | Principles of IEEE 802.11s[END_REF] and 802.11n [START_REF] Wang | IEEE 802.11n MAC Enhancement and Performance Evaluation[END_REF], and finally three routing protocols, ie., AODV [START_REF] Perkins | Ad hoc On-Demand Distance Vector (AODV) Routing[END_REF], OLSR [START_REF] Clausen | Optimized Link State Routing Protocol (OLSR)[END_REF] and HWMP [START_REF] Bahr | Proposed routing for IEEE 802.11s WLAN mesh networks[END_REF]. The remainder of this paper is organized as follows: In section II, we present the routing challenges in wireless mesh networks. The simulation results and analysis appear in Section III. We conclude with Section IV.

II. ROUTING CHALLENGES IN WIRELESS MESH NETWORKS

Despite the availability of several ad-hoc routing protocols, the design of routing protocols specifically for WMNs is still an active and challenging research area. In fact, from a routing perspective, WMNs present a particular topology and different application domains and thus specific requirements and expectations. The main challenging considerations in mesh routing are:

• Network topology: similarly to MANETs, communication in WMNs is performed through hop-by-hop wireless transmissions. However, unlike MANETs, WMNs offer a static backbone for routing and thus routing protocol should perform an adequate mobility management.

• Inter-path interference: unlike wired networks, wireless links in a WMN are particularly affected by environmental conditions, noise resulting in interference between disjoint paths and hidden/exposed terminal problems. For that reason, this parameter should be well addressed in the routing metric.

• Channel diversity and radio-diversity: in WMNs, channel diversity, which is not supported in traditional MANETs, is introduced in order to increase the overall throughput and to reduce inter-nodes interference. Providing a node with multiple radios enables it to transmit and receive simultaneously or transmit in multiple channels simultaneously. So, to properly support this feature, additional management rules (like channel switching) should be included into the routing process.

• Routing strategy: similarly to ad-hoc networks, routing strategy can be either proactive, reactive or hybrid. The choice depends on the network density, the node mobility, the related overhead and user requirements. Each routing class has its particular functioning such as route discovery, route maintenance and related control messages, acknowledgment strategy, route update frequency etc. Hence, such choice can be determinant in the overall network performance. When taking into account these parameters, routing protocols should fulfill several requirements, including, (i) High throughput, (ii) Low average latency, (iii) Heterogeneous traffic (e.g. data, voice, and video), and (iv) Support for QoS.

Nevertheless, if we consider a realistic context, it is not meaningful to speak about a routing protocol in isolation.

Routing performance is considerably related to MAC and PHY layer design. To have an efficient routing layer, an overall view of the MAC and PHY parameters should be provided in order to control lower layers settings and discuss possible improvements. Some solutions based on cross-layer approach are proposed to deal with this separation between layers [START_REF] Paris | EFW: A cross-layer metric for reliable routing in wireless mesh networks with selfish participants[END_REF] [START_REF] Conti | Cross-Layering in Mobile Ad Hoc Network Design[END_REF].

III. PERFORMANCE EVALUATION

In this section, we propose to evaluate the netwrok performances under different PHY/MAC/Routing strategies and parameters. In a comparative way, we try to test the possible interaction and coexitence of some protocols in a wireless mesh environment and how does this impact the network performances. This study would be validated, in a future work, by experiments on real platform of tetaneutral.net [19].

A. Simulation Setup

The simulations were performed using the ns-2 simulator modified to support the 802.11n features [16][17]. Different protocol stacks are considered as described in the figure 1: The network layer is represented by AODV, OLSR and HWMP routing protocols (HWMP is implemented at layer two but is considered here as a routing protocol for organisational reasons). For the MAC layer, we varied the configuration between the mesh architecture based on 802.11s amendement, the MAC part of the 802.11n and the 802.11 standard. Concerning the physical layer, we considered, on the one hand, both 802.11b and Multi-Input Multi-Output (MIMO) [START_REF] Zheng | IEEE 802.15.5 WPAN Mesh Networks[END_REF][10] technology associated to 802.11n standard [START_REF] Wang | IEEE 802.11n MAC Enhancement and Performance Evaluation[END_REF], while varying on the other hand, the propagation models between TwoRayGround, FreeSpace and Shadowing models. For all the scenarios we have used a square topology of 500x500m 2 with randomly deployed static nodes. We varied both the number of nodes (20-40-60-80-100) and the traffic load (10-30-50-70 % of pairs from total number of deployed nodes). We used a constant output (CBR) related to UDP protocol. For the MIMO configuration, nodes are equipped with 2 antennas at both transmitter and receiver (i.e. 2x2 MIMO). We consider both A-MPDU and A-MSDU are enabled. The maximal A-MSDU length is set to 1024 Bytes (i.e two packets of 512 Bytes). Since the initial size of a packet does not exceed 512 Bytes, aggregation then occurs only when the node acts as a router, when it has in its queue at least two packets to the same destination. Data rate is set to 96 Mbps. Using 802.11b physical layer, the bandwidth is set to 2Mbps.

For the 802.11s mesh topology, we assume a network with one MPP set in the network center. Nodes used RANN proactive signalization to get connected to the MPP.

Table1 summarizes the simulation parameters.

B. Simulation Results And Analysis

1) End to End Delay: Figure 2 shows the average end to end delay for the different considered combinations of PHY, MAC and Network layers while increasing the number of deployed nodes and the traffic load in the network. The delay is expressed in milliseconds and it includes all possible delays caused by buffering, queuing at the interface queue, retransmission delay at the MAC layer, propagation and transfer time.

The results show that, for all possible PHY/MAC/Routing protocol stacks, the end to end delay increases with the network size. This increase is particularly important with HWMP+802.11s. This can be explained from a routing point of view by the hybrid character of HWMP: In fact, on the one hand, delays generated at every Path Request increase naturally with the number of hops. On the other hand, with only one MPP in the network, delays of queuing and buffering may also get higher with the number of nodes in the network.

For small networks, the different considered stacks have the same temporel behavior. However, with larger networks, the pattern begins to distinguish from one combination to another: networks based on routing protocols associated to 802.11n MAC layer and MIMO technology achieved the least delay. This is due essentially to the links capacity and the rate offered by the physical layer. Networks based on the 802.11 and 802.11s generate similar delays with a slight difference relative to the used routing protocol : AODV and HWMP achieved the higher delays compared to OLSR.

The difference between the delay of a light traffic and that of the heavy traffic is none other than the buffering delays which increase with the number of pairs communicating at the same time in the network.

The figure 3 shows more the difference between, on the one hand, reactive and proactive routing protocols and on the other hand, 802.11 and 802.11n MAC layer effects. For OLSR, the average end to end delay increases slightly for the same size except for high network size (100 nodes). In fact, by increasing the number of nodes in the network, the neighborhood changes and the number of hops between source and destination also increases. Thus, delays caused by buffering and queuing delays at intermediate nodes contribute largely in the average end to end delay. Regarding the traffic load, the delay increase is relatively slight. This is because packets are crossing the same path within the same size even when the traffic is getting higher.

The pattern of the average end to end delay is the same for AODV. It grows slightly with the number of nodes for the same reason that the number of hops also increases. However, particularly for AODV the delay increases considerably with the traffic load. This result was expectable since for each new pair of nodes communicating in the network, delays for the route discovery are included. The proactive nature of OLSR allows this protocol to quickly discover the optimal route and then the transmission time of packets takes less time compared to reactive protocols (AODV) which explains the better performance of OLSR in terms of delay. The frame aggregation of the IEEE 802.11n protocol results in a great gain in the end to end delay which is considered very low in all cases compared to delays generated using 802.11 based network.

2) Loss Rate: Figure 4 shows the loss rate. It represents the number of packets discarded among all transmitted packets. The pattern of loss rate is the same for both AODV and OLSR.

We notice that all routing protocols do not perform well under all propagation models when the network conditions become stressful, e.g. heavy congestion. The results also reveal that while the FreeSpace model provides the best performance in terms of packet delivery, the shadowing model achieves the highest loss rates for all routing protocols. The shadowing bad performance is due to the low intensity of the signal caused by possible obstacles. This results in the packet loss on weak links, displays wrongly the links disconnection and leads to the interruption and thus the dire need to set up a new itinerary.

3) Normalized Routing Load: Figure 6 shows the normalized routing load. It reflects the number of routing packets transmitted per data packet delivered at the destination.

We can see from these results the clear and significant increase in the routing overhead generated by HWMP compared to that of AODV and OLSR regardless of the lower layers and the three types of traffic loads. This disparity is due to the hybrid feature of the protocol since it uses the two types of control messages (the proactive and the reactive one). The routing load pattern is the same for all schemes which leads us to conclude that the PHY/MAC have no significant impact on this performance metric.

However, results in the figure 8 reveal some difference according to the routing mechanism. Since the route discovery mechanism of AODV is based of Route REQuest flooding, it follows that the overhead generated by this protocol increases rapidly and significantly with the number of nodes in the network, because, for a given flow between a source and a destination, when the number of intermediate nodes which are diffusing the Route REQuest gets higher, naturally the overhead generated increases. As well, for a higher traffic load across a very large network (100 nodes), AODV generates a peak of routing load.

4) Throughput:

The throughput is given in the figure 10. It is expressed in kbits per second and it measures the total number of received packets during the simulation period.

The throughput achieved by the 802.11n based schemes is significantly better than that of 802.11 and 802.11s. This is due essentially to the rate offered by the physical layer. Pattern of throughput within 802.11 and 80.11s based networks is the same as both use the same physical layer which is 802.11b.

When traffic increases, the network throughput relative to the 802.11n increases with the load to consume all the useful throughput. However, the throughput in 802.11/802.11s based networks maintains a certain stability or decreases in some cases.

The results show also that, regardless the load, the throughput for AODV decreases for denser networks. This behavior is characterized as normal because of channel saturation, meaning the resources are limited to the impending demand. For an important traffic, the pattern is the same and throughput remains almost constant on optimal values. OLSR, however, performs better with higher traffic load. It maintains a good throughput at all cases. The throughput offered by the MIMO technology has a great impact on the general network throughput which is relatively high and suitable for data transfer applications.

IV. CONCLUSION

In this paper, we studied the impact of PHY/MAC/Routing strategies on the performance of multi-hop wireless mesh networks. We combined the routing protocols (AODV, OLSR and HWMP) with the MAC strategies (802.11, 802.11n and 802.11s) along with different PHY technologies and models (802.11b, MIMO technology, FreeSpace, TwoRayGround and Shadowing propagation models). We found out that, to achieve good performance in the network, all the parts and parameters of the protocol stack must be considered together.

According to the simulation results, we may state that the different propagation models have a considerable impact on the performance of the network. The latter decreases rapidly when the fading models, mainly Shadowing model, have been taken into consideration.

The throughput offered by the MIMO technology has a great impact in the general network throughput which is suitable for data transfer applications. The frame aggregation of the IEEE 802.11n protocol, on the other hand, results in a great gain in the end to end delay which is considered very low in all cases.

Results also revealed that from a routing perspective, there is a notable superiority in the general performance of OLSR, particularly when the network gets denser, although further study of others topologies is needed to validate this conclusion. Some performance results can be explained by the lack of mobility in our topologies. Proactive routing protocols can be less efficient in dynamic networks compared to reactive protocols particularly when talking about overhead and routing load. HWMP is still very sensitive to the network traffic and size, its scalability is not guaranteed and its performance may be affected if the network size is not correctly adjusted.

Based on these observations, our future interest will be oriented to cross-layer proposals and dynamic routing metrics which adapt to the lower layers. Our contributions will be tested as part of the project tetaneutral.net. From a PHY/MAC level, our choice will be IEEE 802.11n protocol in order to take advantage of MIMO technology, the high capacity of the channel and the two proposed aggregation mechanisms. Given the number of nodes in the tetaneutral.net network and the lack of mobility at some nodes, we are interested to OLSR as first choice of the routing protocol.

Fig. 1 :

 1 Fig. 1: Protocol Stack.

Fig. 2 :Fig. 3 :Fig. 4 :Fig. 5 :Fig. 6 :

 23456 Fig. 2: End to End Delay by traffic load, (a) Low traffic charge (b) Medium traffic charge (c) High traffic charge.

Fig. 7 :

 7 Fig. 7: Throughput by traffic load, (a) Low traffic charge (b) Medium traffic charge (c) High traffic charge.

TABLE I :

 I Simulation Parameters

	Paramater	Value
	Simulation Time	100s
	Topology	500x500m
	Number of nodes	20-40-60-80-100
	Radio Range	250m
	Packet Size	512 Bytes
	Packet generation interval	0.005s
	OLSR-Hello-interval	2s
	OLSR-TC-interval	5s


Chiraz Houaidia
email: chiraz.houaidia@cristal.rnu.tn

Adrien Van Den Bossche

Hanen Idoudi
email: 3hanen.idoudi@ensi.rnu.tn

Thierry Val
email: 4val@irit.fr

Leila Azouz Saidane
email: 5leila.saidane@ensi.rnu.tn

Link Availability Aware Routing Metric For Wireless Mesh Networks

Keywords: Wireless Mesh Network, Routing Metrics, OLSR, Testbed, IEEE 802.11n

This paper investigates the design of effective routing metrics in the purpose of network resources optimization and the satisfaction of users QoS requirements. Using several real experiments, we point out the shortcoming of the Expected Transmission Count (ETX) metric for eventual optimizations towards a more efficient routing. Experiments were carried out into an heterogeneous IEEE 802.11n based network running with OLSR routing protocol and have shown that ETX presents several shortcoming resulting in inaccurate estimation of the link quality and then of the routing decision. This paper presents improvements of the ETX metric based on link availibility for accurately finding high-throughput paths in multihop wireless mesh networks.

I. INTRODUCTION

Wireless Mesh Networks (WMNs) are a flexible, quickly deployable wireless networking solution that benefits from the lack of a rigid infrastructure. They are used to provide rural areas, where broadband infrastructure is not available, with a reliable Internet access based on multihop connections. Compared to adhoc networks, the main difference consists of the use of typically stationary wireless routers (backbone) to interconnect isolated LANs. These backbone nodes usually do not have strict constraints on power consumption, so, mobility and power savings are no longer the main problems in WMNs. For that reason, wireless mesh routing protocols are more and more optimized to consider link-quality metrics such as transmission capacity or error probability instead of simplistic hop-count metric used generally with adhoc networks. This new paradigm is called quality-aware routing

The design of effective routing metrics, however, must be done while optimizing network resources and satisfying users QoS requirements. It depends also on the specific characteristics of the target network. For example, due to the shared nature of the wireless medium, a wireless link in a mesh network does not have dedicated bandwidth since neighboring nodes' transmissions may also contend for the same bandwidth. Therefore, routing performance issues in a WMN are increasingly challenging and routing metrics, particularly, This work is carried out as a part of the project tetaneutral.net must be able to capture the interference between competing flows. Packet losses, throughput degradation, congestioned links, etc., are among several problems identified in WMNs and issued generally from lower layers.

Several link-quality routing metrics [START_REF] Ghannay | Multi-radio multichannel routing metrics in IEEE 802.11s-based wireless mesh networks -And the winner is[END_REF] have been proposed and evaluated by simulations, but only a few have been implemented and evaluated in real networks [START_REF] Campista | Routing metrics and protocols for wireless mesh networks[END_REF] [START_REF] Esposito | Implementing the Expected Transmission Time Metric for OLSR Wireless Mesh Networks[END_REF]. Among implemented mesh routing metrics, we are interested to ETX [START_REF] Couto | A highthroughput path metric for multi-hop wireless routing[END_REF].

The focus of this paper is to investigate the requirements for designing routing metrics in mesh networks to support high network performance, such as high throughput and low packet delay. The purpose of this paper is to setup and configure a real IEEE 802.11n [START_REF] Wang | IEEE 802.11n MAC Enhancement and Performance Evaluation[END_REF] based WMN testbed [12] and to evaluate, in a comparative way, the OLSR performances under different metrics.

The remainder of this paper is organized as follows: We describe some routing metrics in section II mainly the ETX metric. Section III presents a measurement based evaluation of ETX metric in order to point out its shortcoming and ways towards its optimization. We finally present some improvements of ETX metric in section IV.We conclude by Section V.

II. RELATED WORK

The design of effective routing metrics depends on the characteristics of the target network. For example, the severe energy constraints of sensor networks require the design of energy efficient routing metrics. Such metrics respect the emergency character of some applications and the resources availability.

In ad hoc networks, where mobility and topology changes are the main problems, the most convenient metric is hop count. This metric, coupled with a routing strategy, allows a fast recovery of instable routes due to link breakage. However, this shortest-path routing approach implicitly assumes that links either work perfectly or do not work at all.

For wireless mesh backbone, where routers are relatively stationnary and the wireless medium is shared, mesh routing protocols are optimized to consider link quality metrics in order to ensure high throughput and low packet delay.

New metrics, such as ETX, ETT, WCETT, MIC, etc. [START_REF] Ghannay | Multi-radio multichannel routing metrics in IEEE 802.11s-based wireless mesh networks -And the winner is[END_REF], are proposed towards a quality-aware routing, in order to reflect more the link variations such as transmission capacity, loss probability, interferences, etc.

The research community has a particular interest in ETX metric [START_REF] Couto | A highthroughput path metric for multi-hop wireless routing[END_REF]. Indeed, this metric has been the subject of several performance studies and several implementations and integrations in real platforms. In this work, we mainly focus on this research effort and rely on the study of the limitations of this metric and propose improvements.

The Expected Transmission Count (ETX) metric is a proposal to find the route with the highest probability of packet delivery. It represents the number of times a node expects to transmit and retransmit a packet for a successfull delivery. The ETX metric considers the asymetric property of wireless links and is computed as follows :

ET X = 1/(d f × d r ) (1)
Where d f and d r are respectively the forward and the reverse delivery ratios of the link.

To estimate d f and d r , nodes broadcast small-size probes at an average period τ during a time window ω so that each node knows how much probes it should receive during this period which is τ /ω. The probe contains the number of received probes for each neighbor during the last ω. So, each receiving node becomes aware of the forward delivery ratio for each link. This information is then diffused to make all neighbors aware of the ETX of the link. The best link quality is the link with the smallest ETX i.e with the smallest loss probability. The ETX of a route is the sum of the link metrics.

This metric was well studied by real experiments under different testbeds [START_REF] Campista | Routing metrics and protocols for wireless mesh networks[END_REF] [START_REF] Esposito | Implementing the Expected Transmission Time Metric for OLSR Wireless Mesh Networks[END_REF]. One of the most popular implementations is that with OLSR. One of the most-known implementations of OLSR [START_REF] Clausen | Optimized Link State Routing Protocol (OLSR)[END_REF] is OLSRd program (OLSR daemon) [13] which implements basically hop count and ETX as metric.

III. TESTBED AND EXPERIMENTAL RESULTS

As part of this work, we conducted a series of tests in order to evaluate OLSR-ETX performances in a real IEEE 802.11n based wireless mesh network and accurately adress the limitations of such metric.

We run experiments in an indoor testbed formed by seven nodes: four shuttles, two personal computers and one nanostation router. Device configurations are shown in Table I. All nodes are 2x2 MIMO devices equipped with the ath9k driver and are using OpenWRT operating system. The included driver provides enough features for our implementation as well as for future improvements. All nodes are configured to use the channel 9 in the IEEE 802.11n mode. The OLSR routing protocol is implemented natively in the OpenWRT operating system as an OLSR deamon (olsrd). This implementation is improved to offer both the use of the Hop Count and the ETX metrics. Our testbed called BlueMeLab [12] is deployed at the University Institute of Technology (IUT) Blagnac-Toulouse. The nodes are spread over two floors of the building (cf. Figure 1). Rooms are separated by thick bricked walls. It is worthy mentioning that there are other wireless networks in the area.

The choice, then, of the channel was made essentially in order to avoid interferences with existant networks and garantee a certain accuracy of our results. As mentioned above, olsrd implements natively the hop count and the ETX metrics. To measure ETX, olsrd, instead of creating new probe messages, uses HELLO and TC messages of OLSR which are sent periodically each 2s and 5s respectively. This method aims to avoid extra overhead. A multitude of monitoring tools were offered by the ath9k driver and used in our experiments. The iperf tool was used to generate TCP and UDP traffic at different rates between pairs of nodes and measure bandwidth, jitter, packet loss, etc. tcpdump and Wireshark tools were used to dump the traffic in the network and give a description of the contents of packets. iw configuration utility was used to get device capabilities and set parameters and statistics. All the performance evaluation in this paper are the result of measurements taken on the wireless testbed presented hereby.

With ETX metric, the link quality estimation is based on small probe size (some bytes) which doesn't properly reflect the data loss probability. In fact, such measurement underestimates data loss ratios and over-estimates ACK loss ratios. In real scenarios, the packet loss rate and delay are largely higher while increasing the traffic load or the packet size. Moreover, ETX link probes are susceptible to MAC unfairness and route ETX measurements may change under load. These observations are detailed by experimentations in a previous work [START_REF] Houaidia | Experimental Performance Analysis of Routing Metrics in Wireless Mesh Networks[END_REF].

On the other hand, ETX assumes all links run at one bit-rate and probes are sent in broadcast at the network basic physical rate. So, this metric assumes a robust physical layer which is not the case at all. When links data rates are not accounted for, a short path with lower ETX may be chosen over another longer path with higher ETX albeit the latter may be able to support a higher overall throughput and less end-to-end delay. Based on the topology below (cf. Figure 2), we demonstrate the limitations of ETX Sum using experiments of four different paths. Consider the four ad hoc paths shown in Fig. 3 where the send rate of each source node is the maximal one-hop data rate of IEEE 802.11n. TCP traffic is used to get the throughput achieved by each path. First, consider Path A and Path B. Both are 3-hop paths but the ETX Sum of Path A is larger than that of Path B. According to OLSR-ETX, Path B will be selected as the better route to reach node N16 from node N17 while, in reality, the throughput of Path A is approximately 230 % higher than that of Path B.

Second, consider Path C and Path D. Path C is 3-hop route but because of the bad quality of the link (N17, N20), its ETX Sum is higher than that of Path D which is 4-hop route. According to OLSR-ETX, Path D is selected whenever it is longer.

These simple examples show that an ETX Sum metric cannot accurately differentiate paths with different achievable data rates. The main reason is that, ETX is an interference insensitive metric. In fact, when successive hops have different loss rates, the transmission interference of the two nodes is different. The changed transmission interference considerably affects the achievable data rates. ETX Sum is unable to capture this phenomenon.

Further more, a total Sum of ETXs is too simplistic and not always efficient. A route with an ETX equal to 3 (ETX=3.0) doesn't mean that this route is made of three hops nor that it is longer than a route with an ETX equal to 2 (ETX=2.0). Fig. 4: ETX SUM Vs Path length Fig. 4 shows the ETX Sum and hop length of each path from 42 total paths according to our topology. We find that, for nhop paths, ETX Sum is between n and 2n. Particularly for paths longer than four hops, their ETX Sums are quite larger than their hop lengths.

IV. ETX IMPROVMENTS

To overcome the limitations of ETX, a first step would be to take into account the aspect of "multi-rate" in the choice of the link. Indeed, traffic should be routed into the best highspeed links in order to achieve the best possible end-to-end throughputs and delays.

Another aspect one should consider is the link availability and/or occupancy to propose a load-sensitive and loadbalancing routing. In fact, based on the occupancy estimation of a link, the routing protocol would avoid congestioned routes and select links which are "freer" and the most available to transmit data traffic in order to garantee reliability. Such information reflects the possible congestion or interference phenomenon that may affect the data packet delivery.

Using this information of link occupancy, only links with reduced occupancy are selected to form a route between a source node and a destination node so that routing decision is based on link's availability to support more traffic flows. Bottelneck or lossy links with high occupancy rates are supposed to bad links.

Since the link occupancy information is inable to measure accurately the capacity of a link to support a specific amount of data, we should account for the residual link capacity to adapt the transmission relatively to the link capacity.

V. CONCLUSION AND FUTURE WORK

This paper presents the shortcomings of ETX and the challenging aspects in the design of an effective routing metric for WMNs. By taking into account the PHY/MAC diversity of nodes, we focused on the shortcomings of these metrics to adapt a heterogeneous environment.

This paper provides a measurement-based performance evaluation of the OLSR protocol using different metrics such as hop-count and ETX. Results have shown the inability of ETX to measure accurately the link quality and then the routing decision. Results obtained are related to the considered topology, further study of other topologies is needed to validate this conclusion. Although, our results remain coherent with other works [START_REF] Esposito | Implementing the Expected Transmission Time Metric for OLSR Wireless Mesh Networks[END_REF] [START_REF] Sinky | Implementation and performance measurement and analysis of OLSR protocol[END_REF].

We presented, then, improvements and optimizations of this metric towards a link availibility aware routing. Our improvements are load-sensitive and aim to fairly distribute the traffic load between nodes in the network while taking into account their occupancy and availability.

Future work will consist of the proposal of a link availibility aware routing metric and an adaptive routing protocol taking into account this metric. Further contributions will be validated by simulation, prototyping and then deployed on the real mesh network deployed tetaneutral.net [14] in Toulouse, France which offers a more realistic environment, traffic and wireless contraints. It allows us also to check the scalability of our proposal when deployed in a large scale network.

Fig. 1 :

 1 Fig. 1: The Testbed

Fig. 2 :Fig. 3 :

 23 Fig. 2: The Testbed Topology

TABLE I :

 I CONFIGURATION OF DEVICES USED ON THE TESTBED

	Device	Operating System	Processor	RAM
	Computer	OpenWRT	Intel Pentium 4	2Go
		(GNU/Linux)	CPU 3.2GHz
	Shuttle	OpenWRT	Intel Pentium 4	904Mo
		(GNU/Linux)	CPU 3.00GHz
	NanoStation	OpenWRT	Atheros MIPS	16MB SDRAM
	Router	(GNU/Linux)	180MHz	4MB Flash

TABLE II :

 II RESULTS OF EXPERIMENTATIONS

	Path	ETX SUM Throughput (Mbits/sec)
	PathA	3.191	15.12
	PathB	3.000	6.5
	PathC	4.488	5.74
	PathD	4.316	6.2

ACKNOWLEDGMENT

This work is carried out as a part of the project tetaneutral.net. Further contributions will be tested in the real network. Authors would like to thank the project's manager support, Laurent Guerby.


Chiraz Houaidia
email: chiraz.houaidia@cristal.rnu.tn

Adrien Van Den Bossche

Hanen Idoudi
email: 3hanen.idoudi@ensi.rnu.tn

Thierry Val
email: 4val@irit.fr

Leila Azouz Saidane
email: 5leila.saidane@ensi.rnu.tn

Novel Link Availability Aware Metrics for Routing in Wireless Mesh Networks

Keywords: Wireless Mesh Network, QoS Routing, Routing Metrics, Interference, Testbed

This paper presents two novel metrics, Link Occupancy aware routing Metric (LOM) and Residual Link Capacity based routing metric with Interference Consideration (RLCIC), for accurately finding high-throughput paths in multihop wireless mesh networks. The first metric is load-sensitive and aims to balance the traffic load according to the availability of a link to support additional flows. The second metric reproduces better the capacity of a link since it is based on its residual bandwidth. It captures accurately the available path bandwidth information when considering both the intra-flow and the interflow interferences. Using several real experiments carried out into an heterogeneous IEEE 802.11n based network running with OLSR routing protocol, we have shown that our first proposal can accurately determine better paths in terms of throughput and delay, thereby significantly outperforming the other existing metrics. The consistency of the second metric RLCIC is proved formally based on notions of graph theory.

I. INTRODUCTION

Wireless Mesh Networks (WMNs) are a flexible, quickly deployable wireless networking solution that benefits from the lack of a rigid infrastructure. They are used to provide rural areas, where broadband infrastructure is not available, with a reliable Internet access based on multihop connections. WMNs are composed of typically stationary wireless routers (backbone) to interconnect isolated mesh LANs. The lack of mobility and power constraints made wireless mesh routing protocols more and more optimized to consider link-quality metrics such as transmission capacity or error probability instead of simplistic hop-count metric used generally with adhoc networks. This new paradigm is called quality-aware routing.

Providing efficient quality of service (QoS) support is essential for such networks, as they need to deliver realtime services like video, audio, and voice over IP besides the traditional data service. Then, identifying paths with maximum available bandwidth is one of the main issues concerning QoS in WMNs. The available path bandwidth is defined as the maximum additional rate a flow can push before saturating its path [START_REF] Salonidis | Identifying High Throughput Paths in 802.11 Mesh Networks: A Model-Based Approach[END_REF]. We focus mainly, on the one hand, on finding the This work is carried out as a part of the project tetaneutral.net widest path to transmit one flow without violating the existing flow's bandwidth guarantee.

On the other hand, since it is not possible in large wireless networks to separate concurrent transmissions completely in frequency, some transmissions will necessarily occur at the same time in the same frequency band and the signals from many undesired or interfering transmitters are added to the desired transmitters signal at a receiver. This interference can be controlled in a centralized manner with an efficient scheduling algorithm. However, wireless communications may require, from MAC level, distributed solutions based on carrier sensing concept or, from routing level, interference aware routing metrics. We focus mainly on finding the widest path when accouting for intraflow and interflow interferences.

The purpose of this paper is to investigate the requirements for designing routing metrics in mesh networks to support some QoS requirements, such as high throughput and low packet delay. We proposed and implemented two novel metrics that we added to OLSRd program (OLSR daemon) [2], one of the most-known implementations of OLSR [START_REF] Clausen | Optimized Link State Routing Protocol (OLSR)[END_REF] which implements basically hop count and ETX [START_REF] Couto | A highthroughput path metric for multi-hop wireless routing[END_REF] as metric. An interference aware version of the second routing metric is formally proved with notions of graph theory.

The remainder of this paper is organized as follows: Section II presents an overview of the most known routing metrics for WMNs. Section III presents our proposals with experimental results showing its performances when compared to hop-count metric and ETX metric. Section IV presents the design of our residual link capacity based routing metric with interference consideration. We conclude by Section V.

II. RELATED WORK

In ad hoc networks, where mobility and power saving are the main problems, the most convenient metric is hop count. This metric, coupled with a routing strategy, allows a fast recovery of instable routes due to link breakage. On the other hand, as mesh routers are, most of the time, stationary, wireless mesh routing protocols are optimized to consider link quality metrics [START_REF] Houaidia | Experimental Performance Analysis of Routing Metrics in Wireless Mesh Networks[END_REF]. New metrics, such as ETX, ETT, WCETT, MIC, etc. [START_REF] Ghannay | Multi-radio multichannel routing metrics in IEEE 802.11s-based wireless mesh networks -And the winner is[END_REF], are proposed towards a quality-aware routing, in order to reflect more the link variations such as transmission capacity, loss probability, interferences, etc.

The Expected Transmission Count (ETX) metric [START_REF] Couto | A highthroughput path metric for multi-hop wireless routing[END_REF] is a proposal to better suit wireless networks where link fluctuations and packet losses are inevitable. It represents the number of times a node expects to transmit and retransmit a packet for a successfull delivery.

With ETX metric, the link quality estimation is based on small probe size (some bytes) which doesn't properly reflect the data loss probability. Moreover, ETX assumes all links run at one bit-rate and probes are sent in broadcast at the network basic physical rate. So, this metric assumes a robust physical layer which is not the case at all [START_REF] Houaidia | Experimental Performance Analysis of Routing Metrics in Wireless Mesh Networks[END_REF].

To cope with some of these problems, authors in [START_REF] Draves | Routing in multi-radio, multi-hop wireless mesh networks[END_REF] proposed Expected Transmission Time (ETT) metric. The ETT of a link is defined as the expected MAC layer duration for a successful transmission of a packet. By accounting for both the link capacity and quality of a link, this metric offers a better estimation and ensures both reliability and efficiency. However, this metric is still not considering interferences and availability of a link.

Weighted Cumulative Expected Transmission Time (WCETT) [14][16] is the first multi-channel metric for mesh networks. It is determined by the amount of time used by a frame to attend a destination and the maximum time period consumed on links sharing the same channel. The main motivation for WCETT was to specifically reduce intra-flow interference by minimizing the number of nodes on the same channel in the end-to-end path. However, WCETT is a non isotonic metric and requires complex routing protocol to calculate the minimum cost. The isotonicity property is introduced in [START_REF] Hou | Hop-by-Hop Routing in Wireless Mesh Networks with Bandwidth Guarantees[END_REF]: Following the WCETT metric, a new metric, the Metric of Interference and Channel Switching (MIC) [START_REF] Ghannay | Multi-radio multichannel routing metrics in IEEE 802.11s-based wireless mesh networks -And the winner is[END_REF] was proposed. It aims to capture both the intraflow and interflow interferences. Composed of two major parts, it ensures that minimum weight paths can be found by both Bellman-Ford and Dijkstras algorithms and no forwarding loop can be formed in linkstate routing. MIC is, however, non isotonic and may require decomposition into isotonic link weight assignments in a virtual network and hence efficient algorithms can be used to find minimum weight paths. Among these metrics, some improvements of ETX, such as ETT metric, only consider the total capacity of a wireless link and do not account for possible degradation of the bandwidth due to interferences or parallel data transmissions. Some other proposals only treat the intraflow or the interflow interferences but not both at the same time. We have made, in a previous work [START_REF] Houaidia | Experimental Performance Analysis of Routing Metrics in Wireless Mesh Networks[END_REF], an experimental performance study of some of the proposed metrics and based on the results found we propose, in this work, new routing metrics specifically designed for wireless mesh networks. These metrics aim to accurately measure the available capacity of a link when taking into account both the current use of the link and possible interferences with neighboring links.

III. LINK AVAILABILITY AWARE ROUTING METRICS

A. Link Occupancy Aware Routing Metric

The purpose of our first metric is to measure the occupancy level of a link and, based on this estimation, select links which are "freer" and the most available to transmit data traffic. For that, we model our network as an oriented graph G = (E, V ) where E denotes the set of links and V denotes the set of vertices representing the network's nodes. This model allows us to consider bidirectional traffic. We define Link Occupancy Ratio (LOR) as the load of a link i.e. the amount of data traffic occupying the link during a time window ω in both forward and reverse directions. If a link is not used by any flow, its LOR would be theoretically equal zero and its total capacity is available for data transmission. Such "free" link would be a potential alternative for current flow transmission so that we avoid overloaded routes where risk of congestion and data loss is inevitable.

The LOR of the link l between two nodes n 1 and n 2 is expressed as follows :

LOR l = T x (n1,n2) B (n1,n2) × ω + T x (n2,n1) B (n2,n1) × ω (1)
Where T x (n1,n2) and T x (n2,n1) are respectively the reverse and forward amount of transmitted data occupying the link l during a time window ω. B (n1,n2) and B (n2,n1) are respectively the transmission data rate of each source node. ω is the time window during which the data traffic flow through the link l is captured. For the rest of our experiments, ω is set to 10 seconds in order to have enough trafic and to have situations of overloaded links.

We define also the Data Loss Ratio (DLR) of a link l which represents the amount of lost data among those transmitted during ω. This component provides information about the possible congestion or interference phenomenon that may affect the data packet delivery. The DLR of a link l between two nodes n 1 and n 2 is given by the following equation :

DLR l = T x (n1,n2) -Rx (n2,n1) T x (n1,n2) (2)
Where Rx (n2,n1) represents the amount of successfully received data by the node n 2 from the node n 1 .

Thus, the link quality of a link l is estimated by the Link Occupancy Metric (LOM) and is expressed as follows :

LOM l = αLOR l + (1 -α)DLR l (3)
The parameter α ∈ [0,1] and is used to delimit the metric so that the LOM value is still a ratio (∈ [0,1]). For the rest of our experiments, α is set to 0.5 in order to have a fair relation between the link load and the data loss ratio through that link. If α is set to 1, this means that we only consider the link load to assess the occupancy of that link and we neglect the data loss fact. If it is set to zero, our metric, then, will be typically the role of ETX metric.

Using this metric, only links with reduced occupancy are selected to form a route between a source node and a destination node so that routing decision is based on link's availability to support more traffic flows. Bottelneck or lossy links with high occupancy rates are supposed to be bad links. The occupancy level of a path is the sum of link occupancies of links forming the path.

As described, our metric, accounts for the bandwidth heterogeneity in the network and exploits this aspect towards a highthroughput routing. In addition, unlike ETX which is based on small probes to estimate the loss ratio, our metric estimation is more accurate since it is based on real data traffic and real transmission conditions.

B. Residual Link Capacity Based Routing Metric

The Link Occupancy Metric of all links is initiated to zero until having a traffic across the link. Then, during the first 10 seconds and until an update of link occupancy information, the route choice is randomly done and the protocol may consider a route with bad performances or bad link quality. Then, the routing metric should be better initialized to allow the routing protocol to a good start.

On the other hand, given two links with two different link occupancies, the route decision may be made and changed based on a minimal difference of 10 -6 which increases the frequency of route switching and makes the routing unstable. To illustrate this phenomenon, consider two links 1 and link 2 with data rates of, respectively, 300Mb/sec and 160 Mb/sec. Link 1 is already supporting a data traffic of 2Mbits. Having 2Mbits of additional data traffic to transmit, the routing protocol should select, between link 1 and link 2 , the best link to convey this traffic flow. Based on this scenario, the routing decision would be fluctuating so that it changes at every iteration.

To overcome these limitations, we propose a novel routing metric based on the residual link capacity. This proposal is motivated by the inability of the Link Occupancy Metric to measure accurately the capacity of a link to support a specific amount of data. Indeed, even if it accounts for the transmission rate heterogeneity, the link occupancy information is still expressed in terms of ratio and thus doesn't accurately reflect the real residual capacity in terms of bandwidth i.e. that such metric doesn't distinguish between two links having the same link occupancy but not the same bandwidth. Thus, a residual link capacity based metric may be more adaptive since it is relative to the amount of data to transmit, more accurate compared to a percentage based information and more efficient since it allows a more stable routing.

The Residual Link Capacity based metric (RLC) is given by the equation below:

RLC l = B l - T x l ω (4)
Where B l is the link bandwidth and Tx corresponds to the traffic occupying the link during the time window ω. Between two links, the routing protocol selects the link with the greater RLC. The route's RLC corresponds then to the minimum of RLCs of links composing the route.

RLC route = min(RLC l ) l∈route

(5)

Using this metric, each link is initialized to its bandwidth so that the routing protocol can choose from the start the route offering the greater bandwidth and thus supporting the greater traffic.

Since it is based on real exchange of data in the network, the RLC based metric gives a real estimation and thus allows a more efficient routing.

In order to evaluate the effectiveness of our metrics, this paper presents measurements taken from the BlueMeLab [5] testbed network described hereafter. We made some comparison with the hop-count metric as a simplistic routing metric and ETX as a link quality aware routing metric. To measure ETX, olsrd, instead of creating new probe messages, uses HELLO and TC messages of OLSR which are sent periodically each 2s and 5s respectively. This method aims to avoid extra overhead. All the performance evaluation in this paper are the result of measurements taken on the wireless testbed presented hereby.

C. Performance Evaluation

2) Experimental Results: this section presents experimental results that show that LOM and RLC often find higherthroughput paths than minimum hop-count and ETX. First series of experiments compared the throughput realised by hopcount, ETX and LOM metrics. We ommit the performances of RLC in the following figures because results are somehow the same of that of LOM. So, lines corresponding to RLC metric are ommited just for a better visibility. To carry out our performance tests, we first identified all possible routes in the network for each metric : Hop-count, ETX and LOM. We, then, compared the throughput of cumulative pair of nodes of paths found by OLSR using each metric between 42 total node pairs. The throughput is measured through TCP transmissions between each pair.

Results are plotted in Figure 2 and show that OLSR using LOM often finds faster routes than hop-count which doesn't account for any link quality and ETX which assumes all links run at one bit rate and doesn't account for the multi-rate aspect. In fact, in the right half region where throughputs are the highest, there is much more blue points showing highthroughput paths selected by LOM. The extreme right half corresponds to one hop routes where nodes can communicate directly. At these cases, the minimum hop-count metric finds the one-hop route as the best route, and there is no opportunity for ETX or LOM or RLC to perform better. The left half region, however, corresponds to routes with 2 hops or more. In this region, the sensitivity of LOM and RLC to differenciate high throughput paths allows them often to find better paths than hop-count and ETX.

Figure 3 shows the same data as Figure 3, but organized in a per-pair basis so that we can compare between the performances of ETX metric and Link Occupancy Metric for individual pairs. Each pair of nodes is represented by one point: the y value is the throughput obtained by OLSR using LOM, and the x value is the throughput obtained by OLSR using ETX. The line y=x corresponds to cases where ETX and LOM choose both the same path or paths with the same throughput. Points above the line y=x are pairs where LOM outperformed ETX. Results of Figure 3 show largely better performance of LOM compared to those of ETX. This is illustrated by the dense region above the line y=x where points with x near zero and y relatively higher. That region shows that routing based on LOM finds often paths with higher throughputs. In fact, with ETX metric which is loadinsensitive, links with good quality are always used to transmit data traffic even when they become overloaded or supporting many simultaneous data flows. With LOM, however, the routing decision is load-sensitive and can dynamically switch to links less occupied or offering a total unused bandwidth higher than the residual capacity of first chosen link. Hence, this metric allows a load-balancing routing so that all links in the network would be used fairly. In the rest of this section, we compared the performances of OLSR using ETX, OLSR using LOM and OLSR using RLC in terms of throughput, delay and packet loss. For that, we choose one representative pair of nodes to carry out our performance tests. Nodes are numbered as shown in Figure 1. This pair includes the node n 17 and the node n 16 which are distant enough to have different routes with different characteristics (distance between nodes, number of hops, link quality, etc.). In this series of experiments, we generate an UDP traffic from node n 17 to reach node n 16 while varying the transmission rate and we pick up the average throughput of 10 series of tests. Figure 4a plots the average throughput for each metric experienced by node n 17 when pinging node n 16 . For the three metrics, the throughput increases with transmission rate. For small amount of data, the three metrics are achieving the same throughput because they are using the same route. For greater data traffic, some links would be then more occupied and loaded compared to others. In that case, based on LOM and RLC, OLSR would change route and choose links with a better availability which explains the variations in the pattern of OLSR-LOM and OLSR-RLC.

Figure 4b shows the average packet loss of the same scenario described above. For light traffic, the pattern is approximately the same for the three metrics. By increasing the transmission rate, the packet loss also increases greatly. We note, however, for higher transmission rates, a slightly higher packet loss with ETX. Indeed, the more the link is overloaded by heavy traffic, the more is the risk of loss because of congestion or timeout in queues, particularly at bottelneck nodes such as node n 1 9 which is the most used with ETX. This phenomena is avoided with LOM since it is a load-sensitive metric and can dynamically adapt the routing decision based on the bandwidth availability of other links in the network. However, using Link Occupancy Metric, the increase of packet loss is considerably higher at important transmission rates and is represented by several pics which shows in general the route switch. Residual Link Capacity based routing is more regular because it reproduces physical conditions and Figure 4c shows the end-to-end delay to reach node n 16 from the node n 17 . For all metrics, as the transmission rate increases, the packet loss rate also increases over the time. Compared to OLSR-RLC, this increase is particularly important with Link Occupancy based routing as we note several pics especially for higher transmission rates (from 5Mb/sec). These delays are caused essentially by buffering and queuing delays at intermediate nodes. Since both metrics are loadsensitive, packets are crossing different paths when the traffic is getting higher. However, using Link Occupancy Metric, the routing decision can change frequently, as explained in section III-B, according to the availability of freer links. These "freer" links don't always offer more bandwidth to support large amount of data which causes congestion and huge buffering delays. Using Residual Link Capacity, the route decision changes only if there's links with larger residual bandwidth and then are more convenient to support larger data traffic which explains the regular increase of the delay pattern of that metric. This metric is improved to consider intraflow and interflow interferences. We describe here after the interference model adopted in this work and the bandwidth estimation of each link. Our new metric Residual Link Capacity Based Routing Metric with Interference Consideration (RLCIC) is designed based on this information.

IV. RESIDUAL LINK CAPACITY BASED ROUTING METRIC WITH INTERFERENCE CONSIDERATION

A. Preliminaries

In this section, we give an overview of the clique-based method for computing the available path bandwidth.

In wired networks, nodes are able to know the amount of available resources in the medium and how much bandwidth is being used. However, in wireless networks, where the medium is shared between multiple nodes, communication from one node may affect the bandwidth of neighboring nodes. Therefore, the bandwidth consumed by data flows and the available resources to a node are not local concepts, but related to the neighboring nodes in carrier-sensing range [START_REF] Hou | Hop-by-Hop Routing in Wireless Mesh Networks with Bandwidth Guarantees[END_REF]. Generally, we distinguish two types of interferences: intra-flow interferences and inter-flow interferences. Intraflow interference occurs when a data packet is being transmitted over multiple links along a path. In order to avoid conflict at the receiving node, some links may remain idle. Interflow interference occurs when different flows are being transmitted at the same time and then sharing the same available resource. In other words, the interflow interference affects the amount of residual channel resources on each link that will be allocated for a new flow [START_REF] Hou | Hop-by-Hop Routing in Wireless Mesh Networks with Bandwidth Guarantees[END_REF][10].

To model the interference relationship between links, one common method is the use of interference conflict graph (or conflict graph for short). This method is used in several existing works [START_REF] Salonidis | Identifying High Throughput Paths in 802.11 Mesh Networks: A Model-Based Approach[END_REF][9][11] [START_REF] Kodialam | Characterizing the Capacity Region in Multi-Radio Multi-Channel Wireless Mesh Networks[END_REF]. Given a wireless network, each link becomes a node in the conflict graph. If two links in the wireless network interfere with each other i.e. cannot be active simultaneously, we put an edge between the corresponding nodes in the conflict graph. The example depicted in figure 5 illustrates the interference modeling using conflict graph. The wireless network based on a six-link chain topology is given in Figure 5a and the corresponding conflict graph is given in Figure 5b. Assuming that all nodes have the same transmission or communication range R c and the same interference or sensing range R s as respresented, we conclude that link 1 and 2, for example, conflict with each other because node b cannot transmit and receive at the same time. Link 1 and 3 conflict also with each other because node cs transmission will introduce enough interference for the reception at node b.

An interference clique in the wireless network is a set of vertices that mutually conflict with each other. In the conflict graph, the corresponding nodes of these links form a complete subgraph.

A maximal interference clique is a complete subgraph that is not contained in any other complete subgraph. For example, {1, 2, 3} and {3, 4, 5} are maximal cliques while {1, 2} and The size of a maximal clique depends on how many links interfere with each other, which depends on the interference model adopted in the network.

Our work is based on the 802.11 MAC protocol where every reception of a data packet is acknowledged by an ACK packet. Therefore, for a packet transmission to be successful, both the sender and the receiver should not be interfered by other nodes. In other words, the transmissions on links (u, v) and (s, d) are successful at the same time if and only if both s and d are outside the interference ranges of u and v.

This model is referred as the bidirectional transmission model and the Transmitter-Receiver Conflict Avoidance (TRCA) interference model and is adopted by many existing works [START_REF] Chiu | Bandwidth Constrained Routing Problem in Wireless Ad Hoc Networks[END_REF]. Following [START_REF] Hou | Hop-by-Hop Routing in Wireless Mesh Networks with Bandwidth Guarantees[END_REF], we define the transmission range of a node to be hop, while the interference range to be r hops and to simplify our discussion, we set r = 2. We use the previous network to illustrate the TRCA interference model. The conflict graph in Figure 5b assumes r = 1 which is not the TRCA interference model we are using in this paper. Based on the network in Figure 5a, under TRCA model, when node a sends data to node b, node d is not allowed to transmit since it is in the interference range of b. This means that links 1 and 4 interfere with each other. Then, each maximal clique contains four consecutive links.

Relying on this clique-based formulation, we describe below the method to capture bandwidth sharing among links within the path. Given a wireless network, we denote {Q 1 ; ...; Q k } as the maximal interference clique set of the network, C q as the capacity of a clique q, B(l) as the total bandwidth of link l and B(p) as the estimation of the available bandwidth of path p. Then, considering a path p =< l 1 , l 2 , ..., l h >, the available bandwidth of the path p is estimated as follows [START_REF] Li | Minimizing End-to-End Delay: A Novel Routing Metric for Multi-Radio Wireless Mesh Networks[END_REF]:

B(p) = min q∈Qp C q ; C q = 1 l∈q ( 1 B(l) ) (6)
The rationale behind the formula is: transmissions on the links in a clique cannot be concurrent but occur in a serial manner. Thus, ( 1 B(l) ) represents the time it takes for 1 Mbit data to traverse all the links in the clique q. C q is thus the bandwidth available over the clique q. The available bandwidth of the path is the bandwidth of the bottleneck clique.

Proof. Consider two neighboring links i and j along a path. Links i and j have available bandwidth B i and B j , respectively. We denote the equivalent achievable bandwidth over links i and j by B(ij). Since the two links can not be active simultaneously, the time for L Mbits data to traverse the path formed by links i and j satisfies :

L B(ij) = L B i + L B j (7)
It follows : There are two maximal cliques on this path and they are {1, 2, 3} and {3, 4, 5}.

B(ij) = B i × B j B i + B j (
Based on the TRCA interference model, since all maximal cliques in the conflict graph are containing at least four interferring links, the formula for estimating the available bandwidth of a path p becomes as follows:

B(p) = min 1≤k≤(h-4) C k ; C k = 1 1 B(k) + 1 B(k+1) + 1 B(k+2) + 1 B(k+3) (9)
Where B(k) represents the available bandwidth of the link (l k , l k+1 ). For further details about this clique-based estimation, interested readers can refer to the following works [START_REF] Li | Minimizing End-to-End Delay: A Novel Routing Metric for Multi-Radio Wireless Mesh Networks[END_REF].

According to the example in Figure 5 and under TRCA interference model, the estimated path bandwidth of the path p =< a, b, c, d, e, f > is:

B(p) = min 1≤k≤2 C k ;
Where :

C 1 = 1 1 10 + 1 50 + 1 25 + 1 20 = 4.76M bps And C 2 = 1 1 50 + 1 25 + 1 20 + 1 5 = 3.22M bps
Then, B(p) = min{4.76, 3.22} = 3.22M bps. We can easily verify that this result can be also found when applying the clique based estimation and when supposing the interferene range is for 2 hops.

B. Metric Design

In this section, we introduce our novel metric based on residual link capacity and accounting for both intraflow and interflow interferences. The purpose of this metric is to measure accurately the residual capacity of each link when considering the possible conflict with eventually other transmissions occuring at the same time. The routing decision, then, will be based on links offering the greatest capacity, in other words, on widest paths. To avoid interflow interferences, we used the Residual Link Capacity (RLC) metric defined previously. This metric measures accurately the available bandwidth over a link since it captures the amount of data of all flows crossing the specified link. We apply, then, the clique based bandwidth estimation in order to consider possible intraflow interferences. To model the interferences in the network, we used the TRCA interference model described previously. This formulation garantees a global and unique view inside the network i.e. that every node in the network will be aware of the widest neighboring links able to support additional traffic.

Each node computes first the residual capacity of its links. Then, for each path from this node to a destination node, it computes the available bandwidth over this path using the clique based formula introduced previously.

Given a wireless network, we denote {Q 1 ; ...; Q k } as the maximal interference clique set of the network, C q as the capacity of a clique q, RLC l as the Residual Link Capacity of link l and AB(p) as the estimation of the available bandwidth of path p. For each link l, RLC l is estimated as follows:

RLC l = T B l - T x l ω (10)
Where, T B l corresponds to the total available bandwidth of link l and T x l corresponds to the amount of data occupying the link l during the time window ω.

Then, considering a path p =< l 1 , l 2 , ..., l h >, the available bandwidth of the path p is no longer the minimum of RLCs of links composing the path but it is estimated as follows [START_REF] Li | Minimizing End-to-End Delay: A Novel Routing Metric for Multi-Radio Wireless Mesh Networks[END_REF]:

AB(p) = min 1≤k≤h C k ; C k = 1 RLC k + 1 RLC k+1 + 1 RLC k+2 + 1 RLC k+3 (11)
Hence, each node knows the residual capacity of neighboring links and is able to measure the widest path to a destination node while considering all possible interfering transmissions.

V. CONCLUSION AND FUTURE WORK

We presented, in this paper, two novel link quality aware routing metrics. The first proposal is a load-sensitive and additive metric that aims to fairly distribute the traffic load between nodes in the network while taking into account their occupancy and availability.

The second metric is a concave metric based on residual link capacity estimation. We mean by a concave metric when the total cost of a path is the minimum of the costs of individual links along the path. It represents accurately how much of additional traffic can the link support. Both are based on real traffic estimation and are updated periodically using the control messages of OLSR.

This paper provides a measurement-based performance evaluation of the OLSR protocol using different metrics such as hop-count, ETX and the two proposed metrics LOM and RLC.

The first series of experiments show that LOM and RLC outperforms ETX since it reproduces better the real behavior of nodes when they are solicited by several data flows simultaneously. According to the results obtained, the Residual Link Capacity based routing decision is more accurate since it considers better the bandwidth heterogeneity between links. Results obtained are related to the considered topology, further study of other topologies is needed to validate this conclusion. Although, our results remain coherent with other works [2] [START_REF] Houaidia | Experimental Performance Analysis of Routing Metrics in Wireless Mesh Networks[END_REF].

On the other hand, we presented a novel metric based on residual link capacity estimation and considering both intraflow and interflow interferences. We first model the interferences in a network based on conflict graph and we deduced a clique based estimation of the path bandwidth. This metric is described formally by notions of graph theory.

We focus, in further work, in proposing a novel routing protocol supporting the RLCIC metric and able, with specific diffusion algorithm, to garantee a unique global vision of the network shared by all nodes in the network.

Future contributions will be validated by simulation, prototyping and then deployed on the real mesh network tetaneutral.net [15] in Toulouse, France which offers a more realistic environment, traffic and wireless contraints. It allows us also to check the scalability of our proposal when deployed in a large scale network.

1 )

 1 Configuration and Testbed Setup: we run experiments in an indoor testbed [5][6] formed by seven nodes: four shuttles, two personal computers and one nanostation router. Device configurations are presented in a previous work [6]. All nodes are 2x2 MIMO devices equipped with the ath9k driver [7] and are using OpenWRT [8] operating system. Our testbed called BlueMeLab [5] is deployed at the University Institute of Technology (IUT) Blagnac-Toulouse, France. The nodes are spread over two floors of the building. Rooms are separated by thick bricked walls.

Fig. 1 :

 1 Fig. 1: The Testbed Topology.

Fig. 2 :

 2 Fig. 2: Cumulative Pair Throughput.

Fig. 3 :

 3 Fig. 3: Per Pair Cumulative Throughput.

Fig. 4 :

 4 Fig. 4: Performance comparison between OLSR-ETX, OLSR-LOM and OLSR-RLC, (a) Throughput (b) Packet Loss Rate (c) End-to-End delay.

Fig. 5 :

 5 Fig. 5: Illustration for interference model. (a) The original graph, (b) The conflict graph.

  8) Let's illustrate the example in figure Figure 5a: Consider the path p =< a; b; c; d; e; f >. Let B(1), B(2), B(3), B(4) and B(5) of the network in Figure 5a be 10, 50, 25, 20 and 5 Mbps, respectively.