基于事件优先级的蛇形时隙存储算法*

林志贵，安旭磊，刘英平，李 敏，杨子原

（1.天津工业大学电子与信息工程学院，天津300387；2.天津工业大学机械工程学院，天津300387；3.天津工业大学现代机电装备技术天津市重点实验室，天津300387；4.国家海洋技术中心近海海洋环境观测与监测技术研究室，天津300112）

基于事件优先级的蛇形时隙存储算法*

林志贵1*，安旭磊1，刘英平2，3，李 敏1，杨子原4

（1.天津工业大学电子与信息工程学院，天津300387；2.天津工业大学机械工程学院，天津300387；3.天津工业大学现代机电装备技术天津市重点实验室，天津300387；4.国家海洋技术中心近海海洋环境观测与监测技术研究室，天津300112）

针对WSN中的以数据为中心的平面型存储算法没有考虑在数据传输过程中节点的能量消耗问题，考虑到节点数据的重要程度，赋予相应的优先级，在蛇形时隙的节能存储算法（SLPS）基础上，提出基于事件优先级和动态散列位置的蛇形时隙算法（P-SLPS）。P-SLPS算法通过划分网格区域，将特定类型的数据存储在相应的网格中，通过定义事件优先级，将高优先级的事件存储在距离查询节点更近的网络区域，保证高优先级事件优先被搜索。根据监测节点和存储映射地址计算动态散列位置，将检测事件存储在同一优先级区域内离监测节点最近的存储网格。从网络生命周期和网络的节点存活数两方面进行仿真，结果表明P-SLPS算法在能量消耗方面低于SLPS算法，延长了无线传感网络的生命周期。

WSN；数据存储；事件优先级；事件类型

无线传感器网络中，大量节点采集数据，带来网络数据传输量巨大。对于某些应用领域，节点采集数据并非实时传输，这样可以将采集的数据保存在节点（又称存储节点）上，需要时可从网内存储节点获取数据［1-2］。然而，存储节点的选择，直接影响到查询数据效率，以及查询过程和数据传输过程中节点的能量消耗。因此，针对网络数据类型，选择合适的存储节点，设计能量有效的数据存储算法显得尤为重要。

以数据为中心的存储方法是依据数据的属性值（Key和Priority），通过某种映射方法存储到对应的节点上，使得每个节点只存储同一类型的数据，查询时通过对应的映射方法从相应的节点中获取数据［3］。该类算法提供了一种基于数据属性的信息中介机制，平衡数据存储和查询开销，可分为层次型存储算法和平面型存储算法。前者是对网络中节点进行层次划分，底层节点存储数据，高层节点存储元数据，如DIMENSIONS［4］、DIFS［5］等算法。层次型存储算法容易产生热点现象、索引维护比较困难等问题。后者是指网络中各个节点的地位相同，数据和索引信息均匀地存储在各个节点上，如Double Rul⁃ing［6］、Combs［7］、SCOOP［8］和GHT［9］算法。

Double Ruling算法［6，10］采用“存储转发”技术实现多点存储，数据按照一定的路径存储并转发，查询请求也按照一定的路径传播，但该算法要求网络是规则的。Combs算法［7］突破了对规则网络的要求，结合push策略与pull策略，构建梳针查询的策略，适合于平面结构的无线传感器网络进行全局查询。数据（或查询请求）传播时沿多跳路径传播，网络的能量消耗太大，影响网络生命周期。SCOOP算法［8，11］能够根据实际应用情况自适应的选择存储位置，提高了数据存储和查询的效率，只适用于小规模的传感器网络。

GHT算法［9，12］采用基于数据属性的命名，将数据属性集命名为事件，借助于P2P（Peer-to-Peer对等网络）系统的DHT（以数据为中心的散列表）思想，在节点监测到有事件发生时，将事件映射为网络中的存储位置（传感器节点），采用基于位置的路由协议GPSR将数据路由到映射位置最近的节点。GHT算法中，每类事件只有一个存储节点，会产生通信瓶颈和热点现象；通过散列函数得到的散列位置上可能不存在节点；没有考虑到数据存储和查询过程中的能量开销问题。

蛇形时隙的节能存储算法（SLPS）［13］基于GHT算法思想，将被监测区域按实际应用划分为网格，网格内所有节点的工作时隙以一种蛇形排列方式进行分配，各节点周期性地进入睡眠或侦听状态。在任一时隙，只有两个传感节点处于工作状态，其他节点都处于睡眠状态，既保证了系统的可靠性，又降低了能量消耗。该算法没有考虑在数据传输过程中节点的能量消耗。

针对上述问题，考虑到节点数据的重要程度，越重要的数据优先级越高，查询频率也会相应提高；在蛇形时隙节能算法的基础上，对事件划分优先级，本文提出基于事件优先级和动态散列位置的蛇形时隙算法（P-SLPS），通过缩短数据存储和查询时数据的传输路径，减少能量消耗，延长网络生命周期。

1 基于事件优先级和动态散列位置的蛇形时隙算法

P-SLPS算法通过划分网格区域，将特定类型的数据存储在相应的网格中，而不是存储在某个节点上；通过定义事件优先级，将高优先级的事件存储在距离查询节点更近的网络区域，保证高优先级事件最先被搜索到；根据监测节点和存储映射地址计算动态散列位置，将检测事件存储在同一优先级区域内离监测节点最近的存储网格。

1.1 网络划分

假设网络区域为一个L×L的正方形区域，节点均匀分布其中。假定无线传感器网络符合以下规则［14-15］：网络有很好的连通性；网络部署后，Sink节点和其他节点不再移动；网络的周界已知，节点的位置坐标已知；节点间的通信范围相同。另外，网络中事件的产生是随机的，每个事件都有事件类型，不同节点可以产生相同类型的事件和数据。

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

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

图1 事件存储网格划分

1.2 节点工作时隙的分配

以蛇形时隙节能思想，为网格中每个节点分配工作时隙。任一时隙间隙，每个网格中有且仅有两个节点同时处于侦听模式，其他节点都将进入睡眠模式。

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

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

节点工作时隙Tij分配如式（2）所示：

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

图2 4×3矩阵中节点工作时隙分配

从第一行第一列开始，自左向右分配连续的时隙，如遇矩阵边界则垂直换到下一行，并以相反的方向继续分配连续的时隙。如图2所示，第一行从左到右为时隙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的过程中始终处于工作状态，这种分配方式避免了时隙切换时的丢包现象，保证了网络运行的可靠性［13］。

1.3 存储节点的选择

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

图3 存储节点选择

1.4 事件存储

当节点B监测到事件后，经散列运算得到散列位置G，根据监测节点和散列位置坐标求得离监测节点距离最近的动态散列位置G0，采用地理位置路由（GPSR）算法可以将监测到的事件路由到离动态散列位置所在的网格区域。当数据送至动态散列位置所在网格区域时，采用区域泛洪方式将数据保存在处于侦听模式下的两个节点中，如图4所示。收到数据的节点根据ID编号给监测节点B回复一个ACK应答消息。如果监测节点等待一段时间后，没有收到ACK消息，则认为该数据已经丢失，重新向存储区域发送该数据。数据保存在两个节点中，增加了数据存储的可靠性。

图4 数据存储示意图

1.5 事件查询

当用户需要查询相关数据时，Sink节点将查询请求解析优化后，给n个扇形区域各自发送一份查询命令Query(Key,Priority)。当查询分组信息传送到要查询的事件类型对应的存储节点后，存储节点会检索自己保存的数据，看是否存在查询需要的数据，若存储节点存在查询请求所需的数据，则将数据发送给查询节点；如果存储节点不存在查询所需的数据，存储节点将转发收到的查询请求信息，如图5所示。

2 P-SLPS算法运行过程

P-SLPS算法的运行过程主要分为网络初始化和稳定运行两个阶段。初始化阶段的主要工作是：划分网格、分配节点工作时隙。每个节点在网格内通过广播一条消息来交换其在网格内的基本信息，建立一个用于存储同一网格内其他邻居节点的信息表Grid_Node，该表由节点所属的网格（GRID）、节点的坐标（LN）、节点能量（NE）和事件类型（ET）四个部分组成，并且每个节点能量相等。

稳定运行阶段为时间轮的循环，每轮中，当节点监测到有事件发生时，该节点会依据事件类型向存储节点发送一个Put packet数据包，根据监测事件的属性值和监测节点的位置信息选择相应的存储节点，事件发生时的数据存储以及根据用户需求进行的数据查询。Sink节点在检索相应的事件前，向存储节点发送一个Get packet数据查询包。

图5 数据查询示意图

3 仿真分析

为了验证P-SLPS算法，基于MATLAB仿真平台。从扇形区域数、事件数量以及事件集中出现等方面，比较分析P-SLPS、SLPS算法。网络生命周期采用网络中有50%的节点死去的时间。假设100个节点随机部署在边长为200 m的正方形区域内，以Sink节点为顶点，以90/6为夹角，将网络区域划分为n（可变）个扇形区域。在各个优先级事件均匀分布的前提下，比较n从1到8时，P-SLPS算法网络生命周期的情况，如图6所示。由图6可知，当n=6时P-SLPS算法网络生命周期最长，取最优划分个数时，有效地降低系统开销。实验选取最佳扇形区域数（n）为6，再将区域按周向间距为50 m划分，构成网格区域。约定一个时隙为1 s。假设查询频率为10次/s，网络中查询节点位于坐标（0，0）；网格中只有三种属性的事件随机出现在网格中，优先级分别为1、2、3。

图6 扇形区域数对P-SLPS算法网络生命周期的影响

在各个优先级事件随机分布在监测区域内，SLPS和P-SLPS存储算法的网络生命周期情况如图7所示。网络运行的初始阶段，两种算法中网内剩余节点数相同，并且在300 s时都出现死亡节点，随着网络的运行，死亡节点数增加，SLPS算法比P-SLPS算法中节点死亡速度快。SLPS算法在1 800 s时网内剩余节点数量为50个，而P-SLPS算法中的剩余节点数量为73个。P-SLPS算法采用优先级的存储策略降低了网内节点的能量消耗。

图7 SLPS和P-SLPS网络生命周期比较

如图8所示，当单位时间内查询事件数目由10增加到40时，P-SLPS算法和SLPS算法相比，网络生命周期下降的速度较慢；当事件查询频率越高时，网络生命周期差异越大。事件按优先级高低存储在离汇聚节点由近及远的网格内，有效的减少了数据查询过程中的节点的能量消耗，从而延长网络生命周期。

图8 查询事件数量对网络生命周期的影响

如图9所示，当单位时间内监测事件由10增加到40时，两种策略下的网络生命周期整体趋势都是下降的，但基于动态散列位置的存储策略下降比较快。对比图8和图9可以看出，受事件存储的影响，监测相比查询对网络生命周期的影响更明显，因为查询时查询节点首先要向存储节点发送查询包，相比监测事件传输过程中的能量消耗，查询包传输过程中的能量消耗较少。

当单位时间内的监测事件由10增加到40时，假定优先级为2的事件集中出现在监测网中某一区域，事件分布对P-SLPS算法性能的影响，如图10所示。从图10看出，当存储事件频率相同，监测事件均匀分布比事件集中出现时的网络生命周期要长，并且当事件存储频率越大，事件集中出现对网络生命周期的影响也越大。优先级为2的事件集中出现，使该区域内优先级为2的事件对应的存储节点集中存储事件，产生存储热点现象，导致存储节点过早死亡，从而影响整个网络的生命周期。

图9 监测事件数量对网络生命周期的影响

图10 事件集中出现对网络生命周期的影响

4 结论

分析以数据为中心的平面型存储算法基础上，根据事件优先级，结合动态散列位置，本文提出基于事件优先级和动态散列位置的蛇形时隙存储算法（P-SLPS），目的是为减少数据传输过程中产生的能量消耗。该策略采用蛇形时隙控制同一网格中只有两个节点来侦听数据，以节省节点空闲侦听带来的能量消耗。在此基础上设计事件散列函数，根据事件的优先级从高到低将事件存储于离查询节点由近及远的网格内，将散列位置旋转至与监测节点最近的网格内，以减少数据存储和数据查询过程中节点的能量消耗。

P-SLPS算法的运行过程主要分为网络初始化和稳定运行两个阶段。初始化阶段的主要工作是：划分网格、节点工作时隙的分配。稳定运行阶段为时间轮的循环。基于MATLAB仿真平台，从扇形区域数、事件数量以及事件集中出现等方面，比较分析P-SLPS、SLPS算法。仿真结果表明，相比SLPS算法，P-SLPS算法节省能量，延长了无线传感网络的生命周期。

［1］谢志军，唐建华，杨婧，金光.无线传感器网络中基于连通核的高效Skyline查询算法［J］.传感技术学报，2013，26（10）：1437-1445.

［2］陈颖文，徐明，吴一.无线传感器网络网内数据处理节点的优化选取［J］.软件学报，2007，18（12）：3104-3114.

［3］惠晓威，刘彦每.WSN数据收集中移动Sink的路径规划和簇头节点选取问题的综合研究［J］.传感技术学报，2014，27（1）：118-122.

［4］Deepak GANESAN，Deborah Estrin.DIMENSIONS：Why do We Need A New Data Handing Architecture for Sensor Networks［J］.ACM SIGCOMM Computer Communication Review，2003，33（1）：143-148.

［5］Benjamin Greenstein，Deborah Estrin，Ramesh Govindan，et al.DIFS：A Distribnuted Index for Features in Sensor Network［J］.Ad Hoc Networks，2003，1（2-3）：333-349.

［6］Sarkar Rik，Zhu Xianjin，Gao Jie.Double Rulings for Information Brokerage in Sensor Networks［J］.ACM Transactions on Network⁃ing，2009，17（6）：1902-1915.

［7］LiuXin，Huang Qingfeng，Zhang Ying.Balancing Push and Pull for Efficient Information Discovery in Large-Scale Sensor Net⁃works［J］.IEEE Transactions on Mobile Computing，2007，6（3）：241-251.

［8］Gil Thomer M，Madden Samuel.Scoop：An Adaptive Indexing Scheme for Stored Data in Sensor Networks［C］//23rd Internation⁃al Conference on Data Engineering，ICDE 2007，Istanbul，Turkey，April 15-20，2007：89-102.

［9］Sylvia Ratuasamy，Brad Karp，Seott Shenker.Data-centric Stor⁃age in Sensor Nets with GHT，A Geographic Hash Table［J］.Mo⁃ bile Networks and Applications，2003，8（4）：427-442.

［10］Wang Zhu，Lü Cuicui，Shao Xianhe.An Improved Relay Node Layout Approach in Wireless Sensor Networks［J］.Journal of Computational Information Systems，2013，9（23）：9381-9388.

［11］Gonçalves Nuno M F，Dos Santos Aldri L，Hara CarmemS.A poli⁃cy-Based Storage Model for Sensor Networks［C］//IEEE/IFIP Net⁃work Operations and Management Symposium：Management in a Software Defined World，NOMS 2014.May 5，2014-May 9，2014，Krakow，Poland，1-8.

［12］Cheng Shyi-Chyi，Cheng Kwang-Yu，Chen Yi-Ping Phoebe.GHT-based Associative Memory Learning and its Application to Human Action Detection and Classification［J］.Pattern Recognition，2013，46（11）：3117-3128.

［13］Liao Wen-Hwa，Yang Hung-Chun.A Power-Saving Data Storage Scheme for Wireless Sensor Networks［J］.Journal of Network and Computer Applications，2012，35（2）：818-825.

［14］韩鸿泉，朱红松，孟军.无线传感器网络技术［J］.计算机系统应用，2005，14（2）：38-41.

［15］Elsa Macias，Alvaro Suarez and Jaime Lloret.Mobile Sensing Sys⁃tems［J］.Sensors，2013，13（12）：17292-17321

［16］Brad Karp，Scott Shenker，Deborah Estrin.Data-Centric Storage in Sensornets with GHT，a Geographic Hash Table［J］.Mobile Networks and Applications，2003，8（4）：427-442.

林志贵（1974-），男，汉族，博士，副教授，硕士生导师，主要研究方向为无线传感器网络、智能信息处理等，linzhigui@tjpu.edu.cn；

安旭磊（1990-），男，河北保定人，硕士研究生，主要研究方向为体域网、智能信息处理等。

A Snake-Like Power-Saving Algorithm Based on Event Priority in WSNs*

LIN Zhigui1*，AN Xulei1，LIU Yingping2，3，LI Min1，YANGZiyuan4
（1.School of Electronics and Information Engineering，Tianjin Polytechnic University，Tianjin 300387，China；2.School of Mechanical Engineering，Tianjin Polytechnic University，Tianjin 300387，China；3.Tianjin City Key Lab of Modem Mechatronics Equipment Technology，Tianjin Polytechnic University，Tianjin 300387，China；4.Laboratory of marine environment observation and monitoring technology of offshore，National Ocean Technology Center，Tianjin 300112，China）

Against the data-centric planar storage algorithm in wireless sensor network（WSN）does not consider the node energy consumption in the process of data transmission，considering the importance of node data，this paper gives the corresponding data priority，and on the basis of snake-like power-saving algorithm，and proposes a snakelike power-saving（P-SLPS）algorithm which bases on event priority and dynamic hashing position.The P-SLPS algo⁃rithm could store the specific type of data in corresponding grid by the mesh area and store the high-priority event in the network area where near the query node to ensure the high-priority events can be searched.According to the monitor node and storage mapping position calculating dynamic hash mapping address，to store the monitor event in a storage grid which near the monitor node in the same priority area.From the network life cycle and the number of data survival to simulate，and the simulation result shows that in comprison with the SLPS algorithm，the P-SLPS al⁃gorithm reduces energy consumption and prolong the life cycle of wireless sensor networks.

wireless sensor network；data storage；event priority；event type

TP393

A

1004-1699(2015)10-1531-06

��7230

10.3969/j.issn.1004-1699.2015.10.020

项目来源：国家自然科学基金项目（61372011）

2015-05-25 修改日期：2015-06-26