Techniques and tools are described for transmitting beacon messages using a wireless communication protocol, such as the Bluetooth Low Energy protocol. In some examples, beacon messages can be generated in a compact format and included in an AdvData portion of a payload of a protocol data unit of a Bluetooth Low Energy advertising channel packet. A beacon message can be transmitted from a stationary beacon generation device and broadcast to an area within a transmission range of the beacon generation device, and mobile computing devices, such as mobile phones, can receive the beacon message and perform one or more actions in response to information contained in the beacon message, all while conserving energy used by the beacon generation device and the mobile computing device.