Chapter 3 MAC (Media Address Control) Layer

Chapter 3 Outline 3.1. 802.11 碰撞議題相關研究 3.2. 802.11 MAC機制 3.1. 802.11 碰撞議題相關研究 3.2. 802.11 MAC機制 3.3. 802.11 節能、省電議題相關研究 3.4. 802.15.4 MAC 3.5. MAC protocols for WSN Jang Ping Sheu 2019/10/282019/10/28

Chapter 3 Outline 3.1. 802.11 碰撞議題相關研究 3.2. 802.11 MAC機制 3.1. 802.11 碰撞議題相關研究 3.2. 802.11 MAC機制 3.3. 802.11 節能、省電議題相關研究 3.4. 802.15.4 MAC 3.5. MAC protocols for WSN Jang Ping Sheu 2019/10/282019/10/28

(Slotted)ALOHA、CSMA、MACA Collision Avoidance Reservation based TDMA、FDMA、CDMA (Slotted)ALOHA、CSMA、MACA Contention based Reservation-based 利用分配的方法來決定該時間或該頻道有誰可以傳送。 Contention-based 利用競爭的方式來決定誰可以傳送。 Hybrid 通常結合前面 Reservation-based、Contention-based方法。 DAMA Hybrid Jang Ping Sheu 2019/10/282019/10/28

Reservation Based TDMA → 一個點可以用到的較多頻寬，輪到時間較短。 F(頻帶) 1 2 3 4 … n 1 在不同時槽給不同節點使用。利用每個節點在不同時間傳送，來避免彼此間互相碰撞。 1 2 3 4 … n 1 T(時間) Jang Ping Sheu 2019/10/282019/10/28

Reservation Based FDMA → 一個點可以一直傳送，但頻寬較少。 F(頻帶) Guard Band T(時間) 每個節點在不同的frequency做傳送以免互相干擾。Guard Band是保留的頻帶，目的是為了減少不同頻代之間的干擾。 Jang Ping Sheu 2019/10/282019/10/28

Reservation Based CDMA CDMA can transmission in the same space and time Code Frequency Time 在原本的Frequency、Time做切割下，多切割一份資源Code-正交碼基地台對於不同的節點給予不同的正交碼來避開在相同頻道且相同時間下產生碰撞。 FDMA、TDMA can use resource Jang Ping Sheu 2019/10/282019/10/28

G (Attempts per Packet Time) Contention Based Pure ALOHA 當想要傳送Data時就直接往外傳送。 特點：traffic load low → 成功率高，反之碰撞率高 Slotted ALOHA 加入slotted概念，在每個slot的開始點才可以傳送。 特點：改善了隨時隨地都有可能有結點來撞封包的缺點。 S (Throughput per Packet Time) 0.4 0.3 0.2 0.1 0.5 1.0 1.5 2.0 3.0 G (Attempts per Packet Time) Slotted ALOHA Pure ALOHA Jang Ping Sheu 2019/10/282019/10/28

Contention Based 1-persistent CSMA Non-persistent CSMA When medium is Idle → Transmit Busy → Continue listening(Carrier Sense) Non-persistent CSMA Idle → transmit Busy →Wait an amount of time drawn from a probability distribution and repeat to listen Jang Ping Sheu 2019/10/282019/10/28

Contention Based p-persistent CSMA When medium is Idle → transmit probability： transmit probability : p defer probability : 1- p Busy → listen until medium is idle Note： For 1-persistent CSMA Transmit probability 1) transmit probability : 1 2) defer probability : 0 Jang Ping Sheu 2019/10/282019/10/28

Contention Based MACA (Multiple Access with Collision Avoidance) NAV (Network Allocation Vector) RTS CTS GET RTS: Can transmit but can’t receive Disadvantage: GET CTS: Can receive but can’t transmit Can’t check frame GET CTS and RTS: Can’t transmit and receive transmission success or not Sender Receiver MACA的特色是要傳之前不用再去聽網路有沒有人在傳送。 他用收到的RTS與CTS狀況來決定是否可以傳送。 收到RTS的區域是可以傳送的，因為碰撞是發生在收端，但收到RTS的人是沒辦法接收檔案的。 收到CTS的區域代表是不能傳送資料給其他節點的。因為收到CTS代表他在Receiver的傳輸半徑內，如果此時送資料將會打斷Receiver的資料傳送。 收到RTS與CTS的代表他不能接收資料也不能傳送資料。 缺點：無線網路的傳送，相對於有線網路更容易發生封包遺失或者封包錯誤的事件出現。因為MACA把ACK機制拿去，使得沒辦法確認封包是否平安送達。 這點在於無線網路是一個很嚴重的缺點。 Jang Ping Sheu 2019/10/282019/10/28

Hybrid DAMA (Demand Assigned Multiple Access) Two phases: 1) Contention-based: use slotted ALOHA 2) Reservation-based: use reservation list Disadvantage: Maintain reservation list 在Reservation based的時段裡可能使用的技術有 TDMA,FDMA,CDMA 等等 Slotted ALOHA reserved time Jang Ping Sheu 2019/10/282019/10/28

Chapter 3 Outline 3.1. 802.11 碰撞議題相關研究 3.2. 802.11 MAC機制 3.1. 802.11 碰撞議題相關研究 3.2. 802.11 MAC機制 3.3. 802.11 節能、省電議題相關研究 3.4. 802.15.4 MAC 3.5. MAC protocols for WSN Jang Ping Sheu 2019/10/282019/10/28

MAC Medium Access Control(MAC) 無線網路中主要的功能為 碰撞控制 存取控制 排程機制 醒睡省電機制 Layer 7 Application layer Layer 6 Presentation layer Layer 5 Session layer Layer 4 Transport layer Layer 3 Network layer Layer 2 Data-Link layer LLC MAC Layer 1 Physical layer IEEE 802.11主要定義無線網路的傳輸方式。而定義的標準機制分佈於OSI七層中的Data-Link layer的子層mac layer與Physical layer。 (Wireless STD) Jang Ping Sheu 2019/10/282019/10/28

802.11訊框結構(Frame Structure) 2-byte 2-byte 6+6+6-byte 2-byte 6-byte 0 ~ 2312-byte 4-byte Frame control Duration Address 1 ~ 3 Seq. Address 4 Data Checksum 2-bit 4-bit 1-bit Version Type Subtype To DS MF From DS Retry Pwr. O W Frame control是用來區別不同的控制封包用的。 在這個欄位下有戲分多種欄位：Version、Type、 Subtype、To DS、From DS、MF、Retry、Pwr.、W、O W欄位代表這個封包是否使用WEP加密。 O欄位代表此封包的處理需不需要照順序處理。 Jang Ping Sheu 2019/10/282019/10/28

802.11訊框結構(Frame Structure) Version Type Subtype To DS From DS MF Retry Pwr. W O Different type for each frame type (EX-in type control has subtype - CTS/RTS) 802.11定義了三種不同MAC層的frame：Data、Control、Management。 控制欄位為Frame Control中的Type欄位。 而後面接的Subtype則是再細分那三種類封包下個不同意義的封包，例如：CTS、RTS、ACK。 Frame type (Data、Control、Management) Jang Ping Sheu 2019/10/282019/10/28

802.11訊框結構(Frame Structure) Version Type Subtype To DS From DS MF Retry Pwr. W O ESS BSS2 BSS1 STA STA STA STA To DS =1 From DS =1 STA IBSS To DS =0 From DS =0 BSS-由一個AP所管轄的區域 Distribution System-由BSS串接而成的網路系統 ESS-由分散式系統跟IBSS的集合 在不同的網路協定之間需要有一個銜接窗口，例如從我們802.11的無線網路分散式系統到另外一個網路系統802.3、802.16等等。 (1) To DS = 0 From DS = 0 在同一個IBSS(Independent Basic Service Set Network)中資料從一個STA傳送到另外一個STA。 (2) To DS = 1 有資料指定要給這個DS(Distribution System) (3) From DS =1 有資料要離開這個DS(Distribution System) (4) 從一個AP送給另外一個AP STA AP1 AP2 Distribution System To DS =1 From DS =0 To DS =0 From DS =1 Portal 802.X (EX:802.3、802.16) Jang Ping Sheu 2019/10/282019/10/28

802.11訊框結構(Frame Structure) Version Type Subtype To DS From DS MF Retry Pwr. W O More fragment? Retransmit ? MF欄位代表要不要切更多的fragments。 Retry欄位代表需不需要重傳。 Pwr.代表送的人要進入sleep狀態或者離開sleep狀態。 W欄位代表這個封包是否使用WEP加密。 O欄位代表此封包的處理需不需要照順序處理。 Sleep ? Jang Ping Sheu 2019/10/282019/10/28

802.11訊框結構(Frame Structure) 2-byte 2-byte 6+6+6-byte 2-byte 6-byte 0 ~ 2312-byte 4-byte Frame control Duration Address 1 ~ 3 Seq. Address 4 Data Checksum Duration of frame Four address (by To DS/ From DS) Source Address(SA) Destination Address(DA) Transmitter Address(TA) – (now address) Receiver Address(RA) – (next address) Duration –封包傳送所需要的時間，某種程度上也代表著封包的長度。 ‧Address 1~4會依據To DS欄位跟From DS欄位來決定要放哪種位址(原則上是越重要的放越前面) - Source Address來源地 - Destination Address目的地 - Transmitter Address現在所在節點的位置 - Receiver Address下一個要去的節點所在位置 ‧Checksum – 檢查封包有沒有出錯的檢查碼 Jang Ping Sheu 2019/10/282019/10/28

MAC Architecture Contention-Free Contention- Services Service Extent Contention-Free Services (Real-time) Distributed Coordination Function (DCF) Contention- Service (Asynchronous) Point Coordination Function (PCF) Jang Ping Sheu 2019/10/282019/10/28

MAC Architecture Distributed Coordination Function (DCF) The fundamental access method for the 802.11 MAC, known as Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA). Shall be implemented in ALL stations and APs. Used within both ad hoc and infrastructure configurations. Point Coordination Function (PCF) An alternative access method Shall be implemented on top of the DCF A point coordinator (polling master) is used to determine which station currently has the right to transmit. Shall be built up from the DCF through the use of an access priority mechanism. Jang Ping Sheu 2019/10/282019/10/28

PCF period ，根據排程好的傳送者進行傳送 802.11傳遞模式 Super frame Super frame PCF period DCF period AP time Beacon CF_END Beacon STA1 802.11中分兩個週期：PCF與DCF PCF週期代表傳送資料全部由AP來做管理。DCF代表傳送資料是使用競爭的方式傳送。當PCF週期中沒拿到資料傳送權，此時AP會讓那個STA進入NAV狀態(不能傳送資料)。例如：上圖中，STA2沒有拿到傳送資料權，此時(PCF週期)他自己會進入NAV狀態。而這兩個是週而復始的不斷循環。 Note： 由於DCF的週期有可能會為了不中斷Data封包所以DCF週期有可能會增加，所以要讓所有的STA知道PCF開始與否就會先發一個beacon(可以順便對時)然後其他的STA才知道PCF開始了。 NAV STA2 PCF週期中沒拿到資料傳送權的STA ，會進入NAV休息狀態 PCF period ，根據排程好的傳送者進行傳送 DCF period ，節點與節點間傳送是互相競爭傳送權的 Jang Ping Sheu 2019/10/282019/10/28

802.11傳遞模式 - PCF週期 DL-下傳封包 ACK-回應封包 Polling-詢問是否有資料上傳 UL-上傳封包 沒傳完的資料怎辦？ 去DCF競爭 or 等待下一個PCF(DCF沒競爭到) PCF Beacon DL Polling ACK DL Polling ACK Polling ACK 2-1-3. PCF and Piggyback機制 PCF全名為Point Coordination Function。一般來說有AP的情況下時是使用PCF模式。PCF是有集中式的管理者時使用。於集中式管理狀況下AP輪詢STA(station)的情況如下圖表示： Beacon封包表示PCF的周期開始，因為在這個時間點內是有集中式管理的。AP會把時間平均分配給下面的STA來服務。如上圖所示，AP會先把要傳給STA1的封包[DL]Download給STA1。而STA1收到DL封包時則會回傳ACK表示收到，然後上傳封包給[UL]AP。最後AP收到會回ACK封包表示收到UL封包。STA2同理。  思考：來回傳遞頻繁IEEE 802.11如何解決？Piggyback .. AP time STA1 ACK UL UL STA2 ACK UL Jang Ping Sheu 2019/10/282019/10/28

802.11傳遞模式 - PCF週期 AP STA1 STA2 Defer beacon The beginning of DCF time CF_END Beacon AP STA1 Data STA2 time Data Data 在DCF週期中STA要上傳資料必需要利用競爭的方式。當聽到CF_END代表DCF週期開始，想傳送資料的STA會先等待一段DIFS時間，然後做Random Backoff(R.B.)機制。利用Random Backoff機制來決定誰搶到上傳機會。如圖STA1在第一筆資料傳完後STA2聽到資料傳完此時他想要傳送一筆資料。就會去等待一段DIFS的時間，然後開始做Random Backoff.結束後開始傳送資料。當AP發現DCF周期時間到時，會去等待正在進行傳送的資料傳完後等待PIFS時間馬上發出Beacon，代表PCF週期要開始了。每次要傳送資料要等待DIFS的時間是為了讓Beacon有大的優先序，因為Beacon封包只需等待PIFS (p16. Priority Scheme)時間。 Defer beacon-週期時間到但是尚未傳完Data，原本要送出的beacon就往後延遲了 DIFS (DCF Inter-frame Space ) , 一段固定的等待時間 Random backoff ，亂數等待時間 PIFS (PCF Interframe Space ) ， 一段固定的等待時間 ， (DIFS > PIFS) Jang Ping Sheu 2019/10/282019/10/28

Piggyback機制 Problem in Original PCF ? 封包來回傳遞太多次，浪費資源。 One frame in multi-message Piggyback Beacon ACK+ DL2+ Polling2 ACK+ DL3+ Polling3 DL1+ Polling1 DL1+ Polling1 CF_END AP 在有AP的情況下，AP會定期去輪詢他所服務的STA。IEEE 802.11中AP會把Download與Polling的訊息弄成同一份封包一起傳送，如圖：AP把DL1+Polling1一起送。此時代表AP把要傳遞給STA1的資料與詢問A有沒有資料要上傳一起處理掉。而STA1收到時則回傳Download的ACK以及如果有資料要上傳時，則會把他跟ACK打包一起上傳，如圖：ACK+UL1。當AP收到ACK+UL1時則會把UL1的ACK(給STA1)跟DL2(AP要給STA2的資料)、Polling2(問第二個STA要不要傳送資料給AP)同時傳給STA1、STA2。此機制稱為Piggyback機制。AP會利用等待PIFS的時間來判定STA是否還在或者STA已經離開。 STA1 ACK+ UL1 ACK+ UL1 STA2 time ACK+ UL2 STA3沒回ACK (超過PIFS認定他不在) PIFS (PCF Interframe Space ) Jang Ping Sheu 2019/10/282019/10/28

DCF Operation MAC begins frame transmission If both PHY and virtual carrier sense mechanisms indicate the medium is idle for an interval of DIFS (or EIFS if previously received frame contained errors). If medium is busy during the DIFS interval, Backoff interval is selected and increment retry counter For each slot time, if medium is detected to be idle, decrement backoff interval; MAC begins to transmit if backoff interval is expired. If the transmission is not successful (i.e. collision), CW is doubled and new backoff interval is selected and countdown is begun, again. When to stop? Jang Ping Sheu 2019/10/282019/10/28

Example of Backoff Intervals (2) (3) Backoff=2 DIFS DIFS Backoff=9 DIFS Backoff=4 DIFS (5) busy Station 1 Backoff=5 Packet arrival at MAC busy Station 2 (1) busy Station 3 Backoff=7 Backoff=2 (4) busy Station 4 After packet arrival at MAC, station 3 senses medium free for DIFS, so it starts transmission immediately (without backoff interval). For station 1,2, and 4, their DIFS intervals are interrupted by station 3. Thus, backoff intervals for station 1,2, and 4, are generated randomly (i.e. 9,5, and 7, respectively). After transmission of station 2, the remaining backoff interval of station 1 is (9-5)=4. After transmission of station 2, the remaining backoff interval of station 4 is (7-5)=2. After transmission of station 4, the remaining backoff interval of station 1 is (4-2)=2. Jang Ping Sheu 2019/10/282019/10/28

Random backoff 機制 Backoff Counter ： when network busy → B.C. freeze network idle → B.C. decrease BC=3 BC=5 STA1 STA2 BC=3 STA1想傳，會先決定Backoff Counter。STA1經過Backoff機制，決定他的Backoff Counter為5。代表他要過完DIFS之後等待5個slot才可以傳送(不包含DIFS與其他NODE傳送的時間)。而STA3經過計算Backoff Counter為3。當他聽到STA2資料傳完等待DIFS然後等待3個slots開始傳送。當被碰撞到則B.C.重新計算。 --細部參考資料 Random backoff 機制 - Contention Window、Backoff Counter機制  Content Window – CWmin = 31 CWmax = 1023 1)Initial CW = CWmin 2)傳送成功 CW = CWmin 3)傳送失敗 CWnew = CWold * 2 (由下面的Backoff Counter可以看出CW值愈大代表所要等待的時間愈多，傳送失敗代表現在網路忙碌，所以設計理念是讓他在等待久一點。)  Backoff Counter – Random[0,1] * CW * a slot Time Backoff Counter 的計算方式，先去Random一個數值來決定要不要傳送(0不要傳送,1傳送) CW的決定方式如上面Content Window 的說明。假如算出的數值超越CWmax此時使用CWmax。 a slot Time代表的是一個slot所需多少時間。 計算出來的結果就是要等待多少個slots。 STA3 BC=5 BC=2 STA4 DIFS Jang Ping Sheu 2019/10/282019/10/28

DCF: the Random Backoff Time Backoff time = CW* Random() * Slot time CW = starts at CWmin and doubles after each failure until reaching CWmax and remains there in all remaining retries e.g., CWmin = 7, CWmax = 255 Random() = (0,1) Slot Time = Transmitter turn-on delay + medium propagation delay + medium busy detect response time 8 CWmax CWmin 7 15 31 第二次重送 第一次重送 第三次重送 初始值 63 127 255 Jang Ping Sheu 2019/10/282019/10/28

Priority Scheme Goal：Let each frame has different priority SIFS → PIFS → DIFS → EIFS 802.11 DSSS – SIFS(10μs)，PIFS(30μs)，DIFS(50μs)，EIFS(>50μs) DIFS PIFS 在802.11中使用不同的時間差，來達到每個不同封包有不同的傳遞優先權。當所需等待的時間愈少，間接意味這他的優先權愈大。例如：在four-way handshake中，RTS/CTS/DATA/ACK這是一連串的動作，不希望被其他封包給中斷；所以在這些封包間的傳送使用了最高權限的等待時間，使用SIFS，也就是說RTS跟CTS封包的傳遞只需等待SIFS時間段。 Short Interframe Space (SIFS) PCF Interframe Space (PIFS) DCF Interframe Space (DIFS) Extended interframe space (EIFS) SIFS time 1st Priority 2nd Priority 3rd Priority Jang Ping Sheu 2019/10/282019/10/28

CSMA/CA with RTS/CTS Hidden terminal problem → Collision Exposed terminal problem → Waste bandwidth A B C D  Hidden terminal problem A正在傳送資料給B，C想傳送資料給D節點， 但是C節點不知道有人正在傳送資料給B節點， 此時傳送資料給D節點，造成B節點收資料時 產生碰撞。  Exposed terminal problem B傳送資料給A，此時C想傳送資料給D。 但是C發現B正在傳送資料，所以C就停止 傳送資料給D。但事實上C傳送資料給D是 不影響AB傳輸的。 C can send data. But carrier the network is busy A B C D Jang Ping Sheu 2019/10/282019/10/28

CSMA/CA with RTS/CTS Solve hidden terminal problem High overhead NAV(RTS) [LOCK] Sender Neighbor RTS Data Sender Sender Receiver RTS (Request to Send ) CTS (Request to Send ) ----------------------------- 在802.11中為了解決Hidden terminal problem，使用了RTS與CTS的機制。RTS封包用來告訴Sender鄰居，此時Sender的鄰居就會進入禁止傳送的狀態(NAV狀態-Network Allocation Vector)。收端會發送CTS警告他周圍的點，此時他周圍的點也會進入NAV狀態讓其他點不影響送端與收端的傳輸。 Receiver ACK CTS NAV(CTS) [LOCK] Receiver Neighbor time Jang Ping Sheu 2019/10/282019/10/28

Chapter 3 Outline 3.1. 802.11 MAC機制 3.2. 802.11 碰撞議題相關研究 3.2. 802.11 碰撞議題相關研究 3.3. 802.11 節能、省電議題相關研究 3.4. 802.15.4 MAC 3.5. MAC protocols for WSN Jang Ping Sheu 2019/10/282019/10/28

802.11內建省電模式 In 802.11 Power Saving mode 802.11 Infrastructure mode的省電模式 Have AP Ad-hoc mode的802.11省電模式 Only node 這小節會探討的兩種802.11的省電模式。 一種是Infrastructure mode省電模式的討論 在有AP的情況下是一種集中式管理的情形，裡面有分PCF、DCF週期會有其802.11的做法。P.31 一種是802.11 Ad-hoc mode的省電模式的討論 在沒有AP的情況下是一個分散式的系統，裡面會分為Beacon interval、TBIT window、ATIM window。P.32 Jang Ping Sheu 2019/10/282019/10/28

802.11 Infrastructure mode的省電模式 TIM(Traffic Indication Map) TIM record data：Association ID、Buffered(0/1) Mechanism Listen Beacon 1. TIM (if Buffered is 0) Go to SLEEP STATE 2. If Buffer is 1： a. in PCF waiting AP to transmit data b. in DCF 1. STA send PS-Poll to AP 2. AP receives PS-Poll and transmits buffered data 0：no data 1：have data Association ID Buffered TIM表會建立在AP之中。這個TIM表會紀錄哪個NODE是否有資料要做傳送。 欄位如上圖所顯示： Association ID代表的是節點編號， Buffered代表的是是否有資料要接收(其中0代表沒資料要接收，1代表有資料要接收) Association ID – 每個node向AP註冊時，AP就會給node獨立的ID 在infrastructure mode的情況下：NODE收到自己的BUFFER是0他則進入休眠模式。 反之，如果是1 -在PCF週期時則會醒著等待AP傳送資料給他。 -在DCF週期時則節點會送Polling封包給AP，AP收到時則會把buffer資料傳送給他。 Note : 802.11分兩種模式： infrastructure mode、Ad hoc mode infrastructure mode – 一個網路是屬於有AP管理的情況，所以每個節點都是將資料傳送給AP再由AP分配到個節點去。 AP與node間都是1 hop Ad-hoc mode – 節點與節點之間的傳送是沒有AP管理的。都是結點傳節點。屬於multi hop的環境 Jang Ping Sheu 2019/10/282019/10/28

ATIM (Announcement TIM) window 802.11 Ad-hoc mode的省電模式 Beacon interval Beacon interval Data STA1 STA2 Beacon ACK STA3 一個Beacon interval是一個醒睡週期， 在這週期裡面有分TBIT window以及ATIM window。 TBIT window會去聽beacon來知道這個週期有多長以及時間同步。 ATIM window會去競爭交換資料的使用權。 -ATIM ,告知要交換資料 -ATIM_ACK ,回應說可以 有資料交換的在到下一個Beacon interval之前皆會醒著，反之沒有資料的就會去睡覺等待下一個Beacon interval。 圖解： 在TBIT時間與ATIM的時間所有的節點皆必需都為ACTIVE STATE。 有資料要交換的STA會在ATIM window開始丟ATIM封包給要交換的對象。 當對方同意交換資料則會回ATIM_ACK。 然後在Beacon interval那些被同意交換資料與被交換的對象保持ACTIVE SATAE， 其他人都進入SLEEP STATE。 如圖：STA1與STA2開始交換資料，STA3與STA4進入SLEEP STATE。 思考： STA1、STA2傳完沒有馬上去睡。是否有改進的空間? time Beacon Sleep Active TBIT (Time Between Idle Time) window ATIM DATA /ACK ATIM_ACK ATIM (Announcement TIM) window Jang Ping Sheu 2019/10/282019/10/28

References [1] Andrew S. Tanenbaum , “Computer Network 4/e” , PHPTR [2] 曾煜棋, 潘孟鉉, 林致宇 , “無線網域及個人網路-隨意及感測網路之技 術與應用” , 知城 [3] N. Abramson, “The ALOHA system – another alternative for computer communications” , in proc. Fall Joint Computer Conference. [4] Jung-Hyon Jun, Young-June Choi, and Saewoong Bahk , “Affinity-Based Power Saving MAC Protocol in Ad Hoc Network” , in proc. IEEE PerCom2005 [5] V. Bharghavan, A. Demers, S. Shenker, and L. Zhang, “ MACAW: A media access protocol for wireless LAN's.” in proc. ACM SIGCOMM '94 [6] IEEE Std 802.11-1997 [7] IEEE Std 802.11a-1999 [8] IEEE Std 802.11b-1999 Jang Ping Sheu 2019/10/282019/10/28

Chapter 3 Outline 3.1. 802.11 MAC機制 3.2. 802.11 碰撞議題相關研究 3.2. 802.11 碰撞議題相關研究 3.3. 802.11 節能、省電議題相關研究 3.4. 802.15.4 MAC 3.5. MAC protocols for WSN Jang Ping Sheu 2019/10/282019/10/28

IEEE 802.15.4 MAC Architecture Applications ZigBee Network Channel acquisition • Contention Window IEEE 802.15.4標準訂立了物理層(PHY)和媒介存取層(Medium Access Control, MAC)，ZigBee聯盟在IEEE 802.15.4 標準的基礎上定義了網路層和應用層框架，IEEE 802.15.4標準的媒介存取層(Medium Access Control, MAC)中，負責的部份是頻道取得管理，以及競爭窗口的管理，根據命令的有所不同，再去跟下層的物理層去做溝通。 IEEE 802.15.4 MAC IEEE 802.15.4 PHY Jang Ping Sheu 2019/10/282019/10/28

IEEE 802.15.4 MAC Architecture Applications ZigBee Network Device join and leave Frame routing And so on ZigBee Network ZigBee的網路層負責設備加入和離開網路、訊框安全和訊框路由。另外網路層還負責路由發現和維護、發現一步內鄰居並儲存鄰居相關資訊。有需要存取媒介時，會告知下層的媒介存取層做處理。 IEEE 802.15.4 MAC IEEE 802.15.4 PHY Jang Ping Sheu 2019/10/282019/10/28

IEEE 802.15.4 MAC Network topology FFD vs. RFD Full function device (FFD) Any topology Network coordinator capability Talks to any other device Reduced function device (RFD) Limited to star topology Cannot become a network coordinator Talks only to a FFD Very simple implementation 在IEEE 802.15.4網路中，一個裝置可以是一個簡化功能裝置(Reduced-Functionality Device；RFD)或是一個全功能裝置(Full-Functional Device；FFD)。 全功能裝置可使用於任何網路拓撲，它可能與任何其他裝置通訊，並可成為網路協調者(PAN Coordinator)； 簡化功能裝置不能成為網路協調者，且通常僅和一個全功能裝置通訊，但是簡化功能裝置在實作上很簡單且價格較便宜。 通訊於同一實體層頻道中的一個個人操作空間(Personal Operating Space；POS)內的兩個或是兩個以上的裝置會構成一個無線個人區域網路(Wireless Personal Area Network；WPAN)，但是一個網路中必須包含至少一個全功能裝置以作為個人區域網路之協調者。 IEEE 802.15.4標準協定的目的為提供可靠和安全的傳輸，提出三種網路架構，即星狀(Star topology)、同儕式(Peer-Peer topology) 網路架構。一個協調者(coodinator)負責初始、維持、及控制網路。 Jang Ping Sheu 2019/10/282019/10/28

doc.: IEEE 802.15-<doc#> IEEE 802.15.4 MAC - Star Topology <month year> PAN Coordinator Master/Slave FFD RFD Communications flow Jang Ping Sheu 2019/10/282019/10/28 <author>, <company>

doc.: IEEE 802.15-<doc#> IEEE 802.15.4 MAC - Tree and Mesh Topologies <month year> PAN Coordinators Cluster tree Point to point FFD RFD Communications flow Jang Ping Sheu 2019/10/282019/10/28 <author>, <company>

Transfer mode – Superframe Structure CAP CFP GTS Active portion Inactive portion Beacon interval 在IEEE 802.15.4的規範中，Superframe的格式是由網路的協調者來定義的。 Superframe的時間長短就是為協調者所發出的Beacon時間間隔(Beacon interval)，一個Superframe可以再細分為活動區間(Active portion)跟閒置區間(Inactive portion)，而活動區間又可以再細分為16個小的相同大小的時槽，並且這16個時槽又可以分為競爭區間(Contention-Access Period；CAP)以及免競爭區間(Contention-Free Period；CFP)， 協調者只在活動區間和個人區域網路中的裝置互相收送資料，而在閒置區間則可以進入省電模式以減少電源消耗。 對於協調者以外的裝置來說，它們在沒有資料要傳送時可以進入省電模式。 Beacon訊框在第一個時槽傳送，Beacon訊框的目的有裝置同步、宣告PAN的存在、通知網路中的其他節點告知有暫存的封包存於網路協調者以及告知superframe的結構。 當任何裝置欲在競爭區間跟協調者溝通必須使用時槽型之CSMA/CA的機制來爭取傳送的機會。 Superframe的結構由Beacon訊框中包含的資訊來決定，Beacon Order(BO)決定Beacon發送的間隔，而Superframe Order(SO)則決定活動區間的長短，SO及BO的值皆為0到14之間的整數，且SO≦BO。 活動區的長度被設定為: aBaseSuperframeDuration × 2SO symbols aBaseSuperframeDuration為IEEE 802.15.4預設參數。而一個Superframe的長度為: aBaseSuperframeDuration × 2BO symbols 當SO=15時，代表不使用superframe的架構。如果裝置有要求要使用固定時槽傳輸資料並且亦通過協調者的同意，在Beacon訊框裡亦會告知裝置他們可以使用的固定時槽。然而如果網路協調者不希望使用Superframe也可以不傳送Beacon訊框，此時網路中的裝置將會使用非時槽型的CSMA/CA機制來爭取傳送機會。 Beacon frame CAP︰ Contention-Access Period CFP︰ Contention-Free Period GTS︰ Guaranteed Time Slot Beacon frame sent from coordinator Jang Ping Sheu 2019/10/282019/10/28

Transfer mode – GTS Concepts Beacon interval = aBaseSuperframeDuration × 2SO symbols aBaseSuperframeDuration為IEEE 802.15.4預設參數。 Active portion的長度為: aBaseSuperframeDuration × 2BO symbols (BO≦SO≦14) 當SO =15時，代表不使用superframe的架構。 A Guaranteed Time Slot (GTS) allows a device to operate on the channel within a portion of the superframe A GTS shall only be allocated by the PAN coordinator The PAN coordinator can allocated up to seven GTSs at the same time 如果裝置有要求要使用固定時槽傳輸資料並且亦通過協調者的同意，在Beacon訊框裡亦會告知裝置他們可以使用的固定時槽。 如果有些應用必須要保障較低的延遲時間或是要求固定的傳輸速率，網路協調者亦可以給予一個固定時槽(Guarantee Time Slot；GTS)供這些應用程式使用。 免競爭區間是由數個GTSs組成，一個網路協調者最多可以分派七個固定時槽，而每個固定時槽的大小可以是數個時間槽。 一個裝置若已經被分配倒固定時槽，也依然可以在競爭區間中活動。 Jang Ping Sheu 2019/10/282019/10/28

Transfer mode – GTS Allocation If and only if PAN coordinator has enough capacity for the requested GTS GTSs shall be allocated on a first-come-first- served basis by the PAN coordinator Coordinator MAC Device MAC GTS request ACK Beacon(with GTS descriptor) 裝置如果想要使用GTS則跟協調者發送GTS請求，協調者會去根據CAP的長度和請求的GTS長度判斷是否有足夠的容量，如果可用就以先到先服務(first-in-first-served)的方式分配GTS。 Jang Ping Sheu 2019/10/282019/10/28

Transfer mode – GTS deallocation PAN coordinator shall update the final CAP slot subfield of the superframe Coordinator MAC ACK Beacon(with GTS descriptor) 設備不再使用GTS後，就發送撤銷GTS命令給協調者，協調者收到撤銷GTS命令後，就比照撤銷GTS命令中的特徵與現有的GTS特徵相符合，如果沒有相符的GTS，則忽略此命令，如果有，則撤銷此GTS，而Superframe中的CAP長度增加，所以協調者也要相對應的更新信標訊框，在下一個欲發送的信標訊框中更新新的GTS描述子給整個網路知道。 Device MAC GTS release Jang Ping Sheu 2019/10/282019/10/28

Transfer mode – GTS reallocation The deallocation of a GTS may result in the superframe becoming fragmented. CAP CFP GTS1 GTS2 GTS3 撤銷一個GTS可能導致superframe變成零散的碎片，首先有3個分配的GTS，當第2個GTS被撤銷，此時GTS1跟GTS3中間就有一段不能利用的空間，這時協調者就必需移動GTS1，以增加CAP的長度。 8 10 13 Jang Ping Sheu 2019/10/282019/10/28

Transfer mode – GTS reallocation CAP CFP GTS1 GTS3 11 13 Maximize CAP Jang Ping Sheu 2019/10/282019/10/28

Data Transfer Model - Channel Access Beacon-enable networks With beacon frame Slotted CSMA/CA channel access mechanism Non Beacon-enable networks No beacon frame Unslotted CSMA/CA channel access mechanism Jang Ping Sheu 2019/10/282019/10/28

Beacon-enable Networks Slotted CSMA/CA Algorithm Every device in the PAN shall be aligned with the superframe slot 使用Beacon-enable網路裡之時槽型CSMA/CA機制時，當裝置們收到網路協調者所發出的Beacon後，他們會將退後時槽(backoff slot)對準Beacon發出的時間。 在競爭區間中每當一個裝置有資料訊框要傳送時，它必須先等到下一個時槽的起始邊界，然後等待隨機產生的若干個退後時槽時間，當等待的時間結束後，如果這時候頻道是忙碌的，根據random backoff機制，該裝置必須再次等待另一隨機產生的若干個退後時槽時間；如果這時頻道沒有被使用，則裝置可在下一個退後時槽的起始邊界開始傳送資料訊框。 Jang Ping Sheu 2019/10/282019/10/28

Slotted CSMA/CA Algorithm Delay for random(2BE-1) unit backoff period NB=0, CW=2 Perform CCA on backoff period boundary BE = macMinBE Y Channel idle? N Locate backoff Period boundary CW=2, NB=NB+1 BE = min(BE+1, macMaxBE) CW=CW - 1 NB > macMaxCSMABackoffs? N N CW=0? CCA: Clear Channel Assessment Y Y Failure Jang Ping Sheu Success 2019/10/282019/10/28

Slotted CSMA/CA Algorithm Random Backoff BC (Backoff Counter) = random(2BE-1) periods BE：the backoff exponent which is related to how many backoff periods NB︰number of backoff (periods) Channel busy → NB=NB+1，BE=min(BE+1,aMaxBE) Beacon NB=1 BE=BE+1CW=2 Beacon if NB > macMaxCSMABackoffs then failure (NB > macMaxCSMABackoffs it means that the channel is very busy and not suitable to transmit) NB=0 BC=3 STA1 此為CSMA/CA演算法每個設備在每次嘗試傳輸時都需要維護的三個變數︰NB、CW和BE。 變數NB是嘗試當前訊框(Frame)發送過程中CSMA/CA演算法執行random backoff的次數，在每個新的傳輸嘗試之前NB應初始化為0。 變數BE是backoff 指數，設備試圖評估通道前backoff的時間與BE有關。 變數CW是Contention Window的長度，它表示允許發送前要求通道連續空閒的時間，每次發送嘗試之前CW初始化為2，並且每次探測到通道忙碌時也重定為2，變數CW只用於CSMA/CA演算法。 在時槽式的CSMA/CA演算法中， MAC層首先（1）初始化變數NB、CW和BE， 然後（2）對準下一個backoff period的邊界， （3）MAC層隨機延遲隨機個完整backoff period 後， （4）請求物理層執行通道評估(CCA)，backoof period 亂數的取值範圍是0～ 2BE-1。 在時槽式CSMA/CA演算法中，CCA在backoof period 的邊界處開始執行，而在非時槽式的CSMA/CA演算法中，CCA立即開始執行。 如果通道評估為忙碌，則變數NB和BE都加1。 在時槽式的CSMA/CA演算法中還要把變數CW設為2，如果變數NB的值小於或等於屬性 macMaxCSMABackoffs 的值，則演算法跳轉到（3）隨機延遲隨機個完整backoff period 之步驟重新執行，如果變數NB的值大於屬性 macMaxCSMABackoffs 的值，則CSMA/CA演算法結束，通道存取失敗。 在本圖中，以第一個時槽為第0個時槽來說，STA2在第2個時槽欲存取頻道，執行時槽式的CSMA/CA演算法（1）初始化變數NB、CW和BE，（2）對準下一個backoff period的邊界（3）MAC層隨機延遲隨機個完整backoff period，得到的BC值為1，也就是在1個時槽後會執行（4）物理層執行通道評估(CCA)，如果通道評估的結果為閒置，在時槽式CSMA/CA演算法中MAC層要確保在Contention Window （P.60）之後才開始傳輸資料訊框(Frame)。 為了達到這目的，演算法把CW減1並判斷是否為0，如果CW不為0，則演算法跳轉到（4）請求物理層執行通道評估(CCA)之步驟重新執行，如果CW等於0，則MAC層在下一個backoff period 的邊界處開始發送資料訊框(Data frame)。 如果在非時槽式的CSMA/CA演算法中通道評估為閒置，則MAC層將立即開始發送資料訊框(Data frame)。 而當第4個時槽時，STA1欲存取頻道，執行時槽式的CSMA/CA演算法（1）初始化變數NB、CW和BE，（2）對準下一個backoff period的邊界（3）MAC層隨機延遲隨機個完整backoff period，得到的BC值為3，代表在3個時槽後會執行（4）物理層執行通道評估(CCA)，但這時STA2正在存取頻道，故通道評估(CCA)的結果為忙碌，則變數NB和BE都加1。並保證BE不超過常量aMaxBE之後重新執行（3）MAC層隨機延遲隨機個完整backoff period 。 CW=1 BC=1 CW=0 STA2 Inactive portion Jang Ping Sheu 2019/10/282019/10/28

Slotted CSMA/CA Algorithm Random Backoff CW： the number of backoff slots that needs to be clear of channel activity before transmission can commence. Channel idle → CW=CW-1 CW = 0 → transmission CW=1 Beacon BC=6 Beacon CW=0 STA1 如果通道評估的結果為閒置，在時槽式CSMA/CA演算法中MAC層要確保在Contention Window 之後才開始傳輸資料訊框(Frame)。 為了達到這目的，演算法把CW減1並判斷是否為0，如果CW不為0，則演算法跳轉到（4）請求物理層執行通道評估(CCA)之步驟重新執行，如果CW等於0，則MAC層在下一個backoff period 的邊界處開始發送資料訊框(Data frame)。 如果在非時槽式的CSMA/CA演算法中通道評估為閒置，則MAC層將立即開始發送資料訊框(Data frame)。 IFS:MAC層需要時間處理來自物理層的資料，所以訊框後面應預留一段空閒時間，IFS的長度與訊框的大小有關，訊框長度不超過aMaxIFSFrameSize時，使用短的IFS(SIFS)，如果訊框長度大於aMaxIFSFrameSize時，使用長的IFS(LIFS)。 CW=1 Inactive portion BC=1 CW=0 STA2 Jang Ping Sheu 2019/10/282019/10/28

Data Transfer Model Data transferred from device to coordinator In a Beacon-enable network, using slotted CSMA/CA to transmit its data. In a non Beacon-enable network, device simply transmits its data using unslotted CSMA/CA Coordinator MAC Beacon frame (slotted CSMA/CA) ACK 當在一Beacon-enable網路中，當裝置要送一筆資料給網路協調者時，須先等待下一個Beacon的到來。在接收到一個Beacon後，裝置會先將自己與這一個Beacon間隔同步，接下來裝置就可以用時槽型CSMA/CA機制競爭媒介使用權，當得到使用權後裝置即可傳輸資料給網路協調者。 而在非Beacon-enable的網路中，當裝置有資料要傳給網路協調者，該裝置只需使用非時槽型CSMA/CA來競爭媒介使用權，當得到使用權後即可馬上傳輸資料給網路協調者。 Device MAC Data Jang Ping Sheu 2019/10/282019/10/28

Data Transfer Model Data transferred from coordinator to device In a Beacon-enable network, the coordinator indicates in the beacon that “data is pending.” Device periodically listens to the beacon and transmits a MAC command request using slotted CSMA/CA if necessary. Coordinator MAC Device MAC Beacon frame Data request ACK 在Beacon-enable的網路中，當網路協調者要送一筆資料給裝置時，網路協調者會在發出去的Beacon裡頭夾帶訊息告知該裝置，當裝置收到Beacon後會先解析Beacon的資訊看網路協調者有沒有資料要送給它，如果有，裝置以時槽型CSMA/CA機制競爭媒介使用權，當得到使用權後裝置發送Data Request訊框給網路協調者，當網路協調者成功收到這一個要求後會先發送一個回覆訊框接著發送欲給裝置的資料。 Jang Ping Sheu 2019/10/282019/10/28

Data Transfer Model Data transferred from coordinator to device In a non Beacon-enable network, a device transmits a MAC command request using unslotted CSMA/CA. If the coordinator has its pending data, the coordinator transmits data frame using unslotted CSMA/CA. Coordinator MAC ACK FP=0 ACK FP=1 FP=Frame Pending Data 而在非Beacon-enable的網路中，裝置必須要定期的詢問協調者有沒有資料要給他，裝置先以非時槽型的CSMA/CA機制競爭媒介權，接著裝置發送一個Data Request訊框給網路協調者來詢問協調者有無暫存資料。當協調者有資料要送給裝置，也使用非時槽式的CSMA/CA演算法來競爭媒介使用權，等競爭到媒介使用權之後，再傳送資料給裝置。 FP=Frame Pending FP=0︰無暫存資料 FP=1︰有暫存資料 Device MAC Data request Data request ACK Jang Ping Sheu 2019/10/282019/10/28

Data Transfer Model – Reliable Transmission (1) Successful data transmission: originator receives acknowledgment in the period of macAckWaitDuration time originator recipient ACK Data macAckWaitDuration timer to expire 成功的資料傳輸︰發送設備發送資料訊框給接收設備之後，在等待確認時，啟動一個計時器，計時時間為macAckWaitDuration，發送設備在期間內收到來自接收設備的確認訊框，就視為一個成功的資料傳輸。 Jang Ping Sheu 2019/10/282019/10/28

Data Transfer Model– Reliable Transmission(2) Lost data frame : recipient does not receive the Data frame and so does not respond with an acknowledgment Data Data originator macAckWaitDuration timer to expire 遺失資料訊框︰發送設備在發送資料送框給接收設備後，開啟一個計時器，計時時間為macAckWaitDuration ，假使接收設備並沒有收到資料訊框，所以接收設備並不會發送確認訊框給發送設備，在計時器時間到達之後，發送設備會重新發送資料訊框給接收設備。這個重傳過程最多可以重複aMaxFrameRetries次，如果傳送次數超過這個次數，則傳送失敗。 recipient Jang Ping Sheu 2019/10/282019/10/28

Data Transfer Model– Reliable Transmission(3) Lost acknowledgment frame : originator does not receive acknowledgment frame and its timer expires. Repeat aMaxFrameRetries times aMaxFrameRetries times before failure … Data Data Data originator macAckWaitDuration timer to expire 遺失確認訊框︰發送設備在發送資料送框給接收設備後，開啟一個計時器，計時時間為macAckWaitDuration ，假使接收設備收到資料訊框且發送確認訊框給發送設備，但是發送設備並沒有收到確認訊框，在計時器時間到達之後，發送設備會重新發送資料訊框給接收設備。這個重傳過程最多可以重複aMaxFrameRetries次，如果傳送次數超過這個次數，則傳送失敗。 recipient ACK Jang Ping Sheu 2019/10/282019/10/28

Chapter 3 Outline 3.1. 802.11 MAC機制 3.2. 802.11 碰撞議題相關研究 3.2. 802.11 碰撞議題相關研究 3.3. 802.11 節能、省電議題相關研究 3.4. 802.15.4 MAC 3.5. MAC protocols for WSNs Jang Ping Sheu 2019/10/282019/10/28

Main Issues of WSN Lower the device's duty-cycles is a difficult problem. duty-cycles: work period occupy proportion entire cycle Properties of a well-defined MAC protocol for WSN Main issues: Energy-efficient, scalability, and adaptability Secondary issues : latency, throughput, and bandwidth utilization, etc. Adaptability: robustness against frequent topology changes 在感測網路的環境中，該如何節省裝置的電量消耗是一個當重要的問題，在IEEE 802.15.4 標準中亦定義了省電的機制。 其中最重要的概念是降低裝置的工作週期(Duty cycle)，使得每個裝置都能夠盡量的減少運作的時間，並進入休眠模式， 由於IEEE 802.15.4 標準電池最佳化網路參數的作法(Beacon 間隔、工作週期可降低、固定的時槽等)，所以電池的壽命能夠大幅提昇至數月或數年， 而進入休眠模式中則會有延遲訊息的問題，對於整體網路的效能會帶來極大的影響，因此是否進入休眠模式以及進入休眠模式時間的長短主要就取決於使用者所需的應用及環境而定。 Jang Ping Sheu 2019/10/282019/10/28

Energy Problems on the MAC Layer Collision Overhearing Control-packet overhead The major problem is “idle listening” 能源浪費的原因歸咎有以下幾種議題：封包的碰撞造成資料傳送的失敗、接收到太多不是自己的封包、控制建立整個拓樸的封包負擔、保證不在節點尚未準備好的情況下送封包以及最重要的是避免沒事做的時間太長。 IEEE 802.15.4 標準運用CSMA的另一個版本，時槽式的CAMA/CA來解決封包碰撞、保證接收者準備好接收資料以及利用網路協調者的特性，節省建立整個網路拓樸的封包負擔。而又另外訂定了一個Superframe structure，能夠有效的規定網路的所有人進入休眠的時間及同步時槽。 Jang Ping Sheu 2019/10/282019/10/28

802.15.4適用於感測網路之特性 Comparison Between WPAN standard 802.15.4 802.11b 802.15.1 Application Focus Monitoring & Control Web, Email, Video Cable Replacement Battery Life(days) 100-1000+ 0.5-5 1-7 Network Size > 1000 < 100 < 10 Bandwidth (KB/s) 250 11,000+ 720+ Success Metrics Reliability, Power Speed, Flexibility Cost, Convenience IEEE 802.15.4標準跟其他標準格式的差別在於，著重的點不太一樣，IEEE 802.15.4 標準是著重在監測以及控制，跟IEEE 802.11b 標準著重在Web，E-mail，Video不同。 IEEE 802.15.4 標準以前面所提到感測網路的省電議題來說，降低裝置的工作週期(Duty cycle)，並且採用電池最佳化網路參數的作法(Beacon 間隔、工作週期可降低、固定的時槽)等，避免了先前所提到的能源浪費的原因，故電池的壽命可以來到數月甚至數年，IEEE 802.15.1 標準(Bluetooth) 約為一至七天。 在網路的尺寸方面，IEEE 802.15.4 標準可容納的網路尺寸可到達2的6次方個節點或更多，因為利用同儕式(Peer-Peer topology) 可不斷再接裝置至網路上，所以幾乎是沒有限制，而IEEE 802.11b 標準最多可到達32個節點。 而在通訊範圍方面，IEEE 802.15.4 標準最高可到達100公尺以上，而IEEE 802.11b 標準最多可到達100公尺。在頻寬方面，IEEE 802.11b的傳輸速率可到達11000KB/s以上，IEEE 802.15.4 標準的實體層通訊協定中有三個不同的頻率操作頻帶，分別為868MHz、915MHz以及2.4GHz，其中868MHz可提供20kbps的傳輸速率，915MHz可提供40kbps的傳輸速率，2.4GHz可提供250kbps的傳輸速率的傳輸速率。 綜觀來說，IEEE 802.15.4 標準成功增進了可靠度、降低了電量的消耗，IEEE 802.11 標準達到了速度的要求，以及使用上的彈性，IEEE 802.15.1 標準達到了建立網路的代價低，使用便利的特性。 Jang Ping Sheu 2019/10/282019/10/28

MAC Protocols for WSN Asynchronous MAC protocols No synchronization or coordinate schedule between neighbor nodes S-MAC, T-MAC, B-MAC, Wise MAC, etc. Synchronous MAC protocols Time synchronization is achieved externally or synchronization is managed by specific node TRAMA, DMAC, LEACH, etc. 非時間同步的mac，是使用網路中自行決定的internal time， 網路中sensor node藉由和鄰居交換醒睡時間而決定醒睡週期， 而不是透過外部的sink集中式的決定整個網路或是部份網路的醒睡時間 在時間同步的mac中， 指的是網路中的sensor需要透過外部的精確時間同步，或是有需要達到整個網路global同步的情況 Jang Ping Sheu 2019/10/282019/10/28

S-MAC S-MAC assume sensor networks to be composed of many small nodes deployed in an ad hoc fashion. The large number of nodes can also take advantage of short-range, multi-hop communication to conserve energy. Most communication will be between nodes as peers, rather than to a single base-station. 感測網路大部分都是使用ac hoc的方式進行傳輸， 考慮到感測器有電量的使用限制 使用multi hop的短距離傳輸方法，會比一次使用大量電力1 hop傳輸至sink的方案省電， 因此大部分的通訊都是介於node到node之間的通訊， 而考慮到網路的佈點方式是隨機的， 所以在設計傳輸protocol時，網路中的node需要有self-configure的能力 Jang Ping Sheu 2019/10/282019/10/28 66

S-MAC S-MAC designed for reduce energy consumption and support self-configuration To reduce energy consumption in listening to an idle channel, nodes periodically sleep Neighboring nodes form virtual clusters to auto- synchronize on sleep schedules S-MAC applies message passing to reduce contention latency for sensor-network applications 每個node在網路中都會有大半部份的時間是inactive的狀態，一個node真正active的時間大多是非常短暫的； 因此s-mac為了達到energy conservation和self-configuration兩個目標，提出了三種方法去減少電源消耗和idle listening問題， 第一個是使用periodically sleep方法減少idle listening和電源消耗 第二個是使用virtual clusters去自動同步每個鄰居間的醒睡排程 第三個是使用message passing減少contention latency (主要使用store-and forward Processing，就如同DATA在網路中傳輸) Jang Ping Sheu 2019/10/282019/10/28 67

S-MAC Locally managed synchronizations periodic sleep– listen schedules Virtual cluster time Sleep Active Listen sleep 為了省電，S-MAC中的sensor node，依照定義好的cycle時段，規律的進行醒睡狀態切換； 在Listen period中，sensors將會進入active模式， 聽取無線頻道上是否有節點對自己發出傳輸資料的request， 有資料需要傳輸的節點也會在此時段中對receiver發出傳輸需求； 而沒有資料傳輸需求得node，將會在sleep period進入休眠模式以節省電量消耗。 S-MAC protocol 為了讓感測節點能夠正確的在鄰居的listen period中醒來， 使用virtual cluster的方式決定local的醒睡schedule。一個新加入網路的sensor node a， 將會先聽取網路一段時間，如果一段時間內沒有收到其他node傳來的schedule資訊時， a將會自己決定醒睡schedule，並且把自己的schedule廣播出去給周圍的鄰居； 如果a在等待時間結束前，收到來自鄰居的醒睡schedule時，a將會依照收到封包的醒睡schedule運作； 如果一個sensor接收到兩個來自不同node的醒睡週期時， 該sensor將要在兩個不同週期的listen period中醒來，因此在cluster交界處的node， 經常需要同時在兩個cluster的listen period中醒來，會有比較高的idle listening和overhearing問題。 A C B D Cluster 1 Cluster 2 Jang Ping Sheu 2019/10/282019/10/28

S-MAC Every node should wakeup in Listen period Synchronization period Control period (RTS/CTS) ※ Node use CSMA before sending any packet Sending data / sleep period Listen period CS : carrier sense TX : transmit RX : receive S-MAC在送出封包前，會採用CSMA機制，確定頻道上沒有正在傳送資料的人後才開始送封包， Sender node在synchronization period時間中，S-MAC利用廣播方式送出sync，告訴附近的鄰居自己的schedule， 收到sync封包的node若是尚未廣播自己的schedule，則和sync封包中的時間同步 事實上，第一個發出同步封包 的人，所有人就會和他同步 Sender node在control period 中用unicast模式送出RTS封包，並等待receiver送回CTS封包，上述步驟成功後進入傳送資料的模式； TX sync TX RTS RX CTS TX data Sender CS CS TX CTS RX data Receiver CS RX RTS Jang Ping Sheu 2019/10/282019/10/28 69

S-MAC Re-transmit message problem Long message => re-transmission will take a long time Short message => large control overhead (RTS/CTS) message passing 1 2 3 4 5 3 Sender message passing的主要功能是減少contention的latency。 在網路中，進行資料處理或是進行aggregation前，一定要保證封包內容的正確性， message passing的目標就是減少錯誤封包重傳時的overhead。 網路中傳輸長封包時，一旦出現幾個bits錯誤就必須浪費許多時間重傳整個封包， 但是分割成數個短封包時，感測網路環境下又會出現RTS和CTS的control overhead； 在S-MAC的message passing中，每個大封包雖然被切割成小段落， 但是這些獨立的小封包將會被「一次」傳輸出去， 也就是說，只使用一次RTS和CTS就連續傳輸數個小封包； 接著receiver透過類似Store and Forward的概念，即時的檢查接收到的封包， 並且在最後的ACK中，要求sender重傳錯誤的封包； receiver周圍的鄰居聽到receiver送出重傳需求的ACK時，將會多等待一段時間， 等sender re-transmit資料後在開始進行傳輸， 藉此減少re-transmit時造成的contention latency，增加網路的效能。 Receiver Re-transmit 3 ok Neighbor of receiver sleep sleep RTS CTS Transmit data ACK 2019/10/282019/10/28

S-MAC Adaptive-Listening Node who overhears its neighbor’s transmissions (ideally only RTS or CTS) wake up for a short period of time at the end of the data transmission. If the node is the next-hop node => remain active after data transmission, prepare to forwarding its neighbor’s message. If the node does not receive anything during the adaptive listening => go back to sleep. adaptive listening技術靠著overhear周圍鄰居的傳輸資訊（RTS/CTS）， 能夠得知接下來自己是否有forward資訊的必要， 再判斷是否需要延遲進入睡眠模式； S-MAC使用adaptive listening模式時， 除了sender和receiver之外，其他位於routing path上的nodes， 可以overhear到receiver送出的ACK或是CTS，如果得知自己位於傳出訊息的routing path上時， Node將維持active的狀態，幫助上個hop的node forward資訊； 如果node在adaptive listening沒有聽到任何訊息的forward需求，則會進入sleep模式。 因此，當網路中的sensors可以overhear 1 hop的鄰居訊息時， 表示同一個cycle period中，資料能向sink forward 2 hops； 但資料需要forward到3 hop外時，傳輸延遲問題仍然存在。 Jang Ping Sheu 2019/10/282019/10/28

S-MAC-Summary Locally time synchronization between neighbors Power saving method: Fixed wakeup/sleep interval Transmit Characteristic: Contention transmission through CSMA 72 Jang Ping Sheu 2019/10/282019/10/28

S-MAC-Summary Advantage Disadvantage Idle listening is reduced by sleep schedules Time synchronization overhead may be prevented by sleep schedule announcements Disadvantage Adaptive listening incurs overhearing or idle listening Sleep and listen periods are predefined and constant 雖然S-MAC提供sleep mode，可減少平時idle listening的問題， 但是S-MAC的醒睡時間比例是事先定義的，無法依照每次傳輸資料的需求即時調整， 分配太多給listening會造成overhearing的問題，反之則可能造成傳送接收的時間不足， S-MAC最欠缺的就是依照通訊量，彈性調整醒睡時間的機制 73 Jang Ping Sheu 2019/10/282019/10/28 73

Timeout T-MAC To improve the idle listening problem of the fixed duty cycle solution, such like S-MAC T-MAC protocol is to reduce idle listening by transmitting all messages in bursts of variable length, and sleeping between bursts An adaptive duty cycle in a novel way: by dynamically ending the active part of it ※T-MAC protocol的運作環境假設和S-MAC很接近，在此不贅述 T-MAC主要設計的目的是為了減少能量消耗， 比較嚴重的能量消耗問題分別是collisions、protocol overhead和overhearing問題 74 Jang Ping Sheu 2019/10/282019/10/28 74

Timeout T-MAC Improvement of S-MAC T-MAC have variable “Listen Period” The listen period ends when no activation event has occurred for a time threshold TA Cycle period Cycle period Cycle period Listen sleep Listen sleep sleep Listen TA TA TA time T-MAC主要是因應S-MAC無法彈性調整醒睡時間的問題進行改良， 當listening period中，node有一段時間沒有傳送接收資料後， T-MAC的listen period就會提早進入sleep period； 進入sleep period的門檻是1.5（time of contention_period + time of RTS + time from end of RTS to beginning of CTS ) 其中time of contention_interval 的定義如下： RTS transmission in T-MAC starts by waiting and listening for a random time within a fixed contention interval. This interval is tuned for maximum load. 一般在RTS封包送出前都會等待一段 fixed 時間， 而此contention_interval 是這段fixed時間在「最大網路流量」時的長度 RTS CTS Transmit data / ACK 75 Jang Ping Sheu 2019/10/282019/10/28 75

Timeout T-MAC TA = 1.5 (Tcontention interval + TRTS + TRTS2CTS) Jang Ping Sheu 2019/10/282019/10/28

Timeout T-MAC The data forwarding problem Early sleeping problem, Consider the case that A sends data to D Node A Node B Node C Node D TA Sleep awake 由於node D沒有收到來自A的RTS或是B的CTS， 不知道有資料是要給自己的， 因此在TA後提早進入睡眠， 這裡發生的問題叫做Early sleeping problem， 會造成資料要等到下個time slot，node D醒來後才能送達 When node D go sleeping before C forward data, the data transmission process may delay to next cycle. RTS CTS Transmit data / ACK 77 Jang Ping Sheu 2019/10/282019/10/28

Timeout T-MAC Solution of early sleeping problem Future request-to-send (FRTS) Forwarding node uses FRTS awake next hop node and destination node Node A Node B Node C Node D awake Sleep TA 為了解決Early sleeping problem 問題，forwarding node在overhear別人的CTS時， 如果發現自己是forwarding node，將會立刻透過FRTS通知之後需要接收封包的成員 因此所有forwarding node在知道需要forward資料給下個node時， 必須利用FRTS在TA時間內通知next hop的node或是destination，避免routing path上的成員進入休眠， 因此在routing path上的成員，不能在閒置TA時間後 直接進入sleep狀態。 整理核心概念：node在overhearing其他request時，需要判斷自己是否是forwarding的成員， 若自己不是forwarding的成員，才能在等待TA時間沒收到其他封包後，提早進入sleep的狀態 About Data-Send packet ： 投影片中，node C收到node B送到的CTS後，為了避免Early sleeping problem ，將緊接著送出FRTS告訴其他需要forward的node， 為了避免資料封包和其他node發出的FRTS發生collision， Node A在node B送出CTS後應該要間隔一小段時間後在送出資料封包， 但是Node A又擔心這段間隔時間內，會被別的node搶走資料傳送權， 因此Node A將在這段時間內送出Data-Send packet， 此封包的長度和FRTS完全相同，且封包內的資訊完全無用， Data-Send packet若是和node C的FRTS於node B發生collision時“遺失”，也完全沒關係，因為不是真正的資料封包 送出DS封包後，A才會緊接著送出真正的DATA packet RTS CTS Transmit data / ACK FRTS Data-Send packet, avoid collision 78 Jang Ping Sheu 2019/10/282019/10/28

Timeout T-MAC Taking priority on full buffers When a node’s transmit/routing buffers are almost full, it may prefer sending to receiving Node A Node B Node C Node D TA Buffer Full TMAC為了避免node因為buffer已裝滿，而必須要丟棄尚未傳輸的資料的情況發生， 設定了full-buffer priority方法，讓buffer已滿的node可以把自己buffer內的資料傳送出去。 當網路中的node B的buffer裝滿時，又收到來自其他node A的要求傳輸資料的RTS， 該node B將暫時不會回傳CTS給node A，而是先送出RTS給自己要傳送資料的對象node C， 將自己buffer內的資料先行傳輸出去後，再準備重新接受來自node A的資料。 RTS CTS Transmit data / ACK Jang Ping Sheu 2019/10/282019/10/28

Timeout T-MAC-Summary Locally time synchronization between neighbors Power saving method： Dynamic wakeup/sleep interval Transmit Characteristic： Contention transmission through CSMA 80 Jang Ping Sheu 2019/10/282019/10/28

Timeout T-MAC Advantage Disadvantage Enhance the poor results of the S-MAC protocol under variable traffic loads Disadvantage Early sleeping problem Higher latency than S-MAC 雖然T-MAC可以減少S-MAC中的idle listening的問題， 但是T-MAC機制也有問題存在， 因為Timeout後就關閉通訊可能造成其他node無法送達封包， 這個問題稱作Early sleeping problem，會造成T-MAC的傳輸延遲時間高於S-MAC。 81 Jang Ping Sheu 2019/10/282019/10/28 81

B-MAC B-MAC Goals： Low Power operation Effective collision avoidance Simple implementation Small code size and RAM usage Efficient channel utilization at low & high data rates Scalable to large numbers of nodes … B-MAC employs an adaptive preamble sampling scheme to reduce duty cycle and minimize idle listening B-MAC專注於處理link protocol問題， 並不像是S-MAC之類的演算法有處理organization, synchronization,和routing built的問題 B-MAC is a link protocol ,its services include, but are not limited to, target tracking, localization, triggered event reporting, and multi-hop routing B-MAC的目標是在節點間建立一個低耗能且可靠的傳輸方法 為了達成可靠的傳輸，B-MAC使用了Clear Channel Assessment (CCA)避免collision的發生，CCA演算法可以判斷channel是否適合傳輸資料 為了讓達成低耗能的目標，B-MAC使用了low power listening (LPL)演算法讓sender能夠在需要傳輸資料時，能確實通知receiver 82 Jang Ping Sheu 2019/10/282019/10/28 82

B-MAC Low power listening (LPL) Goal: minimize listen cost Nodes periodically wakeup at every cycle check if preamble signals If signal is detected, node powers up in order to receive the packet Sender use long preamble to notify receiver Sender and receiver turn off radios after data receive or time- out B-MAC主要由兩大方法構成：Clear channel assignment (CCA)、Low power listening (LPL)。 其中LPL是主要的傳收機制，而CCA則是檢查頻道中noise level的程序， B-MAC中，每個node可以自己決定本身的醒睡週期， 並且不需要將此週期廣播給鄰居。 為了讓sender和receiver可以同步， LPL機制中，每個node需要定期短暫的醒來進入接收模式， 聽取頻道上是否有其他node發出傳送資料的request (preamble)； 由於sender不知道receiver會在何時醒來接收資料， 因此sender的preamble會連續的發出一段時間，這段時間必須保證比receiver的醒睡週期更長， 以保證receiver能夠聽到此preamble， Receiver聽到此preamble後會進入listen模式，當sender送完preamble後進入資料收送模式； Sender和receiver結束資料收送後會再度進入週期的醒睡模式 83 Jang Ping Sheu 2019/10/282019/10/28 83

Low Power Listening: Preamble Sampling Preamble is not a packet but a physical layer RF pulse Minimize overhead Sender Receiver Preamble Send data Preamble sampling Active to receive a message S R |Preamble| ≥ Sampling period Jang Ping Sheu 2019/10/282019/10/28

B-MAC Clear channel assessment (CCA) CCA effectiveness for a typical wireless channel CCA is used to determine the state of the medium 在B-MAC中， 使用了一種Clear channel assignment （CCA）演算法，判斷頻道是否適合傳輸資料 CCA是專門用在wireless的環境中運作演算法， 在上圖中，最上面的signal是無線感測節點接收到的RSSI訊號強度， 每個packet抵達時間都介於22到54ms之間； 在中間的Threshold圖中，是透過CCA演算法計算出的輸出結果， 而最下面的Outlier是最終的輸出結果，0代表channel正有節點傳輸資料中， 而1代表channel可以傳輸資料 CCA演算法不只是用在傳輸資料前偵測通訊頻道是否可使用， 如之前段落所述，Low power listening (LPL)中規定，每個感測器需要定期醒來聽取頻道上是否有傳輸請求， Clear channel assignment (CCA)就是用來判斷頻道中是否有activity訊號出現， 若是頻道中能探測到activity，感測器將維持awake狀態，等待資料傳輸。 0=busy, 1=clear, Packet arrives between 22 and 54 ms Jang Ping Sheu 2019/10/282019/10/28

B-MAC Check if any preamble signal Clear channel assessment (CCA) Before transmit, adapts to noise floor by sampling channel when it is assumed to be free Sender arrive TX preamble TX data sender c B-mac的sensor自行決定省睡時間， 這會造成：sender有資料要傳輸時，receiver可能還在休眠狀態， 因此sender會連續的發出一長段的preamble，以確保可以通知到receiver ※Preamble is not a packet but a physical layer RF pulse 在本頁的圖例中，每顆sensor都會週期的醒來一小段很短的時間， 聽取頻道上是否有sender要送資料給自己，(圖中使用Listen表示sensor醒來聽取頻道的時間點) 而sender決定要傳送資料後，會先使用Clear channel assignment (CCA)聽取一下頻道中是否有人正在傳送資料， CCA技術可以聽取頻道上的noise，並且從雜亂的載波中，分辨頻道是否可以傳輸資料， 若判斷頻道是空的，sender將會連續送出一長段時間的preamble通知receiver 圖中的receiver在前兩次Listen中，並沒有聽到任何sensor傳給自己的preamble，因此在短暫的醒來後，又進入睡眠 而第三次receiver醒來時，正好收到來自sender的preamble，因此receiver開始進入等待狀態， 等sender的preamble結束後，receiver和sender才開始進入資料的收送狀態 Listen Listen RX preamble RX data receiver Wait data cycle cycle cycle 86 Jang Ping Sheu 2019/10/282019/10/28

B-MAC- Summary B-MAC is a non-time-synchronization method, it uses a long enough preamble to notify the receiver. Power saving method: Self-defined wakeup/sleep interval Long preamble notification Transmit Characteristic: Contention method through Clear Channel Assessment algorithm B-MAC的重要特點 1. 每個節點可以自己決定醒睡時間，不需要和周圍的鄰居同步 2. sender要傳輸資料時，在頻道上連續的發出preamble，確保此preamble能夠覆蓋到receiver的active時段，確實的將資料傳輸的需求通知receiver 87 Jang Ping Sheu 2019/10/282019/10/28 87

B-MAC- Summary Advantage Disadvantage Doesn’t need any synchronization RTS/CTS (optional) Clean and simple interface Disadvantage Transmission delay will be long Bad performance when heavy traffic load B-MAC利用足夠長度的preamble保證能夠通知receiver資料傳送的request， 同時，long preamble周圍的node將要傳送資料的訊息，因此B-MAC中不使用RTS/CTS 但是不採用CTS的情況可能產生hidden terminal問題， long preamble也會造成相當的transmission delay， 在網路通訊量增大後，會造成效能急速下降 88 Jang Ping Sheu 2019/10/282019/10/28 88

MAC protocols for WSN Asynchronous MAC protocols No synchronization or coordinate schedule between neighbor nodes S-MAC,T-MAC, B-MAC, …etc Synchronous MAC protocols Time synchronization is achieved externally or synchronization is managed by specific node TRAMA, DMAC, …etc 89 Jang Ping Sheu 2019/10/282019/10/28 89

Traffic-Adaptive Medium Access Protocol- TRAMA TRAMA reduces energy consumption by ensuring that unicast and broadcast transmissions incur no collisions TRAMA assumes that time is slotted and divides time into random access periods and schedule-access periods. TRAMA avoids assigning time slots to nodes with no traffic to send TRAMA同樣是專門設計給運用在ad hoc模式下的無線感測網路使用 在感測網路的使用環境中，不但要講求省電，同時也要讓網路能self-organize TRAMA演算法主要的理念是避免collision發生， 並且分散式的規劃出每個節點的傳輸順序。 TRAMA不會給沒有傳輸需求的node安排傳輸時槽， 在演算法中TRAMA使用TDMA的方式安排每個傳送者和接收者的時槽， 且允許讓沒有傳送接收的節點進入省電模式 TRAMA在計算每個節點傳輸順序時，只需要蒐集該節點2 hop範圍內的鄰居資訊， 因此TRAMA能夠符合ad hoc network的使用環境 90 Jang Ping Sheu 2019/10/282019/10/28 90

TRAMA Nodes need globally synchronized Time divided into Random access periods Scheduled access periods Three main protocol Neighbor Protocol (NP) Adaptive Election Algorithm (AEA) Schedule Exchange Protocol (SEP) 在TRAMA中，主要分成Random access periods和Scheduled access periods 並且透過三個核心components：Neighbor Protocol (NP)、Schedule Exchange Protocol (SEP)、Adaptive Election Algorithm (AEA) 在Random access periods中每個node會互相傳送封包進行傳輸schedule同步(SEP)， 並且透過小封包蒐集2-hop內鄰居的資訊(NP)，用此資訊來計算自己和2-hop內鄰居的優先順序(AEA) 在Scheduled access periods中，每個node參照之前計算出來的2-hop鄰居優先順序，依序傳送資料 V. Rajendran, K. Obraczka, and J. J. Garcia-Luna-Aceves, “Energy-Efficient, Collision-Free Medium Access Control for Wireless Sensor Networks,” Proc. ACM SenSys ‘03, Los Angeles, CA, Nov. 2003, pp. 181–92. 91 Jang Ping Sheu 2019/10/282019/10/28 91

Scheduled access period TRAMA cycle Random access period Scheduled access period Send data Nodes exchange schedules Using schedule exchange protocol (SEP) Nodes announce the schedule to its neighbors 在每次的cycle中，都分成Random access period和Scheduled access period 每個node在Random access period蒐集鄰居資訊， 同時決定每個node在接下來的Scheduled access period中傳送資料的順序 由於sensor可能會死掉，因此TRAMA中， 透過Random access period蒐集鄰居資訊和計算node傳輸順序的工作要定期重複執行， 在Random access period中 TRAMA會先採用neighborhood exchange protocol交換兩步鄰居的資料， 其主要是要先確定網路的topology是否有改變， 在neighborhood exchange protocol中，每個node都會傳送自己的資訊，也會接收其他node的資訊， 利用這些交換資訊，nodes會更新週邊的鄰居資訊 schedule exchange protocol中， 每個node都會透過Adaptive Election Algorithm 計算先前neighborhood exchange protocol中蒐集到的兩步鄰居資訊， 規劃出兩步鄰居傳輸使用的時槽， 計算完成後之後，node會將計算出來的結果通知周圍1 hop鄰居， (雖然TRAMA會計算2 hop內node的priority，但真正傳輸的對象只有1 hop內的鄰居，所以TRAMA只會通知1 hop內鄰居) 每個node都會運行Adaptive Election Algorithm 計算出未來k個 time slot中， 2 hop內node的傳輸的priority (priority越高，傳輸的time slot越前面)， AEA演算法在下一頁中會進一步介紹。 ※由於交換鄰居的Random access periods中， 是採用競爭的方式， 因此可能會產生碰撞， 為了確保nodes可以完成交換資訊的任務， Random access periods的時段長度將會隨場景中的平均鄰居數量調整。 在Scheduled access period中， 每個node會依照Random access period內規劃出的傳送優先順序傳送資料 Using Adaptive Election Algorithm (AEA) Compute the priority within two hop neighbors Learning about their two-hop neighborhood Using neighborhood exchange protocol (NP) Update information in randomly selected time slots 92 Jang Ping Sheu 2019/10/282019/10/28

TRAMA Neighborhood Exchange Protocol Schedule Exchange Protocol A node picks randomly a number of time slots and transmits small control packets in these without carrier sensing These packets contain incremental neighbor information, that is only those neighbors that belong to new neighbors or neighbors missing during the last cycle Schedule Exchange Protocol A node transmits its current transmission schedule and also picks up its neighbors’ schedules Jang Ping Sheu 2019/10/282019/10/28

TRAMA Schedule Exchange Protocol Each node compute the length of SCHEDULE_INTERVAL based on the rate at which packets are produced by higher layer application. Nodes use AEA algorithm pre-compute the number of slots in time interval [t, t + SCHEDULE_INTERVAL]. Node select the highest priority slots in the duration of SCHEDULE_INTERVAL as its transmitting slots Node uses its last transmitting slot in this duration, to announce its next schedule by looking ahead the next SCHEDULE_INTERVAL Nodes announce their schedule via schedule packets AEA演算法會蒐集2 hop資訊計算， 因此同區域中，每個node計算自己在任意一個time slot中的優先權時，可以避開其他node的傳送slot， （當別人在該slot中是最高優先權時，自己將不會是最高優先權） Schedule Exchange Protocol中，會先利用AEA演算法計算出一段時間內，屬於自己的傳輸slots，並透過廣播通知周圍鄰居； node a會先依照欲傳輸資料量的多寡，決定好pre-compute的時間長度SCHEDULE_INTERVAL， node a透過AEA計算出自己介於時間[t, t + SCHEDULE_INTERVAL]之間中，每一個time slots的優先權， 而在這段時間中，node a擁有最高優先權的time slots，就會是node a可用來傳輸的time slot； 但是AEA只能計算出一段時間內(有最高優先權)的可傳輸time slots，無法精準的控制time slots的數量， 計算出的可傳輸slots數量可能太多，也可能不足； 因此node a確定需要使用的slot數量後，透過透過bitmap的表示方法，於schedule packets中，將需要使用的slots通知鄰居，多餘的slots將留給其他node使用； 考慮到可能有資料需要繼續傳輸的狀況，node a會在上述規劃的最後一個傳輸slot中，傳送下段週期的傳輸schedule給鄰居 Jang Ping Sheu 2019/10/282019/10/28

TRAMA How Adaptive Election Algorithm (AEA) to decide which slot a node can use in scheduled access period? Use node identifier x Use globally known hash function h For a time slot t, compute priority p = h (x XOR t) Compute this priority for next k time slots for node itself and all two-hop neighbors Node uses those time slots for which it has the highest priority 在TRAMA中，每個node和其2 hop內鄰居的優先權，都透過AEA演算法計算， 如果計算出某一個node對於任意一個time slot的優先權在是最高的， 則這個node將擁有這個time slot的傳送權 透過neighborhood exchange protocol (NP) 蒐集2 hop內鄰居的資訊， 並且透過hash function 去計算自己和2 hop內鄰居在任意time slot中的優先權； 為了要錯開每個slot中傳輸的node， 因此利用node ID和time slot t作XOR， 最後丟入hash function； node ID都是獨立的，而且time slot代號也相當於流水號，有不重複的特性， 此hash function可以計算出任意time slot中，每個node的優先權， 補充： p = h (x XOR t)只計算出要傳送DATA的slot，沒有顧及到接收和sleep的時間安排， AEA演算法為了符合省電的需求，計算時會考慮更細節部份的time slot安排， 因此上述p = h (x XOR t)在演算法中還有近一步修正； 因為是細節，本頁只是大略帶過主要概念，不詳述 95 Jang Ping Sheu 2019/10/282019/10/28 95

TRAMA For example Both A and D could transmit in the timeslot because they have the highest priority in their two hop neighbors 上圖中，如果空間利用恰當，A和D可以同時間送資料給B和C； A D B C Priority 200 Priority 100 Priority 95 Priority 79 Jang Ping Sheu 2019/10/282019/10/28

TRAMA During time slot is 1000 When SCHEDULE_INTERVAL is 100 The node need to compute the transmitting slots between [1000,1100] 1000 1100 SCHEDULE_INTERVAL 1009 1030 1033 1064 1075 1098 time 上方圖中假設某個node a現在正在slot 1000的位置， node a計算出的SCHEDULE_INTERVAL 是100 因此node a會透過AEA計算1000到1100這段時間內自己可用來傳輸的time slots， 而這裡我們假設計算出來node a擁有最高優先權的結果是「1009 ,1030 ,1033 ,1064 ,1075 ,1098」 若node a的資料不多，只需要用到四個time slot傳輸資料時， node a在送給鄰居的資訊中，就只會包含1009 ,1030 ,1033 ,1064 ，而1075會標示放棄，讓其他的node可以使用1075， 但是node a將會留下最後一個slot 1098，用來告知周圍鄰居，下個週期1098到1198的schedule。 Using for transmit data If does not have enough packet to send ,it announces gives up the corresponding slot Node uses the last slot to send its next schedule Jang Ping Sheu 2019/10/282019/10/28

TRAMA Inconsistency problem If B looks at its schedule information and D will transmit data to C, B switch to sleep mode. B will end up missing A’s transmission B A C D Priority 100 Priority 95 Priority 79 Priority 200 Sleep 但是從B的角度來看2 hop的neighbor時，B會選擇讓擁有最高priority的node D送資料， 假設D是要送資料給C的情況下，B將會進入sleep模式；造成A無法送資料給B。 為了解決此問題，運行AEA演算法時， Node B將會把node A這類屬於1 hop內擁有最高priority，且有資料要傳送的node標示為Alternate Winner， 如果Alternate Winner和2 hop內擁有最高優先權的可傳輸者Absolute Winner (node D)可以同時傳輸且不會發生collision， 則同時將Absolute Winner和Alternate Winner設定為傳輸者。 Jang Ping Sheu 2019/10/282019/10/28

TRAMA Solution of Inconsistency Problem Node B will denote node A as Alternate Winner if node A want to transmit data to node B If Alternate Winner and the Absolute Winner (node D) are not interfered for each other then both nodes can transmit concurrently Jang Ping Sheu 2019/10/282019/10/28

TRAMA- Summary Global synchronized time slot Power saving method： Higher percentage of sleep time and less collision probability is achieved compared to CSMA based protocols Transmit Characteristic： Contention-Free TDMA Adaptive Election Algorithm decide transmission TRAMA的特色是採用TDMA方式傳送資料， 在傳統使用TDMA的演算法中，大多需要global的規劃所有node的醒睡時間， 這會造成嚴重的control overhead，同時也會讓網路的適應性降低， TRAMA演算法中只需要應用2 hop的鄰居資訊， 就可以達成TDMA的效果，還能兼顧資料傳送的優先順序， 而且TRAMA由於TDMA安排恰當，nodes可以擁有比傳統CSMA更高的睡眠機會， TDMA傳送方式也能避免collision的發生，讓TRAMA需要retransmission的機會降低，進而減少電量的消耗 TRAMA的TDMA主要以文中所提出的Adaptive Election Algorithm為核心構成， 在接下來的投影片中，我們會提到Adaptive Election Algorithm如何分配time slot給網路中的node 100 Jang Ping Sheu 2019/10/282019/10/28

TRAMA- Summary Advantage Disadvantage Only use two hop neighbor information can decide transmission priority Higher percentage of sleep time, less collision probability and higher maximum throughput than contention-based S- MAC Disadvantage Only using local two hop information, cannot avoid collision over three hops Higher delay problem Substantial memory/CPU requirements for schedule computation TRAMA只需要使用2 hop的資訊就能決定傳輸時槽， 不但不需要花太多電力進行資料蒐集，而且TDMA分配好傳輸時間可以幫助sensor節省競爭和idle listening的電量， 但是考慮到TRAMA只蒐集2 hop的資訊，資料如果需要forwarding到3 hop之外的節點時， 可能會發生time slot衝突到的問題， 屆時不是forwarding node需要cache住資料，就是會發生collision； 較高比例的sleeping機率，雖然能省電，但是也會讓資料傳送的delay時間延長 最後的問題就是在memory和使用電量有限的sensor node中，需要計算hash會造成一定程度的運算overhead 101 Jang Ping Sheu 2019/10/282019/10/28

DMAC DMAC achieves very low latency for convergecast communications DMAC could be summarized as an improved Slotted Aloha algorithm in which slots are assigned to the sets of nodes based on a data gathering tree DMAC also adjusts the duty cycles adaptively according to the traffic load in the network DMAC適合用在廣大範圍蒐集資料的場景中使用， 例如target tracking , habitat sensing或是fire detection； 當資料需要從大範圍部屬的感測網路中回報給sink時， DMAC設計的data gathering tree就能發揮最佳化傳輸和感測器醒睡排程的效果 DMAC的特性之一，是解決資料傳輸中的forwarding delay問題， 以S-MAC來說，當感測網路需要multi hop 傳輸資料回sink時， 遇到下一步的sensor是sleep模式時，需要把資料cache住，等帶下一步sensor進入active模式； 但是在D-MAC的data gathering tree架構下， 傳輸資料順序都能被最佳化，當樹狀結構中某一層的感測器是接收者時， 其child的layer將設定為傳輸者； 當第N層的節點接收完資料後，可以馬上forward給第N+1層的node， 因此可以連續的forward資料，可達到低延遲的效果。 102 Jang Ping Sheu 2019/10/282019/10/28 102

DMAC The data forwarding interruption problem (DFI) Only the next hops of receiver can overhear the data transmission Nodes out of hearing range will sleep until next cycle/interval source sink μ 2μ 3μ data forwarding interruption problem (DFI)是在multi hop傳輸資料時， forwarding node因為無法得知有傳輸資料的任務，而直接進入休眠， 造成傳輸delay； 為了改進DFI問題， Nodes使用了adaptive listening技術， 靠著overhear周圍鄰居的傳輸資訊， 能夠得知自己是否有forward資訊的必要，再判斷是否延遲進入睡眠模式； 但node的overhear距離有限（通常只能overhear 1 hop）， 因此routing path上距離sender 2 hop外的nodes， 無法知道自己需要forwarding資料，仍然進入睡眠模式， 減少DFI問題的成效有限。 在上方圖中，以SMAC為例子，每個node使用adaptive listening模式運作， node要從左方的source node傳送資料到右方的sink node， 而active period的時間長度，只能讓node傳送一個packet到1 hop的鄰居， SMAC使用adaptive listening模式時， 除了sender和receiver之外， 位於routing path上的next hop nodes，可以overhear到receiver送出的ACK或是CTS， 因此在一個時間長度為T cycle period中，資料能向sink forward 2 hops， 但資料需要forward到3 hop外時，傳輸延遲問題仍然存在； 如果提昇overhearing的範圍到多hop之外，雖然能增加時間T內可以forward的hop數量， 但是離sender較遠的node將需要等待一段時間後，才能接收到前方node forward過來的資料， 這段等待時間中，會造成idle listening問題。 4μ T+μ T+2μ T+3μ time Active nodes Sleep nodes In S-MAC, DFI causes sleep delay. Jang Ping Sheu 2019/10/282019/10/28

DMAC Staggered Wakeup Schedule Data gathering from sensor nodes to sink by data gathering tree Nodes on multi-hop path to wake-up sequentially like a chain reaction time node μ 2μ 3μ 4μ source sink 5μ 6μ 7μ receive node send node sleep node sink However, to accommodate the possibility of short range between two neighbor nodes, a node will only send one packet every 5μ in DMAC in order to avoid collision as much as possible. Of course, this may reduce the maximum network capacity by about 20%, but if the traffic load is more than 80% of the maximum channel capacity duty cycled mechanisms would not function efficiently in any case, making this a moot point. DMAC為了提高資料蒐集的效率，提出了Staggered Wakeup Schedule方案 Staggered Wakeup Schedule方案分成三個部份： Local data exchange and aggregation： 靠著clustering 或是simple medium access mechanism去處理資料交換和蒐集的問題 Dispatch of control packets and interest packets from sink： sink會使用小到不至於影響傳輸latency的packet去和sensor nodes溝通 最重要的部份是 Data gathering from sensor nodes to sink by data gathering tree， DMAC為了解決之前出現的DFI問題， 傳送資料的path被建立成tree structure， 每個node傳輸資料至sink的path將會依照此樹狀結構的routing 路徑傳輸； 並且假設此感測網路中的node沒有mobility， 因此該蒐集資料用的樹狀結構不需要經常調整 DMAC採用slotted ALOHA進行傳輸， slot的安排要決定於網路的樹狀結構， 最佳的狀況下，從tree的leaf到root可以排出no-delay的資料傳輸順序 在上方樹狀結構的圖中，每段時間被分成receive、sending、sleep “圖中每往上一層 表示往sink方向傳一個hop” 當n-1層nodes是sending state的時候，第n 層的nodes將會是receive state， 在receive state中： 每個node receive packet，同時回傳一個ACK packet給sender， 在send state中： Node send packet 給下一個hop的node，同時接收對方送來的ACK 而右上方的圖中，每個routing path上的node在要傳輸資料時皆維持active， 因此資料傳輸到sink的路上，不會因為中途有節點正在休眠而delay。 data gathering tree Jang Ping Sheu 2019/10/282019/10/28

DMAC When nodes has multiple packets to send DMAC use slot-by-slot mechanism Piggyback a more data flag in MAC header Node not active at next slot, but schedule a 3μ sleep then goes to receiving state. sleep sink RX TX RX TX More data flag DMAC有大量資料需要multi-hop傳輸時， 會利用Piggyback技術，在傳輸資料時發送more data flag， 告訴receiver有繼續傳輸資料的需求 和T-MAC的FRTS不同的是，使用more data flag準備連續forwarding資料時， nodes不會在傳送完資料後的下一個time slot中維持active， 因為下一個time slot是receiver要向前forward資料的時間，如果連續傳送資料，會造成資料丟失和collision問題， 在「J. Li, C. Blake, D. Couto, H. Lee and R. Morris, “Capacity of Ad HocWireless Networks”, in ACM Mobicom July 2001」中指出， 如果interference range是傳輸距離的兩倍時，maximum utilization of a chain of ad hoc nodes is ¼ 在DMAC中，為了保證距離較短的鄰居間不會發生collision， nodes在繼續傳送資料前，會先睡一段時間，並且在間隔三個 slot後再度醒來繼續收送資料。 上圖中，每一層的nodes在確定有More data flag後，為了避免兩層相鄰的node傳輸資料時發生衝撞 每一層nodes在傳送資料完後會先進入睡眠， 確保上一層forward完資料，且不會造成相鄰兩層間collision後， Node才在睡眠三個slot後，繼續醒來傳送下一個packet； 上述的slot-by-slot傳輸方式，不但可以減少idle listening的問題，同時也可以減少資料傳輸時的delay sleep sleep RX TX RX TX More data flag sleep sleep RX TX RX TX time More data flag sleep sleep RX TX RX TX Jang Ping Sheu 2019/10/282019/10/28

DMAC-Summary Need external time synchronized in prescribe area Power saving method: Sleep schedule of a node an offset that depends upon its depth on the tree Transmit Characteristic: Improved Slotted Aloha algorithm Contention-Free slots are assigned based on a data gathering tree Synchronization is needed in DMAC. However, local synchronization is enough since a node only need to be aware of its neighbors’ schedule. DMAC的nodes需要和自己鄰居的時間同步 而sensor需要擁有外部精確的real time以確保整個data gather tree能夠正常的運作 DMAC中data gathering tree不只是用來決定資料forward的先後順序， 同時也能最佳化node的醒睡週期，每個node可以依照自己所在的層次得知醒睡的週期 106 Jang Ping Sheu 2019/10/282019/10/28 106

DMAC-Summary Advantage: Disadvantage DMAC achieves very good latency compared to other sleep/listen period assignment methods Disadvantage Collision avoidance methods are not utilized, if number of nodes that have the same schedule try to send to the same node, collisions will occur. DMAC傳輸資料的效率很高，因為使用slot-by-slot的傳輸方式，資料forwarding的效率比傳統的CSMA MAC (such like S-MAC)來的快， DMAC蒐集整個網路資訊的所需的時間，只需要d*t就足夠，其中d是樹的depth，t是資料傳送所需的時間 DMAC的最大缺點就是彈性太差，當網路拓樸改變後，每個node必須重建醒睡時間 107 Jang Ping Sheu 2019/10/282019/10/28 107

MAC 特性比較 Comparison of MAC protocols Time sync needed type Adaptive to changes S-MAC/ T-MAC no CSMA Good B-MAC CSMA/CCA WiseMAC np-CSMA TRAMA yes TDMA/CSMA DMAC TDMA/ Slotted Aloha weak LEACH TDMA/CDMA ※上方欄位中的LEACH protocol出現在最後3-7節的homework中 np-CSMA : non-persistent CSMA Adaptive to changes : change是只感測網路中的node位置或數量異動，造成網路拓樸的改變； 此欄位表示出protocol是否有足夠的適應性，可以在網路結構改變時，調整成適合新網路結構的傳輸模式 Time sync needed欄位代表需要外部時間同步或是global的時間同步 108 Jang Ping Sheu 2019/10/282019/10/28 108

References Ilker Demirkol, Cem Ersoy, Fatih Alagöz , “MAC Protocols for Wireless Sensor Networks: A Survey,” Communications Magazine, IEEE , April 2006 Deborah Estrin, John Heidemann, and Wei Ye, “An Energy-Efficient MAC Protocol for Wireless Sensor Networks,”IEEE INFOCOM 2002. W. Ye, J. Heidemann, and D. Estrin, “Medium Access Control with Coordinated Adaptive Sleeping for Wireless Sensor Networks,” IEEE/ACM Trans. Net. 2004 , Koen Langendoen and Tijs van Dam, “An Adaptive Energy-Efficient MAC Protocol for Wireless Sensor Networks,” The First ACM Conference on Embedded Networked Sensor Systems (Sensys＆03), pp. 171--180, 2003 DavidCuller, JasonHill, and JosephPolastre, “Versatile Low Power Media Access for Wireless Sensor Networks,” the 2nd ACM Conference on Embedded Networked Sensor Systems (SenSys), November 3-5, 2004 A. El-Hoiydi, “Spatial TDMA and CSMA with Preamble Sampling for Low Power Ad Hoc Wireless Sensor Networks,” Proc. ISCC 2002 C. C. Enz et al., “WiseNET: An Ultralow-Power Wireless Sensor Network Solution,” IEEE Comp., vol. 37, no. 8, Aug. 2004. V. Rajendran, K. Obraczka, and J. J. Garcia-Luna-Aceves, “Energy-Efficient, Collision-Free Medium Access Control for Wireless Sensor Networks,” Proc. ACM SenSys ‘03, Los Angeles, CA, Nov. 2003, pp. 181–92. W. Rabiner Heinzelman, A. Chandrakasan, and H. Balakrishnan, “Energy-Efficient Communication Protocols for Wireless Microsensor Networks,” Hawaii International Conference on System Sciences (HICSS '00), January 2000. G. Lu, B. Krishnamachari, and C. S. Raghavendra, “An Adaptive Energy-Efficient and Low-Latency MAC for Data Gathering in Wireless Sensor Networks,” Proc. 18th Int’l. Parallel and Distrib. Processing Symp., Apr.2004, p. 224. Holger Karl,Andreas Willig , “Protocols and architectures for wireless sensor networks,” Jang Ping Sheu 2019/10/282019/10/28