Routing in Wireless Ad Hoc and Sensor Networks

Introduction

Routing is the process of finding a path from a source node to a destination node. Since each node has a limited transmission range, the message is normally forwarded by other nodes in an ad hoc or sensor network. Therefore routes normally consist of several hops. Proposed routing schemes can be divided into topological and position based, depending on the availability of geographic location for nodes. Topological routing may be proactive, reactive or hybrid. Position based routing consists of greedy approaches applied when a neighbor closer to the destination (than the node currently holding the packet) exists, and recovery schemes otherwise. In order to preserve bandwidth and power which are critical resources in ad hoc and sensor networks, localized approaches are proposed, where each node acts based solely on the location of itself, its neighbors, and the destination. There are various measures of optimality which lead to various schemes which optimize hop count, power, network lifetime, delay, or other metrics. A uniform solution based on ratio of cost and progress is described here.

An ad hoc network is a set of interconnected nodes that are deterministically or randomly dispersed in a given area and communicate over a wireless medium. Each of these nodes has the ability to send and receive messages to and from other nodes. Connections are possible over multiple nodes (multihop ad hoc network). Typical examples of ad hoc networks are conference and disaster relief networks.

Sensor networks are similar to ad hoc networks in the sense that nodes have the ability to communicate over a wireless medium, but they differ in purpose and communication patterns.

Each node in a sensor network is a small, battery powered device that has the capability of measuring or tracking the environment. Sensors can measure distance, speed, humidity, temperature, light, motion, seismic data, torque, and a host of other quantitatively measurable attributes of the environment that they are located in. They differ from ad hoc networks in purpose since each sensor has a specialized purpose of measuring and reporting the measured data. The two types of networks also differ in communication patterns. The nodes in ad hoc networks usually communicate between each other where the source and destination can be any two nodes. In sensor networks, nodes typically only communicate with a base station or sink. They usually only need to report data, and are not able to perform a certain action based on the collected data, other than transmitting or receiving messages. Therefore, communication in a sensor network is much more structured than in an ad hoc network.

Nodes in ad hoc or sensor networks may or may not know their geographic positions. The availability of positional information depends on the hardware of the nodes in the network. Typical devices used for positional information are GPS locators which are relatively small. Positional information is essential in sensor networks. Sensors need to know where they are located in order for whatever they are measuring to make sense to the base station. If a sensor detects fire, for instance, it must report the location of the fire, or else an appropriate response is not possible. However, sensors can be easily equipped with GPS locators, and the sensors themselves are relatively small devices. Positional information of sensors is not an easy problem (Bachrach & Taylor, 2005), but it is definitely an important part of a sensor’s makeup.

It is assumed that nodes have equal transmission radii R, where two nodes are neighbors if they are located at most R units away from each other. That is, two nodes can directly communicate if and only if the distance between them is ≤R. This is referred to as the unit disk graph model. The wireless communication medium is different from the wired one. The wired medium normally provides only one-to-one communication, meaning that a message sent to a neighbor is only received by that neighbor. However, the wireless medium enables one-to-all communication, where a message sent by one node is received by all of its neighbors. This provides both advantages and limitations. A single message reaches more nodes; however, at the same time, bandwidth is limited because normally all nodes use the same frequency for communication. Sensors also have a sensing radius, which is normally less than the communication radius.