Speaker: Wang,Song-Ferng Advisor: Dr. Ho-Ting Wu 2015/7/6

Presentation on theme: "Speaker: Wang,Song-Ferng Advisor: Dr. Ho-Ting Wu 2015/7/6"— Presentation transcript:

1 Speaker: Wang,Song-Ferng Advisor: Dr. Ho-Ting Wu 2015/7/6
IEEE e中無線感測網路之排程演算法設計 Scheduling Algorithm for IEEE e In Wireless Sensor Networks Speaker: Wang,Song-Ferng Advisor: Dr. Ho-Ting Wu 2015/7/6

2 Outline 動機與目的 相關背景介紹 Scheduling Algorithm 模擬測試 結論 參考文獻

3 背景與動機 近年來，隨著無線通訊、電源、微型化，以及嵌入式運算技術的不斷演進，無線 感測器網路(WSN) 的應用已逐漸拓展到工業環境中，且工業系統專用的無線感測 網路標準也陸續問世，其效益已逐漸受到重視與了解。 工業級的無線感測網路環境通常包含數量眾多的低功率感測/致動節點，利用低複 雜度與低速率的連線，在易發生封包傳送錯誤的無線通道中傳輸資訊，因此必須 設計有別於傳統的無線感測網路技術，才能滿足工業環境中對於資料傳輸時間的 即時性與高穩定度的要求，達成令人滿意的服務品質。

4 研究目的 IEEE82.15.4e中設計無線感測網路的MAC層排程演算機制並評估與分析其網路效 益。 排程演算機制: 中央集權式管理
利用多頻率(multi-channel)的對時傳送機制(TDMA)的傳輸規範 使用跳頻(channel hopping)機制 支援多元時槽長度的階層式訊框(multiple slot-length framing)架構設計 TDMA可指定每個無線網路節點在特定的時槽及特定的頻率中傳輸或接收資料 在各種感測項目、感測頻率的差異及即時性的不同需求下，支援多元時槽長度的階層式訊框(multiple slot-length framing)架構設計

5 TDMA環境及限制 無線裝置的傳輸限制: 半雙工式的傳輸，即同一時槽中不能同時傳送或接收資料封 包。
在同一個時槽及同一頻段中，接收裝置接收到多於兩個以上裝置所傳送的資料， 以至於資料受損，即其裝置受到干擾。

6 TDMA環境及限制(cont.)

7 Distance-2 著色演算法 用途 : 方法 : 可使用於避免裝置在同頻段的干擾
由起始裝置開始，在裝置距離為2 Hop之內不能著一樣的顏色。。 依上一點為原則當拓樸所有節點不能著上此顏色時，則替換另一種顏色，其顏色不能與 其他顏色相同。 直到拓樸所有節點著完色為止

8 Distance-2 著色演算法(Cont.)

9 multiple slot-length framing
對於不同功能之感測器，各個都會有不同的即時性及需求，導致產生封包之週期 不盡相同。 感測裝置類型 資料生成頻率(Hz) 每生成的資料封包之間最多間隔時間(ms) A 1 HZ(每秒1次) 1000 ms B 0.2HZ(每5秒1次) 5000 ms

10 Scheduling Algorithm Traffic Aware Scheduling Algorithm (TASA)
LRT_Based Heuristic Scheduling Algorithm LRT_Based Heuristic Scheduling Algorithm –Spatial Function –multiple slot-length framing

11 Traffic Aware Scheduling Algorithm (TASA)
Global Queue Level (GQ) 為裝置A的子樹中擁有需傳遞封包之數量，其中不包含 裝置A自己的封包 Local Queue Level (LQ) 為裝置本身所擁有的封包之數量

12 TASA(Cont.) 方法 : 挑選出符合傳送條件且無干擾之封包集合 從集合中挑選出GQ最大值之裝置
以此裝置做起點做Spatial Function規劃，規劃一個顏色的Distance-2 著色演算法， 若挑選順序有相同的值則依照GQ>LQ>ID做挑選 當Spatial Function規畫完後，換下一個頻道，接續執行方法1，直到此無頻道可用為 止 當頻道規畫完後，換下一個時槽，繼續從方法1開始執行，直到所有封包

13 TASA(Cont.)

14 TASA(Cont.) SLOT CH 1 A AP E B F C H D 2 I 3 4 J 5 SLOT CH 6 B AP D A
TX RX 1 A AP E B F C H D 2 I 3 4 J 5 SLOT CH TX RX 6 B AP D A 7 E 8 C 9 10 11

15 Convergecast基本觀念與假設 無線裝置的傳輸限制: 半雙工式的傳輸，即同一時槽中不能同時傳送或接收資料封包。
所能使用的Channel 總數為可設定的參數。 Convergecast 的資料傳輸模式(詳述於下頁)。 本排程演算法可推導出在不同網路拓樸下，完成所有資料傳輸的排程結果。 本排程演算法的基本設計原則 越靠近Gateway (GW)的無線裝置有較高的優先權傳送資料。 盡量充分利用可使用的 channel 。 目的在於設計一個可以利用最少時槽時間，完成所有資料傳輸的排程演算法。

16 Convergecast Transmission Model
在每個無線裝置都有一個資料封包需要傳送給GW。 GW僅扮演接收者的角色，是所有資料封包的目的端。 本排程演算法在可使用的Channel數量有限制的條件下，針 對每個無線裝置，推導出應該利用哪個時槽與哪個channel 來傳輸資料，進而推導出完成所有資料傳輸所需的總時槽時 間。

17 定理：Latency lower bound of Line/Star/Tree Topology
Latency Lower bound ( T 𝑙𝑑 )代表完成convergecast traffic model 所有封包傳輸 所需要的總時槽時間的下限值。 假設 N 為網路中無線裝置的總數(不包括GW)，而可使用的Channel總數與無線裝 置的 buffer 數量都沒有限制： Line Topology 中的 T 𝑙𝑑 為 2N-1 。 Star Topology 中的 T 𝑙𝑑 為 N，且僅需利用一個Channel就可以實現 T 𝑙𝑑 的排程。 Tree Topology 的 T 𝑙𝑑 為 max{2Nmax-1,N}，其中 Nmax為tree網路拓樸的所有 subtrees 中， 擁有最多無線裝置的那個subtree所包含的無線裝置的總數量。

18 Convergecast Transmission in Line Topology
若每個無線裝置的 Buffer 數量與可使用的Channel 數都沒有限制。 GW需要接收到每個無線裝置的封包，才能完成所有傳輸。在同一無線裝置無法同 時傳送與接收的條件限制下，從 V 1 的角度而言，需要傳N個封包給GW且需要收到 V 2 的N−1個封包。所以，所需時槽數至少為 N+(N-1) = 2N-1 Line Topology中Latency lower bound ( T 𝑙𝑑 )因此為 2N-1。

19 Convergecast Transmission in Tree Topology
假設每個無線裝置的 Buffer 數量沒有限制，但可使用的 channel數量有限制，其 最大值為 𝐶 𝑚𝑎𝑥 。 此Tree Topology 的 Latency lower bound (T 𝑙𝑑 )為 T 𝑙𝑑 =max 𝑑=1 𝐷 𝑑×𝑛 𝑑 𝐶 𝑚𝑎𝑥 + 𝐶 𝑚𝑎𝑥 2 −1 ,2 𝑁 𝑚𝑎𝑥 −1,N , 其中 ，D為tree的level數, n(d)為第d層的無線裝置總數

20 LRT_Based Heuristic Scheduling Algorithm in Tree
LRT(Latest Release Time)的數值用來代表資料封包在某無線裝置中，最遲必須被此裝置傳送出去的時槽時間，才 能滿足Latency lower bound ( T 𝑙𝑑 ) 限制。此數值在傳送過程中，將逐漸遞增。 在LRT中 𝑟 𝑖,𝑗 的定義為由裝置 i 所產生的封包在到達裝置 j 後，此中間節點 j 最遲需要在第 𝑟 𝑖,𝑗 時槽將此封包轉傳出 去，才能滿足 T 𝑙𝑑 的限制。當LRT 的數值越小時，此封包在排程上傳輸的優先權就越高。 當裝置 𝑉 𝑗 轉傳裝置 𝑉 𝑖 所產生 的封包到它的父節點 𝑉 𝑘 時，因為需要一個時槽的時間，所以 𝑟 𝑖,𝑘 = 𝑟 𝑖,𝑗 +1。 LRT的數值 有下列三條計算的規則： Rule 1: 在non-leaf node 中擁有越多子孫節點的裝置，其傳送的最後一個封包的LRT 值越小，它傳送封包的優先權越高。一 個non-leaf node所傳送的最後一個封包的LRT值應設定為它的所有子節點中所傳送的最後一個封包的LRT值的最大值加1。 Rule 2: 在各節點所傳送的最後一個封包的LRT值計算方式上，在第一層各兄弟節點間的LRT值之差值為 1 ；而其餘各層其兄 弟節點間的LRT值之差值為 2。 Rule 3: non-leaf node 𝑉 𝑖 本身所產生的封包之LRT值( 𝑟 𝑖,𝑖 )為 𝑟 𝑖,𝑖 = min 𝑣 𝑖 ∈ 𝐶 𝑖 𝑟 𝑗,𝑗 −1，而 𝐶 𝑖 為 𝑉 𝑖 的所有子節點所形成的集合。 在此排程機制中，由以下兩個步驟來完成封包的初始LRT值( 𝑟 𝑖,𝑖 )的設定(範例在下一頁中) 第一步: 利用 Top-down 方式，在計算出各節點所傳送的最後一個封包的LRT值後，來決定各 leaf node封包的初始LRT值。 第二步: 執行完第一步後，再以 Bottom-up 方式， 決定non-leaf node封包的初始LRT值。

21 Example: Computation of Initial LRT Values
Lower bound = 13 第一步：決定leaf_node 的初始 LRT 值 第二步：決定non-leaf node 的初始 LRT 值

22 Schedule Hole Schedule hole 定義: 在任何時槽 t中，若以下三項條件同時在某一層 level d 中出現，則 level d 稱為schedule hole。其中 d 的範圍為 1~D (D為樹的最深深度)。 在 level d 中沒有封包 在時槽t+1中，每一 level j (j為1~d-1)中只有一個封包可以傳送。 至少還有一個封包存在於 level k ( k > d ) 中等待被傳送。 一次Schedule Hole表示GW將會在某時槽中無法收到封包。 最佳的排程結果僅容許產生 Tlb – N 個 Schedule Holes。

23 3 Phases in LRT_Based Heuristic Scheduling Algorithm
中央排程器依以下次序，完成每個時槽的排程規劃： GW-child scheduling： 選取在level 1上可傳送且具有最小 LRT 值的無線裝置。 Connectivity keeping ( 以避免 schedule hole 的產生)： T 𝑙𝑑 −𝑁 為此Lower bound可以接受的schedule hole次數。 在出現過 T 𝑙𝑑 −𝑁個schedule hole之後，才執行此 Connectivity keeping 的步驟。 當產生schedule hole 時，從schedule hole最近的level選取最小LRT的裝置傳送封包。 LRT-base scheduling： 如果還有可用的Channel數，持續選擇具有最小 LRT 數值的無線裝置來傳送資料。

24 Example of LRT_Based Heuristic Scheduling Algorithm
假設無線裝置沒有 buffer 數量的限制 Channel 數(Cmax) = 2，N = 11 ， 𝑁 𝑚𝑎𝑥 = 6 ， D = 4。 lower bound( T 𝑙𝑑 ) 為max 𝑑=1 𝐷 𝑑×𝑛 𝑑 𝐶 𝑚𝑎𝑥 + 𝐶 𝑚𝑎𝑥 2 −1 ,2 𝑁 𝑚𝑎𝑥 −1,N = 13 Heuristic Scheduling GW-child scheduling Connectivity keeping – 可容忍 13-11= 2 schedule holes LRT-base scheduling

25 𝒓 𝟏,𝟏 =2 𝒓 𝟐,𝟐 =5 𝒓 𝟑,𝟑 =3 𝒓 𝟕,𝟕 =12 𝒓 𝟒,𝟒 =11 𝒓 𝟓,𝟓 =6 𝒓 𝟔,𝟔 =10 𝒓 𝟖,𝟖 =4 𝒓 𝟗,𝟗 =8 𝒓 𝟏𝟎,𝟏𝟎 =7 𝒓 𝟏𝟏,𝟏𝟏 =5

26 𝒓 𝟏,𝟏 =2 𝒓 𝟏,𝟏 =2 𝒓 𝟐,𝟐 =5 𝒓 𝟑,𝟑 =3 𝒓 𝟕,𝟕 =12 𝒓 𝟒,𝟒 =11 𝒓 𝟓,𝟓 =6 𝒓 𝟔,𝟔 =10 𝒓 𝟖,𝟖 =4 𝒓 𝟖,𝟖 =4 𝒓 𝟗,𝟗 =8 𝒓 𝟏𝟎,𝟏𝟎 =7 𝒓 𝟏𝟏,𝟏𝟏 =5

27 𝒓 𝟏,𝟎 =2 𝒓 𝟐,𝟐 =5 𝒓 𝟖,𝟑 =5 𝒓 𝟑,𝟑 =3 𝒓 𝟕,𝟕 =12 𝒓 𝟒,𝟒 =11 𝒓 𝟓,𝟓 =6 𝒓 𝟔,𝟔 =10 𝒓 𝟗,𝟗 =8 𝒓 𝟏𝟎,𝟏𝟎 =7 𝒓 𝟏𝟏,𝟏𝟏 =5

28 𝒓 𝟐,𝟎 =5 𝒓 𝟑,𝟏 =4 𝒓 𝟖,𝟑 =5 𝒓 𝟕,𝟕 =12 𝒓 𝟒,𝟒 =11 𝒓 𝟓,𝟓 =6 𝒓 𝟔,𝟔 =10 𝒓 𝟗,𝟗 =8 𝒓 𝟏𝟎,𝟏𝟎 =7 𝒓 𝟏𝟏,𝟏𝟏 =5

29 𝒓 𝟑,𝟎 =4 𝒓 𝟖,𝟑 =5 𝒓 𝟕,𝟕 =12 𝒓 𝟒,𝟒 =11 𝒓 𝟓,𝟓 =6 𝒓 𝟔,𝟔 =10 𝒓 𝟏𝟏,𝟖 =6 𝒓 𝟗,𝟗 =8 𝒓 𝟏𝟎,𝟏𝟎 =7

30 Schedule hole 𝒓 𝟖,𝟏 =6 𝒓 𝟓,𝟐 =7 𝒓 𝟖,𝟑 =5 𝒓 𝟕,𝟕 =12 𝒓 𝟒,𝟒 =11 𝒓 𝟓,𝟓 =6
𝒓 𝟔,𝟔 =10 𝒓 𝟏𝟏,𝟖 =6 𝒓 𝟗,𝟗 =8 𝒓 𝟏𝟎,𝟏𝟎 =7

31 𝒓 𝟖,𝟎 =6 𝒓 𝟓,𝟐 =7 𝒓 𝟏𝟏,𝟑 =7 𝒓 𝟕,𝟕 =12 𝒓 𝟒,𝟒 =11 𝒓 𝟔,𝟔 =10 𝒓 𝟗,𝟗 =8 𝒓 𝟏𝟎,𝟏𝟎 =7

32 𝒓 𝟓,𝟎 =7 𝒓 𝟏𝟏,𝟏 =8 𝒓 𝟕,𝟕 =12 𝒓 𝟒,𝟒 =11 𝒓 𝟔,𝟔 =10 𝒓 𝟗,𝟗 =8 𝒓 𝟏𝟎,𝟏𝟎 =7

33 𝒓 𝟏𝟏,𝟎 =8 𝒓 𝟏𝟎,𝟓 =8 𝒓 𝟕,𝟕 =12 𝒓 𝟒,𝟒 =11 𝒓 𝟔,𝟔 =10 𝒓 𝟗,𝟗 =8

34 Schedule hole 𝒓 𝟏𝟎,𝟐 =9 𝒓 𝟏𝟎,𝟓 =8 𝒓 𝟗,𝟑 =9 𝒓 𝟕,𝟕 =12 𝒓 𝟔,𝟔 =10
𝒓 𝟒,𝟒 =11 𝒓 𝟔,𝟔 =10 𝒓 𝟗,𝟗 =8

35 Schedule hole 𝒓 𝟏𝟎,𝟎 =9 𝒓 𝟗,𝟏 =10 𝒓 𝟗,𝟑 =9 𝒓 𝟕,𝟕 =12 𝒓 𝟔,𝟔 =10
𝒓 𝟒,𝟒 =11 𝒓 𝟔,𝟔 =10

36 𝒓 𝟗,𝟎 =10 Schedule hole 𝒓 𝟔,𝟐 =11 𝒓 𝟕,𝟕 =12 𝒓 𝟒,𝟒 =11 𝒓 𝟔,𝟔 =10

37 𝒓 𝟔,𝟎 =11 Schedule hole 𝒓 𝟒,𝟏 =12 𝒓 𝟕,𝟕 =12 𝒓 𝟒,𝟒 =11

38 𝒓 𝟒,𝟎 =12 Schedule hole 𝒓 𝟕,𝟐 =13 𝒓 𝟕,𝟕 =12

39 𝒓 𝟕,𝟎 =13

40 LRT_Based Heuristic Scheduling Algorithm –Spatial Function
為了讓LRT_Based Heuristic Scheduling Algorithm演算法利用空間距離區隔，使 得在同一時槽同一頻道可以規劃裝置傳送的數量增加， 在LRT-base scheduling後， 增加spatial function，使其可以安排更多裝置傳送。

41 LRT_Based Heuristic Scheduling Algorithm –Spatial Function(CONT.)

42 模擬測試情境 測試一 : 假設 PDR=1 ，觀察在Line/Star/Tree 網路拓樸中，在不同Channel總數 的限制下，完成convergecast traffic model 資料傳輸所需的總時槽時間。 測試二 : 測試PDR<1時，配合不同資料重傳排程機制，觀察在Line/Star/Tree 網路 拓樸中、在足夠的Channel總數下，完成convergecast traffic model 資料傳輸， 所需平均封包延遲時間。

43 測試情境中的樹狀網路拓樸架構 網路節點總數 N=30 (不包含 GW=Node#0) 樹狀最大深度 D = 3 26 25 19 12 30
3 2 1 4 5 6 7 8 9 11 13 20 15 16 18 17 14 19 21 22 25 24 23 26 27 28 29 30 12 10 網路節點總數 N=30 (不包含 GW=Node#0) 樹狀最大深度 D = 3

44 測試一 測試環境： 測試環境範圍:2000m*2000m Convergecast traffic model: 每個無線裝置都有一個資料封包需要傳送給GW ； GW僅 扮演接收者的角色，是所有資料封包的目的端。 PDR = 1 利用 LRT Based Scheduling Algorithm / LRT Based Scheduling Algorithm Spatial Function / TASA 產生排程結果。 利用 OMNET 模擬平台。 網路拓樸:線性(節點數10及20)、星狀(節點數12)及樹狀(節點數30)；節點數不包含 GW。 模擬結果： Y 軸：完成所有資料傳輸所需的總時槽時間 (slots) X 軸：可使用的 channel 總數

45 測試一：模擬結果 CH 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 line(10 nodes) 27
24 line(20 nodes) 57 54 star(12 nodes) tree(30 nodes) 30

46 測試一：模擬結果 CH 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 line(10 nodes) 30
21 19 line(20 nodes) 66 48 43 40 39 star(12 nodes) tree(30 nodes)

47 測試一：模擬結果 CH 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 line(10 nodes) 53
29 21 19 line(20 nodes) 210 106 72 56 46 40 39 star(12 nodes) tree(30 nodes) 54 30

48 測試一：模擬結果 Summary Summary: 網路深度 (Depth) 越大，所需傳輸總時間越長，所 需channel 數越多
不包含 GW的網路節點總數: N Summary: 網路深度 (Depth) 越大，所需傳輸總時間越長，所 需channel 數越多 Network Topology 完成傳輸所需的總時間 (T) 完成傳輸所需的 channel (C) 數 線性 (Line) 長 (T > = 2 N-1) 多 星狀 (Star) 短 (T=N) 少 (C=1) 樹狀 (Tree) 中

49 測試一：樹狀網路拓樸架構排程結果(1/2) 無channel 數限制 LRT Based Scheduling Alg. 排程結果：
完成傳輸所需總 時槽數= 30 (與 理論的下限值相 等) TIME 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ch0 20 ch1 29 24 22 17 ch2 18 21 ch3 23 ch4 19 27 ch5 ch6 28 16 25 26 30 傳輸源節點編號

50 測試一：樹狀網路拓樸架構排程結果(2/2) channel 數= 2 LRT Based Scheduling Alg.
排程結果：完成傳輸所需總時槽數= 30 time 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ch0 20 ch1 29 24 22 23 21 19 17 time 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 ch0 1 5 12 4 9 3 ch1 13 8 11 14 10 傳輸源節點編號

51 測試二 測試環境： 測試環境範圍:2000m*2000m Convergecast traffic model
利用 LRT Based Scheduling Algorithm 產生排程結果 OMNET 模擬平台 網路拓樸:線性(節點數10)、星狀(節點數12)及樹狀(節點數30) Channel Error Pattern: Random error PDR 為0.1、0.2、0.3、0.4、0.5、0.6、0.7、0.8、0.9、1 資料重傳排程機制參數:n=1、n=2、n=3 每個無線裝置在每個週期(週期長度 = 50 sec.)中產生 1 個資料封包 模擬總時間為20000 sec. 模擬結果： Y 軸：封包平均傳輸延遲時槽時間 (Average Packet Delay in slots) X 軸：PDR

52 Repetition-n 資料重傳排程機制
以 LRT Based Scheduling Algorithm 所完成的排程規劃結果為基礎；完成所有資 料封包傳輸的總時槽時間定義成 Ts1。 針對Ts1中各時槽的傳輸/接收鏈路 (Tx/Rx Link Pair)配置結果，針對每個時槽，重 複在連續的 n 個時槽中，執行相同的時槽配置規劃；則完成所有資料封包傳輸的 總時槽時間將變成 Tsn 。 Tsn= n Ts1。 在 PDR < 1 的環境下，若發生資料傳輸錯誤，無線裝置發射節點可在連續的 n 個 時槽中，重複傳送相同資料封包到其接收節點。 Repetition-n資料重傳排程機制以Tsn為新的資料封包傳輸排程週期，週期性的執 行傳輸/接收鏈路 (Tx/Rx Link Pair)配置。

53 Example of Repetition-n資料重傳排程機制(1/3)
n=1, Ts1= 3 GW 3 2 1 V1 V2 V3 #slot 左圖網路拓樸之時槽規劃及傳輸/接收鏈路配置結果

54 Example of Repetition-n資料重傳排程機制(2/3)
n=2, Ts2= 6 GW 3 2 1 #slot V1 V1 V2 V3 V2 V3 V1 V1 copy copy copy 重複一次時槽規劃及傳輸/接收鏈路配置結果

55 重複兩次時槽規劃及傳輸/接收鏈路配置結果
Example of Repetition-n資料重傳排程機制(3/3) n=3, Ts3= 9 GW 3 2 1 #slot V1 V1 V1 V2 V3 V2 V3 V2 V3 V1 V1 V1 copy copy copy copy copy copy 重複兩次時槽規劃及傳輸/接收鏈路配置結果

56 測試二模擬結果:線性網路 (N=10) Repetition-n

57 Average Packet Delay-Line
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

58 測試二模擬結果:線性網路 (N=10) Repetition-n

59 Average MAX Packet Delay-Line
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

60 測試二模擬結果:星狀網路 (N=12) Repetition-n

61 Average Packet Delay-Star
測試二模擬結果:星狀網路 (N=12) Average Packet Delay-Star n=1 n=2 n=3 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 9.1650 0.9 7.7800 1 6.5000

62 測試二模擬結果:星狀網路 (N=12) Repetition-n

63 Average MAX Packet Delay-Star
測試二模擬結果:星狀網路 (N=12) Average MAX Packet Delay-Star n=1 n=2 n=3 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

64 測試二模擬結果:樹狀網路 (N=30) Repetition-n

65 Average Packet Delay-Tree
測試二模擬結果:樹狀網路 (N=30) Average Packet Delay-Tree n=1 n=2 n=3 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

66 測試二模擬結果:樹狀網路 (N=30) Repetition-n

67 Average MAX Packet Delay-Tree
測試二模擬結果:樹狀網路 (N=30) Average MAX Packet Delay-Tree n=1 n=2 n=3 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

68 測試二：模擬結果 Summary 在不同PDR與各種Repetition-n情境下，封包平均傳輸延遲時間的結果比較 PDR Repetition-n n=1 n=2 n=3 1 短 中 長 0.1 Summary: 當PDR很高時(PDR=1)，n=1資料重傳排程機制不必浪費大量的空時 槽來安排重傳封包，所以封包平均延遲時間較短；而當PDR降低時(PDR=0.1)， n>1 可允許封包連續重傳n-1次，提高封包在一個週期內完成傳輸的機會， 因此，封包平均延遲時間較短。 68

69 結論 本論文在實驗之後，觀察出在PDR=1時規劃排程所需要的Channel 數並不需要很多，所以本論文所設計之方案增加利用空間距離區隔 的方式，來有效增加規劃數量並與本身具有規劃多頻道之方法，與 TASA相比所規劃更具優勢。但在PDR<0.4時，封包重傳數大大增 加，所以應該要去避免使用此頻道，所以未來勢必需要增加屏蔽頻 道之功能，希望未來可對這部分進行改進。

70 References H. Zhang, P. Soldati, and M. Johansson, “Performance bounds and latency- optimal scheduling for convergecast in WirelessHART networks,” IEEE Trans. Wireless Commun., vol. 12, no. 6, pp. 2688–2696, Jun H. Zhang, P. Soldati, and M. Johansson, “Optimal link scheduling and channel assignment for convergecast in linear WirelessHART networks,” in Proc International Symposium on Modeling and Optimization n Mobile, Ad hoc and Wireless Networks. M.R. Palattella, N. Accettura, M. Dothler, L.A. Grieco and G. Boggia, "Traffic Aware Scheduling Algorithm for reliable low-power multi-hop IEEE e networks,“ In: Personal Indoor and Mobile Radio Communications (PIMRC), IEEE 23rd International Symposium on. IEEE, pp M.R. Palattella, N. Accettura, M. Dothler, L.A. Grieco and G. Boggia, “On Optimal Scheduling in Duty-Cycled Industrial IoT Applications Using IEEE e TSCH,” IEEE Sensors Journal, vol. 13, no. 10,pp , OCTOBER 2013

71 Thanks For your Listening