# Combined Sweeping and Jumping Method to Enhance Node Insertion Algorithm for Wi-Fi Sensor Networks
## 2 Combined Sweeping and Jumping Method
Then, \(S_{6}=\{4,7,8\}\) can be obtained because \(C_{6,4}=C_{6,7}=C_{6,8}=1\), and \(C_{6,j}=0\) for other unselected \(j\)'s. Furthermore, \(S_{5}=\{4,7\}\) can be obtained because \(C_{6,4}=C_{6,7}=C_{5,4}=C_{5,7}=1\), and \(C_{6,j}=0\) or \(C_{5,j}=0\) for other unselected \(j\)'s. Sensor 4 can be arbitrarily selected as the third inserted sensor from \(S_{5}\). \(S_{4}=\{2,3\}\) can be obtained because \(C_{4,2}=C_{4,3}=1\), and \(C_{4,j}=0\) for other unselected \(j\)'s. \(S_{6}=\phi\) can be obtained because \(C_{4,j}=0\) or \(C_{6,j}=0\) for all the unselected \(j\)'s. Therefore, the fourth inserted sensor should be selected from \(S_{4}\). Sensor 2 can be arbitrarily selected as the fourth inserted sensor from \(S_{4}\). Then, \(S_{2}=\{1,3,12\}\), \(S_{4}=\{3\}\), and \(S_{6}=\phi\) can be obtained. Therefore, the fifth inserted sensor should be sensor 3. In this manner, the next inserted sensors can be sequentially selected until all the sensors are covered by the constructed sequence of sensors. For the wireless sensor network in Figure 1, a single serially connected multipolling sequence can be obtained as [sensors 5, 6, 4, 2, 3, 1, 12, 11, 10, 9, 8, 7] by the node insertion algorithm. Generally, without the preknowledge of the sets \(S_{i}\)'s, which were obtained for inserting the previous sensor in the multipolling sequence, or exploiting the old sets \(S_{i}\)'s for the previous sensor to obtain the new sets \(S_{i}\)'s for selecting the new sensor, to select a sensor that is inserted into the multipolling sequence in the process, the connectivities between the sensors in the multipolling sequence and the unselected sensors should be taken into account. Therefore, the computational complexity for selecting a sensor that is inserted into the multipolling sequence in the process is \(O(l^{2})\), and the overall computational complexity for selecting \(l\) sensors by the original node insertion algorithm amounts to \(O(l^{3})\). Now, the combined sweeping and jumping method is proposed to enhance the node insertion algorithm. During the course of inserting the sensors into the sequence in the process of construction, let \(N\) be the number of sensors in the current sequence, and sensor \(F(i)\) for \(i\leq N\) be the \(i\)th inserted sensor in the sequence. For the proposed sweeping method, \(D_{j}\) for unselected sensor \(j\) is defined as  
\[D_{j}=Max\Big{\{}i\big{|}C_{F(i),j}=0\Big{\}},\]  
which is the place of the most recently inserted sensor, from which the transmission signal cannot be successfully received and interpreted by unselected sensor \(j\). For the convenience of explanation, \(D_{j}=0\) when unselected sensor \(j\) can interpret the transmission signal from all the sensors in the current sequence, and \(D_{j}=-1\) for selected sensor \(j\). \(D\) denotes the vector \([D_{1},\,D_{2},\ldots,\,D_{l}]\). After a sensor is inserted into the sequence, \(D_{j}\) for unselected sensor \(j\) can be updated by the following:  
\[D_{j}=N\text{ for unselected sensor }j\text{ such that }C_{F(N),j}=0.\]  
Note that the smaller \(D_{j}\) is, the greater connectivity sensor \(j\) has with the recently inserted sensors, and during the course of inserting the sensors into the sequence, \(D_{j}\) does not decrease. According to the node insertion algorithm, sensor \(j\) that has the smallest value of \(D_{j}\) should be selected as the next inserted sensor in the sequence. For example, in Figure 1, assume that after the initial insertion of sensor 1, sensor 3 was inserted into the multipolling sequence. Sensor 2 has the connectivities with all the selected sensors, sensors 1 and 3; therefore, \(D_{2}=0\). Sensors 4 and 5 have the connectivity with the second selected sensor, which is sensor 3; however, they do not have the connectivity with the first selected sensor, which is sensor 1. Therefore, \(D_{4}=D_{5}=1\). Sensors 6 to 12 do not have the connectivity with the last selected sensor, which is sensor 3; therefore, \(D_{6}=D_{7}=\ldots=D_{12}=2\).