Balancing clusters of a wireless mesh network

• US 20080205360A1
• Filed: 02/27/2007
• Published: 08/28/2008
• Est. Priority Date: 02/27/2007
• Status: Active Grant

• Current Assignee: Hitachi Energy Limited
• Original Assignee: Tropos Networks Incorporated (ABB Limited)
• Inventors: Behroozi, Cyrus, Srikrishna, Devabhaktuni, Chari, Amalavoyal, Ren, Wenge
• Granted Patent: US 8,031,615 B2
• Time in Patent Office: Days
• US Class Current: 370/338
• 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 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;

the gateway including its cluster size within routing packets.

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 connecting access nodes determine whether to route through the gateway based at least in part on the cluster size of the gateways.

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

5. The method of claim 3, wherein connecting access nodes determine whether to route through the gateway additionally based on a number of devices that are downstream from the connecting access node.

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

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

8. The method of claim 5, wherein downstream mobile nodes do not count as downstream devices.

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

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

11. 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.

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

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

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

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

16. 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;

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.

17. The method of claim 16, 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.

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

19. The method of claim 17, 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.

20. The method of claim 17, 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.

21. The method of claim 16, 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.

22. The method of claim 21, wherein the connecting access nodes prefer selecting a transmission channel corresponding to a smaller cluster rather than a transmission channel of a larger cluster.

23. The method of claim 21, wherein the clusters comprise a plurality of transmission channels, and each cluster comprises a plurality of transmission channels.

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

25. The method of claim 21, 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.

26. The method of claim 25, 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.

27. The method of claim 16, 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.

28. A method of an access node selecting a routing path, comprising:

the access node evaluating a plurality of clusters of a wireless mesh network;

the 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.

29. The method of claim 28, 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.

30. The method of claim 28, 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.

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

32. A method of an access node selecting a transmission channel, comprising:

the access node evaluating transmission channels of a plurality of clusters of a wireless mesh network;

the access node selecting a transmission channel based on a combination of selection parameters, one of the parameters being the size of the clusters.

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

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

35. The method of claim 32, 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.