Token traversal in ad hoc wireless networks via implicit carrier sensing

摘要: Abstract Communication problems in ad hoc wireless networks have been already widely studied under the SINR model, but a vast majority of results concern with constraints on connectivity, so called strongly-connected networks. In such networks, connectivity is defined based highly reliable links, that is, where both ends are located far closer from their transmission boundaries. What happens if network not strongly-connected, e.g., it contains some long still viable “shortcut links” connecting boundaries? It known even single broadcast weakly-connected uniform powers requires Ω ( n ) communication rounds, number nodes network. The best up-to-date (randomized) distributed algorithm, designed by Daum et al. [1] , accomplishes task O log 2 ⁡ rounds high probability. this work, inspired work broadcasting, we show novel deterministic implementation token traversal — fundamental tool systems model and no restriction connectivity. We efficient very harsh without GPS, carrier sensing other helping features. apply method to span tree accomplish N deterministically, provided equipped unique IDs range [ 1 ] for integer ≥ . This result implies an -round randomized solution does require IDs, which improves lower bound algorithms proved our shows tight randomization. Our routine, terms time memory, implicit algorithmic new type selectors, might be independent interest applicable tasks setting.