Wi-Fi positioning "cheap and cheerful." About the frequency of measurements or is Wi-Fi positioning possible in real time?
This is the third, while the final article in the Wi-Fi series of positioning is “cheap and cheerful”: when specialized client devices and specialized infrastructure are not used, but only publicly available personal devices (smartphones, tablets, laptops) and the usual Wi-Fi infrastructure are used.
In the first two articles, I focused on the accuracy and accuracy of positioning, without touching upon the issue of frequency of measurements. If the Client is in a static position, the frequency of measurements is not critical, and if the Client moves, then the frequency of measurements starts to play a significant role.
The starting point when calculating the frequency of measurements is such a characteristic as the characteristic speed of movement of Customers. For a person it is 5km / h or 1.5 m / s. To ensure real-time positioning, the time interval between two measurements should not exceed twice the positioning accuracy, which allows you to build sufficiently accurate for practical purposes the trajectory of movement.
')
The accuracy of the classic positioning of the tests conducted in the previous article was about five meters with 90% confidence. In this case, the frequency of measurements should be at least 6.6 s (or 13.3 seconds for an accuracy of 10 meters). It now remains to find out what the actual measurement frequency is and whether it corresponds to the stated positioning accuracy.
For tests using a smartphone on Android 4.4.4 and a laptop with Windows 7.
Well, the goal is clear, the means are clear, let's get started!
In specialized positioning systems, the frequency of measurements can be controlled at the level of operation of the wireless adapter drivers and software, adjusting the information transfer intervals, thereby adjusting to the client’s characteristic speed and positioning accuracy.
With personal Wi-Fi devices (smartphones, tablets, laptops) the situation is different: we can only work with what is defined in the IEEE 802.11-2012 standards, the manufacturer's drivers, operating system settings.
Access points (TDs) use a Wi-Fi client (Client) signal positioning (RSSI) for positioning. I will name the presence on the TD of one measured signal level of the Customer Measurement.
To solve the positioning problem, it is necessary to have at least one Measurement from three access points. So that there is no confusion, I will call such a set a Sample.
The access points, the Samples of which form the Sample, generally operate on three different channels, say, first, sixth and 11th (this is connected with the work of the IEEE 802.11 standards).
In accordance with the IEEE 802.11 standards, the Wi-Fi adapter can be in one of three states:
- transmission (Tx)
- reception (Rx)
- monitoring (CCA - Clear Channel Assessment)
If the AP does not transmit or receive, it is in the monitoring mode of its channel (in particular, to assess the virtual (CCA-CS, Carrier Sense) and physical (CCA-ED, Energy Detect) channel occupancy).
If the Client is in the zone of confident reception of one access point, then it transmits and receives on one channel. Returning to what the Sample is formed from, the question arises how the Sample is formed if the Client works only in one channel and the Measurements must be on three different channels?
Modern access points spend a small amount of time on monitoring adjacent channels, but since the main task of access points is customer service, and monitoring of all channels occurs consistently, the time spent on an adjacent channel is very small. For example, in Cisco infrastructure, the access point bypasses all channels in 16 seconds. In this case, the probability of "catching" The customer is measured on the adjacent channel is small. Therefore, we dismiss this method.
For the monitoring of adjacent channels, manufacturers often use additional radio. These technologies include Cisco FastLocation. The monitoring module goes through all possible channels, but it is much longer on each channel. But again, this luxury is not available to us under the terms of the task. In more detail, Cisco FastLocation technology, I am going to devote a separate article.
In a wireless environment, there are a huge number of processes that go unnoticed by the user. There are three types of packets (Data, Control, Management) and at least 39 types of frames, and there is only one frame (and one mode of operation of the wireless client) that allows you to solve the problem.
This is active scanning mode, when the Client is actively (sending Probe Request packets) scanning all available channels for the presence of a suitable wireless network. Probe Request, as a management frame, is sent at maximum power and at the lowest transmission rate. It is this mode that allows access points operating on other channels to get the Measurement from the Client and form a Sample.
There are at least two modes of operation when scanning is used:
1. When the client selects a suitable access point to connect to the wireless network
2. When the client selects a suitable access point during the transition from point to point (during roaming)
The client has two mechanisms for scanning the radio environment:
- passive scanning
- active scanning
In the first case, the wireless client listens to beacon packets (sent every 102.4 ms by default), in the second case it sends a probe request and waits for a probe response.
Obviously, this is a matter of choosing between the scanning speed and the energy expended on it (the most expensive mode of operation of a wireless client is transmission).
Suppose we scan in the 2.4 GHz band in Russia, where 13 channels are allowed. The wireless client receiver should obviously be at least 102.4ms (the standard interval between beacon packets) in monitoring mode on each channel. The full scan cycle takes around 1.4s.
The client sends a request to the channel (Probe Request). Access points operating on this channel and having heard the request, respond to it with information about the available wireless segments (SSID).
A request can be directed (containing a specific SSID) - directed probe request, in this case, the AP should respond with information only about that SSID (if it is on it).
A request can be omnidirectional (Null Probe Request), in this case, the AP that has heard this packet must provide information on all configured SSIDs.
The client sends a Probe Request on the first channel and launches ProbeTimer. The value of ProbeTimer is not standardized and may vary depending on the implementation of network adapter drivers, but in general it is 10ms. During this time, the wireless client processes responses (Probe Response from TD). Then it goes to the next channel and so on all channels. Then decides which TD to connect to.
The full scan cycle in this case takes about 130ms, which is about an order of magnitude less than passive scanning.
Each manufacturer chooses the type of scan and the conditions of its application. Also in the operating system itself may be options that allow you to select a particular mode.
From my point of view, after connecting to the SSID and being in the zone of confident reception of one access point, the Client should not send a Probe Request at all.
The Cisco vendor says that the transmission interval can be from 10 seconds to 5 minutes, depending on the type of client, OS, driver, battery, customer activity (http://www.cisco.com/c/en/us/td /docs/wireless/controller/technotes/8-0/CMX_FastLocate_DG/b_CMX-FastLocate-DG.html).
It turns out that the theory is somewhat contrary to practice, so tests are needed here.
First, tests were subjected to a laptop in a static position, connected to the network, the maximum consumption mode. On one profile, I had “connect automatically” and “connect, even if the network does not broadcast my name (SSID).
The result showed that the system sends an omnidirectional Probe request to all channels about once a minute regardless of anything.
That is, the system, being in a static position, in the zone of confident reception of one TD, still sends Probe request to all channels every minute (for each request all access points send a probe response, which generates considerable traffic). In Maximum Battery Life mode, the laptop showed the same result.
It is also clear that each time the Client sends more than one request, but several at once, with a very small time interval.
The number of Probe Request and the number of samples on the Cisco CMX match. Moreover, it is clear from the logs that several Measurements come once a minute (as the analyzer shows), but CMX obviously combines such requests (and does it right), as the counter increased every minute by one. It looked like this:
In motion, the periodicity changed and a connection with the roaming moment appeared. As the analyzer showed, before the moment of roaming, the laptop sent a Probe Request to all channels, that is, it performed an active scanning procedure.
Here an interesting effect arises: the faster a person moves, the more often roaming occurs. But, unfortunately, roaming occurs somewhat less frequently than every 10 meters (doubled accuracy). The client keeps “until the last” for the access point and only at the last moment switches to a new one. As a result, roaming occurred no less than every 15–20 meters, which is approximately twice as much as required, as a result, we have a not very reliable trajectory of movement (see the previous article).
Next, I conducted tests with a smartphone based on Android 4.4.4. The smartphone has two modes of operation: active and sleep. In sleep mode, there are several options for work. For the tests, I used the loudest mode “Never”.
The results were as follows.
If the smartphone was in place, and I did not use it, the delays were about 500-600 seconds. Even during the period of active surfing, the delays were about 100 seconds. A more frequent update was obtained by viewing the wireless networks (at that moment requests were sent.
In motion, the results were similar to a laptop, that is, there was a direct connection between sending packages and roaming.
1. In classic Wi-Fi positioning, measurements are made by Probe Request packets.
2. On personal devices (laptops, tablets, smartphones), the frequency of sending a Probe Request depends on a large number of factors: device type, OS, driver type and settings, battery status, client activity and can be from 5 seconds to 10 minutes. But!
3. There is a direct link between the speed of movement of the client (roaming frequency) and the frequency of sending Probe Request. If the client is in a static position, then the frequency of measurements is small (but she doesn’t need a big one!). And in the case of movement, Probe Request starts to form on the roaming event. But!
4. The frequency of sending a Probe Request for roaming is insufficient (more than twice the positioning accuracy) and with uniform motion it can be 10-15 seconds (and it takes at least 5-10 seconds), which leads to a deterioration of positioning accuracy in motion not less than twice.
Many manufacturers are trying to optimize the performance of their devices to increase the operating time of the device and the first candidate for optimization is the “active scan” mode. This also leads to the fact that such devices as the iPhone and Android, too, have rarely used this mode of operation, but in the case of roaming, they have not yet departed from using Probe Request.
Unfortunately, IEEE 802.11k protocol, which is included in the new version of the 802.11-2012 standard, also comes to the aid of manufacturers. This standard assumes exactly the function that active scanning is currently performing when roaming.
Due to the active work of manufacturers towards lower power consumption and the introduction of the 802.11k standard, one can hardly expect improvements in this direction.
There remains a use case for measuring data packets (Data frame). In this case, we logically come to the consideration of Cisco FastLocaton technology in the next article.
PS Below is a small digression about active Wi-Fi tags, about which, if you can work with them, there will be a separate article.
In the case of the use of active Wi-Fi tags, we can customize their work, as we need. The software is configured in such a way that the label is always in sleep mode, wakes up with a certain periodicity to send a Probe Request to all channels, and then falls asleep. With this mode of operation, you can achieve the required update frequency and the required battery life.
Here is an example of an active tag that wakes up every 90 seconds to send a Probe Request, running on two AA batteries for about 27 days.
PPS Small add. Support for the 802.11k protocol can both worsen and improve Wi-Fi positioning. While nothing more specifically I can not say, because the topic has not been studied, I will try to sanctify in the future.
In the first two articles, I focused on the accuracy and accuracy of positioning, without touching upon the issue of frequency of measurements. If the Client is in a static position, the frequency of measurements is not critical, and if the Client moves, then the frequency of measurements starts to play a significant role.
The starting point when calculating the frequency of measurements is such a characteristic as the characteristic speed of movement of Customers. For a person it is 5km / h or 1.5 m / s. To ensure real-time positioning, the time interval between two measurements should not exceed twice the positioning accuracy, which allows you to build sufficiently accurate for practical purposes the trajectory of movement.
')
The accuracy of the classic positioning of the tests conducted in the previous article was about five meters with 90% confidence. In this case, the frequency of measurements should be at least 6.6 s (or 13.3 seconds for an accuracy of 10 meters). It now remains to find out what the actual measurement frequency is and whether it corresponds to the stated positioning accuracy.
For tests using a smartphone on Android 4.4.4 and a laptop with Windows 7.
Well, the goal is clear, the means are clear, let's get started!
In specialized positioning systems, the frequency of measurements can be controlled at the level of operation of the wireless adapter drivers and software, adjusting the information transfer intervals, thereby adjusting to the client’s characteristic speed and positioning accuracy.
With personal Wi-Fi devices (smartphones, tablets, laptops) the situation is different: we can only work with what is defined in the IEEE 802.11-2012 standards, the manufacturer's drivers, operating system settings.
Frequency of measurements, and what is it?
Access points (TDs) use a Wi-Fi client (Client) signal positioning (RSSI) for positioning. I will name the presence on the TD of one measured signal level of the Customer Measurement.
To solve the positioning problem, it is necessary to have at least one Measurement from three access points. So that there is no confusion, I will call such a set a Sample.
Is it difficult to get a sample?
The access points, the Samples of which form the Sample, generally operate on three different channels, say, first, sixth and 11th (this is connected with the work of the IEEE 802.11 standards).
In accordance with the IEEE 802.11 standards, the Wi-Fi adapter can be in one of three states:
- transmission (Tx)
- reception (Rx)
- monitoring (CCA - Clear Channel Assessment)
If the AP does not transmit or receive, it is in the monitoring mode of its channel (in particular, to assess the virtual (CCA-CS, Carrier Sense) and physical (CCA-ED, Energy Detect) channel occupancy).
If the Client is in the zone of confident reception of one access point, then it transmits and receives on one channel. Returning to what the Sample is formed from, the question arises how the Sample is formed if the Client works only in one channel and the Measurements must be on three different channels?
Modern access points spend a small amount of time on monitoring adjacent channels, but since the main task of access points is customer service, and monitoring of all channels occurs consistently, the time spent on an adjacent channel is very small. For example, in Cisco infrastructure, the access point bypasses all channels in 16 seconds. In this case, the probability of "catching" The customer is measured on the adjacent channel is small. Therefore, we dismiss this method.
For the monitoring of adjacent channels, manufacturers often use additional radio. These technologies include Cisco FastLocation. The monitoring module goes through all possible channels, but it is much longer on each channel. But again, this luxury is not available to us under the terms of the task. In more detail, Cisco FastLocation technology, I am going to devote a separate article.
Where did the sample come from then ?!
In a wireless environment, there are a huge number of processes that go unnoticed by the user. There are three types of packets (Data, Control, Management) and at least 39 types of frames, and there is only one frame (and one mode of operation of the wireless client) that allows you to solve the problem.
This is active scanning mode, when the Client is actively (sending Probe Request packets) scanning all available channels for the presence of a suitable wireless network. Probe Request, as a management frame, is sent at maximum power and at the lowest transmission rate. It is this mode that allows access points operating on other channels to get the Measurement from the Client and form a Sample.
Why does the client send these requests?
There are at least two modes of operation when scanning is used:
1. When the client selects a suitable access point to connect to the wireless network
2. When the client selects a suitable access point during the transition from point to point (during roaming)
The client has two mechanisms for scanning the radio environment:
- passive scanning
- active scanning
In the first case, the wireless client listens to beacon packets (sent every 102.4 ms by default), in the second case it sends a probe request and waits for a probe response.
Obviously, this is a matter of choosing between the scanning speed and the energy expended on it (the most expensive mode of operation of a wireless client is transmission).
Passive scan
Suppose we scan in the 2.4 GHz band in Russia, where 13 channels are allowed. The wireless client receiver should obviously be at least 102.4ms (the standard interval between beacon packets) in monitoring mode on each channel. The full scan cycle takes around 1.4s.
Active scan
The client sends a request to the channel (Probe Request). Access points operating on this channel and having heard the request, respond to it with information about the available wireless segments (SSID).
A request can be directed (containing a specific SSID) - directed probe request, in this case, the AP should respond with information only about that SSID (if it is on it).
A request can be omnidirectional (Null Probe Request), in this case, the AP that has heard this packet must provide information on all configured SSIDs.
The client sends a Probe Request on the first channel and launches ProbeTimer. The value of ProbeTimer is not standardized and may vary depending on the implementation of network adapter drivers, but in general it is 10ms. During this time, the wireless client processes responses (Probe Response from TD). Then it goes to the next channel and so on all channels. Then decides which TD to connect to.
The full scan cycle in this case takes about 130ms, which is about an order of magnitude less than passive scanning.
Each manufacturer chooses the type of scan and the conditions of its application. Also in the operating system itself may be options that allow you to select a particular mode.
What frequency of scanning by Probe Request can I expect?
From my point of view, after connecting to the SSID and being in the zone of confident reception of one access point, the Client should not send a Probe Request at all.
The Cisco vendor says that the transmission interval can be from 10 seconds to 5 minutes, depending on the type of client, OS, driver, battery, customer activity (http://www.cisco.com/c/en/us/td /docs/wireless/controller/technotes/8-0/CMX_FastLocate_DG/b_CMX-FastLocate-DG.html).
It turns out that the theory is somewhat contrary to practice, so tests are needed here.
Probe Request Parcel Frequency Measurement
First, tests were subjected to a laptop in a static position, connected to the network, the maximum consumption mode. On one profile, I had “connect automatically” and “connect, even if the network does not broadcast my name (SSID).
The result showed that the system sends an omnidirectional Probe request to all channels about once a minute regardless of anything.
That is, the system, being in a static position, in the zone of confident reception of one TD, still sends Probe request to all channels every minute (for each request all access points send a probe response, which generates considerable traffic). In Maximum Battery Life mode, the laptop showed the same result.
It is also clear that each time the Client sends more than one request, but several at once, with a very small time interval.
Is there a correlation between the sending rate of the Probe Request and the sampling rate of the Cisco CMX?
The number of Probe Request and the number of samples on the Cisco CMX match. Moreover, it is clear from the logs that several Measurements come once a minute (as the analyzer shows), but CMX obviously combines such requests (and does it right), as the counter increased every minute by one. It looked like this:
TIMESTAMP :Fri Aug 26 10:43:12 MSK 2016 TIMESTAMP :Fri Aug 26 10:43:12 MSK 2016 TIMESTAMP :Fri Aug 26 10:43:12 MSK 2016 TIMESTAMP :Fri Aug 26 10:43:12 MSK 2016 TIMESTAMP :Fri Aug 26 10:43:12 MSK 2016 TIMESTAMP :Fri Aug 26 10:43:12 MSK 2016 TIMESTAMP :Fri Aug 26 10:44:12 MSK 2016 TIMESTAMP :Fri Aug 26 10:44:12 MSK 2016 TIMESTAMP :Fri Aug 26 10:44:12 MSK 2016 TIMESTAMP :Fri Aug 26 10:44:12 MSK 2016 TIMESTAMP :Fri Aug 26 10:44:12 MSK 2016 TIMESTAMP :Fri Aug 26 10:45:12 MSK 2016 TIMESTAMP :Fri Aug 26 10:45:12 MSK 2016 TIMESTAMP :Fri Aug 26 10:45:12 MSK 2016 TIMESTAMP :Fri Aug 26 10:45:12 MSK 2016 TIMESTAMP :Fri Aug 26 10:45:12 MSK 2016 TIMESTAMP :Fri Aug 26 10:46:14 MSK 2016 TIMESTAMP :Fri Aug 26 10:46:14 MSK 2016 TIMESTAMP :Fri Aug 26 10:46:14 MSK 2016 TIMESTAMP :Fri Aug 26 10:46:14 MSK 2016 TIMESTAMP :Fri Aug 26 10:46:14 MSK 2016 TIMESTAMP :Fri Aug 26 10:47:12 MSK 2016 TIMESTAMP :Fri Aug 26 10:47:12 MSK 2016 TIMESTAMP :Fri Aug 26 10:47:12 MSK 2016 TIMESTAMP :Fri Aug 26 10:47:12 MSK 2016 TIMESTAMP :Fri Aug 26 10:47:12 MSK 2016 TIMESTAMP :Fri Aug 26 10:48:12 MSK 2016 TIMESTAMP :Fri Aug 26 10:48:12 MSK 2016 TIMESTAMP :Fri Aug 26 10:48:12 MSK 2016 TIMESTAMP :Fri Aug 26 10:48:12 MSK 2016 Frequency of measurements in motion
In motion, the periodicity changed and a connection with the roaming moment appeared. As the analyzer showed, before the moment of roaming, the laptop sent a Probe Request to all channels, that is, it performed an active scanning procedure.
Here an interesting effect arises: the faster a person moves, the more often roaming occurs. But, unfortunately, roaming occurs somewhat less frequently than every 10 meters (doubled accuracy). The client keeps “until the last” for the access point and only at the last moment switches to a new one. As a result, roaming occurred no less than every 15–20 meters, which is approximately twice as much as required, as a result, we have a not very reliable trajectory of movement (see the previous article).
Next, I conducted tests with a smartphone based on Android 4.4.4. The smartphone has two modes of operation: active and sleep. In sleep mode, there are several options for work. For the tests, I used the loudest mode “Never”.
The results were as follows.
If the smartphone was in place, and I did not use it, the delays were about 500-600 seconds. Even during the period of active surfing, the delays were about 100 seconds. A more frequent update was obtained by viewing the wireless networks (at that moment requests were sent.
In motion, the results were similar to a laptop, that is, there was a direct connection between sending packages and roaming.
Main conclusions
1. In classic Wi-Fi positioning, measurements are made by Probe Request packets.
2. On personal devices (laptops, tablets, smartphones), the frequency of sending a Probe Request depends on a large number of factors: device type, OS, driver type and settings, battery status, client activity and can be from 5 seconds to 10 minutes. But!
3. There is a direct link between the speed of movement of the client (roaming frequency) and the frequency of sending Probe Request. If the client is in a static position, then the frequency of measurements is small (but she doesn’t need a big one!). And in the case of movement, Probe Request starts to form on the roaming event. But!
4. The frequency of sending a Probe Request for roaming is insufficient (more than twice the positioning accuracy) and with uniform motion it can be 10-15 seconds (and it takes at least 5-10 seconds), which leads to a deterioration of positioning accuracy in motion not less than twice.
What should pay attention
Many manufacturers are trying to optimize the performance of their devices to increase the operating time of the device and the first candidate for optimization is the “active scan” mode. This also leads to the fact that such devices as the iPhone and Android, too, have rarely used this mode of operation, but in the case of roaming, they have not yet departed from using Probe Request.
Unfortunately, IEEE 802.11k protocol, which is included in the new version of the 802.11-2012 standard, also comes to the aid of manufacturers. This standard assumes exactly the function that active scanning is currently performing when roaming.
Due to the active work of manufacturers towards lower power consumption and the introduction of the 802.11k standard, one can hardly expect improvements in this direction.
There remains a use case for measuring data packets (Data frame). In this case, we logically come to the consideration of Cisco FastLocaton technology in the next article.
PS Below is a small digression about active Wi-Fi tags, about which, if you can work with them, there will be a separate article.
In the case of the use of active Wi-Fi tags, we can customize their work, as we need. The software is configured in such a way that the label is always in sleep mode, wakes up with a certain periodicity to send a Probe Request to all channels, and then falls asleep. With this mode of operation, you can achieve the required update frequency and the required battery life.
Here is an example of an active tag that wakes up every 90 seconds to send a Probe Request, running on two AA batteries for about 27 days.
PPS Small add. Support for the 802.11k protocol can both worsen and improve Wi-Fi positioning. While nothing more specifically I can not say, because the topic has not been studied, I will try to sanctify in the future.
Source: https://habr.com/ru/post/309308/
All Articles