Method for Routing Ad-Hoc Signals

• US 20100254316A1
• Filed: 06/03/2010
• Published: 10/07/2010
• Est. Priority Date: 02/25/2002
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Olsonet Communications Corporation
• Inventors: Sendrowicz, Gerry
• Granted Patent: US 8,406,177 B2
• Time in Patent Office: Days
• US Class Current: 370/328
• CPC Class Codes: H04L 1/1874 Buffer management
• CPC Class Codes: H04L 2001/0092 Error control systems characterised by the topology of the transmission link
• CPC Class Codes: H04W 4/16 Communication-related supplementary services, e.g. call-transfer or call-hold
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/248 Connectivity information update
• CPC Class Codes: H04W 40/28 for reactive routing
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

An ad-hoc network is a typically a dynamic collection of nodes capable of communicating therebetween without the aid of pre-established infrastructure. Ad-hoc networks differ from traditional networks in that the topology of interconnections between nodes is inherently dynamic and not fixed. Generally, the routing protocols belong to two groups: proactive and reactive. Proactive protocols attempt to maintain correct and up-to-date routing information at every node. Reactive protocols, in turn, collect necessary routing information only if a pair of nodes are to establish a communication. In accordance with embodiments of the invention a reactive ad-hoc network protocol is disclosed that uses controlled flooding to broadcast packets of information within the ad-hoc network. Furthermore, the ad-hoc network protocol does not maintain up-to-date routing information at every node in an ad-hoc network and does not utilize specific control messages to assure that packets within the ad-hoc network follow optimal paths.

Claims

1. A method of providing a reactive ad-hoc network comprising the steps of:

(a) providing at least a first node and a second other node of a plurality of nodes, each node comprising at least a processor, a memory, and a transceiver in communication with the processor for receiving data and transmitting data via a wireless communication medium;

(b) providing a packet of data comprising message data and header data to the processor of the first node for transmission therefrom, the header data comprising data relating to a source node and a destination node for the packet of data, data relating to a number of hops already completed for the packet of data, data relating to mobility of packets of data within the reactive ad-hoc network transmitted from the source node to the destination node and the destination node to the source node, data relating to a number of hops between the source node and the destination node for a previous packet of data, an optimal path indicator relating to a path between the source node and destination node and being other than data relating any other nodes within the plurality of nodes, and a unique identifier for the packet of data;

(c) transmitting the data from the transceiver of the first node in a broadcast fashion;

(d) receiving the data at the transceiver of the second other node;

(e) extracting the optimal path indicator from the header data;

(f) determining an action in dependence upon the optical path indicator; and

(g) performing the determined action, the determined action being at least one of;

(i) deleting the packet of data where the optimal path indicator indicates that the first node was on an optimal path between the source node and destination node and the data relating to mobility of packets within the reactive ad-hoc network meets a predetermined criterion;

(ii) determining where the optical path indicator indicates that the first node was not on an optimal path between the source node and destination node if the second other node is on an optimal path, the determination made in dependence upon the data relating to a number of hops between the source node and the destination node for a previous packet of data, the data relating to a number of hops already completed for the packet of data, and data relating to the number of hops between the second other node and the destination node stored within the memory of the second other node;

(iii) setting the optimal path indicator to indicate that the second other node is on an optimal path between the source node and destination node; and

(iv) transmitting the packet of data from the second other node in a broadcast fashion.

2. A method according to claim 1 wherein;

the data relating to mobility of packets of data is determined in dependence upon at least one of a measure of physical node mobility, a measure of topology change, and a measure of packets loss within the reactive ad-hoc network.

3. A method according to claim 2 wherein;

the determination of the data relating to mobility of packets of data is made by the source node.

4. A method of providing a reactive ad-hoc network comprising the steps of:

(a) providing at least a first node and a second other node of a plurality of nodes, each node comprising at least a processor, a memory, and a transceiver in communication with the processor for receiving data and transmitting data via a wireless communication medium;

(b) receiving from the transceiver of the second other node a packet of data transmitted from the transceiver of the first node in a broadcast fashion, the packet of data comprising message data and header data to the processor of the first node for transmission therefrom, the header data comprising an optimal path indicator relating to a path between a source node and a destination node and being other than data relating any other nodes within the plurality of nodes;

(c) extracting the optimal path indicator from the header data;

(d) determining an action in dependence upon the optical path indicator; and

(e) performing the determined action, the determined action being at least one of;

(i) deleting the packet of data where the optimal path indicator indicates that the first node was on an optimal path between the source node and destination node;

(ii) determining where the optical path indicator indicates that the first node was not on an optimal path between the source node and destination node if the second other node is on an optimal path without using data relating to the plurality of nodes and specific hops between any pairs of nodes within the plurality of nodes;

(iii) setting the optimal path indicator to indicate that the second other node is on an optimal path between the source node and destination node; and

(iv) transmitting the packet of data from the second other node in a broadcast fashion.

5. The method according to claim 4 wherein;

the header data comprises data relating to the source node and the destination node for the packet of data, data relating to a number of hops already completed for the packet of data, data relating to mobility of packets of data within the reactive ad-hoc network transmitted from the source node to the destination node and the destination node to the source node, data relating to a number of hops between the source node and the destination node for a previous packet of data, and a unique identifier for the packet of data.

6. A method according to claim 5 wherein;

the determination is made in dependence upon the data relating to a number of hops between the source node and the destination node for a previous packet of data, the data relating to a number of hops already completed for the packet of data, and data relating to the number of hops between the second other node and the destination node stored within the memory of the second other node.

7. A method according to claim 5 wherein;

the data relating to mobility of packets of data is determined in dependence upon at least one of a measure of physical node mobility, a measure of topology change, and a measure of packets loss within the reactive ad-hoc network.

8. A method according to claim 7 wherein;

the determination of the data relating to mobility of packets of data is made by the source node.

9. A node for forming part of a reactive ad-hoc network comprising:

a processor;

a memory in communication with the processor;

a transceiver in communication with the processor for receiving signals and for transmitting signals, the signals transmitted and received via a wireless communication medium; and

an application in execution upon the processor executing an ad-hoc communications protocol to communicate with at least one other node to form an ad-hoc network, the application;

(a) at least one of generating, receiving from the transceiver and providing to the transceiver a packet of data comprising message data and header data providing a packet of data comprising message data and header data to the processor of the first node for transmission therefrom, the header data comprising data relating to a source node and a destination node for the packet of data, data relating to a number of hops already completed for the packet of data, data relating to mobility of packets of data within the reactive ad-hoc network transmitted from the source node to the destination node and the destination node to the source node, data relating to a number of hops between the source node and the destination node for a previous packet of data, an optimal path indicator relating to a path between the source node and destination node and being other than data relating any other nodes within the plurality of nodes, and a unique identifier for the packet of data;

(b) extracting the optimal path indicator from the header data of a received packet of data;

(c) determining an action in dependence upon the optical path indicator; and

(d) performing the determined action, the determined action being at least one of;

(i) deleting the packet of data where the optimal path indicator indicates that another node that transmitted the packet of data was on an optimal path between the source node and destination node and the data relating to mobility of packets within the reactive ad-hoc network meets a predetermined criterion;

(ii) determining where the optical path indicator indicates that another node that transmitted the packet of data was not on an optimal path between the source node and destination node if the node is on an optimal path, the determination made in dependence upon the data relating to a number of hops between the source node and the destination node for a previous packet of data, the data relating to a number of hops already completed for the packet of data, and data relating to the number of hops between the node and the destination node stored within the memory of the node;

(iii) setting the optimal path indicator to indicate that the node is on an optimal path between the source node and destination node; and

(iv) transmitting the packet of data to the transceiver of the node.

10. A method according to claim 9 wherein;

the data relating to mobility of packets of data is determined in dependence upon at least one of a measure of physical node mobility, a measure of topology change, and a measure of packets loss within the reactive ad-hoc network.

11. A method according to claim 10 wherein;

the determination of the data relating to mobility of packets of data is made by the source node.

12. A node for forming part of a reactive ad-hoc network comprising:

a processor;

a memory in communication with the processor;

a transceiver in communication with the processor for receiving signals and for transmitting signals, the signals transmitted and received via a wireless communication medium; and

an application in execution upon the processor executing an ad-hoc communications protocol to communicate with at least one other node to form an ad-hoc network, the application;

(a) receiving from the transceiver a packet of data transmitted by a transceiver of another node in a broadcast fashion, the packet of data comprising message data and header data to the processor of the first node for transmission therefrom, the header data comprising an optimal path indicator relating to a path between the source node and destination node and being other than data relating any other nodes within the plurality of nodes;

(b) extracting the optimal path indicator from the header data;

(d) determining an action in dependence upon the optical path indicator; and

(c) performing the determined action, the determined action being at least one of;

(i) deleting the packet of data where the optimal path indicator indicates that the another node was on an optimal path between the source node and destination node;

(ii) determining where the optical path indicator indicates that the another node was not on an optimal path between the source node and destination node if the node is on an optimal path without using data relating to the plurality of nodes and specific hops between any pairs of nodes within the plurality of nodes;

(iii) setting the optimal path indicator to indicate that the node is on an optimal path between the source node and destination node; and

(iv) transmitting the packet of data to the transceiver of the node.

13. The method according to claim 12 wherein;

the header data comprises data relating to the source node and the destination node for the packet of data, data relating to a number of hops already completed for the packet of data, data relating to mobility of packets of data within the reactive ad-hoc network transmitted from the source node to the destination node and the destination node to the source node, data relating to a number of hops between the source node and the destination node for a previous packet of data, and a unique identifier for the packet of data.

14. A method according to claim 13 wherein;

the determination is made in dependence upon the data relating to a number of hops between the source node and the destination node for a previous packet of data, the data relating to a number of hops already completed for the packet of data, and data relating to the number of hops between the node and the destination node stored within the memory of the node.

15. A method according to claim 13 wherein;

the data relating to mobility of packets of data is determined in dependence upon at least one of a measure of physical node mobility, a measure of topology change, and a measure of packets loss within the reactive ad-hoc network.

16. A method according to claim 15 wherein;

the determination of the data relating to mobility of packets of data is made by the source node.