# Data Aggregation Based on Overlapping Rate of Sensing Area in Wireless Sensor Networks
## 4 Implementation of AggOR Scheme
### Gathering Area Construction  
After transmission hierarchy diagram is completed, sensor nodes start to form the gathering area in a distributed manner. Gathering area construction begins from the lower-level free nodes to the upper-level layer by layer and follows the three aggregation rules in Section 3.2. In the construction process, a free node may be chosen as a gathering node in a new gathering area, or join in an existing gathering area as a member node, or become an independent node. Take \(v_{i}\) as an instance; its gathering area construction algorithm is shown in Algorithm 1, a core of which is finding the candidate gathering node set as shown in Algorithm 2.  
```
Input: the transmission hierarchy diagram, a free node \(v_{i}\) Output:\(GA_{i}\) ifa set of nodes \(M\) request to be member nodes of \(GA_{i}\)then  send replies to \(M\) to construct a gathering area \(GA_{i}=(v_{i},M)\); else if\(L_{i}>1\)then \(CG_{i}\leftarrow\) Algorithm 2; if\(CG_{i}=\emptyset\)then \(v_{i}\) is an independent node, \(GA_{i}=(v_{i},\emptyset)\); else  select \(v_{i}\in CG_{i}\) with the maximum residual energy to be the gathering node of \(v_{i}\);  send the request to be a member of \(GA_{i}\);  end if else \(v_{i}\) is an independent node, \(GA_{i}=(v_{i},\emptyset)\);  end if  end for return\(GA_{i}\);
```  
**Algorithm 1**Gathering Area Construction.  
The network is initialized that all the sensor nodes are free nodes and there are \((n+1)\) levels in the transmission hierarchy diagram. Levels are numbered as 0, 1, 2,..., \(n\). Then the nodes at level \(n\) start constructing gathering areas firstly. For a node \(v_{i}\) whose level is larger than 1, it calculates the overlapping rates of sensing area and obtains its candidate gathering node set \(CG_{i}\) through Algorithm 2. If \(CG_{i}\) is empty, \(v_{i}\) becomes an independent node; otherwise, \(v_{i}\) chooses the node \(v_{t}\) in \(CG_{i}\) which has the most residual energy as its gathering node, and sends the request to be a member node in the gathering area \(GA_{t}\). For the free nodes at level 1, it is unnecessary to select the sink as gathering node, and their overlapping rates of sensing area with their neighbor nodes cannot be larger than 2 (Rule 2). Therefore each free node at level 1 turns into an independent node.  
Figure 5: An instance topology under construction.  
```
Input:\(CP_{i}\), \(N_{i}\) Output:\(CG_{i}\) initialize:\(CG_{i}\leftarrow\emptyset\); for\(\forall\;v_{j}\in CP_{i}\)do if\(\exists\;OR_{i,j}\geq OR_{T}\)then \(CG_{i}\gets CG_{i}\cup\{v_{j}\}\);  end if  end for if\(CG_{i}=\emptyset\)then for\(\forall\;v_{k}\in N_{i}\)do if\(OR_{i,k}\geq OR_{T}\) and \((2L_{i}-1)OR_{i,k}>2\)then \(CG_{i}\gets CG_{i}\cup\{v_{k}\}\);  end if  end for return\(CG_{i}\);
```  
**Algorithm 2**Finding Candidate Gathering Node Set.  
Algorithm 2 returns \(CG_{i}\), as the set of candidate gathering nodes of \(v_{i}\). For every candidate parent node \(v_{j}\), if \(OR_{i,j}\geq OR_{T}\), \(v_{j}\) is included in \(CG_{i}\). If there is no candidate gathering node selected from the candidate parent nodes, \(v_{i}\) calculates the overlapping rates of sensing area with its neighbor nodes. If a neighbor node \(v_{k}\) satisfies \(OR_{i,k}\geq OR_{T}\) and \((2L_{i}-1)OR_{i,k}>2\), \(v_{k}\) is included in \(CG_{i}\).