Abstract
In opportunistic network, data transmission relies mainly on node mobility. However, the moving patterns of nodes in diverse application scenarios are different. Thus, nodes moving patterns should be considered when designing data transmission strategy. Based on the analysis of node moving characteristics in opportunistic social networks, two parameters, called social rang and social frequency, are introduced and sociability-based Spray and Forward (SSF) scheme is proposed by applying them to the data dissemination and forwarding phase, respectively. Simulation results show that SSF can effectively improve data delivery ratio and reduce latency under the given model.
1. Introduction
As a new type of wireless ad hoc networks, opportunistic network [1] has been mushrooming in recent years. Compared with traditional ad hoc networks, opportunistic network depends mainly on node moving to achieve data transmission. As one kind of opportunistic networks, opportunistic social network [2] is mainly composed of human-carried mobile devices (such as mobile phone, PDA) and achieves data communication by the human movements in their social activities.
Data transmission in opportunistic network is challenging due to the fact that the network is intermittently connected. Practically, the application scenarios of opportunistic network are diverse, for example, wildlife tracking network [3], vehicle network [4], and pocket switched network [5], which results in the fact that moving patterns of nodes are quite different for different scenarios. So node's mobility pattern should be explored when designing data transmission scheme. Intuitively, in human society, people with wide range of social activities can encounter more different people and some people can meet each other regularly because they are socially connected. On network level, we use social range and social frequency to describe the two features of node mobility. Given that there is no significant linear correlation between the two parameters, this paper introduces social range and social frequency in different stages of data forwarding, and proposes a sociability-based Spray and Forward data transmission scheme based on the improvement of Spray and Wait [6].
2. Related Work
In terms of the number of message copies in network, existing data transmission schemes can be categorized into single-copy scheme and multicopy scheme. For single-copy scheme, there is only one message copy for each message at any time instance. Message carrier deletes the message from its memory once it forwards the message to another node. Typical single-copy scheme includes Direct Delivery (DD) [7] and First Contact (FC) [8]. The basic idea of DD is that source node will always carry the message until it delivers the message to the destination it can reduce network overload and energy consumption, but its performance on delivery ratio and latency are very poor especially in the scenario where source node cannot meet with destination node directly. For FC, by keeping the ID of node it has passed by, message is only forwarded to the node that did not carrier it before. Compared with DD, FC can improve data delivery ratio and shorten delay. Single-copy scheme can reduce traffic redundancy, but its performance on delivery ratio and latency may be very poor.
On the other hand, by increasing the number of message copies in network, multicopy scheme can achieve high delivery ratio. Epidemic [9] is one of the most typical multicopy schemes. Messages are forwarded in a way like database replication. In theory, if network resource is unlimited, with nodes continuous encounters, messages can reach every node. However, owing to the limitation of node storage, message
In consideration of node mobility, this paper applies social range and social frequency to improve Spray and Wait and proposes a sociability-based Spray and Forward scheme (SSF). SSF includes Spray phase and Forward phase. In Spray phase, message relay nodes are selected based on their social range, in Forward phase message is forwarded to the nodes whose social frequency with destination node is bigger than that of the current carrier.
3. SSF Scheme
In human society, people move based on their social activities, so we cannot simply use RWP (random waypoint) [10] mobile pattern to model nodes mobility. Intuitively, in people's daily life, some people have a wide range of social activities; they can meet a variety of people; some people meet each other regularly because they are socially connected for work, friendship, and so on. Figure 1 illustrates the social features (normalization value) of some nodes in pmtr [11] dataset; we can see that there is a significant difference between the two parameters, so instead of integrating them into a single value, we use them in different phase to forward message, which is different from existing work [12].
Social features of nodes in pmtr dataset.
3.1. System Model and Assumptions
In human daily life, people's activities are based on geocommunity, such as a classroom, a lab, or a dormitory for a student. Based on the roles people play, people can engage in various communities, so we give the following network model and related definition.
The mobility of a node is based on the mobility of the user who carries the node. A node can engage in one or more communities; that is, for some inert nodes, they only appear in limited communities, but for some active nodes, they can be active in more communities. In this paper, the area of a geocommunity is small (like a lab, a classroom); individuals in the same community can contact directly in a face-to-face way, so the source and the destination of messages generally belong to different communities. Nodes belonging to a single community move according to the Cluster movement model. Nodes belonging to multiple communities move according to the Map Route movement model.
A. Social Range. Social range reflects the size of people's circle of friendship in social life, and we define the social range of a node as the number of nodes it can directly encounter. Suppose that the collection of nodes that A can directly meet is
B. Social Frequency. Social frequency refers to the frequency of encounter between two nodes. The more they meet each other, the better opportunity they have to communicate with each other. Assuming that the number of times node A encounters B is
3.2. SSF Strategy
Based on the above definitions and Spray and Wait scheme, this paper puts forward an improved data transmission scheme, called SSF (sociability-based Spray and Forward), for opportunistic social network. SSF makes forwarding decision based on the local encounter information of nodes. The main idea of SSF is to spread out the message from local area as far as possible by spraying message to nodes which have a wider social range in Spray phase and to achieve a rapid-delivery of message it forwards message to nodes which have a higher social frequency with destination. A detailed exposition of SSF is given below.
A. Spray Phase
When source node S generates a message M whose destination is D, the related number of message copies is set as L in the network. Assume that S meets node C. If the social range of C is bigger than that of S; that is, Message carrier repeats Step (2) until there is only one message copy left in its buffer; data transmission steps into Forward phase.
B. Forward Phase
Suppose that the current message carrier C meets node E; if there is Repeat Step (4) on E and the following relay nodes until M is delivered to destination D or deleted from the message buffer due to
Compared with Spray and Wait, the advantages of SSF can be concluded as follows.
As is well known, the friend circle of people in the same community largely overlaps. Similarly, the encounters of nodes located in the same geocommunity also largely overlap during a period of time; Spray and Wait makes node continuously spray message copies to its encounter nodes without selection which makes its Spray phase inefficient. Given that nodes with large social range will have a big chance to carry message to different communities, SSF will select the nodes whose social range is larger as message carrier in Spray phase which can avoid invalid spray to some extent. In Forward phase, SSF chooses nodes that have a better social frequency with destination to forward message, so it can achieve rapid delivery and avoid the weakness of Spray and Wait in which message carrier will wait to encounter destination to delivery message.
4. Simulation and Evaluation
4.1. Simulation Scenarios and Parameter Settings
Simulation is made on ONE1.4.1 [13] which is a typical simulation platform for DTN (Delay and Tolerant Network). There are 6 geocommunities in this simulation, and nodes move among these communities. The activity area of some nodes is limited; they can only access few communities and even move in a single community. For other nodes, their activity areas can be very wide; they can access more communities. The above activity patterns are also common in human real social life. Moreover, the geocommunity in this paper refers to some small venues like a lab, a students' dormitory, or a classroom in school, rather than some wide areas like an overall campus and its public areas. Nodes move according to Custer movement model within a community and move according to Map Route movement model among communities. Related simulation parameters are shown in Table 1.
Simulation parameters.
4.2. Simulation Results and Analysis
4.2.1. Performance of Each Protocol under Varying Simulation Time
In our experiment, there are two message generating events, one generates a message every 5 min and the other generates a message every 10 min. Figure 2 shows that, compared with the other three forwarding algorithms, SSF achieves the highest delivery ratio all the time. As is well known, the rational usage of multicopy mechanism can help to improve the delivery ratio; SSF not only uses multicopy mechanism but also makes better use of nodes social features in message transmission, which makes its delivery ratio much higher than the other schemes. FC is one kind of single-copy forwarding schemes, but it forwards message to all the nodes which have not ever carried the message; thus, it can make message go through almost all of the nodes; meanwhile, because of the unlimited message
Delivery ratio versus simulation time.
We also compared overhead ratio in Figure 3. It shows that, under the default settings, the overhead ratio of SSF is the lowest besides Spray and Wait. Because the message forwarding opportunity is very small in Wait phase, the overhead ratio of Spray and Wait is lower than that of SSF. Compared with the above two algorithms, FC uses a single-copy mechanism to forward data, but it enables messages to traverse most of the nodes, so its overhead ratio is higher than the above two algorithms. Due to its flooding strategy, epidemic has the highest overhead ratio.
Overhead ratio versus simulation time.
In addition, we also observed the average latency of every algorithm over time. Message delivery delay includes queuing scheduling delay, sending delay, and transmission delay. Figure 4 shows that the performance of SSF on average latency is the best, that is, because of its wise usage of nodes sociability on message forwarding.
Average latency versus simulation time.
4.2.2. Performance of Each Protocol under Varying Message Generation Interval
In this experiment, the simulation time is set as 2 days.
In Figure 5, we can see that the delivery ratio of SSF is always the highest when the message generation rate changes. Except for Spray and Wait, the delivery ratio of each protocol increases as the message generation interval rises. It is because that the more available buffer there is in the network, the fewer messages are dropped. In Spray and Wait, there are only few messages that can be forwarded, so its delivery ratio keeps stable and low.
Delivery ratio versus message generation interval.
From Figure 6, we can clearly observe that the overhead ratio of epidemic is also the heaviest. Spray and Wait has very low overhead ratio that is also because of its slim message forwarding opportunity. Although FC is one kind of single-copy forwarding schemes, it can forward more messages when the message
Overhead ratio versus message generation interval.
We also plot out the average latency of each protocol in Figure 7. It shows that the average latency of FC and SSF changes significantly as the message generation interval changes while Spray and Wait and epidemic keep stable. In general, the average latency of SSF is lower than epidemic and FC.
Average latency versus message generation interval.
5. Conclusion
Aiming to improve the message delivery ratio and reduce the latency, this paper proposes a sociability-based Spray and Forward scheme for data transmission based on the node's social characteristics. First, we analyze the node's social characteristics in opportunistic social network and by applying them to improve Spray and Wait propose SSF. Experimental results show that SSF can significantly increase the message delivery ratio and reduce the delivery latency. However, this paper uses a relatively simple approach to analyze node's social characteristics; in the future, we can deeply study node's social characteristics and further improve SSF to make it more practical and intelligent.
Footnotes
Acknowledgments
This work is sponsored by the National Natural Science Foundation of China (61373137, 61373017, 61171053, and 61100199), the Scientific & Technological Support Project of Jiangsu (BE2012755), the Natural Science Foundation of Jiangsu (BK2011755), and the Scientific Research & Industry Promotion Project for Higher Education Institutions (JHB2012-7).