论文标题
无线网络中最短路径和背压路由的在线学习方法
An Online Learning Approach to Shortest Path and Backpressure Routing in Wireless Networks
论文作者
论文摘要
我们考虑多跃波无线网络中的自适应路由问题。假定链接状态是从未知分布中绘制的随机变量，该变量是独立且分布在链接和时间之间的。该模型最近在认知无线电网络和自适应通信系统中引起了人们的兴趣。在这样的网络中，设备在学习链路状态并更新传输参数以允许有效资源利用的意义上是认知的。该模型与有关链接状态均值完全了解的路由算法的广泛文献形成鲜明对比。目的是设计一种算法，该算法在线学习数据传输的最佳途径，以最大程度地提高网络吞吐量，同时使网络流量低于流量。我们为最短路径和背压（OLSB）算法开发了一种新颖的在线学习，以实现这一目标。我们严格地分析了OLSB的性能，并表明它与时间上的对数遗憾，被定义为与对链接状态均值完全了解的精灵相比，算法的丢失。我们通过广泛的模拟在数值上进一步评估OLSB的性能，该模拟支持理论发现并证明其高效率。
We consider the adaptive routing problem in multihop wireless networks. The link states are assumed to be random variables drawn from unknown distributions, independent and identically distributed across links and time. This model has attracted a growing interest recently in cognitive radio networks and adaptive communication systems. In such networks, devices are cognitive in the sense of learning the link states and updating the transmission parameters to allow efficient resource utilization. This model contrasts sharply with the vast literature on routing algorithms that assumed complete knowledge about the link state means. The goal is to design an algorithm that learns online optimal paths for data transmissions to maximize the network throughput while attaining low path cost over flows in the network. We develop a novel Online Learning for Shortest path and Backpressure (OLSB) algorithm to achieve this goal. We analyze the performance of OLSB rigorously and show that it achieves a logarithmic regret with time, defined as the loss of an algorithm as compared to a genie that has complete knowledge about the link state means. We further evaluate the performance of OLSB numerically via extensive simulations, which support the theoretical findings and demonstrate its high efficiency.
