WMSCI 05: COMMUNICATION AND NETWORK SYSTEMS, TECHNOLOGIES AND APPLICATIONS 1Optimal Access Point Selection and TrafficAllocation in IEEE 802.11 NetworksRobert Akl and Sangtae ParkDepartment of Computer Science and EngineeringUniversity of North Texas, Denton, Texas, 76207.ABSTRACTWe design an optimal access point (AP) selection andtraffic allocation algorithm for IEEE 802.11 networks.Coverage and capacity are some key issues when selectingAPs in a demand area. APs need to cover all users, i.e.,a user is considered covered if the power received fromits corresponding AP is greater than a given threshold.Moreover, from a capacity standpoint, APs need to providecertain minimum bandwidth to users located in the coveragearea. Our optimization balances the load on the entirenetwork whereby demand clusters will not necessarilyselect the closest AP that has the largest signal level butone that can still service the demand cluster and provideample bandwidth.Keywords: WiFi, Access Point, Wireless Networks, Op-timization.1. INTRODUCTIONIEEE 802.11 wireless networks offer performance nearlycomparable to that of Ethernet [1]. In addition, they providescalability and relative ease of integrating wireless access.Wireless LANs support user demand for seamless connec-tivity, flexibility, and mobility [2]. The most prominentdifferences between wireless LANs and wired LANs aretransmission medium and speed.Designing IEEE 802.11 wireless networks [3] includestwo major components: placement of access points (APs)in the demand areas and assignment of radio frequenciesto each AP. Coverage and capacity are some key issueswhen placing APs in a demand area. APs need to cover allusers. A user is considered covered if the power receivedfrom its corresponding AP is greater than a given threshold.Moreover, from a capacity standpoint, APs need to providecertain minimum bandwidth to users located in the coveragearea.In [4], the authors use a divide-and-conquer algorithmto select APs. The algorithm divides the total service areainto equally sized squares. The problem is then solved ineach of these divisions by exhaustive search. In [5], theauthors formulate an integer linear programming problemfor optimizing AP placement. The algorithm maximizesthe throughput by considering load balancing among APs.The optimization objective is to minimize the maximumof channel utilization of the hot spot service area. In [6],the authors formulate different optimization problems withvarious objective functions. The considered variables arepositions of APs, their heights, their transmission powerlevels, and antenna sectorization. The optimization prob-lems maximize the number of covered demand nodes whilepenalizing multiple coverage of demand nodes. In [7], theauthors use techniques for placement of base stations inan outdoor environment for building an indoor wirelessnetwork. The algorithm minimizes the number of APs,that cover a desired service area. In [8], the authors use agreedy algorithm to solve the AP placement problem. Thealgorithm begins with a set of potential locations for APs.In each iteration, a new AP is greedily picked from theset that covers the maximum number of uncovered demandnodes. This algorithm assumes that if an AP covers themost demand nodes, it is more desirable to select it.In this paper, we design our AP selection algorithmby balancing traffic load. We formulate an optimizationproblem that minimizes heavy congestion. As a result, APsin wireless LANs will have well distributed traffic loads,which maximizes the throughput of the network.The remainder of this paper is organized as follows. Insection 2, we describe our network design procedure. Insection 3, we present our AP selection and traffic allocationoptimization algorithm. In section 4, numerical results arepresented. Finally, the conclusions drawn from this paperare summarized in section 5.2. NETWORK DESIGN PROCEDUREAPs should be placed so that there are no coveragegaps in the service areas. In addition, the coverage overlapamong APs should be minimized to avoid interferenceand achieve better throughput. If too many APs are used,the cost of equipment and installation will be higher thannecessary.Some important issues when placing APs are coverage ofservice areas and throughput requirements. Our approachfor designing 802.11 wireless LANs is composed of thefollowing steps:1. Creation of a service area map: A service area mapwill be divided into smaller demand clusters wherethe number of users or traffic requirements of eachdemand cluster is given.2. Placement of candidate APs: Candidate APs must beplaced taking into account the connection to the wiredLANs, power supply needs, and installation costs.WMSCI 05: COMMUNICATION AND NETWORK SYSTEMS, TECHNOLOGIES AND APPLICATIONS 23. Creation of a signal level map: A signal level map iseither measured or estimated using a radio propagationmodel. Signal levels at demand clusters should begreater than a given threshold in order to provide anadequate signal-to-noise ratio.4. Selection of the APs from among a set of candidate lo-cations: Using the service area map and the signal levelmap, we can calculate the best locations of APs fromamong possible candidate locations to satisfy trafficdemands and capacity requests. Balancing traffic loadswill be crucial to avoid and minimize bottleneck APs,which increases network throughput.3. OPTIMAL ACCESS POINT SELECTION ANDTRAFFIC ALLOCATIONAssumptionsThe following assumptions are made to aid in the place-ment problem.• L is the total number of demand clusters. Demandclusters are defined as the locations of high trafficloads in the service area.• M is the total number of candidate APs. The APsare chosen such that every demand cluster must beconnected to at least one candidate AP.• Sijis the signal level at demand cluster i of AP j.• Diis the location of a demand cluster i.• Tiis the average traffic load of demand cluster i.Traffic requests from a demand cluster i will beassigned to only one AP.• Candidate AP assignment graph, G = (N, E):– Nodes (N ) consist of a set of demand cluster anda set of candidate APs.– Edge (E) exists between a demand cluster i, Di,and a candidate AP j if the signal level, Sij, isgreater than a given threshold.The Access Point Selection Optimization ProblemLoad balancing is crucial when APs are chosen becausedistributing user traffic demands to APs results in higherthroughput. We formulate the problem of AP selection andtraffic