周承復臺灣大學:資訊工程學研究所賴廣甫Lai, Kuang-FuKuang-FuLai2010-06-022018-07-052010-06-022018-07-052007U0001-2207200819310100http://ntur.lib.ntu.edu.tw//handle/246246/184777為了更有效率的開發與保護佔地球面積70%的海洋資源,將感測器網路從陸 延伸至水底下愈顯重要。而有別於陸上感測器網路,水底感測器網路的種種特 衍生新的問題與挑戰。 篇論文是設計媒體存取的排程方法。以節省電力與提升網路產出( Network hroughput )為目標,設計節省能源的水底專用的媒體存取排程;並且克服水底 測器網路中,因為時空不確定性( Spatial-Temporal Uncertainty )所引發的排程 題;簡稱為 ST-MAC。水底感測器網路的時空不確定性,是由於使用聲波傳輸 號,其高傳輸延遲( High Propagation Delay )所導致。所以我們建構時空衝突關 圖( Spatial-Temporal Conflict Graph ),記錄兩兩傳輸連結之間的衝突,簡稱為 T-CG;克服此水底感測器網路的排程困難。我們稱這樣子的排程為時空性排程( patial-Temporal Scheduling )。 先,我們以混合整數線性規劃( Mixed Integer Linear Programming ),解出 類問題( NP複雜度)的最佳排程;另外,此類問題也可等同 ST-CG的新圖論著 ( Graph Coloring )問題;在此我們提出新的策略( Heuristic )解法,稱為 TOTA( raffic-based + One-step Trial Approach )。它考慮高傳輸延遲與每個連結的資料傳輸量等因素,嘗試解出比傳統的策略解法更好的媒體存取排程( MACSchedule )。 後,我們以 NS2 模擬水底感測器網路。經實驗顯示,在網路產出,ECDiG ST-CG比原來的 ECDiG[5]有數倍的提升;表示 ST-MAC的 ST-CG克服時空不確 性,避免封包碰撞,進而提升網路產出。此外,TOTA比 ECDiG+ST-CG能再 升些許網路產出( 大約10% ),顯示對於此新圖論著色問題,TOTA是更好的策 。而在電力消耗上,相比 S-MAC[23],ST-MAC系列的電力消耗更少。Underwater Sensor Network( UWSN)is an extended application of sensor network from errestrial environment to underwater environment. UWSNis different from terrestrial ensor network. Data is transmitted by acoustic signals. Hence, the difference causes ew problems and makes challenges. n this thesis, we propose a Spatial-Temporal MACScheduling, ST-MAC. It is an esign of MACscheduling to overcome the Spatial-Temporal Uncertainty toward the nergy saving and increment of network throughput. The uncertainty is caused by igh propagation delay of acoustic signals in UWSN. Hence, we construct the Spatial- emporal Conflict Graph, ST-CG, to record conflict delay between 2 transmission sched- les. By using ST-CG, we perform a scheduling named Spatial-Temporal Scheduling o solve the uncertainty. irstly, we formulate the solution of Spatial-Temporal Scheduling( NPComplexity by using Mixed Integer Linear Programming. Secondly, this problem can be treated s a new graph coloring problem of ST-CG. Therefore, we propose a heuristic, Traffic- ased One-step Trial Approach( TOTA). It considers high propagation delay and traffic load of each links. Try to get a better MACschedule than traditional heuristics. inally, we use NS2 to simulate UWSN. From experiments, the network through- ut of ECDiG+ST-CGis few times than ECDiG. This shows ST-MACcan overcome the patial-Temporal Uncertainty to avoid packet collisions and increase network through- ut. Besides, TOTAcan increase more 10% network throughput than ECDiG+ST-CG. his demonstrate TOTAis a better heuristic approach for ST-CG’s graph coloring roblem. And on evaluating energy cost, the transmission energy per packet of ST- ACseries is less than the one of S-MAC.口試委員會審定書. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii 要與關鍵詞. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii bstract and Keyword. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v able of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii ist of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x erminology. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xii hapter 1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 .1 Background Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 .2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 .3 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 .4 Main Contribution. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 .5 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 hapter 2 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 .1 S-Mac[23] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 .2 UWAN-MAC[16] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 .3 ECDiG[5] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 hapter 3 ST-MACProtocol Design. . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 .1 Overview of ST-MAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 .2 Conflict graph Construction . . . . . . . . . . . . . . . . . . . . . . . . . . 15 .2.1 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 .2.2 衝突時間差. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 .2.3 衝突關係之狀況探討. . . . . . . . . . . . . . . . . . . . . . . . . 18 .2.4 Conflict Graph 建構範例. . . . . . . . . . . . . . . . . . . . . . . 22 .3 Theoretical Analysis: Formulation of Spatial-Temporal Scheduling . . . 22 .3.1 Propagation Delay Constraint . . . . . . . . . . . . . . . . . . . . 23 .3.2 Inter-frame Constraint . . . . . . . . . . . . . . . . . . . . . . . . . 27 .3.3 Splittable Constraint . . . . . . . . . . . . . . . . . . . . . . . . . . 30 .4 Traffic-based One-Step Trial Approach . . . . . . . . . . . . . . . . . . . 33 .4.1 One-step Trial Approach . . . . . . . . . . . . . . . . . . . . . . . 33 hapter 4 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 .1 Simulation Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 .2 Small Topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 .2.1 Network Throughput in Small topology . . . . . . . . . . . . . . 39 .2.2 Energy Cost in Small topology . . . . . . . . . . . . . . . . . . . 40 .3 Large Topology. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 .3.1 Throughput Comparison in Large Topology . . . . . . . . . . . . 41 .3.2 Energy Cost in Large Topology . . . . . . . . . . . . . . . . . . . 41 hapter 5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44application/pdf3904512 bytesapplication/pdfen-US水底感測器網路媒體存取排程時空不確定性高延遲時間Underwater Sensor NetworkMACSchedulingSpatial-Temporal UncertaintyHigh Propagation Delay[SDGs]SDG16thesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/184777/1/ntu-96-R95922005-1.pdf