一种基于广度优先生成树的无线传感器网络自保护算法  

Breadth-first Spanning Tree-based Algorithm for Self-protection in Wireless Sensor Networks

作　　者：张文哲[1] 李蓥[1] 

机构地区：[1]苏州大学计算机科学与技术学院江苏省计算机信息处理省重点实验室,江苏苏州215006

出　　处：《小型微型计算机系统》2014年第10期2193-2198,共6页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(61070169)资助;江苏省高校自然科学研究计划项目(10KJB520017)资助

摘　　要：从无线传感器网络中选取部分节点作为保护节点,为网络提供保护称为无线传感器网络的自保护.前人已经证明自保护问题是NP-完全问题.提出一种基于广度优先生成树的自保护算法,可以高效地分布式地选择保护节点.我们首先为自保护问题建模,其次提出了分布式的标记过程,不同于前人工作的是,在保持较小保护节点集合的基础上,我们还保持了保护节点的连通性,使得紧急消息到网关的平均汇报跳数最少,这一特点使得本文算法更加合理可行,从而提高了区域监控应用中传感器网络性能.仿真实验证明,本文算法可行性和有效性.The self-protection problem focuses on using the sensor nodes of the network to protect themselves rather than other objects so that the network can resist attacks. The self-protection set has been proved to be an NP complete problem. In this paper, we propose a new breadth-first spanning tree-based approximation algorithm to find a self-protection set. We model the self-protection problem, and propose a distributed marking algorithm based on Breadth-First Spanning Tree. Different from previous works,we not only main- tain the connectivity of all dominating sensors but achieve the minimum hops of urgent message to gateway. This makes the method proposed more practical and sensible and improve the performance of wireless sensor networks substantially. Experimental result mani- fests the efficiency and feasibility of our algorithms proposed.

关 键 词：无线传感器网络 自保护 广度优先生成树 分层 标记 

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