- 學位論文
隨機無線網路的延遲變化法則：通道使用次數的影響
Delay Scaling Law of Random Wireless Networks: Impact of Blocklength
摘要
我們研究在大型網路中，延遲的效應。我們探討隨著使用者個數的增加，延遲會如何增長。藉由通道使用次數來代表延遲，我們得到了最根本的結果。 此結果是由消息理論中最基礎的工具所推導出來。藉由將使用者個數和通道使用次數連結在一起，我們分析出了延遲增長率。 我們從文獻上已知的最佳策略，一個簡單的多重跳躍策略出發，進而推導出這個策略的理論上下界。我們也探討提出了一個時間分工多重存取的策略，並分析了他的資料傳遞率和延遲增長率。我們認為他有潛力延伸模擬現實網路。 本論文的主要貢獻為找到在一大型網路中使用多重跳躍策略，端點對端點的延遲增長率。我們的結果顯示在一個2k使用者的網路中，形成k個隨機配對，每個源點有F(k) bits資料要傳，若網路面積也為k，則延遲效應為Θ(√kF (k))如果F (k) = Ω(√klog k)；為 Θ(k log k) 如果F(k) = o(√klog k).。我們推倒了多重跳躍策略的極限，我們證明就增長率而言，一個準確的通道總使用次數的限制為ω(√klog k)。
並列摘要
In this thesis we focus on an important aspect of all communication networks, the delay. We measure the delay through the blocklength, which is one of the most basic quantities in information theory. By studying the interplay between number of users and blocklength, we characterize the delay scaling. The result is fundamental and is derived from one-shot bounds. We consider the simplest multihopping scheme, where each message is relayed several times. The effect of error propagation is characterized and the optimal strategy when using multihopping scheme is derived. We also came up with a more general version of the multihopping scheme, the time-division multiaccess multihopping scheme, which has the potential to be extended to model practical networks. The contribution of this thesis is to find the delay scaling of the multihopping scheme. In an network with 2k randomly one-to-one paired users and area k, assume a source with F(k) bits to send, we show that the delay is Θ(√kF (k)) if F (k) = Ω(√klog k); and is Θ(k log k) if F(k) = o(√klog k). This is derived by studying the limit of the multihopping scheme for large networks. We derive theoretically lower and upper bounds from the most fundamental one-shot results to characterize the blocklength constraint for the network. The result indicates the necessary and sufficient condition on the network blocklength scaling is ω(√klog k).