Efficient relay placement algorithm using landscape aware routing (erpalar)

• Main Author: Onabajo, Olawale Olusegun
• Format: Thesis
• Language: English
• Published: Universiti Malaysia Sarawak, (UNIMAS) 2011
• Subjects: T Technology (General)
• Online Access: http://ir.unimas.my/id/eprint/12076/1/Onabajo%20Olawale%20Olusegun%20ft.pdf; http://ir.unimas.my/id/eprint/12076/

Relays are generally used to extend the communication range of wireless Access Point (AP). The problem of finding optimum location for Wireless Relay (WR) within irregular terrains that yields the best utilization of hardware as well as maximize bandwidth coverage is called Relay Placement Problem (RPP). This problem occurs whenever objects obstruct the transmission path of radio-frequency signals. Radio wave communication maintains Line-of-Sight (LOS) between transmitters and receivers for effective signal transmission. The key issue in the deployment of wireless broadband is determining where wireless relay hardware should be placed for best-effort network connectivity. In the rural areas, physical barriers constitute major problem against uninterrupted network transmission. Manual placement of wireless relay equipments will be a daunting task when deployment area spans over tens of kilometers and the environment made up of mountains, valleys and other terrains that could impact the transmission of radio-frequency Signal0 In this work, an algorithm code-named 'Efficient Relay Placement Algorithm using Landscape Aware Routing' -ERPALAR has been developed to solve the RPP. ERPALAR explores the deployment area and selects specific locations best suited for relay placement that ensures good network coverage, taking into consideration important factors in wireless relay communications such as: Fresnel zone clearance along the Line-of-Sight (LoS), relay transmission range observation, and prevailing height structures in such environment. ERP ALAR was implemented in Matlab R2009a using Genetic Algorithm (GA) with multi-objectives. GA is an optimization algorithm that simulates natural selection process as found in nature. It uses two genetic operators: crossover and mutation to effect variation in the outcome of the optimization process. While crossover engages two parents through random crossover point selection to produce two offspring, mutation on the other hand operates on a single parent through random gene replacement to create a new offspring. The implementation of ERPALAR uses two GAs. GA-I optimizes the relay coordinates, while GA-2 optimizes the Access Point (AP). A chromosome in GA-l is the relay coordinates: x, y, z converted to binary digits and concatenated head to tail in that order; a gene in GA-I is a single binary digit. Chromosome in GA-2 is the AP, and user slots on the AP as genes. Since this algorithm win be used at different deployment sites, a crossover rate of 0.5 is recommended for both GA-I and GA-2; and mutation rate of 0.1 for GA-l and GA-2. Main contribution of ERP ALAR include user-centered, cheap, rugged and improved network access system through the following inputs: 3D implementation that takes care of landscape structures such as mountains and hills which is a common phenomenon in rural regions; extension of the current network coverage reach through the use of wireless relays; strategic deployment plan for the rural population through phase-by-phase deployment; cheap and affordable hardware implementation to minimize overall investment cost; and use of rugged WiFi hardware (IEEE 802.11 b) to minimize attention required on maintenance. ERPALAR was successfully tested with fifty (50) different terrain samples for performance evaluation. Two separate results were compared in the implementation. ERP ALAR was first implemented with standard GA parameters, a situation whereby the relay coordinates were not optimized but the AP was optimized i.e. one (1) GA involved; and later executed with optimized GA, a new situation whereby both the relay coordinates and the APs where optimized for better performance i.e. two (2) GAs involved here. A comparison between standard and optimized GA shows that optimized GA performs better in terms of network coverage achieved. Results show that ERP ALAR successfully find best location for relay placement by identifYing suitable coordinates in the deployment area.