於估測誤差限制下之無線感測網路佈建成本最小化研究

Minimization of Deployment Cost for Wireless Sensor Networks with Bounded Estimation Errors

張斯窈(Si-Yao Zhang)

指導教授 ： 林永松

國立臺灣大學/管理學院/資訊管理學研究所/碩士(2020年)

https://doi.org/10.6342/NTU202003954

摘要

在進行溫度感測的時候,如果想要百分之百的感測準確率,那麼就要在所有位置點都安裝感測器,但是這樣的話花費的成本就會偏高。為了保證測量的準確率同時最小化成本,本研究的主要內容是提出了一個數學模型,使用拉格朗日鬆弛法進行求解,將使用LR求解該模型的實驗結果與皮爾森相關係數的兩個不同實驗結果進行比較,三個實驗通過考慮三個不同的拓撲結構和三個誤差邊界,在不同情況下將實驗結果進行比較,根據結果判斷哪種方法得到的結果能達到我們的實驗目的。將三個拓撲結構和三個不同的誤差邊界結合起來進行實驗後得到結果證明我們提出的數學模型使用拉格朗日鬆弛法求解後得到的可行解表現結果更好。此研究包含三個主要觀點，一是初始數據集用租賃感測器的方法獲得，經過算法處理後達到未來進行實際長時間感測時真正部署的感測器數量有所減少的目的。二是在實際運行的時候應用算法，把部分的感測器關機以節省能耗，達到省電的目的。三是假設系統的維護需要關閉部分感測器，並且保證不會影響到系統整體的量測結果誤差。此模型中我們認為安裝感測器的成本是固定值,未來的研究中可以考慮變化的安裝成本的情況。本研究的模型還可以應用到壓力,適度,濃度等其他物理量之量測及推估,未來可以同時建置信號接受池連接所有安裝的感測器,應用於網路建置規劃之參考。

關鍵字

溫度 ； 感測 ； 網路 ； 無線網路 ； 規劃 ； 成本 ； 最小化

並列摘要

In the process of temperature sensing, if you want 100% accurate value, then you need to install sensors at all locations, but the cost will be high. In order to ensure the accuracy of measurement and minimize the cost, the main content of this study is to propose a mathematical model, which is solved by Lagrange relaxation method. The experimental results of solving the model using LR are compared with two different experimental results of Pearson correlation coefficients. Three experiments consider three different topologies and three errors According to the results, which method can achieve the purpose of our experiment. Three topologies and three different error bounds are combined to carry out the experiment. The results show that the feasible solution obtained by using Lagrange relaxation method is better. There are three arguments in this study. First, the initial data set is obtained by leasing sensors. After processing by algorithm, the number of sensors deployed in the future will be reduced. Second, in the actual operation of the application of the algorithm, part of the sensor off to save energy consumption, to achieve the purpose of power saving. The third is to assume that the maintenance of the system needs to turn off part of the sensors, and ensure that the measurement result error of the whole system will not be affected. In this model, we consider that the cost of sensor installation AI is a fixed value, and the variable installation cost can be considered in future research. The model in this study can also be applied to the measurement and estimation of pressure, humidity, concentration and other physical parameters. In the future, the simultaneous signal receiving cell can be connected to all installed sensors implementing into the reference of sensor deployment.

並列關鍵字

temperature ； sensor ； network ； wireless network ； deployment ； cost ； minimization

參考文獻

[1] Z. Cheng, M. Perillo, and W. B. Heinzelman, “General Network Lifetime and Cost Models for Evaluating Sensor Network Deployment Strategies,” IEEE Transactions on Moblie Computing, vol. 7, no. 4, pp. 131-141, April 2008.

[2] L. Contreras and C. Ferri, “Wind-sensitive Interpolation of Urban Air Pollution Forecasts,” Procedia Computing Science, vol. 80, no. 3, pp. 313–323, January 2016.

[3] J. Jiang, J. Wan, X. Zheng, C. Chen, C. Lee, L. Su, and W. Huang, “A Novel Weather Information-Based Optimization Algorithm for Thermal Sensor Placement in Smart Grid,” IEEE Transactions on Smart Grid, vol. 9, no. 2, pp. 298-319, March 2018.

[4] B. Liu, O. Dousse, P. Nain, and D. Towsley, “Dynamic Coverage of Mobile Sensor Networks,” IEEE Transactions Parallel Distribution System, vol. 24, no. 2, pp. 301–311, February 2013.

[5] K. Chakrabarty, S. S. Iyengar, H. Qi, and E. Cho, “Grid Coverage for Surveillance and Target Location in Distributed Sensor Networks,” IEEE Transactions Computing, vol. 51, no. 12, pp. 1448–1453, December 2002.