Minimum cardinality for geometric disks covering: application to global system for mobile communication (GSM) masts in telecommunication network design.

Thumbnail Image
September, 2015
Journal Title
Journal ISSN
Volume Title
This thesis is in computational geometry and optimization. Such problems arise in many application domains, such as communication networks, geographic information systems, crop management (watering of grid pattern crops with sprinkler), robotics, computer graphics and many others. More specifically, in this thesis we conduct research in the context of geometric covering with disks and optimization of overlap difference and overlap area for uniform and non-uniform disks. GSM networks are very expensive. The network design process requires too many decisions in a combinatorial explosion. For example, due to inappropriate location of GSM masts and irregular assignment of frequencies, mobile users experience frequent hard handovers, uneconomical soft handovers, call trafficking, call blocking and higher degrees of interference. As a result it is important to design optimized networks that meet performance criteria. In the telecommunication industry it is well known that wireless communication does not perform well without antennas on GSM masts, but the existence and design of GSM masts becomes an inconvenience to many users and the industry when not properly positioned. These wireless networks have a lot of geometric properties since the multiple sector radiated signal corresponds to circular motion. A unique greedy approximation model, called Hexagonal Tessellation Model (HTM) is proposed to solve the network design problem. Data from MTN and GLO Ghana and Nigeria were collected and analyzed using the developed model. Hexagonal Tessellation Model for uniform cell range accounted for an overlap difference of 5.788km using 35 GSM masts instead of for 50 MTN masts in Kumasi East, Ghana. This is a 79% reduction in number over the original layout. GLO Accra East, Ghana accounted for an overlap difference of using 44 GSM masts instead of for 50GSM masts. This is a 41.98% reduction over the original layout. Also, non-uniform cell range for MTN River State accounted for using 36 GSM masts instead of for 50 GSM masts. This is 53.18% reduction over the original design. Finally, non-uniform cell range for GLO River State, Nigeria accounted for an overlap difference of using 38 GSM masts instead of for 45 GSM masts. This is reduction over the original design. Our solution is shown to be optimal in overlap difference and overlap ar ea for both uniform and non-uniform cell range. Theorems on geometry of hexagonal tessellation for GSM network design are stated, conjectures are made followed by a corollary. Also, this research will seek to provide a profound and unifying exposition to telecommunication network theory and the mathematical algorithms that support it. No part of this publication which is material protected by this copyright notice may be reproduced or transmitted or utilized or stored in any form or by any means now known or hereinafter invented, electronic, digital or mechanical, including photocopying scanning, recording or by any information storage or retrieval system, without prior written permission from the author
A thesis submitted to the department of Mathematics, Kwame Nkrumah University of Science and Technology, in partial fulfillment of the requirement for the degree of Doctor of Philosophy, College of Science.