Abstract: Location service protocols in mobile ad hoc network maintain nodes' positions. The performance of upper layer protocols depends on the performance of location service. Protocol cost is defined as the number of one-hop location querying packages and location updating packages. It is one of the most important performance indices of location service protocol and determines the scalability and other performance of the protocol. Without considering location reguest, existing location service protocols optimize protocol cost for networks with specific communication features. For optimizing the location service protocol cost in networks with different communication features, this paper proposes a minimum cost location updating tree. It is used to optimize protocol cost of multi-home region location service protocol according to the number of location querying to each home region and the protocol package transmission costs. Then, it is proved that the minimum cost location updating tree problem is an NP-hard problem. Based on these works, this paper then proposes a demand-driven multi-home region location service protocol. This protocol uses a kind of real time algorithm to get the minimum cost location updating tree just before location updating, and then forwards location updating packages according to the tree. The experimental results show that the proposed protocol can decrease the protocol cost and is more scalable.