Chulalongkorn University Theses and Dissertations (Chula ETD)

Delay analysis of a newly proposed tree based collision resolution algorithm with known multiplicity feedback

Other Title (Parallel Title in Other Language of ETD)

การวิเคราะห์เวลาประวิงอัลกอริทึมการแก้ไขปัญหาการชนกันแบบต้นไม้แบบใหม่เมื่อมีการป้อนข้อมูลกลับจำนวนแพ็กเกตที่ชนกัน

Year (A.D.)

2013

Document Type

Thesis

First Advisor

Lunchakorn Wuttisittikulkij

Second Advisor

Jun-Ichi Takada

Faculty/College

Faculty of Engineering (คณะวิศวกรรมศาสตร์)

Degree Name

Doctor of Engineering

Degree Level

Doctoral Degree

Degree Discipline

Electrical Engineering

DOI

10.58837/CHULA.THE.2013.1367

Abstract

This thesis investigates the performance of two frame-based MAC protocols namely framed slotted Aloha and the tree algorithms with different types of feedback information; binary, ternary, and known multiplicity. Four fundamental mechanisms for resolving collision are introduced as basic building blocks for the construction of a wide range of random access MAC protocols. The proposed analytical evaluation has shown that the use of feedback information, if used efficiently, plays a vital role in delay performance improvement. The achievable delay performance is shown to be highly dependent upon how the feedback information is used in the contention resolution. For known multiplicity, the maximum achievable MST of 0.533 is obtained by our proposed random access protocol that is derived by the combination of splitting mechanism, adaptive frame size, slot-skipping type II, and non-uniform access probability. We also present a preliminary study of a generic model that serves multi-class nodes with different quality of service requirements using slotted aloha, designed specifically for reservation-based MAC protocol with slotted Aloha that allows us to develop a variety of prioritization schemes, whereby nodes can be prioritized through reservation success rates, while aiming to maintain high efficiency of channel utilization.

Other Abstract (Other language abstract of ETD)

วิทยานิพนธ์ฉบับนี้ทำการศึกษาสมรรถนะของโพรโทคอลควบคุมการเข้าถึงตัวกลางที่ใช้รูปแบบเฟรมจำนวน 2 โพรโทคอล ดังนี้ โพรโทคอล framed slotted Aloha และอัลกอริทึม tree ที่ใช้ข้อมูลผลป้อนกลับหลายประเภท คือ ผลป้อนกลับแบบ binary, ผลป้อนกลับแบบ ternary และผลป้อนกลับแบบทราบจำนวนผู้ใช้บริการที่เข้าใช้สล็อตสัญญาณใดๆ โดยมีการนำเสนอกลไกพื้นฐานที่ใช้ในการแก้ปัญหาการชนจำนวน 4 รูปแบบเพื่อเป็นรูปแบบพื้นฐานสำหรับโครงสร้างของโพรโทคอลควบคุมการเข้าถึงตัวกลางแบบสุ่มประเภทต่างๆ การประเมินสมรรถนะด้วยการวิเคราะห์ทางคณิตศาสตร์ที่นำเสนอแสดงให้เห็นว่าการใช้ข้อมูลผลป้อนกลับที่มีประสิทธิภาพนั้น จะมีบทบาทสำคัญในการเพิ่มสมรรถนะทางด้านค่าเวลาประวิงให้ดีขึ้น อีกทั้งยังแสดงให้เห็นว่าสมรรถนะทางด้านค่าเวลาประวิงที่รับได้นั้นจะขึ้นอยู่กับข้อมูลผลป้อนกลับที่ใช้ในการแก้ไขการช่วงชิงกัน สำหรับกรณีที่ใช้ผลป้อนกลับแบบทราบจำนวนผู้ใช้บริการที่เข้าใช้สล็อตสัญญาณใดๆนั้น ค่า MST ที่สามารถรับได้สูงสุดมีค่าเท่ากับ 0.533 ซึ่งได้จากโพรโทคอลการเข้าถึงแบบสุ่มที่นำเสนอโดยใช้กลไกการแบ่ง (split), การปรับเปลี่ยนขนาดของเฟรม, การละทิ้งสล็อตรูปแบบที่ 2 (slot-skipping type II) และความน่าจะเป็นการเข้าถึงแบบไม่เอกรูป (non-uniform) ร่วมกัน เรายังได้นำเสนอการศึกษาแบบจำลองทั่วไปในเบื้องต้น ที่ประกอบด้วยโนดหลายคลาสซึ่งมีความต้องการคุณภาพของการบริการ (quality of service) ที่แตกต่างกัน โดยใช้ slotted Aloha ที่ออกแบบโดยเฉพาะสำหรับ โพรโทคอลชั้นควบคุมการเข้าถึงตัวกลางที่อาศัยการจอง (reservation-based MAC protocol) ที่ยอมให้เราพัฒนาวิธีการจัดลำดับความสำคัญ (prioritization) ของโนดตามอัตราความสำเร็จ (success rate) ในขณะเดียวกันก็ยังรักษาประสิทธิภาพการใช้ช่องสัญญาณ (channel utilization)

Link to Full Text

Share

COinS