论文部分内容阅读
无线传感器网络(Wireless Sensor Network, WSN)是21世纪极具应用价值的新兴学科之一。通过WSN人们可以即时监控,收集并分析WSN监测区域内监测对象的各种有效信息,并可将有效信息通过WIFI、 GPRS、移动数据网络等多种方式传送到任务管理节点,以此达到对监测目标情况变化的实时监控与及时报警。WSN具有易于布置、监控区域广和环境适应力强等特点,如今,无论在军事、商用还是民用领域,WSN技术都受到越来越多的重视,而有效地构造WSN的虚拟骨干网(Virtual-Backbone)则是当今WSN领域的一个热点研究课题。因为WSN传感器节点体积小,分布范围广,所以对传感器节点的管理和维护十分困难,构造一个高效的虚拟骨干网,可以从软件方面延长网络的生存时间,降低维护成本。本文通过求解性能最优的连通支配集(Connected Dominating Set,CDS)来构造虚拟骨干网。最小连通支配集的求取已经被证明是NP完全问题,现在最通用的手段是通过启发式的方法求得最优解。求取连通支配集的算法主要分为集中式和分布式两种,因为WSN的动态性特点,集中式算法难以适应网络的实时变化,故多采用分布式的求取算法。本文提出了两个优化的分布式CDS求解算法：MI-LCDS (Multi-Initiator Layer Based CDS Construction Algorithm)算法和FNDB (A Forward1-hop neighbor Information set Based Distributed algorithm for Virtual Backbone)算法。MI-LCDS算法提出了基于多发起者的网络分层模型,首先根据网络的规模选取数个源节点,源节点独立地进行各自区域范围内的网络划分,得到分层结构,网络各层分布式地求取本层的CDS。最后,不同源节点的CDS通过桥梁节点连通,完成整个网络CDS的构造。MI-LCDS算法的时间复杂度为O(△2),其中△为节点的平均度。FNDB算法只需一跳邻居节点信息,在成功求取节点的边界交点集后,再推导出其转发集,通过染色法在转发集中求出支配节点来构造一个CDS。仿真结果表明,FNDB算法产生的额外消息数约等于CDS的大小,而收敛时间约等于WSN的网络直径。