The best-effort geographical multi-hop routing (BEGHR) protocol routes packets of data in an ad hoc digital radio-communication network on the basis of the current geographical positions of all the network nodes. This protocol was conceived especially for application to a network, (1) the nodes of which are equipped with Global Positioning System receivers to determine their positions, (2) the nodes of which contain environmental sensors, and (3) the main purpose of which is to collect sensory data and relay them to a central node designated as home.

Unlike prior routing algorithms characterized as table-driven, the BEGHR algorithm does not require the maintenance of a routing table containing up-to-date information on the route(s) from every node to every other node. Unlike prior algorithms characterized as on-demand, the BEGHR does not require the discovery of a route from a specific source node to a specific destination node and the subsequent maintenance of that specific route until the route is no longer needed or no longer accessible. Instead, in the BEGHR algorithm, each packet is forwarded on the basis of (1) only minimal local knowledge of network resources, (2) an effort by nodes participating in the hop to adapt toward current optimal forwarding conditions, and (3) statistical measures of performance.

A Network Node Oscillates between client and server modes of operation. A subalgorithm of the BEGHR algorithm allocates portions of the oscillation period to the two modes.
It is assumed that the network is a member of the class of statistically accurate sensor networks (SASNs), defined as networks capable of representing the distributed information gathered by its sensors with a degree of accuracy and timeliness characterized by a statistical measure denoted as currency or currentness: Let d(i) be the interval of time between the generation of the ith piece of information and its arrival at home. The source node or the network is said to be (a,b) current if a is the probability that each piece of information arrives within d(i) < b.

Hence, in an SASN, it is sufficient that only some of the data collected by, and transmitted from, all of the nodes reach home in order to represent the collected measurement data to within a specified degree of accuracy and timeliness. Another measure of performance of node or of the network is that of throughput, defined here as (the total number of packets arrived up to a given time) divided by (the number of packets generated up to that time). A throughput <1 could signify that packets had been lost on account of bit errors in noisy transmission channels and/or overflow of queues of packets awaiting transmission.

In the BEGHR, the network nodes are assumed to be randomly positioned. The nodes are also assumed to be identical and each node to be capable of adapting within the network according to its position relative to home and to other nodes that, like itself, are attempting to send data packets to home. Each node is capable of operating in a client mode, defined here as the mode in which it forwards packets, including both those that it generates and those that it received from one or more other node(s) for relay to home. Each node is also capable of operating in a server mode, defined here as the mode in which it receives packets from one or more other nodes. The position of a node relative to home is used to determine whether a packet is in a loop or is being handed off to a node closer to home. Error checking is performed, but acknowledgements are not sent back to originating or relaying nodes, and there is no guarantee that a server node has properly received a packet forwarded from a client node.

Each node oscillates between the client and server modes, dynamically adjusting the time allocated to each mode (see figure). In addition, each node allocates a fixed amount of time to its own local collection of sensory data. The probability of finding the node in one mode or the other depends on its geographical position relative to home. For this purpose, the distance from home is expressed as the multihop parameter of the node, defined as the ratio between (1) its geographical distance from home and (2) the radio-reception distance beyond which the probability of bit error exceeds a value defined in a controlled test scenario. A node located closer to home adapts toward statistically allocating more time as a server, while a sensor located farther from home adapts toward statistically allocating more time as a client. Prior to entering the oscillation, a node waits for home to broadcast (and for any intervening nodes to relay) a message stating the current location of home. Once it goes into the oscillation, the node also relays the home-location message to nodes farther from home.

This work was done by Clayton Okino of Caltech and Michael Corr of Dartmouth College for NASA's Jet Propulsion Laboratory. For further information, access the Technical Support Package (TSP) free on-line at under the Electronic Components and Systems category.

This software is available for commercial licensing. Please contact Don Hart of the California Institute of Technology at (818) 393-3425. Refer to NPO-30454.

This Brief includes a Technical Support Package (TSP).
Geography-Based Routing in an Ad Hoc Communication Network

(reference NPO-30454) is currently available for download from the TSP library.

Don't have an account? Sign up here.

NASA Tech Briefs Magazine

This article first appeared in the December, 2002 issue of NASA Tech Briefs Magazine.

Read more articles from the archives here.