SPread: Exploiting Fractal Social Community for Efficient Multi-Copy Routing in Taxi VDTNs
Bo Wu, Haiying Shen, Kang Chen · IEEE Transactions on Network Science and Engineering · 2018
In this paper, we focus on the multi-copy routing in Vehicle Delay Tolerant Networks (VDTNs) consisted of taxis. Multi-copy routing can balance the network congestion caused by broadcasting and the efficiency limitation in single-copy routing. However, current multi-copy routing algorithms often let different copies of each packet search the destination node independently, which leads to a low utilization of copies. To solve this problem, we propose a fractal Social community based efficient multi-coPy routing algorithm in VDTNs, namely SPread, by taking advantage of social network features (i.e., weak ties and fractal community structure) measured in two large taxi-based Vehicle NETwork (VNET) traces. SPread carefully scatters different copies of each packet to different communities towards the destination community. This ensures that different copies search the destination community through different weak ties. For the routing of each copy, current routing algorithms either fail to exploit nodes' reachability information to others (e.g., centrality based methods) or only use single-hop reachability information (e.g., community based methods). In order to overcome such drawbacks, inspired by the personalized PageRank algorithm, we design new algorithms for calculating vehicles' multi-hop reachability to different communities/vehicles dynamically. Therefore, the routing efficiency of each copy can be enhanced. Furthermore, we propose an Advanced SPread (denoted by ASPread) by exploiting the spatio-contact correlation of the community and the different sizes of communities. ASPread also sends a larger number of copies of a packet to a community with a larger number of vehicles and vice versa. Finally, extensive trace-driven simulation demonstrates the high efficiency of SPread in comparison with state-of-the-art routing algorithms in DTNs, as well as the enhancement brought by ASPread.