A method and apparatus to reduce the overhead related to allocation of the terminal identifier in a random access procedure and an optimized method for detecting a collision are provided. By allocating a “short” terminal identifier in the Random Access Response that is identifiers and allocating the permanent terminal identifier at the end of the random access procedure, the size of data that must be transmitted in the Random Access Response is reduced and power is saved.