Accelerating the Kamada-Kawai Algorithm for Boundary Detection in a Mobile Ad Hoc Network

Force-directed algorithms such as the Kamada-Kawai algorithm have shown promising results for solving the boundary detection problem in a mobile ad hoc network. However, the classical Kamada-Kawai algorithm does not scale well when it is used in networks with large numbers of nodes. It also produces poor results in non-convex networks. To address these problems, this article proposes an improved version of the Kamada-Kawai algorithm. The proposed extension includes novel heuristics and algorithms that achieve a faster energy level reduction. Our experimental results show that the improved algorithm can significantly shorten the processing time and detect boundary nodes with an acceptable level of accuracy.

• Publication year

  2015

• Venue

  ACM Trans. Sens. Networks

• Publication date

  2015-08-21

• Fields of study

  Computer Science

• Identifiers
  DOI 10.1145/3005718arXiv 1508.05312
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Exploratory Social Network Analysis with Pajek: Revised and Expanded Edition for Updated Software

  2018cited by this paper
• An Algorithmic View on Sensor Networks - Surveillance, Localization, and Communication

  2014influential reference
• Power efficient range-free localization algorithm for wireless sensor networks

  2013cited by this paper
• Optimal self boundary recognition with two-hop information for ad hoc networks

  2012cited by this paper
• Skeleton Extraction from Incomplete Boundaries in Sensor Networks Based on Distance Transform

  2012cited by this paper
• Lifeline: Emergency Ad Hoc Network

  2011cited by this paper
• Boundary node selection algorithms in WSNs

  2011cited by this paper
• Localised alpha-shape computations for boundary recognition in sensor networks

  2009cited by this paper
• Localised convex hulls to identify boundary nodes in sensor networks

  2009cited by this paper
• Fine-grained boundary recognition in wireless ad hoc and sensor networks by topological methods

  2009cited by this paper
• On Boundary Recognition without Location Information in Wireless Sensor Networks

  2008cited by this paper
• Boundary Node Selection and Target Detection in Wireless Sensor Network

  2007cited by this paper
• Rendered Path: Range-Free Localization in Anisotropic Sensor Networks With Holes

  2007cited by this paper
• Information Visualization: Beyond the Horizon

  2006cited by this paper
• Boundary recognition in sensor networks by topological methods

  2006cited by this paper
• Force-directed approaches to sensor localization

  2006cited by this paper
• A New Approach for Boundary Recognition in Geometric Sensor Networks

  2005cited by this paper
• Neighborhood-Based Topology Recognition in Sensor Networks

  2004cited by this paper
• Locating and bypassing routing holes in sensor networks

  2004cited by this paper
• A multi-dimensional approach to force-directed layouts of large graphs

  2000cited by this paper
• Drawing graphs nicely using simulated annealing

  1996cited by this paper
• Global optimization and simulated annealing

  1991cited by this paper
• Graph drawing by force‐directed placement

  1991cited by this paper
• An Algorithm for Drawing General Undirected Graphs

  1989cited by this paper
• A Heuristic for Graph Drawing

  1984cited by this paper
• On the shape of a set of points in the plane

  1983cited by this paper
• Journal of Graph Algorithms and Applications a Fast Multi-scale Method for Drawing Large Graphs

  year unknowncited by this paper

• Detailed Examples of Figure Preparation in the Two Most Common Graph Layouts

  2025cites this paper
• Spatial network disintegration based on ranking aggregation

  2025cites this paper
• An image classification approach for hole detection in wireless sensor networks

  2022cites this paper
• Chemometrics in food science and technology: A bibliometric study

  2022cites this paper
• Online force-directed algorithms for visualization of dynamic graphs

  2022cites this paper
• Coverage hole detection in WSN with force-directed algorithm and transfer learning

  2021influential citation
• KOREAN JOURNAL OF ENGLISH LANGUAGE AND LINGUISTICS

  2021cites this paper
• Student Performance Based on Activity Log on Social Network and e-Learning

  2020cites this paper
• Inferring Networks of Interdependent Labor Skills to Illuminate Urban Economic Structure

  2020cites this paper
• Force-directed algorithms for schematic drawings and placement: A survey

  2019cites this paper
• Snapshot Visualization of Complex Graphs with Force-Directed Algorithms

  2018cites this paper
• CWBound: boundary node detection algorithm for complex non-convex mobile ad hoc networks

  2018influential citation