Microsoft Word - 刘亮.doc

Transcription

1 ISSN CODEN JKYTA8 Journal of Frontiers of Computer Science and Technology /2010/04(08) Tel: DOI: /j.issn * +,,,, Link Aware Spatial Window Query Processing Algorithm in Wireless Sensor Networks * LIU Liang +, QIN Xiaolin, LIU Yulei, LI Bohan College of Information Science & Technology, Nanjing University of Aeronautics & Astronautics, Nanjing , China + Corresponding author: liangliu@nuaa.edu.cn LIU Liang, QIN Xiaolin, LIU Yulei, et al. Link aware spatial window query processing algorithm in wireless sensor networks. Journal of Frontiers of Computer Science and Technology, 2010, 4(8): Abstract: In wireless sensor networks, the users often submit spatial window queries to obtain the summary information of a local area in the network such as maximum temperature, average humidity, et al. The current state-of-the-art itinerary-based spatial query processing algorithms make the assumption of the link model pertaining to the ideal disk model. However, it s not valid in realistic networks, which leads to large energy consumption and poor quality query result. This paper proposes a link quality aware spatial window query processing algorithm called LSA(link aware spatial window query processing algorithm). It divides the query region into several grids according to the topology and link of the network, and collects data from the sensor nodes in each grid to derive the final query result. LSA traverses all the grids within the query region which ensures the query result quality of the algorithm. In order to reduce the packet loss rate of communications between nodes, a heuristic method is given which divides the query region into grids. Then, a link aware data collection algorithm is proposed to reduce energy consumption and *The National High Technology Research and Development Program of China under Grant No.2007AA01Z404( (863)); the Jiangsu Province Science and Technology Pillar Program of China under Grant No.BE ( ); the Electronic Development Fund of the Ministry of Information Industry( ); NUAA Research Funding under Grant No.NS ( ); the National Power Grid Technologies Project under Grant No.SGKJ0884( ). Received , Accepted

2 750 Journal of Frontiers of Computer Science and Technology 2010, 4(8) improve the query result quality of the algorithm. Finally, this paper systematically analyzes and compares the energy consumption and the query result quality of the LSA and the existing IWQE(itinerary-based window query execution) algorithm through simulation experiments. Experimental results show that LSA algorithm outperforms IWQE in most cases. Key words: wireless sensor network; query processing; spatial window query; link quality,,,, LSA,,, LSA,,,, LSA IWQE,,, LSA IWQE ; ; ; A TP ,,,,, (1) TAG(tiny aggregation service for Ad-Hoc sensor networks) [1], (spanning routing tree),,,,, [2] TAG R [3],,, [4] TAG STWinFlood (spatiotemporal window flood algorithm),,, TAG, TAG, STWinFlood, [5], STWinFlood

3 751,,, [6] STWinFlood,, STWinFlood [7 8],, (setting error budgets), Top-k, [9] FILA(filter-based monitoring approach), (2) [10] IWQE(itinerarybased window query execution), ( ) ( ),,,,, [11 13] IWQE K, IWQE [14],, [15 16],,,,, [17], r, n 1 n 2 D(n 1, n 2 )>r, n 1 n 2 P(n 1, n 2 )=0; D(n 1, n 2 r, P(n 1, n 2 )=1, P(n 1, n 2 ) [0,1], [18 19], LSA(link aware spatial window query processing algorithm) ;,,,,,, ; LSA,,,,, LSA IWQE 2 [10] IWQE 1, IWQE IWQE ( p 1 p 2 ),

4 752 Journal of Frontiers of Computer Science and Technology 2010, 4(8), IWQE (1) s, [20] p 1 ; (2) p 1, ; (3) p 1, p 1 ; (4) p 1, ( ), p 2 ; (5), p 13, s, [10] (itinerary width) 3 r/2, r ;,,,,, α, max_delay (α/(2π))( max_delay ), IWQE, [17 19], (1) 1, IWQE, p 1 p 2,, [19], p 2,, (2) n 1 n 2 P(n 1,n 2 ) 1, a p 1 p 2, P(p 1,a)=P(a, p 1 ), P(p 2,a)=P(a, p 2 ), P(p 1,a)<<P(p 2,a) IWQE, a p 1, p 2 a p 2 r 2 p 1 p 3 p 6 r 1 p 5 p 7 p 4 Fig.1 IWQE algorithm 1 IWQE [11 13] IWQE K, 3 3.1,, [21 22] [17,19] s p 10 r 4 p 8 p 9 p 12 r3 p 13 p 11

5 753,,, 3.2 m, h, s N() s ( s h)/ m n 1 m n 2 P(n 1,n 2 ), n 1 m n 2 T(n 1, n 2 )=1/P(n 1,n 2 ) n 1 n 2 D(n 1,n 2 ) s r, D(n 1, n 2 )>r, P(n 1,n 2 )=0 S q, S a S a n r m E s E r, m E=E s +n r E r arg min f ( x) x f(x) x 3.3 IWQE, LSA 2, LSA, IWQE, LSA (1),, ; (2), ; A C E q 2 r 2 q 1 q 3 B q 4 D F q 7 q 13 q 12 Fig.2 LSA algorithm 2 LSA (3), LSA k g i (i= 1,2,,k), g i ns i (i=1, 2,,k), q i (i=1,2,,k), g i ns i q 1 q 0 ( 2 r 2 ) LSA k t c i i i 1 E E (, i q, g ) E (, iq, g) E() i E() i E() i (1) c i i s b a r 1 q 8 q 6 q 5, E c (i,q i,g i ) q i g i, E s (i) q i-1 q i NS ( q) Tq ( i 1, qi) E i 1 Es () i N( S a Sq) T( qi 1, qi) E i=2,3,..., k E b (i) q i g i 0 nsi qi =0 Eb () i NS ( q) max Tq ( i, ne ) ns 0 n ( nsi qi) i qi E a (i) g i q i s q 10 q 9 r 4 q 16 q 11 q 14 r3 q 15

6 754 Journal of Frontiers of Computer Science and Technology 2010, 4(8) E () i N( S ) T( n, q ) E a a i n ( nsi qi), Minimize Et Subject to Dq ( i 1, qi) r, i 1,2,, k D( nq, i) r, n nsi, i 1,2,, k (2) (2),,, [24], (unit disk graph, n 1 n 2, D(n 1, n 2 ) 1, n 1 n 2 ) (minimum connected dominating set, MCDS) NP-hard MCDS (2), (2) NP-hard,,,, (2), q i 1 g i 1, F i (q i,g i ) g i q i Ec(, iqi, gi) F i (q i, g i )= (3) ns i F i (q i, g i ) q i g i, 2, q 1, F 1 (q 1,g) ( g ) g 1, g 1 arg min F 1 (q 1,g) q 1 g 1 g, g 2 g 2 q 2 g 2 q 2 Es(2, qg, ) Eb(2, qg, ) Ea(2, qg, ) F 2 (q, g)= ns q g q 1 q 2, q 2 g 2, 2,,, ( 2 q 16 ), 3.4 LSA (1), ; (2),,, ; (3), LSA [17,23],, LSA, LSA, (1) q i arg min F i+1 (q i+1, q g i+1 ) arg min F i+1 (q i+1,g i+1 ) g i 1 i 1 3, D(q i,e)=d(q i,f)=r q i g i ABCD q i CDEF qn i, qn i q i min F i+1 (q i+1,g i+1 )= min [min Fi 1( ng, )] n qni, arg min F i+1 (q i+1,g i+1 ) arg min F i+1 (q i+1, q i gi 1 g i+1 ) n qn i, n q i F i+1 (n,g)( g ) g g n = arg min Fi 1( ng, ) g n, min F i+1 (q i+1,g i+1 )= min [ Fi 1( n,g n)] g n qni (4) n qn i, g n Cal_g n, 3 b, c d e

7 755 A B qi C a D G b H I c J E d K L M e F N... Fig.3 Calculating the next query node 3 b b g CDGH CDIJ CDKL CDMN F i+1 (b,g) ( g ), g b F i+1 (b,g) (2) q i g i g i, q i g i,,, LADC(link aware data collection algorithm) LADC 1 1 nq i ns i -q i (nq i g i ) q i nq i P(q i,n) ( n nq i ) k, nq i q i ; 2 q i k,, nq i ; 3 rs i u rs i, u, <g i.c, u.pos> β(g i.c g i, u.pos u ), IWQE, max_delay (β/(2π)) u, ; 4 rs i, q i nq i, ;, q i, nq i ls i ; 2 q i ls i q i u; 3 q i u, u u, u;, ls i = ls i -u, 4; 4 q i ls i q i v, q i v, v v, q i 3 v, v ; 5 q i 3 4 ls i, g i (3) 4, D(e,K)=D(e,J)=r, D(G,K)>D(H,J) e EFGH, EFGH GHKJ e, GHKJ,,, e IJLM ( D(I,M)=r), [17,23] 4, e g h IJLM q 3,

8 756 Journal of Frontiers of Computer Science and Technology 2010, 4(8) IJLM IJLM,, IJLM LMNQ ( D(L, Q)=r), [17,23] C D Fig.4 4 G g h E I K L N b e q 3 Bypassing the void region 4, [25] IWQE LSA [23], P4(3.0 GHz) CPU, 512 MB ; Ubuntu Eclipse (1) a [19], Mica2 (LNM(log normal path loss model)) ( d ) f ppr( d) (1 e ) 2 d ( d) Pt PL( d0) 10 lg N(0, ) Pn d 0, ppr(d) f... c d F H J M Q d, ρ ; f γ(d) d P t PL(d 0 ) d 0 η (path loss exponent) N(0,σ) 0 σ P n (noise floor) (2) b [26] ANRG 100, a, b LNM, LNM 1 Table 1 Link model parameters 1 ρ 1 f 50 byte P t 0 dbm d 0 1 m d 0 PL(d 0 ) 55 dbm η 4 σ 4 P n 105 dbm Table 2 Simulation parameters m 100 m IWQE 11 m 110 byte 64% IWQE LNM, 5,

9 757 (transitional region) [19] ( )1(0), Fig.5 Effect of distance between two nodes on link quality 5 [10] IWQE, 3 LNM IWQE 3 2 IWQE, IWQE, IWQE 3 3 IWQE, IWQE,, IWQE,,,,,,, IWQE 11 m,,, IWQE 4.2 IWQE LSA IWQE,, IWQE 6,,,, LSA,, Table 3 Performance of IWQE in LNM model 3 LNM IWQE /m Fig.6 6 Effect of query region size on energy

10 758 Journal of Frontiers of Computer Science and Technology 2010, 4(8) 7,, IWQE, LSA,, Fig.7 Effect of node density on energy IWQE LSA [10], sr=cn/tn,, tn, cn 8,, Fig.8 Effect of query region size on query result quality 8, IWQE LSA, IWQE, LSA, 9,,, [22],,, 1, IWQE, LSA Fig.9 Effect of node density on query result quality 9 5,,,,,,

11 759 LSA,, LSA,,,,, LSA IWQE,, LSA IWQE References: [1] Madden S, Franklin M J, Hellerstein J M, et al. The design of an acquisitional query processor for sensor networks[c]//proceedings of the 2003 ACM SIGMOD International Conference on Management of Data. New York: ACM Press, 2003: [2] Goldin D, Song M, Kutlu A, et al. Georouting and deltagathering: Efficient data propagation techniques for GeoSensor networks[c]//proceedings of 1st GeoSensor Networks Workshop, Portland, Maine, [3] Guttman A. R-trees: A dynamic index structure for spatial searching[c]//proceedings of the 1984 ACM SIGMOD International Conference on Management of Data. New York: ACM Press, 1984: [4] Coman A, Nascimento M A, Sander J. A framework for spatio-temporal query processing over wireless sensor networks[c]//proceedings of the 1st International Workshop on Data Management for Sensor Networks in Conjunction with Very Large Data Bases. New York: ACM Press, 2004: [5] Coman A, Nascimento M A, Sander J. Exploiting redundancy in sensor networks for energy efficient processing of spatiotemporal region queries[c]//proceedings of the 14th ACM Conference on Information and Knowledge Management. New York: ACM Press, 2005: [6] Liu Liang, Qin Xiaolin, Dai Hua, et al. Energy-efficient spatio-temporal query processing algorithm in wireless sensor networks[j]. Acta Electronica Sinica, 2010, 38(1): [7] Jain N, Yalagandula P, Dahlin M, et al. Self-tuning, bandwidth-aware monitoring for dynamic data streams [C]//Proceedings of the 22nd International Conference on Data Engineering. Washington DC: IEEE Computer Society, [8] Jain N, Yalagandula N, Dahlin M, et al. STAR: Self-tuning aggregation for scalable monitoring [C]//Proceedings of the 33rd International Conference on Very Large Data Bases. Washington DC: IEEE Computer Society, 2007: [9] Wu Minji, Xu Jianliang, Tang Xueyan, et al. Top-k monitoring in wireless sensor networks[j]. IEEE Transactions on Knowledge Data Engineering, 2007, 19(7): [10] Xu Yingqi, Lee Wangchien, Xu Jianliang, et al. processing window queries in wireless sensor networks[c]//proceedings of the 22nd International Conference on Data Engineering. Washington DC: IEEE Computer Society, 2006: [11] Fu Taoyang, Peng Wenchi, Lee Wangchen. Parallelizing itinerary-based KNN query processing in wireless sensor networks[j]. IEEE Transactions on Knowledge and Data Engineering, 2010, 22(5): [12] Wu Shanhung, Chuang Kunta, Chen Chungmin, et al. Toward the optimal itinerary-based KNN query processing in mobile sensor networks[j]. IEEE Transactions on Knowledge and Data Engineering, 2008, 20(12): [13] Wu Shanhung, Chuang Kunta, Chen Chungmin, et al. DIKNN: An itinerary-based KNN query processing algorithm for mobile sensor networks[c]//proceedings of the 23rd International Conference on Data Engineering. Washington DC: IEEE Computer Society, 2007: [14] Sharifzadeh M, Shahabi C. Supporting spatial aggregation in sensor network databases[c]//proceedings of 12th ACM International Workshop on Geographic Information Systems. New York: ACM Press, 2004: [15] Cheng Siyao, Li Jianzhong. Sampling based (epsilon, delta)-approximate aggregation algorithm in sensor networks[c]//proceedings of 29th IEEE International Conference on Distributed Computing Systems. Washington DC: IEEE Computer Society, 2009: [16] Cheng Siyao, Li Jianzhong, Ren Qianqian, et al. Bernoulli sampling based (epsilon, delta)-approximate aggregation in larger-scale sensor networks[c]//proceedings of the 29th IEEE International Conference on Computer Communications, [17] Antonio M, Zamalloa Z, Seada K, et al. Efficient geographic routing over lossy links in wireless sensor networks[j]. ACM Transactions on Sensor Networks, 2008, 4(3): 1 33.

12 760 Journal of Frontiers of Computer Science and Technology 2010, 4(8) [18] Woo A, Tong T, Culler D. Taming the underlying challenges of reliable multihop routing in sensor networks[c]// Proceedings of the Conference on Embedded Networked Sensor Systems of the ACM. New York: ACM Press, 2003: [19] Zuniga M, Krishnamachari B. Analyzing the transitional region in low power wireless links[c]//proceedings of The 1st IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks. Washington DC: IEEE Communications Society, 2004: [20] Karp B, Kung H T. GPSR: Greedy perimeter stateless routing for wireless networks[c]//proceedings of the 6th Annual International Conference on Mobile Computing and Networking. New York: ACM Press, 2000: [21] Fonseca R, Gnawali O, Jamieson K, et al. Four bit wireless link estimation[c]//proceedings of the 6th Workshop on Hot Topics in Networks, [22] Senel M, Chintalapudi K, Lal D, et al. A Kalman filter based link quality estimation scheme for wireless sensor networks[c]//proceedings of Conference on the IEEE Global Telecommunications, 2007: [23] Seada K, Zuniga M, Helmy A, et al. Energy-efficient forwarding strategies for geographic routing in lossy wireless sensor networks[c]//proceedings of the 2nd International Conference on Embedded Networked Sensor Systems. New York, ACM Press, 2004: [24] Clark B N, Colbourn C J, Johnson D S. Unit disk graphs[j]. Discrete Mathematics, 1990, 86(1): [25] Coman A, Sander J, Nascimento M A. Adaptive processing of historical spatial range queries in peer-to-peer sensor networks[j]. Distributed and Parallel Databases, 2007, 22(2/3): [26] Zuniga M, Sridharan A, Kapadia S, et al. Measurement of pairwise PRR values from two real 100-node rectangular grid deployments at an indoor basketball court at USC consisting of 59 Moteiv Tmote Sky nodes interspersed with 41 crossbow MicaZ nodes[eb/ol]. [ ]. 附中文参考文献 : [6],,,. [J]., 2010, 38 (1): LIU Liang was born in He received his B.S. degree from Northwestern Polytechnical University in 2005, and now is a Ph.D. candidate at Nanjing University of Aeronautics and Astronautics. His research interest is data management in wireless sensor networks. (1985 ),,, 2005,, QIN Xiaolin was born in He is a professor and doctoral supervisor at Nanjing University of Aeronautics and Astronautics. His research interests include spatial and spatio-temporal databases, data management and security in distributed environment, etc. (1953 ),,,, /, LIU Yulei was born in He received his M.S. degree from Nanjing University of Aeronautics and Astronautics in 2001, and now is a Ph.D. candidate at Nanjing University of Aeronautics and Astronautics. His research interest is data management in wireless sensor networks. (1974 ),,, 2001,, LI Bohan was born in He received his Ph.D. degree from Harbin University of Science and Technology in 2009, and now works as a post-doctoral researcher at Nanjing University of Aeronautics and Astronautics. His research interest is data management in wireless sensor networks. (1979 ),,, 2009,,