In spread spectrum (SS) based robust audio watermarking, the scaling parameter is an important factor for balancing between robustness and imperceptibility. There have been intense studies of the embedded parameter optimization in light of the signal-to-noise ratio (SNR), but little attention has been given to the constrained SNR. Moreover, traditional population-based stochastic search algorithms for optimizing the embedded parameter significantly increase the computation pressure of the corresponding audio watermarking schemes. This paper comprehensively investigates the effect of the constrained SNR on the optimization of the scaling parameter, from both model and algorithmic perspectives. Specifically, the empirical relationship between the scaling parameter, robustness, and imperceptibility is first analyzed in detail. Next, an SNR-constrained optimization model is presented. Then, to solve the proposed model and find the current optimal scaling parameter for watermark embedding, a binary search algorithm and a heuristic search (HS) algorithm are, respectively, developed. Finally, we embed the proposed model and heuristics in the SS-based audio watermarking scheme and compare the integrated technique (called SS-SNR-HS) with the existing similar schemes. The experimental results demonstrate that SS-SNR-HS not only is computationally simple, but also achieves better balance between imperceptibility and robustness and, thus, seems promising in copyright protection of online digital audio.