## 4 Proposed Scheduling Algorithm
### The Finding Minimum Scheduling Time for Convergecast (FMSTC) Algorithm
There are algorithms for constructing minimum spanning trees [9,10,17,28]. However, those algorithms are not suitable for WSNs, because WSNs are energy-constraint sensor networks. Therefore, we modified [PERSON]'s algorithm, which is adaptable in WSNs, to get the minimum spanning tree from each node in _Ns_. [PERSON] _et al._[29] constructed a minimum spanning tree based on a rank function, which is decided by the random number and the unique _id_ for each node. In this study, we use the weight of each distance instead of a random number, i.e., transmission range and node _ids_. The proposed algorithm constructs a minimum cost spanning tree; referred to as FMLSP (find minimum low cost spanning tree). Once the algorithm constructs all the minimum cost spanning trees, we assume that each of the trees is an independent set, i.e., each tree; there is no conflict to send a message because of the transmission range. The algorithm (referred to as FMLSP) is described in Table 2. \begin{table}
\begin{tabular}{l l} \hline \hline
**Steps** & **Procedures** \\ \hline
**1** & All the nodes in the given network \(G=(V,E)\) have unique _ids_. \\  & Select a node \(v_{i}\) which has minimum number _id_ from the given _Ns_ set. Then put the node in the independent minimum spanning set \(t_{i}\), \(t_{i}=\{v_{i}\}\). \\  & Find all the neighboring nodes from \(v_{t_{i}}\). \\  & 1. If there exists only one neighboring node \(v_{j}\), which is within the \\  & transmission range, put the node in the independent minimum spanning \\  & tree \(t_{i}\), \(t_{i}=\{v_{i}\), \(v_{i}\}\). \\  & 2. If there exist more than two neighboring nodes within the transmission \\  & \(v_{i}\) and \(v_{k}\), calculate the weights from \(v_{i}\) to \(v_{i}\) and \(v_{k}\), _i.e._\(W(v_{i}|v_{i})\) and \(W(v_{k}|v_{i})\) (\(j\
eq k\)) \\  & 1. If \(W(v_{i}|v_{i})\) is less than \(W(v_{k}|v_{i})\), put the node \(v_{i}\) to the \\  & 2. independent minimum spanning set \(t_{i}\), \(t_{i}=\{v_{i}\), \(v_{i}\}\), or vice \\  & 2. If \(W(v_{i}|v_{i})\) is equal to \(W(v_{k}|v_{i})\), put the node with smaller _id_ \\  & 2. number to the independent minimum spanning set \(t_{i}\). \\  & 3. If there exists a node \(v_{m}\) which is included in more than two independent \\  & minimum spanning trees, _i.e._\(v_{m}\in t_{i}\) and \(v_{m}\in t_{j}\), calculate the weights from \(v_{m}\) to \(v^{ii}\) and \(v^{bj}\), where \(v^{i}_{a}\in t_{i}\) and \(v^{bj}\in t_{j}\). \\  & 1. If \(W(v^{ii}_{a}|v_{m})\) is less than \(W(v^{ij}_{b}|v_{m})\), put the node \(v_{m}\) to the \\  & 2. independent minimum spanning set \(t_{i}\), \(t_{i}=\{v_{i}\)..., \(v_{m}\}\), or \\  & 3. vice versa, \(t_{j}=\{v_{j}\)..., \(v_{m}\}\). \\  & 4. If \(W(v^{ii}_{a}|v_{m})\) is equal to \(W(v^{ij}_{b}|v_{m})\), put the node \(v_{m}\) in the \\  & 2. independent minimum spanning tree with smaller _id_ \\  & 3. number. \\  & 4. Repeat (a) through (c) until it completes the construction of the \\  & 4. independent minimum spanning tree for each node in _Ns_. \\  & 5. While there exists a branch in the given independent minimum spanning tree \(t_{i}\), \\  & 6. repeat Step 1(b) through 1(d) within the independent minimum spanning tree \(t_{i}\) to \\  & 7. repeat Step 2(b) through 1(d) within the independent minimum spanning tree to \\  & 8. construct the sub-tree \(t_{i}\). \\ \hline \hline \end{tabular}
\end{table} 
Table 2: FMLSP AlgorithmThe algorithm finds the minimum spanning tree set, \(t_{i}\), for each node in \(N\)s. First, it finds all neighbor nodes in its transmission range. If two nodes are in the same transmission range, it calculates the weight for each link from a root node to a neighboring node. The algorithm selects the smaller weight to add to the node to the tree. If the weight of the link is the same for both of the nodes, the algorithm selects the node with the smaller id to add it to the tree. If the algorithm finds that a node is in the ranges of both of the trees, it measures a weight for each link and adds the node to the tree that has the smaller weight link.