簡易檢索 / 詳目顯示

研究生: 李礎宇
Chu-yu Lee
論文名稱: 無線網格網路下STDMA排程之研究
The Study of a Spatial TDMA Scheduling in Wireless Mesh Networks
指導教授: 陳郁堂
Yie-tarng Chen
口試委員: 呂永和
Yung-ho Lu
方文賢
Wen-hsien Fang
陳省隆
Hsing-lung Chen
林銘波
Ming-bo Lin
學位類別: 碩士
Master
系所名稱: 電資學院 - 電子工程系
Department of Electronic and Computer Engineering
論文出版年: 2007
畢業學年度: 95
語文別: 英文
論文頁數: 60
中文關鍵詞: 無線網格網路STDMA排程
外文關鍵詞: wireless mesh networks, physical interference, STDMA scheduling
相關次數: 點閱:150下載:2
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  • 近年來,無線網格網路成為無線存取的新興技術。但是,在無線網格網路中,CSMA/CA的機制並不適用,因其會有極高的overhead。取而代之的是spatial TDMA機制。spatial TDMA機制在無線網格網路下能使系統效能有所提昇,然而,在STDMA的機制中,我們必須很小心的排程每個網路節點。
    很多研究指出,physical interference model比protocol interference model更能精確的模擬出網路節點之間的干擾關係。利用physical interference model我們更能有效的增加空間再利用度。但physical interference model需要更多排程資訊才能正確的計算出網路節點之間的干擾關係且計算上更為複雜,因此目前很少有應用在分散式方面的研究。
    在我們的研究裡,我們發展了一個SLS演算法結合physical interference model並分別有集中式與分散式兩種版本。我們的演算法主要是利用標示狀態的方式來處理interference relation under physical interference model。利用此方式我們可以在分散式有限資訊的環境下使用physical interference model來排出更有效率的排程。
    最後我們在實驗中,我們分別比較了CSMA disable CA與TDMA在1Mbps, 6 Mbps與9Mbps三種網路負載下的效能。結果顯示,在高負載下TDMA結合physical interference model的效能幾乎是CSMA disable CA的三倍。另外,我們也比較了DRAND與我們的SLS演算法在相同環境下效能表現上的差異。我們可以看出,我們的SLS演算法在效能上大部分都優於DRAND。


    In recent years, wireless mesh networks become an emerging technology for broadband Wireless Access. However, CSMA/CA no longer suits to wireless mesh networks due to high overheads in CSMA/CA. Instead, spatial TDMA can increase system throughput in wireless mesh networks if we can carefully schedule wireless mesh routers.
    Previous researches showed that the physical interference model is more precise than the protocol interference model. Using the physical interference model, we can increase spacial reuse under TDMA mechanism. However, the physical interference model not only needs more information to schedule, but also more computational complexity.
    In our research, we develop a status link scheduling algorithm with a centralized and a distributed version under the physical interference model. In this algorithm, we label the status in each node to represent interference relation under the physical interference model. The proposed scheduling algorithm uses limited information and achieves high spacial reuse with the physical interference model under the distributed environment.
    Last, we evaluate the performance of the proposed status link scheduling algorithm incorporating with TDMA and CAMA/CA under workload 1Mbps, 6 Mbps and 9Mbps respectively. The result shows that the proposed status link scheduling algorithm incorporate with TDMA can achieve three times faster than the CSMA disable CA. In addition, we compare the performance of the proposed scheduling algorithm to the DRAND. The performance of the SLS usually is superior to the DRAND algorithm.

    CHAPTER 1 INTRODUCTION 1 1.1 MAJOR ISSUE 3 1.2 OBJECTIVITY OF THIS RESEARCH 4 1.3 CONTRIBUTION OF THIS RESEARCH 5 1.4 ORGANIZATION OF THIS THESIS 5 CHAPTER 2 RELATED WORK 6 CHAPTER 3 NETWORK ARCHITECTURE 7 CHAPTER 4 ALGORITHM 9 4.1 INTERFERENCE IN STATUS LINK SCHEDULING 9 4.2 CENTRALIZED STATUS LINK SCHEDULING 10 4.2.1 Introduce to Centralized Status Link Scheduling 11 4.2.2 Centralized Status Link Scheduling algorithm 12 4.2.3 An example of centralized status link scheduling 16 4.3.1 DRAND algorithm 19 4.3.2 Introduce to Distributed Status Link Scheduling 20 4.3.3 Distributed Status Link Scheduling messages 23 4.3.4 Distributed Status Link Scheduling Algorithm 25 4.3.5 Finite state machine 29 4.4 DRAND-STATUS LINK SCHEDULING WORST CASE BOUNDARY ANALYSIS 30 CHAPTER 5 SIMULATIONS 32 5.1 SIMULATION ENVIRONMENTS 32 5.2 SIMULATION RESULTS 34 5.2.1 Different topologies 34 5.2.1 Enhance signal power level 39 5.2.1 Random network topology 42 CHAPTER 6 CONCLUSION 47 REFERENCES 48

    [1] J. Bicket, D. Aguayo, S. Biswas, R. Morris. Architecture and Evaluation of an Unplanned 802.11b Mesh Networks. In Proceedings of the 11th annual international conference on Mobile computing and networking, pages 31-42, Cologne, Germany, August 28-September 02, 2005.
    [2] J. Gronkvist. Assignment Methods for Spatial Reuse TDMA. In Proceedings of the 1st ACM international symposium on Mobile ad hoc networking & computing, pages 119-124, Boston, Massachusetts, November 20, 2000.
    [3] K. Jain, J. Padhye, V. Padmanabhan, L. Qiu. Impact of Interference on Multi Hop Wireless Network Performance. In ACM Annual International Conference on Mobile Computing and Networking (MOBICOM), pages 66–80, September 2003.
    [4] P. Gupta and P.R. Kumar. The Capacity of Wireless Networks. In IEEE Trans. Info. Theory, Vol. 46, No. 2, pages 388–404, 2000.
    [5] P. Bjorklund, P. Varbrand, and D. Yuan. Resource Optimization of Spatial TDMA in Ad Hoc Radio Networks: A Column Generation Approach. In Proceedings of INFOCOM. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications Societies., Vol.2, pages 818-824, San Francisco, March 2003.
    [6] P. Varbrand and D. Yuan. Maximal Throughput of Spatial TDMA in Ad Hoc Networks. In The 3rd Scandinavian Workshop on Wireless Ad-hoc Networks, Stockholm, Sweden, May, 2003.
    [7] G. Brar, D. Blough, and P. Santi. Computationally Efficient Scheduling with the Physical Interference Model for Throughput Improvement in Wireless Mesh Networks. In Proceedings of the 12th International Conference on Mobile Computing and Networking (MOBICOM), pages 2-13, Los Angeles, CA, USA, 2006.
    [8] R. Nelson and L. Kleinrock. Spatial-TDMA: A Collison-free Multihop Channel Access Protocol. In IEEE Trans. on Communication, Vol. 33, pages 934–944, September, 1985.
    [9] Injong Rhee, Ajit Warrier, Jeongki Min, Lisong Xu. DRAND: distributed randomized TDMA scheduling for wireless ad-hoc networks. In Proceedings of the seventh ACM international symposium on Mobile ad hoc networking and computing, pages 190-201, Florence, Italy, May 22-25, 2006.
    [10] The Network Simulator - ns-2. http://www.isi.edu/nsnam/ns
    [11] SINR module developed by Department of Information Engineering, University of Padova, Italy. http://www.dei.unipd.it/wdyn/?IDsezione=5090
    [12] DRAND website: http://www4.ncsu.edu/~rhee/export/zmac/software/drand/drand.htm

    QR CODE