- 學位論文
無線網路中高效能傳輸控制協定之設計與分析：多跳式廣播與中繼協助網路編碼自動重傳機制
Design and Analysis of Efficient Transmission Control Protocols in Wireless Networks: Multihop Broadcast and Relay-Assisted Network-Coding ARQ
摘要
由於路徑損耗、遮蔽效應、噪音、干擾等原因，無線通訊本質上是易錯的。在只有稀少頻譜資源的易錯環境中，如何有效率地達成可靠資料傳輸是非常重要的。在本論文中，我們發展了有效率的方法以提供無線多跳網路可靠廣播並提供無線中繼網路先進的自動重傳機制。 首先，我們探討了易錯無線網路中的最少傳輸廣播問題並提出有效率的解決方法，包括一個最佳廣播機制與一個基於賽局理論的分散式演算法。於可靠鏈結下和不可靠鏈結下的最少傳輸廣播問題可以分別以混合整數線性規劃公式化。如此一來，在網路規模不大時，我們可利用現有的混合整數線性規劃工具求出最佳解。考量大規模網路，我們提出了一個基於賽局理論的分散式演算法，並證明此賽局最後會達到納許均衡。藉由模擬中與現有其它機制以及最佳解的比較，我們確認了所提出之基於賽局理論的演算法在封包到達率、傳輸次數以及收斂速度方面都有很好的表現。 此外我們探討了在無線中繼網路中的先進自動重傳請求議題並研發了利用機會式重傳與網路編碼技術的中繼協助網路編碼自動傳重請求(Relay-Assisted Network-Coding ARQ, RANC ARQ)協定。 我們提出了工作量的觀念，意指中繼節點將會傳送的再編碼區塊數目；並且研究如何調整工作量增加的速率。基於此觀念，我們提出了一個基於工作量的中繼協助網路編碼統一架構；在此架構下，我們研發了數個中繼協助網路編碼自動重傳請求協定，包括plain-RANC、Work-based Opportunistic RANC (WO-RANC)、Listen-and-Supersede (LS)以及Hold-and-Proceed (HP)。LS可視為單一中繼節點中繼協助網路編碼自動重傳請求協定的效能極限，HP則是簡單有效且幾乎零系統開銷的方法。藉由廣泛分析與模擬，我們顯示了HP的效能很接近最佳的LS。
並列摘要
Wireless communication is inherently error-prone due to path loss, fading, noise, interference, etc. In such an error-inclined environment with scarce spectrum, it is of paramount importance to achieve reliable data delivery efficiently. In this thesis, we develop efficient schemes for providing reliable broadcast in wireless multihop networks and for providing advanced ARQ in wireless relay networks. We first address the minimum transmission broadcast problem in error-prone wireless networks and present efficient solutions, including an optimal broadcast scheme and a distributed game-based algorithm. The minimum transmission broadcast problems over reliable links and over unreliable links are formulated as two mixed integer linear programming (MILP) problems, respectively. This way, optimal broadcast schemes can be easily obtained using any existing MILP solver, for small-scale networks. For large-scale networks, we propose a distributed game-based algorithm and prove that the game-based algorithm achieves Nash Equilibrium. Using simulation, we confirm that compared with existing algorithms in the literature and optimal solutions obtained by our MILP techniques, the proposed game-based algorithm performs very well in terms of delivery ratio, number of transmissions, and convergence speed. We further address the issue of advanced ARQ in wireless relay networks and develop relay-assisted network-coding (RANC) ARQ protocols, which leverage both opportunistic retransmission and network coding techniques. We introduce the concept of work, which is the number of recoded blocks a relay node will send, and study ways to adjusting the rate at which a relay node increases its work. Based on this concept, we present the unified framework of work-based RANC and then, under the unified framework, we develop a number of RANC ARQ protocols including plain-RANC, Work-based Opportunistic RANC (WO-RANC), Listen-and-Supersede (LS) RANC, and Hold-and-Proceed (HP) RANC. LS offers a fundamental limit to any single-relay RANC ARQ protocol. HP is a simple yet efficient RANC ARQ protocol with near-zero overhead. We analyze saturation throughput and segment delay for both LS and HP. Through extensive analysis and simulation results, we show that HP has a performance close to LS.