（计算机应用技术专业论文）基于模糊聚类的无线传感器网络分簇路由算法的研究.pdf

摘要 无线传感器网络是一个规模大、资源有限、动态拓扑的无线自组 织网络。路由算法作为无线传感器网络重要内容，它负责在源节点和 目的节点间传输数据。目前对路由算法研究已成为无线传感器网络的 热点问题。本文对常用的无线传感器网络分簇路由算法进行了研究， 发现其存在着簇头分布不均匀和没有考虑节点能量等问题。针对这些 问题，考虑到将模糊聚类的方法应用到无线传感器网络中。 本文提出了两种新的算法：基于模糊c 一均值的无线传感器网络 分簇多跳路由算法( f c m c ) 和基于减法聚类的无线传感器网络分簇 路由算法( s c c ) 。 在f c m c 中，首轮采用模糊c 一均值的方法选出簇头和划分固定 的簇，在新的一轮开始时，簇头根据节点的能量值动态选择，这种方 法减少了每次成簇的开销和扩展了网络适用范围；在数据传输阶段， 簇内通信采用单跳模式、簇间通信采用多跳模式，均衡节点的负载， 解决了外围节点早死的问题。在s c c 中，簇头的选择采用减法聚类 的方法，使簇头节点在节点密集处产生，这种基于节点密度的头节点 产生方式保证了簇头节点在整个网络中合理均匀分布；在簇形成算法 中，修正了现有的非簇头节点的归属机制，将能量消耗平均分配到整 个网络中。 本文将两种新算法进行仿真，仿真实验结果表明，与l e a c h ， l e a c h c 等算法相比，f c m c 和s c c 算法改善了网络中能耗的均衡 性，延长了网络的生命周期，同时提高了网络扩展性。 关键词无线传感器网络，模糊c 一均值，减法聚类，簇头，多跳 a bs t r a c t w i r e l e s ss e n s o rn e t w o r ki sal a r g e s c a l e 1 i m i t e dr e s o u r c e sa n d d y n a m i ct o p o l o g ys e l f - o r g a n i z i n gn e t w o r k t h er o u t i n ga l g o r i t h mi s a n i m p o r t a n tp a r to ft h ew i r e l e s ss e n s o rn e t w o r k s ，w h i c hi sr e s p o n s i b l ef o r t r a n s m i t i n go fd a t ab e t w e e nt h es o u r c en o d ea n dt h ed e s t i n a t i o nn o d e a t p r e s e n t ，t h er e s e a r c ho nr o u t i n ga l g o r i t h mh a sb e c o m ea ni m p o r t a n ti s s u e i nw i r e l e s ss e n s o rn e t w o r k s t h i sp a p e rf i r s ti n t r o d u c e s t h ew i r e l e s s s e n s o rn e t w o r k s r o u t i n ga l g o r i t h m s ，a n da n a l y z e s t h e e x i s t i n g c l u s t e r - b a s e dr o u t i n ga l g o r i t h m sa d v a n t a g e sa n dd i s a d v a n t a g e si nd e t a i l i n c l u d i n gt w op r o b l e m s ：t h eu n e v e nd i s t r i b u t i o no fc l u s t e r - h e a d sa n d w i t h o u t i n gc o n s i d e r i n gt h ee n e r g yo ft h en o d e s a i m e da tt h e s ep r o b l e m s ， t h ef u z z yc l u s t e r i n ga p p r o a c hi sa p p l i e di nw i r e l e s ss e n s o rn e t w o r k s t w oa l g o r i t h m sa r ep r o p o s e di nt h i sp a p e r ：f u z z yc m e a n sb a s e d c l u s t e r i n gm u l t i - h o p sr o u t i n ga l g o r i t h mf o rw i r e l e s ss e n s o rn e t w o r k s ( f c m c ) a n ds u b t r a c t i v ec l u s t e r i n gb a s e dc l u s t e r i n gr o u t i n ga l g o r i t h m f o rw i r e l e s ss e n s o rn e t w o r k s ( s c c ) i nf c m c ，a tt h ef i r s tr o u n d ，t h ec l u s t e r - h e a d sa r ec h o s e na n dt h e n o d e sa r eg r o u p e di n t ot h ef i x e dc l u s t e r sb yf u z z yc m e a n s i nt h en e x t r o u n d 。c l u s t e r - h e a d sa r ec h o s e nb yt h ee n e r g yo fn o d e s t h i sm e t h o d r e d u c e st h ec o s to fc l u s t e r sa n de x p a n d st h es c o p eo fn e t w o r k i nt h e c o u r s eo fd a t at r a n s m i s s i o n s i n g l e h o pc o m m u n i c a t i o nm o d ei su s e di n i n n e r - c l u s t e rc o m m u n i c a t i o np h a s e ，a n dm u l t i h o pc o m m u n i c a t i o nm o d e i su s e di no u t e r - c l u s t e rc o m m u n i c a t i o np h a s e t h e s em e t h o d sb a l a n c et h e l o a do fn o d e sa n ds o l v et h ep r o b l e mo ft h ef a r e s tn o d e sd i e de a r l i e r i n s c c ，t h es u b t r a c t i v ec l u s t e r i n gm e t h o di su s e dt oc h o o s et h e c l u s t e r - h e a d sa n dg e n e r a t et h ec l u s t e r - h e a d sw h e r eh a v eh i g hd e n s i t y ； b e s i d e s t h ec u r r e n tn o n c l u s t e rh e a da t t r i b u t i o nm e c h a n i s mi sm o d i f i e dt o d i s t r i b u t et h ee x p e n d i t u r eo fe n e r g ya v e r a g e l yi n t ot h ew h o l en e t w o r k c o m p a r e d w i t h l e a c h ( l o w e n e r g ya d a p t i v ec l u s t e r i n g h i e r a r c h y ) ，l e a c h c ( l e a c h c e n t r i a l i z e d ) a l g o r i t h m s ，s i m u l a t i o n r e s u l t ss h o wt h a tt h ef c m ca n ds c ca l g o r i t h m sc a np r o v i d et h e r e a s o n a b l ea r r a n g e m e n to fc l u s t e r - h e a d 1 0 n g e rl i f e t i m eo ft h ef i r s tn o d e a n de v e nl o n g e rl if e t i m eo ft h en e t w o r kt ob a l a n c et h ee n e r g ye x p e n d i t u r e o fa l lt h en o d e si nt h en e t w o r k k e y w o r d sw i r e l e s ss e n s o rn e t w o r k , f u z z yc - m e a n s ，s u b t r a c t i v e c l u s t e r i n g ，c l u s t e r - h e a d ，m u l t i h o p 1 1 1 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：肇逸盏 日期：立竺l 年上月旦日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者签名：罩趟导 硕士学位论文第一章绪论 1 1 课题背景 第一章绪论 本课题来源于国家自然基金资助项目( n o 6 0 7 7 6 8 3 4 ) “基于车载无线传感 器网络列车运行安全信息科学监测关键技术研究 。 无线传感器网络( w i r e l e s ss e n s o r n e t w o r k ，w s n ) 是信息感知和采集的 一场革命，其巨大的应用价值，已经引起了世界许多国家的军事部门、工业界和 学术界的极大关注，纷纷展开了该领域的研究工作。它使用短距离的无线低功率 通信技术，利用随机分布的集成有传感器、数据处理单元和通信模块的微小节点， 并借助于节点中内置的形式多样的传感器测量所在周边环境中的热、红外、声纳、 雷达和地震波等信号。从而探测温度、湿度、噪声、光强度、压力、土壤成份、 移动物体的大小、速度和方向等物质现象。 尽管无线传感器网络有着广泛的应用晗1 ，但是也有着许多的局限性，诸如能 量有限，最大计算量有限，以及用于节点之间无线连接的带宽有限，另外还有节 点移动性的问题。设计无线传感器网络口1 的一个主要目标就是实现数据通讯，同 时尽力延长网络寿命并且通过采用有效的能量管理技术来提高网络的连通性，而 与数据通讯紧密相关的就是路由协议。 路由协议的设计受到许多关键性因素的影响。包括：节点的布置、节点能量 的消耗、数据报告方式、节点之间的差异、网络的动态变化性、网络连通性、可 测量性、数据传输介质、节点的覆盖率、数据融合以及服务质量等等。国内外研 究者正在展开对无线传感器网络路由协议的研究，先后提出了很多新的路由协 议。研究路由协议最终的目的是设计出新的、最适合无线传感器网络特点的路由 协议。 聚类分析是一种基本的数据分析方法，其操作的目的在于将特征空间中二组 没有类别标记的矢量按某种相似性准则划分到若干个子集中，使得每个子集代表 整个样本集的某个或者某些特征和性质，它在数据挖掘、统计学、空间数据库技 术、人工智能、生物学研究、机器学习、模式识别、市场或客户分割领域等都得 到了广泛的应用。但是聚类分析将样本对象严格划分到某个类中，这种类别划分 的界限是分明的，具有“分此即彼 的性质，但是实际应用中的样本对象，其性 态和类属方面存在着中介性，具有“亦此亦彼”的性质。模糊聚类方法，就是将 模糊理论和方法应用到聚类分析，它使每一样本与各个聚类中心都有一个隶属关 系，并用l o ，1 l 闭区间的值表示样本对各个类的隶属度，该方法在很多领域都有广 硕士学位论文 第一章绪论 泛的应用。 1 2 无线传感器网络的概述及特点 无线传感器网路是由部署在监测区域内大量的廉价微型传感器节点组成，通 过无线通信方式形成的一个自组织网络系统n 1 ，其目的是协作地感知、采集和处 理网络覆盖区域中感知对象的信息，并发送给观察者。它作为计算、通信和传感 器三项技术结合的产物，是一种全新的信息获取和处理的工具，目前已成为计算 机科学领域一个活跃的研究分支。 与传统传感器晦1 和传统测控系统相比，无线传感器网络具有明显的优势。它 采用点对点或点对多点的无线连接，大大减少了电缆连线，在传感器节点端合并 了模拟信号数字信号转换、数字信号处理和网络通信功能1 。节点具有自检功能、 组网灵活性、系统性能与可靠性明显提升而成本明显缩减。 在无线传感器网络中，节点通过飞机布撒、人工布置等方式，大量部署在感 知对象内部或者附近。这些节点通过自组织方式盯儿砌构成无线网络，以协作的方 式感知、采集和处理网络覆盖区域中特定的信息，可以实现对任意地点信息在任 意时刻的采集、处理和分析。这种以自组织形式构成的网络，通过多跳中继方式 将数据传回基站节点( 接收发送器) ，最后借助基站链路将整个区域内的数据传送 到远程控制中心进行集中处理。一个典型的传感器网络的体系结构包括分布式传 感器节点( 群) 、基站节点、互联网和用户界面等。在无线传感器网络中绝大多 数的节点只有很小的发射范围，而基站节点的发射能力较强，具有较高的电能， 可以把数据发回远程控制节点。 无线传感器网络除了具有a d h o c 网络的移动性、自组织性等共同特征以外， 还具有很多其他鲜明的特点。这些特点提出了一系列挑战性问题旧，： ( 1 ) 电源能量有限 传感器的电源能量极其有限，网络中的传感器节点由于电源能量的原因经常 失效或废弃。电源能量的局限是阻碍传感器网络应用n 们的严重问题。商品化的无 线发送接收器电源远远不能满足传感器网络的需要。传感器传输信息要比执行运 算消耗更多的电能，传感器传输1 位信息所需要的电能足以执行3 0 0 0 条运算指 令。如何在网络工作过程中节省能源，最大化网络的生命周期，是无线传感器网 络重要的研究课题之一。 ( 2 ) 通信能力有限 传感器1 的通信带宽窄而且经常变化，通信覆盖范围只有几十到几百米。传 感器之间的通信断接频繁，经常导致通信失败。由于传感器网络更多地受到高山、 2 硕士学位论文第一章绪论 建筑物、障碍物等地势地貌以及风雨雷电等自然环境的影响，传感器可能会长时 间脱离网络，离线工作。如何在有限通信能力的条件下高质量地完成感知信息的 处理与传输，是研究无线传感器网络必须要解决的问题。 ( 3 ) 计算能力有限 传感器网络中的传感器都具有嵌入式处理器和存储器，这些传感器都具有计 算能力，可以完成一些信息处理工作。但是，由于嵌入式处理器和存储器的能力 和容量有限，传感器的计算能力十分有限。 ( 4 ) 传感器数量大、分布范围广 传感器网络中，传感器节点密集，数量大。此外，传感器网络可以分布在很 广泛的地理区域。传感器数量大、分布广的特点使得网络的维护十分困难甚至不 可维护，传感器网络的软、硬件必须具有高强壮性和容错性。 ( 5 ) 网络动态性强 传感器网络具有很强的动态性。网络中的传感器、感知对象和观察者这三要 素都可能具有移动性，并且经常有新节点加入或已有节点失效。因此，网络的拓 扑结构动态变化，传感器、感知对象和观察者三者之间的路径也随之变化。传感 器网络必须具备可重构性和自调整性。 ( 6 ) 感知数据流大 传感器网络中的每个传感器通常都产生较大的流式数据，并具有实时性。每 个传感器仅仅具有有限的计算资源，难以处理的实时数据流。我们需要研究强有 力的分布式数据流管理、查询、分析和挖掘方法。 ( 7 ) 大规模分布式触发器 很多传感器网络需要对感知对象进行控制，如温度控制。这样，很多传感器 具有回控装置和控制软件，既称为触发器刳。 1 3 无线传感器网络的体系结构 1 3 1 网络体系结构 无线传感器网络以自组织形式构成，通过多跳中继方式将数据传回基站节点 ( 接收发送器) ，最后借助基站链路将整个区域内的数据传送到远程控制中心进行 集中处理。一个典型的传感器网络的体系结构n 3 包括分布式传感器节点( 群) 、 基站节点、互联网和用户界面等，如图1 1 所示。在传感器网络中绝大多数的节 点只有很小的发射范围，而基站节点的发射能力较强，具有较高的电能，可以把 数据发回远程控制节点。 硕士学位论文 第一章绪论 用户 图卜1 传感器网络的体系结构 1 3 2 传感器节点组成 无线传感器网络节点的基本组成和功能包括如下几个单元：传感单元n 3 1 ( 由 传感器和模数转换功能模块组成) 、处理单元( 由嵌入式系统构成，包括c p u 、 存储器、嵌入式操作系统等) 、通信单元( 由无线通信模块组成) 、以及电源部分， 如图1 2 所示。此外，可以选择的其它功能单元包括：定位系统、移动系统以及 电源自供电系统等。 图卜2 传感器节点组成 1 3 3 基站节点组成 基站节点的硬件部分主要由中央处理单元、存储单元、射频收发模块和 g p r s 通信模块组成n 引，如图1 - 3 所示。基站节点的中央处理单元主要用来处理 从传感器节点采集到的数据以及完成一些控制功能。为了将采集到的数据传输给 使用者，基站节点还配有g p r s 通信单元，用户可以通过普通p c 和g p r s 手机 4 硕士学位论文第一章绪论 终端柬观测传感器采集到的数据。基站节点同时还配有与传感器节点相同的射频 收发模块，用于接收传感器节点发送的数据。 图1 - 3 无线传感器网络基站的组成 1 4 无线传感器网络的关键技术 无线传感器网络作为当今信息领域新的研究热点，涉及多学科交叉的研究领 域，有非常多的关键技术有待发现和研究，以下列出部分关键技术： ( 1 ) m a c 协议 节省网络的能量消耗是w s n 研究的核心问题之一，而m a c 协议直接控制传 感器节点的射频模块，对节点功耗有重要的影响。目前，m a c 协议在降低功耗 方面主要采用的方法有减少数据流量、增加射频模块休眠时间和冲突避免等。 ( 2 ) 路由协议 路由协议n 5 1 的任务是在传感器节点和基站节点之间建立路由，可靠地传递数 据。由于传感器节点资源有限，因此设计路由协议时不能执行太复杂的计算，不 能在节点中保存太多的状态信息、节点间不能交换太多的路由信息等。为了实现 这些任务，已提出的路由协议采用了数据融合、根据数据的属性寻址、节点间多 跳通信n 6 1 等措施。 ( 3 ) 传输控制协议 传输控制机制可以降低由于缓冲区限制引起的分组丢失，可以提供可靠的数 据传输和有效降低数据传输的代价，这对于w s n 是很重要的。但是，w s n 资源 有限的特征对网络协议的要求更为苛刻，传统的传输控制协议如t c p 没有考虑这 些特征，不能直接应用。 ( 4 ) 时间同步 硕士学位论文 第一章绪论 w s n 的通信协议和应用要求各节点间的时钟必须保持同步，多个传感器节 点相互配合工作，确定节点休眠也要求时钟同步。w s n 的结构庞大、密度高、 节点数量大，处理这样高密度的网络需要能够适应大规模的时间同步算法。而基 于g p s 和一些针对i n t e m e t 的较复杂的协议女i n t p 不能日匕1 4 k 1 e i 好地适用于w s n ，目前已 经有了一些专门为w s n 设计的时间同步算法。 ( 5 ) 定位算法 定位算法用于确定网络中每个传感器节点的相对位置或绝对位置。对于大多 数应用，不知道传感器位置而感知的数据是没有意义的，传感器节点必须明确自 身位置才能详细说明“在什么位置或区域发生了特定事件 ，而且能提高路由效 率、向部署者报告网络的覆盖质量等。但是，采用人工部署或对所有节点安装 g p s 设备将会受成本、扩展性问题的限制，甚至在一些应用场景中无法实现。现 在已经有一些系统和算法能够解决w s n 的自身定位问题了。 ( 6 ) 覆盖控制 无线传感器网络的覆盖控制问题，可以看作是在传感器网络节点能量、无线 网络通信带宽、网络计算处理能力等资源普遍受限情况下，通过网络传感器节点 放置以及路由选择等手段，最终使w s n 的各种资源得到优化分配，进而使感知、 监视、传感、通信等各种服务质量得到改善。近年来，已有一些学者开展了w s n 优化覆盖控制方面的研究工作，并取得了一定的进展。 ( 7 ) 安全性 w s n 多用于军事、商业领域，安全性n 7 3 是其重要的研究内容。由于传感器 节点的功能有限、随机部署、网络拓扑的动态性以及信道的不稳定性，使传统的 安全机制无法适用，因此需要设计新型的网络安全机制，借鉴扩频通信、接入认 证鉴权、数字水印、数据加密等技术。 1 5 无线传感器网络的性能评估 传感器网络的性能1 直接影响其可用性，至关重要。如何评价一个传感器网 络的性能是一个需要深入研究的问题。下面将讨论几个评价传感器网络性能的标 准，但是这些标准还没有达到实用的程度，需要进一步地模型化和量化。 ( 1 ) 能源有效性 传感器网络的能源有效性是指该网络在有限的能源条件下能够处理的请求 数量。能源有效性是传感器网络的重要性能指标。到目前为止，传感器网络的能 源有效性还没有被模型化和量化，还不具有有被普遍接受的标准，需要进行深入 研究。 6 硕士学位论文 第一章绪论 ( 2 ) 生命周期 传感器网络的生命周期是指从网络启动到不能为观察者提供需要的信息为 止所持续的时间。影响传感器网络生命周期的因素很多，既包括硬件因素也包括 软件因素，需要进行深入研究。在设计传感器网络的软、硬件时，我们必须充分 考虑能源有效性，最大化网络的生命周期。 ( 3 ) 时间延迟 传感器网络的延迟时间是指当观察者发出请求到其接收到回答信息所需要 的时间。影响传感器网络时间延迟的因素也有很多，时问延迟与应用密切相关， 直接影响传感器网络的可用性和应用范围，这些方面目前的相关研究还很少，需 要进行深入研究。 ( 4 ) 感知精度 传感器网络的感知精度是指观察者接收到的感知信息的精度。传感器的精 度、信息处理方法、网络通信协议等都对感知精度有所影响。感知精度、时问延 迟和能量消耗之间具有密切的关系。在传感器网络设计中，我们需要权衡三者的 得失，使系统能在最小能源开销条件下最大限度地提高感知精度、降低时间延迟。 ( 5 ) 可扩展性 在整个网络的生命周期中，可以分为规划部署，维护和二次部署等阶段。在 各个阶段中，传感节点在无人值守或者恶劣环境下的有效自组网能力，因外部破 坏或内部故障导致节点失效后网络的自我修复能力以及二次部署中新节点加入 后的网络重构能力构成了对无线自组传感器网络的可扩展能力的要求。 ( 6 ) 容错性 传感器网络中的传感器经常会由于周围环境或电源耗尽等原因而失效。由于 环境或其他原因，物理地维护或替换失效传感器常常是十分困难或不可能的。这 样，传感器网络的软，硬件必须具有很强的容错性，以保证系统具有高强壮性。 当网络的软、硬件出现故障时，系统能够通过自动调整或自动重构纠正错误，保 证网络正常工作。传感器网络容错性需要进一步地模型化和定量化。容错性和能 源有效性之间存在着密切关系。在设计传感器网络时，需要权衡两者的利弊。 上述6 个传感器网络的性能指标不仅是评价传感器网络的标准，也是传感器 网络设计的优化目标。 1 6 研究工作及论文主要内容 无线传感器网络具有十分广阔的应用前景，在许多领域都有重要的科研价 值和巨大的实用价值，已经引起世界上许多国家家界，学术界和工业届的高度重 7 硕士学位论文第一章绪论 视，成为一个前沿热点的研究领域。无线传感器网络数据传输离不开路由协议， 但是传统的无线路由协议却不能适用于无线传感器网络，所以研究无线传感器网 络路由协议具有重要的意义。 本文论文主要内容分为五章，具体内容如下： 第一章，绪论。主要是讲述论文的课题背景和无线传感器网络的概述、特点、 体系结构、关键技术和性能评估等几个方面。 第二章，无线传感器网络路由算法研究进展。主要是介绍国内外无线传感器 网络路由算法的现状，重点分析了现有的无线传感器网络分簇路由算法，并且对 无线传感器网络分簇算法的从簇头节点选举方案，对节点的要求，算法的应用场 景，算法的节能性四个方面进行分析。 第三章，基于模糊c 一均值聚类的无线传感器网络的分簇多跳路由算法。主 要讲述了对l e a c h 算法的改进，提出了基于模糊c 一均值的无线传感器网络分 簇多跳路由算法，采用模糊c 一均值方法根据基站预先指定的最优簇头个数q ， 将整个传感器网络分成q 个簇，并且每个节点隶属于其中一个簇。在整个网络 生命周期内，这个簇结构将是固定不变的；各个节点的簇的标识一旦确定，将不 再改变，直至节点失效。在新的一轮开始之后，算法是完全分布的，簇头节点的 选择基于节点的当前能量值，在相应的簇内能量值最大当选为簇头节点；在数据 传输阶段，簇内通信采用单跳模式，簇间通信采用多跳模式。并对新算法进行仿 真与比较。 第四章，基于减法聚类的无线传感器网络的分簇路由算法。提出了基于减法 聚类的无线传感器网络分簇路由算法，考虑到节点密集度和网络能量均衡两个因 素，在簇头节点产生算法和簇的形成这两个方面对传统的l e a c h 算法进行改进， 簇头的选择采用减法聚类的方法，使簇头节点在节点密集处产生，这种基于节点 密度的头节点产生方式保证了簇头节点在整个网络中合理均匀分布；在簇形成算 法中，修j 下了现有的非簇头节点的归属机制，将能量消耗平均分配到整个网络中。 并对新算法进行仿真与比较。 第五章，总结与展望。对本文的内容进行总结，并以后研究工作进行了展望。 8 硕士学位论文第二章无线传感器网络路由算法研究进展 第二章无线传感器网络路由算法研究分析 2 1 无线传感器网络路由算法概述 在无线传感器网络的体系结构中，网络层的路由协议非常重要，吸引了很 多研究者的关注。无线传感器网络的路由协议随着应用和网络基础结构的不同而 有所差异。网络层的主要目标是：寻找用于传感器网络的高能效的路由建立方法 和可靠的数据传输方法，从而使网络寿命最长。 由于无线传感器网络具有不同于传统无线a d h o e 网络的特点，因此对它的 路由的研究非常有挑战性。首先，由于节点众多，不可能建立一个全局的地址机 制；其次，产生的数据有显著的冗余性，因此可以利用数据聚合来提高能量和带 宽的利用率；第三，节点的能量和处理能力有限，因此需要精细的资源管理；最 后，由于网络拓扑变化频繁，需要路由协议有很好的鲁棒性和可扩展性。 考虑以上无线传感器网络的特征以及应用和基础结构的需要，研究者们提出 了很多方案来解决无线传感器网络中的路由问题。一般可以把它们分为四类：以 数据为中心的( d a t a - c e n t r i c ) 、分层次的( h i e r a r c h i c a l ) 、基于位置的 ( l o c a t i o n b a s e d ) 和基于网络流的( n e t w o r kf l o wb a s e d ) 。 ( 1 ) 以数据为中心的路由协议 这类协议是建立在对目标数据的命名和查询上，并通过数据聚合减少重复的 数据传送，和传统的基于地址的路由有显著的差异。以数据为中心的路由协议主 要有s p i n n 8 1 ( s e n s o rp r o t o c o l sf o ri n f o r m a t i o nv i an e g o t i a t i o n ) ，d d 1 9 1 ( d i r e c t e d d i f f u s i o n ) ，r u m o rr o u t i n g 唧1 ( r u m o rr o u t i n ga l g o r i t h mf o rs e n s o rn e t w o r k s ) ， g b r ( g r a d i e n t b a s e dr o u t i n g ) ，c a d r ( c o n t r a n i n e da n i s t o t r o p i cd i f f u s i o n r o u t i n g ) ，c o u g a r 乜卯( c o u g a ra p p r o a c h ) 等。 ( 2 ) 分层次的路由协议 分层路由协议的主要思想是将传感器节点分簇，簇内通信由簇头节点来完 成，簇头节点进行数据聚集和融合减少传输信息量，最后簇头节点把处理后的数 据传给基站节点。分簇的路由协议主要有：l e a c h 瞳引( l o w e n e r g y e f f i c i e n ta d a p t i v ed i s t r i b u t e dh i e r a r c h y ) ，h i e r a r c h i c a l p e g a s i s 矧( h i e r a r c h i c a l p o w e r - e f t i c i e n tg a t h e r i n gi ns e n s o ri n f o r m a t i o ns y s t e m s1 ，t e e n 2 6 1 ( t h r e s h o l ds e n s i t i v e e n e r g ye f f i c i e n ts e n s o rn e t w o r kp r o t o c 0 1 ) ，e a r c s n “u ( e n e r g y a w a r em a n a g e m e n to fw i r e l e s sn e t w o r k s ) 等。 ( 3 ) 基于位置的路由协议 9 硕士学位论文第二章无线传感器网络路由算法研究进展 基于位置的路由协议利用节点的位置信息通过把数据传送到指定区域而不 是整个网络，来降低能耗。这方面的协议主要来源于移动a dh o c 网络，设计时 都考虑了节点的移动性。但在节点移动性很少或者根本不移动的情况下，它们也 非常适用。基于位置的协议有：m e c n 啪1 ( m i n u m u me n e r g yc o m m u n i c a t i o n n e t w o r k ) ，g a f ( g e o g r a p h i c a la d a p t i v ef i d e l i t y ) ，g e a r ( g e o g r a h i ca n d e n e r g ya w a r er o u t i n g ) 等。 ( 4 ) 基于网络流的路由协议 基于网络流的路由协议的目标是：在实现路由功能的同时，考虑端对端的时 延要求，满足一些网络q o s ( q u a l i t yo fs e r v i c e ) 要求。这类路由协议主要有 m l e r ( m a x i m u ml i f e t i m er o u t i n gi nw i r e l e s ss e n s o rn e t w o r k ) ，m c f 嘲 ( m i n m u mc o s tf o r w a r d i n g ) ，s a r ( s e q u e n t i a la s s i g n m e tr o u t i n g ) ，s p e e d 圳 ( as t a t e l e s sp r o t o c o lf o rr e a l t i m ec o m m u n i c a t i o ni ns e n s o rn e t w o r k s ) 等。 2 2 无线传感器网络分簇路由算法 目前，无线传感器网络分簇路由算法m 1 已成为国内外研究的热点。研究 发现，所有的无线传感器网络分簇算法口刀都是围绕如何选择簇头、如何成簇、如 何传输数据来设计的。下面就从分簇路由算法设计的三个关键技术，分别论述每 个阶段多种不同的实现算法。 2 2 1 簇头产生算法 簇头汹儿3 们的产生是簇形成的基础。分簇路由算法的第一步就是考虑怎样产 生簇头。大多数分簇路由算法是让资源受限的传感器节点承担簇头的任务，为了 延长网络的生命周期，簇头需要周期性地更新。簇头的产生方法、数量和位置决 定了最终形成的簇的结构、大小和数量，也影响了节点的能量耗费进度和网络的 生命周期。目前的簇头选择算法一般基于以下一些准则：节点的剩余能量、簇头 到基站的距离、簇头的位置分布、包括簇头的连通度和覆盖度、簇内通信代价。 下面详细介绍各种簇头产生算法。 ( 1 ) l e a c h 及d c h s l e a c h 乜门是w s n 中最早提出的分簇路由算法，它的成簇思想贯穿于其后 所发展的很多分簇路由算法中，如t e e n m 3 、h e e d 0 。( h y b r i de n e r g y e f f i c i e n t d i s t r i b u t e dc l u s t e r i n g ) 等。 每个节点产生一个o 1 之问的随机数，如果这个数小于阈值玎刀) ，则该节 点向周围节点广播它是簇头的消息。及刀) 的计算公式为： 1 0 硕士学位论文 第二章无线传感器网络路由算法研究进展 卜p 幸i r m o d ( r a ，甩g c2 一， 0 ，其它 其中：p 是簇头占所有节点的百分比，即节点当选簇头的概率：堤当前循环进行 的轮数；g 是最近l 蹴中还未当选过簇头的节点集合。从孔刀) 可以看出，当选过 簇头的节点在接下来的1 p 轮循环中将不能成为簇头，剩余节点当选簇头的阈值 t ( n ) 增大，节点产生小- 于t ( n 1 的随机数的概率随之增大，所以节点当选簇头的概 率增大。 p 值决定了每轮产生的簇头数量，在实际应用中，最佳腊的确定是十分困难 的，这与网络规模和节点密度有关。另外，t f n 、没有考虑能量因素，这种算法必 须基于两个前提假设才能达到每个节点平均耗费能量的预期目标：( 1 ) 每个节点 初始能量均等；( 2 ) 每个节点担任簇头期间耗费的能量均等。然而，由于每个簇 的大小以及簇头到基站的距离不一样，前提假设( 2 ) 不符合现实。 针对l e a c h 中孔甩) 计算公式的不足_ d c h sh 2 1 ( d e t e r m i n i s t i cc l u s t e r h e a ds e l e c t i o n ) 将能量的因素考虑进来，改进t t ( n ) 的计算方法： r ( 刀) 。=卜p r m o d ( 1 p ) 】e m 科 e 一。表示节点的当前能量，e 一。表示节点的初始能量。公式( 2 - 2 ) f 拘改 进，使能量消耗比例较低的节点优先当选簇头。实验结果表明，该节点选取算法 能在l e a c h 基础上有效提高网络生命周期2 0 一3 0 。然而，公式( 2 2 ) 的这种改 进还有一个缺陷：当网络运行了相当长一段时间之后，所有节点的当前能量 e 一一都变得很低，那么阈值致胛) 就会变小，所有节点成为簇头的概率都大大降 低，每轮当选的簇头数量减少，最终导致网络能量耗费不均衡网络生命周期缩短。 为此，d c h s 再次改进了玎”) 的计算方法： m k 2 再丽pl 卺+ ( 矽v 扣一卺) j 3 j r 表示节点连续未当选过簇头的轮次。一旦当选了簇头，重置为o 。公式( 2 3 ) 的改进有效地解决了公式( 2 - 2 ) 的缺陷，综合考虑了节点能量和阈值大小对簇头 选取的影响，使算法更公平合理。 ( 2 ) l e a c h c 和l e a c h f l e a c h c h ( l e a c h c e n t r i a l i z e d ) 和l e a c h f h ( l e a c h f i x e d ) 都是集 中式的簇头产生算法，由基站负责挑选簇头。l e a c h 是由每个节点根据随机数 自主决定是否当选簇头，每轮产生的簇头没有确定的数量和位置。l e a c h c 根 据全局信息挑选簇头，可以有效解决l e a c h 的这一不足。每个节点把自身地理 硕士学位论文第二章无线传感器网络路由算法研究进展 位置和当前能量报告给基站。基站根据所有节点的报告计算平均能量，当前能量 低于平均能量的节点不能成为候选簇头。计算公式如下： m 却厅删p 苦 4 ， 其中a l i v e 是现存节点数目，p 是簇头节点所占的比例，e ，是当前节点能量， 巨删是所有节点的能量之和。从剩余候选节点中选出合适数量和最优地理位置的 簇头集合是一个n p 问题。基站根据所有成员节点到簇头的距离平方和最小的原 则，采用模拟退火( s i m u l a t e da n n e a l i n g ) 算法h 3 1 解决该n p 问题。最后，基站把簇 头集合和簇的结构广播出去。 l e a c h f 也是在l e a c h 基础上做了一些改变。簇的形成与l e a c h c 一样， 也是基站采用模拟退火算法生成簇。同时，基站为每个簇生成一个簇头列表，指 示簇内节点轮流当选簇头的顺序。一旦簇形成之后，簇的结构就不再改变，簇内 节点根据簇头列表依次成为簇头。与l e a c h 和l e a c h c 相比，l e a c h f 最大的 优点就是无须每轮循环构造簇，减少了构造簇的开销。但是，l e a c h f 并不适 合真实的网络应用，因为它不能动态处理节点的加入，失败和移动。同时，它还 增加了簇间的信号干扰。 ( 3 ) d a e a d a e a h 钔( d a t aa g g r e g a t i o n e x a c ta n da p p r o x i m a t e ) 是3 层的分簇协议。簇是 依地理位置事先划分成的大小相等，相邻且不重叠的正方形区域。基于这种结构， 为了最大程度地节省能量和融合数据，d a e a 提出为每个簇选择簇头( 即局部汇 聚点l a ( l o c a la g g r e g a t i o n ) 和从l a 中选择上层簇头( 即主汇聚点m a ( m a s t e r a g g r e g a t i o n ) ) 。选择l a 是基于节点的能量和节点己当选过簇头的次数。从l a 集 合中选取最优的m a ，由m a 负责转发数据到基站，从而最大化网络生命周期， 是一个n p 完全问题。d a e a 采用i l p ( i n t e g e rl i n e a rp r o g r a m ，整数线性优化) 技术 求解，目标是最小化： 口盯+ p ( 2 - 5 ) 其中：仃是每个l a 耗费的能量；p 是选出的m a 个数，口，是两个平衡因子同 时，d a e a 还提出m a 的最大个数限制、m a 转发数据到基站的能量限制等9 个约 束条件，采用i l p 算法求解。此外，对于从l a 中选择m a ，d a e a 还提出了3 种次 优的解决方法：遗传算法、k - m e a n s 算法和贪婪算法。 d a e a 提出的这种3 层簇头数据融合结构是能量与延迟之间的折衷，分层的 增加可以节省能量，但增加了延迟，d a e a 适用于中小型网络。 ( 4 ) h e e d h e e d h 们指出：延长生命周期、可扩展性和负载平衡是w s n 中3 个最重要的 1 2 硕士学位论文 第二章无线传感器网络路由算法研究进展 需求，并通过将能量消耗平均分布到整个网络来延长网络的生命周期。 簇头的选择主要依据主、次两个参数。主参数依赖于剩余能量，用于随机选 取初始簇头集合。具有较多剩余能量的节点将有较大的概率暂时成为簇头，而最 终该节点是否一定是簇头取决于剩余能量是否比周围节点多得多，即迭代过程是 否比周围节点收敛得快；次参数依赖于簇内通信代价，用于确定落在多个簇范围 内的节点最终属于哪个簇，以及平衡簇头之间的负载。考虑到分簇后簇内的通信 开销，h e e d 以a m r p ( 簇内平均可达能量) 作为衡量簇内通信代价的标准。 h e e d 的簇头选择算法具有以下特点：完全分布式的簇头产生方式；簇头产 生在有限次迭代内完成；最小化控制报文开销；簇头分布均衡。h e e d 的主要改 进是：在簇头选择中考虑了节点的剩余能量，并以主从关系引入了多个约束条件 作用于簇头的选择过程。h e e d 在簇头选择标准以及簇头竞争机制上都与l e a c h 不同。实验结果表明，h e e d 分簇速度更快，能产生更加分布均匀的簇头、更合 理的网络拓扑。 ( 5 ) c e f l c e f l h 5 j ( c u s t e r - h e a de l e c t i