Ultra-wideband (UWB) is an appealing transmission technology for short-range, bandwidth demanded wireless communications. With the data rate of several hundred megabits per second, UWB demonstrates great potential in supporting multimedia streams such as high-definition television (HDTV), voice over Internet Protocol (VoIP), and console gaming in office or home networks, known as the wireless personal area network (WPAN). While vast research effort has been made on the physical layer issues of UWB, the corresponding medium access control (MAC) protocols that exploit UWB technology have not been well developed. Given an extremely wide bandwidth of UWB, a fundamental problem on how to manage multiple users to efficiently utilize the bandwidth is a MAC design issue. Without explicitly considering the physical properties of UWB, existing MAC protocols are not optimized for UWB-based networks. In addition, the limited processing capability of UWB devices poses challenges to the design of low-complexity MAC protocols. In this thesis, we comprehensively investigate the MAC protocols for UWB networks. The objective is to link the physical characteristics of UWB with the MAC protocols to fully exploit its advantage. We consider two themes: centralized and distributed UWB networks. For centralized networks, the most critical issue surrounding the MAC protocol is the resource allocation with fairness and quality of service (QoS) provisioning. We address this issue by breaking down into two scenarios: homogeneous and heterogeneous network configurations. In the homogeneous case, users have the same bandwidth requirement, and the objective of resource allocation is to maximize the network throughput. In the heterogeneous case, users have different bandwidth requirements, and the objective of resource allocation is to provide differentiated services. For both design objectives, the optimal scheduling problem is NP-hard. Our contributions lie in the development of low-complexity scheduling algorithms that fully exploit the characteristics of UWB. For distributed networks, the MAC becomes node-based problems, rather than link-based problems as in centralized networks. Each node either contends for channel access or reserves transmission opportunity through negotiation. We investigate two representative protocols that have been adopted in the WiMedia specification for future UWB-based WPANs. One is a contention-based protocol called prioritized channel access (PCA), which employs the same mechanisms as the enhanced distributed channel access (EDCA) in IEEE 802.11e for providing differentiated services. The other is a reservation-based protocol called distributed reservation protocol (DRP), which allows time slots to be reserved in a distributed manner. Our goal is to identify the capabilities of these two protocols in supporting multimedia applications for UWB networks. To achieve this, we develop analytical models and conduct detailed analysis for respective protocols. The proposed analytical models have several merits. They are accurate and provide close-form expressions with low computational effort. Through a cross-layer approach, our analytical models can capture the near-realistic protocol behaviors, thus useful insights into the protocol can be obtained to improve or fine-tune the protocol operations. The proposed models can also be readily extended to incorporate more sophisticated considerations, which should benefit future UWB network design.

This thesis contributes toward understanding fundamental limits of multi-user fading channels and random wireless networks. Specifically, considering different samples of channel gains corresponding to different users/nodes in a multi-user wireless system, the maximum number of channel gains supporting a minimum rate is asymptotically obtained. First, the user capacity of fading multi-user channels with minimum rates is analyzed. Three commonly used fading models, namely, Rayleigh, Rician and Nakagami are considered. For broadcast channels, a power allocation scheme is proposed to maximize the number of active receivers, for each of which, a minimum rate Rmin>0 can be achieved. Under the assumption of independent Rayleigh fading channels for different receivers, as the total number of receivers n goes to infinity, the maximum number of active receivers is shown to be arbitrarily close to ln(P.ln(n))/Rmin with probability approaching one, where P is the total transmit power. The results obtained for Rayleigh fading are extended to the cases of Rician and Nakagami fading models. Under the assumption of independent Rician fading channels for different receivers, as the total number of receivers n goes to infinity, the maximum number of active receivers is shown to be equal to ln(2P.ln(n))/Rmin with probability approaching one. For broadcast channels with Nakagami fading, the maximum number of active receivers is shown to be equal to ln(ω/μ.P.ln(n))/Rmin with probability approaching one, where ω and μ are the Nakagami distribution parameters. A by-product of the results is to also provide a power allocation strategy that maximizes the total throughput subject to the rate constraints. In multiple-access channels, the maximum number of simultaneous active transmitters (i.e. user capacity) is obtained in the many user case in which a minimum rate must be maintained for all active users. The results are presented in the form of scaling laws as the number of transmitters increases. It is shown that for all three fading distributions, the user capacity scales double logarithmically in the number of users and differs only by constants depending on the distributions. We also show that a scheduling policy that maximizes the number of simultaneous active transmitters can be implemented in a distributed fashion. Second, the maximum number of active links supporting a minimum rate is asymptotically obtained in a wireless network with an arbitrary topology. It is assumed that each source-destination pair communicates through a fading channel and destinations receive interference from all other active sources. Two scenarios are considered: 1) Small networks with multi-path fading, 2) Large Random networks with multi-path fading and path loss. In the first case, under the assumption of independent Rayleigh fading channels for different source-destination pairs, it is shown that the optimal number of active links is of the order log(N) with probability approaching one as the total number of nodes, N, tends to infinity. The achievable total throughput also scales logarithmically with the total number of links/nodes in the network. In the second case, a two-dimensional large wireless network is considered and it is assumed that nodes are Poisson distributed with a finite intensity. Under the assumption of independent multi-path fading for different source-destination pairs, it is shown that the optimal number of active links is of the order N with probability approaching one. As a result, the achievable per-node throughput obtained by multi-hop routing scales with Θ(1/√N).

A primary challenge in wireless networks is to use available resources efficiently so that the Quality of Service (QoS) is satisfied while maximizing the throughput of the network. Among different resource allocation strategies, power and spectrum allocations have long been regarded as efficient tools to mitigate interference and improve the throughput of the network. Also, achieving a low transmission delay is an important QoS requirement in buffer-limited networks, particularly for users with real-time services. For these networks, too much delay results in dropping some packets. Therefore, the main challenge in networks with real-time services is to utilize an efficient power allocation scheme so that the delay is minimized while achieving a high throughput. This dissertation deals with these problems in distributed wireless networks.

The high deployment and maintenance costs of last mile wireline networks (i.e., DSL and cable networks) have urged service providers to search for new cost-effective solutions to provide broadband connectivity. Broadband wireless access (BWA) networks, which offer a wide coverage area and high transmission rates in addition to their fast and low-cost deployment, have emerged as an alternative to last mile wireline networks. Therefore, BWA networks are expected to be deployed in areas with different terrain profiles (e.g., urban, suburban, rural) where wireless communication faces different channel impairments. This fact necessitates the adoption of various transmission technologies that combat the channel impairments of each profile. Implementation scenarios of BWA networks considered in this thesis are multicarrier-based direct transmission and single carrier-based cooperative transmission scenarios. The performance of these transmission technologies highly depends on how resources are allocated. In this thesis, we focus on the development of practical resource allocation schemes for the mentioned BWA networks implementation scenarios. In order to develop practical schemes, the imperfection of channel state information (CSI) and computational power limitations are among considered practical implementation issues. The design of efficient resource allocation schemes at the MAC layer heavily relies on the CSI reported from the PHY layer as a measure of the wireless channel condition. The channel estimation error and feedback delay renders the reported CSI erroneous. The inaccuracy in CSI propagates to higher layers, resulting in performance degradation. Although this effect is intuitive, a quantitative measure of this degradation is necessary for the design of practical resource allocation schemes. An approach to the evaluation of the ergodic mutual information that reflects this degradation is developed for single carrier, multicarrier, direct, and cooperative scenarios with inaccurate CSI. Given the CSI estimates and estimation error statistics, the presented evaluation of ergodic mutual information can be used in resource allocation and in assessing the severity of estimation error on performance degradation. A point-to-multipoint (PMP) network that employs orthogonal frequency division multiple access (OFDMA) is considered as one of the most common implementation scenarios of BWA networks. Replacing wireline networks requires not only providing the last mile connectivity to subscribers but also supporting their diverse services with stringent quality of service (QoS) requirements. Therefore, the resource allocation problem (i.e., subcarriers, rate and power allocation) is modeled as a network utility maximization (NUM) one that captures the characteristics of this implementation scenario. A dual decomposition-based resource allocation scheme that takes into consideration the diversity of service requirements and inaccuracy of the CSI estimation is developed. Numerical evaluations and simulations are conducted to validate our theoretical claims that the scheme maximizes resource utilization, coordinates with the call admission controller to guarantee QoS, and accounts for CSI inaccuracy. Cooperation has recently received great attention from the research community and industry because of its low cost and fast deployment in addition to the performance improvement it brings to BWA networks. In cooperative scenarios, subscribers cooperate to relay each other's signals. For this implementation scenario of BWA networks, a robust and constrained Kalman filter-based power allocation scheme is proposed to minimize power consumption and guarantee bit error probability (BEP) requirements. The proposed scheme is robust to CSI inaccuracy, responsive to changes in BEP requirements, and optimal in allocating resources. In summary, research results presented in this thesis contribute to the development of practical resource allocation schemes for BWA networks.

This research investigates cross-layer design in multi-hop wireless networks with random access. Due to the complexity of the problem, we study cross-layer design with a simple slotted ALOHA medium access control (MAC) protocol without considering any network dynamics. Firstly, we study the optimal joint configuration of routing and MAC parameters in slotted ALOHA based wireless networks under a signal to interference plus noise ratio based physical interference model. We formulate a joint routing and MAC (JRM) optimization problem under a saturation assumption to determine the optimal max-min throughput of the flows and the optimal configuration of routing and MAC parameters. The JRM optimization problem is a complex non-convex problem. We solve it by an iterated optimal search (IOS) technique and validate our model via simulation. Via numerical and simulation results, we show that JRM design provides a significant throughput gain over a default configuration in a slotted ALOHA based wireless network. Next, we study the optimal joint configuration of routing, MAC, and network coding in wireless mesh networks using an XOR-like network coding without opportunistic listening. We reformulate the JRM optimization problem to include the simple network coding and obtain a more complex non-convex problem. Similar to the JRM problem, we solve it by the IOS technique and validate our model via simulation. Numerical and simulation results for different networks illustrate that (i) the jointly optimized configuration provides a remarkable throughput gain with respect to a default configuration in a slotted ALOHA system with network coding and (ii) the throughput gain obtained by the simple network coding is significant, especially at low transmission power, i.e., the gain obtained by jointly optimizing routing, MAC, and network coding is significant even when compared to an optimized network without network coding. We then show that, in a mesh network, a significant fraction of the throughput gain for network coding can be obtained by limiting network coding to nodes directly adjacent to the gateway. Next, we propose simple heuristics to configure slotted ALOHA based wireless networks without and with network coding. These heuristics are extensively evaluated via simulation and found to be very efficient. We also formulate problems to jointly configure not only the routing and MAC parameters but also the transmission rate parameters in multi-rate slotted ALOHA systems without and with network coding. We compare the performance of multi-rate and single rate systems via numerical results. We model the energy consumption in terms of slotted ALOHA system parameters. We found out that the energy consumption for various cross-layer systems, i.e., single rate and multi-rate slotted ALOHA systems without and with network coding, are very close.

Resource management is important for network design and deployment. Resource management and allocation have been studied under a wide variety of scenarios --- routing in wired networks, scheduling in cellular networks, multiplexing, switching, and channel access in opportunistic networks are but a few examples. In this dissertation, we revisit resource management in the context of routing and scheduling in multihop wireless networks and pricing in single resource systems. The first issue addressed is of delays in multihop wireless networks. The resource under contention is capacity which is allocated by a joint routing and scheduling algorithm. Delay in wireless networks is a key issue gaining interest with the growth of interactive applications and proliferation of wireless networks. We start with an investigation of the back-pressure algorithm (BPA), an algorithm that activates the schedule with the largest sum of link weights in a timeslot. Though the BPA is throughput-optimal, it has poor end-to-end delays. Our investigation identifies poor routing decisions at low loads as one cause for it. We improve the delay performance of max-weight algorithms by proposing a general framework for routing and scheduling algorithms that allow directing packets towards the sink node dynamically. For a stationary environment, we explicitly formulate delay minimization as a static problem while maintaining stability. We see similar improved delay performance with the advantage of reduced per time-slot complexity. Next, the issue of pricing for flow based models is studied. The increasing popularity of cloud computing and the ease of commerce over the Internet is making pricing a key issue requiring greater attention. Although pricing has been extensively studied in the context of maximizing revenue and fairness, we take a different perspective and investigate pricing with predictability. Prior work has studied resource allocations that link insensitivity and predictability. In this dissertation, we present a detailed analysis of pricing under insensitive allocations. We study three common pricing models --- fixed rate pricing, Vickrey-Clarke-Groves (VCG) auctions, and congestion-based pricing, and provide the expected operator revenue and user payments under them. A pre-payment scheme is also proposed where users pay on arrival a fee for their estimated service costs. Such a mechanism is shown to have lower variability in payments under fixed rate pricing and VCG auctions while generating the same long-term revenue as in a post-payment scheme, where users pay the exact charge accrued during their sojourn. Our formulation and techniques further the understanding of pricing mechanisms and decision-making for the operator.

The combination of infrastructure-to-vehicle and vehicle-to-vehicle communications, namely the multi-hop Vehicular Communications Network (VCN) , appears as a promising solution for the ubiquitous access to IP services in vehicular environments. In this thesis, we address the challenges of multi-hop VCN, and investigate the seamless provision of IP services over such network. Three different schemes are proposed and analyzed. First, we study the limitations of current standards for the provision of IP services, such as 802.11p/WAVE, and propose a framework that enables multi-hop communications and a robust IP mobility mechanism over WAVE. An accurate analytical model is developed to evaluate the throughput performance, and to determine the feasibility of the deployment of IP-based services in 802.11p/WAVE networks. Next, the IP mobility support is extended to asymmetric multi-hop VCN. The proposed IP mobility and routing mechanisms react to the asymmetric links, and also employ geographic location and road traffic information to enable predictive handovers. Moreover, since multi-hop communications suffer from security threats, it ensures that all mobility signalling is authenticated among the participant vehicles. Last, we extend our study to a heterogeneous multi-hop VCN, and propose a hybrid scheme that allows for the on-going IP sessions to be transferred along the heterogeneous communications system. The proposed global IP mobility scheme focuses on urban vehicular scenarios, and enables seamless communications for in-vehicle networks, commuters, and pedestrians. The overall performance of IP applications over multi-hop VCN are improved substantially by the proposed schemes. This is demonstrated by means of analytical evaluations, as well as extensive simulations that are carried out in realistic highway and urban vehicular scenarios. More importantly, we believe that our dissertation provides useful analytical tools, for evaluating the throughput and delay performance of IP applications in multi-hop vehicular environments. In addition, we provide a set of practical and efficient solutions for the seamless support of IP tra c along the heterogeneous and multi-hop vehicular network, which will help on achieving ubiquitous drive-thru Internet, and infotainment traffic access in both urban and highway scenarios.

Ad-Hoc Wireless routing has become an important area of research in the last few years due to the massive increase in wireless devices. Computational Geometry is relevant in attempts to build stable, low power routing schemes. It is only recently, however, that models have been expanded to consider devices with a non-uniform broadcast range, and few properties are known. In particular, we find, via both theoretical and experimental methods, extremal properties for the Localized Delaunay Triangulation over the Mutual Inclusion Graph. We also provide a distributed, sub-quadratic algorithm for the generation of the structure.

As portable computers and wireless networks are becoming ubiquitous, it is natural to consider the user’s position as yet another aspect to take into account when providing services that are tailored to meet the needs of the consumers. Location aware systems could guide persons through buildings, to a particular bookshelf in a library or assist in a vast variety of other applications that can benefit from knowing the user’s position. In indoor positioning systems, the most commonly used method for determining the location is to collect samples of the strength of the received signal from each base station that is audible at the client’s position and then pass the signal strength data on to a positioning server that has been previously fed with example signal strength data from a set of reference points where the position is known. From this set of reference points, the positioning server can interpolate the client’s current location by comparing the signal strength data it has collected with the signal strength data associated with every reference point. Our work proposes the use of multiple successive received signal strength samples in order to capture periodic signal strength variations that are the result of effects such as multi-path propagation, reflections and other types of radio interference. We believe that, by capturing these variations, it is possible to more easily identify a particular point; this is due to the fact that the signal strength fluctuations should be rather constant at every position, since they are the result of for example reflections on the fixed surfaces of the building’s interior. For the purpose of investigating our assumptions, we conducted measurements at a site at Växjö university, where we collected signal strength samples at known points. With the data collected, we performed two different experiments: one with a neural network and one where the k-nearest-neighbor method was used for position approximation. For each of the methods, we performed the same set of tests with single signal strength samples and with multiple successive signal strength samples, to evaluate their respective performances. We concluded that the k-nearest-neighbor method does not seem to benefit from multiple successive signal strength samples, at least not in our setup, compared to when using single signal strength samples. However, the neural network performed about 17% better when multiple successive signal strength samples were used.

The current dominate layered networking architecture, in which each layer is designed and operated independently, results in inefficient and inflexible resource use in wireless networks due to the nature of the wireless medium, such as time-varying channel fading, mutual interference, and topology variations. In this thesis, we focus on resource allocation and scheduling in wireless orthogonal frequency division multiplexing (OFDM) networks based on joint physical and medium access control (MAC) layer optimization. To achieve orders of magnitude gains in system performance, we use two major mechanisms in resource management: exploiting the time variance and frequency selectivity of wireless channels through adaptive modulation, coding, as well as packet scheduling and regulating resource allocation through network economics. With the help of utility functions that capture the satisfaction level of users for a given resource assignment, we establish a utility optimization framework for resource allocation in OFDM networks, in which the network utility at the level of applications is maximized subject to the current channel conditions and the modulation and coding techniques employed in the network. Although the nonlinear and combinatorial nature of the cross-layer optimization challenges algorithm development, we propose novel efficient dynamic subcarrier assignment (DSA) and adaptive power allocation (APA) algorithms that are proven to achieve the optimal or near-optimal performance with very low complexity. Based on a holistic design principle, we design max-delay-utility (MDU) scheduling, which senses both channel and queue information. The MDU scheduling can simultaneously improve the spectral efficiency and provide right incentives to ensure that all applications can receive their different required quality of service (QoS). To facilitate the cross-layer design, we also deeply investigate the mechanisms of channel-aware scheduling, such as efficiency, fairness, and stability. First, using extreme value theory, we analyze the impact of multiuser diversity on throughput and packet delay. Second, we reveal a generic relationship between a specific convex utility function and a type of fairness. Third, with rigorous proofs, we provide a method to design cross-layer scheduling algorithms that allow the queueing stability region at the network layer to approach the ergodic capacity region at the physical layer.