Clustering in wireless ad hoc networks

• US 6,876,643 B1
• Filed: 08/08/2000
• Issued: 04/05/2005
• Est. Priority Date: 08/08/2000
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Sarkar, Abhinanda, Ramachandran, Lakshmi, Kapoor, Manika, Aggarwal, Alok
• Primary Examiner(s): Duong, Frank
• Assistant Examiner(s): Moore, Jr., Michael J.
• Application Number:
  US09/634,123
• Time in Patent Office: 1,701 Days
• Field of Search: 370/338, 370/913, 370/328, 370/254, 370/255, 370/449, 370/457
• US Class Current: 370/338
• CPC Class Codes: H04W 4/08 User group management
• CPC Class Codes: H04W 8/005 Discovery of network devices, e.g. terminals
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: H04W 84/20 Master-slave selection or change arrangements
• CPC Class Codes: H04W 92/02 Inter-networking arrangements

Abstract

A method, system, and computer program product for organizing a set of nodes into a minimum number of connected clusters of bounded size in a wireless transmission system, wherein the method comprises using of bits in packets used in the initial stages of the device discovery procedure, to include information relating to a state of device discovery to achieve the separation of the nodes into those in the transmit-state and the receive-state; defining a Master-designate among the nodes through a statistical procedure and defining remaining nodes as a Slave-designate; defining a cluster including the Master-designate and at least one the Slave-designate, wherein the Slave-designate continuously scans for the inquiry message transmitted from the Master-designate and the Slave-designate transmits the inquiry response to the Master-designate.

Claims

1. A method for organizing a set of nodes into a minimum number of connected clusters in a wireless transmission system, said method comprising steps of:

using of bits in packets used in the initial stages of a device discovery procedure, to include information relating to a state of said nodes during the initial stages of the procedure;

setting parameters in the procedure for device discovery to achieve a separation of the nodes into those in a transmit-state and a receive-state;

defining Master-designates among said nodes through a statistical procedure and defining remaining nodes Slave-designates; and

defining clusters including said Master-designates and at least one said Slave-designate, wherein said Slave-designate continuously scans for an inquiry message transmitted from said Master-designate and said Slave-designate transmits an inquiry response to said Master-designate upon receiving said inquiry message to establish a connection between said Master-designate and said Slave-designate,

wherein at least one Super-master-designate is selected from said Master-designates and at least one Proxy-Slave is selected for each Master-designate.

3. The method according to the claim 1, wherein said bits in said packets are transmitted in initial stages of discovery of nodes and include information to convey states of said nodes.

7. The method according to the claim 1, wherein said wireless transmission system is a Bluetooth System.

2. A method for organizing a set of nodes into a minimum number of connected clusters in a wireless transmission system, said method comprising steps of:

using of bits in packets used in the initial stages of a device discovery procedure, to include information relating to a state of said nodes during the initial stages of the procedure;

setting parameters in the procedure for device discovery to achieve a separation of the nodes into those in a transmit-state and a receive-state;

defining Master-designates among said nodes through a statistical procedure and defining remaining nodes as Slave-designates; and

defining clusters including said Master-designates and at least one said Slave-designate, wherein said Slave-designate continuously scans for an inquiry message transmitted from said Master-designate and said Slave-designate transmits an inquiry response to said Master-designate upon receiving said inquiry message to establish a connection between said Master-designate and said Slave-designate,

wherein at least one Super-master-designate is selected from said Master-designates and at least one Proxy-Slave is selected for each Master-designate, said method further comprising a step of communicating between said Super-master-designate of one of said clusters and said Proxy-Slave of other of said clusters such that said Super-master-designate collects information of said clusters from each of said Proxy-Slave having an predetermined ID.

4. A method for organizing a set of nodes into a minimum number of connected clusters in a wireless transmission system, said method comprising steps of:

using of bits in packets used in the initial stages of a device discovery procedure, to include information relating to a state of said nodes during the initial stages of the procedure;

setting parameters in the procedure for device discovery to achieve a separation of the nodes into those in a transmit-state and a receive-state;

defining Master-designates among said nodes through a statistical procedure and defining remaining nodes as Slave-designates; and

defining clusters including said Master-designates and at least one said Slave-designate, wherein said Slave-designate continuously scans for an inquiry message transmitted from said Master-designate and said Slave-designate transmits an inquiry response to said Master-designate upon receiving said inquiry message to establish a connection between said Master-designate and said Slave-designate,

wherein at least one Super-master-designate is selected from said Master-designates and at least one Proxy-Slave is selected for each Master-designate, and

wherein an interval of an inquiry scan is close to a duration of a scan window for said inquiry scan.

5. A method for organizing a set of nodes into a minimum number of connected clusters in a wireless transmission system, said method comprising steps of:

using of bits in packets used in the initial stages of a device discovery procedure, to include information relating to a state of said nodes during the initial stages of the procedure;

setting parameters in the procedure for device discovery to achieve a separation of the nodes into those in a transmit-state and a receive-state;

defining Master-designates among said nodes through a statistical procedure and defining remaining nodes as Slave-designates; and

defining clusters including said Master-designates and at least one said Slave-designate, wherein said Slave-designate continuously scans for an inquiry message transmitted from said Master-designate and said Slave-designate transmits an inquiry response to said Master-designate upon receiving said inquiry message to establish a connection between said Master-designate and said Slave-designate,

wherein said bits in said packet include information selected from the group consisting of numbers of responses received by said node by a predetermined period, numbers of said nodes included in said cluster, whether or not said node transmitting said inquiry response is included in said cluster, and whether or not said node transmitting said inquiry response is said Master-designate.

6. A method for organizing a sat of nodes into a minimum number of connected clusters in a wireless transmission system, said method comprising stops of:

using of bits in packets used in the initial stages of a device discovery procedure, to include information relating to a state of said nodes during the initial stages of the procedure;

setting parameters in the procedure for device discovery to achieve a separation of the nodes into those in a transmit-state and a receive-state;

defining Master-designates among said nodes through a statistical procedure and defining remaining nodes as Slave-designates; and

defining clusters including said Master-designates and at least one said Slave-designate, wherein said Slave-designate continuously scans for an inquiry message transmitted from said Master-designate and said Slave-designate transmits an inquiry response to said Master-designate upon receiving said inquiry message to establish a connection between said Master-designate and said Slave-designate,

wherein at least one Super-master-designate is selected from said Master-designates and at least one Proxy-Slave is selected for each Master-designate, and

wherein said statistical procedure includes Bermoulli trials executed by each node.

8. A system for organizing a set of nodes into a minimum number of connected clusters of bounded size in a wireless transmission system, said system comprising:

means for using of bits in packets used in the initial stages of a device discovery procedure, to include information relating to a state of said nodes during the initial stages of the procedure;

means for setting parameters in the procedure for device discovery to achieve a separation of the nodes into those in a transmit-state and a receive-state;

means for defining a Master-designate among said nodes through a statistical procedure and defining remaining nodes as a Slave-designate; and

means for defining a cluster including said Master-designate and at least one said Slave-designate, wherein said Slave-designate continuously scans for an inquiry message transmitted from said Master-designate and said Slave-designate transmits an inquiry response to said Master-designate upon receiving said inquiry message to establish a connection between said Master-designate and said Slave-designate,

wherein at least one Super-master-designate is selected from said Master-designates and at least one Proxy-Slave is selected for each Master-designate.

10. The system according to the claim 8, wherein said bits in said packets are transmitted in initial stages of discovery of nodes and include information to convey states of said nodes.

14. The system according to the claim 8, wherein said wireless transmission system is a Bluetooth System.

15. The system according to the claim 14, wherein nodes which are connected as slaves in a piconet carry on a node discovery on behalf or in addition to said Master-designate such that a piconet/scatternet for the Bluetooth system is formed.

9. A system for organizing a set of nodes into a minimum number of connected clusters of bounded size in a wireless transmission system, said system comprising:

means for using of bits in packets used in the initial stages of a device discovery procedure, to include information relating to a state of said nodes during the initial stages of the procedure;

means for setting parameters in the procedure for device discovery to achieve a separation of the nodes into those in a transmit-state and a receive-state;

means for defining a Master-designate among said nodes through a statistical procedure and defining remaining nodes as a Slave-designate; and

means for defining a cluster including said Master-designate and at least one said Slave-designate, wherein said Slave-designate continuously scans for an inquiry message transmitted from said Master-designate and said Slave-designate transmits an inquiry response to said Master-designate upon receiving said inquiry message to establish a connection between said Master-designate and said Slave-designate,

wherein at least one Super-master-designate is selected from said Master-designate and at least one Proxy-Slave is selected for each Master-designate, said system further comprising means for communicating between said Super-master-designate of one of said clusters and said Proxy-Slave of other of said clusters such that said Super-master-designate collects information of said clusters from each of said Proxy-Slave having a predetermined ID.

11. A system for organizing a set of nodes into a minimum number of connected clusters of bounded size in a wireless transmission system, said system comprising:

means for using of bits in packers used in initial stages of a device discovery procedure, to include information relating to a state of said nodes during the initial stages of the procedure;

means for setting parameters in the procedure for device discovery to achieve a separation of the nodes into those in a transmit-state and a receive-state;

means for defining a Master-designate among said nodes through a statistical procedure and defining remaining nodes as a Slave-designate; and

means for defining a cluster including said Master-designate and at least one said Slave-designate, wherein said Slave-designate continuously scans for an inquiry message transmitted from said Master-designate and said Slave-designate transmits an inquiry response to said Master-designate upon receiving said inquiry message to establish a connection between said Master-designate and said Slave-designate,

wherein at least one Super-master-designate is selected from said Master-designates and at least one Proxy-Slave is selected for each Master-designate, and

wherein an interval of an inquiry scan is close to a duration of a scan window for said inquiry scan.

12. A system for organizing a set of nodes into a minimum number of connected clusters of bounded size in a wireless transmission system, said system comprising:

means for using of bits in packets used in the initial stages of a device discovery procedure, to include information relating to a state of said nodes during the initial stages of the procedure;

means for setting parameters in the procedure for device discovery to achieve a separation of the nodes into those in a transmit-state and a receive-state;

means for defining a Master-designate among said nodes through a statistical procedure and defining remaining nodes as a Slave-designate; and

means for defining a cluster including said Master-designate and at least one said Slave-designate, wherein said Slave-designate continuously scans for an inquiry message transmitted from said Master-designate and said Slave-designate transmits an inquiry response to said Master-designate upon receiving said inquiry message to establish a connection between said Master-designate and said Slave-designate,

wherein said bits in said packets include information selected from the group consisting of numbers of responses received by said node by a predetermined period, numbers of said nodes included in said cluster, whether or not said node transmitting said inquiry response is included in said cluster, and whether or not said node transmitting said inquiry response is said Master-designate.

13. A system for organizing a set of nodes into a minimum number of connected clusters of bounded size in a wireless transmission system, said system comprising:

means for using of bits in packets used in the initial stages of a device discovery procedure, to include information relating to a state of said nodes during the initial stages of tire procedure;

means for setting parameters in the procedure for device discovery to achieve a separation of the nodes into those in a transmit-state and a receive-state;

means for defining a Master-designate among said nodes through a statistical procedure and defining remaining nodes as a Slave-designate; and

means for defining a cluster including said Master-designate and at least one said Slave-designate, wherein said Slave-designate continuously scans for an inquiry message transmitted from said Master-designate and said Slave-designate transmits an inquiry response to said Master-designate upon receiving said inquiry message to establish a connection between said Master-designate and said Slave-designate,

wherein at least one Super-master-designate is selected from said Master-designates and at least one Proxy-Slave is selected for each Master-designate, and

wherein said statistical procedure includes Bernoulli trials executed by each node.

16. A computer program product having a computer readable medium having a computer program recorded therein for organizing a set of nodes into a minimum number of connected clusters of bounded size in a wireless transmission system, said computer program product including:

computer program code means for using of bits in packets used in an initial stages of a device discovery procedure, to include information relating to a state of said nodes during the initial stages of the procedure;

computer program code means for setting parameters in the procedure for device discovery to achieve a separation of the nodes into those in a transmit-state and a receive-state;

computer program code means for defining a Master-designate among said nodes through a statistical procedure and defining remaining nodes as Slave-designates; and

computer program code means for defining a cluster including said Master-designate and at least one said Slave-designate, wherein said Slave-designate continuously scans for an inquiry message transmitted from said Master-designate and said Stave-designate transmits an inquiry response to said Master-designate upon receiving said inquiry message to establish a connection between said Master-designate and said Slave-designate,

wherein at least one Super-master-designate is selected from said Master-designates and at least one Proxy-Slave is selected for each Master-designate.

18. The computer program product according to the claim 16, wherein said bits in said packets are transmitted in initial stages of discovery of nodes and include information to convey states of said nodes.

22. The computer program product according to the claim 16, wherein said wireless transmission system is a Bluetooth System.

17. A computer program product having a computer readable medium having a computer program recorded therein for organizing a set of nodes into a minimum number of connected clusters of bounded size in a wireless transmission system, said computer program product including;

computer program code means for using of bits in packets used in an initial stages of a device discovery procedure, to include information relating to a state of said nodes during the initial stages of the procedure;

computer program code means for setting parameters in the procedure for device discovery to achieve a separation of the nodes into those in a transmit-state and a receive-state;

computer program code means for defining a Master-designate among said nodes through a statistical procedure and defining remaining nodes as Slave-designates; and

computer program code means for defining a cluster including said Master-designate and at least one said Slave-designate, wherein said Slave-designate continuously scans for an inquiry message transmitted from said Master-designate and said Stave-designate transmits an inquiry response to said Master-designate upon receiving said inquiry message to establish a connection between said Master-designate and said Slave-designate,

wherein at least one Super-master-designate is selected from said Master-designates and at one Proxy-Slave is selected for each Master-designate, said computer program further comprising means for communicating between said Super-master-designate of one of said clusters and said Proxy-Slave of other of said clusters such that said Super-master-designate collects information of said clusters from each of said Proxy-Slave having a predetermined ID.

19. A computer program product having a computer readable medium having a computer program recorded therein for organizing a set of nodes into a minimum number of connected clusters of bounded size in a wireless transmission system, said computer program product including:

computer program code means for using of bits in packets used in initial stages of a device discovery procedure, to include information relating to a state of said nodes during the initial stages of the procedure;

computer program code means for setting parameters in the procedure for device discovery to achieve a separation of the nodes into those in a transmit-state and a receive-state;

computer program code means for defining a Master-designate among said nodes through a statistical procedure and defining remaining nodes as Slave-designates; and

computer program code means for defining a cluster including said Master-designates and at least one said Slave-designate, wherein said Slave-designate continuously scans for an inquiry message transmitted from said Master-designate and said Slave-designate transmits an inquiry response to said Master-designate upon receiving said inquiry message to establish a connection between said Master-designate and said Slave-designate,

wherein at least one Super-master-designate is selected from said Master-designates and at least one Proxy-Slave is selected for each Master-designate; and

wherein an interval of an inquiry scan is close to a duration of a scan window for said inquiry scan.

20. A computer program product having a computer readable medium having a computer program recorded therein for organizing a set of nodes into a minimum number of connected clusters of bounded size in a wireless transmission system, said computer program product including:

computer program code means for using of bits in packets used in au initial stages of a device discovery procedure, to include information relating to a state of said nodes during the initial stages of the procedure;

computer program code means for setting parameters in the procedure for device discovery to achieve a separation of the nodes into those in a transmit-state and a receive-state;

computer program code means for defining a Master-designate among said nodes through a statistical procedure and defining remaining nodes as Slave-designates; and

computer program code means for defining a cluster including said Master-designate and at least one said Slave-designate, wherein said Slave-designate continuously scans for an inquiry message transmitted from said Master-designate and said Slave-designate transmits an inquiry response to said Master-designate upon receiving said inquiry message to establish a connection between said Master-designate and said Slave-designate,

wherein said bits in packets include information selected from the group consisting of numbers of responses received by said node by a predetermined period, numbers of said nodes included in said cluster, whether or not said node transmitting said inquiry response is included in said cluster, and whether or not said node transmitting said inquiry response is said Master-designate.

21. A computer program product having a computer readable medium having a computer program recorded therein for organizing a set of nodes into a minimum number of connected clusters of bounded size in a wireless transmission system, said computer program product including:

computer program code means for using of bits in packets used in an initial stages of a device discovery procedure, to include information relating to a state of said nodes during the initial stages of the procedure;

computer program code means for setting parameters in the procedure for device discovery to achieve a separation of the nodes into those ma transmit-state and a receive-state;

computer program code means for defining a Master-designate among said nodes through a statistical procedure and defining remaining nodes as Slave-designate; and

computer program code means for defining a cluster including said Master-designate and at least one said Slave-designate, wherein said Slave-designate continuously scans for an inquiry message transmitted from said Master-designate and said Slave-designate transmits an inquiry response to said Master-designate upon receiving said inquiry message to establish a connection between said Master-designate and said Slave-designate,

wherein at least one Super-master-designate is selected from said Master-designates and at least one Proxy-Slave is selected for each Master-designate, and

wherein said statistical procedure includes Bermoulli trials executed by each node.