基於IEEE 802.15.4e分時跳頻機制的低延遲排程技術

Low-Delay Scheduling for IEEE 802.15.4e TSCH Networks

余建遠(Jian-Yuan Yu)

指導教授 ： 謝宏昀

國立臺灣大學/電機資訊學院/電信工程學研究所/碩士(2017年)

https://doi.org/10.6342/NTU201704142

摘要

延遲和可靠性是許多實時無線應用中考量的關鍵因素，尤其是在IEEE 802.15.4e目標中提出的TSCH模式下工業級應用。但是現在的方法只是專注于最少利用通信資源，而非利用到多信道來追求最低延遲。 此外，目前方法也僅僅適用於無傳輸失敗的理想情境。
本文中，我們先提出一個新方法來構造開銷平衡路徑算法（Cost balance tree routing）來構建樹的拓撲，結合特定排程算法，接近理論排程下限。然後，我們利用stochastic optimazation方法來探索最優的排程表(Schedule table)。為了達到這個目的，一方面，我們先探索如何構造最優序列，由此通過算法轉變為排程表;另外一方面，我們發現把限制條件加權加入最優方程，在指數級時間內能夠得到更快的收斂。為了讓我們的方法進一步適用於實際情境，我們分配冗餘資源給可能丟失的封包，同時引入並存多幀長機制（Multiple concuurent slotfram）來滿足多個延遲限制的問題。我們的模擬結果顯示，相較於現有方法，提出的方法能夠達到更低的平均延遲時間，同時也能減小關鍵節點的內存和功耗開銷。

關鍵字

低延遲排程 ； IEEE 802.15.4e TSCH ； 平衡負載樹 ； 隨機優化 ； 多幀共存機制

並列摘要

Delay and reliability have been the key factors to consider in many real-time wireless applications, especially in industrial applications that the new TSCH mode proposed in IEEE 802.15.4e targets. However, existing methods focus on minimizing the use of communication resources, but they are unable to exploit the availability of channel multiplicity for achieving lower delay in TSCH networks. Besides, they provide reliability and delay-constraint transmission only under ideal situations. In this paper, we first propose a new method to construct cost-balanced routing trees that can utilize multiple interfaces at the coordinator, and then we propose a stochastic method to explore the best schedule table that satisfies the robust and in-time requirements. To achieve the lowest average delay, we seek for the best initial link sequence, which could be further converted into time- channel schedule table with the method of simulated annealing. We find that adding constraints into the optimal function could provide better converge cast in polynomial time. To further make our method adapt to realistic scenarios, we allocate redundancy cells to improve reliability and the multiple concurrent slot frames to meet different delay-constraint demands. Our simulation results demonstrate that compared to the existing methods, the proposed method is able to achieve low-delay data collection in TSCH networks, while reducing the cache size and overall energy consumption at kernel nodes.

並列關鍵字

low-delay scheduling ； IEEE 802.15.4e TSCH ； load balanced tree ； stochastic optimization ； multiple concurrent slot frame mechanism

參考文獻

[2] N. Accettura, E. Vogli, M. R. Palattella, L. A. Grieco, G. Boggia, and M. Dohler, “Decentralized traffic aware scheduling in 6TiSCH networks: De- sign and experimental evaluation,” IEEE Internet of Things Journal, vol. 2, no. 6, pp. 455–470, 2015.

[3] O. Durmaz Incel, A. Ghosh, B. Krishnamachari, and K. Chintalapudi, “Fast data collection in tree-based wireless sensor networks,” IEEE Transactions on Mobile Computing, vol. 11, no. 1, pp. 86–99, 2012.

[4] M. R. Palattella, N. Accettura, L. A. Grieco, G. Boggia, M. Dohler, and T. Engel, “On optimal scheduling in duty-cycled industrial IoT applications using IEEE802.15.4e TSCH, volume = 13, year = 2013,” IEEE Sensors Jour- nal, no. 10, pp. 3655–3666.

[5] H. Dai and R. Han, “A node-centric load balancing algorithm for wireless sensor networks,” in Global Telecommunications Conference, 2003. GLOBE- COM’03. IEEE, vol. 1. IEEE, 2003, pp. 548–552.

[6] Y. Jin, P. Kulkarni, J. Wilcox, and M. Sooriyabandara, “A centralized scheduling algorithm for IEEE 802.15.4e TSCH based industrial low power wireless networks,” in Wireless Communications and Networking Conference (WCNC), 2016 IEEE. IEEE, 2016, pp. 1–6.