(57)【特許請求の範囲】
【請求項１】
ネットワークを介して接続された第１のノード及び第２のノードが各々一定の周期で第１のメッセージ及び第２のメッセージを送信するシステムにおける前記第１のメッセージの初回送信時間及び第２のメッセージの初回送信時間の算出方法であって、
前記第２のメッセージの初回送信時間から前記第１のメッセージの初回送信時間を減じた値が前記第１のメッセージの周期と前記第２のメッセージの周期との最大公約数で割り切れる場合には１、割り切れない場合には０を取る数δと、前記第１のメッセージの周期および前記第２のメッセージの周期の最小公倍数で表されるメッセージ衝突周期の逆数との積を組毎の性能基準値とし、異なる組毎の性能基準値の総和からなる全体の性能基準値を算出するステップと、
前記全体の性能基準値に基づいて前記第１のメッセージの初回送信時間及び第２のメッセージの初回送信時間を最適化する最適化ステップと、を具備することを特徴とするメッセージ初回送信時間の算出方法。
【請求項２】
前記最適化ステップは、算出された前記性能基準値に基づいて、メッセージ衝突回数を最小化する初回送信時間を求める並列的探索ステップであって、
前記初回送信時間を複数生成するステップと、
生成された前記複数の初回送信時間のそれぞれと前記メッセージの周期との組について前記性能基準値を算出するステップと、
算出された前記性能基準値のいずれか優秀な値をとるものについての初回送信時間を出力するステップと、を具備することを特徴とする請求項１に記載の算出方法。
【請求項３】
前記最適化ステップは、算出された前記性能基準値に基づいて、メッセージ衝突回数を最小化する初回送信時間を求める逐次的探索ステップであって、
第１の初回送信時間について第１の性能基準値を算出するステップと、
前記第１の初回送信時間を第２の初回送信時間に更新するとともに該第２の初回送信時間について第２の性能基準値を算出するステップと、
前記第１の性能基準値と第２の性能基準値との比較に基づいて初回送信時間の更新前後の優劣を求め、探索を打ち切るか否かを決定するステップと、を具備することを特徴とする請求項１に記載の算出方法。
【請求項４】
ネットワークを介して接続された第１のノード及び第２のノードが各々一定の周期で第１のメッセージ及び第２のメッセージを送信するシステムにおける前記第１のメッセージの初回送信時間及び第２のメッセージの初回送信時間の算出プログラムであって、
前記第２のメッセージの初回送信時間から前記第１のメッセージの初回送信時間を減じた値が前記第１のメッセージの周期と前記第２のメッセージの周期との最大公約数で割り切れる場合には１、割り切れない場合には０を取る数δと、前記第１のメッセージの周期および前記第２のメッセージの周期の最小公倍数で表されるメッセージ衝突周期の逆数との積を組毎の性能基準値とし、異なる組毎の性能基準値の総和からなる全体の性能基準値を算出する機能と、
前記全体の性能基準値に基づいて前記第１のメッセージの初回送信時間及び第２のメッセージの初回送信時間を最適化する最適化機能と、をコンピュータに実現させるためのメッセージ初回送信時間の算出プログラム。
【請求項５】
前記最適化機能は、算出された前記性能基準値に基づいて、メッセージ衝突回数を最小化する初回送信時間を求める並列的探索機能であって、
前記初回送信時間を複数生成する機能と、
生成された前記複数の初回送信時間のそれぞれと前記メッセージの周期との組について前記性能基準値を算出する機能と、
算出された前記性能基準値のいずれか優秀な値をとるものについての初回送信時間を出力する機能と、により構成されることを特徴とする請求項４に記載の算出プログラム。
【請求項６】
前記最適化機能は、算出された前記性能基準値に基づいて、メッセージ衝突回数を最小化する初回送信時間を求める逐次的探索機能であって、
第１の初回送信時間について第１の性能基準値を算出する機能と、
前記第１の初回送信時間を第２の初回送信時間に更新するとともに該第２の初回送信時間について第２の性能基準値を算出する機能と、
前記第１の性能基準値と第２の性能基準値との比較に基づいて初回送信時間の更新前後の優劣を求め、探索を打ち切るか否かを決定する機能と、により構成されることを特徴とする請求項４に記載の算出プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は周期的にメッセージを送信するリアルタイム系システム等に好適であり、メッセージ送信が同時に発生した場合のメッセージ衝突によるメッセージ内容の紛失・変質など回避すべく最適なメッセージ初回送信時間を算出するための方法及びプログラムに関する。
【０００２】
【従来の技術】
通信系のシステムの多くは、多数のセンサーやプロセッサがネットワークで結合され、タイマーや割り込みなどで周期的に起動される複数のタスク間でメッセージ通信を行うといった構成を取ることが多い。車載ＬＡＮなどはその典型的な例である。このような構成においては、データを時間内で確実に処理する必要性から、リアルタイム性の要求が年々厳しくなってきている。
【０００３】
このような従来システムでは、メッセージはごく短い場合が多いこともあって、オペレーティングシステムのような優先順位ベースのスケジューリングなどはあまり行われない。このためメッセージの衝突が発生することがあり、これはメッセージ内容の紛失・変質などの問題を生じさせる。
【０００４】
メッセージの衝突が発生した場合、一応は再送処理を行うなどしてこれに対処することができる。しかし再送処理はシステム性能を低下させる要因となり得ることから回避することが好ましく、それ以前に、メッセージの衝突発生自体を回避することが望ましい。
【０００５】
メッセージ送信が周期的な場合、初回送信時間が決まればそれ以降の送信時間も一意的に決まることから、初回送信時間をうまく設定することでメッセージ衝突回数を削減できる可能性がある。ここでいう（初回送信）時間とは、時間軸上の一点をいう。初回送信時間の設定はこれまでシステム設計者の裁量に委ねられており、例えばシミュレーションによる衝突回数の集計結果などに基づいて設定が行われてきた。しかし、従来における初回送信時間の設定は試行錯誤的なものであり、またシミュレーションには時間もかかるため、初回送信時間を適切かつ十分にチューニングして設定できることは希である。
【０００６】
メッセージ衝突回数を十分に削減しないと、メッセージ遅延などネットワーク、ひいてはシステム全体の性能低下を引き起こす恐れもある。
【０００７】
【発明が解決しようとする課題】
本発明はかかる事情を考慮してなされたものであり、メッセージ送信が同時に発生した場合のメッセージ衝突によるメッセージ内容の紛失・変質など回避すべく、最適なメッセージ初回送信時間の設定値を算出するための方法及びプログラムを提供することを目的とする。また、本発明に従い算出されたメッセージ初回送信時間の設定値を設計者に提示することでメッセージ衝突回避によるシステム性能改善を図るための設計支援を実現する。
【０００８】
【課題を解決するための手段】
上記課題を解決し、目的を達成するため本発明は次のように構成されている。
【０００９】
本発明にかかるメッセージ初回送信時間の算出方法はネットワークを介して接続された複数のノードが各々一定の周期でメッセージを送信するシステムにおけるメッセージ初回送信時間の算出方法であって、前記メッセージの周期及び初回送信時間からメッセージ衝突についての性能基準値を算出するステップと、算出された前記性能基準値に基づいて前記初回送信時間を最適化する最適化ステップと、を具備することを特徴とする。
【００１０】
本発明に係るメッセージ初回送信時間の算出プログラムは、ネットワークを介して接続された複数のノードが各々一定の周期でメッセージを送信するシステムにおけるメッセージ初回送信時間の算出プログラムであって、前記メッセージの周期及び初回送信時間からメッセージ衝突についての性能基準値を算出する機能と、算出された前記性能基準値に基づいて前記初回送信時間を最適化する最適化機能と、をコンピュータに実現させるためのプログラムである。
【００１１】
【発明の実施の形態】
以下、図面を参照しながら本発明の実施形態を説明する。
【００１２】
図１は本発明の一実施形態に係る初回送信時間設定最適化システムの概略構成を示すブロック図である。図１に示すように本実施形態に係る初回送信時間設定最適化システムは、メッセージ送信周期設定部１と、性能基準値算出部２及び初回送信時間設定生成部３と、記憶装置４と、シミュレータ５と、出力装置６とにより構成されている。性能基準値算出部２及び初回送信時間設定生成部３は、本発明に必須の構成要素であって、設定部１において設定されたメッセージの送信周期設定について、初回送信時間の最適な設定を生成し、これをシミュレータ５へ出力したり、初回送信時間およびそのメッセージ衝突に関する性能基準値をディスプレイ等からなる出力装置６や記憶装置４のファイル等へ出力する。ここでは図示しないが、出力された初回送信時間設定に設計者が一部修正等を施すことが可能な構成としてもよい。また本発明において、シミュレータ５は必須の構成要素ではない。また、本実施形態に係る初回送信時間設定最適化システムは、図示しないコンピュータと協働するコンピュータソフトウェアとして実現することができる。
【００１３】
このような本実施形態の初回送信時間設定最適化システムを、自動車内ネットワークの設計に適用する場合を例にとって説明する。自動車内に配置された個々のプロセッサやセンサー（以下ノードと呼ぶ）がネットワークを介して相互に接続されており、ノードはネットワーク上に周期的なメッセージを送信する。メッセージの送信周期は、それぞれの処理の必要性や物理的制約・外部環境から定まる部分が多く、設計者が変更する自由度は小さいが、初回送信時間については設計者が比較的自由に設定する余地があると考えられる。初回送信時間を適切に設定することで、ノード内でのメッセージ衝突回数を削減できれば、メッセージ遅延などの問題を軽減できる。ここでは、ノード内のメッセージ衝突の削減を目標とするが、ノード間の同期が良く取れていて、さらにネットワークが十分に高速である場合には、システムの全メッセージに対して初回送信時間設定を試みることも可能である。ただし現状ではノード間で必ずしも十分な同期が取れるとは限らないため、個々のノードごとに初回送信時間設定を行うことが現実的であると思われる。
【００１４】
設計者がメッセージに優先度を設定できる場合は、優先度の高いメッセージができるだけ衝突しないような初回送信時間の設定が望まれる。また初回送信時間に関して、特定のメッセージの初回送信時間が固定であったり、ある範囲に収まるようにといった制約が課せられる場合も考えられる。
【００１５】
このような本実施形態に係る初回送信時間設定最適化システムでは、入力のフォーマットを、例えば次のようなメッセージの性質からなるものとする。
メッセージ１、ノード名、送信周期、（優先度）、（初回送信時間に関する制約）
メッセージ２、ノード名、送信周期、（優先度）、（初回送信時間に関する制約）
：
メッセージＮ、ノード名、送信周期、（優先度）、（初回送信時間に関する制約）
なお、優先度および初回送信時間に関する制約は括弧付きで示してあり、これらは必須でない。
【００１６】
このような入力を受けて、本実施形態に係る初回送信時間設定最適化システムは、メッセージ衝突回数を最小化するような初回送信時間を各ノード毎に出力する。この場合、最良と思われるもの一つを出力する以外に、メッセージ衝突に関する性能基準値が優れたものを何個か出力して設計者に提示してもよい。あるいは、初回送信時間設定のみならずその性能基準値を表示してもよい。さらに、メッセージごとの性能基準値ｆｉ（数式４参照）を算出して表示したり、優先度の高いメッセージについては、性能基準値が小さくなるような初回送信時間設定を選ぶようにしてもよい。
【００１７】
メッセージ送信周期設定部１では、設計者が処理の特性や外部環境等を勘案して、それぞれのメッセージの送信周期を設定する。メッセージには、送信周期以外に、ノード名、優先度、初回送信時間に関する制約などが付加されている。
【００１８】
性能基準値算出部２は、メッセージ送信周期設定部１もしくは記憶部４から受理した上記のような入力フォーマットの情報をもとに、初回送信時間設定生成部３で生成された初回送信時間設定について、その性能基準値を計算する。初回送信時間設定生成部３は、後述する（方法１）、（方法２）、（方法３）のいずれかの手順に従って良好な性能基準値を持つ初回送信時間を生成する。
【００１９】
初回送信時間設定生成部３によって生成された単数もしくは複数の初回送信時間設定は、そのまま出力装置６から出力されるか、シミュレータ５への入力となされる。出力装置６に出力する場合は、たとえばディスプレイ上に、初回送信時間設定およびその性能基準値などを表示する。シミュレータ５への入力とする場合は、全体システムの構成（たとえばノード間のネットワーク接続状況）を考慮したシミュレーションを実行する。シミュレータ５は、出力装置６にシミュレーション結果を表示させたり、記憶装置４にシミュレーション結果を書き込んだりする。設計者はこれらの情報に基づき、初回送信時間設定を採用するか、それともこれに修正を加えるか、もしくは再度初回送信時間最適化を行うか、などの選択肢のうちから、適宜、作業を選択することができる。
【００２０】
本発明では、送信周期と初回送信時間が与えられた（複数の）メッセージに対して、メッセージの衝突頻度を表わす性能基準値を性能基準値算出部２により算出し利用する。これにより、メッセージ衝突回数ができるだけ減少するよう初回送信時間を設定する問題が、性能基準値を最小化する問題に帰着され、最適化手法が適用可能になる。
【００２１】
メッセージが周期的に送信される場合、その送信時刻は送信周期Ｐと初回送信時間ｍの組から定まる。ここで、ｍは０以上Ｐ未満の自然数である。なお、以降の説明では、あるクロック単位の存在を想定し、すべての時刻はクロック単位の整数倍であるとする。ただしクロック単位は、特に具体的には扱わない。クロック単位が１ミリ秒であっても１マイクロ秒であっても、以下の説明には影響しない。
【００２２】
想定される典型的な実施形態では、設計者がメッセージの送信周期を指定する。メッセージの送信周期は、システムの仕様や外部環境から決まる部分が多く、自由度は小さいと思われる。これに対してメッセージの初回送信時間は、設計者が比較的自由に設定できる。ただし、後述する具体的な実施形態では、初回送信時間についても各種の制約が存在し得る。
【００２３】
以下ではメッセージの送信周期は所与であるとして、メッセージ衝突回数が少なくなるよう初回送信時間を設定する問題を検討する。
上述したように、通信系のシステムの多くは多数のセンサーやプロセッサがネットワークでつながれ、タイマーや割り込みなどで周期的に起動されるタスクがメッセージ通信を行うといった構成を取ることが多い。車載ＬＡＮなどは、その典型的な例と言える。本発明のより具体的な実施形態の一つは、通信系システムシミュレータの支援ツールであり、その場合はメッセージの送信周期と初回送信時間が決定されれば、設計者が与えたシナリオに基づいてシミュレーションを実行できる。また本発明はシステム設計における支援ツールとしても実施できるが、その場合は周期的なメッセージ送信機能をタイマーやタスクなどを用いて別途実現することになる。以下ではこれらを区別せずに、メッセージを周期的に送信する機構の存在を前提として説明する。
【００２４】
まず、二つのメッセージがそれぞれ送信周期と初回送信時間の組（Ｐ１，ｍ１）と（Ｐ２，ｍ２）に基づいて送信されるとき、これらの間にメッセージ衝突が生じるのは、
【数１】
0003798720.tif 000002
【００２５】
が成立する場合であり、またその場合に限られる（メッセージ衝突条件）。ただし、ｇｃｄ（Ｐ１，Ｐ２）はＰ１とＰ２の最大公約数を表わす。この式は、ｍ１−ｍ２がｇｃｄ（Ｐ１，Ｐ２）で割り切れることを意味する。またメッセージ衝突が発生する場合、衝突自体が周期的に発生し、その周期はｌｃｍ（Ｐ１，Ｐ２）である。ただしｌｃｍ（Ｐ１，Ｐ２）は、Ｐ１とＰ２の最小公倍数を表わす。
【００２６】
ここで、メッセージ衝突条件を表す数式１の証明を示す。送信周期と初回送信時間の組がそれぞれ（Ｐ１，ｍ１），（Ｐ２，ｍ２）であるメッセージの間に衝突が起きるかどうかを考えると、送信周期と初回送信時間の組が（Ｐ１，ｍ１）であるメッセージが送信される時点は、自然数ｓ≧０によってｍ１＋ｓＰ１と書ける。また、送信周期と初回送信時間の組が（Ｐ２，ｍ２）であるメッセージが送信される時点も同様に、自然数ｔ≧０によってｍ２＋ｔＰ２と書ける。衝突が起こるのは、両方からメッセージが送信される時点であるから、次の等式が成立する：
【数２】
0003798720.tif 000003
【００２７】
これを書き直せば、
【数３】
0003798720.tif 000004
【００２８】
となる。送信周期と初回送信時間の組が（Ｐ１，ｍ１）と（Ｐ２，ｍ２）であるメッセージが衝突することと、数式２が自然数解ｓ，ｔ≧０を持つことは同値である。
【００２９】
数式２がいつ解ｓ，ｔ≧０を持つかを考える。まず解ｓ，ｔ≧０が存在したと仮定する。ｇｃｄ（Ｐ１，Ｐ２）の定義より、
【数４】
0003798720.tif 000005
【００３０】
であるから、ｍ１−ｍ２がｇｃｄ（Ｐ１，Ｐ２）で割り切れることがわかる。実は、この逆も成り立つ。ｍ１−ｍ２がｇｃｄ（Ｐ１，Ｐ２）で割り切れれば、数式２の（必ずしも非負とは限らない）整数解ｓ，ｔが存在することが知られている。これについては例えば片山幸次著「整数論入門」実教出版発行（１９７５年）の第二章定理５などが参考になる。次に、ｓ，ｔ≧０と取れることを示す。ｕを自然数とし、
【数５】
0003798720.tif 000006
【００３１】
とすると、ｓ’，ｔ’も関係式ｔ’Ｐ２−ｓ’Ｐ１＝ｍ１−ｍ２を満たすことを直ちに確認できる。Ｐ１，Ｐ２はともに正整数であるから、ｕを十分大きく取ることでｓ’，ｔ’≧０とすることができる。
【００３２】
最後に、メッセージ衝突の発生時刻に注目する。ある時刻Ｔ１に衝突が発生した後、Ｔ２（＞Ｔ１）でも衝突が発生したとすると、Ｔ２−Ｔ１は双方の送信周期Ｐ１とＰ２の倍数、すなわちＰ１とＰ２の公倍数である。良く知られているように、Ｐ１とＰ２の公倍数は、Ｐ１とＰ２の最小公倍数ｌｃｍ（Ｐ１，Ｐ２）の倍数であるから、ある正整数ｎ≧１についてＴ２＝Ｔ１＋ｎ ｌｃｍ（Ｐ１，Ｐ２）である。逆に、時刻Ｔ１で衝突が起きたとすると、任意の正整数ｎ≧１について時刻Ｔ２＝Ｔ１＋ｎ ｌｃｍ（Ｐ１，Ｐ２）で双方のメッセージが送信され、衝突が生じる。このことから、メッセージ衝突自体が周期的に発生し、その周期はｌｃｍ（Ｐ１，Ｐ２）であることがわかる。メッセージ衝突条件についての数式１の証明は以上である。
【００３３】
二つのメッセージの間のメッセージ衝突に関する性能基準としては、衝突頻度（単位時間当たりの衝突回数）を考えるのが自然である。メッセージ衝突が生じない場合の衝突頻度は０、メッセージ衝突が生ずる場合の衝突頻度は上に述べたことから衝突の周期ｌｃｍ（Ｐ１，Ｐ２）の逆数
【数６】
0003798720.tif 000007
である。
【００３４】
メッセージが三つ以上存在する場合は、そのうちから異なる二つを選ぶ組み合わせそれぞれのメッセージ衝突に関する性能基準値の総和を性能基準値とする。具体的にはこれは次の式で与えられる：
【数７】
0003798720.tif 000008
【００３５】
ただし、δｉｊはメッセージｉとメッセージｊが衝突すれば１、衝突しない場合は０と定義する。メッセージｉ，ｊそれぞれの送信周期と初回送信時間の組を（Ｐｉ，ｍｉ）（ｉ＝１，２）とした時、δｉｊ＝１であるための必要十分条件が
【数８】
0003798720.tif 000009
【００３６】
であることは既に述べた通りである。このメッセージ衝突に関する性能基準値では、ある時点でメッセージが三つ以上衝突する場合を、二つのメッセージの衝突が三つ以上重なって起きたものとして扱っていることに注意されたい。このようにして計算された数値ｆを、以下ではメッセージ衝突に関する性能基準値と言うこととする。この性能基準値が小さいほどメッセージ衝突回数は少なく、特に０であればメッセージ衝突は生じない。もちろん、メッセージ衝突に関する性能基準値としてはここで述べたもの以外にも、たとえば多重衝突のカウント法が異なるものなど、いくつかの可能性が存在することは言うまでもないが、ここで与えた性能基準値はその中でも基本的で、計算が容易なものである。
【００３７】
多重衝突をどう扱うかについて簡単に述べる。三つのメッセージの送信周期と初回送信時間の組が（Ｐ１，ｍ１），（Ｐ２，ｍ２），（Ｐ３，ｍ３）であったとする。この間に三重衝突が存在するためには、まずメッセージ１とメッセージ２、メッセージ２とメッセージ３、メッセージ１とメッセージ３、それぞれが衝突することが前提となる。メッセージ１とメッセージ２の衝突が発生した時刻をｍ１２とする。これは数式２の解ｓまたはｔを具体的に構成して、ｍ１２＝ｍ１＋ｓＰ１、またはｍ１２＝ｍ２＋ｔＰ２とすればよい。三重衝突が生ずるのは、初回送信時間ｍ１２、周期ｌｃｍ（Ｐ１，Ｐ２）で発生しているメッセージ１と２の衝突に、メッセージ３の送信時刻が一致する場合であるから、そのための条件は、
【数９】
0003798720.tif 000010
【００３８】
が成立することである。衝突する場合は周期ｌｃｍ（ｌｃｍ（Ｐ１，Ｐ２），Ｐ３）＝ｌｃｍ（Ｐ１，Ｐ２，Ｐ３）で発生することがわかる。以上のことから、三重衝突を一つの衝突と数える場合の性能基準値は、単純な衝突のみを考慮した性能基準値から、三重衝突の寄与分を引くことで得られ、次式のように示される。
【００３９】
【数１０】
0003798720.tif 000011
【００４０】
ただし、δｉｊは数式３と同様にメッセージｉとメッセージｊが衝突すれば１、衝突しない場合は０である。またδｉｊｋは、メッセージｉ，ｊ，ｋが三重衝突する場合は１、しない場合は０である。初回送信時間が具体的に与えられた時、δｉｊ，δｉｊｋの値を算術的に決定する方法は、上に述べた通りである。
【００４１】
多重衝突をすべて考慮することも原理的には可能であり、ほぼ同様に説明できる。しかしながら、多重衝突は単純衝突に比べて発生の絶対数が少ない上、その一方でたとえば三重衝突を考慮する際には、メッセージ全体から三つの異なるメッセージを取り出す組み合わせを全て調べる必要がある。この組み合わせの総数はメッセージ数のほぼ３乗のオーダーであり、メッセージ数が増加した場合は性能基準値の計算自体に多大な時間がかかる。四重衝突・五重衝突などを考慮すれば、さらに一層の計算時間がかかる。これらのこともあり、現状では多重衝突を考慮する必要性はそれほど高くないと思われる。
【００４２】
簡単な例を用いて説明する。３個のメッセージの送信周期が、短い順に
４，６，８
であったとする。それぞれの初回送信時間が
２，３，４
であるとすると、これらのメッセージは衝突しない。このことを見るには性能基準値が０であることを確認すればよいが、それには送信周期と初回送信時間の組のペア（４，２）と（６，３），（６，３）と（８，４），（４，２）と（８，４）それぞれの性能基準値が０であることを確認すればよい。（４，２）と（６，３）については、３−２＝１が送信周期の最大公約数ｇｃｄ（４，６）＝２で割り切れないため、性能基準値は０である。（６，３）と（８，４）については、４−３＝１が送信周期の最大公約数ｇｃｄ（６，８）＝２で割り切れないため、性能基準値は同様に０である。最後に（４，２）と（８，４）については、４−２＝２が送信周期の最大公約数ｇｃｄ（４，８）＝４で割り切れず、これも性能基準値が０となる。この程度であれば、人手で初回送信時間を設定することが可能である。
【００４３】
８個のメッセージの送信周期が、短い順に
２５，３０，３５，４０，４５，５０，５５，６０
であったとする。この時、それぞれの初回送信時間を
１５，１７，４，２，１３，５，１１，４８
とすると、メッセージは衝突しないことが上に述べたようにして確認できるが、メッセージ数が８個に増えたため確認は面倒であり、そのような初回送信時間設定を人手で発見することは一層困難になる。なお、上記の初回送信時間設定は、本発明の一方法に基づいて求めたものである。実際のシステムではさらにメッセージ数が多いことから、良好な初回送信時間設定を人手により求めることはほぼ不可能であろう。
【００４４】
これまで述べた例では、メッセージが衝突しない初回送信時間設定を発見できたが、すべての場合に良好な初回送信時間設定が必ず見つかるわけではない。例えば、二つのメッセージの送信周期が短い順に
５，７
であったとしする。すると、初回送信時間ｍ１，ｍ２をどのように設定しても、ｍ１−ｍ２はｇｃｄ（５，７）＝１で割り切れることから、メッセージは周期ｌｃｍ（５，７）＝３５で衝突する。特に性能基準値は１／３５で一定である。
【００４５】
メッセージの送信周期が与えられた時、メッセージ衝突回数ができるだけ少なくなるように初回送信時間を設定するためには、上記性能基準値を最小にするという最適化問題を解けばよい。最適化問題には線形計画法や凸計画法といった良く知られた解法が存在するが、ここでの問題に適用できるものではないため、探索などのヒューリスティクスを用いて解くことを試みる。ヒューリスティクスとしてしばしば用いられるものに、乱数などを用いる並列的探索手法や、与えられた出発点を局所探索などによって改良していく逐次的探索手法がある。本発明に係る初回送信時間設定においても、並列的探索と逐次的探索をそれぞれ単独に用いたり、適宜組み合わせてもよい。
【００４６】
並列的探索としては、乱数などを用いて多数の初回送信時間設定を生成し、それら初回送信時間設定のメッセージ衝突に関する性能基準値を算出し、そのうちで性能基準値が最も小さいものを選ぶといった方法が考えられる。次に述べるのは、その一形態である。
【００４７】
図２は、乱数発生等による並列的探索に基づく初回送信時間設定の処理手順（方法１）を示すフローチャートである。
（方法１）
１．与えられた数Ｎに対して、乱数などを用いてメッセージ初回送信時間設定をＮ個生成する（ステップＳ２〜Ｓ５）。
【００４８】
２．それぞれの初回送信時間設定に対し、メッセージ衝突に関する性能基準値を計算する（ステップＳ４）。
【００４９】
３．性能基準値が最小の初回送信時間設定を選抜する、もしくは性能基準値が上位Ｍ個の初回送信時間設定を選抜する（ステップＳ６）。
【００５０】
この方法１の実現は簡単であるが、問題が難しい場合、優れた初回送信時間設定を得るためにはＮを非常に大きくする必要がある。これには、大量の計算機資源を消費するおそれがある。
【００５１】
逐次的探索としては、与えられた初回送信時間から出発し、メッセージの初回送信時間を逐次的に変更していく局所探索が考えられる。変更前と変更後の初回送信時間の優劣は、メッセージ衝突に関する性能基準値を算出することで比較できる。探索をどう打ち切るかとか、初回送信時間設定のどの部分をどう変更するかなどについて、多くのバリエーションが考えられることは明らかである。この方法の難点としては、局所最適化に陥りやすいことがある。また探索の出発点である初回送信時間設定の性能基準値が悪ければ、局所探索を行っても良好な初回送信時間設定を発見することは難しい。次に述べるのは、局所探索の一形態である。ここでは性能基準値が悪くならない限り探索を行い、悪くなった時点で探索を打ち切っているが、局所探索がこの方法に限られるわけではないことは言うまでもない。
【００５２】
図３は、局所探索に基づく初回送信時間設定の処理手順（方法２）を示すフローチャートである。
（方法２）
１．ある初回送信時間設定が与えられたとする。それぞれのメッセージについて、それが他のメッセージと衝突する頻度を算出する。尚、この頻度は性能基準値とほぼ同様に定義できるもので、数式４のｆｉ（後述）とする。この数値が大きいメッセージほど、他のメッセージと頻繁に衝突すると考えられる（ステップＳ１２）。
【００５３】
２．上記の頻度が最大であるメッセージに対し、初回送信時間を再設定する（ステップＳ１４）。得られた初回送信時間設定の性能基準値がこれまでのものより悪くなければ（ステップＳ１６＝ＮＯ）、上記の頻度が二番目に大きいメッセージに対して同様の再設定を行う。以下これを繰り返す（ステップＳ１３〜ステップＳ１８）。得られた初回送信時間設定の性能基準値がこれまでのものよりも悪い場合（ステップＳ１６＝ＹＥＳ）は、そこで探索を終了し、直前の初回送信時間設定を返り値とする。
【００５４】
上述したように、並列的探索と逐次的探索を適宜組み合わせることも可能である。乱数等により大量に生成した初回送信時間の中から上位のものを選択し、それらを出発点に逐次的探索を行うのはその一例である。この方法では、大量に生成した初回送信時間の中から、メッセージ衝突に関する性能基準値が優れたものを選抜することで、局所探索の出発点として良好なものを得ることができる。これら良好な出発点から局所探索を行い、得られた初回送信時間設定中にメッセージ衝突に関する性能基準値が最良または上位のものを選択すれば、並列探索単独の場合や逐次探索単独の場合よりも、計算時間ならびに性能基準値の点で有利と考えられる。次に述べるのは、このような方法の一形態である。
【００５５】
図４は、並列的探索と逐次的探索とを併用した場合の初回送信時間設定の処理手順（方法３）を示すフローチャートである。この方法３は並列的探索を基本とし、方法２の手順すなわち局所探索をステップＳ３９において利用している。
【００５６】
（方法３）
１．自然数Ｌ、Ｍ（＜Ｌ）、Ｎが与えられたとする。乱数などを用いてメッセージの初回送信時間設定をＬ個設定（ステップＳ３２〜Ｓ３５）し、その中から性能基準値が良好なものをＭ個選抜する（ステップＳ３６）。
【００５７】
２．Ｍ個それぞれを出発点として方法２の探索をＮ回行い（ステップＳ３８〜Ｓ４０）、得られた初回送信時間設定から性能基準値が最小の初回送信時間設定を選抜する（ステップＳ４１）。
【００５８】
３．上記２．で選抜されたＭ個の初回送信時間設定のうちで、性能基準値が最良のものを選抜する、もしくは性能基準値が上位のものを何個か選抜する（ステップＳ４３）。
【００５９】
最近よく知られるようになった遺伝的アルゴリズムは、多くの親データから交差や変異などにより優れた子孫データを生成するというものであり、並列的探索と逐次的探索を組み合わせたものであるといえる。このような遺伝的アルゴリズムや、さらにタブサーチといったモダンヒューリスティクスを、初回送信時間設定問題に適用してもよいことは明らかである。本発明に従い、初回送信時間設定問題をメッセージ衝突に関する性能基準値の最適化問題として定式化したことで、既に提案されている多くの最適化手法が適用できるようになる。なお、最適化手法は本実施形態で例示したものに限らないことは言うまでもない。
【００６０】
以上では、メッセージに関する性能基準値が最小な初回送信時間設定をシステムが自動的に探索し設定する状況を考えたが、場合に応じて、設計者が設定した初回送信時間を出発点に、性能基準値がより良いものを自動的にシステムが求めるといった実施形態や、システムが設定した初回送信時間を設計者が少しだけ修正するような実施形態も考えられる。
【００６１】
設計者がメッセージの優先度を指定できたり、また初回送信時間の最大値と最小値を設定できたりすることが、実際の使用の際はしばしば重要である。初回送信時間の最大値・最小値が設定された場合は、乱数等で初回送信時間候補を発生する際に、与えられた最小値以上であって、かつ与えられた最大値以下であるような初回送信時間候補を発生するように修正すればよい。
【００６２】
優先度が与えられた場合に、優先度が高いメッセージほど衝突が少なくなるようにするための手法について簡単に説明する。その一つは、性能基準値自体を優先度を反映する形にすることであり、もう一つは、通常の（優先度を考慮しない）性能基準に基づき、性能基準値が良好な初回送信時間設定を複数個発生させた上で、優先度を反映した性能基準に基づきその中から良好な初回送信時間設定を選出するというものである。メッセージの優先度を反映した性能基準があれば、どちらの方法にも適用可能である。メッセージの優先度を反映した性能基準値はいくつか考えられるが、ここでは、本来の性能基準値をベースにした性能基準値の例を示す。まず、基本的な性能基準値は、メッセージごとの性能基準値の和と考えられることに注意する。すなわち、
【数１１】
0003798720.tif 000012
【００６３】
であることから、メッセージｉが他のメッセージとどれだけ衝突するかを表わす性能基準値として、
【数１２】
0003798720.tif 000013
【００６４】
を計算すれば、数式３の性能基準値ｆはメッセージごとの性能基準値ｆｉの総和となる。
【００６５】
【数１３】
0003798720.tif 000014
【００６６】
メッセージｉの優先度は正数ｐｉ＞０で与えられ、優先度が高いメッセージほどｐｉは小さいとする。例えば、最も優先度が高いメッセージが優先度１、次が優先度２、その次が優先度３、といった設定はよく使われる（メッセージの優先度を考えない場合は、すべてのメッセージに同一の優先度（たとえば１）が与えられたと考えられる）。優先度を反映した性能基準値の一例として、メッセージごとの性能基準値ｆｉの次のような重み付き和：
【数１４】
0003798720.tif 000015
【００６７】
を考えることができる。重みは１／ｐｉであるから、優先度が高いメッセージほど重みが大きくなる。もちろん、１／ｐｉ以外にも種々の関数形が重みとして利用できることは言うまでもない。
【００６８】
なお、本発明は上述した実施形態に限定されず種々変形して実施可能である。
【００６９】
【発明の効果】
以上説明したように、本発明によれば、メッセージ送信が同時に発生した場合のメッセージ衝突によるメッセージ内容の紛失・変質など回避すべく、最適なメッセージ初回送信時間の設定値を算出するための方法及びプログラムを提供できる。また、本発明に従い算出されたメッセージ初回送信時間の設定値を設計者に提示することでメッセージ衝突回避によるシステム性能改善を図るための設計支援を実現できる。
【００７０】
本発明は、ＦＡ（ファクトリーオートメーション）や車載／航空機内ネットワークなど、外部からの情報をリアルタイムに処理する必要のあるシステムに応用できる。さらにこれら以外にも、ネットワーク監視システム、プラント監視システム、交通管制システムなどさまざまなシステムに往々可能である。
【図面の簡単な説明】
【図１】本発明の一実施形態に係る初回送信時間設定最適化システムの概略構成を示すブロック図
【図２】乱数発生等による並列的探索に基づく初回送信時間設定の処理手順（方法１）を示すフローチャート
【図３】局所探索に基づく初回送信時間設定の処理手順（方法２）を示すフローチャート
【図４】並列的探索と逐次的探索とを併用した場合の初回送信時間設定の処理手順（方法３）を示すフローチャート
【符号の説明】
１…メッセージ送信周期設定部
２…性能基準値算出部
３…初回送信時間設定生成部
４…記憶装置
５…シミュレータ
６…出力装置
【図１】
0003798720.tif 000016
【図２】
0003798720.tif 000017
【図３】
0003798720.tif 000018
【図４】
0003798720.tif 000019