In this paper, we propose a systematic solution to the problem of scheduling delay-sensitive media data for transmission over time-varying wireless channels. We first formulate the dynamic scheduling problem as a Markov decision process (MDP) that ex
plicitly considers the users heterogeneous multimedia data characteristics (e.g. delay deadlines, distortion impacts and dependencies etc.) and time-varying channel conditions, which are not simultaneously considered in state-of-the-art packet scheduling algorithms. This formulation allows us to perform foresighted decisions to schedule multiple data units for transmission at each time in order to optimize the long-term utilities of the multimedia applications. The heterogeneity of the media data enables us to express the transmission priorities between the different data units as a priority graph, which is a directed acyclic graph (DAG). This priority graph provides us with an elegant structure to decompose the multi-data unit foresighted decision at each time into multiple single-data unit foresighted decisions which can be performed sequentially, from the high priority data units to the low priority data units, thereby significantly reducing the computation complexity. When the statistical knowledge of the multimedia data characteristics and channel conditions is unknown a priori, we develop a low-complexity online learning algorithm to update the value functions which capture the impact of the current decision on the future utility. The simulation results show that the proposed solution significantly outperforms existing state-of-the-art scheduling solutions.
In this paper, we consider the problem of real-time transmission scheduling over time-varying channels. We first formulate the transmission scheduling problem as a Markov decision process (MDP) and systematically unravel the structural properties (e.
g. concavity in the state-value function and monotonicity in the optimal scheduling policy) exhibited by the optimal solutions. We then propose an online learning algorithm which preserves these structural properties and achieves -optimal solutions for an arbitrarily small . The advantages of the proposed online method are that: (i) it does not require a priori knowledge of the traffic arrival and channel statistics and (ii) it adaptively approximates the state-value functions using piece-wise linear functions and has low storage and computation complexity. We also extend the proposed low-complexity online learning solution to the prioritized data transmission. The simulation results demonstrate that the proposed method achieves significantly better utility (or delay)-energy trade-offs when comparing to existing state-of-art online optimization methods.
In this paper, we propose a systematic solution to the problem of cross-layer optimization for delay-sensitive media transmission over time-varying wireless channels as well as investigate the structures and properties of this solution, such that it
can be easily implemented in various multimedia systems and applications. Specifically, we formulate this problem as a finite-horizon Markov decision process (MDP) by explicitly considering the users heterogeneous multimedia traffic characteristics (e.g. delay deadlines, distortion impacts and dependencies etc.), time-varying network conditions as well as, importantly, their ability to adapt their cross-layer transmission strategies in response to these dynamics. Based on the heterogeneous characteristics of the media packets, we are able to express the transmission priorities between packets as a new type of directed acyclic graph (DAG). This DAG provides the necessary structure for determining the optimal cross-layer actions in each time slot: the root packet in the DAG will always be selected for transmission since it has the highest positive marginal utility; and the complexity of the proposed cross-layer solution is demonstrated to linearly increase w.r.t. the number of disconnected packet pairs in the DAG and exponentially increase w.r.t. the number of packets on which the current packets depend on. The simulation results demonstrate that the proposed solution significantly outperforms existing state-of-the-art cross-layer solutions. Moreover, we show that our solution provides the upper bound performance for the cross-layer optimization solutions with delayed feedback such as the well-known RaDiO framework.
In this paper, we formulate the collaborative multi-user wireless video transmission problem as a multi-user Markov decision process (MUMDP) by explicitly considering the users heterogeneous video traffic characteristics, time-varying network conditi
ons and the resulting dynamic coupling between the wireless users. These environment dynamics are often ignored in existing multi-user video transmission solutions. To comply with the decentralized nature of wireless networks, we propose to decompose the MUMDP into local MDPs using Lagrangian relaxation. Unlike in conventional multi-user video transmission solutions stemming from the network utility maximization framework, the proposed decomposition enables each wireless user to individually solve its own dynamic cross-layer optimization (i.e. the local MDP) and the network coordinator to update the Lagrangian multipliers (i.e. resource prices) based on not only current, but also future resource needs of all users, such that the long-term video quality of all users is maximized. However, solving the MUMDP requires statistical knowledge of the experienced environment dynamics, which is often unavailable before transmission time. To overcome this obstacle, we then propose a novel online learning algorithm, which allows the wireless users to update their policies in multiple states during one time slot. This is different from conventional learning solutions, which often update one state per time slot. The proposed learning algorithm can significantly improve the learning performance, thereby dramatically improving the video quality experienced by the wireless users over time. Our simulation results demonstrate the efficiency of the proposed MUMDP framework as compared to conventional multi-user video transmission solutions.
In this paper, we propose a general cross-layer optimization framework in which we explicitly consider both the heterogeneous and dynamically changing characteristics of delay-sensitive applications and the underlying time-varying network conditions.
We consider both the independently decodable data units (DUs, e.g. packets) and the interdependent DUs whose dependencies are captured by a directed acyclic graph (DAG). We first formulate the cross-layer design as a non-linear constrained optimization problem by assuming complete knowledge of the application characteristics and the underlying network conditions. The constrained cross-layer optimization is decomposed into several cross-layer optimization subproblems for each DU and two master problems. The proposed decomposition method determines the necessary message exchanges between layers for achieving the optimal cross-layer solution. However, the attributes (e.g. distortion impact, delay deadline etc) of future DUs as well as the network conditions are often unknown in the considered real-time applications. The impact of current cross-layer actions on the future DUs can be characterized by a state-value function in the Markov decision process (MDP) framework. Based on the dynamic programming solution to the MDP, we develop a low-complexity cross-layer optimization algorithm using online learning for each DU transmission. This online algorithm can be implemented in real-time in order to cope with unknown source characteristics, network dynamics and resource constraints. Our numerical results demonstrate the efficiency of the proposed online algorithm.
Cross-layer optimization solutions have been proposed in recent years to improve the performance of network users operating in a time-varying, error-prone wireless environment. However, these solutions often rely on ad-hoc optimization approaches, wh
ich ignore the different environmental dynamics experienced at various layers by a user and violate the layered network architecture of the protocol stack by requiring layers to provide access to their internal protocol parameters to other layers. This paper presents a new theoretic foundation for cross-layer optimization, which allows each layer to make autonomous decisions individually, while maximizing the utility of the wireless user by optimally determining what information needs to be exchanged among layers. Hence, this cross-layer framework does not change the current layered architecture. Specifically, because the wireless user interacts with the environment at various layers of the protocol stack, the cross-layer optimization problem is formulated as a layered Markov decision process (MDP) in which each layer adapts its own protocol parameters and exchanges information (messages) with other layers in order to cooperatively maximize the performance of the wireless user. The message exchange mechanism for determining the optimal cross-layer transmission strategies has been designed for both off-line optimization and on-line dynamic adaptation. We also show that many existing cross-layer optimization algorithms can be formulated as simplified, sub-optima
In this paper, we model the various wireless users in a cognitive radio network as a collection of selfish, autonomous agents that strategically interact in order to acquire the dynamically available spectrum opportunities. Our main focus is on devel
oping solutions for wireless users to successfully compete with each other for the limited and time-varying spectrum opportunities, given the experienced dynamics in the wireless network. We categorize these dynamics into two types: one is the disturbance due to the environment (e.g. wireless channel conditions, source traffic characteristics, etc.) and the other is the impact caused by competing users. To analyze the interactions among users given the environment disturbance, we propose a general stochastic framework for modeling how the competition among users for spectrum opportunities evolves over time. At each stage of the dynamic resource allocation, a central spectrum moderator auctions the available resources and the users strategically bid for the required resources. The joint bid actions affect the resource allocation and hence, the rewards and future strategies of all users. Based on the observed resource allocation and corresponding rewards from previous allocations, we propose a best response learning algorithm that can be deployed by wireless users to improve their bidding policy at each stage. The simulation results show that by deploying the proposed best response learning algorithm, the wireless users can significantly improve their own performance in terms of both the packet loss rate and the incurred cost for the used resources.
