One of the most important issues in location-based services is tracking moving objects efficiently. To achieve this goal, an efficient protocol which updates location information in a location server is primarily needed. In fact, the performance of a location update strategy highly depends on the assumed mobility pattern. In most existing studies, however, the mobility issue has been disregarded and oversimplified as a linear function of time. In this paper, we propose a new mobility model, called state-based mobility model (SMM) to provide a more generalized framework for describing both the mobility and updating location information of complexly moving objects. We also introduce the state-based location update protocol (SLUP) based on this mobility model.