Communication network topology determination

• US 7,929,460 B2
• Filed: 09/14/2007
• Issued: 04/19/2011
• Est. Priority Date: 09/14/2006
• Status: Active Grant

• Current Assignee: VANU Incorporated
• Original Assignee: VANU Incorporated
• Inventors: Martin, Nick, Srinivas, Anand, Chen, Li-Wei, Cabrera, Carlos
• Primary Examiner(s): LY, ANH VU H
• Application Number:
  US11/855,968
• Publication Number:
  US 20090109868A1
• Time in Patent Office: 1,313 Days
• Field of Search: None
• US Class Current: 370/255
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/34 Signalling channels for network management communication
• CPC Class Codes: H04W 16/12 Fixed resource partitioning

Abstract

A communication network topology is determined by evaluating costs of states each representing a possible assignment of hubs and remote nodes to nodes of the communication network. The hubs connect to a central network, the remote nodes connect wirelessly to the hubs and obtain connectivity to the central network through the hubs. The cost of each state is determined based on costs for configuring each node as a hub or a remote node, uplink frequencies for sending data from the remote nodes to corresponding hubs, and downlink frequencies for sending data from the hubs to corresponding remote nodes.

Claims

1. A computer implemented method comprising:

determining, using at least one data processor, a topology of a communication network by evaluating costs of states each representing a possible assignment of hubs and remote nodes to nodes of the communication network, the hubs connecting to a central network, the remote nodes connecting wirelessly to the hubs and obtaining connectivity to the central network through the hubs; and

using an iterative process to evaluate the states, and at each iteration evaluate states each representing a network topology having more hubs than those represented by states evaluated at a previous iteration;

wherein the cost of each state is determined based on costs for configuring each node as a hub or a remote node, uplink frequencies for sending data from the remote nodes to corresponding hubs, and downlink frequencies for sending data from the hubs to corresponding remote nodes, and

wherein when the costs of each state evaluated at an iteration are higher than the lowest cost of states evaluated at a previous iteration, the assignment of hubs and remote nodes represented by the state having the lowest cost in the previous iteration is selected as the final topology for the communication network.

2. The method of claim 1 wherein the communication network comprises a cellular telephone network.

3. The method of claim 1 wherein the hubs and the remote nodes comprise base stations for communicating with end users, the central network comprises a switched network, and the links between the remote nodes and the hubs provide in-band backhaul.

4. The method of claim 1 wherein each node can either be a hub or a remote node, and evaluating the costs of states comprises evaluating the costs of a subset of states selected from 2^N states, N representing the number of nodes in the communication network.

5. The method of claim 1, further comprising determining uplink relationships between remote nodes and hubs indicating which remote nodes send data upstream to which hubs.

6. The method of claim 5 wherein determining the uplink relationships comprises assigning each remote node to a closest hub and assigning uplink frequencies such that signal-to-interference-plus-noise ratios for each uplink is above a preset threshold.

7. The method of claim 6 wherein assigning each remote node to a closest hub comprises assigning each remote node to a hub that is closest geographically or a hub that results in a minimum propagation loss.

8. The method of claim 1, further comprising determining downlink relationships between hubs and remote nodes indicating which hubs send data downstream to which remote nodes.

9. The method of claim 8 wherein determining the downlink relationships comprises selecting among a plurality of possible configurations to maximize the number of remote nodes that share frequencies while maintaining the signal-to-interference-plus-noise ratios for each downlink above a preset threshold.

10. The method of claim 1, further comprising using a greedy heuristic algorithm to determine a subset of states to evaluate.

11. A computer implemented method comprising:

determining, using at least one data processor, a topology of a communication network by evaluating costs of states each representing a possible assignment of hubs and remote nodes to nodes of the communication network, the hubs connecting to a central network, the remote nodes connecting wirelessly to the hubs and obtaining connectivity to the central network through the hubs;

using an iterative process to evaluate the states, and at each iteration evaluate states each representing a network topology having more hubs than those represented by states evaluated at a previous iteration; and

at each iteration evaluating a first subset of states and selecting one of the first subset of states having a lowest cost, and at the next iteration evaluating a second subset of states each derived by taking the lowest-cost state in the first subset and changing one or more of the remote nodes to hubs;

wherein the cost of each state is determined based on costs for configuring each node as a hub or a remote node, uplink frequencies for sending data from the remote nodes to corresponding hubs, and downlink frequencies for sending data from the hubs to corresponding remote nodes.

15. The method of claim 11 wherein the communication network comprises a cellular telephone network.

16. The method of claim 11 wherein the hubs and the remote nodes comprise base stations for communicating with end users, the central network comprises a switched network, and the links between the remote nodes and the hubs provide in-band backhaul.

17. The method of claim 11 wherein each node can either be a hub or a remote node, and evaluating the costs of states comprises evaluating the costs of a subset of states selected from 2^N states, N representing the number of nodes in the communication network.

18. The method of claim 11, further comprising determining uplink relationships between remote nodes and hubs indicating which remote nodes send data upstream to which hubs.

19. The method of claim 18 wherein determining the uplink relationships comprises assigning each remote node to a closest hub and assigning uplink frequencies such that signal-to-interference-plus-noise ratios for each uplink is above a preset threshold.

20. The method of claim 19 wherein assigning each remote node to a closest hub comprises assigning each remote node to a hub that is closest geographically or a hub that results in a minimum propagation loss.

21. The method of claim 11, further comprising determining downlink relationships between hubs and remote nodes indicating which hubs send data downstream to which remote nodes.

22. The method of claim 21 wherein determining the downlink relationships comprises selecting among a plurality of possible configurations to maximize the number of remote nodes that share frequencies while maintaining the signal-to-interference-plus-noise ratios for each downlink above a preset threshold.

23. The method of claim 11, further comprising using a greedy heuristic algorithm to determine a subset of states to evaluate.

12. A computer implemented method comprising:

determining, using at least one data processor, a topology of a communication network by evaluating costs of states each representing a possible assignment of hubs and remote nodes to nodes of the communication network, the hubs connecting to a central network, the remote nodes connecting wirelessly to the hubs and obtaining connectivity to the central network through the hubs;

using an iterative process to evaluate the states, and at each iteration evaluate states each representing a network topology having less hubs than those represented by states evaluated at a previous iteration; and

at each iteration evaluating a first subset of states and selecting one of the first subset of states having a lowest cost, and at the next iteration evaluating a second subset of states each derived by taking the lowest-cost state in the first subset and changing one or more of the hubs to remote nodes;

wherein the cost of each state is determined based on costs for configuring each node as a hub or a remote node, uplink frequencies for sending data from the remote nodes to corresponding hubs, and downlink frequencies for sending data from the hubs to corresponding remote nodes.

24. The method of claim 12 wherein the communication network comprises a cellular telephone network.

25. The method of claim 12 wherein the hubs and the remote nodes comprise base stations for communicating with end users, the central network comprises a switched network, and the links between the remote nodes and the hubs provide in-band backhaul.

26. The method of claim 12 wherein each node can either be a hub or a remote node, and evaluating the costs of states comprises evaluating the costs of a subset of states selected from 2^N states, N representing the number of nodes in the communication network.

27. The method of claim 12, further comprising determining uplink relationships between remote nodes and hubs indicating which remote nodes send data upstream to which hubs.

28. The method of claim 27 wherein determining the uplink relationships comprises assigning each remote node to a closest hub and assigning uplink frequencies such that signal-to-interference-plus-noise ratios for each uplink is above a preset threshold.

29. The method of claim 28 wherein assigning each remote node to a closest hub comprises assigning each remote node to a hub that is closest geographically or a hub that results in a minimum propagation loss.

30. The method of claim 12, further comprising determining downlink relationships between hubs and remote nodes indicating which hubs send data downstream to which remote nodes.

31. The method of claim 30 wherein determining the downlink relationships comprises selecting among a plurality of possible configurations to maximize the number of remote nodes that share frequencies while maintaining the signal-to-interference-plus-noise ratios for each downlink above a preset threshold.

32. The method of claim 12, further comprising using a greedy heuristic algorithm to determine a subset of states to evaluate.

13. A computer implemented method comprising:

determining, using at least one data processor, a topology of a communication network by evaluating costs of states each representing a possible assignment of hubs and remote nodes to nodes of the communication network, the hubs connecting to a central network, the remote nodes connecting wirelessly to the hubs and obtaining connectivity to the central network through the hubs; and

using a simulated annealing process to determine a sequence of states to evaluate, including at each step of the process, evaluating one or more neighbor states of a current state and probabilistically determining whether to maintain the current state or evaluate one of the neighbor states, in order to progress generally towards states of lower costs;

wherein the cost of each state is determined based on costs for configuring each node as a hub or a remote node, uplink frequencies for sending data from the remote nodes to corresponding hubs, and downlink frequencies for sending data from the hubs to corresponding remote nodes.

14. The method of claim 13 wherein neighboring states are defined such that two neighboring states differ from each other by one node in which the node is a hub in one of the two neighboring states and a remote node in the other of the two neighboring states.

33. The method of claim 13 wherein the communication network comprises a cellular telephone network.

34. The method of claim 13 wherein the hubs and the remote nodes comprise base stations for communicating with end users, the central network comprises a switched network, and the links between the remote nodes and the hubs provide in-band backhaul.

35. The method of claim 13 wherein each node can either be a hub or a remote node, and evaluating the costs of states comprises evaluating the costs of a subset of states selected from 2^N states, N representing the number of nodes in the communication network.

36. The method of claim 13, further comprising determining uplink relationships between remote nodes and hubs indicating which remote nodes send data upstream to which hubs.

37. The method of claim 36 wherein determining the uplink relationship relationships comprises assigning each remote node to a closest hub and assigning uplink frequencies such that signal-to-interference-plus-noise ratios for each uplink is above a preset threshold.

38. The method of claim 37 wherein assigning each remote node to a closest hub comprises assigning each remote node to a hub that is closest geographically or a hub that results in a minimum propagation loss.

39. The method of claim 13, further comprising determining downlink relationships between hubs and remote nodes indicating which hubs send data downstream to which remote nodes.

40. The method of claim 39 wherein determining the downlink relationships comprises selecting among a plurality of possible configurations to maximize the number of remote nodes that share frequencies while maintaining the signal-to-interference-plus-noise ratios for each downlink above a preset threshold.

41. The method of claim 13, further comprising using a greedy heuristic algorithm to determine a subset of states to evaluate.