|
Title:
|
STUDIES ON THE COMPUTATIONAL SCALE OF A DISTRIBUTED RCA ALGORITHM FOR WLANS |
|
Author(s):
|
Xiaoguang Ma , Ming Yu , Bing W. Kwan |
|
ISBN:
|
978-972-8924-62-1 |
|
Editors:
|
Jörg Roth and Jairo Gutiérrez |
|
Year:
|
2008 |
|
Edition:
|
Single |
|
Keywords:
|
Radio Channel Allocation (RCA), Distributed Heuristic Algorithm (DHA), Computational Scale |
|
Type:
|
Full Paper |
|
First Page:
|
41 |
|
Last Page:
|
48 |
|
Language:
|
English |
|
Cover:
|
|
|
Full Contents:
|
click to dowload 
|
|
Paper Abstract:
|
For the Radio Channel Allocation (RCA) of WLANs, how to efficiently allocate the limited number of channels to
achieve high throughput is a challenging problem. The major difficulty in solving the RCA problem is to maximize the
throughput of the entire network using the min-max optimization scheme. Usually, it is solved by using various heuristic
methods. However, it is not clear whether the min-max optimization problem is an NP-hard problem or not. In this paper,
we propose to analyze a typical RCA method, namely, the distributed heuristic algorithm (DHA) [2], by using both
analytical and statistical analysis in terms of the computational scale of the method. The computation scale of an
algorithm is defined as the number of channel reallocation times until the network reaches a convergence state. By
extensive simulations, we demonstrate that DHA reaches the convergence state very quickly. The total number of channel
reallocations is a log-logistic distribution. After finding out all of the different network configurations, for each of the
configurations, we develop a method to estimate the computational scale. We find that the overall upper limit of the
computational scale, i.e., O(I). |
|
|
|
|
|
|
