Heuristics for multiway partitioning in hexagonal cellular systems

Given a hexagonal mesh of base stations in cellular systems we consider the problem of finding a cover of disjoint clusters of base stations which generate multiple types of traffic among themselves. The objective is to minimize the total communication cost for the entire system where intercluster communication is more expensive than intracluster communication for each type of traffic. We develop several heuristics based on the techniques of moving or interchanging the boundary nodes between adjacent clusters. The heuristics are compared and shown to behave quite well through experimental tests and analysis