(57)【要約】【課題】センサーツリーのノードの移動パターンを増やすことにより、センサーツリー上のノードのエネルギー使用量を削減することを目的とする。【解決手段】センサーツリーにおける経路選択装置は、前記センサーツリーの中で配下に子ノードを保持する第１のノードを選択し、当該第１のノードを頂点とするサブツリーの配下の第２のノードを、当該サブツリーに属さない第３のノードの配下に移動したときに、前記センサーツリーにおいて送受信されるパケット総数が減る場合、前記センサーツリーにおいて前記第２のノードを前記第３のノードの配下に移動するノード移動部を有し、前記ノード移動部は、前記第１のノードを頂点とするサブツリーの配下のノードの中に、移動によってパケット総数が減るノードが存在しない場合、当該サブツリーの配下のノードの中でパケット総数に変化を与えないノードを前記第３のノードの配下に移動する。【選択図】図１０
2020017828.tif 000002
【特許請求の範囲】
【請求項１】
複数のセンサーノードを含む複数のノードで構成されたセンサーツリーにおいて、下位のノードからのセンサーレポートをパケットに格納して上位のノードに送信する際の経路を選択する経路選択装置であって、
前記センサーツリーの中で配下に子ノードを保持する第１のノードを選択し、当該第１のノードを頂点とするサブツリーの配下の第２のノードを、当該サブツリーに属さない第３のノードの配下に移動したときに、前記センサーツリーにおいて送受信されるパケット総数が減る場合、前記センサーツリーにおいて前記第２のノードを前記第３のノードの配下に移動するノード移動部を有し、
前記ノード移動部は、前記第１のノードを頂点とするサブツリーの配下のノードの中に、移動によってパケット総数が減るノードが存在しない場合、当該サブツリーの配下のノードの中でパケット総数に変化を与えないノードを前記第３のノードの配下に移動する、経路選択装置。
【請求項２】
前記ノード移動部は、前記第１のノードを頂点とするサブツリーの配下のすべてのノードに対して、ノードが移動したときのパケット総数の変化を求め、パケット総数が最も減少するノードを移動する、請求項１に記載の経路選択装置。
【請求項３】
前記ノード移動部は、前記センサーツリーにおいてノードの移動を繰り返し行う場合、ノードがサブツリーの頂点として選択される回数に上限を設定する、請求項１又は２に記載の経路選択装置。
【請求項４】
前記ノード移動部は、前記センサーツリーにおいてノードの移動を繰り返し行う場合、ノードの移動回数に上限を設定する、請求項１乃至３のうちいずれか１項に記載の経路選択装置。
【請求項５】
前記ノード移動部は、前記センサーツリーにおいてノードの移動を繰り返し行う場合、パケット総数に変化を与えないノードの移動回数に上限を設定する、請求項１乃至４のうちいずれか１項に記載の経路選択装置。
【請求項６】
複数のセンサーノードを含む複数のノードで構成されたセンサーツリーにおいて、下位のノードからのセンサーレポートをパケットに格納して上位のノードに送信する際の経路を選択する経路選択装置における経路選択方法であって、
前記センサーツリーの中で配下に子ノードを保持する第１のノードを選択し、当該第１のノードを頂点とするサブツリーの配下の第２のノードを、当該サブツリーに属さない第３のノードの配下に移動したときに、前記センサーツリーにおいて送受信されるパケット総数が減る場合、前記センサーツリーにおいて前記第２のノードを前記第３のノードの配下に移動するステップと、
前記第１のノードを頂点とするサブツリーの配下のノードの中に、移動によってパケット総数が減るノードが存在しない場合、当該サブツリーの配下のノードの中でパケット総数に変化を与えないノードを前記第３のノードの配下に移動するステップと、
を有する経路選択方法。
【請求項７】
請求項１乃至５のうちいずれか１項に記載の経路選択装置の各部としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のセンサーノードを含む複数のノードで構成されたセンサーツリーにおける経路選択装置、経路選択方法及びプログラムに関する。
【背景技術】
【０００２】
特定の場所にセンサーを配置し、対象地の湿度、温度、気体濃度等をセンサーノードによって計測し、そのセンサーレポートをデータ収集ツリーで収集し、ルートセンサーノードからベースステーションに通知することによって分析を行う、あるいはガスメータ、電気メータなどの情報を定期的にデータ収集ツリーで収集する、ことを可能にする技術として、ＲＰＬ（Routing Protocol for Low-power and Lossy Networks）プロトコルが標準化されている（例えば、非特許文献１参照）。データ収集ツリーは、ツリー状に構成されたセンサーノードと、センサーノード間に位置してセンサーレポートを中継する役割を果たすリレーノードとの集合であり、センサーツリーとも呼ばれる。
【０００３】
データ収集ツリー上の各センサーノードは収集サイクル毎に当該センサーからの必要数のセンサーレポートを、ツリー上で当該ノードのすべての下位センサーノードからのセンサーレポートと一緒にパケットにまとめてツリーの上位センサーノードに送信する。１パケットに格納できるセンサーレポート数には上限（データ集約レート：S）があるため、各センサーノード／リレーノードが送信するパケット数は、当該センサーノード／リレーノードが送信する必要があるセンサーレポート数とSから導かれる。
【０００４】
またセンサーノード／リレーノードi（ノードi）の１データ収集サイクルにおけるエネルギー使用量：E(i)を以下の式１によって表すことができる。
E(i)=ETx×TN(i)+ERx×RN(i)      （式１）
式１において、ETxは１センサーパケットの送信に必要とされるエネルギー量、ERxは１センサーパケットの受信に必要とされるエネルギー量、TN(i)はノードiが１データ収集サイクルに必要な送信パケット数、RN(i)はノードiが１データ収集サイクルに必要な受信パケット数である。ノードi自身が作成する１データ収集サイクルのセンサーレポート数をd(i)、ノードiが転送するツリー上で下位のノードすべてのセンサーレポート数の合計をd(below_i)とするとTN(i)は以下の式２及び式３で表される。
TN(i)=(d(below_i)+d(i))/S,  ((d(below_i)+d(i))%S=0の場合)      （式２）
TN(i)=(d(below_i)+d(i))/S+1,  ((d(below_i)+d(i))%S≠0の場合)      （式３）
式２及び３において、"/"は割り算の商を示し、"%"は割り算の剰余を示す。式２及び式３から剰余が０以外のときには送受信されるパケットに空きがあることが分かる。そのため、各リンクにおけるパケットの空きを少なくすることもパケット数削減に有効な手段であると考えられる。
【０００５】
ツリーT全体の１データ収集サイクルにおけるエネルギー使用量合計：Etreeは、すべてのツリーノードの１データ収集サイクルのエネルギー使用量を足し合わせたものなので、以下の式４によって表すことができる。
Etree=Σi∈TE(i)      （式４）
特に屋内に設置されるセンサーでは、各センサーが使用する電力はACアダプターから供給されるが、その場合センサーに提供される電力総和をなるべく少なくすることが電力削減の目的で必要となる。そのため式４で表されるEtreeを最小にする方式が検討されている（非特許文献２参照）。非特許文献２では２つの問題に対処している。一つはMECAT（Minimum Energy Cost Aggregation Tree）問題であり、この問題はセンサーレポートを発生せずツリー上の下位センサーノードのセンサーレポートだけを転送する目的で使われるリレーノードが存在しないWSN（Wireless Sensor Network）を対象とするツリーノード（ツリー上のノード）が利用するエネルギー総和の最小化問題である。もう一つはMECAT-RN（MECAT with Relay Node）問題であり、この問題はWSNにおいてリレーノードを含めてのすべてのツリーノードが使用するエネルギー総和の最小化問題である。
【０００６】
上記の式１で、ETxとERxは固定値であるため、リレーノードが存在しないWSN及びリレーノードを含むWSNともに、ツリー上のすべてのリンク（ツリーノードがセンサーレポート転送のために使う隣接関係）上で送受信されるパケット数総和を最小にすることがMECAT問題及びMECAT-RN問題と同値である。つまりMECAT問題及びMECAT-RN問題は次式５と同値であり、ETxとERxは固定値なので、式６と同値である。
【０００７】
【数１】
2020017828.tif 000003
【０００８】
【数２】
2020017828.tif 000004
【０００９】
式５及び式６においてGは当該WSNを示し、T(G)は、G上のツリー集合を示す。また、eはツリー上のリンクを示し、z(e)はe上で１データ収集サイクルで送信されるセンサーレポート数を示すので、もしe上の送信ノードをiとした場合はz(e)=d(below_i)+d(i)が成り立つ。
【００１０】
図１にデータ収集ツリー上のリンクのパケット数の例を示す。ここで、データ集約レートSは５としている。またノード０はルートノードを示し、Nで始まる○のノードはセンサーノード、▲のノードはリレーノードを示している。各ノード内の括弧内の数字は当該ノードから発生するセンサーレポート数：d(i)を示し、その横の下線の数字はd(below_i)を示している。ノード間の実線→はツリー上のリンクを示し→の方向はパケットの送信方向を示している。ツリー上のリンク横の数字は１データ収集サイクルにおいて当該リンク上で送信されるパケット数を示している。
【００１１】
非特許文献２は、ランダムに作成した最短経路ツリーがMECAT問題には有効であり、最短経路ツリーでは最適解（すべてのツリーノードが利用する総エネルギー消費の最小値）の２倍以内のセンサーの総エネルギー消費で抑えられていることを証明している。ここで、最短経路ツリーとはツリー上の各センサーノードがルートノードから最小ホップ数を取るツリーのことである。例えば、図２において（１）は、WSN上でのノード間の隣接関係を点線で示している。ここで隣接関係とは、通信（接続）が可能な関係をいい、例えば、一方のノードが、他方のノードからの電波信号（例えば、ＲＳＳＩ（Received Signal Strength Indicator））の到達範囲内に有る関係をいう。なお、各ノードの横の括弧内数字は当該ノードが１データ収集サイクルで報告するセンサーレポート数である。このWSN上で作成されたセンサーツリー例が（２）〜（４）で示されている。
【００１２】
（２）は最短経路ツリーの一例であり、ツリー上のノードの上下関係（リンク）は実線→で示されており、この上下関係を用いて、センサーレポートがツリーに沿ってルートノードであるノード０まで伝達される。（２）に示すようにツリー上のすべてのノードはノード０までの最小ホップ経路上にある。（３）も最短経路ツリー例であり、（２）以外にも最短経路ツリーは複数存在することがわかる。（４）は最短経路ツリーではないツリー例を示している。この例では、ノード５からノード０までのツリー上のホップ数が３であるが、最小ホップ数は２であるので、最短経路ツリーではない。
【００１３】
非特許文献２では、各ノードが報告するセンサーレポート数に関わらず、最短経路ツリーの場合は式６で示されるセンサーツリーの総エネルギーが最適解（最小エネルギー）の２倍以内に抑えられることを証明している。
【００１４】
また、非特許文献２ではMECAT-RN問題についてはLAST（Light Approximate Shortest-path Tree）アルゴリズム（非特許文献３参照）を適用することが有効であることを示している。LASTアルゴリズムにはパラメータ：α,βがあり、(α,β)-LASTで作成されたツリーでは、ツリー上の各ノードでルートノードからの距離がルートノードからの最短経路のα倍以内、ツリー全体のコスト（ツリーリンクコストの総和）がMST（minimum spanning tree）のツリーコストのβ倍以内であることが保証される。非特許文献２ではリレーノードを含むWSN上で、(3,2)-LASTを適用して作成したツリーは最適解（最小エネルギーツリー）の７倍以内の総エネルギー量に抑えられることを証明している。
【００１５】
図３及び図４に(3,2)-LASTのMECAT-RN問題への適用例を示す。図３（１）は、リレーノード（RN：▲）を含むWSNを示す。リレーノードは、隣接関係のないセンサーノード間を中継する役割を果たし、リレーノード自体はセンサーレポートをルートノード０に送信しないことが特徴である。まず（２）でリレーノードを含まないセンサーノード間の論理リンクを作成する。論理リンクはリレーノードを除いたセンサーノード間の繋がりを示している。この際、各論理リンクコストはセンサーノード間のリレーノードを含めた最小ホップ数である。（２）で論理リンクコストは各論理リンクの横に記されている数字であるが、数字が記されていないリンクはすべてリンクコスト＝３である。（３）及び（４）は(3,2)-LASTアルゴリズムの適用であり、まず（３）で（２）のネットワークでMSTを作成する。MSTはすべてのノード（センサーノード０〜５）にまたがるツリーを構成する論理リンクコスト和が最小のツリーであり、Primのアルゴリズム等が用いられる。
【００１６】
(3,2)-LASTの特徴である（４）では、MST上の各ノードでの最短経路コストの比較が行われ、もしMST上の経路＞（３×ルートノードからの最短経路）の条件を満たす場合はルートノードからの最短経路にMST経路が置き換えられる。この例ではMST上のノード５とノード２までの経路が最短経路に置き換えられていることがわかる。（５）では（４）での(3,2)-LASTアルゴリズムの結果作成されたツリーをリレーノードを含めて展開した結果を示している。もし（５）の結果でノード０からの経路が、あるノードに対して複数存在する場合は、その内の最短経路を選択するが、図３の例では各ノードで経路が一意に定まる。
【００１７】
図４では、リレーノードに分解した結果で一つのノードに対して複数の経路が出る場合の対処法を示す。この例でも同様に、（２）でリレーノードを含まないセンサーノード間の論理リンクを作成する。（２）で論理リンクコストは各論理リンクの横に記されている数字であるが、数字が記されていないリンクはすべてリンクコスト＝２である。（３）で（２）で設定した論理リンクを基にMSTを作成する。この例ではMST上の経路＞（３×ルートノードからの最短経路）の条件を満たすノードが存在しないので、（３）の結果をそのままリレーノードを含めて（４）で展開している。しかし、ノード１〜４は、ルートノード０までの経路が２つあることが判る。その場合は、ノード１から順に最短経路を選択する。ノード１からの最短経路はリレーノード（ｒ１）を介するノードなのでノード１とノードｒ２の間のリンクは削除される。その結果、各ノードからノード０までの経路が一意に定まり（５）の最終ツリーが生成される。
【先行技術文献】
【非特許文献】
【００１８】
【非特許文献１】T. Winter, et al., "RPL: IPv6 Routing Protocol for Low-power and Lossy Networks", RFC6550, IETF, March 2012.
【非特許文献２】Tung-Wei Kuo, Kate Ching-Ju Lin, and Ming-Jer Tsai, "On the Construction of Data Aggregation Tree with Minimum Energy Cost in Wireless Sensor Networks: NP-Completeness and Approximation Algorithms", IEEE Transactions on Computers, vol. 65, issue 10, pp. 3109-3121, 2016.
【非特許文献３】S. Khuller, B. Raghavachari, and N. Young, "Balancing minimum spanning trees and shortest-path trees", Algorithmica, vol. 14, pp. 305-321, 1995.
【非特許文献４】H. Matsuura, "Switching-based Data Aggregation Tree Optimization on Total Energy Consumption", IEICE General Conference, March 2018.
【発明の概要】
【発明が解決しようとする課題】
【００１９】
MECAT問題では最適解の２倍以内、MECAT-RN問題では最適解の７倍以内のエネルギー使用量が上限になることが非特許文献２で証明されているが、逆に最大使用エネルギーがMECAT問題では最大で２倍に増え、MECAT-RN問題では最大で７倍に増えることが懸念される。これらの最適解からの使用エネルギーの増分を減らす方式として非特許文献４の方式が提案されている。非特許文献４ではセンサーツリーのノードを移動してセンサーツリーの構成を変えることにより、センサーツリー上のノードのエネルギー使用量を削減することを可能としている。
【００２０】
図５に従来方式（非特許文献４）で提案しているセンサーツリー上でのノードの移動フローを示す。STEP1で初期ツリーを作成した後、STEP2では当該初期ツリーの中で、STEP1でのツリー作成後、STEP2〜STEP5のループでまだ選択されていないノードをサブツリーの頂点ノードとして選択する。その後にSTEP4で選択されたサブツリーの頂点ノード配下で移動可否を判断する。そして移動可能なノードがある場合はSTEP1に戻り、STEP1でノード移動後のツリーを作成し、移動後のツリーに対してSTEP2以降の処理を行う。もしSTEP4の移動可否判断で移動可能なノードがサブツリー内に無いと判断した場合はSTEP2に戻り他のサブツリーの頂点ノードを選択する。この処理をSTEP1で生成された途中経過ツリー内で選択されたすべてのサブツリーの頂点ノードで移動可能なノードが無くなるまで行う。
【００２１】
しかしながら、非特許文献４では当該フローにおけるSTEP4の移動可否判断として、移動によってセンサーツリー上で送受信されるパケット総数が減少するときのみ移動を可能としている。この場合、図６に示すような課題が生じ、非特許文献４で求めたパケット減少数が理想的なパケット減少数（図７、図８）よりも大幅に少なくなる可能性がある。
【００２２】
図６の（１）は図５のSTEP1で作成される１途中経過ツリーであるとする。データ集約レート：S=5とし、N11〜N13はルートノード０から１ホップのノードであり、N21〜N23はルートノード０から２ホップのノードであり、N31〜N32はルートノード０から３ホップのノードである。また図に示すようにd(N11)=5, d(N12)=5, d(N13)=5, d(N21)=6, d(N22)=5, d(N23)=6, d(N31)=1, d(N32)=1である。→で示されるツリー上の上下関係よりd(below_N11)=6, d(below_N12)=7, d(below_N13)=6, d(below_N22)=2となる。また、N31, N32は図に示すようにツリー上でN22に帰属しているが、N31はN21にN32はN23に対してそれぞれ隣接関係を保持している。また、ツリー上でリンク横に示されている数字は当該リンク上で１データ収集サイクルにおいて送信されるパケット数を示している。この例ではデータ集約レート：S=5であるため(d(below_i)+d(i))/5の値がノードiから送信されるパケット数となる。
【００２３】
図６の（１）で示されるような途中経過ツリーが図５のSTEP1で作成された場合は、非特許文献４の方式では、図６の（２）及び（３）のいずれの途中経過ツリーにも移行しない。理由は図５のSTEP4の移動可否判断において、移動するためには１ノードの移動後にツリー上のパケット数が減ることが条件となるが、図６の（２）及び（３）においていずれのツリーにおいてもパケット数に変化が無いためである。
【００２４】
しかしながら図７に示すように、もしN31とN32が（１）のN22配下から（２）のようにN21/N23にそれぞれ移動した場合は、（２）のツリーに示すようにN22とN12から上位ノードに送信されるパケット数がそれぞれ１減少することになり、結果的にツリー上のパケット数が２減少することになる。図７をMECAT問題で一般化した図が図８である。図７ではルートノードからの最大ホップ数が３のツリーであったが、図８ではホップ数が(k+1)のツリーを対象にしている。図の各ノードの名称でNk1とはルートノード０からのホップ数がkの最も左側のノードで、Nk2はホップ数がkの真ん中のノードでNk3はホップ数がkの最も右側のノードであることを示している。また、0<i<kの場合d(Ni1)=5であることが想定されている。
【００２５】
図６で述べたのと同じ理由で非特許文献４の方式では図８の（１）の途中経過ツリーをこれ以上変更できないが、理想的には図８の（２）のようなツリーになることがパケット数を最小にするためには望ましい。図８の（２）の場合、（１）に比べてパケット数がk減ることになる。理由は、Nk2からN12までの真ん中のk個のノードから送信されるパケット数が１ずつ減少するからである。kの値はルートノード以外のノード数をNとした場合k=(N-2)/3となり、Nの値が大きくなるとkも比例して大きくなる。このように、非特許文献４の方式にはパケット数を最小にできない課題がある。
【００２６】
図８はMECAT問題での課題の一般化であったが、MECAT-RN問題のようにリレーノードが存在する場合でも同じ課題がある。例えば、図８の（１）でルートノード０とN(k-1)i間に複数のリレーノードがセンサーノード間の中継をする場合（ここでi=1, or 2, or 3）でも非特許文献４の方式では図８の（１）のツリー上のノードを移動することはできない。理由は当該移動によってパケット総数が変化しないためである。そのため、MECAT-RN問題においても図６〜８を参照して説明した課題を非特許文献４の方式では解決できない。
【００２７】
また、図６〜８ではS=5としているが、Sの値が3以上であり、且つ0<i<kの条件でd(Nij)=S（ここでj=1, or 2, or 3）の場合、図６〜８の課題が非特許文献４の方式では生じることもわかる。つまり、３以上のすべてのSで同じ課題が生じることになる。
【００２８】
本発明は、上記の点に鑑みてなされたものであって、センサーツリーの構成を変えるための条件を緩和してセンサーツリーのノードの移動パターンを増やすことにより、センサーツリー上のノードのエネルギー使用量を削減することを目的とする。
【課題を解決するための手段】
【００２９】
本発明の一形態に係る経路選択装置は、
複数のセンサーノードを含む複数のノードで構成されたセンサーツリーにおいて、下位のノードからのセンサーレポートをパケットに格納して上位のノードに送信する際の経路を選択する経路選択装置であって、
前記センサーツリーの中で配下に子ノードを保持する第１のノードを選択し、当該第１のノードを頂点とするサブツリーの配下の第２のノードを、当該サブツリーに属さない第３のノードの配下に移動したときに、前記センサーツリーにおいて送受信されるパケット総数が減る場合、前記センサーツリーにおいて前記第２のノードを前記第３のノードの配下に移動するノード移動部を有し、
前記ノード移動部は、前記第１のノードを頂点とするサブツリーの配下のノードの中に、移動によってパケット総数が減るノードが存在しない場合、当該サブツリーの配下のノードの中でパケット総数に変化を与えないノードを前記第３のノードの配下に移動することを特徴とする。
【００３０】
また、本発明の一形態に係る経路選択方法は、
複数のセンサーノードを含む複数のノードで構成されたセンサーツリーにおいて、下位のノードからのセンサーレポートをパケットに格納して上位のノードに送信する際の経路を選択する経路選択装置における経路選択方法であって、
前記センサーツリーの中で配下に子ノードを保持する第１のノードを選択し、当該第１のノードを頂点とするサブツリーの配下の第２のノードを、当該サブツリーに属さない第３のノードの配下に移動したときに、前記センサーツリーにおいて送受信されるパケット総数が減る場合、前記センサーツリーにおいて前記第２のノードを前記第３のノードの配下に移動するステップと、
前記第１のノードを頂点とするサブツリーの配下のノードの中に、移動によってパケット総数が減るノードが存在しない場合、当該サブツリーの配下のノードの中でパケット総数に変化を与えないノードを前記第３のノードの配下に移動するステップと、
を有することを特徴とする。
【００３１】
また、本発明の一形態に係るプログラムは、
上記の経路選択装置の各部としてコンピュータを機能させることを特徴とする。
【発明の効果】
【００３２】
本発明によれば、センサーツリーの構成を変えるための条件を緩和してセンサーツリーのノードの移動パターンを増やすことにより、センサーツリー上のノードのエネルギー使用量を削減することを目的とする。
【図面の簡単な説明】
【００３３】
【図１】データ収集ツリー上のリンクのパケット数の例を示す図である。
【図２】MECAT問題に適用される最短経路ツリーを説明するための図である。
【図３】(3,2)-LASTアルゴリズムのMECAT-RN問題への適用例（その１）を示す図である。
【図４】(3,2)-LASTアルゴリズムのMECAT-RN問題への適用例（その２）を示す図である。
【図５】従来方式におけるツリー生成方法を示すフローチャートである。
【図６】従来方式によって生じる課題を説明するための図である。
【図７】パケット数を最小化するための理想的な移動結果を示す図である。
【図８】従来方式よりパケット数がk減少する例を示す図である。
【図９】本発明の実施の形態における経路選択装置の機能構成例を示す図である。
【図１０】本発明の実施の形態における経路選択装置の動作を示すフローチャートである。
【図１１】MECAT問題に適用したときのノード移動例である。
【図１２】MECAT-RN問題に適用したときのノード移動例である。
【図１３】従来方式に対するパケット数の減少効果を示す図である。
【図１４】従来方式に対する総移動回数の増加を示す図である。
【図１５】移動にかかる総時間について従来方式との比較結果を示す図である。
【図１６】本発明の実施の形態における経路選択装置のハードウェア構成例を示す図である。
【発明を実施するための形態】
【００３４】
以下、図面に基づいて本発明の実施の形態を説明する。図９は、本発明の実施の形態における経路選択装置１００の機能構成例を示している。
【００３５】
本実施の形態では、複数のノード（センサーノード／リレーノード）で構成されたセンサーツリーにおいて、下位のノードからのセンサーレポートをパケットに格納して上位のノードに送信するデータ収集サイクルを繰り返すネットワーク利用形態を想定している。本実施の形態は、リレーノードが存在しないWSNにも適用可能であり、リレーノードを含むWSNにも適用可能である。
【００３６】
図１の例でもわかるように各ノードからのレポート数には違いがあり、より大きなレポート数を持つノードはなるべくルートノードまでのホップ数をより少なくした方がエネルギーの節約になる。また、(d(below_i)+d(i))%Sの剰余が０以外のときは送受信されるパケットに空きがあるので、各パケットに収容できるセンサーレポート数Sがなるべく埋まるようにした方がエネルギーの節約になる。経路選択装置１００は、このような観点でセンサーツリーのノードを移動し、エネルギー使用量を削減できる経路を選択する。
【００３７】
図５に示すように、経路選択装置１００は、ノード情報取得部１１０と、ルーティング要求部１２０と、ルート決定部１３０と、WSN格納部１４０と、ツリー格納部１５０とで構成される。また、ルート決定部１３０は、WSN認識部１３１と、初期ツリー作成部１３２と、センサーレポート数計算部１３３と、ノード移動部１３４とを含む。この例では経路選択装置１００はルートノード（０）に含まれるが、経路選択装置１００は必ずしもルートノードに含まれる必要はなく、例えば、ベースステーション等のルートノードに接続された装置に含まれてもよい。
【００３８】
ノード情報取得部１１０は、ルートノードに隣接しているノードの情報を取得し、それらのノードに隣接しているノードの情報を取得する。同様にしてノードの情報の取得を繰り返し、その結果、ルートノードの所属しているWSNに所属するすべてのノードの隣接関係を取得することができる。
【００３９】
ルート決定部１３０内のWSN認識部１３１は、ノードの隣接関係からWSNの構成を認識することができ、その結果としてWSN構成をWSN格納部１４０に格納する。
【００４０】
初期ツリー作成部１３２は、初期ツリーを作成する。初期ツリーを作成するために、MECAT問題では最短経路ツリー、MECAT-RN問題では(3,2)-LASTアルゴリズムを使うことが１例として考えられる。このようにして作成された初期ツリーはツリー格納部１５０に格納される。
【００４１】
センサーレポート数計算部１３３は、初期ツリーの各ノードiのセンサーレポート数d(i)を設定するとともに、各ノードiが転送する下位ノードの合計センサーレポート数d(below_i)を求める。
【００４２】
ノード移動部１３４は、最終的にセンサーツリーにおいて送受信されるパケット総数が減ることを目的としてセンサーツリーのノード移動を繰り返す。ノード移動部１３４は、ノードを移動した後のツリーをツリー格納部１５０に格納する。
【００４３】
最終的に生成されたツリー構成は、ルーティング要求部１２０から各ノードに対してルーティングの設定を行うことで、実際のWSN上でツリーに反映される。
【００４４】
次に図１０のフローチャートを説明する。図１０は本発明の実施の形態における経路選択装置１００の動作を示すフローチャートである。
【００４５】
STEP101は、最初は初期ツリー作成部１３２が初期ツリーを作成するプロセスである。例えば、MECAT問題であれば最短経路ツリー、MECAT-RN問題であれば(3,2)-LAST等の既存の方式で初期ツリーが作成される。その後は、一つのノードがあるサブツリーから他のサブツリーに移動することが以下のSTEP104及びSTEP105で決まった場合は、そのノードが移動した後のツリーをノード移動部１３４が作成するプロセスである。センサーレポート数計算部１３３は、初期ツリーに対して、各ノードiが作成するレポート数d(i)と、各ノードiが転送する下位ノードの合計センサーレポート数d(below_i)を設定する。また、ノード移動後のツリーに対して、各ノードiが転送する下位ノードの合計センサーレポート数d(below_i)に変化があった場合にd(below_i)を再設定する。
【００４６】
以下のSTEP102〜STEP105はノード移動部１３４が実行するプロセスである。
【００４７】
STEP102はSTEP101で生成されたツリーの中で移動対象サブツリーの頂点ノードを決定する。このときの条件としては、頂点ノードがツリーのリーフノードではなく、少なくとも１つの子ノードを持つことである。また、STEP101での途中経過ツリー生成後、STEP102〜STEP105のループでまだ選択されていないノードを選択する。ただしサブツリーの頂点ノードに選ばれる上限数回まで、すでにサブツリーの頂点ノードとして選択されているノードは、当該上限数回を超えてはサブツリーの頂点ノードとして選択されない。
【００４８】
STEP103はSTEP102でサブツリーの頂点ノードが選択できたかどうか判断する。もし選択できない場合（No）は、その時点までで作成されているツリーが最終出力ツリーとなり、処理が終了する。もしサブツリーの頂点ノードが選択できた場合はSTEP4の処理に移る。
【００４９】
STEP104では当該サブツリーの頂点ノードの配下のノード（頂点ノードは含まない）で、移動によってツリー上で送受信されるパケット総数が減るノードが存在するかどうか判断する。このときの条件としては、移動先の親ノードが当該サブツリーに属さないことである。ここではエネルギー使用量の削減効果を高めるため、移動によって最もパケット削減数が大きいノードを当該サブツリー以外のノード配下に移動するものとする。ただし、サブツリー配下のすべてのノードを調査してパケット数削減を実現する移動が無い場合は移動によりパケット数に変化がないノードを移動する。ただし、すでに移動回数の上限に達しているノードは移動の対象にならない。
【００５０】
STEP105では、STEP104の移動可否判断で移動可能なノードが存在すると判断された場合（Yes）は、STEP101の処理に移り当該ノードの移動先のノード配下への移動を行い、移動後のツリーを作成する。もし当該サブツリー配下で移動ノードが無いと判断された場合（No）はSTEP102に移り他のサブツリーの頂点ノードを探すことになる。
【００５１】
なおSTEP104の移動回数の上限は、移動によりパケット総数に変化を与えないノードの移動回数の上限としてもよい。STEP104の移動回数の上限とSTEP102のサブツリーの頂点ノードに選ばれる回数の上限のどちらかは本発明の実施の形態では必要となる。理由はどちらかの制限がなければ、パケット総数に変化を与えないノードの移動が、移動のループ（ある２つの親配下への移動が無限に繰り返される）になる可能性があり、その場合は図１０のフローチャートが終了しないからである。
【００５２】
＜MECAT問題への適用例＞
図１１に本実施の形態をMECAT問題に適用したときのノード移動例を示す。この例では、図１１の（１）のように最短経路ツリーがすでに生成されている。図１１において各ツリーノード内の括弧内に記されている（a）に関して、aはノードi自身が生成する１データ収集サイクルのセンサーレポート数：d(i)の値であり、その横で下線を引いてあるbはノードiが転送する下位ノードすべてのセンサーレポート数の合計：d(below_i)である。実線矢印はツリーノード間の隣接関係を示し、センサーレポートはこの実線に沿って下位ノードから上位ノードに転送され、最終的にルートノード０に送付される。点線はツリーに使用されていないノード間の隣接関係を示す。また、各リンク横に記されている数字は当該リンク上で送信されるパケット数を示しており、データ集約レートSは５である。
【００５３】
この例では図１１の（１）で初期ツリーとしての最短経路ツリー上で、下位に子ノードを保持するノードとしてN11, N12, N13, N22, N31があるので、その中の１ノードがサブツリーの頂点ノードとして選択される。この例ではN31はサブツリーの頂点ノードとして選択されても配下ノードを移動できない。理由は配下ノードN41がツリー上のリンク以外の隣接関係を持たないからである。
【００５４】
N11がサブツリーの頂点として選択された場合、N21をN31配下に移動することが図１０のSTEP104で検討される。その場合N31-N22, N22-N12, N12-0間の各リンクで１パケットずつ増えるのに対してN11-0間でパケット数が２減少する。そのため、合計でパケット数が１増加する。このようにパケット数が増加する場合は移動対象とならないので、移動は行われない。N13がサブツリーの頂点として選択された場合もN23をN32に移動することによってパケット数が１増加するため移動は行われない。
【００５５】
N12かN22がサブツリーの頂点として選択された場合は、これらのノードの配下ノードあるN31とN32が移動対象として検討される。なぜならN31はN21に対して隣接関係を持ち、N32はN23に対して隣接関係を持つからである。N31, N32のいずれの移動もパケット数に変化が得られないが、図１０のSTEP104でN31, N32が移動可能であると判断される。その場合は任意にどちらかの移動が行われるが、本例では図１１の（２）でN32が移動したとしている。
【００５６】
ここで、再度図１０のSTEP101に戻って図１１の（２）の移動後のツリーのサブツリーの頂点ノードを選択する。ここで、たまたまN13あるいはN23が選択されてしまうとN32がN22配下に戻ってしまうが、N12、N22が選択された場合はN31がN22からN21配下に移動する。理由は図１１の（３）に示すように、この移動によりリンクN22-N12, N12-0のパケット数が１ずつ減ることにより、全体のパケット数が２減るからである。なお、図１１の（２）でサブツリーの頂点ノードとしてN13あるいはN23が選択されてしまい、N32がN22に戻ってしまい、N32がN22配下とN23配下間で繰り返して移動されるループを防ぐためには、ノードの移動回数に上限値を定めることが有効である。
【００５７】
図１１の（３）は出力ツリーとなる。理由はもしN11あるいはN21がサブツリーの頂点ノードとして選択された場合にもN31をN21配下からN22配下に移動した場合にパケット数が２増加（図１１の（２）に戻る）するためである。同じ理由でN13, N23がサブツリーの頂点ノードとして選択された場合もN32が移動することは無い。
【００５８】
＜MECAT-RN問題への適用例＞
図１２に本実施の形態をMECAT-RN問題に適用したときのノード移動例を示す。この例では、図１２の（１）のように(3,2)-LASTアルゴリズムによって、すでにリレーノードを含めたツリーが構成されている。図１２において、r1, r2はリレーノードを示し、他のノードはセンサーノードを示している。実線矢印はツリーノード間の隣接関係を示し、センサーレポートはこの実線に沿って下位ノードから上位ノードに転送され、最終的にルートノード０に送付される。点線はツリーに使用されていないノード間の隣接関係を示す。またリンクの横の数字はそのリンク上で送信されるパケット数を示しており、データ集約レートSは５である。
【００５９】
図１２の（１）では、N12, r2, N22のいずれかがサブツリーの図１０のSTEP102で頂点ノードとして選択された場合を示しているが、もし他のノード（r1, N11, N13）が頂点ノードとして選択されても、配下ノードの移動は行われない。理由はN21をN31配下に移動、あるいはN23をN32配下に移動した場合はいずれの場合ともにツリー上のパケット数が増加するためである。N12, r2, N22のいずれかが頂点ノードとして選択された場合はN31がN22配下からN21配下へ、N32がN22配下からN23配下にそれぞれ移動することが図１０のSTEP104で検討される。いずれの移動も移動前後でパケット数に変化がないので、この場合は任意選択でどちらの移動が行われる。図１２の（２）では図１０のSTEP101でN32がN23に移動したと仮定している。
【００６０】
図１２の（２）のツリーでは再度図１０のSTEP102でサブツリーの頂点ノードとしてN12, r2,N22のいずれが選択されたことを想定しているが、もしN13, N23のいずれかが選択された場合はN32がN22の配下に戻ってしまう。このような移動のループを避けるためには移動回数の上限値設定が有効である。
【００６１】
図１２の（２）ではN31のN22配下からN21配下への移動が検討されるが、図１２の（３）に示すように、この移動によりN22-r2, r2-N12, N12-0の各リンクのパケット数がそれぞれ１減少することになり合計でパケット数が３減少することになるので、N31はN21配下に移動される。
【００６２】
図１２の（３）は出力ツリーとなる。理由はもしN11あるいはN21がサブツリーの頂点ノードとして選択された場合にもN31をN21配下からN22配下に移動した場合にパケット数が３増加（図１２の（２）に戻る）するためである。同じ理由でN13, N23がサブツリーの頂点ノードとして選択された場合もN32が移動することは無い。
【００６３】
＜本発明の実施の形態の効果＞
上記のように、本実施の形態によれば、センサーツリーのノードの移動のパターンを増やすことにより、図６〜図８で述べたような場合であってもセンサーツリー上の送信パケット数を減らすことができ、センサーツリー上のエネルギー使用量を削減することが可能になる。
【００６４】
例えば、本実施の形態により非特許文献４の方式では実現できなかった図６の（１）から（２）又は（３）への移動が可能になる。もし図６の（２）の途中経過ツリーができた場合は、次にN22かN12が図１０のSTEP102でサブツリーの頂点ノードに選択された際にN31がN22の配下からN21の配下に移動されることになり、図７の理想の移動が実現されることになる。もし図６の（３）の途中経過ツリーができた場合も、次にN22かN12が図１０のSTEP102でサブツリーの頂点ノードに選択された際にN32がN22の配下からN23の配下に移動されることになり、図７の理想の移動が実現されることになる。このように非特許文献４の方式では実現されなかった図６の（２）又は（３）のような途中経過ツリーが図１０のSTEP101で作成される可能性が高まることにより、図７、図８で示されるような、ツリー上のパケット数を最小にするための理想的ツリーを作成する可能性が高まる。
【００６５】
図１３〜図１５に本実施の形態によるパケット数削減効果及び処理負荷のシミュレーション結果を示す。
【００６６】
コンピュータシミュレーション環境で400m×400mの平面に1000台のセンサーノードを異なる２台のセンサー間の最短距離間隔を10mとしてランダムに配置した後、センサー信号の送信距離を25ｍとして送信距離内のセンサーノード間に隣接関係を作成した。結果として１センサーノードあたり平均約11.3ノードの隣接関係が作成された。この環境で、幅優先探索（breath first search）で最短経路ツリー（初期ツリー）を作成した後、その初期ツリーに対して本実施の形態を適用した結果を示す。
【００６７】
評価条件として各センサーのセンサーレポート数は1〜5の一様乱数を与えた。図１３は従来方式（非特許文献４）と提案方式（本実施の形態）との初期ツリーからのパケット減少数の比較である。グラフ横軸はデータ集約レート（S）を示している。またサブツリーの頂点ノードとして選択される上限は１０であり、ノードの移動回数の上限は１０である。つまり提案方式の従来方式からの違いは、選択されたサブツリーの頂点ノード配下で、パケット削減効果が無いノードしかない場合に、それらのノードを移動回数の上限以内で移動するかどうかの違いだけである。
【００６８】
図１３に従来方式と提案方式でノードの移動を行った結果の最短経路ツリーに対して１データ収集サイクルにおけるパケット総数の減少数を示している。すべてのデータ集約数（S）において提案方式は従来方式に比較して12%〜36%のパケット減少数の増加が得られる。
【００６９】
反面、提案方式は１移動によるパケット数減少が得られなくても、移動回数の上限までは移動するため、図１０のフローが終了するまでに多くのノード移動が行われる。その負荷を評価するために、図１４に提案方式と従来方式の総移動数を示す。すべてのSで従来方式の移動回数は平均68回であるが、提案方式は平均2821回の移動回数が要求される。ただし、図１５の総移動時間比較から提案方式の移動にかかる総時間は平均6.4秒であり、従来方式の平均1.6秒と比較して平均4.8秒のオーバヘッドしかないことがわかる。
【００７０】
ツリー作成は通常リアルタイム性は求められず、頻度は多くないので、この5秒程度のオーバヘッドは大きな問題にはならないと考えられる。
【００７１】
＜ハードウェア構成例＞
図１６に、本発明の実施の形態における経路選択装置１００のハードウェア構成例を示す。経路選択装置１００は、ＣＰＵ（Central Processing Unit）２０１等のプロセッサ、ＲＡＭ（Random Access Memory）やＲＯＭ（Read Only Memory）等のメモリ装置２０２、ハードディスク等の記憶装置２０３等から構成されたコンピュータでもよい。例えば、経路選択装置１００の機能および処理は、記憶装置２０３又はメモリ装置２０２に格納されているデータやプログラムをＣＰＵ２０１が実行することによって実現される。また、経路選択装置１００に必要な情報は、入出力インタフェース装置２０４から入力され、経路選択装置１００において求められた結果は、入出力インタフェース装置２０４から出力されてもよい。
【００７２】
＜補足＞
説明の便宜上、本発明の実施の形態に係る経路選択装置は機能的なブロック図を用いて説明しているが、本発明の実施の形態に係る経路選択装置は、ハードウェア、ソフトウェア又はそれらの組み合わせで実現されてもよい。例えば、本発明の実施の形態は、コンピュータに対して本発明の実施の形態に係る経路選択装置の機能を実現させるプログラム、コンピュータに対して本発明の実施の形態に係る方法の各手順を実行させるプログラム等により、実現されてもよい。また、各機能部が必要に応じて組み合わせて使用されてもよい。また、本発明の実施の形態に係る方法は、実施の形態に示す順序と異なる順序で実施されてもよい。
【００７３】
以上、センサーツリー上のノードのエネルギー使用量を削減するための手法について説明したが、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々の変更・応用が可能である。
【符号の説明】
【００７４】
１００  経路選択装置
１１０  ノード情報取得部
１２０  ルーティング要求部
１３０  ルート決定部
１３１  WSN認識部
１３２  初期ツリー作成部
１３３  センサーレポート数計算部
１３４  ノード移動部
１４０  WSN格納部
１５０  ツリー格納部
２０１  ＣＰＵ
２０２  メモリ装置
２０３  記憶装置
２０４  入出力インタフェース装置
【図１】
2020017828.tif 000005
【図２】
2020017828.tif 000006
【図３】
2020017828.tif 000007
【図４】
2020017828.tif 000008
【図５】
2020017828.tif 000009
【図６】
2020017828.tif 000010
【図７】
2020017828.tif 000011
【図８】
2020017828.tif 000012
【図９】
2020017828.tif 000013
【図１０】
2020017828.tif 000014
【図１１】
2020017828.tif 000015
【図１２】
2020017828.tif 000016
【図１３】
2020017828.tif 000017
【図１４】
2020017828.tif 000018
【図１５】
2020017828.tif 000019
【図１６】
2020017828.tif 000020