A Message-Passing Algorithm for Wireless Network Scheduling.
A Message-Passing Algorithm for Wireless Network Scheduling.
复制标题
DOI：
10.1109/tnet.2014.2338277
复制
发表时间：
2015-10
期刊：
影响因子：
--
通讯作者：
Lai W
中科院分区：
文献类型：
--
作者：
Paschalidis IC;Huang F;Lai W
我们考虑在无线网络中的调度，并制定它作为最大加权独立集（MWIS）的问题上的“冲突”图，捕捉同时传输之间的干扰。我们提出了一种新的，低复杂度，完全分布式的算法，产生高质量的可行解。我们提出的算法包括两个阶段，每个阶段只需要本地信息，是基于消息传递。第一阶段使用梯度投影方法解决MWIS问题的松弛。我们考虑的松弛比简单的线性规划松弛更紧，并且在图中的所有团上都包含约束。算法的第二阶段从松弛的解开始，构造MWIS问题的可行解。我们表明，我们的算法总是输出一个最佳的解决方案，完美的图的MWIS问题。仿真结果比较我们的政策对载波侦听多路访问（CSMA）和其他替代方案，并显示出优异的性能。
We consider scheduling in wireless networks and formulate it as Maximum Weighted Independent Set (MWIS) problem on a “conflict” graph that captures interference among simultaneous transmissions. We propose a novel, low-complexity, and fully distributed algorithm that yields high-quality feasible solutions. Our proposed algorithm consists of two phases, each of which requires only local information and is based on message-passing. The first phase solves a relaxation of the MWIS problem using a gradient projection method. The relaxation we consider is tighter than the simple linear programming relaxation and incorporates constraints on all cliques in the graph. The second phase of the algorithm starts from the solution of the relaxation and constructs a feasible solution to the MWIS problem. We show that our algorithm always outputs an optimal solution to the MWIS problem for perfect graphs. Simulation results compare our policies against Carrier Sense Multiple Access (CSMA) and other alternatives and show excellent performance.