In this mission it is almost impossible to fail. Doing this mission means keeping your fingers active and keeping your army going. The tribes will defend themselves and it will be very hard for the tribe leaders (Chiefs) to die off. The goal here is to build up a big enough army over time while clearing up some objectives and killing enemies.
Once you have a large enough army you can actually engage the northern base with great success. By knocking it out you can assure a victory as it will support the pending objective that all chiefs must survive.
Your unit composition should start mostly with musketeers and slowly expand into cannons. Mortars are units you should only consider bringing in near the end when you storm the northern base.