基于事件優(yōu)先級(jí)的蛇形時(shí)隙存儲(chǔ)算法*

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

（1.天津工業(yè)大學(xué)電子與信息工程學(xué)院，天津300387；2.天津工業(yè)大學(xué)機(jī)械工程學(xué)院，天津300387；3.天津工業(yè)大學(xué)現(xiàn)代機(jī)電裝備技術(shù)天津市重點(diǎn)實(shí)驗(yàn)室，天津300387；4.國(guó)家海洋技術(shù)中心近海海洋環(huán)境觀測(cè)與監(jiān)測(cè)技術(shù)研究室，天津300112）

基于事件優(yōu)先級(jí)的蛇形時(shí)隙存儲(chǔ)算法*

林志貴1*，安旭磊1，劉英平2，3，李 敏1，楊子原4

（1.天津工業(yè)大學(xué)電子與信息工程學(xué)院，天津300387；2.天津工業(yè)大學(xué)機(jī)械工程學(xué)院，天津300387；3.天津工業(yè)大學(xué)現(xiàn)代機(jī)電裝備技術(shù)天津市重點(diǎn)實(shí)驗(yàn)室，天津300387；4.國(guó)家海洋技術(shù)中心近海海洋環(huán)境觀測(cè)與監(jiān)測(cè)技術(shù)研究室，天津300112）

針對(duì)WSN中的以數(shù)據(jù)為中心的平面型存儲(chǔ)算法沒(méi)有考慮在數(shù)據(jù)傳輸過(guò)程中節(jié)點(diǎn)的能量消耗問(wèn)題，考慮到節(jié)點(diǎn)數(shù)據(jù)的重要程度，賦予相應(yīng)的優(yōu)先級(jí)，在蛇形時(shí)隙的節(jié)能存儲(chǔ)算法（SLPS）基礎(chǔ)上，提出基于事件優(yōu)先級(jí)和動(dòng)態(tài)散列位置的蛇形時(shí)隙算法（P-SLPS）。P-SLPS算法通過(guò)劃分網(wǎng)格區(qū)域，將特定類(lèi)型的數(shù)據(jù)存儲(chǔ)在相應(yīng)的網(wǎng)格中，通過(guò)定義事件優(yōu)先級(jí)，將高優(yōu)先級(jí)的事件存儲(chǔ)在距離查詢(xún)節(jié)點(diǎn)更近的網(wǎng)絡(luò)區(qū)域，保證高優(yōu)先級(jí)事件優(yōu)先被搜索。根據(jù)監(jiān)測(cè)節(jié)點(diǎn)和存儲(chǔ)映射地址計(jì)算動(dòng)態(tài)散列位置，將檢測(cè)事件存儲(chǔ)在同一優(yōu)先級(jí)區(qū)域內(nèi)離監(jiān)測(cè)節(jié)點(diǎn)最近的存儲(chǔ)網(wǎng)格。從網(wǎng)絡(luò)生命周期和網(wǎng)絡(luò)的節(jié)點(diǎn)存活數(shù)兩方面進(jìn)行仿真，結(jié)果表明P-SLPS算法在能量消耗方面低于SLPS算法，延長(zhǎng)了無(wú)線傳感網(wǎng)絡(luò)的生命周期。

WSN；數(shù)據(jù)存儲(chǔ)；事件優(yōu)先級(jí)；事件類(lèi)型

無(wú)線傳感器網(wǎng)絡(luò)中，大量節(jié)點(diǎn)采集數(shù)據(jù)，帶來(lái)網(wǎng)絡(luò)數(shù)據(jù)傳輸量巨大。對(duì)于某些應(yīng)用領(lǐng)域，節(jié)點(diǎn)采集數(shù)據(jù)并非實(shí)時(shí)傳輸，這樣可以將采集的數(shù)據(jù)保存在節(jié)點(diǎn)（又稱(chēng)存儲(chǔ)節(jié)點(diǎn)）上，需要時(shí)可從網(wǎng)內(nèi)存儲(chǔ)節(jié)點(diǎn)獲取數(shù)據(jù)［1-2］。然而，存儲(chǔ)節(jié)點(diǎn)的選擇，直接影響到查詢(xún)數(shù)據(jù)效率，以及查詢(xún)過(guò)程和數(shù)據(jù)傳輸過(guò)程中節(jié)點(diǎn)的能量消耗。因此，針對(duì)網(wǎng)絡(luò)數(shù)據(jù)類(lèi)型，選擇合適的存儲(chǔ)節(jié)點(diǎn)，設(shè)計(jì)能量有效的數(shù)據(jù)存儲(chǔ)算法顯得尤為重要。

以數(shù)據(jù)為中心的存儲(chǔ)方法是依據(jù)數(shù)據(jù)的屬性值（Key和Priority），通過(guò)某種映射方法存儲(chǔ)到對(duì)應(yīng)的節(jié)點(diǎn)上，使得每個(gè)節(jié)點(diǎn)只存儲(chǔ)同一類(lèi)型的數(shù)據(jù)，查詢(xún)時(shí)通過(guò)對(duì)應(yīng)的映射方法從相應(yīng)的節(jié)點(diǎn)中獲取數(shù)據(jù)［3］。該類(lèi)算法提供了一種基于數(shù)據(jù)屬性的信息中介機(jī)制，平衡數(shù)據(jù)存儲(chǔ)和查詢(xún)開(kāi)銷(xiāo)，可分為層次型存儲(chǔ)算法和平面型存儲(chǔ)算法。前者是對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)進(jìn)行層次劃分，底層節(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)，高層節(jié)點(diǎn)存儲(chǔ)元數(shù)據(jù)，如DIMENSIONS［4］、DIFS［5］等算法。層次型存儲(chǔ)算法容易產(chǎn)生熱點(diǎn)現(xiàn)象、索引維護(hù)比較困難等問(wèn)題。后者是指網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)的地位相同，數(shù)據(jù)和索引信息均勻地存儲(chǔ)在各個(gè)節(jié)點(diǎn)上，如Double Rul?ing［6］、Combs［7］、SCOOP［8］和GHT［9］算法。

Double Ruling算法［6，10］采用“存儲(chǔ)轉(zhuǎn)發(fā)”技術(shù)實(shí)現(xiàn)多點(diǎn)存儲(chǔ)，數(shù)據(jù)按照一定的路徑存儲(chǔ)并轉(zhuǎn)發(fā)，查詢(xún)請(qǐng)求也按照一定的路徑傳播，但該算法要求網(wǎng)絡(luò)是規(guī)則的。Combs算法［7］突破了對(duì)規(guī)則網(wǎng)絡(luò)的要求，結(jié)合push策略與pull策略，構(gòu)建梳針查詢(xún)的策略，適合于平面結(jié)構(gòu)的無(wú)線傳感器網(wǎng)絡(luò)進(jìn)行全局查詢(xún)。數(shù)據(jù)（或查詢(xún)請(qǐng)求）傳播時(shí)沿多跳路徑傳播，網(wǎng)絡(luò)的能量消耗太大，影響網(wǎng)絡(luò)生命周期。SCOOP算法［8，11］能夠根據(jù)實(shí)際應(yīng)用情況自適應(yīng)的選擇存儲(chǔ)位置，提高了數(shù)據(jù)存儲(chǔ)和查詢(xún)的效率，只適用于小規(guī)模的傳感器網(wǎng)絡(luò)。

GHT算法［9，12］采用基于數(shù)據(jù)屬性的命名，將數(shù)據(jù)屬性集命名為事件，借助于P2P（Peer-to-Peer對(duì)等網(wǎng)絡(luò)）系統(tǒng)的DHT（以數(shù)據(jù)為中心的散列表）思想，在節(jié)點(diǎn)監(jiān)測(cè)到有事件發(fā)生時(shí)，將事件映射為網(wǎng)絡(luò)中的存儲(chǔ)位置（傳感器節(jié)點(diǎn)），采用基于位置的路由協(xié)議GPSR將數(shù)據(jù)路由到映射位置最近的節(jié)點(diǎn)。GHT算法中，每類(lèi)事件只有一個(gè)存儲(chǔ)節(jié)點(diǎn)，會(huì)產(chǎn)生通信瓶頸和熱點(diǎn)現(xiàn)象；通過(guò)散列函數(shù)得到的散列位置上可能不存在節(jié)點(diǎn)；沒(méi)有考慮到數(shù)據(jù)存儲(chǔ)和查詢(xún)過(guò)程中的能量開(kāi)銷(xiāo)問(wèn)題。

蛇形時(shí)隙的節(jié)能存儲(chǔ)算法（SLPS）［13］基于GHT算法思想，將被監(jiān)測(cè)區(qū)域按實(shí)際應(yīng)用劃分為網(wǎng)格，網(wǎng)格內(nèi)所有節(jié)點(diǎn)的工作時(shí)隙以一種蛇形排列方式進(jìn)行分配，各節(jié)點(diǎn)周期性地進(jìn)入睡眠或偵聽(tīng)狀態(tài)。在任一時(shí)隙，只有兩個(gè)傳感節(jié)點(diǎn)處于工作狀態(tài)，其他節(jié)點(diǎn)都處于睡眠狀態(tài)，既保證了系統(tǒng)的可靠性，又降低了能量消耗。該算法沒(méi)有考慮在數(shù)據(jù)傳輸過(guò)程中節(jié)點(diǎn)的能量消耗。

針對(duì)上述問(wèn)題，考慮到節(jié)點(diǎn)數(shù)據(jù)的重要程度，越重要的數(shù)據(jù)優(yōu)先級(jí)越高，查詢(xún)頻率也會(huì)相應(yīng)提高；在蛇形時(shí)隙節(jié)能算法的基礎(chǔ)上，對(duì)事件劃分優(yōu)先級(jí)，本文提出基于事件優(yōu)先級(jí)和動(dòng)態(tài)散列位置的蛇形時(shí)隙算法（P-SLPS），通過(guò)縮短數(shù)據(jù)存儲(chǔ)和查詢(xún)時(shí)數(shù)據(jù)的傳輸路徑，減少能量消耗，延長(zhǎng)網(wǎng)絡(luò)生命周期。

1 基于事件優(yōu)先級(jí)和動(dòng)態(tài)散列位置的蛇形時(shí)隙算法

P-SLPS算法通過(guò)劃分網(wǎng)格區(qū)域，將特定類(lèi)型的數(shù)據(jù)存儲(chǔ)在相應(yīng)的網(wǎng)格中，而不是存儲(chǔ)在某個(gè)節(jié)點(diǎn)上；通過(guò)定義事件優(yōu)先級(jí)，將高優(yōu)先級(jí)的事件存儲(chǔ)在距離查詢(xún)節(jié)點(diǎn)更近的網(wǎng)絡(luò)區(qū)域，保證高優(yōu)先級(jí)事件最先被搜索到；根據(jù)監(jiān)測(cè)節(jié)點(diǎn)和存儲(chǔ)映射地址計(jì)算動(dòng)態(tài)散列位置，將檢測(cè)事件存儲(chǔ)在同一優(yōu)先級(jí)區(qū)域內(nèi)離監(jiān)測(cè)節(jié)點(diǎn)最近的存儲(chǔ)網(wǎng)格。

1.1 網(wǎng)絡(luò)劃分

假設(shè)網(wǎng)絡(luò)區(qū)域?yàn)橐粋€(gè)L×L的正方形區(qū)域，節(jié)點(diǎn)均勻分布其中。假定無(wú)線傳感器網(wǎng)絡(luò)符合以下規(guī)則［14-15］：網(wǎng)絡(luò)有很好的連通性；網(wǎng)絡(luò)部署后，Sink節(jié)點(diǎn)和其他節(jié)點(diǎn)不再移動(dòng)；網(wǎng)絡(luò)的周界已知，節(jié)點(diǎn)的位置坐標(biāo)已知；節(jié)點(diǎn)間的通信范圍相同。另外，網(wǎng)絡(luò)中事件的產(chǎn)生是隨機(jī)的，每個(gè)事件都有事件類(lèi)型，不同節(jié)點(diǎn)可以產(chǎn)生相同類(lèi)型的事件和數(shù)據(jù)。

假定Sink節(jié)點(diǎn)坐標(biāo)為（0，0），監(jiān)測(cè)事件有K類(lèi)，以[L/(K+1)]*i(i=1，2，3，…，K)為半徑，（0，0）為頂點(diǎn)畫(huà)圓，構(gòu)成K個(gè)圓環(huán)區(qū)域，分別存儲(chǔ)K類(lèi)事件。每類(lèi)事件賦予一種優(yōu)先級(jí)，其值由事件按查詢(xún)頻率確定。優(yōu)先級(jí)值越小，事件優(yōu)先級(jí)越高，事件存儲(chǔ)區(qū)域距離Sink節(jié)點(diǎn)越近。如優(yōu)先級(jí)為1的事件存儲(chǔ)在離Sink節(jié)點(diǎn)最近的圓環(huán)區(qū)域內(nèi)。

為了使存儲(chǔ)節(jié)點(diǎn)距離監(jiān)測(cè)節(jié)點(diǎn)更近，提出動(dòng)態(tài)散列位置的概念。首先以Sink節(jié)點(diǎn)為頂點(diǎn)，90/n為夾角，將網(wǎng)絡(luò)區(qū)域劃分為a、b、c、d、…、n區(qū)。將存儲(chǔ)區(qū)域劃分為網(wǎng)格，如圖1所示。

圖1 事件存儲(chǔ)網(wǎng)格劃分

1.2 節(jié)點(diǎn)工作時(shí)隙的分配

以蛇形時(shí)隙節(jié)能思想，為網(wǎng)格中每個(gè)節(jié)點(diǎn)分配工作時(shí)隙。任一時(shí)隙間隙，每個(gè)網(wǎng)格中有且僅有兩個(gè)節(jié)點(diǎn)同時(shí)處于偵聽(tīng)模式，其他節(jié)點(diǎn)都將進(jìn)入睡眠模式。

首先，計(jì)算每個(gè)網(wǎng)格內(nèi)的節(jié)點(diǎn)個(gè)數(shù)，以及各個(gè)節(jié)點(diǎn)到網(wǎng)格中心點(diǎn)的距離，按距離從小到大為節(jié)點(diǎn)編號(hào)(A、B、C、…、N)，用一個(gè)m行n列的矩陣T為網(wǎng)格內(nèi)的每個(gè)節(jié)點(diǎn)分配偵聽(tīng)或睡眠時(shí)隙。矩陣T中的元素Tij表示節(jié)點(diǎn)工作時(shí)隙。為保證每個(gè)節(jié)點(diǎn)睡眠和偵聽(tīng)周期公平，m和n的值盡量接近。矩陣T的行m和列n與網(wǎng)格內(nèi)節(jié)點(diǎn)數(shù)量N的關(guān)系如式（1）所示：

式中，若N為偶數(shù)，滿足m=n=N/2；若N為奇數(shù)，規(guī)定矩陣行數(shù)m為N/2向上取整，列數(shù)n=N-m，m+n個(gè)節(jié)點(diǎn)對(duì)應(yīng)m×n個(gè)工作時(shí)隙。

節(jié)點(diǎn)工作時(shí)隙Tij分配如式（2）所示：

假設(shè)網(wǎng)格內(nèi)有7個(gè)節(jié)點(diǎn)（A、B、C、D、E、F、G），則N=7，由式（1）計(jì)算得m=4，n=3。根據(jù)式（2）代入i，j值，構(gòu)建矩陣T如圖2所示。

圖2 4×3矩陣中節(jié)點(diǎn)工作時(shí)隙分配

從第一行第一列開(kāi)始，自左向右分配連續(xù)的時(shí)隙，如遇矩陣邊界則垂直換到下一行，并以相反的方向繼續(xù)分配連續(xù)的時(shí)隙。如圖2所示，第一行從左到右為時(shí)隙1、2、3，第二行從右到左為時(shí)隙4、5、6，以此類(lèi)推。每個(gè)節(jié)點(diǎn)被映射到i行或 j列，保證每個(gè)時(shí)隙內(nèi)有兩個(gè)節(jié)點(diǎn)處于活動(dòng)狀態(tài)。矩陣T中，節(jié)點(diǎn)對(duì)應(yīng)行或列中的元素表示節(jié)點(diǎn)的工作時(shí)隙。節(jié)點(diǎn)A的活動(dòng)時(shí)隙為1、2、3，其余時(shí)隙處于睡眠狀態(tài)。節(jié)點(diǎn)E的活動(dòng)時(shí)隙為1、6、7和12。采用蛇形時(shí)序分配方式，在時(shí)隙切換時(shí)始終保證有節(jié)點(diǎn)處于連續(xù)工作狀態(tài)，如時(shí)隙1中節(jié)點(diǎn)A、E處于工作狀態(tài)，當(dāng)時(shí)隙1切換到時(shí)隙2時(shí)，節(jié)點(diǎn)E進(jìn)入休眠狀態(tài)，節(jié)點(diǎn)F從休眠狀態(tài)進(jìn)入工作狀態(tài)，而節(jié)點(diǎn)A在時(shí)隙1切換到時(shí)隙2的過(guò)程中始終處于工作狀態(tài)，這種分配方式避免了時(shí)隙切換時(shí)的丟包現(xiàn)象，保證了網(wǎng)絡(luò)運(yùn)行的可靠性［13］。

1.3 存儲(chǔ)節(jié)點(diǎn)的選擇

如圖3所示，監(jiān)測(cè)節(jié)點(diǎn)B(Xb,Yb)監(jiān)測(cè)到事件優(yōu)先級(jí)為K-1的數(shù)據(jù)，對(duì)應(yīng)存儲(chǔ)點(diǎn)應(yīng)在第K-1層環(huán)內(nèi)。利用散列表［16］映射到散列位置G(Xg,Yg)，節(jié)點(diǎn)B在區(qū)域b中，散列位置G在區(qū)域c中，利用監(jiān)測(cè)節(jié)點(diǎn)和散列位置坐標(biāo)計(jì)算動(dòng)態(tài)散列位置G0(Xg0,Yg0)，其中散列位置G和動(dòng)態(tài)散列位置G0位于同一半徑圓弧上，監(jiān)測(cè)節(jié)點(diǎn)B和動(dòng)態(tài)散列位置G0位于同一半徑軸線上。選擇動(dòng)態(tài)散列位置G0所在網(wǎng)格內(nèi)的工作節(jié)點(diǎn)作為事件存儲(chǔ)節(jié)點(diǎn)，其坐標(biāo)由式（3）和式（4）求得。

圖3 存儲(chǔ)節(jié)點(diǎn)選擇

1.4 事件存儲(chǔ)

當(dāng)節(jié)點(diǎn)B監(jiān)測(cè)到事件后，經(jīng)散列運(yùn)算得到散列位置G，根據(jù)監(jiān)測(cè)節(jié)點(diǎn)和散列位置坐標(biāo)求得離監(jiān)測(cè)節(jié)點(diǎn)距離最近的動(dòng)態(tài)散列位置G0，采用地理位置路由（GPSR）算法可以將監(jiān)測(cè)到的事件路由到離動(dòng)態(tài)散列位置所在的網(wǎng)格區(qū)域。當(dāng)數(shù)據(jù)送至動(dòng)態(tài)散列位置所在網(wǎng)格區(qū)域時(shí)，采用區(qū)域泛洪方式將數(shù)據(jù)保存在處于偵聽(tīng)模式下的兩個(gè)節(jié)點(diǎn)中，如圖4所示。收到數(shù)據(jù)的節(jié)點(diǎn)根據(jù)ID編號(hào)給監(jiān)測(cè)節(jié)點(diǎn)B回復(fù)一個(gè)ACK應(yīng)答消息。如果監(jiān)測(cè)節(jié)點(diǎn)等待一段時(shí)間后，沒(méi)有收到ACK消息，則認(rèn)為該數(shù)據(jù)已經(jīng)丟失，重新向存儲(chǔ)區(qū)域發(fā)送該數(shù)據(jù)。數(shù)據(jù)保存在兩個(gè)節(jié)點(diǎn)中，增加了數(shù)據(jù)存儲(chǔ)的可靠性。

圖4 數(shù)據(jù)存儲(chǔ)示意圖

1.5 事件查詢(xún)

當(dāng)用戶需要查詢(xún)相關(guān)數(shù)據(jù)時(shí)，Sink節(jié)點(diǎn)將查詢(xún)請(qǐng)求解析優(yōu)化后，給n個(gè)扇形區(qū)域各自發(fā)送一份查詢(xún)命令Query(Key,Priority)。當(dāng)查詢(xún)分組信息傳送到要查詢(xún)的事件類(lèi)型對(duì)應(yīng)的存儲(chǔ)節(jié)點(diǎn)后，存儲(chǔ)節(jié)點(diǎn)會(huì)檢索自己保存的數(shù)據(jù)，看是否存在查詢(xún)需要的數(shù)據(jù)，若存儲(chǔ)節(jié)點(diǎn)存在查詢(xún)請(qǐng)求所需的數(shù)據(jù)，則將數(shù)據(jù)發(fā)送給查詢(xún)節(jié)點(diǎn)；如果存儲(chǔ)節(jié)點(diǎn)不存在查詢(xún)所需的數(shù)據(jù)，存儲(chǔ)節(jié)點(diǎn)將轉(zhuǎn)發(fā)收到的查詢(xún)請(qǐng)求信息，如圖5所示。

2 P-SLPS算法運(yùn)行過(guò)程

P-SLPS算法的運(yùn)行過(guò)程主要分為網(wǎng)絡(luò)初始化和穩(wěn)定運(yùn)行兩個(gè)階段。初始化階段的主要工作是：劃分網(wǎng)格、分配節(jié)點(diǎn)工作時(shí)隙。每個(gè)節(jié)點(diǎn)在網(wǎng)格內(nèi)通過(guò)廣播一條消息來(lái)交換其在網(wǎng)格內(nèi)的基本信息，建立一個(gè)用于存儲(chǔ)同一網(wǎng)格內(nèi)其他鄰居節(jié)點(diǎn)的信息表Grid_Node，該表由節(jié)點(diǎn)所屬的網(wǎng)格（GRID）、節(jié)點(diǎn)的坐標(biāo)（LN）、節(jié)點(diǎn)能量（NE）和事件類(lèi)型（ET）四個(gè)部分組成，并且每個(gè)節(jié)點(diǎn)能量相等。

穩(wěn)定運(yùn)行階段為時(shí)間輪的循環(huán)，每輪中，當(dāng)節(jié)點(diǎn)監(jiān)測(cè)到有事件發(fā)生時(shí)，該節(jié)點(diǎn)會(huì)依據(jù)事件類(lèi)型向存儲(chǔ)節(jié)點(diǎn)發(fā)送一個(gè)Put packet數(shù)據(jù)包，根據(jù)監(jiān)測(cè)事件的屬性值和監(jiān)測(cè)節(jié)點(diǎn)的位置信息選擇相應(yīng)的存儲(chǔ)節(jié)點(diǎn)，事件發(fā)生時(shí)的數(shù)據(jù)存儲(chǔ)以及根據(jù)用戶需求進(jìn)行的數(shù)據(jù)查詢(xún)。Sink節(jié)點(diǎn)在檢索相應(yīng)的事件前，向存儲(chǔ)節(jié)點(diǎn)發(fā)送一個(gè)Get packet數(shù)據(jù)查詢(xún)包。

圖5 數(shù)據(jù)查詢(xún)示意圖

3 仿真分析

為了驗(yàn)證P-SLPS算法，基于MATLAB仿真平臺(tái)。從扇形區(qū)域數(shù)、事件數(shù)量以及事件集中出現(xiàn)等方面，比較分析P-SLPS、SLPS算法。網(wǎng)絡(luò)生命周期采用網(wǎng)絡(luò)中有50%的節(jié)點(diǎn)死去的時(shí)間。假設(shè)100個(gè)節(jié)點(diǎn)隨機(jī)部署在邊長(zhǎng)為200 m的正方形區(qū)域內(nèi)，以Sink節(jié)點(diǎn)為頂點(diǎn)，以90/6為夾角，將網(wǎng)絡(luò)區(qū)域劃分為n（可變）個(gè)扇形區(qū)域。在各個(gè)優(yōu)先級(jí)事件均勻分布的前提下，比較n從1到8時(shí)，P-SLPS算法網(wǎng)絡(luò)生命周期的情況，如圖6所示。由圖6可知，當(dāng)n=6時(shí)P-SLPS算法網(wǎng)絡(luò)生命周期最長(zhǎng)，取最優(yōu)劃分個(gè)數(shù)時(shí)，有效地降低系統(tǒng)開(kāi)銷(xiāo)。實(shí)驗(yàn)選取最佳扇形區(qū)域數(shù)（n）為6，再將區(qū)域按周向間距為50 m劃分，構(gòu)成網(wǎng)格區(qū)域。約定一個(gè)時(shí)隙為1 s。假設(shè)查詢(xún)頻率為10次/s，網(wǎng)絡(luò)中查詢(xún)節(jié)點(diǎn)位于坐標(biāo)（0，0）；網(wǎng)格中只有三種屬性的事件隨機(jī)出現(xiàn)在網(wǎng)格中，優(yōu)先級(jí)分別為1、2、3。

圖6 扇形區(qū)域數(shù)對(duì)P-SLPS算法網(wǎng)絡(luò)生命周期的影響

在各個(gè)優(yōu)先級(jí)事件隨機(jī)分布在監(jiān)測(cè)區(qū)域內(nèi)，SLPS和P-SLPS存儲(chǔ)算法的網(wǎng)絡(luò)生命周期情況如圖7所示。網(wǎng)絡(luò)運(yùn)行的初始階段，兩種算法中網(wǎng)內(nèi)剩余節(jié)點(diǎn)數(shù)相同，并且在300 s時(shí)都出現(xiàn)死亡節(jié)點(diǎn)，隨著網(wǎng)絡(luò)的運(yùn)行，死亡節(jié)點(diǎn)數(shù)增加，SLPS算法比P-SLPS算法中節(jié)點(diǎn)死亡速度快。SLPS算法在1 800 s時(shí)網(wǎng)內(nèi)剩余節(jié)點(diǎn)數(shù)量為50個(gè)，而P-SLPS算法中的剩余節(jié)點(diǎn)數(shù)量為73個(gè)。P-SLPS算法采用優(yōu)先級(jí)的存儲(chǔ)策略降低了網(wǎng)內(nèi)節(jié)點(diǎn)的能量消耗。

圖7 SLPS和P-SLPS網(wǎng)絡(luò)生命周期比較

如圖8所示，當(dāng)單位時(shí)間內(nèi)查詢(xún)事件數(shù)目由10增加到40時(shí)，P-SLPS算法和SLPS算法相比，網(wǎng)絡(luò)生命周期下降的速度較慢；當(dāng)事件查詢(xún)頻率越高時(shí)，網(wǎng)絡(luò)生命周期差異越大。事件按優(yōu)先級(jí)高低存儲(chǔ)在離匯聚節(jié)點(diǎn)由近及遠(yuǎn)的網(wǎng)格內(nèi)，有效的減少了數(shù)據(jù)查詢(xún)過(guò)程中的節(jié)點(diǎn)的能量消耗，從而延長(zhǎng)網(wǎng)絡(luò)生命周期。

圖8 查詢(xún)事件數(shù)量對(duì)網(wǎng)絡(luò)生命周期的影響

如圖9所示，當(dāng)單位時(shí)間內(nèi)監(jiān)測(cè)事件由10增加到40時(shí)，兩種策略下的網(wǎng)絡(luò)生命周期整體趨勢(shì)都是下降的，但基于動(dòng)態(tài)散列位置的存儲(chǔ)策略下降比較快。對(duì)比圖8和圖9可以看出，受事件存儲(chǔ)的影響，監(jiān)測(cè)相比查詢(xún)對(duì)網(wǎng)絡(luò)生命周期的影響更明顯，因?yàn)椴樵?xún)時(shí)查詢(xún)節(jié)點(diǎn)首先要向存儲(chǔ)節(jié)點(diǎn)發(fā)送查詢(xún)包，相比監(jiān)測(cè)事件傳輸過(guò)程中的能量消耗，查詢(xún)包傳輸過(guò)程中的能量消耗較少。

當(dāng)單位時(shí)間內(nèi)的監(jiān)測(cè)事件由10增加到40時(shí)，假定優(yōu)先級(jí)為2的事件集中出現(xiàn)在監(jiān)測(cè)網(wǎng)中某一區(qū)域，事件分布對(duì)P-SLPS算法性能的影響，如圖10所示。從圖10看出，當(dāng)存儲(chǔ)事件頻率相同，監(jiān)測(cè)事件均勻分布比事件集中出現(xiàn)時(shí)的網(wǎng)絡(luò)生命周期要長(zhǎng)，并且當(dāng)事件存儲(chǔ)頻率越大，事件集中出現(xiàn)對(duì)網(wǎng)絡(luò)生命周期的影響也越大。優(yōu)先級(jí)為2的事件集中出現(xiàn)，使該區(qū)域內(nèi)優(yōu)先級(jí)為2的事件對(duì)應(yīng)的存儲(chǔ)節(jié)點(diǎn)集中存儲(chǔ)事件，產(chǎn)生存儲(chǔ)熱點(diǎn)現(xiàn)象，導(dǎo)致存儲(chǔ)節(jié)點(diǎn)過(guò)早死亡，從而影響整個(gè)網(wǎng)絡(luò)的生命周期。

圖9 監(jiān)測(cè)事件數(shù)量對(duì)網(wǎng)絡(luò)生命周期的影響

圖10 事件集中出現(xiàn)對(duì)網(wǎng)絡(luò)生命周期的影響

4 結(jié)論

分析以數(shù)據(jù)為中心的平面型存儲(chǔ)算法基礎(chǔ)上，根據(jù)事件優(yōu)先級(jí)，結(jié)合動(dòng)態(tài)散列位置，本文提出基于事件優(yōu)先級(jí)和動(dòng)態(tài)散列位置的蛇形時(shí)隙存儲(chǔ)算法（P-SLPS），目的是為減少數(shù)據(jù)傳輸過(guò)程中產(chǎn)生的能量消耗。該策略采用蛇形時(shí)隙控制同一網(wǎng)格中只有兩個(gè)節(jié)點(diǎn)來(lái)偵聽(tīng)數(shù)據(jù)，以節(jié)省節(jié)點(diǎn)空閑偵聽(tīng)?zhēng)?lái)的能量消耗。在此基礎(chǔ)上設(shè)計(jì)事件散列函數(shù)，根據(jù)事件的優(yōu)先級(jí)從高到低將事件存儲(chǔ)于離查詢(xún)節(jié)點(diǎn)由近及遠(yuǎn)的網(wǎng)格內(nèi)，將散列位置旋轉(zhuǎn)至與監(jiān)測(cè)節(jié)點(diǎn)最近的網(wǎng)格內(nèi)，以減少數(shù)據(jù)存儲(chǔ)和數(shù)據(jù)查詢(xún)過(guò)程中節(jié)點(diǎn)的能量消耗。

P-SLPS算法的運(yùn)行過(guò)程主要分為網(wǎng)絡(luò)初始化和穩(wěn)定運(yùn)行兩個(gè)階段。初始化階段的主要工作是：劃分網(wǎng)格、節(jié)點(diǎn)工作時(shí)隙的分配。穩(wěn)定運(yùn)行階段為時(shí)間輪的循環(huán)?；贛ATLAB仿真平臺(tái)，從扇形區(qū)域數(shù)、事件數(shù)量以及事件集中出現(xiàn)等方面，比較分析P-SLPS、SLPS算法。仿真結(jié)果表明，相比SLPS算法，P-SLPS算法節(jié)省能量，延長(zhǎng)了無(wú)線傳感網(wǎng)絡(luò)的生命周期。

［1］謝志軍，唐建華，楊婧，金光.無(wú)線傳感器網(wǎng)絡(luò)中基于連通核的高效Skyline查詢(xún)算法［J］.傳感技術(shù)學(xué)報(bào)，2013，26（10）：1437-1445.

［2］陳穎文，徐明，吳一.無(wú)線傳感器網(wǎng)絡(luò)網(wǎng)內(nèi)數(shù)據(jù)處理節(jié)點(diǎn)的優(yōu)化選?。跩］.軟件學(xué)報(bào)，2007，18（12）：3104-3114.

［3］惠曉威，劉彥每.WSN數(shù)據(jù)收集中移動(dòng)Sink的路徑規(guī)劃和簇頭節(jié)點(diǎn)選取問(wèn)題的綜合研究［J］.傳感技術(shù)學(xué)報(bào)，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］韓鴻泉，朱紅松，孟軍.無(wú)線傳感器網(wǎng)絡(luò)技術(shù)［J］.計(jì)算機(jī)系統(tǒng)應(yīng)用，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-），男，漢族，博士，副教授，碩士生導(dǎo)師，主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)、智能信息處理等，linzhigui@tjpu.edu.cn；

安旭磊（1990-），男，河北保定人，碩士研究生，主要研究方向?yàn)轶w域網(wǎng)、智能信息處理等。

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

項(xiàng)目來(lái)源：國(guó)家自然科學(xué)基金項(xiàng)目（61372011）

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