In this paper, we proposed an efficient short address allocation mechanism for WiBEEM devices using NAA(Next Address Available) algorithm. The proposed addressing mechanism is based upon the NAA information that is delivered over the beacons every time it is transmitted at the beginning of each super-frame. The NAA-based addressing mechanism is not a systematic way of allocating short addresses to newly joining devices and thus tree-routing cannot be supported. However, it has great advantages when U-City core services including U-Parking Lot System or ATIS(Advanced Traveler Information System) services that require high-speed mobility are considered. Moreover, the proposed addressing mechanism can provide significant expandability of the wireless network to various applications and fast device discovery.