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

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

作　　者：徐力杰[1,2,3] 杨庚 徐佳[1,2] 王磊[1,2] 陈贵海[3] 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)

机构地区：[1]南京邮电大学计算机学院软件学院网络空间安全学院,南京210023 [2]南京邮电大学江苏省大数据安全与智能处理重点实验室,南京210023 [3]南京大学计算机软件新技术国家重点实验室,南京210023

出　　处：《计算机学报》2019年第2期368-387,共20页Chinese Journal of Computers

基　　金：国家自然科学基金(61502251;61572263;61472193);中国博士后科学基金(2016M601859);江苏省博士后科研资助计划(1701047A);江苏省自然科学基金(BK20141429);南京邮电大学引进人才科研启动基金(NY214169)资助~~

摘　　要：无线传感器网络中的节点普遍采用低占空比的工作模式,该工作模式极大地减少了由于空闲侦听所带来的能量浪费,但也给网络中的广播问题带来了新的挑战.该文主要考虑如何解决低占空比传感网中的高效广播调度问题.大多数现有工作通常采用低效的传统广播传输模型,即任意局部单跳广播通过多次单播来实现.实际上,文中发现即使对于低占空比网络,无线媒介的广播属性依然能够为广播能效的提升提供潜在的机会.该文提出了一个新颖的机会式广播传输模型,该模型能够充分利用无线媒介固有的广播属性减少广播的总能耗.在单跳情形下,该模型允许发送者向它的任意接收者发送一个较小的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

关 键 词：无线传感器网络 低占空比 广播调度 自适应性能需求 机会式广播传输模型 自底向上的解决方法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]