| dc.description.abstract | Peer-to-peer opportunistic communication between mobile devices carried by humanswithout using any infrastructure is largely unexploited. As these devices are carried byhumans, their encounter pattern depends on human mobility pattern which is governedby human social behaviour. Individuals belong to multiple communities, i.e. communitiesin social network overlap. These social ties signi cantly a ect people's movementpattern and in-turn contact pattern of mobile nodes carried by them. This networkparadigm is known as Mobile Social Network (MSN). The communication frameworkfor MSN includes community-based and heterogeneous node popularity-based messagetransmission mechanisms. In this work, we design algorithms for such framework anddevelop two proof of concept applications on top of this framework. We also propose arealistic mobility model for MSN for reliable performance analysis through simulation.Traditional mobility models, such as Random Way Point (RWP) and Brownian Motion(BM), model device mobility as random. However, researchers have shown thathuman mobility is rarely random and such models do not provide a reliable analysis ofnetwork protocol performance. Various characteristics of human mobility are derived inthe literature from mobility traces and social network theory. We propose CommunityAware Heterogeneous Human Mobility (CAHM) model incorporating all such characteristics.CAHM model is based on Heterogeneous Human Walk (HHW)[1] mobility model.CAHM achieves heterogeneous local popularity as observed in real mobility traces whichHHW fails to achieve. It also incorporates following additional properties of human mobility:preference of nearby locations, speed as a function of distance to be traveled andpower-law distributed pause time. We also analyze the performance of traditional andsocially-aware routing protocols with CAHM and other existing mobility models. Ouranalysis shows that existing mobility models signi cantly underestimate the performanceof socially-aware routing protocols.Socially-aware routing protocols are designed to exploit the overlapping communitystructure of MSN for e cient communication. Nodes in MSN should be able to detectone or more communities in which it is member independently in a distributed mannerbecause of the peer-to-peer nature of MSN. There is no distributed overlapping communitydetection mechanism for MSN proposed in the literature. We devise Distributed Overlapping Community Detection (DOCD) mechanism by modifying non-overlappingcommunity detection algorithm SIMPLE[2]. Simulation results show that DOCD detectsoverlapping community structure with 75-80% accuracy.Analysis of properties of overlapping community structure formed by human mobilitycan give important insights for designing better routing protocols. We analyze, throughsimulation, properties such as actual community sizes, the probability of community existenceand the fraction of hub and gateway nodes present in the community on an average.Di erent individuals have di erent local popularity within a community and di erentglobal popularity in the network. We call them hub and gateway nodes respectively.Our analysis of overlapping community structure establishes that small communities aretransient. As per simulation results, the threshold for the same is around 10% of thetotal number of nodes in the network. Further, a higher fraction of hub and gatewaynodes remain present in larger communities with less standard deviation as comparedto smaller communities. Also, the fraction of gateway nodes present in a community ismuch lower than the fraction of hub nodes present in the community.Identifying correct hub and gateway nodes is very important for the e ciency of aprotocol aiming to exploit heterogeneous popularity. Existing methods to identify huband gateway nodes require either ooding of messages or forwarding of not only node'sencounter information but also accumulated encounter information from other nodes.We identify hub and gateway nodes using Markov-chain from the overlapping communitystructure itself (which is found using our DOCD mechanism) without doing messageooding or forwarding of accumulated encounter information from other nodes. Sociallyawarerouting protocols based on explicit community detection need to nd such structureanyway for e cient forwarding. We make use of this structure for identifying hub andgateway nodes also. We compare ordered lists of hub and gateway nodes generatedby Markov chain-based methods with ordered lists generated through simulation usingooding and encounter information. Simulation results show that these ordered lists arehighly correlated, i.e. Markov chain-based methods correctly identify hub and gatewaynodes.We develop protocols for viral spread (many-to-all broadcast) and micro-blogging applicationsin MSN exploiting overlapping community structure and heterogeneous popularityof nodes for e cient forwarding. For the viral spread, bu ering all packets from all sources of a community at each node is prohibitive. Bu er space is limited and bu eroccupancy level also has an impact on energy requirements. Existing protocols eitherwork with speci c assumptions regarding the type of MSN or do not aim to achieve improvementin terms of average packet delivery delay or delivery ratio in the presence of alimited bu er. In our Community Aware Viral Spread (CAVS) protocol, to reduce bu erusage, we probabilistically bu er received packets for forwarding. To o set the loss inperformance due to this, we employ network coding. Network coding is a mechanism inwhich nodes encode two or more incoming packets and forward encoded packets insteadof forwarding them as it is. Simulation results show that CAVS gives acceptable performancefor bu ering probability (Pb) value as low as 0:3 as compared to Pb = 1. Also,with a decrease in Pb, the performance of CAVS gets increasingly better than Epidemicrouting[3]. For Pb = 0:1, packet delivery ratio and average packet delivery delay of CAVSis 122% more and 22% less than Epidemic routing respectively.Our protocol for micro-blogging restricts message forwarding based on distance aswell as time and keeps a constant amount of state information. The protocol is scalableand e cient as message ltering is done at the network protocol level itself as opposedto the conventional approach where it is done at the end points of the network. Further,because of in-network ltering, users can follow their interests and receive messages oftheir interests without getting overwhelmed, instead of having to identify and follow userswith similar interests. It also eliminates the need to maintain a large amount of data atserver machines. As server farms consume a huge amount of energy, it is useful to not touse infrastructure even though the bandwidth requirement of the application is limited.We also propose three models to generate user interest pro les synthetically where userinterest pro le is de ned as a list of tags in which a user is interested along with interestlevel in each tag. Allen et al. in [4] have also proposed a micro-blogging protocol forMSN named as `Uttering'. We measure and compare `e ciency' and `spread index' ofour protocol with `Uttering'. E ciency is de ned as the ratio of the total number of usefulmessages received by all nodes to the total number of messages transmitted by all nodes.Spread index is de ned as the ratio of the total number of users who have received usefulmessages to the total number of users who were interested in those messages. Simulationresults show that spread index of our protocol is better than `Uttering' by 18-59% ande ciency is better than `Uttering' by 35-56% for di erent user interest pro le models. | |
