Commenced in January 2007
Frequency: Monthly
Edition: International
Paper Count: 4

minimum spanning tree Related Abstracts

4 A Lifetime-Enhancing Monitoring Node Distribution Using Minimum Spanning Tree in Mobile Ad Hoc Networks

Authors: Sungchul Ha, Hyunwoo Kim


In mobile ad hoc networks, all nodes in a network only have limited resources and calculation ability. Therefore communication topology which have long lifetime is good for all nodes in mobile ad hoc networks. There are a variety of researches on security problems in wireless ad hoc networks. The existing many researches try to make efficient security schemes to reduce network power consumption and enhance network lifetime. Because a new node can join the network at any time, the wireless ad hoc networks are exposed to various threats and can be destroyed by attacks. Resource consumption is absolutely necessary to secure networks, but more resource consumption can be a critical problem to network lifetime. This paper focuses on efficient monitoring node distribution to enhance network lifetime in wireless ad hoc networks. Since the wireless ad hoc networks cannot use centralized infrastructure and security systems of wired networks, a new special IDS scheme is necessary. The scheme should not only cover all nodes in a network but also enhance the network lifetime. In this paper, we propose an efficient IDS node distribution scheme using minimum spanning tree (MST) method. The simulation results show that the proposed algorithm has superior performance in comparison with existing algorithms.

Keywords: Power Control, MANETs, IDS, minimum spanning tree

Procedia PDF Downloads 220
3 A Kruskal Based Heuxistic for the Application of Spanning Tree

Authors: Anjan Naidu


In this paper we first discuss the minimum spanning tree, then we use the Kruskal algorithm to obtain minimum spanning tree. Based on Kruskal algorithm we propose Kruskal algorithm to apply an application to find minimum cost applying the concept of spanning tree.

Keywords: Algorithm, Application, minimum spanning tree, Heuxistic, classification of Sub 97K90

Procedia PDF Downloads 290
2 A Minimum Spanning Tree-Based Method for Initializing the K-Means Clustering Algorithm

Authors: X. Zhang, J. Yang, Y. Ma, S. Li, Y. Zhang


The traditional k-means algorithm has been widely used as a simple and efficient clustering method. However, the algorithm often converges to local minima for the reason that it is sensitive to the initial cluster centers. In this paper, an algorithm for selecting initial cluster centers on the basis of minimum spanning tree (MST) is presented. The set of vertices in MST with same degree are regarded as a whole which is used to find the skeleton data points. Furthermore, a distance measure between the skeleton data points with consideration of degree and Euclidean distance is presented. Finally, MST-based initialization method for the k-means algorithm is presented, and the corresponding time complexity is analyzed as well. The presented algorithm is tested on five data sets from the UCI Machine Learning Repository. The experimental results illustrate the effectiveness of the presented algorithm compared to three existing initialization methods.

Keywords: minimum spanning tree, degree, k-means, initial cluster center

Procedia PDF Downloads 211
1 Surface Deformation Studies in South of Johor Using the Integration of InSAR and Resistivity Methods

Authors: Sirajo Abubakar, Ismail Ahmad Abir, Muhammad Sabiu Bala, Muhammad Mustapha Adejo, Aravind Shanmugaveloo


Over the years, land subsidence has been a serious threat mostly to urban areas. Land subsidence is the sudden sinking or gradual downward settling of the ground’s surface with little or no horizontal motion. In most areas, land subsidence is a slow process that covers a large area; therefore, it is sometimes left unnoticed. South of Johor is the area of interest for this project because it is going through rapid urbanization. The objective of this research is to evaluate and identify potential deformations in the south of Johor using integrated remote sensing and 2D resistivity methods. Synthetic aperture radar interferometry (InSAR) which is a remote sensing technique has the potential to map coherent displacements at centimeter to millimeter resolutions. Persistent scatterer interferometry (PSI) stacking technique was applied to Sentinel-1 data to detect the earth deformation in the study area. A dipole-dipole configuration resistivity profiling was conducted in three areas to determine the subsurface features in that area. This subsurface features interpreted were then correlated with the remote sensing technique to predict the possible causes of subsidence and uplifts in the south of Johor. Based on the results obtained, West Johor Bahru (0.63mm/year) and Ulu Tiram (1.61mm/year) are going through uplift due to possible geological uplift. On the other end, East Johor Bahru (-0.26mm/year) and Senai (-1.16mm/year) undergo subsidence due to possible fracture and granitic boulders loading. Land subsidence must be taken seriously as it can cause serious damages to infrastructures and human life. Monitoring land subsidence and taking preventive actions must be done to prevent any disasters.

Keywords: resistivity, minimum spanning tree, subsidence, interferometric synthetic aperture radar, persistent scatter

Procedia PDF Downloads 1