Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
The Journal of Supercomputing
Published in: The Journal of Supercomputing 10/2018

24-07-2018

CWBound: boundary node detection algorithm for complex non-convex mobile ad hoc networks

Authors: Se-Hang Cheong, Yain-Whar Si

Published in: The Journal of Supercomputing | Issue 10/2018

Log in

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

search-config
loading …

Abstract

Efficient message forwarding in mobile ad hoc network in disaster scenarios is challenging because location information on the boundary and interior nodes is often unavailable. Information related to boundary nodes can be used to design efficient routing protocols as well as to prolong the battery power of devices along the boundary of an ad hoc network. In this article, we developed an algorithm, CWBound, which discovers boundary nodes in a complex non-convex mobile ad hoc (CNCAH) networks. Experiments show that the CWBound algorithm is at least three times faster than other state-of-the-art algorithms, and up to 400 times faster than classical force-directed algorithms. The experiments also confirmed that the CWBound algorithm achieved the highest accuracy (above 97% for 3 out of the 4 types of CNCAH networks) and sensitivity (90%) among the algorithms evaluated.
previous article A stochastic link-fault-tolerant routing algorithm in folded hypercubes
next article PL-DVFS: combining Power-aware List-based scheduling algorithm with DVFS technique for real-time tasks in Cloud Computing

Dont have a licence yet? Then find out more about our products and how to get one 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

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
Appendix
Available only for authorised users
Footnotes
Literature
1.
Akyildiz IF, Su W, Sankarasubramaniam Y, Cayirci E (2002) A survey on sensor networks. IEEE Commun Mag 40(8):102CrossRef
2.
Solmaz G, Turgut D (2017) Tracking pedestrians and emergent events in disaster areas. J Netw Comput Appl 84:55CrossRef
3.
MartíN-Campillo A, Crowcroft J, Yoneki E, Martí R (2013) Evaluating opportunistic networks in disaster scenarios. J Netw Comput Appl 36(2):870CrossRef
4.
Cheong SH, Lee KI, Si YW et al (2011) Lifeline: emergency ad hoc network. In: Computational Intelligence and Security (CIS), 2011 Seventh International Conference on. IEEE, pp 283–289
5.
Mauve M, Widmer J, Hartenstein H (2001) A survey on position-based routing in mobile ad hoc networks. IEEE Netw 15(6):30CrossRef
6.
Phoummavong P, Utsu K, Chow CO, Ishii H (2016) Location-aided route discovery mechanism based on two-hop neighbor information for ad hoc network. J Supercomput 72(3):1201CrossRef
7.
Efrat A, Forrester D, Iyer A, Kobourov SG, Erten C, Kilic O (2010) Force-directed approaches to sensor localization. ACM Trans Sens Netw (TOSN) 7(3):27
8.
Cheong SH, Si YW (2016) Accelerating the Kamada–Kawai algorithm for boundary detection in a mobile ad hoc network. ACM Trans Sens Netw (TOSN) 13(1):3
9.
Schieferdecker D (2014) An algorithmic view on sensor networks: surveillance, localization, and communication (epubli)
10.
Rafiei A, Abolhasan M, Franklin D, Safaei F (2011) Boundary node selection algorithms in WSNs. In: Local Computer Networks (LCN), 2011 IEEE 36th Conference on. IEEE, pp 251–254
11.
Sahoo PK, Hsieh KY, Sheu JP (2007) Boundary node selection and target detection in wireless sensor network. In: Wireless and Optical Communications Networks, 2007. WOCN’07. IFIP International Conference on. IEEE, pp 1–5
12.
Fruchterman TM, Reingold EM (1991) Graph drawing by force-directed placement. Softw Pract Exp 21(11):1129CrossRef
13.
14.
Davidson R, Harel D (1996) Drawing graphs nicely using simulated annealing. ACM Trans Graph (TOG) 15(4):301CrossRef
15.
Bresenham J, Earnshaw R, Pitteway M (1991) Fundamental algorithms for computer graphics. Springer, Berlin
16.
Saukh O, Sauter R, Gauger M, Marrón PJ (2010) On boundary recognition without location information in wireless sensor networks. ACM Trans Sens Netw (TOSN) 6(3):20
17.
Huang B, Wu W, Gao G, Zhang T (2014) Recognizing boundaries in wireless sensor networks based on local connectivity information. Int J Distrib Sens Netw 10(7):897039CrossRef
18.
Wang Y, Gao J, Mitchell JS (2006) Boundary recognition in sensor networks by topological methods. In: Proceedings of the 12th Annual International Conference on Mobile Computing and Networking. ACM, pp 122–133
19.
Zhang C, Zhang Y, Fang Y (2006) Detecting coverage boundary nodes in wireless sensor networks. In: Networking, Sensing and Control, 2006. ICNSC’06. Proceedings of the 2006 IEEE International Conference on. IEEE, pp 868–873
20.
Aurenhammer F (1991) Voronoi diagrams—a survey of a fundamental geometric data structure. ACM Comput Surv (CSUR) 23(3):345CrossRef
21.
22.
Beghdad R, Lamraoui A (2016) Boundary and holes recognition in wireless sensor networks. J Innov Digit Ecosyst 3(1):1CrossRef
23.
24.
Völker M, Wagner D, Schmid J, Gädeke T, Müller-Glaser K (2012) Force-directed tracking in wireless networks using signal strength and step recognition. In: Localization and GNSS (ICL-GNSS), 2012 International Conference on. IEEE, pp 1–8
25.
Park JW, Park DH, Lee C (2013) Angle and ranging based localization method for ad hoc network. J Supercomput 64(2):507CrossRef
26.
De Nooy W, Mrvar A, Batagelj V (2011) Exploratory social network analysis with Pajek, vol 27. Cambridge University Press, CambridgeCrossRef
27.
Chimani M, Gutwenger C, Jünger M, Klau GW, Klein K, Mutzel P (2013) The open graph drawing framework (OGDF). In: Handbook of graph drawing and visualization 2011, p 543
28.
Darabkh KA, Albtoush WY, Jafar IF (2017) Improved clustering algorithms for target tracking in wireless sensor networks. J Supercomput 73(5):1952CrossRef
29.
Jacomy M, Venturini T, Heymann S, Bastian M (2014) ForceAtlas2, a continuous graph layout algorithm for handy network visualization designed for the Gephi software. PLoS ONE 9(6):e98679CrossRef
30.
Fjällström PO (1998) Algorithms for graph partitioning: a survey, vol 3. Linköping University Electronic Press, Linköping
31.
Schloegel K, Karypis G, Kumar V (2003) Graph partitioning for high-performance scientific simulations. In: Dongarra J, Foster I, Fox G, Gropp W, Kennedy K, Torczon L, White A (eds) Sourcebook of parallel computing. Morgan Kaufmann Publishers Inc., San Francisco, CA, pp 491–541
32.
33.
Safro I, Sanders P, Schulz C (2015) Advanced coarsening schemes for graph partitioning. J Exp Algorithmics (JEA) 19:2MathSciNetMATH
34.
Noack A (2007) Unified quality measures for clusterings, layouts, and orderings of graphs, and their application as software design criteria. Ph.D. thesis, Brandenburg University of Technology, Cottbus-Senftenberg
35.
Enderle JD, Bronzino JD (2012) Introduction to biomedical engineering. Academic Press, New York
36.
Gajer P, Goodrich MT, Kobourov SG (2004) A multi-dimensional approach to force-directed layouts of large graphs. Comput Geom 29(1):3MathSciNetCrossRef
37.
Biemann C (2006) Chinese Whispers: an efficient graph clustering algorithm and its application to natural language processing problems. In: Proceedings of the first workshop on graph based methods for natural language processing. Association for Computational Linguistics, pp 73–80
38.
Bracewell DB, Tomlinson MT, Mohler M (2013) Determining the conceptual space of metaphoric expressions. In: International Conference on Intelligent Text Processing and Computational Linguistics. Springer, Berlin, Heidelberg, pp 487–500CrossRef
Metadata
Title
CWBound: boundary node detection algorithm for complex non-convex mobile ad hoc networks
Authors
Se-Hang Cheong
Yain-Whar Si
Publication date
24-07-2018
Publisher
Springer US
Published in
The Journal of Supercomputing / Issue 10/2018
Print ISSN: 0920-8542
Electronic ISSN: 1573-0484
DOI
https://doi.org/10.1007/s11227-018-2494-3

Other articles of this Issue 10/2018

The Journal of Supercomputing 10/2018 Go to the issue

OriginalPaper

Continuous memory allocation model for cloud services

OriginalPaper

CDCSS: cluster-based distributed cooperative spectrum sensing model against primary user emulation (PUE) cyber attacks

OriginalPaper

Infrequent pattern mining in smart healthcare environment using data summarization

OriginalPaper

A machine learning approach for feature selection traffic classification using security analysis

OriginalPaper

An efficient approach for publishing microdata for multiple sensitive attributes

OriginalPaper

Design of DRAM-NAND flash hybrid main memory and Q-learning-based prefetching method

Premium Partner

    Image Credits