センサネットワークにおける負荷分散を考慮したコンバージキャストの動的経路構築
6
0
0
全文
(2) Vol.2015-MPS-102 No.11 2015/3/4. 情報処理学会研究報告 IPSJ SIG Technical Report. トに影響を与える． また，センサネットワークを利用したアプリケーション において，1 つまたは少数のノードに情報を集約する通信の ことをコンバージキャストと呼ぶ．このコンバージキャス トでは，シンクノードに近いほどより遠いセンサノードか らの情報を中継する可能性が高くなるため，トラフィック 量が大きく消費電力が大きくなる傾向がある．デューティ サイクリングを利用する場合，この傾向に適したデュー ティ比を決定する必要がある． デューティサイクリングを利用したセンサネットワー 図 1 デューティサイクリング. クの研究において，コンバージキャストに関する研究と. Fig. 1 Duty Cycling. して DDCA(Distance-based Duty Cycle Assignment) があ る [3]．DDCA はシンクノードに近いほどトラフィック量 が大きくなる問題を考慮したデューティ比の決定手法を提 案している．ルーティングには，あらかじめシンクノード. 割合をデューティ比といい，d を用いて以下の式で定義さ れる．. までの経路情報を保持する必要のない受信ノードベース. d=. ルーティングを使用している．そのため，消費電力につい てデューティ比は最適化が行われているが，ルーティング についての最適化は行われていない．. τ T. (1). デューティサイクリングには，センサノードがアクティ ブ状態の時のみデータを受信することができるという制. コンバージキャストの研究でも，与えられたデューティ. 約がある．この制約によって，デューティ比が小さいほど. 比に対して最適なルーティングを決定する手法や，与えら. 消費電力は小さくなるが，受信可能な時間が短くなるため. れたルーティングに対して最適なデューティ比を決定する. スループットは低下するなど，省電力化と通信性能にはト. 手法など一方を固定のパラメータとして与え，もう一方を. レードオフの関係がある．デューティ比を適切な値にする. 最適化する研究が多く 2 つを最適化しているものは知らな. ことである程度の通信性能を保ったまま省電力化を行うこ. い．本研究では，デューティサイクリングを利用したセン. とが可能となる．. サネットワークにおいて，コンバージキャストを行う際の. デューティサイクリングを利用したセンサネットワーク. 動的なデューティ比決定手法と経路構築手法について提案. の研究では，その研究によって様々なデューティサイクリ. する．提案手法では，各センサノードのデューティ比をシ. ングモデルが存在する．モデル化する際に重要となる点に. ンクノードまでの距離とバッテリ残量に応じて動的に変化. ついて以下で述べる．. させることで，ノードの位置によるトラフィック量の違い. • 同期と非同期. への対応と省電力化を図る．また，次の中継ノードをバッ. ネットワーク全体または隣接するノード間でデュー. テリ残量に応じて確率的なルーティングを行うことで，負. ティサイクリングのスケジュールの同期を考える場合. 荷の分散を行う．動的なデューティ比決定と経路構築の 2. と，同期を考えず非同期とする場合がある．同期を考. つを行うことででネットワーク寿命の延長を図る．. える場合，1 周期の開始と終了がノード間で揃ってい. 2. 準備 2.1 デューティサイクリング デューティサイクリングとは，あるシステムを周期的に アクティブ状態とスリープ状態を切り替える動作またはそ. ることや，ノードが互いに現在の状態を既知であると しているものがある．同期を考えない場合，現在の状 態を知ることができないため，データの送信には確率 的なモデルを使用することになる．. • 静的と動的. の技術のことである [4]．電子回路や機械などの動作の 1. デューティサイクリングのモデル化にはスケジュール. つとして組み込まれ，耐用年数を長くする目的で使用され. が静的であるか動的であるかの 2 つがある．静的な場. ている．センサネットワークでのデューティサイクリング. 合，スケジュールはパラメータとして固定されており. は，各センサノードがアクティブ状態とスリープ状態を周. アルゴリズムによって変更することはできないが，動. 期的に繰り返すことで省電力化を図るものである．図 1 に. 的の場合変更可能である．デューティサイクリングは. 横軸を時間とした状態変化の例をグラフに示す．縦軸の 0. スケジュールは動的に制御でき，必要なときにのみセ. はスリープ状態，1 はアクティブ状態を表している．. ンサノードをアクティブ状態にすることが可能である. ここで，T は 1 周期の長さ，τ はアクティブ状態の時間 を表している．1 周期の内アクティブ状態の時間が占める. ⓒ 2015 Information Processing Society of Japan. と広く考えられているため動的である場合が多い． センサネットワークの実用例は増えてきており，バッテ. 2.
(3) Vol.2015-MPS-102 No.11 2015/3/4. 情報処理学会研究報告 IPSJ SIG Technical Report. ク量の違いに対応する． 前提として，本研究ではノードが移動せず固定されたセ ンサネットワークを仮定する．シンクノードはサーバなど を想定しているため，デューティ比は常に 100%であり，安 定した電力供給があるものとする．また，各ノードは他の ノードのデューティサイクリングスケジュールと同期して おらず，他のノードのスケジュールを知らないものとする． 提案手法にはネットワークの階層化，デューティ比決定， 図 2. コンバージキャスト. 経路決定の 3 つの段階がある．それぞれについて説明する．. Fig. 2 Convergecast. 3.1 ネットワークの階層化 リ問題への大きな解決策がない今，デューティサイクリン. 最初に各センサノードの隣接関係や親ノード候補を知る. グを用いた省電力化の研究は今後更に発展していくものと. ためにネットワークの階層化を行う．これらの処理はネッ. 考えられる．. トワークが展開された直後のみ行われる．ネットワークの 階層化手順について図 3 を用いて説明する．. 2.2 コンバージキャスト コンバージキャストとは，センサネットワークにおいて. シンクノードからホップ数を付加した制御パケットを自 身の通信範囲内にブロードキャストすることで各ノードの. 1 つまたは少数のシンクノードに情報を集約する通信のこ. 階層を決定する．. とである（図 2）．. (1) シンクノードはホップ数をデータとして持つ制御パ. センサノードにストレージ機能や分析を行う十分な演算. ケットを生成し，ホップ数を 1 加算して周囲のノード. 能力がない場合が多いことから，データをサーバなどに一. へ送信する．この時，シンクのホップ数は 0 とする (図. 度集約することが多い．そのため，センサネットワークを. 3(a))．. 利用したアプリケーションの多くでコンバージキャスト. (2) 制御パケットを受信したノードは制御パケットを自. は行われている．コンバージキャストは，シンクノードに. 身の階層として保持する．既に階層の値を保持してい. データを集めるという通信であるため，シンクノードに近. た場合，制御パケットのホップ数が現在の階層よりも. いほど転送回数が多くなる可能性が高いという特徴があ. 小さければホップ数を新しい階層として保持し，ホッ. る．図 2 では，ノード A がその子孫ノードであるノード. プ数を 1 加算して周囲のノードへ制御パケットを送信. B∼F からのデータを中継することになり，自身を含めて. する．ホップ数が現在の階層と等しいまたはホップ数. 6 ノード分の転送を行う必要がある．このため，シンクに. のほうが大きければ，階層を更新せず制御パケットを. 近いノードほどトラフィック量が大きく消費電力が大きく. 破棄する．この時，制御パケットの送信元とそのノー. なるという問題がある．. ドの階層（ホップ数-1）を隣接ノード情報として保持. センサネットワークの応用においてデータの収集は非常 に重要な動作である．そのためコンバージキャストでは， 局所的な電力消費を抑えてネットワーク寿命をより長くす ることが重要である．. 3. 提案手法. しておく．. (3) (2) の作業を繰り返し行い，全てのノードの階層を決 定する．. (4) 各ノードは隣接ノードの中から自身の階層より 1 だ け階層の小さいノードを親ノード候補として保持し， 自身と同じ階層のノードを同階層ノードとして保持. 第 2 章で述べたような問題点を考慮するため，各ノード. する．この親ノード候補および同階層ノードがコン. のシンクとの位置関係に応じて適切なデューティ比を設定. バージキャスト時に次の送信先になる候補となる (図. する必要がある．また，コンバージキャスト木を構築し静. 3(b))．. 的な経路決定をしてしまうと一部のノードに負荷が集中し. ここで，階層はシンクノードまでの最短ホップ数を表す. てしまう可能性があるため，各ノードの状況に応じて動的. ことになるため，シンクノードまでの距離と言い換えるこ. に経路を決定し，負荷を分散する必要がある．本提案手法. とができる．. では，現在のバッテリ残量に応じてデューティ比を動的に 変化させ，負荷が小さくバッテリ残量のあるノードへ転送. 3.2 デューティ比決定. するように動的に経路を決定する．この時，デューティ比. ネットワーク階層化終了後，各ノードのデューティ比を. はシンクノードに近いほど大きく，遠いほど小さくなるよ. 決定する．ノードのデューティ比 d は以下の式を用いて動. うに設定することで，コンバージキャスト時のトラフィッ. 的に決定される．. ⓒ 2015 Information Processing Society of Japan. 3.
(4) Vol.2015-MPS-102 No.11 2015/3/4. 情報処理学会研究報告 IPSJ SIG Technical Report. 図 3. ネットワークの階層化. Fig. 3 Network hierarchy. ており中継を行えない場合は，同階層ノードを親ノード候. dmin E r √ d= E L dmax. ) ( Er dmin ≥ √ E L ( ) Er dmin < √ < dmax E L) ( Er dmax ≤ √ E L. 補とし，同様に選択確率を計算する．. d(ni )2 P (ni ) = ∑ d(nj )2. (2). (3). nj ∈Np. ここで，d(ni ) はノード ni のデューティ比を表している．. この時，dmin はデューティ比の最小値，dmax はデュー. ただし，ノード ni がソースノードの時は d(ni ) = dmin と. ティ比の最大値を表すパラメータであり，0.0 < dmin ≤. して確率の計算を行う．ソースノードは他ノードのデータ. dmax ≤ 1.0 である．E はバッテリ容量，Er はバッテリ残. パケット中継以外に自身のノードが生成したデータパケッ. 量，L はそのノードの階層を表している．デューティ比は. トの送信を行い，他のノードよりも負荷が高くなるため，. バッテリ残量と階層で決められる．各ノードの寿命延長を. 選択確率を低くするために行っている．また，d(ni ) の値. 図るために，バッテリ残量が少ないほどデューティ比を. が大きい方がより選択確率が高くなるように d(ni )2 として. 小さくし，消費電力を抑えるようにしている．また，コン. 計算を行っている．. バージキャストではシンクノードから離れているほどト. デューティ比 d(ni ) が大きいほど選択確率 P (ni ) は大き. ラフィック量が少なくなる傾向があるため，階層が大きく. くなる．デューティ比はバッテリ残量に応じて時間ととも. なるほどデューティ比が小さくなるように設定している．. に変化するため，選択確率も同様に変化する．（2）式とあわ. ネットワークのエリアを円とし，円の中心にシンクノード. せて考えると，バッテリ残量が少ないほど選択確率 P (ni ). がある時のコンバージキャストを考える場合，第 1 階層の. は小さくなる．データの転送回数が多く，より早くバッテ. 2. 面積と第 n 階層の面積は n に比例して増加する．エリア. リを消費したノードは選択確率もより早く低下するため，. 内にノードが一様に分布している場合，各階層に含まれる. 他のノードが選ばれやすくなり，負荷の分散が行われる．. 2. ノード数も n に比例して増加する．このことから，ノー √ ドの持つ子孫ノードの総数は n に反比例して減少してい くため，階層の逆数の平方根をとっている．. 4. 性能評価 提案手法の有効性を示すために OMNeT++[5] を用いた. デューティ比計算にはバッテリ残量を用いており，時間. ネットワークシミュレーションによる性能評価を行う．シ. の経過で再計算を行う必要があるため，定期的に（2）式を. ミュレーションでは，DDCA[3] と，提案手法，ランダム選. 用いて計算される．. 択手法の 3 つをそれぞれ比較検討し，それらの性能につい て評価する．ランダム選択手法は，デューティ比の決定に. 3.3 経路決定 シンクノードまでのルーティングは確率的かつ動的に行 われる．各ノードはパケット送信時に親ノード候補の中か. は提案手法と同様に（2）式を用いるが，経路決定には（3） 式を用いず，親ノード候補の中からランダムに選択する手 法である．. ら確率的に次の送信先となる親ノードを決定する．あるノー ドが親ノード候補の集合 Np の中からノード ni (ni ∈ Np ) を親ノードとして選択する確率 P (ni ) は以下の式を用いて 計算する．ただし，全ての親ノード候補のバッテリが切れ. ⓒ 2015 Information Processing Society of Japan. 4.1 シミュレーションモデル シミュレーションエリアの概要について図 4 に示す． シミュレーションエリアは半径を 200[m] とした円を考. 4.
(5) Vol.2015-MPS-102 No.11 2015/3/4. 情報処理学会研究報告 IPSJ SIG Technical Report. 図 5 図 4 シミュレーションエリア. ソースノード数に対するネットワーク寿命. Fig. 5 Network lifetime for the number of source nodes.. Fig. 4 Simulation area. 4.1.1 電力モデル 表 1. シミュレーションのパラメータ. Table 1 Simulation parameters 項目. パラメータ値. シミュレーションエリア. 半径 200[m] の円. シンクノードの位置. 円の中心. 通信距離. 50[m]. 通信速度. 15630 [bps]. 総ノード数. 400. ソースノード数. 20, 40, 60, 80. データパケットサイズ. 256[Byte]. パケット生成間隔. 7.5[sec], 15[sec], 30[sec], 60[sec]. デューティサイクリングの 1 周期. 1[sec]. バッテリ容量. 5[J]. 1[bit] 送受信時の消費電力 EElec. 50[nJ/bit]. 送信時の増幅電力 εamp. 100[pJ/bit/m2 ]. 無線通信による電力の消費モデルは，[6] と同じものを用 いる．k[bit] のパケットを d[m] 離れたノードへ送信すると きの消費電力 ETx は（4）式，k[bit] のパケットを受信する ときの消費電力 ERx は（5）式でそれぞれ表される．. ETx = Eelec ∗ k + εamp ∗ k ∗ d2. (4). ERx = Eelec ∗ k. (5). ここで，Eelec は 1[bit] のパケットを送受信する際に消費 する電力，εamp は送信時にかかる増幅電力を表している．. 4.2 シミュレーション結果 図 5，6 にネットワーク寿命のグラフを示す．この時，図. 5 でのパケット生成間隔は 60[sec] であり，図 6 でのソース ノード数は 60 である．いずれの場合においても，提案手法 が最もネットワーク寿命を延長できており，負荷分散が行. え，その範囲内に一様にノードが配置されており，シン. えていることがわかる．既存手法である DDCA は，ルー. クノードが円の中央に配置されている．（2）式における. ティングに受信ノードベースルーティングを使用している. dmin および dmax は，事前実験により最良の結果となった. ため，RTS パケットと CTS パケットのやり取りが多くな. dmin = 0.1, dmax = 1.0 を使用する．. り，ネットワーク寿命が短くなってしまったものと考えら. シミュレーションにおける各パラメータを表 1 に示す．. れる．しかしながら，ソースノード数が 80，パケット生成. 本シミュレーションでは，以下の項目についてシミュ. 間隔が 7.5[sec] で 3 つの手法による差はほとんどなくなっ. レーションを行う．シミュレーションはそれぞれ 10 回行. ている．これは，ソースノード数 80，パケット生成間隔. い，その平均をとったもので評価を行う．. 7.5[sec] 程度のトラフィック量がこのネットワーク資源を. • ネットワーク寿命. 最大限に使用しているからだと考えられる．. いずれかのソースノードからシンクノードまでの経路. 図 7，8 に伝送遅延のグラフを示す．この時，図 7 でのパ. が存在しなくなった時をネットワークの寿命が切れた. ケット生成間隔は 60[sec] であり，図 8 でのソースノード数. とし，ネットワークの寿命が切れるまでの時間を測定. は 60 である．図 7 を見ると 3 つの手法ともソースノード数. する．この時，あるノードの中継先となりうるノード. の増加による伝送遅延の大きな変化は見られない．DDCA. 全てのバッテリが切れていた場合をシンクノードまで. が他の 2 つにくらべて遅延が大きくなっているのは，CTS. の経路が存在しなくなったとする．. パケットの送信にシンクノードまでの距離に比例した待ち. • 伝送遅延. 時間があるからと考えられる．図 8 では，提案手法とラン. ソースノードがデータパケットを生成してからシンク. ダム選択手法においてパケット生成間隔が 7.5[sec] の時に. ノードに到達するまでの時間を測定する．. 遅延が大きくなっている．これは， （2）式による影響だと. ⓒ 2015 Information Processing Society of Japan. 5.
(6) Vol.2015-MPS-102 No.11 2015/3/4. 情報処理学会研究報告 IPSJ SIG Technical Report. 図 6. パケット生成間隔に対するネットワーク寿命. 図 8 パケット生成間隔に対する伝送遅延. Fig. 6 Network lifetime for packet generation interval.. Fig. 8 End-to-end delay for packet generation interval.. 5. おわりに 本研究では，デューティサイクリングを利用したセンサ ネットワークにおけるコンバージキャストの動的デュー ティ比決定手法と動的経路決定手法を提案した．また，シ ミュレーションによりネットワーク寿命と伝送遅延につい てそれぞれ評価を行った．シミュレーションの結果，ネッ トワーク寿命の延長ができており負荷の分散が行えている ことを示した． 今後の課題として，バッテリ残量以外にトラフィック負 荷などの要素を各種計算式に取り入れることが挙げられる． 図 7 ソースノード数に対する伝送遅延. 参考文献. Fig. 7 End-to-end delay for the number of source nodes.. [1]. 考えられる．パケット生成間隔が短いと時間あたりの転送. [2]. 回数が増加するため，バッテリがより早く減少してしまう． その結果，各ノードのデューティ比もより早く小さい値に なり，スループットが低下してしまうために遅延が大きく. [3]. なったものと考えられる．一方 DDCA では，隣接ノード にブロードキャストを行い，中継先となりうるノードの中 に 1 つでも受信可能なノードがあればそこに転送すること ができるため，大きな遅延が発生しなかったのだと考えら. [4]. れる． パケット生成間隔が短い場合には，ネットワーク寿命に 大きな差がなく遅延の小さい DDCA が有効であるといえ る．しかしながら，実際のセンサネットワーク，特に今回シ. [5]. ミュレーションを行ったような大規模なセンサネットワー クにおいて，コンバージキャストを数秒間隔で行うことは あまりなく，数分間隔で行うことが通常利用の範囲内であ ると考えられる．そのため，パケット生成間隔が 60[sec] の 時にネットワーク寿命が最も長く，伝送遅延にあまり差の. [6]. Rault, T., Bouabdallah, A. and Challal, Y.: Energy efficiency in wireless sensor networks: A top-down survey, Computer Networks, Vol. 67, pp. 104–122 (2014). Kai Han, Jun Luo, Y. L. A. V. V.: Algorithm Design for Data Communications in Duty-Cycled Wireless Sensor Networks: A Survey, IEEE Communications Magazine, Vol. 51, No. 7, pp. 107–113 (2013). Zhang, Y., Feng, C.-H., Demirkol, I. and Heinzelman, W. B.: Energy-efficient duty cycle assignment for receiverbased convergecast in wireless sensor networks, Global Telecommunications Conference (GLOBECOM 2010), pp. 1–5 (2010). Carrano, R. C., Passos, D., Magalhaes, L. C. S. and Albuquerque, C. V.: Survey and taxonomy of duty cycling mechanisms in wireless sensor networks, Communications Surveys & Tutorials, IEEE, Vol. 16, No. 1, pp. 181–194 (2014). Community, O.: OMNeT++ Network Simulation Framework, OMNeT++ Community (online), available from ⟨http://www.omnetpp.org/⟩ (accessed 2015-01-30). Heinzelman, W. R., Chandrakasan, A. and Balakrishnan, H.: Energy-efficient communication protocol for wireless microsensor networks, System Sciences, 2000. Proceedings of the 33rd Annual Hawaii International Conference on, pp. 3005–3014 (2000).. ない提案手法が最も有効であると考える．. ⓒ 2015 Information Processing Society of Japan. 6.
(7)
図
関連したドキュメント
④大気汚染物質の移流拡散を考慮した面的な分析を 行った．.. 対象エリアは，図-4に示す東京南部・川崎・横浜
重回帰分析，相関分析の結果を参考に，初期モデル
We develop vibration measuring equipment using high accurate inclimeter sensor that was not used in the past studies related to MEMS sensor. Since high accurate inclimeter sensor
Different from the tradition LS algorithm, the SDLS introduced stochastic dynamics into the local search that permits temporary increase of error function, thus resulting in escape
このように資本主義経済における競争の作用を二つに分けたうえで， 『資本
High-speed wireless access is available in guest rooms, lobby, 100 Sails Restaurant & Bar and pool area.. Wireless Network: Prince
We describe a little the blow–ups of the phase portrait of the intricate point p given in Figure 5. Its first blow–up is given in Figure 6A. In it we see from the upper part of
4 because evolutionary algorithms work with a population of solutions, various optimal solutions can be obtained, or many solutions can be obtained with values close to the
