一种可扩展的无线传感网络数据聚合方法

[0001] 本发明设及无线传感网络领域特别是设及可扩展的无线传感网络数据聚合方法 的设计。

[0002] 无线传感网络（WirelessSensor化tworkWSN)由一组具备感知、通信和计算能 力的传感器节点组成，它的一个关键应用就是数据汇集即传感器将数据（可能通过多跳 的形式）传送到汇聚节点上。在实際应用中网络使用者经常关注的只是传感器节点测量 数值的一个特定函数值，而不是需要所有测量数值的原始值网内数据聚合在提高傳感网 络的容量方面发挥着重要的作用，是WSN节约能量的主要手段之一原因是通信的能量消 耗要远远高于计算的能量消耗。因此有必要針对汇聚节点关注的特定函数定义传感网络 的计算和传输数据的综合能力。各种数据聚合方法已被提出它们或者基于集簇，或者基于 树結构在数据聚合的应用中，如环境或栖息地监测传感器周期性地感知数据并传送给汇 聚节点。当假设传输模式和网络拓扑不动时通瑺可采用基于结构的方法，运种方法需要相 对小的维护开销 本发明针对一般密度的WSN设计可扩展的聚合方法，旨在提高WSN的聚合吞吐量和汇 集效率的权衡

[0003] 本发明目的在于克服现有技术的不足，提供一种提高无线传感网络（Wireless Sensor化tworkWSN)数据聚合吞吐量的聚合方法。对于一般密度的WSN聚合吞吐量会受 到两种因素的限制：孤立分支和密集分支。为了克服运两种限制本发明的方法思路中提出 了 "针对密集分支的局部选点法囷针对孤立分支的自适应弃点法"。 为此本发明方法技术方案表征为： 一种可扩展的无线传感网络数据聚合方法，其特征在于面向WSN的数據聚合，设计两 类基于拓扑结构的聚合方法：单一链接长度方法和复合链接长度方法所述单一链接长度 方法：该方法是无职务层次和职級的结构，由相同阶长度的链接构成依据给定的汇集效率需求，在局 部区域选取一定数量的节点W缓解密集分支限制的方法来提高网络嘚聚合吞吐量。所述 复合链接长度方法：该方法是职务层次和职级化的结构由多种不同阶长度的链接构成。依据给定的汇 集效率需求從局部选取一定数量的节点并限制长跳的长度，W同时缓解两个限制的方法 来提高网络吞吐量本发明通过设计运两种有效的方法，结合提絀的"弃点"和"选点"的 方法理念可W提高WSN的聚合吞吐量和汇集效率的权衡。特别地结合单一链接长度方法 和复合链接长度方法，为一般密度嘚WSN针对可分完美压缩聚合函数可W得到聚合吞吐 量和汇集效率间的最优权衡。同时将分组编码技术引入到单一链接长度方法，W此进一步 提高聚合吞吐量和汇集效率的权衡 本发明的目的主要是，考虑可分完美压缩聚合函数设计高效可扩展的数据聚合方法， 结合"弃点"和"选點"的方法理念提升吞吐量和汇集效率之间的权衡。

[0004] 针对具体的应用需求比如，完全覆盖、k-覆盖、连通性等节点的部署密度通常是 一個变化范围很大的变量。因此本发明考虑一般密度的WSN，而不是像大多已有工作那样 考虑两个特例即，随机密集WSN和随机扩展WSN

[0005] 在针对随機WSN的基于结构的聚合方法下，网络聚合吞吐量主要受限于W下两个 因素：孤立分支和密集分支孤立分支：在随机网络中，给定链接长度的仩限将存在一个 大连通分支，其中任意节点对可W通过一系列符合长度的链接连通起来然而，可能有些点 远离（不属于运个连通分支）称作孤立分支。为了达到运些点需要一些更长的链接从而 导致更低的链接速率。密集分支：给定一个确定性路由在其链接的冲突图當中，可能有一 些团图的顶点数目非常大从而，调度运些对应的边的过程将可能成为系统瓶颈

[0006] 为了克服W上的限制，本发明设计两个有效的聚合方法W提高网络的吞吐量和汇 集效率的权衡

[0007] 单一链接长度方法：该方法是无职务层次和职级的结构，由相同阶长度的链接构成依据给定 的汇集效率下界，在局部区域选取一定数量的节点W缓解密集分支限制的方法来提高网 络的聚合吞吐量。

[0008] 复合链接长度方法：该方法是职务层次和职级化的结构由多种不同阶长度的链接构成。依据 给定的汇集效率下界从局部选取一定数量的节点并限制长跳的长喥，W同时缓解两个限 制的方法来提高网络吞吐量

[0009] 在详细描述单一长度方法和复合链接长度方法之前，先给出：

[0010] 可达聚合吞吐量 一个吞吐量A(n)对聚合函数g是可达的，如果存在一个聚合方法A可W把任意泌WXW居诚"靖用时1'(4,,。）聚合到汇聚节点上得到縣(辦*^^):，其中

[0011] 汇集效率 记一个聚匼方法为口(平?n))，其中 ?S(中耐E二柄，0 <i<n- 1}WG(0,1]用来衡量汇集效率。 ?输入任意来自《(￥ ?切中的传感器的测量值巨说在汇聚节点输出

?定义比率W为给定聚合方法Aw，,;掉(4^ ?的)的汇集效率

[0012] 特别地，本发明考虑一类重要的对称函数称之为可分完美压缩聚合函数。称一个 可分的函数为完美压缩洳果来自不同传感器的同一轮的测量值可W聚合成与原先长度相 同的新的数据。从而有W下运个引理

[0013] 可分完美压缩聚合函数的压缩长度 对任意的可分完美压缩聚合函数gk，1《k《n有I氣I= 0(m)，其中氣是函数gk的值 域

[0015] 然后，本发明设计两个聚合方法：单一链接长度方法和复合链接长度方法

[0016] 单一链接长度方法

[0017] 为了描述方便，首先给出下面定义和引理

[001引机制网格 将一个义形K域呢如，a2)叫0,0!2分割成边长为5的小方格子称生成的網格图为机制 网格，并记为lL(a,幻,巧其中

表示格子的边与:^如,a2)边之间的最小夹角。

[001引基于机制网格

0，》0来设计聚合方法Aw,巧0F，n))每个格子 中嘚节点数目的范围为[(I-^A)Inn，（1+^5)Inn]其中￡4和e5是依赖于Z的满足表 格1中条件的常数。记左下角的格子为原点（〇,〇)按照从左到右、从下到上的顺序給每个 格子一个二维坐标，即左上格子为（55 )，其中6 = 5如）=万而^ -1不失一般性，假 设汇聚节点位于格子（5, 5)中随机从每个格子中选取一个节點作为聚合站点，并仍旧 将聚合站点的集合记为进则有r川二n/OlnsO,,令/e?表示格子（i，j)中的站点 表格1相关常数的预设条件

[0021] 局部聚合：在叫中的每個格子里，随机选取e-Inn个传感器节点（如果有）其 中，

.N轮的测量值W单跳的形式聚合到站点上；所有传输用一 个4-TDMA机制调度如图3左。

[0022] 水平骨幹聚合：每个聚合存储的N轮数据按从左至右的顺序W流水线的方式聚合 到相邻的聚合站点上；所有传输用一个9-TDMA机制调度如图3右所示。

[0023] 垂直骨干聚合：第5列中的每个聚合站点存储的N轮数据按从下至上的顺序W流 水线的方式聚合到相邻的聚合站点上；所有传输用一个3-TDMA机制调度如圖3右所示。

[0024] 复合链接长度方法

[002引基于机制网格1*2 = 1(^^〔八/1,;774，.^)来设计聚合方法沒%3^0;(；乎.扣^)其中c〉0是一个满足 表格1中条件的常数。从每个非空的格孓中选取一个节点作为聚合站点构建聚合骨 干，如图2所示称骨干上的聚合站点为骨干站点，称其他的聚合站点为外围站点所有的 外圍站点可W通过一个单跳传输接入骨干站点。

[0026] 对一给定常数K> 0,将机制网格分割成水平（垂直）长方块其水平（垂直） 长度为"/w/A垂直(水平）长度為.卿二（Kinm) . 其中，w=Vn/(V^)假设m/ (KInm)(表示长方块的数量）是一个整数。从而有

则存在一个依赖于C和K的 常数放使得对所有水平（垂直）块有至少堀?Ih奶条沝平（垂直）聚合骨干，其中

[0028] 当聚合骨干建成之后每个长方块的格子可W平均分配给風?化瓶条骨干。比方 说可W将每个长

无线传感器网络的协议栈由物理層、数据链路层、网络层、传输层和应用层组成

网络层负责路由的发现和维护，一个网络设计的成功与否路由协议非常关键。从图中嘚架构可看出无线传感器路由协议的分类我们择其中的一部分进行分析。

扩散法是一种传统的最基本的网络路由协议不需要知道网络拓朴结构和使用任何路由算法。节点将数据副本广播给每个邻居节点邻居节点又将其传输给各自的每个邻居节点，直到将数据传输到目標节点为止

优点：①实现简单；②不需要为保持网络拓扑信息和实现复杂的路由发现算法而消耗计算资源；③适用于健壮性要求高的场匼。

缺点：①存在信息爆炸(Implosion)问题；②出现部分重叠(Overlap)现象；③盲目使用资源

Hedeniemi S等人提出的Gossiping闲聊法是扩散法的改进版本。节点随机选择某一个鄰居节点转发分组而不是用广播，如果一个节点第二次收到它的邻居节点的数据副本则将此数据发回邻居节点。

优点：节约能量 避免了“内爆”问题。

缺点：仍然无法解决部分重叠现象和盲目使用资源问题而且数据传输平均时延拉长，传输速度变慢

以数据为中心嘚路由协议是基于查询和对目标数据的命名之上的，通过数据聚合减少重复的数据传送以数据为中心路由还可分为：事件驱动模式和查詢驱动模式。

SPIN是由Kaulik等提出的第一种以数据为中心的自适应通信路由协议节点仅广播采集数据的属性描述信息（元数据meta-data）而不是数据本身，当有相应的请求时才有目的地发送数据信息。

优点：①元数据的传输耗能相对较少；②只广播其它节点没有的数据减少了能耗；③鈈维护邻居节点信息，适应节点移动的情况

缺点：健壮性差。会出现“数据盲点”进而影响整个网络信息的收集。不适用于高密度节點分布的情况

Boulis等人提出的谣传路由是DD的一个改进。节点的代理消息、汇聚节点的查询消息各自沿随机路径传播当两条路径交叉在一起時，形成一条完整路径

优点：避免了大量扩散过程，显著节省能量适用于数据传输量较小的情况。

缺点：如果网络拓朴结构频繁变动性能大幅下降。

当节点经中转到目的节点的传输能量小于它的最短路径的传输能量时选择该中转节点转发数据。

优点：简单、开销小每个节点只需要找到通往Sink节点的下一跳节点，然后把数据发给它

缺点：节点之间负载不平衡，靠近汇聚节点的节点因路由任务过重很赽耗尽能量而死亡缩短了整个网络的生命。

基于地理位置的路由协议利用位置信息传送数据到指定区域而不是整个网络来降低能耗。這方面的协议主要是来源于移动Ad-hoc网络设计时考虑了节点的移动性。但是它们在节点移动很少或者根本不移动的情况下也非常适用

GEAR也可鉯认为是Directed Diffusion方法的一种改进。利用位置信息向某一个特定的区域广播查询请求根据位置信息和节点能量剩余情况，将数据发回到汇聚节点

优点：避免了扩散传播，节省能源网络寿命延长。

缺点：由于缺乏足够的拓朴信息路由过程中可能遇到路由空洞，反而降低了路由效率只适用于节点移动性不强的应用环境。

基于服务质量的路由协议的目标是在实现路由功能的同时满足一些网络QoS要求这类路由协议茬建立传感器网络的路由路径的同时，考虑端对端的时延要求

SPEED提供了端对端的软实时(soft real-time)保证。交换节点的传输延迟得到网络负载情况；利用局部地理信息和传输速率信息做出路由决定。邻居反馈机制保证网络传输速率在一个阈值之上反向重路由变更机制避开了延迟大的鏈路和路由空洞。

优点：实现了端到端的传输率保证、网络拥塞控制以及负载平衡机制该算法和AODV与DSR比较，性能有一定提高能满足end-to-end delay和预萣传输速度，消耗的总传输能量较少

缺点：没有考虑在多条路径上传输以提高平均寿命，传输的报文也没有优先级机制

低能自适应聚類体系（LEACH）

Hierarchy)是MIT的Chandrakasan等人为无线传感器网络设计的低功耗自适应聚类路由算法，是第一个基于多簇结构的分层路由协议它是主动网络的路由算法。该协议分为两个阶段操作即簇形成阶段和稳定工作阶段，两个阶段所持续的时间总和称为一轮在簇形成阶段，随机选择一个节點作为簇头簇形成后进入稳定工作阶段，簇头开始接收簇内各节点采集的数据然后采用数据融合技术进行处理，将整合后的数据传输給Sink

优点：随机选择簇头，平均分担路由业务减小了能耗。

缺点：①不适合大范围的应用；

②集群分组方式带来了额外开销以及覆盖问題；

③仅适用于每个节点在单位时间内需要发送的数据量基本相同的情况而不适合突发数据通信。

门限敏感的节能型网络协议（TEEN）

protocol)算法茬LEACH算法的基础上针对检测突发事件的场景，对sensor节点进行两次集群分组定义硬、软两个门限值，以确定是否需要发送测数据当监测数據第一次超过硬门限时，节点用它作为新的硬门限并发送它。如果监测数据的变化幅度大于软门限则节点传送最新的数据，并将它设萣为新的硬门限

优点：数据传送量比主动网络少，节省大量能源适用于响应型(Reactive)应用。

缺点：如果某个节点的检测数据始终达不到硬门限用户将无法得到任何数据，也无法知道这个节点是否失效因此这个方法不适用于需周期性采样的网络。

Estrin等提出了一种两层的分簇算法处于某一层的节点同其广播半径及跳数有关，所处职务层次和职级越高所覆盖面积越大。此算法可以扩展成一个多层的簇体系

缺點：在形成多层簇类的过程中会额外消耗一些能源，而且网络需要形成多少层，按照什么策略形成职务层次和职级等都是值得继续探讨嘚课题

Younis(三层体系结构的路由协议)

Younis等人提出了基于三层体系结构的路由协议。用户划分簇并将簇头ID和簇内节点位置通知每个簇头。簇头監控节点的能量变化决定并维护节点的状态（感知、转发、感知并转发、休眠），评价节点间传输链路的成本选择最小成本路径作为朂优路径。

优点：具有很好的节能性能、较高的吞吐量和较低的通信延迟

network，WSN）是由大量传感器节点通过无线通信技术自组织构成的网络它集成了传感器、微机电系统和网络三大技术，目的是感知、采集和处理网络覆盖围内感知对象的信息并转发给观察者，是以数据处悝为中心的系统它是信息技术的新领域，军事和民用领域均有非常广阔的应用前景

无线传感器网络除了具有传统无线网络的共同特征鉯外，还具有很多其它特点

网络具有大规模、自组织、动态性、可靠性

传感器节点的数量可能达到几百万个。网络经常有新节点加入或巳有节点失效网络拓朴结构变化快，人很少干预其运行传感器必须具有相应的通信协议必须具有可重构和自适应性、高健壮性和容错性。

传感节点电源能量、通信能力、计算存储能力有限

传感器采用电池供电能量有限，因此节能设计非常关键无线传感器网络以 “多跳”方式传输数据，通信范围只有几十米传感节点由于体积、成本以及能量的限制，处理器和存储器的能力和容量有限因此计算能力┿分有限。

传感器网络的设计必须以感知数据管理和处理为中心把数据库技术和网络技术紧密结合，实现一个高性能的网络系统使用戶自如地在传感器网络上进行感知数据的管理和处理。

不同的传感器网络应用关心不同的物理量对系统的要求也不同，其硬件平台、软件系统和网络协议有很大差别

建立安全路由已成研究热点

无线传感器网络是一种新的信息获取和处理技术。在特殊领域有着传统技术不鈳比拟的优势必将开辟出不少新颖而有价值的商业应用。

但是在这方面的研究中，目前尚存在几个值得思考的问题：比如如何实现精简协议族、如何实现节点的自组织和重配置、如何设计异构的网络路由协议、如何设计适用于移动的网络路由协议以及网络安全问题。

對于无线传感器网络大多数路由协议都没有考虑安全的需求，都易于遭到攻击从而使整个网络崩溃。无线传感器网络的主要攻击有：虛假路由信息（通过欺骗分割网络，增加端到端的时延）、选择性的转发（导致数据包不能到达目的地）、Sinkhole攻击（攻击节点声称自己电源充足、性能可靠而且高效,所有的数据包都发向它）、Sybil攻击（攻击节点以多个身份出现和其他攻击方法结合使用）、Wormholes攻击（两个恶意节點合谋进行攻击，吸引数据包发向离基站较远恶意节点）、HELLO flood攻击（恶意节点用足够大的功率广播HELLO包以声明自己是其他节点的邻居节点）。

由于传感器节点本身的处理能力、电源以及通信能力方面的限制因此，如何建立节能、高效、健壮、安全的路由协议将是无线传感器網络研究中富于挑战的课题之一