Data Collection Method for Mobile Sensor Networks Based on the Theory of Thermal Fields

3.1. Local Maxima Problem

To accommodate temperature transfer function in the network scenario, we must solve the problem of local maxima to ensure that forwarding by the warmest path will always end up in the data sink. When ξ > 1, the probability of local maxima is ≥0, therefore we modify the original function and use ξ_NORM ∈ 〈0, 1). Maximum temperature is in the data sink, φ_MAX, and the temperature of every non-sink node is calculated as follows:

The data sinks are thermal sources and all other sensor nodes are conducting temperature depending on their own properties. The only condition which must be kept when forwarding the packets in the network, is that there exists path from any node to any sink in the network and the temperature values of all nodes along the path are strictly increasing towards the data sink. This is accomplished by normalizing ξ, ξ_NORM ∈ 〈0, 1) (see Theorem 1).

Theorem 1. Node N_i is non-sink node connected to the network and there exists at least one path from node N_i to the sink. If ξ_NORM ∈ 〈0, 1) then there exists a neighbor of N_i, N_j, and φ_i < φ_j.

Proof. By contradiction. Assume that there is no such neighbor having φ_i < φ_j, so for every neighbor N_j, φ_i ≥ φ_j. Then, from the iterative calculation of the temperature, φ_i, we can write:

3.2. Temperature Calculation in Practice

Figure 2 shows practical calculation of the node’s temperature. Assume that node X has neighbors A, B, C, D and E and knows their temperatures (i.e., φ_A, φ_B, φ_C, φ_D and φ_E). Then, node X creates a list of neighbors sorted descending by their temperature. Based on the Algorithm 1, the node’s temperature is calculated. From the Figures 2(b) and 2(c) is clear that node’s temperature value and also number of alternative paths varies with the node’s own thermal conductivity value ξ_XNORM. In case of high thermal conductivity value, the calculation stops after two steps and only first two neighbors (C and B) are contributing to the node’s own temperature value and only these two neighbors are potential data forwarders (column P shows priority of the next hop forwarder). In case of low thermal conductivity value, ξ_XNORM = 0.3, the node’s temperature calculation consists of three steps. The final temperature value is much lower, because of node’s low thermal conductivity value. There are three neighbors contributing to the temperature of node X. Thus, more alternative paths is available when one of those neighbors is disconnected. From the Equation (1) we can see that temperature of the node depends on the two factors (virtual physical attributes), namely on the temperature of the neighbors and as previously noted, on the node’s thermal conductivity value. The former one enables end-to-end path selection and the latter one depends on the characteristics of node. The characteristics of node could be mapped to node’s energy, location, importance of generated data, position in hierarchy (e.g., clusterhead), priority, transmission power or any other.

3.3. Distribution Function and Conductivity Value

Temperature transfer formula considers several dimensions of network in one value and we can examine its behavior by simplification. At first, this formula considers distance from the sink. This can be clearly shown by setting thermal conductivity a constant value for all sensor nodes (ξ₁ = ξ_i = const). Another dimension is the number of neighbors, thus density of the network. It can be shown that the more neighbors with the higher temperature, the higher temperature of the node itself. When conductivity value is very close to zero (ξ = const ≈ 0), the density of the network has very significant impact on the temperature value. Vice versa, if the thermal conductivity value is close to 1 (ξ = const ≈ 1), the distance from the data sink (number of hops) has significant impact on the temperature. Thus when the sensor nodes, which are closer to the data sink, are in good conditions (their conductivity values are close to 1), then the shortest path is preferred as the most optimal one. When those nodes are in bad conditions (their conductivity values are close to 0), more alternative paths can be found (for detailed example see description of Figure 2), thus the probability of data delivery is increased through path diversity.

This behavior can have significant impact on the network performance when thermal conductivity value is mapped to the real characteristics of node. The thermal conductivity value ξ can be considered as the node’s quality factor, which directly influences the temperature of node. In general, the better are the characteristics of the node, the higher is the conductivity value.

One example of mapping the thermal conductivity value to the characteristics of node is prioritization. We can assign high value (e.g., ξ = 0.9) to those nodes, which are preferred forwarders (high priority) and low conductivity value (e.g., ξ = 0.2) to the nodes which should be used for data forwarding only if necessary (low priority). Those nodes with higher thermal conductivity values are strongly influencing the temperature values of their direct neighbors, thus, are more likely the next hop forwarders for those neighbors.

Another interesting example is mapping the thermal conductivity value to the transmission power of the node. By mapping the nodes with high transmission power to high conductivity values, those nodes will be likely used as next hop forwarders. Vice versa, the nodes with low transmission power could be mapped to low conductivity values, thus, having more potential next hop forwarders (refer to Figure 2(c)). This is especially important when the node with mobility has low transmission radius (due to low transmission power) and the probability of disconnection with other nodes with mobility is high.

4.1. Discovery and Forwarding Phases

Discovery phase is necessary for proper decision of the next forwarder of data. Network discovery is initialized by the sink node, which periodically sends the information about its temperature φ_SINK, which is the maximum temperature and it is always constant. All neighboring sensor nodes calculate (based on the previously described Algorithm 1) own temperature and send this information to their direct neighbors. By this periodical one hop beacon exchange, the overall network is kept in the actual state. Every sensor node keeps small routing table of its neighbors with their temperature values.

Forwarding phase of temperature transfer based network is very trivial. From the previous phase, where every node calculated own temperature and created table of the neighbors, sensor node knows which neighbor is having the highest temperature. That neighbor is used for data forwarding. If the node at the first place in the routing table is disconnected, the table of neighbors is updated, the own temperature is recalculated and the warmest neighbor in the refreshed table is used for forwarding. However, in order to avoid loops, only nodes with higher temperatures than is the temperature of the actual are used for forwarding.

5.1. Study on the Protocol Performance

We used previously described simulation setting and 120 sensor nodes randomly deployed within the network area. Firstly, we investigated the proposed enhancement for TEAR protocol, i.e., the minimum threshold for conductivity value mapped to the relative residual energy of the sensor node ξ_EMIN. We varied the ξ_EMIN value from 0 to 0.5 by step 0.05. When ξ_EMIN = 0, sensor node will not start own poison process. On the other hand, when ξ_EMIN = 0.5, the sensor node will start the poison process when its relative residual energy drops below 50%. Figure 3(a) shows the performance of TEAR protocol.

Clearly, the lifetime grows with increasing minimum thermal conductivity threshold ξ_EMIN, when mapped to the energy. The self-poisoning behavior makes sensor node behaving selfishly from the point that the poisoned sensor nodes cannot be used as a forwarder afterwards. Thus, after some time, many sensor nodes are poisoned and the network becomes disconnected at the network level. To model the behavior of the sensor nodes, we investigated the energetic cost of the protocol (shown in Figure 3(b)). In this case, we simulated every run until the first sensor node dissipates and calculated the ratio between spent energy by the system and delivered useful data. It can be seen that for large ξ_EMIN the cost is very high and has growing tendency. This is because the amount of delivered data is decreasing when many nodes cannot be used as forwarders. The cost function decreases for low ξ_EMIN and reaches minimum when ξ_EMIN ≈ 0.25. This is because some sensor nodes started poison process and stopped sending periodical updates (beacons) to its neighbors to save energy while there are still alternative paths for data delivery.

From the previous evaluations we found out that in order to increase lifetime of the sensor nodes, the minimum conductivity threshold value should be properly chosen. Based on our results, the sensor node should start poison process when it has remaining only 25 percent of the relative residual energy (ξ_EMIN = 0.25).

5.2. Comparative Evaluation

We compared our protocol with two other protocols designed for mobile sensor networks. AODVjr protocol is from the group of MANET protocols, which have been modified for sensor networks. Another protocol is the Epidemic routing, which is aimed for mobile sensor networks.

We implemented AODVjr, a simplified version of AODV protocol, which is aimed for sensor networks. It was originally proposed in [7] and we added support for multiple sinks according to [8], which is another modification of AODV protocol for anycast routing. AODV protocol belongs into the group of reactive protocols, thus when a node does not know the route to the destination, it broadcasts route request message and waits for reply with the route towards the destination.

Epidemic routing is protocol for mobile sensor networks. We implemented this protocol according to a protocol design description in [9]. Epidemic protocol is based on the exchange of message vectors between newly connected neighbors and then, based on the requirements, the sensor nodes exchange required messages, which they do not have in their buffers. The performance of this protocol depends on the buffer size for messages (it stores also messages of other sensor nodes) and on the repetition of the anti-entropy period, which defines how often two connected neighbors exchange their updated message vectors. Based on the results in [9], we set the buffer size of sensor node to 100 messages and re-initiation of the anti-entropy period to 10 seconds.

We implemented our proposed TEAR protocol based on the previously described design and we set the period for beacon (message carrying temperature value) to 1 second. Every sensor stores table of the actually connected neighbors with their temperatures and a time when the most recent beacon came.

5.3. Results of Comparative Evaluation

We performed extensive simulations based on the previously described settings (see Table 1). We investigated the scalability of the protocols by varying network density from 80 sensor nodes to 240 sensor nodes within the network area.

In Figure 4(a), we investigated lifetime of the sensor nodes. As defined earlier, we were interested in the dissipation of the first node, not the overall network. In this evaluation, we also show the performance of TEAR protocol with ξ_EMIN = 0.25. TEAR protocol has more than 4 times higher lifetime of the sensor node than Epidemic or AODVjr protocols in all cases, and when ξ_EMIN = 0.25, it has more than 5 times higher lifetime. Moreover, the lifetime of the TEAR protocol increased by more than 45% in average, when poison process is used.

Figure 4(b) shows control overhead on logarithmic scale. Epidemic protocol completely fails, causing significant control overhead in dense network (when 240 sensor nodes, control overhead is 65 times higher than TEAR protocol). Epidemic routing protocol exchanges message vectors when new sensor node is connected. Denser network increases probability of new connection, thus the sensor node performs exchange of message vectors more often. Moreover, all nodes are generating messages, thus every sensor node has many messages buffered. Therefore, the vector containing all buffered message identifiers is of very large size, causing overhead. Control overhead of AODVjr protocol also grows with the growing density, reaching 4 times higher values than TEAR protocol. This reflects to the issue of flooding. AODVjr protocol uses network flooding technique when requesting the route towards the data sink. TEAR protocol does not cause extra overhead in dense network.

In Figure 4(c), we compared packet delivery ratio of TEAR protocol, AODVjr and Epidemic protocol. In low density scenario, the Epidemic protocol overcomes other protocols as it stores the messages and transmits when connection becomes available. As the density of the network increases, the performance of the Epidemic protocol degrades significantly. This is caused by the buffer size. As the network density increases and all the sensor nodes are generating data, the buffer of the sensor node overflows, thus many data packets are dropped. TEAR and AODVjr protocols are fairly robust in the terms of the network density.

Poor performance of the Epidemic routing protocol in dense networks is reflected in Figure 4(d), spent energy per useful transferred data bit grows with the density. Energetic cost of AODVjr protocol slightly increase with the network density. This result is influenced by higher energy dissipation of the sensor nodes due to the previously described flooding issue resulting in high control overhead. For network with 240 sensor nodes, the AODV protocol has more than 4 times higher energetic cost than TEAR protocol.

Finally, end-to-end delay is compared in Figure 4(e). Epidemic protocol reaches very high delay by its nature. This delay is decreasing due to more frequent message exchange in dense network. AODVjr protocol has almost the same average delay as TEAR protocol when 80 sensor nodes in the network, however, it has 8 times higher end-to-end delay in very dense network (240 sensor nodes).

5.4. Discussion

From the performance of the TEAR protocol is obvious, that the exchange of temperatures between direct neighbors makes this solution very scalable and the protocol performs well regardless of the network density. Another important outcome is that the temperature is calculated without knowledge of the actual data sink. That is, the forwarding is based on anycast paradigm and if there are several data sinks in the network, the actual destination (data sink) depends on the trade-off between the distance in hops, the density towards the sink and actual residual energy of each sensor node on the path towards the data sink. Proactive behavior of our protocol design is very suitable for applications with frequent data exchange and might be ineffective in the network where only few nodes generate data or the data are generated very rarely. Another limitation of our protocol is convergence time of DAG, which depends on the period of the update message. For example, when there is sudden disconnection of data sink due to mobility of the sensor node, the temperature values of the neighbors of that data sink will drop significantly. Similarly, the neighbors of those nodes will recalculate their temperatures when received new beacon. This process will continue until all nodes with temperatures affected by that data sink update their tables and recalculate new temperature values. The overall convergence time strongly depends on the update period. In such situation, the packets are forwarded based on the outdated path, which might lead to longer paths or even packet drops due to temporal local maximum. Therefore, it is very important to properly select the update period in order to prevent temporal packet drops due to outdated paths caused by longer DAG convergence time.

6.1. Routing in Mobile Sensor Networks

There are many works related to data harvesting in MSN, however, mostly focused on delay or fault-tolerant MSN (e.g., [14,15]).

Pervasive information gathering in Mobile Sensor Networks is studied in [14]. This human oriented data collection is analyzed when flooding and optimized flooding is used. Then, new method based on two components, namely the probability of message delivery and queue management, is proposed. Data is forwarded to the neighbor only when the neighbor has higher probability of delivery. Queue management algorithm evaluates whether to drop or transmit the message based on the fault tolerance. Another interesting solution for dynamic networks with mobile sensor nodes is epidemic routing [9]. Message delivery is ensured by random pair-wise exchange of messages among mobile sensor nodes. There are three main goals for epidemic routing, such as maximizing packet delivery, minimizing message latency and also minimizing total resources consumed in message delivery. Semi-epidemic approach is explored in [16], where the probability of replication is proportional to the time of the last encounters and their frequency. Each sensor node maintains delivery predictability vector, which indicates likelihood to meet other sensors. Data collection is based on the message forwarding from the lower predictability sensor nodes to the higher predictability sensors.

Another group of communication protocols for wireless sensor networks is based on widely studied area of wireless ad-hoc networks. Robustness of the routing when nodes have mobility is one of the key goals of Mobile Ad-Hoc Network (MANET) protocols. However, limited energy, low computation capability and memory makes direct use of such protocols difficult, sometimes prohibitive. In the recent years, several MANET protocols have been simplified and adapted to sensor networks to be more suitable for energy constraint nodes with low computational capability (e.g., [7,17,18]). Ad-Hoc On Demand Vector (AODV) [19] routing protocol was adapted to sensor node’s capabilities in [7] as AODVjr. The authors show that AODVjr can reach almost the same performance as the original AODV while having much less complexity. In [18], the authors proposed Not-So-Tiny AODV (NST-AODV) protocol, which provides support for mesh sensor networks. The drawback is that it requires large memory storage.

6.2. Theory of Thermal Fields in Wireless Networks

Recently, the theory of thermal fields and other similar strategies (gradient based or scalar field routing) has been applied to wireless networks (e.g., [13,20,21]).

In [20], a potential fields’ strategy is proposed, allowing routing based on scalar value to extreme, which can be in anycast group member. It considered as the routing decision parameter density of anycast group members in the network. Anycast group consists of multiple members and every member contributes to the field of the group. Thus, the potential field of an anycast group is defined as the superposition of the potential fields of all members in this group. The packets are routed along the steepest gradient of the potential field. The steepest gradient at each node is determined by evaluating the potential values of the neighbors. That is, the link from a node to the neighbor with the highest potential value corresponds to the steepest gradient. Therefore, the nodes always compare the potential value of their neighbors and forward anycast packets to the neighbor with the highest potential value.

In another field-based protocol, HEAT [21], the similar theory is applied to wireless mesh networks, however, the temperature of node is calculated from the density of all hosts in the network. The more neighbors with higher temperature, the higher is temperature value of the forwarding node. This approach can improve the probability of packet delivery in large mesh networks. The probability is increased by routing to denser area with anycast members instead of direct routing to the closest anycast member, because in dynamic network with frequent changes, the anycast member may become unreachable by moving out of range. The drawback of HEAT protocol is that its performance depends on the pre-set heat conductivity value, which makes trade-off between density and proximity routing. Thus, it is impractical to set the value ahead, because real network might likely have areas where proximity is preferred and other parts where density might be more suitable.