物聯通信下考慮封包遺失之節點選擇與資源分配最佳化

Joint Optimization of Node Selection and Time Slot Allocation for Lossy Wireless Sensor Networks Based on Compressive Sensing

陳泓弦(Hung-Hsien Chen)

指導教授 ： 謝宏昀

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

https://doi.org/10.6342/NTU202004186

摘要

隨著裝置數量大幅度成長，隨之而來面臨到有限傳輸資源問題。在本篇論文中，我們探討典型的無線物聯通訊網路，佈滿大量的感測器，但傳輸資源不足以致於無法讓每個裝置都回傳資料。在節點選擇的研究中，大部份的研究假設一個理想的傳輸通道，因此資料不會在傳輸過程中丟失，此外，傳統上每個裝置會被分配同等數量的傳輸資源，並没有考慮個別節點資料的重要性。因此，我們考慮在封包可能遺失情況下，基於壓縮感知技術設計一關於節點選擇和資源分配的最佳化問題。但由於此問題處理上較複雜，首先，我們依據期望傳輸次數預先決定好每個裝置所分配到的資源，將其簡化成一純節點選擇問題，但此問題仍然為一二元變數的非線性規劃問題，因此我們提出一隨機搜尋演算法，以最小化重建誤差。仍而此方法需要較複雜運算時間，因此我們另外提出了兩個貪婪演算法，第一個是基於資料相關性找出一組節點，其資料相對於未選擇節點之資料有最小的條件方差，第二個是基於貝葉斯壓縮感知，找到最低的估計均方誤差。我們提出的這些方法在重建錯誤上至少能再降低70%，然而，依據期望傳輸次數分配資源是較簡略的做法，在資源多的情況並没辦法最有效率地分配，為此我們進一步對每個節點應分配多少傳輸資源建立一最佳化問題，並透過模擬退火機制演算法來解決我們的最佳化問題。相比於預先分配資源的做法，又能進一步降低25%的重建錯誤。為此，在設計節點選擇的同時，對資源分配進行優化，將可獲得比傳統節點選擇演算法還要好的表現。

關鍵字

物聯網 ； 壓縮感知

並列摘要

Due to the tremendous growth of machines, the limited radio resources is a challenge to be overcome. In this thesis, we focus on compressive sensing-based WSN that consists of a large number of sensors but rather insufficient resources. For related works that deal with node selection in CS-based WSNs, a majority of papers assume ideal wireless channels without taking data loss into consideration. Besides, selected nodes are allocated the same amount of radio resource (time slot) for transmission. Thus, we introduce the retransmission mechanism into our target scenario and we formulate a joint optimization problem dealing with node selection and resource allocation. First of all, we heuristically pre-allocate time slots to selected sensors based on expected transmission count (ETX). The problem is an NP-hard problem, and thus we refer to a meta-heuristic algorithm based on cross-entropy method in order to solve the problem. To reduce the computation complexity of the meta-heuristic algorithm, we propose greedy algorithm that iteratively selects the sensor node with the smallest estimated MSE. Besides, from a different perspective, we propose another greedy algorithm that iteratively selects the sensor node with the smallest conditional variance. Compared to baseline method, our proposed methods can reduce reconstruction error by at least 70% on average. Next, we optimize the allocation of time slots to selected sensors. We refer to a meta-heuristic algorithm based on simulated annealing method in order to solve the problem. Compared with heuristic allocation, the optimized resource allocation can reduce the reconstruction error by 25% on average. Thus, considering retransmission in designing node selection methods can bring in better performance in terms of reconstruction error than traditional ones that selected nodes are allocated a unit of radio resource for transmission.

並列關鍵字

Wireless sensor networks ； Compressive sensing

參考文獻

[1] Cisco Visual Networking Index (VNI) Complete Forecast for 2015 to 2020, Cisco, San Jose, CA, USA, Jun. 2016.

[2] H.-Y. Hsieh, C.-H. Chang, and W.-C. Liao, “Not every bit counts: Data centric resource allocation for correlated data gathering in machine-to machine wireless networks,” ACM Transactions on Sensor Networks (TOSN), vol. 11, no. 38, Feb. 2015.

[3] H.-Y. Hsieh, T.-C. Juan, Y.-D. Tsai, and H.-C. Huang, “Minimizing radio resource usage for machine-to-machine communications through data-centric clustering,” IEEE Transactions on Mobile Computing, vol. 15, pp. 3072–3076, Dec. 2016.

[4] S. E. Wei, H. Y. Hsieh, and H. J. Su, “Joint optimization of cluster formation and power control for interference-limited machine-to-machine communications,” 2012 IEEE Global Communications Conference (GLOBECOM), pp. 5512–5518, 2012.

[5] S. Y. Lien, K. C. Chen, and Y. Lin, “Toward ubiquitous massive accesses in 3GPP machine-to-machine communications,” IEEE Communications Magazine, vol. 49, no. 4, pp. 66–74, Apr. 2011.