IEEE Circuits and Systems Magazine - Q2 2019 - 22

nonzero patterns in their corresponding system matrices A 1, A 2, f, A m and A o1, A o2, f, A om .
Definition 7
A linear temporally switching network G represented by
u , B ) with fixed external inputs is structurally control(A
lable if and only if there exists a state controllable linear
temporally switching system (22) with the same strucu , B ).
ture as (A
Note that the temporally switching network G is
structurally controllable if and only if for each admissible realization of the independent nonzero parameters
on the time intervals [t k -1, t k), k =1, 2, f, m -1, and
[t m -1, t m], the corresponding system (A k, B ) is state controllable for all k =1, 2, f, m.
With a new temporal interpretation of the dilation
and intersection concepts, a graph-theoretic criterion
was derived by Hou et al. [48], via the concept of n-walk,
as follows.
Theorem 13 [48]
A linear temporally switching network G of size N with
fixed r (11 r # N ) external inputs is structurally controllable if and only if there exists an n- walk in the graph
u , B ).
of (A
For discrete-time networked systems, an alternative
characterization can be derived from the algebraic systems theory [52].
Consider the state-space form of a general discretetime linear network,
x (k +1) = Ax (k) + Bu (k),
y (k) = Cx (k),

(23)

with appropriate dimensions.
The concept of state controllability-from-0 (or reachability) for network (23) is defined as follows.

x1

x2

x1+

x1-

x2+

x2-

x3+

x3-

x3
(a)

(b)

Figure 9. determination of maximum matching. the maximum matching of the digraph (a) can be determined from
its bipartite representation (b), which is obtained by splitting
each node x i into two nodes x +i and x -i , and then placing an
edge (x +j , x -i ) in the bipartite graph if there is a directed edge
from x j to x i in the original digraph.
22

IEEE cIrcuIts and systEms magazInE

Definition 8
The discrete-time linear network (23) is said to be state
controllable-from-0 (or reachable) if, for the zero initial state x (0) = 0 and any final state x (t f ) ! R N , there
exist a positive integer T and a finite input sequence
u(0), u(1), f, u(T ) such that x (T ) = x (t f ).
Recall [52] that the transfer function (matrix) of the
network (23), G (z) = C (zI - A)-1 B, always has a rightcoprime factorization G (z) = N r (z) D -r 1(z) and a leftcoprime factorization G (z) = D -l 1(z) N l (z).
A characterization of the reachability for the network
(23) is given as follows [52].
Theorem 14
The discrete-time linear network (23) is reachable if and
only if
i) rank [B, AB, f, A N -1 B] = N.
ii) zI - A and B are left coprime for all z ! C.
iii) rank [zI - A, B] = N for all z ! C.
4. Synthesis of Network Controllability
In order to fully control a complex networked system,
the first important step is to identify the driver nodes
that can ensure the network controllability. Mathematically, it is the problem of how to design an appropriate
input matrix B to achieve this goal. For system (5), there
are many possible selections of B that can satisfy the
controllability conditions. The objective here is first
to find a set of B corresponding to the minimum number N D of driver nodes required to control the whole
network. The second step is to design an appropriate
input u (t) =[u 1 (t), u 2 (t), f, u ND (t)]T through which one
can steer the networked system from any initial state to
any desired state in finite time. For system (5), there are
many possible inputs that can achieve this goal of control. The task, then, is to use an optimal control input to
minimize the required energy cost.
In this section, the issues on the selection of driver
nodes, optimization of network controllability and control energy are discussed.
4.1 Selection of Driver Nodes
4.1.1 Approaches Based on Maximum Matching
The minimum inputs theorem (Theorem 7) provides a
guideline to identify the driver nodes in a directed network using maximum matching. From the structural
controllability theorem (Theorem 2), the cactus is the
most economical topological pattern to propagate control influence, because it is a minimal structure such
that the removal of any edge will render the network
uncontrollable. A maximum matching exhibits the important edges using which one can construct the cactus
sEcOnd QuartEr 2019
IEEE Circuits and Systems Magazine - Q2 2019

Table of Contents for the Digital Edition of IEEE Circuits and Systems Magazine - Q2 2019
