## 4 Cluster-Based Distributed Compressed Sensing for QoS Routing
### Event-Driven Clustering
#### 4.1.2 Clustering Algorithm  
The clustering algorithm consists of two parts, i.e., cluster head selection (shown in Algorithm 1) and cluster formation (shown in Algorithm 2). The policy in [35] is referred to improve the robustness of the algorithm in consideration of the impact of lossy links. Before the clustering algorithm is executed, each member informs its neighboring members of remaining energy and channel conditions. According to information received, the IDs of neighbouring members (including itself) that satisfy constraints (5)-(8) will be recorded in set \(\Psi\).  
In the cluster head election phase, each member can autonomously decide whether it can become a cluster head according to received messages. The head selection duration is divided into three time slots. Each member can execute the head selection rule at most twice (one time slot at a time). The operations performed in each time slot are summarized as follows:  
1. In the first time slot, each member performs cluster head selection for the first time. If a member has maximum energy, it broadcasts a _DECLARE_ message (see line 3) to its neighboring members and becomes a candidate cluster head. The candidate cluster head is silent until the end of the cluster head selection process. Otherwise, a member does not send any messages.
2. In the second time slot, the execution process of each member except candidate cluster heads is as follows. Upon receiving a _DECLARE_ message, a member broadcasts an \(ACK\) message to its neighbors to inform them that it has associated with one cluster head. Variable \(t\) is introduced to indicate whether it is the first time a _DECLARE_ message is received (see line 8). If a member receives more than one _DECLARE_ message, it sends an \(ACK\) message once and puts all the IDs of the members that have broadcast _DECLARE_ messages into a set that stores cluster head information, denoted by \(\Phi\). If a member only receives \(ACK\) messages but does not receive any _DECLARE_ messages (there is no candidate cluster head in its neighborhood), it remains silent and removes the neighboring members that have sent \(ACK\) messages from set \(\Psi\).
3. In the third time slot, those silent members in the second time slot perform head selection again.  
```
1\(\Phi\leftarrow\emptyset\); \(t\gets FALSE\);
2 if\(E_{i}==\max_{y_{i}\in\Psi}E_{k}\)then
3 broadcast (\(v_{i}\), \(DECLARE\)) and wait till the end of cluster head selection;
4 end if
5 do
6 if<\(v_{i}\), \(DECLARE\)> is receivedthen
7\(\Phi\leftarrow\Phi\cup\{v_{i}\}\);
8 if!then
9 broadcast (\(v_{i}\), \(ACK\));
10\(t\gets TRUE\);
11
12 end if
13 if<\(v_{i}\), \(ACK\)> is receivedthen
14\(\Psi\leftarrow\Psi\setminus\{v_{i}\}\);
15
16 end if
17 if\(E_{i}==\max_{y_{i}\in\Psi}E_{k}\)then
18 broadcast (\(v_{i}\), \(DECLARE\)) and wait till time out;
19
20 end if
21
22 untiltime out;
```  
**Algorithm 1**Cluster Head Selection  
Next, we explain the cluster formation process. Those members that have been covered by multiple cluster heads follow the rule to associate themselves with a cluster head that has maximum energy. If there is a member node not covered by any cluster heads, the node declares itself as a cluster head.