Open access peer-reviewed chapter - ONLINE FIRST

A Dynamic Graph-Based Systems Framework for Modeling, and Control of Cyber-Physical Systems Typified by Buildings

By Fadel M. Lashhab

Submitted: March 2nd 2021Reviewed: May 31st 2021Published: October 19th 2021

DOI: 10.5772/intechopen.98657

Downloaded: 38

Abstract

In this chapter, we present a framework for modeling certain classes of cyber-physical systems using graph-theoretic thinking. The cyber-physical systems we consider are typified by buildings. We show that the thermal processes associated with a building can be represented as a graph in which (1) the node variables (temperature and heat flows) are governed by a dynamic system and (2) interconnections between these nodes (walls, doors, windows) are also described by a dynamic system. In general, we call a collection of such nodes and interconnections a dynamic graph (dynamic consensus network).Driven to explore this by developing thermal examples, this study outlines a practical framework for dynamic consensus networks and dynamic graphs. In a manner that seamlessly extends these concepts from the static cases, we will explore the combination of dynamic degrees, adjacency, Laplacian matrices, and incident matrices. With these conceptual tools, one can quickly identify equivalent concepts of dynamic consensus networks.

Keywords

  • Dynamic graphs
  • dynamic consensus networks
  • dynamic Laplacian matrix
  • dynamic graph theory

1. Introduction

In this chapter, we present the analysis and design of cyber-physical systems using graph-theoretic ideas. We are motivated by the energy-efficient control of buildings.

Our fundamental view of a building is of overlapping, interacting networks, as shown in Figure 1. This diagram depicts the dominant phenomenon that contributes to building as a network (or graphs). These networks consist of nodes that constitute distinct sub-systems. For example, in heat-sensing or networks of humans, the nodes may refer to specific rooms in a house or office building. In contrast, nodes might represent a particular sensor, actuator, or perhaps a computational unit in a control network. The links between nodes denote communication of fluctuating or sharing variables in a system, such as the passage of people in a human network between rooms through hallways, or the heat flow between rooms in the thermal network through walls and doors. Smaller circles in Figure 1 indicate links between networks. Note that typical graph-based networks assume links that are in some way constant, but as we will see, in some networks, such as the building thermal network, links between nodes may be dynamic.

Figure 1.

A building as a collection of interacting networks.

Control of distributed systems, such as shown in Figure 1 is a currently active area of research within the field of control systems. By a distributed system, we mean one with many inputs and outputs, possibly spatially distributed dynamics, and a decentralized decision and control architecture, with restrictions on communication between computational nodes. Many researchers have focused basically on homogeneous systems. However, a building may be viewed as a hybrid system where a physical process (the structure itself) has been augmented with a hardware infrastructure (sensors and actuators) and a cyber-infrastructure (communication and decision nodes). Such overlaid heterogeneous systems with constrained connectivity and interaction between the different layers present challenges and system optimization and control opportunities. What is needed are ways to reason about discrete, multi-attribute heterogeneous entities (such as cyber-systems) and continuous, heterogeneous processes (such as physical phenomena) operating on a hierarchy of layered graphs related to each other through a set of mappings or transformations.

In this chapter, we consider methods for studying distributed systems that are heterogeneous and possibly spatially varying. Though a building can be seen as a set of interconnected networks, we consider only the thermal network. We begin by showing how a building’s thermal processes can be modeled as a graph whose node variables are temperature and heat flows and whose interconnections are walls, doors, windows, etc. In our graphical representation of a building, both the nodes and the interconnections can be (heterogeneous) dynamic systems. We call this a dynamic graph(or network). For such systems, we show that the relationships between the node variables reduce to the traditional graph Laplacian in the steady-state, so that consensus variable convergence can be obtained by discussing the steady-state properties of the system. We then show how a behavioral systems approach can develop kernel relationships between all system variables in dynamic graphs typified by building thermal models. Using these kernel relationships, we consider the controllability analysis of such systems.

The consensus protocols in networking in engineering have received significant academic and corporate attention because of their vast array of potential applications in various fields. Robotics, transportation, sensor networking, communication networking, biology, and physics are only some potential fields that networking consensus could benefit. This section aims to analyze a generalization of consensus problems whereby the weights of network edges are no longer static gains. Instead, they are dynamic systems, which lead towards dynamic consensus networks.

Network topology is static for the consensus networks, meaning that there are no dynamics in the interconnections between the nodes λij=constant0, and the nodes are assumed to be integrators [1]. Thus,such problems can be written in the time domain for each node i=1,2,,nnas

ẋi=jNiλijxjtxit.E1

The consensus protocol (Eq. (1)) can be written in matrix form as:

ẋt=Lxt,E2

where xt=x1tx2txntTand L, and the Laplacian matrix of the graph L=lij, is defined by

lij=jNiλiji=jλijijandijE0otherwiseE3

For the multi-agent consensus problem, suppose that Nagents develop their personal beliefs xiR1regarding a so-called global consensus variable xby communicating with their next-door neighbors by the referred consensus protocol (Eq. (1)). A key outcome is that the solution of the problem ẋt=Lxtgives xixif only all edges are connected to the static graph [1]. This specific fact has been the basis of much of the literature related to consensus problems.

There have been many engineering scientists in the past years involved in the controllability of dynamic consensus networks. The focus was on controlling dynamic consensus networks under the leader-follower approach, where some nodes are considered leaders and other nodes are followers. This approach aims to transfer followers’ trajectories from an initial position to the desired position (set-point) by adequately selecting the leaders’ trajectory. Many authors [2, 3, 4, 5] have considered this framework by using some algebraic methods and the eigenvalues and eigenvectors of the dynamic Laplacian matrix. Other researchers also investigated the controllability using graphic tools such as the graph’s equitable partition [4] and symmetry properties [3]. These graphical tools are built based on the graph’s configuration and topology associated with the consensus network. The controllability investigation using the minimum energy for static consensus networks using the first-order system formulated and proposed in [6, 7]. This Chapter will investigate the controllability for dynamic consensus networks with edges (links) of rational dynamical systems.

Several researchers have already studied controllability analysis for consensus networks with static topology. The vast majority of these published academic studies have investigated the impact of the static topology on the controllability of their respective consensus networks. Those studies have [8] introduced a graph-theoretic characterization of static networks’ structural controllability with only a single leader. In their research, many illustrate that a static network with variable topology is structurally controllable if the union graph of the underlying static topologies is connected. For example, in [9], the controllability of the network was investigated using the size of the graph as well as its connectivity. Meanwhile, controllability for leader-based, multi-agent systems has been analyzed by [7, 10] based on connectivity and the null space of the leader and followers’ incidence matrices. Controllability using graph symmetry and equitable partition properties has been addressed in [11, 12]. The paper [13] formulated an equivalent data-driven Hautus-type test for a general input/output system that assumes no knowledge of the system’s state. The authors’ work proposed in this Chapter also provided an algorithm for data-driven verification of controllability of the system. They used the singular value decomposition of the Hankel matrix. A multi-vehicle system’s consensus problem was proposed and analyzed by [14, 15] with a time- varying reference state. Under the condition, only a portion of the vehicles can access the reference state in this problem. Those vehicles might not have the ability to share the information with the other cars in the team. Although their paper focused on developing an algorithm for investigating the consensus conditions for a directed fixed information exchange topology, so it is helpful to extend this algorithm to directed switching information-exchange typologies. In our article, the topology (edges) that describes the interconnections between nodes is considered time-varying rational transfer functions. Investigating the consensus conditions and the controllability for a multi-vehicle system might be one of the motivating applications of this work.

The consensus protocol, such as outlined in (Eq. (1)) and its variants, have been studied extensively in previously published academic studies. The findings from these studies have been applied in many domains, such as for formation motion control during time agents are mobile. However, the common intellectual idea of the consensus paradigm can be restrictive for researchers and engineers alike in several ways. For example, notice that we have interpreted the consensus problem as having integrating nodes and static weights. In the next section, will we extend this idea to networks with weights, which were transfer functions or nodes are more than just integrators. We will explore this dilemma by modeling heat transfer in buildings [16, 17, 18, 19]. By the notation “dynamic systems,” we mean that linear ordinary differential equations (LODEs) are described as relationships between the system variables. We call such networks dynamic consensus networksbecause all the node variables converge to a common value called a consensus value under some conditions.

The Chapter is organized as follows: In Section 2, we present a general framework for a dynamic consensus network. We present a detailed study of modeling thermal processes in buildings as directed, dynamic graphs, beginning with a simple two-room model and transitioning to multiple interconnected rooms. Section 3 outlines a theoretical framework dedicated to these dynamic graphs and dynamic consensus networks. This framework will introduce the notion of a degree of dynamics, adjacency, incident, and Laplacian matrices in a way that naturally extends these concepts from a static case. By modeling this, one can easily define equivalent concepts of dynamic interconnection matrices and dynamic consensus networks.

Advertisement

2. Modeling a thermal process in a building as a directed dynamic graph

This Section first presents examples showing how a dynamic graph can arise in applications and then give a general framework for a dynamic consensus network. We present a detailed study of modeling thermal processes in buildings as directed, dynamic graphs, beginning with a simple two-room model and transitioning to a model with multiple interconnected rooms. Motivated by this example, we then propose a mathematical framework in service of dynamic graphs and dynamic consensus networks.

Historically, there has always been a recognized need to model the energy processes within buildings. Typical examples of this modeling application are sizing HVAC equipment, determining energy usage performance, and optimizing energy management in a building through persistent control. Current state- of-the-art methods include modeling packages, such as Energy Plus [20], that allows users to specify a building’s geometry, equipment, orientation, materials, and usage patterns, simulated using first principles models and simulated weather data. Though undoubtedly useful for design, these computationally complex systems may suffer from certain limitations once a building has been constructed due to significant deviations in construction, occupant use, and other specifications that cause the actual building’s behavior to be quite different the model.

At the opposite extreme, so-called black box models have been developed from observational data. Though we can utilize these models to predict future values of particular variables, they do not incorporate any structural information about the system when gathering data, resulting in the need for large amounts of data to train and suffering from the difficulty of extracting relevant information about internal physical parameters that may be of interest.

Semi-physical models resulting in an intermediate level of modeling are known as gray-box modeling. Simple modeling elements containing parameters identified using observational data are chosen and connected based upon physical insight to represent the system’s actual configuration. This is commonly the modeling technique used for thermal networks, which have been used to study load-shifting and peak-reducing control in buildings [21, 22]. A typical thermal network model for a single room is shown in Figure 2, which was adapted from [22]. These networks of (analogous) thermal resistors and capacitors model different building elements. To date, this has typically been performed at a very coarse level, sometimes by combining multiple rooms into one practical room per zone. In [22], a gray-box model for an experimental building was created by utilizing measurements of weather, room temperature, and room air supply and flow. This model was used to predict the effects of a demand-limiting control strategy that we later validated experimentally.

Figure 2.

Thermal model of a room.

This section uses a single-room model as shown in Figure 2 from [22] as the basis for a node and its interconnections to other nodes to build up a dynamic graph representation of a building’s thermal processes. First, we consider two rooms connected by a wall. We then illustrate how several such nodes may be interconnected, using the example of a hypothetical four-room building, with analysis provided of the resulting model that motivates the generalization in the next section.

Before proceeding, we note that the initial interest in modeling thermal processes in a building comes from viewing a building as a group of overlapping, interacting networks. In thermal networks, these nodes may denote rooms in an office or school, while in the control network, they may represent a sensor, actuator, or a unit of computation. The connections in the middle of nodes will represent varibles that share information, such as the flow of air-conditioned air between rooms through walls, windows, and doors in a thermal network. While some typical graph-based networks consist of links that are in some way constant gains; some networks, such as a building’s thermal network, may have dynamic links between nodes, as we will explore in the next section.

2.1 Two rooms connected by a wall

Figure 3 depicts what is called a 3R2C model in the literature [23]. We identify a room ias a node with node variable Ti, the lumped room temperature, Qiin, the input heat flow (a manipulated variable, not shown), and qij, the heat flow out of the room through walls or doors or windows (of course with this convention, if qij<0then this is heat flow into the room). The parameter Ciris the thermal capacity (mass) of the room i.

Figure 3.

Two rooms connected by a wall using the 3R2C model.

The interconnection between the two rooms is a wall represented analogously by an electrical circuit with three resistors and two capacitors, simplifying the model in Figure 3. The capacitors C2 and C4 can be thought of as the heat storage capacity of the wall’s materials, which could be different on each side of the wall. A complete model adds a capacitor to represent the insulation properties in addition to that of the wall’s board materials. For the resistors, R3 represents the heat dissipation inside the wall, while R1 and R5 represent the heat dissipation from each room to the inside of the wall.

As shown in [23], the heat flows in Figure 3 can be written as:

qijqji=1BijsAijsDijsDijsAjisTiTjE4

where

Aijs=1+a1ijs+a2ijs2Ajis=1+a1jis+a2jis2Bijs=b0ij+b1ijs+b2ijs2Dijs=1+d1ijs+d2ijs2

and

a1ij=C4R5+C2R3+C2R5a2ij=C4C2R5R3a1ji=C4R1+C4R3+C2R1a2ji=C4C2R3R1b0ij=R5+R3+R1b1ij=C4R5R1+C2R3R1+C2R5R1+C4R5R3b2ij=C4C2R5R3R1d1ij=d2ij=0

Here, s is the independent variable of the Laplace transform, which can be interpreted as sddt. As noted in [23], we can interpret Gxs=Aijs/Bijsas the external conduction of the wall, Gys=Dijs/Bijsas the cross-conduction of the wall, and Gzs=Ajis/Bijsas the internal conduction of the wall.

From (3), the nodal equation can be written as:

CirdTidt=QiinqijE5

Combining (Eqs. (4) and (5)) gives:

Cirs00CjrsTiTj=Q1inQ2in1BijsAijsDijsDijsAjisTiTjE6

To motivate later analysis, notice that in the absence of any external heat inputs (i.e., Qiin=0), we can rewrite the previous equation as:

sCirTissCirTjs=1BijsAijsDijsDijsAijsTiTj,E7

which defines the relationship between the temperatures in two rooms using the 3R2C model.

It is useful to separate (Eq. (7)) as

Tis=1CirsAijsBijsTisDijsBijsTjs=1sλijSsTisλijCsTjs,E8

where λijSs=AijsBijsis a self-correction weight and λijCs=DijsBijsis a cross-correction weight. Note that we assume Cirin (Eq. (8)) is equal to the unity for simplicity. Comparing this to static-weights consensus networks, we see that this appears similar to the equation of a two-node consensus network, in which the nodes are integrators. The difference is that there is a separate weighting on the terms Ti (s)and Tj (s),and these weights are dynamic.

2.2 Several interconnected rooms

This subsection uses the previous subsection’s expressions to develop a building model with several interconnected rooms with different possible pathways between each room and the outside environment.Ideas are developed for a specific theoretical four-room building shown in Figure 4 with each room having neighboring rooms with which heat can travel through-and-from. One such neighbor is always the external environment (which does not include the rooms), whose variable is denoted Tawith ‘a’ referring to the ambient outdoor temperature variable. Walls, doors, and windows are all pathways that thermal energy can potentially flow in such a network. Therefore, the corresponding graph for this example is shown in Figure 5. There are several heat flows that are not shown, including q14=q14door, q41=q41door, q24=q24wall+q24doorand q42=q42wall+q42door.

Figure 4.

A hypothetical four-room example.

Figure 5.

Heat flow network corresponding to the four-room example.

In developing a model for this system, we modify (Eq. (5)) to sum the energy losses through all pathways connected to a node, resulting in:

CirdTidt=QiinjNikjPjqijkjE9

where Niis the set of neighbors to which a node iis connected and Pjis the set of pathways kjassociated with any neighbor jof node i. We note that qij=kjPjqijkj.

For building thermal analysis, there may be several different types of interconnection elements, though they will all have the basic format of (Eq. (4)). Because there is negligible energy storage in doorways and windows, when these are the sole interconnection elements between rooms, we use a single R model, so that (Eq. (4)) is expressed with b0ij=Rwith all other variables being set to zero. To make the notation a bit more uniform, for the common case when a door or window is in parallel with a wall, the interconnection transfer function matrix is the sum of the single R model and the 3R2C model. That is, the model would be given by Aij,Aji, Bij,and Dijthat satisfies:

AijsBijsDijsBijsDijsBijsAjisBijs=AijsBijs1Bijs1BijsAijsBijs+1R1R1R1R,E10

where the primed variables represent the 3R2C model, and the unprimed variables represent the resulting parallel connection. In the expressions below, we assume that this computation has been done and the resulting unprimed coefficients can be easily calculated and are thus omitted here. Note that in the case of a door or window that is parallel to a wall, the coefficients d1ijand d2ijassociated with the unprimed variables are non-zero.

Table 1 summarizes the neighbors for each node and the pathways between each node and each of its neighbors for this example. The table also identifies the coefficients used in the transfer matrix describing the interconnection between each pair of neighbors where the various polynomials Aij, Bij, Dij(when there is no parallel door or wall) or Aij, Bij, Dij(before being combined in parallel with any doors or windows) are defined as above in (Eq. (4)).

NodeNeighborsPathsCoefficients
121-wallA12, B12
a2-wallA1a, B1a
1-windowRw1a
31-wallA13, B13
41-doorRd14 = B14
211-wallD12, B12
a2-wallA2a, B2a
1-windowRw2a = B2a
42-wallA24, B24
1-doorRd24 = B24
311-wallD13, B13
a2-wallA3a, B3a
1-windowRw3a = B3a
42-wallA34, B34
1-doorRd34 = B34
411-doorRd41 = B41
a1-wallA4a, B4a
22-wallD24, B24
1-doorRd42 = B42
32-wallD34, B34
1-doorRd43 = B43

Table 1.

Hypothetical four room example.

Combining (Eqs. (4) and (9)) for the configuration shown in Figure 5 with the parameters shown in Table 1 and defining the vectors

Ts=T1sT2sT3sT4sT,Qins=Q1insQ2insQ3insQ4insT,

we can easily show that:

sTs=QinsLsTs,E11

where the matrix Ls=Lijsis given as:

Lijs=jNiλijSsi=jλijCsijandijE0otherwise,E12

or L(s) is given as (Eq. (13)). We will refer to L(s) defined in this way as

Ls=1R14d+j=2,3A1jB1j1B121B131R14d1B211R24d+j=1,4A2jB2j01B241R24d1B3101R34d+j=1,4A3jB3j1B341R34d1R41d1B421R42d1B431R43d1R41d+1R42d+1R43d+j=2,3A4jB4jE13

a dynamic Laplacian matrix.For the graph topology shown in Figure 5, the dynamic Laplacian matrix has the form shown in (Eq. (13)). In the previous work [16], We have shown that when the weight matrices λijssatisfy certain assumptions, −L(s)can be viewed as a dynamic interconnection matrix,allowing the demonstration of consensus.

Notice that we can redraw Figure 5 as shown in Figure 6, where

Figure 6.

A hypothetical four-room example as a dynamic consensus network.

λijs=λijSsλijCsE14
=AijBijw+1Rijd1Bijw1Rijd,E15

The graph shown in Figure 6 will be referred to as a dynamic graphor a dynamic consensus network.Then applying the definition of the dynamic.

Laplacian (12) for the dynamic graph Figure 6 we get

Ls=j=2,3,4λ1jSsλ12Csλ13Csλ14Csλ21Csj=1,4λ2jSs0λ24Csλ31Cs0j=1,4λ3jSsλ34Csλ41Csλ24Csλ43Csj=1,2,3λ4jSs,E16

which reduces to (Eq. (13)) if we insert the full expressions for λijCsand λijSsdefined in (Eq. (14)). This leads us to consider the idea of dynamic consensus networks.

Figure 7 shows a simple simulation of (Eq. (9)) for the case when Qiin=0and the scalar Ta = 80 for a nominal set of parameters available from the authors upon request (omitted here in the interest of space). As intuitively expected, all temperatures converge to the ambient temperature, as the external environment has infinite capacity and there is no energy input or removal. This can also be seen by examining (Eq. (9)) at steady-state with Qin=0. Further noting that L(0) has the form of a classic graph Laplacian matrix, with row sum equal to zero (and in this case column sum equal zero as well), we can argue that Tss=Tais a unique solution.

Figure 7.

Example simulation.

We also [24] consider another example that motivated a generalization of the static consensus problem (Eq. (1)), modeling the load frequency control (LFC) network of an electrical power grid as a dynamic consensus network. We consider the following network:

Yis=1sjNiGisaijYisYis,E17

i=1,,N, which can be viewed as a single-integrator consensus network with dynamic interconnection coefficients Gi(s)aij. In the grid’s LFC network, each system’s output is the phase of its voltage, which is the integration of the angular velocity. The interconnection is power exchanges among the individual systems through transmission lines dependent on phase differences.

Based on the dynamics of a network’s nodes and their topology, several consensus problems can be specified. This Chapter focuses on two types of dynamic consensus networks: directed and undirected. The dynamic consensus networks studied are:

  • Dynamic Network 1:Directed dynamic networks with integrator nodes and dynamic edges:

ẋit=jNiλijStxitλijCtxjt,E18

or,

xis=1sjNiλijSsxisλijCsxjsE19

  • Dynamic Network 2:Undirected dynamic networks with integrator nodes and strictly-positive-real (SPR) transfer function edges:

ẋit=jNiλijtxitxjt,E20

or,

xis=1sjNiλijsxisxijsE21

  • Dynamic Network 3:Undirected dynamic networks with identical nodes and dynamic edges:

xit=ptjNiλijtxitxjt,E22

or,

xis=psjNiλijsxisxjsE23

  • Dynamic Network 4:Undirected dynamic networks with heterogeneous nodes and dynamic edges:

xit=pitjNiλijtxitxjt,E24
xis=pisjNiλijsxisxjsE25

Assumptions:For the dynamic networks (Eqs. (19)(25)), we make the following assumptions:

  1. The node and edge processing in the proposed dynamic networks (Eqs. (19)(25)) are linear, time-invariant LTI.

  2. The dynamic topology consists of dynamic edges λijsmodeled as transfer functions. For the second proposed dynamic network (Eq. (21)), we assume the edges’ dynamics are strictly positive real (SPR) transfer functions.

  3. The topology of a network can be directed or undirected. The first dynamic network (Eq. (19)) uses a directed topology, whereas the second dynamic network (Eq. (21)) uses an undirected topology.

  4. Depending on the application, the flow is modeled differently. For instance, λijSsxisλijCsxjsand λijsxisxijsare two different ways of modeling flow, as is indicated by the previous Section. The difference between these two cases is illustrated in (Eqs. (19) and (21)). These flow models are rooted in the types of dynamic networks to be modeled per the motivation for each network. The first dynamic network (Eq. (19)) is based upon modeling buildings’ thermal processes as directed dynamic graphs. In contrast, the second dynamic network (Eq. (21)) is based upon the motivation of modeling micro-grids of power systems as undirected dynamic graphs.

  5. The nodes’ dynamics can be integrators (Eqs. (19) and (21)) or more general dynamics Eqs. (23) and (25).

  6. The nodes’ dynamics and the edges can be identical Eqs. (23) or heterogeneous Eqs. (25).

  7. These models are often autonomous, meaning no input flows into the dynamic consensus networks. However, we add inputs and disturbances to the proposed dynamic consensus networks’ general forms in some problems.

Advertisement

3. Dynamic graphs definitions

Consider the example in Figure 8. These graphical depictions are outlined as a set of nodes (or vertices) N=niconnected by a set of edges Es=ninj:ninjN). We modeled each respective edge as a transfer function λijs. In this example, each edge λijsRs, where Rsdenotes the set of all complex-valued functions analytic in the open right-half complex plane (real rational functions). It is important to note that this model assumes that zero self-loops are connected to any node in question. Meanwhile, if an edge between nodes exists niand nj,we describe such nodes as adjacent (or neighbors). We denote the neighbors of each node nias Ni=j:ninjEs. As previous academic work has described, the path between two respective nodes consists of a sequence of edges from which it is possible to travel along the arc sequence from one of the nodes to the other. If there is at least one node with at least one path to every other node, the graph is connected.

Figure 8.

Directed-dynamic graph.

Later, we also view a node as implementing a transfer function that produces the node variable (Pi(s)for i=1,2,,N, where Nis the number of nodes in the dynamic graph).

As in the static case, we ordered the edges eij(s) by the edge originating from node Pi(s), known as the tail node, and terminating at node Pj(s), which we referred as the head node, which a compass can identify. If the dynamics of the nodes are different, we will call such dynamic networks heterogeneous networks. If the nodes have the same dynamics, the network is homogeneous. However, a particular case does arise when integrator nodes with dynamic edges are present.

Each node Pi(s) in a directed dynamic network, such as Figure 8, is associated with a dynamic degree vi(s) representing the total sum of the dynamic edge weights that are connected to the node i(entering or leaving the node). More specifically, each node has a dynamic in-degree viinsand a dynamic out-degree vioutsrepresenting the sum of the dynamic edge weights of the incoming and outgoing edges, respectively. Clearly vis=viins+viouts. From these dynamic degree definitions, we can define three different dynamic degree matrices:

  1. The dynamic in-degree matrix Dins=diagviins.

  2. The dynamic out-degree matrix Douts=diagviouts.

  3. The dynamic degree matrix Ds=diagvis.

Notice that Ds=Dins+Douts. To illustrate, for the example shown in Figure 8, these matrices are given by (26):

Dins=λ21s+λ31s+λ41s0000λ12s+λ42s0000λ13s+λ43s0000λ14s+λ24s+λ34s;
Dοuts=λ12s+λ13s+λ14s0000λ21s+λ24s0000λ31s+λ34s0000λ41s+λ42s+λ43s;
Ds=Din11+Dout110000Din22+Dout220000Din33+Dout330000Din44+Dout44.E26

If a dynamic edge eijsexists between two nodes iand j, these nodes are considered to be adjacent and are known as neighbors, and are denoted for a node Pisby Ni=j:ninjEs. As before, neighbors can be distinguished based upon whether they are associated with incoming or outgoing arcs. Thus, we can define three dynamic adjacency matrices:

1. The incoming dynamic adjacency matrix Ains=aijins, is defined by

aijins=jNieijs;coming intonifromnjifij0otherwise.

2. The dynamic outgoing adjacency matrix Aouts=aijouts, is defined by

aijouts=jNieijs;going out fromniintonjifij0otherwise.

3. The dynamic adjacency matrix As=aijs, is defined by

aijs=totaljNieijs;betweenniandnjifij0otherwise.

Notice that As=Ains+Aouts. To illustrate, for the example shown in Figure 8, these matrices are given by:

Ains=0λ21sλ31sλ41sλ12s00λ42sλ13s00λ43sλ14sλ24sλ34s0;Aouts=0λ12sλ13sλ14sλ21s00λ24sλ31s00λ34sλ41sλ42sλ43s0;As=0λ12s+λ21sλ13s+λ31sλ14s+λ41sλ21s+λ12s00λ24s+λ42sλ31s+λ13s00λ34s+λ43sλ41s+λ14sλ42s+λ24sλ43s+λ34s0.E27

Another type of matrix is the dynamic incident matrix. For that matrix, we outline two incident matrices: one that indicates the direction of the edges connected to a node, where for node Pi(s) the edge eij(s) is given a value based upon being disconnected, incoming, or outgoing and denoted as BSinwhere “S” refers to static. Meanwhile, another can matrix capture the transfer functions of the edges and is with this denoted as BDinswhere “D” refers to the dynamic. Thus, the dynamic and static incoming incident matrices are defined as BDins=bijDins, BSin=bijSin, where,

bijDins=+λijsifarcjenters nodeni0otherwise.bijSin=+1ifarcjenters nodeni0otherwise.

To illustrate, for the example shown in Figure 8 these matrices are:

BDins=0λ21s0λ31s0λ41s0000λ12s000000λ42s0000λ13s000000λ43s0000λ14s0λ24s0λ34s0BSin=0+10+10+10000+1000000+10000+1000000+10000+10+10+10E28

Similarly, we can define a dynamic and static outgoing incident matrices for a dynamic graph by, BDouts=bijDouts, BSout=bijsout, where,

bijDouts=λijsifarcjleaves nodeni0otherwise.bijSout=1ifarcjleaves nodeni0otherwise.

To illustrate, for the example shown in Figure 8, these matrices are

BDouts=λ12s0λ13s0λ14s000000λ21s0000λ24s000000λ31s0000λ34s000000λ41s0λ42s0λ43sBSout=1010100000010000100000010000100000010101E29

Also, we can define the dynamic and static incident matrices for a directed dynamic graph as BDs=bijDs, BS=bijSwhere

bijDs=λijsifarcjleaves nodesni+λijsifarcjenters nodeni0otherwise.bijS=1ifarcjleaves nodeni+1ifarcjenters nodeni0otherwise.

Notice that BDs=BDins+BDoutsand BS=BSin+BSout. To illustrate, for the example shown in Figure 8, the dynamic and static incident matrices are:

BDs=λ12sλ21sλ13sλ31sλ14sλ41s0000λ12sλ21s0000λ24sλ42s0000λ13sλ31s0000λ34sλ43s0000λ14sλ41sλ24sλ42sλ34sλ43sBS=1111110000110000110000110000110000111111E30

We can now give the definition of dynamic Laplacian matrix equivalent with the derived dynamic degree, adjacency, and incident matrices. This matrix mentioned above has spectral properties that indicate many conditions of a graph. An undirected dynamic graph has a corresponding dynamic Laplacian matrix defined by Ls=DsAs. More specifically, the dynamic Laplacian matrix we propose here can be defined as Ls=lijs, where

lijs=jNiλijsi=jλijsijandijE0otherwise.E31
Douts=λ12s+λ12s+λ14s0000λ21s+λ24s0000λ31s+λ34s0000λ41s+λ42s+λ43s,Aouts=0λ12sλ13sλ14sλ21s00λ24sλ31s00λ34sλ41sλ42sλ43s0,Louts=λ12s+λ13+λ14sλ12sλ13sλ14sλ21sλ21s+λ24s0λ24sλ31s0λ31s+λ34sλ34sλ41sλ42sλ43sλ41s+λ42s+λ43sE32

Here, we also outline the aforementioned matrix of an undirected dynamic graph as

Ls=BDsBT=DsAs,E33

where Dsm×mis the dynamic degree matrix formed by the dynamic degree of the medges, BRn×mis the static incident matrix that captures the orientations of the edges, and Asn×mis the dynamic adjacency matrix.

We define the dynamic Laplacian matrix through the implementation of the the dynamic degree and dynamic adjacency matrices which distinguish between incoming and outgoing conventions. Examples include: Lins=DinsAinsand Louts=DoutsAouts. With these definitions, Ls=Lins+Louts. Particular caution must be taken in noting that while L=BBTin the static case, LsBsBsT, LinsBinsBinsTand LoutsBoutsBoutsT. To overcome this, in the sequel, we will use Lout(s), where the outgoing, dynamic Laplacian matrix can be defined using the incident matrices as follow:

Louts=DoutsAouts,E34

where Dout(s) and Aout(s) are the dynamic-outgoing degree and adjacency matrices, respectively. These matrices can be defined in a static case using the incident matrices as Dout=BoutBoutTand Aout=BoutBinT. Thus, the outgoing, dynamic degree and adjacency matrices can be defined as:

Douts=BDoutsBSoutT,
Aouts=BDoutsBSinT.E35

By combining (Eqs. (34) and (35)), the outgoing, dynamic Laplacian matrix Lout(s) can be defined as

Louts=BDoutsBSoutT+BDoutsBSinT=BDoutsBSoutT+BSinT=BDoutsBST.E36

A similar definition can be given for Lin(s).

To illustrate, regarding the example noted in Figure 8, the associated dynamic degree, adjacency, and Laplacian matrices are given by (Eq. (32)). Notice that λijsdepicted in (Eq. (32)) are transfer functions that describe the interconnections (edges) between the nodes (Figure 9).

Figure 9.

Block diagram of the dynamic graph.

Now, the dynamic of each node can be represented in time domain for i=1,2,,N=4by

ẋit=Aixit+BiuiintjNiλijddtxitxjtyit=Cixit,E37

where, xit, uiint, and yitare the state, input, and output of the node i, respectively, λijsS=ddt. is the transfer function of the edge between the nodes iand j, and Niis the neighboring set to the node i.

The overall system of the dynamic graph 8 can be written in frequency domain as

Ps1Ys=LoutsYs+uins,E38

where, Ps=diagP1sP2sPNs; Pis=CisInAi1Bi, uins, Y(s)are the Laplace transform of the input and output variables, and Lout(s)is the outgoing-dynamic Laplacian matrix of the dynamic graph.

The block diagram for the overall system (38) can be depicted as shown in 9.

The dynamic graphs presented here are governed by dynamic consensus protocols as discussed in the previous sections.

Advertisement

4. Conclusion

This Chapter studied a generalization of consensus network problems whereby the network edges’ weights are no longer modeled as static gains. Instead, they are represented as dynamic systems coupling the nodes. We call such networks dynamic consensus networks because, under some conditions, all node variables converge to a common value called a consensus. We presented examples of how dynamic graphs can arise in applications. Detailed studies of modeling thermal processes in buildings as directed dynamic graphs were presented. Motivated by these examples, a framework was proposed for dynamic graphs and dynamic consensus networks. This framework introduced the idea of dynamic degree, adjacency, incident, and Laplacian matrices in a way that naturally extends these concepts from the static case. The dynamic consensus networks addressed herein considered various dynamics of nodes and interconnection topology, including (1) directed dynamic networks with integrator nodes and real-rational transfer function edges; (2) undirected dynamic networks with integrator nodes and strictly-positive-real transfer function edges; and (3) undirected dynamic networks with identical linear time-invariant nodes and dynamic edges. We used the established aspects and properties of the defined dynamic graph theory in conjunction with the behavioral approach to developing a controllability-analysis methodology for dynamic networks.

Advertisement

Acknowledgments

The authors would like to thank Professor Kevin L. Moore and Professor Tyrone L. Vincent at the Colorado School of Mines for their help and advice.

DOWNLOAD FOR FREE

chapter PDF

© 2021 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Fadel M. Lashhab (October 19th 2021). A Dynamic Graph-Based Systems Framework for Modeling, and Control of Cyber-Physical Systems Typified by Buildings [Online First], IntechOpen, DOI: 10.5772/intechopen.98657. Available from:

chapter statistics

38total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us