Pascale Minet

Paul Muhlethaler

Ines Khoufi

Collision Avoidance in Shared Slots in Wireless Devices of the Internet of Things: Models and Simulations

Keywords: Wireless networks, Model, Collision Avoidance, Shared slots, Medium Access, Markov Model, Slotted Aloha

In this paper we propose an analysis of a slot-based protocol designed for devices of the Internet of Things (IoT). In contrast to other TDMA-based protocols, this scheme uses a random technique to access shared slots, similarly to CSMA protocols. In practice, the transmissions are scheduled in a given back-off window of slots whose duration allows the transmission of a packet and its acknowledgment. Therefore this protocol can be analyzed according to the methodology introduced by Bianchi for the IEEE 802.11 protocol even if the protocol studied differs in many aspects. The model we use is also particular because we succeed in obtaining a Markov model even though the scheme used to send a packet (in a node) may depend on the transmission of the previous packet.

We distinguish two protocols; in the first one, at the initial stage or after a successful transmission, the packets are transmitted without any back-off, whereas in the second protocol each transmission is always preceded by the count down of a random back-off. Extensive simulations validate the both protocols models. In addition, the performances of these protocols are compared with those of slotted Aloha and a protocol using a constant backoff window.

I. CONTEXT AND MOTIVATION

The Internet of Things (IoT) refers to billions of connected devices able to sense their environment and exchange data. These devices are smart items (e.g. a connected watch), autonomous vehicles, smart buildings, etc. The goal of these devices is to improve our daily life. For instance, they help to monitor our health and assist elderly people [START_REF] Sebbak | Majority-consensus fusion approach for elderly iot-based healthcare applications[END_REF], increase road safety by assisting maneuvers for lane changing [START_REF] Hadded | An adaptive TDMA slot assignment strategy in vehicular ad hoc network[END_REF], [START_REF] Doukha | Load balancing aware sdma-based beaconing approach in vehicular ad hoc networks[END_REF], decrease the energy consumed by homes, and detect air pollution [START_REF] Derhab | Wireless and mobile sensing technologies for the future internet[END_REF].

In addition, we are currently entering the fourth industrial revolution with Industrie 4.0 [START_REF] Hermann | Design Principles for Industrie 4.0 Scenarios[END_REF], [START_REF]Recommendations for implementing the strategic initiative Industrie 4.0: Final report of the Industrie 4.0 working group[END_REF]. The first one came about through the introduction of mechanical production facilities using water and steam power. The second revolution was made thanks to the introduction of labor division and mass production with the help of electrical energy. In the third one, electronic and IT (Information Technologies) systems have been massively used to further automate production. Currently, the real transformation is going to be through the use of cyber-physical systems. The complexity degree constantly increases with each new revolution. With the fourth revolution [START_REF] Hermann | Design Principles for Industrie 4.0 Scenarios[END_REF], we are witnessing a greater convergence between operational technology and information technology, through the use of the Industrial Internet of Things (IoT).

IoT relies on wireless networks supporting data gathering applications. Data gathering applications have strong requirements in terms of latency, throughput, robustness and power autonomy. The question is: which wireless sensor network technology is able to support such requirements. Most wireless sensor networks deployed up to now have used a technology based on the IEEE 802.15.4 standard [START_REF] Ieee Sa | IEEE Standard for Local and metropolitan area networks-Part 15.4: Low-Rate Wireless Personal Area Networks (LR-WPANs)[END_REF]. Time Slotted Channel Hopping (TSCH) is specified in amendment e of the IEEE 802.15.4 standard [START_REF]IEEE Standard for Local and metropolitan area networks-Part 15.4: Low-Rate Wireless Personal Area Networks (LR-WPANs) -Amendment 1: MAC sublayer[END_REF]. It is based on a time slotted medium access operating on several channels in parallel. Frequency hopping is used to protect against perturbations. TSCH has been designed for process automation, process control, equipment monitoring and more generally the Internet of Things. In TSCH, all transmissions are scheduled in time and space: they take place in a pair (time slot, channel offset). Each channel offset is mapped on a physical channel. This mapping changes at each time slot. Frequency hopping contributes to reducing the effects of multipath and interferences. Two types of slots are distinguished: dedicated and shared. In a dedicated slot, only the transmitter is allowed to transmit, whereas the receiver(s) is awake to receive the transmission and the other nodes are sleeping in order to save energy. The absence of collisions in the dedicated slots leads to a higher throughput and a higher power autonomy of nodes. Dedicated slots are used to collect application data. In shared slots, all nodes are awake and all nodes that have a message to transmit are allowed to transmit. As a consequence, a collision occurs each time there is more than one transmitter in the same time slot and on the same channel. For unicast messages, the transmitter is aware of a possible collision, because it has not received an acknowledgment. In such a condition, the message is retransmitted, unless the maximum number of transmissions has already been reached. Notice that for broadcast and multicast messages, the transmitter does not know the existence of the collision.

Shared slots are generally used for network control and network adaptivity to topology or application changes. It would be too expensive in terms of bandwidth and latency to reserve dedicated slots for such messages that are not frequent. That is why shared slots that multiplex the transmitters are favored.

In this paper, we propose to model various methods of collision avoidance on shared slots in a wireless slotted network. All the methods studied in this paper are fully distributed and based on a probabilistic transmission by each network node. Two methods will be studied and modeled, including the method used by TSCH. These models will be validated through simulations on the NS3 simulation tool [START_REF]NS3 a discrete network event simulator for internet systems[END_REF]. Performance of these methods are compared with the well-known slotted Aloha method [START_REF] Roberts | Aloha packet system with and without slots and capture[END_REF].

II. RELATED WORK AND OUR CONTRIBUTION

This section is organized in three parts. The first part deals with various collision avoidance methods used in wireless networks. In the second part, we focus on how these methods have been modeled to derive the normalized throughput of the network. In both parts, we position our contributions with regard to this related work. The third part presents the organization of this paper.

A. Probabilistic methods for collision avoidance in wireless networks

All the methods studied in this paper are fully distributed and based on a probabilistic transmission by each network node. Probabilistic collision avoidance methods can be classified into three categories, according to their assumptions:

• The number of competing nodes is known. It has been proven that the normalized throughput is maximized when the transmission probability of each node is equal to 1/N , where N is the number of competitors. This is the method used in slotted Aloha [START_REF] Roberts | Aloha packet system with and without slots and capture[END_REF]. When N becomes large, the normalized throughput tends to 1/e, which can be approximated by 0.3679. This is illustrated in Figure 1, where P trans denotes the node transmission probability. • Each node continuously follows the channel state. Such methods require each node to permanently listen to the channel, which is energy consuming. • Each node uses backoffs only. A backoff is a random value drawn in a backoff window defined by its low value and its high value. Such methods are easy to implement and do not require additional synchronization among nodes. Consequently, the only probabilistic collision avoidance methods that do not consume much energy and do not rely on additional assumptions are those based on backoffs. These are the methods studied in this paper. More precisely, each node draws a random backoff in a backoff window. This backoff is decremented at each slot. The node waits until the backoff is zero to be allowed to transmit.

The methods vary in the backoff window parameters:

• the size: it may be constant or increased with the number of successive collisions.

• the reset: after each transmission, or only after each successful transmission, or at each first transmission of a message, etc. • the increment: for instance, after each unsuccessful transmission of a message, until a maximum value is reached.

B. Models for collision avoidance methods in wireless networks

The first studies dealing with collision avoidance in wireless slotted networks were done for the IEEE 802.11 wireless network. The seminal paper is Bianchi's paper [START_REF] Bianchi | Performance analysis of the IEEE 802.11 distributed coordination function[END_REF]. The analytical model based on a Markov chain designed in this paper is still in use, even if many extensions have been brought, as in, for instance, [START_REF] Korbi | Analytical model of the earliest deadline first policy over 802.11[END_REF]. The first computation of the normalized throughput is given, assuming a finite number of wireless nodes and ideal channel conditions.

More recently, the authors of [START_REF] Bhattacharya | Analytical modeling of IEEE 802.11-Type CSMA/CA networks with short term unfairness[END_REF] show that when some CSMA/CA backoff parameters (e.g. the initial backoff, the backoff multiplier and the number of retries) are different from the standard, some unfairness may occur in single-hop 802.11 networks with saturated transmitters.

Focusing on the slotted access of the IEEE 802.15.4 protocol, we can cite the studies [START_REF] Park | Throughput and energy consumption analysis of IEEE 802.15. 4 slotted CSMA/CA[END_REF], [START_REF] Pollin | Performance analysis of slotted carrier sense IEEE 802.15.4 medium access layer[END_REF], [START_REF] Park | A Generalized Markov Chain Model For Effective Analysis of Slotted IEEE 802.15.4[END_REF], [START_REF] Wen | An Improved Markov Model for IEEE 802.15.4 Slotted CSMA/CA Mechanism[END_REF] that provide an evaluation of the throughput, average delay, energy consumption and reliability. All these papers propose nearly the same Markov chain model. In contrast to the present paper, the back-off evolves during the lifetime of the packet when it encounters collisions. However, when the packet is rejected (i.e. the maximum number of transmissions of this message has been reached and the last transmission collides) the protocol does not remember the actual value of the collision window for the next transmission as our model does. Moreover the models in [START_REF] Park | Throughput and energy consumption analysis of IEEE 802.15. 4 slotted CSMA/CA[END_REF], [START_REF] Pollin | Performance analysis of slotted carrier sense IEEE 802.15.4 medium access layer[END_REF], [START_REF] Park | A Generalized Markov Chain Model For Effective Analysis of Slotted IEEE 802.15.4[END_REF], [START_REF] Wen | An Improved Markov Model for IEEE 802.15.4 Slotted CSMA/CA Mechanism[END_REF] handle the case where the node buffers always have pending packets. Our model handles the more realistic situation where we have a given packet generation rate in a single buffer with loss and provides a much simpler normalization equation than [START_REF] Park | Throughput and energy consumption analysis of IEEE 802.15. 4 slotted CSMA/CA[END_REF], [START_REF] Pollin | Performance analysis of slotted carrier sense IEEE 802.15.4 medium access layer[END_REF], [START_REF] Park | A Generalized Markov Chain Model For Effective Analysis of Slotted IEEE 802.15.4[END_REF], [START_REF] Wen | An Improved Markov Model for IEEE 802.15.4 Slotted CSMA/CA Mechanism[END_REF].

C. Paper organization

This paper is organized as follows. In Section III, we define the problem of shared slots access; the notation used throughout the paper is given. In Section IV, we analyze the medium access protocol that always performs a backoff before each transmission. We propose a node Markov model taking into account the backoff stage and the maximum number of message transmissions. We evaluate the probabilities of success, collision and empty slots. This model is validated through simulations done with NS3. We then model the protocol that does not perform a backoff before the first transmission of each message and design its Markov model in Section V, which is also validated by means of NS3 simulations. We evaluate the performance of each protocol in terms of successful message transmissions, rejected messages and node fairness in Section VI. We also compare these proocols with slotted Aloha and a protocol using a constant backoff window. Finally, we conclude in Section VII.

III. PROBLEM STATEMENT A. Assumptions

In this paper, we adopt the following assumptions:

• A 1 ) We consider a wireless slotted network: each transmission starts at the beginning of a slot. The slot size allows the transmission of one packet and its immediate acknowledgment when this packet is sent point-to-point. • A 2 ) All the slots are shared.

• A 3 ) Access to the shared slots is ruled by a backoff expressed in terms of the number of shared slots that the competing node must wait for before being allowed to transmit. • A 4 ) There is no channel sensing before transmitting. In a wireless slotted network where all nodes are synchronized to start their transmission at the beginning of a slot like in TSCH, it would be useless to assess a clear channel state before transmitting, because all nodes would perform it simultaneously. Finding the channel clear, they would all transmit simultaneously leading to a collision. In addition, channel clear assessment consumes energy. As a consequence, it is not performed in the wireless slotted network considered. • A 5 ) There are N nodes in the network and all these nodes are assumed to be 1-hop neighbors.

• A 6 ) Each node generates a message with a probability 1 -r. • A 7 ) Each node has a buffer which can contain at most one message: if a message is generated, when the node's buffer is not empty, it is lost.

B. Evaluation criteria and Notation

We want to select the collision avoidance method that:

• Maximizes the normalized throughput that is measured as the probability of successful transmission • Minimizes the probability of message rejection. A message that has not been acknowledged after the maximum number of transmissions is rejected. • Ensures node fairness. For this purpose, we use the Jain fairness index [START_REF] Jain | A quantitative measure of fairness and discrimination for resource allocation in shared computer systems[END_REF] on the node opportunity to transmit. We have

J(T x 1 , ..., T x n ) = ( n i=1 T x i ) 2 n n i=1 T x 2 i (1)
where T x i denotes the number of transmission attempts of node i. The Jain fairness index belongs to the interval [0, 1]. The closer the Jain fairness index is to 1, the better the node fairness is.

• Is the least energy-consuming. Since the sensor nodes have a limited amount of energy, this energy should be reserved for useful transmissions. We now introduce some notations that will be used in this paper that are summarized in Table I. Upper bound of backoff window

W j = 2 j at stage j M inB ≤ j ≤ M axB States Name Meaning Default value (i, j, k)
State of the wireless node considered i is the number of transmissions

1 ≤ i ≤ R j is the backoff stage M inB ≤ j ≤ M axB k is the number of slots to wait for 0 ≤ k ≤ W j -

C. Simulation

The NS3 simulation tool is used to evaluate the performance of different collision avoidance methods (in shared slots). It also validates the models proposed.

Let S denote the total number of slots and E be the number of empty slots. Simulation results allow us to compute the values of S and E and more generally, the values of the different probabilities given in Table II. Psuccess Probability for a random slot to correspond to a successful transmission N umber of slots with successf ul transmission S

Pempty

Probability for a random slot to be empty N umber of empty slots S

P collide

Probability for a random slot to correspond to a collision N umber of slots with 2 or more transmitters S

Each result is the average of 30 simulation runs. In each simulation run, 10000 slots are simulated. The parameters given in Table I are used: the maximum number of transmissions of a message is 4 and the backoff stage belongs to the interval [START_REF] Sebbak | Majority-consensus fusion approach for elderly iot-based healthcare applications[END_REF][START_REF] Ieee Sa | IEEE Standard for Local and metropolitan area networks-Part 15.4: Low-Rate Wireless Personal Area Networks (LR-WPANs)[END_REF] and W j = 2 j .

IV. BACKOFF BEFORE EACH TRANSMISSION

We first describe the collision avoidance method performing a backoff systematically before each transmission.

A. Principle of the method

Each node in the slotted wireless network behaves as follows.

• Before transmitting a message, a backoff is drawn in the backoff window. The backoff window increases with the backoff stage. The backoff stage j starts with 1 and is incremented after each unsuccessful transmission (see the definition below) up to a maximum value M axB. The backoff window at stage j is equal to [0, W j -1]. The backoff drawn in this window represents the number of shared slots the node must wait for before being allowed to transmit its message. • When a message is sent, two cases are possible:

either an acknowledgment is received and the transmission is considered successful. The backoff stage is reset to the initial value M inB. The node serves the next message in its Transmit queue. no acknowledgment is received after a time-out and the transmission is considered unsuccessful. There are two possible cases: * the node has already transmitted this message R times, this message is rejected, a failure notification is reported to the upper layer. Notice that the backoff stage is incremented by one (up to the maximum value M axB). * otherwise, the node increments its backoff stage j by one (up to the maximum value M axB) and its number of transmissions for this message. It then draws a random backoff in [0, W j -1]. When the backoff has elapsed, it transmits its message.

• The message is removed from the buffer only after its acknowledgment has been received or the maximum number of retries has been reached.

B. Model based on a Markov chain

Idle denotes the node state with an empty buffer. Any message generated while the node is not in the Idle state is lost. Except in the Idle state where the buffer of the node is empty, the state of the node considered is represented by a triplet (i, j, k) where i denotes the number of transmissions of the current message considered, j denotes the backoff stage and k is the backoff drawn in the backoff window [0, W j -1]. We have the following inequalities:

• 1 ≤ i ≤ R, where R denotes the maximum number of transmissions of a message.

• M inB ≤ j ≤ M axB, where M inB and M axB are constant parameters fixed by the MAC protocol considered.

• i ≤ j • 0 ≤ k ≤ W j -1.
Such a node behavior can be modeled by a Markov chain. This model, following in the footsteps of Bianchi [START_REF] Bianchi | Performance analysis of the IEEE 802.11 distributed coordination function[END_REF]

has many differences:

• There is no Clear Channel Assess (CCA) before transmitting a message.

• The backoff is decremented at each shared slot even if this slot is not empty.

• The backoff stage after R unsuccessful transmissions of a message is not reset to the initial value for the next message.

As a consequence, the first transmission of a new message may correspond to three different states, which we explain for the case R = 4 and M axB = 7:

-(1, 1, 0), when the previous message transmission was successful. The backoff stage is equal to 1.

-(1, 5, 0), when the previous message was rejected. The backoff stage is equal to R + 1 = 5.

-(1, 7, 0), when the two previous messages were rejected. The backoff stage is equal to its maximum value i.e. 7.

• Medium saturation is not assumed. We suppose that the probability of packet generation is 1 -r at each slot. Let us focus on the Idle state, state of a node when it has no message to transmit. We distinguish three Idle states according to the result of the previous transmission. These states are denoted:

• Idle 1 , when the previous message transmission was successful. The backoff stage will be reset to 1 for the next transmission. • Idle 2 , when the previous message was rejected. The backoff stage will be incremented for the next transmission, it will be R + 1 = 5. • Idle 3 , when the two previous messages were rejected. The backoff stage keeps its current maximum value of 7. The introduction of these states allows us to model the node behavior by a Markov chain, where the next node state depends only on the current state and the event occurring. The Markov chain of this contention avoidance method is depicted in Figure 2, where the three Idle states are depicted by a red rectangle, whereas the three states corresponding to the first message transmission are depicted by a blue double-lined rectangle.

When a node transmits, its transmission collides with a probability p.

To improve the readability of the notation we denote by:

• a i the probability of being in state (i, i, 0)

for i = 1, 2, 3 or 4 = R, • b i the probability of being in state (i, min(4 + i, 7), 0) for i = 1, 2, 3 or 4 = R, • c i the probability of being in state (i, 7, 0) for i = 1, 2, 3 or 4 = R, with M axB = 7 < 2 * R, • I 1 the probability of being in state Idle 1 ,
• I 2 the probability of being in state Idle 2 , • I 3 the probability of being in state Idle 3 ,

• τ the probability that a node transmits in a random slot. We obtain the following system of equations:

               I 1 = (1 -p) * τ + r * I 1 a 1 = (1 -r) * I 1 = (1 -p) * τ a 2 = p * a 1 = p * (1 -r) * I 1 a 3 = p * a 2 = p 2 * a 1 = p 2 * (1 -r) * I 1 a 4 = p * a 3 = p 3 * a 1 = p 3 * (1 -r) * I 1                I 2 = p * a 4 + r * I 2 b 1 = (1 -r) * I 2 = p * a 4 = p 4 * a 1 b 2 = p * b 1 = p 5 * a 1 b 3 = p * b 2 = p 6 * a 1 b 4 = p * b 3 = p 7 * a 1                    I 3 = p * (b 4 + c4) + r * I 3 c 1 = (1 -r) * I 3 = p * (b 4 + c 4 ) c 2 = p * c 1 c 3 = p * c 2 = p 2 * c 1 c 4 = p * c 3 = p 3 * c 1 c 1 = p * b 4 + p * c 4
Fig. 2. The Markov chain of the collision avoidance method on shared slots with a backoff before each transmission.

We get:

c 1 = p * b 4 + p 4 * c 1 c 1 * (1 -p 4 ) = p * b 4 = p 8 * a 1 c 1 = p 8 * a1 1-p 4
If we now focus on the different backoff states before the first transmission of a message generated while in state Idle 1 , we have:

     a 1,W1-1 = a 1 /W 1 a 1,W1-2 = 2 * a 1 /W 1 a 1,0 = W 1 * a 1 /W 1
Summing member to member, we get:

             W1-1 k=0 a 1,k = a 1 * (W 1 + 1)/2 W2-1 k=0 a 2,k = a 2 * (W 2 + 1)/2 = p * a 1 * (W 2 + 1)/2 W3-1 k=0 a 3,k = a 3 * (W 3 + 1)/2 = p 2 * a 1 * (W 3 + 1)/2 W4-1 k=0 a 4,k = a 4 * (W 4 + 1)/2 = p 3 * a 1 * (W 4 + 1)/2 Similarly, we obtain:              W5-1 k=0 b 1,k = b 1 * (W 5 + 1)/2 = p 4 * a 1 * (W 5 + 1)/2 W6-1 k=0 b 2,k = b 2 * (W 6 + 1)/2 = p 5 * a 1 * (W 6 + 1)/2 W7-1 k=0 b 3,k = b 3 * (W 7 + 1)/2 = p 6 * a 1 * (W 7 + 1)/2 W7-1 k=0 b 4,k = b 4 * (W 7 + 1)/2 = p 7 * a 1 * (W 7 + 1)/2 and              W7-1 k=0 c 1,k = c 1 * (W 7 + 1)/2 = p 8 1-p 4 * a 1 * (W 7 + 1)/2 W7-1 k=0 c 2,k = c 2 * (W 7 + 1)/2 = p 9 1-p 4 * a 1 * (W 7 + 1)/2 W7-1 k=0 c 3,k = c 3 * (W 7 + 1)/2 = p 10 1-p 4 * a 1 * (W 7 + 1)/2 W7-1 k=0 c 4,k = c 4 * (W 7 + 1)/2 = p 11 1-p 4 * a 1 * (W 7 + 1)/2
For simplicity reasons, we set A =

4 i=1 Wi-1 k=0 a i,k , B = 4 i=1 W min(i+4,7) -1 k=0 b i,k and C = 4 i=1 W7-1 k=0 c i,k . We have:                  A = a 1 * W1+1 2 + p * a 1 * W2+1 2 + p 2 * a 1 * W3+1 2 +p 3 * a 1 * W4+1 2 B = p 4 * a 1 * W5+1 2 + p 5 * a 1 * W6+1 2 + p 6 * a 1 * W7+1 2 +p 7 * a 1 * W7+1 2 C = (1 + p + p 2 + p 3 ) * ( p 8 * a1 1-p 4 ) * W7+1 2 = a 1 * p 8 1-p * W7+1 2        A = a 1 * ( W1+1 2
+ p * W2+1 2 + p 2 * W3+1 2 + p 3 * W4+1 2 ) B = a 1 * (p 4 * W5+1 2 + p 5 * W6+1 2 + p 6 * W7+1 2 + p 7 * W7+1 2 ) C = p 8 * a1 1-p * W7+1 2
From the model depicted in Figure 2 and normalizing the sum of the probabilities, we get:

                 τ = a 1 + a 2 + a 3 + a 4 + b 1 + b 2 + b 3 + b 4 + c 1 + c 2 + c 3 + c 4 1 = A + B + C + I 1 + I 2 + I 3 I 1 = a1 1-r I 2 = p 4 * a1 1-r I 3 = p 8 * a1 (1-r) * (1-p 4 )
By replacing the a i , b i and c i and I i by their value function of a 1 and replacing A+B +C by its value computed previously, we have:

             τ = a 1 * (1 + p + p 2 + p 3 + p 4 + p 5 + p 6 + p 7 1-p ) 1 = a 1 * ( W1+1 2 + p * W2+1 2 + p 2 * W3+1 2 + p 3 * W4+1 2 +p 4 * W5+1 2 + p 5 * W6+1 2 + p 6 * W7+1 2 + p 7 1-p * W7+1 2 + 1 1-r + p 4 1-r + p 8 (1-r) * (1-p 4 ) )            τ = a1 1-p a 1 = ( W1+1 2 + p * W2+1 2 + p 2 * W3+1 2 + p 3 * W4+1 2 +p 4 * W5+1 2 + p 5 * W6+1 2 + p 6 * W7+1 2 + p 7 1-p * W7+1 2 + 1 1-r + p 4 1-r + p 8 (1-r) * (1-p 4 ) ) -1
By replacing a 1 by its value as a function of p, we have:

τ = 1 1-p * ( W1+1 2 + p * W2+1 2 + p 2 * W3+1 2 + p 3 * W4+1 2 + p 4 * W5+1 2 +p 5 * W6+1 2 + p 6 * W7+1 2 + p 7 1-p * W7+1 2 + 1 1-r + p 4 1-r + p 8 (1-r) * (1-p 4 ) ) -1 (2)
We can compute p the probability of a collision knowing that one node already transmits. It is equal to 1 minus the probability that none of the N -1 other nodes transmits. Hence, we obtain:

p = 1 -(1 -τ ) N -1 (3)
Replacing p by its value as a function of τ in Equation 2 leads to f (τ ) = τ where the function f (.) is defined as follows:

f (τ ) = 1 (1-τ ) N -1 + 1 1-r + (1-(1-τ ) N -1 ) 4 1-r + (1-(1-τ ) N -1 ) 8 (1-r) * (1-(1-(1-τ ) N -1 ) 4 ) ) -1 (4)
In the interval [0, 1], the function f (τ ) -τ is monotonic. Hence, there exists a unique solution τ ∈ [0, 1) giving f (τ ) = τ .

As an example, we compute the solution of f (τ ) = τ for the case N = 8, assuming r = 1 -1/N and taking the default values adopted by TSCH and given in Table I. The value of τ solution of f (τ ) = τ is depicted in Figure 3, where τ ≈ 0.1053. After having computed the value of τ , the unique solution of Equation 4, we can compute the probabilities of success, collision and empty slots as follows.

                           a 1 = (1 -p) * τ I 1 = a 1 /(1 -r) = (1-p) * τ 1-r I 2 = p 4 * a1 1-r I 3 = p 8 * a1 1-r P success = N * τ * (1 -τ ) N -1 P empty = (1 -τ ) N P collide = 1 -P success -P empty

C. Model validation by simulation

Assuming a backoff before each transmission, Figure 4 compares the results of simulations and the model for 4, 8, 16 or 32 nodes, when r = 1 -1/N . The values of P success, also called normalized throughput, and P empty are depicted. Since the value of P collide is deduced from the two previous, it is not depicted. Our Markov model is validated by the very close results obtained by simulation.

V. NO BACKOFF FOR THE FIRST TRANSMISSION

We now focus on the collision avoidance method used by TSCH on the shared slots. It differs from the method explained in Section IV by the fact that no backoff is drawn before the first transmission of the message sent after the successful transmission of the previous message. It is also the case for the first transmission of the first message sent by the wireless node.

A. Model based on a Markov chain

The node behavior can be modeled by a Markov chain. As previously stated, the node state with an empty buffer is denoted Idle. Any message generated while the node is not in the Idle state is lost. Except in the Idle state where the buffer of the node is empty, the node state is represented by a triplet (i, j, k) where i denotes the number of transmissions of the current message, j denotes the backoff stage and k is the backoff drawn by the node in the backoff window [0, W j -1]. We have the following inequalities:

• 1 ≤ i ≤ R, where R denotes the maximum number of transmissions of a message.

• M inB ≤ j ≤ M axB, where M inB and M axB are constant parameters fixed by the MAC protocol considered.

• 0 ≤ k ≤ W j -1.
As a consequence, the first transmission of a new message may correspond to three different states, which we explain for the case R = 4 and M axB = 7:

• (1, 0, 0), when the previous message transmission was successful. By convention, the backoff stage is set to 0.

• (1, 4, 0), when the previous message was rejected. The backoff stage is equal to R = 4.

• (1, 7, 0), when the two previous messages were rejected. The backoff stage is equal to its maximum value, i.e. M axB = 7. Notice that unlike the Markov model presented in Section IV-B, the message transmission number is no longer less than or equal to the backoff stage, because in this collision avoidance method, the success or failure of the two previous messages determines the backoff stage of the current message. This explains the three different states corresponding to the first transmission of a message in the Markov model. These states are depicted by a blue double-lined rectangle in Figure 5, whereas the three Idle states are depicted by a red rectangle. We get the same system of equations for I 1 , I 2 and I 3 as in Section IV-B. By similarity with the analysis given in Section IV-B, we finally get:

f (τ ) = 1 (1-τ ) N -1 * (1 + (1 -(1 -τ ) N -1 ) * W1+1 2 + (1 -(1 -τ ) N -1 ) 2 * W2+1 2 +(1 -(1 -τ ) N -1 ) 3 * W3+1 2 + (1 -(1 -τ ) N -1 ) 4 * W4+1 2 +(1 -(1 -τ ) N -1 ) 5 * W5+1 2 + (1 -(1 -τ ) N -1 ) 6 * W6+1 2 + (1-(1-τ ) N -1 ) 7 (1-τ ) N -1 * W7+1 2 + 1 1-r + (1-(1-τ ) N -1 ) 4 1-r + (1-(1-τ ) N -1 ) 8 (1-r) * (1-(1-(1-τ ) N -1 ) 4 ) ) -1 (5)
In the interval [0, 1], the function f (τ ) -τ is monotonic. Hence, there exists a unique solution τ ∈ [0, 1) giving f (τ ) = τ .

To compare with the collision avoidance method presented in Section IV, we compute the solution of f (τ ) = τ for the case N = 8, assuming r = 1 -1/N and taking the default values adopted by TSCH and given in Table I. The value of τ solution of f (τ ) = τ is depicted in Figure 6, where τ ≈ 0.1200. This is a higher value than this found by the method performing always a backoff before each transmission which was τ ≈ 0.1053. After having computed the value of τ , the unique solution of f (τ ) = τ , we can compute the probabilities of success, collision and empty slots as in Section IV.

B. Model validation by simulation

Assuming no backoff before the first transmission, Figure 7 compares the results obtained by simulations and the model for 4, 8, 16 or 32 nodes, when r = 1 -1/N . The values of P success, also called normalized throughput, and P empty are depicted. Since the value of P collide is deduced from the two previous, it is not depicted. Our Markov model is validated by the very close results obtained by simulation.

VI. COMPARATIVE PERFORMANCE EVALUATION

We now compare the two protocols, for a number of neighboring nodes N belonging to [START_REF] Derhab | Wireless and mobile sensing technologies for the future internet[END_REF]32]. We distinguish two cases of channel load: moderate and heavy.

A. Moderately loaded medium

When the medium is moderately loaded, simulation results concerning the probability of success, collision and empty slots are very stable, the error bars of the simulation for a confidence interval of 95% are very small and not visible in the figures. Figure 8 shows that for a number of neighboring nodes in [START_REF] Sebbak | Majority-consensus fusion approach for elderly iot-based healthcare applications[END_REF][START_REF] Ieee Sa | IEEE Standard for Local and metropolitan area networks-Part 15.4: Low-Rate Wireless Personal Area Networks (LR-WPANs)[END_REF] the protocol used by TSCH provides a higher probability of success leading to a higher normalized throughput. This is no longer the case as soon as N ≥ 8. Similarly, simulation results show a higher collision number, whatever the number of nodes. This is due to the fact that the first transmission of any message very often leads to a collision. The probability of empty slots that measures the channel under-utilization is minimized by TSCH.

In this comparison, we have adopted r = 1 -1/N or in other words the packet generation rate is 1/N for each node and in each slot. Other values for this generation rate are acceptable and lead to a model well in accordance with simulation results. However, if the total load becomes too high, significant unfairness appears in the throughput for the TSCH protocol, as we will see in the next subsection. When the unfairness becomes high, the model is no longer able to predict the simulation results accurately.

B. Highly loaded medium

We now assume that each network node always has at least one message to transmit. This leads to a highly loaded medium and even to medium saturation. At medium saturation, we are interested in the normalized throughput, the ratio of successfully transmitted messages over the total number of messages that are either successfully transmitted or rejected, as well as node fairness. Node fairness is evaluated by the Jain fairness index as defined in Section III-B.

1) Results for TSCH: Table III provides the results obtained by TSCH in terms of normalized throughput, probability of empty slots, probability of collision in a slot, ratio of successful transmissions, for a number of nodes N ranging from 2 to 32. Notice that the throughput obtained by TSCH is very good, especially for small values of N . However, this excellent performance is obtained at the cost of some unfairness. This unfairness is maximized for N = 2. In such a scenario, we get simulation traces where the fairness is equal to 0.8371 only. We notice that in 10000 slots, 7441 transmission opportunities have been granted to node 1, compared with only 2896 transmission opportunities for node 2. As a consequence, 6821 messages from node 1 have been successfully delivered against only 2226 messages for node 2. This is reflected by the poor value of the Jain fairness index. The reason for this unfairness is the following: the node that succeeds in transmitting its message, immediately transmits its next message, whereas other nodes are waiting for the end of their backoff, that may reach 127 slots.

2) Results for slotted Aloha: Table IV depicts the results obtained by the simulation with NS3 of slotted Aloha for N ranging from 4 to 32 neighbors. Simulation results are very close to the theoretical ones. We observe that T hroughput = P success → 1/e, when N increases, as proved in [START_REF] Roberts | Aloha packet system with and without slots and capture[END_REF]. For any number of nodes, the fairness provided by this method is Figure 9 compares the performance of TSCH and the 1/N Aloha protocol in terms of normalized throughput. For all values of N in the range of 2 to 16, TSCH provides a higher throughput than 1/N Aloha. For 32 nodes, slotted Aloha outperforms TSCH.

3) Results for Backoff before any transmission: Results obtained when the backoff is used before each transmission are given in Table V. The normalized throughput obtained by this method is less than that provided by TSCH for a number of nodes strictly less than 32. For 32 nodes, the throughput obtained by this method and TSCH are very close. In all cases, it ensures a better fairness than TSCH, by reducing the probability of transmitting in the next slot for the successful transmitter.

Figure 10 depicts the normalized throughput obtained by TSCH and a variant implementing a backoff before each transmission. For all values of N strictly less than 32, TSCH provides a higher throughput than its variant applying a backoff before each transmission. For higher values, this method is better. 4) Results for Backoff before any transmission and a backoff window W = 2 * N : We now study a variant of the Backoffbefore-any-transmission method where the backoff window is constant and does not depend on the backoff stage. It is equal to W = 2 * N . Table VI depicts the simulation results obtained. We observe that when N increases, the performances provided by this method and slotted Aloha are very close in terms of normalized throughput and fairness, with a small advantage to slotted Aloha. However, this method provides a higher rejection probability than slotted Aloha. We also notice that compared with TSCH, it provides a higher fairness, because the node having successfully transmitted its message must draw a backoff before transmitting its next message. Figure 11 depicts the normalized throughput obtained by TSCH and a variant that implements a backoff before each transmission with a backoff size W = 2 * N . For all values of N in the range of 2 to 32, TSCH provides a higher throughput than its variant applying a backoff before each transmission with W = 2 * N , when the number of nodes is less than or equal to 16. For 32 nodes the backoff method with W = 2 * N provides the highest throughput.

5) Comparative performance evaluation of the four collision avoidance methods: Figures 12, 13, 14 and 15 allow us to compare the performance of the four collision avoidance methods studied in this paper, namely TSCH, Backoff before each For all these values of N , the 1/N Aloha protocol provides the best node fairness (higher than 0.9968) and the best ratio of successfully transmitted messages (higher than 0.8467). This is explained by the fact that each node receives a fair share (i.e. 1/N ) of the bandwidth. We recall that in slotted Aloha each node transmits in each slot with a probability equal to 1/N . The protocol used by TSCH provides the highest normalized throughput (higher than 0.4265) up to 16 nodes, the smallest ratio of empty slots (less than 0.1279), but the worst fairness (less than 0.9614 for 4 nodes). This is because the node that succeeds in transmitting its message, immediately transmits its next message, whereas other nodes are waiting for the end of their backoff. For 32 nodes, the best normalized throughput is obtained by slotted Aloha.

The protocol based on a backoff before each transmission provides a normalized throughput smaller than TSCH (0.4332 and 0.3807 for 8 and 16 nodes, respectively) but higher than the 1/N Aloha protocol (0,3927 and 0.3806 for 8 and 16 nodes, respectively). For 32 nodes, the throughput becomes very close to that obtained by TSCH. It also ensures a better fairness than TSCH (higher than 0.986).

The protocol applying a backoff before each transmission with a backoff window W = 2 * N provides results that are very close to slotted Aloha. These results become closer when N the number of competitors increases. However, the normalized throughput as well as the ratio of delivered messages are higher for slotted Aloha. Similarly, slotted Aloha provides the smallest probability of message rejection.

VII. CONCLUSION

In this paper, we have analyzed two medium access protocols operating in a wireless slotted network. Their performances have been evaluated by means of two new Markov models that take into account the unsuccessful transmission of the previous message. Extensive simulations show a very good match between the model and the simulation results. For a moderate medium load, the protocol performing a backoff before each transmission outperforms the TSCH protocol, when the number of neighboring nodes is greater than or equal to 8. For a smaller number of neighboring nodes, the TSCH protocol provides a higher throughput. For a high medium load, the TSCH protocol provides the highest normalized throughput at the cost of some unfairness in the transmission opportunities. An extension of this work could be to introduce a more accurate model of the physical layer, taking into account transmission decay, fading and capture phenomena. It would lead to a collision evaluation that is more representative of the real world.

ACKNOWLEDGMENT Study co-funded by CNES and Inria in the framework of the CNES Launchers Research and Technology program.

Fig. 1 .

 1 Fig. 1. Normalized throughput with slotted Aloha.

Fig. 3 .

 3 Fig. 3. The transmission probability τ = 0.1053 solution of f (τ ) = τ for N = 8.

Fig. 4 .

 4 Fig. 4. Model validation.

Fig. 5 .

 5 Fig. 5. The Markov chain of the collision avoidance method on shared slots of TSCH.

Fig. 6 .

 6 Fig. 6. The transmission probability τ = 0.1200 solution of f (τ ) = τ for N = 8.

Fig. 7 .

 7 Fig. 7. Model validation.

Fig. 8 .

 8 Fig. 8. Normalized throughput and probability of empty slots.

Fig. 9 .

 9 Fig. 9. Comparison between TSCH and 1/N Aloha.

Fig. 10 .

 10 Fig. 10. Normalized throughput obtained by TSCH and a variant implementing a backoff before each transmission.

Fig. 11 .

 11 Fig. 11. Normalized throughput obtained by TSCH and a variant implementing a backoff before each transmission with W = 2 * N .

Fig. 12 .

 12 Fig. 12. Comparative performance evaluation for 4 nodes.

Fig. 13 .

 13 Fig. 13. Comparative performance evaluation for 8 nodes.

Fig. 14 .

 14 Fig. 14. Comparative performance evaluation for 16 nodes.

Fig. 15 .

 15 Fig. 15. Comparative performance evaluation for 32 nodes.

  [START_REF] Sebbak | Majority-consensus fusion approach for elderly iot-based healthcare applications[END_REF]

	Probabilities
	Name	Meaning	Default value
	p	Probability of a collision when
		a node is transmitting
	τ	Node transmission probability
	r	Probability of staying Idle	1-1/N

TABLE II COMPUTATION

 II OF PROBABILITIES.

	Name	Meaning	Value
	τ	Probability for a node to transmit in a random slot	T otal number of transmissions S

TABLE III RESULTS

 III OBTAINED BY TSCH. In this protocol, each node receives a fair share of the bandwidth equal to 1/N . Notice that for 32 nodes, this collision avoidance method provides a better throughput than TSCH.

	N	T hroughput	P empty	P collide	P rejection	P success P success+P rejection	F airness
	2	0.91156	0.0292	0.05928	0.01820	0.9818	0.9578
	4	0.7682	0.0737	0.1581	0.0589	0.9410	0.9614
	8	0.5795	0.1167	0.3039	0.1552	0.8448	0.9720
	16	0.4265	0.1279	0.4456	0.3061	0.6939	0.9716
	32	0.3166	0.107	0.5765	0.4901	0.5099	0.9808
	excellent and the probability of rejecting a message, because the maximum number of transmissions is reached without any
	success, is kept lower than 15%.

TABLE IV SIMULATION

 IV RESULTS OF SLOTTED ALOHA FOR DIFFERENT NUMBERS OF COMPETITORS.

	N	T hroughput	P empty	P collide	P rejection	P success P success+P rejection	F airness
	4	0.4227	0.3160	0.2613	0.1107	0.8893	0.9997
	8	0.3936	0.3422	0.2643	0.1356	0.8644	0.9993
	16	0.3806	0.2643	0.2643	0.1475	0.8525	0.9986
	32	0.3732	0.1356	0.2641	0.1533	0.8467	0.9969

TABLE V RESULTS

 V OBTAINED BY THE PROTOCOL USING A BACKOFF BEFORE EACH TRANSMISSION.

	N	T hroughput	P empty	P collide	P rejection	P success P success+P rejection	F airness
	4	0.4765	0.3011	0.2224	0.1455	0.8545	0.9908
	8	0.4332	0.2546	0.3122	0.2538	0.7462	0.9882
	16	0.3807	0.2024	0.4170	0.3936	0.6064	0.9859
	32	0.3130	0.1412	0.5458	0.5625	0.4375	0.9873

TABLE VI RESULTS

 VI OBTAINED BY A BACKOFF BEFORE EACH TRANSMISSION AND W = 2 * N .

	N	T hroughput	P empty	P collide	P rejection	P success P success+P rejection	F airness
	2	0.4443	0.4444	0.1113	0.0315	0.9685	0.9999
	4	0.4092	0.4102	0.1806	0.1117	0.8883	0.9999
	8	0.3888	0.3901	0.2212	0.1768	0.8232	0.9998
	16	0.3779	0.3805	0.2416	0.2126	0.7874	0.9995
	32	0.3716	0.3749	0.2536	0.2342	0.7657	0.9990


Pascal Helson
email: pascal.helson@inria.fr

A MATHEMATICAL APPROACH ON MEMORY CAPACITY OF A SIMPLE SYNAPSES MODEL

 as part of a more ambitious aim which is to have a general mathematical framework adapted to many models of memory.

2.NETWORK MODELS OF MEMORY

Three main ingredients describes such models.

A stimulus has direct effect on neurons which then modify the synaptic weight matrix leading to a stable response of the network possessing the information sent by the stimulus.

3.AMIT-FUSI MODEL [9]

Discrete time model with two coupled binary processes, stimuli (ξ t ) t≥0 ∈ {0, 1} N and synaptic weight matrix (J t ) t≥0 ∈ {0, 1} N 2 :

Stimuli: (ξ t ) t≥0 i.i.d. random vectors ∼ Bernoulli(f ) ⊗N

Synaptic weights dynamic:

∀i J ii t = 0 and at each time step a new stimulus ξ t is received by the network. The components J ij t , i = j, jump as follows:

• if ξ i t , ξ j t = (1, 1), J ij t = 0 → J ij t+1 = 1 with probability q + ,
• if ξ i t , ξ j t = (0, 1), J ij t = 1 → J ij t+1 = 0 with probability q - 01 ,

• if ξ i t , ξ

j t = (1, 0), J ij t = 1 → J ij t+1 = 0 with probability q - 10 , • if ξ i t , ξ j t = (0, 0), J ij t+1 = J ij t . Remark:
The initial condition is not defined on synaptic weights but on the synaptic input into neurons defined as follows.

Synaptic input into neurons:

h i t t≥0
is the field induced by ξ 0 presented at time t, in neuron i:

h i t = j =i J ji t ξ j 0
In the following, we are interested in the laws of h i t |ξ i 0 = 0 and h i t |ξ i 0 = 1 , respectively called p 0 t and p 1 t . Remark: The state space of h i t depends on the size of ξ 0 : K = j =i ξ j 0 . Moreover, as neurons are similar we use notation h 1 t,K . Finally, it is easy to show p i t,K converges to a unique p ∞,K .

Initial condition:

Initially, synaptic input follows the stationary distribution:

h 1 0,K ∼ p ∞,K

4.RETRIEVAL CRITERIA

Many methods have been used to study the storage capacity of network models. The more intuitive is maybe to see stimuli to be learned as attractors of a neural dynamic [START_REF] Hopfield | Neural networks and physical systems with emergent collective computational abilities[END_REF]: the maximal number of attractors would then be the memory capacity of the model. Signal to Noise Ratio (SNR) analysis [START_REF] Benna | Computational principles of synaptic memory consolidation[END_REF][START_REF] Amit | Learning in Neural Networks with Material Synapses[END_REF] and mean first passage time to a threshold [START_REF] Elliott | Memory Nearly on a Spring: A Mean First Passage Time Approach to Memory Lifetimes[END_REF] have also been proposed. The underlying idea of these methods is that the neural dynamic is ruled by a threshold on the synaptic input: a linear decision rule. In our case, we don't impose such a rule. Our retrieval criteria holds on the knowledge of the two distributions p 0 t,K and p 1 t,K .

Decision rule [10]:

At fixed K, we aim at studying the minimal probability of error assuming the neuron 1 knows p i t and observes h 1 t . As p 1 t,K and p 0 t,K converges to p ∞,K , the error increases with time as distributions get closer: As long as the probability of error ,P e (t) defined below, is less than a given , ξ 1 0 is considered to be retrievable from h 1 t through the following decision rule. We are interested in the maximal time for which such a condition is achieved, and in particular we would like to know its dependence on the different parameters. We then define P e (t).

Let G = {g : [[0, N ]] → {0, 1}}: P e (t) = inf g∈G P g(h 1 t ) = ξ 1 0 = inf g∈G f P g(h 1 t ) = 0|ξ 1 0 = 1 + (1 -f )P g(h 1 t ) = 1|ξ 1 0 = 0 L(t,g)
Unlike the SNR analysis which requires only the first two moments of the variable h 1 t , here we need the knowledge of both p 1 t,K and p 0 t,K . Although it is more costly, it is always valid, which is not the case of SNR as it requires p 0 t and p 1 t to be approximately Gaussian and this is not the case for some parameters: , q + = 0.9, q -10 = 0.1, q -01 = 0.9

We see the difference between the two rules on the probability of error: A: f = 0.5 = q + = q -10 = q -01 . B: q + = q -01 = 0.9, q -10 = 0.1, f = 0.5.

SNR analysis:

In [START_REF] Amit | Learning in Neural Networks with Material Synapses[END_REF], they propose an analysis based on SN R t = S 2 t R t :

• Signal:

S t = E h 1 t | ξ 1 0 = 1 -E h 1 t | ξ 1 0 = 0 • Noise: R t = Var h 1 t
Because of correlation between synapses dynamics, SNR is only computed in a specific case leading to capacity P = max{t ∈ N, SN R t > log(N )}:

f = log(N ) N , q - 01 , q - 10 ∝ f q + ⇒ P ∝ N log(N ) 2 (1)

5.FIRST RESULTS

Mathematical results:

As having the general forms of p 1 t,K and p 0 t,K is difficult, we first studied the spectrum of the transition matrix M h,K of h 1 t t≥0 and got a first result: Proposition 1 The spectrum of the transition matrix M h,K and the one of ξ t , J j1 t 1≤j≤K t≥0

, M ξ,J,K is the following:

Σ M h,K ={µ i = (1 -f )(1 -f q - 01 λ 0 ) i + f (1 -(1 -f )q - 10 -f q + λ 1 ) i , 0 ≤ i ≤ K} Σ M ξ,J,K = Σ M h,K ∪ {0}, multiplicity K -1 i for µ i , 2 K for 0
In fact, the spectrum is linked to the speed at which stimuli are forgotten. However, the slower this speed is, the less plastic the network is. It is a classical compromise in optimising storage capacity.

Sketch of the proof for Σ M ξ,J,K

We can write M ξ,J,K as a matrix by block with p ξ = P (ξ t = ξ) and M ξ the probability matrix of (J j1 t ) j knowing that ξ t = ξ:

M ξ,J,K =        p ξ 1 M ξ 1 p ξ 2 M ξ 1 . . . p ξ 2 K M ξ 1 p ξ 1 M ξ 2 p ξ 2 M ξ 2 . . . p ξ 2 K M ξ 2 . . . . . . . . . . . . p ξ 1 M ξ 2 K p ξ 2 M ξ 2 K . . . p ξ 2 K M ξ 2 K        2 2K-1 ×2 2K-1 matrix It is not difficult to show Σ (M ξ,J,K ) = Σ   M J,K = 2 K k=1 p ξ k M ξ k   ∪ {0}
In particular, if π is an invariant measure of the process with matrix transition M J,K , πM J,K = π, then

π K = p ξ 1 π p ξ 2 π . . . p ξ 2 K π is an invariant measure for ξ t , J j1 t 1≤j≤K t≥0
. One can then compute M ξ from the following 2 × 2 matrices:

M 00 = I 2 , M 01 = 1 0 q - 01 1 -q - 01 , M 10 = 1 0 q - 10 1 -q - 10 , M 11 = 1 -q + q + 0 1
Then, using Kronecker product properties, we have the lemma:

Lemma 1 With the notation ⊗ N M = M ⊗ M ⊗ . . . ⊗ M N times , M J,K =(1 -f ) ⊗ K-1 ((1 -f )M 00 + f M 01 M 0 ) + f ⊗ K-1 ((1 -f )M 10 + f M 11 M 1
)

We conclude on Σ (M ξ,J,K ) using v 0 = [1 1] T and e 2 = [0 1] T :

M 0 v 0 = v 0 = M 1 v 0 , M 0 e 2 = λ 0 e 2 and M 1 e 2 = λ 1 e 2 + f q + v 0 Let u i,K = (u 1 i,K , . . . , u K i i,K
) vectors which can be written as the Kronecker product of i vectors e 2 and (K -i -1) v 0 , u 1 i,K = ⊗ i e 2 ⊗ K-1-i v 0 , then:

M J,K u j i,K =    (1 -f )(λ 0 ) i + f (λ 1 ) i µ i    u j i,K + i-1 k=0 l α k,l u l k,K
In this basis, M J,K is triangular superior with µ i on the diagonal with the multiplicity K-1 i , it ends the proof on Σ (M ξ,J,K ).

Simulation for shaping intuition:

Thanks to simulations, we have a look to the case f and q small: The independent case is the model considering every J ij t evolves independently following the dynamic of one synapse in the model defined in 3. We can see in simulations that the behaviour of h 1 t is similar to the one in the independent case when f and q are small enough. Moreover, this model of independent synapses leads to similar results as (1) for the SNR analysis. Finally, under the assumption that synapses evolve independently, π i t ,the equivalent of p i t in the previous model, are binomial laws. In fact, J ij t converges in law to the invariant distribution π = π -, π + with speed

λ t = 1 -f 2 q + -f (1 -f )(q - 01 + q - 10 ) t
. Hence, we get the following results thanks to the generating function:

π 0 t,K ∼ B K, π + -π + q - 01 λ t , π 1 t,K ∼ B K, π + + π -q + λ t
Therefore, it seems to be possible to extend the result (1) for a larger range of parameters f and q thanks to the similarities between the independent model and the one presented in 3 when f and q are small. However, such a similarity would reduce the model to a too simple model loosing its initial interest.

6.CONCLUSION

When previous studies have considered small coding level f in order to get results on the storage capacity depending on N , such an assumption seems to make the model loose its initial interest sited in the correlations between synapses. Our approach aims at studying the synaptic input into a neuron taking correlations into account through a decision rule. It enabled us to get a first result on the speed of forgetting stimuli thanks to a spectral analysis.

7.PERSPECTIVES

• Show p ∞,K converges to π ∞,K when f , q are small • Control the probability of error thanks to the study in the independent case: f , q small

• A study of the probability of error taking into account all the vector h t

• Add neural dynamics as a feedback to maintain weights structure longer and enhance storage capacity

Fig:

  Fig: Distributions p i t when f = 0.1 and parameters q +/x = 0.5. At time t = 0, the two distributions are well separated (left) and then get closer(right).

  Distribution of p i 3 and p ∞ .

  Fig: Parameters are the following: f = 0.5, q + = 0.9, q -10 = 0.1, q

  linear rule, K=100 linear rule, K=1000 Bayes rule, K = 10 Bayes rule, K = 100 Bayes rule, K = 1000

  linear rule, K=100 linear rule, K=1000 Bayes rule, K = 10 Bayes rule, K = 100 Bayes rule, K = 1000

Fig:

  Fig: Probability of error in function of linear (SNR) and Bayes (the one we use) rules and parameters.

  distributions when f = 0.1 and K = 1000.