Ines Khoufi
email: ines.khoufi@gmail.com

Pascale Minet
email: pascale.minet@inria.fr

An Enhanced Deterministic Beacon Advertising Algorithm for Building TSCH Networks

Keywords: TSCH network, beacon advertising, node joining time, network building

In this paper, we focus first on the time needed by a node to join a Time Slotted Channel Hopping (TSCH) network, this time is called joining time. Second, we are also interested in the network building time. Since the data generated by a sensor node remain unavailable as long as this node has not yet joined the wireless sensor network, these times are of prime importance for applications having strong latency requirements on data gathering. The joining time depends on the beacon advertising policy that has been left unspecified by the standard. The contribution of this paper is triple. First, we propose an Enhanced Deterministic Beacon Advertising algorithm, called EDBA, that ensures a collision-free advertising of beacons and minimizes the average joining time. Second, we model the behavior of a joining node by a Markov chain, validated by NS3 simulations, and compute the average joining time. Third, we compare the performance of EDBA with this of MBS, considered as the best beacon advertising algorithm in the literature.

Context and motivation

The Time Slotted Channel Hopping (TSCH) mode has been designed as a part of the IEEE 802.15.4e [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] amendment to meet the requirements of latency, throughput and robustness of applications belonging to industrial automation, process control and equipment monitoring. TSCH is the most used mode among the five modes introduced in this amendment (see [START_REF] De Guglielmo | IEEE 802.15.4e: A survey[END_REF] for a survey of this amendment). In the following of this paper, an IEEE 802.15.4e TSCH network is denoted a TSCH network, for brevity reason.

TSCH provides time-synchronized communications (time slots) and uses different channels in parallel with frequency hopping. Figure 1 illustrates a schedule of transmissions on 16 frequencies using a periodic slotframe of 28 time slots. The transmissions belonging to this schedule are represented by colored rectangles. Each transmission is defined by its transmitter, its receiver(s), its channel offset depicted in the vertical axis and a slot offset in the horizontal axis. The pair (slotof f set, channelof f set) is called cell in this paper. At each slot change, the mapping of channel offsets to real frequencies changes. The ASN of a slot is its Absolute Sequence Number, starting from 0. The slot offset can be deduced from the ASN as follows: slotof f set = ASN modulo S n , where S n denotes the number of slots in the slotframe. Since a multichannel TDMA medium access is used for data gathering, there is no collision on data. Hence, a higher throughput is obtained. In addition, channel hopping significantly reduces the effects of multipath and interferences, improving network robustness. TSCH supports star, tree and meshed topologies.

Unlike most of the studies on IEEE 802. [START_REF] Accettura | Decentralized traffic aware scheduling in 6tisch networks: Design and experimental evaluation[END_REF].4e networks that focus on communications in an operational network, we focus on two times:

the joining time, defined as the time needed by a node J to join an existing TSCH network. We evaluate this time as the time needed by J to detect a valid beacon. the network building time, defined as the time needed to build the network consisting of a given number of nodes that are powered on successively. The network building time is equal to the time at which the last node joins the network minus the time at which the CPAN (i.e. the network coordinator) has been powered on.

Both times matter for industrial applications that have strong latency requirements on data gathering. As long as a sensor node has not joined the network, its data remain unavailable and cannot be exploited. A node has to join the network at least once: either when the network is built, or later if the node arrives late or it replaces a failed one. In all cases, the joining node is unable to join the network as long as it has not detected a valid beacon. Network building is performed by nodes joining the network, successively and/or in parallel. All the solutions proposed to join a TSCH network are based on the following basic principle:

-The joining node randomly selects a frequency among those used by the TSCH network it wants to join. It listens on this frequency until detecting a valid beacon. A beacon is a TSCH frame that contains useful information about synchronization, channel hopping and time slot used in the network considered. -Nodes having joined the network periodically advertise beacons. Initially, only the CPAN is allowed to send beacons. The presence of the CPAN is mandatory to initiate the creation of the network.

With TSCH, the joining node J has to face a triple problem:

1. First, the beacon advertising policy is voluntarily left unspecified by the standard. 2. Second, the main difficulty with a TSCH network comes from the frequency hopping and the simultaneous use of several channels. How to ensure that any node J that wants to join the network is listening on the frequency used by a network node advertising its beacon and located in the neighborhood of J? 3. Third, as beacons are broadcast, they may collide. In such a case, the collision remains undetected and the important information they carry is lost. How to avoid collisions between nodes advertising beacons? In [START_REF] Cano | A Learning Approach to Decentralised Beacon Scheduling[END_REF], the authors propose a distributed algorithm where each node selects the slot to transmit its beacon with a probability depending on the feedback provided by its neighbors. This algorithm is proved to converge almost surely in a finite time. In [START_REF] Choudhury | Beacon Synchronization and Duty-Cycling in IEEE 802.15.4 Cluster-Tree Networks: A Review[END_REF], the authors jointly address beacon synchronization and duty cycling in IEEE 802.15.4 cluster tree networks, and show how to maximize energy saving.

We propose the Enhanced Deterministic Beacon Advertising Algorithm, called EDBA, to solve this triple problem. This paper is organized as follows. After a brief state of the art, we present the main principles of EDBA and illustrate its behavior with some examples in Section 2. In Section 3, we build a model for a node joining a TSCH network using the EDBA algorithm. We derive the average joining time as a function of the number of nodes present in the network and the number of advertising slots, taking into account the unreliability of wireless links. The performance of EDBA is compared in Section 4 with this of MBS [START_REF] Guglielmo | A Model-based Beacon Scheduling algorithm for IEEE 802.15.4e TSCH networks[END_REF], the algorithm considered as the best one in the literature. Finally, we conclude in Section 5.

Related work

Since TSCH [START_REF] Watteyne | Industrial wireless IP-based cyber-physical systems[END_REF] provides low latency due to its multi-channel and time-slotted medium access, many papers use a TSCH network for data gathering. For example, papers published in [START_REF] Khoufi | Scheduling transmissions with latency constraints in an IEEE 802.15.4e TSCH network[END_REF][START_REF] Rekik | A Performance Analysis of Orchestra Scheduling for TSCH network[END_REF][START_REF] Yang | Analysis of Low Latency TSCH Networks for Physical Event Detection[END_REF] conclude that TSCH networks can be used to achieve low latency event detection or data gathering with a careful setting of TSCH scheduling parameters. Some authors propose a centralized scheduling for scheduling data transmissions such as in [START_REF] Soua | MODESA: An optimized multichannel slot assignment for raw data convergecast in wireless sensor networks[END_REF], whereas others favor a distributed one such as in [START_REF]Wave: A distributed scheduling algorithm for convergecast in ieee 802.15.4e tsch networks[END_REF], [START_REF] Accettura | Decentralized traffic aware scheduling in 6tisch networks: Design and experimental evaluation[END_REF] and [START_REF] Domingo-Prieto | Distributed pid-based scheduling for 6tisch networks[END_REF]. However, in these studies, the TSCH network is assumed to be established. In this paper, we show how to build the TSCH network in order to reduce the network joining time.

To solve the problem raised by multichannel during network building, some authors like [START_REF] Minet | Multichannel Wireless Sensor Networks for Structural Health Monitoring of Aircraft and Launchers[END_REF] want to reduce the time spent and the energy consumed in this phase. They propose to dedicate a channel to beacons. Hence, a joining node has only this channel to scan, whereas network nodes have to periodically advertise their beacons on this channel. This is not easy to apply in a TSCH network, where the schedule is established for channel offsets that are virtual and not for physical frequencies that are real.

That is why in the state of the art, it is usually assumed that several frequencies are used to advertise beacons. In the Random-based Advertisement (RA) algorithm [START_REF] Guglielmo | A performance analysis of the network formation process in IEEE 802.15.4e TSCH wireless sensor/actuator networks[END_REF], each network node advertises its beacon in advertising slots with a probability computed from the number of nodes advertising a beacon. The authors show that the joining time mainly depends on the number of channel offsets used for beacon advertisement. A reduced joining time is obtained when only a subset of frequencies is used for beacon advertisement. This subset should be known from the joining nodes.

In [START_REF] Vogli | Fast Join and Synchronization Schema in the[END_REF], the authors present two algorithms: Random Vertical (RV) and Random Horizontal (RH), illustrated in Figures 2a and2b. In both algorithms, the CPAN sends its beacon in slot offset 0 and channel offset 0. In RV, the other nodes transmit their beacon in the same slot offset but with a random channel offset. In RH, the other nodes transmit their beacon with channel offset 0 but in an random slot offset. The authors show that these algorithms have similar performance.

In [START_REF] Guglielmo | A Model-based Beacon Scheduling algorithm for IEEE 802.15.4e TSCH networks[END_REF], the authors model the behavior of a joining node as a Markov chain. They derive the joining time from this model, assuming that the number of channels available N c and the number of slots in the slotframe N s are coprime (i.e. their greatest common divisor is 1), and for each slot offset in the slotframe, the mapping between the channel offset and the channel frequency is bijective. The optimal beacon schedule is formalized as an optimization problem where the joining time is minimized under the constraint that the sum of the distances between the advertising slots is equal to N c N s . The authors finally propose the Model-based Beacon Scheduling algorithm (MBS), where the CPAN broadcasts the optimal cells (channel offset, slot offset) for beacon advertising. Each network node randomly selects one cell among the optimal cells to transmit its beacon. A comparative performance evaluation is made between MBS, RA, RV and RH. MBS is the best one, even if it is subject to collisions when several nodes transmit their beacon in the same cell.

The Enhanced Deterministic Beacon Advertising algorithm

Before presenting the Enhanced Deterministic Beacon Advertising algorithm, called EDBA, we define a generic framework to allow nodes to join a TSCH network.

General framework

Before giving the assumptions used in this study, we recall some mathematical results.

Two positive integers are said co-prime if and only if they have no common divisor higher than 1. Hence their least common multiple is equal to their product.

We adopt the following assumptions:

-A0: For each slot offset in the slotframe, the channel hopping sequence is a bijection from the set of channel offsets to the set of channel frequencies used by the TSCH network considered. In addition, for simplicity reasons, in all the examples taken, this bijection is the identity for slot offset 0.

-A1: The slotframe has N s slots.

-A2: The TSCH network uses N c channels.

-A3: N s and N c are coprime and S denotes their product.

-A4: The slotframe contains N b beacon cells.

-A5: The spacing between two successive beacon cells b i and b i+1 in S successive slots is equal to: With the Assumptions A0 to A4, we can restrict our study to S successive slots and prove the following properties:

ASN (b i+1 ) -ASN (b i ) if ASN (b i+1 ) > ASN (b i ), ASN (b i+1 ) + N s × N c -ASN (b i ) otherwise.
Property 2 In S successive slots, each cell (s, c), with s ∈ [0, N s -1] and c ∈ [0, N c -1]
, is mapped exactly once on each of the N c frequencies.

P roof : We first observe that each cell (s, c) visits each frequency at least once in slots of ASN = 0 to S -1. By contradiction, we assume that a given frequency is visited more than once by a given cell (s, c), this would mean that there is an ASN ∈ [N s , S -1] that is mapped on the same frequency as (s, c). This is impossible because of A0 and A3. Hence, the property.

Property 3

In S successive slots, there are N b beacon cells mapped exactly once on each of the N c frequencies.

P roof : In S successive slots, there are N c slotframes. Since there are N b beacon cells per slotframe. We get a total of N b × N c beacon cells for S successive slots. According to Property 2, each beacon cell is mapped on each frequency used by the network. Hence, the property. In Figure 3a where N s = 7 and N b = 3, Algorithm 1 gives the pattern Reduced-Reduced-Large = 2R -L. Then slots 0, 2 and 3 are dedicated to beacons advertising. In Figure 3b, N s is equal to 11 and N b equal to 4. Then, the pattern obtained is 3L -R and slots 0, 3, 6, 9 are beacon slots. The last example is shown in Figure 3c of size L and the number of reduced spacings of size R between two successive beacons -The CPAN applies an horizontal first policy. It assigns first the cell with the smallest slot offset higher than the slot offset where the correct beacon has been received, modulo the slotframe size. If several exist, it selects the cell with the smallest channel offset. -Any advertising node, that is not the CPAN, transmits its beacon in a beacon cell computed by the CPAN during the association of the node. -Multi-hop association ensures the uniqueness of transmitters in this beacon cell.

Algorithm 1 Assignment of beacon slots in the slotframe.

u = Ns modulo N b Large = Ns N b Reduced = Ns N b if u ≤ N b -u then if u ==

Properties of EDBA

We first establish the condition under which there is no beacon collision with EDBA and then prove some properties.

Condition 1 N b ≥ Nn-1
Nc + 1, where N n denotes the maximum number of neighbors of a node.

Property 4 With the Condition 1, EDBA ensures the absence of collisions between nodes advertising their beacon.

P roof : In order to enable each node to listen to the beacon sent by the CPAN, no node other than the CPAN transmits its beacon in slot offset 0. Hence, the total number of beacon cells available is equal to 1 + (N b -1)N c . As a consequence, the maximum number of neighbors of a node, denoted N n is limited to this number 3 Markov Chain for a joining node with EDBA

N n ≤ 1 + (N b -1)N c ,

Model presentation

As previously said, a node J wanting to join a TSCH network randomly selects a frequency f among the frequencies used by the TSCH network and listens to this frequency to hear a valid beacon. Since the schedule of a TSCH network repeats in slot offsets and frequencies every S = N c × N s slots, we consider S successive slots denoted s i , with 0 ≤ i ≤ S -1. The joining node is powered on at a random time. As a consequence, it has a probability of 1/S to be powered on in any given slot among the S slots considered. The state of the joining node can be modeled by the slot offset in this period, that is ASN modulo S. We denote such a state s i , with 0 ≤ i ≤ S -1. The behavior of a joining node can be modeled by a discrete time Markov chain shown in Figure 4, where the time granularity is the slot duration. We distinguish whether the slot s i is a beacon slot granted to a neighboring node of the joining node J with a channel offset mapped on frequency f . In such a case, the slot, also called state, s i is denoted b j and belongs to B, the set of beacon slots assigned to a neighbor of J and mapped on frequency f . The joining node J transits from s i / ∈ B to s i+1 with a probability 1 corresponding to the transition to the next slot. It transits from s i ∈ B to:

the absorbing state Joined with a probability 1 -P loss , where 1 -P loss is the probability of receiving a valid beacon sent on the listen frequency f . the next slot s i+1 with a probability P loss .

Unlike the Markov model designed in [START_REF] Guglielmo | A Model-based Beacon Scheduling algorithm for IEEE 802.15.4e TSCH networks[END_REF] for MBS, where the number of beacon slots mapped on frequency f in S successive slots is always equal to N b , this model takes into account a number of beacon slots that is equal to N n the number of nodes having already joined the network that are neighbors of J. Hence, in the Markov model, there are at least N n beacon slots mapped on frequency f . As a consequence, the index j in the b j state, ranges from 0 to N n -1.

Computation of the joining time

With this model, we are able to compute the average joining time of a node. This time depends on N b , N s , N c and N n . Let η i denote the number of transitions from any state s i to the Joined state. Let nextb(s i ) denote the next beacon state in B following s i / ∈ B. Let d(s i , s j ) denotes the distance between slots s i and s j . This distance is expressed by a number of slots. It is equal to:

s j -s i if s j ≥ s i s j + N s -s i otherwise.
We get:

η i = d(s i , nextb(s i )) + η nextb(si) if s i / ∈ B
(1 -P loss ) + P loss η nextb(si) otherwise

Let b 0 denote the first beacon slot in the S successive slots considered and b N n-1 the last one. Hence, we have b N n = b 0 . We can deduce the value of η 0 , η j and finally η Nn-1 as follows:

η b0 = 1 + N n-1 i=0
P i loss d(bi,bi+1) 1-P N n loss and more generally for 0 ≤ j ≤ N n -1

η bj = 1 + N n-1 i=0 P i+N n-j loss d(bi,bi+1) 1-P N n loss + N n-j i=1 P i loss d(b j+i-1 , b j+i ).
Let T Join denote the joining time. it is equal to the sum of the numbers of transitions to the Joined state from each state s i divided by S the total number of states.

T Join = S-1 i=0 η i S (2)
For reliable wireless links with P loss = 0, we obtain η i = 1 for any s i ∈ B, leading to:

T Join = 1 S   N n + N n-1 j=0 d(b j , b j+1 )(d(b j , b j+1 ) -1) 2   (3)
For unreliable wireless links, we get:

T Join = 1 S   N n + N n-1 j=0 d(b j , b j+1 )(d(b j , b j+1 ) -1) 2 + Nn-1 i=0 P i+N n-j loss d(b i , b i+1 ) (4)

Model validation

We assume that the joining node is joining a network consisting of 1 to 10 nodes. The CPAN is denoted node 0. The node i joins the network consisting of nodes 0 to i -1. This joining time is expressed as a number of slots, each slot having a duration of 10 ms. We report here the joining time obtained for N c = 5, N s = 3 and N b = 3 to highlight the differences with the model of MBS given in [START_REF] Guglielmo | A Model-based Beacon Scheduling algorithm for IEEE 802.15.4e TSCH networks[END_REF]. For this example, we assume the simple frequency mapping given in Table 1. In this table slof denotes the slot offset whereas chof denotes the channel offset. Results are given in Table 2, where a star denotes a beacon slot. In Table 1 When the CPAN is the only node in the network, it sends its beacon in slot offset 0 and channel offset 0 by design of EDBA. According to Table 1, this cell is mapped on frequency 0 for ASN = 0 modulo N s N c . The number of transitions to the Joined state is equal to 1 for this ASN and is computed according to Equation 1 for the other ASNs. Hence, the third column of Table 2. When node 1 is inserted, it sends its beacon in slot offset 1 and channel offset 0, according to EDBA. According to Table 1, this cell is mapped on frequency 0 for ASN = 10 modulo N s N c . The number of transitions to the Joined state is equal to 1 for this ASN and is computed according to Equation 1 for the other ASNs. We get the fourth column of Table 2, and so on.

This model has been validated by means of simulations with NS3 [20]. We first implemented the NS3 modules needed to build a 802.15.4 network and then the NS3 modules for a TSCH network. Each simulation result reported in this paper is the average of 200 simulations. We compute the average, the standard deviation and the 95% confidence interval of these simulations runs and represent the average and the error bars in all figures showing the simulations results. We compare the average joining time obtained by computation based on the model and by simulation, when N n neighbors of the joining node send beacons, with 1 ≤ N n ≤ 10. For the model, the average joining time is obtained as the average of each column of Table 2. Figure 5 shows the average joining time obtained with the model and the NS3 simulations for a number of neighbors N n ranging from 1 to 10. Simulation results corroborate the model results. Hence, the Markov model is validated.

Main differences with MBS

We now compare the joining time obtained by EDBA and MBS, when the number of nodes advertising their beacon ranges from 1 to 10, assuming a one-hop network and taking the values N c = 5, N s = 3 and N b = 3 adopted in [START_REF] Guglielmo | A Model-based Beacon Scheduling algorithm for IEEE 802.15.4e TSCH networks[END_REF]. The joining times are illustrated in Figure 6. When the number of advertising nodes is less than or equal to 2, MBS and EDBA obtain the same joining time. With EDBA, the joining time continuously decreases when the number of advertising nodes increases up to 10. This is not the case with MBS. The reason is due to the collisions, since the advertising nodes randomly select one of the two beacon cells, the third one being reserved to the CPAN. Notice that to avoid an unbounded waiting time for the joining node in the MBS simulations, the beacon cell of the CPAN is not shared with other nodes. As a consequence, the joining time is upper-bounded by N s N c = 15 slots for MBS, whereas it is much smaller for EDBA as shown in Figure 6.

Comparative performance evaluation

In this section, our goal is to evaluate the time needed to join the network and then to build the network, as well as the number of beacons transmitted and the number of beacons dropped due to collisions. We compare the performance of EDBA with this of MBS [START_REF] Guglielmo | A Model-based Beacon Scheduling algorithm for IEEE 802.15.4e TSCH networks[END_REF], assuming that the nodes join the network one after the other. We start by considering reliable wireless links where beacons are transmitted with a loss probability P loss = 0. Then, we consider unreliable wireless links where beacons are lost with probability P loss ∈ {10%, 20%, 30%}. The performance evaluation is conducted using the NS3 simulator. The NS3 simulator allows us to take into account the communication protocols used in real TSCH networks. With simulation, we are also able to compare the solutions evaluated in more detailed way. For instance, we can compute the number of lost beacons. The topology considered is a star topology where each node is in radio range of each other. The number of nodes range from 1 to 40.

The number of channels is the default one N c = 16, the number of slots in the slotframe N s is equal to 101. All the nodes successively join the network in the order of their identifier. Hence, when node i ∈ [2, 40] joins the network, all the nodes with an identifier strictly less than i advertise their beacon.

Reliable wireless links

In this subsection, the wireless links are assumed to be reliable. Figures 7, 8 and 9 illustrate the joining time obtained by MBS and EDBA when the number of beacon cells in the slotframe N b is equal to 5, 10 or 15 respectively. When the number of advertising nodes is low, the joining time is high for both MBS and EDBA. This joining time decreases when both the number of advertising nodes and the number of beacon cells in the slotframe increase.

When the number of advertising nodes is strictly less than N b , MBS may provide a smaller joining time than EDBA. This is explained by the design of MBS where each advertising node randomly selects a cell among the N b cells in each slotframe to advertise its beacon and these cells are fairly distributed among S successive slots, whereas EDBA uses a number of beacon cells that is equal to the minimum between N b and the number of advertising nodes. However, EDBA offers a much smaller joining time than MBS, as soon as the number of advertising nodes is higher than the number of beacon cells in the slotframe. For instance, when the number of advertising nodes is 40, the average value of joining time is 20.7 for EDBA and 104.3 for MBS. With MBS, we observe an increased time needed to join the network in this case, due to collisions. As soon as each beacon cell, except this reserved for the CPAN, is selected by more than one node, a node that wants to join the network has to wait for the next beacon from the CPAN. Then, the maximum joining time is equal to N c times the size of the slotframe. Figure 10 shows for each joining node, the average number of beacons transmitted since the previous node started its beacon detection, for N b = 5, 10 and 15. In other words, the number of beacons sent between two successive node insertions. EDBA is a deterministic solution that avoids beacon's collision. However, many beacons may collide with MBS since this solution is based on a random selection of the advertising cells. This explains why with EDBA, this number remains stable: the node that wants to join the network promptly detects a beacon. With MBS, the number of beacons tends to in- crease with the number of advertising nodes due to the increased number of collisions.

Figure 11 shows the average number of beacons dropped for N b = 5, 10 and 15 for both EDBA and MBS. Since EDBA is deterministic, the number of beacons dropped is 0. However, with MBS, this number increases when the number of advertising nodes increases. This is due to the random selection of beacon cells that leads to collisions. In Figure 12, we illustrate the joining time of each node. When unreliable wireless links are considered, the time the node waits until it detects a beacon is very large. This is due to, first, the few number of advertising nodes, second, beacons loss. When unreliable wireless links are considered and the number of advertising nodes increases, the node joining time is still high with MBS, however, with EDBA it becomes very close to the value obtained in case of reliable wireless links. Table 3 gives the cumulative network joining time for both solutions EDBA and MBS in terms of slots. This cumulative joining time can also be considered as the network building time, when nodes successively join the network. When wireless links are reliable, we can see that with EDBA the network building time is 36% less than the time provided by MBS.

In case of unreliable wireless links, the time needed to build the network considerably increases for both solutions. However, EDBA still performs better than MBS. This can be explained by the fact that with MBS beacons can be lost not only because of unreliable wireless links but also collisions. Hence the very large delay to build the network. However, with EDBA, we can lose beacons when wireless links are unreliable but there is no beacon collision due to its deterministic principle. for N b = 10

Figure 13 shows the network building time for both MBS and EDBA. In this figure, we can see the time needed to insert an additional node in the network as a function of neighboring nodes having already joined the network. EDBA and MBS provide close results when the number of nodes is small. However, when the number of nodes increases, EDBA performs better than MBS.

Conclusion

The optimization of the time needed by a node to join a TSCH (Time Slotted Channel Hopping) network led us to specify the advertising beacon policy. We proposed the EDBA (Enhanced Deterministic Beacon Advertisinq) algorithm. This algorithm ensures that each node advertises its beacon without collision. The beacon cells are fairly distributed in the slotframe. The behavior of a joining node has been modeled by a Markov chain from which the average joining time is computed, taking into account the reliability of wireless links. An intensive performance evaluation based on NS3 simulations allows us to validate this model and conclude on the very good performance of EDBA, even when compared with MBS, considered as the best advertising algorithm in the literature.

Fig. 1 :

 1 Fig. 1: An example of a TSCH schedule.

Fig. 2 :

 2 Fig. 2: Random Vertical and Random Horizontal algorithms.

Property 1

 1 The TSCH schedule repeats in time slots and frequencies each lcm(N c , N s ) slots, where lcm(N c , N s ) denotes the least common multiple of N c and N s . Let us first show why Assumption A3 is required. Let us assume that N c and N s have a common divisor > 1. In this condition, any given cell (s, c) with s ∈ [0, N s -1] and c ∈ [0, N c -1] is not mapped on all the N c frequencies, even when considering S successive slots. Since this cell appears lcm(Nc,Ns) Ns < N c times in the S slots considered, it cannot be mapped on the N C frequencies. Hence, the justification of Assumption A3. Example 1: With N s = 15 and N c = 6, only two frequencies are visited.

2. 2

 2 Principles of EDBA EDBA ensures a fair distribution of the N b beacon slots in the slotframe, as illustrated by the different examples shown in Figure 3. The spacing between two successive beacon slots may be Large of size L = Ns N b or Reduced of size (a) Ns = 7 and N b = 3, pattern = 2R-L. (b) Ns = 11 and N b = 4, pattern = 3L-R. (c) Ns = 17 and N b = 5, pattern = 2(L-R).

Fig. 3 :

 3 Fig. 3: Examples of beacon slot assignment.

  , where N s = 17 and N b = 5. Algorithm 1 provides the pattern 2(R -L) to determine the beacon slots which are in this case : 0, 3, 7, 10, 14. More precisely, EDBA is based on the following principles: -Any beacon is transmitted in one of the N b advertising cells of the slotframe. -The CPAN initiates the beacon transmission in the first advertising cell with channel offset 0 and slot offset 0. -The N b advertising cells are regularly spaced in the slotframe according to Algorithm 1. The intuitive idea of this algorithm is first to compute the number of large spacings of size L = Ns N b and the number of reduced spacings of size R = Ns N b between two successive beacons in the slotframe, and second to build a pattern from these two types of patterns that is repeated in the slotframe. This is illustrated by the examples shown in Figure 3. -There are u = N s modulo N b Large spacings of size L = Ns N b ; -There are N b -u Reduced spacings of size R = Ns N b ; -The beacon slots are assigned according to Algorithm 1. The intuitive idea of this algorithm is first to compute the number of large spacings

  0 then assign a beacon slot each Ns N b slots starting from slot 0 else build u patterns, each pattern made of N b -u u Reduced spacings followed by one Large spacing if N b modulo u > 1 then insert a Reduced spacing each u N b modulo u patterns and this up to (N b modulo u) -1 times end if end if else if u == N b then assign a beacon slot each Ns N b slots starting from slot 0 else build N b -u patterns, each pattern made of u N b -u Large spacings followed by one Reduced spacing if u modulo (N b -u) > 1 then insert a Large spacing each N b -u u modulo (N b -u) patterns and this up to (u modulo (N b -u)) -1 times end if end if end if

1 . 5 Property 6

 156 leading to N b ≥ Nn-1 Nc + Property With the Condition 1, EDBA is deterministic. P roof : deduced from Property 4. With the Condition 1, the maximum joining time can be computed as a function of N s , N c and N b and the number of neighboring nodes having already joined the network. P roof : see the computation of the joining time in the next section.

Fig. 4 :

 4 Fig. 4: The Markov model of a joining node with EDBA.

Fig. 5 :

 5 Fig. 5: Validation of the Markov model by NS3 simulations.

Fig. 6 :

 6 Fig. 6: Joining time obtained by EDBA and MBS.

Fig. 7 :Fig. 8 :

 78 Fig. 7: The joining time obtained by MBS and EDBA for reliable links (N b =5).

Fig. 9 :

 9 Fig. 9: The joining time obtained by MBS and EDBA for reliable links (N b =15).

  N b = 15.

Fig. 10 :

 10 Fig. 10: Average number of beacons transmitted

Fig. 11 :

 11 Fig. 11: Average number of beacons dropped

Fig. 13 :

 13 Fig. 13: Average building time (slot) for N b = 10.

Table 1 :

 1 and Table2, ASN modulo N s N c is denoted Am. Frequency mapping.

	slof	0	1	2	0	1	2	0	1	2	0	1	2	0	1	2
	Am	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
	chof0	0	1	2	3	4	0	1	2	3	4	0	1	2	3	4
	chof1	1	2	3	4	0	1	2	3	4	0	1	2	3	4	0
	chof2	2	3	4	0	1	2	3	4	0	1	2	3	4	0	1
	chof3	3	4	0	1	2	3	4	0	1	2	3	4	0	1	2
	chof4	4	0	1	2	3	4	0	1	2	3	4	0	1	2	3

Table 2 :

 2 Number of transitions to the Joined state.

							Joining node
			1	2	3	4	5	6	7	8	9	10
		0	1*	1*	1*	1*	1*	1*	1*	1*	1*	1*
		1	15	10	5	4	4	4	4	4	2	1*
		2	14	9	4	3	3	3	3	3	1*	1*
		3	13	8	3	2	2	2	2	2	2	2
		4	12	7	2	1*	1*	1*	1*	1*	1*	1*
		5	11	6	1*	1*	1*	1*	1*	1*	1*	1*
		6	10	5	5	5	5	5	3	2	2	2
	Am	7	9	4	4	4	4	4	2	1*	1*	1*
		8	8	3	3	3	3	3	1*	1*	1*	1*
		9	7	2	2	2	2	2	2	2	2	2
		10	6	1*	1*	1*	1*	1*	1*	1*	1*	1*
		11	5	5	5	5	4	3	3	3	3	1*
		12	4	4	4	4	3	2	2	2	2	2
		13	5	3	3	3	2	1*	1*	1*	1*	1*
		14	5	2	2	2	1*	1*	1*	1*	1*	1*

  Fig. 12: Average joining time (slot) for N b = 10.

					MBS -reliable links
					EDBA -reliable links
					MBS -10% loss
					MBS -20% loss
					MBS -30% loss
					EDBA -10% loss
					EDBA -20% loss
					EDBA -30% loss
		EDBA				MBS
	Reliable	Unreliable		Reliable	Unreliable
		10%	20%	30%		10%	20%	30%
	796	5916	6726	7659	1257	9208	9907	10908

Table 3 :

 3 Network building time for reliable and unreliable wireless links (slots)

Acknowledgment

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


Iaroslav Omelianenko
email: yaric@newground.com.ua

Creation of Autonomous Artificial Intelligent Agents using Novelty Search method of fitness function optimization

Keywords: novelty search, objective-based search, evolutionary computation, artificial intelligence, autonomous agents, neuroevolution of augmented topologies, NEAT, neuroevolution, artificial neural networks, modular AI systems, modular artificial neural networks, reinforcement learning

Search for Novelty is an universal method of biological life evolution through introduction of the random beneficial mutations to the genetic code of the organism. In this work we describe experiment of applying Novelty Search method of fitness function optimization combined with Neuro-Evolution of Augmenting Topologies (NEAT) algorithm to produce Autonomous Artificial Intelligent Agents capable to solve spatial navigation task in complex maze environment. The AI Agents produced by the neuro-evolution method described by the NEAT algorithm evolve through gradual complexification of their internal neural network by augmenting its topologies.

Finally, we consider how to apply studied optimization methods and evolutionary algorithms to create ensembles of compact modular AI systems trained using vocabulary of terms describing real world settings. And how to control such ensembles by specialized supervisors knowledgeable about the task and the operating environment.

We provide the complete source code for implementing the NEAT algorithm, including Novelty Search and Objective-Based optimization methods, in the GO programming language.

I. INTRODUCTION

For billions of years of evolution, biological intelligent agents have mastered the power to find optimal solutions in deceptive environments that we encounter in our daily interactions with the real world. We can easy navigate themselves through the maze of a big city subways and roadways. But for artificial intelligent systems, this is too difficult to be easily solved using the optimal computing resources. This is especially true for offline autonomous agents that are not backed by super power of cloud servers.

The main problem here is related to the fact that reliable maze navigation requires the development of a solution in an environment having many traps with strong local optima of fitness function. Such traps are represented as cul-de-sacs that are close to the final destination, but that can not be escaped without a step back, away from the ultimate goal (at least temporary). In such environments, objective-based solvers basically can not find optimal solution or any solution at all, because they do not have the necessary internal machinery for committing the leap-of-faith and move backward from the target in order to eventually find a way out.

The objective-based solvers depends on the best attempts of their designers to assess the operating environment and develop a better way to achieve the ultimate goal. But, as it happens in the real world, preliminary assumptions often can not account for all the traps on the way to the goal because of the extreme complexity of the environment settings. And even in simple artificial environments, such as maze navigation, it often happens that objective-based solvers can not find the optimal solution within the adequate execution time and computational resources allocation. But for successful autonomous execution in real world environments, it is critically important to create Intelligent Agents capable of quickly finding a solution with minimal computational load. This paper is organized as follows: In Section II, we provide overview of our assumptions and details of the experiment as well as description of maze solver agent and its seed genome. It is followed by Section III with results of executing the experiment's trials. In Section IV, we compare performance of the optimization methods studied for specific environments using the experimental results obtained. Finally, in Section V we discuss our vision how studied optimization method combined with neuro-evolution can be used to create Autonomous Artificial Intelligent Agents based on ensembles of compact, modular and specialized ANNs that can solve realworld tasks in energy efficient and understandable way.

With this work we provide full implementation of NEAT algorithm and of studied fitness function optimization methods in GO programming language [START_REF] Griesemer | The Go Programming Language Google GO team[END_REF] in form of GitHub repositories: Artificial Intelligent Agents to do spatial navigation in complex maze environment. The main idea behind NS optimization is to rather look for novel outcomes in the search space than the distance to the final objective: the maze exit. The Novelty Search assigns higher fitness values to the Intelligent Agent capable to find the most novel solution among all previous tries. Despite its ignorance to the final objective the NS happens to be extremely effective optimization method capable of breeding AAIA, which crack deceptive real-world tasks even in the realms where traditional objective-based methods have failed completely. The main assumption about what makes this possible, is that in order to reach final goal, AAIA must find several intermediate goals (stepping stones) which in most cases do not resemble the ultimate objective [START_REF] Lehman | Novelty Search and the Problem with Objectives Genetic Programming: Theory and Practice IX (GPTP 2011)[END_REF]. Sometimes Intelligent Agent must step back to avoid deceptive traps. By doing this it will see a decrease in value of objective-based fitness function for a moment but will get a better outcomes in the future. This is one of the fundamental properties of the real-world environment that the exact route to the final objective in most cases can not be predicted in advance, and all intermediate stepping stones should be found by taking the path.

•
The Novelty Search optimization seems like a natural fit for Neuro-evolution family of genetic algorithms [START_REF] Holland | Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology Control and Artificial Intelligence[END_REF] producing elegant custom Artificial Neural Networks (ANNs) [START_REF] Dreyfus | Artificial neural networks, back propagation, and the Kelley-Bryson gradient procedure[END_REF]. In the experiment we combined NS with Neuro-Evolution of Augmenting Topologies [START_REF] Stanley | Evolving Neural Networks Through Augmenting Topologies Evolutionary Computation[END_REF] algorithm which efficiently evolve ANNs through complexification by augmenting its topologies.

A. The Maze Solver Agent Configuration

Autonomous Artificial Intelligent Agent, designed to solve the maze, has ten input sensors that allow collecting information about the environment and two output effectors controlling its movements through the maze (see Figure 1). The final objective of the agent is to go through the maze and find a way out.

The input sensors are: six range finders that indicate the distance to the nearest obstacle (blue arrows) and four pie-slice radar sensors (slices of red circle) that act as a compass towards the goal (maze exit), activating when a line from the goal to the center of the agent falls within the pie-slice. The greenyellow arrow in the center points to the movement direction of the agent.

The agent is also equipped with two effectors producing a forces that respectively turn and propel the robot, i.e. change its linear and angular velocity.

B. Seed Genome Configuration

The configuration of the seed genome of the solver agent can be summarized as follows (see Figure 2):

• ten input (sensor) neurons (blue): six for range finders [RIGHT, FRONT-RIGHT, FRONT, FRONT-LEFT, LEFT, BACK] plus four for slice radar sensors with 45 degree FOV [FRONT, LEFT, BACK, RIGHT]

• two output (effectors) neurons (red): angular (neuron #13) and linear (neuron #14) velocity controlling effectors

• one hidden neuron (#12) to introduce non linearity (green)

• one bias neuron (#1) to avoid zero saturation when input neurons is not activated (dandelion)

The input neurons has following numbers on the seed genome schema (2):

C. The Novelty Search metric definition for a maze environment

The Novelty Search optimization method is based on novelty metric calculation for each solver agent after performing a certain number of time steps in simulation of maze navigation for that agent. The novelty metric biases the search in a fundamentally different way than the objective-based fitness function (which depends only on the distance from the agent to the exit) and determines the behavior-space through which the search will be performed. Therefore, since what is important in the maze, this is where the solving agent ends navigation, then for the maze domain, the behavior of a navigator is defined as its final position. The novelty metric then maximizes the N-nearest neighbor distance [START_REF] Knuth | Fundamental Algorithms Third Edition[END_REF] between the final positions of all known solving agents, i.e. the most distant agent will have the greatest score of the novelty metric.

The effect of this novelty metric is to reward the solver agent for ending in a place where none have ended before and the method of traversal is ignored. This measure reflects that what is important, is to reach a certain location (i.e. the goal) rather than the method of locomotion. Thus, although the novelty metric has no knowledge of the ultimate goal, a solution that reaches the goal can appear novel. In addition, the comparison between fitness-based and novelty-based search is fair because both scores are calculated only based on the distance of the final position of the agent from other points.

III. EXPERIMENT RESULTS

As for deceptive environments we choose two types of maze environments with different complexity as was recommended in [START_REF] Lehman | Novelty Search and the Problem with Objectives Genetic Programming: Theory and Practice IX (GPTP 2011)[END_REF]: medium and hard maze. The maze configurations was designed in such a way as to create many cul-desacs with strong local optima, deceiving the objective-based optimization methods.

A. The Medium Complexity Maze Environment

The first experiment to establish baseline performance metric was performed using maze configuration of medium complexity. The Novelty Search optimization was combined with Neuro-Evolution of Augmenting Topologies algorithm which use genetic neuro-evolution process to create a population of organisms capable of solving a maze. We also compared its performance with the objective-based optimization method for the NEAT algorithm, where fitness function optimization was dependent on how close final destination of produced organism is from the exit of the maze.

The final performance metric of each Autonomous Agent created for both optimization methods depends only on how close to the maze exit is the final destination of the solver after 400 stimulation steps. Thus, despite the various methods of fitness function optimization, the final results can be compared for both methods. Each experimental trial was performed with 2 000 epochs of evolution or until a winner is found.

1) Novelty Search optimization: Applying Novelty Search based optimization it was possible to get the winner in 10 form 10 trials with optimal genome found approximately within 50 generations. An Artificial Neural Network produced by an organism with a near optimal genome has 16 neurons with only three hidden units, i.e. it was capable of growing two additional units compared to the above-mentioned seed genome (see Figure 2). And it is able to control maze solver agent with a spatial error of about 1.9% for targeting the exit of the maze.

Among with the two additional hidden units (neurons), Fig. 4: The color coded final positions of NS maze solvers for medium maze environment Fig. 5: The medium maze winners genome when objectivebased fitness function optimization method is applied the recurrent link was developed at the output neuron #13 (angular velocity effector) -see Figure 3. The recurrent link at this output neuron appears to be of great importance, since it was introduced in each configuration of the winner's genome generated in each test trial. Such a consistent pattern seems pretty reasonable for the neuron #13, because it affects the agent's steering and requires learning more complicated behavior compared to the neuron #14 (linear velocity control).

It is also interesting to consider the hidden neuron #91, which seemingly have learned the complex behavior of the steering to the exit of the maze when it is discovered to the right or behind the agent. Weve made such assumptions because of its connections with input sensors #2, #7 (range finders: RIGHT, BACK) and #10, #11 (radar sensors: BACK, RIGHT).

The hidden neuron #293 connected with input sensor #11 (radar sensor: RIGHT), has learned to influence the steering of the agent in the direction of the exit of the maze, since most of the time the exit is on the right bottom relative to the agent. The hidden neuron #12 which is introduced in seed genome (2) operates as main control-and-relay switch relaying signals from sensors and other hidden neurons to the effectors (neurons #13, #14).

On the Figure 4 presented a diagram of the maze solving simulation by solver agents controlled by ANNs, derived from the genomes of all organisms introduced into the population until a winner is found. Agents are coded by color depending on which species the source organism belongs to. The fitness of agent is measured as the relative distance between its final destination and maze exit after running simulation for certain number of time steps (400 in our setup).

The initial agent position is at the top-left corner marked with green circle and maze exit at the bottom-right marked with red circle.

The upper plot shows the final destinations of the most fit agents (f itness >= 0.8), and the lower plot -the rest. The results are presented for an experimental trial producing the configuration of the winner genome depicted at Figure 3. The total number of species created at that trial is 32, with only 8 becoming the most fit ones (f itness >= 0.8).

2) Objective-Based optimization: Applying objectivebased optimization, it was possible to create the winners capable of solving medium maze configuration in 9 from 10 trials. But the configuration of the winner's genome in most cases was not so elegant and energy efficient, as with abovementioned Novelty Search optimization.

After 248 generations, it was found near optimal configuration of the winner's genome (see Figure 5), capable of guiding the maze solving agent through the medium-complexity maze and reach the exit of the maze with spatial error about 1.8%. The artificial neural network produced by this genome has 22 units (neurons) with nine hidden neurons for modeling complex learned behavior.

Comparing the objective-based simulation plot ( 6) with the similar for simulation based on Novelty Search optimization, it can be seen that agents final destinations are distributed less evenly through the maze space. Another interesting point is that most fit agents were less exploratory, moving mainly along the maze walls towards the local fitness optima. This behavior resulted in more generations needed to produce the winner on average, as well as completely failed trials.

B. The Hard Complexity Maze Environment

The hard maze configuration introduces additional complexity, emphasizing the idiosyncrasies of the objective-based optimization method. This requires a bit of strategic thinking, which sometimes allows the agent to deviate from the seemingly optimal places (with high local fitness function values) to finally find the guiding path through the maze. The ability Fig. 6: The color coded final positions of objective-based maze solvers for medium maze environment Fig. 7: The hard maze winner genome when Novelty Search optimization method applied of Novelty Search optimization to mimic mentioned strategic reasoning due to its inherent ability to find all the promising areas of the search space has made it an absolute champion with this experiment.

1) Novelty Search optimization:

The Novelty Search optimization method, produced solving agents capable to solve the hard maze in 10 from 10 trials. The power of NS method led to the finding of winning solvers within up to 100 generations in the maze environment of both: medium and hard complexity. Which marks NS as a highly effective optimization method for creating Autonomous Artificial Intelligent Agents capable of complex spatial navigation.

After 109 generations of populations of organisms, the near optimal configuration of the winner's genome was found (see Figure 7). The winner is able to guide the agent through the hard maze environment and approach the exit with a spatial error 2.5%. The Artificial Neural Network produced by this genome has only 17 units (neurons) with four hidden neurons for modeling complex learned behavior.

It is interesting to note that recurrent link on the output neuron #13 (angular velocity effector) was routed through two hidden neurons compared with the medium maze, where the neuron #13 was simply linked to itself. This may result in more complex behavior learned, especially taking into account that link passes through the neuron #42, affected by the range finder: LEFT and the radar: BACK. The neuron #42 is also affected by connection to the neuron #643 (affected by the range finder: LEFT). As a result, we can assume that it learned how to steer the agent when the exit of the maze is behind, and the wall is on the left, i.e. follow the left wall, moving forward.

Another important point to consider is about possible learned behavior encoded in the hidden neuron #297, which is affected by input range finder sensors detecting distance to obstacles in the RIGHT and FRONT direction. Considering the maze configuration, we can assume that this neuron learned to avoid the left chamber's trap, where an extremely strong local maximum of the fitness function was introduced (based on the distance to the exit of the maze).

Because of the inherent complexity of the hard maze environment, only one species from 35 was able to beget genome with fitness greater than 0.8. This genome is also the winner able to produce control ANN successfully guiding solver agent to the exit of the maze. But, as can be seen from the Figure 8, there is a high probability that as the number of simulation steps increases, a larger number of species will be able to hit the fitness threshold (0.8).

2) Objective-Based optimization: The objective-based fitness function optimization method completely failed to create any successful solver agent within all 10 experiment trials. In some trials, it was able to create AAIAs, almost finding the exit of the maze, but it seems that many more simulation steps are required to eventually produce the winner genome, which makes it too computationally expensive.

The Figure 9

IV. DISCUSSION

As shown by our experimental data, the Novelty Search method of fitness function optimization, when the fitness of the agent is based on the novelty of the solution that it was able to find, significantly outperforms traditional objective-based optimization and was even able to solve the navigation task when the traditional method failed completely. We believe that Novelty Search optimization can be successfully applied to create optimal solving agents in many areas where strong deceptive local optima of fitness function prevents traditional objective-based methods from finding optimal or any solutions at all.

Our NEAT algorithm implementation in the GO language is also shared through NEAT software catalog, hosted by Evolutionary Complexity (EPlex) Research Group at the University of Central Florida: http://eplex.cs.ucf.edu/neat software/ Special thanks to Dr. Kenneth O. Stanley for advises and sharing the NEAT algorithm details.

V. FUTURE WORK

We consider the development of modular AI systems based on ensembles of highly optimized compact Neural Networks. Our goal is to create compact utility NN blocks that are trained to represent vocabulary of the real-world terms that can be combined to form complex knowledge and skill sets. The mentioned NN blocks will be created using neuro-evolutionary algorithms by the method of gradual complexification, creating small and energy-efficient NN topologies that can be executed on a commodity CPUs with minimal power consumption. We call these blocks as Term Artificial Neural Network (tANN) to emphasize the fact that each NN block represents a specific term in our custom real-world vocabulary.

In addition, in order to model a more complex behavior, the Supervisor ANN (sANN) structure will be created to process the output of the tANN units and combine them with a common knowledge of the internal functions of the supervised process or system component.

It is assumed that Autonomous Artificial Intelligent system will be represented in the form of a complex hierarchy of tANN and sANN blocks in combination. Where each block or hierarchy of blocks will be responsible for a particular function, knowledge unit or set of the system skills. Such a modular / hierarchical approach provides a simple means to increase system capacity by introducing additional blocks with specific training. It is also possible to obtain an understanding of the flow of AI system reasoning, following the activations of its constituent blocks. The knowledge transfer also becomes easier by simply taking a NN block trained for a specific vocabulary term and introducing it into the new system.

A. Our roadmap for future research 1) Creating definitions of the basic vocabulary terms 2) Creation of configurations of the seed genomes for each specific term of the vocabulary 3) Training / breeding of tANN structures from the vocabulary 4) Experiments on training / breeding of sANNstructures, capable of solving specific complex problems 5) Comparison of the performance of AI agents obtained using the described modular architecture against AI

  the NEAT algorithm with Reinforcement Learning experiments: https://github.com/yaricom/goNEAT • the Novelty Search and Objective-Based methods of fitness function optimization along with maze experimental environment: https://github.com/yaricom/ goNEAT NS II. EXPERIMENT OVERVIEW In the experiment we studied how Novelty Search (NS) [3] method of fitness function optimization performs compared to traditional objective-based ones for unsupervised training of

Fig. 1 :

 1 Fig. 1: The schema of maze agent with input sensors plot

Fig. 2 :

 2 Fig. 2: The seed genome schema

  Fig. 8: The color coded final positions of NS maze solvers for hard maze environment

Fig. 9 :

 9 Fig. 9: The color coded final positions of most fit objective-based maze solvers for the hard maze environment