Abstract
This paper presents a novel multicast routing protocol for wireless sensor networks, named Multicast tree protocol with Pruning and Energy Balancing (MPEB) to disseminate data through a layered multicast tree with high-efficiency and low-power consumption. With pruning algorithm and energy balancing algorithm, MPEB can save energy and balance load. Pruning algorithm records and maintains backup parents for each child node, and thus it can detach possible nodes from the multicast tree and turn as many nodes as possible to sleep. Energy balancing algorithm protects nodes with low power from running out of energy and dying out, and thus it can balance total energy consumption of the whole network and prolong the network lifetime. The formal validations and simulations evaluate the performance of MPEB, which shows that MPEB has a distinct advantage over others in both reducing and balancing energy consumption.
1. Introduction
A wireless sensor network (WSN) is a wireless network composed of spatially distributed sensor nodes. Sensor nodes are small, battery-powered, resource-constrained devices equipped with embedded CPU, sensors, and transceivers. They are usually scattered in physical environment to collaboratively monitor the surrounding conditions. Recently more and more applications of WSNs have emerged, such as target tracking on battle fields, monitoring volcanic eruptions, habitat monitoring to protect endangered wildlife, vehicular and traffic monitoring for smart living, and so forth [1].
Routing protocol is one of the key research domains in WSNs, and multicast routing protocol has drawn many attentions for its characteristics in wireless networks. It provides efficient message transmission to a group of hosts and helps reducing the bandwidth consumption. This is especially appropriate in wireless environments where bandwidth is scarce and many users share the same wireless channels. In particular, for WSNs, multicast is a fundamental and important communication pattern. A sink node can collect aggregated data from and send control messages to a set of sensor nodes using multicast. Taking environmental monitoring as an example; when the base station wants to acquire data from a given area, it sends control information by multicasting to nodes there. Additionally, sensor nodes can send messages to different sink nodes to implement distributed management. Thus, research on multicast routing is of great significance.
However, as sensor nodes have limited power, traditional multicast routing protocols for ad hoc networks are not suitable for WSNs. Moreover, multicast routing for WSNs with different mobility characteristics has been an active research domain for several years. Although some of relevant work has taken concern for energy protection, tremendous research is still required to decrease and balance power dissipation and prolong the lifetime of the network.
In this paper, we propose MPEB, an innovative multicast routing protocol for WSNs, which supports data dissemination along a layered multicast tree. Our contributions lie in three aspects. Firstly, to support multicast data dissemination, we construct and maintain a valid multicast tree. (A tree is called valid if it has no useless branches.) Secondly, to decrease total energy dissipation, we optimize the multicast tree to turn more nodes into sleeping state, while still maintain network's coverage requirement and connectivity. We achieve this by the proposed pruning algorithm. Thirdly, to protect overload nodes thereby balancing total energy, the energy balancing algorithm is proposed to protect noncritical overload nodes from running out their energy and partitioning the network. Our formal validations and simulations show that MPEB achieves a distinct advantage in reducing and balancing energy consumption, and it also keeps the connectivity of the network.
The remainder of this paper is organized as follows. After surveying the related work in Section 2, we present a detailed description of our proposal in Section 3, followed by formal validations in Section 4 and the simulation results in Section 5. Finally, we conclude this paper in Section 6.
2. Related Work
In this section, we briefly review previous work on multicast routing for wireless ad hoc and sensor networks. Many multicast routing protocols have been proposed in the literature [2–4]. For WSNs, sensor nodes are usually powered by batteries of limited capacity. In many WSNs applications, it is very difficult or even impossible to recharge or replace nodes' batteries after they are deployed. Therefore, the energy efficiency becomes a major objective for designing routing protocols in WSNs.
Nowadays, energy efficient multicast routing protocols for WSNs have been put forward, including tree-based multicast protocols, such as BAM [5], OTREMM [6], and D-ODMRP [7]. BAM obtains load reduction by single hop aggregation (S-BAM) and multiple paths aggregation (M-BAM). S-BAM aggregates radio transmission within one hop and supports one transmission to multiple intended receivers. M-BAM decreases multiple paths via aggregation and limits the range of radio transmission. SM-BAM, combining S-BAM and M-BAM, can reduce communication load. OTREMM is an energy-efficient multicasting algorithm for the case where the transmission powers of the nodes are fixed. It selects an optimal energy-efficient set of nodes for multicasting, taking into account residual energies, the transmission powers used and the set of nodes covered. D-ODMRP embeds a destination-driven feature into an existing on-demand multicast protocol ODMRP. To build a cost-effective multicast forwarding structure, the path to reach a multicast destination is biased towards those paths passing through another multicast destination; if multiple such choices are available, the one leading to the least extra cost is selected. However, OTREMM acquires specific network parameters, and BAM and D-ODMRP have been improved in more recent proposals to be introduced.
Recent proposed methods include EBMR [8] and MTMRP [9]. EBMR is an on-demand routing algorithm, which selects nodes with high energy and short distance to the source to be multicast forwarders. MTMRP, a heuristic distributed minimum transmission multicast routing protocol for WSNs, chooses the forwarding routes which can connect more multicast receivers and introduce a path handover scheme to prune redundant routes for multicast routing.
However, EBMR can further save total energy consumption by implementing sleep/work mechanism, and MTMRP can be improved by considering critical nodes' power protection to balance loads in the network. Moreover, so far, there is seldom research on the multicast routing with mobility, while there are many applications that require the multicast transmission in highly dynamic scenarios, such as traffic monitoring for smart living. Thus, we do research on a robust multicast routing protocol, which can flexibly adapt to static and dynamic network topology.
Overall, efficient power protection routing protocols are desired in dynamic and smart sensor networks. With the motivation from pruning algorithm in unicast communications [10], we propose our protocol with power saving and balancing to improve the efficiency of multicast communication in WSNs.
3. MPEB
3.1. Protocol Design
We divide all the nodes in WSNs into three types, namely, source nodes, target nodes, and other nodes. Let us firstly give necessary definitions first.
Definition 1 (source nodes).
Source nodes are the nodes which create data and send to destination nodes.
Definition 2 (target nodes).
Target nodes are the destination nodes which the source nodes send data to.
The nodes which are neither source nodes nor target nodes are called other nodes.
The WSN we consider in this paper is composed of one source node, multiple target nodes, and one or more other nodes. All the nodes can move, under a mobility model, within a constrained area. In our simulation in Section 5, the mobility model we choose is random waypoint [11]. Regarding energy model, first order radio model [12] works well for its simplicity and excellent performance. To facilitate analysis, without loss of generality, we only concern energy cost by wireless sending and receiving, ignoring energy dissipated by sensing and computing.
There are four states for sensor nodes, waiting, working, sleeping, and dead. The state transition diagram is shown in Figure 1. More details will be depicted later. Working nodes means those in the routing tree, including one root, several branches, and leaves.
State transition diagram.
Based on the network model above, we propose a new tree-based multicast routing protocol MPEB to improve power efficiency. Each node is identified by a unique ID and has attributes including En (energy remaining), Level (layer in the tree), PID (ID of its parent node), and C List (ID list of its children nodes) for the hierarchical structure. The communication based on multicast tree is implemented by kinds of control messages, including CRQ (children request message), CRQR (reply for CRQ), CMT (children maintenance message), CMTR (reply for CMT), and DNF (detach notification message).
3.2. The Framework of MPEB
The framework of MPEB includes three parts, namely, tree construction, pruning, and energy balance. In this section, we briefly introduce how to construct a multicast tree, and will present pruning and energy balance algorithms in Sections 3.3 and 3.4, respectively.
Since the tree construction is not the main contribution of our paper, we just show the skeleton of the tree construction process here. Readers who are interested in the details can refer to paper [3]. When constructing of multicast tree, the source, as root of the tree, broadcasts a solicit packet CRQ to discover its children, which in turn do the same way to discover their own children, until all the targets join in the tree. As the target nodes' IDs are contained in the CRQ messages, each node knows whether it is a target node or not. To optimize the tree, we utilize a leaf detection mechanism. If leaf node, such as S7 in Figure 2, is not a target, it sends DNF to its parent S6 to voluntarily leave the tree. After a period, all useless branches will be cut off from the tree. Finally, the bold lines in Figure 2 present the valid multicast tree. After that, the relationships between parents and children will be updated periodically via CMT and CMTR messages.
Leaf detection mechanism.
Additionally, the protocol supports coexisting of several multicast groups with adding attribute GID (group ID). Only nodes redundant for all the groups can be pruned from the multicast trees. In the same way, only when there are replacements of the tree node in every group, can it sleep to balance total power. More details are left for further research.
It is common to have several source nodes in a multicast application in WSNs. In [13], Sato proposes an efficient protocol to construct a shared tree for multisource multicast. Here, our algorithms can be easily integrated into this protocol to better multi-source multicast routing. More analysis and experiments will be shown in our future work.
3.3. Pruning Algorithm
Pruning algorithm aims at changing as many nodes as possible into sleeping state so that nodes' energy can be saved. By analyzing control messages, backup parents for each node are found and maintained. If each child of one node has backup parent, this node can be detached from the tree.
Pruning algorithm needs some modification on nodes' attributes and message structure. To maintain nodes' backup parent, GPID (grandparent's ID), and BPID (backup parent's ID) are added in nodes' attributes list. Here the parent of a node's parent is called this node's grandparent. The modifications on message structure are displayed in Table 1. Here CMT messages include the attribute PID. When receiving CMT from its parent, the node records PID in CMT as its GPID. Besides, two kinds of new messages, CDN and CDNR, are needed to detach children from their parents.
Messages for pruning algorithm.
Now we discuss how to find the backup parents. In the MPEB tree, if one node receives CRQ from another, the difference between their Levels is less than or equals 1, which will be proved in Section 4. Thus, we can draw all the possible topologies as illustrated in Figure 3.
Topologies of CRQ's sender A and receiver B.
We record the sender of CRQ as A and the receiver as B. For node B, according to the information in CRQ, the relationship between A and B can be classified into 6 types. (1) A and B have parent-child relationship, as shown in Figures 3(a-1) and (a-2); (2) A and B have the same parent, if the PID in CRQ is equal to B's PID, illustrated in Figure 3(b); (3) A's grandparent is B's parent, as displayed in Figure 3(c); (4) A's parent is B's grandparent, as displayed in Figure 3(d); (5) A and B have the same grandparent, as Figure 3(e); (6) there is no relevance between A's attributes (ID, PID, and GPID) and B's, as presented in Figures 3(f-1), (f-2), and (f-3).
In our proposal, if the relationship between A and B is (a), (b), or (c), B discards this CRQ message. If the relationship is (d), (e), or (f), B records A as its backup parent. Apart from this, if B has more than one available backup parent, the one with minimal Level will be selected. If a node has backup parent, it sets its BP_Flag = 1 when sending out CMTR messages.
When the parent, for example, node 3 in Figure 4(a), receives CMTR, it checks all the children's BP_Flag. If all its children have backup parents and node 3 is not a target node, it can turn to sleep. The process is as follows. First, node 3 sends CDN to all its children. Taking the child node, say node 7, as an example, node 7 sends CRQR to its backup parent node 2, to join node 2's subtree. When CMT from node 2 is received by node 7, which means the parent-child relationship between node 2 and node 7 has been constructed, node 7 sends CDNR to node 3 to relieve the previous relationship. Node 8 does the similar process, and thus node 3 sends DNF to its parent and turns into sleeping state. So the new tree is as Figure 4(b).
The CDN process in pruning algorithm.
As can be seen, the pruning algorithm attempts to detach more nodes from the tree, the total energy dissipated can be greatly decreased. However, there is a side effect about unbalanced loads from pruning algorithm. Take Figure 4 as an example. Although the total power consumed is reduced, nodes 2 and 4 must take more transfer loads, which affects the lifetime of the network due to early deaths of nodes with high load. To solve this problem, we propose energy balancing algorithm as expounded below.
3.4. Energy Balancing Algorithm
To implement this algorithm, we introduce two new attributes, E_Th (energy threshold to take the energy protection scheme) and EPN_ID (ID of the latest EPN message, as shown in Table 2, received by the node), included in node's attributes list. Several kinds of messages are added into this protocol, listed in Table 2. EPB message transmits by broadcasting and others by unicasting.
Messages for energy balancing algorithm.
When node A's energy reduces from original value to E_Th, A sends EPR to its parent and EPN to its children. Any node receiving EPR forwards EPR to its parent until reaching the root, while any node receiving EPN transfers EPN to its children until reaching the leaves. The process of this algorithm is shown below in Algorithm 1. To describe our protocol clearly, we make one definition first.
Energy Balancing Algorithm if node.En decreases to below E_Th, then it sends EPR to the root it sends EPN to its subtree end if If root makes decision to protect node A, then flood EPB nodes with higher power than A are waken up A's children set BPID during EPB flooding if A's child B has BPID, then B sends EPNR to A end if if all A's children send EPNR to A, then if A is a target node, then A detaches with its children A keeps working state else build new paths to targets A turns into sleeping state end if end if
Definition 3 (target leaf and target branch).
For an arbitrary node A, leaves in A's subtree which are also target nodes are defined as A's target leaves, and branch nodes in A's subtree which are also target nodes as A's target branches.
After receiving EPRs, the root computes current overall performance of the network and makes decision on whether to implement energy protection for each EPR. Here, we protect at most 20% nodes of all the alive nodes. If more nodes require protection, those with less remaining power are protected. More dynamic decision making schemes are left for our future work. If A wins the chance to be protected, root records A's ID and En in EPB and broadcasts this message. All nodes, except A, broadcast EPB at the first time they receive it. Sleeping nodes are waken up by EPB to make judgment. If the En of this node is higher than En in EPB, it turns into working state and broadcasts this message, otherwise it keeps sleeping.
When A's target leaf receives EPB for A, if its backup parent is null, it claims the node from which EPB comes as its backup parent. Then, it unicasts EPNR up along the tree to A. Each branch in A's subtree forwards EPNR to its parent only if it has received EPNR from all its children. When A has received EPNR from all its children, the energy protection can be implemented on A. For A's target leaves and target branches having backup parents, they claim their backup parents as new parents. For those without backup parents, they set the backup parents to be one of their children, because in this way, there must exist at least one path to the source node excluding A. Proof in detail will be presented in Section 4. Meanwhile, we adopt different solutions based on whether A is a target node or not. If A is a target node, A destroys the relationships with its children and only keeps communication with its parent. Otherwise, A changes its state into sleeping.
With energy balancing algorithm, we can decrease energy dissipated on nodes with low energy remaining. It is helpful to balance energy in the whole network and prolong the lifetime of the network.
To sum up, as the new protocol MPEB, with pruning algorithm and energy balancing algorithm, changes more nodes into sleeping state and protects nodes with low energy, it can improve the efficiency of power usage.
4. Formal Validation
4.1. Protocol Validation
In this subsection, we prove that MPEB can construct a valid multicast tree to satisfy the routing requirements in WSNs.
Lemma 4.
Taking source node as the root, MPEB constructs a stable multicast tree without loops within finite iterations in a connected WSN.
Proof.
From the protocol MPEB, it is apparent that source node has no parent and every other node in the tree has just one parent. Considering basic graph theory, it is a tree structure without routing loops. Now we prove that under topology changes, a stable tree can be set up within definite iterations. Here we assume that there are N nodes in the network, so Levels of nodes are integers in the interval [0, N]. (Level 0 means that the node is not in the tree.) We firstly focus on the tree construction stage, and then on tree maintenance stage, to see how to achieve a stable and valid multicast tree.
As can be seen from Section 3.2, the tree construction involves three aspects. Firstly, by flooding CRQ messages, an initial multicast tree will be built, and most parts of the nodes are connected in the multicast tree. Secondly, when constructing the multicast tree, if one node, say node A (which is already connected in the multicast tree with node B as its current parent), gets a new CRQ message from another node, say node C, and node C has a lower Level than node B, node A will set its parent as node C and the Level of node A will decrease. Thirdly, those nodes, which are connected into the multicast tree but cannot transmit messages to the target nodes, will leave from the tree and turn into sleeping state. To sum up, during the tree construction stage, there exist and only exist the above two conditions that may lead to the change of tree topology.
During the tree maintenance stage, the topology change can results from three cases. Two are similar to the two cases occurred in tree construction stage as mentioned above. Another one is the case that nodes' levels increase. For example, when a node moves to a new place and it can only connect to a new parent which has a bigger level. In this case, this node and its subtree (if exists) are affected and need to find new parents.
When one node leaves the tree, it just influences the topology once, thus the number of changes on the multicast tree will not surpass N. In the other cases, as the Level changes in the set (2, N) (excluding the root), the number of changes in the tree will not be larger than (N−1)2.
To sum up, whichever case it is, the number of nodes to change is limited, and each of them can be updated within finite iterations. Therefore, the change of the multicast tree takes place in finite iterations. In other words, the stable multicast tree can be constructed within finite iterations.
Lemma 5.
There exists at least one target node in each subtree of the stable MPEB multicast tree.
Proof.
Apparently, if no target node is on the subtree, none of the leaves are targets. With our protocol, in a duration
Lemma 6.
In the stable MPEB tree, all the leaves are target nodes.
Proof.
As one leaf node can be deemed as a special subtree with just one node, we know that it must be a target node based on Lemma 5.
Lemma 7.
In the stable MPEB multicast tree, if two nodes communicate with each other, the absolute value of the difference between their Levels is not larger than 1.
Proof.
We prove this lemma using apagoge. Assume that A and B can communicate with each other and A.Level-B.Level > 1. Obviously they do not have parent-child relationship because the difference between parent's and child's Levels must be 1. If A's parent is C, we get the equation A.Level–C.Level = 1 and B.Level < C.Level. With MPEB, A receives CRQ from B within a period
4.2. Pruning Algorithm Validation
Here, we prove that pruning algorithm does not influence the connectivity of the multicast routing. Before the validation, we first give the definition of critical node.
Definition 8.
For an arbitrary node A, if some target node becomes unachievable after deleting node A from the routing tree, node A is named a critical node.
Lemma 9.
In MPEB multicast routing tree, one node is not a critical node, if and only if this node is a branch and not a target node, and all of its children can be connected to the source node via paths excluding this node.
Proof (Adequacy).
If A is a branch and not a target node, and that for each child
Necessity. If node A is not a critical node, according to Definition 2, A is not a target, or else the target, itself, is unachievable after deleting it from the tree. With Lemma 6, A is not a leaf, so it must be a branch. For an arbitrary child B of A, there is a subtree M. From Lemma 5, M embraces one target node C. Because A is not a critical node, there exists at least one path between C and the source node which excludes A. For another part, both B and C are in the same subtree M, so they are connected. Therefore, B can also communicate with the source node along some path excluding A. As B is an arbitrary child of A, we conclude that all the children can be connected with the source node via paths excluding A.
From the description of pruning algorithm, we know that all the nodes deleted from the tree conform to the adequate condition of Lemma 9, so they are not critical nodes. Therefore, pruning algorithm will not affect the connectivity of the multicast routing. However, as pruning algorithm makes many nodes sleep, it reduces coverage degree of the network. This problem can be solved by nodes' wakeup mechanism [14], which will be further discussed as our future work.
4.3. Energy Balancing Algorithm Validation
As can be seen from Section 3, the connectivity of the multicast routing is not influenced by energy balancing algorithm, which will be validated in this section by the following lemmas.
Lemma 10.
Nodes pruned from the multicast routing tree with energy balancing algorithm are noncritical nodes.
Proof.
Assume that we execute energy balancing algorithm on node A. If A is a target node, we detach its children to save energy, but keep its connection with its parent in the tree. Otherwise, A will turn to sleep only if all its target leaves have received EPB, which is flooded along paths without A. In other words, if we assume that A has turned to sleep, there must be some other paths from its target leaves to source node. Moreover, when taking both A's subtree and new paths to target leaves into account, we can obviously find that every branch is also achievable through paths excluding A to the source. In short, all the children of A have new ways to the source. According to Lemma 9, A is a non-critical node. To sum up, just non-critical nodes can be pruned from the multicast tree by energy balancing algorithm.
Lemma 11.
EPB message never wakes up nodes with lower energy than the one for whom EPB is broadcasted.
Proof.
From the depiction in Section 3, we know that only sleeping nodes with higher energy than the En recorded in EPB will be waken up. Thus, nodes with lower En will keep in sleeping state.
Based on Lemma 11, we conclude that energy balancing algorithm makes sense for energy balancing in the whole network. However, there is more research to be done on nodes' wakeup mechanism to avoid side effects, such as total power waste due to several nodes' wakeup to save one node's power.
5. Performance Evaluation
5.1. Design of Time Parameters
From the detailed description in Section 3, there are four principal time parameters in MPEB, including
From the equations listed above, we know that with the successful ratio of transmissions S increasing,
5.2. Network Configurations
We simulate MPEB on ns-2 simulation platform. The configurations are listed below in Table 3. In our simulation, we suppose the source node has infinite energy. Although there are different kinds of control messages, these messages always carry relevant basic information. Thus, to simplify the simulation, we assume, without loss of generality, that the size of control messages is 10B. Regarding energy model, we use the first-order radio model [12] as mentioned in Section 3.1, and the parameter configurations are the same as the paper [12]. Interested readers can refer to [12] for details.
Simulation environment configurations.
To analyze effects of each algorithm, we have made experiments on three MPEB versions as follows. (1) B-MPEB: basic multicast routing protocol without pruning algorithm and energy balancing algorithm. (2) P-MPEB: multicast routing protocol with pruning algorithm, but without energy balancing algorithm. (3) PB-MPEB: multicast routing protocol with both pruning algorithm and energy balancing algorithm. We compare our proposals with improved protocols EBMR and MTMRP.
In the simulations, we analyze two criteria, total energy remaining and survival ratio (as depicted in Section 5.3). To prove the practicality of our proposal, we also concern about the connectivity of the network. Note that all the values in the simulation results are average in 100 experiments. The results are illustrated as in Figures 5 to 8.
Total energy consumption.
Note that although the results in Figures 5 to 8 are gotten under the network whose configuration is in Table 3, we do still simulate other configurations to see in what kind of WSNs our protocol performs well. Firstly, since node density of the network greatly affects the tree structure, we have made experiments with the number of nodes at 30 and 90. The results show that lower node density of the network, less advantage of the pruning algorithm performs, as less backup parents can be found. This indicates that our proposal works better in WSNs with plenty of nodes. Secondly, we have tested different values for energy threshold E_Th from 1J to 6J. The results show that too low or too high values highly affect the survival radio at around 45% and 80%, respectively, which is inline with expectations, as low E_Th undermines the benefits of energy protection and high E_Th brings about many control messages wasting limited resource. Thus, based on the experiments, we suggest that it is better to set the energy threshold as 2J. More details are omitted due to limited space. We also leave more sufficient simulations and analysis as our future work.
5.3. Simulation Results
5.3.1. Total Energy Analysis
Total energy remaining shows the ratio of total energy remaining to initial total energy during the simulation time. Higher energy remaining means higher efficiency of the total energy usage.
When nodes move with low speed as illustrated in Figure 5(a), PB-MPEB and P-MPEB are advantaged to others, because pruning algorithm can change more nodes to sleep so as to save total energy.
In the early, PB-MPEB consumes least, while after a while, PB-MPEB expends more energy than P-MPEB. The reasons are as follows. (1) As more and more nodes acquire energy protection, energy consumed roars up due to control messages, especially EPB flooded in the network. (2) Side effects of this mechanism, like wasting power by many nodes' waking up to save one node's power, exert detrimental impacts on the overall performance.
Among these five protocols, B-MPEB consumes most energy, while MTMRP with a path handover scheme performs better than EBMR. In B-MPEB, since nodes always select those with the lowest Level to be their parents, this will decrease the number of hops, but increase distance within one hop, costing more energy to send messages. Therefore, B-MPEB does not perform well on total energy saving.
While nodes move at high speed, from Figure 5(b), the performance of B-MPEB becomes even worse, as the moving nodes change their parents with higher frequency due to rapid topology changes. Meanwhile, the advantage of pruning algorithm is weakened because of increasing control messages.
Comparing MTMRP with PB-MPEB, we find that both of them perform almost the same under low speed movement model, while the MTMRP performs much worse than PB-MPEB under high speed movement model. Thus, the robustness of our proposal is better than MTMRP.
To investigate the network stations with different protocols, we collected the energy remaining of each node at 300 s in the simulation. The result is shown in Figure 6. As the initial locations of all nodes are generated randomly and they move with random waypoint model, there are many fluctuations in the figure. But, we can still get the overall performance of the network. As seen from the figure, the average energy remaining and the energy balance of our proposal are better than EBMR and MTMRP.
Energy remaining of each node at 300 s in the network.
To sum up, we make the following conclusion.
Conclusion 1.
For MPEB, the decline in total energy consumption is attributed to pruning algorithm.
5.3.2. Survival Ratio Analysis
Survival ratio means the ratio of the number of alive nodes to the number of all nodes. Higher survival ratio means better balance of the total network.
The simulation results are illustrated in Figure 7. When nodes move with a low speed, our proposals perform better than EBMR and MTMRP. Because energy balancing algorithm can balance total power of the network and avoid early deaths efficiently, PBMPEB performs best in Figure 7(a) as expected. But P-MPEB performs worse than B-MPEB, because the side effect of pruning algorithm, as discussed before, makes some nodes overloaded, hastening their deaths.
Survival ratio of the nodes.
Connectivity of the network.
As the figure shows, MTMRP and P-MPEB do not perform well due to the overload on critical nodes on the paths. In brief, we propose another conclusion.
Conclusion 2.
For MPEB, pruning algorithm may cause load imbalance, but energy balancing algorithm can balance energy consumption.
However, under high-speed movement, P-MPEB is superior to PB-MPEB, shown in Figure 7(b). We can explain this phenomenon with two reasons. (1) High-speed mobility automatically balances communication loads among nodes. While nodes move slowly, the topology seems to be stable and nodes with high load die quickly. However, with high speed, topology changes frequently and different loads cannot exert tremendous impacts such as early deaths, so high mobility is good for load balance. (2) Topology changes consume much more power by control messages in energy balancing algorithm, thus its performance deteriorates. In short, another conclusion is presented below.
Conclusion 3.
For MPEB, when the topology changes with high frequency, the advantage of energy balancing algorithm degrades.
5.3.3. Connectivity Analysis
We use the number of achievable target nodes to analyze network connectivity. As can be seen from Figure 8, PB-MPEB performs better than others with low speed, and P-MPEB performs a little better than PB-MPEB under high mobility, in accordance with our analysis above, too.
In Figure 8(a), after nearly 600 seconds with low-speed mobility, as the branch nodes on the tree are powered off, the target nodes become unreachable. The confidence interval for our proposal is (500, 700) with confidence level 0.95, while that for MTMRP is (350, 500). Thus, we can see that our protocol has advantages over others. With high speed mobility, the total performance looks worse than that with low speed mobility, while our protocol still has a little advantage than others.
To sum up, comparing with EBMR, our protocol decreases total energy consumption nearly 11% and increases survival ratio almost 17%, especially under stable scenario with low moving speed. Comparing with MTMRP, our proposal decreases total energy consumption nearly 14% and increases survival ratio almost 13%, especially under dynamic scenario with high mobility models. The overall performance is superior, so that it can prolong the lifetime and optimize the transmissions in the network.
However, these two new algorithms slightly increase the multicast-based delay. Especially when the network topology changes quickly, the amount of control messages increases rapidly. Hence, it may be not sensible to take these algorithms to save energy under strictly restricted latency.
6. Conclusion
In this paper, we propose MPEB, a multicast routing protocol based on multicast tree structure. To decrease energy consumption, pruning algorithm attempts to change as many non-critical nodes as possible to sleep. However, it makes energy dissipation unbalanced in the network, so energy balancing algorithm is proposed to protect nodes with low power to avoid early deaths. In order to prove the correctness and validity of these schemes, we make theoretical proof in Section 4 and sufficient experiments in Section 5. Compared with EBMR and MTMRP, we verify that MPEB with pruning algorithm and energy balancing algorithm is effective on energy protection and balance.
However, there is still much profound research to be done to avoid side effects of pruning algorithm and energy balancing algorithm, such as that pruning algorithm may decrease the coverage of the network due to nodes' sleeping and that energy balancing algorithm may wake up too many nodes to protect one node. Additionally, many more experiments need to be done to deploy this protocol in actual sensor motes to test its performance in realistic wireless sensor networks.
Footnotes
Acknowledgments
The authors gratefully acknowledge the support from China's Natural Science Foundations (61272350 & 61173009), National High Technology Research and Development Program of China (2011AA010501), International S&T Cooperation Program of China (2010DFB13350), Doctoral Fund of Ministry of Education of China (20091102110017), and Shenzhen Key Laboratory of Data Vitalization (Smart City).