毕业设计(格式参考模板)

1、（输入章及标题）燕山大学 毕业设计（论文） 基于链路质量的无线传感器网络拓扑控制算法设计学院（系）电气工程学院年级专业 级测控 学生姓名 指导教师 答辩日期 II燕山大学毕业设计任务书学院：电气工程学院 系级教学单位：工业自动化仪表学号 学生姓名 专 业班 级 题目题目名称基于链路质量的无线传感器网络拓扑控制算法设计题目类型理论与仿真研究题目性质模拟(真题假做)题目来源纵向课题主要内容1、研究无线传感器网络结构的构建方法2、设计基于链路质量的无线传感器网络拓扑控制算法3、对所设计的拓扑控制算法进行分析和性能评价基本要求1、方案设计合理、查阅文献充分2、理论分析正确、论证严密3、理论和仿真结果可

2、靠，结果和理论相符4、毕业设计论文符合撰写规范、要求参考资料1、无线传感器网络，孙利民、李建中等，清华大学出版社2、网络算法与复杂性理论，谢政著，国防科技大学出版社3、相关文献周 次14周58周912周1316周1718周应完成的内容查阅资料阅读文献方案论证建立模型理论分析算法研究软件设计仿真实验撰写论文准备答辩指导教师： 职 称：教授 2007年12月16日系级教学单位审批： 年 月 日说明：如计算机输入，表题黑体小三号字，内容五号字。本任务书一式二份，教师、学生各执一份。燕山大学本科生毕业设计（论文）摘 要集成了传感器、微机电系统和网络三大技术而形成的无线传感器网络在军事、环境、健康、家庭

3、和其他商业领域都有广阔的应用前景，引起了军事部门、学术界和工业界的高度重视。拓扑控制是无线传感器网络研究中的核心问题之一。好的拓扑控制能提高路由协议和MAC协议的效率，有利于无线传感器网络生命周期的延长。拓扑控制算法XTC率先将“链路质量”引入拓扑控制，不需要节点的位置信息，对网络工作环境也没有太多假设，与以往多数算法相比更简单实用。然而XTC并未明确给出链路质量的定义，且存在一定的时延和构建的网络健壮性不高等局限性。目前XTC的改进算法有很多，但均仅使网络健壮性有所提高而未考虑网络综合性能。通过理论建模得出，接收信号强度可以较好的反映链路质量；经Iris实验平台对无线通信链路质量特性进行分析

4、，验证了以距离和收包率作为链路度量标准来构建拓扑的不合理性及接收信号强度反映链路质量的有效性，从而提出一种基于接收信号强度的拓扑控制算法EPTC，调整决定邻居节点范围的参数r，可在网络健壮性与稀疏性之间获得较好的均衡。理论证明了EPTC构建的拓扑在保证网络连通的前提下具有对称性、连通性、节点度限制等良好的性能指标。经Matlab仿真结果表明，该算法构建的拓扑与XTC算法相比，网络平均能耗略有增加，但具有算法复杂度低、网络拓扑健壮性好、负载均衡等优良性能，在一定程度上实现了延长网络生命周期的目的。关键词无线传感器网络；拓扑控制；XTC算法；链路质量；EPTC算法IV燕山大学本科生毕业设计（论文）

5、AbstractBeing integration of sensor, micro-electro-mechanism system and network techniques, wireless sensor networks have widely application value in military, environment, medical, family and other areas, according to which has caused widespread attention of the military, industry and academic circ

6、les. Topology control is one of the most fundamental problems in wireless sensor networks. Good topology control to improve the efficiency of routing agreements and MAC protocol, and extent the life cycle of wireless sensor networks.XTC topology algorithm bring “link quality” into topology control i

7、n first,do not need locationg information,and the network did not work too many assumptions, compared with most other algorithms, more simple and practical. However, XTC algorithm in not explicitly the definition of link quality, and there are some delay and build a robust network of low limitations

8、. At present there are many improved algorithm for XTC, but onhy enhance the robustness of the XTC algorithm, lack of an integrated considering of other properties in network. Further more, through the establishment of communication links model, and found receiver signal strength better reflect the

9、link quality, analysis the wireless communication links quality by Iris experimental platform, prove that the packet and distance assumed as conditions of constract a topology are unreasonable, proposed one of the topology control algorithms , EPTC, based on a receiver signal strength, through its p

10、arameters r adjustments, between robust and sparse ger a better balance in the network. The theory analysis it turned out to be symmetric, connection and the degree of nodes is limited. The result of simulation shows compared with XTC algorithm, the topology made EPTC have higher averagy enemgy, but

11、 hold lower degree of complexity, the better robustness, and good balance of loads. To a certain extent, it extended the network life cycle.KeywordsWireless sensor network Topology control XTC algorithm Link quality EPTC algorithm目 录摘 要IAbstractII第1章 绪论11.1 课题背景11.2 无线传感器网络概述11.2.1 网络体系结构21.2.2 传感器网

12、络特点及应用21.3 无线传感器网络拓扑控制综述31.3.1 无线传感器网络拓扑控制研究意义31.3.2 无线传感器网络拓扑控制研究现状41.4 本文主要研究内容5第2章 XTC拓扑控制算法研究72.1 引言72.2 网络拓扑设计目标72.3 典型拓扑控制算法XTC82.3.1 XTC算法及特性研究82.3.2 算法局限性分析122.4 XTC的改进算法132.4.1 RTC和-RTC算法142.4.2 k-XTC算法162.5 本章小结16第3章 无线通信链路特性分析与论证183.1 引言183.2 无线链路的度量与建模183.2.1 常用链路度量标准对比193.2.2 链路模型的构建203

13、.3 链路特性分析及实验223.3.1 Iris实验平台223.3.2 通信链路的不稳定性243.3.3 接收信号强度相关特性263.4 本章小结27第4章 基于链路质量的拓扑控制算法EPTC284.1 引言284.2 EPTC算法原理及组成284.2.1 算法设计理论基础284.2.2 EPTC算法构建314.2.3 EPTC算法举例354.3 EPTC特性分析与证明384.3.1 链路对称性384.3.2 网络连通性394.3.3 节点度限制特性394.4 本章小结41第5章 EPTC算法性能评价425.1 引言425.2 性能分析与评价425.2.1 算法复杂度分析425.2.2 健壮性

14、与稀疏性的权衡435.2.3 网络平均能耗及其均衡性研究475.3 本章小结49结论51参考文献53致谢56附录1 开题报告57附录2 文献综述62附录3 外文翻译67附录4 外文复印件76燕山大学本科生毕业设计（论文） 第1章 绪论1.1 课题背景无线传感器网络是人类进入21世纪以来，由微电子机械系统、计算机、通信、自动控制和人工智能等学科飞速发展孕育出来的一种新型的测控网络，它由部署在监测区域内大量的廉价微型传感器节点通过无线通信方式构成，能够实时检测、感知和采集网络分布区域内的各种检测对象信息，并对这些信息进行处理，传到用户终端，使用户完全掌握监测区域的情况并做出反应，是一种多跳的自组织

15、网络系统1。其应用前景相当广阔，在国家安全、环境监测、交通管理等领域具有重大的应用价值，因而引起了军界、工业界和学术界的高度关注。从2000年起，国际上开始出现一些有关传感器网络研究结果的报道，美国国防部和各军事部门把传感器网络作为一个重要研究领域，设立了一系列的军事传感器网络研究项目。2003年美国技术评论将无线传感器网络列为十大新兴技术之首。2005年欧洲第1届专业传感器网络会议在德国柏林召开。同年，ACM增设传感器网络研究专刊TOSN(transactions on sensor networks)2。以加州大学伯克利分校、加州大学洛杉矶分校、伊利诺斯大学、麻省理工学院和康奈尔大学为代表

16、的美国著名高校在无线传感器网络拓扑控制研究方面已经取得了初步的研究成果3。其他国家在这一领域的研究均落后于美国。目前，国内一些高等院校与科研机构已积极开展无线传感器网络的相关研究工作，主要有清华大学、中科院软件所、浙江大学、哈尔滨工业大学、中科院自动化所、中国人民大学等。1.2 无线传感器网络概述无线传感器网络是由大量的密集部署在监控区域的智能传感器节点构成的一种多跳的自组织网络应用系统。下面从无线传感器网络体系结构、特点及应用方面，进行基本阐述。1.2.1 网络体系结构无线传感器网络典型的体系结构如图1-1所示，包括大量随机分布的传感器节点(sensor node)、汇聚节点(sink no

17、de)、互联网(internet)、用户终端(user)等4。散布在监测环境中的传感器节点通过网络自组织多跳方式，将数据向汇聚节点发送，汇聚节点可以使用多种方式与外部网络通信，如Internet卫星或移动通信网络等等，将整个区域内的数据传送到用户终端，用户通过管理节点对无线传感器网络进行配置管理。图1-1 无线传感器网络体系结构在不同应用中，无线传感器网络节点的组成不尽相同，但它们一般都由数据采集、数据处理、数据传输和电源四部分组成，如图1-2所示5。Orientation systemExecution moduleSensorADCProcessorRegisterData transfe

18、rSend ReceivePower RegenerationPower supply图1-2 传感器网络节点组成1.2.2 传感器网络特点及应用无线传感器网络中，一组功能有限的传感器协作地完成大的感知任务是无线传感器网络的重要特点。另外，还具有传感节点没有全局ID、硬件资源有限、电源容量低、自组织网络、节点数量众多，分布密集，利用节点之间高度连接性来保证系统的容错性和抗毁性等鲜明的特点6。无线传感器网络所具有的这些特点赋予了其广阔的应用前景，主要表现在军事、环境、健康、家庭和其他商业领域。军事领域的应用是无线传感器网络产生的主要推动力量，由于其特有的无需架设网络设施、抗毁性强等特点，是数字战

19、场无线数据通信的首选技术，是军队在敌对区域中获取情报的重要技术手段。此外，利用无线传感器网络可以实现对环境的控制如海洋监测，这项应用主要利用了传感器能够长期自动无线工作的特点，完全适合于观察目标。借助无线传感器网络，对一栋大厦的温度、空气流通、湿度以及其他物理参数进行实时的高分辨率监控可以显著地提高居住者的舒适程度，并减少能源消耗。无线传感器网络还可以应用于农业，即将湿度、土壤组合传感器放置在农田中计算出精确的灌溉量和施肥量。类似的，无线传感器网络在卫生保健方面的应用可以让人们大大地受益，如利用医护人员和患者之间的跟踪系统可以及时地救治伤患。总之，无线传感器网络随着传感器技术、无线通信技术、计

20、算技术的不断发展和完善，各种传感器网络将遍布我们的生活环境，实现“无处不在的计算”7。1.3 无线传感器网络拓扑控制综述无线传感器网络向科技工作者提出了大量的研究课题，拓扑控制是其中的一个基本问题。拓扑控制就是要形成一个优化的网络拓扑结构，是传感器网络中其他许多研究课题的基础。1.3.1 无线传感器网络拓扑控制研究意义拓扑控制研究的问题是：在保证一定的网络连通质量和覆盖质量的前提下，一般以延长网络的生命周期为主要目标，兼顾通信干扰、网络延迟、负载均衡、简单性、可靠性、可扩展性等其他性能，形成一个优化的网络拓扑结构8。无线传感器网络一般具有大规模、自组织、随机部署、环境复杂、传感器节点资源有限、

21、网络拓扑经常发生变化的特点9。这些特点决定了拓扑控制在无线传感器网络研究中的重要性：在由无线传感器网络生成的网络拓扑中，可以直接通信的两个节点之间存在一条拓扑边。如果没有拓扑控制，所有节点都会以最大无线传输功率工作。在这种情况下，一方面，节点有限的能量将被通信部件快速消耗，降低了网络的生命周期；另一方面，网络中每个节点的无线信号将覆盖大量其他节点，造成无线信号冲突频繁，影响节点的无线通信质量，降低网络的吞吐率。通过对网络进行拓扑控制，可以实现对传感器节点通信功率的控制，从而保证网络的连通性，同时减少节点间的通信干扰，提高整个网络的通信效率。因此，研究拓扑控制有着重要意义，如何设计优化的网络拓扑

22、结构，进行合理的拓扑控制亦成为WSN中研究的重要方向。1.3.2 无线传感器网络拓扑控制研究现状目前，拓扑控制的研究主要以最大限度地延长网络生命周期作为设计目标，并集中于睡眠调度和功率控制两个方面10。所谓睡眠调度，就是减少传感器节点不必要的转发和接收，控制其在工作状态和睡眠状态之间的转换11。麻省理工学院的Heinzelman等人提出了一直被广泛引用的LEACH算法是睡眠调度的代表性算法12。其基本思想是：以周期循环的方式根据某个阈值自主选取簇头，由簇头节点组成骨干网络，其他节点选择加入不同的簇，成为簇内节点，簇头与簇内节点采用TDMA方式通信，簇内节点在其非通信阶段进入睡眠状态，节省能量消

23、耗13。但其缺陷也是很明显的，阈值很难确定，随机产生簇头，不能保证节点分布均匀问题即相应地无法保证网络覆盖质量，另外，没有考虑能量因素。睡眠调度典型算法还有CCP、SPAN、GAN、TopDisc等，这里不再赘述14。所谓功率控制，就是为传感器节点选择合适的发射功率。在无线传感器网络中，若节点的发射功率过大，节点间容易形成相互干扰，整个网络的能量消耗大，从而使网络的吞吐量变小；若节点发射功率过小，节点之间不能形成有效的链路，网络易被划分为很多子网络，连通性很难保证15。目前功率控制的几个典型的拓扑控制算法如：2002年美国伊利诺斯大学的Narayanaswamy等人提出的COMPOW功率控制方

24、案16。2003年3月德国柏林工业大学的Kubisch等人提出了基于节点度来进行功率控制的LMA(Local Mean Of Neighbors Algorithm)和LMN(Local Mean Of Neighbors Algorithm)算法17。2005年微软亚洲研究院的Wattenhofer和康奈尔大学的Li等人提出了一种能够保证网络连通性的基于方向的CBTC算法18。2004年伊利诺斯大学的Li和Hou提出了基于RNG的DRNG和基于LMST的DLMST算法，是两个具有代表性的基于邻近图理论的算法，直接生成双向连通拓扑等19。当前的这些算法构建的网络拓扑都能够较好地满足连通，节点度

25、受限等良好性能，但它们对节点或工作环境要求苛刻。微软亚洲研究院的Wattenhofer等人将“链路质量”这一名词引入无线通信网络的拓扑控制技术中，于2004年提出了相对简单可靠且性能良好的XTC算法，该算法对节点没有太高的要求，对部署环境也没有过强的假设，为无线传感器网络拓扑控制算法的设计提供了一个面向简单、实用的研究方向20。1.4 本文主要研究内容本文以无线传感器网络为背景，以其核心问题拓扑控制为研究方向，针对简单、实用的XTC拓扑控制算法存在的链路质量定义模糊，构建的网络拓扑健壮性低，一定时延等局限性，提出基于接收信号强度且健壮性可调的拓扑控制算法EPTC，从理论及实验两方面验证了该算法

26、的合理性及有效性。论文第2章对XTC算法进行研究，分析得出该算法构建的拓扑健壮性低、存在一定时延，链路质量未明确定义等局限性。在此基础上研究了3种XTC的改进算法，拓扑健壮性较XTC均有所提高，但未全面考虑网络性能。论文第3章对比分析常用的链路度量标准，论证了收包率与接收信号强度的相关性。通过Iris实验平台分析了无线传感器网络链路特性，验证了收包率和距离不宜直接作为通信链路质量度量标准，而接收信号强度确实能够在一定程度上较好的反映链路质量并可实时监测，具有良好的对称性。论文第4章在前两章的基础上，提出了一种完全分布式的拓扑控制算法EPTC，算法以节点间信号的接收强度为度量，通过调节邻节点范围

27、参数r，能够获得网络健壮性与稀疏性的最佳权衡。理论证明了EPTC算法具有对称性、连通性、节点度限制等良好特性。论文第5章论证了EPTC算法的复杂度，并通过对EPTC构建的拓扑健壮性与稀疏性的折中确定最佳r值，进一步从网络健壮性和稀疏性均衡度、网络平均能耗及能量均衡性方面评价EPTC算法，表明EPTC算法构建的拓扑综合性能更为优化。90第2章 XTC拓扑控制算法研究2.1 引言拓扑控制是无线传感器网络研究中的核心问题之一。在密集型的网络中，一个节点存在很多邻节点，如果发射功率足够大，就能实现它们之间的通信，但是高发射功率需要大量能量，且众多邻节点对于MAC协议来说是负担，此外当节点不断移动，频繁

28、建立或释放大量链接时，路由协议也会遭受到网络多变性的影响。拓扑控制可以解决这些问题，对于延长网络的生存时间、减小通信干扰、提高MAC(media access control)协议和路由协议的效率等具有重要意义。它的思想是限制给定节点的邻节点个数，用最小的能量维持整个网络连通，最终达到网络性能的优化，这可以通过控制发射功率来实现或者简单的通过在某段时间关掉某些节点来实现。因此当前的拓扑控制主要集中于功率控制和睡眠调度两方面，相对睡眠调度功率控制算法能够保证网络的覆盖性和低节点度等良好性能。XTC代表了功率控制的发展趋势，与其他功率控制算法相比，从实用的角度出发避免了开销过大，保证了网络连通，且

29、对节点要求不高，不需地理位置信息，并将“链路质量”引入到拓扑控制，提供了一个面向简单、实用的研究方向。2.2 网络拓扑设计目标拓扑控制算法的目标是通过控制节点的传输范围使生成的网络拓扑满足连通性、对称性、稀疏性及节点度受限性等拓扑性质，以延长网络生命周期，降低网络干扰，提高网络吞吐量。所以拓扑控制算法要从以下几个目标出发来设计21。(1)合适的发射功率 在密集型的网络中，一个节点有很多邻节点，如果发射功率足够大，就能实现它们之间的通信。但是高发射功率需要大量能量，众多邻节点对MAC协议来说是负担，而且当节点不断移动，频繁建立或释放大量链接时，路由协议也会遭受到网络多变性的影响。但是如果发射功率

30、过小，又会破化网络的连通性，导致信息不能正确传送，可见发射功率大小的确定是算法必须考虑的一个重要问题。(2)算法应该是分布式的 无线传感器网络本身是一个分布式的无中心自组织网络，尽管传统的集中式算法能很好的使网络达到最优，但实际环境中集中式算法是难以实现的，根据无线传感器网络具有大规模和动态拓扑的特性，由每个节点根据自己收集到的局部信息来构建拓扑耗能少、对网络的拓扑变化更能及时的做出响应，进行自我管理显得更为实用。(3)最大节点度要受限 无线传感器网络的节点度要适中，若一个节点的节点度过大，会增加节点间通信干扰，也会造成节点负担，以至耗能过快；而节点度过低，意味着网络容错能力低，同样也会增加网

31、络的能量消耗。因此节点度是一个重要的性能度量指标，适中的节点度可以降低MAC层的冲突与竞争，提高通信质量。(4)拓扑算法具有本地化的特点 无线传感器网络内通常存在着数量众多的传感器节点，若基于网络全局信息构建拓扑代价过大，且对于真实的网络而言，每个节点均能获取整个网络信息是不现实的。为此无线传感器网络的拓扑算法必须具有“本地化”的特点，即每个节点基于其所获取的邻节点的信息对周遭拓扑制定做出适当的决策。(5)结构健壮性 无线传感器网络应该对通信链路的失败具有冗余性，即如果网络中的某个节点由于能耗过低(死亡)，从网络中移出，剩余的节点仍应能够保持正常通信。这就需要在节点度受限与网络连通之间进行权衡

32、。2.3 典型拓扑控制算法XTCXTC是一种极其简单、完全基于局部信息的无线传感器网络拓扑控制算法。相对于以往提出的众多算法，XTC从实用的角度出发，不需要节点精确的地理位置信息，仅以邻居链路质量排序的思想实现。2.3.1 XTC算法及特性研究XTC建立了一个稀疏的网络拓扑且避免了长距离的链路通信，在网络稀疏性与连通性之间有较好的折中，它的这些优势极大地吸引了之后拓扑控制算法的设计者，下面对XTC算法进行详细分析，算法流程如图2-1所示。XTC Algorithm1. Establish order over s neighbors in 2. Broadcast to each neighb

33、or in ; receive orders from all neighbors3. Select topology control neighbors:4. :=;:=5. While ( contains unprocessed neighbors)6. := least unprocessed neighbor in7. If ( : )8. :=9. Else10. :=11. 图2-1 XTC算法无线传感器网络一般认为是由部署在检测区域内的大量微型传感器节点组成，由于检测区域范围很大，节点相对很小，可以近似认为节点分布在一个二维平面图中，表示为，V代表网络所有节点的集合，E为通信链

34、路的集合；如果存在链路在E中，则表明节点和能够直接通信。执行XTC算法之后形成的子图为，这里是所有保留链路的集合。在图里每一条边，被赋予一个权值，这里假定链路的权值是对称的：。欧几里德图中的节点被认为是分布在欧几里德平面中的，而且边的权值定义为，代表节点和之间的欧几里德距离。UDG(Unit Disk Graph)图是所有已知、未知图结构的发源地，它是一种欧几里德图，包含满足的所有链路。根据图2-1所示XTC算法由三部分组成，邻居排序、邻居排序信息交换及链路选择，网络中的每一个节点都执行XTC算法，这里仅从节点(网络中任意一节点)的观点来详细描述该算法的执行过程：邻居排序：图中节点以其最大发射

35、功率广播消息，确定邻居节点，并对其所有的邻居按链路质量降序排列，建立序列。中任意两个节点与，表示节点与节点之间建立的链路质量高于节点与之间的通信链路质量。节点根据来确定是否与图中的邻节点建立链路。在XTC算法中为了便于说明算法实现过程，假定是节点与其所有邻居节点之间的欧几里德距离的增序，即每个节点根据邻居节点到自身的距离来构建序列，对应图2-1中第一行。邻居排序信息交换：网络中的每一个节点与它的邻居节点进行第二次通信，邻居排序信息在所有的邻居节点之间进行交换。节点广播它自己的邻居排列信息，同时接收由它的邻居节点广播的邻居排列信息，将该信息进行储存，如图2-1第二行。链路选择：节点之间不需要任何

36、进一步的通信，仅仅每个节点根据第二步接收到的邻节点的邻居信息，来确定与其直接通信的邻节点，建立链路。如图2-1第3-11行所示，节点首先建立两个空集合，集合存放与节点直接建立链路通信的节点；集合存放通过多跳方式与节点实现通信的节点。如果节点存在邻节点，且，如果满足，则将节点放入集合，否则，放入集合，依次检查中的所有节点，直到中的节点都进行了处理，此时中所有的节点都与建立通信链路，成为节点的单跳邻居，整个网络拓扑图构建完成。为了更明确的理解XTC算法，给出一个简单的例子来分析，这里假定两节点之间的链路质量是以欧几里德距离来度量的。图2-2中的a)为原始的网络拓扑图，执行XTC算法后，网络拓扑为d

37、)所示，可以很明显的看到，XTC大大简化了网络链路，减缓了节点间的通信干扰与竞争，降低了网络的能耗。图2-2 XTC拓扑构建在图中应用XTC算法，具体过程如下：首先每一个节点都确定一个排序：依据其所有邻居节点的欧几里德距离的升序。如以节点d而言，节点a与它最近，下来是c节点，最远的是节点b。这样节点d就有如下的排序，类似节点a，b，c也建立邻居排序，如下表2-1所示。表2-1 邻居排序：acb：bdc：adc：dba当网络中每个节点都建立了其邻居节点的排序列表之后，邻居列表在其所有的邻居节点之间进行交换，确保每个节点都了解其邻居节点的邻居信息。以节点a为例，节点a发送它的邻居列表给它所有的邻居

38、b，d，c；同时接收来自邻居的列表，并以列表2-2形式进行储存，表中的第一行是由节点a确定的邻居排序，每一列都是以由其列头节点确定的邻居排序信息。表2-2 节点a邻居信息交换列表bdcaaddcbcba随后确定直接通信链路，节点先选择最好的邻居(中出现最早的节点)建立链路，依次判断中所有的邻居，完成局部拓扑的构建。例如节点a先检测邻节点b，由于集合和都是空集，所以不可能存在节点，使得成立，所以添加节点b到集合中：；接下来在中节点a的最好邻居为d，现在包含节点b，因此需要核实b在中是否出现在a之前。很明显这是不成立的，所以，依次检查整个中的所有邻居后，则，包含了节点a在中的所有单跳节点，所以。经

39、XTC算法构建的网络拓扑具有重要的一些特性，分析如下：定理1(连通性) 对于一般的权图，两个节点和在中是连通的当且仅当它们在中是连通的。这个定理简单的说明由XTC算法构建的网络拓扑控制图是连通的，即整个网络不是由孤立的几部分构成即所说的出现分区现象。定理2(链路冗余性) 对于一般的图，周长为4，即在中最短的环长度为4。这个定理是非常重要的，它可以确保XTC算法构建的拓扑在连通性与稀疏性之间取得很好的折中：XTC构建的拓扑控制图包含环，因此对链路失效有冗余性，但是环的周长有下限值。定理3(节点度受限) 对于UDG网络模型，最大节点度不超过6。低节点度特性使得XTC算法在拓扑控制算法中占据着重要地

40、位，通过降低MAC层的干扰和冲突来降低不必要的网络能耗，延长了网络生命周期。但最大节点度不超过6仅仅是对UDG而言的，对于其他网络模型不适用。2.3.2 算法局限性分析XTC算法对节点要求不高、对网络环境也没有过多的假设，且构建的网络拓扑能够保证连通性、节点度低等良好的特性，但仍存在着一定的局限性，分析如下：(1)链路建立存在时延 XTC算法中链路选择的顺序不受约束，由于接收邻居的邻居排序信息的过程是相互独立的，所以没有必要去存储接收到的邻居的邻居序列。一旦节点收到邻居的邻居排序，节点应该立即做出决定：是否与邻居节点直接建立通信。由图2-2可知，XTC算法执行过程中，节点不得不去收集它所有的邻

41、居，然后以一个固有的排序序列开始选择链路。然而，任意节点都无法知道它所有的邻居排序被完全接收的时间。于是必须遗弃：接收来自所有邻居的排序信息，这个不现实的链路选择前提。另外，为了在一定程度上缩短构建拓扑所需要的时间，保证当接收到来自邻居的邻居排序时，可以对该邻居及时的做出响应，决定是添加与该邻居节点之间的通信链路到中，还是采用其他节点转发的方式来通信，可以通过在算法设计中摒弃排序方式，以其他方式实现邻居节点间的信息交换来实现。(2)链路调整困难 一般来说，如果初始网络图发生了变化，那么拓扑控制图也需要发生改变，因此拓扑控制算法应该能够适应动态的拓扑变化。更具体地说，如果拓扑图变化为，那么拓扑控

42、制图能够自适应的调整到拓扑控制图，是由在上执行XTC算法获得的。考虑到每一个节点都保持其邻居的邻居排序列表，将现存的拓扑控制图转换到是简单的，因为每一个节点侦听来自邻居节点的排序信息，那么只需将当前的邻居信息相互交换。一个接收节点可能处理接收到的排序，确定是建立链路，或是不建立该链路即保持原有的链路。但是由于所有的邻居并不是都直接通信，就不能保证每一个邻居都能接收到修改的排序列表。(3)链路质量定义模糊 XTC算法是率先将链路质量引入拓扑控制中的功率控制算法，该算法是根据与邻居节点之间通信链路质量的降序对邻居进行排序以构建拓扑，但是没有给出明确的链路质量定义，仅仅认为距离与通信节点间的链路质量

43、存在着简单的函数关系：距离小，链路质量就高。而节点一旦布置在检测区域，任意两节点之间的距离是固定的，不能体现链路质量的动态变化，且实际的无线通信过程中，链路质量受噪声、环境变化等诸多因素的影响，这就需要在仔细分析通信链路质量的度量标准之后，以更能反映链路质量状况的依据来构建拓扑。这部分内容在第3章给予详细说明。(4)网络健壮性差 无线传感器网络中，适当的减少拓扑中的链路可以有效的减少通信干扰，提高网络吞吐率。XTC算法在UDG模型中保证了构建的拓扑最大节点度不超过6，但是经有关文献论证，即使在密度较大的网络中其平均节点度也仅介于2到3之间，网络健壮性不强，连通性容易遭到破坏，因此需要在稀疏性与

44、健壮性之间进行权衡。2.4 XTC的改进算法针对XTC算法存在的局限性，现已提出了众多改进算法，这里选取几种较为典型的算法RTC(short for randomized topology control)、-RTC(shor for randomized topology control)、k-XTC(Robust Topology Control Protocols)分别进行介绍。2.4.1 RTC和-RTC算法RTC和-RTC是两个随机排序的拓扑控制算法，它们首先构建特殊的邻居排序，然后以此排序作为XTC算法中的邻居排序，执行XTC算法22。RTC由两阶段组成：首先每个节点产生一个0到1

45、之间的随机数作为通信链路权值，以此来定义邻居排序；其次以这些邻居排序序列作为算法输入执行XTC算法。前一阶段称为邻居排序阶段，图2-3给出了其排序流程，它是随机从0,1之间选择一个实数作为每一条链路的权值，不同链路权值的选取是相互独立的。任意节点维持一个队列，判断节点和的id大小，由id大的节点随机选择实数，作为链路的权值，并且将此值赋予和，最后节点通过以的增序来排列其邻节点创建，其排序流程如图2-3所示。Algorithm NeighborhoodOrdering(u)1. Node sends to each neighbor , the value . It receives from

46、each neighbor , the value .2. For each neighbor with , node picks uniformly at random and assigns and sends to .3. For each neighbor with , node receives from and assigns := .4. Node computes an ordering of its neighborhood such that for any pair of vertices 图2-3 RTC算法流程-RTC假设由节点估计其与邻节点之间的距离，表示为，有可能

47、存在。这里假定距离估计产生的错误是受限的，即存在。当距离估计满足此条件时，称其为容错的。与RTC算法类似，该算法也是由两部分构成，邻居排序与XTC算法执行，邻居排序，链路权值是和平均值为中心在特定误差范围内随机选取的，其流程图如2-4所示。Algorithm -NeighborhoodOrdering()1. Node sends to each neighbor , the value . It receives from each neighbor , the value .2. Node estimates the distance to each neighbor . Then nod

48、e sends to each neighbor the estimate and receives from each neighbor the estimate .3. For each neighbor with , node computes and then picks uniformly at random and assigns and sends to . Here , .4. For each neighbor with , node receives from and assigns := .5. Node computes an ordering of its neigh

49、borhood such that for any pair of vertices 图2-4 -RTC算法流程基于随机数来构建拓扑的RTC算法克服了XTC算法因节点间接收到错误的距离信息产生拓扑不连通的问题。若原拓扑保证了很好的对称性、连通性，则该算法也能保证构建的子拓扑是对称、连通的。但是经理论证明该算法的节点度是完全不受限的，也就是说它改善了XTC过于稀疏的局限性，增强了网络的健壮性，但未考虑节点度过大的问题。-RTC算法通过对链路权值的估计值(由节点和分别测得)求平均数，解决了测距不一致的问题，并引入了距离误差值，相比XTC而言有一定的容错性但较RTC来说容错性较低，若原拓扑是对称的、

50、连通的则该算法也能保证构建的子拓扑是对称、连通的，且其节点度是受限的。可见-RTC是XTC算法与RTC算法的结合，网络健壮性得到了一定的提高。但其缺乏对网络综合性能考虑，仍未解决XTC算法存在的链路定义不明确，网络时延等局限性。2.4.2 k-XTC算法k-XTC算法23是针对XTC算法健壮性不高而提出的，其变换了建立链路的判断条件，将:改为，即意味着节点需要找到k个邻节点，与它们建立的单跳链路皆优于节点和直接通信链路。设为执行k-XTC算法后的拓扑图，那么XTC算法是k-XTC当k=1的特例。k-XTC算法法流程如图2-5所示。k-XTC Algorithm()1. Establish or

51、der over s neighbors in 2. Broadcast to each neighbor in ; receive orders from all neighbors3. Select topology control neighbors:4. :=;:=5. While ( contains unprocessed neighbors)6. := least unprocessed neighbor in7.8. :=9. Else10. :=11. 图2-5 k-XTC算法流程很明显，k-XTC算法构建的拓扑相比XTC而言健壮性提高了，但是该算法不能保证网络的最大节点度受

52、限，仅能给出节点度的下限值，即每个节点的节点度至少为k。2.5 本章小结通过对XTC算法分析表明，网络中每个节点都需要在选择链路之前依据收集到的所有邻居节点信息对其邻居进行排序，然而任何一种排序方式其时间复杂度都较大，以至XTC算法构建链路存在一定的时延。考虑无线传感器网络资源受限，应尽量避免使用排序方式，以降低算法复杂度；XTC尽管将链路质量引入拓扑控制，但对其定义模糊，认为距离大则通信链路质量就低，对链路模型假设过于理想化，有待进一步对通信链路分析，寻找有效、实用的度量标准；此外XTC构建拓扑过于稀疏，不利于选择优化路由、抗干扰性差，从而提出网络稀疏性与健壮性权衡的问题。针对XTC这些局限

53、性，进一步研究了RTC、-RTC以及k-XTC三种XTC改进算法，分析表明此三种算法皆解决了XTC构建的网络拓扑健壮性低的问题，但同时却引入了节点度不受限的问题，且并未考虑算法时延，链路通信状况等网络其他性能，以至算法综合性能不高。第3章 无线通信链路特性分析与论证3.1 引言在自然环境下传感器节点对之间的链路质量估计是设计优化无线传输信号能耗以及路由选择的拓扑控制算法的基础。大量实验研究发现，无线传感器网络的不可靠通信连接对上层协议影响很大。Ganesan等通过在大规模无线传感器网络上的大量实验证实了，即使是最简单的flooding算法也可能由于不稳定链路表现出复杂的性能；Zhou等发现不规

54、则无线连接对传感器网络的路由协议有很大影响，尤其是基于位置的路由协议，如地理转发协议24。这就要求在网络拓扑构建之前需充分考虑链路质量的变化，寻找一个能很好度量链路质量的标准，从而形成能量有效的拓扑控制。以往对链路性能假设过于理想，基于此构建的拓扑与真实网络相差甚远，因此有必要构建更加符合实际的链路模型，并通过对通信链路特性的研究，确定能够有效反映通信链路质量的度量标准，为构建实用、可靠的拓扑算法奠定基础。3.2 无线链路的度量与建模在无线链路传播模型研究方面，众多的文献往往是基于对链路性能的如下假设：现实环境是二维平面；无线发送区域是圆形；所有无线电都有着相等的传播距离；链路是对称的；收包率

55、与距离之间呈现出简单的函数关系。显然，这对链路的假设过于理想化，往往会影响协议或算法的可靠性，例如在构建拓扑时，认为收包率与距离之间存在简单的函数关系，而以距离作为构建拓扑的依据，忽略了其他影响通信链路的因素，与真实的网络相差甚远。本文建立了更接近实际的链路模型，采用Iris平台对无线通信链路特性实际的实验测量，大量采集现场数据，借助Matlab工具，经统计评估、数据绘图及理论分析获得能较好反映无线传感器网络通信链路质量的度量标准。3.2.1 常用链路度量标准对比区分链路质量的好坏，必须有一个统一的度量标准。目前使用的度量标准大致有三种：收包概率(Packet Peception Rate,P

56、RR)，信号强度指示值(Received Signal Strength Indicator,RSSI)，链路质量指示值(Link Quality Indicator,LQI)25。PRR是反映链路质量最常用的度量标准，它定义为一段时间内成功收到包的个数占发送器已发送包个数的比例，基于链路的不对称性和应用的需求，用一组矢量对描述PRR由式(3-1)描述 (3-1)其中，为发包速率，为时间内实际收到包的个数，为正向链路的收包率，为反向链路的收包率。在Iris节点上，RF230无线模块提供了丢包率的测量值，但是这需要低速率的通信量，以确保在链路死亡后，节点能探测到包的丢失。通过统计丢包率来反映链路

57、的质量状况，必须在网络中维持一定数量的控制包，然而这会增大通信开销，且丢包率对链路状况的反映不够灵敏，所以仍需寻找能合理反映节点链路质量并获取容易的度量指标。RSSI(接收信号强度值)和LQI(链路质量指示值)是另外常用的两个链路质量的度量标准。RSSI体现了通信链路上信号的接收功率，因此也能在一定意义上反映链路状态。基于RF230无线芯片提供了信号强度测量值，每个包到达时其RSSI输出可以通过相应的程序获得。从程序中直接获得的RSSI值是芯片寄存器PHY_RSSI的值，此时需经过一个简单运算，才能将其转换为接收节点的RF管脚的功耗值26。运算公式如下 (3-2)其中，的取值为-91dB，可见

58、RSSI的获取比PRR方便的多，每包到达时就可以得到其瞬时值，能够实现实时检测。LQI也是一个衡量链路质量的指标，定义为接收器的能量探测(Energy Detection，ED)，或是信噪比的估计值，或是两者的综合，是对接收包的质量或强度的描述。RF230给出了LQI的具体实现方法，它是对接收到的每个包前8位的误码率进行采样，由这个采样值得到50,100间的相关值，再通过线性变换转换为0,255间的数值，所以LQI实际是比特水平的度量标准。这个最小和最大的LQI值(0和255)应该是信号最低和最高的质量，各LQI的值应该是均匀分布在这两个界限之间。AT86RF230测定了无线通信链路的链路质量

59、，无线接收装置在每接收一个数据帧同时完成LQI的测定。LQI与PER(packet error rate)相关联，PER是无线通信时，节点接收到数据帧错误的数目与总接收到的数据帧数目的比值，若PER为0，则表明网络中传输帧没有出现错误。一个低的LQI值意味着低的信号强度或高的信号失真，信号失真主要是由信号干扰和多路径传播引起的。反之，高的LQI值代表一个足够高的信号能量和低的信号失真27。值得注意的是，接收信号的功率是通过接收信号强度值(RSSI)或能量探测(ED)值来体现的，并没有反映信号的质量和信号解码的能力。例如，一个标准信号输入功率为6dB，已经超出了接收器的灵敏度，但它仍可能导致LQ

60、I接近于255(包失真很小)，这是因为通过增加传输功率不能进一步降低包的错误率，已经达到一个极限值，对发射功率变化是不受限的。可见LQI不能较好的评价链路质量。3.2.2 链路模型的构建对实际的通信链路考虑k个连续包传输的情况，对于每一次包到达只有两种可能结果，即成功接收或丢包。因此，把每次包到达事件看作一次贝努利试验，用1表示成功接收，0表示丢包，那么包到达序列就是贝努利过程。假设为独立同分布的贝努利随机变量，那么的期望值等于第次成功收包的概率，记为。k次包到达的平均成功收包率为，但k足够大时，根据大数定律，的值接近于，即PRR可以由成功接收一个数据包的概率进行估计。采用反向不归零机制编码，