Paul Strohmeier

Victor Håkansson
email: victor@skavi.dk

Cedric Honnet
email: cedric@honnet.eu

Daniel Ashbrook

Kasper Hornbaek

Optimizing Pressure Matrices: Interdigitation and Interpolation Methods for Continuous Position Input

Keywords: Sensor design, piezoresistive, pressure matrix, pressure input, interdigitation, interpolation, eTextile

This paper provides resources and design recommendations for optimizing position input for pressure sensor matrices, a sensor design often used in eTextiles. Currently applications using pressure matrices for precise continuous position control are rare. One reason designers opt against using these sensors for continuous position control is that when the finger transitions from one sensing electrode to the next, jerky motion, jumps or other non-linear artifacts appear. We demonstrate that interdigitation can improve transition behavior and discuss interpolation algorithms to best leverage such designs. We provide software for reproducing our sensors and experiment, as well as a dataset consisting of 1122 swipe gestures performed on 17 sensors.

INTRODUCTION

Continuous multi-touch pressure and position input is becoming increasingly mainstream, notably finding application in synthesizer controllers [START_REF] Donneaud | Designing a Multi-Touch eTextile for Music Performances[END_REF][START_REF] Seaboard | The Future Of The Keyboard | ROLI[END_REF][START_REF]Product -Joué[END_REF]. Pressure based position input is also used in wearable systems, including on-body gesture input [START_REF] Schneegass | GestureSleeve: using touch sensitive fabrics for gestural input on the forearm for controlling smartwatches[END_REF], user authentication [START_REF] Voit | FabricID: Using Smart Textiles to Access Wearable Devices[END_REF], object recognition [START_REF] Zhou | From smart clothing to smart table cloth: Design and implementation of a large scale, textile pressure matrix sensor[END_REF], control of IoT objects [START_REF] Parzer | FlexTiles: A Flexible, Stretchable, Formable, Pressure-Sensitive, Tactile Input[END_REF] or detection body deformations [START_REF] Parzer | SmartSleeve: Real-time Sensing of Surface and Deformation Gestures on Flexible, Interactive Textiles, using a Hybrid Gesture Detection Pipeline Patrick[END_REF].

These systems are often implemented using a resistive pressure sensor matrix, which consists of a pressure sensitive layer surrounded by conductive strips in a row and column arrangement. [START_REF] Cheng | Textile Building Blocks: Toward Simple, Modularized, and Standardized Smart Textile[END_REF][START_REF] Donneaud | Designing a Multi-Touch eTextile for Music Performances[END_REF][START_REF] Parzer | SmartSleeve: Real-time Sensing of Surface and Deformation Gestures on Flexible, Interactive Textiles, using a Hybrid Gesture Detection Pipeline Patrick[END_REF][START_REF] Schneegass | GestureSleeve: using touch sensitive fabrics for gestural input on the forearm for controlling smartwatches[END_REF][START_REF] Zhou | From smart clothing to smart table cloth: Design and implementation of a large scale, textile pressure matrix sensor[END_REF]. Often the sensor is connected to a gesture recognition system [START_REF] Parzer | SmartSleeve: Real-time Sensing of Surface and Deformation Gestures on Flexible, Interactive Textiles, using a Hybrid Gesture Detection Pipeline Patrick[END_REF][START_REF] Schneegass | GestureSleeve: using touch sensitive fabrics for gestural input on the forearm for controlling smartwatches[END_REF], allowing the user to perform discrete actions. Truly continuous position input, however, also requires locating pressure events that do not align with the sensor's electrodes. This is typically achieved through interpolation [START_REF] Donneaud | Designing a Multi-Touch eTextile for Music Performances[END_REF][START_REF] Rosenberg | The UnMousePad -The Future of Touch Sensing[END_REF], however, even with interpolation the transition behavior from one electrode-strip to the next introduces jumps or discontinuities [START_REF] Donneaud | Designing a Multi-Touch eTextile for Music Performances[END_REF][START_REF] Fisher | A Comparison of Algorithms for Subpixel Peak Detection[END_REF]: Depending on the method chosen to extract the position of the finger, the signal might lag behind or jump ahead as a finger moves from one strip to the next (see video figure). There is no consensus if there is a best method to find touchpositions from such sensors, or what this method might be.

Our goal is to maximize the sensing resolution of pressure sensor matrices by methods other than increasing the electrode count. This can be done by leveraging the conductive properties of the resistive material [START_REF] Rosenberg | The UnMousePad -The Future of Touch Sensing[END_REF], by interpolating the collected data [START_REF] Donneaud | Designing a Multi-Touch eTextile for Music Performances[END_REF], or by using diagonal or triangular electrode designs which create gradual transitions from one electrode to the next [START_REF] Yoo | Development of two-dimensional interdigitated center of pressure sensor[END_REF]. The latter approach, which we refer to as interdigitation, is quite common in DIY context (Figure 1,b,c,d,e), and can be found in product briefs and white-papers [START_REF]The world's most energy friendly microcontrollers Hardware Design for Capacitive Touch AN0040-Application Note[END_REF][START_REF] Semtech | Application note: capacitive touch sensing layout guidelines[END_REF]. It is, however, not clear if and how such designs effect resistive pressure matrices.

We investigate effects of interpolation algorithm choice and electrode interdigitation on accuracy, precision, and consistency of touch-position sensing. In doing so we make three contributions: [START_REF] Akhtar | A methodology for evaluating accuracy of capacitive touch sensing grid patterns[END_REF] We provide a data-set of 1122 swipe gestures performed on 17 sensors. This dataset is designed to Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for thirdparty components of this work must be honored. For all other uses, contact the Owner/Author. enable quick testing of algorithms for extracting positions for various sensor designs, pressure levels and touch sizes. [START_REF] Akhtar | A Comparative Analysis of Capacitive Touch Panel Grid Designs and Interpolation Methods[END_REF] We analyze and compare eight peak-detection algorithms for extracting touch position. [START_REF] Blais | Real-time numerical peak detector[END_REF] We investigate the effects of interdigitated patterns on sensor performance. In additionally, we also provide all code used in this project, including the pattern-generator used for creating the sensors and a prototype simulation tool for testing electrode patterns. This project was started to optimize eTextile sensors. While the results generalize to any resistive pressure sensor matrix, we discuss them in the context of eTextile sensing.

ADDITIONAL RESSOURCES

All code, data, and supplementary material can be found at: https://datapaulette.github.io/interdigitation/

BACKGROUND AND RELATED WORK

Pressure Sensor Matrixes

Traditional resistive touchscreens can estimate the position of the touch, but not the amount of pressure exerted. There are variations which can do both, but these are uncommon, due to the complexity of their driving circuits [START_REF] Freed | Novel and Forgotten Currentsteering Techniques for Resistive Multitouch, Duotouch, and Polytouch Position Sensing with Pressure[END_REF]. A simpler alternative is to use a high number of discrete pressure sensors [START_REF] Lokavee | Sensor pillow and bed sheet system: Unconstrained monitoring of respiration rate and posture movements during sleep[END_REF], however, this leads complex physical designs as n pressure positions require at least n*2 physical connections. Pressure sensor matrices provide a middle ground as they are relatively simple to understand and implement, and also scale well: n pressure positions only require 2√𝑛𝑛 physical connectors [START_REF] Freed | Novel and Forgotten Currentsteering Techniques for Resistive Multitouch, Duotouch, and Polytouch Position Sensing with Pressure[END_REF].

Pressure sensor matrices reduce physical complexity by multiplexing measurements; pressure sensitive strips are laid out in a row and column arrangement. Figure 2 (left) shows a schematic where the rows might connect to digital outputs and the column to analog inputs. The top left resistance is measured by grounding all rows, except for row 0 which is pulled high, and reading from column 0. The voltage values would then be sampled sequentially at all positions, resulting in a 2D array of rasterized pressure information (See Figure 2, center and right for a visualization of touch events).

eTextile Touchpads

Both the somewhat delicate mechanical layering required for designs inspired by traditional resistive touchpads [START_REF] Heller | FabriTouch: Exploring Flexible Touch Input on Textiles[END_REF] as well as the relatively fine traces of high resolution devices such as Rosenberg's UnMousePad [START_REF] Rosenberg | The UnMousePad -The Future of Touch Sensing[END_REF] are currently difficult to implement in fabric. As with conventional sensors, the workarounds include sensor arrays [START_REF] Meyer | Textile Pressure Sensor for Muscle Activity and Motion Detection[END_REF][START_REF] Parzer | RESi: A Highly Flexible, Pressure-Sensitive, Imperceptible Textile Interface Based on Resistive Yarns[END_REF] that require a relatively large amount of physical connections. Various unconventional solutions, such as the XY textile by Donneaud [START_REF] Aguilar | XY fabric interface[END_REF] and a solution that shares many similarities with a 4-wire touchpad by Freed et al. [START_REF] Schmeder | Support Vector Machine Learning for Gesture Signal Estimation with a Piezo-Resistive Fabric Touch Surface[END_REF] have been suggested, but are rarely seen as the relative simplicity of the pressure sensor matrix eventually made it the default design.

Due to their softness, pliability, and the ease with which they can be integrated in everyday objects such as clothing or furniture, textile pressure matrices are also commonly used for pose detection while sleeping [START_REF] Parzer | FlexTiles: A Flexible, Stretchable, Formable, Pressure-Sensitive, Tactile Input[END_REF] or sitting [START_REF] Seaboard | The Future Of The Keyboard | ROLI[END_REF][START_REF][END_REF], as well as activity tracking [START_REF] Parzer | SmartSleeve: Real-time Sensing of Surface and Deformation Gestures on Flexible, Interactive Textiles, using a Hybrid Gesture Detection Pipeline Patrick[END_REF][START_REF] Zhou | From smart clothing to smart table cloth: Design and implementation of a large scale, textile pressure matrix sensor[END_REF]43]. Fabric pressure sensor matrices are also used for object recognition [START_REF] Rosenberg | The UnMousePad -The Future of Touch Sensing[END_REF]42]. Within the HCI community, pressure sensor matrices have been used for gestural input [START_REF] Borke | Interpolation methods[END_REF][START_REF] Wicaksono | FabricKeyboard : Multimodal Textile Sensate Media as an Expressive and Deformable Musical Interface[END_REF] body pose as input [START_REF] To | [END_REF] as well as user identification [START_REF] Runner® | Permanent Strips Refillable Value Pack -Scrapbook Adhesives by 3L[END_REF]. These applications do not require the detection of smooth transitions between strips. Instead, the maximum position is used with geometric models [START_REF] Wicaksono | FabricKeyboard : Multimodal Textile Sensate Media as an Expressive and Deformable Musical Interface[END_REF] or the analog data is converted to a binary image before applying computer vision methods [START_REF] Borke | Interpolation methods[END_REF][START_REF] Rosenberg | The UnMousePad -The Future of Touch Sensing[END_REF][START_REF][END_REF]. Machine-learning methods are also used for extracting relevant information from the raw data [START_REF] To | [END_REF][START_REF] Runner® | Permanent Strips Refillable Value Pack -Scrapbook Adhesives by 3L[END_REF]. The focus of this research lies on applications and the post processing of the sensor data. Only few papers report sensing accuracy [START_REF] Fisher | A Comparison of Algorithms for Subpixel Peak Detection[END_REF] which makes it difficult to establish best practices for the physical design and construction of the sensor.

As pressure sensitive touch-surfaces are an intriguing musical input modality, the modern experimental music and NIME communities have been instrumental in pushing eTextile input forward [START_REF] Wicaksono | FabricKeyboard : Multimodal Textile Sensate Media as an Expressive and Deformable Musical Interface[END_REF]. The availability of piezo resistive materials supported prototyping of a range of new input methods [START_REF] Freire | Designing eTextiles for the body: Shape, volume & motion[END_REF] which eventually resulted in various pressure matrix designs both in the NIME [START_REF] Schmeder | Support Vector Machine Learning for Gesture Signal Estimation with a Piezo-Resistive Fabric Touch Surface[END_REF] and DIY communities. Popular products such as the Roli Seaboard [START_REF] Seaboard | The Future Of The Keyboard | ROLI[END_REF] or the Joué board [START_REF]Product -Joué[END_REF] demonstrate the demand for highresolution continuous input, which makes empirically establishing best practices increasingly relevant.

Interpolation in Software and Hardware

As pressure is sampled at discrete intervals, the center of an object or finger is typically not aligned with the sensing elements. Finding the center of a pressure point therefore requires additional steps (see Figure 2, center and right). Most work investigating this focuses on capacitive input, as it is currently the most common method for multi-touch sensing. Examples include comparisons of electrode patterns and interpolation methods [START_REF] Akhtar | A methodology for evaluating accuracy of capacitive touch sensing grid patterns[END_REF].

Finding a signal maxima between sensing elements is common also outside of touch-screen design and is generally referred to as sub-pixel peak estimation [START_REF] Akhtar | A Comparative Analysis of Capacitive Touch Panel Grid Designs and Interpolation Methods[END_REF][START_REF] Nobach | Two-dimensional Gaussian regression for sub-pixel displacement estimation in particle image velocimetry or particle position estimation in particle tracking velocimetry[END_REF]. An overview is presented by Naidu and Fisher [START_REF] Fisher | A Comparison of Algorithms for Subpixel Peak Detection[END_REF][START_REF] Naidu | A Comparative Analysis of Algorithms for Determining the Peak Position of a Stripe to Sub-pixel Accuracy[END_REF] who conducted an empirical analysis of eight algorithms. They noted that all algorithms tested by them displayed periodic error patterns, similar to those observed in the transition behavior of textile pressure matrices [START_REF] Donneaud | Designing a Multi-Touch eTextile for Music Performances[END_REF]. Naidu and Fisher claim these errors to be "symptomatic of the sensor structure" [START_REF] Fisher | A Comparison of Algorithms for Subpixel Peak Detection[END_REF].

There appear to be three factors influencing transition behavior: (1) the spread of the signal of interest [START_REF] Donneaud | Designing a Multi-Touch eTextile for Music Performances[END_REF][START_REF] Fisher | A Comparison of Algorithms for Subpixel Peak Detection[END_REF], (2) the peak detection algorithm [START_REF] Fisher | A Comparison of Algorithms for Subpixel Peak Detection[END_REF] and (3) the physical design of the sensor [START_REF] Fisher | A Comparison of Algorithms for Subpixel Peak Detection[END_REF]. However, there is comparatively little work exploring alternative sensor structures in pressure-sensor matrices. Rosenberg et al. present a matrix that utilizes the horizontal conductivity of the resistive material for better interpolation [START_REF] Ilya | IMPAD -An Inexpensive Multi-Touch Pressure Acquisition Device[END_REF] and demonstrate how adding additional 'dummy electrodes' linearizes the horizontal conductivity [START_REF] Rosenberg | The UnMousePad -The Future of Touch Sensing[END_REF]. The method used by Rosenberg et al. assumes a touch from the tip of a stylus. It is unclear if their approach generalizes to the larger touch area of a fingertip.

An alternative approach uses triangular interdigitation. If one moves a finger from one strip to the next at a fixed speed, the transition occurs faster if the motion is perpendicular to the strips than if the strips are arranged diagonally. Yoo and Pines demonstrate this approach in a 'center of pressure' sensor [START_REF] Yoo | Development of two-dimensional interdigitated center of pressure sensor[END_REF], however they chose a design which only supports input at discrete positions. Triangular interdigitated designs can also be found in white-papers and application notes for capacitive slider design [START_REF]The world's most energy friendly microcontrollers Hardware Design for Capacitive Touch AN0040-Application Note[END_REF][START_REF] Semtech | Application note: capacitive touch sensing layout guidelines[END_REF] and are also common in the DIY community: They are being explored in Paris based textile hackerspace Datapaulette, they can be found in the web-archive by Satomi and Perner-Wilson [START_REF] To | [END_REF], as Instructables by Freire [START_REF]Product -Joué[END_REF] or in the eTextile swatchbook [START_REF] Hertenberger | E-Textile swatchbook exchange: The importance of sharing physical work[END_REF] (see also Figure 1). While triangular interdigitated designs are quite common, they are often justified based on intuition and -to the best of our knowledge -their effectiveness has never been evaluated.

SENSORS Design

We created a processing sketch that generates interdigitated patterns and exports them as .pdf, ready for laser cutting (Figure 3). For the patterns used in the dataset we used triangular digits. We varied the digits using two parameters:

Digit Width: Low digit width allows many digits to fit (Figure 3, top). High digit width means that only few digits fit on the strip (Figure 3, bot). Digit Width is the dimension parallel to the sensing strip.

Digit Length: Low digit length means that there is little overlap between electrodes (Figure 3, left). High digit length means that there is significant overlap (Figure 3, right). Digit Length is the dimension perpendicular to the sensing strip.

Implementation

We built our sensors according to Donneaud et al. [START_REF] Donneaud | Designing a Multi-Touch eTextile for Music Performances[END_REF], however, we created the electrodes following instructions by Strohmeier et al. [START_REF] Strohmeier | zPatch: Hybrid resistive/capacitive etextile input[END_REF]: We used conductive ripstop [START_REF] To | [END_REF] for creating the sensing electrodes. We prepared it by ironing the Ripstop to dual-sided fabric bonding. Then, using dual-sided scrapbook adhesive [START_REF] Runner® | Permanent Strips Refillable Value Pack -Scrapbook Adhesives by 3L[END_REF] we glue the ripstop to an MDF board (bonding glue side up). We insert the board with the ripstop into the laser-cutter and cut the pattern. Once we remove the MDF and ripstop from the laser cutter, we gently peel off all excess material from the board, so that only the electrodes remain glued to the board. We then place a second piece of textile -this time non-conductive -on top of the electrodes and iron it in place. Once the bonding has securely connected the electrodes to the non-conductive fabric, we pull both fabric layers off the MDF board.

This method allowed us to create more precise patterns, as we did not need to manually arrange the electrodes on fabric backing. We used piezo-resistive, non-woven fabric by Eeonyx (20kΩ per square) for our resistive layer (Figure 4).

Dimensions

We created 17 sensors. One sensor with no interdigitation, and 16 sensors with a 4*4 factorial design of width and length (digit length: 55%, 70%, 85%, 100% of strip spacing) and digit width: 95%, 75%, 55%, 35% of strip spacing). We chose our broadest digit (55% length, 95% width) to approximately match DIY designs and White Paper recommendations [START_REF]The world's most energy friendly microcontrollers Hardware Design for Capacitive Touch AN0040-Application Note[END_REF][START_REF] Semtech | Application note: capacitive touch sensing layout guidelines[END_REF]. Our sharpest digit was limited by our manufacturing ability. We only created a single side of each matrix. As our primary interest is to better understand transition behavior between sensing electrodes, the full matrix is not required.

Each sensor was ~160mm wide and consisted of 7 electrodes with a 25mm spacing between strip-centers (the first and last strip were truncated). We use both larger touch-sizes and larger strip widths than we typically use. The larger strip width allows us to evaluate designs which we currently could not manufacture at fingertip scale, the larger touch sizes means we maintain the expected ratio between 'finger' and sensing elements. We chose the sizes so that the 'small' touch-size approximates the size of a human fingertip.

DATA COLLECTION

We used a CNC machine [START_REF][END_REF] to ensure consistent touchbehavior in terms of pressure and location. We created modified Dremel bits that acted as 'fingers' that would press on the sensor. The 'fingers' were made of Sugru with a rubber disk (cut from a mouse-pad [START_REF] Runner® | Permanent Strips Refillable Value Pack -Scrapbook Adhesives by 3L[END_REF]) beneath them to approximate the softness of the human fingertip (Figure 5).

Each strip was sampled by an analog input of an Arduino Uno. We wrote a JavaScript controller that coordinates data logging and communicates between the CNC and Arduino.

The controller is open source and can be downloaded from the projects GitHub page. We used this controller to perform an approximation of a swipe gesture by measuring pressure at 70 consecutive locations on the sensor with 1mm spacing.

For each sensor we repeated this swipe gesture 11 times, with 2.5mm offset for a total of 770 points.

This was repeated for three touch sizes (50%, 100%, 150% of strip spacing) crossed with two pressure settings (strong/gentle), where 'strong' was set to take full advantage of the dynamic range of the sensor and 'gentle' was the lowest pressure level we could consistently detect. In total we collect 4620 touch events per sensor for a total of 78.540 touch events over all 17 sensors.

Assumptions and Limitations

We report independent variables and results in percent of strip spacing (25mm center to center) to support generalization to sensors and patterns of different sizes, and comparisons to previous evaluations [START_REF] Donneaud | Designing a Multi-Touch eTextile for Music Performances[END_REF]. Another relevant unit, however, is the ratio of touch size to strip width. We assume that (within limits) there is an equivalency in increasing the touch size by 100% to reducing strip size by 50%. The touch-size conditions can be either thought of as changing the size of touch area, or as changing size of stripwidth relative to a constant touch size.

Our application scenario is continuous control of audio or video content, so our primary goal is that the user's motion over the eTextile results in a corresponding change in output signal, without jumps or discontinuities.

The Data

We provide the raw log files as we recorded them, including various metadata. We also provide a 'normalized' version.

Here we removed the noise-floor, rescaled the strips so their dynamic range is from 0 to 1 and applied a low-pass filter.

All the modifications done to the 'normalized' data can be done in real time by an embedded system. For the rest of the paper we will be referring to the 'normalized' dataset.

ALGORITHM SELECTION

We chose eight algorithms for detecting touch-positions based on previous work on subpixel peak estimation [START_REF] Akhtar | A methodology for evaluating accuracy of capacitive touch sensing grid patterns[END_REF][START_REF] Fisher | A Comparison of Algorithms for Subpixel Peak Detection[END_REF] and precedent in eTextile matrix designs [START_REF] Donneaud | Designing a Multi-Touch eTextile for Music Performances[END_REF]. As a point of reference, we also add a 'naïve' estimator (NAIVE), which simply places the touch-position at the center of the strip with the highest pressure reading, as was used for gesture extraction by Schneegass et al. [START_REF] Schneegass | GestureSleeve: using touch sensitive fabrics for gestural input on the forearm for controlling smartwatches[END_REF].

We test five algorithms that fit a function through the strip with the highest pressure reading and its neighbors. These assume that there is a linear (LINE) [START_REF] Akhtar | A methodology for evaluating accuracy of capacitive touch sensing grid patterns[END_REF][START_REF] Fisher | A Comparison of Algorithms for Subpixel Peak Detection[END_REF], gaussian (GAUSS) [START_REF] Akhtar | A methodology for evaluating accuracy of capacitive touch sensing grid patterns[END_REF][START_REF] Fisher | A Comparison of Algorithms for Subpixel Peak Detection[END_REF][START_REF] Nobach | Two-dimensional Gaussian regression for sub-pixel displacement estimation in particle image velocimetry or particle position estimation in particle tracking velocimetry[END_REF], cubic (CUBIC) [START_REF] Donneaud | Designing a Multi-Touch eTextile for Music Performances[END_REF][START_REF] Borke | Interpolation methods[END_REF], or parabolic (PARA) [START_REF] Akhtar | A methodology for evaluating accuracy of capacitive touch sensing grid patterns[END_REF][START_REF] Fisher | A Comparison of Algorithms for Subpixel Peak Detection[END_REF] spread of pressure from the maximum pressure point.

Additionally we test a filtered version of the parabolic estimator, suggested by Blais and Rioux (B_R) [START_REF] Blais | Real-time numerical peak detector[END_REF][START_REF] Fisher | A Comparison of Algorithms for Subpixel Peak Detection[END_REF].

We test two geometric solutions: The mTouch algorithm by Microchip [START_REF]TB3064 -Datasheet[END_REF] which fits a centroid around the maximum pressure values and its neighbors (mTOUCH) and the center of mass (COM) for all strips as a touch-estimator. For our sensor these are equivalent to COM3 and COM7 suggested by Fisher and Naidu [START_REF] Fisher | A Comparison of Algorithms for Subpixel Peak Detection[END_REF].

These methods can further be combined with blob tracking:

The function fitting methods can be used to calculate the boundaries of the blob [START_REF] Jordan | Interpolating digital data processing apparatus for correlation-type flow measurement[END_REF], for example Donneaud et al. use bicubic interpolation to find the boundaries of blobs with greater accuracy [START_REF] Donneaud | Designing a Multi-Touch eTextile for Music Performances[END_REF]. The geometric methods can be used to improve the estimate of the blob center, for example Burstyn et al. detect blobs using the naïve approach, but estimate the touch-position within the blob using center of mass [START_REF] Burstyn | DisplaySkin[END_REF]. As these combinations also can be done at arbitrary threshold levels, testing them is beyond the scope of this exploration, however we believe our results can guide designers towards informed choices on reasonable combinations. We will refer to these algorithms as method from now on in the paper.

DATA ANALYSIS

Using the collected pressure values, we (1) compute the touch position for each measured position and each method.

The resulting positions are in units of strip-width. We (2) scale each sensor*method combination to match the expected range in mm. We then (3) calibrate the values by subtracting the y intercept of the regression line and multiplying each value by one minus the slope of the regression line (Figure 6). The resulting positions are in the correct range, with a regression line of y = x (blue). We then subtract the known position from the estimated position to find the error. This resulted in 36,960 error measures per sensor (770 positions by 8 methods, 3 touch sizes, 2 pressure levels) for a total of 628 320 error measures.

We investigate sensor accuracy, precision and consistency over pressure levels, using measures derived from this error measure. For sensor accuracy we need a measure that describes how far the estimated positions are from the known position, on average. We therefore analyze the absolute error (36,960 data points per sensor). For sensor precision we wish to know how consistent the output is between swipes (3360 data points per sensor). We therefore analyze the standard deviation at each x-position of all swipe motions. Finally, for sensor consistency we wish to know if the output behavior is consistent across pressure levels. We therefore analyze the correlation between the mean swipe positions at strong and at gentle pressure levels (24 points per sensor).

While the multiple swipe measures might suggest using a repeated measures ANOVA, the swipes are all performed by the same device, and the variability between them is negligible. This would reduce our degrees of freedom without reducing the error term. We therefore opt for univariate ANOVAs. Our sample size for sensor accuracy is very high, allowing us to detect significant effects, even if the effect size is very small. Precision and consistency use successively higher-level concepts, leading to smaller samples sizes. For the consistency measure the sample size is so too small for a full factorial analysis.

For accuracy we analyzed absolute error by digit width, digit height, touch size, pressure and method. All main effects and all interaction effects were statistically significant at the p < .0001 level.

Precision was analyzed using standard deviation by digit width, digit height, touch size, pressure and method. All main effects and all interactions, except for touch size * method and digit width * method, were significant at p<.0001.

For consistency we performed two separate ANOVAs once correlation by digit width and digit height and once on correlation by touch size and method. There were no significant effects for digit width or digit height. For touch size and method, all main effects and all interaction effects were statistically significant at the p < .0001 level.

Due to our large sample sizes for accuracy and precision, it is not surprising that we could demonstrate significant differences even for very small effects. We therefore also report effect sizes, which typically were small, except for the effect of method, which was medium. The effect size reported is partial eta squared -any variance explained by other variables is removed. This allows for easy comparisons between parameters when exploring other electrode design manipulations. It should be noted that eta measures typically overestimate effect sizes, but that we believe this to be negligible in our case due to the large sample sizes.

All significant results maintain the p <.0001 level after correcting for family wise error -we will from now on not report these. The F-statistics and effect sizes, as well as Bonferroni corrected post-hoc analysis, will be presented where relevant. We vary touch size, as it allows us to explore various touch size to strip width ratios. One can also assume the 50%, 100% and 150% touch sizes to represent strip widths of 200%, 100% and 66.6% finger size.

RESULTS

Pressure

Increasing the touch size had a positive effect on accuracy (F (2, 627504 = 1414.744, η p 2 = .004) and an even stronger effect on precision (F (2, 56304 = 583.094, η p 2 = .020). Bonferroni corrected post-hoc analysis showed that each successively larger size performed significantly better than the previous size for both accuracy and precision (Table 1).

The interactions between strip width and touch size lead to various periodic behaviors, and some sensors display the opposite trend as we find on average. Figure 7 shows the average change between consecutive pressure readings for all x positions of a swipe gesture on the non-interdigitated sensor. For the small touch position (top) there is always a sensor where values are changing, providing information that the touch-point has moved between readings. For the medium touch size (middle), the areas where change occurs begin to cluster and for the large touch size (bottom) they begin to completely overlap. Digit length is the dimension of the digit perpendicular to the strip. It has a significant effect on accuracy, however it is very small (F (3, 627504 = 308.705, η p 2 = .001). Digit Length of 55% had the lowest, and 100% had the highest average errors.

There is a proportionally much stronger interaction effect with touch-size (F (6, 627504 = 650.756, η p 2 = .006). Digit length causes the strips to overlap, effectively increasing their width. This changes the periodic effects described in the touch-size section. Figure 8 compares the digit lengths of the interdigitated sensors using the large touch size and 35% digit length. With increasing digit length, the 'dead zones' become increasingly smaller, until zones appear where changes can be detected two separate strips simultaneously.

Not all position estimation algorithms can fully leverage this though, which is reflected in an even stronger three way interaction between digit length, touch size and method (F(42, 627504 = 481.955, η p 2 = .008).

There is also a -comparatively -strong effect of digit length on precision (F (3, 56304 = 159.583, η p 2 = .008), post hoc tests show that all levels are different, but most notably the noninterdigitated sensor performs best.

Digit Width

Digit width is the dimension of the digit parallel to the strip and had the strongest effects on accuracy and precision of all physical parameters. Reducing the digit width has a positive effect on accuracy (F (3, 627504 = 564.239, η p 2 = .003) with all levels showing a significant difference to each other, except for the non-interdigitated sensor and 75% condition.

Reducing digit width has a strong positive effect on precision (F (3, 56304 = 848.321, η p 2 = .043). Large touch sizes seem to benefit most from this, which is also demonstrated by an interaction effect with touch size (F (6, 56304= 249.334, η p 2 = .026). Reducing the digit width can, on average reduce the error over a non-interdigitated sensor, however at the cost of precision. Reducing the width increases precision, the trend suggests digit widths <35% will match the precision of non-interdigitated sensors (Figure 9).

Method

One of the strongest effect found in our analysis was that of method on accuracy (F (7, 627504 = 31596.752, η p 2 = .261). This is most likely in part driven by the inclusion of the NAIVE estimator which produced on average more than triple the error of the two best algorithms. mTOUCH and LINE performed similarly well on accuracy and were significantly better than all others. We also found no significant difference between COM and CUBIC, but beside those all methods were significantly different (Figure 10).

We found small, but significant simple interaction effects with both digit width (F(21, 627504 = 63.642, η p 2 = .002) and digit length (F (21, 627504 = 95.596, η p 2 = .003). We also found comparatively strong interaction effects with touch size (F (14, 627504 = 281.349, η p 2 = .006), and a three way interaction with touch size and pressure (F (14, 627504 = 603.918, η p 2 = .013) as well as digit length and pressure (F (21, 627504 = 175.997, η p 2 = .006). This suggests that the interpolation methods do not perform equally on all sensors, and that there is even larger variation based on varying pressure and size of the touch. In general, curve fitting methods performed best with small touch-sizes and low pressure, while the geometric methods performed best for strong pressure and large touch.

Finally, there was also an effect of method on precision (F (7, 56304 = 98.828, η p 2 = .012). Here GAUSS dethrones mTOUCH as the best solution. LINE has become significantly worse than mTOUCH (Figure 10).

There was a significant effect of method on consistency (F (7, 384 = 15.257, η p 2 = .417). Post hoc tests showed that NAÏVE performed significantly worse than all others. CUBIC performed better than NAIVE but was also significantly worse than the remaining methods. There was also a significant interaction effect of method*touch size (F (14, 384 = 11.364, η p 2 = .293). This effect is, however, completely due to the NAIVE condition, which performed best with small and worst with large touch sizes.

DISCUSSION

Our analysis demonstrates that triangular interdigitation can improve the accuracy of eTextile pressure sensor matrices. We found that for all digit lengths, the accuracy is improved on average, but at the cost of precision. We found that wide digits performed worse than non-interdigitated sensors. The 55% digit width condition, however, already outperformed the non-interdigitated sensor in terms of accuracy and the 35% digit width condition was even significantly more accurate than both 55% and non-interdigitated, while approaching the non-interdigitated sensor in terms of precision. For the large touch size, the interdigitated designs outperformed the non-interdigitated designs at all levels of digit width and digit height for both accuracy and precision.

Regarding peak estimation method, we found that both the mTOUCH and the LINE algorithm performed significantly better than all others on accuracy. We speculate, however, that they might feel very differently. We believe that there is a certain subjective dimension to interpolation which should not be ignored. We draw an analogy to the effects of latency on musical input -if latency is consistent, it is perceived as a property of the feel of the instrument, but if the latency varies, it is perceived as negatively impacting the quality of the instrument [START_REF] Robert | Effect of latency on performer interaction and subjective quality assessment of a digital musical instrument[END_REF]. In our case it is not clear how relevant the average accuracy or even precision is, compared to the consistency and 'feel' of the errors. The LINE method, for example, has a distribution of errors which appears chaotic and somewhat difficult to predict compared to the mTOUCH method. The GAUSS method, on the other hand has relatively larger errors, but very good precision and consistency over pressure levels. The CUBIC method appears as a reasonable choice in terms of accuracy, however it performed significantly worse than all others in terms of precision. A visualization comparing interpolation methods for the non-interdigitated sensor and the 35% digit width, 100% digit height condition can be seen in Figure 11. The supplementary material includes these for all sensors.

While the mTOUCH method performed well on the clean data, anecdotally, we observed that the mTOUCH method led to periodic jumps when testing on the non-normalized dataset. In the normalized dataset this did not happen, presumably due to removing the noise-floor. The COM method did not display this problem.

An Excel sheet for exploring all combinations is attached in the supplementary material as well as our GitHub repository.

Recommendations

Overall, our data suggests using a digit length of 85%, digit width of 35% or smaller, touch size 150% (or strip size 66% of touch size) and either mTOUCH or LINE interpolation method. If the strip is wider than the touch size, then PARA is the preferred algorithm. Of all combinations tested, the combination which minimized errors and variance was 100% digit length, with 35% digit width, 150% touch size and using the mTOUCH method (see also Figure 11,right).

We suggest method and electrode design should match the application: For example, if one intends to build a footstep sensor for children, one might start with the assumption that a child's foot is 6cm wide and space electrodes 4cm apart (making the touch size 150%). To maximize accuracy, one might design the electrodes to minimize digit width and use 100% digit height and use mTOUCH method.

If one is building a music controller and values precision over accuracy, one might choose the GAUSS method to ensure consistent behavior. Assuming a fingertip is 15mm wide, the strip spacing should be ~10mm. As interdigitation reduces precision, one might choose not to use interdigitation and instead map the electrodes so the periodic errors can be easily understood -for example one strip per half tone. If one does not wish to sacrifice accuracy, one could consider adding small digits, e.g. 55% digit length while minimizing digit width. Additional resources for parameter choice can be found in the supplement and our GitHub repository.

Comparisons with the state of the art

Comparing the input fidelity of matrix pressure sensors is difficult, as details are often not reported, or design parameters and goals differ greatly. For example, RESi demonstrates a potentially high electrode density [START_REF] Parzer | RESi: A Highly Flexible, Pressure-Sensitive, Imperceptible Textile Interface Based on Resistive Yarns[END_REF] and the unMousePad [START_REF] Rosenberg | The UnMousePad -An Interpolating Multi-Touch Force-Sensing Input Pad[END_REF] even increases the resolution possible due to high density with physical interpolation. Our design goal is to maximize the sensing resolution independently of electrode density, as this simplifies the physical interface. We argue that a useful benchmark in comparing design choices is to compare errors relative to strip spacing, as this is less dependent on the circumstances of the specific implementation. The only papers we could find that provide an accuracy measure were by Rosenberg et al. [START_REF] Rosenberg | The UnMousePad -An Interpolating Multi-Touch Force-Sensing Input Pad[END_REF] and by Donneaud et al. [START_REF] Donneaud | Designing a Multi-Touch eTextile for Music Performances[END_REF], reporting an error of 4.89% and 6% respectively. Our best result (35% Digit Width, 100% Digit Length, gentle pressure, COM) almost doubles the accuracy of the eTextile Matrix by Donneaud with 3.09% and even improves on the relative error size of Rosenberg's unMousePad. The more consistent result achieved with the mTOUCH approach with the same physical sensor but averaging both gentle and strong pressure has a slightly larger average error at 3.875%, but still outperforms both Donneaud's and Rosenberg's designs.

Limitations and Future Work

The sensors we designed are flat, while many applications of fabric pressure matrices are not. Especially wearable solutions need to conform to the shape and movements of the body [START_REF] Freire | Designing eTextiles for the body: Shape, volume & motion[END_REF] which inevitably leads to artefacts and noise [START_REF] Heller | FabriTouch: Exploring Flexible Touch Input on Textiles[END_REF]. While any sensor design would be subject to such problems, and we therefore believe that our design recommendations still hold, it is possible that some algorithms perform better than others when subject to noise. Hybrid sensing has been suggested as a way to minimize such problems [START_REF] Strohmeier | zPatch: Hybrid resistive/capacitive etextile input[END_REF].

We maximized the pressure sensitive area of our sensors.

Other approaches, such as sensors using zebra-fabric [START_REF] Parzer | FlexTiles: A Flexible, Stretchable, Formable, Pressure-Sensitive, Tactile Input[END_REF] or pressure sensitive threads [START_REF] Parzer | RESi: A Highly Flexible, Pressure-Sensitive, Imperceptible Textile Interface Based on Resistive Yarns[END_REF], have zones that are not sensitive to pressure between electrodes. It is not clear how the tested algorithms perform under such conditions. While we encourage that such designs utilize interpolation, our work is aimed specifically at interdigitated sensors.

Our work points towards periodic interactions between the ratio of touch size and strip width and that of digit lengths (Figures 7 and8). Our data and the analysis by Donneaud et al. [START_REF] Donneaud | Designing a Multi-Touch eTextile for Music Performances[END_REF] suggest that this is a topic that deserves further exploration, for example by disrupting the periodic interactions through varying strip-widths. We created and share a prototype tool for testing electrode patterns which could be used to explore this. Additional work is however required to validate this tool using the dataset we provide.

Fisher and Naidu [START_REF] Fisher | A Comparison of Algorithms for Subpixel Peak Detection[END_REF] suggest reducing error by modelling the periodic effects. This would also be relevant to eTextile pressure matrices. All peak estimation methods tested by us assumed an underlying behavior of the signal distribution. As we do not believe any of the estimators we tested to be ideal, we suggest that future work either model the signal distribution of the piezo resistive material, or use parameter free approaches, such as Gaussian Processes [START_REF] Runner® | Permanent Strips Refillable Value Pack -Scrapbook Adhesives by 3L[END_REF]. Finally, to fully utilize interdigitation, we need better prototyping methods such as screen printing, etching, or in-situ polymerization.

CONCLUSION

This paper presents an exploration of factors influencing the design of eTextile sensor matrices. Using a combination of 100% digit length, 35% digit width, 150% touch size and the mTOUCH method we are able to achieve a relative sensing accuracy higher than reported for previous pressure sensor matrices, both textile and non-textile.

While we are pleased with this result, our work is primarily intended as a resource for designers of textile input devices. We therefore share our data-set for testing algorithms under various conditions, we provide an evaluation showing the importance of digit width, touch size and algorithm choice, and we share implementations of our algorithms as Processing functions. The supplementary material of this paper also contains visualizations of the errors and variability of errors for all sensors, all touch sizes and all pressure levels. All code, data and additional material can also be found at https://datapaulette.github.io/interdigitation/ Our investigation shows that currently the resolution at which the digits can be manufactures in textile limits the utility of interdigitated pressure matrix designs, however, our work also suggests that the approach is promising and that it is worthwhile investigating new methods for prototyping at high resolution in fabric.

Figure 1 -

 1 Figure 1 -a) Electrodes of two sensors used in this paper b) capacitive sliders by Rachel Freire c, d) electrode designs and circular slider by Kobakant e) electrode testing samples at Datapaulette

Figure 2 -

 2 Figure 2 -(left) 4 by 4 pressure matrix circuit. (Center) 16*16 pressure sensor matrix, and (right) raw data output [6].

Figure 3 -Figure 4 -

 34 Figure 3 -Screenshots of pattern generator, four patterns. Top: low Digit Width, bot: high Digit Width, left: low Digit Length, right: high Digit Length

Figure 5 -

 5 Figure 5 -CNC rig used for collecting data.

Figure 6 -

 6 Figure 6 -Data Processing steps

Figure 7 -

 7 Figure 7 -Average change between readings, per electrode. The graphs are normalized relative to the maximum recorded change per strip. Each color corresponds to an electrode.

Figure 8 -

 8 Figure 8 -Average change between readings. As digit length increases, the 'dead zones', where there is no information to infer change of position, gradually vanish.

Figure 9 -

 9 Figure 9 -Means and 95% confidence interval for effects of digit width on accuracy (top) and precision (bottom). The accuracy graph is zoomed in. Lower scores are better.

Figure 10 -

 10 Figure 10 -Means and 95% CIs for effects of interpolation method on accuracy (top) and precision (bottom). The precision graph is zoomed in. The confidence intervals for accuracy are too small to display (0.11% on average, all differences are significant). Lower scores are better.

Figure 11 -

 11 Figure 11 -Methods for non-interdigitated sensor (left) and 35% digit width with 100% digit height (right). X-axis shows the known position, y-axis shows the average deviation from that position. Blocks indicate the 95% confidence interval of the average at that position. (See our GitHub repository for more details)

Table 1 -Means and 95% confidence intervals for pressure

 1

			Lower	Upper		Lower	Upper
	Pressure	Error	Bound	Bound	Deviation	Bound	Bound
	Gentle	10.86%	10.84%	10.89%	5.48%	5.40%	5.56%
	Strong	11.63%	11.60%	11.66%	4.01%	3.94%	4.04%
	We found that on average that low pressure performed better
	than high pressure over all sensors for accuracy (F (1, 627504 =
	627504, η p 2 = .001). This effect, however, is dwarfed by the
	comparatively larger effect of pressure on precision
	(F (1, 56304 = 535.056, η p 2 = .009), where the strong pressure
	outperforms the gentle pressure. Increased accuracy of
	gentle touches comes at the cost of reduced precision.
	Touch Size
	Touch		Lower	Upper		Lower	Upper
	Size	Error	Bound	Bound	Deviation	Bound	Bound
	50%	11.96%	11.93%	12.00%	6.17%	6.17%	6.17%
	100%	11.50%	11.46%	11.53%	4.68%	4.68%	4.68%
	150%	10.28%	10.25%	10.32%	3.39%	3.39%	3.39%

Table 2 -Means and 95% confidence intervals for touch size

 2

Table 3 -Means and 95% confidence intervals for digit length

 3

ACKNOWLEDGEMENTS

This work was supported by the European Research Council, grant no. 648785, Labex SMART (ANR-11-LABX-65) and French state funds under reference ANR-11-IDEX-0004-02.


Raouf Kerkouche
email: raouf.kerkouche@inria.fr

Réda Alami

Raphaël Féraud

Nadège Varsier

Patrick Maillé
email: patrick.maille@imt.fr

˛reda Alami

Node-based optimization of LoRa transmissions with Multi-Armed Bandit algorithms

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Node-based optimization of LoRa transmissions with Multi-Armed Bandit algorithms

Raouf Kerkouche ‹ , Reda Alami ˛, Raphaël Féraud ˛, Nadège Varsier ˛, Patrick Maillé ' Abstract-The use of Low Power Wide Area Networks (LPWANs) is growing due to their advantages in terms of low cost, energy efficiency and range. Although LPWANs attract the interest of industry and network operators, it faces certain constraints related to energy consumption, network coverage and quality of service. In this paper we demonstrate the possibility to optimize the performance of the LoRaWAN (Long Range Wide Area Network) technology, one of the most widely used LPWAN technology. We suggest that nodes use light-weight learning methods, namely, multi-armed bandit algorithms, to select the communication parameters (spreading factor and emission power). Extensive simulations show that such learning methods allow to manage the trade-off between energy consumption and packet loss much better than an Adaptive Data Rate (ADR) algorithm adapting spreading factors and transmission powers on the basis of Signal to Interference and Noise Ratio (SINR) values.

I. INTRODUCTION

The interest of the industry towards the Low Power Wide Area Networks (LPWANs) is gradually increasing [START_REF] Petajajarvi | On the coverage of LPWANs: range evaluation and channel attenuation model for LoRa technology[END_REF]. Several technologies operating on license-free industrial, scientific and medical radio bands (868 MHz for Europe, 915 MHz for North America and 433 MHz band for Asia) are used by industrials; among those, the LoRaWAN technology is one of the most widely used.

The LoRaWAN network architecture is based on a star-ofstars topology with gateways forming a transparent bridge. These gateways relay messages between end-devices and a central network server in the backend. Nodes use a singlehop wireless connection to one or more gateways whereas gateways are connected to the network server using standard IP connections. Communications with end-point nodes are generally bi-directional, but it is also possible to support multicast operations [START_REF] Alliance | What is LoRaWAN?[END_REF]. Communications between enddevices and gateways are spread out over different frequency channels, using so-called spreading factors (SF) defined as the logarithmic ratio between the symbol rate (R s ) and the chip rate (R c ): SF " log 2 `Rc {R s ˘. Accordingly, selecting the data rate (or equivalently, the SF) can be seen as a tradeoff between communication range and message duration [START_REF] Adelantado | Understanding the limits of LoRaWAN[END_REF]. This possibility to manage data rates and power outputs for each end-device allows to maximize network capacity [START_REF] Alliance | What is LoRaWAN?[END_REF].

The LoRa spread spectrum modulation scheme defines six different spreading factors, SF7 (data rate of 50 kbps) to SF12 (data rate of 0.3 kbps). SF7 allows to send messages with a higher data rate and a reduced time on air but at a shorter distance than the others SFs and vice versa. Before sending a packet, each node also selects a transmission power between 2 dBm and 14 dBm in addition to selecting a spreading factor.

As any IoT technology, LoRa faces several constraints. One strict constraint is the optimization of energy consumption as the end-devices have generally limited energy resources. Another constraint is a limited duty cycle, preventing nodes from sending data too often in order to leave space for the other nodes.

LoRa can operate successfully at ranges exceeding 15 km in suburban settings, and more than 2 km in dense urban environments [START_REF] Electronics | Lorawan part 1: How to get 15 km wireless and 10-year battery life for IoT[END_REF]. However, it is necessary to choose an appropriate spreading factor, to have a compromise between data rate and network coverage in order to avoid high battery consumption or frequent packet loss. That is the possibility offered by the so-called Adaptive Data Rate (ADR) scheme [START_REF] Alliance | What is LoRaWAN?[END_REF], which is currently implemented in LoRa nodes.

Research to optimize time-on-air, receiver sensitivity, packet loss and energy has been conducted by combining game theory and auction-based algorithms [START_REF] Haghighi | Game theoretic and auction-based algorithms towards opportunistic communications in LPWA LoRa networks[END_REF]. The goal there is to choose the best transmission power without changing the allocated spreading factor; the global results are satisfactory, but in case of a change in transmission power requirements all estimations need to be performed again, implying a huge overhead. In [START_REF] Haghighi | Game theoretic and auction-based algorithms towards opportunistic communications in LPWA LoRa networks[END_REF], the authors design a multiradio testing instrument, called LoRabox, for sending and receiving data packets via LoRaWAN, Bluetooth Low Energy (BLE) and Wi-Fi, but this instrument does not have any mechanism to evaluate the cost associated with this overhead. Recently, an approach based on multi-armed bandits has been proposed to optimize the channel choice of end-devices in IoT networks [START_REF] Bonnefoi | Multiarmed bandit learning in iot networks: Learning helps even in nonstationary settings[END_REF]. The authors consider an hypothetical protocol where in each time slot the devices try to send packets to a unique Base Station. In the considered environment, half of the devices are static and the other half learns. Due to the learning of an half of devices, the environment is nonstationary. The reported performance of the stochastic multiarmed bandit algorithms are close to the ones of the optimal policy, which suggests that the environment evolves slowly and sparsely and that learning methods are good candidates to improve performance in those settings.

In this article, we aim to minimize the energy consumption and the packet losses of end-devices in a LoRa network. These objectives are conflicting, hence a trade-off between them has to be found by selecting the transmission power and the spreading factor. We propose to use multi-armed bandit algorithms, instead of the standard ADR algorithm, to handle that trade-off. In contrast to the ADR algorithmmanaged by the gateway-, the SF and power choices are left to each node, that learns and adapts to its environment with limited memory and computational costs. Our work departs from the recent study of [START_REF] Bonnefoi | Multiarmed bandit learning in iot networks: Learning helps even in nonstationary settings[END_REF], since instead of considering an hypothetical protocol, we test multi-armed bandit approaches on the actual LoRa protocols. The tested algorithms compete with the standard ADR algorithm: in our simulation setting, we consider that all devices select their transmission parameters using the ADR algorithm, except one that learns using a multi-armed bandit algorithm. This implies an a priori nonstationary environment (due to ADR having nodes change their parameters), which is likely to favor the non-stationary bandit algorithms over stationary ones.

The remainder of this paper is organized as follows. Section II analyzes the standard ADR algorithm and describes its functioning, while Section III provides an overview on multiarmed bandit problem and algorithms. In Section IV, we demonstrate how decision-making on LoRa parameters can be done by using multi-armed bandit algorithms. Section V describes our Lora network simulator; the experimental setup and simulation results are presented and discussed in Section VI. And finally, Section VII concludes by suggesting directions for future research.

II. THE ADR (ADAPTIVE DATA RATE) ALGORITHM

In order to limit the energy consumption while ensuring successful transmissions, the ADR algorithm, currently recommended by the LoRa Alliance, and implemented by the network, assigns the transmission power and the spreading factor to the nodes based on the packets received from them. Note that only the network may increase the data rate (i.e., decrease the SF) through ADR, while only nodes may decrease their data rate (i.e., increase their SF) during transmissions.

The algorithm is based on the Signal to Interference and Noise Ratio (SINR) of the last 20 transmissions. For each node, the last 20 Signal to Interference and Noise Ratio (SINR) values at the gateway are taken into account to calculate a so-called margin SINR, denoted by SINR margin . Formally, we have SINR margin :" SINR max ´SINR Required ´Margin, where:

' SINR max is the maximum SINR of the last 20 (successfully) received packets from the node, ' Margin is a constant set to 10 dB, ' and SINR Required depends on the spreading factor, as reported in Table I.

At each iteration of the ADR algorithm, the transmission power and the spreading factor are modified according to a value denoted by Nstep, which is defined as: Nstep :" roundpSINR margin {3q. Nstep corresponds to the number of steps to perform. If Nstep is negative (i.e., measured SINRs are low) then the transmission power is incremented by 3 dB until it reaches the maximum transmission power (14 dB), otherwise the spreading factor (SF) is decreased at each step. If the limit (SF7) is reached and there are still steps remaining, then the transmission power is decreased by 3 dB until the minimum transmission power (2 dB) is reached. Note that while the ADR algorithm rules seem intuitive (increase power or decrease data rate in case of low SINRs, and the opposite in case of large SINRs), they are heuristics, and not based on any explicit objective optimization. By contrast, this paper, we intend to optimize specific performance metrics by playing on the SF and power choice. We analyze the performance of ADR, but also of methods specifically designed to optimize metrics in an unknown environment, namely, the multi-armed bandit algorithms described in the next section.

III. MULTI-ARMED BANDITS: AN OVERVIEW

A. The Multi-Armed Bandit problem

The Multi-Armed Bandit problem handles the fundamental exploration-exploitation dilemma that appears in decision making problems facing partial information, where decisions have to be taken over time (discrete turns) and impact both the rewards and the information withdrawn. Specifically, a set of K arms is available to the decision maker (player). At each turn, he has to choose one arm and receives a reward corresponding to the played arm, ignoring what the received reward would have been, if he had played another arm. The player faces the dilemma of exploring, that is playing an arm whose mean reward is loosely estimated in order to build a better estimate, or exploiting, that is playing a seemingly best arm based on current estimates in order to maximize its cumulative reward. The accuracy of the player policy at a given time horizon is typically measured in terms of regret, that is the difference between the cumulative rewards of the player and the one that could have been acquired by a policy assumed to be optimal. The notion of optimality and hence the algorithms depend on the environment.

B. Stationary stochastic environment

The stationary multi-armed bandit problem assumes the rewards to be generated independently from constant and unknown distributions associated with each arm. For those contexts, the most commonly used algorithms are called UCB and Thompson Sampling (TS).UCB [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF] builds an Upper Confidence Bound for each arm, and chooses at each turn the one which achieves the highest current bound, thereby refining the bound for that arm. Thompson Sampling (TS) [START_REF] Thompson | On the likelihood that one unknown probability exceeds another in view of the evidence of two samples[END_REF] uses Bayesian tools, assuming a prior distribution of each arm. The posterior distribution is updated using at each time step the observed reward of the sampled arm. Under the assumption of stationarity (of the reward distributions), UCB and TS achieve respectively rate optimal and asymptotically optimal upper-bounds on the cumulative regret [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF], [START_REF] Kaufmann | Thompson sampling: An asymptotically optimal finite-time analysis[END_REF].

C. Switching stochastic environment

The switching bandit problem introduces non-stationarity within the stochastic bandit problem by allowing reward distributions to change at some turns. As expected rewards stay stationary between those changes, this setting is also qualified as piecewise-stationary. Discounted UCB [START_REF] Kocsis | Discounted UCB[END_REF] and sliding-window UCB [START_REF] Garivier | On upper-confidence bound policies for non-stationary bandit problems[END_REF] are adaptations of UCB to the switching bandit problem and achieve a near optimal regret bound. Recently, the Thompson Sampling algorithm has been combined with a Bayesian online change point detector for handling switching environments [START_REF] Mellor | Thompson sampling in switching environments with bayesian online change point detection[END_REF]. The Switching Thompson Sampling (STS) is based on the notion of expert. An expert is a Thompson Sampling starting at time t. At each time t, a new expert is introduced. To make a decision, the most likely expert is sampled according to the weight attributed to each expert. Then, the Thompson Sampling related to the chosen expert is launched to choose an arm. Finally, based on the reward observed, the weight of each expert is updated. One should notice that the update procedure takes as input a switching rate γ. In this paper, we also use a new algorithm called Switching Thompson Sampling with Bayesian Aggregation (STSBA) [START_REF] Alami | Switching Thompson sampling with Bayesian aggregation[END_REF], which is an updated version of STS where Bayesian aggregation of experts is used in place of sampling the best expert in order to avoid the sampling noise.

D. Adversarial environment

In the adversarial multi-armed bandit problem, rewards are chosen by an adversary. This formulation can model any form of non-stationarity. The EXP3 algorithm [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF] uses a follow-the-perturbed-leader approach [START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF] for computing the probability of each action. It achieves an optimal regret against an oblivious opponent that chooses rewards before the beginning of the game, with respect to the best policy that pulls the same arm over the totality of the game. This weakness is overcome by EXP3.S [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF], that forgets the past adding at each turn a proportion of the mean gain and achieves controlled regret with respect to policies that allow arm switches during the run. To compete against an optimal policy that changes over time, EXP3.R [START_REF] Allesiardo | EXP3 with drift detection for the switching bandit problem[END_REF] uses a statistical test to reset the EXP3 algorithm. REXP3 [START_REF] Besbes | Stochastic multi-armed-bandit problem with non-stationary rewards[END_REF] simply resets the EXP3 algorithm after a time period. A similar approach is used in [START_REF] Allesiardo | The non-stationary stochastic multi-armed bandit problem[END_REF] to reset a randomized version of the SUCCESSIVE ELIMINATION algorithm [START_REF] Even-Dar | Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems[END_REF].

IV. DECISION MAKING USING MULTI-ARMED BANDIT ALGORITHMS

The LoRa network currently uses ADR, a partially decentralized heuristic to tune the SF and transmission power of nodes. The values of these two parameters induce a tradeoff between energy consumption and packet losses. In this section we propose a cost function, which handles the tradeoff between energy consumption and packet losses. The objective of the multi-armed bandit algorithms is then to maximize the cumulated reward or equivalently to minimize the cumulated cost over time. This explicit minimization of the cost function is the main motivation for the use of multiarmed bandits, while ADR does not clearly state any objective function. Moreover, multi-armed bandit algorithms come with theoretical guarantees, which apply to the proposed cost function, and can be used for instance to provide guarantees on the lifetime of devices.

The arms correspond to a discretization of the parameter space, namely of the pair (transmission power,SF). We consider a limited number of possible pairs, each one corresponding to an arm (See Table II). This means that each time an arm is selected, the transmission power and the spreading factor are also selected. We are aware the choice of a limited number of arms can bias the results. Our selection is consistent with the spirit of ADR, that goes in the favor of transmission reliability: all SFs are associated to the maximum transmission power (arms 4 to 9), and when the highest data rate (SF7) can be applied, we reduce the energy consumption by reducing the power. Note however that we could select a larger set of arms, which could only improve performance in the long run (increasing the set of usable pairs) but would increase the learning time. Hence the choice of 9 arms, which offers a good trade-off between the variety of (transmission power,SF) options and the time needed to find the best one(s). The trade-off between energy consumption and packet losses is expressed through a cost metric, that is a weighted sum of the energy cost and a loss cost. Mathematically we define the cost perceived at each turn (i.e., each time the node wants to send a new packet) as:

Cost :" Energy ¨Nb_transmission `penalty ¨1pfailureq

(1) where:

' Energy is the energy cost for one packet emission, and equals the product of the emission duration (which depends on the SF) and the transmission power; ' Nb_transmission represents the number of transmissions to send the packet: it is an integer between 1

(the first emission is a success) and 8 (since there are a maximum of 7 retransmissions);

' 1pfailureq equals 1 if the 8 transmissions of the same packet fail, i.e., the packet is lost. It equals 0 otherwise. ' penalty corresponds to the conversion of a packet loss into the same cost unit as the energy cost. Its choice is specific to the application and to user preferences: a large penalty value means that a high quality of service is needed-for instance for healthcare applications-even if the energy cost is significant; by contrast a small value for the penalty corresponds to applications where the lifetime of the connected device is favored over having highly reliable transmissions. Since bandit algorithms function with rewards instead of costs, we first normalize cost values with respect to the largest possible cost (highest power and lowest data rate, and transmission failure after 8 emissions), to obtain normalized values Cost N in the interval p0, 1s, then we define the reward of each decision step as:

reward :" 1 ´Cost N . (2)

V. LORA TRANSMISSION MODEL AND SIMULATOR

We describe here the MATLAB realistic LoRa network simulator we use to perform capacity studies of the Lo-RaWAN technology [START_REF] Varsier | Capacity limits of LoRaWAN technology for smart metering applications[END_REF].

A. Collision rules

In telecommunications, the Received Signal Strength Indicator (RSSI) is a measurement of the power level of a received radio signal [START_REF] Sauter | From GSM to LTE: An Introduction to Mobile Networks and Mobile Broadband[END_REF]. The Signal-to-Interference-plus-Noise Ratio (SINR) is also an important metric of the wireless link quality [START_REF] Jeske | Signal-to-interference-plus-noise ratio estimation for wireless communication systems: Methods and analysis[END_REF], since it directly affects the bit error rate in the transmissions.

A collision occurs when two LoRa frames are received simultaneously. There are two types of collisions: Inter-SF collisions and Intra-SF collisions, which are modeled according to the two following rules [START_REF] Varsier | Capacity limits of LoRaWAN technology for smart metering applications[END_REF]:

' Intra-SF collisions: if a collision occurs between two LoRa frames with the same SF on the same frequency, then only the LoRa frame with the highest power can be decoded, and provided that the power difference exceeds 6 dB (otherwise it is lost). ' Inter-SF collisions: if a collision occurs on the same frequency between two LoRa frames "a" and "b" with different SFs, then packet "a" is demodulated only if: RSSI a ´RSSI b ą SINR a .

B. Propagation Model

We use the Okumura-Hata model [START_REF]Digital mobile radio towards future generation systems[END_REF], [START_REF] Hata | Empirical formula for propagation loss in land mobile radio services[END_REF] because it is one of the most popular and accurate models, especially used for urban and suburban areas. It is generally applied for frequencies in the range of 150 MHz-1920 MHz, for a distance separation ranging from 1 km to 100 km, and for antenna heights from 30 m to 1000 m [START_REF] Alumona | Path Loss Prediction of Wireless Mobile Communication for Urban Areas of Imo State, South-East Region of Nigeria at 910 MHz[END_REF]. We consider typical indoor penetration losses, with an additional 6 dB loss for deep indoor environments [START_REF] Varsier | Capacity limits of LoRaWAN technology for smart metering applications[END_REF], [START_REF] Ferreira | Characterisation of signal penetration into buildings for GSM and UMTS[END_REF], [START_REF] Rodriguez | Path loss validation for urban micro cell scenarios at 3.5 GHz compared to 1.9 GHz[END_REF].

C. Shadowing and Fast Fading modeling

Fading is the term used to describe the fluctuations in a received signal as a result of multipath components. We model it using a Rayleigh distribution for the amplitude, hence an exponential distribution on power.

Shadowing represents the fact that the received signal power fluctuates due to objects obstructing the propagation path between transmitter and receiver when fast fading is characterized by rapid fluctuations over very short distances. In our LoRa network simulator the shadowing effect is modeled through a log-normal distribution with a 12 dB standard deviation outdoor and 6 dB standard deviation for indoor applications [START_REF] Varsier | Capacity limits of LoRaWAN technology for smart metering applications[END_REF], [START_REF] Ganga Prasad | Analysis of fast fading in wireless communication channels[END_REF].

D. Data rate vs spreading factor

The data rate DR equals [START_REF]Guide d'utilisation v 1.2 transceiver 868mhz : 14/20dbm[END_REF]: DR " SF ¨BW 2 SF ¨CR, with: ' SF the spreading factor (an integer between 7 and 12), ' BW the bandwidth, ' and CR the coding rate.

E. Transmission and Retransmission

Following each uplink transmission the end-device opens two short receive windows in order to receive a downlink message from the server as acknowledgment of its uplink message. The receive window start times are defined using the end of the transmission as a reference [START_REF]LoRaWAN Specification[END_REF]. A node can receive a message only when one of these two windows is open. If no acknowledgment is received after closing the second window, then the message is retransmitted under certain conditions. Indeed, the number of retransmissions is limited, generally to a maximum of 7 retransmissions (what we consider in our simulator), but this number may differ depending on the end-devices. The duration of the reception window depends on the spreading factor (see Table I).

During retransmissions 3, 5, 7 (if any) the node increases its spreading factor (decreases the data rate) before sending the packet again. The rule used to increase the spreading factor is defined as: min `SF node `1, SF12 ˘. Both transmission and retransmission must respect the duty cycle, defined as the maximum percentage of time during which an end-device can occupy a channel and is a key constraint for networks operating in unlicensed bands. For instance, the duty-cycle is 1% in EU 868 for enddevices [START_REF] Adelantado | Understanding the limits of LoRaWAN[END_REF].

In addition to the cases of collisions seen above, a retransmission can occur if the gateway receives the frame with an RSSI strictly below the antenna sensitivity.

In all other cases, the transmission is assumed to succeed. Mathematically, the RSSI is computed as:

RSSI " tx power ¨Rayleigh power {PL

with Rayleigh power a random variable following an exponential law (with mean 1). PL represents the path loss predicted by the Okumura-Hata model and tx power is the transmission power. The sensitivity of the antenna depends on the spreading factor (see Table I).

VI. EXPERIMENTS

A. Simulation setup

For our MATLAB simulations, we consider that the network works in the LoRa European band 863-870 MHz, and we use the 868 MHz frequency channel. The frame size is 11 bytes (4 bytes of payload for the consumption index + 7 bytes Zigbee Cluster Library application protocol overhead [START_REF] Varsier | Capacity limits of LoRaWAN technology for smart metering applications[END_REF], [START_REF]Zigbee cluster library specification[END_REF]), corresponding to a smart metering application. Times on air for each SF are calculated using Semtech LoRaWAN specifications [START_REF]LoRaWAN Specification[END_REF] and are summarized below: Our simulations are for a network consisting of one gateway and 100 end-devices. In order to consider the worst case, devices are supposed to be located deep indoor.

The experiment runs over 1000 time slots of 30 minutes each. Each node sends one packet per time slot to the gateway. While respecting the duty cycle constraint, it can send it up to 8 times (i.e., 7 retransmissions) until receiving an acknowledgment from the gateway. We select a penalty of 1 for handling the trade-off between energy consumption and packet losses, and 9 arms corresponding to the 9 couples [spreading factor, transmission power] given in Table II.

We consider devices with a -5 dBi antenna gain, which corresponds to the reality of LoRa devices on the market [START_REF] Varsier | Capacity limits of LoRaWAN technology for smart metering applications[END_REF].

The first experiment considers a static setting, with a single node to be optimized at different distances from the gateway: 592 m, 1000 m and 1975 m, the 99 remaining nodes following the ADR algorithm. As the transmission between a node and the gateway may interfere with the transmissions of other nodes, the nodes are not independent. The changes of transmission parameters (due to ADR) of the other nodes can affect the distribution of rewards for the node of interest, hence an a priori non-stationary environment. In the second experiment, at time step 500 the node moves from 592 meters to 1975 meters from the gateway (immediate position switch, all other nodes remaining static). This moving node introduces a switch of the best arm (see Figure 1). We compare the simulated standard ADR algorithm with 7 different multi-armed bandit algorithms: UCB [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF] and Thompson Sampling (TS) [START_REF] Thompson | On the likelihood that one unknown probability exceeds another in view of the evidence of two samples[END_REF] designed for stationary environments, Sliding Window UCB (SWUCB) [START_REF] Garivier | On upper-confidence bound policies for non-stationary bandit problems[END_REF], Switching Thompson Sampling (STS) [START_REF] Mellor | Thompson sampling in switching environments with bayesian online change point detection[END_REF], and Switching Thompson Sampling with Bayesian Aggregation (STSBA) [START_REF] Alami | Switching Thompson sampling with Bayesian aggregation[END_REF] designed for switching environments, and EXP3 [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF], REXP3 [START_REF] Besbes | Stochastic multi-armed-bandit problem with non-stationary rewards[END_REF] for adversarial environments.

B. Simulation Results

Figure 2 shows the energy consumption, the number of lost packets, and the cumulative cost (averaged over 20 simulations) for a node at distance of 592 m, 1000 m, and 1975 m from the gateway, respectively, for different SF, tx power selection algorithms (ADR and various bandit algorithms).

The total cost value is defined as: ř t i"1 Cost N piq ,where t represents the current time slot, and Cost N piq the normalized cost at time slot i (See Section IV).

First, note that for all distances, the MAB algorithms have a total cost below that of the ADR algorithm (see Figure 2). Second, the ADR algorithm is dominated, both in terms of energy consumption and packet loss, by the multi-armed bandit algorithms whatever the distance of the node: hence for any penalty value (i.e., any application an user preferences) applying a MAB algorithm instead of ADR guarantees a cost reduction. Figure 2 shows that multi-armed bandits based on a switching environment clearly outperform adversarial bandits, and slightly outperform stationary bandits, which is an indication of the slow evolution of the environment.

When the node moves at step 500, a clear switch is introduced (see Figure 3). ADR, which does not handle mobile nodes is clearly dominated by multi-armed bandit algorithms. The best-performing multi-armed bandit algorithm is Switching Thompson Sampling with Bayesian Aggregation. Surprisingly, the Thompson Sampling algorithm performs as well as Sliding Window UCB and Switching Thompson Sampling, which are specifically designed for switching environments while TS is not. Adversarial algorithms explore too much to be competitive in this stochastic environment, and the UCB algorithm is the worst bandit algorithm in this non-stationary environment.

VII. CONCLUSIONS AND PERSPECTIVES

In this paper, we suggest to optimize the performance of uplink LoRaWAN communications by replacing the standard ADR algorithm with multi-armed bandit algorithms to select both the spreading factor and the transmission power. The experiments are carried out with a simulator that meets the standards of the LoRaWAN technology and are performed on nodes located at different distances from the gateway and located in a deep indoor environment.

Simulation results show that the ADR algorithm has a tendency to perform quite well in terms of energy consumption, but incurs large packet losses. All our experiments suggest that the multi-armed bandit algorithms outperform the ADR algorithm, and can be tuned to reach a compromise between energy consumption and packet loss.

As directions for future research, we plan to investigate the case of several gateways, that correlate their received signals to improve reception, as well as the interactions among multiple node selfishly optimizing their communications.

  air (s) 0.04 0.07 0.14 0.25 0.49 0.99

Fig.

  Fig.Average costs for the 9 arms, for three different distances from the gateway: depending on the distance of the node to the gateway, the best arm to play is not always the same.

Fig. 2 .

 2 Fig. 2. Simulation results: performance for the node of interest, at three distances from the gateway

Fig. 3 .

 3 Fig. 3. Total cost versus time averaged over 20 trials, when at time step 500 the node moves from 592 m to 1975 m from the gateway.

TABLE I SPREADING

 I FACTORS, AND CORRESPONDING RX WINDOWS[START_REF]LoRaWAN Specification[END_REF],ANTENNA SENSITIVITIES[START_REF] Varsier | Capacity limits of LoRaWAN technology for smart metering applications[END_REF], AND SINR Required[START_REF] Ghoslya | How does LoRaWAN Adaptive Data Rate work?[END_REF]

	SF	RX windows (ms)	Antenna	Required SINR
			sensitivity (in dBm) for ADR (in dB)
	SF7	5.1	-124	-7.5
	SF8	10.2	-127	-10
	SF9	20.5	-130	-12.5
	SF10	41.0	-133	-15
	SF11	81.9	-135	-17.5
	SF12	163.8	-137	-20