etrs and ere.s,where etr and ere are the energy costs Therefore the overall energy consumption can be depicted for transmitting and receiving a unit data respectively,and as: etr is also relevant to the distance between the sender and receiver.For simplicity of presentation,the receiving energy Etotal(k)= C[(E,+Eg)·N+E,·Nk+ (Ea·N) cost is assigned to the transmitter without changing the total energy cost.Here we use Si to denote an arbitrary sensor (5) node in the ith hop,when sensor Si in the ith hop sends s And we let data units to Si in the jth hop,the energy cost of S;is 0, Rr=rqasd and the energy consumed by Si is: Rd rasd (etr +ere)s if Si is parent of Si Ro =Tqsa l(etr+ere·c),s if Sj is one of S.'s children· (1) To calculate the optimal hop count kopt for minimized over- In the above equation ci is the number of Si's children.For all energy consumption,we obtain the following discussion,we normalize the energy costs by OEtotal(k) =0→ (etr +ere)for ease of presentation.Thus,to transfer s data 8k units from Si to its parent,the transmitting energy will be (Ra-Rr).k2+(Rr-Ra+2Rg).k+C=0, s and to broadcast s data units to its children,sensor S will consume bis energy,where bi=Based on where tr十er the assumption of near-symmetric topology we can denote ci as the average number of children for sensor nodes in the C=1-n(R-R)+。rRg 6 ith hop,where c.And we set Ti as the Thus kopt has two possible solutions average number of sensor nodes in the subtree for any node in the ith hop (including the ith hop node itself),thus we =BB-2)+d=B-B-2)-4 have: 2(Ra-Rr) 2(Ra-R,】 =1+=1+2- where 2i-1 6=V(R,-Ra+2Rg)2-4C(Ra-R,) As we deduce from ar<ra there exists Rd>Rr,therefore As we know the energy cost Ei for a sensor node in the ith we get: hop consists of three types of energy costs: Ra 6 .1 Ei=Eq+Er+Ed. =互--R-2Ra-R<2 In the above equation,Eg denotes energy cost for query As we have kopt >1 we obsolete k2 and finally obtain the diffusion,Er denotes energy cost for query reply,and Ea optimal hop count: denotes energy cost for raw data forwarding.Hence based on the above energy model,we calculate the energy con- kopt (Ra-R-2Ra)+8 (6) 2(Ra-R) sumption for each ith hop,here we set the sink at the Oth hop. According to Eq.(6),it is known that the optimal hop We use k to denote the last hop of the storage node area. count for the storage area inside the unit zone,i.e.kopt, depends on the maximum hop count of the corresponding For storage nodes within the kth hop (1<i<k )we have: unit topology,i.e.n.Furthermore,it can be inferred that Er rqa Tisd the larger value of n is,the larger value of kopt can be ob- Ed=0 (2) tained.Based on the above analysis,if there are unlimited Ea birasa number of storages,we can compute the optimized storage placement as follows:For a specified deployment area with Here we set the reply data size as aTisd for the snapshot irregular shape,it can be approximately divided into a cer- query only fetches the most recent sensing data,and we set tain number of fan-shaped partitions according to the irreg- E=0 because although the storage nodes generate raw ular shape.Each fan-shaped partition is rooted from the data locally,they don't need to forward these data until sink and must contain no less than one unit zones.More- they're sent out as query replies.For storage nodes right in over,the fan-shaped partition is relatively regular in shape the kth hop,(i=k),we have: as compared to the overall deployment area,thus we can av- erage thethe hop counts of leaf nodes inside the fan-shaped Er Tga Tk sd partition and approximate the maximum hop count as n. Ed=0 (3) Therefore,we can approximately compute the optimal hop E=0 count Kopt for the storage area respectively for each fan- Here we set Eg =0 because the last hop of storage nodes shaped partition.Then,by putting the pieces together,the need not to diffuse queries to their forwarding node children. whole storage area can be obtained.Fig.4 illustrates the ba- For forwarding nodes outside the kth hop (k+1si<n): sic idea of the method.Theoretically,when the deployment area is divided into more refined partitions,the solution is Er=0 closer to the ideal optimal storage structure.In extreme Ed Tirasd. (4) case,when each of the fan-shaped partitions is exactly a E=0 unit zone,the optimal storage structure can be obtained.etr · s and ere · s, where etr and ere are the energy costs for transmitting and receiving a unit data respectively, and etr is also relevant to the distance between the sender and receiver. For simplicity of presentation, the receiving energy cost is assigned to the transmitter without changing the total energy cost. Here we use Si to denote an arbitrary sensor node in the ith hop, when sensor Si in the ith hop sends s data units to Sj in the jth hop, the energy cost of Sj is 0, and the energy consumed by Si is:  (etr + ere) · s if Sj is parent of Si (etr + ere · ci) · s if Sj is one of Si’s children . (1) In the above equation ci is the number of Si’s children. For the following discussion, we normalize the energy costs by (etr + ere) for ease of presentation. Thus, to transfer s data units from Si to its parent, the transmitting energy will be s and to broadcast s data units to its children, sensor Si will consume bi · s energy, where bi = etr+ere·ci etr+ere . Based on the assumption of near-symmetric topology we can denote ci as the average number of children for sensor nodes in the ith hop, where ci = Ni+1 Ni = 2i+1 2i−1 . And we set |Ti| as the average number of sensor nodes in the subtree for any node in the ith hop (including the ith hop node itself), thus we have: |Ti| = 1 + Pn i+1 Nj Ni = 1 + n 2 − i 2 2i − 1 . As we know the energy cost Ei for a sensor node in the ith hop consists of three types of energy costs: Ei = Eq + Er + Ed. In the above equation, Eq denotes energy cost for query diffusion, Er denotes energy cost for query reply, and Ed denotes energy cost for raw data forwarding. Hence based on the above energy model, we calculate the energy con￾sumption for each ith hop, here we set the sink at the 0th hop. We use k to denote the last hop of the storage node area. For storage nodes within the kth hop (1 < i < k ), we have:    Er = rqα|Ti|sd Ed = 0 Eq = birqsq . (2) Here we set the reply data size as α|Ti|sd for the snapshot query only fetches the most recent sensing data, and we set Ed = 0 because although the storage nodes generate raw data locally, they don’t need to forward these data until they’re sent out as query replies. For storage nodes right in the kth hop, (i = k), we have:    Er = rqα|Tk|sd Ed = 0 Eq = 0 . (3) Here we set Eq = 0 because the last hop of storage nodes need not to diffuse queries to their forwarding node children. For forwarding nodes outside the kth hop (k + 1 ≤ i ≤ n):    Er = 0 Ed = |Ti|rdsd Eq = 0 . (4) Therefore the overall energy consumption can be depicted as: Etotal(k) = kX−1 i=1 [(Er + Eq) · Ni] + Er · Nk + Xn i=k+1 (Ed · Ni). (5) And we let    Rr = rqαsd Rd = rdsd Rq = rqsq . To calculate the optimal hop count kopt for minimized over￾all energy consumption, we obtain ∂Etotal(k) ∂k = 0 ⇒ (Rd − Rr) · k 2 + (Rr − Rd + 2Rq) · k + C = 0, where C = 1 − n 2 6 (Rd − Rr) + −2etr ere + etr Rq. Thus kopt has two possible solutions k1 = (Rd − Rr − 2Rq) + δ 2(Rd − Rr) , k2 = (Rd − Rr − 2Rq) − δ 2(Rd − Rr) , where δ = p (Rr − Rd + 2Rq) 2 − 4C(Rd − Rr). As we deduce from αrq < rd there exists Rd > Rr, therefore we get: k2 = 1 2 − Rq Rd − Rr − δ 2(Rd − Rr) < 1 2 . As we have kopt ≥ 1 we obsolete k2 and finally obtain the optimal hop count: kopt = (Rd − Rr − 2Rq) + δ 2(Rd − Rr) . (6) According to Eq. (6), it is known that the optimal hop count for the storage area inside the unit zone, i.e. kopt, depends on the maximum hop count of the corresponding unit topology, i.e. n. Furthermore, it can be inferred that the larger value of n is, the larger value of kopt can be ob￾tained. Based on the above analysis, if there are unlimited number of storages, we can compute the optimized storage placement as follows: For a specified deployment area with irregular shape, it can be approximately divided into a cer￾tain number of fan-shaped partitions according to the irreg￾ular shape. Each fan-shaped partition is rooted from the sink and must contain no less than one unit zones. More￾over, the fan-shaped partition is relatively regular in shape as compared to the overall deployment area, thus we can av￾erage the the hop counts of leaf nodes inside the fan-shaped partition and approximate the maximum hop count as nb. Therefore, we can approximately compute the optimal hop count kopt for the storage area respectively for each fan￾shaped partition. Then, by putting the pieces together, the whole storage area can be obtained. Fig.4 illustrates the ba￾sic idea of the method. Theoretically, when the deployment area is divided into more refined partitions, the solution is closer to the ideal optimal storage structure. In extreme case, when each of the fan-shaped partitions is exactly a unit zone, the optimal storage structure can be obtained