تجزیه و تحلیل عملکرد از گسترش ارسال پیام چند قاب در شبکه های مقاوم تاخیر

Communication opportunities in delay tolerant networks are uncertain, so the message is transmitted in a store-carry-forward way, which depends on the contact between nodes. To use the contact efficiently, the message is often divided into many bundles, which are very small and can be transmitted successfully in one contact. Such multi-frame spreading algorithm is very important, but state of the art works just assume that the message is very small and has only one bundle. This paper proposes a theoretical framework based on mean field limit to evaluate the epidemic-like multi-frame spreading algorithm for the first time. In addition, the selfish behaviors can have certain impact on the store-carry-forward communication mode, so we extend our model to the case that nodes are selfish. Simulations show the accuracy of our model. Numerical results show that the more bundles the message has, the lower the average delivery ratio will be. In addition, the selfish behaviors can make the performance be worse.

With the increasing of mobile operating systems, such as iPhone OS, Android and Symbian OS, mobile phones have already evolved from simple voice communication means into powerful devices able to provide a variety of services to users. In particular, they can transmit the videos or music in a peer-to-peer (P2P) way through the short-range communication technologies (Bluetooth, WiFi, etc.) in them. Due to the limited communication range or mobility of nodes, it is hard to maintain the continuous end-to-end path between them as for classic Internet P2P applications. Obviously, such network can be seen as the mobile opportunistic networks, which belong to the delay tolerant networks (DTNs) in which the end-to-end path between nodes may not exist [1]. At present, DTNs are used in many applications, such as mobile data offloading [2], vehicular networks [3], etc. Message spreading protocols in traditional ad hoc networks, which relay on the end-to-end paths, cannot work in DTNs efficiently. In order to overcome the problem of the network partitions, nodes in DTNs communicate with each other in a store-carry-forward way. When the next hop is not immediately available for the current node, some relay nodes will store the message in their buffer, carry the message along their movements, and forward the message to other nodes when a new communication opportunity is occurring [1]. It is easy to see that the communication in DTNs closely depends on the contact of nodes. However, the duration of each contact is often limit, so if the message is too big, it is hard to transmit the message in one contact successfully. To use the contact efficiently, the message is often divided into multiple bundles (also can be seen as frames), which are very small and can be transmitted in one contact successfully. In this paper, we assume that only one frame can be transmitted in each contact and study the performance of the epidemic-like spreading algorithm. Epidemic spreading has been studied many years in complex networks. Kephart and White [4] and [5] are among the first to propose the epidemiology-based analytic models. However, they are based on topologies that do not represent modern networks. The work in [6] studies the code red worm propagation, but does not create a theoretical model. At present, many works study the epidemic spreading in scale-free networks. For example, the work in [7] studies the epidemic spreading in scale-free networks and finds the absence of epidemic threshold in certain cases. In other words, the infection density tends to be 1 in the network. The work in [8] demonstrates that epidemics pervade in scale-free networks in a precise hierarchical fashion, from higher-degree nodes to lower-degree ones. In addition, there are many other works, which evaluate the performance of the epidemic spreading in different cases. For example, the work in [9] explores the epidemic spreading in weighted scale-free networks. The work in [10] studies the SI (susceptible-infected) model on scale-free networks with identical infectivity. On the other hand, the rumor is spreading in similar way and many works have been proposed to study the performance of the rumor spreading, such as [11] and [12]. Different from the epidemic or rumor, the forwarding process of the message needs certain resource, such as bandwidth, energy, etc. [13]. To save the limited resource, one node may not forward the information to others all the time due to the selfish nature [14]. However, the store-carry-forward communication mode in delay tolerant networks needs nodes to work in cooperative way. Therefore, the selfish behaviors can have certain impact. In particular, the selfish behaviors can be divided into two classes, which are individual selfishness [15] and social selfishness [16], respectively. The first one often denotes the cooperative level between the non-friends, and the second one denotes the cooperative level between the friends. At present, there are some works, which study the impact of the selfish behaviors on the epidemic-link spreading algorithm. For example, the work in [17] proposes a theoretical model to evaluate the impact of social selfishness on Epidemic Routing (ER) algorithm based on Markov process, and then they propose a model to evaluate the impact of both the individual selfishness and social selfishness on the performance of information propagation [18]. In addition, the work in [19] proposes a theoretical model to evaluate the impact of selfishness when nodes may be free-riders, which will quit from the network once they obtain the message. However, these works fail to consider the distribution of the friends of one specific node efficiently. For example, [17] randomly divides the nodes in the network into 2 communities, and nodes in the same community are friends. However, it does not show why nodes are divided in this way. In fact, many works have shown that the number of friends of one specific node may conform to the Power-law distribution [20], but the works in [17], [18] and [19] cannot be used to evaluate the impact of the selfish behaviors in this case. In addition, above works just assume that the message has only one bundle, so they can be used only when the message is very small. When the message is divided into many bundles, the problem is very complex, and we evaluate such multi-frame spreading algorithm for the first time. The main contributions of this paper are summarized as follows. • We obtain quantitative results based on mean filed limit to evaluate the performance of the epidemic-like spreading algorithm in DTNs, in which each message is divided into multiple frames. • We extend the theoretical model to the case that nodes are selfish, and we consider the distribution of the nodes’ friends. For example, the probability that a node has k friends is P(k), and our theoretical model can be used when P(k) conforms to any distribution, but we use the Power-law distribution as a special example to get the simulation and numerical results. • We check the accuracy of our model through simulations. Extensive numerical results show that if the message has many bundles, the average delivery ratio is smaller. In addition, the selfish behaviors can make the performance be worse. On the other hand, the impact of the selfishness is related with other factors. For example, if the average number of friends is bigger, the impact of the individual selfishness is smaller, but the impact of the social selfishness is bigger. This result is different from the works in [17], [18] and [19], which have shown that the epidemic-like spreading algorithm is very robust to the social selfishness. On the other hand, numerical results show that the average delivery ratio nearly has a sharp transition. For example, with the increasing of the number of the frames, the average delivery ratio equals to 0 or 1 most of the time, and the jumping process from 1 to 0 is very short.

Performance analysis of the message spreading algorithm is an important problem in mobile networks. Due to the uncertain of communication opportunities in DTNs, message spreading adopts a store-carry-forward way, which is similar to the epidemic spreading between humans. However, different from the epidemic, the message is often divided into multiple frames to use the opportunistic contact efficiently in DTNs. This paper presents a theoretical model to evaluate the performance of the epidemic-like multi-frame message spreading algorithm in DTNs for the first time. Our model also considers the selfish behaviors of nodes. Different from most of the existing works, we use the probability P(k) to denote the probability that a node has k friends. The probability P(k) may conform to any distribution. In particular, many works have shown that P(k) may conform to the Power-law distribution, and we use such distribution as a special case to get the simulation and numerical results. Simulations based on both synthetic and real motion traces show the accuracy of our model. Extensive numerical results show that the selfish behaviors can make the performance be worse. In addition, the degree of the impact of the selfish behaviors is related with other factors. For example, if the average number of friends is bigger, the social selfishness can have bigger impact, but the individual selfishness has smaller impact. We also check the impact of the number of frames through numerical results. In particular, if the message has more frames, the average delivery ratio is smaller. On the other hand, numerical results show that the average delivery ratio nearly has a sharp transition phenomenon. For example, with the increasing of the number of the frames, the average delivery ratio equals to 0 or 1 most of the time, and the jumping process is very short. The mobility rule of nodes can have important impact on the performance. In this paper, we assume that nodes move according to an exponential model. Though this model is rational in some applications, it is not accurate in some other applications. For example, some works have shown the power law and exponential decay distribution of the inter-meeting time between mobile nodes. In the future, we want to extend our model to this case. The scheduling policy used in this paper may not be optimal, so we will study the optimal scheduling policy in the future and combine the policy with our theoretical model.