Section 20.4. Routing Protocols | Computer and Communication Networks (paperback)

20.4. Routing Protocols

After clusters with well-distributed cluster heads have been established in a network, energy-conscious routing is essential in order to set communication routes among cluster heads in a two-level hierarchical system. Similar to computer networks, routing protocols in sensor networks can be classified as either intracluster or intercluster . This section looks at both categories.

The fundamental concept behind them is much the same as the concept behind intradomain and interdomain routings (see Chapter 7). Assuming that every node in a cluster can act as a relay node, there could be a large number of possible routes from a source to a sink. Because of the limited transmission range associated with low-power wireless technologies cluster-head packets cannot reach the base station unless other cluster heads act as relay nodes. Two major approaches can be used for routing and selecting the best path in a sensor network, as follows :

Centralized routing , whereby the routing decision is made by a single command center
Distributed routing , whereby the routing decision is made in a distributed fashion by several entities

Distributed routing algorithms are further classified as proactive or reactive. With proactive routing algorithms, such as link-state routing and distance-vector routing, nodes keep a routing table that contains next -hop information to every node in the network. Reactive routing protocols set a route to the desirable destination only when it is needed. Note that none of the ad hoc network protocols explained earlier consider energy consumption.

Another group of on-demand reactive routing protocols address the exclusive issues of wireless sensor network. For example, directed diffusion introduces a concept of "interest" propagation whenever a node wants to send data or a source needs to ask for it. With this type of protocol, flooding the network with interest signals establishes a path from a sink to every possible source (spanning tree).

20.4.1. Intracluster Routing Protocols

A routing algorithm within a cluster can be either direct or multihop . In a direct routing algorithm, the cluster head as the destination for all cluster nodes is located in the center of the cluster, so all nodes can communicate with the cluster head directly, as shown in Figure 20.8. Note that in this figure, two nodes cannot reach the destination, as they are located far from it. The number shown in each node indicates the level of energy the corresponding node has.

Figure 20.8. Direct routing in a cluster. The number associated with each node indicates a normalized value of the remaining energy in that node.

In a multihop routing algorithm, a node can face multiple hops in order to reach the destination. If a multihop algorithm is used for the centralized clustering procedure, the algorithm aims to choose the appropriate next neighbor for each node, using a central command node. Typically, a central command node collects the information about direct paths' costs and geographical positions of the nodes and finds the best path.

Figure 20.9 shows a routing implementation. Sensor nodes are usually scattered in the field. A packet from a node is routed to a neighboring node that exhibits the highest amount of energy. The energy is an indication of the node's battery level. The number associated with each node indicates a normalized value of the remaining energy in that node. Figure 20.9 shows two paths from a node to a cluster-head node. One path involves the shortest distance in terms of hop counts; the other one uses the highest-energy route. The challenge here is to find the best path that suits the rapid and secure deployment of data. Data is routed to the cluster head as shown in Figure 20.1, where the cluster head may communicate with the base station via radio frequencies.

Figure 20.9. Multihop routing in a cluster in which the number associated with each node indicates a normalized value of the remaining energy in that node

The least-cost algorithm and the best-energy path can be modeled and compared for a network to provide a behavioral benchmark. The model can determine all possible paths available between a given source and destination. The energy of each node and hence all possible least-cost paths are computed regularly by cluster heads and propagated to all cluster nodes for database updating. During the phase of path finding to a cluster head, the routing algorithm accepts a failing (low-energy) node and finds the least-cost path, taking the failing node into account. The inputs for route process then include source node, destination node, failing nodes, and all other nodes.

20.4.2. Intercluster Routing Protocols

Intercluster protocols are not typically different from the multihop ones for intradomain cases. Interdomain protocols are available for

Intercluster energy conscious routing (ICR)
Energy-aware routing (EAR)
Direct diffusion

ICR uses interest flooding similar to directed diffusion and EAR to establish routes between the base station and sensor nodes but differs from EAR and directed diffusion in some aspects.

Intercluster Energy-Conscious Routing (ICR)

ICR is a destination-initiated reactive routing protocol. This means that a destination, local base station (LBS), initiates an explicit route-discovery phase, which includes the propagation of an interest signal that floods throughout the network and establishes energy-efficient routes. Based on the application, which can be either periodic data collection or event driven, the interest signal can include the type and the period of the desired data shown in Figure 20.10. For an application requiring information from specific locations, the interest signal also includes the position of the required information.

Figure 20.10. Interest-signal structure in a packet

Figure 20.11. LBS starts route discovery by generating interest signals.

If the LBS requires some periodic data collection, it sets the period in which nodes send the specific type of information. Monitoring and surveillance applications are examples for the data-collection paradigm. If it requires sensor nodes to detect one specific event, an LBS includes the type of the event in the interest signal. Following the route-discovery phase, sensor nodes switch to sleep mode and wait for the specific event. In case of event detection, non-cluster-head nodes send the data directly to the associated cluster head, which uses the previously established route to send the information back to the LBS. In short, ICR occurs in two phases: route discovery and data acquisition .

In route discovery , the local base station initiates route discovery by sending an interest signal within the range of R _i . The value of R _i should be both high enough to keep the cluster-head network connected and low enough to prevent unnecessary energy consumption and interest generation. Owing to even distribution of cluster heads achieved by a clustering protocol, R _i can be chosen slightly bigger than the average distance between a pair of adjacent cluster heads. The LBS should adjust its output power and data rate of the interest signal to limit its transmission range to R _i . Also, the cost field is set to zero before interest propagation starts.

Since the distance between a pair of neighboring cluster heads is approximately the same across the network, the communication energy consumption associated with two distinct adjacent cluster heads is also the same. Therefore, the cost, or weight, of a multihop path is defined exclusively by the number of hops. In addition, the remaining energy in the cluster heads along the path affects the route-selection decision. The total-cost function C is defined as

Equation 20.15

where h is the hop number and B _ri represents the remaining energy in the battery of node i, B _M shows the maximum battery capacity of a sensor node, and ± and ² are normalization factors. The second part of the cost field favors the paths that include nodes with higher energy. To update the cost field, each intermediate cluster head calculates the inverse of its remaining battery power plus 1 (increment in the number of hops) and adds the outcome to the existing cost value.

Each intermediate cluster head that receives the interest signal saves the interest in its memory, including the address of the nodes that sent the message. Then the node should update the cost field of the outgoing interest signal and send it within the range of R _i . All the cluster heads within this range around the sender can hear the incoming signal. If it receives an interest signal that currently exists in memory but the sender's address is different, a cluster head compares the cost field of the received signal with the cost field of the previously saved message. If the incoming interest signal includes a cost field smaller than the previously saved message, the node replaces the old interest entry, updates the cost field, and propagates the packet, since the new signal represents a shorter, or more energy-efficient, path. If the new interest signal represents a path with a higher number of hops, the node should destroy the packet.

The data-acquisition phase occurs after each cluster head collects the requested information from sensor nodes and compresses it into a packet with fixed length, searches for the neighbor's address in memory, and relays the packet to that neighbor. In order to reduce the diffusion of spare data bits in the network, relay nodes can receive the data packets, each of length L , from N nodes and aggregate them into one single packet of length L . This reduces the number of data bits forwarded by the relay node from NL to L . To enable data aggregation during the data-collection period, cluster heads that are closer to the base stationthat is, the cost field of the saved interest message includes fewer hopsshould wait for their neighbors to send their data packets and then compress the incoming information with their own data and send the packet with the fixed length to the relay neighbor.

Comparison of ICR and EAR

ICR is different from EAR in two aspects. In EAR, sensor nodes save and propagate most of the incoming interest signals and eliminate only the ones with a very high cost field. However, in ICR, every time that the cost field of the incoming interest message is higher than the previously saved one, the packet gets destroyed . This puts a limit on the generation of interest messages.

In EAR, in order to ensure that the optimal path does not get depleted and that the network degrades evenly, multiple paths are found between a source and a destination. Each node has to wait for all the interest signals to come and then calculates the average cost between itself and the destination. Based on the average cost, each path is assigned a probability of being chosen. Depending on the probability, each time one of the paths is chosen, ICR assumes that data aggregation is executed among cluster heads, and no packet moves along the chosen path independently. This means that during the data-collection period, each cluster head aggregates the data from its N adjacent cluster heads and has to forward only one compressed packet rather than N distinct packets. After the execution of the routing protocol, a spanning tree is established that is rooted in the base station and connects all the cluster heads to the base station. Therefore, only the least-cost, or the optimum, path is a final, established route for each cluster head. This way, the degradation of the optimal path for each packet is prevented.