Lightweight Reprogramming and Energy Balancing in Wireless Sensor Networks

Abstract

Reprogramming in wireless sensor networks is important and challenged by the dynamic environment and its own characteristic, frequently sleeping. Although there has existed various approaches, they still suffer from message control redundancy and energy balancing issues. In this paper, we consider the problem of lightweight code distribution and energy balancing in wireless sensor networks by utilizing shared requests to reduce redundant control messages. Additionally, our contribution is enhanced by various solutions, such as multisegment advertisement strategy and edge-oriented strategy. Through analysis and evaluation sections, we confirm that our protocol does not only help to reduce update completion time by 1/3 compared with the Deluge protocol, but also significantly decreases redundant control messages and balances energy consumption among nodes in the updating process.

1. Introduction

Wireless sensor networks (WSNs) are becoming increasingly necessary in various fields due to the importance of sensor applications such as monitoring systems and warning systems [1]. To achieve useful practice, a WSN must have the ability of operating correctly for a long period of time. This introduces several challenges. Firstly, the dynamic environment changing requires WSNs to adapt and rise to the need for reliable reprogramming of all sensor nodes [2, 3]. To be more specific, nodes in a WSN should be frequently reconfigured with new updating code which is originated from one or more sinks [4]. However, due to nature of energy constraints of WSNs, the code updating process must be optimized. Secondly, a WSN can operate incorrectly as if some nodes die out. Therefore, it should keep energy balancing among sensor nodes to avoid those nodes running out of energy [5].

To address the above difficulties, various code distribution protocols have been proposed. Some approaches are for special sensors such as Sprinkler [6] and GARUDA [7]. In these protocols, at the first step, based on the location information of each sensor, some sensor nodes are selected to receive the update information to achieve energy optimization. Then, in the next step, these nodes spread out that information to all nodes. However, the location information is not commonly supported for sensors. Therefore, most of the available approaches are focused for normal sensors. Traditionally, reprogramming is done within the range of a sink in Mica-2 mode [8] in which a node keeps an update information and other nodes in the range of that node. However, this method seems to be impractical due to the nature of WSN spreading over a large area. Therefore, the initial version of multihop reprogramming was presented by Kulik et al. in 2002. According to this protocol, Kulik et al. took advantage of the advertisement-request-data model in an epidemic algorithm in SPIN protocol [9]. A node after receiving the full version of update information will become a sender to its neighbors. However, overlapping among the transmission range of sensors results in a control message redundancy problem at over 95%. To overcome this obstacle, the Trickle [10] protocol is proposed in 2004 by using SRM-like suppression mechanism. Later, Hui and Culler integrated Trickle into the Deluge protocol [11]. Because of the large amount of update information, therefore, start from sink, this information is divided into multiple parts. Each part of the message, then, used advertisement-request-data model to spread to all sensor nodes. It is estimated as a highly reliable, optimized, code-dissemination protocol. Although providing various methods of suppressing request messages, Deluge still generates too much unnecessary advertise messages due to frequently sending them. Additionally, the performance analysis section later indicates that the update completion time of the whole network increases exponentially while the size of the network gets bigger. As a result, it does not satisfy the energy constraints in WSNs. Moreover, previous approaches did not consider the energy balancing problem. Nodes in the core of a network spend much more energy than nodes on the edge in the activities of sending and receiving packets. For instance, the result in the Deluge paper shows that within the interference range of a node at the edge a much larger number of messages were sent than that of a node at the core.

The above obstacles challenge not only Deluge, but also various next generations of this algorithm, such as MNP [12], Freshet [13], SYNAPSE++ [14], and Typhoon [15]. Although each paper proposes a solution for a new problem, it still suffers from the above problems of the foundation transmission model (advertise-profile-request-data). Take the Freshet protocol as the typical example. This protocol includes three phases: warming phase, distribution phase, and quiescent phase. The idea here is reducing energy consumption by providing a warning phase. Once an update version for sensor nodes is available, the sink will send the informing message to all nodes. Most of nodes which are far from the sink are put into sleep state. Only these nodes which are near the sender will be active in order to receive the update information. The next two phases are inherited from the Deluge protocol. Take another example, the solution in MNP protocol is trying to reduce to collision and hidden terminal by selecting a suitable sleeping schedule among sensor nodes. A node is in the sleep mode as if it receives an unnecessary message. These protocols only focus on sleep schedule of nodes but do not focus on the methods to reduce the redundant messages.

To cope with the above challenges, then, we introduce a protocol named Dsare in which we provide various mechanisms to minimize redundant control messages and quickly distribute code by proposing a new code dissemination model. Afterwards, the contribution is enhanced by providing the edge-oriented strategy to cope with the energy balancing problem. Additionally, an analysis for update completion time and a variety of simulation results concretely confirms the advantages of our solution over the Deluge protocol. Accordingly, the time required to finish the update process is reduced by 1/3, compared with that of Deluge, and there is a dramatic reduction in the proportion of control message redundancy, at around 80% in Deluge and lower than 25% in the Dsare protocol.

The rest of this paper is categorized into three sections. Section 2 firstly describes the basic model of our protocol. Then, some details of our proposed transmission model and enhancements are presented. The next section analyzes the update completion time of our protocol, Dsare. The last section covers the diversity of results of our protocol in comparison with the Deluge protocol and the specific characteristics of Dsare.

2. Code Dissemination Protocol

2.1. Transmission Model

Dsare is an epidemic protocol and follows the advertise-request-data model [11]. In this protocol, utilizing the broadcast medium, all the packets are shared, and especially the shared request messages are seriously considered. First of all, the basic form of the Dsare protocol is illustrated as in Figure 1. The model follows the advertise-request-data model. However, the shared request messages help to reduce the large number of advertise messages. In detail, initially, a sink with a new version image that acts as the first sender broadcasts the new image information to all sensor nodes within its range. After one-hop-count neighbors of the sink receive the advertise message, they decide to send a request message back to the originator. Then, the sender broadcasts a new version image to all of its neighbors. At the same time, two-hop-count neighbors of the sender overhear that request message and estimate an interval before sending a request back to the one-hop-count neighbor to achieve a new version image. After obtaining new data, a one-hop-count neighbor becomes a new sender. And the process is repeated until all nodes are updated completely.

Figure 1

Basic model of Dsare protocol.

At this intuitive version of the Dsare protocol, request messages are shared at the maximum to minimize unnecessary control messages. By overhearing request messages, the two-hop-count neighbors know one-hop-count nodes are going to obtain new data messages. Therefore, it sends a request back to the one-hop-count nodes without receiving an advertise message from that node after a predetermined interval of time. As a result, advertisement messages are mostly saved.

Clearly, the basic form of Dsare is relatively simple. And some obstacles do challenge it. One of them is request missing, which is the result of the difference between the rate of distributed request messages and that of data messages and the loss link. Another is the requirement of a suitable method to calculate the waiting interval at the two-hop-count neighbor. Therefore, in the next section, various critical issues in WSNs are considered seriously to enhance overall performance of the protocol. Firstly, it minimizes advertise and request messages. Secondly, it is about energy balancing. Thirdly, link fails are also considered.

2.2. Multisegment Advertisement

If only the above basic model is applied, a new problem is appearing that a node sends request message to obtain the data while all of its neighbors do not have the new update information due to the difference between the rate of disseminating request messages and rate of distributing data. For instance, once there is an error while transmitting data, a node is unable to obtain data. But, at the same time, one of its neighbors start to send request message to this node while it is not ready to send data. Therefore, in order to eliminate this issue, Dsare applies a strategy to control the schedule of advertise and request messages. To be more specific, all nodes that are $k\mathrm{\ast }\text{BOUND}$ -hop-count far from the sink have to broadcast an advertise message (with $k=\mathrm{0,1},2,\dots$ and BOUND is a predetermined number). Nodes that are ( $k\mathrm{\ast }\text{BOUND}+\mathrm{1}$ )-hop-count far from the sink should only send a request message after receiving an advertise message instead of receiving the previous node's request message and calculating the waiting time. Therefore, the mentioned difference between two rates is no longer relayed to the next BOUND-hop-count nodes.

2.3. Edge-Oriented Strategy

A new problem is that some nodes have to spend much of the energy for requesting and data sending while other nodes do not. Then, these nodes deplete quickly. Therefore, in response to energy balancing, Dsare also applies an edge-oriented strategy, which is a strategy that chooses a sender among the various senders that broadcast new image information to that node. Accordingly, each node in the network estimates the number of neighbors by overhearing request and advertise messages sent by its neighbors. Then, this information is passed to its neighbors through either advertise or request messages. A node calculates the density of the local area based on that data. Finally, the node then selects the best sender with the lowest density value.

2.4. The Protocol

A node running the Dsare protocol transits among three states: MAINTAIN, REQ, and TRANS. All nodes follow a set of rules in response to incoming events. An update image is segmented into multiple pages, as in the Deluge paper.

2.4.1. Maintenance Phase

A node is in the MAINTAIN state when it responds, informing of the availability of a new version, or is in the process of receiving a new image. For the former purpose, a node must be the sink or satisfy the condition of a multisegment advertisement strategy, or not send any request message, right after it receives a page of the new version image. Then, after an interval time $T_{\text{adv}}$ expired, the node calls an advertise message function

$$\begin{array}{cc}& T_{\text{adv}}=\phi +{\tau }_r,\end{array}$$

(1)

where φ is denoted as a predetermined interval and ${\tau }_r$ is denoted as a random time interval to avoid collision. After sending advertise message, the state of the node is transited into REQ.

For the latter one, if a node is in the process of receiving a data message, it is transited to a MAINTAIN state.

2.4.2. Request Phase

A node is in REQ state when it needs to update a new version message. At that moment, that node has just received a new advertise or request message with version ${\varnothing }^{\prime }>\varnothing$ , which is the current version of this node, and the incoming page ${\gamma }^{\prime }>\gamma$ , which is the highest updated page of this node. Whenever a node updates a page, it will send a request to update the next page of the image.

Handling the request function is the most complicated function in this program. There are two options. One is after obtaining a request message; if this node has a new version image, it sends data back and transits the state to TRANS.

In other case, this node sends the request message back as if the number of hop counts from this node to the sink is different from the ( $\text{BOUND}\mathrm{\ast }k+\mathrm{1}$ ) hop count.

A request is sent back after the interval:

$$\begin{array}{cc}& T_{\text{req}}=\text{CONS}{\text{T}}_{\text{REQTIME}}+{\tau }_r.\end{array}$$

(2)

However, the interval for the request to be sent again if the first request failed must be different to take advantage of multiple neighbors in WSNs:

$$\begin{array}{cc}& T_{\omega }=\omega +{\tau }_r.\end{array}$$

(3)

2.4.3. Transition Phase

This state is responsible for broadcasting new version image packets from a sender to its neighbors. Whenever a node receives a data packet, if this node is not updated yet, it should receive all data messages, regardless of its current state.

3. Performance Analysis

To have an objective point of view about the performance of our protocol, this section focuses on analyzing the update completion time of Deluge and Dsare by using mathematical calculation.

Firstly, we consider the Deluge algorithm by taking into account node B and node C. B and C are i-hop-count and (i + 1)-hop-count nodes far from the source, respectively. C is B's neighbor. Figure 2 illustrates the activities of sending and receiving messages of two nodes from the time a node receives an advertise message until that node receives the new version of the message. $T_i$ and $T_{i+1}$ are denoted as the intervals before receiving the new version profile messages at nodes B and C, respectively. $T_l$ is the shortest interval in which it is set whenever a node has a different version with at least one of its neighbors. According to the Deluge algorithm,

$$\begin{array}{cc}& T_i={T_l}^{i+\mathrm{1}},\\ T_{i+\mathrm{1}}={T_l}^{i+\mathrm{2}}.\end{array}$$

(4)

Figure 2

Procedure of sending and receiving message at nodes running (a) Deluge protocol and (b) Dsare protocol.

Assume that all messages are 100% successfully received. $\Delta t$ represents the interval of successfully receiving data messages between 2 neighbors. Then,

$$\begin{array}{cc}& \Delta t\approx T_{i+\mathrm{1}}={T_l}^{i+\mathrm{2}}.\end{array}$$

(5)

According to (5) above, if $T_l$ is considered a constant value, $\Delta t$ depends largely on the distance between this node and the sink. A node (e.g., node C) is updated for a longer time compared to its sender (node B) right before the value of i gets higher. Then, the completion time of the whole network increases. In other words, it suffers scalability and energy-constrained problems.

In the remainder of this section, we discuss the update completion time of a node running the Dsare protocol.

Figure 2(b) describes the schedule of sending and receiving messages in a Dsare node. Message 2 can be an advertise message or an overhear message.

If we consider the normal case, as mentioned above, in which there is no request miss, then nodes B and C are quickly updated:

$$\begin{array}{cc}& \Delta t\approx T_{\text{req}}.\end{array}$$

(6)

This also means that the update completion time for the whole network is much smaller in the case of Dsare when comparing (5) and (6). However, we consider more deeply, where node B requests failed n times before being updated,

$$\begin{array}{cc}& \Delta t\approx T_{\text{req}}+n\mathrm{\ast }{T}_{\omega }.\end{array}$$

(7)

At the node D h-hop count far from node B,

$$\begin{array}{cc}& \Delta t\approx T_{\text{req}}+{\displaystyle \sum }n\mathrm{\ast }{T}_{\omega }.\end{array}$$

(8)

From (2), (3), and (8), $\Delta t$ depends largely on the number of rerequests. That is the reason why multisegment advertisement strategies, along with BOUND values, are taken into account to limit the upper bound of $\Delta t$ . According to the multisegment advertisement strategy, $\Delta t$ is reset to 0 each time the condition of the strategy is satisfied.

However, one of the specific weak points of this protocol, or the weak point of the model advertise-request-data in general, is that there is one advertise message along with the direction from the sender to the receiver. Although a node can take advantage of multiple neighbors to enhance this weak point, there could still be losses in the update process, in the worst case.

4. Performance Evaluation

This section focuses on measuring the overall performance of our protocol by simulating it on the ContikiOS and Cooja simulator and comparing the results with those of the Deluge protocol. To achieve this objective, we consider various metrics and use them as the main characteristics to evaluate our protocol. Some of them were already used in the Deluge paper, such as completion reliability, completion time, and energy consumption. Some new metrics are also exploited:

• (i)

Number of control messages: in the Deluge case, it includes advertise, profile, and request messages, whereas, in the Dsare case, it includes advertise and request messages.

(ii)

Number of congestion points $N_{\mathrm{co}}$ : it is the number of connection between 2 nodes in which collision occurs.

(iii)

Proportion of redundant control messages: It is equal to the division of the number of redundant message $N_{\text{dup}}$ by the total number of generated message at a node, where

$$\begin{array}{cc}& N_{\text{dup}}={\displaystyle \sum }\text{all}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{messages}-{\displaystyle \sum }{N}_{\text{ne}}-{\displaystyle \sum }{N}_{\mathrm{co}},\end{array}$$

(9)

 

where $N_{\text{ne}}$ is the necessary message to transmit a page of data message. Consider transmission from node A to node B in the Deluge protocol:

$$\begin{array}{l}{N}_{\text{ne}}=\text{data}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{message}+\mathrm{2}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{advertise}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{message}\\ +\mathrm{1}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{request}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{message}+\mathrm{1}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{profile}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{message}.\end{array}$$

(10)

 

Now consider it in the Dsare protocol:

$$\begin{array}{l}{\displaystyle \sum }{N}_{\text{ne}}={\displaystyle \sum }\text{data}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{message}+{\displaystyle \sum }\text{advertise}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{message}\\ +{\displaystyle \sum }_{\text{nodes}}\mathrm{1}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{request}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{message}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{per}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{node}.\end{array}$$

(11)

(iv)

Energy balancing: the balance among the total energy consumption of each node.

4.1. Simulation Environment

4.1.1. ContikiOS and Cooja

We rely on the Contiki operating system (OS) [16] to evaluate the overall performance of our protocol. Each virtual sensor is installed in this OS. C language is used as the primary language to build this OS. Applications are written by this language and are called through an interface of the Cooja simulator. This simulator is a discrete-event network simulator and is compiled directly from the ContikiOS.

4.1.2. Parameter Configuration

In each simulation, nodes are located in a square network $N\times N$ ( $N\in [\mathrm{2,20}]$ ). A sink is located at the corner of the network. At the initial stage, all nodes are powered up and contain image version 0, except the sink node that has version 1. Each image version contains just one page [11]. Each page includes 8 packets. Each packet is 64 bytes. Thus, the total size of the image is 500 bytes. After a random interval time Tr, the sink node broadcasts the new version information to start the update process. Each node is configured with BOUND = 4, CONST_REQTIME = 4, Tr = 0.5, λ = 4, $\omega =8$ .

4.2. Simulation Results

This section briefly describes the various results of the Dsare protocol and makes some comparisons with the Deluge protocol. These results are categorized into two groups. One is proving the efficiency of our protocol compared with that of the Deluge protocol. The other illustrates specific characteristics of Dsare.

For the first group, we investigate two aspects. One is the interval time to finish the updating process in all sensor nodes. Another is the cost for the updating process.

4.2.1. Time to Complete

Figure 3 illustrates the completion time of the Deluge and the Dsare protocol in a square network $N\mathrm{\ast }N$ ( $N\in [\mathrm{2,20}]$ ). Node density is kept constant at 10 meters apart. According to this line graph, the figures for both protocols gradually increase. The figures for Dsare are around 2/3 of those for Deluge. At the network scale 20 × 20, the completion time for the Deluge protocol is approximately 290 seconds, whereas for Dsare it is just around 200 seconds.

Figure 3

Comparison of completion time between Dsare and Deluge protocol with different network diameter.

Next, we compare the number of updated nodes between the above protocols in a specific topology at different periods. In this case, we choose the topology $20\mathrm{\ast }20$ . Figure 4 shows that Dsare has a trend to spread from nodes at the border to the center node.

Figure 4

Comparison of updated nodes between Dsare and Deluge with different network parameters.

4.2.2. Cost of Updating Process

From the above comparison, it is easy to recognize that the Dsare protocol helps sensor nodes update more quickly than the Deluge protocol does.

However, the efficiency of the Dsare protocol also depends on the cost of paying for the updating process. This cost is considered the compound of the number of control messages, the number of redundant messages, and the number of collisions that occur in the network.

The first considered attribute is the number of control messages. The method of calculating this number is mentioned in the previous section, to compare 2 algorithms in square topologies with BOUND = 2. According to Figure 5, the figure for Deluge dramatically increases whereas the figure for the Dsare protocol gradually rises. When the diameter of the network is small, the difference between the two figures is around 8 times. However, when the diameter enlarges, the number of control message for Deluge reaches 10070 and is more than 13 times that of Dsare.

Figure 5

Comparison of number of control messages between Dsare and Deluge protocol with different network diameters.

As mentioned, the proportion of collisions is also an important characteristic to contribute to the efficiency of a protocol. Motivated from the previous results, we took various implementations and obtained some achievements, as shown in Figure 7. Obviously, the number of collisions that occurs in a network increases with the rise in the size of the network. However, the figure for Dsare is around 60%, compared with that of Deluge.

After comparing the number of control messages between the two protocols, we look deeper into the proportion of control message redundancy and data message collision. Figure 6 shows that while the proportion of Deluge redundant control messages is relatively stable at around 80%, the figure for the Dsare protocol is just below 20% and has a downward trend when the size of the network gets bigger.

Figure 6

Comparing proportion of redundant control messages between Dsare and Deluge protocol with different network diameters.

Figure 7

Comparing the number of collision points between Dsare and Deluge protocol with different network parameters.

For the second group, Dsare shows its behavior through multiple aspects. We decide to choose the BOUND value and energy balancing as the most typical characteristics of our protocol.

Firstly, we consider the different behaviors of the Dsare protocol with the different values of BOUND. When implementing the Dsare protocol in the basic mode (or BOUND = ∞), we found that, with $N=20$ , some of the nodes furthest from the sink could not be updated. It is the result of different distribution rates between the request messages and the data messages. Additionally, the difference leads to the rise in the number of request misses. As described in Figure 8, this number is around 50 when 100 nodes are completely updated.

Figure 8

Comparison number of request misses between Dsare protocol with various values of BOUND and Deluge protocol.

However, when the nodes near the sink are updated, the mentioned difference shows its affection by increasing the number of request misses. The number of request misses is different with a different value for BOUND. This has a trend to be stable when the Dsare protocol applies a multisegment advertisement strategy. At the time that 350 nodes are updated, this number is more than 250 with BOUND = 8 and just over 100 with $\text{BOUND}=\mathrm{4}$ . In contrast, the figures for $\text{BOUND}\to \infty$ are soaring to 500 at the same time. Furthermore, this figure is better than that of the Deluge protocol with the small value of BOUND.

4.2.3. Energy Balancing

To evaluate two protocols in terms of energy balancing, various simulators take place in a square topology $10\mathrm{\ast }10$ . Energy balancing is reflected in the balance among the total energy consumption of each node. The total energy consumption depends on four main aspects: full CPU energy consumption, reduced power CPU consumption, radio receive, and transmit power consumption. However, the three former gradually increase due to the assumption that all nodes in a network stay awake until finishing the update process. Then, the difference in terms of power consumption between two protocols depends on the difference in transmitted power consumption between those protocols. This parameter depends on the total radio transmit time; thus, we calculate the radio transmit time of 100 nodes when sequentially applying two code distribution protocols. The result is illustrated in Figure 9. Obviously, nodes using the Dsare protocol show their energy balance as better than that of Deluge.

Figure 9

Comparison of energy balancing between two protocols in terms of radio transmit time in topology $10\mathrm{\ast }10$ .

5. Conclusion

In this paper, we presented various improvements to address control message redundancy and energy balancing problems in reprogramming wireless sensor networks. By utilizing shared requests, applying multisegment advertisement strategy and edge-oriented strategy, and, later, through analyzing various simulations, we experienced that our protocol update completion time equals 2/3 that of the Deluge protocol, with the number of required messages reduced by more than 10 times. The energy for the updating process is balanced among nodes. Furthermore, we addressed the emerging problem as if our protocol was applied. It is the different distributed rate between the request message and the data message.