Time Synchronization and Localization in Sensor Networks

So-called sensor nodes combine means for sensing environmental parameters, processors, wireless communication capabilities, and autonomous power supply in a single compact device. Networks of these untethered devices can be deployed unobtrusively in the physical environment in order to monitor a wide variety of real-world phenomena with unprecedented quality and scale while only marginally disturbing the observed physical processes. Due to the close integration of sensor networks with the real world, the categories time and location are fundamental for many applications of sensor networks, for example to interpret sensing results (e.g., where and when did an event occur) or for coordination among sensor nodes (e.g., which nodes can when be switched to idle mode). Hence, time synchronization and sensor node localization are fundamental and closely related services in sensor networks. Existing solutions for these two basic services have been based on a rather narrow notion of a sensor network as a large-scale, ad hoc, multi-hop, unpartitioned network of largely homogeneous, tiny, resource-constrained, mostly immobile sensor nodes that would be randomly deployed in the area of interest. However, recently developed prototypical applications indicate that this narrow definition does not cover a significant portion of the application domain of wireless sensor networks. Our thesis is that applications of sensor networks span a whole design space with many important dimensions. Existing solutions for time synchronization and node localization do not cover important parts of this design space. Substantially different approaches are required to support these regions adequately. Such solutions can actually be provided. We support this thesis by proposing a design space of wireless sensor networks where concrete applications can be located at different points of the space. We identify two important regions in the design space that are not appropriately supported by existing methods for time synchronization and node localization. We also propose, implement, and evaluate new solutions that cover these regions. The practical feasibility of our approaches is demonstrated by means of a typical sensor network application which requires time synchronization and node localization. Our approach to time synchronization supports applications where network connectivity is intermittent. The idea underlying our Time-Stamp Synchronization method is to avoid proactive synchronization of the clocks of all nodes in a network. Instead, the clocks of the sensor nodes run unsynchronized, each defining its own local time scale. Only if clock readings are exchanged among nodes as time stamps contained in network messages, these time stamps are transformed from the time scale of the sender to the time scale of the receiver. This approach is scalable, since time is only synchronized on demand where and when needed by the application. The approach is also resource efficient, since it piggybacks on existing message exchanges. Our approach to node localization supports tiny sensor nodes known as Smart Dust. The Lighthouse Location System is based on a single beacon device that emits particular optical signal patterns. Sensor nodes can autonomously infer their location by passively observing these signals. This approach is scalable, since each node infers its location independent of other nodes. A single beacon device emits long-range signals in broadcast mode and can support arbitrary network densities. The approach is resource efficient, since the sensor nodes do not actively emit any signals. Only a tiny, energy-efficient optical receiver is needed to infer locations.