In　conventional　WLANs,　stations　(STAs)　select　access　points　(APs)　using　the　existing　scheme　based　on　the　current　quality　of　links.　However,　some　novel　improved　architecture　of　WLANs　is　proposed　with　cognitive　radio　(CR)　to　negotiate　spectrum　usage,　where　the　existing　AP　selection　scheme　might　not　be　suitable　for　it.　Thus　in　this　paper,　a　new　optimal　AP　Selection　based　on　Restless　Bandits　(APSRB)　scheme　with　the　＇＇indexability＇＇　property　is　proposed　for　WLANs　with　CR　to　maximize　the　throughput　and　to　minimize　the　energy　consumption.　The　AP　selection　problem　is　firstly　established　as　a　restless　bandit　problem,　which　is　solved　by　the　primal-dual　index　heuristic　algorithm　based　on　the　first　order　relaxation　with　low　complexity　to　yield　APSRB　scheme.　Additionally,　the　APSRB　scheme　is　divided　into　offline　computation　and　online　selection,　where　main　work　will　be　finished　in　former　one　so　as　to　decrease　the　complexity　further.　Finally,　extensive　simulation　results　illustrate　the　significant　performance　improvement　of　the　APSRB　scheme　compared　to　the　existing　one　in　different　scenarios.　©　2011　IEEE.