Routing Protocols in Wireless Sensor Networks - A Survey
---
paper_title: Wireless Sensor Networks: A Networking Perspective

paper_content:

Learn the fundamental concepts, major challenges, and effective solutions in wireless sensor networking This book provides a comprehensive and systematic introduction to the fundamental concepts, major challenges, and effective solutions in wireless sensor networking (WSN). Distinguished from other books, it focuses on the networking aspects of WSNs and covers the most important networking issues, including network architecture design, medium access control, routing and data dissemination, node clustering, node localization, query processing, data aggregation, transport and quality of service, time synchronization, network security, and sensor network standards. With contributions from internationally renowned researchers, Wireless Sensor Networks expertly strikes a balance between fundamental concepts and state-of-the-art technologies, providing readers with unprecedented insights into WSNs from a networking perspective. It is essential reading for a broad audience, including academic researchers, research engineers, and practitioners in industry. It is also suitable as a textbook or supplementary reading for electrical engineering, computer engineering, and computer science courses at the graduate level.
---
paper_title: Energy Efficient Homogenous Clustering Algorithm for Wireless Sensor Networks

paper_content:

Radio transmission and reception consumes a lot of energy in a wireless sensor network (WSN), which are made of low-cost, low-power, small in size, and multifunctional sensor nodes. Thus, one of the important issues in wireless sensor network is the inherent limited battery power within the sensor nodes. Therefore, battery power is crucial parameter in the algorithm design in maximizing the lifespan of sensor nodes. It is also preferable to distribute the energy dissipated throughout the wireless sensor network in order to maximize overall network performance. Much research has been done in recent years in the area of low power routing protocol, but, there are still many design options open for improvement, and for further research targeted to the specific applications, need to be done. In this paper, we propose a new approach of an energy-efficient homogeneous clustering algorithm for wireless sensor networks in which the lifespan of the network is increased by ensuring a homogeneous distribution of nodes in the clusters. In this clustering algorithm, energy efficiency is distributed and network performance is improved by selecting cluster heads on the basis of (i) the residual energy of existing cluster heads, (ii) holdback value, and (iii) nearest hop distance of the node. In the proposed clustering algorithm, the cluster members are uniformly distributed and the life of the network is further extended.
---
paper_title: Wireless Sensor Networks: A Networking Perspective

paper_content:

Learn the fundamental concepts, major challenges, and effective solutions in wireless sensor networking This book provides a comprehensive and systematic introduction to the fundamental concepts, major challenges, and effective solutions in wireless sensor networking (WSN). Distinguished from other books, it focuses on the networking aspects of WSNs and covers the most important networking issues, including network architecture design, medium access control, routing and data dissemination, node clustering, node localization, query processing, data aggregation, transport and quality of service, time synchronization, network security, and sensor network standards. With contributions from internationally renowned researchers, Wireless Sensor Networks expertly strikes a balance between fundamental concepts and state-of-the-art technologies, providing readers with unprecedented insights into WSNs from a networking perspective. It is essential reading for a broad audience, including academic researchers, research engineers, and practitioners in industry. It is also suitable as a textbook or supplementary reading for electrical engineering, computer engineering, and computer science courses at the graduate level.
---
paper_title: A survey on routing protocols for wireless sensor networks

paper_content:

Recent advances in wireless sensor networks have led to many new protocols specifically designed for sensor networks where energy awareness is an essential consideration. Most of the attention, however, has been given to the routing protocols since they might differ depending on the application and network architecture. This paper surveys recent routing protocols for sensor networks and presents a classification for the various approaches pursued. The three main categories explored in this paper are data-centric, hierarchical and location-based. Each routing protocol is described and discussed under the appropriate category. Moreover, protocols using contemporary methodologies such as network flow and quality of service modeling are also discussed. The paper concludes with open research issues. � 2003 Elsevier B.V. All rights reserved.
---
paper_title: Routing Techniques in Wireless Sensor Networks: A Survey

paper_content:

Wireless sensor networks consist of small nodes with sensing, computation, and wireless communications capabilities. Many routing, power management, and data dissemination protocols have been specifically designed for WSNs where energy awareness is an essential design issue. Routing protocols in WSNs might differ depending on the application and network architecture. In this article we present a survey of state-of-the-art routing techniques in WSNs. We first outline the design challenges for routing protocols in WSNs followed by a comprehensive survey of routing techniques. Overall, the routing techniques are classified into three categories based on the underlying network structure: flit, hierarchical, and location-based routing. Furthermore, these protocols can be classified into multipath-based, query-based, negotiation-based, QoS-based, and coherent-based depending on the protocol operation. We study the design trade-offs between energy and communication overhead savings in every routing paradigm. We also highlight the advantages and performance issues of each routing technique. The article concludes with possible future research areas.
---
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: 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: Convex position estimation in wireless sensor networks

paper_content:

A method for estimating unknown node positions in a sensor network based exclusively on connectivity-induced constraints is described. Known peer-to-peer communication in the network is modeled as a set of geometric constraints on the node positions. The global solution of a feasibility problem for these constraints yields estimates for the unknown positions of the nodes in the network. Providing that the constraints are tight enough, simulation illustrates that this estimate becomes close to the actual node positions. Additionally, a method for placing rectangular bounds around the possible positions for all unknown nodes in the network is given. The area of the bounding rectangles decreases as additional or tighter constraints are included in the problem. Specific models are suggested and simulated for isotropic and directional communication, representative of broadcast-based and optical transmission respectively, though the methods presented are not limited to these simple cases.
---
paper_title: RADAR: an in-building RF-based user location and tracking system

paper_content:

The proliferation of mobile computing devices and local-area wireless networks has fostered a growing interest in location-aware systems and services. In this paper we present RADAR, a radio-frequency (RF)-based system for locating and tracking users inside buildings. RADAR operates by recording and processing signal strength information at multiple base stations positioned to provide overlapping coverage in the area of interest. It combines empirical measurements with signal propagation modeling to determine user location and thereby enable location-aware services and applications. We present experimental results that demonstrate the ability of RADAR to estimate user location with a high degree of accuracy.
---
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: Routing on a curve

paper_content:

Relentless progress in hardware technology and recent advances in sensor technology, and wireless networking have made it feasible to deploy large scale, dense ad-hoc networks. These networks together with sensor technology can be considered as the enablers of emerging models of computing such as embedded computing, ubiquitous computing, or pervasive computing. In this paper, we propose a new paradigm called trajectory based forwarding (or TBF), which is a generalization of source based routing and Cartesian routing. We argue that TBF is an ideal technique for routing in dense ad-hoc networks. Trajectories are a natural namespace for describing route paths when the topology of the network matches the topography of the physical surroundings in which it is deployed which by very definition is embedded computing.We show how simple trajectories can be used in implementing important networking protocols such as flooding, discovery, and network management. Trajectory routing is very effective in implementing many networking functions in a quick and approximate way, as it needs very few support services. We discuss several research challenges in the design of network protocols that use specific trajectories for forwarding packets.
---
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: 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: On greedy geographic routing algorithms in sensing-covered networks

paper_content:

Greedy geographic routing is attractive in wireless sensor networks due to its efficiency and scalability. However, greedy geographic routing may incur long routing paths or even fail due to routing voids on random network topologies. We study greedy geographic routing in an important class of wireless sensor networks that provide sensing coverage over a geographic area (e.g., surveillance or object tracking systems). Our geometric analysis and simulation results demonstrate that existing greedy geographic routing algorithms can successfully find short routing paths based on local states in sensing-covered networks. In particular, we derive theoretical upper bounds on the network dilation of sensing-covered networks under greedy geographic routing algorithms. Furthermore, we propose a new greedy geographic routing algorithm called Bounded Voronoi Greedy Forwarding (BVGF) that allows sensing-covered networks to achieve an asymptotic network dilation lower than 4:62 as long as the communication range is at least twice the sensing range. Our results show that simple greedy geographic routing is an effective routing scheme in many sensing-covered networks.
---
paper_title: Routing Techniques in Wireless Sensor Networks: A Survey

paper_content:

Wireless sensor networks consist of small nodes with sensing, computation, and wireless communications capabilities. Many routing, power management, and data dissemination protocols have been specifically designed for WSNs where energy awareness is an essential design issue. Routing protocols in WSNs might differ depending on the application and network architecture. In this article we present a survey of state-of-the-art routing techniques in WSNs. We first outline the design challenges for routing protocols in WSNs followed by a comprehensive survey of routing techniques. Overall, the routing techniques are classified into three categories based on the underlying network structure: flit, hierarchical, and location-based routing. Furthermore, these protocols can be classified into multipath-based, query-based, negotiation-based, QoS-based, and coherent-based depending on the protocol operation. We study the design trade-offs between energy and communication overhead savings in every routing paradigm. We also highlight the advantages and performance issues of each routing technique. The article concludes with possible future research areas.
---
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: 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: 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: 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: Energy-aware data-centric routing in microsensor networks

paper_content:

Large-scale wireless sensors are expected to play an increasingly important role in future civilian and military settings where collaborative microsensors could be very effective in monitoring their operations. However, low power and in-network data processing make data-centric routing in wireless sensor networks a challenging problem.In this paper, we propose a novel and efficient energy-aware distributed heuristic, which we refer to as EAD, to build a special rooted broadcast tree with many leaves that is used to facilitate data-centric routing in wireless microsensor networks. Our EAD algorithm makes no assumption on local network topology, and is based on residual power. It makes use of a neighboring broadcast scheduling and distributed competition among neighboring nodess. We discuss the implementation of our scheme, and present an extensive simulation experiments to study the its performance. Our experimental results indicate clearly that our EAD scheme outperforms previous schemes.
---
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: An application-specific protocol architecture for wireless microsensor networks

paper_content:

Networking together hundreds or thousands of cheap microsensor nodes allows users to accurately monitor a remote environment by intelligently combining the data from the individual nodes. These networks require robust wireless communication protocols that are energy efficient and provide low latency. We develop and analyze low-energy adaptive clustering hierarchy (LEACH), a protocol architecture for microsensor networks that combines the ideas of energy-efficient cluster-based routing and media access together with application-specific data aggregation to achieve good performance in terms of system lifetime, latency, and application-perceived quality. LEACH includes a new, distributed cluster formation technique that enables self-organization of large numbers of nodes, algorithms for adapting clusters and rotating cluster head positions to evenly distribute the energy load among all the nodes, and techniques to enable distributed signal processing to save communication resources. Our results show that LEACH can improve system lifetime by an order of magnitude compared with general-purpose multihop approaches.
---
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: A Survey of Energy-Efficient Scheduling Mechanisms in Sensor Networks

paper_content:

Sensor networks have a wide range of potential, practical and useful applications. However, there are issues that need to be addressed for efficient operation of sensor network systems in real applications. Energy saving is one critical issue for sensor networks since most sensors are equipped with nonrechargeable batteries that have limited lifetime. To extend the lifetime of a sensor network, one common approach is to dynamically schedule sensors' work/ sleep cycles (or duty cycles). Moreover, in cluster-based networks, cluster heads are usually selected in a way that minimizes the total energy consumption and they may rotate among the sensors to balance energy consumption. In general, these energy-efficient scheduling mechanisms (also called topology configuration mechanisms) need to satisfy certain application requirements while saving energy. In this paper, we provide a survey on energy-efficient scheduling mechanisms in sensor networks that have different design requirements than those in traditional wireless networks. We classify these mechanisms based on their design assumptions and design objectives. Different mechanisms may make different assumptions about their sensors including detection model, sensing area, transmission range, failure model, time synchronization, and the ability to obtain location and distance information. They may also have different assumptions about network structure and sensor deployment strategy. Furthermore, while all the mechanisms have a common design objective to maximize network lifetime, they may also have different objectives determined by their target applications.
---
paper_title: An efficient N-to-1 multipath routing protocol in wireless sensor networks

paper_content:

A typical task in a wireless sensor network is that every sensor node senses its local environment and, upon request, sends the data of interest back to a base station. Based on this many-to-one communication pattern, we first propose a distributed N-to-1 multipath discovery protocol which distinguishes from other multipath routing protocols in that it is able to find multiple node-disjoint paths from every sensor node to the base station simultaneously in one route discovery process. Then we propose a hybrid multipath data collection scheme which combines end-to-end multipath traffic dispersion and per-hop alternate path salvaging. Our simulation results show that the proposed N-to-1 multipath discovery protocol is highly efficient and the hybrid data collection scheme based on it provides a seamlessly more reliable and more secure data collection service in wireless sensor networks
---
paper_title: HEED: a hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks

paper_content:

Topology control in a sensor network balances load on sensor nodes and increases network scalability and lifetime. Clustering sensor nodes is an effective topology control approach. In this paper, we propose a novel distributed clustering approach for long-lived ad hoc sensor networks. Our proposed approach does not make any assumptions about the presence of infrastructure or about node capabilities, other than the availability of multiple power levels in sensor nodes. We present a protocol, HEED (Hybrid Energy-Efficient Distributed clustering), that periodically selects cluster heads according to a hybrid of the node residual energy and a secondary parameter, such as node proximity to its neighbors or node degree. HEED terminates in O(1) iterations, incurs low message overhead, and achieves fairly uniform cluster head distribution across the network. We prove that, with appropriate bounds on node density and intracluster and intercluster transmission ranges, HEED can asymptotically almost surely guarantee connectivity of clustered networks. Simulation results demonstrate that our proposed approach is effective in prolonging the network lifetime and supporting scalable data aggregation.
---
paper_title: Distributed clustering in ad-hoc sensor networks: a hybrid, energy-efficient approach

paper_content:

Prolonged network lifetime, scalability, and load balancing are important requirements for many ad-hoc sensor network applications. Clustering sensor nodes is an effective technique for achieving these goals. In this work, we propose a new energy-efficient approach for clustering nodes in ad-hoc sensor networks. Based on this approach, we present a protocol, HEED (hybrid energy-efficient distributed clustering), that periodically selects cluster heads according to a hybrid of their residual energy and a secondary parameter, such as node proximity to its neighbors or node degree. HEED does not make any assumptions about the distribution or density of nodes, or about node capabilities, e.g., location-awareness. The clustering process terminates in O(1) iterations, and does not depend on the network topology or size. The protocol incurs low overhead in terms of processing cycles and messages exchanged. It also achieves fairly uniform cluster head distribution across the network. A careful selection of the secondary clustering parameter can balance load among cluster heads. Our simulation results demonstrate that HEED outperforms weight-based clustering protocols in terms of several cluster characteristics. We also apply our approach to a simple application to demonstrate its effectiveness in prolonging the network lifetime and supporting data aggregation.
---
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: Energy Efficient Homogenous Clustering Algorithm for Wireless Sensor Networks

paper_content:

Radio transmission and reception consumes a lot of energy in a wireless sensor network (WSN), which are made of low-cost, low-power, small in size, and multifunctional sensor nodes. Thus, one of the important issues in wireless sensor network is the inherent limited battery power within the sensor nodes. Therefore, battery power is crucial parameter in the algorithm design in maximizing the lifespan of sensor nodes. It is also preferable to distribute the energy dissipated throughout the wireless sensor network in order to maximize overall network performance. Much research has been done in recent years in the area of low power routing protocol, but, there are still many design options open for improvement, and for further research targeted to the specific applications, need to be done. In this paper, we propose a new approach of an energy-efficient homogeneous clustering algorithm for wireless sensor networks in which the lifespan of the network is increased by ensuring a homogeneous distribution of nodes in the clusters. In this clustering algorithm, energy efficiency is distributed and network performance is improved by selecting cluster heads on the basis of (i) the residual energy of existing cluster heads, (ii) holdback value, and (iii) nearest hop distance of the node. In the proposed clustering algorithm, the cluster members are uniformly distributed and the life of the network is further extended.
---
paper_title: Joint mobility and routing for lifetime elongation in wireless sensor networks

paper_content:

Although many energy efficient/conserving routing protocols have been proposed for wireless sensor networks, the concentration of data traffic towards a small number of base stations remains a major threat to the network lifetime. The main reason is that the sensor nodes located near a base station have to relay data for a large part of the network and thus deplete their batteries very quickly. The solution we propose in this paper suggests that the base station be mobile; in this way, the nodes located close to it change over time. Data collection protocols can then be optimized by taking both base station mobility and multi-hop routing into account. We first study the former, and conclude that the best mobility strategy consists in following the periphery of the network (we assume that the sensors are deployed within a circle). We then consider jointly mobility and routing algorithms in this case, and show that a better routing strategy uses a combination of round routes and short paths. We provide a detailed analytical model for each of our statements, and corroborate it with simulation results. We show that the obtained improvement in terms of network lifetime is in the order of 500%.
---
paper_title: Data MULEs: modeling a three-tier architecture for sparse sensor networks

paper_content:

This paper presents and analyzes an architecture to collect sensor data in sparse sensor networks. Our approach exploits the presence of mobile entities (called MULEs) present in the environment. MULEs pick up data from the sensors when in close range, buffer it, and drop off the data to wired access points. This can lead to substantial power savings at the sensors as they only have to transmit over a short range. This paper focuses on a simple analytical model for understanding performance as system parameters are scaled. Our model assumes two-dimensional random walk for mobility and incorporates key system variables such as number of MULEs, sensors and access points. The performance metrics observed are the data success rate (the fraction of generated data that reaches the access points) and the required buffer capacities on the sensors and the MULEs. The modeling along with simulation results can be used for further analysis and provide certain guidelines for deployment of such systems.
---
paper_title: Dynamic proxy tree-based data dissemination schemes for wireless sensor networks

paper_content:

In wireless sensor networks, efficiently disseminating data from a dynamic source to multiple mobile sinks is important for the applications such as mobile target detection and tracking. The tree-based multicasting scheme can be used. However, because of the short communication range of each sensor node and the frequent movement of sources and sinks, a sink may fail to receive data due to broken paths, and the tree should be frequently reconfigured to reconnect sources and sinks. To address the problem, we propose a dynamic proxy tree-based framework in this paper. A big challenge in implementing the framework is how to efficiently reconfigure the proxy tree as sources and sinks change. We model the problem as on-line constructing a minimum Steiner tree in an Euclidean plane, and propose centralized schemes to solve it. Considering the strict energy constraints in wireless sensor networks, we further propose two distributed on-line schemes, the shortest path-based (SP) scheme and the spanning range-based (SR) scheme. Extensive simulations are conducted to evaluate the schemes. The results show that the distributed schemes have similar performance as the centralized ones, and among the distributed schemes, the SR scheme outperforms the SP scheme.
---
paper_title: Data gathering in sensor networks using the energy*delay metric

paper_content:

In this paper we consider the problem of data collection from a sensor web consisting of N nodes, where nodes have packets of data in each round of communication that need to be gathered and fused with other nodes’ packets into one packet and transmitted to a distant base station. Nodes have power control in their wireless communications and can transmit directly to any node in the network or to the base station. With unit delay cost for each packet transmission, if all nodes transmit data directly to the base station, then both high energy and high delay per round will occur. In our prior work [6], we developed an algorithm to minimize the energy cost per round, where a linear chain of all the nodes are formed to gather data, and nodes took turns to transmit to the base station. If the goal is to minimize the delay cost, then a binary combining scheme can be used to accomplish this task in about log N units of delay with parallel communications and incurring a slight increase in energy cost. The goal is to find data gathering schemes that balance the energy and delay cost, as measured by energy*delay. We conducted extensive simulation experiments with a number of schemes for this problem with 100 nodes in playing fields of 50m x 50m and 100m x 100m and the base station located at least 100 meters and 200 meters, respectively, from any node. With CDMA capable sensor nodes, a chain-based binary scheme performs best in terms of energy*delay. If the sensor nodes are not CDMA capable, then parallel communications are possible only among spatially separated nodes, and a chain-based 3 level hierarchy scheme performs well. These schemes perform 60 to 100 times better than direct scheme and also outperform a cluster based scheme, called LEACH [3].
---
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: Improving routing in sensor networks with heterogeneous sensor nodes

paper_content:

Existing routing protocols mainly consider homogeneous sensor networks where all sensor nodes are the same. However, a homogeneous ad hoc network suffers from poor performance limit and scalability. Recent research has demonstrated its performance bottleneck both theoretically and through experiments. Furthermore, recently deployed sensor network systems are increasingly following heterogeneous designs, incorporating a mixture of sensors with widely varying capabilities. To improve network performance, we propose to form heterogeneous sensor networks by deploying a small number of powerful high-end sensors in addition to a large number of low-end sensors. We design an efficient cluster head relay (CHR) routing protocol for heterogeneous sensor networks. Our simulation experiments demonstrate that CHR performs better than two popular sensor network routing protocols.
---
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: A survey on routing protocols for wireless sensor networks

paper_content:

Recent advances in wireless sensor networks have led to many new protocols specifically designed for sensor networks where energy awareness is an essential consideration. Most of the attention, however, has been given to the routing protocols since they might differ depending on the application and network architecture. This paper surveys recent routing protocols for sensor networks and presents a classification for the various approaches pursued. The three main categories explored in this paper are data-centric, hierarchical and location-based. Each routing protocol is described and discussed under the appropriate category. Moreover, protocols using contemporary methodologies such as network flow and quality of service modeling are also discussed. The paper concludes with open research issues. � 2003 Elsevier B.V. All rights reserved.
---
paper_title: Routing Techniques in Wireless Sensor Networks: A Survey

paper_content:

Wireless sensor networks consist of small nodes with sensing, computation, and wireless communications capabilities. Many routing, power management, and data dissemination protocols have been specifically designed for WSNs where energy awareness is an essential design issue. Routing protocols in WSNs might differ depending on the application and network architecture. In this article we present a survey of state-of-the-art routing techniques in WSNs. We first outline the design challenges for routing protocols in WSNs followed by a comprehensive survey of routing techniques. Overall, the routing techniques are classified into three categories based on the underlying network structure: flit, hierarchical, and location-based routing. Furthermore, these protocols can be classified into multipath-based, query-based, negotiation-based, QoS-based, and coherent-based depending on the protocol operation. We study the design trade-offs between energy and communication overhead savings in every routing paradigm. We also highlight the advantages and performance issues of each routing technique. The article concludes with possible future research areas.
---
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: Wireless sensor networks: a survey

paper_content:

This paper describes the concept of sensor networks which has been made viable by the convergence of micro-electro-mechanical systems technology, wireless communications and digital electronics. First, the sensing tasks and the potential sensor networks applications are explored, and a review of factors influencing the design of sensor networks is provided. Then, the communication architecture for sensor networks is outlined, and the algorithms and protocols developed for each layer in the literature are explored. Open research issues for the realization of sensor networks are also discussed.
---
paper_title: An energy-aware QoS routing protocol for wireless sensor networks

paper_content:

Recent advances in wireless sensor networks have led to many new routing protocols specifically designed for sensor networks. Almost all of these routing protocols considered energy efficiency as the ultimate objective in order to maximize the whole network lifetime. However, the introduction of video and imaging sensors has posed additional challenges. Transmission of video and imaging data requires both energy and QoS aware routing in order to ensure efficient usage of the sensors and effective access to the gathered measurements. In this paper, we propose an energy-aware QoS routing protocol, which can also run efficiently with best-effort traffic. The protocol finds a least-cost, delay-constrained path for real-time data in terms of link cost that captures nodes' energy reserve, transmission energy, error rate and other communication parameters. Moreover, throughput for non-real-time data is maximized by adjusting the service rate for both real-time and non-realtime data at sensor nodes. Simulation results have demonstrated the effectiveness of our approach.
---
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.
---

Title: Routing Protocols in Wireless Sensor Networks - A Survey

Section 1: Introduction
Description 1: Write an introduction that provides background information on wireless sensor networks (WSNs), their significance, typical characteristics, and deployment challenges.

Section 2: QoS support
Description 2: Discuss the different quality-of-service (QoS) requirements for WSN applications, focusing on delivery latency and packet loss, and the importance of considering these requirements in network protocol design.

Section 3: Network Design Challenges and Routing Issues
Description 3: Present the main challenges and issues in designing routing protocols for WSNs, including energy constraints, sensor locations, hardware limitations, node deployment dynamics, unreliable environments, and data aggregation.

Section 4: Routing Protocols in WSN
Description 4: Introduce the various types of routing protocols designed for WSNs and provide an overview of their common characteristics and goals.

Section 5: Location-based Protocols
Description 5: Explain the principles of location-based routing protocols, including specific examples such as Geographic Adaptive Fidelity (GAF), Geographic and Energy-Aware Routing (GEAR), Trajectory-Based Forwarding (TBF), and others.

Section 6: Data Centric Protocols
Description 6: Describe data-centric protocols, how they differ from traditional address-centric protocols, and provide examples such as Sensor Protocols for Information via Negotiation (SPIN), Directed Diffusion, Rumor Routing, and others.

Section 7: Hierarchical Protocols
Description 7: Discuss hierarchical clustering-based protocols, their energy efficiency advantages, and provide examples such as Low-energy adaptive clustering hierarchy (LEACH), PEGASIS, HEED, and others.

Section 8: Mobility-based Protocols
Description 8: Address challenges and strategies in routing for mobile WSNs, with examples of protocols that incorporate sink mobility and mobile data collectors, like Data MULES Based Protocol and SEAD.

Section 9: Multipath-based Protocols
Description 9: Explain the concepts of single-path and multipath routing, and the benefits of using disjoint and braided paths in WSNs, with related protocols.

Section 10: Heterogeneity-based Protocols
Description 10: Discuss protocols designed for heterogeneous WSNs, which use different types of sensors to extend network lifetime, with examples like Information-Driven Sensor Query (IDSQ) and Cluster-Head Relay Routing (CHR).

Section 11: QoS-based Protocols
Description 11: Review protocols that ensure a balance between energy efficiency and QoS requirements, providing examples such as Sequential Assignment Routing (SAR) and SPEED.

Section 12: Conclusion and Future Research
Description 12: Summarize the survey findings, emphasize the importance of energy-efficient routing protocols, and suggest future research directions including duty-cycled WSNs and three-dimensional sensor fields.