（电工理论与新技术专业论文）无线传感器网络路由算法的研究与实现.pdf

a b s t r a c t w i t ht h ed e v e l o p m e n to fm e m st e c h n i q u e ，a n dt h eb e g i n n i n go fp o s t p ca g e ， m a n yn e wt e c h n i q u e sc a m eo u tf r o mb e h i n dt h es c e n e s ，i n c l u d i n gw i r e l e s ss e n s o r n e t w o r k s ，w h i c hi san e wp a r to fc o m p u t e rs c i e n c ea n dt e c h n i q u e ，a n da f r u i tc o m b i n g s e n s o rt e c h n i q u e ，e m b e d d e dc o m p u t i n gt e c h n i q u e ，d i s t r i b u t i n gi n f o r m a t i o np r o c e s s i n g t e c h n i q u ea n dw i r e l e s sc o m m u n i c a t i o nt e c h n i q u e ，h a v i n gab r i g h tf u t u r eo f t h e o r e t i c a l s t u d i e sa n da p p l i c a t i o n t h i sa r t i c l es e a r c h e sa n dd i s c o v e r st h ec o u r s eo ft h ef o r mo fw i r e l e s ss e n s o rn e t a n dr o u t e i n s p i r e db yc i t yp u b l i ct r a n s i ts y s t e m ，t h i sa r t i c l ep u t sf o r w a r d saw i r e l e s ss e n s o r a l g o r i t h mb a s e do nv i r t u a ls i n kn o d e i t c a t a l o g u e st h ed i g i t a lt r a n s i ti nn e ti n t ot w o p a r t s ，w h i c ha r et h ec o u r s et h a tm e m b e rn o d ee x p l o r e sb a c k b o n ea n dt h ec o u r s et h a t d a t af a s tt r a n s i t si nb a c k b o n e t h es c i e n t i f i cc h o i c eo fc i t yp u b l i ct r a n s i tl i n ei s b e n e f i c i a lt ot m 蘧cc o n d u c t i o n a sap r o j e c to fl i n em o d e li nw i r e l e s ss e n s o rn e t w o r k s m o d e l ，t h ec h o i c eo fb a c k b o n ei sm e a n i n g f u l t h ea l g o r i t h ml i s t sa n da n a l y z e st h r e e p o s s i b l eb a c k b o n ef o r m s ，w h i c ha r es i m i l a rd e s c a r t e sc o o r d i n a t em o d e l ，t r e em o d e l a n dd o u g h n u tm o d e l t h i sa r t i c l ea l s oa n a l y z e st h r e em o d e l sb ym a t h e m a t i c a lm o d e l a n dc o m p u t e rs i m u l a t i o n o nt h eb a s eo ft h ea n a l y s i sa b o v e ，t h i sa r t i c l ea p p l i e sv i r t u a ln o d et h e o r yi n t o m e m b e rn o d et os i m p l i f yt o p o l o g y , a n dc o n c l u d e st h a tc o m p l e t es u b g r a p hh a sal a r g e q u a n t i t yb yt h ec h a r a c t e ro f t h a tl i n kc i r c u i tr e d u n d a n c yi nn e ti sl a r g e ，a n dp o s e st h a t p u tc o m p l e t es u b g r a p ha n dh a m i l t o ng r a p hi n t oo n ep o i n tb yg r a p ht h e o r y , m a t r i x a n a l y s i sa n dp e r m u t a t i o n sm a dc o m b i n a t i o n sk n o w l e d g e i no r d e rt ol e a do u tt h ee m p h a s i s ，t h i sa r t i c l ec a t e g o r i z e sa n de x p l a i n sr o u t i n g a g r e e m e n tb e f o r ea l g o r i t h m ，a n dg e t sac l e a rc l u eo fr o u t i n gd e v e l o p m e n t ，a n dd e e p l y a n a l y z e sa n dr e a l i z e sn o d em e a s u r i n gt e c h n i q u et op r o v i d ep a r a m e t e rp r e p a r a t i o nf o r a l g o r i t h m 。 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 s ，v i r t u a ls i n k ，b a c k b o n e ，r o u t i n g 独创性声明 本人声明所量交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包台其他人已经发表 或撰写遥豹研究成梁，也不镪含为获褥盘鲞基茎缄其侄教育视构的学位或诞 书而使用过的材料。与我一嗣工作的同志对本研究所做的任何贡献均已在论文中 作了明确豹说明并表示了谢意。 学位论文作者箍名：拗产签字闩期：如嘭年r 月之日 学位论文版权使用授权书 本学位论文作者完全了霆擘基鎏盘堂有关僳蟹、使用学位论文的规定。 特授权蠢连盘芏可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名 物肃声 ， 签字日期：2 ，口年月j 日 聊签名：刃，内翻 签字日期：】。噶年月。日 第一审绪论 第一章绪论 1 1 无线传感器网络的特点 随着传感器技术、计算机和无线通信的发展，出现了一种新兴的计算机网 络无线传感器网络( w i r e l e s ss e n s o rn e t w o r k sw s n ) 。由于其广泛的应 用前景，无线传感器网络受到越来越多研究人员的重视”“”。无线传感器网络 是由一组传感器节点以a dh o c 方式组成的无线网络，其目的是协作地感知、收 集和处理传感器网络所覆盖的地理区域中感知对象的信息，并传递给观察者。 这种传感器网络集中了传感器技术、嵌入式计算技术和无线通信技术，能协作 地感知、监测和收集各种环境下所感知对象的信息，通过对这些信息的协作式 信息处理，获得感知对象的准确信息，然后通过a dh o c 方式传送到需要这些信 息的用户。由于无线传感器网络的硬件资源是十分有限的，且其工作环境通常 是一些资源受限的地方，这给理论研究人员和工程技术人员提出了大量具有挑 战性的研究课题”1 。本章将通过多方式多角度来介绍无线传感器网络，力求得 出一个清晰的脉络。 1 1 1 无线传感器网络通信协议特点 网络分层的思想是设计协议的基础思想，它使得设计者能够把一个复杂的 问题划分为几个子问题并逐个加以解决。网络协议分层的思想中有两个模型 占据了该领域的主导地位，第一个是基于国际标准化组织i s o 早期所做的工作， 称为i s o 可丌放系统互连参考模型( o s i ) ，另一个是基于t c p i p 协议族的分层 参考模型。参考这两个模型的层次划分，以及其他相关文献，本章这里给出一 个传感器网络分层参考模型，并分析三种模型之l h j 的相互关系。 o s i 七层协议包括物理层、链路层、网络层、传输层、会话层、表示层、 应用层。t c p i p 协议包括建立在硬件层上的四个软件层，分别是网络接口层、 网络层，运输层、应用层。本章参考前述两个模型将无线传感器网络协议族分 为四层，分别是物理层、m a c 层、网络层和应用层，参考图1 - 1 。 第一帝绪论 w s n 协议分层模犁0 5 1 啡议分横掣t c p i p 脚议分从模巾 图卜lo s i 、t c p i p 、w s n 协议层次对照图 物理层：对应o s i 模型中的物理层，对应t c p i p 模型中的网络接口层的一 部分。物理层主要负责感知数掘的收集，并对收集的数据进行抽样，信号的调 制解调、信号的发送和接收、功率控制等任务。物理层最重要的目的是要达到 在任意相邻两个节点之间建立字节级的无线链路，为高层提供服务。目前电子 电路的技术水平在传送和接收相同长度的比特数掘时，发射数掘所需的能量 接收数据所需的能量 c p u 处理所需的能量。考虑到无线传感器网络节点的能 量是十分有限的，节能对延长网络的生存时| 日j 至关重要。在物理层上传输数据 的单位是字节。 m a c 层：对应o s i 模型中的数据链路层，对应t c p i p 模型中的网络接口层的 一部分。对应局域网模型o s i 给出的参考模型将数据链路层分为媒体接入控制 层( m a c ) 和逻辑链路控制层( l l c ) 。其中m a c 子层负责解决介质访问和硬件 相关的问题，在不可靠的链路上提供可靠的链路连接，对l l c 子层及其上层提 供相对硬件透明的服务。m a c 层提供的是点到点的服务而l l c 子层提供的是端到 端的服务，以多跳为主的无线传感器网络的l l c 子层已经相当弱化了，可以融 入高层，而m a c 层是起到了保证各类无线传感器网络高效通信的作用，是研究 的重点之一。在m a c 层上传输的数掘单位是帧“”。 网络层：对应o s i 模型中的网络层和传输层，对应t c p i p 模型中的网络层 ( i n t e r n e t 层、i p 层) 和传输层。o s i 中网络层解决的是交互的定义，负责路 由功能，又叫通信子层；传输层负责建立端到端的可靠有序传输。t c p i p 模型 中i p 层最重要的功能也是选路功能，因为以i p 地址作为源和目的地址，所以是 以机器为一端的；传输层任务是在两个机器上的不同程序之日j 提供端到端的服 务( 在i p 地址的基础上增加了端口号作为各种应用程序的识别) 。与前两者对 比，无线传感器节点自身结构简约、功能单一的特点决定了路由功能是这一层 的最重要功能。因为w s n 中端到端的概念通常只是指事件发生区域节点与槽节 第一带绪论 点之闯，瑟爨鼹传送颞廖没骞严搐静要求，孬翥对霹苇点一毁哭蠢一个应用 程序运行，带点地址可叛淮决定应用程序地址。基于以上三点考虑可以将无 线传感器网络的传输层弱化并融入网络层。网络层的主要任务是发现和维护路 幽。因为多跳通信比直接邋信更加节能，这也正好符含数掘融合和协嗣信号处 理翡需要。在笼线传惑器网络孛，节点一毅帮采矮多筑路由来连接傣源窝蔷窿。 但是，现存的a dh o c 网络多跳路由协议如a o d v ( a dh o co n d e m a n dd i s t a n c e v e c t o r ) “”哪! 、t o r a ( 临时按序路由算法) 和d s r ( 动态源路由协议) 等，一般不 逑含无线转慧器网络鹣特杰，无线砖黪撰网络必须秀发瘸子自己瓣路出按议。 攀实上，由于凭线传感器网络具有很强的具体应用背豢，一个传感器网络通常 怒为某个具体的应用场合设计的。因此，很难采用通用的路由协议。和传统的 以地址为中心的路由协议举样，无线传感器网络的鼹由协议是以数据为中心 翡，没有一个全局翡标设，一救是基予瓣缝戆寻蛙方式，逶鬻采蠲按需静被动 妓路由方式。常见的以数搠为中心的路幽协议有s p i n ，d i r e c t e dd i f u s i o n 等。 另外一类常见的路由协议怒基于分簇的层次化路由执议，常见的肖l e a c h 、 t e e n ( t h r e s h o l ds e n s i t i v ee 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 ) 删。 关于路由层的研究是无线传感器网络研究领域的一个十分活跃的分支，本论文 也是在研究了大量路由协议的基础上提出一种基于虚拟槽节点的路由协议。在 网络层上传输豹数据单位怒分组。 应用层：瓣应o s i 模型巾的会话层、表示凄、应瓣层，对雳影l p 模型孛 的应用层。 因为无线传感器网络自身的定位是面向底层的，对予应用层涉及 极少，建立好网络层之后棚当于每一个带点都具有路幽探测功能了，整个网络 豹逶售滋议栈嚣经基本竞域了。建立在两络层土豹捺议主要是嚣囊瓣采集到豹 数据进行管联簿简单处理工作。应用层协议的设计要力求简单实用，这样j 能 减小对底层的压力。设计时候也是根据释种实际应用以及配备的传感器节点的 功能来实现，携议中数据镪长度一般应该当控刳在十几个字节之斑。 1 ，1 2 硬件结构特点 组成无线传感器网络的硬仕部分，本文把它们称为节点。从逻辑上说节点 懋少需要两个独立模块缀成，分瘸是逶倍模块和传感嚣模块。传感嚣模块受责 对某一特定物理量的侦测与鉴别，是面向实际应用的。传感器模块根据自身网 络使用特点来选择配置传感器元件的类烈。传感器模块侧重的是应用，可以说 镗么样豹壅震场合决定了搜翅嚣么撵熬转惑器，簧感嚣模块数浸诗决定了w s n 节点的用途。通信模块负责节点之问的笼线通信功能。无线传感器网络的强大 第一帝绪论 不在于单独节点功能的强大，而在于其数量的庞大。巨大数量的节点决定了其 对通信模块的较高要求，所以通信模块的设计是w s n 节点成败的关键。另一个 重要组成部分是电源提供模块，它并非一个独立系统而是为其他模块服务的， 基于无线传感器网络节点的不可回收性，这一服务模块被提到了的所未有的高 度，这是节点设计成败的基础( 保障) 。除了这些基本的模块外，一些具有特 殊功能的节点还配有相对复杂的其他模块，槽节点一般要配有基于g p r s 、卫星 通信或者有线介质的远传模块；用作节点定位参考的锚节点一般要配有定位系 统。这些特殊功能的模块不是仅仅服务于本身所在母体节点而是要服务于整个 网络，所以不需要所有节点配备此类模块。此外基于不同用途的节点也可能要 配备其他模块，比如可移动系统需配备运动执行机构；有些节点可以配备电源 再生装置等等。图卜2 表示出的是节点硬件结构示意图。 i扩腥接u 图1 2 节点组成示意图 1 2 无线传感器网络与其他网络的区别 1 2 1 从i e e e 的角度区分 ( 1 ) i e e e 8 0 2 电气和电子工程师协会( i n s t i t u t eo fe l e c t r i c a la n de l e c t r o n i c s e n g i n e e r si e e e ) 是世界上著名的专业组织，每年出版大量的技术杂志并召丌 很多会议。i e e e 的前身a i e e ( 美国电气工程师协会) 和i r e ( 无线电工程师协 会) 成立于1 8 8 4 年。1 9 6 3 年1 月lh a i e e 和i r e i f 式合并为i e e e 。自成立以来i e e e 一直致力于推动电工技术在理论方面的发展和应用方面的进步。作为科技革新 的催化剂，i e e e 通过在广泛领域的活动规划和服务支持其成员的需要。i e e e 计算机委员会下设的i e e e8 0 2 负责制定电子工程和计算机领域的标准。 第一章绪论 i e e e 8 0 2 又称为l m s c ( l a n m a ns t a n d a r d sc o m m i t t e e ，局域网城域网标 准委员会) ，致力于研究局域网和城域网的物理层和m a c 层规范，对应o s i 参考 模型的下两层。因为i e e e 的权威性和标准性，各种标准都希望得到i e e e 8 0 2 工 作组的批准，此节就是从i e e e 8 0 2 工作组对无线网络的划分的角度来指出无线 传感器网络的自身定位及与其他网络的关系。 l m s c 执行委员会( e x e c u t i v ec o m m i t t e e ) 下设工作组( w o r k i n gg r o u p ) 、 研究组( s t u d yg r o u p ) 、技术顾问组( t e c h n i c a la d v i s o r yg r o u p ) 。曾经 设立的多个s g 已经合并n w g 中，目前活跃的w g 和t a g 如下： 8 0 2 1 ：高层局域网协议h i g h e rl a y e rl a np r o t o c o l s 8 0 2 2 ：逻辑链路控s u l o g i c a ll i n kc o n t r o l 8 0 2 3 ：以太网e t h e r n e t 8 0 2 4 ：令牌总线t o k e nb u s 8 0 2 5 ：令牌环t o k e nr i n g 8 0 2 1 l ：无线局域网w i r e l e s sl a n 8 0 2 1 5 ：无线个域网w i r e l e s sp e r s o n a la r e an e t w o r k 8 0 2 1 6 ：宽带无线接入b r o a d b a n dw i r e l e s s a c c e s s 8 0 2 1 7 ：弹性分组环r e s i l i e n tp a c k e tr i n g 8 0 2 1 8 ：无线管制r a d i or e g u l a t o r yt a g 8 0 2 1 9 ：共存c o e x i s t e n c et a g 8 0 2 2 0 ：移动宽带无线接入m o b il eb r o a d b a n dw i r e l e s sa c c e s s ( m b w a ) 8 0 2 2 1 ：媒质无关切换m e d i ai n d e p e n d e n th a n do f f ( 2 ) i e e e 无线通信领域 i e e e8 0 2 目前在无线领域主要有四个工作组：8 0 2 1 1 、8 0 2 1 5 、8 0 2 1 6 、 8 0 2 2 0 。在每个工作组下又设置了任务组( t g ) 。 8 0 2 1 1 无线局域网 已经通过的标准：8 0 2 1 1 、8 0 2 1 l a 、8 0 2 1 l b 、8 0 2 1 l g 、8 0 2 1 1 f 、8 0 2 1 1 d 。 正在研究的标准：8 0 2 1 l i 。 8 0 2 1 5 无线个人域网w p a n ( w i r e l e s sp e r s o n a la r e an e t w o r k ) i e e e8 0 2 1 5 1 ：就是所谓蓝牙技术，这是一个中等速率、近距离的w p a n 网络标准，通常用于手机、p d a 等设备的短距离通信： i e e e8 0 2 1 5 2 ：公用i s m 频段内无线设备的共存问题，研究i e e e 8 0 2 1 5 1 与i e e e 8 0 2 1 5 1 l ( 无线局域网标准，w l a n ) 的共存问题； i e e e8 0 2 1 5 3 a ：u w b 标准； 第一章绪论 i e e e8 0 2 1 5 3 b ：w p a n 维护： i e e e8 0 2 1 5 4 ：研究低于2 0 0 k b i t s 数掘传输率的w p a n 应用。 8 0 2 1 6 宽带无线接入( 无线城域网) 已经通过的标准：8 0 2 1 6 、8 0 2 1 6 a 、8 0 2 1 6 c 、8 0 2 1 6 2 、8 0 2 1 6 一致性 测试。 正在研究的标准：8 0 2 1 6 d 、8 0 2 1 6 e 8 0 2 2 0 移动宽带无线接入 处于提案征求阶段，还处于标准研究初期 i e e e 的权威性影响了其他组织对无线传感器的观点。8 0 2 1 5 4 正是面向无 线传感器网络的标准，i e e e 将其列为i f 式标准之一，体现出其对w s n 的重视程 度。从i e e e 8 0 2 工作组的分工来看，它本身就是面向低传输速率，低能耗的低 端网络，从中也可以看到无线传感器网络同其他无线网络的区别，它与8 0 2 1 1 无线局域网不同，是面向低传输速率的个人域网络，这也提示设计者，对无线 传感器网络的研究要有很强的方向性，一味地追求高效快捷的传送速率和单一 节点的强大功能是不符合它的设计初衷的。 1 2 2 现有网络划分 1 2 2 1 从覆盖范围来分 ( 1 ) 无线局域网 无线局域网( w i r e l e s sl o c a la r e an e t w o r k ，w l a n ) 顾名思义是一种借 助无线技术取代以往有线布线方式构成局域网的新手段，可提供传统有线局域 网的所有功能，它是计算机网络与无线通信技术相结合的产物，它支持较高传 输速率( 2 - - 5 4 m b i t s ，甚至更高) ，利用射频无线电或红外线，借助直接序列 扩频( d i r e c ts e q u e n c e s p r e a ds p e c t r u m ，d s s s ) 或跳频扩频( f r e q u e n c e h o p p i n gs p r e a ds p e c t r u m ，f h s s ) 、高斯最小频移键控( g a u s sm i n i m u m s h i f t k e y i n g ，g m s k ) 、正交频分复用( o r t h o g o n a lf r e q u e n c yd i v i s i o n m u l t i p l e x i n g ，o f d m ) 等技术，甚至将来的超宽带传输技术u w b t ，实现固定、 半移动及移动的网络终端对i n t e r n e t 网络进行较远距离的高速连接访问。 1 9 9 7 年6 月，i e e e 推出了8 0 2 1 l 标准。丌创了w l a n 先河，目f i i w l a n 领域主 要是i e e e 8 0 2 “x 系列与h i p e r l a n x 系列两种标准。 ( 2 ) 无线城域网 无线城域网( w i r e l e s sm e t r o p o li t a na r e an e t w o r k ，w m a n ) 通常指覆盖一 第一章绪论 座城市的无线网络。无线城域网络技术使用户可以在一个大城市的不同地点建 立无线联系，如在不同的办公楼问或不同的校园| 日j 进行无线联系，而不必花费 商昂的费用铺设光缆、电缆和租赁线路。例如，在一个城市范围内，实现各个 大学校园、企业和社会组织之| 日j 等的无线网络连接。w m a n 既可以使用无线电 波也可以使用激光等来传送数据。提供给用户以高速访问因特网的无线访问网 络带宽，其需求正日益增长。另外，当有线网络d d n ( d i g i t a ld a t an e t w o r k 数字数据网) 线路缺乏时，w m a n 还可以作为有线网络的后援。目i i 常见的w m a n 协议主要是1 9 9 9 年公确的8 0 2 1 6 协议。 ( 3 ) 无线广域网 无线广域网络( w i r e l e s sw i d ea r e an e t w o r k ，w w a n ) 技术可使用户通过远 程公共网络或专用网络建立无线网络连接。通过使用无线服务提供商所维护的 若干天线基站或卫星系统，这些连接可以覆盖广大的地理区域，例如若干城市 或者国家( 地区) 。目前的w w a n 技术主要是第2 代( 2 g ) 系统。2 g 系统主要包 括全球数字移动电话系统( g l o b a ls y s t e mf o rm o b i l ec o m m u n i c a t i o n s ，g s m ) 、 蜂窝式数字信息包数据( c e l l u l a rd i g i t a lp a c k e td a t a ，c d p d ) 和码分多路访 问( c o d ed i v i s i o nm u l t i p l ea c c e s s ，c d m a ) 等。 ( 4 ) 无线个域网 无线个域网( w i r e l e s sp e r s o n a la r e an e t w o r k ，w p a n ) 主要服务于个人 工作、娱乐或家庭内对无线网络连接的需要。相对于传统局域网的概念，个人 网络的覆盖范围更小，目标更单一。让用户在“个人使用空日j ”( p e r s o n a l o p e r a t i n gs p a c e ，p o s ) 主要以无线的形式连接诸如个人数字助理( p e r s o n a l d i g i t a la s s i s t a n t ，p d a ) 、蜂窝电话或笔记本电脑等各种个人应用装置。使 用的协议包括i r d a 红外协议和b l u e t o o t h 蓝牙协议或w i - f i 等短距离无线通 信协议。 无线个人网络的概念是在无线网络中最近j 出现的。在w p a n 内，所有支 持无线通信协议的设备可以在一瞬问组成一个局域网，实现共享资源。 无线传感器网络属于无线个域网范畴。 1 2 2 2 从对等情况来分 无线网络可以分成客户月臣务模式网络与对等网络。客户服务模式网络一 般都是星型结构，每一个节点之问不能直接通信，需要中继器或者服务器进行 数据交换，比如无线局域网和蜂窝无线通信网络。而对等网则不同，网络中任 意两个设备只要在通信范围之内就可以相互通信。 第一审绪论 ( 1 ) 客户服务模式网络 此类无线网络中总是需要一些设备充当服务器，充当服务器的设备必须一 直处于运行状态，等待客户端发起的连接，客户端也只能直接和服务器进行数 掘交换而任意两个客户端之间不能进行数掘交换。8 0 2 1 1 无线局域网和蜂窝 通信网是此种网络的典型应用。无线局域网中，设备入网需要一个a p ( a c c e s s p o i n t ) ，a p 其实是一个简称，基本有三种类型：1 、无线接入点，2 、无线网桥， 3 、无线路由器。其中1 相当于一个无线的h u b ，或说是无线接收器。2 的功能 要稍强些，除了有1 的功能外，它还可以无线桥接，无线中继。而3 就相当于 是1 和一个路由器的一体化产品。要连入网络的设备需要一个a p 节点来同无 线集中器进行数掘交换。蜂窝系统和8 0 2 1 l 系统的类似，建立若干的基站， 基站之间通过光纤相连，移动台( 手机) 只能和基站之间相互通信，而移动台 ( 手机) 之间不能直接相互通信。以上两者中无线a p 和基站分别充当了服务 器的角色，而p c 和手机充当了客户端的角色。 ( 2 ) 对等网络 与客户服务模式网络不同，对等网中不存在绝对的服务器和绝对的客户 端，每一个节点既可以充当服务器也可以充当客户端，节点功能是均等的。任 意两个节点只要在通信范围内就可以直接相互通信，不需要其他设备进行中 转。任意两个节点都是通过a dh o c 方式进行连接。无线对等网近期得到了迅 猛的发展，典型的对等网应用有蓝牙和无线m e s h 网络等。 无线m e s h 网络是一种与传统的无线网络完全不同的网络。传统的无线网 络必须首先访问集中的接入点( a p ) 才能进行无线连接。这样的话，即使两个 8 0 2 1 l b 的节点实际上就是互相挨着，它们也必须通过接入点才能进行通信。 而在无线m e s h 网络中，每个节点都可以与一个或者多个对等节点进行直接通 信。“m e s h ”这个词原来的意思就是指所有的节点都互相连接，当然实际上绝 大多数现代的m e s h 网络只是通过部分节点相互连接。m e s h 网络技术一度曾是 一项军方技术，随着人们对8 0 2 1l a 、b 和g 等l a n 技术了解的深入，m e s h 网 络才逐步成为企业界和消费者瞩目的焦点。其实因特网的构架已经就是一个 m e s h 网络的结构。当任意两个节点之f h j 的一条链路失效后，路由器会经由一 个或多个别的路由器找到一条另外的替代路径，这其实就体现了m e s h 网络的 思想。 无线传感器网络就属于这种对等网范畴。 第一章绪论 1 3 论文组织结构及创新点 1 3 1 选题意义 无线传感器网络是一个新兴的研究领域，国内外的研究人员已经取得了一 些初步的研究成果，开发出一些无线传感器网络原型系统，在相关理论上也有 较为广泛、深入的研究。但是，在一些关键理论上仍有许多问题需要解决，同 其他领域的合作仍然有着广泛的应用l j 景。 本文从实际应用出发，在现实中受到各种启发，并将此运用到对无线传感 器网络的研究分析中。例如第三章就是通过对城市公交模型的观察受到启发， 而总结出的一种路由算法。能把其他领域的知识映射到无线传感器网络中，并 以此来解决相应的问题，往往能丌辟一条崭新的道路。这向人们昭示着世界是 统一的，并有机联系在一起的这一基本哲学原理。 1 3 2 论文组织结构 第二章：在介绍无线传感器网络路由协议的研究现状的基础上，按照各种 路由协议的基本特点将其分类，从中就可以总结出路由协议的一个清晰的发展 状况。该章后半部分介绍了定位与测距的技术，重点是测距，为第三章提出的 基于虚拟槽节点的路由算法做准备。因为本论文的主要算法以距离作为已知参 数，这章的内容作为研究成果直接提供给第三章。 第三章：这是本文主要算法，提出一种基于虚拟槽节点的路由算法。算法 思路是将单一槽节点扩充为一个包含槽节点的集合来代替原来的实际槽节点。 该算法将路由分成两部分，其一是成员节点探测组成虚拟槽节点的中继节点 ( 以虚拟槽节点为目的地址) ，其二是数掘在虚拟槽节点内的传递( 以实际槽 节点为目的地址) 。本章的主要着重于通过建立多种数学模型来分析虚拟槽节 点的三种组成形式，即类笛卡儿坐标结构、树型结构、环形结构。为了算法的 优化执行，需要获得一些地理位置和距离的参数，关于这些参数的获得笔者作 为第二章的研究成果部分给出相应形式。 第四章：这是将第三章虚拟节点的概念的扩充，将具有同一性质的节点集 合抽象成一个虚拟节点用来简化网络拓扑。用无线通信网络的圆盘图模型束分 析，因为无线传感器节点数量巨大，网络对应的图中必然含有大量节点和边的 冗余的特点，造成了拓扑结构复杂，具体而占边的大量冗余造成了图中存在大 量完全子图，通过适当分析将完全予图虚拟为一个点或者低阶完全子图用以达 到简化图结构的目的。最后根据完全图和i - l a i n i i t o n 图的特点又提出了将 第一辛绪论 h a m i l t o n 子图替代完全子图进行网络结构化简的方法。 1 3 3 论文创新点 ( 1 ) 在深入分析当前无线传感器网络路由协议的基础上，结合生活实践提出 了基于虚拟槽节点的路由算法，并根据主千网的发展形状不同，将其分成三种 不同形式模型分别加以讨论。 ( 2 ) 根掘无线通信网络的圆盘图模型理论，把组成网络的最基本元素由节点 上升为完全子图( 单一节点视为最简单的完全图) ，并以完全子图为单位对网 络拓扑进行化简。提出了普通节点在逻辑上合并的几种方法。 ( 3 ) 在分析网络节点密度时，将微积分元素法与概率论知识相结合，作为切 入点和分析工具；在分析网络拓扑状态时，把矩阵分析的方法和排列组合的观 点相结合作为分析工具。 ( 4 ) 通过电磁波传播的基本理论，并在分析了各种通过无线测距方法的基础 上，以c c l 0 0 0 为平台着重分析了基于r s s i 的测距方法。 第二章烙出oj 测即 第二章路由与测距 2 1 当前路由协议分类 路由协议负责将数掘分组从源节点通过网络转发到目的节点，它主要包括 两个方面的功能：寻找源节点和目的节点之间的优化路径，将数据沿着优化的 路径正确转发。h dh o c 、无线局域网等传统无线网络的首要目标是提供高服务 质量和公平高效地利用网络带宽，同时提高整个网络的利用率，避免产生通信 拥塞并均衡网络流量等，而能量消耗问题不是这类网络的重点。在无线传感器 网络中，节点的能量一般有限而且一般没有能量补充机制，因此路由协议需要 高效利用能量，传感器网络具有能量优先、基于局部拓扑信息、以数据为中心、 应用相关等特点“。 针对不同的传感器应用，研究人员提出了不同的路由协议。但到目前为止， 仍然缺乏一个完整清晰的路由协议分类，本章从各种路由协议的本质特点为出 发点，大致将路由协议分成下面几类。以下类别并不是互斥的，不同种类的划 分通常是你中有我，我中有你，本文关注的并不是划分的标准而是每一类路由 协议中表现出的基本特点，表现为无线传感器网络路由协议发展的历程。目前 主要的路由协议有一下几类。 2 1 1 传统平面拓扑路由 基于平面网络的路由是最简单的路由形式，其中每一个点都具有对等的功 能。最有代表性的算法是泛洪算法。 泛洪算法：该算法的主要思想是由槽节点发起数据广播，然后任意一个收 到广播的节点都无条件将该数据副本广播出去，每一节点都重复这样的过程直 到数掘遍历全网或者达到规定的最大跳数。算法不用维护网络拓扑结构和路由 计算，实现简单，但是也会带来一些问题，最主要的是内爆( 如图2 一1 ) ，重 叠( 如图2 2 ) 以及资源盲点等。 g o s s i p i n g “”：该算法是泛洪算法的改进，与泛洪算法不同，每一个节点 并不是向所有的邻居节点发送数掘包的副本，而是随机选择一个或者几个邻居 来转发数据包。由于一般无线传感器网络的链路冗余度较大，适当选择转发的 邻居数量，可以保证几乎所有节点都可以接收到数据包。 第一：幸路由j 测罡 | 图2 - 1f l o o d i n g 的消息“内爆”问题图2 2f l o o d i n g 的消息“重叠”问题 2 1 2 新型层次拓扑路由 这是与平面路由相对的概念，主要特点是出现了分簇的结构。相对平面结 构中每一个点都是对等的，具有分簇结构的层次拓扑路出将节点分成若干个集 合( 簇) ，每一个簇有一个节点充当簇头节点，簇头节点负责管理簇内事务以 及与其他簇进行数据交换。簇内其他节点仅仅与簇头节点进行数据交换，而与 其他簇成员不发生联系。这样簇内成员组成一个低层次的节点集合，通过相应 算法进行数据交换，所有簇头节点组成一个高层次的节点集合，各个簇头之间 再通过相应算法进行数据交换。其最有代表性的算法是l e a c h 算法。 l e a c h 算法( l o we n e r g ya d a p t i v ec l u s t e r i n gh i e r a r c h y ) “”：该算法 是分簇结构的算法，它定义出了轮的概念。每一轮有仞始状态和稳定运行状态 两种模式，初始态是用来根掘算法随机选择簇头节点，同时广播自己成为簇头 节点的事实，其他节点收到广播信号后通过判断信号的强弱来决定加入哪个 簇，并告知簇头节点。稳定工作时候，节点将信息传递给簇头节点，然后簇头 节点将信息传递给槽节点。当一轮完成后重新选举簇头。该算法通过轮流担任 簇头的方式来均等的消耗能量，达到延长网络生存周期的目的。但是因为每一 个节点都可以成为簇头，也即都可以将数掘直接传给槽节点，该算法只是适用 于单跳的小型网络。 t o p d is c 算法：此算法在组网阶段分成三色算法和四色算法，分别用各种 颜色来表示节点所处的状态。以三色算法为例，分为白色，灰色和黑色三种节 点。白色是状态未定节点，初始所有节点都是白色，黑色表示簇头节点，灰色 为成员节点，其组网过程为： ( 1 ) 初始进行拓扑探测的节点先变为黑色，并且广播拓扑探测数据包。 ( 2 ) 每一个白点当收到一个柬自黑点的拓扑探测信息则自己变为厌色。所有 灰色点在一个随机延时后向其邻居广播它刚收到的探测数掘包。此随机延时与 第一章路山j 测黔 该点以及发给它数据包使其由白变灰的黑点i 廿j 的距离成反比。 ( 3 ) 每一个白点在收到灰点发过来的探测包后，经过一个随机延时后变成黑 点转发探测包。如果在这过程中它收到另一个黑点发过来的探测包，则变为灰 点。同样该随机延时反比于两个节点之问的距离。 ( 4 ) 当节点变黑或变灰后则不在理会其他节点的探测包。 组网成功后由黑点定义一个簇，并出该黑点充当簇头节点，灰点为成员节 点，并且清楚自己的簇头节点。所有黑点以及满足一定条件的灰点( 算法中称 为活跃传输节点a c t i v ef o r w a r d i n gn o d e ) 组成一棵树，该拓扑树负责信息 的传送。 2 1 3 基于数据为中心的路由协议 最有代表性的是s p i n 算法和d d ( 定向扩散) 算法，以数据为中心的路由算 法与传统网络路由算法最大的区别表现在： ( 1 ) 以数据为中心，网络中的任务是在对数掘进行命名的基础上进行的。 ( 2 ) 数据是在相邻的节点之间进行扩散的，以叩算法为例，d d 算法中每 一个节点都是一个端，都可能是数掘的目的节点，都能进行数掘处理。d d 算 法中没有固定的路由路径。 ( 3 ) 节点遵循本地交换的原则，以d d 算法为例，节点只需要与邻居进行 数据交换而不需对整个网络的拓扑了解。 定向扩散算法 1 5 1 ：是以数掘为中心的路由协议发展过程的里程碑。e s t r i n 等人提出了定向扩散模型来进行数掘分发，它与已有的路由算法的实现机制不 同，节点用一组属性值来命名它所生成的数据。槽节点向所有传感器发送对任 务描述的“兴趣”( i n t e r e s t ) ，即一个任务描述数据包，它是用属性一值对来描 述的。“兴趣”会通过全网逐渐扩散，最终找到匹配请求条件的数据源，与此 同时，也建立起从数据源到槽节点的“梯度”。节点会在它的缓存中存储兴趣 入1 3 ( i n t e r e s te n t r y ) ，兴趣入口包含时日j 戳和梯度场，数掘源节点会沿梯度最大 的方向将数掘传回槽节点。图2 3 展示了兴趣扩散、梯度建立以及数据按照加 强的梯度路径传送的三个步骤。 第一章路由j 测即 争) i n t 尊e s t p t o p a g a t t o a c b ) i m t t a l 争a 由蜘b 州叩r ) i ) 时- 酗、d y a l o n g 删妇d 图2 3d d 算法示意图 s p i n 算法( s e n s o r p r o t o c o l f o r i n f o r m a t i o n v i a n e g o t i a t i o n ) 【16 j 【 1 ：该算法引入 两个革新性概念“协商”和“根据资源情况进行调整”。s p i n 在发送数据之前 先用握手机制确定是否有数掘发送，网络中传输的数据包分为三类分别为 a d v 、r e 0 、和d a t a 。前两者用于握手确认，后者为真正传输的数据包。 如a 向b 发送数据分为三个阶段： 第一步，a 发送a d v 包。 第二步，如果b 同意接收a 的数掘则b 向a 发送r e q 包。 第三步，a 向b 发送真正的数掘包d a t a 。 当b 收到了a 的数掘后，如果自己并非最终目的节点则继续转发a d v ，需 要的节点会向b 发送r e q 包，重复数掘的转发过程。在a d v 包和r e q 包中 存在元数据( m e t ad a t a ) ，它是实际传输数据的一个抽象，也即能够唯一表征 所代表的数据，但是比实际数据小得多，在握手阶段节点通过分析r e c t ad a t a 就可以确认本轮定义的数据d a t a 是否已经接收过，避免了重复。 2 1 4 基于连通支配集的路由算法 连通支配集的概念是出自图论中的，其定义为：d 包含于v ( g ) 称为图g 的 一个支配集，若任何顶点u v ( g ) ，要么u d ，要么