(57)【要約】  インフラストラクチャ型/非インフラストラクチャ型ネットワークにおいて複数のクエリをマッチさせるための方法であって、当該ネットワークは、第一および第二タイプの通信装置をそれぞれ複数備え、当該方法は、当該第一タイプの装置の一つに、ユーザによる第一クエリを設定し、インフラストラクチャ型通信を介して、当該第二タイプの装置の一つに、当該クエリを送信し、当該第一クエリのカテゴリに応じて、当該一つの第二タイプの装置から一つ以上の第一タイプの装置に、インフラストラクチャ型通信を介して、当該第一クエリを送信し、当該一つ以上の第一タイプの装置のそれぞれから、一つ以上の隣接する当該第一タイプの装置へ、非インフラストラクチャ型通信を介して、当該第一クエリを中継することを特徴とするクエリマッチング方法。【選択図】図１
2008522543.tif 000002
【特許請求の範囲】
【請求項１】
インフラストラクチャ型／非インフラストラクチャ型通信が混在するネットワークにおいて複数のクエリをマッチさせるための方法であって、前記ネットワークは、第一および第二タイプの通信装置をそれぞれ複数備え、前記方法は、
前記第一タイプの装置の一つに、ユーザによる第一クエリを設定し、インフラストラクチャ型通信を介して、前記第二タイプの装置の一つに、前記クエリを送信し、
前記第一クエリのカテゴリに応じて、前記一つの第二タイプの装置から一つ以上の第一タイプの装置に、インフラストラクチャ型通信を介して、前記第一クエリを送信し、
前記一つ以上の第一タイプの装置のそれぞれから、一つ以上の隣接する前記第一タイプの装置へ、非インフラストラクチャ型通信を介して、前記第一クエリを中継する
ことを特徴とするクエリマッチング方法。
【請求項２】
請求項１に記載のクエリマッチング方法であって、さらに、
ネットワークでカバーされた地理的エリアを、複数の領域に分割し、
前記一つ以上の第一タイプの装置は、前記一つの第二タイプの装置による前記第一クエリの送信先であり、前記複数の領域の一つに位置する
ことを特徴とするクエリマッチング方法。
【請求項３】
請求項１または２に記載のクエリマッチング方法であって、さらに、
前記第一クエリの前記カテゴリに応じて、前記一つの第二タイプの装置から他の一つ以上の第二タイプの装置に、前記第一クエリを送信する
ことを特徴とするクエリマッチング方法。
【請求項４】
請求項１乃至３の少なくとも１つに記載のクエリマッチング方法であって、さらに、
各第一タイプの装置は、前記第一クエリとマッチする第二クエリが、前記一つの第一タイプの装置で利用可能かどうかを判定する
ことを特徴とするクエリマッチング方法。
【請求項５】
請求項４に記載のクエリマッチング方法であって、
各第一タイプの装置は、第一タイプの装置でマッチしていると判定された場合、ユーザに通知する通知メカニズムを備える
ことを特徴とするクエリマッチング方法。
【請求項６】
請求項１乃至５の少なくとも１つに記載のクエリマッチング方法であって、
各第一タイプの装置は、前記第一タイプの装置に到着した各クエリを記録する
ことを特徴とするクエリマッチング方法。
【請求項７】
請求項６に記載のクエリマッチング方法であって、
各第一タイプの装置は、新たなクエリが前記一つの第一タイプの装置に到着した場合、各クエリの優先順位に基づき、削除するクエリを決定する
ことを特徴とするクエリマッチング方法。
【請求項８】
請求項１乃至７の少なくとも１つに記載のクエリマッチング方法であって、
各第二タイプの装置は、一方では複数のクエリのマッチング時間の統計的分析とマッチング確率、他方ではリソースの活用とに基づき、前記第一クエリの送信先となる一つ以上の第一タイプの装置を判定する
ことを特徴とするクエリマッチング方法。
【請求項９】
請求項７に記載のクエリマッチング方法であって、
各クエリの優先順位は、優先順位に係わる一つ以上の異なる要因で決まる
ことを特徴とするクエリマッチング方法。
【請求項１０】
請求項５に記載のクエリマッチング方法であって、
前記通知メカニズムは、前記複数のマッチングクエリのそれぞれが生じた前記複数の第一タイプの装置へ、通知メッセージを送る
ことを特徴とするクエリマッチング方法。
【請求項１１】
請求項１０に記載のクエリマッチング方法であって、
前記通知メッセージは、ｓｍｓまたはｅメールで送られる
ことを特徴とするクエリマッチング方法。
【請求項１２】
請求項１〜１１の少なくとも１つに記載のクエリマッチング方法であって、
各第一タイプの装置は、インフラストラクチャではなくピア・ツー・ピア接続を利用してクエリを中継する
ことを特徴とするクエリマッチング方法。
【請求項１３】
請求項１２に記載のクエリマッチング方法であって、
前記ピア・ツー・ピア接続は、ＢｌｕｅｔｏｏｔｈまたはＷｉ-Ｆｉサービスである
ことを特徴とするクエリマッチング方法。
【請求項１４】
請求項１〜１３の少なくとも１つに記載のクエリマッチング方法であって、
前記一つの第二タイプの装置に、ユーザからの第一クエリを設定することには、前記ネットワークのセルラーサービスを直接活用することが含まれる
ことを特徴とするクエリマッチング方法。
【請求項１５】
請求項１〜１４の少なくとも１つに記載のクエリマッチング方法であって、
前記第一クエリを、前記一つ以上の第一タイプの装置に送信することには、前記ネットワークのセルラーサービスを直接活用することが含まれる
ことを特徴とするクエリマッチング方法。
【請求項１６】
請求項１〜１５の少なくとも１つに記載のクエリマッチング方法であって、
前記地理的エリアの複数の領域への分割は、前記第一クエリの前記カテゴリからなる、一つ以上のグループと、前記第一クエリのカテゴリの人気度と、前記ネットワークにおける前記複数の第一タイプの装置の密度と、前記ネットワークにおける前記複数の第一タイプの装置の機動性とに基づいておこなわれる
ことを特徴とするクエリマッチング方法。
【請求項１７】
請求項１〜１６の少なくとも１つに記載のクエリマッチング方法であって、
前記複数の第一タイプの装置は、前記ネットワークにおける移動ステーションである
ことを特徴とするクエリマッチング方法。
【請求項１８】
請求項１〜１７の少なくとも１つに記載のクエリマッチング方法であって、
前記複数の第一タイプの装置は、非インフラストラクチャ型通信をおこなうことができ、インフラストラクチャ型通信をおこなうことができない一つ以上の第一サブタイプの装置である
ことを特徴とするクエリマッチング方法。
【請求項１９】
請求項１８に記載のクエリマッチング方法であって、
前記一つ以上の第一サブタイプの装置は、前記一つの第一サブタイプの装置でマッチしていると判定されたかどうかを、一つ以上の前記第一タイプの装置に知らせ、前記一つの第一タイプの装置は、前記一つの第一サブタイプの装置に判定されたマッチをユーザに通知する
ことを特徴とするクエリマッチング方法。
【請求項２０】
請求項２に記載のクエリマッチング方法であって、
前記一つ以上の地理的エリアは、複数の第一タイプの装置が位置する、一つ以上の輸送手段に動的に定義付けされ関連付けられている
ことを特徴とするクエリマッチング方法。
【請求項２１】
請求項２０に記載のクエリマッチング方法であって、
前記輸送手段は、列車と、地下鉄と、飛行機と、船とからなる、一つ以上のグループである
ことを特徴とするクエリマッチング方法。
【請求項２２】
請求項１〜２１の少なくとも１つに記載のクエリマッチング方法であって、
前記複数の第二タイプの装置は、ベースステーションまたは前記ネットワークにおけるアクセスポイントである
ことを特徴とするクエリマッチング方法。
【請求項２３】
インフラストラクチャ型／非インフラストラクチャ型ネットワークであって、
第一および第二タイプの通信装置をそれぞれ複数備え、
前記第一タイプの装置の一つは、インフラストラクチャ型通信を介して、前記第二タイプの装置の一つに、ユーザからの第一クエリを送信し、
前記一つの第二タイプの装置は、前記第一クエリのカテゴリに応じて、インフラストラクチャ型通信を介して、一つ以上の第一タイプの装置に前記第一クエリを送信し、
前記一つ以上の第一のタイプの装置のそれぞれは、非インフラストラクチャ型通信を介して、一つ以上の隣接する第一タイプの装置に、前記第一クエリを中継する
ことを特徴とするネットワーク。
【請求項２４】
請求項２３に記載のシステムであって、さらに、
ネットワークでカバーされ、複数の領域に分割された地理的エリアを備え、
前記一つ以上の第一タイプの装置は、前記一つの第二タイプの装置による前記第一クエリの送信先であり、前記複数の領域の一つに位置する
ことを特徴とするシステム。
【請求項２５】
請求項２３または２４に記載のネットワークであって、
前記一つの第二タイプの装置は、前記第一クエリのカテゴリに応じて、一つ以上の他の第二タイプの装置に前記第一クエリを送信する
ことを特徴とするネットワーク。
【請求項２６】
インフラストラクチャ型／非インフラストラクチャ型ネットワークにおいて複数のクエリをマッチさせるための方法をコンピュータに実行させるよう命令するためのコンピュータコード手段を記憶した、コンピュータで読み取り可能なデータを記録する記録媒体であって、前記ネットワークは、第一および第二タイプの通信装置をそれぞれ複数備え、前記方法は、
インフラストラクチャ型／非インフラストラクチャ型通信が混在するネットワークにおいて複数のクエリをマッチさせるための方法であって、前記ネットワークは、第一および第二タイプの通信装置をそれぞれ複数備え、前記方法は、
前記第一タイプの装置の一つに、ユーザによる第一クエリを設定し、インフラストラクチャ型通信を介して、前記第二タイプの装置の一つに、前記クエリを送信し、
前記第一クエリのカテゴリに応じて、前記一つの第二タイプの装置から一つ以上の第一タイプの装置に、インフラストラクチャ型通信を介して、前記第一クエリを送信し、
前記一つ以上の第一タイプの装置のそれぞれから、一つ以上の隣接する前記第一タイプの装置へ、非インフラストラクチャ型通信を介して、前記第一クエリを中継する
ことを特徴とする記録媒体。
【請求項２７】
請求項２６に記載のデータ記録媒体であって、
前記方法は、さらに、前記ネットワークでカバーされた地理的エリアを複数の領域に分割し、
前記一つ以上の第一タイプの装置は、前記一つの第二タイプの装置による前記第一クエリの送信先であり、前記複数の領域の一つに位置する
ことを特徴とする記録媒体。
【請求項２８】
請求項２６または２７に記載のデータ記録媒体であって、
前記方法は、さらに、前記第一クエリのカテゴリに応じて、前記一つの第二タイプの装置からの一つ以上の他の第二タイプの装置へ、前記第一クエリを送信する
ことを特徴とする記録媒体。
【請求項２９】
ネットワークにおいて複数のクエリをマッチさせるための方法であって、前記ネットワークは、第一および第二タイプの通信装置をそれぞれ複数備え、前記方法は、
前記ネットワークでカバーされた地理的エリアを、複数の領域に分割し、
前記第一タイプの装置の一つに、ユーザによる第一クエリを設定し、前記第二タイプの装置の一つに、前記クエリを送信し、
前記第一クエリのカテゴリに応じて、前記一つの第二タイプの装置から、前記領域の一つにおける一つ以上の第一タイプの装置に、前記第一クエリを送信する
前記領域の一つにおける前記一つ以上の前記第一タイプの装置のそれぞれから、一つ以上の隣接する前記第一タイプの装置へ、前記第一クエリを中継する
ことを特徴とするクエリマッチング方法。
【請求項３０】
ネットワークであって、
第一および第二タイプの通信装置をそれぞれ複数備え、
前記ネットワークでカバーされた地理的エリアを、複数の領域に分割し、
前記一つの第一タイプの装置は、前記第二タイプの装置の一つに、ユーザによって設定された第一クエリを送信し、
前記一つの第二タイプの装置は、前記第一クエリのカテゴリに応じて、前記領域の一つにおける一つ以上の前記第一タイプの装置に、前記第一クエリを送信し、
前記一つ以上の第一タイプの装置のそれぞれは、前記領域の一つにおける前記一つ以上の前記第一タイプの装置のそれぞれから、一つ以上の隣接する前記第一タイプの装置へ、前記第一クエリを中継する
ことを特徴とするネットワーク。
【請求項３１】
ネットワークにおいて複数のクエリをマッチさせるための方法をコンピュータに実行させるよう命令するためのコンピュータコード手段を記憶した、コンピュータで読み取り可能なデータを記録する記録媒体であって、前記ネットワークは、第一および第二タイプの通信装置をそれぞれ複数備え、前記方法は、
前記ネットワークでカバーされた地理的エリアを、複数の領域に分割し、
ユーザによる第一クエリを前記第一タイプの装置の一つに設定し、前記クエリを前記第二タイプの装置の一つに送信し、
前記第一クエリのカテゴリに応じて、前記一つの第二タイプの装置から、前記領域の一つにおける一つ以上の第一タイプの装置に、前記第一クエリを送信し、
前記領域の一つにおける前記一つ以上の第一タイプの装置のそれぞれから、一つ以上の隣接する第一タイプの装置に、前記第一クエリを中継する
ことを特徴とする記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、広義では、ネットワークにおけるクエリマッチング方法およびシステムに関し、ネットワークにおけるクエリマッチング方法をコンピュータに実行させるよう命令するためのコンピュータコード手段を記憶した、コンピュータで読み取り可能なデータを記録する記録媒体に関する。
【背景技術】
【０００２】
知人に尋ねたり、ソーシャルネットワークをナビゲートすることによって、情報を探し求めることがよくある。ウェブサイトや図書館などの巨大な情報の宝庫を利用できるにもかかわらず、このようにして情報を探し求めることは、未だに非常にポピュラーである。なぜなら、人々は、（たとえば、地域限定または期間的な）特有の情報を有している場合があり、このような情報は、インターネットのような他の情報の宝庫からは、容易には手に入らないからである。
【０００３】
ワイヤレス技術は、とてつもなく進歩し、現在では、ニーズに応じたさまざまなアクセス技術が存在する。たとえば、セルラーネットワークは、ユビキタスな音声通信と有限のデータサービスを提供する。ＩＥＥＥ８０２．１１などのワイヤレスＬＡＮ規格は、インターネットへの縛りのない高速アクセスを可能にした。さらに、Ｂｌｕｅｔｅｅｔｈ（登録商標）は、異なる種類の装置間に、低料金のサービスを提供するためのケーブル交換技術として出現した。
【０００４】
最近、装置は多機能化した。すなわち、単一の装置で異なる技術の全てを利用できるようになった。たとえば、Ｂｌｕｅｔｅｅｔｈ（登録商標）通信をおこなうことができる携帯電話がいくつか市場に出回っている。最近、ＨＰ（登録商標）は、セルラーと、Ｂｌｕｅｔｅｅｔｈ（登録商標）と、ＷＬＡＮとをおこなうことができる装置を発表した。よりよいデータおよび音声サービスを提供するために、このような多機能化を活用することが研究されている。たとえば、セルラーベースステーションにデータを中継するためにマルチホップ通信を用いるアーキテクチャが提案されている。その原理は、マルチホップ伝送に用いられる低減パワーは、空間の再利用を改善することにつながり、それによって、ネットワークにおいてよりよい能力が得られるというものである。しかしながら、アドホックネットワークにおける多くの研究は、ソースとデスティネーション（またはマルチキャストの場合は、複数のデスティネーション）との間で、信頼できるエンド・ツー・エンドのパケット配信を提供することを目的とする、伝統的なポイント・ツー・ポイント通信パラダイムに固執している。本研究は、この伝統的な通信パラダイムを、ピア・ツー・ピアのワイヤレスネットワーク（またはアドホックネットワーク）の世界に採り入れることに重点を置いている。
【０００５】
ファイル送信、音声およびストリーミングアプリケーションなどの伝統的な通信ネットワークアプリケーションを可能にする、効率的なルーティングやトランスポートプロトコルの設計に関しては、鋭意研究されている。しかしながら、ソーシャルネットワークにおいては、友人や近所の人に直接尋ねることによって、情報をナビゲートしたりクエリしたりする。このような知人は、答えをくれたり、その答えを知っていると思う人へそのクエリを差し向けてくれたりする。つまり、コミュニケーションセッションにエンド・ツー・エンドの考えはない。他に提案されているシステムは、有線／無線の世界のピア・ツー・ピア（Ｐ２Ｐ）ネットワークに関する。現在のＰ２Ｐネットワークにおいては、要求者は、特定のコミュニティ（たとえば、Ｎａｐｓｔｅｒ（登録商標））を通して伝播されたクエリを送り、マッチが見つかれば、その回答が要求者にルートを遡って返され、マッチングされる。しかしながら、要求者が不在であるときや、一時的に接続されていない場合には、マッチは失われる。必要なら、要求者は、再度サーチをおこなわなければならない。
【０００６】
７ＤＳ［Ｍ．Ｐａｐａｄｏｐｏｕｌｉ  ａｎｄ  Ｈ．Ｓｃｈｕｌｚｒｉｎｎｅ，“Ｅｆｆｅｃｔｓ  ｏｆ  ｐｏｗｅｒ  ｃｏｎｓｅｒｖａｔｉｏｎ，  ｗｉｒｅｌｅｓｓ  ｃｏｖｅｒａｇｅ  ａｎｄ  ｃｏｏｐｅｒａｔｉｏｎ  ｏｎ  ｄａｔａ  ｄｉｓｓｅｍｉｎａｔｉｏｎ  ａｍｏｎｇ  ｍｏｂｉｌｅ  ｄｅｖｉｃｅｓ”，  ＡＣＭ  ＳＩＧＭＯＢＩＬＥ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｍｏｂｉｌｅ  Ａｄ  Ｈｏｃ  Ｎｅｔｗｏｒｋｉｎｇ  ＆  Ｃｏｍｐｕｔｉｎｇ  （ＭｏｂｉＨｏｃ）  ２００１，  Ｏｃｔｏｂｅｒ  ４−５，  ２００１，  Ｌｏｎｇ  Ｂｅａｃｈ，  Ｃａｌｉｆｏｒｎｉａ］は、ピア・ツー・ピアのリソースシェアリングシステムであり、ワイヤレス移動装置へのデータアクセスを提供することを目的とする。ワイヤレスローカルエリアネットワークによる通信が可能な複数のホストのネットワークの例をあげる。これらのホストのうちいくつかは、ワイヤレスモード、アクセスポイント、またはＢｌｕｅｔｅｅｔｈ（登録商標）でインターネットに接続することができる。インターネットアクセスセッションに参加しているものの、インターネットへは断続的に接続しているホストＡを検討する。ホストＡがアクセスを要しているが接続されていない場合、ホストＡは近隣の複数のホストに対し、データをクエリする。たとえば、ホストＢおよびホストＣがこのクエリを受信したとする。それらがこのデータを有する場合、このデータをホストＡに送信することができる。このデータを有してはいないものの、インターネットアクセスを有するときは、それらはこのデータを取得することができ、その後、ホストＡに送信する。７ＤＳの主眼点は、断続的に接続しているワイヤレス移動通信のユーザにデータアクセスを提供することである。７ＤＳの最終目標は、複数の移動ホストにデータ接続性を提供することである。つまり、７ＤＳは、現存する電子リソースへのアクセスを提供する。
【０００７】
インフォステーションのコンセプトは、元々、ＷＩＮＬＡＢ［Ｄｏ  ｗｅ  ｈａｖｅ  ａ  ｎｏｎ−ｗｅｂ  ｒｅｆｅｒｅｎｃｅ  ｔｏ  ＷＩＮＬＡＢ？］の研究者たちによって提案されたものであり、地理的に離れた小さなエリアに高速データネットワークアクセスを提供するために、複数のハイパワーベースステーション（つまり、複数のインフォステーション）を用いるというアイデアに基づくものである。ユーザは、あるインフォステーションの近くにいくまで、大量のデータをバッファにとどめておくことになり、これにより、遅延が生じる。このことは、当然、遅延と能力とのトレードオフにつながる。ＳＷＩＭのコンセプトは、中間の移動アドホックネットワークをホッピングして回ることによって、当該インフォステーションに向けたデータの移動を可能にすることにより、当該インフォステーションのアイデアを拡張するものである。
【０００８】
ＳＷＩＭは、移動ワイヤレス通信装置のネットワーク全体を通して、データを伝播するというアイデアを採り入れている。（７ＤＳを備えた）ＳＷＩＭの主たる目的は、ネットワークアクセスであり、つまり、あるインフォステーションを通して有線ネットワークにオフロードされるデータを、装置が生成するということである。
【０００９】
Ｄｏｄｇｅｂａｌｌ．ｃｏｍとＢｅｄｄ．ｃｏｍのふたつは、移動装置を経由したソーシャルネットワーキングの最近のパラダイムを活用したサービスの例である。それらは、インターネットを通じて視覚的なソーシャルネットワーキングを可能にする、ｆｒｉｅｎｄｓｔｅｒ．ｃｏｍやｏｒｋｕｔ．ｃｏｍなどといった多くの会社を追っている。たとえば、ｆｒｉｅｎｄｓｔｅｒ．ｃｏｍ、ｏｒｋｕｔ．ｃｏｍ、Ｄｏｄｇｅｂａｌｌ．ｃｏｍなどのサービスでは、ユーザが仲間のリストを登録することができる。あるユーザがどこにいても、たとえば、パブやナイトクラブのような場所にいても、携帯電話を使ってＤｏｄｇｅｂａｌｌ．ｃｏｍに連絡すれば、Ｄｏｄｇｅｂａｌｌ．ｃｏｍが半径１０ブロック圏内にいる仲間に連絡し、当該ユーザには仲間が当該エリアにいるかどうかを連絡する。Ｂｅｄｄサービスでは、Ｂｌｕｅｔｅｅｔｈ（登録商標）を利用可能なユーザが、自身の電話にプロフィールを入力し、見知らぬ人々の携帯電話内のプロフィールをサーチできる。プロフィールにマッチがあれば、複数のユーザの一部が変更される。これらのプロフィールには、人と会う約束や品物の購買などのアプリケーションに特有の情報を含めることができる。しかしながら、クエリは、移動アドホックネットワークを通じてのみ伝播するので、行き届いたサービスの保証を提供するシステムを設計することは不可能である。
【００１０】
ワイヤレスセンサーネットワークを通じて情報をクエリすることも詳細に研究されている。当該ネットワークは、単位エリアにおいて、複数のセンサからなる規則正しいグリッド状であり、各センサは、隣接するセンサとのみ通信をおこなうことができる。また、それらのノードは、隣接センサおよびその他のノードの方向に関する情報を有していない。
【発明の開示】
【００１１】
考えられる課題の一つは、クエリをおこなうノードは、知られていないデスティネーションノードからのある情報に関するクエリを送信することである。この仕事における基本的なツールは、ランダムウォークのそれ、具体的には、時間的に継続するランダムウォーク（またはＢｒｏｗｎｉａｎ  ｍｏｔｉｏｎ）である。それは、いくつかのサーチ戦略を検討している。第一のタイプでは、ソースは、デスティネーションにヒットするまでランダムウォークをおこなうクエリを送信する。第二のタイプでは、ソースとデスティネーション双方がクエリを送信し、それらの経路が交差するまでランダムアクセスをおこなう。第三のタイプでは、デスティネーションは、定期的に情報をキャッシュし、ソースはキャッシュの一つにヒットするまでランダムウォークをおこなうだけである。分析によると、この提案における分析では、ランダムウォークおよびランダムウォークの交差点から得られる結果に大きく依存する。継続的なランダムウォークによる推定は、実世界のシナリオでは有効でない。
【００１２】
本発明は、上述のシステムおよび論点に関する知識に基づいて、なされ、実施化された。
【００１３】
本発明の第１のアスペクトにしたがい提供されるものは、インフラストラクチャ型／非インフラストラクチャ型通信が混在するネットワークにおいて複数のクエリをマッチさせるための方法である。当該ネットワークは、第一および第二タイプの通信装置をそれぞれ複数備える。当該方法は、当該第一タイプの装置の一つに、ユーザによる第一クエリを設定し、インフラストラクチャ型通信を介して、当該第二タイプの装置の一つに、当該クエリを送信することと、当該第一クエリのカテゴリに応じて、当該一つの第二タイプの装置から一つ以上の第一タイプの装置に、インフラストラクチャ型通信を介して、当該第一クエリを送信することと、当該一つ以上の第一タイプの装置のそれぞれから、一つ以上の隣接する当該第一タイプの装置へ、非インフラストラクチャ型通信を介して、当該第一クエリを中継することとを含む。
【００１４】
当該クエリマッチング方法は、さらに、ネットワークでカバーされた地理的エリアを、複数の領域に分割することを含んでもよい。当該方法において、当該一つ以上の第一タイプの装置は、当該一つの第二タイプの装置による当該第一クエリの送信先であり、かつ当該複数の領域の一つに位置していてもよい。
【００１５】
当該クエリマッチング方法は、さらに、当該第一クエリの当該カテゴリに応じて、当該一つの第二タイプの装置から他の一つ以上の第二タイプの装置に、当該第一クエリを送信することを含んでもよい。
【００１６】
当該クエリマッチング方法において、さらに、各第一タイプの装置は、当該第一クエリとマッチする第二クエリが、当該一つの第一タイプの装置で利用可能かどうかを判定してもよい。
【００１７】
当該クエリマッチング方法において、各第一タイプの装置は、第一タイプの装置でマッチしていると判定された場合、ユーザに通知する通知メカニズムを備えてもよい。
【００１８】
当該クエリマッチング方法において、各第一タイプの装置は、当該第一タイプの装置に到着した各クエリを記録してもよい。
【００１９】
当該クエリマッチング方法において、各第一タイプの装置は、新たなクエリが当該一つの第一タイプの装置に到着した場合、各クエリの優先順位に基づき、削除するクエリを決定してもよい。
【００２０】
当該クエリマッチング方法において、各第二タイプの装置は、一方では複数のクエリのマッチング時間の統計的分析、他方ではリソースの活用とに基づき、当該第一クエリの送信先となる一つ以上の第一タイプの装置を判定してもよい。
【００２１】
当該クエリマッチング方法において、各クエリの優先順位は、優先順位に係わる一つ以上の異なる要因で決められてもよい。
【００２２】
当該クエリマッチング方法において、当該通知メカニズムは、当該複数のマッチングクエリのそれぞれが生じた当該複数の第一タイプの装置へ、通知メッセージを送ってもよい。
【００２３】
当該クエリマッチング方法において、当該通知メッセージは、ｓｍｓまたはｅメールで送られてもよい。
【００２４】
当該クエリマッチング方法において、各第一タイプの装置は、インフラストラクチャではなくピア・ツー・ピア接続を利用してクエリを中継してもよい。
【００２５】
当該クエリマッチング方法において、当該ピア・ツー・ピア接続は、ＢｌｕｅｔｏｏｔｈまたはＷｉ-Ｆｉサービスであってもよい。
【００２６】
当該クエリマッチング方法において、当該一つの第二タイプの装置に、ユーザからの第一クエリを設定することには、当該ネットワークのセルラーサービスを直接活用することが含まれてもよい。
【００２７】
当該クエリマッチング方法において、当該第一クエリを、当該一つ以上の第一タイプの装置に送信することには、当該ネットワークのセルラーサービスを直接活用することが含まれてもよい。
【００２８】
当該クエリマッチング方法において、当該地理的エリアの複数の領域への分割は、以下に基づいておこなわれてもよい。すなわち、当該第一クエリの当該カテゴリからなる、一つ以上のグループと、当該第一クエリのカテゴリの人気度と、当該ネットワークにおける当該複数の第一タイプの装置の密度と、当該ネットワークにおける当該複数の第一タイプの装置の機動性とに基づいておこなわれてもよい。
【００２９】
当該クエリマッチング方法において、当該複数の第一タイプの装置は、当該ネットワークにおける移動ステーションであってもよい。
【００３０】
当該クエリマッチング方法において、当該複数の第一タイプの装置は、非インフラストラクチャ型通信をおこなうことができ、かつインフラストラクチャ型通信をおこなうことができない一つ以上の第一サブタイプの装置であってもよい。
【００３１】
当該クエリマッチング方法において、当該一つ以上の第一サブタイプの装置は、当該一つの第一サブタイプの装置でマッチしていると判定されたかどうかを、一つ以上の当該第一タイプの装置に知らせてもよく、当該一つの第一タイプの装置は、当該一つの第一サブタイプの装置に判定されたマッチをユーザに通知してもよい。
【００３２】
当該クエリマッチング方法において、当該一つ以上の領域は、複数の第一タイプの装置が位置する、一つ以上の輸送手段に動的に定義付けされ関連付けられていてもよい。
【００３３】
当該クエリマッチング方法において、当該輸送手段は、列車と、地下鉄と、飛行機と、船とからなる、一つ以上のグループであってもよい。
【００３４】
当該クエリマッチング方法において、当該複数の第二タイプの装置は、ベースステーションまたは当該ネットワークにおけるアクセスポイントであってもよい。
【００３５】
本発明の第２のアスペクトにしたがい提供されるものは、インフラストラクチャ型／非インフラストラクチャ型通信が混在するネットワークである。当該ネットワークは、第一および第二タイプの通信装置をそれぞれ複数備える。当該ネットワークにおいて、当該第一タイプの装置の一つは、インフラストラクチャ型通信を介して、当該第二タイプの装置の一つに、ユーザからの第一クエリを送信し、当該一つの第二タイプの装置は、当該第一クエリのカテゴリに応じて、インフラストラクチャ型通信を介して、一つ以上の第一タイプの装置に当該第一クエリを送信し、当該一つ以上の第一のタイプの装置のそれぞれは、非インフラストラクチャ型通信を介して、一つ以上の隣接する第一タイプの装置に、当該第一クエリを中継する。
【００３６】
当該システムは、さらに、ネットワークでカバーされ、複数の領域に分割された地理的エリアを備えていてもよい。当該一つ以上の第一タイプの装置は、当該一つの第二タイプの装置による当該第一クエリの送信先であり、かつ当該複数の領域の一つに位置していてもよい。
【００３７】
当該ネットワークにおいて、当該一つの第二タイプの装置は、当該第一クエリのカテゴリに応じて、一つ以上の他の第二タイプの装置に当該第一クエリを送信してもよい。
【００３８】
本発明の第３のアスペクトにしたがい提供される記録媒体は、インフラストラクチャ型／非インフラストラクチャ型ネットワークにおいて複数のクエリをマッチさせるための方法をコンピュータに実行させるよう命令するためのコンピュータコード手段を記憶した、コンピュータで読み取り可能なデータを記録する記録媒体である。当該ネットワークは、第一および第二タイプの通信装置をそれぞれ複数備える。当該方法は、インフラストラクチャ型／非インフラストラクチャ型通信が混在するネットワークにおいて複数のクエリをマッチさせるための方法である。当該ネットワークは、第一および第二タイプの通信装置をそれぞれ複数備える。当該方法は、当該第一タイプの装置の一つに、ユーザによる第一クエリを設定して、インフラストラクチャ型通信を介して、前記第二タイプの装置の一つに、当該クエリを送信することと、当該第一クエリのカテゴリに応じて、当該一つの第二タイプの装置から一つ以上の第一タイプの装置に、インフラストラクチャ型通信を介して、当該第一クエリを送信することと、当該一つ以上の第一タイプの装置のそれぞれから、一つ以上の隣接する当該第一タイプの装置へ、非インフラストラクチャ型通信を介して、当該第一クエリを中継することとを含む。
【００３９】
当該クエリマッチング方法は、さらに、ネットワークでカバーされた地理的エリアは、複数の領域に分割することを含んでもよい。当該一つ以上の第一タイプの装置は、当該一つの第二タイプの装置による当該第一クエリの送信先であり、かつ当該複数の領域の一つに位置していてもよい。
【００４０】
当該クエリマッチング方法は、さらに、当該第一クエリの当該カテゴリに応じて、当該一つの第二タイプの装置から他の一つ以上の第二タイプの装置に、当該第一クエリを送信することを含んでもよい。
【００４１】
本発明の第４のアスペクトにしたがい提供されるものは、ネットワークにおいて複数のクエリをマッチさせるための方法である。当該ネットワークは、第一および第二タイプの通信装置をそれぞれ複数備える。当該方法は、当該ネットワークでカバーされた地理的エリアを、複数の領域に分割することと、当該第一タイプの装置の一つに、ユーザによる第一クエリを設定し、当該第二タイプの装置の一つに、当該クエリを送信することと、当該第一クエリのカテゴリに応じて、当該一つの第二タイプの装置から、当該領域の一つにおける一つ以上の第一タイプの装置に、当該第一クエリを送信することと、当該領域の一つにおける当該一つ以上の当該第一タイプの装置のそれぞれから、一つ以上の隣接する当該第一タイプの装置へ、当該第一クエリを中継することとを含む。
【００４２】
本発明の第５のアスペクトにしたがい提供されるネットワークは、第一および第二タイプの通信装置をそれぞれ複数備え、当該ネットワークでカバーされ複数の領域に分割された地理的エリアを含む。当該一つの第一タイプの装置は、当該第二タイプの装置の一つに、ユーザによって設定された第一クエリを送信する。当該一つの第二タイプの装置は、当該第一クエリのカテゴリに応じて、当該領域の一つにおける一つ以上の当該第一タイプの装置に、当該第一クエリを送信する。当該一つ以上の第一タイプの装置のそれぞれは、当該領域の一つにおける当該一つ以上の当該第一タイプの装置のそれぞれから、一つ以上の隣接する当該第一タイプの装置へ、当該第一クエリを中継する。
【００４３】
本発明の第７のアスペクトにしたがい提供される記録媒体は、ネットワークにおいて複数のクエリをマッチさせるための方法をコンピュータに実行させるよう命令するためのコンピュータコード手段を記憶した、コンピュータで読み取り可能なデータを記録する記録媒体である。当該ネットワークは、第一および第二タイプの通信装置をそれぞれ複数備える。当該方法は、当該ネットワークでカバーされた地理的エリアを、複数の領域に分割することと、ユーザによる第一クエリを当該第一タイプの装置の一つに設定し、当該クエリを当該第二タイプの装置の一つに送信することと、当該第一クエリのカテゴリに応じて、当該一つの第二タイプの装置から、当該領域の一つにおける一つ以上の第一タイプの装置に、当該第一クエリを送信することと、当該領域の一つにおける当該一つ以上の第一タイプの装置のそれぞれから、一つ以上の隣接する第一タイプの装置に、当該第一クエリを中継することとを含む。
【発明を実施するための最良の形態】
【００４４】
実施の形態において、情報を求めるユーザが自身の移動装置にクエリを設定するというシナリオについて説明する。当該クエリは、その後、特定の地理的領域において、ランダムに選ばれた多くのユーザへ、インフラストラクチャを経由して伝播される。地理的領域はクエリのタイプによって決まる。当該クエリは、当該地理的領域内で、マッチが（典型的には、任意のユーザの移動装置上で）見つかるまで、人々の移動に応じ、ピア・ツー・ピアモードで伝播する。当該クエリを設定したユーザは、その後、このマッチを自動的に（たとえば、ｓｍｓやｅメールで）知らされる。現存するセルラーインフラストラクチャを通じて最小コストで容易に展開されうるシステムアーキテクチャを提供する。本実施の形態において、このシステムアーキテクチャは、配信された地理的データベースを提供する。それが配信されるのは、情報が異なる人々の装置にまたがって記憶されているからである。言い換えると、人々がデータベースである。それが地理的データベースであるのは、特定のカテゴリに関連する複数のクエリが、インフラストラクチャを経由して所定の地理的領域に関するものだからである。
【００４５】
最小限の設計にとどめると、（マッチが見つかるまで時間が計られた）システムのパフォーマンスにおいて膨大な改善を要する結果になりうる。このことは、本実施の形態においてマッチが見つかるまで、時間に関し厳しい理論上の制約を演算することによって量で表せる。さらに、本実施の形態におけるシステムアーキテクチャは、ユーザに対し、サービスの品質保証を与えるための手段を提供する。
【００４６】
本実施の形態におけるシステムアーキテクチャは、さまざまに応用できる。売り手と買い手とを引き合わせたり、人と会う約束をしたりするなど、互いに補間しあうクエリマッチングに関する応用例も可能である。本実施の形態は、複数の専用サーバにホスティングすることによる集中型の解決手段に対する低コストかつ拡張性のある代案である。
【００４７】
図１Ａに示されるように、本実施の形態において、街１００は、バザールと呼ばれる、たとえば１０２などの多くの領域に分割される。一つのバザールには、セルラーネットワークなどのようにいくつかのセル状に広がりうる。たとえば１０２などの各バザールは、複数のカテゴリ（たとえば、スポーツやエンターテイメントなど）に属する複数のクエリを供給するためのものである。ユーザが、自身の装置にクエリ（たとえば、スポーツに関するクエリ）を設定する場合、当該クエリは、たとえば１０２のようなバザール内のベースステーションに、セルラーインフラストラクチャを経由して伝播される。ベースステーションは、その後、ランダムにｋ人のユーザを選出し、彼らに当該クエリを伝播する。ｋ人のユーザは移動するので、彼らは、彼らに代わって当該クエリをピア・ツー・ピアモードでさらに伝播する他のユーザに、当該クエリを伝播する。本実施の形態においては、個々のバザールに「割当て済み」のカテゴリは任意でよい。つまり、バザールは、特定のカテゴリにおける複数のクエリのために好ましいリソースとなる。これは単に、当該カテゴリの全てのクエリが当該バザールに関するものであるためである。これにより、そのようなクエリが高度に集中するようにすれば、当該バザール内で、マッチするクエリが見つかる尤度を高められる。究極的にマッチするクエリが、たとえば、バザール内またはバザールの外部を含むどこかから発生するかもしれないが。
【００４８】
異なる実施の形態において、バザールに対する複数のカテゴリの割当ては、代替的にまたは追加的に、バザールの地理的領域のある特性を含む他のパラメータに基づく。たとえば、多くの自動車の小売業者の存在は、「自動車販売」というカテゴリにおけるクエリを、特定のバザールに割当てることにつながってもよい。
【００４９】
異なる実施の形態において、バザールは、他の領域を参照して代替的に定めてもよい。他の領域には複数のクエリが配信される可能性があり、また、たとえば、地下鉄を含む列車や、飛行機、船または他の輸送手段などの移動装置が潜在的に集中する。そのような実施の形態において、そのようなバザールに関連付けられた領域は、ネットワーク全体の中で動的に定義されてもよい。
【００５０】
図１Ｂ〜１Ｄは、本実施の形態における基本的なシステムアーキテクチャを説明する。二つのマッチングクエリが、単一の装置に互いに存在する場合、当該装置は、ネットワークインフラストラクチャを経由して、当該マッチついて、各ユーザに自動的に知らせる。このことは、たとえば、最初に当該クエリを設定したユーザにｓｍｓメッセージを送ることにより達成できる。ユーザが自身の装置にクエリ（たとえば、スポーツに関するクエリ）を設定した場合、当該クエリは、スポーツに関するバザールにおいて、ランダムに選出されたｋ人のユーザに対し、インフラストラクチャを経由して伝播される。ｋ人のユーザは移動するので、彼らは、彼らに代わってピア・ツー・ピアモードで当該クエリをさらに伝播する他のユーザに、当該クエリを伝播する。
【００５１】
図１Ｂにおいて、たとえば１０４のような×印は、たとえば１０２のようなバザールにおけるユーザを表す。１０８のような□印および１１０のようなアステリスクは、バザール１０６における３人のユーザのそれぞれに設定された二つのマッチングクエリを表す。図１Ｃは、たとえば１０８や１１０のようなクエリが、ピア・ツー・ピアモードでどのように伝播されるかを示す。最後に、図１Ｃにおいて、上記クエリの両方が同一の装置１１２に位置するときにマッチが生じる。二つのマッチングクエリが同一の装置１１２に位置する場合、当該装置１１２は、マッチが生じたことを、クエリを設定したユーザに自動的に知らせる。これは、当該ネットワークインフラストラクチャを用いておこなわれる。
【００５２】
なお、上記装置のいくつかは、当該ネットワークインフラストラクチャを用いて通信することができなくてもよく、非インフラストラクチャ型通信を用いて他の装置と通信可能であればよい。それでも、そのような装置は、実施の形態の実施態様に含まれ、マッチングおよび非インフラストラクチャ型中継をおこなうことができる。ネットワークインフラストラクチャを用いて通信することができない装置の一つにおいてマッチが特定される実施の形態においては、ネットワークインフラストラクチャを用いて通信可能な別の装置が近くにある場合には、当該装置は、当該別の装置にマッチを知らせることができる。ネットワークインフラストラクチャを用いて通信可能な当該装置は、その後、ネットワークインフラストラクチャを用いて、それぞれの相手方へ当該マッチについて通知することができる。
【００５３】
次に、本実施の形態におけるアーキテクチャと関連付けられた設計上の論点のいくつかについて説明する。当該アーキテクチャにおける考え方は、二つのクエリ間の予想されるマッチング時間は、当該二つのクエリ間の予想される当初の距離に比例するというものである。それゆえ、たとえば、街を、あるカテゴリ内の複数のクエリをそれぞれが供給する複数のバザールに区分することによって、人は、マッチングクエリ間の当初の最短距離を実際に縮めることができる。さらに、各クエリのコピーをｋ個送ることにより、二つの目的を達成する。第一に、各クエリを、より長期間システム内に存続させることが保証される。このことは、マッチングクエリが後に到着した場合であっても保証されるので、マッチのチャンスが残される。第二に、マッチングクエリ間の最短距離は、ｋが増加するにつれ著しく縮まる。これにより、マッチング時間が急速になることが保証される。
【００５４】
バザールのプランニング
バザールを作成すれば、マッチングクエリ間の平均初期距離を縮めることによって、複数のクエリのマッチングダイナミクスを加速させることができる。地理的により近いとこらから始まるクエリは、さらに遠いところから始まるクエリよりも、互いに発見する可能性が高い。マッチングクエリ間の初期距離は、バザールのサイズによって制限されるので、マッチング時間に対して確率的な限界を提供可能となる。つまり、バザールのコンセプトは、サービスの品質（ＱｏＳ）保証の提供を求めるためのシステムを知的に設計することを可能にする。
【００５５】
バザールのプランニングは、リソースの割当ての問題と捉えることができる。たとえば、特定のカテゴリのバザールのサイズは、特定のカテゴリにおいて考えられるクエリの数とその人気度によって決まるべきである。つまり、あるクエリのカテゴリの人気がより高ければ、それのために、サイズがより大きいバザールを指定する可能性がある。人口密度が一定であると推定したら、リソースの割当ての観点から、より人気の高いカテゴリへより多くのリソース（たとえば、より多くのメモリ）を割当てる可能性がある。バザールのプランニングはまた、稼働性パターンによって決まってもよい。特定の領域におけるユーザがよく移動していれば、この領域により大きなバザールを割当てたいと思うだろう。なぜなら、マッチを保証するために、特定のバザールにいるユーザには十分長い期間とどまって欲しいからである。
【００５６】
伝播するクエリの数
本実施の形態において、クエリのコピーをｋ個ランダムに設定することにより、マッチングクエリ間の最短距離Ｐ0を著しく縮める。図２において、ｋが増加するにつれ、二種のクエリ間の最短距離がどのように減少するかを示すプロットが示されている。この減少は非常に線形であることが分かる。あるバザールにＮ人のユーザがいるかどうかが直感的に分かる。時間ゼロの時点でのマッチの可能性は、次の式で示される。
【００５７】
【数１】
2008522543.tif 000003
【００５８】
そのゆえ、ｋが増加するにつれてＰ0が急速に減少するので、マッチング時間も急速に減少すると予想される。この簡単な分析も、同一のクエリに対して複数のマッチングがあるかどうかを暗示し、バザールのコンセプトのため、マッチング時間は非常に短くなる。バザール内の各ユーザへ各クエリを配信することが解決策となるが、これは高くつくだけでなく、システムリソースを使いすぎる。このコンテキストにおいては、システムリソースはインフラストラクチャの能力、バッファ、各ノードのエネルギーを含む。
【００５９】
たとえば、インフラストラクチャがセルラーである場合は、バザール内の各ユーザへ各クエリを送信することは、多くの帯域を使うことになり、また、システムを圧倒してしまいかねない。しかしながら、上記分析および図２から、発明者は、あるｋの値を超えると、マッチング時間の減少はわずかなものになると認識した。さらに重要なのは、これが起こるｋの値は非常に小さいということである。つまり、システムリソースを少し用いるだけで、マッチング時間の観点からよいパフォーマンスを達成することができる。さらに、クエリは任意の回数システムに到着するので、各クエリが多くのユーザに送信された場合、各ユーザの見通しから、複数のクエリが到着する率は高く、このことは、複数のクエリが消去される率も高いことを意味する。よって、これにより、システムにおける、あるクエリのために使われる時間が減少し、その結果マッチの可能性も減少する。
【００６０】
バッファ管理
本実施の形態のアーキテクチャにおいて、あるノードは、自身が有するあるクエリがすでにマッチング済みであるかどうか分からない。そのため、メモリ（マッチング済みクエリを記録するためのもの）および余分なクエリの送信のためのエネルギーという両観点から、リソースを無駄に使用することにつながる場合がある。異なる実施の形態における、クレバーなバッファ管理アルゴリズムの設計によって、これを軽減することができる。あるメカニズムとして、各クエリにＴｉｍｅ  Ｔｏ  Ｌｉｖｅ  （ＴＴＬ）スタンプを押し、現在時刻がＴＴＬより進んだ時点で各クエリを消去する。本質的には、当該バッファ管理アルゴリズムには二つのタスクがある。第一に、システムまたは隣接するノードからクエリを受信したら、新たなクエリを収容するために、メモリから削除すべきクエリを決定しなければならない。アルゴリズムの候補としては、Ｆｉｒｓｔ−ｉｎ−Ｆｉｒｓｔ−ｏｕｔ  （ＦＩＦＯ）またはＯｌｄｅｓｔ  Ｑｕｅｒｙ  Ｆｉｒｓｔなどのようなものがいくつかある。同様に、ノードが隣接ノードを有する場合、隣接ノードにどのクエリを中継するかを決定しなければならない。好ましい実施の形態において、マッチング時間を最小限にしつつマッチングの可能性を最大限にするバッファ管理ポリシーが実施される。
【００６１】
システム能力
バッファ管理戦略に関する上記考察は、システム能力の考えを示すものでもある。μがマッチングクエリ間の到着時間の平均を表すとし、λがシステムへのクエリの到着率の平均を表すとする。マッチングの可能性を最大限にするバッファ管理ポリシーが存在すると仮定すると、当該システムの能力領域を複数のデータ（μ、λ）の組であると定義することができる。当該複数のデータの組に対しては、マッチをほぼ保証する何らかのバッファ管理ポリシーが存在する。
【００６２】
システムセキュリティ
セキュリティは、本実施の形態に基づいたシステムおよびネットワークの実施において重要なアスペクトでありうる。簡単な暗号化メカニズムには、ある程度のセキュリティを提供するものがある。しかしながら、異なる実施の形態においては、セキュリティを高めるために他のメカニズムが採用されることが理解される。
【００６３】
サービスの品質
たとえば、あるクエリにより高い優先順位が割り当てられうる。つまり、（i）当該クエリは、より多数のユーザに伝播される、（ii）当該クエリは、消去される可能性が最も低い、（iii）当該クエリは、隣接ノードに中継される可能性がより高い、ということを意味する。
【００６４】
上記実施の形態は、さまざまな種類のシステム（たとえばセルラーやＷＡＮなど）に統合されてもよい。次に、当該アーキテクチャがどのようにして現存するセルラーネットワークに統合されうるかを説明する。第一に、バザールプランニングは、セルラープランニングの最初になされうる。それゆえ、バザールは、単一のＭｏｂｉｌｅ  Ｓｗｉｔｃｈｉｎｇ  Ｃｅｎｔｅｒ  （ＭＳＣ）によって制御された、いくつかのセルとして拡張されたエリアでありうる。図３は、現存するセルラーインフラストラクチャ３０２におけるオーバーレイネットワークとして、たとえば３００のようなバザールを描く。
【００６５】
ユーザがクエリを設定した場合、クエリはＭＳＣに向けられるのであるが、当該クエリに対応する、たとえば３０２などのバザールを担当するＭＳＣへ、当該クエリをルーティングするためのルックアップテーブルが使用される。ＭＳＣが別のＭＳＣからクエリを受信した場合は、自身のＶｉｓｉｔｏｒ  Ｌｏｃａｔｉｏｎ  Ｒｅｇｉｓｔｅｒ  （ＶＬＲ）からｋ人のユーザをランダムに選び、当該クエリをｋ人のユーザに向ける。ある装置がふたつのクエリ（たとえば、クエリｑとｒ）間にマッチを検知した場合は、ｒのアドレスをｑに、ｑのアドレスをｒに自動的に送信する。これは、ｓｍｓまたはｅメールでおこなわれうる。異なるネットワークの実施態様においては、複数のＭＳＣは、Ｇｅｎｅｒａｌ  Ｐａｃｋｅｔ  Ｒａｄｉｏ  Ｓｅｒｖｉｃｅ  Ｓｕｐｐｏｒｔ  Ｎｏｄｅｓ  （ＳＧＳＮｓ）、Ｇａｔｅｗａｙ  ＧＰＲＳ  Ｓｕｐｐｏｒｔ  Ｎｏｄｅｓ  （ＧＧＳＮｓ）、および当該ネットワークのアクセスポイントの形で、ベースステーションなどのような他の装置によって置きかえられてもよい。
【００６６】
本実施の形態における各クエリのフォーマットは、図４に示される。各クエリは、アドレスフィールド４００とクエリフィールド４０２とからなる。アドレスフィールド４００は、電話番号またはｅメールアドレスでありうる。本実施の形態は、現存するセルラーインフラストラクチャに最小限の追加と複雑性を加えて実現することができる。なお、本実施の形態は、オペレーションを支援するための最小限のインフラストラクチャを設置することを意味するであろうが、地面に建設されたネットワークとして代替的に実現されてもよい。
【００６７】
本実施の形態の方法およびシステムは、図５に概略的に示されたコンピュータシステム５００に実装されうる。これは、コンピュータシステム５００内で実行されるコンピュータプログラムのようなソフトウェアとして実装され、コンピュータシステム５００に本実施の形態の方法を実行するよう命令してもよい。
【００６８】
コンピュータシステム５００は、コンピュータモジュール５０２、キーボード５０４のような入力モジュール、マウス５０６、ディスプレイ５０８のような出力装置、およびプリンタ５１０からなる。
【００６９】
コンピュータモジュール５０２は、インターネットや、Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ  （ＬＡＮ）やＷｉｄｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ  （ＷＡＮ）のような他のネットワークシステムへのアクセスを可能にするために、適切なトランシーバー装置５１４経由でコンピュータネットワーク５１２に接続される。
【００７０】
本実施の形態におけるコンピュータモジュール５０２は、プロセッサ５１８と、Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ  （ＲＡＭ）５２０と、Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ  （ＲＯＭ）５２２とを備える。コンピュータモジュール５０２はまた、多くの入／出力（Ｉ／Ｏ）インターフェース、たとえば、ディスプレイ５０８へのＩ／Ｏインターフェース５２４やキーボード５０４へのＩ／Ｏインターフェース５２６をも備える。
【００７１】
コンピュータモジュール５０２の構成要素は、典型的には、インターコネクテッドバス５２８経由で、当業者に周知の方法で通信する。
【００７２】
当該アプリケーションプログラムは、典型的には、ＣＤ−ＲＯＭやフロッピー（登録商標）ディスクのようなデータ記録媒体に符号化されてコンピュータシステム５００のユーザに供給され、対応するデータ記録装置５３０のデータ記録媒体用ドライブを利用して読み取られる。当該アプリケーションプログラムは、プロセッサ５１８によって自身が実行される際に読み出され制御される。プログラムデータの中間的な記録は、ＲＡＭ５２０を用いておこなってもよい。
【００７３】
図６は、インフラストラクチャ型／非インフラストラクチャ型通信が混在するネットワークにおけるクエリマッチング方法を説明するフローチャートを示す。本実施の形態において、当該ネットワークは、第一および第二タイプの通信装置をそれぞれ複数備える。ステップ６００において、第一クエリは、第一タイプの装置の一つにユーザによって設置され、第二タイプの装置の一つにインフラストラクチャ型通信を経由して送信される。ステップ６０２において、第一クエリのカテゴリに応じて、第一クエリは、第二タイプの装置の一つから一つ以上の第一タイプの装置へ、インフラストラクチャ型通信を経由して送信される。ステップ６０４において、第一クエリは、一つ以上の第一タイプの装置のそれぞれから一つ以上の隣接する第一タイプの装置へ、非インフラストラクチャ型通信を経由して中継される。
【００７４】
図７は、ネットワークにおけるクエリマッチング方法を説明するフローチャートを示す。別の実施の形態において、当該ネットワークは、第一および第二タイプの通信装置をそれぞれ複数備える。ステップ７００において、当該ネットワークでカバーされた地理的エリアは、複数の領域に分割される。ステップ７０２において、第一クエリは、第一タイプの装置の一つにユーザによって設定され、第二タイプの装置の一つに送信される。ステップ７０４において、第一クエリのカテゴリに応じて、第一クエリは、第二タイプの装置の一つから、当該領域の一つにおける一つ以上の第一タイプの装置へ送信される。ステップ７０６において、第一クエリは、当該領域の一つにおける一つ以上の第一タイプの装置のそれぞれから、一つ以上の隣接する第一タイプの装置へ中継される。
【００７５】
おおまかに説明した本発明の精神または範囲を逸脱することなく、例示した実施の形態において、さまざまな変更や修正が可能であることは、当業者であれば容易に理解するところである。したがって、本実施の形態は、全ての面において、説明的であり限定的ではない。
【００７６】
本実施の形態は、コンピュータ操作や送信を選択的におこなうことによって、ユーザが、自身が伝播するクエリに意味づけすることを可能にする。
【００７７】
本実施の形態は、情報アクセスのパフォーマンスを改善するために、インフラストラクチャを用いるというアイデアを採り入れて、バザールとして知られる共通の地理的エリアにおいて、所定数のユーザへクエリを広めるものである。このことは、設計上のパラメータを設定し、スマートアルゴリズムを活用することによって、当該実施の形態を知的に設計することを可能にする。
【００７８】
本実施の形態は、ＳＷＩＭのアクティビティを支援してもよいが、「有線ネットワーク」の存在を要求しない。本実施の形態はむしろ、バーチャル・ワイヤレス・ソーシャル・ネットワークを構成することによって、人々に与えられている、現存する配信データベースを活用するものである。本実施の形態における配信は、単なるランダムウォークではなく、ブランチング・ランダムアクセスとみなされてよい。
【図面の簡単な説明】
【００７９】
本発明の実施の形態は、実施の形態を示す付属図面に関する以下の説明から、理解しやすく明確になる。当該図面において、
【図１】図１Ａ〜１Ｄは、本発明の実施の形態にしたがった、ワイヤレス・ビジュアル・ソーシャル・ネットワークのアーキテクチャを説明する概略図である。
【図２】図２は、本発明の実施の形態にしたがった、伝播したクエリの数の作用として、二種類のクエリ間の最短距離を説明するプロットを示す。
【図３】図３は、本発明の実施の形態にしたがった、現存するセルラーインフラストラクチャへのオーバーレイとしてのバザールを説明する概略図である。
【図４】図４は、実施の形態にしたがった、クエリのフォーマットを説明する概略図である。
【図５】図５は、実施の形態にしたがった、方法およびシステムを実施するためのコンピュータシステムを説明する概略図である。
【図６】図６は、実施の形態にしたがった方法を説明するフローチャートである。
【図７】図７は、実施の形態にしたがった方法を説明するフローチャートである。
【図１】
2008522543.tif 000004
【図２】
2008522543.tif 000005
【図３】
2008522543.tif 000006
【図４】
2008522543.tif 000007
【図５】
2008522543.tif 000008
【図６】
2008522543.tif 000009
【図７】
2008522543.tif 000010
【手続補正書】
【提出日】平成18年4月10日(2006.4.10)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
インフラストラクチャ型／非インフラストラクチャ型通信が混在するネットワークにおいて複数のクエリをマッチさせるための方法であって、前記ネットワークは、第一および第二タイプの通信装置をそれぞれ複数備え、前記方法は、
前記第一タイプの装置の一つに、ユーザによる第一クエリを設定し、インフラストラクチャ型通信を介して、前記第二タイプの装置の一つに、前記クエリを送信し、
前記第一クエリのカテゴリに応じて、前記一つの第二タイプの装置から一つ以上の第一タイプの装置に、インフラストラクチャ型通信を介して、前記第一クエリを送信し、
前記一つ以上の第一タイプの装置のそれぞれから、一つ以上の隣接する前記第一タイプの装置へ、非インフラストラクチャ型通信を介して、前記第一クエリを中継することを含み、
各第一タイプの装置は、前記第一クエリとマッチする第二クエリが、前記一つの第一タイプの装置で利用可能かどうかを判定する
ことを特徴とするクエリマッチング方法。
【請求項２】
請求項１に記載のクエリマッチング方法であって、さらに、
ネットワークでカバーされた地理的エリアを、複数の領域に分割し、
前記一つ以上の第一タイプの装置は、前記一つの第二タイプの装置による前記第一クエリの送信先であり、前記複数の領域の一つに位置する
ことを特徴とするクエリマッチング方法。
【請求項３】
請求項１または２に記載のクエリマッチング方法であって、さらに、
前記第一クエリの前記カテゴリに応じて、前記一つの第二タイプの装置から他の一つ以上の第二タイプの装置に、前記第一クエリを送信する
ことを特徴とするクエリマッチング方法。
【請求項４】
請求項１〜３の少なくとも１つに記載のクエリマッチング方法であって、
各第一タイプの装置は、第一タイプの装置でマッチしていると判定された場合、ユーザに通知する通知メカニズムを備える
ことを特徴とするクエリマッチング方法。
【請求項５】
請求項１乃至４の少なくとも１つに記載のクエリマッチング方法であって、
各第一タイプの装置は、前記第一タイプの装置に到着した各クエリを記録する
ことを特徴とするクエリマッチング方法。
【請求項６】
請求項５に記載のクエリマッチング方法であって、
各第一タイプの装置は、新たなクエリが前記一つの第一タイプの装置に到着した場合、各クエリの優先順位に基づき、削除するクエリを決定する
ことを特徴とするクエリマッチング方法。
【請求項７】
請求項１乃至６の少なくとも１つに記載のクエリマッチング方法であって、
各第二タイプの装置は、一方では複数のクエリのマッチング時間の統計的分析とマッチング確率、他方ではリソースの活用とに基づき、前記第一クエリの送信先となる一つ以上の第一タイプの装置を判定する
ことを特徴とするクエリマッチング方法。
【請求項８】
請求項６に記載のクエリマッチング方法であって、
各クエリの優先順位は、優先順位に係わる一つ以上の異なる要因で決まる
ことを特徴とするクエリマッチング方法。
【請求項９】
請求項４に記載のクエリマッチング方法であって、
前記通知メカニズムは、前記複数のマッチングクエリのそれぞれが生じた前記複数の第一タイプの装置へ、通知メッセージを送る
ことを特徴とするクエリマッチング方法。
【請求項１０】
請求項９に記載のクエリマッチング方法であって、
前記通知メッセージは、ｓｍｓまたはｅメールで送られる
ことを特徴とするクエリマッチング方法。
【請求項１１】
請求項１〜１０の少なくとも１つに記載のクエリマッチング方法であって、
各第一タイプの装置は、インフラストラクチャではなくピア・ツー・ピア接続を利用してクエリを中継する
ことを特徴とするクエリマッチング方法。
【請求項１２】
請求項１１に記載のクエリマッチング方法であって、
前記ピア・ツー・ピア接続は、ＢｌｕｅｔｏｏｔｈまたはＷｉ-Ｆｉサービスである
ことを特徴とするクエリマッチング方法。
【請求項１３】
請求項１〜１２の少なくとも１つに記載のクエリマッチング方法であって、
前記一つの第二タイプの装置に、ユーザからの第一クエリを設定することには、前記ネットワークのセルラーサービスを直接活用することが含まれる
ことを特徴とするクエリマッチング方法。
【請求項１４】
請求項１〜１３の少なくとも１つに記載のクエリマッチング方法であって、
前記第一クエリを、前記一つ以上の第一タイプの装置に送信することには、前記ネットワークのセルラーサービスを直接活用することが含まれる
ことを特徴とするクエリマッチング方法。
【請求項１５】
請求項１〜１４の少なくとも１つに記載のクエリマッチング方法であって、
前記地理的エリアの複数の領域への分割は、前記第一クエリの前記カテゴリからなる、一つ以上のグループと、前記第一クエリのカテゴリの人気度と、前記ネットワークにおける前記複数の第一タイプの装置の密度と、前記ネットワークにおける前記複数の第一タイプの装置の機動性とに基づいておこなわれる
ことを特徴とするクエリマッチング方法。
【請求項１６】
請求項１〜１５の少なくとも１つに記載のクエリマッチング方法であって、
前記複数の第一タイプの装置は、前記ネットワークにおける移動ステーションである
ことを特徴とするクエリマッチング方法。
【請求項１７】
請求項１〜１６の少なくとも１つに記載のクエリマッチング方法であって、
前記複数の第一タイプの装置は、非インフラストラクチャ型通信をおこなうことができ、インフラストラクチャ型通信をおこなうことができない一つ以上の第一サブタイプの装置である
ことを特徴とするクエリマッチング方法。
【請求項１８】
請求項１７に記載のクエリマッチング方法であって、
前記一つ以上の第一サブタイプの装置は、前記一つの第一サブタイプの装置でマッチしていると判定されたかどうかを、一つ以上の前記第一タイプの装置に知らせ、前記一つの第一タイプの装置は、前記一つの第一サブタイプの装置判定されたマッチをユーザに通知する
ことを特徴とするクエリマッチング方法。
【請求項１９】
請求項２に記載のクエリマッチング方法であって、
前記一つ以上の地理的エリアは、複数の第一タイプの装置が位置する、一つ以上の輸送手段に動的に定義付けされ関連付けられている
ことを特徴とするクエリマッチング方法。
【請求項２０】
請求項１９に記載のクエリマッチング方法であって、
前記輸送手段は、列車と、地下鉄と、飛行機と、船とからなる、一つ以上のグループである
ことを特徴とするクエリマッチング方法。
【請求項２１】
請求項１〜２０の少なくとも１つに記載のクエリマッチング方法であって、
前記複数の第二タイプの装置は、ベースステーションまたは前記ネットワークにおけるアクセスポイントである
ことを特徴とするクエリマッチング方法。
【請求項２２】
インフラストラクチャ型／非インフラストラクチャ型ネットワークであって、
第一および第二タイプの通信装置をそれぞれ複数備え、
前記第一タイプの装置の一つは、インフラストラクチャ型通信を介して、前記第二タイプの装置の一つに、ユーザからの第一クエリを送信し、
前記一つの第二タイプの装置は、前記第一クエリのカテゴリに応じて、インフラストラクチャ型通信を介して、一つ以上の第一タイプの装置に前記第一クエリを送信し、
前記一つ以上の第一のタイプの装置のそれぞれは、非インフラストラクチャ型通信を介して、一つ以上の隣接する第一タイプの装置に、前記第一クエリを中継し、
各第一タイプの装置は、前記第一クエリとマッチする第二クエリが、前記一つの第一タイプの装置で利用可能かどうかを判定する
ことを特徴とするネットワーク。
【請求項２３】
請求項２２に記載のシステムであって、さらに、
ネットワークでカバーされ、複数の領域に分割された地理的エリアを備え、
前記一つ以上の第一タイプの装置は、前記一つの第二タイプの装置による前記第一クエリの送信先であり、前記複数の領域の一つに位置する
ことを特徴とするシステム。
【請求項２４】
請求項２２または２３に記載のネットワークであって、
前記一つの第二タイプの装置は、前記第一クエリのカテゴリに応じて、一つ以上の他の第二タイプの装置に前記第一クエリを送信する
ことを特徴とするネットワーク。
【請求項２５】
インフラストラクチャ型／非インフラストラクチャ型ネットワークにおいて複数のクエリをマッチさせるための方法をコンピュータに実行させるよう命令するためのコンピュータコード手段を記憶した、コンピュータで読み取り可能なデータを記録する記録媒体であって、前記ネットワークは、第一および第二タイプの通信装置をそれぞれ複数備え、前記方法は、
インフラストラクチャ型／非インフラストラクチャ型通信が混在するネットワークにおいて複数のクエリをマッチさせるための方法であって、前記ネットワークは、第一および第二タイプの通信装置をそれぞれ複数備え、前記方法は、
前記第一タイプの装置の一つに、ユーザによる第一クエリを設定し、インフラストラクチャ型通信を介して、前記第二タイプの装置の一つに、前記クエリを送信し、
前記第一クエリのカテゴリに応じて、前記一つの第二タイプの装置から一つ以上の第一タイプの装置に、インフラストラクチャ型通信を介して、前記第一クエリを送信し、
前記一つ以上の第一タイプの装置のそれぞれから、一つ以上の隣接する前記第一タイプの装置へ、非インフラストラクチャ型通信を介して、前記第一クエリを中継することを含み、
各第一タイプの装置は、前記第一クエリとマッチする第二クエリが、前記一つの第一タイプの装置で利用可能かどうかを判定する
ことを特徴とする記録媒体。
【請求項２６】
請求項２５に記載のデータ記録媒体であって、
前記方法は、さらに、前記ネットワークでカバーされた地理的エリアを複数の領域に分割し、
前記一つ以上の第一タイプの装置は、前記一つの第二タイプの装置による前記第一クエリの送信先であり、前記複数の領域の一つに位置する
ことを特徴とする記録媒体。
【請求項２７】
請求項２５または２６に記載のデータ記録媒体であって、
前記方法は、さらに、前記第一クエリのカテゴリに応じて、前記一つの第二タイプの装置からの一つ以上の他の第二タイプの装置へ、前記第一クエリを送信する
ことを特徴とする記録媒体。
【請求項２８】
ネットワークにおいて複数のクエリをマッチさせるための方法であって、前記ネットワークは、第一および第二タイプの通信装置をそれぞれ複数備え、前記方法は、
前記ネットワークでカバーされた地理的エリアを、複数の領域に分割し、
前記第一タイプの装置の一つに、ユーザによる第一クエリを設定し、前記第二タイプの装置の一つに、前記クエリを送信し、
前記第一クエリのカテゴリに応じて、前記一つの第二タイプの装置から、前記領域の一つにおける一つ以上の第一タイプの装置に、前記第一クエリを送信する
前記領域の一つにおける前記一つ以上の前記第一タイプの装置のそれぞれから、一つ以上の隣接する前記第一タイプの装置へ、前記第一クエリを中継する
ことを特徴とするクエリマッチング方法。
【請求項２９】
ネットワークであって、
第一および第二タイプの通信装置をそれぞれ複数備え、
前記ネットワークでカバーされた地理的エリアを、複数の領域に分割し、
前記一つの第一タイプの装置は、前記第二タイプの装置の一つに、ユーザによって設定された第一クエリを送信し、
前記一つの第二タイプの装置は、前記第一クエリのカテゴリに応じて、前記領域の一つにおける一つ以上の前記第一タイプの装置に、前記第一クエリを送信し、
前記一つ以上の第一タイプの装置のそれぞれは、前記領域の一つにおける前記一つ以上の前記第一タイプの装置のそれぞれから、一つ以上の隣接する前記第一タイプの装置へ、前記第一クエリを中継する
ことを特徴とするネットワーク。
【請求項３０】
ネットワークにおいて複数のクエリをマッチさせるための方法をコンピュータに実行させるよう命令するためのコンピュータコード手段を記憶した、コンピュータで読み取り可能なデータを記録する記録媒体であって、前記ネットワークは、第一および第二タイプの通信装置をそれぞれ複数備え、前記方法は、
前記ネットワークでカバーされた地理的エリアを、複数の領域に分割し、
ユーザによる第一クエリを前記第一タイプの装置の一つに設定し、前記クエリを前記第二タイプの装置の一つに送信し、
前記第一クエリのカテゴリに応じて、前記一つの第二タイプの装置から、前記領域の一つにおける一つ以上の第一タイプの装置に、前記第一クエリを送信し、
前記領域の一つにおける前記一つ以上の第一タイプの装置のそれぞれから、一つ以上の隣接する第一タイプの装置に、前記第一クエリを中継する
ことを特徴とする記録媒体。
【国際調査報告】
2008522543.tif 000011
2008522543.tif 000012
2008522543.tif 000013