# A Cluster-Based Dual-Adaptive Topology Control Approach in Wireless Sensor Networks
## 3 The Improved Clustering Scheme
### Cluster Formation
#### 3.2.1 Neighborhood Discovery
Set the timer \(t_{\Delta}\) as \(\Delta\)
6. Initialize \(FLAG_{1}\) and \(FLAG_{2}\) as _false_ respectively
7.while the timer \(t_{\Delta}\) does not expire do
8.if receive [\(ID_{v}\), \(e_{v}\), \(p_{v,max}\), \(d_{v,max}\), \(L_{v,nei}\)] from any node \(v\) that is not in \(L_{u,nei}\)then
9. Record the receiving power \(p^{r}v_{u}\) and employ the Formula (4) to compute \(d_{v,u}\)
10. Add [\(ID_{v}\), \(d_{v,u}\)] to \(L_{u,nei}\)
11.if\(d_{u,max}<d_{v,u}\)then\(d_{u,max}=d_{v,u}\)
12.\(FLAG_{1}=true\)
13.elseif receive [\(ID_{v}\), \(e_{v}\), \(p_{v,max}\), \(d_{v,max}\), \(L_{v,nei}\)] and node \(u\) is not in \(L_{v,nei}\)then
14.\(FLAG_{2}=true\)
15.endif
16.endwhile
17.if(\(FLAG_{2}==true\))then\(N\)++
18.if(\(N<N_{max}\)) and (\(FLAG_{1}==true\) or \(FLAG_{2}==true\))then go to step 2
19.else go to step 2
20.endif
```  
**Algorithm 1**Neighborhood Discovery (\(ND\))  
Take node \(u\) for an example in Algorithm 1, first, its list of neighbors (i.e., \(L_{u,nei}\)) is initialized as _empty_ (see line 1) to prepare for storing the discovered new neighbors. Since \(u\) does not know any neighbor at the beginning of neighborhood discovery process, its approximate maximum transmission range (i.e., \(d_{u,max}\)) is initialized as _zero_ (see line 1). Then \(u\) uses a CSMA/CA scheme to contend for the channel (see line 2). Once \(u\) succeeds in accessing the channel (see line 3), it sends the hello message (i.e., [\(ID_{u}\), \(e_{u}\), \(p_{u,max}\), \(d_{u,max}\), \(L_{u,nei}\)]) at the maximum transmission power \(p_{u,max}\) to discover its 1-hop neighbors (see line 4). After sending the hello message, \(u\) waits for a fixed duration of time \(\Delta\) to update its list of neighbors (see lines 5-16). During the time \(\Delta\), when \(u\) receives a hello message from a node (i.e., \(v\)) that is not in \(u\)'s neighbor list (see line 8), it computes the distance from \(v\) to \(u\) (i.e., \(d_{v,u}\)) by means of the Formula (4) (see line 9), and adds this neighbor \(v\) and the distance \(d_{v,u}\) to the list \(L_{u,nei}\) (see line 10). Also, \(d_{u,max}\) is updated according to the size of \(d_{v,u}\) and \(d_{u,max}\) (see line 11). The updated neighbor list needs to be sent to all the nodes in the neighborhood of \(u\). Also, when \(u\) receives a hello message from an already known neighbor \(v\) but \(v\)'s hello message does not include \(u\) as a neighbor (see line 13), it needs to resend its hello message, where the number of retransmission for the hello message is kept in the variable \(N\) that is initialized as _zero_ (see line 1) at the beginning of neighborhood discovery process. Therefore, the boolean variables \(FLAG_{1}\) and \(FLAG_{2}\) are used to control the transmission of these messages, which are initialized as _false_ (see line 6) at the beginning of the time \(\Delta\) and then refreshed as _true_ (see lines 12 and 14) if new hello messages are received during the time \(\Delta\). After the time \(\Delta\), if the retransmission for the hello message is needed, the variable \(N\) is increased by 1 (see line 17). Moreover, if \(N\) is not less than the predefined value \(N_{max}\), node \(u\) terminates the neighborhood discovery process regardless of any value taken by \(FLAG_{1}\) or \(FLAG_{2}\) (see line 18). As discussed in [3], if a network is connected before cluster formation, it is also connected after cluster formation as long as \(R_{inter}\) is not greater than \(3R_{intra}\), where \(R_{inter}\) is the inter-cluster transmission range and \(R_{intra}\) is the intra-cluster transmission range. Therefore, if node \(i\) is elected as a MCH node, it employs the clustering range size that is not more than \(d_{i,max}/3\), which can make sure that the distance between node \(i\) and its neighboring MCHs is not more than \(d_{i,max}\).