Jad Darrous
email: jad.darrous@inria.fr

Thomas Lambert
email: thomas.lambert@inria.fr

Shadi Ibrahim
email: shadi.ibrahim@inria.fr

On the Importance of Container Image Placement for Service Provisioning in the Edge

Keywords: Edge Computing, Services provisioning, Container Image, Placement

Edge computing promises to extend Clouds by moving computation close to data sources to facilitate shortrunning and low-latency applications and services. Providing fast and predictable service provisioning time presets a new and mounting challenge, as the scale of Edge-servers grows and the heterogeneity of networks between them increases. This paper is driven by a simple question: can we place container images across Edge-servers in such a way that an image can be retrieved to any Edge-server fast and in a predictable time. To this end, we present KCBP and KCBP-WC, two container image placement algorithms which aim to reduce the maximum retrieval time of container images. KCBP and KCBP-WC are based on k-Center optimization. However, KCBP-WC tries to avoid placing large layers of a container image on the same Edge-server. Evaluations using trace-driven simulations show that KCBP and KCBP-WC can be applied to various network configurations and reduce the maximum retrieval time of container images by 1.1x to 4x compared to state-of-the-art placements (i.e., Best-Fit and Random).

I. INTRODUCTION

Cloud computing has played a significant role in increasing the agility of web service deployment while minimizing the cost by leveraging the economy of scale. However, these centralized Cloud data-centers might not be a suitable deployment platform for every type of application. For example, latency sensitive applications should run physically close to the source of data (e.g., smart city applications) and data analysis on distributed data has to be done in place without moving the data to a central place for performance and privacy concern (i.e., video stream analysis). To overcome these limitations and provide new opportunities, a more distributed Cloud model has been emerging, named Edge computing [START_REF] Garcia Lopez | Edge-centric computing: Vision and challenges[END_REF]. Edge computing, promising to extend Clouds by moving computation close to data sources, has been successfully deployed and utilized in practice to facilitate short-running and low-latency applications and services. For instance, running smart city applications at the Edge shows to be up to 56% more efficient compared to Clouds [START_REF] Renart | Data-Driven Stream Processing at the Edge[END_REF].

In general, services are deployed as containers (a lightweight virtualization technology) in the Edge, therefore, container images are needed to run those services. However, unlike Clouds, where all container images are available locally, provisioning (deploying) a service in the Edge usually requires pulling the corresponding container image over the wide area network (WAN) from a central repository. This may result in long provisioning time; depending on the container images sizes and the network bandwidth [START_REF] Ahmed | Docker Container Deployment in Fog Computing Infrastructures[END_REF]. Usually, the bandwidth between Cloud and Edge-servers can be a few tens of Mb/s [START_REF]Akamai's state of the internet report[END_REF], hence, an image of a size of 1 GB needs at least 100 seconds to be transferred to the Edge-server if the bandwidth is 10 MB/s. This is unacceptable for most Edge services and applications, especially for short-running services and latency-sensitive applications. For example, we often scale-out live video stream analytics to handle data burst; thus, as the response time of those applications is in order of milliseconds, it is not acceptable to wait for hundreds of seconds to provision a new container.

As Edge-servers have limited storage capacity, storing all the images locally is not feasible, especially as the local storage should be exploited to store application data instead of container images. However, given that Edge-servers are featured with high network bandwidth among them compared to the bandwidth with Clouds (e.g., running distributed IoT application on a cluster of Edge-servers is 5.3x times faster than running it on Clouds [START_REF] Yi | Fog Computing: Platform and Applications[END_REF]); a possible solution is to distribute container images across Edge-servers, thus, the network bandwidth and available storage (a small fraction) can be exploited efficiently. Unlike most approaches in the Cloud, container image retrieval in Edge environments needs to be aware of the network heterogeneity between Edge-servers. Even worse, container images and layers are highly heterogeneous. As a result, the retrieval time will depend on the image sizes and the distribution of their layers (and the replicas: usually layers are replicated for performance and fault-tolerance); hence, it is hard to predict the retrieval time of a container image. In this paper, we argue that the initial placement is important for fast service provisioning in Edge environments. Moreover, a service can be provisioned on multiple Edgeservers and an Edge-server may host multiple applications (e.g., camera devices host multiple applications [START_REF]Real-time Video Analytics: the killer app for edge computing[END_REF]), therefore, it is essential to ensure predictable provisioning time as well. Our work tackles this problem (i.e., fast and predictable service provisioning in the Edge) by introducing novel placement algorithms that target reducing the maximum retrieval time of an image to any Edge-server. To the best of our knowledge, no previous studies have worked on container image placement in Edge environments or targeted reducing the maximum retrieval time of container images. Contributions. In an attempt to demonstrate the importance of container image placement across Edge-servers, in this paper, we propose and evaluate through simulation two novel container image placement algorithms based on k-Center optimization. In particular, we introduce a formal model to tackle down the problem of reducing the maximum retrieval time of container images, which we denote as MaxImageRetrieval-Time. Based on the model, we propose KCBP and KCBP-WC, two placement algorithms which target reducing the maximum retrieval time of container images to any Edge-server. While KCBP is based on a k-Center solver (i.e., placing k facilities on a set of nodes to minimize the distance from any node to the closet facility) which is applied on each layer and its replicas (taking into account the storage capacities of the nodes), KCBP-WC uses the same principle but it tries to avoid simultaneous downloads from the same node. More precisely, if two layers are part of the same image, then they cannot be placed on the same nodes. We have implemented our proposed algorithms alongside two other state-of-the-art placement algorithms (i.e., Best-Fit and Random) in a simulator written in Python. We simulate the behavior of the algorithms on realistic and synthetics networks with a dataset of container images from IBM production Cloud data-center [START_REF] Anwar | Improving Docker Registry Design Based on Production Workload Analysis[END_REF]. Simulation results show that the proposed algorithms can outperform state-ofthe-art algorithms by a factor of 1.1x to 4x depending on the characteristics of the networks. For example, on the Sanet network [START_REF]The internet topology zoo[END_REF], we reduce the retrieval time by 13% and 18% compared to Best-Fit and Random, respectively.

The remainder of this paper is organized as follows. First, Section II introduces Edge computing and container image management, followed by a state-of-the-art in Section III. Next, the problem alongside the proposed algorithms are formalized in Section IV. Simulation methodology is discussed in Section V. Then, the obtained results are presented in Section VI and discussed in more details in Section VII. Finally, Section VIII concludes this study.

II. BACKGROUND

A. Edge computing

The Edge is an extension to the Cloud that includes all the devices that are virtualized and placed on/near the data sources ranging from surveillance cameras [START_REF]Real-time Video Analytics: the killer app for edge computing[END_REF], to Cloudlet [START_REF] Satyanarayanan | The Case for VM-Based Cloudlets in Mobile Computing[END_REF] and micro data-center [START_REF] Bahl | Emergence of micro datacenter (cloudlets/edges) for mobile computing[END_REF]. As in traditional Cloud, those resources are leveraged by the users to run their services. Unlike Clouds, Edge-servers have limited computation and storage capacity. However, they are featured with high network bandwidth among them compared to the bandwidth to the Clouds. Hence, they can act as one cluster and serve a wide range of smart city applications [START_REF] Mohamed | SmartCityWare: A Service-Oriented Middleware for Cloud and Fog Enabled Smart City Services[END_REF]: despite the data exchange across Edge-servers, by eliminating the data transmission to Clouds, the response time of face recognition application can be reduced from 900ms to 169ms [START_REF] Yi | Fog Computing: Platform and Applications[END_REF].

B. Container Image management

Most services run in virtualized environments in both Clouds and Edge. While Virtual Machines (VMs) are widely used in Clouds; containers, being more lightweight in terms of provisioning times and image sizes, are often deployed in the Edge [START_REF] Ismail | Evaluation of Docker as Edge computing platform[END_REF], [START_REF] Liu | ParaDrop: Enabling Lightweight Multi-tenancy at the Network's Extreme Edge[END_REF]. Many container technologies have been developed recently such as LXC [START_REF]Linuxcontainers.org, infrastructure for container projects[END_REF] and Docker [START_REF]Docker homepage[END_REF]. Container images are structured as layers. Each image consists of an ordered set of layers that are stacked one on top of the other, and a manifest that maintains the layers of that image. Each layer is a collection of files that are stored as a gzip-compressed tar file. Layers could range in size from few Kilobytes to several Megabytes [START_REF] Anwar | Improving Docker Registry Design Based on Production Workload Analysis[END_REF]. The registry is the component responsible for container image management in the Docker ecosystem. It stores all the layers (from all the container images). Since the same layer could be shared by multiple container images, Docker registry uses layers level deduplication to reduce the size of stored data. Docker registry could be a remote online registry (e.g., Docker Hub [START_REF]Docker hub[END_REF]), a central private registry, or a local registry on the same machine of the Docker daemon.

III. RELATED WORK

Container image management. Slacker [START_REF] Harter | Slacker: Fast distribution with lazy docker containers[END_REF] uses chunks level deduplication to speed up container provisioning by transferring the accessed blocks on demands. This is motivated by the fact that just a small fraction of the image is needed to boot the container. However, dividing Docker images into chunks may break the layer structure among the layers and could bring integrity issues if these chunks are transferred over an insecure network. BitTorrent protocol has been used to distribute container layers in a single data-center setup [START_REF] Kangjin | FID: A Faster Image Distribution System for Docker Platform[END_REF]. It has been shown that a great reduction in provisioning time could be achieved when the same image is requested by a large number of machines simultaneously. However, for single image provisioning, no improvement can be achieved. Moreover, BitTorrent protocol does not guarantee a predictable performance.

Docker image placement and container provisioning have been studied in [START_REF] Nathan | CoMICon: A Co-Operative Management System for Docker Container Images[END_REF]. The authors in [START_REF] Nathan | CoMICon: A Co-Operative Management System for Docker Container Images[END_REF] propose a collaborative docker registry where the private registries on the cluster (compute) nodes can collaborate to store and retrieve docker images instead of relying on a central or remote registry. Also, the authors opt for layer placement rather than complete image placement to avoid redundancy in common layers. For layer placement, they employ simple heuristics by sorting the layers and the nodes Ascending/Descending. Bipartite graphs have been used to balance the retrieval of missing layers from multiple nodes. All the layers are 3-way replicated. While this work targets homogeneous and single cluster environments, this paper deals with heterogeneous network environments. In contrast to the aforementioned works, which focus on single data-center setup, in this study, we opt for fast and predictable image provisioning in Edge environments, where the network links between the Edge-servers are heterogeneous.

Virtual Machine Image (VMI) management. Most of the work on VMI management focuses on reducing the storage capacity required to store VMIs by leveraging deduplication [START_REF] Jin | The effectiveness of deduplication on virtual machine disk images[END_REF], [START_REF] Jayaram | An Empirical Analysis of Similarity in Virtual Machine Images[END_REF] and improving the provisioning time of VMs by exploiting the already available chunks of the host machine [START_REF] Reich | VMTorrent: Scalable P2P Virtual Machine Streaming[END_REF], [START_REF] Bazarbayev | Content-Based Scheduling of Virtual Machines (VMs) in the Cloud[END_REF], [START_REF] Xu | Rethink the storage of virtual machine images in clouds[END_REF]. Few studies have targeted geo-distributed VMI retrieval [START_REF] Karve | Redundancy Aware Virtual Disk Mobility for Cloud Computing[END_REF], [START_REF] Darrous | Nitro: Network-Aware Virtual Machine Image Management in Geo-Distributed Clouds[END_REF] where the goal is to minimize the transfer time of VMIs over a heterogeneous WAN. While all the aforementioned works target VMI management and focus on data retrieval, in this work, we investigate the importance of container image placement on the provisioning time.

IV. CONTAINER IMAGE PLACEMENT

In this section, we introduce the formal model we use to study the container image placement problem. We also introduce the two heuristics we propose to distribute a set of replicated layers through a network (across Edge-servers). In Section IV-A, we focus only on a set of individual layers and try to optimize the maximal retrieval time. In Section IV-B, we show how to extend the problem to a set of images (that are themselves sets of layers) and how to adapt our placement.

A. Layer Placement 1) Formal Model: For the moment, we focus on layers placement and put aside complete images. First, a layer l i is defined by its size s i (i.e., its storage cost) and its replication number n i (i.e., how many times a layer is replicated). We denote by L i = l 1 i , . . . , l ni i the replicas of l i . In the following, the complete set of layers is denoted as L and L R represents the set of replicas (L R = L i ).

In our model, the network is defined as a set of nodes V that are fully connected (thus a complete graph). We denote as c the storage capacity of all nodes (the allocated storage space on each node). For all the pairs of nodes u, v, we denote as b uv the bandwidth between these two nodes (if

u = v then b u,v = +∞).
Given a set of layers L, a set of nodes V and a storage capacity c, we define a placement as a function σ from L R to V (we want to place all replicas). A placement is said to be valid if for each u ∈ V , l k i ∈σ -1 (u) s i ≤ c (i.e., the sum of the sizes of stored replicas does not exceed the storage capacity) and for each k

, k ∈ [1, n i ], σ(l k i ) = σ(l k i ) (i.e.,

replicas of the same layer have to be placed on different nodes).

From a valid placement, we derive the retrieval time of a layer l i on a node u as follows. Let u σ i be the node owning a replica of l i that is the closest to u (i.e., with maximal bandwidth, formally u σ i = arg(max v∈σ(Li) b uv ). The retrieval time of l i on u is thus

T u i = si b uu σ i
. Our goal here is to minimize the maximal retrieval time for all layers on all nodes. We denote this problem MaxLayerRetrievalTime.

Problem 1 (MaxLayerRetrievalTime): Let V be a set of nodes with storage capacity c and L be a set of layers. Return a valid placement that minimizes: max u∈V, li∈L

T u i .
MaxLayerRetrievalTime is close to the k-Center problem, that aims to place facilities on a set of nodes to minimize the distance from any node to the closest facility. See below for a formal definition.

Problem 2 (k-Center): Given a set V with a distance function d (defined between all elements of V ), and a parameter k, return a set S ⊆ V such that |S| = k that minimizes:

max u∈V min v∈S d(u, v).
MaxLayerRetrievalTime is similar to the k-Center problem if considering only one layer. k-Center problem is known for being NP-complete [START_REF] Garey | Computers and intractability[END_REF] and thus MaxLayerRetrievalTime is also NP-complete. In addition, it has been proven that the best possible approximation is a 2-approximation (unless P=NP) [START_REF] Hsu | Easy and hard bottleneck location problems[END_REF].

The solution we introduce to solve MaxLayerRetrievalTime is based on a solver for k-Center. The basic principle of this heuristic, KCBP (k-Center-Based Placement), is to sort the layers in descending order by their sizes and then use this solver several times to place replicas, one layer after another. The distance used is the inverse of bandwidths. A pseudo-code of KCBP is provided in Algorithm 1.

For our implementation, we use SCR, a polynomial k-Center problem solver that was introduced by Robič and Mihelič [START_REF] Robič | Solving the k-center problem efficiently with a dominating set algorithm[END_REF]. SCR is based on a pruning technique (i.e., removing some edges and find a solution on the induced subgraph) and a Dominant Set problem solver (as the Dominant Set problem is also NP-complete, SCR relies on a heuristic). Note that SCR is a 2-approximation, but its experimental average approximation factor is far better and as far as we know the best among polynomial heuristics: 1.058 for SCR on a classical benchmark for graph partitioning [START_REF] Robič | Solving the k-center problem efficiently with a dominating set algorithm[END_REF].

The time complexity of SCR is O(m 2 log m), where m is the number of nodes. Hence, the overall complexity of KCBP is

O(|L||V | 2 log |V |). Algorithm 1: KCBP (L, V, c) Sort L by decreasing size ; foreach u ∈ V do c u = c ; foreach l i ∈ L do V = {u ∈ V, c u ≥ s i } ; S = Scr(V , n i ) ; k = 1 ; foreach u ∈ S do σ(l k i ) = u ; k + + ; c u ← c u -s i ; return σ B. Image Placement
MaxLayerRetrievalTime focuses on layers. However, we target the retrieval of complete container images.

1) Formal definition: We define an image as a set of layers I j = {l i1 , . . . , l iq }. The complete set of images is denoted as I. To retrieve an image I j , a node u has to download a replica of each layer that is in I j . As a first approximation, we could consider the downloads are done in parallel and thus the retrieval time is defined by the largest retrieval time among this different layers (as in MaxLayerRetrievalTime). However, multiple downloads from a same source may degrade the performance by reducing the bandwidth. Therefore, in our model, we consider that if a node requests an image that requires several layers where the closest replicas are on the same node, then the download of these replicas is made sequentially (that is equivalent to do it in parallel with shared bandwidth). More formally, given an image I j , a valid placement σ, and a node u ∈ V , let V σ u,Ij = {v ∈ V, l i ∈ I j and u σ i = v} the set of nodes that are the closest nodes to u for at least one replica of the layers of I j . The retrieval time of an image I j is thus:

T u Ij = max v∈V σ u,I j i,u σ i =v s i b uv .
We define now MaxImageRetrievalTime where the goal is to minimize the maximal retrieval time of a set of images.

Problem 3 (MaxImageRetrievalTime): Let V be a set of nodes with storage capacity c and I be a set of images. Return a valid placement that minimizes: max u∈V,Ij ∈I T u Ij .

2) Without-Conflict: If two layers are part of the same image, then their replicas should not be on the same nodes. However, applying this constraint to all layers can lead to a huge spreading of the replicas and even to a lack of eligible nodes (i.e., nodes with enough remaining storage capacities and have no conflicting layers). Thus, we limit the number of layers that are concerned. More precisely, we add a parameter f that is a percentage of the layers. If a layer l i is among the f % largest layers, then this layer cannot be placed on a node that already has a replica of a layer l i which belongs to the same image I j . We denote this algorithm KCBP-WC (KCBP-Without-Conflict) and a pseudo-code is provided in Algorithm 2.

C. Limitations

To simplify the scenario, we assume that there is a direct link between each pair of Edge-servers. Edge networks are more complex with more network components (switches, routers, etc) with complex and sometimes redundant paths between nodes. Software level approached as Traffic Engineering [START_REF] Hong | Achieving High Utilization with Software-driven WAN[END_REF] and Software-Defined Networking (SDN) [START_REF] Baktir | How Can Edge Computing Benefit from Software-Defined Networking: A Survey, Use Cases and Future Directions[END_REF] are widely employed to abstract the physical network topology from the application and ensure some network properties (e.g., bandwidth) between nodes. Hence, the general trend of the relative performance between the placement algorithm could be preserved. Note that the main goal of this work is to shed light on the importance of container image placement in the Edge. Moreover, we plan to address the problems of path sharing and the load variation of the network during the retrieval time (by introducing a network-aware layer retrieval approach, similar to [START_REF] Darrous | Nitro: Network-Aware Virtual Machine Image Management in Geo-Distributed Clouds[END_REF]).

Algorithm 2: KCBP-WC (I, L, V, c, f ) Sort L by decreasing size ; foreach u ∈ V do c u = c ; foreach l i ∈ L do V = {u ∈ V, c u ≥ s i } ; if l i is one of the f % largest layer then foreach I j ∈ I such that l i ∈ I j do V ← V \ {u ∈ V , ∃l i ∈ I j , σ(l k i ) = u} S = Scr(V , n i ) ; k = 1 ; foreach u ∈ S do σ(l k i ) = u ; k + + ; c u ← c u -s i ; return σ V. SIMULATION METHODOLOGY
We developed a simulator in Python to evaluate the performance of the two proposed placement algorithms on different networks and using real container images dataset.

Our simulator is written in Python and the source code is publicly available at https://gitlab.inria.fr/jdarrous/ image-placement-edge.

A. Network topology

We generate synthetic networks with different bandwidth characteristics and use real-world networks topologies for our evaluation. All the networks are described in Table I.

Synthetic networks. As we consider that network topologies have no interference, we generate complete graphs (i.e., there is a direct link between each pair of nodes) and then assign bandwidths to these links. Four distributions have been considered: [START_REF] Garcia Lopez | Edge-centric computing: Vision and challenges[END_REF] Homogeneous: where all the links have the same bandwidth. (2) Low: where the majority of the links have low bandwidth. (3) High: where the majority of the links have high bandwidth. (4) Uniform: where the links bandwidths follow a uniform distribution between 8Mbps and 8Gbps.

Real-world networks. In addition to synthetic networks, we choose two real-world networks to demonstrate the applicability of our algorithms. We select the national networks of France (Renater) and Slovakia (Sanet) [START_REF]The internet topology zoo[END_REF]. To compute the bandwidth between two nodes that are not directly connected, we do the following: suppose that n is the minimum number of nodes to reach one node from the other, and minb is equal to minimum bandwidth of the links that form the shortest unweighted path between these two nodes. Accordingly, the bandwidth between these two nodes is set to minb * 0.95 n .

B. Container images dataset

Container images and their corresponding layers are retrieved from publicly released IBM Cloud traces [START_REF] Anwar | Improving Docker Registry Design Based on Production Workload Analysis[END_REF]. We extract the images and layers from the traces of frankfort

C. Node storage capacity

For each network, we limit the nodes' capacities according to the total dataset size and number of nodes. First, the theoretical minimum node capacity that is needed to store all the layers (considering that the layers can be split at a byte level) is equal to the dataset size (with replication) divided by the number of nodes. However, this capacity will not satisfy any placement in practice as the integrity of the layers should be preserved. This can be achieved by storing only a complete layer on the same node. Therefore, we set the nodes' capacities as the theoretical minimum capacity multiplied by a capacity scaling factor. In our experiments, we test the following values for the capacity scaling factor: 1.1, 2, and IN F . We include IN F -which represents unlimited storage -just for comparison.

D. State-of-the-art placement algorithms

We compare our proposed algorithms with two placements algorithms: Random and Greedy (Best-Fit). These algorithms are not network-aware (i.e., they do not take into account links bandwidths). They serve as a comparison baseline.

1) Best-Fit placement: The Best-Fit placement is a greedy algorithm to place layers on nodes. The algorithm places the replicas of a layer l i on the n i nodes with the largest remaining storage capacity. The algorithm iterates over all the layers sorted by their decreasing size. As a result, Best-Fit distributes the layers evenly on the nodes in such a way that the nodes have almost the same total storage cost. When the layers have the same size, the behavior of Best-Fit will be like that of a round robin distribution. The algorithm is deterministic when the nodes initially presented in the same order, therefore, we shuffle the initial nodes ordering in every iteration to get a different placement.

2) Random placement: The Random placement serves as a very base solution. The algorithm distributes the layers randomly on the nodes. For each layer, we filter out the nodes that do not have sufficient storage space to host the layers, and then we select r random nodes to place the layer's replicas.

E. Methodology

For our experiments, we consider a default replication factor of 3 (as many storage systems [START_REF] Shvachko | The Hadoop Distributed File System[END_REF]) for each layer (n i = 3 for all i), therefore, the total dataset size with replication is 3 × 74.25GB. For KCBP-WC, we set the limit to define the "large" layers to 10%. For Best-Fit and Random placement algorithms, we run the placement 50 times and we draw the average retrieval times and the variation. KCBP and KCBP-WC are deterministic.

VI. SIMULATION RESULTS

In this section, we present the results of our simulations on the container images dataset presented earlier. We first focus on synthetic networks before considering real-world networks.

A. Results for Synthetic Networks

We would like to note that even though the retrieval times are presented in seconds, their relative values are more important than their absolute ones as the absolute retrieval time depends on the networks bandwidths. Similarly, for the synthetic networks, the distribution of link bandwidths is the important factor, not their actual values.

1) Homogeneous Network: All the links in the Homogeneous network have the same bandwidth, therefore, all the nodes have the same priority to place a layer in case of network connectivity. Fig. 2a shows the retrieval times of the placement algorithms when varying the capacity scaling factor. When the capacity scaling factor is set to 2, KCBP-WC has a maximum retrieval time of 1.97s, which is 1.8x faster than KCBP that needs 3.71s. With homogeneous link bandwidths, placing layers of the same image on the same node can prolong the retrieval time as in the case of KCBP. KCBP-WC handles this by distributing the layers of the same images. Moreover, as the bandwidths are homogeneous, we can notice that the performance of KCBP-WC is similar to Best-Fit and Random because the links bandwidths have no impact on the optimal placement. Best-Fit has the same maximum retrieval time of KCBP-WC (i.e., 1.97s), while the maximum retrieval time of Random is 2.05s.

2) Low Network: In this network, the majority of the nodes are not well connected, therefore, the placement of the layers (especially large ones) is critical for the retrieval performance. Best-Fit and Random experience a high variation in retrieval times and their best-found placements are still worse than that of KCBP-WC (Fig. 2b). For example, for a capacity scaling factor of 2, KCBP-WC achieves 7.85s while KCBP requires 10.09s. Best-Fit and Random have an average retrieval time of 23.15s and 26.63s, while their best retrieval times are 12.63s and 11.35s, respectively.

3) High Network: With High network, the majority of links have high bandwidths, which shows that there are many nodes that are well connected to the rest. In contrary to the Low network, the probability of placing a "large" layer on a low-connected node is smaller, and therefore, we notice a smaller variation in the performance for Best-Fit and Random. Moreover, Best-Fit and Random have better retrieval times than KCBP-WC in their best case. They achieve 1.34s and 1.36s, respectively, while KCBP-WC has a retrieval time of 1.50s in case of capacity scaling factor of 2. Fig. 2c depicts the results.

4) Uniform Network: The Uniform Network (Fig. 2d) shows a similar trend to the Low network as both networks have a high percentage of low-bandwidth links and therefore low-connected nodes. We can notice that Best-Fit and Random exhibit high variation and KCBP-WC has better retrieval time even compared to their best case.

B. Results for Real-world Networks

1) Renater Network: Renater Network exhibits only small variations for links bandwidths, therefore, it shows similar behavior to Homogeneous network. For example, as we can see in Fig. 4a, for a capacity scaling factor of 2 KCBP-WC has a maximum retrieval time of 59s while KCBP achieve 111s, that is more or less the ratio expected according to previous results on homogeneous bandwidth. However, even if the bandwidths are more or less homogeneous, the existing small variations result in differences between the performance of KCBP-WC and the ones of Best-Fit and Best-Fit has a maximum retrieval time of 72s, which is 22% worse than KCBP-WC.

2) Sanet Network: With Sanet network, the majority of links have high bandwidth (the bandwidths of 75% of the links are higher than 6 Gbps). Thus the results are close to that of High network. However, contrary to the High network, in this setup, KCBP performs better with increasing nodes capacities. For example, it achieves 96s, 42s, and 2.3s for 1.1, 2, and INF capacity scaling factor, respectively (Fig. 4b). The main difference between Sanet and High network is the number of nodes (i.e., 35 against 50). Thus, the chance of placing some layers on low-connected nodes with KCBP-WC increases as does the retrieval time (85s for capacity scaling factor of 2). In such a case, pulling more than one layer from the same node is better than having a layer on a low-connected node.

VII. DISCUSSION

In this section, we discuss the previous results and highlight our findings. We focus on five aspects: conflicts, heterogeneity of the bandwidth, storage capacity, percentage of layers considered as large for KCBP-WC, and maximal retrieval time per image.

A. Impact of conflicts

In Fig. 6, we provide the maximum retrieval time for layers instead of images in order to evaluate the impact of conflict. As expected all strategies are not impacted the same way. For example, KCBP doubles its retrieval time when images are considered instead of individual layers on the High network (Fig. 2c and Fig. 6b). However, for KCBP-WC, the impact is small (more obvious with INF capacity) as the algorithm avoids as much as possible putting layers of the same image on the same node. In the case of Random and Best-Fit, as they tend to produce close to even distribution of layers on nodes, the probability of having more than one "large" layer on the same node is less than the case of KCBP and KCBP-WC, thus, conflicts between large layers are rare.

Thus, in general, avoiding conflict is an important factor to consider while placing replicas.

B. Impact of the heterogeneity of the bandwidth

As expected, having nodes with different connectivity change the behavior of the placement strategies. Here, bandwidth-aware strategies are able to deal more efficiently with this heterogeneity, even when it is small (as in case of Renater network). However, we note some important differences between High and Low networks. In the first case, the difference in retrieval times between KCBP-WC and average values of Best-Fit or Random is small, and the variation in the performances of the last two is rather low. For Low network, this variation greatly increases as does the average performance. In this case, the performance of KCBP is even close to KCBP-WC. However, this does not apply to High network. Hence, it seems that centrality of layers is more important for Low network than for High network. In the first case, it is important to target a few nodes with high connectivity while in the second it is important to avoid the few nodes with low connectivity (at least for the largest layers). Thus, in Low network, KCBP compensates the conflicts with a general good connectivity in comparison to the other node, while in High network, the node used by KCBP are not that much better than the average ones. At the same time, it is easier for Best-Fit and Random to avoid few low connectivity nodes than to reach the few high connectivity ones. KCBP-WC is able to manage both situations when the number of nodes is sufficient, otherwise, as in Sanet, it may suffer from the spreading of the layers, as Best-Fit and Random do. Note that in Uniform network, where bandwidths differ significantly, KCBP-WC and KCBP perform well, even against the best results from Best-Fit and Random for KCBP-WC.

C. The extra space effect

A phenomenon that is interesting to point out is the fact that the performances of KCBP and KCBP-WC can be improved by decreasing the node capacity. For example, this effect is visible for KCBP-WC on the Homogeneous network, and for KCBP on all the networks. The reason for this phenomenon is that several layers of the same image are more likely to be placed on the same node (and thus retrieved from the same node) when the node capacity is larger. As explained earlier, we proposed KCBP-WC to avoid such placements that are common with KCBP. However, in order to avoid having layers dispersed on too many nodes (or not being able to place all layers), we only apply this strategy on "large" layers, implying that, in some cases, the placement of layers of the same image still happens and thus slightly decreases the performances.

D. Impact of the percentage of layers concerned by KCBP-WC mechanism

Increasing the percentage of layers considered as "large" in KCBP-WC leads to a diminution of conflicts that should result in decreasing the retrieval time. However, it may also spread layers on nodes with low connectivity, leading to potentially longer retrieval times for some layers (and thus images). The extreme case is when there are no remaining nodes with enough storage capacity. As a result, KCBP-WC does not return a valid placement. This was the case on Sanet network which has only a small number of nodes (Fig. 4b). When testing different values for this percentage (5%, 10%, and 20%) as shown in Fig. 5, we observe almost no difference between them, except that with 20%. Moreover, the algorithm does not succeed to find a solution when the capacity factor is 1.1 on Homogeneous network.

We can not give a general conclusion from this result, as it is strongly correlated with the container images dataset, but it appears here that avoiding conflicts between only the largest layers is enough and expanding this policy to smaller layer offer no clear gain.

E. Maximal retrieval time per image

In this subsection, we discuss the maximal retrieval time per image (i.e., the maximal time to retrieve an image to any node). The cumulative distribution functions (CDFs) are presented in Fig. 7 for synthetic networks and capacity scaling factor of 2. We notice that the performances are close for all strategies in case of Homogeneous and High networks (Fig. 7a and Fig. 7c), with Best-Fit performing slightly better for a portion of images (i.e., around 20% of the images on High network). On such networks, the overall good quality of links does not favor strategies that aim to spread as little as possible the different replicas, as pointed out earlier when evaluating the impact of bandwidth heterogeneity. In addition, KCBP and KCBP-WC favor the largest layers, that may slightly degrade performances for images with smaller layers. Combined together, these two reasons fully explain these results in comparison to the overall equal distribution of layers among the nodes proposed by Best-Fit (even if the difference is not that important). However, for Low and Uniform networks (Fig. 7b and Fig. 7d) the trends are different. In these networks, centrality is important and thus KCBP and KCBP-WC perform well, even when we are considering other images than the ones with maximal retrieval times. More precisely, KCBP and KCBP-WC present better maximal retrieval times for 20% of the images (images with longest retrieval time), with a small advantage for KCBP-WC that also performs better for other images. On Uniform network, KCBP outperforms all other strategies, at the exception of KCBP-WC that has finally a better overall maximum retrieval time (Fig. 2d).

From these distribution functions, we observe that although KCBP and KCBP-WC mainly target large layers (and the images they belong to), their performances are "good enough" compared to Best-Fit, when considering all images. Note that, Best-Fit can propose better retrieval times for intermediate images when network bandwidth is overall high. In a network with lower connectivity, the centralization of layers we propose with KCBP and KCBP-WC allows general improvement of maximal retrieval time for images.

VIII. CONCLUSION

Images management in Edge, especially container images, is gaining more importance with the widespread of Edgeservers. In this work, we propose to store the images across these Edge-servers, in a way that the missing layers of an image could be retrieved from nearby Edge-servers. The main goal behind this approach is to ensure predictable and reduced service provisioning time. To this end, we have proposed two image placement algorithms based on k-Center optimization to reduce the maximum retrieval time for an image to any Edgeserver. Through extensive simulation, using synthetic and realistic networks with production container images dataset, we have shown that our proposed algorithm can reduce the maximum provisioning time by 1.1x to 4x compared to Random and Best-Fit based placements.

In considering future work, we plan to implement our solution in Docker and test its applicability on a real testbed. In addition, we will investigate how to address path sharing and the load variation of the network when retrieving a single and multiple container images.

Fig. 1 .

 1 Fig. 1. The characteristics of layers.

Fig. 2 .

 2 Fig. 2. Retrieval time for Synthetic networks.

Fig. 3 .Fig. 4 .

 34 Fig. 3. Retrieval time for Synthetic networks where the best obtained solution is shown for Best-Fit and Random.

Fig. 5 .

 5 Fig. 5. Retrieval time for KCBP-WC algorithm with different values for the f parameter on Synthetic networks.

Fig. 6 .

 6 Fig. 6. Retrieval time of individual Layers for Synthetic networks.

Fig. 7 .

 7 Fig. 7. CDF of maximal retrieval time per image with storage capacity scaling factor of 2.

TABLE II THE

 II CHARACTERISTICS OF THE CONSIDERED IMAGES DATASET.

ACKNOWLEDGMENT

This work is supported by the Inria Project Lab program Discovery (see http://beyondtheclouds.github.io), the Stack/Apollo connect talent project, and the ANR KerStream project (ANR-16-CE25-0014-01).


Guillaume Vailland

Fabien Grzeskowiak

Louise Devigne

Yoren Gaffary

Bastien Fraudet

Émilie Leblong

Florian Nouviale

Ronan Le Breton

Sylvain Guégan

Valérie Gouranton

Bruno Arnaldi

Marie Babel

User-centered design of a multisensory power wheelchair simulator: towards training and rehabilitation applications

Autonomy and social inclusion can reveal themselves everyday challenges for people experiencing mobility impairments. These people can benefit from technical aids such as power wheelchairs to access mobility and overcome social exclusion. However, power wheelchair driving is a challenging task which requires good visual, cognitive and visuo-spatial abilities. Besides, a power wheelchair can cause material damage or represent a danger of injury for others or oneself if not operated safely. Therefore, training and repeated practice are mandatory to acquire safe driving skills to obtain power wheelchair prescription from therapists. However, conventional training programs may reveal themselves insufficient for some people with severe impairments. In this context, Virtual Reality offers the opportunity to design innovative learning and training programs while providing realistic wheelchair driving experience within a virtual environment. In line with this, we propose a user-centered design of a multisensory power wheelchair simulator. This simulator addresses classical virtual experience drawbacks such as cybersickness and sense of presence by combining 3D visual rendering, haptic feedback and motion cues. It relies on a modular and versatile workflow enabling not only easy interfacing with any virtual display, but also with any user interface such as wheelchair controllers or feedback devices. This paper presents the design of the first implementation as well as its first commissioning through pretests. The first setup achieves consistent and realistic behavior.

I. INTRODUCTION

People with disability may struggle to drive a power wheelchair because of altered perception skills. It has been shown that good visuo-spatial and cognitive abilities are necessary to achieve safe power wheelchair driving [START_REF] Massengale | Effect of visual perception, visual function, cognition, and personality on power wheelchair use in adults[END_REF]. While training and repeated practice through occupational therapy sessions can be satisfactory for some people to master their wheelchair, this conventional training may be insufficient for others.

Some people may need training in specific situations such as driving in a urban environments or crowded places. However, such training set-ups raise safety issues and are difficult to carry out. Moreover, a lack of situation-specific training could lead to hazardous driving [START_REF] Simpson | Smart wheelchairs: A literature review[END_REF]. As a consequence, therapists can decide not to prescribe a power wheelchair for safety concerns (e.g. driving behavior is above a subjective risk level) [START_REF] Mortenson | Prescribers ' Experiences With Powered Mobility Prescription Among Older Adults[END_REF].

In this context, wheelchair driving simulation can provide an additional training tool. Indeed, the beneficial effects Fig. 1: The Power Wheelchair Simulator (PWS): motion platform and 3D scene displayed through HMD for an immersive experience in Rennes city of training in simulation have been long recognized in applications such as aviation with flight simulators to train pilots [START_REF] Hays | Flight simulator training effectiveness: A meta-analysis[END_REF]. Navigational skills acquired thanks to training in simulation have also been demonstrated to positively transfer into real situations for military training [START_REF] Loftin | Training in peacekeeping operations using virtual environments[END_REF] or more recently for car driving training [START_REF] Hirsch | Pilot project to validate the transfer of training of driving skills learned on a high fidelity driving simulator to on-road driving[END_REF]. Moreover, simulation allows safe wheelchair navigation within controlled and repeatable scenarios [START_REF] Abellard | Electric wheelchair navigation simulators: why, when, how?[END_REF].

Virtual Reality (VR) is one way of simulating ecological situations with daily-life scenarios which are hardly reproducible in a real world. While VR appears to be efficient and largely used in training programs [START_REF] Inman | VR Education and Rehabilitation[END_REF] and rehabilitation [START_REF] Howard | A meta-analysis and systematic literature review of virtual reality rehabilitation programs[END_REF], it is also been shown as being safe, easy to use, and contributing to high patient satisfaction [START_REF] Dascal | Virtual Reality and Medical Inpatients: A Systematic Review of Randomized, Controlled Trials[END_REF]. In addition, VR allows therapists to achieve abilities assessment while reducing time, cost or safety constraints [START_REF] Ogourtsova | Ecological Virtual Reality Evaluation of Neglect Symptoms (EVENS): Effects of Virtual Scene Complexity in the Assessment of Poststroke Unilateral Spatial Neglect[END_REF]. Besides, a recent study highlighted that VR can increase user excitement and motivation while performing a task in the virtual environment [START_REF] Howard | A meta-analysis and systematic literature review of virtual reality rehabilitation programs[END_REF]. In the particular case of wheelchair driving, it has been shown that people with visuo-spatial and cognitive impairments may experience reduced motivation while driving a wheelchair [START_REF] Cawood | Impact of post-stroke impairments on activities and participation as experienced by stroke survivors in a Western Cape setting[END_REF]. VR could therefore reveal itself a more motivating tool for people with neurological disorders within wheelchair-related training programs.

A recent review on VR-based wheelchair simulators identified 29 wheelchair simulator projects of which 20 tackle power wheelchair simulation [START_REF] Arlati | Virtual reality-based wheelchair simulators: A scoping review[END_REF]. This review particularly highlighted the discrepancy among the proposed simulators. On the one hand, they differ in their designs and configuration setups. On the other hand, they differ in terms of assessment methodology and training programs, as most of the simulators were initially designed for driving training applications.

Two types of simulators can be identified in the literature. The first type of simulators incorporates a mechanical platform providing haptic and/or motion cues. For example, the Virtual Fauteuil simulator consists of a platform made of 4 actuators and a roller to reproduce manual wheelchair motion sensations [START_REF] Pouvrasseau | Discussion about functionalities of the Virtual Fauteuil simulator for wheelchair training environment[END_REF]. Besides its focus on manual wheelchair simulation, the purpose of the simulator is to assess spatial planning and does not match clinical assessment requirement. The other type of simulators such that miWe [START_REF] Archambault | Development and user validation of driving tasks for a power wheelchair simulator[END_REF] and ViEW [START_REF] Morere | ViEW, a wheelchair simulator for driving analysis[END_REF] relies on driving scenario simulation displayed on a single screen and focus on the assessment of driving simulation impact on patients through learning and training programs. Despite the lack of haptic or motion cues, they have shown benefits on training.

Sense of Presence (SoP), defined as user's sense of "being there" in the simulation [START_REF] Slater | A framework for immersive virtual environments (FIVE): Speculations on the role of presence in virtual environments[END_REF], has been shown to be a key-element for training performance [START_REF] Stevens | The relationship between presence and performance in virtual simulation training[END_REF]. Most VR-based simulators use 3D visual displays such as Head Mounted Devices (HMD) or immersive rooms to increase SoP. Some of the existing VR-based wheelchair driving simulators try to reach a higher SoP level by providing haptic feedback and/or motion cues in addition to the visual feedback. The major drawback of these simulators is that they are not compliant with clinical and user requirements and needs. Indeed, while the choice of the visual display should be adapted to user needs, they often rely on a specific visual display technology. Moreover, they do not provide easy transfer and adapted seating as they do not incorporate wheelchair standard components.

We propose a multi-sensory Power Wheelchair Simulator (PWS) designed in close collaboration with occupational therapists and wheelchair users. The proposed simulator includes a platform providing visual, auditory, and haptic feedback as well as motion cues. The proposed modular design allows to easily interface with any visual display (e.g. HMD, immersive rooms, single screen). It also allows easy integration of add-ons and configuration tuning to match individual user needs. The proposed PWS aims to provide realistic wheelchair driving experience for training and skill transfer to real-life situations. This project is conducted by our multi-disciplinary team in Rennes gathering multiple research centers as INSA Rennes, Inria, IRISA and the Pôle Saint Hélier rehabilitation center. Thanks to this skill plurality, all our design choices have benefited from qualified experts' experience. In particular, computer and mechanical scientists worked closely with the clinical staff to better match therapists and wheelchair user needs and constraints.

This paper is organized as follows. Section II introduces the requirements that our proposed PWS must fulfill. Section III presents the design of our proposed PWS. Section IV details the implementation of our first PWS setup.

II. SIMULATOR REQUIREMENTS

We propose a multisensory PWS design providing visual, auditory, haptic feedback and motion cue. This simulator aims to serve wheelchair driving training and clinical rehabilitation purposes. The simulator design is subject to constraints deduced from targeted user requirements but also from the VR technology itself.

A. Targeted users requirements

In order for the proposed PWS to be efficiently designed, end-user expertise must be considered. End-user needs were formulated thanks to therapists and patients from the Pôle Saint Hélier Physical Medicine and Rehabilitation center. This section therefore presents the constraints based on the recommendations of occupational therapists, physiotherapists, and neurologists but also and above all wheelchair users.

1) Seating and form factor: Considering the complexity of postural condition associated with some mobility impairments, a wide range of seating adjustments is needed. To avoid improperly fitted seating or positioning, the seating should be adjustable and dynamic, allowing for tilt and recline. Besides, a wide range of postural supports must be available on the seat based on the specific user needs, disability type, and postural condition. Moreover, the seat should include add-ons such as lateral trunk supports, hip guides, head rest, lateral thigh supports, armrests, and abduction block. A belt should also be used properly to secure participant positioning during simulation. Proper seating also requires footrests. The platform seat width and height must also be compliant to average wheelchair standards. Platform width must not be significantly larger than the seat width so it can be assimilated as a power wheelchair-like platform by its users.

2) Controller: The plurality of mobility impairments also implies a need for a wide range of control input adjustments, from proportional controllers (e.g. joysticks, chin controls) to discrete controllers (e.g. head array, sip-and-puff). Moreover, various input adaptations should be available for people with low upper limb strength or grasping difficulties (e.g. T-bar handle, U-bar handle, foam ball).

3) From power wheelchair to PWS kinematics: The objective is to provide a virtual driving experience similar to the one obtained with a power wheelchair. Therefore the simulator behavior has to accurately reproduce the dynamic behavior of a power wheelchair. Hence, we have identified the major kinematics parameters of power wheelchair motion (Fig. 2), e.g. the values of accelerations felt by a user (Table I).

These values have been experimentally obtained thanks to a set of driving scenarios representing classical indoor and outdoor use cases. In particular, these scenarios included curb and ramp climbing, navigation on rough surfaces, door passing... The collected values correspond to a natural and safe navigation of a regular wheelchair user, and serve as reference. Dynamics occurring to accidental events, such as collisions and bumps, must not be fully reproduced by the motion feedback in order to alleviate the risks for users. These particular situations should be addressed through haptic and auditory feedback. The PWS should replicate these features.

4) Virtual experience:

The visual display technology depends on each user specific needs. Therefore a simulator should not be dependent on a specific display device or technology and has to be compliant with various immersive visual displays such as HMDs and immersive rooms.

B. VR technology requirements

VR refers to a set of computer-based techniques aiming to simulate a 3D Virtual Environment (VE). As the proposed PWS relies on VR technology, VR-related constraints such as SoP and cybersickness must also be considered for our PWS design.

1) Sense of Presence (SoP): The SoP is a subjective phenomenon that has been defined in [START_REF] Slater | A framework for immersive virtual environments (FIVE): Speculations on the role of presence in virtual environments[END_REF] as user's sense of "being there" in the simulation. It depends on various factors such as immersion, social interactions and 3D scene components (e.g. objects, avatars) behavior. The greater the SoP, the more realistically the user will behave. In that regard, SoP is a critical factor that our PWS must maximize.

2) Cybersickness: Immersion in a virtual environment can induce discomforts often characterized as cybersickness which symptoms are similar to motion sickness (e.g. nausea, headaches, dizziness) [START_REF] Rebenitsch | Review on cybersickness in applications and visual displays[END_REF]. Cybersickness arises from perception conflicts between visual, vestibular and proprioceptive systems. Indeed, while moving around in the VE but getting no physical feedback or incorrectly configured feedback, users will get conflicting information. Cybersickness does not equally affect everyone. Moreover, targeted users with visual, visuo-spatial of cognitive impairments, are likely to be more sensitive to this symptoms. Those symptoms can significantly alter simulation comfort and can thus negatively impact simulator training efficiency. It is therefore critical to design a system minimizing cybersickness by reducing mismatches between visual, vestibular and proprioceptive information.

III. SIMULATOR DESIGN

In previous work, we proposed a first wheelchair simulator design [START_REF] Devigne | Design of an immersive simulator for assisted power wheelchair driving[END_REF]. This simulator consisted in a standard power wheelchair fixed on the Immersia immersive room in Rennes, France. This first simulator matched the constraints related to clinical assessment presented in Section II-A as it directly used an off-the-shelf power wheelchair. In this framework, the user was seating on a motionless wheelchair and immersed in the VE through 3D rendering only. Although this first simulator generated a rather good SoP, most of the people who tested it felt cybersickness.

Based on this first simulator design, we here propose a new simulator design which aims to match VR-related constraints by maximizing SoP as well as addressing the cybersickness issue (Fig. 1).

A. Towards a multisensory simulator

While most of existing VR simulators use only 3D visual rendering techniques to immerse user, immersion is not restricted to visual sense only. Indeed, additional sensory information such as motion, visual, auditory [START_REF] Sherman | Understanding virtual reality: Interface, application, and design[END_REF] or even olfactory [START_REF] Porcherot | Immersive techniques and virtual reality[END_REF] cues can be simultaneously generated to improve user immersive experience. Then, we here propose an innovative multisensory simulator which incorporates a motion platform aiming to reproduce wheelchair motion cues and physical interactions with the virtual environment, as well as visual and auditory feedback modalities.

1) Motion platform: We design a motion platform generating motion cues in order to simulate accelerations as well as haptic feedback in order to reproduce interactions with the virtual environment such as bumps, vibrations and collisions.

Among the existing wheelchair simulators with motion platform, different types of simulators can be identified, depending on the number of degrees of freedom (DoF) that are used. In majority, simulators classically use either 3 DoF or 6 DoF (Stewart platform) [START_REF] Arlati | Virtual reality-based wheelchair simulators: A scoping review[END_REF]. If 6 DoF simulators achieve high frequency performances, 3 DoF simulators have been shown to be sufficient enough for training applications in terms of acceleration rendering.

In addition, some 6 DoF simulators add a turntable in order to extend rotation capabilities along vertical axis: this design achieves a high level of realism [START_REF] Ito | Development of a powered wheelchair driving simulator for research and development use[END_REF]. We then propose to add a turntable on a 3 DoF simulator, leading to an innovative 4 DoF simulator, able to reach kinematics requirements stated in section II-A. The Fig. 4 illustrates the proposed solution, based on a parallel mechanism using 4 linear actuators (3 DoF) and a turntable on the top (4th DoF). This design is a trade-off between the desired range of motion and the compactness. Platform kinematic was designed according real power wheelchair behaviour [START_REF] Baudry | Taking caster wheel behavior into account in the kinematics of powered wheelchairs[END_REF]. An off-the-shelf SALSA M2 wheelchair seat from Sunrise Medical is then fixed on the turntable so that user environment does not differ from a commercial power wheelchair (see Fig. 5c): simulation experience is thus compliant with daily life experience.

The whole volume is similar to the one of a power wheelchair so that it increases the SoP for the use in immersive rooms. Also, the platform is lightweight in order to be compliant with immersive rooms. For example, the platform needs to be lighter than 100kg/m 2 to match Immersia specifications. This choice will also ease the use and transport. The platform has been manufactured by CL Corporation (http://www.clcorporation.com/) from the specifications.

2) Visual feedback: Visual feedback provides wheelchair motion perception for each 6 DoF matching self-motion sensations suggested by the motion platform.

A virtual wheelchair is included in the 3D scenes and co-located with the motion platform. For instance, the 3D representation of the wheelchair seat in the VE matches the exact position of the motion platform seat.

Furthermore, the complexity of the virtual environment, in terms of feedback modalities, is adapted to user impairments and training programs. For example, as some user may not be able to process multiple visual stimuli, proposed 3D scenes would represent in these cases a low complex version of the scene.

3) Auditory feedback: Auditory feedback is provided to the user in order to increase immersive experience and SoP. This includes not only virtual sound rendered on speakers for ambient sounds, but also specific sound effects directly coming from the platform itself. In particular, the sound produced by the brakes of the wheelchair is an important auditory cue for the users: this sound is the first feedback perceived by users when a wheelchair starts to move.

B. Simulator Workflow

PWS design relies on a generic workflow (Fig. 3) composed of the following modules:

• The 3D Engine manages the VE and its display.

• The Physics Engine updates the virtual wheelchair position, velocity and acceleration in the VE. These values are computed from input controller data, previous position, velocity and acceleration values sent by the 3D Engine. It also incorporates physics laws (e.g. gravity). • The Feedback Engine then computes the motion to be applied. The motion is split into a mechanical motion of the platform and to a visual feedback to the 3D Engine.

These modules are independent, and dedicated to distinct specific tasks. This modular arrangement allows PWS to be a versatile and adaptable simulator. Each module can be concurrently and independently developed or replaced. The workflow presented here describes only required modules.

IV. SYSTEM IMPLEMENTATION AND SETUP

We developed, implemented and tested the following simulator setup.

1) Motion platform and motion cues: For our first experiments, only 2 degrees of freedom are used to provide motion cues. This feedback is based on "classical" algorithms as described in [START_REF] Colombet | Motion cueing: What is the impact on the driver's behavior ?[END_REF]. To manage with the lack of DoF, we included a "tilt coordination" strategy that implies a relationship with the 3D Engine as shown in the simulator workflow (Fig. 5c). An off-the-shelf wheelchair joystick controller is used as user interface.

2) Visual feedback and 3D scenes: We used the widespread 3D engine Unity3D to visually render 3D scenes as it is compliant with several HMDs and Immersia (http: //www.irisa.fr/immersia/). In addition to their realism appearance, proposed 3D scenes are replication of real places known by end-users as real-like virtual environment are likely to increase user trust, comfort and SoP.

For now, our simulator includes two 3D scenes that are reproduction of real places. The first one is an outdoor environment: a urban area whose base model has been provided by Rennes Metropole. The second one is an indoor scene: a replication of Pôle Saint Hélier experimental room. Furthermore, because we simulate motion from a static spot with 4 DoF, it does not induce entirely real-like consequences. In particular, it causes undesired head movements leading to irregular gaze direction. Thus, we apply a visual compensation by moving the 3D scene accordingly.

3) System workflow: Finally, to implement a versatile workflow, we used the Robot Operating System (ROS) library [START_REF] Quigley | ROS: an open-source Robot Operating System[END_REF]. Each module of the workflow is represented by a node in a ROS network that can send or receive data regardless of its execution environment and programming language. Thus, each node may be changed as long as input and output specifications are fulfilled.

Our first implementation has been successfully tested in several configurations. In particular, we tried PWS with two HMDs (HTC Vive and HTC Vive Pro), various screens and in Immersia (see Fig. 5b and5a). As for the controller, we used 3 different commercial off-the-shelf joysticks. Regarding physical feedback, this platform achieves a consistent behaviour, which still needs tuning and more advanced studies.

V. DISCUSSION

Our first simulator implementation is operational. In particular, the PWS has been successfully tested with different display devices (HMD, large immersive rooms, simple screens), 3D scenes (indoor/outdoor, low/high graphical resolution) and input devices (standard joystick, head array).

The motion platform as well as the simulator workflow have been designed to be versatile and adaptable not only to each user needs but also to rehabilitation center experimental environment and available hardware.

The proposed setup then meets previously stated usercentered constraints. The compliance of the system with wheelchair driving training and rehabilitation programs has now to be evaluated through clinical assessment with wheelchair users. In particular, the impact of the various feedback modalities provided by the simulator on SoP and cybersickness has to be assessed.

We are aware of the current PWS setup limitations and that some improvements still need to be made. On the one hand, regarding motion feedback, we plan to control all 4 DoF and to enhance the simulator kinematics in order to handle interactions with the environment such as bumps, vibrations and collisions. On the other hand, regarding the visual feedback and virtual environment, we want to populate 3D scenes with dynamic entities such as avatars, vehicles, etc. Furthermore, we want to add user embodiment in order to perform ecological situations as realistically as possible.

However, the simulator is ready to use, safe and includes a consistent motion feedback that can already be evaluated. Thus, we plan to conduct during the next months several experiments to assess the additional motion feedback impact on cybersickness and SoP (protocols similar to [START_REF] Devigne | Design of an immersive simulator for assisted power wheelchair driving[END_REF]). A study on the platform impact on cybersickness is currently being planned with about thirty able-bodied participants. A study of real power wheelchair dynamics is also planned in order to improve the virtual wheelchair dynamics estimations.

Besides studies and enhancements, we want to explore PWS additional use cases. For instance, based on our previous work on assistive robotics, we could consider adding virtual sensors and obstacles avoidance system in the simulator [START_REF] Devigne | Design of an immersive simulator for assisted power wheelchair driving[END_REF]. Thus, our simulator will be a convenient tool to prototype assistive systems.

VI. CONCLUSION

In this paper we presented a user-centered design of a multisensory power wheelchair simulator. This simulator relies on VR technology to immerse the user in simulated wheelchair driving experience. The originality of the simulator relies on the combination of visual, auditory and motion cues provided by an innovative 4 degree of freedom mechanical structure. The proposed simulator design is versatile and adaptable to the diversity of impairments and needs. Indeed, it is directly compliant with any kind of 3D display devices that support Unity3D such as HMD, immersive room or screen display. In addition, wheelchair standard components fixed on the mechanical structure allow the platform to be compliant with clinical requirements. Indeed, the proposed simulator is directly compliant with wheelchair user seating and control needs. Clinical assessment of the simulator with power wheelchair users will then allow evaluation of driving experience in simulation but also its comparison between virtual and real conditions. In addition, the impact of the multimodal feedback provided by the simulator on user experience will be assessed in next studies.

Fig. 2 :

 2 Fig. 2: Motion axes of a power wheelchair (wc).

  s -2 n.a. 15 m.s -2 Rotational accelerations 2 rad.s -2 10 rad.s -2 5 rad.s -2

Fig. 3 :Fig. 4 :

 34 Fig. 3: PWS software diagram with examples of compliant devices

Fig. 5 :

 5 Fig. 5: PWS first implementation

TABLE I :

 I Maximum kinematics values of power wheelchair.

Univ Rennes, INSA Rennes, CNRS, Inria, Irisa-UMR6074, France.

Pôle Saint Hélier rehabilitation center, France.

Univ Rennes, INSA Rennes, LGCGM EA 3913, France.

ACKNOWLEDGEMENT

The authors would like to thank Ronan Gaugne from IRISA Immersia, Solenne Fortun from the IRISA Rainbow team and Éric Bazin from IETR/INSA. This work is carried out as part of the INTERREG VA FMA ADAPT project funded by the European Regional Development Fund (ERDF), and is partially funded by the Crowdbot Project, a European Union Horizon 2020 Project.


Rodrigue Imad

Sebastien Houcke

BLIND FRAME SYNCHRONIZATION AND PHASE OFFSET ESTIMATION FOR CODED SYSTEMS

In this paper, we present a new algorithm of blind frame synchronization and phase offset estimation that can be applied to any digital transmission scheme using a channel coding with a Binary Phase Shift Keying (BPSK) modulation. The estimator is based on the calculation of the syndrome elements of a received codeword obtained using the parity check matrix of the code. After presenting the proposed method, we evaluate its performance by applying it to some Low Density Parity Check (LDPC) codes and convolutional codes. This performance is measured by plotting the probability of false frame synchronization and the Mean Squared Estimation Error (MSEE) versus the Signal to Noise Ratio (E b /N 0 ).

INTRODUCTION

Nowadays, the transmission and storage of information are based on digital techniques. An important step in these techniques is Channel Coding. Several studies [START_REF] Berrou | Near shannon limit error-correcting coding and decoding: turbo-codes[END_REF][START_REF] Mackay | Near shannon-limit performance of low-density parity-check codes[END_REF] have demonstrated that actual codes such as LDPC codes and turbocodes, are very powerful and are able to decode heavily corrupted sequences. However, these works were based on the assumption of a coherent detection, which may be less than realistic for many digital communication systems. Therefore, we are interested in deriving new algorithms that are able to estimate the frame synchronization position and the phase offset introduced by the propagation channel, before applying the decoder. In the literature, many algorithms have been proposed for the estimation of the phase offset introduced by the channel. For a phase offset constant on a whole received codeword and by assuming that we do not have any a priori information about the transmitted data, two synchronization approaches are often used: the "Non Data Aided" (NDA) and the "Hard Decision Directed" (HDD) [START_REF] Meyr | Digital Communication Receivers[END_REF]. These approaches assume that only the modulation type used before transmission is known by the receiver, which is generally the case. In addition, some algorithms of phase offset estimation for coded signals considered the "Code aided" hypothesis, such as recently in [START_REF] Wymeersch | Code-aided frame synchronization and phase ambiguity resolution[END_REF], while others considered the phase recovery jointly with the decoder [START_REF] Mielczarek | Joint synchronization and decoding of turbo codes on AWGN channels[END_REF]. We present in this paper a new method of blind phase recovery based on the calculation of the syndrome elements of a received sequence of coded symbols. This method has been inspired from a blind frame synchronization method that has been introduced and developed in [START_REF] Houcke | Blind frame synchronization for block code[END_REF][START_REF] Imad | Blind frame synchronization on gaussian channel[END_REF][START_REF] Imad | Blind frame synchronization for error correcting codes[END_REF]. This paper is organized as follows. In Section 2 we define and introduce the context of our study. A review on the frame synchronization method recently proposed in the case of perfect phase recovery, is presented in Section 3. In Section 4 we modify the previous method to take into consideration the phase offset due to the channel. Section 5 introduces the proposed method for estimating the phase offset. Simulation results are presented in Section 6 where different LDPC and convolutional codes are synchronized. Finally, Section 7 concludes the work.

CONTEXT OF OUR STUDY

In this paper, we consider that the transmitter is sending a binary sequence of codewords and is using a Binary Phase Shift Keying (BPSK) modulation. The propagation channel is corrupted by an additive white Gaussian noise. For a given code of rate

ρ = n c -n r n c ,
it is often possible to find the corresponding parity check matrix H of size n r × n c , where n c represents the length of a codeword and n r the number of parity relations. Let b(k) = ±1 be the k th coded and modulated bit to be transmitted. At the reception, the k th received sample is given by:

r(k) = b(k -t 0 )e iθ + w(k), (1)
where t 0 is an integer representing the shift of the transmitted symbols and θ is a real representing the phase offset introduced by the propagation channel. w(k) = w 1 (k) + iw 2 (k) is a white complex Gaussian noise. The received sequence of N samples can be written as: r = [r(1), . . . , r(N )].

FRAME SYNCHRONIZATION METHOD IN THE CASE OF PERFECT PHASE RECOVERY

When there is no phase offset introduced by the propagation channel, the phase θ introduced in (1) is equal to zero. We showed in [START_REF] Imad | Blind frame synchronization for error correcting codes[END_REF] that our blind frame synchronization method is based on a MAP approach in the sense of maximizing the probability that a position t corresponds to the correct synchronization moment, given the received samples. In other words, it maximizes the following a posteriori probability:

P r[t/r], t ∈ [0, n c -1].
Therefore, at each position t on the received sequence we apply a sliding window of length Kn c , where K is an integer greater or equal to one. K represents the number of blocks of length n c contained in the synchronization window.

At each position of this sliding window, we calculate the vector of Log-Likelihood Ratios (LLR) of the syndrome elements. This vector can be written as:

L(S t ) = [L(S t (1)), . . . , L(S t (Kn r ))],
where L(S t (k)) is the LLR of the k th syndrome element. According to [START_REF] Hagenauer | Iterative decoding of binary block and convolutional codes[END_REF], L(S t (k)) is proportional to:

L(S t (k)) = (-1) u k +1 u k j=1 sign(r(t+k j )) min j=1,...,u k |r(t+k j )|,
where u k and k j represent the number of ones in the k th line of the parity check matrix of the code and the position of the j th non zero element in this k th line, respectively. Having this, we compute

φ(t) = Knr k=1 L(S t (k))
and the frame synchronization position is estimated by:

t0 = argmin t=0,...,nc-1 { φ(t)}. (2)

FRAME SYNCHRONIZATION IN THE CASE OF A PHASE OFFSET INTRODUCED BY THE CHANNEL

Let us study the robustness of our frame synchronization method when a phase offset θ is introduced by the propagation channel and assumed to be constant on K received codewords.

In order to calculate the reliability of the sum of the syndrome elements, we apply our frame synchronization criterion twice; once on the real part of a received symbol r(k) and the other time on the imaginary part. This gives two functions:

P θ (t) = Knr k=1 (-1) u k +1 u k j=1 sign (r(t + k j )) . min j=1,...,u k (r(t + k j )) = Knr k=1 (-1) u k +1 u k j=1 sign b(t + k j -t 0 )cosθ + w 1 (t + k j ) . min j=1,...,u k b(t + k j -t 0 )cosθ + w 1 (t + k j ) (3)
and

Q θ (t) = Knr k=1 (-1) u k +1 u k j=1 sign (r(t + k j )) . min j=1,...,u k (r(t + k j )) = Knr k=1 (-1) u k +1 u k j=1 sign b(t + k j -t 0 )sinθ + w 2 (t + k j ) . min j=1,...,u k b(t + k j -t 0 )sinθ + w 2 (t + k j ) . (4)
Let E[x] denote the expected value of x. We have for example:

E lim θ→0 P θ (t) = E φ(t) and E lim θ→0 Q θ (t) = 0
and on the other hand

E lim θ→ π 2 P θ (t) = 0 and E lim θ→ π 2 Q θ (t) = E φ(t)
θ being unknown, P θ (t) and Q θ (t) should then be treated together in order to get an idea on the reliability of the syndrome elements. Therefore, an estimation of the frame synchronization position is obtained similarly to (2) but by replacing φ(t) by F P θ (t), Q θ (t) , which is a function of P θ (t) and Q θ (t).

The choice of F depends on the fact that u k is even or odd.

Case I: u k is even

In a noise free channel, ( 3) and ( 4) can be written as:

P θ (t) = φ(t)|cosθ| (5)
Q θ (t) = φ(t)|sinθ| (6)
In the case of a coherent detection, we usually have φ(t 0 ) < 0 < φ(t) t =t0 . Therefore, in order to apply the criterion given in (2) to our case, F (P, Q) should be an increasing function of P and Q. A simple example of F giving good results could be:

F P θ (t), Q θ (t) = P θ (t) + Q θ (t). (7)

Case II: u k is odd

When u k is odd and in a noise free channel, we have:

P θ (t) = φ(t)|cosθ| if θ ∈ [0, π 2 ] ∪ [ 3π 2 , π] -φ(t)|cosθ| if θ ∈ [ π 2 , 3π 2 ] (8)
Q θ (t) = φ(t)|sinθ| if θ ∈ [0, π] -φ(t)|sinθ| if θ ∈ [π, 2π] (9)
The sign of P θ (t) and Q θ (t) being dependent from θ, it does not help us this time for finding the frame synchronization position. However we still have:

E |P θ (t 0 )| > E |P θ (t) t =t0 | and E |Q θ (t 0 )| > E |Q θ (t) t =t0 | (10)
According to the previous observations, the function given in (7) becomes:

F P θ (t), Q θ (t) = -|P θ (t)| -|Q θ (t)|. (11)

PROPOSED METHOD OF CARRIER PHASE RECOVERY

Let us assume that we have correctly estimated the frame synchronization position. In a noise free channel and by combining ( 5), ( 6), ( 8) and ( 9) we get:

θ = Arctan ± Q θ (t 0 ) P θ (t 0 ) ∀u k . ( 12
)
Using the above equation in our context, we get an estimation of θ with an ambiguity of π 2 . However, we can evolve this criterion in order to obtain an estimation of θ modulo π instead of π 2 . The procedure to be done depends on the parity of u k : If u k is even, we study the evolution of the functions δx → P θ+δx and δx → Q θ+δx . Indeed, for δx positive and close to zero, and as P θ (t 0 ) and Q θ (t 0 ) are negative and depend on θ, we have:

• If θ ∈ [0, π 2 -δx] ∪ [π, 3π 2 -δx],
δx → P θ+δx is an increasing function and δx → Q θ+δx is a decreasing one.

• If θ ∈ [ π 2 , π -δx] ∪ [ 3π 2 , 2π -δx],
δx → P θ+δx is a decreasing function and δx → Q θ+δx is an increasing one.

However, when u k is odd, we can use the same procedure as the one described above but by studying this time the variations of δx → P θ+δx and δx → Q θ+δx . We have:

• If θ ∈ [0, π 2 -δx] ∪ [π, 3π 2 -δx],
δx → P θ+δx is a decreasing function and δx → Q θ+δx an increasing one.

• If θ ∈ [ π 2 , π -δx] ∪ [ 3π 2 , 2π -δx],
δx → P θ+δx is an increasing function and δx → Q θ+δx a decreasing one.

By applying this method, we are able to estimate θ with an ambiguity of π.

SIMULATION RESULTS

We present in this section simulation results concerning frame synchronization and phase offset estimation. The results below were obtained for K = 1, which means that only one block is contained in the synchronization window. For all the plotted curves, functions given in [START_REF] Imad | Blind frame synchronization on gaussian channel[END_REF] and (11) were used. In order to evaluate the performance of the proposed method, we synchronized different types of codes. For each simulation, more than 10000 Monte Carlo realizations were made. Fig. 1 shows the curves of the probability of false frame synchronization versus E b /N 0 for two LDPC codes. These codes have a length equals to 512 bits and a rate of 0.5. They differ only by the composition of their parity check matrix. Code I has four non zero elements in each line of its parity check matrix and code II has six. When a phase offset randomly chosen by a uniform law between 0 and 2π is introduced, there is a gap of around 1.5 dB compared to the case where no phase offset exists. Let us now compare the curves plotted for codes I and II: as we can see and as mentioned in [START_REF] Houcke | Blind frame synchronization for block code[END_REF][START_REF] Imad | Blind frame synchronization on gaussian channel[END_REF], there is a degradation in the performance of our synchronization method when the number of non zero elements in the parity check matrix of the code increases. In Fig. 2, we applied the same synchronization method but this time to convolutional codes. We considered in our simulations that the final state of the encoder is not imposed. This means that neither we terminated the trellis nor we applied the "tail-biting" technique [START_REF] Johannesson | Fundamentals of Convolutional Coding[END_REF]. In these conditions, non zero elements in the parity check matrix of the code are placed in a "staircase" form. This leads to a degradation in the performance of our synchronization method. One simple solution to this problem is given in [START_REF] Imad | Blind frame synchronization on gaussian channel[END_REF] where the authors propose to interleave the bits in each transmitted codeword using a pseudorandom interleaver of size n c bits. Two convolutional codes of generator polynomials (5, 7) and (23, 35) were tested. They have same length (512 bits), same rate (0.5) and constraint lengths equal to 3 and 5, respectively. As shown in Fig. 2, we observe the same behavior as the one obtained with LDPC codes. Note that the number of non zero elements in each line of the parity check matrix of codes (5, 7) and (23, 35) is equal to 5 and 7, respectively. Thus, even if u k is odd, the proposed frame synchronization method presents good performance. Let us now apply the frame synchronization procedure for a given θ. Figure 3 shows the performance of the frame syn-chronization method applied to LDPC code I, previously introduced in this section. As we can see in this figure, each plotted curve represents the probability of false synchronization versus θ, for a different E b /N 0 . We can clearly observe that the frame synchronization performance varies in terms of the phase offset of the channel. For θ = π 4 , the performance of our method is the worse. Having this, a correction term θ c can be added to the received samples in order to improve the frame synchronization performance. Therefore, let θ c (i) i=1,...,4 = π 16 , π 8 , 3π 16 and π 4 , respectively. Each time we correct a received block by θ c (i) i=1,...,4 , then we apply our frame synchronization procedure, we get F P θ+θc(i) (t), Q θ+θc(i) (t) . The frame synchronization position is finally estimated by: t0 = argmin t=0,...,nc-1 θc(i)=θc(1),...,θc(4) F P θ+θc(i) (t), Q θ+θc(i) (t) .

(13) Fig. 4 shows the performance of the above procedure once applied to LDPC code II. At a probability of false synchronization equals to 10 -3 , an improvement of around 1.2 dB is observed. Let us now evaluate the robustness of the method proposed in Section 5 concerning the phase offset estimation, by comparing its performance to the HDD algorithm. Being used as a reference for many phase recovery algorithms, the HDD algorithm is based on the estimation of the transmitted symbols by taking hard decisions on the received signal. The estimated symbols are then introduced in the expression of the phase likelihood and an estimation of the phase offset is given by:

φHDD = arg N k=1 r(k) d(k) * , (14)
where { d(k)} k=1,...,N are the hard decision estimations for N transmitted symbols obtained from the received samples {r(k)} k=1,...,N . ( * ) designates the conjugate of a complex number. We assume that the frame synchronization position has been correctly estimated. Fig. 5 shows the mean squared estimation error (in rd 2 ) versus E b /N 0 , once our proposed phase recovery method is applied to LDPC codes I and II previously introduced in this section. Compared to the HDD approach, our method presents better performance. A large gap between the two methods can be clearly seen especially for low E b /N 0 . In Fig. 6, same curves have been plotted for convolutional codes (5,7) and (23,35). Our proposed phase recovery method is always better than the HDD algorithm.

CONCLUSION

We have proposed in this paper a new method of blind synchronization that exploits the redundancy introduced by error correcting codes. The criterion on which our method is based on, is used for the frame synchronization and the phase offset estimation at the same time. As shown by simulations, the frame synchronization method keeps good performance when an arbitrary phase offset is added to the transmitted symbols. Furthermore, we have shown that compared to the HDD algorithm, our method of estimating the phase offset presents better performance.

Fig. 1 .

 1 Fig. 1. Frame synchronization of LDPC codes when a random phase offset is introduced.

Fig. 2 .

 2 Fig. 2. Frame synchronization of convolutional codes when a random phase offset is introduced.

Fig. 3 .

 3 Fig. 3. Frame synchronization of LDPC code I versus θ, for different values of E b /N 0 .

Fig. 4 .

 4 Fig. 4. Frame synchronization of LDPC code II by adding a correction term to the received samples.

Fig. 5 .

 5 Fig. 5. Comparison between the proposed method and the HDD method concerning the phase offset estimation for LDPC codes.

Fig. 6 .

 6 Fig.6. Comparison between the proposed method and the HDD method concerning the phase offset estimation for convolutional codes.

Code I without phase offset Code I with phase offset Code II without phase offset Code II with phase offset