With the emergence of cloud computing, users are increasingly using storage services of cloud providers to satisfy their storage needs. However, these cloud providers charge at different rates and are not 100% reliable, resulting in occasional service outages. Thus the costs on end users are two folds: (1) cost of storage service, and (2) cost of information loss in cloud service outages. End users require a solution that minimizes the overall cost to balance the storage cost and the probability of successfully retrieving stored objects in cases of provider failures. In this paper, based on the concept of federated cloud agent proposed in our previous work [1], we study the cloud storage management strategy which allows end users to simultaneously deploy storage objects to multiple cloud service providers, based on their unit storage costs and failure behaviors. We propose to use random network coding and a decision model to solve this storage management problem. The random network coding over information objects to be stored in clouds helps simplify the cloud storage management and the decision model forms the foundation of solving the problem in a dynamic environment. We solve the decision model analytically and also propose two practical solutions based on efficient local search algorithms which can achieve near-optimal performance and lower computational complexity. In the experiments, we evaluate the proposed cloud storage strategies against a few reference schemes and find our schemes can achieve a good balance between the information success recovery rate and storage cost.