Associative routing for wireless sensor networks

Traditionally routing in computer networks has focused on finding paths along which data packets could be delivered to pre-identified destination nodes. Most existing routing protocols rely on the use of network addresses as unique node or group identifiers that are usually numeric and independent of any application semantics. The semantically-oblivious identification has forced network designers to incorporate resource/service discovery techniques at higher layers of the network stack, resulting in unnecessary overhead. While such overhead can be tolerated in high-speed wired networks, it significantly limits performance and network lifetime in wireless infrastructure-less networks with battery-powered resource-constrained devices like sensor networks. Moreover, sensor nodes are more naturally anonymous and therefore assigning unique identifiers to individual node limits network scalability and imposes significant overhead on resource management. In this paper, we propose associative routing as a class of routing protocols that enables dynamic semantically-rich descriptive identification of network resources and services. As such, associative routing presents a clear departure from most current network addressing schemes, eliminating the need for a separate phase of resource/service discovery. We hypothesize that since, in essence, resource discovery operates similarly to path discovery then both can be performed in a single phase, leading to significant reduction in traffic load and communication latency without any loss of generality. We also propose a framework for associative routing and present adaptive multi-criteria routing (AMCR) protocol as a realization of associative routing for sensor networks. AMCR exploits application-specific message semantics, represented as generic criteria, and adapts its operation according to observed traffic patterns. Analytical results demonstrate the effectiveness, efficiency, and scalability of AMCR.