We have presented a rationale for using Random, Ephemeral TRansaction Identifiers (RETRI) in sensor networks. In our scheme, nodes pick semi-random identifiers that are used for the duration of a single transaction. Occasionally, identifier conflicts lead to losses, which have a small marginal effect on a network which must already be highly robust to losses due to the vagaries of RF connectivity or node dynamics. Persistent identifier collisions are avoided by making identifiers ephemeral: a new one is picked for each transaction. For many applications, we believe this technique is superior to the alternatives: statically-allocated, globally unique node identifiers are typically much longer, and protocols that dynamically assign locally unique addresses may be highly inefficient given the high rate of dynamics in sensor networks and low data rate over which to amortize the cost of the protocol.
We have also developed a simple model for predicting the rate of identifier collisions in a distributed system that uses RETRI. By predicting collisions we are able to model the overall efficiency of RETRI versus a static allocation policy for a given identifier size, data size, and average number of concurrent transactions. These models have been validated through experiments using an actual implementation.
Our models suggest that RETRI is superior to alternatives in distributed systems with the following properties:
RETRI improves the scaling properties of such distributed systems by allowing the size of the identifier space to grow as a function of the system's transaction density, rather than its overall size. RETRI can also significantly reduce the overhead required to transmit data by optimizing the number of header bits transmitted per data bit. By the same token, RETRI does not help in distributed systems that do not exhibit locality; if the optimum number of bits needed by RETRI is the same as the number of bits required for globally unique static allocation, traditional static allocation will always be better.
Although our model was successful in predicting performance in our
simple testbed, predicting performance in a more complex system will
be more difficult. In our ongoing research, we are refining our
analysis of RETRI's expected performance and continuing larger-scale
experiments. Specifically, we are interested in capturing the effects
of listening and non-uniform transaction lengths in our model. A
model of the system topology will be required to capture the effect of
listening so that problems such as hidden terminal effects are taken
into account. We are also investing more accurate ways of estimating
the typical transaction density 
.
Because the utility of RETRI increases as the transaction density decreases, RETRI is most useful in distributed systems that exhibit the highest degrees of locality in their interactions. We are therefore also investigating techniques for maximizing locality in sensor network interactions.
The authors are grateful to Ashish Goel for help in the development of our analysis. Lewis Girod also made contributions to our analysis in addition to helping to build our experimental testbed.
This work was supported by DARPA under grant No. DABT63-99-1-0011 as part of the SCADDS project, and was also made possible in part due to support from Cisco Systems.
0.96001431