Speaker: Chih-Ching Chen Advisor: Dr. Ho-Ting Wu 2015/6/24 無線感測網路中TDMA機制的時槽規劃演算法設計 The Design of TDMA Scheduling Algorithms in Wireless Sensor Networks Speaker: Chih-Ching Chen Advisor: Dr. Ho-Ting Wu 2015/6/24
Outline 介紹 目的 Scheduling Algorithms 模擬測試 結論 參考文獻 Time-Optimal Scheduling Algorithm Node-Based Scheduling Algorithm Level-Based Scheduling Algorithm Top-Down Scheduling Algorithm 模擬測試 結論 參考文獻
介紹 近年來無線感測網路的普及帶動了資訊流傳 的速度，使最新的資訊能夠快速地傳播。 無線感測網路(Wireless Sensor Network, WSN) 主要以一至多個無線資料收集器以及眾多個 無線感測裝置(Sensor)所組成的網路，其中 sensor會生成資料封包並傳送，也可以當作 中繼點負責轉傳資料封包，最後將資料封包 傳送至無線資料收集器。
目的 在WSN裡資料的傳遞有多樣的方式，其中大 多文獻使用TDMA機制進行資料封包的傳送 會比CSMA有效率，原因在於使用CSMA發 生碰撞的頻率較高造成封包傳送失敗以至於 可靠度較低，故使用TDMA進行資料封包的 傳送。 使用TDMA進行封包傳送需要指定sensor在何 時要傳送何時要接收，故我們需要時槽規劃 演算法(Scheduling Algorithm)協助網路上的資 料封包能夠正確的傳送至目的。
目的 (Cont.) 藉由時槽規劃演算法能夠在TDMA機制下將 資料封包傳送至目的，但為了能更迅速的獲 取資訊，故欲設計出一時槽規劃演算法達成 以上要求。
Scheduling Algorithms 考慮在TDMA機制下使用單一通道的時 槽規劃演算法 Time-Optimal Scheduling Algorithm Node-Based Scheduling Algorithm Level-Based Scheduling Algorithm Top-Down Scheduling Algorithm
Time-Optimal scheduling algorithm Time-Optimal scheduling algorithm 以線性網 路作為時槽規劃的基礎，適用於網路上所有 固定位置的裝置皆有一個封包欲傳送至Base Station。 所有裝置皆需要在“active”狀態才能夠傳送封 包，其每個裝置初始狀態受到距離Base Station的hop count而有所不同。 State T: 在此時槽為傳送狀態 State I: 在此時槽為閒置狀態(不接收不傳送) State R: 在此時槽為接收狀態
Time-Optimal scheduling algorithm (Cont.) 當轉為active狀態後，hop count除以3的餘數 為1的裝置狀態為T； hop count除以3的餘數 為2的裝置狀態為I； hop count除以3的餘數 為0的裝置狀態為R。 active狀態持續三個時槽的時間，在這狀態內 的裝置狀態需要遵守下圖的狀態轉換。 R T I Next Slot
Time-Optimal scheduling algorithm – Linear network f e d c b a S #slot I State 1 Num. pkts R T 2 3 4 active
Time-Optimal scheduling algorithm – Multi-line network
Time-Optimal scheduling algorithm – Multi-line network (Cont.) f a b S Branch A Branch B Branch C Branch Slot 1 2 3 4 5 6 7 A State I a3 a2 a1 Num.pkts B C a表示active a3表示hop count由小到大的節點狀態依序為TIRTIRT… a2表示hop count由小到大的節點狀態依序為IRTIRTI… a1表示hop count由小到大的節點狀態依序為RTIRTIR…
Time-Optimal scheduling algorithm – Tree network #slot id 1 1 R I 2 3 8 6 1 2 7 9 8 4 5 3 3 5 4 1 7 R T I R T I R T I 5 3 8 6 5 7 1 7 R T I 8 2 R T I R T I T R I 9 4 9 10 1 6 2 3 1 2 3 1 11 2 12 4 9 R T I T I R 13 6 1 3 2 1 2 3 14 2
Node-based scheduling algorithm Node-based scheduling algorithm 是利用點著 色(vertex coloring)防止鄰近裝置的干擾並進 行時槽規劃。 此演算法的基礎為裝置皆固定位置，每個時 槽選擇一種顏色並且與此同顏色的裝置可以 傳送封包，不會造成封包的碰撞。 顏色依照此顏色裝置的最大degree(鄰近裝置 數量和2hop可到的裝置數量)由大到小排順序。
Node-based scheduling algorithm – Tree network ID Degree 1 8 2 7 3 5 4 3 5 7 6 7 7 3 8 4 9 5 6 1 2 7 9 8 4 5 3
Node-based scheduling algorithm – Tree network (Cont.) ID Degree 1 8 2 7 3 5 4 3 5 7 6 7 7 3 8 4 9 5 Color A B C D E 6 1 2 7 9 8 4 5 3 A B C B C D A B E Color順序: A B C D E
Node-based scheduling algorithm – Tree network (Cont.) 裝置被規劃的順序: 1. 顏色s的裝置 (若此 顏色裝置沒有封包要傳 則換下一個顏色，直到 此顏色的裝置至少有一 個封包要傳) 2. 不在顏色s的裝置若 能不會被鄰近裝置干擾 且能在同個時槽傳送
Node-based scheduling algorithm – Tree network (Cont.) #slot id R 1 1 6 7 6 1 2 7 9 8 4 5 3 2 2 4 8 3 3 5 R T 4 1 9 A B R T T R C 5 1 6 6 2 5 T R T T R 7 3 T B C D A 8 1 9 2 B E T T Color順序: A B C D E
Level-based scheduling algorithm Level-based scheduling algorithm 以到達Base Station有多少hop為基礎劃分裝置在哪一個 level，並且同level的裝置可在同一個時間規 劃傳送封包，但是同level裡的裝置互相干擾 則只能擇一傳送。 劃分為Level後會類似linear network，之後再 進行點著色。
Level-based scheduling algorithm – Tree network 裝置被規劃的順序: 1. 顏色s的裝置， 需要考慮到互相干擾 (若此顏色裝置沒有 封包要傳則換下一個 顏色，直到此顏色的 裝置至少有一個封包 要傳) 2. 不在顏色s的裝 置若能不會被鄰近裝 置干擾且能在同個時 槽傳送
Level-based scheduling algorithm – Tree network (Cont.) 6 1 2 7 9 8 4 5 3 Color Level 1 A Level 2 B Level 3 C Level 4 A
Level-based scheduling algorithm – Tree network (Cont.) #slot id R 1 1 6 7 6 1 2 7 9 8 4 5 3 2 2 4 8 3 1 9 R T R T R T 4 3 5 5 5 6 T T R T R T 6 1 7 3 T T 8 1 9 2 10 2
Top-down scheduling algorithm Top-down scheduling algorithm 從裝置到 Base Station 的 hop count 由小到大的順 序進行時槽規劃，只要注意會不會在傳 送時被鄰近裝置干擾，若沒有干擾則可 以被規劃。
Top-down scheduling algorithm – Tree network #slot id R 1 1 6 7 6 1 2 7 9 8 4 5 3 2 2 4 8 3 1 9 R T R T R T 4 2 5 5 1 6 T R T R T T 6 2 5 7 1 T T 8 3 9 3
模擬測試情境 測試一: 假設PDR = 1，網路為一線性拓樸， 觀察網路上裝置的增加，在演算法的時槽規 劃後完成網路上的封包傳送所需的平均封包 延遲時間與最大封包延遲時間。 測試二: 假設PDR = 1，網路為一星狀拓樸， 觀察網路上裝置的增加，在演算法的時槽規 劃後完成網路上的封包傳送所需的平均封包 延遲時間與最大封包延遲時間。 測試三: 假設PDR = 1，網路為一樹狀拓樸， 觀察網路上裝置的增加，在演算法的時槽規 劃後完成網路上的封包傳送所需的平均封包 延遲時間與最大封包延遲時間。
測試一: 配置 模擬平台: OMNeT++ 測試範圍: 1000×1000 m 無線訊號可到範圍: 134 m 網路拓樸: 線性，裝置互相之間無干擾 PDR = 1 Convergecast traffic model: 每一裝置皆有一個 資料封包欲傳送至Gateway，其中Gateway只 接收資料封包，為所有資料封包的目的端。 裝置數量: 1~30 (不包含Gateway) 時槽規劃演算法: Time-Optimal, Node-Based, Level-Based, and Top-Down。
測試一: 模擬結果
測試一: 模擬結果 (Cont.)
測試二: 配置 模擬平台: OMNeT++ 測試範圍: 300×300 m 無線訊號可到範圍: 134 m 網路拓樸: 星狀，裝置互相之間可能有干擾 PDR = 1 Convergecast traffic model: 每一裝置皆有一個 資料封包欲傳送至Gateway，其中Gateway只 接收資料封包，為所有資料封包的目的端。 裝置數量: 1~30 (不包含Gateway) 時槽規劃演算法: Time-Optimal, Node-Based, Level-Based, and Top-Down。
測試二: 模擬結果
測試二: 模擬結果 (Cont.)
測試三: 配置 模擬平台: OMNeT++ 測試範圍: 750×750 m 無線訊號可到範圍: 134 m 網路拓樸: 樹狀，裝置位置隨機擺放，裝置互 相之間可能有干擾 Packet Delivery Ratio (PDR) = 1 Convergecast traffic model: 每一裝置皆有一個 資料封包欲傳送至Gateway，其中Gateway只 接收資料封包，為所有資料封包的目的端。 裝置數量: 1~30 (不包含Gateway) 時槽規劃演算法: Time-Optimal, Node-Based, Level-Based, and Top-Down。
測試三: 模擬結果
測試三: 模擬結果 (Cont.)
測試一結論 在測試一中，線性的網路拓樸使用Node- Based 的平均封包延遲會比較長，原因在於 使用 Degree 高的裝置優先傳送封包以至於最 接近 Gateway 的裝置未在第一時間傳送，造 成平均封包延遲增長。 至於 Top-Down 的平均封包延遲最短原因在 於將最靠近 Gateway 的封包一定會被優先規 劃。
測試一結論 (Cont.) 除了Time-Optimal多了一個時槽以外，其他 演算法最大封包延遲都是相等的。 Time-Optimal多了一個時槽的原因在於當剩 下兩個封包時會產生一次的時槽浪費，會有 兩裝置的狀態分別為I, R。
測試二結論 在測試二中，星狀的網路拓樸使用Time- Optimal的平均封包延遲與最大封包延遲會比 較長，原因在於裝置在進入”active”時，會遵 守狀態的循環(TIR)，若有裝置A處於“R” 的狀態下，鄰近有裝置想傳送封包卻發現會 干擾到裝置A，故無法傳送造成此時槽的浪 費。 由此可見，Time-Optimal在網路拓樸中有過 多的干擾會造成封包延遲的時間增加。
測試三結論 在測試三中，樹狀的網路拓樸使用Time- Optimal平均封包延遲最長，而Top-Down平 均封包延遲最短。 如同測試一結論，因為Top-Down會優先將最 接近Gateway的封包傳送，故平均封包延遲 會短於其他演算法。
參考文獻 Shashidhar Gandhama, Ying Zhangb, Qingfeng Huangb, “Distributed time-optimal scheduling for convergecast in wireless sensor networks,” Science Direct, Volume 52, Issue 3, Pages 610–629, February 2008. Sinem Coleri Ergen, Pravin Varaiya, “TDMA scheduling algorithms for wireless sensor networks,” Springer Link, Volume 16, Issue 4, pp 985-997, May 2009.
Thanks for listening