Method and apparatus for route discovery within a communication system

• US 7,463,612 B2
• Filed: 10/18/2004
• Issued: 12/09/2008
• 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
• Primary Examiner(s): Chan; Wing F
• Assistant Examiner(s): Choi; Eunsook
• Application Number:
  US10/967,503
• Publication Number:
  US 20050094576A1
• Time in Patent Office: 1,513 Days
• Field of Search: None
• US Class Current: 370/338
• 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;

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

receiving, by a node, a notification message instructing the 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.

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 an ad-hoc 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. The method of claim 1 wherein receiving the notification message comprises receiving the notification message from a communication system that overlays an ad-hoc communication system.

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

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

8. The method of claim 1 further 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 particular node is out of cellular coverage based on the determination that the particular node is out of cellular coverage.

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

10. An apparatus comprising:

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

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

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

a second 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 second receiver is further adapted to receive a route-discovery message comprising a second session identification;

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

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