Routing Techniques in Wireless Sensor Networks: A Survey
---
paper_title: Energy-efficient communication protocol for wireless microsensor networks

paper_content:

Wireless distributed microsensor systems will enable the reliable monitoring of a variety of environments for both civil and military applications. In this paper, we look at communication protocols, which can have significant impact on the overall energy dissipation of these networks. Based on our findings that the conventional protocols of direct transmission, minimum-transmission-energy, multi-hop routing, and static clustering may not be optimal for sensor networks, we propose LEACH (Low-Energy Adaptive Clustering Hierarchy), a clustering-based protocol that utilizes randomized rotation of local cluster based station (cluster-heads) to evenly distribute the energy load among the sensors in the network. LEACH uses localized coordination to enable scalability and robustness for dynamic networks, and incorporates data fusion into the routing protocol to reduce the amount of information that must be transmitted to the base station. Simulations show the LEACH can achieve as much as a factor of 8 reduction in energy dissipation compared with conventional outing protocols. In addition, LEACH is able to distribute energy dissipation evenly throughout the sensors, doubling the useful system lifetime for the networks we simulated.
---
paper_title: A taxonomy of wireless micro-sensor network models

paper_content:

In future smart environments, wireless sensor networks will play a key role in sensing, collecting, and disseminating information about environmental phenomena. Sensing applications represent a new paradigm for network operation, one that has different goals from more traditional wireless networks. This paper examines this emerging field to classify wireless micro-sensor networks according to different communication functions, data delivery models, and network dynamics. This taxonomy will aid in defining appropriate communication infrastructures for different sensor network application sub-spaces, allowing network designers to choose the protocol architecture that best matches the goals of their application. In addition, this taxonomy will enable new sensor network models to be defined for use in further research in this area.
---
paper_title: GPS-less Low Cost Outdoor Localization For Very Small Devices

paper_content:

Instrumenting the physical world through large networks of wireless sensor nodes, particularly for applications like environmental monitoring of water and soil, requires that these nodes be very small, lightweight, untethered, and unobtrusive. The problem of localization, that is, determining where a given node is physically located in a network, is a challenging one, and yet extremely crucial for many of these applications. Practical considerations such as the small size, form factor, cost and power constraints of nodes preclude the reliance on GPS of all nodes in these networks. We review localization techniques and evaluate the effectiveness of a very simple connectivity metric method for localization in outdoor environments that makes use of the inherent RF communications capabilities of these devices. A fixed number of reference points in the network with overlapping regions of coverage transmit periodic beacon signals. Nodes use a simple connectivity metric, which is more robust to environmental vagaries, to infer proximity to a given subset of these reference points. Nodes localize themselves to the centroid of their proximate reference points. The accuracy of localization is then dependent on the separation distance between two-adjacent reference points and the transmission range of these reference points. Initial experimental results show that the accuracy for 90 percent of our data points is within one-third of the separation distance. However, future work is needed to extend the technique to more cluttered environments.
---
paper_title: Energy-efficient communication protocol for wireless microsensor networks

paper_content:

Wireless distributed microsensor systems will enable the reliable monitoring of a variety of environments for both civil and military applications. In this paper, we look at communication protocols, which can have significant impact on the overall energy dissipation of these networks. Based on our findings that the conventional protocols of direct transmission, minimum-transmission-energy, multi-hop routing, and static clustering may not be optimal for sensor networks, we propose LEACH (Low-Energy Adaptive Clustering Hierarchy), a clustering-based protocol that utilizes randomized rotation of local cluster based station (cluster-heads) to evenly distribute the energy load among the sensors in the network. LEACH uses localized coordination to enable scalability and robustness for dynamic networks, and incorporates data fusion into the routing protocol to reduce the amount of information that must be transmitted to the base station. Simulations show the LEACH can achieve as much as a factor of 8 reduction in energy dissipation compared with conventional outing protocols. In addition, LEACH is able to distribute energy dissipation evenly throughout the sensors, doubling the useful system lifetime for the networks we simulated.
---
paper_title: The cougar approach to in-network query processing in sensor networks

paper_content:

The widespread distribution and availability of small-scale sensors, actuators, and embedded processors is transforming the physical world into a computing platform. One such example is a sensor network consisting of a large number of sensor nodes that combine physical sensing capabilities such as temperature, light, or seismic sensors with networking and computation capabilities. Applications range from environmental control, warehouse inventory, and health care to military environments. Existing sensor networks assume that the sensors are preprogrammed and send data to a central frontend where the data is aggregated and stored for offline querying and analysis. This approach has two major drawbacks. First, the user cannot change the behavior of the system on the fly. Second, conservation of battery power is a major design factor, but a central system cannot make use of in-network programming, which trades costly communication for cheap local computation.In this paper, we introduce the Cougar approach to tasking sensor networks through declarative queries. Given a user query, a query optimizer generates an efficient query plan for in-network query processing, which can vastly reduce resource usage and thus extend the lifetime of a sensor network. In addition, since queries are asked in a declarative language, the user is shielded from the physical characteristics of the network. We give a short overview of sensor networks, propose a natural architecture for a data management system for sensor networks, and describe open research problems in this area.
---
paper_title: Adaptive protocols for information dissemination in wireless sensor networks

paper_content:

In this paper, we present a family of adaptive protocols, called SPIN (Sensor Protocols for Information via Negotiation), that efficiently disseminates information among sensors in an energy-constrained wireless sensor network. Nodes running a SPIN communication protocol name their data using high-level data descriptors, called meta-data. They use meta-data negotiations to eliminate the transmission of redundant data throughout the network. In addition, SPIN nodes can base their communication decisions both upon application-specific knowledge of the data and upon knowledge of the resources that are available to them. This allows the sensors to efficiently distribute data given a limited energy supply. We simulate and analyze the performance of two specific SPIN protocols, comparing them to other possible approaches and a theoretically optimal protocol. We find that the SPIN protocols can deliver 60% more data for a given amount of energy than conventional approaches. We also find that, in terms of dissemination rate and energy usage, the SPlN protocols perform close to the theoretical optimum.
---
paper_title: Directed diffusion: a scalable and robust communication paradigm for sensor networks

paper_content:

Advances in processor, memory and radio technology will enable small and cheap nodes capable of sensing, communication and computation. Networks of such nodes can coordinate to perform distributed sensing of environmental phenomena. In this paper, we explore the directed diffusion paradigm for such coordination. Directed diffusion is datacentric in that all communication is for named data. All nodes in a directed diffusion-based network are application-aware. This enables diffusion to achieve energy savings by selecting empirically good paths and by caching and processing data in-network. We explore and evaluate the use of directed diffusion for a simple remote-surveillance sensor network.
---
paper_title: Constrained random walks on random graphs: routing algorithms for large scale wireless sensor networks

paper_content:

We consider a routing problem in the context of large scale networks with uncontrolled dynamics. A case of uncontrolled dynamics that has been studied extensively is that of mobile nodes, as this is typically the case in cellular and mobile ad-hoc networks. In this paper however we study routing in the presence of a different type of dynamics: nodes do not move, but instead switch between active and inactive states at random times. Our interest in this case is motivated by the behavior of sensor nodes powered by renewable sources, such as solar cells or ambient vibrations. In this paper we formalize the corresponding routing problem as a problem of constructing suitably constrained random walks on random dynamic graphs. We argue that these random walks should be designed so that their resulting invariant distribution achieves a certain load balancing property, and we give simple distributed algorithms to compute the local parameters for the random walks that achieve the sought behavior. A truly novel feature of our formulation is that the algorithms we obtain are able to route messages along all possible routes between a source and a destination node, without performing explicit route discovery/repair computations, and without maintaining explicit state information about available routes at the nodes. To the best of our knowledge, these are the first algorithms that achieve true multipath routing (in a statistical sense), at the complexity of simple stateless operations.
---
paper_title: Negotiation-based Protocols for Disseminating Information in Wireless Sensor Networks

paper_content:

In this paper, we present a family of adaptive protocols, called SPIN (Sensor Protocols for Information via Negotiation), that efficiently disseminate information among sensors in an energy-constrained wireless sensor network. Nodes running a SPIN communication protocol name their data using high-level data descriptors, called meta-data. They use meta-data negotiations to eliminate the transmission of redundant data throughout the network. In addition, SPIN nodes can base their communication decisions both upon application-specific knowledge of the data and upon knowledge of the resources that are available to them. This allows the sensors to efficiently distribute data given a limited energy supply. We simulate and analyze the performance of four specific SPIN protocols: SPIN-PP and SPIN-EC, which are optimized for a point-to-point network, and SPIN-BC and SPIN-RL, which are optimized for a broadcast network. Comparing the SPIN protocols to other possible approaches, we find that the SPIN protocols can deliver 60% more data for a given amount of energy than conventional approaches in a point-to-point network and 80% more data for a given amount of energy in a broadcast network. We also find that, in terms of dissemination rate and energy usage, the SPIN protocols perform close to the theoretical optimum in both point-to-point and broadcast networks.
---
paper_title: The ACQUIRE mechanism for efficient querying in sensor networks

paper_content:

We propose a novel and efficient mechanism for obtaining information in sensor networks which we refer to as ACQUIRE. In ACQUIRE an active query is forwarded through the network, and intermediate nodes use cached local information (within a look-ahead of d hops) in order to partially resolve the query. When the query is fully resolved, a completed response is sent directly back to the querying node. We take a mathematical modelling approach in this paper to calculate the energy costs associated with ACQUIRE. The models permit us to characterize analytically the impact of critical parameters, and compare the performance of ACQUIRE with respect to alternatives such as flooding-based querying (FBQ) and expanding ring search (ERS). We show that with optimal parameter settings, depending on the update frequency, ACQUIRE obtains order of magnitude reduction over FBQ and potentially over 60% reduction over ERS in consumed energy.
---
paper_title: Energy aware routing for low energy ad hoc sensor networks

paper_content:

The recent interest in sensor networks has led to a number of routing schemes that use the limited resources available at sensor nodes more efficiently. These schemes typically try to find the minimum energy path to optimize energy usage at a node. In this paper we take the view that always using lowest energy paths may not be optimal from the point of view of network lifetime and long-term connectivity. To optimize these measures, we propose a new scheme called energy aware routing that uses sub-optimal paths occasionally to provide substantial gains. Simulation results are also presented that show increase in network lifetimes of up to 40% over comparable schemes like directed diffusion routing. Nodes also burn energy in a more equitable way across the network ensuring a more graceful degradation of service with time.
---
paper_title: A scalable solution to minimum cost forwarding in large sensor networks

paper_content:

Wireless sensor networks offer a wide range of challenges to networking research, including unconstrained network scale, limited computing, memory and energy resources, and wireless channel errors. We study the problem of delivering messages from any sensor to an interested client user along the minimum-cost path in a large sensor network. We propose a new cost field based approach to minimum cost forwarding. In the design, we present a novel backoff-based cost field setup algorithm that finds the optimal costs of all nodes to the sink with one single message overhead at each node. Once the field is established, the message, carrying dynamic cost information, flows along the minimum cost path in the cost field. Each intermediate node forwards the message only if it finds itself to be on the optimal path, based on dynamic cost states. Our design does not require an intermediate node to maintain explicit "forwarding path" states. It requires a few simple operations and scales to any network size. We show the correctness and effectiveness of the design by both simulations and analysis.
---
paper_title: The cougar approach to in-network query processing in sensor networks

paper_content:

The widespread distribution and availability of small-scale sensors, actuators, and embedded processors is transforming the physical world into a computing platform. One such example is a sensor network consisting of a large number of sensor nodes that combine physical sensing capabilities such as temperature, light, or seismic sensors with networking and computation capabilities. Applications range from environmental control, warehouse inventory, and health care to military environments. Existing sensor networks assume that the sensors are preprogrammed and send data to a central frontend where the data is aggregated and stored for offline querying and analysis. This approach has two major drawbacks. First, the user cannot change the behavior of the system on the fly. Second, conservation of battery power is a major design factor, but a central system cannot make use of in-network programming, which trades costly communication for cheap local computation.In this paper, we introduce the Cougar approach to tasking sensor networks through declarative queries. Given a user query, a query optimizer generates an efficient query plan for in-network query processing, which can vastly reduce resource usage and thus extend the lifetime of a sensor network. In addition, since queries are asked in a declarative language, the user is shielded from the physical characteristics of the network. We give a short overview of sensor networks, propose a natural architecture for a data management system for sensor networks, and describe open research problems in this area.
---
paper_title: Scalable Information-Driven Sensor Querying and Routing for Ad Hoc Heterogeneous Sensor Networks

paper_content:

This paper describes two novel techniques, information-driven sensor querying IDSQ and constrained anisotropic diffusion routing CADR, for energy-efficient data querying and routing in ad hoc sensor networks for a range of collaborative signal processing tasks. The key idea is to introduce an information utility measure to select which sensors to query and to dynamically guide data routing. This allows us to maximize information gain while minimizing detection latency and bandwidth consumption for tasks such as localization and tracking. Our simulation results have demonstrated that the information-driven querying and routing techniques are more energy efficient, have lower detection latency, and provide anytime algorithms to mitigate risks of link/node failures.
---
paper_title: Energy-efficient communication protocol for wireless microsensor networks

paper_content:

Wireless distributed microsensor systems will enable the reliable monitoring of a variety of environments for both civil and military applications. In this paper, we look at communication protocols, which can have significant impact on the overall energy dissipation of these networks. Based on our findings that the conventional protocols of direct transmission, minimum-transmission-energy, multi-hop routing, and static clustering may not be optimal for sensor networks, we propose LEACH (Low-Energy Adaptive Clustering Hierarchy), a clustering-based protocol that utilizes randomized rotation of local cluster based station (cluster-heads) to evenly distribute the energy load among the sensors in the network. LEACH uses localized coordination to enable scalability and robustness for dynamic networks, and incorporates data fusion into the routing protocol to reduce the amount of information that must be transmitted to the base station. Simulations show the LEACH can achieve as much as a factor of 8 reduction in energy dissipation compared with conventional outing protocols. In addition, LEACH is able to distribute energy dissipation evenly throughout the sensors, doubling the useful system lifetime for the networks we simulated.
---
paper_title: PEGASIS : Power-Efficient Gathering in Sensor Information Systems

paper_content:

Sensor network consisting of nodes with limited battery power and wireless communications are deployed to collect useful information from the field. The main idea in PEGASIS is for each node to receive from and transmit to close neighbors and take turns being the leader for transmission to the BS. This approach distributes the energy load evenly among the sensor nodes in the network. Sensor nodes are randomly deployed in the sensor field, and therefore, the i th node is at a random location. The nodes will be organized to form a chain, which can either be accomplished by the sensor nodes themselves using a greedy algorithm. The algorithm to resolve the unbalanced energy consumption problem caused by long distance data transmission of some nodes in a chain formed by the greedy algorithm.
---
paper_title: APTEEN: A Hybrid Protocol for Efficient Routing and Comprehensive Information Retrieval in Wireless Sensor Networks

paper_content:

Wireless sensor networks with thousands of tiny sensor nodes, are expected to find wide applicability and increasing deployment in coming years, as they enable reliable monitoring and analysis of the environment. In this paper, we propose a hybrid routing protocol (APTEEN) which allows for comprehensive information retrieval. The nodes in such a network not only react to time-critical situations, but also give an overall picture of the network at periodic intervals in a very energy efficient manner. Such a network enables the user to request past, present and future data from the network in the form of historical, one-time and persistent queries respectively. We evaluated the performance of these protocols and observe that these protocols are observed to outperform existing protocols in terms of energy consumption and longevity of the network.
---
paper_title: TEEN: a routing protocol for enhanced efficiency in wireless sensor networks

paper_content:

Wireless sensor networks are expected to find wide applicability and increasing deployment in the near future. In this paper, we propose a formal classification of sensor networks, based on their mode of functioning, as proactive and reactive networks. Reactive networks, as opposed to passive data collecting proactive networks, respond immediately to changes in the relevant parameters of interest. We also introduce a new energy efficient protocol, TEEN (Threshold sensitive Energy Efficient sensor Network protocol) for reactive networks. We evaluate the performance of our protocol for a simple temperature sensing application. In terms of energy efficiency, our protocol has been observed to outperform existing conventional sensor network protocols.
---
paper_title: An architecture for building self-configurable systems

paper_content:

Developing wireless sensor networks can enable information gathering, information processing and reliable monitoring of a variety of environments for both civil and military applications. It is however necessary to agree upon a basic architecture for building sensor network applications. This paper presents a general classification of sensor network applications based on their network configurations and discusses some of their architectural requirements. We propose a generic architecture for a specific subclass of sensor applications which we define as self-configurable systems where a large number of sensors coordinate amongst themselves to achieve a large sensing task. Throughout this paper we assume a certain subset of the sensors to be immobile. This paper lists the general architectural and infra-structural components necessary for building this class of sensor applications. Given the various architectural components, we present an algorithm that self-organizes the sensors into a network in a transparent manner. Some of the basic goals of our algorithm include minimizing power utilization, localizing operations and tolerating node and link failures.
---
paper_title: Minimum energy mobile wireless networks

paper_content:

We describe a distributed position-based network protocol optimized for minimum energy consumption in mobile wireless networks that support peer-to-peer communications. Given any number of randomly deployed nodes over an area, we show that a simple local optimization scheme executed at each node guarantees strong connectivity of the entire network and attains the global minimum energy solution for the stationary case. Due to its localized nature, this protocol proves to be self-reconfiguring and stays close to the minimum energy solution when applied to the case of mobile nodes. Our simulations verify its performance.
---
paper_title: Data aggregation in wireless sensor networks - exact and approximate algorithms

paper_content:

A fundamental challenge in the design of wireless sensor networks (WSNs) is to maximize their lifetimes. Data aggregation has emerged as a basic approach in WSNs in order to reduce the number of transmissions of sensor nodes, and hence minimizing the overall power consumption in the network. We study optimal data aggregation in WSNs. Data aggregation is affected by several factors, such as the placement of aggregation points, the aggregation function, and the density of sensors in the network. The determination of an optimal selection of aggregation points is thus extremely important. We present exact and approximate algorithms to find the minimum number of aggregation points in order to maximize the network lifetime. Our algorithms use a fixed virtual wireless backbone that is built on top of the physical topology. We also study the tradeoffs between energy savings and the potential delay involved in the data aggregation process. Numerical results show that our approach provides substantial energy savings.
---
paper_title: Energy aware routing for low energy ad hoc sensor networks

paper_content:

The recent interest in sensor networks has led to a number of routing schemes that use the limited resources available at sensor nodes more efficiently. These schemes typically try to find the minimum energy path to optimize energy usage at a node. In this paper we take the view that always using lowest energy paths may not be optimal from the point of view of network lifetime and long-term connectivity. To optimize these measures, we propose a new scheme called energy aware routing that uses sub-optimal paths occasionally to provide substantial gains. Simulation results are also presented that show increase in network lifetimes of up to 40% over comparable schemes like directed diffusion routing. Nodes also burn energy in a more equitable way across the network ensuring a more graceful degradation of service with time.
---
paper_title: Lightweight sensing and communication protocols for target enumeration and aggregation

paper_content:

The development of lightweight sensing andcommunication protocols is a key requirement for designing resource constrained sensor networks. This paper introduces a set of efficient protocols and algorithms, DAM, EBAM, and EMLAM, for constructing and maintaining sensor aggregates that collectively monitor target activity in the environment. A sensor aggregate comprises those nodes in a network that satisfy a grouping predicate for a collaborative processing task. The parameters of the predicate depend on the task and its resource requirements. Since the foremost purpose of a sensor network is to selectively gather information about the environment, the formation of appropriate sensor aggregates is crucial for optimally allocating resources to sensing and communication tasks.This paper makes minimal assumptions about node onboard processing and communication capabilities so as to allow possible implementations on resource-constrained hardware. Factors affecting protocol performance are discussed. The paper presents simulation results showing how the protocol performance varies as key network and task parameters are varied. It also provides probabilistic analyses of network behavior consistent with the simulation results. The protocols have been experimentally validated on a sensor network testbed comprising 25 Berkeley MICA sensor motes.
---
paper_title: Minimum-energy mobile wireless networks revisited

paper_content:

We propose a protocol that, given a communication network, computes a subnetwork such that, for every pair $(u,v)$ of nodes connected in the original network, there is a minimum-energy path between $u$ and $v$ in the subnetwork (where a minimum-energy path is one that allows messages to be transmitted with a minimum use of energy). The network computed by our protocol is in general a subnetwork of the one computed by the protocol given in [13]. Moreover, our protocol is computationally simpler. We demonstrate the performance improvements obtained by using the subnetwork computed by our protocol through simulation.
---
paper_title: GPS-free positioning in mobile ad-hoc networks

paper_content:

We consider the problem of node positioning in ad-hoc networks. We propose a distributed, infrastructure-free positioning algorithm that does not rely on Global Positioning System (GPS). The algorithm uses the distances between the nodes to build a relative coordinate system in which the node positions are computed in two dimensions. The main contribution of this work is to define and compute relative positions of the nodes in an ad-hoc network without using GPS. We further explain how the proposed approach can be applied to wide area ad-hoc networks.
---
paper_title: Geographical and energy aware routing: A recursive data dissemination protocol for wireless sensor networks

paper_content:

Future sensor networks will be composed of a large number of densely deployed sensors/actuators. A key feature of such networks is that their nodes are untethered and unattended. Consequently, energy efficiency is an important design consideration for these networks. Motivated by the fact that sensor network queries may often be geographical, we design and evaluate an energy efficient routing algorithm that propagates a query to the appropriate geographical region, without flooding. The proposed Geographic and Energy Aware Routing (GEAR) algorithm uses energy aware neighbor selection to route a packet towards the target region and Recursive Geographic Forwarding or Restricted Flooding algorithm to disseminate the packet inside the destina-
---
paper_title: Span: an energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks

paper_content:

This paper presents Span, a power saving technique for multi-hop ad hoc wireless networks that reduces energy consumption without significantly diminishing the capacity or connectivity of the network. Span builds on the observation that when a region of a sharedchannel wireless network has a sufficient density of nodes, only a small number of them need be on at any time to forward traffic for active connections. Span is a distributed, randomized algorithm where nodes make local decisions on whether to sleep, or to join a forwarding backbone as a coordinator. Each node bases its decision on an estimate of how many of its neighbors will benefit from it being awake, and the amount of energy available to it. We give a randomized algorithm where coordinators rotate with time, demonstrating how localized node decisions lead to a connected, capacity-preserving global topology. Improvement in system lifetime due to Span increases as the ratio of idle-to-sleep energy consumption increases. Our simulations show that with a practical energy model, system lifetime of an 802.11 network in power saving mode with Span is a factor of two better than without. Additionally, Span also improves communication latency and capacity.
---
paper_title: GPS-less Low Cost Outdoor Localization For Very Small Devices

paper_content:

Instrumenting the physical world through large networks of wireless sensor nodes, particularly for applications like environmental monitoring of water and soil, requires that these nodes be very small, lightweight, untethered, and unobtrusive. The problem of localization, that is, determining where a given node is physically located in a network, is a challenging one, and yet extremely crucial for many of these applications. Practical considerations such as the small size, form factor, cost and power constraints of nodes preclude the reliance on GPS of all nodes in these networks. We review localization techniques and evaluate the effectiveness of a very simple connectivity metric method for localization in outdoor environments that makes use of the inherent RF communications capabilities of these devices. A fixed number of reference points in the network with overlapping regions of coverage transmit periodic beacon signals. Nodes use a simple connectivity metric, which is more robust to environmental vagaries, to infer proximity to a given subset of these reference points. Nodes localize themselves to the centroid of their proximate reference points. The accuracy of localization is then dependent on the separation distance between two-adjacent reference points and the transmission range of these reference points. Initial experimental results show that the accuracy for 90 percent of our data points is within one-third of the separation distance. However, future work is needed to extend the technique to more cluttered environments.
---
paper_title: Directed diffusion: a scalable and robust communication paradigm for sensor networks

paper_content:

Advances in processor, memory and radio technology will enable small and cheap nodes capable of sensing, communication and computation. Networks of such nodes can coordinate to perform distributed sensing of environmental phenomena. In this paper, we explore the directed diffusion paradigm for such coordination. Directed diffusion is datacentric in that all communication is for named data. All nodes in a directed diffusion-based network are application-aware. This enables diffusion to achieve energy savings by selecting empirically good paths and by caching and processing data in-network. We explore and evaluate the use of directed diffusion for a simple remote-surveillance sensor network.
---
paper_title: Highly-resilient, energy-efficient multipath routing in wireless sensor networks

paper_content:

Previously proposed sensor network data dissemination schemes require periodic low-rate flooding of data in order to allow recovery from failure. We consider constructing two kinds of multipaths to enable energy efficient recovery from failure of the shortest path between source and sink. Disjoint multipath has been studied in the literature. We propose a novel braided multipath scheme, which results in several partially disjoint multipath schemes. We find that braided multipaths are a viable alternative for energy-efficient recovery from isolated and patterned failures.
---
paper_title: Energy aware routing for low energy ad hoc sensor networks

paper_content:

The recent interest in sensor networks has led to a number of routing schemes that use the limited resources available at sensor nodes more efficiently. These schemes typically try to find the minimum energy path to optimize energy usage at a node. In this paper we take the view that always using lowest energy paths may not be optimal from the point of view of network lifetime and long-term connectivity. To optimize these measures, we propose a new scheme called energy aware routing that uses sub-optimal paths occasionally to provide substantial gains. Simulation results are also presented that show increase in network lifetimes of up to 40% over comparable schemes like directed diffusion routing. Nodes also burn energy in a more equitable way across the network ensuring a more graceful degradation of service with time.
---
paper_title: Trade-off between traffic overhead and reliability in multipath routing for wireless sensor networks

paper_content:

In wireless sensor networks (WSN) data produced by one or more sources usually has to be routed through several intermediate nodes to reach the destination. Problems arise when intermediate nodes fail to forward the incoming messages. The reliability of the system can be increased by providing several paths from source to destination and sending the same packet through each of them (the algorithm is known as multipath routing). Using this technique, the traffic increases significantly. In this paper, we analyze a new mechanism that enables the tradeoff between the amount of traffic and the reliability. The data packet is split in k subpackets (k = number of disjoined paths from source to destination). If only Ek subpackets (Ek < k) are necessary to rebuild the original data packet (condition obtained by adding redundancy to each subpacket), then the trade-off between traffic and reliability can be controlled.
---
paper_title: Directed diffusion: a scalable and robust communication paradigm for sensor networks

paper_content:

Advances in processor, memory and radio technology will enable small and cheap nodes capable of sensing, communication and computation. Networks of such nodes can coordinate to perform distributed sensing of environmental phenomena. In this paper, we explore the directed diffusion paradigm for such coordination. Directed diffusion is datacentric in that all communication is for named data. All nodes in a directed diffusion-based network are application-aware. This enables diffusion to achieve energy savings by selecting empirically good paths and by caching and processing data in-network. We explore and evaluate the use of directed diffusion for a simple remote-surveillance sensor network.
---
paper_title: Adaptive protocols for information dissemination in wireless sensor networks

paper_content:

In this paper, we present a family of adaptive protocols, called SPIN (Sensor Protocols for Information via Negotiation), that efficiently disseminates information among sensors in an energy-constrained wireless sensor network. Nodes running a SPIN communication protocol name their data using high-level data descriptors, called meta-data. They use meta-data negotiations to eliminate the transmission of redundant data throughout the network. In addition, SPIN nodes can base their communication decisions both upon application-specific knowledge of the data and upon knowledge of the resources that are available to them. This allows the sensors to efficiently distribute data given a limited energy supply. We simulate and analyze the performance of two specific SPIN protocols, comparing them to other possible approaches and a theoretically optimal protocol. We find that the SPIN protocols can deliver 60% more data for a given amount of energy than conventional approaches. We also find that, in terms of dissemination rate and energy usage, the SPlN protocols perform close to the theoretical optimum.
---
paper_title: Negotiation-based Protocols for Disseminating Information in Wireless Sensor Networks

paper_content:

In this paper, we present a family of adaptive protocols, called SPIN (Sensor Protocols for Information via Negotiation), that efficiently disseminate information among sensors in an energy-constrained wireless sensor network. Nodes running a SPIN communication protocol name their data using high-level data descriptors, called meta-data. They use meta-data negotiations to eliminate the transmission of redundant data throughout the network. In addition, SPIN nodes can base their communication decisions both upon application-specific knowledge of the data and upon knowledge of the resources that are available to them. This allows the sensors to efficiently distribute data given a limited energy supply. We simulate and analyze the performance of four specific SPIN protocols: SPIN-PP and SPIN-EC, which are optimized for a point-to-point network, and SPIN-BC and SPIN-RL, which are optimized for a broadcast network. Comparing the SPIN protocols to other possible approaches, we find that the SPIN protocols can deliver 60% more data for a given amount of energy than conventional approaches in a point-to-point network and 80% more data for a given amount of energy in a broadcast network. We also find that, in terms of dissemination rate and energy usage, the SPIN protocols perform close to the theoretical optimum in both point-to-point and broadcast networks.
---
paper_title: SPEED: a stateless protocol for real-time communication in sensor networks

paper_content:

In this paper, we present a real-time communication protocol for sensor networks, called SPEED. The protocol provides three types of real-time communication services, namely, real-time unicast, real-time area-multicast and real-time area-anycast. SPEED is specifically tailored to be a stateless, localized algorithm with minimal control overhead End-to-end soft real-time communication is achieved by maintaining a desired delivery speed across the sensor network through a novel combination of feedback control and non-deterministic geographic forwarding. SPEED is a highly efficient and scalable protocol for sensor networks where the resources of each node are scarce. Theoretical analysis, simulation experiments and a real implementation on Berkeley motes are provided to validate our claims.
---
paper_title: Protocols for self-organization of a wireless sensor network

paper_content:

We present a suite of algorithms for self-organization of wireless sensor networks in which there is a scalably large number of mainly static nodes with highly constrained energy resources. The protocols further support slow mobility by a subset of the nodes, energy-efficient routing, and formation of ad hoc subnetworks for carrying out cooperative signal processing functions among a set of the nodes.
---
paper_title: Adaptive protocols for information dissemination in wireless sensor networks

paper_content:

In this paper, we present a family of adaptive protocols, called SPIN (Sensor Protocols for Information via Negotiation), that efficiently disseminates information among sensors in an energy-constrained wireless sensor network. Nodes running a SPIN communication protocol name their data using high-level data descriptors, called meta-data. They use meta-data negotiations to eliminate the transmission of redundant data throughout the network. In addition, SPIN nodes can base their communication decisions both upon application-specific knowledge of the data and upon knowledge of the resources that are available to them. This allows the sensors to efficiently distribute data given a limited energy supply. We simulate and analyze the performance of two specific SPIN protocols, comparing them to other possible approaches and a theoretically optimal protocol. We find that the SPIN protocols can deliver 60% more data for a given amount of energy than conventional approaches. We also find that, in terms of dissemination rate and energy usage, the SPlN protocols perform close to the theoretical optimum.
---
paper_title: Directed diffusion: a scalable and robust communication paradigm for sensor networks

paper_content:

Advances in processor, memory and radio technology will enable small and cheap nodes capable of sensing, communication and computation. Networks of such nodes can coordinate to perform distributed sensing of environmental phenomena. In this paper, we explore the directed diffusion paradigm for such coordination. Directed diffusion is datacentric in that all communication is for named data. All nodes in a directed diffusion-based network are application-aware. This enables diffusion to achieve energy savings by selecting empirically good paths and by caching and processing data in-network. We explore and evaluate the use of directed diffusion for a simple remote-surveillance sensor network.
---
paper_title: Wireless Personal Communications Systems

paper_content:

List of Figures XV. List of Tables XXIII. Preface XXV. Acknowledgments XXIX. 1. What is Personal Communications? The Person in Personal Communications. Essential Ingredients. The S in PCS. Two Telephone Calls. Conventional Call. Cellular Call. Technical Challenges. Mobility. Ether. Energy. Evolution of Personal Communications. Cellular Networks. Cordless Telephones. Mobile Computing. Paging. Current Personal Communications. Systems Presented in This Book. Other Wireless Communications Systems. Mobile Satellite Systems. Wireless Local Area Networks. Wireless Local Loops. Wireless Data Networks. Review Exercises. 2. Principles of Personal Communications. Presentations of Practical Systems. Information Services for People. Telephone Services. Short Message Services. Voiceband Data and Facsimile. Direct Digital Access. Closed User Groups. Telemetry. Wireless Local Loops. Video and Other Broadband Services. Figures of Merit: Design Goals. Summary of Figures of Merit. Terminal Price. Terminal Size and Weight. Service Price. Range of Services. Coverage Area. Roaming. User Interface. Call Blocking. Setup Time. Transmission Quality. Privacy. Mobility. Call Dropping. Battery Life. Modes of Operation. Infrastructure Cost. Cell Radius. Spectrum Efficiency. Network Security. Early Deployment and Adaptability. System Operations. User Information Transport. Mobility Management. Authentication and Encryption. Call Management. Radio Resources Management. Operations, Administration, and Maintenance (OA&M). A Framework for Studying Personal Communications Systems. Architecture. Air Interface Layers. Radio Transmission. Logical Channels. Messages. Network Operations. Status. Review Exercises. 3. Analog Cellular Communications AMPS System. Background and Goals. Architecture. Network Elements. Identification Codes. Radio Transmission. Frequency Bands and Physical Channels. Radiated Power. Analog Signal Processing. Supervisory Audio Tone and Supervisory Tone. Digital Signals. Spectrum Efficiency. Logical Channels. Logical Channel Categories. Block Codes. Logical Channel Formats. Messages. Message Structure. Message Content. AMPS Protocol Summary. Tasks Performed by AMPS Terminals. Initialization. Idle. Access. Conversation. Phone Call Examples. Network Operations. Mobility Management. Authentication. Radio Resources Management. AMPS Status. Capacity. Roaming. Network Security. Non-Voice Services. Review Exercises. 4. North American Intersystem Operations. Background and Goals. The Situation Prior to IS-41. The Role of IS-41. Services and Design Goals. Architecture. Messages. Automatic Roaming. Mobility Management. Authentication. Call Management. Intersystem Handoff. Handoff Categories. Handoff Protocols. Other Intersystem Handoff Procedures. Status of IS-41. Review Exercises. 5. North American Cellular System Based on Time Division Multiple Access. Background and Goals. Architecture. Radio Transmission. Physical Channels. Modulation. Radiated Power. Spectrum Efficiency. Logical Channels. Digital Traffic Channel (DTCH). Digital Control Channel (DCCH). Messages. Messages on AMPS Logical Channels. Messages Carried on Associated Control Channels. Messages Carried on Digital Control Channels. Network Operations. Authentication and Privacy. Radio Resources Management: Mobile-Assisted Handoff (MAHO). Call Management. Mobility Management. Status of NA-TDMA. Review Exercises. 6. North American Cellular System Based on Code Division Multiple Access. Background and Goals. Architecture. Radio Transmission. Reverse-Direction Radio Transmission. Forward Link Radio Transmission. Spectrum Efficiency. Logical Channels. Pilot Channel. Sync Channel. Paging Channel. Access Channel. CDMA Traffic Channels. Messages. Message Structure. Acknowledgment Messages. Message Content. Network Operations. Radio Resources Management. Mobility Management. Authentication and Privacy. Operations, Administration, and Maintenance. Status of CDMA. Review Exercises. 7. GSM: Pan-European Digital Cellular System. Background and Goals. Architecture. Radio Transmission. Physical Channels. GSM Bit Stream. Slow Frequency Hopping. Radiated Power. Spectrum Efficiency. Logical Channels. Broadcast Channels and Common Control Channels. Stand-Alone Dedicated Control Channel (SDCCH). Traffic Channels (TCH). Messages. Message Structure. Message Content. Network Operations. Call to a GSM Terminal. Location-Based Registration. Mobile-Assisted Handover. Status of GSM. Review Exercises. 8. Low-Tier Personal Communications Systems. Cordless Telephone, Second Generation (CT2). Architecture. Radio Transmission. Logical Channels. Network Operations. Digital European Cordless Telecommunications (DECT). Architecture. Radio Transmission. Logical Channels. Network Operations. Personal Handyphone System (PHS). Network Architecture. Radio Transmission. Logical Channels. Network Operations. Personal Access Communications System (PACS). Architecture. Radio Transmission. Logical Channels. Network Operations. Review Exercises. 9. Science and Technology Tutorials. Multiple Access. Mobile Radio Signals. Attenuation Due to Distance. Slow Fading Due to Random Environmental Effects. Rayleigh Fading Due to Motion of Terminals. Intersymbol Interference Due to Different Signal Paths. Technology Implications. Spectrum Efficiency. Compression Efficiency and Reuse Factor. Reuse Planning. Channel Coding. Block Codes. Convolutional Codes. Interleaving. Adaptive Equalization. Linear Prediction Coding. CDMA Soft Capacity. Walsh Hadamard Matrix. Open Systems Interconnection. Integrated Services Digital Networks. Signaling System Number 7. Review Exercises. Appendix A: Personal Communications Symbols and Abbreviations. Appendix B: High-Tier Systems. Appendix C: Low-Tier Systems. Appendix D: Glossary of Personal Communications Terms. References and Bibliography. Index.
---
paper_title: Scalable coordination for wireless sensor networks: Selfconfiguring localization systems

paper_content:

Pervasive networks of micro-sensors and actuators offer to revolutionize the ways in which we understand and construct complex physical systems. Sensor networks must be scalable, long-lived and robust systems, overcoming energy limitations and a lack of pre-installed infrastructure. We explore three themes in the design of self-configuring sensor networks: tuning density to trade operational quality against lifetime; using multiple sensor modalities to obtain robust measurements; and exploiting fixed environmental characteristics. We illustrate these themes through the problem of localization, which is a key building block for sensor systems that itself requires coordination.
---
paper_title: Data aggregation in wireless sensor networks - exact and approximate algorithms

paper_content:

A fundamental challenge in the design of wireless sensor networks (WSNs) is to maximize their lifetimes. Data aggregation has emerged as a basic approach in WSNs in order to reduce the number of transmissions of sensor nodes, and hence minimizing the overall power consumption in the network. We study optimal data aggregation in WSNs. Data aggregation is affected by several factors, such as the placement of aggregation points, the aggregation function, and the density of sensors in the network. The determination of an optimal selection of aggregation points is thus extremely important. We present exact and approximate algorithms to find the minimum number of aggregation points in order to maximize the network lifetime. Our algorithms use a fixed virtual wireless backbone that is built on top of the physical topology. We also study the tradeoffs between energy savings and the potential delay involved in the data aggregation process. Numerical results show that our approach provides substantial energy savings.
---
paper_title: An energy efficient hierarchical clustering algorithm for wireless sensor networks

paper_content:

A wireless network consisting of a large number of small sensors with low-power transceivers can be an effective tool for gathering data in a variety of environments. The data collected by each sensor is communicated through the network to a single processing center that uses all reported data to determine characteristics of the environment or detect an event. The communication or message passing process must be designed to conserve the limited energy resources of the sensors. Clustering sensors into groups, so that sensors communicate information only to clusterheads and then the clusterheads communicate the aggregated information to the processing center, may save energy. In this paper, we propose a distributed, randomized clustering algorithm to organize the sensors in a wireless sensor network into clusters. We then extend this algorithm to generate a hierarchy of clusterheads and observe that the energy savings increase with the number of levels in the hierarchy. Results in stochastic geometry are used to derive solutions for the values of parameters of our algorithm that minimize the total energy spent in the network when all sensors report data through the clusterheads to the processing center.
---
paper_title: Secure routing in wireless sensor networks: attacks and countermeasures

paper_content:

We consider routing security in wireless sensor networks. Many sensor network routing protocols have been proposed, but none of them have been designed with security as a goal. We propose security goals for routing in sensor networks, show how attacks against ad-hoc and peer-to-peer networks can be adapted into powerful attacks against sensor networks, introduce two classes of novel attacks against sensor networks sinkholes and HELLO floods, and analyze the security of all the major sensor network routing protocols. We describe crippling attacks against all of them and suggest countermeasures and design considerations. This is the first such analysis of secure routing in sensor networks.
---
paper_title: SPINS: security protocols for sensor networks

paper_content:

As sensor networks edge closer towards wide-spread deployment, security issues become a central concern. So far, much research has focused on making sensor networks feasible and useful, and has not concentrated on security. We present a suite of security building blocks optimized for resource-constrained environments and wireless communication. SPINS has two secure building blocks: SNEP and μTESLA SNEP provides the following important baseline security primitives: Data confidentiality, two-party data authentication, and data freshness. A particularly hard problem is to provide efficient broadcast authentication, which is an important mechanism for sensor networks. μTESLA is a new protocol which provides authenticated broadcast for severely resource-constrained environments. We implemented the above protocols, and show that they are practical even on minimal hardware: the performance of the protocol suite easily matches the data rate of our network. Additionally, we demonstrate that the suite can be used for building higher level protocols.
---
paper_title: Trade-off between traffic overhead and reliability in multipath routing for wireless sensor networks

paper_content:

In wireless sensor networks (WSN) data produced by one or more sources usually has to be routed through several intermediate nodes to reach the destination. Problems arise when intermediate nodes fail to forward the incoming messages. The reliability of the system can be increased by providing several paths from source to destination and sending the same packet through each of them (the algorithm is known as multipath routing). Using this technique, the traffic increases significantly. In this paper, we analyze a new mechanism that enables the tradeoff between the amount of traffic and the reliability. The data packet is split in k subpackets (k = number of disjoined paths from source to destination). If only Ek subpackets (Ek < k) are necessary to rebuild the original data packet (condition obtained by adding redundancy to each subpacket), then the trade-off between traffic and reliability can be controlled.
---
paper_title: Protocols for self-organization of a wireless sensor network

paper_content:

We present a suite of algorithms for self-organization of wireless sensor networks in which there is a scalably large number of mainly static nodes with highly constrained energy resources. The protocols further support slow mobility by a subset of the nodes, energy-efficient routing, and formation of ad hoc subnetworks for carrying out cooperative signal processing functions among a set of the nodes.
---
paper_title: GPS-less Low Cost Outdoor Localization For Very Small Devices

paper_content:

Instrumenting the physical world through large networks of wireless sensor nodes, particularly for applications like environmental monitoring of water and soil, requires that these nodes be very small, lightweight, untethered, and unobtrusive. The problem of localization, that is, determining where a given node is physically located in a network, is a challenging one, and yet extremely crucial for many of these applications. Practical considerations such as the small size, form factor, cost and power constraints of nodes preclude the reliance on GPS of all nodes in these networks. We review localization techniques and evaluate the effectiveness of a very simple connectivity metric method for localization in outdoor environments that makes use of the inherent RF communications capabilities of these devices. A fixed number of reference points in the network with overlapping regions of coverage transmit periodic beacon signals. Nodes use a simple connectivity metric, which is more robust to environmental vagaries, to infer proximity to a given subset of these reference points. Nodes localize themselves to the centroid of their proximate reference points. The accuracy of localization is then dependent on the separation distance between two-adjacent reference points and the transmission range of these reference points. Initial experimental results show that the accuracy for 90 percent of our data points is within one-third of the separation distance. However, future work is needed to extend the technique to more cluttered environments.
---

Title: Routing Techniques in Wireless Sensor Networks: A Survey
Section 1: Introduction
Description 1: Introduce the background, importance, and challenges of routing techniques in Wireless Sensor Networks (WSNs) and outline the structure of the survey.

Section 2: Routing Challenges and Design Issues in WSNs
Description 2: Discuss the main challenges and issues that affect the design and performance of routing protocols in WSNs.

Section 3: Routing Protocols in WSNs
Description 3: Present a comprehensive survey of the various routing protocols in WSNs, categorized based on network structure and protocol operation.

Section 4: Network Structure Based Protocols
Description 4: Detail the routing protocols based on network structure, including flat, hierarchical, and location-based routing.

Section 5: Flat Routing
Description 5: Describe routing protocols where all nodes have equal roles and the network is flat, including data-centric protocols like SPIN and Directed Diffusion.

Section 6: Hierarchical Routing
Description 6: Explain hierarchical or cluster-based routing techniques that aim to enhance scalability and energy efficiency, including protocols like LEACH, PEGASIS, TEEN, and APTEEN.

Section 7: Location Based Routing Protocols
Description 7: Describe routing protocols that utilize geographic information to route data, including protocols like Geographic Adaptive Fidelity (GAF) and Geographic and Energy Aware Routing (GEAR).

Section 8: Routing Protocols based on Protocol Operation
Description 8: Outline routing protocols based on their operational characteristics, such as multipath, query-based, negotiation-based, QoS-based, and coherent/non-coherent processing.

Section 9: Future Research Directions
Description 9: Summarize future research trends and open issues in routing techniques for WSNs, including energy efficiency, QoS, secure routing, and the integration with wired networks.

Section 10: Conclusions
Description 10: Provide final remarks summarizing the survey, highlighting the main findings, and mentioning the potential for future work in routing techniques for WSNs.