A TMSI, comprising a TMSI identification field and a TMSI generation field, is allocated to a mobile subscriber. For non-restart situations, this involves selecting an unused TMSI identification field value; determining an associated present TMSI generation field value; and performing a normal allocation adjustment to the present TMSI generation field value, thereby producing an adjusted TMSI generation field value. A complete TMSI is generated from the selected TMSI identification value and the adjusted TMSI generation field value. The complete TMSI is allocated to the mobile subscriber. For a normal release situation, the TMSI identification value is processed so that it will be considered unused, and a normal deallocation adjustment is performed to the adjusted TMSI generation field value. In some embodiments, the normal deallocation adjustment restores the TMSI generation field to its earlier value. In an abnormal release, the TMSI generation field value is left unchanged.