Computational optimality of combined sweeping-jumping algorithm for connectivity-based node insertion in Wi-Fi sensor networks

Abstract The connectivity-based Medium Access Control (MAC) protocol leverages node connectivity in a wireless LAN to derive an optimal polling sequence, enabling the Access Point (AP) to utilize wireless bandwidth more efficiently when polling each node. However, when the Constraint Satisfaction Problem (CSP) algorithm is applied to generate the optimal sequence, the required computation time varies with the connectivity characteristics of the network; in some cases, such as a Wi-Fi sensor network with 1,000 sensors, it takes excessively long (over 14 seconds on average). To overcome this limitation, a new polling sequence derivation method, called the combined sweeping-jumping algorithm, has been developed. In this paper, we theoretically and experimentally demonstrate that the combined sweeping-jumping algorithm is the computationally optimal solution for the connectivity-based node insertion method.