以理論演算法角度探討無線感測網路的排程問題

Approximating the Wireless Sensor Network Scheduling Problem

陳思蓉(Szu-Jung Chen)

指導教授 ： 廖崇碩

國立清華大學/工學院/工業工程與工程管理學系/碩士(2014年)

https://doi.org/10.6843/NTHU.2014.00294

摘要

無線感測網路(Wireless sensor network)是由分布在空間中的一個或數個無線資料蒐集器和許多無線自動感測器所組成的無線通訊計算機網路，其感測器能夠監測放置區域的物理現象或環境狀況。由於感測器通常是使用電池當作電力來源，若沒有規劃每一個感測器適合的使用時間點將導致無線感測網路的使用壽命不長，進而衍生了無線感測網路的感測器排程問題。
無線感測網路的感測器排程問題描述如下：給定一個感測器的集合，與這些感測器能夠監控的區域的集合。每一個區域可被一些感測器監控，一個感測器也可能監控多個區域。我們想要找出方法劃分每一個感測器到互斥的子集合中，讓每一個感測器子集合都必須能夠監控所有的區域，而每一個感測器子集合對應到一個時段；因此，當我們在不同的時段使用不同的感測器子集合時，感測器子集合中的感測器都能夠監測所有的區域，此問題的目標是希望最大化無線感測網路的使用時段，也就是最大化感測網路的使用壽命。
本研究以理論演算法的角度討論此無線感測網路中的感測器排程問題，分別以兩種不同的模型來探討：一種為當感測器感測範圍為一定值時，本研究提出了3/4倍近似比率的近似演算法求解當區域點之間的點距離至少為√3 r+ε時的感測器排程問題，其中r為感測器的感測距離；我們同時將此結果推廣至較一般化的模型之中。另一種為當監控區域以不相通的封閉區域呈現，本研究提出了3/8倍近似比率的近似演算法求解當每一個感測器最多只能夠監控3個區域的感測器排程問題。此外，本研究根據提出的演算法可以同時找出關鍵性的感測器，其損毀時將會造成無線感測網路的可用時段減少；此關鍵性感測器可提供作為無線感測網路可靠度的重要分析。

關鍵字

無線感測網路 ； 排程 ； 近似演算法

並列摘要

A wireless sensor network (WSN) consists of one or more wireless data collectors and many autonomous sensors to monitor physical phenomena or collect environmental information. Each sensor usually uses a battery to enable its function, which limits its lifetime. In order to prolong the lifetime of WSNs, it is important to schedule the sensors to be activated in WSNs, which is called the wireless sensor network scheduling problem. The WSN scheduling problem is described as follows: Given a set of sensors, and a set of regions to be monitored, each region can be monitored by a subset of the sensors, and a sensor also can monitor more than one region. In order to prolong the lifetime of WSN, we decompose the sensors into disjoint subsets such that every subset of sensors needs to monitor all the regions, i.e. activating a subset of sensors to observe all the regions in each time slot, and the number of times slots (i.e. the number of subsets of sensors), that is, the lifetime of the WSN, is maximized.
We investigate the WSN scheduling problem in two different models, and provide several polynomial time algorithms for approximating this problem. When the monitored range of each sensor is the same, i.e. the distance r, and the distance between any two regions is at least √3 r+ε, we present a 3/4 -ratio approximation algorithm to solve the WSN scheduling problem. In addition, when every monitored region is represented by a closed area, and each sensor can monitor at most three regions, we provide a 3/8 -ratio approximation algorithm to solve this model. Moreover, we also can identify critical sensors of WSNs; a sensor is called critical if the lifetime of WSNs must decrease when the sensor is broken. The identification of critical sensors can assist the reliability analysis of wireless sensor networks.

並列關鍵字

wireless sensor network ； scheduling ； approximation algorithm

參考文獻

[1] Z. Abrams, A. Goel, and S. Plotkin. Set K-Cover Algorithms for Energy Efficient Monitoring in Wireless Sensor Networks. In: Information Processing in Sensor Network (IPSN'04), 424-432, 2004.

[4] G. Aloupis, J. Cardinal, S. Collette, S. Langerman, and S. Smorodinsky. Coloring geometric range spaces. Discrete & Computational Geometry, 348-362, 2009.

[5] B. S. Baker. Approximation Algorithms for NP-Complete Problems on Planar Graphs. Journal of Association for Computing Machinery, 153-180, 1994.

[6] V. Chvatal. A Greedy Heuristic for the Set-Covering Problem. Mathematics of Operations Research, 233-235, 1979.

[7] A. Deshpande, S. Khuller, A. Malekian, and M. Toossi. Energy Efficient Monitoring in Sensor Networks. Algorithmica, 94-114, 2011.