## 4 Centralized and Distributed Algorithms
### Distributed Has\({}^{4}\)  
The distributed HAS\({}^{4}\) is a multi-round procedure. Each round consists of the following stages: self-elect inquiry, self-elect affirm, root select, root affirm, channel-use broadcast and conflict handler. Sensors serving different roles participate in different stages and show different behaviors in each stage. Moreover, in distributed HAS4, the trade-off factor \(l\) indicates the maximum acoustic path from any \(S_{U}\) sensors to \(S_{A}\) sensors. In distributed HAS4, each \(S_{C}\) node changes itself to be \(S_{A}\) node with probability 1/lifetime. When there are some \(S_{A}\) nodes, the relationship between \(S_{A}\) and \(S_{C}\) becomes a matching problem. Each \(S_{C}\) node takes the distance to each \(S_{A}\) node and the lifetime of each \(S_{A}\) node as the preference to choose a root node. Each \(S_{A}\) accepts some \(S_{C}\) nodes on the purpose of maximizing its group. Once an \(S_{C}\) node joins a group, it becomes \(S_{U}\) node. When there are no \(S_{C}\) nodes, this round of matching problem is solved. The execution of distributed HAS4 on \(S_{C}\) nodes is as shown in Algorithm 2. For each \(S_{C}\) node, in the self-elect inquiry stage, it temporarily changes itself to be an \(S_{A}\) node with probability 1/lifetime and broadcasts a self-elect-inquiry message to its neighbours. If it does not receive any self-elect-inquiry messages from its neighbours or its lifetime is less than all its temporarily \(S_{A}\) nodes, it will successfully be an \(S_{A}\) node and broadcast a self-elect-affirm message. Otherwise, it will change back to \(S_{C}\). Once an \(S_{C}\) node receives a self-elect-affirm message, it will add this node to its root candidate set \(U\). In the root select stage, an \(S_{C}\) node chooses the maximum lifetime node from \(U\) as root, and broadcasts a root-inquire message. If an \(S_{C}\) node receives a positive message in the root affirm stage, it will temporarily become an \(S_{U}\) node and broadcast a channel-occupation message based on the positive message. Once an \(S_{C}\) node receives a channel-occupation message, it will update its available channels. If a temporary \(S_{U}\) node does not receive any channel-occupation message or it has a longer lifetime or is closer to the root, it will successfully be an \(S_{U}\) node. Otherwise, it will change back to \(S_{C}\) and broadcast a channel-collision message. ```
\(U\leftarrow\emptyset\);  ChangeFlag \(\leftarrow\) true; while\(\exists N_{v}\in S_{C}\)do  Change \(v\) to \(S_{A}\) with probability 1/lifetime; ifchange to \(S_{A}\)then  broadcast a self-elect-inquiry message;  end if  Receiving self-elect-affirm messages;  On triggering time; \(U\gets U\bigcup\{M_{i}\}\);  Descending sort \(U\) ;  Choose the first node \(u\) from \(U\) as root;  On triggering time;  Broadcast a root-inquiry message ;  Remove \(u\) from \(U\);  Receiving the decision broadcast; if choose by notthen \(S_{U}\gets S_{U}\bigcup v\);  On triggering time\({}_{2l+2}\);  Broadcast a channel-occupation message;  end if  Update available channel;  Receiving channel-occupation messages; ifcollision then  Broadcast a channel-collision message;  end if else  Update available channel;  Change itself to \(S_{U}\);  end if  end while
```  
**Algorithm 2**Distributed HAS4\(S_{C}\).