Distributed opportunistic scheduling for ad-hoc communications: an optimal stopping approach

Distributed opportunistic scheduling for ad-hoc communications: an optimal stopping approach

We consider distributed opportunistic scheduling (DOS) in wireless ad-hoc networks, where many links contend for the same channel using random access. In such networks, distributed opportunistic scheduling involves a process of joint channel probing and distributed scheduling. Due to channel fading, the link condition corresponding to a successful channel probing could be either good or poor. In the latter case, further channel probing, although at the cost of additional delay, may lead to better channel conditions and hence higher transmission rates. The desired tradeoff boils down to judiciously choosing the optimal stopping strategy for channel probing and the rate threshold. In this paper, we pursue a rigorous characterization of the optimal strategies from two perspectives, namely, a network-centric perspective and a user-centric perspective. We first consider DOS from a network-centric point of view, where links cooperate to maximize the overall network throughput. Using optimal stopping theory, we show that the optimal strategy turns out to be a pure threshold policy, where the rate threshold can be obtained by solving a fixed point equation. We further devise an iterative algorithm for computing the threshold. Next, we explore DOS from a user-centric perspective, where each links seeks to maximize its own throughput. We treat the problem of rate threshold selections for different links as a non-cooperative game. We explore the existence and uniqueness of the Nash equilibrium, and show that the Nash equilibrium can be approached by the best response strategy. We then develop an online stochastic iterative algorithm using local observations only, and establish its convergence. Finally, we observe that there is an efficiency loss in terms of the throughput at the Nash equilibrium, and introduce apricing-based mechanism to mitigate the loss.

我们考虑无线自组织网络中的分布式机会调度（DOS），其中许多链路使用随机接入竞争同一信道。在这类网络中，分布式机会调度涉及联合信道探测和分布式调度的过程。由于信道衰落，与成功的信道探测相对应的链路状况可能良好，也可能较差。在后一种情况下，进一步的信道探测虽然会增加延迟，但可能会导致更好的信道条件，从而提高传输速率。期望的权衡归结为明智地选择信道探测的最优停止策略和速率阈值。在本文中，我们从两个角度，即网络中心视角和用户中心视角，对最优策略进行严格的刻画。我们首先从网络中心的角度考虑DOS，其中链路协作以最大化整个网络的吞吐量。利用最优停止理论，我们表明最优策略是一种纯阈值策略，其中速率阈值可通过求解一个不动点方程得到。我们还设计了一种迭代算法来计算该阈值。接下来，我们从用户中心的角度探索DOS，其中每条链路都试图最大化自身的吞吐量。我们将不同链路的速率阈值选择问题视为一个非合作博弈。我们探讨了纳什均衡的存在性和唯一性，并表明可以通过最佳响应策略来逼近纳什均衡。然后，我们仅使用局部观测开发了一种在线随机迭代算法，并证明了其收敛性。最后，我们观察到在纳什均衡下吞吐量方面存在效率损失，并引入一种基于定价的机制来减轻这种损失。