Optimal clustering of master-slave ad-hoc wireless network

• US 20050063313A1
• Filed: 07/03/2001
• Published: 03/24/2005
• Est. Priority Date: 07/03/2001
• Status: Abandoned Application

• Current Assignee: Lenovo Singapore Pte Limited (Lenovo Group Ltd.)
• Original Assignee: International Business Machines Corporation
• Inventors: Nanavati, Amit Anil, Kapoor, Sanjiv, Balaji, Kannan
• Application Number:
  US09/898,162
• Publication Number:
  US 20050063313A1
• Time in Patent Office: Days
• US Class Current: 370/252
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: H04W 92/02 Inter-networking arrangements

Abstract

The present invention relates to a system and method for optimal clustering of master-slave ad-hoc wireless network for minimizing the number of masters and thereby the number of communication hops. It comprises assigning master or slave status to each node and connecting slave nodes to master nodes to form subgroups based on defined optimization parameters and the constraints and characteristics of the network. After that said subgroups are interconnected to form a single cluster either by connecting a slave node at the boundary of one subgroup to the master of an adjacent subgroup where possible, or by connecting two adjacent master nodes together or by converting a slave node at the boundary to a master and linking it to the slave nodes or master nodes in the adjacent subgroups.

Claims

1. The method for optimal clustering of master-slave ad-hoc wireless network, comprising:

assigning master or slave status to each node and connecting slave nodes to master nodes to form subgroups based on defined optimization parameters and the constraints and characteristics of the network;

interconnecting said subgroups to form a single cluster either by connecting a slave node at the boundary of one subgroup to the master of an adjacent subgroup where possible, or by connecting two adjacent master nodes together or by converting a slave node at the boundary to a master and linking it to the slave nodes or master nodes in the adjacent subgroups.

2. A method as claimed in claim 1, wherein each node is assigned master or slave based on the degree of connectivity of said node with other unassigned nodes.

3. A method as claimed in claim 1, wherein said assignment is implemented by a single entity located either within the cluster as one of the nodes or outside the cluster.

4. A method as claimed in claim 1, wherein the formation of clusters and interconnection between the said clusters is based on weight associated with each node in the network where the weight of a node depends upon the number of nodes in its neighborhood.

5. A method as claimed in claim 1 is applied to the formation of a scatternet in a Bluetooth network.

6. A method as claimed in claim 1 wherein activities in steps 1 and 2 are carried out in a distributed manner at each node further comprising:

assigning master or slave status to itself by each node based on the master or slave or unassigned status of all neighboring connected nodes,

forming subgroups around each master node,

merging said subgroups by forming slave-slave bridges or slave-master bridges or master-master bridges wherever possible based on network constraints or by forming additional masters where necessary.

7. A method as claimed in claim 6 is applied to the formation of a Bluetooth scatternet.

8. The system for optimal clustering of master-slave ad-hoc wireless network, comprising:

means for assigning master or slave status to each node and connecting slave nodes to master nodes to form subgroups based on defined optimization parameters and the constraints and characteristics of the network;

means for interconnecting said subgroups to form a single cluster either by connecting a slave node at the boundary of one subgroup to the master of an adjacent subgroup where possible, or by connecting two adjacent master nodes together or by converting a slave node at the boundary to a master and linking it to the slave nodes or master nodes in the adjacent subgroups.

9. A system as claimed in claim 8, wherein means for assigning master or slave status to each node is based on the degree of connectivity of said node with other unassigned nodes.

10. A system as claimed in claim 8, wherein means to implement the said assignment is carried out by a single entity located either within the cluster as one of the nodes or outside the cluster.

11. A system as claimed in claim 8, wherein the formation of clusters and means for interconnection between the clusters is based on weight associated with each node in the network where the weight of a node depends upon the number of nodes in its neighborhood.

12. A system as claimed in claim 8 is used for the formation of a scatternet in a Bluetooth network.

13. A system as claimed in claim 8, wherein said means in steps 1 and 2 operate in a distributed manner at each node further comprising:

means for assigning master or slave status to itself by each node based on the master or slave or unassigned status of all neighboring connected nodes,

means for forming subgroups around each master node,

means for merging said subgroups by forming slave-slave bridges or slave-master bridges or master-master bridges wherever possible based on network constraints or by forming additional masters where necessary.

14. A system as claimed in claim 13 is used for the formation of a Bluetooth scatternet.

15. The computer program product comprising computer readable program code stored on a computer program readable storage medium embodied therein for optimal clustering of master-slave ad-hoc wireless network, comprising:

computer readable program code means configured for assigning master or slave status to each node and connecting slave nodes to master nodes to form subgroups based on defined optimization parameters and the constraints and characteristics of the network;

computer readable program code means configured for interconnecting said subgroups to form a single cluster either by connecting a slave node at the boundary of one subgroup to the master of an adjacent subgroup where possible, or by connecting two adjacent master nodes together or by converting a slave node at the boundary to a master and linking it to the slave nodes or master nodes in the adjacent subgroups.

16. A computer program product as claimed in claim 15, wherein computer readable program code means configured for assigning master or slave status to each node is based on the degree of connectivity of said node with other unassigned nodes.

17. A computer program product as claimed in claim 15, wherein computer readable program code means configured to implement the said assignment is carried out by a single entity located either within the cluster as one of the nodes or outside the cluster.

18. A computer program product as claimed in claim 15, wherein the formation of clusters and computer readable program code means configured to interconnect between the clusters is based on weight associated with each node in the network where the weight of a node depends upon the number of nodes in its neighborhood.

19. A computer program product as claimed in claim 15 is configured for the formation of a scatternet in a Bluetooth networks.

20. A computer program product as claimed in claim 15 wherein computer readable program code means in steps 1 and 2 operate in a distributed manner at each node further comprising:

computer readable program code means configured for assigning master or slave status to itself by each node based on the master or slave or unassigned status of all neighboring connected nodes,

computer readable program code means configured for forming subgroups around each master node,

computer readable program code means configured for merging said subgroups by forming slave-slave bridges or slave-master bridges or master-master bridges wherever possible based on network constraints or by forming additional masters where necessary.

21. A computer program product as claimed in claim 20 is configured for the formation of a Bluetooth scatternet.