（通信与信息系统专业论文）高效能量覆盖及压缩感知算法的应用及研究.pdf

武汉理工大学硕士学位论文 摘要 目标探测是w s n s 中的一种重要应用，目标探测模型主要包括采样探测节 点数据，传输采样数据以及重构探测信息三大部分。目标探测的重要指标包括 对目标源重构的精确度以及整个网络的使用寿命。传统的目标源定位方式多采 用距离测量的方式，在同步时间以及对环境的预测方面需要较高要求才可达到 较好的重构效果。延长生命周期的途径有两种，一是降低传播信息时的能量利 用率( 能量消耗信息量) ；二是均衡无线传感器网络中节点的能耗。 本文针对以上的问题，以无线传感器网络目标探测为应用背景，做出了以 下研究工作： ( 1 ) 提出了一种基于热点抑制的分环多跳分簇算法。首先，算法将整个圆 形网络区域分成等间距环状区域，依据环上簇首的能耗相等为前提，确定每环 上的最优分簇的数目，进而得到每环上的簇首选择阈值。其次，算法通过簇首 间欧氏距离归一化值与节点已耗能量归一化值的权值和来选择路由。 ( 2 ) 提出了一种压缩感知算法在无线传感器网络中的应用模型。与传统的 定位方式的不同，采用压缩感知算法，依据安全的数据传输，对目标源的位置 进行数学重构。同时，采用压缩感知算法在能量消耗上也具有较高的优越性。 不同于传统的采样压缩算法，压缩感知算法可以通过数据中的相关性，传输少 得多的采样数据，最终在保证重构精度的同时恢复出原始数据。文中提出的模 型，将压缩感知算法中的稀疏矩阵与观测矩阵分别对应到目标探测模型中节点 传输消耗及网络分簇等信息。 ( 3 ) 研究了基于热点抑制算法及压缩感知算法的目标探测系统。通过压缩 感知算法对节点存储的数据( 目标源发送信息的叠加) 及网络中分簇信息进行采 集。其中网络节点位置的划分是基于圆形区域的网格方式，每个节点的位置以 矩阵中的对应位置表示。然后进入数据传输阶段中，通过基于热点抑制的分环 多跳算法，将采集后的信息由外向内向心传递，直到s i n k 节点接收数据包。最 后进入目标源信息重构阶段，通过快速的贝叶斯重构算法，将压缩后的信息进 行数学处理，最终精确地重构出目标源的位置信息。 关键字：w s n s ，能量覆盖，能量利用率，分环，多跳，分簇，压缩感知 a b s t r a c t t h e t a r g e td e t e c t i o ni sa ni m p o r t a n ta p p l i c a t i o no fw s n s ，t a r g e td e t e c t i o nm o d e l i n c l u d e ss a m p l i n gt h ed a t aw h i c hi ss t o r e di nt h en o d e s ，t r a n s f o r m i n gt h es a m p l e d d a t aa n d r e c o n s t r u c t i n gt h ed e t e c t e di n f o r m a t i o n t h e r eh a v et w oi m p o r t a n ti n d i c a t o r s w h i c ha l et h ea c c u r a c yo ft h er e c o n s t r u c t i o na n dt h el i f ec i r c l eo ft h ew s n s i nt h e t r a d i t i o n a lw a y so fl o c a t i n g ，w en e e dh i g ha c c u r a c yi nt h et i m es y n c h r o n o u s t h e r e a r et w ow a y st oe x t e n dt h el i f e c y c l e f i r s to fa l l ，r e d u c et h ed i s s e m i n a t i o no f m o r m a t i o ne n e r g ye f f i c i e n c y ( e n e r g yc o n s u m p t i o n a m o u n to fi n f o r m a t i o n ) t h e s e c o n da p p r o a c hi st ob a l a n c et h ee n e r g yc o n s u m p t i o no f t h en o d e si n t h ew s n s a c c o r d i n gt h ep r o b l e m sa b o v e ，w e o fd e t e c t i o nt h et a r g e ti nw s n s ： d i dt h ef o l l o w i n gw o r kb a s e dt h ea p p l i c a t i o n ( 1 ) b r i n gu pah o t s u p p r e s s i o ns u b - l o o pm u l t i - h o pc l u s t e r i n ga l g o r i t h mi nt a r g e t d e t e c t i o ns y s t e m s f i r s t ，d i v i d et h ee n t i r ec i r c u l a rn e t w o r ka r e ai n t oe q u a l l va n n l 】l a r r e g i o n o nt h eb a s i so fe q u a le n e r g yc o n s u m p t i o ni ne v e r ya n n u l a r r e g i o n d e t e n m n e d t h eo p t i m a ln u m b e ro fc l u s t e r so ne a c hr i n g a c c o r d i n gt h eo p t i m a ln u m b e ro f e v e r v n n g ，w eh a v et h es e l e c tt h r e s h o l di ne v e r yr i n g s e c o n d l y , t h ea l g o r i t h ms e l e c tt h e r o u t i n gt h r o u g ht h ec l u s t e rh e a d sb yn o r m a l i z e dc l u s t e re u c l i d e a nd i s t a i l c ea n dt l l e n o r m a l i z e dn o d ee n e r g yc o n s u m p t i o nh a sb e e nu s e d ( 劭b r i n gu pac o m p r e s s e ds e n s i n gd e t e c t i o nm o d e l u n l i k em e 乜a d i t i o n a l l o c a t e dw a y s ，w eu s es a f ed a t at r a n s f o r m a t i o na n dm a t h w a y st ol o c a t et h en o d e s a n d c o m p r e s s e ds e n s i n ga l g o r i t h mn e e dl e s so ft h es a m p l i n gd a t ab e c a u s et h e r eh a y e c o r r e l a t i o nb e t w e e nt r a n s m i td a t a , a n du l t i m a t e l yr e c o v e rt h eo r i g i n a ld a t ai nh i g h a c c u r a c yw i t hr e c o n s t r u c ta l g o r i t h m r a i s e db yt h i sm o d e l ，u s et 1 1 e t r a n s m i s s i o n c o n s u m p t i o nm o d ei nt a r g e td e t e c t i o nn e t w o r ka sw e l la st h ec h a r a c t e r i s t i c so ft h e c l u s t e ri nt h e c l u s t e r i n ga l g o r i t h m ，a p p l i e dt ot h ec o m p r e s s e d s e n s i n gt h e o r y , r e s p e c t i v e l y , a sas p a r s em a t r i xa n dt r a n s f e rm a t r i x ( 3 ) r e s e a r c has u p p r e s s i o nh o tp l o ta l g o r i t h ma n dc o m p r e s s e ds e n s i n ga l g o r i t h m i nd e t e c t i n gt a r g e ts y s t e m f i r s to f a l l ，s a m p l ed a t au n d e rt h ea l g o r i t h mo fc o m p r e s s e d s e n s i n g t h ei n f o r m a t i o nc o l l e c t e df r o mn e t w o r kn o d e s ( s u p e r p o s i t i o ni n f o n n a t i o n h 武汉理工大学硕士学位论文 s e n tf r o mt h et a r g e ts o u r c e s ) a n dt h ei n f o r m a t i o no fn e t w o r kc a r v ec l u s t e rw e r e c o l l e c t e d t h ed i v i s i o no ft h en e t w o r k n o d el o c a t i o ni sb a s e do n ac i r c u l a ra r e ao ft h e 酣dt h ew a y , t h el o c a t i o no fe a c hn o d ei se q u a lt ot h ec o r r e s p o n d i n gp o s i t i o ni nt h e m a t r i x t h e ne n t e rt h es t a g eo fd a t at r a n s f o r m a t i o n ，t h es u b - l o o pa n dm u l t i - h o p a l g o r i t h mb a s e do nh o ts p o ts u p p r e s s i o n ，w i l lt h ei n f o r m a t i o nc o l l e c t e df r o mo u t s i d e t oi n s i d ep a s st ot h eh e a r t u n t i lt h es i n kn o d er e c e i v e st h ep a c k e t t h el a s tt oe n t e rt h e t a r g e t s o u r c ei n f o r m a t i o nr e c o n s t r u c t i o n s t a g e ，w i l lc o m p r e s s t h ei n f o r m a t i o n c o l l e c t e dt h r o u g ht h eb a y e s i a nr e c o n s t r u c t i o na l g o d t h mf o rm a t h e m a t i c a lt r e a t m e n t ， a n du l t i m a t e l yt oa c c u r a t e l yr e c o n s t r u c tt h el o c a t i o ni n f o r m a t i o no ft h et a r g e ts o u r c e k e y w o r d s ：w s n s ，c o v e r i n ge n e r g y , e n e r g ye f f i c i e n c y , s u b l o o p ，m u l t i h o pc l u s t e r i n g ， c o m p r e s s e ds e n s i n g i l l 武汉理工大学硕士学位论文 第1 章绪论 1 1 研究的目的和意义 无线传感器网络近年来引起了很大的关注。凭借其诸多优点，无线传感器 网络在很多地方得到了应用，特别是在沙漠、丛林、战场等一系列人们不便到 达或者长期停留的地方。其中目标探测就是其中的一项重要应用。但是由于无 线传感器网络中存在着一些很难克服的缺陷：节点能源有限，节点处理能力有 限。这样会对节点密集且分布区域广阔的传感器网络产生两方面的影响：首先， 由于节点的处理能力有限，包括s i n k 节点在内的传感器节点仅能处理来自少数 节点的数据包，而进行目标探测的传统方式中，需要对整体网络信息进行处理， 这点上就造成了目标探测系统的难以实现；其次，与所有的无线传感器网络一 样，目标探测系统对于提高能量利用，延长使用寿命有着迫切的需要。 针对节点处理能力有限，影响s i n k 节点恢复出目标源探测情况，具备从少 量节点信息中获得整个网络的具体信息能力的压缩感知理论很好的解决了这一 限制。本文将压缩感知算法与传统的分簇算法进行结合，来解决节点处理能力 低，不能通过获取所有节点信息从而恢复整个网络的目标源情况的缺陷。依据 目标探测网络的路径消耗模型以及分簇模型进行对应的压缩感知理论采样，并 通过贝叶斯压缩感知算法从来自簇首节点的少量数据中获得整个网络中目标源 的信息，对目标源进行了高准确度的探测。 针对传感器网络生命周期的限制问题，研究了一种在传统分簇算法思想为 基础的分簇多跳分簇算法，这种算法的优势在网络分布广阔时尤为明显，并且 在分环过程中，利用假设每环上能耗相等的方式得到每环上独立的阈值选择， 从而使得实际选择簇首数目的过程，每一环接近理想设想，达到每环上的能耗 近似相等，使网络中的能耗均衡到每一环避免出现网络“热点”的出现，同时， 延长了第一个节点能量耗尽的时间，也是延长了网络的生命周期，最终达到的 延长网络使用寿命的目的。 综上所述，对压缩感知算法以及分环多跳分簇算法的研究，在无线传感器 网络目标探测系统中，可以通过降低传输数据大小降低同等信息传输量时网络 武汉理工大学硕士学位论文 能量使用率，通过分环多跳分簇算法，均衡网络能耗分布。压缩感知算法主要 是通过节省能量来延长网络的使用寿命，而分环多跳分簇算法在能量节省方面 的优势没有压缩感知算法明显，但是却能够以更优异的分配簇数目的方式，均 衡能耗，延长网络中出现首个能量耗竭节点的时间，延长目标探测系统的稳定 时间，也从另一方面延长了网络的使用寿命。 1 2 国内外研究现状 国外的各种科研机构都对无线传感器网络投入了大量的精力，成立了许多研 究机构，从基础理论到各个专业应用都进行了各项研究，著名的如下： 最具代表性的是美国加州大学伯克利分校和英特尔公司联合成立的“智能 尘埃( s m a r td u s t ) 实验室，主要目的是为美国军方提供能够在体积为一立方毫 米的情况下自治地完成传感和通信功能的设备原型系统，主要目的是研制无线 传感器节点。这项工作从1 9 9 8 年开始到2 0 0 1 年结束，得到了美国国防预先研 究计划局的支持。在随后的几年里，加州大学伯克利分校有多个实验室开始了 关于无线传感器网络及其相关的工作，如：n e s t ( n e t w o r ke m b e d d e ds y s t e m s t e c h n o l o g y ) 、w e b s ( w i r e l e s se m b e d e ds y s t e m ) 、b a r w a n ( b a ya r e ar e s e a r c h w i r e l e s sa c c e s sn e t w o r k ) 、b w r c ( b e r k e l e yw i r e l e s sr e s e a r c hc e n t e r ) 等实验室， 从不同的角度对无线传感器网络进行了大量具有开创性的研究。 美国很多大学在无线传感器网络方面开展了大量工作。如u c l a 的c e n s 实验室、w i n s 实验室、n e s l 实验室、l e c s 实验室、i r l 等。另外，麻省理工 学院获得了a r p a 的支持，研究低功耗传感器网络，研究发现了著名的s p i n 协 议；奥本大学也获得d a r p a 支持，从事了大量关于自组织传感器网络方面的研 究，并完成了一些实验系统的研制；宾汉顿大学计算机系统研究实验室在移动自 组织网络协议、传感器网络系统的应用层设计等方面做了很多研究工作；州立克 利夫兰大学的移动计算实验室在基于p 的移动网络和自组织网络方面结合无线 传感器网络技术进行了研究。另外，北亚利桑那大学的无线网络研究实验室、莱 斯大学多媒体通信实验室的无线个人局域网工作组；斯坦福大学的无线传感器网 络实验室、新泽西州立大学的无线传感器网络实验室、伊利诺伊大学厄本那一香 槟分校的t i m e l y 实验室、南加州大学的r e s l 实验室、佛蒙特大学的无线自组 织网络实验室、西密西根大学的无线传感器网络实验室，此外新加坡国立大学的 无线传感器网络实验室等也有关于无线传感器网络方面的研究。 武汉理工大学硕士学位论文 1 2 1 无限传感器网络国内外研究现状 无线传感器网络路由，实际上就是建立从传感器节点到s i n k 节点的传播路 径，进行安全的传输数据。现存的各种路由协议特点如下： ( 1 ) 传感器节点依据数据属性寻址，非i p 寻址； ( 2 ) 传感器节点中存储的数据通常都需要传递给s i n k 节点； ( 3 ) 在路由协议中，可以通过融合数据降低原始数据中的大量冗余数据， 从而降低传播消耗能量； ( 4 ) 依据传感器节点的处理数据能力、存储大小以及发送功率、能量有限 的特点，在实际应用中，应尽量以降低消耗作为前提。 如今主要存在的无线传感器网络路由协议主要如下： ( 1 ) 以数据为中心 此类协议中，s i n k 节点通常会向某些特定区域节点发出查询命令。特定区域 节点收到查询命令后，查询所需要的信息，并将最终信息传递给s i n k 。f l o o d i n g 不需要任何网络拓扑结构，节点只需要向周围的节点广播接收的信息，直到跳 数到达规定的极限跳数，效率低。此协议存在内爆和重叠的问题。g o s s i p i n g 就 是针对f l o o d i n g 内爆问题所提出的，不同于向所有邻居节点转发数据的方式， g o s s i p i n g 是随机的选择邻居节点作为转发节点，但增加了端到端的数据传输延 迟。 定向扩散( d d ) 同样是以数据为中心的路由协议。s i l l l 【节点向外发送查询命 令，逐渐扩散，直到全网都收到查询命令。在此过程中，网络中以s i n k 节点的 请求形成临时的“梯度 场。传感数据沿着“梯度 最大的方向中继返回s i n k 节点。在d d 基础上加入提高能量效率机制，通过两种过滤即实时过滤和最有过 滤，解决网络延时和能耗不均衡的问题，从而提高质量和生命周期【l 】。 s p i n 也是以数据为中心的路由协议，具有协商及能量自适应的特点。节点 之间首先会通过协商来决定是否传递数据，其次，网络中的能耗问题也会直接 影响工作模式，上述协议讲述的都是平面路由协议，平面路由协议中，传感器 节点无分区分类【2 j 。 ( 2 ) 分区分层路由协议 分层次协议的中心思想为将网络中的节点划分为以簇为单位的小集合，每 个集合中选举一个节点作为管理节点，即簇首节点。划分簇的依据条件一般分 为以节点之间距离、以节点剩余能量。图1 - 1 为无线传感器网络的分簇结构示意 武汉理工大学硕士学位论文 图，可分为三类节点：普通节点、簇头、s i n k 节点。簇内普通节点由簇头管理， 每簇由一个簇首节点和多个簇成员组成。多个簇首形成高级的网络，簇头节点 主要完成融合簇内普通节点数据融合、融合后数据转发的工作。层次的划分依 据具体的网络需要而定。 分层路由优点有很多，如有助于数据融合、降低通信总量，通过通信时槽 分配，减少节点无线电模块的监听事件、降低能量消耗。分层协议将网络划分 为多个独立的簇，每个簇收集簇覆盖区域内的数据，传感网络与移动机器人系 统的信息交互提供基础。 图1 - l l e a c h 即低功耗自适应分簇算法并不是一个单纯的路由协议，它提供了一 个包括分群、路由、m a c 和物理层的完整的无线传感器网络的协议框架。有的 学者从l e a c h 建立分群结构的角度，将其归于拓扑控制的范畴。l e a c h 把网 络的工作过程分为轮，每一轮包括建立期和稳定期。在建立期执行分群协议， 把网络分成若干个群；稳定期分成若干帧，在每一帧，成员节点向群首发送数 据，群首合并后发送给基站。l e a c h 适用于周期性信息报告、s i n k 距离传感器 网络距离大的情况。是无线传感器网络分簇协议中最经典的协议之一，成为很 多路由协议参考和比较的基准。其主要贡献：一是建立了分群网络结构下无线 传感器网络信息收集的能耗分析模型，并基于此优化了系统设计参数；二是提 出了基于剩余能量的动态群首轮替算法，适合于大多数无线传感器网络的分群 协议【3 1 。 4 武汉理工大学硕士学位论文 t e e n 是在l e a c h 的基础上改进的一种适用于事件触发式信息报告的路由 协议，其分群算法与l e a c h 相同，但是在数据传送阶段以阈值控制数据发送时 机，降低了数据传输量。协议中设置了软、硬阈值( s t h d 。s t 设定后，依据数 据是否超出s t 来选择是否更新s t ，若数据超出s t ，则将数据设定为新s t 。 h s 的更改不同于s t ，只有当数据超过了h s ，并且变化幅度远超过s t ，此时， 节点会传送新的数据，并将此数据设定为新的h s 。t e e n 协议通过上述过程调 节h t 、s t 的大小，在精度要求和系统能耗间取得折中效果。如果要求系统能 够反映被检测对象细微的变化，则可以减小软阈值，这种情况下能耗也在增加； 如果要求系统的检测精度并不高，则软阈值可以设定的比较大，这种情况下能 耗也较低。t e e n 存在的主要缺陷是硬阈值在第一轮中只可能上升，如果由于一 些干扰导致阈值上升到很高的水平，本轮中其余时间内，节点将不会传送任何 数据【4 】。 p e g a s i s 是针对l e a c h 的改进。它的基本思想是网络内所有的传感器节点 构成“链 ( c h i n ) ，在议论中，全网只选择一个群首节点，在这里称为l e a d e r 。 链中节点与相邻节点通信，把收集到的数据沿着链逐跳汇聚到l e a d e r ，再有 l e a d e r 把数据发送给s i n k 。一轮通信开始前建立链，在每轮工作完成后，重新选 择一个l e a d e r 。由于每轮中只选出一个节点作为群首，p e g a s i s 设计了一种基 于节点i d 的算法，避免多节点竞争：在第i 轮，i d 号为( i m o d n ) 的节点成为 本轮的群首。从距离s i n k 最远的节点( 根据物理位置信息得到) 开始，采用贪 婪算法构造链，也可以用s i n k 计算链，然后广播给所有传感器节点。数据收集 过程由l e a d e r 发起，l e a d e r 向链的一端的端节点传送t o k e n ，由端节点收集数据， 然后把分组以及t o k e n 传送给链上的相邻节点，相邻节点接收到t o k e n 后，把自 己采集到的数据与收到的数据合并为一个分组，发送给链上下一跳节点，这样 一直到l e a d e r ：收集完链的一端的数据后，再把t o k e n 传送到链的另一端的端节 点，重复上述收集过程。最后，由l e m e r 将两个数据进行融合后发送给s i n k 【5 j 。 ( 3 ) 地理位置路由协议 鉴于无线传感器网络以及一些自组织通信网络对能量有效性问题的关注，一 些地理路由协议利用节点地理位置所体现的空间方向性以及位置信息，通过合 理选择每个中继节点以及根据每一跳的距离对发射功率进行调整，可以对端到 端的通信总功率进行优化。 g e a r 以地理单播和区域内多播结合的方式实现地域多播。该协议针对的是 5 武汉理工大学硕士学位论文 无线传感器网络中查询命令转发到被查询区域的应用场合。在地理单播的过程 中综合考虑节点的能量和到目的地的距离，设计路由度量指标；当分组传递到 目的区域边缘时，改用递归转发或区域广播的方式。和其他地理单播路由类似， g e a r 在把分组以地理单播的方式项目地区域传输的过程中，也会遇到地理信息 出错或者节点移动后位置信息未及时更新的情况，这些对算法的性能有一定的 影响。为了均衡节点的能耗，算法采用的路径比直接根据地理位置信息转发所 选择的路径要长，这主要发生在网络运行的后期、节点能耗已经不均衡的情况 下【6 】o g r i d 的核心是利用节点的地理位置信息划分栅格，使得在选择路由时实际 上是选择下一个栅格，而非具体的下一跳节点，而群首选举过程保证了每个栅 格中一定存在群首节点进行转发。g r i d 最初设计针对移动性网络，而如果把它 应用于无线传感器网络，其优势更为明显。在无线传感器网络中，节点位置基 本静止，大多数业务是以s i n k 为目的节点，节点可以预先获得其位置信息。这 种情况下，直接根据栅格的相对位置关系转发，而不需要路由建立过程。栅格 的大小对于协议性能有一定影响。例如。以d 5 划分的栅格，只有上下左右四 个方向上的相邻栅格一定可达，而考虑到距离目的更近的情况，在相邻栅格不 交互的情况下，最多可以选择相邻的两个栅格作为下一跳。这会导致路径加长， 端到端能耗增大i _ 7 1 。 1 2 2 压缩感知算法研究现状 无线传感器网络中，压缩感知最能体现其优越性的就在压缩掉数据量的大小 上，压缩后需要传输的数据量越小，说明压缩感知算法对w s n 网络贡献越大。 而由于无线传感器节点最大的缺点就是处理数据的能力有限，因而s i n k 处理的 传感器节点的数目也是有限的。压缩感知算法的采集少量节点信息并可以恢复 整个网络信息的特点刚好能够克服传感器网络的这一缺陷。 应用压缩感知算法到无线传感器网络，首先应将压缩感知理论中的稀疏矩阵 与观测矩阵与具体的传感器网络中对应。一般情况下，观测矩阵很大一部分都 对应于网络的路由路径，稀疏矩阵的确定由具体的应用背景来对应。 地理位置路由算法，在传感器网络中设定一个s i n k 节点，w s n s 内所有的普 通节点都将自身的信息发送到s i n k 节点。在此文中，原始信号被对应到传感器 网络区域内所有的传感器节点，观测矩阵对应为s i n k 收到数据包的数量。观测 6 武汉理工大学硕士学位论文 矩阵中的每一个值为一条发送路径上对应的一个节点传输的权值，即对应的节 点传送数据包数量的权值。有上述算法可以知道，这种地理位置路由算法中， 观测矩阵的行向量代表了一个数据包从节点发送开始直至到达s i n k 节点时的一 条路径，即当数据包的当前传送路径包括节点时，节点对应的矩阵元素值即为 传送权值，若数据包的当前传送路径不包括节点，那么该节点对应的矩阵元素 为0 1 8 使用分区的方式将无线传感器网络分成了块区域，并且假设每个区域内不 多于一个目标源的存在，目标源可以被表示为维向量，无线传感器节点对目 标源进行探测，若探测到目标源的存在，则该区域对应的向量的值为1 ，反之若 不存在，则该区域对应的向量值为o 而稀疏矩阵则对应到传输消耗公式以及每 个传感器节点的探测值经过数学变换后的矩阵 9 1 。 以探测目标源作为原始信号，将原始信号的可能长度作为向量的长度。若探 测目标数目为m ，总网络节点数为n ，m ，n ，构成了原始信号的稀疏表示模型。 观测矩阵的任务在于探测出目标源总数目。此文中将系统的感知能力定义为 m n 。原始信号的稀疏程度以及传感器节点的覆盖范围决定了网络节点感知能力 的上下限【l o 】。 通过整合已有技术来定位目标。假设探测目标为主动噪声源，数目为m ，网 络中共有n 个传感器节点，其中m ，n ，将网络分为面积相等的n 个子区域。将 网络中的n 个节点中的信息表示为n 维向量的形式，每一个元素对应网络中的 一个节点。每一个元素的具体值为此节点接受来自各目标源的信号。将目标源 向量也设定为n 维，每一个向量代表对应节点区域内是否存在目标源，存在则 元素值为1 ，否则为o 。节点矩阵与目标源矩阵之间可以通过传播消耗矩阵进行 关联。即在压缩感知模型中，节点信息可以表示为传播消耗矩阵以及目标源向 量的乘积。由于m ，n ，因为节点矩阵具有稀疏性。在传感器节点对周围进行了 感知操作后在n 个节点中抽取m 个节点的信息传递给s i n k 节点。将选举节点 并将数据最终送往s i n k 节点的节点情况的矩阵设定为观测矩阵。最后通过重构 算法，在s i n k 节点处通过收到的观测数据以及已知观测矩阵和稀疏矩阵的情况 下，重新恢复成原始信号向量l l 。 从路由角度出发，通过b a y e s i a n 自适应重构算法，在考虑了重构精确度以及 路径的能量消耗后，选择观测向量。在传感器网络中设定一个s i n k 节点，其余 的每个传感器节点中的存储自身的数据。对应于传感器网络的n 个节点，设定 7 武汉理工大学硕士学位论文 原始信号向量的维数为n 。将压缩感知理论中的观测矩阵行向量设定为每一条通 往s i n k 节点的节点路径情况，即对应的路径上若经过节点，则观测行向量对应 的原始值为l ，反之为0 。以重构出的信号的微分最小即不确定性最小作为前提， 进行自适应的选择路径即观测行向量。在设定过程中，以重构精度作为判断， 只有重构精度达到需要的标准的前提下，观测行向量被采用，否则重新选择观 测向量。文献同时将路由能耗情况加入考虑范畴内【1 2 】。 通过p c a 构建原始信号压缩感知模型。模型假设在整个网络中有n 个节点， 对应于传感器网络的n 个节点，设定原始信号向量的维数为n 。原始信号向量 的均值、协方差阵可以得到压缩感知算法中的稀疏矩阵与稀疏系数。p c a 是通 过数据降维来压缩数据，从n 维降低到m 维，且m n ，压缩感知理论则是 降低传输的数据总量，在数据方面来说也可以看成是另一种降维方式【1 3 】。 应用到目标探测系统中。假设网络中的所有节点中，有一部分节点处于休眠 状态，且目标探测源信号收到距离的影响，只能影响到周围某一部分节点。此 模型中不设定s i n k 节点，每个处于非休眠状态的节点都需要判断自身以及周围 节点的值来估计原始信号值。传感器节点间运用一直算法迭代的计算新的估计 值。 以上所述的均为具体的无线传感器网络中的压缩感知应用，但是这些算法都 是基于平面路由的基础上了，没有涉及到层次路由协议。本文中将压缩感知理 论应用到了层次路由协议具体为分簇协议上，更加体现出压缩感知理论的优势。 1 3 论文组织结构 本文主要针对解决降低无线传感器网络中的能量消耗以及均衡每个节点的 能耗问题进行了研究。 首先，针对了均衡节点能量这一问题，对一种基于环能耗相等的前提提出的 分环多跳的分簇算法进行了分析研究。研究的分环多跳分簇算法在传统的分簇 算法的基础上，将l e a c h 算法的基础思想应用到了每一个环上，让每环上的节 点利用独立的阈值判断进行独立的簇首选择操作。这一重要的思想的前提是， 已知每一环上最优簇首的数目，在传统的分簇算法中，簇首的数目一般都由自 己规定，但是在研究的此算法中，最优的数目的确定是假设当网络处于理想的 均匀密集分布的情况下，使得每一环上的能耗差异最大的分簇节点，能够在融 合、转发、发送数据包之后，仍能够保证，每一环上的簇首的消耗是相等的， 武汉理工大学硕士学位论文 即每一环上的能耗差异最小，以此来保证能耗均衡从而提高整个网络的生存时 间。 其次，第三章中针对传感器网络能耗的另一个方面，即降低传播同等信息时 需要消耗的能量大小为目的进行了研究。此章节中研究了一种应用于信号压缩 的压缩感知算法，该算法本应用于进行图像处理，即依据数据间的相关性，利 用比传统奈奎斯特采样定理少得多的采样信息，传播信息。研究过程中，以无 线传感器网络中的目标探测作为应用背景，将目标源信号集合在网络中的传输 消耗作为压缩感知算法对应的稀疏矩阵，将探测过程中每一个簇内节点的信息 作为观测矩阵的行向量，将目标源的具体位置作为原始信号。对传输到s i n k 节 点的矩阵信息，利用贝叶斯重构理论对其进行信号恢复，最终得到信号源的位 置。此算法比较传统的压缩算法最大的优势在于，使用更小的采样率，以高准 确度的恢复率传播信息，使得网络中同等信息所消耗的节点能量降低，同时， 也降低了s i n k 节点的处理数据的复杂度，以此来最终高效的节省网络能量，延 长网络寿命。 第四章主要为综合性延长传感器网络寿命做出相关研究。仍然以传感器网络 中的目标探测作为主要应用背景，结合第二章中的分环多跳算法以及第三章的 压缩感知算法。在获取即采集目标源信息时，利用压缩感知算法，将数据集中 到各个簇首节点上，但在之前的应用基础上，更进一步在传播方式上做出改进， 将直接传播融合后的数据包传输到s i n k 节点的方式改为依据环及下一跳路由转 发的方式将信息传递给s i n k 节点，利用了分环多跳以及压缩感知算法的优势使 得目标源探测过程能高效且节能的完成。 9 武汉理工大学硕士学位论文 第2 章基于热点抑制的分环多跳分簇算法的研究与 仿真分析 2 1 无线传感器网络概述 图2 1 所示为w s n s 基本结构。可以看到w s n s 主要包括四部分： ( 1 ) 网络用户。它需要从网络中获取各种需要的信息，并进行选择分析， 并可以对网络下达各种命令； ( 2 ) 传输方式。包括i m e m e t 及通信卫星等。是用户与w s n s 通信的桥梁； ( 3 ) s i n k 节点。能量以及无线收发功率可以作为无限值，将从w s n s 中能 量有限节点上获取的信息进行处理转发到媒介上，同时具有传达用户指令给网 络节点的能力； ( 4 ) 传感网络。整个w s n s 的核心部分。在网络感知区域内，所有的节点 搜集感知数据以直接传递或路由转发的形式发送给s i n k 节点。同时，也可以接 收s i n k 节点的命令，将自身的工作状态进行更新1 1 4 。 图2 1 1 0 武汉理工大学硕士学位论文 2 2 分环多跳分簇算法 对于无线传感器网络路由算法，目前已经存在有很多种，如平面路由、层 次路由、地理位置路由等。而分簇路由则是其中被关注的最多的路由方法之一。 分簇算法属于一种层次型的机构，在网络中节点被分为了三种层次类型：普通 节点、簇首节点和s i n k 节点。在网络通信过程中，普通节点的信息都被集中收 集到各簇首节点中，最终被收集到s i n k 节点。这是一种集中式的管理方式，同 时又是一种分布式的方式，从而实现了簇首间的协调，具有良好的协调性。虽 然分簇结构在某些方面能改进系统的性能，但在无线传感器网络的路由中仍然 存在着问题。由于网络中s i n k 节点往往只有一个，簇首节点在通常情况下也是 远远小于簇内普通节点，这样，在无线传感器网络区域面积很大的情况下，由 于多对一的传输消耗能量模式，会使得靠近s i n k 的节点有很大的通信压力，很 容易由于过多的转发数据消耗能量，而产生能量耗竭的情况，这就是所谓的“热 点 ，如何缓和热点问题，是在设计无线传感器网络路由时要考虑的一个重要问 题。在本章中，将对这一问题进行深入研究，提出一种基于剩余能量以及最短 路径的分环结构的能量均衡路由算法。 2 2 1 传统分簇算法 l e a c h 算法实际上是一种基于概率的分簇技术，这样的概率分簇技术在达 到某种特性如平衡簇的大小的情况下，能够保证算法的快速收敛性。在网络分 簇时，控制消息占很小数量的情况下，每个节点仍能够独立的决定自己的角色。 l e a c h 算法的主要目标是尽可能的使能量消耗均匀的分布到各个节点上，不造 成个别节点的集中能量消耗，从而延长网络的寿命。 l e a c h 算法是周期性的执行，每个生命周期被称作了一“轮，每轮包括 有簇建立阶段以及数据通信阶段。 簇建立阶段：随机选择簇首，簇首之外的普通节点动态的选择自己的簇首， 最终形成簇。 簇首选举过程如下：在整个选举过程中，每个节点都随机的产生一个( o ，1 ) 区间内的值，并将此随机值与阈值t ( ，2 ) 进行比较，若随机值小于t ( n ) ，节点选 举自身为簇首节点，并向外广播簇首信息。每一轮循环中，如果节点已经成功 当选过簇首，则阈值t ( n ) 将被置为0 ( 即该节点不会再次被选为簇首) ；对于 武汉理工大学硕士学位论文 未当选过簇首的节点，以t ( n ) 的概率当选。随着当选过簇首的节点越来越多， 未当选过簇首的节点的当前闽值t ( n ) 越来越大，这样，它们当选簇首的概率 就相对增大。t ( n ) 表达式如( 2 1 ) ： rp m ) _ 夕叫 刮脚椰 协。， l0 ，其他 其中，p 为簇首占节点总数的百分比，r 为选举轮数，m o d 【形) 表示当前这一 轮中当选过簇首的节点数目，g 为这一轮中未当选过簇首的节点集合。 数据通信阶段：簇内节点将自身所携带数据发送给簇首，簇首融合了自身 以及簇内节点的数据后，发送给s i n k 节点【1 5 】。 在l e a c h 的簇首选举过程中，由于没有考虑节点的位置信息，随机所选择 出来的簇首可能会在位置上很集中，不利于整体网络的能量均衡，且容易造成 簇首间的无线通信干扰，并且l e a c h 只考虑了单跳通信的情况。 2 2 2 分环多跳分簇算法 假设在半斤为r 的圆形区域内分布着n 个传感器节点，节点具有时间同步 功能。节点的能量可以被考虑成同构( 能量相同) 或者异构( 能量有优劣之分) ， s i n k 节点位于圆形的圆心位置，圆形区域的面积很大，远离s i n k 节点的普通节 点将无法传送数据到s i n k 。 由于远离圆心位置的普通节点无法与s i n k 节点进行通信，所以算法采用多跳 的形式，向心的方向传递数据给靠近圆心的节点。从s i n k 节点开始向外，将圆 环标记为第一环、第二环，一直到最外环s 环，如下图所示的向心传递方式： 武汉理工大学硕士学位论文 图2 1 算法如下所述： ( 算法在s i n k 节点上配置区域的总体信息i ，定义为i _ i 乙n ，s ) ) ( 1 ) 将半径为r 的圆形区域等环换分为s 个环，单位环半径差值为万，即 r _ s 万； ( 2 ) 节点根据自己的位置信息，判断出自己所在的环位置，加入到所在环 的集合中； ( 3 ) s i n k 通过整体信息集合i ，计算出各个环的初始簇首选举概率，并向区 域内广播； ( 4 ) 各环内的节点根据自己接收到的广播信息进行独立的簇首选举： ( 5 ) 未当选为簇首的节点根据周围的簇首通告，加入到距离自己最近的簇 首所在簇中去； ( 6 ) 外围环的簇首选择向内一环中，距离自己最近的节点作为下一跳的路 由节点； ( 7 ) 进入数据传输阶段，普通节点向簇首发送数据，簇首融合数据向下一 跳路由发送数据，作为下一跳路由节点的传感器节点转发数据； ( 8 ) 一轮结束，进入新的一轮，重复执行步骤3 7 。 武汉理工大学硕士学位论文 2 2 3 算法流程 图2 2 1 4 武汉理工大学硕士学位论文 如图2 2 所示，n 个节点在随机的部署完成之后，s i n k 节点根据信息i 计算 出每个环的最优初始簇首选举概率t ( n ) ，完成后，将总体信息i 、各环概率t ( n ) 向整个网络中进行广播。区域中的每个节点p 。( 勘y ，) ，通过总体信息i 以 及自身的位置信息，确认自己所在的环k ： 若( k - 1 ) 万 d ( p ，p o ) k 万，则p ；是位于环k 。 其中d 是代表着节点i 到圆心的距离，即当前节点的圆心半径，确定了所在 环之后，节点就可以确定自己进行簇首选举的概率。 确定了各个节点所在的环以及每环最优簇首选举概率之后，进行独立的簇首 自选。当选的节点向周围发送簇首当选消息以及自己的位置信息，使得周围的 簇首以及普通节点都接收到此消息。簇首通告结束之后，普通节点从接收到的 周围的簇首的广播信息，选择距离自己最近的簇首，成为其簇内节点，并向其 发送消息表明自己加入。而k + l 环的簇首节点则从接收到的第k 环簇首消息中， 选择距离自己最近的簇首作为下一跳路由节点，并向此簇首发送消息，形成簇 与簇之间的多跳路由。同时也要考虑特殊情况，即没有收到任何信息的节点( 主 要是由访问冲突以及信号干扰等因素造成的) ，对于这样的节点，我们让它向外 广播本身的节点信息，包括自己的地理位置及i d 。收到节点消息的簇首用单播 的方式向它返回应答消息，节点进行再次