The problem of locating the minimum number of Base Stations (BSs) to provide sufficient signal coverage and data rate capacity is often formulated in manner that results in a mixed-integer NP-Hard (Non-deterministic Polynomial-time Hard) problem. Solving a large size NP-Hard problem is time-prohibitive because the search space always increases exponentially, in this case as a function of the number of BSs. This research presents a method to generate a set of Test Points (TPs) for BS locations, which always includes optimal solution(s). A sweep and merge algorithm then reduces the number of TPs, while maintaining the optimal solution. The coverage solution is computed by applying the minimum branching algorithm, which is similar to the branch and bound search. Data Rate demand is assigned to BSs in such a way to maximize the total network capacity. An algorithm based on Tabu Search to place additional BSs is developed to place additional BSs, in cases when the coverage
solution can not meet the capacity requirement. Results show that the design algorithm efficiently searches the space and converges to the optimal solution in a computationally efficient manner. Using the demand nodes to represent traffic, network design with the TP reduction algorithm supports both voice and data users.
| Identifer | oai:union.ndltd.org:PITT/oai:PITTETD:etd-11162007-163544 |
| Date | 31 January 2008 |
| Creators | Pongthaipat, Natthapol |
| Contributors | Dr. Joseph Kabara, Dr. Marwan Simaan, Dr. Prashant Krishnamurthy, Dr. Richard Thompson, Dr. Michael McCloud |
| Publisher | University of Pittsburgh |
| Source Sets | University of Pittsburgh |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | http://etd.library.pitt.edu/ETD/available/etd-11162007-163544/ |
| Rights | unrestricted, I hereby certify that, if appropriate, I have obtained and attached hereto a written permission statement from the owner(s) of each third party copyrighted matter to be included in my thesis, dissertation, or project report, allowing distribution as specified below. I certify that the version I submitted is the same as that approved by my advisory committee. I hereby grant to University of Pittsburgh or its agents the non-exclusive license to archive and make accessible, under the conditions specified below, my thesis, dissertation, or project report in whole or in part in all forms of media, now or hereafter known. I retain all other ownership rights to the copyright of the thesis, dissertation or project report. I also retain the right to use in future works (such as articles or books) all or part of this thesis, dissertation, or project report. |
Page generated in 0.0022 seconds