Katina Kralevska
email: katinak@item.ntnu.no

Danilo Gligoroski
email: danilog@item.ntnu.no

Harald Øverby
email: haraldov@item.ntnu.no

Balanced XOR-ed Coding

Keywords: XOR coding, GF (2), Latin squares, Latin rectangles

de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Encoding and decoding over GF (2) (GF stands for Galois field with 2 elements: 0 and 1) is more energy efficient than encoding and decoding in any other larger field. Recent studies concerning several new techniques in network coding [START_REF] Ahlswede | Network information flow[END_REF] (Linear Network Coding (LNC) [START_REF] Li | Linear network coding[END_REF][START_REF] Koetter | An algebraic approach to network coding[END_REF] and Random Linear Network Coding (RLNC) [START_REF] Ho | A random linear network coding approach to multicast[END_REF]) confirmed that encoding and decoding over GF (2) are up to two orders of magnitude less energy demanding and up to one order of magnitude faster than the encoding/decoding operations in larger fields [START_REF] Shojania | Random network coding on the iphone: fact or fiction?[END_REF][START_REF] Pedersen | Implementation and performance evaluation of network coding for cooperative mobile devices[END_REF][START_REF] Vingelmann | Multimedia distribution using network coding on the iphone platform[END_REF].

The high computational complexity of packet encoding and decoding over large finite fields and its high energy cost which makes it unsuitable for practical implementation are the main motivation to seek for coding techniques only with XOR operations. The first theoretical work was done by Riis in [START_REF] Riis | Linear versus nonlinear boolean functions in network flow[END_REF] who showed that every solvable multicast network has a linear solution over GF [START_REF] Bhattad | Weakly secure network coding[END_REF]. Afterwards, XOR coding in wireless networks was presented in [START_REF] Katti | XORs in the air: Practical wireless network coding[END_REF], where the main rule is that a node can XOR n packets together only if the next hop has all n -1 packets. A more general network coding problem which is called index coding is considered in [START_REF] Rouayheb | On the index coding problem and its relation to network coding and matroid theory[END_REF][START_REF] Qureshi | Optimal solution for the index coding problem using network coding over gf(2)[END_REF]. In [START_REF] Qureshi | Optimal solution for the index coding problem using network coding over gf(2)[END_REF] the authors address the coding problem by proposing coding over GF [START_REF] Bhattad | Weakly secure network coding[END_REF]. The encoding scheme is based on bitwise XORing by adding redundant bits, and the decoding scheme is based on a simple but bit after bit sequential back substitution method.

The main contribution of our work is a construction of codes over GF (2) by using combinatorial designs (Latin squares and Latin rectangles) [START_REF] Colbourn | Applications of combinatorial designs to communications, cryptography, and networking[END_REF]. Its lower computation and energy cost makes it suitable for practical implementation on devices with limited processing and energy capacity like mobile phones and wireless sensors. We will illustrate the construction of codes by the following simple example. Example 1. We use the following strategy (Fig. 1): the source s performs bitwise XOR of packets with equal length based on the incidence matrix of a Latin rectangle L. Each column of L represents a combination of source packets x i , i = 1, . . . , 4, in a coded packet c i , i = 1, . . . , 4. In the first phase, the packets c 1 and c 2 are sent, and in the second phase, the packets c 3 and c 4 are sent. The intermediate nodes u 1 and u 2 forward the coded packets to the sink nodes t 1 and t 2 which decode the packets by using the inverse matrix of the incidence matrix of L. The sink nodes need only to know the combination of source packets in each received packet. Note that the max-flow in the network is achieved.

Routinely as in other coding approaches, this information is included in the header of each coded packet. Since in this paper we use diversity coding performed just by the source nodes, there is no need for updating the coefficients in the header at each intermediate node. The length of the prepended header vector is negligible compared to the length of the packet. The construction of our codes was not motivated by security issues, therefore the security is not the main goal in this paper. However, it turns out that for certain setups and parameters, our approach offers additional plausible security properties. The plausible security properties that accompany our approach are not based on hard mathematical problems in modern cryptology (for example factoring of large integers or discrete logarithm problems or on the Shamir's secret sharing algorithm). We show that if an eavesdropper wants to reconstruct at least one original packet, then the number of eavesdropped links should be equal to the max-flow of the network. Bhattad and al. [START_REF] Bhattad | Weakly secure network coding[END_REF] make similar observations when network coding is implemented so that a weekly secure network coding is achieved.

The rest of the paper is organized as follows: Section 2 presents the notation and the mathematical background that are used in the following sections. The construction of codes is presented in Section 3. Section 4 illustrates the security features of our approach. Sections 5 concludes the paper.

We define a communication network as a tuple N = (V, E, S, T ) that consists of:

a finite directed acyclic multigraph G = (V, E) where V is the set of vertices and E is the set of edges, -a set S ⊂ V of sources, -a set T ⊂ V of sink nodes. Assume that vertex s ∈ S sends n source packets to vertex t ∈ T over disjoint paths. A minimal cut separating s and t is a cut of the smallest cardinality denoted as mincut(s, t). The packets are sent in several time slots, i.e., phases denoted as p. The maximum number of packets that can be sent in a phase from s to t is denoted as maxflow(t). The Max-Flow Min-Cut Theorem [START_REF] Lawler | Combinatorial Optimization: Networks and Matroids[END_REF] indicates that mincut(s, t) = maxflow(t). The multicast capacity, i.e., the maximum rate at which s can transfer information to the sink nodes, cannot exceed the capacity of any cut separating s from the sink nodes. A network is solvable when the sink nodes are able to deduce the original packets with decoding operations. If the network is solvable with linear operations we say that the network is linearly solvable.

XOR-ed coding

First we recall that in [START_REF] Riis | Linear versus nonlinear boolean functions in network flow[END_REF], Riis showed that every solvable multicast network has a linear solution over GF (2) in some vector dimension. The essence of his proof relies on the fact that any two finite fields with the same cardinality are isomorphic. Thus, instead of working in a finite field GF (2 n ) for which the conditions of the linear-code multicast (LCM) theorem [START_REF] Li | Linear network coding[END_REF]Th. 5.1] are met, he showed that it is possible to work in the isomorphic vector space GF (2) n that is an extension field over the prime field GF (2). We formalize the work in the vector space GF (2) n with the following: Definition 1. A XOR-ed coding is a coding that is realized exclusively by bitwise XOR operations between packets with equal length. Hence, it is a parallel bitwise linear transformation of n source bits x = (x 1 , . . . , x n ) by a n × n nonsingular matrix K, i.e., y = K • x.

In [START_REF] Riis | Linear versus nonlinear boolean functions in network flow[END_REF] it was also shown that there are simple network topologies where encoding in GF (2) cannot reach the network capacity with the original bandwidth or by sending data in just one phase. However, it was shown that the network capacity by XOR-ed coding can be achieved either by increasing the bandwidth or the number of phases so that they match the dimension of the extended vector space GF (2) n . In this paper we take the approach to send data in several phases p instead of increasing the bandwidth.

Theorem 1. For any linearly solvable network topology with maxflow(t 1 ) > 1, the sufficient condition for a single sink t 1 to reach its capacity in each of p phases by XOR-ed coding is to receive n linearly independent packets x = (x 1 , . . . , x n ), where n = p × maxflow(t 1 ).

Proof. Assume that the network topology is linearly solvable. That means there exists a vector space GF (2) n where we can encode every n source bits with a bijective function K, i.e., y = K • x. Having in mind that the source s succeeds to send n encoded packets to t 1 in p phases, and the max-flow in the network is maxflow(t 1 ) > 1, we have that n = p × maxflow(t 1 ) and the sink t 1 receives n packets after p phases via maxflow(t 1 ) disjoint paths. In order to have a successful recovery of the initial n packets, the received packets should be linearly independent.

Based on Theorem 1 we can prove the following: Theorem 2. For any linearly solvable network topology and for any two sinks T = {t 1 , t 2 } that have maxflow(t) = maxflow(t 1 ) = maxflow(t 2 ), there always exists a XOR-ed coding for n = p×maxflow(t) packets that achieves the multicast capacity in each of p phases.

Proof. For the sink t 1 we apply Theorem 1 and find one XOR-ed coding that achieves the capacity in each of p phases. Let us denote by U 1 = {u 1,i | there is an edge (u 1,i , t 1 ) ∈ E} the nodes that are directly connected and send packets to the sink node t 1 . We have that |U 1 | = maxflow(t), and the set of n packets is partitioned in maxflow(t) disjoint subsets Y 1,1 , . . . , Y 1,maxflow(t) each of them having p packets. The subset Y 1,i comes from the node u i , i = 1, . . . , maxflow(t).

The set U 2 = {u 2,i |there is an edge(u 2,i , t 2 ) ∈ E} is a set of nodes that are directly connected and send packets to the sink node t 2 . We denote the intersection between the sets of nodes U 1 and U 2 as U 1,2 = U 1 U 2 . The following three situations are considered:

1. There are no mutual nodes that send packets to both sinks t 1 and t 2 , i.e., U 1,2 = ∅. In that case find one partition of the set of n packets in maxflow(t) disjoint subsets Γ 1 = {Y

= U 1 U 2 = U 1 .
In that case, the sink t 2 receives from the nodes in U 1,2 the same packets that are delivered to the sink t 1 . The multicast capacity for the sink t 2 is achieved in each of p phases.

Note that the proof of Theorem 2 is similar to the work by Jaggi et al. [START_REF] Jaggi | Low complexity encoding for network codes[END_REF] where they discuss a construction of general codes using simple algorithms. As a consequence of Theorems 1 and 2 we can post the following:

Theorem 3. For any linearly solvable network topology and for any set of N sinks T = {t 1 , . . . , t N } that have maxflow(t) = maxflow(t 1 ) = . . . = maxflow(t N ), there always exists a XOR-ed coding for n = p×maxflow(t) packets that achieves the multicast capacity in each of p phases.

Proof. (Sketch) First, we recall the construction of generic linear codes presented in the LCM theorem in [START_REF] Li | Linear network coding[END_REF]Th. 5.1]. Second, we use the transformation to equivalent codes over GF (2) n as it was shown in [START_REF] Riis | Linear versus nonlinear boolean functions in network flow[END_REF]. Then, the proof is a straightforward application of the mathematical induction by the number of sinks N . Let us suppose that the claim of the theorem is correct for N -1 sinks. By adding a new N -th sink we consider again three possible situations as in Theorem 2.

Construction of XOR-ed Coding

In this section we describe the construction of codes over GF [START_REF] Bhattad | Weakly secure network coding[END_REF]. Instead of working with completely random binary matrices, in the remaining part of this paper we work with nonsingular binary matrices that have some specific structure related to randomly generated Latin square or Latin rectangle. We do not reduce the space of possible random linear network encoding schemes, since the number of Latin squares and Latin rectangles of order n increases proportionally with factorial of n. Therefore, in our approach we have virtually an endless repository of encoding schemes that have the benefits from both worlds: they are randomly generated, but they have a certain structure and offer plausible security properties.

In order to introduce our approach, we briefly use several definitions that the reader can find in [START_REF] Stinson | Combinatorial Designs: Constructions and Analysis[END_REF] and [START_REF] Colbourn | Handbook of Combinatorial Designs[END_REF]. Definition 2. A Latin square of order n with entries from an n-set X is an n × n array L in which every cell contains an element of X such that every row of L is a permutation of X and every column of L is a permutation of X. Definition 3. A k × n Latin rectangle is a k × n array (where k ≤ n) in which each cell contains a single symbol from an n-set X, such that each symbol occurs exactly once in each row and at most once in each column.

For generating a Latin square, one can always start with a permutation of n elements that is a trivial 1×n Latin rectangle and can use the old Hall's marriage theorem [START_REF] Hall | On representatives of subsets[END_REF] to construct new rows until the whole Latin square is completed. However, this approach does not guarantee that the generated Latin squares are chosen uniformly at random. In order to generate Latin squares of order n that are chosen uniformly at random we use the algorithm of Jacobsen and Matthews [START_REF] Jacobson | Generating uniformly distributed random latin squares[END_REF]. Further, in our approach we sometimes split the Latin square into two Latin

s u 1 u 2 u 3 u 4 t 1 t 2 t 3 t 4 t 5 t 6 C2 C4 C3 C1 C1 C3 C4 C2
Fig. 1. A 4-dimensional binary linear multicast in a single source multicast Fig. 2. A 4-dimensional binary linear multicast in a single source multicast network with delay rectangles (upper and lower), and work with the algebraic objects (matrices or block designs) that are related to either the upper or the lower Latin rectangle. As a convention, throughout this paper, the number of packets n that are sent from the source is equal to the number of columns in the Latin square or Latin rectangle.

Example 2. As shown in Fig. 2, we assume that the source wants to send four packets x 1 , . . . , x 4 to the sink nodes, and that each sink node has maxflow(t k ) = 2, (k = 1, . . . , 6). The sink nodes receive data from different pair of intermediate nodes, u i , (i = 1, . . . , 4). Our aim is all six sink nodes to be able to reconstruct the source packets that are exclusively coded in GF (2).

Let us take the following Latin square and split it into two Latin rectangles:

L =    2 4 1 3 1 3 2 4 3 2 4 1 4 1 3 2    .
Each column from the 3 × 4 upper Latin rectangle represents a combination of source packets in a coded packet c i , i = 1, . . . , 4. Using the incidence matrix M of the Latin rectangle the source computes the coded packets.

Definition 4. Let (X, A) be a design where X = {x 1 , . . . , x v } and A = {A 1 , . . . , A b }.

The incidence matrix of (X, A) is the v × b 0-1 matrix M = (m i,j ) defined by the rule

m i,j = 1, if x i ∈ A j , 0, if x i / ∈ A j .
Proposition 1. The incidence matrix M = (m i,j ) of any Latin rectangle with dimensions k × n is balanced matrix with k ones in each row and each column.

Proof. From the definition of the incidence matrix it follows that the number of ones in each row is equal to the number of elements k in each column of the Latin rectangle. On the other hand, since each row of the Latin rectangle is a permutation of n elements, and there are no elements that occur twice in each column, the number of ones in each column can be neither less nor larger than k.

Note 1. The incidence matrix M of a k × n Latin rectangle is always balanced. However, the inverse matrix of the incidence matrix M -1 is not always balanced.

Proposition 2. The necessary condition an incidence matrix M = (m i,j ) of a k × n Latin rectangle to be nonsingular in GF (2) is k to be odd, i.e., k = 2l + 1.

Proof. Assume that k is even, i.e., k = 2l. Recall that a matrix M is nonsingular in GF (2) if and only if its determinant is 1 (or it is singular if and only if its determinant is 0). Recall further the Leibniz formula for the determinant of an n × n matrix M : det(M ) = σ∈Sn sgn(σ)

n i=1 m i,σi
, where the sum is computed over all elements of the symmetric group of n elements S n , i.e., over all permutations σ ∈ S n , and sgn(σ) is the signature (or the parity of the permutation) whose value is +1 or -1. The elements m i,σi are the elements m i,j of the matrix M where the value for the index j = σ i is determined as the i-th element of the permutation σ.

If k = 2l is even, from Proposition 1 and from the fact that operations are performed in GF (2), it follows that every summand in the Leibniz formula gives an even number of nonzero products, thus the final sum must be even, i.e., the determinant in GF (2) is 0.

The corresponding 4 × 4 incidence matrix of the Latin rectangle in Example 2 is nonsingular in GF (2) (Proposition 2). M is represented as

M =    1 1 1 0 0 1 1 1 1 1 0 1 1 0 1 1    .
A direct consequence from Theorem 1 is the following: Corollary 1. A sink node t ∈ T with maxflow(t) can receive n source packets, encoded with the incidence matrix of a k × n Latin rectangle in GF (2), in p = n maxflow(t) phases. In each phase the sink node reaches its maxflow(t).

Following Corollary 1 the number of phases in which packets are sent depends from the total number of packets and maxflow(t k ).

Using M the source computes the vector of coded packets as

c = M x = [c 1 , c 2 , c 3 , c 4 ] where x = [x 1 , x 2 , x 3 , x 4
] is a vector of the source packets. The coded packets are XOR-ed combinations of the source packets, i.e.,

c1 = x1 ⊕ x2 ⊕ x3, c2 = x2 ⊕ x3 ⊕ x4, c3 = x1 ⊕ x2 ⊕ x4, c4 = x1 ⊕ x3 ⊕ x4.
The source further prepends the information from the incidence matrix to each of the coded packets. The vector of packets that are sent becomes as follows: C = Table 1. Description of receiving coded packets in each phase at the sink nodes

t1 t2 t3 t4 t5 t6 First phase C4, C1 C4, C3 C4, C3 C1, C2 C1, C2 C3, C2 Second phase C2, C3 C2, C1 C2, C1 C3, C4 C3, C4 C1, C4 {(1, 2, 3, c 1 ), (2, 3, 4, c 2 ), (1, 2, 4, c 3 ), (1, 3, 4, c 4 )} = {C 1 , C 2 , C 3 , C 4 }.
The sink nodes receive in each phase a pair of different packets as shown in Table 1. Their buffer should be large enough to store the received packets C i , i = 1, . . . , 4. The decoding at the sink nodes is performed by M -1 . Each sink node computes M -1 from the prepended indexes. The original packets x i , i = 1, . . . , 4, are reconstructed as x = M -1 c. Note that although our approach is similar to [START_REF] Riis | Linear versus nonlinear boolean functions in network flow[END_REF], we use a systematic selection of the encoding functions and we do not send plain packets on the disjoint paths.

Additional Plausible Security Properties of the Balanced XOR-ed Coding

The work with incidence matrices related to randomly generated Latin rectangles is actually a work with balanced block designs. However, as we noted in Note 1, it is not necessary both the incidence matrix and its inverse matrix to be completely balanced. If we are interested in the complexity of decoding and the security issues when an adversary can successfully decode some sniffed packets, then the easiest way to address these issues is to give equal level of security to all encoded packets. In our approach this can be easily achieved by switching the roles of the incidence matrix and its inverse matrix: the encoding of the source packets is done with the inverse matrix of the incidence matrix and decoding of the coded packets is done with the incidence matrix. By applying this approach, decoding of any of the source packets requires an equal number of coded packets.

Corollary 2. For each value of maxflow(t) and a number of source packets n which is multiple of maxflow(t), there exists a Latin rectangle with n -1 or n -2 rows and its incidence matrix can be used for decoding.

Due to Proposition 2, when n is even the necessary requirement for a nonsingular incidence matrix is the Latin rectangle to have n -1 rows. When n is odd the necessary requirement for a nonsingular incidence matrix is the Latin rectangle to have n -2 rows. Theorem 4. When decoding is performed with the incidence matrix from Corollary 2, any eavesdropper needs to listen at least maxflow(t) links in order to decode at least one source packet. Proof. Assume that an adversary eavesdrops maxflow(t) -1 links. Since the incidence matrix used for decoding is related to a Latin rectangle with n -1 or n -2 rows, eavesdropping "just" maxflow(t) -1 links is not sufficient for the adversary to receive at least one subset of n -1 or n -2 packets from which he/she can decode at least one original packet.

Another remark that can be given about our approach is that the number of XOR operations between different packets (both in the source and in the sink nodes) is relatively high. We can address that remark by using Latin rectangles with smaller number of rows as a trade-off between the number of encoding/decoding operations and the ability of an adversary to decode a source packet. Namely, the encoding and decoding efforts at the source and sink node are the highest when encoding and decoding requires n -1 or n -2 packets. In order to decrease the number of operations at the nodes, the Latin rectangle should have k ≤ n -2 rows. However, we are interested to reduce the number k without reducing the number of links that have to be listened by an eavesdropper in order to decode at least one original packet. The following theorem gives the necessary and sufficient condition for that to happen: Theorem 5. Let the coding be done by M -1 obtained from a Latin rectangle L k×n of size k × n, where k ≤ n -2. Further, assume that the transfer is done by sending n packets from s to t in p = n maxflow(t) phases on maxflow(t) disjoint paths and let the sets of indexes of the packets sent via i-th disjoint path are denoted by S i , i = 1, . . . , maxflow(t). A necessary and sufficient condition for an eavesdropper to need to listen at least maxflow(t) links in order to decode at least one original packet is:

∀j ∈ {1, . . . , n}, ∀i ∈ {1, . . . , maxflow(t)} : L k,j ∩ Si = ∅, (1)
where L k,j , j ∈ {1, . . . , n} is the set of elements in the j-th column of the Latin rectangle L k×n .

Proof. To show that the condition ( 1) is necessary assume that an eavesdropper needs maxflow(t) -1 links in order to decode one original packet x l , and let us denote by S m the set of indexes of the packets sent via the disjoint path that was not listened by the eavesdropper. This means that for the l-th column L k,l of the Latin rectangle L k×n : L k,l ∩ S m = ∅ which violates the condition (1).

To show that the condition (1) is sufficient, let us denote by S i,j = L k,j ∩ S i , j ∈ {1, . . . , n}, i ∈ {1, . . . , maxflow(t)}. It is sufficient to notice that S i,j are disjunctive partitions for every set L k,j , i.e., ∀j ∈ {1, . . . , n} :

maxflow(t) i=1 S i,j = L k,j and ∀j 1 , j 2 ∈ {1, . . . , n} : S i,j1 ∩ S i,j2 = ∅.
Since |L k,j | = k, and the encoding of original n packets is done by M -1 , it follows that an eavesdropper can decode any original packet only by listening at least maxflow(t) links.

Example 3. We present an example that illustrates the security in our approach. The goal is to achieve secrecy1 so that a passive adversary is able to reconstruct n source packets only when at least maxflow(t) links are eavesdropped. By sending XOR-ed packets on disjoint paths (exploiting the path diversity), an adversary is unable to decode the message although several paths are eavesdropped. Let us consider the network shown in Fig. 3, where a source s communicates with two sinks t 1 and t 2 with the help of intermediate nodes u i , i = 1, 2, 3, and sends twelve packets to t 1 and t 2 . Packets are sent in four phases since maxflow(t) = 3. Let us use the following 5 × 12 Latin rectangle: The colors of indexes in L 5×12 correspond to the colors of the packets as they are sent in Fig 3 . If the sink nodes reconstruct the source packets with M -1 , then not all packets have the same level of decoding complexity. That is demonstrated with relations (2) and (3). For instance, to decode x 4 , x 7 and x 8 nine coded packets are needed, while to decode x 5 and x 11 just three packets are needed. The goal is to avoid this non-balanced complexity in the decoding. Therefore, as in Theorem 5 the encoding is done by M -1 and the decoding by M . When s computes the vector of coded packets as c = M -1 x, then the coded packets c i , i = 1, . . . , 12 are XOR-ed combinations of different number of source packets. Consequently, decoding of packets is done with a balanced matrix, i.e., x = M c.

L 5×12 =      4
s u 1 u 2 u 3 t 1 t 2 C3 C10 C7 C2 C8 C4 C11 C9 C1 C6 C5 C12
Fig. 3. Routing of 12 packets for secure coding when decoding is performed with 5 coded packets

c1 =x2 ⊕ x3 ⊕ x4 ⊕ x6 ⊕ x9, c2 =x2 ⊕ x4 ⊕ x5 ⊕ x8 ⊕ x10, c3 =x1 ⊕ x2 ⊕ x7 ⊕ x11 ⊕ x12, c4 =x3 ⊕ x6 ⊕ x8 ⊕ x9 ⊕ x10, c5 =x1 ⊕ x3 ⊕ x6 ⊕ x11 ⊕ x12, c6 =x1 ⊕ x7 ⊕ x10 ⊕ x11 ⊕ x12, c7 =x2 ⊕ x4 ⊕ x5 ⊕ x8 ⊕ x9, c8 =x3 ⊕ x5 ⊕ x6 ⊕ x8 ⊕ x11, c9 =x4 ⊕ x5 ⊕ x7 ⊕ x10 ⊕ x12, c10 =x1 ⊕ x4 ⊕ x7 ⊕ x8 ⊕ x11, c11 =x2 ⊕ x6 ⊕ x9 ⊕ x10 ⊕ x12, c12 =x1 ⊕ x3 ⊕ x5 ⊕ x7 ⊕ x9.
(2)

x1 =c2 ⊕ c5 ⊕ c10 ⊕ c11 ⊕ c12, x2 =c1 ⊕ c3 ⊕ c5 ⊕ c6 ⊕ c7 ⊕ c9 ⊕ c10, x3 =c3 ⊕ c5 ⊕ c6 ⊕ c7 ⊕ c8 ⊕ c9 ⊕ c12, x4 =c4 ⊕ c5 ⊕ c6 ⊕ c7 ⊕ c8 ⊕ c9 ⊕ c10 ⊕ c11 ⊕ c12, x5 =c1 ⊕ c2 ⊕ c4, x6 =c1 ⊕ c2 ⊕ c4 ⊕ c6 ⊕ c7 ⊕ c10 ⊕ c11, x7 =c2 ⊕ c3 ⊕ c4 ⊕ c5 ⊕ c6 ⊕ c7 ⊕ c8 ⊕ c11 ⊕ c12, x8 =c1 ⊕ c3 ⊕ c5 ⊕ c7 ⊕ c8 ⊕ c9 ⊕ c10 ⊕ c11 ⊕ c12, x9 =c1 ⊕ c2 ⊕ c5 ⊕ c9 ⊕ c10, x10 =c1 ⊕ c5 ⊕ c7 ⊕ c9 ⊕ c10, x11 =c1 ⊕ c7 ⊕ c8, x12 =c3 ⊕ c4 ⊕ c5 ⊕ c7 ⊕ c9. (3)
Assume that the routing is as follows: on the first path the source sends (C 3 , C 10 , C 7 , C 2 ), on the second path (C 8 , C 4 , C 11 , C 9 ) and (C 1 , C 6 , C 5 , C 12 ) on the third path as it is shown in Fig. 3. We use three different colors for the packets sent to three disjoint paths in order to demonstrate the essence of the proof of Theorem 5. Note that all colors are present in every column of the Latin rectangle L 5×12 . This corresponds to the condition (1) in Theorem 5. In order to reconstruct at least one source packet, an adversary must eavesdrop at least 3 links.

Conclusions

In this paper we have presented a construction of codes over GF (2) which reach the max-flow for single source multicast acyclic networks with delay. The coding is exclusively performed in GF (2), i.e., it is a bitwise XOR of packets with equal lengths. The encoding and decoding are based on balanced nonsingular matrices that are obtained as incidence matrices from Latin rectangles. Balanced XOR-ed coding is of particular importance for energy and processor constraint devices. Additionally, we showed that the approach offers plausible security properties, i.e., if an eavesdropper wants to reconstruct at least one original packet, then the number of eavesdropped links must be equal to the max-flow of the network.

Possible future work includes intermediate nodes to form coded packets, as well as building networks dynamically by adding more and more sink nodes that reach the max-flow when the coding is XOR-ed coding.

2 c3Fig. 1 .Fig. 1 .

 211 Fig. 1. A 4-dimensional binary linear multicast in a single source multicast Fig. 1. An example of balanced XOR coding where the source sends combinations of source packets (combined as the column of the Latin rectangle). The intermediate nodes just forward the data to the sink nodes.

  The multicast capacity for the sink t 2 is achieved in each of p phases. 3. All the nodes that send packets to the sink t 1 , send packets to the sink t 2 as well, i.e., U 1,2

2,1 . . . , Y 2,maxflow(t) } each of them having p packets. The sets of packets Y 2,j are delivered to the sink t 2 via the node u 2,j , j = 1, . . . , maxflow(t). The multicast capacity for the sink t 2 is achieved in each of p phases. 2. There are nodes that send packets to both sinks t 1 and t 2 , i.e., U 1,2 = {u (1,2)ν 1 , . . . , u (1,2)ν k }. Denote the nodes that are in U 2 \U 1 = {u 2ν 1 , . . . . . . , u 2ν maxflow(t)-k }. In that case, the sink t 2 receives from the nodes in U 1,2 the same packets that are delivered to the sink t 1 . The number of the remaining packets that have to be delivered to t 2 is exactly p×(maxflow(t)-k). Find one partition of maxflow(t)-k disjoint subsets Γ 2 = {Y 2,1 . . . , Y 2,maxflow(t)-k } each of them having p packets. The sets of packets Y 2,j are delivered to the sink t 2 via the node u 2,νj , j = 1, . . . , maxflow(t) -k.

We use here the term secrecy as it is used in[START_REF] Médard | Network coding, Fundamentals and Applications[END_REF] Ch.7 pp. 185]

Acknowledgements

We would like to thank Gergely Biczók for his discussions and remarks that significantly improved the paper.


Kornschnok Dittawit

Arve Finn
email: finnarve@item.ntnu.no

Aagesen

Architecture and Functional Framework for Home Energy Management Systems

Keywords: energy management system, smart home, smart grid, demand side management, policy-based reasoning

Residential consumers contribute to a substantial amount of electricity consumption. To ensure grid stability, a Home Energy Management System (EMS) that assists household inhabitants in operating home devices to achieve optimized energy usage is needed. Previous designs of Home EMS often have some issues. First, it places high implementation overhead on device vendors to manufacture devices compatible with the system. Second, it lacks the ability to scale when new device types and external variables are introduced. This paper proposes an architecture model and a functional framework for Home EMS that are simple and scalable. The framework defines functions of Home EMS components. A policy-based reasoning mechanism is proposed as part of the framework for the optimization of home energy usage. In addition, the inter-working of Home EMS components is presented. It relies on a semantic web language for data representation to provide meaningful information for reasoning and harmonization with existing standards.

Introduction

Today's power grid is the result of over hundred years of evolution [1]. At present, there is a vision to transform the present grid into what is denoted as the Smart Grid. In Smart Grid, distributed generation (DG) is promoted, consumers are offered more choices and real-time information, and information and communication technology is tightly integrated for better management. The market is also changing to become more deregulated with the entry of smaller power providers and the possibility of consumers to provide power. As a research area, Smart Grid is considered a multidisciplinary area that spans over multiple domains. This paper looks at the residential demand side of the power grid.

In the EU, residential electricity consumption in 2010 accounted for around one-third of the total consumption [2]. This ratio indicates the importance and the influence of households on the power grid. In other words, electricity usage by households affects grid stability as a whole. This can be seen especially during peak periods when power demand rises and causes a strain to the power grid. One way of ensuring grid stability is the adjustment of consumer energy consumption pattern. To facilitate the adjustment process, assistance to consumers will be needed to decide on how to operate home devices to achieve optimized energy usage. New commercial products are being pushed out that include some energy management functions and there have been many attempts to design a central system to manage home devices. However, the problems with most these product and system designs are 1) it does not look at the hollistic view of the system and was designed to solve a specific problem with no concern on the other components that exist on the power grid 2) it requires specially manufactured devices in order to be compatible with the system which puts a lot of implementation overhead to device vendors and prevents market entry of the system and 3) it lacks scalability when new device types and external variables are introduced. Although it is not possible in practice to design a system to handle new unknown problems, it is possible to design a framework that will serve as a solid and scalable foundation for future solutions.

This paper proposes an architecture model and a functional framework for Home Energy Management System (EMS), a system in a house that assists household inhabitants in operating home devices to achieve optimized energy usage. The architecture model looks at a hollistic view of the system and takes into account the major entities on the power grid which are the Distribution System Operators (DSOs) and Energy Service Providers (ESPs). It was designed to be simple and scalable to enable rapid deployment and also to be integratedly easily with existing standards, namely Sensor Web Enablement [START_REF]Open Geospatial Consortium: Sensor Web Enablement[END_REF] and IEC61970-501 [START_REF]International Electrotechnical Committee[END_REF] which is suggested for use in the power industry. Home EMS components, component functions, and Home EMS inter-working framework have been defined. A policy-based reasoning mechanism is also proposed for energy management as part of the functional framework.

The remaining part of this paper is organized as follows. Section 2 discusses present technology and related works. Section 3 presents the proposed architecture and functional framework. Energy management in Home EMS is discussed in Section 4. Home EMS inter-working framework is presented in Section 5. Section 6 summarizes and concludes.

Present technology and related works

With the increasing concerns in energy conservation and energy efficiency, device vendors are responding to this issue by developing products that facilitate energy savings in households and are more energy efficient. Most of the released products provide the basic function to control the status of home appliances. For example, a consumer may control appliance statuses from the comfort of his mobile device and PC or set a timer to turn the appliances on or off [5] [6]. Some vendors provide a way for consumers to monitor energy consumption for an individual appliance with a specific apparatus [START_REF]eGauge overview[END_REF]. Modern washing machines have a delay start function that allows consumers to set the start time for the washing machine so as to avoid peak periods. As useful as they are, these devices were designed to solve very specific problems and the functions offered are only a small subset of functions that will be incorporated into consumer houses in the future. In addition, some functions such as the delay start function still require consumers to make difficult decisions based on various information sources with no assistance which results in most of these functions left unused. With some analysis, we would see that the value of these new appliances lies in the automation and scheduling of their basic operations, so what is needed is a decision support system that aids household inhabitants in controlling and coordinating appliances to optimize energy usage, i.e., Home EMS is needed.

There have been many research activities related to Home EMS including the effort by the European Commission which funded several research projects under the Seventh Framework Programme (FP7) such as AIM [START_REF]AIM: A novel architecture for modelling, virtualizing and managing the energy consumption of household appliances[END_REF], Beywatch [START_REF] Beywatch | Beywatch Home[END_REF], and Smart House/Smart Grid (SH/SG) [START_REF]SmartHouse-SmartGrid Consortium: Smart House/Smart Grid[END_REF]. In AIM, the inter-working between home devices and the central system was well-designed and it is the same principle used in our proposal. The difference is our use of semantic web language for device information and message-based communication for operation and service invocation as opposed to packet-based solution in AIM. Our message-based solution provides greater flexibility and negates the need to establish standardized command codes before the manufacturing of home devices. The objective of Beywatch included the design of energy efficient white goods. As a result, the appliances that were compatible with Beywatch system had to be specifically manufactured. In SH/SG, energy management was done by algorithmic systems which means substantial effort will be required to change the logic if new device types and external variables are introduced into the picture. In terms of the system architecture, two reference models can be derived from the three projects based on the connectivity among the related systems as depicted in Fig. 1. In model A used by Beywatch, Home EMS is connected to an entity that hosts a medium which is further connected to power utilities and external service providers (SPs). The entity is called Service Provider in Beywatch which implies it can be any entity. In this case, we assume it is the DSO that takes the position of that entity and thus the utilities include only ESPs. In model B used by AIM and SH/SG, Home EMS is connected to DSO, ESPs, and external SPs directly. The comparison between the two models is presented in Table 1. The proposed architecture follows model B for the benefits described and its flexibility of consumers to switch or establish connections to other external SPs.

Consumer Support System functionality

CSS is a computing device in Home EMS that is responsible for energy management, which is the monitoring, controlling, and coordinating of home devices with the help of data obtained from various external systems and home devices in order to optimized energy usage. The proposed functions required by CSS in order to perform energy management are grouped into five main function groups: basic function, policy/goal/constraint management, service and device configuration, monitoring and diagnosis, and user interface. These functions are realized by a combination of Extended Finite State Machines (EFSMs) and a policy-based reasoning machine (see Sect. 4 for more details). Each function group performs sub-functions as shown in Fig. 3. The data maintained by CSS is stored in five different repositories based on the type of data. The details of each function group and repository are given.

Basic function (BSC) BSC performs normal operation and suspended operation. Normal operation refers to an operation mode where CSS performs actions based on the policies, goals, and constraints defined in the system. Suspended operation refers to an operation mode where energy management control actions are taken entirely by the consumer. This could occur from system failure or from deactivation by the consumer.

Policy/Goal/Constraint management (PGC) PGC maintains policies, goals, and constraints in the system. This includes the specification, update, and (re-)validation actions. (Re-)validation applies only to policies. The actions of specifying and updating policies, goals, and constraints could be initiated by the consumer through the CSS user interface or by CSS itself. Service and device configuration (SDC) SDC mainly handles the registration and deregistration of home devices and external services. It also maintains subscription of data and event from home devices and external systems. In addition, it creates and updates consumer-defined services from the consumer inputs given through the user interface.

Monitoring and diagnosis (MON) MON performs home device state monitoring, home device liveness monitoring, home energy usage monitoring, external system data monitoring, fault diagnosis, and statistics calculation. Home device state monitoring monitors the states of home devices. Home device liveness monitoring monitors the operating status of the device, which could at one time be normal mode, standby mode, or off mode. Home energy usage monitoring monitors energy consumption, production, and storage for the entire household and for individual home devices. External system data monitoring monitors data provided by external systems. Fault diagnosis is the analysis of faults found in Home EMS components. Statistics calculation is the collection and calculation of historical data such as electricity cost and energy consumption heuristics.

User interface (UI) UI is responsible for providing graphical user interfaces for the consumer to manage home devices, external system services, consumerdefined services, and policies/goals/constraints. It also displays results from consumer requests, feedbacks from executed actions, and subscribed data and event notifications. CSS must be able to render any device's and system's generic user interface based on the information of the device and system provided in the common agreed format.

Home device functionality

A home device is any device in the house that belongs to the consumer. It can either be a energy consumer device (white goods and multimedia devices), power producer device (solar cells and wind turbines), sensor device (temperature sensor and motion sensor), or energy storage device (electric vehicles). In most cases, a home device has attributes (e.g. temperature and status) and performs operations (e.g. get/set temperature, get/set status). This could be slightly different in case of a sensor. A sensor normally provides measurements on its observed environmental property. Some sensors only publish measurements to CSS hence no operations. Others might be capable of returning measurements upon request. See Fig. 4(a) for a home device ontology. The functionalities of a home device are grouped into three function groups: primary operation, agent function, and monitoring. Each function group is comprised of subfunctions as shown in Fig. 4(b). Note that for a simple device such as a sensor, some functions may not be implemented. For example, there could be only one operation mode for a sensor. In addition, a home device needs a functional component for both communicating with CSS and with itself via electrical signals to perform Primary Operation and Monitoring functions as instructed by CSS. This component is denoted as a CSS Agent and it is the entity performing Agent Function.

¡ ¢£¤¥¦ ¤¢¨© ¡ ¥¨ ¤¢¨© ¡ ¤¢¨© ¡ © £©!"#£¥"¢ ¡ $¢¤¤¥£ ©#%¢¨©£ ¡ ¢""&¥"¢ ¢£"!"¥¢£ ¡ ¥© ¤¢"¢£"! §'()0
Primary operation handles home device operations in different operating modes. A device can be in normal mode where it is able to receive commands and send responses and notifications to CSS, standby mode where it is able to receive wakeup signal, or off mode. In off mode, the device is still a part of Home EMS but cannot interact with the system. It has to be turned on manually by the consumer.

Agent function responds to commands, and sends out subscribed notifications. It also handles the (de-)registration of the device to CSS.

Monitoring monitors the inherent attributes of itself, i.e. the state, and may store the state data in its internal datastore.

Energy management realization

Energy management in Home EMS is the responsibility of CSS. The subfunctions performed by CSS in order to carry out energy management are realized by a combination of EFSMs and a reasoning machine (RM) as illustrated in Fig. 5. RM is a decision-making component that can be invoked by any EFSM requiring decision support, in this case E BSC and E MON . The logic to reach the decisions normally comes from extensive research which tends to change due to new researched solutions or the emergence of new variables. To cope with this issue, the energy management logic should be contained and formalized in a form that facilitates changes. For this matter, policy-based reasoning provides the flexibility that allows new rules to be specified without re-compilation [START_REF] Aagesen | On Capability-related Adaptation in Networked Service Systems[END_REF]. Thus, the term reasoning in the reasoning machine refers to policy-based reasoning.

RM interprets policy specifications and goal specifications. A policy is a set of rules and actions. Rules are defined by variables and constraints. Variables are relevant data required in order to select actions. There are two types of variables: decision variable and dynamic variable. A decision variable is what needs to be determined by RM, e.g. the start time of a device. A dynamic variable is data that changes as a function of time and may be beyond the control scope of RM, e.g. energy and grid prices. Dynamic variables influence the values of decision variables. For example, grid price (dynamic) during certain time of day is high so the start time (decision) could be delayed to reduce cost. Constraints are imposed on decision variables which, consequently, restrict the possible actions. Each action has a cost. Goals are associated with policies and define the targets to achieve. The goal specification and costs of actions determine the selection

¡¢£¤¥¢¦ §¤ £¢ ¨¥ § § § ! § "¥ § " §# § ¢$¤%& ¨¥ § ' §¦#¤% §( ''%¦¤¥¤¢£ ¨¥ § )¢¡ § ¨ §#¤% § $¤# §£ §'' ¨¥ § ¢$¤%& ¨¥ § ' §¦#¤% §( ¢ §¦¥¤¢£ ¨¥ § ' §¦#¤% §( ¢ §¦¥¤¢£ ¨¥ § ©0 123 450 ©60 78 §# §£¥ £¢¥¤¤%¥¤¢£ ZD 9@ABC 9DE ¦ §$¤F¤£G HIPQ E §'¢£¤£G ¡%)¤£ § R! R'¤% £%¥¤¢£ "! §¦#¤% § £¨¨ §#¤% § %¢£¤G¦¥¤¢£ ! ¢$¤%&(G¢$(%¢£'¥¦¤£¥ ¡£G §¡ §£¥ ES E¢£¤¥¢¦¤£G £¤ G£¢'¤' TU T' §¦ ¤£¥ §¦% § " §# § V¢¡ § ¨ §#¤% § ¦ §¢'¤¥¢¦& § §¦#¤% § £¨¢ §¦¥¤¢£ ¦ §¢'¤¥¢¦& ! § ¢$¤%&(G¢$(%¢£'¥¦¤£¥ ¦ §¢'¤¥¢¦& § '%¦¤¥¤¢£ ¦ §¢'¤¥¢¦& "¥ § V¢¡ § 9E ¨¥ ¦ §¢'¤¥¢¦& WXXY`abcdbefg ¤£#¢h § ¡¢£¤¥¢¦¤£G ¦ §i §'¥ ¦ §'$¥' ¤£#¢h § ¦ §'$¥' ¦ §¨(p¦¤¥ § %¥¤¢£' ¦ §i §'¥ ¦ §¥¦£ §¨¦ §'$¥'
qed`r Wggesbcd`t Y`guefg`g de vegd Y`wx`gdg cY`fed gyef eY gbvubsbd

¡¢¢£¤¥¡¦ §¨©¥¦ ¤£¦¡¥¢ ¡¢£¢¦¡¥¦ § §¢¢¥£ ¡¢© §¥¦ £ ¥¤! "¡¥¡# § £¢¦¡¥¦ $£¡ © §¥¦ %¡ §¦ & §'¥¤ §(¦¡¦ § § §¢¢¥£ )£¦ ! 01¨ §¦ © § 2 # §¥ 3¤¦¥'¥¦! ¡ & §¤¥¢¥£"¡¥¡# § &!¡4¥¤"¡¥¡# § ¥¢%! § & §'¥¤ §(¦¡¦ %¥4 § 5 §¤¦¥¤¥¦! £¢¦ 1¦¨££ % §4 §¡¦1 § 5 §!6 $¥¨¥¤ § & §'¥¤ § (¦¡¦ § 5 §!6 £7 §£¦¡¤¦%! § 3¤¦¥£ £¢¦ ¡¢£¢¦ ¡¢1¦1¦ ¥4£¢ §¨ §¢¦¥¤¦¢ § §¢¢¥£ § §¢¢¥£ 89@ABCDEFBG 89@A8H ICDI8GAE PQQRSTUVWUXY § §¨¢ & §'¥¤ § §¡¦¥£ %¥4 § 5 §!6 £7 §%£a §¨1¤ § %¡ §¦ 5 §¤¦¥¤¥¦!£¢¦ %¡ §¦ §¡¦¥%¥4 §
bXWSc bXW Vdd eX``UQdS TVRUVQdSfgXY`WRVUYWfhXVd WieS`VRS UYgdpqSqr Fig. 6. Policy and goal ontology model of actions when more than one action set is applicable. The decided actions, which are mainly operating instructions, will be executed on home devices. Fig. 6 depicts an ontology model for all related concepts. For readability, the example constraints are high-level concepts that can be formulated by decision variables.

Policies are ideally created and updated by the CSS vendor. The constraint values are set by the consumer. Apart from the policies themselves, statistics related to energy consumption heuristics of home devices can be used to adjust some estimates that will improve the decision making by RM.

Policy example: optimized laundry

One policy example that operates a washing machine (wm) at the optimal time and further suggests the method and time to dry clothes (electric dryer (ed) or outdoor drying (od)) is described. The maximum delay between activities is one hour. The goal is to minimize the electricity cost. The constraint is the latest finish time. Two policies are described in Table 2. Dynamic variables are specified explicitly. Decision variables are the start time, dry time, and cost. The first policy describes a case when od is selected while the second policy describes a case when ed is selected. For both cases, the optimal times to start wm, od, and ed are selected based on the weather conditions retrieved from an external weather service and electricity prices retrieved from DSO and ESP which are used to calculate the end time and the electricity cost.

Let: And drytime(t) is the estimated outdoor drying duration in hours which is calculated as a function of the weather conditions from time t to t latest (see (1)). The estimation is based on the heuristics related to the temperature, wind, and humidity. Infinite duration means outdoor drying is not possible.

t
drytime(t) = f (weather(t, t latest )) ∈ {1, 2, ..., ∞} (1)
5 Home EMS inter-working framework

An inter-working framework is here defined as an application layer framework that governs how CSS, home devices, and external systems communicate with one another. Two things are defined: 1) a common and formal format for operation and service description and 2) operation and service invocation. Operations and services provided by home devices and external systems need to be defined in a common agreed format to be accessible and executable by CSS. The required elements to be defined are ID, name, and description, with the optional addition of parameters and return values. We propose the use of RDF/XML as a language for operation and service definitions as well as home device and external system information. Resource Description Framework (RDF) [START_REF]World Wide Web Consortium: Resource Description Framework (RDF)[END_REF] is a semantic web language for describing resources on the web. There are four reasons for choosing RDF: 1) it can be expected that full ontology models for appliances will be standardized 2) RDF is good at modeling relationships in a meaningful way which can be used by CSS to make decisions 3) RDF is suggested as a data exchange format to be used by power utilities in IEC61970-501 [START_REF]International Electrotechnical Committee[END_REF] hence simpler integration with DSO and ESPs. 4) Semantic Sensor Network Ontology [START_REF]W3C Incubator Group: Semantic Sensor Network XG Final Report[END_REF] coupled with Sensor Web Enablement [START_REF]Open Geospatial Consortium: Sensor Web Enablement[END_REF] can be used for the description and measurement data of sensors. Fig. 7(a "msgID ": " CSS201220504170000 ", "type ": "http ://sg.item .ntnu .no/homeems / terms #RequestMessage ", "source ": " http ://homeems -aagesen .net/ CSS", "destination ": " http ://g-appliance .com/ devices /washing -TS169", "operation ": "SetProgram ", "parameters ": { "SetProgramParam _watertemp ": 30, "SetProgramParam _spinspeed ": 1400 } } ¡¢£¤¥¢¦ §¨¨¡ ¢¦ ¢ ¤¦ ¦ ! "¥¢#¥" ¦$!#¥" " %&'()01 2 34¢¤ 56$# $$¢7 " 89@ Fig. 7. Device information description and request message in accordance to the ontology depicted in Fig. 4. The highlighted line shows how a standardized operation name can be specified. This line can be added at any time and the vendor only needs to provide the updated information file which may be pushed to CSS. What this really means is device vendors and CSS vendors can manufacture their products separately without being concerned on naming protocols because declaring that one operation is the same as the other only requires one line. This device information file contains operation descriptions along with other device information. It must be provided by a home device to CSS upon registration. Services exposed by external systems are defined in the same way but the registration is often a manual process by the vendor of the CSS at manufacture time. This is because existing web services use different methods for service execution and thus have to be handled differently. In this regard, service descriptions for external services exist only to enable consistent processing and semantic classification of available services. Operation and service invocation between CSS and home devices or CSS and external systems is done through message exchange. There are three types of messages: request, response, and notification. All messages are included as HTTP payloads. The format of the message is JavaScript Object Notation (JSON) (http://www.json.org). JSON was chosen as opposed to XML-based languages because the processing needs for production is low and thus can be constructed by most devices including microcontrollers. However, any reference to device or system in a JSON-encoded message needs to be the same URI as defined in the RDF/XML device or system information file. See Fig. 7(b) for an example request message in JSON. Note that this inter-working framework only specifies the interface for the communication between Home EMS components. The translation and conversion of the received messages into electrical signals for the actual control of home devices is a necessary and inevitable process that must be done by the device vendors.

Fig. 1 .

 1 Fig. 1. Common architecture models for Home EMS

Fig. 2 .

 2 Fig. 2. Home EMS architecture

Fig. 3 .

 3 Fig. 3. CSS functions

Fig. 4 .

 4 Fig. 4. Home component ontology and functions

Fig. 5 .

 5 Fig. 5. ESFM and RM interaction diagram

  ) shows a simplified device information file of a washing machine. RDF terms used are <rdf :Description rdf :about ="washing -TS169"> <rdf:type rdf :resource ="&hems;WashingMachine "

  They are accessed by EFSMs of the same name as the realized function groups. DataRep stores monitoring and statistical data and is accessible by EM and MON. DevRep stores home device manufacturing information and is accessible by SDC and MON. SORep stores information on registered home device operations and external system services and is accessible by all EFSMs. PGCRep stores policies, goals, and constraints and is accessible by EM and PGC. Finally, SubRep stores subscription information and is accessible by SDC and MON.

It may render a vendor-customized user interface if a custom template is provided. The user interface is web-based and is rendered by XSLT (http://www.w3.org/TR/xslt) technique. CSS repositories There are five repositories in CSS: data repository (DataRep), home device repository (DevRep), service and operation repository (SORep), policy/goal/constraint repository (PGCRep), and subscription repository (Sub-Rep).

Table 2 .

 2 Policy example for optimized laundry in formal notations # Policy specifications 1 dynamic variables: weather(tc, t latest ) and prices(tc, t latest ) constraints: t od,start + drytime(t od,start ) ≤ t latest actions: start wm at twm,start and start od at t od,start such that 0 ≤ t od,start -(twm,start + t wash ) ≤ 1h and t od,start + drytime(t od,start ) ≤ t latest and c(twm,start) < c(t) ∀t ∈ T -twm,start, T = {tc, tc + 1, ..., t latest } cost: c(t) = wwm × t wash × p(t, t + t wash ) 2 dynamic variables: weather(tc, t latest ) and prices(tc, t latest ) constraints: t ed,start + t edry ≤ t latest actions: start wm at twm,start and start ed at t ed,start such that 0 ≤ t ed,start -(twm,start + t wash ) ≤ 1h and t ed,start + t edry ≤ t latest and c(twm,start, t ed,start ) < c(t1, t2) ∀(t1 ∈ T -twm,start, t2 ∈ T -t ed,start ), T = {tc, tc + 1, ..., t latest } cost: c(t1, t2) = (wwm × t wash × p(t1, t1 + t wash )) + (w ed × t edry × p(t2, t2 + t edry ))

	c	represents currrent hour
	t [device],start	represents start time of the device
	t [device],end	represents end time of the device
	t latest	represents latest finish time
	t wash	represents washing duration (hour)
	t edry	represents drying duration by electric dryer (hour)
	w [device]	represents power consumption by device (kW)
	weather(t 1 , t 2 ) represents a set of weather conditions from t 1 to t 2
	prices(t 1 , t 2 )	represents a set of electricity prices from t 1 to t 2
	p(t 1 , t 2 )	represents average electricity price from t 1 to t 2

Summary and conclusion

Residential consumers contribute to a substantial amount of electricity consumption. Energy consumption pattern can affect the stability of the grid. Home Energy Management System (EMS) can assist household inhabitants in operating home devices to optimize energy usage. This paper proposes an architecture model and a functional framework for Home EMS with focus on simplicity and scalability to enable the system's rapid deployment. Energy management is carried out by a central system whose functions are realized by a combination of EFSMs and a policy-based reasoning machine. Our proposal to use policy-based reasoning offers an advantage to cope with changes in variables and simplifies incorporation of new energy management solutions as new policies. In addition, a Home EMS inter-working framework based on RDF and JSON was also proposed. Data representation with RDF provides the necessary semantics and enables harmonization with existing standards while JSON messages can be constructed by most microcontrollers. We are currently working on the construction of more energy management policies to cover broader aspects including indoor temperature adjustment and load scheduling involving more devices. A prototype system based on the proposed functional and inter-working frameworks will be implemented. The prototype will also be used as a platform to evaluate the effectiveness of the constructed policies with respect to electricity cost saved by consumers and the reduction of peak loads.


Jonas Wäfler
email: jonas.waefler@item.ntnu.no

Poul E Heegaard
email: poul.heegaard@item.ntnu.no

Interdependency Modeling in Smart Grid and the Influence of ICT on Dependability

The smart grid is a complex system consisting of interdependent power grid and information and communication (ICT) components. Complex systems have different properties than simple networks and give raise to new risks and failure types. In this paper, we study the dependencies in smart grid and the influence ICT may have on the dependability. We start with giving a categorization of the smart grid components and define state machines for these categories and for smart grid services. Then we investigate their interactions and interdependencies from a dependability perspective. Further, we investigate the positive and negative effects ICT can have on the dependability of the system. Finally, we introduce a meta-model which incorporates the information about the states of the components and services to create a state estimator for the smart grid considering ICT and power components.

Introduction

The reliability analysis of power grids has traditionally not included the state of supporting information and communication technology (ICT) infrastructure [START_REF] Kirschen | Keeping the lights on and the information flowing[END_REF][START_REF] Bose | Models and techniques for the reliability analysis of the smart grid[END_REF][START_REF] Singh | Reliability assurance of cyber-physical power systems[END_REF]. However, in the last ten years several authors pointed out the need of studying the power grid as complex network by including the cyber or ICT part in the analysis [START_REF] Kirschen | Keeping the lights on and the information flowing[END_REF][START_REF] Amin | National infrastructure as complex interactive networks[END_REF][START_REF] Little | Toward more robust infrastructure: Observations on improving the resilience and reliability of critical systems[END_REF]. This complex network is called cyber-physical system or more general system of systems.

Theoretical results indicate the importance of analyzing the power grid (PG) and its supporting ICT together in one common model as a system of systems. It has been shown for interdependent random graphs that system of systems have different properties than simple systems [START_REF] Buldyrev | Catastrophic cascade of failures in interdependent networks[END_REF]. Additionally, with an increasing number of interconnections and therefore a higher interdependency between the systems the vulnerability to random failures increases also [START_REF] Parshani | Critical effect of dependency groups on the function of networks[END_REF].

A classification of particular types of failures which are caused by the interdependency of systems is put forward by [START_REF] Rinaldi | Identifying, understanding, and analyzing critical infrastructure interdependencies[END_REF]. Failures are classified as cascading, escalating and common cause failures depending on the interaction of the systems. Studies of major power grid incidents show that these interdependency effects between the PG and the ICT already exist in the current power grid [START_REF] Buldyrev | Catastrophic cascade of failures in interdependent networks[END_REF][START_REF] Andersson | Causes of the 2003 major grid blackouts in north america and europe, and recommended means to improve system dynamic performance[END_REF][START_REF] Xie | An information architecture for future power systems and its reliability analysis[END_REF]. A chain of cascading failures, i.e. failures in one system that trigger failures in another system, was a major reason for the large blackout in Italy in 2003 [START_REF] Buldyrev | Catastrophic cascade of failures in interdependent networks[END_REF]. And an escalating failure, i.e. independent failures in the systems that amplify each other, was an important reason why the blackout in the US in 2003 could become so large [START_REF] Andersson | Causes of the 2003 major grid blackouts in north america and europe, and recommended means to improve system dynamic performance[END_REF]. Another analysis of the disturbances in the US power grid from 1979 to 1995 found that "problems in real-time monitoring and operating control system, communication system, and delayed restoration contribute to a very high percentage of large failures" [START_REF] Xie | An information architecture for future power systems and its reliability analysis[END_REF]. The smart grid will rely even stronger on ICT than the legacy power grid, therefore, it can be expected that these effects will become even stronger.

The smart grid has the potential to increase the reliability of the power supply with new services like self-healing and demand response, which may reduce downtime and increase dependability [START_REF] Vadlamudi | Challenges in smart grid reliability studies[END_REF]. However, misbehaving ICT and interdependency effects between ICT and PG have to be analyzed carefully and included into the dependability analysis, otherwise the results may be inaccurate and could lead to false conclusions about the system.

An interdependency model for the electricity and information infrastructure was presented in [START_REF] Laprie | Modelling interdependencies between the electricity and information infrastructures[END_REF]. Using four to five different states for both infrastructures the model accommodates the three new failure types of system of systems as described in [START_REF] Rinaldi | Identifying, understanding, and analyzing critical infrastructure interdependencies[END_REF]. The model contains interesting features like passive and active latent errors; however, it is very high-level and the repair is not covered in details. Both power grid and ICT components are repaired in one step at the same time.

In 2009 an interdependency model for the power grid was put forward to illustrate the effect ICT can have on the reliability of the whole power grid [START_REF] Kirschen | Keeping the lights on and the information flowing[END_REF]. In this model, both ICT and PG have a binary state variable and can either be in a normal or abnormal state leading to a four state model. The model is very conceptual and concentrates mostly on the transitions. Because of the high abstraction level most details are hidden within the states.

A more detailed approach is taken by [START_REF] Zhang | An overall reliability and security assessment architecture for electric power communication network in smart grid[END_REF] by introducing a three-level assessment hierarchical architecture consisting of a device, network and service level. Each level has its own properties and is modeled individually.

In this paper, we start bottom-up with the components constituting the smart grid and give a categorization based on their use of ICT. We then give state machines for the components and services and explain their interactions from a dependability perspective. Further, we discuss the positive and negative effects ICT can have on the dependability of the system. Finally, we introduce a metamodel which incorporates the information about the states of the components and services to create a state estimator for the smart grid considering ICT and power components.

Components and Services in the Smart Grid

The power grid consists of the power infrastructure on the one hand and of intelligent devices and a communication infrastructure to control and monitor it on the other hand. We categorize all components of the power grid into five categories as shown in Fig. 1. Category A contains power components with no communication means and no software like power lines and mechanical power devices. Category B contains power components that are configurable but run autonomous and have no communication means like certain distributed energy resources. Category C contains software controlled power components with communication means like intelligent electronic devices used for monitoring and controlling the power grid. Category D contains software controlled communication components like routers. Category E contains communication components with no software like communication cables. It is important to note that some devices can be in several categories like a power cable which is also used as carrier of a PLC (power line communication) signal. Such structural dependencies can be the cause for common cause failures.

Devices in the categories B, C and D are in the following called intelligent devices. Components in A and E are called hardware (HW) components. Power HW components like power lines and transformers build the physical connections in the power grid between production sites and loads. The intelligent devices and the communication HW components are needed to operate the whole grid.

Smart grid services run on top of these components and they need a certain subset of components and other smart grid services to work. This partial dependency is called in the following structural dependency. The services are used to operate the power grid and include power delivery, monitoring, control, protection and more advanced services like demand response.

The biggest change in the transition from the legacy power grid to the smart grid will lie in the increase of software capabilities of B and C components and the quantitative increase of C components. In other words, the components become more intelligent and there will be more intelligent electronic devices to increase the system awareness and control, especially in the distribution grid. The latter will also lead to an increase of D and E devices in the smart grid. Additionally, the transition to the smart grid will change the power grid services. On the one hand, they are extensions to existing services like an increased monitoring and controlling in the distribution grid. On the other hand, they introduce new functionalities like smart metering or demand response.

State Machines for Components and Services

In the following we present state machines for components and services. The states are on a high level and different failure modes are not differentiated. For a quantitative analysis separate states for the considered failure modes have to be created and transition rates or probabilities assigned to the transitions.

Hardware components are modeled with two states as seen in Fig. 2. They can either be in a working state ok or a failed state F. Repair can happen after the monitoring system detected a failure or it can happen before when the failure is only temporary and disappears on its own. Intelligent devices on the other hand, have a more complex failure behavior. First, we differentiate between errors and failures, as described in [START_REF] Avizienis | Basic concepts and taxonomy of dependable and secure computing[END_REF]. A fault can trigger an error in a device but only when the provided service is incorrect it becomes a failure. Differentiating errors and failures allows for example to model intermittent failures. While the failure disappears for some time, the responsible error does not. Second, a failure may be either passive (F p ) or active (F a ), depending on their behavior. We use the following definition similar to [START_REF] Laprie | Modelling interdependencies between the electricity and information infrastructures[END_REF]: passive failure: The device works incorrectly in a passive way, i.e. it does not respond when needed (e.g. not sending monitoring data, not responding to a control signal, not triggering a breaker when needed). active failure: The device works incorrectly in an active way, i.e. it functions but not as intended (e.g. sending wrong monitoring data, executing the wrong control command, triggering self-healing when not necessary).

The corresponding errors are accordingly termed passive errors (E p ) and active errors (E a ). A device may also directly change its state from ok to F p for example if parts of the hardware fail.

The devices are controlled by highly capable software which may cause harm to the system if working incorrectly. Due to the potential complexity of designing, configuring and updating such devices, faults are likely and errors may reside undiscovered in a device for a long time. Faults can be unintentional like design and configuration faults but also intentional like viruses/worms, intrusions and sabotage. Design, configuration or maintenance errors like software bugs, erroneous configuration/reconfiguration or the distribution of a faulty software update will affect potentially many devices at the same time. Failures may propagate on their own like in the case of a virus or a worm. The degree of the spreading depends on the detection and repair time.

The state of smart grid services may depend on the working and operational state of certain components, their structural dependencies, other services and on the input or the situation the system is in. The working states of a component are the states described above, the operational states are states in normal operation which can have an influence on a service. For example an open breaker which was opened by an undetected failure in an IED may cause the disconnection of parts of the grid and a state change for a service. The reason for the state change is the operational state of the breaker and only indirectly a failure. A service is said to be in the failed state F if the service produces incorrect output. If components fail which are necessary to create correct output but the output itself is not yet incorrect, then the service is in the error state E. For example, consider a protection service which is responsible for opening breakers in a high overload situation. This service relies on protection devices installed throughout the power grid. The failure of one of these devices is already critical if there are no redundant devices. However, as long as there is no overload in which this specific device is needed to operate the service does not produce wrong output, hence the service is in the error state E while the device itself is in a failed state. In the error state the failure probability is much higher than in the working state. It is not the same as a failed state because for dependability analysis this state is considered as not failed. The monitoring system may detect the device failure and initiate the repair before the service fails.

Interactions

The components and services are highly depending on each other. The transitions between the states depend theoretically on the state of all the other components and services at a given time. For practical analysis of large systems the states may be modeled as depending only on the state of a subset of all components and services which are either geographically or logically close. In the following, we discuss the influence components can have on other components or services depending on their states.

Influence of HW Components

F A failure may increase the load on other HW components and the probability for them to fail. This is especially the case for power HW components. Intelligent components may fail if a power HW component fails and there is no other power source (transition into F p ).

Influence of Intelligent Devices

E a and E p Errors have by definition no effect on other components. F a An active failure may cause a change in the operational status in another component, e.g. opening a breaker, increasing power production instead of decreasing. This may lead to a critical situation and eventually even to a hardware failure or a service failure. An active failure may also cause errors and failures in other ICT components, e.g. by spreading harmful configuration or virus. It can also cause a smart grid service to not function properly. F p A passive failure may cause a smart grid service to not function properly because for example necessary information is not delivered or information is not received and processed by the component. A passive failure may also lead to a failure in a power grid HW component, e.g. by not alarming the control center about a critical situation which could lead to an overload failure.

Influence of Services

E An error has by definition no effect on other components or services. F A failure can cause problems for the components or services relying on the output of this service. It may provoke a critical situation end eventually even to a failure in a component. For example, if the service demand response is increasing the loads instead of decreasing. If this happens in a distribution grid with a high number of charging electrical vehicles it could lead to an overload in that particular area and eventually even to a blackout, i.e. a failure of the power delivery service.

Perception of Components and Services

The monitoring system has its own perception of the system which is not the same as the actual state of the system. This is because the monitoring system is also just a service which can fail. The monitoring system can either indicate failure or no failure. The error states are considered as no failure as the delivered service is per definition still correct. As shown in Fig. 2 the indication can be wrong, i.e. be a false positive if a failure is indicated when there is none or be a false negative if no failure is indicated when there is indeed one. The deviation of the indication in the monitoring system from the actual state is critical. If false positives are frequent it may cause high costs for the clarification of the cause and eventually to a loss of trust. False negatives may prolong the time a component or service stays in the failed state which decreases the dependability of the system. The longer a component is in the failed state the longer the negative interactions described above take place and more state changes in other components may happen.

Techniques for Quantitative Analysis

A difficulty when modeling the smart grid for quantitative analysis is that it consists of dynamic parts, i.e. the components with their state machines, and structural parts, i.e. the structural dependencies between services and components. This becomes clearer when considering the smart grid services. The working and failed state of a given service may be described by a fault tree, where the events are failures of components or other services. This fault tree represents the structural dependency of the given service. The dynamic parts are the different failure modes leading to the events, i.e. failure of components or services.

A straight forward way of quantitatively analyzing a service is by creating markov models for each individual component and computing with them the dependability parameters needed for the fault tree. In this way, both availability and reliability of a service can be computed. However, this method assumes all events or state changes to be independent which is a very strong assumption and usually not true in real systems.

A way of including dependencies between components in an analytical model has been proposed in [START_REF] Wäfler | A combined structural and dynamic modelling approach for dependability analysis in smart grid[END_REF]. It starts with a reliability block diagram, i.e. a structural model which is equivalent to a fault tree and has the same independence assumption. The dependencies are then included by either isolating them or by using a combination of pivotal decomposition and markov chain. This method is most useful if the number of dependent components is small.

Another solution is to use a stochastic reward net (SRN) [START_REF] Muppala | Stochastic reward nets for reliability prediction[END_REF] which is an extension of a stochastic Petri net. The state machines from Fig. 2 can be used as a basis for the SRN in which the individual components and services are modeled as tokens. The transitions in SRN may be enabled by boolean functions on the markings of states and the transition rates may also depend on the marking of states. This allows to create a small model for a complex problem. However, this holds only if the components or services are treated as anonymous. If the identity of the different components and services become important, the model becomes more complex as well.

If the two mentioned methods are unpractical then a simulation may also be used for quantitative analysis.

Role of ICT in the Smart Grid

ICT components and services have a large potential for supporting the operation of a smart grid and increasing its dependability. The software part allows for smarter decision making processes and the communication allows for sharing information. Both are important for the most fundamental services: monitoring and controlling. An optimal monitoring system shows the actual state of the system with as little delay as possible and minimizes the discrepancy between perceived and real state. Precise data can help to operate the system in an optimal state and reduce errors and failures in the first place. For example, exact monitoring data in the distribution grid may optimize its use, maintenance and replacement, i.e. not wasting capacity or wearing the infrastructure unnecessarily out and preventively initiate repair or replacement before an incident happens. In case of a failure the monitoring service helps to detect and localize the failure. The reparation time may also be shortened by finding an optimal repair strat-egy, by self-healing or by enabling the repair or mitigation by remote control, e.g. by isolating a line failure and possibly reconnect disconnected loads by an alternative route to reduce the impact of the failure.

By aggregating the data from the components new insights can be gained. For example, by finding patterns for failures which might improve error and failure prevention or failure detection. With a wide-area monitoring and control, enabled by communication, the optimal strategy for operation can be found for a certain area or the whole grid and not only for the local component. In case of an incident a coordinated protection or isolation scheme may prevent a propagation of the failure in the system.

While ICT can help to improve dependability, it can also have a negative effect. Passive failures in monitoring lead to a mismatch between perception and reality. A critical situation or failure may not be detected due to the missing data. In a controlling service a passive failure in a component leads to the disregard of the control signal. If no acknowledgment message is used this stays undetected and a mismatch between the assumed state of the component and the real state arises.

Passive failures reduce the potential improvement of ICT. The total failure of an ICT service nullifies its effect and intuitively one may conclude that additional ICT services will either improve the dependability of the whole system or at least keep the status quo. However, this is a dangerous conclusion because of two reasons. First, if services or controllers blindly rely on the service a passive failure may have a worse effect as not having the service at all. In the former case there is a strong assumption that the service works correct, in the latter case there is no correctness assumption and nobody is left with a false sense of security. Second, active failures may trigger new failures which would not exist without the specific service or ICT component.

Active failures in monitoring lead to a mismatch between perception and actual state and eventually even to undesired decisions and actions. For example, wrong information about the status of a breaker or the load of a line can trigger the isolation of a power grid part and lead to an unnecessary outage. Active failures in controlling lead also to a mismatch of perception and actual state but have in addition a direct effect on some components. Examples are protection devices initiating a protection process, breakers opening or closing, or the sending of wrong control signals. Frequent active failures of ICT components may negate the positive effect ICT can have and lead to an overall negative effect.

Last but not least, ICT plays a big enough role in the smart grid to qualify it as system of systems, which have particular interdependency effects and failure types, i.e.Cascading Failure, Escalating Failure, and Common Cause Failure [START_REF] Rinaldi | Identifying, understanding, and analyzing critical infrastructure interdependencies[END_REF].

Aggregated view for the Control Center

In the legacy power grid the control centers for the power grid and the communication system are usually separated. However, as new failure paths emerge in the smart grid which originate in or include ICT components, it becomes crucial to incorporate the information of both into the state estimation of the whole smart grid. This allows an early detection of possible failures coming from the ICT components.

In the following, we propose a meta-model to describe the state of the whole system for the control center. The meta-model is an aggregation and interpretation of the information from the monitoring system to determine the criticality level of the system. It has two axis using the states of the power grid (PG) and the ICT, see Fig. 3. The most important service in the power grid is the power delivery to the customers. The state of this service plus the state of supporting components are used to determine the power grid (PG) state. On the other hand, the states of ICT components and services are used together with a logic which indicates which services are critical to determine the state of the ICT system.

The model follows a service-centric approach. Failure means a service is not delivered correctly and action has to be taken immediately. Excited means that the service may run soon into a critical situation. More detailed, the states of the two axis are defined as:

PG ok: The system operates normally. PG Excited: All customers are powered but the system is excited (N-1 redundancy is harmed, the load is critical, etc.) PG Failure: At least one customer is disconnected from the power supply. ICT ok: The ICT system operates normally.

ICT Excited: All critical ICT services are delivered correctly but the system is excited (non-critical components failed, congestion in the system) ICT Failure: Some critical ICT services are incorrectly delivered.

The nine states are then created by the intersections of this two axis. Both excited states denote states of the system where the corresponding system is still working correctly but the stability and robustness is decreased. They are a key factor in the meta-model because the system may be much weaker than in the failure-free state and failures may propagate.

The states are as perceived by the control center and can be wrong as discussed above. These monitored states should be as close to the real states as possible. The fast detection of failures reduces the risk that the failure can propagate or cascade to other components. Monitoring should also be reliable to reduce the risk of having false positives and false negatives.

The meta-model is a highly condensed view of the whole grid to create a clear and easy understandable warning system. Due to the aggregation it is highly scalable. In large systems or in presence of autonomous structures like micro grids it may be useful to use several meta-models.

Applications

The primary application for the proposed meta-model is the state indication of the smart grid for the control center as explained above. However, there are additional applications.

In ex post incident analysis the meta-model can be used to show the basic cause and effect chains in a clear way and study alternative scenarios. In Fig. 4 we give an example of such an analysis by showing the events of an escalating failure in the US in 2003 [START_REF] Andersson | Causes of the 2003 major grid blackouts in north america and europe, and recommended means to improve system dynamic performance[END_REF]. In short, several generators had an outage, which led to a tripping of several lines. When that happened, the energy management systems (EMS) of the two responsible network operators were not fully functional and the failure could propagate in the PG and ended in a voltage collapse and a blackout spanning several federal states. In the figure, the black disks indicate the information the control center had during the events. The control center knew about the reduced functionality of the EMS but did not learn about the outage in the power grid until it was too late. The white disks indicate the information the control center would have had if the monitoring system had worked. The first outage could have been detected and the failure perhaps isolated which could have stopped the chain of events.

As an extension of the ex post incident analysis the meta-model can also serve as a tool to visualize and illustrate interdependencies in two systems. The new failure types propagation, escalation and common cause failures can be explained in an intuitive way and new failure paths are revealed.

Conclusion

The wide introduction of ICT changes the way the smart grid may fail. It is necessary to consider the states of both the ICT and the PG in the dependability analysis due to the following reasons:

-Dependability analysis for smart grid services yield inaccurate results if the possible non-functioning or malfunctioning of ICT is not included. ICT can have special dynamics like failure propagation within the system and active latent errors, which can have a strong effect on the smart grid. -ICT plays a big enough role in the smart grid to qualify it as system of systems, which introduces particular interdependency effects and failure types.

In individual models it is difficult to include those.

In this paper we categorized the smart grid components and services and showed the interactions between them. We motivated that their state and especially the state of the ICT components and services will play an important role in the dependability analysis of smart grids. We proposed a meta-model which takes this into account and combines the states of ICT and power grid components and services. It can be used as a tool for the control center to estimate the state of the smart grid. The proposed meta-model facilitates the understanding of the mechanisms of previous incidents by tracing their trajectories in the model. The simple structure creates an intuitive model that allows explaining the interdependencies and new failure types that are created by connecting systems. Understanding the risks is the first step to make a system more dependable and secure.

This work is meant to generally describe dependencies in the smart grid and to create a basis for future work. Future work will focus on specific interactions and interdependencies of components and services. We are especially interested in studying the new failure modes and evaluating and quantifying the dependability effects of new smart grid services.

Fig. 1 :

 1 Fig. 1: Services and components of smart grids.

Fig. 2 :

 2 Fig.2: State machines for components and services and the perception of their state in the monitoring system.

Fig. 3 :

 3 Fig. 3: Meta-model for smart grid.

Fig. 4 :

 4 Fig. 4: Events in ICT and PG during an escalating failure in the US in 2003 as seen by the control center. The black disks indicate the information about the events as it happened. The white disks show how it could have been with a working detection mechanism, may be stopping the chain after event 1 or 2.