Clustering prediction for the ID-based clustering algorithm
MetadataShow full item record
The field of clustering offers a very promising benefit to the field of multi-agent sensor networks. Within sensor networks, clustering is essential in creating a hierarchical structure to ad-hoc systems. Furthermore, in order to determine the necessary performance capabilities for the participating nodes of a sensor grid, it would be helpful to have a priori knowledge of the expected number of clusters that will be formed by a given clustering algorithm. The efficiency of operation within a decentralized, distributed sensor network can be greatly improved upon with the aid of both clustering and an accurate prediction of the total number of clusters to be expected. This thesis details an analysis of the ID-Based Clustering algorithm (originally proposed by Gao et al.), an algorithm that utilizes node identification numbers as its clusterhead nomination criterion, and an attempt to determine an analytical model to accurately predict the number of clusters expected from this algorithm. The approach taken to analyzing this method utilizes techniques from probability theory and applies them to a 1-D field of length, L, populated by N sensors (or, alternatively, `nodes') that have a given radius of communication, R. The goal of the model is to predict the average number of clusters from the ID-Based Clustering algorithm knowing only N and the ratio R/L . The result of this study is a proposed model that is accurate to within 15% of a clustering average determined through analyzing trial computer simulations that emulate a one-dimensional sensor field populated with up to fifty sensors that are clustered using the ID-Based Clustering algorithm. In addition to the one-dimensional analysis presented, a two-dimensional analysis is initiated by the end of the study and an alternative to the ID- Based Clustering Algorithm dubbed the Cascade Nomination Method is introduced. Meaningful directions for future work would be to complete the two-dimensional model, improve upon the accuracy of the one-dimensional model, and perform similar analysis on the Cascade Nomination Method.