Gateway selection method for wireless mesh network

• US 8,036,144 B2
• Filed: 01/09/2009
• Issued: 10/11/2011
• Est. Priority Date: 01/09/2008
• Status: Expired due to Fees

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Kim, Hyun Jin
• Primary Examiner(s): Sheikh; Ayaz
• Assistant Examiner(s): CHAU, PETER P
• Application Number:
  US12/351,081
• Publication Number:
  US 20090175204A1
• Time in Patent Office: 1,005 Days
• Field of Search: None
• US Class Current: 370/256
• CPC Class Codes: H04L 45/18 Loop-free operations
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04W 40/246 Connectivity information discovery

Abstract

A gateway selection method for a wireless mesh network is provided for selecting an optimal gateway includes building a spanning routing tree to a given network. Reference factors of routers are calculated regarding the network to total network capacity in association with the spanning routing tree. A router is selected which has the greatest reference factor as being an optimal gateway of the network.

Claims

1. A gateway selection method, for a wireless mesh network, said gateway selection method comprising:

(a) building, by a computer, a spanning routing tree to a mesh network;

(b) calculating, by the computer, reference factors which indicate an efficiency of a routing path of a select number of a plurality of routers within the mesh network to a total network capacity in association with the spanning routing tree, the reference factors being determined as follows;

2. The gateway selection method of claim 1, wherein the reference factors in step (b) are calculated on a basis of link capacities of all links between routers on a routing path and a hop count from a source router to a destination router.

3. The gateway selection method of claim 2, wherein calculating the reference factors in step (b) comprises:

calculating sub-reference factors of all routers in the mesh network to an arbitrary router; and

summing the sub-reference factors.

4. The gateway selection method of claim 3, wherein the reference factors are obtained to all network instances defined with a plurality of respective candidate gateways, the respective candidate gateways being the routers.

5. The gateway selection method of claim 2, wherein selecting an optimal gateway comprises:

comparing reference factors calculated on a basis of the link capacities and hop counts of all routing paths from the source router to the destination router.

6. The gateway selection method of claim 5, wherein selecting an optimal gateway comprises:

comparing reference factors calculated on the basis of path capacities and hop counts of all the routing paths from the source router to the destination router.

7. The gateway selection method of claim 1, wherein the spanning routing tree is built using a Dijkstra algorithm.

8. The gateway selection method according to claim 1, wherein a reference factor to the total network capacity of a network N(g) is calculated as follows:

9. A gateway selection method, for a wireless mesh network, said gateway selection method comprising:

(a) building, by a computer, a routing tree to an arbitrary router as a candidate gateway in the wireless mesh network;

(b) calculating, by the computer, sub-reference factors of routing paths from the arbitrary router to all other routers in the wireless mesh network, the sub-reference factors being determined as;

10. The gateway selection method of claim 9, wherein the sub-reference factors are calculated on the basis of link capacities of routing paths and hop counts from the arbitrary router to all other routers in the wireless mesh network.

11. The gateway selection method of claim 9, wherein calculating reference factors comprises:

(i) calculating sub-reference factors of all other routers in the wireless mesh network to the arbitrary router; and

(ii) obtaining a reference factor by summing the sub-reference factors of all other routers in the wireless mesh network to the arbitrary router.

12. The gateway selection method of claim 9, wherein the routing tree is built using a Dijkstra algorithm.

13. The gateway selection method of claim 9, further comprising:

determining whether the reference factors of all of the routers in the wireless mesh network have been obtained;

calculating, if the reference factors of all of the routers in the wireless mesh network have not been obtained, a reference factor of a router not having a corresponding reference factor calculated; and

comparing, if the reference factors of all the routers have been obtained, the reference factors with each other to determine a router having a highest reference factor.

14. The gateway selection method according to claim 9, wherein a reference factor to the total network capacity of a network N(g) is calculated as follows: