UM E-Theses Collection (澳門大學電子學位論文庫)

check Full Text

Extended Kamada-Kawai for unfolding and boundary node detection in ad hoc network

English Abstract

Extended Kamada-Kawai for Unfolding and Boundary Node Detection in Ad Hoc Network by Cheong Se Hang Thesis Supervisor: Dr. Yain Whar SI, Lawrence Master of E-Commerce Technology 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. Complex non-convex ad hoc networks (CNCAH) contain intersecting polygons and edges. In many instances, the layouts of these networks are also not entirely convex in shape. To address these problems, this thesis proposes an improved version of the Kamada-Kawai algorithm. The proposed extension includes novel heuristics and algorithms that achieve a faster energy level reduction. We also propose a novel approach to detect and unfold stacked regions in CNCAH networks. Experiment results show that the proposed algorithms can achieve fast convergence on boundary node detection in CNCAH networks and able to successfully unfold stacked regions.

Issue date



Cheong, Se Hang


Faculty of Science and Technology


Department of Computer and Information Science




Ad hoc networks (Computer networks) -- Mathematical models


Si, Yain Whar

Files In This Item

Full-text (Intranet only)

1/F Zone C
Library URL