Abstract
Resource discovery in Mobile Peer-to-Peer (MP2P) networks is challenged by node mobility and the lack of centralized infrastructure. Traditional flooding-based search methods suffer from high latency and significant bandwidth consumption. This paper presents the Dynamic Dominant Index Set (DDIS) mechanism, which constructs a virtual backbone of indexing nodes using an optimized Dominating Pruning algorithm. By proactively caching metadata within a Minimum Connected Dominating Set (MCDS), DDIS significantly reduces search response times and improves scalability compared to conventional flooding techniques.
Introduction
Mobile Ad Hoc Networks (MANETs) consist of autonomous mobile devices that communicate without fixed infrastructure. Implementing Peer-to-Peer (P2P) services over MANETs (MP2P) is difficult due to dynamic topologies and resource constraints. Standard search protocols often rely on flooding, which broadcasts queries to all nodes, leading to high "response delay" and excessive battery drain. To address these issues, a more efficient resource discovery mechanism is required that balances search accuracy with network overhead.
Methodology
The DDIS mechanism optimizes resource discovery by identifying a subset of nodes to serve as a distributed index.
1. MCDS-Based Backbone
The system leverages the Minimum Connected Dominating Set (MCDS) to form a network backbone. In this configuration, every node in the network is either part of the DDIS or a direct neighbor of a DDIS node, ensuring that resource metadata is always within a single hop.
2. Optimized Dominating Pruning (DP)
Since finding an optimal MCDS is NP-complete, DDIS employs an improved Dominating Pruning (DP) algorithm. Unlike standard greedy approaches, DDIS prioritizes "key neighbors"—nodes essential for covering specific two-hop neighbors. This refinement results in a smaller, more efficient set of forwarding nodes.
3. Proactive Metadata Advertising
Peers periodically broadcast "ADV" packets containing metadata. Only nodes within the DDIS backbone cache this information. This proactive approach creates localized lookup tables, allowing for rapid query resolution.
Performance Evaluation
The authors evaluated DDIS using a custom simulation in a $1000m \times 1000m$ area with 10 to 120 peers, utilizing the IEEE 802.11 standard.
Hit Rate and Advertising Intervals
The effectiveness of DDIS is influenced by the frequency of metadata advertisements. As shown in Figure 1, shorter advertising intervals (e.g., 5 seconds) yield higher hit rates, reaching approximately 80% with 100 peers. Conversely, longer intervals reduce network overhead but lower the probability of finding resources.
Response Time and Scalability
A primary advantage of DDIS is its search speed. Compared to traditional flooding, DDIS is 2 to 3 times faster. Furthermore, DDIS demonstrates superior scalability. While flooding search latency increases significantly as the network grows, the response time for DDIS remains relatively stable, hovering around 100 units regardless of peer density (see Figure 2).
Conclusion
The Dynamic Dominant Index Set (DDIS) provides a robust solution for resource discovery in MP2P networks. By shifting search costs to a proactive background process and utilizing an efficient virtual backbone, DDIS achieves low latency and high scalability. Future research will focus on optimizing the trade-off between advertising overhead and query accuracy, as well as assessing the impact of high-velocity mobility on backbone stability.
Summary updated