Search

We present a distributed stable protocol for local broadcast in multi-hop wireless networks, where packets are injected to the nodes continuously, and each node needs to quickly disseminate the injected packets to all its neighbors within a given communication range $R$. We investigate the maximum packet injection rate and the minimum packet latency that can be achieved in a stable protocol. This paper assumes the signal-to-interference-plus-noise-ratio (SINR) interference model, which reflects more accurately the physical characteristics of the wireless interference, such as fading and signal accumulation, than conventional local interference models, e.g., graph-based models. More specifically, we present a stable protocol that can handle both stochastic and adversarial injection patterns. The protocol is asymptotically optimal in terms of both injection rate and packet latency. To the best of our knowledge, this paper is the first one studying the properties of stable protocols for the basic primitive of local broadcast in a multi-hop setting under SINR. Our proposed protocol utilizes a static local broadcast algorithm as a subroutine. This static algorithm is of independent interest, and it closes the $O(\log n)$ gap between the upper and lower bounds for static local broadcast. Simulation results indicate that our proposed algorithms can perform well in realistic environments. [ABSTRACT FROM AUTHOR]

This paper proposes a novel approach to assess the performance in terms of end-to-end throughput of an ad hoc multi-hop wireless network, where each link is affected by interference coming from other multi-hop paths nearby. The approach captures the mutual impact of each path on all others. It can be applied to both, contention-based and scheduled, medium access control (MAC) protocols. Sources have data to send to destination nodes through $n$ relays. Nodes are assumed to be uniformly and randomly distributed in the 2-D infinite plane. The model shows the impact on the end-to-end throughput of $n$ ; it also captures the influence of node density, traffic generated, number of retransmissions, and other MAC parameters. Finally, the model provides the throughput-delay tradeoff. Unlike most previous approaches, the mathematical tool proposed appears to be scalable, allowing easy extension to any number of hops. Comparison with simulation results is provided to prove that the impact of the approximations introduced in the analysis is almost negligible. [ABSTRACT FROM PUBLISHER]

There have been some rapid advances on the design of full duplex (FD) transceivers in recent years. Although the benefits of FD have been studied for single-hop wireless communications, its potential on throughput performance in a multi-hop wireless network remains unclear. As for multi-hop networks, a fundamental problem is to compute the achievable end-to-end throughput for one or multiple communication sessions. The goal of this paper is to offer some fundamental understanding on end-to-end throughput performance limits of FD in a multi-hop wireless network. We show that through a rigorous mathematical formulation, we can cast the multi-hop throughput performance problem into a formal optimization problem. Through numerical results, we show that in many cases, the end-to-end session throughput in a FD network can exceed $2 \times$ of that in a half duplex (HD) network. Our finding can be explained by the much larger design space for scheduling that is offered by removing HD constraints in throughput maximization problem. The results in this paper offer some new understandings on the potential benefits of FD for end-to-end session throughput in a multi-hop wireless network. [ABSTRACT FROM AUTHOR]

Recently, multiple concurrent transmission techniques have been proposed for smartly exploiting interference to improve network throughput. This paper considers zero-forcing (ZF) precoding that allows two interfering links to concurrently transmit under certain situations. This paper focuses on identifying appropriate schedule schemes that efficiently utilize the ZF precoding opportunities to improve network throughput. With this motivation, we define novel link models to formulate our concerned problem. We also develop a distributed scheduling algorithm by using belief propagation. Finally, we conduct extensive simulation experiments to evaluate the efficiency of ZF in improving network throughput in multihop wireless networks. Our simulations confirm that intelligently utilizing ZF in multihop networks is very effective in improving throughput. [ABSTRACT FROM PUBLISHER]

This paper presents an analytical study of the stable throughput for multiple broadcast sessions in a multi-hop wireless tandem network with random access. Intermediate nodes leverage on the broadcast nature of wireless medium access to perform inter-session network coding among different flows. This problem is challenging due to the interaction among nodes, and has been addressed so far only in the saturated mode where all nodes always have packet to send, which results in infinite packet delay. In this paper, we provide a novel model based on multi-class queueing networks to investigate the problem in unsaturated mode. We devise a theoretical framework for computing maximum stable throughput of network coding for a slotted ALOHA-based random access system. Using our formulation, we compare the performance of network coding and traditional routing. Our results show that network coding leads to high throughput gain over traditional routing. We also define a new metric, network unbalance ratio (NUR), that indicates the unbalance status of the utilization factors at different nodes. We show that although the throughput gain of the network coding compared to the traditional routing decreases when the number of nodes tends to infinity, NUR of the former outperforms the latter. We carry out simulations to confirm our theoretical analysis. [ABSTRACT FROM PUBLISHER]

In maritime wireless communications, unmanned surface vehicles (USVs) can improve coverage and transmission performance due to their agile maneuverability and flexible deployment. This paper considers a USV-enabled maritime wireless network, where a USV is employed to assist the communication between the terrestrial base station and ships. Considering the maritime environment characteristics and earth curvature, we establish the systematic USV kinetics and information transmission models. To guarantee fairness, we aim to maximize the minimum expected throughput overall ships by jointly optimizing the trajectory and communication resource allocation, subject to the constraints of the USV kinetics, safe sailing, breakpoint distances, line-of-sight links, resource allocation, and information-causality. Due to the complexity of the maritime two-ray signal propagation model, we propose a channel approximation method to find an upper bound of the throughput for the original problem. By the problem decomposition, two sub-problems are derived and solved iteratively using successive convex approximation and interior-point methods. Simulation results confirm the effectiveness of the proposed method and show that USV can significantly improve transmission performance in maritime wireless networks. [ABSTRACT FROM AUTHOR]

In this paper, we study the achievable throughput of batched temporal network coding in multi-hop erasure channels, where network coding is applied only within small coding blocks and each communication hop is modeled as a Gilbert–Elliott (GE) packet erasure channel. The GE channel is a 2-state Markov model that is commonly used for channels with memory. While channel memory does not affect the end-to-end capacity of multi-hop erasure channels, we show that it degrades the end-to-end throughput, when batched network coding with finite batch size is applied, due to the higher variance in erasures within one coding block. On the other hand, if the initial channel state information is available, the channel variance can be significantly reduced. We show that this fact can be utilized for improving the efficiency of the recoding operations at the intermediate nodes, and hence improve the end-to-end throughput of batched network coding schemes. Specifically, we propose adaptive recoding operations, where the network coded packets are adaptively generated based on the number of received packets and the initial channel state for each coding block. The simulation results show that the proposed adaptive recoding scheme significantly enhances the end-to-end throughput of batched network coding over multi-hop GE channels. [ABSTRACT FROM PUBLISHER]

Interference neutralization (IN) is regarded as a promising interference management techniques for multi-hop wireless networks. Yet most existing results of IN are limited to two-hop networks such as the relay-aided cellular network. Little progress has been made so far in the exploration of IN in generic multi-hop (more than two hops) networks. This paper aims to bridge this gap by developing an optimization framework for IN in a generic multi-hop network with the objective of maximizing the end-to-end throughput of multiple coexisting communication sessions. We first derive a mathematical model for IN in a special one-hop network to characterize the capability of IN, and then generalize this model to a multi-hop network. Based on the IN model, we develop a cross-layer optimization framework for a multi-hop network with the objective of fully translating the benefits of IN to the end-to-end throughput of the multi-hop sessions. To evaluate the performance of IN in multi-hop networks, we compare its performance against the case where IN is not employed. Simulation results show that the use of IN can significantly (more than 50%) increase the session throughput and, more notably, the throughput gain of IN increases with the node density and traffic intensity in the network. [ABSTRACT FROM PUBLISHER]

Efficient communication through a multi-hop network with packet loss requires random linear network coding schemes with low computation cost and high throughput. In this paper, we propose a low-density parity-check (LDPC)-based framework for constructing chunked code, a variation of random linear network code with low encoding/decoding computational cost and small coefficient vector overhead. Two classes of chunked codes with LDPC structures, named uniform LDPC-chunked codes and overlapped LDPC-chunked (OLC) codes, are studied under a general chunk transfer matrix model. ULC codes achieve rates close to the optimum and perform better than existing chunked codes that employ parity-check constraints. OLC codes are overlapped chunked codes, where it is not necessary to generate new packets for encoding, and demonstrate much higher rates in certain scenarios than the state-of-the-art designs of overlapped chunked codes. These results justifies the feasibility of this LDPC approach for communication through multi-hop networks with packet loss. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of link scheduling in multihop wireless networks under general interference constraints. Our goal is to design scheduling schemes that do not use per-flow or per-destination information, maintain a single data queue for each link, and exploit only local information, while guaranteeing throughput optimality. Although the celebrated back-pressure algorithm maximizes throughput, it requires per-flow or per-destination information. It is usually difficult to obtain and maintain this type of information, especially in large networks, where there are numerous flows. Also, the back-pressure algorithm maintains a complex data structure at each node, keeps exchanging queue-length information among neighboring nodes, and commonly results in poor delay performance. In this paper, we propose scheduling schemes that can circumvent these drawbacks and guarantee throughput optimality. These schemes use either the readily available hop-count information or only the local information for each link. We rigorously analyze the performance of the proposed schemes using fluid limit techniques via an inductive argument and show that they are throughput-optimal. We also conduct simulations to validate our theoretical results in various settings and show that the proposed schemes can substantially improve the delay performance in most scenarios. [ABSTRACT FROM PUBLISHER]

Multipath routing can offer various advantages for wireless multihop networks. Among those advantages, in this paper, we focus on an advantage of multipath routing for security using the notion of information-theoretic security. We formulate an optimization problem that maximizes the transmission rate from a source node to a destination node with information-theoretic security constraints to avoid eavesdropping that can be carried out at some nodes within a wireless multihop network. Binary erasure channel (BEC) modeling is employed to model wireless links that suffer from fading and interference. It is shown that the proposed throughput maximization problem is a linear optimization problem and the optimal rate allocation can be found by standard optimization techniques. We also study performance analysis including an asymptotic analysis to see whether or not multipath routing (with equal rate allocation) could be secure in terms of an information-theoretic security point of view. Through performance analysis, we can show that multipath routing can provide not only more secure routing against eavesdropping, but also a higher throughput as more multipaths are available. [ABSTRACT FROM PUBLISHER]

This paper investigates the speed limit of information propagation in large-scale multihop wireless networks, which provides fundamental understanding of the fastest information transportation and delivery that a wireless network is able to accommodate. We show that there exists a unified speed upper bound for broadcast and unicast communications in large-scale wireless networks. When network connectivity is considered, this speed bound is a function of node density. If the network noise is constant, the bound is a constant when node density exceeds a threshold; if the network noise is an increasing function of node density, the bound decreases to zero when node density approaches infinity. As achieving the speed bound places strict requirements on node locations, we also quantify the gap between the actual achieved speed and the desired bound in random networks in which the relay nodes are not located as desired. We find that the gap converges to zero exponentially as node density increases to infinity. [ABSTRACT FROM PUBLISHER]

This paper proposes a novel buffer-aided link selection scheme based on network coding in the multiple-hop relay network. The proposed scheme significantly increases transmission throughput by applying data buffers at the relays to decrease the outage probability and using network coding to increase the data rate. The closed-form expressions of both average throughput and packet delay are successfully derived. The proposed scheme not only has significantly higher throughput than both the traditional and existing buffer-aided max-link schemes but smaller average packet delay than the max-link scheme as well, making it an attractive scheme in practice. [ABSTRACT FROM PUBLISHER]

To improve the efficiency of wireless data communications, new physical-layer transmission methods based on known-interference cancelation (KIC) have been developed. These methods share the common idea that interference can be canceled when its content is known. Existing work on KIC mainly focuses on single-hop or two-hop networks, with physical-layer network coding and full-duplex communications as typical examples. This paper extends the idea of KIC to general multihop networks and proposes an end-to-end KIC (E2E-KIC) transmission method, together with its medium access control (MAC) design. With E2E-KIC, multiple nodes in a flow passing through a few nodes in an arbitrary topology can simultaneously transmit and receive on the same channel. We first present a theoretical analysis on the effectiveness of E2E-KIC in an idealized case. Then, to support E2E-KIC in multihop networks with an arbitrary topology, we propose an E2E-KIC-supported MAC protocol (E2E-KIC MAC), which is based on an extension of the Request-to-Send/Clear-to-Send mechanism in the IEEE 802.11 MAC. We also analytically analyze the performance of the proposed E2E-KIC MAC in the presence of hidden terminals. Simulation results illustrate that the proposed E2E-KIC MAC can improve network throughput and reduce end-to-end delay. [ABSTRACT FROM PUBLISHER]

Scheduling is a critical and challenging resource allocation mechanism for multihop wireless networks. It is well known that scheduling schemes that favor links with larger queue length can achieve high throughput performance. However, these queue-length-based schemes could potentially suffer from large (even infinite) packet delays due to the well-known last packet problem, whereby packets belonging to some flows may be excessively delayed due to lack of subsequent packet arrivals. Delay-based schemes have the potential to resolve this last packet problem by scheduling the link based on the delay the packet has encountered. However, characterizing throughput optimality of these delay-based schemes has largely been an open problem in multihop wireless networks (except in limited cases where the traffic is single-hop.) In this paper, we investigate delay-based scheduling schemes for multihop traffic scenarios with fixed routes. We develop a scheduling scheme based on a new delay metric and show that the proposed scheme achieves optimal throughput performance. Furthermore, we conduct simulations to support our analytical results and show that the delay-based scheduler successfully removes excessive packet delays, while it achieves the same throughput region as the queue-length-based scheme. [ABSTRACT FROM AUTHOR]

This paper establishes that random access scheduling schemes, and more specifically CSMA-CA, yield exceptionally good performance in the context of wireless multihop networks. While it is believed that CSMA-CA performs significantly worse than optimal, this belief is usually based on experiments that use rate allocation mechanisms that grossly underutilize the available capacity that random access provides. To establish our thesis, we first compare the achievable rate region of CSMA-CA and optimal in a number of carefully constructed multihop topologies and find that CSMA-CA is always within 48% of the optimal. Motivated by this result, we next characterize the worst-case performance of CSMA-CA in neighborhood topologies representing the congested regions of larger multihop topologies by deriving the neighborhood topology that yields the worst-case throughput ratio for CSMA-CA and find that in neighborhood topologies with less than 20 edges: 1) CSMA-CA is never worse than 16% of the optimal when ignoring physical-layer constraints; and 2) in any realistic topology with geometric constraints due to the physical layer, CSMA-CA is never worse than 30% of the optimal. Considering that maximal scheduling achieves much lower bounds than the above, and greedy maximal scheduling, which is one of the best known distributed approximation of an optimal scheduler, achieves similar worst-case bounds, CSMA-CA is surprisingly efficient. [ABSTRACT FROM AUTHOR]

This paper introduces models and a system for designing 802.11 wireless LANs (WLANs) using flexible channelization— the choice of an appropriate channel width and center frequency for each transmission. In contrast to current 802.11 systems that use fixed width channels, the proposed system, FLUID, configures all access points and their clients using flexible channels. We show that a key challenge in designing such a system stems from managing the effects of interference due to multiple transmitters employing variable channel widths, in a network-wide setting. We implemented FLUID in an enterprise-like setup using a 50 node testbed (with off-the shelf wireless cards) and we show that FLUID improves the average throughput by 59 percent across all PHY rates, compared to existing fixed-width approaches. [ABSTRACT FROM PUBLISHER]

In multihop ad hoc networks over 802.11, the real bandwidth-delay product (BDP) cannot reach a value as large as in wired networks due to contention through wireless shared channels. As a result, conventional congestion-control algorithms cause an overshooting window problem and result in poor throughput in ad hoc networks. In this paper, we split the real round-trip time (RTT) into two parts: 1) congestion RTT and 2) contention RTT. We reveal that the contention RTT has nothing to do with the BDP and that the BDP is determined by only the congestion RTT if a link with the worst contention status does not lead to link breakage. An inadequate use of contention RTT causes a Transmission Control Protocol (TCP) congestion window overshooting problem. We propose a novel mechanism called congestion window adaptation through contention detection, which provides a more accurate method of estimating the contention status. Based on this mechanism, we present a congestion window adaptation method to limit the window size from overshooting. Simulation results show that our proposed mechanism outperforms the conventional TCP and the enhanced mechanisms called TCP with contention control and TCP with a maximum window. [ABSTRACT FROM PUBLISHER]

Although the system throughput of a wireless communication system considering multiple users' geographical distribution on a 2-D plane and various traffic characteristics is an important performance metric, its mathematical analysis is very difficult due to the nonindependent identically distributed distribution of the received signal-to-noise ratio (SNR) of each mobile terminal and the complex dynamics of the traffic patterns. Therefore, complicated system-level simulations have been the only approach to evaluate the system throughput of downlink packet-access systems. In this paper, we propose an efficient analytical approach to estimate the system throughput of downlink packet-access systems by using point mass approximation, which is widely used in physics and mechanics. The proposed analysis framework enables the mathematical analysis of the system throughput performance by considering various positions of mobile terminals and traffic patterns without the complicated and heavy system-level simulations. Although the proposed approach has a tradeoff relation between computation complexity and accuracy, we show that it is possible to obtain an effective accuracy with moderate complexity using the proposed analytical approach. [ABSTRACT FROM PUBLISHER]

There has been an increasing interest in deploying wireless mesh networks (WMNs) for communication and video surveillance purposes thanks to its low cost and ease of deployment. It is well known that a major drawback of WMN is multihop bandwidth degradation, which is primarily caused by contention and radio interference. The use of mesh nodes with multiple radios and channels has been regarded as a straightforward solution to the problem in the research community. However, we demonstrate in this paper through real-world experiments that such an approach cannot resolve the multihop TCP throughput degradation problem in IEEE 802.11n mesh networks. With extensive experimentation, we verify that the degradation is principally caused by the increase in TCP Round-Trip Time (RTT) when the number of hops increases. TCP throughput is fundamentally limited inversely by the RTT. We find that the multihop TCP throughput (up to five hops) when using 802.11n is no better than when using 802.11a, despite the much higher data rate 802.11n. We attempt to use multiple parallel TCP connections as a remedy to the problem, and it turns out that the wireless bandwidth can be fully utilized with a sufficient number of parallel streams. In general, our results give a key message that TCP tuning (e.g., setting the correct TCP buffers and use of parallel streams) is of paramount importance in high-bandwidth multihop wireless mesh networks that employ the latest wireless standards. These tuning techniques have to be implemented into commercial products to fully leverage the ever advancing wireless technologies to support the growing demand of multihop communications in wireless mesh networks. [ABSTRACT FROM PUBLISHER]

A class of carrier sense multiple access (CSMA) protocols used in a broad range of wireless applications uses synchronized contention where nodes periodically contend at intervals of fixed duration. While several models exist for asynchronous CSMA contention used in protocols like IEEE 802.11 MAC, no model exists for synchronized CSMA contention that also incorporates realistic factors like clock drifts. In this paper, we introduce a model that quantifies the interplay of clock drifts with contention window size, control packet size, and carrier sense regulated by usage of guard time. Using a field programmable gate array (FPGA)-based MAC protocol implementation and controlled experiments on a wireless testbed, we evaluate the model predictions on the isolated and combined impact of these key performance factors to per-flow throughput and fairness properties in both single-hop and multihop networks. Our model and experimental evaluation reveal conditions on protocol parameters under which the throughput of certain flows can exponentially decrease; while at the same time, it enables solutions that can offset such problems in a predictable manner. [ABSTRACT FROM AUTHOR]

In this paper, we propose two cross-layer algorithms, namely, the Power-optimal Scheduling Algorithm (PSA) and the Throughput-optimal Scheduling Algorithm (TSA), to minimize energy consumption and to maximize throughput, respectively, in multihop wireless networks. Our algorithms guarantee a flow-based minimum data rate and jointly integrate congestion control, power allocation, routing, and link rate scheduling. Different from traditional algorithms that assume infinite buffers, the proposed algorithms deterministically upper bound the flow-based packet queue length and thus can be employed in multihop networks with finite buffers. In addition, the algorithms achieve a power expenditure/throughput “\epsilon-close” to the optimal value, with a tradeoff of order O(\1/\epsilon) in buffer size. The average end-to-end delay upper bound can also be derived from the finite buffer property. Finally, numerical results are presented to show the performance of the two algorithms with different system parameters. [ABSTRACT FROM PUBLISHER]

In this paper, a comprehensive survey is given on several major systematic approaches in dealing with delay-aware control problems, namely the equivalentrate constraint approach, the Lyapunov stability drift approach, and the approximate Markov decision process approach using stochastic learning. These approaches essentially embrace most of the existing literature regarding delay-aware resource control in wireless systems. They have their relative pros and cons in terms of performance, complexity, and implementation issues. For each of the approaches, the problem setup, the general solution, and the design methodology are discussed. Applications of these approaches to delay-aware resource allocation are illustrated with examples in single-hop wireless networks. Furthermore, recent results regarding delay-aware multihop routing designs in general multihop networks are elaborated. Finally, the delay performances of various approaches are compared through simulations using an example of the uplink OFDMA systems. [ABSTRACT FROM AUTHOR]

Interference alignment (IA) is widely regarded as a promising interference management technique for wireless networks and its potential is most profound in interference-intensive environments. This motivates us to study IA for multicast communications in multihop MIMO networks, which are rich in interference by nature. We develop a set of linear constraints that can characterize a feasible design space of IA for multicast communications. The set of linear constraints constitutes a simple mathematical model of IA that allows us to conduct cross-layer multicast throughput optimization in multihop MIMO networks, but without getting involved into the onerous signal design at the physical layer. Based on the mathematical model of IA, we formulate a multicast throughput maximization problem and develop an approximation solution that can achieve $(1-\varepsilon)$ -optimality. Simulation results show that the use of IA can significantly increase the multicast throughput in multihop MIMO networks and the throughput gain increases with the volume of multicast traffic and the number of antennas. [ABSTRACT FROM AUTHOR]

The introduction of relay station (RS) nodes is a key feature in next generation wireless networks such as 3GPP's long term evolution advanced (LTE-Advanced), or the forthcoming IEEE 802.16j WiMAX standard. This paper presents, using game theory, a novel approach for the formation of the tree architecture that connects the RSs and their serving base station in the uplink of the next generation wireless multi-hop systems. Unlike existing literature which mainly focused on performance analysis, we propose a distributed algorithm for studying the structure and dynamics of the network. We formulate a network formation game among the RSs whereby each RS aims to maximize a cross-layer utility function that takes into account the benefit from cooperative transmission, in terms of reduced bit error rate, and the costs in terms of the delay due to multi-hop transmission. For forming the tree structure, a distributed myopic algorithm is devised. Using the proposed algorithm, each RS can individually select the path that connects it to the BS through other RSs while optimizing its utility. We show the convergence of the algorithm into a Nash tree network, and we study how the RSs can adapt the network's topology to environmental changes such as mobility or the deployment of new mobile stations. Simulation results show that the proposed algorithm presents significant gains in terms of average utility per mobile station which is at least 17.1% better relatively to the case with no RSs and reaches up to 40.3% improvement compared to a nearest neighbor algorithm (for a network with 10 RSs). The results also show that the average number of hops does not exceed 3 even for a network with up to 25 RSs. [ABSTRACT FROM AUTHOR]

To facilitate a viable evolution of cellular networks toward extensive packet data traffic, the High Speed Downlink Packet Access (HSDPA) technology is introduced. The various link adaptation techniques employed by HSDPA augment the bandwidth variation, which is identified as one of the most important factors resulting in the deterioration of TCP performance. In this paper, we firstly build an analytical model of TCP throughput to explain why the bandwidth variation degrades the TCP performance. Subsequently, a split-connection Window Adaptation TCP Proxy is proposed to improve the TCP throughput in HSDPA networks. To use the precious cellular link resources sufficiently, the length of the queue in Node-B is intentionally kept around the reference value through adaptively adjusting the sending window size of TCP proxy based on the dynamic values of varying bandwidth. Since both the disturbance caused by bandwidth variation and the feedback delay are prone to lead an unstable queue system, the robust sliding mode variable structure control theory is employed to design the proper control law to weaken the impact of noise and delay on the stability of the queue system in Node-B. The theoretical analysis and the enhanced scheme are verified through simulation experiments. The simulation results show that our TCP proxy is able to resist against bandwidth oscillation and improve the cellular link utilization. [ABSTRACT FROM AUTHOR]

Network coding aware routing (NCAR) has been emerging as an effective approach to create coding opportunities actively in multihop networks. To the best of our knowledge, most of the existing methods focus on a “static” design that considers coding opportunities based on fixed routes and invariable packet flows. This “static” way results in the optimality of routes suffering from a high sensitive behavior on both network topology and flow dynamic and, hence, reduces the throughput of routes in time-varying networks. To solve this problem, we propose a high-throughput NCAR scheme that supports dynamic multihop network connectivity and achieves throughput optimization, even with multiple variable flows. In the proposed scheme, a back-pressure-based NCAR algorithm is designed to push the flows dynamically into the nodes that have better network coding opportunities with no knowledge of network topology and flow dynamic. As a byproduct, the proposed method also exhibits a significantly improved delay performance relative to the traditional back-pressure algorithm. Simulation results reveal that the proposed scheme improves network capacity and alleviates end-to-end delay in heavy load networks. [ABSTRACT FROM PUBLISHER]

We investigate, both theoretically and experimentally, the stability of CSMA-based wireless mesh networks, where a network is said to be stable if and only if the queue of each relay node remains (almost surely) finite. We identify two key factors that impact stability: the network size and the so-called “stealing effect,” a consequence of the hidden-node problem and nonzero transmission delays. We consider the case of a greedy source and prove, by using Foster's theorem, that three-hop networks are stable, but only if the stealing effect is accounted for. We also prove that four-hop networks are, on the contrary, always unstable (even with the stealing effect) and show by simulations that instability extends to more complex linear and nonlinear topologies. To tackle this instability problem, we propose and evaluate a novel, distributed flow-control mechanism called EZ-flow. EZ-flow is fully compatible with the IEEE 802.11 standard (i.e., it does not modify headers in packets), can be implemented using off-the-shelf hardware, and does not entail any communication overhead. EZ-flow operates by adapting the minimum congestion window parameter at each relay node, based on an estimation of the buffer occupancy at its successor node in the mesh. We show how such an estimation can be conducted passively by taking advantage of the broadcast nature of the wireless channel. Real experiments, run on a nine-node test-bed deployed over four different buildings, show that EZ-flow effectively smooths traffic and improves delay, throughput, and fairness performance. [ABSTRACT FROM PUBLISHER]