Many mobile applications retrieve content from remote servers via user generated queries. Processing these queries is often needed before the desired content can be identified. Processing the request on the mobile devices can quickly sap the limited battery resources. Conversely, processing user queries at remote servers can have slow response times due communication latency incurred during transmission of the potentially large query. We evaluate a network-assisted mobile computing scenario where mid-network nodes with “leasing” capabilities are deployed by a service provider. Leasing computation power can reduce battery usage on the mobile devices and improve response times. However, borrowing processing power from mid-network nodes comes at a leasing cost which must be accounted for when making the decision of where processing should occur. We study the tradeoff between battery usage, processing and transmission latency, and mid-network leasing. We use the dynamic programming framework to solve for the optimal processing policies that suggest the amount of processing to be done at each mid-network node in order to minimize the processing and communication latency and processing costs. Through numerical studies, we examine the properties of the optimal processing policy and the core tradeoffs in such systems.

We study scheduling of multimedia traffic on the downlink of a wireless communication system. We examine a scenario where multimedia packets are associated with strict deadlines and are equivalent to lost packets if they arrive after their associated deadlines. Lost packets result in degradation of playout quality at the receiver, which is quantified in terms of the "distortion cost" associated with each packet. Our goal is to design a scheduler which minimizes the aggregate distortion cost over all receivers. We study the scheduling problem in a dynamic programming (DP) framework. Under well justified modeling reductions, we extensively characterize structural properties of the optimal control associated with the DP problem. We leverage these properties to design a low-complexity Channel, Deadline, and Distortion (CD2) aware heuristic scheduling policy amenable to implementation in real wireless systems. We evaluate the performance of CD2via trace-driven simulations using H.264/MPEG-4 AVC coded video. Our experimental results show that CD2comfortably outperforms benchmark schedulers like earliest deadline first (EDF) and best channel first (BCF). CD2achieves these performance gains by using the knowledge of packet deadlines, wireless channel conditions, and application specific information (per-packet distortion costs) in a systematic and unified way for multimedia scheduling.

The growing popularity of multimedia streaming applications brings a growth in diversity of media clients (laptops, PDAs, cellphones). Effectively serving this heterogeneous group of users is highly desirable. Scalable media codecs such as H.264/MPEG-4 SVC help make this adaptation possible. To account for the various capabilities and requests of each user, such as varying spatial or temporal resolutions, multiple distortion measures (MDM) are considered. Rather than consider a homogeneity in users, the MDM framework considers multiple different distortion values for each media packet for each user type. We consider the scenario of simultaneously broadcasting a video stream to multiple users over wireless links. The objective is to design a scheduling algorithm which achieves the highest aggregate quality-of-service, measured by distortion and delay, over all different user types. We cast the problem as a stochastic shortest path problem and use dynamic programming to find the optimal policy. For statistically static channels, the optimal policy is shown to be of threshold type. For time-varying channels, a quasi-static policy is introduced. Experimental results show that our policy reduces distortion by up to a factor of 2 over conventional approaches which do not consider MDM.

The growing diversity in media clients calls for content providers to adapt media content to adhere to their various needs. It is desirable to serve these heterogeneous users in a fast and efficient manner. Scalable media, such as H.264/MPEG- 4 SVC, helps make this possible. To account for various viewing capabilities of each user, such as different spatial or temporal resolutions, the Multiple Distortion Measures framework is used [1], [2]. MDM associates multiple distortion values with each packet depending on the user types (low/high resolution viewers, low/high frame rate viewers, etc.) who will consume the media packets. In this paper, we examine how to broadcast media packets with multiple distortion measures to multiple users. The tradeoff between media distortion and delay (in the form of retransmissions) plays an integral role in the scheduling decision. We cast the problem as a stochastic shortest path problem and use Dynamic Programming to find the optimal policy. In the case of statistically static channels, the optimal policy is shown to be a threshold policy where the number of allowable retransmissions is dictated by the importance, in terms of incurred distortion, of each packet. Through experimental results, we show that our policy, which considers multiple distortion measures, achieves up to 8 dB gains over conventional approaches. Finally, a policy based on the theoretical results of statistically static channels is empirically shown to have high performance for time-varying channels modeled by a two-state Markov Chain.

With the recent growth in mobile device types, an interesting question that arises is how to serve media content to users with a diverse set of capabilities. Defining multiple distortion metrics, one for each type of user, allows for specialized service to each user type, which can result in significantly improved quality of service. H.264/MPEG-4 SVC is a scalable video codec that allows for easy spatial and temporal adaptation of encoded video by selecting or dropping packets. We examine using multiple distortion measures (MDM) for scheduling packets in the context of streaming temporally scalable video to users with different target frame rates. We show that gains in PSNR of multiple dB can be achieved when taking MDM into consideration for making scheduling decisions.

Multimedia applications for mobile devices are increasing and growing more sophisticated. Many of these applications require computationally intensive processing, such as image processing, source coding, feature extraction and feature matching. If all of this processing were performed on the mobile device, its limited battery supply would quickly deplete. However, if the request must be transmitted through a network and processed at a remote application server large delays may be incurred due to communication latency-especially if the original size of the request message is very large. In this paper, we propose the use of mid-network processing on intermediary nodes in a multistage tandem network. We refer to this as ldquowireless network-Assisted computingrdquo. Allowing for mid-network processing can alleviate some of the processing burden on the mobile device, thereby extending its lifetime. It can also reduce communication latency by reducing the amount of information transmitted along each link. Certainly ldquoleasingrdquo processing power from these nodes comes at a price-in some cases it is beneficial to lease, in others it is not. We examine the core tradeoff between battery usage, latency, and usage of processing power at mid-network nodes. We identify some interesting properties of the optimal processing schedule. Through numerical analysis we study these properties and tradeoffs.

As the diversity in end-user devices and networks grows, it becomes important to be able to efficiently and adaptively serve media content to different types of users. A key question surrounding adaptive media is how to do Rate-Distortion optimized scheduling. Typically, distortion is measured with a single distortion measure, such as the Mean-Squared Error compared to the original high resolution image or video sequence. Due to the growing diversity of users with varying capabilities such as different display sizes and resolutions, we introduceMultipleDistortionMeasures(MDM) to account for a diverse range of users and target devices. MDM gives a clear framework with which to evaluate the performance of media systems which serve a variety of users. Scalable coders, such as JPEG2000 and H.264/MPEG-4 SVC, allow for adaptation to be performed with relatively low computational cost. We show that accounting for MDM can significantly improve system performance; furthermore, by combining this with scalable coding, this can be done efficiently. Given these MDM, we propose an algorithm to generateembeddedschedules, which enables low-complexity, adaptive streaming of scalable media packets to minimize distortion across multiple users. We show that using MDM achieves up to 4 dB gains for spatial scalability applied to images and 12 dB gains for temporal scalability applied to video.

The increasing diversity of end-user devices and networks allow different users to receive and view images and video at different resolutions and rates. Scalable coding methods allow streaming media systems to easily adapt media by selecting packets according to schedules that reflect their importance. Traditional scheduling algorithms are based on a single distortion measure such as mean-squared error relative to the original high resolution image. In this paper, we present a new approach of using multiple distortion measures to schedule packets in a manner that explicitly accounts for a range of rates and resolutions. We show the effectiveness of this approach and examine a common scenario where multiple distortion measures are helpful. We present an algorithm that generates embedded JPEG2000 schedules and achieves 1 to 4 dB improvement over conventional approaches.

Due to the increase in diversity of wireless devices, streaming media systems must be capable of serving multiple types of users. Scalable coding allows for adaptations without re-encoding. To account for various viewing capabilities of each user, such as different spatial resolutions, multiple distortion measures are used. In this paper, we examine the question of how to broadcast media packets with multiple distortion measures to multiple users. We cast the problem as a stochastic shortest path problem and use Dynamic Programming to find the optimal policy. We generate an offline algorithm to generate the optimal transmission policy for the general case. We then show the optimal policy can be done online via a simple threshold policy for the case of independent Bernoulli packet losses. Through experimental results, we show that our policy, which considers multiple distortion measures, achieves up to 2dB gains over conventional approaches.

The JPEG-2000 compression standard codes images into data units, referred to as packets, such that images can be successfully decoded, while incurring some distortion, with a subset of these packets. This paper examines how to optimally select subsets of packets (referred to as schedules) that minimize distortion subject to varying rate constraints. We solve for the optimal schedule at a single rate by solving the precedence constraint knapsack problem (PCKP) via dynamic programming, and show that with modifications that consider the specific dependencies of JPEG-2000 packets, we can compute the optimal schedules for all rates through a single execution of our algorithm. We then analyze important properties of the optimal schedule. Using these properties, we look at a fused-greedy algorithm, similar to the recently proposed convex hull algorithm, to generate embedded schedules of JPEG-2000 packets. These embedded schedules have the property that all the JPEG-2000 packets in lower rate schedules are included in higher rate schedules; embedded schedules enable low-complexity, adaptive streaming. We demonstrate the algorithm's near optional performance through comparisons to the optimal performance for JPEG-2000 coded data.

We consider transfer of video frames over a time-varying wireless channel. When the channel is good, the transmitter can send frames at a higher rate than the receiver can consume them via playout. In that case, we introduce the idea of admitting new frames even when the receiver buffer is full, by selectively evicting frames already in the buffer; we can also control the playout rate, so as to optimize the tradeoff between video distortion and the time to freeze when the channel turns bad and frames arrive at a lower rate than should be played out. The decision/control problem of whether to admit a new frame, which already stored one to evict to accommodate the new one, and at what rate to play out frames is formulated within a dynamic programming framework, and an interesting connection to the Knapsack problem is made. Application of the idea in a relevant simple system shows significant performance gains, indicating that it is a promising approach for improving video delivery performance over challenging wireless channels

Portable devices (such as personal digital assistants and laptops with wireless connectivity) are becoming ubiquitous. As their functionality and capabilities increase, their energy consumption requirements also increase. Yet, these devices have to operate on limited batteries. In order to maximize the battery lifetime, it is necessary to optimize the use of energy at various components of such a device. In this paper, we consider a single portable device operating on a limited battery that transmits information over an interference-limited wireless channel. We seek to optimize the power consumption on the communication radio in this device, by controlling both the operation mode and the transmission power. We model the general problem using dynamic programming, obtain the optimal solutions for insightful special cases and explore various design tradeoffs. Our work provides an analytical framework for stochastic modeling and optimization of energy spent for communications in battery-operated portable devices.