Mitigation of communication failures in distributed model predictive control strategies

On the Mitigation of Communication Failures in Distributed Model Predictive Control Strategies Wicak Ananduta, Julian Barreiro-Gomez, Carlos Ocampo-Martinez, and Nicanor Quijano Abstract— Information sharing among local controllers is the key feature of any Distributed Model Predictive Control (DMPC) strategy. This paper addresses the problem of communication failures in DMPC strategies and proposes a distributed solution to cope with them. The proposal consists in an information-exchange protocol that is based on distributed projection dynamics. By applying this protocol as a complementary plug-in to a DMPC strategy, the controllers become resilient against communication failures and relax the communication requirements. Furthermore, a discussion on the selection criteria of the information-sharing network and a reconfiguration algorithm, which is a contingency procedure to maintain the connectivity of the network, are also presented. In order to demonstrate the performance and advantages when adopting the proposed approach, a case study of a powernetwork control problem is considered. Index Terms— Distributed MPC, information-exchange protocol, distributed projection dynamics I. INTRODUCTION Research in Model Predictive Control (MPC) has been extensively done since the past decades (see e.g., [1]–[4] for a review). Such studies include the application of MPC to large-scale systems, i.e., systems that have a large number of inputs, states, and/or outputs. Since an MPC controller computes control inputs by solving an optimization problem, the problem may become intractable when the system is too large [3]. Therefore, many works in the literature have proposed non-centralized MPC approaches, in which there are multiple local controllers as opposed to the centralized approach, which has a single central controller, in order to cope with such problem [3], [4]. Furthermore, noncentralized MPC approaches could also introduce additional benefits such as better scalability, flexibility, and safety than the centralized counterpart [4]. Non-centralized MPC approaches can be classified into two broad categories: decentralized and distributed apW. Ananduta and C. Ocampo-Martinez are with the Automatic Control Department, Universitat Polit` ecnica de Catalunya, Institut de Rob` otica i Inform` atica Industrial (CSIC-UPC), Barcelona, Spain (emails: {wananduta, cocampo}@iri.upc.edu) J. Barreiro-Gomez is with Learning and Game Theory Laboratory, New York University in Abu Dhabi (NYUAD), Saadiyat Campus PO BOX 129188, United Arab Emirates (email: [email protected]) Nicanor Quijano is with Departamento de Ingenier´ ıa El´ ectrica y Electr´ onica, Universidad de los Andes, Bogot´ a, Colombia (email: [email protected]) The work of W. Ananduta has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 675318 (INCITE). J. BarreiroGomez acknowledges U.S. Air Force Office of Scientific Research under grant number FA9550-17-1-0259. N. Quijano acknowledges SGR C/marca project 2015-2017. proaches. The main difference between these two schemes is the existence of communication among local controllers, which can be found in the latter category [3]. The availability of communication plays an important role for the performance of distributed MPC (DMPC) approaches, which is better than the decentralized ones when the couplings between sub-systems are not weak [4]. In fact, in certain cases, some DMPC approaches are also able to achieve similar performance as the centralized counterpart [4]. Different DMPC approaches require different communication structure as well as different ways to exchange information among local controllers [3]. Some DMPC approaches require local controllers to share information iteratively while others require that the information exchange is made only once at each time instant. In terms of informationsharing network, some approaches, such as [5]–[7], require a neighbour-to-neighbour communication while other approaches, e.g., [8], [9], require all controllers to exchange information with all the others. In any way, the informationsharing network, through which the exchange of information occurs, is important for systems that use a DMPC approach. Some issues of an information-sharing network may arise during the operation of the associated system. Those issues include communication failures (total loss of communication links), delays, and data packet drops [10]. This paper focuses on the failures (loss of links) in the information-sharing network, in which some local controllers are no longer able to communicate with others. As mentioned in [10] and later discussed, communication failures may lead to severe problems such as the inability of the controllers to compute control inputs or the sub-optimality of the solutions. Some recent literature has addressed the problem of communication failures in a distributed control strategy, in particular DMPC. The authors of [11] analyse the performance degradation of a DMPC strategy that is based on Nash optimality during such failures while assuming that the algorithm is convergent. The authors of [12] propose a scheme where the sub-systems assume that their neighbours take null control actions during communication failures. In [13], the authors develop a methodology to extend the DMPC strategy that is proposed in [14] such that it can cope with communication failures. The methodology involves substituting the coupled constraints with tube-based constraints that restrict the control inputs. Furthermore, [15] proposes to add an observer for a robust DMPC strategy. Hence, during a communication failure, the state bounds are estimated by the observer and are posed as extra constraints into the DMPC design. Additionally, a resilient information-sharing network architecture for distributed frequency regulation is proposed in [16]. Moreover, the controller in [16] adopts a zero-bias control strategy and allows other sub-systems to stabilize themselves. The aforementioned contributions only improve some DMPC strategies to tackle communication failures in a way that they specifically add or modify the algorithms. Therefore, they limit the application of the solution only to the DMPC strategies that are discussed in those papers. In this regard, different from the works previously discussed, this paper proposes a communication protocol that can be applied regardless DMPC strategy that is used to control the system. The protocol is an iterative algorithm that requires local controllers to communicate at each iteration until the information that is received converges to the correct value. It is based on the distributed projection dynamics (DPD) [17], [18] and can also be perceived as a distributed consensus protocol [19]. For an extensive treatment of the notion of distributed population dynamics, the reader is referred to [17], [18]. In this paper, an application of the proposed approach is illustrated in a power-allocation problem of interconnected microgrids. These kinds of systems are of large nature and spread over large geographical areas. Furthermore, in the current development of these systems, the power generation is shifted toward distributed generation, particularly renewable energy sources [20]. For these reasons, distributed controllers have been viewed as suitable control approaches [20]–[23]. In this regard and highlighting the fact that power networks are considered to be a critical infrastructure, it is important to ensure the resiliency of the control approach against failures, in particular communication failures. In summary, the main contribution of this paper is the information-exchange protocol that is based on DPD, as presented in Section III. This protocol can be applied to any DMPC strategy and improves the resilience of the DMPC strategy against communication failures as well as relaxes the communication requirements. Criteria to select a suitable information-sharing network for the proposed protocol and a network reconfiguration algorithm that supplements the protocol are also proposed. Moreover, prior to proposing the protocol, Section II provides an analysis of the impact of communication failures in a DMPC strategy. Furthermore, the advantages of the proposed protocol in a power allocation problem of microgrids are shown in Section IV. Notations The statements A0and B0imply Aand Bare positive semi-definite and positive definite, respectively. The set of real numbers is denoted by Rwhereas the set of integers is denoted by Z. Moreover, R≥adenotes all real numbers in the set {i:i≥a, i, a ∈R}and, similarly, Z≥adenotes all integers in the set {i:i≥a, i, a ∈Z}. In addition, | · | is the cardinality operator and k·k2is the Euclidean norm. The vector 0ndenotes [0 0 · · · 0]>∈Rn and, similarly, 1n= [1 1 · · · 1]>∈Rn. The subscript k∈Z≥0denotes discrete-time instants while the subscript t∈R≥0denotes continuous-time instants. For the vectors vj∈Rnjwith j∈ N, the operator [v> j]> j∈N ∈RPj∈N nj denotes the column-wise concatenation that results in a column-wise vector. Moreover, consider a time-dependent vector ui,k and a prediction horizon hp. Then, ˜ ui,k denotes the trajectory of ui,k over the prediction horizon hp, i.e., ˜ ui,k =hu> i,k|ku> i,k+1|k· · · u> i,k+hp−1|ki> . Finally, rnd(·) is the round operator that approximates the argument to the nearest integer. In the case there are two nearest integers, the argument is approximated to the larger integer. II. DISTRIBUTED MPC AND COMMUNICATION FAILURES In this section, a general description of the system that is considered and the DMPC approach are presented. Afterwards, a discussion of the impact of communication failures in a DMPC strategy is provided. A. Distributed MPC Consider a time-invariant linear large-scale system (LSS) that consists of nsub-systems. Let it be described by an undirected graph G= (S,E), where the set of nodes, S={1,2, . . . , n}denotes its sub-systems and the set of unweighted links, E ⊆ S × S, represents the existence of coupling between the sub-systems, i.e., (i, j)∈ E implies that the ith sub-system is physically coupled to the jth subsystem. Furthermore, Nidenotes the set of the neighbours of the ith sub-system, i.e., Ni={j: (i, j)∈ E,∀j6=i}. Let the dynamics of this LSS be described by the discrete-time state-space model of each sub-system, i.e., for each i∈ S, xi,k+1 =Aiixi,k +Biiui,k,(1) where the states and the control inputs the ith sub-system are denoted by the vectors xi∈Rnx,i and ui∈Rnu,i , respectively. Moreover, Aii and Bii are the state-space matrices with the appropriate sizes that define the dynamics in (1). Note that the dynamics of each sub-system might also depend on the states, inputs, and/or disturbances of the neighbouring sub-systems. However, for simplicity of the exposition in Subsection II-B, such dynamical couplings are omitted. Instead, some constraints that couple the inputs will be introduced. Moreover, Gis undirected and unweighted since the interest of this paper is in the existence of communication, as in [13]. The control inputs are constrained by local polytopic constraints described by Hiui,k ≤hi, for each i∈ S, where Hi∈Rnh,i×nu,i and hi∈Rnh,i are constant matrix and vector, respectively. Furthermore, there also exist some hard coupled constraints on the control inputs that are described as Pi∈S Giuc i,k ≤g,where Gi∈Rng×nuc,i , for all i∈ S, and g∈Rngare constant matrices and vector, respectively. Moreover, uc i,k ∈Rnuc,i , for all i∈ S, denote the elements of input ui,k that appear in the coupled constraints. In other words, ui,k can be arranged such that ui,k = [ul> i,k uc> i,k]>, where ul i,k ∈Rnul,i denotes the local control inputs. Notice that the coupled constraints may be constraints in which the sub-systems share a limited common input source. Hence, the optimization problem that should be solved in an MPC scheme at each time instant k∈Z≥0is minimize {˜ ui,k}i∈S X i∈S Ji(xi,k,˜ ui,k)(2a) subject to xi,`+1|k=Aiixi,`|k+Biiui,`|k,∀i∈ S,(2b) Hiui,`|k≤hi,xi,k+hp|k∈ X t i,∀i∈ S,(2c) X i∈S Giuc i,`|k≤g,(2d) for all `∈ {k,...,k+hp−1}, where the trajectory of control input sequence throughout hpat time instant kfor each subsystem is denoted by ˜ ui,k. Notice that the cost function over hpis separable and it is defined as Ji(xi,k,˜ ui,k) = k+hp−1 X `=k x> i,`|kQixi,`|k+u> i,`|kRiui,`|k +Jt i(xi,k+hp|k), where Qi0,Ri0and it is assumed that Problem (2) is feasible. Moreover, Jt i(xi,k+hp), which denotes a convex terminal cost function and Xt i, which denotes a terminal set that is convex, compact, and contains the origin, are introduced and defined in order to guarantee stability [4], [6]. Therefore, since the cost function is strictly convex and by definition the constraints are also convex, Problem (2) is convex. In a DMPC scheme, sub-problems are derived by decomposing (2) and they are solved by local controllers assigned to the sub-systems. When solving the sub-problems, the local controllers need to share some information among each other. Therefore, a DMPC strategy requires an information-sharing network. In this regard, let the information-sharing network of system Gbe described by an undirected connected graph ˜ G= (S,˜ E), where the set ˜ Eshows how the local controllers share information in this network, i.e., the link (i, j)∈˜ Einfers that there exists a bidirectional information flow between the ith and jth sub-systems through a communication channel. Many distributed MPC methods, e.g., [5]–[7], require that local controllers share information with their neighbours in G. This means that ˜ E=E. Other methods, e.g., the method presented in [8] and [9], require full information exchange, i.e., ˜ Gshould be a complete graph. B. Impacts of Communication Failures The availability of communication between sub-systems is the main feature of DMPC strategies. Therefore, this section is dedicated to show, by an example, what could happen when there are failures in the information-sharing network, i.e., at least one communication link fails for a certain time slot. During this period, the affected sub-systems cannot communicate with each other while employing a DMPC strategy. For this example, without loss of generality, consider a system that consists of two sub-systems, i.e., S= {1,2}. Moreover, consider that the system has dynamics and constraints as described in the previous subsection, implying that Problem (2) must be solved by the DMPC controllers. Furthermore, let ˜ u? i,k, for all i∈ S, be the optimal solution of this problem. Now, a DMPC strategy that is based on dual decomposition is considered to be implemented and the control inputs obtained by this strategy are analysed. In principle, the DMPC strategies that are based on dual decomposition are iterative and use the concept of duality in convex optimization [24]. The iterations, which are called the distributed dual ascent, are intended to optimize the Lagrange multipliers that are associated with the coupled constraints in order to solve its dual problem [25]. The solution of this algorithm converges to the global optimal value if the primal problem is convex and the cost function is strictly convex [25]. The iteration steps of the distributed dual ascent algorithm that is applied by the ith sub-system for problem (2) are as follows: 1. 1) The update of the decision ˜ ui,k at the rth iteration is ˜ u(r) i,k =argmin ˜ ui,k Ji(xi,k,˜ ui,k) + k+hp−1 X `=kλ(r)> i,`|kGiuc i,`|k subject to (2b),(2c),∀`∈ {k,...,k+hp−1}, (3) in which λ(r) i,`|k, for all `∈ {k,...,k+hp−1}and i∈ S, are the Lagrange multipliers that are associated with the input-coupled constraints (2d). 2) The update of the Lagrange multipliers is λ(r+1) i,`|k= λ(r) i,`|k+γG1uc(r) 1,`|k+G2uc(r) 2,`|k−g,for all `∈ {k, . . . , k +hp−1}, where γ∈R,0< γ < 1. Notice that all steps of the dual ascent algorithm can be done locally and each sub-system requires the information of the decision of its neighbourhood in order to update the Lagrange multipliers. When exchanging information, consider the information sharing network ˜ G= (S,˜ E), where ˜ E={(1,2)}. During a communication failure, it is assumed that each sub-system uses the information of the neighbourhood from the previous time instant and considers the unknown information to be null, as in [12] and [16]. This is precisely stated in Assumption 1. Assumption 1: Consider that the communication link (i, j)∈˜ Efails. During the period of the failure, the ith sub-system considers the input trajectory of the the jth sub-system (˜ uj,k), denoted by ˜ wj,k = w> j,k · · · w> j,k+hp−1>, as follows: wj,` =(uj,`|k−1, ` =k,...,k+hp−2, 0nu,j , ` =k+hp−1, and vice versa. ♦ Note that based on the structure of ui,k,wj,k = [wl> j,k wc> j,k]>, where wl j,k and wc j,k correspond to the local inputs and the coupled inputs, respectively. In this case, during a communication failure, both sub-system cannot communicate and receive the necessary information, which is the coupled inputs of their neighbour. It implies that the steps of updating the Lagrange multipliers for both sub-systems become λ(r+1) i,`|k=λ(r) i,`|k+γGiuc(r) i,`|k+Gjwc(r) j,` −g,(4) for all `∈ {k, . . . , k +hp−1}and i∈ S, where j∈ Ni. The modification of the dual-ascent algorithm implies that instead of solving Problem (2), the DMPC controllers solve the following optimization problem: minimize {˜ ui,k}i∈S X i∈S Ji(xi,k,˜ ui,k)(5a) subject to (2b), (2c), Giuc i,`|k+Gjwc j,` ≤g,∀j∈ Ni,(5b) for all i∈ S and `∈ {k,...,k+hp−1}. The difference between Problem (5) and Problem (2) is in the existence of coupled constrains (2d) in Problem (2), which are replaced by (5b). Notice that the inequalities (5b) are not coupled constraints since wc j,`, for all j∈ S and `∈ {k,...,k + hp−1}are known information (see Assumption 1). Hence, Problem (5) is separable by definition. An analysis regarding the performance of the controllers can be made by evaluating Problem (5). Problem (5) may be infeasible even though Problem (2) is feasible due to the changes of the constraints. In this case, the dual-ascent algorithm with the updating steps according to (3) and (4) will not obtain a solution. Suppose that Problem (5) is feasible. Since it is convex, the dual-ascent algorithm can find a solution. Consider that each sub-system obtains a solution ˜ u∗ i,k, for all i∈ S. Thus, ˜ u∗ k=h˜ u∗> 1,k ˜ u∗> 2,ki> must be examined, since this is the control input that will be applied to the system. The solution ˜ u∗ kmay be an infeasible solution for Problem (2), i.e., it violates some constraints of Problem (2). The DMPC scheme in [12], which apply Assumption 1 during failures, also assumes that null control input is a feasible solution. However, the latter assumption does not always hold in general. Furthermore, supposing that ˜ u∗ kis feasible, if ˜ u∗ k=h˜ u?> 1,k ˜ u?> 2,ki> , then ˜ u∗ kis the optimal solution. Otherwise, ˜ u∗ kis a suboptimal solution. Thus, this DMPC strategy does not have a guarantee on the feasibility, let alone the stability and the optimality, during communication failures even though the problem is convex with a strictly convex cost function. Similar issues may also be found when the strategy is applied to a more complex and larger problem and in other DMPC strategies. Hence, increasing the resilience of communication infrastructure is important. Section III discusses a proposal to improve the resilience of the information-sharing network. III. INFORMATION-EXCHANGE PROTOCOL BASED ON DISTRIBUTED PROJECTION DYNAMICS The proposal focuses on the methodology of sharing information, which is independent from the control strategy. Thus, it is a general and complementary methodology that can be applied to any DMPC method. A. Description of the Protocol Recall the information-sharing network as the graph ˜ G= (S,˜ E), where ˜ Eshows how the local controllers are connected with each other in the information-sharing network. Furthermore, consider that some nodes (sub-systems) require information denoted by sv= [s1 vs2 v· · · sns,v v]>∈ Rns,v , from the vth node. Depending on the DMPC strategy applied to the system and the couplings in the system, svmay consist of either state or input information, which is required by some or all other nodes to run the DMPC algorithm. Therefore, there exists a sub-graph ˜ Gv= (Sv,˜ Ev)⊆˜ G, where Sv⊆ S is the set that consists of node vand the nodes that require sv, while Ev⊆ E is the set of links that connect the nodes in Sv. For instance, in the DMPC strategies that require neighbour-to-neighbour communication, some neighbours j∈ Nvmight be included in Gvwhile the other neighbours are included in the other information-sharing subgraphs. In order to apply the protocol, the following assumptions must hold. Assumption 2: The undirected sub-graph ˜ Gvis connected. ♦ Assumption 3: The node v, which sends the information, has prior knowledge of |Sv|, while all i∈ Sv\{v}know ns,v.♦ Note that, following Assumption 2, it is possible that there are some nodes in Svthat do not need the information sv, but they are required as intermediate nodes in order to ensure the connectivity of ˜ Gv. The proposed information-exchange protocol is based on the following dynamics: ˙ pi,t =αX j∈˜ Ni (pj,t +rj−pi,t −ri),∀i∈ Sv,(6a) qi,t =pi,t +ri,∀i∈ Sv,(6b) where qi,ri,pi∈Rns,v are the information state, the reference input, and the internal state of the ith node, respectively, ˜ Niis the set of nodes that are the neighbours of the ith node in ˜ Gv, i.e., (i, j)∈˜ Evfor all j∈˜ Ni, and α∈R>0is a constant gain. Furthermore, the reference inputs of all nodes in Svare given by ri=(|Sv|sv, i =v, 0ns,v ,otherwise, (7) and the internal states are initialized as pi,0=0ns,v ,∀i∈ Sv.(8) It is shown in (7) that the information svis used as the reference input of the vth node. In the following subsection, the convergence of the protocol is discussed. Remark 1: The dynamics (6) are in the class of dynamic consensus, which tracks the average of the changing reference inputs. The reader is referred to [26] for further discussions on this topic. ♦ Remark 2: The vectors qi,pi,ri∈Rsvfor all i∈ Svare dedicated only for the transmission of information sv. Thus, each local controller needs to allocate a different data storage for acquiring another information, i.e., if there are more than one source nodes. ♦ B. Convergence of the Protocol Theorem 1 below states the convergence of the proposed information-exchange protocol. Theorem 1: Suppose that Assumptions 2 and 3 hold. Under the dynamics (6) and by providing the references as in (7) and the initial value of the auxiliary state as in (8), the equilibrium point of the information state, i.e., q? i=sv, for each i∈ Sv, is asymptotically stable. Proof: Firstly, notice that the dynamic equations (6a) correspond to distributed projection dynamics (DPD) [17] with the fitness functions fi,t :Rns,v →Rns,v , for all i∈ Sv, which are defined as fi,t =−(pi,t +ri). The protocol dynamics (6a) can be rewritten in the form of the DPD as ˙ pi,t =α|˜ Ni|fi,t −αX j∈˜ Ni fj,t,∀i∈ Sv.(9) Note that fi,t = [f1 i,t f2 i,t · · · fns,v i,t ]>, where fl i,t =−pl i,t − rl i, for each l∈ {1, . . . , ns,v}, is related to the information datum sl v. Then, these dynamics can be rearranged into ˙ ˇ pl t=−αL(˜ Gv)ˇ fl t,∀l∈ {1,2, . . . , ns,v},(10) where ˙ ˇ pl t= [ ˙pl i,t]> i∈Sv,ˇ fl t= [fl i,t]> i∈Sv, for all l∈ {1, . . . , ns,v}, and L(˜ Gv)∈R|Sv|×|Sv|is the Laplacian of the graph ˜ Gv. Hence, it is shown in (10) that the dynamics depend on the structure of the graph ˜ Gv. Secondly, it is necessary to show that the set ∆ = (pt∈R|Sv|ns,v :X i∈Sv pl i,t =ml,∀l∈ {1, . . . , ns,v}), is invariant. This statement can be concluded by the fact that 1> |Sv|L(˜ Gv) = 0, i.e., Pi∈Sv˙pl i,t =−α1> |Sv|L(˜ Gv)ˇ fl t= 0, for all l∈ {1, . . . , ns,v}. Furthermore, by denoting the whole auxiliary states as pt= [p> i,t]> i∈Svand the equilibrium point as p?= [p?> i]> i∈Sv, where p? iis the equilibrium point of the ith sub-system, and, based on Assumption 2, the equilibrium point p?can be characterized from (10), i.e., p?={pt∈ ∆ : ˙ ˇ pl t= 0,∀l∈ {1, . . . , ns,v}} ={pt∈∆ : ˇ fl t∈ span{1|Sv|},∀l∈ {1, . . . , ns,v}},since span{1|Sv|}is the nullspace of L(Gv)when Gvis connected. Now the solution of q? iis derived from p? i. Recall that ∆is invariant. Due to the initialization in (8), Pi∈Svpl i,t = Pi∈Svpl i,0= 0. Therefore, based on this fact and since ˇ fl t∈ span{1Sv}implies fl i(pl? i) = fl j(pl? j)for all i, j ∈ Sv, it is obtained that ˇ fl i(pl? i) = −1 |Sv|Pj∈Sv(pl j,0+rj), which implies pl? i=−ri+1 |Sv|Pj∈Svrj,for all i∈ Svand l∈ {1, . . . ns,v}. Hence, the whole vectors pi,t, for all i∈ Sv, have the following equilibrium point: p? i=−ri+1 |Sv|X j∈Sv rj=−ri+sv,(11) since according to (7) and Assumption 3, Pj∈Svrj= |Sv|sv. Thus, by substituting pi,t into (6b) with the expression in (11), it is obtained that the equilibrium points of the information states are q? i=sv, for all i∈ Sv. Finally, the convergence of the internal state pi,t is shown since it implies the convergence of qi,t to the equilibrium point q? i. To this end, consider the radially unbounded Lyapunov function candidate: V(pt) = Pi∈Sv 1 2p> i,tpi,t −p?> ip? i+r> i(pi,t −p? i), where V(pt)→ ∞ as kptk→∞. The function V(p?)=0 and V(pt)>0for all pt6=p?. The time derivative of V(pt), i.e., ˙ V(pt) = X i∈Sv f> i,t ˙ pi,t =X i∈Sv −αf> i,t  |˜ Ni|fi,t −X j∈˜ Ni fj,t   = ns,v X l=1  −αX i∈Sv fl i,t|˜ Ni|fl i,t −fl i,t X j∈˜ Ni fl j,t   = ns,v X l=1 −αˇ fl> tL(Gv)ˇ fl t. Since ˜ Gvis connected by assumption, L(˜ Gv)0. Hence, ˙ V(pt)≤0, for all pt∈R|Sv|ns,v . Furthermore, notice that equality ˙ V(pt) = 0 only holds when ˇ fl t∈span{1|Sv|}, for all l∈ {1, . . . , ns,v}, i.e., at the equilibrium point p?. Then, applying the LaSalle-invariance principle, convergence to the equilibrium point p?is concluded [27]. Hence, q? i=sv, for all i∈ Sv, are also asymptotically stable. Remark 3: The convergence rate of the protocol depends on the structure of the network. It can be seen from the representation of the protocol in (10), which is similar to the standard consensus algorithm formulation. The convergence rate of such protocol is indicated by the second smallest eigenvalue of the Laplacian of the graph [28]. ♦ Remark 4: Although the information states asymptotically converge to q? i=sv, for all i∈ S, in practice, sufficiently similar information can be recovered in a finite time. ♦ C. Advantages of the Protocol Two main advantages of the DPD-based informationexchange protocol are highlighted as follows. Firstly, it relaxes some assumptions that are required by most of DMPC strategies. Particularly, it relaxes the requirement of the information-sharing network topology. As discussed in Section II-A, different DMPC strategies might have different requirements regarding the information-sharing network topology supposing that the information is exchanged directly as required. However, by employing the proposed protocol, these requirements are relaxed such that ˜ Gdoes not have to fulfil certain topological structure. Instead, only the connectivity of ˜ Gis necessary (Assumption 2). Secondly, this protocol also enhances the resiliency of DMPC-type controllers against communication failures. According to Assumption 2, the information can still be exchanged although some links of the network ˜ Gfail as long as the network is still connected. Therefore, to some extent of link failures, a DMPC strategy that uses the proposed protocol to exchange information can still be performed. The advantages provided by the protocol also come with some costs, which are extra computation and communication, in terms of the amount of data that is exchanged. This is due to the fact that all sub-systems should reach consensus by iteratively exchanging information and applying (6) before obtaining the correct information from their neighbours. Therefore, one must ensure that the total time to exchange information using the DPD-based protocol and to compute the control inputs is smaller than the sampling time of the controlled system. In practice, the satisfaction of this assumption depends on the system complexity, i.e., the instrumentation and the other hardware as well as the software, e.g., the optimization solver. D. Selecting the Information-Sharing Graphs Now consider that the system has an information-sharing network that connects its sub-systems in a certain way. In this subsection, a discussion on how to choose the informationsharing sub-graph, ˜ Gv, from the available informationsharing network is provided. Two criteria of selection are the resiliency of the network against communication failures and the convergence rate of the proposed method. It is a direct implication that, when the information-sharing graph has more links (edges) connecting the sub-systems, the chance that the graph is still connected when a failure occurs is higher. Furthermore, as stated in Remark 3, the second smallest eigenvalue of L(˜ Gv)indicates the convergence rate of the protocol in the sense that a larger eigenvalue implies a faster convergence rate. As noted in [28], the second smallest eigenvalue of a sparse Laplacian is relatively small compared to a dense Laplacian. Hence, these criteria lead to the fact that the network should have as many links as possible. Redundancy is required when dealing with communication failures. Thus, when selecting an information-sharing graph, it is important to consider having redundant links in the information-sharing graph. For instance, a path is not a suitable structure since once a link is disconnected, the graph is disconnected. In that sense, a cyclic graph is more redundant because the proposed method could still be applied when one link of this graph is broken. Furthermore, it is obvious that a complete graph is the most suitable one. On the other hand, the topology of an LSS usually has a sparse Laplacian matrix due to the fact that a sub-system is usually only coupled with other closest sub-systems. This may imply its information-sharing network has sparse Laplacian as well. However, this network can be decomposed into some subgraphs that do not have sparse Laplacian, which implies they may have faster convergence rate. By also considering the redundancy criterion, then one may be able to use a smaller yet redundant information-sharing graph. As an example, consider the information-sharing graph depicted in Fig. 1. Its Laplacian has the second smallest eigenvalue of 0.23. However, now consider its sub-graphs 1 2 4 5 6 8 10 11 12 3 9 7 Fig. 1. A system with 12 nodes. The physical network Gand the information-sharing network ˜ Gare represented by the solid and dashed lines, respectively. 1 2 4 3 4 5 6 11 12 9 6 8 9 78 10 11 9 a. ˜ G1b. ˜ G2 c. ˜ G3d. ˜ G4e. ˜ G5 Fig. 2. Decomposition of ˜ Ginto 5 smaller connected sub-graphs. that are depicted in Fig. 2. Notice that the sub-graphs that are formed are cyclic, in order to satisfy the redundancy requirement. Among these sub-graphs, the smallest value of the Laplacian second smallest eigenvalues is 2.00. This means that the convergence rate of the proposed method is much faster by using the smaller sub-graphs as the information-sharing graphs among the sub-systems. However, the redundancy of the sub-graphs is not as good as the overall graph, ˜ G. For instance, consider sub-graph ˜ G3(Fig. 2c) and suppose that the links (7,9) and (6,7) are broken, then this sub-graph is not connected anymore, which implies the nodes in this sub-graph (6, 7, 8, and 9) cannot exchange information among each other. However, the graph ˜ Gis in fact still connected, allowing the protocol to be applied and all nodes to exchange information when the ˜ Gis used as the information-sharing graph of all information. E. Reconfiguration of Information-Sharing Graphs In this section, a distributed algorithm to reconfigure the information-sharing graphs is proposed. The reconfiguration is a contingency procedure when the information-sharing graphs are disconnected due to the failures, i.e., Assumption 2 does not hold. Moreover, the reconfiguration can also be applied even though the graphs are still connected in order to maintain redundancy. Consider again the information-sharing network ˜ G= (S,˜ E)and its sub-graph ˜ Gv= (Sv,˜ Ev)⊆˜ G that is used to share information of the vth node, denoted by sv, among the sub-systems in Sv⊆ S. Now, denote the set of links that fail by ˜ Ef⊂˜ Ev. Moreover, let the following Assumption 4 holds. Assumption 4: Each node i∈ S has prior knowledge of its neighbours in the information-sharing network ˜ G, i.e., ˜ Ni and ˜ Mi:= {j: (i, j)∈˜ E,∀j /∈ Sv}.♦ Then, for each link (y, z)∈˜ Ef, find a node that is a neighbour of yand zin ˜ Gand does not belong to Sv. By defining Θ := {θ:θ∈˜ My∩˜ Mz,∀(y, z)∈˜ Ef}and ˜ Eθ:= {(θ, y),(θ, z),∀θ∈Θ,∀(y, z)∈˜ Ef}, the updates of the sub-graph ˜ Gvare ˜ Sv←˜ Sv∩Θand ˜ Ev← { ˜ Ev\˜ Ef}∩ ˜ Eθ. Since the sub-graph ˜ Gvis modified, Assumption 3 no longer holds. If the number of links that fail, |˜ Ef|, is known by the source node, v, then it can easily update |˜ Sv|after the reconfiguration since one node is added for each link that fails. If this is not the case, the standard distributed consensus algorithm can be used to recalculate the total number of nodes in |˜ Sv|. To this end, consider an auxiliary variable, denoted by ξi,t, for each node i∈ Sv. Initialize ξi,0= 0 for i6=vand ξv,0= 1. By applying the standard distributed consensus [28] ˙ ξi,t =X j∈˜ Ni α(ξj,t −ξi,t),(12) ξi,t converges to ξ?= 1/|Sv|as t→ ∞, for all i∈ Sv. Therefore, in a finite time, ts, which denotes the settling time of the consensus, the vth node can obtain |Sv|= rnd(1/ξv,ts). Note that the whole reconfiguration procedure can be performed in a distributed fashion, i.e., the algorithm only requires each node to have local information of its neighbours (Assumption 4) and neighbour-to-neighbour communication. The distributed reconfiguration procedure is stated in Algorithm 1. Algorithm 1 Reconfiguration Procedure 1: Each node i∈ Svdetects whether there are link failures. 2: for nodes yand z, for all (y, z)∈˜ Efdo 3: Detect the links that are failed. 4: Send information of the failed links to the neighbors that do not belong to Sv, e.g., node ysends to {j: j∈˜ My}and node zsends to {j:j∈˜ Mz}. 5: end for 6: for θ∈Θdo 7: Receive the same information of one failed link from two different neighbors. 8: Confirm to join the sub-graph ˜ Gv. 9: end for 10: Compute the updated |Sv|using the distributed consensus algorithm. Remark 5: The intersection of ˜ Myand ˜ Mzfor (y, z)∈ ˜ Efmight be empty. In this case, the associated informationsharing graph cannot be reconfigured. ♦ IV. APPLICATION OF THE PROPOSED PROTOCOL TO DMPC IN MICROGRIDS In this section, the optimal power allocation problem of a network of microgrids is discussed and solved by applying a distributed MPC strategy. It is a high-level control problem with the objective to determine the set-points of the distributed generators. Furthermore, it is assumed that there are low-level local controllers that ensure the operation of distributed generators is according to the obtained set points [29]. Some previous works, e.g., [21], [22], and [30], have addressed the advantages of using distributed control strategy for energy management in power networks. Since such systems cover a large geographical area, the communication between local controllers is important to be maintained. Therefore, it is thought that the proposed information-exchange protocol is suitable to be applied in these systems. A. System Description Consider the system as an undirected graph G= (S,E), where S={1, . . . , n}denotes the set of microgrids, and E denotes the physical interconnection among the microgrids, i.e., the link (i, j)∈ E corresponds to the possibility of exchanging energy between the ith and the jth microgrids. Note that Nidenotes the set of the neighbours of the ith microgrid. Each microgrid is considered to have local loads, a dispatchable distributed generator, a storage system, and a controller that must provides set points to the generator. Furthermore, it is possible to transfer energy between two connected microgrids and there exists an external party from which the microgrids can import energy if necessary. Note that the consideration of having one generator at each microgrid is to simplify the problem without loss of generality. The following formulation can easily be extended for the case in which there are multiple distributed generators per microgrid. Each microgrid, i∈ S, has a power balance equation that must be satisfied at each time instant, as follows: pd i,k −pg i,k −pst i,k −pim i,k −X j∈Ni pt ij,k = 0,(13) where pd i,k ∈R≥0denotes the local demand (load) of the ith microgrid, pg i,k ∈R≥0denotes the total generated power of the dispatchable generator, pst i,k ∈Rdenotes the power delivered by or to the storage, pim i,k ∈R≥0denotes the imported power from an external party, and pt ij,k ∈Ris the power that is transferred between the ith microgrid and its neighbour j∈ Ni. The storage systems have dynamical behaviour that is described by a discrete-time state-space model, i.e., xi,k+1 =aixi,k +bipst i,k,∀i∈ S,(14) where xiis the state-of-charge (SOC), aidenotes the efficiency of the storage, 0< ai<1, and bi=−Ts/emax i, where Ts∈R≥0is the sampling time and emax idenotes the maximum energy that can be stored. The operational constraints that are imposed to the storages are the upper and lower bounds of the SOC, as follows: xmin i≤xi,k ≤xmax i,−pch i≤pst i,k ≤pdc i,∀i∈ S,(15) where xmin i, xmax i∈R≥0denote the minimum and the maximum SOC of the storage of the ith microgrid, respectively. Moreover, pch i∈R≥0and pdc i∈R≥0denote the maximum charging and discharging power of the storage. Furthermore, some operational constraints of the power generated by the distributed generators pg i,k ∈R, the power transferred between two neighbouring microgrids, and the power imported from the external party are also established, as follows: pg,min i≤pg i,k ≤pg,max i,∀i∈ S,(16) −pg,down i≤pg i,k −pg i,k−1≤pg,up i,∀i∈ S,(17) −pt,max ij ≤pt ij,k ≤pt,max ij ,∀(i, j)∈ E,(18) pim i,k ≤pim,max,∀i∈ S,(19) where, pg,min i, pg,max i∈R≥0denote the minimum and the maximum power generated by the distributed generator of the ith microgrid, respectively, pg,down i, pg,up i∈R≥0denote the maximum ramping down and ramping up of the power, respectively, while pt,max, pim,max ∈R≥0is the upper bound of the transferred power and imported power from the external party. In addition, there are additional coupled constraints related to pt ij,k, which are pt ij,k +pt ji,k = 0, i 6=j, ∀(i, j)∈ E.(20) Let the vector ui,k = [ul> i,k uc> i,k]>∈Rnu,i with ul i,k = [pst i,k pg i,k pim i,k]>and uc i,k = [pt ij,k]j∈Nibe the decision/control inputs. Denote the trajectory of the control inputs and that of the coupled control inputs by ˜ ui,k and ˜ uc i,k, respectively. Moreover, consider a quadratic cost, i.e., Ji,k(˜ ui,k) = Pk+hp−1 `=ku> i,`|kRiui,`|k, where Ri= diag [cst icg icim ict i1> |Ni|]>0, for all i∈ S. Note that cst i,cg i,cim i, and ct idenote the cost to store, generate, import, and transfer energy, respectively. The centralized optimization problem that is convex and needs to be solved in an MPC scheme can be written as minimize {˜ ui,k}i∈S X i∈S Ji,`(˜ ui,k)(21a) subject to ˜ xi,k+1 =aixi,k +Bi˜ ui,k,∀i∈ S,(21b) Hi˜ ui,k ≤hi,k,∀i∈ S,(21c) ˜ uc i,k +X j∈Ni Gij ˜ uc j,k =0,∀i∈ S,(21d) where ˜ xi,k+1 =hx> i,k+1|kx> i,k+2|k· · · x> i,k+hp|ki> is the trajectory of the state over the whole prediction horizon. The dynamics of the SOC of the storages (14) are rewritten as xi,k+1 =aixi,k +biui,k,in which bi= [bi02+|Ni|]in order to form (21b) with the appropriate concatenated ai∈Rhp×1 and Bi∈Rhp×hpnu,i . The constraints that only include local decisions, which are (13), (15)–(19), over the whole prediction horizon, are compacted in (21c) with the appropriate Hiand hi,k. Moreover, the coupled constraints in (20) for the whole prediction horizon are written as in (21d). Additionally, it is assumed that Problem (21) has a set of feasible solutions for k∈Z≥0. B. DMPC Design The DMPC strategy that is based on dual decomposition is designed for Problem (21). It is presented in Algorithm 2, where λi∈Rhp|Ni|, for all i∈ S, are the Lagrange multipliers associated to the coupled constraints (21d) and ψi=˜ uc i,k +Pj∈NiGij ˜ uc j,k, for all i∈ S. Notice that Algorithm 2 requires the microgrids to exchange information with their neighbours twice at each iteration, as stated in steps 3 and 5. It is assumed that the default protocol of exchanging information is that a microgrid sends and receives information to and from the neighbours through the direct communication links available between them. Furthermore, the proposed information-exchange protocol that is based on DPD may also be applied to this algorithm to replace the default one. When the DPD-based protocol is applied, it is assumed that the information shared at the end of the information-exchange steps is similar enough such that it does not affect the convergence of the algorithm. In addition, rmax, which denotes the maximum number of iterations available in one sampling time, depends on the computational power of the controllers. Algorithm 2 The Dual-Ascent Algorithm 1: All sub-systems, i∈ S, set r= 1 and initialize λ(r) i. 2: while r < rmax do 3: Information exchange: Receive λ(r) jfrom the neighbours, all j∈ Ni, and send λ(r) ito the neighbours. 4: Solve the local optimization problem: minimize ˜ ui,k fi(˜ ui,k) + ˜ y> i˜ uc i,k subject to (21b) and (21c), where ˜ y> i=λ(r)> i+Pj∈Niλ(r)> jGji. 5: Information exchange: Receive the solution ˜ uc j,k from the neighbours, all j∈ Ni, and send ˜ uc i,k to the neighbours. 6: Update λias λ(r+1) i=λ(r) i+γψi,for 0< γ < 1. 7: r←r+ 1. 8: end while C. Simulation Results and Discussion Numerical simulations are carried out in MATLAB on a PC with 16 GB of RAM and 2.6 GHz Intel core i7. The power network consists of 12 microgrids, i.e., S= {1,...,12}. Fig. 1 depicts the topology of the grid, denoted by G= (S,E), and the overall information-sharing network of the controllers, denoted by ˜ G= (S,˜ E). The simulation time of all simulations is one day with the sampling time of 15 minutes. The prediction horizon of the DMPC controller TABLE I PARAMETERS OF THE MICROGRIDS Parameters Value Unit Sub-system (i) xmin i,xmax i20%, 80% - all pch i,pdc i50, 50 kW all pg,min i,pg,max i0, 1000 kW all pg,down i,pg,up i100, 100 kW all pt,max i,pim,max i, 100, 2000 kW all ai0.90 - all cst i,cim i,ct i0.1, 250, 0.1 - all cg i2 - 2, 6, 11 cg i10 - 1, 3, 4, 5, 7, 8, 9, 10, 12 TABLE II THE AVERAGE STAGE COST AT TIME INSTANTS AT WHICH THE FAILURE OCCURS Scenario Protocol, Communication Cost (Proportional) 1 Default, no failures 1.00 2 DPD-based, no failures 1.00 3 Default, with failures 1.16 4 DPD-based, with failures 1.00 is hp= 6 and the parameters corresponding to each microgrid are shown in Table I. Furthermore, it is assumed that each local controller knows the local load and its forecast over the prediction horizon at each time instant. In order to compare the performance of the proposed method, four scenarios, which are described in Table II, are simulated. The communication failures are defined as follows. At k={2,3,10 −13,40 −42,80 −82}, the information-sharing network during the failure scenarios is ˜ G0= (S,˜ E0), where ˜ E0=˜ E\{(2,3),(4,6),(9,11)}(the failed links are indicated by || in Fig. 1). In addition, in Scenarios 2 and 4, the proposed information-exchange protocol uses sub-graphs as shown in Fig. 2 as the informationsharing graphs in order to increase the convergence rates. During failures, all information-sharing sub-graphs only lose one link, hence they are still connected. Scenario 1 is considered as the baseline performance since the controllers produce the global optimal solution. The simulation result of Scenario 2, as seen in Table II, shows that the proposed information-exchange protocol is able to achieve the optimal performance. In Scenario 3, the microgrids that are disconnected cannot exchange information using the default protocol. Therefore, these microgrids adopt Assumption 1, which means that the unknown information of the neighbours is considered to be null. Table II shows that there is a performance degradation (16% of higher cost than the optimal case) when the microgrids are in Scenario 3. On the other hand, all microgrids are able to obtain the required information with the proposed methodology despite the occurrence of the failures, as expected. Therefore, the optimal solutions can be obtained by the system, as can be 10 20 30 40 50 60 70 80 90 0 200 400 10 20 30 40 50 60 70 80 90 0 500 10 20 30 40 50 60 70 80 90 0 50 100 Scenario 3 Scenario 1, 2, 4 Fig. 3. The operation of sub-systems 3 and 2 in Scenario 3 (solid lines) and Scenarios 1, 2, and 4 (dashed lines): a. Power generated by sub-system 3 (pg 3), b. Power generated by sub-system 2 (pg 2), and c. Power transferred from sub-system 2 to sub-system 3 (pt 3,2). seen by comparing the cost of Scenario 4 and that of Scenario 1, which are equal. As illustrations, Figs. 3-5 show the operation of the microgrids that are affected by the communication failures in Scenarios 3 and 4. The communication links between these neighbouring microgrids are broken. In Scenario 4, the 3rd and 4th microgrids import power from the the 2nd and 6th microgrids, respectively, at the time instants when the failure occurs. Furthermore, there is also some energy that is exchanged between the 9th and 11th microgrids during these time instants. These decisions are equal to those that are taken in Scenarios 1 and 2. However, in Scenario 3, the 3rd and 4th microgrids do not import any power from their neighbours (see Figures 3c and 4c). Instead, they produce more power to comply with the load (see Figures 3a and 4a). Moreover, the 9th and 11th microgrids do not always exchange energy and their power generation decisions are slightly different than those in Scenario 4 during these time instants (Figure 5c). V. CONCLUSION AND FUTURE WORK A methodology to cope with the problem of communication failures in distributed MPC strategies has been proposed. It involves an information-exchange protocol that is based on DPD. A numerical study, which shows the application of this protocol to a distributed MPC strategy that is designed to optimize the power production in a microgrid network, demonstrates the advantages of the proposed protocol. As future work, in order to extend the results obtained in Section III-D, a study on how to design an optimal information-sharing network that is able to deal with failures in general while ensuring fast convergence rate of the protocol should be carried out. Moreover, an implementation of time-varying partitioning of the information-sharing net-