Home
Dual graph partitioning of cellular networks : inferring and quantifying the graph properties that guarantee a partition result
Results - Details
|
||||
| Identifier | 000337669 | |||
| Title | Dual graph partitioning of cellular networks : inferring and quantifying the graph properties that guarantee a partition result | |||
| Alternative Title | Εντοπισμός και ποσοτικοποίηση των ιδιοτήτων γράφου που εγγυώνται ένα αποτέλεσμα διαμέρισης | |||
| Author | Μουδάτσος, Μιχαήλ Νικολάου | |||
| Thesis advisor | Τόλλης, Ιωάννης | |||
| Abstract |
Graph partitioning is currently one of the most interesting NP-Hard problems, due to its applications in networks. Its aim is to create a specified number of groups of objects while minimizing the communication cost between these groups, which equals the sum of all edge weights whose nodes belong to different groups. Specifically, in cellular networks, the number of communication operations between cells defines the communication cost. Cells are assigned to switches, which in turn are assigned to routers. Communication between cells belonging to different switches or routers demands extensive signaling, which slows down the process. Graph partitioning aids in the assignment of cells to switch and router groups, minimizing the inter-group communications. Thus, less frequent communications will have to bear the signaling cost. There is an extensive work in the literature, proposing heuristics and comparison results on graph partitioning. Most partitioning solutions concern iterative algorithms whose performance is determined by the partition quality. In this work, an existing planar graph partitioning algorithm is analyzed. The proposed algorithm has a polynomial run time, constituting a faster partitioning solution compared to iterative algorithms, with the trade-off of lower quality. The Dual Graph Partitioning algorithm (DGP) exploits certain properties of a planar graph’s dual. Each path between two nodes at the external border of the dual graph, corresponds to a set of edges in the original graph. The removal of these edges results in two disconnected subgraphs. This kind of partitioning is called bisection. DGP searches shortest paths between all border nodes and chooses the shortest that separates the graph in two subgraphs of almost equal size, depending on a maximum allowed imbalance. However, it is not guaranteed that there will always be a shortest path between any pair of border nodes that would bisect the graph. This work aims to investigate the graph characteristics that affect the successful completion of the algorithm, through partitioning runs on generated hexagonal graphs. The PRAGMA mobility model was used to infer a sample distribution of edge weights. Graphs were generated using similar weight distributions. Results showed that the spatial distribution of high and low weights in a graph, affects the route of border-to-border shortest paths, and therefore, whether they bisect the graph with a desired section size ratio. Weight spatial and value distribution was modeled with the notion of population centers, nodes from which edge weights decrease with distance. The distribution of distances between population center to graph border nodes was used to identify whether a graph can be bisected using DGP. A variation of the algorithm, which guarantees a partition result with the trade-off of higher complexity, is also presented. The partition quality is compared to that of iterative techniques for a number of graphs used in the literature. |
|||
| Physical description | xv, 107 σ. : εικ. ; 30 cm. | |||
| Language | English | |||
| Issue date | 2008-12-04 | |||
| Collection | School/Department--School of Sciences and Engineering--Department of Computer Science--Post-graduate theses | |||
| Type of Work--Post-graduate theses | ||||
| Views | 472 | |||
| Digital Documents | |
|---|---|
|
Download document |
