摘  要： 提出了一個(gè)無線傳感器網(wǎng)絡(luò)多查詢的節(jié)能優(yōu)化方案。該方案通過建立相似查詢判斷算法把多查詢中的相似查詢分為一組，并在每一組找一個(gè)能使傳輸能耗達(dá)到最小的中繼節(jié)點(diǎn)作為處理節(jié)點(diǎn)。組內(nèi)節(jié)點(diǎn)的數(shù)據(jù)都傳送到該處理節(jié)點(diǎn)，并由該節(jié)點(diǎn)利用數(shù)據(jù)處理函數(shù)處理數(shù)據(jù),然后再傳到基站。這樣就減少了網(wǎng)絡(luò)中數(shù)據(jù)的傳輸量，從而有效地節(jié)省了網(wǎng)絡(luò)的能量，達(dá)到能量的最大化利用。
關(guān)鍵詞： 無線傳感器網(wǎng)絡(luò)；多查詢；相似查詢；處理節(jié)點(diǎn)；能量

    無線傳感器網(wǎng)絡(luò)是由一組在地理上廣泛分布、相互之間能夠利用無線信道進(jìn)行通信的傳感器節(jié)點(diǎn)組成的。由于每個(gè)節(jié)點(diǎn)都可以作為接收節(jié)點(diǎn)也可以作為發(fā)送節(jié)點(diǎn)，并可以與多個(gè)其他節(jié)點(diǎn)進(jìn)行協(xié)作通信，因此，無線傳感器網(wǎng)絡(luò)廣泛應(yīng)用于商業(yè)、電信、環(huán)境、軍事等領(lǐng)域。
    從無線傳感器中獲得數(shù)據(jù)主要是靠查詢，通過查詢才能得到想知道的數(shù)據(jù)。目前對(duì)查詢的研究方案很多，但是很少有考慮到多查詢的相似性。這樣傳感器網(wǎng)絡(luò)就會(huì)多收發(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的重要問題。
    針對(duì)以上問題，本文提出了一個(gè)無線傳感器網(wǎng)絡(luò)多查詢的節(jié)能優(yōu)化方案。在基站同時(shí)存在多個(gè)查詢時(shí)，提出的方案通過建立相似查詢算法來判斷相似的查詢，并將相似的查詢分為一組。然后在每一組中找一個(gè)能使傳輸能耗達(dá)到最小的中繼節(jié)點(diǎn)作為處理節(jié)點(diǎn)。組內(nèi)節(jié)點(diǎn)的數(shù)據(jù)都傳送到該處理節(jié)點(diǎn)，并在該節(jié)點(diǎn)利用已知的數(shù)據(jù)處理函數(shù)來處理數(shù)據(jù)。這樣就減少了網(wǎng)絡(luò)中數(shù)據(jù)的傳輸量。從而有效地節(jié)省了網(wǎng)絡(luò)的能量，達(dá)到能量的最大化利用。
1 相關(guān)研究
    目前國(guó)內(nèi)對(duì)這方面的研究很少，參考文獻(xiàn)[2]中針對(duì)多個(gè)查詢頻率的不同，提出了一種節(jié)能的方法，該方法雖然有效地減少了能量的消耗，但是返回?cái)?shù)據(jù)的準(zhǔn)確性較差，返回?cái)?shù)據(jù)也不夠及時(shí)，同時(shí)也沒有考慮查詢的相似性。參考文獻(xiàn)[3]和參考文獻(xiàn)[4]都是以數(shù)據(jù)為中心的方法，但都沒有考慮到查詢的相似性。參考文獻(xiàn)[5]提出了一種低能耗的數(shù)據(jù)處理節(jié)點(diǎn)選取策略，但是該策略只是在網(wǎng)絡(luò)密度低時(shí)比較實(shí)用。參考文獻(xiàn)[6，7]則在多基站下來進(jìn)行相似查詢的分配。以上這些文獻(xiàn)都沒有考慮在基站同時(shí)存在多個(gè)查詢時(shí)的相似性。
2 無線傳感器網(wǎng)絡(luò)多查詢的節(jié)能優(yōu)化方案
    在無線傳感器網(wǎng)絡(luò)中同時(shí)存在多個(gè)查詢時(shí)[8-10]，為了減少數(shù)據(jù)的傳輸量，降低網(wǎng)絡(luò)的能量消耗，提高數(shù)據(jù)傳輸效率，提出了一種通過在多查詢中找相似查詢和處理節(jié)點(diǎn)的高效節(jié)能方案。方案包括系統(tǒng)模型、相似查詢的判斷及分組和數(shù)據(jù)處理節(jié)點(diǎn)的選取幾個(gè)部分。
2.1 系統(tǒng)模型的建立
    系統(tǒng)符合以下假設(shè)條件：
    （1）基站能量不受限制，并且知道網(wǎng)絡(luò)中各節(jié)點(diǎn)的位置信息。網(wǎng)內(nèi)節(jié)點(diǎn)也知道自己的坐標(biāo)信息。
    （2）若節(jié)點(diǎn)i和j在相互通信范圍內(nèi)，則i和j可以直接傳輸數(shù)據(jù)，若二者不能直接通信，則其傳輸路徑長(zhǎng)度記為Dis(i，j)，也就是i和j之間的跳數(shù)。
    （3）所有的查詢都持續(xù)一段時(shí)間。
    （4）每個(gè)傳感器節(jié)點(diǎn)都具有一定的處理能力,可以進(jìn)行數(shù)據(jù)的處理。
    （5）把無線傳感器網(wǎng)絡(luò)看做規(guī)則的網(wǎng)狀結(jié)構(gòu)，并將這個(gè)網(wǎng)絡(luò)抽象為圖G=(V,E)，其中V=v1，v2，…，vn表示節(jié)點(diǎn)集合。節(jié)點(diǎn)vi的位置為(xi，yi)，E表示邊集合，若vi，vj在通信范圍內(nèi)就構(gòu)成了一條邊。它們之間的距離表示為Dis(i，j)。
    如圖1所示，基站B是坐標(biāo)的原點(diǎn)（0，0），橫向右為X軸正向，向下為Y軸正向。圖中基站有3個(gè)查詢分布在網(wǎng)絡(luò)中，分別是S1、S2和S3，根據(jù)算法判斷出S1與S2相似，則把他們分為一組，再找到該組的數(shù)據(jù)處理節(jié)點(diǎn)P1。S3表示沒有相似的，自成一組，找到它的處理節(jié)點(diǎn)為P2。在進(jìn)行數(shù)據(jù)傳輸時(shí)，因?yàn)閿?shù)據(jù)處理函數(shù)根據(jù)實(shí)際情況而不同，所以這里只是假設(shè)函數(shù)已知并可以在所有的傳感器節(jié)點(diǎn)上執(zhí)行。

2.2 相似查詢的判斷及分組
    （1）查詢相似的判斷
    每個(gè)查詢都包括要查詢的范圍和要查詢的信息（即屬性）。判斷兩個(gè)查詢相似是基于位置信息來判斷相似的。
    算法思想：對(duì)于包含m和n個(gè)節(jié)點(diǎn)的任意兩個(gè)查詢qi和qj，掃描每個(gè)查詢節(jié)點(diǎn)的坐標(biāo)，然后進(jìn)行比較，一旦這兩個(gè)查詢有相同的坐標(biāo)，則這兩個(gè)查詢相似。
    算法描述如下：
    Similar(qi，qj)
    {
        Int i，j；//i和j分別表示qi和qj中節(jié)點(diǎn)
        For(i=1→m)
            For(j=1→n)
                If(i坐標(biāo)=j坐標(biāo))
                    則qi和qj相似。
    }
    （2）相似查詢的分組
    算法思想：先將k個(gè)查詢(q1，q2，…，qk)初始化為k個(gè)組，每個(gè)查詢對(duì)應(yīng)一個(gè)組，分別用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)個(gè)組，且每個(gè)組內(nèi)的查詢都是基于地理位置相似的。
2.3 數(shù)據(jù)處理節(jié)點(diǎn)的選取
    將基站的查詢分組后，下面分別在這k1個(gè)組找到相應(yīng)的數(shù)據(jù)處理節(jié)點(diǎn)。前面說過，節(jié)點(diǎn)離數(shù)據(jù)源越近，越能夠節(jié)省傳輸?shù)哪芰縖11-12]。所以把組內(nèi)的幾何中心作為該組的數(shù)據(jù)處理節(jié)點(diǎn)。這樣組內(nèi)節(jié)點(diǎn)到達(dá)數(shù)據(jù)處理節(jié)點(diǎn)的平均距離就達(dá)到最小，消耗的能量也就達(dá)到最小。
    具體選法如下：
    假設(shè)組內(nèi)共有m個(gè)節(jié)點(diǎn)，組內(nèi)節(jié)點(diǎn)分布均勻。設(shè)數(shù)據(jù)處理節(jié)點(diǎn)坐標(biāo)為P（x，y），則數(shù)據(jù)處理節(jié)點(diǎn)的坐標(biāo)為：
    
    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é)點(diǎn)的位置坐標(biāo)為（x，y），即組內(nèi)節(jié)點(diǎn)的數(shù)據(jù)都傳送到該處理節(jié)點(diǎn)，并在該節(jié)點(diǎn)利用已知的數(shù)據(jù)處理函數(shù)來處理數(shù)據(jù)，然后再傳送給基站。這樣就減少了網(wǎng)絡(luò)中數(shù)據(jù)的傳輸量。從而有效地節(jié)省了網(wǎng)絡(luò)的能量，達(dá)到能量的最大化利用。
3 效率與性能分析
    對(duì)于圖1所示的網(wǎng)絡(luò)模型，設(shè)網(wǎng)內(nèi)節(jié)點(diǎn)數(shù)為n，S1與S2相似，則S1與S2分一組為P1，由圖可以知道組內(nèi)節(jié)點(diǎn)的坐標(biāo)，則可以算出組內(nèi)數(shù)據(jù)處理節(jié)點(diǎn)的位置為P1(6，3)，設(shè)節(jié)點(diǎn)產(chǎn)生數(shù)據(jù)的速率相等且一定為r，單位數(shù)據(jù)大小為s。用本文的方法傳輸數(shù)據(jù)在一定時(shí)間T內(nèi)組內(nèi)節(jié)點(diǎn)到數(shù)據(jù)處理節(jié)點(diǎn)傳輸數(shù)據(jù)消耗的能量為C=19rsT，則在數(shù)據(jù)處理節(jié)點(diǎn)總的數(shù)據(jù)量大小為14rsT，在P1節(jié)點(diǎn)經(jīng)過數(shù)據(jù)處理后，因?yàn)檫@兩個(gè)查詢有重合數(shù)據(jù)，所以在P1節(jié)點(diǎn)發(fā)送出的總數(shù)據(jù)大小為10rsT。則從P1點(diǎn)傳輸數(shù)據(jù)到基站所需的能量為90rsT，即該方案總的能量大小為C1=109rsT。
    如果不對(duì)相似查詢進(jìn)行處理，即所有節(jié)點(diǎn)產(chǎn)生的數(shù)據(jù)直接發(fā)送給基站，則這樣的能量消耗為C2=123rsT。由此可見使用該方案可以很有效地減少傳輸數(shù)據(jù)所消耗的能量。
    參考文獻(xiàn)[5]提出一種找數(shù)據(jù)處理節(jié)點(diǎn)的方法，主要針對(duì)單查詢情況，并沒有考慮多查詢，也沒有考慮查詢的相似性。主要考慮了三部分的能量，即數(shù)據(jù)源到數(shù)據(jù)處理節(jié)點(diǎn)的能量、數(shù)據(jù)處理節(jié)點(diǎn)到基站的能量和基站發(fā)送數(shù)據(jù)處理函數(shù)到數(shù)據(jù)處理節(jié)點(diǎn)的能量。然后以這三部分能量和的最小化來求出數(shù)據(jù)處理節(jié)點(diǎn)的坐標(biāo)。因?yàn)槟芰肯牡亩嗌倥c數(shù)據(jù)量有關(guān)，這里雖然考慮了總的能量關(guān)系，但是還不能達(dá)到能量最小，因?yàn)樗葞缀沃行牡姆椒ㄔ黾恿藦臄?shù)據(jù)源到數(shù)據(jù)處理節(jié)點(diǎn)的距離，且這部分的數(shù)據(jù)量比較大，所以這種方法增加了能量的消耗。
    采用以幾何中心作為數(shù)據(jù)處理節(jié)點(diǎn)的方法，可以大大減少?gòu)臄?shù)據(jù)收集節(jié)點(diǎn)到數(shù)據(jù)處理節(jié)點(diǎn)的距離，數(shù)據(jù)處理節(jié)點(diǎn)到基站的距離雖然有所增加，但是這段距離傳輸?shù)氖翘幚砗蟮臄?shù)據(jù)，相比處理前的數(shù)據(jù)量大為減少，所以總的能耗就會(huì)減少。
    本文針對(duì)無線傳感器網(wǎng)絡(luò)中存在的多查詢情況，提出了一種節(jié)能的數(shù)據(jù)查詢方法，經(jīng)分析表明，該方法能夠有效地減少數(shù)據(jù)的傳輸量，從而降低網(wǎng)絡(luò)的傳輸能耗。
參考文獻(xiàn)
[1] 蔚趙春，周水庚，關(guān)佶紅.無線傳感器網(wǎng)絡(luò)中數(shù)據(jù)存儲(chǔ)與訪問研究進(jìn)展[J].電子學(xué)報(bào)，2008，36(10)：2001-2010.
[2] 陳穎文，徐明，虞萬榮.無線傳感器網(wǎng)絡(luò)多頻率查詢的節(jié)能優(yōu)化[J].電子學(xué)報(bào)，2008，36(4)：701-708.
[3] 蔚趙春，周水庚，肖斌.無線傳感器網(wǎng)絡(luò)中自適應(yīng)數(shù)據(jù)存取[J].軟件學(xué)報(bào)，2008，19(1)：103-115.
[4] 郭龍江，李建中，李貴林.無線傳感器網(wǎng)絡(luò)環(huán)境下時(shí)-空查詢處理方法[J].軟件學(xué)報(bào)，2006，17(4)：794-805.
[5] 陳穎文，徐明，吳一.無線傳感器網(wǎng)絡(luò)網(wǎng)內(nèi)數(shù)據(jù)處理節(jié)點(diǎn)的優(yōu)化選取[J].軟件學(xué)報(bào)，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ù)存儲(chǔ)方法[J].計(jì)算機(jī)研究與發(fā)展，2009，46(12)：2111-2116.
[12] 楊挺，孫雨耕，王燕琳，等.無線傳感器網(wǎng)絡(luò)中數(shù)據(jù)融合機(jī)制的能量有效性研究[J].計(jì)算機(jī)應(yīng)用研究，2007，24(10)：95-98.