高密度電波涵蓋地圖資料庫之演算法與物件模型研究

Abstract

無線頻譜在全球皆是一種共同的有限通訊資源。當用戶和連網裝置與日俱增導致網路服務佔用愈來愈多頻譜，行動寬頻交通流量成長也超乎預期，因此可預期未來對於頻譜資源的需求也會不斷上升。如何以最有效的方式提升頻譜使用效率已經成為很重要的研究議題。在各種處理頻譜有限與網路服務需求增加的解決方案中，頻譜共享機制已被認為是可以大幅提升頻譜使用效率的重要方法。 本研究以 TVWS ( TV White Space ) 與 LSA ( Licensed Shared Access ) 為主要系統參考架構。使用頻譜資料庫紀錄網路及頻段資源狀況，包括使用頻段、時間與地理位置等資訊以達成頻譜共享機制。藉由此種頻譜資料庫，能達到頻譜共享和干擾管理的雙重目的：例如可以透過查詢資料庫，了解是否存有既有用戶未用之空閒頻段地區，或是如果要佈建新無線電發射台，可查詢是否會與既有用戶或其他用戶干擾，來避免發生干擾區域。 為實作出此資料庫，本研究認為首先必須先界定出完整的物件模型，定義出物件之間的關係，以及涵蓋範圍的儲存格式才能設計出具延展性的電波涵蓋資料庫。本論文隨後主要探討關於以電波涵蓋為主要功能資料庫的兩個面向，第一個是提出關於頻譜資料庫高密集分佈電波涵蓋地圖資料庫高效率儲存資料格式及其演算法，以及在擁有完整的頻譜資訊下，減少需要儲存的資料量同時提升資料庫的查詢效率。第二個面向是針對頻譜資料庫整體架構及管理需求，提出符合權限不同的多個使用者/管理者需求之多層級式階層物件模型。 本論文提出以最少切割方形演算法為基礎資料格式以及判別重疊區塊及判別權限演算法。經由台大校園 Wi-Fi 實際案例測試，高效率最少切割方形演算法與不使用演算法之資料庫做比較，結果可以得知提出的最少切割方形演算法能夠使得儲存資料量大幅減少，並且提升查詢效率。此外，本研究定義出頻譜資料庫多層級式階層的物件模型，從三種物件階層討論之，分別為管理階層、網路階層與涵蓋地圖階層。最後本研究之設計經由台大研究計畫團隊協助共同完成一個展示雛型系統，得以簡易人機介面展示此資料庫查詢未被使用的空閒頻段位置與查詢電波涵蓋之重疊狀況。

Wireless spectrum is a common limited communication resource in the world. However, mobile Internet services have occupied more and more spectrum than before, as the number of users and mobile devices accessing Internet for various applications keeps increasing every day, and the amount of traffic data has grown beyond our expectation. Therefore, we can easily predict that there will continuously be increasing demands for wireless spectrum and how to improve spectrum utilization is now an important issue. Among different approaches to resolve this issue, spectrum sharing mechanism is considered to be an important method to enhance mobile spectrum utilization. In this study, we focus on a spectrum-sharing system architecture, using the TVWS (TV White Space) and LSA (Licensed Shared Access) models as our main references. Under this architecture, we keep track of the details of mobile networks and spectrum management information in spectrum databases(called repositories), in which the information of occupied spectrum, time and geolocation/coverages of radio stations, and other management information are stored, in order to enable the operation of dynamic spectrum sharing. Furthermore, with the proposed architecture, information storage method, and management object models, we can achieve the goals of spectrum sharing and interference management at the same time. For example, one can determine whether there is any spectrum in an area not occupied by incumbents for other licensees to use, or one can check whether there are some overlapped regions between the coverage contours of new and existing radio stations ,when one wish to add new radio stations without cross-network interferences. To implement such databases, we first define an object model for the spectrum sharing database, in which we clarify the relationship among all objects and the formats to store radio contours in an extensible database. We then explore two key issues in database design, the first one is how to design a highly efficient storage format and related algorithms for databases of high density radio coverages, to reduce the storage complexity and to improve database query efficiency. The second one is to design a hierarchy of multi-level object models, with which one single database architecture can satisfy different demands from different level of users/managers. In this study, we propose the Minimum Partitioned Rectangles Algorithm to obtain the rectangle based data format for storage, and then employ an Overlapped Region and Permission Check Algorithm for identifying regions under interferences. In order to compare the performance of our scheme with other approaches, we test it with real cases of outdoor Wi-Fi in NTU main campus, and we conclude that our algorithms can reduce storage complexity significantly and improve the query efficiency effectively. Next, we define the multi-level object models of spectrum database from three perspectives, including the administration hierarchy model, the network hierarchy model and the coverage map hierarchy model. A demo system is built with partial help of an NTU spectrum-sharing project team, and one can use it to check the spectrum usage contour and also display overlapped regions of radio coverage contours in the user interface.