More Web Proxy on the site http://driver.im/

article

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

Authors:

Daichi Amagata,

Shojiro NishioAuthors Info & Claims

Soft Computing - A Fusion of Foundations, Methodologies and Applications, Volume 21, Issue 15

Pages 4161 - 4178

https://doi.org/10.1007/s00500-015-1867-2

Published: 01 August 2017 Publication History

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}$$2, which integrates the clustering framework of CTR and a data replication approach. CTR$$^{2}$$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.

References

[1]

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

Digital Library

[2]

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

Digital Library

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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-207

Digital Library

[13]

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-191

Digital Library

[14]

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

Digital Library

[15]

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

[16]

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

[17]

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

[18]

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

[19]

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

[20]

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

[21]

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

[22]

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

[23]

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):11

Digital Library

[24]

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

[25]

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

[26]

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-239

Digital Library

[27]

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

[28]

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

[29]

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

[30]

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

[31]

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

[32]

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

[33]

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

[34]

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-1164

Digital Library

[35]

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

[36]

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

[37]

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

[38]

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

[39]

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-58

[40]

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

[41]

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

[42]

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-167

Digital Library

[43]

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

[44]

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-271

Digital Library

[45]

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

[46]

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

[47]

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

[48]

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

Digital Library

[49]

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

Cited By

Alghamdi S(2020)Three-Tier Architecture Supporting QoS Multimedia Routing in Cloud-Assisted MANET with 5G Communication (TCM5G)Mobile Networks and Applications10.1007/s11036-020-01657-625:6(2206-2225)Online publication date: 1-Dec-2020
https://dl.acm.org/doi/10.1007/s11036-020-01657-6
Bhaskar NKumar P(2020)Optimal processing of nearest-neighbor user queries in crowdsourcing based on the whale optimization algorithmSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-020-04722-024:17(13037-13050)Online publication date: 1-Sep-2020
https://dl.acm.org/doi/10.1007/s00500-020-04722-0

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

Recommendations

Link Lifetime-Based Segment-by-Segment Routing Protocol in MANETs
ISPA '08: Proceedings of the 2008 IEEE International Symposium on Parallel and Distributed Processing with Applications

Node mobility is one of the most important factors that may degrade network performance and restrict network scalability in mobile ad hoc networks. An effective way to reduce the impact of node mobility is to select long lifetime routing paths in the ...
Energy efficient zone based routing protocol for MANETs

Mobile Ad Hoc Networks (MANET) are self-configuring infrastructureless networks of mobile devices connected via wireless links. Each device can send and receive data, but it should also forward traffic unrelated to its own use. All need to maintain ...
CTR: An Efficient Cluster-based Top-k Query Routing in MANETs
MoMM '14: Proceedings of the 12th International Conference on Advances in Mobile Computing and Multimedia

Top-k queries, which retrieve the k data items with the highest scores, have been receiving considerable attention because of their utility for many real life applications. In this paper, we propose an efficient query routing scheme enabling top-k data ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Soft Computing - A Fusion of Foundations, Methodologies and Applications

Soft Computing - A Fusion of Foundations, Methodologies and Applications Volume 21, Issue 15

August 2017

330 pages

ISSN:1432-7643

EISSN:1433-7479

Issue’s Table of Contents

Copyright © Copyright © 2017 Springer-Verlag GmbH Germany.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 August 2017

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Alghamdi S(2020)Three-Tier Architecture Supporting QoS Multimedia Routing in Cloud-Assisted MANET with 5G Communication (TCM5G)Mobile Networks and Applications10.1007/s11036-020-01657-625:6(2206-2225)Online publication date: 1-Dec-2020
https://dl.acm.org/doi/10.1007/s11036-020-01657-6
Bhaskar NKumar P(2020)Optimal processing of nearest-neighbor user queries in crowdsourcing based on the whale optimization algorithmSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-020-04722-024:17(13037-13050)Online publication date: 1-Sep-2020
https://dl.acm.org/doi/10.1007/s00500-020-04722-0

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents