（计算机科学与技术专业论文）基于位置信息的无线传感器网络路由算法研究.pdf

硕士学位论文 摘要 本文在研究和分析现有的无线传感器网络基于位置信息的路由算法的基础 上，结合物理学上密度的概念，给每个节点定义了一个新的状态参数一一能量密 度。能量密度的取值大小是与节点的剩余能量成正比，与节点到s i n k 节点的距离 的平方成反比。在此基础上，提出了一种新的无线传感器网络路由算法一一无线 传感器网络基于位置信息的能量密度路由算法。 在基于位置信息的能量密度路由算法中，网络中的节点总是把数据转发给下 一个比自己离s i n k 节点更近而且能量密度是节点常规传输方式所到达的所有邻 接节点中最大者。当没有邻接节点满足此条件的时候，即遇到“空洞 ，则节点用 长距传输方式把数据包直接传给s i n k 节点。 接下来，论文重点介绍了用j a v a 语言来实现了基于位置信息的能量密度路由 算法仿真的过程。各种实验条件百的仿真结果表明基于位置信息的能量密度路由 算法比改进的g p r s 算法更加有效。同时，对基于位置信息的能量密度路由算法的 关键参数进行了深入的探讨和研究，并得出了其变化对算法性能影响的规律。 紧接着，论文提出了一种改进的基于位置信息的能量密度路由算法一一树路由 处理空洞的基于位置信息的能量密度路由算法。在此算法中，利用初始生成的以 s i n k 节点为根的广度优先生成树，来处理基于位置信息的能量密度路由算法的 “空洞 情况。通过仿真实验，证明了改进的基于位置信息的能量密度路由算法 在网络初始阶段比原算法要好。 最后，论文对全文进行了总结和对未来的研究工作进行了展望，并指出了未来 研究工作的方向和重点。 关键词：无线传感器网络；位置信息；路由算法；能量密度 基于位置信息的无线传感器网络路由算法研究 a b s t r a c t i nt h i sp a p e r ，c o n s i d e r i n gt h ee x i s t i n g1 0 c a t i o n b a s e dr o u t i n ga l g o r i t h m sf 0 r w i r e l e s ss e n s o rn e t w o r k s ( w s n s ) ，an o v e ls t a t ep a r a m e t e r ，e n e r g yd e n s i t y ，i sd e f i n e d f 0 re a c hn o d eb a s e do nt h ep h y s i c a lc o n c e p td e n s i t y ：e n e r g yd e n s i t yi sd e s i g n e dt ob e p o s i t i v ep r o p o r t i o nt ot h er e m a i n i n ge n e r g yo fn o d ea n d f a l lo f fa st h es q u a r eo ft h e d i s t a n c eb e t w e e ni t s e l fa n dt h es i n kn o d e a c c o r d i n g l y ，an e wr o u t i n ga l g o r i t h m ， l o c a t i o n - b a s e de n e r g yd e n s i t y r o u t i n ga l g o r i t h m ，i sp r o p o s e df 0 rw s n s i nt h el o c a t i o n - b a s e de n e r g yd e n s i t yr o u t i n ga l g o r i t h m ，a n yn o d ei nt h en e t w o r k o n l yt r a n s m i t sd a t at oo n eo ft h e i ra d ja c e n tn o d e si nt h ec o m m o nt r a n s m i t t a n c er a d i u s t h ea d ja c e n tn o d ei ss e l e c t e db yt w oc o n d i t i o n s o n ei st h a ti t sd i s t a n c et os i n kn o d e b e c o m e ss m a l l e r ，t h eo t h e ri st h a ti t se n e r g yd e n s i t yi sl a r g e s ti nt h ea d ja c e n tn o d e s 妇a ts a t i s f vt h ef i r s tc o n d i t i o n i fn on o d es a t i s f i e sb o t hc o n d i t i o n s ，i ti sj u d g e dt h n 一 ”v o i d ”i se n c o u n t e r e d u n d e rt h i ss i t u a t i o n ，t h en o d et r a n s m i t sd a t at ot h es i n kn o d e d i r e c t l yb yf a rt r a n s m i s s i o ni nt h i sp a p e r a 1 s o ，t h ep a p e ri n t r o d u c e st h es i m u l a t i o np r o c e s sb yu s i n gt h ej a v al a n g u a g et o r e a l i z et h er o u t i n gp r o t o c 0 1 s i m u l a t i o nr e s u l t si nd i f f c r e n te x p e r i m e n tc o n d i t i o n s s h o wt h a tt h el o c a t i o n b a s e de n e r g yd e n s i t yr o u t i n ga l g o r i t h mp e r f o m sb e t t e rt h a na n i m p r o v e d g p s r f u r t h e m o r e ， t h ep a p e re x p l o r e st h ei n f l u e n c eo fs o m ek e y p a r a m e t e r su s e di nt h el o c a t i o n b a s e de n e r g yd e n s i t yr o u t i n ga l g o r i t h mi nd e p t ha n d g e t st h er e g u l a r i t yo ft h ep a r a m e t e r s c h a n g ei m p a c t i n go nt h ep e r f o m a n c e o f a l g o r i t h m t h e nt h ep a p e ri n t r o d u c e sa ni m p r 0 v e d1 0 c a t i o n - b a s e de n e r g yd e n s i t yr o u t i n g a l g o r i t h mt h a ti sn a m e dl o c a t i o n - b a s e de n e r g yd e n s i t yr o u t i n ga l g o r i t h mw i t ht r e e r o u t i n gd e a l i n gw i t h v o i d i nt h ea l g o r i t h m ，i tu s e st h e i n i t i a lb r e a d t h f i r s ts p a n n i n g t r e ew h o s er o o ti sa tsi n kn o d et od e a lw i t h v o i d ”o fl o c a t i o n b a s e de n e r g yd e n s i t y r o u t i n ga l g o r i t h m s i m u l a t i o nr e s u l t sp r o v e dt h a tt h ei m p r o v e da l g o r i t h mi s b e t t e r t h a nt h eo r i g i n a la l g o r i t h mi nt h ei n i t i a ls t a g eo fn e t w o r k f i n a l l y ， t h ep a p e rm a k e sas u m m a r ya n dd r a w st h ep r o s p e c to fr e s e a r c h e s p e c i a l l y ；i tp o i n t so u tt h ef 0 c u sa n dd i r e c t i o ni nt h e 向t u r e r 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 ；l o c a t i o ni n f o m a t i o n ； r o u t i n ga l g o r i t h m ； e n e r g yd e n s i t y l i i 硕上学位论文 图2 1 图2 2 图2 3 图2 4 图2 5 图2 6 图2 7 图3 1 图3 2 图3 3 图3 4 图4 1 图4 2 图4 3 图4 4 图4 5 图4 6 图4 7 图4 8 图4 9 图4 1 0 图4 1 1 图4 1 2 图4 1 3 图4 1 4 图4 15 图4 1 6 图4 1 7 图4 18 图4 1 9 图4 2 0 插图索引 无线传感器网络示意图4 传感器节点体系结构5 d i r e c t e dd i f f u s i o n 算法的路由建立过程7 r u m o r 算法路由建立过程8 p e g a s i s 算法路由建立过程9 “空洞 处理1 2 d i r e c t e df l o o d i n g 算法1 4 能量密度路由节点选择2 5 能量密度路由中节点遇到“空洞 ，选择长距传输方式2 6 程序流程图2 7 路由拓扑变化图3 0 不同比例节点正常死亡时传输成功数据量3 3 不同比例节点正常死亡时丢包率3 3 不同的路径长度( 节点跳数) 下发送成功的数据量总数3 3 不同比例节点正常死亡时传输成功数据量3 5 不同比例节点正常死亡时丢包率3 5 不同的路径长度( 节点跳数) 下发送成功的数据量总数3 5 s i n k 节点位置3 6 不同比例节点正常死亡时传输成功数据量3 7 不同比例节点正常死亡时丢包率3 7 不同的路径长度( 节点跳数) 下发送成功的数据量总数3 7 不同比例节点正常死亡时传输成功数据量4 0 不同比例节点正常死亡时丢包率4 0 不同比例节点正常死亡时传输成功数据量4 1 不同比例节点正常死亡时丢包率4 l 节点死亡2 0 时路由4 2 初始路由拓扑4 2 初始路由拓扑( 加上连线，避开“空洞 ) 4 3 能量密度方式传输4 5 能量密度方式传输，遇到“空洞，选择树路由方式传输4 5 初始路由拓扑4 6 基于位置信息的无线传感器网络路由算法研究 图4 2 l不同比例节点正常死亡时传输成功数据量4 7 图4 2 2不同比例节点正常死亡时丢包率4 7 图4 2 3不同的路径长度( 节点跳数) 下发送成功的数据量总数4 7 v 硕十学位论文 附表索引 表2 1建模域功能表1 9 表4 1不同t 值下，发送成功的数据包的平均路径长度4 l v i i i 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得 的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他 个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人 和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由 本人承担。 作者签名： 簿。闲权 日期：rr 司b ， 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论 文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名： 导师签名： 刁7 月月 r l 1年年 1 1 期期 枢 舟彦 谤 1 j 季叫 订卜川 硕上学位论文 1 1 课题研究背景和意义 第1 章绪论 随着传感器技术、嵌入式技术、分布式信息处理技术和无线通信技术的不断 发展，由大量的具有微处理和无线通信能力的微型传感器节点组成的无线传感器 网络n 3 1 ( w i r e l e s ss e n s o rn e t w o r k s ，w s n s ) 逐渐成为学术界和产业界的研究热点。 美国商业周刊和m i t 技术评论在预测未来技术发展的报告中，分别将无线传感器 网络列为2 1 世纪最有影响的技术和改变世界的技术之一。 无线传感器网络有着巨大的应用前景。建立在各类传感网络节点平台上的， 面向陆海空天全方位的应用需求项目更是数不胜数，层出不穷。以下列出几个代 表：比如大到用于环境监测、气象现象的观测、天气预报、月球等天体探索监测、 太空卫星监控、军事战场监测、地震预测、洪灾预警等等，小到用于生物群落观 测、农田管理、智能家居、智能交通研究、用于定位的网络和医疗应用等等各个 方面，无线传感器网络在这些方面都能大显身手，大有作为。 无线传感器网络与传统的无线网络( 如蜂窝移动电话网络) 有着很大的不同， 后者的设计目标是在移动的环境中通过优化路由和资源管理策略，来最大化带宽 的利用率，从而为用户提供有一定质量保证的服务。而在无线传感器网络中，通 常运行在人无法接近的恶劣甚至危险的远程环境中，采用电池供电，能源无法更 换；而且除了少数节点需要移动以外，大部分节点都是静止的。 无线传感器网络的路由算法h 。7 1 则是无线传感器网络中的关键核心技术，设计 一个优秀的路由算法对于无线传感器网络有着至关重要的作用，乃至有决定性的 作用。 在无线传感器网络中，由于传感器节点能量是采用电池供电，所以节点能量 有限。尽可能延长整个无线传感器网络的生命周期，是无线传感器网络路由算法 设计的一个重要的关键性原则。无线传感器网络路由算法不仅关心单个节点的能 量消耗，更关心整个网络能量的均衡消耗，这样才能延长整个网络的生存期。因 此，无线传感器网络路由算法主要是围绕着减少能量消耗延长网络生命周期而进 行设计的。目前提出了很多类型的无线传感器网络路由算法，就是基于上述的目 的。同时，根据不同的应用需求，无线传感器网络路由算法也有各自不同的需求。 现阶段的大多路由算法都有一些这样或则那样的不足，有很大的改进空间， 研究无线传感器网络的路由算法成为学术界研究的一个新的方向。 当前，在无线传感器网络的路由算法中，基于位置信息的路由算法成为了研 基于位置信息的无线传感器网络路由算法研究 究的重中之重。 这是由于定位技术的快速发展，使得得到节点的位置信息越来越容易( 一般 可以通过g p s 定位系统或则几何三角形算法去计算节点位置信息) 。另一方面， 基于位置信息的无线传感器网络路由算法具有简单、监测信息准确、可以和很多 已有算法相互结合和易于节省能量等等特点，使其能够有效的满足无线传感器网 络应用的特点和需求，得到了很快的发展。 基于位置信息的无线传感器网络路由算法正成为了无线传感器网络研究的新 热点，所以本文研究无线传感器网络基于位置信息的路由算法有很大的理论和现 实意义。 1 2 本论文主要工作概述 本文重点的工作在于：在研究和分析现有的无线传感器网络基于位置信息的 路由算法的基础上，结合物理学上密度的概念，提出了一种新的无线传感器网络 路由算法一一无线传感器网络基于位置信息的能量密度路由算法。 接下来，本文重点介绍了自己用j a v 。语言来实现了基于位置信息的能量密度 路由算法仿真的过程，分析和比较新算法和改进的g p r s 算法的实验仿真结果， 得出了基于位置信息的能量密度路由算法的更加有效。同时，对基于位置信息的 能量密度路由算法的更新路由参数t 进行了深入的研究，并得出了其变化对算法 性能影响的规律。 最后，重点介绍新提出一种改进的基于位置信息的能量密度路由算法，并通 过仿真实验证明其有效性。 1 3 论文基本结构 全文共分为4 章，各章的内容如下： 第l 章为绪论。主要介绍课题研究背景和意义、本文主要做的工作和论文的 基本结构。 第2 章为基于位置信息的路由算法概述。本章在介绍了无线传感器网络和路 由算法相关知识的基础之上，重点介绍了基于位置信息的无线传感器网络路由算 法。同时，分析了无线传感器网络路由算法的特点和介绍了仿真工具的发展现状。 第3 章为基于位置信息的能量密度路由算法。主要介绍了自己新提出的一种 路由算法一一无线传感器网络基于能量密度的路由算法，包括算法的提出的背景、 原理和算法内容等。 第4 章为基于位置信息的能量密度路由算法仿真分析和改进。通过实验仿真， 使基于位置信息的能量密度路由算法与改进的g p s r 算法进行了比较。实验所取 2 硕士学位论文 的条件是比较全面，包括：均匀分布、非均匀的高斯分布等。在这些实验条件下， 证明了基于位置信息的能量密度路由算法的更加有效。同时，对算法更新路由参 数t 进行了深入的研究。接着，本章重点介绍了一种改进的基于位置信息的能量 密度路由算法一一树路由处理空洞的基于位置信息的能量密度路由算法，并通过 数值仿真证明其有效性。 最后对全文进行了总结，并对未来的工作进行了展望。 3 基于位置信息的无线传感器网络路由算法研究 第2 章基于位置信息的路由算法概述 本章在介绍了无线传感器网络和路由算法相关知识，重点介绍了基于位置信 息的无线传感器网络路由算法。同时，分析了无线传感器网络路由算法的特点。 本章最后介绍了仿真工具的发展现状。 2 1 无线传感器网络概述 在无线传感器网络中，由于传感器的廉价性，节点可通过飞机撒布或人工预 先布置等方式，大量部署在需要监控对象内部或附近。这些传感器节点通过自组 织方式构成无线网络，以相互协作的方式实时监控、采集和处理网络覆盖区域中 的信息。这些信息，通过无线传感器网络结点多跳传送方式，最终将数据传送到 s i n k 节点，s i n k 再将整个区域内的感知信息传送到远程管理中心。远程管理中心 也可以根据实际的需要，对网络节点进行操纵控制，以采集需要的感知参数。 无线传感器网络如图2 1 所示呻1 ，无线传感器网络通常包括传感器节点 ( s e n s o rn o d e ) ，s i n k 节点( s i n k ) 和管理节点。传感器节点任意的分布在某一监测区 域内，节点以自组织的形式构成网络，通过多跳中继方式将监测数据传送到s i n k 节点，最后通过i n t e r n e t 或其他网络通信方式将监测信息传送到管理节点。同样 的，用户可以通过管理节点进行命令的发布，告知传感器节点收集监测信息。 一7 、 一。、，、 、 一。 o 、 一 。 ! 厂。 。 。 。 。 广 一一一一橱、9 一 一 一一二一一刊。、咆； ! oo 一、 、 。e 。， ：! 交 、旦7 图2 1无线传感器网络示意图 传感器节点是一个具有信息收集和处理能力的微系统，集成4 大模块，包括 4 硕士学位论文 传感器模块、信息处理模块、无线通信模块和能量供应模块。其结构体系如图2 2 所示【8 1 。 图2 2 传感器节点体系结构 传感器模块( d a t aa c q u i s i t i o nu n i t ) 负责监测区域内信息的采集和转换，信息处 理模块( p r o c e s su n i t ) 负责管理整个传感器节点、存储和处理自身采集的数据或者 其他节点发送来的数据，无线通信模块( d a t at r a n s f e ru n i t ) 负责与其他传感器节点 进行通信，能量供应模块( p o w e r ) 负责对整个无线传感器网络的运行进行能量的供 应。传感器节点能量消耗的模块主要是包括传感器模块、信息处理模块和无线通 信模块，而绝大部分的能量消耗是集中在无线通信模块上，约占整个传感器节点 能量消耗的8 0 。 2 2 路由算法发展现状 无线传感器网络路由算法负责在s i n k 节点和其余传感器节点间进行数据传 输时的路由。由于无线传感器网络与应用高度相关，单一的路由算法不能满足各 种应用需求，因而目前学术界研究了很多的路由算法。 当前主要路由算法一般分为5 大类：平面路由算法、分层( 分簇) 路由算法、 基于位置信息的路由算法、基于能量信息的路由算法和其他一些算法。 2 2 1 平面路由算法 平面路由算法主要是指节点没有层次结构。算法主要包括：f 1 0 0 d i n g 算法、 g o s s i p i n g 例算法、s p i n 1 0 1 算法、d i r e c t e dd i f m s i o n 1 1 1 算法和r u m o r n 2 1 算法等等。 其中，f l o o d i n g 算法是最简单和经典的传统网络路由算法，理论上也可应用 到w s n s 中。在f l o o d i n g 算法中，节点产生或收到数据后向所有邻接节点广播， 数据包直到过期或到达目的地才停止传播。该算法缺点：能量利用率低，节点可 能收到多分相同的数据。优点是：只要有路径到达s i n k 节点，传输数据总能够到 达s i n k 节点，不会丢失数据。g o s s i p i n g 算法是对f l o o d i n g 算法的改进，节点将 产生或收到的数据随机转发给一个邻接节点，而不是发给所有的邻接节点，这样 5 基于位置信息的无线传感器网络路由算法研究 就有效的避免了能量的浪费，但增加了延迟。 平面路由算法中比较典型的是以下三种算法： 1 s p i n 算法是基于数据的路由算法。该算法的思想是：算法以抽象的元数据 对数据进行抽象描述，通过短小的元数据的传送，来减少真实数据的传送量。算 法分三个阶段： 第一阶段：节点a 产生或收到数据后，传送包含了元数据的a d v 消息通知 邻接节点； 第二阶段：邻接节点收到包含了元数据的a d v 消息，分析元数据，如果邻 接节点需要此监测数据，就发送r e q 消息给节点a 提出请求； 第三阶段：节点a 收到r e q 消息以后，通过d a l r a 消息，把监测数据发送 到需要数据且发出r e q 消息的邻接节点。 算法不断重复上述三个阶段，直到数据到达s i n k 节点。 为了应用于不同的情况，该算法有几个子算法，分别是：针对点对点的 s p i n p p ，针对低能量的s p i n e c 和针对广播的s p i n b c 等。 算法的优点是用a d v 和r e q 消息来探测下一个节点是否需要监测数据，从 而避免传输大数据量的真实的监测数据包的次数，再加上询问下一个节点是否需 要此数据包，增加了传输的目的性，也避免做无用的传输。与f l o o d i n g 算法相比， 有效地节约了能量。缺点是：频繁的传送a d v 和r e q 消息，使a d v 和r e q 消 息传送太多，会消耗网络节点的一部分能量。而且元数据需要预先定义和抽象， 增加了网络设计的复杂性，同时还要每个节点都能判断所收到的元数据所代表的 真实数据是否是节点自己需要的数据，这增加了节点的复杂性。 2 d i r e c t e dd i f f u s i o n 算法( 定向扩散) 是一种重要的基于数据的、查询驱动的 路由算法。d i r e c t e dd i f m s i o n 算法是一种以数据为中心的信息传播算法，与已有 的路由算法有着完全不同的实现机制。d i r e c t e dd i f 如s i o n 算法引入4 个基本概念： 兴趣( i n t e r e s t ) 、数据消息( d a t am e s s a g e ) 、梯度( g r a d i e n t ) 和加强( r e i n f o r c e m e n t ) 。 d i r e c t e dd i f m s i o n 算法的路由是通过s i n k 节点发起建立的。首先，s i n k 节点 周期地广播一种称为“兴趣的数据包，告诉网络中的s i n k 的邻居节点它需要 收集的信息；s i n k 的邻居再发送“兴趣”给各自的邻居节点，告诉其邻居节点需 要收集的信息。这个过程不断重复，直到所有节点都收到了“兴趣 ，这样d i r e c t e d d i f f u s i o n 路由算法的初始“梯度场就建立了。当有节点收集到“兴趣 类型的 监测数据，就按建立“梯度场时的路径，沿着梯度最大的方向传输数据到s i n k 节点，同时加强路径上各个节点的“梯度”值。在这个过程里面，节点需要对数 据，包括“兴趣”和“数据消息进行数据的融合，以减少数据的传输量。 d i r e c t e dd i f f u s i o n 算法的优点：该算法只有邻居节点间进行数据传输，不需 要对节点进行地址的设置。节点都能够进行数据融合和对数据进行缓存，使得它 6 硕十学位论文 能够更好的节省能量。同时，该算法的数据传播方式对网络拓扑没有特殊要求。 d i r e c t e dd i f m s i o n 算法的不足：使用查询驱动机制按需建立路由，不适合环 境监测等应用。“梯度的建立开销很大，不适合多s i n k 点网络；同时，每次都 按照梯度最大的方向传输数据，这样虽然节省了能耗，但也会使得这条梯度最大 的路径上的节点过早死亡，导致整个网络的节点能耗不均衡。另外，d i r e c t e d d i f f u s i o n 需要预先定义“兴趣 ，在实际应用时，每一次都应有一个预定的内容， 增加了算法应用的复杂性。如图2 3 所示： s a 黼 o 、 o o c 迫 数据传输 图2 3 dir e c t e dd if f u sio n 算法的路由建立过程 3 r u m o r 算法是主动查询驱动路由算法。主要是针对于当无线传感器网络只 要查询少量监测数据时，由于d i r e c t e dd i f f u s i o n 算法需要洪泛“兴趣 建立梯度， 太浪费能量。该算法的主要思想是：s i n k 节点发送的查询消息沿随机路径在网络 中传播；同时，事件区域中的传感器节点产生代理消息，代理消息也沿随机路径 在网络中传播。当代理消息和查询消息相“碰撞 ，即传输路径交叉在一个传感器 节点时，就会形成一条从s i n k 节点到事件区域的完整路径，然后监测信息就会按 照此路径传输。如果没有相交或则超时，则采用洪泛方式，传播事件信息。 m o n t e c a r l o 模拟告诉我们两条直线在一个有界矩形区域内相交的概率大约 是6 9 ，这就意味着一个事件发出的5 条路径有9 9 7 的机会与一个查询相遇， 这就证明了r u m o r 路由是可行的n 3 1 。 该算法的优点在于：利用了几何学上的“平面上两条直线相交的概率很大 的特性，有一定的理论基础；同时，也比较节省能量。缺点在于：在直线不相交 时，会采用洪泛方式，比较耗能。 如图2 4 所示： 7 o b 基于位置信息的无线传感器网络路由算法研究 图2 4r u m o r 算法路由建立过程 2 2 2 分层路由算法 分层的路由算法主要是指把网络节点分簇处理，簇头和非簇头节点形成层次。 这种分层可以是两层或则多层。主要包括：l e a c h 1 算法、p e g a s i s n 叫算法、 t e e n n 们算法和多层聚类算法啼1 等等。 比较典型的是以下三种算法： 1 l e a c h 算法是第一个提出数据聚合的分层次路由算法。该算法的思想是： 按照一定的时间间隔t ，作为一轮传播时间，每轮开始的时候随机选择网络中的 节点作为簇头，其他非簇头节点把数据传给簇头，然后簇头把数据传给s i n k 节点。 算法每一轮分如下二个阶段： 第一阶段：选择簇头，建立簇阶段( a d v e r t i s e m e n tp h a s e ，c l u s t e rs e t u pp h a s e ， sc h e d u l ec r e a t i o n )。 簇头是周期性按轮随机选举的，每轮簇头选举方法是：各节点产生一个【o ， 1 】之问的随机数，如果该数小于丁( ，1 ) ，则该节点为簇头。f ( 聆) 的计算公式如下2 1 ： m 卜p 刍) ，刀g ( 2 1 ) ，其他 其中，p 是网络中簇头数与总节点数的百分比( 一般是0 0 5 ) ，r 是当前的选 举轮数，g 是最近1 p 轮不是簇头的节点集。这种选择的方式保证了1 p 轮里面， 所有的节点都会成为簇头。 成为簇头的节点在无线传感器网络中广播这一消息，而且广播消息时发射能 8 硕士学位论文 量都一样大，其余非簇头节点选择加入自己收到消息信号能量最强的簇头所代表 的簇，并发送消息通知簇头，确定传输的方案等。这就保证非簇头节点到簇头之 间的传输消耗最小。 第二阶段：数据传输阶段( d a t at r a n s m i s s i o n ) 非簇头节点通过一跳通信将数据传送给簇头，簇头在一定的时间里面会缓存 这些数据，当所有节点数据都被收集，簇头进行数据的融合和压缩，最后，簇头 也通过一跳通信将数据传送给s i n k 点。 每轮时间到了，算法又重复上述过程。 该算法优点在于，采用随机选举簇头的方式，避免簇头过分消耗能量，提高 了网络生存时间；数据聚合能有效减少通信量。算法不足在于，簇头与s i n k 仍采 用一跳通信，在离s i n k 点较远的簇头，由于采用大功率通信也会导致生存时间较 短；而且频繁选举簇头引发的通信量也耗费了一定的能量。 2 p e g a s i s 算法是对l e a c h 算法的改进。该算法首先形成一个簇，包括网 络中所有节点的，可以称为链。该算法要求每个节点部知道网络中其他节点的位 置，通过贪心算法选择最近的邻接节点形成链。如图2 5 所示： n 0 j n l 哼n 2 专n 3 七_ n 4 七一n s 七_ n 6 七- n 1 七- n 8 山 s i n k 图2 5p e g a s i s 算法路由建立过程 接着，在选择簇头阶段，直接使用如下方法，在每一轮的开始时，动态选举 簇头：设网络中n 个节点都用l 到n 的自然数编号，第j 轮选取的簇头是第i 个 节点，i - jm o dn ( i 为o 时，j 取n ) 。为了保证能量低的节点不选为簇头，可以设 置一个能量的门限值，使低于此值的节点不能成为簇头。 只有簇头与s i n k 节点一跳通信，其他节点都把自己收到和采集到的数据传给 链中的下一个节点。即向簇头传输数据，直到数据到达簇头，最后簇头把数据传 给s i n k 节点。每个节点在传输数据的时候，都要进行数据的压缩和聚合，使每个 节点都只传输一个相同大小的数据包。当链两端数据都传送完成时，开始新一轮 选举与传输。如果有节点失效，需要重新链接成链。 该算法优点在于，避免l e a c h 算法频繁选举簇头和有效的链式数据聚合， 使其与l e a c h 算法相比减少了数据传输次数和通信量，提高网络生存时间。该 算法不足点在于，如果链过长，数据传输时延将会增大；单簇方法使得簇头成为 关键点，其失效会导致路由失败。 3 t e e n 算法是一种适用于对突发事件的感知的分层路由算法，其重要的特 点是对即时性的重要变化的数据具有快速反应能力。 9 基于位置信息的无线传感器网络路由算法研究 t e e n 算法是在以数据为中心的层次算法中的典型算法，它是在l e a c h 算 法的基础上进行改进。t e e n 算法将l e a c h 算法的由簇头直接与s i n k 进行通信 方式，扩展为把簇头的集合作为另一个簇，再选出簇头与s i n k 通信。 当簇构造好之后，簇头节点会广播两个限值。分别称为硬门限和软门限。硬 门限是开始进行数据传输的最低限度，软门限是外界条件变化的幅度。数据只有 超过硬门限后，同时变化的幅度要大于软门限，传感器节点才会向其所在簇的簇 头发送采集到的数据。 该算法优点在于，由于传输数据需要达到一定条件，所以使用这种方法可以 有效地减少数据的传输量。同时，t e e n 算法对簇头的分级，使得它能够用于地 理分布更广，节点数量更大的无线传感器网络。该算法不足点在于，只有达到一 定条件的数据才传输，必然会有一定1 的数据在数据收集过程中丢失，导致无线传 感器网络无法对所在环境进行全面而准确的监测。 2 2 3 基于能量信息路由算法 基于能量的路由算法主要是指节点在路由中考虑节点的能量信息。主要包括： e n e r g ya w a r er o u t i n g n 算法和e b m r n 8 3 算法等等。 比较典型的是以下二种算法： 1 e n e r g ya w a r er o u t i n g 算法是一种基于节点能量信息的路由算法，称为能量 感知的重激发路由算法。该算法分三个阶段：邻居发现( n e i 曲b o rd i s c o v e r y ) 、 路由应答( r o u t er e p l y ) 和可靠传输( r e l i a b l et r a n s m i s s i o n ) ，它们都依赖于两 个消息即广播消息和路由回复消息。当s i n k 节点需要某个监测信息时，s i n k 节点 启用发现源节点的操作机制一一s i n k 节点在整个网络里面洪泛发射广播消息，直 到消息到达源节点。源节点收到这个消息以后沿原路径把数据传回给s i n k 节点。 其中，在每个节点广播这个消息时，会保存和不断更新一张路由表，记录所 有从源节点到s i n k 节点经过节点本身的路由( 即保存下一跳节点) 。在真实传输 数据时，选择所有路径上，下一跳节点中剩余能量最大的节点作为路由节点。 该算法优点在于能够很好的平衡节点能耗，延长网络的使用时间。算法不足 在于，s i n k 节点发现源节点时，需要洪泛消息，会浪费一定的能量。 2 e b m r 算法是一种基于节点能量信息的集中控制查询路由算法。该算法首 先定义了两个概念：边权重( w e i 曲t ) 和最短路径( s h o r t e s tp a t h ) 。边权重是两 个节点间发送方的能量，边权重代表从发送方节点到接受方节点的这条拓扑边的 权重。最短路径表示从源节点到s i n k 节点所有路径中的有向边的边权重之和最小 的路径。该算法初始阶段会洪泛消息，找出所有的网络的信息，并存储在s i n k 节 点，包括网络的拓扑结构和每条的有向边的边权重。在实际需要查询某个源节点 监测信息时，s i n k 节点会通过广度优先算法( b f s ) 计算一条最短路径，然后把 1 0 硕十学位论文 路由信息发给源节点。源节点按照路由信息把数据传给s i n k 节点，同时收集各个 节点的能量消耗情况，一并发给s i n k 节点，s i n k 节点更新各条边的边权重。 该算法通过定义边权重的做法，把能量直接转化为拓扑边长，每次路由选择 最短路径。同时，路由后会动态调整边权重的做法，节省了网络能量的消耗，延 长了网络时间。算法缺点在于收集整个网络拓扑结构阶段耗费能量多，而且都是 s i n k 节点集中控制路由，路由信息的传送和维护也会耗费一定的网络能量。 其他的基于能量信息的路由还有：s h a h 等人提出的能量感知路由算法n 们( 根 据剩余能量和节点发送数据消耗来构建立节点的选择概率，然后随机抽取) ；s i v a d m u r u g a n a t h a n 等人提出中心控制的能量效率路由算法乜引；文献 2 1 基于 节点能量使用的历史数据，提出了一种实用指南并发展了一系列的新技术来增强 传感网络的路由；文献 2 2 针对现有无线传感器网络中路由协议产生“热点区域 问题，提出了一种能量平衡的路径选择算法。文献 2 3 结合无线传感器网络的特 点和其实际应用环境，提出一种由基站负责分簇、利用d t r a p 进行节点位置的 估计和采用重定向技术进行性能优化的新路由算法；文献 2 4 基于协作通信技术， 提出了一种协作路奠：策略。 2 2 4 基于位置信息的路由算法 基于位置信息的路由算法主要包括：g p s r 凹5 1 算法、g p s r s 口明算法、 g l b d m e c r 心 算法和t b f 乜钔算法等等。 2 2 5 其他一些算法 s a r 算法乜们( 这是第1 个在w s n s 中保证q o s 的主动路由算法) ，c h a n g 等 人提出的最大化生存时问路由算法们( 代价为剩余能量和节点发送数据消耗的能 量的函数) ，t i n y o sb e a c o n i n g 算法口妇( 以s i n k 节点为根的广度优先生成树) ， y e 等人提出的最小代价路由算法口列( 所有节点到s i n k 节点最小代价) ，t t d d 算法口3 1 ( 利用节点生成的网格和a g e n t 代理机制，主要是解决网络中存在多s i n k 节点及s i n k 节点移动问题) ，w e i k ec h e n 等人提出基于q o s 的自适应分簇算法 口4 1 ，d e b a ox i a o 等人提出安全保证的数据协商路由算法( s e c u r e s p i n ) 口引，刘志 强等提出基于小世界的无线传感器网络资源查询机制们和张锦等人提出基于密 度控制的路由算法口7 1 等等算法。 2 3 基于位置信息的路由算法介绍 基于位置信息的路由算法是节点知道自己的位置，路由选择是利用已知的位 置信息进行路由。地址信息在路由选择中可以起确定性或则辅助性的作用。重点 介绍了以下几种基于位置信息的路由算法。 基于位置信息的无线传感器网络路由算法研究 2 3 1g p s r 算法 g p s r 算法是一个典型的基于位置的路由算法。该算法假定所有的传感器节 点知道自己节点的地理位置并被统一编址( 可以通过三角形算法或则g p s 定位系 统获得) ，网络初始阶段是s i n k 节点广播自己的位置给所有节点，使得所有节点 知道s i n k 节点的位置。 节点产生或者收到数据时，就利用“贪心”算法选择离s i n k 节点距离最近的 邻居节点作为路由的下一跳节点。由于平面上，两点距离最近是线段。所以也可 以说是尽量的沿直线传播。该算法在具体求这个离s i n k 节点最近的邻居节点时， 是把节点自己的各个邻居节点的位置投影到节点自己与s i n k 节点的连线上，其中 在连线上离s i n k 节点最近的投影点就是下一跳节点。另外，还必须保证下一跳节 点比节点本省离s i n k 节点更近。 如果节点的所有的邻居节点都比节点到s i n k 的距离远，这时，就是出现了“空 洞 ( v o i d ) 。算法就进入“空洞 处理阶段，算法利用右手法则绕开空洞。右 手法则如图2 6 所示凹5 l ： 图2 6 “空洞”处理 为了能运行右手法则，算法必须在初始化的时候，计算所有遇到“空洞 节 点的右手法则绕行的线路，并存储在节点里面；而且由于节点易失效，必须周期 性的计算这个右手法则绕行的线路。 该算法优点在于，算法是一个无状态的算法，节点中不用存储和维护路由表， 只与直接邻节点进行交互，就能进行路由选择；算法的容错性好，部分非关键节 点的失效，并不影响算法的路由选择，保证了网络的连通性。该算法缺点在于， “空洞 处理过程太复杂，对于能量和计算能力都有限的无线传感器网络不适应； “空洞 处理，耗能