請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/43761
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 周承復(Cheng-Fu Chou) | |
dc.contributor.author | Ying-Ru Lai | en |
dc.contributor.author | 賴盈如 | zh_TW |
dc.date.accessioned | 2021-06-15T02:27:54Z | - |
dc.date.available | 2009-08-21 | |
dc.date.copyright | 2009-08-21 | |
dc.date.issued | 2009 | |
dc.date.submitted | 2009-08-17 | |
dc.identifier.citation | [1] C. Bron and J. Kerbosch. Algorithm 457: finding all cliques of an undirected graph. Commun. ACM, 16(9):575–577, 1973.
[2] N. Chirdchoo, W.-S. Soh, and K. C. Chua. Aloha-based mac protocols with collision avoidance for underwater acoustic networks. In INFOCOM 2007. 26th IEEE International Conference on Computer Communications. IEEE, pages 2271–2275, May 2007. [3] I. A. Dario, I. F. Akyildiz, D. Pompili, and T. Melodia. Underwater acoustic sensor networks: Research challenges. Ad Hoc Networks (Elsevier, 3:257–279, 2005. [4] J. Heidemann, W. Ye, J. Wills, A. Syed, and Y. Li. Research challenges and applications for underwater sensor networking. In In Proceedings of the IEEE Wireless Communications and Networking Conference, pages 228–235, 2006. [5] C.-C. Hsu, K.-F. Lai, C.-F. Chou, and K.-J. Lin. St-mac: Spatial-temporal mac scheduling for underwater sensor networks. In INFOCOM 2009. The 28th Conference on Computer Communications. IEEE, pages 1827–1835, April 2009. [6] X. L. Huang and B. Bensaou. On max-min fairness and scheduling in wireless ad-hoc networks: analytical framework and implementation. In MobiHoc ’01: Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, pages 221–231, New York, NY, USA, 2001. ACM. [7] Y. Jian and S. Chen. Can csma/ca networks be made fair? In MobiCom ’08: Proceedings of the 14th ACM international conference on Mobile computing and networking, pages 235–246, New York, NY, USA, 2008. ACM. [8] K. Makino and T. Uno. New algorithms for enumerating all maximal cliques. pages 260–272. 2004. [9] M. Molins and M. Stojanovic. Slotted fama: a mac protocol for underwater acoustic networks. In OCEANS 2006 - Asia Pacific, pages 1–7, May 2006. [10] C. H. Papadimitriou and K. Steiglitz. Combinatorial optimization: algorithms and complexity. Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1982. [11] A. Rao and I. Stoica. An overlay mac layer for 802.11 networks. In MobiSys ’05: Proceedings of the 3rd international conference on Mobile systems, applications, and services, pages 135–148, New York, NY, USA, 2005. ACM. [12] A. Sridharan and B. Krishnamachari. Max-min fair collision-free scheduling for wireless sensor networks. In Performance, Computing, and Communications, 2004 IEEE International Conference on, pages 585–590, 2004. [13] A. A. Syed, W. Ye, J. Heidemann, and B. Krishnamachari. Understanding spatiotemporal uncertainty in medium access with aloha protocols. In WuWNet ’07: Proceedings of the second workshop on Underwater networks, pages 41–48, New York, NY, USA, 2007. ACM. [14] L. Tassiulas and S. Sarkar. Maxmin fair scheduling in wireless ad hoc networks. Selected Areas in Communications, IEEE Journal on, 23(1):163–173, Jan. 2005. [15] E. Tomita, A. Tanaka, and H. Takahashi. The worst-case time complexity for generating all maximal cliques and computational experiments. Theor. Comput. Sci., 363(1):28–42, 2006. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/43761 | - |
dc.description.abstract | 隨著科技的進步, 最近逐漸受到重視的水底感測網路(Underwater Sensor Network)提供了人們對海洋作更深入探索的機會。而在水底感測網路這種頻寬極小的環境中, 如何適當地應用有限頻寬變得十分地重要。
本論文主要是針對水底感測網路的極大極小公平(Max-Min Fairness)的問題做一些討論。在水底感測網路中,較長的傳輸延遲(propagation delay)將會導致它的傳輸和陸地上的無線感測網路有所不同, 我們稱之所造成的影響為時空不確定性(Spatial-Temporal Uncertainty)。而連線其實可以利用這個時空的不確定性來增加頻寬在時間上的再利用。因此,在陸地上所使用計算極大極小公平速率配置(Rate Allocation)的方法已不再適用在水底感測網路。為了呈現時空不確定性造成的影響, 我們提出了一個時間延展衝突關係圖(Time Expanded Conflict Graph) 來檢視水底感測網路中真正的衝突關係。接著,在考慮多重跳躍資料流(Multi-hop flow)的影響後, 我們提出了一個端點對端點(end-to-end)極大極小公平速率配置方法的擴充。最後我們將以網路模擬程式的結果來呈現我們所提出的極大極小公平速率配置的方法的確會比原本陸地上計算出的配置公平且產出效能高。 | zh_TW |
dc.description.abstract | According to the progress of technology, Underwater Sensor Networks (UWSNs), which becomes attractive recently, provides the chance for human to explore more about the ocean. In such low bandwidth environment, using limited bandwidth more suitable is very important.
This paper addresses the max-min fairness problem in UWSNs. The characteristic of long propagation delay in UWSNs make the new challenge for MAC protocol designs, called Spatial-Temporal Uncertainty. The links can exploit the spatial-temporal uncertainty to improve the temporal reuse of a bandwidth allocation. Thus, the max-min fairness rate derived by the approach for terrestrial scenarios can not work in UWSNs. To eliminate the spatial-temporal uncertainty, we propose Time Extended Conflict Graph (TECG) to represent the conflict relationship under spatial-temporal uncertainty. We also extend the proposed algorithm to provide end-to-end fairness assignment for multi-hop flows. Finally, a comprehensive study is presented and our simulation results show that our proposed max-min fairness solution can perform better than existing solutions for terrestrial wireless networks in term of the network throughput and fairness. | en |
dc.description.provenance | Made available in DSpace on 2021-06-15T02:27:54Z (GMT). No. of bitstreams: 1 ntu-98-R96944011-1.pdf: 1696735 bytes, checksum: 99d8173fff041d99e3bdc2300b46b6d4 (MD5) Previous issue date: 2009 | en |
dc.description.tableofcontents | 口試委員會審定書2
中文摘要3 Abstract 4 1 Introduction 9 1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.1.1 Underwater Wireless Sensor Network(UWSN) . . . . . . . . . . 9 1.1.2 Max-Min Fairness . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.3 Main Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.4 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2 System Model 13 2.1 Max-Min Fairness Rate Allocation in Terrestrial WSN . . . . . . . . . . 13 2.2 Spatial-Temporal Conflict Graph . . . . . . . . . . . . . . . . . . . . . . 15 3 Time Expanded Conflict Graph 16 3.1 Key Idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.2 Construct TECG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.3 Characteristic of TECG . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.3.1 Finding by each vertex . . . . . . . . . . . . . . . . . . . . . . . 18 3.3.2 Finding by Conflict Delay <= 0 . . . . . . . . . . . . . . . . . . . 18 3.3.3 Sum of Conflict Delay should be 0 . . . . . . . . . . . . . . . . . 19 4 Max-Min Fairness Rate Allocation in UWSN 21 4.1 Centralized Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.1.1 Getting Compact TECG . . . . . . . . . . . . . . . . . . . . . . 21 4.1.2 Calculating Rate Allocation . . . . . . . . . . . . . . . . . . . . 22 4.1.3 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4.2 Flow Constraint . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.2.1 Refined Method . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.2.2 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 5 Performance Evaluation 25 5.1 Simulation Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 5.2 Simulation Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 5.3 Minimizing Size of Compact TECG . . . . . . . . . . . . . . . . . . . . 27 6 Conclusion 29 Bibliography 29 A Finding All Maximal Cliques 32 | |
dc.language.iso | zh-TW | |
dc.title | 探討水底感測網路的極大極小公平問題 | zh_TW |
dc.title | Discussing Max-Min Fairness Problem in Underwater Sensor Network | en |
dc.type | Thesis | |
dc.date.schoolyear | 97-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 陳伶志(Ling-Jyh Chen),逄愛君(Ai-Chun Pang),蔡明哲(Ming-Jer Tsai),趙禧綠(Hsi-Lu Chao) | |
dc.subject.keyword | 水底感測網路,極大極小公平,時空不確定性,較長的傳輸延遲,速率配置,端點對端點, | zh_TW |
dc.subject.keyword | Underwater Sensor Network,Max-Min Fairness,Spatial-Temporal Uncertainty,Long Propagation Delay,Rate Allocation,End-to-End, | en |
dc.relation.page | 32 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2009-08-17 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 資訊網路與多媒體研究所 | zh_TW |
顯示於系所單位: | 資訊網路與多媒體研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-98-1.pdf 目前未授權公開取用 | 1.66 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。