Systems and methods for robust beam tracking and data communication data are provided. The method includes dividing, by a base station, time into frames each having two phases, a location probing phase and a data communication phase. In the location probing phase, the base station uses a fractional search policy to localize a mobile device by transmitting multiple probing packets over different time-slots and updates information about a location of the mobile device. In the data communication phase, the base station communicates with the mobile device while expanding a beamwidth to compensate for possible mobility of the mobile device.