Method and apparatus for route discovery within a communication system

• US 20050094576A1
• Filed: 10/18/2004
• Published: 05/05/2005
• Est. Priority Date: 10/30/2003
• Status: Active Grant

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Fonseca, Benedito J. Jr., Bonta, Jeffrey D.
• Granted Patent: US 7,463,612 B2
• Time in Patent Office: Days
• US Class Current: 370/255
• CPC Class Codes: H04L 45/42 Centralised routing
• CPC Class Codes: H04L 45/44 Distributed routing
• CPC Class Codes: H04L 45/64 using an overlay routing layer
• 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
• CPC Class Codes: H04W 84/22 with access to wired networks

Abstract

A communication system (100) is provided that comprises an overlay communication system and an underlay ad-hoc communication system. Route discovery in the ad-hoc communication system takes place by notifying the overlay communication system of the source and destination nodes. The overlay communication system instructs all base stations between the source and destination nodes to instruct all nodes to participate in route discovery.

Claims

1. A method for route discovery between a source node and a destination node within an ad-hoc communication system, the method comprising:

receiving a route discovery request from the source node;

locating a source base station and a destination base station serving the source node and the destination node;

determining intervening base stations between the source and the destination base stations; and

instructing intervening nodes in communication with the intervening base stations to participate in route discovery.

2. The method of claim 1 further comprising:

receiving route information from the destination node;

determining at least one route between the source and the destination node; and

providing route information to at least one node in the underlay communication system.

3. The method of claim 2 wherein determining the at least one route comprises determining a set of intervening nodes based on battery life of the intervening nodes.

4. The method of claim 1 wherein instructing intervening nodes to participate in route discovery comprises providing the intervening nodes with a session identification, instructing the intervening nodes to only forward route-discovery messages containing the session identification.

5. A method for flooding within an underlay communication system, the method comprising:

receiving a notification message instructing a node to participate in route discovery, wherein the notification message comprises a first session identification;

receiving a route-discovery message comprising a second session identification;

determining if the first session identification matches the second session identification; and

forwarding the route-discovery message based on whether the first session identification matches the second session identification.

6. The method of claim 5 wherein receiving the notification message comprises receiving the notification message from an overlay communication system.

7. The method of claim 6 wherein receiving the route-discovery message comprises receiving the route-discovery message from a first node within the underlay communication system.

8. The method of claim 7 wherein forwarding the route-discovery message comprises forwarding the route-discovery message to a second node within the underlay communication system.

9. A method for route discovery within an ad-hoc communication system, the method comprising:

receiving a flood message;

determining that a particular node within an ad-hoc communication system is out of cellular coverage; and

rebroadcasting the flood message with an indication that the node is out of cellular coverage based on the determination that the particular node is out of cellular coverage.

10. The method of claim 9 wherein receiving the flood message comprises receiving a route-discovery message in an ad-hoc communication system.

11. A route-discovery message comprising:

a source address;

a destination address; and

a session identification that identifies a particular route/destination combination.

12. An apparatus comprising:

a receiver adapted to receive a route discovery request from a source node in an underlay communication system to communicate with a destination node within the underlay communication system;

logic circuitry adapted to locate the source and the destination nodes and adapted to determine intervening base stations between the source and the destination nodes; and

a transmitter adapted to transmit instructions instructing intervening nodes in communication with the intervening base stations to participate in route discovery.

13. An apparatus comprising:

a receiver adapted to receive a notification message instructing a node to participate in route discovery, wherein the notification message comprises a first session identification, and wherein the receiver is further adapted to receive a route-discovery message comprising a second session identification;

logic circuitry adapted to determine if the first session identification matches the second session identification; and

a transmitter adapted to forward the route-discovery message based on whether the first session identification matches the second session identification.