Á¤º¸°úÇÐȸ ³í¹®Áö D : µ¥ÀÌŸº£À̽º
ÇѱÛÁ¦¸ñ(Korean Title) |
¹«¼± ¼¾¼ ³×Æ®¿öÅ©¿¡¼ Ŭ·¯½ºÅÍ ±â¹ÝÀÇ Top-k ÁúÀÇ Ã³¸® |
¿µ¹®Á¦¸ñ(English Title) |
A Cluster-Based Top-k Query Processing Algorithm in Wireless Sensor Networks |
ÀúÀÚ(Author) |
¿©¸íÈ£
¼ºµ¿¿í
À¯Àç¼ö
Myung Ho Yeo
Dong Ook Seong
Jae Soo Yoo
|
¿ø¹®¼ö·Ïó(Citation) |
VOL 36 NO. 04 PP. 0306 ~ 0313 (2009. 08) |
Çѱ۳»¿ë (Korean Abstract) |
¼¾¼ ³×Æ®¿öÅ© ÀÀ¿ë ºÐ¾ß¿¡¼ Top-k ÁúÀÇ´Â °¡Àå ³ôÀº ȤÀº °¡Àå ³·Àº k°³ÀÇ ¼¾¼¿¡ ´ëÇÑ À¯¿ëÇÑ Á¤º¸¸¦ Á¦°øÇÑ´Ù. Top-k ÁúÀÇ Ã³¸® ½Ã ¿¡³ÊÁö ¼Ò¸ð¸¦ ÁÙÀ̱â À§ÇÑ ¸¹Àº ¿¬±¸µéÀÌ ÁøÇàµÇ¾ú´Ù. FILAÀÇ °æ¿ì, ÇÊÅ͸¦ ÀÌ¿ëÇÏ¿© ºÒÇÊ¿äÇÑ °á°úÀÇ °»½ÅÀ» Á¦°ÅÇÏ¿´À¸¸ç, PRIMÀÇ °æ¿ì, ¼¾½ÌµÈ µ¥ÀÌŸÀÇ ¿ì¼± ¼øÀ§¸¦ ºÎ¿©ÇÏ¿© ¼¾¼ µ¥ÀÌŸÀÇ Àü¼ÛÀ» ÃÖ¼ÒÈÇÏ´Â ¹æ¹ýÀ» Á¦¾ÈÇÑ´Ù. ÇÏÁö¸¸, °°Àº µ¥ÀÌŸ ¹üÀ§(ÇÁ·¹ÀÓ)¿¡ ¼ÓÇÑ ¸ðµç µ¥ÀÌŸ¸¦ ¼öÁýÇϱ⠶§¹®¿¡ µ¥ÀÌŸÀÇ ÁýÁßÀÌ ¹ß»ýÇÏ¸é ¸¹Àº False Positive µ¥ÀÌŸ¸¦ Àü¼ÛÇÏ´Â ¹®Á¦°¡ ¹ß»ýÇÑ´Ù. º» ³í¹®¿¡¼´Â Top-k °á°úÀÇ False Positive µ¥ÀÌŸ¸¦ È¿°úÀûÀ¸·Î Á¦°ÅÇϱâ À§ÇÑ Å¬·¯½ºÅÍ ±â¹ÝÀÇ »õ·Î¿î Top-k ÁúÀÇ Ã³¸® ±â¹ýÀ» Á¦¾ÈÇÑ´Ù. ÁúÀÇ Ã³¸® °úÁ¤Àº Ŭ·¯½ºÅÍ ·¹º§°ú Æ®¸® ·¹º§·Î ³ª´©¾îÁö¸ç, °¢ ·¹º§ÀÇ ³×Æ®¿öÅ© ÅäÆú·ÎÁöÀÇ Æ¯¼ºÀ» È°¿ëÇÏ¿© False Positive µ¥ÀÌŸ¸¦ È¿°úÀûÀ¸·Î ÇÊÅ͸µÇÑ´Ù. ¼º´É Æò°¡ °á°ú, ±âÁ¸ Top-k ÁúÀÇ Ã³¸® ±â¹ý¿¡ ºñÇØ False Positive µ¥ÀÌŸÀÇ ¼ö°¡ 70% °¨¼ÒÇÏ°í, ³×Æ®¿öÅ© ¼ö¸íÀÌ ¾à 105% ¿¬ÀåµÈ´Ù. |
¿µ¹®³»¿ë (English Abstract) |
Top-k queries are issued to find out the highest (or lowest) readings in many sensor applications. Many top-k query processing algorithms are proposed to reduce energy consumption; FILA installs a filter at each sensor node and suppress unnecessary sensor updates; PRIM allots priorities to sensor nodes and collects the minimal number of sensor reading according to the priorities. However, if many sensor reading converge into the same range of sensor values, it leads to a problem that many false positives are occurred. In this paper, we propose a cluster-based approach to reduce them effectively. Our proposed algorithm operates in two phases: top-k query processing in the cluster level and top-k query processing in the tree level. False positives are effectively filtered out in each level. Performance evaluations show that our proposed algorithm reduces about 70% false positives and achieves about 105% better performance than the existing top-k algorithms in terms of the network lifetime. |
Å°¿öµå(Keyword) |
¹«¼± ¼¾¼ ³×Æ®¿öÅ©
Ŭ·¯½ºÅ͸µ
Top-k ÁúÀÇ Ã³¸®
Wireless sensor networks
clustering
top-k query processing
|
ÆÄÀÏ÷ºÎ |
PDF ´Ù¿î·Îµå
|