（计算机应用技术专业论文）高效能耗的传感器网络拓扑控制和路由技术的研究.pdf

摘要 摘要 随着通信技术、嵌入式技术、传感器技术、无线技术的迅速发展和日趋成熟，具有广泛 应用前景的无线传感器网络在多个领域出现，传感器网络在成网方式、通信模式、资源能力 等方面与传统的计算机无线网络具有很大差异，也有别于传统意义上的自组织网络。传统无 线网络的设计强调高服务质量的保障和高效带宽的利用；然而传感器网络与之不同，由于缺 乏持续、稳定的能量供给，其重要设计目标是通过高效使用能量来最大化网络生命期。网络 生命期体现了能耗效率的高低，从本质上反映出网络拓扑结构、节点可用能量和路由选择等 因素的影响，因此如何延长传感器网络的生命期成为了当前无线传感器网络技术研究领域的 热点之一。 本论文首先从网络体系结构的角度对传感器网络进行了研究，提出一种高效能耗、具备 自适应能力的传感器网络体系结构( e e w n a ) ，并提供了e e w n a 的构件化表示方法。本 论文还提出一种通用的传感器网络形式化描述模型，为拓扑控制和路由技术的研究提供了一 套标准的形式化描述方法。 拓扑控制技术的研究是本论文的研究重点，首先对传感器网络中拓扑控制问题进行了系 统分类和算法性能比较，为传感器网络拓扑控制算法和技术的研究建立起系统的理论框架。 提出一种基于度约束最小生成树问题的拓扑控制算法t c s ，与具有相同时间复杂度的同类 算法相比，t c s 所获得的拓扑结构在通信干扰和结构健壮性方面表现出更好的性能。本论 文采用自顶向下的方法研究传感器网络拓扑，运用复杂网络理论刻画传感器网络的统计特 性，根据统计特性要求寻找理想的拓扑形成方式，并结合到适应度模型，研究节点入网时功 率设置和链接选择行为。本论文还针对分簇方式拓扑控制算法的部署受限或可靠性缺乏等问 题，把分簇方式拓扑控制问题转化为携近似优化目标的簇划分及簇头选取两个子问题，提出 了一种启发式的分簇方式拓扑控制算法h t c c ，该算法创新之处在于权衡了空闲侦听能耗和 网络通信开销两方面能耗。 在路由技术方面，首先以网络生命期作为能耗效率的指标，采用网络流理论构建传感器 网络生命期模型，在该模型上考虑节点异跳单位传输代价的差异性，分析生命期最大化对路 由过程的需求。基于高效能耗传感器网络模型，从路由层面分析节点负载压力对网络生命期 的影响，并给出节点负载压力的启发式定义，研究能反映节点相对负载压力的路由策略。 最后对本论文的工作进行了总结，指出了需要进一步研究的内容和方向。 论文的研究内容作为无线传感器网络技术研究的重要组成部分，其研究结论可以应用于 多种传感器网络技术所构建的网络应用中，以提高能量的使用效率和增长网络生命期，同时 希望能为推动传感器网络的实用化进程和构建新型的传感器网络应用提供有益的参考。 关键词： 无线传感器网络；拓扑控制：路由算法；适应度模型；节点负载压力 分类号：t p 3 9 3 东南大学博士学位论文 高效能耗的传感器网络拓扑控制和路由技术的研究 a b s t r a c t t h ea d v a n c e so fr e c e n tt e c h n o l o g i e s ，f o re x a m p l e ，c o m m u n i c a t i o nt e c h n o l o g y , e m b e d m e n t t e c h n o l o g y , s e n s o rt e c h n o l o g ya n dw i r e l e s st e c h n o l o g y , e n a b l ew i r e l e s ss e n s o rn e t w o r k ( w s n ) a n dc o r r e l a t i v ea p p l i c a t i o n si nm a n yf i l e d s w s ni sq u i t ed i f f e r e n tf r o mt r a d i t i o n a lc o m p u t e r w i r e l e s sn e t w o r k so rm a n e ti nn e t w o r kf o r m c o m m u n i c a t i o nm a n n e r , r e s o u r c ea b i l i t ya n ds oo n t h ed e s i g no ft r a d i t i o n a lw i r e l e s sn e t w o r k sf o c u s e so nh i g hq u a l i t yo fs e r v i c ea n dh i 【g he f f i c i e n c y o fb a n d w i d t hu s e h o w e v e r ，t h ep r i m a r yo b j e c to fw s ni st om a x i m i z en e t w o r kl i f e t i m eb e c a u s e w s nc a n tg e te n o u g ha n ds t e a d yb a t t e r ys u p p l y t h en e t w o r kl i f e t i m er e f l e c t st h es t a t u so fc o s t e f f i c i e n c y , a n ds u g g e s t st h ee f f e c to ft o p o l o g ys t r u c t u r e ，r e s i d u a le n e r g y , r o u t i n gs e l e c t i o n t h e r e f o r e ，h o wt ob o o s tt h ee f f i c i e n c yo fe n e r g yc o s ti so n eo ft h eh o t s p o t si nr e c e n tw s n r e s e a r c ha r e a s f r o mt h ev i e wo fn e t w o r ka r c h i t e c t u r et h ew s ni ss t u d i e df i r s t l yo fa 1 1 a f t e rt h a t , a ne n e r g y e f f i c i e n t s e l f - a d a p t e dw s na r c h i t e c t u r e ( e e w n a ) a n di t sc o m p o n e n td e s c r i p t i o nm e t h o da r e p r o p o s e d ac o m m o nw s nf o r m a ld e s c r i p t i o nm o d e li sa l s op r o v i d e df o rt h er e s e a r c ho ft o p o l o g y c o n t r o la n dr o u t i n gt e c h n i q u e t h er e s e a r c ho nt o p o l o g yc o n t r o lt e c h n i q u ei st h ee m p h a s i so fo u rw o r k w ec l a s s i f yt h e p r o b l e m so ft o p o l o g yc o n t r o la n dp u tu pp e r f o r m a n c ec o m p a r i s i o n s u b s e q u e n t l y , as y s t e m i c t h e o r yf r a m e w o r ko ft o p o l o g yc o n t r o la l g o r i t h m sa n dt e c h n i q u e si s s e tu p at o p o l o g yc o n t r o l s c h e m eb a s e do ns i m u l a t e da n n e a l i n ga l g o r i t h m ( t c s ) i sp r o p o s e d t h er e s u l t e dt o p o l o g yw i t h l o wt o t a lp o w e rc o n s u m e d ，h i i g hr o b u s ts t r u c t u r ea n dl o wc o n t e n t i o nt h a tc a nb ec o n t r o l l e da m o n g n o d e sc a r lb eo b t a i n e db yt c s w ee x p l o r et h ed e f e c ti nd e p l o y m e n tr e s t r i c t i o na n dp o o rr e l i a b i l i t y i nt r a d i t i o n a ls c h e m e s ，t h e nt h e o r e t i c a l l ya n a l y z e da n dm o d e lt h er e q u i r e m e n to fc l u s t e r i n g , w h i c h u l t i m a t e l yt u r n st oac l u s t e r i n ga n dc l u s t e r - h e a de l e c t i n gp r o b l e mw i t ha p p r o x i m a t eo p t i m i z i n g o b j e c t i v e s ah e u r i s t i ct o p o l o g yc o n t r o la l g o r i t h mo fc l u s t e r ( h 1 c ) i sp r o p o s e da sas o l u t i o nt o t h ea b o v ep r o b l e m t h ei n n o v a t i o no fh t c cr e p r e s e n t st h eb a l a n c eb e t w e e nl i s t e nc o s ta n d c o m m u n i c a t i o nc o s t i nt h es t u d yo fr o u t i n gp r o t o c o l s ，w es e tt h en e t w o r kl i f e t i m ea st a r g e tf o re f f i c i e n c yo fe n e r g y c o n s u m i n gf i r s t l y , t h e nc o n s t r u c tt h ew s n l i f e t i m em o d e lb a s e do nn e t w o r kf l o wt h e o r y t h e m o d e lt a k e si n t oa c c o u n tt h eu n i tc o s td i f f e r e n c e sa m o n gn e x th o pn o d e s w ea n a l y z et h er o u t i n g r e q u i r e m e n tf o rl i f e t i m em a x i m i z a t i o n b a s e do nt h ee n e r g ye f f i c i e n tw s nm o d e l ，ah e u r i s t i c d e f i n i t i o no fn o d el o a dp r e s s u r ei sp r o p o s e d a tl a s tw es t u d yt h ee f f e c to fn o d el o a dp r e s s u r eo n n e t w o r kl i f e t i m ea n dp r o p o s ear o u t i n ga l g o r i t h mw h i c hr e f l e c t st h er e l a t i v el o a dp r e s s u r eo f n o d e s f i n a l l yw ec o n c l u d eo u rr e s e a r c hw o r k sa n dp u tf o r w a r dp o s s i b l ef u t u r er e s e a r c hd i r e c t i o n s r e s e a r c hc o n c l u s i o n sa l e a p p l i e dt ot h ea v a i l a b i l i t ye n h a n c e m e n t o fw s nn e t w o r k sa n d a p p l i c a t i o n s ，a n dh a v eg r e a tr e f e r e n c ev a l u et ot h ef a r t h e rr e s e a r c h k e y w o r d s ：w i r e l e s ss e n s o rn e t w o r k s ；t o p o l o g yc o n t r o l ；r o u t i n ga l g o r i t h m ；f i t n e s sm o d e l ；n o d a l l o a dp r e s s u r e i i 论文插图索弓 论文插图索引 w s n 系统示意图。2 数据在协议栈中流动示意图【1 6 】3 拓扑控制在协议栈中的位置。4 h a n d z i s k i 等人提出的w s n 体系结构10 s e n s o r s t a c k 的体系结构及各层对应功能1 1 环境定义所包括的具体内容1 2 高效能耗w s n 体系结构( e e w n a ) 。1 3 环境适应模块影响各层协议的示意图1 4 e e w n a 的构件化表示1 7 w s n 模型示意图( 分簇方式) 2 0 存在单向链接的l m s t 生成拓扑2 4 节点f 的闭包图2 5 d i s tr n g 算法示意图2 6 事件区域划分2 7 t o p d i s c 算法执行示例图2 9 c l u s t e r p o w 分簇通信示意图2 9 节点么的邻接域示意图一3 4 生成树与编码序列对应关系示例图一3 7 邻域变换示意图3 8 ( 回变化时t c s 性能曲线4 2 不同算法所获拓扑结构比较4 2 三种功率控制算法性能比较4 3 衰减系数a 对t c s 性能的影响4 4 报文发送失败比率4 4 节点连接示意图4 9 入网响应报文的结构描述5 l 传感器节点的p 厂r 网描述5 4 参数a 1 和屯对网络生命期的影响6 0 平均路径代价丁变化情况6 0 平均度值变化情况6 l 聚类系数c 变化情况。6 l 参数p 对w s n 生命期影响6 2 参数v 对w s n 生命期影响6 2 m 的取值对w s n 生命期的影响图6 3 单位时间侦听能耗对生命期的影响6 3 参数r m a x 和口变化对生命期的影响6 4 c f m 算法和l e a c h 算法性能比较6 5 簇规模与簇区域关系图7 0 节点保存信息的结构描述7 3 v i i 2 3 j 2 3 4 5 石2 3 4 5 石j 一2 3 4 5 石7 8 ，2 3 4 5 6 7 8 9 k n记乃，2 ，2 2 2 2 2 2 3 3 3 3 3 3王龟屯乱禾屯屯屯重孓i孓i孓孓蔓i i 孓i 王生& “图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图雕卧卧 东南大学博士学位论文高效能耗的传感器网络拓扑控制和路由技术的研究 图6 3 簇构建的示例图。7 4 圈6 4 兴趣事件发生概率对h t c c 性能的影响8 0 图6 5 三种分簇方式拓扑控制算法的性能比较8 1 图6 6h t c c 性能提升曲线8 1 图6 7 如变化与单位时间能耗关系图8 2 图7 1w s n 模型拓扑图8 4 图7 2 定向扩散路由的三个阶段8 8 图7 3s p i n 算法示意图8 9 图7 4r u m o r 算法示意图。9 0 图7 5l p r 算法示例。9 3 图7 6 仿真拓扑图9 4 图7 7 ( 仅，所变化时l p r 性能曲线9 5 图7 8 即变化时l p r 与e a r 性能比较9 5 图7 9 不同网络负载下的l p r 与e a r 的生命期变化9 6 v i l l 论文表格索弓 论文表格索引 表3 1 拓扑控制算法比较表3 0 表4 1t c s 算法实验参数表。41 表5 1c f m 算法实验参数表5 9 表6 1h t c c 算法实验参数表7 9 表7 1路由算法性质比较表9 0 表7 2l p r 选路示例表。9 3 i x 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名：删一日 期：堡里：! j 8 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学 位论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。 本人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外， 允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文 的公布( 包括刊登) 授权东南大学研究生院办理。 研究生签名：壶l 必堡 导师繇蝴日期：瑚& 绪论 第一章绪论 随着通信技术、嵌入式技术、传感器技术、无线技术的迅速发展和日趋成熟，具备通信 能力、计算能力和感知能力的微型传感器节点开始在世界范围内涌现。数目众多的传感器节 点协同工作，它们随机分布于监测区域周遭环境，通过自组织的无线通信方式构成无线传感 器网络【l l 【2 1 ( w s n ，w i r e l e s ss e n s o r n e t w o r k ) ，节点所采集的兴趣数据逐跳路由至汇聚节点， 以对客观物理世界进行感知和控制。w s n 具有易部署、自组织、高容错、可靠性等特点， 在国防军事 3 1 、环境监测和预报h i 5 】【6 】、智能家居【7 】【8 】【9 】、建筑物状态监控、空间探索、医疗 卫生【1 0 l 1 1 】1 1 2 】、城市交通【1 3 】【1 4 1 1 5 1 等诸多领域有着广阔的应用前景，这也使得w s n 成为当前 无线网络领域的一个热门研究方向，它的出现被视作信息感知和采集领域的一场革命。自 2 0 世纪9 0 年代末起，w s n 的研究工作己经引起世界发达国家军事部门、工业界和学术界 的广泛重视。学术界较为著名的研究项目有u cb e r k e l e y 的s m a r td u s t 项目，u c l a 的w i n s 项目，以及多所机构联合攻关的s e n s l t 计划等；美国国防部是较早开展w s n 研究的机构， 并已将部分研究成果付诸于战场应用；美国自然科学基金委员会2 0 0 3 年专l - l 铝j 定了w s n 研究计划，斥巨资支持相关基础理论的研究；英特尔公司于2 0 0 2 年宣布已确立了分三阶段 的w s n 研究方案，并最终将把研究成果应用于预防医学、环境监测、森林灭火等方面。此 外，加拿大、日本、英国、德国、意大利、芬兰等国家也相继展开了该领域的研究工作。在 我国目前正在进行的下一代互联网c n g i 的建设中，w s n 被给予了高度重视，该领域的研 究和部署工作也在相继开展。 最早的w s n 雏形可追溯到1 9 7 8 年，美国国防部高级研究所计划署( d a 砌) a ) 资助卡 耐基一梅隆大学进行分布式w s n 的研究，出现了采用点对点传输的传统传感器节点，并连 接了传感控制器，被称为第一代w s n 。此后随着相关技术的进步，w s n 获得了采集多种信 息信号的综合处理能力，并通过与传感控制器的相联，形成了具备信息处理能力的w s n ， 被称为第二代w s n 。上世纪末以来，应用现场总线技术并以无线通信方式所组成的、具有 智能化能力的第三代w s n 问世。第三代w s n 是本文的研究对象。 1 1 研究背景 w s n 在成网方式、通信模式、资源能力等方面与互联网具有很大差异，也有别于传统 东南大学博士学位论文 商效能耗的传感器网络拓扑控制和路由技术的研究 意义上的自组织网络，概而言之w s n 还具有能量稀缺、节点能力受限、应用相关性、数据 为中心等典型网络特征，不再遵循传统互联网中“端系统复杂、核心网络简单”的网络体系 结构原则，与传统i p 层路由转发和存储机制也不完全相同，此外节点的弱移动性也使得传 统白组织网络的设计无法完全契合w s n 的需求。 w s n 系统示意图如图1 1 所示，w s n 中通常包括普通传感器节点、汇聚节点( s i n k ) 和任务终端节点三种：常点。普通传感器节点的处理能力、存储能力和通信能力相对有限，通 常仅携带能量有限的电池，同时扮演着终端和路由器的双重角色，除了本地采集数据外，还 应具备数据存储、管理和融合的功能；汇聚节点能力较强，它连接w s n 和外部网络，通常 研究中不考虑它的能量和计算资源；任务终端节点负责数据的最终处理及控制信息的反馈。 特别地，为了便于对大规模网络的管理，出现了以部分节点管理其他：肖点并形成骨干网络的 分簇结构，分簇结构中管理节点称作簇头，被管理节点称作普通节点。 监测区域 互联嘲或卫 任务终端节点 ( 用户) 幽耩斟f 掣 i 数据采蜒糖块；l 徽船处理模块ll j 通倍填块 雾藐易誓：i 苏多，够“j ；供电搓块，j ：“。多：7 一，：j 7 图1 1w s n 系统示意图 图1 2 示意了分簇结构中数据在簇内节点协议栈中的流动情况【1 6 l ，图中节点1 和节点2 为普通节点，节点3 为簇头，节点1 首先观察到兴趣事件的发生，对其事件特征描述形成数 据报文，并予以发送，邻居节点2 在接收到该报文后忽略传输层和网络层直接置数据于m a c 层并标识为待发状态，当簇头节点3 收到该报文后，将在网络层选择合适的下一跳，报文转 交出本簇区域。 2 血 绪论 o t h e r e l u s t e r s 图1 2 数据在协议栈中流动示意图【1 6 】 传统无线网络的设计强调高服务质量的保障和高效带宽的利用，然而由于w s n 缺乏持 续、稳定的能量供给，通过高效使用能量来最大化网络生命期( 也是为了能够采集更多的兴 趣数据) 成为其重要设计目标。其中w s n 生命期通常定义为在w s n 系统的流量路由过 程中，最早因耗尽电池能量而失效的节点的生存时间。网络生命期体现了能耗的效率，从本 质上反映出网络拓扑结构、节点可用能量和路由选择等因素对生命期的影响，生命期极大化 是高效能耗w s n 的优化目标。w s n 的绝大部分能量消耗于通信传输环节【1 8 】，通信时节点 的能量消耗模型决定着能耗不仅与路径的选择相关，还与网络拓扑、数据流量、通信干扰等 诸多因素紧密相联。w s n 应该通过高效使用能量来最大化网络生命期，即注重网络的高效 能耗( e n e r g ye f f i c i e n t ) 特征。 针对高效能耗w s n 的研究主要集中于通信环节的关键技术，包括拓扑控制技术和路由 技术等方面。由于w s n 中一般不赋予节点自私行为能力，节点不能完全控制自身资源的损 耗，并且w s n 规模一般很大，无力承受整个网络尺度上的报文交互和协作开销，因此一般 采用分布式的算法。拓扑控制技术和路由技术本质上都可视为一种以延长网络生命期为导 向，形成并采用局部行动进而推动全局优化的w s n 的内在策略。现阶段的拓扑控制算法从 管理方式上可划分为节点功率控制和分簇方式拓扑控制两类，其中节点功率控制机制指通过 设置或动态调整节点的通信覆盖范围，达到网络拓扑连通的目的，同时尽量避免隐终端和暴 露终端【1 9 1 问题；分簇方式采用分层结构形成处理和转发数据的骨干网络，其中普通节点可 通过空闲休眠策略来达到节能目的。拓扑控制在协议栈中的位置如图1 3 所示，当拓扑控制 层发现邻居列表改变后会触发网络层的路由更新，当拓扑控制层对节点信号范围作出新判断 后会触发数据链路层的节点功率重新设置，当网络层发现路由被破坏或数据链路层发现新邻 居节点时也会触发拓扑控制层的运行。路由协议的职责在于将兴趣数据报文从采集节点逐跳 3 东南大学博士学位论文高效能耗的传感器网络拓扑控制和路由技术的研究 中继到汇聚节点，该过程可分为两个阶段：判断采集节点和汇聚节点间的路径；正确转发数 据报文。 a p p l i c a t i o n t r a n s p o r t n e t w o r k t p d a l e s i e x 咖 - ， t o p o l o g yc o n t r o l 屺u t i o n i s e t p ( 工 d a t al i n k p h y s i c s 图1 3 拓扑控制在协议栈中的位置 对于功率控制方式的拓扑控制，目前的研究往往关注所生成拓扑是否具有连通性、平面 性、稀疏性、节点度有界性等性质，从链路层面来看，健壮性也是功率控制中必须考虑的问 题，由于拥有较高剩余能量的节点对端间的通信链接具有较强的健壮性，选择相对健壮的链 接组成路由有益于w s n 生命期的延长。对于分簇方式的拓扑控制，现有研究一般采用普通 节点休眠、簇头轮换的方法，簇区域的形成尚无精确的定性依据。由于闲时侦听能耗和网络 通信开销的降低目标往往无法表现出完全一致的关系，侦听能耗的降低势必带来簇内通信代 价的上升，所以在簇区域划分和簇头选取时应兼顾侦听能耗和网络通信开销这两方面的因 素。路由协议研究的难点本质上归咎于节点的有限能力和网络的自组织性质之间的矛盾，网 络尺度上的局部拓扑和可用能量等信息的交互开销对于w s n 而言是难以承受的，而小尺度 信息交互所形成的单点瓶颈效应又显然不利于全局的高效耗能，此外流量生成的未知性也是 制约路由协议性能的关键因素，因此分析并依据节点对预测流量的负载能力进行路由规划将 成为一种较好的选路方式。除此之外，w s n 的研究还需关注可行性和应用相关性两个重要 方面，可行性归纳为以下几点：( 1 ) 算法的复杂度、所需额外报文量与节点有限的计算能力、 存储能力、通信能力形成的矛盾；( 2 ) 算法所需的基本信息( 如节点方位等) 或辅助设备( 如 g p s 等) 能否得以满足；( 3 ) 算法设计所基于的模型前提是否符合或接近真实部署环境；( 4 ) 节点硬件条件是否能支持算法的执行，如节点功率调节能力的设置粒度；( 5 ) 算法是否易于 部署，并具有分布式执行、网络规模可缩放性等能力；( 6 ) 网络性能是否较为稳定。应用多 样性是w s n 的另一个显著特征，不同应用场景对w s n 的硬件平台、软件系统以及网络协 议的需求迥异，国内外研究组织往往根据特定应用类型、运行环境独立进行研究与开发，未 对w s n 的共性和个性问题进行分析、抽象、归纳。本论文从兴趣事件发生的敏感程度对 4 绪论 w s n 的应用场景进行分类，归纳为如下几类场景：( 1 ) 兴趣事件发生概率较低的应用场景， 对应于观察兴趣区域中偶然事件的应用，如建筑物状态监控、环境监测等；( 2 ) 事件发生概 率较高的应用场景，对应于观察兴趣区域中事件发生概率相对较高的应用，如动物生态监测、 预报系统等应用；( 3 ) 对兴趣数据采集频率极高的应用场景，用于采集对兴趣区域变化非常 敏感的应用数据，一般属于事件实时性要求极高的应用，例如医疗护理和相关军事领域的应 用。在不同类型的应用场景下，某些环境参数( 环境参数的定义见第2 2 节) 对w s n 生命 期所造成的影响是不一致的，这在本文算法研究内容中将会有所涉及。 在拓扑控制技术和路由技术的具体研究中，增强对可行性、应用相关性的关注和研究能 直接提升算法性能和实际部署价值。本论文将以高效能耗为切入点，对具备可行性的w s n 拓扑控制和路由技术进行系统且细致的研究，并且结合应用相关性分析拓扑控制的共性目标 需求，力争为推动w s n 技术的实用化部署进程做出贡献。 1 2 论文研究对象及主要研究内容 本论文主要针对w s n 的拓扑控制及路由技术进行研究，其目标是通过w s n 中通信环 节相关的拓扑控制和路由技术的研究，提出具有一定现实部署价值的协议算法，提高w s n 能量消耗效率，解决w s n 生命期延长的问题。本论文的研究还将对新研究方法( 复杂网络 理论) 进行尝试和探索。 本论文在分析评价传统w s n 拓扑控制算法的基础上，归纳可行拓扑控制技术的共性特 点和基本要求，建立能演化为功率控制和分簇方式拓扑控制的w s n 通用拓扑控制模型。研 究兼具能耗低、信道干扰小、健壮性好的网络拓扑结构，设计相应的功率控制算法。分析大 规模w s n 的系统参数，结合拓扑需求探索所期望的网络特征。从全局能耗组成出发，利用 概率论等理论提出分簇理论模型，提出能权衡簇间能耗与簇内能耗的分簇机制。以网络生命 期作为能耗效率的指标，采用网络流理论构建w s n 理想生命期模型，在该模型上考虑节点 异跳上单位传输代价的差异性，分析生命期最大化对路由过程的需求。基于高效能耗w s n 模型，给出节点负载压力的启发式定义，并从路由层面分析节点负载压力对网络生命期的影 响，研究能反映节点相对负载压力的路由策略。本文的主要内容包括以下四个方面： ( 1 ) w s n 体系结构和形式化模型的研究。提出了一种结构分层、功能分面的高效能耗、 具备环境自适应能力的无线传感器网络体系结构( e e w n a ) ，从构件化框架模型及网络构 件等抽象级别对体系结构进行了描述。目前w s n 的研究还缺乏统一的形式化网络模型，这 东南大学博士学位论文 高效能耗的传感器网络拓扑控制和路由技术的研究 对系统地分析和解决相关研究中的问题不利。本论文研究能反映部署环境特征、通用的w s n 模型，该模型能为w s n 拓扑控制和路由技术的研究提供一个统一的问题描述和分析的理论 框架，有助于描述当前w s n 拓扑控制和路由技术研究中的各类问题，为我们今后的研究工 作提供了便利； ( 2 ) 功率调整方式拓扑控制算法的研究。比较、分析传统w s n 的功率调整方式的拓扑控 制方案，归纳可行拓扑控制技术的基本特点和要求，研究和建立w s n 功率控制模型；分析 大规模w s n 的拓扑目标需求，结合需求探索所期望的网络特征并研究 ，点功率与之的关联； 探讨隐式链接对m a c 层信道干扰的影响，研究兼具能耗低、信道干扰小、健壮性好的功率 控制算法。 ( 3 ) 分簇方式拓扑控制算法的研究。分别从节点行为和簇区域划分( 点与面) 两种角度对 分簇方式的拓扑控制算法进行了理论分析和算法设计。首先运用复杂网络理论刻画w s n 的 网络统计特性，分析w s n 节点的入网行为，并从节点入网行为角度对分簇方式下的拓扑控 制算法进行了研究；然后着重从簇区域划分的角度对拓扑控制算法进行了研究，基于分簇模 型提出相应的簇划分和簇形成策略，设计合适的分簇方式拓扑控制算法来权衡簇间与簇内两 种能耗。 ( 4 ) 高效能耗路由算法的研究。w s n 生命期与理想生命期的比值通常作为路由算法性能的 评判标尺之一，国内外研究机构针对w s n 拓扑和传输需求相对静态的特性，相继提出了多 种w s n 理想生命期模型，并将之转化为并发最大流问题，但该类模型未区分节点异跳上的 单位传输代价，本文建立了能区分节点异跳上传输代价差异性的w s n 理想生命期模型，运 用网络流理论分析相应的网络理想生命期；依据路由规划与生命期优化的本质联系，针对传 统能量路由算法复杂度高或效率低的弊端，设计能体现节点负载压力的自适应路由算法。 1 3 论文的组织结构 根据以上研究内容，本论文的组织结构安排如下： 第一章叙述了本论文的研究背景，概述了论文的研究对象及相关研究内容，列出了论文 结构的安排，并归纳出主要贡献。 第二章提出了一种结构分层、功能分面的高效能耗w s n 体系结构，对模型的设计理念、 主要特色、各层和各模块功能进行了详细阐述，并从构件化框架模型及网络构件等抽象级别 6 绪论 对体系结构进行了描述。 第三章首先给出了w s n 问题的形式化描述模型，并针对w s n 的拓扑控制问题、协议 和算法进行综述研究，对现有典型拓扑控制算法进行了分类比较。在此基础上，对当前重要 的w s n 拓扑控制协议和算法的技术特点进行了全面的分析和归纳。 第四章研究符合高效能耗要求的w s n 功率控制算法，本文针对传统算法所获拓扑的通 信干扰过高或结构健壮性较低等弊端，从理论上对拓扑需求进行了建模分析，最终转化模型 为度约束最小生成树问题，并设计了一种模拟退火算法处理该问题，进而提出了一种基于度 约束最小生成树问题的拓扑控制算法。 第五章运用复杂网络理论研究w s n 节点的入网行为，用平均路径代价、节点度及分布 和聚类系数3 个统计参数来抽象网络结构特点，并结合w s n 需求归纳出拓扑目标。提出符 合拓扑目标的适应度模型，在此基础上设计了一种包含3 个执行阶段( 链接形成、簇头确立 和簇区域划分) 的分簇方式拓扑控制算法，用数学期望手段对该算法进行了分析并得出了重 要结论，这些结论与算法仿真结果能够互相得到印证。 第六章主要针对传统分簇方式拓扑控制算法的部署受限或可靠性缺乏等弊端，从理论上 对分簇需求进行了分析，转化为携近似优化目标的簇划分和簇头选取问题，最终提出了一种 启发式的分簇方式拓扑控制算法，并对算法进行了仿真性能分析和验证。在本章的最后还对 第五章和第六章提出的两种算法进行了比较。 第七章针对传统的生命期模型未考虑节点异跳上单位传输费用的差异性，研究具有此特 征的w s n 的理想生命期，转化模型目标为带不等式约束的最大费用最大流问题，对该问题 从理论上进行了构造与求解。还提出一种基于节点负载压力的自适应路由算法，算法实现所 需的计算量、通信量较小，并通过仿真实验对算法进行了性能分析和验证。 1 4 论文主要贡献 本论文主要研究具有高效能耗特征的w s n 拓扑控制和路由技术，主要贡献可归纳为： ( 1 ) 提出了一种高效能耗、具备自适应能力的w s n 体系结构和一种通用的w s n 形式化 描述模型，对w s n 中拓扑控制问题进行了系统分类和现有算法的性能比较，为w s n 拓扑控制算法和技术的研究建立起系统的理论框架，为进一步开展研究提供了有效 的理论建模和分析方法。 ( 2 ) 提出一种基于度约束最小生成树问题的拓扑控制算法t c s ，与具有相同时间复杂度 7 东南大学博士学位论文高效能耗的传感器网络拓扑控制和路由技术的研究 的同类算法相比，t c s 所获得的拓扑结构在连通网络能耗、结构健壮性和通信干扰 方面表现出更好的性能。 ( 3 )采用自顶向下的方法研究w s n 拓扑，根据复杂网络理论刻画出w s n 拓扑的统计特 性，并依据统计特性要求寻找理想的拓扑形成方式，最终结合到适应度模型( f i t n e s s m o d e l ) ，研究节点入网时功率设置和链接选择行为，相应地设计了拓扑控制算法 c f m ，c f m 为数据的高效传输、均衡地消耗w s n 的能量和延长网络生命期提供了 良好的支撑基础。 ( 4 ) 空闲侦听能耗的降低往往会造成簇头间通信开销的增大，采纳了负载均衡的思想， 计算合适的簇区域规模和选举周期，并提出了一种启发式的分簇方式拓扑控制算法 h t c c ，该算法创新之处在于权衡空闲侦听和网络通信开销两方面能耗，以达到高 效能耗的目的。 ( 5 ) 以网络生命期作为能耗效率的指标，采用网络流理论构建w s n 生命期模型，在该 模型创新之处在于区分了节点不同异跳上单位传输代价。给出节点负载压力的启发 式定义，并从路由层面分析节点负载压力对网络生命期的影响，提出一种能反映节 点相对负载压力的路由算法l p r 。 w s n 在国防军事、环境监测和预报等诸多领域有着广阔的应用需求，如何高效地使用 有限能量、增强网络可行性、满足各类应用场景的共性需求是w s n 研究的主要问题，对这 些问题的研究有助于提升w s n 的性能和促进实用化进程。本论文的研究成果可为w s n 拓 扑控制和路由技术提供一整套新的理论参考模型和技术解决方案，应当具有一定的理论价值 和应用前景。 g w s n 体系结构及构件化描述 第二章w s n 体系结构及构件化描 述 在w s n 研究领域，学术界现有成果多集中于特定环境下对某项关键技术的关注，国内 外研究机构往往根据特定应用类型、运行环境独立进行研究与开发。网络体系结构是所有网 络系统的根本所在，对w s n 体系结构的研究不仅能从整体上把握w s n 这一新型网络形式， 还将对关键技术的研究产生深远的指导意义。从网络体系结构的角度来看，w s n 作为计算 机网络的一种新型形式，其体系结构既与传统网络有着很强的延续性，又具有与传统网络所 不同的多重特点，因此w s n 的体系结构必将赋予新的内涵和外延，从而以适应网络形式的 更新和需求的变化。目前关于w s n 体系结构的研究相对薄弱，根源在于w s n 的应用和部 署区域多样化特点。w s n 也属于一种极其复杂的分布、并发系统，前人工作未从网络体系 结构角度分析w s n 的目标需求，尤其没有充分重视高效能耗、环境自适应等特征在w s n 体系结构中体现的必要性。本章将借鉴其他形式网络如互联网、p 2 p 网络、a dh o e 网络、o v e r l a y 网络等的体系结构，以高效能耗为立足点兼顾其它特征，首先从体系结构角度分析、抽象、 归纳w s n 的共性和个性需求目标，然后将问题划分、归类、映射到关键技术层面，最后依 据网络需求给出w s n 体系结构的设计原则。 2 1 研究基础 当前学术界较为认同的w s n 协议通常由物理层、数据链路层、网络层、传输层和应用 层组成，其每层功能与互联网结构的对应层相似，除此之外传感器体系结构中还配以能量管 理、移动管理、任务管理、时间同步、定位技术等功能模块，分别针对w s n 的各项特点对 结构进行扩充和支撑。各协议或模块是息息相关的，如定位技术为基于节点位置信息的拓扑 控制或路由协议等提供位置信息；拓扑控制为路由协议提供必要的支撑平台，因此会直接影 响