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 [2,10,6]. The vision of many researchers is to create sensor-rich ``smart environments'' through planned or ad-hoc deployment of thousands of sensors, each with a short-range wireless communications channel, and capable of detecting ambient conditions such as temperature, movement, sound, light, or the presence of certain objects.
While this new class of distributed systems has the potential to enable a wide range of applications, it also poses serious design challenges, described more fully by KKP [10] and EGHK [6]. The sheer number of these devices makes global broadcasting undesirable; wireless nodes' limited communication range relative to the geographic area spanned by the system often makes global broadcasting so inefficient that it is infeasible. As a consequence, many argue that nodes must depend on localized algorithms--making control decisions based solely on interactions with neighbors, without global system knowledge [6,9].
Sensor networks must be energy-efficient. Most current network protocols are designed to be conservative only in their use of bandwidth or required processing. Many nodes in the emerging sensor systems will be untethered and therefore have small energy reserves. All communication--even passive listening--will have a significant effect on those reserves. Therefore, to maximize the lifetime of the system, it is critical to maximize the usefulness of every bit transmitted or received [16].
Sensor networks are expected to be dynamic. Over time, sensors may fail or new sensors may be added. Sensors will experience changes in their position, reachability, available energy, and even task details. These changes make configuration unacceptable; the system must evolve to make the best use of available resources.
Sensor networks must be self-configuring. Large-scale networks such as the Internet work in the face of brittle software partly because the number of people maintaining the network has grown along with the size of the network itself. In contrast, there may be a single human responsible for thousands of nodes in a dense sensor network. It simply becomes impractical to imagine any design where each of these devices requires individual attention. In fact, manual configuration is ruled out completely if sensors are dropped into inhospitable terrain. This is expected in disaster-relief scenarios such as earthquakes and fires.
All of these distinguishing characteristics can potentially affect critical aspects of the system's design--routing and addressing mechanisms, naming and binding services, application architectures, security mechanisms, and so forth. Many of these problems are more challenging than their analogues in the traditional networking and distributed systems spaces, but there are also new opportunities for solutions.
This paper focuses on one such opportunity: a design philosophy for sensor networks where small, randomly selected, ephemeral, probabilistically unique transaction identifiers (which we call RETRI) are used in place of identifiers that are guaranteed to be unique. We define a ``transaction'' quite generally to be any computation during which some state must be maintained by the nodes involved. The identifier might be playing any of a number of roles; for example, a node's address, or the abbreviated form of a commonly-occurring bit sequence used in compression schemes. In traditional distributed systems, such identifiers are guaranteed to be unique and unambiguous. This guarantee comes with a number of important costs, described in the next section, that RETRI helps to avoid.
Most importantly, RETRI changes the scaling properties of a distributed system such that identifier sizes are tied to a system's transaction density, not its overall size. We define the transaction density as the average number of transactions that occur in the same place (connectivity-wise) and at the same time in a system. Many factors affect this value. Networks designed using spatially localized algorithms will have much lower transaction densities than those in which all nodes can potentially peer with each other. Higher physical node densities have an important effect because of the broadcast nature of the wireless medium. Temporal locality and the average duration of a transaction are also important: spatially local nodes that transmit simultaneously will see a higher transaction density than a group that spreads out its communication over time. Our scheme scales well because all of these factors can remain constant in a distributed system as it grows in size.
We show how RETRI 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.
Although our premise is applicable to many uses of identifiers, we studied it in the context of one particular use: unique node addresses. We explore the idea of ephemeral identifiers using an address-free packet fragmentation service as a case study. Our contributions are the description of this address-free method, a simple model that predicts its performance, and an implementation that validates our model. The next section will review the traditional role of network addresses and discuss their costs. Section 3 presents our address-free fragmentation. In Section 4, we analyze our architecture and develop a model to evaluate its performance. We describe an actual implementation and experiment used to validate our model in Section 5. Section 6 describes other contexts in which RETRI can be used. Related work is reviewed in Section 7. Finally, in Section 8, we present our conclusions.