1、Evolution-cast: Temporal Evolution in Wireless Social Networks and Its Impact on Capacity,Luoyi Fu, Jinbei Zhang, Xinbing Wang Department of Electronic Engineering Shanghai Jiao Tong University,2,Outline,Introduction Motivations Objectives Network Model and Definition Evolution-cast in Homogeneous T
2、opology Evolution-cast in Heterogeneous Topology Discussion Conclusion,3,Motivations,Social network has been under intensive study for decades. Barabasi and Albert Model: preferential attachment phenomenon Watts and Kleinberg: small-world phenomen Densification: shrinking diameter over time,4,Motiva
3、tions (cont),Wireless social network is drawing popularity. Cost-effective routing design taking advantage of the characteristics of social networks 123,1 E. Dlay and M. Haahr, “Social Network Analysis for Routing in Disconnected Delay-Tolerant MANETs”, in ACM MobiHoc07, Montreal,Quebec, Canada, 200
4、7. 2 P. Hui, J. Crowcroft, E. Yoneki, “BUBBLE Rap: Social-based Forwarding in Delay Tolerant Networks”, in ACM MobiHoc08, Hong Kong, China, 2008. 3 W. Gao, Q. Li, B. Zhao and G. Cao, “Multicasting in Delay Tolerant Networks: A Social Network Perspective”, in Proc. MobiHoc, New Orleans, USA, 2009.,Ca
5、pacity receives little investigation under wireless social networks.,5,Motivations (cont),Several questions arise: Stringent demand on capacity in wireless social networks New challenges as well as potentials brought by social networks Any difference on capacity studied under wireless social network
6、s? How will capacity be impacted by social network properties, positively or negatively?,6,Objectives,Capacity in large scale wireless social netowrks Wireless communication: adjacent interference and transmission range Nodes exhibit social network characteristics The network is also evolving (real
7、networks are not fixed objects 45678):1. New node joins the network over time2. New links established between nodes over time,4 M. Starnini, A. Baronchelli, A. Barrat, R. Pastor-Satorras, “Random Walks on Temporal Networks”, in Phys. Rev. E 85, 056115, 2012. 5 N. Perra, A. Baronchelli, D. Mocanu, B.
8、 Goncalves, R. PastorSatorras, A. Vespignani, “Walking and Searching in Time-varying Networks”, arXiv:1206.2858, 2012. 6 L. Rocha, F. Liljeros, P. Holme, “Simulated Epidemics in an Empirical Spatiotemporal Network of 50,185 Sexual Contacts”, in PLoS Comput Biol 7(3): e1001109, 2011. 7 L. Rocha, A. D
9、ecuyper, V. Blondel, “Epidemics on a Stochastic Model of Temporal Network”, arXiv:1204.5421, 2012. 8 L. Rocha, V. Blondel, “Temporal Heterogeneities Increase the Prevalence of Epidemics on Evolving Networks”, arXiv:1206.6036, 2012.,7,Outline,Introduction Network Model and Definition Evolution-cast i
10、n Homogeneous Topology Evolution-cast in Heterogeneous Topology Discussion Conclusion,8,Network Model,Temporal evolution of network An algorithm describing the increase of the number of nodes and that of links established between nodes 5,9S. Lattanzi and D. Sivakumar, “Affiliation Networks”, in Proc
11、. ACM STOC09, Bethesda, Maryland, USA.,9,Network Model (cont),Geographical Topology: Homogeneous distribution Heterogeneous distributionTraffic Pattern-evolution-cast: Evolution unicast: a new arriving node is chosen to be either a source or a destination of a randomly chosen node in existing networ
12、kmessage sharing between limited number of individuals Evolution multicast: a new arrival randomly chooses k(t) out of n(t)nodes that already existing before t, acting as a source or destinations of these k(t) nodes.message broadcast among multiple friends Interference Model: widely used protocol mo
13、del,10,Definition,Feasible Capacity: We say that a per node capacity (t) at time t is said to be feasible if there exists a spatial and temporal scheduling scheme that yields a per-node capacity of (t). Consider the case where the network enters stable evolution (the network evolves according to a c
14、ertain rule over time), for an arbitrary duration(i1)T(t), iT (t), if there are packets transmitted from source to destination, then, we say the average per-node capacity isat time t, after t exceeds a specific value t0. Here t0 is the threshold of time after which the network is supposed to enter s
15、table evolution.Per-node Capacity: We say that a per-node capacity at time t in the network is of order (f(t) if there is a deterministic constant 0 c1 c2 + such that,11,Outline,Introduction Network Model and Definition Evolution-cast in Homogeneous Topology Evolution Unicast Evolution Multicast Evo
16、lution-cast in Heterogeneous Topology Discussion Conclusion,12,Property of Homogeneous Topology,Probability distribution of homogeneous topology,Lemma 1: Consider the geographical distribution of nodes at time slot t, where there are n(t) nodes in the network. Then, the positions of nodes follow a u
17、niform distribution over the whole network when t .Lemma 2: In homogeneous geographical distribution, the probability that a social path (denoted by S = u1 u2 u3 . . . uH = D) composed of a sequence of consecutive links generated in Algorithm 1 are also reachable within constant hop of transmission
18、range goes to zero.,Intuition behind: Social relations do not affect capacityOnly network evolution will affect capacity,13,Routing Scheme,Evolution-cast Tree (ET): The idea is similar to that in 10.The only difference lies in that the number of nodes increases over time in our work.,10X. Li, “Multi
19、cast Capacity of Wireless Ad Hoc Networks”, in IEEE/ACM Tracs. Networking, Vol. 17, Issue 3 June 2009.,14,Evolution Unicast,The number of destinations per source,Lemma 3: In evolution unicast, the average number of destinations per source is of order (log t).The capacity of evolution unicastTheorem
20、1: With homogeneous geographical distribution of nodes, the per-node capacity for evolution unicast traffic iswhen t is sufficiently large.,15,Evolution Multicast,The number of destinations per source,Lemma 6: In evolution mutlicast traffic, the average number of destinations per source is of order
21、, where . The capacity of evolution multicastTheorem 1: With homogeneous geographical distribution of nodes, the per-node capacity for evolution multicast traffic iswhen t is sufficiently large.,16,Outline,Introduction Network Model and Definition Evolution-cast in Homogeneous Topology Evolution-cas
22、t in Heterogeneous Topology Evolution Unicast Discussion Conclusion,17,Heterogeneous Topology,Generation of heterogeneous topology New arrival tends to locate more closer to his friendProbability distribution of heterogeneous topologyLemma 9: If the topological generation of the network evolves acco
23、rding to Mechanism 2, then, when t is sufficiently large, the distribution of geographic distance between nodes will yield as follows:The spatial stationary distribution of a node is assumed to be rotationally invariant with respect to another node called support, which can be described by a functio
24、n (l) decaying as a power law of exponent , i.e., (l) l, . And here l ranges from to (1), representing the distance between the node and the support.,18,Routing Scheme,Temporal evolution routing scheme: Message is delivered along a chain of relay nodes whose home point is progressively closer to the
25、 destination.,19,Evolution Unicast Capacity,Theorem 3: For heterogeneous topology distribution, under our proposed routing scheme, the achievable per node capacity of evolution-cast, under uniform traffic pattern, is,20,Outline,Introduction Network Model and Definition Evolution-cast in Homogeneous
26、Topology Evolution-cast in Heterogeneous Topology Discussion Conclusion,21,Discussions,Impact of evolution-cast on capacity Social relations cannot lead to capacity improvement in homogeneous geographical distribution:1. transmission is only within a certain transmission range2. the average source-d
27、estination distance is3. New arrivals causes more bandwidth allocation The capacity can be improved in heterogeneous topology:1. a constant capacity is achievable when,Resulting in constant number of highly centralized nodes in the network,22,Discussions,Relationship with networks having fixed numbe
28、r of nodes Network with uniform topology1. Unicast: Fixing t=n, we have 2. Multicast: Fixing t=n, we have,Close to the result in 11,Close to the result in 12,11 P. Gupta and P. R. Kumar, “The Capacity of Wireless Networks”, in IEEE Trans. Inform. Theory, vol. 46, no. 2, pp. 388-404, Mar. 2000. 12 X.
29、 Li, “Multicast Capacity of Wireless Ad Hoc Networks”, in IEEE/ACM Tracs. Networking, Vol. 17, Issue 3 June 2009.,23,Discussions,Relationship with networks having fixed number of nodes Network with heterogeneous topology1. Unicast: Fixing t=n, we have,Almost constant capacity when Close to the (1) c
30、apacity in 13,13 A. Ozgur and O. Leveque, “Throughput-Delay Trade-Off for Hierarchical Cooperation in Ad Hoc Wireless Networks”, in Proc. Int. Conf. Telecom., Jun. 2008.,24,Outline,Introduction Network Model and Definition Evolution-cast in Homogeneous Topology Evolution-cast in Heterogeneous Topolo
31、gy Discussion Conclusion,25,Conclusions,We present a mathematically tractable model where nodes are associated with each other through social relations but employ transmission through wireless communications. We investigate evolution-cast capacity in terms of unicast and multicast in both homogeneous and heterogeneous topology. This is the first work that studies capacity in a both evolving and socially related wireless networks. Our result can be flexibly applied to more general cases and shed insights into the design and analysis of future wireless networks.,Thank you !,
