## 2 Background Knowledge
### WSN Routing Mechanism  
Routing is a key issue in sensor computing. A pair of nodes not within the transmission range can communicate with each other by other intermediate nodes used as relay nodes. The selection of intermediate nodes to send a message is called routing. In other words, the routing process is to construct a path between the source node and destination node that is not within the transmission range. Many routing researches have been proposed for sensor networks. A routing protocol for sensor networks should have scalability, data aggregation, network dynamics, low complexity, energy-efficiency, fault tolerance and multiple paths [8].  
In on-demand routing mechanisms, the route is discovered only when needed by the source node, minimizing the network overhead at the cost of a slow response. One such mechanism is DSR (Dynamic Source Routing), which is an on-demand routing protocol. DSR allows a network to be completely self-organizing and self-configuring, without the need for any existing network infrastructure or administration. The protocol consists of the two main mechanisms, namely \"Route Discovery\" and \"Route Maintenance\", which work together to allow nodes to discover and maintain routes to arbitrary destinations in the _ad hoc_ network. All aspects of the protocol operate entirely on-demand, allowing the routing packet overhead of DSR to scale automatically to only that needed to react to changes in the routes currently in operation. Determining the source routes requires obtaining the address of each device between the source and destination during route discovery. The sourcedemands a routing path by flooding request packets in the networks. The accumulated path information is cached by nodes processing the route discovery packets. A node denotes a route with complete information of the destination node it has traversed, as shown in Figure 3. This may result in a high overhead for long paths. Figure 4 shows a scenario in which a route breaks; the detecting node returns a Route Error packet to the original sender. The sender can invoke Route Discovery again to obtain a new route.  
Figure 4: Route maintenance in DSR protocol.  
Figure 3: DSR routing operations.  
Clustering means that grouping all wireless sensor nodes into many clusters [9,10]. Partitioning the whole sensor network into small regions, can turn a network into an easily controllable and manageable infrastructure. Clustering provides a good framework for power control, low interference and efficient channel utilization. Clusters are generally formed in two stages: (1) a cluster header is selected at random or by a pre-defined method; (2) cluster headers and the member nodes interact to form a group named cluster. A cluster performs information filtering, data fusion and aggregation such as periodic calculation of the average temperature of its coverage area, and effectively reduces communication overhead. The amount of control traffics is limited within each cluster, helping reduce the energy consumption. Since the cluster header must manage all nodes belonging to it, excessive operations of header may quickly cause energy exhaustion. Hence, the nodes within a cluster take turns based on a round-robin strategy to act as the cluster header. The strategy can also be determined by a node's connectivity relationships or power level, in order to balance the energy consumption and extend the system lifetime.