Increasing demand for wireless mobile communications, coupled with limited network resources, has motivated investigation into alternative efficient mobility management solutions. In this paper, we consider wireless PCS call setup protocols. We propose a Lightweight Location Lookup Protocol, which significantly reduces the network signaling and setup delay during call setup. As an alternative, we propose a Reverse Connection Setup protocol that also performs efficient call setup, while minimizing the cost of failed call attempts. The two new protocols have different advantages, in particular when combined with location management techniques including HLR/VLR, HLR/VLR with partial replication, and HLR/VLR with caching. We study combinations of call setup protocols with location management techniques and compare their performance. Both analytical and simulation results are presented.