## 4 Efficient Node Insertion Algorithm
### Description of Algorithm  
We assume a wireless LAN consisting of an AP and Wi-Fi sensors associated with the AP. Each low-power Wi-Fi sensor was assumed to be able to transmit its data frame directly to the AP at a relatively low transmission speed, as in [7]. The connectivity-based multipolling MAC protocol was employed for each Wi-Fi node to transmit its uplink data frames to the AP. In this subsection, the node insertion algorithm is explained, by which the serially connected multipolling sequences of Wi-Fi sensor nodes necessary for the connectivity-based multipolling MAC protocol are derived. An unselected node can be randomly selected as the first Wi-Fi node of a new serially connected multipolling sequence. When inserting a new Wi-Fi node into the serially connected multipolling sequence of nodes being constructed, the primary condition for selecting the next Wi-Fi node is that it should be connected from the most recently added node in the sequence. However, suppose multiple Wi-Fi nodes connected from the most recently added node are available. In that case, a secondary condition is proposed for selecting the next Wi-Fi node. After selecting the new Wi-Fi node for the sequence, the connectivity of the remaining Wi-Fi nodes that have not been selected is maximized. The connectivity of a set \(S\) of nodes is defined as the number of ordered pairs \((i,j)\) such that node \(j\) is connected from node \(i\), \(i\
eq j\), and \(i\) and \(j\) are in \(S\). If no new Wi-Fi node satisfies the first condition, the current serially connected multipolling sequence is closed, and a new serially connected multipolling sequence of nodes begins to be constructed by selecting the random remaining Wi-Fi node as the first node of the new serially connected multipolling sequence. Let us consider only the first condition for selecting the next Wi-Fi node to be added to the serially connected multipolling sequence. A minimal number of serially connected multipolling sequences may not be constructed for the remaining Wi-Fi nodes because the connectivity of the set of the remaining Wi-Fi nodes may not be maximized. Note that in Figure 2, if node 4 is selected as the next node after the addition of nodes 1 and 3 to the first serially connected multipolling sequence, the connectivity of the set of remaining nodes 2, 5, 6,..., 10 is not maximized because node 2 is not connected to any other remaining node. The easy way of implementing the primary and secondary conditions for selecting the next Wi-Fi node that is to be inserted into a serially connected multipolling sequence in construction is that the Wi-Fi nodes are searched that are simultaneously connected from the \(m\) (=1, 2,...) most recently added nodes in the sequence. As the next node, a Wi-Fi node  
Figure 2: Example of node deployment in a row. Each circle represents a node, and each bidirectional arrow represents mutual connectivity between a pair of nodes. is selected that is simultaneously connected from as many most recently added nodes in the sequence as possible. By selecting the next node, the selected Wi-Fi node is most likely to be connected from the smallest number of nodes that have not been selected so that the connectivity of the set of the remaining nodes that have not been selected is maximized. Note that in Figure 2, after the addition of nodes 1 and 3 to the first serially connected multipolling sequence in the construction, node 2 has the largest number of nodes in the current sequence from which it is connected and has the smallest number of unselected nodes from which it is connected, so that the connectivity of the set of the remaining nodes 4, 5, 6,..., and 10 is maximized. \(m\) should not exceed the number of Wi-Fi nodes in the current sequence during construction.