周承復Chou, Cheng-Fu臺灣大學:資訊網路與多媒體研究所賴盈如Lai, Ying-RuYing-RuLai2010-05-052018-07-052010-05-052018-07-052009U0001-1708200912524100http://ntur.lib.ntu.edu.tw//handle/246246/180723隨著科技的進步， 最近逐漸受到重視的水底感測網路（Underwater Sensor Network）提供了人們對海洋作更深入探索的機會。而在水底感測網路這種頻寬極小的環境中， 如何適當地應用有限頻寬變得十分地重要。論文主要是針對水底感測網路的極大極小公平（Max-Min Fairness）的問題做一些討論。在水底感測網路中，較長的傳輸延遲（propagation delay）將會導致它的傳輸和陸地上的無線感測網路有所不同， 我們稱之所造成的影響為時空不確定性（Spatial-Temporal Uncertainty）。而連線其實可以利用這個時空的不確定性來增加頻寬在時間上的再利用。因此，在陸地上所使用計算極大極小公平速率配置（Rate Allocation）的方法已不再適用在水底感測網路。為了呈現時空不確定性造成的影響， 我們提出了一個時間延展衝突關係圖（Time Expanded Conflict Graph） 來檢視水底感測網路中真正的衝突關係。接著，在考慮多重跳躍資料流（Multi-hop flow）的影響後， 我們提出了一個端點對端點（end-to-end）極大極小公平速率配置方法的擴充。最後我們將以網路模擬程式的結果來呈現我們所提出的極大極小公平速率配置的方法的確會比原本陸地上計算出的配置公平且產出效能高。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.his 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.口試委員會審定書2文摘要3bstract 4 Introduction 9.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.1.1 Underwater Wireless Sensor Network(UWSN) . . . . . . . . . . 9.1.2 Max-Min Fairness . . . . . . . . . . . . . . . . . . . . . . . . . 10.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.3 Main Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12.4 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 System Model 13.1 Max-Min Fairness Rate Allocation in Terrestrial WSN . . . . . . . . . . 13.2 Spatial-Temporal Conflict Graph . . . . . . . . . . . . . . . . . . . . . . 15 Time Expanded Conflict Graph 16.1 Key Idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16.2 Construct TECG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16.3 Characteristic of TECG . . . . . . . . . . . . . . . . . . . . . . . . . . . 17.3.1 Finding by each vertex . . . . . . . . . . . . . . . . . . . . . . . 18.3.2 Finding by Conflict Delay 0 . . . . . . . . . . . . . . . . . . . 18.3.3 Sum of Conflict Delay should be 0 . . . . . . . . . . . . . . . . . 19 Max-Min Fairness Rate Allocation in UWSN 21.1 Centralized Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.1.1 Getting Compact TECG . . . . . . . . . . . . . . . . . . . . . . 21.1.2 Calculating Rate Allocation . . . . . . . . . . . . . . . . . . . . 22.1.3 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22.2 Flow Constraint . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23.2.1 Refined Method . . . . . . . . . . . . . . . . . . . . . . . . . . . 23.2.2 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 Performance Evaluation 25.1 Simulation Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25.2 Simulation Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25.3 Minimizing Size of Compact TECG . . . . . . . . . . . . . . . . . . . . 27 Conclusion 29ibliography 29 Finding All Maximal Cliques 32application/pdf1696735 bytesapplication/pdfen-US水底感測網路極大極小公平時空不確定性較長的傳輸延遲速率配置端點對端點Underwater Sensor NetworkMax-Min FairnessSpatial-Temporal UncertaintyLong Propagation DelayRate AllocationEnd-to-Endthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/180723/1/ntu-98-R96944011-1.pdf