A Distance-Aware Replica Adaptive Data Gathering Protocol for Delay Tolerant Mobile Sensor Networks

3.1. Network Model

Without loss of generality, we consider a network that consists of N sensors randomly deployed in a square area A. Each sensor and gathering point has the same radius r. And we assume the mobile sensor network has the following character:

• All sensors’ movement accord with the Community-based Mobility model [15], which can be described as follows: in the community-based mobility model, the whole network area A consists of a gathering place (e.g., in reality it can be a market for people, or a feeding ground for animals), and some communities. Each node has one home community that it is more likely to visit than other places, and for each community there are a number of nodes that have it as home community. Each node selects a destination and moves to it at a selected speed v (v_min, v_max), and then repeats the process. The destination is selected such that if a node is a home community, there is a high probability that it will go to the gathering place, of course it is also possible for the node to go to other places); and if it is away from home, it is very likely that the node will return home. The mobility of every mobile node follows the process described above and is mutually independent each other, as shown in Figure 1.

• The sink node is located at the gathering place. When the sink node is immobile, we assume that its location is known to all sensor nodes.

• Through either GPS (Global Positioning System) or other GPS-less technique such as those described in [16–18], each sensor node can compute its physical position.

3.2. Message Replica Number Calculation

To solve the performance problem that results from the fixed replica number in quota-based protocols, DRADG dynamically decides the replica number of each data message based on the distance between the sensor which generates the message and the sink node. We assume that each message head includes a field of integer type that keeps its replica ticket. The value of ticket denotes the upper bound of a message replica number.

Take node i, denoted as n_i, for an example. When n_i generates a new message M and just has an appropriate neighbor node for the next hop, it sets the ticket of M according to the following Equation 1:

3.3. Node Delivery Probability Calculation

In DRADG, each node calculates its delivery probability in accordance to its frequency of meeting with the sink node (i.e., the frequency that the node moves into the communication range of the sink node and can directly communicate with it), and forwards data messages to nodes with high delivery probability in order to further enhance the data gathering performance. The delivery probability of a node indicates the possibility that the node can directly deliver data messages to the sink node. Let P_i denote the delivery probability of n_i. Due to the node mobility feature, the delivery probability varies with the change of the node’s activities, so each node needs to calculate the delivery probability periodically and broadcast the value to its neighbors through hello messages.

In the real world, the activities of mobile objects (e.g., people, vehicles or animals) usually show remarkable regularity and predictability [19], so we can predict the meeting probability of a mobile node within a future period of time based on the historic meeting records of the node. As to any node, e.g., n_i, it maintains a timer with a timeout interval of τ, records its meeting times with the sink node in the latest interval of τ, denoted as Num_i. Then the meeting frequency of n_i in the most recent interval of τ, denoted as freq_i, can be computed by Equation 2 as follows:

In Equation 3, the exponentially weighted moving average places an emphasis proportional to α on the most recent interval τ.

3.4. Data Delivery Algorithm

By receiving hello messages, each node maintains a dynamic neighbor list in which it can acquire the delivery probability of every neighbor within its communication range. Take n_i for example, let it have a data message M need to delivery, and its neighbor set be ∑ = {Ψz | 1 ≤ z ≤ Z}, where Z is the neighbor number of n_i. Firstly n_i looks for the neighbor with a highest delivery probability, denoted as n_m, in set ∑.

If the delivery probability of n_m is greater than that of n_i, then n_m is just regarded as the next hop; or else, there is no proper next hop at present, and the routing algorithm ends. Secondly, n_i checks whether the ticket of M, denoted as ticket_M, is equal to 1. If so, then n_i directly transmits M to n_m, routing decision completes. Otherwise, i.e., ticket_M ≥ 2, n_i generates a replica M′ for message M, and set ticket_M′ as ⌊ticket_M/2⌋. Node i forwards M′ to n_m. At last, n_i updates ticket_M as ⌈ticket_M/2⌉ and then puts M into its routing queue. Detailed pseudo-code is shown in Figure 2.

3.5. Queue Management

Due to the limited buffer size of each node in a DTMSN, the buffer queue management would greatly influence the transmission performance. In DRADG, the ticket indicates how many replicas are allowed to be propagated, and the survival time shows how long a certain message has existed in the network. Therefore the ticket and survival time together denote the importance of a message, and the queue management is just based on the two parameters.

Messages are sorted in the routing queue based on a decreasing order of their tickets. For those with the same ticket value, they are further sorted according to an increasing order of survival time. Thus messages with larger tickets and shorter survival time are closer to the top of the queue, and can be transmitted with higher priorities. Moreover, messages will be dropped in the following two occasions: (a) when a message arrives and the queue is full, it is compared with that message at the end of the queue, and the one with less ticket is dropped among them. If the ticket values of the two messages are equal, then the one with a longer survival time is dropped; (b) whenever one message’s survival time is longer than the delay tolerance of the network, it is dropped to avoid unnecessary resource consumption.

4.1. Impact of Message Generation Rate

In this section, we vary the data generation rate in order to evaluate the performance of the four protocols under different transmission loads. As the date generation rate varies from 0.01 to 0.1 message/s, the performance of these protocols is as shown in Figure 3.

From Figure 3(a) we can see that all the four protocols achieve very high performance and their data delivery rates are close when the data generation rate is very low. However, as the data message generation rate goes up, the performance of the epidemic protocol decreases dramatically. This is due to MAC layer collision and rapid exhaustion of the limited network resources resulting from forwarding a tremendous amount of copies in epidemic routing. By using the fixed message replica number, which effectively limits the transmission overhead, Spray-and-Wait shows better performance than epidemic routing. In addition, we find that FAD outperforms Spray-and-Wait and the epidemic protocol as to the data delivery ratio. As the transmission load increases, its performance descends gradually since it is generating very many copies in this protocol. In general, DRADG achieves better performances than FAD, Spray-and-Wait and epidemic protocols, though its performance slowly decreases as the data generation ratio increases. The reason is that DRADG has less resource demands and can deal with high transmission loads by efficiently reducing the number of redundant data message replicas.

As shown in Figure 3(b), the average delivery delays of all protocols go up when the data generation rate increases. Obviously, the delivery delay of epidemic routing has the fastest speed increase among the four protocols. Because data messages with single-quota are not forwarded until a direct encounter with the respective destinations, Spray-and-Wait routing has higher delivery delay compared with the other three protocols in most cases. It can clearly be seen that our proposed DRADG routing has the shortest delivery delay among all protocols, because it efficiently cut down communication overhead as well as properly chooses next hop based on nodes’ delivery probabilities.

4.2. Impact of Buffer Size

To evaluate the impact of buffer space on the performance, we vary the buffer size from 50 to 250 messages and get the delivery ratios and average delay of four protocols (see Figure 4). From Figure 4(a), we find that the data delivery ratio of all evaluated protocols increases as the buffer size increases, which shows the node buffer size has a remarkable influence on the performance of the multiple copy delivery protocols. Epidemic protocol is more sensitive to the buffer size compared to the others because it generates many redundant messages so that needs much more buffer space. Due to the fact that DRADG generates much less message replicas than the epidemic, FAD and Spray-and-Wait protocols, it needs less amount of buffer space. Therefore, DRADG outperforms the other three protocols most of the time. In Figure 4(b), it can be seen that the average delivery delays of all four protocols show an incremental trend when the node buffer size increases. The reason is that larger node buffer size leads to more data message exchange between nodes, so the chance of network congestion also increases.

4.3. Impact of Node Density

The connectivity of DTMSN is closely related to the density of sensor nodes. The following experiments show the network performance of the four protocols with different sensor node densities. As shown in Figure 5(a), the epidemic protocol almost achieves the upper bound of the data delivery ratio when the node density is very low, since low node density means low transmission load and a small amount of wireless collisions. As the node density increases, the number of message copies increases dramatically in epidemic routing, which results in an increasing number of collisions and the reduction of the data delivery ratio. FAD shows a slightly better data delivery ratio than DRADG when the node density is very low. This is due to poor connectivity resulting from very low node density, which influences the performance of DRADG. With the increment of node density, the connectivity of the network is enhanced, and thus the performance of DRADG improves rapidly. When the node number reaches 300, DRADG outperforms the other three protocols. As far as the performance of FAD and Spray-and-Wait are concerned, when the node density is high, both of the protocols will generate large numbers of message copies, which expends the limited resources of bandwidth and buffer quickly and results in the decrease of their performance.

In Figure 5(b), we can find that the delivery delay of DRADG reduces as the node density is increasing in the initial stage, because its performance is improved as the network connectivity is enhanced, but the delay of DRADG begins to go up due to the increasing communication overhead when the node number is more than 250. The delivery delays of the other three protocols show sustained trends with the increase of the node density. The reason is that the three protocols above have very high demand for network resources, and an increase of the node density aggravates the situation. Of course, epidemic routing has the fastest increase speed of the delivery delay among all four protocols.

4.4. Data Traffic Overhead

To evaluate the traffic overhead of the protocols, we use the number of data messages generated per second, which is a summation of individual message-hops [20]. For example, if a data message is forwarded five hops, the message overhead is counted as five message-hops. From Figure 6, we can see the number of messages generated by each of the four protocols increases as the data generation rate increases. However, the increase trends are very different from each other. The overhead of the epidemic protocol increases fastest among all protocols, and the traffic overhead of FAD is obviously higher than that of DRADG and Spray-and-Wait, which means FAD generates too many messages copies though it achieves high data delivery ratio. Due to its effective reduction of the number of message copies and proper selection of next hop nodes, we can clearly find that the traffic overhead of DRADG is the lowest in the four protocols.

4.5. Network Life

The network life is an important assessment criterion of a protocol from the aspect of total energy consumption. The experiments show the network lifetime of the four protocols, and the results are described in Figures 7 and 8. We assume that the energy of the sink node is unlimited, and the initial energy of each sensor is 10 J. The energy needed in each transmission and receiving action is as specified in [21]. We consider the mobile sensor network dead according to the two scenarios as follows. Scenario 1: the network dies when any one of all sensor nodes depletes its energy; scenario 2: the network life ends when over a half of all sensor nodes deplete their energy.

From Figure 7, we can see that DRADG protocol achieves the longest network lifetime, since it makes use of a self-adapting algorithm to cut down the redundant replicas of messages, i.e., reduce the consumption of nodes’ energy, and thus much energy can be saved. Since sending and receiving too many messages copies expends too much energy, the network lifetime of the epidemic protocol is the shortest among the four protocols. Moreover, we also see that Spray-and-Wait has much longer network life than FAD. The reason is that, Spray-and-Wait adopts fixed message copy number transmission scheme, thus it can efficiently limit communication overhead. Therefore, the total energy consumption of DRADG is much less than the Spray-and-Wait, FAD and epidemic protocols, which demonstrates the advantage of our proposed protocol in the aspect of economizing energy.

Figure 8 shows the network life of the four protocols under scenario 2. We can find that the network life values of all four protocols under scenario 2 go up significantly compared with the corresponding values in scenario 1. However, the size relationships of the network life values among these protocols remain unchanged. It can be clearly seen that the network life of DRADG protocol is still longest in all schemes and the network life of Spray-and-Wait is much longer than that of the FAD and epidemic protocols. To achieve a high data delivery ratio, FAD routing needs to generate and transfer a mass of data message copies, so its energy consumption is also very high. Similarly, the epidemic scheme has the shortest network life among the four protocols because of its enormous demand for the network resources. In a word, the above discussions, under both scenario 1 and 2, show that our proposed DRADG scheme clearly outperforms the Spray-and-Wait, FAD and epidemic protocols from the point of view of energy savings.