รายละเอียดโครงงาน
หลักสูตร/ปี พ.ศ. วิศวกรรมศาสตรบัณฑิต สาขาวิชาวิศวกรรมคอมพิวเตอร์ ปี พ.ศ. 2563
ภาคและปีการศึกษาที่สำเร็จการศึกษา ภาคปลาย ปีการศึกษา 2562
ประเภทโครงงาน
โครงงานวิศวกรรม
ชื่อโครงงานภาษาไทย
การพัฒนาและออกแบบขั้นตอนวิธีแบบประมาณเพื่อหาเซตครอบงำระดับ m ที่มีการเชื่อมต่อระดับ k บนเครือข่ายไร้สายเฉพาะกิจ
ชื่อโครงงานภาษาอังกฤษ
Constructing k-connected m-dominating set in a wireless ad hoc network
ผู้พัฒนา
5910500121 คุณานนต์ บุรเทพ
อาจารย์ที่ปรึกษาหลัก
จิตร์ทัศน์ ฝักเจริญผล
อาจารย์ที่ปรึกษาร่วม
-
บทคัดย่อ
ปัญหา k-connected m-dominating set บน coin graph คือ การหาเซตของโหนดที่มีขนาดเล็กมากพอที่ยังทำให้โครงสร้างของกราฟยังคงคุณสมบัติ k-connected m-dominating set กล่าวคือ เมื่อเรามองเซตของโหนดที่เป็นคำตอบเปรียบเสมือน virtual backbone กราฟจะต้องมีคุณสมบัติที่โหนดปกติ (โหนดที่ไม่ได้อยู่ในเซตคำตอบ) จะต้องมีการเชื่อมต่อกับโหนดที่เป็น virtual backbone (โหนดในเซตคำตอบ) อย่างน้อย m เราเตอร์ (m-dominating) และ โหนดแต่ละตัวที่อยู่ในเซตคำตอบจะสามารถแทนด้วยเราเตอร์ที่อยู่ใน virtual backbone จะต้องมีคุณสมบัติคือ มีการเชื่อมต่อกับโหนดที่เป็น virtual backbone ด้วยกันเองอย่างน้อย k เราเตอร์ (k-connected) ซึ่งเราสนใจบน coin graph ที่นิยามกราฟขึ้นมาเพื่อจำลองเราเตอร์กระจายสัญญาณ ซึ่งแต่ละเครื่องนั้นจะมีกำลังในการกระจายสัญญาณไม่เท่ากัน จึงทำให้ coin graph มีลักษณะเฉพาะคือ แต่ละ โหนด จะมีรัศมีแผ่ออกไปไม่เท่ากัน ซึ่งแต่ละ โหนด จะมีเส้นเชื่อมถึงกันเมื่อรัศมีของสองคู่โหนดนั้นมีส่วนที่ทับซ้อนกัน หรือ สัมผัสกัน
โดยผลลัพธ์คือสามารถพิสูจน์ได้ว่าจากปัญหา k-connected m-dominating set บน coin graph เราสามารถแก้ปัญหาได้ด้วยอัลกอริทึมแบบประมาณของ Shang et al. และ Nutov. Z. ซึ่งเป็นอัลกอรึทึมแบบประมาณที่ใช้แก้ปัญหา k-connected m-dominating set บน unit disk graph โดยเราสามารถพิสูจน์ได้ว่า อัลกอริทึมแบบประมาณดังกล่าวสามารถแก้ปัญหาเดียวกันได้บน coin graph
Abstract
Given an undirected coin graph G=(V,E) and positive integer K and m, set T∪S which is a k-connected m-dominating set in coin graph such that be subset T of V such that each node in V\T has at least m neighbors in T and induced subgraph of T∪S is k-connected. We consider the case in which k≤m
Our result show that we can apply approximation algorithm by Shang et al. to find a set of T with property m-dominating set, then we add connectivity from m-dominating set to k-connected m-dominating set using approximation algorithm by Nutov. Z. for find set S such that induced subgraph of T∪S is k-connected. The output is set T∪S which contain k-connected m-dominating set.
คำสำคัญ (Keywords)
Coin graph, Connectivity, Dominating set
เว็บไซต์โครงงาน
-
วีดีโอคลิปของโครงงาน
ที่เก็บเวอร์ชันซอร์สโค้ด
-
สถานะการนำเข้าข้อมูล
ผู้นำเข้าข้อมูลครั้งแรก
คุณานนต์
บุรเทพ
(b5910500121)
แก้ไขครั้งสุดท้าย
เมื่อ March 20, 2020, 3:59 a.m. โดย
คุณานนต์
บุรเทพ
(b5910500121)
สถานะการอนุมัติ
อนุมัติแล้ว โดย
จิตร์ทัศน์
ฝักเจริญผล
(jtf)
เมื่อ May 2, 2020, 7:17 a.m.