Wireless Sensor Networks in Motion - Clustering Algorithms for Service Discovery and Provisioning

The evolution of computer technology follows a trajectory of miniaturization and diversification. The technology has developed from mainframes (large computers used by many people) to personal computers (one computer per person) and recently, embedded computers (many computers per person). One of the smallest embedded computers is a wireless sensor node, which is a battery-powered miniaturized device equipped with processing capabilities, memory, wireless communication and sensors that can sense the physical parameters of the environment. A collection of sensor nodes that communicate through the wireless interface form a Wireless Sensor Network (WSN), which is an ad-hoc, self organizing network that can function unattended for long periods of time. Although traditionally WSNs have been regarded as static sensor arrays used mainly for environmental monitoring, recently, WSN applications have undergone a paradigm shift from static to more dynamic environments, where nodes are attached to moving objects, people or animals. Applications that use WSNs in motion are broad, ranging from transport and logistics to animal monitoring, health care and military, just to mention a few. These application domains have a number of characteristics that challenge the algorithmic design of WSNs. Firstly, mobility has a negative effect on the quality of the wireless communication and the performance of networking protocols. Nevertheless, it has been shown that mobility can enhance the functionality of the network by exploiting the movement patterns of mobile objects. Secondly, the heterogeneity of devices in a WSN has to be taken into account for increasing the network performance and lifetime. Thirdly, the WSN services should ideally assist the user in an unobtrusive and transparent way. Fourthly, energy-efficiency and scalability are of primary importance to prevent the network performance degradation. This thesis focuses on the problems and enhancements brought in by network mobility, while also accounting for heterogeneity, transparency, energy-efficiency and scalability. We propose a set of algorithms that enable WSNs to self-organize efficiently in the presence of mobility, adapt to and even exploit dynamics to increase the functionality of the network. Our contributions include an algorithm for motion detection, a set of clustering algorithms that can be used to handle mobility efficiently, and a service discovery protocol that enables dynamic user access to the WSN functionality. In short, the main contributions of this thesis are the following: 1. Classifications of service discovery protocols and clustering algorithms. We systematically analyse the discovery and clustering mechanisms for WSNs through a thorough review and classification of the state of the art. 2. A generalized clustering algorithm for wireless sensor networks. We propose a clustering algorithm for dynamic sensor networks, which represents a generalization of a set of state-of-the-art clustering algorithms. This generalized algorithm allows for a better understanding of the specialized algorithms and facilitates the definition and demonstration of common properties. 3. Cluster-based service discovery for wireless sensor networks. We propose a cluster-based service discovery solution for heterogeneous and dynamic wireless sensor networks. The service discovery protocol exploits a cluster overlay for distributing the tasks according to the capabilities of the nodes while providing an energy-efficient search. The clustering algorithm is designed to function as a distributed service registry. 4. On-line recognition of joint movement in wireless sensor networks. We propose a method through which dynamic sensor nodes determine whether they move together by communicating and correlating their movement information. The movement information is acquired from tilt switches and accelerometer sensors. 5. A context-aware method for spontaneous clustering of dynamic wireless sensor nodes. We propose a clustering algorithm that organizes wireless sensor nodes spontaneously and transparently into clusters based on a common context, such as movement information. Through these contributions, the thesis opens novel perspectives for WSN applications in the field of distributed situation assessment, where sensor nodes can collaboratively determine the movement characteristics of the people or moving objects and organize in structures that correspond to the real world.