ソーシャルネットワークの関係性を中継インセンティブとした

Wi-Fi モバイルアドホックネットワークの性能評価
理学専攻・情報科学コース

1

はじめに

Wi-Fi での通信カバーエリア拡大のために，モバイ
ルアドホックネットワーク技術を用いた中継通信方法が注目されている．公衆無線 LAN などの AP に対して，電波的には接続できるものの，契約などの関係で接続できない場合に，AP 接続可能なユーザ経由で接続するアドホックネットワークを構築することが想定される．アドホックネットワークを形成する端末のユーザ同士が顔見知りの知り合いであれば，そのこと自体がインセンティブになり，直接依頼されれば，接続させ中継してあげる，というアドホックネットワーク形成の可能性はあると思われる．このことを明示的に利用した例が，FON であり，ギブアンドテイクがインセンティブになる好例であろう．
本研究では，性能をインセンティブとした場合およびユーザ同士の関係性をインセンティブとした場合の特性評価をおこなった．ここでは，ソーシャルネットワークの接続関係でリンクを構成するアドホックネッ
トワークの提案と評価について述べる．

2

藤井 聡佳

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

図 2: 2-SN のリンク

ここで，実際の物理的な配置を表したのが図 3 である．これは，電波的にはフルメッシュ(全ノードがIEEE802.11g のキャリアセンス範囲内にある) だが，AP に接続可能なノード数 j は限られている (契約上利用不可能，または，できれば接続したくない等)．ここで，j = 2 とし，B, D のみが AP に接続可能であるとき，図 3 で示した 2 ホップ以内の結びつきをマッピングしたものが図 4 である．図 4 が，実際にネットワークにおいてパケットが転送されうる経路である．

従来研究[1] では，SNS 上のユーザの友人親密度に基づくアクセス制御メカニズムを提案しているが，親密度はユー
ザ 1 対 1 の関係にのみ設定されるものとし，知人の知人にあたる人物については言及していない．しかし，現実世界においては，知人の知人など，間接的な知人，いわゆるソーシャルネットワーク (SN) でリンクされている人に対して，利便性を提供する場合もあるだろう．

3

親密度 (ホップ数) と接続率・スループット

3.1

ソーシャルネットワーク上でのホップ数と知り合いが増える度合

本稿で想定するネットワークについて述べる．ユー
ザ同士がある条件にあてはまる間接的な知り合いであれば，ノード同士接続され，トラヒックが中継されるものとする．ある条件とは，例えば n ホップの知り合い，という条件である．n ホップの知り合いとは，SN上で知り合いの知り合いの知り合いの．
．
．と，知り合いの知り合いを n 回以内で繋いでたどり着く知り合いと定義する．(以後，n を接続許容最大ホップ数と呼ぶ．)
この n ホップの知り合いに対して直接リンクを張ったネットワークを，n-SN と呼ぶ．各ノードは，r%の割合で他のノードと直接の知り合い関係にある．(以後，r を知り合い割合と呼ぶ．) 例えば，r = 5 のとき，100人のソーシャルネットワーク中，ある人は平均的に約5 人と直接の知り合いである．図 1 において，線で結ばれているノード同士が，直接の (1 ホップの) 知り合いである．この中から，実際に，ある AP の電波の届く範囲にあるノード k 台 (ここでは A-E の 5 台) を抽出する．n = 2 として，A-E のうち 2 ホップ以内で接続可能なノード同士を線で結んだものが図 2 である．

図 3: 物理的な配置

3.2

図 4: 2 ホップ以内の物理的リンク

ホップ数とアドホックネットワークにおける接続率とスループット

3.2.1

評価尺度：接続率と AP スループット

接続率は，あるノードが AP への接続が確立する可能性を意味し，n ホップのとき，j 人のノードのいずれかを経由することで AP に間接的に接続可能であるノード数を jn とする．ここで，j 人が k 人のうちどういった割り当てになっているかで場合分けしたすべてのパターン (パターン数：k Cj ) ごとの接続確立ノードの割合を合計し，パターン数で割ることによって算出した平均値を接続率 P とする．
AP スループット T h とは，k 台の端末が複数の経路がある場合は，できるだけホップ数を少なくするように接続した場合の AP を通過するスループットを意味する．

3.2.2

定性評価

接続率 P と AP スループット T h は次の式で求まる．
無線 LAN 総スループットを G とする．G は，ホップ数 n で決まる．ホップ数 n が決まると無線 LAN に (直接または間接的に) 接続しているノードが決まり，このノード間の接続状況とそれらのノード位置とから伝送レートが求まり，この伝送レートの調和平均で G が求められる．伝送レートの値の組み合わせが異なると，G の値も変動する (Performance Anomaly [2] が起こる場合もある)．

P = (j + jｎ )/kT h = j/(j + jｎ ) · G
ホップ数 n が増えると，一般に，AP に間接的に接続するノード数 jn が増加し，接続率 P が高くなる．このとき，AP に対して，AP と直接つながっているノードと AP との通信機会は j/(j + jn ) 倍に減少するため，概して AP スループット T h は低下する．ここで，接続率とスループットのどちらも高い状態を，効率がよいと考える．接続率が上がれば，スループットは低下しやすいため，P と T h はトレードオフの関係だと言える．そこで，効率を P · T h で定義して評価する．したがって，この効率を最大化にするためには，ホップ数 n で決まる G を最大化すればよい．

図 6: n の変化に対する AP スループット変化

P · T h = j/k · G
3.2.3

定量評価

上記特性を評価するために，次のようなモデルを用いた．100m × 100m の範囲で，中心に AP が 1 台存在する物理モデルにおいて，k 台が AP の周囲にランダムな位置で配置されている．この k 台は，100 台のSN からランダムに抽出されたものである．
r=5%，k=10，物理的に 10 ホップまで接続可能としたときの，j および n と接続率との関係を表したグラフが図 5 である．j を大きくすれば接続率を 100%により近付けることができるが，r がある程度の割合であれば，j が小さくとも，n を大きくするだけで接続率を高くすることができる．j=1, 2 程度でも，n を 1,2 程度にするだけで接続率は飛躍的に向上し，100%に近付く．

図 7: n の変化に対する効率変化

4

まとめアドホックネットワークにおける中継インセンティ
ブの課題を解決するために，SN ベースのアドホックネットワークを提案した．直接または間接の知り合いであることが中継を行うインセンティブになりうるというアイデアを利用する．
本稿では，この SN ベースのアドホックネットワークにおけるユーザの接続率とスループットを求めた．SN
において n ホップでリンクする関係ならば物理的にも接続可能であると仮定すると，今回用いたパラメータ
設定においては，AP に直接接続可能なノード数が少ない場合でも，n を 1,2 程度にするだけで接続率は飛躍的に向上し，100%に近付く．また，接続率とスループットのどちらも高い状態を，効率がよいものとすると，n の値を変化させても効率に大きい変化はないが，n が 1,2 程度で効率のよい場合がみられることがある．
すなわち，「知り合いの知り合いまで接続可能」とするだけでも，SN を利用しない場合と比較して接続率や効率がよくなる．

参考文献
図 5: n の変化に対する接続率変化
このときの，j および n と AP スループットとの関係を表したグラフが図 6 である．j=1，2 程度のとき，n=1 と n=2 の間，すなわち接続率の大幅に向上した区間において，AP スループットが大幅に低下する．これは前述のように，マルチホップ接続を可能とすることで，AP に間接的に接続するノード数が増えることによるものである．
また，このときの効率を計算したグラフが図 7 である．n の値を変化させても効率に大きい変化は見られないため，効率の観点からは，n は任意の値で構わないことが分かった．ただし，j=1, j=2 の場合など，nが 1,2 程度で多少効率が良くなる．

[1] 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. 517524, 2012.
[2] M. Heusse, F. Rousseau, G. Berger-Sabbatel andA. Duda, Performance anomaly of 802.11b,
Proc. of IEEE Inforcom2003, vol.2, pp.836-843,
Mar.2003.