Fourth Generation (4G) cellular technology Third Generation Partnership Project (3GPP) Long Term Evolution (LTE) offers high data rate capabilities to mobile users; and, operators are trying to deliver a true mobile broadband experience over LTE networks. Mobile TV and Video on Demand (VoD) are expected to be the main revenue generators in the near future [36] and efficient video streaming over wireless is the key to enabling this. 3GPP recommends the use of H.264 baseline profiles for all video based services in Third Generation (3G) Universal Mobile Telecommunication System (UMTS) networks. However, LTE networks need to support mobile devices with different display resolution requirements like small resolution mobile phones and high resolution laptops. Scalable Video Coding (SVC) is required to achieve this goal. Feasibility study of SVC for LTE is one of the main agenda of 3GPP Release10. SVC enhances H.264 with a set of new profiles and encoding tools that may be used to produce scalable bit streams. Efficient adaptation methods for SVC video transmission over LTE networks are proposed in this thesis. Advantages of SVC over H.264 are analyzed using real time use cases of mobile video streaming. Further, we study the cross layer adaptation and scheduling schemes for delivering SVC video streams most efficiently to the users in LTE networks in unicast and multicast transmissions. We propose SVC based video streaming scheme for unicast and multicast transmissions in the downlink direction, with dynamic adaptations and a scheduling scheme based on channel quality information from users. Simulation results indicate improved video quality for more number of users in the coverage area and efficient spectrum usage with the proposed methods.

abstract: Demands in file size and transfer rates for consumer-orientated products have escalated in recent times. This is primarily due to the emergence of high definition video content. Now factor in the consumer desire for convenience, and we find that wireless service is the most desired approach for inter-connectivity. Consumers expect wireless service to emulate wired service with little to virtually no difference in quality of service (QoS). The background section of this document examines the QoS requirements for wireless connectivity of high definition video applications. I then proceed to look at proposed solutions at the physical (PHY) and the media access control (MAC) layers as well as cross-layer schemes. These schemes are subsequently are evaluated in terms of usefulness in a multi-gigabit, 60 GHz wireless multimedia system targeting the average consumer. It is determined that a substantial gap in published literature exists pertinent to this application. Specifically, little or no work has been found that shows how an adaptive PHYMAC cross-layer solution that provides real-time compensation for varying channel conditions might be actually implemented. Further, no work has been found that shows results of such a model. This research proposes, develops and implements in Matlab code an alternate cross-layer solution that will provide acceptable QoS service for multimedia applications. Simulations using actual high definition video sequences are used to test the proposed solution. Results based on the average PSNR metric show that a quasi-adaptive algorithm provides greater than 7 dB of improvement over a non-adaptive approach while a fully-adaptive alogrithm provides over18 dB of improvement. The fully adaptive implementation has been conclusively shown to be superior to non-adaptive techniques and sufficiently superior to even quasi-adaptive algorithms. / Dissertation/Thesis / M.S. Engineering 2011

Fourth Generation (4G) cellular technology Third Generation Partnership Project (3GPP) Long Term Evolution (LTE) offers high data rate capabilities to mobile users; and, operators are trying to deliver a true mobile broadband experience over LTE networks. Mobile TV and Video on Demand (VoD) are expected to be the main revenue generators in the near future [36] and efficient video streaming over wireless is the key to enabling this. 3GPP recommends the use of H.264 baseline profiles for all video based services in Third Generation (3G) Universal Mobile Telecommunication System (UMTS) networks. However, LTE networks need to support mobile devices with different display resolution requirements like small resolution mobile phones and high resolution laptops. Scalable Video Coding (SVC) is required to achieve this goal. Feasibility study of SVC for LTE is one of the main agenda of 3GPP Release10. SVC enhances H.264 with a set of new profiles and encoding tools that may be used to produce scalable bit streams. Efficient adaptation methods for SVC video transmission over LTE networks are proposed in this thesis. Advantages of SVC over H.264 are analyzed using real time use cases of mobile video streaming. Further, we study the cross layer adaptation and scheduling schemes for delivering SVC video streams most efficiently to the users in LTE networks in unicast and multicast transmissions. We propose SVC based video streaming scheme for unicast and multicast transmissions in the downlink direction, with dynamic adaptations and a scheduling scheme based on channel quality information from users. Simulation results indicate improved video quality for more number of users in the coverage area and efficient spectrum usage with the proposed methods.

We investigate diverse aspects of the performance of wireless networks, including throughput, delay and distributed complexity. <br />One of the main challenges for optimizing them arises from radio interference, an inherent factor in wireless networks.<br />Graph-based interference models represent a large class of interference models widely used for the study of wireless networks,<br />and suffer from the weakness of over-simplifying the interference caused by wireless signals in a local and binary way.<br />A more sophisticated interference model, the physical interference model, based on SINR constraints,<br />is considered more realistic but is more challenging to study (because of its non-linear form and non-local property).<br />In this dissertation, we study the connections between the two types of interference models -- graph-based and physical interference models --<br />and tackle a set of fundamental problems under the physical interference model;<br />previously, some of the problems were still open even under the graph-based interference model, and to those we have provided solutions under both types of interference models.<br /><br />The underlying interference models affect scheduling and power control -- essential building blocks in the operation of wireless networks -- that directly deal with the wireless medium; the physical interference model (compared to graph-based interference model) compounds the problem of efficient scheduling and power control by making it non-local and non-linear.<br />The system performance optimization and tradeoffs with respect to throughput and delay require a ``global\'\' view across<br />transport, network, media access control (MAC), physical layers (referred to as cross-layer optimization)<br />to take advantage of the control planes in different levels of the wireless network protocol stack.<br />This can be achieved by regulating traffic rates, finding traffic flow paths for end-to-end sessions,<br />controlling the access to the wireless medium (or channels),<br />assigning the transmission power, and handling signal reception under interference.<br /><br />The theme of the dissertation is<br />distributed algorithms and optimization of QoS objectives under the physical interference model.<br />We start by developing the first low-complexity distributed scheduling and power control algorithms for maximizing the efficiency ratio for different interference models;<br />we derive end-to-end per-flow delay upper-bounds for our scheduling algorithms and our delay upper-bounds are the first network-size-independent result known for multihop traffic.<br />Based on that, we design the first cross-layer multi-commodity optimization frameworks for delay-constrained throughput maximization by incorporating the routing and traffic control into the problem scope.<br />Scheduling and power control is also inherent to distributed computing of ``global problems\'\', e.g., the maximum independent set problems in terms of transmitting links and local broadcasts respectively, and the minimum spanning tree problems.<br />Under the physical interference model, we provide the first sub-linear time distributed solutions to the maximum independent set problems, and also solve the minimum spanning tree problems efficiently.<br />We develop new techniques and algorithms and exploit the availability of technologies (full-/half-duplex radios, fixed/software-defined power control) to further improve our algorithms.<br />%This fosters a deeper understanding of distributed scheduling from the network computing point of view.<br /><br /><br />We highlight our main technical contributions, which might be of independent interest to the design and analysis of optimization algorithms.<br />Our techniques involve the use of linear and mixed integer programs in delay-constrained throughput maximization. This demonstrates the combined use of different kinds of combinatorial optimization approaches for multi-criteria optimization.<br />We have developed techniques for queueing analysis under general stochastic traffic to analyze network throughput and delay properties.<br />We use randomized algorithms with rigorously analyzed performance guarantees to overcome the distributed nature of wireless data/control communications.<br />We factor in the availability of emerging radio technologies for performance improvements of our algorithms.<br />Some of our algorithmic techniques that would be of broader use in algorithms for the physical interference model include:<br />formal development of the distributed computing model in the SINR model, and reductions between models of different technological capabilities, the redefinition of interference sets in the setting of SINR constraints, and our techniques for distributed computation of rulings (informally, nodes or links which are well-separated covers).<br /> / Ph. D.

In recent years, the development of a large variety of mobile computing devices has led to wide scale deployment and use of wireless ad hoc and sensor networks. Wireless Sensor Networks consist of battery powered, tiny and cheap "motes", having sensing and wireless communication capabilities. Although wireless motes have limited battery power, communication and computation capabilities, the range of their application is vast. In the first part of the dissertation, we have addressed the specific application of Biomedical Sensor Networks. To solve the problem of data routing in these networks, we have proposed the Adaptive Least Temperature Routing (ALTR) algorithm that reduces the average temperature rise of the nodes in the in-vivo network while routing data efficiently. For delay sensitive biomedical applications, we proposed the Hotspot Preventing Routing (HPR) algorithm which avoids the formation of hotspots (regions having very high temperature) in the network. HPR forwards the packets using the shortest path, bypassing the regions of high temperature and thus significantly reduces the average packet delivery delay, making it suitable for real-time applications of in-vivo networks. We also proposed another routing algorithm suitable for being used in a network of id-less biomedical sensor nodes, namely Routing Algorithm for networks of homogeneous and Id-less biomedical sensor Nodes (RAIN). Finally we developed Biocomm, a cross-layer MAC and Routing protocol co-design for Biomedical Sensor Networks, which optimizes the overall performance of an in-vivo network through cross-layer interactions. We performed extensive simulations to show that the proposed Biocomm protocol performs much better than the other existing MAC and Routing protocols in terms of preventing the formation of hotspots, reducing energy consumption of nodes and preventing network congestion when used in an in-vivo network. In the second part of the dissertation, we have addressed the problems of habitat-monitoring sensor networks, broadcast algorithms for sensor networks and the congestion problem in sensor networks as well as one non-sensor network application, namely, on-chip communication networks. Specifically, we have proposed a variation of HPR algorithm, called Hotspot Preventing Adaptive Routing (HPAR) algorithm, for efficient data routing in Networks On-Chip catering to their specific hotspot prevention issues. A protocol similar to ALTR has been shown to perform well in a sensor network deployed for habitat monitoring. We developed a reliable, low overhead broadcast algorithm for sensor networks namely Topology Adaptive Gossip (TAG) algorithm. To reduce the congestion problem in Wireless Sensor Networks, we proposed a tunable cross-layer Congestion Reducing Medium Access Control (CRMAC) protocol that utilizes buffer status information from the Network layer to give prioritized medium access to congested nodes in the MAC layer and thus preventing congestion and packet drops. CRMAC can also be easily tuned to satisfy different application-specific performance requirements. With the help of extensive simulation results we have shown how CRMAC can be adapted to perform well in different applications of Sensor Network like Emergency Situation that requires a high network throughput and low packet delivery latency or Long-term Monitoring application requiring energy conservation.

No description available.

Video communications play a vital role in present and future wireless ad hoc networks. One of the key requirements for a successful deployment of multimedia applications in multihop wireless networks is the ability to provide an acceptable video quality, even under a highly dynamic and perhaps unfriendly (or hostile) environment (e.g., in the presence of frequent node/link failure, interference, shadowing, fading, and so forth). Existing ad hoc routing protocols work well for data communications, but are not optimized for video, which is sensitive to latency and packet loss. Moreover, traditional end system based error control mechanisms alone cannot guarantee a sustainable video quality. Conventional QoS approaches typically optimize one or more network layer metrics, but they are usually agnostic to any kind of application layer performance. Consequently, new methodologies must be explored to improve the performance of video applications in multihop wireless networks. This dissertation directly addresses this important problem area by leveraging recent advances in video coding techniques along with novel cross-layer formulations and powerful optimization techniques. We follow an application centric cross-layer approach to address multimedia service provisioning over ad hoc networks. Our research efforts show that video communications over multihop wireless networks can substantially benefit from a cross-layer design principle by factoring in application layer video quality into routing algorithmic designs at the network layer. There are three components in this investigation, namely, (1) concurrent routing, (2) path selection and rate allocation, and (3) multipath routing for multiple description video. Each component addresses one or more unique challenges that hinder video communications in multihop wireless networks. Although we expect that a cross-layer approach will be more effective than a network centric (single-layer) approach in addressing application performance, it also brings in complex problems that cannot be effectively solved using traditional methods, and thus, calls for the design of customized algorithms. In concurrent routing, we focus on issues that arise while supporting multiple concurrent video communication sessions in an ad hoc network. These sessions compete for limited network resources (such as bandwidth) while interacting with each other. Such inter-session interactions couple the performance of an individual flow with that of other flows. Applying a video centric cross-layer design principle, we model the end-to-end video distortion as a function of network layer behavior, and formulate a network-wide optimal routing problem that minimizes the total video distortion. Results based on computational experiments performed using randomly generated network topologies establish the relative efficacy and robustness of the proposed genetic algorithm based solution approach. Specifically, we demonstrate that our approach outperforms other trajectory based metaheuristic approaches as well as with conventional network centric routing algorithms such as shortest path and disjoint shortest path routing. The joint path selection and rate allocation problem considers not only selecting the best set of paths for video communication, but also, computing the optimal video encoding rate and partitioning it among the chosen set of paths. The end-to-end video distortion is modeled as a function of network layer resources by capturing the tight coupling that exists between the optimal encoding rate for each video session, the selection of paths for video transmission, and the allocation of traffic among these selected paths. This problem is formulated as a nonlinear nonconvex programming problem, for which a tight linear programming relaxation is constructed via the Reformulation-Linearization Technique (RLT). This construct is embedded within a specialized branch-and-bound algorithm to achieve global optimality. Computational experience is reported for various problem instances, and the results validate the robustness of the proposed algorithmic procedure. The results exhibit the advantage of the solution approach over the popularly used max-min rate allocation scheme. The emergence of Multiple Description (MD) coding technique offers great potential for multipath routing of video in multihop wireless networks. In studying multipath routing for MD coding, we show that MD coded video, when used in combination with multipath routing in wireless networks, has tremendous advantages over traditional layered video coding techniques. We discuss how to implement an MD video codec and formulate a cross-layer optimization problem that can find a set of optimal paths, (one for each description) such that the overall video quality at the receiver is maximized. We further devise a specialized RLT-based branch-and-bound solution procedure for the ensuing 0-1 mixed integer nonconvex optimization problem. Convergence behavior of the proposed solution procedure is observed for various network topologies and the results further demonstrate the performance advantage of the proposed cross-layer approach over non-cross-layer approaches. The scope of this research is highly interdisciplinary. It intersects video communication, networking, optimization, and algorithm design. We expect that the theoretical and algorithmic results of this investigation will serve as important building blocks in developing a comprehensive methodology for addressing complex cross-layer problems in the area of wireless ad hoc networks. / Ph. D.

Recent advancements in frequency-agile radio technology and dynamic spectrum access network have created a huge space for improving the utilization efficiency of wireless spectrum. Existing algorithms and protocols, however, have not taken full advantage of the new technologies due to obsolete network design ideologies inherited from conventional network design, such as static spectrum access and static channelization. In this dissertation, we propose new resource management models and algorithms that capitalize on the frequency-agility of next generation radios and the dynamic spectrum access concepts to increase the utilization efficiency of wireless spectrum. We first propose a new analytical model for Dynamic Spectrum Access (DSA) networks. Compared to previous models, the new model is able to include essential DSA mechanisms such as spectrum sensing and primary interference avoidance into solid mathematical representation and thus drastically increase the accuracy of our model. The subsequent numerical study conforms well with existing empirical studies and provides fundamental insights on the design of future DSA networks. We then take advantage of partially overlapped channel in frequency-agile radio networks and propose simple joint channel scheduling and flow routing optimization algorithm that maximizes network throughput. The model quantifies the impact of fundamental network settings, such as node density and traffic load, on the performance of partially overlapped channel based networks. We then propose a cross-layer radio resource allocation algorithm JSSRC (Joint Spectrum Sharing and end-to-end data Rate Control) that iteratively adapts a frequency-agile radio network to optimum with regard to aggregate network spectrum utilization. Subsequently, we extend JSSRC to include routing and present TRSS (joint Transport, Routing and Spectrum Sharing) to solve the much more complex joint transport, routing and spectrum sharing optimization problem. Both JSSRC and TRSS enjoy theoretical convergence and achieve optimum with appropriate scheduling algorithms. The works together strive to improve efficiency of spectrum utilization in frequency-agile radio networks. Numerical and simulation studies show the effectiveness of our designs to reduce the so-called spectrum shortage problem. / Ph. D.

Spatial diversity, in the form of employing multiple antennas (i.e., MIMO), has proved to be very effective in increasing network capacity and reliability. However, equipping a wireless node with multiple antennas may not be practical, as the footprint of multiple antennas may not fit on a wireless node (particularly on handheld wireless devices). In order to achieve spatial diversity without requiring multiple antennas on the same node, the so-called cooperative communications (CC) has been introduced. Under CC, each node is equipped with only a single antenna and spatial diversity is achieved by exploiting the antennas on other nodes in the network through cooperative relaying. The goal of this dissertation is to maximize throughput at network level through CC at the physical layer. A number of problems are explored in this investigation. The main contributions of this dissertation can be summarized as follows. <b>1. Optimal Relay Assignment.</b> We first consider a simple CC model where each source-destination pair may employ only a single relay. For this three-node model, the choice of a relay node (among a set of available relay nodes) for a given session is critical in the overall network performance. We study the relay node assignment problem in a cooperative ad hoc network environment, where multiple source-destination pairs compete for the same pool of relay nodes in the network. Our objective is to assign the available relay nodes to different source-destination pairs so as to maximize the minimum data rate among all pairs. We present an optimal polynomial time algorithm, called ORA, that solves this problem. A novel idea in this algorithm is a "linear marking" mechanism, which maintains linear complexity at each iteration. We offer a formal proof of optimality for ORA and use numerical results to demonstrate its capability. <b>2. Incorporating Network Coding.</b> It has been shown that network coding (NC) can reduce the time-slot overhead when multiple session share the same relay node in CC. Such an approach is called network-coded CC (or NC-CC). Most of the existing works have mainly focused on the benefits of this approach. The potential adverse effect under NC-CC remains unknown. We explore this important problem by introducing the concept of network coding noise (NC noise). We show that due to NC noise, NC may not be always beneficial to CC. We substantiate this important finding in two important scenarios: analog network coding (ANC) in amplify-and-forward (AF) CC, and digital network coding (DNC) in decode-and-forward (DF) CC. We analyze the origin of NC noise via a careful study of signal aggregation at a relay node and signal extraction at a destination node. We derive a closed-form expression for NC noise at each destination node and show that the existence of NC noise could diminish the advantage of NC in CC. Our results shed new light on how to use NC in CC effectively. <b>3. Session Grouping and Relay Node Selection.</b> When there are multiple sessions in the network, it may be necessary to combine sessions into different groups, and then have each group select the most beneficial relay node for NC-CC. We study this joint grouping and relay node selection problem for NC-CC. By studying matching problems in hypergraphs, we show that this problem is NP-hard. We then propose a distributed and online algorithm to solve this problem. The key idea in our algorithm is to have each neighboring relay node of a newly joined session determine and offer the best group for this session from the groups that it is currently serving; and then to have the source node of this newly joined session select the best group among all received offers. We show that our distributed algorithm has polynomial complexity. Using extensive numerical results, we show that our distributed algorithm is near-optimal and adapts well to online network dynamics. <b>4. Grouping and Matching for Multi-Relay Cooperation.</b> Existing models of NC-CC consider only single relay node for each session group. We investigate how NC-CC behaves when multiple relay nodes are employed. For a given session, we develop closed form formulas for the mutual information and achievable rate under multi-relay NC-CC. In multi-relay NC-CC, the achievable rate of a session depends on the other sessions in its group as well as the set of relay nodes used for NC-CC. Therefore, we study NC-CC via joint optimization of grouping and matching of session and relay groups in an ad hoc network. Although we show that the joint problem is NP-hard, we develop an efficient polynomial time algorithm for grouping and matching (called G²M). G²M first builds beneficial relay groups for individual sessions. This is followed by multiple iterations during which sessions are combined with other sessions to form larger and better session groups (while corresponding relay groups are merged and updated accordingly). Using extensive numerical results, we show the efficiency and near optimality of our G²M algorithm. / Ph. D.

Plenty of novel emerging technologies are being proposed and evaluated today, mostly at the device and circuit levels. It is unclear what the impact of different new technologies at the system level will be. What is clear, however, is that new technologies will make their way into systems and will increase the already high complexity of heterogeneous parallel computing platforms, making it ever so difficult to program them. This paper discusses a programming stack for heterogeneous systems that combines and adapts well-understood principles from different areas, including capability-based operating systems, adaptive application runtimes, dataflow programming models, and model checking. We argue why we think that these principles built into the stack and the interfaces among the layers will also be applicable to future systems that integrate heterogeneous technologies. The programming stack is evaluated on a tiled heterogeneous multicore.