運用在無線物聯網的位置更新之 樹狀資料結構最佳修剪演算法

Abstract

在本篇論文當中，我們提出了運用在無線物聯網之下，使用剖析 樹資料結構的位置更新演算法。在無線物聯網的通訊網路環境中，可 能會有非常大量的通訊設備(MTC 設備) 聚集在同一個區域當中，假 使每個MTC 設備都採取定期更新位置的方式回報給伺服器，如此一 來就會造成伺服器端雍塞的情況。根據消息理論，跟傳統的定期回報 位置更新訊息方式比較起來，比較有效率的方法是: 唯有在需要增加 新節點到剖析樹中的時候，MTC 設備才需要回報位置更新的資訊。 進一步而言，由於MTC 設備的記憶體容量通常不大，而且使用電池 供電，需要避免能源的消耗，因此我們提出了一個樹狀資料結構最佳 修剪演算法，此演算法可以最小化記憶成本和能源成本的權重和。此 外，我們推導出此演算法的計算複雜度很小，是可以運用在實際的系 統上的。最後，我們同時使用了分析結果和模擬結果來證明我們所提 出的方法。

In this thesis, we propose a parsing-tree-based location update scheme for wireless Machine-to-Machine (M2M) communication. In M2M communication networks, there might be a large amount of Machine-Type-Communication (MTC) devices in a small area. If each MTC device periodically performs location update, the MTC server might be overloaded. According to Information Theory, in comparison with periodically performing location update, it is more efficient for a MTC device to perform location update only when the MTC device has to add a new node into the parsing tree. Since a MTC device typically has limited memory and is battery-powered, we propose an optimal tree pruning algorithm that minimizes the weighted sum of the energy cost and the memory cost. In addition, we show that the computation complexity of the proposed scheme is low. Furthermore, we use both analytical results and simulation results to justify the proposed scheme.