Intra and Inter Community Routing in Mobile Social Networks

Intra and Inter Community Routing in Mobile Social Networks

ABSTRACT: Mobile social networks (MSNs) is providing a rapidly deployable and self configuring networking in many applications, which is Delay tolerant network(DTN) which has a large number of mobile nodes with few social characteristics. DTNs lack continuous network connectivity but challenges lesser delay. In recent years social based approaches are matching better routing design and decision which is improving the routing performance and is building positive social characteristics like community ,centrality etc. There are many social aware algorithm proposed to address routing problems which cannot achieve efficient optimal performance. In this paper we proposed an opportunistic routing algorithm for community and computes the minimum expected delivery delay of nodes using reverse dijikstras algorithm to achieve higher performance which in turn reduces the computational and maintenance cost.

1. INTRODUCTION

   Mobile social networks (MSNs) are a special kind of delay tolerant network (DTN), in which mobile users move around and communicate with each other via their carried short-distance wireless communication devices. Typical MSNs include pocket switch networks, mobile vehicular networks, mobile sensor networks. As more users exploit portable short-distance wireless communication devices (such as smart phones, i-Pads, mobile PCs, and sensors in vehicles) to contact and share data between each other in a cheap way, MSNs attract more attention. Since MSNs experience intermittent connectivity incurred by the mobility of users, routing is a mainly concerning and challenging problem.

   Recently, some social-aware routing algorithms that are based on social network analysis have been pro- posed, such as Bubble Rap, SimBet , etc. Two key concepts in social network analysis are: (i) community, which is a group of people with social relations; (ii) centrality, which indicates the social relations between a node and other nodes in a community. Based on the two concepts, these algorithms detect the communities and compute the centrality value for each node. Messages are delivered via the nodes with good centralities. Since social relations of mobile users generally have long term characteristics and are less volatile than node mobility, social-aware algorithms outperform traditional DTN algorithms, such as flooding- based algorithms and probability-based algorithms. Despite this, these algorithms tend to forward messages to the nodes with locally best centralities.

   In this system Mobile social networks (MSNs) have number of community home (home nodes). All home nodes have radio frequency the nodes falls in its radio range

   are belong to the home community. Sometime radio range will overlap, the nodes in this overlap region are called centrality node in this system.

   If you have to pass message from one node to another node than that communication happen through community home.

   Two types of communication:

   Inter-Community Centrality The communication will happen through centrality node. If more than one centrality node present by using CAOR algorithm we will select centrality node.

   Intra-Community Betweenness – The communication will happen through community home.

   In this paper, we focus on the single-copy routing problem in MSNs. In many real MSNs, mobile users that have a common interest generally will visit some (real or virtual) location that is related to this interest. For instance in Fig. 1, students with a common study interest will visit the same classrooms to take part in the same courses; customers with the same shopping interests often visit the same shops; friends generally share some resources through Facebook, and so on.

   Fig.1.1 An example of mobile social network

   Based on this basic social characteristic, we propose a home-aware community model. Mobile users with the common interest autonomously form a community, in which the frequently visited location is their common home. Moreover, like, we assume that each home supports a real or virtual throwbox, a local device that can temporarily store and transmit messages. Under the home- aware community model, we propose a distributed optimal Community-Aware Opportunistic Routing algorithm (CAOR). We first turn the routing between lots of nodes to the routing between a few community homes. Then, we adopt the optimal opportunistic routing scheme by maintaining an optimal relay set for each home. Each home only forwards its message to the node in its optimal relay set

   and ignores other relays. Since this scheme solves the problem of whether a home should select a visited node as the relay of message delivery or ignore this visited node to wait for those better relays, it can achieve the optimal performance. More specifically, our major contributions are summarized as follows:

   • We present a home-aware community model and extend the centrality concept from a single node to a group of nodes. Unlike existing community models, each community home in our model is assumed to have a throwbox to store and transmit messages.

   • We present a rule of optimal opportunistic routing through a theoretical analysis. We design a reverse Dijkstra algorithm to determine the optimal relays and compute the minimum expected delivery delay. Based on this, the CAOR algorithm can achieve the optimal opportunistic routing performance.

   • We turn the routing in |V | mobile nodes into a routing in |L| (|L||V |) community homes by virtue of the home-aware community model. Moreover, we prove that the simplification will not sacrifice the routing performance. As a result, the network scale and the maintaining costs are reduced significantly.

   • We first design the CAOR algorithm for the case that each home has a real throwbox. Then, we extend it to the case of virtual throwbox by letting the members of a community with high centralities to act as the home of this community.

2. RELATED WORK

   So far, many traditional DTN routing algorithms have been proposed. These algorithms include flooding- based algorithms (e.g., [1]) and probability-based algorithms (e.g., [2]). Among these algorithms, the MH algorithm [3] adopts the optimal opportunistic routing strategy ,based on global contact information. Compared with this algorithm, the CAOR algorithm adopts the home aware community model and turns the routing problem among mobile nodes into the routing problem among static communities, and therefore, achieves the optimal routing performance only based on community contact information. The maintenance cost of the contact information is far less than the MH algorithm. This is important because it means that the mobility behaviors of most nodes would not affect the

   routing performance of the whole network. Moreover ,since the network is simplified to be a static network ,many previous routing algorithms in static networks, such as wireless sensor networks, can be applied. Social-aware algorithms assume that each node has some social characteristics (such as community ,centrality, and similarity, etc.)and then exploits the knowledge to direct the routing decision, so as to improve the delivery ratio. The SimBet [5] algorithm exploits the ego network technique to locally compute the approximate centrality and similarity for each node. It then uses these characteristics to find

   bridge nodes for the message delivery. The Bubblerap [4] algorithm uses the k-clique algorithm to detect a community, ranks each node by calculating their centrality values, and then exploits the rank values of nodes to direct the routing decision. Besides, the algorithm in [6], a multicasting MSN algorithm, also uses the k-clique technique to detect the communities, and defines the cumulative contact probability of each node as its centrality, based on which, it finds the relay for message delivery. The Social-Greedy [7] algorithm calculates the social closeness for each node based on its social profile, and then greedily delivers the destinations. Compared with the CAOR algorithm, these algorithms just exploit the social characteristics of nodes to improve the probability of meeting the destination for each message. However, this is still unpredictable, and thus cannot achieve the optimal result.

   The CAOR algorithm is based on the home-aware community model. There are two features: one is that nodes are assumed to frequently meet at some homes and the cases that they occasionally encounter at other places are ignored; another is that the interval for each nodes visit to homes follows the exponential distribution. In fact, most of the mobility research has captured the characteristics of skewed location visiting preferences and the periodic re-appearance of nodes at the same location from numerous realtrace analyses. Moreover, they also point out that the inter- meeting time of nodes in the real traces follows the power law distribution. However, Cai etal. [8] has proven that when the area is bounded, the distribution is the exponential distribution; otherwise ,if there is no bound, the distribution becomes power law. Therefore, for simplicity, the exponential distribution is still widely adopted, as seen in [6].Compared with these mobility models, our model does not remove the homes. Instead, we utilize these homes to relay messages.

   In addition, a lot of research also uses some auxiliary nodes to relay messages: research in [10] exploits throwboxes to relay messages, and research in [9] uses mobile message ferries to relay transfer messages, etc. Compared with our work, messageferries are mobile message relays, unlike our static community homes. The throwbox is just like our community home; however, their works mainly focus on the capacity and delivery delay of the Epidemic algorithm when adding throwboxes into the DTNs. To the best of our knowledge, this is the first work to use home-aware communities to find the optimal opportunistic routing among mobile nodes.

3. SOCIAL PROPERTIES AND METRICS Some social properties related to DTNs routing.

   1. Social Graph and Contact Graph

      The most popular way, to study the social relations among people and extract their social properties, is building a socialgraph (also called social network). A social graph is a global mapping of everybody and how they are related. Such a graph is an abstract graph where vertices represent individual people and edges describe social ties between individual people. Social ties can be expressed in many

      forms. For example, different types of social ties may describe different social relationships among people such as friends, family members, and co-workers. Social graphs have been widely used in many applications, such as analysis of online social networks or terrorist networks . With a social graph, a variety of social metrics (e.g., communality, centrality, and similarity) can be easily calculated or estimated, and these metrics can be then used by social-based approaches. Therefore, it is crucial to obtain social graphs for social-based approaches. A social graph is an intuitive source for many social metrics such as community and friendship. Unfortunately it is not always available (due to either privacy or security reasons) or hard to be obtained via disclosed social data. However, with new networking technology, we can study relationships among people by observing their interactions and interests over wireless networks. Building a contact graph is a common way to study the interactions among people in a network and thus analyze their relationships and estimate the social metrics among them. In DTNs, each possible packet forwarding happens when two mobile nodes are in contact (i.e., within transmission range of each other). By recording contacts seen in the past, a contact graph can be generated where each vertex denotes a mobile node (device or person who carries the device) and each edge represents one or more past meetings between two nodes. An edge in this contact graph conveys the information that two nodes encountered each other in the past. Thus the existence of an edge intends to have predictive capacity for future contacts. A contact graph can be constructed separately for each single time slot in the past, or it can be constructed to record the encounters in a specific period of time by assigning a set of parameters to each edge to record the time, the frequency and the duration of these encounters. From the observation that people with close relationships such as friends, family members, etc. tend to meet more often, more regular and with longer duration, we can extract DTN nodes relationships from the recorded contact graph, estimate their social metrics, and use such information to choose relays with higher probabilities of successful forwarding. How to detect peoples relationships and create the relative social graph from the recorded contact graph may affect estimation accuracy and the efficiency of social-based approaches. Most of the current social-based DTN routing algorithms

      [13] directly treat the aggregated contact graph (merging the contact graphs of several time slots into one graph) as the social graph of all entities in the network, and uses this graph to generate social metrics for forwarding selection. This strategy is based on the observation that although the contact graph reflects the encounter history while the social graph reflects the social relations among people, the aggregated contact graph (the sum of contact graph over time) and the social graph are statistically similar. However, Hossmann et al. [11] showed that the performance of these algorithms heavily depends on the way the graph is constructed out of observed contacts (i.e., contact aggregation) and proposed a method to select an appropriate aggregation period for contact aggregation. After building the aggregated contact graph, different social metrics can be obtained. For example, Hui, et al. [12] proposed serval

      community detection pproaches (simple, k-clique, modularity, etc.) with great potential to detect both static and temporal communities. Bulut et al. [14] introduced a method of detecting the quality of friendship by calculating the social pressure metric (SPM) from contact graphs.

   2. Building Home-Aware Communities

      In this paper, we propose a concept of home-aware community. A home-aware community is a community of nodes that frequently visit a given home. The frequently visited home is the common home of the community members, i.e., the community home. Moreover, if a node visits several homes frequently, it can belong to multiple communities and have multiple homes. Each community exactly contains a group of nodes that have the common interest to the community home.

   3. Centrality Metric

      In an MSN, the centrality metric is generally used to measure the importance of nodes during message delivery. A node with a better centrality value means that it has a stronger capability of connecting with other nodes. Previous works mainly adopt three centrality measures: degree centrality, closeness centrality, and betweenness centrality [5] Degree centrality is measured as the number of direct links between a given node and other nodes. Closeness centrality is a measure of how long it will take to deliver a message from a given node to other nodes. Betweenness centrality measures the extent to which a node lies on the paths linking other nodes. In this paper, we model the whole network into some overlapped star- topology communities. The message delivery thus can be turned into the delivery within and/or between these communities. Accordingly, we only present an intra- community centrality metric and an inter-community betweenness metric for nodes ,to measure their importance in the message delivery within and between these communities, respectively.

      • Intra-Community Centrality

        In intra-community routing, the most concern is measuring the capability of each community member to meet and deliver messages to other members .Since intra- community message deliveries happen only when nodes visit community homes, the smaller the expected delay to visit a community home, the higher capability to deliver messages a community member would have. In fact, the expected delay for a node v to visit a community home l, denoted by Dv,l, can be simply derived from the parameter =_v,l. That is, Dv,l = 1/v.l .Therefore, we can directly use this value to measure the intra-community centrality of the node to the community.

      • Inter-Community Betweenness

        In this paper, we adopt the opportunistic routing scheme, in which multiple nodes cooperatively deliver messages. It can be defined as follows.

        Opportunistic Routing: each message sender (home or node) has a relay set (homes nodes). Once a relay in the set meets

        the message sender, the sender will let this relay deliver messages. In other words, the first relay in the set to meet the

        message sender will act as the real relay. This dynamical routing scheme is more general than the routing based on a single fixed relay. Based on this scheme, we extend the concept of betweenness from a single node to a node set. Concretely, we define the inter-community betweenness to measure the ability of a node set to be taken as a communication bridge between communities. Moreover, we use the delivery delay to evaluate the inter-community betweenness of a set of nodes.

        Inter-Community Betweenness: Bl,l (S)is the expected delivery delay that it takes for a relay set S (S ClCl ) to cooperatively deliver messages from community home l to l. The smaller the Bl,l (S), the better the delivery ability of S will be. According to the opportunistic routing scheme, anode in the relay set acts as the real relay only when it is the first node in the set to meet the message sender. There must be a relay set that has the smallest betweennes. Thus this set is the optimal betweenness set.

        Optimal Betweenness Set: ~ Sl;l is the relay set with the smallest betweenness for the message delivery from community home l to l.

4. SYSTEM ARCHITECTURE

   Fig 4.1 System Architecture

   A system architecture or systems architecture is the conceptual model that defines the structure, behavior, and more views of a system. An architecture description is a formal description and representation of a system, organized in a way that supports reasoning about the structures of the system .A system architecture can comprise system components, the externally visible properties of those components, the relationships (e.g. the behavior) between them. It can provide a plan from which products can be procured, and systems developed, that will work together to implement the overall system. There have been efforts to formalize languages to describe

   system architecture, collectively these are called architecture description languages.

   A complete subsystem can be broken down into smaller subsystems like community which is formed when the mobile users of same interest visit particular site, home node is the frequently visited location. Moreover, like we assume that each home supports a real or virtual throw box a local device that can temporarily store and transmit messages. Centrality,which indicates the social relations between a node and other nodes in a community. A system interacts with the other system like when a node has to send a message for the other node initially it will create a message with the source and the destination address then will be sent for the home node which searches locally, the communication will happen through community home and is called as Intra- community betweeness. If destination node is not present locally then, the communication will happen through centrality node which send all the routes for the home node, then it will choose the best path and send it

   for the source node which finally sends for the destination node with the less delay which is called as Inter- Community Centrality .If more than one centrality node present by using CAOR algorithm we will select centrality node.

5. IMPLEMENTATION

   This includes the initialization phase and the routing phase. The first phase simplifies the network (Algorithm 1), and the second phase computes the routing decision (Algorithm 2).

   • Initialization Phase:

     Algorithm 1: CAOR: initialization For each community home lL do 1: Collect delay characterstics

     2: Use Optimal betweeness technique to produce relay sets 3: Create the virtual link

     4: Receive the link weights from other home 5.Construct the contact graph

     Each community home first collects the parameters of its community members in Step 1. Then, the home determines the optimal betweenness sets for the message deliveries from itself to other community homes in Step 2. In Step 3, the home produces the virtual links for these deliveries and sends the corresponding weights to other community homes. Next, the home receives the link weights of other pairwise community homes to locally construct the contact graph of homes in Steps 4 and 5. Note that the algorithm is a distributed one. The computational overhead is dominated by the cost of determining the optimal betweenness sets in Step 2.

   • Routing Phase

   Algorithm 2 Compute minimum expected delay

   Require: G+ = L+;W+, i, l0=d

   Ensure: Di,d

   1: Set S=Ø;

   2: Let D l0, l0 =0, S l0, and L+=L+ l0; 3: for each l L+ do

   4: Compute Dl,l0 (S) ;

   5: Select the smallest one, and let Dl,l0 = Dl,l0 (S); 6: if l is i then

   7: Break;

   8: else

   9: S l, and L+=L+l; 10: return Di,d=Dl,l0 ;

   Algorithm 3: CAOR: routing

   For each node vV do

   1: if v visits a community home lL then

   2: for each message of v and l, v do

   3: Extract destination (d) information;

   4: Get G+ by adding v and d to G in home l; 5: Compute Dv,d and Dl,d ;

   6: if Dv,d <Dl,d then

   7: Let v hold the message; 8: else

   9: Let l hold the message;

   The routing phase extends the graph, uses the reverse Dijkstra algorithm to compute the minimum expected delays for each home in the extended graph, and then makes the routing decision. The reverse Dijkstra algorithm is shown in Algorithm 2. Steps 1 and 2 are the initialization. In each round, i.e., Steps 4-9, the minimum expected delivery delay of a home is determined. The computational overhead is O(|L|2). The routing decision of CAOR is shown in Algorithm 3. When a node v visits a community home l, it first construct the extended contact graph of homes G+ in Step 4 by adding v and d into the graph G, which is generated by home l in the initialization phase. Then, node v uses Algorithm 2 to compute the minimum expected delivery delays Dv,d and Dl,d in Step 5. The routing decision is made in Steps 6- 9. The computational overhead of this algorithm is dominated by the execution of Algorithm 2 in Step 5. Moreover, the rule of optimal opportunistic routing ensures that this algorithm can achieve the minimum expected delay for each message delivery.

6. CONCLUSION AD FUTURE WORKS

In this paper, we have modeled an MSN into overlapping home-aware communities by simplifying the routing problem among many mobile nodes into static communities, and this Community Aware algorithm achieves optimal opportunistic routing within and between the communities using the centrality and betweeness as social characteristics. Optimal opportunistic routing only depends on a few nodes in the network. A change in behavior of most nodes would not affect the routing performance. We can thus achieve the optimal routing performance at a very low maintenance cost. Compared with previous social-aware algorithms, the optimal and predictable routing performance is the biggest advantage of this algorithm. It also predicts the best centrality node if

there exists more than one centrality node. The drawback of the algorithm is predicted to be that, it takes more time to find out optimal relay set which may decrease the efficiency by increasing the delay in the system and few related security features may be added.

REFERENCES

1. A. Vahdate and D. Becker, Epidemic routing for partially-connected ad hoc networks, Duke University, Tech. Rep. CS-2000-06, June 2000.

2. A. Lindgren, A. Doria, and O. Schelen, Probabilistic

   routing in intermittently connected networks, Lecture Notes in Computer Science, vol. 3126, no. 1, pp. 239254, 2004.

3. V. Conan, J. Leguay, and T. Friedman, Fixed point opportunistic routing in delay tolerant networks, IEEE Journal on Selected Areas in Communications, vol. 26, no. 5, pp. 773782, 2008.

4. P. Hui, J. Crowcroft, and E. Yoneki, Bubble rap: social-based forwarding in delay tolerant networks, in ACM MobiHoc, 2008.

5. E. Daly and M. Haahr, Social network analysis for routing in disconnected delay-tolerant manets, in ACM MobiHoc, 2007.

6. W. Gao, Q. Li, B. Zhao, and G. Cao, Multicasting in delay tolerant networks: A social network perspective, in ACM MobiHoc, 2009.

7. K. Jahanbakhsh, G. C. Shoja, and V. King, ocialgreedy:A socially- based greedy routing algorithm for delay tolerant networks, in MobiOpp, 2010.

8. H. Cai and D. Y. Eun, Crossing over the bounded domain: From exponential to powerlaw inter-meeting time in manet, in ACM Mobi- Com, 2007.

9. M. M. B. Tariq, M. Ammar, and E. Zegura, Message ferry route design for sparse ad hoc networks with mobile nodes, in ACM MobiHoc, 2006.

10. M. Ibrahim, P. Nain, and I. Carreras, Analysis of relay protocols for throwbox-equipped dtns, in WiOPT, 2009.

11. T. Hossmann, F. Legendre, and T. Spyropoulos, From contacts to graphs: pitfalls in using complex network analysis for DTN routing, in INFOCOM09: Proc. 28th IEEE International conference on Computer Communications Workshops, pp. 260265, 2009.

12. P. Hui, E. Yoneki, S.Y. Chan, and J. Crowcroft, Distributed community detection in delay tolerant networks, in Proc. ACM SIGCOMM Workshop, MobiArch07, 2007.

13. P. Hui, A. Chaintreau, J. Scott, R. Gass, J. Crowcroft, and C. Diot, Pocket switched networks and the consequences of human mobility in conference environments, in WDTN 05: Proc. 2005 ACM SIGCOMM workshop on Delay-tolerant networking, 2005.

14. E. Bulut and B. K. Szymanski, Friendship based routing in delay tolerant mobile social networks, in Proc. IEEE Global Telecommunications Conference (GLOBECOM),, Dec, 2010.

15. T. Spyropoulos, K. Psounis, and C. Raghavendra, Spray and wait: An efficient routing scheme for intermittently connected mobile networks, in ACM SIGCOMM Workshop on Delay-Tolerant Networking (WDTN), 2005.

16. J. Burgess, B. Gallagher, D. Jensen, and B. N. Levine, Maxprop: routing for vehicle-based disruption-tolerant networks, in IEEE INFOCOM, 2006.

17. S. Jain, K. Fall, and R. Patra, Routing in a delay tolerant network, in ACM SIGCOMM, 2004.

18. T. Henderson, D. Kotz, and I. Abyzov, The changing usage of a mature campus-wide wireless network, in ACM MobiCom, 2004.