I have a project that uses 4 DS18B20 temperature sensors. When powered using USB from my desktop it works perfectly. Very rarely one of the temp readings drops to -196.6°F, I can live with that. If I power it any other way. Power jack with 12V in, VIN pin with 11.6 or 7.6 V, Laptop USB both on battery or USB powered by a battery, I get random bad temp readings, -196.6°F, on all sensors. Sometimes many reads in a row. Results on test from data log here.
I have also tried using different sketches that ONLY read from the four sensors using both sensor address or by index. Using my phone via bluetooth to see the readings when not using a computer for serial, I get the same results. The ONLY way I get reliable results is powering the Mega with the desk top PC. Second place came from a powered USB hub plugged into the same computer.
If I power using the computer USB it will happily plod along for hours with no dropped readings. Even dropping the read times to 50mills only gets an occasional dropped reading.