论文部分内容阅读
无线网络作为当今应用最广泛的网络接入方式正向覆盖范围更广,接入用户更多,传输速率更快的方向快速发展。无线传输媒体的开放性以及通信频谱资源的有限性与通信需求的无限增长形成了天然的矛盾。因此如何充分利用这些资源来最大化地满足通信的需求成为无线网络的核心问题。无线网络吞吐量优化(Throughput Optimization in Wireless Networks),考虑如何充分利用网络中的有限资源(时间、空间、频谱等等),结合底层的通信技术及特性,以达到最大化满足网络通讯需求的目的。为了更好地对信道及时间片资源进行分配,必须对信号传输之间的干扰有精确的了解与控制,这促使对干扰模型的研究。干扰模型分为协议干扰模型及物理干扰模型。前者又称为干扰图模型,其假设两个干扰实体(节点或者链接)之间的干扰关系是二元的。这样网络中的干扰关系构成一个干扰图,对于建模其上的优化问题可以方便的使用已有的图论算法。但其缺点是过于简化的干扰关系即无法度量干扰的程度从而失去一些复用的机会,亦无法建模多元的累积干扰效应。因此,优化结果与实际结果存在较大的偏差。相比而言,物理干扰模型(SINR模型)则被认为是较为精确的模型,其基础是信噪比SINR (Signal to Interference and Noise Ratio),通过SINR是否大于某一阈值来判定参与的各方是否相互干扰。该模型的优点是,一方面较为精确地建模了干扰程度的关系,同时可以建模多元的累积干扰效应,此外也可以通过香农公式与信道容量联系起来。但SINR模型数学形式的非线性使得建构其上的优化问题建模无法在多项式时间内求解,另外它对底层的信号接收强度RSS的精度非常依赖,从而降低了SINR模型的实用性。为了克服上述模型的缺点,我们从两个方向来优化干扰模型。其一,我们希望建立高效而精确度可控的干扰模型生成机制,最大限度地将复杂的网络环境反映到模型之中,从而提高基于这些干扰模型的吞吐量优化算法的效果。其二,我们期望改造干扰模型以达到精确度及计算复杂性兼顾的目的。具体来说我们的工作贡献主要集中于以下方面:●针对SINR干扰模型极度依赖于底层RSS精确度的问题,我们提出了一种基于测量的高效且精确度及开销可控的SINR干扰模型生成机制。我们通过实验证明底层RSS精度对于基于SINR的优化算法的效果有极大的影响,同时基于SINR模型的优化算法需要所有节点之间在所有信道上的RSS,这样的测量需要O(N2 MC)的时间开销。我们提出了一个基于测量的方法利用“少量测量,大量估算”的基本思想将时间开销降低到O(N/M)的量级。同时我们在理论上得出测量数量与估算精确度与测量开销之间的数学关系,从而提供了一个控制时间开销与精确度之间平衡的方法。基于我们真实SWIM实验平台数据的实验证明了我们方法的有效性。●针对如何高效的获得网络SINR干扰模型的问题,我们发现在实际的无线网络环境中,来自多个节点的信号强度RSS是线性叠加的。从而将整个基于测量的SINR干扰模型生成问题建模成为一个线性系统,利用压缩感知(Compressive Sensing)的思想与数学原理,我们设计了一种基于压缩感知的SINR干扰模型高效生成机制,其将时间开销降低到O(log N的量级,同时可以保证1-2e-Tδ/8的估算精确度。我们通过实际平台数据的实验发现基于压缩感知的方法与基于测量的方法在不同网络密度下的预测精度上具有很强的互补性。在不同的网络环境下,用户可以选择两者中较好的一个作为生成SINR干扰模型的方法。●针对协议干扰模型无法处理累积干扰效应及无法精确表达网络干扰程度的问题,我们提出了一个新型的协议干扰模型:量化冲突图模型(Quantized Conflict Graph, QCG)。我们证明该模型在处理链接调度及网络干扰最小化等问题时可以很好地处理如累积干扰效应等问题,并可以得到相比于传统干扰图模型更好的优化结果而并不增加优化问题的复杂度。我们同时研究了基于矩阵填充的高效QCG生成机制。该方法基于矩阵低秩逼近及列间相似性使得我们可以采用少量的测量结果生成精确的全网络QCG模型。实验结果证明了我们新型模型的有效性及高效生成机制在时间效率及精确度上的优势。