Adaptive nearest neighbor algorithm on hierarchical weighted-index graph

Abstract

Two main factors to satisfy the needs of SPP applications that require fast response are the data transfer part and the path finding part. On the first part, IEEE 802.16j is to enable the operation of multi-hop Relay Stations (RS). It aims to enhance the coverage, per user throughput and system capacity. However, the Mobile Stations (MSs) which connect to the RS are suffered from exponentially throughput degradation and increased end-to-end delay in congested networks. As the number of RS hops increase, so does the degradation and the delay growth. This research proposes a Network Coding-based Relay scheme and improved OFDMA frame structure design for multi-hop relay networks, called NC-based Relay. It allows RSs to combine two wireless backhaul transmissions into one using network coding technique. The analysis and simulation results by QualNet confirm that the proposed scheme can enhance the throughput gain up to 140%, and reduce the end-to-end delay by up to 83%. On the second part, the path finding part, this research proposes a model to index the digital map of the weighted-graph, called hierarchical index weighted-graph (HIGLA). And also propose an adaptive travel-time path selection algorithm (ATTPS) that performs faster path selection in term of traveling time than the existing shortest path algorithms.