The previous section seems to paint a bleak picture of our options for designing an efficient addressing scheme for sensor networks. Large packets or high data rates provide plenty of bits over which to amortize either the cost of addresses that are long enough to be globally unique, or the cost of running a protocol that assigns locally unique addresses. We are not so lucky in low data rate distributed systems with high dynamics and energy constraints.
The SCADDS project [6] provides a potential framework for a solution because is uses attribute-based data naming [17,1,13]. In SCADDS, applications are unlikely to ask: ``Was there motion detected at sensor #27.201.3.97?'' Rather, they might ask: ``Was there motion detected in the north-east quadrant?'' or ``Where has motion been detected recently?'' This kind of data naming will be application-specific, and effectively moves naming, addressing, and even routing from the network layer into the application.
We wondered, if unique addresses are only being used as unique identifiers--and their significance as addresses are being ignored--why are they still sent in each packet?
Our idea, at its core, is very simple: whenever a guaranteed-unique identifier is needed, an ephemeral, randomly selected, probabilistically-unique identifier can be used instead. Of course, there is a chance that two peers will use the same identifier at the same time. We do not try to resolve such conflicts. Identifier collisions lead to lost transactions, and are treated like any other loss. Sensor networks already must be highly robust to existing common sources of loss such as RF collisions and node or environment dynamics that change connectivity. Occasional losses due to identifier collisions are likely to have a negligible marginal effect considering the losses that sensor networks must already assume. By choosing a new random identifier for each transaction, persistent losses are avoided.
This scheme is best illustrated with an example. In Section 2.1, we described IP packet fragmentation and noted that it depends on having a unique packet identifier. IP uses the sender's unique IP address plus an identifier generated by the sender. In our Address-Free Fragmentation (``AFF''), each packet simply receives a random packet identifier. Once an identifier is selected for a packet, all of that packet's fragments receive the same identifier, allowing receivers to correctly reconstruct the packet. The next packet receives a new random identifier. For this service, we define a ``transaction'' as the transmission of all of a single packet's fragments.
Often, an identifier is simply a way to reference state that is kept on a transmitter or receiver. The identifier provides continuity among the packets that make up a logical transaction. Fragmentation is an example that illustrates the identifier's role. By separating the function of an address from that of a unique identifier, we free nodes from using addresses in situations when a unique identifier is really all that is needed.
Because new identifiers are selected for each packet, the AFF identifier alone is not sufficient to tell a receiver which node sent a packet, or even if two successive packets were sent by the same node. Of course, there may still be situations when a specific node needs to be identified--for example, for debugging or maintenance purposes. Long, globally unique identifiers, statically assigned like Ethernet hardware addresses, are appropriate for this. In AFF, we are not arguing against assigning globally unique identifiers to nodes. Rather, we are suggesting that unique identifiers should be used sparingly--even if they have been assigned--in favor of AFF identifiers that are likely to be much shorter. A node's unique identifier can be sent as data, on demand, instead of in the header of every packet.
For scalability, interactions in sensor networks are being designed to be localized. The energy cost of communication makes local processing and summarization at each node far more efficient than simply forwarding large amounts of data end-to-end through many hops [16]. AFF takes advantage of this spatial locality of sensor networks: nodes that are far apart may use the same identifier at the same time. AFF also takes advantage of temporal locality: nearby nodes can use the same identifier at different times. AFF identifiers must only be unique to a particular place at a particular time. In contrast, globally unique addresses must be unique with respect to every other node that exists. By leveraging locality, the size of AFF identifiers must only scale with the transaction density of a growing sensor network, while a global address space must scale with the total number of nodes in the network. For these reasons, we expect that AFF identifiers can be much shorter than globally unique addresses.
One heuristic that can significantly improve the performance of the scheme is listening. That is, instead of picking identifiers completely at random, nodes can avoid using identifiers that are already in use by listening to packets being transmitted. This is not guaranteed to work perfectly, of course: two nodes that are not in range of each other might pick the same identifier when trying to communicate with a receiver that lies in between them.4 (To help alleviate this problem, the receiver could try to send an explicit ``identifier collision notification'' to the two senders.)
Packet loss may also prevent perfect listening. In addition, some nodes may choose to minimize the time they spend listening because of the significant power requirements of running a radio. Because of these limitations, listening is usually not as helpful as making the size of the identifier pool larger, but it does help to make the best possible use of available resources. Listening has been successfully used to reduce the probability of address allocation collisions in other contexts such as SDR [8], a tool for distributed allocation of Internet multicast addresses.