Comments
Description
Transcript
無線LAN省電力化のための マルチホップ通信を用いたAP数低減手法
情報処理学会論文誌 Vol.54 No.2 610–620 (Feb. 2013) 無線 LAN 省電力化のための マルチホップ通信を用いた AP 数低減手法 進藤 博子1,a) 鈴木 瑛識1 重野 寛1 受付日 2012年5月14日, 採録日 2012年11月2日 概要：近年，環境問題への意識の高まりから，無線 LAN の省電力化が課題としてあげられている．その課 題に対し，通信量の少ないクライアント（CL）を 1 台のアクセスポイント（AP）に集約し，使用する AP 数を低減させる研究があるが，通信範囲の観点から低減させることができる AP 数に限りがある．本論文 では，マルチホップ通信を用いた AP 数低減手法を提案する．CL が他の CL を経由し通信範囲外の AP を使用することで，より多くの CL を 1 台の AP に集約でき，AP 数をより低減させることができる．マ ルチホップ通信による電力削減効果を定式化し，電力削減量を最大化するように使用する AP を選択する． また，CL のスループット等にスレッショルドを設け，スレッショルドを満たさない AP を選択しないこと で，CL の通信に多大な影響を与えずに AP 数を低減させる．シミュレーションと実機実装による評価を 行い，本提案の有効性を示す． キーワード：無線 LAN，省電力化，AP 数低減，マルチホップ通信 Reduction of Active APs Using Multi-hop Communication for Wireless LANs Power-saving Hiroko Shindo1,a) Akinori Suzuki1 Hiroshi Shigeno1 Received: May 14, 2012, Accepted: November 2, 2012 Abstract: Recently wireless LANs power-saving is getting much attention, with increasing awareness of environmental issues. One solution is to aggregate clients (CLs) into one Access Point (AP), and to reduce active APs. However, limited communication ranges of APs limit the number of active APs which can be reduced. In this paper, we propose a method for reduction of active APs using multi-hop communication. This method allows CLs outside the communication range of an AP to use the AP via adjacent CLs, which makes more CLs be aggregated into one AP, and reduces more active APs. We select APs which can aggregate more CLs as active APs by an AP selection algorithm based on formulation of power-saving effect of multi-hop communication. We avoid fatal influences on the communication of CLs by setting a threshold for each CL’s throughput and not selecting APs below the threshold. We evaluate our proposal by simulations and real machines, and show its effectiveness. Keywords: wireless LAN, power-saving, reduction of active APs, multi-hop communication 1. はじめに 接続のために不可欠なものとなっている．ノート PC 等の 無線クライアント（CL）はネットワークを使用する方法 IEEE 802.11 に代表される無線ネットワークは家や会社 の 1 つとしてアクセスポイント（AP）と呼ばれるノード オフィス，大学キャンパス等でインターネットへの柔軟な を使用する．AP は CL を相互に接続したり，有線ネット ワークに接続したりするための無線機である．特に大規模 1 a) 慶應義塾大学大学院理工学研究科 Graduate School of Science and Technology, Keio University, Yokohama, Kanagawa 223–8522, Japan [email protected] c 2013 Information Processing Society of Japan なビルでは，CL 数の増減や CL が要求する通信速度の増 減に柔軟に対応するために，必要と想定される数より多く 610 情報処理学会論文誌 Vol.54 No.2 610–620 (Feb. 2013) の AP を建物内に配置する例がある [1]． における消費電力削減効果を示し，トポロジの違いによる しかし近年，環境問題への意識の高まりから消費電力削 効果の差を検討する．実機評価では，大学研究棟内に数台 減が社会的な大きな課題として考えられている．それにと の AP と CL を設置し消費電力の測定，CL の通信状況の検 もない，ネットワークの研究においても省電力化が重要な 証を行うことで，マルチホップ通信によって AP 数を低減 テーマとして考えられている．現在の ICT における消費電 させ消費電力を削減することと，CL のスループットを維 力は 2006 年度の時点で日本の総消費電力の約 5.8%を占め 持し，遅延とパケット損失率を抑制できることを確認する． 増加傾向にあり，2012 年にはネットワークにおける消費電 以下，2 章で関連研究とその問題点を述べ，3 章で提案手 力が ICT 全体の約 50%を占めると推定されている [2]．そ 法について述べる．そして 4 章で評価について述べ，5 章 の課題に対し，利用者が急速に増加している無線 LAN に に結論を示す． おいて，トラヒック量削減により AP の送受信に費やす電 力の削減を図る研究が行われている [3], [4]．しかし後述の ように，無線 LAN の構成に重要な AP の消費電力におけ 2. 関連研究 2.1 トラヒック量削減による消費電力削減 る無線インタフェースが占める消費電力の割合はトラヒッ 消費電力削減のためにトラヒック量削減が提案されてい ク量が多い場合でも全体の 1 割にも満たない．つまり，ト る [3], [4], [7]．文献 [3] は，無線 LAN における省電力モー ラヒック量を削減しても無線 LAN の消費電力の削減に与 ドと通常モードの従来の切替え方式は制御パケットの衝突 える影響はとるに足らない． によりシステムスループットが減少するという問題を取り 無線 LAN の消費電力削減のための別の方法として，通 上げ，モード切替えのタイミングは AP と CL 間で共有さ 信量の少ない CL を 1 台の AP に集約し，使用する AP 数 れているため切替え時の制御パケットの送信は冗長である を低減させる研究がある [1], [5], [6]．企業等は CL の通信 とし，送信を抑制することで，省電力効果を落とさずにス 量に柔軟に対応するために多くの AP を設置するが，それ ループットを向上させる．シミュレーションにより，省電 らはまったくのアイドル状態でも最大時と同等の電力量を 力モードをいっさい用いない場合と同等程度のスループッ 消費していることが多い．そこで通信量が少なく要求する トを実現しながら，従来のモード切替え方式を用いた場合 伝送速度の低い CL の接続を 1 台の AP に集約する．これ と同等程度の省電力効果を実現することを示す．つまり， により，使用する AP 数を低減させることができ，使用し 冗長な制御パケットの送信を抑制することで，単位あたり ない AP をスリープさせることで消費電力を大幅に削減で のスループットに消費される電力を削減するといえる．文 きる．しかし，それらの研究では通信範囲の観点から低減 献 [4] は，無線 LAN でのストリーミングにおいてデータス させることができる AP 数に限りがある．CL の通信量が ケジューリングのために CL が消費する電力は，従来方式 少なくても，他に接続できる AP がなければその AP を使 では MAC 層でスケジューリングするために CL の無線イ 用し続けなければならない．使用する AP 数をより減らす ンタフェースの電源を完全には停止できなかったが，アプ ために AP にできるだけ多くの CL の接続を集約するには， リケーション層で消費電力を意識したスケジューリングを AP の通信範囲には直接属さない CL もその AP に接続で 提案し実現することで CL の無線インタフェースの電源を きるような仕組みが必要である． 完全に停止し消費電力を削減する．シミュレーションによ そこで本論文では，マルチホップ通信を用いた AP 数低 減手法を提案する．CL が他の CL を経由して AP に接続 り，従来方式と比べ，フレーム損失を起こさずに消費電力 を削減することを示す． することで，AP の電波が直接到達していない CL もその AP を使用できる．これにより，より多くの CL を 1 台の 2.2 AP 数低減による消費電力削減 AP に集約でき，AP 数を低減させることができる．その まず，冗長な AP が存在する可能性は高い．会社オフィ 際，消費電力削減の観点からはすべての CL を 1 台の AP スや大学キャンパスでは，高密度に数百から数千もの AP に集約することが理想だが，過多な CL の集約やホップ数 が配置されていることが少なくない．多数の AP を配置す の増加は通信速度の大幅な低下や遅延の増加等を引き起こ る主な目的は広帯域や移動性，信頼性といったユーザの す．そこで，まずはマルチホップ通信による無線 LAN の 要求を満足させることである．しかし実際には，これらの 消費電力削減効果を定式化し，消費電力削減量を最大化す ネットワークは許容量を超えることは滅多になく，通信 るように使用する AP を選択する．その際，CL の使用可 量の多い昼間でさえ 10∼20%の AP がアイドル状態であ 能帯域幅等にスレッショルドを設け，スレッショルドを満 る [1]．アイドルな無線 LAN 資源はそれらがアイドルであ たさない AP を選択しないことで，CL の通信に多大な影 る間，電力を浪費することを意味する． 響を及ぼさずに AP 数を低減させる． そこで，集中管理された無線 LAN 環境において，ユー 本論文ではシミュレーションと実機実装により，提案手 ザの需要に合わせて起動する AP 数を低減させ消費電力 法の評価を行う．シミュレーションでは，様々なトポロジ の削減を図るリソースオンデマンド戦略が提案されてい c 2013 Information Processing Society of Japan 611 情報処理学会論文誌 Vol.54 No.2 610–620 (Feb. 2013) る [1], [5], [6]．文献 [1] は，ユーザの通信状況をオンライ である．それゆえ，トラヒック量を削減しても消費電力削 ンで測定し，ユーザの通信量や位置に応じて AP やスイッ 減量はたかだか 0.2 VA である．これに対し，AP 自体を停 チ，ルータ等の無線機器の電源を切り，できるだけ多くの 止するとおよそ 16 VA の消費電力削減が期待できる．よっ CL の接続を 1 台の AP に集約する．実機実装による評価 て，無線 LAN の省電力化のためには，トラヒック量の削 により，ユーザの通信品質を維持しながら，わずかな通信 減よりも，AP を停止して AP 数を低減させることが効率 量のために使用される AP の数を低減させ，消費電力を削 的であると考えられる． 減することを示す．文献 [5] は，ユーザの需要を 2 種類の基 文献 [1], [5] はユーザの通信状況に応じて冗長な AP を停 準によって測定し，それらの基準に基づいて各 AP の電源 止し，AP 数を低減させることで無線 LAN の省電力化を 管理を行う．1 つの基準は各 AP に接続しているユーザ数 図る．しかし，これらの手法では通信範囲の観点から低減 であり，もう 1 つの基準は各 AP に対しトラヒックを生成 させることができる AP 数に限りがある．通信量の観点か しているユーザ数である．シミュレーションにより，ユー らは AP に集約できる CL でも，その AP の通信範囲に含 ザの通信量が少ないときには，両モデルとも QoS を維持 まれていなければ集約できないからである．他の AP に接 しながら最大 87%まで消費電力を抑制することを示す．文 続できない CL がわずかでもトラヒックを発生していれば 献 [8] は，AP の消費電力削減に対し無線モジュールの停止 AP は停止できないため，消費電力は削減できない．よっ が効果的だが無線による遠隔からのスリープ解除は困難で て，使用する AP 数をより減らすために AP にできるだけ あるという問題に対し，必要に応じて CL が無線 LAN 信 多くの CL の接続を集約するには，AP の通信範囲には直 号を用いてスリープ中の AP を起動し接続を行う，AP の 接属さない CL もその AP に接続できるような仕組みが必 オンデマンド起動方式を提案する．AP に備え付ける信号 要である． 受信機を試作し，ビット誤り率の測定，無線 LAN 信号の フレーム長検出誤り率の解析を行い，無線 LAN の通信エ リアと同等以上のエリアにおいて AP のオンデマンド起動 が可能であることを示す． 3. マルチホップ通信を用いた AP 数低減手法 本論文では，CL が CL を経由して AP に接続するという マルチホップ通信を用いた AP 数低減手法を提案する．本 手法の目的は，直接通信を行うことができない AP への接 2.3 関連研究の問題点 続を可能にすることでより多くの CL の通信を 1 台の AP 文献 [3], [4] は，トラヒック量削減により無線 LAN シス に集約し，不要になった AP を停止させることでより多く テムの消費電力を削減する．しかし，トラヒック量削減によ の AP 数を低減させ，無線 LAN システム全体の消費電力 る AP の消費電力削減の効果は薄い．図 1 にトラヒック量 削減効果を向上させることである． の変化にともなう AP の消費電力量の測定結果を示す．測 定には，電力メータとして Sanwa Watt checker AZT2000， 3.1 提案概要 AP として Buffalo の WZR-AMPG144NH と Cisco の AIR- 本論文では，オフィスビルや大学研究棟のように，複数 AP1142N-P-K9，CL として Lenovo の ThinkPad X201i を の部屋が隣接し 1 部屋に数台の AP が設置され，通信範囲 用いた．図 1 より，トラヒック量の増減による AP の消費 が重複している環境において，マルチホップ通信を用いる 電力の増減は AP 全体の消費電力と比べて数%程度である ことで原理的に消費電力を削減できる可能性を示すことに ことが分かる．わずかでもトラヒックが発生していれば， 主眼を置く．エリア内の無線 LAN を一括管理する者が存 消費電力量は 16.0 VA である．15 Mbps のときは 16.2 VA 在する環境を想定し，システム内の全 AP，CL は集中管理 されているものとする．提案手法によってトポロジが変更 される前である初期状態において，各 CL は最寄りの AP を使用して動作中のアプリケーションに支障をきたすこ となく通信できているとする．管理者は各 AP/CL の電波 到達範囲，各 CL が動作するアプリケーションの種類や使 用可能帯域幅等の情報をあらかじめ把握している．アプリ ケーションの種類としては，VoIP，動画等のストリーミン グ，Web 閲覧のいずれかとし，CL が生成するトラヒック 量は一定もしくは最大容量が制約されていると想定する． そして，管理者はそれらの情報を基に AP 選択アルゴリズ ムを実行し，算出したトポロジに従って各 AP の電源管理， 図 1 AP，CL の消費電力 各 CL の接続先変更を行う．提案手法実行後，他の CL の Fig. 1 Power consumption of APs and a CL. トラヒックを中継する CL を中継 CL と呼ぶ．非中継 CL c 2013 Information Processing Society of Japan 612 情報処理学会論文誌 Vol.54 No.2 610–620 (Feb. 2013) より中継 CL の方が消費電力が大きいため，中継 CL と非 中継 CL の消費電力を区別する．AP の消費電力は，図 1 より，トラヒック量にほとんど左右されないとして定数で 扱う．また，現在の標準的な AP 本体の消費電力はおよそ 10 W であるのに対し，送信出力に必要な電力は最大でも およそ 0.05 W であることから，AP の送信出力を最小にす ることによる AP 本体の消費電力削減効果は薄いと考え， AP の送信出力は最大で一定とする．CL は通信品質の要 図 2 システム例 求変更・移動・離脱は行わないとする． Fig. 2 A system example. 本提案では，マルチホップ通信導入の消費電力削減効果 を定式化し，消費電力削減量が最大になるようにシステム のトポロジを決定する．提案手法実行後のシステムにおい て起動している AP を起動 AP と呼び，接続ツリーを用い て各 CL の接続先を決定しながら起動 AP を選択する．接 続ツリーとは，初期状態において接続可能な AP/CL を表 したツリーである．各 CL の接続先決定の際は，CL の使 用可能帯域幅，遅延，パケット損失率を推定し，CL で動 作するアプリケーションの通信品質の要求を満たすか事前 (a) 手順 (1) 図 3 (b) 手順 (2)∼(3) 図 2 の例における AP1 の接続ツリー作成 Fig. 3 Making AP1’s connectable tree in the example of Fig. 2. に確認する． を表したツリーである．AP 選択アルゴリズムにおいてト 3.2 マルチホップ通信による消費電力削減効果 ポロジの把握のために用いられる．システムの一例を示す マルチホップ通信の導入による無線 LAN システム全体 の消費電力削減効果を定式化する．初期状態において，N 台の AP，M 台の CL から構成されるシステム全体の消費 電力 P は次式で示される． P = αN + βM 図 2 を用いて接続ツリーの作成方法を述べる．図 2 の円 は各 AP/CL の電波到達範囲を示す． (1) まず，1 台の AP を根として，接続可能な範囲に存在 する CL を子に追加する．AP1 に着目すると，AP1 の通信 (1) 範囲には CL1，CL2，CL3 が存在するため，図 3 (a) のよ うなツリーが得られる． ここで，α は AP の消費電力，β は非中継 CL の消費電力 (2) 次に，葉の CL は接続可能な範囲に存在する CL を子 である．一方，提案手法実行後，AP を N 台中 n 台停止で に加える．ただし，ツリー内にすでに存在する CL は加え き，中継 CL が m 台，非中継 CL が M − m 台になったと ない．例では葉の CL3 の通信範囲に CL4，CL5 が存在す すると，システム全体の消費電力 P は次式で示される． るため，図 3 (b) のように接続ツリーを更新する．CL2 の P = α(N − n) + β m + β(M − m) (2) 通信範囲に CL3 が存在するが，CL3 はすでにツリーに含 まれているため加えない． ここで，β は中継 CL の消費電力である．よって，提案手 法による消費電力削減効果 R は，次式で示される． (3) 追加できる CL がなくなるまで (2) を繰り返す．そ の際，提案手法の消費電力削減効果が低い場合でも消費電 R = P − P (3) R = αn − (β − β)m (4) 力が削減できるように，内部ノード数つまり中継 CL 数を α/(β − β) に制限する．本論文では中継 CL の消費電力を 中継する CL 数やトラヒック量によらず，定数 β としてい ここで，AP 数低減により消費電力を削減できるとすると るため，中継 CL が直接 1 台の CL しか中継しない場合は n ≥ 1，R > 0 である．そのとき，次式を満たすように m， 提案手法の消費電力削減効果が低い．その場合にも 1 台の n を設定する必要がある． AP 停止による消費電力削減効果を，非中継 CL が中継 CL m α > β − β n (5) になるために増加する消費電力量で打ち消すのを防ぐため には，中継 CL 数を α/(β − β) に制限する必要がある．例 このうち，左辺はシステムでの定数となるため，それに では葉の CL4，CL5 の通信範囲に CL3 が存在するが，す 従って m，n を設定すればよい． でにツリー内に含まれているため加えない．よって，AP1 の接続ツリーの作成は図 3 (b) をもって終了する． 3.3 接続ツリーの作成 接続ツリーとは，初期状態において接続可能な AP/CL c 2013 Information Processing Society of Japan 以上の動作を各 AP に対して行う．全 CL が初期状態に おいて最低 1 台の AP に接続しているという前提があるた 613 情報処理学会論文誌 Vol.54 No.2 610–620 (Feb. 2013) め，深さ 1 で最低 1 つの接続ツリーに含まれる． ここで，need B i は nodei において動作中のアプリケー ションの通信維持に必要な帯域幅である． 3.4 CL の使用可能帯域幅，遅延，損失率の推定 (b) 遅延 各 CL の接続先決定の際，CL の使用可能帯域幅，AP ま での遅延時間，AP までのパケット損失率を後述の方法に CL から k ホップ離れた AP までの遅延 Dk は，i ホップ 目における遅延 di を用いて次式によって推定する． より推定し，ユーザが動作するアプリケーションの要求を Dk = 満たすか事前に確認する． di (9) i=1 (a) 使用可能帯域幅 CL の使用可能帯域幅の推定には，文献 [9] で導出された di は実測値に基づき既知とする．そのため，di にはデー タ処理時間，伝搬時間等が含まれる．また一般に，マルチ リンク i のスループット ei を示す次式を利用する． ei = xi · (1 − γi ) · d · data rate k ホップ通信を用いた無線 LAN では，AP に近いリンクほ (6) ど多くのトラヒックが流れるため送信キューでの待ち時間 ここで，xi はリンク i の送信エアタイム，γi をリンク i の も大きくなる．しかし，本論文ではトラヒック負荷が制限 衝突率とする．また，d = DAT A/(DIF S + P ACKET + されているとしており，それに合わせてボトルネックリン SIF S + ACK) であり，DAT A はデータペイロードの クのスループットを十分にとれば，遅延は小さく収まる． 送信時間，DIF S は DIFS 時間，P ACKET はパケット よって，AP に近い CL における送信キューでの待ち時間 の送信時間，SIF S は SIFS 時間，ACK は ACK の送信 の増加はほとんどないと見なせる． 時間，data rate は伝送速度を表す．なお，本論文では (c) 損失率 バックオフタイム back of f を固定長として考慮し，d = CL から k ホップ離れた AP までのパケット損失率 Γk は DAT A/(DIF S + back of f + P ACKET + SIF S + ACK) 文献 [9] で述べられているリンク i における隠れ端末によ とする．また，伝送速度は受信信号強度（RSSI）から ARF るパケット衝突率 γi を用いて次式によって推定する． （Auto Rate Fallback）により求める．ARF とは，無線 LAN において RSSI の値に応じて伝送速度を自動調整する機能 Γk = 1 − (1 − γ1 ) · (1 − γ2 ) · · · · · (1 − γk ) (10) である．文献 [9] では，マルチホップ通信において，経路 パケット損失の要因として隠れ端末による電波干渉や が決まっている様々なトポロジにおいて CBR トラヒック バッファあふれが考えられる．このうち，バッファあふれ を生成する際のエンドツーエンドでの最大スループットを による損失はほとんど起きないと考えられる．なぜなら， 隠れ端末等による衝突率やキャリアセンスの動作を考慮 バッファあふれはトラヒックが出ていく量に対して入っ して解析している．式 (6) によって各リンクの最大スルー てくる量が大きいと，バッファにトラヒックが溜まるため プットが得られ，ボトルネックリンクのスループットがそ 発生するが，本論文ではトラヒック負荷が制限されてい のトポロジの最大スループットである．つまり，AP であ るとしており，それに合わせてボトルネックリンクのス る node0 から k ホップして接続する CL である nodek の最 ループットを十分にとれば防げると考えられるからであ 大スループット Ek は次式で示される． る．よって，CL から AP までのパケット損失率は隠れ端 Ek = min{e1 , e2 , · · · , ek }({li } ⊆ Lk ) (7) ここで，li は nodei−1 と nodei の間のリンク，Lk は node0 末からの干渉による損失を基に算出すればよい． 3.5 CL の通信品質維持の確認 CL において動作するアプリケーションの必要帯域幅，許 から nodek までの経路上のリンクの集合である． マルチホップ通信においては同一リンクに複数の CL に 容遅延，許容損失率について述べる．これらは各 CL の接 よるトラヒックが流れるため，Ek が nodek の使用可能帯 続先決定の際に通信品質の維持を確認するために，上述の 域幅 Bk であるとは限らない．そのため，次のようにして 方法で推定された使用可能帯域幅等の情報と比較される． 接続ツリー内の CL を幅優先探索したときに i 番目となる 本論文では，CL が行う通信形態を VoIP，動画等のスト リーミング，Web 閲覧に大別して考え，各 CL はいずれ nodei の使用可能帯域幅 Bi を求める． ⎧ ⎪ (i = 1 かつ CL が非中継 CL) ⎪Ei ⎪ ⎪ ⎪ ⎪ need B i (CL が中継 CL かつ ⎪ ⎪ ⎨ i−1 Bi = Ei − need B j ≥ need B i ) ⎪ ⎪ j=1 ⎪ ⎪ ⎪ i−1 ⎪ ⎪ ⎪ need B j (上記以外) ⎩Ei − か 1 つの通信を行うものとする．VoIP を使用する場合は スループットが 100 kbps 以上，遅延が 50 msec 以下，損失 率が 3%以下 [10] であることが条件とする．よって，この 場合 need B i = 100 kbps となる．ITU では片方向の全体 的な遅延には 150 msec 以下が推奨されている [11]．この うち，符号化遅延が 10 msec，パケット化遅延が 30 msec， j=1 (8) c 2013 Information Processing Society of Japan バックボーンネットワークによる遅延が 20 msec，ジッタ 614 情報処理学会論文誌 Vol.54 No.2 610–620 (Feb. 2013) バッファ遅延が 30 msec，復号化遅延が 10 msec と想定 [10] を満たすか確認する．満たさない CL が存在した場合は， し，AP と CL 間の遅延を 50 msec 以下とする．ストリーミ 他ツリーにも含まれる CL の中でそのツリーにおいて最 ングは，動画ストリーミングの標準サイズである 512 kbps も深い位置にある CL をツリーから削除し，使用可能帯域 以上のスループットが出ることを条件とする．Web 閲覧 幅等を再計算する．他ツリーにも含まれる CL で最も深い は，VoIP やストリーミングのような強い制約はないが， CL が複数ある場合は，幅優先探索で前に来る CL から削 余裕を持たせるために制約の強いストリーミングに合わせ 除する．たとえば図 5 の例において AP1 の接続ツリーの て 512 kbps 以上のスループットが出ることを条件とする． CL3 が通信の要求条件を満たしていない場合，AP1 の接続 よって，CL がストリーミングと Web 閲覧を使用する場合 ツリーから，AP2 の接続ツリーにも含まれる CL2，CL3， は need B i = 512 kbps となる． CL4，CL5 の中で，最も深い位置にあり幅優先探索で前に ここで，ホップ数増加やトラヒック中継による使用可能 くる CL4 を削除し，再計算する．この際，使用可能帯域幅 帯域幅の低下の偏りを CL 間で平等にするため，帯域幅減 等の条件を満たしていない，かつ，他ツリーも含まれる CL 少割合許容スレッショルド T hB （0 < T hB < 1）を設け がない状況は発生しない．なぜなら，全 CL は初期状態に る．初期状態における使用可能帯域幅を基準に，その T hB おいて最低 1 台の AP に QoS を満たして接続していると 倍の帯域幅を保証帯域幅とし，提案手法実行後も維持する． いう前提があるからである．自身が中継 CL となるために T hB は提案手法実行時にヒューリスティックに定める． QoS を満たさない CL が存在したとしても，子は他のいず れかの AP に QoS を満たして接続できることが保証され 3.6 AP 選択アルゴリズム 起動 AP を選択する AP 選択アルゴリズムについて述べ る．マルチホップ通信を用いた無線 LAN における消費電 ているため，子を削除できる．図 5 の例では，CL4 は AP1 の接続ツリーから削除されても，AP2 への接続が保証され ている．よってフェーズ B のループは必ず終了する． 力削減効果は式 (4) で表される．式 (4) の値を最大化する 次に，起動 AP を 1 台ずつ選択する（フェーズ C）ため ために，1 台の AP に接続する CL 数をできるだけ多くす に，必ず起動しなければならない AP を選択する．この ることで AP の停止台数 n を大きくし，その中で中継 CL ような AP を必須 AP と呼ぶ．必須 AP とは，接続できる 数 m の増加をできるだけ抑える． AP が 1 つしかない CL を含む AP であり，どのような AP 図 4 に AP 選択アルゴリズムのフローチャートを示す． 選択方法でもその CL のネットワークへの接続を保つため まず各 AP の接続ツリーを作成する（フェーズ A） ．図 2 に最終的に必要となる．CL 数が最大の必須 AP から選択 のようなシステムであれば，図 5 のような接続ツリーが得 し，同数の場合は中継 CL 数が最小の必須 AP を選択する． られる． 図 5 の例では CL1 が AP1 にしか接続できないため，AP1 次に，各接続ツリー中の全 CL について，通信品質維持 の確認を行う（フェーズ B） ．その時点での接続ツリーを基 は必須 AP であり，起動 AP となる．必須 AP が存在しな い場合は，CL 数が最大のツリーを持つ AP を選択する． に，各 CL の使用可能帯域幅・遅延・パケット損失率を計 CL 数が最大のツリーが複数存在する場合は，中継 CL 数 算し，それぞれの CL がその位置において通信の要求条件 が最小の AP を選択する．そして，ツリーに従っての CL の接続先を決定し，接続先が決定した CL を他ツリーから 削除する．以上のフローをすべての CL の接続先が決定す るまで繰り返す．全 CL の接続先が決定するとフェーズ C は終了し，全起動 AP を出力してアルゴリズムが終了する． 図 5 の例では AP1 を起動 AP として選択した時点で全 CL の接続先が決定するため，全起動 AP のリストとして AP1 を出力して終了する．もし，フェーズ B で AP1 の接続ツ リーから CL4 が削除されていたら，CL4 のみが接続され 図 4 AP 選択アルゴリズム た AP2 も出力される． Fig. 4 AP selection algorithm. 4. 評価 4.1 シミュレーションによる評価 AP 選択アルゴリズムを Java を用いて実装し，表 1 で示 されるパラメータにより AP，CL をランダムに配置し，そ れぞれの配置において提案手法実行後のトポロジを求め， 図 5 図 2 の例における接続ツリー Fig. 5 Connectable trees in the example of Fig. 2. c 2013 Information Processing Society of Japan 消費電力を算出した．シミュレーションエリア，AP 数， CL 数は大学研究棟の配置状態を参考に決定した．1 フロア 615 Vol.54 No.2 610–620 (Feb. 2013) 情報処理学会論文誌 表 1 シミュレーションパラメータ Table 1 Simulation parameters. シミュレーションエリア 50 m × 50 m AP 数 N 3∼20 台 CL 数 M 3∼20 台 AP の消費電力 α 16 VA 非中継 CL の消費電力 β 23 VA 中継 CL の消費電力 β 27 VA T hB 1/5 ペイロードサイズ 1,460 byte ACK サイズ 14 byte DIF S 34 μsec back of f 67.5 μsec SIF S 16 μsec data rate 5.5∼54 Mbps 図 6 消費電力削減率 Fig. 6 Reduction rate of the power consumption. が約 50 m × 50 m であり，1 部屋約 120∼800 m2 に AP が 1 台あるため AP 数を 3∼20 とした．また AP 数に対して 通信量が少ない状況を想定するため，CL 数は AP 数と同 じにした．AP と CL はプログラムにより位置座標をラン ダムに決定し，全 CL が初期状態において最低 1 台の AP に QoS を満たして接続している前提を満たした配置のみ を採用した．AP と CL の電力は，図 1 で示される AP と CL のトラヒックと消費電力の相関の実験結果を基にした． CL の電力消費量はトラヒック量によって様々な値をとり うるが，本シミュレーションではワーストケースを再現し， 図 7 基本必須 AP の割合に応じた消費電力削減率 Fig. 7 Reduction rate according to rate of basic essential AP. 中継 CL の電力は最大の 27 VA とした．T hB は後に示すと おり，本環境での適切な値 1/5 を用いた．ペイロードサイ め削減率が低い．CL 数が AP 数の 2 倍以上の場合は，マ ズは最大の 1,460 byte，ACK サイズは IEEE 802.11 で使用 ルチホップ通信を用いることによる削減率はおよそ 6%程 されている 14 byte とした．DIFS 時間，SIFS 時間は IEEE 度であり，CL と AP がほぼ同数のときはおよそ 10%電力 802.11g 規格に則り，それぞれ 34 μsec，16 μsec とした．ま 消費量を削減できる．しかし，平均 CL 数が同数でも削減 たバックオフタイムは平均値 67.5μsec とした．伝送速度 率には差がある．その原因を，CL と AP が同数の時を例 は文献 [12] に従い，RSSI を実環境での測定結果により得 とし，図 7 を用いて説明する． たノード間の距離に変換した．5 m 以内の場合は 54 Mbps， 図 7 に CL と AP が同数のときの全 AP 数に対する基本 10 m 以内の場合は 24 Mbps，15 m 以内は 12 Mbps，20 m 必須 AP 数の割合と消費電力削減率の関係を示す．基本必 以内の場合は 5.5 Mbps，20 m より大きい場合は接続不能 須 AP とは，基本トポロジにおける必須 AP である．図中 とした． の各プロットは AP と CL の配置を変えて 5 回シミュレー 図 6 に T hB = 1/5 のときの 1 台の AP に接続する平均 ションを行った際の平均値である．図 7 より，基本必須 CL 数と消費電力削減率の関係を示す．消費電力削減率と AP が多い場合は提案手法による効果が大きく，基本必須 は，基本トポロジにおけるシステム全体の消費電力に対す AP が少ない場合は提案手法の効果が小さい．これは，基 る提案トポロジにおけるそれの削減量の割合を示す．基本 本必須 AP が多ければ AP の代わりに CL を中継 CL とし トポロジとは 2.2 節であげた既存研究のように CL から 1 て使用することで消費電力削減の余地があるが，基本必須 ホップ圏内で AP 選択を行った場合のトポロジであり，提 AP が少ないと基本トポロジの時点ですでに比較的多くの 案トポロジとは提案手法の AP 選択実行後のトポロジであ AP を停止させることができているため，それ以上の消費 る．図中の各プロットで AP と CL の配置は異なり，1 プ 電力削減は困難となるからである．基本必須 AP が多い状 ロットにつき 1 回の評価結果である．図 6 より，基本トポ 況とは，たとえば，各 AP が地理的に均等に距離を隔てて ロジより提案トポロジの方が消費電力が低いことが確認で 分布し各 CL と近接しているために，各 AP が各 CL 専用 きる．また，CL 数が多い場合はトラヒック量も増え，多 のように存在するような状況である．また，基本必須 AP くのトラヒックを処理するために必要な AP 数が増えるた の割合が 50%以下になると，削減率の低下が鈍化する．こ c 2013 Information Processing Society of Japan 616 情報処理学会論文誌 Vol.54 No.2 610–620 (Feb. 2013) 図 8 最大中継 CL 数に対する消費電力削減率 図 10 AP と CL の配置 Fig. 8 Reduction rate for every maximum number of relay CLs. Fig. 10 The placement of APs and CLs. く保つが，削減率が低い．Ptr が低く保たれ，削減率が大 きくなるように T hB を設定すべきである．よって，適切 な T hB は，Ptr が急増する前であり削減率の増加が鈍化す る前である図 9 に斜線で示されている部分であり，およそ 1/4∼1/6 であると考えられる． 4.2 実機実装による評価 実機実装により提案手法が CL の通信を維持しながら消 図 9 1 Mbit のデータ転送における消費電力と消費電力削減率 Fig. 9 Power consumption per Mbit and reduction rate. 費電力を削減することを示す．4.1 節で作成したプログラ ムを用いてトポロジを求めた後，実機を用いて接続関係を 手動で再現し，電力メータにより消費電力を測定した．実 れは，提案手法では T hB を用いて CL の通信品質を維持 機実装による再現は現実的な環境で行うために，実際に無 しているからだと考えられる．T hB = 1/5 のとき，基本必 線ネットワークを扱う大学研究棟の隣接した 2 部屋で行っ 須 AP の割合が 50%以下では AP を停止しすぎると，CL た．各部屋はともにおよそ 7.5 m × 7.5 m の大きさである． の通信が維持できなくなってしまうと考えられる． 部屋には机や本棚等日常に使用される備品が多く存在して 図 8 に最大中継 CL 数に対する消費電力削減率を示す． いる．部屋と廊下の間には鉄筋コンクリートの壁がある． AP1 台あたりの許容する最大中継 CL 数を α/(β − β) 以下 近隣の部屋にも異なるネットワークがあり，20∼30 の無 で変化させ，各最大中継 CL 数に対して AP と CL の配置 線ネットワークが構築されている．AP，CL の配置は 4.1 を変えて 5 回シミュレーションを行い，それぞれの場合に 節で作成したプログラムにより位置座標をランダムに決定 おいて削減率の平均値を計算した．図 8 より，中継 CL 数 し，全 CL が初期状態において最低 1 台の AP に QoS を が増加すると消費電力を削減できることが分かる．また， 満たして接続している前提を満たした配置 1 種類のみを採 中継 CL 数の増加にともない削減率の増加が鈍化する．こ 用し，消費電力の測定を 1 回行った．なお，本環境におい れは，非中継 CL が中継 CL となり電力消費量が増えるた ては CL の使用可能帯域幅推定の際に，3.4 節で推定され めだと考えられる． た値を 0.8 倍した値を用いた．これは，実環境においては 図 9 に各 T hB における 1 Mbit データ転送で消費する 電力量 Ptr と消費電力削減率の関係を示す．各 T hB に対 d · data rate は実測値が推定値より約 15∼20%下回ったか らである． して AP と CL の配置を変えて 12 回のシミュレーション 図 10 に各部屋における AP と CL の配置を示す．実 を行った．Ptr は大きくなるとトラヒックの単価が高くな 線は結ばれたノードどうしが接続可能であることを示す． るため望ましくない．Ptr は T hB の低下にともない増加し CL1，CL2，CL5，CL6 は Web 閲覧を行い，CL4 と CL7 ている．T hB が低下するほど，CL の通信維持の要求は低 はストリーミングを行い，CL3 は VoIP を使用するとした． くなるため，基本的にホップ数は増加する．つまり，マル 各リンクの数字は両端のノードにおける互いの RSSI に基 チホップ通信により中継 CL 数が増加するほど，Ptr は大 づいて計算した伝送速度である．RSSI が両端のノードで きくなる．T hB が 1/6 まではほぼ一定であり，1/6 以下で 異なる場合は小さい方の値を用いた．T hB = 1/6 に設定 急激に増加する．一方，消費電力削減率は T hB が低下す した． るほど増加しており，マルチホップ通信の効果が大きくな 図 11 に基本トポロジを示す．このトポロジにおいてト る．T hB が 1/4 までは大幅に増加し，1/4 以下では増加が ラヒックを発生させたところ，システム全体の消費電力は 鈍化する．低すぎる T hB の設定は削減率を増加させるが， 263.4 VA であった． Ptr を増加させる．また，高すぎる T hB の設定は Ptr を低 c 2013 Information Processing Society of Japan 次に，図 12 に提案トポロジを示す．図 11 との比較に 617 情報処理学会論文誌 Vol.54 No.2 610–620 (Feb. 2013) 図 11 基本トポロジ Fig. 11 The basic topology. 図 14 最適解との比較 Fig. 14 Comparison of the proposal with the best answer. あった．これらは，VoIP を使用する場合に保証すべき品 質である遅延 50 msec 以下，パケット損失率 3%以下を満 たしている．以上より，提案手法を用いたときに各 CL の スループットが維持され，遅延とパケット損失率が許容範 囲を超えていないことが確認できる． 図 12 提案トポロジ Fig. 12 The proposal topology. 4.3 評価結果と実現可能性の考察 提案手法の位置付けと評価結果から，提案手法の目的が 達成されたかを考察する．提案手法の目的は，マルチホッ プ通信によってより多数の CL の通信を少数の AP に集約 し，不要な AP を停止させることで無線 LAN の消費電力 を削減することである．本論文では，シミュレーションと 実機実装による評価によって提案手法が原理的に消費電力 を削減できることを示すことに主眼を置いている．評価で は，シミュレーションと実機実装の双方において，提案手 法は基本トポロジより消費電力を削減することを示せた． また，シミュレーションにより T hB = 1/5 のときに 6 種 類の AP と CL の配置において最適解と提案手法を比較し 図 13 各 CL のスループット た所，図 14 のようになった．最適解とは消費電力削減率 Fig. 13 Throughput of each CL. が最大となるよう各 CL の接続先を総当りで調べた場合で ある．図中の各プロットは AP と CL の配置を変えて 5 回 より，マルチホップ通信を用いると，さらに 2 台の AP を シミュレーションを行った際の平均値である．図 14 より， 停止させることができたことが分かる．合計の消費電力も 提案手法は最適解に近い消費電力削減効果があると考えら 236.4 VA に減少した．よって，実機においても消費電力を れる．よって提案手法の目的は達成したといえる． 10.25%削減できることを確認した． CL の通信が維持されていることを示すため，提案手法 また，本手法を実現するためには，管理方法，各種情報 の収集・伝達方法，AP の電源管理・各 CL の接続先変更方 実行後の各 CL とその CL が接続している AP との間のス 法，CL の移動への対応方法について検討する必要がある． ループットを測定した．スループットの測定には Iperf [13] まず，管理方法については，本論文では各 AP と有線で接 を用いた．100 秒間の測定を 10 回繰り返し，その平均値を 続する管理サーバによる集中管理を想定している．各 AP， 測定値とした．図 13 に各 CL の保証帯域幅とスループッ CL では管理アプリケーションを動作させるとする．次に， トの測定結果を示す．各 CL のスループットはそれぞれ異 情報収集・伝達については各 AP/CL 内の管理アプリケー なるが，保証帯域幅を上回っていることが確認できる．ま ションが必要な情報を収集し，管理サーバに送信する．提 た，CL3 は VoIP を使用するため，CL3 の遅延とパケット 案手法で必要な情報のうち，CL が接続可能な AP/CL の 損失率を計測した．遅延の測定には Ping を用い，パケッ リストとそれぞれの AP/CL からの電波強度は CL で無線 ト損失率の測定には Iperf を用いた．100 秒間の測定を 10 スキャンを実行することで得られる．各 CL が生成するト 回繰り返し，その平均値を測定値とした．遅延の測定値 ラヒック量はアドミッションコントロールを行えば把握で は 21.8 msec であり，パケット損失率の測定値は 0.038%で きる場合もあるが，ベストエフォート型のトラヒックは事 c 2013 Information Processing Society of Japan 618 情報処理学会論文誌 Vol.54 No.2 610–620 (Feb. 2013) 前予測が難しい．そのため，帯域管理を導入する等，検討 が必要である．次に，AP の電源管理・各 CL の接続先変 更については，管理アプリケーションが管理サーバから受 [4] け取った指示に従って処理する．この際，CL の通信の切 断時間を短縮するために，CL の接続先変更の手順や接続 先変更完了の確認方法について検討する必要がある．最後 に，CL の移動に対応するために，移動ノード数に応じて アルゴリズムを再実行するか，または位置推定やハンドオ [5] フの既存研究を利用して移動ノードのみの接続先を変更 するかを切り替える．この際，アルゴリズム再実行による CL の再接続時間を明確にし，両手法を切り替える基準を 検討する必要がある．なお，AP が停止しているためにで [6] きている，死角に位置する CL が接続を希望した場合には， 文献 [8] の手法を適用すれば CL のネットワークへのリー チャビリティを得られると考えられる． 5. おわりに [7] 本論文では，CL が CL を経由して AP に接続するとい うマルチホップ通信を用いた AP 数低減手法を提案した． [8] 目的は，マルチホップ通信によってより多数の CL の通信 を少数の AP に集約し，不要な AP を停止することで無線 LAN の消費電力を削減することである．マルチホップ通 信による消費電力削減の効果を定式化し，消費電力削減量 [9] を最大化するように起動 AP を選択する．この際，各 CL の使用可能帯域幅，遅延，パケット損失率を推定しながら トポロジを決定することで，CL が動作するアプリケーショ ンの要求品質を常に満足させる．また T hB により，ホッ [10] プ数増加やトラヒック中継による使用可能帯域幅の減少割 合を CL 間で等しくする．シミュレーションと実機実装に よる評価では，AP 数が低減可能であり，システム全体の [11] 消費電力を削減できることを確認した．シミュレーション 評価では，T hB を変化させることで最大約 20%の消費電 [12] 力削減を示し，6 台の AP，7 台の CL を用いた実機実装に よる評価では，約 10%の消費電力削減を確認した．また， CL のスループット，遅延，パケット損失率を計測し，CL の通信品質を維持できることを確認した．よって，提案手 法は CL の通信品質に多大な影響を及ぼさずに AP 数を低 [13] through Arranged Power-saving Mechanism in Wireless LAN, IEEE International Conference on Communications, ICC ’06, Vol.10, pp.4780–4785 (2006). Acquaviva, A., Lattanzi, E. and Bogliolo, A.: Design and simulation of power-aware scheduling strategies of streaming data in wireless LANs, Proc. 7th ACM International Symposium on Modeling, Analysis and Simulation of Wireless and Mobile Systems, MSWiM ’04, New York, NY, USA, ACM, pp.39–46 (2004). Marsan, M.A., Chiaraviglio, L., Ciullo, D. and Meo, M.: A simple analytical model for the energy-efficient activation of access points in dense WLANs, Proc. 1st International Conference on Energy-Efficient Computing and Networking, e-Energy ’10, New York, NY, USA, ACM, pp.159–168 (2010). Fujimoto, K., Nobayashi, D., Fukuda, Y., Ikenaga, T. and Ito, T.: Power saving scheme with low-utilization station aggregation for Radio-On-Demand Networks, 2011 IEEE Pacific Rim Conference on Communications, Computers and Signal Processing (PacRim), pp.625–630 (2011). Noto, M.: An efficient flooding method in ad-hoc networks for reducing power consumption, IEEE International Conference on Systems, Man and Cybernetics, SMC 2008, pp.974–979 (2008). 近藤良久，四方博之，湯 素華，筒井英夫，小花貞夫： オンデマンド起動型無線 LAN アクセスポイントのため のウェイクアップ受信機の設計と評価，マルチメディア， 分散協調とモバイルシンポジウム 2011 論文集，Vol.2011, pp.286–291 (2011). Gao, Y., Chiu, D.-M. and Lui, J.C.: Determining the end-to-end throughput capacity in multi-hop networks: methodology and applications, Proc. Joint International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS ’06/Performance ’06, New York, NY, USA, ACM, pp.39–50 (2006). Shin, S. and Schulzrinne, H.: Measurement and Analysis of the VoIP Capacity in IEEE 802.11 WLAN, IEEE Trans. Mobile Computing, Vol.8, No.9, pp.1265–1279 (2009). International Telecommunication Union: International Telephone Connections and International Telephone Circuits, ITU-TG.114 (2003). Wireless Site Survey FAQ [Wireless, LAN (WLAN)] — Cisco Systems, available from http://www.cisco.com/ en/US/tech/tk722/tk809/tech-nologies q and a item09186a00805e9a96.shtml#qa23 (accessed 2012-0806). Iperf, available from http://iperf.sourceforge.net/ (accessed 2012-05-12). 減できる手法であるといえる． 参考文献 進藤 博子 （学生会員） [1] 2011 年慶應義塾大学理工学部情報工 [2] [3] Jardosh, A.P., Papagiannaki, K., Belding, E.M., Almeroth, K.C., Iannaccone, G. and Vinnakota, B.: Green WLANs: On-Demand WLAN Infrastructures, Mob. Netw. Appl., Vol.14, No.6, pp.798–814 (2009). Minami, M., Kawamura, R., Morikawa, H. and Hirabaru, M.: Power-Aware New Generation Network, The Transactions of the Institute of Electronics, Information and Communication Engineers, Vol.J92-B, pp.605–614 (2009). Kim, H.-D. and Cho, D.-H.: Throughput Enhancement c 2013 Information Processing Society of Japan 学科卒業．現在，同大学大学院理工学 研究科修士課程に在籍． 619 情報処理学会論文誌 Vol.54 No.2 610–620 (Feb. 2013) 鈴木 瑛識 （学生会員） 2012 年慶應義塾大学理工学部情報工 学科卒業．現在，同大学大学院理工学 研究科修士課程に在籍． 重野 寛 （正会員） 1990 年慶應義塾大学理工学部計測工 学科卒業．1997 年同大学大学院理工 学研究科博士課程修了．現在，同大学 理工学部教授．博士（工学）．情報処 理学会学会誌編集委員，同論文誌編集 委員，同マルチメディアと分散処理研 究会幹事等を歴任．現在，情報処理学会高度交通システム 研究会幹事，同モバイルコンピューティングとワイアレ ス通信研究会運営委員，電子情報通信学会英文論文誌 B 編集委員，同ネットワークシステム研究専門委員会委員． Vice Chair of IEEE ComSoc Asia Pacific Board Technical Affair Committee．ネットワーク・プロトコル，モバイルコ ンピューティング，ITS 等の研究に従事．著書『コンピュー タネットワーク』 （オーム社） ， 『ユビキタスコンピューティ ング』 （オーム社）等．電子情報通信学会，IEEE，ACM 各 会員． c 2013 Information Processing Society of Japan 620