Broadcast as a triggering mechanism for route discovery in ad-hoc networks

• US 6,704,293 B1
• Filed: 12/06/1999
• Issued: 03/09/2004
• Est. Priority Date: 12/06/1999
• Status: Expired due to Term

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Rune, Johan, Larsson, Tony, Sörensen, Johan
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): George, Keith M.
• Application Number:
  US09/455,460
• Time in Patent Office: 1,555 Days
• Field of Search: 370/351, 370/400, 370/401, 370/328, 370/254, 370/255
• US Class Current: 370/255
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04W 4/06 Selective distribution of broadcast services, e.g. multimedia broadcast multicast service [MBMS]; Services to user groups; One-way selective calling services
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 48/16 Discovering, processing access restriction or access information
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A method and/or an apparatus which places a broadcast message which the source expects a reply message in a broadcast message for route discovery. The combined message is broadcast throughout the ad-hoc network. When the combined broadcast message is received at the destination node, the destination node generates a response message including a reply message to the broadcast message that the source node expects a reply. The response message is sent back to the source node over the route which the combined broadcast message traveled to the destination node.

Claims

1. In a network, a method for determining a route from a source node to another node, wherein a request for route broadcast message is used to discover and establish routes between the source node and the another node, the method comprising the steps of:

generating, in the source node, a broadcast message for which the source node expects a reply message;

placing the broadcast message in a request for route broadcast message;

broadcasting, from the source node, the request for route broadcast message to neighboring nodes;

determining, in one of the neighboring nodes, whether the one of the neighboring nodes is a node which generates the reply message;

storing in each of the neighboring nodes a temporary route back to the source node; and

rebroadcasting the request for route broadcast message to all nodes which are neighboring nodes of the one of the neighboring nodes which has received the request for route broadcast message.

2. The method of claim 1, further comprising the steps of:

generating a response message to the request for route broadcast message if the one of the neighboring nodes is the node which generates the reply message;

placing the reply message in the response to the broadcast message; and

sending the response message to the source node over the temporary route stored in each neighboring node in a path between the source node and the node which generated the reply message.

3. The method of claim 2, further comprising the step of:

activating a route, in each of the neighboring nodes in the route between the source node and the node which generates the reply message, as the response message is sent from the node which generates the reply message to the source node.

4. In a network, a method for determining a route from a source node to another node, wherein a request for route broadcast message is used to discover and establish routes between the source node and the another node, the method comprising the steps of:

generating, in the source node, a broadcast message for which the source node expects a reply message;

placing the broadcast message in a request for route broadcast message;

broadcasting, from the source node, the request for route broadcast message to neighboring nodes; and

determining, in one of the neighboring nodes, whether the one of the neighboring nodes is a node which generates the reply message, wherein the source node, the neighboring nodes and the node which generates the reply message operate according to Bluetooth protocol.

5. In a network, a method for determining a route from a source node to another node, wherein a request for route broadcast message is used to discover and establish routes between the source node and the another node, the method comprising the steps of:

generating, in the source node, a broadcast message for which the source node expects a reply message;

placing the broadcast message in a request for route broadcast message;

broadcasting, from the source node, the request for route broadcast message to neighboring nodes;

determining, in one of the neighboring nodes, whether the one of the neighboring nodes is a node which generates the reply message;

receiving, at the one of the neighboring nodes, the request for route broadcast message;

waiting a predetermined amount of time;

examining the request for route broadcast message to determine whether the request for route broadcast message contains the broadcast message for which the source node expects the reply message; and

determining, if the request for route broadcast message contains the broadcast message for which the source node expects the reply message, if the one of the neighboring nodes is the node which generates the reply message.

6. The method of claim 5, further comprising the step of:

rebroadcasting the request for route broadcast message if, after the expiration of the predetermined amount of time, it has not been determined that the one of the neighboring nodes is the node which generates the reply message.

7. The method of claim 5, further comprising the step of:

generating a response message to the request for route broadcast message if, during the predetermined amount of time, it is determined that the neighboring node is the node that generates the reply message.

8. The method of claim 7, wherein the response message contains the reply message.

9. In a network, a method for determining a route from a source node to another node, wherein a request for route broadcast message is used to discover and establish routes between the source node and the another node, the method comprising the steps of:

generating, in the source node, a broadcast message for which the source node expects a reply message;

placing the broadcast message in a request for route broadcast message;

broadcasting, from the source node, the request for route broadcast message to neighboring nodes;

determining, in one of the neighboring nodes, whether the one of the neighboring nodes is a node which generates the reply message;

waiting a predetermined amount of time; and

determining whether a higher protocol layer has sent an indication to a lower protocol layer that a reply message has been generated.

10. The method of claim 9, further comprising the step of:

rebroadcasting the request for route broadcast message if, after the predetermined amount of time, the higher protocol layer has not sent the indication that the reply message has been generated.

11. The method of claim 9, further comprising the step of:

generating a response message to the request for route broadcast message if, during the predetermined amount of time, the higher protocol layer has sent the indication that a reply message has been generated.

12. In a network, a method for determining a route from a source node to another node, wherein a request for route broadcast message is used to discover and establish routes between the source node and the another node, the method comprising the steps of:

generating, in the source node, a broadcast message for which the source node expects a reply message;

placing the broadcast message in a request for route broadcast message;

broadcasting, from the source node, the request for route broadcast message to neighboring nodes; and

determining, in one of the neighboring nodes, whether the one of the neighboring nodes is a node which generates the reply message, wherein the broadcast message for which the source node expects a reply message is formed in accordance with name resolution protocol.

13. In a network, a method for determining a route from a source node to another node, wherein a request for route broadcast message is used to discover and establish routes between the source node and the another node, the method comprising the steps of:

generating, in the source node, a broadcast message for which the source node expects a reply message;

placing the broadcast message in a request for route broadcast message;

broadcasting, from the source node, the request for route broadcast message to neighboring nodes; and

determining, in one of the neighboring nodes, whether the one of the neighboring nodes is a node which generates the reply message, wherein the broadcast message for which the source node expects a reply message is formed in accordance with dynamic host configuration protocol (DHCP).

14. In a network, a method for determining a route from a source node to another node, wherein all nodes in the network include a network adaptation layer and a higher protocol layer, the method comprising the steps of:

generating, in the higher protocol layer of the source node, a broadcast message for which the source node expects a reply message;

placing the broadcast message for which the source node expects a reply message in a network adaptation layer request for route broadcast message; and

broadcasting, from the source node, the network adaptation layer request for route broadcast message to neighboring nodes.

15. The method of claim 14, further comprising the steps of:

waiting a predetermined amount of time; and

determining whether a higher protocol layer has sent an indication to the network adaptation layer that the reply message has been generated.

16. The method of claim 15, further comprising the step of:

rebroadcasting the request for route broadcast message if, after the predetermined amount of time, the higher protocol layer has not sent the indication to the network adaptation layer that the reply message has been generated.

17. The method of claim 15, further comprising the step of:

generating, in the network adaptation layer, a response message to the request for route broadcast message if, during the predetermined amount of time, the higher protocol layer has sent the indication to the network adaptation layer that the reply message has been generated.

18. The method of claim 14, wherein the higher layer operates in accordance with Internet Protocol (IP).

19. In a network, an arrangement for determining a route from a source node to another node, wherein a request for route broadcast message is used to discover and establish routes between the source node and the another node, the arrangement comprising:

means for generating, in the source node, a broadcast message for which the source node expects a reply message;

means for placing the broadcast message in a request for route broadcast message;

means for broadcasting, from the source node, the request for route broadcast message to neighboring nodes;

means for determining, in one of the neighboring nodes, whether the one of the neighboring nodes is a node which generates the reply message;

means for storing in each of the neighboring nodes a temporary route back to the source node; and

means for rebroadcasting the request for route broadcast message to all nodes which are neighboring nodes of the one of the neighboring nodes which has received the request for route broadcast message.

20. The arrangement of claim 19, further comprising:

means for generating a response message to the request for route broadcast message if the one of the neighboring nodes is the node which generates the reply message;

means for placing the reply message in the response to the broadcast message; and

means for sending the response message to the source node over the temporary route stored in each neighboring node in a path between the source node and the node which generated the reply message.

21. The arrangement of claim 20, further comprising:

means for activating a route, in each of the neighboring nodes in the route between the source node and the node which generates the reply message, as the response message is sent from the node which generates the reply message to the source node.

22. In a network, an arrangement for determining a route from a source node to another node, wherein a request for route broadcast message is used to discover and establish routes between the source node and the another node, the arrangement comprising:

means for generating, in the source node, a broadcast message for which the source node expects a reply message;

means for placing the broadcast message in a request for route broadcast message;

means for broadcasting, from the source node, the request for route broadcast message to neighboring nodes; and

means for determining, in one of the neighboring nodes, whether the one of the neighboring nodes is a node which generates the reply message,

wherein the source node, the neighboring nodes and the node which generates the reply message operate according to Bluetooth protocol.

23. In a network, an arrangement for determining a route from a source node to another node, wherein a request for route broadcast message is used to discover and establish routes between the source node and the another node, the arrangement comprising:

means for generating, in the source node, a broadcast message for which the source node expects a reply message;

means for placing the broadcast message in a request for route broadcast message;

means for broadcasting, from the source node, the request for route broadcast message to neighboring nodes;

means for determining, in one of the neighboring nodes, whether the one of the neighboring nodes is a node which generates the reply message;

means for receiving, at one of the neighboring nodes, the request for route broadcast message;

means for waiting a predetermined amount of time;

means for examining the request for route broadcast message to determine whether the request for route broadcast message contains the broadcast message for which the source node expects the reply message; and

means for determining, if the request for route broadcast message contains the broadcast message for which the source node expects the reply message, if the one of the neighboring nodes is the node which generates the reply message.

24. The arrangement of claim 23, further comprising:

means for rebroadcasting the request for route broadcast message if, after the expiration of the predetermined amount of time, it has not been determined that the one of the neighboring nodes is the node which generates the reply message.

25. The arrangement of claim 23, further comprising:

means for generating a response message to the request for route broadcast message if, during the predetermined amount of time, it is determined that the neighboring node is the node that generates the reply message.

26. The arrangement of claim 25, wherein the response message contains the reply message.

27. In a network, an arrangement for determining a route from a source node to another node, wherein a request for route broadcast message is used to discover and establish routes between the source node and the another node, the arrangement comprising:

means for generating, in the source node, a broadcast message for which the source node expects a reply message;

means for placing the broadcast message in a request for route broadcast message;

means for broadcasting, from the source node, the request for route broadcast message to neighboring nodes;

means for determining, in one of the neighboring nodes, whether the one of the neighboring nodes is a node which generates the reply message;

means for waiting a predetermined amount of time; and

means for determining whether a higher protocol layer has sent an indication to a lower protocol layer that a reply message has been generated.

28. The arrangement of claim 27, further comprising:

means for rebroadcasting the request for route broadcast message if, after the predetermined amount of time, the higher protocol layer has not sent the indication that the reply message has been generated.

29. The arrangement of claim 27, further comprising:

means for generating a response message to the request for route broadcast message if, during the predetermined amount of time, the higher protocol layer has sent the indication that a reply message has been generated.

30. In a network, an arrangement for determining a route from a source node to another node, wherein a request for route broadcast message is used to discover and establish routes between the source node and the another node, the arrangement comprising:

means for generating, in the source node, a broadcast message for which the source node expects a reply message;

means for placing the broadcast message in a request for route broadcast message;

means for broadcasting, from the source node, the request for route broadcast message to neighboring nodes; and

means for determining, in one of the neighboring nodes, whether the one of the neighboring nodes is a node which generates the reply message,

wherein the broadcast message for which the source node expects a reply message is formed in accordance with name resolution protocol.

31. In a network, an arrangement for determining a route from a source node to another node, wherein a request for route broadcast message is used to discover and establish routes between the source node and the another node, the arrangement comprising:

means for generating, in the source node, a broadcast message for which the source node expects a reply message;

means for placing the broadcast message in a request for route broadcast message;

means for broadcasting, from the source node, the request for route broadcast message to neighboring nodes; and

means for determining, in one of the neighboring nodes, whether the one of the neighboring nodes is a node which generates the reply message,

wherein the broadcast message for which the source node expects a reply message is formed in accordance with dynamic host configuration protocol (DHCP).

32. In a network, an arrangement for determining a route from a source node to another node, wherein all nodes in the network include a network adaptation layer and a higher protocol layer, the arrangement comprising:

means for generating, in the higher protocol layer of the source node, a broadcast message for which the source node expects a reply message;

means for placing the broadcast message for which the source node expects a reply message in a network adaptation layer request for route broadcast message; and

means for broadcasting, from the source node, the network adaptation layer request for route broadcast message to neighboring nodes.

33. The arrangement of claim 32, further comprising:

means for waiting a predetermined amount of time; and

means for determining whether a higher protocol layer has sent an indication to the network adaptation layer that the reply message has been generated.

34. The arrangement of claim 33, further comprising:

means for rebroadcasting the request for route broadcast message if, after the predetermined amount of time, the higher protocol layer has not sent the indication to the network adaptation layer that the reply message has been generated.

35. The arrangement of claim 33, further comprising:

means for generating, in the network adaptation layer, a response message to the request for route broadcast message if, during the predetermined amount of time, the higher protocol layer has sent the indication to the network adaptation layer that the reply message has been generated.

36. The arrangement of claim 32, wherein the higher layer operates in accordance with Internet Protocol (IP).