Inherent to the design of most distributed systems today is the assumption that each node has a unique network address. These addresses appear in every packet to identify its source and destination. We will consider special addressing requirements that a sensor network may have. However, it is useful to first reconsider the role that addresses play in traditional distributed systems.
One of the primary purposes of an address in a traditional distributed system is to provide topological information that can be used to find routes. Addresses are sometimes also used as names in order to specify a communications endpoint: ``I need to contact that node.'' These roles are the purest for an address according to the generally accepted definitions of names, addresses, and routes [18].
An important property of addresses in traditional distributed systems is that every node has a globally unique one. Addressing therefore has an additional benefit--essentially a side effect--of assigning unique identifiers to nodes. Unlike addresses, unique identifiers have no inherent meaning. They have no special properties other than their mutual distinctiveness. Many protocols are designed under the assumption that unique identifiers are available; addresses are sometimes used in this role simply because they are already there. We will illustrate this point with two examples:
In a system where each node has a unique address, allowing those addresses to serve the dual role of unique identifiers is often a good idea and a natural choice. As we will discuss in Section 3, a key to our architecture is separating these two roles. Others have objected to the overloaded role of addresses for various reasons; Chiappa's ``Nimrod'' architecture [3] is one example. We chose to separate the roles because unique addresses come with a price. In fact, in some contexts, they can be quite expensive.
Most addressing schemes can be classified as using either global or local addresses. Each has its own advantages and disadvantages.
In systems such as Ethernet [12], every node that exists has a globally unique address. The address is statically assigned, typically at the time of the device's manufacture. This approach guarantees that any particular collection of interconnected Ethernet devices will have distinct addresses. However, it can be inefficient if the number of devices that exist is much larger than the number that are interconnected. Ethernet's large data payloads and lack of energy constraints make this inefficiency small, and certainly well worth the convenience that it buys. In contrast, we will argue in the next section that the cost of globally unique addresses is much higher in a sensor network.
An alternative is to configure nodes with addresses that are locally unique. That is, each node in a distributed system has an address that is unique with respect to its potential peers, based on the connectivity of the network or the scope of communication. Devices that are mutually disconnected may share the same address at the same time. This is in contrast to globally unique addresses that are always distinct with respect to every other device that exists.
Global address spaces tend to be very large to make decentralized allocation more convenient, and to accommodate growth in the number of nodes. If the number of interconnected devices is significantly smaller than the total number of devices, locally unique addresses can use far fewer bits than globally unique addresses. For example, although Ethernet nodes use 48 bit addresses, a typical Ethernet of a few hundred nodes could use only 10 or fewer bits if the addresses were locally assigned. In contrast, such savings are not possible in IP addressing because every node on the Internet can potentially communicate with every other node.3
Different methods exist for assigning local addresses. The simplest example is manual configuration. Protocols such as DHCP [5] allocate addresses from a local authority. More complex schemes such as the multicast address allocation in SDR [8] and MASC [11] listen to the addresses already in use, allocate addresses autonomously, then detect collisions and resolve conflicting address claims. They also use explicit scoping to achieve spatial reuse of addresses.
Complementary to the discussion of the benefit of an address must be a discussion of its cost. By the cost of an address, we refer to the overhead required in terms of network utilization. It is vital to consider this cost in unattended wireless sensor networks where, as Pottie points out, every bit transmitted reduces the lifetime of the network [16]. We do not attempt to quantify factors such as the human effort required to coordinate a global address allocation.
A key factor to consider is that both the packet size and data rate in many typical sensor networks will be very small. This is by design: the energy cost of communication makes it desirable for nodes to minimize the size and frequency of transmissions by doing as much local processing, summarization, and aggregation of data as possible. Although sensors will transmit large messages occasionally, we expect that they will normally transmit periodic messages consisting of only a few bits to describe the current state--perhaps the ambient temperature or the number of vehicles detected in the past hour.
The cost of an address in an energy-constrained distributed system can be considered high if the address space is underutilized and the address itself accounts for a significant portion of the total number of bits transmitted. In sensor networks, globally unique addresses would need to be very large--at least as large as Ethernet's 48 bits--compared to the typical few bits of data attached to them. Therefore, local addressing seems to be needed.
To maintain local addresses, a sensor network could use a protocol that dynamically assigns addresses to nodes based on the addresses of other nodes in the neighborhood. However, as the network topology becomes more dynamic, more work is required to keep addresses locally unique. This scheme will be efficient only as long as the address-allocation overhead is small compared to the amount of useful data transmitted. In a static system, the work done at the beginning to resolve address conflicts is amortized over all the work done in the system thereafter. In sensor networks, the expected dynamics make this scheme potentially very inefficient given the low data rate.
The other methods for assigning locally unique addresses we discussed in Section 2.2 are also inappropriate for sensor networks. Manual configuration is clearly not possible for reasons we described in Section 1. A central address authority is not possible because of the highly decentralized nature of the network and the lack of global knowledge at any single node.