Fast detection of compact topology representation for wireless networks

This paper considers a hybrid cellular architecture in which mobiles can communicate with others in their vicinity, e.g. using 802.11 interface, in addition to the base stations of the cellular network. Such an architecture can aid device-to-device communication as well as assist critical tasks of cellular networks such as mobility management, content caching and relaying. In order to enable these capabilities, base stations need to have sufficient knowledge of the underlying network topology induced by the 802.11 links of the mobiles. Due to the dynamic nature of this network, a compressed snapshot of its topology should be collected within a very short time duration and with minimal communication among mobiles. Addressing this need, we propose a compact topology representation that is suitable for a number of applications. We utilize the broadcast nature of wireless channels to design an efficient topology detection algorithm that acquires a compact representation of the underlying network (at most 3N links and a low `stretch´ factor for the N mobiles) within a short duration (10s of ms). Our scheme does not have collision resolution, backoffs or any of the other MAC layer inefficiencies.