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.     

On Throughput Efficiency of Geographic Opportunistic Routing in Multihop Wireless Networks

Geographic opportunistic routing (GOR) has shown throughput efficiency in coping with unreliable transmissions in multihop wireless networks. The basic idea behind opportunistic routing is to take advantage of the broadcast nature and spacial diversity of the wireless medium by involving multiple neighbors of the sender into the local forwarding, thus improve transmission reliability. The existing GOR schemes typically involve as many as available next-hop neighbors into the local forwarding, and give the nodes closer to the destination higher relay priorities. In this paper, we show that it is not always the optimal way to achieve the best throughput. We introduce a framework to analyze the one-hop throughput of GOR, provide a deeper insight into the trade-off between the benefit (packet advancement and transmission reliability) and cost (medium time delay) associated with the node collaboration, and propose a local metric named expected one-hop throughput (EOT) to balance the benefit and cost. We also identify an upper bound of EOT and its concavity, which indicates that even if the candidate coordination delay were negligible, the throughput gain would become marginal when the number of forwarding candidates increases. Based on the EOT, we also propose a local candidate selection and prioritization algorithm. Simulation results validate our analysis and show that the EOT metric leads to both better one-hop and path throughput than the corresponding pure GOR and geographic routing.     

Analytical Expression of Maximum Throughput for Long-Frame Communications in One-way String Wireless Multihop Networks

It is important to obtain analytical expressions of the maximum throughput in IEEE 802.11 Distributed Coordination Function multi-hop networks. In the previous works, the analytical expressions of the maximum throughput for one-way string multi-hop networks taking into account the signal capture effect were obtained. In other researches, the analytical expressions of the maximum throughput for one-way string multi-hop networks were also obtained, which are, however, valid only for short-frame communications. There is no analytical expression for maximum throughput, which is valid for long-frame communications. This paper presents an analytical expression of the maximum throughput for long-frame communications. For the long-frame-communication analysis, we make different assumptions from those in the previous-analyses. In the short-frame-communication analyses, it is assumed that all nodes always have frames. In the long-frame-communication analysis, however, it should be assumed that every equal to or more than three nodes in a string-topology network have frames. The comprehension of this behavior is the most important progression in this paper. The assumptions and the analytical expression are validated by the simulation results.     

Throughput Analysis in Multihop CSMA Packet Radio Networks

In this paper, we use a Markov model to develop a product form solution to efficiently analyze the throughput of arbitrary topology multihop packet radio networks that employ a carrier sensing multiple access (CSMA) protocol with perfect capture. We consider both exponential and nonexponential packet length distributions. Our method preserves the dependence between nodes, characteristic of CSMA, and determines the joint probability that nodes are transmitting. The product form analysis provides the basis for an automated algorithm that determines the maximum throughput in networks of size up to 100 radio nodes. Numerical examples for several networks are presented. This model has led to many theoretical and practical extensions. These include determination of conditions for product form analysis to hold, extension to other access protocols, and consideration of acknowledgments.     

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.     

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.     

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.     

On-Demand Multicast Routing Protocol in Multihop Wireless Mobile Networks

An ad hoc network is a dynamically reconfigurable wireless network with no fixed infrastructure or central administration. Each host is mobile and must act as a router. Routing and multicasting protocols in ad hoc networks are faced with the challenge of delivering data to destinations through multihop routes in the presence of node movements and topology changes. This paper presents the On-Demand Multicast Routing Protocol (ODMRP) for wireless mobile ad hoc networks. ODMRP is a mesh-based, rather than a conventional tree-based, multicast scheme and uses a forwarding group concept; only a subset of nodes forwards the multicast packets via scoped flooding. It applies on-demand procedures to dynamically build routes and maintain multicast group membership. ODMRP is well suited for ad hoc wireless networks with mobile hosts where bandwidth is limited, topology changes frequently, and power is constrained. We evaluate ODMRP performance with other multicast protocols proposed for ad hoc networks via extensive and detailed simulation.     

Stochastic Traffic Engineering in Multihop Cognitive Wireless Mesh Networks

In this work, the stochastic traffic engineering problem in multihop cognitive wireless mesh networks is addressed. The challenges induced by the random behaviors of the primary users are investigated in a stochastic network utility maximization framework. For the convex stochastic traffic engineering problem, we propose a fully distributed algorithmic solution which provably converges to the global optimum with probability one. We next extend our framework to the cognitive wireless mesh networks with nonconvex utility functions, where a decentralized algorithmic solution, based on learning automata techniques, is proposed. We show that the decentralized solution converges to the global optimum solution asymptotically.     

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.     

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.     

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.     

Downlink Throughput Maximization in CDMA Wireless Networks

We investigate optimum rate assignment scheme maximizing network throughput on the downlink of a multirate CDMA wireless network. Systems employing orthogonal variable spreading factor (OVSF) codes as well as systems employing multiple codes have been studied. Our objective is to maximize the network throughput under constraints on total transmit power, total bandwidth and individual QoS requirements specified in terms of minimum rates. First, users are ordered based on their transmit energy per bit requirements to achieve the target received energy per bit to interference power spectral density ratio at the receivers. Based on the initial ordering, we prove that for systems employing multiple codes, greedy rate assignment yields maximum network throughput. For systems employing variable spreading codes, we show that greedy rate assignment is optimal if the minimum rate requirement of a user is larger than or equal to the minimum rate requirement of any other user with a larger transmit energy per bit requirement. Simulation results verify the superiority of the greedy algorithm under various system and channel assumptions     

Cross-Layer Collaborative In-Network Processing in Multihop Wireless Sensor Networks

Emerging wireless sensor network (WSN) applications demand considerable computation capacity for in-network processing. To achieve the required processing capacity, cross-layer collaborative in-network processing among sensors emerges as a promising solution: sensors do not only process information at the application layer, but also synchronize their communication activities to exchange partially processed data for parallel processing. However, scheduling computation and communication events is a challenging problem in WSNs due to limited resource availability and shared communication medium. In this work, an application-independent task mapping and scheduling solution in multihop homogeneous WSNs, multihop task mapping and scheduling (MTMS), is presented that provides real-time guarantees. Using our proposed application model, the multihop channel model, and the communication scheduling algorithm, computation tasks and associated communication events are scheduled simultaneously. The dynamic voltage scaling (DVS) algorithm is presented to further optimize energy consumption. Simulation results show significant performance improvements compared with existing mechanisms in terms of minimizing energy consumption subject to delay constraints     

A Cross-Layer Approach for Concurrent Delay and Throughput Assurances in Multihop Wireless Hotspots

Next generation Wireless Local Area Networks (WLAN’s) are likely to require multihop wireless connections between mobile nodes and Internet gateways to achieve high data rates from larger distances. The paper addresses the challenges in concurrently providing a wide range of end-to-end throughput and delay assurances in such mobile multihop WLAN hotspots. The proposed solution is based on the Neighborhood Proportional Delay Differentiation (NPDD) service model. With NPDD, Transmission Control Protocol (TCP) based applications achieve their desired throughputs using a dynamic class selection mechanism. This approach integrates well with the NPDD-based end-to-end delay assurance mechanism proposed earlier. To better model the node mobility in a multihop hotspot in our simulation studies, the Public Hotspot Mobility (PHM) model is proposed. Simulation results show that the proposed solution is better in meeting the desired throughputs and delays as compared with best effort and strict priority approaches. Recent theoretical analyses show that the NPDD model with a continuous range of classes can guarantee convergence to desirable QoS through dynamic class selection. However, the overhead of realizing the continuous class scheduler is high. We propose two continuous NPDD schedulers, the Single Queue Continuous NPDD (SQ-CNPDD) scheduler and the Multiple Queue Continuous NPDD (MQ-CNPDD) scheduler, to realize the continuous NPDD model. With simulations, the performance of SQ-CNPDD and MQ-CNPDD are compared to that of NPDD. Kuang-Ching Wang received the B. S. and M. S. degrees in electrical engineering from the National Taiwan University, Taipei, Taiwan, in 1997 and 1999, and the M. S. and Ph. D. degrees in electrical and computer engineering from the University of Wisconsin, Madison, in 2001 and 2003, respectively. Dr. Wang is currently with the Department of Electrical and Computer Engineering, Clemson University, Clemson, SC, as an Assistant Professor. From 2000 to 2003, he participated in the DARPA Sensor Information Technology (SensIT) Program as the leading developer of its network protocols and collaborative signal processing applications. His research interests include wireless networks, mobile computing, distributed protocols, and embedded systems. Dr. Wang is a member of the IEEE Computer, Communication, and Biomedical Engineering Societies and the Association for Computing Machinery. Parameswaran Ramanathan received the B. Tech degree from the Indian Institute of Technology, Bombay, India, in 1984, and the M. S. E. and Ph. D. degrees from the University of Michigan, Ann Arbor, in 1986 and 1989, respectively. Since 1989, Dr. Ramanathan has been faculty member in the Department of Electrical & Computer Engineering, University of Wisconsin, Madison, where is presently a Full Professor. He leads research projects in the areas of sensor networks and next generation cellular technology. In 1997–98, he took a sabbatical leave to visit research groups at AT&T Laboratories and Telcordia Technologies. Dr. Ramanathan’s research interests include wireless and wireline networking, real-time systems, fault-tolerant computing, and distributed systems. He is presently an Associate Editor for IEEE Transactions on Mobile Computing and Elsevier AdHoc Networks Journal. He served as an Associate Editor for IEEE Transactions on Parallel and Distributed Computing from 1996–1999. He has also served on program committees of conferences such as Mobicom, Mobihoc, International Conferences on Distributed Systems and Networks, Distributed Computing Systems, Fault-tolerant Computing Symposium, Real-time Systems Symposium, Conference on Local Computer Networks, and International Conference on Engineering Complex Computer Systems. He was the Finance and Registration Chair for the Fault-tolerant Computing Symposium (1999). He was the program co-chairman of the Workshop on Sensor Networks and Applications (2003), Broadband Wireless (2004), Workshop on Architectures for Real-time Applications, 1994 and the program vice-chair for the International Workshop on Parallel and Distributed Real-time Systems, 1996. He is a member of Association of Computing Machinery and a senior member of IEEE.This revised version was published online in August 2005 with a corrected cover date.     

Performance Improvements Provided by Route Diversity in Multihop Wireless Networks

In multihop wireless networks, the variability of channels results in some paths providing better performance than other paths. Although it is well known that some paths are better than others, a significant number of routing protocols do not focus on utilizing optimal paths. However, cooperative diversity, which is an area of recent interest, provides techniques for efficiently exploiting path and channel diversity. This paper examines the potential performance improvements offered by path diversity. Three settings are examined, namely, where the path loss and channel correlation are neglected, where path loss is considered, but channel correlation is neglected, and where path loss and channel correlation are both accounted for. It is shown that, by exploiting path diversity, dramatic improvements in the considered route metric may be achieved. Furthermore, in some settings, if the link statistics are held constant, then when path diversity is exploited, the route metric improves with path length. This implies that, if links statistics are fixed and if sufficient path diversity exists, then paths with more hops tend to support higher bit rates than paths with fewer hops. It is shown that such behavior occurs when a particular map has a nonzero fixed point.