Communication Network Topology Determination

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.

1 . A computer implemented method comprising:
 determining, using at least one computer, 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   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.   
     
     
         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 . The method of  claim 1 , further comprising 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. 
     
     
         12 . The method of  claim 11  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. 
     
     
         13 . The method of  claim 11 , further comprising 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. 
     
     
         14 . The method of  claim 1 , further comprising 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. 
     
     
         15 . The method of  claim 14 , further comprising 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. 
     
     
         16 . The method of  claim 1 , further comprising 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. 
     
     
         17 . The method of  claim 16  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. 
     
     
         18 . A computer implemented method comprising:
 determining, using at least one computer, a topology of a communication network by using linear programming to find a minimum of a cost function subject to a set of constraints,   the cost function including variables representing whether a node of the communication network is a hub or a remote node, variables indicating whether a set of uplink frequencies are used, and variables indicating whether a set of downlink frequencies are used,   the constraints taking into account signal-to-interference-plus-noise ratio requirements for the uplinks and downlinks.   
     
     
         19 . The method of  claim 18  wherein the linear programming comprises integer linear programming and one or more of the variables comprise integers. 
     
     
         20 . A computer implemented method comprising:
 determining, using at least one computer, a topology of a communication network using an iterative process, each step of the iterative process comprising
 determining which nodes of the communication network are hub nodes and which nodes are remote nodes, the hub nodes connecting to a central network, the remote nodes connecting wirelessly to the hub nodes and obtaining connectivity to the central network through the hubs, 
 assigning the remote nodes to the hub nodes for establishing uplink channels between the remote nodes and corresponding hub nodes, 
 assigning frequencies for the uplink channels, 
 assigning the remote nodes to the hub nodes for establishing downlink channels between hub nodes and corresponding remote nodes, 
 assigning frequencies for the downlink channels, and 
 evaluating a cost of network configuration based on assignments of the hub nodes, uplink frequencies, and downlink frequencies. 
   
     
     
         21 . The method of  claim 20  wherein assigning the remote nodes to the hub nodes for establishing uplink channels and assigning the uplink frequencies comprise assigning each remote node to a closest hub node and assigning uplink frequencies such that signal-to-noise ratios for each uplink is above a preset threshold. 
     
     
         22 . The method of  claim 20  wherein assigning the remote nodes to the hub nodes for establishing downlink channels and assigning the downlink frequencies comprise assigning each remote node to a closest hub node and assigning downlink frequencies such that signal-to-noise ratios for each downlink is above a preset threshold. 
     
     
         23 . The method of  claim 20  wherein assigning the remote nodes to the hub nodes for establishing downlink channels and assigning downlink frequencies comprise selecting among a plurality of possible configurations to maximize reuse of frequencies while maintaining the signal to noise ratios for each downlink above a preset threshold. 
     
     
         24 . A system comprising:
 a state machine to determine 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 to the hubs, and   a cost determination engine to determine a cost of each state 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.   
     
     
         25 . An article comprising computer-readable medium encoded with computer executable instructions that when executed by one or more computers causes the one or more computers to perform operations comprising:
 determining 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 hub nodes and obtaining connectivity to the central network through the hubs;   wherein the cost of each state determined based on costs for configuring each node as a hub node or a remote node, uplink frequencies for sending data from the remote nodes to corresponding hub nodes, and downlink frequencies for sending data from the hub nodes to corresponding remote nodes.