On Neighbors, Groups and Application Invariants in Mobile Wireless Sensor Networks

The miniaturization and energy-efficient operation of wireless sensor networks (WSNs) provides unprecedented opportunities for monitoring mobile entities. The motivation for this thesis is drawn from real-world applications including monitoring wildlife, assisted living, and logistics. Nevertheless, mobility unveils a series of problems that do not arise in fixed scenarios. Through applications, we distill three of those, as follows. Neighbor discovery, or knowing the identity of surrounding nodes, is the precondition for any communication between nodes. As compared to other existing solutions, we provide a framework that approaches the problem from the perspectives of latency (the time required to detect an amount of contacts), lifetime (the time nodes are expected to last) and probability (the fraction of contacts guaranteed to be detected within a given latency). By formalizing neighbor discovery as an optimization problem, we obtain a significant improvement w.r.t. the state-of-art. We offer a solver providing the optimal configuration and an implementation for popular WSN devices. Group membership, or knowing the identity of the transitively connected nodes, can be either the direct answer to a requirement (e.g., caring for people that are not self-sufficient), or a building-block for higher-level abstractions. Earlier works on the same problem target either less constrained devices such as PDAs or laptops or, when targeting WSN devices, provide only post-deployment information on the group. Instead, we provide three protocols that cover the solution space. All our protocols empower each node with a run-time global view of the group composition. Finally, we focus on the behavior of the processes monitored by WSNs. We present a system that validates whether global invariants describing the safe behavior of a monitored system are satisfied. Although similar problems have been tackled before, the invariants we target are more complex and our system evaluates them in the network, at run-time. We focus on invariants that are expressed as first-order logic formulas over the state of multiple nodes. The requirement for monitoring invariants arises in both fixed and mobile environments; we design and implement an efficient solution for each. Noteworthy is that the solution targeting mobility bestows each node with an eventually consistent view on the satisfaction of the monitored invariants; in this context, the group membership algorithms play the role of global failure detectors.