Community-Home in Mobile Social Network

Community-Home in Mobile Social Network

Neha Phalswal

Department of CSE AMC Engineering College

Bangalore, INDIA

Mrs. Shalini.S

Department of CSE AMC Engineering College

Bangalore, INDIA

AbstractA mobile social network (MSN) is a special kind of delay tolerant network (DTN). The MSNs are composed of mobile nodes that move around and offer data with one other through short-distance wireless communication devices. Mobile nodes in MSNs by and large visit a few areas habitually, while going to different areas less every now and again. The community homes have higher need to spread messages into the system. We propose a novel zero-knowledge multi-copy routing algorithm, homing spread (HS), for homogeneous MSNs. In homogeneous MSNs all mobile nodes share all community homes. We also extend HS to the heterogeneous MSNs. Mobile nodes having different community homes known as heterogeneous MSNs. We calculate the expected delivery delay of HS. In addition, far reaching recreations are directed. Results demonstrate that group homes are vital considers message spreading. Utilizing homes to spread messages quicker and HS attains to a superior execution than existing calculations, for example, zero-information MSN routing algorithms, including Epidemic and Spray&Wait.

Index Terms Mobile social networks, community homes, homing spread, routing.

1. INTRODUCTION

   Mobile social networks (MSNs) are composed of mobile users that move around and use their carried wireless communication devices to impart data by means of online informal community administrations. MSNs can be seen as an extraordinary sort of postponement tolerant system (DTN). Like different DTNs, because of the versatility of hubs, there are for the most part no stable end-to-end conveyance ways in a MSN. Therefore, delivering messages is a challenging issue.

   The existing algorithms are divided into two categories. One category is knowledge-based routing algorithms, which mainly includes probability-based algorithms and social- aware algorithms. The nodes in these algorithms are assumed to have known some contact probabilities between nodes or some social characteristics of nodes, and then they use this knowledge to guide their message deliveries. However, it is difficult for each node to get to know the contact probabilities or social characteristics of other nodes in real MSNs. Another category consists of zero-knowledge routing algorithms, which do not require any prior knowledge on the contact probabilities or social characteristics of nodes. The typical algorithms include Epidemic and Spray&Wait. Epidemic spreads messages to each encountered node through the flooding strategy. To avoid producing too many message copies, Epidemic in the real implementation generally limits the maximum number of copies. While flooding strategy has

   a high probability of delivery, they waste a lot of energy and suffer from severe contention which can significantly degrade their performance. Spray&Wait also limits the number of copies. Moreover, it adopts a binary splitting method to spread copies into the network until one message holder encounters the destination. Both of the algorithms assume that all nodes just randomly walk in a given area, and that nodes visit all locations in a uniformly random way. However, real MSNs generally do not follow this assumption, making them less efficient.

   MSNs have social characteristics, where nodes in an MSN generally visit some locations frequently, while visiting other locations less frequently, due to their different interests. The nodes that frequently visit the same location will form a community with a common interest, as shown in Fig. 1. The location is seen as the home of the community.

   Fig.1. An example of MSN: mobile users move around to form three communities. Each community has its home or a mobile user that visits its home most frequently.

   Moreover, each community home (or simply, home) in real traces can support a real throwbox, a device that can locally store and forward messages, or can let the nodes that visit it most frequently act as virtual throwboxes.

   A zero-knowledge multi-copy MSN routing algorithm is proposed, homing spread (HS). The objective is to minimize the expected delay of delivering each message from its source to its destination, while the copies of each message are no more than a given threshold. Thus, it can achieve a better performance than existing zero-knowledge routing algorithms.

2. NETWORK MODEL & PROBLEM

   In this section, we introduce the network model, followed by the problem.

   1. Network Model

      Consider a typical MSN that is composed of a number of

      mobile nodes and many locations. Each node frequently visits a few locations, called community homes or homes, while the other locations, called normal locations, are visited less frequently. Each node might have multiple homes. Assume that each home has a throwbox that can locally store and forward messages. Even though there are no real throwboxes in some homes, we can let the nodes that most frequently visit these homes act as the virtual throwboxes.

      Virtual throwboxes will only result in a little bit of performance degradation, compared to real throwboxes.

      Fig.2. The network model

   2. Problem

   There are two type MSN settings: the homogeneous setting and the heterogeneous setting. They are defined as follows:

   Definition 1: The homogeneous setting refers to that all nodes in the MSN share all of the h homes. That is to say, Hi = H for each i V .

   Definition 2: The heterogeneous setting means that each node i might have a different home set Hi, each home in which is randomly selected from H. That is, Hi H. Other homes outside of Hi are seen as normal locations for node i.

   Under both the homogeneous and the heterogeneous setting, the zero-knowledge multi-copy routing problem is studied. Here, zero-knowledge routing means that each node in the MSN is unaware of other nodes. That is to say, each node in the MSN does not know the home sets of other nodes. Objective is to minimize the delivery delay for a given number of message copies C (1 < C < n/2). A visit to a home is known as homing, but when a message holder meets

   another node at a normal location, it is known as roaming.

   Challenges are as follows: What is the optimal way for a message holder to spread copies during homing and roaming? Once a home receives some message copies, how should it further spread these copies? What is a general way for a mobile destination to obtain a copy?

3. HOMING SPREAD (HS)

   To solve the above problem, first propose the zero- knowledge multi-copy routing algorithm, homing spread (HS), for the homogeneous setting. Then, extend HS to the heterogeneous setting. Since each node has a relatively high probability of visiting homes, the basic idea of HS is to let the homes have a higher priority to get the copies, so as to maximize the probability that the destination meets a message holder. More specifically, HS consists of three phases: homing, spreading, and fetching, as shown in Fig. 3.

   Homing phase

   Spreading phase

   Fetching phase

   Homing phase

   Spreading phase

   Fetching phase

   Fig.3. The framework of Homing Spread

   In the homing phase, the source sends copies quickly to homes. Upon reaching the first home, the message holder (which includes the source) dumps all copies into the throwbox of the home. When roaming occurs, copies are split between the two nodes and both become message holder.

   In the spreading phase, the homes with multiple copies spread these copies to other homes and mobile nodes. These homes first spread their copies to each node that visits them by splitting the copies between themselves and those visiting nodes. Then, each node that receives copies spreads these copies to other homes and mobile nodes. In the splitting of copies between the homes and the visiting nodes, each home always keeps at least one copy through its throwbox.

   In the fetching phase, the destination fetches the message when it meets any message holder for the first time, which can be either a home or a mobile node.

   The three phases might not follow a strict order. There might be overlaps among them in probability.

4. HS: HOMOGENEOUS MSNS

   Focus is on one message delivery only, but the results can be applied to multiple messages as long as each node, including home, has sufficient cache space. The inter-meeting time between any two nodes and between a node and a home follows independent and identical exponential distributions, HS is optimal in terms of minimizing the expected delivery delay in homogeneous MSNs.

   1. The Homing Phase

      In the homing phase, the source tries to send the message to the homes first. If the source encounters other nodes before it reaches a home, it will give some of its copies to the encountered node, and will let the node jointly send the copies to homes. The more nodes that the message copies are sent to before reaching homes, the smaller the delay of the next two phases will be. Thus, the source needs to spread the copies to as many other nodes as possible before they reach the homes.

      Definition 3: (Binary Homing Scheme): Each message holder sends all of its copies to the first (visited) home. If the message holder encounters another node before it visits a home, it binary splits the copies between them.

   2. The Spreading Phase

      In the spreading phase, the homes which have more than one copy spread their extra copies to other homes and nodes. H, H and H_ (H = H + H+ H_) denote the homes with more than one copy, the homes with only one copy, and the homes without copies, respectively.

      Definition 4: (1-Spreading Scheme): Each home li H spreads a copy to each node in the same home until only one copy remains, so that li H_ after the spreading. If such a node with one copy later visits another home lj H, the node

      sends the copy to that home, so that lj H after the visit.

   3. The Fetching Phase

      In the fetching phase, the destination just fetches the message once it encounters a message holder.

      C/2 C/2

      C/4 C/4 C/4 C/4

      C/8 C/8 C/8 C/8

      Fig.4. The binary homing scheme

   4. The HS Algorithm

      Algorithm 1 is a distributed algorithm, in which each node only needs to exchange the copies with the encountered node or home. Note it do not distinguish the three phases when nodes exchange the copies. This is because the message exchange in this algorithm is compatible with each phase.

      Algorithm 1: The Homing Spread (HS)

      send its copies to a home. Thus, when two nodes that have copies meet, the node with more homes should hold more copies, so as to minimize the average delay for these copies to be delivered to the homes. The objective is, each pair of encountered nodes should equally split their copies.

      Algorithm 2: The Extended Homing Spread

      1. for each mobile node i do

      2. if node i encounters another node j then

      3. if node j is the destination then

      4. node i sends the message to j;

      5. if nodes i and j have ci and cj message copies

         then

      6. node i holds (1 ij)ci+jicj copies through exchange with node j;

      7. if node i visits a home l then

      8. node i sends all its copies to l;

      9. if l H or i is the destination then

      10. l sends a copy to node i.

   Definition 5: (Proportional Homing Scheme): Each node with message copies sends its copies to the first (visited) home. If a node i that has c copies encounters another node j before it visits a home, node i will split these copies between them by sending out |ijc| copies and holding the remaining copies by

   | H |

   i

   i

   itself, where

   i .

   1. for each mobile node i do

      ij | H

      | | H j |

   2. if node i encounters another node j then

   3. if node j is the destination then

   4. node i sends the message to j;

   5. if nodes i and j have ci and cj message copies

      then

   6. node i holds [ci/2]+[cj/2] copies through exchange with node j;

   7. if node i visits a home l then

   8. node i sends all its copies to l;

   9. if l H or i is the destination then

   10. l sends a copy to node i.

5. HS: HETEROGENEOUS MSNS

   Extend the HS algorithm from the homogeneous setting to the heterogeneous setting, where each node might have a different home set, but all of them will form the overlapped home set H. Using a zero-knowledge routing algorithm. Without loss of generality, the source treats every home as a potential home of destination. Then, the objective is still to spread the message copies to each home.

   A. The Extended HS

   Consider the homing phase. Since the nodes in the heterogeneous setting have different home sets, the expected delays for them to visit a home will be different. In general, the more homes a node has, the more quickly the node will

   In the proportional homing scheme, is a ratio of copy- splitting between encountered nodes. The message copies be split in proportion to the numbers of homes of encountered nodes, since the number of homes of a node represents the message-spreading capability of this node. Fig. 6 shows an example of the proportional homing scheme. Message copies are proportionally split until they reach the homes. When = 0.5, the proportional homing scheme becomes the binary homing scheme.

   Based on the proportional homing scheme and the 1- spreading scheme, we present the extended HS algorithm, as shown in Algorithm 2.

   [(1-12)C] [12C] [(1-23)[12C]] [23[12C]]

   Fig.6. The proportional homing scheme.

6. PERFORMANCE ANALYSIS

   Formally analyze the expected delivery delay of HS. First, adopt the continuous Markov chain to compute the expected delivery delay. For generality, focus on the extended HS for heterogeneous MSNs in the following.

   s

   s

   C = 6. According to Definition 6, a state s = {s1, · · · , sh, · · · , sh+n} satisfies:

   C

   C

   hn

   i1 i

   1. Two states are combined as one state: s = (2, 1, 0, 2, 1, 0, 0, 0, 0)

      s1 s2

      ….. sh

      (1)

      $

      (b) The start state: st = (0, 0, 0, 6, 0, 0, 0, 0, 0)

      (c) The optimal state: so = (1, 1, 1, 1, 1, 1, 0, 0, 0)

      Fig.7. An example of network state, in which the numbers in the squares and the circles are the numbers of copies held by the homes and nodes, respectively (h = 3, n = 6, C = 6).

      Algorithm 3: Compute the expected delivery delay

      1. Construct the state transition graph G:

      2. Determine the state set S;

      3. Determine s,s_ (t) for each pairwise s, s_S;

      4. Set fs,se (t)=0 (sS);

      5. Delete all states (_=st) whose in-degree is 0;

      6. Let array dout(s)=out-degree of s (sS);

      7. while S _= do

      8. for each s_S that dout(s_)=0 do

   9. S=S{s_};

   1. for each sS that s,s_ (t) _=0 do

      sp …… shn

      Second, we determine the state transition functions. For two arbitrary states s, s S, we use s,s (t) to denote the probability density function about the time t that it takes for the state transition from s to s. The transition probability is zero if more than two component of s, s are different.

      Finally, add the end state into the graph, denoted by se, which is related to the third phase. In fact, each state in the first phase and the second phase can be directly transited to be the end state when a message holder encounters the destination. Thus, each state has a direct edge to the end state se.

      Based on the above method, the state transition graph G(S,

      {s,s (t)|s, s, S}) is constructed. That is, the state transition graph G is a directed acyclic graph. After constructing the state transition graph, calculate the expected delivery delay of the message, which is equal to the expected delay for the transition from the start state to the end state. The cumulative probability density function for the state transition from the start state to the end state, denoted by fst,se (t). An arbitrary state s and its next states Ns = {s|s,s (t) > 0, sS }. Then, the cumulative probability density functions for the state transitions from these states to se satisfy:

      t

   2. if s_ is se then

      f s,se (t) s,s' (x) f s,s ' (t x)dx

      c

      c

      (2)

   3. fs,se (t)=s,s_ (t);

   4. else

   5. fs,se (t)=fs,se (t)+s,s_ (x)fs_,se (tx)dx;

   6. dout(s)=dout(s)1;

   16. Output: tfst,se (t)dt;

   1. Computing the Expected Delivery Delay

      Construct a state transition graph and use a continuous Markov chain to compute the expected delivery delay of HS.

      First, a concept of network state, which is used to describe the distribution of message copies in the whole network.

      Definition 6: (State of Network s): s is a vector with h+n components, i.e., s = _s1, s2, · · ·, sh, sh+1, · · ·, sh+n (s1 · · ·

      s'Ns0

   2. The Upper Bound of Expected Delivery Delay

      The average delay of the homing phase as the average value of delays for each copy reaching the first home in the homing phase, denoted by D(1). The average delay of the spreading phase as the average value of delays for each home in H_ to receive a copy, denoted by D(2). The delay for the destination to fetch a copy from a message holder is defined as the delay of the fetching phase, and is denoted by D(3). Then, the average delays of the first two phases D(1), D(2), and the delay of the fetching phase D(3) satisfy:

      sh; sh+1 · · · sh+n), in which the i-th component si represents the number of message copies held by the i-th home (if i h) or node i h (if i>h).

      Here, for simplicity, we let s1 s2 · · · sh and sh+1 · ·

      · sh+n. If si < sj (1 i < j h or h + 1 i < j n), we exchange si and sj , and treat the states before and after the

      D(1)

      D(2)

      1

      h

      3h 2h

      h

      (3)

      (4)

      exchange as the same state, so as to decrease the number of

      total states. Then, based on Definition 6, there are two special

      hC (h h)C ,C h D(3)

      (5)

      states. One is the start state, denoted by s = _0, · · ·, 0, s =

      1 ,C h

      t h+1

      h (C h)

      C, 0, · · ·, 0. Another is the state that all message copies have

      finished the homing phase and the spreading phase, but none

      By combining the average delay of the two parts we have

      of them are received by the destination. In this state, the

      D(2) D(2) D(2) 3h

      (6)

      probability of the destination fetching a message copy is the largest. Thus, we call it the optimal state, denoted by so = _1, 1, · · ·, 1, 0, 0 · · · . Fig. 7 shows three states of a simple MSN, where h = 3, n = 6, and

      1 2 2h

      The expected delivery delay of the HS algorithm, denoted by D, satisfies:

      1 3h

      • h ,C h

        h

        D

        2h

        hC (h h)C

        (7)

        1

        h

      • 3h 2h

      1

      h (C h)

      ,C h

7. PERFORMANCE EVALUATION

The algorithms in the comparison, evaluation methods, settings, and results are presented as follows.

1. Algorithms in Comparison

   The focus is on zero-knowledge multi-copy routing algorithms for MSNs. To make a fair performance comparison, compare the Homing Spread algorithm with the existing zero-knowledge routing algorithms: the Spray&Wait algorithm and the Epidemic algorithm with a given number of copies. An Epidemic algorithm in which there is no limit to the number of copies, denoted by EpidemicU.

2. Simulation Settings and Metrics

   Simulations are conducted on synthetic traces that are generated by a Time-Variant Community Model (TVCM) [8]. All of the evaluated variables are shown in Table 1.

   Parameter name	Range
   Deployment area	20*20
   Number of nodes n	100-200
   Number of homes h	0-5
   Homing probability per second	0.04-0.08
   Number of messages	10,000
   Allowed message copies C	2-20

   Table 1. Evaluation Setting

   The widely-adopted metrics are evaluated in simulations, including the average delivery delay and average delivery ratio. The average delivery delay is the delivery time for the first message copy to reach its destination. The average delivery ratio is the ratio of successful deliveries to all message deliveries.

   (a)Number of nodes: n=100 (b) Number of nodes: n=200 Fig.9. Performance comparisions of average delivery delay vs. number of message copies(h=5,=0.04

   Number of homes: h=0)

   (a)Number of home: h=0 (b)Number of home: h=5

   Fig.10. Performance comparisions of average delivery delay vs. number of message copies(n=200 ,=0.04).

   (a)Homing probability:=0.04 (b)Homing probability:=0.08 Fig.11. Performance comparisons of average delivery delay vs. number of message copies (n=200, h=5).

3. Evaluation in Homogeneous Settings

   Three groups of simulations to evaluate the performance of average delivery delay of the algorithms under the homogeneous setting.

   The results in Figs. 9-11 show that the average delivery delays of the three algorithms reduce when there is an increase in the number of copies. In Epidemic, only the source spreads the copies in the network, has the worst delivery delay. Spray&Wait, in which multiple nodes and homes help to spread the copies in the network, has a medium performance. Homing Spread, which mainly lets homes, assisted by nodes, spread the copies in the network, has the best performance among the three algorithms. The results also prove that homes play an important role in the message spreading process. When the number of homes increases, or the homing probability increases, the average delivery delay of Homing Spread reduces significantly, while the average delivery delay of Spray&Wait decreases moderately. At the same time, the average delivery delay of Epidemic reduces slightly, as shown in Figs. 10 and 11, respectively.

   Also conduct three groups of simulations to evaluate the performance of the above algorithms on the delivery ratio.

   The results in Figs.12-14 show that Homing Spread can successfully deliver the messages more quickly, and can achieve an average delivery ratio that is much higher than those of Epidemic and Spray&Wait. When the number of homes or the homing probability increases, the average delivery ratio of Homing Spread reduces significantly, as shown in Figs. 10 and 11. In contrast, the average delivery ratio of Spray&Wait reduces moderately. However, the average delivery ratio of Epidemic reduces by a little.

   In addition, Fig. 14 shows that when the number of copies increases, the average delivery ratios of Homing Spread and Spray&Wait will increase significantly. However, when the number ofcopies goes beyond a moderate value their average delivery ratios increase slightly. In contrast, Epidemic is barely affected by the number of copies.

   (a)Number of homes: h=0 (b)Number of homes: h=5

   Fig.12. Performance comparisons of average delivery ratio vs. time- to-live (n=200, =0.04, C=10).

   (a)Homing probability:=0.04 (b)Homing probability:=0.08 Fig.13. Performance comparisons of average delivery ratio vs. time- to-live (n=200, h=5, C=10).

   (a)Message copies: C=5 (b)Message copies: C=10

   Fig. 14. Performance comparisons of average delivery ratio vs. time- to-live (n =200, h =5, =0.04).

4. Evaluation in Heterogeneous Settings

First, change the parameter from 4 to 12, set h n = 200,

= 0.04 0.16, C = 10, and then, record the average delay of all message deliveries. Second, evaluate the average delivery ratio by setting the

(a)Homing probability: =0.04 (b)Homing probability: =0.08 Fig.15: Performance comparison of average delivery delay vs. average home number (n=200, C=10).

(a)Homing probability :=0.04 (b)Homing probability: =0.08 Fig.16: Performance comparison of average delivery delay vs. average home number(n=200,C=10, TTL=10).

Time-To-Live of each message TTL = 10, beyond which the message copy will be discarded. Homing Spread has a smaller average delivery delay and a larger average delivery ratio than other algorithms, including Binary HS. When the average home number increases, the average delivery delay of Homing Spread will decrease, and the average delivery ratio will increase; these come close to the best results.

CONCLUSION

A special type of mobile social network, where the routing space includes some frequently visited homes, and propose a zero-knowledge multi-copy routing algorithm called Homing Spread (HS). HS uses the home highlight and sets a higher need for homes to help spread messages rapidly. Theoretical

analysis and reproduction results demonstrate that homes assume a vital part in the message spreading procedure. By utilizing the idea of home, HS accomplishes a superior execution than existing zero-knowledge MSN routing algorithms.

REFERENCES

1. J. Wu, M. Xiao, and L. Huang, Homing spread: Community home-based multi-copy routing in mobile social networks, in IEEE INFOCOM, 2013.

2. A. Balasubramanian, B. N. Levine, and A. Venkataramani, Dtn routing as a resource allocation problem, in ACM SIGCOMM, 2007.

3. X. Chen, J. Shen, T. Groves, and J. Wu, Probability delegation forwarding in delay tolerant networks, in IEEE ICCCN, 2009.

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

5. L. Guo, C. Zhang, H. Yue, and Y. Fang, A privacy- preserving social-assisted mobile content dissemination scheme in dtns, in IEEE INFOCOM, 2013.

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

   2000-06, June 2000.

7. T. Spyropoulos, K. Psounis, and C. Raghavendra, Efficient routing in intermittently connected mobile networks: The multiple-copy case, IEEE/ACM Transactions on Networking, vol. 16, no. 1, pp. 7790, 2008. .

8. W. Hsu, T. Spyropoulos, K. Psounis, and A. Helmy, Modeling time-variant user mobility in wireless mobile networks, in IEEE INFOCOM, 2007.

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