论文部分内容阅读
[摘 要]无线传感器网络是由大量随机部署在监测区域的微小传感器节点通过无线通信、自组织方式构成的分布式网络系统，一般用于对人类无法到达的区域或环境进行监测，并将采集的信息传送给远方的监测者，由监测者根据得到的信息进行分析，从而了解监测区域或环境的情况。
[关键词]无线传感器 网络 分簇算法
中图分类号：IDl63 文献标识码：A 文章编号：1009-914X（2014）41-0339-01
绪 论
1.1 选题背景及意义
随着片上体系、微机电系统、无线通信系统和嵌入式技术的蓬勃发展，无线传感器网络（Wireless Sensor Networks，WSN）作为一种新兴网络随即出现，使得网络技术的发展进入了信息感知的时代。20世纪90年代开始了对无线传感器网络的研究，它具有功耗低、成本低、分布式以及自组织的特性，与之相关的技术有数据库技术、分布式信息处理技术、无线通信技术、嵌入式计算技术等。无线传感器网络在军事战场、抗灾、环境保护、国家安全、医疗护理、商业和智能家居等众多领域都有着广泛的应用。
传感器网络、通信技术以及计算机技术是信息技术的三大中坚力量，具有数据采集、处理和传输的作用。传感器网络和传统无线ad hoc自组织网络在很多地方有着共同的特点。但是两者相比较而言，无线传感器网络具有下述特性：
1）无线传感器网络的节点数量在一定程度上远远多于ad hoc网络。为了对某一区域进行监测，通常要将大量的传感器节点布置在被监测区域。传感器节点集中，一般利用节点之间的高连接性来确保系统的抵抗毁坏的程度，检查在故障存在的情况下计算机系统不失效是否能够正常工作的特性。传感器节点大多在比较恶劣的外部环境下工作，由于节点电池能容量的限制，传感器节点很容易由于能量的耗尽而失去作用。
2）在无线传感器网络中，节点之间往往以广播的形式进行通信，但在ad hoc网络中，节点关键依靠着端到端的传送地址唯一的通信。由于价格、硬件体积、功耗等条件的限定，传感器节点的计算功能和信号管理能力较弱。
3）在无线传感器网络中，节点仅仅能与之相邻的节点直接通信。与其射频覆盖范围之外的节点进行数据通信时，则需要通过其他网络节点作为媒介实施路由。无线传感器网络中没有特定的路由装置，多跳路由仅通过网络中传感器节点来实现，。
4） 无线传感器网络节点常常被安置在环境条件差或无人区域内，由于物理条件的限制，网络中节点能量往往由电池供给，当电池能量受到约束时，则网络中断正常运行。
由于传感器网络节点的能量限制，我们对传感器网络中的节点进行分簇，这样可减小网络中存在传输冲突的概率，尽最大程度降低节点损耗，增强网络的延展性，增加整体网络的生存周期。在簇结构下，算法仅在一个簇范畴内施行不用等待控制消息传输整个网络体系，在大型网络中，相比在整个结构中施行的中心化算法而言，这种细节化算法具有更好的扩充性。在信息传播与数据有效查询中分簇算法的研究同样具有重要意义，簇头能在簇内辅助传播信息并收集相关数据。分簇算法能够将数据融入在一起，将无线传感器节点感知监测到的数据融合处理，得到有效准确的数据信息。
1.2 国内外研究现状
无线传感器网络（Wireless Sensor Networks， WSNs）作为物联网（Internet of Things， IoT）主要的支撑技术之一，改变了信息的获取和处理方式，在研究和应用领域获得了广泛关注。，20世纪70年代出现了第一代传感器网络，使用具有简单信息信号获取能力的传统传感器节点，采用点对点传输方式、连接传感控制器构成传感器网络；第二代传感器网络，具有获取多种信息信号的综合能力，采用串、并接口与传感控制器相联，构成有综合多种信息能力的传感器网络；20世纪90年代后期和本世纪初出现第三代传感器网络，采用具有智能获取多种信息信号的传感器节点，现场总线连接传感控制器，构成局域网络、智能化传感器网络；第四代传感器网络正在研究开发中，目前成形并大量投入使用的产品尚未出现。用大量的具有多功能多信息信号获取能力的传感器节点，采用自组织无线接入方式，与传感器网络控制器连接，构成无线传感器网络。
我国对无线传感器网络的运用探讨与发达国家几乎同步进行，1999年中国科学院《知识创新工程试点领域方向研究》的“信息与自动化领域研究报告”中首次正式出现，为该领域提出的五个重大项目之一。上海微系统所、声学所、微电子所、半导体所、电子所、软件以及中国科技大学等研究机构为系统研究与发展中心在无线传感器网络趋势上逐渐安排了若干重大研究项目。经过研究人员不懈的努力，我国初步成立了传感器网络系统的研究平台，在无线智能传感器网络通信技术、微型传感器、传感器端机、移动基站和应用系统等方面获得了重大进步。研究者在学习借鉴国外WSN研究经验精华的基础上，提出并处理着新的发现与问题。从网络拓扑结构的角度可以大体上把路由协议为两类：一类为平面路由协议，平面路由中所有节点的地位相等，优点是简单，容易扩充，不需保护，缺点是没有管理节点，网络通信不能被很好得细致管理。另一类为层次路由协议。网络一般情况下划分为簇，即具有某种联系的网络节点总和。
1.3 研究内容
分簇算法是一种层次路由协议，与普通的层次路由不同，它探求更多的是节点聚类和数据融合。目前分簇算法的研究主要包括以下几个方面：
1）分簇的理论基础：研究焦点在于簇首的选择问题，目前提出的分簇算法基本可以分为三类。第一种是以LEACH为代表的基于概率的分簇算法，这类算法不考虑节点的能量和网络整体的特征，算法的稳定性较差。在随机的网络中，算法的效率相对较低；第二种是考虑节点功能函数的分簇算法，例如HEED，它考虑节点充当簇首的最小能量约束，因此算法的执行效率比LEACH明显提高；第三种是以节点特征为约束的分簇算法，这类算法包括节点度、权值、能效函数、地理位置等为基础的分簇算法。
2）簇头的选取和簇的形成：簇头的选取和簇的形成是分簇算法的重点。簇头选取应尽量选取具有较大剩余能量和较强通信能力的节点，从而使簇头能够更好地进行簇内的管理和簇间信息的交互。
3）簇头的轮换：由于在某些同构网络应用中，簇头节点和成员节点的通信能力和能量是一样的。而簇头节点又要承担比普通成员节点更多的工作，为了使簇头节点不会因负载过重而导致能量耗尽，需要定期地轮换簇首节点。
4）均衡网络负载：在无线传感器网络中，由于被探测事件发生和数据传输存在区域性，从而有可能造成某区域内节点能量过早耗尽。簇头节点相对普通节点能够承担更多的工作，因此利用分簇來达到网络负载均衡是提高网络数据传输能力一个有效措施。
5）提高网络容错能力：在多数应用中，WSNs的工作环境非常恶劣，传感器节点具有随时移动性，网络中节点死亡率较高，容易导致通信链路失效，链路间存在通信干扰等问题。因此如何在网络中保证数据传输的可靠性以及如何在链路失效后快速有效地对链路进行修复成为分簇算法研究的重点之一。
6）最优成簇数目：簇的形成主要解决如何在动态分布式网络环境下使节点高效地聚集成簇，它是分簇算法的关键。在传感器网络中，如果簇的数目过多将会使簇内以及簇间通信发生冲突的几率大大增加。因此，通过减少网络中分簇的数量，降低簇间的重叠，能够有效提高网络的通信质量。
7）延长网络生存周期：由于受成本和物理环境的限制，目前传感器节点一般都是采用电池供电的方式获取能源，受到节点有限能量的限制。而对于绝大多数应用来说，给大规模的传感器节点更换电池是不现实的。因为传感器节点常被安装在不可回收的位置，比如传感器节点被嵌入到墙体内部或者被撒布到遥远的区域。
通过对网络中未分簇节点的合并和冗余簇的合并，降低簇间重叠，使网络中的簇拓扑结构更加合理。我们还提出了一些如何防止在合并过程中出现冲突的策略。仿真结果表明，我们的算法能够有效降低网络中冗余簇的数量，显著减少簇内重叠区域。
[关键词]无线传感器 网络 分簇算法
中图分类号：IDl63 文献标识码：A 文章编号：1009-914X（2014）41-0339-01
绪 论
1.1 选题背景及意义
随着片上体系、微机电系统、无线通信系统和嵌入式技术的蓬勃发展，无线传感器网络（Wireless Sensor Networks，WSN）作为一种新兴网络随即出现，使得网络技术的发展进入了信息感知的时代。20世纪90年代开始了对无线传感器网络的研究，它具有功耗低、成本低、分布式以及自组织的特性，与之相关的技术有数据库技术、分布式信息处理技术、无线通信技术、嵌入式计算技术等。无线传感器网络在军事战场、抗灾、环境保护、国家安全、医疗护理、商业和智能家居等众多领域都有着广泛的应用。
传感器网络、通信技术以及计算机技术是信息技术的三大中坚力量，具有数据采集、处理和传输的作用。传感器网络和传统无线ad hoc自组织网络在很多地方有着共同的特点。但是两者相比较而言，无线传感器网络具有下述特性：
1）无线传感器网络的节点数量在一定程度上远远多于ad hoc网络。为了对某一区域进行监测，通常要将大量的传感器节点布置在被监测区域。传感器节点集中，一般利用节点之间的高连接性来确保系统的抵抗毁坏的程度，检查在故障存在的情况下计算机系统不失效是否能够正常工作的特性。传感器节点大多在比较恶劣的外部环境下工作，由于节点电池能容量的限制，传感器节点很容易由于能量的耗尽而失去作用。
2）在无线传感器网络中，节点之间往往以广播的形式进行通信，但在ad hoc网络中，节点关键依靠着端到端的传送地址唯一的通信。由于价格、硬件体积、功耗等条件的限定，传感器节点的计算功能和信号管理能力较弱。
3）在无线传感器网络中，节点仅仅能与之相邻的节点直接通信。与其射频覆盖范围之外的节点进行数据通信时，则需要通过其他网络节点作为媒介实施路由。无线传感器网络中没有特定的路由装置，多跳路由仅通过网络中传感器节点来实现，。
4） 无线传感器网络节点常常被安置在环境条件差或无人区域内，由于物理条件的限制，网络中节点能量往往由电池供给，当电池能量受到约束时，则网络中断正常运行。
由于传感器网络节点的能量限制，我们对传感器网络中的节点进行分簇，这样可减小网络中存在传输冲突的概率，尽最大程度降低节点损耗，增强网络的延展性，增加整体网络的生存周期。在簇结构下，算法仅在一个簇范畴内施行不用等待控制消息传输整个网络体系，在大型网络中，相比在整个结构中施行的中心化算法而言，这种细节化算法具有更好的扩充性。在信息传播与数据有效查询中分簇算法的研究同样具有重要意义，簇头能在簇内辅助传播信息并收集相关数据。分簇算法能够将数据融入在一起，将无线传感器节点感知监测到的数据融合处理，得到有效准确的数据信息。
1.2 国内外研究现状
无线传感器网络（Wireless Sensor Networks， WSNs）作为物联网（Internet of Things， IoT）主要的支撑技术之一，改变了信息的获取和处理方式，在研究和应用领域获得了广泛关注。，20世纪70年代出现了第一代传感器网络，使用具有简单信息信号获取能力的传统传感器节点，采用点对点传输方式、连接传感控制器构成传感器网络；第二代传感器网络，具有获取多种信息信号的综合能力，采用串、并接口与传感控制器相联，构成有综合多种信息能力的传感器网络；20世纪90年代后期和本世纪初出现第三代传感器网络，采用具有智能获取多种信息信号的传感器节点，现场总线连接传感控制器，构成局域网络、智能化传感器网络；第四代传感器网络正在研究开发中，目前成形并大量投入使用的产品尚未出现。用大量的具有多功能多信息信号获取能力的传感器节点，采用自组织无线接入方式，与传感器网络控制器连接，构成无线传感器网络。
我国对无线传感器网络的运用探讨与发达国家几乎同步进行，1999年中国科学院《知识创新工程试点领域方向研究》的“信息与自动化领域研究报告”中首次正式出现，为该领域提出的五个重大项目之一。上海微系统所、声学所、微电子所、半导体所、电子所、软件以及中国科技大学等研究机构为系统研究与发展中心在无线传感器网络趋势上逐渐安排了若干重大研究项目。经过研究人员不懈的努力，我国初步成立了传感器网络系统的研究平台，在无线智能传感器网络通信技术、微型传感器、传感器端机、移动基站和应用系统等方面获得了重大进步。研究者在学习借鉴国外WSN研究经验精华的基础上，提出并处理着新的发现与问题。从网络拓扑结构的角度可以大体上把路由协议为两类：一类为平面路由协议，平面路由中所有节点的地位相等，优点是简单，容易扩充，不需保护，缺点是没有管理节点，网络通信不能被很好得细致管理。另一类为层次路由协议。网络一般情况下划分为簇，即具有某种联系的网络节点总和。
1.3 研究内容
分簇算法是一种层次路由协议，与普通的层次路由不同，它探求更多的是节点聚类和数据融合。目前分簇算法的研究主要包括以下几个方面：
1）分簇的理论基础：研究焦点在于簇首的选择问题，目前提出的分簇算法基本可以分为三类。第一种是以LEACH为代表的基于概率的分簇算法，这类算法不考虑节点的能量和网络整体的特征，算法的稳定性较差。在随机的网络中，算法的效率相对较低；第二种是考虑节点功能函数的分簇算法，例如HEED，它考虑节点充当簇首的最小能量约束，因此算法的执行效率比LEACH明显提高；第三种是以节点特征为约束的分簇算法，这类算法包括节点度、权值、能效函数、地理位置等为基础的分簇算法。
2）簇头的选取和簇的形成：簇头的选取和簇的形成是分簇算法的重点。簇头选取应尽量选取具有较大剩余能量和较强通信能力的节点，从而使簇头能够更好地进行簇内的管理和簇间信息的交互。
3）簇头的轮换：由于在某些同构网络应用中，簇头节点和成员节点的通信能力和能量是一样的。而簇头节点又要承担比普通成员节点更多的工作，为了使簇头节点不会因负载过重而导致能量耗尽，需要定期地轮换簇首节点。
4）均衡网络负载：在无线传感器网络中，由于被探测事件发生和数据传输存在区域性，从而有可能造成某区域内节点能量过早耗尽。簇头节点相对普通节点能够承担更多的工作，因此利用分簇來达到网络负载均衡是提高网络数据传输能力一个有效措施。
5）提高网络容错能力：在多数应用中，WSNs的工作环境非常恶劣，传感器节点具有随时移动性，网络中节点死亡率较高，容易导致通信链路失效，链路间存在通信干扰等问题。因此如何在网络中保证数据传输的可靠性以及如何在链路失效后快速有效地对链路进行修复成为分簇算法研究的重点之一。
6）最优成簇数目：簇的形成主要解决如何在动态分布式网络环境下使节点高效地聚集成簇，它是分簇算法的关键。在传感器网络中，如果簇的数目过多将会使簇内以及簇间通信发生冲突的几率大大增加。因此，通过减少网络中分簇的数量，降低簇间的重叠，能够有效提高网络的通信质量。
7）延长网络生存周期：由于受成本和物理环境的限制，目前传感器节点一般都是采用电池供电的方式获取能源，受到节点有限能量的限制。而对于绝大多数应用来说，给大规模的传感器节点更换电池是不现实的。因为传感器节点常被安装在不可回收的位置，比如传感器节点被嵌入到墙体内部或者被撒布到遥远的区域。
通过对网络中未分簇节点的合并和冗余簇的合并，降低簇间重叠，使网络中的簇拓扑结构更加合理。我们还提出了一些如何防止在合并过程中出现冲突的策略。仿真结果表明，我们的算法能够有效降低网络中冗余簇的数量，显著减少簇内重叠区域。