Full exploitation of the bandwidth resources of Wireless Networks is challenging because of the sharing of the radio medium among neighboring nodes. Practical algorithms and distributed schemes that tries to optimising the use of the network radio resources. In this technical report we present the proof that maximising the network capacity is is an APX Complete problem (not approximable within 1 (1 - 2^(-k)) - eps for eps > 0).
@cite_14: The expected transmission count (ETX) metric is a new route metric for finding high-throughput paths in multi-hop wireless networks. The ETX of a path is the expected total number of packet transmissions (including retransmissions) required to successfully deliver a packet along that path. For practical networks, paths with the minimum ETX have the highest throughput. The ETX metric incorporates the effects of link loss ratios, asymmetry in the loss ratios between the two directions of each link, and interference among the successive links of a path. Busy networks that use the ETX route metric will also maximize total network throughput. We describe the design and implementation of ETX as a metric for the DSDV and DSR routing protocols, as well as modifications to DSDV and DSR which make them work well with ETX. Measurements taken from a 29-node 802.11b test-bed show that using ETX improves performance significantly over the widely-used minimum hop-count metric. For long paths the throughput increase is often a factor of two or more, suggesting that ETX will become more useful as networks grow larger and paths become longer. We also present a simple model for predicting how packet delivery ratio varies with packet size, and detailed measurements which characterize the test-bed's distribution of link delivery ratios and route throughputs. (Copies available exclusively from MIT Libraries, Rm. 14-0551, Cambridge, MA 02139-4307. Ph. 617-253-5668; Fax 617-253-1690.)
@cite_4: In wireless mesh networks (WMNs) traffic is routed from mobile clients through a multihop wireless backbone to and from Internet gateways (IGWs). Because of their limited number, IGWs become the major traffic bottlenecks. The purpose of this work is to explore the benefits of introducing load-dependent routing metrics to increase WMN capacity and performance. We use weighted shortest path routing and introduce LAETT a weight metric that captures both traffic load and link quality. We compare the scheme to ETT and MIC, two load independent metrics, and show in simulation its benefits for various network and traffic configurations.
@cite_22: We address the problem of balancing the traffic load in multi-hop wireless networks. We consider a point-to-point communicating network with a uniform distribution of source-sink pairs. When routing along shortest paths, the nodes that are centrally located forward a disproportionate amount of traffic. This translates into increased congestion and energy consumption. However, the maximum load can be decreased if the packets follow curved paths. We show that the optimum such routing scheme can be expressed in terms of geometric optics and computed by linear programming. We then propose a practical solution, which we call Curveball Routing which achieves results not much worse than the optimum. We evaluate our solution at three levels of fidelity: a Java high-level simulator, the ns2 simulator, and the Intel Mirage Sensor Network Testbed. Simulation results using the high-level simulator show that our solution successfully avoids the crowded center of the network, and reduces the maximum load by up to 40 . At the same time, the increase of the expected path length is minimal, i.e., only 8 on average. Simulation results using the ns2 simulator show that our solution can increase throughput on moderately loaded networks by up to 15 , while testbed results show a reduction in peak energy usage by up to 25 . Our prototype suggests that our solution is easily deployable.
@cite_9: Wireless mesh networks are an alternative technology for last-mile broadband Internet access. In WMNs, similar to ad hoc networks, each user node operates not only as a host but also as a router; user packets are forwarded to and from an Internet-connected gateway in multihop fashion. The meshed topology provides good reliability, market coverage, and scalability, as well as low upfront investments. Despite the recent startup surge in WMNs, much research remains to be done before WMNs realize their full potential. This article tackles the problem of determining the exact capacity of a WMN. The key concept we introduce to enable this calculation is the bottleneck collision domain, defined as the geographical area of the network that bounds from above the amount of data that can be transmitted in the network. We show that for WMNs the throughput of each node decreases as O(1 n), where n is the total number of nodes in the network. In contrast with most existing work on ad hoc network capacity, we do not limit our study to the asymptotic case. In particular, for a given topology and the set of active nodes, we provide exact upper bounds on the throughput of any node. The calculation can be used to provision the network, to ensure quality of service and fairness. The theoretical results are validated by detailed simulations.
@cite_21: We show that link interferences in multihop wireless networks make the problem of selecting a path satisfying bandwidth requirements an NP-complete problem, even under simplified rules for bandwidth reservation. This is in sharp contrast to path selection in wireline networks where efficient polynomial algorithms exist. We also describe a distributed mechanism for the problem of slot allocation according to bandwidth reservation in a wireless slotted environment.
@cite_2: We propose three heuristics to compute QoS routes in a multihop wireless networks considering interferences constraints. It has been proved that reservation under such conditions is an NP-complete problem. Our heuristics are based on Dijkstra's shortest path algorithm in which we integrate the notion of bandwidth capacity in order to satisfy flows requirements.We show with several simulations that these heuristics not only allows computation of routes that save bandwidth of nodes with low capacity but also that network can handle more QoS-flows.
@cite_5: 
@cite_15: MIN PB is the class of minimization problems whose objective functions are bounded by a polynomial in the size of the input. We show that there exist several problems that are MIN PB-complete with respect to an approximation preserving reduction. These problems are very hard to approximate; in polynomial time they cannot be approximated within ne for some e > 0, where n is the size of the input, provided that P ≠ NP. In particular, the problem of finding the minimum independent dominating set in a graph, the problem of satisfying a 3-SAT formula setting the least number of variables to one, and the minimum bounded 0 - 1 programming problem are shown to be MIN PB-complete.We also present a new type of approximation preserving reduction that is designed for problems whose approximability is expressed as a function of some size parameter. Using this reduction we obtain good lower bounds on the approximability of the treated problems.
@cite_16: Due to the static nature of nodes, in mesh networks, a poor choice of paths may remain unchanged for a long time and create hot spots. Hence, it is very important to design path weight functions (also called routing metrics) to facilitate load-balanced routing in mesh networks. Such path weight functions (PWFs) must reflect the shared nature of wireless channels and support easy calculation of loop-free paths. In this abstract, we present our theoretical studies of the requirements on PWFs and design the first PWF, called Metric of Interference and Channel-switching (MIC), that satisfies these requirements. Our simulation results show that MIC's performance is substantially better than existing PWFs. (See our technical report [5] for more details.)
@cite_10: We present a new metric for routing in multi-radio, multi-hop wireless networks. We focus on wireless networks with stationary nodes, such as community wireless networks.The goal of the metric is to choose a high-throughput path between a source and a destination. Our metric assigns weights to individual links based on the Expected Transmission Time (ETT) of a packet over the link. The ETT is a function of the loss rate and the bandwidth of the link. The individual link weights are combined into a path metric called Weighted Cumulative ETT (WCETT) that explicitly accounts for the interference among links that use the same channel. The WCETT metric is incorporated into a routing protocol that we call Multi-Radio Link-Quality Source Routing.We studied the performance of our metric by implementing it in a wireless testbed consisting of 23 nodes, each equipped with two 802.11 wireless cards. We find that in a multi-radio environment, our metric significantly outperforms previously-proposed routing metrics by making judicious use of the second radio.
@cite_25: Abstract We show that for some positive constant c it is not feasible to approximate Independent Set (for graphs of n vertices) within a factor of n c , provided Maximum 2- Satisfiability does not have a randomized polynomial time approximation scheme. We also study reductions preserving the quality of approximations and exhibit complete problems.
@cite_17: We present a new routing metric for multi-rate multi-radio mesh networks, which takes into account both contention for the shared wireless channel and rate diversity in multi-radio multi-channel mesh networks. A key property of the proposed contention-aware transmission time (CATT) metric is that it is isotonic, hence can be applied to link-state routing protocols. We have implemented the CATT metric in the OLSR routing protocol, and evaluate it in a test-bed with mesh nodes each equipped with four radio interfaces. Our experiments show that the proposed routing metric significantly outperforms other metrics that have appeared in the literature, in a number of scenarios that correspond to different mesh network topologies.
In a wired network, finding an elementary path between two nodes minimizing over-loaded nodes can be solved by using the distributed and polynomial dijkstra algorithm @cite_5 . In a wireless network, this problem is the Remaining Capacity problem ( ) defined in @cite_21 . @cite_15 @cite_25 , authors show that finding the shortest path (repectively longest path) that avoid over-loaded nodes cannot be solved in a polynomial time. Centralized heuristics are proposed in @cite_4 . Moreover, experimental studies aim at increasing the capacity of the network @cite_9 (i.e. we call network capacity the cumulated data rate flows present in the network) by giving the best routing decisions (distributed routing protocols) that avoids using over-loaded nodes, see @cite_4 @cite_17 @cite_2 @cite_16 @cite_10 @cite_14 . @cite_22 , authors try to decreased the maximum load with curve routing. This routing needs the knowledge of the geographical localization of nodes.