Cross-Layer Design for QoS Support in Multihop Wireless Networks

Due to such features as low cost, ease of deployment, increased coverage, and enhanced capacity, multihop wireless networks such as ad hoc networks, mesh networks, and sensor networks that form the network in a self-organized manner without relying on fixed infrastructure is touted as the new frontier of wireless networking. Providing efficient quality of service (QoS) support is essential for such networks, as they need to deliver real-time services like video, audio, and voice over IP besides the traditional data service. Various solutions have been proposed to provide soft QoS over multihop wireless networks from different layers in the network protocol stack. However, the layered concept was primarily created for wired networks, and multihop wireless networks oppose strict layered design because of their dynamic nature, infrastructureless architecture, and time-varying unstable links and topology. The concept of cross-layer design is based on architecture where different layers can exchange information in order to improve the overall network performance. Promising results achieved by cross-layer optimizations initiated significant research activity in this area. This paper aims to review the present study on the cross-layer paradigm for QoS support in multihop wireless networks. Several examples of evolutionary and revolutionary cross-layer approaches are presented in detail. Realizing the new trends for wireless networking, such as cooperative communication and networking, opportunistic transmission, real system performance evaluation, etc., several open issues related to cross-layer design for QoS support over multihop wireless networks are also discussed in the paper.     

Low-Power Wake-Up Radio for Wireless Sensor Networks

Power consumption is a critical issue in many wireless sensor network scenarios where network life expectancy is measured in months or years. Communication protocols typically rely on synchronous operation and duty-cycle mechanisms to reduce the power usage at the cost of decreased network responsiveness and increased communication latency. A low-power radio-triggered device can be used to continuously monitor the channel and activate the node for incoming communications, allowing purely asynchronous operations. To be effective, the power consumption of this wake-up device must be on the order of tens of microwatts since this device is always active. This paper presents our first attempt at designing such a low-power receiver. Very few realizations of wake-up devices are reported in the literature and none presents power dissipation below 40 μW. Our design implements a complete wake-up device and initial results indicate an average power consumption below 20 μW, which is more than 2 times lower than other reported devices.     

Asymptotically Optimal Energy-Aware Routing for Multihop Wireless Networks With Renewable Energy Sources

In this paper, we develop a model to characterize the performance of multihop radio networks in the presence of energy constraints and design routing algorithms to optimally utilize the available energy. The energy model allows us to consider different types of energy sources in heterogeneous environments. The proposed algorithm is shown to achieve a competitive ratio (i.e., the ratio of the performance of any offline algorithm that has knowledge of all past and future packet arrivals to the performance of our online algorithm) that is asymptotically optimal with respect to the number of nodes in the network. The algorithm assumes no statistical information on packet arrivals and can easily be incorporated into existing routing schemes (e.g., proactive or on-demand methodologies) in a distributed fashion. Simulation results confirm that the algorithm performs very well in terms of maximizing the throughput of an energy-constrained network. Further, a new threshold-based scheme is proposed to reduce the routing overhead while incurring only minimum performance degradation.     

Tandem Queue Models with Applications to QoS Routing in Multihop Wireless Networks

We consider the problem of quality of service (QoS) routing in multi-hop wireless networks where data are transmitted from a source node to a destination node via multiple hops. The routing component of a QoS-routing algorithm essentially involves the link and path metric calculation which depends on many factors such as the physical and link layer designs of the underlying wireless network, transmission errors due to channel fading and interference, etc. The task of link metric calculation basically requires us to solve a tandem queueing problem which is the focus of this paper. We present a unified tandem queue framework which is applicable for many different physical layer designs. We present both exact and approximated decomposition approaches. Using the queueing framework, we can derive different performance measures, namely, end-to-end loss rate, end-to-end average delay, and end-to-end delay distribution. The proposed decomposition approach is validated and some interesting insights into the system performance are highlighted. We then present how to use the decomposition queueing approach to calculate the link metric and incorporate this into the route discovery process of the QoS routing algorithm. The extension of the queueing and QoS routing framework to wireless networks with class-based queueing for QoS differentiation is also presented.     

Controller Placement in Software-Defined Multihop Wireless Networks: Optimal Solution and GA-based Approximation

In a multi-controller software-defined networking (SDN) architecture, solving the controller placement problem (CPP) has a direct effect on the generated control overhead in the network. We aim to minimize the control overhead exchanged in the network, especially in software-defined multihop wireless networks (SDMWN), i.e., a network that is built on multihop communications using a wireless medium. We solve this problem both optimally, using a nonlinear optimization model, and via a heuristic algorithm. The proposed heuristic approach is based on the genetic algorithm (GA). The objective of both the proposed optimization problem and the proposed GA algorithm is to find a given number of controllers, controller placements and assignments of controllers to devices while minimizing the generated control overhead in the network. Our results show the impact of different metrics, including the number of controllers, the arrival rate of new flows and the capacity limit of wireless links on the control overhead and the average number of controller-device and inter-controller hops. In addition, our results demonstrate that the GA-based heuristic approach can derive the same optimal solution for a small network with much less computational overhead, and can solve larger networks in a short period of time, making it feasible for non-trivial network sizes.

     

Energy-Efficient SINR-Based Routing for Multihop Wireless Networks

In this paper, we develop an energy-efficient routing scheme that takes into account the interference created by existing flows in the network. The routing scheme chooses a route such that the network expends the minimum energy satisfying with the minimum constraints of flows. Unlike previous works, we explicitly study the impact of routing a new flow on the energy consumption of the network. Under certain assumptions on how links are scheduled, we can show that our proposed algorithm is asymptotically (in time) optimal in terms of minimizing the average energy consumption. We also develop a distributed version of the algorithm. Our algorithm automatically detours around a congested area in the network, which helps mitigate network congestion and improve overall network performance. Using simulations, we show that the routes chosen by our algorithm (centralized and distributed) are more energy efficient than the state of the art.     

Efficient and Resilient Backbones for Multihop Wireless Networks

We consider the problem of finding "backbones" in wireless networks. The backbone provides end-to-end connectivity, allowing non-backbone nodes to save energy since they do not route or forward non-local data. Ideally, such a backbone would be small, consist primarily of high capacity nodes, and remain connected even when nodes move or fail. Unfortunately, it is often infeasible to construct a backbone that has all of these properties, e.g., a small optimal backbone is often too sparse to handle node failures or high mobility. We present a parameterized backbone construction algorithm that permits explicit tradeoffs between backbone size, resilience to node movement and failure, energy consumption, and path lengths. We prove that our scheme can construct essentially best possible backbones (with respect to energy consumption and backbone size) when the network is relatively static. We generalize our scheme to build more robust structures better suited to high-mobility scenarios. We present a distributed protocol based upon our algorithm and show that this protocol builds and maintains a connected backbone in dynamic networks. Finally, we present detailed packet-level simulations to evaluate and compare our scheme against existing energy-saving techniques. Depending on the network environment, our scheme increases network lifetimes by 20—220% without adversely affecting network performance.     

Cross-Layer Design of Wireless Multihop Backhaul Networks With Multiantenna Beamforming

A cross-layer design approach is considered for joint routing and resource allocation for the physical (PHY) and the medium access control (MAC) layers in multihop wireless backhaul networks. The access points (APs) are assumed to be equipped with multiple antennas capable of both transmit and receive beamforming. A nonlinear optimization problem is formulated, which maximizes the fair throughput of the APs in the network under the routing and the PHY/MAC constraints. Dual decomposition is employed to decouple the original problem into smaller subproblems in different layers, which are coordinated by the dual prices. The network layer subproblem can be solved in a distributed manner and the PHY layer subproblem in a semidistributed manner. To solve the PHY layer subproblem, an iterative minimum mean square error (IMMSE) algorithm is used with the target link signal-to-interference-and-noise-ratio (SINR) set dynamically based on the price generated from the upper layers. A scheduling heuristic is also developed, which improves the choice of the transmission sets over time. Simulation results illustrate the efficacy of the proposed cross-layer design.     

Throughput Behavior in Multihop Multiantenna Wireless Networks

Multiantenna or MIMO systems offer great potential for increasing the throughput of multihop wireless networks via spatial reuse and/or spatial multiplexing. This paper characterizes and analyzes the maximum achievable throughput in multihop, MIMO-equipped, wireless networks under three MIMO protocols, spatial reuse only (SRP), spatial multiplexing only (SMP), and spatial reuse and multiplexing (SRMP), each of which enhances the throughput, but via a different way of exploiting MIMO's capabilities. We show via extensive simulation that as the number of antennas increases, the maximum achievable throughput first rises and then flattens out asymptotically under SRP, while it increases "almost" linearly under SMP or SRMP. We also evaluate the effects of several network parameters on this achievable throughput, and show how throughput behaves under these effects.     

Multiradio Channel Allocation in Multihop Wireless Networks

Channel allocation was extensively investigated in the framework of cellular networks, but it was rarely studied in the wireless ad hoc networks, especially in the multihop networks. In this paper, we study the competitive multiradio multichannel allocation problem in multihop wireless networks in detail. We first analyze that the static noncooperative game and Nash equilibrium (NE) channel allocation scheme are not suitable for the multihop wireless networks. Thus, we model the channel allocation problem as a hybrid game involving both cooperative game and noncooperative game. Within a communication session, it is cooperative; and among sessions, it is noncooperative. We propose the min-max coalition-proof Nash equilibrium (MMCPNE) channel allocation scheme in the game, which aims to maximize the achieved data rates of communication sessions. We analyze the existence of MMCPNE and prove the necessary conditions for MMCPNE. Furthermore, we propose several algorithms that enable the selfish players to converge to MMCPNE. Simulation results show that MMCPNE outperforms NE and coalition-proof Nash equilibrium (CPNE) schemes in terms of the achieved data rates of multihop sessions and the throughput of whole networks due to cooperation gain.     

Verifying Delivered QoS in Multihop Wireless Networks

The question that we consider here is the following: "How can a source verify the quality of service (QoS) experienced by its packet(s) at each hop to the destination in a multihop wireless network?" For example, if Bob needs to forward packets within some maximum delay of delta _B , how can the source verify that Bob in fact forwarded the packets within this bound? Answering this question will enable innovations in multihop wireless network deployments, where nodes may receive payment not only for forwarding packets but also for meeting some QoS guarantees. In this paper, we present protocols that enable verification of delivered QoS for individual packets, as well as verification of statistical QoS for groups of packets. The protocols are proven to be cheat proof. We also provide expressions for the minimum verifiable delay.     

Profit-Based Routing for Multihop Coverage Extension in Wireless Networks

In future wireless systems, the coverage of a base station will decrease due to the characteristics of the channel at high-frequency bands. To expand the service coverage, a hybrid network that combines an ad hoc network with a cellular (or wireless LAN) network, appears to have great potential. In such systems, some mobile users outside the service area can access the network with the aid of other intermediate mobiles. However, this method incurs energy consumption in routing users, which could be a serious obstacle for wide-spread deployment of multihop wireless networks. Therefore we consider a revenue-cost model and propose a profit-based routing strategy that encourages routing users to actively participate in the relaying service because they are compensated for their energy consumption cost. Our strategy enables each mobile node to find an appropriate multihop path to a base station (or access point) that satisfies the interests of the service provider and the users. Numerical results show that our model successfully expands the network coverage area while ensuring the profit of each system involved.     

Time-Driven Access and Forwarding for Industrial Wireless Multihop Networks

The deployment of wireless technologies in industrial networks is very promising mainly due to their inherent flexibility. However, current wireless solutions lack the capability to provide the deterministic, low delay service required by many industrial applications. Moreover, the high level of interference generated by industrial equipment limits the coverage that ensures acceptable performance. Multihop solutions, when combining frame forwarding with higher node density, have the potential to provide the needed coverage while keeping radio communication range short. However, in multihop solutions, the medium access time at each of the nodes traversed additively contributes to the end-to-end delay and the forwarding delay (i.e., the time required for packets to be processed, switched, and queued) at each node is to be added as well. This paper describes time-driven access and forwarding, a solution for guaranteeing deterministic delay, at both the access and forwarding level, in wireless multihop networks, analyzes its properties, and assesses its performance in industrial scenarios.     

Energy Optimization in Multihop Wireless Embedded and Sensor Networks

This paper provides an analytical model for the study of energy consumption in multihop wireless embedded and sensor networks where nodes are extremely power constrained. Low-power optimization techniques developed for conventional ad hoc networks are not sufficient as they do not properly address particular features of embedded and sensor networks. It is not enough to reduce overall energy consumption, it is also important to maximize the lifetime of the entire network, that is, maintain full network connectivity for as long as possible. This paper considers different multihop scenarios to compute the energy per bit, efficiency and energy consumed by individual nodes and the network as a whole. The analysis uses a detailed model for the energy consumed by the radio at each node. Multihop topologies with equidistant and optimal node spacing are studied. Numerical computations illustrate the effects of packet routing, and explore the effects of coding and medium access control. These results show that always using a simple multihop message relay strategy is not always the best procedure.     

A Smart TCP Acknowledgment Approach for Multihop Wireless Networks

Reliable data transfer is one of the most difficult tasks to be accomplished in multihop wireless networks. Traditional transport protocols like TCP face severe performance degradation over multihop networks given the noisy nature of wireless media as well as unstable connectivity conditions in place. The success of TCP in wired networks motivates its extension to wireless networks. A crucial challenge faced by TCP over these networks is how to operate smoothly with the 802.11 wireless MAC protocol which also implements a retransmission mechanism at link level in addition to short RTS/CTS control frames for avoiding collisions. These features render TCP acknowledgments (ACK) transmission quite costly. Data and ACK packets cause similar medium access overheads despite the much smaller size of the ACKs. In this paper, we further evaluate our dynamic adaptive strategy for reducing ACK-induced overhead and consequent collisions. Our approach resembles the sender side's congestion control. The receiver is self-adaptive by delaying more ACKs under nonconstrained channels and less otherwise. This improves not only throughput but also power consumption. Simulation evaluations exhibit significant improvement in several scenarios     

一种多跳无线网扩频码分配算法

在多跳分组无线网中使用码分多址(CDMA)技术可以明显地降低隐终端问题对网络造成的影响.码分配是多跳无线网中使用CDMA的基本问题.码分配的目的在于提高扩频码的空间重用、降低分组冲突以及反映网络的动态变化.本文提出了一种多跳无线网扩频码分配算法,证明了其正确性并与其它算法比较了复杂度.与以往的算法追求降低码的数目不同,本算法是假设扩频码的数目有一定的冗余,寻求算法的方便、快捷和低通信开销.     

Network Lifetime Maximization for Estimation in Multihop Wireless Sensor Networks

We consider the distributed estimation by a network consisting of a fusion center and a set of sensor nodes, where the goal is to maximize the network lifetime, defined as the estimation task cycles accomplished before the network becomes nonfunctional. In energy-limited wireless sensor networks, both local quantization and multihop transmission are essential to save transmission energy and thus prolong the network lifetime. The network lifetime optimization problem includes three components: i) optimizing source coding at each sensor node, ii) optimizing source throughput of each sensor node, and iii) optimizing multihop routing path. Fortunately, source coding optimization can be decoupled from source throughput and multihop routing path optimization, and is solved by introducing a concept of equivalent 1-bit MSE function. Based on the optimal source coding, the source throughput and multihop routing path optimization is formulated as a linear programming (LP) problem, which suggests a new notion of character-based routing. The proposed algorithm is optimal and the simulation results show that a significant gain is achieved by the proposed algorithm compared with heuristic methods.     

A Simulation-Based Method for Predicting Connectivity in Wireless Multihop Networks

This study presents an approach to the problem of predicting k-connectivity in wireless multihop networks. Assuming the network consists of randomly placed nodes with a common transmission range, the threshold range for k-connectivity is a random variable. Knowing the distribution of this random variable under the circumstances of interest allows one to determine how the number of nodes, the transmission range, and the network area are related so that a random network realization is k-connected with a given probability.     

A Cross-Layer Optimization Framework for Multihop Multicast in Wireless Mesh Networks

The optimal and distributed provisioning of high throughput in mesh networks is known as a fundamental but hard problem. The situation is exacerbated in a wireless setting due to the interference among local wireless transmissions. In this paper, we propose a cross-layer optimization framework for throughput maximization in wireless mesh networks, in which the data routing problem and the wireless medium contention problem are jointly optimized for multihop multicast. We show that the throughput maximization problem can be decomposed into two subproblems: a data routing subproblem at the network layer, and a power control subproblem at the physical layer with a set of Lagrangian dual variables coordinating interlayer coupling. Various effective solutions are discussed for each subproblem. We emphasize the network coding technique for multicast routing and a game theoretic method for interference management, for which efficient and distributed solutions are derived and illustrated. Finally, we show that the proposed framework can be extended to take into account physical-layer wireless multicast in mesh networks