Random, Ephemeral Transaction Identifiers in Dynamic Sensor Networks¹

Jeremy Elson and Deborah Estrin
Department of Computer Science, University of California, Los Angeles; and
USC/Information Sciences Institute
{jelson,estrin}@isi.edu

Abstract:

Recent advances in miniaturization and low-cost, low-power design have led to active research in large-scale, highly distributed systems of small, wireless, low-power, unattended sensors and actuators. We explore the use of Random, Ephemeral TRansaction Identifiers (RETRI) in such systems, and contrast it with the typical design philosophy of using static identifiers in roles such as node addressing or efficient data naming. Instead of using statically assigned identifiers that are guaranteed to be unique, nodes randomly select probabilistically unique identifiers for each new transaction.

We show how this randomized scheme can significantly improve the system's energy efficiency in contexts where that efficiency is paramount, such as energy-constrained wireless sensor networks. Benefits are realized if the typical data size is small compared to the size of an identifier, and the number of transactions seen by an individual node is small compared to the number of nodes that exist in the entire system. Our scheme is designed to scale well: identifier sizes grow with a system's density, not its overall size. We quantify these benefits using an analytic model that predicts our scheme's efficiency. We also describe an implementation as applied to packet fragmentation and an experiment that validates our model.