Date of Award
December 2016
Document Type
Dissertation
Degree Name
Doctor of Philosophy (PhD)
Department
Electrical and Computer Engineering (Holcomb Dept. of)
Committee Member
Haiying Shen
Committee Member
Adam Hoover
Committee Member
Ilya Safro
Committee Member
Yongqiang Wang
Abstract
Vehicle Delay Tolerant Networks (VDTNs) is a particular kind of Delay Tolerant Networks (DTNs), where vehicles equipped with transmission capabilities are interconnected to form Vehicle NETworks (VNETs). Some applications and services on the top of VDTNs have raised a lot of attention, especially by providing information about weather conditions, road safety, traffic jams, speed limit, and even video streamings without the need of infrastructures. However, due to features such as high vehicle mobility, dynamic scenarios, sparsity of vehicles, short contact durations, disruption and intermittent connectivity and strict requirements for latency, many VDTNs do not present satisfactory performance, because no path exists between a source and its target. In this dissertation, we propose three routing methods to solve the problem as follows.
Our first VDTN system focuses on the multi-copy routing in Vehicle Delay Tolerant Networks (VDTNs). Multi-copy routing can balance the network congestion caused by broadcasting and the efficiency limitation in single-copy routing. However, the different copies of each packet search the destination node independently in current multi-copy routing algorithms, which leads to a low utilization of copies since they may search through the same path repeatedly without cooperation. To solve this problem, we propose a fractal Social community based efficient multi-coPy routing in VDTNs, namely SPread. First, we measure social network features in Vehicle NETworks (VNETs). Then, by taking advantage of weak ties and fractal structure feature of the community in VNETs, SPread carefully scatters different copies of each packet to different communities that are close to the destination community, thus ensuring that different copies search the destination community through different weak ties. For the routing of each copy, current routing algorithms either fail to exploit reachability information of nodes to different nodes (centrality based methods) or only use single-hop reachability information (community based methods), e.g., similarity and probability. Here, the reachability of node $i$ to a destination $j$ (a community or a node) means the possibility that a packet can reach $j$ through $i$. In order to overcome above drawbacks, inspired by the personalized PageRank algorithm, we design new algorithms for calculating multi-hop reachability of vehicles to different communities and vehicles dynamically. Therefore, the routing efficiency of each copy can be enhanced. Finally, extensive trace-driven simulation demonstrates the high efficiency of SPread in comparison with state-of-the-art routing algorithms in DTNs.
However, in SPread, we only consider the VNETs as complex networks and fail to use the unique location information to improve the routing performance. We believe that the complex network knowledge should be combined with special features of various networks themselves in order to benefit the real application better. Therefore, we further explore the possibility to improve the performance of VDTN system by taking advantage of the special features of VNETs. We first analyze vehicle network traces and observe that i) each vehicle has only a few active sub-areas that it frequently visits, and ii) two frequently encountered vehicles usually encounter each other in their active sub-areas. We then propose Active Area based Routing method (AAR) which consists of two steps based on the two observations correspondingly. AAR first distributes a packet copy to each active sub-area of the target vehicle using a traffic-considered shortest path spreading algorithm, and then in each sub-area, each packet carrier tries to forward the packet to a vehicle that has high encounter frequency with the target vehicle. Furthermore, we propose a Distributed AAR (DAAR) to improve the performance of AAR. Extensive trace-driven simulation demonstrates that AAR produces higher success rates and shorter delay in comparison with the state-of-the-art routing algorithms in VDTNs. Also, DAAR has a higher success rate and a lower average delay compared with AAR since information of dynamic active sub-areas tends to be updated from time to time, while the information of static active sub-areas may be outdated due to the change of vehicles' behaviors.
Finally, we try to combine different routing algorithms together and propose a DIstributed Adaptive-Learning routing method for VDTNs, namely DIAL, by taking advantages of the human beings communication feature that most interactions are generated by pairs of people who interacted often previously. DIAL consists of two components: the information fusion based routing method and the adaptive-learning framework. The information fusion based routing method enables DIAL to improve the routing performance by sharing and fusing multiple information without centralized infrastructures. Furthermore, based on the information shared by information fusion based routing method, the adaptive-learning framework enables DIAL to design personalized routing strategies for different vehicle pairs without centralized infrastructures. Therefore, DIAL can not only share and fuse multiple information of each vehicle without centralized infrastructures, but also design each vehicle pair with personalized routing strategy. Extensive trace-driven simulation demonstrates that DIAL has better routing success rate, shorter average delays and the load balance function in comparison with state-of-the-art routing methods which need the help of centralized infrastructures in VDTNs.
Recommended Citation
Wu, Bo, "Complex Network Analysis and the Applications in Vehicle Delay-Tolerant Networks" (2016). All Dissertations. 2312.
https://open.clemson.edu/all_dissertations/2312