Fast Detection of Compact Topology Representation for Wireless Networks

This paper considers a hybrid cellular architecture in which mobile devices can communicate with users in their vicinity, e.g. using 802.11 interface, in addition to the base stations of the cellular network. Such an architecture may assist some of the critical tasks of the cellular networks such as mobility management, content caching and relaying. In order to these capabilities, the 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 underlying network, a compressed snapshot of the network topology should be collected within a very short time duration and with minimal communication between mobiles. Addressing this need in this paper, we propose a compact topology representation that is suitable for a number of applications. We utilize the broadcast nature of the wireless channel to design an efficient topology detection algorithm that acquires a compact representation of the underlying network (at most 3 N links and a low ‘stretch factor for the N mobiles) in near constant time (~100 ms).