I found a very good way for Arduino with mobile or outdoor usage , a rechargeable Li-ion battery will give 3.5 to 4.2V DC out , to fit Arduino main board's request , we need add a DC2DC boost circuit then we can get 9V form the power box , in the meantime , we add battery protection / charging circuit , with fulling charged , the power box can be working over 6 to 8 hours , and then we can recharge it , this will save us a lot of batteries , also friendly for environment.
Why use 9V? You will have the losses of the DC/DC converter and also the losses of the on-board LDO.
If you can get it to fit another idea would be to make a Shield that sits in between and powers the 5V Rail directly from it's own DC/DC converter?