Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Wireless Networks
Erschienen in: Wireless Networks 4/2010

01.05.2010

A scalable energy-efficient continuous nearest neighbor search in wireless broadcast systems

verfasst von: Kwangjin Park, Hyunseung Choo, Patrick Valduriez

Erschienen in: Wireless Networks | Ausgabe 4/2010

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

When the mobile environment consists of light-weight devices, the energy consumption of location-based services (LBSs) and the limited bandwidth of the wireless network become important issues. Motivated by this, we propose new spatial query processing algorithms to support Mobile Continuous Nearest Neighbor Query (MCNNQ) in wireless broadcast environments. Our solution provides a general client–server architecture for answering MCNNQ on objects with unknown, and possibly variable, movement types. Our solution enables the application of spatio-temporal access methods specifically designed for a particular type, to arbitrary movements without any false misses. Our algorithm does not require any conventional spatial index for MCNNQ processing. It can be adapted to static or moving objects, and does not require additional knowledge (e.g., direction of moving objects) beyond the maximum speed and the location of each object. Extensive experiments demonstrate that our location-based data dissemination algorithm significantly outperforms index-based solutions.
Vorheriger Artikel Achieving robust message authentication in sensor networks: a public-key based approach
Nächster Artikel An optimal new-node placement to enhance the coverage of wireless sensor networks

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Fußnoten
1
Clients who have no prior knowledge of the contents of the broadcast data will access the directory from air [5].
 
2
Nearest neighbor (NN) query is to find the spatial object with the smallest distance to a query position.
 
3
Each object determines their maximum speed. For example, a moving car may not exceed a speed of 300 km/h.
 
4
The R-tree is a classical spatial index structure. The basic idea is to approximate a spatial object with a minimal bounding rectangle (MBR) and to index the MBRs recursively [26].
 
5
In BBS, indexes are broadcast m times during one broadcast cycle. The whole index is broadcast preceding every fraction \(({\frac{1}{m}})\) of the broadcast cycle [5]. By replicating the index for m times, the waiting time for reaching a forthcoming index segment can be reduced.
 
6
The server disseminates data items via one-dimensional wireless broadcast channel and the client sequentially accesses them.
 
7
If more than two points have the same x-axis value, upper point is selected first.
 
8
In conventional moving query processing over moving objects, there is no accuracy guarantee, since even a high sampling rate may still miss some points of the query segment where there is a change of neighborhood [32].
 
9
Split points represent the points of the query segment where there is a change of neighborhood.
 
Literatur
1.
Lee, D. L., Lee, W.-C., Xu, J., & Zheng, B. (2002). Data management in location-dependent information services: Challenges and issues. IEEE Pervasive Computing, 1(3), 65–72.CrossRef
2.
Zheng, B., Xu, J., Lee, W.-C., & Lee, D. L. (2006). Grid-partition index: A hybrid approach to nearest-neighbor queries in wireless location-based services. The International Conference on Very Large Data Bases (VLDB) Journal, 15(1), 21–39.CrossRef
3.
Zhang, J., & Gruenwald, L. (2002). Prioritized sequencing for efficient query on broadcast geographical information in mobile-computing. In Proceedings of SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS), pp. 88–93.
4.
Zheng, B., Lee, W.-C., & Lee, D. L. (2004). Spatial queries in wireless broadcast systems. Wireless Network, 10(6), 723–736.CrossRef
5.
Imielinski, T., Viswanathan, S., & Badrinath, B. R. (1997). Data on air: Organization and access. IEEE Transactions on Knowledge and Data Engineering, 9(3), 353–372.CrossRef
6.
Zheng, B., Lee, W.-C., & Lee, D. L. (2003). Spatial index on air. In Proceedings of Pervasive Computing and Communication (PerCom), pp. 297–304.
7.
Lee, W.-C., & Zheng, B. (2005). DSI: A fully distributed spatial index for location-based wireless broadcast services. In Proceedings of International Conference on Distributed Computing Systems (ICDCS), pp. 349–358.
8.
Saltenis, S., Jensen, C. S., Leutenegger, S. T., & Lopez, M. A. (2000). Indexing the positions of continuously moving objects. In Proceedings of International Conference on Management of Data (SIGMOD), pp. 331–342.
9.
Hu, H., Xu, J., & Lee, D. L. (2005). A generic framework for monitoring continuous spatial queries over moving objects. In Proceedings of International Conference on Management of Data (SIGMOD), pp. 479–490.
10.
Tao, Y., & Papadias, D. (2003). Spatial queries in dynamic environments. ACM Transactions on Database Systems, 28(2), 101–139.CrossRef
11.
Mouratidis, K., Papadias, D., Bakiras, S., & Tao, Y. (2005). A threshold-based algorithm for continuous monitoring of k nearest neighbors. IEEE Transactions on Knowledge and Data Engineering, 17(11), 1451–1464.CrossRef
12.
Mokbel, M. F. (2004). Continuous query processing in spatio-temporal databases. In Proceedings of International Conference on Extending Database Technology (EDBT), pp. 100–111.
13.
Prasad Sistla, A., Wolfson, O., Chamberlain, S., & Dao, S. (1997). Modeling and querying moving objects. In Proceedings of International Conference on Data Engineering (ICDE), pp. 422–432.
14.
Song, Z., & Roussopoulos, N. (2001). K-nearest neighbor search for moving query point. In Proceedings of Symposium on Spatial and Temporal Databases (SSTD), pp. 79–96.
15.
Zhang, J., Zhu, M., Papadias, D., Tao, Y., & Lee, D. L. (2003). Location-based spatial queries. In Proceedings of International Conference on Management of Data (SIGMOD), pp. 443–454.
16.
Zheng, B., & Lee, D. L. (2001). Semantic caching in location-dependent query processing. In Proceedings of Symposium on Spatial and Temporal Databases (SSTD), pp. 97–116.
17.
Gedik, B., & Liu, L. (2004). MobiEyes: Distributed processing of continuously moving queries on moving objects in a mobile system. In Proceedings of International Conference on Extending Database Technology (EDBT), pp. 67–87.
18.
Xiong, X., Mokbel, M. F., & Aref, W. G. (2005). SEA-CNN: Scalable processing of continuous k-nearest neighbor queries in spatio-temporal databases. In Proceedings of International Conference on Data Engineering (ICDE), pp. 643–654.
19.
Prabhakar, S., Xia, Y., Kalashnikov, D., Aref, W. G., & Hambrusch, S. E. (2002). Query indexing and velocity constrained indexing: Scalable techniques for continuous queries on moving objects. IEEE Transactions on Computers, 51(10), 1124–1140.
20.
Zheng, B., Lee, W.-C., & Lee, D. L. (2004). Search continuous nearest neighbors on the air. In Proceedings of International Conference on Mobile and Ubiquitous Systems (MobiQuitous), pp. 236–245.
21.
Hambrusch, S. E., Liu, E., Aref, W. G., & Prabhakar, S. (2001). Query processing in broadcasted spatial index trees. In Proceedings of Symposium on Spatial and Temporal Databases (SSTD), pp. 502–521.
22.
Zheng, B., Lee, W.-C., & Lee, D. L. (2007). On searching continuous k nearest neighbors in wireless data broadcast systems. IEEE Transactions on Mobible Computing, 6(7), 748–761.CrossRef
23.
Park, K., Song, M., & Hwang, C.-S. (2006). Adaptive data dissemination schemes for location-aware mobile services. Journal of Systems and Software, 79(5), 674–688.CrossRef
24.
Park, K., & Choo, H. (2007). Energy-efficient data dissemination schemes for nearest neighbor query processing. IEEE Transactions on Computers, 56(6), 754–768.CrossRefMathSciNet
25.
Zheng, B., & Lee, D. L. (2005). Information dissemination via wireless broadcast. Communications of the ACM, 48(5), 105–110.CrossRef
26.
Guttman, A. (1984). R-trees: A dynamic index structure for spatial searching. In Proceedings of International Conference on Management of Data (SIGMOD), pp. 47–57.
27.
Xu, J., Zheng, B., Lee, W.-C., & Lee, D. L. (2004). D-tree: An index structure for planar point queries in location-based wireless services. IEEE Transactions on Knowledge and Data Engineering, 16(12), 1526–1542.CrossRef
28.
Shih, E., Cho, S.-H., Ickes, N., Min, R., Sinha, A., Wang, A., & Chandrakasan, A. (2001). Physical layer driven protocol and algorithm design for energy-efficient wireless sensor networks. In Proceedings of International Conference on Mobile Computing and Networking (MOBICOM), pp. 272–287.
29.
Lu, G., Krishnamachari, B., & Raghavendra, C. S. (2004). An adaptive energy-efficient and low-latency MAC for data gathering in sensor networks. In Proceedings of International Workshop on Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks (WMAN), pp. 1–12.
30.
Ruzzelli, A. G., O’Hare, G. M. P., Tynan, R., Cotan, P., & Havinga, P. J. M. (2006). Protocol assessment issues in low duty cycle sensor networks: The switching energy. In Proceedings of International Conference on Sensor Networks, Ubiquitous, and. Trustworthy Computing (SUTC), pp. 136–143.
31.
Kollios, G., Gunopulos, D., & Tsotras, V. J. (1999). On indexing mobile objects. In Proceedings of Symposium on Principles of Database Systems (PODS), pp. 261–272.
32.
Tao, Y., Papadias, D., & Shen, Q. (2002). Continuous nearest neighbor search. In Proceedings of international Conference on Very Large Data Bases (VLDB), pp. 287–298.
33.
Camp, T., Boleng, J., & Davies, V. (2002). A survey of mobility models for ad hoc network research. Wireless Communication and Mobile Computing, 2(5), 483–502.CrossRef
34.
Metadaten
Titel
A scalable energy-efficient continuous nearest neighbor search in wireless broadcast systems
verfasst von
Kwangjin Park
Hyunseung Choo
Patrick Valduriez
Publikationsdatum
01.05.2010
Verlag
Springer US
Erschienen in
Wireless Networks / Ausgabe 4/2010
Print ISSN: 1022-0038
Elektronische ISSN: 1572-8196
DOI
https://doi.org/10.1007/s11276-009-0185-y

Weitere Artikel der Ausgabe 4/2010

Wireless Networks 4/2010 Zur Ausgabe

OriginalPaper

Packet data messaging over TETRA: network performance analysis

OriginalPaper

TDMA scheduling algorithms for wireless sensor networks

OriginalPaper

A channel preemption model for vertical handoff in a WLAN-embedded cellular network

OriginalPaper

Modeling and analysis of intrusion detection integrated with batch rekeying for dynamic group communication systems in mobile ad hoc networks

OriginalPaper

Achieving robust message authentication in sensor networks: a public-key based approach

OriginalPaper

Power saving with p-persistent sleep decision for wireless communications