Luận án: Kiểm soát và Tối ưu hóa Phân tán cho Hệ thống Truyền thông và Điện bởi Qiuyu Peng

Distributed Control and Optimization for Communication and Power Systems Thesis by Qiuyu Peng In Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy California Institute of Technology Pasadena, California 2016 (Defended December 07, 2015) ii c 2016 Qiuyu Peng All Rights Reserved iii This thesis is dedicated to my girlfriend Huan, whose love made this possible, and my parents, who have supported me all the way. iv Acknowledgements First and foremost, I would like to express my deepest gratitude to my advisor, Professor Steven Low, for his continuous support of my Ph. Steven is a great scholar who dedicates to work on impactful and hard research problems. He introduced me to a variety of research areas in both communication and power networks.

He gave me freedom and supported me to work on projects based on my own interests. It is his enthusiasm on research that motivates me to think big and work on important research problems no matter how hard they look. I could not have imagined having a better advisor and mentor for my Ph. Besides my advisor, I would like to thank the rest of my thesis committee: Professor John Doyle, Professor Mani Chandy, Professor P.

Vaidyanathan and Professor Adam Wierman. It’s really my great honor to have them on my committee. They gave me their insightful comments and encouragement. I learned advanced control theory in John’s class.

Mani raised many interesting questions in both my candidacy exam and thesis defense that were very beneficial in the completion of my thesis. V’s class on signal processing and he could always explain the complex formula from different perspectives. Adam gave me great help and advice on writing good papers and making presentations. He taught me how to communicate complicated ideas through plain English that people could easily understand.

I am also thankful to my former research advisor, Professor Xinbing Wang, for his guidance during my undergraduate study at Shanghai Jiao Tong University. I was a junior when I joined Xinbing’s lab. He gave me much advice on doing research and encouraged me to pursue my Ph. It was his advice and encouragement that made it possible for me to study at Caltech.

My collaborators also gave me their great supports: Anwar Walid, Jaehyun Hwang from Bell Lab, Minghua Chen from Chinese University of Hong Kong and Seungil You, Yujie Tang from Caltech. It was a great pleasure to work with these great minds and I am grateful for all of those fruitful discussions. I am grateful to all the colleagues in my research group RSRG. Special thanks to an incomplete list of current and past group members: Minghong Lin, Zhenhua Liu, Lingwen Gan, Desmond Cai, Changhong Zhao, Xiaoqi Ren and Niangjun Chen, etc.

The department of Electrical Engineering at California Institute of Technology provides a great v and cozy environment. It is a paradise for studying and doing research. I want to thank the great help from staff members, especially Christine Ortega, Sydney Garstang and Tanya Owen. Finally, I would like to thank my parents for their spiritual support during the past five years.

It is their supports and love that gave me the strength and stamina to finish my Ph. I dedicate this thesis to my parents as an inadequate appreciation of everything that they have done for me. vi Abstract We are at the cusp of a historic transformation of both communication system and electricity system. This creates challenges as well as opportunities for the study of networked systems.

Problems of these systems typically involve a huge number of end points that require intelligent coordination in a distributed manner. In this thesis, we develop models, theories, and scalable distributed optimization and control algorithms to overcome these challenges. This thesis focuses on two specific areas: multi-path TCP (Transmission Control Protocol) and electricity distribution system operation and control. Multi-path TCP (MP-TCP) is a TCP exten- sion that allows a single data stream to be split across multiple paths.

MP-TCP has the potential to greatly improve reliability as well as efficiency of communication devices. We propose a fluid model for a large class of MP-TCP algorithms and identify design criteria that guarantee the existence, uniqueness, and stability of system equilibrium. We clarify how algorithm parameters impact TCP- friendliness, responsiveness, and window oscillation and demonstrate an inevitable tradeoff among these properties. We discuss the implications of these properties on the behavior of existing algo- rithms and motivate a new algorithm Balia (balanced linked adaptation) which generalizes existing algorithms and strikes a good balance among TCP-friendliness, responsiveness, and window oscilla- tion.

We have implemented Balia in the Linux kernel. We use our prototype to compare the new proposed algorithm Balia with existing MP-TCP algorithms. Our second focus is on designing computationally efficient algorithms for electricity distribution system operation and control. First, we develop efficient algorithms for feeder reconfiguration in distribution networks.

The feeder reconfiguration problem chooses the on/off status of the switches in a distribution network in order to minimize a certain cost such as power loss. It is a mixed integer nonlinear program and hence hard to solve. We propose a heuristic algorithm that is based on the recently developed convex relaxation of the optimal power flow problem. The algorithm is efficient and can successfully computes an optimal configuration on all networks that we have tested.

Moreover we prove that the algorithm solves the feeder reconfiguration problem optimally under certain conditions. We also propose a more efficient algorithm and it incurs a loss in optimality of less than 3% on the test networks. Second, we develop efficient distributed algorithms that solve the optimal power flow (OPF) vii problem on distribution networks. The OPF problem determines a network operating point that minimizes a certain objective such as generation cost or power loss.

Traditionally OPF is solved in a centralized manner. With increasing penetration of volatile renewable energy resources in distribu- tion systems, we need faster and distributed solutions for real-time feedback control. This is difficult because power flow equations are nonlinear and kirchhoff’s law is global. We propose solutions for both balanced and unbalanced radial distribution networks.

They exploit recent results that suggest solving for a globally optimal solution of OPF over a radial network through a second-order cone program (SOCP) or semi-definite program (SDP) relaxation. Our distributed algorithms are based on the alternating direction method of multiplier (ADMM), but unlike standard ADMM-based dis- tributed OPF algorithms that require solving optimization subproblems using iterative methods, the proposed solutions exploit the problem structure that greatly reduce the computation time. Specifically, for balanced networks, our decomposition allows us to derive closed form solutions for these subproblems and it speeds up the convergence by 1000x times in simulations. For unbalanced networks, the subproblems reduce to either closed form solutions or eigenvalue problems whose size remains constant as the network scales up and computation time is reduced by 100x compared with iterative methods.

viii Contents Acknowledgements iv Abstract vi 1 Introduction 1 1.2 Feeder Reconfiguration in Distribution Networks .3 Distributed OPF Algorithm on Radial Distribution Networks. 4 2 Multipath TCP: Analysis, Design and Implementation 5 2.1 Multipath TCP model .2 Existing MP-TCP algorithms .3 Existence, uniqueness and stability of equilibrium .5 Responsiveness around equilibrium .3 Implications and a new algorithm .1 Implications on existing algorithms .A Proof of Theorem 2.B Proof of Theorem 2.1 Proof of part 1 .2 Proof of part 2 .C Proof of Theorem 2.D Proof of Theorem 2.E Proof of Theorem 2.1 Proof of part 1 .2 Proof of part 2 .F Proof of Theorem 2.G Proof of Theorem 2.1 Proof of part 1 .2 Proof of part 2 .H Proof of Lemma 2. 38 3 Optimal Power Flow and Convex Relaxation 39 3.1 OPF and its SOCP Relaxation on Balanced Networks .1 Branch flow model .2 OPF and SOCP Relaxation .2 OPF and its SDP relaxation on Unbalanced Networks .1 Branch flow model .2 OPF and SDP relaxation. 48 4 Feeder Reconfiguration in Distribution Networks Based on Convex Relaxation of OPF 49 4.2 Model and Problem formulation .2 Network Configuration with Single Redundant Line .3 General network configuration .1 Case I: Tai-83 Bus System [81] .2 Case II: Brazil-135 Bus System [63] .3 Case III: SCE-47 Bus System .4 Case IV: SCE-56 Bus System .A Proof of Lemma 4.B Proof of Theorem 4.C Proof of Lemma 4.D Proof of Theorem 4.

71 5 Alternating Direction Method of Multipliers (ADMM) 78 5.1 Background on ADMM .2 Algorithm Design using ADMM .1 Optimal Power Flow .2 Second Order Cone Program. 92 6 Distributed OPF Algorithm: Balanced Radial Distribution Networks 93 6.2 Distributed OPF Algorithm on Balanced Networks .1 Simulation on a 2,065-bus circuit .2 Rate of Convergence .A Solution Procedure for Problem (6.B Solution Procedure for Problem (6.1 Ii takes the form of (3.2 Ii takes the form of (3. 111 7 Distributed OPF Algorithm: Unbalanced Radial Distribution Networks 112 7.2 Distributed OPF Algorithm on Unbalanced Networks .1 Simulations on IEEE test feeders .2 Rate of convergence .A Proof of Theorem 7. 126 Bibliography 127 xii List of Figures 2.1 Test network for the definition of TCP friendliness.

The link in the middle is the only bottleneck link with capacity c.2 Network for our Linux-based experiments on TCP friendliness and responsiveness, with N1 MP-TCP flows and N2 single-path TCP flows sharing two links of capacity, c1 , c2 , and propagation delay (single trip) T1 , T2. MP-TCP flows maintain two routes with rate x1 , x2. Single-path TCP flows maintain one route with rate x3 .3 Responsiveness Performance: congestion window trajectory of MP-TCP for each path (left column). SP-TCP starts at time 40s and ends at 80s.

The throughput of SP- TCP and total throughput of MP-TCP are shown in the right column. Parameters: T1 = T2 = 10ms, c1 = c2 = 20Mbps, and N1 = 1, N2 = 5.4 Window oscillation: the red trajectories represent throughput fluctuations experienced by the application in the case of MP-TCP and the case of single-path TCP.1 Notations of graph G(N , E), where the ancestor and children set of node 3 are also labeled explictly.1 Notations for Balanced Network.1 Notations for Unbalanced Networks.1 Possible network topology with one redundant line.3 Intuitions of Algoirthm 4.1 A modified SCE 47-bus feeder. The blue bar (1) represents the substation bus, the red dots (13, 17, 19, 23, 24) represent buses with PV panels, and the other dots represent load buses without PV panels.2 A modified SCE 56-bus feeder. The blue bars (1, 57, 58) represent the substation buses and the red dot (45) represents the bus with PV panels.1 Message passing for a node i.1 Graph representation of SOCP.1 Simulation results for 2065 bus distribution network.2 Topologies for tree and fat tree networks.1 Topologies for line and fat tree networks.

124 xiv List of Tables 2.1 MP-TCP algorithms .2 How design choices affect MP-TCP performance.3 TCP friendliness (same RTTs): Average throughput (Mbps) and 95% confidence in- terval of MP-TCP and single-path TCP users.4 Basic behavior (WiFi/3G): throughput (Mbps) of a MP-TCP user and 95% confidence interval.5 Responsiveness: convergence time (s) of MP-TCP and total throughput (Mbps) of all single-path TCP users.1 Network of Fig.1: Line impedances, peak spot load KVA, Capacitors and PV gen- eration’s nameplate ratings.2 Summary on Brazil-135 Bus System .3 Summary on Tai-83 Bus System .4 Network of Fig.2: Line impedances, peak spot load KVA, Capacitors and PV gen- eration’s nameplate ratings.1 Multipliers associated with constraints(6.1 Statistics of different networks .2 Statistics of line and fat tree networks .1 Multipliers associated with constraints (7.1 Statistics of different networks .2 Statistics of line and fat tree networks. 124 xv List of Algorithms 4.1 Network with one redundant line .2 Network with one redundant line (simplified) .3 General Network Reconfiguration .4 General Network Reconfiguration (simplified) .1 Initialization of the Algorithm .2 Distributed OPF algorithm on Balanced Radial Networks .1 Initialization of the Algorithm .2 Distributed OPF algorithm on Unbalanced Radial Networks .