在有機率連線的先進讀表基礎建設網路，佈建最少預期射頻及電力線通訊集中器的改良式貪婪演算法

Improved Greedy Algorithm for Deploying Minimum Expected RF and PLC Concentrators in an AMI Network with Probabilistic Links

羅惠琦(Hui-Chi Lo)

指導教授 ： 蔡明哲

國立清華大學/電機資訊學院/資訊工程學系所/碩士(2018年)

摘要

使用智慧電網可以提供供電者以及使用者許多好處，其中包含了更有效率的使用電力以及帳單的最佳化，這是因為使用智慧電網後，我們可以即時監控用電量並做出對應的行為。然而，在建立智慧電網的過程中，先進讀表基礎建設 (Advanced Metering Infrastructure, AMI) 扮演了很重要的角色，因為AMI建立了可以讓電力公司、智慧電表以及集中器互相溝通之網絡。由於AMI的重要性，以及安裝集中器之高成本，要如何佈建集中器的問題成為了一個重要的議題。在此篇論文中，我們致力於在許多集中器候選位置中，選擇出最少的集中器來使每個智慧便表透過他們傳遞資料至電力公司。此外，在解決此問題時，我們同時也考慮了延遲 (latency)以及信賴度 (reliability)的需求。
為了解決上述提到之問題，在此篇論文中我們提出了兩個演算法：ImpGreedy以及IDPIG。除此之外，我們設定不同參數並跑實驗與greedy演算法比較。透過觀察實驗結果，結果顯示利用此篇論文所提出之演算法可得到較好之結果。

關鍵字

智慧電網 ； 智慧電表 ； 射頻集中器 ； 電力線集中器 ； 先進讀表基礎建設

並列摘要

Using smart grids provides several advantages for both providers and customers, including using electricity more efficiently and payment optimization since we can monitor the electricity consumption promptly and do action in time. In the construction of smart grid, Advanced Metering Infrastructure (AMI) plays an important role, because it constructs the network between utility company, smart meters and concentrators. Due to the importance of AMI and the high cost of concentrator installation, the problem of concentrator deployment is a great issue. We aim to select a minimum number of concentrators from candidates to make each smart meter transmit data to the utility company, and also consider latency and reliability simultaneously due to the rules in the specification of smart grids. For the purpose of solving this problem, we came up with two algorithms ImpGreedy and IDPIG in this thesis and further compared our algorithms with a greedy algorithm. In addition, we conduct experiments and the results show that we can get better solutions by using our proposed algorithms.

並列關鍵字

smart grid ； smart meter ； RF concentrator ； PLC concentrator ； AMI

參考文獻

[1] Mohassel, Ramyar Rashed, et al. ”A survey on advanced metering infrastructure.” International Journal of Eletrical Power & Energy Systems 63 (2014): 473-484.

[2] Bing He, Bin Xie, and Dharma P. Agrawal. ”Optimizing the internet gateway deployment in a wireless mesh network.” Mobile Adhoc and Sensor Systems, 2007. MASS 2007. IEEE International Conference on. IEEE, 2007.

[3] Maolin, T. A. N. G. ”Gateways placement in backbone wireless mesh networks.” International Journal of Communications, Network and System Sciences 2.01 (2009): 44.

[4] Wong, Jennifer L., Roozbeh Jafari, and Miodrag Potkonjak. ”Gateway placement for latency and energy efficient data aggregation [wireless sensor networks].” Local Computer Networks, 2004. 29th Annual IEEE International Conference on. IEEE, 2004.

[5] Wang, Junfang, et al. ”Efficient mesh router placement in wireless mesh networks.” Mobile Adhoc and Sensor Systems, 2007. MASS 2007. IEEE International Conference on. IEEE, 2007.