We investigate the navigation process on a variant of the Watts-Strogatz small-world network model with local information. In the network construction, each vertex of an N × N square lattice sends out a long-range link with probability p. The other end of the link falls on a randomly chosen vertex with probability proportional to r-α, where r is the lattice distance between the two vertices, and α ≥ 0. The average actual path length,i.e. the expected number of steps for passing messages between randomly chosen vertex pairs, is found to scale as a power-law function of the network size Nβ, except when α is close to a specific value αmin, which gives the highest efficiency of message navigation. For a finite network, the exponent β depends on both α and p, and αmin drops to zero at a critical value of p which depends on N. When the network size goes to infinity,β depends only on α, and αmin is equal to the network dimensionality.