# LESS: Link Estimation with Sparse Sampling in Intertidal WSNs
## 1 Introduction  
The intertidal zone is the area between the high tide line and the low tide line, and long served as a testbed for investigating the impact of environmental conditions such as temperature on the ecology of plants and animals. Due to the unpredictable sea waves, the living conditions of intertidal creatures (e.g., mussels, sea stars, oysters and corals) change significantly. For example, mussels are exposed to the sunlight during the low tide and the temperature of rocks (the habitat for mussels) can go up to 60 \({}^{\circ}\)C. When the high tide comes, the sea water cools down the temperature to only 30 \({}^{\circ}\)C. Besides temperature, environmental conditions such as humidity, oxygen concentration and pressure also change significantly during a tidal period. Thus, deploying wireless sensor networks in the intertidal areas to grasp the environment changes provides an efficient method for biologists to obtain the first-hand materials. Deploying a wireless sensor network in the intertidal zone is challenging. In IT-WSNs, packets are expected to be delivered to the sink efficiently with the help of the accurate routing paths. In order to achieve the goal, sensor nodes need to exchange and update the link quality information with neighbors once the link quality changes. However, due to the change of external network conditions in intertidal zones, the network topology may be dynamically changing. For example, wave forces can exceed a category 5 hurricane on an almost daily basis [1] and severe sea waves may impact thecommunication between nodes and damage the connectivity of the network. Thus, an efficient link quality estimation mechanism is crucial. Existing link quality estimation methods like 4-bit [2] and EAR [3] perform well when the network is relatively static. However, in IT-WSNs, these methods suffer from a trade-off between performance and energy cost. Specifically, to capture the frequent changes of the network, sensors have to transmit a large amount of beacons which consume a large portion of energy and bandwidth resources. On the other hand, we can limit the energy consumption by decreasing the frequency of beacon updates, yet at the cost of a lower link quality estimation accuracy and, consequently, poorer packet forwarding performance. In this paper, we strive to mitigate the challenge and manage to strike the balance between accurate link estimation and overwhelming beacon exchanges with sparse sampling. By leveraging the characteristics of link conditions and network system knowledge (e.g., the distribution of sensor nodes and the tide cycle), our approach based on compressive sensing (CS) can obtain high link estimation accuracy while requiring a much fewer amount of link quality measurements and updates. There are additional challenges to apply CS in link quality estimation. First, CS technique requires the data matrix to be sparse; in reality, however, the original data do not always satisfy this requirement, which means CS cannot be directly used for data reconstruction. Second, the noisy measurement, which is common in real-world sensor networks, may greatly impair the performance of CS [4]. To facilitate the use of CS, we specially design the data matrix, the transform matrix and incorporate the system properties in terms of spatial-temporal correlation. With the tailored CS design, we propose \(LESS\)--a link Quality estimation protocol with fine-grained sparse sampling for IT-WSN systems. The key of LESS is to determine which links among all shall be measured, i.e., the scheduling strategy need to achieve both high estimation accuracy and low communication cost. Furthermore, we find that naive CS scheduling algorithms introduce significant errors in the scheduling process as it fails to distinguish different nodes that play unequal roles in the systems (see Section 4 for details).