Abstract: With the fast development of 3G network, and the gradual popularity of Wi-Fi which can cover the whole city area, the requirement of multimedia service in mobile grid has been growing significantly in recent years. Because the streaming media service on the Internet is the most important supplier for mobile multimedia users in mobile grid, the edge streaming servers which locate between the boundary of wireless network and the Internet, can act as bridges and buffers to achieve the notable effect on reducing the load of the Internet and improving the QOS of mobile multimedia service. Accordingly, a new design of cluster-based edge streaming server (CESS) is introduced; in the meanwhile, aiming at solving the most important problems of CESS, namely loading balance, some analysis and experiments are carried out. On the basis of such work, a new kind of caching replacement algorithm called MCLBS is brought out to make CESS an adaptive loading balance system. Finally, the experiment results and related analysis show that in comparison with the traditional cache replacement algorithm, the MCLBS algorithm which is more suitable for cluster server architecture makes the cache-hit-rate increase significantly and greatly reduces remote server's bandwidth requirements in the same environment.