|
|
| แถว 1: |
แถว 1: |
| − | = ประวัติ =
| + | You have shed a ray of snushine into the forum. Thanks! |
| − | '''ชื่อ:''' จักริน ชวชาติ
| |
| − | | |
| − | = หัวข้องานวิจัย =
| |
| − | | |
| − | == Degree Limiting Minimum Diameter Tree Problem ==
| |
| − | เป็นปัญหา Network design มีกราฟ <math>G=(V,E)</math> ต้องการหา spanning tree <math>T</math> โดยมี objective ที่สนใจอยู่ 2 อย่าง ได้แก่ low diameter และ degree ของแต่ละ nodeไม่เกินดีกรีที่ node นั้นรับได้ ปัญหานี้สามารถนำไปประยุกต์ใช้เกี่ยวกับงาน peer to peer streaming ได้คือต้องการให้มี delay น้อย(สัมพันธ์กับ diameter) และการ assign งานไม่เกินที่แต่ละ node รับได้(สอดคล้องกับ degree)
| |
| − | | |
| − | === Problem Definition ===
| |
| − | Given a metric length function <math>\ell</math> over a set <math>V</math> of <math>n</math> nodes, and a degree-bound <math>B_v</math> for each <math>v\in V</math>, the Degree-Limiting Minimum-Diameter Spanning Tree Problem (DLDST) is to find a spanning tree <math>T</math> of <math>G</math> of minimum diameter such that each node <math>v</math> has degree at most <math>B_v</math> in <math>T</math>.
| |
| − | === เอกสารอ้างอิง ===
| |
| − | Shi, S. Y.; Turner, J. S. & Waldvogel, M. Dimensioning server access bandwidth and multicast routing in overlay networks In 11th International Workshop on Network and Operating System Support for Digital Audio and Video (NOSSDAV’01), 2001, 83-92
| |
| − | | |
| − | Frederickson, G. N.; Hecht, M. S. & Kim, C. E. Approximation Algorithms for Some Routing Problems SIAM Journal on Computing, SIAM, 1978, 7, 178-193
| |
| − | | |
| − | Könemann, J.; Levin, A. & Sinha, A. Approximating the degree-bounded minimum diameter spanning tree problem Algorithmica, Springer, 2003, 109-121
| |
| − | | |
| − | = บันทึก =
| |
| − | | |
| − | =='''Paper:''' Minimum-Latency Broadcast Scheduling in Wireless Ad Hoc Networks.==
| |
| − | | |
| − | ที่มา INFOCOM 2007. 26th IEEE International Conference on Computer Communications. IEEE (2007), pp. 733-739.
| |
| − | ของ Huang, S.C.-H. Peng-Jun Wan Xiaohua Jia Hongwei Du Weiping Shang
| |
| − | | |
| − | ==Problem==
| |
| − | An instance of Minimum-Latency Broadcast Scheduling consists of an undirected graph <math>G=(V,E)</math> representing the communication topology and a distinguished node <math>s\in V</math> as the source of the broadcast.
| |
| − | For any subset <math>U</math> of <math>V</math>, denote by <math>Inf(U)</math> the set of nodes in <math>V\setminus U</math> each of which has exactly one neighbor in <math>U</math>. Then a broadcast schedule of latency <math>l</math> is a sequence <math><U_1, U_2,\cdots , U_l></math> satisfying that
| |
| − | | |
| − | (1)<math>U_1 =\{s\}</math>.
| |
| − | | |
| − | (2)<math>U_i\subseteq \cup_{j=1}^{i-1}Inf(U_j)</math> for each <math>2\leq i\leq l</math>.
| |
| − | | |
| − | (3)<math>V\setminus \{s\}\subseteq \cup_{j=1}^{l}Inf(U_j)</math>.
| |
| − | | |
| − | The problem MLBS seeks a broadcast schedule of the smallest latency.
| |
| − | | |
| − | แต่สนใจ MLBS ใน unit-disk graphs G(V,E) ที่จะมี edge เชื่อมระหว่าง 2 nodesก็ต่อเมื่อ ระยะทาง(euclidean distance)ระหว่างสองโหนดนั้นไม่เกิน 1
| |
| − | | |
| − | ==บันทึก==
| |
| − | | |
| − | เข้าใจว่า
| |
| − | | |
| − | อัลกอริทึมจะสร้าง BFS tree<math> T</math>ของ <math>G</math> rooted at <math>s</math> แล้วคำนวณหาความลึกของทุกๆ nodes ใน tree จากนั้นในแต่ละชั้น <math>i</math> จะหา maximal independent set <math>U_i</math> จะเรียก node พวกนี้ว่าเป็น dominators ส่วน node ที่เป็น parents ของ dominators ใน T เรียกว่า connectors เวลาที่ส่งข้อมูลจาก s ก็จะเริ่มส่งไป dominator->connector->dominator ไปเรื่อยๆ
| |
| − | | |
| − | ในแต่ละชั้นนั้ independent set <math>U</math> of UDG <math>G</math> จะถูกแบ่งเป็น 12 2-IS of <math>G</math> ซึ่งจะมองเป็น proper node coloring of <math>G^2</math> ซึ่งแต่ละ subset ใน partition จะสอดคล้องกับสี หนึ่งสี
| |
| − | | |
| − | ทีนี้ส่วนที่น่าสนใจจะเป็นในแต่ละชั้นจะส่งข้อมูลกันอย่างไร โดยที่ไม่ชนกัน ซึ่งปัญหานี้แปลงไปเป็นปัญหา coloring ได้
| |
| − | | |
| − | ==อื่นๆ==
| |
| − | *[[การใช้งาน gnuplot]]
| |
| − | *[[การใช้งาน Google Chart API]]
| |
