张源

（东南大学 移动通信国家重点实验室，江苏 南京 210096）

1 引言

考虑一个一般的无向图G=(V, E)，其中V代表所有节点的集合，E代表所有边的集合。考虑E的某个子集，如果其中任意2条边都没有交点，则称该子集为图G的一个匹配（match）。假设每条边e∈E都被赋予一个正权重 we，则本文研究最大权匹配（MWM）问题，即寻找具有最大权重和的匹配。在形式上，MWM问题可以描述为下列二值线性整数规划问题：

其中，xe=1或0分别代表边e是或不是匹配的边，N(i)是所有与节点i相连的边构成的集合。

最大权匹配问题是一个非常基本的数学问题[1]，并且能被用于解决大量实际问题。在无线网络领域中，有各种无线资源分配与调度问题，其核心就是寻找给定图的最大权匹配如文献[2,3]。因此，高效的MWM算法，对于解决无线网络中的资源调配问题是非常重要的。事实上，在图论、组合优化等数学领域中针对该问题的研究已经相当充分与完整，并已提出了大量算法[4,5]。然而，这些算法都是中心式的，即需要有某个中心节点知道整个图的全局信息。在无线网络中，一般来说是不存在这种能掌握全局信息的中心节点的，而必须采用能够分布式执行的最大权匹配算法。因此，这些算法是无法直接应用于无线网络中。

在文献[6,7]中，已经提出了几种分布式MWM算法。这些算法都是基于贪婪（greedy）原则，非常简单，其找出的匹配质量一般较低（本文第4节中的仿真结果也说明了这一点）。近年来，又出现了一类全新的基于信念传播（belief propagation）的方法。……