Proactive neighbor localization based on distributed geographic table

Marco Picone, Michele Amoretti, Francesco ZanichelliInternational Journal of Pervasive Computing and Communications 2011 · DOI

TL;DR

This paper introduces the Distributed Geographic Table (DGT), a novel decentralized peer-to-peer framework for proactive neighbor localization. DGT enables mobile devices to efficiently discover and track nearby peers without relying on centralized servers, addressing scalability and privacy concerns in location-based services.

What Problem Does This Paper Address?

Modern applications like social networking, ambient intelligence, and emergency management increasingly rely on real-time location data from mobile devices. Centralized approaches to track and share this data face significant scalability challenges due to the sheer volume of users and the dynamic nature of mobile devices. Furthermore, centralized systems can be expensive to maintain and may raise privacy concerns. The paper aims to solve this by proposing a decentralized, peer-to-peer solution that allows devices to manage their own location information and discover nearby peers efficiently.

Methods

The core of the proposed solution is the Distributed Geographic Table (DGT), a peer-to-peer overlay scheme. DGT organizes peers based on their geographic location, allowing each peer to maintain a "geo-bucket" (GB) data structure. These GBs are essentially lists of known nearby peers, organized into concentric circles around the peer's own location.

The paper details a proactive peer neighborhood construction protocol. Instead of waiting for explicit requests, each peer actively maintains its list of geographic neighbors. This involves:

  • Geo-Buckets (GBs): Each peer stores information about nearby nodes in a set of concentric circles (GBs) with defined radii and thicknesses. Nodes outside this model are stored separately.
  • Peer Lookup (findNodes(GP)): A recursive, asynchronous message-passing protocol is used to discover nearby peers. When a peer needs to find neighbors, it queries its GBs and forwards requests to peers that are likely to have relevant information.
  • Position Update: When a peer moves, it checks if the displacement exceeds a threshold (ε). If so, it updates its neighbors and potentially a bootstrap node to maintain accurate location awareness.
  • Gossiping: To enhance knowledge sharing, gossip information is incorporated into exchanged messages, increasing the overall awareness of available nodes in an area.

Datasets

Not discussed in the paper. The evaluation relies on simulations using realistic mobility models.

Key Insights and Ideas

  • Decentralization is Key for Scalability: The paper strongly advocates for decentralized approaches to handle the massive scale and dynamism of location-based services, moving away from resource-intensive centralized models.
  • Proactive Discovery Reduces Latency: By proactively maintaining neighbor lists, peers can access location information much faster when needed, crucial for real-time applications.
  • Geo-Buckets as an Efficient Data Structure: The GB structure effectively organizes local peer information, allowing for efficient querying and maintenance of neighborhood awareness.
  • Adaptive Parameter Tuning is Crucial: The performance of DGT is shown to be highly dependent on parameters like the number and thickness of geo-buckets (GB configuration), the discovery period, and the position update threshold (ε). Optimal configuration depends heavily on the specific application requirements.
  • Robustness in Dynamic Environments: The DGT protocol demonstrates remarkable robustness, maintaining performance even under significant node churn (disconnections), which is a common challenge in peer-to-peer systems.

Key Results

The paper presents simulation results demonstrating the effectiveness of the DGT protocol:

  • Low Missing Node Percentage (PMN): The percentage of missing nodes in a peer's geo-bucket (PMN) remained consistently low, generally below 10%, and often around 5%, even in highly dynamic scenarios.
  • Low Message Rate (MR): The average number of messages received per second per node (MR) was found to be very low, indicating an efficient use of network resources despite the decentralized nature.
  • Scalability: The protocol showed good performance with up to 2,000 active peers and in larger simulations with approximately 5,400 peers.
  • Robustness: Even with up to 70% of nodes disconnecting simultaneously, the PMN remained stable, highlighting the system's resilience.
  • Parameter Sensitivity: Results indicated that the choice of GB configuration (number and thickness) and the position update threshold (ε) significantly impact performance, with a trade-off between accuracy and message overhead. For instance, a value of ε between 0.35 and 0.6 km was suggested as a good compromise for accuracy and message efficiency.

Limitations and Future Work

  • Parameter Tuning: The paper acknowledges that optimal parameter configuration (GB size, discovery period, ε) is application-dependent and requires careful design phase analysis.
  • Formal Model: The authors plan to investigate a formal model to support the general analysis of the DGT implementation.
  • Trajectory Estimation: Future work includes incorporating peer trajectory estimation to further reduce message exchange.
  • Local Communication: Exploring Ad-Hoc networks for direct peer discovery and information exchange is another avenue for future research.
  • Alternative Routing: The paper mentions ongoing work on a new protocol using a triangular area for routing, which aims to be less bandwidth-consuming.

Summary updated

Abstract

Purpose A large set of valuable applications, ranging from social networking to ambient intelligence, may see their effectiveness and appeal improved when supported by the large‐scale, real‐time tracking of mobile devices, either carried by humans or embedded into vehicles. A centralized approach, where few servers would collect position data and provide them to interested consumers, would hardly cope with the resource demand of the foreseen huge increase of users interested in location‐based services and with the flexibility needs of emerging user‐generated services. The purpose of this paper is to propose a decentralized peer‐to‐peer approach to cope with these requirements, for which positioning information flows directly among mobile devices incurring in limited data exchange. Design/methodology/approach The authors propose a decentralized peer‐to‐peer approach for which positioning information flows directly among mobile devices incurring limited data exchange. A peer‐to‐peer overlay scheme is introduced called distributed geographic table (DGT), where each participant can effectively retrieve node or resource information (data or service) located near any chosen geographic position. Next, the authors describe a DGT‐based localization protocol that allows each peer to proactively discover and track all peers that are geographically near to itself. Findings The authors provide a performance analysis of the protocol by simulating several 1,000 users that move across an urban area according to realistic mobility models. The results show that the solution is effective, robust, scalable and highly adaptable to different application scenarios. Originality/value The new contributions of this paper are a general framework called DGT, which defines a peer‐to‐peer strategy for mobile node localization, and a particular instance of the DGT that supports applications in which every node requires to be constantly updated about the location of its neighbors.
BibTeX
@article{picone2011proactive,
  author = {Marco Picone and Michele Amoretti and Francesco Zanichelli},
  title = {{Proactive neighbor localization based on distributed geographic table}},
  journal = {International Journal of Pervasive Computing and Communications},
  year = {2011},
  doi = {10.1108/17427371111173022},
}
Figure