CROSSOVER TIMES IN BIPARTITE NETWORKS WITH ACTIVITY CONSTRAINTS AND TIME-VARYING SWITCHING RATES

• 成果类型: Article
• 署名作者: Borst, Sem; den Hollander, Frank; Nardi, Francesca Romana; Taati, Siamak
• 署名单位: Eindhoven University of Technology; Leiden University - Excl LUMC; Leiden University; University of Florence; University of Groningen
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/22-AAP1787
• 发表日期: 2022
• 页码: 4279-4314
• 关键词: delay performance; access; metastability; asymptotics; algorithm

摘要

In this paper, we study the performance of a bipartite network in which customers arrive at the nodes of the network, but not all nodes are able to serve their customers at all times. Each node can be either active or inactive, and two nodes connected by a bond cannot be active simultaneously. This situation arises in wireless random-access networks where, due to destruc-tive interference, stations that are close to each other cannot use the same frequency band. We consider a model where the network is bipartite, the active nodes switch themselves off at rate 1 and the inactive nodes switch themselves on at a rate that depends on time and on which half of the bipartite network they are in. An inactive node cannot become active when one of the nodes it is connected to by a bond is active. The switching protocol allows the nodes to share activity among each other. In the limit as the activation rate becomes large, we compute the crossover time between the two states where one-half of the network is active and the other half is inactive. This allows us to as-sess the overall activity of the network depending on the switching protocol. Our results make use of the metastability analysis for hard-core interacting particle models on finite bipartite graphs derived in an earlier paper. They are valid for a large class of bipartite networks, subject to certain assump-tions. Proofs rely on a comparison with switching protocols that are not time varying, through coupling techniques.