Evaluation of Mesh Points Placement Schemes for Rural Wireless Mesh Network (RWMN) Deployment
University of Zululand
Internet connectivity in most rural African areas has been viewed as a major challenge due to lack of reliable power, scarcity of network expertise, expensive installation of network equipment and the high cost of providing Internet connectivity. However, with the rapid development of wireless technologies, Wireless Mesh Network (WMN) has emerged as a promising networking infrastructure, bridging the digital divide between town and countryside. This is because of low cost, easy deployment and increased high speed of WMN internet connectivity. Despite the aforementioned features, WMN deployments still suffer from a challenge of achieving optimum network performance which is affected by a number of factors. One of these factors is choosing optimal positions for Mesh Points’ (MP’s) placement in a geographical environment. MP’s placement problems have been thoroughly investigated in the WMN field and different research works propose MP’s placement schemes that can be used to solve the placement problem. Deploying a WMN requires taking into account limitations and topology of the terrain. However, none of the existing MP’s placement schemes have been evaluated and compared using rural settlement patterns in order to judge their suitability of solving MP’s placement problem in such environments. The purpose of this study was to compare the existing MP’s placement schemes and to recommend the best scheme(s) to be used during rural WMN deployment. This can be viewed as a twofold objective, the first one involves evaluating Mesh Access Points (MAP’s) placement schemes and the second one involves evaluating Mesh Portal Points (MPP’s) placement schemes in the rural settlement patterns. Four MAP’s placement schemes were evaluated namely; Hill Climbing, Virtual Force Based (VFPlace), Time-efficient Local Search and Random placement schemes and, on the other hand, Four MPP’s placement schemes were evaluated namely Incremental Clustering, Multi-hop Traffic-flow Weight (MTW), Grid Based and Random MPPs placement schemes. Simulation was done in NS2, and four rural settlement patterns were considered, Nucleated, Dispersed, Linear and Isolated rural settlement patterns. The experimental evaluation revealed that Hill Climbing is better fitted to solving a placement problem in nucleated and dispersed settlement patterns. VFPlace could be applied as a first choice for placement in linear settlement patterns while Time-efficient Local Search is better for deployment in isolated settlement patterns. As an improvement from the existing works of MAP’s placement schemes, this study not only focuses on optimizing coverage and connectivity among the MAPs, but also focuses on the other factors like network throughput, packet deliver ratio and end-to-end delay. To complete the deployment problem, the recommended placement schemes were used as bases for MPP’s placement. The study revealed that MTW is best fit for placement in linear and nucleated settlement patterns, Grid is best for dispersed settlement patterns while incremental clustering is best for isolated settlement patterns. The performance of MPP’s placement schemes was evaluated by measuring and comparing the packet delivery ratio, throughput and end-to-end delay in the network. Random selection of MP’s led to poor network performance in all scenarios. Deploying single MPP improves network performance only in a small instance. However, the increase in the number of MAP’s results in a bottleneck on the MPP, hence the findings of this study recommends more than one MPP should be deployed when there are too many MAP’s in the network. In all scenarios a good placement scheme should be adaptive to the number of MAP’s and MPPs.
A thesis submitted to the Faculty of Science and Agriculture in fulfilment of the requirements for the Degree of Master of Science in the Department of Computer Science at the University of Zululand, South Africa, 2014
wireless mesh network --RWMN --mesh points --internet connectivity