Method for determining placement of internet taps in wireless neighborhood networks

• US 8,582,490 B2
• Filed: 11/01/2012
• Issued: 11/12/2013
• Est. Priority Date: 02/17/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Qiu, Lili, Jain, Kamal, Chandra, Ranveer, Mahdian, Mohammad
• Primary Examiner(s): Wu, Jianye
• Application Number:
  US13/666,229
• Publication Number:
  US 20130100818A1
• Time in Patent Office: 376 Days
• Field of Search: None
• US Class Current: 370/312
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04W 16/18 Network planning tools
• CPC Class Codes: H04W 74/08 Non-scheduled access, e.g. ALOHA hybrid access H04W74/02
• CPC Class Codes: H04W 80/00 Wireless network protocols or protocol adaptations to wireless operation
• CPC Class Codes: H04W 88/16 Gateway arrangements
• CPC Class Codes: H04W 92/02 Inter-networking arrangements

Abstract

Disclosed is a method for determining the placement of ITAPs in wireless neighborhood networks. The method disclosed provides for efficient integration of multi-hop wireless networks with the Internet by placing ITAPs at strategic locations. Initially the method provides for the formulation of the ITAP placement problem under three wireless models. For each model, methods are developed to efficiently place ITAPs in the networks. The methods aim to minimize the number of required ITAPs while guaranteeing users'"'"' bandwidth requirements. Next, a fault tolerance version of the placement method is presented that provides bandwidth guarantees in the presence of failures. Finally the methods are extended to take into account variable traffic demands by developing an approximation algorithm to simultaneously optimize ITAP placement based on demands over multiple periods.

Claims

1. A method for determining placement locations of access points in a network, the method comprising:

(a) accepting connectivity information for the network, the network being a multi-hop wireless mesh network employing a contention-based media access control (MAC) protocol and comprising nodes and links between the nodes, the connectivity information comprising link capacity constraints, node capacity constraints, node demands for flow, and a set of prospective access point locations;

(b) employing a processor executing computer-executable instructions to perform acts of;

(i) iterating through each prospective access point location, in each iteration;

(I) selecting a test access point, from the set of prospective access point locations, to be added to a set of currently open access points; and

(II) computing node demands satisfied if the test access point is added to the set of currently open access points;

(ii) selecting, as a new access point for the network, the test access point from the set of prospective access point locations having a maximum computed value of the node demands satisfied when opened together with access points in the set of currently open access points;

(iii) adding the selected new access point to the set of currently opened access points; and

(iv) repeating the iterating, selecting, and adding until all the node demands are satisfied; and

(c) implementing each access point in the set of currently opened access points in the network at its respective placement location.

2. The method of claim 1 wherein the computing the node demands satisfied if the test access point is added to the set of currently open access points comprises:

formulating a max-flow problem, wherein the max-flow problem computes the amount of node demands that can be satisfied under a given set of opened access points when network throughput is independent of network path length;

creating a subgraph induced on a set of nodes, a set of currently opened access points, and the test access point;

transforming each node'"'"'s capacity constraint to an edge capacity constraint by replacing each node with a first node and a second node, the first node accepting all incoming edges to the transformed node and all outgoing edges from the transformed node originating from the second node, and creating a directed edge, having the node'"'"'s capacity, from the first node to the second node;

adding a source node, the source node having edges of capacity equal to the demand of the transformed node from the source to each node in the network;

adding a destination node, the destination node having edges of capacity equal to the capacity of each currently opened access point and the potential access point to be opened, from each currently opened access point and the potential access point to be opened to the destination node; and

computing the maximum flow from the source node to the destination node.

3. The method of claim 1 wherein computing the node demands satisfied if the test access point is added to the set of currently open access points comprises:

developing a linear program to compute maximum demands satisfied in the wireless neighborhood network by opening the test access point in conjunction with the set of currently opened access points, wherein the linear program treats throughput of a connection as independent of path length;

modifying the linear program to ensure that flow from each node is served by independent paths;

modifying the linear program to multiply the node demand by the number of independent paths;

modifying the linear program to multiply the capacity constraints by a ratio of an over-provisioning factor to the number of independent paths; and

solving the resulting linear program.

4. The method of claim 1 wherein computing the node demands satisfied if the test access point is added to the set of currently open access points comprises:

finding a shortest path from demand points to opened access points;

routing one unit of flow along the shortest path;

decreasing capacities of edges on the path by one; and

repeating the finding, routing, and decreasing until the shortest path found has a length greater than a hop-count bound.

5. The method of claim 1 wherein computing the node demands satisfied if the test access point is added to the set of currently open access points comprises:

finding a shortest path from demand points to opened access points;

routing one unit of flow along the shortest path;

decreasing capacities of edges on the path by one;

repeating the finding, routing, and decreasing until no path between any demand point and any open access point remains; and

computing a demand satisfied along each path according to a throughput function.

6. The method of claim 1 wherein computing the node demands satisfied if the test access point is added to the set of currently open access points comprises:

developing a linear program to compute maximum demands satisfied in the wireless neighborhood network by opening the test access point in conjunction with the set of currently opened access points, wherein the linear program treats throughput of a connection as a function of a number of hops the connection traverses;

denoting an amount of flow routed through an edge based on a position of the edge along a path;

modifying the linear program to limit the maximum flow from each node; and

solving the resulting linear program.

7. The method of claim 1 wherein computing the node demands satisfied if the test access point is added to the set of currently open access points comprises:

developing a linear program to compute maximum demands satisfied in the wireless neighborhood network by opening the selected access point in conjunction with the set of currently opened access points, wherein the linear program treats throughput of a connection as a function of a number of hops the connection traverses;

modifying the linear program to ensure that flow from each node is served by independent paths;

modifying the linear program to multiply the node demand by the number of independent paths;

modifying the linear program to multiply the capacity constraints by a ratio of an over-provisioning factor to the number of independent paths; and

solving the resulting linear program.

8. A computer-implemented process for determining placement locations of access points in a network, comprising:

using a computer to perform the following process actions;

accepting connectivity information for the network, the network being a multi-hop wireless mesh network employing a contention-based media access control (MAC) protocol and comprising nodes and links between the nodes, the connectivity information comprising link capacity constraints, node capacity constraints, node demands for flow, and a set of prospective access point locations;

selecting an access point, from the set of prospective access point locations, to be added to a set of currently open access points;

computing node demands satisfied if the selected access point is added to the set of currently open access points;

when the computing indicates the selected access point increases the node demands satisfied when opened together with access points in the set of currently open access points, adding the selected access point to the set of currently opened access points; and

repeating the selecting, computing, and adding until all the node demands are satisfied.

9. The computer-implemented process of claim 8 wherein computing the node demands satisfied if the selected access point is added to the set of currently open access points comprises:

formulating a max-flow problem, wherein the max-flow problem computes the amount of node demands that can be satisfied under a given set of opened access points when network throughput is independent of network path length;

creating a subgraph induced on a set of nodes, a set of currently opened access points, and a potential access point to be opened;

transforming each node'"'"'s capacity constraint to an edge capacity constraint by replacing each node with a first node and a second node, the first node accepting all incoming edges to the transformed node and all outgoing edges from the transformed node originating from the second node, and creating a directed edge, having the node'"'"'s capacity, from the first node to the second node;

adding a source node, the source node having edges of capacity equal to the demand of the transformed node from the source to each node in the network;

adding a destination node, the destination node having edges of capacity equal to the capacity of each currently opened access point and the potential access point to be opened, from each currently opened access point and the potential access point to be opened to the destination node; and

computing the maximum flow from the source node to the destination node.

10. The computer-implemented process of claim 8 wherein computing the node demands satisfied if the selected access point is added to the set of currently open access points comprises:

developing a linear program to compute maximum demands satisfied in the wireless neighborhood network by opening the selected access point in conjunction with the set of currently opened access points, wherein the linear program treats throughput of a connection as independent of path length;

modifying the linear program to ensure that flow from each node is served by independent paths;

modifying the linear program to multiply the node demand by the number of independent paths;

modifying the linear program to multiply the capacity constraints by a ratio of an over-provisioning factor to the number of independent paths; and

solving the resulting linear program.

11. The computer-implemented process of claim 8 wherein computing the node demands satisfied if the selected access point is added to the set of currently open access points comprises:

finding a shortest path from demand points to opened access points;

routing one unit of flow along the shortest path;

decreasing capacities of edges on the path by one; and

repeating the finding, routing, and decreasing until the shortest path found has a length greater than a hop-count bound.

12. The computer-implemented process of claim 8 wherein computing the node demands satisfied if the selected access point is added to the set of currently open access points comprises:

finding a shortest path from demand points to opened access points;

routing one unit of flow along the shortest path;

decreasing capacities of edges on the path by one;

repeating the finding, routing, and decreasing until no path between any demand point and any open access point remains; and

computing a demand satisfied along each path according to a throughput function.

13. The computer-implemented process of claim 8 wherein computing the node demands satisfied if the selected access point is added to the set of currently open access points comprises:

developing a linear program to compute maximum demands satisfied in the wireless neighborhood network by opening the selected access point in conjunction with the set of currently opened access points, wherein the linear program treats throughput of a connection as a function of a number of hops the connection traverses;

modifying the linear program to limit the maximum flow from each node; and

solving the resulting linear program.

14. The computer-implemented process of claim 8 wherein computing the node demands satisfied if the selected access point is added to the set of currently open access points comprises:

developing a linear program to compute maximum demands satisfied in the wireless neighborhood network by opening the selected access point in conjunction with the set of currently opened access points, wherein the linear program treats throughput of a connection as a function of a number of hops the connection traverses;

modifying the linear program to ensure that flow from each node is served by independent paths;

modifying the linear program to multiply the node demand by the number of independent paths;

modifying the linear program to multiply the capacity constraints by a ratio of an over-provisioning factor to the number of independent paths; and

solving the resulting linear program.

15. A method for determining placement locations of access points in a network, the method comprising:

(a) accepting connectivity information for the network, the network being a multi-hop wireless mesh network employing a contention-based media access control (MAC) protocol and comprising nodes and links between the nodes, the connectivity information comprising link capacity constraints, node capacity constraints, node demands for flow, a set of potential access points to be opened, and a set of time intervals, each access point in the set of potential access points having a potential placement location;

(b) employing a processor executing computer-executable instructions to perform acts of;

(i) iterating through the set of potential access points to be opened;

(ii) iterating through the set of time intervals;

(iii) for each time interval, computing a total of node demands satisfied by adding an access point from the set of potential access points to be opened, to a set of currently open access points;

(iv) selecting the access point that results in the largest increase in the sum of satisfied node demands over all time intervals;

(v) adding the selected access point to the set of currently opened access points; and

(vi) repeating the iterating, selecting, and adding until the node demands at all time intervals are satisfied; and

(c) implementing each access point in the set of currently opened access points in the network at its respective placement location, wherein the set of currently opened access points provide Internet connectivity to the nodes.