基于相继干扰消除的无线传感网低时延广播算法

作     者：焦贤龙 王刚 田海琛 董周 冯新喜 陈桂茸 JIAO Xian-Long;WANG Gang;TIAN Hai-Chen;DONG Zhou;FENG Xin-Xi;CHEN Gui-Rong

作者机构：空军工程大学信息与导航学院 

基　　金：国家自然科学基金(61573017,61402510) 中国博士后科学基金(2014M553686)资助~~ 

出 版 物：《计算机学报》 (Chinese Journal of Computers)

年 卷 期：2019年第42卷第11期

页      码：2526-2538页

摘      要：近年来,传感器技术、嵌入式计算技术与通信技术迅猛发展且日益成熟,因此传感器节点日益小型化和智能化,促进了无线传感网在战场监视、智能交通、精准农业、建筑结构健康状况监测、灾难恢复、环境监控、医疗监护等军用和民用领域的广泛应用.广播的目的是将数据从源节点分发给网络中的所有节点,在无线传感网中主要用于路由发现和重要通知的发布等.无线传感网应用于战场情报获取或火灾监控等时延敏感领域时,需要将数据快速地从源节点广播给全网所有传感器节点,因此,设计一种低时延的广播算法具有非常重要的理论研究意义和实际应用价值.但是,由于无线信号传输的广播特性,节点的信号传输会对其干扰范围内所有节点的数据接收产生干扰,而信号干扰是影响广播时延的重要因素.在信号干扰约束下的最低时延广播问题是NP(Non-Polynomial)难问题,因此难以设计出多项式时间的最优化算法.现有研究工作通常通过干扰避免调度方法来设计低时延的广播算法,虽然能避免信号之间的干扰,但是不能增加可并发传输的广播链路数目,进而有效地降低广播时延.为了有效地解决该问题,本文首先设计了一种贪婪广播算法GreedyB.该算法通过构造宽度优先搜索树来实现网络节点的分层,依据覆盖节点数最多优先选为父节点的规则来构造广播树,最后采用逐层调度和干扰避免调度的方式来分配广播链路的传输时间片.在贪婪广播算法GreedyB的基础上,本文结合相继干扰消除技术设计了另一种广播算法SICB,致力于进一步降低广播时延.与GreedyB算法不同,SICB算法在分配传输时间片时,分析广播链路之间是否满足相继干扰消除的条件,条件满足时安排在同一时间片,不满足时进行干扰避免调度.本文通过理论分析证明了,GreedyB和SICB两种算法都能提供正确的无信号干扰的广播调度方案,并且两种算法时间复杂度和空间复杂度都是多项式时间的.本文通过大量的仿真实验对所提算法进行了性能分析.仿真实验结果表明,GreedyB和SICB两种算法在不同网络规模、最大传输距离、信号传输功率、噪声功率等网络参数下的广播时延都要低于现有的广播算法,性能优化率最高分别可达43.5%和52.7%.

主 题 词：无线传感网 广播算法 干扰避免调度 相继干扰消除 链路调度 时间片分配 

学科分类：0810[工学-土木类] 0808[工学-自动化类] 0839[0839] 08[工学] 0835[0835] 0811[工学-水利类] 081201[081201] 0812[工学-测绘类] 

核心收录：

D　O　I：10.11897/SP.J.1016.2019.02526

馆 藏 号：203822935...