论文部分内容阅读
空间资源复用是无线网络的关键特征，空间资源复用在提高网络容量的同时，也引起了公共信道冲突，这被认为是无线通信性能下降的一个主要原因。冲突的本质是干扰，干扰建模是量化干扰的通用方法。分布式理论在无线传感器网络中有着广泛的应用，无线网络中的许多问题都是分布式算法设计中需要面对的经典问题。染色问题在实际生活中有着广泛的应用，不仅是无线网络中是一些MAC协议设计的基础，也是分布式计算中打破对称的一个主要方法。分布式理论的一些问题具有一定难度，容易产生的一个错觉是理论与实际应用之间存在较大断层，即理论上很成熟，但是实际应用中又比较抽象。论文从应用的角度探究分布式理论在无线传感器网络算法设计中出现的经典问题，并对一些经典问题之间的关系进行了讨论，例如独立集和染色之间、独立集和支配集之间等。目前主要存在冲突图（Conflict Graph, CG）模型、一般图（General Graph, GG）模型、协议干扰模型（Protocol Interference Model, PM）和物理干扰模型（Signal to Interference PlusNoise, SINR）等各类干扰模型，这些模型各有优缺点。论文通过干扰建模对SINR模型进行扩展，使得一些CG模型或者PM能够更好的描述实际情况。最后，在我们扩展后的SINR模型下，利用弱图染色的思想，设计染色算法。具体研究内容如下：在各类干扰模型中，物理干扰模型能够更好的描述实际情况，2-distance冲突图模型能够更好地限制干扰，但是只能模型化两个并发传输的干扰。我们累积所有并发传输的干扰，并以此为依据建立规划函数，将2-distance冲突模型转化为SINR。论文总结了将冲突图模型转化到SINR模型的一般过程，通过选择合适的因子实现σ模型向标准2-distance的转化，通过公式推导将以接收节点为中心的PM模型转化为σ-协议模型，以发送节点为中心的PM模型转化为σ-Tx协议模型，从而达到PM模型向SINR模型的转化。染色问题在不同的干扰通信模型下有很多不同的解决方案，我们在深入研究染色问题之后，结合缺陷染色和部分正常染色的思想，在SINR模型下得到一个(Δ+1)-染色分布式算法。我们假设图最初弱染色，并且每一个节点有一个不一样的顶点标识符。我们首先计算一个极大独立集（Maximal Independent Set, MIS），算法的时间复杂度为O(logn)；然后通过时间复杂度为O(Δ)的K-部分正常染色算法和时间复杂度为O (logΔ)的D-缺陷染色算法得到(Δ+1)-染色，其中K <Δ，最终算法的时间复杂度为O (logn+Δ)。在设计弱染色算法时，利用贪心策略和启发式规则使得节点能够选择正确的颜色而不产生错误。论文对每一个算法进行了严格的算法正确性分析和证明。