Performance Analysis And Optimal Control Of Information Propagation In Delay Tolerant Network

Nodes in mobile ad hoc network(MANET) can communicate with each other based on their self-organization, and MANET has many excellent characteristics, such as simple construction, rapid deployment and distributed control, etc. MANET extends the available range of wireless network at a substantial degree. However, routing in traditional MANET often needs the reliable paths between the source and destination pairs as a premise. In fact, such paths may not exist at given time due to the mobility of nodes, sparse density, environment interfere and signal attenuation, etc. This will constrain the application of MANET. For this reason, researchers propose the delay tolerant network(DTN), in which nodes communicate based on the store-carry-forward method. Such communication mode can overcome the network partitions, so DTN further extends the available range of wireless network, and it is very popular now.Information propagation is the base of the application of wireless network, so it is very important. In the store-carry-forward communication mode, nodes do not need to maintain the routing table. When the next hop is not immediately available for the current node, it will store the message in its buffer, carry the message along its movement, and forward the message to others when a new communication opportunity occurs. Obviously, this communication policy depends on many factors, such as the nodes’ behavior and mobility, etc. This further brings many challenges. Combining with the existing latest achievement, this paper explores the performance of the information propagation and its optimal control problem based on the stochastic process and optimal control theory. The main contributions include five aspects, and they are shown in the following contents, respectively.First, we propose the theoretical model to evaluate the impact of nodes’ selfish behaviors and interesting. The story-carry-forward communication mode closely depends on the nodes’ behaviors. For example, if the nodes carrying the message are not willing to forward the message to others due to the selfishness, the performance of the information propagation may decrease. In addition, the selfishness may be related to the social relations of nodes. State of the art works often assume that the nodes can be divided into two communities according to their social relations. However, the nodes may include multiple communities. In order to overcome this problem, this paper proposes a theoretical model to evaluate the impact of the selfish behaviors based on the ordinary differential equations(ODE). This model also can be used to evaluate the impact of the nodes’ interesting. On the other hand, some works find that the communities may not be proper to describe the social relations in some applications, and they use the probability(e.g., the friends of a node may conform to the power-law distribution). Therefore, we also propose a theoretical model to evaluate the impact of selfishness in such case. The accuracy of above models is checked by simulations.Second, we explore the impact of the energy constraint on information propagation. One efficient policy to improve the performance in DTN is to create multiple replicas, and epidemic routing(ER) algorithm is a classic example. However, too many replicas will consume too much energy, and it is a big problem for the wireless network. To decrease the energy consumption, one can constrain the hop count of the message and this can be seen as the L-hop limited ER protocol. For this algorithm, one important problem is to determinate the rational hop count, and this needs an accurate theoretical model to evaluate the relationship between the performance and hop count. To satisfy this demand, we present such model for the first time. Though the L-hop limited ER protocol can decrease the energy consumption, it does not consider the energy consumption of any specific node. In other words, some nodes may use too much energy, and the load distribution is unbalanced. To overcome this problem, we propose the L-count limited ER algorithm, in which the maximal forwarding times of the nodes are limited. Then, we propose a theoretical model to evaluate the relationship of the performance and forwarding times. We find that the L-count limited ER protocol is better under the same energy consumption. Finally, we extend the L-count limited ER protocol to the case, where the maximal forwarding times of nodes are heterogeneous, and propose the corresponding theoretical model. We check the accuracy of above models by simulations.Third, we propose a theoretical model to evaluate the performance of the multi-frame information propagation. Nodes in DTN can exchange the information only when they encounter each other. Due to the limited contact duration and bandwidth, nodes only can transmit limited data in each contact. To use the communication opportunity efficiently, the information is often divided into multiple frames, and they are transmitted, respectively. In this case, the scheduling policy of the frames may have important impact, and this paper proposes the sequential scheduling policy for the first time, and then proposes a theoretical model to evaluate the message spreading performance. The accuracy of the model is checked by simulation. Numerical results show that when the message is bigger, the performance is worse. This means that the sequential scheduling policy may not be a good selection in this case, and shows the necessary to explore the optimal scheduling policy in the future.Then, we explore the optimal control problem of the information propagation. Both the energy constraint and nodes’ selfish behaviors can have important impact on information propagation. Therefore, how to maximize the average delivery ratio under certain constraint is very important. This paper first explores the optimal forwarding and beaconing policies when the total energy consumption is limited. Through Pontryagin’s Maximal Principle, we obtain the optimal policies and prove that the both the optimal forwarding and beaconing policies conform to threshold form. Then, we study the optimal incentive policy. Due to the impact of selfishness, the source has to pay certain fees to other nodes to get help. Such fees may be varying with time. This paper explores the optimal incentive policy when the total cost is limited. This problem is also solved by the Pontryagin’s Maximal Principle. We prove that the optimal policy conforms to the threshold form when the fees satisfy certain conditions(e.g., no-negative, no-decreasing).Finally, we explore the optimal management of dynamic information. The store-carry-forward communication mode needs the nodes to work in a cooperative way. Nodes other than the source and destinations can be seen as the relay nodes. In particular, the source often forwards the information to the relay nodes, and then the relay nodes can further forward the information to the destination. The relay nodes carrying the information can be seen as the server. At present, dynamic information is common in the real world, such as weather forecasts, traffic reports, etc. For dynamic information, newer version is often more important than the older one. If we use a utility function to denote the availability of different versions, the utility of the newer version is bigger. In this case, how to maximize the total utility of the replicas in all servers is very important. Due to the constraint of the buffer or other factors, one message cannot have too many replicas. To constrain the number of the replicas, we first propose the destination-control policy, in which the source often forwards the new version to others, but the relay nodes drops the message with certain probability according to the state of the replicas in them. Similarly, the existing policy is called as the source-control policy, in which the source forwards the new version with certain probability. We prove that the optimal policies in both cases conform to the threshold form. Simulations show the accuracy of our model, and numerical results show that the second policy is better than the source-control policy. Then, we consider the optimal destination-control policy when the information is evolving uncertainly. In this case, nodes other than the source may not know whether the replica stored in them is the latest version. Therefore, they can make decisions only according to the local state and decisions based on the local state can be seen as local-policy. We also explore the global-policy, that is, nodes understand the real state. Then, we get the optimal policies in both cases.In summary, this paper explores some open problems in DTN, and provides the theoretical evidences to further improve the performance of information propagation. Our work has certain academic and practical significance to promote further research of information propagation in DTN.