無線センサネットワークにおける送信スケジューリングに関する研究
2007MI035 長谷川 祐

2007MI194 大津 恭敬
指導教員

1 はじめに
近年，無線通信技術の発達によりセンサネットワークの普及が進んでいる [1]．センサネットワークの研究は1980 年代にさかのぼり，軍事研究を経て産業界でも徐々に利用されるようになってきている．現在では森の管理システムや，家庭のセキュリティシステムなど様々な場で活用されており，今後もユビキタスシステムの中核として私たちの生活にますます重要な役割を果たすようになる．
センサネットワークとは，小型のセンサや無線装置，情報装置，電力装置を内蔵した多数のセンサノードから構成されるネットワークである．センサは，物理量や化学量を認識・計測・感知し，電気量に変換して出力する．
熱，温度，位置など一般感知センサから，人の体温，脈拍，心拍数などを測る五感センサ，特定の薬品や科学物質を検知するセンサなどその用途は多種多様である．そのようなセンサを搭載したセンサノードは，自身で収集した情報と，他のセンサノードから受信した情報を処理し，転送する機能を持っている．設置されたセンサノードは自律的にネットワークを構築し，各々がセンシングした情報や他のノードから受信した情報を処理して，シンクノードと呼ばれるデータ収集地点など特別なセンサノードへ送信する仕組となっている．
センサネットワークでは，センサノードを分布させ，測定したデータをノード間で無線通信することにより，有線ネットワークが不必要となる．これにより，センサネットワークの野外での使用が容易に行えるようになった．また，ノードを自由に配置できることから，一度に多くのデータを集めることが可能である．しかし，センサノードはデータ観測のために広域に分布されている場合が多く，内蔵されている電源をすべて取り換えるのには大変なコストがかかるといえる．そこで，センサノードの無駄な消費電力を極力抑えて，センサネットワークを長時間動作させるための手法として，階層数の多いクラスタツリー型のネットワーク構成を用いる．階層数が多いと，データ圧縮の回数が増え，それぞれのノードがデータ送信に必要とする消費電力は減る．データの送信に消費する電力量が最も大きいとすると，階層数の多いツリーであれば，消費電力の総和を抑えることができるはずである．また，データの送信に必要な電力は，送信距離の 2 乗から 4 乗に比例することから [2]，センサノード間の距離の総和を最小にする必要がある．そのために，ツリー型のネットワークを構成するときには，最2007MI228 鈴木 貴士

石崎 文雄
小全域木を求めるアルゴリズムを持つ，プリム法を用いるものとする．
現実でのセンサネットワークは大規模なものが多く存在する．大規模なネットワークのスケジューリング問題を解くために，全てのノード間の関係や組合せを求めて最適解を得ようとすることは非常に困難である．そこで時間をタイムスロットと呼ばれる単位で分割して共有する多重方式である TDMA によるスケジューリング問題を考える．渡辺他 [3] は TDMA によってスケジューリングが行われるツリー型構造のセンサネットワークについて，スケジューリング問題を定式化し，定式化した問題をホップフィールドニューラルネットワークを利用して解いている．ホップフィールドニューラルネットワー
クによる解法ではネットワークを分割してスケジューリングを行い，それらを結合し，結果を求めている．
本研究では，プリム法によって作成したツリー型構造のセンサネットワークについて考える．そのセンサネッ
トワークにおける TDMA スケジューリング問題を研究する．グリーディ法での計算結果とホップフィールドニューラルネットワークでの計算結果とを比較し，実用的な時間でスケジューリング問題の比較的良い解を求める．
大津恭敬は主に研究背景を，鈴木貴士は主にモデルから定式化までを，長谷川祐は主にスケジューリング以降を担当した．

2 モデリング
センサネットワークのモデル化のために，よく使われるグラフ理論モデルはユニットグラフモデルである．ユ
ニットグラフモデルにおいては，ノード A とノード B のユークリッド距離が任意の送信半径以下であればノードA とノード B は隣接し枝で結ばれる．ノード A とノード B が隣接しているとき 2 つのノードを 1 ホップの関係にあると言う．またノード A とノード B が 1 ホップの関係になくとも，2 つのノードに対して 1 ホップの関係にある共通のノードが存在している場合，ノード A とノード B は 2 ホップの関係にあると言う．
本研究で考えるモデルでは，各センサノードはデータをパケットの形で送信するとし，パケットを送信するのに 1 スロットを使用するとする．多数のノードが 1 つのチャネルを共有して使うので，同じスロットで複数のノードが送信を行うと干渉が発生する可能性がある．したがって，干渉が発生しないスケジューリングを行うことが必要である．
本研究で考えるモデルでは，干渉が発生しないことを前提においたスケジューリングを行うものとし，干渉が発生しないための条件を以下のように定めるものとす
る．
・ノード A をリーフとし，親ノードであるノード B に送信するものとする．
・リーフノード A の親ノード B と 1 ホップ関係にない，ノード A を除くリーフノードとは干渉が発生しない．
本研究ではプリム法を用いてネットワークの最小全域木を求めるものとする．プリム法では複数のノードから任意のノードを選択する．任意のノードと，そのノードに接続されているノードのなかで最も辺の重みの小さいノードを選択し枝でつなぐ．この行程を繰り返して行い，全てのノードが枝で接続されたら終了とし，最小全域木が求められたこととする．本研究ではノード間の距
離を辺の重みとして実験を行うものとする．以下の図はノード数 8 のネットワークにおいて任意のノード（図では番号 0）を選択し，のプリム法による最小全域木を求める行程である．図 1 では番号 0 のノードを頂点としている. 番号 0 のノードから繋がっているノードは番号2 のノードのみなので，番号 0 と番号 2 のノードが接続される (図 2)．次に現在接続されている，番号 0，番号2 のノードと繋がるノードのなかで最も距離が近いノードを検索する．最も近いノードは番号 2 のノードから繋がる，番号 4 のノードなので，番号 2 のノードと番号 4のノードが接続される (図 3)．同様に，現在接続されているノードの中で，最も距離の近いノードを接続する行
程を繰り返し行い (図 4，図 5，図 6，図 7)，全てのノードが接続されたら，最小全域木が求められたものとする(図 8)．

図5

プリム法（5）

図6

プリム法（6）

図7

プリム法（7）

図8

プリム法（8）

3 定式化
本研究で考えるセンサネットワークは，ツリー型構造をしているものと考える．しかしスケジューリングを行う際に以下のような条件を定めるものとする．
・各センサノードはデータをパケットの形で送信し，パケット送信には 1 スロットを使用するものとする．
・各センサノードは自分の全ての子ノードからパケットを受信した後，自分がセンシングしたデータと子ノードから得たデータを集約して自分の親ノードに 1 パケットで転送する．
・親ノードは自分の全ての子ノードからパケットを受信するまで送信することが出来ない．
センサネットワークのスケジューリング問題を定式化するために，変数の定義をする．n をセンサノードの数，m をフレーム内のタイムスロット数とするとノード i, j はともに 0 から n − 1 個，タイムスロット t は 0 か
ら m − 1 で表し，これにより sti , fij を定義する．

{
図1

プリム法（1）

図2

プリム法（2）

1(タイムスロット t において, ノード i が送信する)

sti =0(その他){1(ノード i, j が 1 あるいは 2 ホップ関係にある)

fij =0(その他)
このとき以下の制約条件を受けるものとする．

図3

プリム法（3）

図4

プリム法（4）

・干渉が発生しない
・すべてのノードからのデータをシンクノードへ送信する
これらの制約を満たす制約条件を考える．
制約条件 1m−1∑

Sti = 1(i = 0, 1, ...n − 1)

t=0

すべてのノードがフレーム内に必ず 1 回データを送信することを表す．

る場合を選択し送信するものとする．リーフノードを送信する毎に，送信したリーフノードを削除し，Pi を更新する．全てのセンサノードがシンクノードに集約するまでこれらの行程を繰り返し，シンクノードを除く全てのセンサノードが送信されたとき，スケジューリングが完了したと考える．グリーディ法でのスケジューリング問題を解くためには，いくつか条件を定めないとならない．まず，検索したリーフ同士が 2 ホップの関係であった場合，ノード番号の若い方を優先してパケット送信を行う．シンクノードはセンサネットワークの中心にあるノードに設定し，データを集約するものとする．以上の条件を加えてグリーディ法を用いれば，スケジューリングが正しく行われるはずである．

5 実行結果
制約条件 2n−1
∑ n−1
∑ n−1
∑

本研究では，ノード数 100 のセンサネットワークを考える前に，小規模のネットワークとして，図 8 を例にノード数 8 のセンサネットワークを考え，グリーディ法によってスケジューリングを求めた．

fij sti stj = 0

t=0 i=0 j=0

ノード i，j が 1 ホップまたは 2 ホップの関係にあるとき，同じタイムスロットでパケットを送信できないことを表す．

4 スケジューリング
本研究では，ホップフィールドニューラルネットワー
クを使って，各ノードの送信スケジュールを求める方法との処理速度の違いを比較するために，グリーディ法を用いてスケジューリング問題を解くことを考える．グ
リーディ法とは，問題をいくつかの部分問題に分割し，それぞれの段階で最適な解を選択して最後に統括することで近似解を得る手法である．本研究で使用するグリーディ法では，リーフについて考える．
n をセンサノードの数 i は 0 から始まり，上限は各数式によって異なる．Pi を任意の i の時の子ノードの有無の集合とする．
n−1
∑
i=0

{0(リーフノードである)(1)

Pi =0 以外 (リーフノードではない)(1) はリーフノードの条件式であり，合計が 0 のとき子ノードが無いということなので，リーフノードであるとする．(1) の条件式を全てのノードに対して当てはめてリーフノードを検索する．次に (1) の数式で検索されたリーフノードの中から，任意のリーフノードと同時に送信できる他のリーフノードを検索する．任意のリーフノードと，他のリーフノードが 2 ホップ関係にない場
合それらのノードは干渉しないとして同時に送信できるものとする．全てのリーフノードに対し，同時に送信できるノードを検索し，最もたくさんのノードが送信でき

表1

グリーディ法によるスケジューリング結果@@@
01234567012110001010001100000100000

表 1 はノードがどのタイムスロットでどのノードがデータを送信しているかを表している．縦軸がセンサノードを，横軸がタイムスロットを表している．表 1 のグリーディ法による解法では，タイムスロット 3 かかってシンクノードにデータを集約した．よって，同じタイムスロットで複数のノードが送信することによって，スケジューリング結果を短くすることに成功した．シンクノードがノード番号 6 なので，最終的にグラフの中心に位置するシンクノードに全てのデータが集約されることが確認できた．
以下に 8 ノードから構成されるセンサネットワークのスケジューリングの様子を図で示す．以下の図よりノードがタイムスロット毎に中心のシンクノードにデータが集約される様子が確認できた．

大規模なネットワークとしてノード数が縦軸 100，横軸 100 の範囲内に 100 個のノードをランダムに配置し，グリーディ法によるスケジューリングする行程を 100 回繰り返したところ，タイムスロットの平均が 26.70，スケジューリングの平均時間は 0.93 秒という結果になった．これは同じ条件下でのホップフィールドニューラルネットワークのスケジューリングのスケジューリングの平均時間 17.94 秒に比べ大幅に時間を短縮出来たことが確認できた．

6 まとめ

図9

ツリー型構造 (1)

図 10 ツリー型構造 (2)本研究では，ノード数 100 のセンサネットワークをプリム法を用いて，ツリー型のネットワークを作成した．グリーディ法を用いて干渉が発生しないノード同士を，同じタイムスロットで送信する方法を考え，ホップフィールドニューラルネットワークによる方法と比較した．グリーディ法を用いた結果，ホップフィールドニューラルネットワークを用いた方法に比べて，実行結果の出力時間を短縮することができた．理由としてホップフィールドニューラルネットワークによるスケジューリングではネットワークを分割・結合する行程があるた
め，時間が余分にかかっているものと考えられる．このことよりホップフィールドニューラルネットワークに比べ，より効率的なスケジューリングが出来たといえる．
また，提案したプログラムではタイムスロット毎に treeファイルを作成し，タイムスロット毎の図が確認できるようにした．

7 今後の課題
ノード数が 100 の場合は約 1 秒内でスケジューリングを終えることができたので，今後はノード数が 1000 を越えるような大規模なネットワークでも 60 秒以内で計算可能なスケジューリングを実現する必要がある．またネットワーク内でノードが故障した場合を想定した研究も今後必要になってくる．
図 11 ツリー型構造 (3)図 12 ツリー型構造 (4)参考文献[1] 阪田史郎編著，“ユビキタス技術センサネットワー
ク，”1 章，pp.2-18，2006．
[2] T. Furuta, M. Sasaki, F. Ishizaki, T. Ukai, H.
Miyazawa, W. Koo, A. Suzuki, K. Inakawa, “Newformulation for scheduling problem in multi-hop
wireless sensor networks,” Proceedings of the 6thInternational Wireless Communications and Mobile Computing Conference (IWCMC ’10), pp.73–78, 2010.
[3] 渡辺博功，吉田亮介，“センサネットワークのスケジューリングに関する研究，” 南山大学数理情報学部情報通信学科 2009 年度卒業論文.