## 3 The Proposed Routing Protocol--CRD
### Underlying Technology--Necessary Algorithms
#### 3.3.3. The Proposed Connected Dominating Set Based Clustering Algorithm--CDS Based Clustering  
Since the CDS helps mobile nodes stay connected in MANETs, CHs should be selected from this set. The main goal of the proposed CDS based clustering algorithm is to classify nodes into clusters and to be used as underlying infrastructure. These clusters satisfy the following properties--stability, keeping connection between nodes, saving control overheads, reducing delay, saving energy and increasing packet delivery ratio. In this algorithm, mobile nodes use the common channel to exchange information with their neighbors.  
**Best CH candidate.** Let \(v\) be a **non-intermediate node** and \(u_{1},\ldots,u_{n}\) be intermediate neighbors of node \(v\). Node \(u_{b}\) is the best CH candidate of node \(v\) if it satisfies one of the following conditions  
* \(W(u_{b})>W(u_{j})\) for all \(j\
eq b\).
* \(W(u_{b})=W(u_{j1})=\cdots=W(u_{jk})=\max_{l=1,\ldots,n}\{W(u_{l})\}\) and \(id(u_{b})>id(u_{j})\) for all \(j=j1,\ldots,jk\).  
Let \(v\) be a **intermediate node** and \(u_{1},\ldots,u_{n}\) be intermediate neighbors of node \(v\). Node \(u_{b}\) is the best CH candidate of node \(v\) if it satisfies one of the following conditions  
* \(W(u_{b})>W(v)\) and \(W(u_{b})>W(u_{j})\) for all \(j\
eq b\),
* \(W(u_{b})=W(u_{j1})=\cdots=W(u_{jk})=\max_{l=1,\ldots,n}\{W(u_{l})\}\geq W(v)\), \(id(u_{b})>id(v)\) and \(id(u_{b})>id(u_{j})\) for all \(j=j1,\ldots,jk\).  
**Best CH.** Let \(v\) be a node and \(u_{1},\ldots,u_{n}\) be CH neighbors of node \(v\). Node \(u_{b}\) is the best CH of node \(v\) if it satisfies one of the following conditions  
* \(W(u_{b})>W(u_{j})\) for all \(j\
eq i\).
* \(W(u_{b})=W(u_{j1})=\cdots=W(u_{jk})=\max_{l=1,\ldots,n}\{W(u_{l})\}\) and \(id(u_{b})>id(u_{j})\) for all \(j=j1,\ldots,jk\).  
We outline the proposed CDS based clustering algorithm in Algorithm 3 which can be explained as follows:  
* Step 1. We use the Algorithm 1 (CDS selection algorithm) to build a CDS and the Algorithm 2 (CDS size reduction algorithm) is used to remove some intermediate nodes from the CDS.
* Step 2. If a non-intermediate node \(v\) does not have any CH in its list of neighbors, node \(v\) elects a best CH candidate \(u\) to become a CH and sends join cluster packet to CH \(u\).  
Figure 5: The basic concept of the proposed CDS based clustering algorithm.  
* Step 3. If a non-intermediate node \(v\) has at least one CH in its neighbors list, node \(v\) uses common channel and sends a join cluster packet to the best CH \(u\).
* Step 4. If a node \(v\) receives a join cluster packet from node \(u\), it becomes a CH and uses common channel and sends a reply acceptance message to node \(u\). Then, this CH records the sender node in its cluster table.
* Step 5. Each intermediate node \(v\) elects/chooses a CH in the same way as non-intermediate nodes.  
In Figure 5, cluster members 1, 2, 3, 6 and 7 elect node 4 as a CH to join in the cluster of CH(4). Because node \(W(5)=0.75>W(4)=0.6\), cluster members 8 and 9 choose node 5 as a CH to join the cluster of CH(5). Cluster members 12, 13 and 15 choose node 14 as a CH to join in the cluster of CH(14). Next, GW(10) choose CH(5) to join in the cluster of CH(5) and GW(11) choose CH(14) to join in the cluster of CH(14). The CDS includes CHs (4, 5 and 14) and GWs (10 and 11).  
After finishing the proposed CDS clustering algorithm, the CDS includes intermediate nodes and CHs. We will call these intermediate nodes gateways.  
**Algorithm 3** The flowchart of proposed connected dominating set based clustering algorithm--CDS based clustering.  
**Algorithm 4** The flowchart of connected dominating set based clustering algorithm--CDS based clustering.