서브메뉴
검색
Theory and Algorithms for Scheduling Deadline-Constrained Packets in Single-Hop and Multi-Hop Wireless Networks
Theory and Algorithms for Scheduling Deadline-Constrained Packets in Single-Hop and Multi-Hop Wireless Networks
상세정보
- 자료유형
- 학위논문 서양
- 최종처리일시
- 20250211151054
- ISBN
- 9798382261027
- DDC
- 004
- 서명/저자
- Theory and Algorithms for Scheduling Deadline-Constrained Packets in Single-Hop and Multi-Hop Wireless Networks
- 발행사항
- [Sl] : Columbia University, 2024
- 발행사항
- Ann Arbor : ProQuest Dissertations & Theses, 2024
- 형태사항
- 168 p
- 주기사항
- Source: Dissertations Abstracts International, Volume: 85-10, Section: A.
- 주기사항
- Advisor: Ghaderi, Javad.
- 학위논문주기
- Thesis (Ph.D.)--Columbia University, 2024.
- 초록/해제
- 요약This dissertation considers the problem of scheduling deadline-constrained packets in networks, an increasingly relevant problem, which due to the rise of time-sensitive applications such as teleconferencing and video streaming, has recently received renewed attention. To accommodate a diverse range of environments and scenarios, our work investigates single-hop and multi-hop networks, across various traffic models and network conditions, including wired and wireless settings. We propose algorithms in each setting, with their performance evaluated by considering commonly used benchmarks in the related literature, such as the attained fraction of the real-time capacity region achieved in single-hop networks and the maximization of the cumulative weight of packets reaching their destinations within their deadlines in multi-hop networks. We explore traffic which is either worst-case, or stochastic, and provide different performance guarantees in each case.The first part of our study focuses on scheduling real-time traffic in single-hop wireless networks with conflict-graph interference models. We propose randomized policies that achieve higher real-time efficiency ratios, compared to state-of-the-art existing algorithms, such as the Largest-Deficit-First algorithm. The research then extends to single-hop wireless networks with unreliable links due to channel fading, designing randomized algorithms that achieve efficiency ratios strictly higher than traditional scheduling algorithms, such as Maximum-Weight Scheduling.The dissertation proceeds to examine online admission, routing, and scheduling algorithms for multi-hop wireless networks under a general interference graph model. It presents online algorithms that are competitive with the optimal offline algorithms and provides upper bounds on performance which demonstrate the asymptotic optimality of these results. Simulation results illustrate significant improvements over prior approaches.Furthermore, the research addresses the problem of scheduling packets with end-to-end deadline constraints in both wired and wireless multi-hop networks, in the case of stochastic traffic. It illustrates the first near-optimal approximation algorithms under nontrivial assumptions on traffic and link capacity, showcasing significant improvements over worst-case algorithms in practical settings.In conclusion, this dissertation contributes scheduling algorithms for deadline-constrained packet delivery in single and multi-hop networks, under various traffic and interference models, and in both wired and wireless settings. The proposed algorithms materially improve the state-of-the-art performance guarantees in each case.
- 일반주제명
- Computer science
- 일반주제명
- Communication
- 일반주제명
- Information science
- 키워드
- Single-hop
- 키워드
- Multi-hop
- 기타저자
- Columbia University Electrical Engineering
- 기본자료저록
- Dissertations Abstracts International. 85-10A.
- 전자적 위치 및 접속
- 로그인 후 원문을 볼 수 있습니다.
MARC
008250123s2024 us c eng d■001000017160647
■00520250211151054
■006m o d
■007cr#unu||||||||
■020 ▼a9798382261027
■035 ▼a(MiAaPQ)AAI31142097
■040 ▼aMiAaPQ▼cMiAaPQ
■0820 ▼a004
■1001 ▼aTsanikidis, Christos.
■24510▼aTheory and Algorithms for Scheduling Deadline-Constrained Packets in Single-Hop and Multi-Hop Wireless Networks
■260 ▼a[Sl]▼bColumbia University▼c2024
■260 1▼aAnn Arbor▼bProQuest Dissertations & Theses▼c2024
■300 ▼a168 p
■500 ▼aSource: Dissertations Abstracts International, Volume: 85-10, Section: A.
■500 ▼aAdvisor: Ghaderi, Javad.
■5021 ▼aThesis (Ph.D.)--Columbia University, 2024.
■520 ▼aThis dissertation considers the problem of scheduling deadline-constrained packets in networks, an increasingly relevant problem, which due to the rise of time-sensitive applications such as teleconferencing and video streaming, has recently received renewed attention. To accommodate a diverse range of environments and scenarios, our work investigates single-hop and multi-hop networks, across various traffic models and network conditions, including wired and wireless settings. We propose algorithms in each setting, with their performance evaluated by considering commonly used benchmarks in the related literature, such as the attained fraction of the real-time capacity region achieved in single-hop networks and the maximization of the cumulative weight of packets reaching their destinations within their deadlines in multi-hop networks. We explore traffic which is either worst-case, or stochastic, and provide different performance guarantees in each case.The first part of our study focuses on scheduling real-time traffic in single-hop wireless networks with conflict-graph interference models. We propose randomized policies that achieve higher real-time efficiency ratios, compared to state-of-the-art existing algorithms, such as the Largest-Deficit-First algorithm. The research then extends to single-hop wireless networks with unreliable links due to channel fading, designing randomized algorithms that achieve efficiency ratios strictly higher than traditional scheduling algorithms, such as Maximum-Weight Scheduling.The dissertation proceeds to examine online admission, routing, and scheduling algorithms for multi-hop wireless networks under a general interference graph model. It presents online algorithms that are competitive with the optimal offline algorithms and provides upper bounds on performance which demonstrate the asymptotic optimality of these results. Simulation results illustrate significant improvements over prior approaches.Furthermore, the research addresses the problem of scheduling packets with end-to-end deadline constraints in both wired and wireless multi-hop networks, in the case of stochastic traffic. It illustrates the first near-optimal approximation algorithms under nontrivial assumptions on traffic and link capacity, showcasing significant improvements over worst-case algorithms in practical settings.In conclusion, this dissertation contributes scheduling algorithms for deadline-constrained packet delivery in single and multi-hop networks, under various traffic and interference models, and in both wired and wireless settings. The proposed algorithms materially improve the state-of-the-art performance guarantees in each case.
■590 ▼aSchool code: 0054.
■650 4▼aComputer science
■650 4▼aCommunication
■650 4▼aInformation science
■653 ▼aWireless networks
■653 ▼aSingle-hop
■653 ▼aMulti-hop
■653 ▼aScheduling algorithms
■690 ▼a0984
■690 ▼a0459
■690 ▼a0723
■71020▼aColumbia University▼bElectrical Engineering.
■7730 ▼tDissertations Abstracts International▼g85-10A.
■790 ▼a0054
■791 ▼aPh.D.
■792 ▼a2024
■793 ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17160647▼nKERIS▼z이 자료의 원문은 한국교육학술정보원에서 제공합니다.
