文献

J-GLOBAL ID：201402227232341889   整理番号：14A0775712

アドホックネットワークにおける貪欲な幾何学的ルーティングアルゴリズムへの統一見解

A Unified View to Greedy Geometric Routing Algorithms in Ad Hoc Networks

著者 (6件)： CHUN Jinhee (Graduate School of Information Sciences, Tohoku Univ.) ,  SHIOURA Akiyoshi (Graduate School of Information Sciences, Tohoku Univ.) ,  SHIOURA Akiyoshi (JST, ERATO, Kawarabayashi Large Graph Project) ,  MINH TIEN Truong (Graduate School of Information Sciences, Tohoku Univ.) ,  TOKUYAMA Takeshi (Graduate School of Information Sciences, Tohoku Univ.) ,  TOKUYAMA Takeshi (JST, ERATO, Kawarabayashi Large Graph Project)
資料名： IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences (Web)  (IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences (Web))
巻： E97.A  号： 6  ページ： 1220-1230 (J-STAGE)  発行年： 2014年 
JST資料番号： U0466A  ISSN： 1745-1337  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 筆者らは,アドホックネットワークにおける貪欲な幾何学的ルーティングアルゴリズムへの統一見解を与えた。これに対し,筆者らは最初に,点集合の合同変換の下で不変である目的関数のクラスを使用して,貪欲なルーティングアルゴリズムの一般形式を提示した。筆者らは,貪欲ルーティング,コンパスルーティング,そして中間ルーティングのような,いくつかの既知の貪欲ルーティングアルゴリズムが,汎用貪欲ルーティングアルゴリズムの特殊事例とみなすことができることを示した。加えて,貪欲ルーティング統一見解に誘発され,筆者らは3つの新しい貪欲ルーティングアルゴリズムを提案した。それから筆者らは,Delaunayグラフ上で,パケット配達を保証する筆者らの汎用貪欲ルーティングアルゴリズムに対する十分条件を導出した。この条件は,所定のルーティングアルゴリズムがパケット配達を保証するか否かをチェックすることを容易にし,目的関数の凸一次結合の下で閉じている。貪欲ルーティング,中間ルーティング,そして本論文において提案した貪欲ルーティングアルゴリズムが,その十分条件を満足することを示した。すなわち,それらはDelaunayグラフ上で,パケット配達を保証した。筆者らはまた,これらの方法の利点と欠点を論じた。(翻訳著者抄録)

シソーラス用語： *アドホックネットワーク ,  検索 ,  *アルゴリズム ,  *意見 ,  集合 ,  変換 ,  重合せ ,  目的関数 ,  一般式
準シソーラス用語： *ルーティングアルゴリズム ,  一般形式 ,  *見解 ,  合同 ,  点集合 ,  貪欲な検索

分類 (2件)： 計算機網  (JC03000K) ,  数学一般  (AB01000K)

引用文献 (12件)：

• [1] P. Bose and P. Morin, “Online routing in triangulations,” SIAM J. Comp., vol.33, pp.937-951, 2004.
• [2] P. Bose, L. Devroye, M. Loeffler, J. Snoeyink, and V. Verma, “The spanning ratio of the Delaunay triangulation is greater than π/2,” Proc. 21st Canadian Conf. Computational Geometry, pp.165-167, 2009.
• [3] G.G. Finn, “Routing and addressing problems in large metropolitan-scale internetworks,” Tech. Rep. ISI/RR-87-180, Univ. Southern California, March 1987.
• [4] E. Kranakis, H. Singh, and J. Urrutia, “Compass routing on geometric networks,” Proc. 11th Canadian Conf. Computational Geometry, pp.51-54, 1999.
• [5] F. Kuhn, R. Wattenhofer, Y. Zhang, and A. Zollinger, “Geometric ad-hoc routing: of theory and practice,” Proc. 22nd ACM Symp. Principles of Distributed Computing, pp.63-72, 2003.

タイトルに関連する用語 (4件)： アドホック ,  幾何学 ,  ルーティングアルゴリズム ,  見解