Adaptive nearest neighbor algorithm on hierarchical weighted-index graph

ขั้นตอนวิธีในการดัดแปลงการเลือกจุดใกล้ที่สุดบนกราฟที่มีดัชนีถ่วงน้ำหนักแบบลำดับขั้น

Name: Adisak Sukul

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.

Abstract: หลักสำคัญที่จะทำให้ระบบงาน Shortest-Path Problem (SPP) ที่ต้องการการ ตอบสนองรวดเร็วนั้น ประกอบไปด้วยสองส่วน ได้แก่ ส่วนของการรับส่งข้อมูล และส่วนการ ค้นหาเส้นทาง สำหรับส่วนแรกนั้น เครือข่าย IEEE 802.16j ได้เปิดการทำงานของ Relay Stations (RS) แบบกระโดดหลายขั้น ซึ่งมีเป้าหมายที่จะขยายระยะครอบคลุม และปริมาณ การส่งข้อมูลของผู้ใช้แต่ละคน อย่างไรก็ตาม Mobile Stations (MSs) ที่เชื่อมต่อกับ RS นั้น จะได้ปริมาณการส่งข้อมูลลดลงและข้อมูลล่าช้าเพิ่มขึ้นอย่างมากในกรณีที่เครือข่ายคับคั่ง เมื่อจำนวนขั้นกระโดดของ RS ยิ่งมากขั้น ปริมาณการส่งข้อมูลก็จะยิ่งลดลง และข้อมูลก็จะ ยิ่งล่าช้ามากขึ้น ในงานวิจัยนี่ได้เสนอระบบการจัดการ RS ด้วย Network coding และ ออกแบบโครงสร้างของ Frame ใหม่ที่ดีขึ้นกว่าเดิม รวมเรียกว่า NC-based Relay โดยระบบ การจัดการนี้อนุญาตให้ RS รวมการส่งข้อมูลในเส้นทางหลักแบบไร้สายสองเส้นทางแล้วส่งใน ครั้งเดียวโดยใช้เทคนิค Network coding ผลการวิเคราะและจำลองด้วยโปรแกรม Qualnet ยืนยันว่าวิธีที่เสนอนี้สามารถขยายปริมาณการส่งข้อมูลขึ้นได้ถึง 140% และลดการล่าช้าของ การส่งข้อมูลลงได้ถึง 83% ส่วนที่สองได้แก่ส่วนการหาเส้นทาง ซึ่งงานวิจัยนี้ได้เสนอรูปแบบ สำหรับดัชนีแบบลำดับขั้นบนแผนที่ดิจิทัลที่มีการถ่วงน้ำหนัก เรียกว่า hierarchical index weighted-graph (HIGLA) และยังเสนอขั้นตอนวิธีในการดัดแปลงเลือกเส้นทางสั้นที่สุดด้วย เวลาเดินทาง เรียกว่า adaptive travel-time path selection algorithm (ATTPS) ซึ่งสามารถ ทำงานได้เร็วกว่าขั้นตอนวิธีอื่น ๆ ที่มีอยู่ในปัจจุบัน

Chulalongkorn University. Office of Academic Resources

Address: BANGKOK

Email: cuir@car.chula.ac.th

Name: Pattarasinee Bhattarakosol

Role: advisor

Created: 2009

Modified: 2564-09-09

Issued: 2021-03-06

วิทยานิพนธ์/Thesis

application/pdf

URL: http://cuir.car.chula.ac.th/handle/123456789/67926

eng

DegreeName: Doctor of Philosophy

Level: Doctoral Degree

Descipline: Computer Science

Grantor: Chulalongkorn University

©copyrights Chulalongkorn University

ลำดับที่.	ชื่อแฟ้มข้อมูล	ขนาดแฟ้มข้อมูล	จำนวนเข้าถึง	วัน-เวลาเข้าถึงล่าสุด
1	Adisak_su_tdc.pdf	4.52 MB

ใช้เวลา

0.033194 วินาที