ソーシャルネットワークの接続関係でリンクを構成することによりインセンティブ問題を解決する Wi-Fi アドホックネットワークの提案と評価
代表研究者

1村瀬 勉

名古屋大学〒464-8601 愛知県名古屋市千種区不老町

はじめに

近年，ノート PC やスマートフォンやタブレットなど，移動通信デバイスが増えている．これらのデバイスの中には，3G や LTE の通信機能を持たず，IEEE802.11(Wi-Fi)通信機能のみを持つものも少なくない．一方，
3G や LTE の通信機能を持つデバイスにおいても，Wi-Fi 通信のニーズは高い．これには，次の 2 つの理由がある．一つ目は，料金体系として，東南アジアをはじめ海外各国では，従量課金制を採用している場合が多いことである．二つ目は，日本では長年，3G や LTE での定額使い放題が主流であったが，近年では従量課金制のニーズも高まっており，安価な従量課金プランが主として MVNO にて多く導入されているということである．
一般に，3G や LTE は，カバレッジは広いが，従量課金制を考慮すると，Wi-Fi を利用し，積極的にオフロードしたいと考えるユーザも多い．しかし，Wi-Fi はカバレッジが狭い上に，電波の届く範囲に AP があっても契約していなければ，あるいは許可を得なければ，利用することはできない．ここでの AP には，固定的に設置されている公衆 AP に加えて，テザリングしているスマートフォンやモバイルルータなどアドホックなAP も含む．
しかし，もし，この AP に接続可能な端末がトラヒックを中継してくれるならば，すなわち，アドホックネットワークを構成して，中継接続してくれるならば，直接通信することができないユーザも Wi-Fi 通信を行うことができる．また，電波的に AP に直接接続できない状況であっても，アドホックネットワークを構成することができれば，Wi-Fi のカバレッジを，実質的に広げることができる．
そこで，本研究では，AP までアドホックネットワークを用いて接続する Wi-Fi ネットワークを想定する．
アドホックネットワークに関しては，多くの研究がすでに行われており，その有効性が示されている．しかしながら，アドホックネットワークにおいては，中継ユーザのインセンティブの問題を解決する必要があった．例えば，他の人のためにバッテリーが消費してしまうため，積極的には中継しないのが通常であろうとされている．アドホックネットワークの実用例が少ないのは，この問題がきちんと解決されていないからであろう．
ところで，アドホックネットワークを形成する端末のユーザ同士が顔見知りの知り合いであれば，そのこと自体がインセンティブになり，直接依頼されれば，接続させ中継してあげる，というアドホックネットワーク形成の可能性はあると思われる．これは，ギブアンドテイクが成立するとの想いが潜在的にあるからだと思われる．このことを明示的に利用した例が，FON[1]であり，ギブアンドテイクがインセンティブになる好例であろう．しかしながら，直接の知人であればまだしも，知人のそのまた知人という関係の相手が自身の身近に存在することを，直接知ることは難しい．ただし，昨今，Facebook や twitter といった SNS の興隆で，簡単に知り合いを見つけることが可能になってきている．
そこで，本稿では，この SNS(ソーシャル・ネットワーキング・サービス)を基にして，知り合い同士で接続しあう，つまり，ソーシャルネットワークの接続関係でリンクを構成するアドホックネットワークを提案し，その性能を評価する．

2

関連研究

本研究で想定するアドホックネットワークは，そのネットワークを用いることで，通信相手との経路を確立するものである．そのためには，電波の届かない相手に対して，相手との間にいる見知らぬ不特定多数のユーザにトラヒックを中継してもらう必要がある．そのようなアドホックネットワークの研究はすでに数多くなされている．[2][3]．しかしながら，このようなアドホックネットワークにおいて，見知らぬ不特定多数のユーザにトラヒックを中継してもらう，ことに対するインセンティブ問題をどう解決するかは，大きな課題となっている[4]．このインセンティブ問題に関しても，さまざまな研究がある[5]．例えば，[6]では，
1
電気通信普及財団 研究調査報告書

アドホックネットワークを事業化する場合に課題となる中継端末の確保に対して，中継に対する対価として謝金を支払うサービスモデルを提案し，料金とユーザ効用並びに事業者収益の関係を示している．しかし，この例のように，貸し借りの大がかりな仕組みを必要とするものが多く，より低コストの現実的な仕組みが求められている．
また，貸し借りではなく，中継端末の QoS 向上をインセンティブに用いた研究[7]があるが，見知らぬ不特定多数のユーザ同士が，QoS のために接続し合うかどうかについての議論は行われていない．
一方，[8]では，SNS 上のユーザの友人親密度に基づくアクセス制御メカニズムを提案しているが，親密度はユーザ 1 対 1 の関係にのみ設定されるものとし，知人の知人にあたる人物については言及していない．しかし，現実世界においては，知人の知人など，間接的な知人，いわゆるソーシャルネットワークでリンクされている人に対して，利便性を提供する場合もあるであろう．また，知人の中でも親密度に大きく幅があり，さらにその知人についても同様である．たとえ知人であっても，マルチホップ通信をさせてあげるほどではない，といった場合や，直接の知人ではないが，親友の家族だからマルチホップ通信をさせてあげたい，といった場合が存在する．なお，知り合いの知り合いなど間接的な知り合いを見つける方法も技術的な課題になるが，本研究では，間接的な知り合いは，既存 SNS などでの探索メカニズムを用いて，調査できると仮定する．また，知人同士がコミュニケーションすることで，情報が伝搬するようなモデルについての研究(例えば[9])においては，Delay Tolerant Network に似た通信モデルに関して議論されている．ただし，中継端末同士が，即時に情報を転送するようなモデルへの拡張は難しい．
本研究では，「知り合い」ということが中継インセンティブになるという前提の下，知り合いの知り合いといった間接的な知り合い関係まで考慮して，それをベースに，すなわち，ソーシャルネットワークベースのアドホックネットワークを構成することで，QoS（接続性）を飛躍的に高めるアーキテクチャを提案し，この性能を評価する．

3

ソーシャルネットワークベースのアドホックネットワーク(SOCNET)

3-1 SOCNET の定義
SOCNET においては，あるユーザが持つ端末(以後，ノードと呼ぶ)同士は，もしユーザ同士がある条件にあてはまる間接的な知り合いであれば，ノード同士接続され，トラヒックが中継されるものとする．ある条件とは，例えば N ホップの知り合い，という条件である．N ホップの知り合いとは，ソーシャルネットワーク上で知り合いの知り合いの知り合いの．．．と，知り合いの知り合いを N 回以内で繋いでたどり着く知り合いと定義する．(以後，N を接続許容最大ホップ数と呼ぶ．)ソーシャルネットワークにおいて，この N ホップの知り合いに対して直接リンクを張ったネットワークを，N ホップソーシャルネットワーク(N-SN)と呼ぶ．
本論文では，この N-SN のノードとリンクで構成された物理ネットワークを SOCNET とする．
知り合いであることが中継インセンティブになる，と書いたが，N が大きくなって知り合い度合が薄れると，他のノードに接続させてあげることに対して心理的な抵抗が生じると考えられる．
知り合い関係は，SNS から得るものとする．例えば，Facebook の「友達」関係により，知人か否かを容易に定義できる．もちろん，SNS 上の関係性を取り出せるかについては，プライバシーの問題があるが，本稿ではこれには注目せず，コンピュータ上での知り合い関係は容易に得られ，そのデータベースが存在するものとする．
3-2 アドホックネットワーク構築
アドホックネットワーク構築においては，Wi-Fi を用いて peer-to-peer のネットワークを構成する．さらに，AP に接続できるノードは AP にも接続する．本論文では，一つの AP とその近隣のノードで構成されるSOCNET に着目する．具体的には，ノードの電波が届く範囲，すなわち電波的に接続可能なノード同士で，上記データベースの N-SN を参照し，N-SN にてノード間にリンクがあれば，接続して，アドホックネットワークを構成する．この SOCNET においては，どのノードが AP に直接接続しているかによって，あるノードからAP までの通信経路が異なる．さらに，AP までの経路が確立されるノードがある反面，N-SN でのリンクが存在しないため誰とも接続されず孤立してしまうノードや，いくつかのノードと接続するが AP への経路を持たないサブネットワークなどが生まれる可能性がある．もし AP へ複数の経路がある場合には，ルーティングを決定することで，SOCNET が最終的に構成される．
この SOCNET の構築手順については，以下のような仮定をする．各ノードは，予めデータベースをダウンロ

2
電気通信普及財団 研究調査報告書

ードしておくか，3G/LTE 経由で検索し，接続相手を見つけるものとする．あるいは，AP において，データベースを参照・検索する通信のみは，誰にでも開放しているものとする．接続相手の情報は，ビーコンなどの捕捉で SSID や MAC アドレスなどが認識でき，これらがユーザの属性として，予めデータベースに記録されているものとする．
3-3 SOCNET の構築例
ソーシャルネットワークのつながりに基づいたデータベース上に，図 1 のように，A-E の 5 ノードのほか，多数のノードが存在している．このデータベース上に存在する各ノードは，r%の割合で他のノードと直接の知り合い関係にある．(以後，r を知り合い割合と呼ぶ．) 例えば，r=5 のとき，101 人のソーシャルネットワーク中，ある人は平均的に 5 人と直接の知り合いである．線で結ばれているノード同士が，直接の(1 ホップの)知り合いである．この中から，実際に，ある AP の電波の届く範囲にあるノード S 台(ここでは A-E の 5台)を抽出する．N=1 として，A-E のうち 1 ホップ以内で接続可能なノード同士を線で結んだものが図 2 である．さらに，N=2 として，A-E のうち 2 ホップ以内で接続可能なノード同士を線で結んだものが図 3 である．
図 1-3 でのリンクを，論理的リンク(データベース上のリンクであり，実際の物理的な配置は無関係)と呼ぶ．

図 1. SNS 上の直接のリンク

図 2. 1-SN のリンク

図 3. 2-SN のリンク

ここで，実際の物理的な配置を表したのが図 4 である．これは，電波的にはフルメッシュ(全ノードがIEEE802.11g のキャリアセンス範囲内にある)だが，AP に接続可能なノード数 T は限られている(契約上利用不可能，または，できれば接続したくない等)．ここで，T=2 とし，B, D のみが AP に接続可能であるとき，
図 3 で示した 1 ホップ以内および 2 ホップ以内の結びつきをマッピングしたものが図 5 および 6 である．図
5 および 6 を物理的リンク(実際にネットワークにおいてパケットが転送されうる経路)と呼ぶ．例えば，C は直接 AP に接続することができなかった．また，Cは B および D と直接の論理的リンクがなかった(図 2)ため，AP に接続できなかったが，C と B は共通の知人の存在により 2 ホップの知り合いとなり，論理的リンクが生じ，物理的に接続可能となった．さらに，もし接続時の物理的な経由ホップ数をできるだけ少なくしたいという条件をつけると，最終的な接続経路は図 7 のようになり，A-E の全ノードが AP に接続可能となる．(A: A→B→AP,
B: B→AP, C: C→B→AP, D: D→AP, E: E→D→AP)．論理的リンクを用いること
図 4: 物理的な配置により，物理的リンクが作られ，ユーザ A, C, E はネットワークを利用できることとなる．

図 5: 1 ホップ以内
3-4 SOCNETの基本特性(1)
評価尺度：接続率

図 6: 2 ホップ以内

図 7: 最終的な接続経路

3
電気通信普及財団 研究調査報告書

接続率は，あるノードが AP への接続が確立する可能性を意味している．AP に直接接続している T 人が S人のうちどういった割り当てになっているかで場合分けしたすべてのパターンごとの接続確立ノードの割合を合計し，パターン数で割ることによって算出した平均値を接続率とする．
(2)
AP のカバレッジと収容人数
AP の電波の届く範囲が広ければ広いほど，存在するノードの数は多くなり，同範囲に知人が存在する可能性は高く，接続率は高くなる．しかし，ここでは AP のカバレッジを，AP を中心としたある範囲内と固定し，S 人がこの範囲に存在するとしている．行動範囲の似た人物の多く存在するコミュニティから構成される
N-SN であるほど，S の値は大きくなる．また，より大規模な母集団であるほど，S の値は大きくなる．
(3)
知り合い割合と接続率
母集団の人数を G とすると，一対一の関係性のうち，知り合いであるものの数は G*r である．N ホップ先まで拡張すると，知り合いの数は平均するとネズミ算式に増加するはずなので，N ホップでは (G*r)n となる．
したがって，r の値が大きいほど，ホップ数を増やした時に接続率に与える影響も大きく，比較的小さい Nで接続率を 100％にできる可能性が高い．
(4)
接続許容最大ホップ数の変化の影響SOCNET では，ソーシャルネットワークにて，直接のリンクが多ければ多いほど，接続可能性は高くなる．
従って，接続性を上げるためには，例えば，ホップ数 N を大きくすればよい．しかしながら，N が大きいということは，あまり知らないユーザ同士が接続されてしまうことを意味し，ユーザ同士がソーシャルネットワークにおいて関係性をもっていることが必ずしも中継インセンティブとして働くとは言い切れない．これは，インセンティブの面からは，あまり好まれないと思われる．従って，妥当な N の範囲が存在するかしないのか，検討する必要がある．
(5)
AP 直接接続可能ノード数の変化の影響
また，AP に接続可能なノードの数 T を大きくすることでも接続率を向上させることができ，
T=S であれば，接続率は 100%である．しかしながら，ここでは，SOCNET を利用した場合の接続率変化を評価するため，T=S，つまり S 台すべてが AP に接続可能である状況よりも，T がより少ない値の場合に注目する．

4

SOCNET の接続率評価

図 8. AP と S 個のノードの物理的配置

図 9. S=10 台のノードの抽出例

r=5%のときの，T および N と接続率との関係を表したグラフが図 10,11 である．T を大きくすればするほど接続率は 100%に近付く．r がある程度の割合であれば，T が少なくとも，N を少し大きくするだけでよい．T=1,2 程度でも，N を 1, 2 程度にするだけで接続率は飛躍的に向上し，100%に近付く．すなわち，「知り合いの知り合いまで接続可能」とするだけでも，SNS で知人関係を利用しない場合と比較して接続率が大幅に向上し，もしそれ以上先の知り合いまで接続可能範囲を広げたとしても，接続率の向上はあまりみられない．
N=2 のときのグラフが図 12 である．r の値が小さい場合，AP に直接接続可能なノード数を大きくしなければ，接続率向上効果は見られない．r の値が 5％程度のとき，T を 10 人中 1 人とすれば，接続率が向上した．
そこで，T は 0 台からすべての台数まで有り得るとして平均化した場合のグラフが図 13 である．あるネットワークにおいて，もし AP に直接接続可能なノード数が判明していなくても，r の値が 5％以上ならば N の値に関係なく接続率が 100％に近付いた．N=0 と比較すると，N=1, 2 程度とするだけで，接続率が向上することを示した．つまり，ソーシャルネットワークの接続関係を用いることは，無線アドホックネットワークで

4
電気通信普及財団 研究調査報告書

の接続率向上に有効である．

図 10. T の変化に対する接続率変化

図 11. N の変化に対する接続率変化

図 12. r の変化に対する接続率の変化

5電気通信普及財団 研究調査報告書

図 13. r の変化に対する接続率変化

5

まとめアドホックネットワークにおける中継インセンティブの課題を解決するために，SNS ベースのアドホックネットワークを提案した．知り合いであることが，中継を行うインセンティブになりうるというアイデアを利用する．これにより，ある AP に対して直接接続ができないと思われていた物理ノード間でも，中継を用いて通信が可能となる．
この SNS ベースのアドホックネットワークにおけるユーザの接続率を求めた．SNS において N ホップでリンクする関係ならば物理的にも接続可能であると仮定すると，AP に直接接続可能なノード数が少ない場合(1,2 台程度)でも，N を 1,2 程度にするだけで接続率は飛躍的に向上し，100%に近付く．すなわち，「知り合いの知り合いまで接続可能」とするだけでも，SNS を利用しない場合と比較して接続率が大幅に向上し，もしそれ以上先の知り合いまで接続可能範囲を広げたとしても，接続率の向上はあまりみられない．また，SNS での直接の知り合いの割合を r とすると，r の値が小さい場合，AP に直接接続可能なノード数を大きくしなければ接続率向上効果は見られない．そこで，AP に直接接続可能なノード数は 0 台からすべての台数まで有り得るとして平均化した場合，r の値が 5％以上ならば N の値に関係なく接続率が 100％に近付く．以上のように，知り合いであると言うことで接続関係を構成することが、アドホックネットワークにおける中継インセンティブになり得ること、なおかつ十分な接続率が得られることが明らかになった．

【参考文献】[1]FON: https://www.fon.com/jp/info/whatsFon[2]W. Kiess and M. Mauve, “A survey on real-world implementations of mobile ad-hoc networks,”
Ad Hoc Networks, Volume 5, Issue 3, pp. 324-339, 2007[3]R. Bruno, M. Conti and E. Gregori, “Mesh Networks: Commodity Multihop Ad Hoc Networks,”
IEEE Communications Magazine, IEEE Vol. 43, Issue 3, pp. 123-131, 2005
[4]S. Zhong, L. E. Li, Y. G. Liu and Y. R. Yang, “On designing incentive-compatible routing andforwarding protocols in wireless ad-hoc networks,” Wireless Networks, Vol. 13, Issue 6, pp.
799-816, 2007[5]M. Feldman, K. Lai, I. Stoica and J. Chuang, “Robust Incentive Techniques for Peer-to-PeerNetworks,” EC '04 Proceedings of the 5th ACM conference on Electronic commerce, pp. 102-111,
2004[6]藤井 拓也，矢守 恭子，田中 良明：中継謝金を支払うアドホックネットワークサービスにおける基本料金と通信料金の設定法(アドホック NW)，電子情報通信学会技術研究報告. NS, ネットワークシステム 110(448),263-268(2011)

6
電気通信普及財団 研究調査報告書

[7]藤井 聡佳，村瀬 勉，小口 正人：マルチホップマルチレートネットワ kuークでの接続先選択ポリシーと接続
元別重み付けスケジューリングにおける通信性能評価，第 6 回データ工学と情報マネジメントに関するフォー
ラム(DEIM2014)，C9-4(2014)[8]Y. Wang, E. Zhai, E. K. Lua, J. Hu and Z. Chen, “iSac: Intimacy Based Access Control for Social
Network Sites,” Ubiquitous Intelligence & Computing and 9th International Conference on
Autonomic & Trusted Computing (UIC/ATC), 2012 9th International Conference on, pp. 517-524,
2012[9]S. Takeuchi, J. Kamahara, S. Shimojo and H. Miyahara,”Human-Network-based Filtering: The
Information Propagation Model based on Word-of-Mouth Communication,” Proc. SAINT-2003,
pp.40-47, 2003

〈発題名

ソーシャルネットワークの接続関係でリンクを構成する Wi-Fi アドホックネットワー
クの提案と評価
テザリング端末の存在する無線ネットワー
クのスループット解析
ソーシャルネットワークを利用し構築した
Wi-Fi アドホックネットワークの 親密性に基づく通信制御による性能評価
V2V
Communication
QualitywithMulti-Antnna in Field Assessment andSimulations

表資料〉

掲載誌・学会名等

発表年月

電子 情報通信学 会 IN 研 究会、IN2014-109
電子 情報通信学 会 ASN 研究会 ,ASN2014-152
第 7 回データ工学と情報マネジメントに関するフォーラム(DEIM2015)，C2-4
IEEE International Conference on
Connected Vehicles & Expo
(ICCVE)2014

2015 年 1 月
2015 年 1 月
2015 年 3 月

2014 年 11 月

7電気通信普及財団 研究調査報告書