# LESS: Link Estimation with Sparse Sampling in Intertidal WSNs
## 5 Design of \(Less\) Protocol
### Protocol Overview  
The protocol is illustrated in Figure 7. We interpret LESS from sink node (which can be connected to a PC and therefore its power and computation capability is not limited) side and normal node side. The sink node is composed of initialization module, broadcast module, reconstruction module and analysis module. The sink node determines the sampling rate (SR) and scheduling algorithm with which the normal nodes perform measurements accordingly. Normal nodes measure link quality and upload the measurement results by embedding them in data packets, e.g., the monitored environment data in our system. The sink node then reconstructs the link quality matrix, thereby calculating proper routing paths. **Initialization Module:** In this module, the initial sampling rate and scheduling algorithm are determined. The default sampling rate is set to \(0.6\) and is adjusted based on the measurement results from normal nodes, considering the system requirements, i.e, energy efficiency and accuracy. Besides, the default scheduling algorithm is also chosen in this module based on the availability and property of system knowledge. **Broadcast Module:** In this module, the sink node broadcasts specified sampling rate (either from the initialization module or from the analysis module) and scheduling algorithm to normal nodes. This module is triggered by the the analysis module if the sampling rate is updated. The broadcast procedure can use protocols such as ADB [55] and BPS [56]. **Reconstruction Module:** The reconstruction module in the sink node computes and reconstructs the link quality matrix \(X\) from sparsely-sampled measurements. On the sink node side, this module is able to recover the original \(X\) with the tailored CS with high accuracy. With the recovered \(X\), here is the link quality matrix of the network, the sink can decide a routing path for each node with the guidance of typical routing protocols (i.e., Dijkstra shortest path algorithm [57], CTP [37]). Generally, the sink node is more powerful and directly connected with a PC, therefore adding the reconstruction module on sink node will not affect the lifetime of a system due to energy consumption. **Analysis Module:** This module checks the reconstruction result and determines corresponding strategies under different conditions. * **Condition 1 (C.1)**: Update sampling rate. If any of the two conditions are satisfied, sampling rate needs to be increased: (1) over **30%** of nodes show deficiency in data collection (PDR decreases up to **20%** during the last _10_ cycles); and/or (2) did not receive packets from over **10%** of nodes during the last _10_ cycles. If the following conditions are satisfied, the sampling rate should be decreased: (1) the average PDR increases **20%** during the last _10_ cycles; and (2) the average PDR stays in a considerable level (over **90%**) for over _30_ cycles. Note that the lowest sampling rate should equal to the initial sampling rate. * **Condition 2 (C.2)**: Update routing path. If the reconstructed link quality matrix produces different and new routing paths, the sink node informs relevant nodes to change their parent nodes. Occurrence of _C.1_ and _C.2_ indicates improper parameters, i.e., sampling rate and routing path setting in LESS. For example, in high-tide period, the sparsity of the link quality matrix is worse than that in low-tide period, therefore a higher sampling rate is demanded. We then explain LESS from the normal node side. **Measurement and Upload Module:** With the sampling rate (predefined or updated by the sink node) and the scheduling algorithm, nodes can regulate their behaviors for link quality measurement locally. To alleviate the overhead of transmission, the measured information is attached to normal data packets generated or relayed by the node. **Routing Path Update Module:** When the normal nodes receive commands for routing path update from the sink, they change their parent nodes immediately. The data format of the command will be discussed in detail later.