Team Members
Device Discovery
Motivation and Aim
In order for two mobile devices to perform ad-hoc networking, each device must first become aware of the presence of the other. In addition, each device must gain some knowledge of the other device that allows a connection to be made, such as MAC addresses. These are the functions performed by what is known as device discovery, which is performed before any Bluetooth or Wi-Fi connection is set up between mobile devices.
Wi-Fi scanning has been identified as one of the most power consuming functions on Smartphones. Common strategies for performing device discovery rely on the Bluetooth and Wi-Fi radios’ scanning ability. For these strategies, a device must scan every time it wishes to check for devices. Reducing the number of scans that the device performs should then extend the battery life. The acquisition of MAC addresses is often a step in the scanning protocol. If the awareness and MAC address acquisition functions can somehow be separated, then scanning need not be performed as often. The GROUT device discovery system aims to create a way in which the MAC addresses of all Android devices in the vicinity can be acquired by other Android devices, and save power consumption at the same time.
Design and Implementation
The system design was influenced by a number of systems that use surrounding Wi-Fi access points (APs) and Bluetooth devices to establish a relative location (location defined by an object’s position relative to other objects). The GROUT system uses Cellular towers, Wi-Fi Aps and Bluetooth devices as reference points with which to establish its relative location.
The system was also influenced Edward Hall’s theory of proxemics and interpersonal space, which is visualised in the image below.
The theory essentially says that the zone of an individual’s interpersonal space that another person occupies indicates how intimate the relationship between the two individuals is. This idea is used in the system by defining a discovery space around an individual device; space that other devices can occupy.
The GROUT device discovery system is made up of two components; a client application and a web application. The process of discovery is outlined below with screenshots to of the application. The interface is made of a display, and of two buttons. Each button performs a specific function. Buttons need not be pressed in any specific order.
Client collects information regarding itself.
The client application is started and the device collects ways of uniquely identifying itself. Identifiers can be Bluetooth or Wi-Fi MAC addresses, or some other value that is unique to a specific device.
Client scans for nearby access points.
When the scan button is pressed, the client senses the cellular tower to which it is connected. If the device does not have a cellular radio, then this is skipped. The client then performs a scan for Bluetooth and Wi-Fi Aps, and collects their MAC addresses.
Client registers itself and all detected access points on the server.
When the check for friends button is pressed, the client formats all of the above information into a JSON file, and sends it to a remote server. This server reads the file and registers the client, using its unique identifier in a database. The APs that were sensed are also stored in the database.
The server estimates the relative distance between the client and all nearby devices
Using the database, the server works out which other devices share Cellular towers and access points with the client, and how many of each it shares with the client. The number and type of APs that are shared define the zones of the discovery space surrounding the client, as can be seen in the picture below.
Devices that share just one cellular tower will be labelled as being in the same neighbourhood as the client. Devices that share exactly one Wi-Fi AP (and possibly a cellular tower) are labelled as being in the same block. Devices that share more than one Wi-Fi AP are labelled as being in the same building, and devices that share a Bluetooth AP (and possibly Wi-Fi APs) are labelled as being in the same room.
These measurements of distance are known as inter-entity distances¬. Inter-entity distances are the system’s best estimates of distance, they are not absolute. If two devices that are actually in the same only share a cellular tower AP, then the inter-entity distance will be same neighbourhood.
Their must exist a number of Wi-Fi APs that can give the same location information as a single Bluetooth device. A naïve calculation showed that number to be somewhere around 25 Wi-Fi APs. So if two devices share no Bluetooth AP, but do share 25 or more Wi-Fi APs, then the inter-entity distance will be same room. Device limitations make it so that no more than one cellular tower can be sensed at one time, thus the same method cannot be used with cellular towers
The server returns this information to the client.
The server sends a list of devices, their MAC addresses and their inter-entity distance to the client. The client then uses the mac addresses to form an Ad-hoc network Because the system separates the scanning and discovery process, the scanning function need not be performed, unless a device changes its location. This potentially reduces the number of times that scanning occurs, and thus potentially reduces power consumption.
The system is summarized by the image below
Results
The system was evaluated on three factors.
- How often an inter-entity distance of same room was recorded when three devices performed discovery while situated side by side.
- How much battery is used by the two functions of scanning and discovery.
- Because client-server communication requires the transfer of data, the amount of data used for each discovery operation was evaluated.
1. Discovery
The system was tested on three devices, codenamed Jack, Jill and Jess in a number of scenes. As can be seen from the table below, some had Bluetooth devices present in the area, some did not. Some had a large number of Wi-Fi APs in the area, others did not. In all cases, the devices were placed next to each other, and each performed a scan operation, followed by a discovery operation. This was repeated in each location ten times.
The results of the experiment are summarized below.
All of the same room results in this experiment were due to the presence of Bluetooth devices. The number of same block results indicates that only one Wi-Fi AP was shared between often, there was only one Wi-Fi AP shared between devices. Table 1 shows that only scene 3 had less than three visible Wi-Fi APs. This suggests that even when APs are visible they are not necessarily sensed by all devices. This brings into question whether the system is usefel in the absence of Bluetooth devices.
2. Power consumption
Attempts at measuring the power usage did not provide any conclusive evidence that the scan operations used any more power than the discovery operation, as was hypothesised. What was found that on some devices, process such as the display were using far more power than any of the processes involved with device discovery. In these cases, the power use of the GROUT device discovery system is inconsequential.
3. Data Usage
The amount data transferred for every server communication was monitored. It was found that the total amount of data sent was fairly small, less than 3 kilobytes on average. The results are shown in Table 3.
Many cellular service providers charge per kilobyte, so this result is good in the sense that it is not likely to use significant amounts of data. The monitoring process was not entirely accurate, and thus a correlation coefficients were calculated for the between number of APs and data transferred. It was found that there were no strong relationships between data volume and number of Aps. This indicates that some of the data recorded was unrelated to the discovery process; therefore it is likely that the GROUT system uses less data than was recorded.