Geographic data propagation in location-unaware wireless sensor networks: a two-dimensional random walk analysis

For wireless sensor networks with many location-unaware nodes, which can be modeled as a planar Poisson point process, we investigate a protocol, dubbed BeSpoken, which steers data transmissions along a straight path called a spoke. BeSpoken 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. Bespoken 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. Based on this model, we propose 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. The energy efficiency is demonstrated through simulations of the BeSpoken-based data search, and a comparison with the energy consumption of a search based on directed diffusion.