- 學位論文
時空性排程的水底感測器網路媒體存取協定
A Spatial-Temporal Scheduling MAC protocol for Underwater Sensor Network
摘要
為了更有效率的開發與保護佔地球面積70%的海洋資源,將感測器網路從陸 上延伸至水底下愈顯重要。而有別於陸上感測器網路,水底感測器網路的種種特 性衍生新的問題與挑戰。 本篇論文是設計媒體存取的排程方法。以節省電力與提升網路產出( Network Throughput )為目標,設計節省能源的水底專用的媒體存取排程;並且克服水底 感測器網路中,因為時空不確定性( Spatial-Temporal Uncertainty )所引發的排程 問題;簡稱為 ST-MAC。水底感測器網路的時空不確定性,是由於使用聲波傳輸 訊號,其高傳輸延遲( High Propagation Delay )所導致。所以我們建構時空衝突關 係圖( Spatial-Temporal Conflict Graph ),記錄兩兩傳輸連結之間的衝突,簡稱為 ST-CG;克服此水底感測器網路的排程困難。我們稱這樣子的排程為時空性排程( Spatial-Temporal Scheduling )。 首先,我們以混合整數線性規劃( Mixed Integer Linear Programming ),解出 這類問題( NP複雜度)的最佳排程;另外,此類問題也可等同 ST-CG的新圖論著 色( Graph Coloring )問題;在此我們提出新的策略( Heuristic )解法,稱為 TOTA( Traffic-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 terrestrial environment to underwater environment. UWSNis different from terrestrial sensor network. Data is transmitted by acoustic signals. Hence, the difference causes new problems and makes challenges. In this thesis, we propose a Spatial-Temporal MACScheduling, ST-MAC. It is an design of MACscheduling to overcome the Spatial-Temporal Uncertainty toward the energy saving and increment of network throughput. The uncertainty is caused by high propagation delay of acoustic signals in UWSN. Hence, we construct the Spatial- Temporal Conflict Graph, ST-CG, to record conflict delay between 2 transmission sched- ules. By using ST-CG, we perform a scheduling named Spatial-Temporal Scheduling to solve the uncertainty. Firstly, we formulate the solution of Spatial-Temporal Scheduling( NPComplexity ) by using Mixed Integer Linear Programming. Secondly, this problem can be treated as a new graph coloring problem of ST-CG. Therefore, we propose a heuristic, Traffic- based 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. Finally, we use NS2 to simulate UWSN. From experiments, the network through- put of ECDiG+ST-CGis few times than ECDiG. This shows ST-MACcan overcome the Spatial-Temporal Uncertainty to avoid packet collisions and increase network through- put. Besides, TOTAcan increase more 10% network throughput than ECDiG+ST-CG. This demonstrate TOTAis a better heuristic approach for ST-CG’s graph coloring problem. And on evaluating energy cost, the transmission energy per packet of ST- MACseries is less than the one of S-MAC.
參考文獻
延伸閱讀
- 杞權恆（2012）。在水下感測網路中具高頻寬利用率之多頻道媒體存取控制協定〔碩士論文，淡江大學〕。華藝線上圖書館。https://doi.org/10.6846/TKU.2012.00987
- 張佳銘（2011）。在水下聲波網路中，設計一改善頻寬利用率之頻道竊用媒介存取控制協定〔碩士論文，淡江大學〕。華藝線上圖書館。https://doi.org/10.6846/TKU.2011.00534
- Tsai, I. C. (2009). 在水底感測網路中之多重路徑繞徑協定 [master's thesis, National Taipei Uinversity]. Airiti Library. https://www.airitilibrary.com/Article/Detail?DocID=U0023-2408200922343800
- 李隆顥（2015）。無線水下感測網路中具資料時效性考量的資料收集機制〔碩士論文，淡江大學〕。華藝線上圖書館。https://doi.org/10.6846/TKU.2015.01026
- Chen, Y. S., Juang, T. Y., Lin, Y. W., & Tsai, I. C. (2010). A Low Propagation Delay Multi-Path Routing Protocol for Underwater Sensor Networks. 網際網路技術學刊, 11(2), 153-165. https://doi.org/10.6138/JIT.2010.11.2.03