INTRODUCTION: Wireless Sensor Networks (WSN) are intended for monitoring an environment. The main task of a wireless sensor node is to sense and collect data from a certain domain, process them and transmit it to the sink where the application lies. However, ensuring the direct communication between a sensor and the sink may force nodes to emit their messages with such a high power that their resources could be quickly depleted. Therefore, the collaboration of nodes to ensure that distant nodes communicate with the sink is a requirement. In this way, messages are propagated by intermediate nodes so that a route with multiple links or hops to the sink is established.
Taking into account the reduced capabilities of sensors, the communication with the sink could be initially conceived without a routing protocol. With this premise, the flooding algorithm stands out as the simplest solution. In this algorithm, the transmitter broadcasts the data which are consecutively retransmitted in order to make them arrive at the intended destination. However, its simplicity brings about significant drawbacks. Firstly, an implosion is detected because nodes redundantly receive multiple copies of the same data message. Then, as the event may be detected by several nodes in the affected area, multiple data messages containing similar information are introduced into the network. Moreover, the nodes do not take into account their resources to limit their functionalities.
One optimization relies on the gossiping algorithm 1. Gossiping avoids implosion as the sensor transmits the message to a selected neighbor instead of informing all its neighbors as in the classical flooding algorithm. However, overlap and resource blindness are still present. Furthermore, these inconveniences are highlighted when the number of nodes in the network increases.
Due to the deficiencies of the previous strategies, routing protocols become necessary in wireless sensor networks. Nevertheless, the inclusion of a routing protocol in a wireless sensor network is not a trivial task. One of the main limitations is the identification of nodes. Since wireless sensor networks are formed by a significant number of nodes, the manual assignation of unique identifiers becomes infeasible 2. The use of potentially unique identifier such as the MAC (Medium Access Control) address or the GPS coordinates is not recommended as it forces a significant payload in the messages 3. However, this drawback is easily overcome in wireless sensor networks since an IP address is not required to identify the destination node of a specific packet. In fact, attribute-based addressing fits better with the specificities of wireless sensor networks. In this case, an attribute such as node location and sensor type is used to identify the final destination.
Once nodes are identified, routing protocols are in charge of constructing and maintaining routes between distant nodes. The different ways in which routing protocols operate make them appropriate for certain applications.
In the related literature, there are plenty of proposals concerning routing algorithms in wireless sensor networks. This paper aims at describing the most relevant ones in order to facilitate the understanding of the different routing techniques that could be applied into wireless sensor networks. Specifically, the paper explains some attributed-based, geographic, hierarchical and multipath routing protocols. The most significant Spanish proposals are also described.
The rest of the paper is structured as follows. Section 2 shows the basic communication paradigms that wireless sensor networks follow while Section 3 describes the main design constraints that routing protocols must face in wireless sensor networks. In Section 4, we present the most popular classification schemes for routing protocols in this kind of networks. Section 5 outlines the optimization procedures adopted by these routing protocols. The application of these techniques leads to attribute-based, geographic, hierarchical and multipath routing protocols, as shown in Section 6. Section 7 summarizes the most significant schemes for routing protocols defined in Spain, focusing on our contributions. Finally, Section 8 draws the main conclusions of this work.
ALGORITAM PARADIGAM AND WIRELESS SENCER-
Sensor applications demand the communication of nodes to execute certain procedures or algorithms. In fact, three kinds of algorithms can be executed on wireless sensor networks –
Centralized Algorithms: They are executed in a node that posses the knowledge of the whole network. These algorithms are quite rare because of the cost of transmitting the data to make the node know the status of the complete network.
Distributed Algorithms: The communication is supported by message-passing.
Local based Algorithms: The nodes use restricted data acquired from a close area. With this local information, the algorithm is executed in one node.
DESIGN CONSTRIANTS AND ROUTING WIRELESS-
Due to the reduced computing, radio and battery resources of sensors, routing protocols in wireless sensor networks are expected to fulfill the following requirements:
Autonomy: The assumption of a dedicated unit that controls the radio and routing resources does not stand in wireless sensor networks as it could be an easy point of attack. Since there will not be any centralized entity to make the routing decision, the routing procedures are transferred to the network nodes.
Energy Efficiency: Routing protocols should prolong network lifetime while maintaining a good grade of connectivity to allow the communication between nodes. It is important to note that the battery replacement in the sensors is infeasible since most of the sensors are randomly placed. Under some circumstances, the sensors are not even reachable. For instance, in wireless underground sensor networks, some devices are buried to make them able to sense the soil.
Scalability: Wireless sensor networks are composed of hundred of nodes so routing protocols should work with this amount of nodes.
Resilience: Sensors may unpredictably stop operating due to environmental reasons or to the battery consumption. Routing protocols should cope with this eventuality so when a current-in-use node fails, an alternative route could be discovered.
Device Heterogeneity: Although most of the civil applications of wireless sensor network rely on homogenous nodes, the introduction of different kinds of sensors could report significant benefits. The use of nodes with different processors, transceivers, power units or sensing components may improve the characteristics of the network. Among other, the scalability of the network, the energy drainage or the bandwidth are potential candidates to benefit from the heterogeneity of nodes.
Mobility Adaptability: The different applications of wireless sensor networks could demand nodes to cope with their own mobility, the mobility of the sink or the mobility of the event to sense. Routing protocols should render appropriate support for these movements.
Classification of Routing Protocols in Wireless Sensor Networks
Taking into account their procedures, routing protocols can be roughly classified according to the following criteria.
4.1. Hierarchy Role of Nodes in the Network
In the flat schemes, all sensor nodes participate with the same role in the routing procedures. On the other hand, the hierarchical routing protocols classify sensor nodes according to their functionalities 8. The network is then divided into groups or clusters. A leader or a cluster head is selected in the group to coordinate the activities within the cluster and to communicate with nodes outside the own cluster. The differentiation of nodes can be static or dynamic.
4.2. Data Delivery Model
Depending on the application, data gathering and interaction in wireless sensor networks could be accomplished on several ways. The data delivery model indicates the flow of information between the sensor nodes and the sink 7. The data delivery models are divided into the following classes: continuous, event-driven, query-driven or hybrid. In the continuous model, the nodes periodically transmit the information that their sensors are detecting at a pre-specified rate. In contrast, the query-driven approaches force nodes to wait to be demanded in order to inform about their sensed data. In the event-driven model, sensors emit their collected data when an event of interests occurs. Finally, the hybrid schemes combine the previous strategies so sensors periodically inform about the collected data but also response to queries. Additionally, they are also programmed to inform about events of interest.
Optimization Techniques for Routing in Wireless Sensor Networks?
The particular characteristics of wireless sensor networks and their constraints have prompted the need for specific requirements to routing protocols. When compared to mobile ad hoc networks routing protocols, the algorithms in wireless sensor networks usually realize the following specifications:
In these algorithms, the sink sends queries to certain regions and waits for the response from the sensors located in this area. Following an attribute-value scheme, the queries inform about the required data. The selection of the attributes depends on the application. An important characteristic of these schemes is that the content of the data messages is analyzed in each hop to make decisions about routing.
5.2. Energy Efficiency
Multiple routes can communicate a node and the sink. The aim of energy-aware algorithms is to select those routes that are expected to maximize the network lifetime. To do so, the routes composed of nodes with higher energy resources are preferred.
5.3. Data Aggregation
Data collected in sensors are derived from common phenomena so nodes in a close area usually share similar information. A way to reduce energy consumption is data aggregation. Aggregation consists of suppressing redundancy in different data messages. When the suppression is achieved by some signal processing techniques, this operation is called data fusion.
5.4. Addressing Scheme
Wireless sensor networks are formed by a significant number of nodes so the manual assignation of unique identifiers is infeasible. The use of the MAC address or the GPS coordinates is not recommended as it introduces a significant payload 3. However, network-wide unique addresses are not needed to identify the destination node of a specific packet in wireless sensor networks. In fact, attribute-based addressing fits better with the specificities of wireless sensor networks. In this case, an attribute such as node location and sensor type is used to identify the final destination. Concerning these identifiers, two different approaches have been proposed 3. Firstly, the ID reuse scheme allows identifiers to be repeated in the network but keeping their uniqueness in close areas. In this way, a node knows that its identifier is unique in a k-hop neighborhood, being k a parameter to configure. On the other hand, the field-wide unique ID schemes guarantee that the identifiers are unique in the whole application. With this assumption, other protocols such as routing, MAC or network configurations can be simultaneously used.
When this technique is used, a node decides the transmission route according to the localization of the final destination and the positions of some other nodes in the network.
5.6. Multipath Communication
With this technique, nodes use multiple paths from an origin to a destination in the network. As multipath communications are intended to increase the reliability and the performance of the network, these paths should not share any link. Multipath communications can be accomplished in two ways. Firstly, one path is established as the active communication routing while the other paths are stored for future need, i.e. when the current active path is broken. On the other hand, it is also possible to distribute the traffic among the multiple paths.