1．は　じ　め　に

　センサネットワークは，空間上に配置されたセンサ群が計測データを収集し（センシング），ネットワークを通じてそれらを伝達・共有するシステムである^(1),(2)．センサはネットワーク上の頂点として表され，通信路あるいは物理的な隣接関係はネットワーク上の辺に対応する．センサネットワークを利用する主な目的は，センサ群を協調させて観測環境を正確かつ効率的に把握することである．センサネットワークは，観測量のディジタル化，取得したデータの雑音除去や加工，センサ間のデータ通信，センサの制御など，多数のレイヤから構成される．そのため，計測，信号処理，通信，ロボティクス，機械学習といった幅広い領域で研究されている^(3),(4)．

　センサネットワークの技術的課題として，周囲の環境を可能な限り正確に把握すること，センシングコストを抑えることの2点が挙げられる．環境を正確に把握するとは，全ての頂点における観測量（信号値）を，所望の応用に応じた適切な誤差量で再現できる状態を指す．センシングコストとは，センサの数，価格，稼動時間，通信量，ライフタイムなど多くの要因で決まるが，センサ数は特に決定的な要因である．つまり，少ないセンサで広い領域を監視する技術がセンサネットワークの根本的な要請である^(5),(6)．その一つのアプローチとして，センサネットワーク内の一部のセンサのみを実際の観測に使用し，それ以外のセンサに対応する信号値を推定する方法が挙げられる．少ないセンサで多くの頂点の信号を推定することは，言い換えれば，限られた数のセンサを適切な位置に配置してネットワーク全体の信号推定精度を高めることとも言える．

　一般に，センサネットワークの構造は不規則であり，センサの配置に関して万能なアルゴリズムは存在しない．ネットワーク上の重要な頂点を決定する問題はセンサ配置問題と呼ばれる^(5)～(7)．古典的なセンサ配置問題では，センサの空間的制約を無視した上でセンサ配置を考えるため，センサは空間上で自由に配置可能であり，センサ間の接続関係が空間的な距離のみで決まる．その結果，既存のセンサ配置アルゴリズムは，連続空間を等間隔にサンプリングし，近傍法で頂点を接続した結果得られるネットワーク（格子ネットワーク）を前提としている^(8),(9)．しかし，実際のセンサネットワークでは，障害物，電源，環境条件など多くの空間的制約が想定され，センサの隣接関係は空間的な距離に必ずしも対応しない．そのため，空間的な制約を考慮した上でセンサ配置を決定する技術が新たに要請されている．