アドホックネットワークにおけるTop-k検索のためのルーティング手法

• 天方, 大地

• 佐々木, 勇和

• 原, 隆浩

• 西尾, 章治郎

書誌事項

タイトル別名

• A Top-k Query Routing Method in Mobile Ad Hoc Networks

抄録

アドホックネットワークでは，膨大なデータの中から必要なデータのみを効率的に取得するため，Top-k検索を用いることが有効である．既存研究として，検索クエリをフラッディングし，ネットワーク内のデータのk番目のスコアを推定することにより，検索結果に含まれないデータの返信を抑制する手法が提案されている．しかし，これらの手法はネットワーク内のすべての端末が検索クエリ，およびクエリ応答を送信するため，検索結果の取得に必要のない端末によるメッセージ転送から，不要なトラヒックやメッセージ衝突が発生してしまう．本論文では，この問題を解決するため，アドホックネットワークにおけるTop-k検索のためのルーティング手法を提案する．提案手法では，各端末がスコアが大きいデータを取得するための検索クエリの送信先端末（宛先）を管理する経路表を作成する．また，検索を要求するデータを指定し，そのデータに対応する宛先に検索クエリをユニキャストすることで，検索結果の取得に必要のない端末へのメッセージ転送を抑制する．さらに，ネットワークトポロジ変化にも着目し，トポロジ変化が激しい環境においても取得精度の低下を抑制することを目的として，提案手法の拡張手法も提案する．シミュレーション実験の結果から，提案手法は，小さいトラヒックで既存手法以上の取得精度を維持していることを確認した．

In mobile ad hoc networks, using a top-k query is effective to acquire only necessary data items. In a previous work, the methods which the query issuer floods a query message over the network and nodes that received the message prune data items which are not included in the top-k result by estimating kth score have been proposed. However, in these methods, unnecessary nodes to acquire the top-k result also transmit query and reply messages, which provokes unnecessary traffic and message collisions. In this paper, we propose a top-k query routing method in mobile ad hoc networks. Our proposed method utilizes a routing table which maintains node identifiers (query addresses) to forward a query message to acquire data items with high scores. Each node specifies ranks of data items to retrieve and sends a query message to corresponding query addresses. As a result, the proposed method can suppress unnecessary traffic while keeping high accuracy of query result. We also propose an extension of the proposed method, which aims to prevent the decrease of acucracy of query result in highly dynamic network. The simulation results show that the proposed methods acheive high accuracy of query result with small traffic compared with the existing method.

収録刊行物

• 情報処理学会論文誌

  情報処理学会論文誌 54 (8), 2036-2047, 2013-08-15

キーワード

• [一般論文 (推薦論文)] Top-k検索，ルーティング，モバイルアドホックネットワーク

詳細情報

• CRID: 1050001337903266048
• NII論文ID: 110009596043
• NII書誌ID: AN00116647
• ISSN: 18827764
• Web Site: http://id.nii.ac.jp/1001/00094783/
• 本文言語コード: ja
• 資料種別: journal article
• データソース種別:
  • IRDB
  • CiNii Articles
  • KAKEN