センサネットワークのスケジューリングに関する研究
2006MI196 渡辺 博功
指導教員

1 はじめに
近年，無線技術の発達により，センサネットワーク技術が急速に発達している [1]．センサネットワークは元々，戦闘地域の監視など軍事目的や物理的状況を採取することを可能とする無線ネットワークとして開発され，現在では交通状況や環境調査，健康管理などのモニタを目的として用いられている．今後はユビキタスネッ
トワークの実現に向けた基盤技術のひとつとして注目されている．
センサネットワークは，小型のセンサ，無線装置，情報処理装置を内蔵した多数のセンサノードから構成される．センサノードは他のセンサノードから送られた情報を受信し，その情報を処理し，転送する機能も持っている．各センサノードは，設置されると自動的に周囲の状況を認識し，認識した情報をもとに自律的にネットワークを構築し，センシングした情報あるいは他のセンサノードから受信した情報を処理して必要なところ (例えばシンクノードと呼ばれるデータ収集地点や基地局) へ送信する．
センサネットワークにおいては，制約のある資源，例
えばセンサノードの電力資源，計算資源，通信資源などをどのように効率的に利用するかが課題となる．センサ
ノードは，環境の観測などの応用においては通常地理的に散らばって配置されており，内蔵されている電源を新しいものと入れ換えることが難しいため，センサノードの無駄な電力消費を極力抑えたい．またデータ送信時だけでなく，受信時や情報を圧縮する時にも電力を消費してしまうので，これも極力抑えたい．電力消費を抑える
観点からは，クラスタツリー型のネットワーク構成が優れていることが知られている [2]．階層数が多いとデー
タ圧縮の回数が増え，消費電力は増えるがデータ送信に要する消費電力は減る．データ送信に必要な電力量が最も大きいとすると，階層数の多いツリーのほうが消費電力総和を抑える可能性が高いからである．環境モニタリ
ングでのデータの収集など様々な応用上も，ツリー型構造のネットワーク構成は適していると考えられる．デー
タを送信する際には送信距離の 2 乗から 4 乗に比例する大きな電力を要するため，センサノード間の距離の総和を最小にする必要がある．最短経路を求める方法としてプリム法がある．プリム法は最小全域木を解くグラフ理論におけるアルゴリズムである．
ネットワークの構成と同様にアクセス制御も制約のある資源を効率的に利用するためには，重要な要素である．木利他 [3] はマルチホップ通信を行う大規模センサ
ネットワークにおけるアクセス制御について研究し，すべてのセンサノードの位置情報に基づいて TDMA によ2006MI209 吉田 亮介

石崎 文雄
る理想的なスケジューリングを行う場合と比較して，位置情報を必要としない CSMA/CA を適用した場合は，データの収集に要する時間が 3．7 倍となり，消費電力は 12% 増となることを報告している．TDMA は時間をスロットと呼ばれる単位で分割して共有する多重化方式であり，CSMA/CA とは，無線 LAN で採用されている媒体アクセス制御方式で，同一のチャネルに複数のユーザーがアクセスする際の競合を回避する方式である．
本研究で行うネットワークのスケジューリング問題とは NP 困難な組合せ最適化問題として定式化され，問題の規模が大きくなると，解の総数が指数関数的に増加する．そのため，ネットワークにおけるスケジューリング問題を解くために全てのノード間の関係，組合せを求めて最適解を得ようとすると，計算時間が長くなり実質的に不可能となる．
本研究では，TDMA によってスケジューリングが行われるツリー型構造をしたセンサネットワークをプリム法で考え，そのセンサネットワークにおけるスケジューリング問題を定式化する．定式化された問題をホップフィールドニューラルネットワークを利用して解くことを試みる．吉田亮介は主にスケジューリングの定式化までを，渡辺博功は主にスケジューリングの制約式以降を担当した．

2 モデル
センサネットワークのモデル化のために，よく使われる基本的なグラフ理論モデルは，ユニットグラフモデルである [4]．ユニットグラフモデルにおいては，ノード Aとノード B のユークリッド距離が送信半径 R 以下であればノード A とノード B は隣接し枝で結ばれる．ノード A とノード B が隣接している時，ノード A とノード B は 1 ホップの関係にあると言う．またノード A とノード B が，1 ホップの関係ではないが，1 ホップの関係にある共通のノードを持つ場合，ノード A とノード Bは 2 ホップの関係にあると言う．
本研究で考えるセンサネットワークは，アクセス制御方式として TDMA を使用する．本研究で考えるモデル
では，各センサノードはデータをパケットの形で送信し，パケットを送信するのに 1 スロットを使用することとする．多数のノードが 1 つのチャネルを共有して使うので，同じスロットで複数のノードが送信を行うと干渉が発生する可能性がある．したがって，干渉が発生しないスケジューリングを行うことが必要である．本研究で考えているモデルでは，干渉が発生した時は，通信が正しく行われないものとする．また干渉以外の原因で通信が正しく行われないことはないものとする．干渉が発生しないための必要十分条件は以下のように記述される．

• ノード A からノード B に送信しているものとする．ノード B と 1 ホップの関係にあるノード Aを除くすべてのノードが送信していない，かつその時に限り，ノード A からノード B への送信に対する干渉が発生しない．
例えば，図 7 において，ノード 2 と 3 が同時にノード 1に送信するとデータが干渉してしまい破損してしまう．
本研究ではプリム法を用いて最小全域木を求める．プリム法は任意のノードを 1 つ選択する (図 1)．任意のノードと接続されているノードの中で最も辺の重みが少ないノードを選択する (図 2)．選択されたノードと接続されているノードの中で最も辺の重みが少ないノードを選択していくことで，最小全域木を求める (図 3，図 4，
図 5)．全てのノードが接続されたら終了する (図 6) ことにより最小全域木を求める．本研究では，辺の重みをノード間の距離とし，ノード数を 100 としてプリム法を使用する．

ンシングした情報と子ノードから得た情報を集約して自分の親ノードに集約した情報を 1 パケットで転送する．
したがって，親ノードは自分のすべての子ノードからパケットを受信するまでは，自分の親ノードにパケットを送信できない．この過程を繰り返し，ツリーの子から親にデータが送信され最終的にツリーの最上流の根にあるシンクノードにすべてのノードからのデータが集まる．
例として，図 7 は 7 つのセンサノードから構成される．ユニットグラフ上に構築されたツリー型構造のセンサネットワークを図 8 に示す．ツリー型構造のセンサネットワークを表わすグラフは，そのユニットグラフの部分グラフとして構成されることに注意する．

図 7 センサノードから構成されるグラフ

図 8 ツリー型構造のセンサネ
ットワーク

3 スケジューリングの定式化
図1

プリム法の例 1

図 2 プリム法の例 2

センサネットワークのスケジューリング問題を定式化するために，変数の定義から始める．N をセンサネッ
トワークを構成するセンサノードの数とし，M をフレーム内のタイムスロット数とする．さらに，ノードi = 0, 1, 2, . . . , N − 1，j = 0, 1, 2, . . . , N − 1，タイムスロット t = 0, 1, . . . , M − 1 に関して sti ，fij ，hij を以下のように定義する．

{sti =
図3

プリム法の例 3

図 4 プリム法の例 41 (タイムスロット t において，ノード i が送信する)
0 (otherwise){
fij =1 (ノード i, j が 1 あるいは2 ホップ関係にある)
0 (otherwise)

{
hij =

図5

プリム法の例 5

図 6 プリム法の例 6

本研究では，ツリー型構造をしたセンサネットワークを考える．このツリー型構造のセンサネットワークにおいては，各センサノードはセンシングしたデータを自分の親ノードに１パケットで転送する．親ノードは自分のすべての子ノードからパケットを受信した後，自分がセ1 (ノード j がノード i の子ノードである)
0 (otherwise)

このとき sti (t = 0, . . . , M − 1; i = 0, . . . , N − 1) は各センサノードの送信スケジュールを表わしていることに注意する．
送 信 ス ケ ジ ュ ー ル sti (t = 0, . . . , M − 1; i =0, . . . , N − 1) は自由に決められるわけではなく，• 干渉が発生しない．
• 親ノードは自分のすべての子ノードからパケットを受信するまでは，自分の親ノードにパケットを送信できない．

• すべてのノードからのデータをシンクノードに送信しないといけない．という 3 つの制約を受ける．そのため以下の 3 つの制約条件を考える．

• 制約条件 IM−1∑

sti = 1

(j = 0, 1, ..., N − 1)

(1)

t=0

この制約条件は，すべてのノードがフレーム内に必ず 1 回データを送信することを表わしている．
• 制約条件 II
M−1 N−1 N−1∑∑∑

fij sti stj = 0(2)

t=0 i=0 j=0

たがって，wti,uj = 1 となるのは次のいずれかの場合に限られる．

• ノード i = 0, . . . , N − 1 において任意の i およびタイムスロット t, u = 0, . . . , M − 1 において任意の t, u に関して wti,ui = 1• fij = 1 となるような任意のノード i, j およびタイムスロット t = 0, . . . , M − 1 において任意の tに関して wti,tj = 1• hij = 1 となるような任意のノード i, j ，タイムスロット t = 0, . . . , M − 1 において任意の t およびタイムスロット u = t, . . . , M − 1 において任意の u に関して wti,uj = 1
これ以外の場合は wti,uj = 0 である．

この制約条件は，ノード i, j が 1 ホップまたは2 ホップ関係にあるとき，同じタイムスロットでパケットを送信できないということを表わしている．この制約条件は，2 節で記述した干渉が発生しないための条件の十分条件になっていることに注意する．
• 制約条件 III
M−1 N−1 N−1∑∑∑
t=0 i=0 j=0

hij stiM−1∑

suj = 0(3)

u=t

この制約条件は，親ノードは自分のすべての子ノードからパケットを受信するまでは，自分の親ノードにパケットを送信できないということを表わしている．
スケジューリング問題を解くことは，以上の (1) から (3) の制約条件を満たす sti (t = 0, . . . , M − 1; i =0, . . . , N − 1) が存在する最小の M と，その時の sti を求めることである．

4 ホップフィールドニューラルネットワーク
による解法
本研究では，ホップフィールドニューラルネットワー
クによってスケジューリング問題を解くことを考える．
本研究で考えるホップフィールドニューラルネットワー
クは，ユニット ti (t = 0, . . . , M − 1; i = 0, . . . , N − 1)とユニット uj (u = 0, . . . , M − 1; j = 0, . . . , N − 1) が結合係数 wti,uj で結合された相互結合型ネットワークである．ここに，ユニット間の結合係数が対称 wti,uj =wuj,ti であるとする．さらに，ユニットの状態変化は非同期的であり，1 回に任意の 1 ユニットしか状態変化しないものとする．本研究においては，wti,uj は 01 変数であり，センサノード i がタイムスロット t にパケットを送信し，かつセンサノード j がタイムスロット u にパケットを送信するとき，制約条件 I から III を満たす時
は wti,uj = 0，満たさないときは wti,uj = 1 となる．し

図9

ホップフィールドネットワークの条件

ホップフィールドニューラルネットワークによってスケジューリング問題を解くためには次の手続きを行う．0,1 の値をとる適当な sti (t = 0, . . . , M − 1; i =0, . . . , N − 1) を初期値として設定し，式 (4) により逐次sti (t = 0, . . . , M − 1; i = 0, . . . , N − 1) を更新する．この処理を反復し，反復を行っても sti の更新が行われなくなったとき，sti (t = 0, . . . , M − 1; i = 0, . . . , N − 1)は制約条件 I から III を満たすスケジューリングとなっているはずである．

sti = isgn[M−1 N−1∑∑

wti,uj suj ](4)

u=0 j=0{
isgn(a) =0 (a > 0)
1 (otherwise)

5 実行結果本研究では、ノード数 100 のセンサネットワークを考える前に、小規模のネットワークとして、図 8 に示されたノード数 7 のセンサネットワークを考え、3 節で説明したホップフィールドニューラルネットワークによって制約条件 I–III を満たすスケジューリングを求めた。
ここでは、フレームのタイムスロット数を 7(すなわちM = 7) として、表 1 に示された sti の初期値から始めて、表 2 に示された結果を得た。
表1@@@012345601234560001000001000000000101000000000010000000010100000

表2@

@
@
0123456

sti の初期値

スケジューリング結果

01234560001000000001000001000000001010000000100001000000

横軸:タイムスロット
縦軸:ノード
表 1–2 では、ノード i がどの時間 t で送信するかを表している。縦軸がノードを、横軸がタイムスロットを表している。例えば、表 1 の右から一列目、つまりタイムスロット 0 においては、ノード 3 が送信するスケジュールになっていることがわかる。表 2 から、制約条件を満たしたスケジューリングがホップフィールドニューラルネットワークによって求められてることがわかる。
ノード数を 7 としたプログラムを 100 回実行したところ、変更回数が毎回違っていた。これは、sti の初期値を決める際にランダム関数を使用しているのが原因となっていると考えられる。変更回数の平均は 38.89 回となった。計算時間はノード数が少なかったので、計測が出来ないほど短かった。
本研究で，ノード数を 100 のセンサネットワークのスケジューリングを行った場合は計算に 1 週間掛けても解を求めることが出来なかった．このことから，ノード数の多いネットワークのスケジューリングにホップフィールドネットワークは適していないといえる．そのため本研究ではプログラムを，ノードの生成とネットワーク，ツリー構成，ツリーの分割様プログラム，分割したネットワークでスケジューリングをおこなうプログラム，分割して行ったスケジューリングをまとめるプログラム，まとめたスケジューリングが正しいかどうか確認するプ
ログラムの 4 つを作成した．4 つのプログラムの合計実行時間はそれぞれのプログラムを実行するために掛かる時間を省くと 30 秒程度となった．よって，ノードを分割しないでスケジューリングを行うよりも，ノードを分割してスケジューリングを行ったほうが計算時間が短く効率よくスケジューリングを求められる結果となった。

6 まとめ
本研究では，アクセス制御を TDMA で行うツリー型構造のセンサネットワークを考え，ホップフィールドニューラルネットワークを使って各ノードの送信スケジュールを求める方法を考えた．プログラムを分割し，実行することによりホップフィールドニューラルネットワークを使用してセンサネットワークのスケジューリングを行うことが出来ることが確認できた．

参考文献[1] 佐々木美裕 , 古田壮宏 , 石崎文雄 , 鈴木敦夫, “クラスタツリーを用いたセンサネットワークの構成方法,” 日本オペレーションズ・リサーチ学会 2007 年
春季研究発表会, pp．90-91, 2007.

[2] T. Furuta, M. Sasaki, F. Ishizaki, A. Suzuki andH. Miyazawa, “A new clustering model of wireless sensor networks using facility location theory,” Journal of the Operations Research Societyof Japan，vol.52, no.4, pp. 366-376, 2009.
[3] 木利友一, 菅野正嗣, 村田正幸, “大規模センサネッ
トワークにおけるクラスタ間マルチホップ通信の性能評価,” 信学技報, vol. 106, no. 42, IN2006-6, pp.

31-36, 2006.
[4] J. C. Hou, N. Li and I. Stojmenović, Topology construction and maintenance in wireless sensor networks, Handbook of sensor networks algorithms
and architectures, Wiley, 2005.
[5] S. Salcedo-Sanz, C. Bousono-Calzon and
A. R. Figueiras-Vidal, “A mixed neural-genetic
algorithm for the broadcast scheduling problem,”IEEE Transactions on Wireless Communications,vol.2 , no.2, pp.277-283 , 2003.
[6] B. C. Prim, “Shortest connection networks andsome generalizations,” Bell System Technical
Journal, 36， pp.1389-1401, 1957.