Sinuhé Martinez-Martinez

Hossein Hashemi Nejad

Taha Boukhobza

Dominique Sauter

Communication sequence selection to preserve reachability/observability in networked control systems with communication constraints: a graphic approach

Keywords: Networked Control Systems, Medium Access Constraint, Reachability, Observability, Graph Theory, Maximal Matching

Communication sequence selection to preserve reachability/observability in networked control systems with communication constraints: a graphic approach Sinuhe Martinez-Martinez * Hossein Hashemi-Nejad * Taha Boukhobza * Dominique Sauter *

INTRODUCTION

In classical control theory a perfect information exchange is assumed. But the progress in communication, control and real time computation has enabled the development of large scale systems which sensors and actuators exchange information with feedback controller through a shared network. Control systems having this configuration have been termed Networked Control Systems (NCSs). Introduction of networks in control loop adds some limitation in data exchange and it brings new problems and challenges such as networked induced delay, packet dropout and constraints in access to the medium. As consequence, the classical control theories must be revised to be adapted in NCSs.

For instance stabilization problem of NCS which is studied in [??]. The networked induced delays which may degrade the performance of closed loop system were investigated in [??]. Important surveys about recent results in NCSs are given in [???].

Access constraints are one of the major obstacles in control system design. It occurs when capacity of communication medium for providing simultaneous medium access channels for its user is limited. As a consequence only limited number of sensors or actuators is allowed to communicate with controller at each time instant. Moreover, if a Fault detection and isolation (FDI) module exists, its connexion to the network has not access to measurement of all sensors simultaneously. Recently there was a number research activity in this field. As an example, an LQG design method for NCS which are subject to medium access constraints was presented in [?]. Problem of FD with communication constraints in linear systems [??] and in non-linear systems [?] were considered. The reachability and observability of an NCS with limited communication was studied in [?].

Observability and/or reachability are properties which depend strongly on the structure of the system, see for example [??]. A study on observability for LTI structured systems is carried out in [?] and in [?] in the context of NCS systems. A complete survey on structural methods can be found in [?]. From the structural view point, the problem of the existence of sequences which preserve the observability/reachability of a NCS with limited communication is treated in [?] where an algorithm for building the command and communication sequence that ensure the reachability and observability of a NCS with medium access constraints was taken into account.The structural approach is a powerful tool for the systems analysis which main advantage is the low complexity of its algorithms when combined with the graphical approach (see [?]).

This paper presents a graphical strategy to find all communication sequence for given networked access constraint on input and output channels that preserve reachability and observability of the system. Comparing with previous works that studied design of communication sequence, this method is simpler and complex mathematical computation is not necessary. Also, it enables us a) to verify existence of a communication sequence that preserve reachability and/or observability of system for given channel limit ω ρ and ω σ respectively . b) Considering channel limitation, Find all communication sequences which guarantee system's reachability/observability.

The rest of this paper is structured as follows. In section 2, constraints of communication and communication sequences in model of system are taken into account and an extended linear time varying (LTV) system is presented. Graphical representation of linear systems is studied in section 3 then in section 4, a graphical method for finding all communication sequence that preserve observability and reachability of extended system with respect to communication constraints is proposed.

PROBLEM STATEMENT

Suppose that the model of plant connected to the network with communication constraints in figure 1 is described by following discrete-time LTI system:

x(k + 1) = Ax(k) + Bu(k) y(k) = Cx(k) (1)
Where A,B and C are matrices of appropriate dimensions, x(k) ∈ R n u(k) ∈ R m and y(k) ∈ R p are the state, input and the output of the system.

Fig. 1. NCS with communication constraints

In the figure 1 output (or input) channel is illustrated.

It is referred to communication link that enables data transmission from sensors to controller (or controller to actuators). To focus on the effects of communication constraints, the following statements are assumed:

• the communication channels are noiseless,

• there are not packet dropouts,

• inherent delay of transmission is not considered.

Due to communication constraints in output and input channels, the shared communication medium can simultaneously provide ω σ outputs with 1 ≤ ω σ ≤ p and ω ρ inputs with 1 ≤ ω ρ ≤ m. In other words, at each sampling instant k, only ω σ of the p sensors and ω ρ of the m actuators are allowed to access to the network. Two independent communication media are considered for sensors and actuators.

For all i = 1, . . . , p, a binary-valued function σ i (k) is defined as the medium access status for sensor i at sample time k. Then if the i-th sensor has access to the network at instant k, σ i (k) = 1, otherwise σ i (k) = 0.

The instantaneous medium access status of p sensors at sample time k can be represented by a p-to-ω σ communication sequence [?].

σ(k) = [σ 1 (k), . . . , σ p (k)] T (2)
Given a communication sequence σ, we define M σ (k) as its matrix form by

M σ (k) diag(σ i (k)) (3)
Let ȳ(k) denote the available outputs in FDI side at sample time k,

ȳ(k) = Mσ (k)Cx(k), Mσ (k) ∈ R ωσ×p (4)
Where Mσ is obtained by deleting the zero rows of M σ . In a similar way, whenever an actuator j loses its access to the communication medium, the control signal generated at the controller for the actuator will be unavailable.

The instantaneous medium access status of m actuators at sample time k is hence represented by a m-to-ω ρ communication sequence

ρ(k) = [ρ 1 (k), . . . , ρ m (k)]
T

(5) and then in its matrix form M ρ (k) as in (3). Let ū(k) the available input actually used by the system whereas u(k) be the signal generated by the controller. We can state similar to the sensor case ū

(k) = B Mρ (k)u(k), Mρ (k) ∈ R ωρ×p (6)
Where Mρ is obtained by deleting the zero rows of M ρ

Therefore "from the controller/FDI point of view " NCS will behaves as a time-varying system with input ū and output ȳ. The system is represented as follows

x(k + 1) = Ax(k) + B(k)u(k) B(k) = B Mρ (k) ȳ(k) = C(k)x(k), C(k) = Mσ (k)C (7)
Equation ( 7) incorporates the dynamic of the plant together with access of communication medium and we call it extended plant.

Dynamic of the extended plant (7) depends on communication policies σ(k) and ρ(k). Important properties of system (1), e.g. reachability and observability, may be lost when communication constraint are imposed. In this communication definition of the reachability and observability of the extended plant ( 7) is given as follows Definition 1. The extended plant ( 7) is reachable on [k 0 , k f ] if given any x f , there exists an input ū(k) that steers 7 from

x(k 0 ) = 0 to x(k f ) = x f . Definition 2. The extended plant (7) is observable on [k 0 , k f ] if any initial condition at k 0 can be uniquely determined from the output ȳ(k) for k ∈ [k 0 , k f ]
For verifying acceptability of a communication sequence, we can look for sequences which preserve reachability and/or observability of underlying system (7). As it is well known reachability/observability of the system may be lost depending on the sequence selection (some examples are given in [?]. The choice of a sequence is not obvious and requires a specific knowledge of the system. As we will show later, the sequence depends strongly on the structure of the system.

Existence of sequences has already treated in precedent works, we concentrate in finding periodic communication sequences that ensure observability of the NCS. In the general case, a discrete-time communication sequence η(•)

is called T -periodic if η(k) = η(k + T ) for all k.
If a communication sequence exists for a given value of communication constraint ω η , it is possible that such communication sequence not be unique. In such case two questions arise:

• How can we find all communication sequences with period T such that each of them preserves the observability/reachability of the extended plant (7)? • What is the minimal size of ω η which guarantees the preservation of the observability/reachability of the extended plant (7)?

Before giving answer to these questions, we introduce the graphic approach which will be useful to find the communication sequences.

GRAPHIC REPRESENTATION OF LINEAR SYSTEMS

In this part we will consider the graphical representation of a linear system and then its generalization to the extended system.

Directed graph associated to a linear system

In this part we will present how it is possible to associate a directed graph to a linear discrete system. Consider the following linear discrete-time system:

Σ Λ x(k + 1) = Ax(k) + Bu(k) y(k) = Cx(k) (8)
We will refere to this system as structured because we concentrate only in its structure. That is to say, we consider matrices A, B and C having elements either fixed to zero or free (non-zero) parameters noted λ i . These parameters form a vector Λ = (λ 1 , . . . , λ h ) T ∈ R h . We say that a property is true generically if it is true for almost all parameters values Λ ∈ R h . For "almost all" is to be understood as for all parameters values except those in some proper algebraic variety in the parameter space.

A digraph can be used to represent structured linear system (Σ Λ ). The digraph associated to (Σ Λ ) is noted G(Σ Λ ) and is constituted by a vertex set V and an edge set E i.e. G(Σ Λ ) = (V, E). The vertices are associated to the state, the inputs, and measured outputs (Σ Λ ) and the edges represent links between these variables. More precisely,

V = X ∪ U ∪ Y. Hence, V consists of n + m + p vertices.
The edge set is

E = A λ -edges∪B λ -edges∪C λ -edges, where A λ -edges = {(x j , x i ) | A(i, j) = 0}, B λ -edges = {(u j , x i ) | B(i, j) = 0}, C λ -edges = {(y j , x i ) | C(i, j) = 0}. Here M λ (i, j) is the (i, j)th element of matrix M λ and (v 1 , v 2 ) denotes a directed edge from vertex v 1 ∈ V to vertex v 2 ∈ V.
In order to understand the ideas developed in next section, we introduce some important definitions in the context of graph approach for structured systems.

Considering the associate graph G(Σ Λ ) = (V, E). For an edge e = (v i , v f ) ∈ E, v i (respectively v f ) is the begin (respectively the end) vertex of e. We denote path P containing vertices v r0 , v r1 , . . . , v r i by For the sake of clarity we present an example of the graphic representation of an structured system and we show some of the concepts developed in this section.

P = v r0 → v r1 → . . . → v r i . The pair (v r j , v r j+1 ) ∈ E for j = 0, 1 . . . , i -1 if there is an integer l and vertices v 0 , v 1 , . . . , v l ∈ V such that (v i-1 , v i ) ∈ E for i = 1, 2, . . . , l. Then, path P is of length l. When v 0 = v i , P
Example 1. Consider an structured linear system given by the following matrices:

A =    0 0 0 0 0 0 λ1 0 0 0 0 0 0 λ2 0 0 0 0 0 λ3 0 0 0 λ4 0    , B =    λ5 0 0 λ6 0 0 0 0 0 λ7    , and
C = λ8 λ9 0 0 0 0 λ10 λ11 0 0 0 0 λ12 0 0 (9)
The directed graph associated to the structured system ( 9) is presented in figure (2) Fig. 2. Directed graph associated to the structured system (9)

One can notice that the graphic representation is rather intuitive. The vertices are associated to the states, inputs and outputs and the edges represent links between them. For example, the two simple paths starting from vertices u 2 and x 4 and arriving to vertex x 5 represent the equation

ẋ5 (t) = λ 4 x 4 (t) + λ 7 u 2 (t).
Let us recall that the main interest in this work is to find (all) T -periodic communications which preserve the reachability and observability of the extended plant. For this aim, the method must allow us to explore all the possibilities of choice for the inputs and outputs i.e. at every sampling time k, M ρ and M σ select every input and output. In other words, we deal with the nominal system (8).

First of all let us concentrate in the observability issue. Exploring all the possibilities for M σ means that availability of each output must be verified at each step k. Assuming control input is known (the input is not taken into account with no loss of generality). For example, the equation y 1 (k) = λ 8 x 1 (k) + λ 9 x 2 (k). The evolution of this output for k + 1 is given by y 1 (k + 1) = λ 8 x 1 (k + 1) + λ 9 x 2 (k + 1). Exploiting equation ( 9) we verify that

y 1 (k + 1) = λ 1 λ 9 x 2 (k), y 1 (k + 2) = λ 2 1 λ 9 x 2 (k), . . . . . . y 1 (k + q + 1) = λ q 1 λ 9 x 2 (k),
since x 1 (k + 1) = 0. Graphically, these relations represent a Y-topped path of length q + 1. As in x 2 there is a cycle, q can increase indefinitely which is not the case with x 1 that form a Y-topped path of length 1. It follows that at every sampling time we search all the Y-topped path families with length equals to q + 1. Indeed, if we consider that it is possible to store last information in controller side, it is worth noting that actually what is of real interest is the beginning and final vertex of such paths at each step k. The same behaviour may be recognized on the inputs side in which case we would be interested in the Urooted path families. This brings us to the idea of create a bipartite graph which relates the beginning vertices to the corresponding ending vertices at every sampling time either for the inputs or the outputs. This idea help us to capture graphically the dynamic of the instantaneous medium access.

Dynamic bipartite graph association to a directed graph

In this section we introduce the bipartite graph which will be useful in the determination of the access sequences.

In order to capture graphically the dynamic of the instantaneous medium access for each step k, a particular graph will be associated to the structured system Σ Λ called dynamic bipartite graph. The dynamic bipartite graph associated to the structured system Σ Λ is noted B η k (Σ Λ ) = (X , Z; W k ). Super index η states either for the dynamic bipartite graph associated to the outputs, B σ k , or to the inputs, B ρ k . The vertex set X is associated to the states and the vertex set Z is associated either to the outputs or to the inputs depending on the case deal with. The edge set is define as follows:

W η k = {W η 1,1 , . . . , W η i,k }| W σ i,k = (x j , y i,k
), if there exist a path in G(Σ Λ ) of lenght k between x j and y i or W ρ i,k = (u i,k , x j ), if there exist a path in G(Σ Λ ) between u i and x j }

The index k must be fixed before constructing the dynamic bipartite graph as well as whether one is interested on the analysis of the dynamic of the input or output medium access. Regarding the observability issue we can generate the following edge subsets for the digraph of the figure 2 for k = 5. The edges were grouped into different subset for the sake of clarity.

{W σ

1,1 ; . . . ; W σ 3,1 } = {(x 1 , y 1,1 ); (x 2 , y 1,1 ); (x 2 , y 2,1 ); (x 3 , y 2,1 ); (x 3 , y 3,1 )} {W σ 1,2 ; . . . ; W σ 3,2 } = {(x 2 , y 1,2 ); (x 2 , y 2,2 ), (x 4 , y 2,2 ); (x 4 , y 3,2 )} {W σ 1,3 ; . . . ; W σ 3,3 } = {(x 2 , y 1,3 ); (x 2 , y 2,3 ), (x 5 , y 2,3 ); (x 5 , y 3,3 )} {W σ 1,4 ; . . . ; W σ 3,4 } = {(x 2 , y 1,4 ); (x 2 , y 2,4 ), (x 4 , y 2,4 ); (x 4 , y 3,4 )} {W σ 1,5 ; . . . ; W σ 3,5 } = {(x 2 , y 1,5 ); (x 2 , y 2,5 ), (x 5 , y 2,5 ); (x 5 , y 3,5 )}

For this kind of bipartite graphs attention must be paid to those edges having the same vertices and belonging to the same edge subset W η i,k . The dynamic bipartite graph generated with the edges subsets calculated above is depicted in figure 3 for k = 5. In the case of reachability analysis we obtain the following edge sets for k = 4

{W ρ 1,1 ; W ρ 2,1 } = {(u 1,1 , x 1 ); (u 2,1 , x 2 ), (u 2,1 , x 5 )}; W ρ 2,2 = {(u 2,2 , x 2 ), (u 2,2 , x 4 )}; W ρ 2,3 = {(u 2,3 , x 2 ), (u 2,3 , x 5 ), (u 2,3 x 3 )}; W ρ 2,4 = {(u 2,4 , x 2 ), (u 2,4 , x 4 )}.
and its associated dynamic graph B ρ 4 depicted in figure 4 For these bipartite graphs some definitions must be introduced in order to understand the ideas developed in following sections.

• A matching is an edge set M ⊆ W η k such that the edges in M are disjoint.

• A ω η -matching is a matching taking at most ω η disjoint edges in each edge subset W η i,j for i = 1, . . . , p (m) and j fixed.

• The cardinality of a matching M is the number of edges in it,

s j =         z 1 . . . z i    j | z i ∈ W η i,j ⊆ M      for j = 1, . . . , k.
Notice that only one sequence can be generated by a maximal ω η -matching. Thus, in figure 3 (B σ 5 ) for example, edges (x 2 , y 1,1 ) ∈ W σ i,1

and (x 2 , y 1,2 ) ∈ W σ i,2 are not disjoint. On the contrary edges (x 1 , y 1,1 ) ∈ W σ i,1 and (x 2 , y 2,1 ) ∈ W σ i,1 are disjoint. Moreover, it can be verified that no maximal 1-matching (one communication channel at a time) can be formed. On the other hand, a maximal 2-matching, (ω σ = 2), may be constituted of the following edges {(x 1 , y 1,1 ), (x 3 , y 2,1 )} ∈ W σ i,1

{(x 2 , y 1,2 ), (x 4 , y 3,2 )} ∈ W σ i,2 {(x 5 , y 3,3 )} ∈ W σ i,3
with its associated vertex sequence

S = y 1 y 2 0 , y 1 0 y 3 , 0 0 y 3 (10)
On the other hand, in figure 4 (B ρ 4 ) for example, edges (u 2,2 , x 2 ) ∈ W ρ 2,2 and (u 2,3 , x 2 ) ∈ W ρ 2,3 are not disjoint. On the contrary edges (u 2,1 , x 2 ) ∈ W ρ 2,1 and (x 2 , y 2,1 ) ∈ W ρ i,1 are disjoint. Moreover, a maximal 1-matching, (only one communication channel at a time, ω ρ = 1), may be constituted of the following edges

{(u 1,1 , x 1 ), (u 2,1 , x 5 ), (u 2,2 , x 2 ), (u 2,3 , x 3 ), (u 2,4 , x 4 )}
The vertex sequence generated by this maximal 1matching is

S = u 1 0 , 0 u 2 , 0 u 2 , 0 u 2 , 0 u 2
In addition, there exists a close relation between maximal ω η -matching in a dynamic bipartite graph and the maximal number of disjoint paths in a directed graph as it is enounced in the next Lemma (this relation is also proved for a maximal matching in a normal bipartite graph, see

[?]). We study here the case of output vertices only. It is worth noting that for the case of input vertices the formulation is similar. Lemma 2. Let the system Σ Λ be the linear structured system defined by ( 8) with its associated directed graph G(Σ Λ ) and dynamic bipartite graph B σ k (Σ Λ ). Following statements are equivalents:

• there exists a family of disjoint Y-topped paths and a cycle family covering all the state vertex set in the associated directed graph G(Σ Λ ), • there exists a maximal ω σ -matching of size n with ω σ = p in B σ k (Σ Λ ) for some k = 0. Proof. Suppose that there exists a complete matching M on B k for some k. Then the cardinality of the matching M is equal to the number of vertices it covers, n. For each x j ∈ X (1 ≤ j ≤ n), there is a unique sequence of disjoint edges (x j1 , y i1,1 ), (x j2 , y i1,2 ), . . . (x jp , y i1,l ), . . . , (x jq , y i1,k ) contained in the matching which form a disjoint path Conversely, suppose that there exists a family of disjoint Y-topped paths covering all the state vertices on G. Then, by the definitions given above concerning the disjoint edges and the construction of the edge set W on B σ k , it is possible to construct a sequences of disjoint edges which form a complete matching on B σ k for some k = 0.

P = x jp → • • • → x j1 → y i1 ,

SEQUENCES WHICH PRESERVE REACHABILITY/OBSERVABILITY

In this section we give a graphical method to search the communication sequences allowing the extended plant to preserve observability and reachability along a period of time T . For the sake of simplicity we concentrate first into the observability issue. We recall the graphic conditions to guarantee observability in a structured system defined in (8) without communication constraints. After this, we state the condition to preserve the observability in the case of a communication constraint. Subsequently, based on the observability issue, we state the condition to preserve the reachability with communication constraints. Finally we explain how the communication sequences may be chosen for both cases.

Observability preservation

In a graph-theoretic approach, conditions for the observability of system (1) without communication constraints, can be deduced from [??] and stated as follows: Theorem 3. Let Σ Λ be the linear structured system defined by ( 8) with associated graph G(Σ Λ ) . The system (in fact the pair (A, C)) is structurally observable if and only if: a. the system Σ Λ is output connected, b. there exists a family of disjoint Y-topped paths and a family of cycles covering all the state vertex set in the associated directed graph G(Σ Λ )

As mentioned in section 2 we consider that system (1) is observable and so it is output connected. In the sequel we assume the output connectability of system Σ Λ without loss of generality. Consequently we concentrate in condition (b) of Theorem 3 which can be expressed in terms of a maximal matching in the associated bipartite graph B σ k of system Σ Λ according to Lemma 2.

In addition, is straigthforward to show [see ?] that the extended plant ( 7) is observable on [0, k f ] if the matrix

O(0, k f ) =     M σ (0)C M σ (1)CA . . . M σ (k f -1)CA k f     satisfies rank (O(0, k f )) = n (11)
Consequently conditions of Theorem 3 are equivalent to equation ( 11). It is clear that even with communication constraints this condition must be satisfied if the interest is to preserve the observability. In the next proposition we extend the graphic conditions given in theorem 3 to the case when the communication constraint is taken into account. Proposition 4. Let Σ Λ be the linear structured system defined by ( 8) with associated dynamic bipartite graph

B σ k (Σ Λ ). The system is structurally observable in [k 0 , k f ] if an only if in B σ k (Σ Λ
) there exists a maximal and complete ω σ -matching of size n.

Proposition 4 can be easily proved considering results of lemma 2 and those found in [?] reformulated in section 2. It is worth noting that in the dynamic bipartite graph, a maximal and complete ω σ -matching of size n could not be unique. As a consequence different sequences S j may be generated for every maximal and complete ω σ -matching found.

Reachability preservation

As it is well known, the reachability property of a system is the dual of the observability property. Let us studying the reachability of the extended plant 7. Suppose that x(0) = 0 and that the extended plant 7 evolves from k = 0 to k = k f . Then

x(k f ) = R(0, k f ) • [ ū(0) ū(1) . . . ū(k f -1) ] T , where R(0, k f ) = [A k f -1 BM ρ (0) A k f -2 BM ρ (1) . . . BM ρ (k f -1) ] T The extended plant (7) is reachable on [0, k f ] if rank(R(0, k f )) = n (
12) Conditions have been derived for the controllability on the context of the structured linear systems [?]. It turns out that such conditions can be applied in our case since they involve the same condition (12). Thus, conditions to the reachability for linear time discrete systems with communication constraints can be deduced directly from those found in [?] or [?].

Theorem 5. Let Σ Λ be the linear structured system defined by ( 8) with associated graph G(Σ Λ ) . The system (in fact the pair (A, B)) is structurally reachable if and only if: a. the system Σ Λ is input connected, b. there exists a family of disjoint U-rooted paths and a family of cycles covering all the state vertex set in the associated directed graph G(Σ Λ )

As the system is considered originally reachable, input connection is assumed. Remains the second condition which is similar to the observability case but considering inputs instead. Thus, the next proposition is easily deduced from Theorem 5 and Lemma 2, using exactly the same arguments than those for the observability issue. The proposition is presented without its proof. Proposition 6. Let Σ Λ be the linear structured system defined by ( 8) with associated dynamic bipartite graph B ρ k (Σ Λ ). The system is structurally reachable in [k 0 , k f ] if an only if in B ρ k (Σ Λ ) there exists a maximal and complete ω ρ -matching of size n.

Then, according to proposition 4 and 6 every combination of disjoint edges which form a maximal ω η -matching of size n, preserves the reachability/observability of the system. Now, before select a communication sequence we have to fix the constraint of the communication medium ω η . We can propose the following algorithm: Algorithm 1. Let G(Σ Λ ) the directed graph associated to the structured system (8):

1. From the directed graph G(Σ Λ ) determine the size k of the maximal U-rooted (Y-topped) path , 2. Build the dynamic bipartite graph B η k (Σ Λ ) for k (k might be infinity, in such case fix k = n), 3. Set the constraint ω η of the communication medium, 4. If there exists in B η k (Σ Λ ) a maximal ω η -matching M of size n 4.1. then the output communication sequence η(k) is given by the associated vertex sequence S formed with the maximal ω η -matching M 4.2. Else the system can not preserve the reachability (observability) with the given communication constraint. If it is possible put ω η = ω η + 1 and return to step 3.

In order to illustrate the selection of the communication sequences we give the next example.

Example 7. Let the dynamic bipartite graph of figure 3 be associated to the structured system 8 for k = 5. Suppose the communication constraint imposed for this system is ω σ = 1 only one channel access at a time. It is clear by figure 3 that a maximal 1-matching of size 5 cannot be found. Indeed, it cannot be possible to cover all the state vertices using only one output at a time. The reason is because of the vertices x 1 and x 3 are at the same distance, k = 1 from different outputs, y 1 and y 3 respectively. It means that these two vertex should be measured at same time and in the first sampled time in order to be observed. Thus, the minimal communication constraint accepted for this system to be observable is ω σ = 2. Now, it is possible to find a maximal 2-matching of (at least) size 5 as we have seen in subsection 3.2 which

Fig. 3 .

 3 Fig. 3. B σ 5 dynamic bipartite graph w.r.t. output associated to the structured system (9)

Fig. 4 .

 4 Fig. 4. B ρ 4 dynamic bipartite graph w.r.t. input associated to the structured system (9) • In case |X | = |Z| a ω η -matching that covers all the vertices is a complete ω η -matching. • A ω η -matching M is maximal if it has a maximum cardinality. • A vertex sequence is a vertex subset S ⊆ Z such that S = [s 1 , . . . , s j ] where

  and a cycle family P c = x jq → • • • → x jp+1 → x jq in the associated directed graph G. Thus a complete matching on B σ k determines a family of disjoint Y-topped paths P j = x jp → • • • → x j1 → y i1 and cycle families P c,j = x jq → • • • → x jp+1 → x jq for j = 1, . . . , n and i = 1, . . . , p on G

  is a cycle. Some paths are called disjoint if they have no common vertex. A path P is a U-rooted (Y-topped) path if its begin (end) vertex is an element of U (Y). A U-rooted (Y-topped) path family consist of disjoint simple U-rooted (Y-topped) paths. If such a family contains a path or a cycle which covers a vertex v it is said to cover such vertex. A system Σ Λ is output connected (input connected) if in its associated graph G(Σ Λ ) for every state vertex x i there exists a direct path to the output (from the input) set Y (U).

associated vertex sequence is given by equation 10. Such sequence represents obviously a 3-periodic communication sequence given by {σ 1 (0), σ 1 (1), σ 1 (2), . . .} = 1 1 0

Where symbol "×" indicates that respective output, y 2 or y 3 , may be used as long as output y 3 is always present. Indeed, output y 2 or y 3 can be added or not without loss of the rank in the observability matrix.

It is also possible to choose another maximal 2-matching

which gives the following associated vertex sequence:

as in the first case y 2 or y 3 on the third column may be used or not without loss of the observability. More communication sequences can be found.

On the controller side, it is possible to find a communication sequence when ω ρ = 1 as we have seen in section 3.2. Only one communication sequence is acceptable

to which is associated the following 5-periodic communication sequence {ρ(0), ρ(1), . . .

In all the cases it is interesting to point out that some outputs/inputs are fixed to an established order. This fact is completely related to the system's structure. In this example, y 1 as well as u 1 must be accessed at the beginning of any chosen sequence.

CONCLUSION

This paper dealt with the generation of communication sequences which preserve observability and reachability of a system with communication constraints. To generate such sequences an original method based on the structural analysis was presented. Different communication sequences may be generated for different communication restrictions and in all the cases the minimal admissible restriction is calculated. The structural approach presented allows to get more insight into the system's limitations and possibilities to generate successful communication sequences.