IEEE 802.15.4e分時跳頻下結合專用與共享鏈接之馬可夫模型與分析

Abstract

IEEE 802.15.4e TSCH主要特色有兩個，包括時槽和通道偏移。TSCH模式下最小單位是一個鏈接(單元)，節點可以使用鏈接主要有兩種模式，即專用鏈接和共享鏈接。關於專用鏈接，大多數文章用於討論排程相關的問題。而在有關共享鏈接的相關論文中，大多數文章討論模型組成並分析數學分析。然而我們發現專用鏈接和共享鏈接都無法達到工業4.0所希望達到的最佳延遲，除此之外也沒有論文討論同時考慮共享鏈接和專用鏈接的混合數學分析。我們在這篇論文中探討如何建立分析模型以評估TSCH在共享和專用單元中的性能。我們提出了一種建構馬可夫模型的新方法。首先，我們在馬可夫模型中添加了專用鏈接的概念。另外，我們需要在原始馬可夫模型中添加一個睡眠模式，因為在專用鏈接中，通道只能提供一個節點進行傳輸，而其他節點要進入睡眠。將這兩種傳輸模式添加到馬可夫中，使得模型從二維模型轉換成三維模型。經過實驗測試後，我們發現使用共享鏈接替換部分專用鏈接能夠有效減少延遲。但是共享鏈接持續上升不會使得延遲持續的下降。共享鏈接的過量增加將增加碰撞發生機率進而導致更多延遲。我們還發現，具有最低延遲的鏈接分配方式比起全部使用專用鏈接的分配提高20％延遲時間。我們也設計了一種演算法，為了方便我們能更快速找到最佳的延遲分配方案。我們提出二進制搜索演算法。此演算法能幫助我們有效且快速的找到最佳解決方案，而且比起完整搜索演算法快上14.3倍。

The IEEE has issued an amendment to 802.15.4e. In TSCH mode, the smallest unit under the TSCH specification is a cell, which includes a slot and channel offset. There are two main modes on the cell that can be used by the node, namely dedicated cell and shared cell. Regarding dedicated cells, most articles are used to discuss scheduling. In the related papers on shared cells, most of the articles will discuss and analyze the mathematical analysis. But we found that neither dedicated cells nor shared cells can achieve the best delay. Also, none of the papers discusses the mathematical analysis that simultaneously considers a mixture of shared and dedicated cells. We probe into the measure of how to build an analytical model to evaluate the performance of TSCH in both shared and dedicated cells. We proposed a novel method to construct Markov chain model. First, we added the concept of dedicated cell into the Markov model. Also, we need to add a sleep mode to the original model because in the dedicated cell, the channel can only provide one node for transmission. These two transmission modes are added to the state to turn the original Markov 2-dimensional model into a 3-dimensional model. After experimental testing, We found that replacing all the allocations using dedicated cells with shared cells one by one will reduce latency. However, increasing the shared cells continuously will not always reduce the delay. Too much increase in shared cell will increase the delay due to collision. We also found that the cell allocation with the lowest latency will be a 20\% improvement over the allocation of dedicated cells. Then we designed an algorithm for finding the best solution of delay to find the lowest value faster. In order to find the cell allocation required when the lowest delay occurs, we use the binary search algorithm. Binary search can find the best solution, which is 14.3 times faster than the full search algorithm.