A Community-Based Routing Algorithm for Opportunistic Networks

Opportunistic networks are special multi-hop ad hoc networks in which nodes exploit any opportunity of pair-wise contact to forward information, without requiring any fixed infrastructures. Routing is one of the most challenging problems in opportunistic networks, because there is not an end-to-end path in most situations. To deal with this issue, researchers have investigated various routing protocols based on redundancy messages or the prediction of future contacts according to the nodes' mobility history. However, most of the previous work ignored the social attributes of nodes, which can be fully utilized to improve routing efficiency. In this paper, we proposes an efficient routing algorithm, community-based routing (CR), where nodes determine which community it belongs to and choose a proper next hop node in order to reduce the number of forwarding and improve the delivery probability. A unique feature of this algorithm is that it records the contact history and calculates the tie strength with other nodes while moving around and exploits the recorded contact history to optimize the forwarding path. We show through simulation that this algorithm is effective and it achieves better performance than Epidemic, Bubble Rap and PROPHET.