Top

Soft Computing

Published in:

09-09-2015 | Focus

Efficient cluster-based top-k query routing with data replication in MANETs

Authors: Daichi Amagata, Takahiro Hara, Yuya Sasaki, Shojiro Nishio

Published in: Soft Computing | Issue 15/2017

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Top-k queries, which retrieve k data items with the best score, have been receiving considerable attention because they can support many real life applications. In this paper, we propose an efficient query routing scheme in mobile ad hoc networks (MANETs), namely CTR. CTR enables top-k data retrieval by only necessary nodes by employing a new clustering framework for top-k query processing. In this framework, nodes holding high rank data items become ClusterHeads (CHs), and top-k queries are transmitted between CHs via gateway nodes which belong to multiple clusters. Each CH maintains a set of hop counts between itself and high rank data items, so that it can judge whether or not to transmit a query on the fly. We further propose a query routing method, CTR\(^{2}\), which integrates the clustering framework of CTR and a data replication approach. CTR\(^{2}\) improves the performance by retrieving the top-k data from nearby nodes. Extensive experiments have demonstrated that the proposed approaches function well in terms of accuracy of the query result, traffic, and delay.

previous article Special issue on intelligent analytics and management of mobile data and social media

next article A single-directional influence topic model using call and proximity logs simultaneously

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

We define “hop count” here as the number of GWs which relay a query message to a particular CH. In Fig. 2, the hop-count from A to H, B, and X is 1, 0, and 2 respectively.

http://www.scalable-networks.com/.

Akbarinia R, Pacitti E, Valduriez P (2006) Reducing network traffic in unstructured p2p systems using top-k queries. Distrib Parallel Databases 19(2):67–86

Akbarinia R, Pacitti E, Valduriez P (2007) Best position algorithms for top-k queries. In: VLDB, pp 495–506

Amagata D, Sasaki Y, Hara T, Nishio S (2013a) A robust routing method for top-k queries in mobile ad hoc networks. In: MDM, pp 251–256

Amagata D, Sasaki Y, Hara T, Nishio S (2013b) A routing method for top-k query processing in mobile ad hoc networks. In: AINA, pp 161–168

Amagata D, Sasaki Y, Hara T, Nishio S (2014) CTR: an efficient cluster-based top-k query routing in manets. In: MoMM, pp 225–234

Basu P, Khan N, Little TD (2001) A mobility based metric for clustering in mobile ad hoc networks. In: ICDCS workshop, pp 413–418

Buckley C, Voorhees EM (2000) Evaluating evaluation measure stability. In: SIGIR, pp 33–40

Camp T, Boleng J, Davies V (2002) A survey of mobility models for ad hoc network research. Wirel Commun Mob Comput 2(5):483–502CrossRef

Cao P, Wang Z (2004) Efficient top-k query calculation in distributed networks. In: PODC, pp 206–215

Chen B, Liang W, Zhou R, Yu JX (2010) Energy-efficient top-k query processing in wireless sensor networks. In: CIKM, pp 115–122

Chen B, Liang W, Min G (2011) Top-k query evaluation in sensor networks with the guaranteed accuracy of query results. In: DEXA, pp 156–171

Chinara S, Rath SK (2009) A survey on one-hop clustering algorithms in mobile ad hoc networks. J Netw Syst Manag 17(1–2):183–207CrossRef

Chow CY, Leong HV, Chan AT (2007) Grococa: group-based peer-to-peer cooperative caching in mobile environment. IEEE J Sel Areas Commun 25(1):179–191CrossRef

Cugola G, Migliavacca M (2009) A context and content-based routing protocol for mobile sensor networks. In: Wireless sensor networks, pp 69–85

Das G, Gunopulos D, Koudas N, Sarkas N (2007) Ad-hoc top-k query answering for data streams. In: VLDB, pp 183–194

Ephremides A, Wieselthier JE, Baker DJ (1987) A design concept for reliable mobile radio networks with frequency hopping signaling. Proc IEEE 75(1):56–73CrossRef

Fiore M, Mininni F, Casetti C, Chiasserini C (2009) To cache or not to cache? In: INFOCOM, pp 235–243

Fiore M, Casetti C, Chiasserini C (2011) Caching strategies based on information density estimation in wireless ad hoc networks. IEEE TVT 60(5):2194–2208

Hagihara R, Shinohara M, Hara T, Nishio S (2009) A message processing method for top-k query for traffic reduction in ad hoc networks. In: MDM, pp 11–20

Hara T (2001) Effective replica allocation in ad hoc networks for improving data accessibility. INFOCOM 3:1568–1576

Hara T, Hagihara R, Nishio S (2010) Data replication for top-k query processing in mobile wireless sensor networks. In: SUTC, pp 115–122

Huang Z, Jensen CS, Lu H, Ooi BC (2007) Collaborative spatial data sharing among mobile lightweight devices. In: SSTD, pp 366–384

Ilyas IF, Beskales G, Soliman MA (2008) A survey of top-k query processing techniques in relational database systems. ACM Comput Surv (CSUR) 40(4):11CrossRef

Jiang H, Cheng J, Wang D, Wang C, Tan G (2011) Continuous multi-dimensional top-k query processing in sensor networks. In: INFOCOM, pp 793–801

Lee SB, Wong SHY, Lee KW, Lu S (2011) Content management in a mobile ad hoc network: beyond opportunistic strategy. In: INFOCOM, pp 266–270

Lim S, Lee WC, Cao G, Das CR (2006) A novel caching scheme for improving internet-based mobile ad hoc networks performance. Ad Hoc Netw 4(2):225–239CrossRef

Liu X, Xu J, Lee WC (2010) A cross pruning framework for top-k data collection in wireless sensor network. In: MDM, pp 157–166

Menchaca-Mendez R, Garcia-Luna-Aceves J (2008) An interest-driven approach to integrated unicast and multicast routing in manets. In: ICNP, pp 248–257

Menchaca-Mendez R, Garcia-Luna-Aceves J (2010) Robust and scalable integrated routing in manets using context-aware ordered meshes. In: INFOCOM, pp 1–9

Michel S, Peter T, Weikum G (2005) Klee: a framework for distributed top-k query algorithms. In: VLDB, pp 637–648

Mottola L, Cugola G, Picco GP (2008) A self-repairing tree topology enabling content-based routing in mobile ad hoc networks. IEEE TMC 7(8):946–960

Niedermayer J, Nascimento MA, Renz M, krøger P, Kriegel HP (2010) Exploiting local node cache in top-k queries within wireless sensor networks. In: ACM Sigspatial GIS, pp 434–437

Padhariya N, Mondal A, Goyal V, Shankar R, Madria S (2011) Ecotop: an economic model for dynamic processing of top-k queries in mobile-p2p networks. In: DASFAA, pp 251–265

Padmanabhan P, Gruenwald L, Vallur A, Atiquzzaman M (2008) A survey of data replication techniques for mobile ad hoc network databases. VLDB J 17(5):1143–1164CrossRef

Parekh AK (1994) Selecting routers in ad-hoc wireless networks. In: Proceedings of the international telecommunications symposium, pp 420–424

Royer EM, Perkins CE (1999) Multicast operation of the ad-hoc on-demand distance vector routing protocol. In: Mobicom, pp 207–218

Sasaki Y, Hagihara R, Hara T, Shinohara M, Nishio S (2010) A top-k query method by estimating score distribution in mobile ad hoc networks. In: AINA workshop, pp 944–949

Sasaki Y, Hara T, Nishio S (2011) Two-phase top-k query processing in mobile ad hoc networks. In: NBiS, pp 42–49

Sasaki Y, Hara T, Nishio S (2014) Top-k query processing for replicated data in mobile peer to peer networks. J Syst Softw 92:45–58CrossRef

Tang B, Gupta H, Das SR (2008) Benefit-based data caching in ad hoc networks. IEEE TMC 7(3):289–304

Torkestani JA, Meybodi MR (2011) A mobility-based cluster formation algorithm for wireless mobile ad-hoc networks. Clust Comput 14(4):311–324CrossRef

Tseng YC, Ni SY, Chen YS, Sheu JP (2002) The broadcast storm problem in a mobile ad hoc network. Wirel Netw 8(2–3):153–167CrossRefMATH

Vlachou A, Doulkeridis C, Nørvåg K, Vazirgiannis M (2008) On efficient top-k query processing in highly distributed environments. In: SIGMOD, pp 753–764

Vlachou A, Doulkeridis C, Nørvåg K (2012) Distributed top-k query processing by exploiting skyline summaries. Distrib Parallel Databases 30(3–4):239–271CrossRef

Wu M, Jianliang XuJ, Xueyan Tang X, Wang-Chien Lee WC (2007) Top-k monitoring in wireless sensor networks. IEEE TKDE 7:962–976

Yang W, Zhang G (2007) A weight-based clustering algorithm for mobile ad hoc network. In: International conference on wireless and mobile communications, p 3

Yin L, Cao G (2006) Supporting cooperative caching in ad hoc networks. IEEE TMC 5(1):77–89

Yoo S, Son JH, Kim MH (2009) A scalable publish/subscribe system for large mobile ad hoc networks. J Syst Softw 82(7):1152–1162CrossRef

Zhu Q, Lee DL, Lee WC (2011) Collaborative caching for spatial queries in mobile p2p networks. In: ICDE, pp 279–290

Title: Efficient cluster-based top-k query routing with data replication in MANETs
Authors: Daichi Amagata
Takahiro Hara
Yuya Sasaki
Shojiro Nishio
Publication date: 09-09-2015
Publisher: Springer Berlin Heidelberg
Published in: Soft Computing / Issue 15/2017
Print ISSN: 1432-7643
Electronic ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-015-1867-2

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 15/2017

Tense operators on non-commutative residuated lattices

An improved NSGA-III algorithm based on objective space decomposition for many-objective optimization

Privacy-preserving outsourcing of image feature extraction in cloud computing

A new cuckoo search algorithm with hybrid strategies for flow shop scheduling problems

Lyapunov stability-based control and identification of nonlinear dynamical systems using adaptive dynamic programming

Sparse representation-based classification using generalized weighted extended dictionary

Premium Partner