非線形最適化による協調位置推定手法に関する研究
代表研究者

塩 田 茂 雄千葉大学 大学院工学研究院教授

1 はじめに実世界に置かれた無数のセンサが収集する大量のデータを蓄積・解析し，有意な情報を得て実世界にフィードバックする IoT 技術が注目されている．センサが収集するデータに収集された場所の位置情報が付与されていれば，データの有用性は大きく向上する．このため，センサ自身が自らの位置を推定し（もしくはオフラインで推定した位置情報をセンサに与え），収集データに位置情報を自動でタグ付けすること等を目的として，センサ位置推定法に関して数多くの研究・提案が行われてきた．
センサ位置推定の１手法に，周囲のセンサまでの距離とその推定位置に基づいてセンサが相互に多辺測量を行い自らの位置を推定する協調位置推定がある．協調位置推定は最適化問題として数学的に定式化でき，最適解が得られれば高精度での位置推定が可能となるが，目的関数が非線形で多数の局所解をもつため，本質的に最適解を得ることが困難である．
上述の困難を解決するために，本研究では特に「レンジフリー手法」と呼ばれる位置推定技術について，(1)良好な初期解を効率的に発見する手法と，(2)初期解から最終解を探索的に求める majorization と呼ぶ手法を組み合わせた協調位置推定のアルゴリズムを提案し，その有効性を主としてシミュレーションにより検証した．さらに，対象物に反応する多数のバイナリセンサを監視領域に散布し，上記手法により各センサの位置が正確に把握できることを前提として，監視領域を通過する対象物の数を推定する手法を考案し，その精度を検証した．その結果についても報告する．
協調位置推定で用いられるタイプの最適化問題は，グラフの自動描画などにも利用されている．本研究では，提案手法をグラフの自動描画に適用し，特定のノードを中心に据えたレイアウトを実現するグラフ描画手法を確立することに成功した．この点についても本稿で説明する．

2 レンジフリー協調位置推定法
2-1 はじめに
位置推定には，位置参照点（位置が既知な点）までの距離を測定して，多辺測量などの方法により位置参照点との相対位置関係を認識し，位置を推定する手法が一般に用いられる．位置参照点までの距離の代わりに，距離に代わる他の情報を推定に用いる場合もある．位置参照点までの距離の測定値を用いるものをレンジベース手法，距離に代わる情報を位置推定に用いるものをレンジフリー手法と呼ぶ．位置参照点を多数設置するほど推定精度は向上するが，位置参照点の設置やメンテナンスには一定のコストがかかるので，いたずらに位置参照点を増やすことはできない．このため，位置推定対象の端末（センサ等）を相互にそれぞれの位置参照点として機能させることで，位置参照点の不足を補い，全体として推定精度を高める「協調位置推定」と呼ばれる手法が提案されている．協調位置推定は非線形最適化問題として定式化することができ，降下法により数値的に解を求めることが可能であるが，多数の局所解を持つため，最適解への収束が得られにくい．
レンジフリー手法では，距離の情報を「近い」もしくは「遠い」の 2 値で表現する手法がしばしば用いられる．距離を 2 値表現する手法では，距離の精密な測定が不要であるため，実装が容易である反面，十分な位置推定精度を得ることが難しい．前述の協調位置推定を用いると，2 値表現された距離情報を用いても，一定の推定精度は得られるが，センサの配置に偏りがある場合には，位置推定精度が大きく劣化することが知られる．本章では，最適解への収束性の改善に加えて，センサの配置に地理的に偏りがある場合にも十分な推定精度が得られるようなレンジフリー協調位置推定法のアルゴリズムについて検討した．
2-2 最適化問題による定式化
個のセンサが置かれている空間を考える． 個のセンサのうち，1 番から 番までは位置が既知のセンサ，+ 1番から 番までは位置が不明なセンサとし，位置が既知のセンサ の位置を ，位置が不明のセンサ の推定位置を で表す．一部のセンサペアについてはその間の距離が測定されているものとし，センサ とセン

1（公財）電気通信普及財団 研究調査助成報告書 No.32 2017

サ 間の距離が測定されている場合，その測定値を で表す． は必ずしも正確なものではなく．一般的には誤差を含むものとする．このとき，センサの位置推定は以下の最適化問題として定式化できる．
((,⋯, ) =, ⋯ , ).
(1)
ここで()≡∑,⋯,∑(−−) +∑∑(−−) ,であり， はセンサ 間の距離が測定されていれば1，そうでなければ0を取る変数とする．この定式化は古典的MDS（multi-dimensional scaling）[1]のバリエーションの一つであり，何らかの初期値を与えてstress majorization[2][3][4]と呼ばれる最急降下法の一種により数値的に解を求めることが可能であるが，目的関数が非凸であるため多数の局所解が存在し，得られた解の最適性が一般に保証されない．
2-3 緩和法による解法研究代表者は基礎的な検討により，すべてのセンサ間の距離が測定できる場合，式(1)の最適化問題をstress majorizationで解いた際の最適解への収束性は大きく改善され，初期値によらずほぼ最適解に収束することを数値的に発見した．この事実を用いて，本研究では，以下に述べるレンジフリー協調位置推定用のアルゴリズムを提案する．レンジフリー位置推定では，センサ間の距離を「近い」もしくは「遠い」の2値情報で表現するが，近い位置にあるセンサペアをリンクで結ぶと，センサの位置関係を無向グラフで表現でき，得られた無向グラフが連結であるならば，全センサ間の距離をホップ数により便宜的に表せることに注意する．そこで，全センサ間の距離をホップ数により与えて式(1)の最適化問題を解き，センサの相対的な位置座標を決定する（手順1）．全センサ間の距離が（便宜的に）与えられているため，得られた位置座標の初期値依存性は無視でき，センサの相対位置座標はほぼ一意に決定できる．次に，センサ間のホップ数にしきい値ℎ を設け，センサ間の距離がしきい値以上の場合，その間の距離は測定できないこととする．つまり式(1)において<ℎ1,=0,≥ℎとして，再度，式(1)の最適化問題を解く．このとき，しきい値はネットワークの直径（最大ホップ数）とし，初期値には前述の手順で得られたセンサの相対位置座標を利用する．得られた相対位置座標を，初期値とし，しきい値はネットネットワークの直径から1つ減らして，再び式(1)の最適化問題を解く．しきい値を1つずつ減らしながら以上の手順を繰り返す（手順2）．本研究ではこれを「緩和法」と呼ぶ．センサの分布に偏りがある場合，緩和法を適用することで，相対位置座標の推定精度は大きく向上する．
次いで，アンカー（位置が既知のセンサ）の位置情報を用いて，上記の手順で得られたセンサの相対位置座標を絶対位置座標に変換する（手順3）．具体的には，アンカーが実際の位置にできるだけ近づくように，手順2で得られたセンサの相対位置マップの拡縮，回転，並進を行い，センサの相対位置マップを絶対位置マップに変換する．相対位置マップの絶対位置マップへの変換には既知の手法[5]を用いる．最後に，stress majorization法を再度適用し，得られた絶対位置座標の微修正を行う（手順4）．
2-4 数値例
100ｍ×100ｍの領域の中の C 形状の領域に，79 個のセンサを規則的（規則配置）に，もしくは 164 個のセンサをランダムに配置（ランダム配置）した（図 1）．
100100Y coordinate [m]Y coordinate [m]8060402080604020000204060

X coordinate [m]80100020406080X coordinate [m]100

図1. センサ配置図2（公財）電気通信普及財団 研究調査助成報告書 No.32 2017

図 1 の左は規則配置の場合のセンサの位置，右はランダム配置の場合のセンサの位置（青丸）を示したものである．図における青線は，距離が 15 メートル以内に位置するセンサ間を結んだものである．
図2には提案手法によるセンサの位置推定精度を示した．図の縦軸は位置推定値の平均誤差（推定位置と実際の位置のユークリッド距離の平均）を示し，横軸（ ）は距離を2値表現する際の距離しきい値を示している（ より距離が小さければ，「近い」と認識）．比較対象として，古典的なMDS手法によりセンサの位置を推定した結果も示した．古典的MDSは，協調位置推定を最適化問題に定式化して解く際に，しばしば用いられる一般的な手法である．図2より，提案アルゴリズムは，古典的MDSよりもはるかに高精度な位置推定値を与えることが確認できる．古典的MDSは，2.3節で説明した手法において手順2と手順4を省いた手法（緩和法と最後の微調整を用いない手法）におよそ相当する．古典的MDSでは，センサ間のホップ数をそのままセンサ間距離とみなして相対的な位置推定を行うが，C形状にセンサが配置されている場合，センサ間の距離が過大に評価され，位置推定値の誤差を増大させる．提案アルゴリズムでは緩和法の適用によって，この誤差要因が大幅に低減されているが，この効果が数値結果に表れている．
図3は， =25 mの場合に提案アルゴリズムにより得られた推定位置（青丸）と実際の位置（赤×）を比較して示したものである（左：規則配置，右：ランダム配置）．特に規則配置の場合，極めて高い精度で実際の位置が推定できていることが確認できる．
Classical MDS
403535

Average estimation error [m]Average estimation error [m]Proposed Method
4030252015105

Proposed Method

Classical MDS

1525302520151050152025030

dth [m]2030dth [m]

図2. 位置推定精度
100100

Y coordinate [m]Y coordinate [m]8060402080604020000204060

X coordinate [m]80100020406080

X coordinate [m]100

図3. 推定位置と実際の位置との比較
2-5 人物の屋内位置推定への応用
屋内や地下施設にはGPSの電波は届きにくいことから，屋内や地下施設ではGPSに代わる新たな位置推定手法が必要である．屋内や地下施設用の位置推定法として，Wi-Fi，ZigBee，UWB（Ultra-wide Band）などの電波を発する装置を屋内に配置し，これら装置からの電波をユーザが所持する端末で受信することによって位置を推定する方式が検討されている．位置推定ユーザ間の近接情報（誰と誰が近い位置にいるか，等）を3（公財）電気通信普及財団 研究調査助成報告書 No.32 2017

利用できるならば，本研究で提案するセンサ用の位置推定手法は，既存の屋内位置推定法の推定精度向上に活用できると考えられる．一例として，30 m四方の部屋に位置参照点を5個（部屋の四隅と部屋の中央）設置し，20人の位置推定ユーザの位置を推定するシミュレーション実験を行った結果を紹介する．位置参照点は（Wi-Fiなどの）信号を発し，位置推定ユーザは位置参照点からの信号を受信することにより，自分がどの位置参照点の近くにいるかを知ることができるとする．さらに，位置推定ユーザ自身も（Wi-Fiなどの）信号を発する端末を所持し，それぞれのユーザが発する信号に基づき，各ユーザはどのユーザが近くにいるかを知ることができるとする．この状況はレンジフリー協調位置推定で想定している状況と同じであり，提案するレンジフリー協調位置推定アルゴリズムをそのまま適用することで，位置推定ユーザの位置を推定することができる．
図4は距離が15m以内にあるユーザを「近い」と認識したときの位置推定値と実際の位置を比較したものである．青丸が実際の人物の位置，赤の×印が人物の推定位置を示している．良好な位置推定結果が得られていることがわかる．
表1はセントロイドアルゴリズム（信号を受信した位置参照点の重心を位置推定値とする手法）と近接情報利用型位置推定法の比較をしたものである．100回シミュレーションを行い，推定誤差の平均を算出した．セントロイドアルゴリズムの平均推定誤差は5.24mであるが，近接情報を用いることにより推定精度が大きく改善されている（平均推定誤差=2.80m）ことが確認できる．
実際の位置

推定位置30m0m0m30m

図4. 屋内位置推定シミュレーション実験結果

表1. 平均推定誤差の比較
手法
平均推定誤差提案手法
2.80 mセントロイドアルゴリズム
5.24 m

3 バイナリセンサによる対象物数推定
3-1 はじめに監視領域内に，近くの対象物に反応するバイナリセンサ（対象物に反応した場合は 1，未反応の場合は 0 を出力する 2 値センサ[6][7][8]）を多数配置し，センサの反応から監視領域を通過中の対象物の数をカウントする手法について検討した．例えば，センサを道路内に埋め込むことで，道路を通過する自動車の数を自動カウントする手法などへ応用が考えられる．各センサは 2 章で述べた手法などにより，その位置が正確に把握されているものとする．センサによる対象物数推定は多数の既存研究があるが，大半は各センサがそのセンシングエリア内の対象物数をカウントする機能を持つ（例えば，画像認識機能を持つセンサにより，視野に存在する対象物をカウントできる）ことを想定しており[9][10][11][12][13][14]，バイナリセンサ等の低機能センサを用いた対象物数推定に関する研究はごく少数である．

4（公財）電気通信普及財団 研究調査助成報告書 No.32 2017

3-2 モデル
監視領域内を，複数の対象物が次々と通過する．対象物は非 0 の面積を有し，各時点で監視領域の一定のエリアを占有する．対象物の大きさや形状は時間に寄らず一定であるとする．監視領域には複数のセンサがランダムに置かれている．センサはそれぞれ一定の大きさのセンシングエリアを有し，対象物が占めるエリアとそのセンシングエリアが重なりを有する場合，センサは対象物に反応するとする．対象物が占めるエリアとセンシングエリアが重ならない場合，センサは反応しない．センサは定期的に反応結果をクラウド内のサーバに送信する．サーバでは各センサの反応結果から，監視エリア内の対象物の数を推定する．センサの散布密度が低い場合，一部の対象物を捕捉できず，対象物数は過小に見積もられる．一方，センサを密に配置した場合，一つの対象物に対して複数のセンサが反応するので，単に反応センサ数を対象物数の推定値として用いると，対象物数を過大に評価する結果となる．本研究は，対象物を確実に捕捉できるような密度でセンサを散布する場合においても，対象物数を正しく推定できるアルゴリズムを提案するものである．
3-3 自動カウントアルゴリズム
サーバは反応したセンサと未反応のセンサに分類し，それぞれの位置を調べる．次に，反応センサ群を複数のクラスタに分類する．各クラスタは未反応センサにより周囲をとり囲まれており，他のクラスタとは未反応センサにより隔てられているように選ぶ．この場合，クラスタの数を対象物数の推定値として利用できる．従って，反応センサを適切にクラスタリングする手法が見つかれば，対象物数の推定が可能となる．
本研究では，相互最近接近傍（Mutual Nearest Neighbor）の考え方を用いて反応センサ群を複数のクラスタに分類する．以下，その定義を述べる． を反応センサ ， を と 間の距離とする．さらに( ) = max| ,∈,( ,) = min( )は反応センサ集合 の内部距離， ( ,を定義する．の距離に相当する概念である．

|∈,∈) は反応センサ集合 と反応センサ集合 間

本研究では，以下の式を満たす反応センサ集合 を「相互最近接近傍を形成する」と呼ぶ．
( ) < ( , Ω/ )例えば，「反応センサ１，2，3 が相互最近接近傍を形成する」とは，センサ 12，センサ 23，センサ 13 間の距離が，それ以外の反応センサまでの距離よりも短いことを意味する．相互最近接近傍によるクラスタ分類には任意性があるが，各相互最近接近傍がその内部（凸包）に未反応センサを含まないという条件を課すことで，相互最近接近傍によるクラスタ分類が一意に可能になることを数学的に証明した．なお，相互最近接近傍によるクラスタ分類は研究代表者が初めて提案する数学的概念である．
3-4 数値例
100 m×100 m の領域にセンサをランダムに配置する．センサは半径 r の円形のセンシングエリアを有する．監視領域を複数の対象物が 10 m/s の速度で通過する（図 5）．対象物はいずれも半径 5 m の円形であるとする．センサは 1 秒おきに対象物の検出を行い．対象物に反応したセンサはその結果をクラウド内のサーバに送信する．クラウド内のサーバは前述のアルゴリズムに従い，毎秒，監視領域内の対象物数を推定する．
Region where sensors are
deployed

100 m

Direction oftarget movement

100 m

図 5. 監視領域と対象物の動き

5（公財）電気通信普及財団 研究調査助成報告書 No.32 2017

図 6 はセンサの密度が 0.1 [1/m2]のときの反応センサ（青丸），未反応センサ（灰丸），および対象物の中心点（赤×）を時間の経過とともに示したものである．センサのセンシングエリアは 0m とした（対象物が占めるエリア内にいる場合にのみセンサは反応）．各対象物の中心付近に複数の反応センサが存在してクラスタを形成し，対象物の移動（対象物は図の左から右に移動）とともにクラスタの形成場所も移動する様子が確認できる．
図 7 はセンサ密度を 0.02 [1/m2]から 0.12 [1/m2]まで変えて，時間を追いながら対象物数の推定結果と真の対象物数を比較して示したものである．センサ密度が低い場合は対象物を補足できず，対象物数が低く見積もられているが，センサ密度が高くなるにつれて推定精度が向上し，（一つの対象物に対して複数のセンサが反応するような）高密度の場合でも，対象物数の過剰な見積もりは生じていないことが確認できる．
⋅ non-target-detecting sensor

806060404020200204060t=3s80

100 [m]

[m]

060

40

402020002040t=5s6080

100 [m][m]

60t=4s8060

4040202002040t=7s6080

100 [m]0523456789Time [s] (ρ = 0.02 [1/m2])

20

40

60

t=6s805123456789107891078910Time [s] (ρ = 0.04 [1/m2])

20

Estimate

True
15

105

1100 [m]101000

Estimate

True
15

0
120

23456789

Time [s] (ρ = 0.06 [1/m2])

Estimate

True
15

1050

10

12

3456

Time [s] (ρ = 0.08 [1/m2])

[m]

20

80

60

10100 [m]

[m]

0100

80

04080

60

100

20

Number of Targets

80

1500100

20

Estimate

True

Number of Targets

100020

Number of Targets

80

center of disk-shaped target[m]Number of Targets

100

0204060t=8s80100 [m]20

Estimate

True

Number of Targets[m]Number of Targets

target-detecting sensor
100

15105010501

図 6. センサの反応

Estimate

True
1523456789

Time [s] (ρ = 0.10 [1/m2])

10123456

Time [s] (ρ = 0.15 [1/m2])

図 7. 対象物数推定精度

4 特定のノードを中心に据えたレイアウトを実現するグラフ描画手法
4-1 はじめに「グラフ」とは，あるシステムを構成する要素を点（ノード）とし，それらの接続の様子を辺（エッジ）の集合で表した数学的概念である．会社の組織図や作業の工程図など，我々は日常生活の中でグラフを図化して表現することがある．それらのレイアウトはほとんどの場合手動で行われているが，グラフを構成するデータが大規模な場合，人の手によって視覚的に分かりやすいレイアウトを実現することは非常に困難となる．そのため，グラフの可読性や美的基準を満足するグラフのレイアウトを表現する方法が要請されている．
これをグラフの自動描画（Graph Drawing）と呼ぶ．
グラフ描画には，これまでに力学モデルと呼ばれる手法に関する多数の研究がなされている．力学モデルはノード同士が引力を及ぼし合う仮想的な物理系をグラフから構築し，その系の平衡状態を計算するものである．この手法は，グラフ全体のレイアウトの審美性・可読性を志向したものが主流であり，それらを満足するための研究には多くの蓄積がある．一方で，ネットワークの分析には特定のノードやエッジを対象とし6（公財）電気通信普及財団 研究調査助成報告書 No.32 2017

た分析手法が多く知られている．それらの分析課題に対応するためには，特定のノードやエッジを基準にレイアウトを変化させることが要請される．
本章では，既存の力学モデルによるグラフ描画手法を拡張し，特定のノードを中心に据えたレイアウトを実現するグラフ描画手法を提案する．その具体的な手法として，代表的な力学モデルである kamada-kawai 法(以下，KK 法)[15]に用いられている目的関数にパラメータを導入し，任意のノードに作用する引力および斥力を調整することでレイアウトを変化させる．本章では，レイアウトが容易に想像できる簡単な構造のグラフと，一般的な構造を持つグラフを対象に提案手法による描画を行い，提案手法の有用性を検証する．
4-2 グラフ描画の最適化問題への定式化と描画アルゴリズム
個のノードの集合V =, ,⋯,と 本のエッジの集合 ⊆ × からなるグラフ = ( , )を考える．グラフの各ノードの二次元平面上の位置を =, ,⋯,とする．KK 法では，ノード 間の純粋なグラフ理論的距離を理想的な距離として設定し，以下の関数を最小化する を理想のグラフレイアウトとする．
( ,,⋯,)=∑∑−−(2)

この定式化は 2 章で説明した協調位置推定と全く同じである点に注意したい．すなわち，2 章で述べた手法
は理想のグラフレイアウトを得るためにそのまま適用できる．
本研究では，特定のノードを中心に据えるために，「特定のノードと関係が近いノード(グラフ理論的距離が短いノード) 同士の距離は拡大して配置され，関係が遠いノード同士の距離は縮小して配置される」ことを描画仮説として与える．描画仮説に基づき，式(2) の説明変数である理想的な距離 を以下の手順で設定する．グラフ理論的距離を として用いずに，異なる値を として与えることで，特定のノードを中心に据えるグラフ描画を実現することが可能となる．
手順 1：と，中心に据えたいノード からのグラフ理論的距離（

手順 2：とがエッジで接続されているとき，エッジの長さ=からのホップ数) をℎ( ) とする．
を以下の式で与える．

( ), ( )ここでα（0 < α ≤ 1）は距離に関するパラメータである．ノード に接続されたエッジの長さは常に 1 であり，ノード から遠いエッジほど，その長さは 1 より小さくなる．αが小さいほど，ノード に近いエッジと遠いエッジの長さのコントラストは大きくなる．
手順 3： 手順 2 で計算したエッジの長さを用いて，全てのノード間のグラフ理論的距離を(ダイクストラ法などで) 計算し，それをノード間の理想的な距離とする．この手順により，ノード から遠いノード間の理想的な距離はグラフ理論的距離よりも小さくなる．つまり，ノード 付近のレイアウトに比べて，ノードから離れた箇所のレイアウトは全体的に縮約されて表示されることとなる．
手順 4：と の間のホップ数ℎ( , ) がℎ( , ) ≥ ℎ( , ) + ℎ( , )を満たす場合は， と の間の理想的な距離 を以下の式で置き換える．
=+
これは ， 間の最短経路がノード を通る場合，その間の距離はノード から および までの距離の和で与えるものであり，手順 2 の効果により，ノード を迂回する経路に沿った距離の方が短くなり，その距離が ， 間の距離として採用されて，当初の意図に反するレイアウトが描画されることを防ぐ効果を狙っている．
4-3 描画結果と考察
提案した手法によって，実際にグラフを描画した．描画対象としたグラフは，格子状をした簡単な構造のグラフおよび V. ユゴーの小説『Les Miserables』に登場する人物の関係を示すグラフ[16] である．図 7，
図 8 はそれぞれ格子状グラフ，および Les Miserables の人物関係のグラフを異なるαの値で描画した結果である（左：α = 1.0，中：α = 0.5，右：α = 0.1）．中心ノードは赤色で着色してある．なお，α = 1.0では7（公財）電気通信普及財団 研究調査助成報告書 No.32 2017

通常の KK 法によるグラフ描画結果が得られ，αが小さくなるほど中心ノードからの視点でのグラフ（中心ノード近傍を強調したレイアウトのでグラフ）が描画されるようになる．
図 8 に示す通り，格子状のグラフでは，αが小さくなるほど，周辺の格子が縮小し，中心ノード視点でのグラフへと変化している．Les Miserables のグラフ（図 9）においては，αが小さくなるにつれて，中心ノードと 1 ホップでつながっているノードの所在が強調して描画されている．以上の通り，双方のグラフにおいて概ね描画仮説を満足する結果が得られた．

図 8. グラフ描画結果（格子）図 9. グラブ描画結果（Les Miserables）

5 むすび
本研究では，センサの協調位置推定を非線形最適化問題に定式化して位置推定値を求める際に生じる様々な問題を解決するための方法論について検討し，具体的な問題において，解決策を提案するとともに，その解決案をグラフ描画の問題に適用して，特定のノードを中心に据えたレイアウトを実現するグラフ描画手法を提案した．また，提案する位置推定法により，センサの位置が正確に把握できたことを前提として，バイナリセンサを用いた対象物数推定問題を考察し，新たなアルゴリズムを得た．対象物数推定用のアルゴリズ
ムは対象物が凸形状であることを暗黙のうちに仮定しているが，非凸形状の対象物に関するアルゴリズムについては現在検討中である．本研究では，端末自身は直接的な位置推定機能を持たないことを仮定しているが，端末自身が直接的な位置推定機能を持つ場合においても，近傍関係情報（各端末の近隣にどの端末が存在するか）と位置推定値との整合をとることで，位置推定値を補正する「近傍情報利用型位置推定技術」として協調位置推定を一般化できる可能性がある．端末間の近傍関係情報は，例えば Wi-Fi 機能を用いてスマートフォンから Wi-Fi 信号を送信させ，端末相互に Wi-Fi 信号を受信すれば取得可能である．今後は，一部の端末が直接的な位置推定機能を持つ場合においても，端末間の近傍関係情報を利用して推定値を補正する技術として協調位置推定法を拡張する検討を進めたい．

【参考文献】[１] T. Cox and M. Cox, Multidimensional Scaling. Chapman & Hall, London 1994.
[2] J. Costa, N. Patwari, and A. Hero III, “Distributed weighted multidimensional scaling for nodelocalization in sensor networks,” ACM Transactions on Sensor Networks, vol. 2, no. 1, pp. 39–64,
2006.

8

（公財）電気通信普及財団 研究調査助成報告書 No.32 2017

[3] S. Shioda, “Localizing sensors from their responses to targets,” IEICE Trans. Commun., vol. E98B, no. 1, pp. 145–152, 2015.
[4] E. Gansner, Y. Koren, and S. North, “Graph drawing by stress majorization,” in Graph Drawing,
ser. Lecture Notes in Computer Science. Springer, 2005, pp. 239–250.
[5] B. Horn, H. Hilden, and S. Negahdaripour, “Closed-from solution of absolute orientation using
orthonormal matrices,” Journal of the Optical Society of America, vol. 5, no. 7, pp. 1127–1135, 1988.
[6] W. Kim, K. Mechitov, C. J.-Yoon, and S. Ham, “On target tracking with binary proximity sensors,”in Fourth International Symposium on Information Processing in Sensor Networks, 2005, pp. 301–308.
[7] N. Shrivastava, R. Mudumbai, U. Madhow, and S. Suri, “Target tracking with binary proximity
sensors: fundamental limits, minimal descriptions, and algorithms,” in SenSys, 2006, pp. 251–264.
[8] J. Singh, U. Madhow, R. Kumar, S. Suri, and R. Cagley, “Tracking multiple targets using binary
proximity sensors,” in 6th International Symposium on Information Processing in Sensor
Networks, 2007, pp. 529–538.
[9] S. Guo, T. He, M. Mokbel, J. Stankovic, and T. Abdelzaher, “On accurate and efficient statisticalcounting in sensor-based surveillance systems,” in IEEE MASS, 2008, pp. 24–35.
[10] S. Gandhi, R. Kumar, and S.Suri, “Target counting under minimal sensing: Complexity andapproximations,” in Fourth International Workshop, ALGOSENSORS, 2008, pp. 30–42.
[11] Y. Baryshnikov, E. Coffman, K. Kwak, and B. Moran, “Target count recovery from sensing error,
or: Noise is good,” in Proceeding of Distributed Computing in Sensor Systems, 2008.
[12] Y. Baryshnikov and R. Ghrist, “Target enumeration via integration over planar sensor networks,”
in Proceedings of Robotics: Science and Systems IV, 2008.
[13] Y. Baryshnikov and R. Ghrist, “On target enumeration in sensor networks via integration withrespect to Euler characteristics,” SIAM J. Appl. Math, vol. 70, no. 3, pp. 825–844, 2009.
[14] D. Wu, D. Chen, K. Xing, and X. Cheng, “A statistical approach for target counting in sensorbased surveillance systems,” in IEEE INFOCOM, 2012, pp. 226–234.
[15] T.Kamada ， S.Kawai ， An Algorithm for Drawing General Undirected Graphs ， Information
Processing Letters，Vol.31，No.1，pp.7-15，1989[16] ”Netwok data repository”，http://networkdata.ics.uci.edu/index.php(2017.1.11 閲覧)〈発題

名Target counting using binary proximity
sensors via cluster identification
Connectivity-Based Sensor Localization
for Anisotropic Networks by Stress
Relaxation

表資料〉

掲載誌・学会名等

発表年月

IEEE ICC

2015 年 6 月

IEEE VTC Fall2015 年 9 月

レイアウトを変化させるグラフ自動描
画手法

電子情報通信学会 ソサエティ大会, A-1-13

2015 年 9 月

Localizing Sensors from their Responses
to Targets

IEICE
Information
andCommunication Technology Forum2016 年 6 月

近接情報を利用した屋内位置推定手法
力学モデルを用いた特定のノードを中心に据えるグラフ描画手法

電子情報通信学会 総合大会,
B-18-22
電子情報通信学会 総合大会,
A-1-5

2017 年 3 月
2017 年 3 月

9（公財）電気通信普及財団 研究調査助成報告書 No.32 2017