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
1586023924
Exponential growth in the number of wireless devices that operate in the limited unlicensed frequency spectrum necessitates the next generation of radio devices to be reconfigurable and sensitive to changes in network conditions and spectrum availability. Most modern wireless devices offer increased software programmability and control over radio communication parameters. Since a large portion of the MAC protocol is implemented in software, with the firmware providing a set of functional primitives, it is possible to design and implement alternate MAC protocols in real testbeds equipped with commodity 802.11 devices. This paper describes FreeMAC, a reconfigurable MAC protocol development framework that enables the design and implementation of a general class of multi-channel MAC protocols on a typical Linux system. FreeMAC provides support for frequent channel switching and fine control over the timing of packet transmissions. We also propose a mechanism to reduce the latency in the scheduling of periodic operations of a software MAC protocol that have strict timing requirements. Results from our six node testbed indicate that using our approach, the scheduling latency of slot transitions in a TDMA-style MAC can be improved by up to an order of magnitude, with minimal overhead. FreeMAC also exports a number of radio configuration parameters as API functions to enable cross layer interactions among wireless networking protocols. As a proof of concept, we implement a simple multi-channel TDMA MAC on our testbed to demonstrate the utility of FreeMAC as a development framework. 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. This paper describes Extremely Opportunistic Routing (ExOR), a new unicast routing technique for multi-hop wireless networks. ExOR forwards each packet through a sequence of nodes, deferring the choice of each node in the sequence until after the previous node has transmitted the packet on its radio. ExOR then determines which node, of all the nodes that successfully received that transmission, is the node closest to the destination. That closest node transmits the packet. The result is that each hop moves the packet farther (or average) than the hops of the best possible pre-determined route.The ExOR design addresses the challenge of choosing a forwarding node after transmission using a distributed algorithm. First, when a node transmits a packet, it includes in the packet a simple schedule describing the priority order in which the potential receivers should forward the packet. The node computes the schedule based on shared measurements of inter-node delivery rates. ExOR then uses a distributed slotted MAC protocol for acknowledgements to ensure that the receivers agree who the highest priority receiver was.The efficacy of ExOR depends mainly on the rate at which the reception probability falls off with distance. Simulations based on measured radio characteristics [6] suggest that ExOR reduces the total number of transmissions by nearly a factor of two over the best possible pre-determined route. 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. 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 the expected transmission count metric (ETX), which finds high-throughput paths on multi-hop wireless networks. ETX minimizes the expected total number of packet transmissions (including retransmissions) required to successfully deliver a packet to the ultimate destination. The ETX metric incorporates the effects of link loss ratios, asymmetry in the loss ratios between the two directions of each link, and interference among the successive links of a path. In contrast, the minimum hop-count metric chooses arbitrarily among the different paths of the same minimum length, regardless of the often large differences in throughput among those paths, and ignoring the possibility that a longer path might offer higher throughput.This paper describes the design and implementation of ETX as a metric for the DSDV and DSR routing protocols, as well as modifications to DSDV and DSR which allow them to use ETX. Measurements taken from a 29-node 802.11b test-bed demonstrate the poor performance of minimum hop-count, illustrate the causes of that poor performance, and confirm that ETX improves performance. For long paths the throughput improvement is often a factor of two or more, suggesting that ETX will become more useful as networks grow larger and paths become longer. Physical layer (PHY) network coding (PLNC), which performs the operation of network coding at physical layer, is an attractive means to improve throughput of wireless multi-hop networks. The PLNC requires multiple nodes to transmit their packets with accurate synchronization at symbol-level. Therefore, in many works of literature, centralized scheduling with perfect synchronization has been assumed to be employed on top of PLNC. Another common assumption is perfect channel state information (CSI) availability for end-nodes to decode their desired packets. However, these assumptions are challenged when we attempt to apply PLNC to large-scale and distributed networks. Therefore, in this paper, we propose a distributed medium access control (MAC) protocol for wireless multi-hop networks employing PLNC. The proposed MAC protocol is a random access protocol, which solves the PHY-specific problems, such as synchronization and CSI, jointly with distributed scheduling at MAC layer. We evaluate throughput of PLNC employing the proposed MAC protocol by computer simulation, and compare it with that of conventional relaying. With numerical results, we investigate the effectiveness of PLNC in distributed wireless multi-hop networks. The time-complexity of deterministic and randomized protocols for achieving broadcast (distributing a message from a source to all other nodes) in arbitrary multi-hop radio networks is investigated. In many such networks, communication takes place in synchronous time-slots. A processor receives a message at a certain time-slot if exactly one of its neighbors transmits at that time-slot. We assume no collision-detection mechanism; i.e., it is not always possible to distinguish the case where no neighbor transmits from the case where several neighbors transmit simultaneously. We present a randomized protocol that achieves broadcast in time which is optimal up to a logarithmic factor. In particular, with probability 1 --E, the protocol achieves broadcast within O((D + log n s) ‘log n) time-slots, where n is the number of processors in the network and D its diameter. On the other hand, we prove a linear lower bound on the deterministic time-complexity of broadcast in this model. Namely, we show that any deterministic broadcast protocol requires 8(n) time-slots, even if the network has diameter 3, and n is known to all processors. These two results demonstrate an exponential gap in complexity between randomization and determinism. Spatial reuse TDMA is an access scheme for multi-hop radio networks. The idea is to increase capacity by letting several radio terminals use the same time slot when possible. A time slot can be shared when the radio units are geographically separated such that small interference is obtained. STDMA schedules can assign transmission rights to nodes or alternatively assign transmission rights to links, i.e. transmitter receiver pairs. Here we compare these two methods and determine which one is preferable. We show that only the connectivity of the network and the input traffic load of the network is needed in order to determine whether node or link assignment is preferable. 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. Since underwater acoustic (UWA) networks have the nature of long propagation delay, low bit rates and error-prone acoustic communication, protocols designed for underwater acoustic networks are significantly different from that of terrestrial radio networks. Limited by these nature of UWA channels, conventional medium access control (MAC) protocols of radio packet network ether have low efficiency or are not able to apply to underwater acoustic networks. It is necessary to develop an efficient MAC protocol for underwater acoustic networks. In this paper, a collision-free MAC protocol for UWA networks called Ordered Carrier Sense Multiple Access (Ordered CSMA) is proposed and analyzed. Ordered CSMA combines the concepts of round-robin scheduling and CSMA. In Ordered CSMA, each station transmits data frame in a fixed order. More specifically, each station transmits immediately after the data frame transmission of last station in the order, instead of waiting for a period of maximum propagation delay. To achieve this, each station is constantly sensing the carrier and listens to all received frames. Due to the characteristics of collision free and high channel utilization, Ordered CSMA shows a great MAC efficiency improvement in our simulations, compared to previous works. Two tasks of communication in a multi-hop synchronous radio network are considered: point-to-point communication and broadcast (sending a message to all nodes of a network). Efficient protocols for both problems are presented. Even though the protocols are probabilistic, it is shown how to acknowledge messages deterministically. Let n, D, and ∆ be the number of nodes, the diameter and the maximum degree of our network, respectively. Both protocols require a setup phase in which a BFS tree is constructed. This phase takes O ((n + Dlogn)log∆) time. After the setup, k point-to-point transmissions require O ((k +D)log∆) time on the average. Therefore the network allows a new transmission every O (log∆) time slots. Also, k broadcasts require an average of O ((k +D)log∆logn) time. Hence the average throughput of the network is a broadcast every O(log∆logn) time slots. Both protocols pipeline the messages along the BFS tree. They are always successful on the graph spanned by the BFS tree. Their probabilistic behavior refers only to the running time. Using the above protocols the ranking problem is solved in O (nlognlog∆) time. The performance analysis of both protocols constitutes a new application of queueing theory. A selection problem is among the basic communication primitives in networks. In this problem at most k participating stations have to broadcast successfully their messages. This problem is especially important in packet radio networks, where simultaneous transmissions of many neighbors result in interference among delivered messages. This work focuses on a single-hop radio networks with n-stations, also called a multiple access channel, and considers both static and dynamic versions of the selection problem. We construct a family of efficient oblivious deterministic protocols based on selectors, one of them with selection time cO(klog(n k)), and the second explicit construction with selection time cO(k polylog n). The first construction matches the lower bound Ω(klog(n k)) on deterministic oblivious selection, while the second one is the first known explicit construction better than Θ(k2). In the dynamic case we introduce the model of dynamic requests, called k-streams, which generalizes the static model and the dynamic requests with at most k participants. We prove that each oblivious deterministic protocol has latency Ω(k2 log k), and on the other hand we prove the existence of the oblivious deterministic protocol with latency cO(k2log n). In view of the existence of the randomized oblivious protocol with expected latency cO(klog(n k)), this shows that randomization is substantially better than determinism for dynamic setting. Selection problem can be applied to implement other communication primitives --- we demonstrate it in the example of broadcast problem in multi-hop ad-hoc radio networks. In particular, we design an adaptive deterministic protocol broadcasting in time cO(nlog D) in every D-hop radio network of n-stations. Providing packet-level quality of service (QoS) is critical to support both rate-sensitive and delay-sensitive applications in bandwidth-constrained, shared-channel, multihop wireless networks. Packet scheduling has been a very popular paradigm to ensure minimum throughput and bounded delay access for packet flows. This work describes a packet scheduling approach to QoS provisioning in multihop wireless networks. Besides minimum throughput and delay bounds for each flow, our scheduling disciplines seek to achieve fair and maximum allocation of the shared wireless channel bandwidth. However, these two criteria can potentially be in conflict in a generictopology multihop wireless network where a single logical channel is shared among multiple contending flows and spatial reuse of the channel bandwidth is possible. In this paper, we propose a new scheduling model that addresses this conflict. The main results of this paper are the following: (a) a two-tier service model that provides a minimum "fair" allocation of the channel bandwidth for each packet flow and additionally maximizes spatial reuse of bandwidth, (b) an ideal centralized packet scheduling algorithm that realizes the above service model, and (c) a practical distributed backoff-based channel contention mechanism that approximates the ideal service within the framework of the CSMA CA protocol. 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. Underwater acoustic communication networks (UWANs) have recently attracted much attention in the research community. Two properties that set UWANs apart from most radio-frequency wireless communication networks are the long propagation delay and the possible sparsity of the network topology. This in turn offers opportunities to optimize throughput through time and spatial reuse. In this paper, we propose a new adaptive coding method to realize the former. We consider time-slotted scheduling protocols, which are a popular solution for contention-free and interference-free access in small-scale UWANs, and exploit the surplus guard time that occurs for individual links for improving transmission reliability. In particular, using link distances as side information, transmitters utilize the available portion of the time slot to adapt their code rate and increase reliability. Since increased reliability trades off with energy consumption per transmission, we optimize the code rate for best tradeoff, considering both single and multiple packet transmission using the incremental redundancy hybrid automatic repeat request (IR–HARQ) protocol. For practical implementation of this adaptive coding scheme, we consider punctured and rateless codes. Simulation results demonstrate the gains achieved by our coding scheme over fixed-rate error-correction codes in terms of both throughput and consumption of transmitted energy per successfully delivered packet. We also report results from a sea trial conducted at the Haifa harbor, which corroborate the simulations. Considered is a mobile ad hoc network consisting of three types of nodes (source, destination and relay nodes) and using the two-hop relay routing protocol. Packets at relay nodes are assumed to have a limited lifetime in the network. All nodes are moving inside a bounded region according to some random mobility model. Both closed-form expressions, and asymptotic results when the number of nodes is large, are provided for the packet delivery delay and the energy needed to transmit a packet from the source to its destination. We also introduce and evaluate a variant of the two-hop relay protocol that limits the number of generated copies in the network. Our model is validated through simulations for two mobility models (random waypoint and random direction mobility models), numerical results for the two-hop relay protocols are reported, and the performance of the two-hop routing and of the epidemic routing protocols are compared. We study a slotted version of the Aloha Medium Access (MAC) protocol in a Mobile Ad-hoc Network (MANET). Our model features transmitters randomly located in the Euclidean plane, according to a Poisson point process and a set of receivers representing the next-hop from every transmitter. We concentrate on the so-called outage scenario, where a successful transmission requires a Signal-to-Interference-and-Noise (SINR) larger than some threshold. We analyze the local delays in such a network, namely the number of times slots required for nodes to transmit a packet to their prescribed next-hop receivers. The analysis depends very much on the receiver scenario and on the variability of the fading. In most cases, each node has finite-mean geometric random delay and thus a positive next hop throughput. However, the spatial (or large population) averaging of these individual finite mean-delays leads to infinite values in several practical cases, including the Rayleigh fading and positive thermal noise case. In some cases it exhibits an interesting phase transition phenomenon where the spatial average is finite when certain model parameters (receiver distance, thermal noise, Aloha medium access probability) are below a threshold and infinite above. To the best of our knowledge, this phenomenon, which we propose to call the wireless contention phase transition, has not been discussed in the literature. We comment on the relationships between the above facts and the heavy tails found in the so-called "RESTART" algorithm. We argue that the spatial average of the mean local delays is infinite primarily because of the outage logic, where one transmits full packets at time slots when the receiver is covered at the required SINR and where one wastes all the other time slots. This results in the "RESTART" mechanism, which in turn explains why we have infinite spatial average. Adaptive coding offers another nice way of breaking the outage RESTART logic. We show examples where the average delays are finite in the adaptive coding case, whereas they are infinite in the outage case. Scheduling is a critical and challenging resource allocation mechanism for multihop wireless networks. It is well known that scheduling schemes that favor links with larger queue length can achieve high throughput performance. However, these queue-length-based schemes could potentially suffer from large (even infinite) packet delays due to the well-known last packet problem, whereby packets belonging to some flows may be excessively delayed due to lack of subsequent packet arrivals. Delay-based schemes have the potential to resolve this last packet problem by scheduling the link based on the delay the packet has encountered. However, characterizing throughput optimality of these delay-based schemes has largely been an open problem in multihop wireless networks (except in limited cases where the traffic is single-hop). In this paper, we investigate delay-based scheduling schemes for multihop traffic scenarios with fixed routes. We develop a scheduling scheme based on a new delay metric and show that the proposed scheme achieves optimal throughput performance. Furthermore, we conduct simulations to support our analytical results and show that the delay-based scheduler successfully removes excessive packet delays, while it achieves the same throughput region as the queue-length-based scheme. Recent trends witness the shift of the 3GPP Long Term Evolution - Advanced (LTE-A) radio access network (RAN) architecture from a traditional macro-cellular layout towards smaller base stations moving closer to end users. The evolved LTE-A RAN offers rich environment for multi-point and multi-hop cooperation and coordination resulting in increased capacity and more predictable channel conditions between heterogeneous base stations and end users. While these opportunities are recently well investigated at the physical layer through various cooperative multi-point (CoMP) schemes, upper layer protocols preserve the design proposed for macro-cellular single-hop data delivery. In this paper, we address this issue by proposing and investigating in detail a cooperative RAN-wide MAC layer protocol based on random network coding (RNC) that is designed specifically for reliable and flexible data delivery over the evolved LTE-A RAN. The proposed RNC-based MAC protocol (MAC-RNC) is evaluated and compared with the existing HARQ-based (MAC-HARQ) protocol in various LTE-A RAN layouts using a customized packet-based link-level simulator based on Finite-State Markov Chain (FSMC) channel models. Our results show that the MAC-RNC protocol introduces simplicity and flexibility required for future LTE-A RANs, while preserving or improving the performance of the MAC-HARQ protocol in traditional single-point single-hop macro-cellular scenarios.