Didier Dubois
email: dubois@irit.fr

Henri Prade
email: prade@irit.fr

Gilles Richard
email: richard@irit.fr

Multiple-valued extensions of analogical proportions

Keywords: Multiple-valued logic, Analogical proportion, Similarity, Dissimilarity, Interpolation

This paper provides a discussion of different multiple-valued extensions of logical expressions of analogical proportions that are equivalent in the Boolean case. It is advocated that these extensions may serve different goals, or at least reflect different views. Boolean expressions of analogical proportions, modeling statements of the form A is to B as C is to D, are first restated and commented. An approach to handling the case of binary attributes that may not apply in the Boolean setting is also outlined via a proper encoding.

Introduction

Comparing situations, a core step in reasoning processes, is often a matter of assessing similarities and dissimilarities, which may be a matter of degree. This has motivated fuzzy logic-based works in case-based reasoning [START_REF] Dubois | Fuzzy set-based methods in instance-based reasoning[END_REF][START_REF] Hüllermeier | Case-Based Approximate Reasoning[END_REF] but also in approximate reasoning [START_REF] Zadeh | A theory of approximate reasoning[END_REF], although with different approaches. The works by Francesc Esteva are in part dedicated to this kind of topic. In particular, some were published in joint papers with the two first authors of this note on fuzzy case-based reasoning [START_REF] Dubois | Fuzzy set modelling in cased-based reasoning[END_REF], and on interpolative reasoning [START_REF] Dubois | A logical approach to interpolation based on similarity relations[END_REF][START_REF] Perfilieva | Interpolation of fuzzy data: analytical approach and overview[END_REF]. More recently, the two last authors of this note have devoted a significant effort to the development of a formal logic approach to analogical reasoning [START_REF] Miclet | Handling analogical proportions in classical logic and fuzzy logics settings[END_REF][START_REF] Prade | Multiple-valued logic interpretations of analogical, reverse analogical, and paralogical proportions[END_REF].

Analogical proportions are statements of the form A is to B as C is to D, often denoted A : B :: C : D, where the comparison made between situations A and B is balanced against the comparison made between situations C and D. One may think of these situations as described by vectors of Boolean or graded attribute values. This kind of pattern for analogy has been already implicitly at work in fuzzy set-based approximate reasoning [START_REF] Turksen | An approximate analogical reasoning schema based on similarity measures and interval-valued fuzzy sets[END_REF][START_REF] Subašić | Similarity rules and gradual rules for analogical and interpolative reasoning with imprecise data[END_REF][START_REF] Bouchon-Meunier | A fuzzy approach to analogical reasoning[END_REF] and is also at the root of case-based reasoning [START_REF] Dubois | Case-based and analogical reasoning[END_REF]. In the numerical case, the analogy principle is typically rendered by the equality a b = c d . However, it is only recently that a rigorous notion of logical proportion, leading to a sound logical formula for A : B :: C : D in terms of Boolean attributes has been proposed (see [START_REF] Prade | From analogical proportion to logical proportions[END_REF] for an overview).

Table 1 The six Boolean patterns for which an analogical proportion is true.

0 0 0 0 1 1 1 1 0 0 1 1 1 1 0 0 0 1 0 1 1 0 1 0
The aim of this note is to review the logical approach to analogical reasoning developed by the second and third authors, and to discuss the potential merits of many-valued extensions of several logical expressions of analogical proportions that are equivalent in the Boolean case. These propositional logic expressions are first recalled in Section 2. Section 3 discusses the handling of the case of binary attributes, in the case when they may not apply to all situations. Then Section 4 is devoted to two different many-valued extensions of the Boolean analogical proportions, when attribute values are assumed to be precisely known.

The Boolean expressions of analogical proportion

Let us consider the case where situations or objects A, B, C, and D are described in terms of binary attributes (i.e. that are either true or false). Let us focus on a particular Boolean attribute or predicate X of interest, and let a, b, c, d (the values of) the respective Boolean variables pertaining to this attribute in each of the four situations A, B, C, and D that is, a = X (A), b = X (B), c = X (C), d = X (D). In the following, a Boolean variable, or its value, are denoted in the same way, as far as this abuse of notation does not create any confusion.

Properties of the analogical proportion

In the classical logical setting, an analogical proportion can be viewed as a quaternary connective linking four Boolean variables a, b, c, and d, which will be denoted a : b :: c : d, as first proposed in [START_REF] Miclet | Logical definition of analogical proportion and its fuzzy extensions[END_REF][START_REF] Miclet | Handling analogical proportions in classical logic and fuzzy logics settings[END_REF]. Then, an analogical proportion holds between four situations A, B, C, and D, i.e. A : B :: C : D, if and only if the analogical proportion a : b :: c : d holds true for each of the binary attributes used for describing the situations.

The following properties describe the logical behavior of the analogical proportion [START_REF] Prade | From analogical proportion to logical proportions[END_REF]: Although analogical proportions had not been thought of in a logical way until recently, these properties have been always associated to the idea of analogical proportion since Aristotle time [START_REF] Dorolle | Le Raisonnement par Analogie[END_REF][START_REF] Prade | From analogical proportion to logical proportions[END_REF], as these properties are true for numerical ratios. Thus, it is natural that these properties should hold for a : b :: c : d as well.

Thus in particular, by reflexivity and central permutation, a : b :: a : b and a : a :: b : b should be tautologies. This means that in the truth table of a : b :: c : d, the 6 patterns given in Table 1 makes it true. Moreover, a : b :: c : d should be false for the 10 other quaternary patterns (among the 2 4 = 16 possible ones). These 10 other patterns are of two kinds:

• (1, 0, 0, 1) and (0, 1, 1, 0) that are certainly undesirable since accepting them as making the analogical proportion true would lead to admit that A : B :: C : D entails B : A :: C : D, which sounds strange; • the 8 patterns are those with an odd number of '1's or '0's such as (1, 0, 0, 0) or (0, 1, 1, 1). They express the idea that one among a, b, c, d is different from the three others, which has nothing to do with the statement a is to b as c is to d.

It can be easily checked that beyond reflexivity, symmetry and central permutation, the following properties hold for a : b :: c : d defined by truth The first equivalence is the permutation of the extremes and derives from symmetry and central permutation in any setting. The second property, derivable from the three basic properties in the Boolean setting [START_REF] Prade | From analogical proportion to logical proportions[END_REF], is also important since it expresses some invariance with respect to encoding (it is the same to describe a situation in terms of a property or of its negation).

As can be easily seen on the patterns of Table 1, when the analogical proportion a : b :: c : d holds true, either the truth pattern for (a, c) is the same as the one for (b, d) (4 patterns among 6), or the truth change from a to b goes along with a change in the same direction (from true to false, or from false to true) from c to d. In particular, a : b :: c : d is false for the patterns (1, 0, 0, 1) and (0, 1, 1, 0); it is also false for the 8 patterns with one '1' or one '0' such as (1, 0, 0, 0) or (0, 1, 1, 1).

The logical expressions for analogy

A logical expression corresponding to the truth Table 1 has been first proposed in [START_REF] Miclet | Logical definition of analogical proportion and its fuzzy extensions[END_REF][START_REF] Miclet | Handling analogical proportions in classical logic and fuzzy logics settings[END_REF]. It defines what a : b :: c : d logically means: The central and extreme permutation properties are easy to see on the truth table, while they are not obvious on Eq. (1) (while symmetry is patent). In particular, these permutation properties do not hold separately on each of the two sides of the external conjunction, i.e. a ∧ ¬b ≡ c ∧ ¬d and a ∧ ¬c ≡ b ∧ ¬d do not have the same truth tables.

a : b :: c : d = (a ∧ ¬b ≡ c ∧ ¬d) ∧ (¬a ∧ b ≡ ¬c ∧ d) (1)
Finally, the above expression of the logical proportion can be equivalently written using material implication and conjunction only as [START_REF] Miclet | Logical definition of analogical proportion and its fuzzy extensions[END_REF][START_REF] Miclet | Handling analogical proportions in classical logic and fuzzy logics settings[END_REF]:

a : b :: c : d = (a → b ≡ c → d) ∧ (b → a ≡ d → c), (2)
which means that we can reason from c to d and back, just as we do from a to b and back. Note that the truth of (a → b) → (c → d) comes down to the license to deduce d from the rule a → b and the fact c (this is the principle of the so-called "triple I method" [START_REF] Wang | Unified forms of triple I method[END_REF]). Under this view, the logical expression of analogy looks stronger than usual inference, since it comes down to the above license to deduce d from the rule a → b and the fact c, plus three other inferences (of b from c → d and a, and likewise of a and c using the right-hand side of the pattern (2)). There exists another remarkable, equivalent expression of the analogical proportion [START_REF] Miclet | Handling analogical proportions in classical logic and fuzzy logics settings[END_REF] where the permutation properties are obvious (as well as symmetry). Namely

a : b :: c : d = (a ∧ d ≡ b ∧ c) ∧ (¬a ∧ ¬d ≡ ¬b ∧ ¬c) (3)
As can be seen, this expression focuses on similarities, while expression (1) focuses on dissimilarities. Indeed a ∧ d and ¬a ∧ ¬d are positive and negative similarity indicators respectively [START_REF] Prade | From analogical proportion to logical proportions[END_REF]. Thus, Eq. (3) reads A is to B as C is to D if and only if A and D are similar just as B and C are (on the considered attribute). This is not so obvious a translation of the idea of analogy since the latter usually expresses that A compares to B just as C compares to D, an idea better captured by expression [START_REF] Barbot | Analogical proportions and the factorization of information in distributive lattices[END_REF]. Moreover it is straightforward to see that Eq. ( 3) can be rewritten equivalently without negation but using disjunction:

a : b :: c : d = (a ∧ d ≡ b ∧ c) ∧ (a ∨ d ≡ b ∨ c) (4)
Interestingly enough, this expression was precisely considered by Piaget [START_REF] Piaget | Logic and Psychology[END_REF] as defining the idea of logical proportion (applicable not only on atoms, but on any 4-tuple of propositional formulas). He viewed it as a counterpart of the idea of numerical geometric1 proportions (since a b = c d if and only if a × d = b × c), although he apparently never made any connection with the idea of analogical proportion.

Remark 1.

Recently, an expression of the analogical proportion as a disjunction of two conjunctions of equivalences has been also noticed [START_REF] Miclet | Analogical proportions and square of oppositions[END_REF]:

a : b :: c : d = ((a ≡ b) ∧ (c ≡ d)) ∨ ((a ≡ c) ∧ (b ≡ d)). (5)
This expression directly compares a, b, c, d and does not use dissimilarity or similarity indicators as in (3) (or ( 4)).

It may seem less appropriate with respect to the intended meaning of an analogical proportion. However, reflexivity, symmetry, central permutation, and invariance with respect to encoding are easy to check on (5).

A set-theoretic view

The apparent discrepancy between the expressions (1) and ( 3) of the analogical proportion a : b :: c : d can be better understood through a set-theoretic, equivalent view of the analogical proportion, due to [START_REF] Stroppa | Analogical learning and formal proportions: definitions and methodological issues[END_REF]. As already said, a : b :: c : d can be true only for the six patterns of Table 1. Consider the set-theoretic counterpart of (1), that is, interpret A, B, C, D as the subsets of models of the Boolean variables a, b, c, d respectively. Then, (1) reads:

(A \ B = C \ D) and (B \ A = D \ C) Introduce the sets • X = A \ B = C \ D, Y = B \ A = D \ C; • U = A ∩ B ∩ C ∩ D, Z = (A ∩ B) \ (C ∩ D), T = (C ∩ D) \ (A ∩ B), and finally V = A ∩ B ∩ C ∩ D.
Then it is clear that X, Y, Z, Y, U, V form a partition of the whole set of interpretations of the language, , and

A = X ∪ Z ∪ U, B = Y ∪ Z ∪ U, C = X ∪ T ∪ U, D = Y ∪ T ∪ U.
Then it is easy to check that under these constraints, the set-theoretic-counterpart of (3) holds, that is:

A ∩ D = B ∩ C = U and A ∩ D = B ∩ C = V . (6)
Hence,

A ∪ D = X ∪ Y ∪ Z ∪ T ∪ U = B ∪ C
, which lays bare the link between expressions (1) and ( 4). The setting in [START_REF] Stroppa | Analogical learning and formal proportions: definitions and methodological issues[END_REF] is in fact the one of a Boolean table with objects A, B, C, D, etc., in lines, and properties X i , i = 1, . . . , n, in columns. And A, B, C, D are then understood as the subsets of Boolean properties that hold true for each of the four respective objects (or situations). So letting a i = X i (A), etc. The analogy pattern A : B :: C : D stands for a i : b i :: c i : d i , i = 1, . . . , n, which can be denoted by (a 1 , . . . , a n )

: (b 1 , . . . , b n ) :: (c 1 , . . . , c n ) : (d 1 , . . . , d n ).
Hence, for instance, Z (resp. T ) is the set of properties that hold both in situations A and B (resp. C and D), and do not in situations C and D (resp. A and B). The last expression [START_REF] Dubois | A logical approach to interpolation based on similarity relations[END_REF] clearly means that the properties common to A and D are those common to B and C, and likewise for their missing properties.

These different views of the analogical proportion are all equivalent in the Boolean setting. It is no longer the case when we consider their possible extensions for handling numerical attributes, as explained in the rest of this paper, where we provide a comparative discussion of the merits of the two main existing options, based on previous results [START_REF] Prade | Multiple-valued logic interpretations of analogical, reverse analogical, and paralogical proportions[END_REF][START_REF] Prade | Analogical proportions and multiple-valued logics[END_REF]. However, we first revisit the case of attributes that may not be applicable to some situations.

Beyond Boolean analogical proportions: attributes that may fail to apply

Binary attributes may fail to be applicable to all objects or situations. In this situation, some propositions are neither true nor false. This is captured by some kind of null-values in databases for instance. A multiple-valued logic modeling has also been recently proposed to handle the adaptation of analogy patterns to this case [START_REF] Prade | Analogical proportions and multiple-valued logics[END_REF]. It is indeed tempting to introduce a third truth value meaning "not applicable" (denoted by na for short), leading to a truth table with 3 4 = 81 lines. Then it may seem to be intuitively appealing to acknowledge that all patterns of the form (s, s, s, s), (s, s, t, t) and (s, t, s, t) where s, t ∈ {0, 1, na} satisfy a : b :: c : d. It consists of 15 patterns:

(1, 1, 1, 1), (0, 0, 0, 0), (na, na, na, na), (1, 0, 1, 0), (0, 1, 0, 1), (1, na, 1, na), (na, 1, na, 1), (0, na, 0, na), (na, 0, na, 0), (1, 1, 0, 0), (0, 0, 1, 1), (1, 1, na, na), (na, na, 1, 1), (na, na, 0, 0), (0, 0, na, na), while all the 81 -15 = 66 other patterns built from the set {na, 0, 1} will be considered as making a : b :: c : d false.

Extensions of definitions ( 1) or (3) with suitable connectives for making a : b :: c : d true for the 15 desired patterns, and false otherwise, have been proposed in [START_REF] Prade | Analogical proportions and multiple-valued logics[END_REF]. Some of these tri-valued connectives were quite unusual. Namely, two different three-valued extensions of logical difference were needed in [START_REF] Barbot | Analogical proportions and the factorization of information in distributive lattices[END_REF] or equivalently two circular negations (in the style of Post logic) and an associative nonmonotonic conjunction already studied by Walker [START_REF] Walker | Stone algebras, conditional events, and three-valued logic[END_REF] for combining three-valued conditional events (that are not applicable when their antecedent is false).

In the following, we indicate a simpler method for obtaining the same partition of the patterns into "true" and "false" categories, i.e. remaining in a Boolean setting. This view comes down to using a non-compact encoding using two attributes instead of one, and considering na as a kind of additional Boolean attribute. Namely, rather than asking if an attribute X is true in a considered situation a, or false or yet not applicable, we shall view the applicability of attribute X itself as a binary attribute Y 1 = appl(X ) which can be only true or false, and a second attribute Y 2 defined as the conjunction appl(X ) ∧ X , which is true if X is applicable and true, and false otherwise. Thus, the values 1, 0, and na will be encoded by the pairs (1, 1), (1, 0), and (0, 0) respectively, corresponding to the two Boolean attributes Y 1 , Y 2 . In fact, this may be viewed as a special case of a general method for dealing with discrete domains having more than two values, using Boolean variables. Proposition 1. All forms of the analogical proportion are valid for the three patterns (s, s, s, s), (s, s, t, t) and (s, t, s, t), where s, t ∈ {0, 1, na}, on both components of the two-variable encodings of possibly non-applicable attribute, and only those forms.

Proof. The validity of the patterns (s, s, s, s), (s, s, t, t), (s, t, s, t) is easy to check. For example, for (s, t, s, t), Boolean 4-tuples obtained from components of the vectors (Y 1 , Y 2 ) will be either equal or will form the pattern (s, t, s, t). For instance, the patterns (0, na, 0, na) supposed to satisfy the analogical proportion expression will then be encoded as an analogical proportion between pairs in B 2 :

(1, 0) : (0, 0) :: (1, 0) : (0, 0), which clearly holds in a componentwise manner, since the 2 Boolean 4-tuples (1, 0, 1, 0) and (0, 0, 0, 0) are valid patterns in the truth table of a : b :: c : d. Conversely, any non-valid patterns among the 66 ones, falsifies the analogical proportion expression for the two components in the binary encoding. It concerns patterns (s, t, t, s), e.g.

(1, na, na, 1), that include at least one similar Boolean 4-tuple, hence not valid. Patterns (s, t, t, t) and their permutations, having three identical components, will contain one Boolean 4-tuple with an odd number of ones and zeros, hence not valid. Finally, consider patterns with three distinct components (s, t, u, t), such as (0, 1, na, 1), and their permutations. Noticing that Boolean triples extracted from (s, t, u) (with s, t, u distinct) contain one 0 and two 0's respectively for attributes Y 1 , and Y 2 , (s, t, u, t) will contain at least one Boolean 4-tuple with an odd number of 1's, hence not valid. ✷ As an example, consider a set of individuals, and attribute X indicating pregnancy. Clearly, this is a partially applicable attribute, depending on the sex. So, Y 1 = appl(X ) indicates the sex of individuals, and takes value 1 for women. Then the validity of analogical proportions after the above approach is clear: for instance, (na, na, na, na) corresponds to four men, that are clearly analogous with respect to pregnancy, (na, na, 1, 1), means that a man is to a man what a pregnant woman is to a pregnant woman, (0, na, 0, na) means that a non-pregnant woman is to a man what another non-pregnant woman is to another man, etc.

Thus, the case of non-applicable Boolean attributes may still be handled in a satisfactory way in a Boolean setting, insofar as the non-applicability of one attribute can be interpreted as the truth of another meaningful property. Remark 2. In the above approach, the third truth-value is viewed as a supplementary Boolean attribute, which explains why the result is always true or false. Yet, one might object to the assumption that a pattern such as (na, na, na, na) can still stand as an analogical proportion. Taking the idea of non-applicable for granted, one may consider that in this case the whole pattern is not applicable to four objects with non-applicable properties, that is we may look for connectives that take the value na in some situations (after all, why should we see a pattern of analogical proportion between attributes on situations where these attributes do not apply?). There are two alternative ways of handling the latter idea of non-applicable in a three-valued setting. One may assign the value na to a : b :: c : d in all cases when the value na appears, in the spirit of strong truth-tables of Kleene three-valued logics. Such contamination effect would not lead to a very useful framework (it would lead us to restrict to the 6 Boolean valid patterns and drop the non-Boolean ones). The other approach leads to considering na as a semi-group identity in the truth tables of conjunction and disjunction, in the style of Sobocinski's logic [START_REF] Sobocinski | Axiomatization of a partial system of three-value calculus of propositions[END_REF]; conjunction and disjunction are uninorms with respective absorbing elements 0 and 1 [START_REF] Ciucci | A map of dependencies among three-valued logics[END_REF]. Then the truth-value na abstains from intervening whenever possible. Only the pattern (na, na, na, na) has truth-value na. However, using Sobocinski's connectives on analogy pattern [START_REF] Dubois | Fuzzy set modelling in cased-based reasoning[END_REF], we obtain a result such as 1: na :: 1 : 1 = 1, which looks highly questionable. So, finding an alternative three-valued logic approach (simpler than the one outlined in [START_REF] Prade | Analogical proportions and multiple-valued logics[END_REF]), where the logical proportion never takes the value na, is an open problem.

Gradual extensions of the analogical proportion

When the attributes used for describing situations are numerical, the logical definition of analogical proportion needs to be extended. For simplicity, as in the Boolean case, we assume that all numerical attribute domains are then (proportionally) rescaled on the unit interval [0, 1].

In contrast with the case of non-applicable values discussed above, we now expect that the multiple-valued extension of a : b :: c : d from B 4 to [0, 1] 4 takes values intermediary between 0 and 1 (e.g., a : b :: c : d for the pattern (0.9, 0, 1, 0) can be neither1 nor 0, but should rather have a high value since 0.9 is close to 1). For simplicity, in the sequel, the symbol a denotes both a variable and its truth-value.

The multiple-valued logic extension of the equivalent logical expressions of analogical proportion encountered in Section 2 first requires the choice of connectives for the external conjunction and the two equivalences. The following choices are of special interest [START_REF] Prade | Multiple-valued logic interpretations of analogical, reverse analogical, and paralogical proportions[END_REF][START_REF] Prade | Analogical proportions and multiple-valued logics[END_REF]: i) the central, external conjunction ∧ is taken as equal to the minimum. It is desirable here that the result of the conjunction be non-zero if both conjuncts have positive truth-values; in this case, nilpotent conjunctions are excluded. Finally, there is an argument of simplicity and one of dependence between terms that preclude the use of product. ii) s ≡ t is taken as min(s → L t, t → L s) where → L is Łukasiewicz implication, defined by s → L t = min(1, 1s + t), for L = [0, 1] and thus s ≡ t = 1 -|s -t|. There are two arguments in favor of this choice. First, with this definition, s ≡ t takes the truth value 1 if and only if s = t, which is fully in the spirit of exact comparisons; moreover this index is explicitly related to the usual distance between numerical values (expressed by the absolute value of the difference between s and t ).

Remark 3. The minimal algebraic structures needed to extend the equivalent logical proportion patterns presented in Section 2 to the multiple-valued case are not the same. For instance, the expressions ( 2), ( 4) and ( 5) only need a residuated lattice (e.g. min, max and Gödel implication) to be extended. However, one expects to also use an involutive negation in (1) and (3).

A conservative graded extension

A straightforward extension of expression ( 4) is obtained by also taking minimum for the internal conjunction and maximum for the internal disjunction [START_REF] Prade | Analogical proportions and multiple-valued logics[END_REF]. It yields:

a : b :: C c : d = min(1 -| max(a, d) -max(b, c)|, 1 -| min(a, d) -min(b, c)|) (7)
It is an extension of expression (3) as well, using 1 -• for negation. It can be easily seen that reflexivity, symmetry, central permutation, and invariance with respect to encoding continue to hold. Then it is clear that: It means that only patterns of the form (x, y, x, y) or (x, x, y, y) where x, y ∈ [0, 1] and possibly x = y make a : b :: C c : d fully true, generalizing the six cases of Table 1 and replacing 0 and 1 by x and y. In these patterns, a, b, c, d take values on a binary set {x, y} ⊂ [0, 1] only, and the degree of change from a to b, if any, must be exactly the same as the one from c to d, in direction (the first requirement enforcing the same amplitude of change). This is clearly a conservative view of graded analogy that remains close in spirit to the Boolean case.

In contrast, for instance, 0.2 : 0.4 :: C 0.6 : 0.8 = 0.2 : 0.4 :: C 0.4 : 0.6 = 0.8, rather than 1 since in both cases there are more than two distinct truth-values for a, b, c, d, despite the fact that the changes from a to b and from c to d have the same direction and amplitude. These cases are of the form (x, x + z, y, y + z) with x + z ≤ 1, y + z ≤ 1, for which we have:

x : (x + z) :: C y : (y + z) = 1 -z if min(x + z, y + z) ≤ max(x, y) 1 -|x -y| otherwise, (8)
or equivalently, x : (x + z) :: C y : (y + z) = 1 -min(z, |x -y|). It lays bare the role played by the difference between the truth-values of a and b, a and c, c and d. If x + z = y (three distinct values, x, y, 2y -x ≤ 1), then x : y :: C y :

(2y -x) = 1 -|x -y| = 1 -z.
Besides, it is obvious as well from the expression (7) that:

Proposition 3. a : b :: C c : d = 0 if and only if | min(a, d) -min(b, c)| = 1 or | max(a, d) -max(b, c)| = 1.
In other words, the only patterns fully falsifying the analogical proportion are of the form 1 : 0 :: C x : 1 or 0 : 1 :: C x : 0, ∀x ∈ [0, 1] (and the other patterns obtained from these two by symmetry and central permutation). Thus, a : b :: C c : d = 0 if and only if there is a maximal difference between a and b, while a and d are equal, whatever the remaining term (and the like for the ones obtained by symmetry and central permutation). Interestingly, the two extreme patterns of the form 1 : 0 :: C x : 1 are 1 : 0 :: 0 : 1 and 1 : 0 :: 1 : 1 that have truth-value 0, which explains the same holds if 0 < x < 1. Again this is a conservative extension of the false Boolean cases.

If we use a 3-level scale L = {α 0 = 0, α 1 = 1/2, α 2 = 1}, a : b :: C c : d defined by ( 7) is equal to 1 exactly for the same 15 patterns (replacing na by 1/2) where truth was preserved in the case of non-applicable values. It is equal to 0 for the 18 patterns of the form 1 : 0 :: C x : 1 or 0 : 1 :: C x : 0 (and the ones obtained by symmetry or central permutation). In the 3 4

Proposition 4. Numerical expressions ( 9) and ( 7) coincide.

Proof. Indeed, it can be seen that using [START_REF] Dubois | Fuzzy set-based methods in instance-based reasoning[END_REF] are such that 1/2 : 1/2 :: 1 : 1 = 1 and 1/2 : 1 :: 1/2 : 1 = 1/2 (resp. 1/2 : 1/2 :: 1 : 1 = 1/2 and 1/2 : 1 :: 1/2 : 1 = 1), i.e. central permutation does not hold.

A liberal graded extension

The multiple-valued extension of (4) (or ( 5)) has truth value 1 only for patterns of the form (x, y, x, y) or (x, x, y, y) where x, y ∈ L and possibly x = y. It makes sense on ordinal lattice-like truth scales [START_REF] Barbot | Analogical proportions and the factorization of information in distributive lattices[END_REF], but it sounds like a very restrictive view of graded analogy, not in line with its usual numerical forms. This will be no longer the case with the multiple-valued extension of expression [START_REF] Barbot | Analogical proportions and the factorization of information in distributive lattices[END_REF], which is now discussed. Keeping the same choices of connectives for central conjunction and equivalence, we interpret s ∧ ¬t in (1) as a bounded difference max(0, st) = 1 -(s → L t), in other words, this is like using Łukasiewicz implication in expression [START_REF] Ciucci | A map of dependencies among three-valued logics[END_REF]. The resulting expression is then

The expression [START_REF] Miclet | Logical definition of analogical proportion and its fuzzy extensions[END_REF] still satisfies reflexivity, symmetry, central permutation, and invariance with respect to encoding. It can be checked that the analogical proportion is valid when the changes from a to b and from c to d have the same direction and amplitude, and there is no longer any requirement on the number of distinct values a, b, c, d: For instance, 0.2 : 0.4 :: L 0.6 : 0.8 = 0.2 : 0.4 :: L 0.4 : 0.6 = 1, in contrast with the conservative approach of the previous section.

In case of a three-valued truth scale L = {0, 1/2, 1}, there are 4 more patterns that satisfy a : b :: L c : d = 1 with respect to [START_REF] Dubois | Fuzzy set-based methods in instance-based reasoning[END_REF], namely (0, 1/2, 1/2, 1), (1, 1/2, 1/2, 0), (1/2, 1, 0, 1/2), and (1/2, 0, 1, 1/2), on top of the 15 patterns for which [START_REF] Dubois | Fuzzy set-based methods in instance-based reasoning[END_REF] was fully true and are still true here. So this is a more liberal view of graded analogy, more precisely one of the known natural numerical expressions of it, in terms of equal differences.

Besides, it takes little effort to check from expression (11) that In the 3-valued case means the 22 following false patterns:

(1, 1, 1, 0); (1, 1, 0, 1); (1, 0, 1, 1); (0, 1, 1, 1); (0, 0, 0, 1); (0, 0, 1, 0); (0, 1, 0, 0);

(1, 0, 0, 0); (1, 0, 0, 1); (0, 1, 1, 0); (1, 0, 0, 1/2); (0, 1, 1, 1/2); (1, 0, 1/2, 1);

(1/2, 0, 0, 1); (0, 1/2, 1, 0); (1, 1/2, 0, 1); (0, 1, 1/2, 0); (1/2, 1, 1, 0), (1, 0, 1/2, 1/2); (0, 1, 1/2, 1/2); (1/2, 1/2, 1, 0); (1/2, 1/2, 0, 1).

Note that the conservative approach (7) yields truth-value 1/2 (rather than 0) for the last 4 listed patterns. Thus, a : b :: L c : d = 1/2 for 81 -19 -22 = 40 distinct patterns when we use L = {0, 1/2, 1}.

The discrepancy between ( 7) and ( 11) may be still better seen when considering so-called "continuous" proportions of the form a : b :: b : c. Indeed,

• with ( 7 This result suggests that the liberal approach ( 11) is suitable for interpolation and extrapolation purposes [START_REF] Prade | Completing rule bases in symbolic domains by analogy making[END_REF][START_REF] Schockaert | Interpolation and extrapolation in conceptual spaces: a case study in the music domain[END_REF].

In particular, the following result is noticeable:

Proposition 7. If A, C are the coordinates of points in a n-dimensional space, i.e. A = (a 1 , • • • , a n ), C = (c 1 , • • • , c n ),
the solution of the analogical proportion equation

A : X :: L X : C = 1 is the midpoint B = ((a 1 + c 1 )/2, • • • , (a n + c n )/2) of the segment AB in the n-dimensional space.
Proof. For each component, the equation reads: x i -a i = c i -x i , which yields x i = (a i + c i )/2. ✷

The solution of equation A : X :: L X : C = 1 is thus obtained by a linear interpolation.

Similarly, the solution of equation A : B :: L C : X = 1 is obtained by a linear extrapolation x i = c i + b i -a i , ∀i. This solution exists provided that 0 ≤ c i + b i -a i ≤ 1 for all i = 1, • • • , n. Remark 6. The same equations with the conservative approach generally have no solutions. Namely, A : X :: C X : C = 1 only if X = A = C, for otherwise, generally, neither A : B :: C B : C nor A : A :: C A : C, nor A : C :: C C : C can get value 1. Likewise A : B :: C C : X = 1 if A, B, C take distinct values. Note that in the Boolean case, the extrapolation equation A : B :: C : X = 1 is solvable iff (A ≡ B) ∨ (A ≡ C) holds componentwise. In that case, the unique solution is X = A ≡ (B ≡ C) [START_REF] Miclet | Logical definition of analogical proportion and its fuzzy extensions[END_REF][START_REF] Miclet | Handling analogical proportions in classical logic and fuzzy logics settings[END_REF][START_REF] Prade | From analogical proportion to logical proportions[END_REF]. This solution can be adapted for solving A : B :: C C : X = 1 but as pointed out in Proposition 2, each 4-tuple (a i , b i , c i , d i ) must contain at most two distinct values, which comes down to very few feasible cases if values lie in [0, 1], whose practical interest looks limited.

Concluding remarks

The ambition of this paper is modest. It is an invitation to study, in the setting of fuzzy set theory, the notion of logical proportion pervading analogical reasoning. The multiple-valued extensions of various Boolean expressions of the logical proportions discussed here are some significant examples among other possible ones. In particular, a systematic investigation of algebraic structures needed to make sense of each expression of the logical proportion, especially, ordinal structures using residuated lattices with or without involutive negation, and the expressive power of the corresponding analogical reasoning patterns is a matter of future research.

In practice, the analogical inference machinery is based on the idea that if the same logical proportion holds for a number of components of A, B, C, D, then it may still hold for a new component known for A, B, C, but not for D, which can then be extrapolated. This has been applied to classification. The core principle of the algorithm is then to extrapolate the class of D on the basis of the best triple of examples A, B, C, such that a i : b i :: c i : d i holds with a high degree for a maximum number of components (the best triple using a leximax ordering of the n-tuples of scores); see e.g., [START_REF] Prade | Enforcing regularity by means of analogy-related proportions-a new approach to classification[END_REF]. Although the multiple-valued extension of the analogical proportion in the liberal form of Subsection 4.2 may sound more appropriate for completing incomplete databases via extrapolation, the conservative extension discussed in this paper may be also of interest in classification. Judging the appropriateness of a particular extension for a given context still remains an open question.

1 .

 1 a : b :: a : b (reflexivity) 2. a : b :: c : d ≡ c : d :: a : b (symmetry) 3. a : b :: c : d ≡ a : c :: b : d (central permutation)

•

  a : b :: c : d ≡ d : b :: c : a • a : b :: c : d ≡ ¬a : ¬b :: ¬c : ¬d

  Then, A : B :: C : D means that A differs from B as C differs from D on the considered attribute. More precisely, a ∧ ¬b (resp. ¬a ∧ b) computes the difference or dissimilarity between a and b (resp. b and a), which is equated to the difference between c and d (resp. d and c). This logical view has been further studied and discussed in[START_REF] Prade | From analogical proportion to logical proportions[END_REF].Note also that by changing a into ¬a, b into ¬c, c into d, d into b in the logical expression (1), we get the logical expression of a : c :: b : d, (which is equivalent to a : b :: c : d using central permutation). We can infer that if a is to c as b is to d, then not a is to not c what d is to b.

Proposition 2 .

 2 a : b :: C c : d = 1 if and only if min(a, d) = min(b, c) and max(a, d) = max(b, c).

Remark 4 .

 4 -(15 + 18) = 48 other cases, a : b :: C c : d = 1/2. Note that if we use product instead of minimum for the inner conjunctions, and the probabilistic sum (x + yxy) in expression (4), then a : b :: C c : d = 1 if and only if both equalities a b = c d and ab = cd hold, that is, both arithmetic and geometric proportions must hold, which yields a = c and b = d or a = b and c = d. It generalizes again the same six cases of Table 1 replacing 0 and 1 by a and b, respectively, as with minimum and maximum. Using Łukasiewicz conjunction and disjunction instead would only yield the condition ab = cd. The alternative disjunctive expression (5) could be also considered as a starting point for the extension of a : b :: C c : d to the multiple-valued case. Namely, using min for ∧, max for ∨, and 1 -| • -• | for ≡, we obtain (factoring out the negation appearing in the many-valued equivalences): a : b :: C c : d = 1 -min(max(|a -b|, |c -d|), max(|a -c|, |b -d|))

Remark 5 .

 5 a : b :: C c : d can be also written as: 1 -max(|a -b|, |c -d|) if a ≥ d and b ≥ c, or a ≤ d and b ≤ c 1 -max(|a -c|, |b -d|) if a ≥ d and c ≥ b, or a ≤ d and c ≤ b (10) Besides, we have max(|a -b|, |c -d|) ≤ max(|a -c|, |b -d|) if a ≥ d and b ≥ c. This can be easily checked by letting a = d + x and b = c + y with x > 0 and y > 0 and rewriting the inequality as max(|d -b + x|, |d -b + y|) ≤ max((|d -b + x + y|, |d -b|). The three other cases are similar. This shows the equality of (9) and (10) (and thus (7)). ✷ However, (7) no longer coincides with the extensions of two other disjunctive expressions of the logical proportion, involving negations of equivalences in place of equivalences in one of the two conjunctions (and suitable permutations of a, b, c, d) [13]: a : b :: c : d = ((a ≡ d) ∧ (b ≡ c)) ∨ ((a ≡ b) ∧ (c ≡ d)) = ((a ≡ d) ∧ (b ≡ c)) ∨ ((a ≡ c) ∧ (b ≡ d)) whose respective multiple-valued extensions a : b :: c : d = max(min(|a -d|, |b -c|), min(1 -|a -b|, 1 -|c -d|)) a : b :: c : d = max(min(|a -d|, |b -c|), min(1 -|a -c|, 1 -|b -d|))

a

  : b :: L c : d = (a -b) -(cd)|, if a ≥ b and c ≥ d, or a ≤ b and c ≤ d 1 -max(|a -b|, |c -d|), if a ≤ b and c ≥ d, or a ≥ b and c ≤ d

Proposition 5 .

 5 a : b :: L c : d = 1 if and only if ab = cd.

Proposition 6 .

 6 a : b :: L c : d = 0 if and only if • ab = 1 and c ≤ d, • or ba = 1 and d ≤ c, • or a ≤ b and cd = 1, • or b ≤ a and dc = 1 Thus, a : b :: L c : d = 0 when the change inside one of the pairs (a, b) or (c, d) is maximal, while the other pair shows either no change or any change in the opposite direction. Here, again there are more cases where the analogical proportion totally fails than in the previous subsection.

  ), a : b :: C b : c = 1 -max(|a -b|, |b -c|), and thus a : b :: b : c = 1 if and only if a = b = c, • while a : b :: L b : c = 1 if and only if (ab) = (bc), i.e., b = (a + c)/2.

table on Table 1 :

 on1

This is true as well for arithmetic proportions of the form ab = cd, which is equivalent to ac = bd, and to a + d = b + c [16].


Daniela Genius
email: daniela.genius@lip6.fr

Letitia W Li

Ludovic Apvrille
email: ludovic.apvrille@telecom-paristech.fr

Model-Driven Performance Evaluation and Formal Verification for Multi-level Embedded System Design

Keywords: Virtual prototyping, Embedded systems, System-level design, Formal verification

The design methodology of an embedded system should start with a system-level partitioning dividing functions into hardware and software. However, since this partitioning decision is taken at a high level of abstraction, we propose regularly validating the selected partitioning during software development. The paper introduces a new model-based engineering process with a supporting toolkit, first performing system-level partitioning, and then assessing the partitioning choices thus obtained at different levels of abstraction during software design. This assessment shall in particular validate the assumptions made on system-level (e.g. on cache miss rates) that cannot be precisely determined without low-level hardware model. High-level partitioning simulations/verification rely on custom model-checkers and abstract models of software and hardware, while low-level prototyping simulations rely on automatically generated C-POSIX software code executing on a cycle-precise virtual prototyping platform. An automotive case study on an automatic braking application illustrates our complete approach.

Introduction

Embedded systems are composed of a tightly integrated ensemble of HW and SW components. The design of these systems usually starts with a system-level partitioning phase, continues with separate software and hardware design, and finishes with a HW/SW integration. In fact, this integration can also be performed progressively during software design using prototyping techniques.

At system-level partitioning, properties of embedded applications can be tested rapidly and their description remains somewhat "human-readable". Properties can also be proven formally. Exploration, however, remains at a rather abstract level e.g. many hardware parameters are approximated. For example, the cache miss rate is modeled as a fixed value (e.g., 5%) obtained from the architect's experience.

After partitioning, software is designed at lower abstraction levels. Commonly, the hardware target is not available, leading to the use of simulation techniques with precise hardware models. System parameters, such as the cache miss ratio, can be closely evaluated with simulations and formal proofs. Unfortunately, more details also means much slower simulations, and infeasible formal proofs, even if com-positional approaches could help handle entire hardware platforms. However, they are costly [START_REF] Basu | Rigorous component-based system design using the BIP framework[END_REF][START_REF] Syed-Alwi | Efficient Refinement Strategy Exploiti ng Component Properties in a CEGAR Process[END_REF] in terms of development time.

To improve both development stages (partitioning, prototyping), we propose to unify them in a common SysML formalism. In fact, prototyping can rely on software and hardware elements that were formally evaluated at partitioning. Partitioning models can be enhanced using precise parameters that can be obtained during simulation at the prototyping level. Our toolkit, TTool [START_REF] Apvrille | Webpage of TTool[END_REF], supports both stages, and makes it possible, at the push of a button, to evaluate the design at a given development stage, and to propagate the results to enhance the system at another development state, thus easing development iterations. We previously described [START_REF] Li | Virtual prototyping of automotive systems: Towards multi-level design space exploration[END_REF] our approach towards multi-level Design Space Exploration, but without the ability to generate detailed performance metrics during prototyping that we present in this paper.

Section 2 presents related work. Section 3 presents the overall design method. Section 4 details an automotive case study used to exemplify the highlevel design space exploration (Section 5), as well as software component design and performance evalua-tion (Section 6). A final discussion and perspectives on future work are presented in Section 7.

2 System-level Design for Embedded Systems A number of system-level design tools exist, offering a variety of verification and simulation capabilities at different levels of abstraction.

Ptolemy [START_REF] Buck | Ptolemy: a framework for simulating and prototyping heterogeneous systems[END_REF] proposes a modeling environment for the integration of diverse execution models, in particular hardware and software components. If design space exploration can be performed with Ptolemy, its first intent is the simulation of the modeled systems.

Metropolis [START_REF] Balarin | Metropolis: An integrated electronic system design environment[END_REF] targets heterogeneous systems, and architectural and application constraints are closely interwoven. This approach is more oriented towards application modeling, even if hardware components are closely associated to the mapping process. While our approach uses Model-Driven Engineering, Metropolis uses Platform-Based Design.

Sesame [START_REF] Erbas | Multiobjective optimization and evolutionary algorithms for the application mapping problem in multiprocessor system-on-chip design[END_REF] proposes modeling and simulation features at several abstraction levels for Multiprocessor System-on-Chip architectures. Pre-existing virtual components are combined to form a complex hardware architecture. Models' semantics vary according to the levels of abstraction, ranging from Kahn process networks (KPN [START_REF] Kahn | The semantics of a simple language for parallel programming[END_REF]) to data flow for model refinement, and to discrete events for simulation. Currently, Sesame is limited to the allocation of processing resources to application processes. It models neither memory mapping nor the choice of the communication architecture.

The ARTEMIS [START_REF] Pimentel | Exploring embedded-systems architectures with artemis[END_REF] project is strongly based on the Y-chart approach. Application and architecture are clearly separated: the application produces an event trace at simulation time, which is read by the architecture model. However, behavior depending on timers and interrupts cannot be taken into account.

MARTE [START_REF] Vidal | A co-design approach for embedded system modeling and code generation with UML and MARTE[END_REF] shares many commonalities with our approach, in terms of the capacity to separately model communications from the pair application-architecture. However, it intrinsically lacks a separation between control and message exchange.

Other works based on UML/MARTE, such as Gaspard2 [START_REF] Gamatié | A model-driven design framework for massively parallel embedded systems[END_REF], are dedicated to both hardware and software synthesis, relying on a refinement process based on user interaction to progressively lower the level of abstraction of input models.

However, such a refinement does not completely separate the application (software synthesis) or architecture (hardware synthesis) models from communication.

Rhapsody can automatically generate software, but not hardware descriptions from SysML. MDGen from Sodius (Sodius Corporation, 2016) adds timing and hardware specific artifacts such as clock/reset lines automatically to Rhapsody models, generates synthesizable, cycle-accurate SystemC implementations, and automates exploration of architectures.

The Architecture Analysis & Design Language AADL [START_REF] Feiler | An overview of the SAE architecture analysis & design language (AADL) standard: A basis for model-based architecture-driven embedded systems engineering[END_REF] allows the use of formal methods for safety-critical real-time systems. Similar to our environment, a processor model can have different underlying implementations and its characteristics can easily be changed at the modeling stage. Recently, [START_REF] Yu | The challenge of interoperability: model-based integration for automotive control software[END_REF] developed a model-based formal integration framework which endows AADL with a language for expressing timing relationships.

Capella [START_REF] Polarsys | ARCADIA/CAPELLA[END_REF] relies on Arcadia, a comprehensive model-based engineering method. It is intended to check the feasibility of customer requirements, called needs, for very large systems. Capella provides architecture diagrams allocating functions to components, and advanced mechanisms to model bitprecise data structures.

Methodology

Modeling Phases

Our approach combines partitioning -the partitioning decision relies on design space exploration techniques -and software design. The latter includes the prototyping of the designed software. All stages are supported within the same SysML-based free and opensource environment/toolkit (as shown in Figure 1):

1. The overall method starts with a partitioning phase containing three sub-phases: the modeling of the functions to be realized by the system (functional view), the modeling of the candidate architecture as an assembly of highly abstracted hardware nodes, and the mapping phase. A function mapped on a processor is a software function, a function mapped on a hardware accelerator corresponds to a custom ASIC (Application-specific Integrated Circuit).

2. Once the system is fully partitioned, the second phase starts with the design of the software and the hardware. Our approach offers software modeling while taking into account hardware parame- Choice of parameters on the higher level is subject to validation or invalidation due to experimental results on the generated prototype. Thus, simulations results at prototyping level could lead to reconsider the partitioning decisions.

Simulation, Verification and Prototyping

During the methodological phases, simulation and formal verification help in deciding whether safety, performance and security requirements are fulfilled.

Our toolkit offers a press-button approach for performing these proofs. Model transformations translate the SysML models into an intermediate form that is sent into the underlying simulation and formal verification utilities. Backtracing to models is then performed to better inform the users about the verification results. Proofs of safety involve UPPAAL semantics [START_REF] Bengtsson | Timed automata: Semantics, algorithms and tools[END_REF], and security proofs use ProVerif [START_REF] Blanchet | Proverif automatic cryptographic protocol verifier user manual[END_REF]. Before the next stage, simulation and formal verification ensure that our design meets performance, behavioral, and schedulabil-ity requirements. Simulation of partitioning specifications involves executing tasks on the different hardware elements in a transactional high-level way. Each transaction executes for a variable time depending on execution cycles and CPU parameters. The simulation shows performance results like bus usage, CPU usage, execution time, etc., so as to help users decide on an architecture and mapping. For example, singles execution sequences can be investigated with gtkwave. Also, our toolkit assists the user by automatically generating all possible architectures and mappings, and summarizes performance results of each possible mapping. Users are provided with the "best" architecture under specified criteria, such as minimal latency or bus/CPU load.

During functional modeling, verification intends to identify general safety properties (e.g., absence of deadlock situations). At the mapping stage, verification intends to ascertain if performance and security requirements are met. Hardware components are highly abstracted. For example, a CPU can be defined with a set of parameters such as an average cache-miss ratio, power-saving mode activation, context switch penalty, etc.

After mapping, software components can also be verified independently of any hardware architecture in terms of safety and security. For example, when designing a component implementing a security protocol, the reachability of the states and absence of security vulnerabilities can be verified. When the soft- SoCLib also contains a set of performance evaluation tools [START_REF] Genius | Mapping a telecommunication application on a multiprocessor system-on-chip[END_REF]. Last but not least, the SoCLib prototyping platform comes with an operating system well adapted to multiprocessor-on-chip [START_REF] Becoulet | Mutekh operating system (webpage[END_REF].

If the performance results of the SystemC simulation differ too greatly from the ones obtained during the design space exploration stage -e.g., a cache miss ratio -then, design space exploration shall be performed again to assess if the selected architecture is still the best according to the system requirements. If not, software components may be (re)designed. Once the iterations over the high-level design space exploration and the low level virtual prototyping of software components are finished, software code can be generated from the most refined software model.

Automotive Case Study

Our methodology is illustrated using an automotive embedded system designed in the scope of the European EVITA project [START_REF] Evita | E-safety Vehicle InTrusion protected Applications[END_REF]. Recent onboard Intelligent Transport (IT) architectures comprise a very heterogeneous landscape of communication network technologies (e.g., LIN, CAN, MOST, and FlexRay) that interconnect in-car Electronic Control Units (ECUs).

The increasing number of such equipment triggers the development of novel applications that are commonly spread among several ECUs to fulfill their goals. Prototyping on multiprocessor architectures, even if they are more generic than the final hardware, is thus very useful.

An automatic braking application serves as a case study [START_REF] Kelling | Specification and evaluation of e-security relevant use cases[END_REF]. The system works essentially as follows: an obstacle is detected by another automotive system which broadcasts that information to neighboring cars. A car receiving such information has to decide if it is concerned with this obstacle. This decision includes a plausibility check function that takes into account various parameters, such as the direction and speed of the car, and also information previously received from neighboring cars. Once the decision to brake has been taken, the braking order is forwarded to relevant ECUs. Also, the presence of this obstacle is forwarded to other neighboring cars in case they have not yet received this information. Figure 2 shows the model for Partitioning: an Architecture Diagram with the tasks divided onto different CPUs and Hardware Accelerators. Figure 3 shows the Block Diagram for Software Design. Figure 4 shows the Deployment Diagram. We elaborate in detail on the different stages in the following sections.

5 Hardware/Software Partitioning

Modeling

The HW/SW Partitioning phase of our methodology intends to model the abstract, high-level functionality of a system [START_REF] Knorreck | Formal System-level Design Space Exploration[END_REF]. It follows the Y-chart approach, first modeling the abstract functional tasks, candidate architectures, and then finally mapping tasks to the hardware components [START_REF] Kienhuis | A Methodology to Design Programmable Embedded Systems: The Y-Chart Approach[END_REF]. The application is modeled as a set of communicating tasks on the Component Design Diagram (an extension of the SysML Block Instance Diagram). Task behavior is modeled using communication operators, computation elements, and control elements.

The architectural modeling (Figure 2) is displayed as a graph of execution nodes, communication nodes, and storage nodes. Execution nodes, such as CPUs and Hardware Accelerators, include parameters such data size, instruction execution time, and clock ratio (see Figure 5. CPUs also must be defined by task switching time, cache-miss percentage, etc. Communication nodes include bridges and buses. Buses connect execution and storage nodes, and bridges connect buses. Buses are defined by parameters such as arbitration policy, data size, clock ratio, etc, and bridges are characterized by data size and clock ratio. Storage nodes are Memories, which are defined by data size and clock ratio. Mapping involves specifying the location of tasks on the architectural model. A task mapped onto a processor will be implemented in software, and a task mapped onto a hardware accelerator will be implemented in hardware. The exact physical path of a data/event write may also include mapping channels to buses and bridges. Alternatively, if the data path is complex (e.g., DMA transfer), channels can be mapped over communication patterns [START_REF] Enrici | A uml model-driven approach to efficiently allocate complex communication schemes[END_REF].

High-Level Simulation

Using simulation techniques described in section 3.2, we can see that the mapping of tasks of our case study (see Figure 2) ensures that the maximum latency between the decision (DangerAvoidanceStrategy) and the resulting actions (doReduceDrivingPower and DoBrake) respect safety requirements. Similarly, we have verified that the worst latency between the reception of an emergency message by DRSCManagement and the consequent actions (e.g., DoBrake) is always also below the specified limit. These performance verifications are performed according to the selected functions, operating systems and hardware components. In particular, many parameters of the hardware components are simple values (we have for example selected a cache-miss ratio of 5%) that are meant to be confirmed during the software design phase.

Software Components

Figure 3 shows the software components of the active braking use case modeled using an AVATAR block diagram. These modeling elements have been selected during the previous modeling stage (partitioning). Software components are grouped according to their destination ECU:

• Communication ECU manages communication with neighboring vehicles.

• Chassis Safety Controller ECU (CSCU) processes emergency messages and sends orders to brake to ECUs.

• Braking Controller ECU (BCU) contains two blocks: DangerAvoidanceStrategy determines how to efficiently and safely reduce the vehicle speed, or brake if necessary. BrakeManager operates the brake for a given duration.

• Power Train Controller ECU (PTC) enforces the engine torque modification request.

The AVATAR model can be functionally simulated using the integrated simulator of our toolkit, which takes into account temporal operators but completely ignores hardware, operating systems and middleware. While being simulated, the model of the software components is animated. This simulation aims at identifying logical modeling bugs. Figure 6 shows the state machine of DangerAvoidanceStrategy, Figure 8 shows a visualization of the generated sequence diagram. We show traces for the CarPositionSimulator block and for three of the blocks which interact in an emergency braking situation: DrivingPowerReduc-tionStrategy, DangerAvoidanceStrategy and BrakeManagement.

Formal Verification

During formal verification of safety properties with UPPAAL, a model checker for networks of timed automata, the behavioral model of a system to be verified is first translated into a UPPAAL specification to be checked for desired behavior. For example, UPPAAL may verify the lack of deadlock, such as two threads both waiting for the other to send a message. Behavior may also be verified through "Reachability", "Leads to", and other general statements. The designer can indicate which states in the Activity Diagram or State Machine Diagram should be checked if they can be reached in any execution trace. "Leads to" allows us to verify that one state must always be followed by another. Other user-defined UPPAAL queries can check if a condition is always true, is true for at least one execution trace, or if it will be true eventually for all execution traces. These statements may be entered directly on the UPPAAL model checker, or permanently stored on the model as pragma to be verified in UPPAAL.

For example, for our case study, we can verify that state 'Plausibility Check' is always executed after a neighboring car signals that it has detected an obstacle. We can also verify that an order to brake can be received, or state 'Braking Management' in Task 'Danger Avoidance Strategy' is reachable. Figure 7 shows the UPPAAL verification window which allows the user to customize which queries to execute, and then returns the results as shown.

Prototyping

To prototype the software components with the other elements of the destination platform (hardware components, operating system), a user must first map them to a model of the target system. Mapping can be performed using the new deployment features recently introduced in [START_REF] Genius | Virtual yet precise prototyping : An automotive case study[END_REF]). An AVATAR Deployment Diagram is used for that purpose. It features a set of hardware components, their interconnection, tasks, and channels.

The partitioning phase selected an architecture with five clusters. Some tasks are destined to be software tasks (they are mapped onto CPUs), and the others are expected to be realized as hardware accelerators. Yet, each specific hardware accelerator in SoCLib needs to be developed specifically which requires a significant effort. We do not consider that case in the paper since all AVATAR tasks are software tasks. The five clusters are represented by five CPUs and the channels between AVATAR tasks are implemented as software channels mapped to on-chip RAM. Some properties pertaining to mapping must be explicitly captured in the Deployment Diagram, such as CPUs, memories and their parameters, while others, such as simulation infrastructure and interrupt management, are added transparently to the top cell during the transformation to SoCLib. Figure 4 shows the Deployment Diagram of the software components of the active braking application mapped on five processors and five memory elements. From the Deployment Diagram, a SoCLib prototype is then generated. This prototype consists of a SystemC top cell, the embedded software in the form of POSIX threads compiled for the target processors, and the embedded operating system (Figure 9).

Capturing Performance Information

We now present how performance information can be obtained from the use case simulated with SoCLib. In the experiments shown here, we use PowerPC cores.

The cycle accurate bit accurate (CABA)-level simulation allows measurement of cache miss rates, la- tency of any transaction on the interconnect, taking/releasing of locks, etc. Since SoCLib hardware models are much more precise than the ones used at the design space exploration level, precise timing and hardware mechanisms can be evaluated. However, these evaluations take considerable time compared to high-level simulation/evaluation. We restrict ourselves to using only the hardware counters available in the SoCLib cache module. We start by an overview of performance problems. For this, we use an overall metric summing up all phenomena that slow down execution of instructions by the processor, such as memory access latency, interconnect contention, overhead due to context switching etc.: Cycles per Instruction (CPI). For bottom line comparison, the CPI is first measured on a mono processor platform (Figure 10). On this platform, the single processor is constantly overloaded (CPI > 16).

Our tool allows per-processor performance evaluation, which is particularly useful in detecting unbalanced CPU loads. Even when prototyping onto five processors (Figure 11) to reflect the DIPLODOCUS partitioning, the CPU loads are not very well balanced. This is due to the fact that currently, a central request manager is required to capture the semantics of AVATAR channels. Requests are stored in waiting queues for synchronous as well as asyn- 5). While the estimated 5% of cache misses includes both data and instruction cache misses, SoCLib measures them separately. Instruction cache miss rates will be higher for the cache of CPU0 because the central request manager runs on this CPU, as noted in the previous paragraph.

We vary size and associativity of both caches, initially considering direct mapped caches (Figure 13), then setting associativity to four (Figure 14) for the same size. This action can be performed with a few mouse clicks (see Figure 12). Even if we do not explore the cache parameters fully in the work presented here, we can already conclude from this first exploration that data cache misses were overestimated; they are below 10 -7 . As for instruction cache misses, they are below 10% for the cache of CPU0, below 2% for the other four caches. We can thus lower the estimations, distinguishing between CPU0 and the others. Since our toolkit does distinguish between data and instruction cache misses during partitioning, we take the less favorable case of instruction cache misses and raise the miss rate for CPU0 to 10%, and lower it to 2% for the others. Figure 5 shows the window for customizing the CPU during partitioning, where we can now adapt the cache miss rate (and redo the partitioning).

We finally compare the influence of the interconnect latency (10 and 20 cycles, see Figures 17 and18). We observe a significant influence on the cost of a cache miss; latency of data cache misses is generally We observe after these first exploration steps that apart from correcting the estimated cache miss rate in DIPLODOCUS, adding another CPU in order to take some of the load from CPU4 would improve the performance.

As we can see in the CPU attributes window of Figure 5, our toolkit potentially allows a designer to improve estimates of several more hardware parameters like branch misprediction rate and go idle time. Until now, we used only the hardware counters implemented in the SoCLib components. Taking into account the OS, over which we have full control, we will soon be able to address other issues such as task switching time. Our model-driven approach with a SysML-based methodology and supporting toolkit enables designers to capture systems at multiple levels and facilitates the transitions between embedded system design stages. Prototyping from AVATAR enables the user to take into account performance results in a few clicks in the In order to deliver more realistic results, we are currently working on integrating clustered architectures. These architectures are supported in So-Clib, but various details make top cell generation much more complex (two-level mapping table, address computation complexity, etc.).

To help backtrace low level results (prototyping) to a higher level (partitioning), we are currently working on providing the performance graphs shown in the paper directly and automatically in the toolkit. Also, most metrics we have exemplified are CABA-based. We could also propose two other abstraction levels of SoCLib: TLM (Transaction Level) and TLM-T (Transaction Level with Time). Future work will focus on adding these intermediate levels, considerably speeding up prototypes at the cost of loss of precision to be evaluated. However, using this intermediate level of abstraction would smooth the development gap between system-level and low-level prototyping.

  Figure 1: Overall Approach

Figure 3 :

 3 Figure 3: Active Braking Block Diagram

Figure 4 :

 4 Figure 4: Deployment Diagram of the Active Braking Application: five CPUs and five RAMs

Figure 5 :

 5 Figure 5: Adapting architecture parameters during partitioning

Figure 6 :

 6 Figure 6: High Level Simulation of the Active Braking Automotive system: State Machine

Figure 7 :

 7 Figure 7: UPPAAL Formal Verification

Figure 8 :

 8 Figure 8: High Level Simulation of the Active Braking Automotive system: generated Sequence diagram

Figure 9 :

 9 Figure 9: AVATAR/SoCLib Prototyping Environment in TTool

Figure 11 :

 11 Figure 11: CPI per processor for a 5 processor configuration

Figure 12 :

 12 Figure 12: Varying cache associativity with a few mouse clicks For the instruction cache, using the same parameters (Figures 15 and 16), miss rates are closer to the estimated ones.Even if we do not explore the cache parameters fully in the work presented here, we can already conclude from this first exploration that data cache misses were overestimated; they are below 10 -7 . As for instruction cache misses, they are below 10% for the cache of CPU0, below 2% for the other four caches.

Figure 14 :

 14 Figure13: Data cache misses per processor for a 5 processor configuration with a direct mapped cache

Figure 15 :Figure 16 :

 1516 Figure 15: Instruction cache misses per processor for a 5 processor configuration with a direct mapped cache

Figure 17 :

 17 Figure 17: Cost of instruction cache miss in cycles for a 5 processor configuration with 4 cache sets

Figure 18 :

 18 Figure 18: Cost of data cache miss in cycles for a 5 processor configuration with 4 cache sets

Software Design with AVATAR/SoCLibOnce the partitioning is complete, the AVATAR methodology[START_REF] Pedroza | AVATAR: A SysML environment for the formal verification of safety and security properties[END_REF] allows the user to design the software, perform functional simulation and formal verification, and finally test the software components in a virtual prototyping environment.


Keywords: connected walking stick, fall detection, multistage thresholding, real-time movements

fall related injuries caused have become a leading cause of fatalities among the elderly. Lots of aging people rely on a cane as a help device to overcome such problems as balance loss and leg weakness, presumed to be at the origin of many fall incidents. In this respect, the internet of things may turn out to be critically helpful, by offering disabled people the assistance and support necessary for achieving a good quality of life and allowing them to participate in the social and economic activities. In this paper, a 3DCane design is depicted, with an implementation for the CANet project, a system whereby a comprehensive monitoring of disabled people can be maintained through the use of their connected walking stick. Actually, the 3Dcane is modeled through consideration of real-time movements for a thorough understanding of the concerned person's state, including fall detection. To note, the 3DCane applies a multistage thresholding framework based on an accelerometer. Experiments have revealed that the fall-detection algorithm appears to be robust in term of detection rate and false positive rate.

I. INTRODUCTION

Owadays, the world has witnessed remarkable demographic changes culminating in the emergence of aging populations and life longevity phenomena [1]. The worldwide number of elderly, exceeding the age of 65, reached 760 million in 2010, and is expected to attain 1 billion by the end of 2020 [2], and 2 billion by 2050 [1]. Projections for 2150 have shown that the proportion of elderly people is expected to represent the third of the world population, which makes the goal of maintaining healthy aging a priority at the European level [START_REF] Ben | Behavioral wireless sensor network for smart home monitoring[END_REF].

In this context, using sensor networks likely to help collect various measures on the persons' condition, or monitor any suspicious change in their environment, stands as a very favorable solution for many reasons. Economically, monitoring elderly persons while safeguarding their usual living environment helps greatly in reducing nursing costs by specialized staff at a hospitals or nursing care units home. A significant contribution is related to the old person's psychological and social aspects, as it is thanks to the discreet and imperceptible monitoring, that the sense of security, respect for privacy and autonomy could be preserved. Indeed, mobility devices and personal assistance are strongly desired to ensure a certain independence of the elderly [START_REF] Warnock | Older users, multimodal reminders and assisted living technology[END_REF]. In this regard, used by a large number of old people, the cane constitute a massively versatile assisting device thanks to the simplicity and precious help it may provide.

A new discipline called e-health [START_REF] Eysenbach | What is e-health[END_REF] has emerged, as a bridge between the new information-communication technology and public health [START_REF] Pagkalos | SENHANCE: A Semantic Web framework for integrating social and hardware sensors in e-Health[END_REF].In this respect, e-health has highlighted certain elderly related health problems and dependence, with the particular aim of solving the aging population relating problems. In a bid to improve the elderly living conditions, several solutions integrating new technologies within the health system have been proposed by specialist in this area. This new field of research is intended to help grant a privilege to users by facilitating life and making it rather convenient. In fact, its applications' results on the human being's life is valued and required by society as several human needs can be satisfied by means of implementing such e-health applications.

It is worth noting that there exist several e-health systems applying the cane as a critical health support device, for instance the Co-Robot cane project [7] initially designed to help the blind use the cane as a guiding element and a recognition device of the environment. We can mention also the AID project [8] that proposes to equip a walking cane with several sensors useful for measuring the user's pulse, blood pressure and body temperature when the forearm is in contact with the cane. The detected information is displayed on LCD (Liquid Crystal Display). Systems, which use sensors to detect information derived from the environment or human body. They then process the acquired information locally through dedicated applications to provide indicators on the health status and efforts amount exerted by the monitored public.

In turn, the CANet project [START_REF] Val | CANet project : a monitoring system for people with disabilities using their walking stick[END_REF] and Smart Cane [START_REF] Jordan | The SmartCane System: An Assistive Device for Geriatrics[END_REF] constitute also other projects that serve to monitor a person via sensors instrumenting a connected walking cane. These applications introduce new analysis-executing methods and the necessary remote monitoring process without the need to move. They offer safe data exchange methods likely to facilitate the sharing of digital content among a local or remote processing center as well as the sensors that help 3DCane: a monitoring system for the elderly using a connected walking stick Abdelfetteh LACHTAR, Thierry VAL, Abdennaceur KACHOURI Laboratory of Electronics and Information Technology University of Sfax, ENIS, BP 1173, Sfax, 3038, Tunisia lachtar.abdelfetteh@gmail.com, thierry.val@irit.fr, abdennaceur.kachouri@enis.rnu.tn N collect the natural environment related data.

Actually, the CANet project [START_REF] Val | CANet project : a monitoring system for people with disabilities using their walking stick[END_REF] constitutes a significant evolution in terms of offered features. It proposes to integrate a multitude of sensors tracking the elderly health status. Unlike other projects [7] [8], this approach puts forward a real time vital data transmission framework. The gathered data are subsequently processed by means of specific systems. The idea of the CANet project lies in serving as a control and monitoring system. Gathering all these properties and being non-intrusive make it very scalable with respect to the proposed projects devoted to the same age group, which turns out to be very sensitive as a system. To this end, a new monitoring system is advanced through the present work, whereby a contribution to the CANet project is planned.

In recent years, fall related injuries and fractures have stood as the major causes of death amongst the elderly [START_REF] Salva | Incidence and consequences of falls among elderly people living in the community[END_REF]. In this respect, roughly 30% of people aged over 65 appear to score at least a single fall each year in the US [START_REF] Rizzo | Health care utilization and costs in a medicare population by fall status[END_REF]. The statistics are almost three times higher for people living in nursing homes [START_REF] Kannus | Fall-induced deaths among elderly people[END_REF]. Among the common fall engendered injuries one can cite the damage of soft and connective tissues, bone fractures and head injuries [START_REF] Tinetti | Prevention of falls among the elderly[END_REF][START_REF] Runge | The cost of injury[END_REF][START_REF] Lord | Falls in older people: risk factors and strategies for prevention[END_REF]. As a matter of facts, the lack of autonomy proves to stand as a serious threat to the elderly population's health condition. In addition, the induced injuries can also lead to an average annual cost of health care of about $ 20,000 per person [START_REF] Rice | Cost of injury in the United States: a report to congress[END_REF], amounting to an estimated cost of more than $ 12.6 billion for those aged 65 [START_REF] Rubenstein | Falls in the nursing home[END_REF][START_REF] Tinetti | Falls, injuries due to falls, and the risk of admission to a nursing home[END_REF].

It is worth noting that there exist several systems that apply subsequence matching as a fall detection tool using the cane. Noteworthy, Subsequence matching constitutes a technique to measure the similarity between two sequences to recognize human activities and positions (sitting, lying on the left side, lying on the right side, lying on one's back, walking, running etc) which are registered as signals in a special database. The SMARTFALL process [START_REF] Lan | SmartFall: An Automatic Fall Detection System Based on Subsequence Matching for the SmartCane[END_REF], is an example of fall detection systems for a Smart Cane [START_REF] Jordan | The SmartCane System: An Assistive Device for Geriatrics[END_REF]. It uses subsequence matching process to distinguish a fall from out of the frequent daily activities. The system allows a fall detection rate of almost 100%, but the false positive rate for a variety of daily activities is low due to the close similarity between the fall sequences and other similar activities such as lying on one's lap. The problem attached to subsequence matching lies in the fact that a fall sequence may change depending on the surrounding environment, which makes a fall is not always detectable and recognizable. In our paper, we used a multistage thresholding method with multiple parameters (linear acceleration and acceleration due to gravity), which implies an ongoing comparison of sensor data versus predefined thresholds. Indeed, a multi-stage threshold determination process applies more than a single threshold. All the thresholds must be exceeded in a particular sequence over a certain period of time to trigger the final alarm.

Hence, the present paper proposes a novel method along its associated tools necessary for monitoring the elderly while using their walking stick. In this regard, we consider to propose 3DCane as a system that helps tracks the elderly movements even more visually using their walking stick in accordance with the CANet project procedures [START_REF] Lord | Falls in older people: risk factors and strategies for prevention[END_REF], as a monitoring system for people with disabilities through their walking stick. In fact, the system allows to display a 3D model of the cane and its graphic animation based on actual movements obtained through a wireless data transmission system from sensors on the cane. The system's major function consists in detecting any potential fall through the cane by generating a voice alert within a smart home.

The remainder of this paper is organized as follows: Section 2 is devoted to provide an overview of the CANet system, including the relevant hardware and software architectures. Section 3 concern the design and the 3D sensing details along with the modeling algorithms developed and experimentally evaluated in terms of detection rate, and false positive rate in Section 4. As for section 5, it bears the major concluding remarks as well as some suggested horizons and perspectives of possible potential improvements of the 3dCane system. A novel application of the cane 3D model, along with its graphic animation and fall detection are presented. The global architecture of the CANet project is presented in figure 1 by Sabri Khsibi [START_REF] Khsibi | cane sensor networks for elderly monitoring[END_REF]. Every cane user sends data to the access point, while data are transmitted to a data collection server prior to treatment via a special data processing device.

II. SYSTEM ARCHITECTURE

With regard to the present work, the system is conceived to involve the following parts, namely: (i) a transmitter node positioned on the cane, (ii) a receiver node as well as (iii) a data analysis terminal for the 3DCane application. As illustrated in figure 1, the sensor node measures the sensor emitted data and sends them to the receiver using a Radio network processor. The software environment applied to fit for the experiment is Matlab 2014a with the fall-detection code being written in C language on a Windows XP PC.

Concerning the transmitter, it consists in a Wino Node [START_REF] Van Den | WiNo : an emulation platform for rapid prototyping and engineering of wireless sensor network protocols[END_REF] equipped with a diversity of sensors, namely, an accelerometer, a gyroscope, a magnetometer, a temperature sensor and a radio transmitter RF22. In this application, we used initially a three-axis accelerometer of an adafruit trademark reference LSM303 and a three-axis magnetometer of an adafruit trademark reference LSM303.

At this level, the sampling rate is set to 100Hz, a bandwidth exceeding the characteristic response of human movement. Each triaxial acceleration is statistically calibrated for the sake of correcting any possible axis tilt due to the device orientation on the subject or lower back tilt of the subject. For the purpose of implementing the algorithm that helps detect a fall suffered by an aged person, the gateway monitor the sensor node transmitted acceleration and calculates several parameters including the linear acceleration and the gravity related one.

To note, the Wino node [START_REF] Van Den | WiNo : an emulation platform for rapid prototyping and engineering of wireless sensor network protocols[END_REF] is based on the Arduino architecture, as it should be easily interfaced with real sensors. The Arduino module used in this card is a Teensy 3.1. It is based on an ARM Cortex M4 processor and offers several advantages. Unlike the majority of Arduino modules, this one has an electronic design enabling standby. It has a very favorable processing capacity ratio / consumed energy, which will allow the integration of low-consuming communication protocols such as 6LoWPAN in the future. The dimensions of a wino node are very limited as seen in Figure 2, allowing its easy integration in operational systems such as the 3D cane. The transmitter is positioned on the cane, as shown in Figure 3.

III. THE 3DCANE APPLICATION FUNCTIONING ALGORITHM

In this section, we detail our 3DCane algorithms functioning system such as the determination of absolute orientation and fall detection algorithm.

Prior to executing the algorithms implementation, we have to initially detail the cane orientation, with the X, Y and Z axes figuring on the cane as shown in Figure 4.

A. Absolute orientation

The applied orientation calculation system is shown in Figure 5. The calibrated accelerometer signal is used to obtain the roll and pitch via equations 2 and 3. As for the magnetometer calibrated signal, it is applied to compute the Yaw through equation 6. The accelerometer is intended to provide a measurement based on the linear acceleration and acceleration due to gravity [START_REF] Badura | Acceleration trajectory analysis in remote gait monitoring[END_REF]. Still, a major problem related to the accelerometers consists in the fact that they help measure both of the linear acceleration and that related to gravity. As it cannot distinguish between these two accelerations, it turns out to be critically necessary to separate both of the acceleration types (gravity and motion) through the use of a special filter.

On the X axis, for instance, the gravity relating acceleration can be calculated as follows:

Initially Xg = 0.

(1) With alpha = 0.5 (as presented in [START_REF] Abyarjoo | Implementing a Sensor Fusion Algorithm for 3D Orientation Detection with Inertial/Magnetic Sensors[END_REF]) and X is the value of acceleration on the x-axis provided by the accelerometer.

Using the accelerometer output, the rotation around the X axis (roll) and the Y axis (pitch) can actually be calculated. On considering the Accel_X, Accel_Y and Accel_Z as the accelerometer measurements (gravity acceleration) in the X, Y and Z, then equations ( 2) and (3) blow, would demonstrate how to calculate the angles Roll and Pitch [30]:

² (2) ² (3)
If mx, my and mz are calibrated and normalized magnetometer outputs, and α, β and γ respectively stand for roll, pitch and yaw, the heading appears to be computable through equation ( 6). Equations 4 and 5 are applied to transform the magnetometer reading to the horizontal plane.

Once the magnetometer data appear on the flat plane, equation 6 would then get a reliable calculation.

(4) (5) (6) Following the calculation of the absolute orientation we turn to representing this particular step animation. In a first place we undertake to analyze the sensors' derived data when the elderly is in the walking process (see figure 6). After several walking related analyses, one is able to recognize that when the elderly is walking, the linear acceleration on the z and x axes tends to increase, exceeding 0.7 m/s 2 , with a time delay that does not exceed 0.3 second. To this end, a simple algorithm has been implemented to help detect a particular step then for representation in the graphic animation.

Through the cane graphic modeling, one might well differentiate between three activities: walking, standing and lying on lap. Yet, the related problem lies in recognizing how a fall can be depicted.

B. Fall detection algorithm

Actually, the fall relating principle must be well understood for an effective fall-detection algorithm to be constructed. For this reason, more than 200 falls have been performed with the cane at different positions (forward, backward and side falls), while the linear acceleration as well as the gravity related data have been entirely displayed. An analysis of the linear acceleration data reveals well that for the entirely of falls made by the elderly, the linear acceleration value appears to perpetually remain superior to 5 ms. So, for the fall validation purposes, the gravity data related acceleration, and the reached findings prove to reveal that following each fall, the acceleration on the y axes appear to remain close to zero as depicted in figure 11. It has been assumed and checked that the cane would follow a similar process as that of a free fall, even in case the user loses control of the cane. The free fall case has been modeled, with the maximum acceleration level being computed. Following the linear acceleration data analysis, it has been discovered that for all free falls, the linear acceleration value does not seem to exceed 5 ms, as displayed in figure 12, below. Hence, based on the sensor data analysis derived from figures 6 and 7, one can well state that a cane user's typical fall turns out to consist of a three step process: (i) falling, (ii) horizontal position, (iii) inactivity.

During the fall phase, the user appears to lose balance and fall on the ground in an accelerated motion. An extensive experimentation leads us to discover that the minimum threshold proves to be 5 m/s².

Following the fall phase, the identifiable stage is reached by tilting the cane. The latter's position turns out to be almost fully horizontal, and the gravity related acceleration figuring on the Y axis is almost 0 m/s². The inactivity step is obviously the easiest step to model and detect. A thirty-second period has been selected, during which the cane stands still, lie motionless, for the actual fall to be confirmed. Otherwise, it means that the person has resumed his cane to keep walking, the fall is less serious, or it is simply a control loss of the cane by the person.

After identi The implemented fall detection algorithm is depicted in Figure 13, below.

IV. RESULTS AND PERFORMANCE ANALYSES

In a first test, the application GUI has been assessed in various situations prior to testing the fall detection algorithm.

A. Activity recognition

The 3DCane GUI resulting application allows a visualizing of the real time Cane status using a 3D display representing its absolute orientation. It also helps recognize the number of steps. The interface representation interface is shown in Figure 14.

Fig. 14. GUI 3DCane application

The cane 3D modeling, together with its movements, appears to be helpful in identifying its condition as well as the user's status. Once a fall is detected, the application triggers a voice alert. In addition, such an interface enables us to recognize whether the user is walking or in a standing still position.

B. Fall detection experimental platform

A secure fall reserved platform has been constructed for experimental purposes. It consists in a soft cushion for the person to fall over without damage, and a harder surface for the cane. The cushion positions and orientations are adjusted for different fall positions ways. An elderly person has been selected to perform all the fall types. Slow walk: walking with the cane at a pace of less than one step per second.

Fast walk: walking with the cane at a pace of around two steps per second.

Sit and stand: standing up with the help of the cane from a sitting position. Swing: swinging the cane back-and-forth at around 1Hz with an angle less than 30± from the vertical axis.

Cane on lap: picking up the vertically oriented cane and placing it horizontally on the lap.

Free fall: simulates an unobstructed topple of the cane due to loss of control. The subject does not fall with the cane in this case.

The results, listed in table 2, appear to indicate well that the algorithm is robust in terms of false-positive rate while perfectly solving the sit and stand as well as lay on lap problems. Indeed, the applied system seems to be more accurate than the Smart-fall one.

V. CONCLUSION

In the present work, a novel method has been developed whereby a real-time monitoring process of disabled people is advanced using through the use of an accelerometer and a gyroscope equipped walking cane. Real time data have initially been displayed to analyze the accelerometer and the magnetometer movements for a fall detection algorithm to be conceived. Then, a 3DCane application has been carried out for the walking stick state real-time visualization to replace, so as to control the elderly movement. Noteworthy, the proposed monitoring system will be soon ready for real tests in homes exclusively inhabited by old people. Several experiments simulating various fall types have been conducted to evaluate the 3DCane performance. The findings prove to indicate that the algorithm turns on to be able to detect almost all the experiment related falling cases while achieving low falsepositive rates for the entirely of the non-falling activities.

One of the future research perspectives is to implement an algorithm through which the number of steps can be computed by means of the cane. As the cane is equipped with other types of sensors, such as temperature and gyroscope, we are planning to investigate the accuracy based inference possibility with regard to these sensors. We also envisage conducting large-scale clinical trials to further validate the 3DCane application effectiveness. Finally, we plan to implement a special architecture likely to help ensure interoperability persistent between the cane and other items or devices connected to the smart home or to the Internet in general. For instance, we intend to trigger a remote alarm, open the house doors to facilitate the arrival of relief, and send Smartphone messages to the emergency operating medical personnel whenever an elderly person falls and an alert message is emitted through his / her smart cane sends an alert message.

Fig. 1 .

 1 Fig. 1. The CANet Global architecture.

Fig. 2 .

 2 Fig. 2. A Wino node prototype and its commercial version[START_REF] Van Den | WiNo : an emulation platform for rapid prototyping and engineering of wireless sensor network protocols[END_REF].

Fig. 3 .

 3 Fig. 3. Connected cane prototype equipped with a wino and its battery

Fig. 4 .

 4 Fig. 4. representation of the X, Y and Z axes.

Fig. 5 .

 5 Fig. 5. Orientation calculation system

Fig. 6 .

 6 Fig. 6. Data of linear acceleration when walking with the cane.

Fig. 7 .

 7 Fig. 7. linear acceleration data with a backward fall.

Fig. 8 .

 8 Fig. 8. linear acceleration data with a left side fall.

Fig. 9 .

 9 Fig. 9. linear acceleration data with a forward fall.

Fig. 10 .

 10 Fig. 10. linear acceleration data with a right side fall.

Fig. 11 .

 11 Fig. 11. acceleration due to gravity data when falling with the cane.

Fig. 12 .

 12 Fig. 12. linear acceleration data with a free fall.

Fig. 13 .

 13 Fig. 13. fall detection algorithm.

TABLE 1 THE

 1 FALL DETECTION RATE (30 TRIALS) FOR DIFFERENT TYPES OF FALLS.

	Project	Cane3D	Smart fall
	Forward	100%	100%	100%
	Backward	96.7%	93.3%
	Side	100%	100%
	Forward: simulates a face down fall due to trip over.
	Backward: simulates a fall on the back or bottom due to a
	slip.
	Side: simulates a sideward fall due to balance loss.
	The table 1 figuring results prove a detection rate of almost
	100% for the three fall types, as performed by the elderly.

TABLE 2 THE

 2 FALL DETECTION RATE (30 TRIALS) FOR DIFFERENT TYPES OF FALLS.

	Project	Cane3D	Smart fall
	Slow walk	0%	3.3%
	Fast walk	0%	0%
	Swing	0%	0%
	Sit and Stand	3.3%	16.7%
	Lay on lap	3.3%	10%
	Free fall	0%	0%