一种无线传感数据存储方法

摘要

本发明是在以数据为中心的存储算法基础上，根据存储阈值，事件优先级，提出一种无线传感数据存储方法。目的是为解决当事件分布不均匀时，某些节点存储数据过多，采用以数据为中心的存储算法出现热点现象。该方法设计事件散列函数，根据事件的优先级将事件存储于离查询节点由近及远的网格内，将散列位置旋转至与监测节点最近的网格内，减少数据存储和查询过程中节点的能量消耗；定义节点存储阈值，对于达到存储阈值的节点，改变其坐标，不再参与下一轮时隙分配；当网格内节点都达到存储阈值，则将数据存储于同一优先级级别的邻居网格内；当同一优先级的所有网格内的所有节点都达到某一存储阈值，重新开始工作时隙的分配。

权利要求

1.一种无线传感数据存储方法，其特征在于：通过定义事件优先级以及设定节点存储阈值，将高优先级的事件存储在距离查询节点更近的网络区域，保证高优先级事件最先被搜索；该方法实施步骤包括：步骤一、网络划分：通过划分网格区域，将特定类型的数据存储在相应的网格中，不是存储在某个节点上；通过定义事件优先级以及设定节点存储阈值，将高优先级的事件存储在距离查询节点更近的网络区域，保证高优先级事件最先被搜索；

步骤二、节点工作时隙的分配：计算每个网格内的节点个数，以及各个节点到网格中心点的距离，按距离从小到大为节点编号(A、B、C...N)，用一个m行n列的矩阵T为网格内的每个节点分配侦听或睡眠时隙；

步骤三、存储节点的选择：根据监测节点和存储映射地址计算动态散列位置，结合节点剩余存储空间，将检测事件存储在同一优先级区域内离监测节点近且剩余存储空间大的存储网格；为每个节点设定存储阈值，每一轮工作时隙结束后，检测网格内各个节点的存储容量；若某个节点存储容量超过阈值，将该节点虚拟坐标设为(∞，∞)，同时告知网格内其他节点自身存储达到存储阈值，网格内其他节点改变该节点的相关信息；下一轮根据各节点距离网格重心的距离为各个节点分配工作时隙时，该节点不再参与节点工作时隙的分配；

其余节点分配工作时隙后重新开始新一轮的工作；

步骤四、基于距离的存储阈值策略：假定网络中每个节点同构且有一个Grid_Node表，并为其设定多个存储阈值及存储阈值等级TL；当存储节点的数据达到预定义的阈值，其虚拟坐标LV改为无穷大(∞，∞)，表示远离当前事件的散列位置，用虚拟坐标LV覆盖节点的原始坐标；同时该节点向网格内其他节点发送Storage_Full包，告诉其他节点自身存储达到某一阈值；网格内收到Storage_Full包的节点，根据包中的ID改变其Grid_Node表中节点的LV值；当下一次检测到事件，计算节点到散列位置的距离时，达到存储阈值的节点用LV计算，此时该节点是网格内距离散列位置最远的节点，数据不会存储到该节点，转而选择存储到本次计算到离散列位置最近的其他节点；当网格中所有节点都达到同一存储阈值但未达到最大阈值时，最后一个达到阈值的节点向网格内其他节点发送Change_Threshold包，使TL＝TL+1且所有邻居节点的虚拟坐标改为实际坐标，收到Change_Threshold包的节点改变其存储阈值和Grid_Node表中的相关参数值；改变后离散列位置最近的节点重新成为存储节点，直至网格中的所有节点达到最高存储阈值水平。

说明书

一种无线传感数据存储方法

技术领域

[0001] 本发明涉及的是无线传感监测网中的一种数据存储方法。可应用于无线传感网络数据存储领域。

背景技术

[0002] 无线传感监测网中，对监测数据实时性要求不高，为节省能量，节点将监测数据暂存，需要时再将数据传输，称该节点为存储节点。存储节点的选择，直接影响到查询数据效率，以及查询过程和数据传输过程中节点的能量消耗。一些学者提出以数据为中心的存储方法，该方法是依据数据的属性值，通过某种映射方法存储到对应的节点上，使得每个节点只存储同一类型的数据，查询时可通过对应的映射方法从相应的节点中获取数据；如Double Ruling、Combs、SCOOP和GHT方法，这些方法中网络各个节点的地位相同，数据和索引信息均匀地存储在各个节点上。GHT方法中，每类事件只有一个存储节点，会产生通信瓶颈和热点现象；通过散列函数得到的散列位置上可能不存在节点；没有考虑到数据存储和查询过程中的能量开销。

[0003] 蛇形时隙的节能存储方法基于GHT方法思想，将被监测区域按实际应用划分为网格，网格内所有无线传感器节点的工作时隙以一种蛇形排列方式进行分配，使各节点周期性地进入睡眠或侦听状态。在任一时隙，只有两个传感节点处于工作状态，其他节点都处于睡眠状态，保证了系统的可靠性，又降低了能量消耗。该方法没有考虑在数据传输过程中节点的能量消耗。文献考虑到节点数据的重要程度，越重要的数据优先级越高，查询频率也会相应提高；在蛇形时隙的节能存储方法的基础上，对事件划分优先级，提出基于事件优先级和动态散列位置的蛇形时隙方法，通过缩短数据存储和查询时数据的传输路径，减少能量消耗。

[0004] 当网络中的事件分布不均匀时，某些节点存储数据过多，基于事件优先级和动态散列位置的蛇形时隙方法会使网络出现热点现象。超过节点的存储空间而引起数据丢失，网络能够查询的数据和信息减少，热点区域的节点能量消耗过快甚至耗尽死亡，缩短网络的生命周期。

发明内容

[0005] 为解决存储节点热点现象，实现网络中节点的负载平衡，本文引入多阈值(multi-threshold)的存储思想，基于事件优先级和动态散列位置的蛇形时隙方法，提出无线传感数据存储方法。无线传感数据存储方法根据节点剩余存储空间选择网格内的工作节点，有效的改善节点能量分布不均的问题，延长网络生命周期。无线传感数据存储方法通过划分网格区域，将特定类型的数据存储在相应的网格中，不是存储在某个节点上；通过定义事件优先级以及设定节点存储阈值，将高优先级的事件存储在距离查询节点更近的网络区域，保证高优先级事件最先被搜索；根据监测节点和存储映射地址计算动态散列位置，结合节点剩余存储空间，将检测事件存储在同一优先级区域内离监测节点近且剩余存储空间大的存储网格。若某个节点存储容量超过阈值，将告知网格内其他节点自身存储达到存储阈值，该节点不再参与节点工作时隙的分配，避免存储热点现象发生。无线传感数据存储方法具体如下：

[0006] 1.网络划分：假设网络区域为一个L*L的正方形区域，节点均匀分布，每个节点分别有实际坐标LR和虚拟坐标LV，令其初始值LV＝LR，且无线传感器网络符合以下规则：网络有很好的连通性，即节点密度足够大；网络部署后，Sink节点和其它节点不再移动；网络的周界已知，节点可以获得自己的位置坐标；节点间的通信范围相同。另外，网络中事件的产生是随机的，每个事件都有事件类型，不同节点可以产生相同类型的事件和数据。

[0007] 令Sink节点坐标为(0，0)，监测事件有K类，以[L/(K+1)]*i(i＝1、2、3...K)为半径，(0，0)为顶点，画圆构成K个圆环区域，分别存储K类事件，如图1所示。每类事件赋予一种优先级，其值由事件按查询频率确定。优先级值越小，事件优先级越高，事件存储区域距离Sink节点越近。如优先级为1的事件存储在离Sink节点最近的圆环区域内。

[0008] 为了使存储节点距离监测节点更近，提出动态散列位置的概念。首先以Sink节点为顶点，90/n为夹角，将网络区域划分为a、b、c、d...n区。将存储区域划分为网格，如图2所示。

[0009] 2.节点工作时隙的分配：首先，计算每个网格内的节点个数，以及各个节点到网格中心点的距离，按距离从小到大为节点编号(A、B、C...N)，用一个m行n列的矩阵T为网格内的每个节点分配侦听或睡眠时隙。矩阵T中的元素Tij表示节点工作时隙。为保证每个节点睡眠和侦听周期公平，m和n的值尽量接近。矩阵T的行m和列n与网格内节点数量N的关系如公式(1)所示：

[0010]

[0011] 公式(1)中，若N为偶数，满足m＝n＝N/2；若N为奇数，规定矩阵行数m为N/2向上取整，列数n＝N-m，m+n个节点对应m×n个工作时隙。

[0012] 节点工作时隙Tij分配如公式(2)所示：

[0013]

[0014] 假设网格内有7个节点(A、B、C、D、E、F、G)，则N＝7，由公式(1)计算得m＝4，n＝3。根据公式(2)带入i，j值，构建矩阵T如图3所示。

[0015] 从第一行第一列开始，自左向右分配连续的时隙，如遇矩阵边界则垂直换到下一行，并以相反的方向在该行继续分配连续的时隙。如图3所示，第一行从左到右为时隙1、2、3，第二行从右到左为时隙4、5、6，以此类推。每个节点被映射到i行或j列，保证每个时隙内有两个节点处于活动状态。矩阵T中，节点对应行或列中的元素表示节点的工作时隙。节点A的活动时隙为1、2、3，其余时隙处于睡眠状态。节点E的活动时隙为1、6、7和12。采用蛇形时序分配方式，在时隙切换时始终保证有节点处于连续工作状态，如时隙1中节点A、E处于工作状态，当时隙1切换到时隙2时，节点E进入休眠状态，节点F从休眠状态进入工作状态，而节点A在时隙1切换到时隙2的过程中始终处于工作状态，这种分配方式避免了时隙切换时的丢包现象，保证了网络运行的可靠性。

[0016] 3.存储节点的选择：如图4所示，监测节点B(Xb，Yb)监测到事件优先级为K-1的数据，对应存储点应在第K-1层环内。利用散列表映射到散列位置G(Xg，Yg)，节点B在区域b中，散列位置G在区域c中，利用监测节点和散列位置坐标计算动态散列位置G0(Xg0，Yg0)，其中散列位置G和动态散列位置G0位于同一半径圆弧上，监测节点B和动态散列位置G0位于同一半径轴线上。选择动态散列位置G0所在网格内的工作节点作为事件存储节点，其坐标由公式(3)和公式(4)求得。

[0017]

[0018]

[0019] 考虑到同一时隙监测到的某一类型的事件数量不一样造成各节点存储容量的差异，为每个节点设定存储阈值，每一轮工作时隙结束后，检测网格内各个节点的存储容量。若某个节点存储容量超过阈值，将该节点虚拟坐标设为(∞，∞)，同时告知网格内其他节点自身存储达到存储阈值，网格内其他节点改变该节点的相关信息。下一轮根据各节点距离网格重心的距离为各个节点分配工作时隙时，该节点不再参与节点工作时隙的分配；其余节点分配工作时隙后重新开始新一轮的工作，以此类推。

[0020] 4.基于距离的存储阈值策略：假定网络中每个节点同构且有一个Grid_Node表(用来存储网格内其他节点信息的数据信息表)，并为其设定多个存储阈值及存储阈值等级TL。当存储节点的数据达到预定义的阈值，其虚拟坐标LV改为无穷大(∞，∞)，表示远离当前事件的散列位置，用虚拟坐标LV覆盖节点的原始坐标；同时该节点向网格内其他节点发送Storage_Full包，告诉其他节点自身存储达到某一阈值。网格内收到Storage_Full包的节点，根据包中的ID改变其Grid_Node表中节点的LV值。当下一次检测到事件，计算节点到散列位置的距离时，达到存储阈值的节点用LV计算，此时该节点是网格内距离散列位置最远的节点，数据不会存储到该节点，转而选择存储到本次计算到离散列位置最近的其他节点。
当网格中所有节点都达到同一存储阈值但未达到最大阈值时，最后一个达到阈值的节点向网格内其他节点发送Change_Threshold包，使TL＝TL+1且所有邻居节点的虚拟坐标改为实际坐标，收到Change_Threshold包的节点改变其存储阈值和Grid_Node表中的相关参数值。
改变后离散列位置最近的节点重新成为存储节点，直至网格中的所有节点达到最高存储阈值水平。

[0021] 如图6所示为多阈值虚拟坐标的方案，假定节点存储阈值有100和200两个等级，监测事件对应的散列位置坐标为(23，17)，散列位置所在网格内有三个存储节点A、B、C。经计算节点B为距离散列位置最近的节点。若节点B存储了99个数据，随后即将收到一个数据，达到第一个阈值100，则节点B在收到第100个数据后将虚拟坐标改为(∞，∞)，远离散列位置。基于地理位置的路由忽略节点B，新的数据到来时将数据传送到节点A，如果节点A也达到第一个存储阈值100，其虚拟坐标也改为远离散列位置的(∞，∞)，节点C将变为新的存储节点，如图5(a)所示。当节点A、B、C都达到存储阈值100时，网格内所有节点恢复实际坐标，且存储阈值都变为200，如图5(b)所示，重新按照节点实际坐标离散列位置的距离选择存储节点。

[0022] 对于同一类型的事件集中出现在网内某一区域，使得对应存储区域内节点存储频繁，导致节点能量消耗过快并出现数据溢出的现象。当网格内节点都达到存储阈值TL，最后一个达到存储阈值的节点向同一优先级事件的存储网格发送存储网格扩展包，接收到扩展包的节点判断自身所处网格优先级与发来数据包网格优先级是否相同，若相同则存储数据，不相同则转发网格扩展包。当同一优先级网格内的所有节点都达到存储阈值，达到存储阈值的最后一个节点向同等优先级网格发送Storage_Full包，该网格内的节点接收到邻居网格发来的Storage_Full包，改变节点存储阈值TL＝TL+1。网格内所有节点将其坐标改为原始坐标，各个网格按照原始坐标重新为节点分配工作时隙。

附图说明

[0023] 图1 优先级区域划分

[0024] 图2 事件存储网格划分

[0025] 图3 4×3矩阵中节点工作时隙分配

[0026] 图4 存储节点选择

[0027] 图5 存储阈值方案示意图

[0028] 图6 无线传感数据存储方法的运行过程

[0029] 图7 节点剩余能量均匀度比较

[0030] 图8 无线传感数据存储方法和基于事件优先级和动态散列位置的蛇形时隙方法网络生命周期比较

具体实施方式

[0031] 采用Matlab平台，对本发明进行实施，具体流程如下：

[0032] (1)网络划分：假设100个节点随机部署在边长为200m的正方形区域内，以Sink节点为顶点，以90/6为夹角，将网络分为6个区域，再将区域按周向间距为50m划分，构成网格区域。规定一个时隙为1s，假设事件产生频率为10次/s，网络中汇聚节点位于坐标(0，0)，只有两种属性的事件随机出现在网格中，优先级分为1、2、3，节点存储阈值分为10和20。为验证MT-PSLPS优化事件出现集中性带来的存储热点现象，假定优先级为2的事件集中出现在坐标为(150，150)的网络区域附近。

[0033] (2)节点工作时隙的分配：依据公式(1)可由网格内的节点个数计算出矩阵T的行数m和列数n。且可由公式(2)计算出矩阵T中的元素Tij(节点工作时隙)。本发明中的节点工作时隙为1s。

[0034] (3)存储节点的选择：首先判断监测节点所监测到的是哪个事件优先级上的数据，再利用散列表映射到散列位置G，然后，利用监测节点和散列位置坐标计算动态散列位置G0，最后，选择动态散列位置G0所在网格内的工作节点作为事件存储节点，其坐标由公式(3)和公式(4)求得。

[0035] (4)基于距离的存储阈值策略：如图5所示为多阈值虚拟坐标的方案，假定节点存储阈值有100和200两个等级，监测事件对应的散列位置坐标为(23，17)，散列位置所在网格内有三个存储节点A、B、C。经计算节点B为距离散列位置最近的节点。若节点B存储了99个数据，随后即将收到一个数据，达到第一个阈值100，则节点B在收到第100个数据后将虚拟坐标改为(∞，∞)，远离散列位置。基于地理位置的路由忽略节点B，新的数据到来时将数据传送到节点A，如果节点A也达到第一个存储阈值100，其虚拟坐标也改为远离散列位置的(∞，∞)，节点C将变为新的存储节点，如图5(a)所示。当节点A、B、C都达到存储阈值100时，网格内所有节点恢复实际坐标，且存储阈值都变为200，如图5(b)所示，重新按照节点实际坐标离散列位置的距离选择存储节点。

[0036] (5)节点剩余能量均匀度的比较：无线传感数据存储方法和基于事件优先级和动态散列位置的蛇形时隙方法的节点剩余能量的方差如图7所示。两种方法中节点剩余能量的方差依次增大，基于无线传感数据存储方法的节点剩余能量方差整体比基于事件优先级和动态散列位置的蛇形时隙方法小，表示无线传感数据存储方法使网络节点的能量分布比基于事件优先级和动态散列位置的蛇形时隙方法均衡。由方差的计算公式可知，当网络开始出现失效节点时，全网节点剩余能量的方差将随着死亡节点数的增加而增大，无线传感数据存储方法在网络运行过程中能更好地均衡各个节点的能量水平，提高整个网络的能量利用率，延长网络寿命。

[0037] (6)网络生命周期的比较：无线传感数据存储方法和基于事件优先级和动态散列位置的蛇形时隙方法对网络生命周期的影响如图8所示。网络运行开始时，两种方法节点死亡数差别不大，但随着网络的运行基于事件优先级和动态散列位置的蛇形时隙方法节点死亡率比无线传感数据存储方法快，无线传感数据存储方法考虑存储节点贡献能力，采用存储阈值，有效地减少了节点能量消耗。