论文部分内容阅读
在过去几十年无线传感器网络(Wireless Sensor Networks, WSNs)得到了快速、全面的发展,其应用领域也在逐渐扩大。求解可同时传输的链路数目问题是无线传感器网络研究的基本内容之一。链路调度就是研究在给定的时隙中哪些发送接收节点对可以同时被激活进行传输。有效的调度算法不仅可以提高网络的吞吐量,减少时延,而且可以延长无线网络的生命周期。因此,链路调度问题成为了无线传感器网络研究中的主要性能瓶颈。在无线通信环境中,链路传输需要共享信道,同时传输必将造成彼此的干扰,因此选择合适的干扰模型对于设计算法显得尤为重要。在本文的第2章,介绍了两种常用的干扰模型,相比于基于图的协议干扰模型,SINR模型更贴近实际情况且更加准确。在调度问题中,功率分配是资源分配的关键部分,对于能力有限的传感器节点来说功率分配尤为重要,因此在第2章详细介绍了显示功率分配方案,本文所有算法都是基于显示功率分配策略的。具体研究内容如下:(1)单时隙调度包括极大链路调度(Maximum Link Scheduling, MLS)和极大带权链路调度(Maximum Weighted Link Scheduling, MWLS)两方面。单时隙调度已经证明是NP-难的,因此可以设计性能较好的启发式算法。在第2章提出了两个SINR模型下的启发式算法,算法均使用了显示功率分配。针对MLS问题,提出的MTMA (Maximum Tolerance and Minimum Affectance)算法在调度链路数目上性能得到了提高;针对MWLS问题,提出的MWMA (Maximum Weighted and Minimum Affectance)算法在运行时间和调度链路数目两方面均表现较优。这两个算法都考虑了环境噪声,因而更具实际意义。不仅在理论上证明了算法的正确性,而且通过仿真实验证明了算法性能的优越性。(2)分布式调度方案的缺点之一就是控制小时隙引起的开销,需要调度的链路越多,开销也越大。为了减少控制小时隙的开销,在第4章,给出了警戒半径的定义,提出了带有预筛选机制的分布式链路调度方案PS-DSS (Pre-Selection Distributed SINR-based Scheduling)。这个预筛选机制可提前删除部分造成调度集合传输失败的链路,有效降低了选择链路失败的概率,同时该分布式算法经证明可得到最佳的吞吐量。最后给出了一个带有预筛洗机制的启发式调度算法。