（计算机应用技术专业论文）无线传感器网络高能效的多层分簇算法研究与设计.pdf

硕士学位论文 m a s t e r st h e s i $ 中文摘要 无线传感器网络由大量的传感器节点构成，随着技术的发展传感器节点的成本 很低，体积很小、节点所携带的电池能量有限。传感节点具有传感、数据处理、保 存和无线通信能力的传感器节点构成的网络。无线传感器网络可以用于在大范围内 收集、处理和发布复杂的环境数据。由于无线传感网络的独特性，其网络性能如网 络生命周期、网络负载平衡性、网络稳定性、数据传输延时等都与网络结构密切相 关。分簇路由具有能量利用高效、拓扑控制管理快捷方便、数据融合技术简单等优 点，在网络中通过有效的拓扑控制机制可以自动生成层次的网络拓扑结构，该结构 可以充分利用传感节点的有限能量和资源以提高网络性能是研究的重点和关键。本 文所做的工作和贡献包括： 本文首先对无线传感器网络的系统结构、网络的特点和设计的局限性、关键技 术和应用做简要的介绍。并且着重介绍了无线自组的传感器网络的拓扑控制技术， 主要介绍了无线传感器网络拓扑控制问题目前主要开展的三个方向的研究，即功率 控制、层次型拓扑控制和休眠调度。接着分析了无线传感器网络分簇算法的相关内 容，从拓扑控制的角度，网络簇结构的形成过程分析现存的典型的几种分簇路由算 法，并对存在的问题和可能的研究方向进行了简要的阐述。 分簇机制具有很多优势如能量利用高效、拓扑结构管理快捷方便、数据融合简 单等优点，通过拓扑结构控制机制自动生成的层次型的网络拓扑结构，能够有效利 用传感节点的有限能量和资源以提高网络性能。以最小化无线传感器网络的能量消 耗为目标。文章给出了一个更优的能量模型，该能量模型不仅考虑节点的数据传输 消耗还考虑节点在建簇时候控制信息的通信消耗。接着我们给出了一个求无线传感 器网络多层分簇算法最优层的方法。基于此，我们提出了带最优层的多层分簇算法 c o t e 。并通过严格的理论分析了c o t e 的能量消耗和计算复杂度。c o t e 不仅通 过把网络中的节点以最优层的结构组织从而最小化网络的能量消耗，而且c o t e 具 有很低的信息交换复杂度。最后本文在m a t l a b 中对提出的带最优层的多层分簇 算法进行仿真实验，并对实验结果进行详细地研究和分析，验证了c o t e 在节约网 络能量和延长网络生命周期方面的优势以及c o t e 的可行性和有效性。 本文最后对所做的工作进行了总结，并提出了一些需要进一步研究的问题。 关键词：无线传感器网络；拓扑结构；分簇算法；能量有效；簇头 硕士学位论丈 h a s t e r st h e s i s a b s t r a c t v m e l e s ss e n s o rn e t w o r k ( w s n ) i ss e l f - o r g a n i z e d 嘶ml o t so fl o w - c o s ts e n s o r s ， w h i c hh a v et h ea b i l i t i e so fs e n s i n g ，l o c a ld a m p r o c e s s i n ga n dw i r e l e s st r a n s m i s s i o n t h e n e t w o r kp e r f o r m a n c es u c ha sl i f et i m eo fn e t w o r k ，t h eb a l a n c eo fl o a d ，s t a b i l i t ya n d l a t e n c yi sh i g h l yr e l a t e dw i t hn e t w o r kh i 锄r c h yt h ed e s i g no fr o u t i n gt e c h n o l o g ya tt h e n e t w o r kl a y e ri si m p o r t a n ti nt h ep r o t o c o lo fw i r e l e s ss e n s o rn e t w o r k s f o rw i r e l e s s s e n s o rn e t w o r k sw i t hl i m i t e de n e r g ya n db a n d w i d t h , i ti sv i t a lt od e s i g na n e n e r g y - e f f i c i e n ta n da p p r o p r i a t et o p o l o g yc o n t r o la l g o r i t h m w h a tw eh a v ed o n ei nt h i s p a p e ri sa sf o l l o w ： f i r s t l y , t h ec o n c e p t i o n sa n da r c h i t e c t u r ea n dk e yt e c h n o l o g i e so fw s n a r ei n t i d d u c e d b r i e f l y , a n ds o m ed e s i g ni s s u e sa n da p p l i c a t i o n so fw s n a r ec o v e r e d t h e n , w ef o c u so n t h ei s s u eo ft o p o l o g yc o n t r o lo fw s n a n ds o m ec l a s s i c a lc l u s t e r - b a s e dr o u t i n g m e c h a n i s m sf o rw i r e l e s ss e n s o rn e t w o r k sa r ea n a l y z e d w i r e l e s sc l u s t e r i n ga l g o r i t h m c o n t a i n st h r e ek e yp r o c e d u r e s ：c l u s t e r1 1 e a ds e l e c t i o n ,c l u s t e rf o r m a t i o na n dd a t a t r a n s m i s s i o n b yc o m p a r i n gt h ec h a r a c t e r i s t i c st h e s el i t e r a t u r e s ，t h e i rp o s s i b l ef u t u r e i m p r o v e m e n t s a r ep o i n t e do u t t o p o l o g yc o n t r o lo nt h ef o r m a t i o no ft h en e t w o r kt o p o l o g yp l a y sav i t a lr o l e i nt h e p a p e r , w ea d d r e s st h ei s s u eo fh o wm a n yt i e r si nag i v e nc l u s t e r i n gs c h e m ea r eo p t i m a li n s a v i n ge n e r g y w ep r e s e n tam e t h o d t oc a l c u l a t et h e o p t i m a lt i e r n u m b e rw i t h c o n s i d e r a t i o nt ot h ee n e r g yc o n s u m p t i o nb o 也i nd a t at r a n s m i s s i o na n dc o n t r o lo v e r h e a d w ep r o p o s eac l u s t e r i n gs c h e m ew i t ho p t i m a lt i e r sa n de n e r g ye f f i c i e n c yf o rw i r e l e s s s e n s o rn e t w o r k s ，w h i c hw et e r mc o t ef o rs h o r t w et h e o r e t i c a l l ya n a l y z et h ee n e r g y c o n s u m p t i o n , c o m p u t i n gc o m p l e x i t ya n dn e t w o r kl a t e n c yo fc o t e a tl a s t , w es i m u l a t e t h ee n e r g y - e f f i c i e n tm u l t i - t i e rc l u s t e r i n ga l g o r i t h mb ym a t l a ba n dl u c u b m t et h e a n a l y s i so ft h er e s u l t s i tv e r i f i e st h a tc o t ee x c e e d so t h e ra l g o r i t h mi ns a v i n gt h e n e t w o r k s e n e r g ya n dp r o l o n g i n gt h en e t w o r k sl i f e t i m e w ec a na l s os f r o m t h er e s u l t s t h a tc o t ei sf e a s i b l ea n dc a nc o m et oa na n t i c i p a n te f f e c t 。 f i n a l l y , t h ef u t u r er e s e a r c hi s s u e s i nt h i sa r e aa r ep o i n t e do u t k e yw o r d s ：w i r e l e s ss e n s o rn e t w o r k ；t o p o l o g y ；c l u s t e r i n ga l g o r i t h m ；e n e r g y - e f f i c i e n t ；c h 硕士学位论文 m a s t e r st h e s i s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或集 体已经发表或撰写过的作品或成果。对本文的研究做出重要贡献的个人和集体，均 已在文中以明确方式标明。本声明的法律结果由本人承担。 论文作：珈呜眺研年铝7 日 | 。 学位论文版权使用授权说明 本人完全了解华中师范大学关于收集、保存、使用学位论文的规定，即：学校 有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密论文在解密后遵守此规定。 论文作糍：矽谢黜纠铭亏二 日期： 沙7 年6 月留日日期：丑祈年万月，日 ： 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程 ，同意将本人 的学位论文提交“c a l i s 高校学位论文全文数据库 中全文发布，并可按“章程” 中规定享受相关权益。回童途塞埕銮卮进卮：目兰生；旦二生；旦三生苤查。 论文作者签名：j 参戈缪 吼叩年d 月莎日言篓勺瑟弋 ： 硕士学位论文 m a s t e r st h e s i s 1 1 无线传感器网络概述 1 绪论 随着无线传感- 器( w i r e l e s ss e n s o rn e t w o r k s ，w s n ) t l j 的应用日益广泛，其重要性 日益突出。得益于微型机电系统、计算机科学技术、通信技术等学科的快速发展和 日趋成熟，大大降低了传感器节点的成本，从而使得无线传感器网络的广泛应用得 以实现。无线传感器网络具有网络的规模大、网络自组织等特点，可以广泛应用于 特殊环境监测、医疗卫生系统、军事战争和农业等领域。 无线传感器网络通过无线通信的方式将分布在网络中的大量的传感节点组织 成一个高效的数据传输网络，通过无线通信的方式形成一个自组织的网络系统，无 线传感器网络主要是用于传感、收集和处理网络监测区域中被监测对象的状态，并 将结果发送到基站【l 】。无线传感器网络的应用大多都是野外的环境，节点通常部署 在人们无法接近的恶劣甚至偏远的环境中，节点的电源没有办法更新替换，因此设 计有效的能量节约机制和策略以延长网络的生命周期是无线传感器网络的核心关 键问题。另外，目前的无线通信的带宽比较窄、且容易受信号干扰，无线传感器网 络的数据传输比较容易出错、容易被窃取。因而设计容易安装、生命周期长、容错 能力强、传输性能安全的无线传感器网络是研究人员努力追求的目标。 无线传感器网络的独特性和应用价值为研究人员提供了广阔的研究空间。美国 很早就开始无线传感网络的研究，现在我们国家也对无线传感网络开展了广泛的研 究。因此本文选择了无线传感网络作为研究对象，具有科研意义以及实用价值。 无线传感网络的研究涉及很多学科和研究领域甚至是多个学科交叉。其研究内 容主要包括：网络拓扑控制、路由算法设计、能量节约问题、数据融合、网络信息 安全等【2 】。无线传感网络普遍存在节点的计算能力、存储能力和一些如电量，通信 带宽等资源有限等问题。如何在根据无线传感网络的特殊性在有限的资源环境下、 尽可能的有效的收集获取监测对象的数据信息，并将结果发送给最终到用户节点进 行处理，是目前研究的重点内容，这些问题都可以归结为传感器网络的拓扑控制方 法问题f 2 j 。 1 2 无线传感器网络的系统结构和特点 图1 1 中给出了一个典型的无线传感网络的系统结构，从图中可以看出这个系 统结构包括分布式的传感节点、接收器、发送器、英特网和最终用户。其中，传感 器网络节点的结构包括四个基本单元，传感单元，该单元实现数据的传感和模数转 换；以及由c p u 、保存设备、嵌入式操作系统等组成的处理单元；通信单元由无线 通信模块组成以及电源。对于传感器网络中节点在监测区域中的安置，有两种方式： 飞机散布和人工布置等方式。分布在网络中的节点通过一定的自组织机制拓扑结 构，节点之间相互可以通信从而实时感知、收集和发送网络监测区域中的信息，传 感区域内收集到的数据可以通过网络结构将数据通过基站发送给最终的用户。同样 地，基站也可以对网络区域中的节点进行实时控制和操纵。 用户 图1 1 无线传感网络系统结构 无线传感网络是a dh o e 网络的一个分支，是一种不同于传统的网络的特殊网 络，无线传感网络在网络组织方式、网络性能评价等方面具有以数据为中心、节点 资源受限、通信能力有限、拓扑变化频繁和冗余数据多，数据流量大等鲜明的特点 【l 】： 无线传感网络具有其自身的独特性，以及极为广泛的应用环境，节点的能量受 限，且节点的计算能力有限以及发送带宽等诸多资源有限，也给无线传感网络的发 展带来许多的限制。影响无线传感网络中设计的因素大致可以归纳为： 1 无线传感器节点电池所带的的能量有限，并且处于偏远地区，节点能量再充 比较困难，为了有效节约能量从而延长网络生命周期，无线传感网络各协议层算法 2 硕士擘位论文 m a s t e r st h e s i s 及协议的设计应尽可能简单，这样可以减少许多不必要的能量消耗。另外，无线传 感器网络的能量有限问题不仅影响到网络层，甚至是网络中的其他各协议层。为了 能够使节点以及网络的能量减少不必要的消耗，并及时完成监测任务。跨层设计的 思想是一种有效的节能设计思想来设计整体的网络的协议。 2 通常无线传感器网络应用的环境是野外的一些危险偏远地方，因而无线传感 网络在监测环境中的部署可能存在很难以预料的问题。这为算法和协议的设计带来 了巨大的困难。 3 无线传感网络中节点部署密度比较高，并且网络覆盖的传感区域半径大特点。 因为无线传感器网络协议和算法的设计应该要具有可扩展性。也即要就网络中的节 点对算法的执行是分布式的f 3 j 。 4 目前我们对无线传感器网络的研究基本都是建立在假设网络中的节点是同构 的，节点的能量处于同一水平，然而现在的许多应用要求网络的结构具有异构性。 特别是在一些特殊的应用中，节可能在结构，能量水平，甚至是处理能力上存在差 异，根据节点的不同能力分配不童的网络功能任务。尽可能使得网络中的节点的能 量消耗均衡。 5 无线传感器网络的许多应用，如军事上的目标跟踪、突发时间的监测、区域 中的安全监测等，都要求无线传感器网络的设计应该满足实时性已经可靠性。由于 网络中的节点可能由于能量的问题随时会加入和退出。以引起网络拓扑结构的变 化，导致网络中对监测环境数据的监测是动态不断变化的。对于该类情况，网络应 能及时的将监测数据的时延动态的做变化【4 j 纠。 1 3 无线传感器网络的应用领域 军事领域最早开始传感器网络的应用，随着传感技术和通信技术的不断发展， 使得传感器节点的功能日趋强大，而成本却不断降低，目前，无线传感器网络在我 们生活的各个方面和领域的应用也取得了巨大的进展。随着技术的进步和经济的发 展，传感器网络势必会应用到社会生活的各个方面。如无线传感器网络可以应用到 家庭中，家庭电器的安全、节能、调控等都可以有传感器网络实现；企业与社区的 安全和保卫、安全监测、车辆进出与人员流动等都都可以有传感器网络负责；另外 在其他的各种社会活动中，无线传感器网络的也广泛应用【3 1 。下面我们就无线传感 器网络应用比较广泛的几个方面做简要的阐述： 1 军事应用 3 硕士学位论文 k u l s t e r st 1 4 e s i s 传感器网络最早应用于军事活动，由于军事活动要求能实现对敌方的实时准确 监测，以便采取正确的措施和行动，如对敌方装备，兵力的实时监控，已经战场中 目标定位，一些危险的生物化学和核武器的监测等等内容。而无线传感器网络具有 的快速自组织、隐蔽性强、在监测区域的快速部署、和高容错性等特点正使用于该 应用。无线传感器网络能够及时对在军事监控区域中收集的数据进行分析，根据得 到的结果采取正确的行动方案，有利于军事活动的成功。 2 环境监测 无线传感网络在军事方面得到广泛的应用之后，在其他方面的应用也逐渐发展 开来。对于覆盖面积大的监控区域内数据的监测，传感器网络能够很好的应用。比 较常用的如在环境方面的监测，如监测环境中的温度，湿度，土壤、地质、空气等 的情况。这些方面的研究可以直接应用到农业、畜牧业甚至是航空事业。 3 医疗护理 无线传感器网络的研究极大的促进了现代医学设备和技术的发展。它在在医疗 卫生系统、以及健康保健护理机构中都具有普遍的应用，在医疗卫生系统中可以用 于患者的各种生理数据的监测，例如，对在住院的一些特殊病人可以在他们身上安 装特殊用途的传感器节点，传感器节点可以随时的反馈给医生病人的生理数据，如 心率和血压，以快速的掌握病人的情况，对发现异常情况的病人能够及时抢救。另 外，以及对医院内医生和患者的行动跟踪和监控，甚至是医院的药物管理等。 4 交通控制 无线传感器网络在交通控制中应用广泛，目前开发的智能的交通监控系统中都 集成了无线传感器网络。主要是对交通中的车辆进行监控和管理。结合信息采集技 术和网络技术，可以将传感器节点部署在路边的立柱上，十字路口等地方，用于监 控对应交通路段的车辆的情况。包括车辆的进出，违章情况的反馈等等，除此之外 还可以进行交通检测统计以及测速等。 1 4 本文的主要工作以及组织结构 本文深入研究了无线传感网络分簇算法，分析了无线传感网络分簇分簇算法相 关研究，着重从簇头的产生、簇的形成和簇的路由角度系统地描述了当前典型的分 簇路由算法，并比较和分析了这些算法的特点和适用情况，并对存在问题和可能的 研究方向进行了简要的阐述。本文的主要篇章结构如下： 第一章为绪论，介绍了无线传感网络的系统结构和特点、设计的限制因素、性 4 硕士学位论文 n a s t e r st h e s i s 能评价、关键技术和应用领域。最后阐述了本文的主要工作和篇章结构。 第二章首先介绍了无线传感网络的拓扑控制的概念，接着分别介绍了无线传感 器网络拓扑控制问题目前主要开展的三个方向的研究，即功率控制、层次型拓扑控 制和休眠调度。 第三章分析了无线传感网络分簇分簇算法相关研究，特别的从拓扑控制技术的 角度，即簇的形成过程描述了当前典型的分簇路由算法，并比较和分析了这些算法 的特点和适用情况，并对这些算法存在的问题和一些可能的研究方向进行了简要的 说明。 第四章中，以最小化无线传感网络的能量消耗为目标。文章给出了一个更优的 能量模型，该能量模型不仅考虑节点的数据传输消耗还考虑节点在建簇时候的控制 信息通信消耗。基于该能量模型，我们给出了一个求无线传感网络多层分簇算法最 优层的方法。 第五章我们提出了带最优层的多层分簇算法c o t e 。并通过严格的理论分析了 c o t e 的能量消耗和计算复杂度。c o t e 不仅通过把网络中的节点以最优层的结构 组织从而最小化网络的能量消耗，而且c o t e 具有很低的信息交换复杂度。 第六章通过实验仿真验证了c o t e 的有效性和正确性。 第七章对文章所做的工作进行总结，并提出存在的问题和需进一步做的工作。 5 硕士擘位论文 m a s t e r st h e s i s 2 无线传感器网络分簇算法研究 2 1 无线传感器网络分簇算法 无线传感器网络分簇算法指的是，无线传感网络根据具体的应用需求，按照某 种机制将网络划分为多个相互连通并覆盖网络中全部节点的多个簇结构，并在网络 的拓扑结构发生变化时，实时的更新簇的结构和节点的状态以维护网络的正常运 行。分簇算法也即层次型的拓扑控制机制是在保证无线传感器网络节点的连通性和 覆盖度的前提条件下，通过某种规则由网络中的节点分布式的运行分簇算法，将节 点划分到相互连通的簇结构，网络中的簇要就覆盖所有的节点。网络中的节点根据 形成的簇结构有效、正确的传输收集到的数据。除此之外，为了最大化的降低网络 的能量消耗，无线传感器网络的分簇算法的内容还包括，簇头节点采用局部的存储 和融合技术对数据进行压缩，以减少网络通信量，达到节省网络能量消耗的目的。 在网络运转的过程中，由于网络的特殊性和节点的易失效性，网络的节点容易发生 变化，因而，分簇算法还应随网络结构变化实时动态的重建网络的的簇拓扑结构， 确保网络的正常工作。网络分簇过程一般由两个阶段构成，即初始化阶段建立簇结 构，分簇算法中的簇指的是有多个节点构成的集合，在网络运行的过程中，随着节 点的移动或损坏等问题的出现，节点的集合也依据一定的机制相继进行更新，在一 些特殊分簇结构的网络中，簇头节点是预先设置的，其他节点仅仅是作为成员节点 执行相应的加入或离开等重构操作，即只有相应簇成员节点的更新，而并不发生以 簇头的重新选举为代表的簇的重构行为。为减少分簇算法带来的开销，算法应该简 单高效，在只有少数节点发生移动或网络拓扑结构发生较慢变化时，簇结构不会发 生剧烈变化，整个网络只会对发生变化的部分进行簇结构调整i l 哪。 2 2 无线传感器网络分簇算法的相关问题 2 2 1 无线通信模型 能量问题始终是无线传感网络设计考虑的首要因素，无线传感网络分簇算法的 设计与所采用的信道的电路模型直接相关。网络数据传输随着距离的逐渐增大，电 路信号的消耗也不断的增大。因而为了节约网络中节点的能量消耗，对于远距离的 6 硕士学位论丈 h l a s t e r 。st h e s i s 数据传输，由于节点的能量限制，一般采用多跳的传输方式进行传输。 图2 1 信道能量消耗电路模型 图2 1 给出了无线传感器网络采用的信道能量消耗电路模型【阁。对每个传感器 节点该模型有三个电路组成部分：发送电路，发送放大器和接收电路。正如【3 9 1 中表 示的，运行发送电路和接受电路分别需要b 和b 个单位的能量消耗，运行发送放大 器需要消耗国个单位的能量。因而，节点向距离d 的另一节点发送大小为，的信息 需要消耗的能量为： = z ( 巳+ e 2 d 2 ) ， ( 2 1 ) 而节点接受一个距离d 的另一节点发送来的大小为，的信息需要消耗的能量 为： 易= z 。e r ( 2 2 ) 为了方便建立能量模型，我们令岛= 巳= e t 。在文章中，因为节点用于计算的 能量消耗远远小于通信的消耗，故我们忽略节点用于计算的消耗。 2 2 2 数据融合模型 在无线传感网络中，由于在传感区域中位置相近的传感器节点收集到的数据具 有高度的相关性，而如果网络节点都向终端用户发送所有采集到的收集到的数据， 将造成了大量的数据冗余。这将产生很多不必要的数据的传输，从而造成资源的浪 费。目前绝大多数分簇算法的设计都假设网络中所有节点都以相同的长度将收集到 的数据信息传给簇头节点，簇头节点在经过局部的存储和局部数据融合之后，发送 一条相同长度的数据包来描述多个节点发送来的数据信息。在第二章中提出的一个 新的分簇算法采用的是该数据融合模型。 2 2 3 簇头的选取方法 无线传感器网络分簇算法设计中簇头的选取是网络簇结构形成的第一步。由于 传感器网络的广泛应用，目前的无线传感器网络相应的算法设计是与应用相关的， 7 硕士学位论文 曩a s t e r st h e s i s 簇头的选取也随之不同。按簇头的状态可以将簇头的选取方法分为两类：第一类簇 头是被预先指定部署的，e c m r ( e n e r g y c o n s c i o u sm e s s a g er o u t i n g ) t l o 属于这一类， 在e c m r 中假定网络节点不存在能量受限的问题。这与一般的无线传感器网络不 同，因为大多的传感器网络的节点都是能量受限的。第二类簇头是动态生成，并且 周期性的做更新，以平衡节点的能量消耗。簇头的选取机制、决定了簇头数量和位 置和整个拓扑结构，也影响了整个网络的数据传输结构，从而影响节点的能量消耗 和网络的生命周期。目前的大多的无线传感器网络的分簇算法的簇头选择算法基于 以下一些标准： ( 1 ) 节点的剩余能量，即运行一段时间后，节点的剩余能量，一般节点剩余能量 越大，节点成为簇头的几率也更大。 ( 2 ) 节点到簇头的距离：网络中的节点的能量开销主要来自于传输，因而节点与 簇头的距离，直接关系到节点的簇头通信的开销，因而也是一个主要的常用的依据。 ( 3 ) 簇头到基站的距离；簇头担负的任务比一般的节点要重，网络的生命周期与 簇头的生命周期直接相关，网络中的簇头的一种主要的的能量开销主要来自于与基 站节点的通信开销，因而簇头到基站的距离，直接关系到簇头通信的开销，因而也 是一个主要的常用的依据。 ( 4 ) 簇头的位置分布：簇头的位置分布包括簇头包含的节点数目，位置信息等， 这些也之间影响了簇头的能量消耗。 另外，根据簇头产生方式的不同，可以把簇头的选取方法分为分布式和集中式 两种。分布式算法包括两类：集中式算法是指由基站基于整个网络信息挑选簇头， 如l e a c h - c 1 2 7 1 。一类是由节点根据某个比值自主决定是否当选簇头，如l e a c h 2 7 1 ， 另一类是节点之间根据相互交换的信息决定是否成为簇头，如h e e d l 2 2 。 8 硕士学位论文 m a s t e r st h e s i s 3 无线传感器网络多层分簇结构的最优层 无线传感网络中，通过分簇机制网络的节点被划分到多个簇中，采用一定的成 簇方式形成一个以簇头节点为中心的数据处理和转发的子网络，该中网络拓扑结构 大大降低整个网络的能量消耗。在这章中我们提出了如何求能使网络能量消耗最低 的最优分簇层数问题。综合考虑网络中节点的传输消耗和成簇的控制信息消耗，以 最小化整个网络的能量消耗为目标，给出了求最优层数的一般方法。 3 1 研究背景 3 1 1 无线传感器网络分簇算法研究现状 无线传感器网络能量受到限制，设计能量有效的拓扑结构和通信协议以延长网 络的生命周期仍旧是一个巨大的挑战。目前设计低能耗的无线传感网络是研究的热 点之一，包括多方面的内容：能量感知的m a c 层协议【2 5 1 、数据链路和物理层协议 【2 6 l 以及高能效的路由层协议 2 7 - 3 1 1 。路由层协议由于其可扩展性被广泛研究，尤其是 层次型的路由协议也称为分簇路由协议被广泛开发研究。在分簇协议中，传感器节 点依据某种规则被划分到各个簇中，节点收集到的数据在传送到基站节点之前经过 簇头处理转发【3 。利用分簇机制，网络中的节点无需全部节点都向基站节点传输数 据，该方式减少了无线传感网络中的总通信量，从而减少整个网络的能量消耗。分 簇机制与平面路由协议相比具有很多的优势，首先，采用分簇机制节点的能耗比较 小且能量消耗分布相对均匀，这能有效的延长网络生命周期，均衡网络节点的负载； 分簇路由协议不需要所有的节点都想基站传输数据，大大减少了数据的通信量。从 两减少参与路由计算的节点数目，也减小了路由表的大小，降低了交换路由信息所 需的通信开销和维护路由表所需的内存开销；分簇机制通过簇形成策略，选举产生 一个较为稳定的子网络，从而减少了拓扑结构的变化对路由协议带来的影响：分簇 机制通过簇头节点对所在簇的成员节点进行管理，便于管理和维护网络的结构和各 种控制信息的传输，例如节点能量、网络安全、通讯故障等。并且基站的覆盖范围 比较广可以和网络中的所有节点直接通信，这是平面路由所不能实现的【1 8 1 。 l e a c h 是由h e i n z d m a n 等人最早提出了无线传感网络的一个分布式地，单跳 的自适应分簇路由算法。在l e a c h 中，传感器节点以一定的概率成为簇头，并广 播其决定。同一个簇内的节点轮换担当簇头以平衡网络中节点的能量消耗。然而 9 硕士学位论文 m a s t e r st h e s l 8 l e a c h 有其自身的限制性，l e a c h 必须事先知道网络中节点的分布以及网络密度 等网络信息。在l e a c h 之后，紧接着出现了许多关于分簇算法的研究如t 1 9 - 3 2 1 。这 些分簇机制要么在l e a c h 的基础之上研究，要么提出独立的新的分簇思想。但是 大致的这些分簇机制都是在簇头的选取、成簇和路由这三个方面对无线传感网络的 性能做提高和改进。这些协议根据不同的应用和不同的网络特性( 如节点的分布， 网络的结构，簇头节点的性能以及网络操作模式等) 而提出。 3 1 2 无线传感器网络多层分簇算法研究现状 e s t r i n 等人提出了一种新的无线传感网络分层路由算法实现机制多层次的分 簇算法田j 。多层次的分簇算法的主要思想是：通过把传感器网络中的所有节点根据 一定的机制和策略划分为不同的层次，其中如果节点所处的层次越高，那么该节点 可以传输的范围就越广。反之，如果节点所处的层次越低，那么该节点可以传输的 范围就越窄，即覆盖面很窄。在原始阶段，网络中所有的节点都是最低层，通过一 定的方式获得进入上层的机会。具体的过程为：在每轮的分簇算法开始的时候，网 络中的所有节点都广播自身的状态信息，该状态信息包括剩余能量多少、节点所在 的层次和其对应的簇头的d ，消息广播后，节点便进入等待状态以获取周边节点的 信息，节点所需的等待时间和节点处的层次成反比关系。如果在最低层的节点在等 待时间内没有在他的邻近区域内有簇头节点的存在，则等待时间结束之后，该节点 将结束等待状态而进入竞争状态。节点设置一个定时器，该定时器的的时间与节点 的剩余能量和接收到的来自同一层其它节点发送的消息的总数目成反比关系，因为 剩余能量较高并且处于节点分布密集区域的节点应该有更多的机会进入到高一层 的结构中。如果设置的定时器时间结束，节点便进入更高的一层，同时它将已经给 自己发送过消息的节点都归为自己的簇成员，并向这些节点广播自己的状态信息。 如果在这个过程中，已经选择了簇头的节点则不进行上述的工作，即不进行进入上 层结构的竞争。在每一轮的簇结构的建立之后，处于高一层的节点将根据自己的状 态信，该状态信息包括有无成员节点、剩余能量是否充足，通过该状态信息来决定 是否放弃担任簇头。e s t r i n 等人提出的多层簇算法具有扩展性，在文章中，e s t r i n 等 人通过应用两层的模型验证其有效性。 在无线传感网络中，通过拓扑控制以平衡节点之间的能量消耗、提高网络的扩 展性和网络生命周期。b a n d y o p a d h y a y 和c o y l e 指出在无线传感网络中采用层次型 的结构有利于节约能量p 4 。许多的文献对无线传感网络中的多层的分簇算法进行研 究如0 6 - 3 9 1 。在文章f 3 5 1 中，作者提出了一个2 层的层次型的远程通信网络，研究了网 1 0 硕士擘位论文 m a s t e r + st h e s i s 络中节点的分布的特征。如低层次节点与高层次节点连接的数目，以及在层次的结 构中低层节点和高层节点连接的总共的长度。b a n d y o p a d h y a y l 3 7 j 等人以最小化网络 中节点的能量消耗为目标，提出了一个高能效的多层分簇算法。该算法通过严格限 制簇内的层次以及节点和对应簇头之间的跳数来实现能力消耗最优。文章【3 7 】主要通 过实验来表明无线传感网络网络的能量消耗随着网络中分簇层数的增加而减少，这 个发现很重要。然而这些文章中的结果都是基于启发式的，网络的能量消耗和分簇 机制中分簇的层次之间的关系缺乏全面的和理论的基础和分析。l i e s t m a n 3 9 等人提 出了高能效的多层的结构用于无线传感网络中数据压缩。文章计算出了各层中最优 的簇头数目，并且通过仿真实验表明，在无线传感网络中使用多层次的结构大大降 低了网络的能量消耗以及传感器节点的最大的能量消耗。然而文章 5 3 1 4 j 研究网络能 量模型都没有考虑节点接受数据的能量消耗和发送控制信息的消耗。在设计层次型 的分簇结构时，控制信息是一个重要的能量消耗。因而，在研究无线传感网络多层 分簇算法的时候能量模型应该要更全面，另外，网络的能量消耗和分簇机制中分簇 的层次之间的关系需要全面的和理论的基础和分析。 在本章中，我们研究了在分簇式的无线传感网络中能量的有效性和分簇的层数 之间的关系。通过全面考虑网络中节点的通信消耗和控制信息的消耗，提出了一个 求最优层的的方法。基于此，我们提出了一个无线传感网络的带最优层高能效多层 分簇算法，简称为c o t e ( a c l u s t e r i n gs c h e m e w i t ho p t i m a lt i e r sa n de n e r g ye f f i c i e n c y f o rw i r e l e s ss e n s o rn e t w o r k s ) 。我们以伪代码的形式给出了c o t e 算法的描述。对该 算法能量的有效性以及算法的复杂度给出了理论分析。通过分析表明c o t e 通过把 网络中的节点组织成最优的层次结构使得网络能耗最小化，并且算法具有较低的时 间复杂度。因而，c o t e 可以有效地延长网络的生命周期。方针结果表明与传统的 单层分簇算法l e a c h 和已存在的多层分簇算法相比，c o t e 能量消耗更少，具有 更长的网络生命周期。 3 2 系统模型 3 2 1 网络模型 图3 1 信道能量消耗模型 为了方便的建立多层的无线传感网络的能量模型，在文章中，我们研究的网络 传感范围比较大，并且基站位于整个传感区域的中心。网络中所有的传感器节点都 是静态的。簇头节点有足够强的处理能力，即簇头能够将来自多个节点的数据融合 为一个完整的单一信息。除此之外，我们还做如下的假设： ( 1 ) 传感器节点随机的分布在被监测的区域。 ( 2 ) 网络中节点的i d 是唯一的。 ( 3 ) 存在与最终用户之间相连的基站，基站位于整个传感区域的中心，基站有 持续的电源供应没有能量限制，基站可以与整个网络中的节点通信，基站 可以获得网络初始部署情况。 ( 4 ) 无线传感器网络中的节点是同构的，所有的节点具有相同的通信能力和处 理能力，传输一个单位的数据的能量消耗取决于传输的距离。节点能量是 有限的，能量不可再充。 ( 5 ) 在每轮的初始化阶段，用于控制的控制信息的单位长度为所，在传输阶段 的数据的单位长度为f 。 ( 6 ) 传感器网络中的节点都均匀分布，并且可以直接到达对应的簇头。、 ( 7 ) 每个传感器节点可以通过g p s 获得它的位置信息。 ( 8 ) 整个通信环境是无竞争、无差错的，即数据无需重传。 3 2 2 通信模型 任何一个高能效的协议都应该基于一定的具体的网络拓扑结构和无线电系统。 对无线电电路的特征包括在不同的传输和接收模式下的能量消耗将会影响协议的 1 2 硕士学位论文 m a s t e r st h e s i $ 性能。同样的我们采用和文章b 3 】中一样的典型的电路模型。在图3 1 中给出了该电 路模型。根据第二章提到的通信模型，有节点向距离d 的另一节点发送大小为，的 信息需要消耗的能量为： = l ( e t + 乞矗2 ) ， ( 3 1 ) 而节点接受一个距离d 的另一节点发送来的大小为，的信息需要消耗的能量 为： ， = ，勺 ( 3 2 ) 为了方便建立能量模型，我们令e t = 巳= 龟。在文章中，因为节点用于计算的 能量消耗远远小于通信的消耗，故我们忽略节点用于计算的消耗。 3 3 求多层分簇算法最优层的方法 3 3 1 一般的多层分簇拓扑结构 在层次型的分簇网络中，共享同一个簇头节点的节点我们认为属于同个簇。 在一个簇中，簇头作为局部的中间处理中心担负着对来自其附属节点的数据的压缩 处理。如果多个簇的簇头将压缩数据传向同一个上一层的簇头，那么我们定义这些 簇属于同一个层。 一个k 层的分簇策略以至上而下的方式的形成过程即，第一层为最高层，第k 层 为最低层。首先选择第一层簇头，然后第二层，以此类推至第k 层。具体的形成过 程为：传感器网络中的每个节点基于一定的策略以一定的比例成为簇头，并且对在 其传输范围内的节点广播其决定。每个节点根据一定的如簇依据选择簇头进入。接 着在第一层中的每个簇中的普通节点在执行相同的成簇过程。以此类推形成第三 层、第四层第k 层的簇结构。在图3 2 中给出了一个k 层的无线传感器网络分簇 拓扑结构形成图。在多层的分簇传感器网络中，数据的传输过程与形成过程相反 即最底层的传感器节点把收集到的数据传给第一层的簇头，第k 层的簇头对接收到 的数据经过压缩后传给上一层即第k 一1 层簇头，第k l 层簇头再依次往上传输数据 知道网络的最高层。最后第一层簇头把压缩后的数据传给基站。整个网络的毹量消 耗为每层结构中传输数据和控制信息消耗的总和。 硕士学位论文 m a s t e r st h e s i s 图3 2 无线传感器网络多层分簇拓扑结构 根据我们的网络模型，无线传感器网络中的节点是均匀地分布在一个半径为 的圆形传感区域中。对于每个层中的每个簇都可以近似为簇头位于中心的圆形区 域。因而我们可以计算得到第f 层的簇的粗内半径为瞄l ： ，；= 何 ( 3 3 ) 其中，m 是第f 层中簇头的数目，i = 1 ，2 ，k 。对于一个层次型的传感器网络拓扑 结构，上层的簇头不能包含于任何一个下层的簇头。因为弛吒书i = l ，2 ，幺。把 不等式2 ，；- l i - 1 ，2 ，一- , k ，迭代地带入到不等式2 ，i r o 的左边，最后可以得到在没 层中的簇内半径都满足如下的不等式： t ( 3 - 4 ) 1 4 硕士学位论文 m a s t e r st h e s i s 在多层的分簇网络中每层节点成为簇头的概论标记为只，网络中的节点总数为o 因而为们可以得到第k 层中簇头数和非簇头数分别为 k - i m = n o 兀( 1 一弓) 丘 ( 3 - 5 ) 户l 和 i 兢兀( 1 一弓) ( 3 6 ) 暑l 无线传感器网络的主要能量消耗，无线传感器网络中主要有两种信息传输：控 制信息传输和收集到的数据传输。对于七层的分簇机制( 七2 ，3 ，4 ，) ，疋( c 1 ) 标识每 一轮中用于收集到的数据从底层到最高层的数据传输消耗，互( q ) 由普通节点的数 据传输消耗e 和簇头节点的数据传输消耗如两部分组成。臣( c 2 ) 标识每一轮初始 化阶段用于控制信息传输的能量消耗。根据我们之前的网络模型，我们提出的分簇 算法每一轮的初始化阶段，节点传输的控制信息长度是恒定的且无需重传。l e a c h 是典型的单层分簇算法，在簇头选取阶段，无需迭代过程，控制信息消耗接近最优， 控制信息的数量为2 p + ( 1 一即= ( 尸+ 1 ) 侈5 】。其中，和p 分别为网络中的节点 数和节点称为簇头的概率。在我们的文章中，我们采用和l e a c h 相近的簇头选取 方法，具体的过程我们在下一章中给出。因而，对应地对于我们多层的分簇算法第 j 层普通节点数目为o 兀急1 一弓) ，我们可以得到用于第歹层簇建立的控制信息量 为： ，一i o n ( 1 一只) ( 弓+ 1 ) ( 3 - 7 ) i = l 对应地用于第j 层簇建立的控制信息消耗为： 士，一lk - i 【兀0 - p , ) (