観測データの相関を利用した符号化テーブルの削減手法

情報処理学会研究報告
Vol.2012-DPS-151 No.24
Vol.2012-MBL-62 No.24
2012/5/22
IPSJ SIG Technical Report
観測データの相関を利用した符号化テーブルの削減手法
伊藤 裕作1,a)
小林 健太郎2
岡田 啓2
片山 正昭2
概要：センサネットワークにおいてノードが通信するデータ量を削減することを考える．1 つの方法とし
てデータを情報源符号化して圧縮する方法がある．効率の良い情報源符号化の方法としてハフマン符号が
ある．しかし，ハフマン符号を用いるにはノードとベースステーション (BS) の双方に符号化テーブルが必
要であり，テーブルの送受信に必要なデータ量も考慮する必要がある．本稿では，全てのノードで共通の
符号化テーブルを作成する手法を提案し，ノード個別の符号化テーブルを作成する手法と総テーブルサイ
ズと圧縮率により比較評価を行う．提案手法は総テーブルサイズを大幅に削減しつつ高い圧縮率を保つこ
とが可能であることを示す．
キーワード：センサネットワーク，ハフマン符号，共通テーブル，個別テーブル
Reduction of Code Table Using Correlation of Observed Data
Y USAKU ITO1,a)
K ENTARO KOBAYASHI2
H IRAKU OKADA2
M ASAAKI KATAYAMA2
Abstract: Our goal is the reduction of the amount of transmitted data in sensor networks. One method to reduce the
transmitted data is source coding. One of efficient source coding methods is Huffman coding. When we employ Huffman coding in sensor network, each sensor node and a base station (BS) need the same code table. So, we need to
consider the amount of code table size transmitted between each sensor node and the BS. In this paper, we propose
a method which makes a common code table at the BS for all nodes. By comparing a method which makes individual code tables for all nodes, we show that the proposed method achieves very small code table and maintains high
compression rate.
Keywords: sensor network, Huffman coding, common table, individual tables
1. はじめに
リティなど多岐にわたる．
一般的にセンサネットワークではセンサノードは高密度
センサネットワークとはセンサノードで観測した情報を
で多数配置され，定期的に観測したデータを BS に送信す
無線通信によって BS(ベースステーション) へ送ることで広
るという特徴がある．このことから収集された情報は時間
範囲の情報を取得する技術である. センサネットワークで
的，空間的に似たような分布を持つ．時間的に似た分布を
はセンサ機能と無線通信機能を持つ多数のセンサノードと
持つというのは物理的な距離が近いノード同士のデータが
センサノードから伝送されたデータを集約する少数の BS
似たような値を持つこと，空間的に似た分布を持つという
で構成される．センサノードは温度や湿度，照度などの情
のはあるノードが T 回目にセンシングして得たデータと
報を取得する小型端末であり，電池駆動によって配線を必
T + 1 回目にセンシングして得たデータが似たような値を持
要としない自由度の高い配置が可能になる. そのため，セ
つということである．このことから，適切な符号化を行う
ンサネットワークの用途は環境測定，省エネ管理，セキュ
ことでセンサノードが送受信するデータ量を削減すること
が可能であると期待できる．データ量の削減手法としては
1
2
a)
名古屋大学大学院 工学研究科 電子情報システム専攻
名古屋大学エコトピア科学研究所
[email protected]
ⓒ2012 Information Processing Society of Japan
情報源符号化 [1, 2] を用いる方法，データ集約 [3, 4] を用い
る方法などがある．前者はセンサ個々のデータを圧縮し，
1
情報処理学会研究報告
Vol.2012-DPS-151 No.24
Vol.2012-MBL-62 No.24
2012/5/22
IPSJ SIG Technical Report
Node 1
Node 1
22㷄
22㷄
Node 2
࡮
࡮࡮
BS
࡮
࡮࡮
Node 2
BS
23㷄
Data2
22㷄 32/100
23㷄 30/100
䊶䊶䊶
20㷄 6/100
19㷄 3/100
26㷄 2/100
(a) ノード毎のデータの集計
Node 1
図1
ノードの配置
Node 2
BS
࡮
࡮࡮
後者はセンサのデータ 1 つにまとめることでデータ量を削
DataN
22㷄 30/100
23㷄 23/100
䊶䊶䊶
19㷄 5/100
26㷄 3/100
20㷄 2/100
Node N
Table1
Node N
䊶䊶䊶
Data1
23㷄 35/100
22㷄 23/100
䊶䊶䊶
19㷄 7/100
18㷄 3/100
25㷄 2/100
Node N
23㷄
22㷄
䊶䊶䊶
19㷄
18㷄
25㷄
11
100
01001
01000
01100
Table2
䊶䊶䊶
22㷄 01
23㷄 00
䊶䊶䊶
20㷄 10011
19㷄 10010
26㷄 10000
TableN
22㷄 10
23㷄 111
䊶䊶䊶
19㷄 00101
26㷄 00100
20㷄 00110
(b) 符号化テーブルの作成
減する．本研究では前者を扱う．符号化の方法として，文
献 [5] でハフマン符号を用いている．ハフマン符号はアル
ゴリズムが比較的単純かつ整数の符号長においては最適な
符号が作成できる. 文献 [5] では実測した温度データを用い
減できるデータ量を評価している．しかし文献 [5] では符
Node 2
BS
࡮
࡮࡮
てセンサネットワークにハフマン符号を適用した場合に削
Table1
Node 1
う特徴を持つ．センサネットワークにおいてハフマン符号
11
100
01001
01000
01100
Table2
䊶䊶䊶
22㷄 01
23㷄 00
䊶䊶䊶
20㷄 10011
19㷄 10010
26㷄 10000
TableN
22㷄 10
23㷄 111
䊶䊶䊶
19㷄 00101
26㷄 00100
20㷄 00110
Node N
号化テーブルのサイズに関しては考慮されていない．ハフ
マン符号では予めデータの出現頻度を知る必要があるとい
23㷄
22㷄
䊶䊶䊶
19㷄
18㷄
25㷄
(c) 符号化テーブルの配信
図 2 個別のテーブルを用いた符号化
を適用するには BS，センサノードの両方にデータと符号
を対応付けしたテーブルが必要となる．BS とセンサノー
をそのまま BS に送信する．次に，図 2(a) のように BS は
ドの間で符号化テーブルのやりとりも必要であるため，符
ノード別にデータの出現する回数を集計する．例えば，図
号化テーブルも削減が必要である．
2(a) では Node1 において 27 ℃のデータが 100 回中 35 回
本稿では符号化テーブルについて評価を行う．その作成
発生している．T o 秒後，図 2(b) のように BS は符号化テー
手法において，センサノード共通の符号化テーブルを作成
ブルをノード別に作成する．作成したテーブルは図 2(c) の
することを提案する．符号化テーブルを共通にすることで
ように各ノードへブロードキャストされる．符号化テーブ
センサノード毎に個別のテーブルを作成する方法と比較し
ルを受信したノードはその後受信した符号化テーブルを用
てセンサノードの数の増加に対して総テーブルサイズの
いて観測したデータを符号化し BS に送信する．この手法
増加を抑制できることを示す．同時に削減できるデータ量
はノード毎に最適な符号化テーブルが作成できるが，ノー
(圧縮率) から提案手法においても効率良くデータを圧縮で
ドの数が増加すると総テーブルサイズも同時に増加してし
きることを示す．
まう．故に，BS のメモリリソースや符号化テーブルのブ
2. システムモデル
ロードキャストに必要なネットワークリソースを圧迫する
と考えられる．
本稿では図 1 のように 1 個の BS に対して N 個のノー
ドが配置されているシステムを考える．符号化テーブルは
2.2 共通のテーブルを用いたハフマン符号化
T o 秒間観測を行って得られたデータから作成する．全て
図 3 に共通の符号化テーブルを作成する手法について示
のノードは一定の間隔 T 秒毎に符号化テーブルに基づいて
す．前節と同様にまず，各ノードは観測を行いデータを取
データを符号化し BS に送信するものとする．各ノードが
得しデータをそのまま BS に送信する．次に，図 3(a) のよ
観測したデータは BS にて必ず受信に成功するものとする．
うに BS は全てのデータをまとめて集計する．例えば，図
符号化テーブルは BS にて作成を行い，各ノードに配信す
3(a) では全てのノードにおいて 23 ℃のデータが 100 回中
るものとする．BS が配信する符号化テーブルは各ノード
35 回発生している．T o 秒後，図 3(b) のように BS はノー
にて必ず受信に成功するものとする．ノード間でデータの
ド共通の符号化テーブルを作成する．作成したテーブルは
やりとりは行わない．
図 3(c) のように各ノードへブロードキャストされる．符号
化テーブルを受信したノードはその後受信した符号化テー
2.1 個別のテーブルを用いたハフマン符号化
ブルを用いて観測したデータを符号化し BS に送信する．
図 2 に個別の符号化テーブルを作成する手法について
この手法はノード毎にみた場合，最適な符号化テーブルと
示す．まず，各ノードは観測を行いデータを取得しデータ
ならないので個別の符号化テーブルを作成する手法と比較
ⓒ2012 Information Processing Society of Japan
2
情報処理学会研究報告
Vol.2012-DPS-151 No.24
Vol.2012-MBL-62 No.24
2012/5/22
IPSJ SIG Technical Report
N
Data
22㷄
Node 1
23㷄 35/100
22㷄 23/100
䊶䊶䊶
19㷄 7/100
18㷄 3/100
25㷄 2/100
22㷄
Node 2
࡮
࡮࡮
BS
23㷄
Node6
Node12
Node5
Node11
Node4
Node10
Node14
Node N
(a) 全ノードのデータの集計
Node13
Table
Node 1
Node 2
23㷄
22㷄
䊶䊶䊶
19㷄
18㷄
25㷄
࡮
࡮࡮
BS
11
100
Node9
Node3
01001
01000
01100
Node8
Node N
Node2
(b) 符号化テーブルの作成
BS
Table
Node 1
23㷄
22㷄
䊶䊶䊶
19㷄
18㷄
25㷄
Table
Node 2
࡮
࡮࡮
BS
Table
Node7
Node1
Table
11
100
図 4 ノードの配置
01001
01000
01100
∑

N


 i=1 pi × L
S =


 pa × L
Node N
(c) 符号化テーブルの配信
図 3 共通のテーブルを用いた符号化
Individual T ables
(1)
Common T able
ここで， pi は i 番目のノードの総データパターンの数，
pa は全ノードでのデータパターンの数を示す．図 5 にノー
表1
ド数 N と総テーブルサイズ S の関係を示す．横軸はノー
実験諸元
測定場所
名古屋大学 IB 電子情報館 9F
ノード数 N
14
データ収集期間 T a
2012/2/16～2012/2/22
データ送信間隔 T
5分
観測対象
温度
データ長 L
10 ビット
して圧縮率が低下することが考えられる．しかしノードの
数が増加しても総テーブルサイズを小さく保つことができ
ると期待される．
3. 性能評価
3.1 データの実測
ノードには Crossbow 社の Iris mote XM2110J にセンサ基
板 MTS400 を搭載したものを用いた [6]．ノードの配置を
図 4，実験諸元を表 1 に示す．収集した温度データを用い
て 3.3 節及び 3.4 節で総テーブルサイズ及びデータの圧縮
率を計算機シミュレーションにて評価する．
3.2 総テーブルサイズの比較
総テーブルサイズ S を次式で定義する．
ⓒ2012 Information Processing Society of Japan
ド数 N ，縦軸は総テーブルサイズ S である．
図 5 より，個別に符号化テーブルを作成した場合 (図中
の Individual Tables) はノード数の増加に対して総テーブル
サイズが比例的に増加する．一方で共通の符号化テーブル
を作成した場合 (図中の Common Table) はノード数が増加
しても総テーブルサイズはほとんど増加しない．例えば，
N = 14 のとき，個別のテーブルを作成した場合と比較して
91%テーブルサイズを削減できる．このことから提案手法
においては総テーブルサイズを大幅に削減できるので BS
のメモリリソース及びネットワークリソースを節約できる
ことがわかる．
3.3 データの圧縮率の比較
データの圧縮率 R は次式で定義される．
∑ TT0
R=
L
j=1 l j
× TT0
(2)
ここで，l j は j 番目の符号化後のデータ長を示す．図 6
にノード数 N と圧縮率 R の関係を示す．横軸はノード数
N ，縦軸は圧縮率 R である．
図 6 より，個別に符号化テーブルを作成した場合はノー
3
情報処理学会研究報告
Vol.2012-DPS-151 No.24
Vol.2012-MBL-62 No.24
2012/5/22
IPSJ SIG Technical Report
1800
参考文献
1600
[1]
Total Table Size[bit]
1400
1200
[2]
Individual Tables
1000
800
600
[3]
Common Table(Proposal)
400
200
[4]
0
2
4
図5
6
8
Nodes
10
12
14
総テーブルサイズの比較
[5]
[6]
25
Compression Ratio[%]
30
Z. Xiong, A.D. Liveris, and S. Cheng, “Distributed source coding for sensor networks,” IEEE Signal Processing Magazine,
vol.21, no.5, pp.80–94, Sept. 2004.
C. Tharini and P.V. Ranjan, “Energy efficient low power architecture for distributed source coding in wireless sensor networks,” 2010 IEEE International Conference on Computational Intelligence and Computing Research (ICCIC), pp.1–4,
Dec. 2010.
H. Jiang, S. Jin, and C. Wang, “Prediction or not? an energyefficient framework for clustering-based data collection in
wireless sensor networks,” IEEE Transactions on Parallel and
Distributed Systems, vol.22, no.6, pp.1064–1071, June 2011.
Y. Ma, Y. Guo, X. Tian, and M. Ghanem, “Distributed
clustering-based aggregation algorithm for spatial correlated
sensor networks,” IEEE Sensors Journal, vol.11, no.3, pp.641–
648, March 2011.
D.I. Sacaleanu, R. Stoian, and D.M. Ofrim, “An adaptive huffman algorithm for data compression in wireless sensor networks,” 2011 10th International Symposium on Signals, Circuits and Systems (ISSCS), pp.1–4, June 2011.
“Moteview マ ニ ュ ア ル,” http://www.xbow.jp/mv_
manual_aj.pdf．
Individual Tables
35
40
Common Table(Proposal)
45
50
2
4
6
8
Nodes
10
12
14
図 6 データの圧縮率の比較
ド数の増加に対して圧縮率はほぼ一定である．一方で共通
の符号化テーブルを作成した場合はノード数の増加ととも
に圧縮率が低下する．例えば N = 14 のとき，個別の符号化
テーブルを作成した場合と比較して 5%程度圧縮率が低下
するが依然高い圧縮率を保っている．このことから提案手
法においても効率良くデータが圧縮できることがわかる．
4. まとめ
本稿ではセンサネットワークにおいてハフマン符号を用
いるにあたって共通の符号化テーブルを作成することを提
案し, 総テーブルサイズ及び圧縮率の 2 点で評価を行った.
提案手法は総テーブルサイズを大幅に削減しつつ高い圧縮
率を保つことが可能であることを示した．
謝辞 本稿をまとめるにあたり熱心にご指導くださった
名古屋大学教養教育院教授山里敬也博士に感謝する．
ⓒ2012 Information Processing Society of Japan
4