Routing protocol selection for an ad hoc network

• US 6,845,084 B2
• Filed: 12/28/2001
• Issued: 01/18/2005
• Est. Priority Date: 12/28/2001
• Status: Active Grant

• Current Assignee: TeleCommunication Systems Inc (Comtech Telecommunications Corporation)
• Original Assignee: TSYS Acquisition Corporation (Comtech Telecommunications Corporation)
• Inventors: Rangnekar, Aniruddha, Quirolgico, Stephen
• Primary Examiner(s): Rao, Seema S.
• Assistant Examiner(s): Harper, Kevin C.
• Application Number:
  US10/028,267
• Publication Number:
  US 20030123419A1
• Time in Patent Office: 1,117 Days
• Field of Search: 370254-255, 370/310, 370/338, 370/347, 370/349, 370/351, 370/400, 370/901, 370464-465, 370/241, 370/252, 709/220, 709/230, 709/238
• US Class Current: 370/254
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/52 Multiprotocol routers
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 48/08 Access restriction or access information delivery, e.g. discovery data delivery signalling during connection H04W76/00
• 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

An ad hoc network includes a set of nodes. A source node in the network attempting to transmit a message to a destination node in the network establishes a common routing protocol between nodes in the network. The source node transmits a request for routing protocol information to a limited number of nodes in the network. The source node receives the routing protocol information from the limited number of nodes and selects a common routing protocol based on the received information. The source node transmits the selected common routing protocol to the nodes in the network.

Claims

1. A method of selecting a common routing protocol in an ad hoc network having a set of nodes, the method comprising steps of:

transmitting a request for routing protocol information to a limited number of nodes, the limited number of nodes including a number of nodes less than the number of nodes in the ad hoc network;

receiving routing protocol information from one or more of the limited number of nodes;

selecting a common routing protocol based on the received routing protocol information; and

transmitting information associated with the selected common routing protocol to all the nodes in the network.

2. The method of claim 1, wherein the selected common routing protocol is a routing protocol to be used by the set of nodes to facilitate multi-hop communication within the ad hoc network and the step of transmitting information further comprises transmitting at least one of an identification of the selected common routing protocol and a selected common routing protocol object to all the nodes in the network.

3. The method of claim 1, wherein the set of nodes are configured to use one of a set of routing protocols, and the routing protocol information transmitted from each of the limited number of nodes comprises a currently used routing protocol and one or more routing protocols that are available for use.

4. The method of claim 3, wherein the step of selecting further comprises steps of:

determining whether a majority of the limited number of nodes is currently using a same routing protocol;

selecting the same routing protocol as the common routing protocol in response to the majority currently using the same routing protocol; and

selecting a routing protocol that is available for use to a largest number of the limited number of nodes in response to no majority existing.

5. The method of claim 1, wherein the step of selecting further comprises steps of:

storing the received routing protocol information in a memory; and

retrieving the stored routing protocol information from the memory after a predetermined period of time; and

selecting the common routing protocol based at least on the retrieved routing protocol information.

6. The method of claim 1, wherein the steps of claim 1 are performed by a source node, and the limited number of nodes are in a zone, the zone having a radius based on a predetermined number of hops from the source node.

7. The method of claim 1, wherein the network comprises a source node configured to transmit a message to a destination node, and further comprising steps of:

the source node determining whether a route to the destination node is included in a routing table for the source node in order to transmit a message to the destination node; and

the source node performing the steps of claim 1 in response to the route not being included in the routing table.

8. A method of selecting a routing protocol for use in a node in an ad hoc network, the method comprising steps of:

receiving a first message identifying a first routing protocol;

receiving a second message identifying a second routing protocol; and

selecting one of the first and second routing protocols for use in the node;

wherein the step of selecting further comprises steps of;

determining whether a predetermined period of time since the first message was received is expired;

selecting the second routing protocol in response to the predetermined period of time bring expired; and

selecting one of the first and second routing protocols for use in the node based on predetermined criteria in response to the predetermined period of time not being expired;

determining whether the source node identification for the second message is less than the source node identification for the first message in response to the predetermined period of time not being expired;

selecting the second routing protocol for use in response to the source node identification for the second message being less than the source node identification for the first message; and

selecting the first routing protocol for use in response to the source node identification for the second message not being less than the source node identification for the first message.

9. An ad hoc network system comprising:

a set of nodes in an ad hoc network, each node being configured to use one of a set of routing protocols,

wherein a source node in the network transmits a request for routing protocol information to nodes within a predetermined number of hops from the source node;

the source node receives protocol information from the nodes within the predetermined number of hops;

the source node selects a common routing protocol based on the received routing protocol information; and

the source node transmits information associated with the selected common routing protocol to the whole network.

10. The system of claim 9, wherein the common routing protocol includes a routing protocol to be used by the set of nodes to facilitate multi-hop communication within the ad hoc network.

11. The system of claim 10, wherein the routing protocol information transmitted comprises a currently used routing protocol and one or more available routing protocols that are available for use to the nodes within the predetermined number of hops.

12. The system of claim 11, wherein the common routing protocol is a routing protocol currently used by a majority of the nodes within the predetermined number of hops.

13. The system of claim 11, wherein the common routing protocol is a routing protocol that is available for use to a largest number of the nodes within the predetermined number of hops.

14. A source node of a set of nodes in an ad hoc network, the source node comprising:

a transmitter transmitting a request for routing protocol information to nodes within a predetermined number of hops from the source node;

a receiver receiving protocol information from the nodes within the predetermined number of hops;

a memory storing the received protocol information; and

a processor selecting a common routing protocol based on the received routing protocol information for transmission to all the nodes in the network through the transmitter.

15. The source node of claim 14, wherein the processor retrieves the received routing protocol information from the memory after a predetermined period of time from the transmission of the request.

16. The source node of claim 15, wherein the period of time is based on a maximum time for a message to travel the predetermined number of hops from a node and return to that node.

17. The source node of claim 14, wherein the routing protocol information comprises a currently used routing protocol and one or more routing protocols that are available for use to the nodes within the predetermined number of hops.

18. The source node of claim 17, wherein the selected common routing protocol includes one of a routing protocol currently used by a majority of the nodes within the predetermined number of hops and a routing protocol that is available for use to a largest number of the nodes within the predetermined number of hops.

19. Apparatus for selecting a common routing protocol in a network having a set of nodes, comprising:

a transmitter to transmit a request for routing protocol information to a limited number of said nodes, said limited number of said nodes being less than a total number of nodes in said network;

a receiver to receive routing protocol information from one or more of said limited number of said nodes;

a selector to select a common routing protocol based on said received routing protocol information;

a transmitter to transmit information associated with said selected common routing protocol to all nodes in said network.

20. The apparatus for selecting a common routing protocol in a network having a set of nodes according to claim 19, wherein:

said selected common routing protocol is a routing protocol to be used by said nodes to facilitate multi-hop communication within said network; and

said transmitter further transmits at least one of an identification of said selected common routing protocol and a selected common routing protocol object to all said nodes in said network.

21. The apparatus for selecting a common routing protocol in a network having a set of nodes according to claim 19, wherein:

said nodes are configured to use one of a set of routing protocols, and

said routing protocol information transmitted from each of said limited number of nodes comprises a currently used routing protocol and one or more routing protocols that are available for use.

22. Apparatus for selecting a common routing protocol in a network having a set of nodes, comprising:

means for transmitting a request for routing protocol information to a limited number of nodes, said limited number of nodes including a number of nodes less than a number of nodes in said network;

means for receiving routing protocol information from one or more of said limited number of nodes;

means for selecting a common routing protocol based on said received routing protocol information; and

means transmitting information associated with said selected common routing protocol to all said nodes in said network.

23. A method of selecting a common routing protocol in a network having a set of nodes, comprising:

configuring each node in a network to use one of a set of routing protocols;

transmitting from a source node a request for routing protocol information to nodes within a predetermined number of hops from said source node;

receiving protocol information by said source node from said nodes within said predetermined number of hops;

selecting a common routing protocol by said source node based on said receiving routing protocol information;

transmitting information associated with said selected common routing protocol from said source node to sail network.

24. The method of selecting a common routing protocol in a network set of nodes according to claim 23, wherein:

said common routing protocol includes a routing protocol to be used by said set of nodes to facilitate multi-hop communication within said network.

25. The method of selecting a common routing protocol in a network having a set of nodes according to claim 24, wherein:

said routing protocol comprises a currently used routing protocol and one or more available routing protocols that are available for use to sad nodes within said predetermined number of hops.

26. The method of selecting common routing protocol in a network having a set of nodes according to claim 23, wherein:

said common routing protocol is a routing protocol currently used by a majority of said nodes within said predetermined number of hops.

27. The method of selecting common routing protocol in a network having a set of nodes according to claim 23, wherein:

said common routing protocol is a routing protocol that is available for use to a largest number of said nodes within the predetermined number of hops.

28. Apparatus for selecting a common routing protocol in a network having a set of nodes, comprising:

means for configuring each node in a network to use one of a set of routing protocols;

means for transmitting from a source node a request for routing protocol information to nodes within a predetermined number of hops from said source node;

means for receiving protocol information by said source node from said nodes within said predetermined number of hops;

means for selecting a common routing protocol by said source node based on said receiving routing protocol information;

means for transmitting information associated with said selected common routing protocol from said source node to said network.