• KSII Transactions on Internet and Information Systems
    Monthly Online Journal (eISSN: 1976-7277)

Efficient Peer-to-Peer Lookup in Multi-hop Wireless Networks

Vol. 3, No.1, February 23, 2009
10.3837/tiis.2009.01.001, Download Paper (Free):

Abstract

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.


Statistics

Show / Hide Statistics

Statistics (Cumulative Counts from December 1st, 2015)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article

[IEEE Style]
Minho Shin and William A. Arbaugh, "Efficient Peer-to-Peer Lookup in Multi-hop Wireless Networks," KSII Transactions on Internet and Information Systems, vol. 3, no. 1, pp. 5-25, 2009. DOI: 10.3837/tiis.2009.01.001

[ACM Style]
Shin, M. and Arbaugh, W. A. 2009. Efficient Peer-to-Peer Lookup in Multi-hop Wireless Networks. KSII Transactions on Internet and Information Systems, 3, 1, (2009), 5-25. DOI: 10.3837/tiis.2009.01.001