(57)【要約】  自己編成ネットワークでは、ビーコンと呼ぶ、存在情報を備えるブロードキャストは、近傍情報、すなわち、特定の装置のネットワーク内に存在している装置に関する情報を探索するうえでのデフォールト手順である。そうしたビーコンは、各装置から周期的に送信される。装置は、ネットワーク内の他の装置の存在が、そうしたものからビーコンを受信すると分かる。本発明の方法は、装置は、その後続するスケジューリングされたビーコンを、その近傍装置全てが同じ周期中に先行ビーコンを受信している場合にスキップすることができるということを示唆するものである。
2007517451.tif 000002
【特許請求の範囲】
【請求項１】
ブロードキャストを自己編成ネットワーク内でスケジューリングする方法であって、
存在情報を備えるブロードキャストを第１の装置から該第１の装置の近傍装置に前記自己編成ネットワーク内で周期TB毎に送信する工程を備え、
前記第１の装置からの存在情報を備えるブロードキャストの送信を、前記第１の装置の近傍全てが前記ブロードキャストを前記第１の装置から周期TCB中に受信している場合にスキップすることを特徴とする方法。
【請求項２】
請求項１記載の方法であって、前記第１の装置からの存在情報を備える前記ブロードキャストの送信は、前記周期TCBの第２の部分中に、前記第１の装置の近傍全てが前記ブロードキャストを前記第１の装置から周期TCBの第１の部分中に受信した場合にスキップすることを備えることを特徴とする方法。
【請求項３】
請求項１記載の方法であって、装置から送信される存在情報を備えるブロードキャストは、近傍装置のリスト内に、前記装置が各装置からのブロードキャストを受信したか否かに関する情報を更に備えることを特徴とする方法。
【請求項４】
請求項３記載の方法であって、前記装置から送信される前記ブロードキャストが、スキップ・ブロードキャスト・ビットを備え、該スキップ・ブロードキャスト・ビットは、存在情報を備えるブロードキャストが前記近傍装置のリスト内の各装置から現行TCB内に受信されている場合に設定されることを特徴とする方法。
【請求項５】
請求項４記載の方法であって、前記装置から送信される前記ブロードキャストがスキップ・ブロードキャスト・ビットを備え、該スキップ・ブロードキャスト・ビットは、
（tCB(i),next−t）＞TBであるという条件と、
存在情報を備えるブロードキャストが前記近傍装置リスト内の各装置から前記現行のTCB内に受信されたという条件との両方が満たされる場合に設定され、
tCB(i),nextは、前記装置が、存在情報を備えるブロードキャストをそこから受信したその装置を検査するよう形成される次の時点であり、tは現在の時間であることを特徴とする方法。
【請求項６】
請求項４記載の方法であり、前記装置は、前記現行周期TCB内の近傍装置リスト内の装置からの存在情報を備えるブロードキャスト全てが前記スキップ・ブロードキャスト・ビットを設定させている場合にブロードキャストをスキップすることを特徴とする方法。
【請求項７】
請求項６記載の方法であって、前記装置は、
前記現行周期TCB内の前記近傍装置リスト内の装置からの存在情報を備えるブロードキャスト全てが前記スキップ・ブロードキャスト・ビットを設定させているという条件と、
（tCB(j),next−t）＞TBであるという条件との両方が満たされる場合にブロードキャストをスキップし、
tCB(j),nextは、前記装置が、存在情報を備えるブロードキャストをそこから受信したその装置を検査するよう形成される次の時点であり、tは現在の時間であることを特徴とする方法。
【請求項８】
請求項4記載の方法であって、（tCB(j),next−t）＞TBである場合、かつ、
前記現行周期TCBにおける近傍装置のリストNj内の装置からの存在情報を備えるブロードキャスト全てが前記スキップ・ブロードキャスト・ビットを設定させているという条件、
又は、
Mk⊂Njの場合、Mk内の装置から現行検査ビーコン周期中に受信された存在情報を備えるブロードキャスト全てが前記スキップ・ブロードキャスト・ビットを設定させており、かつ、Nj＼Mk内の装置が、リストMk内の装置から送信されたブロードキャストの何れかの「LAST＿KNOWN＿BEACON」フィールド内にないという条件との一方が満たされる場合にブロードキャストをスキップし、
前記「LAST＿KNOWN＿BEACON」フィールドは、存在情報を備えるブロードキャストが現行検査ビーコン周期TCB中の最も早い時点でそこから受信されたその装置を示し、tCB(i),nextは、前記装置が、存在情報を備えるブロードキャストをそこから受信したその装置を検査するよう形成される次の時点であり、tは現在の時間であることを特徴とする方法。
【請求項９】
請求項１記載の方法であって、TB＜TCBであることを特徴とする方法。
【請求項１０】
請求項９記載の方法であって、TCB=N*TBであり、N∈N+であることを特徴とする方法。
【請求項１１】
装置であって、請求項１記載の方法を行うことを特徴とする装置。
【請求項１２】
自己編成ネットワークであって、請求項１記載の方法を行う装置を備えることを特徴とする自己編成ネットワーク。
【請求項１３】
コンピュータ・プログラムであって、プログラム可能なコンピュータに、請求項１記載の方法を行わせるコンピュータ命令のプログラムを備えることを特徴とするコンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、自己編成ネットワークにおいてブロードキャストをスケジューリングする方法に関し、この方法は、自己編成ネットワークにおける第１の装置からその近傍装置に毎周期TB、存在情報を備えるブロードキャストを送信する工程を備える。本発明は、装置、及び装置を備える自己編成ネットワークに更に関する。
【背景技術】
【０００２】
自己編成ネットワークは、ネットワーク・インタフェースを備える、ノードと呼ばれる装置集合体が、確立されたインフラや集中化された管理を利用することなく一時的なネットワークを形成することができるネットワークである。自己編成ネットワークのトポロジは、特に、移動体装置が移動することができる、移動体装置の無線ネットワークにおいて急速に変わり得る。通常、２つの無線ノード間の通信は、２つのノードが無線通信の範囲内にある場合にのみ可能である。そうした自己編成ネットワークの既存例として、無線アドホック・ネットワーク（MANET）、マルチホップ・セルラ・ネットワーク（MCN）やパーソナル・エリア・ネットワーク（PAN）がある。自己編成無線ネットワークは、種々の産業アプリケーション、医療アプリケーション、消費者向アプリケーション及び軍事アプリケーションにおいてただちに役に立つものである。
【０００３】
ネットワーク内の各ノードは、ビーコン、すなわち、存在情報を備えるブロードキャストを周期的に送出する。このビーコンを受信するノードは全て、送出元ノードを近傍とみなし、近傍ノードのテーブルを更新する。ビーコンは、自己編成装置の近傍情報を探索するデフォールト手順である。こうしたビーコンは、周期的なものであり、各装置によって周期的に送信されることが要求される。このことは、各装置が、新たな装置の存在を知り、現行の装置がその送信範囲にまだあることを評価することに寄与する。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかし、こうしたビーコンを送信することは、電力及び帯域を消費するものである。ビーコンを効率的にスケジューリングする方法に対する必要性が存在しており、本発明の目的は、そうした方法を提供することである。
【課題を解決するための手段】
【０００５】
上記目的は、本願の最初の段落に記載した方法が、存在情報を備えるブロードキャストの第１の装置からの送信が、その近傍全てがブロードキャストを第１の装置から周期TCB中に受信している場合にスキップされることを特徴とすることによって達成される。これによって、第１の装置の近傍装置に関する情報を失うことなくブロードキャストをスキップするやり方が提供される。ブロードキャスト又はビーコンをスキップすることができる場合、装置内の電力消費と、帯域消費を削減することができる。更に、送信されるブロードキャスト間の衝突を、本発明の方法によって削減することが可能である。自己編成ネットワークは、有線、無線、又はそれらの組み合わせであり得る。ネットワーク内の装置は移動体であっても固定であってもよい。
【０００６】
好ましくは、自己編成ネットワーク内の第１の装置は、その近傍装置である装置のリストを管理する。よって、自己編成ネットワーク内の装置は、その現行の近傍装置を把握する。近傍装置のリストを通常、新たな装置がネットワークに入ったかを検査することにも、装置がネットワークを出たかを検査することにも用いる。
【０００７】
好ましくは、存在情報を備えるブロードキャストの第１の装置からの送信は、その近傍全てがブロードキャストを第１の装置から周期TCBの第１の部分中に受信した場合に、周期TCBの第２の部分中、スキップすることを備える。
【０００８】
好ましい実施例では、装置から送信される存在情報を備えるブロードキャストは、該装置が近傍装置のリスト内の各装置からのブロードキャストを受信したか否かに関する情報を更に備える。これは、近傍装置の存在に関する情報を失うことなくブロードキャストをスキップする時点を判定するやり方を備える。その近傍装置リスト内の各装置からのブロードキャストを当該装置が受信したか否かに関する情報は、存在情報を備えるブロードキャスト内のビットの形式にあり得るものであり、このビットは特定の条件（例えば、以下を参照されたい。）の下で設定され、このビットは、近傍装置がブロードキャストをスキップすべきが否かを受信近傍装置に示す。
【０００９】
好ましくは、TB＜TCBである。TBは、ビーコン周期、すなわち、自己編成ネットワーク内の装置から送信される存在情報を備えるブロードキャスト間の周期であり、TCBは、検査ビーコン周期、すなわち、近傍装置からのブロードキャストの受信の各検査間の周期である。ビーコン周期は好ましくは、ネットワーク内の各装置について等しいものである。しかし、別々の装置のビーコン周期は通常、同期化されていない。同じことが、検査ビーコン周期に当てはまる。なお、装置はビーコンの受信を実質的に連続して検出するが、検査ビーコン周期TCBでの近傍装置からのブロードキャストの受信の検査は、現在近傍の装置を識別する。
【００１０】
更なる好ましい実施例では、TCB＝N*TBであり、ここでN∈N＋である。TCB＝N*TBである場合、ビーコン検査がビーコン送信と同期化され、このことは、2ホップ・トポロジを用いるプロトコルの近傍情報を正しいものに維持するのに役立つ。好ましくは、Nは、２，３、又はより大きな数に等しいものである。
【００１１】
装置から送信される存在情報を備えるブロードキャストは、
（tCB(i),next−t）＞TBであることと、
存在情報を備えるブロードキャストが近傍装置リスト内の各装置から現行のTCB内に受信されたこととの両方の条件が満たされる場合に設定されるスキップ・ビーコン・ビットを備える。ここで、tCB(i),nextは、存在情報を備えるブロードキャストをそこから受信したその装置を検査するよう装置が形成される次の時点であり、tは現在の時間である。このことは、スキップしなければスケジューリングされる次のブロードキャストをスキップし得るか否かを受信局に示すビットであるスキップ・ビーコン・ビットを設定するうえでの条件を正確に示すものである。
【００１２】
好ましくは、装置は、
現行周期TCB内の近傍装置のリスト内の装置からの存在情報を備えるブロードキャスト全てがスキップ・ビーコン・ビットを設定させていることと、
（tCB(j),next−t）＞TBであることとの両方の条件が満たされる場合、ブロードキャストをスキップすることになる。ここで、tCB(j),nextは、存在情報を備えるブロードキャストをそこから受信したその装置を検査するよう装置が形成される次の時点であり、ｔは現在の時間である。
【００１３】
前述の２つの条件とともに、こうした条件は、局がブロードキャストをスキップすることができるか否かを正確に示す。
【００１４】
更に別の好ましい実施例では、第１の装置から送信される存在情報を備えるブロードキャストは、第１の装置の近傍装置のリストを更に備える。このことは、2ホップ・トポロジにおけるルーティングを容易にする。装置は、存在情報を備えるブロードキャストを受信すると、送信元をその近傍として、かつ、リスト内の装置を、２ホップ・トポロジ内の送信装置を介して到達することが可能な装置として導き出す。ブロードキャストにおいてスキップ・ビーコン・ビットを設定する時点と、装置がブロードキャストをスキップすべき時点とに関する、前述の条件と同様な条件を以下に記載する。前述のことは、他のマルチホップ・トポロジにも拡張することが可能である。
【００１５】
本発明による方法の更に別の好ましい実施例では、（tCB(j),next−t）＞TBであり、かつ、
現行周期TCB内の近傍装置のリストNj内の装置からの存在情報を備えるブロードキャスト全てという条件と、
Mk⊂Njのとき、Mk内の装置から現行検査ビーコン周期中に受信される存在情報を備えるブロードキャスト全てがスキップ・ブロードキャスト・ビットを設定させていること、及び、Nj＼Mkにおける装置が、リストMk内の装置から送信されるブロードキャストの何れかの「LAST＿KNOWN＿BEACON」フィールドにないことという条件との一方が満たされる場合にブロードキャストをスキップし、
「LAST＿KNOWN＿BEACON」フィールドは、存在情報を備えるブロードキャストの、現行の検査ビーコン期間TCB中の最も早い時点でそこから受信したその装置を示し、tCB(j),nextは、存在情報を備えるブロードキャストをそこから受信したその装置を検査するよう装置iが形成された次の時点であり、ｔが現在の時間である。Mkは近傍装置のリストNjの部分集合である。よって、Mkは装置jの近傍装置の一部のリストである。Nj＼MkはNjの残り、すなわち、NjにあるがMkにない装置のリストである。
【００１６】
この好ましい実施例は、存在情報を備えるブロードキャスト、すなわち、ビーコンの送信を、情報を喪失することなく削減するやり方を提供する点で、電力及び帯域の消費の更なる最適化を提供する。
【００１７】
なお、「ビーコン」の語は、装置の近傍のリストを場合によってはやはり備える、装置の存在を示すブロードキャストを包含するものとする。更に、スキップ・ブロードキャスト・ビット及びスキップ・ビーコン・ビットの語は本明細書及び特許請求の範囲では同義に用いる。
【００１８】
自己編成ネットワークにおける装置は、同様なタイプの装置であっても異なるタイプの装置であってもよく、上記方法を用いることができる自己編成ネットワークの重要な特徴は、装置がブロードキャストを互いに送受信することができるはずであるということである。しかし、自己編成ネットワーク内の装置は、好ましくは、他のタイプの情報を交換することができるはずである。
【発明を実施するための最良の形態】
【００１９】
本発明は、好ましい実施例に関して、かつ、添付図面を参照して以下に更に詳細に説明する。
【実施例】
【００２０】
図１は、4つのノードA、B、C及びDを備えた自己編成ネットワーク１００を示す。「ノード」の語は、自己編成ネットワーク１００内に存在する移動体装置(i,j)である。２つのノード間の矢印は、ノードが互いに通信することができることを示す。通常、これは、ノードが互いに無線通信範囲にあり、かつ、お互いに情報を交換することができることを意味する。
【００２１】
ノードAは、３つの近傍、すなわち、B、C及びDを有する。ノードB及びCは２つの近傍をそれぞれ有する、すなわち、ノードBは近傍A及びCを有し、ノードCは近傍A及びBを有する。最後に、ノードDは１つの近傍、すなわちAのみを有する。この自己編成ネットワーク１００を、図２乃至図４の基礎として用いる。
【００２２】
図２は、図１に示す自己編成ネットワーク１００内のノードからのブロードキャストのタイミングの例を示す。ブロードキャストは、存在情報を備えており、自己編成ネットワーク１００内の何れかのノードからその近傍移動体装置に送られる。そうしたブロードキャストをビーコンと呼ぶ。ビーコンは、ネットワーク内の各ノード、すなわち、移動体装置から周期的に送られる。
【００２３】
図２中の水平方向の線は、図の上部にある数に相当する、秒単位の時間を示す。垂直方向の線は、ビーコンを送信する時点を示し、矩形を備えた、垂直方向の線は、近傍ノードからのブロードキャストの受信を検査する時点に相当し、円によって実質的に囲まれた、垂直方向の線は、本発明の方法によって、ビーコンをスキップすることが可能な時点に相当する。
【００２４】
前述のように、ビーコン周期TBは、ネットワーク内の各移動体装置について等しい。しかし、別々の移動体装置のビーコン周期は通常同期化されていないので、ビーコンを送信する時点は、別々のノードについて異なる。同じことが、検査ビーコン周期TCBに当てはまる。
【００２５】
存在情報を備えるブロードキャスト間の時間、すなわち、ビーコン周期TBはノード毎に同じであり、図２では2秒に等しい。近傍ノードからのブロードキャストの受信の各検査間の時間は、図２では4秒に等しい検査ビーコン周期TCBである。
【００２６】
ビーコン周期TB及び検査ビーコン周期TCBをノード毎に同期化するので、受信ビーコンを検査する時点はノード毎にビーコンを送信する時点と一致する。しかし、図２では、ノードA、B、C及びDのそれぞれは、時間をシフトさせたビーコンを送信し始めるので、ビーコンを、ノードAは1秒の時点で、ノードBは1.5秒の時点で、ノードCは２秒の時点で、ノードDは2.5秒の時点で送信し始める。
【００２７】
全ての近傍ノードによるビーコン送信後、各ノードはその近傍、すなわち、その近傍トポロジの知識を有する。例えば、３つの近傍B、C及びDを有することをノードAは知っている。ノードB及びCは、それらの２つの近傍について知っており、ノードDはその近傍Aについて知っている。
【００２８】
ノードA、B、C及びDの近傍トポロジが、図示する期間（1秒から16.5秒までの間）、安定した状態に留まるものとする。このことは、2ホップ・トポロジに用いる近傍情報を正しいものに維持することに寄与する。2ホップ・トポロジでは、各ノードiは、その近傍ノードの更新リストNiを管理する。ノードiでのビーコン検査後、正しいリストNiは、既知であり、2ホップ・トポロジや他のマルチホップ・トポロジに用いる対象の、次にスケジューリングされるビーコンとともに送信することができる。
【００２９】
本発明の方法によって、スケジューリングされたビーコンをスキップすることができる場合を以下に説明する。ノードが、受信ビーコンを検査する時点のずっと前にその近傍ノード全てからビーコンを受信すると、現行の検査ビーコン周期内に他の近傍ノードの全てからビーコンをやはり受信したという条件の下で、スケジューリングされたビーコンをスキップする旨をその近傍に通知する。前述のように、移動体装置はビーコンの受信を実質的に連続して検出するが、検査ビーコン周期TCBでの近傍移動体装置からのブロードキャストの受信の検査は、現在近傍の移動体装置を識別する。
【００３０】
tがノードiの現在の時間であり、Niがノードiの近傍リストであり、tCB(i),nextは、存在情報を備えるブロードキャストをそこから受信したその移動体装置を検査するようノードiが形成される次の時点であり、TBはビーコン周期を表し、後続ビーコンとともに送信する対象のスキップ・ビーコン・ビットをノードが設定する条件は、
(tCB(i),next−t)＞T  (1)、及び、
存在情報を備えるブロードキャストが、近傍移動体装置のリストNi内の各移動体装置から現行TCB内に受信されていること  (2)
である。
【００３１】
ノードjは、
現行TCB周期内の近傍移動体装置のリストNj内の移動体装置からの存在情報を備えるブロードキャスト全てが、スキップ・ビーコン・ビットを設定させており  (3)、かつ、
(tCB(j),next−t)＞TB                                                (4)
である場合、その後続ビーコン送信をスキップし、
ここで、tが現在の時間であり、tCB(j),nextは、存在情報を備えるブロードキャストをそこから受信したその移動体装置を検査するようノードjが形成される次の時点である。
【００３２】
ノードAの２つの検査ビーコン時点間の時間、例えば、５秒と9秒との間の時間を次に検討する。6.5秒の時点の直後に、ノードAは各近傍ノードからビーコンを受信しているので、前述の条件（１）及び（２）が満たされる。よって、ノードAは、スキップ・ビーコン・ビットをそのビーコンに設定し、スキップ・ビーコン・ビットとともにビーコンを7秒の時点で送信することが可能である。（近傍ノード間の送信時間による）短い時間スパンの後、ノードB、C及びDは、設定スキップ・ビーコン・ビットを備えたビーコンをノードAから受信する。上記ノードは、前述の条件（３）及び（４）を検査して、後続のスケジューリングされたビーコンをスキップすることが可能かを確かめる。条件（３）はノードBの場合、満たされないが、それは、設定されたスキップ・ビーコン・ビットを備えるビーコンをノードCから受信していないからである。条件（３）も条件（４）もノードC及びノードDの場合、満たされている。よって、8秒の時点及び8.5秒の時点のそれぞれで、スケジューリングされたビーコンをスキップする。このことは、ノードCの場合、タイムライン上の8秒の時点で円によって囲まれた垂直方向の線として、ノードDの場合、タイムライン上の8.5秒の時点で円によって囲まれた垂直方向の線として、図２に示す。図２に示すように、ノードC及びDのスケジューリングされたビーコンの半分をスキップすることができる。TCB＝2*TBの場合、スケジューリングされたビーコンの8/32=25%をスキップすることが可能である。
【００３３】
図３は、自己編成ネットワークにおけるノードからのブロードキャストのタイミングの例を示す。図2のように、水平方向の線は、図の上部にある数に相当する、秒単位の時間を示す。垂直方向の線は、ビーコンを送信する時点を示し、矩形を備えた、垂直方向の線は、近傍ノードからのブロードキャストの受信を検査する時点に相当し、円によって実質的に囲まれた、垂直方向の線は、本発明の方法によって、ビーコンをスキップすることが可能な時点に相当する。
【００３４】
やはり、存在情報を備えるブロードキャスト間の時間、すなわち、ビーコン周期TBはノード毎に同じであり、図３では2秒に等しい。近傍ノードからのブロードキャストの受信の各検査間の時間は、図3では6秒に等しい検査ビーコン周期TCBである。
【００３５】
スキップ・ビーコン・ビットを設定し、ビーコンをスキップするための条件（１）乃至（４）は、図２を参照して説明したものと同様である。
【００３６】
より多くの割合のビーコンをスキップできることは図３から明らかである。これは、図３中の検査ビーコン周期TCBが3*TBに等しいので、条件（１）及び（４）は、図２中のように、TCB=2*TBである場合と比較して、満たされる頻度が高い。図３では、ビーコンの10/32=31%を、伝統的なスケジューリングと対照的に、スキップすることができる。
【００３７】
新たなノ―ドが自己編成ネットワークに入る場合と、現行ノードが自己編成ネットワークを離れる場合との本発明の方法の機能を以下に説明する。
【００３８】
新たなノードEが自己編成ネットワークに入っており、ノードA及びCの近傍に過ぎないものとする。ノードAは、検査ビーコン時点で受信されたビーコンを検査する場合にのみネットワーク内の新たなノードの知識を有する。よって、ノードAは、前述のように、現行検査ビーコン周期内にその近傍全てからビーコンを受信した場合（条件（１）及び８２））にのみ、ビーコン内にスキップ・ビーコン・ビットを設定する。
【００３９】
ノードCは、次にスケジューリングされたビーコンをスキップしようとしている（条件（３）及び条件（４）が満たされる）が、新たに入ったノードEからのビーコンを受信する場合、次にスケジューリングされたビーコンをスキップすることが可能でないが、それは、ノードEから受信されたビーコンがスキップ・ビーコン・ビットを設定させていないからである（条件（３））。この場合、条件（３）によって、ノードCがその存在を新たな近傍ノードEに確実に示すようになる。
【００４０】
自己編成ネットワークが図１に示すノードA、B、C及びDを備え、ノードCがネットワークを出るものとする。
【００４１】
ネットワーク内の残りのノードからのビーコンをスキップするための条件（２）は、リストNj内の各ノードからビーコンを受信する必要があるということである。(a)ノードCが、ノードA及びBの現行サイクル内でビーコンを送ることなくネットワークを出る。(b)ノードCが、ノードA及びBの現行サイクル内でのビーコンの送出の直後に出る。２つのケースが起こり得る。
【００４２】
ケース(a)では、ノードA及びBは、スキップ・ビーコン・ビットを設定することができないが、それは、それらの近傍のそれぞれからビーコンを受信していない（すなわち、条件（２）が満たされていない。）からである。よって、ノードA及びBからビーコンを受信するノードはそれらの後続のビーコンをスキップすることができないが、それは、条件（３）が満たされていないからである。
【００４３】
ケース(b)では、ノードA及びBは、ビーコンをノードCから受信しており、他の近傍からもビーコンを受信する場合、スキップ・ビーコン・ビットをそれらの次のビーコン内に設定する。ノードは、ノードの移動について分かるのは、現行検査ビーコン周期中にビーコンを既に受信しているという点で、唯一、現行検査ビーコン周期後である。
【００４４】
図４は、自己編成ネットワークにおけるノードからのブロードキャストのタイミングの例であって、ブロードキャストが近傍移動体装置のリストを備える例を示す。図２及び図３と同様に、水平方向の線は、図の上部にある数に相当する、秒単位の時間を示す。垂直方向の線は、ビーコンを送信する時点を示し、矩形を備えた、垂直方向の線は、近傍ノードからのブロードキャストの受信を検査する時点に相当し、円によって実質的に囲まれた、垂直方向の線は、本発明によって、ビーコンをスキップすることが可能な時点に相当する。
【００４５】
やはり、存在情報を備えるブロードキャスト間の時間、すなわち、ビーコン周期TBはノード毎に同じであり、図4では2秒に等しい。近傍ノードからのブロードキャストの受信の各検査間の時間は、図4では4秒に等しい検査ビーコン周期TCBである。
【００４６】
図４は、2ホップ・トポロジにおけるノードのビーコン・スキップ手順を示す。図２及び図３では、各ビーコンはビーコンを送信するノードの送信元アドレスを備えている。図４では、各ビーコンは、ノードiの近傍ノードのリストNiも備えている。更に、各ビーコンは、現行の検査ビーコン期間中の最も早い時点でビーコンを送ったノードを示すフィールド「LAST＿KNOWN＿BEACON」を有している。すなわち、フィールド「LAST＿KNOWN＿BEACON」は、現行の検査ビーコン期間TCB中の最も早い時点でビーコンをそこから受信したそのノードを示す。
【００４７】
7秒の時点で、ノードAのフィールド「LAST＿KNOWN＿BEACON」は「B」に等しいが、それは、Bが、（5.5秒の時点で）ビーコンをAに送信した第１のノードであるからである。同様に、ノードBの場合、「LAST＿KNOWN＿BEACON」は「C」に等しい、等である。
【００４８】
ノードAが、ビーコンを７秒の時点で送信すると、（前述のように）スキップ・ビーコン・ビットを設定させる。ノードC及びDは、図２を参照して説明した理由でそれらの後続ビーコンをスキップする。更に、ノードBは、フィールド「LAST＿KNOWN＿BEACON」を利用し、かつ、2ホップ・トポロジによって（9.5秒の時点でスケジューリングされる）その後続のスケジューリングされたビーコンをスキップする。
【００４９】
例えば、7秒の時点でノードAから送られるビーコンは、フィールド「LAST＿KNOWN＿BEACON」とともにノードAの近傍ノードのリストNAを備えている。リストNAはノードB、C及びDを備えており、フィールド「LAST＿KNOWN＿BEACON」は「B」に等しい。この情報によって、ノードBは、ノードC及びDにノードAを介して到達することが可能であることと、それらのそれぞれが、5.5秒の時点でのビーコンの先行送信の後にノードAにビーコンを送信したこととを導き出すことが可能である。
【００５０】
上記条件（３）はよって、以下に変更することが可能である。
【００５１】
現行周期TCB内の近傍移動体装置のリストNj内の移動体装置からの存在情報を備えるブロードキャスト全てがスキップ・ビーコン・ビットを設定させている（3a）、
又は、
Mk⊂Njの場合、現行検査ビーコン周期に、Mk内の移動体装置から受信される存在情報を備えるビーコン全てがスキップ・ビーコン・ビットを設定させており、かつ、Nj＼Mk内の移動体装置が、リストMk内の移動体装置から送信されるビーコンの何れかの「LAST＿KNOWN＿BEACON」フィールド内になく(3b)、
ここで、Mkは、近傍ノードのリストNjの部分集合であり、よって、Mkは、ノードjの近傍ノードの一部のリストである。Nj＼Mkは、Njの残りの部分、すなわち、NjにあるがMkにないノードのリストである。
【００５２】
条件（１）、（２）及び（４）は変わらない状態に維持されている。なお、条件(3a)は旧条件(3)に等しいので、別の条件(3b)、すなわち、フィールド「LAST＿KNOWN＿BEACON」を備えることを用いて更なるビーコンをスキップすることが可能であるということが分かり得る。
【００５３】
図４では、すなわち、検査ビーコン周期TCBが２*TBに等しく、ビーコンが近傍ノード・リストを備えている場合、スケジューリングされたビーコンのうち、12/32=37.5%のものをスキップすることが可能である。
【００５４】
明瞭にする目的で、図は全て、４つのノードのみを備えている自己編成ネットワークに関係している。しかし、前述の結論は、より多くの数のノードを備えているネットワークに拡張することが可能である。よって、一般に、スキップすることが可能なビーコンの割合は、TCBがTBに対して増加するについて増加する。
【００５５】
近傍リストを用いることなしで、新たなノ―ドが自己編成ネットワークに入る場合と、現行ノードが自己編成ネットワークを離れる場合との本発明の方法の機能を前述した。この方法は、受信ビーコン全ての後に各ノードで近傍リストを検査するよう形成することが可能であり、それによって、次のビーコン周期中の代わりに、現行ビーコン周期中に新たなノードがネットワークに入ること、又は現行ノードがネットワークを出ることを知ることにつながり得る。しかし、このことによって、通常、多数の近傍が存在する場合、ノード内の処理能力が増大してしまう。
【００５６】
本発明を好ましい実施例に関して説明したが、前述した原理内に収まるその修正は当業者に明らかであろう。よって、本発明は、好ましい実施例に限定されるものでない一方で、そうした修正を包含することを意図している。本発明は、新規の特徴的な特性、及び、特徴的な特性の組み合わせ全てにおいて存在している。請求項における参照符号は、その保護範囲を限定するものでない。「to  comprise」の動詞及びその活用形を用いていることは、特許請求の範囲記載のもの以外の構成要素が存在することを排除するものでない。構成要素に先行する冠詞「a」又は「an」を用いていることは、そうした構成要素が複数存在することを排除するものでない。
【００５７】
本発明は、別個のいくつかの構成要素を備えるハードウェアによって、かつ、適切にプログラムされたコンピュータによって実施することが可能である。「Computer  program」は、フロッピー（登録商標）・ディスクなどのソフトウェア、インターネットなどのネットワークを介してダウンロード可能なソフトウェア、又は何れかの他の方法で流通可能なソフトウェアを意味することとする。
【図面の簡単な説明】
【００５８】
【図１】自己編成ネットワークを示す図である。
【図２】自己編成ネットワークにおけるノードからのブロードキャストのタイミングの例を示す図である。
【図３】自己編成ネットワークにおけるノードからのブロードキャストのタイミングの例を示す図である。
【図４】自己編成ネットワークにおけるノードからのブロードキャストのタイミングの例であって、ブロードキャストが近接移動体装置のリストを備える例を示す図である。
【図１】
2007517451.tif 000003
【図２】
2007517451.tif 000004
【図３】
2007517451.tif 000005
【図４】
2007517451.tif 000006
【国際調査報告】
2007517451.tif 000007
2007517451.tif 000008