4.1. The Finding Minimum Scheduling Time for Convergecast (FMSTC) Algorithm
In this section, we describe the proposed algorithm to find the minimum scheduling time in a general topology.
Table 1 described the algorithm based on the assumptions in the previous section.
Table 1.
FMSTC Algorithm
Steps  Procedures 

1  In a given network
G = (V, E), where V is the set of vertices (sensor nodes), E is the set of edges (links between nodes), and s is a sink node (s ∈ V, s ≠ v_{i}). All the nodes have unique ids.
Find nodes set N_{s} = { v_{1}, v_{2}, v_{3}…, v_{i}}, where ^{∀}v_{i} ∈ V and v_{i} is the transmission range of s.
If the node v_{i} which is in the transmission range of s is in the transmission range of the other node v_{j}, ( v_{i} & v_{j}∈ N_{s}, v_{i} ≠ v_{j}).
Calculate the weight W(⋅⋅) of each link from s to v_{i} and v_{j}, i.e. W(v_{i}s) and W(v_{j}s), where W(⋅) = ⌈ l ⌉ − 1 and l is the distance between s to v_{i} or v_{j}. Select the lowest id node for the nodes set N_{s}, if W(v_{i}s) is equal to W(v_{j}s). Exclude the node v_{j} from the nodes set N_{s} if W(v_{i}s) is less than W(v_{j}s), or vice versa. Repeat (i) through (iii) until it has a complete set of N_{s}.

2.  Construct the independent minimum spanning tree set, ST = {t_{1}, t_{2}, t_{3}…, t_{n}}, where each tree in ST is rooted from each node in N_{s}. – modified Khan et al. [29] algorithm
If there exist a node v_{k} which satisfies the following condition − v_{k} ∈ t_{i} & v_{k} ∈ t_{j} (t_{i} & t_{j} ∈ ST), then calculate the weight W(⋅) of each link from v_{k} to v^{ti}_{a} and v^{tj}_{b}, where v^{ti}_{a} ∈ t_{i} and v^{tj}_{b} ∈ t_{j}. Add v_{k} to t_{i} if W(v^{ti}_{a}v_{k}) is less than W(v^{tj}_{b}v_{k}), or vice versa. Repeat (a) & (b) until it has a complete set of ST.

3  For each tree in ST, reconstruct to a line topology based on the distance between nodes of the tree. 
4  Get the minimum scheduling time for the given network applying Choi et al. (2011) algorithm. 
In step 1, the algorithm constructs the node set (
Ns), which has nodes around the transmission range of the sink node (
s). The algorithm selects a node that is closer to the sink node.
Figure 2 explains this step. The nodes,
v_{1},
v_{2},
v_{3},
v_{4},
v_{5} and
v_{6}, are in the transmission range of the sink node,
s. First, the algorithm needs to find a node set,
Ns, from these nodes. If the algorithm finds that node
v_{1} and
v_{2} are in the range of the sink node,
s, it calculates the weight from
s to
v_{1} and
s to
v_{2}. Then, it selects the node,
v_{1}, which has the smaller weight than that of
v_{2}. The algorithm applies for the nodes,
v_{3},
v_{4},
v_{5} and
v_{6}, and selects the nodes,
v_{3} and
v_{5}, which have a smaller weight than those of
v_{4} and
v_{6}. The complete set of nodes,
Ns, is defined as follows:
Figure 2.
Node set (Ns) in the FMSTC algorithm (v_{1}, v_{3} and v_{6}, respectively, are chosen instead of v_{2}_{,} v_{4} and v_{5}, because they are closer to the sink node (s)).
Figure 2.
Node set (Ns) in the FMSTC algorithm (v_{1}, v_{3} and v_{6}, respectively, are chosen instead of v_{2}_{,} v_{4} and v_{5}, because they are closer to the sink node (s)).
Once it has the complete set of nodes,
Ns, it starts to construct the minimum spanning tree for each node in
Ns that will be the root of each spanning tree. There are algorithms for constructing minimum spanning trees [
9,
10,
17,
28]. However, those algorithms are not suitable for WSNs, because WSNs are energyconstraint sensor networks. Therefore, we modified Khan’s algorithm, which is adaptable in WSNs, to get the minimum spanning tree from each node in
Ns. Khan
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.
Table 2.
FMLSP Algorithm
Steps  Procedures 

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_{i}. 
 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_{j}}.

  b.
If there exist more than two neighboring nodes within the transmission range,
v_{j} and v_{k}, calculate the weights from v_{i} to v_{j} and v_{k}, i.e. W( v_{j} v_{i}) and W( v_{k} v_{i}) ( j ≠ k)
If W(v_{j}v_{i}) is less than W(v_{k}v_{i}), put the node v_{i} to the independent minimum spanning set t_{i}, t_{i} = {v_{i}, v_{j}}, or vice versa, t_{i} = {v_{i}, v_{k}}. If W(v_{j}v_{i}) is equal to W(v_{k}v_{i}), put the node with smaller id number to the independent minimum spanning set t_{i}.

  c.
If there exists a node v_{m} which is included in more than two independent minimum spanning trees, i.e. v_{m} ∈ t_{i} and v_{m} ∈ t_{j}, calculate the weights from v_{m} to v^{ti}_{a} and v^{tj}_{b}, where v^{ti}_{a} ∈ t_{i} and v^{tj}_{b} ∈ t_{j}.
If W(v^{ti}_{a}v_{m}) is less than W(v^{tj}_{b}v_{m}), put the node v_{m} to the independent minimum spanning set t_{i}, t_{i} = {v_{i}…, v_{m}}, or vice versa, t_{j} = {v_{j}…, v_{m}}. If W(v^{ti}_{a}v_{m}) is equal to W(v^{tj}_{b}v_{m}), put the node v_{m} in the independent minimum spanning tree with smaller id number.

  d.
Repeat (a) through (c) until it completes the construction of the independent minimum spanning tree for each node in Ns.

2  While there exists a branch in the given independent minimum spanning tree t_{i}, repeat Step 1(b) through 1(d) within the independent minimum spanning tree t_{i} to construct the subtree t_{ij}. 
The algorithm finds the minimum spanning tree set,
t_{i}, for each node in
Ns. 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. The algorithm also adds the node to the tree that has the smaller
id if the weights of two links are the same in the case of a node that is in range of both of the trees. The algorithm repeats, until it gets the complete independent set of tree
t_{i}. After it gets a complete set of tree
t_{i}, it starts to find subtree set
t_{ij} from
t_{i}. This process is for the next step of the FMSTC algorithm. The FMSTC algorithm builds the line topology after constructing a minimum spanning tree. This subtree set,
t_{ij}, allows us to complete an independent set of tree
t_{i} by repeating the process described above.
Figure 3 explains the subtree set environment.
Figure 3.
Building a subtree set.
Figure 3.
Building a subtree set.
In
Figure 3, the spanning tree,
t_{1}, has Nodes
v_{1},
v_{2},
v_{7},
v_{8},
v_{9} and
v_{10};
t_{1} = {
v_{1},
v_{2},
v_{7},
v_{8},
v_{9},
v_{10}}. A node,
v_{1}, is connected to sink node, and Nodes
v_{2} and
v_{7} are connected to
v_{1}. With a tree,
t_{1}, we can produce two subtrees
t_{11} = {
v_{7},
v_{8}} and
t_{12} = {
v_{2},
v_{9},
v_{10}}, i.e.,
t_{11} ⊂
t_{1} and
t_{12} ⊂
t_{1}.We eventually construct the line topology in the given minimum spanning tree set with this process.
Figure 4 explains the algorithm to produce minimum spanning tree set
t_{i}. There are three minimum spanning trees:
t_{1},
t_{2} and
t_{3}.
Figure 4.
Constructing the minimum spanning trees for nodes in the node set (Ns) using the FMLSP algorithm.
Figure 4.
Constructing the minimum spanning trees for nodes in the node set (Ns) using the FMLSP algorithm.
Three nodes (
v_{1},
v_{3},
v_{5}) are selected from a sink node. The FMSTC algorithm starts to construct a minimum spanning tree rooted from each node (
v_{1},
v_{3},
v_{5}). It produces three spanning trees, which are
t_{1},
t_{2} and
t_{3}. The tree,
t_{1}, has two leaf nodes, which need to be divided into two subspanning trees. The algorithm produces the subtrees,
t_{11} and
t_{12}, from
t_{1}. Therefore, there are five spanning trees produced in the graph:
the node,
v_{10}, is in the spanning tree,
t_{12}, because it is close to Node
v_{9}, even though it is also in the transmission range of
v_{11}, which is in
t_{2}.
4.2. Applying Linear Structure to Get the Minimum Scheduling Time for Convergecast
The algorithm produces the line structure of each spanning tree. We applied the algorithm of Choi
et al. [
3] to get the minimum scheduling time. The authors have proposed an optimal convergecast scheduling algorithm based on the line topology with a fixed transmission range. The developed algorithm consists of four different algorithms. When the number of sensors is in a range less than the transmission range, the SIMPLE algorithm is used to send a message to the sink node directly. If the number of sensors is placed in the
p ≤
n ≤
p(
p + 1) range, where
n is the number of sensors and
p is the transmission power, then apply the TABLE and ADJUST algorithms. If the number of sensors is placed in the
p (
p + 1) <
n range, then apply the REDUCE algorithm first to use TABLE and ADJUST. The algorithms, SIMPLE, TABLE, ADJUST and REDUCE, are described in more detail as follows:
(1) If n < p, then apply the SIMPLE algorithm, which can allocate n time slots for the messages (m_{i}, 1 ≤ i ≤ n) to send a message from node i to the sink node at time slot i, because each node directly sends the message to the sink node in the given condition.
(2) If p ≤ n ≤ p(p + 1), then apply the TABLE and ADJUST algorithms. The TABLE algorithm allows us to allocate 2p(p + 1) − p time slots to deliver any p(p + 1) messages; on the other hand, the ADJUST algorithm reallocates it for p(p + 1) nodes and then allocates the time slots for n nodes.
(3) If p(p + 1) < n, then apply the REDUCE algorithm with (n − p) nodes and then apply the TABLE and ADJUST algorithms.
Table 3 explains the minimum time schedule for using these algorithms.
Table 3.
Time schedule with TABLE when n = 10, p = 3.
Table 3.
Time schedule with TABLE when n = 10, p = 3.
Time  Node 
0  1  2  3  4  5  6  7  8  9  10 
1  0  4  0  0  0  0  0  0  11  0  0 
2  0  0  5  0  0  0  0  0  0  12  0 
3  0  0  0  6  0  0  0  0  0  0  13 
4  1  0  0  0  0  8  0  0  0  0  0 
5  2  0  0  0  0  0  9  0  0  0  0 
6  3  0  0  0  0  0  0  10  0  0  0 
7  4  0  0  0  0  11  0  0  0  0  0 
8  5  0  0  0  0  0  12  0  0  0  0 
9  6  0  0  0  0  0  0  13  0  0  0 
10  0  0  8  0  0  0  0  0  0  15  0 
11  0  0  0  9  0  0  0  0  0  0  16 
12  0  0  11  0  0  0  0  0  0  18  0 
13  0  0  0  12  0  0  0  0  0  0  19 
14  8  0  0  0  0  0  15  0  0  0  0 
15  9  0  0  0  0  0  0  16  0  0  0 
16  11  0  0  0  0  0  18  0  0  0  0 
17  12  0  0  0  0  0  0  19  0  0  0 
18  0  0  0  15  0  0  0  0  0  0  0 
19  0  0  0  18  0  0  0  0  0  0  0 
20  15  0  0  0  0  0  0  0  0  0  0 
21  18  0  0  0  0  0  0  0  0  0  0 
22  0  0  0  0  0  0  0  0  0  0  0 
23  0  0  0  0  0  0  0  0  0  0  0 
24  0  0  0  0  0  0  0  0  0  0  0 
The above table is the output of the TABLE algorithm and function TABLE, with 11 nodes, including the sink node and three transmission ranges. We want to deliver the individual contents to the sink node, where the content number is the message originating from the cell number. The algorithms assumed that they can use virtual nodes, which are not physically used. The virtual node numbers used in this algorithm are {11, 12, 13, 15, 16, 18, 19}. In the table, the content “0” means there is no message delivered at the assigned time slot. For example, for the node number “1” and time slot “1”, there is content from the node “4”. For the node number “8” and time slot “1”, there is content from the node “11”, which is the virtual node.
When we send Contents 4, 5 and 6 to Nodes 1, 2 and 3, we move the nonconflicting messages in the same time slot as follows:
When sending 4 to 1, then move 11 to 8, and 18 to 15, and so on, up to n + p^{2} (here, 10 + 9 = 19);
when sending 5 to 2, then move 12 to 9 and 19 to 16, when sending 6 to 3; then move 13 to 10.
When we send Contents 1, 2 and 3 to the sink node, we also move the nonconflicting messages in the same time slot as follows:
When sending 1 to the sink node (0), then move 8 to 5 and 15 to 12;
when sending 2 to the sink node (0), then move 9 to 6 and 16 to 13;
when sending 3 to the sink node (0), then move 10 to 7.
When we send Contents 4, 5 and 6 to the sink node, we move nonconflicting messages as follows:
When sending 4 to 1, then move 11 to 5 and 18 to 12;
when sending 5 to 1, then move 12 to 6 and 19 to 13;
when sending 6 to 1, then move 13 to 7.
When we send Contents 8 and 9 to Nodes 2 and 3, we can move 15 to 9 and 16 to 10.
When we send Contents 11 and 12 to Nodes 2 and 3, we can move 18 to 9 and 19 to 10.
When we send Contents 8 and 9 to the sink node, we can move 15 to 6 and 16 to 7.
After we send Content 15 to 3 in time slot 18 and 18 to 3 in time slot 19, Contents 15 and 18 arrive at the sink node in Time Slots 20 and 21.
Table 4 is made, and it has
p(
p + 1) messages in the sink node, because n is always less than or equal to
p(
p + 1).
Table 4.
Time schedule with ADJUST − (1) when n = 10, p = 3.
Table 4.
Time schedule with ADJUST − (1) when n = 10, p = 3.
Time  Node 
0  1  2  3  4  5  6  7  8  9  10 
1  0  4  0  0  0  0  0  0  11  0  0 
2  0  0  5  0  0  0  0  0  0  12  0 
3  0  0  0  6  0  0  0  0  0  0  13 
4  1  0  0  0  0  8  0  0  0  0  0 
5  2  0  0  0  0  0  9  0  0  0  0 
6  3  0  0  0  0  0  0  10  0  0  0 
7  4  0  0  0  0  11  0  0  0  0  0 
8  5  0  0  0  0  0  12  0  0  0  0 
9  6  0  0  0  0  0  0  13  0  0  0 
10  0  0  8  0  0  0  0  0  0  15  0 
11  0  0  0  9  0  0  0  0  0  0  16 
12  0  0  11  0  0  0  0  0  0  18  0 
13  0  0  0  12  0  0  0  0  0  0  19 
14  8  0  0  0  0  0  15  0  0  0  0 
15  9  0  0  0  0  0  0  16  0  0  0 
16  11  0  0  0  0  0  18  0  0  0  0 
17  12  0  0  0  0  0  0  19  0  0  0 
18  0  0  0  15  0  0  0  0  0  0  0 
19  0  0  0  18  0  0  0  0  0  0  0 
20  15  0  0  0  0  0  0  0  0  0  0 
21  18  0  0  0  0  0  0  0  0  0  0 
22  0  0  0  0  0  0  0  0  0  0  0 
23  0  0  0  0  0  0  0  0  0  0  0 
24  0  0  0  0  0  0  0  0  0  0  0 
In the sink node, we have messages, i.e., 1, 2, 3, 4, 5, 6, 8, 9, 11, 12, 15 and 18. That means we missed Messages 7 and 10. For 7, we find the smallest number, but greater than n (=10), among those received, which is 11.
After searching 11 among Column 7, 6 and 5, we can find it at Table (7, 5) and replace the content with 7. The next 11 is located in column 2 (5 − 3 = 2) which is the Table (12, 2), and we replace the content with 7. The next, 11, is located in 0 (2 − 3 = −1, but the negative number is always 0 here), which is the Table (0, 16); replace Table (0, 16) with 7. We can execute the same algorithm for the content of 10. Then, we can get
Table 5.
Table 5.
Time schedule with ADJUST − (2) when n = 10, p = 3.
Table 5.
Time schedule with ADJUST − (2) when n = 10, p = 3.
Time  Node 
0  1  2  3  4  5  6  7  8  9  10 
1  0  4  0  0  0  0  0  0  11  0  0 
2  0  0  5  0  0  0  0  0  0  10  0 
3  0  0  0  6  0  0  0  0  0  0  13 
4  1  0  0  0  0  8  0  0  0  0  0 
5  2  0  0  0  0  0  9  0  0  0  0 
6  3  0  0  0  0  0  0  10  0  0  0 
7  4  0  0  0  0  7  0  0  0  0  0 
8  5  0  0  0  0  0  10  0  0  0  0 
9  6  0  0  0  0  0  0  13  0  0  0 
10  0  0  8  0  0  0  0  0  0  15  0 
11  0  0  0  9  0  0  0  0  0  0  16 
12  0  0  7  0  0  0  0  0  0  18  0 
13  0  0  0  10  0  0  0  0  0  0  19 
14  8  0  0  0  0  0  15  0  0  0  0 
15  9  0  0  0  0  0  0  16  0  0  0 
16  7  0  0  0  0  0  18  0  0  0  0 
17  10  0  0  0  0  0  0  19  0  0  0 
18  0  0  0  15  0  0  0  0  0  0  0 
19  0  0  0  18  0  0  0  0  0  0  0 
20  15  0  0  0  0  0  0  0  0  0  0 
21  18  0  0  0  0  0  0  0  0  0  0 
22  0  0  0  0  0  0  0  0  0  0  0 
23  0  0  0  0  0  0  0  0  0  0  0 
24  0  0  0  0  0  0  0  0  0  0  0 
The next step of the algorithm deletes all numbers greater than
n and deletes all rows that do not contain any number from one to
n.
Table 6 shows the minimum time schedule when the number of nodes
n = 10 and the transmission range
p = 3.
Table 6.
Completed time schedule when n = 10, p = 3.
Table 6.
Completed time schedule when n = 10, p = 3.
Time  Node 
0  1  2  3  4  5  6  7  8  9  10 
1  0  4  0  0  0  0  0  0  11  0  0 
2  0  0  5  0  0  0  0  0  0  10  0 
3  0  0  0  6  0  0  0  0  0  0  0 
4  1  0  0  0  0  8  0  0  0  0  0 
5  2  0  0  0  0  0  9  0  0  0  0 
6  3  0  0  0  0  0  0  10  0  0  0 
7  4  0  0  0  0  7  0  0  0  0  0 
8  5  0  0  0  0  0  10  0  0  0  0 
9  6  0  0  0  0  0  0  0  0  0  0 
10  0  0  8  0  0  0  0  0  0  0  0 
11  0  0  0  9  0  0  0  0  0  0  0 
12  0  0  7  0  0  0  0  0  0  0  0 
13  0  0  0  10  0  0  0  0  0  0  0 
14  8  0  0  0  0  0  0  0  0  0  0 
15  9  0  0  0  0  0  0  0  0  0  0 
16  7  0  0  0  0  0  0  0  0  0  0 
17  10  0  0  0  0  0  0  0  0  0  0 
The example we used is when the number of nodes is less than
p (
p + 1),
n <
p(
p + 1). If the number of nodes is greater than
p(
p + 1),
n >
p(
p + 1), the REDUCE algorithm is applied to make the condition,
n <
p(
p + 1); then, use the TABLE and ADJUST algorithm to get the minimum time schedule. For example, If
n = 14 and
p = 3, we have nodes,
n = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14}; then, make it
n = {4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14} using
Table 7, as follows.
Table 7.
Time schedule with REDUCE when n = 14, p = 3.
Table 7.
Time schedule with REDUCE when n = 14, p = 3.
Time  Node 
0  1  2  3  4  5  6  7  8  9  10  11  12  13  14 
1  1          8                   
2  2            9                 
3  3              10               
4    4              11             
5      5              12           
6        6              13         
7          7              14       
After 2p + 1 = 7 steps, we have n = {4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14}. This is the same as the problem with n = 10 and p = 3 from this point. Then, we use the TABLE and ADJUST algorithms to get the minimum time schedule.