May 26-30, 2008 | Pan Hui, Jon Crowcroft, Eiko Yoneki
This paper presents BUBBLE Rap, a social-based forwarding algorithm for Delay Tolerant Networks (DTNs), which improves forwarding efficiency compared to traditional methods like oblivious forwarding and PROPHET. The algorithm leverages social structures, such as community membership and node centrality, to make forwarding decisions. Human mobility traces show that interactions are heterogeneous, with hubs and communities playing significant roles. BUBBLE uses a hierarchical approach, first using global rankings to find nodes in the same community, then using local rankings within that community to forward messages. It is implemented in a distributed manner, making it suitable for decentralized environments like Pocket Switched Networks (PSNs).
The algorithm was evaluated using five experimental datasets, including mobility traces from conferences, universities, and real-world scenarios. Results show that BUBBLE significantly improves forwarding efficiency, with lower delivery costs compared to other schemes. It outperforms PROPHET in terms of delivery ratio and cost, especially when messages are destined for nodes in different communities. The algorithm also demonstrates the effectiveness of using social structures for forwarding, with high correlation between node centrality and delivery performance.
BUBBLE is implemented in a distributed manner, using community detection algorithms like K-CLIQUE and weighted network analysis (WNA) to identify communities. It also approximates node centrality using methods like DEGREE, S-Window, and C-Window. These methods allow for efficient forwarding decisions without requiring global knowledge of all nodes.
The paper also compares BUBBLE with other forwarding algorithms, including WAIT, FLOOD, MCP, LABEL, and PROPHET. Results show that BUBBLE achieves similar delivery ratios to PROPHET but with significantly lower costs. It is particularly effective in multi-community scenarios, where it outperforms other algorithms in terms of delivery efficiency and cost.
The study highlights the importance of social structures in DTNs and demonstrates that leveraging these structures can lead to more efficient and effective forwarding strategies. The results suggest that social-based forwarding is a viable approach for PSNs, with potential for further improvements through better community detection and centrality approximation methods.This paper presents BUBBLE Rap, a social-based forwarding algorithm for Delay Tolerant Networks (DTNs), which improves forwarding efficiency compared to traditional methods like oblivious forwarding and PROPHET. The algorithm leverages social structures, such as community membership and node centrality, to make forwarding decisions. Human mobility traces show that interactions are heterogeneous, with hubs and communities playing significant roles. BUBBLE uses a hierarchical approach, first using global rankings to find nodes in the same community, then using local rankings within that community to forward messages. It is implemented in a distributed manner, making it suitable for decentralized environments like Pocket Switched Networks (PSNs).
The algorithm was evaluated using five experimental datasets, including mobility traces from conferences, universities, and real-world scenarios. Results show that BUBBLE significantly improves forwarding efficiency, with lower delivery costs compared to other schemes. It outperforms PROPHET in terms of delivery ratio and cost, especially when messages are destined for nodes in different communities. The algorithm also demonstrates the effectiveness of using social structures for forwarding, with high correlation between node centrality and delivery performance.
BUBBLE is implemented in a distributed manner, using community detection algorithms like K-CLIQUE and weighted network analysis (WNA) to identify communities. It also approximates node centrality using methods like DEGREE, S-Window, and C-Window. These methods allow for efficient forwarding decisions without requiring global knowledge of all nodes.
The paper also compares BUBBLE with other forwarding algorithms, including WAIT, FLOOD, MCP, LABEL, and PROPHET. Results show that BUBBLE achieves similar delivery ratios to PROPHET but with significantly lower costs. It is particularly effective in multi-community scenarios, where it outperforms other algorithms in terms of delivery efficiency and cost.
The study highlights the importance of social structures in DTNs and demonstrates that leveraging these structures can lead to more efficient and effective forwarding strategies. The results suggest that social-based forwarding is a viable approach for PSNs, with potential for further improvements through better community detection and centrality approximation methods.