There are lots of constrains for video steganography in sensor networks. Based on the analysis of previous similar researches, a novel video steganography algorithm is proposed to improve steganography efficiency and reduce energy consumptions. Considering the characteristics of H.264/AVC video stream in multimedia sensor network, this algorithm promotes a novel classification strategy having the advantages of error drift prevention and covering code adjustment with simplified calculation complexity. Furthermore, for different types of data features, we introduce and design a covering coding method satisfied the application limited conditions of multimedia sensor networks. Both data analysis and experimental results show that the proposed algorithm is robust against statistical analysis attacks and it also minimizes embedding error. With less communicating redundancy, the algorithm doubles embedding efficiency and decreases computation complexity from exponential to linear.