# Combined Sweeping and Jumping Method to Enhance Node Insertion Algorithm for Wi-Fi Sensor Networks
## 2 Combined Sweeping and Jumping Method  
Assume a wireless sensor network where an AP and \(l\) sensors of sensor 1, sensor 2, \(\ldots\), sensor \(l\) exist. When sensor \(i\) transmits a data frame to the AP, the transmission signal from sensor \(i\) can be picked up and understood by sensor \(j\) (\(\
eq i\)). This status of the wireless channel between sensors \(i\) and \(j\) is represented by \(C_{i,j}=1\). \(C_{i,j}=0\) represents the status of the wireless channel that sensor \(j\) cannot interpret the transmission signal from sensor \(i\). The connectivity information of \(C_{i,j}\) can be efficiently collected by the connectivity-based multipolling MAC protocol described in [13,14]. For convenience of explanation of the proposed combined sweeping and jumping method, Figure 1 depicts a wireless sensor network where \(l=12\) sensors that are located at the boundary of the circular service area with a radius of \(r\), and an AP is located at the center of the service area. Figure 1: Wireless sensor network as example. If the transmission signal from each sensor in Figure 1 is propagated in the circular form with the transmission range of \(r\), the connectivity information among 12 sensors is represented by the following matrix:  
\[\left[c_{i,j}\right]=\left[ \begin{array}{ccccccccccccc}0&1&1&0&0&0&0&0&0&0&1&1\\ 1&0&1&1&0&0&0&0&0&0&0&1\\ 1&1&0&1&1&0&0&0&0&0&0&1\\ 0&1&1&0&1&1&0&0&0&0&0&0\\ 0&0&1&1&0&1&1&0&0&0&0\\ 0&0&0&1&1&0&1&1&0&0&0\\ 0&0&0&0&0&1&1&0&1&1&0\\ 0&0&0&0&0&0&1&1&0&1&1\\ 1&0&0&0&0&0&0&1&1&0&1\\ 1&1&0&0&0&0&0&0&1&1&0\end{array} \right]\]  
In Figure 1, the angle between the lines from the AP to two sensors that have a common neighboring sensor is \(60^{\circ}\), and the distance between two sensors that have a common neighbor is \(r\). Therefore, two neighboring sensors and two sensors that have a common neighbor are connected with each other because two sensors are located within the transmission range of each other. The backtracking algorithm in [13; 14] and the node insertion algorithm in [4] try to sequence the sensors in the manner in which the cases where sensor \(j\) cannot interpret the transmission signal from the previous sensor \(i\) in the sequence, that is, \(C_{i,j}=0\), occur as little as possible. By the minimization of the cases where a sensor cannot interpret the transmission signal from the previous sensor in the sequence, the connectivity-based multipolling MAC protocol can minimize the transmissions of multipolling frames, which are the transmission overhead for uplink data transmissions from sensors in wireless sensor networks. In the node insertion algorithm in [4], after selecting an arbitrary sensor as the first inserted sensor, the next sensor inserted into the sequence in the process is selected by searching for the set of sensor \(j\)'s that have not been selected for each sensor \(i\) in the sequence, such as \(C_{k,j}=1\) for all the recently inserted sensor \(k\)'s up to sensor \(i\). The set of these sensor \(j\)'s for sensor \(i\) will be denoted by \(S_{i}\). The search for the set of sensor \(j\)'s is sequentially conducted for each sensor \(i\) from the most recently inserted sensor \(i\) to the firstly inserted sensor \(i\) until the obtained set of sensor \(j\)'s is empty or \(S_{i}\)'s have been obtained for all the sensor \(i\)'s in the sequence. A sensor in the lastly obtained non-empty set of sensor \(j\)'s is selected as the next sensor inserted into the sequence of sensors. The selected sensor is a sensor that is connected from as many most recently inserted sensors in the sequence in the process as possible. Let us apply the node insertion algorithm to the wireless sensor network in Figure 1. Let sensor 5 be the first inserted sensor in the sequence of sensors. Then, \(S_{5}=\{3,4,6,7\}\) is obtained because \(C_{5,3}=C_{5,4}=C_{5,6}=C_{5,7}=1\), and \(C_{5,j}=0\) for other \(j\)'s. Sensor 6 can be arbitrarily selected as the next inserted sensor from \(S_{5}\).