Abstract: Traditional wireless sensor network localization algorithms are generally based on the assumption that there is a mapping function between measured distance and Euclidean distance for pair of wireless sensor nodes. This assumption however would not hold when wireless sensor networks are deployed into complex areas. Thus, directly applying traditional algorithms to these networks would result in a large localization error. To solve the localization problem in the anisotropic wireless sensor networks deployed in complex areas, a range-free localization algorithm based on convex-hull partitioning (CHP) is proposed. At first, all the reference nodes are divided to form different convex-hulls in the CHP. And then, each unknown node determines which convex-hull it belongs to. Finally, each unknown node computes its own location based on reference nodes in the convex-hull it belongs to. The CHP algorithm can effectively reduce the localization errors incurred by the boundary or barrier factors of complex area through theoretical analysis. The results from extensive simulations show that compared with traditional algorithms, the CHP algorithm significantly reduces the localization errors and error jitters. At the same time, the proposed CHP localization scheme minimizes the unfavorable effects brought by the boundaries or barriers of the complex area in the executing process.