# CoDA: Collaborative Data Aggregation in Emerging Sensor Networks Using Bio-Level Voronoi Diagrams
## 3 System Model
### Deployment of Relay Nodes  
The research shows that the use of the multi-hop communication manner between sensor nodes can improve the energy efficiency and prolong the network lifetime, but it also brings some problems, for example, more delay for packet forwarding, and the formation of energy holes owing to the excessive overhead for the nodes close to the sink.  
Therefore, the data aggregation mechanism proposed in this paper divides the nodes of the whole network into three levels, consisting of the cluster head, the member node and the relay nodes. The backbone network topology is formed by arranging a small amount of powerful relay nodes in the network, which can achieve inter cluster communication efficiently and reduce the delay of the data transmitted from the monitoring sensor to the sink effectively. Relay nodes usually are equipped with strong energy supply, communication capacity and computing power. In contrast with cluster heads, they possess much wider coverage and are responsible for data aggregation from adjacent clusters. Obviously, the bio-level structure of the node is adaptive for nodes' management. Meanwhile, it has a good scalability.  
For the lower level network, each cluster head can communicate with corresponding relay node by using multi hop mode. In the upper level topology, relay nodes consist of the backbone network. In order to reduce the communication cost, the number of relay nodes should be as less as possible under the premise of connectivity.  
**Definition 4**.: _If \(s_{j}\) satisfies the condition: \(N_{c}(i)=\left\{s_{i}|d(s_{i},s_{j})\leq R_{c},j\
eq i\right\}\), then \(s_{j}\) is the neighbor node of \(s_{i}\), where \(R_{c}\) denotes the transmission radius and \(s_{j}\) is the neighbor node of \(s_{i}\)._  
**Definition 5**.: _If any point in a region is within the scope of coverage from any node in the set \(S\), and satisfy that the points in \(S\) are connected, then, \(S\) can be defined as a connected coverage set._  
**Definition 6**.: _If the minimal nodes can constitute a connected coverage set, then the set \(S=\{s_{1},s_{2},\cdots,s_{n}\}\) can be defined as a minimum connected coverage set._  
To determine the minimum communication radius of inters cluster communication, the proposed Algorithm 2 is designed as following:  
```
Input: the sensor node set \(S=\{s_{1},s_{2},\cdots,s_{N}\}\), the number of cluster head \(k\). Output: the set of relay nodes \(RS\).
1. Suppose all nodes in the set \(S\) as generic point, generates the corresponding k order Voronoi diagram \(V_{k}(S)\);
2. The set of polygon for Voronoi diagram is denoted as \(V=\{V_{k}(PL_{1},S),\ V_{k}(PL_{2},S),\\ \cdots,V_{k}(PL_{M},S)\}\), where \(V_{k}(PL_{1},S)\) is the i-th polygon for \(V_{k}(S)\);
3. \(RS=\varnothing\);
4. while \(V\
eq\varnothing\) do
5. for each \(V_{k}(PL_{i},S)\in V\) do
6. if \(s_{j}\) is the generic point of polygon \(V_{k}(PL_{i},S)\) then
7. record the occurrence time of node \(s_{j}\);
8. end if;
9. end for;
10. Find out the \(s_{\max}\) which denotes the maximum number of occurrences of generic point;
11. The node \(s_{\max}\) can be added in the set of \(RS\);
12. \(V=V-\{V_{k}(PL_{i},S)|s_{\max}\in PL_{i}\}\);
13. end while.
```  
**Algorithm 2**Determination of the minimum communication radius of inters cluster communication.