(57)【要約】  修正された制約を満たすスロット割当結果に関する制約の修正箇所および修正理由を出力できるタイムスロット設計装置を提供する。スロット設計装置10は、充足解が導出されない制約充足問題に関する制約群に含まれる修正対象の制約である修正制約と修正制約が修正される理由である修正理由とを出力する出力手段11と、出力された修正制約が修正された制約群を基に生成された制約充足問題の充足解を導出する導出手段12を備え、導出手段12は、充足解が導出されるまでに出力された修正制約および出力された修正理由を示す情報を出力する。
2017179540.tif 000002
【特許請求の範囲】
【請求項１】
充足解が導出されない制約充足問題に関する制約群に含まれる修正対象の制約である修正制約と前記修正制約が修正される理由である修正理由とを出力する出力手段と、
出力された前記修正制約が修正された前記制約群を基に生成された制約充足問題の充足解を導出する導出手段を備え、
前記導出手段は、
前記充足解が導出されるまでに出力された前記修正制約および出力された前記修正理由を示す情報を出力する、
タイムスロット設計装置。
【請求項２】
前記制約群に含まれる制約を作成する作成手段を備える
請求項１記載のタイムスロット設計装置。
【請求項３】
前記作成手段は、修正候補の制約を作成する修正候補制約作成手段と、修正の対象外である固定的な制約を作成する固定制約作成手段とを含む
請求項２記載のタイムスロット設計装置。
【請求項４】
前記出力手段は、前記制約群に含まれる制約を前記修正候補の制約と前記固定的な制約に分類し、出力される前記修正制約を分類された前記修正候補の制約の中から選択する
請求項３記載のタイムスロット設計装置。
【請求項５】
導出された前記充足解を用いてパケットにタイムスロットを割り当てる割当手段を備える
請求項１から請求項４のうちのいずれか１項に記載のタイムスロット設計装置。
【請求項６】
前記導出手段は、前記充足解が導出されない制約充足問題に関する前記制約群を前記出力手段に入力する  請求項１から請求項５のうちのいずれか１項に記載のタイムスロット設計装置。
【請求項７】
充足解が導出されない制約充足問題に関する制約群に含まれる修正対象の制約である修正制約と前記修正制約が修正される理由である修正理由とを出力し、
出力された前記修正制約が修正された前記制約群を基に生成された制約充足問題の充足解を導出し、
前記充足解が導出されるまでに出力された前記修正制約および出力された前記修正理由を示す情報を出力する、
タイムスロット設計方法。
【請求項８】
前記制約群に含まれる制約を作成する
請求項７記載のタイムスロット設計方法。
【請求項９】
コンピュータに、
充足解が導出されない制約充足問題に関する制約群に含まれる修正対象の制約である修正制約と前記修正制約が修正される理由である修正理由とを出力する出力処理、
出力された前記修正制約が修正された前記制約群を基に生成された制約充足問題の充足解を導出する導出処理、および
前記充足解が導出されるまでに出力された前記修正制約および出力された前記修正理由を示す情報を出力する情報出力処理
を実行させるためのタイムスロット設計プログラムを格納する記憶媒体。
【請求項１０】
前記コンピュータに、
前記制約群に含まれる制約を作成する作成処理を実行させる
請求項９記載のタイムスロット設計プログラムを格納する記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信ネットワークにおけるパケットの送信タイミングを設計するタイムスロット設計装置等に関する。
【背景技術】
【０００２】
商業衛星、科学衛星、または惑星間探査機等の人工衛星に搭載された機器（コンポーネント）間で行われるデータ通信のインタフェース、およびデータ通信のプロトコルの標準仕様に、スペースワイヤ(SpaceWire)がある。非特許文献１には、SpaceWireの内容が記載されている。【０００３】
SpaceWireが採用されている機器は、人工衛星で利用された後、観測目的等の任務（ミッション）が異なる衛星で再利用される。すなわち、SpaceWireに対応した機器が用いられると、例えば既に開発された人工衛星の機器以外の設定内容が変更されるだけで他の任務用の人工衛星が開発されるため、衛星開発の開発期間が短縮される。【０００４】
ただし、SpaceWireは、機器に採用された場合、機器のネットワーク設計の自由度が高くなる仕様である。ネットワーク設計の自由度が高いと確認作業が増えるため、機器の動作試験におけるネットワーク試験の工数が増加する。【０００５】
例えば、通信の統合試験が行われる場合を想定する。統合試験が行われる前に、ネットワーク内の経路と各制御機器に関するパケットの送信タイミングのスケジュールが設計される。設計された送信タイミングのスケジュールに従って、パケットが送信される。【０００６】
設計された送信タイミングのスケジュールに設計ミスが存在した場合、例えば最初に送信されたパケットが使用する経路と同じ経路を使用する他のパケットが、最初に送信されたパケットのリプライパケット等と衝突する。衝突の発生は、パケット不達、またはパケット遅延を引き起こす。【０００７】
上記のように、SpaceWireが採用されるとネットワーク設計の自由度が高くなるため、多くの設計の選択肢から理想的なネットワーク設計を選択するための手間が増える。すなわち、SpaceWireが採用された場合、通信の統合試験において送信タイミングのスケジュールの設計ミス等に起因する試験の手戻りが多く発生する可能性がある。【０００８】
以下の説明において、SpaceWireの仕様に対応したインタフェースを備えた機器で構成されたネットワークを、SpaceWireネットワークと呼ぶ。SpaceWireネットワークを構成する機器には、人工衛星に搭載される各種機器が含まれる。人工衛星に搭載される各種機器は、電源機器、観測機器、および姿勢機器等の衛星搭載機器である。【０００９】
また、SpaceWireネットワークを構成する機器には、地球局と通信する通信機器、および衛星内の全システムを制御するシステム制御機器も含まれる。システム制御機器は、SpaceWireの仕様に規定されたネットワーク管理機能を用いて、SpaceWireネットワークを構成する各機器を制御する。【００１０】
以下、図面を参照してSpaceWireネットワークを説明する。図２５は、SpaceWireネットワーク200の構成例を示すブロック図である。なお、図２５に示すSpaceWireネットワーク200を利用する装置が人工衛星であるとして、SpaceWireネットワーク200を説明する。【００１１】
SpaceWireネットワーク200は、システム制御機器201と、通信機器202と、電源機器203と、姿勢系制御機器204と、観測系制御機器205と、ルータ206A〜ルータ206Eと、姿勢制御機器214A〜姿勢制御機器214Bと、観測機器215A〜観測機器215Xとを含む。なお、図２５に示す各機器の数は一例である。SpaceWireネットワーク200は、各機器を１台のみ含んでもよいし、図２５に示す数以外で複数含んでもよい。【００１２】
システム制御機器201は、上記の通り、SpaceWireの仕様に規定されたネットワーク管理機能を用いてSpaceWireネットワーク200を構成する各機器を制御する機能を有する。システム制御機器201は、例えばコマンドを用いて各機器を制御する。【００１３】
通信機器202は、地球局（図示せず）または他の人工衛星（図示せず）との間で所定の通信を実行する機能を有する。電源機器203は、SpaceWireネットワーク200を構成する各機器に電力を供給する機能を有する。ルータ206Aは、システム制御機器201、通信機器202、および電源機器203を通信可能に接続する。【００１４】
姿勢系制御機器204は、姿勢制御機器214A〜姿勢制御機器214Bを制御することによって人工衛星の姿勢を制御する機能を有する。姿勢制御機器214Aは、例えば所定の向きに対する人工衛星の姿勢を変更する機能を有する。また、姿勢制御機器214Bは、例えば回転方向に対する人工衛星の姿勢を変更する機能を有する。【００１５】
図２５に示すように、姿勢系制御機器204と、姿勢制御機器214Aと、姿勢制御機器214Bとで姿勢系が構成されている。ルータ206Dは、姿勢系制御機器204、姿勢制御機器214A、および姿勢制御機器214Bを通信可能に接続する。【００１６】
観測系制御機器205は、観測機器215A〜観測機器215Xを制御することによって各種の観測を実行する機能を有する。観測機器215A〜観測機器215Xは、それぞれ設定された内容の観測を実行する機能を有する。【００１７】
図２５に示すように、観測系制御機器205と、観測機器215A〜観測機器215Xとで観測系が構成されている。ルータ206Eは、観測系制御機器205、および観測機器215A〜観測機器215Xを通信可能に接続する。【００１８】
ルータ206Bは、ルータ206Aと姿勢系を通信可能に接続する。また、ルータ206Cは、ルータ206A、ルータ206B、姿勢系、および観測系を通信可能に接続する。【００１９】
SpaceWireの仕様に従う通信では、各機器のアドレスを示す情報がパケットヘッダに記載されたパケットが送受信されるソースルーティング方式が主に利用される。ソースルーティング方式が利用された通信をパスアドレッシング通信と呼ぶ。【００２０】
パスアドレッシング通信では、始点の機器のアドレスおよび終点の機器のアドレスに加えて、パケットを中継する機器のアドレスも指定される。なお、始点の機器は、送信元または送信者がパケット送信に使用する機器である。また、終点の機器は、宛先または受信者がパケット受信に使用する機器である。【００２１】
なお、パスアドレッシング通信で指定されるアドレスは、通信ネットワークにおける位置を示す情報である。通信ネットワークにおける位置は、例えばポート番号で指定される。すなわち、通信ネットワークにおけるパケットが経由する位置が指定されるため、パスアドレッシング通信が実行される際、例えばTCP/IP(Transmission Control Protocol/Internet Protocol)で利用されるルーティングテーブルは不要である。【００２２】
以下、パスアドレッシング通信で用いられるアドレスを、パスアドレスと呼ぶ。パスアドレッシング通信において、経路変更は、パケットヘッダに記載されているパスアドレスが変更されることによって実行される。【００２３】
以下、図面を参照してパスアドレッシング通信を説明する。図２６は、パスアドレッシング通信の例を示す説明図である。図２６に示すシステムは、搭載機器210A〜搭載機器210Bと、ルータ206X〜ルータ206Yとを含む。すなわち、図２６に示すシステムは、２台の搭載機器と、２台のルータとを含む。また、図２６に示す搭載機器210Aは、２台のルータを介して搭載機器210Bと通信可能に接続されている。【００２４】
図２６に示すルータ206Xは、搭載機器210Aに接続されているパスアドレスが「１」のポートと、ルータ206Yに接続されているパスアドレスが「２」のポートとを含む。また、図２６に示すルータ206Yは、ルータ206Xに接続されているパスアドレスが「３」のポートと、搭載機器210Bに接続されているパスアドレスが「４」のポートとを含む。【００２５】
以下、パスアドレスが「１」のポートをポート１、パスアドレスが「２」のポートをポート２、パスアドレスが「３」のポートをポート３、パスアドレスが「４」のポートをポート４とそれぞれ呼ぶ。【００２６】
各搭載機器は、他の搭載機器にパケットを送信する場合、パケットが通過する中継機器（すなわち、ルータ206Xおよびルータ206Y）内の各ポートに割り当てられたアドレス情報であるパスアドレスを、送信するパケットのパケットヘッダに記載する。【００２７】
また、パケットを受信した中継機器（すなわち、ルータ206Xおよびルータ206Y）は、パケットヘッダに記載されている先頭のパスアドレスに対応するポートから、次の機器へパケットを送信する。【００２８】
ただし、各ルータは、対象のポートからパケットを送信する前に、対象のポートのパスアドレスであるパケットヘッダに記載されている先頭のパスアドレスを削除する。すなわち、パスアドレッシング通信では、パケットがルータを通過するごとにパケットヘッダに記載されている先頭のパスアドレスが削除される。【００２９】
例えば、図２６に示す搭載機器210Aが搭載機器210Bにパケットを送信する場合、搭載機器210Aは、送信するパケットのパケットヘッダに、パスアドレスとして［２−４］を記載する。パケットヘッダに記載されたパスアドレス［２−４］は、送信されるパケットが、パスアドレスが「２」のポートと、パスアドレスが「４」のポートを順に経由することを示す。【００３０】
すなわち、パケットヘッダに記載されたパスアドレス［ｐ−ｑ］は、「ｐ」が先頭のパスアドレスであること、および「ｑ」が末尾のパスアドレスであることをそれぞれ示す。
なお、パケットヘッダに記載されるパスアドレスの数は、２つに限られない。【００３１】
例えば、３つのパスアドレスが記載される場合、パケットヘッダには、［ｐ−ｑ−ｒ］の形式でパスアドレスが記載される。パスアドレス［ｐ−ｑ−ｒ］は、「ｐ」が先頭のパスアドレスであること、「ｑ」が中間のパスアドレスであること、および「ｒ」が末尾のパスアドレスであることをそれぞれ示す。【００３２】
搭載機器210Aが搭載機器210Bにパケットを送信した時のシステムの動作をより具体的に説明する。まず、搭載機器210Aは、パケットヘッダにパスアドレスとして［２−４］を記載する。次いで、搭載機器210Aは、パケットをルータ206Xに送信する。【００３３】
パケットをルータ206Xに送信する際、搭載機器210Aは、送信先のルータ206Xのポートを指定しなくてよい。その理由は、図２６に示すように搭載機器210Aはルータ206Xのポート１のみに接続されているため、送信されたパケットは、必然的にルータ206Xのポート１に到着するからである。【００３４】
次いで、ルータ206Xは、受信されたパケットのパケットヘッダに記載されている先頭のパスアドレスに対応するポートからパケットを送信する。パケットヘッダにパスアドレスとして［２−４］が記載されているため、先頭のパスアドレスに対応するポートは、ポート２である。【００３５】
ただし、パケットを送信する際、ルータ206Xは、パケットヘッダに記載されている先頭のパスアドレス（すなわち、パスアドレス「２」）を削除する。先頭のパスアドレスが削除されると、パケットヘッダに記載されているパスアドレスは［４］になる。【００３６】
すなわち、ルータ206Xは、パケットを通過させる際、パケットヘッダに記載されている先頭のパスアドレスであるパスアドレス「２」を削除し、削除されたパスアドレスに対応するポートであるポート２からパケットを送信する。【００３７】
ルータ206Xのポート２は、ルータ206Yのポート３に接続されている。よって、ルータ206Xから送信されたパケットは、ルータ206Yに受信される。次いで、ルータ206Yは、受信されたパケットのパケットヘッダに記載されている先頭のパスアドレスに対応するポートからパケットを送信する。パケットヘッダにパスアドレスとして［４］が記載されているため、先頭のパスアドレスに対応するポートは、ポート４である。【００３８】
ただし、パケットを送信する際、ルータ206Yは、パケットヘッダに記載されている先頭のパスアドレス（すなわち、パスアドレス「４」）を削除する。先頭のパスアドレスが削除されると、パケットヘッダに記載されているパスアドレスは空（空集合）になる。【００３９】
すなわち、ルータ206Yは、パケットを通過させる際、パケットヘッダに記載されている先頭のパスアドレスであるパスアドレス「４」を削除し、削除されたパスアドレスに対応するポートであるポート４からパケットを送信する。【００４０】
ルータ206Yのポート４は、搭載機器210Bに接続されている。よって、ルータ206Xから送信されたパスアドレスが空のパケットは、搭載機器210Bに受信される。搭載機器210Bは、パスアドレスが空のパケットを転送不要のパケット、すなわち自機器宛のパケットであると判断する。上記のように、搭載機器210Bは、自機器宛のパケットを受信する。【００４１】
以上、パケットの宛先である搭載機器210Bに到着するまでに経由するルータの送信ポートのパスアドレスをパケットヘッダに記載することによって、搭載機器210Aは、パケットを搭載機器210Bに送信できる。同様に、搭載機器210Aにパケットを送信する場合、搭載機器210Bは、図２６に示すように送信対象のパケットのパケットヘッダにパスアドレス［３−１］を記載すればよい。【００４２】
また、SpaceWireでは、タイムスロットと呼ばれる15.625msごとの時間間隔が定義されている。すなわち、６４個のタイムスロットが１秒に相当する。【００４３】
SpaceWireでは、通信対象のパケットを所定のタイムスロットに割り当てることによって、所定の周期または所定のタイミングでパケットが送信されるように送信タイミングを制御する手法が採用されている。なお、所定の周期は、例えば１秒である。SpaceWireで定義されているタイムスロットを用いて送信タイミングを制御する手法は、非特許文献２に記載されている。【００４４】
SpaceWireの仕様に対応した制御機器は、送信されるパケットが割り当てられたタイムスロットの一覧表を保持する。保持されているタイムスロットの一覧表に従って、制御機器は、機器間でパケットが送受信される通信を実行する。【００４５】
また、非特許文献３には、SpaceWireネットワーク（特に、衛星内ネットワーク）で使用されるスケジューリングツールが記載されている。非特許文献３に記載されているスケジューリングツールは、SpaceWireネットワークのトポロジ情報、および通信要求情報を用いて、送信元の機器から宛先の機器までにパケットが経由する位置のパスアドレスを算出する。【００４６】
さらに、非特許文献３に記載されているスケジューリングツールは、パケットの通信に用いられるタイムスロットにパケットを割り当てる。なお、非特許文献３に記載されているトポロジ情報の形式、および通信要求情報の形式は、XML(Extensible Markup Language)形式である。【００４７】
また、非特許文献４には、制約プログラムを利用して衛星内ネットワークのスケジューリングを行う方法が記載されている。非特許文献４に記載されている方法は、SpaceWireネットワーク内の機器間の結線を示す情報や、各タイムスロットにおける帯域幅の使用率の上限等を全て制約式化する。【００４８】
制約式化することによって、非特許文献４に記載されている方法は、経路計算およびタイムスロット割当を、制約充足問題の解決に変換する。非特許文献４に記載されている方法は、変換された制約充足問題を解決し、導出された充足解を用いて衛星内ネットワークのスケジューリングを行う。【００４９】
また、制約充足解は、例えば既存の制約充足ソルバで探索される。探索された制約充足解が解析されると、送信を要求されたパケットが通過するノードの情報やタイムスロット割当情報が求められる。【００５０】
また、非特許文献５には、厳し過ぎる制約を緩和して充足解を探索する方法が記載されている。一般的に、制約充足問題には充足解が存在しない場合がある。非特許文献５に記載されている方法は、制約充足問題に充足解が存在しない場合、全制約群のうち矛盾が存在している部分制約群を抽出し、矛盾が存在しなくなるように全制約群から選択された制約を適切に削除する。選択された制約が適切に削除されると、元の制約充足問題が修正され、充足解が得られる。【００５１】
元の全制約群に含まれる矛盾が存在している部分制約群は、Unsatisfiable Core（以下、Unsat Coreと呼ぶ。）と呼ばれる。非特許文献５には、矛盾を解消するための削除対象の制約が１つになるようなUnsat Coreを高速に算出するアルゴリズムが記載されている。
【先行技術文献】
【非特許文献】
【００５２】
【非特許文献１】SpaceWire Standard ECSS-E-ST-50-12C (European Cooperation for Space Standardization (ECSS)), July 21, 2008.
【非特許文献２】Steve Parkes, Albert Ferrer, Stuart Mills, and Alex Mason, "SpaceWire-D: Deterministic Data Delivery with SpaceWire", Proceedings of International SpaceWire Conference 2010, February 2010.
【非特許文献３】高田光隆, 高田広章, 湯浅孝行他, "SpaceWireのリアルタイム性を保証するソフトウェアプラットフォームの開発", 第57回宇宙科学技術連合講演会講演集, pp.6, 2013-10-09.
【非特許文献４】Gibson, David, Steve Parkes, and Karen Petrie, "Modeling Deterministic Spacecraft Networks with Constraint Programming", CP Doctoral Program 2013: 49.
【非特許文献５】Mencia, Carlos, and Joao Marques-Silva, "Efficient Relaxations of Over-constrained CSPs", Tools with Artificial Intelligence (ICTAI), 2014 IEEE 26th International Conference on, IEEE, 2014.
【発明の概要】
【発明が解決しようとする課題】
【００５３】
非特許文献３に記載されているスケジューリングツールは、焼き鈍し法で最適化問題を解くことによってタイムスロットを割り当てる。しかし、最適化問題を解くことによってタイムスロットを割り当てる場合、スケジューリングツールは、制約を満たさないスロット割当結果も算出してしまう。【００５４】
また、非特許文献３に記載されているスケジューリングツールが制約を満たさないスロット割当結果を算出しても、スケジューリングツールの使用者は、算出されたスロット割当結果が制約を満たさないことを結果の内容から把握できない。【００５５】
非特許文献１および非特許文献２には、SpaceWireの仕様が記載されている。しかし、非特許文献１および非特許文献２には、設計時に非特許文献３に記載されているスケジューリングツールが使用された時に生じる可能性がある上記の問題点の解決方法は記載されていない。【００５６】
また、非特許文献４に記載されている方法は、制約プログラムを実行することによってタイムスロット割当を行うので、制約を満たすスロット割当結果を算出できる。すなわち、非特許文献４に記載されている方法が使用されると、非特許文献３に記載されているスケジューリングツールにおける上記の問題点が解決される。【００５７】
しかし、制約充足解が存在しない場合、スロット割当結果は算出されない。また、非特許文献４に記載されている方法が使用された場合、設計者は、スロット割当結果が算出されない理由を知ることができない。【００５８】
制約充足解が存在しない場合、設計者は、通信要求の設計内容を見直し、再度タイムスロット割当を行う。しかし、通信要求の設計内容を見直す際、非特許文献４に記載されている方法による出力結果を参照しても、設計者は、通信要求の設計内容のどの項目を修正すれば充足解が得られるかが分からない。【００５９】
非特許文献５に記載されている方法は、Unsat Coreを算出することによって修正を要する制約候補を設計者に提示できる。すなわち、非特許文献５に記載されている方法が使用されると、非特許文献４に記載されている方法における上記の問題点が解決される。しかし、非特許文献５に記載されている方法は、修正対象の制約を選択したり、修正対象の制約の選択理由を提示したりできない。【００６０】
また、選択される修正箇所や修正理由として提示される内容は、タイムスロット割当の実行時に考慮を要する制約の内容に依存する。しかし、非特許文献５には、タイムスロット割当の実行時に考慮される制約の内容が記載されていない。具体的な修正箇所および修正理由が提示されるためには、タイムスロット割当の実行時に考慮される制約の内容が具体的であることが求められる。【００６１】
そこで、本発明は、上述した課題を解決する、修正された制約を満たすスロット割当結果に関する制約の修正箇所および修正理由を出力できるタイムスロット設計装置、タイムスロット設計方法およびタイムスロット設計プログラムを提供することを目的とする。
【課題を解決するための手段】
【００６２】
本発明によるタイムスロット設計装置の一態様は、充足解が導出されない制約充足問題に関する制約群に含まれる修正対象の制約である修正制約と修正制約が修正される理由である修正理由とを出力する出力手段と、出力された修正制約が修正された制約群を基に生成された制約充足問題の充足解を導出する導出手段を備え、導出手段は、充足解が導出されるまでに出力された修正制約および出力された修正理由を示す情報を出力する。【００６３】
本発明によるタイムスロット設計方法の一態様は、充足解が導出されない制約充足問題に関する制約群に含まれる修正対象の制約である修正制約と修正制約が修正される理由である修正理由とを出力し、出力された修正制約が修正された制約群を基に生成された制約充足問題の充足解を導出し、充足解が導出されるまでに出力された修正制約および出力された修正理由を示す情報を出力する。【００６４】
本発明による記憶媒体に格納されたタイムスロット設計プログラムの一態様は、コンピュータに、充足解が導出されない制約充足問題に関する制約群に含まれる修正対象の制約である修正制約と修正制約が修正される理由である修正理由とを出力する出力処理、出力された修正制約が修正された制約群を基に生成された制約充足問題の充足解を導出する導出処理、および充足解が導出されるまでに出力された修正制約および出力された修正理由を示す情報を出力する情報出力処理を実行させる。
【発明の効果】
【００６５】
本発明によれば、修正された制約を満たすスロット割当結果に関する制約の修正箇所および修正理由を出力できる。
【図面の簡単な説明】
【００６６】
【図１】本発明による送信タイミングスケジューラ100の第１の実施形態の構成例を示すブロック図である。
【図２】制約作成部110の構成例を示すブロック図である。
【図３】通信要求情報リストの例を示す説明図である。
【図４】トポロジ情報に含まれるパスアドレス情報リストの例を示す説明図である。
【図５】トポロジ情報に含まれる結線情報リストの例を示す説明図である。
【図６】SpaceWireネットワーク200の構成例の一部を示すブロック図である。
【図７】制約充足問題解決部130の構成例を示すブロック図である。
【図８】充足解情報の例を示す説明図である。
【図９】修正箇所情報の例を示す説明図である。
【図１０】スケジュール結果情報の例を示す説明図である。
【図１１】第１の実施形態の送信タイミングスケジューラ100による設計処理の全体動作を示すフローチャートである。
【図１２】第１の実施形態の制約作成部110による補足情報付き制約情報作成処理の動作を示すフローチャートである。
【図１３】第１の実施形態の制約充足問題解決部130による充足解探索処理の動作を示すフローチャートである。
【図１４】第１の実施形態の充足解解析部140による充足解解析処理の動作を示すフローチャートである。
【図１５】第１の実施形態のUnsat Core解析部132によるUnsat Core解析処理の動作を示すフローチャートである。
【図１６】制約作成部110の第２の実施形態の構成例を示すブロック図である。
【図１７】スロット制限定義情報リストの例を示す説明図である。
【図１８】依存関係定義情報リストの例を示す説明図である。
【図１９】第２の実施形態の制約作成部110による補足情報付き制約情報作成処理の動作を示すフローチャートである。
【図２０】第２の実施形態の送信制約作成部113による送信制約作成処理の動作を示すフローチャートである。
【図２１】第２の実施形態の帯域制約作成部114による帯域制約作成処理の動作を示すフローチャートである。
【図２２】第２の実施形態のスロット制限制約作成部115によるスロット制限制約作成処理の動作を示すフローチャートである。
【図２３】第２の実施形態の依存関係制約作成部116による依存関係制約作成処理の動作を示すフローチャートである。
【図２４】本発明によるタイムスロット設計装置の概要を示すブロック図である。
【図２５】SpaceWireネットワーク200の構成例を示すブロック図である。
【図２６】パスアドレッシング通信の例を示す説明図である。
【発明を実施するための形態】
【００６７】
以下、本発明の実施形態を、図面を参照して説明する。各図面は、本発明の実施形態を示す。なお、本発明の実施形態は、各図面に示す内容に限られない。また、各図面に示す同一の構成要素には、同じ番号が付されている。
【００６８】
＜第１の実施形態＞
［構成の説明］
次に、本発明の第１の実施形態を、図面を参照して説明する。図１は、本発明による送信タイミングスケジューラ100の第１の実施形態の構成例を示すブロック図である。
【００６９】
本実施形態の送信タイミングスケジューラ100は、使用されると人為的なミスの発生が防止され信頼性の高い通信が実行されるスケジュール情報を作成する。また、本実施形態の送信タイミングスケジューラ100が使用されると、設計者は、通信要求の設計内容を迅速に見直すことができる。
【００７０】
図１に示す送信タイミングスケジューラ100は、通信ネットワーク内の装置に関する設計内容を作成する。具体的には、送信タイミングスケジューラ100は、図２５に示すSpaceWireネットワーク200等で使用されるパケット送信タイミングのスケジュールを示すタイムスロットテーブルを作成する。また、本実施形態の送信タイミングスケジューラ100は、タイムスロットテーブルと共に制約群内の修正箇所も提示する。
【００７１】
図１に示すように、本実施形態の送信タイミングスケジューラ100は、制約作成部110と、制約情報記憶部120と、制約充足問題解決部130と、充足解解析部140とを備える。
【００７２】
また、図１に示すように、送信タイミングスケジューラ100には、通信要求情報と、トポロジ情報と、制約定義情報とが入力される。なお、制約定義情報は、入力されなくてもよい。
【００７３】
なお、送信タイミングスケジューラ100に通信要求情報、トポロジ情報、および制約定義情報を入力する手段は、どのような手段でもよい。例えば、送信タイミングスケジューラ100の利用者が入力装置（図示せず）に各情報を入力し、入力装置が入力された情報を送信タイミングスケジューラ100に送信してもよい。または、利用者が送信タイミングスケジューラ100を直接操作して、各情報を入力してもよい。
【００７４】
図１に示すように、送信タイミングスケジューラ100の制約作成部110は、補足情報付き制約情報を作成する機能を有する。制約作成部110は、作成された補足情報付き制約情報を制約情報記憶部120に記憶する。
【００７５】
また、図１に示すように、制約充足問題解決部130は、制約情報記憶部120に記憶されている補足情報付き制約情報を基に充足解情報と修正箇所情報を生成する機能を有する。制約充足問題解決部130は、生成された充足解情報を充足解解析部140に入力する。
【００７６】
また、図１に示すように、充足解解析部140は、入力された充足解情報を用いてスケジューリング結果情報を生成する。スケジューリング結果情報は、タイムスロット割当結果を示す。最終的に、送信タイミングスケジューラ100は、スケジューリング結果情報と修正箇所情報とを出力する。
【００７７】
出力されたスケジューリング結果情報が適切に入力されると、衛星制御機器は、入力された情報が示すタイムスロット割当結果に従って動作する。また、修正箇所情報は、修正箇所、および修正箇所に対する修正理由を含む修正コメントを示す。
【００７８】
すなわち、送信タイミングスケジューラ100の利用者は、出力された修正箇所情報を参照して、入力された通信要求情報を修正できる。利用者は、修正された通信要求情報を用いて、送信タイミングスケジューラ100にタイムスロット割当を再度実行させることができる。
【００７９】
以下、送信タイミングスケジューラ100に含まれる各構成要素を、図面を参照して説明する。最初に、制約作成部110を説明する。
【００８０】
図２は、制約作成部110の構成例を示すブロック図である。図２に示すように、本実施形態の制約作成部110は、修正候補制約作成部111と、背景制約作成部112とを含む。
【００８１】
図２に示すように、制約作成部110の修正候補制約作成部111は、通信要求情報とトポロジ情報とを基に、制約式、「修正候補」タグ、および修正コメントを含む補足情報付き制約情報を作成する。すなわち、修正候補制約作成部111が作成する補足情報付き制約情報は、修正候補制約を示す。修正候補制約作成部111は、作成された補足情報付き制約情報を、制約情報記憶部120に記憶する。
【００８２】
また、図２に示すように、制約作成部110の背景制約作成部112は、通信要求情報とトポロジ情報とを基に、制約式、「背景」タグ、および修正理由コメントを含む補足情報付き制約情報を作成する。すなわち、背景制約作成部112が作成する補足情報付き制約情報は、背景制約を示す。背景制約作成部112は、作成された補足情報付き制約情報を、制約情報記憶部120に記憶する。
【００８３】
なお、修正候補制約作成部111および背景制約作成部112は、制約定義情報も用いて補足情報付き制約情報を作成してもよい。本実施形態では、修正候補制約作成部111および背景制約作成部112が制約定義情報を使用せずに補足情報付き制約情報を作成する例を説明する。
【００８４】
修正候補制約作成部111は、修正候補制約作成部111で作成された修正候補制約群に含まれる制約のみが考慮された制約充足問題に、必ず充足解が存在するように修正候補制約を作成する。また、背景制約作成部112は、背景制約作成部112で作成された背景制約群に含まれる制約のみが考慮された制約充足問題に、必ず充足解が存在するように背景制約を作成する。
【００８５】
上記のように修正候補制約群および背景制約群が作成されると、全ての制約群が考慮された制約充足問題に充足解が存在しない場合、Unsat Coreに必ず修正候補制約群に含まれる制約と背景制約群に含まれる制約の両方が含まれる。
【００８６】
本実施形態の送信タイミングスケジューラ100は、Unsat Coreに必ず修正候補制約群に含まれる制約と背景制約群に含まれる制約の両方が含まれる性質を利用し、背景制約を用いて修正対象の制約の選択と修正の理由付けを行う。もし、Unsat Coreに修正候補制約群に含まれる制約のみが含まれる場合、送信タイミングスケジューラ100は、背景制約群に含まれる制約がないため修正対象の制約に対する修正の理由付けを行うことができない。
【００８７】
また、Unsat Coreに背景制約群に含まれる制約のみが含まれる場合、修正候補制約群に含まれる制約自体がないため、送信タイミングスケジューラ100が制約群を修正できないことは自明である。上記の理由により、修正対象の制約の選択と修正の理由付けが行われるためには、Unsat Coreに修正候補制約群に含まれる制約と背景制約群に含まれる制約の両方が含まれることが求められる。
【００８８】
以下、制約作成部110に入力される通信要求情報とトポロジ情報を説明する。最初に、通信要求情報を説明する。
【００８９】
通信要求情報は、SpaceWireネットワークに含まれる衛星制御機器が送信を要求したパケットの内容を示す情報である。通信要求情報は、試験対象の通信に関連する経路情報、および試験に用いられるプロトコルの種類やデータサイズ等の通信に関する具体的な情報を示す。すなわち、通信要求情報は、ネットワーク設計者の設計意図に合わせて作成される。
【００９０】
図３は、通信要求情報リストの例を示す説明図である。図３に示す通信要求情報リストは、複数の通信要求情報で構成されている。また、図３に示すように、通信要求情報は、通信要求ID(Identifier)と、プロトコルと、送信元と、宛先と、パスアドレスと、コマンドと、リプライと、リプライパスアドレスと、データサイズと、通信間隔とで構成されている。
【００９１】
通信要求IDは、通信要求情報を識別する識別子である。プロトコルは、通信要求IDが示す要求された通信で使用されるプロトコルである。
【００９２】
図３に示すプロトコルには、「RMAP」と記載されている。RMAP(Remote Memory Access Protocol)は、SpaceWireネットワークに接続されている機器がデータを読み書きする際に使用する機能が規定されているプロトコルである（例えば、非特許文献１を参照）。また、RMAPアドレスは、RMAPでアクセスされる対象機器のメモリアドレスである。非特許文献１には、通信先の機器においてアクセスされるメモリアドレスが規定されている。
【００９３】
送信元は、パケットの送信元（始点）である機器の名称、または機器の識別子を示す。
また、宛先は、パケットの宛先（終点）である機器の名称、または機器の識別子を示す。
【００９４】
パスアドレスは、通信要求IDが示す要求されたパスアドレッシング通信で用いられるアドレスである。上記の通り、パスアドレスは、送信対象のパケットのパケットヘッダに記載される。また、本実施形態のパスアドレスの形式は、図２６に示すシステムで使用されるパスアドレスの形式と同様である。
【００９５】
コマンドは、送信対象のパケットに含まれるコマンドの種類を示す。コマンドの種類として、例えばコマンド名が示される。本実施形態の通信要求情報にコマンドが含まれる理由は、試験で使用される情報の種類のうち、特にコマンドの種類が多いためである。なお、通信要求情報には、コマンド以外の試験に要する情報が含まれてもよい。
【００９６】
リプライ（応答）は、送信されたパケットに対するリプライの有無を示す。また、リプライパスアドレスは、リプライパケットの通信で用いられたパスアドレスである。
【００９７】
データサイズは、通信要求IDが示す要求された通信で用いられるパケットのデータサイズである。図３に示すデータサイズの単位はbyteである。なお、データサイズには、byte以外の単位での値が記載されてもよい。
【００９８】
通信間隔は、通信要求IDが示す要求された通信が実行される間隔である。通信間隔には、タイムスロット数が記載されている。例えば、通信要求IDが「１」の通信は、タイムスロット２つ分の時間間隔を空けて繰り返し実行される。
【００９９】
なお、通信要求情報の形式は、図３に示す形式に限られない。例えば、通信要求情報の形式は、SpaceWireネットワークに含まれる各制御機器に入出力されるコマンドで構成されたコマンドリスト形式でもよい。
【０１００】
次に、トポロジ情報を説明する。トポロジ情報には、制御部、ルータ、姿勢機器、および観測機器等の、SpaceWireネットワークに含まれる機器の情報と、機器の接続に関する情報である結線（リンク）情報が含まれる。結線情報は、ルータを含む各機器のポートが接続されている機器のポートを示す情報である。
【０１０１】
なお、トポロジ情報には、SpaceWireネットワークに含まれる機器に関する結線情報以外の情報が含まれてもよい。例えば、トポロジ情報には、SpaceWireネットワークに含まれる機器の性能や機能を示す情報が含まれてもよい。
【０１０２】
本実施形態のトポロジ情報には、パスアドレスに関するパスアドレス情報と、結線に関する結線情報とが含まれる。図４は、トポロジ情報に含まれるパスアドレス情報リストの例を示す説明図である。図４に示すパスアドレス情報リストは、複数のパスアドレス情報で構成されている。また、図５は、トポロジ情報に含まれる結線情報リストの例を示す説明図である。図５に示す結線情報リストは、複数の結線情報で構成されている。
【０１０３】
なお、図４に示すパスアドレス情報および図５に示す結線情報は、図６に示すSpaceWireネットワーク200に含まれる各ルータのポートのポート番号（パスアドレス）が用いられて作成された情報である。図６は、SpaceWireネットワーク200の構成例の一部を示すブロック図である。
【０１０４】
図６に示す機器とルータとを結ぶ線、およびルータ同士を結ぶ線がリンクを表す。なお、図６に示すリンク以外にも、SpaceWireネットワーク200にはリンクが含まれている。
【０１０５】
また、図６は、図２５に示すSpaceWireネットワーク200に含まれるルータ206A〜ルータ206Cのポートのパスアドレスを示す。具体的には、図６に示す各リンクに接続されている各ルータ内の矩形が、ポートを表す。また、各ルータ内の矩形内に記載されている数字が、ポート番号（パスアドレス）である。例えば、システム制御機器201のポートとリンクを介して接続されているルータ206Aのポートのパスアドレスは「１２」である。
【０１０６】
図４に示すパスアドレス情報は、各機器の機器名と、ポートと、最大遅延時間とで構成されている。機器名は、SpaceWireネットワーク200に含まれる機器の名称である。機器名には、具体的な名称が記載されてもよいし、識別子等の機器を識別可能な情報が記載されてもよい。
【０１０７】
ポートは、機器名が示す機器にパケットが送信される際に経路として使用されるポートのポート番号（パスアドレス）を示す。例えば、システム制御機器201にパケットが送信される場合、パスアドレスが「１」のポートが経路として使用される。
【０１０８】
最大遅延時間は、パスアドレスが示すポートを経由して機器名が示す機器にパケットが到達するまでに要する最大時間である。図４に示す最大遅延時間の単位は秒である。なお、最大遅延時間には、秒以外の単位での値が記載されてもよい。
【０１０９】
また、図５に示す結線情報は、リンクIDと、接続元機器名と、接続元ポートと、接続先機器名と、接続先ポートと、通信容量とで構成されている。リンクIDは、リンクを識別する識別子である。
【０１１０】
接続元機器名は、リンクIDが示すリンクが接続された接続元の機器の名称、または接続元の機器のIDを示す。また、接続元ポートは、接続元機器名が示す機器の、リンクが接続されたポートのポート番号を示す。
【０１１１】
接続先機器名は、リンクIDが示すリンクが接続された接続先の機器の名称、または接続先の機器のIDを示す。また、接続先ポートは、接続先機器名が示す機器の、リンクが接続されたポートのポート番号を示す。
【０１１２】
なお、図５に示す結線情報において、接続元機器名が示す情報および接続元ポートが示す情報と、接続先機器名が示す情報および接続先ポートが示す情報は入れ替えられてもよい。例えば、図５に示すリンクIDが「１」の結線情報を参照すると、リンクIDが「１」のリンクを介して、システム制御機器201からルータ206Aへの通信と、ルータ206Aからシステム制御機器201への通信の両方の通信が実行されることが分かる。
【０１１３】
通信容量は、リンクIDが示すリンクの通信容量である。通信容量を示す値として、例えば通信帯域幅の値が記載される。図５に示す通信容量の単位はMbit/秒である。なお、通信容量には、Mbit/秒以外の単位での値が記載されてもよい。
【０１１４】
次に、制約充足問題解決部130を説明する。図７は、制約充足問題解決部130の構成例を示すブロック図である。図７に示すように、本実施形態の制約充足問題解決部130は、問題解決部131と、Unsat Core解析部132とを含む。
【０１１５】
制約充足問題解決部130の問題解決部131は、制約情報記憶部120に記憶されている情報が示す全制約を満たす解である充足解を求める機能を有する。
【０１１６】
制約充足問題を解いて充足解が求められた場合、問題解決部131は、充足解の導出時に変数に割り当てられた値を示す情報を含む充足解情報と、充足解が求められるまでに修正された制約および修正コメントを示す情報を含む修正箇所情報とを出力する。
【０１１７】
制約充足問題を解いても充足解が求められなかった場合、問題解決部131は、Unsat Coreを生成する。次いで、問題解決部131は、生成されたUnsat CoreをUnsat Core解析部132に入力する。
【０１１８】
Unsat Core解析部132は、補足情報付き制約情報を参照して入力されたUnsat Coreを解析する機能を有する。Unsat Coreが解析された情報を用いて、Unsat Core解析部132は、「修正候補」タグを含む補足情報付き制約情報が示す制約群の中から修正対象の制約を選択し、修正コメントを生成する。
【０１１９】
一般的に、１つのUnsat Coreには、制約情報記憶部120に記憶されている情報が示す全制約の中の、矛盾が存在する制約の一部が含まれている。すなわち、全制約から修正対象の制約が除かれても、問題解決部131は、充足解を求めることができない場合がある。制約充足問題解決部130では、充足解が求められるまで、問題解決部131による充足解の探索と、Unsat Core解析部132による修正対象の制約の導出が繰り返し実行される。
【０１２０】
以下、制約充足問題解決部130に含まれる各構成要素を、図７を参照してより具体的に説明する。最初に、問題解決部131を説明する。
【０１２１】
問題解決部131は、与えられた制約群を全て充足する解である充足解を探索する。問題解決部131に最初に与えられる制約群は、制約情報記憶部120に記憶されている情報が示す全ての制約で構成された制約群である。
【０１２２】
２回目以降の充足解の探索で問題解決部131に与えられる制約群は、最初に与えられた制約群から、Unsat Core解析部132から入力された修正対象の制約が除かれた全ての制約で構成された制約群である。探索により充足解が求められた場合、問題解決部131は、充足解情報および修正箇所情報を出力する。
【０１２３】
次に、Unsat Core解析部132を説明する。Unsat Core解析部132には、問題解決部131からUnsat Coreが入力される。Unsat Core解析部132は、入力されたUnsat Coreに含まれる制約を修正候補制約と背景制約に分類する。次いで、Unsat Core解析部132は、分類された修正候補制約の中から修正対象の制約を選択し、選択された制約を問題解決部131に入力する。
【０１２４】
以下、問題解決部131が出力する充足解情報と修正箇所情報を説明する。最初に、充足解情報を説明する。
【０１２５】
図８は、充足解情報の例を示す説明図である。図８に示すように、充足解情報は、変数を示す変数情報で構成されている。また、変数情報は、変数名と、変数の値とで構成されている。
【０１２６】
本実施形態の変数名は、「スロットｎ；パケットｍ」の形式で定義される。なお、ｎはタイムスロット番号であり、ｍはパケットに関する通信要求IDまたはパケット番号である。また、本実施形態の変数の値は、０と１のいずれかである。
【０１２７】
例えば、変数名「スロットｎ；パケットｍ」の変数の値が１である場合、通信要求IDがｍの通信要求に関するパケットにスロット番号ｎのタイムスロットが割り当てられる。また、例えば、変数名「スロットｎ；パケットｍ」の変数の値が０である場合、通信要求IDがｍの通信要求に関するパケットにスロット番号ｎのタイムスロットが割り当てられない。
【０１２８】
次に、修正箇所情報を説明する。図９は、修正箇所情報の例を示す説明図である。図９に示すように、修正箇所情報は、修正された制約を示す。また、図９に示すように、修正箇所情報は、修正通信制約IDと、修正コメントとで構成される。修正通信制約IDは、修正された制約を識別する識別子である。
【０１２９】
次に、充足解解析部140を説明する。充足解解析部140は、入力された充足解情報に基づいて、スケジュール結果情報を生成する機能を有する。図１０は、スケジュール結果情報の例を示す説明図である。
【０１３０】
図１０に示すように、スケジュール結果情報は、通信要求IDと、タイムスロットとで構成されている。通信要求IDは、通信要求情報で定義された情報である。スケジュール結果情報には、通信要求IDに対して割り当てられたタイムスロットの番号が記載されている。
充足解解析部140は、充足解情報に記載されている変数の値を解釈することによって、スケジュール結果情報が示すタイムスロット割当結果を得る。
【０１３１】
［動作の説明］
以下、本実施形態の送信タイミングスケジューラ100の動作を図１１〜図１５を参照して説明する。図１１は、第１の実施形態の送信タイミングスケジューラ100による設計処理の全体動作を示すフローチャートである。
【０１３２】
送信タイミングスケジューラ100に、通信要求情報とトポロジ情報とが入力される。なお、送信タイミングスケジューラ100に、制約定義情報が入力されてもよい（ステップS110）。
【０１３３】
次いで、制約作成部110は、入力された通信要求情報とトポロジ情報を基に補足情報付き制約情報を作成する（ステップS120）。制約作成部110は、作成された補足情報付き制約情報を制約情報記憶部120に記憶する。
【０１３４】
次いで、制約充足問題解決部130は、制約情報記憶部120に記憶されている情報を用いて、充足解情報および修正箇所情報を作成する（ステップS130）。制約充足問題解決部130は、作成された充足解情報を充足解解析部140に入力する。
【０１３５】
次いで、充足解解析部140は、入力された充足解情報を基にスケジューリング結果情報を作成する（ステップS140）。次いで、送信タイミングスケジューラ100は、作成されたスケジューリング結果情報と修正箇所情報とを出力する（ステップS150）。出力した後、送信タイミングスケジューラ100は、設計処理を終了する。
【０１３６】
以下、設計処理を構成する副処理を説明する。最初に、ステップS120の補足情報付き制約情報作成処理を説明する。図１２は、第１の実施形態の制約作成部110による補足情報付き制約情報作成処理の動作を示すフローチャートである。
【０１３７】
制約作成部110に、送信タイミングスケジューラ100に入力された通信要求情報とトポロジ情報とが入力される。なお、送信タイミングスケジューラ100に制約定義情報が入力された場合、制約作成部110に制約定義情報が入力されてもよい（ステップS121）。
【０１３８】
次いで、修正候補制約作成部111は、入力された情報を基に修正候補制約を示す補足情報付き制約情報を作成する（ステップS122）。修正候補制約作成部111は、作成された補足情報付き制約情報を制約情報記憶部120に記憶する。
【０１３９】
次いで、背景制約作成部112は、入力された情報を基に背景制約を示す補足情報付き制約情報を作成する（ステップS123）。背景制約作成部112は、作成された補足情報付き制約情報を制約情報記憶部120に記憶する。記憶した後、制約作成部110は、補足情報付き制約情報作成処理を終了する。
【０１４０】
次に、ステップS130の充足解探索処理を説明する。図１３は、第１の実施形態の制約充足問題解決部130による充足解探索処理の動作を示すフローチャートである。
【０１４１】
制約充足問題解決部130は、制約情報記憶部120に記憶されている補足情報付き制約情報が示す全ての制約を取得する（ステップS131）。次いで、問題解決部131は、ステップS131で取得された全制約を充足する解である充足解を探索する（ステップS132）。
【０１４２】
充足解が導出されなかった場合（ステップS133におけるNo）、問題解決部131は、Unsat Coreを出力する。問題解決部131は、出力されたUnsat CoreをUnsat Core解析部132に入力する（ステップS134）。
【０１４３】
次いで、Unsat Core解析部132は、入力されたUnsat Coreを解析し、修正対象の制約である修正制約と、修正制約に対する修正コメントを生成する（ステップS135）。なお、Unsat Core解析部132は、生成された修正コメントを充足解が導出されるまで記憶する。
【０１４４】
次いで、問題解決部131は、ステップS131で取得された全ての制約からステップS135で生成された修正制約が除かれた制約群を満たす充足解を再度探索する（ステップS136）。
なお、問題解決部131は、ステップS136で修正制約が除かれた制約群の代わりに、修正制約の内容が修正された制約群を満たす充足解を探索してもよい。
【０１４５】
充足解が導出されるまで、問題解決部131は、ステップS133〜ステップS136の処理を繰り返し実行する。なお、ステップS133〜ステップS136の処理ループが継続して実行されると、最終的に充足解の探索対象の制約群には修正候補制約が含まれなくなり、背景制約のみが含まれる。
【０１４６】
背景制約作成部112は背景制約群に含まれる制約のみが考慮された制約充足問題に必ず充足解が存在するように背景制約を作成しているため、制約群に背景制約のみが含まれると、問題解決部131は、充足解を導出できる。すなわち、ステップS133〜ステップS136の処理ループは、必ず終了する。
【０１４７】
充足解が導出された場合（ステップS133におけるYes）、問題解決部131は、導出された充足解を示す充足解情報と、存在する修正箇所情報を出力する（ステップS137）。出力される修正箇所情報には、ステップS135で生成された修正制約と修正コメントが記載されている。出力した後、制約充足問題解決部130は、充足解探索処理を終了する。
【０１４８】
次に、ステップS140の充足解解析処理を説明する。図１４は、第１の実施形態の充足解解析部140による充足解解析処理の動作を示すフローチャートである。
【０１４９】
充足解解析部140に、制約充足問題解決部130から充足解情報が入力される（ステップS141）。次いで、充足解解析部140は、入力された充足解情報の中から、変数の値が１である変数情報を全て列挙する（ステップS142）。
【０１５０】
次いで、充足解解析部140は、列挙された各変数情報が示す変数名に従って、パケットにタイムスロットを割り当てる（ステップS143）。変数の値が１である変数情報に関してタイムスロット割当が全て行われた後、充足解解析部140は、パケットにタイムスロットが割り当てられた全ての結果を示すスケジューリング結果情報を出力する（ステップS144）。
【０１５１】
例えば、図８に示す最初の変数情報であれば、充足解解析部140は、通信要求ID=1の通信要求に関するパケットにタイムスロット番号が「１」のタイムスロットを割り当てる。
充足解解析部140による割当に対応して、図１０に示す通信要求IDが「１」のスケジュール結果情報のタイムスロットには「０」が記載されている。出力した後、充足解解析部140は、充足解解析処理を終了する。
【０１５２】
以下、充足解探索処理を構成する副処理である、ステップS135のUnsat Core解析処理を説明する。図１５は、第１の実施形態のUnsat Core解析部132によるUnsat Core解析処理の動作を示すフローチャートである。
【０１５３】
Unsat Core解析部132に、Unsat Coreが入力される（ステップS161）。次いで、Unsat Core解析部132は、入力されたUnsat Coreに含まれる制約を、修正候補制約と背景制約に分類する（ステップS162）。Unsat Core解析部132は、制約情報記憶部120に記憶されている情報を参照して制約を分類する。
【０１５４】
次いで、Unsat Core解析部132は、分類された修正候補制約の中から、修正対象の制約である修正制約を選択する。また、Unsat Core解析部132は、選択された修正制約に関連する修正コメントを補足情報付き制約情報から取得する（ステップS163）。図９に示す例は、Unsat Core解析部132が１つの修正制約を選択した場合の例である。
【０１５５】
次いで、Unsat Core解析部132は、背景制約群に含まれる全ての修正理由を示すメッセージを修正コメントに追記する（ステップS164）。次いで、Unsat Core解析部132は、修正制約と修正コメントとを出力する（ステップS165）。出力した後、Unsat Core解析部132は、Unsat Core解析処理を終了する。
【０１５６】
［効果の説明］
本実施形態の送信タイミングスケジューラ100は、固定の制約と修正候補の制約のいずれであるかを示すタグと、設計装置が修正箇所と共に提示する修正コメントに関する情報が追加された補足情報付き制約情報を作成する制約作成部110を備える。
【０１５７】
制約作成部110は、通信ネットワークに含まれる機器の接続関係を示すトポロジ情報と、通信ネットワークに含まれる機器に実行が要求される通信を示す通信要求情報と、通信タイミングが決定される際に考慮を要する制約を示す制約定義情報とに基づいて補足情報付き制約情報を作成する。作成された補足情報付き制約情報は、通信ネットワークに含まれる制御機器に対するパケット送信タイミングのスケジューリングで使用される。
【０１５８】
また、本実施形態の送信タイミングスケジューラ100は、補足情報付き制約情報が示す全制約群、または修正候補のタグが付与された制約が修正された制約群を充足する解の変数情報である充足解情報を出力する制約充足問題解決部130を含む。充足解を導出する際、制約充足問題解決部130は、全制約群のうち修正された制約と、修正された制約に対する修正コメントを含む修正箇所情報を生成する。すなわち、制約充足問題解決部130は、制約群の修正箇所と修正理由を提示できる。
【０１５９】
また、本実施形態の送信タイミングスケジューラ100は、出力された充足解情報を用いて各制御機器に対するパケット送信タイミングのスケジューリングを行い、スケジューリング結果を示すスケジューリング結果情報を作成する充足解解析部140を含む。
【０１６０】
本実施形態の送信タイミングスケジューラ100は、人為的なミスやリンクでの帯域超過が発生しないように、パスアドレッシング通信における送信タイミングのスケジューリングを適切に行う。スケジューリングが行われる際、制約充足問題解決部130は、修正された通信要求および通信要求の修正理由を示す情報を作成し、作成された情報を外部に出力する。
【０１６１】
すなわち、本実施形態の送信タイミングスケジューラ100は、通信要求の修正理由を明確に設計者に提示できる。よって、設計者が、通信要求設計を迅速に見直すことができるため、通信における人為的なミスに起因した障害の発生が予防される。本実施形態の送信タイミングスケジューラ100が作成したパケット送信タイミングのスケジュール情報が使用されると、使用されない場合に比べて信頼性の高い通信が実行される。
【０１６２】
＜第２の実施形態＞
［構成の説明］
次に、本発明の第２の実施形態を、図面を参照して説明する。図１６は、制約作成部110の第２の実施形態の構成例を示すブロック図である。図１６に示すように、本実施形態の制約作成部110は、送信制約作成部113と、帯域制約作成部114と、スロット制限制約作成部115と、依存関係制約作成部116とを含む。
【０１６３】
本実施形態では、第１の実施形態の修正候補制約作成部111の代わりに、送信制約作成部113が修正候補制約を示す補足情報付き制約情報を作成する。また、本実施形態では、第１の実施形態の背景制約作成部112の代わりに、帯域制約作成部114、スロット制限制約作成部115、および依存関係制約作成部116が背景制約を示す補足情報付き制約情報を作成する。
【０１６４】
また、本実施形態の制約作成部110には、第１の実施形態の制約定義情報の代わりに、スロット制限定義情報および依存関係定義情報が入力される。なお、制約作成部110以外の第２の実施形態の構成は、第１の実施形態の構成と同様である。
【０１６５】
以下、制約作成部110に含まれる各構成要素を、図面を参照して説明する。最初に、送信制約作成部113を説明する。
【０１６６】
送信制約作成部113には、通信要求情報が入力される。送信制約作成部113は、入力された通信要求情報を基に補足情報付き制約情報を作成する機能を有する。具体的には、送信制約作成部113は、１つの通信要求情報が示すパケット投入処理に対して１つの制約式を作成する。すなわち、パケット投入処理が制約式化される。
【０１６７】
また、送信制約作成部113は、制約式が記載された制約情報に「修正候補」タグと修正コメントを補足情報として追記する。送信制約作成部113は、作成された補足情報付き制約情報を制約情報記憶部120に記憶する。
【０１６８】
次に、帯域制約作成部114を説明する。帯域制約作成部114には、通信要求情報とトポロジ情報とが入力される。帯域制約作成部114は、入力された通信要求情報とトポロジ情報とを基に補足情報付き制約情報を作成する機能を有する。
【０１６９】
具体的には、帯域制約作成部114は、各タイムスロットにおける各リンクの帯域使用率の上限値を基に制約式を作成する。また、帯域制約作成部114は、制約式が記載された制約情報に「背景」タグと修正理由コメントを補足情報として追記する。帯域制約作成部114は、作成された補足情報付き制約情報を制約情報記憶部120に記憶する。
【０１７０】
次に、スロット制限制約作成部115を説明する。スロット制限制約作成部115には、通信要求情報とスロット制限定義情報とが入力される。スロット制限制約作成部115は、入力された通信要求情報とスロット制限定義情報とを基に補足情報付き制約情報を作成する機能を有する。具体的には、スロット制限制約作成部115は、パケットの種類に依存する、割り当てられるタイムスロットの選択肢を制限する制約を示す補足情報付き制約情報を作成する。
【０１７１】
例えば、SpaceWire-Dの標準仕様では、提供するサービスの種類が観測データ収集である通信のパケットには、(4n+1)番のタイムスロットを割り当てること等が規定されている。スロット制限制約作成部115は、割り当てられるタイムスロットの規則に関する補足情報付き制約情報を作成できる。
【０１７２】
スロット制限制約作成部115は、１つの割り当てられるタイムスロットの条件に対して１つの制約式を作成する。また、スロット制限制約作成部115は、制約式が記載された制約情報に「背景」タグと修正理由コメントを補足情報として追記する。スロット制限制約作成部115は、作成された補足情報付き制約情報を制約情報記憶部120に記憶する。
【０１７３】
以下、スロット制限制約作成部115に入力されるスロット制限定義情報を説明する。図１７は、スロット制限定義情報リストの例を示す説明図である。図１７に示すスロット制限定義情報リストは、複数のスロット制限定義情報で構成されている。なお、スロット制限定義情報の形式は、図１７に示す形式に限られない。
【０１７４】
図１７に示すように、スロット制限定義情報は、スロット制限IDと、許容タイムスロットと、RMAPアドレスと、コマンドと、リプライとで構成されている。スロット制限制約作成部115は、１つのスロット制限定義情報を基に１つの補足情報付き制約情報を作成する。
【０１７５】
スロット制限IDは、スロット制限定義情報を識別する識別子である。スロット制限IDは、例えば、図９に示す修正箇所情報の修正コメントに「スロット制限ID=nのスロット制限定義情報に記載されている条件に違反」等と記載されるように利用される。
【０１７６】
RMAPアドレス、コマンド、およびリプライは、スロット制限IDに対応するスロット制限の対象のパケットに関する情報である。なお、RMAPアドレス、コマンド、およびリプライは、通信要求情報にも含まれている。
【０１７７】
スロット制限IDが「３」のスロット制限定義情報のリプライには、「−」が記載されている。すなわち、スロット制限ID「３」に対応するスロット制限の対象のパケットに関して、リプライは「あり」と「なし」のどちらでもよい。
【０１７８】
許容タイムスロットは、スロット制限IDに対応するスロット制限の対象のパケットへの割当が許容されているタイムスロットの番号を示す。図１７に示すように、許容タイムスロットには、複数の番号が記載される。なお、許容タイムスロットには、番号が１つだけ記載されてもよい。
【０１７９】
次に、依存関係制約作成部116を説明する。依存関係制約作成部116には、通信要求情報と依存関係定義情報とが入力される。依存関係制約作成部116は、入力された通信要求情報と依存関係定義情報とを基に補足情報付き制約情報を作成する機能を有する。
【０１８０】
具体的には、依存関係制約作成部116は、通信間の依存関係を基に制約式を作成する。
例えば、依存関係制約作成部116は、観測機器による観測データの収集が行われる通信に、ポーリングが行われる通信に割り当てられたタイムスロットの番号よりも後の番号のタイムスロットを割り当てる等の規則を基に制約式を作成する。
【０１８１】
依存関係制約作成部116は、ネットワーク中のリンクごとに１つの制約式を、各タイムスロットに対して作成する。また、依存関係制約作成部116は、制約式が記載された制約情報に「背景」タグと修正理由コメントを補足情報として追記する。依存関係制約作成部116は、作成された補足情報付き制約情報を制約情報記憶部120に記憶する。
【０１８２】
以下、依存関係制約作成部116に入力される依存関係定義情報を説明する。図１８は、依存関係定義情報リストの例を示す説明図である。図１８に示す依存関係定義情報リストは、複数の依存関係定義情報で構成されている。なお、依存関係定義情報の形式は、図１８に示す形式に限られない。
【０１８３】
図１８に示すように、依存関係定義情報は、依存関係IDと、優先RMAPアドレスと、優先コマンドと、優先リプライと、劣後RMAPアドレスと、劣後コマンドと、劣後リプライと、タイムスロット間隔とで構成される。依存関係制約作成部116は、１つの依存関係定義情報を基に１つの補足情報付き制約情報を作成する。
【０１８４】
依存関係IDは、依存関係定義情報を識別する識別子である。また、優先RMAPアドレス、優先コマンド、および優先リプライは、優先的にタイムスロットが割り当てられるパケットである優先パケットに関する情報である。
【０１８５】
また、劣後RMAPアドレス、劣後コマンド、および劣後リプライは、優先パケットの次にタイムスロットが割り当てられるパケットである劣後パケットに関する情報である。また、タイムスロット間隔は、優先パケットに割り当てられるタイムスロットと劣後パケットに割り当てられるタイムスロットとのスロット間隔である。
【０１８６】
例えば、依存関係定義情報のタイムスロット間隔が「ｍ」であり、依存関係定義情報が示す優先パケットにｎ番のタイムスロットが割り当てられた場合、依存関係定義情報が示す劣後パケットには（ｎ＋ｍ）番のタイムスロットが割り当てられる。
【０１８７】
また、依存関係定義情報のタイムスロット間隔は、指定されなくてもよい。値が指定されない場合、タイムスロット間隔は空欄になる。または、タイムスロット間隔に「＊」等のワイルドカードが記載されてもよい。
【０１８８】
タイムスロット間隔が指定されていない依存関係定義情報を基に、依存関係制約作成部116は、優先パケットに割り当てられるタイムスロットの番号をｘ、劣後パケットに割り当てられるタイムスロットの番号をｙとして、「ｘ＜ｙ」の制約式を作成する。上記のように、依存関係制約作成部116は、補足情報付き制約情報を作成する。
【０１８９】
なお、本実施形態でも、修正候補制約群および背景制約群は、必ず充足解が存在するように作成される。すなわち、本実施形態で作成される制約群は、第１の実施形態で作成される制約群と同じ性質を有する。
【０１９０】
［動作の説明］
以下、本実施形態の制約作成部110の動作を図１９〜図２３を参照して説明する。図１９は、第２の実施形態の制約作成部110による補足情報付き制約情報作成処理の動作を示すフローチャートである。
【０１９１】
なお、本実施形態の送信タイミングスケジューラ100による設計処理の全体動作は、図１１に示す全体動作と同様である。すなわち、図１９に示す処理は、図１１に示すステップS120の補足情報付き制約情報作成処理に相当する。
【０１９２】
制約作成部110に、送信タイミングスケジューラ100に入力された通信要求情報、トポロジ情報、スロット制限定義情報、および依存関係定義情報が入力される（ステップS210）。
【０１９３】
次いで、送信制約作成部113は、入力された情報を基に送信制約を示す補足情報付き制約情報を作成する（ステップS220）。送信制約作成部113は、作成された補足情報付き制約情報を制約情報記憶部120に記憶する。
【０１９４】
次いで、帯域制約作成部114は、入力された情報を基に帯域制約を示す補足情報付き制約情報を作成する（ステップS230）。帯域制約作成部114は、作成された補足情報付き制約情報を制約情報記憶部120に記憶する。
【０１９５】
次いで、スロット制限制約作成部115は、入力された情報を基にスロット制限制約を示す補足情報付き制約情報を作成する（ステップS240）。スロット制限制約作成部115は、作成された補足情報付き制約情報を制約情報記憶部120に記憶する。
【０１９６】
次いで、依存関係制約作成部116は、入力された情報を基に依存関係制約を示す補足情報付き制約情報を作成する（ステップS250）。依存関係制約作成部116は、作成された補足情報付き制約情報を制約情報記憶部120に記憶する。記憶した後、制約作成部110は、補足情報付き制約情報作成処理を終了する。
【０１９７】
以下、補足情報付き制約情報作成処理を構成する副処理を説明する。最初に、ステップS220の送信制約作成処理を説明する。図２０は、第２の実施形態の送信制約作成部113による送信制約作成処理の動作を示すフローチャートである。
【０１９８】
送信制約作成部113に、制約作成部110に入力された通信要求情報が入力される（ステップS221）。次いで、送信制約作成部113は、入力された全ての通信要求情報に対する制約式化が完了しているか否かを確認する（ステップS222）。
【０１９９】
全ての通信要求情報に対する制約式化が完了していない場合（ステップS222におけるNo）、送信制約作成部113は、入力された通信要求情報のうち制約式化されていない通信要求情報を選択する（ステップS223）。
【０２００】
次いで、送信制約作成部113は、選択された通信要求情報の通信間隔を参照して、制約式と修正コメントを作成する（ステップS224）。次いで、送信制約作成部113は、作成された制約式と修正コメントが含まれる補足情報付き制約情報を作成する。作成した後、送信制約作成部113は、再度ステップS222の処理を行う。
【０２０１】
全ての通信要求情報に対する制約式化が完了している場合（ステップS222におけるYes）、送信制約作成部113は、送信制約作成処理を終了する。
【０２０２】
次に、ステップS230の帯域制約作成処理を説明する。図２１は、第２の実施形態の帯域制約作成部114による帯域制約作成処理の動作を示すフローチャートである。
【０２０３】
帯域制約作成部114に、制約作成部110に入力された通信要求情報とトポロジ情報とが入力される（ステップS231）。次いで、帯域制約作成部114は、入力されたトポロジ情報に含まれる全ての結線情報に対する制約式化が完了しているか否かを確認する（ステップS232）。
【０２０４】
全ての結線情報に対する制約式化が完了していない場合（ステップS232におけるNo）、帯域制約作成部114は、入力された結線情報のうち制約式化されていない結線情報を選択する（ステップS233）。
【０２０５】
次いで、帯域制約作成部114は、選択された結線情報のリンクIDが示すリンクを通過するパケットに関する通信要求情報を全て列挙する（ステップS234）。次いで、帯域制約作成部114は、列挙された通信要求情報を基に帯域に関する制約式と修正理由コメントを作成する（ステップS235）。
【０２０６】
次いで、帯域制約作成部114は、作成された制約式と修正理由コメントが含まれる補足情報付き制約情報を作成する。作成した後、帯域制約作成部114は、再度ステップS232の処理を行う。
【０２０７】
全ての結線情報に対する制約式化が完了している場合（ステップS232におけるYes）、帯域制約作成部114は、帯域制約作成処理を終了する。
【０２０８】
次に、ステップS240のスロット制限制約作成処理を説明する。図２２は、第２の実施形態のスロット制限制約作成部115によるスロット制限制約作成処理の動作を示すフローチャートである。
【０２０９】
スロット制限制約作成部115に、制約作成部110に入力された通信要求情報とスロット制限定義情報とが入力される（ステップS241）。次いで、スロット制限制約作成部115は、入力されたスロット制限定義情報に対する制約式化が完了しているか否かを確認する（ステップS242）。
【０２１０】
全てのスロット制限定義情報に対する制約式化が完了していない場合（ステップS242におけるNo）、スロット制限制約作成部115は、入力されたスロット制限定義情報のうち制約式化されていないスロット制限定義情報を選択する（ステップS243）。
【０２１１】
次いで、スロット制限制約作成部115は、選択されたスロット制限定義情報で定義されているRMAPアドレス等のパケット情報を含む通信要求情報を全て列挙する（ステップS244）。次いで、スロット制限制約作成部115は、列挙された通信要求情報と選択されたスロット制限定義情報で定義されている許容タイムスロットとを基に、制約式と修正理由コメントを作成する（ステップS245）。
【０２１２】
次いで、スロット制限制約作成部115は、作成された制約式と修正理由コメントが含まれる補足情報付き制約情報を作成する。作成した後、スロット制限制約作成部115は、再度ステップS242の処理を行う。
【０２１３】
全てのスロット制限定義情報に対する制約式化が完了している場合（ステップS242におけるYes）、スロット制限制約作成部115は、スロット制限制約作成処理を終了する。
【０２１４】
次に、ステップS250の依存関係制約作成処理を説明する。図２３は、第２の実施形態の依存関係制約作成部116による依存関係制約作成処理の動作を示すフローチャートである。
【０２１５】
依存関係制約作成部116に、制約作成部110に入力された通信要求情報と依存関係定義情報とが入力される（ステップS251）。次いで、依存関係制約作成部116は、入力された依存関係定義情報に対する制約式化が完了しているか否かを確認する（ステップS252）。
【０２１６】
全ての依存関係定義情報に対する制約式化が完了していない場合（ステップS252におけるNo）、依存関係制約作成部116は、入力された依存関係定義情報のうち制約式化されていない依存関係定義情報を選択する（ステップS253）。
【０２１７】
次いで、依存関係制約作成部116は、選択された依存関係定義情報で定義されている優先パケット情報を含む通信要求情報、および選択された依存関係定義情報で定義されている劣後パケット情報を含む通信要求情報を全て列挙する（ステップS254）。
【０２１８】
次いで、依存関係制約作成部116は、列挙された通信要求情報と選択された依存関係定義情報で定義されているタイムスロット間隔とを基に、制約式と修正理由コメントを作成する（ステップS255）。
【０２１９】
次いで、依存関係制約作成部116は、作成された制約式と修正理由コメントが含まれる補足情報付き制約情報を作成する。作成した後、依存関係制約作成部116は、再度ステップS252の処理を行う。
【０２２０】
全ての依存関係定義情報に対する制約式化が完了している場合（ステップS252におけるYes）、依存関係制約作成部116は、依存関係制約作成処理を終了する。
【０２２１】
［効果の説明］
本実施形態の送信タイミングスケジューラ100の制約作成部110は、様々な入力情報に応じて補足情報付き制約情報を作成できる。よって、送信タイミングスケジューラ100は、設定がより複雑な通信ネットワークで使用されるパケット送信タイミングのスケジュールを作成できる。
【０２２２】
なお、各実施形態において、送信タイミングスケジューラ100の設計対象システムをSpaceWireネットワークを用いるサブシステムとして説明した。しかし、各実施形態の送信タイミングスケジューラ100の設計対象システムは、タイムスロットを用いてパケットを送信するシステムであれば、SpaceWireネットワークを使用するシステムに限られない。また、各実施形態の送信タイミングスケジューラ100の設計対象システムは、サブシステムに限られない。
【０２２３】
また、各実施形態の各構成要素が、他の構成要素に情報を直接送信または出力するとして説明した。情報を直接送信または出力する以外にも、各構成要素は、生成された情報、および受信された情報を各実施形態に含まれる記憶部に一旦保存し、記憶部から情報を読み出して他の構成要素に送信または出力してもよい。
【０２２４】
なお、本実施形態の送信タイミングスケジューラ100は、例えば、記憶媒体に格納されているプログラムに従って処理を実行するCPU(Central Processing Unit)によって実現される。すなわち制約作成部110、制約充足問題解決部130、および充足解解析部140は、例えば、プログラム制御に従って処理を実行するCPUによって実現される。
【０２２５】
また、制約情報記憶部120は、例えばRAM(Random Access Memory)で実現される。
【０２２６】
また、本実施形態の送信タイミングスケジューラ100における各部は、ハードウェア回路によって実現されてもよい。
【０２２７】
次に、本発明の概要を説明する。図２４は、本発明によるタイムスロット設計装置の概要を示すブロック図である。本発明によるタイムスロット設計装置10は、充足解が導出されない制約充足問題に関する制約群（例えば、Unsat Core）に含まれる修正対象の制約である修正制約と修正制約が修正される理由である修正理由とを出力する出力手段11（例えば、Unsat Core解析部132）と、出力された修正制約が修正された制約群を基に生成された制約充足問題の充足解を導出する導出手段12（例えば、問題解決部131）とを備え、導出手段12は、充足解が導出されるまでに出力された修正制約および出力された修正理由を示す情報を出力する。
【０２２８】
そのような構成により、タイムスロット設計装置は、修正された制約を満たすスロット割当結果に関する制約の修正箇所および修正理由を出力できる。
【０２２９】
また、タイムスロット設計装置10は、制約群に含まれる制約を作成する作成手段（例えば、制約作成部110）を備えてもよい。
【０２３０】
そのような構成により、タイムスロット設計装置は、入力された情報に対応したスロット割当結果を出力できる。
【０２３１】
また、作成手段は、修正候補の制約を作成する修正候補制約作成手段（例えば、修正候補制約作成部111）と、修正の対象外である固定的な制約を作成する固定制約作成手段（例えば、背景制約作成部112）とを含んでもよい
【０２３２】
また、出力手段11は、制約群に含まれる全ての固定的な制約に基づいて修正理由を作成してもよい。
【０２３３】
そのような構成により、タイムスロット設計装置は、固定的な制約に基づいて修正制約に対する修正理由を作成できる。
【０２３４】
また、出力手段11は、制約群に含まれる制約を修正候補の制約と固定的な制約に分類し、出力される修正制約を分類された修正候補の制約の中から選択してもよい。
【０２３５】
そのような構成により、タイムスロット設計装置は、設計者に修正の検討の余地がある制約を提示できる。
【０２３６】
また、タイムスロット設計装置10は、導出された充足解を用いてパケットにタイムスロットを割り当てる割当手段（例えば、充足解解析部140）を備えてもよい。
【０２３７】
そのような構成により、タイムスロット設計装置は、制約充足問題の充足解を用いてタイムスロットテーブルを設計できる。
【０２３８】
また、導出手段12は、充足解が導出されない制約充足問題に関する制約群を出力手段11に入力してもよい。
【０２３９】
そのような構成により、タイムスロット設計装置は、最初の処理で充足解が導出されない場合にも対応できる。
【０２４０】
また、修正候補制約作成手段および固定制約作成手段は、作成される制約に出力手段11が出力する修正理由に関する情報を追加してもよい。
【０２４１】
また、修正候補制約作成手段は、通信要求情報を入力とし、通信要求情報に記載されている制御機器にパケットを送信させる要求を基に修正候補の制約を作成する送信制約作成手段（例えば、送信制約作成部113）を含んでもよい。
【０２４２】
また、固定制約作成手段は、トポロジ情報と通信要求情報とを入力とし、通信ネットワーク内の各リンクの使用可能な帯域幅の条件を示す固定的な制約を作成する帯域制約作成手段（例えば、帯域制約作成部114）を含んでもよい。
【０２４３】
また、固定制約作成手段は、スロット制限定義情報と通信要求情報とを入力とし、通信の種類ごとに割り当て可能なタイムスロットの条件を示す固定的な制約を作成するスロット制限制約作成手段（例えば、スロット制限制約作成部115）を含んでもよい。
【０２４４】
また、固定制約作成手段は、依存関係定義情報と通信要求情報とを入力とし、通信の実行優先順位、および通信間のタイムスロット間隔の条件を示す固定的な制約を作成する依存関係制約作成手段（例えば、依存関係制約作成部116）を含んでもよい。
【０２４５】
以上、実施形態を参照して本願発明を説明したが、本願発明は上記実施形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【０２４６】
この出願は、２０１６年４月１２日に出願された日本出願特願２０１６−０７９５２０を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【産業上の利用可能性】
【０２４７】
本発明は、SpaceWireの仕様に従うインタフェースを備えた衛星内ネットワークの設計に好適に適用される。また、本発明は、衛星内ネットワークの開発初期段階での初期設計、および衛星試験時の設計検査に好適に適用される。また、本発明は、ソースルーティング方式が採用されたパスアドレッシング通信が行われる通信ネットワークに含まれる機器の設計および機器の試験に好適に適用される。
【符号の説明】
【０２４８】
10  タイムスロット設計装置
11  出力手段
12  導出手段
100  送信タイミングスケジューラ
110  制約作成部
111  修正候補制約作成部
112  背景制約作成部
113  送信制約作成部
114  帯域制約作成部
115  スロット制限制約作成部
116  依存関係制約作成部
120  制約情報記憶部
130  制約充足問題解決部
131  問題解決部
132  Unsat Core解析部
140  充足解解析部
200  SpaceWireネットワーク
201  システム制御機器
202  通信機器
203  電源機器
204  姿勢系制御機器
205  観測系制御機器
206A〜206E、206X、206Y  ルータ
210A〜210B  搭載機器
214A〜214B  姿勢制御機器
215A〜215X  観測機器
【図１】
2017179540.tif 000003
【図２】
2017179540.tif 000004
【図３】
2017179540.tif 000005
【図４】
2017179540.tif 000006
【図５】
2017179540.tif 000007
【図６】
2017179540.tif 000008
【図７】
2017179540.tif 000009
【図８】
2017179540.tif 000010
【図９】
2017179540.tif 000011
【図１０】
2017179540.tif 000012
【図１１】
2017179540.tif 000013
【図１２】
2017179540.tif 000014
【図１３】
2017179540.tif 000015
【図１４】
2017179540.tif 000016
【図１５】
2017179540.tif 000017
【図１６】
2017179540.tif 000018
【図１７】
2017179540.tif 000019
【図１８】
2017179540.tif 000020
【図１９】
2017179540.tif 000021
【図２０】
2017179540.tif 000022
【図２１】
2017179540.tif 000023
【図２２】
2017179540.tif 000024
【図２３】
2017179540.tif 000025
【図２４】
2017179540.tif 000026
【図２５】
2017179540.tif 000027
【図２６】
2017179540.tif 000028
【手続補正書】
【提出日】平成30年9月19日(2018.9.19)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項９
【補正方法】変更
【補正の内容】
【請求項９】
コンピュータに、
充足解が導出されない制約充足問題に関する制約群に含まれる修正対象の制約である修正制約と前記修正制約が修正される理由である修正理由とを出力する出力処理、
出力された前記修正制約が修正された前記制約群を基に生成された制約充足問題の充足解を導出する導出処理、および
前記充足解が導出されるまでに出力された前記修正制約および出力された前記修正理由を示す情報を出力する情報出力処理
を実行させるためのタイムスロット設計プログラム。
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１０
【補正方法】変更
【補正の内容】
【請求項１０】
前記コンピュータに、
前記制約群に含まれる制約を作成する作成処理を実行させる
請求項９記載のタイムスロット設計プログラム。
【国際調査報告】
2017179540.tif 000029
2017179540.tif 000030
2017179540.tif 000031
2017179540.tif 000032