Hi guys,
All the options are previously mentioned - wireless repeater, improving antenna performance, centralising the access point, inline power, changing channels and running a cable upstairs. You can also try 5Ghz instead of 2.4Ghz which will give much better strength but at lower throughput - though your hardware might not support it.
The best bang for buck and time will be running the cable (which whilst is technically illegal, its very easy to do yourself and doesnt present a safety risk - if you dont want to spend the $$). Insulation, plaster, timber, ducting etc all attenuate the RF signal more than you think. If you want some more info on a self install, PM me.
On windows / android, get a freeware tool called "InSSIDer" and this will show you channel interference and power levels. I find channels 1, 6 and 11 are vendor defaults and I find 6 & 7 the best options for the 2 x access points I use.
Cheers
Steve