無線傳感器網(wǎng)絡(luò)多查詢的節(jié)能優(yōu)化*

申少輝，王曉明

（暨南大學(xué) 計算機(jī)系，廣東 廣州510632）

無線傳感器網(wǎng)絡(luò)是由一組在地理上廣泛分布、相互之間能夠利用無線信道進(jìn)行通信的傳感器節(jié)點組成的。由于每個節(jié)點都可以作為接收節(jié)點也可以作為發(fā)送節(jié)點，并可以與多個其他節(jié)點進(jìn)行協(xié)作通信，因此，無線傳感器網(wǎng)絡(luò)廣泛應(yīng)用于商業(yè)、電信、環(huán)境、軍事等領(lǐng)域。

從無線傳感器中獲得數(shù)據(jù)主要是靠查詢，通過查詢才能得到想知道的數(shù)據(jù)。目前對查詢的研究方案很多，但是很少有考慮到多查詢的相似性。這樣傳感器網(wǎng)絡(luò)就會多收發(fā)很多數(shù)據(jù)，造成能量消耗。由于能量是影響網(wǎng)絡(luò)壽命的關(guān)鍵因素，并且CPU的能耗要遠(yuǎn)遠(yuǎn)小于數(shù)據(jù)傳輸?shù)哪芎腫1]。因此數(shù)據(jù)傳輸在無線傳感器網(wǎng)絡(luò)的能耗中占據(jù)主體地位。如何進(jìn)行相似查詢的處理，如何減少數(shù)據(jù)傳輸?shù)哪芎亩际羌庇诮鉀Q的重要問題。

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

1 相關(guān)研究

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

2 無線傳感器網(wǎng)絡(luò)多查詢的節(jié)能優(yōu)化方案

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

2.1 系統(tǒng)模型的建立

系統(tǒng)符合以下假設(shè)條件：

（1）基站能量不受限制，并且知道網(wǎng)絡(luò)中各節(jié)點的位置信息。網(wǎng)內(nèi)節(jié)點也知道自己的坐標(biāo)信息。

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

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

（4）每個傳感器節(jié)點都具有一定的處理能力,可以進(jìn)行數(shù)據(jù)的處理。

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

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

2.2 相似查詢的判斷及分組

（1）查詢相似的判斷

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

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

算法描述如下：

（2）相似查詢的分組

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

算法描述如下：

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

2.3 數(shù)據(jù)處理節(jié)點的選取

將基站的查詢分組后，下面分別在這k1個組找到相應(yīng)的數(shù)據(jù)處理節(jié)點。前面說過，節(jié)點離數(shù)據(jù)源越近，越能夠節(jié)省傳輸?shù)哪芰縖11-12]。所以把組內(nèi)的幾何中心作為該組的數(shù)據(jù)處理節(jié)點。這樣組內(nèi)節(jié)點到達(dá)數(shù)據(jù)處理節(jié)點的平均距離就達(dá)到最小，消耗的能量也就達(dá)到最小。

具體選法如下：

假設(shè)組內(nèi)共有m個節(jié)點，組內(nèi)節(jié)點分布均勻。設(shè)數(shù)據(jù)處理節(jié)點坐標(biāo)為P（x，y），則數(shù)據(jù)處理節(jié)點的坐標(biāo)為：

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

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

數(shù)據(jù)處理節(jié)點的位置坐標(biāo)為（x，y），即組內(nèi)節(jié)點的數(shù)據(jù)都傳送到該處理節(jié)點，并在該節(jié)點利用已知的數(shù)據(jù)處理函數(shù)來處理數(shù)據(jù)，然后再傳送給基站。這樣就減少了網(wǎng)絡(luò)中數(shù)據(jù)的傳輸量。從而有效地節(jié)省了網(wǎng)絡(luò)的能量，達(dá)到能量的最大化利用。

3 效率與性能分析

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

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

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

采用以幾何中心作為數(shù)據(jù)處理節(jié)點的方法，可以大大減少從數(shù)據(jù)收集節(jié)點到數(shù)據(jù)處理節(jié)點的距離，數(shù)據(jù)處理節(jié)點到基站的距離雖然有所增加，但是這段距離傳輸?shù)氖翘幚砗蟮臄?shù)據(jù)，相比處理前的數(shù)據(jù)量大為減少，所以總的能耗就會減少。

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

參考文獻(xiàn)

[1]蔚趙春，周水庚，關(guān)佶紅.無線傳感器網(wǎng)絡(luò)中數(shù)據(jù)存儲與訪問研究進(jìn)展[J].電子學(xué)報，2008，36(10)：2001-2010.

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

[3]蔚趙春，周水庚，肖斌.無線傳感器網(wǎng)絡(luò)中自適應(yīng)數(shù)據(jù)存取[J].軟件學(xué)報，2008，19(1)：103-115.

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

[5]陳穎文，徐明，吳一.無線傳感器網(wǎng)絡(luò)網(wǎng)內(nèi)數(shù)據(jù)處理節(jié)點的優(yōu)化選取[J].軟件學(xué)報，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]付雄，王汝傳，鄧松.無線傳感器網(wǎng)絡(luò)中一種能量有效的數(shù)據(jù)存儲方法[J].計算機(jī)研究與發(fā)展，2009，46(12)：2111-2116.

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