《传感器网络中基于leach算法的改进分簇模型研究毕业设计论文》由会员分享,可在线阅读,更多相关《传感器网络中基于leach算法的改进分簇模型研究毕业设计论文(47页珍藏版)》请在金锄头文库上搜索。
1、湖南大学毕业论文 HUNAN UNIVERSITY毕业设计(论文)设计论文题目:传感器网络中基于LEACH算法的改进分簇模型研究学生姓名:学生学号:专业班级:学院名称:指导老师:学院院长:湖南大学毕业论文 第 20 页传感器网络中基于LEACH算法的改进分簇模型研究摘 要无线传感器网络是众多的传感器通过无线通信的方式,相互联系,处理、传递信息的网络。该网络综合了传感器技术、嵌入式计算技术、分布式信息处理技术和通信技术,可以实时监测、感知和采集网络分布区域内的各种对象的信息,并对这些信息进行处理,传送给所需用户。无线传感器网络在军事、工业、交通、安全、医疗、探测以及家庭和办公环境等很多方面都有着
2、广泛的用途,其研究、开发和应用,关系到国家安全、经济发展的各个方面,近年来在国际上引起了广泛的重视和投入。由于外界环境的不确定性,经常导致需要部署成百上千的传感器协同工作,故对由大量传感器构成的大规模传感器网络的研究正逐渐引起关注,并被认为是本世纪的一项具有挑战性的研究课题。目前,学术界的研究热点主要集中在传感器网络分簇算法、通信路由协议、网络覆盖等领域。LEACH算法是一种典型的层次路由算法,该算法提出了低功耗持续运行的模型。但LEACH算法也存在没有考虑能量的消耗和传感器拓扑结构的问题。本文提出了一种传感器网络中能量有效的分簇算法,该算法在经典的分簇算法LEACH的基础上,通过引入平均能耗
3、调节参数和密度调节参数,使得靠近簇结构地理中心位置的节点以及位于节点密集分布区域的节点有更高机率成为簇头。采用该算法时,传感器网络簇头的选取更为合理,从而进一步优化了簇的结构,均衡了网络的能量消耗,与采用LEACH算法相比,传感器网络的生命周期有一定幅度的延长。 关键词:传感器网络;分簇算法;平均能耗;节点密度LEACH-based Improved clustering model Research in the Sensor NetworkAbstractWireless sensor networks are a kind of network which a lot of sensor
4、s interrelate, process and transmit information with each other through wireless communications. The network integrates sensor technology, embedded computing technology, distributed information processing and communication technology which can be real-time monitoring, sensing and acquisition the inf
5、ormation of various environmental monitoring or targeting object within regional of distribution networks. Such information will be processed and transmitted to the user. Wireless sensor networks are widely used in military, industrial, transportation, security, medical, detection, family and office
6、 environment. The research, development and application of it relates to national security, economic development and other important fields. In recent years the wireless sensor networks have been caused much attention and investment. External uncertainty environment often leads to hundreds of sensor
7、s shall be deploymented to work together, so the large-scale sensor networks research is gradually aroused widespread interest and considered a challenging research topic of this century. Against the above problems, the academic research mainly concentrated in the sensor clustering algorithm, commun
8、ications routing protocols, network coverage and sensor data fusion technology.LEACH algorithm is a typical level routing algorithm. This algorithm put forward a continued operation of low-power model. But LEACH algorithm did not consider the problem of energy consumption and topology of the sensor.
9、 This paper presents an energy efficient clustering algorithm in sensor network. On the basis of the classical LEACH algorithm, through the introduction of average energy consumption adjustable parameters and density adjustment parameters. The new algorithm enable the nodes which near the geographic
10、 center of the cluster structure or in the node-intensive region has a higher probability to be a cluster head. And it also takes into account both the choice of the cluster heads location and the size of the network, then further optimizes the structure of the cluster, balances energy consumption,
11、elects more reasonable cluster head which makes the life cycle of sensor networks has a larger extension on the basis of in LEACH algorithm.Key Words: Sensor networks; Clustering Algorithms; The average energy consumption; Node Density目 录1. 绪论11.1 课题研究背景与意义11.2 国内外研究现状21.3论文结构和研究内容31.4 小结32. 传感器网络概述
12、42.1 传感器网络简介42.1.1 传感器网络的概念42.1.2 传感器网络的特点52.1.3 传感器网络的核心技术62.2 传感器网络的应用62.2.1 环境的检测和保护62.2.2 医疗护理72.2.3 其他应用72.3传感器网络的特点与挑战82.4小结93. LEACH算法简介及分析103.1引言103.2 LEACH算法103.3 LEACH算法中存在的问题分析123.3.1 未考虑簇头在簇结构中位置时存在的问题123.3.2 频繁动态拓扑变换带来的问题153.4 小结164. 能量有效的分布式簇头选取算法174.1引言174.2 EECHS算法174.3算法性能分析184.4小结2
13、05. 算法仿真实验215.1实验平台215.2实验设计215.3实验过程225.4实验结果245.5小结26结 论27致 谢29参考文献30附录A 部分源程序321. 绪论1.1 课题研究背景与意义随着通讯技术,计算机技术和传感技术的日益成熟,微型传感器在世界范围内广泛出现。传感器网络的发展经历了几个阶段,它最早出现在二十世纪七十年代,这个时期的传感器网络具有点对点的传输能力和简单的信息获取能力。随后便出现了使用串/并接口与传感器连接,可以获取多种信息的传感器网络。到了二十世纪九十年代后期,智能传感器采用现场总线连接形成局域网络。随着无线通讯技术被引入传感器,传感器网络技术的发展和应用发生了
14、革命性的变化,以无线传感器网络为标志的全新的传感器网络研究领域,在基础理论和工程技术两个层面向科技工作者提供了大量的具有挑战性的课题1-6。由于传感器网络的巨大应用价值,它已经引起了世界许多国家的军事部门、工业界和学术界的极大关注。美国自然科学基金委员会2003年制定计划并投巨资支持传感器网络相关基础理论的研究。美国国防部和各军事部门把传感器网络作为一个重要研究领域,设立了一系列的军事传感器网络研究项目7。主要的信息工业界巨头也开始了传感器网络方面的工作,纷纷设立或启动相应的行动计划。其它一些国家也对传感器网络表现出了极大的兴趣,并纷纷展开了在该领域的研究工作。由于传感器网络具有异于MANET
15、的独特性质13,因此传统MANET协议不适用于传感器网络,需要为传感器网络研究新的有效的路由算法。目前,在传感器网络的路由算法研究中,鉴于传感器网络中节点稠密分布、节点的能量、存储及数据处理能力十分有限的特性,一般采用基于分簇的方法来进行路由算法设计,以提高路由算法的性能。分簇算法作为路由协议的研究基础,对路由算法性能的优劣具有重要的影响。此外,在传感器网络中,要保障信息的完整性,数据汇聚节点首先要判定该感兴趣的区域是否被一组给定的传感器节点覆盖,覆盖问题也因此被看作是衡量传感器网络服务质量(Quality Of Service)的一种标准10。而覆盖算法也是以分簇算法为基础进行研究的。由于为
16、改善传感器网络的服务质量而提出的许多覆盖算法是以分簇算法作为其研究基础的,因此分簇算法的改进可以极大的促进覆盖算法的性能。综上所述,本文研究传感器网络中能量有效的分簇算法,具有重要的理论意义与实用价值。1.2 国内外研究现状由于外界环境的不确定性经常导致需要布置成百上千的传感器协同工作,故对由大规模传感器构成的传感器网络的研究正逐渐引起广泛关注,并被认为是本世纪的一向具有挑战性的研究课题。针对以上问题,学术界的研究热点主要集中在传感器分簇算法、通信路由协议、传感器网络覆盖以及传感器数据融合技术上的研究上。传感器分簇算法通常包括两个阶段。第一个阶段是根据一定的机制算法选取某个接点作为簇头,用于管
17、理或控制整个簇内成员节点,协调成员节点之间的工作,负责簇内信息的收集和数据的融合处理以及簇间转发。第二个阶段是在选取簇头的基础上,选取具有某种关联的网络节点形成集合,也就是成簇。在成簇算法中,网络通常被划分为簇(Cluster)。每个簇由一个簇头(Cluster Head)和多个簇内成员(Cluster Member)组成,由簇头与基站BS(Base Station)通信。网络分布如图1所示,图1.1簇集网络示意图1、 簇头选取算法 簇头的产生是簇形成的基础,在一些算法中,比如Max-min Zpmin,簇头是被预先指定部署的,且假设它们的能量并不受限。但这是理想的情况,在实际应用是不可能实现
18、的。更多的簇头选取算法综合考虑了节点的剩余能量,簇头到基站的距离,簇内通信代价等问题。目前提出的主流簇头选取算法有LEACH、LEACH-F、DAEA、HEAD、CEFL、DCHS、DEFG等。2、 成簇算法成簇算法在簇头产生后,形成簇的拓扑结构,将网络划分成相连的区域。良好的簇拓扑结构有助于延长传感器网络的使用周期。目前提出的成簇算法有ACMWN、HYENAS、EECS、PEGASIS、GAF、ACE、FBCC等。1.3 论文结构和研究内容目前,人们基于节能的考虑已提出了各种各样的路由协议,本文对其中的LEACH算法进行分析,主要研究内容如下:(1) 详细分析了LEACH的簇头选取以及成簇算
19、法,并对LEACH在簇头选取和成簇过程中存在的问题进行了说明。(2) 针对LEACH算法在簇头选取过程中没有考虑簇头在簇结构中位置和没有考虑节点实际部署情况而引发的问题,将基于节点平均能耗的簇头选取算法和节点密度数学模型结合起来,提出了能量有效簇头选取算法。(3) 对算法进行仿真实验,并借鉴传感器网络中节能评价指标体系对实验结果进行质量评价,最后本文通过理论分析和大量实验证明了新算法较LEACH算法性能更优越。论文主要由以下部分构成:第一章对本课题背景和国内外研究现状做了描述。第二章对传感器网络的概念以及应用进行介绍。第三章对传统的LEACH算法进行了介绍,并详细分析了其存在的不足。第四章将节
20、点密度模型和平均能耗模型结合起来,进一步对LEACH算法的簇头选取过程进行改进,提出了能量有效的簇头选取算法。第五章对算法进行仿真模拟实验。最后为结论与展望,首先本文工作进行了总结,然后对下一步的研究方向进行了展望。1.4 小结本章首先给出了课题的研究背景与意义、然后综述了国内外传感器网络覆盖判定算法的研究现状、最后,给出了论文的结构和研究内容简介。2. 传感器网络概述2.1 传感器网络简介2.1.1 传感器网络的概念传感器网络是由一组传感器以Ad-Hoc方式构成的有线或无线网络,其目的是协作地感知、采集和处理网络覆盖的地理区域中感知对象的信息,并发布给观察者。从定义可以看出,传感器、感知对象
21、和观察者是传感器网络的3个基本要素;有线或无线网络是传感器之间、传感器与观察者之间的通信方式,用于在传感器与观察者之间建立通信路径;协作地感知、采集、处理、发布感知信息是传感器网络的基本功能。一组功能有限的传感器协作地完成大的感知任务是传感器网络的重要特点。传感器网络中的部分或全部节点可以移动。传感器网络的拓扑结构也会随着节点的移动而不断地动态变化。节点间以Ad-Hoc方式进行通信,每个节点都可以充当路由器的角色,并且每个节点都具备动态搜索、定位和恢复连接的能力。传感器由电源、感知部件、嵌入式处理器、存储器、通信部件和软件这几部分构成(如图2.1所示)。电源为传感器提供正常工作所必需的能源。感
22、知部件用于感知、获取外界的信息,并将其转换为数字信号。处理部件负责协调节点各部分的工作。通信部件负责与其他传感器或观察者的通信。软件则为传感器提供必要的软件支持,如嵌入式操作系统、嵌入式数据库系统等。图2.1 传感器示意图典型的传感器网络由传感器节点、接收发送器(sink)、Internet或通信卫星、任务管理节点等部分构成。传感器节点散布在指定的感知区域内,每个节点都可以收集数据,并通过“多跳”路由方式把数据传送到Sink。Sink也可以用同样的方式将信息发送给各节点。Sink直接与Internet或通信卫星相连,通过Internet或通信卫星实现任务管理节点(即观察者)与传感器之间的通信。
23、图2.2描述了一个典型的传感器网络的结构14。2.2典型的传感器网络的结构2.1.2 传感器网络的特点传感器网络除了具有Ad-Hoc网络的移动性、断接性、电源能力有限等特征外,还具有以下鲜明特点14:(1) 通信能力有限。传感器网络中的传感器的通信带宽较窄而且经常变化,通信覆盖范围只有几十到几百米。传感器之间的通信断接频繁,经常导致通信失败。由于传感器网络更多地受到高山、建筑物、障碍物等地势地貌以及风雨雷电等自然环境的影响,传感器可能会长时间离线工作。(2) 计算能力有限。传感器网络中的传感器都具有嵌入式处理器和存储器。这些传感器都具有计算能力,可以完成一些信息处理工作。但是,由于嵌入式处理器
24、和存储器的能力和容量有限,传感器的计算能力十分有限。使用大量具有有限计算能力的传感器进行协作分布式信息处理,是我们的选择之一。(3) 传感器数量大、分布范围广。传感器网络中传感器节点密集,数量巨大,可能达到几百、几千万,甚至更多。此外,传感器网络可以分布在很广泛的地理区域。传感器的数量与用户数量比通常也非常大。这就要求传感器网络的软、硬件必须具有高强壮性和容错性。(4) 感知数据流巨大。传感器网络中的每个传感器通常都产生较大的流式数据,并具有实时性。每个传感器仅仅具有有限的计算资源,难以处理巨大的实时数据流。这就需要研究强有力的分布式数据流管理、查询、分析和挖掘方法。2.1.3 传感器网络的核
25、心技术以数据为中心的传感器网络的基本思想是:把传感器视为感知数据流或感知数据源,把传感器网络视为感知数据空间或感知数据库,把数据管理和处理作为网络的应用目标。传感器网络以数据为中心的特点使得其设计方法不同于其他计算机网络(包括Internet)。传感器网络的设计必须以感知数据管理和处理为中心,把数据库技术和网络技术紧密结合,从逻辑概念和软、硬件技术两个方面实现一个高性能的以数据为中心的网络系统,为用户或观察者提供一个有效的感知数据空间或感知数据库管理和处理系统,使用户如同使用通常的数据库管理系统和数据处理系统一样自如地在传感器网络上进行感知数据的管理和处理。感知数据管理与处理技术是实现以数据为
26、中心的传感器网络的核心技术17。感知数据管理与处理技术包括感知网络数据的存储、查询、分析、挖掘、理解以及基于感知数据决策和行为的理论和技术。传感器网络的各种实现技术必须与这些技术密切结合,融为一体,而不是像目前其他网络设计那样分而治之。只有这样才能够设计实现高效率的以数据为中心的传感器网络系统。对感知数据管理与处理的研究方向主要包括:感知数据管理技术的研究、感知数据查询处理技术的研究、感知数据分析技术的研究、感知数据挖掘技术的研究以及感知数据管理系统的研究。2.2 传感器网络的应用2.2.1 环境的检测和保护随着人们对于环境问题的关注程度越来越高,需要采集的环境数据也越来越多,无线传感器网络的
27、出现为随机性的研究数据获取提供了便利,并且还可以避免传统数据收集方式给环境带来的侵入式破坏。比如,2002年英特尔研究实验室研究人员曾经将32个小型传感器连进互联网,掌握缅因州大鸭岛上的气候,以此评价一种海燕巢的条件。2003年第二季度,他们换用150个安有D型微型电池的第二代传感器,来评估这些鸟巢的条件。另外,无线传感器网络可以跟踪候鸟和昆虫的迁移,研究环境变化对农作物的影响,监测海洋、大气和土壤的成分等。它也可以应用在精细农业中,来监测农作物中的害虫、土壤的酸碱度和施肥状况等。2.2.2 医疗护理无线传感器网络在医疗研究、护理领域同样可以大展身手。它可以用于病区移动查房、床边护理、呼叫通信
28、、护理监控、药库管理等方面。罗彻斯特大学的科学家使用无线传感器创建了一个智能医疗房间,使用微尘来测量居住者的重要征兆(血压、脉搏和呼吸)、睡觉姿势以及每天24小时的活动状况。英特尔公司也推出了无线传感器网络的家庭护理技术。该技术是作为探讨应对老龄化社会的技术项目Center for Aging Services Technologies(CAST)的一个环节开发的18。该系统通过在鞋、家具以家用电器等家中道具和设备中嵌入半导体传感器,帮助老龄人士、阿尔茨海默氏病患者以及残障人士的家庭生活。利用无线通信将各传感器联网可高效传递必要的信息从而方便接受护理。而且还可以减轻护理人员的负担。英特尔主管预
29、防性健康保险研究的董事Eric Dishman称,“在开发家庭用护理技术方面,无线传感器网络是非常有前途的领域”。2.2.3 军事领域由于无线传感器网络具有密集型、低成本、随机分布的节点组成,自组织性和容错能力使其非常适合应用于恶劣的战场环境中,包括侦察敌情、监控兵力、装备和物资,判断生物化学攻击等多方面用途1。美国国防部远景计划研究局已投资几千万美元,帮助大学进行智能尘埃传感器技术的研发。哈伯研究公司总裁阿尔门丁格预测:智能尘埃式传感器及有关的技术销售将从2004年的1000万美元增加到2010年的几十亿美元。 2.2.3 其他应用无线传感器网络还被应用于其他一些领域。比如一些危险的工业环境
30、如井矿、核电厂等,工作人员可以通过它来实施安全监测。也可以用在交通领域作为车辆监控的有力工具。此外和还可以在工业自动化生产线等诸多领域,英特尔正在对工厂中的一个无线网络进行测试,该网络由40台机器上的210个传感器组成,这样组成的监控系统将可以大大改善工厂的运作条件。它可以大幅降低检查设备的成本,同时由于可以提前发现问题,因此将能够缩短停机时间,提高效率,并延长设备的使用时间。尽管无线传感器技术目前仍处于初步应用阶段,但已经展示出了非凡的应用价值,相信随着相关技术的发展和推进,一定会得到更大的应用。无线传感器网络有着十分广泛的应用前景,它不仅在工业、农业、军事、环境、医疗等传统领域有具有巨大的
31、运用价值,在未来还将在许多新兴领域体现其优越性,如家用、保健、交通等领域。我们可以大胆的预见,将来无线传感器网络将无处不在,将完全融入我们的生活。比如微型传感器网络最终可能将家用电器、个人电脑和其他日常用品同互联网相连,实现远距离跟踪。家庭采用无线传感器网络负责家电协同工作,进行安全调控,并且可以节省电能。另外,用户可以根据自己的个人喜好,可以利用传感器网络设置智能生活环境,如依据传感器检测数据来调节室内光线强度、音乐声音,以形成惬意的房间氛围。无线传感器网络将是未来的一个无孔不入的十分庞大的网络,其应用可以涉及到人类日常生活和社会生产活动的所有领域。2.3传感器网络的特点与挑战传感器网络除了
32、具有Ad-Hoc网络的移动性、断接性、电源能力局限等共同特征以外,还具有很多其他鲜明的特点。这些特点向我们提出了一系列挑战性问题14:(1)通信能力有限。传感器网络的传感器的通信带宽窄而且经常变化,通信覆盖范围只有几十到几百米。传感器之间的通信断接频繁,经常导致通信失败。由于传感器网络更多地受到高山、建筑物、障碍物等地势地貌以及风雨雷电等自然环境的影响,传感器可能会长时间脱离网络,离线工作。 (2)电源能量有限。传感器的电源能量极其有限。网络中的传感器由于电源能量的原因经常失效或废弃。电源能量约束是阻碍传感器网络应用的严重问题。商品化的无线发送接收器电源远远不能满足传感器网络的需要。传感器传输
33、信息要比执行计算更消耗电能.传感器传输1位信息所需要的电能足以执行3000条计算指令。(3)计算能力有限。传感器网络中的传感器都具有嵌入式处理器和存储器。这些传感器都具有计算能力,可以完成一些信息处理工作。但是,由于嵌入式处理器和存储器的能力和容量有限,传感器的计算能力十分有限。如何使用大量具有有限计算能力的传感器进行协作分布式信息处理,是我们面临的第3个挑战。(4)传感器数量大、分布范围广。传感器网络中传感器节点密集,数量巨大,可能达到几百、几千万,甚至更多。此外,传感器网络可以分布在很广泛的地理区域。传感器的数量与用户数量比通常也非常大。传感器数量大、分布广的特点使得网络的维护十分困难甚至
34、不可维护,传感器网络的软、硬件必须具有高强壮性和容错性。(5)网络动态性强。传感器网络具有很强的动态性。网络中的传感器、感知对象和观察者这三要素都可能具有移动性,并且经常有新节点加入或已有节点失效。因此,网络的拓扑结构动态变化,传感器、感知对象和观察者三者之间的路径也随之变化。传感器网络必须具有可重构和自调整性。(6)大规模分布式触发器。很多传感器网络需要对感知对象进行控制,如温度控制。这样,很多传感器具有回控装置和控制软件。(7)感知数据流巨大。传感器网络中的每个传感器通常都产生较大的流式数据,并具有实时性。每个传感器仅仅具有有限的计算资源,难以处理巨大的实时数据流。这就需要研究强有力的分布
35、式数据流管理、查询、分析和挖掘方法。2.4小结本章首先给出了传感器网络的定义、特点以及传感器网络管理核心技术的描述,然后,简要介绍了传感器网络的应用领域,最后,简述了当前传感器网络研究中所面临的挑战。3. LEACH算法简介及分析3.1引言未来的计算装置将越来越与环境融于一体,直至它们对于用户是不可见的。而分布式无线传感器网络正是这一思想的重要体现。不断小型化是微型传感器的设计目标,而传感器的能源供应则是传感器小型化过程中最主要的限制。 传统的能量供应装置是电池,然而缩小电池的体积,增加电池容量的工程技术发展缓慢,这直接影响了无线传感器网络的发展。无法从能量存储的硬件设备上获得突破,于是科研人
36、员开始寻求延长传感器网络使用寿命的其它途径。这就是通过各种优化应用,完善操作系统和通信协议来降低网络的能量消耗,从而在总能量不变的情况下增加传感器网络的使用时间。在上述背景下,各种有关传感器网络的路由算法和通信协议纷纷被提出,其中 Heinzelman 等人提出的LEACH算法是最具代表性和里程碑意义的。3.2 LEACH算法 LEACH算法是一种典型的层次路由算法。相比较平面路由算法而言,LEACH算法具有以下的优点: 成员节点大部分时间可以关闭通信模块,由簇头构成一个更上一层的连通网络来负责数据的长距离路由转发。这样既保证了原有覆盖范围内的数据通信,也在很大程度上节省了网络能量。 簇头融合
37、了成员节点的数据之后再进行转发,减少了数据通信量,降低了数据冗余,在节省了通讯能量的同时也降低了传感器网络在数据计算方面的能量开销。 成员节点的功能比较简单,无须维护复杂的路由信息。这大大减少了网络中路由控制信息的数量,减少了通信量。 分簇拓扑结构便于管理,有利于分布式算法的应用,可以对系统变化作出快速反应,具有较好的可扩展性,适合大规模网络。 LEACH算法首先作了如下的假设: 基站(BS)远离传感器网络节点并且是稳定的。 传感器网络中的所有节点是同构的,并且能量都受到限制。 所有节点可以直接和基站通讯。 节点都没有位置信息。 簇头节点负责数据压缩汇聚以及与基站进行通讯。 该算法主要通过随机
38、选择簇首领,平均分担中继通信业务来实现节能。同时LEACH 定义了“轮”(Round)的概念,针对每个节点n设定了一个阀值T(n): (2.1)式(2.1)中p表示簇头节点占网络节点总数的百分比,r表示重新挑选簇头节点的轮数,G表示网络中最近1/p轮未当选簇头的节点的集合。并根据该阀值从候选节点中挑选簇头,具体的步骤: Step1: 若传感器节点NiG,则对于每个Ni独立运算(2.1)式,获得阀值T(n)。Step2: 若Ni不属于G,则根据(2.1)式,T(n)为零。Step3: Ni产生一个01之间的随机数RadomNum。Step4: 若T(n)RadomNum,则该节点当选为簇头,并广
39、播当选消息。Step5: 其余节点选择加入某簇头所在的簇,形成稳定的拓扑结构。Step6: 稳定工作阶段。Step7: 每隔时间t,进行下一轮簇头选取,转Step1,重新选择簇头并成簇。 由以上步骤可知LEACH算法中的轮是指两次簇头选取之间的时间段,每一轮由初始化和稳定工作两个阶段组成。在初始化阶段,随机选择节点为簇首领,成为簇首领的节点向周围广播信息,其它节点根据接受到广播信息的强度来选择它所要加入的簇,并告知相应的簇首领,由于信息的强度和节点之间的距离是成正比的,因此,实际上各非簇头节点是选择距离自己地理距离最短的簇头所在的簇加入,并形成簇拓扑结构,如图3.1所示:图3.1 成簇阶段图
40、传感器网络首先产生中心节点,其余节点加入距离自己最近的中心节点所在的簇,然后由中心节点直接和SINK节点进行通讯。在稳定工作阶段,节点持续采集监测数据,传送到簇头,由簇头对数据进行必要的融合处理之后,发送到终端节点。每轮工作周期结束后,重新选择簇头并重复前面的工作。3.3 LEACH算法中存在的问题分析 在上述的LEACH算法描述中,我们仔细思考,不难发现其中存在着以下的诸多问题。(1) 算法没有考虑簇头节点在簇结构中的位置对簇头能耗的影响。在簇头选取的过程中,位于簇中心位置的节点和位于簇边缘位置的节点成为簇头的机率是一样的。由于位于簇边缘位置的簇头其通讯能耗远大于位于簇中心位置的簇头,因此将
41、导致各簇头能耗不均衡,使某些簇头节点能量提前耗尽。 (2) LEACH没有考虑到传感器网络在进行部署的时候,节点分布密度对簇头能耗的影响。由此导致在传感器节点密集分布区域的簇头能耗巨大,而在传感器节点稀疏分布区域的簇头能耗较小,网络中各簇头的能耗极不均衡。(3) 动态分簇引起网络拓扑结构频繁变换和大量广播通信,从而带来了额外的能量开销。3.3.1 未考虑簇头在簇结构中位置时存在的问题为指出未考虑簇头在簇结构中位置时LEACH算法中存在的问题,首先假定通过飞机播撒等方式部署的传感器网络中已经形成了若干个簇。其中有某个簇由5个传感器节点构成,且簇中各节点A,B,C,D,E的初始能量均为40,该簇的
42、5个传感器节点的具体分布情况如图3.2所示。图3.2 具有5个节点的传感器网络为计算方便,且假定簇中各节点A,B,C,D,E两两之间的距离如表2.1所示:表3.1 图2.2中节点A,B,C,D,E两两间的距离距离ABCDEA01243B10364C23032D46303E34230假定在每轮通信中,各簇成员分别发送一次数据给簇头,则每轮通信中各节点的工作能耗如表2.2所示: 表3.2 A,B,C,D,E分别为簇头时各节点的工作能耗簇头/能耗ABCDEA102486B2146128C461064D8126166E684612基于式(2.1)可知:采用LEACH算法时整个网络的生命周期可能如表2.
43、3所示:表3.3 采用LEACH算法时整个网络的生命周期簇头/剩余能量ABCDE第1轮:A为簇头3038363234第2轮:B为簇头2824302026第3轮:C为簇头2418201422第4轮:D为簇头16614-216显然,采用LEACH算法时,整个网络的生命周期将小于4轮。从上面的分析不难看出,LEACH算法进行第四轮簇头选取时,没有考虑到节点的剩余能量及其工作能耗,导致剩余能量小于工作能耗的节点D当选为簇头,使节点D的能量过早衰竭,网络的生命周期也随之结束。若结合考虑节点的位置信息,使靠近簇结构中心位置且剩余能量较多的节点有更多机会成为簇头,无疑将有效延长网络的生命周期。3.3.2 未
44、考虑节点分布密度时存在的问题为考虑节点分布密度对网络生命周期的影响,给出一个具有8个节点的传感器络,如图2.3所示。图3.3 具有8个节点的传感器网络 假定各节点的初始能量均为20,各节点簇内通讯半径为10。其中D,F,H三个节点为最近1/p轮未当选簇头的节点。网络中各节点A,B,C,D,E,F,G,H两两之间的距离如表2.4所示:表3.4 图2.3中节点A,B,C,D,E,F,G,H两两间的距离距离ABCDEFGHA0584791114B50449101313C8404761111D4440671012E797604611F910674058G111311106506H14131112118
45、60根据LEACH算法,则有可能出现以下的成簇情况,各种情况下簇头的能量消耗如表2.5所示。由表2.5知,显然在第2种情形下,即当D,F当选为簇头时,簇头节点的工作能耗最接近均衡。因此,应尽可能使密集分布区域中的节点比稀疏分布区域中的节点具有更大当选为簇头的概率(即让D,F当选为簇头的概率最大化),使得密集分布区域比稀疏分布区域产生更多簇头,并且每个簇中成员节点数目大致相同,各簇头的工作能耗也相对均衡。表3.5 图2.3中节点当选簇头的能耗情况序号簇头选取情形簇头簇成员当选簇头工作能耗1F当选为簇头FA,B,C,D,E,G,H492D,F均当选为簇头DA,B,C12FE,G,H173D,H均当
46、选为簇头DA,B,C,E,F25HG64F,H均当选为簇头FA,B,C,D,E,G49H无05D,F,H均当选为簇头DA,B,C12FE,G9H无03.3.3 频繁动态拓扑变换带来的问题由于传感器网络在使用LEACH算法的时候存在轮的概念,并且每轮结束后,都要重新产生新的簇头节点,然后围绕这些簇头再产生新的簇。这使得传感器网络的拓扑结构是动态变化的,并且为了维持这种拓扑结构的动态性,必须要耗费大量的能量进行计算和通讯。下面对LEACH算法每轮动态成簇耗费的能量和簇结构稳定阶段每次工作耗费的能量进行一下对比。1每轮动态成簇的能量开销包括以下几个方面(1) 网络中所有的节点独立的进行运算,然后根据
47、结果判断自己是否能够成为簇头节点所耗费的能量。(2) 当选簇头的节点向周围节点广播自己当选为簇头并邀请其它节点加入簇所耗费的能量。(3) 非簇头节点收到邀请后同时向合适的簇头节点发送成簇请求消息所耗费的能量。(4) 簇头节点接收成簇请求所耗费的能量。2传感器网络稳定阶段每轮工作耗费的能量包括以下几个方面(1) 所有节点采集周围数据所耗费的能量。(2) 非簇头节点向簇头节点发送数据所耗费的能量。(3) 簇头节点接受数据所耗费的能量。(4) 簇头节点将接收到的数据进行汇聚融合计算所耗费的能量。(5) 簇头节点将处理后的数据发送给基站所耗费的能量。不难看出,网络拓扑结构变化一次的开销接近传感器网络工
48、作一次的能量开销。如果能尽可能的长时间保持拓扑结构的稳定性,则可以减少拓扑结构变化的次数,使能量更多的消耗在更有意义的工作阶段。3.4 小结针对LEACH算法中存在的问题,学术界展开了广泛的研究,并提出了许多基于LEACH的改进算法。这些算法从不同的条件和需求出发,都是以延长传感器网络的生命周期为目的,为传感器网络的实际应用提供了许多行之有效的解决方案。4. 能量有效的分布式簇头选取算法4.1引言目前提出的很多路由算法都没有考虑传感器节点的实际分布情况。事实上,受到自然界气流、地形等因素的影响,传感器网络在实际部署的时候,节点可能在某个局部分布非常的密集,而在其它的一些地方分布又非常稀疏。因此
49、在这种情况下,简单的采用LEACH算法中的簇头选取机制,那么选择出来的簇头就会出现如本文3.3.2节中所描述的问题,从而导致传感器网络生命周期的提前结束,这是不希望被看到的。本章首先提出了密度调节参数数学模型,然后把其与上一章提出的平均能耗调节参数结合起来,进而提出了能量有效的分布式簇头选取算法。实验证明采用该算法与采用LEACH算法相比较,传感器网络的生命周期有一定幅度的延长。4.2 EECHS算法 为了解决上面的问题,首先必须量化传感器网络的节点分布密度,为方便描述,不妨做如下的假设:(1) 传感器的通信半径R可以根据需求而改变,R0是基本通信半径,R= R0;(2) Ni表示传感器网络中
50、的第i个节点;(3) 任意节点Ni坐标为;(4) Dist(Ni,Nj)=f(SignalIntension)根据上面的假设,可知Dist(Ni,Nj)表示传感器网络中任意两点之间的直线距离,但是由于在分布式路由算法中节点的位置信息都无法获取,因此给出函数f(SignalIntension),其中SignalIntension表示Ni节点接收到的,由Nj节点发出的信号的强度,这个值可以通过Ni节点的通讯模块获得,而f(SignalIntension)则表示接收信号的强度与收发信号的两节点之间距离的映射关系。对于任意节点Ni,若Dist(Ni,Nj)R0,则称Nj为Ni的邻居节点。从上面的描述不
51、难看出,当某个节点的邻居节点非常多的时候,意味着以该节点为圆心,节点基本通信半径为半径的圆形区域分布的节点很多,单位区域节点的密度很高。故可以把节点分布密度量化为关于其邻居节点总数的正比例函数。根据前面的分析,本节提出一种能量有效的分布式簇头选取算法(EECHS,Energy Efficient Cluster Heads Selection),该算法同时引入能量调节参数和密度调节参数,通过能量调节参数可以使得剩余能量越大且每轮平均工作能耗越小的节点有更多机会成为簇头。通过密度调节参数可以使得分布密度越大区域的节点有更多机会成为簇头。密度调节参数如式(4.1);其中Nodedensity(i)
52、= ,N(j)NeighborSet(i)。NeighborSet(i)是节点Ni的邻居节点集合。即Nodedensity(i)的值表示节点Ni的邻居节点的总数,也就是以N(i)为圆心,R0为半径的圆形区域的节点的个数。当Nodedensity(i)的值比较大时,意味着该节点所在区域节点分布的密度比较大。故,式(2.1)可修订为式(4.2): (4.2)引入一个调节函数,通过该调节函数可以使得剩余能量越大且每轮平均能耗越小的节点有更多机会成为簇头。调节函数的定义如下: (i)在式(i)中,Ecur表示节点当前的剩余能量,Eavg表示节点每轮的平均能耗。故,式(2.1)可修订为以下式(ii):
53、(ii)在上式(ii)中,当整个网络能量较低, 即EcurEavg且Ecur与Eavg接近时,值趋近于零,则T(n)的值接近0,意味所有节点当选为簇头的概率均趋向于0,显然不符合实际情况。为了保障在上述情形中各节点同样能以较大概率当选为簇头,我们将式(ii)进一步改进如式(iii)所示。 (iii)其中,rs为节点连续未当选为簇头的轮数,一旦节点当选簇头,则rs重置为0。得出能量调节参数如式(4.3): (4.3)故LEACH算法的式(2.1)可以改进为如式(4.4)所示: (4.4)由于F(n)和H(n)都为纯小数,并且要求0T(n) 1,因此 的取值范围必须在0和1之间。故式(4.4)中的
54、a,b两参数要满足如下关系,如式(4.5):a + b = 1 (4.5)显然,a=0,b=1时,式(4.4)将简化为以下式(4.6): (4.6)即只在LEACH算法中进一步考虑剩余能量与工作能耗对网络生命周期的影响。而当a=1,b=0时,式(4.4)将简化为以下式(4.7): (4.7)即只在LEACH算法中进一步考虑节点分布密度对网络生命周期的影响。4.3算法性能分析为了说明上述算法的性能,下面仍以第3.3.1节中图3.3所示网络为例,来计算采用新算法时整个网络的生命周期。(1) 假设传感器节点的基本通讯半径设置为10,所以可以很容易的计算出各节点的邻居节点总数,如表4.1所示:表4.1
55、 邻居节点表节点邻居节点总数A6B6C6D7E8F9G5H3(2) 根据节点的邻居节点总数计算出各节点的密度调节参数F(n),如表4.2所示:表4.2 各节点密度调节参数表节点H(n)A5/6B5/6C5/6D6/7E7/8F8/9G4/5H2/3(3) 由于只有D,F,H三个节点为最近1/p轮未当选簇头的节点,因此只需要计算这3个候选簇头节点的T(n)值。因为对于D,F,H而言,的值均相同,故令=K,则D,F,H三点的T(n)值分别为:,。(4) 根据概率论,D,F,H三点中,F点成为簇头的概率最大,H点成为簇头的概率最小。如果假设在三点中只能有两个点成为簇头,依据上面的计算结果,F和D两节
56、点是最有可能的组合。在图3.3中不难看出,F和D正是位于节点密集分布的区域,而H则是位于节点稀疏分布的区域。正好可以保证使节点密集区域的簇头数量比节点稀疏区域的簇头数量多。有效避免了节点密集分布区域簇的规模过大,能量消耗不均匀的现象。4.4小结本章在分析LEACH算法存在问题的基础上提出了节点分布密度数学模型,并将其与每轮平均工作能耗的簇头选取算法结合起来,既把节点平均能耗因素作为选取簇头的考虑对象,又将节点实际部署的拓扑结构也纳入到簇头选取的考虑范畴。采用该算法选取出来的簇头比采用LEACH算法选取出的簇头更为合理。 5. 算法仿真实验5.1实验平台开发一个操作简单,使用方便,直观的传感器节
57、点部署及分簇的系统仿真平台。C#语言是一个很好的选择。C#是可用于创建要运行在.NET CLR上的应用程序语言之一,是Microsoft专门为.NET Framework平台而创建的完全的面向对象的语言。从语法上看,C#非常类似于C+和JAVA,许多关键字都是相同的。其设计与现代开发工具的适应性要比其它语言更高,同时具有Visual Basic的易用性、高性能以及C+的低级内存访问性。它具有以下的一些特性:(1) 完全支持类和面向对象编程,包括接口和继承、虚函数和运算符重载的处理。(2) 对自动生成XML文档说明的内置支持。(3) 自动清理以及动态分配内存。(4) 可以对.NET基类库进行完全
58、的访问,使用.NET Framework代码库提供的每种功能。并且还能容易的访问Windows API。(5) 可以把程序编译为可执行文件或.NET组件库,该组件库可以用于ActiveX控件(COM组件)相同的方式由其它代码调用。(6) C#可以编写ASP.NET的动态Web页面和XML Web服务。本课题使用Microsoft Visual Studio .NET工具,利用C#语言进行仿真系统开发,并使用系统对提出的理论进行验证。5.2实验设计(1) 在生成节点的过程中首先必须构造节点类,由于假设所有的节点都是同构的,所以只需构造一个节点类。该类包括节点ID(唯一),节点当前能量,节点相对位
59、置以及节点的密度等关键属性。(2) 为模拟节点随机分布,首先确定传感器节点的部署区域的大小,即区域的长度和宽度,然后分别产生两个随机数x,y,其中x的取值范围应该是介于0到区域长度之间,而y的取值范围介于0到区域宽度之间。最后将x和y作为节点的坐标,从而确定节点的位置。由于x和y是随机生成的,故可以将节点视为随机分布的。(3) 为确定节点的密度属性,计算该节点和其它所有节点的直线距离,并统计距离小于指定值的节点的总数,再计算出该节点的密度。(4) 通过实例化节点并为每个节点对象的相关属性赋值即可产生节点,而产生节点的个数也可由实例化的次数来控制。(5) 每个节点独立运算簇头的阀值计算公式,并产
60、生一个0到1之间的随机数,并比较该随机数与阀值的大小。根据比较结果确定自己是否成为簇头。(6) 非簇头节点计算自己与该轮产生的所有的簇头之间的距离,并选择距离自己最近的簇头加入,形成簇拓扑结构。(7) 在分簇过程中,每个节点都有计算开销,同时还有广播等通讯消耗,通过减少各节点的当前能量属性来体现能量的消耗。(8) 每轮分簇完成后,判断所有节点的当前能量,若当前能量小于0,则表示该节点能量耗尽,否则继续实验并统计分簇的轮数。5.3实验过程在输入要进行部署的传感器节点个数,区域大小,初始能量和调节参数等相关数据后,可以根据这些数据产生指定个数的节点,并且为每个节点随机分配一个坐标。随后仿真实验平台
61、将生成节点分布的模拟图。接下来采用EECHS算法在刚才模拟部署的传感器节点中选择簇头并成簇,实验平台将以直观的方式显示簇头选取的结果。最后实验平台还将记录每轮分簇过程中产生的簇头的坐标,并以列表的方式显示出来。具体的操作界面如图5.1,图5.2,图5.3,图5.4,图5.5所示。图5.1 获取初始参数界面图图5.1为仿真系统中获取部署节点参数数据的截图,取得相应的数据后即可对节点进行部署,其中能量调节参数和密度调节参数的取值范围为01之间。图5.2 生成节点部署模拟图代码图5.2为生成节点部署模拟图并显示在窗口中的代码。图5.3 节点部署模拟图图5.3为模拟100个节点部署的截图,其中每个小圈
62、代表一个传感器节点。图5.4 簇头选取模拟图图5.4为节点数为200个时,最后一轮分簇时选取的簇头截图,其中比较粗的小圈表示当选为簇头的节点,较细的圈表示普通节点。图5.5 分簇结果图图5.5为在指定参数的情况下分簇结果图,在图4.5中可通过选择左侧窗格中的分簇轮数来查看该轮产生的簇头节点的个数及各簇头的坐标,同时还可以查看总的分簇轮数,从而与采用LEACH算法时传感器网络的生命周期进行比较。5.4实验结果在实验过程中随机生成若干个点,代表随机分布的传感器,假定p=0.1,节点初始能量均为2000。当传感器节点个数固定为200,而部署区域大小分别取800 800,900 900,1000 10
63、00,1100 1100,1200 1200时,得到的仿真实验结果如图5.6所示: 图5.6 部署区域大小变化时EECHS与LEACH算法实验对比图在图5.6中,横坐标为正方形部署区域的边长,纵坐标为采用LEACH算法或EECHS算法时成簇的轮数(即网络的生命周期)。由图5.6知,当节点数量不变,随部署区域面积的扩大,仅考虑节点的分布密度(a=0,b=1)、或仅考虑节点的剩余能量及其工作能耗(a=1,b=0)、或综合考虑节点的分布密度以及节点的剩余能量及其工作能耗(a=0.5,b=0.5)时,采用EECHS算法,传感器网络的生命周期均比采用LEACH算法时更长。特别地,当综合考虑节点的分布密度
64、、节点的剩余能量及其工作能耗(a=0.5,b=0.5)时,传感器网络的生命周期延长了近150%。若随机生成100,150,200个点,而部署区域大小固定为1000 1000时,p=0.1,则仿真实验结果如图5.7所示。图5.7 节点个数变化时EECHS与LEACH算法实验对比图在图5.7中,横坐标为部署的节点个数,纵坐标为采用LEACH算法或EECHS算法时成簇的轮数(即网络的生命周期)。由图4.7知,当部署区域面积一定,随部署的节点数增加,仅考虑节点的分布密度(a=0,b=1)、或仅考虑节点的剩余能量及其工作能耗(a=1,b=0)、或综合考虑节点的分布密度以及节点的剩余能量及其工作能耗(a=
65、0.5,b=0.5)时,采用EECHS算法,传感器网络的生命周期均比采用LEACH算法时更长。特别地,当综合考虑节点的分布密度、节点的剩余能量及其工作能耗(a=0.5,b=0.5)时,传感器网络的生命周期延长了近100%。 若随机生成100个点,而部署区域大小固定为1000 1000,p=0.1时,节点的初始能量分别取1000,1500,2000,2500,3000则仿真实验结果如图4.8所示。 图5.8 初始能量变化时EECHS与LEACH算法实验对比图在图5.8中,横坐标为节点的初始能量,纵坐标为采用LEACH算法或EECHS算法时成簇的轮数(即网络的生命周期)。由图5.8知,当部署区域面
66、积及节点个数一定,随节点初始能量的增加,当仅考虑节点的分布密度(a=0,b=1)、或仅考虑节点的剩余能量及其工作能耗(a=1,b=0)、或综合考虑节点的分布密度以及节点的剩余能量及其工作能耗(a=0.5,b=0.5)时,采用EECHS算法,传感器网络的生命周期均比采用LEACH算法时更长。特别地,当综合考虑节点的分布密度、节点的剩余能量及其工作能耗(a=0.5,b=0.5)时,传感器网络的生命周期比采用LEACH算法时延长了近90%。5.5小结理论分析和仿真实验表明,将该算法应用于传感器网络中,能更有效地降低与均衡网络的能量消耗,与采用LEACH算法时相比较,传感器网络的生命周期有较大幅度的延
67、长。结 论本文首先对传感器网络的各个发展阶段进行了描述,并介绍了目前传感器网络在许多领域的实际应用和各国对传感器网络的重视程度,从而阐明了传感器网络研究的重大意义。由于传感器网络是目前学术界研究的热点,文中对目前国内外关于传感器网络的研究成果进行了总结,着重对近年来提出的各种通信路由协议进行了简要介绍,同时还对部分协议的优缺点进行了分析。Heinzelman等人提出的LEACH算法是关于传感器网络的最具代表性的一种算法,本文的研究也是基于LEACH算法的改进。因此,在对LEACH算法的簇头选取过程和成簇过程进行说明后,本文仔细分析了LEACH算法中存在的问题。比如它没有考虑簇头节点在簇结构中的
68、位置;忽视节点的实际分布对算法的影响;采用能耗巨大的单跳路径选择模式进行通讯等。针对LEACH算法没有考虑簇头节点在簇结构中位置时存在的问题,文中提出了一种基于节点平均能耗的分布式簇头选取算法,通过引入平均能耗调节参数,提高每轮能耗较少的节点成为簇头的机率,从而使靠近簇结构地理中心位置的节点优先成为簇头,簇内节点能量消耗更均衡。考虑到传感器网络在实际部署过程中可能出现规模过大,节点个数过多的簇以及簇头能量消耗不均衡的现象。本文还设计了一种基于传感器网络密度调节参数的数学模型,并通过将密度调节参数引入到LEACH算法中,使位于节点密集分布区域的节点较节点稀疏分布区域的节点有更高机率成为簇头,有效
69、的控制了簇的规模,从而避免了某个簇中节点过多的情况出现。由于上述两种调节参数都能有效的解决LEACH算法中存在的问题,因此本文在LEACH算法基础上同时引入平均能耗调节参数和密度调节参数,提出了能量有效的分布式簇头选取算法。将该算法应用于传感器网络时,能同时兼顾簇头的位置选择和簇的规模控制,进一步优化簇的结构,均衡网络能量的消耗。为了对前面提出的理论进行实验,本文还设计了一个仿真的实验平台。该平台采用C#语言进行开发,用图形化的界面直观的显示出节点的部署情况,根据能量有效簇头选取算法选取出来的簇头位置以及每轮运行算法时各簇头节点在坐标系中的具体坐标。同时该实验平台还能方便的对实验的参数进行修改
70、,全方位的对提出的新算法进行性能分析。根据实验平台的实验结果,采用本文提出的新算法时,传感器网络的簇头选取更为合理,与采用LEACH算法时相比较,传感器网络的生命周期有一定幅度的延长。致 谢本文从拟定题目到最后定稿,历时四个半月。时间很宽松,但由于我是第一次正式接触传感器网络领域,之前对这部分内容的了解甚少。通过课题研究和设计,我接触到传感器网络领域最前沿的科技,感受到做研究的基本思路和方向。 在论文完成之际,首先要向我的导师王雷副教授致以最诚挚的谢意和最崇高的敬意。一直以来,王老师给了我许许多多的帮助和关怀,他学识渊博、治学严谨,平易近人。他对工作认真负责、精益求精的态度,令我非常钦佩和尊敬
71、。 衷心感谢陈喆老师从毕业开题到毕业论文的完成,他都给予了我悉心的指导和关怀。感谢软件学院的所有老师,正是由于他们的传道、授业、解惑,让我学到了这么多专业知识,并从他们身上学到了如何求知治学、如何为人处事。我也要感谢母校湖南大学,是她给我提供了良好的学习环境和生活环境,让我的大学生活丰富精彩。最后,向我亲爱的爸爸、妈妈、爷爷表示万分的谢意!感谢他们对我的信任和关爱,使我养成积极进取,努力勤奋的性格,成为我在学习中不断前进的动力。四年大学生活的磨练,让我在未来的路上更加自信!参考文献1 林亚平, 王雷. 传感器网络中一种分布式数据汇聚层次路由算法,电子学报,2004,32(11):1801-18
72、05.2 任丰原, 黄海宁, 林闯. 无线传感器网络J.软件学报,2003,14 (7):1282-1291.3 谢志军, 王雷, 林亚平, 陈红. 传感器网络中基于数据压缩的汇聚算法研究J,软件学报,2006,17(4): 860-868。4 Agre J, Clare L. An Integrated Architecture for Cooperative Sensing NetworksJ. IEEE Transactions on Computer, 2000, 33 (5):106-108.5 沈 波,张世永,钟亦平. 无线传感器网络分簇路由协议. 软件学报, 2006,17(7)
73、: 1672-1681 6 Vikram Srinivasan, et al, Optimal rate allocation for energy-efficient multipath routing in wireless ad hoc networksJ, IEEE Transactions on Wireless Communications, 2004, 3 (3):891-899.7 B. Krishnamachari, D. Estrin, and S. Wicker. Modelling Data-Centric Routing in Wireless Sensor Netw
74、orks. In Proceedings of IEEE Infocom, 2002,102-1118 Heinzelman,W, Kulik,J, Balakrishnan,H. Negotiation-based protocols for dissemi- nating information in wireless sensor networks. Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, 1999, 441-455 9 Hein
75、zelman,W.R; Chandrakasan,A.; Balakrishnan,H. Energy-efficient communication protocol for wireless micro sensor networks. Proceedings of the 33rd Annual Hawaii International Conference on System Sciences, 2000, 3005-301410 Heinzelman W. Application-Specific protocol architectures for wireless network
76、s Ph.D. Thesis. Boston: Massachusetts Institute of Technology, 2000, 221-22911 Fan Ye, Gary Zhong, et al. PEAS: A Robust Energy Conserving Protocol for Long-lived Sensor NetworksA. Proceedings of the 23rd International Conference on Distributed Computing SystemsC. Providence: IEEE Press, 2003, 28-37
77、.12 M. Chu, H. Haussecker, and F. Zhao, Scalable information-driven sensor querying and routing for ad hoc heterogeneous sensor networks, International Journal of High-Performance Computing Applications, 2002,16(3):348-35613 Chi Fu Huang, Yu Chee Tseng, The Coverage Problem in a Wireless Sensor Net-
78、workA, Proceedings of the 2nd ACM International Conference on Wireless Sensor Networks and ApplicationsC, Oakland: IEEE Press, 2003, 115-121.14 D. Li, K. Wong, Y. Hu, and A. Sayeed. Detection, classication and tracking of targets in distributed sensor networks. IEEE Signal Processing Magazine, 2002,
79、19(2):876-88315 Anthony Man-Cho So, Yinyu Ye. On Sloving Coverage Problems in a Wireless Sensor Network Using Voronoi DiagramsA. Proceedings of the 1st Workshop on Internet and Network EconomicsC. Hong Kong: IEEE Press, 2005: 584-593.16 Ye M, Li CF, Chen GH, Wu J. EECS: An energy efficient clusterin
80、g scheme in wireless sensor networks. In: Proc. of the IEEE Intl Performance Computing and Communications Conf. New York: IEEE Press, 2005,507-51617 Lindsey S, Raghavendra CS. PEGASIS: Power-Efficient gathering in sensor information systems. In: Proc. of the IEEE Aerospace Conf. Montana: IEEE Aerosp
81、ace and Electronic Systems Society, 2002, 497-50518 Xu Y, Heidemann J, Estrin D. Geography-Informed energy conservation for ad hoc routing. In: Proc. of the 7th Annual ACM/IEEE Intl Conf. on Mobile Computing and Networking. Rome: ACM Press, 2001,223-23119 Chan H,Perrig A.ACE:An emergent algorithm fo
82、r highly uniform cluster formation. Proc.of the 1st European Workshop on Wireless Sensor Networks.LNCS 2920,Berlin:Springer-Verlag,2004,33(9):154-17120 Heinzelman W. Application-Specific protocol architectures for wireless networks. Massachusetts Institute of Technology, 2000,342-34621 Al-Karaki JN,
83、 Ul-Mustafa R, Kamal AE. Data aggregation in wireless sensor networksExact and approximate algorithms. In: Proc. of the IEEE Workshop on High Performance Switching and Routing. Phoenix: IEEE Communications Society, 2004, 241-24922 Younis O, Fahmy S. Heed: A hybrid, energy-efficient, distributed clus
84、tering approach for ad-hoc sensor networks. IEEE Trans. on Mobile Computing, 2004,33(4):660-66923 Qun Li and Javed Aslam and Daniela Rus. Hierarchical Power-aware Routing in Sensor Networks, In Proceedings of the DIMACS Workshop on Pervasive Networking, 2001,12(8):108-11724 J. Rabaey, J. Ammer, J.L.
85、 da Silva Jr. and D. Patel, Ad-Hoc Wireless Networking of Ubiquitous Low-Energy Sensor/Monitor Nodes ,” Proceedings of the IEEE Computer Society Annual Workshop on VLSI, Orlando, Florida, 2000,306-314附录A 部分源程序using System;using System.Drawing;using System.Collections;using System.ComponentModel;usin
86、g System.Windows.Forms;using System.Data;using System.Text ;using System.Drawing .Drawing2D;using generatenodes;using System.Xml ;namespace generatenodes public class Result :System.Windows.Forms.Formconst float p=0.1F; const int Ecalculate=20; const int Eoutercommunicate=150; const int rd=100; bool
87、 flagover;int flag;int nodesnum;int zonelength;int initialenergy;string nodenum;string borderlength;string energy;/循环轮数 string resultstr = new string 300;TreeNode newNode = new TreeNode 200;Node nodes = new Node600; public Result() InitializeComponent();flag=0;XmlDocument document = new XmlDocument
88、();document.Load (C:Documents and SettingsAdministratorMy Documentsproject画图TransportData.xml);XmlElement element = document.DocumentElement ;RecurseXmlDocument(XmlNode)element); nodesnum = int.Parse (nodenum);zonelength = int.Parse (borderlength);initialenergy = int.Parse (energy);/实例化对象数组for (int
89、i=0;inodesnum;i+)nodesi = new Node ();Random randomNum = new Random (); /给对象赋初始值for(int i=0;inodesnum;i+)nodesi.ID = i;nodesi.x = (float) (randomNum.NextDouble () * 1000 * 0.4);nodesi.y = (float) (randomNum.NextDouble () * 1000 * 0.3);nodesi.Ecur = initialenergy;nodesi.rs = 0;nodesi.clusterID = -1;n
90、odesi.g = true;nodesi.cluster = false;municateround = 150;nodesi.neighbornodenum = 0;/计算每个节点的邻居节点的个数for(int i=0;inodesnum;i+)int neighbornum = 0;for(int j=0;jnodesnum;j+)if(i!=j)if(dist(nodesi,nodesj) municateround)neighbornum+; nodesi.neighbornodenum = neighbornum; nodesi.nodedensity=(float)(neighb
91、ornum-1)/(float)neighbornum; /运行EECHS算法for(int i=1;ird;i+)EECHS(nodes,i);newNodei-1 = new TreeNode(第+i+轮分簇);treeView1.Nodes.Add (newNodei-1);if(flagover = true)statusBar1.Text = 可以分簇+i+轮; break; private void RecurseXmlDocument(XmlNode root) if(root = null)return;if(root is XmlElement )if(root.HasChi
92、ldNodes )RecurseXmlDocument(root.FirstChild );if(root.NextSibling !=null)RecurseXmlDocument(root.NextSibling );else if (root is XmlText)flag+;if(flag = 1)nodenum = (XmlText)root).Value ;if(flag = 2)borderlength = (XmlText)root).Value;if(flag = 3)energy = (XmlText)root).Value;public float dist(Node x
93、1,Node x2) /float result;result = (float)Math.Sqrt(x1.x-x2.x)*(x1.x-x2.x) +(x1.y-x2.y)*(x1.y-x2.y);return result; public void EECHS(Node arr,int r) float T; float k1,k2;k1=0.5F; /密度调节参数 k2=0.5F; /平均每轮消耗的能量调节参数 Random randomNum1 = new Random (); for(int i=0;i nodesnum;i+)arri.cluster = false;arri.clu
94、sterID = -1; for(int i=0;i (float)randomNum1.NextDouble () )arri.rs=0;arri.rscontinue=0;arri.g = false;arri.cluster = true;arri.clusterID=arri.ID;arri.Ecur = arri.Ecur - Ecalculate; arri.Ecur = arri.Ecur - Eoutercommunicate; elsearri.Ecur = arri.Ecur - Ecalculate; arri.rs+;arri.rscontinue+;if(arri.r
95、s = 10)arri.g = true;arri.rs = 0; elsearri.rs+;arri.rscontinue+;if(arri.rs = 10)arri.g = true;arri.rs = 0; /成簇算法float maxLength ; for(int i=0;inodesnum;i+)maxLength = (float)Math.Sqrt (nodesnum*nodesnum+nodesnum*nodesnum);if(arri.cluster = false)for(int j=0;jnodesnum;j+) if(arrj.cluster = true) if(d
96、ist(arri,arrj) = maxLength) maxLength = dist(arri,arrj);arri.clusterID=arrj.clusterID; for(int i=0;inodesnum;i+)if(arri.cluster = true)for(int j=0;jnodesnum;j+)if(arri.clusterID = arrj.clusterID)arrj.Ecur = arrj.Ecur - dist(arri,arrj)*(float)0.1; /记录每轮分簇的情况for (int i=0;inodesnum;i+)if(arri.cluster =
97、 true)resultstrr = resultstrr + (+arri.x + ,+arri.y+)+、; /判断是否有节点能量消耗完for(int i=0;inodesnum;i+)if(arri.Ecur =0)flagover = true; private void treeView1_AfterSelect(object sender,System.Windows.Forms.TreeViewEventArgs e)for(int i=1;i200;i+)tryif(int.Parse (e.Node.Text.Substring (1,1) = i)richTextBox1.Text =当选簇头的节点的坐标为:+ resultstri;catchpublic class Node public int ID; public float x; public float y; public int rs; public int clusterID; public float Ecur; public bool cluster; public bool g; public int rscontinue; public int communicateround; public int neighbornodenum; public float nodedensity;