Method and apparatus for route discovery within a communication system
View Patent ↗During route discovery in an ad-hoc communication network, an overlay transceiver ( 104 ) determines a plurality of “seed” nodes that lie between the source and the destination node. The seed nodes are notified of the desire to discover a route between the source and the destination node. Once notified, the seed nodes immediately broadcast route discovery messages. All nodes ( 101 ) within the underlay communication system ( 110 ) periodically listen for route discovery messages. If any node within the underlay communication system ( 110 ) receives a route discovery message having the same route identification, route information between the two seeds will be provided to the overlay transceiver ( 104 ), giving the overlay communication system a “path” between the seeds. Once the overlay transceiver ( 104 ) receives route information between all seeds, it then determines an appropriate route between source and destination devices, and broadcasts this information to the source and the destination devices.
1. A method of operating an overlay communication system, the method comprising the steps of:
receiving a route needed message from a first node in an underlay communication system, wherein the route-needed message notifies the overlay communication system that a route is needed between the first and a second node within the underlay communication system;
determining locations for seed nodes within the underlay communication system;
transmitting a message to the seed nodes causing the seed nodes to begin broadcasting route discovery messages;
receiving a plurality of route segments from nodes within the underlay communication system;
determining route based on the route segments; and
transmitting the route to the first node.
2. The method of claim 1 wherein the step of transmitting the message to the seed nodes comprises the step of transmitting a rout identifier to the seed nodes identifying a particular route to be discovered.
3. The method of claim 1 wherein the step of receiving the route needed message comprises the step of receiving a message comprising identification of the first node and the second node.
4. The method of claim 1 wherein the step of receiving the plurality of route segments comprises the step of receiving a plurality of route segments, wherein each route segment comprises a route between two seeds.
5. The method of claim 1 wherein the step of determining locations for seed nodes within the underlay communication system comprises the step of determining nodes nearest a line connecting a source node and a destination node.
6. A method for operating a node within an ad-hoc communication system, the method comprising the steps of:
receiving a first route-discovery message;
determining from the first route-discovery message, an identification of a first seed node that originated the first route-discovery message;
determining a first route identifier from the first route-discovery message;
determining if a prior-received route-discovery messages was received from a differing seed node containing a similar route identifier; and
transmitting route information obtained from the two route-discovery messages to an overlay communication system based on a determination that a prior-received route-discovery messages was received from a differing seed node containing a similar route identifier.
7. The method of claim 6 wherein the step of transmitting route information comprises the step of transmitting a route between two seed nodes.
8. An apparatus existing within an overlay communication system, the apparatus comprising:
a receiver, receiving a plurality of route segments from a plurality of nodes within an underlay communication system;
logic circuitry determining a route between a first and a second node within the underlay communication system, wherein the route is determined from the plurality of route segments; and
a transmitter, transmitting the route to the first node within the underlay communication system.
9. The apparatus of claim 8 wherein the receiver comprises a receiver within a cellular communication system.
10. An apparatus existing within an underlay communication system, the apparatus comprising:
a receiver receiving a first and a second route-discovery message from a first and a second node;
logic circuitry determining a first and a second route identifier from the first and the second route-discovery messages, and additionally determining if the first and the second route identifiers are similar; and
transmission circuitry transmitting route information obtained from the first and the second route-discovery messages when the first and the second route identifiers differ.
11. The apparatus of claim 10 wherein the route information comprises a route between the first and the second node.