一种应用于无线传感器网络的快速数据融合算法

摘要

一种基于虚拟单元格的快速链式数据融合算法，将整个传感区域划分为一个个的虚拟单元格，单元格内的节点都将数据发送给一个事先指定的节点进行融合，随后沿着单元格的垂直方向进行链式的数据融合过程，每条链每次只有一个节点将数据发送给Sink节点。为了均衡节点的能量消耗，节点之间都是轮流担当数据融合的角色。本发明的有益效果是，CFDASC算法中组成的数据传输链很短，因此数据传输时的时延很小。算法的鲁棒性好：每条链都传送数据给Sink节点。节能性较好：整个无线传感器网络区域内的所有数据最后被融合为几条链发送的数据，在数据传输过程中所传输的数据量大大减少，有效地节约了大部分的能量。

说明书

技术领域

本发明涉及一种应用于无线传感器网络的快速数据融合算法。本发明适用于无线网络应用领域，尤其适用于无线传感器网络应用领域。

背景技术

无线传感器网络(wireless sensor network，WSN)是由部署在监测区域内大量的廉价微型传感器节点组成，通过无线通信方式形成的一个多跳的自组织的网络系统，其目的是协作地感知、采集和处理网络覆盖区域中感知对象的信息，并发送给观察者。无线传感器网络节点的资源十分有限，主要体现在电池能量、处理能力、存储容量以及通信带宽等几个方面。在收集信息的过程中采用各个节点单独传送数据到汇聚节点的方法是不合适的，主要有以下两个原因。

(1)浪费通信带宽和能量：在覆盖度较高的传感器网络中，邻近节点报告的信息存在冗余性，各个节点单独传送数据会浪费通信带宽；同时，传输大量数据会使整个网络消耗过多的能量，缩短网络的生存时间。

(2)降低信息收集的效率：多个节点同时传送数据会增加数据链路层的协调难度，造成频繁的冲突碰撞，降低了通信效率，从而影响了信息收集的及时性。

为避免上述问题，无线传感器网络在收集数据的过程中需要使用数据融合(data aggregation或data fusion)技术。数据融合是将多份数据或信息进行处理，组合出更有效、更符合用户需求的数据的过程。数据融合的方法普遍应用在日常生活中，比如在辨别一个事物的时候通常会综合各种感官信息，包括视觉、触觉、嗅觉和听觉等。单独依赖一种感官获得的信息往往不足以对事物做出准确判断，而综合各种感官数据，对事物的描述会更准确。在无线传感器网络的应用中，许多时候只关心监测结果，并不需要收到大量原始数据，数据融合是实现此目的的重要手段。

数据融合算法最近已引起研究人员的重视。在无线传感器网络中，将路由技术与数据融合技术相结合是一个重要的问题。数据融合可以减少数据量，减轻数据汇聚过程中的网络拥塞，协助路由协议延长网络的生存时间。应用于无线传感器网络的路由技术中的数据融合技术主要有三大类：第一类是基于查询的路由；第二类是基于层次的路由；第三类是基于链的路由。基于链的路由的代表算法有PEGASIS算法及其高阶算法。PEGASIS算法在收集数据之前，首先利用贪心算法将网络中的所有节点连接成一条单链，然后随机选取一个节点作为首领。首领向链的两端发出收集数据的请求，数据从单链的两个端点向首领流动。中间节点在传递数据之前要执行融合操作，最终由首领节点将结果数据传送给汇聚节点。PEGASIS算法的优点在于单链的结构使得每个节点发送数据的距离几乎都是最短的，且最终只有一个节点进行远距离的数据传输。单链结构的PEGASIS算法主要有以下两个缺陷：(1)平均延迟较大：数据需要沿着单链结构顺序传送，收集数据的延迟决定于首领节点与单链端节点的距离，因此平均延迟与节点数目成正比。(2)鲁棒性较差：由于传感器节点的易失效性，如果不采取适当的修复策略，单链结构的传输路径容易增大数据请求的失败率。

发明内容

为了克服现有的数据融合算法的不足，本发明提供一种应用于无线传感器网络的基于虚拟单元格的快速链式数据融合算法(CFDASC：an Chain-basedFast Data Aggregation algorithm based on a Suppositional Cell forwireless sensor networks)，解决无线传感器网络数据融合算法延迟的问题。

本发明解决其技术问题所采用的技术方案是：

本发明提出了一种基于虚拟单元格的快速链式数据融合算法。

一种基于虚拟单元格的快速链式数据融合算法，将整个传感区域划分为一个个的虚拟单元格，单元格内的节点都将数据发送给一个事先指定的节点进行融合，随后沿着单元格的垂直方向进行链式的数据融合过程，每条链每次只有一个节点将数据发送给Sink节点。为了均衡节点的能量消耗，节点之间都是轮流担当数据融合的角色。

本发明的一种应用于无线传感器网络的快速数据融合算法，包括如下两个步骤过程：

步骤一、网络初始化，在此阶段，形成虚拟单元格，每个虚拟单元格根据所处位置有一个标号，方便数据传输，同时每个虚拟单元格内(即一个簇内)的节点都要有一个簇内唯一的编号。

步骤二、数据收集、融合与传输，此步骤包括两个步骤，

步骤1)、一是虚拟单元格内部的数据收集、融合与传输，

步骤2)、一是虚拟单元格之间的，也包括与Sink节点之间的数据收集、融合与传输。

本发明是基于虚拟单元格的链式数据融合算法，利用节点的位置信息将节点归属于一个个的虚拟单元格中，单元格中的节点轮流充当单元格内数据融合的簇头；将一串单元格的数据进行融合后发送给汇聚节点，从而使数据融合过程加快，降低数据的传输时延，同时减少了数据传输量，节约了节点能量，进一步延长了网络的生命周期。

本发明的有益效果是，

1、数据的延时小：CFDASC算法中组成的数据传输链很短，因此数据传输时的时延很小。

2、算法的鲁棒性好：每条链都传送数据给Sink节点，不会像PEGASIS算法的单链结构，如果链失效，Sink节点将接收不到数据。

3、节能性较好：整个无线传感器网络区域内的所有数据最后被融合为几条链发送的数据，在数据传输过程中所传输的数据量大大减少，有效地节约了大部分的能量。

附图说明

图1无线传感器网络节点初始分布图；

图2节点成簇图；

图3数据传输图；

图4确定节点虚拟单元格内唯一编号的流程图；

图5虚拟单元格内部数据收集的流程图；

图6虚拟单元格之间链式数据融合的流程图；

图7CFDASC算法总的流程图。

下面结合附图和实施例对本发明进一步说明。

具体实施方式

首先给出采用CFDASC算法的传感器网络结构，图1给出了一个初始节点分布图示例，有100个节点随机分布在50m×50m的平面区域内，Sink节点位于75m处。图2是单元格内节点成簇的情况，如何选择簇头后面会介绍。图3给出了在分簇确定的情况下，数据是如何通过链式数据融合算法传输到Sink节点。步骤一、网络初始化：

在此阶段，形成虚拟单元格，每个虚拟单元格根据所处位置有一个标号，方便数据传输，同时每个虚拟单元格内(即一个簇内)的节点都要有一个簇内唯一的编号。如图1所示，每个虚拟单元格都可以用形式为G_ij的标号来标记，其中下标i，j分别表示虚拟单元格所对应的横纵坐标，用这样的标记方法，图1中最左边一列的五个单元格的标号分别为C₁₁、C₁₂、C₁₃、C₁₄和C₁₅。

虚拟单元格的边长应该由汇聚节点根据整个无线传感器网络的监测区域面积和应用所要求的延迟时间来综合决定。总的说来，为了达到快速融合的目的，虚拟单元格不宜过多。

虚拟单元格的边长确定下来后，由Sink节点向全网广播一个消息，该消息中包含有监测区域的矩形四个顶点的位置信息、虚拟单元格的边长信息和Sink节点的位置信息，节点收到这些信息后即可根据自己的位置信息迅速计算出自己所属的单元格。每个节点都记录Sink节点的位置信息以便于在数据传输过程中确定数据传输的方向以及成链的走向。

由图1中可以看到有一些节点恰好位于两个虚拟单元格的公共边上或是四个虚拟单元格的公共顶点处，此时这类节点的归属为永远加入离Sink节点更近的虚拟单元格中，这样做的好处是距离Sink节点更近，融合数据的传输更节约能量。

节点簇内唯一编号的确定方法为：在确定自己归属的虚拟单元格后，每个节点都广播自己的位置信息，每个节点都记录那些和自己处于同一个单元格内的节点的位置，经过一定的时间后，每个节点都清楚了自己所属单元格内的节点信息，每个虚拟单元格内的节点唯一编号是根据这个节点的位置信息自动获得的，可以有很多种方法。例如：坐标值最小的编号最小，x坐标优先级优于y坐标，即先看节点的x坐标值，最小的节点获得1号，当x坐标相同时，再参考节点的y坐标。

以虚拟单元格C_ij内节点(x_n，y_n)唯一编号n的确定过程为例来说明同一个虚拟单元格内的节点唯一编号是如何确定的。流程图如图4所示，假设虚拟单元格C_ij内的节点总数为k，其中1≤n≤k，则确定节点虚拟单元格内唯一编号的过程如下：

步骤1、节点(x_n，y_n)通过记录节点位置获知C_ij内节点总数为k，转入步骤2；

步骤2、将x_n与其他k-1个节点的x坐标进行比较，转入步骤3；

步骤3、通过比较，将其他k-1个节点分成三部分：第一部分节点的x坐标都小于x_n，节点个数为k₁；第二部分节点的x坐标都等于x_n，节点个数为k₂；第三部分节点的x坐标都大于x_n，节点个数为k-1-k₁-k₂；转入步骤4；

步骤4、判断k₂是否为0，若k₂等于0，转入步骤5；否则转入步骤6；

步骤5、得到节点(x_n，y_n)在虚拟单元格C_ij内唯一编号n为n＝k₁+1，算法结束。

步骤6、将y_n与这k₂个节点的y坐标进行比较，转入步骤7；

步骤7、判断y_n是否最小，若是最小，转入步骤5；若不是最小，转入步骤8；

步骤8、将这k₂个节点分成两部分：第一部分节点的y坐标都小于y_n，节点个数为k₃；第二部分节点的y坐标都大于y_n，节点个数为k₂-k₃；转入步骤9；

步骤9、得到节点(x_n，y_n)在虚拟单元格C_ij内唯一编号n为n＝k₁+k₃，算法结束。步骤二、数据收集、融合与传输：

数据收集、融合与传输包括两部分内容，一是虚拟单元格内部的数据收集、融合与传输过程，一是虚拟单元格之间的，也包括与Sink节点之间的数据收集、融合与传输过程。

1、虚拟单元格内部

每个虚拟单元格内每次有一个节点起数据收集、单元格内数据融合的作用，这个节点是单元格内轮换的，从编号为1的节点开始，依次进行。如图2所示。单元格内的这个簇头节点也有可能要执行接收其他单元格簇头节点的数据，并进行融合，转发给其他单元格的簇头节点或是直接发送给Sink节点。

以图示的方法来说明虚拟单元格C_ij中k(k≥1)个节点之间数据收集、融合及传输的过程，设这k个节点的编号为1，2，…n…，k-1，k。流程图如图5所示，虚拟单元格内部数据收集过程描述如下：

步骤1、网络初始化完成，转入步骤2；

步骤2、节点感知和采集数据，转入步骤3；

步骤3、编号为n的节点作为本格内的簇头节点，其他k-1个节点将感知的数据发送给节点n，节点n对接收的数据进行融合，虚拟单元格之间链式数据融合、传输过程，转入步骤4；

步骤4、判断n＝k是否成立，若成立，转入步骤5；否则转入步骤6；

步骤5、令n＝1，转入步骤2；

步骤6、令n的值增1，转入步骤2。

2、虚拟单元格之间，也包括与Sink节点之间

首先要考虑成链的方向。这个方向是和Sink节点的位置有关系的。如图3所示，每条链的一端都离Sink节点最近。

其次是每条链的数据如何传输到Sink节点，这里采用PEGASIS算法，即每次有一个单元格内的簇头节点作为整条链的首领，负责从链上的邻近单元格的簇头节点接收数据，并融合后发送给Sink节点。这个任务也是链上的所有单元格之间轮换完成的。

以链C_i1-C_im为例用图示来说明虚拟单元格之间数据收集、融合和传输的过程，假设该链共包含m个虚拟单元格，每个虚拟单元格在每次数据传输时的簇头统一用CH_i1-CH_im来表示，实际上每次传输数据时虚拟单元格簇头节点都是由单元格内节点轮流担当的。虚拟单元格之间链式数据融合流程如图6所示，虚拟单元格之间链式数据融合过程描述如下：

步骤1、网络初始化完成，虚拟单元格内部数据收集过程，转入步骤2；

步骤2、此轮中，虚拟单元格C_ij的簇头CH_ij作为链式数据融合的首领(1≤j≤m)，转入步骤3；

步骤3、CH_ij接收并融合CH_ij-1与CH_ij+1发送来的数据，若j＝1或j＝m，则只接收和融合一端单元格发送来的数据，CH_ij将融合后的数据传输给汇聚节点，转入步骤4；

步骤4、判断j＝m是否成立，若成立，转入步骤5；否则转入步骤6；

步骤5、令j＝1，转入步骤2；

步骤6、令j的值增1，转入步骤2。

综合上面两个步骤所述的内容，可以得到CFDASC算法总的流程图如图7所示，CFDASC算法过程的文字描述如下：

步骤1、网络初始化，在监测区域内布撒传感器节点，汇聚节点确定虚拟单元格的边长，然后向全网广播一个消息，转入步骤2；

步骤2、传感节点计算自己所属的单元格，并广播自己的位置信息，同时接收其他传感节点的信息，记录属于同一个单元格内的节点位置，转入步骤3；

步骤3、进行虚拟单元格内传感节点唯一编号确定过程，转入步骤4；

步骤4、进行虚拟单元格内部的数据收集过程，转入步骤5；

步骤5、进行虚拟单元格之间链式数据融合，融合后的数据发送给汇聚节点，转入步骤4。