論 文

論 文

無人飛行体による災害復旧ネットワークにおける 正規化相互相関を用いた複数メッセージ収集点決定法

檀上 梓紗

^†a)

原 晋介

^†b)

松田 崇弘

^††c)

小野 文枝

^†††d)

A Multiple Data Collection Points Selection Method

Using a Normalized Crosscorrelation in a UAV Enabled Disaster Recovery Network

Azusa DANJO

^†a)

, Shinsuke HARA

^†b)

, Takahiro MATSUDA

^††c)

, and Fumie ONO

^†††d)

あらまし 大規模災害が発生し，多くの人々が避難所での生活を余儀なくされた場合，避難者の安否確認のた めに，災害発生後すぐに構築できる代替の情報ネットワークが必要不可欠となる．無人飛行体(UAV: Unmanned

Aerial Vehicle)を利用することにより，安否確認メッセージをワイヤレスに収集できるが，避難所は同一地域に多

数指定されており，効率的にメッセージを収集できる複数の地点を決定する必要がある．そこで，本論文では受 信信号強度(RSS: Received Signal Strength)の正規化相互相関を利用した複数収集点決定法を提案する．また，実 験値による性能評価を行い，経路長及びデータ収集時間の観点での提案法の有用性を示す．更に，計算回数にお いても有利であることを示す．

キーワード 無人飛行体，災害復旧ネットワーク，受信信号強度，正規化相互相関

1.

ま え が き

2011

年に発生した東日本大震災では，電力，ガス，

水道や道路などのライフラインやインフラの壊滅的な 被害により約

47

万人が避難者となっている

[1]

．また，

情報ネットワークに注目すると，地上の情報通信ネッ トワークの完全復旧には約

1

か月かかっている

[2]

．こ のように，大規模災害が発生した場合，多くの人々が 避難所での生活を余儀なくされ，地上の情報通信イン フラは長期的に遮断される可能性が今後も高いことを 考えると，避難者の安否確認のために，災害発生後す

†大阪市立大学大学院工学研究科，大阪市

Graduate School of Engineering, Osaka City University, 3–3–138 Sugimoto, Sumiyoshi-ku, Osaka-shi, 558–8585 Japan

††東京都立大学大学院システムデザイン研究科，日野市

Graduate School of Systems Design, Tokyo Metropolitan University, 6–6 Asahigaoka, Hino-shi, 191–0065 Japan

†††情報通信研究機構ワイヤレスネットワーク総合研究センター，横浜 市

Wireless Networks Research Center, National Institute of Information and Com- munications Technology, 3–4 Hikarino Oka, Yokosuka-shi, 239–0847 Japan a) E-mail: [email protected]

b) E-mail: [email protected] c) E-mail: [email protected] d) E-mail: [email protected]

DOI:10.14923/transcomj.2020GWP0007

ぐに構築できる代替の情報ネットワークを準備してお くことが必要不可欠となる．

一方，我が国では，内閣府が

2016

年から小型の無人 飛行体

(UAV: Unmanned Aerial Vehicle)

に対してロー ドマップを策定しており，最新の改定によると，

2022

年度以降に目視外・有人地帯での飛行（レベル

4

^）が 許可される見込みである

[3]

．

UAV

は，道路が遮断さ れている場合でも被災地まで到達することが可能であ り，また，避難所に避難者からの安否確認メッセージ を蓄積するためのサーバと無線機を設置している自治 体もある

[4]

．これらのことを考慮に入れると，無線通 信機器を搭載した

UAV

が拠点から避難所まで飛行し 上空でホバリングしながら安否確認メッセージを収集 するような臨時の情報通信ネットワークが大いに期待 できる

[5]

．

UAV

が拠点を出発し，複数の避難所を巡りながら安 否確認メッセージを収集する場合の問題として，

UAV

の飛行時間が短く，現状で

20–40

分に制限されている ことが考えられる

[6]

．限られた時間で安否確認メッ セージを効率良く収集するためには，拠点から避難所 への移動及び安否確認メッセージ収集の二つの側面か ら問題解決にあたらなければならない．

電子情報通信学会論文誌 ©一般社団法人電子情報通信学会

自動車を利用する場合のように，避難所でメッセー ジを収集する位置が道路上に限定されている場合は，

運搬経路問題

(VRP: Vehicle Routing Problem) [7]

^を解 くことにより，最適なメッセージ収集経路は決定でき る．しかしながら，無線を使って

UAV

でメッセージ を収集する場合は，避難所でメッセージを収集する 位置は

3

次元空間上で自由に決定できるので，メッ セージを効率良く収集できる点をまず決定しておく必 要がある．一般的に，無線品質は受信信号強度

(RSS:

Received Signal Strength)

の増加関数であるため，メッ セージを効率良く収集するには，避難所の無線機から の信号に対する

RSS

が高い点をメッセージ収集点と して決定し，そこでホバリングしながらメッセージを 収集するべきである．そのメッセージ収集点を決定す る方法として，筆者らはテンソル再構成に基づいた方 法を提案した

[8]

．この方法では，メッセージの収集前 に，対象とする領域で無線機からの信号に対する

RSS

のセンシングを疎に行い，

RSS

^マップを

3

^{階テンソル} とみなして再構成した後，

RSS

が高くなるメッセージ 収集点を決定する．

[8]

において，我々は実験結果を用 い，対象領域の

25%

で

RSS

のセンシングを行うだけ で，複数の無線機からのメッセージを効率良く収集で きる単一のメッセージ収集点を決定できることを示し た．しかしながら，この方法では，送信機数が増加し た場合，それらの信号に対する

RSS

が同時に高くな るような単一のメッセージ収集点を選択しても，全て の信号に対して

RSS

が十分高くならないので，メッ セージが効率良く収集できなくなる．このような場合 は，

RSS

が十分高くなるような複数のメッセージ収集 点を選択するべきである．

そこで本論文では，複数のメッセージ収集点を

RSS

マップ間の正規化相互相関を利用して決定する方法を 提案する．複数の送信機に対する複数のメッセージ収 集点の決定問題は，厳密には組合せ最適化問題を解く 必要があり計算回数が莫大となるが，提案法の計算回 数は

RSS

センシング点数の線形関数で与えられる．ま た，提案法は従来法である単一メッセージ収集点を選 択する方法

[8]

をサブクラスとして含んでいる．以下，

2.

では本提案法で用いるモデル及び仮定について説明 し，

3.

で問題設定を行う．

4.

で提案法を二つ提案し，

5.

でその性能評価を行う．

6.

では本論文の結論を示す．

2.

モデル及び仮定

2. 1

^{システムモデル}

無線機を搭載した

UAV

が，複数の避難所に設置さ れているサーバに蓄積された安否確認メッセージを収 集するモデルを想定する．以下では，サーバを送信機 と呼び，安否確認メッセージをデータを呼ぶ．このモ デルはセンシングステージ及びデータ収集ステージで 構成され，センシングステージでは

UAV

が複数地点 で送信機からの信号の

RSS

をセンシングする．また，

データ収集ステージでは，センシングステージで得た

RSS

を利用してデータ収集点を決定し，その地点で データ収集を行う．

2. 2 UAV

及びレイアウトモデル

図

1

はレイアウトモデルであり，ここには

3

次元 領域

F

，

P

台の静止した送信機

(TX)

と

1

台の飛行す る

UAV

がある．

F

の大きさは

Xm × Y m × Zm

であ り，大きさ

∆Xm × ∆Ym × ∆Z m

^{のボクセルで分割さ} れている．

N

₁，

N

₂ 及び

N

₃をそれぞれ

x

軸，

y

^軸及 び

z

軸方向の分割数とすると，

F

を構成するボクセル 数は合計

N

₁

× N

₂

× N

₃

= N

_v個となる．ボクセルのラ ベルは

l = i + N

₁

( j − 1 ) + N

₁

N

₂

( k − 1 ) (l = 1 , 2 , . . ., N

_v

, i = 1 , 2, . . . N

₁

, j = 1, 2, . . . N

₂

, k = 1, 2, . . . N

₃

)

^とし，

l

番目のボクセルの重心を

G

_l

= [ x

_i

, y

j

, z

_k

]

^⊤，その

集合を

G = {G

1

, G

₂

, . . ., G

_Nv

}

^{と定義する．以下で}

は，ボクセルの重心を単に点と呼ぶ．また，

P

台の送 信機は

F

の外側に配置し，

p

番目の送信機の位置を

S

p

= [X

p

, Y

p

, Z

p

]

^⊤

(p = 1, 2, . . ., P)

^{とし，その集合を}

図1 レイアウトモデル Fig. 1 Layout model.

S = { S

₁

, S

₂

, . . ., S

_P

}

^{と定義する．}

センシングステージでは，

UAV

は

G

^から

M

個の点 を選択し

(M ≤ N

_v

)

^{，それぞれの点で}

P

^{台の送信機か} らの信号に対して

RSS

をセンシングする．

m

番目の センシング点を

U

_m

(m = 1, 2, . . ., M )

とし，その集合

を

U = { U

₁

, U

₂

, . . ., U

_M

}

と定義する．更に，このと

きのセンシングレートを

B

_sense

= M / N

_vと定義する．

なお，ここでいう

RSS

は，送受信機が静止している場 合に，それらの周りの建物分布等の物理的な環境から 決定される距離減衰とシャドウイングによる成分を含 み，時間的な瞬時値変動であるフェージングによる成 分は含まないものとする．

一方，データ収集ステージでは，

UAV

^は

U

^から

Q

個の点を選択し

(Q ≤ M )

，それぞれの点でデータを収 集する．

q

番目のデータ収集点を

W

_q

(q = 1, 2, . . ., Q)

とし，その集合を

W = { W

₁

, W

₂

, . . ., W

_Q

}

^と定義 する．また，

W

_q でデータ収集が行われる送信機の 集 合 を

S

q

= {S

q1

, S

_q2

, . . ., S

_{q Pq}

}

^，

S

q の 集 合 族 を

S^c

= {S

1

, S

2

, . . ., S

Q

}

と定義する．ここで，全ての

送信機は重複なくどれかのデータ収集点でデータ収集 されることが必要であるので，直和を

⊕

^と表すと

S = S

1

⊕ S

2

⊕ · · · ⊕ S

Q

(1)

が成立している．このとき，

W

_qでデータ収集が行わ れる送信機の個数を

P

_q

(P

₁

+ P

₂

+ · · · + P

_Q

= P)

と定 義する．更に，

UAV

は一定速度

v

^{で移動し，}

G

_aから

G

_bへの移動にかかる時間を

T

^f

(G

a

, G

_b

)

^{と定義する．}

2. 3

無線通信モデル

セ ン シ ン グ ス テ ー ジ で ，

p

番 目 の 送 信 機 か ら の 信 号 を

U

_m で セ ン シ ン グ す る 場 合 ，そ の

RSS

を

R ( U

_m

, S

_p

) dBm

と 定 義 す る ．以 下 で は ，

R

Sp

= {R(U

1

, S

p

), R(U

2

, S

p

), . . ., R(U

M

, S

p

)}

^を

p

番目の送信 機の

RSS

マップと呼び，

R

Sp の

U

mの要素を

R

Sp

Um

= R(U

m

, S

p

) (2)

と定義する．特に，

M = N

_vの場合を全

RSS

マップ，

一方，

M < N

_vの場合を部分

RSS

マップと呼ぶ．なお，

U

_mで

RSS

をセンシングするのに必要な時間を

T

^s

( U

_m

)

と定義とし，

T

^s

(U

1

) = T

^s

(U

2

) = · · · = T

^s

(U

M

) = T

^s と仮定する．

一方，データ収集ステージで，

p

番目の送信機のデー タを

W

_qで収集する場合，データ伝送速度は

R ( W

_q

, S

_p

)

の関数となる．したがって，この関数を

f ( R ( W

_q

, S

_p

))

とし，そのデータサイズを

D

_p

bits

と定義すると，デー タ収集に必要な時間は

T

^c

(W

q

, S

_p

) = D

_p

/ f (R(W

q

, S

_p

)) (3)

で与えられる．なお，

D

₁

= D

₂

= · · · = D

_Q

= D

と仮 定する．

3.

問 題 設 定

3. 1

センシングステージ

UAV

が

U

₁

, U

₂

, . . ., U

_M の順に訪問する場合，

U

^の

決定問題は総センシング時間の最小化問題として定式 化でき，

find U ⊆ G ˆ which minimizes

∑

M m=1

T

^s

(U

m

) +

^M−1

∑

m=1

T

^f

(U

m

, U

_m+1

) (4)

と書ける．このときの総センシング経路長

L

^sは，

U

a から

U

_bへの経路長を

L

_ab

= ∥U

b

− U

a

∥

^{と定義する} と，以下のように表すことができる：

L

^s

=

M

∑

−1 m=1

∥U

_m+1

− U

m

∥. (5)

3. 2

データ収集ステージ

UAV

が

W

₁

, W

₂

, . . ., W

_q

, . . ., W

_Qの順に訪問する場

合，

W

^とScの決定問題は，総データ収集時間の最小 化問題として定式化でき

find W ⊆ U, ˆ

_S

ˆ

^c

which minimizes

∑

Q q=1

∑

Sp∈Sq

T

^c

(W

q

, S

_p

) +

^Q−1

∑

q=1

T

^f

(W

q

, W

_q+1

) (6)

と書ける．このときの総データ収集経路長

L

^cは，以 下のように表すことができる：

L

^c

=

Q

∑

−1 q=1

∥W

_q+1

− W

_q

∥. (7)

4.

提 案 解 法

4. 1

センシングステージ

センシング点間の移動時間とセンシング時間には

T

^f

≫ T

^sが成立するので，この最小化問題は総センシ ング経路長

L

^sの最小化問題として

find U ⊆ G ˆ which minimizes

L

^s

=

^M−1

∑

m=1

∥ U

_m+1

− U

_m

∥ (8)

と書ける．本論文では，遺伝的アルゴリズムに基づい た

3

次元の巡回セールスマン問題の解法

[9]

を利用し て

UAV

の経路を決定する．

UAV

が

U

₁からセンシン グを開始し，

M

点のセンシング地点を訪問した後に

U

_M+1

= U

₁へ帰還する経路を考え，新たに総センシ ング経路長

L

^sを以下のように閉路として定義する：

L

^s

=

∑

M m=1

∥U

_m+1

− U

m

∥. (9)

また，センシング地点は

G

^から

M

点ランダムに選択

して

U = {U

^′1

, U

^′₂

, . . ., U

^′_M

}

^{を構成し，総センシン}

グ経路長

L

^sが最短経路となるように

U

^{を並び替え} て

U

^を

randomly select U ⊆ G then U = arg min

U=U

L

^s

(10)

のように構成する．

4. 2

データ収集ステージ

避難所の収容人数の合計が約

5

万人の大阪市住吉 区でデータ収集を行う場合，一人当りのデータ量を

300kBytes

と仮定すると，全てのデータをデータ伝送

速度

54Mbps

で収集できたとしてもデータの収集に

40

分程度かかるが，データ収集点間の移動時間は

UAV

が時速

40km

以下で移動したとしても，

20

分程度とな る

[10]

．また，例えば

6Mbps

程度でしか収集できな いような環境下ではデータ収集時間は

300

分以上かか ると考えれる．実際には，これらの値は，一人当りの データ量，避難所の収容人数，

UAV

の移動速度等様々 な要因に依存するが，本論文では上記の想定に基づき

T

^c

≫ T

^fを仮定する．このとき，この問題はデータ収 集時間の和の最小化問題に置き換えられる：

W, ˆ

_S

ˆ

c

= arg min

W ⊆U,^Sc

∑

Q q=1

∑

Sp∈Sq

D / f ( R ( W

_q

, S

_p

)).

(11)

4. 2. 1

全 探 索 法

W

^とScの全ての組合せを列挙し，その中からデー タ収集時間の和を最小にする組合せを探索する方法を 考える．与えられた

Q

に対して

W

^{に含まれるデータ}

収集点の総数は

N

_W

=

M

C

_Q

(12)

であり，一方，

Q

個の要素からなるS^cの総数は第

2

種スターリング数

[11]

N

_S^c

= S ( P , Q ) = 1 Q!

∑

Q n=1

(− 1 )

^Q−nQ

C

_n

n

^P

(13)

で与えられるので，探索すべき組合せの総数は

N

_W

×N

S^c

である．これらを全て探索して最適な組合せを探す方 法は総データ収集時間の下界となり，全探索

(BS: Brute

Search)

法と呼ぶ．この計算のステップ数は最小でも

O ( P × M

^Q

)

^{となるため（付録}

1.

^参照），

M

が大きい場 合，この方法により解を求めることは現実的でない．

4. 2. 2

相 関 法

与えられた

W

^{，Scに対し，}

S

_p内の送信機に対す る

f ( R ( W

_q

, S

_p

))

^{の最小値を}

f

_min,q

( R ( W

_q

, S

_p

))

^とす る．

W

q でのデータ収集時間を決定する支配要因は，

T

^c

(W

q

, S

p

)

^{の最大値，すなわち}

f

_min,q

(R(W

q

, S

p

))

^で あると仮定する．このとき，データ収集時間の最小化 問題を

f

_min,q

( R ( W

_q

, S

_p

))

^{の全データ収集点}

W

^上で の総和が最大となる問題と考える．したがって，この 問題は次式のように定式化できる：

W, ˆ

_S

ˆ

^c

= arg max

W ⊆U,^Sc

∑

Q q=1

f

_min,q

( R (W

q

, S

p

)). (14)

f

_min,q

(R(W

q

, S

_p

))

^は

R(W

q

, S

_p

)

^{の増加関数となっ} ていることから，上記の最適化問題を更に簡単にする ため，データ伝送速度の和ではなく，

RSS

の和を最大 化する問題に置き換える：

W, ˆ

_S

ˆ

c

= arg max

W ⊆U,^Sc

R

^c

(15)

R

^c

=

∑

Q q=1

R

_q^c

(16)

R

^c_q

= min

Sp∈Sq

R

Sp

Wq

. (17)

一般に，データ伝送速度は

RSS

の線形関数とはなって いないため，このような近似は厳密にデータ収集時間 を最小化しているとはいえない．

UAV

で受信する信号 の

SNR

を

γ

とすると，雑音電力を一定値と仮定したと き，

γ

^は

RSS

に比例した値となる．通信路容量に関す るシャノン限界により，データ伝送速度は

log

₂

( 1 + γ)

に比例した値として表されると仮定する．また，上記 の最適化問題において，

RSS

は

dBm

の単位で扱って いる．つまり，データ伝送速度の和を

RSS

^の和に置 き換えるということは，評価関数を

log

₂

(1 + γ)

^から

10 log

₁₀

(γ)

に置き換えることに等しい．したがって，

γ

^が

1

よりも十分に大きい場合には，式

(15)–(17)

の 最適化問題は式

(14)

と同等の最適化問題を扱っている と考えることができる．

上記のように近似的な最適化問題を用いることが真 に妥当であるかは，両者を比較して検討する必要があ る．しかし，本論文の目的は両者の比較よりも後に述 べる正規化相互相関を使うことの有効性を示すことに あり，この妥当性検証は本論文で扱う範囲を超えてい るため，今後の課題とする．

R

Sp と

R

Sp′の正規化相互相関を

ρ( p , p

^′

) = Cov(R

Sp

, R

Sp′

)

σ

_RSp

σ

_RSp′

(p, p

^′

= 1, 2, . . ., P, p , p

^′

) (18)

と定義する．ここで，

Cov (X, Y)

^は

X

^と

Y

^{の共分散，}

σ

_X^は

X

^{の標準偏差を表す．}

互いの

RSS

マップの相関が高い複数の送信機から は同一の点でデータを収集できると考えられる．すな

わち，S^c

= {S

1

, S

2

, . . ., S

Q

}

は，同一の要素に含まれ

る送信機間の

RSS

マップが高い相関をもち，一方，異 なる要素に含まれる送信機間の

RSS

マップが低い相 関をもつように分割すればよい．したがって，相関の しきい値を

ρ

thとし，

find

_S

ˆ

c

subject to

{ ρ(p, p

^′

) ≥ ρ

th

(S

p

, S

p^′

∈ S

q

, p , p

^′

)

ρ(p, p

^′

) < ρ

th

(S

p

∈ S

q

, S

_p′

∈ S

q^′

, p , p

^′

) (q, q

^′

= 1, 2, . . ., Q, q , q

^′

)

で分割できる．なお，この問題は，送信機を頂点とし，

RSS

マップの相関が

ρ

th以下の頂点間を辺でつないだ 無向グラフを考えることにより，彩色数を

Q

に固定 したグラフ彩色問題

[12]

として定式化できる（付録

2.

参照）．

S

ˆ

^cが決まったので，

W

^は

W

qに対する個別の最大 化問題

W ˆ

_q

= arg max

Wq∈U

R

_q^c

(q = 1, 2, . . ., Q) (19)

R

_q^c

= min

Sp∈Sˆq

R

Sp

Wq

(20)

を解くことによって決定できる．この方法の計算回 数は

O(P

²

× M )

^{であり（付録}

3.

参照），相関

(CO:

Correlation)

法と呼ぶ．

なお，これらの方法で得られた解は最短経路を与え ないので，センシングステージの解法と同じように，

3

次元の巡回セールスマン問題の解法を利用して

UAV

の経路を決定する．そのため，

UAV

は

W

₁からデータ 収集を始め，

Q

点でデータを収集した後に

W

_Q+1

= Q

₁ へ帰還する閉路として，総データ収集経路長を

L

^c

=

∑

Q q=0

∥ W

_q+1

− W

_q

∥ (21)

と再定義し，

L

^cが最短経路となるようにデータ収集点 を最終的に並び替えるものとする．

式

(9)

，

(21)

より，提案法では，センシングステー ジ，データ収集ステージのそれぞれにおいて，センシ ング点，データ収集点の始点から開始して，始点へ帰 還するルートを決定しており，センシング点の終了点 からデータ収集ステージの始点へのルートについては 考えていない．これは，実際にはセンシングステージ を効果的に実施し，更にはデータ収集ステージにおい て大容量データを収集する可能性を考慮し，

UAV

を センシングステージ及びデータ収集ステージにおいて 周回させることを想定しているからである．これらの ルートは周回ルートとして得られることから，データ 収集ステージの始点をセンシングステージの終了点と 最も近い点とすることにより，上記の問題については 回避できる．

5.

実験及び性能評価

提案法の性能評価のため，大阪市立大学にて実験を 行った．図

2

にその写真を示す．

7

台の

2.4GHz

^帯

Wi-

Fi [13]

の送信機を図

2 (a)–(f)

に示すよう屋内の窓際に 設置し，屋外でセンシングを行った．なお，

UAV

の飛行 が禁止されているエリアであるため，図

2 (g)

に示すよ う

UAV

の代わりに受信機

(RX)

をポールの先端に取り 付けた．センシング領域の大きさは

X = 30m, Y = 8m,

Z = 10m

であり，その

x

軸，

y

^軸及び

z

軸をそれぞ れ

2m

間隔（付録

4.

）で分割し

(∆X = ∆Y = ∆Z = 2m,

N

₁

= 15, N

₂

= 4, N

₃

= 5)

，送信機からの信号の

RSS

を

N

_v

= 300

点でセンシングした．なお，同一センシング

図2 実 験 環 境 Fig. 2 Photos of the experiment.

点では，

RSS

の大きな時間的変動は観測されなかった が，

RSS

は十分時間を離して

10

回センシングした値 の中央値とした．表

1

に実験諸元を示す．

図

3

に各送信機に対して得られた

RSS

マップを示 す．実験で得られた全

RSS

マップからボクセルをラン ダムに

M(= ⌊N

v

× B

sense

⌋)

^個選択し

(0 < B

sense

≤ 1)

， 部分

RSS

マップを作成するものをランダムセンシング

(RS: Random Sensing)

と呼び，その部分

RSS

マップに 対して，相関法を適用した方法をランダムセンシング

/

相関

(RS/CO)

法と呼ぶ．

RS/CO

法の結果は試行回数 を

1000

回とし，中央値を示した．ここで，

B

sense

= 1

とした場合は全

RSS

マップになるが，これを全領域 センシング

(FS: Full Sensing)

と呼び，全探索法を適用 した方法を全領域センシング

/

全探索

(FS/BS)

法，相 関法を適用した方法を全領域センシング

/

相関

(FS/CO)

法と呼ぶ．提案手法は

MATLAB [14]

により実装して いる．

[10]

で は ，避 難 所 一 箇 所 に つ き ，平 均 約

D =

400Mbytes

のデータを収集することを想定しており，

全てのデータを収集するために

UAV

は

4

周程度する 必要があることが示されている．本論文では一度の

表1 実 験 諸 元 Table 1 Specifications of experiment.

実験場所 大阪市立大学

領域サイズ X=30m×Y=8m×Z=10m センシング間隔

∆X=∆Y=∆Z=2m N1=15,N2=4,N3=5, N_v=300

送信機台数(P) 7

無線通信ツール 2.4GHz帯Wi-Fi アンテナ ダイポール 受信回数 10回

飛行で全てのデータ収集を行うことを想定しており，

UAV

の飛行時間が

20–40

分であることを考慮して，

データサイズを

D = 100Mbytes

とする．想定よりデー タサイズが小さい場合は，今回のアルゴリズムでは

T

^c

≫ T

^f を想定しているので，データサイズが大き い方が提案している手法がより効果的であるが，飛行 に充てられる時間が増えるため，更にデータ収集点を 増やすことが可能であると考えられる．一方，データ サイズが想定より大きくなった場合は，一度に全ての データを回収できず，複数回周回する必要があると考 えられる．また，

IEEE 802.11-2016

標準規格（帯域幅

図3 RSSマップ(Bsense=0.25) Fig. 3 RSS maps (Bsense=0.25).

図4 Bsenseに対する総センシング経路長(L^s) Fig. 4 Dependency of the total sensing route length (L^s) on the

RSS sensing rate (Bsense).

20MHz

）

[15]

を仮定して

RSS R dBm

に対するデータ 伝送速度

f ( R ) Mbps

として以下を採用した：

f (R) =

 

 



 

 



6 . 5 (− 82 ≤ R < − 79 ) 13.0 (−79 ≤ R < −77) 19.5 (−77 ≤ R < −74) 26.0 (−74 ≤ R < −70) 39 . 0 (− 70 ≤ R < − 66 ) 52 . 0 (− 66 ≤ R < − 65 ) 58.5 (−65 ≤ R < −64) 65.0 (−64 ≤ R)

. (22)

図

4

に

B

_senseに対する総センシング経路長を示す．

B

senseの増加に対して，総センシング経路は線形に増

加しており，

FS/CO

法と比較して

B

_sense

= 0.5

^でも総 センシング経路長を約

40%

短縮できることがわかる．

図

5

に

B

_senseに対する総データ収集時間を示す．な

お，総データ収集時間は決定したデータ収集点におけ る式

(3)

の和であり，

T

_total

=

∑

Q q=1

∑

Sp∈Sq

T

^c

(W

q

, S

_p

) (23)

と書ける．また，

Q = 1

のときのデータ収集は単一の 点で行われるため，

RS/CO

法で

Q = 1

とした結果は従 来法に相当する．更に，

FS/BS

法で

Q = 7

とした場合，

総データ収集時間は下界となる．図

5

では，

B

_sense及 び

Q

の増加に伴い総データ収集時間は減少しており，

B

_sense

= 0.25

でほぼ一定に収束していることが確認で

きる．これは，

B

_senseを増加させることでデータ収集 点の候補が増え，

RSS

が高くなるデータ収集点を選択 できるからである．一方，

Q

が少ない場合，総データ

図5 Bsenseに対する総データ収集時間(Ttotal)

Fig. 5 Dependency of total data collection time (Ttotal) on the RSS sensing rate (Bsense).

図6 データ収集点数(Q)に対する総データ収集時間(Ttotal) Fig. 6 Dependency of total data collection time (Ttotal) on the

number of data collection points (Q).

収集時間が小さくならないのは，

RSS

が同時に高くな るようなデータ収集点を選択しても，全ての送信機に 対して

RSS

が十分高くならないためである．

Q = 3

と した場合は，下界と比較して，

B

_sense

= 0 . 25

で総デー タ収集時間の増加は

30%

である．一方，図

4

から，こ の場合の総センシング経路長は全領域センシングの総 センシング経路長と比較して

70%

短い．そこで，以

降では

B

_sense

= 0.25

^{と設定する．}

図

6

にデータ収集点数に対する総データ収集時間を 示す．なお，

FS/BS

法の結果は各データ収集点数

(Q)

における総データ収集時間の最小値を表している．各

Q

ごとに

FS/BS

法と

FS/CO

法の総データ収集時間を 比較すると，

Q = 2

のときに

FS/CO

法は

FS/BS

法と 比較して

10%

増加することがわかる．このとき，そ れぞれの方法で選択されたデータ収集点の

RSS

を比

図7 データ収集点数(Q)に対する総データ収集経路長 (L^c)

Fig. 7 Dependency of the total data collection route length (L^c) on the number of data collection points (Q).

較すると，

FS/BS

法での

RSS

の最小値は，

FS/CO

法 の

RSS

の最小値よりも低くなっているが，

RSS

の最 大値は

FS/CO

法の

RSS

の最大値よりも高くなってい ることが確認できた．つまり，この誤差は各点におい て

RSS

の最小値のみを考慮してデータ収集点を選択し たことにより発生したと考えられる．また，

FS/BS

法 及び

FS/CO

法は

Q = 5

以上で一定となっており，こ の値が総データ収集時間の下界である．

RS/CO

法の総 データ収集時間は

Q = 7

でその下界と一致することが わかる．更に，

Q = 1

のとき

RS/CO

法の総データ収 集時間は下界と比較して約

100%

増加するが，

Q = 3

ではその増加を約

30%

に抑えることができる．

図

7

に

RS/CO

法におけるデータ収集点数に対する 総データ収集経路長を示す．

Q = 3

では

Q = 7

，つま り各送信機に対して最適なデータ収集点を選択する場 合と比較して総データ収集経路長を

50%

短縮できる．

最後に，計算回数の比較を行った，与えられたパラメー タ値，

N

_v

= 300

，

B

_sense

= 0 . 25

，

M = 75 ( = N

_v

× B

_sense

)

，

P = 7

と

Q = 3

に対して，

BS

法と

CO

法の計算回数 はそれぞれ

3.0 × 10

⁶と

4.0 × 10

⁴となり，

BS

法に比 較して，

CO

法は計算回数を

10

²分の

1

にできる．

6.

む す び

本論文では，

RSS

の正規化相互相関を利用した複数 のデータ収集点決定法を提案した．実験値による経路 長及びデータ収集時間の比較により，

7

台の送信機で データ収集を行う場合，全領域をセンシングすれば，

CO

法によりデータ収集点

5

点で総データ収集時間を 最小にできることを示した．また，

25%

センシングで

データ収集点を

3

点とした場合，下界と比較してデー タ収集時間を約

30%

を増加させるだけで，総センシ ング経路長を

70%

短縮できることを示した．また，そ のときの

CO

法の計算回数は

BS

法の

10

²分の

1

とな ることを示した．

本論文では

UAV

の消費エネルギーを考慮せず，

UAV

が必ず一度にセンシング及びデータ収集が可能である バッテリーを搭載していることを仮定して経路長を算 出している．しかし，実際は避難所は広域に分布して いることが多く，

UAV

が帰還できない可能性がある ため，

UAV

の消費エネルギーを考慮する必要がある．

また，本論文では，データ収集点数

Q

は事前に与えら れた値を用いており，

Q

の決定方法自体については検 討していないが，実際には避難所の密集度合い等の要 因により決定されるべき値である．更に，センシング 点はランダムに選択するという手法を用いているが，

RSS

値の空間相関の強さに応じてセンシング点を離し て配置するなど，効果的な選択手法が存在する．以上 のことから，本研究の今後の課題として，

UAV

の消費 エネルギーを考慮したルート設計法，データ収集点数 の決定方法，及びセンシング点の選択方法等が挙げら れる．

謝辞 本研究の一部は，科学研究費補助金（基盤研 究

B

課題番号

JP18H01445

，

JP19H04096

）及び公益財 団法人アイコム電子通信工学振興財団から助成を受け て行われた．

文 献

[1] 復 興 庁 ，“避 難 所 生 活 者・避 難 所 の 推 移（ 東 日 本 大 震 災 ，阪 神・淡 路 大 震 災 及 び 中 越 地 震 の 比 較 ），” https:

//www.reconstruction.go.jp/topics/hikaku2.pdf，Oct. 2011.

[2] 総務省，“平成23年版情報通信白書，” https://www.soumu.

go.jp/johotsusintokei/whitepaper/ja/h23/html/nc111100.html

[3] 内閣府，“小型無人機の利用活用と技術開発のロードマップ，”

https://www.kantei.go.jp/jp/singi/kogatamujinki/pdf/siryou12.pdf [4] M. Takai, J. Martin, S. Kaneda, and T. Maeno, “Scenargie as a network simulator and beyond,” J. Inf. Process., vol.27, pp.2–9, Jan. 2019. DOI: 10.2197/ipsjjip.27.2

[5] A.M. Hayajneh, S.A.R. Zaidi, D.C. McLernon, M. Di Renzo, and M. Ghogho, “Performance analysis of UAV enabled disaster recov- ery networks: a stochastic geometric framework based on cluster processes,” IEEE Access, vol.6, pp.26215–26230, May 2018. DOI:

10.1109/ACCESS.2018.2835638 [6] DJI, https://www.dji.com/

[7] P. Toth and D. Vigo, eds., The Vehicle Routing Problem, Society for Industrial and Applied Mathematics, 2002.

[8] A. Danjo, S. Hara, T. Matsuda, and F. Ono, “A Tensor Completion- Based Selection Method of a Single Data Collection Point for Multiple Shelters in a UAV Enabled Disaster Recovery Network,”

Proc. 12th Int. Conf. Advances in Satellite and Space Commun.

(SPACOMM 2020), pp.7–12, Lisbon, Portugal, Feb. 2020.

[9] J. Grefenstette, R. Gopal, B. Rosmaita, and D.V. Gucht, “Genetic algorithms for the traveling salesman problem,” Proc. 1st Int. Conf.

Genetic Algorithms and their Applications, pp.160–168, 1985.

[10] A. Danjo, A. Murata, S. Hara, T. Matsuda, and F. Ono, “Con- struction of a temporary message collection system using a drone for refugees in a large-scale disaster,” Proc. 2020 IEEE 91st Veh. Technol. Conf., pp.1–5, May 2020. DOI: 10.1109/VTC2020- Spring48590.2020.9128632

[11] D.E. Knuth, The Art of Computer Programming, Volume 1: Fun- damental algorithms, Third Edition, Addison-Wesley, 1997.

[12] 久保幹雄，ジョア（ジョアン）・ペドロ・ペドロソ，村松 正和，アブドル・レイス，あたらしい数理最適化，近代科 学社，2016.

[13] Wi-Fi Alliance, https://www.wi-fi.org/

[14] MATLAB, MathWorks, https://mathworks.com/

[15] IEEE Standard for Information technology Telecommunications and information exchange between systems Local and metropoli- tan area networks Specific requirements Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) speci- fications, 2016.

[16] A. Mawira, “Models for the spatial correlation functions of the (log)-normal component of the variability of VHF/UHF field strength in urban environment,” Proc. 3rd IEEE Int. Symp. Per- sonal, Indoor and Mobile Radio Commun., Boston, MA, USA, pp.436–440, Oct. 1992. DOI: 10.1109/PIMRC.1992.279892 [17] P. Taaghol and R. Tafazolli, “Correlation model for shadow fading

in land-mobile satellite systems,” Electron. Lett., vol.33, no.15, pp.1287–1289, July 1997. DOI: 10.1049/el:19970905 [18] L. Liu, C. Tao, D.W. Matolak, T. Zhou, and H. Chen, “Investigation

of shadowing effects in typical propagation scenarios for high- speed railway at 2350MHz,” Int. J. Antennas Propag., Hindawi Publishing Corporation, Oct. 2016. DOI: 0.1155/2016/8782671 [19] M Series, ITU 2135-1, “Guidelines for evaluation of radio interface

technologies for IMT-Advanced,” 2009.

付 録

1. BS

法の計算回数

W

^とScの一つの組合せに対して，式

(11)

で，総デー タ収集時間を計算するのに必要な計算回数は

2P − 1

で与えられる．これは

W

^{とScの全ての組合せに必} 要になるので，全ての総データ伝送時間を列挙する ために必要となる計算回数は

(2P − 1) × N

_W

× N

S^cと なる．更に，全ての総データ伝送時間から最小値を探 索するのに必要な計算回数は

N

_W

× N

_S^c

− 1

で与えら れるので，式

(11)

を計算するのに必要な計算回数は

2P × N

_W

× N

S^c

− 1

となる．

N

_W の計算量が

O(M

^Q

)

で与えられ，

N

S^c

≥ 1

であることを考慮に入れると，

最小の計算量は

O ( P × M

^Q

)

^となる．

2. CO

法のグラフ彩色問題としての定式化 送信機を頂点とした無向グラフ

G (V, E)

^{を考える．}

ここで，頂点の集合

V

^は

V = {v

1

, v

2

, . . ., v

P

} (A · 1)

であり，一方，辺の集合

E

^は

E = { e

_αβ

|α, β = 1 , 2 , . . ., P , α > β} (A · 2) e

_αβ

=

{

0 (ρ(α, β) ≥ ρ

_th

)

1 (ρ(α, β) < ρ

th

) (A·3)

のように相関が低い頂点だけを辺でつなぐ．このとき，

0

と

1

の

2

値をとる変数

h

_pqを導入することにより，

P

個の頂点の集合を，辺でつながれていない頂点を一 つの集合の要素とした

Q

個の集合に分割する問題に帰 着できる．すなわち，

h

_pqの決定問題として

arg min

hp q

∑

vα,vβ∈V

e

_αβ

(= 0 ) (A · 4)

subject to { ∑

Q

q=1

h

_pq

= 1

h

_αq

+ h

_βq

≤ 1 + e

_αβ

(A · 5)

のように定式化できる．ただし，

ρ

thは

Q

個の集合に 分割されるまで変化させる必要がある．

1

回の計算で 変化させる

ρ

thの幅を

0 < ∆ ρ < 1

と定義すると，

ρ

th の決定問題は二分探索で求めることができ，計算回数 は最大で

log

₂

(2/ ∆ ρ) = 1 − log

₂

∆ ρ

^となる．

頂点の組合せは

N

S^c通りである．また，一つの組合 せに対して，異なる二つの頂点の全ての組合せに対し て辺が存在するかを調べる必要があり，その計算回数 は_p

C

₂で与えられるので，合計の計算回数は

N

_gcp

= P

²

× (1 − log

₂

∆ ρ) (A·6)

となる．

3. CO

法の計算回数

送信機

2

台の一つの組合せに対して，式

(18)

の計算 回数は

O ( M )

である．この計算を異なる送信機の全て の組合せ，_P

C

₂通りに対して行う必要があるので総計 算回数は

N

_ρ

= P

²

× M (A · 7)

となる．また，一つの

q

に対して，式

(20)

で，

W

_qの 全ての要素に対して

R

^c_qを計算するのに必要な回数は

( P

_q

− 1 ) × M

であり，式

(19)

で，それらから最大値を 探索するのに必要な計算回数は

M − 1

である．した

がって，

S

1

, S

2

, . . ., S

Qのそれぞれに対して最小値を

探索するのに必要となる計算回数の和は

N

_min−max

=

∑

Q q=1

{(P

q

− 1)M + (M − 1)}

= PM − Q (A·8)

となる．ゆえに，相関法の計算量は，式

(A · 6)–(A · 8)

よ り

M

の支配的な項だけを残すと

O ( P

²

× M )

^となる．

4.

空間センシング間隔

マイクロ波帯無線信号のシャドウイングに対して は，その相関距離が様々な環境で実験により測定され モデル化されている

[16]

〜

[19]

．その中で最短の相関 距離は，

[19]

に示されている都市部マイクロセル（屋 外から屋内）

(Urban Micro Cell, Outdoor-to-Indoor)

の

7m

である．したがって，シャドウイングによる空間 相関があるような

RSS

の空間センシング間隔として

2m ( < 7 m)

は妥当であると考えられる．

（2020年5月21日受付，9月19日再受付，

11月19日早期公開）

檀上 梓紗 （正員）

平26大阪市立大学工学部情報工学科卒．

平28同大学大学院前期博士課程了．現在 株式会社ダイヘン勤務．平30より大阪市 立大学大学院後期博士課程在学中．無人航 空機を用いた無線通信システムに関する研 究に従事．

原 晋介 （正員）

昭60大阪大学工学部通信工学科卒．平2 同大大学院博士後期課程了．博士（工学）． 平9同大助教授を経て，現在，大阪市立大 学大学院工学研究科教授．無線通信方式と 信号処理の研究に従事．平19本会論文賞 受賞．

松田 崇弘 （正員：シニア会員）

平8大阪大学工学部通信工学科卒，平11 同大大学院博士課程了，博士（工学）．同 年同大大学院工学研究科助手，平17講師，

平21准教授，平30首都大東京（令2より 東京都立大）大学院システムデザイン研究 科教授，現在に至る．無線ネットワーク，

ネットワーク計測に関する研究に従事．平13本会学術奨励賞，

平24本会通信ソサイエティBest Tutorial Paper Award，マガジ ン論文賞受賞，平26本会論文賞受賞．IEEE，情報処理学会各 会員．

小野 文枝 （正員）

平24情報通信研究機構入所．以来，無 人航空機を用いた無線通信システムや遠隔 制御用無線通信システムなどに関する研究 に従事．現在，総務省に出向中．博士（工学）