  Social Delay Tolerant Networks (SDTNs) are a special kind of Delay Tolerant
Network (DTN) that consists of a number of mobile devices with social
characteristics. The current research achievements on routing algorithms tend
to separately evaluate the available profit for each prospective relay node and
cannot achieve the global optimal performance in an overall perspective. In
this paper, we propose a Movement Pattern-Aware optimal Routing (MPAR) for
SDTNs, by choosing the optimal relay node(s) set for each message, which
eventually based on running a search algorithm on a hyper-cube solution space.
Concretely, the movement pattern of a group of node(s) can be extracted from
the movement records of nodes. Then the set of commonly visited locations for
the relay node(s) set and the destination node is obtained, by which we can
further evaluate the co-delivery probability of the relay node(s) set. Both
local search scheme and tabu-search scheme are utilized in finding the optimal
set, and the tabu-search based routing Tabu-MPAR is proved able to guide the
relay node(s) set in evolving to the optimal one. We demonstrate how the MPAR
algorithm significantly outperforms the previous ones through extensive
simulations, based on the synthetic SDTN mobility model.
