This paper introduces a protocol that distributively constructs a collision-free schedule for multi-hop packet radio networks in the presence of hidden terminals. As a preliminary step, each wireless station computes the schedule length after gathering information about the number of flows in its neighbourhood. Then, a combination of deterministic and random backoffs are used to reach a collision-free schedule. A deterministic backoff is used after successful transmissions and a random backoff is used otherwise. It is explained that the short acknowledgement control packets can easily result in channel time fragmentation and, to avoid this, the use of link layer delayed acknowledgements is advocated and implemented. The performance results show that a collision-free protocol easily outperforms a collision-prone protocol such as Aloha. The time that is required for the network to converge to a collision-free schedule is assessed by means of simulation.
A general discussion of this class of protocols, together with performance comparisons and protocol refinements, is offered in @cite_12 . This last paper also introduces the concepts of stickiness and variable schedule length to accommodate a larger number of contenders in slotted networks. In the present work, we will reuse both concepts in the context of multi-hop packet radio networks.
@cite_12
2033017950 2124107362 2071787409 2098222105 2107421266 2088693732 1491256424 2154594768 2963418374 2102224707 2107505399 2113952765 2059746594 2139644003 2027034953 2099654130 2102200576 2114106914 2115537518 2949886575
This paper provides a general framework for analyzing the stability of general nonlinear networked control systems (NCS) with disturbances in the setting of stability. Our presentation provides sharper results for both gain and maximum allowable transfer interval (MATI) than previously obtainable and details the property of uniformly persistently exciting scheduling protocols. This class of protocols was shown to lead to stability for high enough transmission rates and were a natural property to demand, especially in the design of wireless scheduling protocols. The property is used directly in a novel proof technique based on the notions of vector comparison and (quasi)-monotone systems. We explore these results through analytical comparisons to those in the literature, as well as through simulations and numerical comparisons that verify that the uniform persistence of excitation property of protocols is, in some sense, the ldquofinestrdquo property that can be extracted from wireless scheduling protocols. We consider a frequency-flat fading multihop network with a single active source-destination pair terminals communicating over multiple hops through a set of intermediate relay terminals. We use Shannon-theoretic tools to analyze the tradeoff between energy efficiency and spectral efficiency (known as the power-bandwidth tradeoff) for a simple communication protocol based on time-division decode-and-forward relaying in meaningful asymptotic regimes of signal-to-noise ratio (SNR) under a system-wide power constraint on source and relay transmissions. The impact of multi-hopping and channel fading on the key performance measures of the high and low SNR regimes is investigated to shed new light on the possible enhancements in power bandwidth efficiency and link reliability. In contrast to the common belief that in fading environments communicating over multiple hops suffers significantly in performance due to the worst link limitation, our results indicate that hopping could significantly improve the outage behavior over slow-fading networks and stabilize links against the random channel fluctuations. In particular, we prove that there exists an optimal number of hops that minimizes the end-to-end outage probability and characterize the dependence of this optimal number on the fading statistics and target energy and spectral efficiencies. This paper presents the evaluation of the multi-hop aggregate information efficiency of the slotted and unslotted ALOHA protocols. We consider a multi-hop wireless network where the nodes are spatially characterized by a Poisson point process and the traffic generation also follows a Poisson distribution. By applying the properties of stochastic geometry, we derive a closed-form lower bound on the outage probability as a function of the required communication rate, the single-hop distance, the number of hops and the maximum number of retransmissions. The results indicate that slotted ALOHA always outperforms its unslotted version, demonstrating the importance of synchronization in distributed networks. In addition, we show that it is always possible to optimize the network efficiency by properly setting the required rate for a given packet density. Finally, in the scenario considered, the use of retransmissions and multiple hops never achieves the best performance if compared to the option of single-hop links without retransmissions. This paper presents an efficient protocol for reliably exchanging information in a single-hop, multi-channel radio network subject to unpredictable interference. We model the interference by an adversary that can simultaneously disrupt up to t of the C available channels. We assume no shared secret keys or third-party infrastructure. The running time of our protocol depends on the gap between C and t: when the number of channels C =Omega(t^2), the running time is linear; when only C = t+1 channels are available, the running time is exponential. We prove that exponential-time is unavoidable in the latter case. At the core of our protocol lies a combinatorial function, possibly of independent interest, described for the first time in this paper: the multi-selector. A multi-selector generates a sequence of channel assignments for each device such that every sufficiently large subset of devices is partitioned onto distinct channels by at least one of these assignments. A comprehensive study of the problem of scheduling broadcast transmissions in a multihop, mobile packet radio network is provided that is based on throughput optimization subject to freedom from interference. It is shown that the problem is NP complete. A centralized algorithm that runs in polynomial time and results in efficient (maximal) schedules is proposed. A distributed algorithm that achieves the same schedules is then proposed. The algorithm results in a maximal broadcasting zone in every slot. > The scheduling problem in multi-hop wireless networks has been extensively investigated. Although throughput optimal scheduling solutions have been developed in the literature, they are unsuitable for multi-hop wireless systems because they are usually centralized and have very high complexity. In this paper, we develop a random-access based scheduling scheme that utilizes local information. The important features of this scheme include constant-time complexity, distributed operations, and a provable performance guarantee. Analytical results show that it guarantees a larger fraction of the optimal throughput performance than the state-of-the-art. Through simulations with both single-hop and multi-hop traffics, we observe that the scheme provides high throughput, close to that of a well-known highly efficient centralized greedy solution called the greedy maximal scheduler. In this paper we study the problem of assigning transmission ranges to the nodes of a multi-hop packet radio network so as to minimize the total power consumed under the constraint that adequate power is provided to the nodes to ensure that the network is strongly connected (i.e., each node can communicate along some path in the network to every other node). Such assignment of transmission ranges is called complete. We also consider the problem of achieving strongly connected bounded diameter networks. This paper studies the problem of scheduling in single-hop wireless networks with real-time traffic, where every packet arrival has an associated deadline and a minimum fraction of packets must be transmitted before the end of the deadline. Using optimization and stochastic network theory we study the problem of scheduling to meet quality of service (QoS) requirements under heterogeneous delay constraints and time-varying channel conditions. Our analysis results in an optimal scheduling algorithm which fairly allocates data rates to all flows while meeting long-term delay demands. We also prove that under a simplified scenario our solution translates into a greedy strategy that makes optimal decisions with low complexity. Future 5G cellular networks supporting delay-sensitive, low-latency communications could employ random access communication to reduce the overhead compared to scheduled access techniques used in 4G networks. We consider a wireless communication system where multiple devices transmit payloads of a given fixed size in a random access fashion over shared radio resources to a common receiver. We allow retransmissions and assume Chase combining at the receiver. The radio resources are partitioned in the time and frequency dimensions, and we determine the optimal partition granularity to maximize throughput, subject to given constraints on latency and outage. In the regime of high and low signal-to-noise ratio (SNR), we derive explicit expressions for the granularity and throughput, first using a Shannon capacity approximation and then using finite block length analysis. Numerical results show that the throughput scaling results are applicable over a range of SNRs. The proposed analytical framework can provide insights for resource allocation strategies in reliable and delay-sensitive random access systems and in specific 5G use cases for massive, short packet uplink access. We consider the problem of designing an online scheduling scheme for a multi-hop wireless packet network with arbitrary topology and operating under arbitrary scheduling constraints. The objective is to design a scheme that achieves high throughput and low delay simultaneously. We propose a scheduling scheme that - for networks operating under primary interference constraints - guarantees a per-flow end-to-end packet delay bound of 5dj (1-ρj), at a factor 5 loss of throughput, where dj is the path length (number of hops) of flow j and ρj is the effective loading along the route of flow j. Clearly, dj is a universal lower bound on end-to-end packet delay for flow j. Thus, our result is essentially optimal. To the best of our knowledge, our result is the first one to show that it is possible to achieve a per-flow end-to-end delay bound of O(# of hops) in a constrained network. Designing such a scheme comprises two related subproblems: Global Scheduling and Local Scheduling. Global Scheduling involves determining the set of links that will be simultaneously active, without violating the scheduling constraints. While local scheduling involves determining the packets that will be transferred across active edges. We design a local scheduling scheme by adapting the Preemptive Last-In-First-Out (PL) scheme, applied for quasi-reversible continuous time networks, to an unconstrained discrete-time network. A global scheduling scheme will be obtained by using stable marriage algorithms to emulate the unconstrained network with the constrained wireless network. Our scheme can be easily extended to a network operating under general scheduling constraints, such as secondary interference constraints, with the same delay bound and a loss of throughput that depends on scheduling constraints through an intriguing "sub-graph covering" property. In multi-hop ad hoc networks, the efficiency of a medium access control protocol under heavy traffic load depends mainly on its ability to schedule a large number of simultaneous non-interfering transmissions. However, as each node has only a local view of the network, it is difficult to globally synchronize transmission times over the whole network. How does the lack of global coordination affect spatial reuse in multi-hop wireless networks? We show that in a de-centralized network the spatial reuse does not benefit from global clock synchronization. On the contrary, we demonstrate that non-slotted protocols using collision avoidance mechanisms can achieve a higher spatial reuse than the corresponding slotted protocols. By means of a simple backoff mechanism, one can thus favor the spontaneous emergence of spatially dense transmission schedules. In this paper, we propose a cross layer optimization framework for multi-hop routing and resource allocation design in an orthogonal frequency division multiple access (OFDMA) based wireless mesh network. The network under consideration is assumed to consist of fixed mesh routers (or base station routers) inter-connected using OFDMA wireless links with some of the mesh routers functioning as gateways to a wired network. The objective of our cross-layer formulation is to allow joint determination of power control, frequency-selective OFDMA scheduling and multi-hop routing in order to maximize the minimum throughput that can be supported to all mesh routers. Results of our investigations under typical cellular deployment, propagation and channel model assumptions show that this approach achieves significant mesh throughput improvements primarily due to the following: (a) frequency selective scheduling with OFDMA which provides improved tone diversity thus allowing more efficient bandwidth utilization relative to single carrier methods; and (b) multi-hop routing which provides improved path diversity relative to single hop transmissions. Packet scheduler at the medium access control (MAC) layer is essential to improve radio resource utilization in the Long Term Evolution (LTE) network. The MAC scheduler allocates resource blocks to user terminals (UEs) according to the priority metric, which varies in different scheduling algorithms. Although there have been many studies on the performance of LTE schedulers at the MAC layer, it is interesting to evaluate the impact of different LTE MAC schedulers on the transport layer, particularly on the transmission control protocol (TCP). In this study, we implement three mainstream LTE MAC schedulers in Network Simulator-3 (NS-3), namely, maximum throughput (MT), blind equal throughput (BET) and proportional fair (PF). Extensive simulations are conducted to examine the different TCP throughput achieved with the frequency domain version and the time domain version of these schedulers in a vehicular environment. The performance difference is attributed to important factors such as the resource allocation granularity, channel-awareness in scheduling, and the number of UEs. Accurate analytical expressions of delay and packet reception probabilities, and energy consumption of duty-cycled wireless sensor networks with random medium access control (MAC) are instrumental for the efficient design and optimization of these resource-constrained networks. Given a clustered network topology with unslotted IEEE 802.15.4 and preamble sampling MAC, a novel approach to the modeling of the delay, reliability, and energy consumption is proposed. The challenging part in such a modeling is the random MAC and sleep policy of the receivers, which prevents to establish the exact time of data packet transmission. The analysis gives expressions as function of sleep time, listening time, traffic rate and MAC parameters. The analytical results are then used to optimize the duty cycle of the nodes and MAC protocol parameters. The approach provides a significant reduction of the energy consumption compared to existing solutions in the literature. Monte Carlo simulations by ns2 assess the validity of the analysis. We consider the question of obtaining tight delay guarantees for throughout-optimal link scheduling in arbitrary topology wireless ad-hoc networks. Two classes of scheduling policies are considered: 1) a maximum queue-length weighted independent set scheduling policy and 2) a randomized independent set scheduling policy where the set scheduling probabilities are selected optimally. Both policies stabilize all queues for any set of feasible packet arrival rates, and are therefore throughput-optimal. For these policies, we show that the average packet delay is bounded by a constant that depends on the chromatic number of the interference graph, and the arrival slack in the system-a metric representing the overall load on the network. We prove that this upper bound is asymptotically tight in the sense that there exist classes of topologies where the expected delay attained by any scheduling policy is lower bounded by the same constant. We extend our upper bounds to the case of multi-hop sessions. Through simulations, we study how our analysis compares with actual delays computed for i.i.d., Markovian, and trace-driven packet arrival processes. Emerging spread spectrum high-speed data networks utilize multiple channels via orthogonal codes or frequency-hopping patterns such that multiple users can transmit concurrently. In this paper, we develop a framework for opportunistic scheduling over multiple wireless channels. With a realistic channel model, any subset of users can be selected for data transmission at any time, albeit with different throughputs and system resource requirements. We first transform selection of the best users and rates from a complex general optimization problem into a decoupled and tractable formulation: a multiuser scheduling problem that maximizes total system throughput and a control-update problem that ensures long-term deterministic or probabilistic fairness constraints. We then design and evaluate practical schedulers that approximate these objectives. Recent advances in multi-radio multi-channel transmission technology have the potential of substantially improving the system capacity in multi-hop wireless networks. While previous work has primarily focused on the link level protocol design, in this paper we investigate the achievable performance gain, by jointly optimizing routing and scheduling in a multi-radio multichannel multi-hop network. We formulate the optimization under a deterministic model, and we seek to minimize overall system activation time in use to satisfy given end-to-end traffic demands subjected to the multi-access interference among neighboring transmissions and the radio interface constraint at each node. The exact solution to such an optimization problem is prohibitively complex due to the combinatorial complexity, particularly with the deployment of multi-radio and multi-channel. We develop a column generation based approach to solve this problem, which decomposes the original problem into sub-problems and solves them iteratively. Numerical results are given, and discussions as well as insights into the performance aspects for multi-radio multichannel deployment are provided. We develop a new metric for quantifying end-to-end throughput in multihop wireless networks, which we term random access transport capacity, since the interference model presumes uncoordinated transmissions. The metric quantifies the average maximum rate of successful end-to-end transmissions, multiplied by the communication distance, and normalized by the network area. We show that a simple upper bound on this quantity is computable in closed-form in terms of key network parameters when the number of retransmissions is not restricted and the hops are assumed to be equally spaced on a line between the source and destination. We also derive the optimum number of hops and optimal per hop success probability and show that our result follows the well-known square root scaling law while providing exact expressions for the preconstants, which contain most of the design-relevant network parameters. Numerical results demonstrate that the upper bound is accurate for the purpose of determining the optimal hop count and success (or outage) probability. We first consider a multi-user, single-hop wireless network with arbitrarily varying (and possibly non-ergodic) arrivals and channels. We design an opportunistic scheduling algorithm that guarantees all sessions have a bounded worst case delay. The algorithm has no knowledge of the future, but yields throughput-utility that is close to (or better than) that of a T-slot lookahead policy that makes “ideal” decisions based on perfect knowledge up to T slots into the future. We then extend the algorithm to treat worst case delay guarantees in multi-hop networks. Our analysis uses a sample-path version of Lyapunov optimization together with a novel virtual queue structure. In this paper, we consider CSMA policies for scheduling of multihop wireless networks with one-hop traffic. The main contribution of this paper is to propose Unlocking CSMA (U-CSMA) policy that enables to obtain high throughput with low (average) packet delay for large wireless networks. In particular, the delay under U-CSMA policy becomes order-optimal. For one-hop traffic, delay is defined to be order-optimal if it is O(1), i.e., it stays bounded, as the network-size increases to infinity. Using mean field theory techniques, we analytically show that for torus (grid-like) interference topologies with one-hop traffic, to achieve a network load of @math , the delay under U-CSMA policy becomes @math as the network-size increases, and hence, delay becomes order optimal. We conduct simulations for general random geometric interference topologies under U-CSMA policy combined with congestion control to maximize a network-wide utility. These simulations confirm that order optimality holds, and that we can use U-CSMA policy jointly with congestion control to operate close to the optimal utility with a low packet delay in arbitrarily large random geometric topologies. To the best of our knowledge, it is for the first time that a simple distributed scheduling policy is proposed that in addition to throughput utility-optimality exhibits delay order-optimality.