著者

佐々木 勇和 原 隆浩 西尾 章治郎

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.52, no.1, pp.175-186, 2011-01-15

---

アドホックネットワークでは,膨大なデータの中から必要なデータのみを効率的に取得するため,端末が何らかの値(スコア)によって順序付けられたデータの上位k個のものを検索するTop-k検索を用いることが有効である.本論文では,アドホックネットワークにおいて,トラヒックの削減と検索結果の取得精度の低下を抑止を目的とするTop-k検索手法を提案する.提案手法では,各端末がヒストグラムを作成し,ネットワーク全体のk番目のスコアを推定する.次に,推定したk番目のスコア以上のスコアを持つデータを返信することで,できる限り検索結果に入るデータのみを返信する.また,返信先の端末とのリンク切断を検出した端末は,他の隣接端末にクエリ応答を返信することで,検索結果の取得精度の低下を抑止する.In mobile ad hoc networks , to acquire only necessary data items, it is effective that each mobile node retrieves data items using a top-k query, in which data items are ordered by the score of a particular attribute and the query-issuing mobile node acquires data items with the k highest scores. In this paper, we propose a query processing method for top-k query for reducing traffic and also keeping high accuracy of the query result. In this method, each node constructs a histogram and estimates the k-th score in the entire network. When transmitting a reply, each mobile node sends back only data items whose scores are larger than the estimated k-th score to reduce traffic as much as possible. Moreover, when a mobile node detects the disconnection of a radio link, it sends the reply to another neighboring node to keep high accuracy of the query result.