## 2 Routing Algorithms for Wireless Sensor Networks
### Data-Centric Protocols (Flat Architecture)  
In data-centric protocols, the sensor nodes broadcast an advertisement for the available data and wait for a request from an interested sink. Flooding is a simple technique that can be used to broadcast information in wireless sensor networks. However, it requires significant resources because each node receiving a message must rebroadcast it, unless a maximum number of hops for the packet are reached, or the destination of the packet is the node itself. Flooding is a reactive technique that does not require costly topology maintenance or complex route discovery algorithms. However, it does have several additional deficiencies, including implosion, overlap and resource blindness [6]. A derivation of flooding is gossiping, in which nodes do not broadcast. Instead, they send the incoming packets to a randomly selected neighbor. Sensor protocols for information via negotiation (SPIN) address the deficiencies of classic flooding by providing negotiation and resource adaptation [7]. However, the SPIN data advertisement mechanism cannot, by itself, guarantee data delivery [8]. SPIN employs a shortest path strategy based on three types of messages to communicate:  
ADV--new data advertisement. When a SPIN node has data to share, it can advertise this fact by transmitting an ADV message containing meta-data. REQ--request for data. A SPIN node sends a REQ message when it wishes to receive some actual data. DATA--data message. A DATA messages contains actual sensor data with a meta-data header. Unlike traditional networks, a sensor node does not necessarily require an identity (e.g., an address). Instead, applications focus on the different data generated by the sensors. Because data is identified by its attributes, applications request data matching certain attribute values. One of the most popular algorithms for data-centric protocols is direct diffusion, which bases its routing strategy on a shortest path strategy [9]. A sensor network based on direct diffusion exhibits the following properties: each sensor node names the data it generates with one or more attributes, other nodes may express interest based on these attributes, and network nodes propagate interests. Interests establish gradients that direct the diffusion of data. In its simple form, a gradient is a scalar quantity. Negative gradients inhibit the distribution of data along a particular path, and positive gradients encourage the transmission of data along the path. The Energy-Aware Routing protocol is a destination-initiated reactive protocol that increases network lifetime by using a single path at all times, which is very similar to source routing [10]. Rumor routing [11] is a variation of direct diffusion that is mainly intended for applications where geographic routing is not feasible. Gradient-based routing is another variant of direct diffusion [12]. The key idea of gradient-based routing is to memorize the number of hops when the interest is diffused throughout the network. Constraint Anisotropic Diffusion Routing (CADR) is a general form of direct diffusion [13] and lastly, Active Query Forwarding in Sensor Networks (ACQUIRE) [14] views the network as a distributed database, where complex queries can be further divided into several sub queries. The XMesh Routing Protocol is a multi-hop routing protocol developed by Crossbow to run on the MICA and eKo families of modes [15]. In the XMesh routing protocol the cost metric minimizes the total number of transmissions required to deliver a packet over multiple hops to a destination and is termed Minimum Transmission (MT) cost metric. This differs from the traditional cost metric of distance vector routing which is hop count. The multi-hop network is initially formed when motes broadcast periodic beacon messages to all other motes within radio range. When the beacon messages are sent, they contain a cost value, which indicates the energy required to transmit a message from the motes to the base station.