{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T13:47:59Z","timestamp":1760708879127,"version":"build-2065373602"},"reference-count":22,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2015,7,27]],"date-time":"2015-07-27T00:00:00Z","timestamp":1437955200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>The \u03ba                                                  -Nearest Neighbors ( \u03baNN) query is an important spatial query in mobile sensor networks. In this work we extend \u03baNN to include a distance constraint, calling it a l-distant \u03ba-nearest-neighbors ( l-\u03baNN) query, which finds the \u03ba sensor nodes nearest to a query point that are also at     or greater distance from each other. The query results indicate the objects nearest to the area of interest that are scattered from each other by at least distance l. The l-\u03baNN query can be used in most \u03baNN applications for the case of well distributed query results. To process an l-\u03baNN query, we must discover all sets of \u03baNN sensor nodes and then find all pairs of sensor nodes in each set that are separated by at least a distance l. Given the limited battery and computing power of sensor nodes, this l-\u03baNN query processing is problematically expensive in terms of energy consumption. In this paper, we propose a greedy approach for l-\u03baNN query processing in mobile sensor networks. The key idea of the proposed approach is to divide the search space into subspaces whose all sides are l. By selecting \u03ba sensor nodes from the other subspaces near the query point, we guarantee accurate query results for l-\u03baNN. In our experiments, we show that the proposed method exhibits superior performance compared with a post-processing based method using the \u03baNN query in terms of energy efficiency, query latency, and accuracy.<\/jats:p>","DOI":"10.3390\/s150818209","type":"journal-article","created":{"date-parts":[[2015,7,28]],"date-time":"2015-07-28T02:12:37Z","timestamp":1438049557000},"page":"18209-18228","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Distance-Constraint k-Nearest Neighbor Searching in Mobile Sensor Networks"],"prefix":"10.3390","volume":"15","author":[{"given":"Yongkoo","family":"Han","sequence":"first","affiliation":[{"name":"Department of Computer Engineering, Kyung Hee University, Suwon 446-701, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kisung","family":"Park","sequence":"additional","affiliation":[{"name":"Department of Computer Engineering, Kyung Hee University, Suwon 446-701, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jihye","family":"Hong","sequence":"additional","affiliation":[{"name":"Department of Computer Engineering, Kyung Hee University, Suwon 446-701, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Noor","family":"Ulamin","sequence":"additional","affiliation":[{"name":"Department of Computer Engineering, Kyung Hee University, Suwon 446-701, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Young-Koo","family":"Lee","sequence":"additional","affiliation":[{"name":"Department of Computer Engineering, Kyung Hee University, Suwon 446-701, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2015,7,27]]},"reference":[{"key":"ref_1","unstructured":"United States Department of Transportation Intelligent Transportation System Joint Program Office Home, Available online: http:\/\/www.its.dot.gov."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Juang, P., Oki, H., Wang, Y., Martonosi, M., Peh, L., and Rubenstein, D. (2002, January 6\u201310). Energy-Efficient Computing for Wildlife Tracking: Design Tradeoffs and Early Experiences with Zebranet. Proceeding of 10th International Conference of Architectural Support for Programming Languages and Operating Systems, San Jose, CA, USA.","DOI":"10.1145\/605397.605408"},{"key":"ref_3","unstructured":"Federation of American Scientists Remote Battlefield Sensor System (Rembass). Available online: http:\/\/fas.org\/man\/dod-101\/sys\/land\/rembass.htm."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1023\/A:1024535730539","article-title":"Range and KNN Query Processing for Moving Objects in Grid Model","volume":"8","author":"Chon","year":"2003","journal-title":"Mob. Netw. Appl."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1109\/TKDE.2003.1161588","article-title":"Optimizing Index Allocation for Sequential Data Broadcasting in Wireless Mobile Computing","volume":"15","author":"Chen","year":"2003","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_6","unstructured":"Lee, W., and Zheng, B. (2005, January 6\u201310). DSI: A Fully Distributed Spatial Index for Location-Based Wireless Broadcast Services. Proceedings of International Conference on Distributed Computing Systems, Columbus, OH, USA."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1655","DOI":"10.1109\/TKDE.2008.80","article-title":"Toward the Optimal Itinerary-Based KNN Query Processing in Mobile Sensor Networks","volume":"20","author":"Wu","year":"2008","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1145\/320248.320255","article-title":"Distance Browsing in Spatial Databases","volume":"24","author":"Hjaltason","year":"1999","journal-title":"ACM Trans. Database Syst."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Mokbel, M., Xiong, X., and Aref, W. (2004, January 13\u201318). SINA: Scalable Incremental Processing of Continuous Queries in Spatio-Temporal Databases. Proceedings of the ACM SIGMOD International Conference on Management of Data, Paris, France.","DOI":"10.1145\/1007568.1007638"},{"key":"ref_10","unstructured":"Demirbas, M., and Ferhatosmanoglu, H. (2003, January 1\u20133). Peer-to-peer Spatial Queries in Sensor Networks. Proceedings of the IEEE International Conference on Peer-to-Peer Computing, Linkoping, Sweden."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Winter, J., and Lee, W. (2004, January 30). KPT: A Dynamic KNN Query Processing Algorithm for Location-Aware Sensor Networks. Proceedings of the ACM International Workshop on Data Management for Sensor Network, Toronto, ON, Canada.","DOI":"10.1145\/1052199.1052219"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"2861","DOI":"10.1016\/j.sigpro.2007.05.013","article-title":"Processing K Nearest Neighbor Queries in Location-aware Sensor Networks","volume":"87","author":"Xu","year":"2007","journal-title":"Signal Process."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Wu, S.-H., Chuang, K.-T., Chen, C.-M., and Chen, M.-S. (2007, January 15\u201320). DIKNN: An Itinerary-Based KNN Query Processing Algorithm for Mobile Sensor Networks. Proceedings of the IEEE International Conference on Data Engineering, Istanbul, Turkey.","DOI":"10.1109\/ICDE.2007.367891"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1989","DOI":"10.1007\/s00779-014-0795-y","article-title":"Novel itinerary-based KNN query algorithm leveraging grid division routing in wireless sensor networks of skewness distribution","volume":"18","author":"Han","year":"2014","journal-title":"Pers. Ubiquitous Comput."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"711","DOI":"10.1109\/TKDE.2009.146","article-title":"Parallelizing Itinerary-Based KNN Query Processing in Wireless Sensor Networks","volume":"22","author":"Fu","year":"2010","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_16","first-page":"385","article-title":"k-nearest neighbor search based on node density in MANETs","volume":"10","author":"Komai","year":"2014","journal-title":"Mob. Inf. Syst."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1007\/978-3-319-07425-2_19","article-title":"K Nearest Neighbour Query Processing in Wireless Sensor and Robot Networks","volume":"8487","author":"Xie","year":"2014","journal-title":"Lect. Notes Comput. Sci."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"582","DOI":"10.3390\/a7040582","article-title":"Processing KNN Queries in Grid-Based Sensor Networks","volume":"7","author":"Huang","year":"2014","journal-title":"Algorithms"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Karp, B., and Kung, H. (2000, January 6\u201311). GPSR: Greedy perimeter stateless routing for wireless networks. Proceeding of the 6th annual international conference on Mobile computing and networking, Boston, MA, USA.","DOI":"10.1145\/345910.345953"},{"key":"ref_20","unstructured":"Xu, Y., Lee, W., Xu, J., and Mitchell, G. (2006, January 3\u20138). Processing window queries in wireless sensor networks. Proceedings of International conference of Data Engineering, Atlanta, GA, USA."},{"key":"ref_21","unstructured":"The Network Simulator. Available online: http:\/\/www.isi.edu\/nsnam\/ns."},{"key":"ref_22","unstructured":"Dubuisson, M., and Jain, A.K. (1994, January 9\u201313). A Modified Hausdorff Distance for Object Matching. Proceedings of International Conference on Pattern Recognition, Jerusalem, Israel."}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/15\/8\/18209\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T20:49:46Z","timestamp":1760215786000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/15\/8\/18209"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,7,27]]},"references-count":22,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2015,8]]}},"alternative-id":["s150818209"],"URL":"https:\/\/doi.org\/10.3390\/s150818209","relation":{},"ISSN":["1424-8220"],"issn-type":[{"type":"electronic","value":"1424-8220"}],"subject":[],"published":{"date-parts":[[2015,7,27]]}}}