Analysis of a Hypercube-based Social Feature Multi-Path Routing in Delay Tolerant Networks

Social behavior plays a more and more important role in delay tolerant networks (DTNs). In this paper, we present an analytical model for a hypercube-based social feature multi-path routing protocol in DTNs. In this routing protocol, we use the internal social features of each node (individual) in the network for routing guidance. This approach is motivated from several real social contact networks, which show that people contact each other more when they have more social features in common. This routing scheme converts a routing problem in a highly mobile and unstructured contact space (M-space) to a static and structured feature space (F-space). The multi-path routing process is a hypercube-based feature matching process where the social feature differences are resolved step-by-step. A feature matching shortcut algorithm for fast searching is presented where more than one feature difference is resolved at one time. The multiple paths for the routing process are node-disjoint. We formally analyze the delivery rate and latency by using hypercube-based routing. The solutions for the expected values of latency and delivery rate are given under different path conditions: single-/multi-path and feature difference resolutions with/without shortcuts. Extensive simulations on both real and synthetic traces are conducted in comparison to several existing state-of-the-art DTN routing protocols.