基于事件優先級的蛇形時隙存儲算法*

林志貴，安旭磊，劉英平，李 敏，楊子原

（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