Search

Social cloud systems, which aggregate the computing capabilities of a large pool of users, have emerged in recent years as a key solution for resource provision and sharing in large-scale online communities due to their inherent flexibility and cost-effectiveness. However, the performance and reliability of these systems depend on the users' cooperative behavior in sharing their computing capabilities. Hence, incentive mechanisms are needed to deter users from free-riding. In this paper, we first model the selfish behavior of the users supplying resources and aiming to maximize their own benefits, and compute the performance of the resulting non-cooperative equilibrium, which is highly inefficient. We then augment the existing job allocation schemes currently implemented in social cloud systems with a novel class of incentive mechanisms based on reputation-based pricing and collective punishment schemes that compel suppliers to change their selfish strategies in a manner that improves the efficiency of the system. We study the cloud system operator's problem of jointly optimizing the incentive mechanism and the job allocation scheme in order to find an optimal social cloud protocol which eliminates the free-riding behavior of suppliers while maximizing the social welfare of the system. We rigorously prove that, using only simple designs for both the incentive mechanism and the job allocation scheme, the resulting protocol provides significant improvements in terms of the social welfare compared to existing social cloud systems.

Most congestion control schemes are based on user cooperation, i.e., they implicitly assume that users are willing to share their private information and to take actions such that the network operates efficiently. However, a self-interested and strategic user might exploit such schemes to obtain an individual gain at the expenses of the other users, misrepresenting its private information and overusing the resources. We first quantify the inefficiency of the network in the presence of selfish users for two different scenario: in the complete information case - in which the users have no private information - and in the incomplete information case - in which the users have private information. Then, we ask whether the congestion control scheme can be designed to be robust to self-interested strategic users. To reach this objective, we use an intervention scheme. For the complete information scenario we describe a scheme that is able to give the users an incentive to optimally use the resources. For the incomplete information scenario we describe two schemes that provide the users with an incentive to report truthfully and to use the resources efficiently, although not always optimally. Illustrative results show that the considered schemes can considerably improve the efficiency of the network.

Electric vehicles (EVs) will play an important role in the future smart grid because of their capabilities of storing electrical energy in their batteries during off-peak hours and supplying the stored energy to the power grid during peak hours. In this paper, we consider a power system with an aggregator and multiple customers with EVs and propose novel electricity load scheduling algorithms which, unlike previous works, jointly consider the load scheduling for appliances and the energy trading using EVs. Specifically, we allow customers to determine how much energy to purchase from or to sell to the aggregator while taking into consideration the load demands of their residential appliances and the associated electricity bill. We propose two different approaches: a collaborative and a non-collaborative approach. In the collaborative approach, we develop an optimal distributed load scheduling algorithm that maximizes the social welfare of the power system. In the non-collaborative approach, we model the energy scheduling problem as a non-cooperative game among self-interested customers, where each customer determines its own load scheduling and energy trading to maximize its own profit. In order to resolve the unfairness between heavy and light customers in the non-collaborative approach, we propose a tiered billing scheme that can control the electricity rates for customers according to their different energy consumption levels. In both approaches, we also consider the uncertainty in the load demands, with which customers' actual energy consumption may vary from the scheduled energy consumption. To study the impact of the uncertainty, we use the worst-case-uncertainty approach and develop distributed load scheduling algorithms that provide the guaranteed minimum performances in uncertain environments. Subsequently, we show when energy trading leads to an increase in the social welfare and we determine what are the customers' incentives to participate in the energy trading in various usage scenarios including practical environments with uncertain load demands.

Real-time stream mining such as surveillance and personal health monitoring, which involves sophisticated mathematical operations, is computation-intensive and prohibitive for mobile devices due to the hardware/computation constraints. To satisfy the growing demand for stream mining in mobile networks, we propose to employ a cloud-based stream mining system in which the mobile devices send via wireless links unclassified media streams to the cloud for classification. We aim at minimizing the classification-energy cost, defined as an affine combination of classification cost and energy consumption at the cloud, subject to an average stream mining delay constraint (which is important in real-time applications). To address the challenge of time-varying wireless channel conditions without a priori information about the channel statistics, we develop an online algorithm in which the cloud operator can dynamically adjust its resource provisioning on the fly and the mobile devices can adapt their transmission rates to the instantaneous channel conditions. It is proved that, at the expense of increasing the average stream mining delay, the online algorithm achieves a classification-energy cost that can be pushed arbitrarily close to the minimum cost achieved by the optimal offline algorithm. Extensive simulations are conducted to validate the analysis.

This paper presents the first study of the endogenous formation of networks by strategic, self-interested agents who benefit from producing and disseminating information. This work departs from previous works on network formation (especially in the economics literature) which assume that agents benefit only by acquiring information produced by other agents. The strategic production and dissemination of information have striking consequences. We show first that the network structure that emerges (in equilibrium) typically displays a core-periphery structure, with the few agents at the core playing the role of eeconnectorsee, creating and maintaining links to the agents at the periphery. We then determine conditions under which the networks that emerge are minimally connected and have short network diameters (properties that are important for efficiency). Finally, we show that the number of agents who produce information and the total amount of information produced in the network grow at the same rate as the agent population; this is in stark contrast to the "law of the few" that had been established in previous works which do not consider information dissemination.

We consider the problem of energy-efficient point-to-point transmission of delay-sensitive data (e.g., multimedia data) over a fading channel. Existing research on this topic utilizes either physical-layer centric solutions, namely power-control and adaptive modulation and coding (AMC), or system-level solutions based on dynamic power management (DPM); however, there is currently no rigorous and unified framework for simultaneously utilizing both physical-layer centric and system-level techniques to achieve the minimum possible energy consumption, under delay constraints, in the presence of stochastic and a priori unknown traffic and channel conditions. In this paper, we propose such a framework. We formulate the stochastic optimization problem as a Markov decision process (MDP) and solve it online using reinforcement learning (RL). The advantages of the proposed online method are that 1) it does not require a priori knowledge of the traffic arrival and channel statistics to determine the jointly optimal power-control, AMC, and DPM policies; 2) it exploits partial information about the system so that less information needs to be learned than when using conventional reinforcement learning algorithms; and 3) it obviates the need for action exploration, which severely limits the adaptation speed and runtime performance of conventional reinforcement learning algorithms. Our results show that the proposed learning algorithms can converge up to two orders of magnitude faster than a state-of-the-art learning algorithm for physical layer power-control and up to three orders of magnitude faster than conventional reinforcement learning algorithms.

The increase of Internet application requirements, such as throughput and delay, has spurred the need for transport protocols with flexible transmission control. Current TCP congestion control adopts an Additive Increase Multiplicative Decrease (AIMD) algorithm that linearly increases or exponentially decreases the congestion window based on transmission acknowledgments. In this paper, we propose an AIMD-like media-aware congestion control that determines the optimal congestion window updating policy for multimedia transmission. The media-aware congestion control problem is formulated as a Partially Observable Markov Decision Process (POMDP), which maximizes the long-term expected quality of the received multimedia application. The solution of this POMDP problem gives a policy adapted to multimedia applications' characteristics (i.e., distortion impacts and delay deadlines of multimedia packets). Note that to obtain the optimal congestion policy, the sender requires the complete statistical knowledge of both multimedia traffic and the network environment, which may not be available in practice. Hence, an online reinforcement learning in the POMDP-based solution provides a powerful tool to accurately estimate the environment and to adapt the source to network variations on the fly. Simulation results show that the proposed online learning approach can significantly improve the received video quality while maintaining the responsiveness and TCP-friendliness of the congestion control in various network scenarios.

Online television (TV) market has been expanding rapidly over the last few years and provided TV studios with a cost-effective and reliable channel for the delivery of high-quality TV content. To maximize profit by setting up an online TV content platform, two major challenges are faced by the platform owner: what is the optimal investment (e.g., how many hosting servers, bandwidth acquisition) and how to price TV content producers who utilize the platform as a channel to distribute their content. To address these two challenges, we first derive the optimal pricing policy based on the widely-adopted “pay-per-usage” model, and then formalize and solve the optimal investment decision problem. Rationality of self-interested TV content producers and audiences is also taken into account. Specifically, we first use a model with a representative content viewer to determine how many times a TV content with a certain quality is watched. Then, by modeling the content providers as self-interested agents making independent production decisions, we show that for any price charged by the platform, there always exists a unique equilibrium in the content production stage, which makes it possible for the platform owner to maximize its profit without uncertainties because of the unique outcome in the content producers' decision stage. Finally, we develop an algorithm to derive the optimal price and then formalize the investment decision problem to maximize the platform's profit.

We propose a BitTorrent-like protocol based on an online learning (reinforcement learning) mechanism, which can replace the peer selection mechanisms in the regular BitTorrent protocol. We model the peers' interactions in the BitTorrent-like network as a repeated stochastic game, where the strategic behaviors of the peers are explicitly considered. A peer that applies the reinforcement learning (RL)-based mechanism uses the observations on the associated peers' statistical reciprocal behaviors to determine its best responses and estimate the corresponding impact on its expected utility. The policy determines the peer's resource reciprocations such that the peer can maximize its long-term performance. We have implemented the proposed mechanism and incorporated it into an existing BitTorrent client. Our experiments performed on a controlled Planetlab testbed confirm that the proposed protocol 1) promotes fairness and provides incentives to contributed resources, i.e., high capacity peers improve their download completion time by up to 33 percent, 2) improves the system stability and robustness, i.e., reduces the peer selection fluctuations by 57 percent, and (3) discourages free-riding, i.e., peers reduce their uploads to free-riders by 64 percent as compared to the regular BitTorrent protocol.

Social computing provide a popular, cost-effective and scalable framework for building new engineering systems as well as improving the performance of numerous existing systems. However, the self-interest of agents of such systems generates intrinsic incentive problems. This work analyzes these incentive problems from several points of view. First, we analyze the trade-offs (of each individual agent) between the costs and benefits of producing information personally and forming links to collect information (from other agents), and the strategic implications of these trade-offs. A central point of the analysis is that information is assumed to be heterogeneous (rather than homogeneous as in previous analyses) and agents value this heterogeneity. The analysis has implications for the topology that emerges endogenously. For large populations, the implication is that the topology is necessarily of a core-periphery type: hub agents (at the core of the network) produce and share most of the information, while spoke agents (at the periphery of the network) derive most of their information from hub agents, producing little of it themselves. As the population becomes larger, the number of hub agents and the total amount of information produced grow in proportion to the total population. Our conclusions had been conjectured for many social computing systems but not been previously derived in any formal framework, and are in stark contradiction to the "law of the few" that had been established in previous work, under the assumption that information is homogeneous and part of the endowment of agents, rather than heterogeneous and produced.

In this work, we propose a method to reduce the impact of process variations by adapting the application's algorithm at the software layer. We introduce the concept of hardware signatures as the measured post manufacturing hardware characteristics that can be used to drive software adaptation across different die. Using H.264 encoding as an example, we demonstrate significant yield improvements (as much as 30% points at 0% hardware overdesign), a reduction in overdesign (by as much as 8% points at 80% yield) as well as application quality improvements (about 2.0 dB increase in average peak-signal-to-noise ratio at 70% yield). Further, we investigate implications of limited information exchange (i.e., signature quantization) on yield and quality. We conclude that hardware-signature-based application adaptation is an easy and inexpensive (to implement), better informed (by actual application requirements) and effective way to manage yield-cost-quality tradeoffs in application-implementation design flows.

In communication systems where users share common resources, users' selfish behavior usually results in suboptimal resource utilization. There have been extensive works that model communication systems with selfish users as one-shot games and propose incentive schemes to achieve Pareto optimal action profiles as non-cooperative equilibria. However, in many communication systems, due to strong negative externalities among users, the sets of feasible payoffs in one-shot games are nonconvex. Thus, it is possible to expand the set of feasible payoffs by having users choose convex combinations of different payoffs. In this paper, we propose a repeated game model generalized by intervention. First, we use repeated games to convexify the set of feasible payoffs in one-shot games. Second, we combine conventional repeated games with intervention, originally proposed for one-shot games, to achieve a larger set of equilibrium payoffs and loosen requirements for users' patience to achieve it. We study the problem of maximizing a welfare function defined on users' equilibrium payoffs, subject to minimum payoff guarantees. Given the optimal equilibrium payoff, we derive the minimum intervention capability required and design corresponding equilibrium strategies. The proposed generalized repeated game model applies to various communication systems, such as power control and flow control., 42 pages, 7 figures, 2 tables

Nowadays, multimedia applications and specifically streaming systems over wireless networks use the TCP transport protocol. Indeed, TCP can deal with practical issues such as firewalls and also deploys built-in retransmissions and congestion control mechanisms. We propose in this paper a Quality-centric Mean Opinion Score (MOS) based congestion control that determines an optimal congestion window updating policy for multimedia transmission. Unlike the standard congestion control algorithms, our approach defines a new Additive Increase Multiplicative Decrease (AIMD) algorithm given the multimedia application and the transmission characteristics. In order to get the optimal congestion policy in practice, the sender requires complete statistical knowledge of both multimedia traffic and the network environment, which may not be available in wireless systems. Hence, we propose in this paper, a Partially Observable Markov Decision Process (POMDP) framework in order to determine an optimal congestion control policy which maximizes the long term expected Quality of Experience (QoE) of the receiver. Moreover, the computation of an optimal policy is usually time/process consuming and as wireless devices are capacity-limited, we consider optimal solutions based on temporal difference (TD-λ) online learning algorithms. Finally, we do some practical experiments of our algorithm on a Microsoft Lync testbed with unidirectional and bidirectional communications over a wireless network. We observe that for both scenarios, our algorithm improves significantly the QoE compared to standard AIMD congestion control mechanism.

In this paper, we propose a quality-centric congestion control for multimedia streaming over wired IP networks, which we refer to as media-TCP-friendly congestion control (MTCC). Our solution adapts the sending rate to both the network condition and the application characteristics by explicitly considering the distortion impacts, delay deadlines, and interdependencies of different video packet classes. The media-aware solution is able to provide differential services for transmitting various packet classes and thereby, further improves the multimedia streaming quality compared to the conventional network-aware congestion control. We use finite-horizon Markov decision process (FHMDP) to determine the optimal congestion control policy that maximizes the long-term multimedia quality, while adhering to the horizon-K TCP-friendliness constraint, which ensures long-term fairness with existing TCP applications. Moreover, the proposed MTCC is able to achieve quality-based fairness among multimedia users. We derive sufficient conditions for multiple multimedia users to achieve quality-based fairness using MTCC congestion control. Note that the proposed solution only modifies the adaptation mechanism of the TCP congestion window size at the sender, without changing the design at the receiver side (i.e., each current TCP receiver can correctly receive and process MTCC streams). Our simulation results show that MTCC achieves more than 3 dB improvement in terms of PSNR over the conventional TCP congestion control approaches, with the largest improvements observed for real-time streaming applications requiring stringent playback delays.

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 that explicitly considers the users' heterogeneous multimedia data characteristics (e.g., delay deadlines, distortion impacts and dependences, and so on) 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. This priority graph provides us with an elegant structure to decompose the multidata 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 focus on the users' aggregate data demand dynamics in a wireless communications market served by a monopolistic wireless service provider (WSP). Based on the equilibrium data demand, we optimize the WSP's data plans and long-term network capacity decisions to maximize its profit. First, by considering a market where only one data plan is offered, we show that there exists a unique equilibrium in the data demand dynamics regardless of the data plans, and that the convergence of data demand dynamics is subject to the network congestion cost, which is closely related to the WSP's long-term capacity decision. A sufficient condition on the network congestion cost indicates that the WSP needs to provide a sufficiently large network capacity to guarantee the convergence of data demand dynamics. We also propose a heuristic algorithm that progressively optimizes the WSP's data plan to maximize its equilibrium revenue. Next, we turn to a market where two different data plans are offered. It is shown that the existence of a unique equilibrium data demand depends on the data plans, and the convergence of data demand dynamics is still subject to the network congestion cost (and hence, the WSP's network capacity, too). We formalize the problem of optimizing the WSP's data plans and network capacities to maximize its profit. Finally, we discuss the scenario in which the data plans are offered by two competing WSPs and conduct extensive simulations to validate our analysis.

Delay-sensitive video transmission over IEEE 802.11 wireless local area networks (WLANs) is analyzed in a cross-layer optimization framework. The effect of delay constraint on the quality of received packets is studied by analyzing “expired-time packet discard rate”. Three analytical models are examined and it is shown that M/M/1 model is quite an adequate model for analyzing delay-limited applications such as live video transmission over WLAN. The optimal MAC retry limit corresponding to the minimum “total packet loss rate” is derived by exploiting both mathematical analysis and NS-2 simulations. We have shown that there is an interaction between "packet overflow drop" and "expired-time packet discard" processes in the queue. Subsequently, by introducing the concept of virtual buffer size, we will obtain the optimal buffer size in order to avoid "packet overflow drop". We finally introduced a simple and yet effective real-time algorithm for retry-limit adaptation over IEEE 802.11 MAC in order to maintain a loss protection for delay-critical video traffic transmission, and showed that the average link-layer throughput can be improved by using our adaptive scheme.

Some users of a communications network may have more information about traffic on the network than others do-and this fact may be secret. Such secret information would allow the possessor to tailor its own traffic to the traffic of others; this would help the secret information possessor or informed user and (might) harm other uninformed users. To quantitatively study the impact of secret information, we formulate a flow control game with incomplete information where users choose their flows in order to maximize their (expected) utilities given the distribution of the actions of others. In this environment, the natural baseline notion is Bayesian Nash Equilibrium (BNE); we establish the existence of BNE. Next, we assume that there is a user who knows the realized congestion created by other users, but that the presence of this informed user is not known by other uninformed users; thus, the informed user has secret information. For this environment, we define a new equilibrium concept: the Bayesian Nash Equilibrium with Secret Information (BNE-SI) and establish its existence. We establish rigorous estimates for the benefit (to the informed user) and harm (to the uninformed users) that result from secret information; both the benefit and the harm become smaller for large networks. Interestingly, simulations demonstrate that secret information may in fact benefit all users. Secret information may also harm uninformed users in particular scenarios. This analysis can be used as a starting point for securing communications networks, both from the network manager and the user's perspectives.

In this paper, we consider a wireless amplify-and-forward relay network with one relay node and multiple source-destination pairs/users and propose a pricing framework that enables the relay to set prices to maximize either its revenue or any desirable system utility. Specifically, depending on the quality of the received signals, the relay sets prices and correspondingly charges the users utilizing its resources for their transmissions. The price is determined in such a way that the relay's revenue or system utility is maximized. Given the specified price, the users competitively employ the relay node to forward their signals. We model each user as a rational player, which aims at maximizing its own net utility through power allocation, and analyze the competition among the users within the framework of noncooperative game theory. It is shown that, in the game played by the users, there always exists a unique pure Nash equilibrium point that can be achieved through distributed iterations. Next, subject to the availability of complete information about the users at the relay, we propose a low-complexity uniform pricing algorithm and an optimal differentiated pricing algorithm, in which the relay either charges the users at a suboptimal uniform price or charges different users at different prices. We also show that, by applying the differentiated pricing algorithm that enforces the users to transmit at certain power levels, any system utility can be maximized. Extensive simulations are conducted to quantify the performance of the proposed methods.

We consider wireless communication networks where network users are subject to critical events such as emergencies and crises. If a critical event occurs to a user, the user needs to send critical traffic as early as possible. However, most existing medium access control (MAC) protocols are not adequate to meet the urgent need for data transmission by users with critical traffic. In this paper, we devise a class of distributed MAC protocols that achieve coordination using the finite-length memory of users containing their own observations and traffic types. We formulate a protocol design problem and find optimal protocols that solve the problem. We show that the proposed protocols enable a user with critical traffic to transmit its critical traffic without interruption from other users after a short delay while allowing users to share the channel efficiently when there is no critical traffic. Moreover, the proposed protocols require short memory and can be implemented without explicit message passing., 24 pages, 7 figures, 1 table

Multimedia stream mining applications require the identification of several different attributes in data content, and hence rely on a set of cascaded statistical classifiers to filter and process the data dynamically. In this paper, we introduce a novel methodology for configuring such cascaded classifier topologies, specifically binary classifier trees, in resource-constrained, distributed stream mining systems. Instead of traditional load shedding, our approach configures classifiers with optimized operating points after jointly considering the misclassification cost of each end-to-end class of interest in the tree, the resource constraints for every classifier, and the confidence level of each data object that is classified. The proposed approach allows for both intelligent load shedding as well as data replication based on available resources dynamically. We evaluate the algorithm on a sports video concept detection application and identify huge cost savings over load shedding alone. Additionally, we propose several distributed algorithms that enable each classifier in the tree to reconfigure itself based on local information exchange. We analyze the associated tradeoffs between convergence time, information overhead, and the cost efficiency of results achieved by each classifier for each of these algorithms.

Multi-hop wireless networks can provide flexible network infrastructures at a low cost. However, most existing wireless networking solutions are designed for delay-insensitive applications, thereby resulting in poor performance when handling delay-sensitive applications. Traditionally, network design problems are formulated as static optimizations, by assuming the network characteristics remain static. However, these solutions are not optimal when the environments are dynamic. Recently, several research works apply machine learning to maximize the performance of multi-hop wireless networks in dynamic environments, but they either only focus on determining policies at the network layer, without considering the lower-layers' actions, or use centralized learning approaches, which are inefficient for delay-sensitive applications, due to the large delay when propagating messages throughout the network. We propose in this paper a new solution that enables the nodes to autonomously determine their routing and transmission power to maximize the network utility, in a dynamic environment. We formulate the problem as a Markov Decision Process, and propose a distributed computation of the optimal policy. Moreover, we use reinforcement-learning to find the optimized policy when the dynamics are unknown. We explicitly consider the impact of the information overhead on the network performance, and propose several novel algorithms to reduce the information overhead.

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 conditions 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., Comment: 36 pages, 13 figures

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., Comment: 30 pages, 10 figures

In this paper, we consider the resource reciprocation among self-interested peers in peer-to-peer (P2P) networks, which is modeled as a stochastic game. Peers play the game by determining their optimal strategies for resource distributions using a Markov decision process (MDP) framework. The optimal strategies enable the peers to maximize their long-term utility. Unlike in conventional MDP frameworks, we consider heterogeneous peers that have different and limited ability to characterize their resource reciprocation with other peers. This is due to the large complexity requirements associated with their decision making processes. We analytically investigate these tradeoffs and show how to determine the optimal number of state descriptions, which maximizes each peer's average cumulative download rates given a limited time for computing the optimal strategies. We also investigate how the resource reciprocation evolves over time as peers adapt their reciprocation strategies by changing the number of state descriptions. Then, we study how resulting download rates affect their performance as well as that of the other peers with which they interact. Our simulation results quantify the tradeoffs between the number of state descriptions and the resulting utility. We also show that evolving resource reciprocation can improve the performance of peers which are simultaneously refining their state descriptions.

Recent research in wireless multimedia streaming has focused on optimizing the multimedia quality in isolation, at each station. However, the cross-layer transmission strategy deployed at one station impacts and is impacted by the other stations, as the wireless network resource is shared among all competing users. Hence, efficient and fair resource management for autonomous wireless multimedia users becomes very important. We consider quality-based fairness schemes based on axiomatic bargaining theory, which can ensure that the autonomous multimedia stations incur the same drop in multimedia quality as compared to a maximum achievable quality for each wireless station. Implementing this quality-based fairness solution in the time-varying channel condition requires high-computational complexity and communication overheads. Hence, we develop solutions that significantly reduce the computational complexity and communication overheads. Our simulations show that the proposed game-theoretic resource management can indeed guarantee desired utility-fair allocations when wireless stations deploy different cross-layer strategies.

In this paper, we assume that the network resources are managed by several brokers, which are endowed with resources by a (remote) central resource manager according to several predetermined policies. Our focus is on autonomous multimedia users. We propose a novel resource management scheme, where resource brokers choose well-suited axiomatic bargaining solutions to divide their allocated resources among the users associated with them. These resource division solutions enable resource brokers to provide strict minimum video quality guarantees according to the (varying) number of multimedia users associated with them. Finally, we show that the proposed solution enables us to model the problem of selecting resource brokers by multimedia users as an unweighted congestion game, thereby ensuring convergence to a stationary distribution of users across resource brokers. We investigate the number of required users' switches to reach the stationary distribution, and quantify the fairness of the stationary distribution by introducing a novel quality fairness comparison metric for the users.

This paper considers a noncooperative game in which competing users sharing a frequency-selective interference channel selfishly optimize their power allocation in order to improve their achievable rates. Previously, it was shown that a user having the knowledge of its opponents' channel state information can make foresighted decisions and substantially improve its performance compared with the case in which it deploys the conventional iterative water-filling algorithm, which does not exploit such knowledge. This paper discusses how a foresighted user can acquire this knowledge by modeling its experienced interference as a function of its own power allocation. To characterize the outcome of the multiuser interaction, the conjectural equilibrium is introduced, and the existence of this equilibrium for the investigated water-filling game is proven. Importantly, we show that both the Nash equilibrium and the Stackelberg equilibrium are special cases of the conjectural equilibrium. We also develop practical algorithms to form accurate beliefs and select desirable power allocation strategies. Numerical simulations indicate that a foresighted user without any a priori knowledge of its competitors' private information can effectively learn how the other users will respond to its actions, and induce the entire system to an operating point that improves both its own achievable rate as well as the rates of the other participants in the water-filling game.

An increasing number of networked and battery-powered devices require the simultaneous processing of multiple high-complexity dynamic multimedia tasks. Existing resource allocation solutions include both centralized approaches and distributed approaches. Centralized approaches typically have two fundamental limitations. First, multimedia algorithms typically have a large number of operating points and thus requires high implementation complexity to optimally allocate resources across multiple applications, making centralized solutions unsuitable for dynamic environments. Second, autonomous multimedia applications may not be willing to reveal information about their private utility functions, since such information can be exploited by other selfish applications to gain an unfair performance advantage by strategically misusing the system resources. On the other hand, existing decentralized solutions typically solve only resource-constrained utility maximization problems, without regard to other system platform-dependent costs and objectives, and without considering application dynamics. To address these limitations, we present in this paper a decentralized low-complexity resource management solution that can optimize a variety of system performance objectives without requiring applications to provide their utilities. We demonstrate analytically and experimentally that our algorithms converge quickly to their respective optimal solutions and are thus practical in dynamic environments.

In this letter, we consider peer-to-peer (P2P) networks, where multiple peers are interested in sharing their content. In the considered P2P system, autonomous and self-interested peers use a Markov Decision Process (MDP) framework to determine their upload bandwidth allocations, which maximize their individual utilities. This framework enables the peers to make foresighted decisions on their bandwidth allocations, by considering the future impact of their decisions. In this letter, we focus on the impact of the peers’ bounded rationality on their resource reciprocation strategies and ultimately, on their achievable utilities. Specifically, we consider peers who have only a limited ability to model the other peers' strategies for resource reciprocation, and study how this impacts their own decisions.

Video decoding complexity modeling and prediction is an increasingly important issue for efficient resource utilization in a variety of applications, including task scheduling, receiver-driven complexity shaping, and adaptive dynamic voltage scaling. In this paper we present a novel view of this problem based on a statistical framework perspective. We explore the statistical structure (clustering) of the execution time required by each video decoder module (entropy decoding, motion compensation, etc.) in conjunction with complexity features that are easily extractable at encoding time (representing the properties of each module's input source data). For this purpose, we employ Gaussian mixture models (GMMs) and an expectation-maximization algorithm to estimate the joint execution-time-feature probability density function (PDF). A training set of typical video sequences is used for this purpose in an offline estimation process. The obtained GMM representation is used in conjunction with the complexity features of new video sequences to predict the execution time required for the decoding of these sequences. Several prediction approaches are discussed and compared. The potential mismatch between the training set and new video content is addressed by adaptive online joint-PDF re-estimation. An experimental comparison is performed to evaluate the different approaches and compare the proposed prediction scheme with related resource prediction schemes from the literature. The usefulness of the proposed complexity-prediction approaches is demonstrated in an application of rate-distortion-complexity optimized decoding.

Designing efficient and fair solutions for dividing the network resources in a distributed manner among self-interested multimedia users is recently becoming an important research topic because heterogeneous and high bandwidth multimedia applications (users), having different quality-of-service requirements, are sharing the same network. Suitable resource negotiation solutions need to explicitly consider the amount of information exchanged among the users and the computational complexity incurred by the users. In this paper, we propose decentralized solutions for resource negotiation, where multiple autonomous users self-organize into a coalition which shares the same network resources and negotiate the division of these resources by exchanging information about their requirements. We then discuss various resource sharing strategies that the users can deploy based on their exchanged information. Several of these strategies are designed to explicitly consider the utility (i.e., video quality) impact of multimedia applications. In order to quantify the utility benefit derived by exchanging different information, we define a new metric, which we refer to as the value of information. We quantify through simulations the improvements that can be achieved when various information is exchanged between users, and discuss the required complexity at the user side involved in implementing the various resource negotiation strategies.

Cross-layer optimization solutions have been proposed in recent years to improve the performance of wireless users that operate in a time-varying, error-prone network environment. However, these solutions often rely on centralized cross-layer optimization solutions that 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 systematic framework for cross-layer optimization, which allows each layer to make autonomous decisions to maximize the wireless user's utility by optimally determining what information should be exchanged among layers. Hence, this cross-layer framework preserves the current layered network architecture. Since the user interacts with the wireless environment at various layers of the protocol stack, the cross-layer optimization problem is solved in a layered fashion such that each layer adapts its own protocol parameters and exchanges information (messages) with other layers that cooperatively maximize the performance of the wireless user. Based on the proposed layered framework, we also design a message-exchange mechanism that determines the optimal cross-layer transmission strategies, given the user's experienced environment dynamics.

In recent years, cross-layer multimedia system design and optimization has garnered significant attention; however, there exists no rigorous methodology for optimizing two or more system layers (e.g., the application, operating system, and hardware layers) jointly while maintaining a separation among the decision processes, designs, and implementations of each layer. Moreover, existing work often relies on myopic optimizations, which ignore the impact of decisions made at the current time on the system's future performance. In this paper, we propose a novel systematic framework for jointly optimizing the different system layers to improve the performance of one multimedia application. In particular, we model the system as a layered Markov decision process (MDP). The proposed layered MDP framework enables each layer to make autonomous and foresighted decisions, which optimize the system's long-term performance.

We propose a novel cross layer solution for optimizing the performance of multiple users, which are concurrently transmitting their delay-sensitive video streams over the same shared contention-based wireless LAN. To improve the performance of their applications, they dynamically adapt their medium access control (MAC) strategies (i.e., retry limits). Higher retry limits will benefit the user, but they will also lead to an increased congestion for the other users. Hence, we explicitly consider how the cross layer strategy adopted by one video user will impact the strategies of the competing users. Specifically, we analytically model how the cross layer transmission strategies adopted by each wireless user impact their own incurred distortion and delay but also that of their competing wireless stations. We also propose a distributed, low-complexity, and highly scalable optimization algorithm which can maximize the utility of the delay-sensitive video application. We compare our scheme to existing retry limit-based solutions, and the simulation results show that the proposed solution can outperform these solutions and maximize the users' utilities in a highly congested multiuser wireless environment.

In this letter, we consider a simple two-user channel access game and investigate how to improve the performance of Nash equilibrium (NE) by employing a correlated device that coordinates the users' actions and leads them to play a higher efficiency correlated equilibrium (CE). Unlike existing papers, we discuss both the public and private CEs and quantify their performances in various simple, but illustrative scenarios. Moreover, we propose a simple procedure for the correlated device to select the CE leading to the highest payoff, without the need for the users to report their private utility functions.

We consider peer-to-peer (P2P) networks, where multiple peers are interested in sharing multimedia content. In such P2P networks, the shared resources are the peers' contributed content and their upload bandwidth. While sharing resources, autonomous and self-interested peers need to make decisions on the amount of their resource reciprocation (i.e., representing their actions) such that their individual utilities are maximized. We model the resource reciprocation among the peers as a stochastic game and show how the peers can determine optimal strategies for resource reciprocation using a Markov Decision Process (MDP) framework. Unlike existing resource reciprocation strategies, which focus on myopic decisions of peers, the optimal strategies determined based on MDP enable the peers to make foresighted decisions about resource reciprocation, such that they can explicitly consider both their immediate as well as future expected utilities. To successfully formulate the MDP framework, we propose a novel algorithm that identifies the state transition probabilities using representative resource reciprocation models of peers. These models express the peers' different attitudes toward resource reciprocation. We analytically investigate how the error between the true and estimated state transition probability impacts each peer's decisions for selecting its actions as well as the resulting utilities. Moreover, we also analytically study how bounded rationality (e.g., limited memory for reciprocation history and the limited number of state descriptions) can impact the interactions among the peers and the resulting resource reciprocation. Simulation results show that the proposed approach based on reciprocation models can effectively cope with a dynamically changing environment such as peers' joining or leaving P2P networks. Moreover, we show that the proposed foresighted decisions lead to the best performance in terms of the cumulative expected utilities.

In this paper, we study the system-level computational resource allocation problem among multiple multimedia tasks. We consider the multimedia tasks to be autonomous, i.e., they are selfish and behave strategically. We propose a resource allocation framework based on mechanism design to prevent the tasks from behaving strategically and manipulating the available system resources. We apply two mechanisms in the framework and assess their advantages over proportional-share resource allocation algorithms, which are often used in multimedia systems. We show in the simulations that the incorporation of mechanism design for system resource allocation is a promising solution that achieves efficient, fair and robust allocation against manipulation from strategic applications.

In this paper, we consider a peer-to-peer (P2P) network, where multimedia streams are broadcast by matched peers based on their resource reciprocation profiles. We propose a new framework where each peer creates a coalition of matched peers with which it can exchange resources in order to improve its utility. The utility is determined based on explicit consideration of the peer's multimedia attributes and the quality derived by the peers' reciprocation behavior. We adopt the proportional bargaining solution to negotiate the upload bandwidth among the matched peers. Proportional bargaining allows to determine each peer's optimal (in a Pareto optimal sense) upload rates in a coalition in terms of its utility impact. The impact of an incoming peer on the coalition value, which represents the collective utility achieved by the peers in a coalition, is assessed by explicitly investigating the coalition value improvement. Finally, our results show that the proposed coalition-based resource reciprocation can improve the resource allocation/scheduling algorithms deployed in existing P2P systems such as BitTorrent and CoolStreaming. We also discuss how the proposed resource reciprocation approach can be implemented in other multimedia broadcasting applications.

The objective of dynamic voltage scaling (DVS) is to adapt the frequency and voltage for configurable platforms to obtain energy savings. DVS is especially attractive for video decoding systems due to their time-varying and highly complex workload and because the utility of decoding a frame is solely depending on the frame being decoded before its display deadline. Several DVS algorithms have been proposed for multimedia applications. However, the prior work did not take into account the video compression algorithm specifics, such as considering the temporal dependencies among frames and the required display buffer. Moreover, the effect of the passive (leakage) power when performing DVS for multimedia systems was not explicitly considered. In this paper, we determine the optimal scheduling of the active and passive states to minimize the total energy for video decoding systems. We pose our problem as a buffer-constrained optimization problem with a novel, compression-aware definition of processing jobs. We propose low-complexity algorithms to solve the optimization problem and show through simulations that significant improvements can be achieved over state-of-the art DVS algorithms that aim to minimize only the active power.

We study the problem of optimal resource allocation for multi-user multiaccess wireless video communication from an information-theoretic point of view. We derive the optimal resource allocation policies by directly maximizing at the application layer the weighted sum of video qualities of all users, subject to information-theoretic multiaccess capacity region constraints in the MAC-PHY layers. We solve this problem for three multiaccess capacity regions: (1) non-fading channel, (2) fading channel with a given power control policy, and (3) fading channel with dynamic power control policies. The optimal resource allocation policy is referred as largest quality improvement highest possible rate (LQIHPR). We propose simple greedy algorithms to implement this policy. Since the capacity region is the fundamental characterization of achievable rates, the solutions developed in this paper provide the operational upper bound of achievable video quality in a multiaccess fading channel.

In this paper, we propose a dynamic channel-selection solution for autonomous wireless users transmitting delay-sensitive multimedia applications over cognitive radio networks. Unlike prior works that seldom consider the requirement of the application layer, our solution explicitly considers various rate requirements and delay deadlines of heterogeneous multimedia users. Note that the users usually possess private utility functions, application requirements, and distinct channel conditions in different frequency channels. To efficiently manage available spectrum resources in a decentralized manner, information exchange among users is necessary. Hence, we propose a novel priority virtual queue interface that determines the required information exchanges and evaluates the expected delays experienced by various priority traffics. Such expected delays are important for multimedia users due to their delay-sensitivity nature. Based on the exchanged information, the interface evaluates the expected delays using priority queuing analysis that considers the wireless environment, traffic characteristics, and the competing users' behaviors in the same frequency channel. We propose a dynamic strategy learning (DSL) algorithm deployed at each user that exploits the expected delay and dynamically adapts the channel selection strategies to maximize the user's utility function. We simulate multiple video users sharing the cognitive radio network and show that our proposed solution significantly reduces the packet loss rate and outperforms the conventional single-channel dynamic resource allocation by almost 2 dB in terms of video quality.

In this paper, we propose a new resource allocation framework for multimedia systems that perform multiple simultaneous video decoding tasks. We jointly consider the available system resources (e.g., processor cycles) and the video decoding task's characteristics such as the sequence's content, the bit-rate, and the group of pictures (GOP) structure, in order to determine a fair and optimal resource allocation. To this end, we derive a quality-complexity model that determines the quality [in terms of peak signal-to-noise ratio (PSNR)] that a task can achieve given a certain system resource allocation. We use these quality-complexity models to determine a quality-fair and Pareto-optimal resource allocation using the Kalai-Smorodinski Bargaining Solution (KSBS) from axiomatic bargaining theory. The KSBS explicitly considers the resulting multimedia quality when performing a resource allocation and distributes quality-domain penalties proportional to the difference between each video decoding task's maximum and minimum quality requirements. We compare the KSBS with other fairness policies in the literature and find that, because it explicitly considers multimedia quality, it provides significantly fairer resource allocations in terms of the resulting PSNR compared with policies that operate solely in the resource domain. To weight the quality impact of the resource allocations to the different decoding tasks depending on application-specific requirements or user preferences, we generalize the existing KSBS solution by introducing bargaining powers based on each video sequence's motion and texture characteristics.

Analytical modeling of the performance of video coders is essential in a variety of applications, such as power-constrained processing, complexity-driven video streaming, etc., where information concerning rate, distortion, or complexity (and their interrelation) is required. In this paper, we present a novel rate-distortion-complexity (R-D-C) analysis for state-of-the-art wavelet video coding methods by explicitly modeling several aspects found in operational coders, i.e., embedded quantization, quadtree decompositions of block significance maps and context-adaptive entropy coding of subband blocks. This paper achieves two main goals. First, unlike existing R-D models for wavelet video coders, the proposed derivations reveal for the first time the expected coding behavior of specific coding algorithms (e.g., quadtree decompositions, coefficient significance, and refinement coding) and, therefore, can be used for a variety of coding mechanisms incorporating some or all the coding algorithms discussed. Second, the proposed modeling derives for the first time analytical estimates of the expected number of operations (complexity) of a broad class of wavelet video coding algorithms based on stochastic source models, the coding algorithm characteristics and the system parameters. This enables the formulation of an analytical model characterizing the complexity of various video decoding operations. As a result, this paper complements prior complexity-prediction research that is based on operational measurements. The accuracy of the proposed analytical R-D-C expressions is justified against experimental data obtained with a state-of-the-art motion-compensated temporal filtering based wavelet video coder, and several new insights are revealed on the different tradeoffs between rate-distortion performance and the required decoding complexity.

Stream mining applications require the identification of several different attributes in data content and hence rely on a distributed set of cascaded statistical classifiers to filter and process the data dynamically. In this letter, we introduce a novel methodology for configuring cascaded classifier topologies, specifically binary classifier trees, with optimized operating points after jointly considering the misclassification cost of each end-to-end class of interest in the tree, the resource constraints for every classifier, and the confidence level of each data object that is classified. By configuring multiple operating points per classifier, we enable not only intelligent load shedding when resources are scarce but also intelligent replication of low confidence data across multiple edges when excess resources are available. Using a classifier tree constructed from support vector machine-based sports image classifiers, we verify huge cost savings and discuss how different classifier placements and costs can influence the gains obtained by various algorithms.

Video decoding applications must often cope with highly time-varying workload demands, while meeting stringent display deadlines. Voltage/frequency scalable processors are highly attractive for video decoding on resource-constrained systems, since significant energy savings can be achieved by dynamically adapting the processor speed based on the changing workload demand. Previous works on video-related voltage scaling algorithms are often limited by the lack of a good complexity model for video and often do not explicitly consider the video quality impact of various steps involved in the decoding process. Our contribution in this paper is threefold. First, we propose a novel complexity model through offline training that explicitly considers the video source characteristics, the encoding algorithm, and platform specifics to predict execution times. Second, based on the complexity model, we propose low complexity online voltage scaling algorithms to process decoding jobs such that they meet their display deadlines with high probability. We show that on average, our queuing-based voltage scaling algorithm provides approximately 10%-15% energy savings over existing voltage scaling algorithms. Finally, we propose a joint voltage scaling and quality-aware priority scheduling algorithm that decodes jobs in order of their distortion impact, such that by setting the processor to various power levels and decoding only the jobs that contribute most to the overall quality, efficient quality, and energy tradeoffs can be achieved. We demonstrate the scalability of our algorithm in various practical decoding scenarios, where reducing the power to 25% of the original power can lead to quality degradations of less than 1.0 dB PSNR.

Contrary to the conventional paradigm of transform decomposition followed by quantization, we investigate the computation of two-dimensional (2D) discrete wavelet transforms (DWT) under quantized representations of the input source. The proposed method builds upon previous research on approximate signal processing and revisits the concept of incremental refinement of computation: Under a refinement of the source description (with the use of an embedded quantizer), the computation of the forward and inverse transform refines the previously computed result, thereby leading to incremental computation of the output. In the first part of this paper, we study both the forward and inverse DWT under state-of-the-art 2D lifting-based formulations. By focusing on conventional bitplane-based (double-deadzone) embedded quantization, we propose schemes that achieve incremental refinement of computation for the multilevel DWT decomposition or reconstruction based on a bitplane-by-bitplane calculation approach. In the second part, based on stochastic modeling of typical 2D DWT coefficients, we derive an analytical model to estimate the arithmetic complexity of the proposed incremental refinement of computation. The model is parameterized with respect to ( i) operational settings, such as the total number of decomposition levels and the terminating bitplane; (ii) input source and algorithm-related settings, e.g., the source variance, the complexity related to the choice of wavelet, etc. Based on the derived formulations, we study for which subsets of these model parameters the proposed framework derives identical reconstruction accuracy to the conventional approach without any incurring computational overhead. This is termed successive refinement of computation, since all representation accuracies are produced incrementally under a single (continuous) computation of the refined input source with no overhead in comparison to the conventional calculation approach that specifically targets each accuracy level and is not refinable. Our results, as well as the derived model estimates for incremental refinement, are validated with real video sequences compressed with a scalable coder.

Available resources in peer-to-peer (P2P) systems depend strongly on resource contributions made by individual peers. Empirical data shows that in the absence of incentives, a majority of the participating peers do not contribute resources. Modeling interactions between individual peers is often difficult as the number of peers in the system can be very large, and the relationships among them can be very complex. In this paper, we propose a new solution for P2P systems, where peers upload and download content to and from the contributing peers based on agreed-upon/determined sharing rates. We propose a P2P solution that deters free-riders by imposing constraints on participating peers; specifically, a peer is allowed access to new content only as long as its own content contribution exceeds an adaptively set threshold. The constraints are enforced either by a central authority (e.g., a tracker) or by a decentralized coalition of peers in a swarm, social network, etc. We derive optimal upload policies for the peers given their estimated future download requirements and their previous contribution (credit) to the other peers. Our results show considerable improvement in the cost-benefit tradeoff for peers that deploy such an optimal policy as compared to heuristic upload policies. We also propose mechanisms based on which the coalition of peers can provide incentives or penalties to participating peers to adjust their policies such that the availability of content and/or number of peers contributing content is maximized.

Networks of classifiers are capturing the attention of system and algorithmic researchers because they offer improved accuracy over single model classifiers, can be distributed over a network of servers for improved scalability, and can be adapted to available system resources. In this paper, we develop algorithms to optimally configure networks (chains) of such classifiers given system processing resource constraints. We first formally define a global performance metric for classifier chains by trading off the end-to-end probabilities of detection and false alarm. We then design centralized and distributed algorithms to provide efficient and fair resource allocation among several classifier chains competing for system resources. We use the Nash bargaining solution from game theory to ensure this. We also extend our algorithms to consider arbitrary topologies of classifier chains (with shared classifiers among competing chains). We present results for both simulated and state-of-the-art classifier chains for speaker verification operating on real telephony data, discuss the convergence of our algorithms to the optimal solution, and present interesting directions for future research.

Multihop networks provide a flexible infrastructure that is based on a mixture of existing access points and stations interconnected via wireless links. These networks present some unique challenges for video streaming applications due to the inherent infrastructure unreliability. In this paper, we address the problem of robust video streaming in multihop networks by relying on delay- constrained and distortion-aware scheduling, path diversity, and retransmission of important video packets over multiple links to maximize the received video quality at the destination node. To provide an analytical study of this streaming problem, we focus on an elementary multihop network topology that enables path diversity, which we term "elementary cell." Our analysis is considering several cross-layer parameters at the physical and medium access control (MAC) layers, as well as application-layer parameters such as the expected distortion reduction of each video packet and the packet scheduling via an overlay network infrastructure. In addition, we study the optimal deployment of path diversity in order to cope with link failures. The analysis is validated in each case by simulation results with the elementary cell topology, as well as with a larger multihop network topology. Based on the derived results, we are able to establish the benefits of using path diversity in video streaming over multihop networks, as well as to identify the cases where path diversity does not lead to performance improvements.