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

Successive Interference Cancellation Based Low-Delay Broadcast Algorithms for Wireless Sensor Networks

作　　者：焦贤龙[1] 王刚[1] 田海琛 董周 冯新喜[1] 陈桂茸[1] JIAO Xian-Long;WANG Gang;TIAN Hai-Chen;DONG Zhou;FENG Xin-Xi;CHEN Gui-Rong(Information and Navigation College,Air Force Engineering University,Xi’an 710077)

机构地区：[1]空军工程大学信息与导航学院

出　　处：《计算机学报》2019年第11期2526-2538,共13页Chinese Journal of Computers

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

摘　　要：近年来,传感器技术、嵌入式计算技术与通信技术迅猛发展且日益成熟,因此传感器节点日益小型化和智能化,促进了无线传感网在战场监视、智能交通、精准农业、建筑结构健康状况监测、灾难恢复、环境监控、医疗监护等军用和民用领域的广泛应用.广播的目的是将数据从源节点分发给网络中的所有节点,在无线传感网中主要用于路由发现和重要通知的发布等.无线传感网应用于战场情报获取或火灾监控等时延敏感领域时,需要将数据快速地从源节点广播给全网所有传感器节点,因此,设计一种低时延的广播算法具有非常重要的理论研究意义和实际应用价值.但是,由于无线信号传输的广播特性,节点的信号传输会对其干扰范围内所有节点的数据接收产生干扰,而信号干扰是影响广播时延的重要因素.在信号干扰约束下的最低时延广播问题是NP(Non-Polynomial)难问题,因此难以设计出多项式时间的最优化算法.现有研究工作通常通过干扰避免调度方法来设计低时延的广播算法,虽然能避免信号之间的干扰,但是不能增加可并发传输的广播链路数目,进而有效地降低广播时延.为了有效地解决该问题,本文首先设计了一种贪婪广播算法GreedyB.该算法通过构造宽度优先搜索树来实现网络节点的分层,依据覆盖节点数最多优先选为父节点的规则来构造广播树,最后采用逐层调度和干扰避免调度的方式来分配广播链路的传输时间片.在贪婪广播算法GreedyB的基础上,本文结合相继干扰消除技术设计了另一种广播算法SICB,致力于进一步降低广播时延.与GreedyB算法不同,SICB算法在分配传输时间片时,分析广播链路之间是否满足相继干扰消除的条件,条件满足时安排在同一时间片,不满足时进行干扰避免调度.本文通过理论分析证明了,GreedyB和SICB两种算法都能提供正确的无信号干扰的广In recent years,the rapid development and maturity of sensor technology,embedded computing technology and communication technology,along with the growing miniaturization and intellectualization of sensor nodes have promoted the wide application of wireless sensor network in military and civil fields,such as battlefield surveillance,intelligent transportation,precision agriculture,health monitoring of building structures,disaster recovery,environmental monitoring,and medical monitoring,etc.The purpose of broadcast is to distribute data from the source node to all the sensor nodes in the network,which is mainly used for routing discovery and important announcement in wireless sensor networks.When wireless sensor networks are used in the delay-sensitive fields,such as battlefield information acquisition or fire monitoring,the data need to be quickly broadcast from the source node to all the sensor nodes in the whole network.Therefore,designing low-delay broadcast algorithms has very great theoretical research significance and practical application value.However,because of the broadcast characteristics of wireless signal transmission,the signal transmission of nodes will interfere with the data reception of all nodes within the interference range,and signal interference is an important factor that affects broadcast delay.The minimum-delay broadcast problem under the constraint of signal interference is NP(Non-Polynomial)-hard,and it is difficult to design a polynomial-time optimal algorithm.Existing research work usually designs low-delay broadcast algorithms by using the interference avoidance scheduling method.Although these algorithms can avoid interference between signals,these algorithms cannot increase the number of broadcast links that can transmit concurrently,and thus cannot effectively reduce the broadcast delay.In order to solve this problem effectively,a greedy broadcast algorithm called GreedyB is first designed.The GreedyB algorithm layers the network nodes by constructing the breadth first search tree.

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

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