New selectors and locally thin families with applications to multi-access channels supporting simultaneous transmissions
New selectors and locally thin families with applications to multi-access channels supporting simultaneous transmissions
复制标题
新的选择器和局部精简系列，适用于支持同时传输的多路访问通道
DOI：
10.1016/j.tcs.2019.08.020
复制
发表时间：
2019
影响因子：
1.1
通讯作者：
Annalisa De Bonis
中科院分区：
文献类型：
--
作者：
Annalisa De Bonis
摘要本文考虑了多址系统中多个站点可以同时成功传输报文的冲突解决问题。我们假设有n个站点，且最多k个站点同时处于活动状态，k≤n，即有发送消息的意愿。如果最多d， d≤k，活动站同时发送则消息发送成功，如果同时发送的活动站数超过d，则消息丢失。活动电台从信道接收反馈，通知它们它们的消息是否已成功传输。优化的措施是解决所有活动台站之间的冲突所需的时隙数量，即使所有活动台站都能成功传输消息。我们通过提出一种冲突解决算法，证明该度量随着可以成功同时传输的消息数d而减少，该算法使用了特定情况下最优冲突解决算法使用的时隙数的1/d比率d= 1[26]。我们给出了一个下界它与算法使用的时隙数相差一个log （k/d）因子。该算法是通过[13]的一种新的选择器得到的，而下界则是由[1]，[12]的局部薄族的一种新的推广的非存在性结果隐含的。我们还提出了一种随机算法，该算法允许在k= O(1)的期望多项式时间内生成上述组合结构。
Abstract We consider the Conflict Resolution Problem in the context of a multiple-access system in which several stations can transmit their messages with success simultaneously. We assume that there are n stations and at most k, k≤ n, stations are active at the same time, ie, are willing to transmit a message. If at most d, d≤ k, active stations transmit simultaneously then their messages are successfully transmitted, whereas if more than d active stations transmit simultaneously then their messages are lost. The active stations receive a feedback from the channel that informs them on whether their messages have been successfully transmitted. The measure to optimize is the number of time slots needed to solve conflicts among all active stations, ie, to make all active stations transmit their messages successfully. We prove that this measure decreases with the number d of messages that can be simultaneously transmitted with success by presenting a conflict resolution algorithm that uses a 1/d ratio of the number of time slots used by the optimal conflict resolution algorithm for the particular case d= 1 [26]. We give a lower bound which is only a log(k/d) factor away from the number of time slots used by the algorithm. The algorithm is obtained via a new kind of the selectors of [13], whereas the lower bound is implied by a non-existential result for a new generalization of the locally thin families of [1],[12]. We present also a randomized algorithm that allows to generate the above combinatorial structures in expected polynomial time when k= O (1).