具通訊傳輸品質認知性之IEEE 802.15.4e網路形成和快速加入演算法設計 The Design of Channel Quality Aware IEEE 802.15.4e Network Formation and Fast Re-Join Algorithms Speaker: Po-Hung Chen Advisor: Dr. Ho-Ting Wu 2017/05/04

Outline 相關背景及技術介紹 頻道品質估算方法 網路形成及快速加入演算法設計 模擬結果(只有部分) 目前進度 參考文獻

相關背景及技術介紹 WSN IEEE 802.15.4e RPL Network Formation

Wireless Sensor Network CC2420 CC2538

Wireless Sensor Network (Cont.)

IEEE 802.15.4e LR-WPAN IEEE 802.15.4 Layer 7 : Application 低傳輸速率 低成本 低耗能 Layer 7 : Application Layer 6 : Presentation Layer 5 : Session Layer 4 : Transport Layer 3 : Network Layer 2 : Data Link IEEE 802.15.4 MAC Layer 1 : Physical IEEE 802.15.4 PHY LR-WPAN

IEEE 802.15.4e (Cont.) Industrial WSN Layer 7 : Application 低延遲 高可靠度 可預測的延遲 保證頻寬 高能源使用效率 Layer 7 : Application Layer 6 : Presentation Layer 5 : Session Layer 4 : Transport Layer 3 : Network Layer 2 : Data Link IEEE 802.15.4e MAC Layer 1 : Physical IEEE 802.15.4 PHY

IEEE 802.15.4 IEEE 802.15.4e IEEE 802.15.4e (Cont.) 2003 Single Channel CSMA/CA IEEE 802.15.4e 2012 Multiple Channel TSCH

IEEE 802.15.4e (Cont.) Channel hopping TSCH Time slotted access Multiple channel Channel hopping Channel hopping P H channel = ASN+chOffset % N ch ∗ASN : absolute slot number

IEEE 802.15.4e (Cont.) TSCH A time slot is 10 ms. 4 ms Transmit Process 1 ms ACK Radio Turnaround 5 ms

IEEE 802.15.4e (Cont.) IEEE 802.15.4 PHY 定義了27個頻段 16 個 2.4 GHz 10 個 915 MHz 1 個 868 MHz

IEEE 802.15.4e (Cont.) Enhanced Beacon (EB) TSCH Synchronization IE ASN、Join Metric TSCH Timeslot IE Current slot in a slotframe Channel Hopping IE Channel hopping sequence TSCH Slotframe and Link IE Initial Schedule *Information Elements (IEs)

RPL IPv6 Routing Protocol for Low-Power and Lossy Networks Layer 7 : Application Layer 6 : Presentation Layer 5 : Session Layer 4 : Transport Layer 3 : Network RPL Layer 2 : Data Link IEEE 802.15.4e MAC Layer 1 : Physical IEEE 802.15.4 PHY *DAG (Directed acyclic graph)、DODAG (Destination Oriented DAG)

RPL (cont.) RPL 控制封包 DIO DODAG Information Object DAO Destination Advertisement Object DAO-ACK DAO Acknowledgement DIS DODAG Information Solicitation

RPL (Cont.) DIO DAO DAO-ACK DIS Trickle演算法

Network Formation

頻道品質估算方法 ACK Tx PDR Grouping Share Aggregation

Channel Quality Estimate 1. Grouping *Edge、Middle、None

Channel Quality Estimate (Cont.) 分群策略 分群數量 依照常用Wi-Fi頻道分群 A 4 {11~14}, {16~19}, {21~24}, {15, 20, 25, 26} 依照常用Wi-Fi頻道干擾特性分群 B 3 Edge {11, 14, 16, 19, 21, 24} Middle {12, 13, 17, 18, 22, 23} None {15, 20, 25, 26} C 7 Edge {11, 14}, {16, 19}, {21, 24} Middle {12, 13}, {17, 18}, {22, 23} 頻道個別評估 D 16 整體評估 E 1

Channel Quality Estimate (Cont.) 2. Share by TTL = 2 (with hop-count weight) 固定PDR Case Group C的情況下 200個樣本 平均PDR誤差 < ± 0.1 1 秒 1 個 packet Single Node Neighbor = 5 Node 200秒 40秒 hop-count weight 1 hop 0.7 2 hop 0.3

Channel Quality Estimate (Cont.) 3. 估計PDR封包的Aggregation 1 Byte  0 - 255 1 在短時間(200秒)內用來存Tx和Ack數值，各只需要1 Byte。 每個Group最多只需要2個Bytes 分群 數量 A 4 B 3 C 7 D 16 E 1 在廣播自己的估計PDR封包時，還可以將自己近期內(5秒)更新樣本的統計資訊包在同一個封包裡，一起廣播出去。

網路形成及快速加入演算法設計 Network Formation & Fast Re-Join Algorithms Which cells for send EB When to send EB Fast Re-Join Algorithm

Network Formation & Fast Re-Join Algorithms 協定沒明確訂定 耗電量 Trade-off IEEE 802.15.4e

Fast mNetwork Formation & Fast Re-Join Algorithms (Cont.) 1. 快速形成： 只傳送Control Message，提升單位時間內EB和RPL封包的數量，以快速建立TSCH網路。 2. 正常模式： 依照頻道品質估算的結果調整EB傳送的period，大部分cell用來傳送感測資料，少數用來維持網路的Control Message 。

Which cells for send EB Random (RD) Random Vertical (RV) Random Horizontal (RH) Uniform Distribution(UD)

Which cells for send EB (Cont.) Random (RD) 每一個cell都可以拿來傳送EB，全部隨機選擇 1 2 3 4 5 6 7 8 9 10 11 Channel Offset timeslot

Which cells for send EB (Cont.) Random Vertical (RV) 只會選擇第一個時槽的cell來傳送EB 1 2 3 4 5 6 7 8 9 10 11 Channel Offset timeslot

Which cells for send EB (Cont.) Random Horizontal (RH) 只會選擇第一個頻道的cell來傳送EB 1 2 3 4 5 6 7 8 9 10 11 Channel Offset timeslot

Which cells for send EB (Cont.) Uniform Distribution(UD) 將要規劃的cell均勻分布在第一個頻道上 1 2 3 4 5 6 7 8 9 10 11 Channel Offset timeslot

When to send EB Each frame random 1-hop avoid and randomize 每個Slotframe隨機選擇一個cell用來傳送一個EB 1-hop avoid and randomize 和1-hop的鄰居節點避開使用的cell，如果都被選用選擇最少被選擇的，並且傳送EB的機率為1-hop鄰居數量分之一 2-hop avoid 傳送EB時將自己以及鄰居節點選擇的cell和起始時間一起廣播出去，每3個slotframe送一次EB

Fast Re-Join Algorithm 耗電 時間 目標時間 PDR = 1 Channel Quality Estimate 事情就沒有那麼單純惹 PDR < 1 Collision Avoid EB Scheduling Neighbor Number

Fast Re-Join Algorithm (Cont.) Collision Avoid EB Scheduling by Coloring + RV. 2-hop Coloring Root 要知道整個拓樸的實際情況 1 : 14 15 2 3 4 5 … 97 89 99 100 101 Channel Offset timeslot

Fast Re-Join Algorithm (Cont.) Node 3 和 Node 4 因為相隔2-hop以上可以使用同 個Channel，但是對於未加入的Node 5會產生碰撞。 1 : 14 15 2 3 4 5 … 97 89 99 100 101 Channel Offset timeslot

模擬結果 Fast Network Formation Channel Quality Estimate Fast Re-Join (未完成) (Grouping) (未完成)

Channel Quality Estimate Grouping 採用固定PDR Case channel 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 Case 1 PDR 0.5 0.3 0.7 Case 2 PDR Case 3 PDR

Channel Quality Estimate Grouping (Cont.) 分群策略 PDR平均誤差收斂到小於0.1大約所需樣本數 Case 1 Case 2 Case 3 Group A 144 192 464 Group B 永遠到不了 (720 0.0172) (1088 0.0172) 80 Group C Group D 384 400 Group E (320 0.02) (320 0.028) (320 0.025)

Channel Quality Estimate Grouping (Cont.)

Channel Quality Estimate Grouping (Cont.)

Channel Quality Estimate Grouping (Cont.)

目前進度 已完成 未完成 演算法初步設計 Send EB 時機 Initial Scheduling Algorithm Channel Quality Estimate: Share Combine Initial and Data Scheduling Channel Quality Estimate: Aggregation Channel Quality Estimate: Grouping RPL Fast Re-Join Algorithm 模擬測試

Reference N. Salman; I. Rasool; A.H. Kemp, ” Overview of the IEEE 802.15.4 standards family for Low Rate Wireless Personal Area Networks” in 2010 7th International Symposium Wireless Communication Systems (ISWCS), pp.701-705 Domenico De Guglielmo; Simone Brienza; Giuseppe Anastasi, “A Model-based Beacon Scheduling algorithm for IEEE 802.15.4e TSCH networks” in 2016 IEEE 17th International Symposium on A World of Wireless, Mobile and Multimedia Networks (WoWMoM), June. 2016 , pp1-9 Domenico De Guglielmo; Alessio Seghetti; Giuseppe Anastasi; Marco Conti, “A performance analysis of the network formation process in IEEE 802.15.4e TSCH wireless sensor/actuator networks” in 2014 IEEE Symposium on Computers and Communication (ISCC), June 2014, pp1-6 T. Watteyne; A. Mehta and K. S. J. Pister, “Reliability Through Frequency Diversity: Why Channel Hopping Makes Sense”, Performance Evaluation of Wireless Ad Hoc, Sensor, and Ubiquitous Networks(PE-WASUN), Oct. 2009, pp116-123 IEEE Std 802.15.4™-2003 IEEE Std 802.15.4e™-2012 IETF RFC 6206 IETF RFC 6550 IETF RFC 7554 Minimal 6TiSCH Configuration draft-ietf-6tisch-minimal-21

Thank you for listening.