Recent years have seen growing popularity of multi-hop wireless networks such as wireless mesh networks and sensor networks. Such systems require efficient lookup services for reliable system operation such as packet routing, key-discovery, and object lookup. The lack of infrastructure, however, makes the centralized lookup fail to scale in multi-hop wireless networks. For example, consider a citywide wireless mesh network which provides wireless connection service to a number of mobile users. Due to a high volume of user access and inherent vulnerability of wireless links, centralized authentication methods fail to scale. The decentralization of user authentication, however, faces a challenge of key discovery ; how to find the location of user keys. Motivated from the user authentication problem in wireless mesh networks, this dissertation work aims to provide efficient and scalable distributed lookup services for multi-hop wireless networks.

Employing the notion of peer-to-peer lookup where each node can both query and respond, I present two different methods: Valley-Walk and Rigs. A loosely-structured scheme Valley-Walk strategically places object copies and locates them efficiently only with a minimal local structure. The Valley-Walk finds target objects in near-optimal hop counts with a moderate number of copies (e.g., 10% the network size) stored in the network. Without a global structure, however, Valley-Walk fails to guarantee the low cost search with a small number of copies.

A tightly-structured scheme Rigs (Ring Interval Graph Search) realizes a Distributed Hash Table (DHT) in multi-hop wireless networks. Experimental study shows the limitations of existing DHTs in mult-hop wireless networks due to its independence of underlying topology. Unlike DHT, Rigs constructs a search structure Ring Interval Graph such that queries are forwarded only to local neighbors. Rigs guarantees successful object lookup with near-optimal performance.