Advances in techniques of locating mobile users have promoted the development of marketing campaigns based on customers' location. WiFi-based location methods have proven their usefulness in tracking and locating customers within a indoor mall. Nevertheless, in some cases the performance of these methods prevents them from being used in real scenarios. In this paper, we have faced the problem of improving the execution time and reducing the cost of one of these WiFi-based location methods. Parallel programming techniques, serviceoriented technologies and the cloud computing paradigm have been combined to solve efficiently these problems. The resulting system has been deployed in the Amazon EC2 environment, evaluating different configuration and deployment options.
The BAI4SOW project [
WiFi-based fingerprinting localization methods [
The rest of the paper is organized as follows. The proposed localization method and the computational cost is described in Section 2. Section 3 and Section 4 detail the parallel service for user’s location and how this service has been deployed in Amazon EC2, respectively. Finally, Section 5 presents the conclusions and future work. 2
reference surface will correspond with the estimated RSS from a different AP (Access Point).
After that, during the localization stage, a new sample collected at an unknown position will be used to estimate the real location of the user’s device. The RSS from each AP will be searched in the corresponding reference surface and a new sub-surface will be created by means of the assignation of scores to the coordinates of the environment depending on how similar is the collected RSS with the stored one. This way, the coordinate will obtain the maximum score (equal to one) if the RSS exactly matches the value stored in the corresponding surface and will be reduced accordingly to the difference between the measured and the stored values.
Once the sub-surfaces for all the APs are computed, they are summed up to obtain a resulting surface containing higher scores as the coordinates are more probable to be the real location of the device. However, as the complete surface could contain non-reachable areas by the users (e.g. storage rooms at shops), a mask is applied in order to remove the non-reachable areas. Therefore, the most probable location of the user’s device will be the one with the highest score in the masked resulting surface.
It is important to highlight that the time required to process the continuous reference surfaces and to obtain the device location during the localization stage will depend on two variables chosen during the design of the localization system: the number of the APs and the resolution of the system.
In this paper, the experimental environment has been set up in a
mediumsize indoor scenario (around 2500m2). Although the use of cells with 15cm-side
was proved to be the most effective [
These times must be improved to offer an efficient response from the point of view of BAI4SOW system, especially during the localization stage, as the solution must be able to locate hundreds of customers that are simultaneously participating in a marketing campaign. The proposed solution to solve this problem will be described in the following sections. 3
Two issues must be addressed to integrate the WiFi-based location method into the BAI4SOW system. On the one hand, the execution time of algorithms must be reduced to locate efficiently customers in a medium-size indoor mall. We propose the design and programming of a new parallel version of these algorithms. This new version is based on a master-worker architecture that can be executed in a concurrent or distributed execution environment. And, on the other hand, it is necessary that these new algorithms are deployed in high-performance computing resources while their functionality is easily accessible from BAI4SOW applications. For these reasons, we have decided to integrate them into RESTful Web services that will be executed in the Amazon cloud infrastructure.
In the following sections we detail the solutions proposed to overcome the two introduced issues. 3.1
A parallelization strategy based on the master-slave architecture In software engineering, a master-worker architecture is a high-level design pattern that facilitates the parallel execution of applications composed by a set of independent tasks. The pattern consists of two class of processes: a master and a pool of workers. The former is responsible of assigning tasks to workers and guaranteeing that all of them are correctly completed; whereas the workers simply execute the assigned tasks by returning the corresponding results to the master. This architectural model is highly scalable by increasing (or decreasing) the size of pool according to the execution requirements. It also facilitates the deployment of the solution in a distributed computing environment, such as in a cloud infrastructure, for instance.
The training and location algorithms can be programmed as a master-worker system. On the one hand, the process of creating a continuous reference surface is an independent task computed from RSS measures. Therefore, the generation of the different surfaces can be parallelized in order to accelerate the original solution. On the other hand, the location algorithm requires checking the sample of the customer’s unknown position against to each of the reference surfaces. These checks are independent and, therefore, can be also programmed as parallel tasks. The parallelization of these algorithms has consisted of two stages. Firstly, we have implemented a generic master-worker architecture that can be easily customized and reused for solving different problems. The architecture was developed using the Java programming language. Figure 2 shows an abstraction of the proposed architecture. The configuration file determines the number of workers and the IP addresses of the computing instances where they will be executed. On the other hand, the application file describes the set of tasks to be completed (task’s identification, input parameters and output results, mainly). The master node uses the configuration data for deploying and managing the workers. Then, it assigns tasks to the workers so that they are always busy. Besides, the task’s and workers’ state are monitored in order to guarantee the fault tolerance of the system. On the other hand, the data involved in solving the problem are stored into a shared database. This reduces the data transfers among the processes.
The second stage of the parallelization consists of dividing the original algorithms in a set of independent tasks than can be executed in parallel. Loop-level parallelization techniques has been applied to code the new version of both algorithms. Besides, all the MATLAB code used to create and process the reference surfaces has been converted to Octave code. This decision is based on economic criteria: running MATLAB code in cloud instances represents an additional cost because of the licences required. 3.2
Parallel algorithms as RESTful services executed on the cloud Once the algorithms have been parallelized, the goal is to make them accessible to BAI4SOW applications. We decided to integrate them into two RESTful Web services that were published as part of the BAI4SOW infrastructure. This approach allows any application connected to the network to make use of them.
Figure 3 shows the cloud-based implementation of the system. The Surface Creation Service (SCS) provides operations to submit training measures and compute the corresponding continuous reference surfaces. The master-worker version of the corresponding algorithm has been integrated into the logic of the service and it has been deployed into the Amazon EC2 infrastructure. The flexibility of the master-worker architecture allows us to deploy the service over a concurrent environment (using an only virtual instance that has a high number of CPU cores) or a distributed environment (using a pool of virtual instances). In both cases the data are stored into the Amazon S3 service.
On the other hand, the Location Service (LS) offers functionality to estimate users’ location. RSS samples measured by the user’s mobile are aggregated and sent to the service as input parameters. These are processed by the masterworker version of the location algorithm which checks them against the reference surfaces previously computed (therefore, the Amazon S3 storage is shared by both services). Finally, the service can be also deployed over a concurrent or distributed environment.
Because the services are deployed in the cloud it is necessary to select the computing resources to be provisioned according to the BAI4SOW applications’ requirements. The execution times and costs are briefly analysed and discussed in the following section. 4
In this evaluation an user has freely walked in the environment described in Section 2. During the walk, the user’s mobile has measured 300 RSS values in different positions and a location request has been sent for each of these values to determine her/his location. Previously, 100 reference surfaces with an accuracy of 1 centimetre were computed to be used by the location method.
In this scenario we are interested in configuring different service deployments
in the Amazon EC2 cloud and comparing their execution times and costs. Some
decisions related to the provisioning of resources are based on our experience
in the deployment of cloud-based systems [
Table 1 shows the execution times of the parallel algorithms by considering different deployments in the Amazon EC2 infrastructure. First, different models of R4 virtual instances have been hired following an on-demand schema in order to evaluate a concurrent deployment. These instances are optimized for memoryintensive applications, and they can offer a good performance for this type of processing problems. The number of cores and the memory of these instances are specified in the second and third columns of Table 1, respectively. As it is shown, the r4.xlarge instance suffered memory problems and the experiment was not successfully completed. The other three R4 instance models execute correctly the experiment and present a linear speedup according to the number of available cores. The best execution time was achieved by the r4.8xlarge instance (4.2 hours) which improves an order of magnitude the time of the sequential version (44.4 hours). On the other hand, the cost of experiments (column Total cost ) considers the costs of computing resources and of storing the data into the Amazon S3 service. The former is calculated multiplying the cost per hour of the selected instances (column Cost/hour ) by the total execution time (column Total time); whereas, the second is the same in all the deployments (the size of involved data is around 66Gb and the storage price is 0.022 e/Gb for the first 50TB/month). As a conclusion, the cost of these instances is proportional to the number of cores and, therefore, the total cost of experiment is very similar for all the concurrent deployments.
On the other hand, we have provisioned and configured two different distributed environments as well. These environments are composed by a pool of three and six r4.8xlarge instances, respectively. Let us to remark that the workers are now distributed between the cores of the different instances. Therefore, a maximum of 95/191 workers may be running simultaneously on the provisioned instances (the other core is occupied by the master). The total execution time continues to improve in proportion to the available cores completing the experiment in less than 1 hour with a pool of six instances. These results show that the overhead of the parallelization has not a significant influence in the times. On the other hand, the total costs slightly increased compared to the costs of concurrent deployments, but this is due to the fact that there is an excess in the computing capacity hired (in the first distributed deployment 96 cores are not used during 30 minutes, for instance). 5
In this paper we have presented a parallel and service-oriented system to improve the execution time of a WiFi-based location method. The system is based on the master-worker architecture and has been tested and deployed in the cloud. The experimental validation has shown a significant improvement in execution time with respect to the sequential solution.
As future work, we are interested in validating the system in a real indoor mall (with hundreds of mobile users participating in a marketing campaign) and in considering new deployments based on the mobile-edge computing paradigm to reduce the communication latency between mobile users and services.
This work has been partially supported by the Ctedra de Ingeniera Avanzada Escribano of the UAH (Catedra2017-005), the TIN2017-84796-C2-2-R project, granted by the Spanish Ministry of Economy, Industry and Competitiveness, and the JIUZ-2018-TEC-04 project, granted by the Ibercaja Foundation (UZ).