Efficient Peer-to-Peer Lookup in Multi-hop Wireless Networks
Minho Shin · KSII Transactions on Internet and Information Systems · 2009
In recent years the popularity of multi-hop wireless networks has been growing.Its flexible topology and abundant routing path enables many types of applications.However, the lack of a centralized controller often makes it difficult to design a reliable service in multi-hop wireless networks.While packet routing has been the center of attention for decades, recent research focuses on data discovery such as file sharing in multi-hop wireless networks.Although there are many peer-to-peer lookup (P2P-lookup) schemes for wired networks, they have inherent limitations for multi-hop wireless networks.First, a wired P2P-lookup builds a search structure on the overlay network and disregards the underlying topology.Second, the performance guarantee often relies on specific topology models such as random graphs, which do not apply to multi-hop wireless networks.Past studies on wireless P2P-lookup either combined existing solutions with known routing algorithms or proposed tree-based routing, which is prone to traffic congestion.In this paper, we present two wireless P2P-lookup schemes that strictly build a topology-dependent structure.We first propose the Ring Interval Graph Search (RIGS) that constructs a DHT only through direct connections between the nodes.We then propose the ValleyWalk, a loosely-structured scheme that requires simple local hints for query routing.Packet-level simulations showed that RIGS can find the target with near-shortest search length and ValleyWalk can find the target with near-shortest search length when there is at least 5% object replication.We also provide an analytic bound on the search length of ValleyWalk.