空间信道博弈的分布式算法

发布时间：2018-05-04 20:18

本文选题：分布式计算 + 无线网络　；参考：《南京大学》2014年硕士论文

【摘要】：随着无线网络和移动计算技术的迅速发展,整个网络的状态呈现出两大趋势。首先,网络中的用户数量迅速增加。当使用信道的用户越来越多,而信道频谱作为一种不变的自然资源显得越来越稀缺的时候,一种高效的调度算法显得越来越重要。其次,用户的行为逐渐由硬件控制转向软件控制,从而变得越来越智能。用户可以根据自己的需求破坏既定的通信协议,做出更加复杂的行为,从而增加自己所获得的网络资源。这样的行为有可能损害其他用户的利益,并且破坏整个系统的性能。本篇论文将该优化问题建模成为图博弈,目标是使用局部的分布式算法给出一个性能最优或者接近最优的纳什均衡(Nash equilibrium)。纳什均衡的最优性保证了整个网络的性能,纳什均衡的稳定性保证了用户不会偏离已有的协议,从而同时克服了上述两个问题。为了实现这个目标,我们将图博弈的优化问题归约为在相应的因子图中计算最大后验概率,并且使用置信传播算法(Belief Propagation)来设计局部的消息传递算法。该算法在无环图上可以在线性时间内求出最优解,在有环图上同样可以保证极快的收敛速度和稳定的性能。此外,在平面图上,该算法可以给出极好的近似结果。
[Abstract]:With the rapid development of wireless network and mobile computing technology, the state of the whole network presents two major trends. First, the number of users in the network is growing rapidly. As more and more users use the channel, and the channel spectrum is becoming more and more scarce as a kind of invariant natural resources, an efficient scheduling algorithm becomes more and more important. Secondly, the behavior of users is gradually changed from hardware control to software control, thus becoming more and more intelligent. Users can break the established communication protocols and make more complex behaviors according to their own requirements, thus increasing the network resources they obtain. Such behavior may harm the interests of other users and undermine the performance of the system as a whole. In this paper, the optimization problem is modeled as a graph game, and the goal is to give a Nash equilibrium Nash equilibrium with or near optimal performance using a local distributed algorithm. The optimality of Nash equilibrium guarantees the performance of the whole network, and the stability of Nash equilibrium ensures that users will not deviate from the existing protocols, thus overcoming the above two problems simultaneously. In order to achieve this goal, we reduce the optimization problem of graph game to calculate the maximum posterior probability in the corresponding factor graph, and design a local message passing algorithm by using the confidence propagation algorithm (belief Propagation). The algorithm can obtain the optimal solution in linear time on the acyclic graph, and it can also guarantee the extremely fast convergence speed and stable performance on the annular graph. In addition, the algorithm can give excellent approximate results on planar graphs.
【学位授予单位】：南京大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TN911.5

【相似文献】