Patent ID: 8582490

Claim:
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.