Melanesia is the region of Oceania consisting of Fiji, New Caledonia, Papua New Guinea, Solomon Islands and Vanuatu .