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

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

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

Low duty cycle mode is widely employed in wireless sensor networks,such mode greatly reduces the energy waste caused by idle listening.However,it brings many new challenges for broadcast problem in wireless sensor networks.This paper mainly focuses on how to address the efficient broadcast scheduling problem for low duty cycle sensor networks.Most of the existing works usually adopt the inefficient traditional broadcasting transmission model,in which any local single-hop broadcast is realized by multiple unicasts.Actually,we can see that even for low duty cycle networks,the broadcast nature of wireless media still offers potential chances to improve the energy efficiency of broadcasting.This paper proposes a novel opportunistic broadcasting transmission model,which can make full use of the inherent broadcast nature of wireless media to reduce the total energy consumption for broadcasting.For single-hop cases,specifically,such model allows the sender to send the beacon packet,which is a short control packet,to any of its receivers.The beacon packet will notify the receiver of the deferred time of the wake-up slot,so that the receiver can opportunistically receive the broadcasting message which is sent from the forwarder to some other node.For multiple-hop cases,such model adopts an efficient pre-beacon scheme,which allows any forwarder to send the beacon packet to any of its receivers once the forwarder receives a beacon packet.We find that the opportunistic broadcasting transmission model can reduce the total energy consumption for broadcasting,but could increase the average end-to-end broadcasting delay.Currently,many existing works have investigated the energy optimization problem for broadcasting under delay constraints.However,it is usually unnecessary to require that the broadcast should be done within a bounded delay for many real applications.More broadcasting applications focus on the tradeoff between delay and energy.This paper defines a generalized broadcasting cost function,which can provide a flexible control on the tradeoff between delay and energy,to adaptively meet various broadcasting performance requirements.In this paper,our target problem is how to employ the opportunistic broadcasting transmission model to design an efficient broadcasting schedule for low duty cycle wireless sensor networks,so that the broadcasting cost function is minimized.First,we consider our target problem for single-hop cases,and propose an optimal solution in polynomial time.Afterwards,we extend the solution for single-hop cases to multi-hop cases.Specifically,we first define a constrained minimum cost single-hop broadcast problem,which is solvable in polynomial time by adopting a dynamic programming algorithm,then extend it to our target problem for multi-hop cases and come up with an efficient bottom-up solution.We can find that our solution can be available for applications with various performance requirements by adjusting the tradeoff factor parameter in the broadcasting cost function.Further,this paper discusses how to extend our solution to the general case where a few of the neighboring nodes could have the identical working schedule.Simulation results show that our proposed solution always significantly outperforms the other solutions for various low duty cycle network configurations.