Energy-Efficient Designs in Cyber-Physical Systems with a Control and Optimization Approach by Yingsong Huang A dissertation submitted to the Graduate Faculty of Auburn University in partial fulfillment of the requirements for the Degree of Doctor of Philosophy Auburn, Alabama May 5, 2013 Keywords: CPS, smart grid, microgrids, wireless networks, video, energy efficiency, optimization, control, majorization, Lyapunov optimization Copyright 2013 by Yingsong Huang Approved by Shiwen Mao, Chair, Associate Professor of Electrical and Computer Engineering Prathima Agrawal, Professor of Electrical and Computer Engineering Jitendra K. Tugnait, Professor of Electrical and Computer Engineering Tin-Yau Tam, Professor of Mathematics Abstract In modern cyber-physical systems (CPS), new dimensions of freedom are enabled to energy efficient solutions. We first focus on the energy delivery side within the smart grid paradigm for smart, efficient and reliable energy delivery. We then explore the demand side with ?green? wire- less networks for multimedia streaming, in response to the drastic increasing demand in multimedia service in wireless networks. In this dissertation, we first study energy management systems in smart grid. We design power scheduling policies for smoothing power profile in power distribution networks. The pro- posed power scheduling policies allow the operator to deploy generators, transformers and power transmission lines with smaller capacity in the grid, thus reducing the capital investment. In addi- tion, the power consumption can be reduced during peak hours, and the average energy generation cost will also be minimized. We also propose a smart electric energy management system in mi- crogrids (MGs). With the proposed algorithm, the MG achieves the fundamental requirements in smart grid with distributed renewable energy integration, energy storage systems management and residential power quality management, while keeping the compatibility to the legacy grid. We then propose downlink power control frameworks for streaming multiple variable bit rate (VBR) videos in wireless cellular networks. We develop both centralized and low-complexity dis- tributed algorithms, which optimally schedule the transmission power for the BS?s, such that VBR videos can be delivered to mobile users without causing playout buffer underflow or overflow un- der wireless channel uncertainty. The proposed solutions achieve the quality of experience (QoE) requirements of users, as well as keeping the systems ?green?. In this dissertation, we adopt a control and optimization approach for energy efficient design in CPS.The synergy of the advanced control and optimization methods in engineering systems provides new visions for practical solutions to bring a green world in the future. ii Acknowledgments I have received such immeasurable help from many people, and in such diverse ways, to sup- port me during the development of this dissertation, and more generally, my academic experience. A few words? mention here cannot adequately capture all my appreciation. I would like to express my deepest gratitude to my dissertation advisor, Prof. Shiwen Mao, for his continuing and inspirational guidance, support and encouragement during my Ph.D. program. I would also like to sincerely thank my dissertation committee, Prof. Prathima Agrawal, Prof. Jitendra Tugnait, and Prof. Tin-Yau Tam for their valuable comments and time, who contribute their broad perspective in refining the ideas in this dissertation. I am also indebted to Prof. Alvin Lim for serving as the university reader, and reviewing my work. I would like to thank Prof. Stuart Wentworth for his constant support and inspiration in my instructing the RF Systems Labs. I enjoyed the teaching experience as well as his sense of humor in the labs. I want to take this opportunity to recognize all my fellow colleagues in the Electrical and Computer Engineering at Auburn University: Dr. In Keun Son, Dr. Donglin Hu, Bobby Black, Jing Ning, Yi Xu, Yu Wang, Zhifeng He and Zhefeng Jiang, for the discussions, cooperation and assistance during these years. In addition, I am very grateful to Dr. Yihan Li for her hospitality and help in my study and life at Auburn. Finally, I would like to extend my heart felt thanks to my parents, without their continuous support and tremendous care, the achievements of this dissertation could not be possible. iii Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Enabling Energy Efficient Cyber-Physical Systems . . . . . . . . . . . . . . . . . 1 1.2 Smart Grid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.1 Traditional Electricity Grid . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.2 Smart Grid Evolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2.3 Microgrid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2.4 Smart Energy Management Systems . . . . . . . . . . . . . . . . . . . . . 9 1.3 Energy Efficient Multimedia Networks . . . . . . . . . . . . . . . . . . . . . . . . 11 1.3.1 Multimedia Networks Architecture . . . . . . . . . . . . . . . . . . . . . 11 1.3.2 Energy Efficiency in Video Coding . . . . . . . . . . . . . . . . . . . . . 13 1.3.3 Energy Efficiency in Video Transmission . . . . . . . . . . . . . . . . . . 15 1.3.4 Joint Video Coding and Transmission Design . . . . . . . . . . . . . . . . 17 1.3.5 Video over Emerging Wireless Networks . . . . . . . . . . . . . . . . . . 18 1.4 Key Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.5 Overview of the Dissertation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2 Smooth Electric Power Scheduling in Power Distribution Networks . . . . . . . . . . 25 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.2 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.2.1 Load Demand Profile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 iv 2.2.2 Cumulative Demand and Supply Curves . . . . . . . . . . . . . . . . . . . 29 2.2.3 Smooth Power Scheduling Problem . . . . . . . . . . . . . . . . . . . . . 31 2.3 Majorization Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.4 Smooth Electric Power Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.4.1 SEPS-DL Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.4.2 Performance of SEPS-DL . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.4.3 Extension to the General Case . . . . . . . . . . . . . . . . . . . . . . . . 38 2.4.4 Electric Power Allocation Among Individual Users . . . . . . . . . . . . . 39 2.5 Simulation Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 2.6 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 2.7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3 Adaptive Electricity Scheduling in Microgrids . . . . . . . . . . . . . . . . . . . . . . 51 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.2 System Model and Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . 54 3.2.1 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.2.2 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 3.2.3 Lyapunov Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 3.3 Optimal Electricity Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 3.3.1 Properties of Optimal Scheduling . . . . . . . . . . . . . . . . . . . . . . 62 3.3.2 MG Optimal Scheduling Algorithm . . . . . . . . . . . . . . . . . . . . . 64 3.3.3 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 3.4 Simulation Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 3.4.1 Algorithm Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 3.4.2 Comparison with a Benchmark . . . . . . . . . . . . . . . . . . . . . . . . 69 3.5 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 4 Overview of Green Video Streaming over Celluar Networks and Variable Bit Rate Video 76 v 4.1 Green Video Streaming over Celluar Networks . . . . . . . . . . . . . . . . . . . 76 4.2 VBR Video System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 5 Downlink Power Allocation for Stored Variable-Bit-Rate Video in Cellular Network . . 81 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 5.2 System Model and Problem Formation . . . . . . . . . . . . . . . . . . . . . . . . 82 5.3 Two-Step Downlink Power Allocation . . . . . . . . . . . . . . . . . . . . . . . . 85 5.4 Distributed Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 5.5 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 5.6 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 5.7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 6 Downlink Power Control for Variable Bit Rate Video over Multicell Wireless Networks 100 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 6.2 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 6.2.1 Network and Video System Model . . . . . . . . . . . . . . . . . . . . . . 101 6.2.2 Problem Formation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 6.2.3 Existence of Feasible Solutions . . . . . . . . . . . . . . . . . . . . . . . 105 6.2.4 Comparison with a Lazy Scheme . . . . . . . . . . . . . . . . . . . . . . 107 6.3 Centralized Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 6.3.1 Reformulation and Linearization . . . . . . . . . . . . . . . . . . . . . . . 108 6.3.2 Branch-and-Bound Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 110 6.3.3 Enhancement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 6.4 Distributed Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 6.5 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 6.5.1 Centralized Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 6.5.2 Distributed Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 6.5.3 Empirical Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . 122 6.6 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 vi 6.7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 7 Energy Efficiency on Downlink Multiuser VBR Video Streaming . . . . . . . . . . . . 126 7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 7.2 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 7.2.1 Network and Video Source Model . . . . . . . . . . . . . . . . . . . . . . 127 7.2.2 Power-Aware Transmission Scheduling . . . . . . . . . . . . . . . . . . . 129 7.3 Problem Reformulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 7.3.1 Majorization Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . 131 7.3.2 Schur-convexity of Problem (7.9) . . . . . . . . . . . . . . . . . . . . . . 131 7.4 Power Allocation Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 7.4.1 Power Minimization Algorithm . . . . . . . . . . . . . . . . . . . . . . . 132 7.4.2 Optimality Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 7.4.3 Multiuser Video Transmissions . . . . . . . . . . . . . . . . . . . . . . . 135 7.4.4 Application to Interactive Video Streaming . . . . . . . . . . . . . . . . . 137 7.5 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 7.5.1 Simulation Results for Interactive Video Streaming . . . . . . . . . . . . . 143 7.6 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 7.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 8 Summary and Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 8.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 8.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 Appendices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 A Proofs in Chapter 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 A.1 Proof of Theorem 2.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 A.2 Proof of Theorem 2.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 B Proofs in Chapter 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 B.1 Proof of Theorem 3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 vii B.2 Derivation of Equation (3.16) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 B.3 Proof of Lemma 3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 B.4 Proof of Lemma 3.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 B.5 Proof of Lemma 3.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 B.6 Proof of Theorem 3.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 B.7 Proof of Theorem 3.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 B.8 Proof of Theorem 3.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 C Proofs in Chapter 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 C.1 Proof of Lemma 5.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 C.2 Proof of Lemma 5.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 C.3 Proof of Lemma 5.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 C.4 Proof of Theorem 5.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 C.5 Proof of Theorem 5.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 D Proofs in Chapter 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 D.1 Proof of Lemma 6.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 D.2 Proof of Theorem 6.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 E Proofs in Chapter 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 E.1 Proof of Theorem 7.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 E.2 Proof of Corollary 7.2.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 F Acronyms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176 viii List of Figures 1.1 Cyber-physical system - Integration of communication, control and computation [1]. . 2 1.2 Traditional electricity grid with unidirectional power and information flow. . . . . . . 4 1.3 Smart grid with plug-and-play interfaces and two-way flow of power and information. 6 1.4 Microgrid: Localized cluster of DRERs, ESS?s, information networks and residents. . 8 1.5 Energy management systems enhanced by smart grid paradigm. . . . . . . . . . . . . 9 1.6 Overview of the wireless video networking system. . . . . . . . . . . . . . . . . . . . 12 1.7 Block diagram of a typical video encoder. . . . . . . . . . . . . . . . . . . . . . . . . 12 1.8 Block diagram of a typical video decoder. . . . . . . . . . . . . . . . . . . . . . . . . 12 1.9 Protocol layers and system controls involved in wireless video transmission. . . . . . . 16 1.10 Overview of the dissertation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.1 Illustration of the electricity distribution network. . . . . . . . . . . . . . . . . . . . . 27 2.2 Cumulative demand and supply curves. . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.3 Lorenz Curves. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.4 Illustrate the operation of the SEPS-DL algorithm. . . . . . . . . . . . . . . . . . . . 36 ix 2.5 Smooth power scheduling with priority load. (Note that although not deferrable, the cumulative priority load can also be represented with two curves as shown in (a), where the maximum and minimum curves meet at the corners.) . . . . . . . . . . . . 39 2.6 Comparison of the power schedules achieved by SEPS-DL an GSEPS. . . . . . . . . . 43 2.7 Convergence of the individual power allocation achieved by DUMLC. . . . . . . . . . 44 2.8 Peak electric powers achieved by SEPS-DL, GSEPS, SUDP and UMRP. . . . . . . . . 46 2.9 Load factor achieved by SEPS-DL, GSEPS, SUDP and UMRP. . . . . . . . . . . . . . 46 2.10 Variances of the power schedules achieved by SEPS-DL, GSEPS, SUDP and UMRP. . 47 3.1 Illustrate the microgrid architecture. . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 3.2 The system model considered in this chapter. . . . . . . . . . . . . . . . . . . . . . . 55 3.3 Average QoSEs of three residents (V = Vmax). . . . . . . . . . . . . . . . . . . . . . . . 68 3.4 Energy levels of three Li-ion batteries (V = Vmax). . . . . . . . . . . . . . . . . . . . . . 69 3.5 QoSEs for three residents with different service contracts (V = Vmax/2). . . . . . . . . . . . 70 3.6 MG operation traces of the proposed algorithm for the 5-day period. . . . . . . . . . . 71 3.7 MG operation traces of proposed algorithm for the 7-day period. . . . . . . . . . . . . 72 4.1 Perceived quality of VBR and CBR videos: Football video coded with an H.264 codec. 77 4.2 Frame size of VBR and CBR videos: Football video coded with an H.264 codec. . . . 78 4.3 Transmission schedules for VBR video session n. . . . . . . . . . . . . . . . . . . . . 79 5.1 Normalized capacity curves and inflection points for a two-user system, where link 1 has better quality than link 2, i.e. A1 min{Pmax,Pmax(t)} then 12 Select Pmin from tstart to tstop = tc1 ; 13 else if Pmax < max{Pmin,Pmin(t)} then 14 Select Pmax from tstart to tstop = tc2 ; 15 else 16 t+ + ; 17 CONTINUE ; 18 end 19 tstart = tstop,tstop = tc1 = tc2 = tstart + 1,t = tstart + 1,Pmin = 0, Pmax = ? ; 20 end Corollary 2.2.1. The optimal power schedule is unique. Proof. Suppose vectorP? is not unique. Then there exists vectorP? ? vectorPk, for all k, and vectorP? negationslash= vectorP?. vectorP? must have a different set of power changing points from that of vectorP?. According to the proof of Theorem 2.2, we can construct an auxiliary schedule vectorP1, such that vectorP? ? vectorP1 ? vectorP?, which contradicts the assumption that vectorP? is optimal. Theorem 2.3. The complexity of SEPS-DL is O(L2). Proof. In the worst case, the SEPS-DL algorithm computes the optimal schedule for each time slot by probing the full length of the remaining power sequence (as in Steps 4?10 in Algorithm 1). The worst case execution time issummationtext1i=Li= L(L+1)2 ?O(L2). Theorem 2.4. The smooth electric power schedule computed by SEPS-DL has the smallest peak power. 37 Proof. From Theorem 2.2, we have vectorP? ? vectorPk, for all k. We may reorder the elements in both vectorP? and vectorPk to a non-increasing order. According to the definition of Majorization in Definition 2.3, the first element in the re-ordered vectorP? is not greater than that of vectorPk, which means the largest element in vectorP? is not greater than that of vectorPk. Thus, the schedule generated by SEPS-DL has the lowest peak power. Corollary 2.4.1. The SEPS-DL achieves highest load factor. Proof. The load factor in electric power grid is defined as in [99] Load factor(%) = AveragePowerPeakPower ?100% By Theorem 2.4, the SEPS-DL generates the lowest peak power, which achieves the highest load factor during the scheduled period. Theorem 2.4 and Corollary 2.4.1 is highly preferable for grid design and operation. A lower peak power allows the operator to deploy generators, transformers and power transmission lines with smaller capacity in the grid, thus reducing the capital investment. In addition, the grid may be alleviated of the power usage burden during peak hours, and the electric energy usage quality of users can be improved. Theorem 2.5. SEPS-DL is generation operating cost optimal. Proof. See Appendix A.2. 2.4.3 Extension to the General Case We next extend SEPS-DL to solve the general case problem (2.2). With the priority load, a feasible power schedule should satisfy P(t) ? Ep(t)/? in every time slot. The presence of priority load enforces new constraints on the feasibility of the schedules. For example, consider the aggregated cumulative priority load curves and deferrable load curves shown in Fig. 2.5(a) 38 kWh 0 t1 t3t2 (a) Cumulative priority load curves kWh t1 t3t2 (b) Cumulative deferrable load curves kWh t1 t3t2 1 2 3 (c) Aggregated cumulative load curves Figure 2.5: Smooth power scheduling with priority load. (Note that although not deferrable, the cumulative priority load can also be represented with two curves as shown in (a), where the maxi- mum and minimum curves meet at the corners.) and Fig. 2.5(b). According to the definition of feasible power supply schedule in SEPS-DL, both segments 1 and 2 in Fig. 2.5(c) are feasible. However, it can be seen that segment 1 actually cannot provide enough power to satisfy the priority load in time slot t2, since its slope is smaller than the required slope (i.e., that of segment 0 in Fig. 2.5(a)). To solve this problem, we develop the general smooth electric power scheduling algorithm (GSEPS), which is based on SEPS-DL. Specifically, SEPS-DL assumes no priority load. During the execution, the generated power segment is compared with the priority load. If the SEPS-DL generated power segment P?(t) is less than the priority load in time slot t, GSEPS will increase P?(t) to the priority load (e.g., see segment 3 in Fig. 2.5). Then SEPS-DL will continue to compute further segments of the schedule by setting the new starting point to t, until the entire schedule is computed. 2.4.4 Electric Power Allocation Among Individual Users After the smooth electric power schedule is obtained, the DCC announces the schedule to all the users and requests them to control their loads to match the supplied electric energy W?(t) = P?(t)? in each time slot t. To divide the total supply W?(t) among the N users, we assume a benefit function Un(pn(t)) for each user n, which is a nondecreasing concave function [92] and 39 represents the level of satisfaction of the user when receiving pn(t) in time slot t. We then develop an algorithm that maximizes the sum of the benefit functions of all users in the power distribu- tion network. The maximization of the total benefit under the smooth schedule constraint can be formulated in each time slot t as follows: maximize: summationtextn?RUn(pn(t)) (2.4) subject to: pminn (t) ?pn(t) ?pmaxn (t), for all n summationtext n?Rpn(t) = W ?(t)/?, where pmaxn (t) and pminn (t) are the maximum and minimum power consumptions of user n in slot t, respectively. Problem (2.4) is a convex optimization problem, which can be solved effectively with a convex optimization solver. In case that DCC may not know the exact parameters of individual utility functions in practice, we develop a distributed user benefit maximization load control algorithm (DUBMLC) based on dual decomposition [100] to solve problem (2.4). For brevity, we omit the time slot notation t in following equations. First, we introduce the non-negative Lagrange multiplier ?, and derive the Lagrange function: L(pn,?) = summationdisplay n?R Un(pn) +? parenleftBigg W ? summationdisplay n?R pn parenrightBigg (2.5) = summationdisplay n?R Ln(pn,?) +?W, whereLn(pn,?) = Un(pn)??pn. Observing thatLn(?) only depends on usern?s local information, we have the dual decomposition for each user n. Each user solves subproblem (2.6) for given Lagrange multipliers ??: pn(??) = argmaxpminn ?pn?pmaxn Ln(pn,??), for all n. (2.6) 40 Subproblem (2.6) can be solved with the subgradient method [14], sinceLn is strictly concave. User n iteratively updates its power pn until pn converges, as: pn(l+ 1) = bracketleftbigg pn(l) +?(l)? ?Ln(pn)?p n bracketrightbigg+ (2.7) where [?]+ denotes the projection of pn onto the range [pminn ,pmaxn ], and ?(l) is the step size varies in each step l according to the Armijo Rule [14]. The solution pn can be solved locally by the users and converges to the optimal solution of ?pn for all n as l??. For a given optimal solution ?pn, the master dual problem is to solved by DCC: minimize: L(?pn,?), subject to: ? ? 0, for all n. We can also apply the subgradient method to iteratively update the multipliers as: ?(l+ 1) = max braceleftbigg ?(l)??(l)? ?L(?)?? ,0 bracerightbigg , (2.8) where ?(l) is the step size. The Lagrange multipliers converges to the optimal as l ? ?, since problem (2.4) is a convex problem, the duality gap is zero and the solution of (2.6) is unique. The primal variable pn will also converge to the optimal solutions [100]. The distributed user benefit maximization load control (DUBMLC) algorithm is presented in Algorithm 2. With DUBMLC, each user greedily maximizes its own benefit by solving (2.6) with current ?price? ?, which is controlled by DCC through the master due problem (2.8). Due to convexity of the problem, the optimization gap is zero and the optimal total maximum benefit is reached when the algorithm converges. Combining of GSEPS and DUBMLC, we now present the General Smooth Electric Power Scheduling Policy. Specifically, at the beginning of each period, which can be daily based or be an arbitrary period of time, the users send their slotted demand profiles to the DCC through 41 Algorithm 2: Distributed User Benefit Maximization Load Control Algorithm 1 l = 0 and the DCC initializes nonnegative parameter ?(l) ; 2 The DCC announces the parameters to the users via the communications network ; 3 Each user locally solves problem (2.6) as in (2.7) to obtain its requested power ; 4 Each user sends its requested power to the DCC via information networks ; 5 The DCC updates the parameters ?(l) as in (2.8) and announces the new value ?(l+ 1) to all users ; 6 l = l+ 1 and go to Step 3, until the solution converges ; the communications network. After aggregating all the demand profiles, the DCC calculates the deterministic cumulative supply/demand curves for the power distribution networks and executes GSEPS to compute the smooth power profile. After that, DCC let the users to control their elec- tricity usage to match the smooth schedule with DUBMLC. The load control does not necessarily need to be fully executed at the exact beginning of the period. It may operate at some time ahead of the scheduled time slot. If a user requests a usage exceeding the planned level, the DCC may allow the distribution substation to temporally fulfill the excess demand but charging a penalty price based on the electric energy availability of the power distribution network. 2.5 Simulation Evaluation In this section, we evaluate the proposed algorithms by simulating an electric power distri- bution network with 250 independent users. We assume a daily period slotted into L = 144 time slots (i.e., ? = 10 min). The demand for each user during the period is randomly dis- tributed from 35 kWh to 50 kWh. The DCC aggregates the load profiles and generates the cumulative supply/demand curves at the beginning of the period. We adopt a benefit function Un(t) = k1qn(t) ? 12k2qn(t)2 [101], where qn(t) ? [0,1] is the normalized value of power sup- ply pn(t). With this Un(?), problem (2.4) becomes a quadratic programming problem, which can be effectively solved with the proposed distributed algorithm. Without loss of generality, we set k1 = k2 = 1 in the simulations. We first examine the performance of SEPS-DL and GSEPS. For SEPS-DL, all the electric energy demand is deferrable. For GSEPS, we assume 50% of the demand is deferrable and the 42 0 20 40 60 80 100 120 1400 2000 4000 6000 8000 10000 12000 Time Cumulative electric energy (kWh) Cumulative min demand curve of the grid Cumulative supply curve of SEPS?DL Cumulative supply curve of GSEPS Cumulative max demand curve of the grid Figure 2.6: Comparison of the power schedules achieved by SEPS-DL an GSEPS. deadlines are randomly distributed during the daily period. The cumulative demand curves and the computed schedules are plotted in Fig. 2.6. We find that both electric power schedules lie between vectorWmin and vectorWmax, meaning they are feasible and satisfying the user demands in the entire period. In some time slots, e.g., slots [70, 80] and [110, 120], GSEPS requests a larger electric power than SEPS-DL. This is due to the hard requirement for the priority load, which temporally forces GSEPS to increase the electric power supply. After the smooth power schedule is obtained, DUBMLC is executed to divide the power to individual users in each time slot. For better illustration, we only plot the power convergence curves for six users in Fig. 2.7. The curves for other users are similar. We find that all the curves converge to the optimal values very quickly; after one step there is no significant variation in the electric powers of individual users. We next compare the proposed algorithms with two alternatives: ? A ?supply until deadline? scheme (SUDP), in which the deferrable load demand is served until the last minute. 43 0 10 20 30 40 50 60 70 80 90 1000 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 Steps Electric power (kW) User 1 User 2 User 3 User 4 User 5 User 6 Figure 2.7: Convergence of the individual power allocation achieved by DUMLC. ? The ?utility maximization real-time pricing? scheme (UMRP) that is introduced in [102], which solves the demand side management problem with a real-time pricing strategy and has been widely cited in the smart grid research community. In particular, the UMRP scheme maximizes the social welfare in a smart grid at each time slot independently, i.e., max summationdisplay n?R Un(pn(t))?g(P(t),?(t)), for all t, subject to the total power generation constraint and user power consumption constraints. This algorithm can be extended to our simulation scenario. In this work, the operating cost of power generation is evaluated by g(P(t),?(t)) = (?1 + ?2P(t) + ?3P(t)2)?(t), which is generalized from [103].We let ?1 = 120.0,?2 = 6,?3 = 0.04 for a generator [103] and ?(t) be uniformly distributed in [0.5,2.5]. This yields a quadratic programming problem, which can be solved in either a centralized or distributed manner [102]. In the simulations, we use a centralized interior- point method to solve the problem. 44 The peak power, load factor and power variation achieved by the above algorithms for net- works with different numbers of users are presented in Fig. 2.8, Fig. 2.9, and Fig. 2.10, respec- tively. Each number is the average of 100 simulation runs with different random seeds, with the 95% confidence interval plotted at the top of each bar. We observe that SEPS-DL and GSEPS can significantly reduce both peak power and power variation in the power distribution network. For example, for the network with 1000 users, SEPS-DL and GSEPS achieves peak powers 1947 kW and 2560 kW, respectively, which are only 55% and 73% of the corresponding SUDP and UMRP peak powers. We also notice that the load factors achieved by SEPS-DL and GSEPS are more than 100% and 50% larger than those of SUDP and UMRP under all cases. Similiarly, we find in Figure 2.10 that the SEPS-DL and GSEPS schedules are much more smoother than both SUDP and UMRP schedules. Therefore, to design the power generation, transmission and distribution infrastructure for this 1000-user site, we may select components, such as transformers and trans- mission lines, based on the capacity specifications of 1947 kW and 2560 kW, respectively (with SEPS-DL and GSEPS), instead of 3513 kW with SUDP and UMRP. As the network size increases, the performance gap increases as well. For the smallest gap case when network size is 100, the power reduction is 176 kW for SEPS-DL and 110 kW for GSEPS, which meets the requirement of 100 kW minimum energy reductions for the DR products at ISONE [104]. It is interesting to observe that UMRP and SUDP have almost identical performance in the simulations. This is largely due to the choice of the object functionsummationtextn?RUn(pn(t))?g(P(t),?(t)). In the simulation with the above utility functions and cost functions, the effect of the total power decrement on the cost functions dominates the effect of the individual user power increments in their utility functions. Thus UMRP attempts to reduce the total power generation, while only main- taining the minimum user satisfaction level. This strategy indeed degenerates UMRP to SUDP, both with similar performance. Although UMRP maximizes the welfare of the distribution net- work, it does not aim to smooth the power schedules. It would be helpful to carefully introduce some coefficients to balance the contributions of utility and cost to the welfare. This phenomenon also verifies our motivation of the work that the real-time pricing with utility maximization may 45 100 200 500 1000 15000 1000 2000 3000 4000 5000 6000 Power distribution networks size (# of users) Average peak electric power (kW) SEPS?DL GSEPS SUDP UMRP Figure 2.8: Peak electric powers achieved by SEPS-DL, GSEPS, SUDP and UMRP. 100 200 500 1000 15000 10 20 30 40 50 60 70 80 90 100 Power distribution network size (# of users) Load factor (%) SEPS?DL GSEPS SUDP UMRP Figure 2.9: Load factor achieved by SEPS-DL, GSEPS, SUDP and UMRP. not automatically solve the smooth electric power scheduling and peak power reduction problems. Compared to UMRP, the proposed algorithms directly target at the smoothness optimization prob- lem and are robust to various configurations of the distribution network. 46 0 100 200 500 1000 15000 2 4 6 8 10 12 x 105 Power distribution networks size (# of users) Average electric power variance(KW 2 ) SEPS?DL GSEPS SUDP UMRP Figure 2.10: Variances of the power schedules achieved by SEPS-DL, GSEPS, SUDP and UMRP. We finally compare the average generator operating cost of SEPS-DL, GSEPS, SUDP and UMRP. Similar to the previous scenario, we assume a load site with average aggregated demand 100 MW, which is scheduled by SEPS-DL, GSEPS, SUDP and UMRP based on a daily period. The average generator operating costs are shown in Table 2.2. It can be seen that both SEPS- DL and GSEPS obtain smaller operating costs than SUDP and UMRP for serving the same load site. It is not surprising to see that SUDP and UMRP obtain similar results, due to the effect of the objective function. Also note that UMRP is not operating cost optimal, although it seeks to maximize the social welfare. This is due to the fact that the operating cost is not independent from time slot to time slot; greedily optimizing social welfare in each time slot does not guarantee optimality over the entire period. Suppressing user satisfaction level some time slots, may result in high power allocations at a later time slot to meet all the delayed demands right before their deadline, leading to larger peak power and electricity generation cost. On the contrary, SEPS-DL and GSEPS optimize power scheduling over the entire period, and can flexibly serve the demand to achieve smooth electric power scheduling and low operating cost. 47 Table 2.2: Average operating cost of power generation SEPS-DL GSEPS SUDP UMRP $/hour 1653 1669 1746 1746 2.6 Related Work SG is regarded as the next generation power grid that exploits a coexisting communications network for better control and optimization of power generation and distribution. In SG, infor- mation technologies and computational intelligence are integrated across electricity generation, transmission, distribution and consumption to achieve green, reliable, efficient and sustainable en- ergy goals. Comprehensive surveys of SG technologies can be found in [3?5, 105]. The emergence of SG attracts new interest in evolving the next generation of power distri- bution systems [88]. Demand response is an important power distribution paradigm to reduce the peak demand and smooth demand profiles in the grid by shaping the user demands. Various imple- mentation issues of demand response in SG are examined in [104]. Real-time pricing and direct load control are two important ways to shape user demand profile. Due to the real-time communications and control through two-way information flows in SG, new design approaches in demand response are being developed recently [90?93], which are based on optimization and game theory approaches. In [90], the authors proposed an optimal and au- tomatic residential energy consumption scheduling framework to achieve the trade-off between minimization of electricity payment and appliance operation waiting time. In [91], a game the- ory approach is used to control the power demand at peak hours by dynamic pricing strategies. In [92], the authors studied demand response for households based on utility maximization, and showed that there exist time-varying prices that may achieve social optimality. A recent work [93] introduced the framework for optimal resource allocation under the uncertainty in the two-way information network and provided a decentralized algorithm that can be implemented in practice. Although providing some interesting methods to achieve cost efficient electricity usage, these work do not explicitly address the problem of smooth electric power scheduling. 48 Two recent works [106,107] studied the problem of reducing the peak-to-average ratio (PAR) of the electric energy consumption in SG. In [106], the authors introduced a game theory frame- work for a distributed algorithm to minimize the total energy payment and reduce PAR. However, users need to broadcast control messages to announce their new schedules to the entire network. The control overhead could be considerable. In [107], energy storage devices were incorporated in the SG and users? cost and PAR are minimized with a distributed algorithm. Although the dis- tributed algorithm only needs to exchange information with the energy provider, the achieved Nash equilibrium cannot be guaranteed to be socially optimal. In addition, this work does not consider the operating cost of the energy provider. Majorization is a useful tool for problems involving vectors [13]. It has been used in solving optimization problems in the communication and networking area [57,95,96]. In [95], majorization is applied to variable-bit-rate (VBR) video smoothing over a wired CBR link. Ref. [96] presented an optimal transmission algorithm over a wireless multiple-input single-output (MISO) link based on majorization. In our recent work [57], we adopted majorization for power efficient VBR video streaming over a cellular network. Our work differs from these existing efforts by introducing the mathematic theory of majoriza- tion to solve the smoothness scheduling problem in electric distribution networks, while explicitly targeting at the unique mathematical notion of smoothness. To the best of our knowledge, this is the first work that introduces maojorization into electric energy management in power grid, which jointly considers smooth power scheduling, electric usage quality provisioning on the user side, and grid operating cost on the electric energy provider side. The effective electric power smooth- ing solution provides a highly competitive solution for future SG design and operations. 2.7 Conclusions In this chapter, we addressed the problem of smooth electric power scheduling in a power dis- tribution network. We introduced a deterministic model to characterize the complex relationship 49 between demand and supply. A constrained nonlinear optimization problem is formulated aim- ing to minimize the electric power variation and satisfy user power usage quality. We developed majorization-based algorithms for deriving smoothness optimal schedules for the network, and a distributed algorithm for dividing the power supply among the users. Our simulation study shows that the proposed algorithms can effectively reduce the peak power, minimize the power variation, and reduce the operating cost of the grid, while satisfying user power usage quality. 50 Chapter 3 Adaptive Electricity Scheduling in Microgrids 3.1 Introduction In this chapter, we designed a smart energy management systems in Microgrid (MG) by taking advantage of the plug-and-play interfaces of smart grid. MG is a promising component for future SG deployment. Due to the increasing deployment of distributed renewable energy resources (DR- ERs), MG provides a localized cluster of renewable energy generation, storage, distribution and local demand, to achieve reliable and effective energy supply with simplified implementation of SG functionalities [4, 108]. We review the typical MG architecture in Fig. 3.1, consisting of DRERs (such as wind turbines and solar photovoltaic cells), energy storage systems (ESS), a communica- tion network (e.g., wireless or powerline communications) for information delivery, an MG central controller (MGCC), and local residents. The MG has centralized control with the MGCC [108], which exchanges information with local residents, ESS?s, and DRERs via the information net- work. There is a single common coupling point with the macrogrid. When disconnected, the MG works in the islanded mode and DRERs and ESS?s provide electricity to local residents. When connected, the MG may purchase extra electricity from the macrogrid or sell excess energy back to the market [3]. The balance of electricity demand and supply is one of the most important requirements in MG management. Instead of matching supply to demand, smart energy management matches the demand to the available supply using control technology or off-peak pricing to achieve more effi- cient capacity utilization [4]. In this chapter, we develop a novel access control framework for MG energy management, exploiting the two-way flows of electricity and information. In particular, we consider two types of electricity usage: (i) a pre-agreed basic usage that is ?hard?-guaranteed, such as basic living usage, and (ii) extra elastic quality usage exceeding the pre-agreed level for 51 Macrogrid Power flow Inf orm ati on flo w Microgrid Power flow Market Broker Energy storageMGCC Figure 3.1: Illustrate the microgrid architecture. more comfortable life, such as excessive use of air conditioners or entertainment devices. In prac- tice, residents may set their load priority and preference to obtain the two types of usage [89]. The basic usage should be always satisfied, while the quality usage is controlled by the MGCC according to the grid status, such as DRER generation, ESS storage levels and utility prices. The MGCC may block some quality usage demand if necessary. This can be implemented by incor- porating smart meters, smart loads and appliances that can adjust and control their service level through communication flows [3]. To quantify residents? satisfaction level, we define the outage percentage of the quality usage as Quality of Service in Electricity (QoSE), which is specified in the service contracts. For example, the residents may customize their outage risk of quality usage in return for paying an insurance premium, which is differentiated according to local residents preferences [109] [109]. The MGCC adaptively schedules electricity to keep the QoSE below a target level, and accordingly dynamically balance the load demand to match the available supply. In this chapter, we investigate the problem of smart energy scheduling by jointly considering renewable energy distribution, ESS management, residential demand management, and utility mar- ket participation, aiming to minimize the MG operation cost and guarantee the residents? QoSE. The MGCC may serve some quality usage with supplies from the DRERs, ESS?s and macrogrid. On the other hand, the MG can also sell excessive electricity back to the macrogrid to compensate 52 for the energy generation cost. The electricity generated from renewable sources is generally ran- dom, due to complex weather conditions, while the electricity demand is also random due to the random consumer behavior, and so do the purchasing and selling prices on the utility market. It is challenging to model the random supply, demand, and price processes for MG management, and it may also be costly to have precise, real-time monitoring of the random processes. Therefore, a simple, low cost, and optimal electricity scheduling scheme that does not rely on any statistical information of the supply, demand, and price processes would be highly desirable. We tackle the MG electricity scheduling problem with a Lyapunov optimization approach, which is a useful technique to solve stochastic optimization and stability problems [12]. We first introduce two virtual queues: QoSE virtual queues and battery virtual queues to transform the QoSE control problem and battery management problem to queue stability problems. Second, we design an adaptive MG electricity scheduling policy based on the Lyapunov optimization method and prove several deterministic (or, ?hard?) performance bounds for the proposed algorithm. The algorithm can be implemented online because it only relies on the current system status, without needing any future knowledge of the energy demand, supply and price processes and any future information. The proposed algorithm also converges exponentially due to the nice property of Lyapunov stability design [110]. The algorithm is evaluated with trace-driven simulations and is shown to achieve significant efficiency on MG operation cost while guaranteeing the residents? QoSE. The remainder of this chapter is organized as follows. We present the system model and problem formulation in Section 3.2. An adaptive MG electricity scheduling algorithm is designed and analyzed in Section 3.3. Simulation results are presented and discussed in Section 3.4. We discuss related work in Section 3.5. Section 3.6 concludes the chapter. The notations used in this chapter are summarized in Table 3.1. 53 3.2 System Model and Problem Formulation 3.2.1 System Model Overview We consider the electricity supply and consumption in an MG as shown in Fig. 3.1. We as- sume that the MG is properly designed such that a portion of the electricity demand related to basic living usage (e.g., lighting) from the residents, termed basic usage, can be guaranteed by the min- imum capacity of the MG. There are randomness in both electricity supply (e.g., weather change) and demand (e.g., entertainment usage in weekends). To cope with the randomness, the MG works in the grid-connected mode and is equipped with ESS?s, such as electrochemical battery, supercon- ducting magnetic energy storage, flywheel energy storage, etc. The ESS?s store excess electricity for future use. The MGCC collects information about the resident demands, DRER supplies, and ESS levels through the information network. When a resident demand exceeds the pre-agreed level, a quality usage request will be triggered and transmitted to the MGCC. The MGCC will then decide the amount of quality usage to be satisfied with energy from the DRERS, the ESS?s, or by purchasing electricity from the macrogrid. The MGCC may also decline some quality usage requests. The excess energy can be stored at the ESS?s or sold back to the macrogrid for compensating the cost of MG operation. Without loss of generality, we consider a time-slotted system. The time slot duration is deter- mined by the timescale of the demand and supply processes, as well as how frequent the MG can switch on and off to the macrogrid. Energy Storage System Model The system model is shown in Fig. 3.2. Consider a battery farm with K independent battery cells, which can be recharged and discharged. We assume that the batteries are not leaky and do not consider the power loss in recharging and discharging, since the amount is usually small. It is 54 Resident 1's quality usage Control outage probability at ?N P(t) S(t)Q(t) pN(t) p1(t) R1(t) D1(t) Resident N's quality usage Served quality usage Served quality usage Control outage probability at ?1 Battery 1 Battery K ESSs MGCC Rk(t) Dk(t) Figure 3.2: The system model considered in this chapter. easy to relax this assumption by applying a constant percentage on the recharging and discharging processes. For brevity, we also ignore the aging effect of the battery and the maintenance cost, since the cost on the utility market dominates the operation cost of MGs. Let Ek(t) denote the energy level of the kth battery in time slot t. The capacity of the battery is bounded as Emink ?Ek(t) ?Emaxk ,?k,t, (3.1) where Emaxk ? 0 is the maximum capacity. Emink ? 0 is the minimum energy level required for battery k, which may be set by the battery deep discharge protection settings. The dynamics over time of Ek(t) can be described as Ek(t+ 1) = Ek(t)?Dk(t) +Rk(t),?k,t, (3.2) where Rk(t) and Dk(t) are the recharging and discharging energy for battery k in time slot t, respectively. The charging and discharging energy in each time slot are bounded as ? ?? ?? 0 ?Rk(t) ?Rmaxk , ?k,t 0 ?Dk(t) ?Dmaxk , ?k,t. (3.3) In each time slot t, Rk(t) and Dk(t) are determined such that (3.1) is satisfied in the next time slot. 55 Usually the recharging and discharging operations cannot be performed simultaneously, which leads to ?? ? ?? Rk(t) > 0 ?Dk(t) = 0, ?k,t Dk(t) > 0 ?Rk(t) = 0, ?k,t. (3.4) Energy Supply and Demand Model Consider N residents in the MG; each generates basic and quality electricity usage requests, and each can tolerate a prescribed outage probability ?n for the requested quality usage part. The MGCC adaptively serves quality usage requests at different levels to maintain the QoSE as well as the stability of the grid. The service of quality usage can be different for different residents, depending on individual service agreements. Let ?n be the average quality usage arrival rate, and ?n a prescribed outage tolerance (i.e., a percentage) for user n. The average outage rate for the quality usage, ?n, should satisfy ?n ??n ??n. (3.5) At each timet, the quality usage request from residentnis?n(t) ? [0,?maxn ] units, which is an i.i.d random variable with a general distribution. The average rate is ?n = limt??(1/t)summationtextt?1?=0?n(?) by the law of large number. The DRERs in the MG generate U(t) units of electricity in time slot t. U(t) can offer enough capacity to support the pre-agreed basic usage in the MG, which is guaranteed by islanded mode MG planning. due to complex weather conditions. The electric is transmitted over power trans- mission lines. Without loss of generality, we assume the power transmission line is not subject to outages and the transmission loss is negligible. Let ?bn(t) be the pre-agreed basic usage for resident n in time slot t, which can be fully satisfied by U(t), i.e., summationtextNn=1?bn(t) ? U(t), for all t. In addition, some quality usage request ?n(t) may be satisfied if P(t) = U(t)?summationtextNn=1?bn(t) ? 0. 56 Let pn(t) be the energy allocated for the quality usage of resident n. We have 0 ?pn(t) ??n(t). (3.6) We define a function In(t) ? 0 to indicate the amount of quality usage outage for resi- dent n, as In(t) = ?n(t) ? pn(t). Then the average outage rate can be evaluated as ?n = limt??(1/t)summationtextt?1?=0In(t). The MGCC may purchase additional energy from the macrogrid or sell some excess energy back to the macrogrid. Let Q(t) ? [0,Qmax] denote the energy purchased from the macrogrid and S(t) ? [0,Smax] the energy sold on the market in time slot t, where Qmax and Smax are determined by the capacity of the transformers and power lines. Since it is not reasonable to purchase and sell energy on the market at the same time, we have the following constraints ? ?? ?? Q(t) > 0 ?S(t) = 0, ?t S(t) > 0 ?Q(t) = 0, ?t. (3.7) To balance the supply and demand in the MG, we have P(t)+Q(t)+ Ksummationdisplay k=1 Dk(t)?S(t)? Ksummationdisplay k=1 Rk(t)= Nsummationdisplay n=1 pn(t),?t. (3.8) Utility Market Price Model The price for purchasing electricity from the macrogrid in time slot t is C(t) per unit. The purchasing price depends on the utility market state, such as peak/off time of the day. We assume finite C(t) ? [Cmin,Cmax], which is announced by the utility market at the beginning of each time slot and remains constant during the slot period [111]. Unlike prior work [111], we do not require any statistic information of the C(t) process, except that it is independent to the amount of energy to be purchased in that time slot. 57 If the MGCC determines to sell renewable energy on the utility market, the selling price from the market broker is denoted by W(t) ? [Wmin,Wmax] in time slot t, which is also a stochastic process with a general distribution and mean ?n. We also assume W(t) is known at the beginning of each time slot and independent to the amount of energy to be sold on the market. We assume Cmax ? Wmax, Cmin ? Wmin and C(t) > W(t) for all t. That is, the MG cannot make profit by greedily purchasing energy from the market and then sell it back to the market at a higher price simultaneously. 3.2.2 Problem Formulation Given the above models, a control policyA(t) = {Q(t),S(t),Rk(t),Dk(t),pn(t)}is designed to minimize the operation cost of the MG and guarantee the QoSE of the residents. We formulate the electricity scheduling problem as minimize: limt?? 1t t?1summationdisplay ?=0 E{Q(?)C(?)?S(?)W(?)} (3.9) s.t. (3.1), (3.3), (3.4), (3.5), (3.6), (3.7), (3.8) battery queue stability constraints. Problem (3.9) is a stochastic programming problem, where the utility prices, utility generation of DRERs, and utility consumption of residents are all random. The solution also depends on the evolution of battery states. It is challenging since the supply, demand, and price are all general processes. Virtual Queues We first adopt a battery virtual queue Xk(t) that tracks the charge level of each battery k: Xk(t) = Ek(t)?Dmaxk ?Emink ?VCmax, ?k,t, (3.10) 58 where 0 0 when vector?(t) negationslash= vector0 and L(vector?(t)) = 0 ? vector?(t) = vector0. We then define the conditional one slot Lyapunov drift as ?(vector?(t)) = E{L(vector?(t+ 1))?L(vector?(t))|vector?(t)}. (3.15) 60 With the drift defined as in (3.15), it can be shown that ?(vector?(t)) = 12E braceleftBigg Ksummationdisplay k=1 [(Xk(t+ 1))2 ?(Xk(t))2|Xk(t)]+ Nsummationdisplay n=1 [(Zn(t+ 1))2 ?(Zn(t))2|Zn(t)] bracerightBigg ? B + Nsummationdisplay n=1 E{Zn(t)(1??n)?n(t)|Zn(t)}+ Ksummationdisplay k=1 E{Xk(t)(Rk(t)?Dk(t))|Xk(t)}? Nsummationdisplay n=1 E{(Zn(t) +?n(t))pn(t)|Zn(t)}, (3.16) where B = 12summationtextKk=1(max{Dmaxk ,Rmaxk })2 + 12summationtextNn=1(2 + ?2n)(?maxn )2 is a constant. See Ap- plendix B.2 for the derivation of (3.16). To minimize the operation cost of the MG, we adopt the drift-plus-penalty method [112]. Specifically, we select the control policy A(t) = {Q(t),S(t),Rk(t),Dk(t),pn(t)} to minimize the bound on the drift-plus-penalty as: ?(vector?(t)) +VE{Q(t)C(t)?S(t)W(t)|vector?(t)} ? right-hand-side of (3.16) + VE{Q(t)C(t)?S(t)W(t)|vector?(t)}, (3.17) where 0 < V ? Vmax is defined in Section 3.2.2 for the trade-off between stability performance and operation cost minimization. Given the current virtual queue states Xk(t) and Zn(t), market prices S(t) and W(t), available DRERs energy P(t), and the resident quality usage request ?n(t), 61 the optimal policy is the solution to the following problem. minimize: B + Nsummationdisplay n=1 [Zn(t)(1??n)?n(t)] + V[Q(t)C(t)?S(t)W(t)] + Ksummationdisplay k=1 [Xk(t)(Rk(t)?Dk(t))]? Nsummationdisplay n=1 [(Zn(t) +?n(t))pn(t)] (3.18) s.t. (3.3), (3.4), (3.6), (3.7), (3.8) . Since the control policy A(t) is only applied to the last three terms of (3.18), we can further simplify problem (3.18) as minimize: V[Q(t)C(t)?S(t)W(t)] + Ksummationdisplay k=1 [Xk(t)(Rk(t)? Dk(t))]? Nsummationdisplay n=1 [(Zn(t) +?n(t))pn(t)] (3.19) s.t. (3.3), (3.4), (3.6), (3.7), (3.8) , which can be solved based on observations of the current system state{Xk(t),Zn(t),C(t),W(t),P(t), ?n(t)}. 3.3 Optimal Electricity Scheduling 3.3.1 Properties of Optimal Scheduling With the Lyapunov penalty-and-drift method, we transform problem (3.13) to problem (3.19) to be solved for each time slot. The solution only depends on the current system state; there is no need for the statistics of the supply, demand and price processes and no need for any future information. The solution algorithm to this problem is thus an online algorithm. We have the following properties for the optimal scheduling. 62 Lemma 3.1. The optimal solution to problem (3.19) has the following properties: 1. If Q(t) > 0, we have S(t) = 0, (a) If Xk(t) > ?VC(t), the optimal solution always selects Rk(t) = 0; if Xk(t) < ?VC(t), the optimal solution always selects Dk(t) = 0. (b) If Zn(t) >VC(t)??n(t), the optimal solution always selects pn(t) ? (1??n)?n(t); if Zn(t) 0, (a) If Xk(t) > ?VW(t), the optimal solution always selects Rk(t) = 0; if Xk(t) < ?VW(t), the optimal solution always selects Dk(t) = 0. (b) If Zn(t) >VW(t)??n(t), the optimal solution always selects pn(t) ? (1??n)?n(t); if Zn(t) ?VWmin, the optimal solution always selects Rk(t) = 0. 2. If Xk(t) VCmax, the optimal solution always selects pn(t) ? (1??n)?n(t). 2. If Zn(t) ?VC(t), and Dk(t) = 0 if Xk(t) < ?VC(t) according to Lemma 3.1. Also, if Zn(t) P?n, Cn is convex. Proof. See Appendix C.3. The normalized capacities for a two-user system is plotted in Fig. 5.1, with the inflection points marked. It can been observed that the curves are concave on the left hand side of the inflection points and convex on the right hand side of the inflection points. The processing gain is usually large for practical systems (e.g., Ln = 128 in IS-95 CDMA). We assume Ln ? 1 in the following analysis. Theorem 5.2. For problem C, there can be at most two links operating in the convex region if Ln ? (4 ?P + 6An)/( ?P + 3An). Proof. See Appendix C.4. For a clean channel where An ? 0, Ln ? 4 will guarantee at most two links operating in the convex region. The following results are on the impact of channel quality An = ?n/Gn. 88 Theorem 5.3. For a given Ln, the inflection point P?n is an increasing function of An. For two links i and j with the same transmit power P, if Ai < Aj, we have Ci(P,Ai) > Cj(P,Aj) and ?Ci(Pi,Ai) ?Pi |Pi=P > ?Cj(Pj,Aj) ?Pj |Pj=P > 0. Proof. See Appendix C.5. Theorem 5.3 shows that, for two links in the convex region with the same initial power P, allocating more power to the link with better quality can achieve larger objective value than alter- native ways of splitting the power between the two links (i.e., achieving the multi-user diversity gain). Based on the above analysis, we develop the second step of the power allocation algorithm for solving problem C, as given in Algorithm 5. In Algorithm 5, Lines 3 ? 4 tests the feasibility of the power allocation. If the sum of the total minimum required power is larger than the BS peak power, there is no feasible power allocation and there will be buffer underflow. In this case, we select users with ?good? channels for transmission and suspend the users with ?bad? channels. The Step II algorithm checks the three possible solution scenarios for problem C depending on the network status and video parameters: ? All links operate in the convex region; ? One link operates in the convex region and the remaining links operate in the concave region ? Two links operate in the convex region and the remaining links operate in the concave region. Each of the three phases in Algorithm 5 considers the optimality condition for one of the three scenarios. In particular, Phase 1 first optimizes the power allocation in the concave region and then allocates the remaining power to the links that could be moved to the convex region. Phase 2 allocates as much power as possible to the link with the best quality, which could work in the convex region. Phase 3 attempts to move the second best link to the convex region if the total power constraint is not violated. Usually when Ln and n are large, Phase 3 will rarely occur due to the peak power constraint. 89 Algorithm 5: Two-Step Power Allocation Algorithm: Step II 1 Initialization ; 2 BS obtains bn, Dn, and Bn for all user n; 3 BS computes ?maxn , ?minn , and P?n, for all n; 4 BS computes the minimum required sum power ?Pmin =summationtextn?U Pminn and gap ?P = ?P ? ?Pmin; 5 if ?Pmin > ?P then 6 Remove links from U, according to descending order of An, until ?Pmin ? ?P; 7 end 8 Compute Rn = Cn(min{Pmaxn ,Pminn +?P})?Cn(Pminn )min{Pmax n ,Pminn +?P}?Pminn , for all Pmaxn > P?n; 9 Phase 1 ; 10 Select all the users satisfying Pminn < P?n as a set U? ?U; 11 Solve problem C under constraints Pminn ? Pn ? min(Pmaxn ,P?n) andsummationtext n?U? Pn ? ?P ? = ?P ?summationtext n??U? P minn , where ?U? is the complementary set of U?, and obtain solution vectorP1; 12 Calculate Rn by updating Pminn to the solution in Line 11 and assign the remaining power to the nodes in set U, in descending order of Rn; 13 Obtain the Phase 1 solution, vectorPp1, and objective value fp1; 14 Phase 2 ; 15 Select the link with the maximum Rn, and assign all the available power ?P ? ?Pmin to the link, until either all the power is assigned or the link attains power Pmaxn ; 16 if there is still power to allocate then 17 Select all the nodes in set U\n and repeat Lines 8 ? 12; 18 end 19 Obtain the Phase 2 solution, vectorPp2, and objective value fp2; 20 Phase 3 ; 21 Select the first 2 links with the largest Rn?s, and assign all the available power ?P ? ?Pmin to the links, until all the power is assigned or the links attains power Pmaxn , and repeat Lines 16 ? 18; 22 Obtain the Phase 3 solution, vectorPp3, and objective value fp3; 23 Decision ; 24 Choose the largest objective value among fp1, fp2 and fp3, and stop with the corresponding power assignment; In Algorithm 5, Line 7 presents a convex optimization component, for which several effective solution techniques can be applied. In the following section, we describe a distributed algorithm for Line 7 based on dual decomposition. 5.4 Distributed Algorithm As discussed in Section 5.3, the core of the Step II algorithm is to solve problem C in the concave region (see Fig. 5.1). In this section, we present a distributed algorithm for this purpose, 90 where the users are involved in power allocation to reduce the control and computation overhead on the BS. In the concave region, we have problem D as (D) maximize summationdisplay n?U log(1 +?n(t)) (5.19) subject to: ?n(t) = LnPn(t)?P ?P n(t) +An , for all n (5.20) Pminn (t) ?Pn(t) ? min{Pmaxn ,P?n},for all n (5.21) summationdisplay n?U Pn(t) ?Ptot, (5.22) where Ptot ? ?P is the total power budget for the links in the concave region. For brevity, we define Pthn = min{Pmaxn ,P?n} and drop the time slot index t in the following analysis. Introducing non-negative Lagrange multipliers ?n,?n, and? for constraints (5.21) and (5.22), respectively, we obtain the Lagrange function as L(vectorP,vector?,vector?,?) (5.23) = summationdisplay n?U bracketleftbigg log parenleftbigg 1 + LnPn?P ?P n +An parenrightbigg +?n(Pn ?Pminn ) bracketrightbigg + summationdisplay n?U bracketleftbig? n(Pthn ?Pn) bracketrightbig+? parenleftBigg Ptot ? summationdisplay n?U Pn parenrightBigg = summationdisplay n?U bracketleftbigL n(Pn,?n,?n,?)+(?nPthn ??nPminn ) bracketrightbig+?P tot, where Ln(Pn,?n,?n,?) = log parenleftbigg 1 + LnPn?P ?P n +An parenrightbigg + (?n ??n ??)Pn. (5.24) Since Ln only depends on user n?s own parameters, we have the dual decomposition for each user n. For given Lagrange multipliers (or, prices) ??n, ??n, and ??, we have the following subproblem for each user n. ?Pn( ??n, ??n,??) = [Pminn ?Pn ?Pthn ]argmaxLn(Pn, ??n, ??n,??), for all n. (5.25) 91 Subproblem (5.25) has a unique optimal solution due to the strict concavity of Ln. We use the gradient method [14] to solve (5.25), where user n iteratively updates its power Pn as: Pn(l+ 1) (5.26) = [Pn(l) +?(l)?nLn(Pn)]? = bracketleftbigg Pn(l) +?(l) Ln( ?P +An) ( ?P ?Pn +An)( ?P + (Ln ?1)Pn +An) +?(l)(?n ??n ??) bracketrightbigg? , where [?]? denotes the projection onto the range of [Pminn ,Pthn ]. The update stepsize ?(l) varies in each step l and is determine by the Armijo Rule [14]. Due to the strict concavity of Ln, the series {Pn(1),Pn(2),???} will converge to the optimal solution ?Pn as l??. For a given optimal solution for problem (5.25), vector?P = [ ?P1,??? , ?PN]T, the master dual problem is as follows: minimize L(vector?P,vector?,vector?,?) (5.27) subject to: ?n,?n,? ? 0, for all n. (5.28) Since the objective function (5.27) is differentiable, we also apply the gradient method to solve the master dual problem [14], where the Lagrange multipliers are iteratively updated as ? ???? ? ???? ? ?n(l+ 1) = [?n(l)???(l)? ?L(vector?,vector?,?)??n ]+, for all n ?n(l+ 1) = [?n(l)???(l)? ?L(vector?,vector?,?)??n ]+, for all n ?(l+ 1) = [?(l)???(l)? ?L(vector?,vector?,?)?? ]+, (5.29) where [?]+ denotes the projection onto the nonnegative axis. The update stepsizes are also deter- mined by the Armijo Rule [14]. As the dual variablesvector?(l),vector?(l),?(l) converge to their stable values as l??, the primal variables vector?P will also converge to the optimal solution [100]. 92 Algorithm 6: Distributed Power Control Algorithm 1 BS sets l = 0 and prices ?n(l),?n(l),?(l) equal to some nonnegative initial values for all n; 2 BS broadcasts the prices to the selected users; 3 Each user locally solves problem (5.25) as in (5.26) to obtain its requested power; 4 Each user sends its requested power to the BS; 5 BS updates prices ?n(l),?n(l),?(l) as in (5.29) and broadcasts new prices ?n(l + 1),?n(l + 1),?(l + 1) for all n; 6 Set l = l + 1 and go to Step 3, until the solution converges; The distributed algorithm is given in Algorithm 6, where the above procedures are repeated iteratively. The BS first broadcasts Lagrange multipliers to the users. Each user updates its re- quested power as in (5.26), using local information Pminn , Pmaxn , P?n, An, Ln, and BS peak power ?P. Each user then sends its requested power back to the BS, and the BS will updates the Lagrange multipliers as in (5.29). And so forth, until the optimal solution is obtained. 5.5 Simulation Results We evaluate the proposed algorithms with MATLAB simulations, where the deterministic VBR traffic model and the optimization solution algorithms are implemented. We use a cellular network with 20 users;1 the network topology is illustrated in Fig. 5.2. The downlink bandwidth is 1 MHz. The path gain averages are Gn = d?4n , where dn is the physical distance from the BS to user n. The downlink channel is modeled as log-normal block fading with zero mean and variance 8 dB [50]. The processing gains are set to Ln = 128 for all n. The distance dn is uniformly distributed in [100m, 1000m]. The device temperature is T0 = 290 Kelvin and the equivalent noise bandwidth is Bw = 1MHz. The BS peak power constraints is set to ?P = 10 Watts. We use three VBR movies traces, Star Wars, NBC News, and Tokyo Olympics, from the Video Trace Library maintained at Arizona State University [139]. We plot the sizes of the first 100 frames of the NBC News video sequence in Fig. 5.3, to illustrate the high variation of VBR video frame sizes, which makes it very challenging to develop accurate mathematical models. Each playout buffer is set to 1.5 times of the largest frame size in the requested VBR video. 1The number of users/links in the cellular network is chosen according to the resource specified in the simulation: bandwidth and the total BS power limit. 93 Figure 5.2: Topology of the cellular network. 0 10 20 30 40 50 60 70 80 90 1000 1 2 3 4 5 6 7 8 x 10 4 Frame Fr am e s ize (b its ) Figure 5.3: The sizes of the first 100 frames of the NBC News sequence. In the simulations, we have 7 user streaming NBC news, 7 users streaming Star Wars, and 6 users streaming Tokyo Olympics. The proposed power allocation algorithm is executed at the beginning of each time slot. In Fig. 5.4, we plot the cumulative consumption, overflow and trans- mission curves for NBC News transmitted to user 2. The top sub-figure is the overview of 10,000 94 0 2000 4000 6000 8000 100000 0.5 1 1.5 2 2.5 x 10 5 Frame Index Cu mu lat ive bi ts (kb its) 2620 2625 2630 2635 2640 4.88 4.9 4.92 4.94 4.96 4.98 x 104 Frame Index Cu mu lat ive bi ts (kb its) Cumulative consumption curve Cumulative overflow curve Cumulative transmission curve Figure 5.4: Transmission schedule for video NBC News to user 2. frames. We also plot the curves from frame 2,620 to 2,640 in the bottom sub-figure. We observe that the cumulative transmission curve X(t) is very close to the cumulative overflow curve B(t), indicating that the algorithm always aim to maximize the transmission rate as allowed by the buffer and power constraints. The playout buffers are almost fully utilized most of the time. There is no playout buffer overflow and underflow for the entire range of 10,000 frames. Among the NBC News frames, frame 2,625 is the largest frame. We let seven out of the 20 links playout this largest frame simultaneously at time slot 2,625 in the simulation. There is no buffer underflow under such heavy load. In Fig. 5.5, we plot the power allocation and price updates for all the 20 links in one of the 10,000 time slots. The power and prices converges in around 70 steps. The converged power vector is vector?P = [0.0022, 1.396, 0.0356, 0.0024, 1.396, 0.0351, 0.0016, 1.396, 0.0356, 0.0026, 1.396, 0.0356, 0.0023, 1.396, 0.0356, 0.0018, 1.396, 0.0356, 0.0034, 1.394] Watts. Note that with the distributed algorithm, the computation in each iteration only consisting updating power or price as in (5.26) and (5.29), which takes only a negligible amount of time. The 70-step convergence time is very small comparing to the power control in cellular standards (e.g., 1500 Hz for UMTS power 95 0 20 40 60 800 1 2 3 Steps Power (Watts) (a) Transmit powers 0 20 40 60 800 0.5 1 Steps ? (b) Lagrange mulipliers ? 0 20 40 60 800 0.5 1 Steps ? (c) Lagrange mulipliers ? 0 20 40 60 800 0.5 1 1.5 Steps ? (d) Lagrange muliplier ? Figure 5.5: Convergence of power allocation and Lagrange multipliers. control [140]). Since the gradient method is used, the convergence of the algorithm is dependent on the gradients, which further depend on the system parameters such asLn andAn. Another main factor for the convergence speed is the choice of the stepsize. As discussed, we use Armijo Rule to determine step size, in which the stepsize evolves according to the difference of the target values between steps. Finally, we compare the proposed algorithm with a diversity-aware power allocation scheme, where the BS allocates power according to channel quality. With this scheme, the best channel n will be assigned power to achieve its maximum required power Pmaxn (t). Then the second best channel will be allocated power until its maximum required power is achieved, and so forth until all of ?P is allocated. In this simulation, we increase the number of users to 50 to stress the capacity of the cellular network, such that the system is close to saturate. The purpose is to show the performance of the algorithms under a nearly congested scenario, which is more interesting in performance analysis than an under-load scenario. 96 0 1000 2000 3000 4000 5000 6000 7000 8000 9000 100000 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Frame Index Av era ge pl ay ou t b uff er uti liz ati on Proposed power control algorithm Diversity based algorithm Figure 5.6: Average playout buffer utilization for the entire video sequence (10000 frames). We compare the algorithms by their average playout buffer utilization. In Fig. 5.6, we plot the average buffer utilizations achieved by the proposed scheme and the diversity-aware scheme for the entire video sequence. A zoomed in version is presented in Fig. 5.7 from frames ranging from 2,000 to 2,500. It can be seen that the proposed algorithm consistently achieves high buffer utilization, ranging from 60% to 100%. The diversity scheme achieves buffer utilization lower than 50% for frames from 2,000 to 2,250. Such considerably higher buffer utilization translates to better video quality: there is no buffer overflow or underflow for proposed algorithm, while there is buffer underflow in 17% of the playout frames for the diversity scheme. 5.6 Related Work Most of the prior work on VBR video streaming consider wired networks, which can be clas- sified according to their traffic models, i.e., statistical or deterministic models. With the former approach, stochastic models are developed to capture the burstiness in VBR traffic. In [131, 132], the authors observed the long-range-dependence in VBR video traffic and modeled the autocorre- lation with self-similar processes. This class of work provides valuable insights on the nature of 97 2000 2050 2100 2150 2200 2250 2300 2350 2400 2450 25000.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Frame Index Av era ge pl ay ou t b uff er uti liz ati on Proposed power control algorithm Diversity based algorithm Figure 5.7: Average playout buffer utilization for frames 2000 to 2500. VBR video traffic. The stochastic models can be incorporated in quality of service (QoS) mecha- nisms for VBR videos, and for traffic synthesizing in simulations [133]. With the deterministic approach, the piecewise-constant-rate transmission and transport (PCRTT) method was used, aiming to optimize one or more objectives while preserving continuous video playout. In [135], Liew and Chan proposed bandwidth allocation schemes for dynamically shar- ing a CBR channel among multiple VBR video streams, either i) to minimize the total receiver buffer size, or ii) to avoid underflow and overflow for a given playout buffer size. In [95], Salehi et al. considered smoothing VBR video over a CBR link and developed an effective algorithm to achieve the greatest smoothness in rate. In [141], McManus and Ross introduced a dynamic pro- gramming framework to set PCRTT rates and intervals to optimize different objective functions. These techniques do not directly apply to our problem of VBR over wireless networks, due to the fundamental difference between wireless and wired CBR links. The downlink power allocation problem was studied in [50, 137], aiming to obtain the power allocation that maximizes a properly defined system utility. A distributed algorithm based on dynamic pricing and partial cooperation was proposed. Deng, Webera, and Ahrens [142] studied 98 the achievable maximum sum rate of multi-user interference channels. These papers provide the theoretical foundation and effective algorithms for utility maximization of downlink traffic, but the techniques used cannot be directly applied for VBR video over wireless networks with buffer and delay constraints. In [54, 143], the authors studied the problem of one VBR stream over a given time-varying wireless channel. In [143], it was shown that the separation between a delay jitter buffer and a decoder buffer is in general suboptimal, and several critical system parameters were derived. In [54], the authors studied the frequency of jitters under both network and video system constraint and provided a framework for quantifying the trade-offs among several system parameters. In this chapter, we jointly consider power control in wireless networks, playout buffers, and video frame information, and address the more challenging problem of streaming multiple VBR videos, and present a cross-layer optimization approach that does not depend on any specific channel or video traffic models. 5.7 Conclusions We developed a downlink power allocation model for streaming multiple VBR videos in a cel- lular network. The model considers interactions among downlink power control, channel interfer- ence, playout buffers, and VBR video traffic characteristics. The formulated problem aims at max- imizing the total transmission rate under both peak power and playout buffer overflow/underflow constraints. We presented a two-step approach for solving the problem and a distributed algorithm based on the dual decomposition technique. Our simulation studies validated the efficacy of the proposed algorithms. 99 Chapter 6 Downlink Power Control for Variable Bit Rate Video over Multicell Wireless Networks 6.1 Introduction In this chapter, we extend power control in variable bit rate (VBR) video streaming to mul- ticell wireless networks scenario. We consider video streaming over a multicell wireless network, a wireless network architecture widely deployed all over the world. We consider the typical case of downlink video transmissions. For the multicell system, generally intra-cell interference can be effectively controlled with precise synchronization or the use of guard times. The capacities of the downlinks are mainly limited by the inter-cell interference due to simultaneous base station (BS) transmissions using the same channel. Therefore, effective downlink power control is necessary to support concurrent videos. In this chapter, we presented a problem formulation that considers downlink power control, inter-cell interference, VBR video characteristics, and playout buffer requirements. The objective is to achieve high playout buffer utilization, under playout buffer underflow and overflow con- straints and peak power constraint. This is a nonlinear nonconvex problem to which traditional convex optimization techniques [59] and low- or high- Signal to Interference-plus-Noise Ratio (SINR) approximations [59, 138] do not directly apply. We first derive the condition of the existence of feasible power assignments, which can achieve downlink capacities to guarantee no buffer underflow and overflow. We then develop a central- ized algorithm that can produce solutions with bounded optimality gap. Specifically, we use the Reformulation-Linearization Technique (RLT) to obtain a linear programming (LP) relaxation of the original problem. Solving this LP relaxation yields an upper bound to the original problem. Interestingly, since the constraints are preserved in the relaxation procedure, the upper-bounding 100 solution is also feasible to the original problem; the corresponding objective value with this solu- tion provides a lower bound to the global optimum. The LP relaxation is then incorporated into the branch-and-bound framework to obtain a centralized algorithm, which can produce a solution within the (1-?) range of the global optimal. To simplify computation and control, we also develop a distributed algorithm based on dis- tributed constrained power control (DCPC) [48], where each BS iteratively updates transmit power based on feedback of measured SINR at the target receiver. It is shown that with DCPC, the power vector converges to a unique power vector that can achieve the goal of maximizing playout buffer utilization and avoiding playout buffer underflow and overflow. We evaluate the proposed al- gorithms with simulations using VBR video traces [139] and fading channels. The distributed algorithm is shown to achieve a performance very close to that of the centralized algorithm. Both algorithms are demonstrated to be highly effective for streaming VBR videos over multicell wire- less networks. In the reminder of this chapter, we present the problem formulation in Section 6.2. We de- scribe a centralized algorithm in Section 6.3 and a distributed algorithm in Section 6.4. Simulation results are presented in Section 6.5 and related work is discussed in Section 6.6. Section 6.7 con- cludes this chapter. The notation used in this chapter are summarized in Table 6.1. 6.2 Problem Statement 6.2.1 Network and Video System Model We consider the downlinks of an M-cell wireless network as shown in Fig. 6.1. In each cell, a BS streams video to mobile users in the cell, each allocated with a downlink channel. A channel is a spectral resource slot, the nature of which depends on the specific multiple access technique adopted for the multicell network. Without loss of generality, we assume that the downlink chan- nels within a cell are orthogonal (e.g., due to perfect synchronization of spreading codes or use of guard times). The main interference at a user stems from the concurrent downlink transmissions 101 Table 6.1: Notation Table for Chapter 6 Symbol Description M total number of cells (or, BS?s) U set of users sharing the same channel Li total number of frames for user i video bi playout buffer size of user i Di(t) cumulative consumption curve at user i Xi(t) cumulative transmission curve at user i Bi(t) cumulative overflow curve at user i Pm(t) transmit power of BS m in time slot t vectorP(t) BS transmit power vector in time slot t ?P peak power constraint for the BS?s vectorP? optimal power vector to the LP relaxation Gmk path gain from BS k to user unm Bw channel bandwidth ? duration of a time slot ?m noise power at user unm Cm capacity of the cell m downlink Cminm (t) min. rate for user unm without underflow ?Cminm (t) the largest value of Cminm (t) ?m(t) SINR at user unm ?minm (t) minimum SINR corresponding to Cminm (t) ??minm (t) SINR corresponding to ?Cminm (t) ?maxm (t) max. SINR for user unm without overflow ?thm receiver sensitivity at user unm A matrix of path gain ratios defined in (D.5) ?min defined as diag{?min1 (t),?min2 (t),??? ,?minM (t)} ??min defined as diag{??min1 (t),??min2 (t),??? ,bar?minM (t)} ? M ?M matrix defined as (??min ??min) ?tarm target user unm SINR for distributed alg. ??tar defined as diag{?tar1 (t),?tar2 (t),??? ,?tarM (t) ?m vector of elements ?m/Gmm um RLT substitution variable for logarithm terms vmk RLT substitution variable for quadratic terms ?, ? parameters for the distributed algorithm in neighboring cells that use the same channel. There is a need for the BS?s to adopt power control to mitigate such inter-cell interference. We consider the problem of streaming multiple VBR videos in the multicell network. We assume the wired segment of a video session path is reliable with sufficient bandwidth, while the last-hop wireless link is the bottleneck [144]. Thus the corresponding video data is always 102 Figure 6.1: A multicell wireless network with concurrent VBR video sessions. The inter-cell interference experienced by the central cell user is illustrated. available at the BS before the scheduled transmission time. We adopt the deterministic VBR video model in 4.2. 6.2.2 Problem Formation For the multicell wireless video network, consider a specific channel and let U = {un1,un2, ??? ,unM} denote the set of users sharing the channel, where unm is the user in cell m.1 Let the BS transmit power vector be vectorP(t) = [P1(t),P2(t),??? ,PM(t)]T in time slot t. The capacity of the downlink from BS m to user unm, denoted as Cm(t), depends on the SINR at unm, which can be written as ?m(vectorP(t)) = G m mPm(t)summationtext knegationslash=mG m k Pk(t) +?m , (6.1) where Gmk is the path gain from BS k to user unm and ?m is the noise power at unm. We assume slow-fading channels such that the path gains do not change within each time slot [50], but vary over different time slots following a certain distribution. The downlink capacity Cm(t) also de- pends on the channel bandwidth Bw and the transceiver design, such as modulation and channel 10-1 index variables can be used to model the case where no user uses the channel in some cells, but are omitted for brevity. 103 coding. Without loss of generality, we use the upper bound as predicted by Shannon theorem: Cm(vectorP(t)) = Bw log parenleftBig 1 +?m(vectorP(t)) parenrightBig . (6.2) The impact of fading channels is incorporated in the SINR in (6.2). For practical systems, the achievable capacity may be a fraction of Cm(vectorP(t)), but this part is omitted for brevity. Once the link capacity is determined, Cm(t)? video bits will be delivered to user unm in that time slot. The cumulative transmission curve Xm(t) can be written as Xm(0) = 0; Xm(t) = Xm(t?1) +Cm(t)?. (6.3) Assume peak power constraint 0 ? Pm ? ?P, for all m. The problem is to determine the transmit power vector vectorP(t), for 0 LB then 10 Set sol = vectorP?l and LB = LBl ; 11 if UB ? (1 +?)LB then 12 stop with solution sol ; 13 else 14 remove all probs k in S with UBk ? (1 +?)LB ; 15 end 16 end 17 Partition ; 18 For Prob l, find the maximum relaxation error among all RLT variables, e.g., maxm,k{|?mPk ?vmk|} ; 19 Evaluate the following condition: (?maxm ??minm )?min{??m??minm ,?maxm ???m}? (Pmaxm ?Pminm )?min{P?m?Pminm ,Pmaxm ?P?m}; 20 if true then 21 partition [?minm ,?maxm ] into [?minm ,??m] and [??m,?maxm ] ; 22 else 23 partition [Pminm ,Pmaxm ] into [Pminm ,P?m] and [P?m,Pmaxm ] ; 24 end 25 Bounding ; 26 Solve the partitioned probs l1 and l2 to get solutions soll1, soll2 and bounds UBl1, UBl2, LBl1, LBl2 ; 27 Remove Prob l from S ; 28 if (1 +?)LB Dm(t). The evolution of the BS transmit powers are plotted in Fig. 6.5.2, where after 23 steps, all the transmit powers converges to a value between 0 and ?P = 1 Watt. The converged power vector is vectorP? = [0.0023, 0.208, 0.185, 0.0013, 0.163, 7.1?10?04, 0.188] Watt. The evolution of the bit rates are plotted in Fig. 6.5.2. It is interesting to see the data rates converge faster than the transmit powers in this case. All the data rates reach stable values after a few steps. 121 6.5.3 Empirical Performance Evaluation We evaluate the performance of the proposed schemes by comparing them with the following two schemes. ? A round-robin scheme where the BS allocates power in a quality of service (QoS) based round-robin fashion, which favors the session that would suffer buffer starvation if no trans- mission is scheduled. When a specific BS is selected for transmission, it transmits the video with maximum power without overflowing the client buffer, and all its neighbors remain silent in the same frame-time slot. ? W-Lazy, as described in Section 6.2.3. First, we investigate the average buffer utilization at end of each time slot. When underflow happens, the missing frame is discarded, and the next frame will be scheduled for the transmission in the next time slot. We observe that the proposed RLT and DCPC schemes achieve higher average buffer utilization than the other two schemes. Fig. 6.10 shows the average buffer utilization from frame-time slot 1,600 to 1,700. We find that the buffer utilization of RLT and DCPC fluctuate around 90% mostly, while the utilization of the Round-robin scheme is in the range of 50% to 80%. We also find that the W-Lazy scheme always achieves a zero buffer utilization,since it only transmits each frame as late as possible in each time slot. At the end of a time slot, all the data will be comsumed by the user and the buffer is left empty. We then compare the average number of underflow events in Table 6.2. we find RLT achieves underflow free transmission, while the number of underflow events for DCPC is negligible in the simulations. This is because both schemes aim to transmit as much video data as possible under the feasible condition in each frame-time slot. The extra video data transmitted will be in the playout buffer to provide a cushion to future large frames or network dynamics. On the other hand, both Round-robin and W-Lazy suffers a large number of underflow events. We also illustrate the buffer underflow events in the period from 1,680 to 1,700 in Fig. 6.11. The red dot circles indicate the buffer underflow. It can be seen that the cumulative transmission curve lies below the cumulative 122 1600 1620 1640 1660 1680 17000 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Frame-Time Ave rag e b uff er Uti liza tio nu RLT DCPC Round-Robin W-Lazy Figure 6.10: Average buffer utilization of the four schemes. Table 6.2: Number of underflow events RLT DCPC Round-robin W-Lazy Mean 0 0.2 516 1076 Conf. Int. [0,0] [?0.355,0.755] [442,591] [514,1637] consumption curve when buffer underflow events occur. This results in an infeasible transmission schedule, which causes frozen playout. The average power consumption of the schemes are shown in Fig 6.12. W-Lazy has the lowest power consumption. Due to the variation of frame size and network condition, the transmission of W-Lazy are infeasible in many time slots. To prevent the divergence of power allocation, some video sessions should be paused and the power savings of W-Lazy are achieved by pausing video transmissions. However, this is at the cost of significantly more buffer underflow events, which are undesirable for user experience. The Round-robin scheme tries to transmit as much video data as possible. However, it chooses a session greedily and pauses other unselected video sessions. This also causes many underflow events for the unselected sessions. Also, due to the round robin fashion and limited buffer size, when the unselected session become selected, its low buffer utilization will lead to a larger power consumption in order to fill the buffer, especially when it misses the previous good channel condition and the channel condition is worse at the current time slot. Thus, the 123 1680 1685 1690 1695 1700 2.7 2.72 2.74 2.76 2.78 x 104 Frame-time Cu mu lat ive bi ts (kb its) (a) RLT - NBC News Cumulative service curve Cumulative overflow curve Cumulative transmission curve 1680 1685 1690 1695 1700 2.7 2.72 2.74 2.76 2.78 x 104 Frame-time Cu mu lat ive bi ts (kb its) (b) DCPC - NBC News Cumulative service curve Cumulative overflow curve Cumulative transmission curve 1680 1685 1690 1695 1700 2.7 2.72 2.74 2.76 2.78 x 104 Frame-time Cu mu lat ive bi ts (kb its) (c) Round-Robin - NBC News Cumulative service curve Cumulative overflow curve Cumulative transmission curve 1680 1685 1690 1695 1700 2.7 2.72 2.74 2.76 2.78 x 104 Frame-time Cu mu lat ive bi ts (kb its) (d) W-Lazy - NBC News Cumulative service curve Cumulative overflow curve Cumulative transmission curve Figure 6.11: Illustration of underflow events. proposed algorithms achieve the better balance between the energy consumption and the quality of experience of the video streaming. 6.6 Related Work A thorough review in VBR video model and VBR video streaming over wired networks has been explored in 5.6. Due to the fundamental difference between wireless and wired CBR links, these techniques do not directly apply to our problem of VBR over the multicellular wireless networks. In this chapter, we take advantage of power control in wireless networks to adjust the capacity of wireless links based on video frame size information, such that we can jointly optimize the transmission of multiple VBR video sessions over multiple VBR channels. Our approach does not depend on any channel or video traffic models, and can be adopted for CBR video as well. Power control is an important problem for interference-limited wireless networks. Most prior work focuses on maximizing network utility in the forms of SINR or bit rate [48,59,138]. In [48], Grandhi, Zander, and Yates presented centralized and distributed power control algorithms for 124 1 2 3 40 0.002 0.004 0.006 0.008 0.01 0.012 0.014 0.016 0.018 Schemes (1: RLT 2: DCPC 3: Round-Robin 4: W- Lazy) Ave rag e p ow er co nsu mp tio n ( W) Figure 6.12: Average power consumption. achieving target SINRs in a cellular network. In [59], Chiang studied the problem of joint power control and congestion control, aming to maximize the throughput of TCP-Vegas over an ad hoc network. Gjendemsj et al. [138] presented centralized binary power control algorithms for max- imizing the sum rate over multiple interfering links. Although laid out the theoretical foundation and developed effective algorithms, these techniques cannot be directly applied for VBR video over multicell wireless networks with buffer and delay constraints. 6.7 Conclusions We studied downlink power control for VBR video streaming in multicell wireless networks. The problem formulation considers downlink power control, inter-cell interference, VBR video characteristics, and playout buffer requirements. We developed a centralized algorithm that can provide (1-?)-optimal solutions, and a fast distributed algorithm that only needs local informa- tion. The algorithms are evaluated with extensive simulations with VBR video traces and fading channels, and are demonstrated to be effective for streaming VBR videos over multicell wireless networks. 125 Chapter 7 Energy Efficiency on Downlink Multiuser VBR Video Streaming 7.1 Introduction In this chapter, we present a power efficient downlink power control framework in wireless system with orthogonal channels for variable bit rate (VBR) streaming with focus on minimizing the power consumption for the total streaming period. We consider the problem of optimal power allocation for multiuser VBR video streaming in the downlink of a cellular network with orthog- onal channels. We assume the wireline segment of a video session path is reliable with sufficient bandwidth, while the last-hop wireless link is the bottleneck. Thus the corresponding video data is always available at the BS before the scheduled transmission time. We adopt a deterministic model for VBR video traffic that incorporates video frame and playout buffer characteristics. The BS allocates a transmit power to each user in each time slot. The problem is to find the optimal power control schedule to stream the requested VBR video data to users, such that the total trans- mit power consumption can be minimized, while minimizing the buffer underflow and overflow events. The problem is formulated as a constrained stochastic optimization problem. We show that the problem fits well with majorization theory, which concerns with partial ordering of real vectors and order-preserving functions. It answers the question of how to order vectors with nonnegative real components and its order-preserving functions [13]. A majorization-based solution framework is developed to tackle the problem. First, we prove that the objective function of the formulated prob- lem is Schur-convex with the order-preserving property [13]. Second, we investigate the case of a single VBR video session with relaxed peak power constraint. We develop a majorization-based power optimal algorithm with low complexity, and prove the power optimality of the proposed 126 algorithm and the uniqueness of the global optimum. We also demonstrate that the proposed algo- rithm is smoothness optimal as well. Third, we investigate the case of multiuser VBR streaming, where power allocations for the users are coupled with the BS peak power constraint. We develop a heuristic algorithm that selectively suspends some video sessions, which will not incur underflow in the next time slot, when the peak power constraint is violated. Finally, the proposed algorithms are evaluated with trace-driven simulations [139], and are shown to achieve considerable power savings and improved video quality over a conventional ?lazy? scheme [136]. The rest of this chapter is organized as follows. The system model and problem statement are presented in Sec- tion 7.2. We transform the problem into a majorization problem in Section 7.3. The proposed algorithms are described in Section 7.4 and simulation results are presented in Section 7.5. We review related work in Section 7.6. Section 7.7 concludes this chapter. The notation used in this chapter is summarized in Table 7.1. 7.2 System Model 7.2.1 Network and Video Source Model We consider the downlink in a cellular network, as shown in Fig. 7.1. There are N active mobile users in a set U = {1,2,??? ,N} in the cell that subscribe to the video service. A BS transmits multiple VBR videos to the mobile users. Each user occupies a downlink channel, which is a spectral/time resource slot, the nature of which depends on the specific multiple access tech- nique adopted. We assume that the downlink channels within a cell are orthogonal, due to perfect synchronization of the spreading codes or the use of guard times or frequencies. We further as- sume the wireline segment of a video session path is reliable with sufficient bandwidth, while the last-hop wireless link is the bottleneck. Thus the corresponding video data is always available at the BS before the scheduled transmission time. We adopt a deterministic VBR video model, which was presented in the Section 4.2. The BS allocates a transmit power to each user in each time slot. Let vectorP(t) = [P1(t),??? ,PN(t)] be the power allocation in time slot t. The Signal to Interference-plus-Noise Ratio (SINR) at user 127 Table 7.1: Notation Table for Chapter 7 Symbol Description N number of mobile users in the cell U set of users bn playout buffer size at user n Tn total number of frames of the user n video ?n total number of bits of the use n video Dn(t) cumulative consumption curve of user n Bn(t) cumulative overflow curve of user n Xn(t) cumulative transmission curve of user n Pn(t) transmit power of user n in time slot t vectorP(t) power allocation in time slot t ?n(t) SINR at user n in time slot t Gn(t) path gain from BS to user n in time slot t ?n(t) noise power at user n in time slot t cn(t) downlink data rate of user n in time slot t Bw channel bandwdith ? a transceiver dependent constant ?P peak power constraint vectorCin the i-th feasible transmission schedule vectorC?n the optimal solution to (7.9) vectorCoptn an evenly distributed rate vector vectorC1n an auxiliary schedule used in Theorem 7.2 proof ?(?) a mapping function RTn ?R defined in (7.12) vectorX,vectorY,vectorZ n-dimensional nonnegative vectors Cmax(t),Cmin(t) rate of probe lines U(vectorC) smoothness utility function n in time slot t can be written as ?n(t) = Gn(t)Pn(t)/?n(t), (7.1) where Gn(t) is the path gain from BS to user n and ?n(t) is the noise power at user n in time slot t. We assume block fading channels, where the Gn(t)?s are i.i.d. random variables with a certain distribution, for t = 1,??? ,Tn [50]. The downlink data rate can be written as cn(t) = Bw log(1 +??n(Pn(t))), where Bw is the channel bandwidth and ? depends on the transceiver design, such as modulation and channel coding. Without loss of generality, we use the Shannon 128 Mobile user BS Video server High speed wired link Figure 7.1: Cellular network and video streaming system model. capacity as an upper bounding approximation: cn(t) = Bw log(1 +?n(Pn(t))). (7.2) Once the link capacity is determined, cn(t)? bits of video data will be delivered to user n in that time slot. The cumulative transmission curve Xn(t) can be written as Xn(0) = 0; Xn(t) = Xn(t?1) +cn(t)?. (7.3) A feasible transmission schedule should cause neither playout buffer underflow nor overflow, i.e., satisfying Dn(t) ?Xn(t) ?Bn(t), for all t,n. (7.4) 7.2.2 Power-Aware Transmission Scheduling As discussed, we jointly consider the traffic source model in the application layer and power allocation in the physical layer. We adopt cross-layer design to compute the optimal feasible transmission schedule {Xn(t), 0 min{Cmax,Cmax(t)} then 12 Select Cmin from tstart to tstop = tc1 ; 13 else if Cmax < max{Cmin,Cmin(t)} then 14 Select Cmax from tstart to tstop = tc2 ; 15 else 16 t+ + ; 17 CONTINUE ; 18 end 19 tstart = tstop,tstop = tc1 = tc2 = tstart + 1,t = tstart + 1,Cmin = 0,Cmax = ? ; 20 end 21 while more video frames to transmit do 22 Measure the channel gain of the time slot, calculate power using (7.5), and transmit the video data ; 23 end After the transmission schedule for [tstart,tstop) is determined, we set tstart = tstop and repeat the above procedure to find the schedule for the next time interval. In Algorithm 9, the algorithm probes for the longest feasible rate starting from tstart in Steps 4?10. In Steps 11?14, the transmis- sion rate for the interval [tstart,tstop) is determined depending on which of the two cases it is as illustrated in Fig. 7.2. Steps 16?17 are for the case that the rate does not change in the time slot. Step 19 resets the variables to start the computation for the next segment of Xn(t). Finally, Steps 21?23 transmit the frames following the computed schedule. 134 7.4.2 Optimality Proof We next show that the algorithm given in Algorithm 9 computes the optimal solution to prob- lem (7.9). Theorem 7.2. The power minimization algorithm PMA is optimal to problem (7.9). Corollary 7.2.1. The power optimal transmission scheme vectorC?n is unique for given Bn(t) and Dn(t). Corollary 7.2.2. The computational complexity of Algorithm PMA is O(T2n). The proofs of above conclusions are similar to the proofs of in Chapter 2 and thus omitted for brevity. Note that Algorithm PMA is executed during the session setup time. It only incurs a small initialization delay. In our simulations with VBR video traces, we find the execution time is usually negligible. When the channel statistics are changed (i.e., due to handoff), the schedule will be recomputed for the remaining video frames. Corollary 7.2.3. The power optimal transmission schedule vectorC?n is also the smoothest one among all feasible schedules. Proof. The proof of Corollary 7.2.3 is given in Appendix E.2. 7.4.3 Multiuser Video Transmissions We now consider problem (7.6) to compute transmission schedules forN VBR video sessions, which are coupled by the peak power constraint (7.8). Due to the peak power constraint and random channel gains, the individually calculated transmit powers may violate (7.8) in some time slots. The problem is further complicated because of the random channel gains, which is not available a priori (except for the statistics of the channels). 135 Algorithm 10: Power Minimization Algorithm for Multiuser Videos (PMA-m) 1 Execute power minimization algorithm PMA to compute transmission schedules for all active users ; 2 while there are more video frames to transmit do 3 Measure channel gains of the current time slot and calculate the transmit powers using (7.5) ; 4 if peak power constraint is violated then 5 Select the users who won?t have underflow even without transmission in this time slot ; 6 Sort the selected users in decreasing order of powers ; 7 while peak power constraint is not satisfied do 8 Decrease the power of the selected users by the order ; 9 end 10 end 11 Transmit the videos and recalculate the optimal transmission scheme for the paused mobile users for the next time interval ; 12 end To solve problem (7.6), we develop a heuristic algorithm, termed PMA-m, as presented in Algorithm 10. The PMA-m algorithm uses PMA to compute transmission schedules for all active users. Then based on current channel state information, it computes the power needed to achieved the rate for each user, and checks the peak power constraint summationtextn?Un Pn(t) ? ?P. If the constraint is not violated, each user?s video data will be transmitted at the computed power. Otherwise, as in Steps 4?10, PMA-m selects those users who will not have buffer underflow if their transmissions are suspended in the following time slot, and sort them in the deceasing order of their required powers. Starting with the first user, PMA-m decreases the powers of the users in the list; if the first user?s power reaches 0 W but the peak power constraint is till not satisfied, PMA-mstarts to reduce the power of the second user in the list; and so forth until the peak power constraint is satisfied. In some extremely severe channel conditions, the total power ?P cannot even support the minimum required bit rate for all the users. Some users have to be paused and the current frames be discarded. The corresponding playout of such a user will be frozen until the next time slot. Finally, the transmission schedules for the suspended users will be recomputed using PMA as in Step 11 and the above procedure is repeated. 136 7.4.4 Application to Interactive Video Streaming The ubiquitous spread of mobile devices and trend of multimedia applications require the interactive service be supported [148?150]. Thus, it is necessary to investigate how to apply the proposed schemes to the case of interactive video streaming. Interactive video is a relatively new and still evolving technology with a broad scope. We focus on the three interactive video streaming related typical scenarios in the following, and show that the proposed schemes are applicable for these scenarios for improved performance. First, for quick response to user inputs, many interactive video streaming applications have tight delay requirements. Such stringent delay requirements have two implications: (i) unlike stored video, not all the future frame sizes are known now; only the frames sizes for a short look- ahead period (LAP) are known. (ii) the playout buffer sizes cannot be large, since a large buffer usually introduces large delay. Clearly, the proposed schemes can be applied to the look-ahead time period for which the future frame sizes are known, to compute a schedule for the near future. Furthermore, given the small playout buffer size, usually a chosen transmission rate won?t last very long into the future before it hits either the cumulative overflow curve or the cumulative consumption curve (see Fig.4). Therefore the impact of limited look-ahead period would be small or moderate at best. Second, many interactive video applications support VCR controls [151]. For example, a user may slide the progress bar of the video player to replay or skip a part of the video. This case is equivalent to a change in the cumulative overflow and consumption curves. The proposed algorithms will seek to the new start frame that the user requires and recalculate the transmission schedules for the following frames. Third, in both ?exploratory? online interactive videos (where a user can move through dif- ferent locations in a space or view an object from different angles) and video click throughs [152] (where a user can click objects in the video that are linked to other contents), new data will be transmitted after each user input. These are equivalent to the case of VCR controls. A new set 137 Table 7.2: VBR Video Trace Statistics Video Trace Average Rate Frame Rate Average PSNR Star Wars 331,681 b/s 30 f/s 44.62 dB NBC News 784,840 b/s 30 f/s 38.80 dB Tokyo Olympics 509,191 b/s 30 f/s 41.46 dB Terminator 2 5,085,453 b/s 30 f/s 43.92 dB From Mars to China 4,849,711 b/s 30 f/s 39.26 dB Sony Demo 5,803,650 b/s 30 f/s 44.07 dB of cumulative overflow and consumption curves will be delivered (derived from the new data re- quested) and new schedules computed. In Section 7.5.1, we evaluate the performance of the proposed schemes under the above in- teractive video streaming scenarios. Our simulation results show that the proposed schemes still achieve considerable power savings and better video quality than a conventional scheme for inter- active videos. 7.5 Performance Evaluation We demonstrate the performance of the proposed optimal power control algorithm through trace-driven simulations. We simulate the downlink of a cell with 1 mile radius. The channels are assumed to be orthogonal, each with Bw = 1 MHz bandwidth. We assume that bit errors can be corrected by error correction codes. The path gain averages are ?Gn = d?4n , wheredn is the physical distance from the BS to user n. We assume log-normal fading with zero mean and 8 dB standard deviation. The device temperature is 290 Kelvin and the equivalent noise bandwidth is Bw = 1 MHz. The BS streams three movies Star Wars, NBC News, and Tokyo Olympics to active users. The video traces are obtained from the Video Trace Library at Arizona State University [139]. The statistics of the three video traces are summarized in Table 7.2. We first investigate the performance of the power optimal algorithm. In the simulation, the BS streams 3,000 frames of a video sequence to each mobile user located at different distances to the BS. The cumulative consumption, overflow and transmission curves of the Star wars video session 138 0 500 1000 1500 2000 2500 30000 1 2 3 4 x 10 4 Frame-time Cu mu lat ive bi ts (kb its ) 50 100 150 200 250 300 200 400 600 800 1000 1200 1400 Frame-time Cu mu lat ive bi ts (kb its ) Cumulative consumption curve Cumulative overflow curve Cumulative transmission curve Figure 7.3: Simulation results: transmission curves of Star wars. are plotted in Fig. 7.3. It can be seen that the transmission schedule always lie in between the cumulative consumption and overflow curves, indicating that there is no playout buffer underflow or overflow events in this simulation. We next compare the optimal power algorithm with a conventional transmission scheme with respect to the average power consumption at the BS. In each time slot, the conventional scheme only transmits the video data that is needed by the decoder at the end of the time slot. It achieves a cumulative transmission curve that connects all the corner points of Dn(t) (also called the ?lazy? scheme). Intuitively, such lazy approach should be energy efficient since it always transmits the minimal amount of data as needed. However, we will see that the proposed algorithm outperform this lazy approach in the simulations. In Fig. 7.4, we plot the average power consumption achieved by the two schemes for increased distance to the BS. Each point in the figure is the average of 10,000 simulation runs. The 95% confidence intervals are plotted as vertical bars in the figure, which are all very small. It can be seen that the proposed algorithm outperforms the conventional scheme for the entire range of distances examined. When the distance to BS is small, both schemes use small transmit 139 100 200 400 500 800 1000 1200 16000 0.01 0.02 0.03 0.04 0.05 0.06 Distance (meters) Av era ge po we r c om su mp tio n ( W att s) Optimal Conventional Figure 7.4: Simulation results: average power consumption. powers and the power savings are not very big. However, when the distance is increased, channel fading has a bigger impact on interference and channel capacity. The proposed algorithm achieves considerable power savings than the conventional scheme. When the distance is 1,600 m, the total power of the proposed scheme is only 46.62% of that of the conventional approach, corresponding to a 54.34% normalized improvement. We further investigate in more detail the difference of the transmissions between the two schemes. The position of a mobile node is set to 1,000 m from the BS. The first 3,000 frames of the Star wars movie are transmitted to the node using the PMA-1 scheme and conventional scheme, respectively. Fig. 7.5 shows the cumulative power consumption for the first 1,000 frames, while the energy consumption for each video frame is plotted in Fig. 7.6 for frames in [200, 250]. We observe that at the beginning, the ?lazy? scheme archives smaller power consumption than the PMA scheme, due to the fact that it only transmits the minimum amount of required frames in each time slot. However, the transmission of frame 241 of the conventional scheme generates a sharp power increase, because it encounters a large frame as well as bad channel condition, as indicated in Fig. 7.6. The transmission curves of the two schemes are plotted in Fig. 7.7 for the 140 0 200 400 600 800 10000 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 Frame-time Cu mu lat ive P ow er (W att s) PMA Conventional Figure 7.5: Cumulative power consumptions achieved by PMA-1 and the conventional scheme. first 250 frames for the two schemes. Although the conventional scheme archives smaller power consumption frame by frame for about 80% of the 3,000 frames, the average power consumption of the proposed scheme during the entire period (0.0055 W) is much smaller than that of the conventioanal scheme (0.0141 W). In summary, the ?lazy? scheme only uses the current video and channel status, and transmits only the minimum amount of required video data, It does not effectively utilize the playout buffer capacity. Thus during the entire transmission period, the cumulative power may increased due to some large frames and bad channel conditions. On the contrary, the proposed scheme aims at minimizing the total average transmission power during the entire period. Thus, it achieves considerable power savings comparing to the conventional scheme. We also obtain the average execution time of the proposed algorithm, under the same setting but for 20,000 Star Wars frames. We find that the average execution time is about 0.06 s on an IBM Laptop with Intel T2400 1.83 GHz processor and 2 GB RAM. Finally, we examine the buffer underflow events. The following scenarios are simulated: 141 200 210 220 230 240 2500 0.05 0.1 0.15 0.2 0.25 0.3 0.35 Frame-time Po we r ( W att s) Optimal Conventional Figure 7.6: Power consumption for each frame achieved by PMA-1 and the conventional scheme. ? Scenario 1: ?P = 1 W; the movies are Star Wars, NBC News, and Tokyo Olympics; 50 mobile users; Bw = 1 MHz; ? Scenario 2: The same setting as i) except that Bw = 125 KHz; ? Scenario 3: ?P = 10 W; the HD movies are Terminator 2, From Mars to China, and Sony Demo; 20 mobile users; Bw = 1 MHz. The HD movies have larger frame sizes and higher variability in frame sizes. The buffer underflow rates are presented in Table 7.3, each being the ratio of the number of underflow frames over the total number of frames. PMA-m achieves considerably lower underflow rates for all the three sce- narios. The PMA-m underflow rates are 0.056%, 13.60%, and 14.26% of that of the conventional scheme. Therefore, PMA-m achieves not only considerable energy savings, but also much better video quality for the mobile users. 142 0 50 100 150 200 2500 500 1000 1500 Frame-time Cu mu lat ive bi ts (kb its ) Cumulative consumption curve Cumulative overflow curve Cumulative transmission curve 0 50 100 150 200 2500 500 1000 1500 Frame-time Cu mu lat ive bi ts (kb its ) Cumulative consumption curve Cumulative overflow curve Cumulative transmission curve (A) Conventional (B) PMA Figure 7.7: Transmission curves achieved by PMA-1 and the conventional scheme. Table 7.3: Simulation Results: Playout Buffer Underflow Rates Scenario 1 Scenario 2 Scenario 3 PMA-m 0.0005% 1.8% 1.66% Conventional 0.89% 13.24% 11.64% 7.5.1 Simulation Results for Interactive Video Streaming In this section, we study the performance of the proposed algorithms for interactive video streaming. First, we simulate the interactive real-time video streaming with stringent delay require- ments and small playout buffer sizes. The same simulation settings are used. All the positions of mobile nodes are randomly generated in the cell. We apply the proposed PMA-m, but only assume only the frame sizes in a small LAP are known. The transmission curves of VBR movie NBC News are plotted in Fig. 7.8 for the first 100 frames, where the length of the LAP is 16 frames. We may observe that the proposed algorithm PMA-m is executed piecewisely for each block of LAP frames, where LAP=16. For this range of frames, there is neither playout buffer overflow nor playout buffer underflow occurs. We then 143 0 20 40 60 80 1000 500 1000 1500 2000 2500 3000 Frame-time Cu mu lat ive bi ts (kb its ) Cumulative consumption curve Cumulative overflow curve Cumulative transmission curve Figure 7.8: Transmission curves for real-time interactive video streaming: NBC News and LAP = 16. Table 7.4: Playout Buffer Underflow Rates for Interactive VBR Videos with Different LAPs Scenario I Scenario II Scenario III LAP=16 PMA-m 0.387% 5.969% 4.766% Conventional 0.711% 12.446% 12.495% LAP=8 PMA-m 0.377% 5.690% 4.894% Conventional 0.620% 11.409% 9.645% compute the number of the underflow frames over the total number of frames, as presented in Table 7.4. The PMA-m still archive the underflow rate that are 54.56%, 47.96%, 38.15% of those of the conventional scheme in this case. To illustrate the impact of the length of LAP, we further decrease it to 8 frames and then run the simulations with random deployed mobile nodes. The playout buffer underflow rates are presented in Table 7.4. For the halved delay requirement, naturally the proposed scheme?s perfor- mance is slightly degraded due to limited information about the video frame sizes. However, the PMA-m scheme still archives underflow rates that are 60.90%, 49.88%, 50.74% of those of the 144 200 250 300 350 400 450 500500 1000 1500 2000 2500 3000 Frame-time Cu mu lat ive bi ts (kb its ) Cumulative consumption curve Cumulative overflow curve Cumulative transmission curve Figure 7.9: Transmission curves after the user skips the frames in [10s, 20s]: Star Wars. conventional scheme, indicating considerably superior viewer performance over the conventional ?lazy? approach. Finally, we demonstrate the application of the proposed schemes to VCR control in interactive video streaming. We assume that after 10 seconds of streaming the VBR video (i.e, corresponding to 300 frames), the user skips the next 10 seconds of the video, and then resumes the video playout from 20 second. We plot the dynamics in the transmission/schedule curves of the Star Wars video in Fig. 7.9. Comparing the curves with the original non-skipped transmissions in Fig. 7.10, we observe that after playing out the 300th frame, the frame from 301 to 600 are skipped by user?s operation. Then the frame 601 is moved to the time-slot 301 and a new transmission schedule is computed for the following frames. 7.6 Related Work A thorough review in VBR video model and VBR video streaming over wired networks has been explored in 5.6. In an interesting work [95], Salehi, et al. applied majorization to VBR video smoothing and developed a smoothness optimal algorithm. The proof of Theorem 7.2 follows a 145 200 300 400 500 600 700 800500 1000 1500 2000 2500 3000 3500 4000 Frame-time Cu mu lat ive bi ts (kb its ) Cumulative consumption curve Cumulative overflow curve Cumulative transmission curve Figure 7.10: Transmission curves for the original non-skipped video streaming: Star Wars. similar approach as in [95]. These prior work are based on the assumptions of a single video session and constant rate channels, which may not be directly applied to the case of wireless networks. In this chapter, we consider multiuser VBR video streaming within a cellular network with or- thogonal channels. We jointly consider power control, video traffic, and video palyout information for power minimization. Our stochastic majorization theory based approach is quite different from the prior works [54,143], which allow us to develop effective algorithms with low complexity and proven optimality. 7.7 Conclusion In this chapter, we studied the problem of downlink multiuser VBR video streaming in cel- lular networks. Our formulation takes into account the interactions among power control, fading channels, VBR video traffic and playout characteristics. We formulate a constrained stochastic optimization problem aiming to minimize the BS power consumption and to avoid playout buffer 146 overflow or underflow. We developed majorization-based algorithms to solve the formulated prob- lem. For the case of large peak power constraints, we prove the optimality of the proposed algo- rithm and the uniqueness of the global optimal, as well as the equivalence of power optimal and smoothness optimal. For the case of multiple videos coupled with the peak power constraint, we develop an effective heuristic algorithm that selectively suspends some video sessions when the peak power constraint is violated. The superior performance of the proposed algorithms over a conventional scheme is validated with trace-driven simulations. 147 Chapter 8 Summary and Future Work 8.1 Summary In the previous chapters, we proposed frameworks for energy efficient designs in Cyber- physical systems. We investigated the problems by a control and optimization approach, which contains Lyapunov optimization [12], majorization [13], nonlinear and convex optimization [14]. The synergy of these advanced mathematical tools produces new visions for the energy efficient solutions to alleviate energy resource depletion, decrease greenhouse gases emission and air pol- lution, which evolves a green world in the future. In Chapter 2, we presented the electric power scheduling policies for smoothing the demand profile in power distribution networks. We introduced a deterministic electricity supply/demand model that takes into account time-varying demands and their deadlines. We formulated a con- straint nonlinear optimization problem and incorporated the theory of majorization to develop algorithms that can compute smooth optimal electric power schedules. After the smooth power schedule is obtained, a distributed user benefit maximization load control scheme is used to al- locate the scheduled power to individual users, while maximizing their level of satisfaction. The proposed algorithms are highly desirable for grid design and operation, which provide smooth electric power scheduling, minimum peak power and operating cost. The simulation showed that the proposed algorithms can alleviate the peak power up to 45%. This means we can deploy trans- formers, transmission lines and other electrical devices with much smaller capacity, which save the captital investment in the power grid construction. The generation cost saving is about 5% by the proposed algorithms. Due to the tremendous amount of energy of bulk generation, 5% cost savings could indeed contribute to billions of dollars. 148 In Chapter 3, we investigated the problem of balancing supply and demand of electric en- ergy in microgrid (MG). We presented a novel framework for smart energy management based on the concept of quality-of-service in electricity (QoSE). Specifically, the resident electricity de- mand is classified into basic usage and quality usage. The basic usage is always guaranteed by the MG, while the quality usage is controlled based on the MG status. The microgrid control center (MGCC) aims to minimize the MG operation cost and maintain the outage probability of quality usage, i.e., QoSE, below a target value, by scheduling electricity among DRERs, ESS?s, and macrogrid. The problem is formulated as a constrained stochastic programming problem. The Lyapunov optimization technique is then applied to derive an adaptive electricity scheduling algo- rithm by introducing the QoSE virtual queues and energy storage virtual queues. The proposed algorithm is an online algorithm since it does not require any statistics and future knowledge of the electricity supply, demand and price processes. We derive several ?hard? performance bounds for the proposed algorithm. and evaluate its performance with trace-driven simulations. The proposed electricity scheduling algorithm enables an efficient integration of DRERs, ESS?s, and residential power quality management into the smart grid by plug-and-play interfaces, and provides a promis- ing paradigm for smart energy management systems in smart grid. The simulation showed that the MG operation cost can be saved up to 60%, while keeping the power quality of the users. In Chapter 5, we studied the problem of power allocation of base station (BS) for streaming multiple variable bit rate (VBR) videos in the downlink of a wireless cellular network with intracell interference. We considered a deterministic model for VBR video traffic and finite playout buffer at the mobile users. The objective is to derive the optimal downlink power allocation for the VBR video sessions, such that the video data can be delivered in a timely fashion without causing playout buffer overflow and underflow. The formulated problem is a nonlinear nonconvex optimization problem. We analyzed the convexity conditions for the formulated problem and proposed a two- step greedy approach to solve the problem. We also developed a distributed algorithm based on the dual decomposition technique. The proposed algorithms effectively allocated the power in BS?s 149 to stream the VBR video in cellular networks, while preserving the quality of experience (QoE) requirement. In Chapter 6 we further extended the problem of downlink power control for streaming mul- tiple VBR videos in a multicell wireless networks, where downlink capacities are limited by inter- cell interference. We adopted a deterministic model for VBR traffic that considers video frame sizes and playout buffers at the mobile users. The problem is to find the optimal transmit powers for the BS?s, such that VBR video data can be delivered to mobile users without causing play- out buffer underflow or overflow. We formulated a nonlinear nonconvex optimization problem and proved the condition for the existence of feasible solutions. We then developed a centralized branch-and-bound algorithm incorporating the Reformulation-Linearization Technique, which can produce (1??)?optimal solutions. We also proposed a low-complexity distributed algorithm with fast convergence. Numerical results showed that the proposed algorithms is QoE performance bounded and achieve effective usage of the BS?s power in streaming VBR videos. In Chapter 7, we addressed the energy saving for BS in wireless cellular networks with or- thogonal channels to achieve energy efficient VBR video streaming. We took into account the interactions among power control, fading channels, VBR video traffic, and playout characteristics. A constrained stochastic optimization problem was formulated aiming to minimize the BS power consumption and to avoid playout buffer overflow or underflow. We then developed majorization- based algorithms to achieve energy efficiency, while preserving the QoE demands, for BS downlink VBR streaming in cellular networks. The simulation showed that the average power consumption can achieve 54% improvement and the proposed algorithms are also compativle to interactive video streaming in wireless cellular networks. 8.2 Future Work Although there has been considerable advances in energy efficient Cyber-physical systems, many problems still remain open in this interesting area. We briefly extend our discussion on 150 the control and optimization in distributed smart electric energy management systems and low complexity energy efficient wireless multimedia networks. Distributed Electric Energy Management Systems We investigated the efficient electric energy scheduling in the power delivery in previous chapters. The proposed policies are mainly based on the centralized control in the electric power delivery networks and Microgrids, which were largely inherited from the control infrastructure of legacy grid. In the evolution of smart grid, all the components, such as DRERs, ESS?s, MGs, and users, will be deployed in an ad-hoc mode and accessed in a plug-and-play fashion. Accordingly, such distributed electric power delivery networks prefer distributed intelligent electric energy man- agement systems. Compared to the centralized approaches, distributed management systems make decisions based on local information with very limited timely information exchange, which reduce the amount of real time information delivery in the communication networks. The distributed manage- ment systems are less susceptible to the information loss due to the impairment of the communi- cation links and also have faster response to the grid status. The security design and cryptographic systems would also be simplified due to reduced amount of information exchange. However, due to the limitation on the accessible information, the distributed management systems usually are not capable of computing a globally optimal decision. Further, analytical models and mathematical tools would be necessary to provide the performance bounded optimal decisions locally. Low Complexity Energy Efficient Wireless Multimedia Networks Due to the intrinsic complexity of video sources and the dynamics and uncertainty of wireless systems, we conjecture that a holistic approach that encompasses the parameter space would be necessary and the trade-off between complexity and efficiency of a solution algorithm should be carefully investigated. In particular, we list some interesting problems that may be worth of further investigation in the following. 151 ? Complexity-distortion analysis and the design of energy-efficient video codecs require ac- curate models of video codecs. However, a video codec is a combination of complex func- tional blocks, which makes accurate mathematic modeling extremely difficult. In addition, the quality of compressed video and the power consumption of the video codec depend on a large number of parameters. A content-based power-aware design may encounter a large search space for optimal solutions. It would be useful to develop an accurate and effective model for video codec that can be incorporated into the mathematical optimization frame- works for both energy efficient codec design and wireless multimedia system design. ? Cross-layer design has been widely adopted for video networking problems. It has been shown that an adaptive strategy with cooperation of several layers can achieve optimal power efficiency for video streaming. Most prior work assume that the wireless channel informa- tion and network status are known apriori (e.g., by accurate estimation, measurement, and timely feedback). In practice, this assumption may not be true, because of channel/network uncertainty and dynamics, and delay and congestion in the network. Thus, balancing the achievable performance and the control overhead of the design is still an open problem. Effective schemes that are robust to the channel/network uncertainties would be highly ap- pealing. 152 Appendices 153 Appendix A Proofs in Chapter 2 A.1 Proof of Theorem 2.2 The schedule computed by SEPS-DL, vectorP?, could be a straight line or in the general case, consist of one or more convex and concave segments. If vectorP? is a straight line, it is obvious that vectorP? ? vectorPk for any other vectorPk (see Fig. 2.3) and it is smooth optimal. In the general case, we need to show vectorP? ? vectorPk, for all k in every convex or concave segment. Then according to Lemma 2.1, we have vectorP? ? vectorPk for all k and it is optimal. Let vectorPk denote an arbitrary feasible schedule. We introduce an auxiliary schedule vectorP1, which intersects with vectorP? at all its power changing points in every convex segment, and with vectorPk at all its power changing points in every concave segment, as shown in Fig. A.1. First, we prove that vectorP? ? vectorP1. For a convex segment of vectorP?, because vectorP1 intersects with vectorP? at all the power changing points of vectorP?, we have vectorP? = vectorP1 in all the convex segments. For a concave segment of vectorP?, the endpoints of the concave segment should be the last (first) power changing point of the previous (next) convex segment, where vectorP? intersects with vectorP1. The power changing points within the concave segment are all on Wmin(t), as in SEPS-DL. Therefore, vectorP1 is an outer concave curve above vectorP? (or, it is farther away from the straight line A in Fig. 2.3) in this segment. From the discussion of Fig. 2.3, we have vectorP? ? vectorP1 for all the concave segments. It follows that vectorP? ? vectorP1 according to Lemma 2.1. We next prove that vectorP1 ? vectorPk. For a convex segment of vectorP?, the endpoints of the convex segment should be the last (first) power changing point of the previous (next) concave segment, where vectorPk intersects with vectorP1. The power changing points of vectorP1 (or, of vectorP?) in the convex segment are all on Wmax(t). Therefore, vectorPk is an outer convex curve below vectorP1 in this segment. From the discussion of Fig. 2.3, it follows that vectorP1 ? vectorPk in all the convex segments. In a concave segment, we have either 154 Time kWh 0 Wmax(t) Wmin(t) Pk P * P1 Cross point of Pk and P1 in a concave interval Cross point of P and P1 in a convex interval * Figure A.1: Illustration for the optimality proof of SEPS-DL algorithm vectorPk = vectorP1 or vectorPk ? vectorP1, because vectorP1 intersects with vectorPk at each power changing point. Thus, we obtain vectorP1 ? vectorPk for all the concave segments, and vectorP1 ? vectorPk according to Lemma 2.1. Finally we have vectorP? ? vectorP1 ? vectorPk. Proposition 2.1 states that problem (2.3) is Schur-convex and order preserving. It follows from Fact 2.1 that vectorP? is optimal to problem (2.3). A.2 Proof of Theorem 2.5 Without loss of generality, we assume the fuel cost at time slot t is C(t) = g(P(t),?(t)), which a nondecreasing convex function of the supplied power P(t) [92]. This assumption is gen- erally practical, e.g. classically, the fuel cost for the electric energy generation is usually considered as a quadratic function of its power generation [103]. We also assume the cost C(t) is affected by the random factors ?(t), which correspond to the cost uncertainty during the period, such as the fuel market price disturbance, and etc. We assume each element in ?(t) is i.i.d over slots. Thus, 155 the minimization of the expectation of the total cost over the period L is: Minimize: Lsummationdisplay t=1 E{g(P(t),vector?(t))} s.t. Wmin(t) ?W(t) ?Wmax(t),?t P(t) = W(t)/? Lsummationdisplay t=1 W(t) = ? (A.1) Due to the convexity of the cost function g(?) respective to P(t), problem (A.1) is similar to problem (2.3), except the random variable ?(t). Thus, we resort to stochastic majorization (rather than ordinary majorization) to solve this constraint nonlinear stochastic optimization problem. Lemma A.1. The objective function of problem (A.1) is an increasing Schur-convex function. Proof. The i.i.d. random variables ?(t) are exchangeable for all t. The objective function (A.1) can be rewritten as G(vectorP) = E braceleftBigg Lsummationdisplay t=1 g(P(t),?(t)) bracerightBigg , where g(P(t),?(t)) is convex and increasing with respective to P(t) for each fixed ?(t), and summationtextL t=1g(P(t),?(t)) is a symmetric, convex and increasing function w.r.t. P(t). According to Proposition 11.B.5 in [13], the expectation G(vectorP) is symmetric, convex and increasing. Following Fact 2.1, the objective function (A.1) is Schur-convex and increasing. By Lemma A.1, the solution of problem (A.1) is equivalent to finding the optimal power vector vectorP?, which is majorized by any other feasible power vectors. Thus, the smooth optimal solution vectorP? in Table 1 is also the solution for problem (A.1). Thus, the proposed SEPS-DL achieves fuel cost optimal for energy generation. 156 Appendix B Proofs in Chapter 3 B.1 Proof of Theorem 3.1 According to the system equation (3.12), we have ? ???? ? ??? ?? Zn(1) ?Zn(0)??n ??n(0) +In(0) ??? Zn(t) ?Zn(t?1)??n ??n(t?1) +In(t?1). (B.1) Summing up the inequalities in (B.1), we have Zn(t) ?Zn(0)??n ? t?1summationdisplay ?=0 ?n(?) + t?1summationdisplay ?=0 In(?). (B.2) Dividing both sides by t and letting t go to infinity, we have limt?? Zn(t)?Zn(0)t ? limt?? 1t bracketleftBigg ??n t?1summationdisplay ?=0 ?n(?)+ t?1summationdisplay ?=0 In(?) bracketrightBigg . Zn(0) is finite. If Zn(t) is rate stable by a control policy In(t), it is finite for all t. We have limt?? Zn(t)?Zn(0)t = 0, which yields ?n ??n ??n due to the definitions of ?n and In(t). 157 B.2 Derivation of Equation (3.16) With the drift defined as in (3.15), we have ?(vector?(t)) = 12E braceleftBigg Ksummationdisplay k=1 [(Xk(t+ 1))2 ?(Xk(t))2|Xk(t)]+ Nsummationdisplay n=1 [(Zn(t+ 1))2 ?(Zn(t))2|Zn(t)] bracerightBigg ? 12 Ksummationdisplay k=1 Ebraceleftbigbracketleftbig(Dk(t))2 + (Rk(t))2 + 2Xk(t)(Rk(t)? Dk(t))|Xk(t)]}+ 12 Nsummationdisplay n=1 EbraceleftbigbracketleftbigIn(t)2+ (?n?n(t))2 + 2Zn(t)(In(t)??n?n(t))|Zn(t)} = 12 Ksummationdisplay k=1 E{[(Dk(t))2 + (Rk(t))2]}+ Ksummationdisplay k=1 E{Xk(t)(Rk(t)?Dk(t))|Xk(t)}+ 1 2 Nsummationdisplay n=1 E{[(1 + (?n)2)(?n(t))2 + (pn(t))2]}+ 1 2 Nsummationdisplay n=1 E{2Zn(t)(1??n(t))?n(t)? (Zn(t) +?n(t))pn(t)|Zn(t)} ?B + Nsummationdisplay n=1 E{Zn(t)(1??n)?n(t)|Zn(t)}+ Ksummationdisplay k=1 E{Xk(t)(Rk(t)?Dk(t))|Xk(t)}? Nsummationdisplay n=1 E{(Zn(t) +?n(t))pn(t)|Zn(t)}. where B = 12summationtextKk=1(max{Dmaxk ,Rmaxk })2 + 12summationtextNn=1(2 +?2n)(?maxn )2 is a constant. 158 B.3 Proof of Lemma 3.1 In part 1) of Lemma 3.1, if Q(t) > 0, we have S(t) = 0 according to (3.7). The objective function of problem (3.19) becomes VQ(t)C(t) + Ksummationdisplay k=1 Xk(t)(Rk(t)?Dk(t))? Nsummationdisplay n=1 (Zn(t) +?n(t))pn(t). (B.3) We first prove Lemma 3.1-1a). If Xk(t) > ?VC(t), we assume Rk(t) > 0. Then we have Dk(t) = 0 according to (3.4). Accordingly, the object function (B.3) is transformed to VQ(t)C(t) + summationdisplay inegationslash=k Xi(t)(Ri(t)?Di(t))? Nsummationdisplay n=1 (Zn(t) +?n(t))pn(t) +Xk(t)Rk(t) > VQ(t)C(t) + summationdisplay inegationslash=k Xi(t)(Ri(t)?Di(t))? Nsummationdisplay n=1 (Zn(t) +?n(t))pn(t)?VC(t)(P(t) +Q(t)? summationdisplay inegationslash=k (Ri(t)?Di(t))? Nsummationdisplay n=1 pn(t) = V bracketleftBiggsummationdisplay inegationslash=k (Ri(t)?Di(t)) + Nsummationdisplay n=1 pn(t)?P(t) bracketrightBigg C(t) + summationdisplay inegationslash=k Xi(t)(Ri(t)?Di(t))? Nsummationdisplay n=1 (Zn(t) +?n(t))pn(t). The above inequality is due toXk(t) >?VC(t) andRk(t) = P(t)+Q(t)?summationtextinegationslash=k(Ri(t)?Di(t))? summationtextN n=1pn(t) ? 0. The last expression shows, given the assumptionRk(t) > 0, we may find another feasible electricity allocation scheme ?Q(t) = summationtextinegationslash=k(Ri(t)?Di(t)) +summationtextNn=1pn(t)?P(t), which can achieve a smaller objective value by choosing Rk(t) = 0 and Dk(t) = 0. This contradicts with 159 the assumption Rk(t) > 0. Thus, we prove that Rk(t) = 0 when Xk(t) > ?VC(t), under the situation Q(t) > 0,S(t) = 0. We then prove the second part of Lemma 3.1-1a). It follows (3.4) thatRk(t) = 0 ifDk(t) > 0. Then (B.3) becomes VQ(t)C(t) + summationdisplay inegationslash=k Xi(t)(Ri(t)?Di(t))? Nsummationdisplay n=1 (Zn(t) +?n(t))pn(t)?Xk(t)Dk(t) > VQ(t)C(t) + summationdisplay inegationslash=k Xi(t)(Ri(t)?Di(t))? Nsummationdisplay n=1 (Zn(t) +?n(t))pn(t) +VC(t)( Nsummationdisplay n=1 pn(t)?P(t)? Q(t) + summationdisplay inegationslash=k (Ri(t)?Di(t))) = V bracketleftBiggsummationdisplay inegationslash=k (Ri(t)?Di(t)) + Nsummationdisplay n=1 pn(t)?P(t) bracketrightBigg C(t) + summationdisplay inegationslash=k Xi(t)(Ri(t)?Di(t))? Nsummationdisplay n=1 (Zn(t) +?n(t))pn(t). The above inequality is due to Xk(t) 0. The last expression shows, given the assumption Dk(t) > 0, we may find another electricity allocation scheme with ?Q(t) = summationtextinegationslash=k(Ri(t) ? Di(t)) + summationtextNn=1pn(t) ? P(t), which can achieve a smaller objective value by choosing Rk(t) = 0 and Dk(t) = 0. This contradicts with the assumptionDk(t) > 0. We thus prove thatDk(t) = 0 whenXk(t) 0,S(t) = 0, which completes the proof of Lemma 3.1-1a). 160 We next prove Lemma 3.1-1b). For the first part, if Zn(t) > VC(t) ??n(t), we assume 0 ?pn(t) < (1??n)?n(t). Following (3.18) and S(t) = 0, we have B +VQ(t)C(t) + Ksummationdisplay k=1 Xk(t)(Rk(t)?Dk(t)) + summationdisplay jnegationslash=n (Zj(t)(1??j)?j(t)?(Zj(t) +?j(t))pj(t)) + Zn(t)(1??n)?n(t)?(Zn(t) +?n(t))pn(t) =B +VQ(t)C(t) + Ksummationdisplay k=1 Xk(t)(Rk(t)?Dk(t)) + summationdisplay jnegationslash=n (Zj(t)(1??j)?j(t)?(Zj(t) +?j(t))pj(t)) + Zn(t)[(1??n)?n(t)?pn(t)]??n(t)pn(t) >B +VQ(t)C(t) + Ksummationdisplay k=1 Xk(t)(Rk(t)?Dk(t)) + summationdisplay jnegationslash=n (Zj(t)(1??j)?j(t)?(Zj(t) +?j(t))pj(t)) + (VC(t)??n(t))[(1??n)?n(t)?pn(t)]??n(t)pn(t) =B +V[ Ksummationdisplay k=1 (Rk(t)?Dk(t)) + summationdisplay jnegationslash=n pj(t)?P(t) + (1??n)?n(t)]C(t) + Ksummationdisplay k=1 Xk(t)(Rk(t)?Dk(t)) + summationdisplay jnegationslash=n (Zj(t)(1??j)?j(t)?(Zj(t) +?j(t))pj(t)) + Zn(t)(1??n)?n(t)?(Zn(t) +?n(t))(1??n)?n(t). The above inequality is due to Zn(t) >VC(t)??n(t) and the assumption pn(t) < (1??n)?n(t). The last equality shows, given the assumptionpn(t) < (1??n)?n(t), we may find another electric- ity allocation scheme withpn(t) = (1??n)?n(t) and ?Q(t) =summationtextKk=1(Rk(t)?Dk(t))+summationtextjnegationslash=npj(t)? P(t) + (1??n)?n(t), which can achieve a smaller objective value. This contradicts with the pre- vious assumption. Thus, we have pn(t) ? (1??n)?n(t). 161 For the second part of Lemma 3.1-1b), assume pn(t) > 0 for 0 ? Zn(t) B +VQ(t)C(t) + Ksummationdisplay k=1 Xk(t)(Rk(t)?Dk(t)) + summationdisplay jnegationslash=n (Zj(t)(1??j)?j(t)?(Zj(t) +?j(t))pj(t)) + Zn(t)(1??n)?n(t)?VC(t)pn(t) ? B +V[?P(t) + Ksummationdisplay k=1 (Rk(t)?Dk(t)) + summationdisplay jnegationslash=n pj(t)]C(t) + Ksummationdisplay k=1 Xk(t)(Rk(t)?Dk(t)) + summationdisplay jnegationslash=n (Zj(t)(1??j)?j(t))? summationdisplay jnegationslash=n ((Zj(t) +?j(t))pj(t)). The first inequality is due to 0 ? Zn(t) < VC(t) ??n(t) and the assumption pn(t) > 0. The second inequality is due to the non-negativity of Zn(t) and ?n(t). The last equation shows, given the assumption pn(t) > 0, we may find another electricity allocation scheme with pn(t) = 0 and ?Q(t) = ?P(t) + summationtextKk=1(Rk(t) ? Dk(t)) + summationtextjnegationslash=npj(t), which can achieve a smaller objective value. This contradicts with the previous assumption. Thus, we have pn(t) = 0, which completes the proof of Lemma 3.1-1b). In part 2) of Lemma 3.1, if S(t) > 0, we have Q(t) = 0 according to (3.7). The objective function (3.19) becomes ?VS(t)W(t) + Ksummationdisplay k=1 Xk(t)(Rk(t)?Dk(t))? Nsummationdisplay n=1 (Zn(t) +?n(t))pn(t). (B.4) 162 We can prove part 2) with a similar approach as in the case of part 3.1. The detailed proof is omitted for brevity. B.4 Proof of Lemma 3.2 Since 0 ? Cmin ? C(t) ? Cmax and V > 0, we have Rk(t) = 0 when Xk(t) < ?VCmax, and Dk(t) = 0 when Xk(t) > ?VCmin according to Lemma 3.1-3.1). Similarly, since 0 ? Wmin ?W(t) ?Wmax andV > 0, we obtainRk(t) = 0 whenXk(t) ?VWmin according to Lemma 3.1-2) Since Cmax >Wmax and Cmin >Wmin, we conclude that if Xk(t) > ?VWmin, the optimal solution always selectRk(t) = 0. IfXk(t) ?VWmin ?Rk(t) = 0 from Lemma 3.2, we 163 haveXk(t+1) = Xk(t)?Dk(t) ?Xk(t) ?Emaxk ?VCmax?Dmaxk ?Emink . IfXk(t) ??VWmin, then the largest value is Xk(t+ 1) = ?VWmin +Rmaxk . For any 0 VCmax, following Lemma 3.3, the optimal scheduling for the quality usage of resident n satisfies pn(t) ? (1??n)?n(t). From the virtual queue dynamics (3.12), we have Zn(t+ 1) ? [Zn(t)??n?n(t)]+ +?n?n(t). If Zn(t) ? ?n?n(t), we have Zn(t + 1) ? Zn(t) ? VCmax + ?maxn ; otherwise, it follows that Zn(t+ 1) ??n?n(t) 1. For the SINR at user n, we have ?n(vectorP??(t)) = LnGnP ?? n(t)summationtext knegationslash=nGnP ?? k (t) +?n = ?LnGnP ? n(t)summationtext knegationslash=n?GnP ? k(t) +?n > ?LnGnP ? n(t)summationtext knegationslash=n?GnP ? k(t) +??n = ?n(vectorP?(t)). It follows that summationtextn?U log(1 + ?n(vectorP??(t))) > summationtextn?U log(1 + ?n(vectorP?(t))), since log(1 + x) is an increasing function of x. Choosing ? = ?P/summationtextn?U P?n(t), we can construct a feasible solution vectorP???(t) = ?? vectorP?(t), such that summationtextn?U P???n (t) = ?P. Then we have ?n(vectorP???(t)) > ?n(vectorP?(t)) and summationtextn?U log(1 +?n(vectorP???(t))) > summationtext n?U log(1 +?n(vectorP ?(t))). That is, any feasible solution withsummationtext n?U P ? n(t) < ?P will be dominated 168 by feasible solutions with summationtextn?U P???n (t) = ?P. We conclude that the optimal solution vectorP(t) must satisfysummationtextn?U Pn(t) = ?P. C.3 Proof of Lemma 5.3 Taking the first and second derivatives of the objective function (5.14) with respect to Pn, we have ?Cn(Pn) ?Pn = Ln( ?P +An) ( ?P ?Pn +An)[ ?P + (Ln ?1)Pn +An] (C.1) ?2Cn(Pn) ?Pn2 = ?Ln[(Ln ?2)( ?P +An) + 2(1?Ln)Pn]( ?P +An) [( ?P ?Pn +An)2 +LnPn( ?P ?Pn +An)]2 . (C.2) Since Pn ? ?P and An > 0, both the first and second derivatives exist. Letting ?2Cn(Pn)?P n2 = 0, we derive the unique inflection point P?n = Ln ?22(L n ?1) ( ?P +An). (C.3) WhenPn P?n, it can be shown that ?2Cn(Pn)?P n2 > 0. C.4 Proof of Theorem 5.2 The reflection point is P?n = Ln?22(Ln?1)( ?P +An). As Ln ? ?, we have P?n = 0.5( ?P +An). Only one link can operate in the convex region due to constraint (5.17). Since ?P?n?Ln > 0, P?n is an increasing function of Ln. When 1 ?Ln 0, for Ln > 2. The second part can be easily shown by evaluating (5.14), (5.15), and (C.1). 170 Appendix D Proofs in Chapter 6 D.1 Proof of Lemma 6.1 According to the definition of Xm(t) in (6.3), we have Cm(t) = [Xm(t)?Xm(t?1)]/?. From the definition ofCminm (t), the playout buffer is emptied at the end of time slott, i.e., Xm(t) = Dm(t). Therefore, we can derive the minimum required rate as Cminm (t) = max{0,Dm(t)?Xm(t?1)}/?. (D.1) From the feasibility condition (6.4), we have Xm(t?1) ? Dm(t?1). Substituting it into (D.1), we have Cminm (t) ? [Dm(t)?Dm(t?1)]/? ? ?Cminm (t). (D.2) Rate ?Cminm (t) occurs when the playout buffer is empty at both the beginning and end of time slot t, but without buffer overflow during the entire time slot. D.2 Proof of Theorem 6.1 Recall that?minm is the SINR corresponding to the minimum required rateCminm (t). Let ??minm (t) be the SINR corresponding to ?Cminm (t). Since (6.2) is a monotonically increasing function, we have 0 ??minm (t) ? ??minm (t). We now consider the power assignment that achieves rates ?Cminm (t), or, the corresponding SINRs ??minm (t). From (6.7) and (6.8), the minimum SINR constraint is: ?m(t) = G m mPm(t)summationtext knegationslash=mG m k Pk(t) +?m ? ??minm (t), ?m. (D.3) 171 Eqn. (D.3) is a system of linear equations of the power vector vectorP(t), which can be written in the matrix form as: parenleftbigI???minAparenrightbigvectorP(t) followsequal ??minvector?, (D.4) where I is the identity matrix, A is an M ?M matrix with Amk = ?? ? ?? 0, m = k Gmk /Gmm, mnegationslash= k, (D.5) ??min = diag{??min1 (t),??min2 (t),??? ,??minM (t)} is a diagonal matrix, and vector? = [?1/G11,?2/G22,??? , ?M/GMM]T. Define ?min = diag{?min1 (t),?min2 (t),??? ,?minM (t)} and ? = ??min ??min followsequal 0. Assume vectorP is a power assignment that achieves ??minm (t) for all m, which satisfies (D.4). Substituting ??min = ?+?min into (D.4), we have parenleftbigI??minAparenrightbigvectorP followsequal?minvector? +?parenleftBigvector? +AvectorPparenrightBig. Since ?, vector?, A and vectorP all have non-negative elements, we have ? parenleftBig vector? +AvectorP parenrightBig followsequal0, and therefore, parenleftbigI??minAparenrightbigvectorP followsequal?minvector?. That is, vectorP can also achieve ?minm (t) for all m and it satisfies the minimum SINR constraint in (6.8). Once the minimum SINR constraint in (6.8) (i.e., no buffer underflow) is satisfied, the max- imum SINR constraint in (6.8) (i.e., no buffer overflow) can be satisfied since BS m can stop transmission when the playout buffer at user unm is full. 172 Appendix E Proofs in Chapter 7 E.1 Proof of Theorem 7.1 Due to i.i.d. channel gains and noise powers, the random variables ?n(t)/Gn(t)?s are ex- changeable, for all t. Define w(g,?,c) = (2c/Bw ?1)?/g, which is convex and increasing with c, for all g ? 0 and ? ? 0. Let ?(vectorC) = E[?(vectorC)] = E[summationtextTt=1w(g(t),?(t),c(t))]. ?(vectorC) is a symmet- ric, convex and increasing function in vectorC for each fixed vectorG and vector?. According to Proposition 11.B.5 in [13], ?(vectorC) is symmetric, convex and increasing. Following Fact 2.1, the objective function (7.9) is Schur-convex and increasing. E.2 Proof of Corollary 7.2.3 To evaluate the smoothness of a transmission schedule vectorC, the following smoothness utility function can be used: U(vectorC) = Tnsummationdisplay t=1 ([c(t)??c]/Tn), (E.1) where ?c = summationtextTnt=1c(t)/Tn is the average rate. This is a continuous symmetric convex function U : RTn ? R. From Fact 2.1, U is Schur-convex and order preserving. The optimal power transmission schedule vectorC?n satisfies vectorC?n ? vectorCin for all i. Therefore, it also achieves the minimum value for U(?). 173 Appendix F Acronyms AMI Automated Meter Infrastructure BS Base Station CBR Constant Bit Rate CDMA Code Division Multiple Access CPS Cyber-Physical System CSMA Carrier Sense Multiple Access DCC Distribution Control Center DCPC Distributed Constrained Power Control DCT Discrete Cosine Transform DR Demand Response DRER Distributed Renewable Energy Resource DUBMLC Distributed User Benefit Maximization Load Control DVS Dynamic Voltage Scaling ESS Energy Storage System GSEPS General Smooth Electric Power Scheduling FDMA Frequency-Division Multiple Access HAN Home Area Network ICT Information and Communications Technology IDCT Inverse DCT LAN Local Area Network LB Lower Bound LP Linear Programming 174 MB Macro Block MG Microgrid MGCC MG Central Controller PMA Power Minimization Algorithm PMU Phasor Measurement Unit PHEV Plug-in Hybrid Electric Vehicles PLC Power Line Communication QoE Quality of Experience QoS Quality of Service QoSE Quality of Service in Electricity RLT Reformulation-Linearization Technique RTP Real-time Transport Protocol SEPS-DL Smooth Electric Power Scheduling for Deferrable Load SINR Signal to Interference-plus-Noise Ratio SG Smart Grid SST Solid State Transformer SUDP Supply Until Deadline Policy TCP Transmission Control Protocol TDMA Time Division Multiple Access UB Upper Bound UDP User Datagram Protocol UMRP Utility Maximization Real-time Pricing V2G Vehicle-to Gird VBR Variable Bit Rate VPP Virtual Power Plant VSN Visual Sensor Networks WAN Wide Area Network 175 Bibliography [1] N. Wu and X. Li, RFID Applications in Cyber-Physical Sys- tem. InTech, 2011, ch. 16, [online] Available: http://www. intechopen.com/books/deploying-rfid-challenges-solutions-and-open-issues/ rfid-applications-in-cyber-physical-system. [2] K. Kim and P. R. Kumar, ?Cyber-physical systems: A perspective at the centennial,? Pro- ceedings of the IEEE, vol. 100, no. 3, pp. 1287?1308, May 2012. [3] H. Farhangi, ?The path of the smart grid,? IEEE Power and Energy Mag., vol. 8, no. 1, pp. 18?28, Jan.-Feb. 2010. [4] X. Fang, S. Misra, G. Xue, and D. Yang, ?Smart grid - the new and improved power grid: A survey,? IEEE Commun. Surveys & Tutorials, vol. PP, no. 99, pp. 1?37, Dec. 2011. [5] F. Li, W. Qiao, H. Sun, H. Wan, J. Wang, Y. Xia, Z. Xu, and P. Zhang, ?Smart transmission grid: Vision and framework,? IEEE Trans. Smart Grid, vol. 1, no. 2, pp. 168?177, Sept. 2010. [6] C. W. Clark, The Smart Grid: Enabling Energy Efficiency and Demand Response. Lilburn, GA: Fairmont Press, 2009. [7] Energy.gov, ?How the smart grid promotes a greener future,? [online] Available: http:// energy.gov/oe/downloads/how-smart-grid-promotes-greener-future. [8] G. Fettweis and E. Zimmermann, ?Ict energy consumption - trends and challenges,? in Proc. WPMC?08, Lapland, Finland, Sep. 2008, pp. 1?4. [9] Cisco, ?Cisco visual networking index: Global mobile data traffic forecast update, 2010- 2015,? Feb. 2011, [online] Available: http://www.cisco.com/en/US/solutions/collateral/ ns341/ns525/ns537/\\ns705/ns827/white\ paper\ c11-520862.html. [10] C. Schaefer, C. Weber, and A. Voss, ?Energy usage of mobile telephone services in Ger- many,? Elsevier Energy, vol. 28, no. 5, pp. 411?420, Apr. 2003. [11] S. Vadgama, ?Trends in green wireless access,? FUJITSU Scientific Technical Journal, vol. 45, no. 4, 2009. [12] L. Tassiulas and A. Ephremides, ?Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks,? IEEE Trans. Autom. Control, vol. 37, no. 12, pp. 1936?1948, Dec. 1992. 176 [13] A. W. Marshall and I. Olkin, Inequalities: Theory of Majorization and Its Applications. New York, NY: Academic Press, 1979. [14] D. Bertsekas, Nonlinear Programming. Belmont, MA: Athena Scientific, 1995. [15] Nationalacademies.org, ?Greatest engineering achievements of the 20th century,? [online] Available: http://www.nationalacademies.org/greatachievements/. [16] Whitehouse.gov, ?Battery and electric vehicle report,? Jul. 2010, [online] Available: http: //www.whitehouse.gov/files/documents/Battery-and-Electric-Vehicle-Report-FINAL.pdf. [17] G. Iyer, P. Agrawal, E. Monnerie, and R. S. Cardozo, ?Performance analysis of wireless mesh routing protocols for smart utility networks,? in IEEE SmartGridComm?11, Oct. 2011, pp. 114?119. [18] Z. Zhong, C. Xu, B. J. Billian, L. Zhang, S.-J. Tsai, R. W. Conners, V. A. Centeno, A. G. Phadke, and Y. Liu, ?Power system frequency monitoring network (FNET) implementa- tion,? IEEE Trans. Power Systems, vol. 20, no. 4, pp. 1914?1921, Nov. 2005. [19] S. Xu, A. Q. Huang, S. Lukic, and M. E. Baran, ?On integration of solid-state transformer with zonal DC microgrid,? IEEE Trans. Smart Grid, vol. 3, no. 2, pp. 975?985, Jun. 2012. [20] J. A. P. Lopes, F. J. Soares, and P. M. R. Almeida, ?Integration of electric vehicles in the electric power system,? Proceedings of the IEEE, vol. 99, no. 1, pp. 168?183, Jan. 2011. [21] J. Kumagai, ?Virtual power plants, real power,? Spectrum IEEE, vol. 49, no. 3, pp. 13?14, Mar. 2012. [22] A. Q. Huang, M. L. Crow, G. T. Heydt, J. P. Zheng, and S. J. Dale, ?The future renew- able electric energy delivery and management (FREEDM) system: the energy internet,? Proceedings of IEEE, vol. 99, no. 1, pp. 133?148, Jan. 2011. [23] J. Huang, Z. Li, M. Chiang, and A. Katsaggelos, ?Joint source adaptation and resource allo- cation for multi-user wireless video streaming,? IEEE Trans. Circuits Syst. Video Technol., vol. 18, no. 5, pp. 582?595, May. 2008. [24] A. Brooks, E. Lu, D. Reicher, C. Spirakis, and B. Weihl, ?Demand dispatch,? IEEE Power and Energy Mag., vol. 8, no. 3, pp. 20?29, May/Jun. 2010. [25] A. N. Netravali and J. O. Limb, ?On the performance of distributed polling service-based medium access control,? Proceedings of the IEEE, vol. 68, no. 3, pp. 366?406, Mar. 1980. [26] A. N. Netravali and B. G. Haskell, Digital pictures: representation and compression. New York, NY: Plenum Press, 1988. [27] C. J. Sreenan, J. Chen, P. Agrawal, and B. Narendran, ?Delay reduction techniques for playout buffering,? IEEE Trans. Multimedia, vol. 2, no. 2, pp. 88?100, Jun. 2000. 177 [28] T. Zhang, E. van den Berg, J. Chennikara, P. Agrawal, J. Chen, and T. Kodama, ?Local predictive resource reservation for handoff in multimedia wireless ip networks,? IEEE J. Sel. Areas Commun., vol. 19, no. 10, pp. 1931?1941, Oct. 2001. [29] P. Ramanathan, K. M. Sivalingam, P. Agrawal, and S. Kishore, ?Dynamic resource alloca- tion schemes during handoff for mobile multimedia wireless networks,? IEEE J. Sel. Areas Commun., vol. 17, no. 7, pp. 1270?1283, Jul. 1999. [30] P. Agrawal, E. Hyden, P. Krzyzanowski, P. Mishra, M. B. Srivastava, and J. A. Trotter, ?SWAN: a mobile multimedia wireless network,? IEEE Personal Communications, vol. 3, no. 2, pp. 18?33, Apr. 1996. [31] S. Misra, M. Reisslein, and X. Guoliang, ?A survey of multimedia streaming in wireless sensor networks,? IEEE COMMUNICATION Surveys & Tutorials, vol. 10, pp. 18?39, 2008. [32] I. F. Akyildiz, T. Melodia, and K. R. Chowdury, ?Wireless multimedia sensor networks: A survey,? IEEE Trans. Wireless Commun., vol. 14, no. 6, pp. 32?39, Dec. 2007. [33] P. Agrawal, J. Yeh, J. Chen, and T. Zhang, ?Ip multimedia subsystems in 3GPP and 3GPP2: overview and scalability issues,? IEEE Commun. Mag., vol. 46, no. 1, pp. 138?145, Jan. 2008. [34] A. K. Katsaggelos, F. Zhai, Y. Eisenberg, and R. Berry, ?Energy-efficient wireless video coding and delivery,? IEEE Trans. Wireless Commun., vol. 12, no. 4, pp. 24?30, Aug. 2005. [35] P. Agrawal, J. Chen, S. Kishore, P. Ramanathan, and K. Sivalingam, ?Battery power sen- sitive video processing in wireless networks,? in Proc. IEEE Personal, Indoor and Mobile Radio Communications?98, Sep. 1998, pp. 116?120. [36] Z. He, Y. Liang, L. Chen, I. Ahmad, and D. Wu, ?Power-rate-distortion analysis for wireless video communication under energy constraints,? IEEE Trans. Circuits Syst. Video Technol., vol. 15, no. 5, pp. 645?658, May 2005. [37] D. N. Kwon, P. F. Driessen, A. Basso, and P. Agathoklis, ?Performance and computational complexity optimization in configurable hybrid video coding system,? IEEE Trans. Circuits Syst. Video Technol., vol. 16, no. 1, pp. 31?42, Jan. 2006. [38] H. Cheng and L. Dung, ?A content-based methodology for power-aware motion estimation architecture,? IEEE Trans. Circuits Syst. Video Technol., vol. 52, no. 10, pp. 631?635, Oct. 2005. [39] N. J. August and D. S. Ha, ?Low power design of dct and idct for low bit rate video codecs,? IEEE Trans. Circuits Syst. Video Technol., vol. 6, no. 3, pp. 414?422, Jun. 2004. [40] Z. Cao, B. Foo, L. He, and M. van der Schaar, ?Optimality and improvement of dynamic voltage scaling algorithms for multimedia applications,? IEEE Trans. Circuits Syst. Video Technol., vol. 57, no. 3, pp. 681?690, Mar. 2010. 178 [41] H. M. Wang, H. S. Choi, and J. T. Kim, ?Workload-based dynamic voltage scaling with the qos for streaming video,? in Proc. IEEE Electronic Design, Test and Applications?08, Jan. 2008, pp. 236?239. [42] M. Li, Z. Guo, R. Y. Yao, and W. Zhu, ?A novel penalty controllable dynamic voltage scaling scheme for mobile multimedia applications,? IEEE Trans. Mobile Computing, vol. 5, no. 12, pp. 1719?1733, Dec. 2006. [43] A. Goldsmith, Wireless Communications. New York, NY: Cambridge University Press, 2005. [44] IEEE, ?Part 11, Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications: Medium Access Control (MAC) Enhancements for Quality of Service (QoS),? July 2003, ANSI/IEEE Std 802.11e, Draft 5.0. [45] Y. Huang, P. Walsh, Y. Li, and S. Mao, ?A gnu radio testbed for distributed polling service- based medium access control,? in Proc. IEEE MILCOM?11, Baltimore, MD, Nov. 2011. [46] G. J. Foschini and Z. Miljanic, ?A simple distributed autonomous power control algorithm and its convergence,? IEEE Trans. Veh. Technol., vol. 42, no. 4, pp. 641?646, Nov. 1993. [47] D. Mitra, ?An asynchronous distributed algorithm for power control in cellular radio sys- tem,? in Proc. 4th Winlab Workshop on Third Generation Wireless Information Networks, New Brunswick, NJ, Oct. 1993, pp. 249?257. [48] S. Grandhi, J. Zander, and R. Yates, ?Constrained power control,? Int. J. Wireless Personal Commun., vol. 1, no. 4, pp. 257?270, Apr. 1995. [49] P. Hande, S. Rangan, M. Chiang, and X. Wu, ?Distributed uplink power control for optimal sir assignment in cellular data networks,? IEEE/ACM Trans. Networking., vol. 16, no. 6, pp. 1420?1433, Dec. 2008. [50] J. Lee, R. Mazumdar, and N. Shroff, ?Downlink power allocation for multi-class wireless systems,? IEEE/ACM Trans. Networking, vol. 13, no. 4, pp. 854?867, Aug. 2005. [51] N. Bambos, S. C. Chen, and G. J. Pottie, ?Radio link admission algorithm for wireless net- works with power control and active link quality protection,? in Proc. IEEE INFOCOM?95, Boston, MA, Apr. 1995, pp. 97?104. [52] M. Xiao, N. B. Shroff, and E. K. P. Chong, ?Distributed admission control for power- controlled cellular wireless systems,? IEEE/ACM Trans. Networking, vol. 9, no. 6, pp. 790? 800, Dec. 2001. [53] C. Comaniciu and H. V. Poor, ?Jointly optimal power and admission control for delay sensi- tive traffic in cdma networks with lmmse receivers,? IEEE Trans. Signal Processing, vol. 51, no. 8, pp. 2031?2042, Aug. 2003. [54] G. Liang and B. Liang, ?Balancing interruption frequency and buffering penalties in VBR video streaming,? in Proc. IEEE INFOCOM?07, Anchorage, AK, May 2007, pp. 1406? 1414. 179 [55] Y. Huang, S. Mao, and Y. Li, ?Downlink power allocation for stored variable-bit-rate videos,? in Proc. ICST QShine?10, Houston, TX, Nov. 2010, pp. 423?438. [56] Y. Huang and S. Mao, ?Downlink power control for variable bit rate video over multicell wireless networks,? in Proc. IEEE INFOCOM?11, Shanghai, China, Apr. 2011, pp. 2561? 2569. [57] Y. Huang, S. Mao, and Y. Li, ?Downlink power control for VBR video streaming in cellular networks: A majorization approach,? in Proc. IEEE Globalcom?11, Houston, TX, Dec. 2011, pp. 1?6. [58] ??, ?On downlink power allocation for multiuser variable-bit-rate video streaming,? Wiley Security and Communication Networks, to appear. [59] M. Chiang, ?Balancing transport and physical layers in wireless multihop networks: jointly optimal congestion control and power control,? IEEE J. Sel. Areas Commun., vol. 23, no. 1, pp. 104?116, Jan. 2005. [60] S. Mao, S. Lin, Y. Wang, S. S. Panwar, and Y. Li, ?Multipath video transport over wireless ad hoc networks,? IEEE Wireless Commun., vol. 12, no. 4, pp. 42?49, Aug. 2005. [61] S. Mao, Y. T. Hou, H. D. Sherali, and S. F. Midkiff, ?Multimedia-centric routing for multiple description video in wireless mesh networks,? IEEE Network, vol. 22, no. 1, pp. 19?24, Jan./Feb. 2008. [62] H. Y. Shutoy, D. Gunduz, E. Erkip, and Y. Wang, ?Cooperative source and channel coding for wireless multimedia communications,? IEEE J. Sel. Signal Process., vol. 1, no. 2, pp. 295?307, Aug. 2007. [63] T. Koponen, T. Koponen, B. Chun, A. Ermolinskiy, K. H. Kim, and S. Shenker, ?A data- oriented (and beyond) network architecture,? in ACM SIGCOMM?07, Kyoto, Japan, Agu. 2007, pp. 181?192. [64] X. Lu, E. Erkip, Y. Wang, and D. Goodman, ?Power efficient multimedia communication over wireless channels,? IEEE J. Sel. Areas Commun., vol. 21, no. 10, pp. 1738?1751, Dec. 2003. [65] Y. Eisenberg, C. E. Luna, T. N. Pappas, R. Berry, and A. K. Katsaggelos, ?Joint source coding and transmission power management for energy efficient wireless video communi- cations,? IEEE Trans. Circuits Syst. Video Technol., vol. 12, no. 6, pp. 411?424, Jun. 2002. [66] Y. Li, M. Reisslein, and C. Chakrabarti, ?Energy-efficient video transmission over a wireless link,? IEEE Trans. Veh. Technol., vol. 58, no. 3, pp. 1229?1244, Mar. 2009. [67] Z. Li, F. Zhai, and A. K. Katsaggelos, ?Joint video summarization and transmission adap- tation for energy-efficient wireless video streaming,? EURASIP J. on Advances in Signal Processing, vol. 2008, pp. 1?11, Jan. 2008. 180 [68] D. Wu, S. Ci, and H. Wang, ?Cross-layer optimization for video summary transmission over wireless networks,? IEEE J. Sel. Areas Commun., vol. 25, no. 4, pp. 841?850, May 2007. [69] S. Soro and W. Heinzelman, ?A survey of visual sensor networks,? Advances in Multimedia, vol. 2009, 2009, article ID 640386, 21 pages, doi:10.1155/2009/640386. [70] A. Seema and M. Reisslein, ?Towards efficient wireless video sensor networks: A survey of existing node architectures and proposal for a flexi-wvsnp design,? IEEE Commun. Surveys Tutorials, vol. 13, no. 3, pp. 462?486, Quarter 2011. [71] M. Chen, T. Kwon, S. Mao, Y. Yuan, and V. C. M. Leung, ?Reliable and energy-efficient routing protocol in dense wireless sensor networks,? International Journal of Sensor Net- works, vol. 4, no. 1/2, pp. 104?117, 2008. [72] M. Chen, V. C. M. Leung, and S. Mao, ?Directional controlled fusion in wireless sensor networks,? ACM/Springer MONET, vol. 14, no. 2, pp. 220?229, Apr. 2009. [73] ??, ?Directional controlled fusion in wireless sensor networks,? in Proc. QShine?08, Hong Kong, P.R. China, Jul. 2008, pp. 1?7. [74] J. Liu and S. Singh, ?Atcp: Tcp for mobile ad hoc networks,? IEEE J. Sel. Areas Commun., vol. 19, no. 7, pp. 1300?1315, Jul. 2001. [75] V. Tsaoussidis and H. Badr, ?Tcp-probing: towards an error control schema with energy and throughput performance gains,? in Proc. Network Protocols?00, 2000, pp. 12?21. [76] D. Hu, S. Mao, Y. T. Hou, and J. H. Reed, ?Fine grained scalability video multicast in cognitive radio networks,? IEEE J. Sel. Areas Commun., vol. 28, no. 3, Apr. 2010. [77] D. Hu and S. Mao, ?Streaming scalable videos over multi-hop cognitive radio networks,? IEEE Trans. Wireless Commun., vol. 9, no. 11, pp. 3501?3511, Nov. 2010. [78] Y. Zhao, S. Mao, J. H. Reed, and Y. Huang, ?Experimental study of utility function selection for video over cognitive radio networks,? in Proc. TRIDENTCOM 2009, Washington D.C., Apr. 2009, pp. 1?10. [79] ??, ?Utility function selection for streaming videos with a cognitive engine testbed,? ACM/Springer Mobile Networks and Applications Journal, vol. 15, no. 3, pp. 446?460, June 2010. [80] Y. Huang, S. Mao, and R. M. Nelms, ?Smooth electric power scheduling in power distribu- tion networks,? in Proc. IEEE GLOBECOM 2012 ? Workshop on Smart Grid Communica- tions: Design for Performance, Anaheim, CA, Dec. 2012, pp. 1?5. [81] M. LeMay, R. Nelli, G. Gross, and C. A. Gunter, ?An integrated architecture for demand response communications and control,? in HICSS ?08, Washington, DC, 2008, pp. 174?183. [82] Y. Huang, S. Mao, and R. M. Nelms, ?Adaptive electricity scheduling in microgrids,? in Proc. IEEE INFOCOM 2013, Turin, Italy, Apr. 2013. 181 [83] Y. Huang and S. Mao, ?Adaptive electricity scheduling with quality of usage guarantees in microgrids,? in Proc. IEEE GLOBECOM 2012, Anaheim, CA, Dec. 2012, pp. 1?6. [84] ??, ?On qualify of usage provisioning for electricity scheduling in microgrids,? IEEE Systems Journal, Special Issue on Smart Grind Communications Systems, 2013, to appear. [85] S. Mao, Y. Huang, and Y. Li, ?Downlink vbr video scheduling in cellular networks with orthogonal channels,? IEEE E-Letter for MMTC, vol. 6, no. 9, pp. 40?42, Sept. 2011. [86] Y. Huang, S. Mao, and Y. Li, ?A majorization approach to downlink power control for vbr videos over cellular networks,? Elsevier Computer Communications, vol. 35, no. 15, pp. 1828?1837, Sept. 2012. [87] ??, Green video streaming over cellular networks. New York, NY: CRC Press, 2012, ch. 23, pp. 659?690. [88] G. T. Heydt, ?The next generation of power distribution systems,? IEEE Trans. Smart Grid, vol. 1, no. 3, pp. 225?235, Dec. 2010. [89] S. Shao, M. Pipattanasomporn, and S. Rahman, ?Demand response as a load shaping tool in an intelligent grid with electric vehicles,? IEEE Trans. Smart Grid, vol. 2, no. 4, pp. 624?631, Dec. 2011. [90] A. H. Mohsenian-Rad and A. Leon-Garcia, ?Optimal residential load control with price prediction in real-time electricity pricing environments,? IEEE Trans. Smart Grid, vol. 1, no. 2, pp. 120?133, Sept. 2010. [91] C. Ibars, M. Navarro, and L. Giupponi, ?Distributed demand management in Smart Grid with a congestion game,? in Proc. IEEE SmartGridComm?10, Gaithersburg, MD, Oct. 2010, pp. 495?500. [92] N. Li, L. Chen, and S. H. Low, ?Optimal demand response based on utility maximization in power networks,? in 2011 IEEE PES General Meeting, Detroit, MI, Jul. 2011, pp. 1?8. [93] M. G. Kallitsis, G. Michailidis, and M. Devetsikiotis, ?Optimal power allocation under com- munication network externalities,? IEEE Trans. Smart Grid, vol. 3, no. 1, pp. 162?173, Mar. 2012. [94] J. Medina, N. Muller, and I. Roytelman, ?Demand response and distribution grid operations: Opportunities and challenges,? IEEE Trans. Smart Grid, vol. 1, no. 2, pp. 193?198, Sept. 2010. [95] J. Salehi, Z.-L. Zhang, J. Kurose, and D. Towsley, ?Supporting stored video: reducing rate variability and end-to-end resource requirements through optimal smoothing,? IEEE/ACM Trans. Networking., vol. 6, no. 4, pp. 397?410, Aug. 1998. [96] E. Jorswieck and H. Boche, ?Optimal transmission strategies and impact of correlation in multiantenna systems with different types of channel state information,? IEEE Trans. Signal Processing, vol. 52, no. 12, pp. 3440?3453, Dec. 2004. 182 [97] A. Papavasiliou and S. S. Oren, ?Supplying renewable energy to deferrable loads: Algo- rithms and economic analysis,? in Proc. IEEE Power & Energy Society General Meeting?10, Jul. 2010, pp. 1?8. [98] B. C. Arnold, Majorization and the Lorenz Order: A Brief Introduction. New York, NY: Springer-Verlag, 1987. [99] A. Keyhani, Design of Smart Power Grid Renewable Energy Systems. Hoboken, NJ: Wiley-IEEE Press, 2011. [100] D. P. Palomar and M. Chiang, ?A tutorial on decomposition methods for network utility maximization,? IEEE J. Sel. Areas Commun., vol. 24, no. 8, pp. 1439?1451, Aug. 2006. [101] M. Fahrioglu and F. L. Alvarado, ?Designing incentive compatible contracts for effective demand management,? IEEE Trans. Power Systems, vol. 15, no. 4, pp. 1255?1260, Nov. 2000. [102] P. Samadi, A. Mohsenian-Rad, R. Schober, V. Wong, and J. Jatskevich, ?Optimal real- time pricing algorithm based on utility maximization for smart grid,? in IEEE SmartGrid- Comm?10, Oct. 2010, pp. 415?420. [103] A. J. Wood and B. F. Wollenberg, Power Generation, Operation, and Control. New York: John Wiley & Sons, 1984. [104] F. Rahimi and A. Ipakchi, ?Demand response as a market resource under the smart grid paradigm,? IEEE Trans. Smart Grid, vol. 1, no. 1, pp. 82?88, Jun. 2010. [105] S. Amin and B. Wollenberg, ?Toward a smart grid: power delivery for the 21st century,? IEEE Power and Energy Mag., vol. 3, no. 5, pp. 1?37, Sept.-Oct. 2005. [106] A. Mohsenian-Rad, V. Wong, J. Jatskevich, R. Schober, and A. Leon-Garcia, ?Autonomous demand-side management based on game-theoretic energy consumption scheduling for the future smart grid,? IEEE Trans. Smart Grid, vol. 1, no. 3, pp. 320?331, Dec. 2010. [107] H. K. Nguyen, J. B. Song, and Z. Han, ?Demand side management to reduce peak-to- average ratio using game theory in smart grid,? in Proc. IEEE INFOCOM Workshops?12, Orlando, FL, Mar. 2012, pp. 91?96. [108] J. Huang, C. Jiang, and R. Xu, ?A review on distributed energy resources and microgrid,? ELSEVIER Renewable and Sustainable Energy Reviews, vol. 12, no. 9, pp. 2472?2483, Dec. 2008. [109] E. Fumagalli, J. W. Black, I. Vogelsang, and M. Ilic, ?Quality of service provision in elec- tric power distribution systems through reliability insurance,? IEEE Trans. Power Systems, vol. 19, no. 3, pp. 1286?1293, Aug. 2004. [110] J. Slotine and W. Li, Applied Nonlinear Control. Prentice Hall, 1991. [111] T. T. Kim and H. H. V. Poor, ?Scheduling power consumption with price uncertainty,? IEEE Trans. Smart Grid, vol. 2, no. 3, pp. 519?527, Sept. 2011. 183 [112] M. J. Neely, E. Modiano, and C. E. Rohrs, ?Dynamic power allocation and routing for time- varying wireless networks,? IEEE J. Sel. Areas Commun., vol. 23, no. 1, pp. 89?103, Jan. 2005. [113] M. J. Neely, ?Stock market trading via stochastic network optimization,? in Proc. IEEE CDC?10, Atlanta, GA, Dec. 2010, pp. 1?8. [114] M. J. Neely, A. S. Tehrani, and A. G. Dimakis, ?Efficient algorithms for renewable energy allocation to delay tolerant consumers,? in IEEE SmartGridComm?10, Oct. 2010, pp. 549? 554. [115] M. J. Neely and R. Urgaonkar, ?Opportunism, backpressure, and stochastic optimization with the wireless broadcast advantage,? in Asilomar Conference on Signals, Systems, and Computers?08, Pacific Grove, CA, Oct. 2008, pp. 1?7. [116] The National Renewable Energy Laboratory, ?Western wind resources dataset,? [online] Available: http://wind.nrel.gov/Web nrel/. [117] S. B. Peterson, J. F. Whitacre, and J. Apt, ?The economics of using plug-in hybrid electric vehicle battery packs for grid storage,? J. Power Sources, vol. 195, no. 8, pp. 2377?2384, 2010. [118] ?The Electric Reliability Council of Texas,? [online] Available: http://www.ercot.com/. [119] M. He, S. Murugesan, and J. Zhang, ?Multiple timescale dispatch and scheduling for stochastic reliability in smart grids with wind generation integration,? in Proc. IEEE IN- FOCOM?11, Shanghai, China, Apr. 2011, pp. 461?465. [120] B. Karimi and V. Namboodiri, ?Capacity analysis of a wireless backhaul for metering in the smart grid,? in Proc. IEEE INFOCOM?12, Orlando, FL, Mar. 2012, pp. 61?66. [121] Z. Lu, W. Wang, and C. Wang, ?Hiding traffic with camouflage: Minimizing message delay in the smart grid under jamming,? in Proc. IEEE INFOCOM?12, Orlando, FL, Mar. 2012, pp. 3066?3070. [122] M. A. Rahman, P. Bera, and E. Al-Shaer, ?Smartanalyzer: A noninvasive security threat analyzer for AMI smart grid,? in Proc. IEEE INFOCOM?12, Orlando, FL, Mar. 2012, pp. 2255?2263. [123] H. Ma, H. Li, and Z. Han, ?A framework of frequency oscillation in power grid: Epidemic propagation over social networks,? in Proc. IEEE INFOCOM?12, Orlando, FL, Mar. 2012, pp. 67?72. [124] H. Liang, B. J. Choi, W. Zhuang, and X. Shen, ?Towards optimal energy store-carry-and- deliver for PHEVs via V2G system,? in Proc. IEEE INFOCOM?12, Orlando, FL, Mar. 2012, pp. 1674?1682. [125] X. Liu, ?Economic load dispatch constrained by wind power availability: A wait-and-see approach,? IEEE Trans. Smart Grid, vol. 1, no. 3, pp. 347?355, Dec. 2010. 184 [126] X. Fang, D. Yang, and G. Xue, ?Online strategizing distributed renewable energy resource access in islanded microgrids,? in IEEE GLOBECOM?11, Huston, TX, Dec. 2011, pp. 1931?1937. [127] I. Koutsopoulos, V. Hatzi, and L. Tassiulas, ?Optimal energy storage control policies for the smart power grid,? in IEEE SmartGridComm?11, Oct. 2011, pp. 475?480. [128] S. X. Chen, H. B. Gooi, and M. Q. Wang, ?Sizing of energy storage for microgrids,? IEEE Trans. Smart Grid, vol. 3, no. 1, pp. 142?151, Mar. 2012. [129] R. Urgaonkar, B. Urgaonkar, M. J. Neely, and A. Sivasubramaniam, ?Optimal power cost management using stored energy in data centers,? in Proc. ACM SIGMETRICS?11, San Jose, CA, Jun. 2011, pp. 221?232. [130] H. Sistek, ?Green-tech base stations cut diesel usage by 80 percent,? Apr. 2008, [online] Available: http://news.cnet.com/8301-11128 3-9912124-54.html. [131] M. W. Garrett and W. Willinger, ?Analysis, modeling and generation of self-similar VBR video traffic,? ACM SIGCOMM Comput. Commun. Rev., vol. 24, no. 4, pp. 269?280, 1994. [132] J. Beran, R. Sherman, M. Taqqu, and W. Willinger, ?Long-range dependence in variable-bit- rate video traffic,? IEEE Trans. Commun., vol. 43, no. 2/3/4, pp. 1566?1579, Feb./Mar./Apr. 1995. [133] D. P. Heyman and T. V. Lakshmanr, ?What are the implications of long-range dependence for VBR-video traffic engineering?? IEEE/ACM Trans. Networking, vol. 4, no. 3, pp. 301? 317, June 1996. [134] T. Lakshman, A. Ortega, and A. Reibman, ?VBR video: Trade-offs and potentials,? Proc. IEEE, vol. 86, no. 1, pp. 952?973, May 1998. [135] S. Liew and H. Chan, ?Lossless aggregation: a scheme for transmitting multiple stored VBR video streams over a shared communications channel without loss of image quality,? IEEE J. Sel. Areas Commun., vol. 15, no. 6, pp. 1181?1189, Aug. 1997. [136] S. Sen, D. Towsley, Z. Zhang, and J. K. Dey, ?Optimal multicast smoothing of streaming video over the internet,? IEEE J. Sel. Areas Commun., vol. 20, no. 7, pp. 1345?1359, Sep. 2002. [137] J. Lee and J. Kwon, ?Utility-based power allocation for multiclass wireless systems,? IEEE Trans. Vehic Tech., vol. 58, no. 7, pp. 3813?3819, Sep. 2009. [138] A. Gjendemsj, D. Gesbert, G. Oien, and S. Kiani, ?Binary power control for sum rate max- imization over multiple interfering links,? IEEE Trans. Wireless Commun., vol. 7, no. 8, pp. 3164?3173, Aug. 2008. [139] M. Reisslein, ?Video trace library,? Arizona State University, [online] Available: http://trace.eas.asu.edu/. 185 [140] UMTS World, UMTS Power Control, [online] Available: http://www.umtsworld.com/ technology/power.htm. [141] J. M. Mcmanus and K. W. Ross, ?A dynamic programming methodology for managing prerecorded vbr sources in packet-switched networks,? in Proc. SPIE, Performance and Control of Network Systems, 1997, pp. 140?154. [142] S. Deng, T. Webera, and A. Ahrens, ?Capacity optimizing power allocation in interference channels,? AEU - International Journal of Electronics and Communications, vol. 63, no. 2, pp. 139?147, Jan. 2009. [143] T. Stockhammer, H. Jenkac, and G. Kuhn, ?Streaming video over variable bit-rate wireless channels,? IEEE Trans. Multimedia, vol. 6, no. 2, pp. 268?277, Apr. 2004. [144] M. Chen and A. Zakhor, ?Multiple TFRC connections based rate control for wireless net- works,? IEEE Trans. Multimedia, vol. 8, no. 5, pp. 1045?1062, Oct. 2006. [145] H. D. Sherali and W. P. Adams, A Reformulation-Linearization Technique for Solving Dis- crete and Continuous Nonconvex Problems. Dordrecht, Boston, London: Kluwer Aca- demic Publishers, 1999. [146] S. Kompella, S. Mao, Y. Hou, and H. Sherali, ?On path selection and rate allocation for video in wireless mesh networks,? IEEE/ACM Trans. Networking., vol. 17, no. 1, pp. 212? 224, Feb. 2009. [147] M. Andersin, Z. Rosberg, and J. Zander, ?Gradual removals in cellular PCS with constrained power control and noise,? in Proc. IEEE PIMRC?95, Toronto, Canada, Sept. 1995, pp. 56? 60. [148] A. Naman and D. Taubman, ?JPEG2000-based scalable interactive video (JSIV),? IEEE Trans. Image Process., vol. 20, no. 5, pp. 1435?1449, May 2011. [149] W.-K. Liao and Y.-H. Lai, ?Type-aware error control for robust interactive video services over time-varying wireless channels,? IEEE Trans. Mobile Comput., vol. 10, no. 1, pp. 136? 145, Jan. 2011. [150] G. Cheung, A. Ortega, and N.-M. Cheung, ?Interactive streaming of stored multiview video using redundant frame structures,? IEEE Trans. Image Process., vol. 20, no. 3, pp. 744?761, Mar. 2011. [151] A. Dan, P. Shahabuddin, D. Sitaram, and D. Towsley, ?Channel allocation under batching and vcr control in movie-on-demand servers,? J. Parallel Distrib. Comput., vol. 30, pp. 168? 179, 1995. [152] buto.tv, ?Feature: Clickable videointeractive, clickable video that anyone can build in min- utes,? [online] Available: http://get.buto.tv/features/clickable-video/. 186