D2D 型 SNS を用いた情報共有システムに対する階層化グラフに基づく障害回避技術
Failure Avoidance Technology Based on Hierarchical Graphs for Information Sharing with D2D-based
SNS
１．研究の目的
本研究では、D2D 型 SNS を利用した情報共有システムに対する障害回避技術を確立する。障害回避技術を確立するために、2 つの異なるネットワークで構成された本システムを、図 1 に示すように一階層構造のグラフでモデル化する。それから、構築した一階層グラフを用いて耐障害性の性能評価指標を導出する。なお、構築する一階層グラフは両階層の接続状況を同時橘 拓至 ( Takuji TACHIBANA, Dr. Eng.)に考慮することができる。

福井大学 学術研究院 工学系部門 教授(Professor, University of Fukui, Faculty of Engineering)
電子情報通信学会 日本オペレーションズ・リサーチ学会 IEEE
受賞：コミュニケーションシステム研究会委員長賞 (2023 年) 国際会議
ICETC2021 Best Poster Award (2021 年) ネットワークシステム研究賞(2015 年、2012 年、2006 年)
第 22 回テレコムシステム技術賞 (2007年) 他
研究専門分野：情報ネットワーク 通信工学

あらまし
D2D 型 SNS は、インターネットやアクセスポイントなどの通信インフラが一切不要であるため、近年多発している自然災害時などの緊急時用情報共有システ

図1

D2D 型 SNS のネットワーク構成

ムとして広く利用されることが期待されている。しかし、このような緊急時の情報共有システムで利用する一階層グラフに対して導出した耐障害性の性能指標には耐障害性・ロバスト性の向上が必須であり、障害に関する最適化問題を定式化する。定式化する最適化によるシステム停止の回避が最重要課題である。本研問題では、適切な友達申請先を導出することができる。

究課題では、D2D 型 SNS を利用した情報共有システ

さらに、D2D 通信の性能を向上させるために無線中継ムに対する障害回避技術を確立する。障害回避技術を機器の利用も想定し、最適化問題を拡張する。拡張し確立するために、まず 2 つの異なるネットワークで構た最適化問題の解を導出し、無線中継機器の適切な導成された本システムを一階層の階層構造のグラフでモ入位置と導入数を決定する。

デル化する。それから、構築した一階層グラフを用い最適化問題の求解を高速化するためにヒューリステて耐障害性の性能評価指標を導出する。定式化する最ィックアルゴリズム（障害回避技術）も確立する。確適化問題では、適切な友達申請先を導出することがで立したヒューリスティックアルゴリズムの性能はシミきる。さらに、D2D 通信の性能を向上させるために無ュレーションによって評価し、ユーザの移動や友達申線中継機器の利用も想定し、最適化問題を拡張する。

請の成功確率の影響を詳細に調査する。さらに、構築拡張した最適化問題の解を導出し、無線中継機器の適したヒューリスティックアルゴリズム（障害回避技術）

切な導入位置と導入数を決定する。

を導入した情報共有システム用アプリの設計・開発に取り組む。

1

TELECOM FRONTIER No.123 2024 SPRING

D2D 型 SNS を用いた情報共有システムに対する階層化グラフに基づく障害回避技術
Failure Avoidance Technology Based on Hierarchical Graphs for Information Sharing with D2D-based
SNS２．研究の背景
ソーシャルネットワークサービス(SNS) の普及と携帯端末の進歩によって、携帯端末間で直接データをやり取りする Device-to-Device（D2D）通信を利用した SNS が開発・利用されている[1]。このような D2D型 SNS として，現在 FireChat [2] や AirTalk [3] が運用されている。これらのアプリは、災害時の情報伝達手段としての利用も期待されている。D2D 型 SNS
は、D2D 通信を行う物理網と SNS によってユーザが交流するソーシャルネットワークによって構成される。
この 2 つの異なるネットワークは異なるネットワーク構造となっている。D2D 型 SNS の通信性能は 2 つの異なるネットワーク構成に大きく依存し、物理網での端末配置とソーシャルネットワークでの交友関係によって通信性能が変化する。
この D2D 型 SNS は、インターネットやアクセスポ

図2

イントなどの通信インフラが一切不要であるため、近D2D 型 SNS を用いた情報共有システムの障害発生年多発している自然災害時などの緊急時用情報共有システムとして広く利用されることが期待されている。

D2D 型 SNS の障害に対する性能指標であるノード

しかし、このような緊急時の情報共有システムで利用の存続率 𝜓 は、通信時間が平均 𝜆 の指数分布に従うするには耐障害性・ロバスト性の向上が必須であり、場合、上限と下限は以下の式で与えられる。

障害によるシステム停止の回避が最重要課題である。

𝜓 ≤ 1 − (1 − 𝑝𝑓 − 𝑠∞ )𝑒 −𝜆𝑇𝑚𝑎𝑥 − 𝑝𝑓

このような D2D 型 SNS では、SNS に関するユー𝜓 ≥ 𝑠∞ + (1 − 𝑝𝑓 − 𝑠∞ )(1 − 𝑒 −𝜆 )ザ間の接続状況と D2D 通信における端末間の接続状

ここで、𝑇𝑚𝑎𝑥 は障害発生後にネットワーク構成が安況がシステムの運用状況および通信性能に大きく影響定するまでの時間を表し、𝑝𝑓 は初期障害ノード割合をする。特に D2D 型 SNS を利用した情報共有システム示している。

では、システムの運用停止を回避するために SNS でのユーザ間接続（友達関係）状況と D2D 通信上での３．研究の方法端末間接続状況を同時に改善しなければならない。図

本研究では、D2D 型 SNS を用いた情報共有システ

2 は D2D 型 SNS における障害発生例を示している。

ムに対して、階層化グラフに基づく 2 つの障害回避技

この図に示されるように、耐障害性・ロバスト性の向術を提案する。

上による障害回避の実現が容易ではない。
D2D 型 SNS

提案法では，D2D 型 SNS を用いた情報共有システ

では一方のネットワークで発生した障害がもう一方のムに対して、発生した障害による影響を表す指標としネットワークにも影響する。結果として障害が時間とてノード存続率 𝜓 を定義する。このノード存続率 𝜓

ともに両ネットワークを連鎖して大規模化するカスケは、上記の式の上限を利用する。情報共有システムのード障害が発生する[4]。特に、D2D 型 SNS は災害時ノード存続率が高く（低く）なると、情報共有の性能での有効利用も期待されているため、障害の影響を低が高く（低く）なる。

減することが期待される。

以下ではまず、D2D 型 SNS を用いた情報共有シス

2TELECOM FRONTIER No.123 2024 SPRING

D2D 型 SNS を用いた情報共有システムに対する階層化グラフに基づく障害回避技術
Failure Avoidance Technology Based on Hierarchical Graphs for Information Sharing with D2D-basedSNS
テムにおける障害回避技術として、階層化グラフに基を追加することで、ノード存続率 𝜓 が向上する。

づく最適中継装置配置法を確立する [5]。

ここで、𝐴𝑚𝑎𝑥 は情報共有システムに追加する最大仮想友人関係数を示している。このとき、以下の最適化問題を定式化する。
max
1 − (1 − 𝑝𝑓 − 𝑠∞ )𝑒 −𝜆𝑇𝑚𝑎𝑥 − 𝑝𝑓𝑠𝑎𝑖𝑗

subject to:𝑠∑𝑖 ∑𝑗 𝑎𝑖𝑗≤ 𝐴𝑚𝑎𝑥𝑠
この最適化問題において、𝑎𝑖𝑗はユーザ 𝑖 とユーザ𝑗 の間に仮想友人関係を追加した場合に 1 の値をとる。
提案法では、本最適化問題の解を発見的アルゴリズムによって高速に導出する。図 7 は、メインアルゴリズムを示しており、ノード次数を考慮して仮想友人関図 3 中継装置の追加配置による障害回避係を生成する。

図 3 は、以下で検討する中継装置問題を示している。
以下では、𝑁 人のユーザ、すなわち 𝑁 台の中継装置が情報共有システムに参加している場合を考える。こ𝑟𝑒𝑙𝑎𝑦

こで、𝑁𝑚𝑎𝑥

は情報共有システムに追加する最大中継装置数を示している。このとき、以下の最適化問題を定式化する。
max𝑟𝑒𝑙𝑎𝑦 1 − (1 − 𝑝𝑓 − 𝑠∞ )𝑒 −𝜆𝑇𝑚𝑎𝑥 − 𝑝𝑓

𝑟𝑒𝑙𝑎𝑦

𝑥𝑖, 𝑦𝑖subject to:𝑟𝑒𝑙𝑎𝑦∑𝑖 𝑎𝑖𝑟𝑒𝑙𝑎𝑦 ≤ 𝑁𝑚𝑎𝑥
𝑟𝑒𝑙𝑎𝑦𝑐𝑖=1𝑟𝑒𝑙𝑎𝑦

この最適化問題において、(𝑥𝑖𝑟𝑒𝑙𝑎𝑦, 𝑦𝑖) は配置する
𝑟𝑒𝑙𝑎𝑦𝑖 台目の中継装置を配置する座標を示しており、𝑐𝑖は追加した中継装置は 1 台以上の端末と接続されている場合に 1 の値をとる。
提案法では、本最適化問題の解を発見的アルゴリズムによって高速に導出する。図 4 は、メインアルゴリ
図 4ズムを示している。このメインアルゴリズム内では、
図 5 に示すように各ノードが順に処理を実行し、ノー最適中継装置配置法に対する発見的アルゴリズム（一部）

ド密度が少ない場所に中継装置を配置する。
次に、仮想友人関係生成法を提案する [6]。本方式
では、障害発生時のノード存続率 𝜓 が向上するように、SNS 上に仮の友人関係を一時的に追加する。図 6は、生成した仮想友人関係が発生した障害に与える影響を示している。この図に示すように、仮想友人関係
3

TELECOM FRONTIER No.123 2024 SPRING

D2D 型 SNS を用いた情報共有システムに対する階層化グラフに基づく障害回避技術
Failure Avoidance Technology Based on Hierarchical Graphs for Information Sharing with D2D-based
SNS

図5

各ノードにおけるアルゴリズムの実行

図 8 D2D 型 SNS に基づく情報共有システムの開発した画面
最後に、D2D 型 SNS を用いた情報共有システムを実現するアプリを開発する。図 8 はオープンソース
Ramble を用いて開発した利用画面を示している。本
アプリによって、D2D 型 SNS によってユーザ間での図 6 仮想友人関係が情報共有システムに与える影響情報共有が可能になる。本アプリでは、障害回避技術としてグループ外ユーザ中継機能を実装する。本機能
では、使用する 3 つの異なる方式としてランダム選択方式、単一ユーザ選択方式、受信履歴選択方式のいずれかを利用する。図 9 は、グループ外ユーザ中継機能の設定画面を示しており、ランダム選択方式，単一ユーザ選択方式，受信履歴選択方式で使用するパラメータを設定できる．実装するグループ外ユーザ中継機能
によって、メッセージの送信先に指定された特定グループに所属していないユーザにメッセージを転送することが可能になり、メッセージの到達率を向上させてノード存続率 𝜓 を向上させる。

図 7 仮想友人関係生成法に対する発見的アルゴリズム（一部）図 9 グループ外ユーザ中継機能の設定画面

4TELECOM FRONTIER No.123 2024 SPRING

D2D 型 SNS を用いた情報共有システムに対する階層化グラフに基づく障害回避技術
Failure Avoidance Technology Based on Hierarchical Graphs for Information Sharing with D2D-based
SNS４．数値例

友人関係数が増加するとノード存続率が増加すること

本章では、提案する最適中継装置配置法と仮想友人がわかる。これは、図 10 の中継装置の場合と同様に、関係生成法の性能をシミュレーションで評価する。さ階層化グラフ内のリンク数が増加するためである。ま

らに、情報共有システムを実現する開発アプリの実験

た、この図では 2 つの GA 方式の性能が有効であるこ結果を示す。とがわかる。この 2 つの GA 方式のうち、提案方式と𝑝状況が類似している GA（𝑧𝑖𝑗 = 1）方式はやや存続率が低い結果となっている。提案方式については、ラン𝑝ダム方式と比べると著しく存続率が高く、GA（𝑧𝑖𝑗 = 1）方式の存続率とも比較的近い値になっていることがわかる。提案方式では最適化問題の解を自律分散処理で導出しているにもかかわらず、ノード存続率の向上に大きく貢献している。以上の結果から、実環境での利

図 10

最適中継装置配置法に対する中継装置の追加数に対するノード存続率の変化

図 10 は、配置する中継装置数が変化した場合の最適中継装置配置法のノード存続率を示している。また、性能比較のために GA 方式とランダム方式の結果も示している。この図から，配置可能な中継装置数が増加用を踏まえると提案法が有効であることがわかる。

するとノード存続率が増加することがわかる。これは、階層化グラフ内のリンク数が増加するためである。こ図 11 仮想友人関係生成法に対する仮想友人関係ののグラフから、最適化問題の解を遺伝的アルゴリズム追加数に対するノード存続率の変化（GA）で導出する方式が，最もノード存続率が高くなることがわかる。これは、ネットワークの全情報を把握できる最適化問題の解を導出しているためである。
提案法は図 8 に示すように、自律分散的に、各ノードが周囲の情報だけを用いて最適化問題の解を導出していることになるため、GA 方式よりもノード存続率が低くなる。しかし、ランダム方式よりも提案法は性能が高く、また GA 方式の実運用は不可能であることか
図 12

ら、実環境での利用を踏まえると提案法が有効である

開発したアプリを用いて構築した実験環境

ことがわかる。
図 11 は、生成可能な仮想友人関係数が変化した場合の仮想友人関係生成法のノード存続率を示している。
また、性能比較のために 2 つの GA 方式とランダム方式の結果も示している。この図から、生成可能な仮想5

TELECOM FRONTIER No.123 2024 SPRING

D2D 型 SNS を用いた情報共有システムに対する階層化グラフに基づく障害回避技術
Failure Avoidance Technology Based on Hierarchical Graphs for Information Sharing with D2D-basedSNS

表 1 開発したアプリの実験結果

５．将来展望災害が多い日本では、今まで以上に、SNS を活用した情報共有に対する期待が大きくなることが予想され
る．
端末間で直接データをやり取りする D2D 通信は、通信インフラが不要なため、災害発生時に有効となる。
本研究課題で取り組んだ D2D 型 SNS に基づく情報共有システムを災害時に有効利用してもらうためには、日常的に使用するアプリの機能に組み込むことが期待されるため、日常的に利用するユースケースを踏まえ

表 1 は、図 12 に示した実験環境で実施したグルーたアプリの改良が必要となる。今後は、障害回避法とプ外ユーザ中継機能に対する実験結果を示している。

して提案した最適中継装置配置法と仮想友人関係生成

本実験では FFF-TAB7 Android タブレット 7 型（スト法をアプリに導入したうえで、日常から使用できるアレージ 32 GB、Android バージョン 9.0）を利用し、プリへ改良し、災害発生時などの情報共有に貢献した

D2D 型 SNS に基づく情報共有システムをインストーいと考えている。

ルして Bluetooth によって D2D 通信を行う。この実
験環境では、d1 と d5 が同一グループに所属し、d2，おわりにd3，d4 は別のグループに所属している．このとき，本研究課題では、D2D 型 SNS を利用した情報共有

d1 が所属グループ向けにメッセージを送信し，グルーシステムに対する障害回避技術として、最適中継装置プ内の d5 がメッセージを受信すると伝送成功となる。

配置法と仮想友人関係生成法を提案し、数値例で各方本実験では、d1 からグループ内ユーザ d5 へメッセー式の有効性を調査した。また、D2D 型 SNS を用いた

ジを 3 秒間隔で 100 回自動送信し、d5 へのメッセー情報共有システムのアプリを開発した。本アプリには

ジ到達率や d2，d3，d4 のメッセージ受信割合、平均グループ外のユーザにもメッセージを送信する障害回転送回数、未送信割合を評価する。なお本実験は端末

避技術を実装し、その有効性を実験で調査した。これの位置は固定したままで実行している。

らの結果から、本研究開発で確立した各方式，アプリ
は、それぞれ D2D 型 SNS の障害回避技術として有効この表から、ランダム選択方式で確率を変化させると，各端末のメッセージ受信割合が変化していることであることがわかった。

がわかる。メッセージ到達率を示す d5 の受信割合はd2 の受信割合と同じとなり、d3 と d4 に対する受信割合の増加はメッセージの冗長な転送に繋がる。単一ユ参考文献

ーザ選択方式では必ず一ユーザにメッセージを転送す[1] Y. Zhang, E. Pan, L. Song, W. Saad, Z. Dawy, andるため、平均転送回数は 1 で未送信割合は 0 となる。

Z. Han,“Social Network Aware Device-to-Device

本方式はメッセージの無駄な転送は回避できるが、メCommunication in Wireless Networks,” IEEE

ッセージ転送率が増加しにくい傾向にある。最後の受Transactions on Wireless Communications, vol.

信履歴選択方式では、受信履歴に基づき、d5 のメッセ

14, no. 1, pp. 177–190, Jan. 2015.

ージを中継した経験のある d2 と d3 にメッセージが転[2] FireChat,送される。それゆえ、平均転送回数は 2 となり、未送

https://www.opengarden.com/firechat.html.

信割合が 0 となる。d5 の受信割合が 1.0 であることか[3] AirTalk, http://airtalk.off-line.co.jp/.

ら、本方式がメッセージ到達率の増加に最も有効であ[4] S. V. Buldyrev, R. Parshani, G. Paul, H. E.
Stanley, and S. Havlin, “Catastrophic Cascade ofることがわかる。
6TELECOM FRONTIER No.123 2024 SPRING

D2D 型 SNS を用いた情報共有システムに対する階層化グラフに基づく障害回避技術
Failure Avoidance Technology Based on Hierarchical Graphs for Information Sharing with D2D-based
SNSFailures in Interdependent Networks,” Nature,
vol. 464, no. 7291, pp. 1025–1028, Apr. 2010.
[5] H. Yokoi and T. Tachibana, ``Autonomous Relay
DevicePlacement

Cascading

FailureAlgorithm
infor

D2D-Based

Avoiding
SocialNetworking Service,” IEICE Transactions on
Information and Systems, vol. E104-D, no. 5, pp.
597-605, May 2021.
[6] H. Yokoi and T. Tachibana, ``Autonomous Relay
DevicePlacement

Cascading

FailureAlgorithm
infor

D2D-BasedAvoiding
SocialNetworking Service,” IEICE Transactions on
Communications, vol. E105-B, no. 4, pp. 379-387,
Apr. 2022.
[7] 岡田 空，橘 拓至，``D2D 型 SNS における中継先選択方式の提案と実装評価,” 信学技報，vol. 120,no. 413, NS2020-149, pp. 155-160, Mar. 2021．

この研究は、令和元年度ＳＣＡＴ研究助成の対象として採用され、令和２～４年度に実施されたものです。

7

TELECOM FRONTIER No.123 2024 SPRING