## 4 Efficient Node Insertion Algorithm  
### Motivational Idea  
When sequencing nodes in a serially connected manner, the previous scheduling algorithm employed by the connectivity-based multipolling MAC protocol considered only the connectivity from the most recently added node in a sequence to select the next node. This may result in selecting the next node not connected to other recently added nodes in the sequence by skipping nodes simultaneously connected to multiple recently added nodes. Therefore, as the scheduling algorithm progresses, the remaining nodes that have not been added to the sequences may not have sufficient connectivity; thus, the scheduling algorithm may fail to construct a minimal number of serially connected multipolling sequences for the remaining nodes in real time. For example, Figure 2 shows that ten nodes 1, 2, \(\ldots\), and 10 are deployed in a row, and nodes \(i\) and \(j\) for \(\left.\left|i-j\right.\right|<3\) are mutually connected. Let us consider only the connectivity from the most recently added node in the sequence to insert a new node into a serially connected multipolling sequence. Three serially connected multipolling sequences: (1, 3, 4, 6, 7, 9, 10, and 8), (2), and (5) can be constructed. The scheduling algorithm randomly selects the next nodes among the nodes that are connected from the most recently added nodes in the first multipolling sequence. For example, after the insertion of node 1, the scheduling algorithm randomly selects node 3 among nodes 2 and 3, which are connected from node 1. After constructing the first multipolling sequence (1, 3, 4, 6, 7, 9, 10, and 8), the remaining nodes 2 and 5 are not connected. However, a single serially connected multipolling sequence (1, 2, 3, 4, 5, 6, 7, 8, 9, and 10) can cover ten nodes. Although the scheduling algorithm can find the minimal number of serially connected multipolling sequences by a backtracking search in the end, as the number of nodes in a wireless LAN increases, the possibility of the previous scheduling algorithm being able to find the minimal number of serially connected multipolling sequences in real time significantly decreases.  
Figure 1: Connectivity-based multipolling process. (**a**) Initialization phase. (**b**) Multipolling phase. Rsp represents response frame.  
The optimization problem for constructing the minimal number of serially connected multipolling sequences that covers a set of nodes can generally be formulated as a TSP [1; 2; 3; 4]. When a relatively small number of nodes exist in wireless LANs, it is beneficial to solve the general TSP problem using a backtracking algorithm. However, when many nodes exist in wireless LANs, which may be the case with Wi-Fi sensor networks, solving the TSP problem using a backtracking algorithm can be extremely time consuming in some cases. As the number of Wi-Fi sensor nodes grows in wireless LANs, the connectivity from the most recently added multiple nodes in a serially connected multipolling sequence in construction should be considered to insert a new node into the sequence so that the search space becomes smaller. The nodes simultaneously connected from the most recently added multiple nodes are not skipped from being inserted into the serially connected multipolling sequence in construction. Moreover, to save the time required by the newly proposed node insertion algorithm, it does not backtrack or undo any insertion of the previous node in sequence. The proposed node insertion algorithm is explained in the following subsection.