WiFi Hotspot Localization
Localize WiFi hotspot using gradient descent.
In this case study, we built an application to locate the WiFi hotspot using gradient descent.
The algorithm starts with an initial location that is far away from a WiFi hotspot we placed in an open area. At each iteration, the algorithm measures the WiFi signal strengths at four locations ((x+5,y),(x-5,y),(x,y+5),(x,y-5)) around the current location (x,y). The measurements at these four locations allow the algorithm to compute the gradient of the WiFi signal strength field at location (x,y). Then, the algorithm move the current location 5 meters toward the direction of gradient. Iteration by iteration, the current location (x,y) will be getting closer to the location of the WiFi hotspot. In this algorithm, the four measurements in each iteration can happen at any order. We use the newTask() primitive to program this logic.
We show a simplied version of this application in testcases/testapp2.py. The main application logic is an active sensing loop.
Predictive Optimization
In this active sensing loop, the four tasks created in each iteration can be executed in any order. Choosing the right order to visit the tasks in each iteration can lead to different execution time. Next, we show BeeCluster's predictive optimization feature can help in this scenario.
As an illustrative example, consider an application with the active sensing loop shown in the above block. The algorithm starts with three initial locations A,B,C. In line 3, the algorithm collects sensor readings from these three locations. Then it updates the three locations based on the sensor readings and proceeds to a new iteration. This basic algorithm represents a category of iterative, active sensing applications. For example, the above case study application falls into this category. Let A_n, B_n, C_n denote the locations of A,B,C at line 3 in the n-th iteration.
Consider the scenario in the above figure, where we wish to run this application using one drone. When the program first reaches line 3, the orchestration system dispatches the drone to visit locations A_1, B_1, C_1. At this time, any orchestration system that only considers the current set of requests, i.e., A_1, B_1, C_1, yields two equivalent routes: A_1 --> B_1 --> C_1 or A_1 --> C_1 --> B_1. However, these two routes are not equivalent if we consider multiple iterations of the program.
If we choose the route A_1 --> B_1 --> C_1, then in the second iteration, the drone needs to fly from C_1 to A_2 to start the new iteration (the worst case in the above figure).
However, if we choose the route A_1 --> C_1 --> B_1, then in the second iteration, the drone only needs to fly from B_1 to A_2 to start the new iteration (the best case in the above figure).
In this example, the worst case can take 50\% more flying time compared to the best case. However, this optimization is possible only if we consider future requests.
Predictive Optimization in WiFi Hotspot Localization
Go back to the WiFi hotspot localization application, BeeCluster can use the first few iterations of execution to predict what will happen next. Then, this future information can help BeeCluster's scheduler makes optimal plan to minimize the execution time.
We show the traces of the drone in our real world experiment in the figure below.
We can clearly see that in the first few iteration, the drone visited the four tasks in each iteration with random and local-optimal patterns. Later on, the drone starts to visit the four tasks in each iteration in an global-optimal order.