容忍节点失效的传感器网络空间范围查询算法.doc

第11期刘亮等：容忍节点失效的传感器网络空间范围查询算法11容忍节点失效的传感器网络空间范围查询算法刘亮，秦小麟，戴华，沈佳佳(南京航空航天大学 信息科学与技术学院，江苏 南京 210016)摘 要：提出了一种容忍节点失效的空间范围查询处理算法GSA。给出了理论上最节省能量的网格大小设置。提出了一种基于网格的查询结果收集调度策略，以避免查询结果收集过程中的消息碰撞问题。系统地分析了算法在不同节点密度、节点失效概率和查询区域大小条件下的查询成功率，以及不同节点密度、查询消息大小、感知数据大小、查询区域大小、节点失效概率条件下的能量消耗。理论和实验表明，在多数情况下，GSA算法优于现有的IWQE算法。关键词：无线传感器网络；空间查询；容忍节点失效；网格中图分类号：TP393 文献标识码：A 文章编号：1000-436X(2008)11-0002-10GSA: node failures tolerent spatial window query processing algorithm in wireless sensor networksLIU Liang, QIN Xiao-lin, DAI Hua, SHEN Jia-jia(Colledge of Information Science & Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China)Abstract: A node failures tolerent spatial window query processing algorithm called GSA was proposed. The grid size parameter was studied and a grid-based data collection schedule scheme to avoid the message collisions in the process of data collection was proposed. Finally, the influence of node density, the probability of node failure, query region size on the success rate of a query and the influence of node density, query message size, sensed data size, query region size, the probability of node failure on energy consumption were analysed. Analytical and experimental results show that in most cases GSA outperforms IWQE.Key words: wireless sensor networks; spatial query; node failures tolerance; grid1 引言收稿日期：2008-06-20；修回日期：2008-10-09基金项目：国家自然科学基金资助项目(60673127)；国家高技术研究发展计划（“863”计划）基金资助项目(2007AA01Z404)Foundation Items: The National Natural Science Foundation of China(60673127); The National High Technology Research Program of China(863 Program) (2007AA01Z404)无线传感器网络通常由基站和大量传感器节点组成。基站用于接收用户查询请求，并将查询发送到网络中。传感器节点利用分布式信息处理和网内处理等技术处理查询，然后按多跳路由方式将查询结果发回基站。无线传感器网络不同于其他的网络，它是以数据为中心的网络，大部分传感器网络上的查询是空间相关的，如获得南京长江大桥近一个月内的车流量信息，玄武湖的平均温度等。另外，由于传感器节点的能量由电池供应且通常无法更换，能量十分有限。因此，能量高效的空间查询处理技术是传感器网络数据管理的重要研究内容。现有的传感器网络环境下的空间查询处理算法建立在特定的下层构造(infrastructure)之上1。如TinyDB2将传感器网络组织成一种树型结构，传感器网络中的空间索引技术3将传感器网络组织成一棵分布式的R树等。由于受到节点能源供应不足、节点休眠以及周围环境等因素的影响，传感器节点常无法正常工作，节点与节点之间的通信链路也频繁失效。再加上节点移动的影响，导致这样的下层构造极不稳定，查询结果极易丢失。因此，为了解决上述问题，需研究不受节点失效、通信链路失效和节点移动因素影响的查询处理技术。本文提出了一种不受这些因素影响的空间窗口查询处理算法（GSA，grid-based spatial window query processing algorithm），它将查询区域划分为若干个网格。首先利用位置路由协议将查询消息发送到查询区域内的一个网格。该网格内的一个节点（网格代表节点）收到查询消息后收集该网格的查询结果并计算出部分查询结果，将查询消息和部分查询结果发送至下一个网格。如此继续，到达查询区域的最后一个网格后，该网格的代表节点利用位置路由协议将最终的查询结果返回至查询发起节点。由于算法的查询处理过程不依赖于特定的下层构造，所以，GSA不易受通信链路失效和节点移动因素影响。另外，GSA能保证网格内的所有节点均能收到上一网格发送的部分查询结果和所在网格的其他节点发送的查询结果。因此，只要网格内的节点不全部失效，GSA能够继续进行数据的收集。本文给出了理论上最节省能量的网格大小设置，提出了一种基于网格的查询结果收集调度策略，以避免查询结果收集过程中的消息碰撞问题。并对算法的性能进行了系统的理论和实验分析。分析结果表明，在多数情况下，本文的算法优于现有的IWQE算法。2 相关工作在TinyDB2和FullFlood4中，查询发起节点将查询消息泛洪到网络内的所有节点，形成一棵分发路由树（spanning routing tree）。查询区域内的节点收到查询消息后，将查询结果沿查询消息泛洪过程中形成的自己到查询发起节点的路径返回查询发起节点。在文献3中，在建立的分发路由树的基础之上，生成一棵分布式的R树。节点收到查询消息后，仅将查询消息发送到MBR（最小边界矩形）与查询区域相交的子结点，这样无需访问不在查询区域内的子树，减少了能量的消耗。在文献4中，针对采用本地存储方式的传感器网络，提出了一个将时空查询分为两阶段处理的通用框架STWin及该框架下的两种算法：STWinFlood和STWinDepth。相比传统的泛洪式算法（FullFlood），这两种算法仅将查询消息发送到查询区域内而无需在整个网络内广播，减少了能量的消耗。实验证明，在大多情况下，前两种算法的能量消耗均小于泛洪式算法，仅在查询区域较大，网络节点密度较小的情况下，泛洪式算法较优。文献5给出了三种算法的能量消耗的近似公式和理论推导。文献6利用传感器冗余和数据的空间相关性，对STWin算法的第二阶段进行了改进，使得在满足数据质量要求的前提下，减少冗余数据的发送，降低了能量的消耗。文献7中指出在不同查询的数目、事件发生的概率、节点密度、事件类型数目的条件下，应采取不同的数据存储方式，并提出了基于CM-DCS(以数据为中心的中心映射存储策略)的时空查询处理方法，对于适于采用以数据为中心存储的网络，该方法更优。文献1提出了一种基于路线（itinerary-based）的空间窗口查询算法。它先将查询发送到查询区域内的一个节点，然后从该节点出发，沿查询区域内的一条路线进行查询处理，查询路线上的节点（查询节点）将查询广播到邻居节点（数据节点）、收集邻居节点的查询结果和对查询结果的聚集，并将聚集后的结果发给查询路线上的下一个节点，如此继续。到达查询路线上的最后一个节点后，该节点将最终的查询结果返回查询发起节点。为了保证能收集到查询区域内所有节点的数据，文献1证明查询路线的宽度（itinerary width）不能超过R/2；为了减少查询节点的个数和查询时间，选择在查询路线方向上前进距离最大的节点作为下一个查询节点；为了避免多个数据节点同时发送结果消息带来的消息碰撞问题，采用了基于竞争（contention- based）的方法，即查询节点广播查询消息的同时，发送一条以查询节点为一个端点的参考线段，数据节点收到该参考线段后，计算查询节点和当前节点的连线与参考线段之间的夹角a，并按公式max_delay(a/2)（其中max_delay表示查询节点完成数据收集花费时间的最大值）计算当前节点发送查询结果的时间。该算法的查询路线是在查询过程中形成的，因而相比基于树的算法，能有效地消除通信链路失效和节点移动的影响。但该方法还存在以下问题：1）无法保证查询路线的联通性。如图1所示，若Q6不在Q5的通信半径内，Q5查询处理完成后查询终止，Q6到Q12路线上的查询结果均无法获得。2）节点失效问题。IWQE的性能瓶颈在于查询节点。当数据节点失效时，则仅丢失了该节点的数据。而当查询节点失效时，则前面收集的查询结果均丢失且无法收集后续查询节点上的结果。另外，文献8研究了连续近似空间范围查询，文献9研究了节点不均匀分布时的空间聚集查询处理算法，文献10研究了空间范围内现象的估计方法。图1 IWQE3 容忍节点失效的空间窗口聚集查询处理算法空间窗口聚集查询SWQ可以表示为SELECT aggFun(fieldName) FROM sensors Where sensors.pos IN sw。其中，aggFun为聚集函数，如min、max、average等；fieldName 为表sensors某一列的属性名，如温度、压力等；pos为节点的位置，sw代表查询区域，为了讨论的方便，本文假设为一矩形。以查询SELECT AVERAGE(temparature) FROM sensors Where sensors.pos IN Rect(0,0), (100,100)为例，它的语义是获得 (0,0), (100,100)矩形区域内平均温度。由于数据通信消耗的能量远大于处理器处理数据消耗的能量11，空间窗口聚集查询处理算法的优化目标在于使得查询处理过程中的数据通信量最小。3.1 算法思想为了避免现有算法的问题，提出一种基于网格的传感器网络空间窗口查询处理算法。算法将查询区域划分为若干个网格，网格的大小满足条件：相互邻接（四邻接，包含水平与垂直方向邻接）的网格中的任意两个节点之间的距离不超过节点的通信半径，由该条件可以得出以下结论。1) 同一网格内的所有节点均能收到从邻居网格发送的查询请求与部分查询结果。2) 网格内节点能收到所有在同一网格内的节点的查询结果。这样，网格内的所有节点均能分别计算出到当前网格为止的部分查询结果。当网格内节点失效时，只要网格内还存在未失效的节点，则不会影响查询处理的执行。如图2所示，n2发送所在网格G(0,5) (网格用G(x，y)表示)的部分查询结果和查询请求到下一个网格G(0,4)中的节点n3，n3、n4和n5均能收到该消息。n4和n5收到该消息后，依次广播自身感知的数据。由于无线通信的广播特性，此时，n3能获得n4和n5的感知数据，n4和n5能分别获得彼此的数据。n3利用从前面的网格中收到的部分查询结果消息和自身感知的数据，能计算出到当前网格为止的部分查询结果。n4和n5也能计算出除n3的感知数据之外的部分查询结果。当n3失效时，n4或n5能代替n3将查询结果发送到下一个节点。虽然此时的查询结果没有将n3的感知数据计算在内，但是可以得到近似的查询结果。可以看出，在GSA算法中每个节点既是数据节点，也是查询节点。查询节点的冗余，图2 GSA保证了查询处理不易受节点失效的影响。另外，类似于IWQE，GSA算法不依赖于预先建立的下层构造。它的查询线路也在查询处理的过程中生成，能有效地消除通信链路失效和节点移动的影响。当网格中不存在节点时，GSA利用基于位置的路由算法12将消息发送到下一个包含节点的网格。如图2所示，n19计算出部分查询结果后，查询当前节点的邻居节点列表，发现没有节点在G(1,4)中，则以G(1,4)的下一个网格G(1,5)为目标网格，利用基于位置的路由算法将部分查询结果和查询请求发送到该目标网格。图中消息先发送到n23，然后到达网格G(1,5)。因此，在查询路线不连通时，GSA依然能够继续处理查询。3.2 算法设计为了便于讨论，先做以下定义。传感器网络表示为SN=s1,s2,sN，|SN|=N。网络区域面积记为An。网络节点均匀分布，节点密度为，=N/An。节点传输半径相等且为R。节点的位置信息记作s.pos、s.pos.x和s.pos.y分别表示节点的x方向和y方向的坐标。平均每个节点有n个邻居节点。发送和接收1byte消耗的能量分别为Et和Er，节点广播一个1byte网络消耗的能量为E=Et+nEr。查询区域为一矩形记作sw。查询区域面积记为Aq，(sw.x1,sw.y1)和(sw.x2,sw.y2)分别表示sw的左下角和右上角坐标，sw中的节点数为M=Aq。查询消息包的大小为qs。查询区域内各节点感知数据消息包大小相等记为as。查询与部分查询结果消息包的大小为qpas。网格的宽度和高度分别记为gw和gh。查询区域的网格的数目记为gnum。网格中的节点数目为num。节点s所在的网格用s.g表示，s.g的x方向和y方向的坐标用s.g.x和s.g.y表示，s.g的矩形区域用s.g.rect表示。节点通信半径为R，记以节点s所在位置(s.pos.x, s.pos.y)为圆心，R为半径圆为s.c。空间聚集查询消耗的能量Etotal=Ef+Ec+Eb，其中，Ef：将查询请求发送到查询区域消耗的能量；Ec：在查询区域内分发查询、收集查询结果消耗的能量；Eb：将最终的查询结果返回查询发起节点消耗的能量。1) 计算节点所在网格节点si利用自己的位置信息，通过式(1)和式(2)可以计算出节点所在的网格(1)(2)2) 基于网格的查询结果收集调度策略当前网格内的节点收到上一个网格发送的查询请求和部分查询结果后，节点按从网格中心到节点向量的角度大小（从小到大或从大到小）排序，依次广播感知的数据。因为网格内的任意两个节点均在彼此的通信半径内，所以当一个节点的感知数据发送完毕后，下一个节点能感知到数据发送结束，并立即开始发送本节点的感知数据。相比IWQE的基于竞争的方法，减少了结果收集的时间，与此同时，由于不需要发送参考线段信息，也减少了能量的消耗。3) 网格代表节点每个网格需要一个节点收集所在网格中其他节点的数据，计算出部分查询结果和将结果发送至下一个网格，称该节点为网格代表节点。本文任选网格中的一个节点作为网格代表节点。如何选择网格代表节点使得节点负载平衡是本文未来的研究方向。4) 网格大小查询请求到达查询区域后，查询区域内除网格代表节点外的每个节点都需要广播一次查询结果消息，网格代表节点需要将查询请求和部分查询结果发送到下一个网格，因此Ec=(M-gnum)asE(gnum-1)qpasE显然，qpasas，所以Ecgnum。(3)显然，gnum1/(gwgh)。可以得到，Ec1/(gwgh)。网格四邻接时，网格的大小满足以下条件：(2gw)2+(gh)2R2且(gw)2+(2gh)2R2。显然，当(2gw)2+(gh)2=R2且(gw)2+(2gh)2=R2时，gwgh取最大值。解方程得gw=gh=/5。此时，gnum取最小值，Ec也取最小值。3.3 GSA算法GSA算法分为3个阶段：1) 位置路由查询消息阶段，即将查询消息发送到查询区域内；2) 查询分发与结果收集阶段，即将查询发送到查询区域内的所有网格，收集并聚集感知数据，计算出最终的查询结果；3) 返回结果阶段，即将第2阶段生成的查询结果返回至查询发起节点。为了便于算法的描述，不失一般性，假设查询发起节点o在查询区域的上方，查询消息的目的网格dg位于查询区域的左上角，查询字段的数据类型为数值类型，查询的聚集函数为SUM。下面给出GSA算法的详细执行过程。第1阶段：位置路由查询消息阶段。1) 若当前节点s是查询发起节点，收到查询请求SWQ后，提取SWQ中的聚集函数，查询字段和查询区域信息。计算目的网格的dg.x和dg.y。生成查询消息包qp，设置qp.qid为未出现的ID号， 通过SWQ可以得到qp的aggFun、fieldName、pos和sw字段的值。另外，qp.dg.x=dg.x，qp.dg.y=dg.y；转到2)；若s不是查询发起节点，收到上一个节点发送的查询消息包（包结构如图3所示）qp后，初始化目的网格：dg.x=qp.dg.x，dg.y=qp.dg.y，转到2)。2) 根据dg.x和dg.y计算出dg所在的矩形区域dg.rect。3) 根据s的邻居节点集合，计算出s在dg.rect中的所有邻居节点的集合s.dgNeigbhor。 若s.dgNeigbhor=f且s.c包含dg.rect，则dg不包含任何节点。计算dg的下一个网格dgNext，dg赋值为dgNext，转到2)； 若s.dgNeigbhorf且s.c包含dg.rect，则此时dg中的所有节点均能收到s发送的消息。初始化查询与部分查询结果消息qpap（消息结构如图4所示），通过收到的查询消息qp可以得到qpap的前7个字段的值（若当前节点是查询发起节点，则可通过提取SWQ中的信息获得）。另外，在s.dgNeighbor中任选一节点did，qpap.did=did ，qpap.sid=s.id，qpap.pa=0。广播qpap至节点did，转到第2阶段； 若s.dgNeigbhorf且s.c不包含dg.rect，则将查询消息包qp发送到s.dgNeigbhor中的任一节点；qid：查询标识oid：查询发起节点IDpos：查询发起节点位置aggFun：查询聚集函数fieldName：查询字段名sw：查询区域dg：目的网格，仅包含网格x，y坐标图3 查询消息结构qid：查询标识oid：查询发起节点IDpos：查询发起节点位置aggFun：查询聚集函数fieldName：查询字段名sw：查询区域dg：目的网格，仅包含网格x，y坐标sid：源节点IDdid：目的节点IDpa：部分查询结果图4 查询与部分查询结果消息结构qid：查询标识sid：源节点IDqa：传感器感知数据图5 感知数据消息结构 若s.dgNeigbhor=f且s.c不包含dg.rect，则转到4)。4) 判断当前节点是否是离目的位置最近的节点（通过GPSR路由协议，见文献12）。 若是，则查询消息无法到达dg，计算dg的下一个网格dgNext，dg赋值为dgNext，转到2)； 若否，以dg.rect的中心为目的位置，利用GPSR路由协议发送查询消息包qp。第2阶段：查询分发与结果收集阶段。节点s广播查询与部分查询结果消息包qpap至ID为qpa.did的网格代表节点gn。s的邻居集合s.neighbor中的节点收到该消息。对于所有在s.neighbor中的节点n，n计算自己所在的网格，判断是否等于目的网格qpap.dg。若不相等，则n不在网格qpap.dg中，n丢弃该消息。若相等，则n在网格qpap.dg中进行以下步骤。1) 节点n计算在qpap.dg中的除gn之外的邻居节点集合n.gNeighbor。对于所有在n.gNeighbor中的节点m，计算网格qpap.dg的中心到m.pos的向量的角度，并按该角度大小对节点进行排序（从小到大或从大到小）。2) 按角度排序后，在节点m之前的一个节点记做m.p。若m.p为空，则m收到qpap消息后开始发送感知数据消息（结构如图5所示）。若m.p非空，则m在m.p完成感知数据消息发送后开始发送感知数据。3) 网格内所有节点的感知数据发送结束后，gn利用从上一个网格发送来的查询与部分结果消息qpap，和所在网格的其他节点发送的感知数据消息包集合aps，计算出到当前网格为止的部分查询结果n.pa。计算公式如下4) gn计算所在网格的下一个网格dgNext，生成一个新的查询与部分查询结果消息包qpapNew。 通过qpap可以得到qpapNew的前6个字段的值，另外，qpapNew.dg=dgNex，qpapNew.sid=sc.is，qpapNew. pa=n.pa，判断dgNext中是否存在节点。 若存在，则在网格dgNext中任选一节点did，以该节点为下一个网格的网格代表节点，即qpapNew.did=did，将qpapNew广播到dgNext； 若不存在，则利用第一阶段的方法将qpapNew发送到下一个包含节点的网格。5) 网格中除gn之外的节点均监视gn是否发送了查询结果消息到下一网格。若在预定义的一段时间后，发现gn没有发送该消息，网格中剩余能量最大的节点代替gn，发送该节点计算出部分查询结果到下一网格。第3阶段：返回结果阶段。完成收集查询区域中的最后一个网格的感知数据后，能计算出最终的查询结果fqa。生成查询结果消息包qap（包结构如图6所示），利用收到的查询与部分查询消息包能得到qap的前3个字段的值，另外，qap.pa=fqa。以qap.pos为目的位置，利用GPSR11路由协议将qap发送到查询发起节点。qid：查询标识oid：查询发起节点IDpos：查询发起节点位置pa：部分查询结果图6 查询结果消息结构3.4 算法分析为了便于理论分析，假设任意时刻节点失效的概率为pf。IWQE算法的查询线路连通且查询区域内的查询节点数目记为qnum。为了保证能收集到查询区域内的所有数据，查询线路的宽度iw取最大的允许值R/2。查询节点s到它的下一个查询节点在查询路线方向上前进的距离的最大值z的期望值记为E(z)。E(z)的估计方法如下：如图7所示， 图7 估计E(z)节点s位于O点，s有n个邻居节点s1,s2,sn，节点sk(1kn)的y坐标值yk是随机变量，它的分布函数是P(yk)=(R2/2+R2sincos+R2)/(R2)=1/2+(sincos+)/ 其中，yk=Rsin且-/2/2。令，则y的分布函数F(y)=P(y)n。令，z的平均值记为E(z)，则因此可以得到可以近似认为qnum(sw.x2-sw.x1)/(R/2)(sw.y2-sw.y1)/E(z)(4)根据式(3)，可以得到gnum/qnum5E(z)/(2R)3.4.1 查询分发与结果收集阶段成功的概率对于IWQE算法，查询节点成功地将消息发送到下一查询节点的概率为(1-pf)2，因而，IWQE查询分发与结果收集阶段成功的概率为p(IWQE)=(1-pf)2qnum。对于GSA算法，消息从一个网格成功发送到下一个网格的概率为(1-pfnum)2，因而，GSA查询分发与结果收集阶段成功的概率为p(GSA)=(1-pfnum)2gnum。3.4.2 能量消耗由于Ef(IWQE)=Ef(GSA) Eb(IWQE)=Eb(GSA)，可以得到Etotal(GSA)-Etotal(IWQE)=Ec(IWQE)-Ec(GSA) 所以仅比较GSA与IWQE查询分发与结果收集阶段消耗的能量。先考虑理想的节点不失效的情况，对于GSA算法Ec(GSA)=(M-gnum)asE+(gnum-1)qpasE对于IWQE算法。利用IWQE处理空间范围查询，每个查询节点要广播一次查询消息。该查询节点的邻居节点中未发送感知数据消息的数据节点发送感知数据消息。查询节点将查询与部分查询结果发送到下一个查询节点，因此，IWQE分发查询和收集查询结果消耗的能量为Ec(IWQE)=qnumqsE+(M-qnum)asE+ (qnum-1)qpasE另外，可以认为qpasqs+as。可以得到Ec(GSA)(gnum-1)qsE+(M-1)asEEc(IWQE)(2qnum-1)qsE+(M-1)asEEc(IWQE)-Ec(GSA)(2-gnum/qnum)qnumqsE因此E(z)满足：当n3时，E(z)/R4/15；当n4时，4/15 p(IWQE)；当pf0.36时，p(GSA)p(IWQE)且它们的值接近于0。可见，随着节点失效概率的增加，查询成功率急剧减小。相比IWQE，GSA的下降幅度较小。图10 网络节点失效的概率对查询成功率的影响4) 查询区域大小对查询成功率的影响。查询区域面积占网络区域的比例分别取：0、0.04、0.16、0.36、0.64、1。如图11所示，随着查询区域面积的增加，图11 查询区域大小对查询成功率的影响对于IWQ，查询节点个数增多，查询成功率急剧减小。对于GSA，由于网格中存在网格代表节点的备份节点，查询成功率缓慢下降。5) 网络节点密度对能量消耗的影响。网络节点个数分别取375、750、1 125、1 500、1 875。图12显示了节点不失效的情况，可见，Ec(GSA) Ec(IWQE)。当网络的节点数目增加，需要收集更多节点的数据，所以两种算法的能量消耗均变大。图13显示了pf =0.04的情况。当N=375时， ；当N375时，。图12 pf=0时网络节点密度对能量消耗的影响图13 pf=0.04时网络节点密度对能量消耗的影响6) 查询消息大小对能量消耗的影响。查询消息大小分别取20、40、60、80、100。图14显示了节点不失效的情况。当N=750，可以推出gnum 2qnum。根据公式，可知GSA和IWQE的能量消耗与查询消息大小成正比，且GSA的斜率大于IWQE。实验与理论分析的结果是一致的。图15显示了pf=0.04的情况，可见。这是因为：当N=750，p(GSA)p(IWQE)，减少了GSA的执行次数，从而降低了消耗能量的期望值。图14 pf=0时查询消息大小对能量消耗的影响图15 pf=0.04时查询消息大小对能量消耗的影响7) 感知消息大小对能量消耗的影响。感知消息大小分别取20、40、60、80、100。图16显示了节点不失效的情况，可见，Ec(GSA)Ec(IWQE)。GSA和IWQE的能量消耗与查询消息大小成正比，且斜率近似相等，与理论分析的结果是一致的。图17显示了pf=0.04的情况。当N=750，p(GSA)p(IWQE)使得。8) 查询区域大小对能量消耗的影响。查询区域面积占网络区域的比例分别取：0、0.04、0.16、0.36、0.64、1。图18显示了节点不失效的情况。当查询区域变大，需要发送查询消息到更多的节点以及收集它们的感知数据，因而两种算法消耗的能量均变大。图19显示了图16 pf =0时感知消息大小对能量消耗的影响图17 pf =0.04时感知消息大小对能量消耗的影响图18 pf =0时查询区域大小对能量消耗的影响图19 pf =0.04时查询区域大小对能量消耗的影响pf=0.04的情况。随着查询区域面积占网络区域比例的增大，p(IWQE)急剧减小，急剧增大。而相比IWQE算法，Ec(GSA)增幅较小。5 结束语经理论和实验分析，若值较小，则GSA的查询线路连通性优于IWQE。若值较大，当节点不失效时，IWQE优于GSA。当节点失效时，若节点失效概率较小，则p(GSA)p(IWQE)且；若节点失效概率较大，则p(GSA)p(IWQE)且它们的值接近于0。对于GSA算法，增加网络节点密度能够显著地提高查询成功率，而IWQE算法没有该特性。因此，在多数情况下，GSA优于IWQE算法。参考文献：1XU Y Q, LEE W C, XU J L, et al. Processing window queries in wireless sensor networksA. Proc of the 22nd International Conference on Data EngineeringC. Washington, 2006. 70-80.2MADDEN S, FRANKLIN M J, HELLERSTEIN J M, et al. The design of an acquisitional query processor for sensor networksA. Proc of the 2003 ACM SIGMOD International Conference on Management of dataC. New York, 2003. 491-502.3GOLDIN D, SONG M, KUTLU A, et al. Georouting and delta-gathering: efficient data propagation techniques for geosensor networksA. Proceedings of GeoSensor Networks WorkshopC. Portland, Maine, 2003.4COMAN A, NASCIMENTO M A, SANDER J. A framework for spatio-temporal query processing over wireless sensor networksA. Proc of the 1st Intl Workshop on Data Management for Sensor Networks in Conjunction with VLDB 2004C. New York, 2004. 104-110.5COMAN A, NASCIMENTO M A. An analysis of spatio-temporal query processing in sensor networksA. Proc of the 1st IEEE Intl Workshop on Networking Meets Databases in Cooperation with 21st IEEE Conf on Data EngineeringC. Washington, 2005. 120-125.6COMAN A, NASCIMENTO M A, SANDER J. Exploiting redundancy in sensor networks for energy efficient processing of spatiotemporal region queriesA. Proc of the 14th ACM Co