摘 要： 提出了一個無線傳感器網(wǎng)絡多查詢的節(jié)能優(yōu)化方案。該方案通過建立相似查詢判斷算法把多查詢中的相似查詢分為一組，并在每一組找一個能使傳輸能耗達到最小的中繼節(jié)點作為處理節(jié)點。組內(nèi)節(jié)點的數(shù)據(jù)都傳送到該處理節(jié)點，并由該節(jié)點利用數(shù)據(jù)處理函數(shù)處理數(shù)據(jù),然后再傳到基站。這樣就減少了網(wǎng)絡中數(shù)據(jù)的傳輸量，從而有效地節(jié)省了網(wǎng)絡的能量，達到能量的最大化利用。
關鍵詞： 無線傳感器網(wǎng)絡；多查詢；相似查詢；處理節(jié)點；能量
無線傳感器網(wǎng)絡是由一組在地理上廣泛分布、相互之間能夠利用無線信道進行通信的傳感器節(jié)點組成的。由于每個節(jié)點都可以作為接收節(jié)點也可以作為發(fā)送節(jié)點，并可以與多個其他節(jié)點進行協(xié)作通信，因此，無線傳感器網(wǎng)絡廣泛應用于商業(yè)、電信、環(huán)境、軍事等領域。
從無線傳感器中獲得數(shù)據(jù)主要是靠查詢，通過查詢才能得到想知道的數(shù)據(jù)。目前對查詢的研究方案很多，但是很少有考慮到多查詢的相似性。這樣傳感器網(wǎng)絡就會多收發(fā)很多數(shù)據(jù)，造成能量消耗。由于能量是影響網(wǎng)絡壽命的關鍵因素，并且CPU的能耗要遠遠小于數(shù)據(jù)傳輸?shù)哪芎腫1]。因此數(shù)據(jù)傳輸在無線傳感器網(wǎng)絡的能耗中占據(jù)主體地位。如何進行相似查詢的處理，如何減少數(shù)據(jù)傳輸?shù)哪芎亩际羌庇诮鉀Q的重要問題。
針對以上問題，本文提出了一個無線傳感器網(wǎng)絡多查詢的節(jié)能優(yōu)化方案。在基站同時存在多個查詢時，提出的方案通過建立相似查詢算法來判斷相似的查詢，并將相似的查詢分為一組。然后在每一組中找一個能使傳輸能耗達到最小的中繼節(jié)點作為處理節(jié)點。組內(nèi)節(jié)點的數(shù)據(jù)都傳送到該處理節(jié)點，并在該節(jié)點利用已知的數(shù)據(jù)處理函數(shù)來處理數(shù)據(jù)。這樣就減少了網(wǎng)絡中數(shù)據(jù)的傳輸量。從而有效地節(jié)省了網(wǎng)絡的能量，達到能量的最大化利用。
1 相關研究
目前國內(nèi)對這方面的研究很少，參考文獻[2]中針對多個查詢頻率的不同，提出了一種節(jié)能的方法，該方法雖然有效地減少了能量的消耗，但是返回數(shù)據(jù)的準確性較差，返回數(shù)據(jù)也不夠及時，同時也沒有考慮查詢的相似性。參考文獻[3]和參考文獻[4]都是以數(shù)據(jù)為中心的方法，但都沒有考慮到查詢的相似性。參考文獻[5]提出了一種低能耗的數(shù)據(jù)處理節(jié)點選取策略，但是該策略只是在網(wǎng)絡密度低時比較實用。參考文獻[6，7]則在多基站下來進行相似查詢的分配。以上這些文獻都沒有考慮在基站同時存在多個查詢時的相似性。
2 無線傳感器網(wǎng)絡多查詢的節(jié)能優(yōu)化方案
在無線傳感器網(wǎng)絡中同時存在多個查詢時[8-10]，為了減少數(shù)據(jù)的傳輸量，降低網(wǎng)絡的能量消耗，提高數(shù)據(jù)傳輸效率，提出了一種通過在多查詢中找相似查詢和處理節(jié)點的高效節(jié)能方案。方案包括系統(tǒng)模型、相似查詢的判斷及分組和數(shù)據(jù)處理節(jié)點的選取幾個部分。
2.1 系統(tǒng)模型的建立
系統(tǒng)符合以下假設條件：
（1）基站能量不受限制，并且知道網(wǎng)絡中各節(jié)點的位置信息。網(wǎng)內(nèi)節(jié)點也知道自己的坐標信息。
（2）若節(jié)點i和j在相互通信范圍內(nèi)，則i和j可以直接傳輸數(shù)據(jù)，若二者不能直接通信，則其傳輸路徑長度記為Dis(i，j)，也就是i和j之間的跳數(shù)。
（3）所有的查詢都持續(xù)一段時間。
（4）每個傳感器節(jié)點都具有一定的處理能力,可以進行數(shù)據(jù)的處理。
（5）把無線傳感器網(wǎng)絡看做規(guī)則的網(wǎng)狀結構，并將這個網(wǎng)絡抽象為圖G=(V,E)，其中V=v1，v2，…，vn表示節(jié)點集合。節(jié)點vi的位置為(xi，yi)，E表示邊集合，若vi，vj在通信范圍內(nèi)就構成了一條邊。它們之間的距離表示為Dis(i，j)。
如圖1所示，基站B是坐標的原點（0，0），橫向右為X軸正向，向下為Y軸正向。圖中基站有3個查詢分布在網(wǎng)絡中，分別是S1、S2和S3，根據(jù)算法判斷出S1與S2相似，則把他們分為一組，再找到該組的數(shù)據(jù)處理節(jié)點P1。S3表示沒有相似的，自成一組，找到它的處理節(jié)點為P2。在進行數(shù)據(jù)傳輸時，因為數(shù)據(jù)處理函數(shù)根據(jù)實際情況而不同，所以這里只是假設函數(shù)已知并可以在所有的傳感器節(jié)點上執(zhí)行。
2.2 相似查詢的判斷及分組
（1）查詢相似的判斷
每個查詢都包括要查詢的范圍和要查詢的信息（即屬性）。判斷兩個查詢相似是基于位置信息來判斷相似的。
算法思想：對于包含m和n個節(jié)點的任意兩個查詢qi和qj，掃描每個查詢節(jié)點的坐標，然后進行比較，一旦這兩個查詢有相同的坐標，則這兩個查詢相似。
算法描述如下：
Similar(qi，qj)
{
Int i，j；//i和j分別表示qi和qj中節(jié)點
For(i=1→m)
For(j=1→n)
If(i坐標=j坐標)
則qi和qj相似。
}
（2）相似查詢的分組
算法思想：先將k個查詢(q1，q2，…，qk)初始化為k個組，每個查詢對應一個組，分別用b1，b2，…，bk表示。然后比較這些組，將所有相似的查詢都分為一組。
算法描述如下：
Group(b1，b2，…，bk)
{
n=k；
for(i=1→k-1)
{
for(j=i+1→k)
{
If(similar(bi，bj)成立)
{
則 bi←bj；清空bj；
For(m=j→k)
bm←bm+1；
k--；
}
}
if(k<n) Group(b1，b2，…，bk)；
}
}
通過以上算法將基站的查詢分為k1(k1≤k)個組，且每個組內(nèi)的查詢都是基于地理位置相似的。
2.3 數(shù)據(jù)處理節(jié)點的選取
將基站的查詢分組后，下面分別在這k1個組找到相應的數(shù)據(jù)處理節(jié)點。前面說過，節(jié)點離數(shù)據(jù)源越近，越能夠節(jié)省傳輸?shù)哪芰縖11-12]。所以把組內(nèi)的幾何中心作為該組的數(shù)據(jù)處理節(jié)點。這樣組內(nèi)節(jié)點到達數(shù)據(jù)處理節(jié)點的平均距離就達到最小，消耗的能量也就達到最小。
具體選法如下：
假設組內(nèi)共有m個節(jié)點，組內(nèi)節(jié)點分布均勻。設數(shù)據(jù)處理節(jié)點坐標為P（x，y），則數(shù)據(jù)處理節(jié)點的坐標為：
for(i=1…m)
{
int xmax，xmin；
xmax=x1；
xmin=x1；
if(xi>xmax)
xmax=xi；
if(xi<xmin)
xmin=xi；
}
同理可以求得min(y1，…，ym)和max(y1，…，ym)。
數(shù)據(jù)處理節(jié)點的位置坐標為（x，y），即組內(nèi)節(jié)點的數(shù)據(jù)都傳送到該處理節(jié)點，并在該節(jié)點利用已知的數(shù)據(jù)處理函數(shù)來處理數(shù)據(jù)，然后再傳送給基站。這樣就減少了網(wǎng)絡中數(shù)據(jù)的傳輸量。從而有效地節(jié)省了網(wǎng)絡的能量，達到能量的最大化利用。
3 效率與性能分析
對于圖1所示的網(wǎng)絡模型，設網(wǎng)內(nèi)節(jié)點數(shù)為n，S1與S2相似，則S1與S2分一組為P1，由圖可以知道組內(nèi)節(jié)點的坐標，則可以算出組內(nèi)數(shù)據(jù)處理節(jié)點的位置為P1(6，3)，設節(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。
如果不對相似查詢進行處理，即所有節(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é)點的坐標。因為能量消耗的多少與數(shù)據(jù)量有關，這里雖然考慮了總的能量關系，但是還不能達到能量最小，因為它比幾何中心的方法增加了從數(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)絡中存在的多查詢情況，提出了一種節(jié)能的數(shù)據(jù)查詢方法，經(jīng)分析表明，該方法能夠有效地減少數(shù)據(jù)的傳輸量，從而降低網(wǎng)絡的傳輸能耗。
參考文獻
[1] 蔚趙春，周水庚，關佶紅.無線傳感器網(wǎng)絡中數(shù)據(jù)存儲與訪問研究進展[J].電子學報，2008，36(10)：2001-2010.
[2] 陳穎文，徐明，虞萬榮.無線傳感器網(wǎng)絡多頻率查詢的節(jié)能優(yōu)化[J].電子學報，2008，36(4)：701-708.
[3] 蔚趙春，周水庚，肖斌.無線傳感器網(wǎng)絡中自適應數(shù)據(jù)存取[J].軟件學報，2008，19(1)：103-115.
[4] 郭龍江，李建中，李貴林.無線傳感器網(wǎng)絡環(huán)境下時-空查詢處理方法[J].軟件學報，2006，17(4)：794-805.
[5] 陳穎文，徐明，吳一.無線傳感器網(wǎng)絡網(wǎng)內(nèi)數(shù)據(jù)處理節(jié)點的優(yōu)化選取[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] 付雄，王汝傳，鄧松.無線傳感器網(wǎng)絡中一種能量有效的數(shù)據(jù)存儲方法[J].計算機研究與發(fā)展，2009，46(12)：2111-2116.
[12] 楊挺，孫雨耕，王燕琳，等.無線傳感器網(wǎng)絡中數(shù)據(jù)融合機制的能量有效性研究[J].計算機應用研究，2007，24(10)：95-98.