(a)Separate routing strategy (b)Double ruling based routing strategy (c)Steiner tree based routing strategy Fig.4.Routing strategies for range query forwarding horizontal path it further imposes routing paths vertically Assume for each specified zone Si,it has a set of replicate to reach those corresponding storage regions.This routing storage node (si,1,si.2,...,si.m},here m is the number of scheme uses the horizontal routing path as the backbone path, redundancy of Si,which we can also denote as Sil,we thus it brings opportunities to sufficiently share the horizontal propose Algorithm 3 to compute the optimized routing path routing path,however,as it only utilizes the rectangular paths, for query diffusion by leveraging the approximation algorithms which may not be efficient enough when compared with the for Euclidean Minimum Steiner tree problem. shortest path. Hence according to the analysis over the pros.and cons. Algorithm 2 Computing the optimized routing path for query of the above two strategies,as our ultimate goal is to find diffusion the connecting paths with minimum routing cost,given the Input:Query node sg storage zone S1,$2,...,Sn specified query nodes and specified storage nodes,we can reduce the by range query O above problem into the Euclidean Minimum Steiner Tree[11] Procedure: problem.Based on the theory of Euclidean Steiner tree,we set Let opt =oo,steinset=o the query node and those specified storage nodes as terminal for each storage zone S:(1≤i≤n)do points,we then construct a Steiner tree according to these Enumerate each storage node si.j from Si,(1 <j<Sil) terminal points by selecting specific sensor nodes as the Si=Si,j Steiner points,thus to sufficiently share the routing path and (cost,S]=ComptuteSteinerTree(sg s1,...,si,..,sn) achieve the minimum routing cost for best energy efficiency. if (cost opt)then Fig.4(c)shows the Steiner tree based routing paths. opt cost steinset =S end if C.Optimized Routing Scheme for Query Forwarding end for We have reduced the optimized query forwarding problem Output:opt,steinset into the Euclidean minimum Steiner tree problem,actually as the problem is NP hard,so polynomial-time heuristics As each storage zone covers several storage nodes as are desired.There're a lot of research works which presents the candidate terminal points for the optimized solution,the heuristics algorithms to approximate the optimized Steiner above algorithm enumerates all permutations of storage nodes tree[11][12][13],and most of them are mainly solved by first (s1,s2....,sn)from those specified zones S1,S2,...,Sn.and constructing a Minimum Spanning Tree,for example,Dreyer leverage the function ComptuteSteinerTree to approximate the et.al.proposed two heuristics for the Euclidean Steiner tree optimized Steiner tree according to each permutation,among problem[12],which includes the Steiner Insertion Algorithm these candidate Steiner tree solutions we finally choose the and the Incremental Optimization Algorithm.The Steiner In- one which gives the minimum cost as the optimized Steiner sertion Algorithm systematically inserts Steiner points between tree solution.As here we leverage the Steiner Insertion Al- edges of the minimal spanning tree meeting at angles less gorithm as the approximation method,which has the time than 120 degrees,performing a local optimization at the end. complexity of O(n3),consider the number of permutations The Incremental Optimization Algorithm begins by finding M=I<inSil.we have the computing complexity as the Steiner tree for three of the fixed points.Then,at each O(M.n3).And the routing cost for query diffusion is equal iteration,it introduces a new fixed point to the tree,connecting to the overall lengths of the optimized Steiner tree it to each possible edge by inserting a Steiner point,and mini- Consider the distributed implementation of this optimized mizes over all connections,performing a local optimization for routing scheme,as each sensor node has the global information each.In this paper,we leverage Steiner Insertion Algorithm as of the index tree,for the query node,it first calculates the approximation method due to its simplicity and low computing optimized Steiner tree according to the specified range query, complexity.Readers can refer to [12]for detail algorithms. then it route the messages of sub-queries along the Steiner tree 171 Authorized licensed use limited to:Nanjing University.Downloaded on July 11,2010 at 07:42:17 UTC from IEEE Xplore.Restrictions apply.(a) Separate routing strategy (b) Double ruling based routing strategy (c) Steiner tree based routing strategy Fig. 4. Routing strategies for range query forwarding horizontal path it further imposes routing paths vertically to reach those corresponding storage regions. This routing scheme uses the horizontal routing path as the backbone path, thus it brings opportunities to sufficiently share the horizontal routing path, however, as it only utilizes the rectangular paths, which may not be efficient enough when compared with the shortest path. Hence according to the analysis over the pros. and cons. of the above two strategies, as our ultimate goal is to find the connecting paths with minimum routing cost, given the query nodes and specified storage nodes, we can reduce the above problem into the Euclidean Minimum Steiner Tree[11] problem. Based on the theory of Euclidean Steiner tree, we set the query node and those specified storage nodes as terminal points, we then construct a Steiner tree according to these terminal points by selecting specific sensor nodes as the Steiner points, thus to sufficiently share the routing path and achieve the minimum routing cost for best energy efficiency. Fig. 4(c) shows the Steiner tree based routing paths. C. Optimized Routing Scheme for Query Forwarding We have reduced the optimized query forwarding problem into the Euclidean minimum Steiner tree problem, actually as the problem is NP hard, so polynomial-time heuristics are desired. There’re a lot of research works which presents heuristics algorithms to approximate the optimized Steiner tree[11][12][13] , and most of them are mainly solved by first constructing a Minimum Spanning Tree, for example, Dreyer et.al. proposed two heuristics for the Euclidean Steiner tree problem[12], which includes the Steiner Insertion Algorithm and the Incremental Optimization Algorithm. The Steiner In￾sertion Algorithm systematically inserts Steiner points between edges of the minimal spanning tree meeting at angles less than 120 degrees, performing a local optimization at the end. The Incremental Optimization Algorithm begins by finding the Steiner tree for three of the fixed points. Then, at each iteration, it introduces a new fixed point to the tree, connecting it to each possible edge by inserting a Steiner point, and mini￾mizes over all connections, performing a local optimization for each. In this paper, we leverage Steiner Insertion Algorithm as approximation method due to its simplicity and low computing complexity. Readers can refer to [12] for detail algorithms. Assume for each specified zone Si , it has a set of replicate storage node {si,1, si,2, ..., si,m}, here m is the number of redundancy of Si , which we can also denote as |Si |, we propose Algorithm 3 to compute the optimized routing path for query diffusion by leveraging the approximation algorithms for Euclidean Minimum Steiner tree problem. Algorithm 2 Computing the optimized routing path for query diffusion Input: Query node sq, storage zone S1, S2, ..., Sn specified by range query Q Procedure: Let opt = ∞, steinset = φ for each storage zone Si(1 ≤ i ≤ n) do Enumerate each storage node si,j from Si , (1 ≤ j ≤ |Si |) si = si,j [cost, S]=ComptuteSteinerTree(sq, s1, ..., si , ..., sn ) if (cost < opt) then opt = cost steinset = S end if end for Output: opt, steinset As each storage zone covers several storage nodes as the candidate terminal points for the optimized solution, the above algorithm enumerates all permutations of storage nodes (s1, s2, ..., sn) from those specified zones S1, S2, ..., Sn, and leverage the function ComptuteSteinerTree to approximate the optimized Steiner tree according to each permutation, among these candidate Steiner tree solutions we finally choose the one which gives the minimum cost as the optimized Steiner tree solution. As here we leverage the Steiner Insertion Al￾gorithm as the approximation method, which has the time complexity of O(n 3 ), consider the number of permutations M = Q 1≤i≤n |Si |, we have the computing complexity as O(M · n 3 ). And the routing cost for query diffusion is equal to the overall lengths of the optimized Steiner tree. Consider the distributed implementation of this optimized routing scheme, as each sensor node has the global information of the index tree, for the query node, it first calculates the optimized Steiner tree according to the specified range query, then it route the messages of sub-queries along the Steiner tree 171 Authorized licensed use limited to: Nanjing University. Downloaded on July 11,2010 at 07:42:17 UTC from IEEE Xplore. Restrictions apply