تجمع داده ها و مسیریابی در شبکه های حسگر بی سیم: الگوریتم های بهینه و هیوریستیک

A fundamental challenge in the design of Wireless Sensor Networks (WSNs) is to maximize their lifetimes especially when they have a limited and non-replenishable energy supply. To extend the network lifetime, power management and energy-efficient communication techniques at all layers become necessary. In this paper, we present solutions for the data gathering and routing problem with in-network aggregation in WSNs. Our objective is to maximize the network lifetime by utilizing data aggregation and in-network processing techniques. We particularly focus on the joint problem of optimal data routing with data aggregation en route such that the above mentioned objective is achieved. We present Grid-based Routing and Aggregator Selection Scheme (GRASS), a scheme for WSNs that can achieve low energy dissipation and low latency without sacrificing quality. GRASS embodies optimal (exact) as well as heuristic approaches to find the minimum number of aggregation points while routing data to the Base-Station (BS) such that the network lifetime is maximized. Our results show that, when compared to other schemes, GRASS improves system lifetime with acceptable levels of latency in data aggregation and without sacrificing data quality.

Wireless Sensor Networks (WSNs) is a class of wireless ad hoc networks in which sensor nodes collect, process, and communicate data acquired from the physical environment to an external Base-Station (BS) [1]. Future WSNs are envisioned to revolutionize a maintenance free and fault-tolerant platform for collecting and processing information in diverse environments. A major technical challenge for WSNs, however, lies in the node energy constraint and its limited computing resources, which may pose a fundamental limit on the network lifetime [1]. Therefore, innovative techniques to eliminate energy inefficiencies that would otherwise shorten the lifetime of the network are highly needed. In many applications of WSNs (e.g., military battlefields, target field imaging, intrusion detection, surveillance, and inventory control), data collected by many sensors is based on common phenomena, and hence there is a high probability that this data has some redundancy (or correlation). Due to the correlation present in the sensors’ readings, it is expected that communication approaches that take into account this correlation, e.g., data aggregation and in-network processing, will outperform traditional approaches. The main idea of the data aggregation and in-network processing approaches is to combine the data arriving from different sources (sensor nodes) at certain aggregation points (or simply aggregators) en route, eliminate redundancies by performing simple processing at the aggregation points, and minimize the total amount of data transmission before forwarding data to the external BS. Removing redundancies results in transmitting fewer number of bits, and hence reduces energy consumption and increases the sensor nodes’ lifetimes. A number of studies that compared aggregation scheme, e.g., [3], [4], [5] and [23] concluded that enhanced network throughput and more potential energy savings are highly possible using data aggregation and in-network processing in WSNs. Aside from the task of efficient design of data aggregation algorithms, the task of finding and maintaining routes in WSNs is also nontrivial [2], especially when it includes the selection of aggregation points and routing through those points. Many routing and data dissemination with aggregation protocols have been proposed for WSNs (a comprehensive survey of the routing techniques in WSNs can be found in [2]). In [3], Intanagonwiwat et al. proposed a popular data aggregation paradigm for WSNs, called Directed Diffusion (DD) where aggregation is used to reduce communication costs. In [5], Heinzelman et al. introduced a hierarchical clustering algorithm for WSNs, called Low Energy Adaptive Clustering Hierarchy (LEACH). LEACH is a cluster-based protocol where ClusterHead (CH) nodes compress data arriving from nodes that belong to the respective cluster, and send an aggregated packet to the BS. Following these protocols, many other studies focused on the routing problem [6], [7], [8], [9], [10], [11], [12], [13], [14], [15], [16], [17], [18], [19], [20] and [21]. Among these, [17] introduced a linear programming formulation to solve the optimal routing problem in WSNs. The objective was to maximize the network life time, and the life time was defined as the network operational time until one of the nodes fails. Necessary, but insufficient, conditions for the existence of a solution under arbitrary traffic generation processes were introduced. A heuristic solution was also introduced. However, no aggregation was assumed. In [18], aggregation was taken into account, but only full aggregation was considered. That is, regardless of the number of packets to be aggregated, a single packet will always be produced. This simplifies the problem of aggregation significantly. A special case of partial aggregation, in which the aggregated data size is equal to the minimum of the original data, and a maximum size, was considered in [19]. A heuristic was introduced for this case. In [20], heuristics as well as an approximation algorithm, were introduced to select the minimum number of sensors which would form the minimum connected correlation dominating set. Such a set is used to infer readings from other sensors (with an acceptable error), and also forward data towards the data collection center. The network lifetime was not explicitly addressed in this paper. The authors in [32] proposed a Voronoi detection method that utilizes distributed Voronoi diagram and genetic algorithms to gather data in WSNs, while [33] considers maximizing large scale Wireless Sensor Networks lifetime under energy constraint via joint relay deployment and adaptation. In [36], several lossless aggregate repacking algorithms for cluster-model Wireless Sensor Networks were presented. In [37], an energy-efficient data gathering scheme that prolongs the lifetime of battery-powered sensor nodes is considered. The proposed scheme constructs and maintains a spanning tree that is based on breadth-first search and has more leaf nodes in network. Kalpakis et al. [29] presented algorithms for the Maximum Lifetime Data Aggregation (MLDA) problem with the objective of maximizing the system lifetime. A near optimal algorithm for solving the MLDA problem was proposed in [29]. Since this algorithm is computationally expensive for large sensor networks, authors in [29] presented a clustering based heuristics approaches (CMLDA) for MLDA in large scale WSNs. Experimental results of MLDA demonstrated enhanced system lifetime of WSNs. Other related studies also appeared [28], [30], [31] and [34]. A recent survey of strategies and protocols for routing correlated data can be found in [35]. To the best of our knowledge, the joint optimization of the routing and data aggregation functions were not carried out in the literature, especially for the general case of partial aggregation. In this paper, we present a novel data aggregation and routing scheme, called Grid-based Routing and Aggregator Selection Protocol (GRASS). GRASS embodies optimal (exact) as well as heuristic approaches to find the minimum number of aggregation points while routing data to the BS such that the network lifetime is maximized. That is, GRASS jointly addresses the issues of the selection of data aggregation points, and the optimal routing of data from sensors to aggregation points, as well as the routing of the aggregated data to the BS. While solving these two problems separately may simplify the problem, the solution may be far from optimal. Therefore, our proposed solution treats the two problems jointly in order to reach an optimal solution. Since this joint problem is not trivial, we adopt a hierarchical structure in which each group of sensor nodes elect a cluster head which is responsible for: (1) collecting their sensed data, (2) performing a first level aggregation, and then (3) routing this data to the next aggregator on its way to the BS. This first level of aggregation achieves two benefits. First, it offers the greatest performance benefits in this environment since nodes in a cluster are most likely to generate correlated data, and then it simplifies the routing function since only the cluster head will be in charge of this functionality. Hence, the hierarchical structure facilitates digests of sensor data. Indeed, this is a key issue in the design of GRASS. In GRASS, correlation means that sensors’ readings overlap statistically as they monitor the same event. This overlap will be captured in our proposed solutions using aggregation overlap factor. The factor represents linear as well as non-linear relations among the gathered data. We propose to solve the joint aggregator selection and routing problems in a powerful node, such as the BS, and then dispatch the results to the sensor nodes. Hence, an optimal solution that is obtained by the BS will result in an optimal routing and aggregation strategy. The rest of this paper is organized as follows: the problem description and system model are presented in Section 2. Section 3 presents exact algorithms to solve the problem, and using two definitions of network lifetime. Section 4 presents several approximate algorithms for the problem under consideration. Section 5 presents analysis of energy-delay tradeoffs due to our aggregation scheme. The performance evaluation of the proposed scheme is presented in Section 6. We conclude with final remarks in Section 7.

In this paper, we studied the maximum lifetime data gathering and routing problem in WSNs. We showed that cluster-based algorithms along with data aggregation and in-network processing can achieve significant energy savings in WSNs. This has a direct effect on prolonging the network lifetime. In particular, we developed GRASS (Grid-based Routing and Aggregator Selection Scheme), a scheme for WSNs that combines the ideas of fixed cluster-based routing together with application-specific data aggregation in order to enhance the wireless sensor network performance in terms of extending the network lifetime, while incurring acceptable levels of latency under data aggregation. Within GRASS, we have presented optimal as well as heuristic algorithms that solve the joint problem of optimal routing with data aggregation for the sake of maximizing the network lifetime. Our results show that, when compared to other approaches in the literature, the proposed scheme is able to improve the network lifetime while incurring acceptable levels of latency and without sacrificing quality. Hence, GRASS can attain the energy and latency efficiency needed for Wireless Sensor Networks.