论文部分内容阅读
不同于传统的无线自组织网络,能量效率优化是无线传感器网络的首要设计目标。为了减少空闲侦听所造成的能量浪费,无线传感器网络通常以低占空比的模式运行。然而,节点的低占空比操作又为低延迟高能效的数据传输带来了新的挑战。一方面,低占空比操作虽然提高了能效但是却产生了显著的睡眠延迟;另一方面,低占空比操作使得无线媒介丧失了固有的广播特性,从而导致了广播传输的低效性。因此,低占空比传感器网络的数据传输调度问题是一个重要且具有挑战性的研究问题。低占空比传感器网络的数据传输调度问题主要关注的是如何基于已知的数据链路层信息或者结合数据链路层的设计提出面向低占空比传感器网络的有效的数据传输策略,以应对低占空比操作所带来的延迟能效和广播能效的挑战。现有的工作仍然存在一些不足,例如缺少对延迟和能效权衡优化的研究、没有考虑利用无线媒介的广播时空特性来优化广播能效且缺乏理论上的性能保证、忽视了广播传输的能量公平性问题以及缺乏对分布式广播调度算法的研究。本文主要针对现有工作的这些不足进行了研究,其主要贡献如下:1.针对适度规模的低占空比传感器网络中传输数据较大的事件监测应用,首先定义了一个归一化的网络效用模型来刻画事件延迟和网络能效的权衡关系,然后提出了一个完全分布式的低延迟高能效的决策机制来进行感知节点的在线选择,以使得在保证避免冗余的事件监测信息传输的前提下达到网络效用的最大化,并且从理论上分析了该机制的性能。此外,通过利用节点中存储的已知历史信息进一步优化了算法的性能,并且提出了一个sink扩展机制将解决方法扩展到面向大规模监测区域的场景。仿真实验结果显示了该决策机制展现了平均事件延迟和网络生存周期之间一个相当好的权衡关系,并且展现出比已有的方法更好的性能。2.针对低占空比传感器网络中最小覆盖延迟约束下的最小能量广播问题,提出了一个利用无线媒介的广播时空特性的近似算法。首先证明了目标问题是NP难的,然后通过构造多跳广播的时空关系图将目标问题建模成一个在时空关系图上的有向最优延迟群组斯坦纳树问题,并且通过提出一个基于确定性随机取整的方法近似解决了该问题。基于有向最优延迟群组斯坦纳树问题的解决方法,进一步设计了一个新颖的广播调度构造算法以得到目标问题的解决方法,该算法本质上避免了广播中的冗余传输并且极大地降低了包冲突概率。最终,通过理论分析证明了提出的解决方法可以达到一个多项式对数的近似比。仿真实验结果验证了所提出的解决方法相比较传统的方法具有显著更好的能量效率,并且会随着广播消息的增大呈现出更好的性能优势。3.针对低占空比传感器网络中最小平均延迟广播调度的能量公平性问题,分别提出了一个集中式近似算法和一个有效的分布式算法。首先将目标问题转换成了等价的负载均衡父节点指派问题并且证明了它的NP困难性。然后提出了一个负载均衡父节点指派算法来解决这一问题,并且证明了该算法的近似比。进一步地,提出了一种简单高效的分布式算法并且分析了它的消息复杂度。最后,仿真实验结果表明提出的集中式近似算法和分布式算法与传统的方法相比较而言,在能量公平性、总能量消耗和传输成功率方面都显著地具有更好的平均性能。最后对本文工作进行了总结,并讨论了进一步的研究工作。