# An Effective Scheduling Algorithm for Coverage Control in Underwater Acoustic Sensor Network
## 3 Energy-Efficient Coverage Control Using Memetic Algorithm
### Node Wake-Up Scheme  
To achieve energy-saving coverage, we propose a node sleep-scheduling strategy based on a memetic algorithm. However, uncovered events will occur as certain nodes are gradually depleted of energy. Therefore, we propose a wake-up strategy to wake up some sleeping nodes for re-coverage. Assume that the power of the sink node of the network is sufficient to perform ESACC operations and wake-up schemes. Below, we describe the node wake-up scheme. In UASNs, the node wake-up scheme runs in rounds, each of which includes clustering, scheduling, and data-transmission phases. In the clustering phase, nodes form several clusters through self-organizing and select one node in each cluster as the cluster head. The cluster head is responsible for forwarding messages received by the cluster node to the sink node. Then, it enters the scheduling phase. The UASNs applies a TDMA (Time Division Multiple Access) technique to accomplish communication in between the nodes and also their cluster head. Additionally, the cluster head has the ability to connect with the remote base station directly as well as accountable of forwarding the messages gotten from its cluster nodes to the base station. The head node will set up a TDMA timetable as well as send it to its cluster nodes. The cluster nodes could utilize the TDMA timetable to arrange the time slots for every node. Specifically, a TDMA frame consists of a fixed number of time slots, which equals the number of nodes in the cluster. The first time slot of each frame is reserved for the cluster head. After the inter-cluster communication link is established, it enters the data-transmission phase and the cluster members are designated to send data in their respective time slots. Compared with radio channels, the propagation delay of underwater channels is large. Therefore, the guard interval between slots should be set large enough to ensure that the cluster head has completed the reception of the current slot data before the data of the next slot arrives. In the entire network, the length of each frame period is uniform, which determines the interval between two consecutive transmissions. Since the guard interval may be long, the number of cluster members should not be excessive. Figure 4 shows a slot diagram of a TDMA frame period. After completing the data collection, it will enter the next round, re-elect a cluster head, and re-dispatch. According to the node sleep-scheduling scheme, some nodes enter the sleep mode, and the rest are responsible for event monitoring. When the sink node receives a signal from a dead node, i.e., the energy of a certain node is about to run out, the wake-up scheme will wake some of the nodes in the next round. Assume that the energy of node \(n_{i}\) is about to be exhausted (\(E_{n_{i}}<E_{tth}\)). If node \(n_{i}\) is active, then the original composite coverage vector of all nodes is \(c_{n_{i}}^{\Delta}\). If node \(n_{i}\) is dead, then the original composite coverage vector of all nodes is \(c_{n_{i}}^{\
abla}\). Then, according to the Boolean operation, the vector \(c_{un\,c}^{n_{i}}\) that can be obtained by an uncovered event can be expressed as  
\[c_{un\,c}^{n_{i}}=c_{n_{i}}^{\Delta}\oplus c_{n_{i}}^{\
abla} \tag{15}\]  
where \(\oplus\) denotes an exclusive-OR operation in Boolean operations; if \(optcom\) represents an optimal scheduling combination when node \(n_{i}\) runs out, then the pseudo code of the node wake-up scheme is described as follows in Algorithm 2.