博士論文

受信信号強度に基づく信号源位置の効率的探索の研究
A Study on Eﬃcient Search Algorithm of Signal Source Location
based on Received Signal Strength IndicatorKazuyuki Ishii
石井 和行
情報セキュリティ大学院大学
情報セキュリティ研究科
情報セキュリティ専攻

2020 年 3 月

要旨
本論文は，無線通信時に得られる受信信号強度 (RSSI: Received Signal Strength Indicator ) が通
信距離によって値が異なることに着目し，信号源を効率的に探索する手法として接近離反判定を提案
し，評価をしたものである．
本論文は，以下 6 章で構成されている．
第 1 章では，研究の背景として，アドホックネットワークが既存ネットネットワークが代替手段になりうること，要救助者とみなす信号源の探索の現状と GPS に代わる位置特定手法の必要性を述べた．その代替手段として，RSSI を用いた信号源に対して接近離反を判定することで探索すること述べたが，その問題点，接近離反の判定手法について詳述した．
第 2 章では，接近離反の判定を猶予することの効果について述べた．具体的には，連続で続く事象の確率より，連続回まで起きれば精度が保証されること，つまり，その回数まで判定を猶予することについてである．そして，判定を猶予することに対して数値解析を行った．
第 3 章では，信号源と探索者の端末 (探索端末) 間のシングルホップを対象にした探索について述べた．接近離反の判定には，RSSI の揺らぎによる，ばらつきから判定猶予回数を決定することとした．
そして，探索端末が移動しながら等間隔毎に RSSI を測定し，較正を行うことで，探索の精度および判定の精度の向上をはかった．シミュレーションの対象は，自由区間モデルを疑似する無線伝搬モデ
ルにホワイトノイズを加えるシャドーイングモデルを採用した．測定値のばらつきには，32 , 62 , 92 ,122 [dB] を設定し，それぞれシミュレーションを行った．
計算機シミュレーションで検証を行い，探索の精度は較正を施さない RSSI での結果より 1.67 倍精度が高いことを確認した．そして，迂回率の比較で，RSSI の較正を施してない場合は RSSI の較正を施した場合と比べて最大 3.63 倍の差であった．さらに，RSSI の較正を施さず，かつ，判定猶予回数を用いない場合は RSSI の較正を施し，判定猶予回数を用いた場合と比べて最大で 7.68 倍の差があった．これは，接近離反の判定猶予することが有効的に働いているためであり，探索が広範囲に及ばずに済んだため，迂回率は抑えることができた．また，接近離反の判定を猶予することで移動距離がかさむことが判定精度とトレードオフの関係にあることがわかった．しかし，本手法は測定した RSSIの較正を行う為に，手法が複雑化し，手間がかかる．そのため，より簡単に，RSSI の測定値だけで行える手法が期待されると結した．
第 4 章は，第 3 章同様にシングルホップを対象にした探索について述べた．接近離反の判定には，
統計的仮説検定より判定猶予回数を算出した値を用いた．本節中で 2 通りの判定猶予回数を提案している．その手法は，手法 1) 接近か離反の確率モデルと測定地点ごとの RSSI からの標準偏差を用いた
判定猶予回数，手法 2) N 段のリセット計数器から N に到達するまでの確率母関数 QN (Z) から算出
した判定猶予回数，である．それぞれのシミュレーションを行い，誤判定率と迂回率の 2 つを利用して検証を行った．
シミュレーションの対象は，第 3 章同様の無線伝搬モデルと同様のもの用い，危険率 α に 0.01, 0.05,

0.1 としした．その結果，両手法で誤判定率は判定の猶予を行った場合は 0.25 以下であったに対し，判定の猶予を行わない場合はおよそ 0.5 で，およそ 2 倍であった．迂回率は，判定の猶予を行わなかった場合で探索が計算機シミュレーションにおける最大ステップ回数 (s max) 以内に終了しない場合がi

あった．つまり，判定の猶予を行った場合のほうが，広範囲に及ぶことなく探索できているためであり，判定を猶予することの有効性が確認できた．
そして，従来手法と迂回率の比較をシングルホップ接続の構成で行った．手法 1) では，従来手法の手法 1) に対する比は，およそ 1/26∼5/8 の移動距離の差があった．手法 2) では，従来手法の手法

2) に対する比は，およそ 1/10 の移動距離の差があった．このことより，提案手法は従来手法より迂回率が上回っていることから，移動距離を低減できたことが確認できた．
また，手法 2) では，固定の判定猶予回数と動的な判定猶予回数の提案をした．それぞれの結果を比較すると，α を小さくすると固定および動的な判定猶予回数の誤判定率が小さくなった．これは，

α を小さくすることで判定猶予回数が大きくなっているため，誤判定が抑制されているためであった．
つまり，動的な判定猶予回数は測定値のばらつきが小さいほど，誤判定が抑制されてないことを示している．動的な判定猶予回数は測定値のばらつきが小さい環境ほど判定猶予回数が小さくなるという特性があり，固定の判定猶予回数より小さい値が与えられているためであった．迂回率に関しては，
信号源近くで開始した探索では信号源を周回してしまう事で，迂回率を悪くしていたが，動的な判定
猶予回数が探索開始位置をに依存せずに迂回率が一定に保つための糸口になると考察した．
第 5 章では，アドホックネットワークで通信している中継端末を含む複数の端末が協調して信号源を探索する手法を検討することを目的として，複数の端末が協調して探索する組織戦略，ランダム探
索戦略と隣接端末追随探索戦略を提案してシミュレーションで評価を行った．これらの評価から得られた知見より，中継端末固定探索戦略を提案した．中継端末固定探索戦略の評価では，停止させる中
継端末の分類を行い，同様の評価および考察を行った．その結果，a) 中継端末数が増加すると，探索者の探索成功率が悪化する, b) 中継端末の探索成功率は，中継端末数が増加すると探索者に遠い端末
から探索成功率が向上していく, c) 中継端末数が 3∼6 台で，探索不正効率が最も低い, と示されたことで，中継端末数は 3∼6 台，端末間の間隔は最大で 70 [m] が最適な配置である考察して結した
第 6 章では，本研究の結論と今後の課題をまとめた．

ii

Abstract
This thesis for a degree proposed and validated the eﬃcient search algorithm of signal source
location based on Received Signal Strength Indicator (RSSI) due to that we focus on RSSI values
which are diﬀerent depending on the communication distance.
This thesis contains the six chapters as described below.
In Chapter 1, the background of the study is that ad hoc networks can be used as an alternative
to the existing networks, the current state of searching for the signal sources which are regarded
as rescuers, and the need for GPS-based location methods. As an alternative, the search forapproaching and leaving a signal source using RSSI was described, but the problem and the methodof approaching and leaving were described in detail.
Chapter 2 described the eﬀect of delaying the decision of approach and departure. Specifically,
the accuracy is guaranteed if it occurs up to consecutive times, this is based on the probability ofa continuous event, that is, the decision is deferred until that number of times. Then, a numericalanalysis was performed for delaying the decision of approach and departure.
Chapter 3 described the search for single hop between the signal source and the searcher’s terminal (search terminal). For the determination of approaching and leaving, the moratorium steps
which is the number of judgment delays is set to the variance value based on the fluctuation of
RSSI. And by what the RSSI is measured at regular intervals while the search terminal is moving
and calibrated the received RSSI, it was aimed at what the search accuracy and determination of
the search are improved.
The verification was performed by computer simulation, and it was confirmed that the search
accuracy was 1.67 times higher than that of RSSI without calibration. In the comparison of the
detour ratios, the diﬀerence was up to 3.63 times that when RSSI was calibrated when RSSI was
not calibrated. Furthermore, when the RSSI calibration was not performed and the moratorium
steps was not used, there was a maximum diﬀerence of 7.68 times compared to the case where the
RSSI calibration was performed and the moratorium steps was used.
From the simulation results, it was confirmed that the search was completed within about 2 [m]from the distance from the set signal source, and this result had less error than the result of
RSSI without any calibrations. As a result of the analysis, it was shown that it is eﬀective for themoratorium steps to delay the decision of approaching and leaving. However, it was found that there
is a trade-oﬀ between the judgment accuracy and the judgment that the moving distance increases
by delaying the judgment of approaching and leaving. Finally, we concluded that a method thatcan be performed more simply with the measured RSSI is expected because this method calibrates
the measured RSSI.
Chapter 4 describes the search for single hops as same as in Chapter 3. For the determination of
approaching and leaving, a value (the moratorium steps) obtained by calculating the moratorium
steps by statistical hypothesis test was used. The two methods in this section are 1) the moratoriumiii

steps using the probability model of approach or departure and the standard deviation from RSSI for
each measurement point, and 2) the moratorium steps calculated by the generating function QN (Z)of reaching N from the N -stage counter. Each simulation was performed, and the verification was
performed using two of the erroneous judgment rate and the detour rate.
For the simulation, the same wireless propagation model of Chapter 3 was used and the risk
factor α were set to 0.01, 0.05, and 0.1. As a result, the misjudgment rate was less than 0.25 in
the case the moratorium steps was used in both methods, whereas it was about 0.5 and about
twice in the case the moratorium steps was used. In some cases, the search was not completed
within maximum number of steps (s max) on the computer simulation ,when the moratorium steps
was used. In other words, it was possible to search without extending over a wide area when thedecision was delayed, and the eﬀectiveness of delaying the decision was confirmed.
Then, the comparison of the detour ratio with the existing method was performed in the singlehop connection configuration. In method 1), the ratio of the existing method to method 1) was
about 1/26 ∼ 5/8. In method 2), the ratio of the existing method to method 2) had a diﬀerence ofthe moving distance of about 1/10. From these results, it was confirmed that the proposed method
was able to reduce the moving distance because the detour rate was higher than the existing
method.
In method 2), fixed moratorium steps and dynamic moratorium steps were proposed. Comparing the results, the smaller the value of α, the smaller the erroneous judgment rate of the fixedand dynamic judgment delays. This is because erroneous judgments are suppressed because themoratorium steps is increased by reducing α. In other words, the smaller the RSSI variance is, theless the erroneous decision is suppressed. This is because the value of the dynamic moratorium
steps is smaller than the fixed moratorium steps because the environment where the RSSI varianceis smaller has a smaller value. Regarding the detour rate, the search started near the signal source
made the signal source go around, so we consider that the dynamic moratorium steps is a clue tokeep the detour rate constant without depending on the search start position.
In Chapter 5, the purpose of this study is to investigate a method in which multiple nodes including a relay terminal communicating in an ad hoc network cooperate to search for a signal source.
We proposed a random search strategy and a strategy of following the nearest node and evaluated them by simulation. Based on the knowledge obtained from these evaluations, we proposed a
strategy of following the fixed relay nodes.
In the evaluation of the strategy of following the fixed relay nodes, the types of relay nodes tobe stopped were classified, and similar evaluations and considerations were made. As a result,a) the search success rate of the searcher is deteriorated as the number of relay nodes increases,b) the search success rate of the relay nodes is increased from terminals far from the searcher as
the number of relay nodes increases, c) the search unsuccess rate was the lowest when the numberof relay nodes was 3 to 6. Due to this, we considered the optimal arrangement and concluded thatthe number of relay nodes was 3 to 6 and the interval between nodes was 70 [m] at the maximum.

iv

Chapter 6 summarized the conclusions of this study and future tasks.

v

目次

第 1 章 緒論

1

1.1

研究の背景

1.2

従来の位置推定手法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.2.1

Distance/angle estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.2.2

Position computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.2.3

Localization Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.3

問題定義 · 設定 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.4

研究の目的

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.4.1

目的 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.4.2

従来手法との違い . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

探索モデルの分類 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

1.5.1

目標物の特性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

1.5.2

探索者の特性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

1.5.3

探索努力の最適配分 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

1.5

1.6

本論文の構成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

第 2 章 接近離反判定の猶予

11

2.1

まえがき . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.2

接近離反の判定を猶予することの効果 . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.3

むすび . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

第 3 章 シングルホップ接続の探索手法 1: RSSI のゆらぎを判定猶予回数に利用

3.1

3.2

15

まえがき . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3.1.1

背景 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3.1.2

MANET based on IEEE 802.11b . . . . . . . . . . . . . . . . . . . . . . . . . 16

3.1.3

無線特性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3.1.4

関連研究 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.1.5

A case of the known distance . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.1.6

A case of the unknown distance . . . . . . . . . . . . . . . . . . . . . . . . . . 20

POSITION TRACKING MODEL . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2.1

RSSI Calibration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

3.2.2

Target Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

i

3.3

3.4

3.2.3

RSSI Diﬀerence Detection (RDD) . . . . . . . . . . . . . . . . . . . . . . . . 23

3.2.4

Movement Angle Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

結果 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.3.1

検討条件 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.3.2

計算機シミュレーションの結果 . . . . . . . . . . . . . . . . . . . . . . . . . . 26

むすび . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

第 4 章 シングルホップ接続の探索手法 2: 統計的仮説検定より判定猶予回数を算出

4.1

4.2

4.3

4.4

4.5

4.6

まえがき . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

4.1.1

関連研究 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

4.1.2

従来研究の問題点と課題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

4.1.3

研究の目的 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

提案手法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

4.2.1

概要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

4.2.2

接近離反判定の動作手順 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

4.2.3

判定猶予回数の設計 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

4.2.4

判定猶予回数の設計 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

探索シミュレーション . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

4.3.1

検討条件 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

4.3.2

評価指標 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

計算機シミュレーション結果 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

4.4.1

探索者の移動軌跡の例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

4.4.2

誤判定率 λ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

4.4.3

迂回率 η . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

4.4.4

比較 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

考察 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

4.5.1

接近離反判定を猶予する影響

4.5.2

判定猶予回数を動的にする効果 . . . . . . . . . . . . . . . . . . . . . . . . . . 59

. . . . . . . . . . . . . . . . . . . . . . . . . . . 58

むすび . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

第 5 章 マルチホップ接続の探索手法

5.1

5.3

61

まえがき . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

5.1.1
5.2

33

関連研究 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

複数の端末が協調した探索戦略 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

5.2.1

ランダム探索戦略 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

5.2.2

隣接端末追随探索戦略 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

複数の端末が協調して探索する計算機シミュレーション . . . . . . . . . . . . . . . . . 62

5.3.1

検討条件 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

5.3.2

シミュレーションの設定 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

ii

5.4

5.5

5.3.3

シミュレーション結果 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

5.3.4

考察 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

ランダム探索戦略と隣接端末追随探索戦略の特徴を組み合わせた探索 . . . . . . . . . 69

5.4.1

中継端末固定探索戦略 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

5.4.2

検討条件 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

5.4.3

シミュレーションの設定 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

5.4.4

シミュレーションの結果 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

5.4.5

考察 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

むすび . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

第 6 章 結論

83

謝辞

87

参考文献

94

研究業績

95

iii

第 1 章 緒論

第 1 章では，本研究を取り巻く背景とその位置付け，および本研究の目的について概説する．また，本論文の構成について説明する．

1.1

研究の背景

これまでに我が国は地震や津波により物理的な被害を受けてきた．東日本大震災では通信ビル内の設備の倒壊 · 水没 · 流失，地下ケーブルや管路等の断裂 · 損壊，電柱の倒壊，架空ケーブルの損壊，携帯電話基地局の倒壊 · 流失などにより，通信設備に甚大な被害の発生が報告されている [1]．このような自然災害時において，被災者 · 遭難者を救出するため，迅速な救助活動を行うことが重要であるが，電話やメール等の通信ができなくなると被災者 · 遭難者の情報を得ることが困難となる．
そこで，そのような状況下ではアドホックネットワークの技術 [2][3] の利用が有効であると考えられている．アドホックネットワークは，既存の通信基盤を必要とせずに無線端末同士で自律的にネッ
トワークを構築できる技術であリ，既存の通信が利用できない地域では通信確保に有力な手段となる[2][4]．アドホックネットワークの研究は，もともと移動することを対象とした軍事研究が発端であり，過酷な環境においても縦横に移動する兵士間での無線通信を可能にすることを目的とした．そして，戦場を類似した環境を想定した災害時におけるアドホックネットワークの利用が考えられるようになってきた．その具体的な利用例として，• 地震，津波，洪水，台風，竜巻が発生したときの警察や消防による捜索，救出，緊急通報，避難誘導，被害者情報の収集 · 連絡，復旧活動支援• 被災者同士の安否確認が，想定される [2]．
位置情報は重要な情報であり，捜索，救出，緊急通報，避難誘導などに利用される．その位置情報の取得には，GPS (Global Positioning System)[5] が広く利用されている．しかし，無線端末に GPSが未装備，GPS 信号が得られられないようなエリア (例として，水中や屋内など) ，GPS 信号の受信
妨害 [6][7]，などで GPS が使用できないことがある．ゆえに，無線端末の位置特定に関して GPS に代わる代替手段を必要と考える．

1.2

従来の位置推定手法

ここでは，これまでに提案されてきた従来の位置推定手法の一例を紹介する．位置推定手法は次の3 つに分類される [8]．

1• 距離/角度推定 (Distance/angle estimation):
推定する情報は，端末間の距離および/または角度．この情報は他の位置推定手法で利用される．

• 位置測定 (Position computation):
距離/角度推定や参照端末の位置が考慮された有効な情報をもとに端末の位置を計算する．

• 位置推定アルゴリズム (Localization algorithm):
端末の位置を推定するためにネットワーク内の多くのもしくは全ての端末を許容するために，どの様に操作するかを決定する．

1.2.1

Distance/angle estimation

推定する情報は，端末間の距離および/または角度になる．
位置推定で使用される主な手法は，AoA (Angle of Arrival)，ToA (Time of Arrival)，TDoA (TimeDiﬀerence of Arrival)，RSSI (Received Signal Strength Indicator) がある．

AoA (Angle of Arrival)
信号の到達角度を推定することより，位置推定を行う．AoA は，指向性アンテナもしくはアレイ
アンテナを利用して推定が行われる [9][10]．追加のハードウェアが必要であるため，費用や端末の大きさや，推定にあたり端末間にある程度の距離が必要であることがデメリットとして挙げられる．

ToA (Time of Arrival)/TDoA (Time Diﬀerence of Arrival)
ToA
送信者は信号が時刻 t1 に送信した場合，受信者は時刻 t2 に信号を受信する．送信者と受信者間の距離 d は，d = sr (t2 − t1 ) である．sr は無線信号の速度 (光速度) であり，端末間は時刻同期をする必要がある．ToA の代表例は，GPS[5] である．

TDoA
受信者が無線信号を受信した時刻 t1 , 超音波パルスを受信した時刻 t2 で受信する．送信者と受信者間の距離 d は，d = (sr − ss ) × (t2 − t1 ) である．ここで，sr ，ss は無線信号の速度，超音波パルスの速度である [11]．そして，無線信号と超音波パルスを同時に送出するためのハードウェアが必要である [12]．

RSSI (Received Signal Strength Indicator)
端末間の距離推定に用いられ，無線信号の信号強度である RSSI にもとづいている．理論的に，

RSSI は通信距離の二乗に反比例することから，既知の無線伝搬モデルから RSSI を距離に変換する．しかし，実環境ではノイズ，障害物等の影響で RSSI はノイズを含んだ値となり，距離推定に大きな影響を与える．このような場合では，較正することが一般的である [13]．本手法の利点は，一般的な端末は RSSI を測定する機能有しているため，低コストで実現できることにある．一方，ノイズや干渉に影響を受けやすく，RSSI による距離推定は不正確であるという欠点がある．文献 [14] では，通信範囲 10m で地面から 1.5m の平面に全端末が展開している前提で，2∼3m の誤差が生じる

2

ことが報告されている．このように，RSSI はシミュレーションや管理された環境下でもっともらしい結果を出しているが，実環境のアプリケーションでの使用は疑問の余地がある [15]．しかし，低コ
ストであることを考慮すると，より高度に正確な RSSI の利用が，コスト · 精度の面から使用される距離推定の技術になる実現性がある [16] が，実現に至ってない．

1.2.2

Position computation

端末距離と/もしくは角度と位置の情報がある前提で，次に説明する手法を利用して位置測定が可能である．

Trilateration and Multilateration
Trilateration (三辺測量) は基本的かつ直感的な手法である．本手法は端末の位置を 3 つの円が交差することで計算される．本手法で端末の位置を推定するためには，3 つの参照する端末の位置と互いの距離を知っておく必要がある．その距離は ToA や RSSI などが用いられる．

Multilateration (多辺測量) は，より多くの参照する端末を用いる手法である．
Bounding Box
三辺測量の円の代わりに正方形を用いる手法が，文献 [17] で提案されている．その正方形を Bound-ing Box と呼び，3 つの Bounding Box が交差する正方形の中心が，位置測定を行いたい端末の位置になる．

Triangulation[18], [19]
本手法は，距離の代わりに角度を用いる手法である．位置測定には，参照端末側で角度を計算する
か，位置測定を行いたい端末で角度を計算することの 2 通りがある．後者の場合は，最低 3 つ以上の参照端末が必要になる．AoA にもとづいた場合，参照端末との距離も導き出すことは可能である[19]．
Probabilistic Approaches
文献 [20] で，確率的アプローチが提案されている．具体的には，位置測定を行いたい端末が参照端
末からパケットを受信して，参照端末の周辺に存在することの確率を計算する．これを複数回，別々の参照端末からパケットを受信して行う．しかし，計算コストがかかることが難点である．

1.2.3

Localization Algorithm

位置推定アルゴリズムの主要な機能として，ネットワーク内の多くのもしくは全ての端末の位置推定を行うために，距離と位置を調整する情報をどの様に扱うかを決定することにある．位置推定アル
ゴリズムは，Table 1.1 のように分類できる．

Table 1.1: Category of Localization Algorithm
Category

Literature

Category

Literature

Category

Literature

Category

Literature

分散型[5][21][22]

インフラあり[21][22]

屋内用[18][23]

one hop[5][23]

中央管理型

[24]

インフラなし[5][18][23]

屋外用

[5]

multi hop[21][22]3

以下に，主な手法について述べる．

Ad Hoc Poitioning System
文献 [22] は，位置推定を行いたい端末と一緒に複数の参照端末 (Beacon を発信する端末) が構築されている multi-hop 環境で，各参照端末との距離の推定を行う．一度，距離の推定が出来れば，三辺測量で位置推定が行える．

Recursive Position Estimation
文献 [21] は，初期設定での参照端末 (全体の 5%) と地域情報 (参照端末になっている端末の情報) をもとに位置推定を行う．具体的には，1) 参照端末を決定する．2) その参照端末との距離を RSSI を利用して推定する．3) 三辺測量で位置推定を行う． 4) 位置推定できた端末は参照端末になり，付近の端末に新しく推定した位置を展開する．
本手法は，アルゴリズム開始時から急速に参照端末を増やせることが利点であるが，その参照端末との距離推定は RSSI にもとづいているため，推定エラーが発生する．つまり，1 つの端末の不正確な位置情報が他の端末の位置推定に利用されることになる．

Localization with a Moile Beacon
文献 [25] は，Beacon を発信する移動端末 (移動端末) の補助で位置推定を行う．その移動端末は自身の位置は GPS を利用して既知であり，位置推定を行いたい端末の領域を移動できることを前提に，移動しながら現在地を含んだメッセージを展開する．3 つ以上のメッセージを受信することで，

Probabilistic Approaches や RSSI を利用して推定した距離を用いることで，位置推定が行る．
本手法は，同一の移動端末より位置推定を行えることが利点であるが，位置推定エラーを低く保ち，無線伝搬エラーを防ぐことが課題である． さらに，本手法は GPS を装備した移動端末の利用が想定されている．これは，移動端末が移動できる領域であったり，効率的な移動ができているかで，位置推定に時間を要することになる．これは，移動端末は全ての端末の近くを通過できないことにも起
因する．

1.3

問題定義 · 設定

前述で記したことから，位置推定に関する課題は以下の 3 点があると考える．

• RSSI を用いる手法が低予算で実現性がある• 位置推定するために少ない台数の参照端末が望ましい• 無指向性アンテナを搭載した端末による電波到来方向推定の困難さ
RSSI を用いる手法が低予算で実現性がある
RSSI は環境によって電波の減衰特性は大きく変動するため，どのような状況でも通用する一般的な RSSI-通信距離モデルを作成することは非常に困難であり，推定する通信距離には大きな誤差が含まる．そのため，環境を考慮したモデルの較正や，予備実験によってその特性を明らかにする必要がある．

4

位置推定するために少ない台数の参照端末が望ましい
前述での手法は，複数台の参照端末が必要であることが述べられている．1 台のみのものは，文献[5] の GPS である．これは，ToA にもとづいた手法であり，GPS 衛星からの距離が計測できる．ただし，位置推定は 3 つ以上の GPS 衛星からの交点が現在位置として行われる．なお，RSSI で同様のことを行おうとすると，無線 LAN などの一般的な無線端末では，測定のための特別なハードウェ
アが必要となる．
無指向性アンテナを搭載した端末による電波到来方向推定の困難さ
電波到来方向の推定は AoA を利用することで推定が行えるが，推定を行うためのハードウェアが追加で必要になる．無指向性アンテナでの電波到来方向推定に関して，RSSI がノート PC の向きによって強度が異なることに着目した到来方向推定手法 [26] が提案されている．この手法は，事前測定した RSSI 分布のデータと，ユーザがその時点で測定した RSSI 分布のデータの類似度から電波到来方向を推定する手法である．しかし，事前測定を準備しておかなければならず，あらゆる環境に対応した情報を事前に準備しておくことは困難と考える．

1.4
1.4.1

研究の目的
目的

本研究では，位置推定を行いたい端末が発した信号を受信した端末が，その信号の RSSI を利用して探索することを検討する．RSSI は，理論的には通信距離に 2 乗に反比例することから，測定位置
により RSSI は測定値が異なる．そのため，信号源である位置推定を行いたい端末に接近できている
か，もしくは，遠ざかっていることの判定が可能である．このことを利用して，信号源位置を探索す
ることを検討する．つまり，1 台の信号源 (つまり，参照端末) の RSSI を利用することで，先に述べた課題の克服をする．
一般的な無線端末でも取得できる RSSI を利用して，RSSI が変動する環境で，無指向性アンテナ
端末の無線端末が信号源位置を探索するために判定の信頼性を向上する手法を検討する．具体的には，

IEEE 802.11 の無線端末の探索者が信号源より定期的に送信される Beacon 電波の RSSI を利用することを想定し，同一直線上を一定間隔ごとに移動しながら測定した RSSI が連続して増加変化の場合は信号源に接近していると (以後，接近) 判定，また，連続して減少変化の場合は信号源から遠ざかっていると (以後，離反) 判定し，探索する端末の移動方向を変更して，同様の探索を繰り返す．つまり，1.3 節での問題点を踏まえ，予備実験などその特性を明らかにすることなく，変動する

RSSI から接近および離反判定を行い，移動方向制御を行うことで，それぞれの課題を克服する手法の確立を目指す．以後，接近および離反の判定を接近離反判定と呼ぶこととする．
本論文では， RSSI を利用して信号源を探索するのに接近離反の判定に猶予を与える回数 (以後，判定猶予回数) を提案する．この判定猶予回数は接近離反判定の信頼性の向上と効果的に判定回数から効率的な探索に貢献すると考える．

5

1.4.2

従来手法との違い

無線通信時に得られる RSSI は，信号源からの距離が大きくなるほど小さくなり，等電界強度は円を描く．このことから，探索者が同一直線上で RSSI を等間隔に測定しながら移動することで，最大値 (極値) を見つけることができ，その地点が信号源に対して最も接近できている位置となる．これには，勾配法 (または，山登り法)[27] と呼ばれる手法が適用できる．勾配法とは，1 変数関数 f (x)の最大値を求めることで最適解が得られる手法である．具体的には，関数値をとる点に近いと思われる点 x0 を初期値として与え，f ′ (x0 )=0 ならそこで最大値をとる．f ′ (x0 ) が正なら x 軸上を右に，

f ′ (x0 ) が負なら左に進む (Fig. 1.1)．ここで重要になるのは，ステップ幅 (Fig. 1.1 の h) の進む距離であり，進み過ぎると最大値をとる点を通り過ごしてしまう．逆に，小さすぎるとなかなか最大値をとる点に到達しない．なお，進行方向の直線上で関数値が最大になる点を探すことを直線探索，その直線を探索直線と呼ぶ．
勾配法は単純であるが，極めて有効であり，最も基本的な手法として広く用いられている．しかし，極値付近の関数形によってはなかなかその点に近づけないことが起こる．これは，探索直線上で本来，最大値になるべきでない点が最大値となってしまうことで生じる (Fig. 1.2)．

Fig. 1.1: The hill-climbing of primary variable function.
そこで，本研究では，最大値でない箇所が極値になることを避けるために，判定に猶予を与える回数を検討を行う．つまり，探索直線上で連続して f ′ (x0 ) が負であれば，最大値は通り過ぎたと判断できる．この回数の最適化を図ることが，本研究の新規性になる．

不確かな情報 (例えば，環境によって変動する RSSI) から確かな情報を得ることは重要な課題である．人間の勘などに頼らず，客観的に行いたいことは大昔からの問題意識であり，過去の事例を”

6

Fig. 1.2: Do not react the extremum.
ルール”という形で蓄えることで対処されてきた．本研究は，環境によって変動する RSSI において大小関係を判定するのに最適な判定回数を提案するものであり，客観的に判定を行うことにある．

1.5

探索モデルの分類

信号源に接近すること，すなわち，信号源を探索することである．探索の観点から捉えると，信号源である目標物と信号源を探索する探索者側のそれぞれに特性がある．それぞれの特性について説明
し，本研究で扱うのもについて述べる．

探索という視点から考慮すると，探索理論を構成する要素は，以下の 2 つに分けられる．Fig. 1.3に探索モデルの分類 [28] を示す．

• 目標物の特性• 探索者の特性
これらが結合されて探索努力の最適配分問題が追及されることになる．次に，目標物の特性と探索者の特性をそれぞれ述べる．

1.5.1

目標物の特性探索モデルを構築するのに，探索者が目標物の何等かしらの情報を持っていることが前提になる．
しかし，目標物の立場では以下の 2 つが考えられる．

7

Fig. 1.3: The Search model classification.
• [two-side (競争的) ] 目標物が探索者に関する情報を持ち合わせている．探索は競争的に行われる．

• [one-side (一方的) ] 目標物が探索者に関する情報を持ち合わせていない．探索は一方的に行われる．
前者の競争的な探索は，犯人と警察官における敵 · 味方に分けられて，目標物の探索 · 発見の回避が繰り返される場合である．一方，後者の一方的な探索は，目標物は盲目 (blind) であるといえる．
本論文では，one-side (一方的) を扱う．
そして，他の目標物の特性について以下に述べる．
（1）探索空間: 離散的な空間と連続的な空間に区別される．この区別は必ずしも絶対的なものではない．本来，連続的であるはずの海域もこれに多くの升目に細分化して 1 つ 1 つの升目と区別して探索することにすれば，離散的な扱いになる．
（2）目標物の個数: 単数か複数に区別される．複数の場合，a) 相互間の位置的な関連性，b) 相互間の通信，などを考慮しなければならいため，探索が複雑になる．本論文では，単数のみを扱うこととする．
（3）目標物の現れ方: 探索空間に 1 度出現したらそのまま出現し続けるか，消滅状態 (探知不可能な状態) から出現状態 (探知可能な状態) に移り，再び消滅状態に復帰する，に区別される．本
論文では，出現を扱うこととする．

8

（4）目標物の運動: 時間経過に伴って位置の確率分布が変わるような場合，これは非停留的である．
これに反して，確率分布は時間が経過しても変化しない場合，停留的である．非停留的目標物
は移動目標物であり，停留的目標物は静止目標物である．

1.5.2

探索者の特性（1）探索者の個数: 単数か複数に区別される．
（2）投入努力の過分性: 探索努力を任意に分割する連続的な探索と，1 回の探知に要する時間，費用などの基本量を考慮する離散的な探索に区別できる1 ．本論文では離散的な探索を扱うこととする．
（3）探知情報の信憑性: 探索者が入手できる情報の質の信憑性のことであり，探索空間に雑音 (虚目標物) がある場合，情報に虚情報が混ざる場合は，雑音ありとなる．本論文では，雑音ありを扱う．
（4）探索課程: 先ず目標の概略位置の探知，そして目標物の正確な探知と多段階にわたって探索が行われることである．
なお，探索空間の離散的 (連続的) と探索の離散的 (連続的) とは異なる．離散的な探索空間を連続的な探索によって探索することもありうる．そのため，探索空間の構成法と探索努力の可分性は必ず
しも結びつかない．
探索には離散的と連続的に区別される．離散的な探索は，探索が，1 回目の探知，2 回目の探知というように，とびとびに行われる．この場合，第 i 回次での探知による条件づき探知確率を定義する
ことができる．
連続的な探索は，探索行動を区切られた各回次ごとの探知動作のつながり，とみなすことができる場合である．
以上，離散的な探索と連続的な探索についての区別を述べた．本論文では，離散的な探索を扱う．
ただし，この区別は必ずしも絶対的なものではなく，便宜上区別している．

• 時間的に連続している探知を，時間区間をさいぶんかしてとびとびの時間に行われる離散的な探知で近似する．

• 離散的な探知を平滑化連続化して連続的な探知で近似する．
など，常時行われることである．

1.5.3

探索努力の最適配分

そして，探索の計画を立てる際に計画の最適性を評価する手法を選択することに対して，• 発見確率の最大化: 手堅い探索• 発見までの所要時間の期待値の最小化: 手速い探索

9などが目標とされてきた．
また，目標物を発見することによって得られる収益 (報酬) 等，1 回の探索に要するコストを考慮して，• 期待リスク (期待費用-期待収益) の最小化
• 期待利得 (期待収益-期待費用) の最小化なども目標とされてきている．
本論文では，発見確率の最大化と発見までの所要時間の期待値の最小化 (手速い探索) と，期待リ
スク · 期待利得の最小化 (手堅い探索) について議論する．

1.6

本論文の構成

本論文は，以下 6 章で構成されている．
まず，第 2 章で接近離反の判定を猶予することについて述べる．まず，接近離反の判定を猶予する
ことの概要として，連続して続く確率の例としてコイントスを挙げ，判定することに対する効果を述
べる．第 3, 第 4 章では信号源と探索者の端末 (探索端末) 間のシングルホップ接続を対象にした探索について述べる．第 5 章では，アドホックネットワークで通信している中継端末を含む複数の端末が協調して信号源を探索する手法を検討することを目的として，複数の端末が協調して探索について述べる．第 6 章で結論とする．

10

第 2 章 接近離反判定の猶予

第 2 章では，接近離反の判定を猶予することの効果について述べる．

2.1

まえがき

連続で続く確率について検討する．例えば，コイントスで表が連続で続く確率やじゃんけんで連続で勝つ確率など，ある確率が連続で続く確率などがある．コイントスの表と裏が出る確率は，50%になり， 12 になる．1 回 1 回のコイントスはすべて独立しているため，その 1 回 1 回の確率を一定値のP0 とする．コイントスで連続 N 回まで表になる確率を Pf とすると，Pf = (P0 )N(2.1)

ここで，統計的な危険率 α を用いて，エラーが発生するという仮説を棄却することを考える．これは，途中で裏がでる確率は α だけ残るが，この危険率を一定の値に抑制することにより，連続 N 回まで表がでることの精度を保証することができる．
すなわち，(P0 )N < α(2.2)

log(α)
log(P0 )

(2.3)

より，

N>

であるから，これを満たす，最小の非負の整数値 N を求めると，連続して表がでる回数が得られる．
ここで，探索者が同一直線上を一定間隔ごとに移動しながら測定した RSSI が連続して増加もしくは減少することを考えると，RSSI の増加もしくは減少の変化が連続 N 回まで起きれば，その精度は保証されるといえる．つまり，RSSI の増加もしくは減少の変化を計測して，接近離反判定を行う
回数であり，接近離反の判定を猶予することである．

2.2

接近離反の判定を猶予することの効果

接近離反の判定を判定猶予回数まで猶予させることで，誤判定を抑制できることが期待できる．その判定猶予回数は，RSSI の増加もしくは減少の変化を計測を打ち切る基準となっているといえる．
本節では，判定報酬と誤判定によるペナルティを定義し，RSSI の増加もしくは減少の変化を計測ことから得られる利得の期待値を見積ることによって，連続して同じ事象が起こり続けるまでの期待値，
言い換えれば，何回目で計測を停止させることの打ち切り効果を検討する．

2.2.0.1

判定報酬と誤判定によるペナルティの定義

判定報酬と誤判定によるペナルティについて，以下のように仮定する．

11

• 判定報酬は，RSSI の変化が連続して同じ変化で 1 ステップ歩進するときのみを考えることとする．

• 誤判定によるペナルティは，RSSI の変化が連続して同じ変化が判定猶予回数に達する前に異なる変化が計測されることのみを考える．

• 判定に要するコストは，ここでは 1 ステップ歩進する移動コストのみを考え，簡単にするため，全ての 1 ステップ歩進する移動コストを一定値の T0 とする．

2.2.0.2

打ち切りの基準

打ち切りの基準を以下に示す．1 段歩進するコストを T0 ，連続して同変化であることへの報酬を

aT0 ，異なる変化であることへのペナルティを bT0 とする．ただし，a，b は非負の定数とする．
ここで，k(≥0) 回目の判定から判定猶予回数に達する確率を Pk として，k 回目の判定で判定猶予′回数に達しなかった場合，k + 1 回目の判定を行うことにより得られる利得の期待値 Ek+1 は，′Ek+1 = a · T0 · Pk+1 − (k + 1)T0 − b · T0 (1 −

k
∏

Pi )

(2.4)

i=1

= a · Ek+1 − (k + 1)T0 − b · T0 (1 −

k
∏

Pi )

(2.5)

i=1

と表せる．ここで定数 a，b は，任意の値をとる．Ek+1 は連続して同変化であることへの期待値であり，Ek+1 = a · T0 · Pk+1 である．
′′′

Ek+1 が判定猶予回数 N になるまでの E1 から EN までの値を計算することによって，接近離反の判定を猶予することの効果を知ることが可能である．

2.2.0.3

数値解析

打ち切りの基準を利用して，その特性を以下に示す．

k(≥0) 回目の判定から判定猶予回数に達する確率を Pk は，P0 を用いる．定数 a の値は，1 として，′b の値を 100, 20, 10 の 3 通りに変えた場合，k + 1 回目での利得の期待値 Ek+1 は，Fig. 2.1 のよ
うな結果になる．なお，b の値は，危険率 α の逆数とした．その α は，0.01，0.05，0.1 の 3 つを用いた．
′

b が 100 で k が 7 以上で Ek+1 は正の値をとる．同様に，b が 20 で k が 5 以上，b が 10 で k が 4
以上で正の値をとる．これは，これらの k 以下で接近離反の判定を打ち切ると得られる利得がないた
め，判定の精度が低いことを示している．よって，これらの k 以上で接近離反の判定を打ち切るべきであるといえる．
これらの結果より，b によって接近離反の判定を打ち切ると得られる利得が異なることが確認できる．これは，危険率 α に依存する．
判定報酬および誤判定によるペナルティを定義し，RSSI の増加もしくは減少の変化を計測ことから得られる利得の期待値を見積ることによって判定に有利な回数まで判定を継続することの効果を確
認した．

12

Fig. 2.1: The expectation value.

2.3

むすび

第 2 章では，RSSI の増加もしくは減少の変化を計測して接近離反判定を行う回数についての概念を述べた．そして，その回数の効果を判定報酬と誤判定によるペナルティを定義して検討した．
これまで，接近離反の判定を猶予することの効果について述べたが，判定を猶予すること，つまり，判定回数で打ち切る従来の手法について紹介する．
判定回数で打ち切る従来の手法に，フレーム同期の前方保護/後方保護がある．前方保護とは，同期がとれているにも関わらず，瞬時的な符号誤りによって同期が取れていないと判断し，同期を取る
ための動作が却って同期はずれを起こさないよう，n 回連続でフレームで同期がはずれていることを検出したときに判断することである．これは，前方保護 n 段と表される．後方保護とは，同期が取れていないにも関わらず，瞬時的な符号誤りにより同期が取れていると誤って判断されないよう，m 回
連続でフレームで同期が取れていることが検出したときに判断することである．これは，後方保護 m段と表される．一例として，SONET (Synchronous Optical Network)/SDH (Synchronous

Digital Hierarchy) の光ファイバー通信でフレーム同期は利用されている．そのフレーム同期保護
で，STM-1 信号などでは前方保護 5 段/後方保護 2 段となっている [29]．ここでは，何回目で計測を停止させる回数が段数として定義されている．
また，インターネットにおける情報探索で，ターゲットである探索情報が発見されない場合，ある時点で打ち切ることが必要であり，探索エラーが起こる確率を統計的に一定の率以下に抑制する探索回数を求める方式と，探索者にとって有利な探索回数を求める方式が提案されている [30]．
このように，不確かな情報から正確な情報を得るために，判定を猶予することで，より正確な情報を得ようとしている．

13

第 3 章 シングルホップ接続の探索手法 1: RSSI の
ゆらぎを判定猶予回数に利用
第 3 章では，RSSI をもとにした接近離反判定を用いた探索手法として，RSSI のゆらぎを判定猶
予回数に利用した接近離反判定手法について述べる．提案するそれぞれの判定猶予回数を利用して計算機シミュレーションで評価し，その効果を述べる．

3.1

まえがき

モバイル無線ネットワークは，インフラストラクチャありとインフラストラクチャなしの 2 種類のネットワークに分類される．インフラストラクチャを備えたネットワークにはアクセスポイント (AP:Access Point) が含れ，アクセスポイントは，基地局に相当する．無線端末は，AP を介して通信する必要がある．インフラストラクチャなしのネットワークには AP が含まれないため，無線端末同士にピアツーピアで通信し，これはアドホックネットワークと呼ばれる．
アドホックネットワークの通信は，静的と動的の 2 つのクラスにさらに細分化される．静的アド
ホックネットワークでは，ネットワークの一部に組み込まれた無線端末の位置は変わらない．一方，
モバイルアドホックネットワーク (MANET: Mobile Ad Hoc Network) と呼ばれるネットワー
クは，無線端末のみによって端末相互の通信を実現する技術であり，無線端末は新たに追加されたり，退去したり，移動する動的な環境を想定している [2]．
無線端末の位置は，MANET では不明であり，位置を検出するための技術が必要である．今日，GPS (Global Positioning System)[31] は，主に無線端末の位置を検出するために使用されている．ただし，GPS を使用できないような場合があるため，GPS を使用せずに MANET でその位置を検出する機能が必要である．

MANET は災害復旧時に効果的に展開でき，災害後の救助活動の一助になることが期待される[32]．
その手法の１つとして，MANET で RSSI に基づく距離推定を使用することが期待される．これは，屋内でのマルチパスや信号の遮断など，さまざまな原因により GPS の使用が制限されてしまうためである．とくに，GPS の代わりとして RSSI に基づく距離推定を使用して，救助活動等で探索に使用されることが期待される．

RSSI に基づく測位技術は，多くの研究者によって研究されている．これは，RSSI が多くの無線端末で標準機能となっているため，これらには追加のハードウェアは必要としないためである．そのため，端末のサイズとコストを削減することが期待できる．ただし，RSSI は非常に曖昧であり，

RSSI のみから距離を推定することは非常に困難である．
距離減衰定数 (PLE: Path Loss Exponent) は，RSSI に基づく距離推定の重要な無線パラメー

15タである．RSSI に基づく測位手法を実行する前に，その値を知っておく必要がある．PLE は最小二乗法 (LSM: Least Squares Method) またはその他の近似法を使用して推定されるが，測定と計算に時間がかかる．これは，AP を使用して PLE を推定するのに事前測定が必要であり，RSSIに基づく距離推定の弱点である．
これまでの先行研究 [33] [34] [35] では，LSM を使用して PLE を推定する方法が提案された．これらの方法は，通信距離が既知であるか，AP からの距離が近似されることで推定が行われている．
しかし，これらの仮定は非現実的である．
したがって，RSSI は非常に曖昧であるため，RSSI から距離推定を使用した探索は困難である．
これは，要救助者が救助を要請することを想定して，無線パラメータを知るために事前の測定なしで信号源を探索する手法を検討することの意義があると考える．
本研究の目的は，RSSI の大小関係を利用して，探索者の探索端末が要救助者とみなされる信号源に接近する手法を検討することである．そして，本研究のポイントは，RSSI の事前測定を行わず，較正を施した RSSI と RSSI 差分検出 (RDD :RSSI Diﬀerence Detection) を利用して信号源に接近する方法である．
較正を施した RSSI は，LSM を利用して探索端末が移動中に取得した RSSI で実行される．RDD
は RSSI の大小関係を確認するために実行し，探索端末の移動方向を変更すると判断することにも利用される．仮に判断が移動方向の変更であっても，判定猶予回数が超過するまで移動方向を維持す
る．そのために，リセット計数器が RDD に実装される．この判定猶予回数は，RSSI の変動を表す値に依存する変数である．最後に，本研究では，探索者が信号源への接近精度を二乗平均平方根誤
差 (RMSE: Root Mean Squared Error ) を利用して評価を行う．さらに，信号源に接近するまでに要した総移動距離に基づいた迂回率を利用して評価を行う．

3.1.1

背景

このセクションでは，IEEE 802.11b とその RF チャネル特性に基づいた MANET について簡単に説明する．

3.1.2

MANET based on IEEE 802.11b

MANET は，ワイヤレスで接続されたモバイル端末の自己構成インフラストラクチャレスネット
ワークである．MANET の各端末は，任意の方向に独立して自由に移動でき，他の端末へのリンクを頻繁に変更する．さらに，各端末は自身の使用とは無関係のトラフィックを転送する必要があるため，トラフィックの中継をすることも必要となる．

IEEE 802.11b ベースの探索端末間の直接通信は，共通のチャネル周波数で行われいる．基本的に，同じチャネルを選択してセットアップする必要がある．さらに MANET では，通常，アンテナが使用される全方向アンテナ (無指向性アンテナ) は，あらゆる方向のノードと通信できるためである．IEEE 802.11b 規格では合計 14 の周波数チャネルが定義されている．互いに重ならないチャ
ネルは 1，6，11，14 であり，これらは干渉なしで使用できる．ただし，使用できるチャネルは国によって異なる．

16

3.1.3無線特性

探索端末で送信される信号の電力は，探索端末間の距離に応じて異なる．ある地点での探索端末の

RSSI は，その探索端末からの信号がその地点でどれくらい強いかの指標である．

Pr (d) =Pt Gt Gr λ2(4π)2 d2

[W]

(3.1)

ここで，各パラメータは以下のように定義する．

Pr : 受信電力 (W)Pt : 送信電力 (W)Gt : 送信利得
Gr : 受信利得
λ: 波長 (m)d: 通信距離 (m)この RSSI は，自由空間モデル (FSM) としてモデル化されている．これは理想的な空間モデルであり，通信範囲を理想的な円として表している [36]．
より一般的で広く使用されているモデルは，シャドウイングモデル (SM) と呼ばれる．次のように，対数正規モデル [36] でモデル化される．

(
P L(d) = P L(d0 ) − 10γlog10

d
d0

)
+ Xσ

[dBm]

P L(d)[dBm] ∼ N (P L(d)[dBm], Xσ2 )

(3.2)
(3.3)

ここで，各パラメータは以下のように定義する．

P L: RSSI [dBm]
P L: 平均 RSSI [dBm]
d: 通信距離 [m]d0 : 参照距離 [m]γ: 距離減衰定数 (PLE)Xσ : 計測値の変動を表す値, 平均 0 のガウス分布に従うランダムな値 [dB]
Eq. (3.1) と (3.2) の無線特性を Fig. 3.1∼3.4 に示す．Eq. (3.2)(3.1)∼(3.2)(3.4) は，Xσ はそれぞれ 3∼12 [dB] である場合の特性を示している．

17

Fig. 3.1: RF specifications, Xσ =3.

Fig. 3.2: RF specifications, Xσ =6.

Fig. 3.3: RF specifications, Xσ =9.

18

Fig. 3.4: RF specifications, Xσ =12.
3.1.4

関連研究

Range − based の測位手法 [37] [22] [21] [38] は，ToA (到着時間) ，TDoA (到着時間差) ，および RSSI に基づく距離推定である．

ToA と TDoA は，距離に応じて 2 つのノード間を移動する信号の異なる時間を使用する方法である．少なくとも 3 つのノードを使用する必要があり，ノード間の時間の同期が必要である．GPSは同じ概念である．RSS は，距離減衰効果を使用する方法である．少なくとも 3 つのノードを使用する必要がある．RSSI で距離を計算するには，環境内の距離減衰のモデリングが必要である．さらに，AoA (到来角) を使用した測位手法では，受信信号の方向を利用する．少なくとも 2 つのノードを使用する必要があるが，方向を推定するには指向性アンテナが必要であり，コストは他の ToA，

TDoA，および RSSI よりも高価である．Range − f ree の測位手法 [39] [40] [15] [25] は，ランドマークまたはアンカーノードなど，位置がわかっている 1 つのノードを利用する方法である．位置は，アンカーノードまでの距離とホップ数により推定される．PLE 推定 [33] [34] [35] を使用した

Range − f ree の測位手法は，RSSI から計算される距離推定を利用する方法である．PLE 推定により，距離推定はより正確になる．PLE 推定による距離推定の一般的な概念を Fig. 3.5 に示す．

3.1.5

A case of the known distance

例として，探索端末間の距離が既知の場合，測定された RSSI を Eq. (3.2) に当てはめる．そこで，これらの測定データを直線の方程式 y = ax + b に変換し，PLE はこれらの測定データと LSMによって推定される．

1∑(yi − (axi + b))2 → min
2
N

J=

i=1

ここで，Eq. (3.2) より各パラメータは以下のように定義する．

xi : log10 (d)yi : P L

19

(3.4)

Fig. 3.5: General concept of PLE estimation by using LSM.
a: 10γb: P L(d0 )ただし，d0 =1m のため，b は定数である．その故，a のみ推定を行う．

∑Nxi
i=1 xi yi − b∑N 2 i=1
i=1 xi

∑N
a=

(3.5)

これより，PLE は Eq. (3.5) より推定できる．

3.1.6

A case of the unknown distance

おおよその距離が決定することで，未知の距離の問題が解決される．実際，8m x 8m のフィール
ドに 16 個の固定端末が設定され，すべての局の高さが 2．8m であり，各局が 4 x 4 の網状パター
ンで各 2m 間隔で設定する．
次のようにして距離は概算される．
（1）ターゲット端末の高さを設定する．ターゲット端末の高さは不明だが，おおよその高さを推定
する．
（2）最大 RSSI を取得する固定端末の検索する．ターゲット端末はこの固定端末に近いと推定できる．
（3）座標での距離を参照する．距離は，見つかった固定端末の座標から概算される．
これ故，3.1.5 節で述べたように，PLE は LSM によって推定される．これより，通信距離が推定できることになる．

20

3.2

POSITION TRACKING MODEL

Fig. 3.6 に想定する状況を示す．想定モデルを簡単にするために，信号源は静止していると仮定する．この信号源は，被災者を想定する探索端末とする．そして，信号源の位置が不明な場合，提案されたモデルを使用することで信号源に接近できることを検討する．本節では，RSSI に基づいて信号源を探索する方法を提案する．ただし，取得した RSSI には環境依存して大きく変動するため，

RSSI の較正が重要となる．提案する手法は，信号源と探索端末間の距離を想定するための事前測定は行わない．探索端末は RSSI と自身の移動距離を利用して，RSSI を較正を行う．
前提条件として，探索端末は• RSSI が取得できること，• RSSI を連続的に測定して保持できること．
• 移動方向を制御することができること (角度が与えられた場合の方向の変化を意味する)．
とする．

Fig. 3.6: Typical situation.
本モデルでは較正を施した RSSI と RSSI の比較の 2 つの要素に分けられる．較正を施した RSSI
では，移動中に LSM を使用して RSSI が較正される．この RSSI は，信号源を探索するために RSSIの比較要素で移動方向を制御するために使用される．本モデルの概要を Fig. 3.7 に各モデルの要素ごと詳述する．
（1）ランダムな方向に移動する．
（2）移動距離は，移動角度 (θmoving angle =π/2) より決定する．信号源までの仮距離 (r) は γ = 2 とする．これは，移動距離は θmoving angle ·r で決定される．
（3） P̂ は Eq. (3.8) より決定する．移動中に RSSI の平均化 (Ave.) を行い，Xσ2 [dB] は測定値のばらつきを表す値 (σ 2 ) を決定する．

21

（4） Eq. (3.9) で true が reset counter 回以上か以内かを確認する．
（5）探索者の位置が信号源から閾値距離以内か確認する．

(a) 閾値距離以内の場合は探索を終了する．
(b) 閾値距離以外の場合は探索を続行する．
（6）移動方向制御量 (θ) を決定する．
（7）移動方向を変更する．
（8） 2) に戻る．

Fig. 3.7: Host approaching model.

3.2.1

RSSI Calibration

探索端末は，アドホックモードで信号源と相互に通信をする．信号源は移動しないと想定する．探索端末は直線的に移動し，移動距離を測定できるものとする．そして，探索端末は RSSI の取得ができるものとする．Fig. 3.8 に示す各範囲 [a，b] の RSSI のばらつきを求める．各範囲 [a，b] における測定値のばらつきを表す値は，σ 2 として定義される．RSSI は，移動中に LSM を使用して調整される．とくに，各範囲 [a，b] には 3 つのポイントがあり，ポイント間の距離は探索端末の移動距離を意味するステップとして定義され，デファルト値として 1 m に設定される．
そのため，Eq. 3.4 などの曲線近似手法の LSM を使用して，RSSI を較正を行う．次に，a と bは次のように計算される．

a=

N

∑N

i=1 xi yi −

N
∑N
b=

2
i=1 xiN∑N

i=1 xi∑N

i=1 yi

∑N

(∑

)2

∑N

∑N

∑N

∑N

(∑

2
i=1 xi −i=1 yi −2
i=1 xi −N
i=1 xii=1 xi yiN
i=1 xi)2

i=1 xi

(3.6)

(3.7)

ここで，N は測定回数であり，探索端末が方向を変えるまでは step 数にあたる．そして，yi は

RSSI，xi は log10(stepi + 1) である．較正する RSSI は，P̄ として次のように定義する．

P̂i = b + aN∑log10 (stepi + 1)

(3.8)

i=1

RSSI の較正は Eq. (3.8) からの各ステップで調整できる．そして，P̂ については，3.2.3 節で説
明する．

22

Fig. 3.8: Variance of RSSI readings at each range [a, b].
3.2.2

Target Detection

距離は，接近が完了したかどうかを検出するために使用する．本研究では閾値距離を簡単にするために，γ が 4 のときに信号源から 5m の距離を-61．389 [dBm] に設定する．距離が P̂ − σ より大きい場合，探索は終了とし探索端末は信号源から 5m 以内の距離に接近できたことを意味する．従って，閾値距離が 5 m に設定される理由は次のの 2 つである．1) 探索端末が信号源に視覚的に近づくことができる距離であること．2) ステップ幅が 1 m であるため，信号源までの閉値域を考慮しないためである．

3.2.3

RSSI Diﬀerence Detection (RDD)ˆ の間で大小を比較を行う．RDD はRSSI 差分検出 (RDD) は，Eq. (3.9) を利用して P̂i と Pi−1
Eq. (3.9) に基づいて実施され，その概念を Fig. 3.9 に示す．Eq. (3.9) で true の場合，方向の変更が必要であると判断することする．

ˆ + 3σi−1
P̂i − 3σi < Pi−1

(3.9)

リセット計数器は，判定猶予回数を超過するまで移動方向を維持するために実装される．Eq. (3.9)
が最初に真になるのは位置 b ではなく，Fig. 3.10 に示すように位置 b から直線的に前進し続ける位′

置 b で方向の変更を実行する．判定猶予回数 N は次のように決定する．

N=√
Ave(σ 2 ) · σi(3.10)

N は変数であり，その値は Xσ に依存する．したがって，N は Xσ が小さいほど小さく，Xσ が大き
いほど大きくなる．そのような理由から，RSSI の大きい変動に起因する移動方向制御の誤判定を抑制できる．ただし，RSSI が閾値 (Threshold) + (-15) [dBm] 以下の場合，N は 5 に設定される．
これは，探索端末は信号源に近づき，見落とさないように信号源に向かって細かく移動する必要があ
るためである．

23ˆ with using the variance.
Fig. 3.9: Compare large and small between P̂i and Pi−1

Fig. 3.10: The reset counter and change the direction.

24

3.2.4

Movement Angle Control

移動方向制御量 (θ) は，取得および較正された RSSI に応じて決定させる．θ は次のように決定する．

Pri ≥ Pri−1andˆ ≥ Pi−1ˆ → θ = 0◦
Pi−1

(3.11)Pri ≤ Pri−1andˆ ≤ Pi−1ˆ → θ = 90◦
Pi−1(3.12)Pri ≥ Pri−1andˆ ≤ Pi−1ˆ → θ = 45◦
Pi−1(3.13)Pri ≤ Pri−1andˆ ≥ Pi−1ˆ → θ = 45◦
Pi−1(3.14)

ただし，Eq. (3.12) が 5 回目検出したときは，θ = 60◦とする．

移動方向制御量 (θ) は，Eq. (3.11)， (3.12)， (3.13)， (3.14) に基づいて変更する．Eq. (3.11) より信号源へ接近していると検出する．Eq. (3.12) より信号源検出から離反していると検出する．

Eq. (3.14)， (3.14) では，取得および較正された RSSI の変動が異なり，移動方向制御量はEq. (3.11)， (3.12) の間の半分の角度とする．

3.3

結果

C ++ (Microsoft Studio C ++ 2010) で記述された計算機シミュレーションを使用して，提案されたモデルを精度の観点と有用性の観点から評価した．

3.3.1

検討条件

表 3.1 に計算機シミュレーションで用いるパラメータ諸元を示す．

Table 3.1: Simulation Specifications.
Parameters

Values

Unit

Wavelength

0.125 ( = 2.4 GHz)[m]

Transmitted power

10

[mW]

Antenna gain

1.0 (transmitting/receiving)-Radio propagation model

Shadowing model-

Received Signal Strength Pr(d0 )-33.425109 (d0 =1 m)[dBm]

Threshold-61/389 (5 m from target station)[dBm]

Eﬀective measuring range

Max -200[dBm]

Path loss exponent， γ

4-Shadowing deviation， Xσ

3, 6, 9, 12[dB]

計算機シミュレーションは，2 次元平面上での探索を想定する．そして，2 次元直交座標の位置より探索を開始する (Table 3.2)．各移動開始地点ごとに 100 回のシミレーションを表 3.1 の各 Xσ 毎に試行する．信号源は (x，y) = (0，0) で静止している．

25

Table 3.2: Starting positions of searcher.
Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9Test10

x [m]

100

90

80

70

60

50

40

30

20

10

y [m]

100

90

80

70

60

50

40

30

20

10

3.3.2
3.3.2.1

計算機シミュレーションの結果
精度

探索端末が信号源へ接近できて探索が終了できているかを検証する．その評価には，探索端末が閾
値距離内に位置したときの位置 xˆn ，yˆn (つまり，探索を終了したとき) ，信号源の位置 xn ，yn の誤差の大きさを示す二乗平均平方根誤差 (RMSE) (Eq. (3.15)) を用いた．
v
u
N [
]
u1 ∑
t
RM SE =
(xˆn − xn )2 + (yˆn − yn )2N(3.15)

n=1

較正を施した RSSI を使用した場合の信号源への接近精度を Fig. 3.11，較正を施さない RSSI を使用しない場合の信号源への接近精度を Fig. 3.12，そして，較正を施さない RSSI を使用せず，かつ，判定猶予回数なしの信号源への接近精度を Fig. 3.13 にそれぞれ示した．図中で，横軸は移動開始地点と信号源の距離 [m] ，縦軸は RMSE [m] を表す．

Table 3.3 に，較正を施さない RSSI を使用しない場合の RMSE に較正を施した RSSI を使用した場合の RMSE に対する比を示した．これより，較正を施した RSSI の結果は，Xσ が大きい環
境で較正を施さなかった場合と比べて最大で 1.67 倍精度が高いことが確認できる．

Fig. 3.11: RMSE with Calibration.

3.3.2.2

RSSI の較正

本節では，P̂ の較正の度合いについて検証するため，Pr と比較して確認する．Fig. 3.14 に Fig. 3.11で Xσ が 12 [dB] での Pr ，P̂ の一例を示す．そして，比較のため理想空間 (Xσ =0) の Pr も同図に示

26

Fig. 3.12: RMSE without Calibration.

Fig. 3.13: RMSE without Calibration and N =1.

27

Table 3.3: Ratio of ”RMSE with Calibration” to ”RMSE without Calibration”.
Distance between thestarting point and TN

Xσ [dB]

Coordinate

Distance [m]

3

6

9

12

{10, 10}

14.14

0.99

1.01

1.29

1.58

{20, 20}

28.28

0.99

1.03

1.21

1.45

{30, 30}

42.43

0.99

1.07

1.16

1.52

{40, 40}

56.57

1.00

1.03

1.18

1.65

{50, 50}

70.71

1.02

1.01

1.20

1.67

{60, 60}

84.85

0.98

1.04

1.29

1.53

{70, 70}

98.99

1.00

1.00

1.13

1.51

{80, 80}

113.14

1.00

1.02

1.09

1.46

{90, 90}127.28

1.02

0.99

1.01

1.45

{100, 100}

141.42

1.00

1.00

1.03

1.60

す．図中で，横軸は移動開始地点と信号源の距離 [m] ，縦軸は RSSI [dBm] である．結果は，Pr が効果的に較正され，Xσ =0 の場合に RSSI の値に近づいたことがわかる．

Fig. 3.14: An example of RSSI readings.

3.3.2.3

迂回率

提案手法が信号源に接近することの効率性について，迂回率をもとに検証を行う．迂回率は，判定
猶予回数を大きくすれば誤判定率はよくなるが，探索者の移動距離は長くなる．探索者が信号源に効率的に探索できているかの指標である．

28

迂回率 (η) は，以下のように定義する．

η=
探索に要した移動距離
移動開始地点と信号源までの直線距離(3.16)

較正を施した RSSI を使用した場合の迂回率を Fig. 3.15，較正を施さない RSSI を使用しない場
合の迂回率を Fig. 3.16，そして，較正を施さない RSSI を使用せず，かつ，判定猶予回数なしの迂回率を Fig. 3.17 にそれぞれ示した．図中で，横軸は移動開始地点と信号源の距離 [m] ，縦軸は η である．ただし，探索が limax 以内で探索が終了しなかった結果は除いてある．

Fig. 3.15: The ratio of detour with Calibration.

Fig. 3.16: The ratio of detour without Calibration.
Table 3.4 に，Fig. 3.16 の Fig. 3.15 に対する比を示した．これより，較正を施した RSSI を使用した場合は較正を施さない RSSI を使用しない場合と比べて，最大で 3.63 倍の移動距離の差が29

Fig. 3.17: The ratio of detour without Calibration and N =1.
あった．逆に，較正を施さない RSSI を使用しない場合が上回った結果では，最大で 0.70 倍の移動
距離の差で大きな差はなかった．これらの結果より，較正を施したことで，広範囲に及ぶことなく探索ができているといえる．

Table 3.5 は，Fig. 3.17 の Fig. 3.15 に対する比を示した．これより，較正を施した RSSI を使用した場合は較正を施さない RSSI を使用し，かつ，判定猶予回数を用いない場合と比べて，最大で 7.68 倍の移動距離の差があった．較正を施さない RSSI を使用せず，かつ，判定猶予回数を用いてない場合が上回った結果では，最大で 0.54 倍の移動距離の差であった．これは，Xσ =12 [dB] で{10,10} から探索を開始した場合であった．判定猶予回数が大きな値になってしまうことで，判定まで距離がかさんでしまっていることが起因している．しかし，RSSI の較正を施し，かつ，判定を猶予することで誤判定が抑制され，広範囲に及ぶことなく探索ができたといえる．
これらの結果より，Fig 3.15 の結果が他の結果より効率よく探索できていることを示している．特に，Fig 3.16 と Fig 3.17 の結果で，判定猶予回数の効果が出ていることがわかる．これは，接近離反の判定を猶予しないことで，誤判定が生じ，移動距離が長くなっていしまっているためである．

3.4

むすび

RSSI を利用して信号源に接近するための手法を提案した．その手法は，通信距離を推定を行わず，
RSSI モデル (Eq. (3.2)) のパラメータ (γ) の推定のための事前測定を必要としない．探索端末は同一直線上を移動しながら，等間隔毎に信号源からの RSSI の測定を行う．測定した RSSI を逐次較正を行いながら，RSSI の大小関係から信号源に対して接近離反の判定を行い，移動方向制御を行うこととした．その手法の評価は，1) 探索端末が信号源へ接近できて探索が終了できているか，2) 移動開始地点での信号源との距離に対する移動距離の比である迂回率，の 2 つで行った．信号源から

5 [m] の距離内に位置できたことで探索終了とみなし，およそ 2 [m] の誤差範囲で接近できていることが確認できた．較正を施さない RSSI の場合は，Xσ が 12 [dB] のときでおよそ 4 [m] であった．
これは接近離反の判定を猶予する場合の結果も同様であった．このことは，RSSI の較正と判定に猶30

Table 3.4: Ratio of ”with Calibration” to ”without Calibration”.
Distance between thestarting point and TN

Xσ [dB]

Coordinate

Distance [m]

3

6

9

12

{10, 10}

14.14

0.70

1.15

1.32

1.76

{20, 20}

28.28

1.12

1.26

1.27

2.89

{30, 30}

42.43

0.97

1.24

2.11

2.08

{40, 40}

56.57

1.08

1.25

1.68

4.48

{50, 50}

70.71

1.08

1.25

1.68

4.48

{60, 60}

84.85

1.21

1.38

1.89

3.63

{70, 70}

98.99

1.06

1.45

1.99

1.91

{80, 80}

113.14

1.13

1.43

1.82

2.08

{90, 90}127.28

1.21

1.27

1.74

2.23

{100, 100}

141.42

1.27

1.62

1.55

3.46

Table 3.5: Ratio of ”with Calibration” to ”without Calibration and N=1”.
Distance between theXσ [dB]

starting point and TN
Coordinate

Distance [m]

3

6

9

12

{10, 10}

14.14

0.70

0.61

0.55

0.54

{20, 20}

28.28

0.98

1.36

1.57

2.69

{30, 30}

42.43

1.64

2.42

3.01

4.00

{40, 40}

56.57

1.86

3.76

4.35

4.65

{50, 50}

70.71

2.45

4.46

6.55

5.46

{60, 60}

84.85

2.77

6.25

5.82

7.19

{70, 70}

98.99

2.46

5.30

5.94

7.16

{80, 80}

113.14

2.86

5.31

7.74

7.68

{90, 90}127.28

2.95

5.57

6.60

7.14

{100, 100}

141.42

2.88

6.51

4.57

7.25

31

予することが有効的であることを示している．
さらに，迂回率 (η) は移動開始地点がおよそ 60 [m] までほぼ一定であったが，移動開始地点が信号源に近づくほど η は大きくなっていることを確認した．これは，判定猶予回数が関与していると考えらる．信号源付近で接近離反の判定を猶予されてしまっているため，移動距離がかさんでしまっているためであると考える．
本節では，較正した RSSI を利用して，その RSSI の大小関係より信号源に対して接近離反を判定を行うことで，信号源の探索を行った．しかし，RSSI を較正せずに，RSSI の大小関係より信号源に対して接近離反を判定を行うことで，より簡単に，測定値だけで行うことができる．ゆえに，RSSIの測定値だけで信号源に対して接近離反の判定を行って探索を行うことが期待される．
本研究は，文献 [41] で発表したものをまとめたものである．

32

第 4 章 シングルホップ接続の探索手法 2: 統計的仮説検定より判定猶予回数を算出
第 4 章では，RSSI をもとにした接近離反判定を用いた探索手法として，統計的仮説検定より判定
猶予回数を算出した接近離反判定手法について述べる．提案するそれぞれの判定猶予回数を利用して計算機シミュレーションで評価し，その効果を述べる．

4.1

まえがき

近年，情報通信ネットワークは欠くことのできない社会インフラとなっている．しかし，災害時には停電や設備破壊，アクセス集中等により，情報通信ネットワークの確保自体が困難となる状況が発生している．そのような状況での代替通信手段として，アドホックネットワークの通信の活用が想定される [4]．
アドホックネットワークの通信は既存の通信基盤を必要とせずに無線端末同士で自律的にネットワークを構築できる技術である [3]．そのアドホックネットワークの通信を利用し要救助者からの救助要請が考えられる. しかし，位置情報が不足する場合，救助は困難となる．その簡単な解決策として，無線端末に GPS を装備することが挙げられる．しかし，無線端末の GPS 未装備，GPS 信号が得られないようなエリア (例として，水中や屋内など)，敵対者による GPS 信号の受信妨害 [6]，などで GPS が使用できないことがある．故に無線端末の位置特定に関して GPS に代わる代替手段が必要と考える．

4.1.1

関連研究

GPS を用いない既存の位置推定アルゴリズムは，range-based と range-free の 2 つに分けられる．
range-based 位置推定は，AoA (Angle of Arrival)，ToA (Time of Arrival)，TDoA (TimeDiﬀerence of Arrival)，RSSI (Received Signal Strength Indicator)[42]–[44] などを利用する手法である．位置推定をしたい端末は，位置が明らかな端末からの無線信号 (Beacon 電波) を用
いて，三角測量，三辺測量や，多辺測量を利用する．range-free 位置推定は，ホップ数などのネットワークのトポロジー情報を利用する手法 [43], [44] である．

AoA，ToA，TDoA の位置推定は追加のハードウェアが必要であったり，参照する端末同士が時刻同期していることが必要であったりする．一方，RSSI は一般的な無線端末でも取得できる指標であり，しばしば通信距離推定に利用されてきた．
また，これまでに Beacon 電波を利用した最適な経路探索のアルゴリズムが多く検討されてきた．
それは，目標の端末 (例えば，センサー端末) を探索するために，探索する端末の探索経路を決定す
る経路計画である．経路計画には，あらかじめ決められた経路を移動する静的経路計画と移動しなが33

ら経路を決定する動的経路計画がある [43], [44]．
静的経路計画は SCAN[45]，HILBERT[45]，CIRCLES[46]，S-CURVES[46] が提案されており，位置推定に RSSI が利用されている．しかし，静的経路計画は信号源が予測領域内に存在することを前提としているため，その前提が異なる場合，静的経路計画では信号源の位置特定が行えないことになる．
動的経路計画では RSSI を用いた Adaptive Path Planning (APP)[47]，DeteRministic dy-

namic bEAcon Mobility Scheduling (DREAMS)[48] や Arrival and Departure Overlap (ADO)[49] がある．APP はセンサノードをランダムに配置した場合の移動経路長と移動体からの Beacon 電波のメッセージ数を考慮した経路計画を提案している．移動端末は，未知のセンサノー
ドから受信した要求メッセージを分析しながら次の目的地を決定する．センサノード間およびセンサ
ノードと移動端末間の距離は，RSSI から推定している．DREAMS は，ヒューリスティック (発見的) に未知の端末を訪問し，その端末から中継する端末を経由して目標の端末までの移動経路をグラ
フ上の探索手法である Depth-First Traversal (DFT) を用いて決定する．未知の端末を訪問するために，各計測地点ごとの RSSI より通信距離を算出し，比較しながらヒューリスティックな移動をする．ADO は，計測地点ごとの RSSI の変化を利用する方法である．この場合，探索者は同一直線上を移動し，目標の端末からの Beacon 電波を一定間隔ごとに受信することで，RSSI が最も大きく受信できた地点から，進行方向に対する目標の端末の位置を推定を行う．
これら RSSI を利用している 3 つの提案で，RSSI は環境によって電波の減衰特性が大きく変動する [36] ことが考慮されていない．

4.1.2

従来研究の問題点と課題

RSSI は環境によって電波の減衰特性が大きく変動するため，どのような状況でも通用する一般的な RSSI-通信距離モデルを作成することは非常に困難であり，推定する通信距離には大きな誤差が含まれる．そのため，環境を考慮したモデルの校正や，予備実験などでその特性を明らかにする必要がある．RSSI が通信距離に応じて変化することを利用して，信号源に接近していることを判定する
のに，環境によって RSSI が変動するため誤判定してしまう課題がある．また，一般的な無線端末では無指向性アンテナを用いているため，位置推定精度が悪く [50]，経路探索に比較的多くの時間を要する，という問題がある．

4.1.3

研究の目的

一般的な無線端末でも取得できる RSSI を用いて，無指向性アンテナの無線端末が RSSI の表示が可能であることを前提に，RSSI が変動する環境で，信号源位置を効率よく探索することを検討する．
上記目標を実現するために，信号源に対して接近していること，もしくは遠ざかっていることの判定の信頼度を向上させる手法を確立する．具体的には，IEEE 802.11 の無線端末の探索者が信号源より定期的に送信される Beacon 電波の RSSI を利用することを想定し，同一直線上を一定間隔ごとに移動しながら計測した RSSI が連続して増加の場合は信号源に接近していると (以後，接近) 判定する．また，連続して減少の場合は信号源から遠ざかっていると (以後，離反) 判定し，探索する端末の移動方向を制御して，同様の探索を繰り返す．つまり，4.1.2 節での問題点を踏まえ，予備実験などでその特性を明らかにすることなく，変動する RSSI から接近および離反判定を行い，移動方向

34

制御を行うことで，それぞれの課題を克服する手法の確立を目的としている．以後，接近および離反の判定を接近離反判定と呼ぶこととする．
本稿では，移動方向制御のために，一回の RSSI 計測ではなく，連続した複数の RSSI 計測を利用して，判定に時間的猶予を与える方式を検討する．その判定のために RSSI 計測回数を判定猶予回数と呼ぶこととする．この判定猶予回数は接近離反判定の信頼性の向上と誤判定回数を減らせることにより効率的な探索に貢献すると考える．
判定猶予回数の設計は，以下の 2 通りで検討する．
（1） 1 段進むたびに増加もしくは減少の 0.5 の確率として，RSSI の変化が連続で続く確率から判
定猶予回数の設計する．
（2） TTC 標準 JT-G707 のフレーム同期はずれ検出手法 JTG-707 から判定猶予回数の設計する．
これは，本来のフレーム同期信号なのか，偶然一致しただけなのかを識別するため，連続する数フレームにわたってパターンが一致したとき初めて同期はずれとみなす技術である．
すなわち，RSSI が一貫性を持って連続して変化したときに，接近離反の判定を下す．その判定猶予
回数を以下の評価指標を用いて計算機シミュレーションで評価する．

• 誤判定率: 接近もしくは離反の判定が誤判定した割合を示す指標で，接近離反の判定を判定猶
予回数分猶予することの信頼性を計る指標．以下の最適性の基準 (1 章の Fig. 1.3) にあたる．

– 期待リスク · 期待利得の最小化 (手堅い探索)• 迂回率: 判定猶予回数を大きくすれば誤判定率はよくなるが，探索者の移動距離は長くなる．探索者が信号源に効率的に探索できているかを計る指標．以下の最適性の基準 (1 章の Fig. 1.3) にあたる．

– 発見確率の最大化と発見までの所要時間の期待値の最小化 (手速い探索)
計算機シミュレーションでは，RSSI に変動を与えることで，接近離反の判定を判定猶予回数分猶予することの信頼性と探索者が信号源に効率的な探索ができているかを検証する．さらに，同一地点で複数回のサンプリングを行い，平均化を行った RSSI を用いて接近離反の判定を判定猶予回数分猶予しない探索との比較を行うことで，提案手法の有効性の検証を行う．
本稿ではこのような検討の端緒として，提案手法の有効性を大まかに検証するため，比較的簡易な環境を想定する．すなわち，(1) 2 次元の平面で，(2) 障害物によって経路が制約されない，(3) 単
一の端末間で直接通信が可能な場合を取り扱うこととする．

4.2

提案手法

4.2.1

概要

RSSI が変動する環境で，通信距離推定を行わず，計測地点によって RSSI が異なることに着目し，信号源位置を効率よく探索することを検討する．その実現のために，信号源に対して接近離反判定の信頼度を向上させる手法を確立する．

35

判定に猶予を設けるとは，計測された RSSI から接近離反を直ちには判定せず，現在の移動を維持して計測を数回繰り返し，RSSI が一貫して変化することを確認して接近離反判定することを指す．
すなわち，接近および離反の誤判定を抑制し，望ましい移動方向を制御する機能のことである．探索者が信号源から Beacon 電波の RSSI を直線上に一定間隔ごとに計測し，RSSI の増加と減少の連続回数を計数するために N 段のリセット計数器 [51], [52] を用いる．その計数値がリセットされた状態から N 回 (以後，この回数のことを判定猶予回数とする) に到達した場合には，接近もしくは離反と判定し，移動方向制御を行う．つまり，接近と判定された場合は移動方向を変更しないが，離反と判定された場合は移動方向 (時計周り/反時計回りのいずれか一方に固定とする) を変更する．変更
方向を一方に固定することで，信号源へ螺旋を描くような軌跡になる．螺旋型の探索は目標の端末に遭遇する確率が最大になる経路であり，移動しやすい経路で近似できるという理由から，離反と判定された場合の移動方向制御量を π/2 とする [28]．
前提として，探索者と信号源は，アドホックネットワークの通信に対応し，無指向性のアンテナを装備していることとする．探索者は，• RSSI の計測ができる• 移動した距離の計測ができる• 移動方向の制御ができることとして，探索エリアを 2 次元直交座標系で検討を行うこととする．

4.2.2

接近離反判定の動作手順

本節では，RSSI を用いた接近離反判定の動作例を Fig. 4.1 を用いて述べる．同図において，自由空間モデル [53] を仮定すると，信号源からの距離が大きくなるほど RSSI は小さくなり，等電界
強度は円を描く．このことを前提に，以下に動作例を述べる．
ここで，Signal Source は信号源であり，Searcher が探索者である．探索者は地点 a から地点 d の方向へ直線上を移動する．移動開始時の地点 a での RSSI を基準値とする．以後，基準値の RSSI を
比較基準値 (Refrssi ) と呼ぶこととする．そして，一定間隔 (ステップ幅，sw) ごとに RSSI を計測しながら移動し，その RSSI (Ri ) と Refrssi との大小関係を比較する．Ri が Refrssi と比べて増加の時，リセット計数器の計数値 (CTI ) を 1 つ増加させる．そして，CTI が判定猶予回数 (N ) 回に地
点 b で到達した時，接近と判定する．Refrssi を計測区間 [ab] で計測した最小の RSSI に更新し，CTIを 0 にリセットする．Ri が Refrssi と比べて減少の場合，CTD を 1 つ増加させる．CTD が N 回に地点 c で到達した場合，離反と判定する．Refrssi を計測区間 [bc] で計測した最小の RSSI に更新し，CTD を 0 にリセットする．そして，移動方向制御量 (m angle) だけ移動方向を変更する．この場合，
移動方向は d から e に変更される．仮に，CTI が N 回に到達する前に，CTD を 1 つ増加になった場
合，CTI を 0 にリセットさせる．そして，探索者が信号源から所定の閾値距離 (r src) 以内に到達した場合，探索を終了とする．また，計算機シミュレーションは移動距離を無制限にしないため 1 試行
でステップできる最大ステップ回数 (s max) を設定する．Table 4.1 に使用する記号を示す． 以下に，本稿において提案する手法は次のステップからなる．

Step 1 探索者は信号源の計測地点 i で RSSI (Ri ) を 1 回計測する．

36

Fig. 4.1: An example of approach/departure judgment.
Step 2 移動開始時の Ri を比較基準値 (Refrssi ) とする．
Step 3 判定猶予回数 (N ) を設定する．
Step 4 探索者が信号源から r src 以内に位置した場合，探索終了とする．
Step 5 Ri を Refrssi と比較をする．
 CT = 0
D
Ri > Refrssi (増加) → CTI + + CT + +D
Ri < Refrssi (減少) → CTI = 0
 CT = 0
D
Ri = Refrssi (増加減少以外) → CTI = 0
Step 6 CTD ，CTI と N を比較する．
N に到達した場合と到達してない場合で条件を分ける．
if
CTD = N → m angle =π2or
CTI = N → m angle = 0
then

37

Table 4.1: List of parameters using the search algorithm.
Parameters

Description

Positioni

Position index (i = 1, 2, 3, ...)

Step widthswDistance of one step

Maximum number of stepss max

Maximum number of steps
in one search movement

RSSI

Ri

RSSI at position i

Reference value

Refrssi

Reference RSSI to evaluate Ri

Contorl amount of moving direction

m angleAmount of change
in the moving direction

Distance to terminate the searchr src

Distance from signal source

Decrement counter

CTD

Increment when Ri is decremented
compared to Refrssi

Increment counter

CTI

Increment when Ri is Incremented
compared to Refrssi

Moratorium steps

N

Numeric value to respite
the judgment of approach/departure

Step 7 へ進む．
else if
CTD < N or
CTI < N

→ m angle = 0

thenStep 8 へ進む．
Step 7 CTD と CTI を 0 にリセットし，Refrssi を更新する．
Step 8 sw だけ移動する．移動開始時はランダム方向に sw だけ移動する．Step 1 に戻る．
判定猶予回数の設計 14.2.3

本節では，接近離反判定の接近か離反の確率モデルと測定地点ごとの RSSI からの標準偏差を用いた判定猶予回数 N の設計 [54] を説明する．

4.2.3.1

判定猶予回数 N の設計

判定猶予回数 N の設計を説明する．
（1）接近離反判定は，接近か離反の 2 通りであり，その確率は 0．5 である．そして，判定猶予回数

N までの確率は，(0．5)N である．ここで，統計的な危険率 α を利用して，この (0．5)N が十分38小さい値 α 以下となり，誤判定が発生するという仮説を棄却することを考える．すなわち，(0．5)N < α(4.1)と表せる．そして，N に関する条件が以下の様に求まる．

N>log10 (α)
log10 (0．5)(4.2)

ここで，α を 0．05 とする．そして，N は 5 となる．

√
（2）測定地点ごとの RSSI よりその標準偏差 (SDi ) を計算する．その計算には，平均偏差 (M Di = π/2·SDi ) より [55] 計算することとする．具体的には，測定地点 i での Ri と平滑化した RSSI (SRi ) より，

M Di [dB] = |Ri [dBm] − SRi [dBm]|(4.3)

SDi [dB] = 10 · log10 (0．8 × M Di [mW])(4.4)

そして，SPi は次のようにする．

1nSRi [mW] =

i
∑

(4.5)

Rt [mW]

t=i−n+1

SRi [dBm] = 10 · log10 (SRi [mW])(4.6)

ここで，n はサンプリング回数であり，i ≥ n − 1 を満たすこととする．i が n − 1 より小さい
場合は，SRi = Ri とする．本節では，n を 3 とする．
（3）以上，これらより判定猶予回数 N を次のようにする．

N ← max {SDi ，5}(4.7)

これは，SDi が 5 より大きい場合は SDi の値を N とし，それより小さい場合は N を 5 として
いる．

4.2.4

判定猶予回数の設計 2フレーム同期技術の同期はずれ検出の従来方式を示し，判定猶予回数 N の設計を説明する．

4.2.4.1

従来方式

フレーム数を計数するリセット計数器を用いた従来方式 [51], [52] を示す．N 段のリセット計数器の計数値がリセットされた状態から初めて N に到達するまでの確率母関数を QN (Z) とする．QN (Z)は次式で与えられることが明らかにされている．

QN (Z) =(1 − pZ) · pN · Z N
1 − Z(1 − p′ · pN · Z N )

(4.8)
′

ただし，Z は単位時間の遅延を示す作用素，p は計数値が 1 段歩進する確率，p (= 1 − p) は計数値がリセットされる確率である．
′

計数値が N に到達するまでの平均時間は QN (Z) での微分係数 QN (1) で与えられる．
′

QN (1) =1 − pN(1 − p) · pN

39

(4.9)

4.2.4.2

判定猶予回数 N の設計

判定猶予回数 N の設計を説明する．(4.9) 式は N の期待値でもあるので，N に到達する確率 τ は
以下のようになる．

τ=(1 − p) · pN
1 − pN(4.10)

ここで，統計的な危険率 α を用いて，(4.10) 式の τ が十分小さい値 α 以下となり，誤判定が発生するという仮説を棄却することを考える．この α を十分に小さくすることにより，誤判定を抑制できる．すなわち， τ < α の条件より，N に関する条件が以下の様に求まる．

(
N > log10

)
α
1
·
1−p+α
log10 (p)(4.11)

以上より，(4.11) 式を満たす最小の整数値 N を判定猶予回数とする．各計測地点 i での p を瞬間判
定確率 pi とする．

4.2.4.3

瞬間判定確率 pi の設計

次の 2 つのアプローチで瞬間判定確率 pi の設計をする．
（1） pi =p とし，近似値として扱う．つまり，増加と減少がランダムに等確率 0.5 で発生するとして，0.5 の固定値とする．これから求められた N を固定の判定猶予回数とする．
（2）各計測地点 i での pi を算出して，N を動的にする．これから求められた N を動的な判定猶予
回数とする．
次に，動的な判定猶予回数の具体的な設計について述べる．
同一直線上を一定間隔ごとに計測した Ri から，その RSSI の平均値 mi を (4.12) 式より決定する．そして，標準偏差 SDi は 3 計測地点ごとに mi を用いて (4.13) 式より決定することとする．
dBmmi ←− β · Ri + (1 − β) · mi−1
v
u
i
1 ∑
dBm u
SDi ←− t(Rj − mi )2n(4.12)(4.13)j=i−2

ここで，β (0 < β) は平滑定数であり，β を 0.125，n は 3 とする．そして，mi ，SDi から次式を用いて係数 ti を求める．

ti =Ri − miSDi(4.14)RSSI の確率密度関数が正規分布に従うと仮定して，正規分布について ti から ∞ までの確率分布を求める．これを pi とする．

pi =
=

( 2)
∫ ∞
1
x
√
exp √
dx
2π ti
2
{
(
)}
ti
1
1 − erf √2
2

40(4.15)

Fig. 4.2: A relationship between pi and N .
Table 4.2: Starting positions of searcher
Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

x [m]

100

90

80

70

60

50

40

30

20

y [m]

100

90

80

70

60

50

40

30

20

(4.11) 式から (4.15) 式を用いて N を算出すると，t < 0 では，pi > 0.5 となるため，N も pi = 0.5の時よりも大きな値になる．また，t > 0 では，pi < 0.5 となるため，N も pi = 0.5 の時よりも小さな値になる．よって，N は動的に与えられた判定猶予回数となる．Fig. 4.2 に α (=0.01，0.05，

0.1) ごとの pi と N の関係を示す．

4.3

探索シミュレーション

4.3.1
4.3.1.1

検討条件
探索エリア

探索エリアは，ステップ幅 sw を単位とする 2 次元格子状の直交座標系である xy 平面とする．探索者は RSSI を各格子点上で計測し，上下左右の 4 方向に一定速度で移動する．探索エリアには，概ね電波到達範囲で，移動を妨げる障害物はないものとする．

4.3.1.2

探索開始位置と信号源探索者は探索エリアの xy 平面で，計 9 地点の移動開始地点からシミュレーションを開始
し，各移動開始地点ごと (Table 4.2 の Test 1∼Test 9) に 100 回のシミュレーションを試行する．
信号源は (x，y) = (0, 0) 座標で静止している．

41

Table 4.3: Parameters in (4.16) and (4.17)
Parameters4.3.1.3

ValuesUnit

reference distanced0

1

RSSI at reference distanceP0-30.05

path loss exponentγ

2measurement variation of RSSI

Xσ2

32

62

92

122

[m]
[dBm]
[dB]

無線伝搬モデル

本節では計算機シミュレーションで用いる無線伝搬モデルについて述べる．RSSI を P̄ [dBm] として，無線伝搬モデルには RSSI が対数正規分布に従う一般的なモデルを用いる [36]．

P [dBm] ∼ N (P̄ [dBm], Xσ2 )P̄ [dBm] = P0 [dBm] − 10 · γ · log10(d)d0(4.16)(4.17)

ここで，P̄ [dBm] はデシベル表記の平均 RSSI，Xσ2 [dB] は計測値の変動を表す分散値 ( 以下，Xσ2 ) であり，N (P̄ [dBm], σi2 ) は P̄ , Xσ2 の正規分布に従うことを意味する．P0 [dBm] は基準距離 d0 [m] に対する RSSI であり，本稿では d0 =1[m][36] として与えることとする．既知の無線伝搬モデルである自由空間モデル [53] から P0 は-30.05 [dBm] (周波数: 2.4 [GHz]，送信出力: 10 [mW][56], 送
受信アンテナ利得: 1) である．d [m] は通信距離，γ は距離減衰定数を表す．ただし，計算機シミュ
レーションでは，γ と d および信号源は探索者に対して未知数として扱う．Table 4.3 に (4.16) 式，(4.17) 式で用いるパラメータと計算機シミュレーションで設定する値を示す．Xσ2 は環境に依存し，室内 · 屋外で 32 ∼ 122 [dB] と報告されている [57] ことから，本稿でもこの範囲で検討するのが望ましい．γ は固定値とする．

4.3.2

評価指標

4.2.3, 4.2.4 節で述べた判定猶予回数の評価を次の指標を用いて行う．
• 誤判定率
接近もしくは離反と判定した回数のうち，誤判定した回数の割合を誤判定率とする．誤判定
率 λ を次の式より決定する．

λ=

総誤判定回数[0 ∼ 1]
総判定回数(4.18)• 迂回率
探索者の移動開始地点と信号源との直線距離に対する探索者が移動した距離の比 η を次の式より決定する．

η=
探索に要した移動距離[≥ 1]
移動開始地点と信号源までの直線距離

42(4.19)

誤判定率 (λ) は，判定精度を評価するために用いる．λ は，0∼1 の範囲で表され，0 に近いほど判定精度が高いこと示す．そして，迂回率 (η) は，探索の遅延度合いを評価するために用いる．η は，1以上の値で表される．η が 1 の場合は，移動開始地点から信号源まで一直線で進んだことになる．
なお，λ と η の関係性は次のようなものがある．1) λ が悪化すれば，η も悪化する．2) λ が小さい値で精度高い判定と評価されても，η の値は場合がある．これは，信号源の周辺を周回するためである．

4.4

計算機シミュレーション結果

計算機シミュレーションから，誤判定率 λ と迂回率 η について述べる．計算機シミュレーション諸元を Table 4.4 に示す．

Table 4.4: Simulation parameters.
Parameters
sw
s max

Unit

0.5

[m]

5000

m angle
r src

4.4.1

Values[times]

0

[rad]

π/2

[rad]

5

[m]

探索者の移動軌跡の例

各計数値 (CTI ，CTD ) の推移と，探索者の移動軌跡の一例として，N = 4 とした固定の判定猶予
回数を用いた場合を Fig. 4.3 に，動的な判定猶予回数を用いた場合を Fig. 4.4 に示した．同図では，移動開始地点 (i=1) から 2 回目の移動方向制御 (i=30) までとし，各地点で RSSI を計測する．図中，A，B，C，D は，接近もしくは離反を判定した計測区間を表している．

Fig. 4.3 で，i=5 の地点で CTI が N に到達したため，接近と判定した．Refrssi は区間 A 内で最小の RSSI であった i=1 での RSSI に更新した．そして，i=15 の地点で CTI が N に到達したため，接近と判定し，区間 B 内で最小の RSSI であった i=7 での RSSI に Refrssi を更新した．次に，

i=19 の地点で CTD が N に到達したため，離反と判定し移動方向を垂直方向に変更した．Refrssi は
区間 C 内で最小の RSSI であった i=16 での RSSI に更新した．そして，i=30 の地点で CTD が Nに到達したため，離反と判定し移動方向を垂直方向に変更した．Refrssi は区間 D 内で最小の RSSIであった i=27 での RSSI に更新した．

Fig. 4.4 も先の例同様，i=5 の地点で CTI が N に到達する例である．その途中，i=5 の地点での N より大きな値になったりしているが，計数値に到達することで判定をすることに変わりはない．
そのほかの地点も，先の例同様であり，計数値が N に到達する前に，その地点での N より大きくな
ることはある．N は動的に変化をし，一度その値 (例えば，N =13) になったとしても，計数値がその値になるまで判定が下されないとということはない．各地点で動的に変化した N と計数値が一致した場合に判定を下さす．
移動方向制御では，探索者が同一直線上を移動する軌跡上で信号源に最も接近した地点が，理想43

的に最大の RSSI になる．区間 D は誤判定が発生した区間の例である．すなわち，RSSI が大きく変動していたことで減少を計数し，N に到達して誤判定してが発生している例である．Fig. 4.3 やFig. 4.4 から誤判定が発生すると，移動距離が増えることがわかる．

Fig. 4.3: An example of trajectory in static moratorium steps (N = 4).

4.4.2
4.4.2.1

誤判定率 λ判定猶予回数の設計 1

4.2.3 節で述べた判定猶予回数を用いたシミュレーション結果について述べる．
Eq. (4.18) の λ を Fig. 4.5 に示す．シミュレーションは，Table 4.3 で示した Eq. (4.16) の Xσ2ごとに実施いている．

Fig. 4.9 より，λ は Xσ2 に依存していることがわかった．Xσ2 が大きくなるにつれて，λ は悪化する．そして，判定猶予回数の最低値を 5 としているため，λ はおおよそ 0.05 になっている．これは，Eq. (4.1) の α を 0.05 にしているためである．
4.4.2.2

判定猶予回数の設計 24.2.4 節で述べた判定猶予回数を用いたシミュレーション結果について述べる．
(4.18) 式の λ を Fig. 4.6∼4.8 に示す．シミュレーションは，(4.11) 式の各 α (=0.01，0.05，
0.1) を Table 4.3 の Xσ2 ごとに実施した．図の横軸は移動開始地点と信号源の距離 [m] であり，各移動開始地点ごとに探索を 100 回試行して λ を求めた．N は 4.2.4.3 節で述べた (1) の固定の判定

44

Fig. 4.4: An example of trajectory in dynamic moratorium steps.

Fig. 4.5: The misjudgment rate in Moratorium steps 1.

45

猶予回数と，(2) の動的な判定猶予回数それぞれについてシミュレーションしている．なお，移動開始から最初の判定までは Refrssi が移動開始地点での RSSI であるため，この区間を除いて λ を求めている．

Fig. 4.6∼4.8 より，α を小さくすると固定および動的な判定猶予回数の λ が小さくなる．これは，
α を小さくすることで判定猶予回数が大きくなっているため，誤判定が抑制されているためである．
そして，動的な判定猶予回数での λ は固定の判定猶予回数での λ に対して，(α，Xσ2 )=(0.01，32 ) のときでおよそ 4.45 倍だが，(α，Xσ2 )=(0.1，122 ) のときでおよそ 0.91 倍と小さくなっていることがわかった．つまり，動的な判定猶予回数は Xσ2 が小さいほど，誤判定が抑制されていないことを示している．動的な判定猶予回数は Xσ2 が小さい環境ほど判定猶予回数が小さくなるという特性がある
ため，固定の判定猶予回数より小さい値が与えられているためである．

Fig. 4.6: The misjudgment rate in α=0.01 in Moratorium steps 2.

Fig. 4.7: The misjudgment rate in α=0.05 in Moratorium steps 2.

46

Fig. 4.8: The misjudgment rate in α=0.1 in Moratorium steps 2.
4.4.3
4.4.3.1

迂回率 η
判定猶予回数の設計 1

4.2.3 節で述べた判定猶予回数を用いたシミュレーション結果について述べる．
Eq. (4.19) の η を Fig. 4.9 に示す．シミュレーションは，Table 4.3 で示した Eq. (4.16) の Xσ2ごとに実施いている．ただし，探索が s max 以内で終了しなかった結果は除いてある．

Fig. 4.9 より，η は Xσ2 に依存していることがわかった．Xσ2 が大きくなるにつれて，η は大きくなる．そして，移動開始地点が信号源に近いほど η は大きくなり，移動開始地点が信号源から最も遠い
地点と最も近い地点の結果を比較すると，最大でおよそ 2.5 倍の差があった．これは，移動方向を変更するための離反判定になるまで移動方向が維持されて，信号源付近ではなかな離反判定がされずに周回しているからである．

Fig. 4.9: The detour ratio in Moratorium steps 1.

47

4.4.3.2

判定猶予回数の設計 24.2.4 節で述べた判定猶予回数を用いたシミュレーション結果について述べる．
Eq. (4.19) の η を Fig. 4.10∼4.12 に示す．シミュレーションは，Table 4.3 で示した Eq. (4.16)の Xσ2 ごとに実施いている．ただし，探索が s max 以内で終了しなかった結果は除いてある．

Fig. 4.10∼4.12 の (α，Xσ2 )=(0.05，32 )，(α，Xσ2 )=(0.1，32 ) の場合では，動的な判定猶予回数の η は固定の判定猶予回数に対して，およそ 2 倍であった．(α，Xσ2 )=(0.05，122 ), (α，Xσ2 )=(0.1，

122 ) では，およそ 0.99 倍以下であり小さくなっていることがわかった．Fig. 4.10 の η は，移動開始地点が信号源から近いほど η は大きくなっている．これは，α=0.01 の場合，N が大きい値になってしまうことによる．N が大きくなることで判定が長い区間猶予されることで，信号源周辺を周回してしまっている．そのため，η が大きくなっている．
そして，Xσ2 が大きくなるにつれて，動的な判定猶予回数での η は固定の判定猶予回数に対して，(α，Xσ2 )=(0.05，92 ) でおよそ 1.06 倍，(α，Xσ2 )=(0.05，122 ) でおよそ 0.99 倍と差がなかった．
一方，Xσ2 が小さい場合では，(α，Xσ2 )=(0.05，32 ) でおよそ 2.29 倍，(α，Xσ2 )=(0.05，62 ) でお
よそ 1.38 倍となった．

Fig. 4.10: The detour ratio in α=0.01 in Moratorium steps 2.

4.4.3.2.1 判定猶予回数 N と瞬間判定確率 pi
ここでは，探索中に判定猶予回数 N と瞬間判定確率 pi がどの様に推移しているかを見ていく．
ある一つの探索中の N と pi を各測定地点での通信距離ごとに示している．まず，Fig. 4.13∼4.15に各測定地点での通信距離に対して，その地点での N を α=0.01，0.05，0.1 の場合でそれぞれ示している．そして，そのときの pi を示したのが，Fig. 4.16∼4.18 である．図の横軸は信号源からの通信距離 [m] である．

Fig. 4.13∼4.15 と Fig. 4.16∼4.18 から，RSSI 計測地点ごとの N および pi を一次回帰式に変換した図が，Fig. 4.19 と Fig. 4.20 である．図の横軸は信号源からの通信距離 [m] である．

Fig. 4.19 より，α ごとに一次回帰線が密集していることから，N は α に依存していることがわかる．そして，Fig. 4.20 より，Xσ2 ごとに一次回帰線が密集していることから，pi は Xσ2 に依存して48

Fig. 4.11: The detour ratio in α=0.05 in Moratorium steps 2.

Fig. 4.12: The detour ratio in α=0.1 in Moratorium steps 2.

49

(a) Xσ2 =32(b) Xσ2 =62(c) Xσ2 =92(d) Xσ2 =122

Fig. 4.13: The relationship of the communication distance - N in α = 0.01.

(a) Xσ2 =32(b) Xσ2 =62(c) Xσ2 =92(d) Xσ2 =122

Fig. 4.14: The relationship of the communication distance - N in α = 0.05.

50(a) Xσ2 =32(b) Xσ2 =62(c) Xσ2 =92(d) Xσ2 =122

Fig. 4.15: The relationship of the communication distance - N in α = 0.1.

(a) Xσ2 =32(b) Xσ2 =62(c) Xσ2 =92(d) Xσ2 =122

Fig. 4.16: The relationship of the communication distance - pi in α = 0.01.

51

(a) Xσ2 =32(b) Xσ2 =62(c) Xσ2 =92(d) Xσ2 =122

Fig. 4.17: The relationship of the communication distance - pi in α = 0.05(a) Xσ2 =32(b) Xσ2 =62(c) Xσ2 =92(d) Xσ2 =122

Fig. 4.18: The relationship of the communication distance - pi in α = 0.1

52いることがわかる．つまり，(4.11) 式の動的な判定猶予回数は Xσ2 が大きいほど判定に猶予をもたせるようにしているため，RSSI の変動に応じて N が変化することの確認ができた．なお，一次回
帰線がほぼ一定であるのは，本稿で用いた電波伝搬モデル (4.3.1.3 節) において Xσ2 が一定であることによるためである．

Fig. 4.19: The relationship of the communication distance - N .

Fig. 4.20: The relationship of the communication distance - pi .

4.4.4

比較

提案手法を DREAMS[48] と迂回率 η で比較を行う．比較はシングルホップ接続で，4.3.1 節で挙げた条件を行うものとする．ただし，DREAMS の探索エリアは 2 次元の xy 平面であり，2 次元
格子状の格子点上を移動する提案手法と異なる．DREAMS のシミュレーションでは，1 回の最大移動距離を 100 [m] とした．これは，RSSI から得られた距離が非現実的であることを防ぐために行っ
ている．

53

4.4.4.1

判定猶予回数の設計 1

判定猶予回数の設計 1 と DREAMS における迂回率 η の比較結果を Table 4.5 および 4.6 に示す．Table 4.5 において，DREAMS は各 RSSI の測定地点で 10 回のサンプリングを行い平均化した RSSI を用いている．

4.6 の結果で比較すると，判定猶予回数の設計 1 は DREAMS と比べて，およそ 1/26∼5/8 の移動距離で信号源に探索できている．このことは，RSSI をもとにした距離が誤った距離をよるものであることが説明できる．そして，平均化した RSSI でも判定猶予回数の設計 1 の方が短い移動距離で信号源に探索できていることがわかる．ただし，Xσ2 =32 [dB] で移動開始地点が {20, 20} のときに，DREAMS が判定猶予回数の設計 1 より短い移動距離になった．この結果が，DREAMS が判定猶予回数の設計 1 より上回っていた唯一の結果である．

Table 4.5: η of Moratorium steps 1 and DREAMS.
Distance between theMoratorium steps 1

DREAMS

starting point and TN

Xσ2 [dB]Xσ2 [dB]

Coordinate

Distance [m]

32

62

92

122

32

62

92

122

{20, 20}

28.28

14.34

20.89

34.36

35.31

18.06

55.39

167.76355.53{30, 30}

42.43

9.33

16.75

25.93

26.53

20.75

85.87

201.37404.43{40, 40}

56.57

9.56

14.72

19.48

19.22

21.70

80.27

217.14432.37{50, 50}

70.71

7.38

12.28

15.80

16.74

23.41

85.76

245.26423.52{60, 60}

84.85

7.26

10.89

13.47

15.55

29.14

80.54

246.29542.80{70, 70}

98.99

7.15

11.60

10.09

13.30

30.78

76.14

188.20356.28{80, 80}

113.14

6.71

10.13

11.17

10.41

25.51

92.58

227.06515.65{90, 90}127.28

5.93

9.06

9.27

10.68

26.17

107.55252.48474.56{100, 100}

141.42

5.92

8.75

8.10

9.20

25.95

117.69351.60565.134.4.4.2

判定猶予回数の設計 2

判定猶予回数の設計 2 と DREAMS における迂回率 η の比較結果を Table 4.7∼4.12 に示す．Ta-ble 4.7∼4.9 は，固定の判定猶予回数との比較であり，α は 0.01, 0.05, 0.1 である．Table 4.10∼4.12
は，動的な判定猶予回数との比較であり，α は 0.01, 0.05, 0.1 である．4.4.4.1 節の結果より，

DREAMS は各 RSSI の測定地点で 10 回のサンプリングを行い平均化した RSSI を用いた結果のみと比較を行うこととした．
これらの結果からも先と同様，判定猶予回数の設計 2 が DREAMS の結果より上回っている．一部，Xσ2 =32 [dB] での結果が DREAMS の方が上回っている場合があるが，Xσ2 =62 [dB] 以上では，全ての結果で判定猶予回数の設計 2 のほうがおよそ 1/10 の移動距離で信号源に探索ができている．
これは，RSSI の変動が大きい環境では，RSSI をもとにした距離をが誤った距離を導き出しているためである．

54

Table 4.6: η of Moratorium steps 1 and DREAMS with averaged RSSI.
Distance between theMoratorium steps 1

DREAMS (with averaged RSSI)

starting point and TN

Xσ2 [dB]Xσ2 [dB]

Coordinate

Distance [m]

32

62

92

122

32

62

92

122

{20, 20}

28.28

14.34

20.89

34.36

35.31

9.69

17.45

57.79

124.31{30, 30}

42.43

9.33

16.75

25.93

26.53

9.53

21.50

85.80

230.16{40, 40}

56.57

9.56

14.72

19.48

19.22

10.48

22.75

129.75315.37{50, 50}

70.71

7.38

12.28

15.80

16.74

11.05

37.92

165.50373.57{60, 60}

84.85

7.26

10.89

13.47

15.55

13.00

36.69

173.19392.41{70, 70}

98.99

7.15

11.60

10.09

13.30

11.56

40.29

223.18431.49{80, 80}

113.14

6.71

10.13

11.17

10.41

13.70

46.36

257.60426.58{90, 90}127.28

5.93

9.06

9.27

10.68

13.62

44.10

248.04419.13{100, 100}

141.42

5.92

8.75

8.10

9.20

13.15

60.22

323.46406.71

Table 4.7: η of Moratorium steps 2 (Static, α=0.01) and DREAMS with averaged RSSI.
Distance between theMoratorium steps 2DREAMS (with averaged RSSI)

starting point and TN

Xσ2 [dB]Xσ2 [dB]

Coordinate

Distance [m]

32

62

92

122

32

62

92

122

{20, 20}

28.28

7.14

9.62

9.30

10.71

9.69

17.45

57.79

124.31{30, 30}

42.43

9.31

9.48

9.97

9.18

9.53

21.50

85.80

230.16{40, 40}

56.57

9.99

12.10

10.31

10.22

10.48

22.75

129.75315.37{50, 50}

70.71

10.77

11.08

10.71

13.50

11.05

37.92

165.50373.57{60, 60}

84.85

10.71

14.06

13.71

12.42

13.00

36.69

173.19392.41{70, 70}

98.99

14.15

15.96

14.82

12.57

11.56

40.29

223.18431.49{80, 80}

113.14

16.29

15.46

17.32

18.31

13.70

46.36

257.60426.58{90, 90}127.28

28.36

22.48

25.36

22.99

13.62

44.10

248.04419.13{100, 100}

141.42

36.97

31.70

38.31

37.33

13.15

60.22

323.46406.7155

Table 4.8: η of Moratorium steps 2 (Static, α=0.05) and DREAMS with averaged RSSI.
Distance between theMoratorium steps 2DREAMS (with averaged RSSI)

starting point and TN

Xσ2 [dB]Xσ2 [dB]

Coordinate

Distance [m]

32

62

92

122

32

62

92

122

{20, 20}

28.28

7.70

9.59

11.20

12.47

9.69

17.45

57.79

124.31{30, 30}

42.43

7.12

10.54

11.40

11.07

9.53

21.50

85.80

230.16{40, 40}

56.57

6.70

10.85

11.97

12.83

10.48

22.75

129.75315.37{50, 50}

70.71

6.17

10.78

11.16

14.00

11.05

37.92

165.50373.57{60, 60}

84.85

5.90

8.97

12.76

13.10

13.00

36.69

173.19392.41{70, 70}

98.99

5.49

9.12

12.60

12.57

11.56

40.29

223.18431.49{80, 80}

113.14

4.84

9.69

11.43

14.90

13.70

46.36

257.60426.58{90, 90}127.28

5.16

7.32

12.79

12.10

13.62

44.10

248.04419.13{100, 100}

141.42

5.35

8.96

12.13

17.24

13.15

60.22

323.46406.71

Table 4.9: η of Moratorium steps 2 (Static, α=0.1) and DREAMS with averaged RSSI.
Distance between theMoratorium steps 2DREAMS (with averaged RSSI)

starting point and TN

Xσ2 [dB]Xσ2 [dB]

Coordinate

Distance [m]

32

62

92

122

32

62

92

122

{20, 20}

28.28

12.10

14.29

13.59

15.63

9.69

17.45

57.79

124.31{30, 30}

42.43

12.03

16.04

15.43

13.92

9.53

21.50

85.80

230.16{40, 40}

56.57

11.47

13.88

16.20

15.15

10.48

22.75

129.75315.37{50, 50}

70.71

11.69

15.23

14.84

15.23

11.05

37.92

165.50373.57{60, 60}

84.85

11.17

15.57

17.85

19.13

13.00

36.69

173.19392.41{70, 70}

98.99

10.66

16.86

18.69

19.45

11.56

40.29

223.18431.49{80, 80}

113.14

7.79

16.06

18.80

19.94

13.70

46.36

257.60426.58{90, 90}127.28

5.76

13.07

17.11

20.46

13.62

44.10

248.04419.13{100, 100}

141.42

5.78

11.65

15.93

19.39

13.15

60.22

323.46406.7156

Table 4.10: η of Moratorium steps 2 (Dynamic, α=0.01) and DREAMS with averaged RSSI.
Distance between theMoratorium steps 2DREAMS (with averaged RSSI)

starting point and TN

Xσ2 [dB]Xσ2 [dB]

Coordinate

Distance [m]

32

62

92

122

32

62

92

122

{20, 20}

28.28

7.67

9.19

9.59

9.07

9.69

17.45

57.79

124.31{30, 30}

42.43

8.64

10.73

9.39

9.95

9.53

21.50

85.80

230.16{40, 40}

56.57

7.94

10.46

12.14

11.12

10.48

22.75

129.75315.37{50, 50}

70.71

8.90

10.16

11.29

13.73

11.05

37.92

165.50373.57{60, 60}

84.85

6.96

10.81

13.72

13.62

13.00

36.69

173.19392.41{70, 70}

98.99

8.06

14.11

13.29

15.35

11.56

40.29

223.18431.49{80, 80}

113.14

7.81

16.56

18.28

18.69

13.70

46.36

257.60426.58{90, 90}127.28

10.16

15.61

19.43

25.29

13.62

44.10

248.04419.13{100, 100}

141.42

11.21

21.75

29.54

38.68

13.15

60.22

323.46406.71

Table 4.11: η of Moratorium steps 2 (Dynamic, α=0.05) and DREAMS with averaged RSSI.
Distance between theMoratorium steps 2DREAMS (with averaged RSSI)

starting point and TN

Xσ2 [dB]Xσ2 [dB]

Coordinate

Distance [m]

32

62

92

122

32

62

92

122

{20, 20}

28.28

12.52

11.03

10.50

9.50

9.69

17.45

57.79

124.31{30, 30}

42.43

12.33

11.22

9.13

10.37

9.53

21.50

85.80

230.16{40, 40}

56.57

13.61

11.90

12.28

11.56

10.48

22.75

129.75315.37{50, 50}

70.71

14.81

11.88

11.88

12.92

11.05

37.92

165.50373.57{60, 60}

84.85

14.46

14.41

11.42

10.65

13.00

36.69

173.19392.41{70, 70}

98.99

14.22

13.61

12.78

14.35

11.56

40.29

223.18431.49{80, 80}

113.14

14.99

14.19

13.62

14.46

13.70

46.36

257.60426.58{90, 90}127.28

14.11

13.85

16.59

16.44

13.62

44.10

248.04419.13{100, 100}

141.42

13.51

16.93

16.47

19.46

13.15

60.22

323.46406.7157

Table 4.12: η of Moratorium steps 2 (Dynamic, α=0.1) and DREAMS with averaged RSSI.
Distance between theMoratorium steps 2DREAMS (with averaged RSSI)

starting point and TN

Xσ2 [dB]Xσ2 [dB]

Coordinate

Distance [m]

32

62

92

122

32

62

92

122

{20, 20}

28.28

13.40

13.04

11.72

11.99

9.69

17.45

57.79

124.31{30, 30}

42.43

16.18

14.40

11.28

10.72

9.53

21.50

85.80

230.16{40, 40}

56.57

20.16

15.25

13.60

12.69

10.48

22.75

129.75315.37{50, 50}

70.71

23.19

14.61

14.28

10.99

11.05

37.92

165.50373.57{60, 60}

84.85

20.56

16.18

14.17

13.25

13.00

36.69

173.19392.41{70, 70}

98.99

19.51

17.38

14.18

15.52

11.56

40.29

223.18431.49{80, 80}

113.14

23.04

18.27

18.06

15.30

13.70

46.36

257.60426.58{90, 90}127.28

27.66

17.52

16.70

17.05

13.62

44.10

248.04419.13{100, 100}

141.42

19.07

21.99

18.54

18.49

13.15

60.22

323.46406.71

4.5
4.5.1

考察
接近離反判定を猶予する影響

判定猶予回数の設計 1 の判定猶予回数，判定猶予回数の設計 2 の固定もしくは動的な判定猶予回
数による接近離反判定で，誤判定率 λ は 0.25 以下で抑えられることを確認した．その判定猶予回数の有効性を確認するために，接近離反の判定を猶予しない (N =1) 場合の誤判定率を Fig. 4.21 に示す．この際，同一地点にて複数回 RSSI のサンプリング (100 回) を行い，平均化を行った RSSI を用いた．Fig. 4.21 から，Xσ2 =32 では，λ は 0.37∼0.48 であった．そして，Xσ2 =62 ∼122 では，λ は
およそ 0.5 であった．このことから，接近離反の判定を猶予することで誤判定が抑制されていることがわかる．接近離反の判定を猶予しない (N =1) 場合の迂回率を Fig. 4.22 に示す．同様に，同一地

Fig. 4.21: The misjudgment rate in N = 1.

58

点にて複数回 RSSI のサンプリング (100 回) を行い，平均化を行った RSSI を用いた．なお，探索が s max 以内で終了しなかった結果は除いてある．そのため，1 度も探索が s max 以内に終了しなかった移動開始地点では，η を 0 とする．Xσ2 = 32 では η は 20 以下であったが，それ以外の Xσ2 では η が 0 になる場合もあった．つまり，接近離反の判定を猶予することで，誤判定が抑制されて効率的に探索できていることがわかる．
このことより，Xσ2 がある環境下で RSSI を平均化を行っても変動があるため，一般的な平均化では接近離反の判定には不十分であり，接近離反の判定を猶予することは有効であるといえる．また，同一地点にて複数回 RSSI のサンプリングを行っていることで，RSSI の計測回数は提案手法よりも増加している．このことは，Fig. 4.22 で η が 0 になっていることから確認できる．

Fig. 4.22: The detour ratio in N = 1.
4.5.2

判定猶予回数を動的にする効果

Fig. 4.6∼4.8 および Fig. 4.10∼4.12 の結果から，α を小さくすると N が大きくなるため λ はよくなるが，判定が長い区間猶予されるため多く歩進してしまう．例えば，Fig. 4.1 で地点 b を過ぎても，すぐに離反判定が行われず，地点 c もしくはそれ以上の地点で離反判定がされて，移動距離が多くなり η を悪くすることになる．特に，Fig. 4.10 では，信号源近くで開始した探索では上述の理由
で信号源を周回してしまうことで η を悪くしている．Fig. 4.11 と Fig. 4.12 の結果から，動的な判定猶予回数が探索開始位置に依存せずに η を一定に保つための糸口になると考えられる．

α が小さくなるほど，N は大きくなっている．そのため，判定を猶予する区間も長くなることで，λはよくなる．しかし，移動距離もかかるため，α をなるべく小さくしないほうが効率のよい探索ができる．つまり，探索開始位置に依存せずに η を一定に保ち，かつ，λ をよくするためには，α は 0.05
もしくは 0.1 が望ましいことがこれらの結果からいえる．ここから，Fig. 4.7，Fig. 4.8，Fig. 4.11，

Fig. 4.12 の Xσ2 =92 や 122 のような Xσ2 が大きな環境の場合，動的な判定猶予回数での λ と η は固定の判定猶予回数に対しておよそ 0.96 倍であった．この結果は，動的な判定猶予回数は Xσ2 が大きな環境で有効であることを示唆している．本稿では信号源を静止させて検討を行ったが，現実の環境
では信号源が静止しているとは限らない．信号源が移動することで，探索者が得られる RSSI の変動

59

が大きくなることが予想され，動的な判定猶予回数が効果的に働くことが期待できる．

4.6

むすび

本研究では RSSI を利用することで，同一直線上を一定間隔ごとに移動しながら計測した RSSI が増加もしくは減少の変化が連続して計数値 (CTD もしくは CTI ) が判定猶予回数 (N ) に到達すること
でその判定を行い，移動方向制御を行うための判定猶予回数を提案した．そして，RSSI の変動する環境では RSSI は計測地点での通信距離に応じて単調な増減とならないが，接近離反の判定を判定猶
予回数分猶予することで，接近離反判定の誤判定が抑制でき，探索が効率的に行えることを計算機シ
ミュレーションにより確認した．本提案手法は，無線通信時に入手できる RSSI から接近離反判定が可能であるため，幅広い無線方式でも適用可能である．
今後は信号源も探索者と同様に移動している場合での検証を行う予定である．そして，本稿では単一の接続で検討を行ったが，複数の端末が接続して通信する場合で，複数の端末が協調して探索を行うことを検討する．
本研究は，文献 [54][58] で発表したものをまとめたものである．

60

第 5 章 マルチホップ接続の探索手法

第 5 章では，アドホックネットワークの通信を想定して複数の端末が協調して信号源を探索する
組織戦略を提案する．RSSI を用いた接近離反判定の手法には，第 4 章で述べた固定の判定猶予回数を利用して，計算機シミュレーションで評価し，その効果を述べる．

5.1

まえがき

第 4 章では，1 対 1 の探索であった．通信範囲に限界があるため，広域の通信を可能する技術としてマルチホップ通信が有効である．本章ではマルチホップ通信を対象として，複数の端末が協調して信号源を探索する手法の検討を行う．

5.1.1

関連研究

アドホックネットワークの通信では端末間の距離が離れてしまうと通信が行えなくる．そのため，複数の端末を介して通信するマルチホップ通信は，広域でも通信ができる．そのマルチホップ通信を用いた組織的な救助活動 [59] が提案されている．マルチホップ通信の端末を救助活動エージェント
として，隊列を組んで移動しながら救助活の捜索のシミュレーションを行い評価を行っている．本研
究は，組織戦略，情報共有の観点から，情報共有と広域探索のトレードオフに対処するための組織戦略の提案を行っている．

RSSI と方向センサ用いた隊形制御アルゴリズムが提案 [60] されている．複数のモバイルロボット
がメッシュネットワーク上で，提案アルゴリズムを利用して自動で隊形に整列する．そして，複数のモバイルロボットの相互通信の安定化のため，モバイルロボット同士が協調して RSSI をもとにして制御される手法 [61] が提案されている．これらは，複数のモバイルロボットの隊形を制御するために RSSI が利用されている．
また，複数の端末を活用して経路を決定する手法が提案されている．グラフ構造を活用した BRF (Breadth-First)[62] や BTG (Backtracking greedy)[62] がある．これらは，探索する端末の経路をグラフ構造を通して決定している．MBL (ndc)[63] は，点在している端末をクラスタリングし最も密度が高い端末を選択することで経路を決定している．MALS[64] は，点在している端末を縫い繕うようにして経路を決定している．
これらは，マルチホップ通信を対象として，複数の端末を協調する手法であるが，探索経路を決定するのに RSSI は用いられていない．このことより，第 4 章での手法をマルチホップ通信に適用して，信号源の探索手法を検討する．次に，探索手法として，複数の端末が協調する戦略を検討する．

61

5.2

複数の端末が協調した探索戦略

複数の端末が協調して探索する戦略について述べる．中継端末には，信号源から探索端末の順に番
号付け (1, 2, · · · ) を̇行う．
検討を行うにあたって，簡単にするために探索開始時にアドホックネットワークの通信を行っている端末のみとする．つまり，端末が移動しながら，周辺の参加してない端末へルーティングすることは考慮しない．探索開始時に参加している端末で，RSSI の強度で隣接する端末を選択する．つまり，最も強い RSSI の端末と接続することとすることを基本前提とする．

5.2.1

ランダム探索戦略

ランダム探索戦略は非協調戦略であり，各端末が信号源からの RSSI の変化をもとに信号源へ探索を行う．ランダム探索戦略の概念図を Fig. 5.1 に示す．

Fig. 5.1: The random search strategy.

5.2.2

隣接端末追随探索戦略

隣接端末追随探索戦略は各端末が隣接端末の RSSI の変化をもとに隣接端末へ探索を行う．隣接端末追随探索戦略の概念図を Fig. 5.2 に示す．信号源の隣接の端末は信号源を探索することから，その隣接の端末を探索する端末は，信号源に対して探索できていることになる．

5.3
5.3.1

複数の端末が協調して探索する計算機シミュレーション
検討条件

計算機シミュレーションで検討するための諸条件について述べる．
探索エリア
探索エリアは，ステップ幅 sw を単位とする 2 次元格子状の直交座標系である xy 平面とする．探索者は RSSI を各格子点上で計測し，上下左右の 4 方向に一定速度で移動する．探索エリアには，概62Fig. 5.2: The strategy of following the nearest node.
ね電波到達範囲で，移動を妨げる障害物はないものとする．
探索端末, 信号源
各端末は，

• 無線 LAN(IEEE 802.11b) を装備した無線端末• アドホックネットワークの通信に対応• アンテナは無指向性のアンテナであることを前提とする．そして，探索端末は次の機能を有することとする．

• RSSI の測定ができる• 移動した距離が測定できる• 移動方向の制御ができる
信号源は, 探索端末同様の機能を持つ無線端末であることを前提とし，ビーコン等の電波を定期的に発信ができることとする．そして，静止しているものとする．
移動方向制御xy 平面上で信号源の位置が原点になるようにすると信号源の存在する確率が最大になるように探索端末および中継端末は螺旋を描くような経路になる [28]．本研究では，探索端末が螺旋を描くような移動軌跡にするため，接近判定の場合は 0 [rad] ，離反判定の場合は π/2 [rad] とする．
電波伝搬モデル63

Table 5.1: Parameters in (5.1) and (5.2).
Parameters

ValuesUnit

reference distanced0

1

RSSI at reference distanceP0-30.05

path loss exponentγ

2measurement variation of RSSI

Xσ2

32

62

92

122

[m]
[dBm]
[dB]

本節では計算機シミュレーションで用いる無線伝搬モデルについて述べる．RSSI を P̄ [dBm] として，無線伝搬モデルには RSSI が対数正規分布に従う一般的なモデルを用いる [36]．

P [dBm] ∼ N (P̄ [dBm], Xσ2 )P̄ [dBm] = P0 [dBm] − 10 · γ · log10

(d)
d0

(5.1)
(5.2)

ここで，P̄ [dBm] はデシベル表記の平均 RSSI，Xσ2 [dB] は測定値のばらつきを表す値であり，N (P̄ [dBm], σi2 )は P̄ , Xσ2 の正規分布に従うことを意味する．P0 [dBm] は基準距離 d0 [m] に対する RSSI であり，本研究では d0 = 1[m][36] として与えることし，既知の無線伝搬モデルである自由空間モデル [53] から P0 は-30.05 [dBm] (周波数:2.4 [GHz], 送信出力: 10 [mW ][56], 送受信アンテナ利得: 1) である．

d [m] は通信距離，γ は距離減衰定数を表す．ただし，計算機シミュレーションでは，γ と d は探索者
および信号源は未知数として扱う．Table 5.1 に Eq. (5.1)，Eq. (5.2) で用いるパラメータと計算機シミュレーションで設定する値を示す．
探索終了条件探索端末が信号源から所定の閾値距離 (r src0) 以内に達した場合，探索を終了とする．また，探索端末が中継端末からの所定の閾値距離 (r src1) 以内に達した場合，その中継端末への探索を終了し，次の端末の探索へ移行する．

5.3.2

シミュレーションの設定

シミュレーション諸元
シミュレーション諸元を表 5.2 に示す．探索端末と信号源の通信距離に制限のない想定でシミュ
レーションを行う．ステップ最大回数 (s max) 以内に探索終了条件に満たさなかった場合，探索は失敗したとする．探索端末は xy 平面の (x,y) = (200,200) の座標から探索を開始することとする．信
号源は (x,y) = (0,0) の座標に静止していることとする．
判定猶予回数
判定猶予回数は，第 4 章で述べた固定および動的な判定猶予回数を組み合わせたものを用いる．すなわち，Eq. (4.11) で，pi が 0.5 のを用いた判定猶予回数と Eq. (4.15) を用いた判定猶予回数で大きい値をを N とする．なお，α は 0.05 とした．
探索に参加する端末
探索者と目標物を他の端末が中継して通信を行う，マルチホップを想定中継する端末数を 0∼14 台
まで変えて，計算機シミュレーションを行う. 5.2 節で述べた複数の端末が協調して探索する戦略か64

Table 5.2: Specification of simulation.
Parameters
sw
s max

Values

Unit

0.5

[m]

5000

[times]

0

[rad]

π/2

[rad]

r src010[m]

r src13[m]

m angleら，探索失敗率を比較する．計算機シミュレーションでは，α (0.01, 0.05, 0,1) と各 Xσ2 ごとの組み合わせで，それぞれ 100 回のシミュレーションを行う．探索失敗率は 100 回の試行中で失敗した回
数とする．

5.3.3

シミュレーション結果

Fig. 5.3∼5.7 にランダム探索戦略での結果を示す．そして，Fig. 5.8∼5.12 に隣接端末追随探索
戦略の結果を示す．図の横軸は探索に参加した端末番号，縦軸は探索不成功率 [%] である．探索に参加した端末数ごとにデータを示している．

Fig. 5.3: The result of random search strategy, Xσ2 =02
Fig. 5.3 の Xσ2 =02 では，全ての端末が探索に成功している．しかし，Fig. 5.4∼Fig. 5.7 において，Xσ2 が大きくなるにつれて探索の不正効率が大きくなっていくことが確認できる．そして，信号源から遠い位置する端末ほど探索の不正効率が高いことが確認できる． Fig. 5.8 の Xσ2 =02 では，Fig. 5.3 での結果と異なり，探索の不成功率が大きいことが確認できる．そして，Fig. 5.4∼Fig. 5.7
において，Xσ2 が大きくなるにつれて探索の不成功率は微量ではあるが大きくなっていることが確認
できる．

65

Fig. 5.4: The result of random search strategy, Xσ2 =32

Fig. 5.5: The result of random search strategy, Xσ2 =62Fig. 5.6: The result of random search strategy, Xσ2 =92

66

Fig. 5.7: The result of random search strategy, Xσ2 =122

Fig. 5.8: The result of following the nearest node strategy, Xσ2 =02

Fig. 5.9: The result of following the nearest node strategy, Xσ2 =32

67

Fig. 5.10: The result of following the nearest node strategy, Xσ2 =62Fig. 5.11: The result of following the nearest node strategy. Xσ2 =92

Fig. 5.12: The result of following the nearest node strategy, Xσ2 =122

68

5.3.4

考察

Fig. 5.3∼Fig. 5.7 より Xσ2 が大きくなるにつれて，つまり通信環境が悪化するにつれて，探索の不成功率が大きくなる．これは，第 4 章で述べた誤判定率 λ が Xσ2 によって悪化しているためである．
しかし，信号源から遠い位置を移動開始する端末ほど探索の不正効率が高く，信号源から近い位置を移動開始する端末ほど探索の不正効率が低くなっている．これは，探索する距離に起因しているためである．探索する距離が長いほど，接近離反の誤判定する確率がたかくなるためである．

Fig. 5.8∼Fig. 5.12 より端末数が増えると探索の不成功率が大きくなる．これは，端末が移動する度に隣接端末の変更されるため，ステップ回数が増えてしまい，ステップ最大回数を超えてしまって探索失敗となっているためである．つまり，静止している端末の RSSI をもとに探索たほうが移動
範囲が広がらず，ステップ数がより少なくなるといえる．
ゆえに，RSSI を利用して探索することに対して，移動している端末の RSSI を利用して探索する
より静止している端末の RSSI を用いたほうが有利であり，かつ，通信距離が短いほうが有利である．つまり，以上のことから以下の知見を得られる．

• 静止している端末の RSSI をもとに探索したほうが移動範囲が広がらないため成功率がよい• 通信距離が短い端末の RSSI をもとに探索したほうが移動範囲が広くなる前に接近できるため成功率がよい
全端末が信号源を探索するには，それぞれがその目標に向かって探索する必要がある．しかし，信号源から通信距離が遠い位置で移動開始する端末が信号源へ探索するために，複数の中継端末から一部の端末を停止させ，その端末を探索してから信号源を探索するように協調して探索する戦略の提案が必要となると考える．

5.4

ランダム探索戦略と隣接端末追随探索戦略の特徴を組み合わせた探索

ここでは先のランダム探索戦略と隣接端末追随探索戦略の計算機シミュレーション結果から得られた知見に合致する中継端末固定探索戦略の計算機シミュレーションを行う．この戦略は信号源の探索を行う端末と停止する端末に分ける．停止する端末は複数ある中継端末から一部を停止させ，この停止する端末を固定中継端末と呼ぶこととする．
探索する端末は，信号源より中継端末の RSSI が大きい場合は，先ず，停止している中継端末の

RSSI を利用して固定中継端末を探索を行う．その探索後に，信号源の RSSI を利用してへ信号源を探索を行う．こうすることにより，静止している端末の RSSI をもとにした探索と通信距離が短い端末の RSSI をもとにした探索の 2 つ知見を満たすことができる．
一方，探索する端末が増えることになるため，ステップ回数，接近離反の判定を行う回数が増える
ことが予想される．しかし，短い通信距離の端末の探索のため，通信環境が悪化による探索失敗を抑えられると考える．

5.4.1

中継端末固定探索戦略

Fig. 5.13∼5.16 に中継端末固定探索戦略を示す．その戦略を 4 つに分類する．

69

• Fig. 5.13 は，信号源を含む端末数の 1/2 の端末番号の端末を固定中継端末とする．図では，6端末のため端末番号 3 の端末を固定中継端末としている．

• Fig. 5.14 は，端末番号が偶数の端末を固定中継端末とする．図では，端末番号 2 と 4 の端末を固定中継端末としている．

• Fig. 5.15 は，端末番号が奇数の端末を固定中継端末とする．図では，端末番号 3 と 5 の端末を固定中継端末としている．

• Fig. 5.16 は，全ての中継端末を固定中継端末とする．図では，端末番号 2∼5 の端末を固定中継端末としている．

Fig. 5.13: The strategy of following the fixed relay nodes, Case 1.

Fig. 5.14: The strategy of following the fixed relay nodes, Case 2.

70

Fig. 5.15: The strategy of following the fixed relay nodes, Case 3.

Fig. 5.16: The strategy of following the fixed relay nodes, Case 4.

71

5.4.2

検討条件

中継端末固定探索戦略の検討条件は 5.3.1 節と同条件とする．

5.4.3

シミュレーションの設定

中継端末固定探索戦略の評価は 5.3.2 節と同設定とする．

5.4.4

シミュレーションの結果

Fig. 5.17∼5.21 に中継端末固定探索戦略 (Fig. 5.13) のシミュレーション結果を示す．Fig. 5.22∼5.26に中継端末固定探索戦略 (Fig. 5.14) のシミュレーション結果を示す．Fig. 5.27∼5.31 に中継端末
固定探索戦略 (Fig. 5.15) のシミュレーション結果を示す．Fig. 5.32∼5.36 に中継端末固定探索戦
略 Fig. 5.16) のシミュレーション結果を示す．これらの図の横軸は探索に参加した端末番号，縦軸は探索不成功率 [%] である．

Fig. 5.17: The result of following the fixed relay nodes, Case 1, Xσ2 =02 .

Fig. 5.18: The result of following the fixed relay nodes, Case 1, Xσ2 =32 .

72

Fig. 5.19: The result of following the fixed relay nodes, Case 1, Xσ2 =62 .

Fig. 5.20: The result of following the fixed relay nodes, Case 1, Xσ2 =92 .

Fig. 5.21: The result of following the fixed relay nodes, Case 1, Xσ2 =122 .

73

Fig. 5.22: The result of following the fixed relay nodes, Case 2, Xσ2 =02

Fig. 5.23: The result of following the fixed relay nodes, Case 2, Xσ2 =32

Fig. 5.24: The result of following the fixed relay nodes, Case 2, Xσ2 =6274

Fig. 5.25: The result of following the fixed relay nodes, Case 2, Xσ2 =92

Fig. 5.26: The result of following the fixed relay nodes, Case 2, Xσ2 =122

Fig. 5.27: The result of following the fixed relay nodes, Case 3, Xσ2 =0275

Fig. 5.28: The result of following the fixed relay nodes, Case 3, Xσ2 =32

Fig. 5.29: The result of following the fixed relay nodes, Case 3, Xσ2 =62Fig. 5.30: The result of following the fixed relay nodes, Case 3, Xσ2 =9276

Fig. 5.31: The result of following the fixed relay nodes, Case 3, Xσ2 =122

Fig. 5.32: The result of following the fixed relay nodes, Case 4, Xσ2 =02

Fig. 5.33: The result of following the fixed relay nodes, Case 4, Xσ2 =32

77

Fig. 5.34: The result of following the fixed relay nodes, Case 4, Xσ2 =62Fig. 5.35: The result of following the fixed relay nodes, Case 4, Xσ2 =92

Fig. 5.36: The result of following the fixed relay nodes, Case 4, Xσ2 =122

78

考察

5.4.5
5.4.5.1

計算機シミュレーション結果の考察

Fig. 5.17∼5.36 より，中継端末固定探索戦略の結果は，ランダム戦略と隣接追随戦略と比べて不成功率は下回っていることがわかる．特に，Xσ2 が大きい無線環境が悪い環境で中継端末固定探索戦
略が勝っている．静止する中継端末が増えるほど，不正効率は下がる．つまり，先にシミュレーショ
ンで得られた知見を活かせる戦略になっているといえる．
ただし，Fig. 5.16 の中継端末固定探索戦略では，参加する端末数が増え，そして，Xσ2 が大きい
無線環境が悪い環境になるほど，不正効率が高くなる．これは，隣接する端末の探索は距離が短く移動範囲が広がらずに探索できるが，信号源までの各中継端末を探索していく．Xσ2 が大きい無線環境が悪い環境では，誤判定率が悪化し，信号源までの各中継端末を探索するため，移動範囲が広くなっている．つまり，先にシミュレーションで得られた知見を活かせてないといえる．
中継端末固定探索戦略の結果から，次の様にまとめらられる．

• 中継端末数が増加すると，探索者の探索成功率が悪化する• 中継端末の探索成功率は，中継端末数が増加すると探索者に遠い端末から探索成功率が向上していく• 中継端末数が 3∼6 台で，探索不正効率が最も低い
が，示されている．
これらの要因として，• 探索する端末数が増加するため，移動ステップ・距離の増加に起因する• 探索者から近距離に位置する中継端末ほど，移動ステップ・距離がかからずに済むことに起因するが考えられる．
ゆえに，これらの要因を解決するために，• 中継端末数: 3∼6 台• 端末間の間隔: 最大でおよそ 70 [m]が最適な配置と考える．

5.4.5.2

課題および展望マルチホップ接続の探索手法は，シングルホップ接続での探索の拡張させて，探索精度の観点から検討を行った．それには，2 つの課題が含まれており，１つ目は個々の探索精度，2 つ目は協調して探索する組織戦略である．本研究では，2 つ目の課題を検討した．1 つ目の課題は，シングルホップ
接続での探索で検討に含まれる．しかし，移動する目標物に対する探索精度を向上させることの課題がでてきた．そのため，この課題を回避させるために中継端末固定探索戦略を提案した．

79

Fig. 5.37: Representation of a wireless sensor network[65].
中継端末固定探索戦略の課題は 2 つあり，1 つ目は多数の端末が探索空間に散在するような空間 (ワイヤレスセンサーネットワーク，Fig. 5.37) でのルーティング方法である．ルーティングする端末の変化次第では，探索目標の中継端末の変更が多くなれば，探索に要するコストも増大すると考えられ
る．2 つ目は適切な位置の固定中継端末を探すことである．検討からも，固定中継端末が多すぎるの探索に要するコストも増大する．また，適切な位置の固定中継端末を探すのに，ホップ数，端末間距
離等で決定していくことになるが，さらに検討していく必要がある．
マルチホップ接続での探索の今後の展望として，移動経路や探索者が消費エネルギー (例えば，バッ
テリーなど) を効率的する動的経路計画の向上である．それには，探索空間に移動を妨げる障害物があるような空間や水中センサネットワーク [66] も検討の対象に入る．IOT デバイスが展開されているワイヤレスセンサーネットワークのよう環境では，頻繁にルーティングが変わることが多いと推測できることから，効率的する動的経路計画が重要な課題である．本研究がこの課題解決の一助になれることを信じている．

5.5

むすび

本節では複数の端末が協調した探索戦略について検討をした．複数の端末が協調して信号源へ探索する戦略を提案し比較評価を行った．その戦略は，各端末が信号源からの RSSI を利用して自律して探索するランダム探索戦略と，各端末は隣接する端末の RSSI を利用して探索する隣接端末追随探索戦略である．シミュレーションの結果，複数の端末が協調して信号源へ探索する戦略では以下が重要である:• 静止している端末の RSSI をもとに探索したほうが成功率がよい• 通信距離が短い端末の RSSI をもとに探索したほうが成功率がよい
この 2 つの性質を満たす戦略として中継端末固定探索戦略を提案した．この戦略は，信号源の探索を行う端末と停止する端末に分け，停止する端末は複数ある中継端末から一部を停止させることで，静止している端末の RSSI をもとにした探索と通信距離が短い端末の RSSI をもとにした探索の 2 つを満たすことができる．その戦略を停止する中継端末のパターンごとに 4 つに分類した．シミュレー

80

ションの結果，各パターンでの探索不正効率は，ランダム探索戦略と隣接端末追随探索戦略の結果を上回る成果を確認した．そして，これらの結果から中継端末数は 3∼6 台で端末間の間隔が最大でおよそ 70 [m] とすることが最適な配置として提案した．

81

第 6 章 結論

本論文は，無線通信時に得られる RSSI が通信距離によって値が異なることに着目し，信号源を効率的に探索する手法として接近離反判定を提案し，評価をした．
まず，探索する端末 (探索端末) 信号源のみで構成されるシングルホップ接続で検討した．探索端末
は同一直線上を等間隔に信号源の RSSI を取得しながら移動する．その RSSI の大小関係を利用することで信号源に対して接近もしくは離反できているかを判定する手法を提案した．第 3 章では，測定した RSSI を較正し，計測値の変動を表す値を判定猶予回数にすることで探索の精度および判定の精度の向上をはかった．計算機シミュレーションで検証を行い，探索の精度は較正を施さない RSSI
での結果より 1.67 倍精度が高いことを確認した．そして，迂回率の比較で，RSSI の較正を施してない場合は RSSI の較正を施した場合と比べて最大 3.63 倍の差であった．さらに，RSSI の較正を施さず，かつ，判定猶予回数を用いない場合は RSSI の較正を施し，判定猶予回数を用いた場合と比べて最大で 7.68 倍の差があった．これは，接近離反の判定猶予することが有効的に働いているためであり，探索が広範囲にならずに済んだため，迂回率は抑えることができた．また，接近離反の判定を猶予することで移動距離がかさむことが判定精度とトレードオフの関係にあることがわかった．しかし，本手法は測定した RSSI の較正を行う為に，手法が複雑化し，手間がかかる．そのため，より簡単に，RSSI の測定値だけで行える手法が期待される．
そして，第 4 章では，接近離反の判定に統計的仮説検定より判定猶予回数を算出した値を用いた．
その判定猶予回数は，2 通りを提案した．その判定猶予回数は，
手法 1) 接近か離反の確率モデルと測定地点ごとの RSSI からの標準偏差を用いた判定猶予回数
手法 2) N 段のリセット計数器から N に到達するまでの確率母関数 QN (Z) から算出した判定猶予
回数である．それぞれの判定猶予回数を誤判定率と迂回率の 2 つを利用して計算機シミュレーションで検証を行った．その結果，両手法で，接近離反の判定を猶予したほうが，猶予しないより誤判定率は上回る結果となった．具体的には，誤判定率は，同一地点で 100 回のサンプリングを行い，平均化を行った RSSI を用いて，判定の猶予を行わずに同様の探索を行った結果を比較をした．その結果，判定の猶予を行った場合は 0.25 以下であったに対し，判定の猶予を行わない場合はおよそ 0.5 で，およそ 2 倍であった．迂回率は，判定の猶予を行わなかった場合で探索が s max 以内に終了しない場合があった．つまり，判定の猶予を行った場合のほうが，広範囲に及ぶことなく探索できているためである．以上のことから，判定を猶予することの有効性が確認できた．
そして，DREAMS[48] と迂回率の比較をシングルホップ接続の構成で行った．手法 1) では，DREAMS の手法 1) に対する比は，およそ 1/26∼5/8 の移動距離の差があった．手法 2) では，DREAMS の固定および動的な判定猶予回数の手法 2) に対する比は，およそ 1/10 の移動距離の83

差があった．このことより，提案手法は従来手法の DREAMS より迂回率が上回っていることから，移動距離を低減できたことが確認できた．
また，手法 2) で動的な判定猶予回数は計測値の変動を表す値が小さいほど，誤判定が抑制されてないことを確認した．迂回率は，信号源近くで開始した探索では信号源を周回してしまう事で，迂回率を悪くしてたが，動的な判定猶予回数が探索開始位置に依存せずに迂回率が一定に保つための糸口になると考えられる．
次に，探索端末と信号源間を中継する中継端末で構成されるマルチホップ接続で検討した．第 5 章
では，アドホックネットワークで通信している中継端末を含む複数の端末が協調して信号源を探索す
る手法を検討することを目的として，複数の端末が協調して移動する組織戦略をから検討を行った．
その組織戦略は，ランダム探索戦略と隣接端末追随探索戦略を提案してシミュレーションで評価を行った結果，• 静止している端末の RSSI をもとに探索したほうが移動範囲が広がらないため成功率がよい• 通信距離が短い端末の RSSI をもとに探索したほうが移動範囲が広くなる前に接近できるため成功率がよいという，知見が得られた．これらの評価から得られた知見より，中継端末固定探索戦略を提案した．
この戦略は，探索する端末は，信号源より中継端末の RSSI が大きい場合は，先ず，停止している中継端末の RSSI を利用して固定中継端末を探索を行う．その探索後に，信号源の RSSI を利用してへ信号源を探索を行う．こうすることにより，静止している端末の RSSI をもとにした探索と通信距
離が短い端末の RSSI をもとにした探索の 2 つ知見を満たすことができる．そして，中継端末固定探索戦略では，停止させる中継端末の分類を行い，次の結果を得られたことで，中継端末数は 3∼6 台，
端末間の間隔は最大で 70 [m] が最適な配置である考察した．

a) 中継端末数が増加すると，探索者の探索成功率が悪化するb) 中継端末の探索成功率は，中継端末数が増加すると探索者に遠い端末から探索成功率が向上していくc) 中継端末数が 3∼6 台で，探索不正効率が最も低い
最後に，本論文では信号源の探索を効率的に行うための検討を行ったきた．本手法は，無線通信時に入手できる RSSI から接近離反判定が可能であるため，幅広い無線方式でも適用可能である．しかし，本論文では障害物がある環境を想定されておらず，今後その検討が必要と考える．その障害物がある環境を想定した経路計画についていくつか提案されている．virsual ruler[67] は，自動車 (Vehicle) の前方と後方に Beacon 電波を発する機器を搭載し，位置が不明な端末は受信機が搭載されていることが想定されている．Vehicle が対象区域を任意に移動することで距離推定を行う．Vehicle で移動することで，障害物を避けられている．Snake − like[68] は，SCAN，HILBERT[45] の静的経路計画に障害物に直面した際に移動方向を変更することを加えたものである．そして，Visibility Binary

Tree (VBT)[69] は探索するロボットと目標物間に複数の円形の障害物があると想定して，その円形障害物の内/外の縁に沿って目標物までの最短経路を探すアルゴリズムである．以上，既存の障害物

84

がある環境を想定した経路計画は，周辺の障害物を検知するためにレーダー，ソナー，レザー，赤外線，カメラ等のハードウェアが装備されていることが想定されている [43]．
今後，以上の提案を障害物のある環境への適用も含めて実現に向けて検討を進めていく．

85

謝辞

本研究は，情報セキュリティ大学院大学博士前期課程時代 (2006 年 4 月 ∼2008 年 3 月) の研究をもとに，2012 年 4 月に博士後期課程に入学後，約 8 年 (内 2 年は休学) にわたって取り組んだ研究をまとめたものです．研究と仕事との両立が厳しい場面も多々あり，くじけそうなことも途中何度もありましたが，紆余曲折を経て，どうにか論文の形にまとめることができました．
ここに至るまでに，修士時代からずっと根気よくご指導頂いてきた佐藤直名誉教授のお力添えあってのことです．そして，修行期間が残り 1 年半で私を引き受けてくれました松井俊浩教授に厚く御礼申し上げます．また，審査を担当していただいた大久保隆夫教授ならび土井洋教授に厚く感謝を申し上げます．私のような不出来な学生を長期間ご指導頂いたことは御礼の言葉に言い表すことができないほど程であります．
ゼミや輪講などで様々な助言や研究の励みをいただきました佐藤研究室，松井研究室，橋本研究室，そして，情報セキュリティ大学院大学の皆様にも重ねて感謝いたします．
最後に，毎日帰りが遅く休日も研究活動に専念していた私に対して，いつも笑顔で生活面を支えてくれた妻に深く感謝いたします．

87

参考文献[1] 総務省, 情報通信白書平成 23 年度版, http : / / www . soumu . go . jp / johotsusintokei /whitepaper/ja/h23/index.html, 2011, Online; accessed 28 February 2020.
[2] 間瀬憲一，阪田史郎, アドホック・メッシュネットワーク: ユビキタスネットワーク社会の実現に向けて. コロナ社, 2007.

[3] C.-K. Toh, アドホックモバイルワイヤレスネットワーク: プロトコルとシステム. 構造計画研究所, 2003.

[4] 総務省, 非常時のアドホック通信ネットワークの活用に関する研究会, 非常時のアドホック通
信ネットワークの活用に関する研究会, http://www.soumu.go.jp/main_sosiki/kenkyu/

adhocnw/index.html, 2016, Online; accessed 28 February 2020.
[5] B. Hofmann-Wellenhof, H. Lichtenegger, and J. Collins, Global positioning system: theory andpractice. Springer Science & Business Media, 2012.
[6] H. Hu and N. Wei, “A study of gps jamming and anti-jamming,” in 2009 2nd international
conference on power electronics and intelligent transportation system (PEITS), IEEE, vol. 1,
2009, pp. 388–391.
[7] Oﬃcial U.S. government information about the Global Positioning System (GPS), Selective
availability, https : / / www . gps . gov / systems / gps / modernization / sa/, 2018, Online;
accessed 28 February 2020.
[8] A. Boukerche, H. A. Oliveira, E. F. Nakamura, and A. A. Loureiro, “Localization systems for
wireless sensor networks,” wireless Communications, IEEE, vol. 14, no. 6, pp. 6–12, 2007.
[9] A. Kalis and T. Antonakopoulos, “Direction finding in ieee802. 11 wireless networks,” IEEE
Transactions on Instrumentation and Measurement, vol. 51, no. 5, pp. 940–948, 2002.
[10] B. N. Hood and P. Barooah, “Estimating doa from radio-frequency rssi measurements using
an actuated reflector,” IEEE Sensors Journal, vol. 11, no. 2, pp. 413–417, 2010.
[11] A. Kulaib, R. Shubair, M. Al-Qutayri, and J. W. Ng, “An overview of localization techniques
for wireless sensor networks,” in 2011 International Conference on Innovations in Information
Technology, IEEE, 2011, pp. 167–172.
[12] N. A. Azmi, S. Samsul, Y. Yamada, M. F. M. Yakub, M. I. M. Ismail, and R. A. Dziyauddin,“A survey of localization using rssi and tdoa techniques in wireless sensor network: Systemarchitecture,” in 2018 2nd International Conference on Telematics and Future Generation
Networks (TAFGEN), IEEE, 2018, pp. 131–136.

89

[13] K. Whitehouse and D. Culler, “Calibration as parameter estimation in sensor networks,” inProceedings of the 1st ACM international workshop on Wireless sensor networks and applications, 2002, pp. 59–67.
[14] A. Savvides, C.-C. Han, and M. B. Strivastava, “Dynamic fine-grained localization in ad-hoc
networks of sensors,” in Proceedings of the 7th annual international conference on Mobile
computing and networking, 2001, pp. 166–179.
[15] T. He, C. Huang, B. M. Blum, J. A. Stankovic, and T. Abdelzaher, “Range-free localization schemes for large scale sensor networks,” in Proceedings of the 9th annual international
conference on Mobile computing and networking, ACM, 2003, pp. 81–95.
[16] J. Bachrach and C. Taylor, “Localization in sensor networks,” Handbook of sensor networks:
Algorithms and Architectures, vol. 1, pp. 277–289, 2005.
[17] S. Simic and S. Sastry, “Distributed localization in wireless ad hoc networks,” Technical
Report UCB/ERL, Tech. Rep., 2002.
[18] N. B. Priyantha, A. K. Miu, H. Balakrishnan, and S. Teller, “The cricket compass for contextaware mobile applications,” in Proceedings of the 7th annual international conference on
Mobile computing and networking, ACM, 2001, pp. 1–14.
[19] D. Niculescu and B. Nath, “Ad hoc positioning system (aps) using aoa,” in INFOCOM 2003.
Twenty-Second Annual Joint Conference of the IEEE Computer and Communications. IEEE
Societies, IEEE, vol. 3, 2003, pp. 1734–1743.
[20] V. Ramadurai and M. L. Sichitiu, “Localization in wireless sensor networks: A probabilistic
approach.,” in International conference on wireless networks, 2003, pp. 275–281.
[21] J. Albowicz, A. Chen, and L. Zhang, “Recursive position estimation in sensor networks,” inProceedings Ninth International Conference on Network Protocols. ICNP 2001, IEEE, 2001,
pp. 35–41.
[22] D. Niculescu and B. Nath, “Ad hoc positioning system (aps),” in Global Telecommunications
Conference, 2001. GLOBECOM’01. IEEE, IEEE, vol. 5, 2001, pp. 2926–2931.
[23] N. B. Priyantha, A. Chakraborty, and H. Balakrishnan, “The cricket location-support system,” in Proceedings of the 6th annual international conference on Mobile computing andnetworking, 2000, pp. 32–43.
[24] L. Doherty, L. El Ghaoui, et al., “Convex position estimation in wireless sensor networks,” inProceedings IEEE INFOCOM 2001. Conference on Computer Communications. Twentieth
Annual Joint Conference of the IEEE Computer and Communications Society (Cat. No.
01CH37213), IEEE, vol. 3, 2001, pp. 1655–1663.
[25] M. L. Sichitiu and V. Ramadurai, “Localization of wireless sensor networks with a mobile
beacon,” in 2004 IEEE international conference on mobile Ad-hoc and sensor systems (IEEECat. No. 04EX975), IEEE, 2004, pp. 174–183.

90

[26] 伊藤誠悟，佐藤弘和，河口信夫, “無線 lan の受信電波強度分布間類似度による方向推定手法,”
情報処理学会論文誌, vol. 47, no. 1, pp. 51–62, 2006.

[27] 金谷健一, これなら分かる最適化数学: 基礎原理から計算手法まで. 共立出版, 2005.
[28] 多田和夫, 探索理論. 日科技連出版社, 1973.
[29] 東日本電信電話株式会社, 電気通信事業法第 33 条第 2 項及び第 7 項に基づく第 1 種指定電気通信設備との接続に関する契約約款 技術的条件集別表 11.13 専用回線ノード装置インタフェー
ス仕様 (新超高速専用回線ノード装置インタフェース仕様 (sdh 方式)), https://www.ntt-

east.co.jp/info-st/constip/cons1/, 1999, Online; accessed 28 February 2020.
[30] 菅原真司，山岡克式，酒井善則, “超分散情報探索手法に対する探索打ち切りの効果,” 電子情報通信学会技術研究報告. CQ, コミュニケーションクオリティ, vol. 98, no. 331, pp. 1–6, 1998.

[31] National Coordination Oﬃce for Space-Based Positioning, Navigation, and Timing, Oﬃcial
u.s. government information about the global positioning system (gps) and related topics,
https://www.gps.gov/, 2020, Online; accessed 28 February 2020.
[32] G. Zussman and A. Segall, “Energy eﬃcient routing in ad hoc disaster recovery networks,” inIEEE INFOCOM 2003. Twenty-second Annual Joint Conference of the IEEE Computer andCommunications Societies (IEEE Cat. No. 03CH37428), IEEE, vol. 1, 2003, pp. 682–691.
[33] K. Tateishi and T. Ikegami, “Estimation method of attenuation constant during localizationin rssi,” in 2008 International Symposium on Communications and Information Technologies,
IEEE, 2008, pp. 482–487.
[34] A. Ali, L. A. Latiﬀ, and N. Fisal, “Gps-free indoor location tracking in mobile ad hoc network(manet) using rssi,” in 2004 RF and Microwave Conference (IEEE Cat. No. 04EX924), IEEE,
2004, pp. 251–255.
[35] G. Mao, B. D. Anderson, and B. Fidan, “Path loss exponent estimation for wireless sensor
network localization,” Computer Networks, vol. 51, no. 10, pp. 2467–2483, 2007.
[36] T. S. Rappaport et al., Wireless communications: principles and practice. prentice hall PTR
New Jersey, 1996, vol. 2.
[37] S. Čapkun, M. Hamdi, and J.-P. Hubaux, “Gps-free positioning in mobile ad hoc networks,”
Cluster Computing, vol. 5, no. 2, pp. 157–167, 2002.
[38] S. Gezici, “A survey on wireless position estimation,” Wireless personal communications,vol. 44, no. 3, pp. 263–282, 2008.
[39] N. Bulusu, J. Heidemann, J. Heidemann, D. Estrin, and T. Tran, “Self-configuring localization
systems: Design and experimental evaluation,” ACM Transactions on Embedded Computing
Systems (TECS), vol. 3, no. 1, pp. 24–60, 2004.
[40] D. Niculescu and B. Nath, “Dv based positioning in ad hoc networks,” Telecommunication
Systems, vol. 22, no. 1-4, pp. 267–280, 2003.

91

[41] K. Ishii and N. Sato, “Gps-free host approaching in mobile ad-hoc networks,” in 2013 SeventhInternational Conference on Innovative Mobile and Internet Services in Ubiquitous Computing, IEEE, 2013, pp. 108–115.
[42] G. Mao, B. Fidan, and B. D. Anderson, “Wireless sensor network localization techniques,”
Computer networks, vol. 51, no. 10, pp. 2529–2553, 2007.
[43] G. Han, J. Jiang, C. Zhang, T. Q. Duong, M. Guizani, and G. K. Karagiannidis, “A survey on
mobile anchor node assisted localization in wireless sensor networks,” IEEE Communications
Surveys & Tutorials, vol. 18, no. 3, pp. 2220–2243, 2016.
[44] S. Halder and A. Ghosal, “A survey on mobile anchor assisted localization techniques inwireless sensor networks,” Wireless Networks, vol. 22, no. 7, pp. 2317–2336, 2016.
[45] D. Koutsonikolas, S. M. Das, and Y. C. Hu, “Path planning of mobile landmarks for localization in wireless sensor networks,” Computer Communications, vol. 30, no. 13, pp. 2577–2592,
2007.
[46] R. Huang and G. V. Zaruba, “Static path planning for mobile beacons to localize sensor
networks,” in Fifth annual IEEE international conference on pervasive computing and communications workshops (PerComW’07), IEEE, 2007, pp. 323–330.
[47] K. Kim, B. Jung, W. Lee, and D.-Z. Du, “Adaptive path planning for randomly deployedwireless sensor networks.,” J. Inf. Sci. Eng., vol. 27, no. 3, pp. 1091–1106, 2011.
[48] X. Li, N. Mitton, I. Simplot-Ryl, and D. Simplot-Ryl, “Dynamic beacon mobility schedulingfor sensor localization,” Parallel and Distributed Systems, IEEE Transactions on, vol. 23,
no. 8, pp. 1439–1452, 2012.
[49] B. Xiao, H. Chen, and S. Zhou, “A walking beacon-assisted localization in wireless sensor networks,” in 2007 IEEE International Conference on Communications, IEEE, 2007, pp. 3070–
3075.
[50] J. J. Carr, Joe Carr’s Receiving Antenna Handbook. HighText Publications, 1993.
[51] 丸田力男, “フレーム同期保護回路の設計法に関する考察,” 電子情報通信学会論文誌 A, vol. 56,
no. 1, pp. 17–24, 1973.
[52] 佐藤直, “同期安定度を改善するフレーム同期方式の提案,” 電子情報通信学会論文誌 B, vol. 67,
no. 4, pp. 432–438, 1984.
[53] H. T. Friis, “A note on a simple transmission formula,” proc. IRE, vol. 34, no. 5, pp. 254–256,
1946.
[54] K.Ishii and N.Sato, “Approaching a target using a protection feature based on received signal strength indicator,” in Proceedings of 5th the International Conference on Operations
Research and Enterprise Systems - Volume 1: ICORES, INSTICC, 2016, pp. 170–177.

92

[55] V. Jacobson, “Congestion avoidance and control,” ACM SIGCOMM computer communication
review, vol. 18, no. 4, pp. 314–329, 1988.
[56] 守倉正博，久保田周治, 802.11 高速無線 LAN 教科書. インプレス R&D, 2004.
[57] K. Fall and K. Varadhan, The ns manual. notes and documentation on the software ns2simulator, https://www.isi.edu/nsnam/ns, 2002, Online; accessed 28 February 2020.
[58] 石井和行，佐藤直，松井俊浩, “Rssi を用いた信号源への接近離反判定の信頼性を上げる方法の提案,” 電気学会論文誌 C (電子・情報・システム部門誌), vol. 140, no. 6, 2020.

[59] 高橋徹，北村泰彦，巳波弘佳, “劣通信環境下における災害救助エージェントの組織,” 情報処理学会論文誌, vol. 53, no. 11, pp. 2379–2387, 2012.

[60] T. Komatsu, T. Ohkubo, K. Kobayashi, K. Watanabe, and Y. Kurihara, “A study of rssibased formation control algorithm for multiple mobile robots,” in Proceedings of SICE Annual
Conference 2010, IEEE, 2010, pp. 1127–1130.
[61] H.-J. Im, C.-E. Lee, Y.-J. Cho, and S. Kim, “Rssi-based control of mobile cooperative robots
for seamless networking,” in 2012 12th International Conference on Control, Automation and
Systems, IEEE, 2012, pp. 980–982.
[62] H. Li, J. Wang, X. Li, and H. Ma, “Real-time path planning of mobile anchor node in
localization for wireless sensor networks,” in 2008 International Conference on Information
and Automation, IEEE, 2008, pp. 384–389.
[63] F. Zhao, H.-y. Luo, and L. Quan, “A mobile beacon-assisted localization algorithm based on
network-density clustering for wireless sensor networks,” in 2009 Fifth International Conference on Mobile Ad-hoc and Sensor Networks, IEEE, 2009, pp. 304–310.
[64] H. Wang, W. Qi, K. Wang, P. Liu, L. Wei, and Y. Zhu, “Mobile-assisted localization by stitching in wireless sensor networks,” in 2011 IEEE International Conference on Communications(ICC), IEEE, 2011, pp. 1–5.
[65] Wikipedia, Wireless sensor network, https://en.wikipedia.org/wiki/Wireless_sensor_
network, 2020, Online; accessed 28 February 2020.
[66] H. Li, Y. He, X. Cheng, H. Zhu, and L. Sun, “Security and privacy in localization for underwater sensor networks,” IEEE Communications Magazine, vol. 53, no. 11, pp. 56–62, 2015.
[67] Y. Ding, C. Wang, and L. Xiao, “Using mobile beacons to locate sensors in obstructed environments,” Journal of Parallel and Distributed Computing, vol. 70, no. 6, pp. 644–656,
2010.
[68] S. M. Mazinani and F. Farnia, “Localization in wireless sensor network using a mobile anchor
in obstacle environment,” International Journal of Computer and Communication Engineering, vol. 2, no. 4, p. 438, 2013.

93

[69] A. T. Rashid, A. A. Ali, M. Frasca, and L. Fortuna, “Path planning with obstacle avoidance
based on visibility binary tree algorithm,” Robotics and Autonomous Systems, vol. 61, no. 12,
pp. 1440–1449, 2013.

94

研究業績

査読付学術論文（1）石井 和行，佐藤 直，松井 俊浩,

RSSI を用いた信号源への接近離反判定の信頼性を上げる方法の提案 , 電気学会論文誌 C (電子・情報・システム部門誌), Vol.140, No. 6,

2020.

査読付き国際会議（1） Kazuyuki Ishii, Naoshi Sato, ”GPS-Free Host Approaching in Mobile Ad-

Hoc Networks,”

In Proceedings of 2013 Seventh International Conferenceon Innovative Mobile and Internet Services in Ubiquitous Computing (IMIS),
pp. 108 - 115, 3-5 July 2013.
（2） Kazuyuki Ishii, Naoshi Sato, ”Approaching a Target using a Protection Fea-ture based on Received Signal Strength Indicator,” In Proceedings of 5th
the International Conference on Operations Research and Enterprise Systems (ICORES), pages 170-177, 23-25 February 2016.

国内会議（1）石井 和行, 佐藤 直，”シングルホップアドホックネットワークにおける RSSI を利用した対象端末への駆けつけ方式の検討,” マルチメディア，分散協調とモバイルシンポジウム

2014 論文集 (2014), 1785-1791, 2014-07-02.
（2）石井 和行, 佐藤 直，”大規模自然災害時を想定したアドホックネットワークにおける協調
駆けつけ方式の研究,” 第 77 回全国大会講演論文集 2015(1), 53-54, 2015-03-17.
（3）石井 和行, 佐藤 直，”劣悪な通信環境における受信信号強度の階差を探索の打ち切りに用いた発信者への駆けつけの研究,” 第 15 回情報科学技術フォーラム 2016 論文集 (2016),

A-014, 2016-09-07.
（4）石井 和行, 松井 俊浩, ”受信信号強度を接近離反判定に用いた保護段数の研究,” 電気学会研究会資料, ST 2019(1-11), 31-36, 2019-06-01.

95

その他の研究業績（1） Y.Okada, K.Ishii, N.Sato,

Proposal of SNS Membership Qualification Sys-

tem Using Security Information Database,

Asia Pacific & MEA Cup 2013，

Mar. 2013.
（2）岡田 康義, 石井 和行, 佐藤 直,
案,

情報セキュリティDB を用いた SNS 会員資格制度の提電子情報通信学会技術研究報告 = IEICE technical report : 信学技報 113(33),

11-16, 2013-05-16.
（3）小出 雄太, 佐藤 直, 石井 和行,

災害時におけるアドホックネットワークを利用した被災者

駆けつけ方式の計算機シミュレーション,

電子情報通信学会技術研究報告. USN, ユビキ

タス・センサネットワーク: IEICE technical report 110(378), 107-112, 2011-01-13.
（4）小出 雄太, 佐藤 直, 石井 和行,
特性の一検討,M-063 アドホックネットワークを用いた協調駆けつけ

情報科学技術フォーラム講演論文集 8(4), 387-388, 2009-08-20.

（5）佐藤 直, 石井 和行,

アドホックネットワークにおける駆けつけ方式の一検討,

全国大会講演論文集 第 71 回 (ネットワーク), 63-64, 2009-03-10.
（6）佐藤 直, 石井 和行,

M-004 アドホックネットワークにおける発信者探索の一検討,

情

報科学技術フォーラム講演論文集 7(4), 177-178, 2008-08-20.
（7）石井 和行, 佐藤 直,の検討,

B-21-9 アドホックネットワークにおける発信者探索アルゴリズム

電子情報通信学会総合大会講演論文集 2008 年通信 (2), 610, 2008-03-05.

（8）石井 和行, 佐藤 直,

B-21-11 無線アドホックネットワークにおける発信者位置への駆けつけ方式の基本検討, 電子情報通信学会ソサイエティ大会講演論文集 2007 年通信 (2),413, 2007-08-29.

96

付図

1.1

The hill-climbing of primary variable function. . . . . . . . . . . . . . . . .

6

1.2

Do not react the extremum. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

1.3

The Search model classification. . . . . . . . . . . . . . . . . . . . . . . . . .

8

2.1

The expectation value. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

3.1

RF specifications, Xσ =3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18

3.2

RF specifications, Xσ =6. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18

3.3

RF specifications, Xσ =9. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18

3.4

RF specifications, Xσ =12. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

3.5

General concept of PLE estimation by using LSM. . . . . . . . . . . . . .

20

3.6

Typical situation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21

3.7

Host approaching model. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22

3.8

Variance of RSSI readings at each range [a, b]. . . . . . . . . . . . . . . . .
ˆ with using the variance.
Compare large and small between P̂i and Pi−1

23

3.10 The reset counter and change the direction. . . . . . . . . . . . . . . . . .

24

3.11 RMSE with Calibration. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

3.12 RMSE without Calibration. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

3.13 RMSE without Calibration and N =1. . . . . . . . . . . . . . . . . . . . . .

27

3.14 An example of RSSI readings. . . . . . . . . . . . . . . . . . . . . . . . . . .

28

3.15 The ratio of detour with Calibration. . . . . . . . . . . . . . . . . . . . . . .

29

3.16 The ratio of detour without Calibration. . . . . . . . . . . . . . . . . . . . .

29

3.17 The ratio of detour without Calibration and N =1. . . . . . . . . . . . . .

30

4.1

An example of approach/departure judgment. . . . . . . . . . . . . . . . .

37

4.2

A relationship between pi and N . . . . . . . . . . . . . . . . . . . . . . . . .

41

4.3

An example of trajectory in static moratorium steps (N = 4). . . . . . .

44

4.4

An example of trajectory in dynamic moratorium steps.

. . . . . . . . .

45

4.5

The misjudgment rate in Moratorium steps 1. . . . . . . . . . . . . . . . .

45

4.6

The misjudgment rate in α=0.01 in Moratorium steps 2. . . . . . . . . .

46

4.7

The misjudgment rate in α=0.05 in Moratorium steps 2. . . . . . . . . .

46

4.8

The misjudgment rate in α=0.1 in Moratorium steps 2. . . . . . . . . . .

47

4.9

The detour ratio in Moratorium steps 1. . . . . . . . . . . . . . . . . . . . .

47

3.9

i

24

4.10 The detour ratio in α=0.01 in Moratorium steps 2. . . . . . . . . . . . . .

48

4.11 The detour ratio in α=0.05 in Moratorium steps 2. . . . . . . . . . . . . .

49

4.12 The detour ratio in α=0.1 in Moratorium steps 2. . . . . . . . . . . . . . .

49

4.13 The relationship of the communication distance - N in α = 0.01. . . . . .

50

4.14 The relationship of the communication distance - N in α = 0.05. . . . . .

50

4.15 The relationship of the communication distance - N in α = 0.1.

. . . . .

51

4.16 The relationship of the communication distance - pi in α = 0.01. . . . . .

51

4.17 The relationship of the communication distance - pi in α = 0.05 . . . . .

52

4.18 The relationship of the communication distance - pi in α = 0.1 . . . . . .

52

4.19 The relationship of the communication distance - N . . . . . . . . . . . . .

53

4.20 The relationship of the communication distance - pi . . . . . . . . . . . . . .

53

4.21 The misjudgment rate in N = 1. . . . . . . . . . . . . . . . . . . . . . . . . .

58

4.22 The detour ratio in N = 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

59

5.1

The random search strategy. . . . . . . . . . . . . . . . . . . . . . . . . . . .

62

5.2

The strategy of following the nearest node. . . . . . . . . . . . . . . . . . .

63

5.3

The result of random search strategy, Xσ2 =02 . . . . . . . . . . . . . . . . .
The result of random search strategy, Xσ2 =32 . . . . . . . . . . . . . . . . .
The result of random search strategy, Xσ2 =62 . . . . . . . . . . . . . . . . .
The result of random search strategy, Xσ2 =92 . . . . . . . . . . . . . . . . .
The result of random search strategy, Xσ2 =122 . . . . . . . . . . . . . . . .
The result of following the nearest node strategy, Xσ2 =02 . . . . . . . . .
The result of following the nearest node strategy, Xσ2 =32 . . . . . . . . .
The result of following the nearest node strategy, Xσ2 =62 . . . . . . . . .
The result of following the nearest node strategy. Xσ2 =92 . . . . . . . . .
The result of following the nearest node strategy, Xσ2 =122 . . . . . . . . .

65

5.13 The strategy of following the fixed relay nodes, Case 1. . . . . . . . . . .

70

5.14 The strategy of following the fixed relay nodes, Case 2. . . . . . . . . . .

70

5.15 The strategy of following the fixed relay nodes, Case 3. . . . . . . . . . .

71

5.16 The strategy of following the fixed relay nodes, Case 4. . . . . . . . . . .

71

The result of following the fixed relay nodes, Case 1, Xσ2 =02 . . . . . . . .
The result of following the fixed relay nodes, Case 1, Xσ2 =32 . . . . . . . .
The result of following the fixed relay nodes, Case 1, Xσ2 =62 . . . . . . . .
The result of following the fixed relay nodes, Case 1, Xσ2 =92 . . . . . . . .
The result of following the fixed relay nodes, Case 1, Xσ2 =122 . . . . . . .
The result of following the fixed relay nodes, Case 2, Xσ2 =02 . . . . . . .
The result of following the fixed relay nodes, Case 2, Xσ2 =32 . . . . . . .
The result of following the fixed relay nodes, Case 2, Xσ2 =62 . . . . . . .

72

5.4
5.5
5.6
5.7
5.8
5.9
5.10
5.11
5.12

5.17
5.18
5.19
5.20
5.21
5.22
5.23
5.24

ii

66
66
66
67
67
67
68
68
68

72
73
73
73
74
74
74

5.25 The result of following the fixed relay nodes, Case 2, Xσ2 =92 . . . . . . .

75

5.26 The result of following the fixed relay nodes, Case 2, Xσ2 =122

. . . . . .

75

5.27 The result of following the fixed relay nodes, Case 3, Xσ2 =02 . . . . . . .

75

The result of following the fixed relay nodes, Case 3, Xσ2 =32 . . . . . . .
The result of following the fixed relay nodes, Case 3, Xσ2 =62 . . . . . . .
The result of following the fixed relay nodes, Case 3, Xσ2 =92 . . . . . . .
The result of following the fixed relay nodes, Case 3, Xσ2 =122 . . . . . .
The result of following the fixed relay nodes, Case 4, Xσ2 =02 . . . . . . .
The result of following the fixed relay nodes, Case 4, Xσ2 =32 . . . . . . .
The result of following the fixed relay nodes, Case 4, Xσ2 =62 . . . . . . .
The result of following the fixed relay nodes, Case 4, Xσ2 =92 . . . . . . .
The result of following the fixed relay nodes, Case 4, Xσ2 =122 . . . . . .

76

5.37 Representation of a wireless sensor network[65]. . . . . . . . . . . . . . . .

80

5.28
5.29
5.30
5.31
5.32
5.33
5.34
5.35
5.36

iii

76
76
77
77
77
78
78
78

付表

1.1

Category of Localization Algorithm . . . . . . . . . . . . . . . . . . . . . . .

3

3.1

Simulation Specifications. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

3.2

Starting positions of searcher.

. . . . . . . . . . . . . . . . . . . . . . . . . .

26

3.3

Ratio of ”RMSE with Calibration” to ”RMSE without Calibration”. .

28

3.4

Ratio of ”with Calibration” to ”without Calibration”. . . . . . . . . . . .

31

3.5

Ratio of ”with Calibration” to ”without Calibration and N=1”.

. . . .

31

4.1

List of parameters using the search algorithm. . . . . . . . . . . . . . . . .

38

4.2

Starting positions of searcher . . . . . . . . . . . . . . . . . . . . . . . . . . .

41

4.3

Parameters in (4.16) and (4.17) . . . . . . . . . . . . . . . . . . . . . . . . .

42

4.4

Simulation parameters. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

43

4.5

η of Moratorium steps 1 and DREAMS. . . . . . . . . . . . . . . . . . . . .

54

4.6

η of Moratorium steps 1 and DREAMS with averaged RSSI. . . . . . . .

55

4.7

η of Moratorium steps 2 (Static, α=0.01) and DREAMS with averaged
RSSI. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.8

η of Moratorium steps 2 (Static, α=0.05) and DREAMS with averaged
RSSI. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.9

55

56

η of Moratorium steps 2 (Static, α=0.1) and DREAMS with averaged
RSSI. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

56

4.10 η of Moratorium steps 2 (Dynamic, α=0.01) and DREAMS with averaged RSSI. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

57

4.11 η of Moratorium steps 2 (Dynamic, α=0.05) and DREAMS with averaged RSSI. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

57

4.12 η of Moratorium steps 2 (Dynamic, α=0.1) and DREAMS with averaged
RSSI. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

58

5.1

Parameters in (5.1) and (5.2). . . . . . . . . . . . . . . . . . . . . . . . . . .

64

5.2

Specification of simulation. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

65v