2.2 Routing in WSN:

ROUTING CHALLENGES AND DESIGN ISSUES IN WIRELESS SENSOR NETWORKS

Wireless Sensor Networks (WSNs) possess several distinctive characteristics that differentiate them from wired and ad hoc networks. These unique traits bring forth specific routing design requirements and pose challenges that are distinct from those encountered in traditional networks
Meeting these design requirements and overcoming the challenges posed by the unique characteristics of WSNs require the development of specialized routing protocols that can optimize energy efficiency, adapt to dynamic environments, and ensure reliable data delivery despite resource constraints.

1. Network Scale and Time-Varying Characteristics
   Dynamic and Adaptive Behavior: Sensor nodes constantly adjust their behavior to conserve energy and adapt to changing network conditions, such as varying levels of activity and wireless interference.
   Wide Range of Densities: WSNs can range from sparse to dense deployments, with hundreds to thousands of nodes covering wide areas.
   Unsupervised Deployment: Nodes are often deployed ad hoc without supervision, leading to dynamic and unpredictable network behavior.
2. Resource Constraints
   Energy Limitations: Sensor nodes operate on limited battery reserves and must conserve energy to achieve long lifetimes.
   Power Consumption in Multihop Transmission: Routing protocols must minimize energy consumption, especially in multihop transmission scenarios, which are significant sources of power consumption.
   Mission-Critical Applications: Many applications have strict performance constraints, requiring a delicate balance between energy efficiency and meeting application requirements.
3. Sensor Applications Data Models
   Variety of Data Models: Different sensor applications require different data collection models, including periodic sampling, event-driven data gathering, data aggregation, and bidirectional communication.
   Complexity of Routing Design: Routing protocols must optimize for specific application data requirements while supporting diverse data models and delivering scalability, reliability, responsiveness, and power efficiency.
4. Severe Energy Constraints:
   Sensor nodes in WSNs typically operate on limited battery power, leading to severe energy constraints.Routing protocols must minimize energy consumption to prolong the network's lifetime.
5. Limited Computing and Communication Capabilities:
   Sensor nodes have constrained processing power and memory, limiting their ability to perform complex computations.
   Communication among nodes may be constrained by low bandwidth and limited transmission range.

Routing strategies/algorithms for ad hoc networks, which share similarities with WSNs, can be categorized into three main strategies: proactive, reactive, and hybrid.

1. Proactive (Table-Driven) Routing: Proactive strategies maintain consistent and accurate routing tables across all nodes by periodically disseminating routing information. These strategies can be flat or hierarchical. While flat strategies have the potential to compute optimal paths, the overhead required for maintaining these paths may be high in dynamic environments. Hierarchical routing is more suitable for large networks, providing scalability and efficiency.

2. Reactive Routing: Reactive strategies establish routes to specific destinations on demand, without maintaining global information across all nodes. They rely on dynamic route search mechanisms, often involving flooding route discovery queries and processing replies. These strategies vary in how they control the flooding process to reduce overhead and manage route establishment and failure recovery.

3. Hybrid Routing: Hybrid strategies combine elements of proactive and reactive routing to leverage network structure for stability and scalability. Nodes are organized into clusters, and routing may be proactive within clusters and reactive across clusters. Clustering helps limit the scope of routing algorithm reactions to network changes, reducing overhead. However, managing clusters efficiently presents its own challenges.

6.5.1 WSN Routing Techniques, 203

several routing techniques have been proposed for WSNs:

1. Flat Network Architecture: Some routing protocols adopt a flat network architecture where all nodes are considered peers. This architecture minimizes overhead in maintaining infrastructure and allows for the discovery of multiple routes between communicating nodes, enhancing fault tolerance.

2. Cluster-Based Routing: Another approach involves organizing network nodes into clusters, with each cluster typically led by a node with higher residual energy (cluster head). Cluster heads coordinate activities within their clusters and forward information between clusters. Clustering can improve energy efficiency, stability, and scalability, potentially extending the network's lifetime.

3. Data-Centric Routing: This class of protocols takes a data-centric approach to disseminate interest within the network. Source nodes issue queries based on attributes of phenomena rather than specific sensor nodes. Tasks are assigned to sensor nodes based on these attributes, and various strategies, such as broadcasting, multicasting, geo-casting, and anycasting, are used to communicate interests to sensor nodes.

4. Location-Based Routing: Routing protocols in this class utilize the location of sensor nodes within the network's geographical coverage. Queries issued by source nodes may specify a particular area of interest or proximity to a specific point in the network environment, making location-based routing relevant for such applications.

6.5.2 Flooding and Its Variants, 203

Flooding is a straightforward technique commonly used for path discovery and information dissemination in both wired and wireless ad hoc networks. It operates on a reactive basis, where each node receiving a data or control packet forwards it to all its neighbors. This process continues until the packet reaches its destination or its hop count reaches zero. While flooding is simple and adaptable to changing network topologies, it suffers from several drawbacks in wireless sensor networks (WSNs).

1. Traffic Implosion: Flooding can lead to traffic implosion, where duplicate packets are sent repeatedly to the same node. This redundant transmission increases network congestion and resource consumption.

2. Overlap Problem: Overlapping occurs when multiple nodes covering the same region send packets with similar information to the same destination node. This redundancy wastes network resources and bandwidth.

3. Resource Blindness: Flooding does not consider the energy constraints of sensor nodes. As a result, nodes may deplete their energy rapidly, leading to a shortened network lifetime.

To mitigate these issues, a derivative approach called gossiping has been proposed. Gossiping maintains the simplicity of flooding while addressing its drawbacks:

• Randomized Forwarding: Instead of broadcasting packets to all neighbors, each node in gossiping forwards the packet to a randomly selected neighbor. This randomness helps distribute the traffic more evenly across the network.

• Limited Packet Replication: Gossiping limits the number of copies of a packet sent by each node to its neighbors, reducing the likelihood of traffic implosion.

• Iterative Forwarding: The packet forwarding process continues iteratively, with each node randomly selecting a new neighbor to forward the packet to. This iterative process helps avoid congestion and reduces the chances of overlapping.

6.5.3 Sensor Protocols for Information via Negotiation, SPIN206

Sensor Protocols for Information via Negotiation (SPIN) is a family of data-centric negotiation-based information dissemination protocols designed for Wireless Sensor Networks (WSNs). These protocols aim to efficiently distribute observations collected by individual sensor nodes to all nodes within the network. Unlike simple protocols such as flooding and gossiping, which suffer from performance degradation with increasing network size and traffic load, SPIN protocols address these limitations by incorporating data negotiation and resource adaptation.

Here's an overview of SPIN and its key features:

1. Data Negotiation: SPIN protocols employ semantic-based data negotiation, where nodes learn about the content of data before transmitting it. Nodes associate metadata with the data they produce, and interested nodes can request specific data by sending a request (REQ) message to the advertising node. This negotiation ensures that data are sent only to nodes interested in receiving them, reducing traffic implosion and redundant data transmission.

2. Resource Adaptation: Nodes running SPIN are capable of adapting their activities based on their energy resources. Each node monitors its resource consumption and may adjust its participation in protocol operations to conserve energy. For example, when a node's energy level is low, it may reduce or eliminate certain activities to extend its longevity and the network's lifetime.

3. Message Types: SPIN protocols use three types of messages for negotiation and data transmission:

   • ADV (Advertisement): Used by a node to advertise new data to its neighbors by transmitting metadata describing the data.
   • REQ (Request): Sent by nodes interested in receiving specific data advertised by other nodes.
   • DATA: Contains the actual data collected by a sensor node, along with metadata.

4. SPIN Variants:

   • SPIN-PP (Point-to-Point): Designed for point-to-point communication networks, SPIN-PP uses a three-step handshake protocol to advertise, request, and transmit data. It addresses implosion and overlap problems of traditional protocols.
   • SPIN-EC (Energy-Conscious): An extension of SPIN-PP that incorporates a threshold-based resource-awareness mechanism to conserve energy.
   • SPIN-BC (Broadcast): Designed for broadcast networks, SPIN-BC takes advantage of broadcasting capabilities to eliminate redundant data exchange by delaying requests and limiting data transmission.
   • SPIN-RL (Reliability): Enhances SPIN-BC by periodically broadcasting ADV and REQ messages to improve reliability and overcome message transmission errors caused by a lossy channel.

5. Performance: Simulation studies have shown that SPIN protocols are more energy-efficient and achieve higher data dissemination rates compared to flooding and gossiping protocols. They achieve these improvements by localizing topology changes, reducing redundant information dissemination, and conserving energy through resource adaptation.

Despite its advantages, SPIN may have limitations in scenarios where intermediate nodes drop ADV messages, potentially preventing interested nodes from receiving data advertisements. However, overall, SPIN protocols offer significant improvements over traditional dissemination protocols in WSNs.

6.5.4 Low-Energy Adaptive Clustering Hierarchy, LEACH 210

The Low-Energy Adaptive Clustering Hierarchy (LEACH) is a routing algorithm designed to extend the lifetime of Wireless Sensor Networks (WSNs) by reducing energy consumption and utilizing data aggregation

1. Extension of Network Lifetime: By distributing energy consumption evenly across all sensor nodes.
2. Reduced Energy Consumption: Achieved through hierarchical clustering and data aggregation.
3. Data Aggregation: To reduce the number of communication messages and conserve energy.

   Operations:

   1. Hierarchical Clustering: LEACH organizes the network into clusters, each managed by a selected cluster head responsible for data collection, aggregation, and transmission to the base station.
   2. Cluster Head Selection: During the setup phase, nodes compete to become cluster heads based on a randomized threshold calculation. Cluster heads are responsible for organizing cluster members and managing communication.
   3. TDMA-Based Schedule: Cluster heads create and distribute Time Division Multiple Access (TDMA) schedules to allocate time slots for data transmission among cluster members, reducing collision probability.
   4. CDMA-Based Communication: To further reduce interference, LEACH nodes use Code Division Multiple Access (CDMA) for communication.
   5. Data Collection and Transmission: During the steady-state phase, nodes collect data periodically and transmit it to the cluster head using their allocated time slots.

   Shortcomings and Improvements:

   1. Assumption of One-Hop Communication: LEACH assumes that all nodes can reach the base station in one hop, which may not be realistic in all scenarios.
   2. Steady-State Period Length: The duration of the steady-state phase affects energy consumption, balancing protocol overhead and cluster head energy depletion.
   3. Extended LEACH (XLEACH): Addresses shortcomings by considering node energy levels in cluster-head selection. The threshold calculation includes current energy and maximum energy, ensuring fair selection based on residual energy.

   Properties and Benefits:

   1. Distributed Energy Consumption: Nodes assume the cluster head role in a round-robin fashion based on residual energy, distributing energy requirements across all sensor nodes.
   2. Decentralized Operation: LEACH is a completely distributed algorithm, requiring no control information from the base station. Cluster management is achieved locally.
   3. Data Aggregation: Reduces energy consumption by allowing clusters to aggregate data before transmission to the base station.
   4. Performance: Simulation studies show that LEACH outperforms conventional routing protocols in terms of energy efficiency and network lifetime extension.

   LEACH and its variants, such as XLEACH, offer significant improvements in energy efficiency and network longevity compared to traditional routing protocols. However, they require careful consideration of parameters and network characteristics to optimize performance in different deployment scenarios.

6.5.5 Power-Efficient Gathering in Sensor Information Systems ,PEGASIS 213

Power-Efficient Gathering in Sensor Information Systems (PEGASIS) and its hierarchical extension are routing and information-gathering protocols designed for Wireless Sensor Networks (WSNs) with the objectives of extending network lifetime and reducing data transmission delay. Here's an overview of PEGASIS, its operations, and improvements:

Objectives:

1. Extend Network Lifetime: Achieved by enhancing energy efficiency and balancing energy consumption across all nodes.
2. Reduce Data Transmission Delay: Minimize the delay encountered by data on their way to the sink.

Network Model:

• Homogeneous Nodes: Nodes are assumed to be homogeneous and deployed across a geographical area.
• Global Knowledge: Nodes have global knowledge about other sensor nodes' positions.
• Power Control: Nodes can adjust their power to cover arbitrary ranges.
• CDMA-Capable Radio Transceivers: Nodes may be equipped with CDMA-capable radio transceivers.
• Data Sink: Typically a wireless base station to which data is gathered and delivered.

Chain Structure:

• Nearest Neighbor Communication: Nodes communicate with their closest neighbors.
• Chain Construction: Starts with the farthest node from the sink, progressively adding nodes in a greedy fashion until all nodes are included.
• Chain Leader: Selected node responsible for transmitting aggregated data to the base station.
• Rotation of Leadership: Ensures balanced energy consumption among all network nodes.

Data Aggregation:

• Sequential Aggregation: Data aggregation along the chain, starting from the end nodes and progressing towards the leader.
• Parallel Aggregation: Achieved using CDMA-capable transceivers, allowing for simultaneous transmissions along the chain and hierarchical overlay.

Hierarchical PEGASIS:

• Hierarchical Structure: Nodes organized into a hierarchical, tree-like structure to achieve parallel data aggregation.
• Binary Chain Approach: Nodes operate in a highly parallel manner, with data aggregated and transmitted in a balanced, hierarchical manner.
• Balanced Energy Reduction: Guarantees that aggregated data arrive at the leader after a logarithmic number of steps.
• Intermediate Scheme: Strikes a balance between sequential and fully parallel schemes, achieving some level of parallelism without requiring CDMA capabilities.

Simulation Results:

• Performance Improvement: Hierarchical extension of PEGASIS shows considerable improvement over schemes like LEACH.
• Outperformance: Hierarchical scheme outperforms the original PEGASIS by a significant factor.

6.5.6 Directed Diffusion, 215

6.5.7 Geographical Routing, 219