1.1 研究背景、目的及意义

（a）研究背景

随着无线应用的不断拓展，频谱资源的缺乏成为无线应用研究过程中不得不面临的问题。当前采用的固定频谱分配方案，易于管理。但是，由于频谱资源在不同位置不同时间段的利用有所不同，这种静态的频谱分配方式造成了频谱的利用率低。若能对传感器智能监测系统中的频谱进行动态分配，可以缓解当前无线频谱资源短缺、频谱利用率不均的局面。

在传感器智能监测系统中，传感器可以监测环境中湿度、温度和气压等。由于传感器的计算能力、内存、通讯带宽均有限，所以每个传感器结点仅能对半径为内的区域进行监测。因此，要对整个环境进行监测需要多个传感器协调工作。在这种情形下，由于传感器监测和通讯的局部性，没有一个传感器可以拥有其他所有传感器的相关数据。在对传感器智能监测系统的进行无线频谱分配时，我们必须也只能使用分布式算法。当两个传感器的覆盖区重叠时,不能使用同一段的频谱，否则信号会互相干扰。也就是说，如果代表两个传感器的代理节点之间有边相连，两个代理节点不能取相同的状态，否则会发生冲突，该问题完全可以被形式化为图形着色问题，由此可以设计势博弈算法来解决图形着色类问题。此时，我们就可以把信道分配问题转化到图形着色问题的求解上。

图形着色是典型的DCOP（分布式约束满足问题），其应用相当广泛，比如资源分配，计划编排，工业任务分配和调度问题，分布式传感器网络管理等诸多问题都可以形式化为图形着色问题。因此图形着色问题自提出以来一直是计算机科学研究的热点问题，其解决方法可以分为三类：完全算法：比如Dynamic programming，Local search，Branch-and-reduce等等。该类算法追求完美的结果，但是往往时效性和鲁棒性都很差，不适合用于解决大规模的分散式图形着色问题;并行算法：比如：MIS（Max Independent Set），Jones-Plassmann，LDF(Largest-Degree-First)和SDF（Smallest-Degree-First）等等。该类算法核心在于选择图形中独立集，并用并行处理器同时对这些独立集进行着色。这类算法在并行机流行的时候很适用，到现在该类算法已经基本被淘汰;分布式算法：比如BP（Belief Propagation），Max-product，Max-sum等等这类算法特点是仅用小范围内的局部通信就可以解决分布式图形着色问题。然而这类算法在相邻节点增加时，算法效率会严重下降甚至崩溃。另外在诸如无线传感器网络的信道分配问题中，当节点只能检测到冲突却不能与相邻节点进行通信时，该类局部信息传递算法就不能适用了。另外在数学上，该算法的收敛性一直没有得到证明。

（b）研究目的及意义

本次毕业设计主要针对无线传感器信道分配问题的分散式求解问题，这是一个比较具有现实意义的问题，如前文所述，当前无线传感器网络主要采用采用的固定频谱分配方案，易于管理。但是，由于频谱资源在不同位置不同时间段的利用有所不同，这种静态的频谱分配方式造成了频谱的利用率低。众所周知，国际国内对无线频谱的划分有严格的限制，但是在小范围领域，用户却可以灵活的选择信道，这就是使得我们的研究具有实际意义。我们旨在找出一种比较通用的方法，在适用条件下将信道分配问题比较高效率、成本可控制的解决。在广泛查阅资料的基础上，我们把研究的重点放在图形着色问题的势博弈方法上，以WRM-I为核心。

1.2 国内外研究综述

无论是图形着色问题，博弈论方法还是信道划分问题，国内外都有较为广泛深刻的研究。这3个问题是有广泛而深刻的联系的，博弈论方法是解决图形着色问题比较通用的解法，而我们有意把图形着色运用到信道划分上。在此前，Pragnesh Jay Modi等人05年提出ADOPT算法，该算法使得代理在异步决策时然可以找到全局最优解。A.Petcu and B. Faltings.等人在05年提出了DPOP算法，考虑了对求解问题拓扑结构的适应性。Miller Rand Lesser V等人在06年提出APO算法首次引入中间块的概念将大的DCOP问题分解成若干小的DCOP问题来解决，进一步提高了算法的求解规模。Cooper等人在07年DAC算法以及A.Farinelli等人在08年aamas中提出的改进最大和算法，利用局部信息的传递解决了DCOP问题。Marden等人08年提出JSFP算法改进了经典的博弈论算法用于DCOP问题的求解。