Issam Mabrouki
email: issam.mabrouki@telecom-bretagne.eu

Gwillerm Froc
email: froc@tcl.ite.mee.fr

Xavier Lagrange
email: xavier.lagrange@telecom-bretagne.eu

On the Data Delivery Delay taken by Random Walks in Wireless Sensor Networks

Keywords: Wireless Sensor Networks, Random Walk Theory, Performance Evaluation

In recent years, the use of random walk techniques in wireless sensor networks has attracted considerable interest among numerous research efforts. The popularity of this approach is attributed to the natural properties of random walks such as locality, simplicity, low-overhead and inherent robustness. However, throughout the variety of research works that assess the effectiveness of random walk techniques, most results are derived from a qualitative view or by means of simulations. Furthermore, when analytical tools are used, the obtained results often provide bounds on various performance metrics of interest, which may have little consequences for practical applications. Instead, our goal in this paper is to quantify the effectiveness of such techniques based on the derivation of closed-form expressions.

In particular, we focus on the data delivery delay taken for the random walk to deliver messages from sensor to sink nodes and study its statistics through closed-form derivations.

I. INTRODUCTION

Wireless Sensor Networks (WSN) have been one of the most prosperous research areas in recent years thanks to its wide spectrum of potential applications, including environment and habitat monitoring, healthcare application, home or industrial automation and control, precision agriculture and inventory tracking [START_REF] Akyildiz | A survey on sensor networks[END_REF]. Faced to this general trend of application diversification, large amounts of research being done in the WSN area are trying to provide useful tools and design methods for better architectures and protocols [START_REF] Karl | Protocols and Architectures for Wireless Sensor Networks[END_REF].

Most application scenarios for WSN involve small devices called sensor nodes, which are equipped with sensing capabilities, wireless communication and limited power supply, CPU and memory. On top of that, sensor nodes are often supposed to operate unattended and under strict energy constraints. Such adverse conditions make the design of robust, scalable and energy efficient systems a considerable challenge. The extensive research in this field, though, allowed to learn a few principles for the design of efficient WSN [START_REF] Karl | Protocols and Architectures for Wireless Sensor Networks[END_REF]. For example, topology-driven algorithms are at a disadvantage for such networks as they induce an excessive amount of communication, which is problematic for WSN.

In the search of an alternative solution, many earlier recent research efforts have investigated the use of randomization to build robust, scalable and energy efficient protocols in the context of WSN [START_REF] Dimakis | Geographic gossip: efficient aggregation for sensor networks[END_REF]. One example consists of the use of random walks to convey data from a source node to a destination one. The use of this technique is not new and has been extensively explored in many networking models providing a variety of algorithms including routing [START_REF] Servetto | Constrained random walks on random graphs: routing algorithms for large scale wireless sensor networks[END_REF], self-stabilization [START_REF] Dolev | Random walk for self-stabilizing group communication in ad hoc networks[END_REF], data gathering and query processing in wireless networks [START_REF] Avin | Efficient and robust query processing in dynamic environments using random walk techniques[END_REF], [START_REF] Lima | Random walks on sensor networks[END_REF], [START_REF] Mabrouki | Random walk based routing protocol for wireless sensor networks[END_REF], peer-to-peer networks [START_REF] Gkantsidis | Random walks in peer-to-peer networks[END_REF] and other distributed systems.

However, throughout the variety of research works that assess the effectiveness of random walk techniques, most results are derived from a qualitative view or by means of simulations [START_REF] Servetto | Constrained random walks on random graphs: routing algorithms for large scale wireless sensor networks[END_REF]. Furthermore when analytical tools are used, the obtained results often provide bounds on various performance metrics of interest [START_REF] Avin | The power of choice in random walks: an empirical study[END_REF], [START_REF] Lv | Search and replication in unstructured peer-to-peer networks[END_REF]. For example, different authors are interested in the well studied concept of cover time, which is the expected time taken by a random walk to visit every node in a graph. This property is relevant to a wide range of algorithmic applications [START_REF] Avin | Efficient and robust query processing in dynamic environments using random walk techniques[END_REF], [START_REF] Bisnik | Optimizing random walk search algorithms in P2P networks[END_REF], and various methods of bounding the cover time of graphs have been thoroughly investigated [START_REF] Feige | Deterministic approximation of the cover time[END_REF], [START_REF] Jonasson | On the cover time of planar graphs[END_REF]. Recently, it has been proven that for any size-n geometric graph with connectivity radius r, when r = Θ(r con )1 then w.h.p. 2 the optimal cover time behaves as O n ln(n) where r con growing as O( ln(n)/(πn)) is the critical radius to guarantee connectivity w.h.p. [START_REF] Avin | On the cover time and mixing time of random geometric graphs[END_REF].

There are other properties of the random walk also that need to be evaluated. One is the data delivery delay, which is the time required for the random walk to deliver a message from a given node to a destination. This property is of great interest in many WSN applications where the primary task of the network is to gather information from a particular location [START_REF] Duarte-Melo | Data-gathering wireless sensor networks: organization and capacity[END_REF]. Such systems are generally composed of two kinds of nodes: a large number of sensor nodes with limited storage, processing and communication capabilities, and a smaller number of sink nodes with more complex capabilities to gather, process and control data. Each sensor node performs some sensing of a particular confined area, and sends messages to sink nodes through a random walk motion.

Many recent research efforts have studied this random walk property on different classes of graphs. However, most of the obtained results often provide upper bounds on the data delivery delay and not a closed form derivation [START_REF] Bar-Yossef | RaWMS: random walk based lightweight membership service for wireless ad hoc network[END_REF], [START_REF] Fukś | Packet delay in models of data networks[END_REF].

Clearly, results of this nature may have little consequences for practical applications because the constants hidden in the bounds notation can be very large. Moreover, most of the works concentrate on the evaluation of the mean value of the data delivery delay [START_REF] Gelenbe | A diffusion model for packet travel time in a random multihop medium[END_REF], which makes difficult to get statistically robust conclusions about the relevance of the random walk efficiency. Instead, our take in this paper is to obtain a complete insight into the data delivery delay induced by a random walk by constructing an analytical model that owes much to the powerful analytic tools developed in the physics community [START_REF] Lindenberg | Lattice random walks for sets of random walkers. first passage times[END_REF], [START_REF] Liyanage | A bibliography on applications of random-walks in theoretical chemistry and physics[END_REF], [START_REF] Montroll | Random walks on lattices. II[END_REF]. In particular, this model enables us to study both the central tendency and the dispersion of the data delivery delay through close form derivations. Although our work mainly focuses on the data delivery delay, the level of abstraction of the proposed model is such that it can be applied to investigate other performance metrics of the random walk.

The remainder of the paper is organized as follows. A formal network model description followed by backgrounds and theoretical elements of random walk theory are given in section II. In section III, we focus on the data delivery delay with prior attention to two properties: the mean value and the dispersion. In section IV, we show that the data delivery delay can be approximated by a geometric distribution under some conditions. We provide some conclusions in section V and point out aspects that will be subject of future research.

II. RANDOM WALK MODELING

A. Network Description and Assumptions

We consider a WSN made of two kinds of nodes: a large number of sensor nodes and a smaller number of sink nodes with more complex capabilities to gather, process and control data. Each sensor node performs some sensing of a particular confined area, and sends messages to sink nodes in a multihop fashion, using other sensor nodes as relays and without any specific mapping between sensor and sink nodes.

We look more specifically at a common regular and periodic deployment topology where nodes are spread over an area of interest with a square pattern. As illustrated in Fig. 1(a), this pattern is formed by a periodically repeated square unit cell of size N × N containing N 2 nodes of which N 2 -1 are sensor nodes and one is a sink node.

Based on these underlying assumptions, the data delivery process can be described as follows. When a message reaches a given node, the next hop occurs uniformly at random only to the nearest-neighbors. Thus, in the case of 4-connectivity all the 4 nearest-neighbors away from the current node are equally likely with transition probability 1 4 . A message generated at a given sensor node performs then a random walk until it reaches for the first time a sink node where it will be trapped. At this moment, we consider that the data delivery process has occurred with success and then, we no longer care about the outcome of the walk.

With sufficiently large number of unit cells, we can assume that the envisioned network is infinite, and hence the considered deployment pattern corresponds to embedding nodes into the space of 2-dimensional integers, Z 2 . Recalling the assumption that there is no specific mapping between sensor and sink nodes, and given the structural periodicity of the envisioned pattern, we can consider that the formed network is equivalent to a torus lattice T of size N × N formed by connecting the opposite ends of a unit cell. The resulting structure, as it is shown in Fig. 1(b), contains a single sink node located at the origin whereas the other sites are sensor nodes. Based on this observation, the original network pattern and the torus lattice are used interchangeably. However, for the sake of simplicity, we actually investigate the data delivery process in reference to torus lattice T where every node r is labeled with (r 1 , r 2 ): r 1 and r 2 are integers such that 0 ≤ r 1 , r 2 ≤ N -1.

There are many motivations that prompted us to choose this network structure. First, many WSN applications are often desired to follow regular patterns for at least two reasons:

(i) convenience of deployment and (ii) to achieve a higher degree of connectivity and coverage. Second, this division of the network into unit cells suggests a very natural way of grouping nodes together (clustering). Such a clustering is often required by protocols in order to deal with a large number of nodes. Third, it is natural to start with regular patterns before addressing more complex ones of interest to us. Finally, this pattern is simple enough to allow a complete analytical treatment of the random walk problem while still being useful to incorporate specific key issues of WSN such as connectivity and coverage.

B. Problem Formulation and Characterization

We define, for n ≥ 1, P n ( r, s) the probability of being at node s after n hops, given that a message has been issued at node r. We also define F n ( r, s) the probability of arriving at node s for the first time on the nth hop, given that the walk started at node r. We shall refer to these probabilities as the node occupation probability and the first-passage probability respectively. By convention we have P 0 ( r, s) = δ r s and F 0 ( r, s) = 0. We denote also by P ( r, s|z) and F ( r, s|z) the generating functions [START_REF] Lando | Lectures on Generating Functions[END_REF] associated with {P n ( r, s)} n∈N and {F n ( r, s)} n∈N respectively. Hereafter we present a wellknown classical relation extensively used in random walk theory, and upon which the theoretical results derived in this paper rely. For proof, refer to [START_REF] Hugues | Random Walks and Random Environments[END_REF].

F ( r, s | z) = P ( r, s | z) -δ r s P ( s, s | z) , r, s ∈ T. (1)
A key issue in random walk problem is the resolution of the following question: how likely does the walk evolve in the future under some initial conditions? Answering this question consists in finding an explicit expression of P ( r, s | z), which completely determines the node occupation probability distribution. Globally, throughout the large number of interdisciplinary works in random walk theory, the exact closed-form solution was mostly carried out under restrictive conditions such as the periodicity of the network, the homogeneity of the system and the infiniteness of the structure on which the random walk takes place. Among these special cases, the problem of random walk on finite lattices with periodic boundary conditions (i.e., toroidal lattices) has been extensively studied. Montroll and Weiss [START_REF] Montroll | Random walks on lattices. II[END_REF] originally proposed this special problem and solved it for k-dimension. In particular, in the case of a torus lattice, they established an explicit expression of P ( r, 0 | z) as follows.

Lemma 2. P ( r, 0 | z) can be expressed as

P ( r, 0 | z) = 1 N 2 N -1 m1=0 N -1 m2=0 e i 2π N m1r1 e i 2π N m2r2 1 -z 2 cos( 2π N m 1 ) + cos( 2π N m 2 ) • (2)
Even though relation [START_REF] Avin | Efficient and robust query processing in dynamic environments using random walk techniques[END_REF] does not give a simple form of P ( r, 0 | z), it is of great importance and represents our basic relation upon which relies most of our contribution in this paper. In the following, we focus our attention on one interesting performance metric of the proposed random walk scheme and attempt to study its statistics through close form derivations. Generating function techniques and asymptotic expansion calculus are the key tools here and they are used in tandem to elaborate interesting results.

III. DATA DELIVERY DELAY ANALYSIS

A primary objective of the proposed random walk scheme is to perform successful data delivery while achieving desired guarantees on delay times. It is worth noting that although there are different categories of delay times in WSN depending on application requirements, the time or the number of hops experienced by a message generated at a sensor node before being trapped at the sink node represents one of the significant metrics to measure the random walk performance. We refer to this delay time as the data delivery delay.

Formally, given a sensor node r ∈ T, let D N ( r) be the data delivery delay defined at this sensor node. D N ( r) is a discrete random variable taking nonnegative integer values. Thus, it can be characterized by its probability distribution. Once the probability distribution of D N ( r) is determined, all the statistics of the data delivery delay can be theoretically derived. Unfortunately, it is not a simple matter to derive this probability distribution. This difficulty is well known in random walk theory while studying first-passage times [START_REF] Hugues | Random Walks and Random Environments[END_REF], [START_REF] Spitzer | Principles of Random Walk[END_REF]. Indeed, most of the analytical works in this respect concentrate on the derivation of either the short-or the longtime behaviors of first-passage times and not on the exact expression of the probability distribution.

In spite of this, we show in this paper that many statistical properties of the data delivery delay can be deduced by calculating its first-or higher-order moments using generating function techniques. In particular, we are interested in this section in central tendency, dispersion and their dependencies on key model parameters. These two basic properties can be reflected by calculating for example the mean value and the standard deviation of random variable D N ( r). To do this, we first determine the generating function associated with random variable D N ( r) and then, we apply the generating function techniques.

Proposition 1. Let D N ( r | z) be the generating function of random variable D N ( r). D N ( r | z) can be then expressed as D N ( r | z) = P ( r, 0 | z) P (0, 0 | z) . ( 3
)
Proof: From the definition of D N ( r), we can see that the probability of a message generated at sensor node r to be gathered at the sink node on the n-th hop is equal to the probability of being at the origin for the first time on the n-th hop, given that the walk started at node r, that is, first-passage probability F n ( r, 0). Thus, in terms of probability notation, we have By multiplying both sides of this relation by z n and summing over all n, we obtain

Pr D N ( r) = n = F n ( r, 0), n ≥ 0.
D N ( r | z) = F ( r, 0 | z).
Finally, from Lemma 1, we obtain (3).

A. Mean Value 1) Generating Function Analysis:

Generally, the most frequently used measure for describing central tendency is the mean value or in probability parlance the expectation. We propose here to study this property for the data delivery delay by calculating its expectation denoted by E D N ( r) . Applying generating function techniques, mean value E D N ( r) can be derived by taking the limit of the first-derivative of generating function D N ( r | z) as z → 1 -, so that

E D N ( r) = lim z→1 - ∂ ∂z D N ( r | z).
Although this relation does not give an explicit solution of the mean value, we can fortunately extract a closed-form expression from the Taylor's series expansion of generating function D N ( r | z) at point z = 1. Indeed, if D N ( r | z) is holomorphic at z = 1, then the limit of its first derivative with respect to z as z → 1 -is nothing but the first-order term of its Taylor's series expansion at point z = 1. To evaluate this Taylor's series expansion, we proceed as follows. We first estimate the asymptotic expansion of P ( r, 0 | z) as z → 1 -, which is provided by [START_REF] Jonasson | On the cover time of planar graphs[END_REF] in Appendix A. Second, by setting r = 0 in ( 16), we derive the asymptotic expansion of P (0, 0 | z) as z → 1 -and then, after elementary calculus, we prove that function D N ( r | z) = P ( r, 0 | z)/P (0, 0 | z) is holomorphic at z = 1. So, it can be represented by its Taylor's series expansion at point z = 1, which is given by [START_REF] Karl | Protocols and Architectures for Wireless Sensor Networks[END_REF] in Appendix B. By differentiating [START_REF] Karl | Protocols and Architectures for Wireless Sensor Networks[END_REF] with respect to z and taking the limit as z → 1 -, we obtain the following result:

Result 1. Mean value E D N ( r) can be written in a closedform expression as

E D N ( r) = N 2 ϕ N (0, 1) -ϕ N ( r, 1) + 2r 2 (N -r 2 ), (4)
where ϕ N ( r, z) is defined by [START_REF] Gelenbe | A diffusion model for packet travel time in a random multihop medium[END_REF] in Appendix A.

2) Discussion: Some general remarks can be drawn from the previous analysis. First, from the Taylor's series expansion of generating function D N ( r | z) at point z = 1 given by [START_REF] Karl | Protocols and Architectures for Wireless Sensor Networks[END_REF] in Appendix B, the value of D N ( r | z) at point z = 1 is equal to unit, which represents the probability that a message issued from sensor node r is ever gathered by the sink node. This means that the proposed data delivery process is certain. This result is at first glance surprising since we have assumed that the original network is infinite (a large number of unit cells), which implies that there would be potential infinite paths allowing messages to escape sink nodes and diffuse indefinitely around the entire network without being trapped. However, since the network is equivalent to a torus lattice, a finite-size effect arises precluding messages to continuously move away from sink nodes.

Second, referring to (4), the mean value of the data delivery delay is finite. This is not a trivial property because it means that only short paths between sensor and sink nodes are significant. The main reason is that, with a regular and periodic deployment of sink nodes, there are no network areas where a message can spend a lot of time without meeting a sink node. Third, the dependance of E D N ( r) on parameter N and hence, indirectly on the concentration of sink nodes highlights the scalability property of the proposed scheme. That is, if additional sensor nodes are added, the mean value does not change provided that the concentration of sink nodes (or equivalently parameter N ) remains constant. This is once again a simple manifestation of the regular and periodic deployment of sink nodes, which ensures that the maximum distance between sensor and sink nodes (∼ N ) is very small compared to the effective network size.

Let us now study the spatial distribution of expectation E D N ( r) over torus lattice T. A first comment is that, for symmetric considerations, coordinates r 1 and r 2 play similar roles in the expression of E D N ( r) although at first glance it is not obviously straightforward from (4). This property is observable in Fig. 2 where E D N ( r) is depicted as a function of position r = (r 1 , r 2 ) over a unit cell of size 10 × 10. Other values of parameter N are possible to plot, however, our goal is to show numerical examples of practical interest. It should also be emphasized that the observed properties are not limited to value N = 10 but are valid for all finite ones.

The first important feature of Fig. 2 is the fact that the mean number of hops required to reach the sink node increases initially with a high rate as we move away from the origin towards the middle region, where E D N ( r) saturates. The relatively low value of E D N ( r) observed around the origin (or the sink node) means that messages generated in vicinity of the sink node do not spend a lot of time exploring the neighborhood they were created in and they are trapped quickly at early time. It is then found the closer a sensor node is to the sink node, the faster the data delivery process is performed. However, far away from the sink node, generated messages can escape their initial territory and visit more new sensor nodes before being trapped, which argues the higher values of E D N ( r) with low slope in the middle of the unit cell. As we can see in the plot, though, there is a crossover in this behavior.

Beyond the middle region, the value of E D N ( r) decreases again with low slope as we move towards the other corners. This crossover behavior is due to the periodicity property of the torus lattice, which means that the opposite corners of the unit cell are connected.

To get deeper insight into the mean value efficiency induced by the random walk scheme, we propose now to compare it with the analogue one if the shortest path routing (SPR) scheme is used. This implies that whenever a message is generated at a given sensor node, it will be rather trapped by the closest sink node. At a given sensor node r, let us define D SP R N ( r) as the data delivery delay induced by the SPR scheme. Therefore, we readily obtain D SP R N ( r) = min(r 1 , N -r 1 ) + min(r 2 , N -r 2 ). As we should expect, the SPR scheme will achieve the optimal data delivery delay due to its deterministic nature. For example, the minimum/maximum mean values achieved by the random walk scheme for a unit cell of size 10 × 10 exceeds the one achieved by the SPR scheme about one hundred/19 times respectively. In fact, this efficiency is achieved at the expense of sophisticated capabilities required for explicit route discovery/repair computations, and maintaining explicit state information about available routes at the nodes. However, optimality is not generally a fundamental issue in many WSN applications. Instead, the focus is more on properties such as scalability, robustness and load balancing.

We investigate now the worst case of the mean value efficiency, which corresponds to the maximum value of E D N ( r) . This maximum value corresponds to the maximum possible distance between an arbitrary sensor node and its nearest sink node. This maximum distance occurs in the middle of the unit cell. Thus, if N is even, E D N ( r) is maximum only at the single position r = ( N 2 , N 2 ). In contrast, if N is odd, the maximum value of E D N ( r) is reached at four positions, which are r = (⌊ N 2 ⌋+i, ⌊ N 2 ⌋+j) where the ⌊ . ⌋ symbol stands for the floor function and i, j = 0, 1. Merging the two cases into one, we can see that the maximum value of

E D N ( r) is always reached at position r M = (⌊ N 2 ⌋, ⌊ N 2 ⌋
). By a linear scale plot, we can show that E D N ( r M ) increases initially with a slow rate and then the increase is almost superlinear. However, the large range of produced values makes a semi-logarithmic scale more appropriate. This is illustrated in Fig. 3. The obtained curve suggests that E D N ( r M ) may follow a power law. The log-log plot described in Fig. 4, where both horizontal and vertical axis are plotted on a logarithmic scale confirms our prediction of a power law growth of E D N ( r M ) . Indeed, by a linear regression model, we can estimate the slope of the best straight line fitted to this plot. Finally, the result of the fit is E D N ( r M ) ≃ 0.97N 2.27 and the quality of the fit is very satisfactory with a coefficient of correlation equal to 0.99. Although this procedure is partially heuristic, the obtained fit formula could help practitioners to rapidly determine the concentration of sink nodes to be deployed in order to guarantee an upper bound of the mean value.

We turn now our attention to a simple example on how the previous analysis can be applied to a concrete scenario. We consider IEEE 802.15.4 enabled nodes with supported data transmission rate of 20 kbps. One reason for choosing the IEEE 802.15.4 standard stems from its suitability for the development and deployment of WSN. If we don't take into account the physical limitations posed by the radio medium, the time required for a message to perform a single hop is simply its size divided by the data transmission rate. Therefore, it is interesting to study the effect of varying the message size on the maximum mean value. This is illustrated in Fig. 5 where E D N ( r M ) (in seconds) is plotted as a function of parameter N for different message sizes.

As indicated in Fig. 5, the increase in message size at fixed values of parameter N leads to performance degradation. On the other hand, at a given message size, it is always possible to enhance the mean value efficiency by reducing parameter N , or say equivalently by increasing the concentration of sink nodes. However, this enhancement is lower-bounded by the maximum mean value achievable at the smallest unit cell size, which corresponds to N = 2. To illustrate this assertion, we can see from Fig. 5 that this lower bound is about 32 ms for a message size of 20 bytes, whereas it is equal to 128 ms for a message size of 80 bytes. Since in many applications of WSN sensor nodes often send only beep-like small messages to sink nodes to report their status, we find that routing messages based on random walk can achieve acceptable delay provided that the concentration of sink nodes is carefully tuned. For illustration purposes, we can see from Fig. 5 that in order to guarantee a delay threshold of 1 s, the unit cell size should not exceed N 2 = 8 2 , 6 2 , 5 2 , 4 2 nodes for a message size of 20, 40, 60, 80 bytes respectively. Thus, we can conclude that the random walk scheme can be viable in the scenarios where (i) applications do not require too stringent delay, (ii) the sensed data to be transmitted are of small sizes (tens bytes) and (iii) the concentration of sink nodes to be deployed is carefully managed.

B. Dispersion 1) Generating Function Analysis:

The dispersion of the data delivery delay is another basic property that indicates the degree of spread around the mean value. A commonly-used of dispersion is the standard deviation, is square root of the variance. In the context of the proposed random walk scheme, by knowing standard deviation the data delivery delay, we should be able to make statistically robust conclusions about the relevance of the mean value that was previously calculated. Indeed, a small standard deviation indicates that the values actually taken by the data delivery delay are clustered closely around the mean value thereby its probability distribution can be reasonably summarized by the mean value. However, a large standard deviation indicates that they are far from the mean value and hence the latter is a bad representative measure for the data delivery delay.

We propose here to derive the standard deviation of the data delivery delay and study its dependence on key model parameters. This study will provide us a somewhat different picture of the data delivery delay efficiency than we have previously obtained by considering the mean value alone. Denoting the variance by Var D N ( r) , the standard deviation is found by computing first the variance using generating function techniques and then taking the square root. So that,

Var D N ( r) = lim z→1 - ∂ 2 ∂z 2 D N ( r | z) + lim z→1 - ∂ ∂z D N ( r | z) - lim z→1 - ∂ ∂z D N ( r | z) 2 • (5)
We can see from this relation that only the first and second partial derivatives of generating function D N ( r | z) with respect to z at z = 1 -are involved while defining the variance of the data delivery delay. In a similar way as that is used for the calculation of the mean value, these partial derivatives can be expressed in an explicit form using the second order Taylor's series expansion of D N ( r | z) at point z = 1, which is provided by [START_REF] Karl | Protocols and Architectures for Wireless Sensor Networks[END_REF] in Appendix B. Plugging (17) into (5) leads to the following result:

Result 2. The variance of the data delivery delay can be written in exact closed-form expression as

Var D N ( r) = 4N 2 r 2 (N -r 2 ) ϕ N ( r, 1) + 1 3 N 2 (1 + 2N 2 ) ϕ N (0, 1) -ϕ N ( r, 1) + 2N 2 ϕ (1) N (0, 1) -ϕ (1)
N ( r, 1) + N 4 ϕ 2 N (0, 1) -ϕ 2 N ( r, 1) + 2 3 r 2 (N -r 2 ) 2N 2 -4r 2 (N -r 2 ) -1 (6)
where ϕ N ( r, z) is defined by [START_REF] Gelenbe | A diffusion model for packet travel time in a random multihop medium[END_REF] in Appendix A.

2) Discussion: Using this result, it is now straightforward to derive the standard deviation by taking the square root of both sides of (6). In the following, we propose to illustrate numerically the basic properties of the standard deviation and to revisit the main question, previously raised, as to whether the mean value already investigated would be a good summary of the data delivery delay. Fig. 6 depicts the typical form of how the standard deviation varies over the network. We set here N = 10. An important property to note from Fig. 6 is that the standard deviation exhibits a closely similar behavior to that found while studying the mean value. Indeed, the basic pattern is that, except near the corners or equivalently near any sink node, the standard deviation is reasonably similar throughout the network and achieves its maximum value in the middle of the unit cell. At first glance, the relatively small values of the standard deviation near the corners may mislead us to believe that the mean value can be considered as a good indicator for the data delivery delay. With the benefit of hindsight, we rather find that near the corners the standard deviation always exceeds the mean value regardless of the unit cell size. Furthermore, as we move away from the corners of the unit cell towards the middle region, the standard deviation increases rapidly but becomes nearly constant over most of the unit cell. This high dispersion results in a significant probability that the effective data delivery delay will be greatly different from the mean value. Therefore, the mean value provides us little information about what the data delivery delay actually will be, and it should not be interpreted as a representative value. It is largely for this reason that a treatment of the data delivery delay based only on the mean value is inadequate.

To have a deeper analysis of this question, it is now convenient to define CV D N ( r) as the coefficient of variation of the data delivery delay, which is defined as the ratio of the standard deviation to the mean value. Fig. 7 shows the spatial distribution of the coefficient of variation over a unit cell for N = 10. A key observation to note from this plot is that the coefficient of variation roughly changes around the corners but becomes nearly constant as we move far away. Note also that values greater than 1 are achieved around the corners where a maximum value is reached at node r m = (0, 1), but a slight decrease lying over a broad and flat plateau occurs towards the middle region in which a minimum value lower than 1 is achieved at

r M = (⌊ N 2 ⌋, ⌊ N 2 ⌋).
The expanse of the plateau can be characterized by more than 79% and 86% of the achieved values lying in the range [0.9, 1.1] for N = 10 and 20 respectively.

This peculiar behavior can be attributed to the proximity- sink effect. Indeed, consider a message that is generated in the vicinity of a given sink node. As already demonstrated while studying the mean value, this message does not spend a lot of time exploring the neighborhood it was created in and it is trapped quickly at early time on the average. If such a message happens to avoid the sink node, it is likely to have done so by reducing its proximity to the sink node, thereby significantly decreasing its likelihood of being trapped soon and tending to occupy as many nodes as possible on its way. This leads to very high variability, and so the standard deviation will greatly exceed the mean value. In contrast, when generated in the middle region, the message does not initially find itself in a preferential position, so any escape from its initial territory will likely transport it towards one of the four nearest sink nodes around it, thereby significantly increasing its likelihood of being trapped soon. This yields again high variability but the difference between the standard deviation and the mean value becomes no longer pronounced.

Let us now concentrate more specifically on the maximum and minimum values of the coefficient of variation achieved near the corners (at sensor node r m = (0, 1)) and at the middle of the unit cell (at sensor node r M = (⌊ N 2 ⌋, ⌊ N 2 ⌋)) respectively. We are interested here in how these typical values depend on parameter N or equivalently on the concentration of sink nodes. Our interest stems from the fact that the mean value, as previously demonstrated, achieves its minimum and maximum at sensor nodes r m = (0, 1) and r M = (⌊ N 2 ⌋, ⌊ N 2 ⌋) respectively, which makes particularly the following analysis a good benchmark for the data delivery delay efficiency.

Fig. 8 shows that the maximum value of the coefficient of variation, almost above 1, monotonically grows with N whereas the minimum value, markedly less sensitive to parameter N , varies a little but rapidly equilibrates to the constant value 1 as N increases. The latter behavior suggests a good evidence for nearly memorylessness property which characterizes both the exponential distribution and the geometric distribution with very small probability of success [START_REF] Feller | An introduction to probability theory and its applications[END_REF].

A heuristic explanation of such a property can be given as follows. Consider a message that is initially generated at

sensor node r M = (⌊ N 2 ⌋, ⌊ N 2 ⌋).
For sufficiently large values of N , it is always possible to neglect the distance traveled by the message during a given hop number n 0 in comparison with the distance required for the message to be trapped at the sink node. Thus, if the message has not been trapped by hop n 0 , the probability that it will be trapped after an additional n hops can be approximated closely by the original probability that it will be trapped after the very first n-th hop. This statement is nothing but one of the characterization of memorylessness property. Formally, this can be expressed in the form of Pr D N ( r M ) > n 0 + n | D N ( r M ) > n 0 = Pr D N ( r M ) > n . In passing, note that this property is not restricted to sensor node r = (⌊ N 2 ⌋, ⌊ N 2 ⌋), which corresponds to the maximum possible distance between an arbitrary sensor node and its nearest sink node, but can be extended to the surrounding region provided that N is large enough.

IV. GEOMETRIC DISTRIBUTION APPROXIMATION

The analysis of dispersion has shown a high spread of the data delivery delay around the mean value regardless of sensor node positions. As a consequence, the mean value is a poor indicator for the data delivery delay efficiency. It is therefore interesting to look at upper bounds for the data delivery delay rather than the mean value. The cumulative distribution function of the data delivery delay would give the probability that this delay is lower than a certain threshold. Unfortunately, the intractability of the exact probability distribution function makes this task difficult to be carried out. However, exploiting memorylessness property observed at the middle of the unit cell, and since it is also discrete, the data delivery delay at sensor node r M = (⌊ N 2 ⌋, ⌊ N 2 ⌋) can be reasonably approximated by a geometric random variable provided that N is sufficiently large (small concentration of sink nodes).

The geometric distribution by definition deals with a series of independent, identical trials (here, moves across nodes) each of which has only two possible outcomes, success or failure (here, trapping or move on) with probabilities that are constant from trial to trial. The geometric random variable is the number of trials needed to get one success (here, trapping), supported on the set {1, 2, 3, • • • }. Formally, we can therefore express approximately the probability that a message initially released at sensor node r M = (⌊ N 2 ⌋, ⌊ N 2 ⌋) will be trapped by the n-th hop in the form of Pr D N r M = n ≃ a(1-a) n-1 for all n ≥ 1, where 0 < a < 1 is the geometric parameter also referred to as the success probability [START_REF] Feller | An introduction to probability theory and its applications[END_REF]. In our case, this parameter corresponds to the probability that the message will be trapped while moving from one node to another.

In this simplest version of the model, only one parameter, namely a, determines the geometric distribution approximation. An estimate of a can be quickly obtained by remarking that expectation E D N ( r M ) can be related to a as E D N ( r M ) = 1/a if random variable D N ( r M ) is geometrically distributed. Under such a condition, the variance of D N ( r M ) can be also written as Var D N ( r M ) = (1 -a)/a 2 . In passing, note that the given estimate of a has obviously the necessary condition that E D N ( r M ) > 1, which is consistent with the results obtained while studying the central tendency of the data delivery delay. The cumulative distribution function of the data delivery delay at sensor node r M can be then approximately written as Pr D

N r M ≤ n ≃ 1 -1 - 1/E D N ( r M ) n . Knowing the exact value of E D N ( r M ) ,
which is given by Result 1, it is then possible to infer this cumulative distribution function as a function of parameter N . More interestingly enough, this enables us to find the value of N for a given percentile, or equivalently the concentration of sink nodes to be deployed while achieving a threshold delay with high probability.

It is now possible to assess the quality of the mean value achieved at sensor node r M by answering the question how likely the data delivery delay is effectively below this mean value. In probability parlance, this consists in calculating the probability

Pr D N r M ≤ E D N ( r M ) } = 1 -1 - 1 E D N ( r M ) E DN ( rM ) •
Remarking that 1/E D N ( r M ) decreases rapidly to zero as N increases (recall that E D N ( r M ) ≃ 0.97N 2.27 ), the above probability can be reasonably approximated by the constant value 1 -1/e ≃ 0.63. Concretely, this value indicates that nearly two-fifth of messages issued at the middle of the unit cell would experience a delay time larger than the mean value. This high variability makes it interesting to look at upper bounds for the data delivery delay. For example, applications with strict requirements on delay would benefit from estimating the data delivery delay with a high percentile.

For instance, we find that the 95-percentile is about three times as much as the mean value regardless of the unit cell size. Equivalently, this means that only 5% of the messages issued at the middle of the unit cell would spend at least three times as long as the mean value before being trapped.

V. CONCLUSION In this paper we addressed the problem of random walk to model data delivery in wireless sensor networks. In this approach, a packet generated from a given sensor node performs a random motion until reaching a sink node where it is collected. The primary objective of this work was to study the data delivery delay induced by a random walk taking place on a regular and periodic topology.

Three different studies were reported. First, we studied central tendency of the data delivery delay and derived a closed-form expression for its mean value as a function of sink node concentration. This study showed that the random walk can achieve acceptable performance in terms of data delivery delay in the scenarios where (i) applications do not require too stringent delay, (ii) the sensed data to be transmitted are of small sizes (tens bytes) and (iii) the concentration of sink nodes to be deployed is carefully tuned. Second, we derived a closed-form expression for the variance and showed how it varies with the concentration of sink nodes. However, the study of dispersion revealed a high spread of the data delivery delay around the mean value. So, a treatment of the data delivery delay based only on the mean value is inadequate. Third, the analysis of the coefficient of variation for small concentration of sink nodes argued for a reasonably memorylessness property and suggested a geometric distribution approximation of the data delivery delay. Exploiting this approximation, we assessed the effective quality of the mean value as a representative indicator for the data delivery delay. Indeed, we found that nearly two-fifth of messages issued far away from sink nodes would experience a data delivery delay larger than the mean value, and hence, applications with severe requirements on delay would rather benefit from estimating the data delivery delay with a high percentile.

To improve the data delivery delay efficiency, it is therefore necessary to avoid the "undesirable" aspects of random walks like visiting a node more than once or moving in the wrong direction. Several interesting ideas in this direction can be investigated in further work. For example, we can consider biased random walks that give priority to unvisited neighbors instead of choosing uniformly at random or issuing multiple copies of a message in parallel.

where functions c m1 (z) and S m1 (z) are defined as where α m1 (z) is the smaller root of the equation

c m1 (z) = z 2 -z cos( 2π N m 1 ) (8a)
X 2 - 2 c m1 (z)
X + 1 = 0 whose discriminant is positive for 0 < z < 1. Thus, we find

α m1 (z) = 1 -1 -c 2 m1 (z) c m1 (z) • (9)
Now, using partial fraction decomposition, we can write S m1 (z) as S m1 (z) = 1 -c 2 m1 (z) 1 -z 2 cos( 2π N m 1 ) 1 -c 2 m1 (z)

1 2 × α r2 m1 (z) + α N -r2 m1 (z) 1 -α N m1 (z) • (11)
Note that the summand involved in [START_REF] Feller | An introduction to probability theory and its applications[END_REF] is holomorphic over 0 < z < 1 for all 0 ≤ m 1 ≤ N -1. However, it diverges at z = 1 if and only if m 1 = 0. Thus, the singularity of P ( r, 0 | z) at z = 1 comes only from the first term of the sum given by [START_REF] Feller | An introduction to probability theory and its applications[END_REF]. It is convenient therefore to separate out the singular and non-singular parts of P ( r, 0 | z) as follows 1 -z 2 cos( 2π N m 1 ) 1 -c 2 m1 (z)

P ( r, 0 | z) = 1 N (1 -z)
1 2 × α r2 m1 (z) + α N -r2 m1 (z) 1 -α N m1 (z) (13)

Fig. 1 .

 1 Fig. 1. Dark-filled circles show sink nodes whereas sensor nodes are represented by light-filled circles.

Lemma 1 .

 1 F ( r, s | z) and P ( r, s | z) are related to each other according to the relation

Fig. 2 .

 2 Fig. 2. Spatial distribution of the mean value of the data delivery delay.

Fig. 3 .

 3 Fig. 3. Semi-logarithmic plot of E D N ( r M ) as a function of N .

Fig. 4 .

 4 Fig. 4. Fitting of E D N ( r M ) to a power law.

EFig. 5 .

 5 Fig. 5. Effect of message size on the maximum mean value.

Fig. 6 .

 6 Fig. 6. Spatial distribution of the standard deviation.

Fig. 7 .

 7 Fig. 7. Spatial distribution of the coefficient of variation.

NFig. 8 .

 8 Fig. 8. Effect of N on the maximum and minimum coefficient of variation.

1 -N m 1 )

 11 APPENDIX A ASYMPTOTIC EXPANSION OF P ( r, 0 | z) Before calculating the asymptotic expansion of P ( r, 0 | z) as z → 1 -, we propose first to simplify the expression of P ( r, 0 | z) given by (2) and to study its singularity at z = 1. By factorizing the denominator of the summand and using the addition theorems of trigonometric functions, we obtainP ( r, 0 | z) c m1 (z) cos( 2π N m 2 )× S m1 (z)

S m1 (z) = N - 1 m2=0 e i 2π N m2r2 1 -

 11 c m1 (z) cos( 2π N m 2 ) • (8b)Before studying the singularity of P ( r, 0 | z) at z = 1, we propose to simplify S m1 (z). The first step is to see from (8a) that 0 < |c m1 (z)| < 1 for 0 < z < 1. Using the exponential representation of trigonometric functions, S m1 (z) can be written asS m1 (z) = -2 c m1 (z) N -1 m2=0 e i 2π N m2(1+r2) e i 2π N m2 -α m1 (z) × 1 e i 2π N m2 -α -1 m1 (z)

-1 2 N - 1 m2=0 e i 2π N m2r2 1 -•

 211 α m1 (z) e -i 2π N m2 + α m1 (z) e i 2π N m2(1+r2) 1 -α m1 (z) e i 2π N m2Noting that |α m1 (z)| < 1, it is then possible to expand each sum involved in S m1 (z) by using successively the expansion1/(1 -x) = ∞ k=0x k and the identityN -1 m=0 e i 2π N mn = N for n = 0, ± N, ± 2N, • • • 0 otherwisewhich can be derived by remarking that the vectors e i 2π N mn form an orthogonal basis over the set of N-dimensional complex vectors. Therefore, we obtain S m1 (z

We recall the following notation:(i) f (n) = O g(n) means that exists a constant C and integer K such that f (n) ≤ Cg(n) for n > K. (ii) f (n) = Θ g(n) means that f (n) = O g(n) ; g(n) = O f (n) .

Event Em occurs with high probability (w.h.p.) if probability Pr(Em) is such that limm→∞ Pr(Em) = 1.

is holomorphic at z = 1. The first term involved in [START_REF] Fukś | Packet delay in models of data networks[END_REF] corresponds to the term m 1 = 0 in [START_REF] Feller | An introduction to probability theory and its applications[END_REF], and the second term, that is ϕ N ( s, z), corresponds to the sum over the range

To obtain the first-order asymptotic expansion of P ( r, 0 | z) as z → 1 -, let us successively expand the first term of P ( r, 0 | z) involved in Eq. ( 12) and then function ϕ N ( s, z) close to z = 1. Hence, the first term of P ( r, 0 | z) can be expanded as

Being holomorphic at z = 1, ϕ N ( r, z) can be represented by its first-order Taylor's series expansion at point z = 1, so that

N ( r, 1)(z -1) + o(z -1). (15) Finally, combining ( 14) with ( 15), the asymptotic expansion of P ( r, 0 | z) as z → 1 -can be written as

N ( r, 1)

APPENDIX B ASYMPTOTIC EXPANSION OF D N ( r | z) Using ( 16), the Taylor's series expansion of generating function D N ( r | z) as z → 1 -can be expressed as

N ( r, 1) -ϕ

N (0, 1) -6r 2 2 ϕ N (0, 1) -4N r 2 (1 + r 2 2 ) + 2r 2 2 (2 + r 2 2 ) (z -1) 2 + o(z -1) 2 .

(17)


Omar Krichen

Eric Anquetil

Nathalie Girard

Mickaël Renault

Renault

Online analysis of hand-drawn strokes for Geometry learning

Keywords: Pattern Recognition, and Intelligent Systems Processing, Pattern Recognition, and Intelligent Systems output page 2 2

This work takes place within the ACTIF project, in the context of the eFran call for projects that aims for active and collaborative learning promotion. This paper presents a pattern recognition and analysis system for Geometry learning in middle school. The goal is to allow students to draw geometric shapes on a pen-based tablet, given a teacher's instruction. To make the student active, the system have to recognize and analyze on the fly the hand-drawn student's productions in order to produce real-time visual, corrective, and guidance feedback. We base our work on the visual grammar CD-CMG 1 (Context Driven Constraints Multi-set Grammar), to model the domain prior knowledge and interpret the hand-drawn sketches on the fly. Our first contribution lies in adapting this grammar to the Geometry domain to cover the geometric objects taught in middle school curriculum. Although being expressive enough to model this large scope, the original formalism could not cope with the requirement of real-time analysis, given that the multiple interactions between geometric objects generate combinatorial issues. Our second contribution lies in extending the formalism to obtain acceptable performance for a real-time user interaction system. The first experiments on complex geometric figures drawing scenarios show that the proposed approach allows complexity and interpretation time reduction. We present also our result on another application domain, architecture plan sketching, to prove the generecity of our approach.

Introduction

Our work is in the context of e-FRAN ACTIF * project, which aims to use pen-based tablets in an educational context, mainly in French middle schools, to foster active learning. [START_REF] Chickering | Implementing the seven principles: Technology as lever[END_REF] In this paper, we focus on learning Geometry by drawing freely on a touch-tablet. Dynamic Geometry Software products are now an important part of teaching geometry. Their goal is to make geometric concepts understanding easier for the student by graphical construction, manipulation and visualization of figures. To our knowledge, the tools used in middle schools, Geogebra 2 being one of the most widely used ones, rely on a drag-and-drop approach to manipulate geometric objects. Indeed, in order to compose a figure, a student must choose from a graphical panel the object he wants to create then has to place its components in the interface. This tends to limit the creative process of the user. Fiorella and Mayer 12 demonstrate that "generative drawing", i.e. learning by drawing, has a positive impact on students learning abilities in the classroom. Kluger and DeNisi [START_REF] Kluger | The effects of feedback interventions on performance: A historical review, a meta-analysis, and a preliminary feedback intervention theory[END_REF] show the impact of feedback intervention on learning performance. These two points represent the pedagogical foundation of our project. We propose a pen-based system that simulates the traditional pen and paper figure sketching and enriches it by real-time visual, corrective and guidance feedback. This paper presents the first works done in the project, and focuses on the online recognition method of the system. The method is based on modelling the knowledge domain with a bi-dimensional formalism (CD-CMG grammar). Although the formalism is expressive, it could not cope with complexity of the application domain in terms of the handwritten strokes analysis time. We therefore optimized and extended this formalism have an acceptable performance in the context of real-time user interaction. In the literature several works have been done for hand-drawn sketches recognition, the following Sec. 2 presents an overview of existing approaches. Based on this overview and the application domain, we introduce the formalism in Sec. 3. Sec. 4 describes the formalism extension and its impact on the analysis process. Sec. 5 presents our experiments and results while conclusion and perspectives are given in Sec. 6.

Related works

In this work, we are interested in on-line recognition of handwritten structured documents. We distinguish between two types of handwritten documents interpretations methods: lazy 8 and eager 9 (see Fig. 1). Lazy interpretation means that the analysis process begins after completion of the user's production. Eager interpretation means that the handwritten strokes are analyzed on the fly, which is more relevant to our objective of having real-time corrective and guidance feedback to prevent error propagation.

Fig. 1.: Difference between eager and lazy interpretation: at left, the handwritten strokes, at right, analysis result and beautification There are two major approaches for document analysis: statistical and structural. Statistical approaches 3 rely on learning on large labelled databases to discriminate between symbols and are well suited for isolated shapes recognition. However, they do not allow the modelling of the document's structure. Since we are in Geometry context, the system has to recognize not only the geometric shapes, but also the structural relations between the objects. Structural approaches consider a symbol in terms of its constituents, the graphical primitives, and the structural relations between them. For instance, a triangle is considered as three segments related by spacial relations. Structural approaches rely on modelling prior domain knowledge by visual grammars. We distinguish between two classes of structural recognition methods. The former is based on graph grammars. For example, Zannibi et al. [START_REF] Zanibbi | Evaluating structural pattern recognition for handwritten math via primitive label graphs[END_REF] use labelled graphs to recognize handwritten mathematical expressions. One problem with graph-based methods is that they are complex to manipulate for the designer, especially if the production rules number is high. The latter is based on bi-dimensional grammars. For example, in [START_REF] Hammond | LADDER, A Sketching Language for User Interface Developers[END_REF] Hammond and Davis proposed Ladder, a generic description language, and applied it for the interpretation of Truss diagrams in a digital learning context. [START_REF] Atilola | Mechanix : A natural sketch interface tool for teaching truss analysis and free-body diagrams[END_REF] In 7 a bi-dimensional extension to the Stochastic Context Free Grammar is proposed for handwritten mathematical expressions analysis. In this work, to model the geometry domain knowledge, we prefer to use Context Driven Constraints Multi-set Grammar 1 (CD-CMG), a generic formalism for eager interpretation of hand drawn documents. Indeed, in this grammar, the context is explicitly specified in the production rules, which reduces the search space. Moreover, this formalism is the combination between a statistical approach (to locally recognize a shape) and a structural approach (to model the global structure of the document). Finally, CD-CMG has been applied to various types of documents such as architectural plans 10 or electrical sketches. [START_REF] Macé | Eager interpretation of on-line hand-drawn structured documents: The DALI methodology[END_REF] All these features show this formalism is well adapted for our purpose. Thereafter, our contribution lies in twofold: adapting this grammar to the Geometry domain for e-education (see Section 3), and extending this formalism to match the constraint of real-time analysis of geometric productions (see Section 4). Moreover, we have to ensure that our extension of the formalism is coherent with the genericity aspect of CD-CMG, i.e. that our optimization not only improve the system's performance in the geometry sketching domain, but also on other applications. In Section 5, we present the impact of the formalism extension on the analysis complexity in two different but related domains: geometry sketching and architecture plan sketching.

Geometry domain modelling

In this section, we present the formalism, and illustrate it through its adaptation to the Geometry domain.

Context Driven Constraints Multi-Set Grammar

As an extension of the well-known grammar CMG, 11 CD-CMG is formally defined as follows: Definition 1. A CD-CMG is a tuple G=( V N , V T , S, P) with:

• V N : the set of non terminal symbols = symbol classes; • V T : the alphabet, here V T = {stroke}; • S: the first symbol, or axiom; • P: the set of production rules.

And where a production rule p ∈ P is composed of three blocks allowing different levels of vision on the document. The precondition and the postcondition blocks stand for the global vision of the document while the constraint block stands for the local vision of the analyzed strokes. Therefore, a production rule p is denoted as follows:

α → β      Preconditions Constraints Postconditions      | α ∈ V N + , β ∈ (V T ∪ V N ) +
Preconditions and postconditions are based on the concept of Document Structural Context, which models a zone in the document and the awaited elements in it, defined as follows:

Definition 2. A DSC is defined by (λ)[position](γ) [part] where:

• λ is a set of reference elements;

• position is a zone (i.e. a position) related to λ;

• γ is a set of awaited symbols in this zone;

• part is a part of the awaited symbol that has to intersect the zone.

The preconditions are a set of DSC that have to be satisfied and represent the context in which β can be replaced by α. The postconditions are a set of DSC that represent the objects that can be created from the new reduced elements α. This formalization enables to drive the analysis process by the context. Indeed, the preconditions represent the verification step while the postconditions represent the prediction step. The constraints model a local vision on the analyzed elements β. They have two purposes: checking that the shape of β is consistent with the production, and decide if it is pertinent to reduce β into α

Adaptation of CD-CMG to Geometry

We consider the main geometric objects taught in French middle schools: segments, arcs, circles, angles, all the types of triangles and quadrilaterals. We defined around 20 productions rules to model these objects productions as well as the interactions between them (e.g. intersection and orthogonality). Let's illustrate this with two production rules. Fig. 2 presents a part of a segment production rule, while Fig. 3 and Fig. 4 illustrate a segment composition. In this example, the red stroke in Fig. 3 is transformed into a segment if the precondition block and the constraint block are satisfied. The first postcondition DSC in the Post-Conditions block (green rectangle in Fig. 2) models the fact that a bisector production rule will be triggered if a straight d intersects the center zone of the new created segment (res).

Segment: res → stroke: t where:

Preconditions: (Segment:s1) [Zone] (t) [first] & (Segment:s2) [Zone] (t) [last] or (Segment:s1) [Zone] (t) [extremity] or Document[int] (t) [all]
Constraints: Recognizer(t, segment) Online analysis of hand-drawn strokes for Geometry learning 7

Postconditions (res) [center] (Straight: d) [one] =⇒ [Bisector → d] (res) [LengthSegment] (Stroke: t) [one] =⇒ [Angle → t] (res) [InitialExtremity] (Segment: s1) [extremity] =⇒ [Triangle → res, s1, Segment: s] ... -→
Triangle: res → segment: s1, s2, s3 with: we established a hierarchy between production rules, from general to specific, in order to prune the search space and speed up the analysis process. For example, a triangle can be reduced into an isosceles triangle if two of its sides are equal.

Preconditions: (S1) [Zone] (s2) [one] & (S2) [Zone] (s3) [one] & (S3) [Zone] (s1) [one] Constraints: LinkedSegments(s1, s2, s3) Postconditions: (res)[TriangleZone] (Circle: c) [All] =⇒ [Inscribed-Circle → c]

Analysis process associated to CD-CMG

The analysis process, extensively explained in, 1 is a combination of a bottom-up strategy (guided by the reduced elements) and a top-down strategy (guided by the postconditions DSCs). For each new element, the parser searches the DSC it satisfies and vice versa. Consequently, a production is triggered if its β elements contain at least a new element and its precondition block contains at least a new DSC. Let's consider the scene illustrated in Fig. 6 composed of a new stroke t (in red) and three segments (s1, s2, s3).

Fig. 6.: Stroke analysis process

The analysis of t leads to the construction of the analysis (or derivation) tree presented in Fig. 7. The root represents the stroke t. The nodes and the leaves represent the triggered rules, while the blue path is the sequence of reduced production rules, i.e. the analysis result. As shown in Fig. 7, t is first reduced into a segment, denoted thereafter s4. Then, several rules are tested among which the production rules that led to the correct interpretation of the user's drawing. The exploration strategy is explicit for each rule. For basic shape creation, the strategy is breadth-first, i.e. the analyzer checks if the stroke is either an arc, an angle, a segment, a circle, or a point. Each production rule is associated with a score, depending on the adequacy with the preconditions and the constraints. If there are more than one possible interpretation (two applicable productions at the same analysis level for example), the analyzer expands the analysis tree, and chooses the sequence of productions with the highest score. For other productions, such as triangle creation, the exploration strategy is depthfirst, such as the first applicable rule is reduced without considering the other alternatives. This allows to reduce the search space.

Limits of CD-CMG in geometry

As we can see in Fig. 7, the triangle production rule is triggered three times for each possible combination of segments: (s4, s1, s2), (s4, s1, s3) and (s4, s2, s3), even if there is no coherent context for creating a triangle in this scene. This is due to the fact that these productions contain a new element (s4) and one of their preconditions DSC is satisfied (c.f. Fig. 6). Only the precondition block is checked in this case, since not all DSC are satisfied. The impact on the combinatorics is not important here, but when the document is complex, the analysis becomes costly. Even though the formalism is generic and expressive enough to model the prior geometry knowledge, the multiple possible interactions between geometric objects, e.g. creating sub-figures from existing ones (c.f. Fig. 8), also generate combinatorial problems in the analysis process.

Let's consider the triangle production rule (c.f. Fig. 5). A direct conse- quence of adapting CD-GMC to the geometry domain is that the β elements (here the 3 segments) are not really replaced by the α elements (here the triangle). They contribute to create the triangle but they remain considered in the analysis process in order to create other new elements. This has a big impact on the applicable rules search space size. We identify two factors producing the combinatorial explosions: the format of the DSCs, and the computation of equivalent interpretations. We will explicit these factors and our proposed solutions in the next section.

Revision and formalism extension

In this section, we present the problems we faced in terms of analysis process complexity and our proposed solutions.

The DSC problematic

The expressivity of the formalism in terms of describing the document structure with the DSC allows to formalize that all the components of a polygon are linked by their extremities. Unfortunately, as we have seen in Section 3.C, the fact that a production can be triggered even if only one of its preconditions DSC is validated generates a combinatorial problem. Indeed, the more segments a polygon contains, the more DSC there are in the polygon production. Fig. 9 illustrates the composition of a new stroke t in the context of three already interpreted segments. t will be recognized as a new segment called thereafter s2. The fact that s2 is linked to [AB] (blue zone in Fig. 9) will activate the DSC:

[AB] [InitialExtremity] s2 [one] =⇒ triangle → [AB],s2,s3.
The parser will search the third segment (i.e. s3) that completes the triangle rule with [AB] and s2. There is no contextual information in this DSC about the segment [BC] that completes the triangle since it is not concerned by the zone [AB] [InitialExtremity]. In consequence, for this scene composed of 3 segments besides [AB] and s2, the triangle production rule will be tested three times (for s3=[BC], s3=[ED] and s3=[EF]) instead of once. Thus, the analysis time can be very long, especially if the document is complex. In fact, this issue relies on a CD-CMG limitation. The formalism does not allow to have more than one zone in a DSC, which would enable positioning many awaited elements in relation to one reference element.

To resolve this problem, we propose to refine the constraints on the zones such that a zone can cover all the awaited symbols in the same DSC. The DSC related to the triangle production rules will then be:

[AB] [T otalLengthSegment] s2, s3 [one],
where T otalLengthSegment is the zone that covers the length of [AB] (in blue in Fig. 10). This formulation allows to have a contextual information on all the segments composing a triangle. The loss in focus of the zone (from covering an extremity to covering all the segment) is balanced in the Constraint block by verifying that the segments are structurally linked by their extremities. For the scene illustrated in Fig. 10, the triangle production rule is triggered only once, which reduces the analysis complexity. Online analysis of hand-drawn strokes for Geometry learning 11

Problem of equivalent interpretations and formalism extension

Since we are in Geometry learning context, it is important to know the dependency links between the elements, e.g. the connections between several segments. These links are modeled in the preconditions DSCs. Fig. 11 presents a focus on the precondition block of the segment production rule.

It is composed of a disjunction of three preconditions. They model the fact that there are three possible contexts for a segment creation. The stroke can be linked to two existing segments by their extremities, or linked to the extremity of only one segment, or not linked to anything (in the document).

The F irstP recondition operator, introduced in, 10 establishes an order between the preconditions, e.g. from specific to general, and forces the parser to stop the context research at the first valid precondition.

Fig. 12.: FirstPrecondition limits Fig. 12 illustrates a scene in which a stroke t is recognized as a segment. F irstP recondition forces the parser to consider the stroke as linked to two segments, considering only the first precondition. Without this operator, the three preconditions, which are valid in this case, will be tested as hypotheses. The parser will expand the analysis tree in a breadth-first manner then choose the interpretation with the highest score. A limit to this operator is that the verification of the first precondition can also be complex. Indeed, in this example, there are six contextually valid hypotheses: t can be linked to the couples (s1, s5), (s1,s6), (s1, s7), (s4, s5), (s4, s6), (s4, s7). Hence, six equivalent branches will be created in the analysis tree multiplying the analysis complexity by six. The issue is that the existing grammar does not include alternative strategies to deal with these hypotheses. The context search will then be exhaustive, generating in consequence combinatorial problems, where in fact the six hypotheses mentioned above are equivalent. To tackle this problem, we propose to extend the formalism by creating a new operator F irstContext. This operator forces the parser not only to stop the research at the first valid precondition, but also at the first valid context within a precondition. It means that the search is stopped when the first reference elements that are coherent with the precondition are found. In the example (Fig. 12), the parser will choose the first couple of segments that satisfies the DSCs of the preconditions, e.g. it will choose the couple (s1, s7) without considering the other combinations. This means we have an alternative exploration strategy enabling to reduce the search space. This will drastically reduce complexity, without losing information about connections. In use, we have noticed a limit to this new operator, which occurs when the segments are not exactly connected, but have overlapping zones (see the example in Fig. 13). Without the F irstContext operator, the system computes the mem-Fig. 13.: Zone overlap problem bership degree of the stroke's extremity in each zone of the segments to choose the best possible interpretation. With F irstContext operator, it has to choose the first valid interpretation, which is not necessarily the best. However, the robustness of this extension lies in the interaction with the user since he has the possibility to implicitly validate the interpretation by continuing his drawings, or to delete the segment and redraw it more precisely. This is a trade-off between interpretation precision and analysis process. We will detail the impact of our contributions in the next section. Online analysis of hand-drawn strokes for Geometry learning 13

5. Experiments and results

Quantitative study on Geometry domain

To evaluate the impact of our contributions on the system performance, we established several criteria:

• Iterations: number of reduced productions rules • Interpretations: number of branches in the analysis tree • Time: Analysis time

• Triggered: Number of triggered rules
The evaluation is realized on one complex drawing benchmark, illustrated in Fig. 14.

Fig. 14.: Benchmark

We study the impact of our contributions on three critical steps of the drawing scenario of this figure, illustrated in Fig. 15, Fig. 16, and Fig. 17. We compare the performance of our system with the existing CD-CMG grammar and its associated parser. In the following, the term ZoneOpt refers to the constraints refinement on the zones while F irstContext refers to the formalism extension by the addition of the new operator.

First step of the scenario

The scene (Fig. 15) illustrates a drawn stroke that will produce an analysis process. The stroke will be first interpreted as segment [AD]. This segments will trigger the production of a rectangle. to 23. F irstContext operator has no effect since there is no equivalent interpretations to consider.

Second step of the scenario

The scene (Fig. 16) illustrates a more complex production. The drawn stroke will be first interpreted as segment [EB]. This segments will trigger the production of two triangles, one being isosceles and the other rectangle.

Drawn stroke Analysis result Fig. 16.: Second step of the scenario

The impact of our contributions on this step is illustrated in TABLE 2.

With the existing formalism, the performance is not acceptable since analysis time takes 6.4 seconds. This is due to the number of triggered rules (1057) and equivalent interpretations (3). By modifying the format of the 2 and TABLE 3, the more complex the scene gets, the greater the impact of our contributions on the performance gets. Thus, taking into account the desired real-time user interaction, the proposed optimization allow the design of a system with acceptable performance. To prove the genericity of our approach, we adapt our extension of CD-CMG to the Architecture sketching domain. The previous version of the formalism was already applied in this domain as mentioned before in Section 2. The elements are walls, editable doors and windows. We add the possibility to recognize rooms, which are modelled by polygons. This adds another layer of complexity which wasn't incorporated until now. Moreover, the analysis engine is not only capable of detecting newly created rooms, but also to create what we call "implicit rooms" (elements that are not displayed), which are determined by the combinations of all the connected rooms in the scene (c.f. Fig. 18). This is an important func-Fig. 18.: Explicit rooms (piece 2 and piece 3), one implicit room (piece 1) tionality because we want to be able to maintain the notion of a created room, even after deleting a wall connecting two adjacent rooms. As we can see in Fig. 19, after the deletion of "chamber 4", "couloir" (corridor in French), and "salle a manger" (dining room), the implicit room "pièce 14" becomes explicit and is displayed in the scene. We study the impact of our formalism extension (mainly the FirstContext operator) on a complex drawing scenario illustrated in Fig. 20. The red stroke will lead to the creation of segment, which will lead to the creation of 29 "implicit" rooms, and one visible room ("chambre 1"). We study the impact of our optimization using the same criteria as in Geometry sketching domain. We can see 4 that the extension of the formalism with the FirstContext operator, enabling to choose alternative strategies for context search, has the consequence of dividing nearly by 10 the analysis time, from 2.09 to 0.22 seconds. We can then say that our extension is coherent with the generic aspect of the formalism.

Qualitative study

As shown in Fig. 21, we have implemented a pen-based prototype for the composition of geometric sketches. The real-time analysis of the user's composition allows to give visual feedback, which are signs that the system has correctly interpreted the hand-drawn figures (see angle recognition in green in Fig. 21).

To respect to continuum with pen and paper habits, the system has to be flexible enough in order to make the exercise execution as intuitive for the child as possible. For example, the construction of a parallelogram needs a level of precision that can interfere with our free drawing objective. Therefore, we integrated an edition mode to our system to facilitate the drawing process. We work closely with our partners in ergonomics and usages (Loustic, LP3C), in our user-centered design. They conducted the first user experiments on a beta version of the system, with 12 volunteer children from a Brittany region middle-school. The objective was to perform a simple exercise in a short time (5 minutes, after 5 minutes of training). Even if some children encountered difficulties in completing the task, due to some system imperfections and lack of training time, the post-test questionnaire showed a prevailing feeling of satisfaction from the pupils and the teachers towards our application and its potential.

Conclusion and perspectives

In this paper, we propose a pen-based system that interprets in real-time geometric figures, based on the modelling of the prior domain knowledge with a bi-dimensional grammar. We optimize and extend the CD-CMG formalism to adapt it to the geometry domain. Our formalism extension is coherent with the genericity aspect of the grammar, as we has proven when adapting CD-CMG to the architecture domain. Our contributions have a consequent impact on the system performance which is now acceptable for real-time user-interaction. Our future work consist in improving even more the analysis time, one possible solution being the modification of the analysis process in terms of triggering rules. Given that there multiple layers of interpretation (basic shapes, polygons, etc), the idea would be to extend the grammar to include the notion of hierarchy between production rules. We will also work on the semantic interpretation of the child's drawing. The goal is to enable the teacher to create customized exercises. The system will be generate automatically the solver procedure from the teacher's drawings. Given that there are more than one possible solution for solving the exercise, we will have to generate all the alternative solutions as sequence of actions. The goal is for the system to detect in real-time from the child's actions the solution that he intends to realize and guide him accordingly. The successive versions of our prototype will be tested in pilot middle schools to validate our approach, and we will benefit from the studies of LP3C and LOUSTIC laboratories in usage psychology and ergonomics to be aware of the users needs and preferences in terms of visual and corrective feedback, and other features such as virtual manipulable tools.

Fig. 2 .

 2 Fig. 2.: Segment production rule in CD-CMG

Fig. 5 .

 5 Fig. 5.: Triangle production rule

Fig. 7 .

 7 Fig. 7.: Analysis tree

Fig. 9 .

 9 Fig. 9.: Strict DSC Fig. 10.: Refined DSC

Fig. 11 .

 11 Fig. 11.: Precondition block for segment production

5. 1 . 3 .

 13 Fig. 17.: Third step of the scenario

Deleting 4

 4 Fig. 19.: Complexity of architecture domain

Fig. 21 . 4 .

 214 Fig. 21.: Prototype interface

TABLE 1

 1

	presents the analysis results for this step.
	Since the document is still simple, the performance is good (around 0.20
	seconds). However, our contributions have no real impact on the analy-
	sis time. With ZoneOpt, the number of triggered rules decreases from 43

Table 1 .

 1 : First step analysis result

	Approach	Iterations Interpretations Time Triggered
	DALI	4	1	0.23 s	43
	ZoneOpt	4	1	0.20 s	23
	F irstContext	4	1	0.20 s	43
	ZoneOpt+ F irstContext	4	1	0.19 s	23

Table 2

 2 ZoneOpt improves the analysis time (2s) by reducing the number of triggered rules. F irstContext operator forces the parser to consider only one interpretation. In consequence, the number of triggered rules decreases from 1057 to 356, and the analysis time is down to 4.2 seconds, which is still not acceptable in a context of real-time interaction with a user. However, the coupling of Opt1 and Opt2 enables to have an analysis time of 0.62 which is acceptable.

		.: Second step analysis results
	Approach	Iterations Interpretations	Time	Triggered
	CD-CMG	15	3	6.4 s	1057
	ZoneOpt	15	3	2 s	330
	F irstContext	5	1	4.2 s	356
	ZoneOpt + F irstContext	5	1	0.62 s	113
	DSCs,

Table 3

 3

	.: Third step analysis results
	Approach	Interpretations Analysis time Triggered rules
	CD-CMG	6	30 s	2472
	Extended zones	6	7 s	962
	F irstContext	1	5 s	412
	Extended zones + F irstContext	1	1.5 s	167
	5.2. Quantitative study on Architecture domain

Table 4 .

 4 : Third step analysis results

	Approach	Interpretations Analysis time Triggered rules
	CD-CMG	9	2.09 s	760
	Extended formalism	1	0.22 s	92
	from TABLE

Acknowledgment

"ACTIF" is funded by the region of Brittany and the French state call for projects e-FRAN, operated by the "Caisse des Dépôts". The project is supported by the LabCom « ScriptAndLabs » (n°ANR-16-LVC2-0008-01). The authors would like to tank the academic partners, the LP3C and LOUSTIC.

Online analysis of hand-drawn strokes for Geometry learning Online analysis of hand-drawn strokes for Geometry learning


Strong electrical magneto-chiral anisotropy in tellurium G.L.J.A. Rikken Laboratoire National des Champs Magnétiques Intenses UPR3228 CNRS/EMFL/INSA/UGA/UPS, Toulouse & Grenoble, France.

N. Avarvari

MOLTECH-Anjou, UMR 6200, CNRS, UNIV Angers, 2 blvd Lavoisier, 49045 ANGERS Cedex, France (Dated: May 13, 2019)

We report the experimental observation of strong electrical magneto-chiral anistropy (eMChA) in trigonal tellurium (t-Te) crystals. We introduce the tensorial character of the effect and determine several tensor elements and we propose a novel intrinsic bandstructure-based mechanism for eMChA which gives a reasonable description of the principal results.

Chirality is important in many areas of physics, chemistry and biology, where objects or materials can exist in two non-superimposable forms, one being the mirror image of the other (enantiomers). Such a system is not invariant under parity reversal. If in addition it is not invariant under time-reversal because it has a magnetization, an entire class of effects called magnetochiral anisotropy (MChA) becomes allowed. The existence of MChA in the optical properties of chiral systems under magnetic field has been predicted since 1962 [1], [2], [3], [4], [5]. It corresponds to a difference in the absorption and refraction of unpolarized light propagating parallel or anti-parallel to the magnetic field in a chiral medium. After its first experimental observations [6], [7], [8], its existence was confirmed across the entire electromagnetic spectrum, from microwaves [9] to X-rays [10]. The existence of MChA was further generalized to other transport phenomena [11]. It was experimentally observed in the electrical transport in bismuth helices [11], carbon nano tubes [12], [13] and bulk organic conductors [14], as an electrical resistance  that depends on the handedness of the conductor and on the relative orientation of electrical current I and magnetic field B:

  (B I) =  0 (1+ 2  2 +  B • I), with   = - 
referring to the right-and left-handed enantiomer of the conductor. More recently, such electrical MChA was also observed in chiral magnetic systems [15], [16], [17], which was tentatively explained by scattering by chiral spin fluctuations. The spin filter effect [18] can also be regarded as a form of eMChA. As another generalization, MChA was recently observed in the propagation of ultrasound [19]. Although the characteristics of eMChA make it interesting for applications, the small values reported so far daunt their development. Whereas a microscopic theory exists for optical MChA [5], apart from some simplified model calculations [20], no quantitative theory exists for eMChA in bulk materials. Here we report the experimental observation of much larger values in t-Te, and introduce a novel intrinsic mechanism for eMChA that explains this observation and allows to iden- . Its crystal structure consists of parallel stacked helices of 3 Te atom per turn (Fig. 1) and belongs to the crystal class 32. The chirality of t-Te and the absence of time reversal symmetry at the H point allow for the existence of linear k-terms in the bandstructure (k = wavevector) [21]. Using this bandstructure, several chiroptical properties (see [22] and references therein) and magneto-optical properties (see [START_REF]The Physics of Selenium and Tellurium[END_REF] and references therein) of t-Te have been calculated, in good agreement with experiment. The existence of a strong eMChA in t-Te is plausible because of its helical crystal structure, and it is further supported by the recent observation of current-induced shifts in the 125 Te NMR frequency in t-Te [START_REF] Furukawa | [END_REF]. This observation confirms the existence of strong inverse eMChA in in this material. This effect corresponds to a current induced longitudinal magnetization present in all chiral conductors [11] and therefore implies the existence of a strong FIG. 2: Current and magnetic field dependence of the resistance (triangles, defined as  =     ) and eMChA (balls, for definition see text) of a x-oriented left-handed Te crystal at 300 K and with a cross section of 5 10 -7 m 2 . Lines are linear fits.

eMChA in t-Te. Theoretical work has addressed several contributions to the inverse eMChA in t-Te (see [25] and references therein) but cannot be straightforwardly adapted to make quantitative predictions for the direct eMChA effect. Single crystals of zone refined t-Te (purity better than 99,9999%) were commercially obtained [START_REF][END_REF]. They can be easily cleaved along the c-axis, and etching the cleavage surface with hot concentrated sulfuric acid reveals characteristic etch pits from which the crystal axis orientation and the crystal handedness can be straightforwardly deduced [28]. Typical sample sizes are cross-sections of 0,5 x 0,5 mm 2 and lengths of 4 mm. Gold contacts for colinear 4-terminal resistance measurements were deposited by sputtering and a 200 Hz AC current   was injected with a low-distorsion current source. The generated voltages   and its second harmonic  2 were measured by phase-sensitive detection. The above expression for   is a simplification, only strictly valid in cubic crystals or isotropic media. In crystals of lower symmetry, the correct description of eMChA requires a fourth rank tensor γ:

 2  =            ( 1
)
where    = -   and  is the current density. The crystal symmetry imposes further restrictions on the tensor components (see e.g. [START_REF] Birss | Symmetry and magnetism[END_REF]). In the geometry used in our experiments,  =  =  and the cases for  =  and  =  have been addressed by using crystals of different cuts. It can be easily shown that eMChA, defined as (( ) -( -))(( ) + ( -)) ≡ ∆ equals 4 2   (for details see [14]- [17]). By taking the difference between the results for + and -, all nonlinearities that are even in magnetic field are eliminated. The dependence of ∆ on current and magnetic field for an x-oriented left-handed crystal (space group D 6 3 ) is shown in Figure 2, confirming the strictly linear dependence of eMChA on these quantities. By making different crystal cuts and by rotating the crystals, different tensor components can be measured, as illustrated in Fig. 3 and4. The enantioselectivity of FIG. 3: eMChA of a x-oriented left handed crystal at room temperature, as a function of the angle between B and the crystal x-axis. At

 = 0 • , ∆ ∝   , at  = ±90 • , ∆ ∝   .
the eMChA is illustrated in Figure 4, which shows eM-ChA results for a left-handed and a right handed crystal (space group D 4 3 ) in the same orientation, with opposite results. From Figs. 3 and4 12  ≈   and   ¿   . The latter result does not mean that   = 0, as there is no symmetry argument that imposes that. The uncertainty in the exact geometrical shape of the sample, in combination with the small value of   and the much larger values of the other tensor elements, make it difficult to determine a significant value for this quantity. Fig. 5 shows the temperature dependence of eMChA in the intrinsic regime around room temperature. Table 1 gives a summary of the values reported so far for eMChA, illustrating that t-Te shows by far the strongest effect. We propose as explanation for the observed eM-ChA the k-linear terms in the t-Te bandstructure around the H-point. Nakoa et al [29] have shown theoretically and experimentally that these terms lead to the lifting of the energy degeneracy between valence band states with k and -k in the presence of a magnetic field perpendicular to the z-axis, whereas as no degeneracy lifting occurs for a magnetic field parallel to the z-axis. Although these authors did not comment on this aspect, such an energy-splitting has to be enantioselective in order to be symmetry allowed. We can therefore heuristically simplify their findings to the existence of a MChA energy term around the t-Te valence band maximum of the form

Material  [ 2  • ] Ref. Remark t-
∆  =   k • B ⊥ with   = -  and || ≈ 15 • 10 -30  .
A similar behavior was later found for the t-Te conduction band [30]. If we neglect the regular non-parabolicity of the valence band, its energy dispersion relation around the

H-point is (k) = ~2k 2 2 * +   k • B ⊥ .
In the constant relaxation time approximation, the Boltzmann equation gives for the electrical conductivity  [START_REF] Seeger | Semiconductor physics[END_REF]:

  =  2  4 3 ~2 Z µ (k)   ¶ 2    3 k (2)
where  is the distribution function,  the charge,  the scattering time,  * the effective mass and for Maxwell-Boltzmann statistics,  = -   . Applying the magnetic field in the x-direction and neglecting terms in  2 this results in

  =  2   * -  2    4 3  *    Z    3 k (3) =  0 ³ 1 -      ´(4)
where

   =  *    ~   (5)
Note that at room temperature an analogous contribution to eMChA will come from the conduction band which, depending on the relative signs of  for the two bands, may have the same or opposite sign. This electron contribution will disappear at low temperature when t-Te becomes extrinsic p-type. This simple model leads to several predictions: 1) as a general rule, metals, with their much larger carrier density, will show smaller eMChA than semiconductors and semi-metals, in agreement with the table above.

2) for t-Te at 300 K, ∆(BJx) =    with   ≈ 610 -10  2  -1  -1 whereas our experimental result (Fig. 3) gives   ≈ 210 -9  2  -1  -1 , a reasonable agreement in view of the simple model.

3)   = 0 in t-Te because of the absence of the degeneracy lifting for B k z, in agreement with our observations. Other mechanisms for eMChA [11], not included in our model, may still lead to a small non-zero value. One may obtain an estimate for   from the free-electron-on-ahelix model [20]. This can only give an upper limit, as there is significant coupling between adjacent Te helices and charge carriers are therefore not confined to one helix. For the same parameters as in Fig. 4, this model predicts ∆ ≈ 10 -9 , consistent with the experimental result. 4) Taking into account the temperature dependence of the carrier concentration [START_REF] Seeger | Semiconductor physics[END_REF], Eq. 5 implies the temperature dependence of   to be  -52 exp(  2   ) Fig. 5 shows that this is a reasonably good description. Although t-Te is topologically trivial, the existence of k-linear terms in its bandstructure and its strong spinorbit interaction suggest a link to topological insulators and Weyl semi-metals. Indeed, strong eMChA was also claimed for topologically non-trivial systems like Weyl semi-metals [START_REF] Morimoto | [END_REF] and non-centrosymmetric Rashba superconductors [33], although these systems are not chiral in the strict sense of the term. In line with this suggestion, t-Te is predicted to become a strong topological insulator under pressure [34] and ARPES measurements have revealed Weyl nodes at ambient pressure [35].

It will be clear that a more sophisticated theoretical approach, including the effect of the Lorentz force, plus the full details of the band structure are necessary to obtain full understanding of eMChA in t-Te and to arrive at an accurate description of all its tensor elements.

Our model allows to identify the major contributing factors and allows to identify other materials showing strong eMChA through straightforward band structure calculations, thereby opening a venue for realistic applications of this effect. Obvious candidates are trigonal selenium and its binary alloys with tellurium, and cinnabar (-HgS) that have the same crystal structure, albeit slightly different band structures. At different band structure extrema, the MChA energy term, present around the H point in t-Te, may be zero, which could lead to a much lower eMChA.

In summary, we have experimentally observed strong eM-ChA in t-Te, we have demonstrated the tensorial character of this effect and we have identified a novel intrinsic bandstructure mechanism that agrees with these results. This work was supported by the French National Agency for Research (ChiraMolCo, ANR 15-CE29-0006-02).

FIG. 1 :

 1 FIG. 1: Trigonal tellurium crystal structure. Left: view on the x-z plane of a single helix. Right: view on the x-y plane. a = 445 pm, c = 593 pm, d = 238 pm

  FIG. 4: eMChA of a left-handed (N) and right-handed (H ) zoriented Te crystal at room temperature, as a function of the angle between B and the crystal z-axis. At  = 0 • , ∆ ∝   , at  = ±90 • ,∆ ∝   

FIG. 5 :

 5 FIG. 5: Temperature dependence of eMChA of an x-oriented left handed crystal. For dotted line, see text.