Infrastructures for data dissemination and in-network storage in location-unaware wireless sensor networks:

For wireless sensor networks with many location-unaware nodes, we propose mechanisms to organize nodes in an infrastructure of intersecting paths, suitable for efficient data dissemination and event localization. As an underpinning for such an infrastructure, we propose a protocol, dubbed BeSpoken, that steers data transmissions along a straight path called a spoke. The BeSpoken protocol implements a simple, spatially recursive process, where a basic set of control packets and a data packet are exchanged repeatedly among daisy-chained relays that constitute the spoke. Hence, a data packet originated by the first relay makes a forward progress in the direction of the spoke. Despite the simplicity of the protocol engine, modeling the spoke process is a significant challenge. The protocol directs data transmissions by randomly selecting relays to retransmit data packets from crescent-shaped areas along the spoke axis. The resulting random walk of the spoke hop sequence may be modeled as a two dimensional Markov process. Analysis of this model results in design rules for protocol parameters that minimize energy consumption while ensuring that spokes propagate far enough and have a limited wobble with respect to the spoke axis. In addition, adaptive mechanisms are proposed that increase the propagation distance under the same energy per spoke hop. Finally we show how the spokes serve as the building block of a web-like infrastructure that can be used for data source localization and efficient data search and dissemination. In particular, we demonstrate how to increase data availability and persistence through the application of distributed coding techniques over concentric circular subnetworks forming the infrastructure. We study decentralized, Fountain, and network-coding based strategies for facilitating data collection, which rely on the stochastic diversity of data storage. The goal is to allow for a reduced delay collection by a data collector who accesses the circular network at a random position and random time. Data dissemination is performed by a set of relays which form a circular route to exchange source packets. The storage nodes within the transmission range of the route's relays linearly combine and store overheard relay transmissions using random decentralized strategies. An intelligent data collector first collects a minimum set of coded packets from a subset of storage nodes in its proximity, which might be sufficient for recovering the original packets and, by using a message-passing decoder, attempts recovering all original source packets from this set. Whenever the decoder stalls, a source packet which restarts decoding is polled/doped from its original source node. The random-walk-based analysis of the decoding/doping process furnishes the collection delay analysis with a prediction on the number of required doped packets. The number of doped packets can be surprisingly small when employed with an Ideal Soliton code degree distribution and, hence, the doping data collection strategy may have the least collection delay when the density of source nodes is sufficiently large. We also demonstrate that network coding makes dissemination more efficient at the expense of a larger collection delay. Not surprisingly, a circular network allows for a significantly more (analytically and otherwise) tractable strategies relative to a network whose model is a random geometric graph.Ph.D.Includes bibliographical references (p. 124-128)by Silvija Kokalj-Filipovi