Balancing clusters of a wireless mesh network

• US 8,031,615 B2
• Filed: 02/27/2007
• Issued: 10/04/2011
• Est. Priority Date: 02/27/2007
• Status: Active Grant

• Current Assignee: Hitachi Energy Limited (Hitachi, Ltd.)
• Original Assignee: Tropos Networks Incorporated (ABB Limited)
• Inventors: Behroozi, Cyrus, Srikrishna, Devabhaktuni, Chari, Amalavoyal, Ren, Wenge
• Primary Examiner(s): Shah; Chirag
• Assistant Examiner(s): SHIVERS, ASHLEY L
• Application Number:
  US11/711,357
• Publication Number:
  US 20080205360A1
• Time in Patent Office: 1,680 Days
• Field of Search: None
• US Class Current: 370/238
• CPC Class Codes: H04W 40/22 using selective relaying for reaching a BTS [Base Transceiver Station] or an access point
• CPC Class Codes: H04W 40/32 for defining a routing cluster membership

Abstract

An apparatus and method of propagating a size of a cluster within a wireless mesh network is disclosed. The method includes a gateway within the cluster maintaining information of access nodes within the cluster. The gateway determines a cluster size based on the maintained information, and transmits routing packets that include the cluster size of the gateway. An apparatus and method of balancing clusters of a wireless mesh network is also disclosed. The method includes the gateway of each cluster originating beacons, wherein the beacons include a size of the cluster of the gateway. The access nodes of each cluster, re-broadcasts beacons received from the gateway of the cluster. A connecting access node selects which cluster to connect to at least in part based on the size of each of the clusters.

Claims

1. A method of propagating information regarding a size of a cluster within a wireless mesh network, comprising:

a gateway within the cluster maintaining information of access nodes within the cluster;

the gateway determining a cluster size based on the maintained information, wherein the cluster size is based on a number of access nodes within the cluster;

the gateway including its cluster size within routing packets;

wherein each connecting access node not within the cluster determines whether to route through the gateway based at least in part on the cluster size of the gateway, and additionally based on a number of devices that are downstream from the connecting access node.

2. The method of claim 1, further comprising access nodes of the cluster that receive cluster size within the routing packets, re-transmitting the cluster size.

3. The method of claim 1, wherein the connected access nodes prefer routing through smaller clusters than larger clusters.

4. The method of claim 1, wherein downstream devices comprise at least one of downstream access nodes and downstream client devices.

5. The method of claim 4 wherein the downstream access nodes are weighted differently than the downstream client devices.

6. The method of claim 1, wherein downstream mobile nodes do not count as downstream devices.

7. The method of claim 1, further comprising the gateway originating and broadcasting the routing packets.

8. The method of claim 1, further comprising the gateway maintaining a routing table that includes the information of access nodes of the cluster.

9. The method of claim 1, further comprising a connecting access node selecting a transmission channel at least in part, based on the cluster size of a gateway operating on that channel.

10. The method of claim 9, wherein connecting nodes prefer selection of transmission channels associated with gateways that have smaller clusters rather than gateways having larger clusters.

11. The method of claim 9, wherein connecting access nodes select the transmission channel based at least in part on a number of downstream devices associated with the connecting access node.

12. The method of claim 11, wherein downstream devices comprise at least one of downstream access nodes and downstream client devices.

13. The method of claim 12 wherein the downstream access nodes are weighted differently than the downstream client devices.

14. A method of balancing clusters of a wireless mesh network, each cluster comprising a gateway, the method comprising:

the gateway of each cluster originating beacons, the beacons comprising a size of the cluster of the gateway, wherein the size of the cluster is based on a number of access nodes within the cluster;

the access nodes of each cluster, re-broadcasting beacons received from the gateway of the cluster;

a connecting access node selecting which cluster to connect to based on the size of each of the clusters, wherein the connecting access node is not within the clusters, and

the connecting access node estimating a projected cluster size by summing the size of each cluster with a number of nodes downstream from the connecting access node, and the connecting access node using the projected cluster size in its routing selection.

15. The method of claim 14, wherein the connecting access node selects a routing path to a gateway of the wireless mesh network based on a combination of routing selection parameters, one of the parameters being the size of clusters the connecting access node receives beacons from.

16. The method of claim 15, wherein connecting access nodes prefer selecting routing paths of gateways having smaller clusters rather than gateways having larger clusters.

17. The method of claim 15, wherein the connecting access node selecting a routing path further includes at least one of a persistence of successfully received beacons, a persistence of successfully received reverse beacons, and a hop count included within re-broadcast beacons.

18. The method of claim 14, wherein the connecting access node selects a transmission channel based at least in part on the size of the clusters the connecting access node receives beacons from.

19. The method of claim 18, wherein the connecting access nodes prefer selecting a transmission channel of a smaller cluster rather than a transmission channel of a larger cluster.

20. The method of claim 18, wherein the clusters comprise a plurality of transmission channels.

21. The method of claim 18, wherein the gateway and all access nodes within each cluster, comprise a single transmission channel.

22. The method of claim 18, wherein the connecting access node selecting a transmission channel further includes at least one of a persistence of successfully received beacons, a persistence of successfully received reverse beacons, and a hop count included within re-broadcast beacons.

23. The method of claim 22, wherein the connecting access node estimates a projected cluster size by summing the size of each cluster with a number of nodes downstream from the connecting access node, and the connecting access node uses the projected cluster size in its routing selection.

24. The method of claim 14, wherein each gateway has a routing table that includes routes to all access nodes within the cluster of the gateway, thereby allowing the gateway to determine the size of its cluster.

25. A method of a connecting access node selecting a routing path, comprising:

the connecting access node evaluating a plurality of clusters of a wireless mesh network, wherein the connecting access node is not within the plurality of clusters;

the connecting access node selecting a routing path to a gateway of the wireless mesh network based on a combination of routing selection parameters, one of the parameters being a size of each of the clusters, wherein the size of each cluster is based on a number of access nodes within the cluster, and wherein the connecting access node estimates a projected cluster size by summing the size of each cluster with a number of nodes downstream from the connecting access node, and the connecting access node using the projected cluster size in its routing selection.

26. The method of claim 25, further comprising:

the access node receiving the size of each of the plurality of clusters from each of the plurality of clusters, wherein each cluster comprises a gateway.

27. The method of claim 25, further comprising the access nodes receiving routing beacons from each of the clusters, the routing beacons originating at gateways of each cluster, and including information indicating the size of the corresponding cluster.

28. The method of claim 25, further comprising the access node retrieving the size of each cluster from each cluster.

29. A method of a connecting access node selecting a transmission channel, comprising:

the connecting access node evaluating transmission channels of a plurality of clusters of a wireless mesh network, wherein the connecting access node is not within the plurality of clusters;

the connecting access node selecting a transmission channel based on a combination of selection parameters, one of the parameters being the size of the clusters, wherein the size of each cluster is based on a number of access nodes within the cluster, and wherein the connecting access node estimates a projected cluster size by summing the size of each cluster with a number of nodes downstream from the connecting access node, and the connecting access node additionally uses the projected cluster size in its transmission channel selection.

30. The method of claim 29, further comprising the access node receiving a cluster size from a plurality of wireless mesh network clusters, each cluster comprising a gateway.

31. The method of claim 29, further comprising the access node retrieving the size of each cluster from each cluster.

32. The method of claim 29, further comprising the access nodes receiving routing beacons from each of the clusters, the routing beacons originating at gateways of each cluster, and including information indicating the size of the corresponding cluster.