Search

The end-to-end throughput of multi-hop communication in wireless ad hoc networks is affected by the conflict between forwarding nodes. It has been shown that sending more packets than maximum achievable end-to-end throughput not only fails to increase throughput but also decreases throughput owing to high contention and collision. Accordingly, it is of crucial importance for a source node to know the maximum end-to-end throughput. The end-to-end throughput depends on multiple factors, such as physical layer limitations, medium access control (MAC) protocol properties, routing policy, and nodes’ distribution. There have been many studies on analytical modeling of end-to-end throughput but none of them has taken routing policy and nodes’ distribution as well as MAC layer altogether into account. In this paper, the end-to-end throughput with perfect MAC layer is obtained based on routing policy and nodes’ distribution in 1-D and 2-D networks. Then, imperfections of IEEE 802.11 protocol are added to the model to obtain precise value. An exhaustive simulation is also made to validate the proposed models using ns-2 simulator. Results show that if the distribution to the next hop for a particular routing policy is known, our methodology can obtain the maximum end-to-end throughput precisely. [ABSTRACT FROM AUTHOR]

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]

There are two fundamentally different fronthaul techniques in the downlink communication of cloud radio access network (C-RAN): the data-sharing strategy and the compression-based strategy. Under the former strategy, each user's message is multicast from the central processor (CP) to all the serving remote radio heads (RRHs) over the fronthaul network, which then cooperatively serve the users through joint beamforming; while under the latter strategy, the user messages are first beamformed then quantized at the CP, and the compressed signal is unicast to the corresponding RRH, which then decompresses its received signal for wireless transmission. Previous works show that in general the compression-based strategy outperforms the data-sharing strategy. This paper, on the other hand, points out that in a C-RAN model where the RRHs are connected to the CP via multihop routers, data-sharing can be superior to compression if the network coding technique is adopted for multicasting user messages to the cooperating RRHs, and the RRH's beamforming vectors, the user-RRH association, and the network coding design over the fronthaul network are jointly optimized based on the techniques of sparse optimization and successive convex approximation. This is in comparison to the compression-based strategy, where information is unicast over the fronthaul network by simple routing, and the RRH's compression noise covariance and beamforming vectors, as well as the routing strategy over the fronthaul network are jointly optimized based on the successive convex approximation technique. The observed gain in overall network throughput is due to that information multicast is more efficient than information unicast over the multihop fronthaul of a C-RAN. [ABSTRACT FROM PUBLISHER]

In this paper, we consider random-access wireless multihop networks, with multipacket reception capabilities, where multiple flows are forwarded to the gateways through node disjoint paths. We explore the issue of allocating flow on multiple paths, exhibiting both intra- and interpath interference, in order to maximize average aggregate flow throughput (AAT) and provide bounded packet delay. A distributed flow allocation scheme is proposed where allocation of flow on paths is formulated as an optimization problem. Through an illustrative topology, it is shown that the corresponding problem is nonconvex. Furthermore, a simple but accurate model is employed for the AAT achieved by all flows, which captures both intra- and interpath interference through the signal-to-interference-plus-noise ratio (SINR) model. The proposed scheme is evaluated through Ns2 simulations of several random wireless scenarios. Simulation results reveal that the model employed accurately captures the AAT observed in the simulated scenarios, even when the assumption of saturated queues is removed. Simulation results also show that the proposed scheme achieves significantly higher AAT for the vast majority of the wireless scenarios explored than for the following flow allocation schemes: one that assigns flows on paths on a round-robin fashion, one that optimally utilizes the best path (BP) only, and another one that assigns the maximum possible flow on each path. Finally, a variant of the proposed scheme is explored, where interference for each link is approximated by considering its dominant interfering nodes only. [ABSTRACT FROM PUBLISHER]

While multi-hop multi-frequency mesh has been extensively studied in the past decades, only several deployable and relatively bulky systems have been developed to support small numbers of hops under stationary settings. This paper presents a new Software-Defined Networking (SDN)-based design of multi-hop multi-frequency mesh. A new lightweight hardware platform is developed to support adaptive routing and frequency selection, by modifying and integrating commercial-off-the-shelf WiFi modules. We also extend the celebrated Dijkstra's algorithm in support of the new multi-hop multi-frequency platform, where non-overlapping frequency bands are selected together with the routing paths by maintaining $N^2$ Dijkstra processes for $N$ frequency bands. These processes interact to recursively select the optimal upstream node and frequency for each downstream frequency of a node. Mininet-WiFi is used to evaluate the routing of the new system under dense network settings. The results indicate that our system improves the end-to-end throughput by taking background WiFi traffic into account and adaptively selecting the routes and frequencies, as compared to the shortest-path-based routing strategy. [ABSTRACT FROM AUTHOR]

While considerable work has addressed the optimal AoI under different circumstances in single-hop networks, the exploration of AoI in multi-hop wireless networks is rarely attempted. More importantly, the inherent relationships between AoI and throughput are yet to be explored, especially in multi-hop networks. This paper studies AoI in multi-hop wireless networks and explores its potential relationships with throughput for the very first time, particularly focusing on the impacts of flexible routes on the two metrics, i.e., AoI and throughput. By developing a rigorous mathematical model with interference, channel allocation, link scheduling, and routing path selection taken into consideration, we build the interrelation between AoI and throughput in multi-hop networks. A multi-criteria optimization problem is formulated with the goal of simultaneously minimizing AoI and maximizing network throughput. By qualitatively analyzing their relationships, we exhibit that the two metrics may conflict with each other, implying the optimal solutions for the multi-criteria problem will include a set of Pareto-optimal points rather than a single point existing in the traditional optimization problem. We resort to a novel approach by transforming the multi-criteria problem into a single objective one so as to find the weakly Pareto-optimal points iteratively, thereby allowing us to screen all Pareto-optimal points for the solution. Through formal proof, our solution is demonstrated to be able to identify all Pareto-optimal points and terminate in a finite number of iterations. We conduct the simulation evaluation to identify the optimal tradeoff points of AoI and throughput, demonstrating that one performance metric may improve at the expense of degrading the other, with the routing path found as one of the key factors in determining such a tradeoff. [ABSTRACT FROM AUTHOR]

In covert communication, Alice tries to communicate with Bob without being detected by a warden Willie. When the distance between Alice and Bob becomes large compared with the distance between Alice and Willie(s), the performance of covert communication will be degraded. In this case, multi-hop message transmission via intermediate relays can help to improve the performance. Hence, in this paper, multi-hop covert communication over a moderate size network and in the presence of multiple collaborating Willies is considered. The relays can transmit covertly using either a single key for all relays or different independent keys at the relays. For each case, we develop efficient algorithms to find optimal paths with maximum throughput and minimum end-to-end delay between Alice and Bob. As expected, employing multiple hops significantly improves the ability to communicate covertly versus the case of a single-hop transmission. Furthermore, at the expense of more shared key bits, analytical results and numerical simulations demonstrate that the multi-hop covert communication with different independent keys at the relays has better performance than the multi-hop covert communication with a single key. [ABSTRACT FROM AUTHOR]

Being readily available in most of 802.11 radios, multirate capability appears to be useful as WiFi networks are getting more prevalent and crowded. More specifically, it would be helpful in high-density scenarios because internode distance is short enough to employ high data rates. However, communication at high data rates mandates a large number of hops for a given node pair in a multihop network and thus, can easily be depreciated as per-hop overhead at several layers of network protocol is aggregated over the increased number of hops. This paper presents a novel multihop, multirate adaptation mechanism, called multihop transmission opportunity (MTOP), that allows a frame to be forwarded a number of hops consecutively to minimize the MAC-layer overhead between hops. This seemingly collision-prone nonstop forwarding is proved to be safe via analysis and USRP/GNU Radio-based experiment in this paper. The idea of MTOP is in clear contrast to the conventional opportunistic transmission mechanism, known as TXOP, where a node transmits multiple frames back-to-back when it gets an opportunity in a single-hop WLAN. We conducted an extensive simulation study via OPNET, demonstrating the performance advantage of MTOP under a wide range of network scenarios. [ABSTRACT FROM PUBLISHER]

Hybrid wireless network is composed of both ad hoc transmissions and cellular transmissions. Under the $L$ -maximum-hop routing policy, flow is transmitted in the ad hoc mode if its source and destination are within $L$ hops away; otherwise, it is transmitted in the cellular mode. Existing works study the hybrid wireless network capacity as a function of $L$ so as to find the optimal $L$ to maximize the network capacity. In this paper, we consider two more factors: traffic model and base station access mode. Different from existing works, which only consider the uniform traffic model, we consider a traffic model with social behavior. We study the impact of traffic model on the optimal routing policy. Moreover, we consider two different access modes: one-hop access (each node directly communicates with base station) and multi-hop access (node may access base station through multiple hops due to power constraint). We study the impact of access mode on the optimal routing policy. Our results show that: 1) the optimal $L$ does not only depend on traffic pattern, but also the access mode; 2) one-hop access provides higher network capacity than multi-hop access at the cost of increasing transmitting power; and 3) under the one-hop access mode, network capacity grows linearly with the number of base stations; however, it does not hold with the multi-hop access mode, and the number of base stations has different effects on network capacity for different traffic models. [ABSTRACT FROM AUTHOR]

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 considers the problem of throughput optimal routing/scheduling in a multi-hop constrained queueing network with random connectivity whose special cases include opportunistic multi-hop wireless networks and input-queued switch fabrics. The main challenge in the design of throughput optimal routing policies is closely related to identifying appropriate and universal Lyapunov functions with negative expected drift. The few well-known throughput optimal policies in the literature are constructed using simple quadratic or exponential Lyapunov functions of the queue backlogs and as such they seek to balance the queue backlogs across network independent of the topology. By considering a class of continuous, differentiable, and piece-wise quadratic Lyapunov functions, this paper provides a large class of throughput optimal routing policies. The proposed class of Lyapunov functions allow for the routing policy to control the traffic along short paths for a large portion of state-space while ensuring a negative expected drift. This structure enables the design of a large class of routing policies. In particular, and in addition to recovering the throughput optimality of the well-known backpressure routing policy, an opportunistic routing policy with congestion diversity is proved to be throughput optimal. [ABSTRACT FROM AUTHOR]

Previous works on multicast capacity mainly focus on deriving asymptotic order results in large-scale wireless networks. While they can explore the general scaling laws of throughput capacity, it is also of great interest for practical concern to predict the exact achievable throughput in networks with an arbitrary finite number of nodes. In this paper, we investigate the nonasymptotic throughput and delay of multihop wireless networks for multicast applications wherein for each source node, $k$ nodes are randomly selected as receivers. It is challenging for the exact performance analysis since multicast transmission has a dynamic nature due to the following factors: 1) random distribution of nodes; 2) bursty traffic arrivals; and 3) different timescales for transient analysis. To tackle the problem, we propose an explicit analytical model and develop a multicast routing scheme, which accounts for these aspects. With our proposed model, we derive lower bound (LB) and upper bound (UB) on nonasymptotic multicast throughput and delay using stochastic network calculus. We show that the performance results hold for all timescales and network sizes and are strongly correlated to data burstiness and the number of receivers. While we investigate from a nonasymptotic point of view, our results can also cover the asymptotic scaling laws. Simulations are conducted to further verify the accuracy of the analytical bounds. [ABSTRACT FROM AUTHOR]

We consider a single-unicast networking scenario where a sender periodically sends a batch of data to a receiver over a multi-hop network, possibly using multiple paths. We study problems of minimizing peak/average Age-of-Information (AoI) subject to throughput requirements based on a stylized deterministic model in this scenario. The consideration of batch generation and multi-path communication differentiates our AoI study from existing ones. We first show that our AoI minimization problems are NP-hard, but only in the weak sense, as we develop an optimal algorithm with a pseudo-polynomial time complexity. We then prove that minimizing AoI and minimizing maximum delay are “roughly” equivalent, in the sense that any optimal solution of the latter is an approximate solution of the former with bounded optimality loss. We leverage this understanding to design a general approximation framework for our problems. It can build upon any $\alpha $ -approximation algorithm of the maximum delay minimization problem to construct an $(\alpha +\mathsf {c})$ -approximate solution for minimizing AoI. Here $\mathsf {c}$ is a constant depending on the throughput requirements. Furthermore, we show that our results can be extended to the multiple-unicast setting. Simulations over various network topologies validate the effectiveness of our approach. Our results make a major advance to optimizing AoI in multi-path communication, and hence can be of broad interest to the networking research community. [ABSTRACT FROM AUTHOR]

We consider the problem of throughput-optimal packet dissemination, in the presence of an arbitrary mix of unicast, broadcast, multicast, and anycast traffic, in an arbitrary wireless network. We propose an online dynamic policy, called Universal Max-Weight (UMW), which solves the problem efficiently. To the best of our knowledge, UMW is the first known throughput-optimal policy of such versatility in the context of generalized network flow problems. Conceptually, the UMW policy is derived by relaxing the precedence constraints associated with multi-hop routing and then solving a min-cost routing and max-weight scheduling problem on a virtual network of queues. When specialized to the unicast setting, the UMW policy yields a throughput-optimal cycle-free routing and link scheduling policy. This is in contrast with the well-known throughput-optimal back-pressure (BP) policy which allows for packet cycling, resulting in excessive latency. Extensive simulation results show that the proposed UMW policy incurs a substantially smaller delay as compared with the BP policy. The proof of throughput-optimality of the UMW policy combines ideas from the stochastic Lyapunov theory with a sample path argument from adversarial queueing theory and may be of independent theoretical interest. [ABSTRACT FROM AUTHOR]

This paper develops upper bounds on the end-to-end transmission capacity of multihop wireless networks. Potential source–destination paths are dynamically selected from a pool of randomly located relays, from which a closed-form lower bound on the outage probability is derived in terms of the expected number of potential paths. This is in turn used to provide an upper bound on the number of successful transmissions that can occur per unit area, which is known as the transmission capacity. The upper bound results from assuming independence among the potential paths, and can be viewed as the maximum diversity case. A useful aspect of the upper bound is its simple form for an arbitrary-sized network, which allows insights into how the number of hops and other network parameters affect spatial throughput in the nonasymptotic regime. The outage probability analysis is then extended to account for retransmissions with a maximum number of allowed attempts. In contrast to prevailing wisdom, we show that predetermined routing (such as nearest neighbor) is suboptimal, since more hops are not useful once the network is interference-limited. Our results also make clear that randomness in the location of relay sets and dynamically varying channel states is helpful in obtaining higher aggregate throughput, and that dynamic route selection should be used to exploit path diversity. [ABSTRACT FROM PUBLISHER]

Back-pressure-type algorithms based on the algorithm by Tassiulas and Ephremides have recently received much attention for jointly routing and scheduling over multihop wireless networks. However, this approach has a significant weakness in routing because the traditional back-pressure algorithm explores and exploits all feasible paths between each source and destination. While this extensive exploration is essential in order to maintain stability when the network is heavily loaded, under light or moderate loads, packets may be sent over unnecessarily long routes, and the algorithm could be very inefficient in terms of end-to-end delay and routing convergence times. This paper proposes a new routing/scheduling back-pressure algorithm that not only guarantees network stability (throughput optimality), but also adaptively selects a set of optimal routes based on shortest-path information in order to minimize average path lengths between each source and destination pair. Our results indicate that under the traditional back-pressure algorithm, the end-to-end packet delay first decreases and then increases as a function of the network load (arrival rate). This surprising low-load behavior is explained due to the fact that the traditional back-pressure algorithm exploits all paths (including very long ones) even when the traffic load is light. On the other-hand, the proposed algorithm adaptively selects a set of routes according to the traffic load so that long paths are used only when necessary, thus resulting in much smaller end-to-end packet delays as compared to the traditional back-pressure algorithm . [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]

The increasing demand for wireless services has led to a severe energy consumption problem with the rising of greenhouse gas emission. While the renewable energy can somehow alleviate this problem, the routing, flow rate, and power still have to be well investigated with the objective of minimizing energy consumption in multi-hop energy renewable wireless mesh networks (ER-WMNs). This paper formulates the problem of network-wide energy consumption minimization under the network throughput constraint as a mixed-integer nonlinear programming problem by jointly optimizing routing, rate control, and power allocation. Moreover, the min-max fairness model is applied to address the fairness issue because the uneven routing problem may incur the sharp reduction of network performance in multi-hop ER-WMNs. Due to the high computational complexity of the formulated mathematical programming problem, an energy-aware multi-path routing algorithm (EARA) is also proposed to deal with the joint control of routing, flow rate, and power allocation in practical multi-hop WMNs. To search the optimal routing, it applies a weighted Dijkstra’s shortest path algorithm, where the weight is defined as a function of the power consumption and residual energy of a node. Extensive simulation results are presented to show the performance of the proposed schemes and the effects of energy replenishment rate and network throughput on the network lifetime. [ABSTRACT FROM AUTHOR]

Cognitive radio (CR) technology opens the licensed spectrum bands for opportunistic usage and initiates spectrum trading to improve the spectrum utilization. In this paper, we investigate the path selection problem in multihop cognitive radio networks (CRNs) under constraints on flow routing, link scheduling and CR source's budget. We extend the per-user-based spectrum trading in prior work to CR session-based spectrum trading, and effectively develop the spectrum trading mechanisms based on the cross-layer optimization in multihop CRNs. We introduce a new service provider, called secondary service provider (SSP), to help CR sessions to select the paths for packet delivery. Considering the price of bands and the potential returning of primary services at different CR links, the SSP purchases the licensed spectrum and jointly conducts flow routing and link scheduling under the budget constraints. We also propose a 4D conflict graph to characterize the conflict relationship among CR links and mathematically formulate the path selection problem under multiple constraints into an optimization problem with the objective of maximizing the end-to-end throughput. Due to the NP-hardness of the problem, we have also developed a heuristic algorithm to find the approximate solution. [ABSTRACT FROM AUTHOR]

In this paper, a cross-layer optimal scheduling algorithm for cooperative multi-hop Cognitive Radio Networks (CRNs) is presented, where secondary users (SUs) assist primary users' (PUs') multi-hop transmissions and in return gain an immediate time-share of the channel proportional to their assistance. While providing deterministic upper-bounds for PU queue backlogs, the proposed algorithm approaches the optimal PU throughput arbitrarily close, with a tradeoff in the average delay upper-bounds of flows. The analysis is further extended to a model with a more general "long-term reward mechanism", where a time-averaged share of the channel is guaranteed for SUs. The proposed algorithm provides order-optimal delay for the primary traffic. Distributed implementation issues have also been investigated. The properties of the proposed algorithm have also been illustrated through simulation studies. [ABSTRACT FROM PUBLISHER]

We suggest and analyze algorithms for routing in multi-hop wireless ad-hoc networks that exploit mutual information accumulation as the physical layer transmission scheme, and are capable of routing multiple packet streams (commodities) when only the average channel state information is present, and that only locally. The proposed algorithms are the modifications of the diversity backpressure (DIVBAR) algorithm, under which the packet whose commodity has the largest “backpressure metric” is chosen to be transmitted and is forwarded through the link with the largest differential backlog (queue length). In contrast to traditional DIVBAR, each receiving node stores and accumulates the partially received packet in a separate “partial packet queue”, thus increasing the probability of successful reception during a later possible retransmission. We present two variants of the algorithm: DIVBAR-renewal mutual information accumulation (RMIA), under which all the receiving nodes clear the received partial information of a packet once one or more receiving nodes firstly decode the packet; and DIVBAR-full mutual information accumulation (FMIA), under which all the receiving nodes retain the partial information of a packet until the packet has reached its destination. We characterize the network capacity region with the RMIA transmission scheme and prove that (under certain mild conditions) it is strictly larger than the network capacity region with the repetition (REP) transmission scheme that is used by the traditional DIVBAR. We also prove that DIVBAR-RMIA is throughput-optimal among the policies with RMIA, i.e., it achieves the network capacity region with RMIA, which in turn demonstrates that DIVBAR-RMIA outperforms traditional DIVBAR with respect to the achievable throughput. Moreover, we prove that DIVBAR-FMIA performs at least as well as DIVBAR-RMIA with respect to throughput. Simulations also confirm these results. [ABSTRACT FROM PUBLISHER]

In this paper, we introduce the concept of "route robustness" for path selection in multi-hop cognitive radio networks. We demonstrate that the aggregate throughput and the robustness of routes determined by the proposed route selection strategy are superior to existing rate-based selection strategies. The rationale behind our approach is to guarantee a basic level of robustness for a set of routes (referred to as skeletons in this paper). Then, we select some routes from this robust route set and determine the spectrum to be allocated on each link along these routes such that the system throughput is maximized. We also design a polynomial time algorithm for this problem, and evaluate our proposed mechanism via simulations. The results show that our proposed algorithm indeed achieves a near optimal solution of this problem for multi-hop overlay CR networks. [ABSTRACT FROM PUBLISHER]

This work is an offline study to characterize the performance of cooperative relaying in interference-limited multihop networks, where nodes are equipped with multi-rate and continuous power control capabilities. We formulate a cross-layer flow-based framework to obtain the achievable throughput rates by jointly optimizing the parameters for multi-path routing, scheduling, rates, transmit powers, and selection of cooperative nodes. This framework is generic in that it is not restricted to any particular cooperative combining technique or type of network architecture. To take continuous power control into account, we introduce a non-trivial power allocation subproblem while keeping the main cross-layer framework as a linear program. We solve the problem optimally to obtain the max–min throughput for the case when cooperation is based on the distributed Alamouti code and networks have a mesh-like topology. We derive a number of practical engineering insights based on our numerical optimal results obtained for small-to-medium-sized random networks. In particular, we establish that the use of cooperative relaying in a small-to-medium-sized random mesh network often does not yield significant performance gains in throughput and connectivity even when multi-rate and continuous power control capabilities are available at the nodes. [ABSTRACT FROM PUBLISHER]

Two major factors that limit the throughput in multi-hop wireless networks are the co-channel interference and unreliability of wireless transmissions. Multi-radio multi-channel technology and opportunistic routing (OR) have shown their promise to significantly improve the network capacity by combating these two limits. It raises an interesting problem on the tradeoff between multiplexing and spatial diversity when integrating these two techniques for throughput optimization. It is unknown what the capacity of the network could be when nodes have multiple radios and OR capability. In this paper, we present our study on optimizing an end-to-end throughput of the multi-radio multi-channel network when OR is available. First, we formulate the end-to-end throughput bound as a linear programming (LP) problem which jointly solves the radio-channel assignment, transmission scheduling, and forwarding candidate selection. Second, we propose an LP approach and a heuristic algorithm to find a feasible scheduling of opportunistic forwarding priorities to achieve the capacity. Simulations show that the heuristic algorithm achieves desirable performance under various number of forwarding candidates. Leveraging our analytical model, we find that 1) OR can achieve better performance than traditional routing (TR) under different radio/channel configurations, however, in particular scenario (e.g. bottleneck links exist between the sender and relays), TR is preferable; 2) OR can achieve comparable or better performance than TR by using less radio resource. [ABSTRACT FROM PUBLISHER]

Multihop self-backhauling is a key enabling technology for millimeter wave cellular deployments. We consider the multihop link scheduling problem with the objective of minimizing the end-to-end delay experienced by a typical packet. This is a complex problem, and so we model the system as a network of queues and formulate it as a Markov decision process over a continuous action space. This allows us to leverage the deep deterministic policy gradient algorithm from reinforcement learning to learn the delay minimizing scheduling policy under two scenarios: 1) an ideal setup where a centralized scheduler performs all per slot scheduling decisions and has full instantaneous knowledge of network state and 2) a centralized scheduler, but where network state feedback and scheduling decisions are limited to once per frame, which is many slots. For the second scenario, we model the scheduler with a recurrent neural network to capture the evolution of the network state over the frame. Detailed system-level simulations show that for the more realistic second scenario, the delay experienced by the 5th percentile packets under backpressure based scheduling and max-min scheduling can be up to 230% and 260%, respectively more than that under the proposed scheduler. [ABSTRACT FROM AUTHOR]

Fair allocation of resources is an important consideration in the design of wireless networks. In this paper, we consider the setting of multihop wireless networks with multiple routing paths and develop an online flow control and scheduling algorithm for packet admission and link activation that achieves high aggregate throughput while providing different data flows with a fair share of network capacity. For fairness provisioning, we seek to maximize the minimum throughput provided to flows in the network. To cope with different degrees of data reliability among the different links in the network, we use different channel code rates as appropriate. While we expect performance improvement using channel coding and multipath routing, the main contribution of our work is a joint treatment of network stability, multipath routing and link-level reliability in meeting the overarching goal of maxmin fairness. We develop a decentralized, and hence practical, scheduling policy that addresses various concerns and demonstrate, via simulations, that it is competitive with respect to an optimal centralized rate allocator. We also evaluate the fairness provisioning under the proposed algorithm and show that channel coding improves the performance of the network significantly. Finally, we show through simulations that the proposed algorithm outperforms a class of existing approaches on fairness provisioning, which are developed based on utility maximization. [ABSTRACT FROM PUBLISHER]

Although the back-pressure (BP) algorithm has been proven to be a throughput-optimal policy for traffic scheduling and routing in wireless networks, the optimal control of delays in the BP algorithm remains an open problem, especially for conventional multihop networks. To enhance the delay performance, we proposed an improved BP algorithm called sojourn-time-based BP (STBP) by introducing a novel delay metric called the sojourn time backlog (STB). The STB considers the queue length and accumulated packet delays comprehensively. It provides more pressure to push forward flows suffering from greater delays. Based on this new metric, the calculation of the routing weight for each packet is determined for maximizing the difference of the STB in the routing process. The proposed routing algorithm is robust and distributed, and does not require any prior knowledge of network connections and load conditions. We analyze the network stability with delay considerations and prove the throughput optimality of the STBP in multihop networks. Simulation results reveal that the enhanced algorithm effectively improves the end-to-end delay while ensuring throughput optimality. [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]

This letter addresses the dynamic resource control and routing problem in multihop wireless networks with time-varying channels. Subject to different per-flow end-to-end delay requirements, a new queue management policy is designed and then, a delay parameter is introduced by combining both delay constraints and path length to destination nodes. By taking advantage of the delay parameter and the queue management policy, this letter proposes a congestion control, routing and scheduling backpressure algorithm. The proposed algorithm not only approaches arbitrarily close to the optimal throughput, but also adaptively selects favorable routes according to per-flow delay constraints. Simulation results show our algorithm effectively achieves a well-performed delay performance while ensuring the throughput. [ABSTRACT FROM PUBLISHER]

In this letter, we study throughput-optimal scheduling policies in single-path buffer-aided relay networks, where the packets of a user travel one fixed path from the source to the destination and do not require routing. We modify the well-known Max-Weight (MW) policy and propose a version of throughput-optimal algorithms, which we refer to as Modified MW (MMW). In MMW, by defining a suitably large threshold, a link's weight is proportional to just the corresponding local queue size either in the base station or the relay station, in most of the time slots. Moreover, a parameter can be adjusted for improving delay fairness between the relayed and direct users. MMW is suitable for use in both shared and independent channel scenarios and facilitates decentralized network implementations. Numerical results confirm that MMW is better able to provide similar performance for direct and relayed users in terms of queueing delay, compared with the existing algorithms. [ABSTRACT FROM PUBLISHER]

Large-scale multi-hop wireless networks have many important applications. However, Gupta and Kumar showed that the capacity of multi-hop wireless networks decreases as the number of nodes in the network increases. Subsequent research efforts to achieve linear capacity scaling have significant limitations such as long latency, high technical complexity, restricted traffic pattern, or infrastructure requirement. We propose to achieve close-to-linear (CTL) capacity scaling through the use of directed energy (DE) links such as laser communications links or highly directional pencil beam links in the EHF band in a hybrid network that also contains traditional omni-directional (OD) antenna links. Our approach has none of limitations mentioned earlier. We show that when the probability distribution of DE links follows the inverse-square law, a distributed scheme with local routing information suffice to achieve CTL capacity scaling. [ABSTRACT FROM PUBLISHER]

We investigate the problem of designing delay-aware joint flow control, routing, and scheduling algorithms in general multi-hop networks for maximizing network utilization. Since the end-to-end delay performance has a complex dependence on the high-order statistics of cross-layer algorithms, earlier optimization-based design methodologies that optimize the long term network utilization are not immediately well-suited for delay-aware design. This motivates us in this work to develop a novel design framework and alternative methods that take advantage of several unexploited design choices in the routing and the scheduling strategy spaces. In particular, we reveal and exploit a crucial characteristic of back pressure-type controllers that enables us to develop a novel link rate allocation strategy that not only optimizes long-term network utilization, but also yields loop free multi-path routes between each source-destination pair. Moreover, we propose a regulated scheduling strategy, based on a token-based service discipline, for shaping the per-hop delay distribution to obtain highly desirable end-to-end delay performance. We establish that our joint flow control, routing, and scheduling algorithm achieves loop-free routes and optimal network utilization. Our extensive numerical studies support our theoretical results, and further show that our joint design leads to substantial end-to-end delay performance improvements in multi-hop networks compared to earlier solutions. [ABSTRACT FROM PUBLISHER]