Maximizing k-Coverage Lifetime of Wireless Sensor Networks Using Mobile Sensor Nodes

本論文では，環境情報の収集を目的とする，静止ノードと可動ノードから構成されるWSNにおいて，広範囲のセンシング領域をk重被覆し，かつ，稼働時間を最大化するような可動ノードの適切な移動先，および，データ収集のためのマルチホップ通信経路を構築する手法を提案する．対象問題はMinimum Geometric Disk Cover問題を含んでいるため，NP困難な問題である．そこで，準最適解を実用時間で求めるため，遺伝的アルゴリズム（Genetic Algorithm，以下GA）に基づいた近似アルゴリズムを提案する．一般に，データ収集型WSNでは，基地局ノード（データを収集するノード）に近いノードは，より遠方のノードのデータを中継するため通信回数（通信量）が多くなって他のノードより早くバッテリが枯渇し，結果としてWSNの稼働時間が短くなることが問題になっている．この問題に対処するため，各ノードの通信における電力消費量のバランスがとれたデータ収集木を構築するような解を生成し，GAの初期解に含ませている．さらに，フィールドのk重被覆に関する十分条件を判定する効率的な手法を考案した．提案手法によるWSN稼働時間延長の性能を評価するため，提案手法の各部位を無効化した手法との比較実験をシミュレーションにより行った．その結果，100から300ノードのWSNに対し，他の手法よりも十分に優れた性能を示すことを確認した．For a wireless sensor network (WSN) consisting of both static and mobile sensor nodes to collect environmental information, we propose a method to kcover the target sensing field and maximize the WSN lifetime by moving the mobile sensor nodes to appropriate positions. Our target problem is NP-hard since it contains a Minimum Geometric Disk Cover Problem known to be NPhard, as a special case. We develop a genetic algorithm (GA) based scheme to find a near optimal solution in practical time. We devise an efficient method to check a sufficient condition of k-coverage of the field. Considering that a node near the sink node tends to consume more battery power by forwarding the data transmitted from nodes farther from the sink node, we add a tree where power consumption for communication is balanced among all nodes to our GA-based algorithm as an initial candidate solution. Through computer simulations, we confirmed that our method achieves much longer k-coverage lifetime than conventional methods for 100 to 300-node WSNs