Jin Cui
email: jin.cui@insa-lyon.fr

Fabrice Valois
email: fabrice.valois@insa-lyon.fr

Simba: Similar-evolution Based Aggregation in Wireless Sensor Networks

Keywords: Data aggregation, temporal-spatial correlation, similar evolution, wireless sensor networks

Data aggregation is an important mechanism to reduce energy consumption in Wireless Sensor Networks (WSNs). By investigating spatial and/or temporal correlation of raw data, sensor nodes can aggregate raw data to a meaningful digest instead of directly sending raw data to sink, this process is considered as data aggregation. Several aggregation works focus on the raw data, they use raw data to cluster the nodes or to do aggregation. While analysis of datasets of real projects shows that some nodes perform similar evolution. Thus we propose a raw data-independent aggregation, i.e., Similar-evolution Based Aggregation (Simba), to consider the evolution of data rather than the raw data. Simba creates a group out of isolated nodes, nodes in the group can cooperatively execute data aggregation, this process reduces the energy consumption on each node. Besides, similar evolution of nodes guarantees the recover accuracy. Our experiments demonstrate that Simba can save more than 91% energy comparing no aggregation, and save more 30% energy than original aggregation functions, and Simba can recover data with higher fidelity comparing with the works relying on raw data.

I. INTRODUCTION

As a wireless networking solution, wireless sensor networks (WSNs) suffer from problems like network congestion, packet loss. Moreover, sensor nodes have intrinsic limitations, e.g., low computation and energy constraint. All of these problems are challenging the WSNs techniques. To solve these problems, data aggregation has been proposed. Data aggregation is a data gathering strategy with the idea of using data correlation to reduce the amount of data. In general, spatial and/or temporal correlation may exist in the data of WSNs. Spatial correlation occurs in data collected by neighbouring nodes; and data collected by a node at different time instants may lead to temporal correlation. The correlations can help sensor nodes to aggregate raw data as a digest, and nodes only send this digest to sink.

Due to the spatial and/or temporal correlation, most dedicated aggregation works highlight the role of raw data, such as [START_REF] Solis | Isolines: efficient spatio-temporal data aggregation in sensor networks[END_REF], [START_REF] Li | A novel characteristic correlation approach for aggregating data in wireless sensor networks[END_REF]. These works point out that the nodes holding same or close data (close here is defined by a threshold) can be clustered together to reduce traffic, and can achieve the goal of aggregation. These works reveal importance of raw data and the correlation, but we know sensor nodes are error-prone that may lead to raw data have errors and perform dynamically.

We find two properties from real datasets: 1) even if the environment is quite similar, the raw data are not necessarily close; 2) although nodes do not have similar raw data, but some nodes have similar evolution. From the first property, we know that the works involving raw data need to pay more attention on choosing appropriate threshold, and they need to conquer the dynamic change of raw data. The second property reveals an interesting phenomena, neighbouring nodes often show the similar evolution even though the raw data are not totally same. The evolution has spatial-temporal features, spatial feature is shown from the location of the node, and temporal feature is shown from the sequence of data.

Therefore, we propose a raw data-independent solution: Similar-evolution Based Aggregation (Simba). Simba takes benefits from groups, and the groups are built by similarity of evolution. In a network, Simba introduces two phases: set-up phase and aggregation phase. Set-up phase is group forming phase, all the nodes use a vector ( Rc) to demonstrate evolution, and then by communicating with neighbours, nodes holding similar evolution form a group. A group leader GL will be selected to represent the group. Aggregation phase is aggregation function executing phase, when data of GL are recovered by sink, the data of other nodes in the same group can be easily computed. We provide aggregation functions, A-ARMA [START_REF] Lu | Optimized data aggregation in wsns using adaptive arma[END_REF], polynomial aggregation [START_REF] Ozdemir | Prda: polynomial regression-based privacy-preserving data aggregation for wireless sensor networks[END_REF] and average, to test the performance with and without Simba. The simulation results from Matlab and WSNet [START_REF]WSNet simulator[END_REF] show that, Simba can save more 30% energy than original functions, and save more than 91% energy comparing with no aggregation. In the meanwhile, sink can recover data with high fidelity according to RMS computation.

The main contributions of our work are listed as:

• We investigate the real datasets, and analyse two key properties: 1) even if the environment is quite similar, the raw data are not necessarily close; 2), although nodes do not have similar raw data, but some nodes have similar evolution.

• We propose Similar-evolution Based aggregation.

Simba groups several nodes together by similar evolution, and nodes execute aggregation functions by the unit of group. The experiments show that Simba reduces energy consumption and guarantees the recover accuracy in the meanwhile.

The rest of paper is organized as follow. Prior data aggregation techniques are reviewed in Section II. We discuss our analysing, and present how to model evolution in Section III. We propose similar evolution-based aggregation protocol in Section IV and evaluate the performance in Section V. Finally, we conclude our work in Section VI.

II. RELATED WORKS

To the best of our knowledge, there is few works concerned on data evolution, many works pay attention on value of raw data. In [START_REF] Solis | Isolines: efficient spatio-temporal data aggregation in sensor networks[END_REF], the authors propose to draw a map for sensors, and the isoline is defined by difference between raw data. It means nodes in same isoline share same raw data (under some threshold), only when an isoline changes, corresponding nodes need to update new data. [START_REF] Li | A novel characteristic correlation approach for aggregating data in wireless sensor networks[END_REF] propose characteristic correlation to group nodes with same raw data, they highlight that same or similar raw data can provide characteristic correlation between nodes, and which is more precise than spatial distance of nodes. In addition, they provide a "categorizing range" to define the error of similar raw data, smaller range is, similar raw data are. When sink receive the representative of virtual cluster, it retrieves the value as all the cluster members readings. They only focus on raw data, not the evolution of data series, which leads to frequently change cluster or group when threshold is too sensitive or raw data fluctuate.

We also review the aggregation functions we considered. Average is a traditional aggregation function, sensor nodes send average value to sink replacing several raw data. A-ARMA is proposed in [START_REF] Lu | Optimized data aggregation in wsns using adaptive arma[END_REF], which provide to use ARMA model to forecast the data. An ARMA model can be formulated as:

F arma ≡ xτ =ϕ 0 + ϕ 1 x τ -1 + • • • + ϕ p x τ -p + ϑ 1 ε τ -1 + • • • + ϑ q ε τ -q (1)
where xτ is predicted value, {x τ -p , • • • , x τ -1 } are time series, ε is error term, and ϕ, ϑ are model coefficients. A node builds ARMA model (as Eq. 1), and the coefficients (ϕ, ϑ) are sent to the sink instead of raw data. After collecting next S data, the node detects the RMS error between predicted data xτ and the raw data. If the difference is lower than th err , the node continues using its current ARMA model. Otherwise, the node computes the new coefficients on the latest samples.

Polynomial aggregation [START_REF] Ozdemir | Prda: polynomial regression-based privacy-preserving data aggregation for wireless sensor networks[END_REF] holds similar idea with A-ARMA, while sensor nodes compute the polynomial coefficients as:

F poly ≡ ẋi = a 0 + a 1 i + • • • + a m i m ( 2
)
where ẋi is recovered data, and a 0 , • • • , a m are coefficients of polynomial. Sensor nodes update m coefficients to sink replacing raw data to reduce the traffic. Sink recovers data from Eq. 2. All the above functions are belongs to forecasting aggregation functions [START_REF] Cui | Data aggregation in wireless sensor networks: Compressing or forecasting?[END_REF].

III. EVOLUTION ANALYSIS

In this section we describe our observations of similar evolution from real datasets first, and secondly show how sensor nodes model the evolution.

A. Observations from real datasets

We analyse several datasets to observe the evolution, here we present the two datasets we tested. First dataset is from Tropical Atmosphere Ocean (TAO) Project [START_REF] Project | Temperature data[END_REF] (denoted as T AO). The project focuses on monitoring the real-time ocean surface (The Pacific) temperature for understanding and prediction of EIN i no and LaN i na. Plotting the data from April 1993 to December 1995 per month, showed in Fig. 1(a), we observe that the nearby sensors generally express similar evolution, whereas the data are not the same (note that all the sensors are deployed in North Latitude 0 0 ). The temperature from the nearby location have the similar evolution with some fluctuation along time. Second dataset is from a custom project, which is temperature monitoring in a House (denoted as T MH). The monitoring begins from January 2012 to July 2012, and nodes report every 10 minutes (about 26130 readings for every node). After 7903 samples, node 1 and node 6 suffer physical errors (no data reporting for a while), thus to data alignment, we use the first 7900 data to constitute T MH, shown in Fig. 1(b).

B. Capture the evolution

From the above observations, we know that raw data often express similar evolution despite the data is not so close. Thus, how to capture the evolution is the present problem. Linear regression investigation [START_REF] Montgomery | Introduction to linear regression analysis[END_REF] indicates that straight lines can be used to approximate time series, and the straight lines can be seen as evolution in our case. We know raw data of WSN can be seen as a set of (y, τ ), in which y is the data reading and τ is corresponding data sequence. For example, temperature reading (27.6, 10) denotes that the 10 th temperature value is 27.6 o C. Thus, linear regression in WSNs can be simply expressed as: y = Rc • τ + β, where Rc is the regression coefficient, and β is the incept. In our case, we use the Rc to describe the evolution.

Considering the computation constrain of sensor node, we use piecewise linear regression, i.e., each 5 data as a segment (S ι =5) to calculate Rc. Under one segment, regression coefficient Rc can be calculated as:

vector Rc = [• • • , Rc Seg-1 , Rc Seg ].
In our experiment, we set Rc = 4.

Fig. 2 verifies the piecewise liner regression result for given sensor nodes (N3 and N13 of dataset T MH).

We can see that the approximating line during one segment S ι can fit the raw data well. Thus, in our context, evolution of sensor node is approximated by the regression coefficient.

C. Measuring the similarity of evolutions

We use cosine similarity as a metric [START_REF] Van Dongen | Metric distances derived from cosine similarity and pearson and spearman correlations[END_REF] to evaluate similarity. Cosine similarity is a measurement of similarity between two vectors, used to measure the angle between them. When two vectors are the same, the cosine similarity is 1; when the angle between two vectors is increasing, the cosine similarity is decreasing. Cosine similarity provide us a positive value ((0, 1]) to show the similarity. When the value is closer to 1, it means the nodes are in a more similar environment. The cosine similarity function between two vectors Rc i and Rc j is defined as:

Cs( Rc i , Rc j ) = Rc i • Rc jT ( Rc i • Rc iT )( Rc j • Rc jT ) (4)
where Rc T states the transpose vector of Rc, and Cs denotes cosine similarity. Note here, Cs function meets commutative law, i.e., Cs( Rc

i , Rc j ) = Cs( Rc j , Rc i ).
Therefore, to identify the similarity between the evolution, we provide following definition: Definition 1: We define the similarity function between two Rc as:

sim( Rc i , Rc j ) = 1 if Cs( Rc i , Rc j ) ≥ th cs , 0 otherwise. ( 5
)
where th cs is a threshold determined by the application, which means if the cosine similarity of two Rc meets threshold, they are considered as similar. Since Rc represents the evolution of raw data, thus two nodes are similar if and only if their sim function is equal to 1. Note here, we define th cs > 0.5, which can avoid two orthogonal vectors grouping together.

i , Rc j ) = 1 & sim( Rc i , Rc k ) = 1 ⇒ sim( Rc j , Rc k ) = 1, ∀j, k (6)
This theorem is easily to be proved, due to the page limitation, we omit the proof process.

IV. SIMBA: SIMILAR-EVOLUTION BASED AGGREGATION Fig. 3 demonstrates the two phases of Simba. Set-up phase (Fig. 3(b)) focuses on group forming, nodes group together due to similar evolution. Aggregation phase (Fig. 3(c)) focuses on executing data aggregation, group leader represents the group to update aggregated packet.

A. Set-up phase

During set-up phase, each node calculates its Rc Seg by Eq.3, and broadcasts it to neighbours (assuming the network is already connected). Node maintains a table to store the recent coming Rc Seg and computes the similarity. When the similarity is higher than a threshold, marked as th cs , the two nodes are considered having similar evolution.

As shown in Fig. 4, we take node A as an example to show the set-up phase. Supposing node A is adjacent with node B, C and D, after broadcasting Rc, every node checks the table and calculates similarity. Table I shows an example of node A, where the column N br_ID is the neighbour ID, Rc is used to store Rc, Cs and Sim are the values of Eq.4 and Eq.5 respectively.

=[• • • ,Rc B Seg-2 , Rc B Seg-1 , Rc B Seg ] Cs( Rc A , Rc B ) 1 C Rc C =[• • • ,Rc C Seg-2 , Rc C Seg-1 , Rc C Seg ] Cs( Rc A , Rc C ) 0 D Rc D =[• • • ,Rc D Seg-2 , Rc D Seg-1) , Rc D Seg ] Cs( Rc A , Rc D ) 1 Table I. THE NEIGHBOUR TABLE OF NODE A.
are similar, even though they are not 1-hop neighbours. So node A multicasts to sink and node B,D that group {A,B,D} ({} notes the unit of one group) with timer T x . Note that T is a timer, and x is the number of similar neighbours (i.e. Sim = 1 as defined by Eq. 5). Thus, a node having more similar neighbours will send notification more quickly than others. When a node receives the group notification from its neighbours, it marks its own transmission redundant, and then it cancels notification. This timer can avoid collision and redundancy, while note that irrespective of the strategy that a node follows, the result of the group remains unaffected. When a node has no similar neighbours, it does not have notification to sink. For sink side, if none of notification messages involves a node, it means this node forms a group with itself, it does not belong to any other groups.

B. Aggregation phase

In the aggregation phase of Simba, the group members share the aggregated information. It means the nodes having similar evolutions use the same coefficient to aggregate data. For example, node A and node B are in the same group, and we consider aggregation function is A-ARMA. Thus the model coefficient (ϕ and ϑ in Eq. 1) of A-ARMA computed by node A are also used to predict node B's data. In each group, only leader (GL) processes and transmits aggregated packet. With the group information in set-up phase, sink can recover GL's data using aggregation function, and the data of other nodes can be retrieved easily.

1) Aggregating progress: At the beginning of aggregation phase, sink sends group result to one node of each group, and it select one node as the first group leader. In addtion, GL adds a field in its neighbour table to store the nodes in the same group. For example, node A receives the group from sink, it adds a list as A-B-D to assign the next leader, i.e., the next GL is node B, and node B will also store the list.

Briefly, aggregation progress is: node uses aggregation function to predicted data (or recovered data from sink view), when new raw data arrives, node compares the predicted data and raw data, if the error is beyond predefined threshold th err , node transmits aggregated packet to sink; otherwise, node waits for new data to compare, and repeats the process. In Simba, every leader will process data as normal aggregation process. While when the current leader (e.g. node A) finds the accuracy exceeds th err , it sends new aggregated packet to sink and the next leader (e.g. node B). The new GL (node B) will use this aggregated packet to predict data and compare with new raw data, and then repeats the process as last leader (node A). In this scheme, there is no effect from the size of group, all members of group are passively to wait for the instruction to execute aggregation function. From the list field in aggregated packet, group member becomes group leader in turn.

2) Recovering progress: For a group leader A, sink recover its data directly from the aggregation functions as (see Sec. II):

y A = F(y A ) ( 7
)
where F denotes the aggregation function, y A states the recover data of node A, and y A is the raw data of node A.

For A-ARMA and polynomial aggregation, sink recovers data from Eq. 1 and Eq. 2 respectively. For Average, sink uses y as the average value for recover data. Suppose that node B is in the group of node A, and the difference between node A and node B is:

D AB = y A -y B ( 8
)
where D AB marks the difference. Since the raw data maintain similar evolution, thus sink can simply recover data of node B. The data of node B can be recovered as:

y B = y A -D AB (9)
Therefore, from the Eq.7, Eq.8 and Eq.9, sink can recover all data for a group. Group leader is responsible for transmitting the aggregated packet to sink and next leader, and due to similar evolution, the group member can share the same aggregated packet. Similar evolution helps sink recover all nodes data and guarantees the recover accuracy. Moreover, the cooperation between nodes in the same group substantially reduces the group transmission as well as energy consumption.

V. PERFORMANCE EVALUATION

Based on the two datasets, we simulate the set-up phase using WSNet [START_REF]WSNet simulator[END_REF], an event-driven simulator for wireless networks, to show the group results. We simulate the aggregation phase using Matlab considering the T MH dataset. Note here, the network is connected before Simba, and we use GPSR [START_REF] Ye | Gradient broadcast: A robust data delivery protocol for large scale sensor networks[END_REF] for data set T MH, the node deployment and topology are shown in Fig. 5. For T AO, all the nodes can be seen in a chain topology corresponding there location, and each node can connect with its 1-hop neighbours. A. Selection of similarity threshold th cs Similarity threshold th cs is defined to check the similarity between different nodes, the higher th cs is, more similar the evolution of values is. On one hand, a higher th cs is desirable to maximize the similarity between nodes to keep accuracy. On the other, if it is too high, no nodes can be grouped together, there is no means for aggregation. Thus, choosing an appropriate th cs is necessary for Simba.

We use A-ARMA(2,2) with Simba to investigate number of group and recover accuracy considering dataset T MH. In Fig. 6, we plot with y-axes on both two sides, where the left one corresponds to recovery error and the right one corresponds to group number. When similar threshold th cs = 1, the group number is 10, it means every node forms a isolated group. Correspondingly, recover accuracy is highest (RMS≤ 0.15) because every node only executes aggregation function by its own data. As decrease of th cs , more nodes meet th cs , they group together to execute A-ARMA(2,2), the accuracy is decreasing. When th cs = 0.75, we have only 3 group in the network, while the accuracy is lowest. Thus, considering energy saving and accuracy, we chose 0.8 as the similarity threshold for dataset T MH. Similarity threshold for dataset T AO can be calculated using the same method, which is 0.85. Normally, for dataset from in-door temperature readings, th cs can be setting around 0.8, which can keep the accuracy of recovery data and group size.

B. Accuracy and Energy issues

A good aggregation scheme should keep high recover accuracy and save more energy. In this section, we investigate the accuracy and energy issues of Simba. First, we analyse the recover accuracy of A-ARMA, polynomial aggregation and average with and without Simba within dataset T M H.

In Fig. 7, we show the detail recover accuracy of each node of 3 original aggregation functions, and comparing with situation of Simba. If node has no group, every node works on the original functions, there is no change for recover accuracy, such as N 13, N 14 and N 5. For the nodes grouped together, we can see that Simba indeed introduces some error but not so obviously. This is because only GL operates aggregation function on its own data, the others data are recovered based on similar evolution. Besides, there is an error threshold th err makes nodes to respect accuracy. Thus, the margin between original functions and Simba is not so big. For example, the average RMS error of 10 nodes for A-ARMA(2,2) is 0.1437, and error for A-ARMA(2,2) with Simba is 0.1758. That is to say, with Simba, nodes respect the accuracy in a group, which can guarantee the final fidelity.

In terms of energy, we detail the energy consumption for one node firstly, and then demonstrate the energy consumption of the whole network. Takes N3 as an example, which is one member of the group {N3,N6,N11}. Assuming energy consumption of transmitting an aggregated packet is 1, and the energy for reception is 1. As samples arrives, we compare transmission energy of aggregation functions with and without Simba. Calculating transmission energy begins from aggregation phase (removing the 100 samples for Set-up duration). Fig. 8(a) plots the energy consumption of N3 from data sequence 100 to 200, we can see that whatever the aggregation function is, with Simba, the energy consumption decreases. This is because Simba moves the energy consumption from a node to a group. N3 belongs a group {N3,N6,N11}, and the group is represented by leader. When N3 is current GL, it needs to transmit aggregated packet; when N3 is not the current GL, it keeps silence to save energy. Thus with Simba, the group member can save more energy than they originally do. More specifically, Fig. 8(b) demonstrates the total energy consumption for the whole network (each node generates 7800 packets) in situation of no aggregation, without Simba and with Simba. We can see that the whole energy consumption is reduced by the situation with Simba (scale in Log). Whatever the functions are, Simba helps them to save energy, and at least saves 30% more than the original functions do. For A-ARMA(2,2), Simba achieves a 41% reduction on energy consumption. Comparing with the situation of no aggregation, Simba can save energy around 94%, 91% and 95% for 3 aggregation function respectively.

C. Comparative analysis

To the best of our knowledge, few aggregation works focus on data evolution, similar works all pay attention on raw data. We select the work using raw data to cluster nodes as the stateof-the-art benchmark for Simba, characteristic correlation [START_REF] Li | A novel characteristic correlation approach for aggregating data in wireless sensor networks[END_REF]. To compare with Simba, we simulate [START_REF] Li | A novel characteristic correlation approach for aggregating data in wireless sensor networks[END_REF] in Matlab with dataset T MH, and nodes are deployed as the hierarchy in Fig. 5(b). We use 0.5 0 C and 1 0 C as "categorizing range" respectively. Actually, this "categorizing range" is error threshold th err in Simba, thus we also set th err = 0.5 0 C to compare with characteristic correlation. The first 100 raw data of dataset are used to make cluster stable (which is also proposed in [START_REF] Li | A novel characteristic correlation approach for aggregating data in wireless sensor networks[END_REF], with enough raw data, the cluster keeps stable and then node is able to do aggregation). Average is used as aggregation function in Simba and characteristic correlation. We calculate RMS error (between recovery value and real value) for every 10 data, to show the error from two aggregation methods. Fig. 9 demonstrates the RMS error per 10 data for characteristic correlation and Simba, we can see Simba performs lower RMS error than characteristic correlation. Moreover, with different "categorizing range" (0.5 0 C and 1 0 C), characteristic correlation shows very dynamic RMS error. This is because characteristic correlation relies on raw data, this method groups the nodes holding similar raw data, but raw data often show dynamic properties. For Simba, it uses evolution to group nodes together, the evolution is more stable than raw data. Besides, in characteristic correlation, sink retrieves the average values as all cluster members data, it does not consider the difference between nodes. While for Simba, sink uses the mean difference to recover data, this can guarantee the accuracy further.

VI. CONCLUSION

We propose Similar-evolution Based Aggregation, a raw data-independent aggregation, to take benefits taken from similar evolution in this paper. Our simba works as: nodes use linear regression to catch the evolution and group with the similar neighbours together. The nodes in one group alternatively send the aggregated packets to sink. Each node uses a few packets to transmit, and sink can recover the whole data for a group due to similar evolution. We can see, similar evolution give nodes the opportunity of cooperating with each other when executing aggregation function. The experiments results show that Simba use less aggregated packets to get high fidelity recover value, and Simba can save at least 30% more energy than original aggregation functions do. Comparing with situation of no aggregation, Simba can save energy more than 91%. In the future, we will extent our protocol within more dynamic situation, e.g., dynamic evolution and topology change.

  Dataset T MH.

Figure 1 .

 1 Figure 1. Dataset T AO and T MH, the observations of similar evolution behaviour.

  N13 Linear regression for N13(a) Raw data 1 -100 from N.13 and the linear regression result.

  N3 Linear regression for N3 (b) Raw data 1-100 from N.3 and the linear regression result.

Figure 2 .

 2 Figure 2. 20-segment linear regression, using data of N3 and N13 from dataset T MH, segment length Sι is 5.

Figure 3 .

 3 Figure 3. The two phase in Simba, set-up phase is the processing of group forming, GL executes aggregation functions in aggregation phase.

Figure 4 .

 4 Figure 4. An example in set-up phase. The link labels correspond to the value of sim function.

  The nodes deployment.

  The schematic routing for T MH.

Figure 5 .

 5 Figure 5. The nodes topology of dataset T MH.

Figure 6 .

 6 Figure 6. The influence of threshold of similarity thcs on recover accuracy and group result, based on dataset T MH (error threshold therr = 0.03).

Figure 7 .

 7 Figure 7. The recover accuracy with and without Simba (nodes ID in {} in x-axis are group members). Here, error threshold therr = 0.03.

  n s m i s s i o n E n e r g y o f N 3S a m p l e sA v e r a g e A v e r a g e w i t h S i m b a A -A R M A ( 2 , 2 ) A -A R M A ( 2 , 2 ) w i t h S i m b a P o l y n o m i a l a g g r e g a t i o n P o l y n o m i a l a g g r e g a t i o n w i t h S i m b a (a) Energy consumption for N3 (calculating every 10 data).A -A R M A ( 2 , 2 )A v e r a g e P o l y n o m i a l a g g r e g a t i r g y c o n s u m p t i o n ( i n L o g 1 0 )A g g r e g a t i o n f u n c t i o n s N o a g g r e g a t i o n W i t h o u t S i m b a W i t h S i m b a (b) Total energy comparison in different aggregation functions (Log scale).

Figure 8 .

 8 Figure 8. Energy comparison from one node to the whole network.

Figure 9 .

 9 Figure 9. Comparison analysis between characteristic correlation and Simba, considering error threshold as 0.5 0 C and 1 0 C.

Rc Seg = Sι i=1 (τ i -τ )(y i -ȳ) Sι i=1 (τ i -τ ) 2(3) where τ = 1 Sι Sι i=1 τ i , ȳ = 1 Sι Sι i=1 y i , S eg denotes the current segment. With more segments, node generates a coefficient

ACKNOWLEDGEMENT

We would like to thank Tropical Atmosphere Ocean (TAO) project for its dataset. This work was particularly supported in part by the INSA Lyon BQR ARBRE project.


Valentin Gavan
email: valentin.gavan@engie.com2anna.perehinec@engie.com

Anna Perehinec

Sergeï Agapoff
email: sergei.agapoff@cstb.fr2stephanie.derouineau@cstb.fr

Stéphanie

Stéphanie Derouineau

Rule based Fault Detection & Diagnosis

Keywords: fault detection, expert rules, performance gap, threshold, actual value

Introduction

By improving the energy efficiency of buildings, European total energy consumption could be reduced by 6% and CO2 emissions by 5%. Although efforts have been made at the national level to improve building performance, significant discrepancies remain between the targets defined at the design stage and the actual performance both in terms of energy efficiency and users' comfort. The PERFORMER FP7 project addresses those issues by developing an innovative integrated concept for monitoring and evaluating building energy performance which will help reduce the gap between predicted and actual performance in a performance guarantee perspective.

FDD (Fault Detection and Diagnosis) is one of the key methods used in the project to achieve its objectives and the technique identified to support the FDD approach is the expert rules-based method. Although FDD is often investigated in research projects and is integrated in many solutions, the expert rules method remains underexploited, though. While the building industry is seeking even smarter and sophisticated solutions to reach a high level of performance, expert rules are more simple and straightforward to implement, and they address very operational matters in Building Managers' daily life.

Many reports and articles deal with FDD and, to a lesser extent, expert rules. The International Energy Agency has published several reports ("Annexes") which highlight the benefits of FDD methodologies and techniques, and in particular, Annexes 25 [START_REF] Iea Ecbcs | Real Time Simulation of HVAC Systems for Building Optimisation, Fault Detection and Diagnostics[END_REF], 31 [START_REF] Iea Ecbcs | Energy -Related Environmental Impact of Buildings[END_REF], 34 [START_REF]Computer Aided Evaluation of HVAC System Performance[END_REF] and 40 [START_REF] Iea Ecbcs | Commissioning Tools for Improved Building Energy Performance[END_REF] that were very valuable to conduct our study. However when we tried to apply the knowledge to practical cases, we pointed out some limits of the literature. Most of time, the expert rules topic is analysed only as a piece of a whole FDD method and is therefore not detailed enough. Moreover, the field of knowledge is often reduced to specific equipment such as HVAC (e.g. IEA's Annex 34), whereas other recurring issues are actually raised by Building Managers and they do not necessarily comes from the systems themselves.

The added-value of our work on expert rules is firstly embedded in the use case we are developing. We have built up a methodology to define the rules that is directly linked to one of the project's pilot sites, the Woopa Office Building (Lyon, France). This building was put into operation in 2011 and is a high-performance building with efficient systems, which is a distinguishing feature. Indeed, most of the existing case studies are often focused on old or low-performance buildings, while our study demonstrated that the same problems and other recurring issues remain in new efficient buildings. Moreover, our approach follows a well-defined process included in a global project, and integrates key stakeholders and valuable experience feedbacks. The purpose of our work is not to deliver further academic features but to rather provide the Building Managers with a consistent method, easy to apply to achieve their performance targets. All this gives meaning to our the study.

Methodology a. The expert rules methodology in Performer

Expert rules were included in a first instance in the PERFORMER energy performance assessment methodology to provide functional requirements and specifications towards the development of the solution and the expert system. The process we chose to implement expert rules follows three main steps : (1) the definition of the expert rules addressing the issues raised by the Building Manager, (2) the development of the algorithms to test the rules on the pilot (off/online), and (3) a set of recommendations to help the decision-makers when they want to use and apply the rules. The approach is a top-down approach targeting the end user needs, i.e. the Building Managers or the Facilities. It has been broken down into several steps (Figure 1) in order to devise a consistent and robust framework.

[ Step 1] We collected all the most recurring and impacting symptoms and faults that were previously listed in the literature and existing case studies.

[ Step 2] We analyzed the faults and selected the ones that were the most impacting in terms of energy consumption and users' comfort which are key primary KPIs defined in PERFORMER. These indicators support the overall process for energy performance monitoring and assessment, and are expected to assess energy performance by comparing expected and actual value of energy performance, and to check that expected energy consumption, CO2 emissions and economic targets are reached, and to manage energy performance by explaining any gap between expected and actual values, and to ensure the continuity of energy performance. We also used secondary KPIs (specific to FDD) to define the thresholds for the application of expert rules in order to detect any performance gap between actual and predicted values :

Lighting

% of time when the lights are "on" when the building is not occupied % of time when the lights are "on" when the building is occupied Lifts Lift energy consumption per month and year Working monthly hours in non-occupancy [Step 3] Other feedback from the other pilot sites helped us to write the expert rules methodology and provide specifications for the expert rules development and application. In order to deliver a practical use case, we worked closely with the Building Manager of the Woopa Office Building to define some rules for specific faults. We finally came up with a set of recommendations presenting a list of specific rules tailored to detect and diagnose the malfunctions raised by the Building Manager.

[

Step 4] The simulation models realised in another module of the project [START_REF] Lefort | Performance Validation of a Positive Energy Building in France using Advanced Data Analytics and Calibrated Simulation[END_REF] should also help to adjust the rules and make them more accurate (this task has not been completed yet and will be used within a verification process once the rules are practically applied to the building.

[ We have already started to test some rules on the data collected from the BMS of the Woopa Office building to check their validity and efficiency. These tests are off-line driven [Step 7] The whole work described above will have to be integrated in the on-line expert module of the Performer tool.

Development of FDD methods

Assesment of FDD methods with simulation

Correct and Adjust the methods

Development of user interface

Implement FDD methods

Adjust FDD methods

Off-line validation with real data

Implement in site Correct and adjust FDD methods

Correct simulations or models

On-Line validation in buildings

Inventory &Analyse of faults to detect with end-users

Select Fault to treat

Implement faults to detect

Adjust methods

Fit interface according to users demands

Implement in BEMS

Test the methods

b. Case study and experience feedback

The method has been applied to the Woopa Office Building [7]. It is located in Lyon (France) and is a NZEB building (BEPOS). The office building covers a 11,000m 2 area over 7 floors. The notions of sustainability and high energy performance were included since the conception of the building until its delivery in 2011. Efforts were made on the thermal and visual comfort (external insulation, triple glazed windows, atrium) and on the integration of high performance systems (active floor system using groundwater only, balanced ventilation with 80% of energy recovery, highly efficient individual lighting systems). The building also produces energy from its renewable energy systems in place: an rapeseed oil cogeneration, 3 biomass condensation boilers, one gas condensation boiler for backup and more than 800m 2 of photovoltaic modules. Its BMS records data every 15 minutes and every 24 hours with an accurate granularity for each usage. It also generates 691 csv files per day and each file contains up to 13,000 data. 312 sensors were initially installed in order to measure the consumptions of the systems per usage : heating, ventilation, comfort & occupancy, lighting, hot water for sanitary use, fan coils, lifts and auxiliary equipment. Although the building is globally highly efficient, several issues regarding its BMS performance were flagged. Among the problems related to the BMS, some sensors are not properly connected and others deliver unreliable data. Some data collected to measure the energy consumption from the solar panels and the micro-cogeneration are so unreliable that the Building Manager has to report them manually. And we finally identified lots of programming errors that impacted the writing and the application of some rules. These issues acted as a brake on our work and one of our conclusions was to focus our future investigation much more on the quality and the reliability of the data than the systems themselves.

The rules off-line tests were conducted within a process around 5 main steps as following: the transfer of data from BMS database to FDD database (Acquisition interface), the removal of irrelevant values in order to filter data (Data filtering), the definition of the building's operating mode (Building's mode definition), the definition of the expert rules to detect any symptom of fault or deviation to an expected behavior, the application of the expert rules on the values transferred to the database (rules application ) and the diagnosis of the malfunctions by listing the potential causes (diagnostic and final step of the process).

The main added-value of our methodology is the way we address the Building Manager's requirements and needs. In this case, the Building Manager is the end user and also a proactive stakeholder in the whole process. Although the Woopa building is highly efficient and is equipped with high quality systems, lots of remaining and recurring issues hold back the improvement of its energy performance. Our methodology aims at delivering a comprehensive methodology and an easy-to-use toolkit to the Building Manager so that he can detect, understand and fix the malfunctions in the building. Beyond the quantitative results, it is also valuable to show how relevant and efficient expert rules can be when conductingfor instance -an Energy Performance Contract study in high energy performance buildings to avoid any further drift, and to come from a corrective to a preventive maintenance.

Method

The proposed application of expert rules consists in the analysis of measured data to detect any equipment malfunction or energy performance drift. A diagnosis process based on relevant indicators is defined to detect faults and drifts as early as possible and to guide the Building Manager through the potential causes and help him make a decision. Several rules can be applied to a given building. The following rules have been identified for the Woopa Office building:

 R1: Checking of heating systems start optimization at start of occupancy (1st hour) over the heating season  R2: Checking of the operative temperature in occupancy over the heating season  R3: Checking of the hourly programming system -3 modes of the heating setpoint temperature over heating season  R4: Checking of the hourly programming ventilation system  R5: Checking of air-treatment filtration system  R6: Checking of photovoltaic production  R7: Checking of cogeneration production  R8: Checking of the cascade of boilers  R9: Checking of the command of pumps with respect to the heating system status  R10: Checking of specific appliances consumption drift In order to illustrate the approach we chose the R2 rule and analysed the measurement of indoor temperatures used to support building energy performance mastering. As presented in step 4 of the application process, the rules have to be described before their application. We defined a set-point temperature variable Tstp(t) of a given time t based on the functional analysis of the building: the set-point temperature varies depending on the outside temperature and the building occupancy. We then defined two thresholds TOH(t) and TUH(t) based on Tstp(t) and tolerances δOH for overheating and δUH for underheating. To implement the rule, Boolean indicators were defined to check the compliance between the theory ("temperature should be between 19°C and 22°C") and the real values ("temperature is 18.5°C"). Equations ( 1) and ( 2) define the indicators IOH and IUH as the truth values of comparison between the actual zonal temperature T(z,t) of a given zone z and a given time t and the corresponding thresholds. A fault occurs when an indicator is True, i.e. the temperature is over the overheating threshold or under the underheating threshold.

IOH(z,t) = { T(z,t) > TOH(t) } (1) IUH(z,t) = { T(z,t) < TUH(t) }

(2)

To simplify the visualisation of indicators, Boolean values are encoded in binary (True=1, False=0) which allows averaging indicators every hour, day or week. The average indicator is then an evaluation of the fault rate. Once the rules have been described, those indicators are used to detect and analyse the faults. We follow a funnel approach from a big picture to a detailed analysis through four main steps:

(1) Global alarm: To notify the building manager on a specific fault, we worked on two global indexes: the overall building fault rate and the number of units, where the weekly fault rate is over 50%. In our case, the temperature level is under the underheating threshold for more than 50% over the occupancy period. (2) Spatial localisation: To understand the coherence of the results we provide a zoning of the building with zonal fault rates. The user can identify entire faulty floors and/or facades indicating a global cause (not enough insulation on the north side…) or isolated faulty zones for a local cause (open window, heater malfunction…). (3) Temporal localisation: When the user identifies a fault, he has to understand how the indicator behaves in time. By selecting a faulty zone, the user can go deeper in the visualisation details and look at the indicator with a more accurate granularity (daily or hourly average). If there are regular faults on the same pattern, then specific causes can be listed: for example temperature fault in the morning can be due to a heating system starting too late. (4) Diagnosis: We finally come up with a list of possible causes to explain the detected fault, and with other detailed visuals depending on the rule we selected.

The user can compare our analysis with the events that occurred in the building to understand the fault and undertake an action plan to mitigate it and/or prevent it.

Results

Over the heating season, temperature can be used as a proxy for the comfort of occupants. The analysis of the temperature levels enables to check whether both the programming and regulation of the heating system are compliant with users' requirements in terms of comfort and, when appropriate, to adapt it to the building environment and people activities. This can provide the Building Manager with an efficient and operational support, based on the analysis of measurement generally available for large office buildings. Here is an example of application for an expert rule based on the analysis of indoor temperatures during occupancy in a heating period. This analysis is split into the identification of overheating (OH) and underheating (UH). To simulate the operational use, expert rules were applied to the BMS weekly data (collected and filtered according to steps 1 and 2 of methodology). The building manager can therefore monitor the performance every week and undertake actions to improve it or fix any faulty piece of equipment. Rule R2 was applied to the Woopa Office building (temperature data recorded every 15 minutes) with tolerances δOH=2°C and δUH=1°C, and indicators IOH and IUH were therefore calculated. In order to make the visualisation easier, we illustrated this step with the underheating indicator IUH over the working week from 25 th February to 1 st Mach 2013. An underheating problem has been tracked for each zone: an example is presented in Figure 2.

Although the graph shows the required information, it does not match operational purposes though, especially when the manager wants to monitor the temperature of every room in a large building. It is therefore important to simplify the process and provide a global overview to give the user a perspective to find the underlying causes of the fault. Based on the calculated indicator IUH we followed the four steps described in the method above.

(1) Global alarm In the Woopa Office building case study, the overall building fault rate is 18% and 10 zones have a fault rate higher than 50%: this results encourages the manager to go deeper into the fault analysis.

(

2) Spatial localisation

We can see the indicator's zonal weekly average for one of the floors (see Figure 3 where temperature in white areas is not monitored). In Figure 3, high (resp. low) fault rates are represented in dark red color (resp. light yellow). We can see that the fault rate is higher in zone "BN_F3_N" (north-west of the lower part of the figure): this means that the set point temperature is hardly met in this zone. The results in the other floors (not presented here) show that other northern zones of the building are working properly: it seems therefore to be an isolated issue. (3) Temporal localisation Figure 4 shows the hourly average of underheating fault indicator during the considered week in the selected faulty zone (BN_F3_N). The fault rate level is represented by a color on the scale on the right hand side, where 1 means that the indicator is "True", i.e there is a fault. The days are on the X-axis while the Y-axis shows the time slots (from 07:00-08:00 to 18:00-19:00). The heating period (beginning before 07:00 and ending at 17:00) is displayed so that the manager knows if the heating is on or off. The underheating fault happens every day during this week: it seems to be a recurrent issue. The low fault rate observed on Thursday and Friday afternoon should motivate the Building Manager to understand what happened at this specific time (more activity, action on the heating system…) and fix the fault observed during the rest of the week.

(

4) Diagnosis

To further analyse the faulty zone, the user is provided with a global overview of the indoor temperatures relating to the outdoor temperatures. This shows whether the low or high indoor temperature levels can be explained by low or high outdoor ones. The chart below gives an overview where the dots are the tuples {Indoor Temperature ; Outdoor Temperature} for the faulty zone: the straight grey line is the set point temperature, the blue (resp. red) area shows the default area for underheating (resp. overheating) and the grey area represents outdoor temperatures below the reference temperature used for sizing (-11°C for the Woopa Building). Below this point, the building cannot be considered as "faulty". Figure 5 shows that even for relatively high outdoor temperatures (>5°C) the system is not able to meet the set point temperature.

The fault is isolated and recurrent: the user can collect information to know what happened and the state of the systems in the zone. Monitoring this specific zone for several weeks can also help understand the cause of the fault. For the fault illustrated above, potential causes can be: sensor failure, regulation valve locked, faulty settings on local controller, broken/open window.

Discussion

To implement R2 we chose overheating and underheating thresholds of 2°C and 1°C to adapt the rule to the heating season: underheating faults can be more impacting on the occupant's comfort. Those values could be a parameter that the user can tune according to the level of detection accuracy he wants to achieve. The impact of such faults on KPIs has not been fully addressed yet but is essential to drive the Building Manager towards better fault treatment: it can help quantify the overconsumption or user lack of comfort due to a temperature fault, for example. We displayed a picture of the proposed methodology to detect the faults and guide the Building Manager to the possible causes. It is based on the interaction between the automatic evaluation of indicators and the manual selection of objects and group of objects to be further analysed. This work is on-going and will continue to build an operational tool based on the presented concept. The development of the tool and the rest of the implementation process will involve the Building Managers to ensure that their needs and expectations are met. For example the analysis could be more relevant on a monthly basis or with more detailed visualisation charts. To balance the importance of a fault we thought of a trust indicator based on the data quality received by the BMS: this enables the user to prioritise the actions to undertake and fix the most probable and impacting faults. Such a methodology is also able to store the fault history for a given object and use this information to guide the user to this specific object if a fault often occurs. The automatic detection of patterns to identify the temporal and spatial regularity of faults is also in the scope of this development.

Conclusion

The main purpose of the article was to focus on the first steps of the methodology, that is to say the building data analysis, the expert-rules definition and the application of those rules to the collected data in order to detect any localised or recurring fault. The technical part is only focused on one rule among others. It was our choice to go in depth on the indoor temperature issues for a better comprehension rather than giving a brief overview of all the rules that we identified for the Woopa office building. The work on FDD is an on-going process in the PERFORMER project and the involvement of the Building Managers is fundamental to ensure that the entire process meets specific requirements in an energy performance guarantee perspective. The other rules are being tested off-line and the team has to work on the next steps of the FDD methodology and particularly on the connection aspects including the integration of the expert-rules into the BMS hierarchy, the energy management control system and the use of sensors.

The user interface is also an important component of the whole FDD chain that the team has to develop as it has to provide the end user with all the information that helps him conduct the detection and diagnosis work. The Building Manager has to see straight away if there is any system or piece of equipment which does not work properly and where in the building the fault occurred. The user interface has to display the most relevant visualisation tools for the end users, both in terms of skills and details. It has to be considered as an operational tool that provides the most accurate representation modes of the situation of the building in real time and as a decisionmaking tool to help Building Managers in the fault diagnosis process. In order to ensure that the rules are working properly, it is therefore important to test them by creating artificial faults. This testing phase should include: a fault-free test procedure, sensor validation procedure, the list of the specific faults to be tested, threshold settings, alarm handling, etc.

The results from the simulation work will be also used to adjust the accuracy of the rules. As an overall recommendation, expert rules should not be considered just as an easy way to conduct a FDD approach but as the key technique to ensure that the specific faults identified with the Building Managers will be detected and diagnosed in a very accurate manner and as the best operational method that includes all the stakeholders into the process.

2 Fig. 1 -

 21 Fig.1-The FDD approach followed within the PERFORMER project[START_REF] Vaezi-Nejad | Automatic tools for fault detection and diagnostic of HVAC systems for hotel and office buildings[END_REF]

Fig. 2 -

 2 Fig. 2 -Underheating issue of the Temperature in zone BQ_F1_S

Fig. 3 - 4 -

 34 Fig. 3 -Weekly average of Temperature Fig. 4 -Heatmap of hourly underheating indicator (zone underheating faults on building map (Floor 3) BN_F3_N) [1: Fault]

Fig. 5 -

 5 Fig. 5 -Scatter plot of Indoor and Outdoor Temperatures with set point temperature (T_stp)

Table 1 :

 1 Indicators for global performance of systems and FDD

		System efficiency
		Pumps energy consumption for distribution
	Heating Systems	Indicator of optimal start test (EN NF12098-1) % successful starts Local hourly average operative temperature for the 1 st hour of occupancy
		Temperature differential between local hourly average operative
		temperature and local set point temperature
		System efficiency
		Pumps energy consumptions for distribution
	Cooling Sytems	Indicator for optimal start test % of successful starts Local hourly average temparature for the 1 st hour of occupancy
		Temperature differential between local hourly average operative
		temperature and local set point temperature
	DHW Systems (Hotels)	DHW system efficiency Thermal solar collector efficiency Supply temperature from hot water tank
		Fans energy consumptions
	AHU/ ventilation	Status of the fan Pumps battery consumption Ratio of supplied flow rate and hygienic ventilation flow rate
		Pressure drop across AHU filters

Acknowledgment

The research leading to these results has received funding from the FP-7-2013-NMP_ENV-EeB call of the European Union's Seventh Framework Program FP7/2007-2013 under grant agreement n° [609154].


Soukaina Cherkaoui

Inès Keskes

Hervé Rivano

Razvan Stanica

LTE-A Random Access Channel Capacity Evaluation for M2M Communications

Keywords: M2M, LTE-A, RACH, MTC, Random Access, Capacity

The densification of the urban population and the rise of smart cities applications foster the need for capillary networks collecting data from sensors monitoring the cities. Among the multiple networking technologies considered for this task, cellular networks, such as LTE-A, bring an ubiquitous coverage of most cities. It is therefore necessary to understand how to adapt LTE-A, and what should be the future 5G architecture, in order to provide efficient connectivity to Machine-to-Machine (M2M) devices alongside the main target of mobile networks, Human-to-Human devices. Indeed, cellular random access procedures are known to suffer from congestion in presence of a large number of devices, while smart cities scenarios expect huge density of M2M devices. Several solutions have been investigated for the enhancement of the current LTE-A access management strategy. In this paper, we contribute to the modeling and computation of the capacity of the LTE-A Random Access Channel (RACH) in terms of simultaneous successful access. In particular, we investigate the hypothesis of piggybacking the payload of Machine Type Communications from M2M devices within the RACH, and show that M2M densities considered realistic for smart cities applications are difficult to sustain by the current LTE-A architecture.

I. INTRODUCTION

While many academic studies in the last decade have considered that wireless sensor networks are multi-hop, short range and low power, there is currently a strong push promoting cellular networks for collecting Machine-to-Machine (M2M) data [START_REF] Bartoli | Low-Power Low-Rate Goes Long-Range: The Case for Secure and Cooperative Machine-to-Machine Communications[END_REF]. Dedicated M2M cellular infrastructure are rising, e.g. SigFox 1 and LoRa 2 , but address only very low throughput (few bytes per minutes) and mostly asymmetric applications. Traditional mobile operators are trying to take their share of the market, taking benefit from their ubiquitous coverage of cities and their ability to manage secured and authenticated communications. Besides, the background traffic of recent smartphones (e.g. application notifications, system synchronization) is very close to Machine Type Communication (MTC) traffic, and it is already causing resource management issues. As a consequence, the 2014 Ericsson mobility report [START_REF] Ericsson | Ericsson Mobility Report[END_REF] notes that more than 200 million cellular M2M devices were in used at the end of 2013. However, only 1% of 1 http://www.sigfox.com/en 2 http://lora-alliance.org USA deployed M2M devices use the LTE network, while 64% of active M2M devices are still connected via GPRS-EDGE. As CDMA-based 3G is not suitable to low power operations [START_REF] Bartoli | Low-Power Low-Rate Goes Long-Range: The Case for Secure and Cooperative Machine-to-Machine Communications[END_REF], exploiting the existing LTE infrastructure and preparing the future 5G standards for M2M access is therefore a very important challenge.

All the cellular technologies share a common characteristic in the use of slotted Aloha [START_REF] Metzner | On Improving Utilization in ALOHA Networks[END_REF] as the pillar element of the Random Access Channel (RACH). Even though slotted Aloha has been extensively studied in terms of achievable throughput [START_REF] Namislo | Analysis of Mobile Radio Slotted ALOHA Networks[END_REF], the literature is missing a proper modeling of the access capacity. In particular, the question we ask is how does an LTE-A eNodeB react when facing a large number of uplink requests?

Although the 3GPP LTE-A standard is incrementally including some support for MTC communications, the modern cellular system has been basically designed, engineered and managed to afford access to a reasonable number of Humanto-Human (H2H) communications, with high dowlink data rate. In contrast, M2M applications require connections from a significant number of devices, mostly for uplink traffic, each communication having a low volume, and the interarrival times being conditioned by duty-cycle mechanisms [START_REF] Shafiq | Large-Scale Measurement and Characterization of Cellular Machine-to-Machine Traffic[END_REF]. The usual optimization of the infrastructure may therefore be irrelevant for supporting M2M communications. In particular, the LTE-A Random Access (RA) procedure organizes the contention for access both physically, on time-frequency resources, and logically, on available signatures, which makes the collision detection challenging. When the number of user equipments (UE) is too large, the access may be denied to virtually all of them. This kind of congestion is classic in H2H communication, when crowds gather at the same place for exceptional events. With the deployment of MTC devices, such density of UEs can become a regular situation.

Our main contribution in this study is providing a new modeling of the RA procedure that abstracts the physical layer and focuses on the impact of the traffic arrival rate and on the number of M2M devices. This model is used in extensive simulations, to derive engineering insights on the configuration of the RACH. The parameters showing the highest impact are the number of RA opportunities in which UEs can compete for access, and the number of available preambles, which gives the size of the contention space. The trade-offs between these parameters show that each configuration presents a threshold on the number of users after which the success ratio drops very quickly, requiring an adaptation of the RACH settings to the number of users.

The rest of the paper is structured as follows. In Section II, we give a brief overview of M2M communications and of the random access procedure in LTE-A. Section III introduces our RACH model, while Section IV is dedicated to the analysis of our simulation results and the deduced engineering insights. Section V positions our contribution among the literature of the domain, before concluding remarks in Section VI.

II. RACH FOR M2M COMMUNICATION

Communication in a mobile network follows two major procedures: a resource allocation demand is first transmitted by the UE which, if successful, is followed by the actual data transmission phase, using dedicated resources allocated by the eNodeB (eNB) to the UE. This procedure was designed specifically for H2H traffic, which is bursty by nature, and it is based on the notions of session and call, activities that keep the user involved for a relatively long time and necessitate the exchange of a series of messages with the network.

M2M traffic is essentially heterogeneous and applicationdependent, which makes it uneasy to classify into a specific category. However, it is common to smart metering and reporting applications to generate and transmit periodically very low amount of data [START_REF] Vodafone | RACH Intensity of Time Controlled Devices[END_REF]. This means that the M2M UEs have to go through a signaling-heavy RA procedure, described below, simply to transmit one message to the network.

Therefore, the idea of piggybacking the M2M data transmission within one of the RA procedure messages is tempting and it is now considered as the best solution for this type of traffic [START_REF]Study on RAN Improvements for Machine-type Communications[END_REF]. This means that the M2M data is transmitted on the shared resources of the RACH, and raises questions regarding the capacity of the RACH, which was not designed for these purposes. In the following, we detail the RA procedure, used by UEs competing for channel access. This competition takes place on two dimensions: the RACH resource blocks (RB), and the preamble signatures.

An eNB contains a pool of predefined orthogonal signal patterns, denoted preamble signatures and divided into two groups: contention-based and contention-free signatures. The explanation for this division is that, for some operations where the user is already connected to the network, such as handover or new downlink data arrival, the UE is allocated directly a contention-free signature. However, in most cases, and especially for M2M traffic, the UE is idle before a transmission and therefore needs to go through the RA procedure, using contention-based preambles. The RA procedure consists of four successive steps:

• Step 1 (UE → eNB): Preamble transmission. A user needing network access randomly selects and transmits a preamble among those available for the contention-based procedure. At this step, no additional information is sent by the UE. In particular, the eNB is not informed yet of the reason for the resource request. It is important to note that the preambles can be transmitted only during an RA slot, and the number of RA slots per LTE-A frame is decided by the eNB and broadcast to the UEs in the system information block. As discussed in Section IV, the UE can decide to increase the number of RA slots, but this will happen at the expense of data slots.

• Step 2 (eNB → UE): Random access response.

If a preamble has been correctly decoded, the eNB acknowledges it by sending a random access response (RAR). Since the eNB has simply received a predefined signal pattern, it has no knowledge on the identity of the UE making the request. Therefore, the RAR is addressed to a Random Access Radio Network Temporary Identifier (RA-RNTI), which identifies the RB on which the preamble was decoded. As the transmitting UE implicitly knows the RB it used to transmit the preamble, it will also be able to interpret the acknowledgment. A back-off indicator can also be included in the RAR, to be used by the UEs in case of a failed transmission in Step 3. A device expects to receive the RAR within a configured time window, or else it deduces that its preamble was not decoded and goes back to Step 1, retransmitting with a higher transmitting power (i.e. the power ramping mechanism) during the next RA opportunity. It is noteworthy that the RAR does not directly help solving collisions: if several users have sent the same preamble in the same RA slot, and if the eNB has decoded it, they will all receive the same RAR and consider they have been granted uplink resources for message transmission in Step 3.

• Step 3 (UE → eNB): Connection request message.

This message contains the connection request cause, such as a Radio Resource Control (RRC) connection request, tracking area update or scheduling request. In this step, the UEs send for the first time their real identity to the eNB. For M2M traffic, this is the message considered for piggybacking the application data, as explained above. We note that users who collided on preamble selection in Step 1 are granted the same uplink resources in Step 3, therefore their transmissions will interfere. This interference may lead all the colliding UEs to restart the complete RA procedure. Nevertheless, if one user has a much better channel quality than the others, its message will be successfully decoded, a phenomenon denoted as the capture effect.

• Step 4 (eNB → UE): Contention resolution.

This message conveys the identity of the decoded UE in the previous step. If an UE that transmitted a message in the previous phase can not decode the contention resolution message, or if it does not find its identity within this message, the UE stops the RA procedure and restarts another one from Step 1. On the contrary, an UE retrieving its identity within this message marks a successful access procedure and can use the dedicated uplink resources granted by the eNB in the message. In the case of M2M, this message is simply used for contention resolution, as an acknowledgement of the reception of the information piggybacked at Step 3.

III. RA PROCEDURE MODEL

In this section, we present our modeling of the RACH, our main assumptions and the default values of some parameters. We note that we evaluate the performance of the RA procedure from a network perspective. We therefore make an abstraction of lower protocol layers and the physical environment. In particular, we do not model precisely the position of the UEs, nor the radio propagation, and account for transmission failures and capture effect as input parameters of the model. Practically, the entire physical layer is represented by three parameters: p d , p c , p r , discussed below. The proposed model is summarized in Fig. 1.

A. Assumptions and model description

One cell of 3GPP LTE-A is considered serving a set of M2M devices that are perfectly time-synchronized. UEs can be in either one of the three following states.

• Idle (I-mode): UEs with an empty transmission buffer.

• Transmitting mode (T-mode): users trying to send a message. • Backlogged (B-mode): UEs waiting to retry after a transmission failure. We assume that the traffic is periodic, each UE having one message arrival per period. The message is considered small enough to be piggybacked in the Step 3 of the RA procedure, without segmentation. If, due to buffering and transmission failures, a UE has x messages in its buffer at a given time, it will perform x times the RA procedure and send one message at a time. This is an obvious under estimation of the throughput in our model, but a better understanding of the access capacity of the cell.

Each period contains a number Opp of RA opportunities. It is important to note that this gathers in one value two major parameters: the duration of the M2M application period, and the number of RA slots per LTE-A frame. On the one hand, the periodicity of the M2M traffic depends on the application: uploading vehicular data for fleet monitoring requires short periods, in the order of 100 ms [START_REF] Ancona | Performance Boundaries of Massive Floating Car Data Offloading[END_REF], while smart metering applications produce one message every few minutes [START_REF] Vodafone | RACH Intensity of Time Controlled Devices[END_REF]. On the other hand, as mentioned in Sec. II, the number of RA slots per LTE-A frame is decided by the network, and can even change dynamically [START_REF] Kim | Adaptive Random Access Preamble Split in LTE[END_REF]. These two parameters are combined in one input value for our model.

The message arrivals at different UEs are randomly distributed over the application period. Upon message arrival, or when the transmission buffer is not empty, I-mode UEs switch to T-mode and start their RA procedure at the next RA opportunity. In each opportunity, T-mode UEs randomly select one of the available preambles and send it to the eNB. The size of the pool of available preambles for contention-based access is denoted K. The transmission of the preamble is detected by the eNB with probability p d , which accounts for the possible transmission failures due to radio propagation issues. In our model, p d is independent and identically distributed for all the selected preambles, meaning that the preamble detection probability does not depend on the number of UEs having selected it.

UEs with undetected preambles move directly to B-mode. In the case of the detected preambles, the RA procedure continues and several possibilities arise:

i) The same preamble was selected by three or more UEs. In this case, we consider the RA procedure fails for all the nodes. This can happen either because the eNB realizes that multiple UEs transmitted the same preamble in Step 2, and therefore it does not replies with an RAR, or because the UEs reach Step 3 and transmit their messages at the same time, resulting in a collision. Practically, we consider that the interference is too important for the capture effect to allow the decoding of any message at the eNB.

ii) The same preamble was selected by two UEs. When this happens, the capture effect produces with probability p c , meaning that the transmissions of the two UEs are received at the eNB with so different power levels that the eNB is able to detect and decode the message of the strongest signal. In our model, we have a probability p c that one of the UEs, randomly chosen between the two, succeeds and moves in I-mode, while the second UE restarts the RA procedure, by moving to B-mode. We note that the opposite event, arriving with probability 1 -p c , is that both UEs fail and move in B-mode.

iii) The preamble was selected by only one UE. In this event, we only account for possible radio propagation problems, and the UE succeeds its transmission with probability p r .

As explained, non-successful UEs are put in B-mode. They have the chance to retry their transmission after a backoff window, of maximum value b max . A maximum number of retrials is allowed and denoted r max . If r max is reached, the access procedure fails. For the sake of simplicity and without losing precision on our estimation of the access capacity, we mingle the retransmissions in Step 1 with those in further steps, although the LTE-A standard distinguishes them for more detailed UE management.

B. Parameter settings

Our model relies on a set of parameters that are summarized in Tab. I. One can distinguish two kinds of parameters: those that describe our abstraction of the radio environment, and those describing the configuration of the system. The first group consists of the three probabilities defined above (p d , p r , p c ), that account for the effects of the physical layer, environment, and UE distribution. One could argue that these simple parameters are not enough to account for such a complex set of physical phenomenon. However, since we are not interested in the physical capacity of the RACH, but on the number of UEs that can be granted access in one period, we believe this aggregated and abstract modeling of the environment is enough. On reasonable ranges of values for these parameters, the impact of each probability is weak whatever the number of UEs. In the following, they are considered fixed with the assigned values in Tab. I.

The second group of parameters consists of the system settings that have to be set up by the operator. Most of them have default or advised values that are defined by 3GPP, such as the backoff window or the maximum number of restransmissions. For the number of available preambles, 64 preamble signatures are defined by the standard. However, some of these preambles are reserved for contention-free access (see Sec. II), so not all of them are usable in the RA procedure. Finally, the LTE-A standard defines a set of valid frequencies of RA opportunities ranging between 0.05 to 1 RA opportunities per millisecond. Nevertheless, we remind that the time basis of our model is the periodicity of the application messages, not the one of the LTE-A frames. We are therefore interested in Opp, the number of opportunities per period, which does not only depend on the RA opportunities, but also on the application traffic model. We remark that, for the parameters in this second group, default values are provided in Tab. I, but the impact of each parameter is also analyzed.

IV. RESULTS AND DISCUSSION

Assuming some essential in-home M2M applications, coupled with house density and cell size, an urban area cell should support in average 18000 devices [START_REF] Vodafone | RACH Intensity of Time Controlled Devices[END_REF]. Therefore, in order to investigate the capacity limits of the LTE-A RACH, our simulations are carried with more than 1000 devices. For the rest of the paper, unless specified, we consider the default values for parameters given in Tab. I.

A. Impact of the number of available preambles

We begin by studying the impact of the number of available preambles on the UE RACH success ratio, in Fig. 2 Nevertheless, one must keep in mind that the number of preambles available for an eNB should be shared between contention-free and contention-based access. Also, the contention-based set could be separated according to the user type, between M2M and H2H UEs. Considering that as many as 40 preambles are required in order to obtain an M2M success ratio higher than 0.95 for 1000 M2M UEs, even the support of this relatively small number of devices seems questionable in a real deployment.

As explained above, high densities of M2M devices are expected, especially in smart city scenarios. Therefore, in Tab. II we show that supporting 10000 M2M users per cell requires the eNB to provide only for these UEs almost 7 times more preambles than the value currently set by the standard, in order to guarantee an efficient success rate of 0.97.

B. Impact of the number of opportunities per period

The opportunities represent the RBs where a user is allowed to transmit its access request. Therefore, the more opportunities a period is divided into, the wider the random access contention space is. Thus, increasing Opp reduces the number of collisions and improves the success ratio, as shown in Fig. 3.

Increasing the number of opportunities per period can be achieved in two different ways. The frequency of RA opportunities can be increased, as explained in Sec. III-B, but this comes at the expense of less RBs for data in the LTE-A frame. This means that, adding more RACH slots to increase the success ratio of M2M UEs can have a significant negative effect on regular H2H UEs, who mostly use dedicated RBs. The transmission period of the M2M application can also be increased, to allow more access opportunities to the Fig. 3: Impact of the number of opportunities per period on the success ratio (95% confidence intervals are shown). users. However, the transmission period generally comes as a constraint, being dictated by application requirements.

The impact of the Opp parameter is significant. For example, if we consider a normal scenario today, with one RA opportunity every LTE-A frame, the results in Fig. 3 can be understood as follows: if 48 preambles are dedicated to M2M traffic, the LTE-A RACH can support the access of up to 1000 UEs running an application with a transmission period of 500ms, and up to 10000 UEs if the application has a transmission period of 4.5s.

C. Impact of the number of retransmissions

If the RA procedure fails, the UE will enter a back-off phase before attempting the access again. The number of attempts that are allowed, r max , is decided by the network, and communicated to the UEs. The impact of r max on the UE success ratio is shown in Fig. 4.

Success ratio

Max allowed retransmissions number of users =1000 number of users =2000 number of users =3000 number of users =4000 Fig. 4: Impact of the number of allowed retransmissions on the success ratio.

Two opposite behaviors can be noticed, depending on the number of UEs in contention for access. For less than 1000 M2M users, increasing r max results in a higher success ratio. However, when more than 2000 UEs are present, authorizing more retransmissions simply leads to an even higher RACH congestion, drastically reducing the success ratio.

A high number of retransmissions can also result in larger transmission delays. As a consequence, a situation might occur where a new message arrives at the MAC layer for transmission before the UE can finalize the RA procedure for the previous message. In our model, we consider that these messages will use independent access procedures, whereas in a practical deployment they could be aggregated, or even transmitted on dedicated RBs, outside the RACH.

D. Impact of the backoff window size

To highlight the impact of the backoff window configuration, we choose a less congested situation than in the previous scenarios, by setting the number of preambles to 60, while the default values are used for the other parameters. The success ratio for different backoff windows is shown in Fig. 5, where the successful transmission for the different UEs is also depicted. For example, we can notice that the backoff window does not impact significantly the success distribution for the 1000 M2M users case, where 60% of the accesses are done without retransmission, regardless the backoff window size. However, in heavily congested scenarios, e.g. 3000 M2M users, increasing the back-off window can bring important improvements, a back-off window of 35 RA slots almost doubling the success ratio compared with the default value.

E. Preamble dimensioning use case

From the results above, two parameters are noticed to have a major impact on the performance of the RA procedure: the number of available preambles, and the number of opportunities per period. As explained, this second parameter is not entirely up to the operator, as it also depends on the application requirements. We therefore focus on the number of preambles, by analyzing the minimum number of signatures required for M2M users in order to guarantee a targeted success ratio. These results are presented in Fig. 6, where the traffic arrival is represented in terms of number of UEs attempting the access in a given RA opportunity.

The results outline a trade-off between the acceptable performance and the available preamble resources. For example, improving the success ratio from 0.8 to 0.999 costs the addition of at least 20 more preambles for a traffic intensity Fig. 6: Minimum number of preambles required for a predefined success ratio, as a function of the number of users per opportunity.

of 10 users per opportunity, while only 5 additional preambles are required to reach a 0.99 success rate.

Overall, we observe that, using the current values of the standard, the capacity of the RACH is one order of magnitude smaller than the number of M2M devices that are expected in a smart city scenario. This problem can be alleviated by increasing the number of available preambles or RA opportunities for M2M traffic, but such solutions should be carefully designed, in order to minimize the impact on the regular H2H traffic.

V. RELATED WORKS

As the H2H traffic generally uses dedicated resources, most of the studies in the literature focus on the performance of the cellular downlink. The cellular uplink in general, and the RACH in particular, have been relegated to a second level. For example, state-of-the-art LTE simulation frameworks, such as LTE-Sim [START_REF] Piro | Simulating LTE Cellular Systems: An Open-Source Framework[END_REF] do not implement the random access procedure. With the rise of M2M traffic, which is mostly uplink, a few studies tackled the subject of the LTE capacity at a physical layer, e.g. [START_REF] Novlan | Analytical Modeling of Uplink Cellular Networks[END_REF]. However, physical layer metrics are difficult to translate in an access capacity and require as input a very detailed knowledge of the environment and of the UE placement.

The first attempts to evaluate the LTE RACH capacity in terms of successful UE access ( [START_REF]Study on RAN Improvements for Machine-type Communications[END_REF], [START_REF] Ericsson | LTE Random-Access Capacity and Collision Probability[END_REF]) were presented in the 3GPP working groups. However, these studies consider a constant collision probability, independent of the number of UEs or of the available resources. Analytical models of the RA procedure were also proposed (e.g. [START_REF] Cheng | RACH Collision Probability for Machine-Type Communications[END_REF], [START_REF] Nielsen | A Tractable Model of the LTE Access Reservation Procedure for Machine-Type Communications[END_REF]), where the UE outage probability is computed. These studies also make assumptions that are difficult to verify on the collision probability, such as an exponential dependence on the number of preambles in [START_REF] Cheng | RACH Collision Probability for Machine-Type Communications[END_REF]. Also, phenomena difficult to represent analytically, such as the capture effect, are ignored. Finally, several studies start from the observation that RACH congestion is produced by M2M devices, and propose different mechanisms to alleviate this problem [START_REF] Laya | Is the Random Access Channel of LTE and LTE-A Suitable for M2M Communications? A Survey of Alternatives[END_REF], without actually quantifying it. VI. CONCLUSIONS Support of short information messages generated by M2M applications is identified as one of the key challenges for 4G and beyond wireless networks. In this paper, we propose a model for the RA procedure in LTE-A networks. By abstracting the physical layer parameters, we are able to model in detail the RA procedure, without any supplementary assumptions on the collision probability, while at the same time taking into account complex phenomena such as the capture effect. This allows us to provide an estimation of the access capacity on the LTE-A uplink, and highlight the difference between the number of M2M UEs that can be supported by the RACH and the number of devices foreseen by M2M applications.

VII. ACKNOWLEDGMENT

Fig. 1 :

 1 Fig. 1: LTE-A random access procedure model.

  Parameter settings and default values.

Fig. 2 :

 2 Fig. 2: Impact of the number of available preambles on the UE success ratio (95% confidence intervals are shown).

Fig. 5 :

 5 Fig. 5: Backoff impact on success ratio and distribution of the successful transmission attempt.

  . Our results show major difficulties in carrying the M2M traffic of more than 2000 UE with an acceptable success ratio, even

	Number of	100	200	300	400	500
	available
	preambles
	Success ratio 0.00059 0.065	0.41	0.87	0.97

TABLE II :

 II Success ratio for 10000 UEs with different numbers of available preambles. when all the 64 available preambles are dedicated to M2M contention-based random access.

This work has been carried out in the framework of IDEFIX project, funded by the ANR under the contract number ANR-13-INFR-0006, the ADR Green of the Alcatel-Lucent/INRIA common laboratory, and the Inria Project Lab CityLab@Inria.