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.
To further complicate the issue, wireless propagation introduces an additional degree of randomness and unpredictability to the network. In order to advance in the analysis of multi-hop packet radio networks, some simplifications are in order. One of the most common modeling assumptions is the use of a graph representation of the network, where an edge exists between two stations if they are in the transmission range of each other. As an example, @cite_28 uses a graph representation to show that determining whether a traffic matrix belongs to the capacity region of a packet radio network is NP hard. We will use the graph topology representation and several other assumptions in the present paper.
@cite_28
2114927595 2027916448 2151792936 2053616686 2110360611 1981696935 2095074540 2219211182 2161281242 2048655757 1555881611 2150450717 2018438786 2114106914 2058571581 2156464137 2071787409 1778740484 2435603672 2115314281
We consider networks consisting of nodes with radios, and without any wired infrastructure, thus necessitating all communication to take place only over the shared wireless medium. The main focus of this paper is on the effect of fading in such wireless networks. We examine the attenuation regime where either the medium is absorptive, a situation which generally prevails, or the path loss exponent is greater than 3. We study the transport capacity, defined as the supremum over the set of feasible rate vectors of the distance weighted sum of rates. We consider two assumption sets. Under the first assumption set, which essentially requires only a mild time average type of bound on the fading process, we show that the transport capacity can grow no faster than O(n), where n denotes the number of nodes, even when the channel state information (CSI) is available noncausally at both the transmitters and the receivers. This assumption includes common models of stationary ergodic channels; constant, frequency-selective channels; flat, rapidly varying channels; and flat slowly varying channels. In the second assumption set, which essentially features an independence, time average of expectation, and nonzeroness condition on the fading process, we constructively show how to achieve transport capacity of spl Omega (n) even when the CSI is unknown to both the transmitters and the receivers, provided that every node has an appropriately nearby node. This assumption set includes common models of independent and identically distributed (i.i.d.) channels; constant, flat channels; and constant, frequency-selective channels. The transport capacity is achieved by nodes communicating only with neighbors, and using only point-to-point coding. The thrust of these results is that the multihop strategy, toward which much protocol development activity is currently targeted, is appropriate for fading environments. The low attenuation regime is open. In a wireless network, the set of transmitting nodes changes frequently because of the MAC scheduler and the traffic load. Analyzing the connectivity of such a network using static graphs would lead to pessimistic performance results. In this paper, we consider an ad hoc network with half-duplex radios that uses multihop routing and slotted ALOHA for the network MAC contention and introduce a random dynamic multi-digraph to model its connectivity. We first provide analytical results about the degree distribution of the graph. Next, defining the path formation time as the minimum time required for a causal path to form between the source and destination on the dynamic graph, we derive the distributional properties of the connection delay using techniques from first-passage percolation and epidemic processes.We show that the delay scales linearly with the distance and provide asymptotic results (with respect to time) for the positions of the nodes which are able to receive information from a transmitter located at the origin. We also provide simulation results to support the theoretical results. This paper surveys and unifies a number of recent contributions that have collectively developed a metric for decentralized wireless network analysis known as transmission capacity. Although it is notoriously difficult to derive general end-to-end capacity results for multi-terminal or adhoc networks, the transmission capacity (TC) framework allows for quantification of achievable single-hop rates by focusing on a simplified physical MAC-layer model. By using stochastic geometry to quantify the multi-user interference in the network, the relationship between the optimal spatial density and success probability of transmissions in the network can be determined, and expressed-often fairly simply-in terms of the key network parameters. The basic model and analytical tools are first discussed and applied to a simple network with path loss only and we present tight upper and lower bounds on transmission capacity (via lower and upper bounds on outage probability). We then introduce random channels (fading shadowing) and give TC and outage approximations for an arbitrary channel distribution, as well as exact results for the special cases of Rayleigh and Nakagami fading. We then apply these results to show how TC can be used to better understand scheduling, power control, and the deployment of multiple antennas in a decentralized network. The paper closes by discussing shortcomings in the model as well as future research directions. Compared to single-hop networks such as WiFi, multihop infrastructure wireless mesh networks (WMNs) can potentially embrace the broadcast benefits of a wireless medium in a more flexible manner. Rather than being point-to-point, links in the WMNs may originate from a single node and reach more than one other node. Nodes located farther than a one-hop distance and overhearing such transmissions may opportunistically help relay packets for previous hops. This phenomenon is called opportunistic overhearing listening. With multiple radios, a node can also improve its capacity by transmitting over multiple radios simultaneously using orthogonal channels. Capitalizing on these potential advantages requires effective routing and efficient mapping of channels to radios (channel assignment (CA)). While efficient channel assignment can greatly reduce interference from nearby transmitters, effective routing can potentially relieve congestion on paths to the infrastructure. Routing, however, requires that only packets pertaining to a particular connection be routed on a predetermined route. Random network coding (RNC) breaks this constraint by allowing nodes to randomly mix packets overheard so far before forwarding. A relay node thus only needs to know how many packets, and not which packets, it should send. We mathematically formulate the joint problem of random network coding, channel assignment, and broadcast link scheduling, taking into account opportunistic overhearing, the interference constraints, the coding constraints, the number of orthogonal channels, the number of radios per node, and fairness among unicast connections. Based on this formulation, we develop a suboptimal, auction-based solution for overall network throughput optimization. Performance evaluation results show that our algorithm can effectively exploit multiple radios and channels and can cope with fairness issues arising from auctions. Our algorithm also shows promising gains over traditional routing solutions in which various channel assignment strategies are used. The wireless sensor networks community, has now an increased understanding of the need for realistic link layer models. Recent experimental studies have shown that real deployments have a "transitional region" with highly unreliable links, and that therefore the idealized perfect-reception-within-range models used in common network simulation tools can be very misleading. In this paper, we use mathematical techniques from communication theory to model and analyze the low power wireless links. The primary contribution of this work is the identification of the causes of the transitional region, and a quantification of their influence. Specifically, we derive expressions for the packet reception rate as a function of distance, and for the width of the transitional region. These expressions incorporate important channel and radio parameters such as the path loss exponent and shadowing variance of the channel; and the modulation and encoding of the radio. A key finding is that for radios using narrow-band modulation, the transitional region is not an artifact of the radio non-ideality, as it would exist even with perfect-threshold receivers because of multi-path fading. However, we hypothesize that radios with mechanisms to combat multi-path effects, such as spread-spectrum and diversity techniques, can reduce the transitional region. We consider broadcasting in radio networks, modeled as undirected graphs, whose nodes know only their own label and labels of their neighbors. In every step every node acts either as a transmitter or as a receiver. A node acting as a transmitter sends a message which can potentially reach all of its neighbors. A node acting as a receiver in a given step gets a message if and only if exactly one of its neighbors transmits in this step. Bar-Yehuda, Goldreich, and Itai [J. Comput. System Sci., 45 (1992), pp. 104--126] considered broadcasting in this model. They claimed a linear lower bound on the time of deterministic broadcasting in such radio networks of diameter 3. This claim turns out to be incorrect in this model (although it is valid in a more pessimistic model [R. Bar-Yehuda, O. Goldreich, and A. Itai, Errata Regarding "On the time complexity of broadcast in radio networks: An exponential gap between determinism and randomization," http: www.wisdom.weizmann.ac.il mathusers oded p .html, 2002]). We construct an algorithm that broadcasts in logarithmic time on all graphs from the Bar-Yehuda, Goldreich, and Itai paper (BGI). Moreover, we show how to broadcast in sublinear time on all n-node graphs of diameter @math . On the other hand, we construct a class of graphs of diameter 4, such that every broadcasting algorithm requires time @math on these graphs. In view of the randomized algorithm from BGI, running in expected time @math on all @math -node graphs of diameter D (cf. also a recent @math -time algorithm from [D. Kowalski and A. Pelc, Proceedings of the 22nd Annual ACM Symposium on Principles of Distributed Computing, Boston, 2003, pp. 73--82; A. Czumaj and W. Rytter, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, Cambridge, MA, 2003, pp. 492--501]), our lower bound gives the first correct proof of an exponential gap between determinism and randomization in the time of radio broadcasting, under the considered model of radio communication. A fundamental problem for the delay and backlog analysis across multihop paths in wireless networks is how to account for the random properties of the wireless channel. Since the usual statistical models for radio signals in a propagation environment do not lend themselves easily to a description of the available service rate, the performance analysis of wireless networks has resorted to higher-layer abstractions, e.g., using Markov chain models. In this paper, we propose a network calculus that can incorporate common statistical models of fading channels and obtain statistical bounds on delay and backlog across multiple nodes. We conduct the analysis in a transfer domain, where the service process at a link is characterized by the instantaneous signal-to-noise ratio at the receiver. We discover that, in the transfer domain, the network model is governed by a dioid algebra, which we refer to as the (min, ×) algebra. Using this algebra, we derive the desired delay and backlog bounds. Using arguments from large deviations theory, we show that the bounds are asymptotically tight. An application of the analysis is demonstrated for a multihop network of Rayleigh fading channels with cross traffic at each hop. Multi-hop wireless networks are often regarded as a promising means to extend the limited coverage area offered by WLANs. However, they are usually associated with poor and uncertain performance in terms of available bandwidth and packet losses, which clearly stands as a limitation to their use. In this paper, we consider the performance evaluation of a multi-hop path (also called chain), based on the IEEE 802.11 DCF. The proposed modeling framework is constructive and versatile, so that it can handle various types of multi-hop wireless paths, including scenarios with two flows in opposite directions, and topologies where nodes are exposed to the well-known hidden node problem. The models derived from our framework are conceptually simple, easy to implement and produce generally accurate results for the attained goodput of flows, as well as the datagram loss probability. Typical relative errors for these two quantities are below a few percent. Also, fundamental phenomena occurring in multi-hop wireless networks, such as performance collapse and starvation, are well captured by the models. In much of the theoretical literature on wireless algorithms, issues of message dissemination are considered together with issues of contention management. This combination leads to complicated algorithms and analysis, and makes it difficult to extend the work to harder communication problems. In this paper, we present results of a current project aimed at simplifying such algorithms and analysis by decomposing the treatment into two levels, using abstract "MAC layer" specifications to encapsulate the contention management. We use two different abstract MAC layers: the basic one of [14, 15] and a new probabilistic layer. We first present a typical randomized contention-manageent algorithm for a standard graph-based radio network model We show that it implements both abstract MAC layers. We combine this algorithm with greedy algorithms for single-message and multi-message global broadcast and analyze the combination, using both abstract MAC layers as intermediate layers. Using the basic MAC layer, we prove a bound of O(D log(n ∈) log Δ) for the time to deliver a single message everywhere with probability 1 -- ∈, where D is the network diameter, n is the number of nodes, and Δ is the maximum node degree. Using the probabilistic layer, we prove a bound of O((D + log(n ∈)) log Δ), which matches the best previously-known bound for single-message broadcast over the physical network model. For multi-message broadcast, we obtain bounds of O((D + kΔ) log(n ∈) log Δ) using the basic layer and O((D + kΔ log(n ∈)) log Δ) using the probabilistic layer, for the time to deliver a message everywhere in the presence of at most k concurrent messages. The unstructured multi-hop radio network model, with asynchronous wake-up, no collision detection and little knowledge on the network topology, is proposed for capturing the particularly harsh characteristics of initially deployed wireless adhoc and sensor networks. In this paper, assuming such a practical model, we study a fundamental problem of both theoretical and practical interests--the local broadcasting problem. Given a set of nodes V where each node wants to broadcast a message to all its neighbors that are within a certain local broadcasting range R, the problem is to schedule all these requests in the fewest timeslots. By adopting the physical interference mode land without any knowledge on neighborhood, we give a new randomized distributed approximation algorithm for the local broadcasting problem with approximation ratio O (log n) where nis the number of nodes. This distributed approximation algorithm improves the state-of-the-art result in [22] by a logarithmic factor. We consider the communication problem in a multi-hop relay network where the intermediate relay nodes cannot transmit and receive at the same time. The motivation for this assumption comes from the fact that current radios operate in TDD mode when the transmitting and receiving frequencies are the same. We label such a node radio as a cheap radio and the corresponding node of the network as a cheap node. In this paper we derive the capacities of the degraded cheap relay channel and the multi-hop net- work with cheap nodes. The proof of the achievability parts in coding theorems are presented based on the jointly typical sequences, while the proof of the con- verses are derived from the direct application of the upper bounds derived in (7). Receivers with N antennas in single-hop, ad-hoc wireless networks with nodes randomly distributed on an infinite plane with uniform area density are studied. Transmitting nodes have single antennas and transmit simultaneously in the same frequency band with power P that decays with distance via the commonly-used inverse-polynomial model with path-loss- exponent (PLE) greater than 2. This model applies to shared spectrum systems where multiple links share the same frequency band. In the interference-limited regime, the average spectral efficiency of a representative link E[C] (b s Hz link) is found to grow as log(N) and linearly with PLE, and its variance decays as 1 N. The average signal-to-interference-plus-noise-ratio (SINR) on a representative link is found to grow faster than linearly with N. With multiple-input-multiple-output (MIMO) links where transmit nodes have multiple antennas without Channel- State-Information, it is found that E[C] in the network can be improved if nodes transmit using the optimum number of antennas compared to the optimum selfish strategy of transmitting equal-power streams from every antenna. The results are extended to random code-division-multiple-access systems where the optimum spreading factor for a given link length is found. These results are developed as asymptotic expressions using infinite random matrix theory and are validated by Monte-Carlo simulations. This paper investigates two fundamental characteristics of a wireless multi -hop network: its minimum node degree and its k--connectivity. Both topology attributes depend on the spatial distribution of the nodes and their transmission range. Using typical modeling assumptions :--- :a random uniform distribution of the nodes and a simple link model :--- :we derive an analytical expression that enables the determination of the required range r0 that creates, for a given node density ρ, an almost surely k--connected network. Equivalently, if the maximum r0 of the nodes is given, we can find out how many nodes are needed to cover a certain area with a k--connected network. We also investigate these questions by various simulations and thereby verify our analytical expressions. Finally, the impact of mobility is discussed.The results of this paper are of practical value for researchers in this area, e.g., if they set the parameters in a network--level simulation of a mobile ad hoc network or if they design a wireless sensor network. 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. The design of packet radio networks involves a large number of issues which interact in a very complex fashion. Many of these pertain to the RF channel and its use, others pertain to the operational protocols. Clearly, no single model can be formulated which incorporates all the necessary parameters and leads to the optimum solution. The one essential element which complicates matters is that, contrary to point-to-point networks in which each channel is utilized by a single pair of nodes, the radio channel in packet radio networks is a multiaccess broadcast resource: i) in a given locality determined by radio connectivity, the channel is shared by many contending users, hence the need for channel access protocols; ii) radio is a broadcast medium and thus the action taken by a node has an effect on the actions taken by neighboring nodes and their outcome. Despite the complexity of the problem, there has been significant progress worth reporting on. The work accomplished so far has been either the analysis of specific examples of networks or an attempt to create models that would be useful in the design of general networks. The purpose of this paper is to survey the various modeling techniques that have been used for the performance analysis of packet radio networks, and to discuss the assumptions underlying these models, their scope of applicability, and some of the results obtained. In wireless networks, it is well understood what throughput can be achieved by nodes who can hear each other (i.e. nodes within a single cell). The effects of nodes beyond the sensing range (known as hidden nodes) on a sender are complicated and difficult to analyze. Consequently, how to analytically model multi-hop ad-hoc networks, specially networks based on the popular IEEE 802.11 standards remains largely open. In a recent paper, the throughput of a particular wireless network topology (linear network with a given number of hidden nodes) has been derived analytically. In this paper, we unify previous results on single-cell models, and results characterizing different types of hidden node interference and the analysis of C. , (2004), to derive a general solution for throughput given a linear network of arbitrary density and transmission distance between source and destination nodes. An important insight from our model is that there is a certain transmission distance, which is less than the maximum transmission distance, that optimizes throughput in such networks. This result is verified using ns-2 simulation with both single as well as multiple flows. 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. Mobile Communications DepartmentEur´ecom InstituteSophia-Antipolis, Franceraymond.knopp@eurecom.frAbstractIn this work, we are interested in characterizing the performance of decentral-ized multiple-access and retransmission schemes for multi-hop wireless networks.We assume that nodes are randomly distributed on the plane according to a homo-geneous spatial Poisson process. We investigate two transmission strategies: onethat maximizes the distance of a successful transmission for each hop towards theﬁnal destination; and the other that forwards packets to the closest node in range inthe direction of the ﬁnal destination where transmission is successful. This is usefulin the context of multi-hop wireless networks as it is important to assess the trade-oﬀ between spatial density of communication and the range of each transmission.The results of this work also show that coding and retransmissions provide meansof reliable communication coupled with a completely decentralized multiple-accessstrategy. In this paper, we address the following question: given a specific placement of wireless nodes in physical space and a specific traffic workload, what is the maximum throughput that can be supported by the resulting network? Unlike previous work that has focused on computing asymptotic performance bounds under assumptions of homogeneity or randomness in the network topology and or workload, we work with any given network and workload specified as inputs.A key issue impacting performance is wireless interference between neighboring nodes. We model such interference using a conflict graph, and present methods for computing upper and lower bounds on the optimal throughput for the given network and workload. To compute these bounds, we assume that packet transmissions at the individual nodes can be finely controlled and carefully scheduled by an omniscient and omnipotent central entity, which is unrealistic. Nevertheless, using ns-2 simulations, we show that the routes derived from our analysis often yield noticeably better throughput than the default shortest path routes even in the presence of uncoordinated packet transmissions and MAC contention. This suggests that there is opportunity for achieving throughput gains by employing an interference-aware routing protocol. Packet radio networks are modeled as arbitrary graphs by most researchers. We show that an arbitrary graph is an inaccurate model of the radio networks. This is true because there exists a large class of graphs which will not model the radio networks. Radio networks can be modeled accurately by a restricted class of graphs called the planar point graphs. Since the radio networks can accurately be modeled only by a restricted class of graphs, the NP-completeness results for scheduling using an arbitrary graph as the model, do not correctly reflect the complexity of the problem. We study the broadcast scheduling problem using the restricted class as the model. We show that the problem remains NP-complete even in this restricted domain. We give an O(nlogn) algorithm when all the transceivers are located on a line. We restrict our attention to static allocation in general and TDMA in particular. However, it may be noted that the results presented are also valid for other static allocation schemes.