無線傳感器網絡多查詢的節能優化*

申少輝，王曉明

（暨南大學 計算機系，廣東 廣州510632）

無線傳感器網絡是由一組在地理上廣泛分布、相互之間能夠利用無線信道進行通信的傳感器節點組成的。由于每個節點都可以作為接收節點也可以作為發送節點，并可以與多個其他節點進行協作通信，因此，無線傳感器網絡廣泛應用于商業、電信、環境、軍事等領域。

從無線傳感器中獲得數據主要是靠查詢，通過查詢才能得到想知道的數據。目前對查詢的研究方案很多，但是很少有考慮到多查詢的相似性。這樣傳感器網絡就會多收發很多數據，造成能量消耗。由于能量是影響網絡壽命的關鍵因素，并且CPU的能耗要遠遠小于數據傳輸的能耗[1]。因此數據傳輸在無線傳感器網絡的能耗中占據主體地位。如何進行相似查詢的處理，如何減少數據傳輸的能耗都是急于解決的重要問題。

針對以上問題，本文提出了一個無線傳感器網絡多查詢的節能優化方案。在基站同時存在多個查詢時，提出的方案通過建立相似查詢算法來判斷相似的查詢，并將相似的查詢分為一組。然后在每一組中找一個能使傳輸能耗達到最小的中繼節點作為處理節點。組內節點的數據都傳送到該處理節點，并在該節點利用已知的數據處理函數來處理數據。這樣就減少了網絡中數據的傳輸量。從而有效地節省了網絡的能量，達到能量的最大化利用。

1 相關研究

目前國內對這方面的研究很少，參考文獻[2]中針對多個查詢頻率的不同，提出了一種節能的方法，該方法雖然有效地減少了能量的消耗，但是返回數據的準確性較差，返回數據也不夠及時，同時也沒有考慮查詢的相似性。參考文獻[3]和參考文獻[4]都是以數據為中心的方法，但都沒有考慮到查詢的相似性。參考文獻[5]提出了一種低能耗的數據處理節點選取策略，但是該策略只是在網絡密度低時比較實用。參考文獻[6，7]則在多基站下來進行相似查詢的分配。以上這些文獻都沒有考慮在基站同時存在多個查詢時的相似性。

2 無線傳感器網絡多查詢的節能優化方案

在無線傳感器網絡中同時存在多個查詢時[8-10]，為了減少數據的傳輸量，降低網絡的能量消耗，提高數據傳輸效率，提出了一種通過在多查詢中找相似查詢和處理節點的高效節能方案。方案包括系統模型、相似查詢的判斷及分組和數據處理節點的選取幾個部分。

2.1 系統模型的建立

系統符合以下假設條件：

（1）基站能量不受限制，并且知道網絡中各節點的位置信息。網內節點也知道自己的坐標信息。

（2）若節點 i和 j在相互通信范圍內，則 i和 j可以直接傳輸數據，若二者不能直接通信，則其傳輸路徑長度記為 Dis(i，j)，也就是 i和 j之間的跳數。

（3）所有的查詢都持續一段時間。

（4）每個傳感器節點都具有一定的處理能力,可以進行數據的處理。

（5）把無線傳感器網絡看做規則的網狀結構，并將這個網絡抽象為圖 G=(V,E)，其中 V=v1，v2，…，vn表示節點集合。 節點 vi的位置為(xi，yi)，E表示邊集合，若 vi，vj在通信范圍內就構成了一條邊。它們之間的距離表示為 Dis(i，j)。

如圖 1所示，基站 B是坐標的原點（0，0），橫向右為X軸正向，向下為Y軸正向。圖中基站有3個查詢分布在網絡中，分別是 S1、S2和 S3，根據算法判斷出 S1與S2相似，則把他們分為一組，再找到該組的數據處理節點P1。S3表示沒有相似的，自成一組，找到它的處理節點為P2。在進行數據傳輸時，因為數據處理函數根據實際情況而不同，所以這里只是假設函數已知并可以在所有的傳感器節點上執行。

2.2 相似查詢的判斷及分組

（1）查詢相似的判斷

每個查詢都包括要查詢的范圍和要查詢的信息（即屬性）。判斷兩個查詢相似是基于位置信息來判斷相似的。

算法思想：對于包含m和n個節點的任意兩個查詢qi和 qj，掃描每個查詢節點的坐標，然后進行比較，一旦這兩個查詢有相同的坐標，則這兩個查詢相似。

算法描述如下：

（2）相似查詢的分組

算法思想：先將 k個查詢(q1，q2，…，qk)初始化為 k個組，每個查詢對應一個組，分別用 b1，b2，…，bk表示。然后比較這些組，將所有相似的查詢都分為一組。

算法描述如下：

通過以上算法將基站的查詢分為k1(k1≤k)個組，且每個組內的查詢都是基于地理位置相似的。

2.3 數據處理節點的選取

將基站的查詢分組后，下面分別在這k1個組找到相應的數據處理節點。前面說過，節點離數據源越近，越能夠節省傳輸的能量[11-12]。所以把組內的幾何中心作為該組的數據處理節點。這樣組內節點到達數據處理節點的平均距離就達到最小，消耗的能量也就達到最小。

具體選法如下：

假設組內共有m個節點，組內節點分布均勻。設數據處理節點坐標為P（x，y），則數據處理節點的坐標為：

其中min(x1， … ，xm)，max(x1， … ，xm)，min(y1， … ，ym)和max(y1，…，ym)。 min(x1，…，xm)和 max(x1，…，xm)的求解算法如下：

同理可以求得 min(y1，…，ym)和 max(y1，…，ym)。

數據處理節點的位置坐標為（x，y），即組內節點的數據都傳送到該處理節點，并在該節點利用已知的數據處理函數來處理數據，然后再傳送給基站。這樣就減少了網絡中數據的傳輸量。從而有效地節省了網絡的能量，達到能量的最大化利用。

3 效率與性能分析

對于圖 1所示的網絡模型，設網內節點數為 n，S1與 S2相似，則 S1與 S2分一組為 P1，由圖可以知道組內節點的坐標，則可以算出組內數據處理節點的位置為P1(6，3)，設節點產生數據的速率相等且一定為 r，單位數據大小為s。用本文的方法傳輸數據在一定時間T內組內節點到數據處理節點傳輸數據消耗的能量為C=19rsT，則在數據處理節點總的數據量大小為14rsT，在P1節點經過數據處理后，因為這兩個查詢有重合數據，所以在P1節點發送出的總數據大小為10rsT。則從P1點傳輸數據到基站所需的能量為90rsT，即該方案總的能量大小為C1=109rsT。

如果不對相似查詢進行處理，即所有節點產生的數據直接發送給基站，則這樣的能量消耗為C2=123rsT。由此可見使用該方案可以很有效地減少傳輸數據所消耗的能量。

[5]提出一種找數據處理節點的方法，主要針對單查詢情況，并沒有考慮多查詢，也沒有考慮查詢的相似性。主要考慮了三部分的能量，即數據源到數據處理節點的能量、數據處理節點到基站的能量和基站發送數據處理函數到數據處理節點的能量。然后以這三部分能量和的最小化來求出數據處理節點的坐標。因為能量消耗的多少與數據量有關，這里雖然考慮了總的能量關系，但是還不能達到能量最小，因為它比幾何中心的方法增加了從數據源到數據處理節點的距離，且這部分的數據量比較大，所以這種方法增加了能量的消耗。

采用以幾何中心作為數據處理節點的方法，可以大大減少從數據收集節點到數據處理節點的距離，數據處理節點到基站的距離雖然有所增加，但是這段距離傳輸的是處理后的數據，相比處理前的數據量大為減少，所以總的能耗就會減少。

本文針對無線傳感器網絡中存在的多查詢情況，提出了一種節能的數據查詢方法，經分析表明，該方法能夠有效地減少數據的傳輸量，從而降低網絡的傳輸能耗。

參考文獻

[1]蔚趙春，周水庚，關佶紅.無線傳感器網絡中數據存儲與訪問研究進展[J].電子學報，2008，36(10)：2001-2010.

[2]陳穎文，徐明，虞萬榮.無線傳感器網絡多頻率查詢的節能優化[J].電子學報，2008，36(4)：701-708.

[3]蔚趙春，周水庚，肖斌.無線傳感器網絡中自適應數據存取[J].軟件學報，2008，19(1)：103-115.

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

[5]陳穎文，徐明，吳一.無線傳感器網絡網內數據處理節點的優化選取[J].軟件學報，2007，18(12)：3104-3114.

[6]XIANG Shi Li，ZHOU Yong Luan，HOCK B L，et al.Query allocation in wireless sensor networks with multiple base station[J].Lecture Notes in Computer Science，2009(5463)：107-122.

[7]XIANG S，LIM H B，TAN K L，et al.Similarity-aware query allocation in sensor networks with multiple base stations.In：Proc.of DMSN.2007.

[8]LING Hui，ZNATI T.Similarity based optimization for multiple query processing in wireless sensor networks[J].Lecture Notes in Computer Science，2009，5516：117-130.

[9]TRIGONI N，YAO Yong，DEMERS A，et al.Multi-query optimization for sensor networks[J].Lecture Notes in Computer Science，2005，3560：307-321.

[10]AKYILDIZ l，SU W，SANKARASUBRAMANIAM Y，et al.A survey on sensor networks.IEEE Communications Magazine，2002，40(8)：102-114.

[11]付雄，王汝傳，鄧松.無線傳感器網絡中一種能量有效的數據存儲方法[J].計算機研究與發展，2009，46(12)：2111-2116.

[12]楊挺，孫雨耕，王燕琳，等.無線傳感器網絡中數據融合機制的能量有效性研究[J].計算機應用研究，2007，24(10)：95-98.