Bloom Filterを用いたウェイクアップ型無線通信の消費電力評価

Bloom Filter を用いたウェイクアップ型無線通信の消費電力評価
Evaluation of Power Consumption for Wireless Wake-up Communication with Bloom Filter
瀧口 貴啓
Takahiro TAKIGUCHI
森戸 貴
Takashi MORITO
猿渡 俊介
Shunsuke SARUWATARI
南 正輝
Masateru MINAMI
森川 博之
Hiroyuki MORIKAWA
東京大学先端科学技術研究センター / Research Center for Advanced Science and Technology，The University of Tokyo
はじめに
無線通信では受信待機時にも多くの電力を消費しており，ウェイクアッ
プ型無線通信は受信待機時の消費電力を削減する手法の 1 つである．全ての
無線機器がウェイクアップ型になった環境を考えると，柔軟にウェイクアッ
プする機器を選択ができる仕組みが必要となる．本稿では Bloom Filter を
用いた ID マッチングを示し，その消費電力をシミュレーションによって
評価した．
ドウェア的な制限を満たしつつ，よりウェイクアップ型無線通信に適した
柔軟な ID マッチングが実現できる．
1
評価
最初に Bloom Filter のビット長による消費電力の差を評価した．ビット
長を長くするほど Bloom Filter が誤判定する確率は小さくできるが，ハー
ドウェアの増大で消費電力も大きくなるので，ビット長と消費電力の関係
を考慮しなければならない．そこで [1] の回路設計を用い，ビット長を変え
た時の受信待機電力の違いをシミュレーション評価した．シミュレータに
は QuartusII を使い，動作電圧 1.8 V，クロック周波数 500 kHz とした．
その結果，16, 32, 64 bit では消費電力 0.01 mW であり，128 bit で 0.02
mW となった．これからビット長を大きくしても受信待機電力は急激には
増えず，アナログ部の消費電力 0.31 mW に比べれば十分に小さいことが
分かる．従ってビット長は消費電力よりも，誤ウェイクアップ率や遅延な
どの評価で最適な値を決めることができる．
次に Bloom Filter を用いた ID マッチングで，どれほど消費電力を削
減できるかをシミュレーションによって評価した．ウェイクアップモジュー
ルにはビットレートは 40 kbps 受信待機時の消費電力 12.4 µW，ID 受信
時の消費電力 368.1 µW のものを想定した [1]．データ通信モジュールは
IEEE802.11g 規格の WLRG-RA-DP101 を想定し，受信時の消費電力は
907.5 mW である．シミュレーションにおいて Bloom Filter の誤判定確
率はビット長 128 bit，要素数 5 の場合を考え 0.00045 とした．またウェ
イクアップパケットを受信してウェイクアップしたデータ通信モジュール
は，自身に関係のない通信であるならば 10 ms 経つと再びスリープするも
のとする．
ウェイクアップパケットを送信する端末数と端末 1 台当たりの平均消費
電力の関係を図 2 に示す．縦軸は対数表示である．また個々の端末のウェイ
クアップパケット送信間隔は 10 秒とした．端末が 1 台の場合では Bloom
Filter の有無で消費電力は約 100 倍の差であるが，200 台の場合では 1000
倍以上の差となった．
図 3 にウェイクアップパケット送信間隔と端末 1 台当たりの平均消費電
力の関係を示す．縦軸は対数表示であり，ウェイクアップパケットを送信
する端末数は 100 とした．ウェイアップパケット送信間隔が 1 秒の場合は
消費電力は 1700 倍の差であるが，60 秒の場合では 700 倍の差となった．
図 2，3 から Bloom Filter を用いた場合の端末 1 台当たりの消費電力
は 0.013 ∼ 0.53 mW である．これに対しウェイクアップ型無線通信を使
用しない場合は常にデータ通信モジュールが受信待機状態にあるので，端
末 1 台当たりの消費電力は 907.5 mW となる．従って Bloom Filter を用
いたウェイクアップ型無線通信では，柔軟な ID マッチングを行いつつ受
信待機時の消費電力を数千∼数万分の 1 にできる．
4
ウェイクアップ型無線通信
無線通信では送受信の際だけでなく通信を待ち受ける受信待機時にも電
力を消費する．特に家庭用無線 LAN や携帯電話のフェムトセル基地局な
どの受信待機している時間が長いと想定される通信機器では，受信待機電
力が全体の消費電力の大部分を占めることになる．ウェイクアップ型無線
通信 [1][2] は受信待機電力を削減する手法の 1 つである．
多くの無線モジュールがウェイクアップ型になった環境を考えると，ウェ
イクアップパケットが至る所で送信されるようになる．全ての無線モジュー
ルが単一の信号でウェイクアップする仕組みであると，無線モジュールが
不必要なウェイクアップをする機会が多くなる．その結果，消費電力の大
きなデータ通信モジュールの受信待機時間が多くなり，ウェイクアップ型
の低消費電力の特徴が発揮されなくなる．従って，選択的にモジュールを
ウェイクアップさせることができる仕組みが必要である．また実際のアプ
リケーションを考えると，サービスやグループで指定してウェイクアップ
できるような柔軟な ID マッチングが求められる．
2
Bloom Filter を用いた無線ウェイクアッププロトコル
ウェイクアップ型無線通信に適する ID の条件を考える．まずウェイク
アップ型無線通信は低消費電力を目的とするものであり，ハードウェア的な
制限より多くのメモリ領域を確保することができない．また誤って必要の
ない時にウェイクアップするのは許容できるが，必要のある時には必ずウェ
イクアップしなければならない．以上の条件を考慮し，Bloom Filter[3] を
用いた ID マッチングを示す．Bloom Filter とは，B. H. Bloom が考案し
た空間効率の良い確率的データ構造であり，要素が集合に含まれているか
どうかをチェックすることができる．また，要素が集合に含まれていると誤
判定することはあるが，集合に含まれている要素は必ず正しく判定される．
無線モジュールは自身がウェイクアップする必要のある複数の ID から
Bloom Filter を作成する．ID は任意の機関がユニークなものを割り当て
て配布することを想定する．また ID は端末 (MAC アドレス)，ブロード
キャスト，無線 LAN 基地局や携帯型ゲームのすれちがい通信などといっ
たサービス，複数台同時制御などに使用するグループなどのウェイクアッ
プさせる対象ごとに割り当てる．送信機からウェイクアップパケットが送
られて来ると，そのウェイクアップ ID が自身の Bloom Filter に含まれて
いるか判断する．ウェイクアップ ID が含まれていると判断されればデー
タ通信モジュールをウェイクアップさせ，実際のデータ通信を開始する．
Bloom Filter の作成方法を図 1 に示す．まずウェイクアップ ID を複
数のハッシュにかける．次にそのハッシュ値の位置ビットをそれぞれ 1 に
したものをウェイクアップ ID 毎に作成する．最後に作成されたビット列
全てのビット毎の論理和をとったものが Bloom Filter となる．
例として 3 つの ID を持つ無線 LAN 基地局を考える．1 つ目の ID は無
線 LAN 基地局は端末固有の ID である MAC アドレスである．2 つ目は
“無線 LAN 基地局” というサービスに割り当てられた ID であり，3 つ目
は “ある部屋にある端末” というグループの ID である．ここでは Bloom
Filter の ID 長を 8 bit，ハッシュ関数の数を 2 とする．それぞれの ID を
ハッシュにかけた後には 00001001，01000100，00011000 になったとす
ると，そのビット毎の論理和をとった 01011101 が無線 LAN 基地局が保
持する Bloom Filter の値となる．
このように Bloom Filter を用いた ID マッチングを採用することでハー
3
Hashed ID 2
Hash 2
Wake-up ID 3
Hashed ID 3
[2] 瀧口ほか, “ウェイクアップ型無線モジュールにおける通信時の消費電
力に関する検討”, 信学ソ大, B-5-79, Sep. 2008.
[3] B. H. Bloom, “Space/time trade-offs in hash coding with allowable errors,” Comm. of the ACM, pp. 422-426, Jul. 1970.
1000
＋
Bloom Filter
10
1
0.1
Bloom Filterなし
Bloom Filterあり
0
50
100
150
0.01
図2
100
10
1
0.1
Bloom Filterなし
Bloom Filterあり
0
20
40
60
0.01
端末数
図 1 Bloom Filter の作成
200
消費電力 [mW]
Hash 1
Wake-up ID 2
参考文献
[1] 石田ほか, “低受信待機電力無線通信のための多段ウェイクアップ機構”,
信学技報, IN2007-218, Mar. 2008.
100
Hashed ID 1
消費電力 [mW]
Wake-up ID 1
おわりに
本稿では無線機器の受信待機電力を削減する手法であるウェイクアップ
型無線通信に適する ID マッチングとして，Bloom Filter を適用した仕組
みを示した．また Bloom Filter を用いたウェイクアップ型無線通信で受
信待機時の消費電力を数千∼数万分の 1 にできる可能性をシミュレーショ
ン評価によって示した．
5
端末数と消費電力
ウェイクアップ間隔 [ 秒 ]
図 3 ウェイクアップ間隔と消費電力