Date of Completion
Dr. Reda Ammar; Dr. Zheng Peng
Field of Study
Computer Science and Engineering
Master of Science
Social networks and sensor networks are two very different types of networks that have been made possible by modern technology. Portable wireless devices, including laptops and cell phones, have made social networks part of our daily lives. Similarly, cheap, fast, portable devices are ideal for sensor networks. The common thread is the underlying graph structure, which is decentralized and can naturally form groups. However, human groups are messy, and can best be modeled by graph clusters that can be allowed to overlap with each other. We apply this idea to the identification of pre-existing groups as well as discovering a group structure for routing.
In this thesis, we present a method for clustering a graph that allows the clusters to overlap. We developed an implementation of the clustering algorithm which allows us to examine its properties. We present analysis of the properties of the clusterings. We also present an analysis of the algorithm's ability to recognize node groups that overlap, based only on the graph structure. In addition, we present a routing algorithm for sensor networks to reduce transmission costs for sensors communicating with a base station. The routing algorithm uses the results of the clustering algorithm to perform hierarchical routing by taking advantage of the nodes that overlap in the clustering. We then present an analysis of the routing algorithm based on simulations.
Adelson, Jonathan, "A Method for Network Clustering and Cluster Based Routing" (2013). Master's Theses. 434.
Dr. Jun-Hong Cui