Adaptive Tree Addressing Scheme for Wireless Ad Hoc and Sensor Networks
Address assignment in wireless sensor networks, where nodes have limited resources, is a challenging issue. We introduce a novel concept of organizing address space into a multi-dimensional hypercube, as a 3-dimensional space shown by Figure 1, and then transforming that space into a tree structure. The tree dynamically and adaptively grows along any dimension as new nodes join. Our scheme is efficient and has low storage and communication costs. It avoids bottlenecks typically faced by central address assignment approaches and eliminates a need for address conflict detection and resolution mechanism as needed by many distributed addressing schemes. It also removes a need for routing tables by allowing nodes to route frames along underlying addressing tree.
Background & Objective: Address space is a precious network resource that must be utilized judicially. An addressing scheme must be robust and flexible enough so that it adapts to geographical distribution of nodes to avoid formation of address starved pockets in networks. Finally, a distributed addressing scheme should be able to identify and reclaim addresses assigned to devices that ceased to function. Our scheme aims at addressing these.
Technical Discussion: We organize address space into an N-dimensional hypercube, where N>1. Each address, thus, consists of N values called address components. There are constraints on the number of address values a node gets allocated, called its address share, which it can freely assign to its children. In general, nodes along nth dimension, 1=n=N, can have up to n children. That defines a mechanism for mapping the address space into a tree structure, which makes the basis of our approach. We partition the hypercube by cutting its size along all dimensions, for example, to half. Initially we use only this smaller cube, called active address space (AAS), for address assignment. If any node needs additional addresses, it can expand AAS along a suitable dimension by allocating an extra bit to the corresponding address component, thus, effectively doubling its size. A node can always expand AAS if at least one free bit is available. After each expansion, however, rest of the nodes must be informed about new composition of addresses. That is done by transmitting a network wide broadcast frame. Our scheme offers a trade off between adaptability and cost (due to broadcasts) making it well suited to a wide spectrum of applications.
Technology Area: Digital Communications
Modification Date: July 3, 2007