低占空比传感网中面向自适应性能需求的高效广播调度算法

无线传感器网络中的节点普遍采用低占空比的工作模式,该工作模式极大地减少了由于空闲侦听所带来的能量浪费,但也给网络中的广播问题带来了新的挑战.该文主要考虑如何解决低占空比传感网中的高效广播调度问题.大多数现有工作通常采用低效的传统广播传输模型,即任意局部单跳广播通过多次单播来实现.实际上,文中发现即使对于低占空比网络,无线媒介的广播属性依然能够为广播能效的提升提供潜在的机会.该文提出了一个新颖的机会式广播传输模型,该模型能够充分利用无线媒介固有的广播属性减少广播的总能耗.在单跳情形下,该模型允许发送者向它的任意接收者发送一个较小的beacon控制包,该beacon控制包将会通知接收者推迟自己的工作时隙去机会式地接收由发送者发送给其它节点的广播消息.在多跳情形下,该模型采用了一个有效的预推迟机制,即允许任意转发者在收到来自上游节点的beacon控制包后就可以预先向下游节点发送beacon控制包.文中发现采用机会式广播传输模型能够减少广播总能耗,但是可能会带来平均端到端广播延迟的增加.当前的许多现有工作考虑了延迟约束下的广播能耗优化问题,尽管如此,很多实际应用通常并不需要广播延迟一定要约束在一个限定的范围内,更多的广播应用关注的是能耗与延迟性能的权衡.该文定义了一个具有普适性的广播代价函数,该函数能够对广播延迟和广播能耗两者的权衡关系提供一个自适应的控制以刻画各种不同的广播性能需求,该文的目标是在低占空比传感网中基于机会式广播传输模型找到一个有效的广播调度,以最小化该广播代价函数.首先,文中考虑了单跳情形下的目标问题,并且提出了一个多项式时间复杂度的最优解决方法.接着,文中将单跳情形下的解决方法扩展到多跳情形下.具体地说,我们先定义了一个约束性最小代价单跳广播问题,并且证明了该问题可以在多项式时间内利用动态规划算法求出最优解,然后文中将其扩展到多跳情形下的目标问题并且提出了一个高效的自底向上的解决方法.文中发现通过自适应地调节广播代价函数中权衡因子参数的值,文中的方法可以适用于各种广播性能需求的应用场景.进一步地,该文还讨论了如何将我们提出的解决方法扩展到更加一般化的情形下,即允许少部分相邻节点具有相同的工作调度.仿真实验结果表明在低占空比的网络环境下,文中的解决方法相比较于其它方法而言总是能够获得较大的性能优势.

An Efficient Broadcast Scheduling Algorithm with Adaptive Performance Requirements for Low Duty Cycle Sensor Networks

XU Li-Jie;YANG Geng;XU Jia;WANG Lei;CHEN Gui-Hai(School of Computer Science, Nanjing University of Posts and Telecommunications, Nanjing 210023;Jiangsu Key Laboratory of Big Data Security & Intelligent Processing, Nanjing University of Posts and Telecommunications, Nanjing 210023;State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210023)