Accelerating the Kamada-Kawai Algorithm for Boundary Detection in a Mobile Ad Hoc Network
Authors:
Open Access
- 19 December 2016
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Sensor Networks
- Vol. 13 (1) , 1-29
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.Keywords
All Related Versions
Funding Information
- Research Committee of University of Macau (MYRG2015-00054-FST and MYRG2016-00148-FST)
This publication has 19 references indexed in Scilit:
- Power efficient range-free localization algorithm for wireless sensor networksWireless Networks, 2013
- Force-directed approaches to sensor localizationACM Transactions on Sensor Networks, 2010
- On boundary recognition without location information in wireless sensor networksACM Transactions on Sensor Networks, 2010
- Localised alpha-shape computations for boundary recognition in sensor networksAd Hoc Networks, 2009
- Localised convex hulls to identify boundary nodes in sensor networksInternational Journal of Sensor Networks, 2009
- A multi-dimensional approach to force-directed layouts of large graphsComputational Geometry, 2004
- Drawing graphs nicely using simulated annealingACM Transactions on Graphics, 1996
- Graph drawing by force‐directed placementSoftware: Practice and Experience, 1991
- An algorithm for drawing general undirected graphsInformation Processing Letters, 1989
- On the shape of a set of points in the planeIEEE Transactions on Information Theory, 1983