Due to the limited resources and dynamically varying nature of wireless links, guaranteeing high quality demands for a large number of heterogeneous users is very challenging in video streaming over wireless networks. In this paper, we introduce a layered multiple description coding with an embedded forward error correction scheme (LMDC-FEC). The combination of layered MDC and FEC aims at coping with not only the diverse bandwidth and unreliability of wireless links but also the heterogeneous user devices. We further propose a joint replication density and rate allocation (RD-RA) optimization problem in the context of video on-demand systems (VoDs) over wireless mesh networks (WMNs), and employ a genetic algorithms based approach to solve the optimization problem. Our objective is to elaborately distribute proper replication density for each video segment and allocate optimal bit rate to each layer of each segment in order to gain high userperceived quality (UPQ) with small consumption of storage resource. By this method, both optimal replication densities and rate allocations are found in accordance with the access rate of segments, the diverse loss characteristics of descriptions in each segment, and the rate–distortion relationship of segments, so as to thoroughly optimize UPQ and storage resource consumption. Simulation results demonstrate that our proposed method significantly enhances the streaming performance of VoDs over WMNs.