無線傳感器網絡數據環區域查詢處理算法*

李澤軍，曾利軍，劉 卉

(湖南工學院計算機科學與信息學院，湖南衡陽421002)

由于無線傳感器網成本低、配置靈活、具有自組網能力、對環境影響小而廣泛應用于對目標的感知和環境監測。在工農業中具有廣泛的應用前景。目前Skyline查詢的研究領域都集中在數據庫領域中，無線傳感器網絡的Skyline查詢處理技術研究相對而言還比較少。而無線傳感器網絡在實際研究中同樣具有重要意義，例如在地質檢測研究時，當地質研究員需要尋找在近海地層中具有一定礦物分布、一定的水流速度，并且滿足一定開采條件的地層作為研究對象時，就可以采用Skyline查詢來尋找接近這幾個查詢條件的多目標樣本區域，然后進行處理研究。同樣在海洋中研究一定溫度、一定數量、一定水流速度的魚群也可利用Skyline處理技術進行查詢等。目前人們針對傳感器網絡設計了很多節能查詢處理算法[1]。這些算法可以分為以下5類:聚集查詢、JOIN查詢處理算法、近似查詢處理算法、數據采集算法以及基于事件的查詢。近年來許多學者們對Skyline處理技術做了大量研究。BorZsonyi S.等提出了 Skyline查詢處理的通用 B＆L與 D＆C算法[1－2]。其基本思路是通過比較每個對象的值域，從而得出Skyline集。Chomicki J.等提出了基于預排序的SFS算法[3]。該算法將對象的各個屬性按照評價值的大小進行排序，然后根據排序值進行訪問、判斷。Kossmann D.等借鑒了最近鄰搜索技術，提出了R樹索引[4]。該方法通過計算最近鄰查詢的結果進行遞歸劃分數據空間。以上這些算法只適合于集中的數據庫系統，對分布式環境和無線傳感器網絡不能達到預期的目標。Wang S Y.等基于平衡樹結構[4]。該方法對查詢子空間的Peer點進行估計，在一定程度上平衡了Peer節點的查詢負載，解決了查詢熱點問題。但由于平衡樹結構的數據量大，從而給計算和數據通信帶來較大的困難，因此以上方法無線傳感器網絡中并不合適。

針對無線傳感器網絡節點能量高效問題以及Skyline查詢處理技術本身復雜性等問題，本文提出了基于無線傳感器網絡數據環區域查詢處理算法。該方法的基本思想:在無線傳感器網絡數據查詢處理上，將數據區域進行區域環劃分，判斷位置節點P是否屬于全局K－Skyline，只需對距離小于節點P的屬性節點比較，環內數據以數據鏈的形式組織，環內節點與環間節點分別采用串行與并行的處理模式，從而提高了K－Skyline的數據查詢能耗與節點處理延遲。

1 相關問題描述

無線傳感器網絡節點的能耗和查詢延遲是目前傳感器網絡的查詢熱點之一。如何建立即滿足查詢條件又高效的K－Skyline數據查詢算法是本文需要解決的問題。設傳感器網絡中有N個節點，簇首節點為m個，在數據空間 S={s1，s2，…，sm}中對數據區域Q 進行查詢計劃 KSQ=＜S，Q，P，K＞，其中 P 為K－Skyline的查詢條件，K為數據區域環數。

1.1 相關定理

定理1:設定 m維數據集 S和 S1為全序數據[5－6]，且 S1?S，若 Skyline(S1)和 Skyline(S)為 S1和S的 Skyline數據集，則對于任意 s∈S1，若 s?Skyline(S1)，則s?Skyline(S)。此定理容易用反證法證明。這里省略。

定理2:設定m維數據集S為全序數據空間S={s1，s2，…，sm}[7]，O 為 S 上的數據集，D={p，q}?O，Skyline(D為集合Si(1≤i≤m)和集合D所確定的 Skyline 集。若存在維 Si滿足 p.si﹤ q.si，則 p∈Skyline(D)。

根據定理1和定理2可以得到以下2個推論。

推論1:設定m維數據集S為全序數據空間S={s1，s2，…，sm}，O 為 S 上的數據集，D={p，q}?O，Skyline(D)為集合Si(1≤i≤m)和集合D所確定的Skyline集。若存在維 Si滿足 p.si﹤ q.si，則如果存在維 sj(1≤j≤m，j≠i)滿足 p.sj﹤ q.sj，則 q∈Skyline(D)。

推論2:設定m維數據集S為全序數據空間S={s1，s2，…，sm}，p={pi|1≤i≤n}為 S 上的對象集，且i＜j，pi.si≤pj.si。設 Skyline(P)為集合 Si(1≤i≤m)和集合P所確定的Skyline集。pi∈p，p1={pj|1≤j＜i}，p2={pj|i＜j≤n}，則 pi∈Skyline(P)不存在 pk∈p1使得對于任意維 sk(1≤k≤m，k≠i)滿足 pj.sk﹤pi.sk，且與 P2無關。

1.2 問題分析

由定理1，2和推論3，4我們在m維數據集S的Skyline時，通過對數據集D的預處理即對數據集的對象進行屬性的隊列Q排序，使得隊列前面的數據對象在m維上支配隊列后面的數據對象，由此可以判斷對象P是否在S上的Skyline點問題就可以轉化為判斷對象P是否在S1上的Skyline點問題[8]。其中S1為在隊列Q前面的數據對象集。此轉化的目的是為了得到規模更小的數據對象集。如圖1的具體實例中，以費用最小距離越近為原則的Skyline點集合，假定考慮以距離為維度的次序關系，對于P節點來說，只需下方節點的集合就可以確定P是否屬于全局的Skyline集。

圖1 節點skyline集規?？s小示意圖

根據以上綜合分析可以得出，在傳感器網絡中進行Skyline數據查詢可以根據距離的屬性值大小進行排序及對數據集進行歸類劃分，判斷P是否屬于PSkyline只需將P節點與距離P節點的屬性值小的節點除距離以外的其它Skyline進行比較即可，從而減少數據庫查詢的規模。由于距離P節點小的處理結果已知，因此節點P處理的結果即為全局P－Skyline的查詢條件的結果，無需對距離大于P節點進行比較處理。提高了p－Skyline的查詢處理延遲。

2 基于無線傳感器網絡的數據環區域K-Skyline查詢

2.1 數據環區域查詢思想

(1)將傳感器網絡待檢測的區域劃分為以q為節點的同心環，在同環內的節點屬性為一集合。按照環的距離劃分可以得到不同的節點屬性集合，這里編號為 r(0)，r(1)，…，r(n)。且對于 r(i)和 r(j)(i＜j)。因此在處理r(0)到r(n)時只需處理r(0)到r(i－1)的r個環內K－Skyline集。通過比較環內K－Skyline集和已得到的K－Skyline集，直到滿足K－Skyline查詢條件k個數據對象。

(2)對于同一環內的節點則采用鏈簇式結構[9－10]。在鏈簇式結構的鏈首節點負責向環內的節點發送K－Skyline查詢條件以得到同簇內K－Skyline集并向鄰簇首節點發送同簇內K－Skyline集，直到最后一個簇首節點。

(3)不同環內的節點數據采用串行和并行的處理模式。串行的數據處理則根據同心環的距離，并行的數據處理則根據環內的數據進行同步處理。其兩種模式的數據處理如圖2和圖3所示。

圖2 串行數據處理模式

圖3 并行數據處理模式

由圖2得知串行數據處理模式中將R(0)做為鏈式首節點，將 R(0)環內數據作為 K－Skyline集(記作rp(0))，根據定理2和推論3可以得出rp(0)也為全局K－Skyline集的解(記作 rp)。將 rp(0)全局 KSkyline集的一部分返回至查詢起始點。若|rp(0)|＜k則將rp(0)的鏈式尾節點與查詢條件發送到R(1)鏈式首節點，R(1)接收到查詢計劃后與K－Skyline集重復比較rp(0)得到rp(1)。若|rp(0)+rp(1)|＞k則查詢結束。重復執行以上過程直到找到R(i)，滿足|rp(0)+rp(1)+…+rp(i)|＞k，rp(0)∪rp(1)∪…∪rp(i)均返回查詢起始點。然后起始點從rp(0)∪rp(1)∪…∪rp(i)中選擇最優的K個K－Skyline集返回到Sink節點。在并行模式下查詢起始點將K－Skyline查詢計劃發送到各個環內的首節點，然后由各個環內的數據處理模式并行處理。最后返回到Sink節點。

2.2 數據環區域寬度最優劃分

數據環區域劃分的關鍵是如何確定數據區域寬度DW(Data Width)的問題。若DW過小，則在傳感器數據通信中存在過多的信號覆蓋問題，在信號交叉區域內會收到重復的多個簇節點訪問，傳感器節點能量過多。若DW太大，則每個數據區域環的節點就增多，導致節點的距離增大。而傳感器需要收集區域環寬度內所有數據，因此數據的延遲和能耗也過多。理想的DW使整個覆蓋區域內有最小的覆蓋交叉，并能保證所有節點都能采集到。下面通過圖4和驗證來求解最優DW值。

圖4 傳感器數據區域最優DW示意圖

設n1和n2為數據區域環形的鄰簇節點，由圖4可以看出環形區域寬度DW不能超過n1和n2重疊區域的直徑，否則其它簇的節點將不能被訪問到，如n3節點。這里用Sr表示相鄰環節點通信重疊區，Sc表示相鄰簇首節點通信重疊區。S表示查詢所有節點的重疊區。故S=Sc+Sr，求解最優DW即為求解min(S)。

設查詢區域半徑為Rq，傳感器通信半徑為Rc，則環形的最大數目。則最大的Sr為:

在計算Sc時，設環形R(i)的Sc記為Sc(Ri)。d為相鄰節點的距離，Sc(ni，ni+1)為相簇首節點的Sc，則在R(i)環內的節點數Ci為:

根據外接矩陣L可以得到:

根據式(2)和(4)可得:

又S=Sc+Sr和式(1)、式(5)聯立可得:

令 DW=krt，查詢半徑 rq=αrt，則。在α和rt為常量時，可使得S最小即的極值。通過證明可得kmin≈1.84，DW≈1.84rt時，d≈0.8rt，S 最小。(由于篇幅，這里證明省略，如需要可以提供)

2.3 鏈簇式結構的處理與構建

根據環形結構的特點和節點位置已知的情況，首先將已知節點組織成鏈簇式結構，然后根據節點的組織結構進行 K－Skyline查詢處理。鏈簇式結構[11]與節點信息如表1和表2進行組織。

表1 節點結構

表2 信息結構

在節點結構中，Link_Position_Flag表示節點位置標識，0為鏈首節點，1為鏈中節點，2為鏈尾節點，3為簇內節點。在信息結構中，Query_Area_Q字段為信息查詢區域，Ring_Width_Dw為區域信息寬度DW值，Ring_No環編號，MsgFlag為信息類型標識。在構建鏈簇式結構時分為串式處理模式與并行處理模式。在串行處理建簇中，鏈首節點P根據查詢區域Q與DW值及P的位置信息建立節點結構并設標記為1。通過廣播傳播未接到建鏈信息的節點且與Q在同一環中時設為簇內節點。同時P根據d≈0.8rt計算下一簇首節點的最優值q。根據q和圖2串行數據處理順時針查詢距離q最近的節點最優值為下一簇的首節點P1。也就是鏈中節點P1。重復以上建鏈，直到鄰節點本身為首節點時結束。最后向環外節點繼續進行建鏈并進行環編號。并行數據處理模式與串行基本相同，其區別是各環區域的鏈并不是首尾相連。即環R(i)與環R(i+1)的首節點相連。其建鏈過程圖如5所示。

圖5 串、并行處理數據節點的建鏈過程

這里只描述并行數據環區域K－line算法，參數DRSK(Q，c，k，q_ini)為數據環區域 K－line 查詢計劃。C為查詢條件，Q為查詢區域，q_ini為首節點。記局部K－line集為RSK_temp，全局K－line集為RSK_all。由于篇幅限制，這里只描述并行處理算法:

輸入:DSK(Q，c，k，q_ini)，RSK_temp

輸出:RSK_all

if ni為起始節點則執行(1)～(3)

(1)等待直到返回RSK(R(i))

(2)根據所有RSK(R(i))集以獲得RSK

(3)通過GPS發送RSK_all到簇首節點

那么從父節點 ni接收 DSK(Q，c，k，q_ini)執行(4)

(4)在ni上執行DSK并且返回RSK(ni)到父節點ni

否則根據條件 DSK(Q，c，k，q_ini)，RSK_temp執行(5)～(8)

(5)if(ni是link_head node)并且(next link_head node是空)

發送 DSK(Q，c，k，q_ini)和 RSK_temp 到 next link_head node

(6)發送 DSK(Q，c，k，q_ini)到 cluster_in node(ni)

(7)從cluster_in node(ni)和RSK_temp聚集所有的 DSK(Q，c，k，q_ini)來得到新的 RSK_temp

(8)if ni不是link_tail node

發送 DSK(Q，c，k，q_ini)和 RSK_temp 到 next cluster_head節點

否則通過GPS發送RSK_temp到q_ini。

3 數據環區域K-Skyline查詢的傳輸開銷與延遲

3.1 查詢算法的傳輸開銷

查詢算法的主要傳輸開銷為簇與簇之間節點的數據傳輸以及環內節點的數據傳輸[12]。由3.2節的數據分析可得數據環區域的寬度為DW≈1.84rt，查詢區域半徑為R≈1.84krt(k為環區域數，rt為節點傳輸半徑)，設N為節點數。則節點分布密度ρ=N/πR2。則第i個環內節點數N(i)為:

其中ρ為數據融合率均值。若并行數據環區域KSkyline處理環形區域數為k則傳輸總能耗為。

3.2 查詢算法的延遲

設通信中數據包大小為Sd，數據鏈通知大小Sm。節點接收和發送速率為V。則在R(i)環內的總延遲為:

4 實驗數據及仿真實驗

實驗中采用ns2作為模擬平臺根據不同K值實現能耗和有效節點約束查詢處理算法，傳感器的初始能量設為50 J，節點的通信半徑為26 m，數據包的大小為128 byte，300個傳感器節點隨機分布在半徑R為100 m的區域內。節點速率為100 kbit/s。節點發送或接收1 bit的能耗為9.6×10－6J，12.8×10－6J。MAC層采用IEEE802.11的DCF模式。目前傳感器比較經典的算法是集中式(Flooding)算法和TAG算法。Flooding算法是以廣播方式將查詢計劃發送到查詢目標區域，然后將查詢數據集沿原路返回至起始點。TAG算法是采用生成樹對數據進行分發、匯聚的形式進行處理。仿真實驗中用并行數據環區域PPRDA(Parallel Processing Ring of Data Area)算法及串行數據環區域 SPRDA(Serial Processing Ring of Data Area)算法與集中式數據查詢算法、TAG算法在數據的傳輸開銷和傳輸延遲進行對比。在不同環形區K值的數據處理能耗及總傳輸延遲如圖6和圖7所示。

圖6 K取不同值時各算法的查詢總能耗對比圖

圖7 K取不同值時各算法的查詢總延遲對比圖

由圖1～圖6可以看出，在數據環區域的寬度為DW≈1.84rt，隨著K值的不斷增加總能耗也隨之增加，這是因為K值增加，處理數據量增大的緣故。Flooding算法采用的是廣播方式進行數據傳輸，而廣播方式存在大量的重發現象，因而總能耗遠大于其它算法的查詢能耗，而TAG算法生成樹方式需要查詢所有節點數，然后從葉子節點通過匯聚方式返回起始節點。本文的PPRDA和SPRDA算法都是以指定位置開始查詢計劃，在環內節點滿足查詢條件時就停止查詢，并將查詢集做為最終結果的一部分，因而有效地降低了總能耗。

由圖1～圖7可以看出，K值增加導致數據量增大，各算法的數據處理延遲都要增加。在K值較小的情況下，各算法的總延遲差不多。隨著K值的增加，總的情況下，Flooding算法與TAG算法的總延遲要小于本文的PPRDA和SPRDA算法，這是由于Flooding算法與TAG算法都采用并發的處理模式。在K值較大時，PPRDA算法比SPRDA算法小，這是由于在數據環與數據環之間PPRDA算法采用并行處理模式的緣故。

5 結束語

本文研究了傳感器網絡下的K－Skyline查詢處理決策問題，提出了基于無線傳感器網絡的數據環區域K－Skyline查詢方法，根據不同情況在數據環采用并行數據處理模式與串行數據處理模式，串行處理模式的節點傳輸總能耗最小，而并行處理模式的數據總延遲要小于串行處理模式。兩種算法的都具有良好的穩定性。理論和實踐表明，在不同K值下，本文的PPRDA和SPRDA的K－Skyline查詢處理比Flooding算法與TAG算法具有更小的數據傳輸處理能耗和延遲。異構傳感器高維數據的處理以及信號轉換是目前研究的熱點，下一步將通過投影映射的方式解決高維數據復雜度問題，采用壓縮感知算法與傳感器網路相結合解決信號轉換問題。通過對異構傳感器網絡與不同協議來提高數據查詢處理能耗和延遲效果。

[1]Li J，Mohapatra P.Analytical Modeling and Mitigation Techniques for the Energy Hole Problems in Sensor Networks[J].Pervasive and Mobile Computing，2007，3(3):233－254.

[2]Lindesy S，Raghavendra C S.PEGASIS:Power－Efficient Gathering in Sensor Information Systems[C]//Proc of IEEE Aerospace Conference.Montana:IEEE Press，2002:1125－1130.

[3]Madan R，Lall S.Distributed Algorithms for Maximum Lifetime Routing in Wireless Sensor Networks[J].IEEE Transon Wireless Communications，2006，5(8):2185－2193.

[4]Braginsky D，Estrin D.Rumor Routing Algorithm for Sensor Networks[C]//Proe.of the 1st ACM International Workshop on Wireless Sensor Network sand Applications(WSNA’02).New York，NY，USA:ACM Press，2002:22－32.

[5]范興剛，侯佳斌，介婧.基于DPSO的智能WSN分簇路由算法[J].傳感技術學報，2011，24(4):593－600.

[6]郭龍江，李建中，李貴林.無線傳感器網絡環境下時－空查詢處理方法[J].軟件學報，2006，17(4):794－805.

[7]劉亮，秦小麟，戴華，等.能量高效的無線傳感器網絡時空查詢處理算法[J].電子學報，2010，38(1):54－60.

[8]舒堅，劉琳嵐，董海星，等.機會網絡數據收集中的轉發控制[J].傳感技術學報，2012，25(1):129－134.

[9]潘立強，李建中，駱吉洲.無線傳感器網絡中一種近似Skyline查詢處理算法[J].軟件學報，2010，21(5):1020－1030.

[10]信俊昌，王國仁，張小藝.無線傳感器網絡中的近似輪廓查詢算法[J].小型微型計算機系統，2009，30(8):1490－1494.

[11]陳寧寧，俞立，洪榛，等.無線傳感網高斯分簇路由算法的研究及實現[J].傳感技術學報，2011，22(9):1347－1352.

[12]李貴林，李建中.傳感器網絡中節點個數約束查詢處理算法[J].計算機研究與發展，2008，45(1):90－96.