We are using yagi antennas, but the terrain has substantial differences in elevation and is also covered with many trees. Will these obstructions impede our signals? Do we need a direct line of sight from antennas? Is there any thing we can do to increase our signal strength?
I think in your case, more than increasing signal strength, you need to properly plan your antennas without much disturbance from trees and elevations. Make sure you do a site survey, a signal quality, and a link test very carefully. If it still doesn't help, then you may want to increase the signal strength.
I also recommend that you read these articles by Lisa Phifer:
Understanding wireless antennas - part 1
Understanding wireless antennas - part 2