This page focuses on Mobility Prediction comparing its performance when based on either RSSI or wireless client position information. Grey Model is exploited to forecast next RSSI and wireless client position.

Introduction

Service provisioning in the wireless Internet usually calls for downsizing service contents to suit the specific limits of client devices. For instance, dynamic content negotiation and tailoring are crucial for multimodal services that are willing to provide resource-consuming multimedia in Web pages. In addition, device mobility requires other support operations that are too expensive to be performed by severely limited devices, e.g., context-aware local/global resource retrieval and binding. On the one hand, local discovery operations may consume non-negligible client resources to explore the execution environment and to negotiate with available services. On the other hand, the global identification and retrieval of user-related properties, such as user/terminal profiles and security certificates stored in directories, may require long continuous connectivity, difficult to be handled directly by portable devices.

We claim that wireless Internet service provisioning can significantly benefit from distributed and active infrastructures of mobile middleware proxies working in the fixed network on behalf of portable devices. Proxies can decide the best adaptation operations to perform on service results and can be in charge of any additional management operation, such as supporting connectivity and discovering the needed resources/service components, either in the current wireless locality or in the whole Internet environment. Moreover, proxies can act, locally to the client, as distributed cache repositories for successive service requests. In addition, if proxies are mobile, they can follow device movements during service provisioning by supporting session migration between the different network localities visited, and install automatically only where and when needed.

For all above reasons, the primary design choice in SOMA-based middlewares for the wireless Internet is to provide any wireless device with one SOMA-based companion entity, called shadow proxy, which run in a wired node (place) in the same wireless network locality that currently provides connectivity to the device. Wired/wireless terminals in a locality can be grouped into logical domains, as depicted in the next figure; domains are disjointed, even if they include wireless access points with coverage areas that partially overlap.



Shadow proxies are in charge of determining the applicable context for their clients and of consequently retrieving and binding to the needed local/global resources and service components. Proxies solve the issues related to receiving, caching, and coordinating the tailoring of service contents by taking context-dependent decisions based on profile metadata that describe device characteristics and user preferences.

In the following, the paper concentrates on the crucial issue of how to predict the client movements between SOMA localities in order to migrate in advance the proxies to the next domain of attachment of their associated clients. A detailed description of the design and implementation of the different SOMA middleware components that support the distribution of context-dependent news and video on demand to wire-less devices is out of the scope of the paper, and can be found elsewhere.

To better understand the need for mobility prediction, let us describe the service management operations that the SOMA-based middleware performs in response to a client change of locality. Let us suppose a user roams from DomainA to DomainB in the above figure while she is receiving her personalized service contents. Depending on the (usually configurable) handover strategy of the underlying communication layer, the user device is transparently deassociated from the origin wireless cell and associated to the destination one i) when the client no more receives the origin signal, ii) when the destination RSSI overcomes the origin RSSI (handover hysteresis = 0), iii) or, more generally, when the destination RSSI overcomes the origin RSSI of a specified threshold t (handover hysteresis = t).

Once notified of the communication handover, the middleware should migrate the shadow proxy to the destination domain. There, the proxy should instantiate and con-figure the needed local middleware components and reconnect to the server (or to an equivalent local replica of it) before being capable of serving its client again. This can cause a temporary suspension of the service typically experienced by the client as a provisioning block or delay. The goal of mobility prediction is to effectively per-form the migration of a shadow proxy clone before the client communication handover, so to establish the cloned proxy in the new destination domain, ready for the service session of its incoming client.

We propose and compare three alternative solutions for mobility prediction: RSSI-GM (Received Signal Strength Indication-Grey Model), ECP-GM (Ekahau Cell Probability-Grey Model), and ED-GM (Ekahau Distance-Grey Model). The proposed solutions do not need any additional specific hardware; in particular, they do not require external GPSs, which are still rather expensive, battery-consuming, and therefore unsuitable for very resource-constrained wireless devices. Moreover, the mobility prediction solutions, which we have evaluated and implemented for IEEE 802.11 connectivity, are easily applicable also to wireless clients that exploit other forms of access point connectivity, e.g., Bluetooth clients towards Bluetooth infotainment points. The only constraint is to have client-side awareness of RSSI, either directly exploited in RSSI-GM or indirectly used (via the EPE mediation) in both ECP-GM and ED-GM.

RSSI-GM

The RSSI-GM prediction solution requires having a lightweight client stub running on any participating client device. It is the client stub that autonomously predicts the next cell that will be visited by the hosting wireless device and that communicates the prediction to the shadow proxy place, thus triggering the clone migration. To this purpose, the client stub needs to access the monitoring data about the RSSI values of the IEEE 802.11 base stations in its visibility. The RSSI data is used as input for a simple Grey-based discrete model GM(1,1) for the prediction of future RSSI values. Client stubs achieve platform- and vendor-independent visibility of RSSI data by integrating with portable and dynamically installable monitoring mechanisms.

Given one reachable access point and the set of its actual RSSI values measured at the client side R0 = {r0(1), …, r0(n)}, where r0(i) is the RSSI value at the discrete time i, it is possible to calculate R1 = {r1(1), …, r1(n)}, where:

Then, from the GM(1,1) discrete differential equation of the first order:

the client stub determines a and u, which are exploited to obtain the predicted RSSI value pr(i) at discrete time i according to the GM(1,1) prediction function:

When the pr(i) for a base station x overcomes the pr(i) for the currently associated base station y, then the client stub communicates the mobility prediction to the shadow proxy place, thus triggering the proxy clone migration.
The above solution for client mobility prediction is completely local and lightweight; any client stub can estimate its future RSSI values simply by maintaining a finite series of previous RSSI data. In particular, the client stub catches the needed monitoring in-formation and predicts the next cell in a completely autonomous way, with a very limited overhead. The client stub exploits the limited bandwidth wireless channel only occasionally to inform the shadow proxy place in the case of predicted change of logical domain.

ECP-GM and ED-GM

Similarly to RSSI-GM, both ECP-GM and ED-GM prediction solutions use GM(1,1) discrete models. However, they do not exploit RSSI data as the input values for the prediction models but, respectively, the estimated probability that a client device is located in a cell and the estimated device distances from the borders of IEEE 802.11 cells of access points in visibility. In these two solutions, it is directly the SOMA place hosting the shadow proxy execution that performs mobility prediction by communicating with EPE (Ekahau Positioning Engine) to obtain the needed information about cell probabilities and distances.

EPE is the most widespread commercial solution for non-GPS-based positioning in IEEE 802.11 infrastructure-mode networks. For any target device, EPE provides the probabilities that the device is located in a set of pre-defined logical areas, i.e., configurable disjointed portions of the wireless deployment scenario. Bayes-based probability estimation is performed by observing the current and recent RSSI values at the target device, by comparing them with a database of RSSI samples for the provisioning environment, and by considering a set of specified admitted mobility paths in that environment. This implies that, before exploiting EPE in a specific deployment scenario, system administrators must provide EPE with a map of the environment and the admitted paths of client movements. In addition, an initial "learning" phase is necessary for EPE to acquire the database of RSSI samples for the different points of the provisioning environment. The EPE system consists of a centralized server responsible for the whole processing to obtain the position estimations, and of lightweight Ekahau clients that run on target wireless devices and regularly send the observed RSSI values to the EPE server.

Given a target device, ECP-GM considers the finite set of probabilities provided by EPE and greater than a specified threshold, and applies GM(1,1) to these probabilities. The proxy clone migration is triggered when the predicted probability of the current shadow proxy cell becomes minor than the predicted probability of another logical area. ED-GM, instead, exploits the position estimation provided by EPE to calculate the distances between the target device and the cell borders of visible base stations, and applies GM(1,1) to these distances. In this case, the proxy clone migration is triggered when the predicted distance from the borders of the current cell exceeds the predicted distance from the borders of another logical area.

Let us note that, differently from RSSI-GM, both ECP-GM and ED-GM are not completely decentralized prediction solutions. It is the Ekahau client running on the target device that achieves visibility of the RSSI data and regularly communicates it to EPE. In addition, the shadow proxy in charge of mobility prediction has to interwork with the centralized EPE, which feeds the proxy with estimations about either current cell probabilities or current distances from the cell borders of visible base stations. In addition, since the Ekahau client is currently available only for MS Windows, ECP-GM and ED-GM are not portable on different operating systems, differently from the RSSI-GM solution.

To evaluate the effectiveness and performance of the proposed prediction solutions, we have developed three alternative implementations of the mobility prediction module: all the solutions are integrated with the SOMA platform and present the same API. SOMA is a Java-based mobile agent system intended to support service provisioning in pervasive and ubiquitous environments. We have extended SOMA with the mobility prediction module by adding a shadow proxy which is a new MA subclass that exploits the usual one. The SOMA platform (by either the client stub in RSSI-GM or the SOMA place in ECP-GM and ED-GM) automatically notifies the shadow proxy in the case of handover prediction for the associated client devices. The prediction notification triggers the transparent cloning of the shadow proxy and the clone migration to the predicted cell. The original proxy executes at its previous place until the associated device eventually exits its wireless access locality and completes its handover. Application developers can concentrate only on the service-specific application logic that implements this part of shadow proxy while SOMA automatically handles cloning, anticipated migration, and lifecycle management of shadow proxy instances.

We have measured some performance indicators for all three mobility prediction solutions in both a simulated environment and a real deployment scenario involving the wireless access points in our campus. The simulation has the goal to evaluate the solution behavior also in presence of a large number of mobile clients roaming among a large number of wireless localities. Indicators are:

effectiveness E1%

where NFSP measures times the wireless devices do not find their shadow proxies already running at their destination domains at their arrivals, while NR is the total number of client handovers;

efficiency E2%

where USP is the number of shadow proxies eventually used by the wireless clients and NM is the total number of migrated proxies;

advance time AT

the time interval between the shadow proxy arrival at the destination domain and the eventual client reconnection to that domain.

Effectiveness and efficiency are both significant performance indicators. In general, high effectiveness may be tied to low efficiency that may occur. When the middleware exaggerates in migrating shadow proxy clones to visible localities, by generating useless network traffic. Let us stress that migrated proxy clones are automatically discarded if the associated clients do not reach their domains within a timeout.

Simulations

We have developed a simple lightweight simulator to analyze wireless device movement and to monitor RSSI. Already existing but more complex simulators can't supply so easily and efficiently these feature. We have simulated two extreme trajectories: trajectory1, a straight path with constant random velocity between two random points, and trajectory2, with random variable velocity and with random direction with a Gaussian component of 30 degree standard deviation. In both trajectories the velocity is always between 0.2 and 2.5 m/s to mimic the behavior of walking mobile users. Typically, wireless device performs a cell roaming when the destination cell RSSI rises above actual cell RSSI of a fixed hysteresis threshold. In our simulated environment the hysteresis threshold value ranges from 0 to 2 db. On the average, each mobile client has the contemporaneous visibility of 6 access points, that represents a worst case scenario significantly more complex than the actually deployed wireless networks (where usually no more than 3 access points are visible from any point).

We have tested our proposed prediction solutions in several simulated scenarios, different in number and uniformity of deployed access points. For each scenario we present dimensions, number and density of deployed access point, RSSI distribution (when available), performances with trajecory1 and trajectory2 within 600 simulations for each simulated environment. When in a particular simulated environment handovers are rarely predicted, that is when E1% is really low, AT is not shown because it doesn't present a significant positive value, due to poor performances.

Environment1: uniform AP density

This is the most uniform tested environment. As you can see in figure 2, APs are deployed in a regular squared way. Figure shows RSSI distribution displayed from Ekahau Manager based on the collected RSSI database. AP are where RSSI is stronger.

Dimensions 64m X 64m Number of access points 16 Access point density 256mq / ap Table 1: environment1's characteristics. Figure 1: RSSI in db.

Figure 2: environment1's AP deployment.

Trajectory1	E1%	E1%	E1%	E2%	E2%	E2%	AT (s)	AT (s)	AT (s)
Threshold (db)	0	1	2	0	1	2	0	1	2
RSSI-GM	79.01	91.69	94.67	80.53	74.27	74.19	2.99	4.34	5.30
ECP-GM	9.67	14.89	19.61	30.07	33.24	37.32	---	---	---
ED-GM	21.93	34.99	43.01	40.63	43.79	47.21	---	0.79	2.56

Table 2: RSSI-GM, ECP-GM, and ED-GM performance results in the case of environment1 and trajectory1.

Trajectory2	E1%	E1%	E1%	E2%	E2%	E2%	AT (s)	AT (s)	AT (s)
Threshold (db)	0	1	2	0	1	2	0	1	2
RSSI-GM	75.35	91.00	93.01	78.61	76.31	72.86	2.88	4.12	4.80
ECP-GM	10.37	13.50	20.18	34.10	34.62	38.97	---	---	---
ED-GM	22.22	33.00	37.94	40.34	44.15	43.78	---	0.84	1.91

Table 3: RSSI-GM, ECP-GM, and ED-GM performance results in the case of environment1 and trajectory2.

RSSI-GM outperforms the other solutions for all three performance indicators. EPE performs positioning quite well, but it is less prompt in ascertaining device wireless movements that affects negatively ECP-GM and ED-GM performances. When the hysteresis threshold increases, roaming is delayed and there is more time to predict wireless device roaming: consequently both E1% and AT increase. In this case, RSSI-GM E2% lowers because delayed roaming triggers more predictions, most of them unnecessary.

In summary, RSSI-GM E1% is significant also with a null hysteresis threshold and an higher threshold doesn't make E1% much better. As consequence E2% decreases since NM increases and USP is almost constant. On the contrary ECP-GM and ECP-GM E2% often rises, in particular when E1% increases, because the number of useful predictions increases significantly, proportionally more than total number of predictions. In fact, NM increases but USP increases furtherly.

As expected, the Gaussian Trajectory2 component makes handover prediction more difficult; however, the performance figures exhibit only a slight occasional deterioration.

The next goal is to prove generality of results testing our proposed system in a non-uniform wireless environment.

Environment2: non-uniform AP density

Figure 3 shows a non-uniform AP deployment. AP density is a bit bigger than Environment1's one.

Dimensions 70m X 50m Number of access points 13 Access point density 269.23mq / ap Table 4: environment2's characteristics.

Figure 3: environment2's AP deployment (red points represent APs and green lines are cell borders).

Trajectory1	E1%	E1%	E1%	E2%	E2%	E2%	AT (s)	AT (s)	AT (s)
Threshold (db)	0	1	2	0	1	2	0	1	2
RSSI-GM	73.99	88.59	92.09	72.37	70.87	74.43	2.90	4.72	4.10
ECP-GM	13.00	20.11	17.51	27.62	33.33	24.80	---	---	---
ED-GM	17.94	36.41	41.24	22.35	32.06	33.80	---	1.73	2.43

Table 5: RSSI-GM, ECP-GM, and ED-GM performance results in the case of environment2 and trajectory1.

Trajectory2	E1%	E1%	E1%	E2%	E2%	E2%	AT (s)	AT (s)	AT (s)
Threshold (db)	0	1	2	0	1	2	0	1	2
RSSI-GM	75.13	90.34	94.18	75.32	71.46	71.73	2.55	3.64	4.92
ECP-GM	11.79	15.34	19.94	31.29	31.95	37.89	---	---	---
ED-GM	22.56	32.96	43.21	32.84	37.66	41.49	0.40	0.70	1.96

Table 6: RSSI-GM, ECP-GM, and ED-GM performance results in the case of environment2 and trajectory2.

Performances indicators don't change significantly from Environment1 to Environment2; performance indicators are almost the same in a uniform environment and in a non-uniform one.

Environment3: highly heterogeneous AP density

The last one tested environment has highly heterogeneous AP density. AP deployment doesn't follow any rule. Note AP density is almost the same than in Environment1.

Dimensions 68m X 49m Number of access points 13 Access point density 256.3mq / ap Table 7: environment3's characteristics.

Figure 4: environment3's AP deployment (red points represent APs and green lines are cell borders).

Trajectory1	E1%	E1%	E1%	E2%	E2%	E2%	AT (s)	AT (s)	AT (s)
Threshold (db)	0	1	2	0	1	2	0	1	2
RSSI-GM	79.40	87.50	90.42	77.83	75.23	70.83	4.18	4.13	6.33
ECP-GM	23.11	25.54	31.38	42.59	35.07	40.97	---	---	1.50
ED-GM	37.69	52.17	56.38	35.71	39.83	40.46	2.83	4.17	6.06

Table 8: RSSI-GM, ECP-GM, and ED-GM performance results in the case of environment3 and trajectory1.

Trajectory2	E1%	E1%	E1%	E2%	E2%	E2%	AT (s)	AT (s)	AT (s)
Threshold (db)	0	1	2	0	1	2	0	1	2
RSSI-GM	77.63	84.97	91.02	77.02	72.33	67.41	3.43	3.78	4.40
ECP-GM	22.63	21.31	23.35	48.04	43.58	38.42	0.13	0.35	0.40
ED-GM	35.79	38.80	48.80	41.34	43.69	45.03	2.10	2.47	3.62

Table 9: RSSI-GM, ECP-GM, and ED-GM performance results in the case of environment3 and trajectory2.

RSSI-GM always outperforms other mobility prediction solutions independently from a particular environment. Moreover performance indicators don't change substantially in proposed environments. Notwithstanding AP deployment in Environment1 is completely uniform, its performance indicator values have a general validity.

In-the-Field Experiments

Apart from simulation, we have tested the three different mobility prediction modules over an actual deployment scenarios with 5 partially overlapping IEEE 802.11b wireless cells and 10 client devices (Compaq iPAQ h3850 with Windows CE.NET) randomly roaming in the campus environment. The deployed CISCO Aironet 1100 access points use a null signal strength hysteresis threshold for cell handover triggering. We have imposed other hysteresis thresholds, bigger than in simulated environments according to bigger RSSI fluctuations.

Instead of in simulations where we calculate AP RSSI, now we have to obtain from the wireless card visible AP list with related RSSI. It's not easy to obtain information, as actual AP or visible APs, from wireless cards because of hardware and software heterogeneity. Windows NDIS user-level interface (ndisuio) doesn't appear to be useful due to incompatibility from different Windows versions. Moreover not every wireless card is 100% NDIS-compatible. So it is necessary to implement a different low-level driver for each used wireless card. To avoid those problems Ekahau Client (EC) presents a generic driver for NDIS-compatible cards and also different drivers for each most common wireless card that correctly implements AP'scan but isn't completely NDIS-compatible.

EPE obtains AP list form ECs with the following protocol:

1. EPE periodically looks for active EC in the subnet sending a broadcast "Are you there?" message;
2. ECs answer with a "I'm hire" message;
3. when EPE is interest in monitoring a particular EC, it sends a "Send me RSSI" message;
4. now EC starts to send RSSI information packets (RIP) to EPE repeatedly.

In order to easily obtain visible AP list, we simulate EPE behavior to stimulate ECs to send us RIP. Then we extract from RIP the visible AP list with related RSSI and we save it. Finally as in simulations we create a Grey Model with the most recent saved data to predict RSSI.

Random path	E1%	E1%	E1%	E2%	E2%	E2%	AT (s)	AT (s)	AT (s)
Threshold (db)	3	6	9	3	6	9	3	6	9
RSSI-GM	75.00	91.67	100.0	100.0	100.0	100.0	7.65	9.98	19.24
ECP-GM	37.50	50.00	87.50	75.00	100.0	100.0	---	4.39	12.12
ED-GM	50.00	58.30	100.0	100.0	100.0	100.0	1.01	6.83	14.36

Table 10: RSSI-GM, ECP-GM, and ED-GM performance results in the case of in-the-field experiments.

Hysteresis threshold ranges from 3 to 9 db according to signal strength standard deviation of about 6 db. A null hysteresis threshold induces too many unnecessary reassociations when mobile node is between two AP. On the other hand a too high hysteresis threshold delays too much reassociations. At our knowledge 6 db hysteresis threshold is a good compromise.

With strong signal strength fluctuations RSSI predicted values cross early and so mobility prediction happens early. As consequence E1% end AT of in-the-field experiments are really good. Moreover E2% is quite perfect because mobile nodes always associate in every AP and so there aren't useless predictions.

The experimental results outperform the simulation-based ones, showing that the simulated environment represents a worst case scenario. RSSI-GM shows better performances despite strong signal strength fluctuations observed in a real environment because access points aren't as close as in simulations. For the same reasons also ECP-GM and ED-GM show better performances than in simulation, even if still lower than RSSI-GM ones.

In summary, the RSSI-GM mobility prediction solution has proven to offer the best performance, both in the simulated environment and the actual deployment, at least when the goal is handover prediction and not fine-grained positioning prediction. In particular, RSSI-GM achieves AT values that permit SOMA to move and reorganize the middleware support in the next visited locality for a wide set of Internet services. In addition, if compared with ECP-GM and ED-GM, RSSI-GM has also significant advantages in terms of simplicity since it doesn't need additional components as EPE.