毫米波無線個人通訊網路結合中繼點選擇與排程之演算法

Abstract

60 GHz頻段通訊被認為是深具潛力的高速家庭及區域網路無線通訊之前瞻技術。由於訊號衰減性高且載波穿透性低，資料傳輸範圍相當有限。在802.15.3c網路中，使用波束形成(beamforming)及指向性天線來加強其傳輸功率及資源使用效率，但改善有限。由於傳輸範圍僅10公尺，因此在一空間中可能存在多個網路，在同一網路間傳輸對為intra-piconet flow，而跨網路傳輸的傳輸對稱為inter-piconet flow，本論文的研究目的為在60 GHz免執照頻段之高速通訊系統之MAC層技術，有效利用其指向性天線特色與定位資訊，在網路內尋找適合傳輸的時機以及中繼者(relay)幫忙轉運資料，並設計一時空重複利用度(time-spatial reusability)最佳的排程機制，以達到增加系統吞吐量及多個網路間溝通效率之目標。 本論文首先設計ㄧ模型來最佳化本研究欲解之問題，並推算出此解的複雜度，由於最佳化求解通常為NP問題，因此本文提出簡化演算法來求得一近似最佳解。演算法主要是分成兩個部分，第一部分為了減化演算法的複雜度，先進行網路內傳輸對intra-piconet flow的排程，期望用最少的時間傳完intra-piconet flow。第二部分則是根據第一階段的排程結果，定義interference-free、concurrence-restricted extent、concurrence index，並設計適當的中繼點選擇及排程演算法，使得在增加傳輸時間最少的情況下完成所有傳輸對的傳輸。 最後以模擬結果呈現在任意選擇中繼點的情況下與本篇所提之演算法作比較，比較系統效能以及通道再利用率，結果顯示所提出之演算法，可藉由適當的中繼點選擇及排程的交互作用提升通道再利用率，並有效改善系統的整體效能。

The unlicensed 60 GHz spectrum is very attractive for the broadband wireless networks because it can support the multi Gbs transmissions with 7 GHz bandwidth. Due to the oxygen absorption and path loss, the transmission range is limited to several meters. Operating in the 60 GHz band, IEEE 802.15.3c and 802.11ad networks use directional antenna and beamforming technique to avoid high propagation attenuation and path loss, and improve the overall system throughput by exploiting spatial channel reuse. In our thesis, we introduce the necessity and design challenges of inter-piconet communications. First, we develop a formulation for optimal relay selection and scheduling to minimize the inter-piconet flows’ transmission time. Since the optimization is a NP problem, our research is to find a heuristic algorithm to solve. Based on our observation, we propose a joint design of relay selection and scheduling with greedy concept. Specifically, we define “interference-free”, “concurrence-restricted extent”, and “concurrence index” for properly selecting relays to improve the degree of spatial channel reuse. The designed scheduling algorithm consists of two phases: intra-piconet flow scheduling and inter-piconet flow scheduling. After performing phase 1 operations, intra-piconet flows are scheduled and the total required channel time is known. The phase 2 operations are to use the least channel time extension to schedule all inter-piconet flows. We evaluate our algorithm through simulations. The results show that the joint algorithm performs well and does achieve its objectives.