Sleep Scheduling Method Based on Node Set Division for Maximizing Wireless Sensor Network Lifetime

本論文では，多数のセンサノードが散布されたデータ収集型無線センサネットワーク （WSN） において，必要最小限のノードを稼働させ，残りをスリープさせることで，WSN の k 重被覆維持時間を最大化する手法を提案する．本手法を実現するため，k 重被覆維持時間を最大化する，各時刻のノードの動作モード （センシングやスリープなど） およびマルチホップ通信経路を決定する問題を定式化する．本問題は典型的な組合せ最適化問題であり，短時間で最適解を算出するのは困難である．そのため，時間を多期間に区切り，1 期間にわたって維持される最適な動作モードとデータ収集経路を繰り返し決定していくヒューリスティックアルゴリズムを提案する．提案アルゴリズムとして，k 重被覆への貢献度合順に稼働させるノードを選んでいく方法と，フィールドを 1 重被覆するノードの集合 （レイヤ） を複数求め，k 個の稼働レイヤを選択する耐故障性が高い方法を提案する．提案手法における各部位の k 重被覆維持時間延長に対する効果を評価するために，提案アルゴリズムおよびその 1 部位を無効化したアルゴリズムの比較実験をシミュレーションにより行った．その結果，k の値やノード数にかかわらず，提案手法は，各比較手法よりもk重被覆維持時間が約 1.1 倍から 1.3 倍長いことが確認できた．In this paper, we propose a method for maximizing the lifetime of a wireless sensor network which k-covers the target field, by making minimum number of nodes operate and putting other nodes in sleep. For this objective, we first formulate the problem to decide the operating mode for each sensor node and the multi-hop communication route at each time to maximize the k-coverage time. This problem is a typical combinatorial optimization problem, and thus it is hard to find the optimal solution for practical time. So, we propose a method which periodically finds the solution for each of shorter time periods, which are made by subdividing the entire time period. We propose two methods; the first one is to choose active nodes in order of their contribution degree to the field k-coverage, and the second one is to find layers that each of them 1-covers the field, and choose k active layers for k-coverage. The second method is considered to be more fault-tolerant. In order to evaluate the effectiveness of our algorithms in terms of k-coverage time, we compared our methods with methods in which some of the proposed features are disabled. Through simulation-based comparison, we confirmed that the proposed methods achieve 1.1 to 1.3 times longer lifetime regardless of k and the number of nodes, than the other methods