An Optimized algorithm for device discovery using BLE

Yan Zhang, Zheng Song, Wendong Wang, Ye Tian2016 · DOI

Abstract

There are more and more mobile smart devices with high capabilities in both computing and storage, leading to device cooperation in vicinity becoming popular. As the first step in device cooperation, the device discovery process is particularly important. Because of the mobility of devices and the limitation of energy, how to perform the device discovery process efficiently is the key to device cooperation. This paper compares existing wireless communication technologies and proposes an optimized algorithm for device discovery using Bluetooth Low Energy (BLE).

Introduction

The proliferation of powerful mobile devices like smartphones, tablets, and wearables has enabled "vicinity cooperation," where devices share resources such as computing power or storage. However, before any cooperation can occur, a device must successfully identify and connect with its neighbors. This initial phase, known as device discovery, faces significant hurdles due to device mobility and strict energy constraints.

Conceptual model of vicinity device discovery within a range R.

In a typical scenario, a Request Device (RD) seeks to identify Assist Devices (ADs) within a specific range $R$. As devices move in and out of this range, the RD must maintain an accurate list of available neighbors without depleting its battery. Traditional methods often fail to balance the need for high-frequency updates with the limited power supply of mobile hardware.

The Discovery Challenge: Protocol Selection

The authors evaluated several wireless protocols for this task to determine the most efficient baseline:

  • NFC: Limited by an extremely short range (~0.1m), making it unsuitable for most vicinity cooperation tasks.
  • WiFi/WiFiP2P: While offering high data rates, these protocols consume significant power. Experiments showed that maintaining a UDP listening state for four hours resulted in an 18% battery drop.
  • Bluetooth Low Energy (BLE): Offers a range of approximately 100m with significantly lower power consumption (15% battery drop in similar tests).
Comparison of discovery sequences: BLE (left) vs. WiFi/UDP (right).

As shown in the comparison above, BLE simplifies the discovery process by using advertising and scanning states that are inherently more energy-efficient than the continuous listening required by WiFi-based socket connections.

Proposed Optimized Discovery Algorithm

To further improve efficiency, the authors developed an algorithm that dynamically adjusts scanning parameters based on environmental stability. The core logic relies on a "similarity coefficient" ($r$) calculated between consecutive scans.

The "Shortcut" Logic

To minimize computational overhead, the algorithm employs a two-step comparison:

  1. Count Comparison: It first compares the number of devices found in the current scan ($num_i$) with the previous scan ($num_{i-1}$).
  2. ID Comparison: Only if the counts are identical does the algorithm perform the more expensive task of comparing the actual device IDs (MAC addresses or UUIDs).

Dynamic Adjustment

The algorithm adapts to the user's environment based on the similarity coefficient:

  • High Mobility ($r < 1$): If the device list is changing frequently, the algorithm assumes high mobility. It decreases the scan interval and increases scan duration to ensure high accuracy.
  • Stable Environment ($r \ge 1$): If the environment is static (e.g., a user sitting in an office), the algorithm increases the scan interval and decreases duration to conserve energy.

Experimental Evaluation

The algorithm was tested using a physical testbed consisting of a Nexus 9 tablet (RD) and four ADs (two Nexus 6 and two iPhones). The experiments focused on two primary scenarios:

Static Scenario

In a controlled environment where devices remained stationary, the optimized algorithm achieved 98% accuracy—matching the performance of a "constant scanning" approach—while reducing battery consumption from 22% to 17% over the test period.

Dynamic Scenario

In a scenario with moving devices, the optimized algorithm significantly outperformed a fixed-interval scanning scheme:

  • Accuracy: 97.34% (Optimized) vs. 94.58% (Fixed Interval).
  • Energy Efficiency: The optimized approach consumed only 17% battery, compared to 22% for constant scanning.

Conclusion

The proposed BLE-based optimized algorithm successfully balances the trade-off between discovery accuracy and energy consumption. By dynamically adjusting to the mobility of the surrounding environment, it provides the reliability of continuous scanning with the energy profile of periodic scanning. Future work will focus on scaling the algorithm to handle "crowded" environments with hundreds of devices and investigating the impact of 2.4GHz signal interference on discovery reliability.

Summary updated

Abstract

There are more and more mobile smart devices with high capabilities in both computing and storage, which leading to the device cooperation in vicinity becomes popular. As the first step in the device cooperation, the device discovery process is particularly important. Because of the mobility of the devices and the limitation of the energy, how to perform the device discovery process efficiently is the key of the device cooperation. However, the devices support not only one type of wireless communication modules, choose which module to perform the device discovery is the first issue to think about. This paper compares the existing wireless communication technologies and find the suitable method. Then proposes an optimized algorithm for the device discovery using Bluetooth Low Energy (BLE).
BibTeX
@misc{zhang2016optimized,
  author = {Yan Zhang and Zheng Song and Wendong Wang and Ye Tian},
  title = {{An Optimized algorithm for device discovery using BLE}},
  year = {2016},
  doi = {10.2991/icmmita-16.2016.23},
}

Loading related content...

Figure