(57)【要約】【課題】データが昇順又は降順にソートされた配列データ群から所望のデータを検索するための二分検索方法にて、検索の頻度がデータ毎に異なる場合の検索効率を向上させる。【解決手段】配列データ群全体を検索範囲とした検索開始位置のデータと検索対象データとが一致するか否かを判定する比較判定を行い（Ｓ１０２０）、一致しない場合に配列データ群を２分した領域の何れかに検索範囲を絞りこんで同様に比較判定を行う、ということを繰り返す上記の二分検索方法にて、データ毎に、検索の頻度を考慮した単位時間あたりの比較判定回数を、上記検索開始位置を配列データ群の先頭から末尾の各位置にした場合のそれぞれについて算出する。全データについての単位時間あたりの比較判定回数の和が最も小さくなる位置を、配列データ群全体を検索範囲とした初回の検索開始位置とする（Ｓ１１０）。【選択図】図５
2009040106.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークにおいてやりとりされるデータフレームに割り当てられる識別番号を昇順或いは降順に並べた配列データ群から、所望のデータフレームについての前記識別番号（以下、対象識別番号と言う）を検索するための二分検索方法であって、
前記配列データ群全体を検索範囲とした検索開始位置（以下、初回検索開始位置と言う）における識別番号と前記対象識別番号とを比較して、両者が一致するか否かを判定すると共に、一致しないと判定したならば、その両者の大小関係に基づき、その対象識別番号が前記配列データ群の前記初回検索開始位置よりも前半部分にあるべきか後半部分にあるべきかを判定する比較判定ステップを備え、
前記初回検索開始位置を境にした前記配列データ群における前記前半部分及び前記後半部分のうち、前記対象識別番号があるべき部分を新たな検索範囲とすると共にその検索範囲について予め定められる検索開始位置に基づき前記比較判定ステップを実行し、前記比較判定ステップを、検索範囲の検索開始位置における識別番号と前記対象識別番号とが一致するか、或いは新たな検索範囲を設定できなくなるまで繰り返すようになっている二分検索方法において、
前記データフレームの送信或いは受信毎に、その送信或いは受信に係るデータフレームの識別番号を前記配列データ群から検索するようになっており、
前記データフレーム毎に、そのデータフレームの送信周期に基づき、そのデータフレームの識別番号を検索するために実行される前記比較判定ステップの単位時間あたりの実行回数を、前記配列データ群の先頭から末尾までの各位置を前記初回検索開始位置とした場合のそれぞれにおいて算出する実行回数算出ステップと、
前記配列データ群の先頭から末尾までの各位置のうち、前記実行回数算出ステップで前記データフレーム毎に算出した前記比較判定ステップの実行回数の和が最も小さくなる位置を算出する位置算出ステップとを備え、
前記配列データ群の先頭から末尾までの各位置のうち前記位置算出ステップで算出した位置を、前記初回検索開始位置とすることを特徴とする二分検索方法。
【請求項２】
請求項１に記載の二分検索方法において、
前記ネットワークに接続され、前記配列データ群を記憶する電子制御装置において、その電子制御装置が前記ネットワークを介して受信したデータフレームの識別番号を前記配列データ群から検索するために用いられ、
前記実行回数算出ステップ及び前記位置算出ステップは、前記電子制御装置の起動の際に順次実行されることを特徴とする二分検索方法。
【請求項３】
車両内のネットワークに接続され、前記車両を制御する電子制御装置であって、
前記ネットワークにおいてやりとりされるデータフレームに割り当てられる識別番号を昇順或いは降順に並べた配列データ群を記憶し、受信したデータフレームに割り当てられた識別番号（以下、対象識別番号と言う）をその配列データ群から検索するための検索手段として、
前記配列データ群全体を検索範囲とした検索開始位置（以下、初回検索開始位置と言う）における識別番号と、前記対象識別番号とを比較して、両者が一致するか否かを判定すると共に、一致しないと判定したならば、その両者の大小関係に基づき、その対象識別番号が配列データ群の前記初回検索開始位置よりも前半部分にあるべきか後半部分にあるべきかを判定する比較判定処理を行う比較判定手段を備え、
前記比較判定手段は、前記初回検索開始位置を境にした前記配列データ群における前記前半部分及び前記後半部分のうち、前記対象識別番号があるべき部分を新たな検索範囲とすると共にその検索範囲について予め定められる検索開始位置に基づき前記比較判定処理を実行し、前記比較判定処理を、検索範囲の検索開始位置における識別番号と前記対象識別番号とが一致するか、或いは新たな検索範囲を設定できなくなるまで繰り返すようになっている電子制御装置において、
前記検索手段は、
前記データフレーム毎に、そのデータフレームの送信周期に基づき、そのデータフレームの識別番号を検索するために実行される前記比較判定処理の単位時間あたりの実行回数を、前記配列データ群の先頭から末尾までの各位置を前記初回検索開始位置とした場合のそれぞれにおいて算出する実行回数算出手段と、
前記配列データ群の先頭から末尾までの各位置のうち、前記実行回数算出手段により前記データフレーム毎に算出された前記比較判定処理の実行回数の和が最も小さくなる位置を算出する位置算出手段とを備え、
前記比較判定手段は、前記配列データ群の先頭から末尾までの各位置のうち前記位置算出手段により算出された位置を前記初回検索開始位置として、前記比較判定処理を実行することを特徴とする電子制御装置。
【請求項４】
請求項３に記載の電子制御装置において、
当該電子制御装置の起動の際に、前記実行回数算出手段及び前記位置算出手段を起動する起動制御手段を備えていることを特徴とする電子制御装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、二分検索方法、及びその二分検索方法を用いて、検索対象のデータフレームを、データフレームを並べた配列データ群から検索する電子制御装置に関する。
【背景技術】
【０００２】
従来、データが昇順或いは降順にソートされた配列データ群から検索対象のデータを高速に検索できる二分検索が知られている。
この種の二分検索では、配列データ群の中央のデータと検索対象のデータとを比較して、一致すれば検索を終了し、一致しない場合にはその両者の大小関係に基づき、検索対象のデータが配列データ群の中央よりも前半部分にあるか後半部分にあるかを判断する。そして、配列データ群のうち、検索対象のデータが含まれていると判断した前半部分、或いは後半部分を新たな検索範囲として、その新たな検索範囲の中央のデータと検索対象のデータとを比較する。以後、同様である。このような処理を、検索範囲の中央のデータと検索対象のデータとが一致するか、或いは新たな検索範囲を設定できなくなるまで（具体的に、検索範囲を構成するデータが１つになるまで）繰り返す。尚、検索範囲の中央のデータと検索対象のデータとが一致することがなければ、検索対象のデータは配列データ群には含まれていないということになる。
【０００３】
図８を用いてより具体的に説明する。
図８は、例えば車両を制御する電子制御装置（以下、ＥＣＵと記載する）において実行される二分検索処理を表すフローチャートである。車両では、ＥＣＵがネットワークを介して接続され、そのＥＣＵは、ＣＡＮ（Ｃｏｎｔｒｏｌｌｅｒ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）プロトコルで、所定のデータが含まれるＣＡＮフレームをやりとりする。ＣＡＮフレームには、そのＣＡＮフレームを識別するためのＣＡＮＩＤも含まれている。
【０００４】
そして、ＥＣＵは、ネットワークにおいてやりとりされるＣＡＮフレームそれぞれについてのＣＡＮＩＤを昇順或いは降順にソートした配列データ群を記憶しており、ＣＡＮフレームを受信すると、その受信したＣＡＮフレームのＣＡＮＩＤ（検索対象のＣＡＮＩＤであり、以下、Ｔａｒｇｅｔと記載する）を配列データ群から検索するようになっている。尚、図８において、インデックスとは、配列データ群を構成するデータ（ＣＡＮＩＤ）のそれぞれに通して付与される番号である。
【０００５】
この二分検索処理では、まず、Ｓ１０１０で、配列データ群の先頭に付与されたインデックス（Ｌｏ）と、その配列データ群の末尾に付与されたインデックス（Ｈｉ）とを取得する。このＬｏ〜Ｈｉまでの範囲が、検索範囲となる。また、Ｓ１０１０では、検索結果（Ｒｅｓｕｌｔ）として、「未一致」を設定する。具体的に、検索結果（Ｒｅｓｕｌｔ）が格納される記憶領域に、「未一致」の旨の情報を格納する。尚、Ｔａｒｇｅｔが配列データ群の何れかのＣＡＮＩＤと一致したならば、言い換えると、Ｔａｒｇｅｔが配列データ群にあれば、検索結果（Ｒｅｓｕｌｔ）として「一致」を設定する（後述するＳ１０９０）。
【０００６】
Ｓ１０１０の後は、Ｓ１０２０に進み、Ｒｅｓｕｌｔが未一致（Ｒｅｓｕｌｔ＝未一致）で、かつＬｏ≦Ｈｉであるか否かを判定し、Ｒｅｓｕｌｔ＝未一致、かつＬｏ≦Ｈｉでないと判定すると、そのまま当該処理を終了する。例えば、Ｒｅｓｕｌｔ＝一致であれば、Ｔａｒｇｅｔが配列データ群にあると判断し、そのまま当該処理を終了する。また例えば、検索範囲を構成するデータが０個の場合は、Ｌｏ≦Ｈｉが成立せず、そのまま当該処理を終了する。
【０００７】
一方、Ｓ１０２０で、Ｒｅｓｕｌｔ＝未一致、かつＬｏ≦Ｈｉであると判定すると、Ｓ１０３０に移行し、（Ｌｏ＋Ｈｉ）／２を、検索開始位置を表すインデックスＭｉｄとする。
【０００８】
次に、Ｓ１０４０に進み、配列データ群においてＭｉｄで指示されるＣＡＮＩＤ（以下、ＣｕｒＫｅｙと記載する）を取得する。
次に、Ｓ１０５０に進み、Ｔａｒｇｅｔが、Ｃｕｒｋｅｙよりも小さいか否かを判定し、Ｔａｒｇｅｔが、Ｃｕｒｋｅｙよりも小さくない（つまり、ＴａｒｇｅｔがＣｕｒｋｅｙ以上）と判定すると、Ｓ１０７０に移行し、Ｔａｒｇｅｔが、Ｃｕｒｋｅｙよりも大きいか否かを判定する。Ｓ１０５０及びＳ１０７０の趣旨は、Ｔａｒｇｅｔと、Ｃｕｒｋｅｙとが一致するか否かを判定すると共に、一致しない場合において、Ｔａｒｇｅｔが、配列データ群の中間（（Ｌｏ＋Ｈｉ）／２）よりも前半部分にあるか後半部分にあるかを判定するものである。
【０００９】
Ｓ１０５０で、ＴａｒｇｅｔがＣｕｒｋｅｙよりも小さいと判定すると、Ｓ１０６０に移行し、Ｍｉｄ−１を、末尾のインデックスＨｉとして新たに設定する。そして、再びＳ１０２０に戻る。これは、検索範囲を、Ｌｏ〜Ｍｉｄ−１の範囲に絞る趣旨である。
【００１０】
次に、Ｓ１０７０で、ＴａｒｇｅｔがＣｕｒｋｅｙより大きくないと判定すると、Ｔａｒｇｅｔ＜Ｃｕｒｋｅｙでもなく、Ｔａｒｇｅｔ＞Ｃｕｒｋｅｙでもない、つまりＴａｒｇｅｔ＝Ｃｕｒｋｅｙと判断して、Ｓ１０９０に移行し、検索結果（Ｒｅｓｕｌｔ）として「一致」を設定する。そしてその後、Ｓ１０２０に戻る。
【００１１】
Ｓ１０９０から戻ったＳ１０２０では、Ｒｅｓｕｌｔ＝未一致でないと否定判定し、そのまま当該処理を終了する。
一方、Ｓ１０７０で、ＴａｒｇｅｔがＣｕｒｋｅｙより大きいと判定すると、Ｓ１０８０に移行し、Ｍｉｄ＋１を、先頭のインデックスＬｏとして新たに設定する。そして、再びＳ１０２０に戻る。これは、検索範囲を、Ｍｉｄ＋１〜Ｈｉの範囲に絞る趣旨である。
【００１２】
このように、検索範囲を徐々に絞り、配列データ群からＴａｒｇｅｔを見つけ出すか、或いは配列データ群にＴａｒｇｅｔが含まれていないと判断する。
この種の二分検索については、例えば特許文献１に記載されている。
【特許文献１】特開平１０−２７６２２５号公報
【発明の開示】
【発明が解決しようとする課題】
【００１３】
ところで、上記のような従来の二分検索では、検索範囲の中央から検索を開始するため、配列データ群を構成するデータ数が一定とすると、所望のＣＡＮＩＤに辿り着くまでの比較判定処理（具体的に、Ｓ１０２０の処理）の回数は一意的に決まる。例えば、ＣＡＮフレーム（Ａ）のＣＡＮＩＤ（Ａ）に辿り着くまでの比較判定処理回数はＸ回、ＣＡＮフレーム（Ｂ）のＣＡＮＩＤ（Ｂ）に辿り着くまでの比較判定処理回数はＹ回、というようになる。
【００１４】
ここで、例えば上記のような車両ネットワークにおいては、ＣＡＮフレームの送信周期は、ＣＡＮフレーム毎に異なる。例えば車両においては精密な制御が要求され、精密な制御を実現するための重要なＣＡＮフレームは頻繁にやりとりされたりする。つまり、送信周期はより小さくなる。一方、重要度がさほど高くないＣＡＮフレームの送信周期は大きくなる。このため、ＥＣＵにおいて、ＣＡＮフレームのＣＡＮＩＤを配列データ群から検索する頻度は、ＣＡＮフレーム毎に異なる。例えば、ＣＡＮフレーム（Ａ）の送信周期が１０ｍｓの場合、ＥＣＵにおいて、そのＣＡＮフレーム（Ａ）のＣＡＮＩＤ（Ａ）の検索頻度は１００回／ｓｅｃとなり、ＣＡＮフレーム（Ｂ）の送信周期が１０００ｍｓの場合、ＥＣＵにおいて、そのＣＡＮフレーム（Ｂ）のＣＡＮＩＤ（Ｂ）の検索頻度は１回／ｓｅｃとなる。
【００１５】
そうすると、ＣＡＮフレーム（Ａ），（Ｂ）の場合について言えば、単位時間（例えば１ｓｅｃ）における比較判定処理回数は、１００Ｘ＋Ｙとなる。このため、Ｙが多少大きくなったとしても、Ｘの値がより小さくなったほうが、単位時間における比較判定処理回数は小さくなり有利である。
【００１６】
ところが、従来の二分検索では、前述のように検索範囲の中央から検索を開始するためＸ，Ｙは一意的に決まり、１００Ｘ＋Ｙが最小となるようにＸ，Ｙが定まるとは限らない。
【００１７】
本発明は、こうした問題に鑑みなされたもので、データが昇順或いは降順にソートされた配列データ群から所望のデータを検索するための二分検索方法において、検索の頻度がデータ毎に異なる場合の検索効率を向上させることを目的とする。
【課題を解決するための手段】
【００１８】
上記目的を達成するためになされた請求項１に記載の二分検索方法は、ネットワークにおいてやりとりされるデータフレームに割り当てられる識別番号を昇順或いは降順に並べた配列データ群から、所望のデータフレームについての識別番号（以下、対象識別番号と言う）を検索するためのものである。
【００１９】
この二分検索方法は、配列データ群全体を検索範囲とした検索開始位置（以下、初回検索開始位置と言う）における識別番号と対象識別番号とを比較して、両者が一致するか否かを判定すると共に、一致しないと判定したならば、その両者の大小関係に基づき、その対象識別番号が配列データ群の初回検索開始位置よりも前半部分にあるべきか後半部分にあるべきかを判定する比較判定ステップを備えている。
【００２０】
そして、初回検索開始位置を境にした配列データ群における前半部分及び後半部分のうち、対象識別番号があるべき部分を新たな検索範囲とすると共にその検索範囲について予め定められる検索開始位置に基づき比較判定ステップを実行し、比較判定ステップを、検索範囲の検索開始位置における識別番号と対象識別番号とが一致するか、或いは新たな検索範囲を設定できなくなるまで繰り返すようになっている。
【００２１】
この二分検索方法では、データフレームの送信或いは受信毎に、その送信或いは受信に係るデータフレームの識別番号を配列データ群から検索するようになっている。
そして、データフレーム毎に、そのデータフレームの送信周期に基づき、そのデータフレームの識別番号を検索するために実行される比較判定ステップの単位時間あたりの実行回数を、配列データ群の先頭から末尾までの各位置を初回検索開始位置とした場合のそれぞれにおいて算出する実行回数算出ステップと、配列データ群の先頭から末尾までの各位置のうち、実行回数算出ステップでデータフレーム毎に算出した比較判定ステップの実行回数の和が最も小さくなる位置を算出する位置算出ステップとを備えている。
【００２２】
そして、配列データ群の先頭から末尾までの各位置のうち位置算出ステップで算出した位置を、初回検索開始位置とするようになっている。
このような請求項１の二分検索方法では、配列データ群全体を検索範囲とした場合の初回検索開始位置が、単位時間あたりの比較判定ステップの実行回数が最も小さくなる位置になる。単位時間あたりの比較判定ステップの実行回数は、データフレームそれぞれの送信周期と、そのそれぞれのデータフレームの識別番号を検索する際に実行されることとなる比較判定ステップの実行回数とに基づき算出されるものである。
【００２３】
このため、データフレーム毎に送信周期が異なる場合でも、その違いを吸収して、全体として比較判定ステップの実行回数を減らすことができる。
例えば送信周期が小さいデータフレームについては、そのデータフレームの識別番号の単位時間あたりの検索頻度は大きくなる。この場合、初回検索開始位置は、その識別番号の検索に要する比較判定ステップの実行回数がより小さくなるような位置としたほうが有利である。
【００２４】
請求項１の二分検索方法ではこのような点を考慮し、検索に要する比較判定ステップの実行回数が全体として小さくなるようにしているため、全体として検索効率が向上する。
ところで、請求項１の二分検索方法はを制御する電子制御装置において利用されることが考えられるが、この場合、請求項２のように構成すると良い。
【００２５】
請求項２の二分検索方法は、請求項１の二分検索方法において、ネットワークに接続され、配列データ群を記憶する電子制御装置において、その電子制御装置がネットワークを介して受信したデータフレームの識別番号を配列データ群から検索するために用いられ、実行回数算出ステップ及び位置算出ステップは、電子制御装置の起動の際に順次実行されることを特徴としている。
【００２６】
車両ネットワークにおいては、車両の精密な制御を実現するためにより高速の通信が望まれ、電子制御装置におけるリソース（つまり、コンピュータを動作させるための資源）の制約も厳しくなる。
【００２７】
この点、請求項２の二分検索方法のように、電子制御装置の起動の際に実行回数算出ステップ及び位置算出ステップが実行されるようにすれば、最適な初回検索開始位置を予め求めておくようにすることができる。このため、例えば車両の運行中のようなリソースの制約がより厳しいときに、最適な初回検索開始位置の算出のためにその貴重なリソースを消費してしまう、ということが生じることを防止することができる。
【００２８】
次に、請求項３に記載の発明は、車両内のネットワークに接続され、車両を制御する電子制御装置であって、ネットワークにおいてやりとりされるデータフレームに割り当てられる識別番号を昇順或いは降順に並べた配列データ群を記憶し、受信したデータフレームに割り当てられた識別番号（以下、対象識別番号と言う）をその配列データ群から検索するための検索手段として、配列データ群を記憶する記憶手段と、配列データ群全体を検索範囲とした検索開始位置（以下、初回検索開始位置と言う）における識別番号と、対象識別番号とを比較して、両者が一致するか否かを判定すると共に、一致しないと判定したならば、その両者の大小関係に基づき、その対象識別番号が配列データ群の初回検索開始位置よりも前半部分にあるべきか後半部分にあるべきかを判定する比較判定処理を行う比較判定手段を備え、比較判定手段は、初回検索開始位置を境にした配列データ群における前半部分及び後半部分のうち、対象識別番号があるべき部分を新たな検索範囲とすると共にその検索範囲について予め定められる検索開始位置に基づき比較判定処理を実行し、比較判定処理を、検索範囲の検索開始位置における識別番号と対象識別番号とが一致するか、或いは新たな検索範囲を設定できなくなるまで繰り返すようになっている電子制御装置である。
【００２９】
この電子制御装置において、検索手段は、データフレーム毎に、そのデータフレームの送信周期に基づき、そのデータフレームの識別番号を検索するために実行される比較判定処理の単位時間あたりの実行回数を、配列データ群の先頭から末尾までの各位置を初回検索開始位置とした場合のそれぞれにおいて算出する実行回数算出手段と、配列データ群の先頭から末尾までの各位置のうち、実行回数算出手段によりデータフレーム毎に算出された比較判定処理の実行回数の和が最も小さくなる位置を算出する位置算出手段とを備え、比較判定手段は、配列データ群の先頭から末尾までの各位置のうち位置算出手段により算出された位置を初回検索開始位置として、比較判定処理を実行する。
【００３０】
このような電子制御装置では、請求項１と同様に、配列データ群全体を検索範囲とした場合の初回検索開始位置が、単位時間あたりの比較判定処理の実行回数が最も小さくなる位置になる。このため、請求項１と同様に、データフレームの識別番号の検索に要する比較判定処理の実行回数が全体として小さくなり、全体として検索効率が向上する。
【００３１】
次に、請求項４に記載の電子制御装置は、請求項３の電子制御装置において、当該電子制御装置の起動の際に、実行回数算出手段及び位置算出手段を起動する起動制御手段を備えている。
【００３２】
このため、電子制御装置の起動の際に、単位時間あたりの比較判定処理の実行回数が最も小さくなる最適な初回検索開始位置が算出されるようになる。よって、請求項２と同様に、例えば車両の運行中のようなリソースの制約がより厳しいときに、最適な初回検索開始位置の算出のためにその貴重なリソースを消費してしまう、ということが生じることを防止することができる。
【発明を実施するための最良の形態】
【００３３】
以下に、本発明の実施形態を図面に基づき説明する。
図１は、本発明が適用された電子制御装置（以下、ＥＣＵと記載する）を備えた車両ネットワークシステム１の概略図である。
【００３４】
図１の車両ネットワークシステム１では、ＥＣＵ１０，２０が、ＣＡＮ（Ｃｏｎｔｒｏｌｌｅｒ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）バス２を介して接続されている。ＣＡＮは、車両ネットワークにおける通信プロトコルである。
【００３５】
図１の車両ネットワークシステム１では、ＥＣＵ１０が、センサ３０から取得したデータを含むＣＡＮフレーム３をＥＣＵ２０に送信すると共に、ＥＣＵ２０は、ＥＣＵ１０から受信したＣＡＮフレーム３に含まれるデータに基づき、アクチュエータ４０を駆動制御する。尚、ＣＡＮフレーム３には、そのＣＡＮフレーム３を識別するためのＣＡＮＩＤが格納されている。また、図示しない他のＥＣＵからも、ＣＡＮフレーム３が送信される。
【００３６】
ＥＣＵ２０は、ＣＡＮバス２を介して受信できたＣＡＮフレーム３のうち、そのＣＡＮフレーム３に含まれるＣＡＮＩＤに基づき自身宛のＣＡＮフレーム３（つまり、自身が処理すべきＣＡＮフレーム３）を判別する。
【００３７】
図２は、ＥＣＵ１０或いはＥＣＵ２０の具体的構成図である。ここでは、ＥＣＵ１０について説明するが、ＥＣＵ２０も同じ構成を備えている。
ＥＣＵ１０は、車両の各部を制御するための制御処理や他のＥＣＵ（例えばＥＣＵ２０）と通信を行うため処理を実行するマイコン１１と、ＣＡＮバス２に接続されて、マイコン１１から与えられるデータに基づく信号をＣＡＮバス２に送出すると共に、ＣＡＮバス２上の信号を、その信号が表すデータに変換するＣＡＮトランシーバ１６と、マイコン１１とＣＡＮトランシーバ１６との間においてデータの受け渡しをしたり、そのデータの処理順を決定する調停制御をしたり、通信エラー処理等を実行するＣＡＮコントローラ１５とを備えている。
【００３８】
マイコン１１は、所定のプログラムに従い動作するＭＰＵ１２と、ＭＰＵ１２が実行するプログラムを格納するＲＯＭ１３と、ＭＰＵ１２による演算結果等が記憶されるＲＡＭ１４とを備えている。
【００３９】
次に、図３は、ＥＣＵ１０及びＥＣＵ２０のマイコン１１に実装されるソフトウェアの構成図である。
受信処理部５０は、ＣＡＮコントローラ１５からの受信通知（ＣＡＮフレーム３を受信した旨の通知）を検出すると共に、ＣＡＮフレーム３の情報、具体的に、ＣＡＮＩＤやデータを取得する。
【００４０】
受信処理部５０は、取得したＣＡＮＩＤを用いて、後述する配列データ７０を二分検索し、そのＣＡＮＩＤが配列データ７０に登録されているか否かを判別する。ＣＡＮＩＤが配列データ７０に登録されていれば、そのＣＡＮＩＤと共に取得したデータを、公開データ６０として登録する。具体的に、公開データ６０用のレジスタに、その取得したデータを格納する。格納先のアドレスは、後述するように、配列データ７０において指示されている。
【００４１】
公開データ６０として登録されたデータは、例えばアクチュエータ４０の制御などに用いられる。
ここで、図４は、配列データ７０を表す図面である。
【００４２】
配列データ７０は、図４に示すように、インデックス、ＣＡＮＩＤ、及びデータ格納アドレスの３つの要素からなる。
インデックスは、行数、具体的に、配列データ７０に登録されるＣＡＮＩＤの数を管理するための番号であり、０からの通し番号となっている。
【００４３】
ＣＡＮＩＤは、後半３桁が実質的に固有の番号（ＩＤ）を示す部分であり、１６進数で表されている。また、前半２桁は、後半３桁が１６進数表示であることを表す符号である。このＣＡＮＩＤは、昇順にソートされている。
【００４４】
データ格納アドレスは、ＣＡＮＩＤとともにＣＡＮフレーム３に含まれているデータの格納場所を示すものである。
次に、図５は、ＭＰＵ１２が実行する本発明に係る二分検索処理を表すフローチャートである。この処理は、ＥＣＵ１０，２０がＣＡＮフレーム３を受信する毎に実行され、その受信したＣＡＮフレーム３のＣＡＮＩＤ（図５において、Ｔａｒｇｅｔと記載する）を配列データ７０から検索する処理である。尚、図５において、図８と同じステップについては同じ符号を付している。
【００４５】
この図５の処理では、Ｓ１０１０で配列データ７０の先頭インデックス（Ｌｏ）及び配列データ７０の末尾インデックス（Ｈｉ）を取得し、検索結果Ｒｅｓｕｌｔに「未一致」を設定すると、次に、Ｓ１１０に進む。
【００４６】
Ｓ１１０では、検索を開始する位置（以下、検索開始位置と記載する）のインデックスを示すＭｉｄに、初回検索開始位置ＦｓｔＰｏｓを設定する。初回検索開始位置ＦｓｔＰｏｓは、後述する図６のＳ２９０で算出されるものである。
【００４７】
次に、Ｓ１０２０に進み、検索結果Ｒｅｓｕｌｔ＝未一致、かつＬｏ≦Ｈｉでないと判定すると（Ｓ１０２０：ＮＯ）、そのまま当該処理を終了し、一方、検索結果Ｒｅｓｕｌｔ＝未一致、かつＬｏ≦Ｈｉであると判定すると（Ｓ１０２０：ＹＥＳ）、Ｓ１０４０に移行する。
【００４８】
Ｓ１０４０では、配列データ７０のうち、Ｍｉｄにより指示される位置（つまり、図６のＳ２９０で算出されるＦｓｔＰｏｓ）のＣＡＮＩＤを取得する。尚、以下、Ｍｉｄで指示される位置のＣＡＮＩＤを、Ｃｕｒｋｅｙと記載する。
【００４９】
Ｓ１０４０の後はＳ１０５０に進み、Ｔａｒｇｅｔが、Ｃｕｒｋｅｙよりも小さいか否かを判定し、Ｔａｒｇｅｔが、Ｃｕｒｋｅｙよりも小さいと判定すると（Ｓ１０５０：ＮＯ）、Ｓ１０６０に移行し、Ｍｉｄ−１を、新たな末尾インデックスＨｉとして設定する。これは、検索範囲を、Ｌｏから新たなＨｉ（Ｍｉｄ−１）の範囲に絞る趣旨である。具体的に、検索範囲は、配列データ７０のＭｉｄを境にした前半部分に絞られる。
【００５０】
そして次に、Ｓ１２０に進み、（Ｌｏ＋Ｈｉ）／２を、新たなＭｉｄとして設定する。そしてその後、Ｓ１０２０に戻る。つまり、Ｓ１０６０で検索範囲を絞った後は、その絞った検索範囲については、その中間から検索が開始される。
【００５１】
一方、Ｓ１０５０で、ＴａｒｇｅｔがＣｕｒｋｅｙより小さくない、つまりＴａｒｇｅｔがＣｕｒｋｅｙ以上であると判定すると（Ｓ１０５０：ＮＯ）、Ｓ１０７０に移行し、ＴａｒｇｅｔがＣｕｒｋｅｙより大きいか否かを判定する。
【００５２】
Ｓ１０７０でＴａｒｇｅｔがＣｕｒｋｅｙより大きいと判定すると、Ｓ１０８０に移行し、Ｍｉｄ＋１を、新たな先頭インデックスＬｏとして設定する。これは、検索範囲を、新たなＬｏ（Ｍｉｄ＋１）からＨｉの範囲に絞る趣旨である。具体的に、検索範囲は、配列データ７０のＭｉｄを境にした後半部分に絞られる。そして、Ｓ１２０に進み、その後、再びＳ１０２０に戻る。つまり、前述のように、絞った検索範囲については、その中間から検索が開始される。
【００５３】
一方、Ｓ１０７０で、ＴａｒｇｅｔがＣｕｒｋｅｙより大きくない、つまり、ＴａｒｇｅｔがＣｕｒｋｅｙ以下であると判定すると（Ｓ１０７０：ＮＯ）、ＴａｒｇｅｔとＣｕｒｋｅｙとが一致すると判断してＳ１０９０に移行し、検索結果Ｒｅｓｕｌｔに「一致」を設定する。そしてその後、Ｓ１０２０に戻る。Ｓ１０９０から戻ったＳ１０２０では、Ｒｅｓｕｌｔ＝一致と判定することとなり（Ｓ１０２０：ＮＯ）、当該処理を終了する。
【００５４】
次に、図６は、初回検索開始位置ＦｓｔＰｏｓを算出する初回検索開始位置算出処理の流れを表すフローチャートである。この処理は、ＥＣＵ１０の起動の際に、ＭＰＵ１２により実行される。
【００５５】
この処理では、まずＳ２１０で、配列データ７０（図４参照）を作成する。配列データ７０は、自身が受信するＣＡＮフレーム３が網羅されるように作成する。また、配列データ７０における並び順は、図４の如く、例えばＣＡＮＩＤの昇順とする。尚、配列データ７０を予め例えばＲＯＭ１３に記憶しておいても良い。この場合、Ｓ２１０のステップを省略することができる。
【００５６】
次に、Ｓ２２０に進み、配列データ７０に含まれるＣＡＮＩＤ毎（つまり、ＣＡＮフレーム３毎）に、その送信周期から、検索の頻度（回／ｓｅｃ）を算出する。図５の二分検索処理は、前述のように、ＥＣＵ１０がＣＡＮフレーム３を受信する毎に実行される。そして、この検索の頻度は、図５の処理の実行頻度のことであり、ＣＡＮフレーム３の検索の頻度は、そのＣＡＮフレーム３の送信周期から算出することができる。尚、送信周期は、車両ネットワークシステム１において、ルールとして予め定められており、その情報は例えばＲＯＭ１３に記憶される。また、例えばイベントの発生に伴い送受信されるＣＡＮフレーム３については、送信周期は不定期であるが、この場合、暫定的に定められた送信周期の情報がＲＯＭ１３に記憶される。
【００５７】
次に、Ｓ２３０に進み、配列データ７０の先頭を、検索開始位置Ｎとして設定する。配列データ７０の先頭とは、具体的に、図４の例で言えば、インデックスに０が割り当てられた列である。
【００５８】
次に、Ｓ２４０に進み、ループ処理に入る。ここでは、配列データ７０の行数分（ＣＡＮＩＤの数分）ループする。
まず、Ｓ２５０では、ＣＡＮフレーム３のそれぞれについて、検索開始位置Ｎを初回検索開始位置とした場合のＳ１０２０の処理の実行回数（以下、Ｓ１０２０の処理のことを比較判定処理と記載する）を算出する。言い換えれば、検索範囲の絞り込みの回数を算出する。例えば１回目のループでは、配列データ７０の先頭から検索を開始した場合の比較判定処理の実行回数（検索範囲の絞り込みの回数）を算出することとなる。
【００５９】
次に、Ｓ２６０では、ＣＡＮフレーム３毎に、単位時間あたりの比較判定回数を算出する。単位時間あたりの比較判定処理の実行回数は、Ｓ２２０で算出した検索の頻度（回／ｓｅｃ）に、Ｓ２５０で算出した比較判定処理の実行回数を乗じて算出する。
【００６０】
続いて、Ｓ２７０では、ＣＡＮフレーム３毎に算出した単位時間あたりの比較判定処理の実行回数について、それらの和を算出する。
次にＳ２８０では、Ｎ＋１を新たなＮとする。具体的に、検索開始位置Ｎを、配列データ７０の例えば先頭から１だけ繰り上げる。そして、Ｓ２５０〜Ｓ２７０の処理を繰り返す。以後、同様にして、配列データ７０の先頭から末尾まで（インデックス０〜Ｎまで）のそれぞれについて、単位時間あたりの比較判定処理の実行回数の和（ＣＡＮフレーム３毎に算出したものの和）を算出する。
【００６１】
その後、Ｓ２９０に進み、単位時間あたりの比較判定処理の実行回数が最も小さくなる検索開始位置Ｎを算出する。そしてその後、当該処理を終了する。ここで、この単位時間あたりの比較判定処理の実行回数が最も小さくなる検索開始位置Ｎが、図５の処理におけるＳ１１０の初回検索開始位置ＦｓｔＰｏｓとなる。
【００６２】
ここで、図７は、Ｓ２２０，Ｓ２５０〜Ｓ２７０の算出結果を表す表である。図７において、パターン１，２はそれぞれ、検索開始位置Ｎが異なる。つまり、検索開始位置Ｎの数分だけ、具体的に、インデックス０〜Ｎ（図７では０〜８）の数分だけ、パターンが存在する。
【００６３】
そして、図７では、ＣＡＮＩＤ毎（ＣＡＮフレーム３毎）に、送信周期に基づく検索の頻度と（Ｓ２２０）、ＣＡＮＩＤを検索するために実行される比較判定処理（Ｓ１０２０）の実行回数と（Ｓ２５０）、その実行回数と検索の頻度とをかけ合わせた単位時間あたりの比較判定処理の実行回数（Ｓ２６０）とが現れている。
【００６４】
図７において、比較判定処理の実行回数が１となるのは、検索対象のＣＡＮＩＤと、検索を開始した位置（初回検索開始位置）のＣＡＮＩＤとが合致する場合である。例えば、パターン１は、インデックス４の位置から検索を開始した場合の例であり、パターン２は、インデックス２の位置から検索を開始した場合の例である。
【００６５】
そして、図７では、パターン毎（検索開始位置Ｎ毎）に、単位時間あたりの比較判定処理の実行回数の和が算出されている（Ｓ２７０）。その和は、図７の例のように、パターン１とパターン２とを比較すれば、パターン２のほうが小さくなっている。つまり、パターン１とパターン２とを比較すれば、パターン２における検索開始位置Ｎを初回検索開始位置としたほうが、単位時間あたりの比較判定処理の実行回数は少なくて済むことが分かる。このようにして、本実施形態では、単位時間あたりの比較判定処理の実行回数の和が最も小さくなるような検索開始位置Ｎを、初回検索開始位置としている。
【００６６】
以上のように、本実施形態においては、配列データ７０全体を検索範囲とした場合の初回検索開始位置が、その配列データ７０の先頭から末尾までの位置のうち、ＣＡＮフレーム３毎の単位時間あたりの比較判定処理の実行回数の和が最も小さくなる位置になる。具体的に、ＣＡＮフレーム３毎の検索の頻度（ＣＡＮフレーム３毎の送信周期）を考慮して、全体として比較判定処理の実行回数が小さくなる位置が、初回検索開始位置となる。
【００６７】
このため、ＣＡＮフレーム３毎に検索の頻度（送信周期）が異なる場合でも、その違いを吸収して、全体として比較判定処理の実行回数を減らすことができる。このため、検索の効率が向上する。そして、比較判定処理に要する時間を小さくできるため、ＥＣＵ１０，２０の負荷を抑えることができ有利である。
【００６８】
尚、上記実施形態において、Ｓ１０２０，Ｓ１０４０及びＳ１０７０の処理が比較判定ステップ及び比較判定処理に相当し、Ｓ２２０，Ｓ２５０及びＳ２６０の処理が実行回数算出ステップ及び実行回数算出手段に相当し、Ｓ２７０及びＳ２９０の処理が位置算出ステップ及び位置算出手段に相当している。
【００６９】
以上、本発明の一実施形態について説明したが、本発明は上記実施形態に限定されるものではなく、本発明の技術範囲内において種々の形態をとることができる。
例えば、上記実施形態において、配列データ７０ではＣＡＮＩＤが昇順にソートされているが、降順にソートされていても良い。この場合、図５の処理において、Ｓ１０６０の処理とＳ１０８０の処理とを入れ換えることにより対応できる。
【００７０】
また、上記実施形態において、図６の処理は、例えばＥＣＵ１０，２０の外部のツールにより実行されても良い。この場合、その図６の処理結果が、そのツールからＥＣＵ１０，２０に送信され、そのＥＣＵ１０，２０において記憶されるようにすれば良い。
【００７１】
また、上記実施形態において、ＣＡＮフレーム３毎の検索の頻度を、そのＣＡＮフレーム３毎の受信途絶時間から算出しても良い。
【図面の簡単な説明】
【００７２】
【図１】車両ネットワークシステムの概略図である。
【図２】電子制御装置（ＥＣＵ）の具体的構成図である。
【図３】電子制御装置（ＥＣＵ）のマイコンに実装されるソフトウェアの構成図である。
【図４】配列データを表す図である。
【図５】二分検索処理を表すフローチャートである。
【図６】初回検索開始位置算出処理の流れを表すフローチャートである。
【図７】比較判定回数の算出結果を示す図である。
【図８】従来の二分検索処理を表すフローチャートである。
【符号の説明】
【００７３】
１…車両ネットワークシステム、２…ＣＡＮバス、３…ＣＡＮフレーム、１１…マイコン、１２…ＭＰＵ、１３…ＲＯＭ、１５…ＣＡＮコントローラ、１６…ＣＡＮトランシーバ、３０…センサ、４０…アクチュエータ、５０…受信処理部、６０…公開データ、７０…配列データ。
【図１】
2009040106.tif 000003
【図２】
2009040106.tif 000004
【図３】
2009040106.tif 000005
【図４】
2009040106.tif 000006
【図５】
2009040106.tif 000007
【図６】
2009040106.tif 000008
【図８】
2009040106.tif 000009
【図７】
2009040106.tif 000010