A Graph-Theoretic and Stochastic Analysis of BLE-Assisted Cooperative Wi-Fi Scanning

Abstract

Wi-Fi stations (STAs) repeatedly scan channels to maintain access-point information, but a conventional full Wi-Fi scan incurs substantial delay and energy overhead. SplitScan mitigates this cost by allowing neighboring STAs to exchange reports through Bluetooth Low Energy (BLE) advertisements and divide channel-set scanning responsibilities. We develop a graph-theoretic and stochastic framework for this cooperation over a tri-band channel-set space. For fixed BLE graphs, the framework models cooperation through closed-neighborhood coverage, yielding topology-dependent load limits and a centralized min–max reference for evaluating distributed assignments based on neighbor reports. For spatially random deployments, a random geometric model captures density-dependent load scaling and yields an energy break-even condition. To address report loss, Robust SplitScan-r uses redundant scan assignments to improve reliability. Monte Carlo simulations show that increasing the mean BLE neighbor count from 0.45 to 9.0 reduces the mean Responsible Channel Set (RCS) load from 21.9 to 5.1 sets, a 77% decrease. At an empirical mean degree of 6.68, the mean maximum load is 13.8 sets for SplitScan and 25 sets for SplitScan without the load threshold, while the centralized greedy and exact min–max assignments achieve 8.2 and 7.8 sets, respectively. When each BLE report is delivered with probability 0.9, increasing redundancy from r=1 to r=3 lowers the bound on missing scan information for a channel set from 10−1 to 10−3, while increasing the scan energy. Overall, BLE connectivity determines the attainable cooperative-scanning gain, and the centralized comparisons quantify the maximum-load difference between distributed decisions based on neighbor reports and centralized assignments.