Speaker : Chih-Ching Chen Advisor : Dr. Ho-Ting Wu 2014/10/21 Reliable and Real-time Communication in Industrial Wireless Mesh Networks Speaker : Chih-Ching Chen Advisor : Dr. Ho-Ting Wu 2014/10/21

Outline Introduction Wireless Mesh Network Reliable Graph Routing Definitions Algorithms Conclusions References

Introduction Wireless Mesh Network具有與傳統有線網路截然不同的特性，包括隨時可能改變的網路型態、沒有方向或範圍限制的移動等，因此，它需要一種新的路由協定（Routing Protocol）來替這些Node（節點）找出彼此聯繫的路徑。 在無線網路的環境中，時常會因為距離和雜訊的影響下而導致資料無法成功傳送，為了確保資料傳送的成功率上升，這裡敘述如何建立 reliable graph routing。

Wireless Mesh Network (1/2) Wireless Mesh Network是一種完全無線、可任意移動的網路架構，不需要基地台，所有Node可以任意地進行連結，且每個Node同時具有Router（路由器）的功能。

Wireless Mesh Network (2/2) 在Wireless Mesh Network網路架構中，當其中一個Node發生問題，其他與它相連的Node會自動找到其他的Node代替，也就是說，Wireless Mesh Network不會因為一個Node無法發揮作用，就導致該Node以下的全部Node都跟著失去作用，而使用者可視情況需要隨時新增或移除一個Node，非常方便。 同時每個Node都必須擁有動態的Routing能力，讓每個裝置在接收訊息的時候，都能判斷這個訊息是“接收這個訊息”或是“傳給下一個Node”，訊息也就是利用這樣的方式傳送到目的地。

Reliable Graph Routing

Source Routing 來源裝置到目的裝置在傳送資料之前先決定一條繞送方式，之後傳送資料只能依照此路徑傳送， 如Figure 1。 Figure 1 - Source routing

Graph Routing 來源裝置到目的裝置能夠在傳送資料的過程中，選擇繞送的方式，如Figure 2。 Figure 2 – Graph routing

Network Topology 以下(Figure 3)是一網路拓樸 Figure 3 – Network topology

Uplink Graph 每個裝置都有到Gateway的路徑，如Figure 4。 Figure 4 – Uplink graph

Broadcast Graph 從Gateway到每個裝置的路徑，如Figure 5。 Figure 5 – Broadcast graph

Downlink Graph 從Gateway到其中一個裝置的路徑，如Figure 6所示，實線為Gateway到裝置4，虛線為Gateway到裝置3。 Figure 6 – Downlink graph

Notations G(V, E): original network topology (Figure 3) GU(VU, EU): uplink graph (Figure 4) GB(VB, EB): broadcast graph (Figure 5) GV(VV, EV): downlink graph (Figure 6) δi-: device i 有多少 incoming degree δi+: device i 有多少 outgoing degree

Reliability Requirements and Reliable Graphs – Definition 1 Definition 1: 一有向圖 G(V, E)的所有節點v必須滿足 (k, m)-reliability 且 δv-≧k, δv+≧m。 若k = 0, δv-則沒有限制 若m = 0, δv+則沒有限制

Reliability Requirements and Reliable Graphs – Definition 2 Definition 2: 從有向圖G(V, E)找到一有向無環圖GB(VB, EB) (其中 VB = V, EB為E的子集合)，此圖符合 (2, 0)-reliability 則是一 reliable broadcast graph，其中Gateway和AP不在此限制。

Reliability Requirements and Reliable Graphs – Definition 3 Definition 3:從有向圖G(V, E)找到一有向無環圖GU(VU, EU) (其中 VU = V, EU為E的子集合)，此圖符合 (0, 2)-reliability 則是一 reliable broadcast graph，其中Gateway和AP不在此限制。

Reliability Requirements and Reliable Graphs – Property 1 Property 1: GB 和 GU 都不會少於兩個AP。 Proof: 假設只有一個AP AP AP u u v v

Reliability Requirements and Reliable Graphs – Definition 4 Definition 4:從有向圖G(V, E)找到一圖GV(VV, EV) (其中 VV 為V的子集合, EV為E的子集合)。 其中節點v是唯一的目的端，Gateway是唯一的來源端 每一個中繼節點必須符合 (0, 2)-reliability 環路的長度必須為2，並且在環路中的節點要有一條方向往節點v 符合以上三項條件則是一 reliable download graph。

Reliability Requirements and Reliable Graphs – Property 2 Property 2: GV(VV, EV) 至少包含一條有向環路。 Proof: 假設裝置v鄰近AP G A1 A2 v

Difficulties in Achieving Completely Reliable Graphs Figure 7 – Success ratio vs. Edge success probability Figure 8 - Percentage of reliable nodes

Constructing Reliable Broadcast Graph - Algorithm 1 2 3 4 5

Constructing Reliable Uplink Graph - Algorithm 1 2 3 4 5

Constructing Scalable Reliable Downlink Graph 為什麼不是“Constructing Reliable Downlink Graph”? 因為有n個裝置要從G(V, E)找到n個GV(VV, EV) 會造成網路上不必要的配置開銷，並且考慮到裝置v的前一跳的節點若已經建立了自己的 reliable downlink graph，為何不將此 graph “reuse” 則能減少網路上的配置開銷，還能夠建立裝置v的reliable downlink graph。

Constructing Scalable Reliable Downlink Graph - constraints v Gu2 C2 v u1 u2 Gu1 C3 u1 u2 v C1

Constructing Scalable Reliable Downlink Graph - Algorithm

Constructing Scalable Reliable Downlink Graph v C1 v u1 u2 Gu1 C3 G A A u1 u2 v Gu2 C2 1 2 3 4 5

Conclusions 以上說明的這些演算法可以找到比較可靠的繞送方式，但對於比較邊緣裝置的可靠度較低，甚至只有一條連結可以連接，對此裝置的Packet delivery ratio (PDR)會比其他裝置還要低。 當底層使用TDMA的架構進行傳輸，在此並未詳細說明時槽的規劃。 假設在時槽規劃上，勢必會浪費一些時槽，但可以確保PDR會有所上升。

References Song Han, Xiuming Zhu, Aloysius K. Mok, Deji Chen, Mark Nixon, “Reliable and Real-time Communication in Industrial Wireless Mesh Networks,” Real-Time and Embedded Technology and Applications Symposium (RTAS), 2011 17th IEEE, pp. 3-12, April 2011. WirelessHART, 2010 International Electrotechnical Commission, IEC 62591. 無線網狀網路http://www.gss.com.tw/index.php/focus/eis/76-eis43/476-wireless-mesh-network

Thanks for listening