Method for intelligent merging of ad hoc network partitions

• US 7,792,050 B2
• Filed: 10/26/2007
• Issued: 09/07/2010
• Est. Priority Date: 10/26/2007
• Status: Active Grant

• Current Assignee: ARRIS Enterprises LLC (CommScope Holding Company, Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Metke, Anthony R., Ekl, Randy L.
• Primary Examiner(s): Pham, Chi H.
• Assistant Examiner(s): HOM, SHICK C
• Application Number:
  US11/924,859
• Publication Number:
  US 20090109870A1
• Time in Patent Office: 1,047 Days
• Field of Search: None
• US Class Current: 370/252
• CPC Class Codes: H04L 45/46 Cluster building
• CPC Class Codes: H04L 63/104 Grouping of entities
• CPC Class Codes: H04L 63/20 for managing network security; network security policies in general filtering policies H04L63/0227
• CPC Class Codes: H04W 12/06 Authentication
• CPC Class Codes: H04W 40/32 for defining a routing cluster membership

Abstract

A method for merging of ad hoc network partitions within an ad hoc network, the method includes forming a plurality of network partitions by forming a security association among each of a group of partitioned nodes. Each network partition includes a Network Identifier. A node operating within one of the network partitions receives an update message from another node, compares its current Network Identifier to the received Network Identifier; and determines whether to update to the received Network Identifier using an arbitration method when the received Network Identifier is different from the current Network Identifier.

Claims

1. A method of operation of a node within an ad hoc network, the method comprising:

monitoring one or more messages from one or more other nodes in the ad hoc network to identify a Network Name and a Network Identifier associated with each of the other nodes;

comparing each Network Name with a current Network Name of the node;

for each of the other nodes having the same Network Name as the current Network Name of the node, comparing each Network Identifier with a current Network Identifier of the node; and

when at least one Network Identifier of at least one other node is different from the current Network Identifier of the node, using an arbitration method to determine if the node should change the current Network Identifier to a second Network Identifier,

wherein the arbitration method comprises;

comparing a parameter value associated with each of the at least one other node and the node; and

changing the current Network Identifier of the node to the second Network Identifier of one of the other nodes having the same Network Name using one of the criteria selected from a group comprising (a) when the parameter value of the at least one other node is lower than parameter value of the node, (b) when the parameter value of the at least one other node is higher than the parameter value of the node, and (c) when the parameter value of the at least one other node is closer to a target parameter value than the parameter value of the node.

2. The method as claimed in claim 1, wherein the Network Name comprises a Service Set Identifier.

3. The method as claimed in claim 1, wherein the Network Identifier comprises a Basic Service Set Identifier.

4. The method as claimed in claim 1, wherein the parameter value is selected from a group comprising the Network Identifier, a timestamp, and a randomly chosen number.

5. The method as claimed in claim 1, further comprising:

transmitting an indication that it has changed its Network Identifier to the second Network Identifier to one or more neighbor nodes, wherein the one or more neighbor nodes operate using the original Network Identifier.

6. The method as claimed in claim 1, further comprising:

forming security associations between the node and one or more neighbor nodes, wherein the one or more neighbor nodes operate using the second Network Identifier.

7. The method as claimed in claim 1, where the arbitration method comprises:

transmitting a Network Identifier update message to one of the other nodes having the same Network Name, when the second Network Identifier is higher than the current Network Identifier, wherein the Network Identifier update message informs the other nodes to change to the current Network Identifier of the node.

8. A method of operation of a node within an ad hoc network, the method comprising:

operating the node within a portion of the ad hoc network using a Network Name and a current Network Identifier, wherein a first parameter value is associated with the node;

receiving a Network Identifier update message including a second Network Identifier and a second parameter value from another node operating within the portion of the ad hoc network using the Network Name;

comparing the second parameter value to the first parameter value; and

operating the node using the second Network Identifier when the second parameter value meets a pre-determined criteria, wherein the pre-determined criteria is selected from a group comprising (a) the second parameter value is lower than the first parameter value, (b) the second parameter value is higher than the first parameter value, and (c) the second parameter value is closer to a target parameter value than the first parameter value.

9. The method as claimed in claim 8, wherein the parameter value is selected from a group comprising the Network Identifier, a timestamp, and a randomly chosen number.

10. The method as claimed in claim 8, wherein the Network Name comprises a Service Set Identifier.

11. The method as claimed in claim 8, wherein the current Network Identifier comprises a first Basic Service Set Identifier, and wherein the second Network Identifier comprises a second Basic Service Set Identifier.

12. The method as claimed in claim 8, further comprising:

transmitting an indication that it has changed its Network Identifier to the second Network Identifier to one or more neighbor nodes, wherein the one or more neighbor nodes operate using the current Network Identifier.

13. The method as claimed in claim 8, further comprising:

forming security associations between the node and one or more neighbor nodes, wherein the one or more neighbor nodes operate using the second Network Identifier.

14. A method for merging of ad hoc network partitions within an ad hoc network, the method comprising:

forming a first network partition by forming a first security association among a first group of nodes including a first Network Identifier;

forming a second network partition by forming a second security association among a second group of nodes including a second Network Identifier;

communicating a message including the first Network Identifier from a first node of the first group of nodes to a second node of the second group of nodes;

performing a mutual authentication between the first node and the second node;

comparing the first Network Identifier to the second Network Identifier by the second node; and

operating the second node using the first Network Identifier when the first Network Identifier meets a predetermined criteria as compared to the second Network Identifier,

wherein each node has an associated parameter value, and further wherein the predetermined criteria is selected from a group comprising;

(a) a parameter value of the second node is lower than the parameter value of the first node, (b) the parameter value of the second node is higher than the parameter value of the first node, and (c) the parameter value of the second node is closer to a target parameter value than the parameter value of the first node.

15. The method as claimed in claim 14, wherein the message comprises a beacon.

16. The method as claimed in claim 14, wherein the parameter value is selected from a group comprising the Network Identifier, a timestamp, and a randomly chosen number.

17. The method as claimed in claim 14, further comprising:

communicating a Network Identifier update message including the second Network Identifier from the second node to the second group of nodes; and

operating each of the second group of nodes using the second Network Identifier.

18. The method as claimed in claim 17, further comprising:

forming a third network partition by forming a third security association among a third group of nodes including a third Network Identifier;

communicating a message including the third Network Identifier from a third node of the third group of nodes to a fourth node of the second group of nodes;

performing a mutual authentication between the third node and the fourth node;

comparing the third Network Identifier to the first Network Identifier by the fourth node; and

operating the fourth node using the third Network Identifier when the third Network Identifier meets the predetermined criteria as compared to the first Network Identifier.

19. The method as claimed in claim 18, wherein the message comprises a beacon.

20. The method as claimed in claim 18, wherein each node has an associated parameter value, and further wherein the predetermined criteria is selected from a group comprising:

(a) a parameter value of the third node is lower than the parameter value of the fourth node, (b) the parameter value of the third node is higher than the parameter value of the fourth node, and (c) the parameter value of the third node is closer to a target parameter value than the parameter value of the fourth node.

21. The method as claimed in claim 20, wherein the parameter value is selected from a group comprising the Network Identifier, a timestamp, and a randomly chosen number.

22. The method as claimed in claim 20, further comprising:

continuing to operate the fourth node using the first Network Identifier when the third Network Identifier does not meet the predetermined criteria as compared to the first Network Identifier.