Wireless sensor networks (WSNs) usually contain power-constraint nodes that require energy-efficient (a.k.a. green) transmission techniques, resource sharing algorithms and networking protocols (see an example in Figure 1). Each WNS node consists of one or more sensors for sensing the surrounding environment. Sensors are small and usually inexpensive, and have limited processing resources. Sensors sense and gather information from the environment, based on the decision guidelines provided by users in forms of queries. Acquired data are transmitted, via embedded radio in nodes, among nodes in a multi-hop way and finally reach the root, i.e., the base station (Estrin, Girod, Pottie, & Srivastava, May 2001).
Usually, a WSN has no infrastructure and has an ad-hoc topology. This topology is due to the fact that sensor networks are typically deployed in hard-to-access environment. Obstructions in the environment can limit the wireless communication between nodes, affecting the network connectivity. These networks have many applications, such as military target tracking and surveillance, natural disaster relief, biomedical health monitoring and hazardous environment exploration and sensing.
Data Query, Processing, and Routing
Data sensing and transmitting consume a considerable portion of nodes' energy which is limited and vital (Potdar, Sharif, & Chang, May 2009). The main goal of query processing is to answer queries posed by users, while decreasing the energy consumption and prolonging network lifetime are also considered (Gehrke & Madden, March 2004). Queries are declared by users to the network and the network returns the required data by using the query processing engine (Madden, Franklin, Hellerstein, & Hong, Tinydb, An acquisitional query processing system for sensor networks, March 2005). A single query processing scheme assumes one active query in the network. However, in reality, different users may connect to the base station and query various data. In many cases, although different users may have different requests, their requests are somewhat similar. Thus, assigning a network to a single query and running queries sequentially not only lead to undesirable delays in responding to user requests, but also results in a vast energy wasting by doing redundant operations corresponding to different queries. Therefore, multi-query processing has been considered in which multiple queries run in the network simultaneously (Trigoni, Yao, Demers, Gehrke, & Rajaraman, June 2005).
Severe energy constraints and consequently communication and processing limitations of sensor nodes make centralized methods not suitable for these networks, as their execution involves noticeable processing overhead and needs a global view of the network. Generating this global view especially when the network is large will lead to a quick energy drain of nodes. Therefore, distributed and lightweight methods which are executable by low-powered sensor nodes and that need only local information to run properly, are required (Akyildiz, Su, Sankarasubramaniam, & Cayirci, March 2002).
Multi-hop data routing, driven by the above mentioned limitations, is typically used in a tree topology for data delivery, where intermediate nodes (as parents) receive data from their beneath nodes (i.e., child nodes), apply aggregation functions on them and their local data, and send the aggregated data to the next hop towards the base station (Yao & Gehrke, January 2003). This topology is formed by issuing a “flood” from the base station towards the network, through which nodes are assigned to different levels. Due to flooding and the location of nodes, each node might receive multiple flooding messages from some other nodes which can be its candidate parents. Thus, each node can have some candidate parents. However, at the end of flooding process, each node selects a parent in one level lower than its level, to which it will send the acquired data. Higher amount of traffic leads to faster energy depletion and the nodes suffering this problem have a shorter lifetime compared to nodes dealing with a less amount of traffic. Thus, uneven distribution of children among parents implies uneven drain of energy and lifetimes for nodes. As the nature of sensor networks is ad-hoc and randomly distributed, the connectivity of the network highly depends on the lifetime of nodes.