Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

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

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. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Sensor Networks (TOSN) Association for Computing Machinery

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

Download PDF
29 pages

Loading next page...
 
/lp/association-for-computing-machinery/accelerating-the-kamada-kawai-algorithm-for-boundary-detection-in-a-znUHo7yi1v
Publisher
Association for Computing Machinery
Copyright
Copyright © 2016 ACM
ISSN
1550-4859
eISSN
1550-4867
DOI
10.1145/3005718
Publisher site
See Article on Publisher Site

Abstract

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.

Journal

ACM Transactions on Sensor Networks (TOSN) – Association for Computing Machinery

Published: Dec 19, 2016

Keywords: Kamada-kawai

References

  • Information Visualization Beyond the Horizon
    Chen, C.
  • Optimal self boundary recognition with two-hop information for ad hoc networks
    Chen, Y. H.; Chung, W. H.; Ni, G. K.; Zhang, H.; Kuo, S. Y.
  • Lifeline: Emergency ad hoc network
    Cheong, S. H.; Lee, K. I.; Si, Y. W.; U., L. H.
  • Drawing graphs nicely using simulated annealing
    Davidson, R.; Harel, D.
  • Fine-grained boundary recognition in wireless ad hoc and sensor networks by topological methods
    Dong, D.; Liu, Y.; Liao, X.
  • A heuristic for graph drawing
    Eades, P.
  • On the shape of a set of points in the plane
    Edelsbrunner, H.; Kirkpatrick, D. G.; Seidel, R.
  • Force-directed approaches to sensor localization
    Efrat, A.; Forrester, D.; Iyer, A.; Kobourov, S. G.; Erten, C.; Kilic, O.
  • Locating and bypassing routing holes in sensor networks
    Fang, Q.; Gao, J.; Guibas, L. J.
  • Localised alpha-shape computations for boundary recognition in sensor networks
    Fayed, M.; Mouftah, H. T.
  • Localised convex hulls to identify boundary nodes in sensor networks
    Fayed, M.; Mouftah, H. T.
  • A new approach for boundary recognition in geometric sensor networks
    Fekete, S. P.; Kaufmann, M.; Kröller, A.; Lehmann, K.
  • Neighborhood-based topology recognition in sensor networks
    Fekete, S. P.; Kröller, A.; Pfisterer, D.; Fischer, S.; Buschmann, C.
  • Graph drawing by force-directed placement
    Fruchterman, T. M. J.; Reingold, E. M.
  • A multi-dimensional approach to force-directed layouts of large graphs
    Gajer, P.; Goodrich, M. T.; Kobourov, S. G.
  • A fast multi-scale method for drawing large graphs
    Harel, D.; Koren, Y.
  • An algorithm for drawing general undirected graphs
    Kamada, T.; Kawai, S.
  • Power efficient range-free localization algorithm for wireless sensor networks
    Kumar, S.; Lobiyal, D. K.
  • Rendered path: Range-free localization in anisotropic sensor networks with holes
    Li, M.; Liu, Y.
  • Skeleton extraction from incomplete boundaries in sensor networks based on distance transform
    Liu, W.; Jiang, H.; Bai, X.; Tan, G.; Wang, C.; Liuand, W.; Cai, K.
  • Exploratory Social Network Analysis with Pajek
    Nooy, W. D.; Mrvar, A.; Batagelj, V.
  • Boundary node selection algorithms in WSNs
    Rafiei, A.; Abolhasan, M.; Franklin, D.; Safaei, F.
  • Boundary node selection and target detection in wireless sensor network
    Sahoo, P. K.; Hsieh, K. Y.; Sheu, J. P.
  • On boundary recognition without location information in wireless sensor networks
    Saukh, O.; Sauter, R.; Gauger, M.; Marrón, P. J.
  • An Algorithmic View on Sensor Networks: Surveillance, Localization, and Communication
    Schieferdecker, D.
  • Boundary recognition in sensor networks by topological methods
    Wang, Y.; Gao, J.; Mitchell, J. S. B.