資料收集機制於具有行動資料收集器之無線感測網路

Data Gathering by Mobile Sinks in Wireless Sensor Networks

余昭甫(Chao-Fu Yu)

指導教授 ： 鄭建富

淡江大學/工學院/資訊工程學系資訊網路與通訊碩士班/碩士(2015年)

https://doi.org/10.6846/TKU.2015.00065

摘要

利用行動資料收集器(mobile sink)於無線感測網路(Wireless Sensor Network, WSNs)中收集資料已被廣泛的使用，此做法雖然可以避免多步傳輸(multi-hop transmission)所帶來的電量消耗不平衡問題，但不可避免的將會帶來較長之資料延遲時間。因此在本研究當中，我們將探討如何縮短拜訪路徑之長度來降低資料延遲時間。本研究將藉由拜訪感測器通訊範圍重疊的區域，來取代逐一拜訪每一個感測器，然後再利用旅行業務員演算法(Traveling Salesperson Problem algorithm, TSP algorithm)，規劃出拜訪路徑。最後再針對規劃出來的拜訪路徑做進一步的縮減。我們提出一個路徑規劃演算法，名為CTR(Combine-TSP-Reduce)。此方法之好處在於，透過合併拜訪點，可以減少拜訪點的數量，如此一來不但可以縮短拜訪路徑長度，更可以降低利用TSP演算法於規劃拜訪路徑時所需之計算量。由於我們是從交集區域中取一點做為拜訪點，因此規劃出來的路徑將會還有縮短的可能性。故在執行完TSP演算法後，我們將針對規劃出來的拜訪路徑做進一步的優化，藉此進一步地縮短拜訪路徑長度。此外，我們也將加入資料傳輸速率考量，規劃出符合傳輸速率要求的拜訪路徑。經由實驗結果可以驗證，我們所提出的方法，在減少計算量以及縮短拜訪路徑長度上皆有著很好的表現。

關鍵字

無線感測網路 ； 資料收集 ； 行動資料收集器 ； 路徑規劃

並列摘要

Mobile sinks are extensively used for data gathering in Wireless Sensor Networks (WSNs). In this study, we focus on how to shorten the length of traveling path. We propose that the mobile sink visits the overlapping areas of communication regions of sensors instead of sensors one by one. We use the Traveling Salesperson Problem (TSP) algorithm to plan an optimal traveling path to reduce the delay time of data gathering. The benefit of the proposed method is that the number of visiting points is reduced after integration of the visiting points. Our experimental results show that the proposed algorithm delivers good results in terms of time complexity, space complexity, and length of traveling path.

並列關鍵字

wireless sensor network ； data gathering ； mobile mule ； Traveling Salesperson Problem algorithm

參考文獻

[2]P. Cheong, K.F. Chang, Y.H. Lai, S.K. Ho, I.K. Sou and K.W. Tam, "A ZigBee-based wireless sensor network node for ultraviolet detection of flame," IEEE Trans. Ind. Electron., vol. 58, no. 11, pp. 5271-5277, 2011.

[4]M. Dunbabin and L. Marques, "Robots for environmental monitoring: significant advancements and applications," IEEE J. Robot. Automat., vol. 19, no. 1, pp. 24-39, 2012.

[5]D. Gong, and Y. Yang, “Low-latency SINR-based data gathering in wireless sensor networks,” IEEE Trans. Wirel. Commun., vol. 13, no. 6, pp. 3207-3221, 2014.

[6]J. Gudmundsson and C. Levcopoulos, “A fast approximation algorithm for TSP with neighborhoods,” Nordic J. Computing, vol. 6, no. 4, pp. 469-488, 1999.

[7]J. He, S. Ji, Y. Pan and Y. Li, “Constructing load-balanced data aggregation trees in probabilistic wireless Sensor networks,” IEEE Trans. Parallel Distrib. Syst., vol. 25, no. 7, pp. 1681-1690, 2014.