# Combined Sweeping and Jumping Method to Enhance Node Insertion Algorithm for Wi-Fi Sensor Networks
## 1 Introduction
The connectivity-based multipolling MAC protocol was employed for the direct communication between nodes in [13], and for the reliable multicast transmission in [14]. In [13; 14], the backtracking algorithm was employed to derive the minimal number of serially connected multipolling sequences for the nodes in Wi-Fi networks. However, in some cases of Wi-Fi networks with a large number of nodes, more than 100, the backtracking algorithm consumes excessive time to derive the minimal number of serially connected multipolling sequences. The search space of possible multipolling sequences of nodes should be reduced to alleviate the problem of excessive time taken by the backtracking algorithm so that Wi-Fi networks are seamlessly evolved to wireless sensor networks. In [4], the node insertion algorithm was proposed to reduce the search space of multipolling sequences of sensors by composing the multipolling sequences in the manner by which the new sensors are inserted that have the greatest connectivities with the recently inserted sensors, without retracting the existing sensors in the multipolling sequences in the process. Whereas the backtracking algorithm has the computational complexity of \(O(l! )\), the node insertion algorithm has the computational complexity of \(O(l^{3})\). As the numbers of sensors existing in wireless sensor networks grow, the numbers of derived \begin{table}
\begin{tabular}{c c c} \hline \hline
**MAC Protocol** & **Channel Access Method** & **Appropriate Network Scenario** \\ \hline \multirow{3}{*}{DCF} & \multirow{3}{*}{Contention-Based} & Small Network with Small Number of \\  & & Attempts of Simultaneous \\  & & Transmissions \\ \hline \multirow{3}{*}{PCF} & \multirow{3}{*}{Contention-Free and Polling-Based} & Large Network with Large Number of \\  & & Attempts of Simultaneous \\ \cline{1-1}  & & Transmissions \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Comparison between DCF and PCF Protocols. serially connected multipolling sequences converge to 1. The search space of multipolling sequences of sensors still needs to be reduced so that the connectivity-based multipolling MAC protocol is more easily applied to wireless sensor networks. To further reduce the search space of multipolling sequences of sensors, the new sweeping method eliminates the repetitive search for the connectivity information with the sensors that have been inserted. To accelerate the search process, over the two-dimensional search space of the connectivity information between the inserted sensors and the remaining sensors that have not been inserted yet, the jumping method skips the unnecessary search. Thanks to the combined sweeping and jumping method, the node insertion algorithm can be enhanced so that the resulting computational complexity is reduced to \(O(l^{2})\). This paper is organized as follows. Following the introduction, in the next section, the proposed combined sweeping and jumping method is introduced. Numerical results are presented to validate the proposed combined sweeping and jumping method in Section 3. The issues including scalability, hardware implementation, and performance metrics of data loss and delay that are relevant to the node insertion algorithm with the combined sweeping and jumping method are discussed in Section 4. Finally, some conclusions are drawn, and future research themes are suggested in Section 5.