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.
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 www.nasatech.com/tsp 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?
Overview
The document presents a technical support package from NASA, detailing the Best Effort Geographical Multi-Hop Routing (BEGHR) protocol developed for ad hoc communication networks. Authored by Clayton Okino and Michael Corr from the Jet Propulsion Laboratory, the work addresses the challenges of routing in highly volatile networks where traditional routing tables may not be effectively maintained.
The BEGHR protocol is designed to facilitate packet routing based on the geographical positions of network nodes relative to a designated "home" location. Each node in the network can operate in two modes: client mode, where it forwards packets (both generated and received), and server mode, where it receives packets from other nodes. The protocol allows nodes to oscillate between these modes, dynamically adjusting the time spent in each based on their distance from home. Nodes closer to home tend to allocate more time to server mode, while those farther away operate more frequently in client mode.
A key feature of the BEGHR protocol is its reliance on minimal local knowledge of the network, enabling efficient packet forwarding in a best-effort manner. This adaptability is crucial for maintaining communication in environments where network conditions can change rapidly. The document also emphasizes the importance of error checking in packet transmission, although it notes that acknowledgments are not sent back to originating or relaying nodes, which means there is no guarantee of successful packet reception.
The document outlines the multihop parameter, which is a ratio that helps determine a node's geographical distance from home relative to its radio-reception distance. This parameter plays a critical role in the decision-making process for packet routing and mode allocation.
In addition to the technical details of the BEGHR protocol, the document provides information on the commercial licensing of related software and hardware, specifically the EDT PCI SS family of data acquisition cards, which are suitable for various applications, including telecommunications and satellite data collection.
Overall, this technical support package serves as a comprehensive overview of the BEGHR protocol, highlighting its innovative approach to routing in ad hoc networks and its potential applications in real-world scenarios, particularly in space exploration and communication.
