Abstract: Background: The WSN is a set of wireless sensor nodes with limited energy. It is impossible to supply extra energy or recharge. Objective: In this study, the difference between the precision data gathering mode and correlated data gathering mode is analyzed. Materials and Methods: Data gathering is the major work of WSNs and also the main reason of energy consumption. However, the existing studies mainly focus on the energy-efficient route protocol. In addition, although some of them have survey the data gathering, mainly focus on the periodic data gathering and event-driven data gathering. Results: In this study, the energy-efficient data gathering of WSNs is summarized from the precision data gathering and correlated data. Conclusion: To our best of knowledge, it is a more comprehensive survey from the perspective of data gathering.
INTRODUCTION
The WSN is a set of wireless sensor nodes with constrained energy which generally is stationary or mobile. Moreover, it is not possible to supply extra energy or even replace the battery. Data gathering is the major work of WSNs and also the main reason of energy consumption. Data gathering means that each node periodically sensing quantitative data in the sensor network and then forward to the sink by one hop or more hops. The main work modes can be summarized as the precision data gathering mode and correlated data gathering one1. However, the existing studies mainly summarize from the perspective of routing protocol. The survey proposed by Akkaya and Younis2 is a relatively early one and introduces the routing protocols and presents categories for the various approaches. They describe the existing protocols from the point of data-centric, hierarchical and location-based. Differ from Akkaya and Younis2 and Pantazis et al.3 introduces the history and application of WSNs, as well as concludes and discusses the protocol from the perspective of network structure, communication model, topology and reliable routing. With the development of WSNs, new protocols are being constantly proposed. Thus Pantazis et al.3 survey these four protocols into more detailed classification. Although data fusion is mentioned in Akkaya and Younis2, no more detailed discussion is shown. Furthermore, some of them have summarized the data gathering from the perspective of the network operating mode thus, the periodic data gathering4 and event-driven data gathering5. Underthe periodic data gathering scenario, the wireless sensor network communication, infrastructure techniques, middleware techniques are shown in Li and Gao4 and Liang et al.5 mainly focus on the event-driven data gathering. They introduce the concepts and the features of the event-driven data gathering and show analysis and comparison on the existing protocols. Differ from the above ones, goal in this study mainly focus on data gathering from the perspective of precision data gathering and correlated data gathering. To the best of knowledge, it is a more comprehensive survey for data gathering. In this study, the recent literatures on these two aspects are reviewed. The difference of these two modes is analyzed. Then a more detailed classification and comparative discussion is shown for each method.
The remaining of this study is organized as follows. The problem description is introduced firstly. Secondly, the precision data gathering mode is described and then the correlated data gathering mode is discussed. Finally, the future study is discussed.
MATERIALS AND METHODS
The main data gathering modes can be summarized as followings: The precision data gathering mode and the correlated data gathering mode. The related background of lifetime and round is introduced firstly, as this is the target of the data gathering. The aim of such mode is transfer all of the data to the sink (or base station) efficiently so that the network lifetime can be maximized in terms of each round. More specially, a round is defined as the process of gathering all of the data from the common nodes to the base station, regardless of how much time it takes. In addition, lifetime is generally defined as the number of rounds until the first node in this network depletes of its energy6.
Precision data gathering mode: As the nodes in WSNs constantly sensing data all the time. The easiest way is to transfer all the sensor data to the sink node directly. However, this will accelerate the dissipation of energy of each node. Thus, it is necessary to establish an effective route (shortest path) or strategies to gather data. This method can be used for general sensor networks. It can also be used in heterogeneous homogeneous WSNs. All in all, the design challenge is to find the optimal path transmission algorithm to maximize the network life time. As illustrated in Fig. 1, the precision data gathering can be classified with three types, cluster-based data gathering, chain-based data gathering and tree-based data gathering.
Correlated data gathering mode: Since, the nodes in WSNS are deployment relatively close, it makes the sensing data get a strong correlation7. Therefore, some subset of the data collection node is selected to approximate expression perceive events to reduce network energy consumption. All in all, the design difficulty is how to design and construct the correlation algorithm to determine a subset of connected dominating. Especially, this method can be only used for homogeneous WSNs not for heterogeneous networks.
| Fig. 1: | Category of precision data gathering mode |
As illustrated in Fig. 2, the correlated data gathering can be classified with three categories, connected dominating sets transmit, connected dominating sets gathering and tree-based data integration.
Generally speaking, precision data gathering usually focus on the design of efficient routing algorithm and the correlated data gathering mainly focus on the application layer. Especially, the tree-based data gathering can be used for both two scenarios.
Precision data gathering mode: Precision data gathering mode can be divided into three types. Thus, cluster-based, chain-based and tree-based data gathering protocol. While, the last protocol can be subdivided into centralized and distributed data gathering protocol.
Cluster-based data gathering protocol: In order to reduce the communication cost caused by all the nodes frequently interact with sink, cluster-based algorithm is proposed. The main idea of this protocol is as follows.
As illustrated in Fig. 3, the node can be classified with three type, the common node, cluster head and the sink. The cluster nodes only communicate directly with the cluster head node, while cluster head node can communicate with sink directly or transmit the data to sink by multi-hop as communication with other cluster heads. A part of nodes are selected from the whole nodes according to certain rule and treated as the cluster heads and then the remaining nodes choose to join their neighboring clusters as the members. Especially, only the cluster head is responsible for gathering the data and then transmit to the Sink node by one hop or more hops. The LEACH8, HEED9 and EEUC10 are the typical instances. The LEACH is the earliest cluster-based data gathering protocol. The other ones are mainly proposed based on it. The main idea of LEACH is using localized coordination and control for cluster construction, as well as local computation in each cluster to reduce the information must be transferred to the base station.
Based on LEACH, a novel distributed clustering protocol named HEED was proposed9. Differ from LEACH; the latter one periodically selects cluster heads according to a hybrid of the remaining energy and a secondary parameter. Moreover, the cluster head algorithm in HEED is more effective.
As the previous clustering algorithms usually use two techniques, thus selecting cluster heads with more remaining energy and rotating cluster heads periodically. However, they ignored the hot spots problem. More specially, the hot spots means the cluster heads are burdened with heavy traffic as they closer to the Sink and forward more data and therefore tend to die early. To address this issue, a mechanism named EEUC was proposed10. The nodes are divided into clusters of unequal size, while clusters closer to the sink get smaller sizes, so that these ones can preserve more energy and improve the lifetime of whole network.
| Fig. 2: | Category of correlated data gathering mode |
| Fig. 3: | Cluster-based protocol |
Above all, the difficult of cluster-based protocol is the design of clustering algorithm. It not only needs to ensure the fairness of the cluster head selection but also needs to reduce the hot spots near the sink.
Chain-based data gathering protocol: The main idea of chain-based data gathering protocol is as follows. All the nodes consist of a chain and one of noes is selected and treated as the head node. As illustrated in Fig. 4, the head node is in the center. The nodes at the both ends of the chain transmit their sensing data to the head node and only the head node transmits data to sink directly. The PEGASIS11, CCS12 and DRAEM13 are the typical instances.
The PEGASIS11 is an improvement chain-based protocol based on LEACH. In PEGASIS, in order to reduce the amount of energy cost, each node only communicates with its neighboring nodes and alternate forwarding information to the sink. However, the PEGASIS causes the transmission of redundant data as the cluster head selection algorithm does not take into account the location of sink. Inspired by this disadvantage, an enhanced PEGASIS based on CCS is proposed and consider this factor12. For many applications, it is also important to consider the delay caused by gathering data. The DRAEM13 is an improved protocol as it considers this factor.
All in all, the advantage of the chain based protocol can be summarized into two aspects. For one thing, as the node only communicate with the neighboring ones and therefore reducing energy consumption. For another, compared with the cluster based algorithm, it also reduces the cost of reconstruction caused by clustering algorithm. However, the main inadequate is that the nodes farther away from head node will cause large delay, as well the head node may become the bottleneck.
Tree-based data gathering protocol: In large-scale intensive multi-hop sensor network, there exists hot spot problem for precision data gathering. In order to maximize the lifetime of WSNs, it requires constructing maximum lifetime spanning tree. As illustrated in Fig. 5, all the nodes in WSNs consist of a tree and each node receives data transmitted by its child nodes and then transmits to the parent node together with its own sensing data. According to the character of the algorithm, the main study can be summarized as the centralized data gathering and distributed data gathering. In this section, the centralized data gathering algorithm is introduced and then the distributed one.
| Fig. 4: | Chain-based data gathering protocol |
| Fig. 5: | Tree-based data gathering protocol |
Centralized data gathering algorithm: The PEDAP and PEDAP-PA6, MLDGA14, EESR15 and MAXLAT16 are the typical examples of centralized data gathering algorithm.
Tan and Korpeoglu6 propose two new algorithms; one is named as PEDAP and the other one is PEDAP-PA. The PEDAP-PA is the power-aware version of the former one. The two algorithms are near-optimal tree-based routing protocols. A near-optimal maximum lifetime data gathering and aggregation algorithm named MLDGA is proposed by Zhang et al.14, which attempts to minimize the total energy cost and maximize the lifetime of the nodes in each round. Hussain and Islam15 propose an algorithm named EESR based on multi-hop routing in a homogeneous network. Given both the location of the nodes and sink, they generate a sequence of routing paths with appropriate number of rounds that maximize the network lifetime.
| Table 1: | Precision data gathering protocol comparison |
Liang et al.16 proposed an algorithm named MAXLAT for the construction of spanning tree. The MAXLAT reduces cost as it does not need to know the location information of each node.
Above all, the existing algorithms mainly focus on the centralized data gathering, under this scenario, the existing ones have reached the theoretical optimum, however the communication overhead of centralized algorithm protocol is too large and thus it is not suitable for WSNs as the characters of large-scale nodes and resource-constrained.
Distributed data gathering algorithm: Differ from the former one, the distributed algorithms only need partial information to calculate routes and thus it is more suitable for the WSNs scenarios. The gradient flooding protocol17 and NNT18 and EEDAT19 are the typical examples of distributed data gathering algorithm.
Most existing methods suppose that the sensing data transmissions are delivered in the direction of a sink from multi- distributed nodes. However, they do not consider the mobility of nodes. Thus, Han et al.17 propose a new gradient flooding protocol which only needs one hop count as a cost metric for data forwarding and thus minimum overhead. A simple and local distributed algorithms named NNT was proposed by Khan et al.18 for construction of an energy-efficient approximate minimize spanning tree. They assume that the nodes are uniformly distributed and then show provable bounds on the quality of the spanning tree and the energy consumption of constructing them. They show that NNT produces a close approximation to the minimize spanning tree and also consumes asymptotically less energy than the existing distributed algorithm.
Chen et al.19 proposes a distributed tree-based algorithm for precise data gathering in WSNs named EEDAT. The EEDAT mainly consists of two steps. First of all, a shortest path tree was constructed by a distributed manner. Then adjusts the load of nodes in the tree to balance energy consumption of different nodes.
The existing energy cost model generally assumed that each node performed perfect fusion and thus transmitted only one message. Differ from this, Imon et al.20 consider a more generic scenario wherein a node does not perform fusion and can forward a varying number of messages. They propose a novel randomized switching algorithm to maximize the lifetime of network on the concept of bounded balanced trees, as well as provide a distributed version of the this algorithm.
A special tree based data gathering algorithm: In some applications of delay-sensitive and durative surveillance, such as forest fire monitoring, mine road gas monitoring and battlefield surveillance. The network needs to meet these two requirements of maximum lifetime and minimum delay. Thus, it not only requires the networks can save energy and have long lifetime, but also it requires that the data can be transmitted to the sink as soon as possible. However, the two objects have been proved to be contradictory. Then, they proposed a new tree-based data gathering algorithm named MILD16 to effectively balance these two objectives.
Improvement of network topology: Moreover, the new topologies21,22 are proposed for the data gathering of WSNs. Given the disadvantage of network delay in the existing data gathering methods. Yu21 proposes an optimal construction algorithm of network topology for data gathering. The WSNs can be seen as a connected graph, the k-subgraphs are found from the above graph, which minimizes the distance among each node and then they use the Hungarian method to reduce the edges in k-subgraphs until obtaining a spanning tree.
Small world network, the typical instance of complex network, has large aggregation coefficient and small average path length. Inspired by the advantages of small word network and combine with UCR mechanism, a new cluster level topology algorithm for WSNs was proposed by Wang et al.22. Thus, it reduces the cluster size near the sink and effectively solves the hot spots problem. All in all, at the end of this section, a comparison analysis of the given precision data gathering protocol is shown in this section. The details are shown in the Table 1.
RESULTS AND DISCUSSION
Correlated data gathering: Correlated data gathering mode can be divided into three types. The first one is to construct a connected dominating subset to transmit data and the second one is to reduce data redundancy, the last one is fusion intermediate node tree.
Connected dominating sets for data transmission: In WSNs, as the result of the lack of fixed infrastructure or centralized management, Connected Dominating Set (CDS) of the graph is suitable for representing the network for the virtual backbone of WSNs. At present, a lot of work of constructing a network of MCDS virtual backbone for efficient data collection have been proposed. However, constructing a minimum CDS is NP-hard15,23-25. Many of the existing CDS construction algorithms do not take into account of the diameter of a CDS while it is an important factor. Li et al.23 investigate the problem of constructing a CDS with a bounded diameter and propose a heuristic algorithm for the solution. Assume that a sensor networks is defined as a connected Unit Disk Graph (UDG). The problem is attempt to find a minimum CDS of given UDG with minimum routing cost for each node pair. Du et al.24 presents a constant approximation scheme which produces a CDS, as well as a distributed algorithm is also provided with analogical performance. A CDS based backbone was proposed in Hussain and Islam15 to support the operation of an energy efficient network. The main characters of this paper are three key ideas in design. Thus a realistic weight matrix, an asymmetric link between pairs of nodes and a role switching technique is proposed to prolong the lifetime of the CDS backbone. Kui et al.25 proposed a novel distributed algorithm named EBCDS, where each node had high energy and large degree. According to transmitting data through the backbone with small routing space, the nodes can maintain more energy. Therefore, the nodes in the backbone would not die quickly as a result of lacking energy.
Connected dominating sets for data gathering: The WSN generally consists of homogenous nodes and deployed intensive and thus nearby data may get a high correlation. This induces opportunities for data aggregation. Consequently, it is very necessary to make use of data correlations, so as to reduce data redundancy26, CAG27,28 EECDS29 and IAA30 are the typical instances. Enachescu et al.26 formalize a notion of correlation that can vary by a given parameter. Then they propose a randomized routing algorithm for data aggregation. Yoon and Shahabi27 propose a method named CAG, the main idea of CAG is reduce the number of transmission and provide approximate results to aggregate queries by using the spatial correlation. In addition, the result is ensured to be within a threshold of user-provided error-tolerance.
Gupta et al.28 proposes using exploit data correlations to minimize energy costs caused by data gathering. They firstly select a relative small subset of nodes which may be sufficient to reconstruct data for the whole network. Then, only the selected nodes need to be involved in process of data gathering. They select problem as the connected CDS problem and propose energy-efficient distributed algorithms to solve this issue.
Yu et al.29 proposes an algorithm named EECDS to reduce the redundancy data in WSNs. They firstly determine the correlation degree between sensor nodes by evaluating the entropy of Gaussian random variables and then generate a correlation graph. They finally construct a connected correlation dominating set by removing redundant nodes based on this graph. Especially, the method in Yoon and Shahabi27 only considerate the correlation among neighboring nodes. As well as the method in Gupta et al.28 also take into account the correlation of near nodes within K-hop. While this one propose using entropy evaluation for the solution. Compared with the former ones, it is more accurately to evaluate the data correlation among each node.
As illustrated in the above section, the tree can be widely used for precision data gathering. Actually, it also can be used for correlated data gathering. Goel and Estrin30 propose the problem of finding trees to send information from multi-source node to a single sink in the given network where the information can be fusion on an intermediate node. Then they propose a randomized tree construction algorithm for this issue. In addition, the methods mentioned in the previous section, such as PEDAP, PEDAP-PA and MLDGA also can be used for the correlated data gathering.
Other correlated data gathering mode: Besides the correlated data gathering method, the correlated events detection can also be used for energy saving. In heterogeneous WSNs, a strong connection exists among different types of data being composed into an event. Energy cost can be reduced by gathering part of data to approximately detect the event. The approximate event detection problem is proposed by Gao and Li31. The network lifetime is maximized under the condition that the part of data gathering can be formed as an approximation of the event. The problem is proved to be NP-complete and a greedy algorithm is also proposed for solving this issue31,32.
In addition, Jiang et al.32 propose using dynamic ring-based routing scheme for correlated data gathering. Firstly, nodal data is routed to rings in minimum-hop and then all data aggregation is handled with along the ring, after that the aggregated data is routed to the sink with shortest path.
At the end of this section, a comparison analysis of correlated data gathering protocol is shown from four aspects. The details are shown in the Table 2.
| Table 2: | Correlated data gathering protocol comparison |
CONCLUSION
In this study, two types of data gathering mode of WSNs are reviewed by introducing and summarizing a number of representatives. In summary, although the existing studies have achieved good results, there are still some potential future studies issues need to be further investigated. For precision data gathering issue, the low time cost of distributed data gathering tree algorithm can be further improvement. More specifically, which local information is more effectively requires further study. Furthermore, the new WSNs topology clustering algorithm can be proposed for the solution of hot spots problem. As known to all, data center network structure has been well studied recently, maybe the related technique can be used for the topology improvement of WSNs. For correlated data gathering issue, when considering redundancy reduction, the existing data saving method only consider the cost of data transmission; neither consider the impact of the accuracy of the user data fusion decision. Therefore, the new correlated data gathering protocol need to be proposed and take into account this factor.
ACKNOWLEDGMENTS
The authors would like to thank the reviewers for their detailed reviews and constructive comments, which have helped improve the quality of this study. This study is supported by Quanzhou Science and Technology Project (No.2015Z115), Huaqiao University Phase III fund to start research projects for attracting talent of in 2014 (No.14BS316), the Cloud Computing Platform for Internet of Things-Fujian Scientific Research Platform for Innovation (2013H2002).