Unless there is a weight penalty, I'd run it off a 9V AA pack (6 cells -> 9V alkaline = 7.5V NiMH). The cells in a Snap-Top 9V are pretty tiny and low capacity at 625 mAh. Some experimentation and duration numbers available on this website. The best times were running the Arduino with a NiMH pack using 2500mAh cells. He also ran tests on XBee standalone power.
http://www.faludi.com/projects/arduino-and-xbee-battery-test-results/