## 4 Proposed Protocol
### MST and Chain Construction Period
1: Set MSTs = \(\os\);
2:for\(i=1\) to \(N_{cell}\)do
3: Set count = 0;
4: Set ei = 1;
5: Set TREEi = TREEi \(\cup\) [CHNii];
6: Set CHNi as the root node;
7:for\(i=1\) to [The number of edges in cell(i)] do
8: E[i].chosen = FALSE;
9:endfor
10: Sort [list of edges in set E] as not ascending of distance values
11:while (ei \(<\) [the number of edges in E] \(-\) 1) do
12: Select edge ei in E, whose E[ei].chosen is FALSE;
13: Set \(u\) = get root of edge (E[ei].u);
14: Set \(v\) = get root of edge (E[ei].v);
15:if (\(u\) and \(v\) are on two different trees) then
```  
**Algorithm 3** MSTs and Chain Formation```
16: Union(E[ei].u,E[ei].v)
17: E[i].chosen = TRUE;
18: Set count = count + 1;
19:if (count = [number of nodes in cell(i)] \(-\) 1) then
20: break;
21:endif
22:endif
23: Set ei = ei + 1;
24:endwhile
25:for each edge \(i\) in [List of the edges in E] do
26:if (E[i].mark = TRUE) then
27: TREEi = TREEi \(\cup\) [E[i].u, E[i].v];
28:endif
29:endfor
30: Set MSTS = MSTS \(\cup\) TREEi;
31:endfor
32: Set CHAIN = [super-CH];
33: Set super-CH as root device;
34:forCHNi = 1 to [The number of CHNs] do
35: Find the path from CHNi to CHNj by calculating the transition probability value
36: as Equation (20);
37: Update the pheromone according to Equation (21)
38: Connect CHNi and CHNj into CHAIN
39: Discard the CHNi in [List of the CHN devices]
40:endfor
41: Create slots time as TDMA schedule for all nodes to communicate in cells;
42: Create CDMA codes for CHNs to forward data along CHAIN to the sink device;
43: Broadcast the TDMA schedule, CDMA code, MSTs, and CHAIN to the network;
44:return [MSTs and CHAIN];
```

**Algorithm 3**_Cont._

Figure 6 illustrates an example of clustering, CHN selection, and data transmission route establishment, which includes 100 sensing nodes and the sink device deployed in the region of 100 \(\times\) 100 m\({}^{2}\). Figure 6: The network topology with EEGT protocol in one round. ### Data Transmission Stage

After finishing the CHN selection and establishing the multi-hop routes above, sensor nodes monitor the environment and periodically transmit sensed data packets to the sink through trees and a chain with intra-cell and inter-cell communication, respectively. Firstly, the farthest nodes in each MST will start sending to their parent node toward their CHN. The parent nodes receive the data packets, aggregate them, compress them with their own sensed data in a single packet, and transmit them to the upper-level nodes in the MST. The CHNs send to the next nodes along the chain to super-CHN. Whenever the super-CH nodes receive all the data, they will forward the data packets to the sink device after it is aggregated in the same way. After an interval of time, the next round will be started again by rebuilding the grid with several cells (clusters), reselecting CHNs and super-CHN, and reconstructing the tree and chain in the network for a new round. ## 5 Simulation and Performance Evaluation

### Simulation Parameters

To analyze EEGT performance, we simulated EEGT, LEACH-C [21], PEGASIS [22], and PEGCP [25] by network simulator ns-2 (v.2.34) [41; 42] installed in the Ubuntu 12.04 virtual machine using the scenarios with the \(c_{1}=0.5\), \(c_{2}=500\) m, \(c_{3}=0.05\) m, and other parameters that are described in Table 1[21; 36; 43]. ### Simulation Scenario

In this experiment, we have simulated the LEACH-C [21], PEGASIS [22], PEGCP [25], and EEGT protocols in many different scenarios to advance the reliability of the protocols in practice. Specifically, we employed the _\"-/setdest -v 1 -n 100 -t 1 -x 100 -y 100 -M 1 ->sceni.txt\"_ command in ns2 to create randomly many different scenarios with the same simulation parameters.