Discrete Networked Dynamic Systems: Analysis and Performance

By Magdi S. Mahmoud and Yuanqing Xia

Discrete Networked Dynamic Systems: Analysis and Performance provides a high-level treatment of a general class of linear discrete-time dynamic systems interconnected over an information network, exchanging relative state measurements or output measurements. It presents a systematic analysis of the material and provides an account to the math development in a unified way.

The topics in this book are structured along four dimensions: Agent, Environment, Interaction, and Organization, while keeping global (system-centered) and local (agent-centered) viewpoints.

The focus is on the wide-sense consensus problem in discrete networked dynamic systems. The authors rely heavily on algebraic graph theory and topology to derive their results. It is known that graphs play an important role in the analysis of interactions between multiagent/distributed systems. Graph-theoretic analysis provides insight into how topological interactions play a role in achieving coordination among agents. Numerous types of graphs exist in the literature, depending on the edge set of G. A simple graph has no self-loop or edges. Complete graphs are simple graphs with an edge connecting any pair of vertices. The vertex set in a bipartite graph can be partitioned into disjoint non-empty vertex sets, whereby there is an edge connecting every vertex in one set to every vertex in the other set. Random graphs have fixed vertex sets, but the edge set exhibits stochastic behavior modeled by probability functions. Much of the studies in coordination control are based on deterministic/fixed graphs, switching graphs, and random graphs.

• This book addresses advanced analytical tools for characterization control, estimation and design of networked dynamic systems over fixed, probabilistic and time-varying graphs
• Provides coherent results on adopting a set-theoretic framework for critically examining problems of the analysis, performance and design of discrete distributed systems over graphs
• Deals with both homogeneous and heterogeneous systems to guarantee the generality of design results

• Language: English
• Publisher: Academic Press
• Release date: Oct 22, 2020
• ISBN: 9780128236994

Magdi S. Mahmoud

Magdi S. Mahmoud is a distinguished professor at King Fahd University of Petroleum and Minerals (KFUPM), Saudi Arabia. He has been faculty member at different universities worldwide including Egypt (CU, AUC), Kuwait (KU), UAE (UAEU), UK (UMIST), USA (Pitt, Case Western), Singapore (Nanyang), and Australia (Adelaide). He lectured in Venezuela (Caracas), Germany (Hanover), UK (Kent), USA (UoSA), Canada (Montreal) and China (BIT, Yanshan). He is the principal author of 51 books, inclusive book-chapters, and author/co-author of more than 610 peer-reviewed papers. He is a fellow of the IEE and a senior member of the IEEE, the CEI (UK). He is currently actively engaged in teaching and research in the development of modern methodologies to distributed control and filtering, networked control systems, fault-tolerant systems, cyberphysical systems, and information technology.

Book preview

2020

Chapter 1: Mathematical background and examples

Abstract

In this chapter, we provide an overview of mathematical analysis followed by a brief overview of algebraic graph theory with emphasis on averaging and estimation algorithms defined over graphs. We also review basic concepts from matrix theory with a special emphasis on the so-called Perron–Frobenius theory. These concepts will be useful when analyzing the convergence of the linear dynamical systems discussed throughout the book. Next, we focus our attention on discrete-time networked dynamic systems (DNDSs), where the underlying connection topology couples the agents at their outputs. A distinction is made between DNDSs with homogeneous agent dynamics and NDSs with heterogeneous agent dynamics.

Additionally, we introduce some representative examples and systems from multiple disciplines to motivate our treatment of a class of linear DNDSs in the subsequent chapters. In particular, we look at the following examples:

(i) In the context of social influence networks, we discuss a classic model on how opinions evolve and possibly reach a consensus opinion in groups of individuals.

(ii) In the context of wireless sensor networks, we discuss a simple distributed averaging algorithm and we present two advanced design problems for parameter estimation and hypothesis testing.

(iii) In the context of compartmental networks, we discuss dynamical flows among compartments with a classic example for water in desert ecosystems.

(iv) Finally, we discuss simple robotic behaviors for cyclic pursuit and balancing. In all cases we are interested in presenting the basic models and motivating interest in understanding their dynamic behaviors, such as the existence and attractivity of equilibria.

Keywords

Mathematical analysis; algebraic graph theory; averaging and estimation algorithms; matrix theory; discrete networked dynamic systems (DNDSs)

1.1 Introduction

Recent years have witnessed an explosive increase in research activities on developing methodologies for cooperative control and motion coordination. This interest is motivated by the growing possibilities enabled by robotic networks and/or multivehicle systems in the monitoring of natural phenomena and the enhancement of human capabilities in hazardous and unknown environments.

Admittedly, we assert that networks are everywhere. We watch TV through the television network; we interact with each other in a closely connected social network; our body itself is a highly complicated biological network. Mathematically, a network can be thought of as a collection of nodes that represent some physical quantities and edges that interconnect different nodes (see Fig. 1.1). On a parallel avenue, we have witnessed the emergence of a discipline of study focused on modeling, analyzing, and designing dynamic phenomena over networks. We refer to such systems as networked dynamic systems; they are also equivalently referred to as multiagent or distributed systems. This emerging discipline, rooted in graph theory, control theory, and matrix analysis, is increasingly relevant because of its broad set of application domains. Discrete networked dynamic systems (DNDSs) appear naturally in

(i)  social networks and mathematical sociology,

(ii)  electric, mechanical, and physical networks, and

(iii)  animal behavior, population dynamics, and ecosystems.

Network systems are designed in the context of networked control systems, robotic networks, power grids, parallel and scientific computation, and transmission and traffic networks, to name a few (see [1]).

Figure 1.1 A network structure.

This book has been written to be an accurate introduction to the emerging topic of DNDSs. The chief goal is establishing a unified and self-contained theoretical framework that is suitable to the analysis and performance for several related dynamical models that feature time variance, randomness, and heterogeneity with emphasis on the methodological and general aspects of the subject. We will also treat applications to inferential problems in sensor networks, rendezvous of mobile robots, and opinion dynamics in social networks.

The focal point addressed throughout this book is that complex dynamical evolutions originate from the interactions of a large number of simple units. Not only such collective behaviors are evident in biological and social systems, but the digital revolution and the miniaturization in electronics have also made possible the creation of man-made complex architectures of interconnected devices, including computers, sensors, and cameras.

Most of the time, we concentrate on linear discrete-time dynamics, which we identify as the core theoretical issue. We present the fundamental set-theoretic results of dynamic systems over graphs and gather together a unified viewpoint of various models and results scattered in the literature.

To this end, we provide in the sequel some relevant mathematical information.

1.2 Mathematical background

In this chapter, we provide some mathematical notations, present basic notions, collect useful algebraic inequalities and lemmas, and give an introduction to some relevant topics which are quite useful for the book.

At first, we assume that the reader already has basic training in linear algebra, and for a more complete introduction, some familiarity with the numerical software MATLAB® is also encouraged.

to denote the set of all nonnegative integers. For any positive real number rdenotes the largest integer that is less than or equal to rmatrix Astands for its induced matrix norm. For any function, including controls or inputs. In the case when ϕ denotes the truncation of ϕ at k.

to denote the set of controls taking values in Ω.

In this book, we deal mostly with finite-dimensional linear spaces, which are also often called linear vector spaces. Seeking generality, we consider the linear space to be n. For instance, the eigenvalues or eigenvectors of a real matrix could be complex.

. Then the n-dimensional vectors x, y of elements x, y is called the real (or complex) vector space (or real [complex] linear space) by defining two algebraic operations, vector additions and scalar multiplication, in .

is of the form

is called a linear subspace and αx whenever x and y for any scalar αis said to be a spanning set . That is, we have

is said to be a basis of the spanning set X as the kth unit vector. The geometric ideas of linear vector spaces have led to the concepts of "spanning a space and a basis for a space."

1.2.1 Basic notions

We begin with some definitions.

Definition 1.1

The n, is a linear vector space equipped with the inner product

and with the trace inner product in a matrix space

and the superscript ⁎ means the complex conjugate transpose.

be a linear space over the field F (typically F ). Then a function

if and only if

(nonnegativity);

(positive definiteness);

);

(triangle inequality).

.

Definition 1.2

A linear space or a vector space

A set (of vectors) V is also a vector in V. Furthermore, the addition is commutative and associative, it has an identity 0, and each element has an inverse, "−v.

is a linear space over the field of real numbers ℜ. To be consistent, we always use a column to represent a vector:

(1.1)

, their linear combination is a component-wise summation weighted by α and β:

(1.2)

is the conjugate transpose of A.

We will now provide a brief review of basic notions and frequently used notation associated with a linear vector space V ).

Definition 1.3

Subspace

A subset W of a linear space is called a subspace if the zero vector 0 is in W .

Definition 1.4

Spanned subspace

, the subspace spanned by S . This subspace is usually denoted by span(S).

.

Definition 1.5

Linear independence

is linearly independent if

implies

not all zero such that

Definition 1.6

Basis

of a linear space V is said to be a basis if B is a linearly independent set and B spans the entire space V.

1.2.2 Signal norms

In the sequel, we use norms are:

(positivity);

(positive definiteness);

∀ scalars α (homogeneity);

(triangle inequality)

.

Some key signal norms are:

•  Energy of the signal , 2-norm,

•  Maximum value over time, ∞-norm,

It is also called sup-norm , defined by

•  Average power-norm,

1.2.3 Vector norms

, and let the vector p-norm be

,

;

;

.

Of significant interest is the Euclidean norm defined by

, equipped with this norm, is called a Euclidean space. Two important results for the Euclidean norm are the