Exploiting Friendship Relations for Efficient Routing in Mobile Social Networks

    51 Votes

Delay Tolerant Networks (DTN) are a class of wireless networks. These networks are usually sparse and the connection between their nodes changes frequently. Real life examples of DTNs, mobile social networks (MSN).Due to the challenging network environment in these networks, efficient routing of messages is not an easy task. The relationship defining the frequency and duration of the connectivity between nodes has to be analyzed to route messages efficiently. Exploiting friendship based social network features of an MSN, we present a new routing algorithm: Friendship Based Routing. To analyze social relations between nodes (i.e. people), we need to define their friendships in terms of their behaviours.

Friendship Based Routing

To analyze social relations between nodes (i.e. people), we need to define their friendships in terms of their behaviours. A new metric measuring different aspects of friendship behaviour from the encounter history of nodes need to be introduced. Utilizing this metric, we find both the direct and indirect close friends of each node. We present Friendship Based Routing in which periodically differentiated friendship relations are used in forwarding of messages.

Proposed Algorithm

Analysis of Node Relations

The intermittent connectivity between nodes in an MSN makes the routing of messages possible only in opportunistic manner. Message exchanges occur only when two nodes come within the range of each other and one of them assesses that the other has higher delivery chance than itself. The link quality between each pair of nodes needs to be estimated accurately  to consider the possible forwarding opportunity arising from the encounter. Six different encounter histories between nodes i and j in the time interval [0, T]. 

Analysis Node Relations

All these metrics have some deficiencies in accurate representation of forwarding opportunity arising from encounters between nodes. To find a link metric that reflects the node relations more accurately,considered the following three behavioural features of close friendships: high frequency, longevity, and regularity. Frequency refers to average inter meeting time while regularity refers to the variance of the inter meeting time. New metric called social pressure metric (SPM) is a measure of a social pressure that motivates friends to meet to share their experiences. The average message forwarding delay to node j if node i had a new message destined to node j at each time unit when the time unit tends to zero. The link quality (wi,j ) between each pair as the inverse of this value. F(t) represents the time remaining to the next encounter of the two nodes at time t.

Friendship Community Formation

Using its encounter history, each node can compute qualities (wi,j values) of its links with other nodes. Friendship community is a set of nodes having a link quality with itself larger than a threshold(t).This set will include only direct friends. Relations between nodes may show periodic changes. Both strong indirect relationships and periodic variations of relationships must be addressed when forming friendship communities. To find indirect friendships between nodes in a way relevant for routing, we propose to use relative SPM (RSPM) metric.

Handling Indirect Relationships

Encounter history between nodes i and j (upper diagram) and between nodes j and k (lower diagram) in the same time interval [0, T].Duration of this stages are  ta,x  and tb,x. x denotes the number of indirect information passing occurring.There are three full information passing sessions between nodes i and k via node j, and the beginning of the fourth one. Since the intermediate node, j, records all of its past contact times with i and k, it can compute the value of RSPM. 

Handling Periodic Variation in Node Relations

Node relations in an MSN often change with time periodically. Such periodic changes must be addressed for accurate computation of link qualities between nodes. To reflect the periodic variation of the strength of friendship, we propose to use periodic friendship communities in our protocol. Each node i computes its Fi for different periods of the day and has different friendship communities in different periods.

Forwarding Algorithm

After a node constructs its friendship community for each period based on its current encounter history, it decides whether to forward a message to the encountered node. Node I having a message for node d meets with node J, it forwards the message to J if and only if node J’s friendship community in the current period pid includes node D and node J is a stronger friend of node d than node I is. if node J has a stronger link with node d than node I has, if node J does not include d in its current friendship community (i.e. weight of link between J and d is less than), node I will not forward the message to node J.


First, we introduce a new metric to detect friendship based node relations accurately. We also treat indirect relations between nodes novel way making them amenable to routing.we present a new routing algorithm in which a node forwards its messages to those nodes that contain the destination node in their friendship communities.We evaluate the proposed algorithm through simulations using two real DTN traces and a synthetic data.The results show that our algorithm performs better than three benchmark algorithms proposed previously.

Download this file (Exploiting Friendship Relations for Efficient Routing.ppt)Exploiting Friendship Relations for Efficient Routing.ppt[PPT Presentation]633 Kb