分散式時空性排程的水底感測器網路媒體存取協定

Abstract

自古以來，人類歷史的演進便與海洋息息相關；隨著技術改進，在陸地上廣為應用的感測器網路也開始被運用在水底。然而，因為水中的傳播環境與陸上相當不同，獨特的性質讓水底感測器網路衍生許多挑戰。

本篇論文的主題，在於設計一個水底感測器網路的媒體存取層排程法。為了改良原本中央式作法Traffic-based One-step Trial Approach (TOTA)所不足的規模可伸縮性，本篇研究所提出的分散式時空演算法，Distributed Traffic-based One-step Trial Approach (DTOTA)，既保留了原本中央式處理的優點，也以更低的代價進行排程、更機動的方式動態調整行程。 DTOTA是接收端導向(Receiver-driven)的排程法。排程順序根據感測器距離基地台的遠近，由最近的感測器開始向外擴散。同階級(Level)的感測器，會在同一個時期(Epoch)進行排序。每個時期又可分成兩階段，分別為排程階段(Scheduling Phase)與復原階段(Recovery Phase)。感測器在排程階段指定連結行程，遵循依序(Ordering)的機制，減少發生衝突的可能；一旦任何感測器發現排程結果產生衝突，便在復原階段利用復原(Recovery)機制調整行程以排除衝突。利用依序和復原這兩種機制，我們可以確保最後的排程結果無衝突(Conflict-free)。

在動態調整行程的部份，我們運用Paused Frame來讓所有位於干擾範圍內的節點都能得知更動後的新行程。一旦有多個行程調整需求同時發生，為避免接收者混淆，我們也運用取消(Cancellation)與Exponential Back-off的機制來停止行程更新並分散連續碰撞的可能。 經實驗顯示，DTOTA比起中央式處理的TOTA大大減少了建構行程的費用。網路產出部份，DTOTA與TOTA相當接近，更大幅領先同為分散式作法的Staggered TDMA Underwater Mac Protocol(STUMP)。DTOTA也保有了分散式排程法的彈性，在動態調整行程所需費用上遠低於TOTA。

From ancient times, human history is associated closely with ocean. As technology progressing, people start to use sensors underwater. However, there are many characteristics of Underwater Sensor Network (UWSN) different from those of terrestrial networks. These environment limits cause new problems and new challenges. In this thesis, we focus on the design of an Underwater Sensor Network MAC scheduling protocol. In order to improve the scalability of centralized scheduling algorithm, Traffic-based One-step Trial Approach (TOTA), we propose a distributed algorithm to assign schedules. Distributed Traffic-based One-step Trial Approach (DTOTA) is a receiver-driven scheduling algorithm. Schedule assignments start from sensor nodes nearest from sink, propagating in a level by level fashion. The scheduling procedure can be divided into several epochs, each with two phases: Scheduling phase and Recovery phase. Sensor nodes assign schedules for responsible edges in Scheduling phase. With the aid of Ordering mechanism, the probability of conflicted schedule results can be reduced. Whenever there is a conflict, sensor nodes can trigger the Recovery mechanism to adjust previous schedules. Eventually, the schedule assignments of all links will be conflict-free. In the part of adaptation, we use Paused Frame to transmit new schedules to all nodes within interference range. Whenever there are multiple adaptation requests happen simultaneously, in order to avoid the confusion of receiver, we use the cancellation mechanism to revoke new schedule notifications and postpone them with exponential back-off. From simulation results, DTOTA shows a great improvement in scalability from TOTA. In network throughput, DTOTA can achieve 94% of TOTA, and 25% more than the other distributed scheduling method, Staggered TDMA Underwater Mac Protocol (STUMP). We also show that DTOTA maintains much lower adaptation overhead, even with the growing of network scale.